programming challenge

by jaekwon • 16 years ago

20 39 16 years ago

Swizec• 16 years ago

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.

uncompetence• 16 years ago

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

jules• 16 years ago

Integer linear programming!

Someone• 16 years ago

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.

jaekwon11• 16 years ago

The question is, why on earth would anybody come up with such a confounding puzzle? Jars and balls??

lisper2• 16 years ago

View source on the home page is interesting too.

Natsu4• 16 years ago

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).

jaekwon11• 16 years ago

the loser has the least number of friends. no, you can't friend yourself.

sharpneli4• 16 years 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.

tlb• 16 years ago

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 
  15

ciju• 16 years ago

is there a need for jar2:3 at line 12 ?

Natsu4• 16 years ago

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.

Natsu4• 16 years ago

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...

jaekwon11• 16 years ago

Thanks for your input Natsu, I edited the puzzle to require positive integers.

jaekwon11• 16 years ago

:) you are correct.

silvajoao• 16 years ago

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 :)

earl• 16 years ago

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.

njckname2• 16 years ago

You can tell the author is the user who submitted this to hacker news.

jaekwon11• 16 years ago

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.

gacek• 16 years ago

So how is this "challenge" more interesting than thousands of problems on SPOJ, UVA, topcoder or project Euler?

jaekwon11• 16 years ago

I challenge you to create a more interesting problem.

daivd2• 16 years ago

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 ;).

benjoffe• 16 years ago

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.

beaumartinez• 16 years ago

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...

jaekwon11• 16 years ago

No, Facebook's directions were good so I copied them a bit. I expected people to notice.

yousuffauzan3• 16 years ago

Another solution for white=35.

2 jar1:1

4 jar2:3

5 jar1:1

7 jar2:4

8 jar1:1

10 jar2:6

13 jar1:12

programming challenge

Related Stories