If you treated this as a variant on the backpack problem, you run into trouble as you can't properly memoize or use dynamic programming. You use 'timesteps' as the size of the 'knapsack' since the number of balls is unbounded. At each timestep, you cannot determine the the optimal solution to the subproblem and you'd have to save every possible ball combination.
TL;DR - It gets to be a pretty messy/bad backpack and should probably be solved another way
Hm, let's see. 15 moves, an average branching factor of say 5, 5^15 ~ 3E10. Bookkeeping will be a bit of work, so let's give that 1E4 instructions per step gives us 3E14 steps or 1E5 seconds at 3GHz, single-core.
So, brute-forcing this looks doable in a day, probably a lot less, as I took a high estimate for the branching factor. One instruction/cycle probably is on the high side, but that can be compensated for by using multiple cores.
"the world is a sphere,
and friends don't cross each other."
My guess would be that the social graph needs to be planar (e.g embeddable on a plane so that no edges go across eachother).
The world is a sphere can be interpreted in too many ways. One would be that there exists a hamiltonian cycle for the graph and other would be that if you do a depth first search you'd always hit yourself eventually.
My strong guess would be that 2 friends is the least and the most a loser may have.
Biggest problem with too smart puzzles such as this is that there are way too many ways to legitimately interpret them.
I'd consider that a minor adjustment as it would still essentially be a planar graph (with periodic boundary conditions). Locally both of the cases look identical.
Just checked wiki while writing this and toroidal embeddings are a subclass of planar graphs.
I think I got it now. Don't read this if you are afraid of possible spoiling.
We are looking for a graph with highest possible minimum vertice count for any single node. The answer is 6. This graph comes from simply making a hexagonal tiling with node on center and vertices going trough edges. Any tiling with more angles does not produce a planar graph and we'd have to insert polygons with less vertices and thus less neighbours and therefore lowering the smallest edge count.
Oh, I did it by hand (and I was checking all the balls). I just missed one of the +4s somehow.
I wonder how efficient people can make this. I've envisioned all kinds of test cases that crank up the branching factor, require that you find solutions even if you have to trade away white balls for them and other such things.
Just because he made them positive integers doesn't mean that there are no ways to punish solutions that won't scale or those that don't always find optimal solutions.
Honestly, I wish I were on the other end of this. I wonder how many solutions I could find test cases to break even assuming I play nice and allow only positive integers?
Yes, I really did imagine all kinds of cases involving zero time and negative time rules (or having zero time to produce anything) and tried to conform them to the spec, but most of them conflict with the output requirements. Not all, though...
Care to elaborate? Is the solution presented in the original article incorrect?
BTW, the original solution yields 27 whites: 5 from the start, and then jar1 is used 2+3+3+3=11 times, yielding 22 more.
I noticed the solution in the article is in a "steady state", that can produce 6 whites every 3 steps, or 2 whites per step. The better solution by tlb produces 26 whites in 8 steps, but I didn't check whether it is sustainable (in the sense that after those 8 steps we have enough material to start over).
It's an interesting problem, and I couldn't even model it after a first glance using a graph or linear programming. Will try again later :)
If you run whois and check linkedin, you can figure out where the author most likely works and what sort of things they do... No names since he probably doesn't want to be googleable.
Yeah I don't care to be anonymous.
I don't work at the moment, I'm building connections and learning some business chops at an incubator to start a business.
If you want to change life on earth as we know it, you know where to find me.
How about the same problem, but with each Jar having:
a) a known fail percentage - 40% of the time the Jar fails and produces nothing. Maximize expected win.
b) an unknown fail percentage, evenly distributed between 0 and 100%. Find a strategy that maximizes expected win over many runs (each run has new fail probabilities), by perfectly balancing between exploration of jars and exploitation. If you can find an optimal (and practical) strategy for this one I applaud you!
Also, I solved your example with a simple Python brute-forcer with < 1s run time. I don't know if I care enough to write a parser of your file format just to mail it in ;).
Under 1 sec is amazing. When you say brute force, do you mean that for the first step (TS 1), you took all the three routes available, [0,0], [1,0], [2,0] for jar 1 and 2. Cause that just makes the number of branches too many to be solved in a reasonable amount of time. I would love to have a peek at you code.
It is real brute force, but I do not investigate some stupid nodes. If I choose to not use an available jar during a timestep, I disqualify that jar, until another jar has been used, since there is no point in waiting to use a jar unless you want to save your balls for another jar.
The code is ugly and undocumented. I think the same could be accomplished in less than 10 lines of Haskell :).
http://pastebin.com/MfXK9fwS
An implementation detail is that my branches are actually "jar1" "jar2" and "stepforward". To use a jar many times, you do jar1, jar1, stepforward.
As my first erlang program, I tried to solve this problem. The code is very ugly, and rather long for my taste, but it solves the thing in 917 steps. I also took the case where if no output has been gotten in a particular timestep, then do not consider any jars.
The section under "Submission Directions" is exactly the same as the directions here: http://www.facebook.com/careers/puzzles.php verbatim even down to the exact version numbers.
Is there some standard testing package that these are both using? Otherwise it seems fishy.
I noticed that too. Googling the text yields quite a few matches; my guess is either they think "Facebook does it, so we should do it like that too", or it's a standard testing package or something.
42 comments
[ 2.7 ms ] story [ 94.0 ms ] threadBut something tells me the solution is going to be a lot less simple though.
TL;DR - It gets to be a pretty messy/bad backpack and should probably be solved another way
So, brute-forcing this looks doable in a day, probably a lot less, as I took a high estimate for the branching factor. One instruction/cycle probably is on the high side, but that can be compensated for by using multiple cores.
It has me wondering how 'loser' is defined and if a person can be their own 'friend' ... (read their riddle poem if that makes no sense to you).
My guess would be that the social graph needs to be planar (e.g embeddable on a plane so that no edges go across eachother).
The world is a sphere can be interpreted in too many ways. One would be that there exists a hamiltonian cycle for the graph and other would be that if you do a depth first search you'd always hit yourself eventually.
My strong guess would be that 2 friends is the least and the most a loser may have.
Biggest problem with too smart puzzles such as this is that there are way too many ways to legitimately interpret them.
Just checked wiki while writing this and toroidal embeddings are a subclass of planar graphs.
We are looking for a graph with highest possible minimum vertice count for any single node. The answer is 6. This graph comes from simply making a hexagonal tiling with node on center and vertices going trough edges. Any tiling with more angles does not produce a planar graph and we'd have to insert polygons with less vertices and thus less neighbours and therefore lowering the smallest edge count.
http://en.wikipedia.org/wiki/Geodesic_dome
Start producing 4 more (2 jars) at timestep 1.
Start producing 4 more at timestep 6.
Start producing 22 more at timestep 12.
22 + 4 + 4 + 5 = 35
I wonder how efficient people can make this. I've envisioned all kinds of test cases that crank up the branching factor, require that you find solutions even if you have to trade away white balls for them and other such things.
Just because he made them positive integers doesn't mean that there are no ways to punish solutions that won't scale or those that don't always find optimal solutions.
Yes, I really did imagine all kinds of cases involving zero time and negative time rules (or having zero time to produce anything) and tried to conform them to the spec, but most of them conflict with the output requirements. Not all, though...
BTW, the original solution yields 27 whites: 5 from the start, and then jar1 is used 2+3+3+3=11 times, yielding 22 more.
I noticed the solution in the article is in a "steady state", that can produce 6 whites every 3 steps, or 2 whites per step. The better solution by tlb produces 26 whites in 8 steps, but I didn't check whether it is sustainable (in the sense that after those 8 steps we have enough material to start over).
It's an interesting problem, and I couldn't even model it after a first glance using a graph or linear programming. Will try again later :)
a) a known fail percentage - 40% of the time the Jar fails and produces nothing. Maximize expected win.
b) an unknown fail percentage, evenly distributed between 0 and 100%. Find a strategy that maximizes expected win over many runs (each run has new fail probabilities), by perfectly balancing between exploration of jars and exploitation. If you can find an optimal (and practical) strategy for this one I applaud you!
Also, I solved your example with a simple Python brute-forcer with < 1s run time. I don't know if I care enough to write a parser of your file format just to mail it in ;).
The code is ugly and undocumented. I think the same could be accomplished in less than 10 lines of Haskell :). http://pastebin.com/MfXK9fwS
An implementation detail is that my branches are actually "jar1" "jar2" and "stepforward". To use a jar many times, you do jar1, jar1, stepforward.
Is there some standard testing package that these are both using? Otherwise it seems fishy.
http://www.google.com/search?q=%22All+submissions+must+execu...
1
2 jar1:1
3
4 jar2:3
5 jar1:1
6
7 jar2:4
8 jar1:1
9
10 jar2:6
11
12
13 jar1:12
14
15