Guest User

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 =
  6.     let addDigits number =
  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) ->
  26.                         match (addDigits x)+(addDigits y) with
  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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×