# Tail-recursive version of ant puzzle

a guest
Sep 25th, 2011
795
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. open System.Collections.Generic
2.
3. let visited = new Dictionary<_,_>(HashIdentity.Structural)
4.
5. let rec walk xx yy =
7.         let rec sumInner n soFar =
8.             match n with
9.             | x when x<10  -> soFar+x
10.             | x -> sumInner (n/10) (soFar + n % 10) in
11.         sumInner number 0 in
12.     let rec innerWalk (totalSoFar,listOfPointsToVisit) =
13.         match listOfPointsToVisit with
14.         | [] -> totalSoFar
15.         | _ ->
16.             innerWalk (
17.                 listOfPointsToVisit
18.                 (* remove points that we've already seen *)
19.                 |> List.filter (fun (x,y) ->
20.                     match visited.TryGetValue((x,y)) with
21.                     | true,_ -> false (* remove *)
22.                     | _      -> visited.[(x,y)] <- 1 ; true)
23.                 (* increase totalSoFar and add neighbours to list *)
24.                 |> List.fold
25.                     (fun (sum,newlist) (x,y) ->
27.                         | n when n<26 ->
28.                             (sum+1,(x+1,y)::(x-1,y)::(x,y+1)::(x,y-1)::newlist)
29.                         | n -> (sum,newlist))
30.                     (totalSoFar,[]))
31.     innerWalk (0,[(xx,yy)])
32.
33. let _ =
34.     Printf.printf "Points: %d\n" (walk 1000 1000)
RAW Paste Data