### Wednesday, March 01, 2006

## Let's scream

Screamer has two parts. The first part is backtracking/search. You can write your program somewhat normally, but where your searching ends you put a "fail" call. Where your code doesn't "fail" is where your answers get collected. Brian Kuhn posted an "interview question" where you have a sequence of numbers, positive and negative, and you return the subsequence that would give the highest total. He had 100 lines of Java; with Screamer's help I had

(screamer:define-screamer-package :maxsub

(:export :findmaxsub))

(in-package :maxsub)

(defun findmaxsub (numbers)

(let ((total -99999))

(car

(nreverse

(all-values

(let ((begin (an-integer-between 0 (1- (length numbers))))

(end (an-integer-between 1 (length numbers))))

(when (>= begin end) (fail))

(let ((subtotal (apply #'+ (subseq numbers begin end))))

(if (> total subtotal)

(fail)

(setf total subtotal)))

(subseq numbers begin end)))))))

Every time the subtotal is higher than the previous total there's a "success", and the sublist is collected by the "all-values" call. When it's done, the highest of them all is at the end of that list.

The other part is the "constraints" part, where you list the constraints on your variables, wind up Screamer, and let it go. The main problem I found with Screamer is that it doesn't handle arrays well, it does lists better, and individual variables best of all. This turned Sudoku into an exercise in typing. I had to list out 81 variables - mostly are "something between 1 and 9", some are the starting numbers - and 27 constraints, 9 row, 9 column and 9 box.

You can see the code here. If you have a Gmail account, you should get your Google page to host files if you don't want your own domain.

I've also wanted to learn LTK, so I wrote a separate LTK front-end for Sudoku. It uses LTK as well as the LTK "mega-widgets" in ltk-mw.lisp. Inside it uses a Sudoku solver that takes a 2D array as input, 0's for blanks, and returns a 2D array. Code is here. If you want to try this out as is you'll need to get Screamer loaded.

Something funny in the license for Screamer. Part of the conditions of its use is you have to send an e-mail telling them what version of Common Lisp you're using it with, so they can list it. I'll be adding OpenMCL 1.0 under Mac OSX and SBCL 0.9.0 under Linux. If you try this out then let them know.

int[] maxSeq(int[] a) {

int max = 0, sum = 0,low = 0, high = 0, maxlow = 0, maxhigh = 0;

for ( int i = 0 ; i < a.length ; i++, high++ ) {

sum += a[i];

if ( sum < 0 ) {

sum = 0;

low = i+1;

} else if ( sum > max ) {

max = sum;

maxlow = low;

maxhigh = high;

}

}

int[] seq = new int[maxhigh-maxlow];

System.arraycopy(a, maxlow, seq, 0, maxhigh-maxlow);

return seq;

}

The last parameter to System.arraycopy is length, which needs to be 'maxhigh - maxlow + 1'. Also, your app doesn't work for all negative numbers; from Brian's comments in his solution,

{-5, -12, -3, -7} => {-3}

Thanks for catching the off-by-one bug. The line above the arraycopy() needs a "+1" also.

I didn't read the original problem carefully so I figured that if all of the numbers were negative then the largest largest sum would be zero and it would belong to any zero-length sequence.

<< Home