Tuesday, March 25, 2014

Spring Break - Problem 76 in Forth

Yet again, a problem solved after a long hiatus: hopefully the distance between this solution and the next will be less than the distance between it and the previous, as I am now on a two-week long Spring Break, a perfect time to solve some Project Euler problems. Today, I used Forth, which I hadn't used since problem 9, and there I really only used it as a glorified postscript. This time around, I used some of the more interesting features of the language, like actually using data structures, in this case a big "two dimensional" (that was two hard, so its just a one dimensional and I convert indices between 1 and 2 dimensions) array which I use to solve the problem: We just covered Dynamic Programming in my Algorithms class, and Project Euler 76 happens to be a wonderful problem for Dynamic Programming. Now, the combination of the fact that the solution was found through dynamic programming and the fact that it is written in Forth may make the solution unintelligible to most looking at it, but oh well, and I will admit I had to work through the solution in Python before converting it over to Forth. Here is my solution, runs in about 80ms on my machine.
create count 101 101 * cells allot
: splitIndex { x } x 101 mod x 101 / ;
: makeIndex { i j } 101 j * i + ;
: test1 { i j } i 1 = j 1 = or ;
: test0 { i j } i 0 = j 0 = or ;
: testbig { i j } j i >= ;
: setArray { index value } value count index cells + ! ;
: getArray { index } count index cells + @ ;
: computeAns { i j } i j - j makeIndex getArray i j 1 - 
makeIndex getArray +  ;
: main 0 begin  
dup splitIndex test1 if dup 1 setArray else 
dup splitIndex test0 if dup 0 setArray else
dup splitIndex testbig if dup dup splitIndex drop dup 1 - 
makeIndex getArray 1 + setArray else
dup dup splitIndex computeAns setArray then then then 
1 + dup 101 101 * = until 
100 99 makeIndex getArray CR . CR bye ;
main

No comments:

Post a Comment