Saturday, November 4. 2006Programming Puzzle #2 Steve Returns
So everyone posted their solutions to the last programming puzzle, and we got to see all sorts of crazy shit, like this solution in J (i. >./) (0 >. +)/@:|.\ a
Is that even a language? Yes, it is. More about J at JSoftware.com. Another cool thing was that Tyler Griffin HicksWright stopped by, who you might remember from Project Aardvark. Anyways, Jeremy Weissmann from mathmeth.com mailed offering a variation of the puzzle. I played with it for a while, and decided that it's not as easy as it sounds, so here we go again... The blurbYour friend Steve is a psychic gambler. He can predict the profit or loss of each day of his gambling a whole month in advance. Here are his anticipated takings for the month... 
The actual figures are 158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380. To declare them in Java, its So the twist is this... Steve can gamble any days he wants. He is free to pick and choose, but the casino will not let him gamble on consecutive days (i.e. he can't gamble for 2 or more days in a row). How can he maximize his winnings? I am gonna mail all the old commenters, hopefully we can get another J solution, that language fascinates me Comments
Display comments as
(Linear | Threaded)
I've got a linear algorithm, but can't yet tell if it's correct. Can anyone do better than $5798 for the sample input?
Another tidbit. The solution space has Fibonacci growth, so this 33-day input has 3,524,578 potential solutions.
I get $5798 as well
[158,399,2,375,806,953,20,7,191,654,784,159,49,861,380] code in erlang: -module(gambler). -compile(export_all). -define(DATA, [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380]). start() -> look(?DATA). look([]) -> {0, []}; look([H|T]) -> {SumY, PathY} = look(T), case look(tail(T)) of {SumN, PathN} when SumN + H > SumY -> {SumN + H, [ H | PathN ]}; _ -> {SumY, PathY} end. tail([]) -> []; tail([_|T]) -> T.
#!/usr/bin/python
wins = [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380] def maxTake(start, end): if start == end: return wins[start] if end == start + 1: return max(wins[start], wins[end]) if end == start + 2: return max(wins[start] + wins[end], wins[start+1]) return max(wins[start] + maxTake(start+2, end), wins[start+1] + maxTake(start+3, end)) print maxTake(0, len(wins)-1)
Just realized the solution is the sequence, not the max. Not as pretty this way...
#!/usr/bin/python wins = [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380] end = len(wins) - 1 def maxSeq(start): if start == end: return [wins[start], [start]] elif start + 1 == end: opt1 = [wins[start],[start]] opt2 = [wins[end],[end]] elif start + 2 == end: opt1 = [wins[start]+wins[end],[start,end]] opt2 = [wins[start+1], [start+1]] else: subseq1 = maxSeq(start+2) subseq2 = maxSeq(start+3) opt1 = [wins[start] + subseq1[0], [start] + subseq1[1]] opt2 = [wins[start+1] + subseq2[0], [start+1] + subseq2[1]] if opt1[0] > opt2[0]: return opt1 return opt2 sol = maxSeq(0) print "Max:",sol[0] print sol[1]
good call on the split... it reduced my runtime from 2 seconds to 800usec
-module(gambler). -compile(export_all). -define(DATA, [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380]). start() -> lists:foldl(fun({Sum, Path}, {ASum, APath}) -> {ASum+Sum, Path ++ APath} end, {0, []}, [ look(X) || X split(D, [[]]). split([], Acc) -> Acc; split([H|T], Acc) when H =< 0 -> split(T, [[]|Acc]); split([H|T], [AccH|AccT]) -> split(T, [AccH ++ [H]|AccT]). look([]) -> {0, []}; look([H|T]) when H =< 0 -> look(T); look([H|T]) -> {SumY, PathY} = look(T), case look(tail(T)) of {SumN, PathN} when SumN + H > SumY -> {SumN + H, [ H | PathN ]}; _ -> {SumY, PathY} end. tail([]) -> []; tail([_|T]) -> T.
The problem with the solutions so far is that they make two recursive calls in order to compare the solution with or without the most recent element. This turns what should be a linear algorithm into an exponential one. Here's a linear version of one of the algorithms presented so far
-module(gambler). -compile(export_all). -define(DATA, [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380]). start() -> {{Sum, Path}, _} = look(?DATA), {Sum, Path}. look([]) -> {{0, []}, {0, []}}; look([H|T]) -> {{Sum1, Path1}, {Sum2, Path2}} = look(T), if Sum2 + H > Sum1 -> {{Sum2 + H, [H | Path2]}, {Sum1, Path1}}; true -> {{Sum1, Path1}, {Sum1, Path1}} end. Note that the look function now returns two pairs: the first one is the solution for all the previous values and the second one is the solution for all the previous values except the most recent one. If you use this algorithm, then the optimization of splitting the problem space based on negative values becomes unnecessary. Splitting the problem space on a linear algorithm should yield no significant benefit, but it's very significant if you have an exponential algorithm. -Andrew
Andrew, are you sure your program is not O(n^2)? I must admit that I don't know haskell, so this is a genuine question.
It seems to me that either [H | Path2] or {{Sum1, Path1}, {Sum1, Path1}} would require copying a list of length O(n). Or is Haskell smart enough to create a tree in this case? I put up a C version at http://www.daimi.au.dk/~sandmann/gambler.c
And here is a non-recursive version:
http://www.daimi.au.dk/~sandmann/gambler3.c
this particular code is erlang, not haskell
lists are implemented as linked lists so appending the existing path to the single element H with [H|Path2] is a constant time operation the construction of the sum/path tuples is also a constant time operation as well as there is no copy made of the lists.
I was curious and ran some timings on the above solution
10 elements = 3 usec 100 elements = 20 usec 1000 elements = 205 usec 10000 elements = 3563 usec 100000 elements = 22789 usec 1000000 elements = 204604 usec 10000000 elements = 3191128 usec
The problem with this version is that it still needs O(N) time to run! Here's a version that runs in O(1) time. Admittedly, it still compiles in O(N) time
 #include <iostream> template<int Day> struct DailyWinnings { enum { value = 0 }; }; template<> struct DailyWinnings<0> { enum { value = 158 }; }; template<> struct DailyWinnings<1> { enum { value = 44 }; }; template<> struct DailyWinnings<2> { enum { value = 196 }; }; template<> struct DailyWinnings<3> { enum { value = 399 }; }; template<> struct DailyWinnings<4> { enum { value = 47 }; }; template<> struct DailyWinnings<5> { enum { value = 2 }; }; template<> struct DailyWinnings<6> { enum { value = -158 }; }; template<> struct DailyWinnings<7> { enum { value = -197 }; }; template<> struct DailyWinnings<8> { enum { value = 375 }; }; template<> struct DailyWinnings<9> { enum { value = 121 }; }; template<> struct DailyWinnings<10> { enum { value = 806 }; }; template<> struct DailyWinnings<11> { enum { value = 44 }; }; template<> struct DailyWinnings<12> { enum { value = 953 }; }; template<> struct DailyWinnings<13> { enum { value = 7 }; }; template<> struct DailyWinnings<14> { enum { value = 20 }; }; template<> struct DailyWinnings<15> { enum { value = 1 }; }; template<> struct DailyWinnings<16> { enum { value = 7 }; }; template<> struct DailyWinnings<17> { enum { value = 88 }; }; template<> struct DailyWinnings<18> { enum { value = 191 }; }; template<> struct DailyWinnings<19> { enum { value = 33 }; }; template<> struct DailyWinnings<20> { enum { value = 654 }; }; template<> struct DailyWinnings<21> { enum { value = 156 }; }; template<> struct DailyWinnings<22> { enum { value = 321 }; }; template<> struct DailyWinnings<23> { enum { value = 784 }; }; template<> struct DailyWinnings<24> { enum { value = -111 }; }; template<> struct DailyWinnings<25> { enum { value = 159 }; }; template<> struct DailyWinnings<26> { enum { value = 88 }; }; template<> struct DailyWinnings<27> { enum { value = 49 }; }; template<> struct DailyWinnings<28> { enum { value = 25 }; }; template<> struct DailyWinnings<29> { enum { value = 366 }; }; template<> struct DailyWinnings<30> { enum { value = 861 }; }; template<> struct DailyWinnings<31> { enum { value = 869 }; }; template<> struct DailyWinnings<32> { enum { value = 380 }; }; template<int A, int B> struct Max { enum { value = A > B ? A : B }; }; template<int A> struct BestResult { enum { value = Max< DailyWinnings<A>::value + BestResult<A + 2>::value, BestResult<A + 1>::value >::value }; }; template<> struct BestResult<33> { enum { value = 0 }; }; template<> struct BestResult<34> { enum { value = 0 }; }; int main() { std::cout << BestResult<0>::value << "\n"; }
Howdy. I'm the "author" of said problem. I'm not very good at reading code in popular programming languages, so I can't tell whether any of the above programs are O(N) --in terms of access to the array, Aaron!-- .
However, there is an O(N) solution, in fact, quite a short and elegant one. Just something to keep in mind. Mine uses three program variables and a simple "do" loop wherein each variable is updated once. Each element of the array is accessed precisely once. +j
Well, there is the simple, optimal solution (easy to modify to print the optimal path):
int linear( int start, int length ) { int with = 0; int without = 0; for( int i=0; i without ) without = with; if( tmp > with ) with = tmp; } return max( with, without ); } but that is so boring. Doing unbalanced recursion is just silly, here is a balanced recursive solution: int rec1( int start, int length, int &count ) { count++; if( length == 1 ) { return data[start]; } else if( length == 2 ) { return max( data[start], data[start+1] ); } else if( length == 3 ) { int result1 = data[start] + data[start+2]; int result2 = rec1( start, 2, count ); return max( result1, result2 ); } else { int mid = length/2; int result1 = rec1( start, mid, count ) + rec1( start+mid+1, length-mid-1, count ); int result2 = rec1( start, mid-1, count ) + rec1( start+mid, length-mid, count ); return max( result1, result2 ); } } The unbalanced takes 7049155 steps, the balanced 213 steps(can be reduced to 108 with dynamic programming), the linear 33.
ok, that is just annoying, the comment section deletes lines.
so, lets try again: int linear( int start, int length ) { int with = 0; int without = 0; for( int i=0; length>i; i++ ) { int tmp = without + data[i]; if( with > without ) without = with; if( tmp > with ) with = tmp; } return max( with, without ); } To other submitters: watch out for the use of less than. There may also be problems in the recursive solution, but I am too lazy to look through it...
In Haskell:
gamble = [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380] type Seq = (Integer, [Integer]) total = fst append :: Seq -> Integer -> Seq append (a,bs) c = (a+c, bs ++ [c]) helper :: Seq -> Seq -> [Integer] -> Seq helper a b [] = a helper a b (x:xs) = if total b + x > total a then helper (append b x) a xs else helper a a xs solve :: [Integer] -> Seq solve = helper (0,[]) (0,[]) main = print (solve gamble)
I should give credit to Andrew's erlang solution here, too. I had come up with the basic iteration (recursing on "helper (b ++ [x]) a xs" and "helper a a xs") independently, but my original version was much uglier with more sum computations (which probably made it O(n^2) instead of O(n)) until I got the idea from Andrew's post to couple the total with the sequence in a custom data type.
I don't think anyone has posted an ocaml solution yet, but here's a tail-recursive version that definitely runs in linear time and it's short and sweet. (With due credit to Soren.)
let gambler_max l = let rec gambler_max_aux l max_list max_total max_not_last_list max_not_last_total = match l with h::t -> if max_not_last_total + h > max_total then gambler_max_aux t (h::max_not_last_list) (max_not_last_total+h) max_list max_total else gambler_max_aux t max_list max_total max_list max_total | [] -> max_list in gambler_max_aux l [] 0 [] 0;;
Ok, I was very good and didn't look at any replies till I had a go myself.
I seem to have come up with a solution which is similar in some ways to what's above in that it splits the problem into sub-problems and then maximises the takings for each sub-set of consequtive days and concatentates all the days to get a total. My solution gets a bit dirty within each sub-set of consequtive days though, it builds a table of all possible permutations of gambling and not gambling for all days (a truth table effectively) and then goes through each potential solution breaking out as soon as two consequitve ones are met. It is optimised a little in that it totals each permutation while checking it. I'm rather heartened that I get the same answer as everyone else: bartmac:~/Documents/temp bart$ time ./dez.pl The maximum ammount is 5798 which can be obtained by gambling on the following days: 0, 3, 5, 8, 10, 12, 14, 16, 18, 20, 23, 25, 27, 30, 32 real 0m4.200s user 0m3.263s sys 0m0.121s bartmac:~/Documents/temp bart$ Also, as you can see, it runs in descent time on my old G4 MacMini so it can't be horribly inefficient. It should also scale well because it's complexity is mainly determined by the maximum number of straight days that the gambler makes a profit and that is not likely to get longer regardless of how long you gamble. Anyhow, here's my Perl solution, complete with comments (also emailed to Dez in case the code gets chewed up with smilies and the like!): #!/usr/bin/perl use strict; our @data = (158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380); our @daysToGamble; our $winnings = 0; our $startConseq = -1; my $i = 0; while($i0){ #if we haven't start a sequence of consequtive winning days start one unless($startConseq>=0){ $startConseq = $i; } #if we've hit the end of the array process what ever sequence we have if($i == (scalar(@data)-1)){ &processWinningSequence($startConseq, $i); } }else{ # if we were in the middle of a sequence we've just found the end, process the sequence if($startConseq>=0){ &processWinningSequence($startConseq, $i-1); } # make sure we end any sequence that may have been started $startConseq = -1; } $i++; } print "\nThe maximum ammount is $winnings which can be obtained by gambling on the following days: ".join(", ", @daysToGamble)."\n\n"; #function to deal with sequence of winning days sub processWinningSequence{ my $start = shift; my $end = shift; #if the sequence is of lenght 1 we are good to gamble! if($start == $end){ &doGamble($start); return; } #if not then get the maximum possible for the set # I just figured out why this is so bloody hard .... thanks Des! #generate all possibe permutations of gambling and not gambling my $numVariables = $end-$start+1; my $numPermutations = 2**$numVariables; my @permutations; my $i=1; for(my $x=$numVariables-1;$x>=0;$x--){ my $c=0; my $cc=0; for(my $y=0;$y
Here is my (solution?) in javascript:
function max(x,y) { return (x > y ? x : y); } var winnings = [158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380]; //create a buffer var total = [0,0,0]; for (var i=0; i < winnings.length; i++) { total.push( max(winnings[i],0) + max(total[i],total[i+1])); } var length = total.length; var maxWinning = max(total[length-1],total[length-2]);
Solution in Java.
This isn't the most elegant of solutions. I decided to make my decision on whether to bet today by looking at the next 6 days. Although with this sample data 4 days is enough. int[] winnings = { 158, 44, 196, 399, 47, 2, -158, -197, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, -111, 159, 88, 49, 25, 366, 861, 869, 380 }; int total = 0; boolean skip = false; winnings:for (int i = 0; i < winnings.length; i++) { if (skip || winnings[i] < 1) { skip = false; continue; } int largestFirst = 0; int[] next6 = new int[6]; int[] first = new int[8]; int[] second = new int[5]; for (int j = i, k = 0; j < winnings.length && k < next6.length; j++, k++) { next6[k] = winnings[j]; } first[0] = next6[0]; first[1] = next6[0] + next6[2]; first[2] = next6[0] + next6[3]; first[3] = next6[0] + next6[4]; first[4] = next6[0] + next6[5]; first[5] = next6[0] + next6[2] + next6[4]; first[6] = next6[0] + next6[2] + next6[5]; first[7] = next6[0] + next6[3] + next6[5]; second[0] = next6[1]; second[1] = next6[1] + next6[3]; second[2] = next6[1] + next6[4]; second[3] = next6[1] + next6[5]; second[4] = next6[1] + next6[3] + next6[5]; for (int j = 0; j < first.length; j++) { int f = first[j]; if (f > largestFirst) { largestFirst = f; } } for (int k = 0; k < second.length; k++) { if (largestFirst < second[k]) { continue winnings; } } total += next6[0]; skip = true; } System.out.println("Total " + total);
Short but hard to find
 Result is $5798 too.C# 2.0 public static void Try( int[] input, Label output ) { int length = input.Length; int sumC, sumP = 0, sumPP = 0, sumPPP=0; for( int i = 0; i < length; i++ ) { sumC = ( sumPP > sumPPP ? sumPP : sumPPP ) + input[i]; sumPPP = sumPP; sumPP = sumP; sumP = sumC; } int result = sumP > sumPP ? sumP : sumPP; output.Text = string.Format( "${0}", result ); }
Hi, I love your solution to this problem. I am a newbie to programming. Can you explain the logic behind your solution and how it works? I would be so grateful!
Solution in Ruby:
[158, 399, 2, 375, 806, 953, 20, 7, 191, 654, 784, 159, 49, 861, 380] total: 5798 --CODE-- days = [158, 44, 196, 399, 47, 2, 0, 0, 375, 121, 806, 44, 953, 7, 20, 1, 7, 88, 191, 33, 654, 156, 321, 784, 0, 159, 88, 49, 25, 366, 861, 869, 380] total = 0 soln = Array.new while (days.length > 0) do a = days[0] unless days[0].nil? b = days[1] unless days[1].nil? c = days[2] unless days[2].nil? d = days[3] unless days[3].nil? if a + c > b + d || a + d > b + d then soln < < a 2.times {days.shift} else soln < < b 3.times {days.shift} end total += soln.last end p soln p 'total: ' + total.to_s |
About:Switch to Dark on Light!
This website is the online diary of me, Des Traynor, a User Experience Researcher in Dublin, Ireland. I work with Contrast. I usually write on 5 topics: I update about 3-4 times per month. Be sure to subscribe so you don't miss this good stuff. If this is your first time here, check out the archives.My official homepage provides more information about who I am, and what I research. You can contact me at destraynor [at] gmail [dot] com Quicksearch |
{document.getElementById(%22switcher%22).style.display=%22none%22;document.body.style.background=%22#fcfcfc%22;document.body.style.color=%22#333%22;document.getElementById(%22blogbanner%22).src=%22http://www.destraynor.com/serendipity/templates/destraynor/header-alt.png%22;function%20changeSizeColor(tag,size,%20color){var%20elements%20=%20document.getElementsByTagName(tag);for%20(var%20i=0;i<elements.length;i++){elements[i].style.fontSize=size;elements[i].style.color=color;}}var%20all%20=%20document.getElementsByTagName(%22*%22);for(var%20i=0;i<all.length;i++){all[i].style.background%20=%20%22white%22;all[i].style.color%20=%20%22#444%22;}changeSizeColor(%22h1%22,%2232px%22,%22#333%22);changeSizeColor(%22h2%22,%2222px%22,%22#222%22);changeSizeColor(%22h3%22,%2220px%22,%22#111%22);changeSizeColor(%22p%22,%2216px%22,%22#444%22);changeSizeColor(%22a%22,%22%22,%22#cc0000%22);var%20paragraphs%20=%20document.getElementsByTagName(%22p%22);for(var%20i=0;i<paragraphs.length;i++){paragraphs[i].style.lineHeight=%22150%%22;paragraphs[i].style.fontFamily=%22Arial,Helvetica,Verdana,sans-serif%22;}})()){kind=link}
Thanks again to everyone who submitted solutions to the second gambling puzzle. I am impressed at the amount of solutions I get to these problems, and also the variety of languages used. I promise I will fix the comment box for the next programming puzzle
Tracked: Nov 12, 17:22
Time for another programming puzzle, this was given to a friend in an interview for a mobile phone operator. Apparently it maps neatly on to some problem that must regularly be solved in mobile phone networks, but seeing as said friend didn't get the job,
Tracked: Dec 05, 20:52