Friday, October 13. 2006Steve the Gambler, A Programming Puzzle
I was shown a very interesting programming puzzle yesterday, and I figured I'd share it with you guys. It was apparently used in a technical interview recently, so it is probably worth having a stab at it.
The storyYour friend Steve is a psychic gambler. He can predict the profit or loss of each day of his gambling a whole month in advance. He's losing money however, as he can't only play on the days he is winning(The casino won't let him). He has to pick one set of consecutive days each month that he plays. He comes to you for help, because he can't work out what is the best time to start, best time to stop, or even how much money he can make. Here are Steves predictions of the next months takings. 
The actual figures are 44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1. To declare them in Java, its Okay, so the question is what is the most money Steve could make in any consecutive stint of gambling for this month, and for bonus marks, what day should he start and end gambling? Can you write a program to determine this for any given array of numbers? What do you think the complexity of solving this problem is? Have a go at it, I'll post the solution on Monday, or if earlier if the debate gets out of hand. Enjoy. Update: if it is not profitable at all for Steve to go gambling (i.e. if every day he loses money), then zero is an acceptable answer. No, there is no magic trick to this, it's just a programming question Update 2: You can read the solutions and, and 2 more puzzles in the programming section of the blog Comments
Display comments as
(Linear | Threaded)
I haven't got the code written, but I think it's possible to do this in order N squared, I think.
Damn you, I was enjoying relaxing on my Friday evening!
Another one for N squared. Two 1 to N loops. Feels like there is a more clever solution tho.
I can't even work out how you'd do it in NSquared, you need to get the max of the total of every possible sub array in N.
Dammit, I need more coffee.
Actually I think there is a way to do it in O(n), using O(n) memory to store intermediate results. But I will have to take a second look at my algorithm later, I'm too hungry and tired now...
I'm done:
Weapon of choice: Java 6 variables. 1 If statement. 2 For loops (nested). 1 Array. All in main method.
This is a classic dynamic programming problem, solvable in O(n).
running total in one var
min & max one var each max - min = most money O(N) i.e. just find largest delta in running total
+ min must precede max
forgot that, or largest LOSS (- delta) can be found adds 1 var
This is a quick pass done in C# 2.0 in a "Compute" button event with rudimentary gold-pla... uh... rationality checking (hey, I was intrigued...):
if (!string.IsNullOrEmpty(numbersTextBox.Text)) { string[] split = numbersTextBox.Text.Split(new char[] { ',' }); List < double > numbers = new List < double > (); double tempDouble = 0; foreach (string tempString in split) { if (double.TryParse(tempString, out tempDouble)) { numbers.Add(tempDouble); } } if (numbers.Count > 0) { double bestSum = 0, sum; int bestStart = 0, bestStop = 0, start, stop; for (start = 0; start < numbers.Count; start++) { sum = 0; for (stop = start; stop < numbers.Count; stop++) { sum += numbers[stop]; if (sum > bestSum) { bestStart = start; bestStop = stop; bestSum = sum; } } } resultsLabel.Text = string.Format("The best sum was achieved by beginning at position {0} (value {1}) and continuing to position {2} (value {3}) for a sum of {4}.", bestStart + 1, numbers[bestStart], bestStop + 1, numbers[bestStop], bestSum); } }
It's more than classic - the similar problem (and an O(n) solution) can be found in the Programming Pearls book. A function to get just the maximal sum of the array span looks like this:
maxseq = maxseq2 0 0 where maxseq2 s _ [] = s maxseq2 s t (x:xs) = maxseq2 s2 t2 xs where t2 = max 0 (t + x) s2 = max s t2
the pearls algo:
maxsofar = 0 maxendinghere = 0 for i = [0,n) maxendinghere = max(maxendinghere + x[i], 0) maxsofar = max(maxsofar, maxendinghere) O(N)
maybe i'm reading it wrong, but the pearls algorithm seems to assume that he starts gambling on the first day of the month.
doesn't the problem state that the "biggest payoff" could be any consecutive day range within the month?
It takes rather more code in Ada. It looked prettier before I posted it. Of course it could be all wrong; results are max=383, start=19. And I think it's n-squared.
with Ada.Text_IO; use Ada.Text_IO; procedure Psychic is type Data is array (Positive range ) of Integer; procedure Largest_Run (D : Data; Maximum : out Integer; Starting_At : out Positive) is Sums : array (D'Range) of Data (D'Range) := (others => (others => 0)); To_Add : Data := D; begin Maximum := Integer'First; Sums (Sums'First) := D; for R in Sums'First + 1 .. Sums'Last loop To_Add := To_Add (To_Add'First + 1 .. To_Add'Last) & 0; for C in D'Range loop Sums (R)(C) := Sums (R - 1)(C) + To_Add (C); if Sums (R)(C) > Maximum then Maximum := Sums (R)(C); Starting_At := C; end if; end loop; end loop; end Largest_Run; D : constant Data := (44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1); Maximum : Integer; Starting_At : Positive; begin Largest_Run (D, Maximum, Starting_At); Put_Line ("maximum return is " & Integer'Image (Maximum) & " starting at index" & Positive'Image (Starting_At)); end Psychic;
missed another corner case - a min after the max may presage a +delta greater than the prior +delta, but which does not reach a new max -- can be simply handled by reseting min and max
t = x = n = z = 0 for (i = 1 .. |a|) { t += a[i] if (t < z) z = t if (t - z > x - n) {x = t, n = z} if (t > x) {x = t, n = z} } max +delta = x - n -- could be 0 or -neg (if stable or monotically decreasing) getting the dates is just saving the index of min & max
For all the cats who think it's just a "single sweep, running sum, find the min and max and you're done", try this input data instead:
[432, 90, -57, -276, -349, -262, -365, 154, 244, -4, -443, -426, 457, -187, -8, 80, 222, 180, 428, -440, -420, -50, 204, -375, 94, 241, -476, 14, 45, -395]
since my pseudocode compiler is in the shop, I converted to C/C++:
#include int main(int argc, char **argv) { int a[30] = {432, 90, -57, -276, -349, -262, -365, 154, 244, -4, -443, -426, 457, -187, -8, 80, 222, 180, 428, -440, -420, -50, 204, -375, 94, 241, -476, 14, 45, -395}; int t, x, n, z; t = x = n = z = 0; for (int i = 0; i < 30; i++) { t += a[i]; printf("%d ", t); if (t < z) z = t; if (t - z > x - n) {x = t; n = z;} if (t > x) {x = t; n = z;} } printf("%d", x - n); for (;;); } OUTPUT 432 522 465 189 -160 -422 -787 -633 -389 -393 -836 -1262 -805 -992 -1000 -920 -6 98 -518 -90 -530 -950 -1000 -796 -1171 -1077 -836 -1312 -1298 -1253 -1648 1172 1172 is the correct answer (by cursory inspection) -- and my original answer (#8,#9) did fu on this, but the corrected sol'n (#14) fixed
My solution, in common-lisp:
(defun max-set (numbers result-function combiner-function test-function) __(do* __( (number numbers (cdr number)) ____(result (apply result-function (list number)) (apply result-function (list number))) ____(current result (apply combiner-function `(,current ,result))) ____(max current (if (apply test-function `(,current ,max)) current max))) __((endp (cdr number)) max))) (max-set __`(432 90 -57 -276 -349 -262 -365 154 244 -4 -443 -426 457 -187 -8 80 222 180 428 -440 -420 -50 204 -375 94 241 -476 14 45 -395) __#'(lambda (numbers) (max-set numbers #'car #'+ #'>)) __#'(lambda (&rest numbers) (cadr numbers) __#'>) This returns 1172, which is the correct answer. The underscores are added to fit the indentation. While this solution is not the fastest, it is vert general. To find the lowest possible set, change to #'> to a #'
Excellent work everyone,
I'll re-format your code and post it with the solution on Monday. Des
can we get the optimum answer? cuz, from whatever is posted here, i get the feeling that the it is assumed that the person gambles all throughout the month...
i did this one, and for the original problem statement, i got the answer as 383 for the days 19 to 28... as for the modified values given by someone in the comments the answers are as follows, 1172 for days 13 to 19... i am not posting my code, as i didnt write it keeping efficiency or any such parameters in mind. i was just trying to practise my programming...
Check out the follow up post, this post is part of a series called programming puzzles, you can view the rest in the archives (link in the side bar)
A very stupid Haskell version:
maxseq xs = foldr1 max (map ((foldr1 max) . (map sum) . (scanr (:) []) . reverse) (scanr (:) [] xs)) (I think this one could be done very concisely in J) Sergiy Matusevych, your implementation is very nice. It can also be done with a fold: maxseq2 = fst . (foldr h (0,0)) where --h x (s,t) = ((max s t2), t2) where ----t2 = max 0 (x + t) But this is less readable of course.
// any prefix string adding to 0 or less
// 0 can be discarded... O(n). int data[30] = {44, -78, -3, 32, 7 ,2, -9, 33, 9, 183 ,-350, -34, 44, 75, ,17 ,22, 19, -190, 120, ,19 ,7, 3, 29, 8, 65 ,42, 2, 88, -119, 1 }; int main () { copy (data, data + 30, ostream_iterator < int >(cout, "\t")); cout
Common Lisp solution for max earnings (adding which days is trivial, but another ugly line). Underscores added for clarity.
(defun max-subsequence (numbers) _ (setq m 0) _ (setq p 0) _ (dolist (element numbers m) __ (setq p (max 0 (+ p element))) __ (setq m (max m p))))
pearls algo works as advertised:
#include "stdlib.h" #define MAX(a,b) (a >= b ? a : b) main() { int x[30] = {44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1}; int maxsofar = 0; int maxendinghere = 0; int i; for (i = 0; i < 30; i++) { maxendinghere = MAX(maxendinghere + x[i], 0); maxsofar = MAX(maxsofar, maxendinghere); } printf("%d\n", maxsofar); } the result is 383.
Here's another Haskell solution:
forecast = [44,...] cumulative = scanl (+) 0 forecast cumulativeMin = scanl1 min cumulative differences = zipWith (-) cumulative cumulativeMin best = maximum differences main = print best
points-free O(n) Haskell version:
gamble = foldr max 0 . scanl (curry $ max 0 . uncurry (+)) 0
#include
using namespace std; int main() { const int sales[] = {44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1 }; /*const int sales[] = {432, 90, -57, -276, -349, -262, -365, 154, 244, -4, -443, -426, 457, -187, -8, 80, 222, 180, 428, -440, -420, -50, 204, -375, 94, 241, -476, 14, 45, -395 };*/ int max = 0; int start = 0; for (int i = 0; i < 30; i++) { int currVal = 0; for (int y = i; y < 30; y++) { currVal += sales[y]; if (currVal > max) { max = currVal; start = y; cout
Here is my solution in PHP as my knowledge of java is lacking. I'm pretty sure this is the right answer.
void maxFive( int []arr, out int maxValue, out int maxIndex )
{ int tmp; int max; int maxIdx = -1; for ( int i = 0; i < arr.length - 5; i++ ) { if ( i > 4 ) { tmp -= arr[i-5]; } tmp += arr[i]; if ( tmp > max ) { max = tmp; maxIdx = i - 4; } } maxValue = max; maxIndex = maxIdx; } in D. O(N), using trivial amounts of outside memory.
VBA:
Function gamble() Dim x, curSet, curSum, topSum As Integer Dim dataset As Variant dataset = Array(44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1) For topSet = LBound(dataset) To UBound(dataset) parse: For x = curSet To topSet curSum = curSum + dataset(x) Next x If curSum > topSum Then topSum = curSum answer = "The best time to gamble is from day " & curSet + 1 & " (" & dataset(curSet) & ") to day " & topSet + 1 & " (" & dataset(topSet) & ") where your buddy will make $" & topSum End If curSum = 0 If curSet < topSet Then curSet = curSet + 1 GoTo parse Else curSet = 0 End If Next topSet MsgBox (answer) End Function
A 5 minute VB6 way of doing it:
sDays = Split("44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1", ",") For I = 0 To 29 _ For z = I To 29 ____ tmpSum = 0 ____ For x = I To z: tmpSum = tmpSum + CLng(sDays(x)): Next ____ If tmpSum > BestSum Then _______ BestSum = tmpSum _______ BestStart = I _______ BestEnd = z ____ End If _ Next Next MsgBox "Best days are " & BestStart + 1 & " to " & BestEnd + 1 & " = $" & BestSum
Puzzle is OK and entertaining. But, why would anybody want to use it in a technical interview? This is a very simple problem that requires below average IQ to solve it, so almost anybody can qualify. The typical workplace problem is at least 100 times more complex and takes 100 times longer to come up with a solution. This is as if you are buying a car and testing if it can run 3 miles per hour without stopping for 5 minutes. Who does need this type of test? I feel sorry for hiring managers who use this type of testing to determine who to hire. Obviously their IQ is below average, and if you are a smart person and looking for a smart job you do not want to work with these people.
Flattner, I presume you have heard about the FizzBuzz challenge then, no?
http://www.codinghorror.com/blog/archives/000781.html FizzBuzz - Why can't programmers program?
If this is an interveiw question, I think the employer would be more interested in the optimization of performance. Wouldn't we get more performance by first removing trivial elements from original data set, and then processing the smaller data set? (IE remove winnings/losses
Personally, I'd be looking to see if the candidate asked question(s) needed to fully understand the problem before starting to code.
1. When you say that he has to pick one set of days for each month, do you mean that an acceptable answer must contain at least two gambling days? 2. When you say that the casinos won't let him play only on days when he will win, do you mean that there must be at least one day of losses in an acceptable answer? If yes to question 2: 3. Must that day of losses be at any particular point in the sequence (i.e. the last day)? Coding is never as hard as understanding what the user really wants. I care that someone can create the code, I care more that that person will find out what is really required before coding. As a coder, I would fail the Systems Analyst that made the specification for this coding problem for being un-clear.
In an interview, I'd be happy with a candidate whose first solution was n-squared -- because, as the problem states, your psychic gambling friend can only see 30 days into the future. "That doesn't scale" isn't always a deal-breaker, because some problems are just one-offs.
Now, I'd be reluctant to continue interviewing someone who couldn't tell me what the complexity of their approach was, but coming up with a readable solution in 3 minutes (and knowing it was n-squared) could make for a better interview than taking 15 minutes on the linear version (and possibly missing an edge case or two). Giving a preliminary answer first, even if it's non-optimal, gives more of an opportunity for interaction. An n^2 solution in Ruby (which tells Steve which days to start and stop): def max_takings(predictions) __ max_takings, begin_date, end_date = 0, nil, nil __ 0.upto(predictions.length - 1) do |i| __ i.upto(predictions.length - 1) do |j| ____ takings = predictions[i..j].inject(0) { |mem, var| mem + var } ____ max_takings, begin_date, end_date = takings, i + 1, j + 1 if takings > max_takings __ end __ end __ puts "Max possible take is #{max_takings}, starting on day #{begin_date} and ending on day #{end_date}" end
The optimal solution requires O(n) time, and constant storage. Think back to data structures and algorithms!
Not memory efficient but was funner to write and showcases C++ more (how come no one wants to showcase C++ anymore?)
#include #include using namespace std; int monthsTakings[] = { 44, -78, -3, 32, 7, 2, -9, 33, 9, 183, -350, -34, 44, 75, 17, 22, 19, -190, 120, 19, 7, 3, 29, 8, 65, 42, 2, 88, -119, 1 }; int main() { const int count = sizeof(monthsTakings) / sizeof(monthsTakings[0]); int res[count count] = { 0 }; for(int days = 0; days < count; days++) for(int i = 0; i < count - days; i++) res[days count + i] = accumulate(monthsTakings + i, monthsTakings + days + i, 0); int i = max_element(res, res + (count count)); cout
This problem is relatively easy: the derivation of it you can find in this book: Programming: The Derivation of Algorithms.
A more fun to read (less math) description of it is in programming pearls. (also posted above). neat litle problem 
|
About:
My name is Des, I'm the UX Lead and COO of Intercom, a fantastic CRM & messaging tool for web sites and web software. Keep in touch
 |
This is a follow up to the previous programming puzzle Steve the Gambler. I was pretty impressed iwth the response the post got, and the code submissions. I even got an email from someone who will remain anonymous saying "It's pretty mean to post exponen
Tracked: Oct 16, 11:51
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 t
Tracked: Nov 04, 14:48