7 ms·
programming challenge
- benjoffe 16y agoThe section under "Submission Directions" is exactly the same as the directions here: http://www.facebook.com/careers/puzzles.php 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.
- beaumartinez 16y agoI 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+execute+in+a+*NIX+type+environment+(sorry,+no+Windows+specific+solutions+are+accepted).+You+are+not+guaranteed+any+libraries+or+plugins+beyond+what+is+part+of+the+language/interpreter+itself.+The+following+languages+are+accepted:%22 http://www.google.com/search?q=%22All+submissions+must+execu...
- jaekwon 16y agoNo, Facebook's directions were good so I copied them a bit. I expected people to notice.
- Swizec 16y agoThis looks like a really cool challenge. Reminds me a bit of the knapsack problem (http://en.wikipedia.org/wiki/Backpack_problem http://en.wikipedia.org/wiki/Backpack_problem) But something tells me the solution is going to be a lot less simple though.
- uncompetence 16y agoIf 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
- jules 16y agoInteger linear programming!
- Someone 16y agoHm, 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.
- jaekwon 16y agoThe question is, why on earth would anybody come up with such a confounding puzzle? Jars and balls??
- lisper 16y agoView source on the home page is interesting too.
- Natsu 16y agoI 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).
- jaekwon 16y agothe loser has the least number of friends. no, you can't friend yourself.
- sharpneli 16y ago"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.
- jaekwon 16y agoThe social graph need not be planar, say if the world is a donut.
- sharpneli 16y agoI'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.
- deleted 16y ago[deleted]
- tlb 16y agoThe 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 15
- ciju 16y agois there a need for jar2:3 at line 12 ?
- Natsu 16y agoDoesn'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.
- MtL 16y agoWe 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
- Natsu 16y agoOh, 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.
- Natsu 16y agoHonestly, 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...
- earl 16y agoIf 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.
- njckname2 16y agoYou can tell the author is the user who submitted this to hacker news.
- jaekwon 16y agoYeah 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.
- gacek 16y agoSo how is this "challenge" more interesting than thousands of problems on SPOJ, UVA, topcoder or project Euler?
- jaekwon 16y agoI challenge you to create a more interesting problem.
- daivd 16y agoHow 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 ;).
- jaekwon 16y agoGood problems. What are you working on now?
- yousuffauzan 16y agoUnder 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.
- daivd 16y agoIt 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 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.
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]
- yousuffauzan 16y agoAnother solution for white=35. 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