This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Tail-recursive version of ant puzzle

By: a guest on Sep 25th, 2011  |  syntax: F#  |  size: 1.31 KB  |  views: 315  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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)
clone this paste RAW Paste Data