programming challenge(glyphtree.com)
glyphtree.com
programming challenge
http://glyphtree.com/puzzles
10 comments
[deleted]
[deleted]
This looks like a really cool challenge. Reminds me a bit of the knapsack problem (http://en.wikipedia.org/wiki/Backpack_problem)
But something tells me the solution is going to be a lot less simple though.
But something tells me the solution is going to be a lot less simple though.
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
TL;DR - It gets to be a pretty messy/bad backpack and should probably be solved another way
Integer linear programming!
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.
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 question is, why on earth would anybody come up with such a confounding puzzle? Jars and balls??
View source on the home page is interesting too.
I was kind of hoping it would explain what Glyphtree is, but it's a riddle/poem.
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).
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).
"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.
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.
The social graph need not be planar, say if the world is a donut.
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.
Just checked wiki while writing this and toroidal embeddings are a subclass of planar graphs.
I'm sorry, the puzzle is asking for a global property. The new text has the adjustments.
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.
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.
I don't think it's possible to tile a sphere with hexagons. You have to throw a couple of pentagons in.
http://en.wikipedia.org/wiki/Geodesic_dome
http://en.wikipedia.org/wiki/Geodesic_dome
True. So for a spherical topology the largest minimum is 5. However for toroidal topology the largest minimum is 6.
the loser has the least number of friends.
no, you can't friend yourself.
[deleted]
The solution given is incorrect. It yields 29 white balls, while the following yields 35.
1 jar1:2
2
3 jar2:3
4
5
6 jar1:2 jar2:4
7
8
9 jar2:6
10
11
12 jar1:11 jar2:3
13
14
15Honestly, 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...
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...
Thanks for your input Natsu, I edited the puzzle to require positive integers.
:) you are correct.
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 :)
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 :)
The sample solution on the original article is incorrect.
is there a need for jar2:3 at line 12 ?
Doesn't seem like there is. Also, is my count wrong, or does that only produce 31 white balls? It's still more than the 29, though.
We have 5 from the start.
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
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
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.
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.
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.
You can tell the author is the user who submitted this to hacker news.
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.
So how is this "challenge" more interesting than thousands of problems on SPOJ, UVA, topcoder or project Euler?
I challenge you to create a more interesting problem.
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 ;).
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 ;).
Good problems. What are you working on now?
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.
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.
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.
http://www.google.com/search?q=%22All+submissions+must+execu...
http://www.google.com/search?q=%22All+submissions+must+execu...
No, Facebook's directions were good so I copied them a bit. I expected people to notice.
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