Mafiascum Coding Challenge

[Kagami]

Vonflare, I'm not sure what the input to the desired function is. Is it an array of strings, or a string together with a preexisting grid?

Is the grid of fixed size prior to any input (as it apparently is in your example)?

Does the grid fit it such that there are as many empty spaces as possible (as in your example) or does it prefer to use completely empty diagonals (as in the problem statement)?

[Kagami]

I think a more elegant problem statement for this challenge is as follows:

Input is a set of strings. The function should output the smallest square matrix such that each string fits in the manner vonflare specified. When there are multiple configurations that yield the smallest square matrix, the output should be one (though there are still multiple possibilities) that also maximizes the number of empty squares.

[Kagami]

Spoiler: Game of life problem

You know that for a grid with N elements there are 2^N possible configurations, thus each board can be nicely represented as an N-bit number, and you are guaranteed to see a repeat within 2^n + 1 steps (so the problem halts even in the torus-board case).

Given the board input, you simply run it, placing each observed board into a suitable data structure (binary search tree seems reasonable) together with the step number of the observation. As soon as you observe a state that's already in the tree, you're done, and the board oscillates with period equal to the current step number minus the previously observed step number. If you care only about stable states, you can halve memory usage by not storing step numbers, and instead just comparing the value of the current state with that of the prior state upon algorithm completion.

[AxleGreaser]

Spoiler: Game of life problem

You know that for a grid with N elements there are 2^N possible configurations, thus each board can be nicely represented as an N-bit number, and you are guaranteed to see a repeat within 2^n + 1 steps (so the problem halts even in the torus-board case).

Given the board input, you simply run it, placing each observed board into a suitable data structure (binary search tree seems reasonable) together with the step number of the observation. As soon as you observe a state that's already in the tree, you're done, and the board oscillates with period equal to the current step number minus the previously observed step number. If you care only about stable states, you can halve memory usage by not storing step numbers, and instead just comparing the value of the current state with that of the prior state upon algorithm completion.

Your avatar seems strangely apt.

Spoiler: a problem

How big is the memory virtual or otherwise and so what maximize board size will the proposed solution work for?

[Kagami]

Worst case scenario is that you store 2^(2N) bits, but in practice it's going to be far fewer: (2^N) * foo, where foo is the number of steps between the initial state and the first repeated state.

If you're worried about memory, which perhaps you should be for a large board, you can run two threads of the game. For each step in thread A, thread B advances two steps. They will eventually have the same board, you store that step number, and then keep going until they meet again. The difference of the final step number and the earlier step number is the period of the final board state.

[AxleGreaser]

If you're worried about memory, which perhaps you should be for a large board, you can run two threads of the game.

2^32 is 4 gig.
A game of life board with 32 cells is trivially small.
2^48 is 256 terra bytes
2 ^ 64 (and 8x8 game of life board.) is ... oopsie
Non trivial boards would fairly rapidly have more memory required than there are baryons in the visible universe.

[Kagami]

I think think you're confusing the numbers that be represented by some number of bits with the number of bits

[Ircher]

2^64 ~ 1000^6 * 2^4

[Kagami]

The problem is that I got some wires crossed in my head.

The worst-case memory requirement for the original algorithm is N*2^N bits with the actual requirement N*<steps of longest run>, which is generally not too bad.

The alternative algorithm requires at least twice as much computation. You'd likely want to pick between them based on the input's N.

I can't think of a better algorithm to solve the problem, and I would surprised if anything beyond an incremental refinement is possible.

[Kagami]

Best solution is probably to run the first algorithm until some memory limit is reached, then apply the second algorithm from there, giving you the best of both worlds.

[yessiree]

Spoiler: problem 8 solution

Code: Select all

function maxProd(arr) {
    if (arr.length <= 0) return false;

    var curr_max = arr[0];
    var curr_min = arr[0];
    var max_prod = curr_max;

    for (var i = 1; i < arr.length; i++) {
        var prev_max = curr_max;
        var prev_min = curr_min;
        curr_max = Math.max(arr[i], arr[i] * prev_min, arr[i] * prev_max);
        curr_min = Math.min(arr[i], arr[i] * prev_min, arr[i] * prev_max);
        max_prod = Math.max(max_prod, curr_max);
    }
    return max_prod;
}

At each iteration, the algorithm keeps track of a max value as well as a min value to account for negative values, since the min value has a chance to become the max value at the next iteration, and vice-versa

[Ircher]

Okay, a simple problem:

Given x and y, find the least common multiple of X and Y. If the language has a builtin feature for this, don't use it.

[Realeo]

Why I can't spoiler code..

Spoiler: Ircher's LCM

Code: Select all

#Python
def LCM(a,b):
 return a*b/GCM(a,b)

def GCM(a,b):
 if a==0:
  return b
 return GCM(b%a,a)

[Plotinus]

Code: Select all

[spoiler=Ircher's LCM]
[code]
#Python
def LCM(a,b):
 return a*b/GCM(a,b)

def GCM(a,b):
 if a==0:
  return b
 return GCM(b%a,a)

[/spoiler][/code]

produces:

Spoiler: Ircher's LCM

Code: Select all

#Python
def LCM(a,b):
 return a*b/GCM(a,b)

def GCM(a,b):
 if a==0:
  return b
 return GCM(b%a,a)

[Ircher]

hLet's see:

LCM(4,6) --> Yields 4 * 6 / GCM(4, 6) = 24 / 2 = 12. 2*2 and 3*2 : 2 * (2*3) --> 12

4,6 --> 2,4
2,4 --> 0,2

Looks correct to me.

[Ircher]

Now, to make it a but tougher:

Make it where it can handle an arbritrary number of arguments. The number of arguments provided may be supplied as a parameter.

[Realeo]

Now, to make it a but tougher:

Make it where it can handle an arbritrary number of arguments. The number of arguments provided may be supplied as a parameter.

Simple.

Take the first two number. Find the lcm, Find the lcm of the lcm and the 3rd number. Rinse and repeat. Code coming later.

EDIT:

Spoiler: Ircher's LCM

Code: Select all

def multipleLCM(array):
 a,b = array[0],array[1]
 answer=lcm(a,b)
 array.pop(0)
 array.pop(0)
 while len(array) != 0:
  a=array[0]
  answer=lcm(answer,a)
  array.pop(0)
 return answer

#Python
def LCM(a,b):
 return a*b/GCM(a,b)

def GCM(a,b):
 if a==0:
  return b
 return GCM(b%a,a)

[Ircher]

That works!

[AxleGreaser]

Now, to make it a but tougher:

Make it where it can handle an arbritrary number of arguments. The number of arguments provided may be supplied as a parameter.

Simple.

Take the first two number. Find the lcm, Find the lcm of the lcm and the 3rd number. Rinse and repeat. Code coming later.

EDIT:

Spoiler: Ircher's LCM

Code: Select all

def multipleLCM(array):
 a,b = array[0],array[1]
 answer=lcm(a,b)
 array.pop(0)
 array.pop(0)
 while len(array) != 0:
  a=array[0]
  answer=lcm(answer,a)
  array.pop(0)
 return answer

#Python
def LCM(a,b):
 return a*b/GCM(a,b)

def GCM(a,b):
 if a==0:
  return b
 return GCM(b%a,a)

LCM is an odd concept. It is equivalent to wanting the smallest of all the common prime factors

So just to check that I have that oddness right.
The LCM of 30 and 12 is 2? (3 and 6 are also common multiples but 2 is smallest)
(also implcitly is not 1)

Re Irchers list problem.

LCM of 30,12, 9....

The algorithm above claims
LCM ( LCM (30,12) , 9 ) is the same as LCM(30,12,9)

its not.

The LCM of 30,12 is 2. (we chucked the 3 out because both numbers had prime factor of 2.)

LCM of 2 and 9 is ... doesnt have one?

Ok trying again.....

nope i cant make the algorithm succeed but be wrong, but it can for lists fail to find an LCM when there is one.

Spoiler: alt alg no code

LCM (a,b,c, ...) = smallest prime factor of GCM(a,b,c,...)
or using existing functions.
LCM (a, GCM(a,b,c,...) ) //implement GCM(...) by successive calls to GCM(x,y) )

[AxleGreaser]

OOOOPS

apparentyl I woke up with head scrwed on backwards and upsdie down


the previous post is bollocks please ignore me...

[Realeo]

Can we have a coding competition? I mean, like the ICM ICPC or Google Jam or Codeforces style? I think some site lets us to host one?

[Frozen Angel]

Its doable.

even in this site and theme

we need to choose a team for making the questions and stuff and asking to see if people are interested or not.

[Flubbernugget]

Shameless bump. Updating the OP with Ircher's problem and crediting Realeo with the solution.

I would have to look into the rules of the coding competition to see how it would be modded on the side and how much work that would take before I offer hosting/modding. Consider me interested at the least.

[Realeo]

Shameless bump. Updating the OP with Ircher's problem and crediting Realeo with the solution.

I would have to look into the rules of the coding competition to see how it would be modded on the side and how much work that would take before I offer hosting/modding. Consider me interested at the least.

What came to my mind was Project Euler style competition.

Preface:

Most common OJ ask you to upload the code an let the judge compiles it for you. Euler just posts the test case and he just asked you for your solution.

Like Google Jam, but if GJ you only have 5 minutes to submit the answer after you downloaded the .in, Euler-style let you submit your answer at any point that you want.

Format:

We will have problem call where user can send in problem. Each user can have max. 1 problem accepted.

Material that will be our person of interest.

Code: Select all

[*] Ad-Hoc
[*] Geometry
[*] Math
[*] Brute force
[*] Divide & Conquer
[*] Searching (ie. Binary search)
[*] Dynamic Programming
[*] (anything else that I forgot)

Then competition day. We will release the problem and give 1 weeks to compete. They can submit their answer via PM.

Each correct answer worth 100 points. But 3 most difficult problem worth 125 points instead. Player who send in the problem is automatically credited with correct answer.

The winner is the one with most point.

A primitive programming, if OJ is not a solution.