Steve the Gambler - Caught by the IRS

destraynor

Tuesday, December 5. 2006

Steve the Gambler - Caught by the IRS

Programming

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, I have no more information. Read on, just in case you end up in such an interview :-)

The story

Steve has been caught by the I.R.S (aka Revenue Collectors etc). They know Steve gambled on at 9 days in the last month, yet he declared a profit/loss of $0. Luckily for Steve they don't know what 9 days he gambled on, so all he has to do is find receipts for any 9 days in the last month that total to $0.

If he can’t find a suitable 9 days, he has to get as close to zero as possible to ensure a minimal fine. Time is a serious factor here, the quicker Steve works this out, the better.

The no-nonsense programming requirement

You are given an array of 31 integers. You must write a method that will do the following...

  • Find any 9 entries in the array whose total is 0.
  • When 0 is not available, it should be as close as possible.

Bonus marks if your method generalises for any number of days :-) Here is some data to work with. There is a 9 day $0 solution to this dataset.

int monthsTakings[] = {-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101, 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8,}
Update:
  • The best way to submit your code without losing formatting is to email me.
  • If you're posting code in the comments encode your spaces to preserve them
  • So far I've received working solutions in Python, OCaml, Erland, $yourLanguageHere!.
Previous Puzzles

Update: Comments are currently broken, at least the spam filter is, so the best way to contact me re: Steve the Gambler is via email, address in the side bar
Posted by Des Traynor in Programming at 20:11 | Comments (19) | Trackbacks (0)

Trackbacks
Trackback specific URI for this entry

No Trackbacks

Comments
Display comments as (Linear | Threaded)

I wrote a fairly naive algorithm in ocaml which you can see at

http://rafb.net/paste/results/itG6Ak89.html

The basic idea is just to recursively go through the list and for each element, consider solving the problem with/without that element in the solution. Despite the naivety of this solution, finding the answer for 9 days takes between 1 and 2 seconds after compiling with the ocaml optimizing compiler.

C:\temp>camlprog -days 9
List is: 87 -40 -65 54 -45 -12 -12 25 8
Sum is: 0

An interesting thing to note is that there is a perfect solution (totaling 0) for any number of days from 3 to 28. Only 1, 2, 29, and 30 don't have perfect solutions.

C:\temp>camlprog -days 3
List is: -45 38 7
Sum is: 0

...

C:\temp>camlprog -days 28
List is: -50 -21 13 171 14 -58 109 4 -23 -44 -98 -121 101 33 87 -121 -40 -65 43 54 -45 -12 -12 38 25 3 7 8
Sum is: 0
#1 Andrew on 2006-12-05 22:41 (Reply)
Wouldn't any solution less than zero (a net loss gambling) result in no fine for Steve? Thus -20 dollars would be better than +5 dollars?
#2 Outsourced on 2006-12-06 00:13 (Reply)
Lets imagine that the IRS fine you based on how incorrect your taxes were, in either direction, okay :-)
#2.1 Des Traynor (Homepage) on 2006-12-06 07:39 (Reply)
Used Erlang, found several solutions that worked. Here's one:
[-12,-12,-23,-50,54,25,3,7,8]
#3 James on 2006-12-06 02:31 (Reply)
here's an erlang solution that runs in around 120 microseconds on my powerbook

http://rafb.net/paste/results/PAoNnd38.html

I basically took andrews solution and speed it up by some orders of magnitude by removing the without path when it wasn't necessary to run
#4 Jason on 2006-12-06 03:51 (Reply)
Since the url above will expire in 24 hours I figured I better just paste it here...

-module(irs).
-compile(export_all).

data() ->
    [-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101, 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8].

go() ->
     find(9, data(), 0).

find(N, L, _) when N == 0;L == [] -> [];
find(N, L, _) when length(L) == N -> L;
find(N, [H|T], S) ->
    With = [H | find(N-1, T, S - H)],
    case lists:sum(With) of
        S ->
            With;
        WS ->
            Without = find(N, T, S),
            case abs(WS - S) < abs(lists:sum(Without) - S) of
                true -> With;
                _ -> Without
            end
    end.
#5 Jason on 2006-12-06 04:08 (Reply)
Cheap, cheap hack that nevertheless found the solution in under two minutes. Should not scale well, though.

--
module IRS where
import Random
import Control.Monad
import Data.List

select [] x = []
select (l:ls) x = (x !! l) : (select ls x)
sumSelect l x = sum (select l x)
getList n = [getStdRandom (randomR (1,9)) >>= return | x>=(putStr . (++" ") . (" "++) . show )) (getList n)


main = do { x
#6 Diego (Homepage) on 2006-12-06 08:11 (Reply)
Argh! HTML escaping gone awry!
#7 Outsourced on 2006-12-07 02:40 (Reply)
Bendick, your solution still has the problem that it goes down paths that are not needed...

take this version for example, it runs in 68k of memory rather than 25mb and is 3 orders of magnitude faster even without the memoization

(define (steve days off-by l)
(if (zero? days)
(list off-by)
(if (null? l)
#f
(let ((first-try (steve (- days 1) (+ off-by (car l)) (cdr l))))
(if (and first-try (= 0 (car first-try)))
(cons (car first-try) (cons (car l) (cdr first-try)))
(let ((second-try (steve days off-by (cdr l))))
(if (not first-try)
second-try
(let ((first-fixed (cons (car first-try)
(cons (car l)
(cdr first-try)))))
(if (or (not second-try)
(< (abs (car first-try)) (abs (car second-try))))
first-fixed
second-try)))))))))

(define (answer days list-of-days)
(cdr (steve days 0 list-of-days)))

(time (answer 9 '(-50 -21 13 171 14 -42 -58 109 4 7 -23 -44 -98 -121 101 33 87 -121 -40 -65 43 54 -45 -12 -12 38 25 3 7 8 )))
3 ms real time
2 ms cpu time (2 user, 0 system)
no collections
68224 bytes allocated
no minor faults
no major faults
#8 Jason on 2006-12-07 02:56 (Reply)
Hi Jason. I thought about checking to see if the first try was exactly correct and only try the second otherwise, but it doesn't change the asymptotic runtime.

Furthermore, without the memoization, your code is exponetial. Try running it on a dataset that doesn't have any solution exactly equal to zero. Try the example dataset with just positive values.

(time (answer 9 (map abs '(-50 -21 13 171 14 -42 -58 109 4 7 -23 -44 -98 -121 101 33 87 -121 -40 -65 43 54 -45 -12 -12 38 25 3 7 8-))))

Let me know if it ever returns. =]
#8.1 |/|/ Bendick (Homepage) on 2006-12-07 03:35 (Reply)
Des, you've gotta nix the mandatory smileys on comments. =]
#8.1.1 |/|/ Bendick (Homepage) on 2006-12-07 03:39 (Reply)
The erlang solution runs in around 8 seconds with an all positive data set which while slower isn't all that bad.

I'd never done scheme before yesterday so I'm not sure why the other version is so much slower in the worst case

I'd ask if you'd prefer a solution that took 2ms for the cases where there is a solution and 8sec when there is not one or 2 seconds for all of them but I suppose you could mix and match and have both worlds.
#8.1.2 Jason on 2006-12-07 12:48 (Reply)
My Java solution is admittedly rather low-level, even for Java (would look almost the same in C), but with the example data, it takes just 66ms - for 10000 iterations. The worst case is at 500ms for 1 iteration. Six orders of magnitude difference!

public class SteveTheGambler {
final int[] monthsTakings = {-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101, 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8,};
final int n=9;

int bestSum = Integer.MAX_VALUE;
int[] bestSelection = new int[n];

public void compute() {
select(new int[n], 0,0,0);
}

private void select(int[] selection, int i, int sum, int nSelected) {
if(nSelected == n) {
if(Math.abs(sum) < Math.abs(bestSum)) {
bestSum = sum;
System.arraycopy(selection, 0, bestSelection, 0, n);
}
return;
}
for( ; i
#8.1.2.1 axel (Homepage) on 2006-12-07 16:25 (Reply)
and here's the second half... (HTML formatting!)

for( ; i &lt;= monthsTakings.length-(n-nSelected); ++i) {
int elt = monthsTakings[i];
selection[nSelected] = elt;
select(selection, i+1, sum+elt, nSelected+1);
if(bestSum == 0)
return;
};
}
}
#8.1.2.1.1 axel (Homepage) on 2006-12-07 16:29 (Reply)
Just for the record, this problem is known to be NP-complete, http://en.wikipedia.org/wiki/Subset_sum_problem
#8.1.2.2 elfz on 2006-12-17 15:27 (Reply)
Bendick's memoization approach disappeared so I didn't get a chance to look at it, but there are some ways to further optimize the search solutions.

For example, by breaking apart the positive and negative lists and sorting them, it restricts the number of options to try at any point. If a running sum is positive, we know the any solution will contain a negative number, and vice versa. If we have a positive sum and no negative numbers, the best thing to do is to just take the smallest remining positive numbers and return immediately. That ends up cutting a lot of branches out of the search space.

HTML version of the code: http://www.theaboutbox.com/code/steve-irs

You can download the actual code here. http://www.theaboutbox.com/code/steve-irs/steve-irs.ml

This algorithm seems to take about the same amount of time whether or not there is a solution. (2ms on my machine, FWIW)

Thinking about the problem in the context of a mobile phone network may beg a different solution. If this maps onto some sort of routing or flow control algorithm, I can imagine it being more important to come up with a good solution in a fixed period of time (with a much larger dataset) than converge on the exact solution...
#9 cameron (Homepage) on 2006-12-07 12:05 (Reply)
Hi Cameron,
Bendicks code is here:
http://destraynor.com/bendick.txt

I had to move it as the formatting was causing oddities in the page display.


Des
#9.1 Des Traynor (Homepage) on 2006-12-07 12:27 (Reply)
I've posted a solution in perl here: http://www.lazycodemonkey.com/?p=37

It was fairly challenging - maybe because I haven't written anything like this in a while. About 50 ms total time to run.

Out of curiosity, how long did it take you guys to write this?
#10 dmitry (Homepage) on 2006-12-07 17:23 (Reply)
Delphi Implementation takes 219ms to find all 33494 Solutions, 0ms to find the first.
#11 Delphite on 2006-12-17 08:15 (Reply)

Add Comment

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
Standard emoticons like :-) and ;-) are converted to images.
E-Mail addresses will not be displayed and will only be used for E-Mail notifications
You can use [geshi lang=LANG][/lang] tags to embed source code snippets
 
 

About:

Switch to Dark on Light!
Pic of Me.

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

Shower doors Ireland, Bathrooms, Shower Enclosures, Bathroom Suites, showers, beds, mattresses, online bed store, king size, queen, duvet, bedroom furniture bathroom furniture, sinks, suites, toilets, taps, and basins online

RSS Feed

Quicksearch