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)?
Posted: Fri Apr 29, 2016 4:34 am
by 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.
Posted: Fri Apr 29, 2016 6:37 am
by 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.
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?
Posted: Sat Apr 30, 2016 1:46 pm
by 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.
Posted: Sun May 01, 2016 3:59 pm
by AxleGreaser
In post 79, Kagami wrote:
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.
Posted: Mon May 02, 2016 1:41 am
by Kagami
I think think you're confusing the numbers that be represented by some number of bits with the number of bits
Posted: Mon May 02, 2016 4:20 am
by Ircher
2^64 ~ 1000^6 * 2^4
Posted: Mon May 02, 2016 10:53 am
by 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.
Posted: Mon May 02, 2016 11:44 am
by 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.
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
Posted: Thu May 05, 2016 12:49 pm
by 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.
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) )
Posted: Fri May 20, 2016 10:59 pm
by AxleGreaser
OOOOPS
apparentyl I woke up with head scrwed on backwards and upsdie down
the previous post is bollocks please ignore me...
Posted: Tue May 31, 2016 5:54 pm
by 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?
Posted: Tue May 31, 2016 6:18 pm
by 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.
Posted: Sun Jun 05, 2016 3:55 pm
by 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.
Posted: Sun Jun 05, 2016 10:42 pm
by Realeo
Flubbernugget wrote: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.
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.
[*] 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.
