Solutions to the 2nd gambling puzzle

Second was this Python snippet from Taylor...

1. #!/usr/bin/python
2. wins = [158
3. end = len(wins) - 1
4. def maxSeq(start):
5.         if start == end:
6.                 return [wins[start]
7.         elif start + 1 == end:
8.                 opt1 = [wins[start]
9.                 opt2 = [wins[end]
10.         elif start + 2 == end:
11.                 opt1 = [wins[start]+wins[end]
12.                 opt2 = [wins[start+1]
13.         else:
14.                 subseq1 = maxSeq(start+2)
15.                 subseq2 = maxSeq(start+3)
16.                 opt1 = [wins[start] + subseq1[0]
17.                 opt2 = [wins[start+1] + subseq2[0]
18. if opt1[0] > opt2[0]:
19.                 return opt1
20.         return opt2
21. &nsbp;
22. sol = maxSeq(0)
23. print "Max:"
24. print sol[1]

Next up is some Haskell from Cale Gibbard

1. import Data.List
2. gamble = [158 ... 380]
3. gen [] = [[]]
4. gen [x] = [[x]] -- note we assume all elements are positive here
5. gen (x:y:xs) = gen (y:xs) ++ map (x:) (gen xs)
6.  
7. comparing p x y = compare (p x) (p y)
8. solve = maximumBy (comparing sum) . gen
9. splitBy p xs =
10. case break p xs of
11. (a,[]) -> [a]
12. (a,_:b) -> a : splitBy p b
13.  
14. main = do
15. let sol = splitBy (<= 0) gamble >>= solve
16. print sol

Andrew then chimed in with another Haskell solution, this one not relying on recursive calls.

1. -module(gambler).
2. -compile(export_all).
3.  
4. -define(DATA
5. start() -> {{Sum
6.            {Sum
7. look([]) -> {{0
8. look([H|T]) -> {{Sum1
9.                if Sum2 + H > Sum1 ->
10.                        {{Sum2 + H
11.                   true ->
12.                        {{Sum1
13.                end.

Soren then provided 2 different versions of the solution in C, a recursive solution, and a non-recursive linear solution. Aaron then provided a O(1) solution, that compiles in O(N), which was clever I thought

Going back towards the short sweet and a little bit weird, we have an Objective Caml solution provided by Cameron.

1. let gambler_max l =
2.   let rec gambler_max_aux l max_list
3. max_total max_not_last_list max_not_last_total =
4.    match l with
5.     h::t ->
6.      if max_not_last_total + h > max_total then
7.       gambler_max_aux t (h::max_not_last_list) (max_not_last_total+h) max_list max_total
8.      else gambler_max_aux t max_list max_total max_list max_total
9.     | [] -> max_list
10.   in
11.    gambler_max_aux l [] 0 [] 0;;

Bart mailed me a Perl solution, which I will post once my laptop returns to life, or once Bart mails it to me again Two other interesting offerings were a C# one from Kaerber, and a Ruby solution from Nikhil Gupte.

C#

1. public static void Try( int[] input
2. {
3. int length = input.Length;
4. int sumC
5. for( int i = 0; i < length; i++ )
6. {
7. sumC = ( sumPP > sumPPP ? sumPP : sumPPP ) + input[i];
8. sumPPP = sumPP;
9. sumPP = sumP;
10. sumP = sumC;
11. }
12. int result = sumP > sumPP ? sumP : sumPP;
13. output.Text = string.Format( "${0}"
14. }

And of course the newest 13 year language there is, Ruby

1. days = [158 ... 380]
2. total = 0
3. soln = Array.new
4. while (days.length > 0) do
5.     a = days[0] unless days[0].nil?
6.     b = days[1] unless days[1].nil?
7.     c = days[2] unless days[2].nil?
8.     d = days[3] unless days[3].nil?
10.     if a + c > b + d || a + d > b + d then
11.         soln < < a
12.         2.times {days.shift}
13.     else
14.         soln < < b
15.         3.times {days.shift}
16.     end
17.     total += soln.last
18. end
19. p soln
20. p 'total: ' + total.to_s

That might be the end of Steve for a short while, I'm trying to find/create other interesting less known programming puzzles to see the solutions. I get a lot of emails (well 5 anyways) from people saying they find these really educational, and for that I have to thank everyone who posts solutions or comments. If I didn't include your solution it's not cause it's bad, it's because I forgot. If you mail me, I'll post it up, with apologies. I'd still like to see a J solution to this also