programming challenge

[benjoffe]

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]

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

[jaekwon]

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

[tlb]

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

[Natsu]

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

[jaekwon]

:) you are correct.

[ciju]

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

[gacek]

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

[jaekwon]

I challenge you to create a more interesting problem.

[lisper]

View source on the home page is interesting too.

[Natsu]

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

[Swizec]

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]

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

[Someone]

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.

[jaekwon]

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

[earl]

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]

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

[yousuffauzan]

Another 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