rather imperative OCaml ~ around 0.7 secs in a VMWarePlayer Debian VM.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 let sumofdigits n =
let sn = string_of_int n in
let rv = ref 0 in
let zero = int_of_char '0' in
let _int_of_char x = (int_of_char x) - zero in
String.iter (fun x -> rv := !rv + _int_of_char x) sn;
!rv ;;

module IntIntSet = Set.Make (
struct
let compare (x1,y1) (x2,y2) = if x1=x2 then y1-y2 else x1-x2
type t = int*int
end ) ;;

let p = ref IntIntSet.empty ;;

let rec children x y bndry =
if (sumofdigits x)+(sumofdigits y) > bndry then 0
else if IntIntSet.mem (x,y) !p then 0
else (p := IntIntSet.add (x,y) !p ;
1 + (children (x+1) y    bndry)
+ (children (x-1) y    bndry)
+ (children  x   (y+1) bndry)
+ (children  x   (y-1) bndry))

let _ = Printf.printf "%d points can be visited" (children 1000 1000 25) 
By on 3/10/2012 6:03 PM ()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#light

(*
There is an ant which can walk around on a planar grid. The ant can move one
space at a time left, right, up or down. That is, from (x, y) the ant can go
to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the
digits of the x coordinate plus the sum of the digits of the y coordinate
are greater than 25 are inaccessible to the ant. For example, the point (59,
79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25.
How many points can the ant access if it starts at (1000, 1000), including
(1000, 1000) itself?
*)

let rec sum  n t =
if n < 0 then sum (-n) t else
if n=0 then t else
sum (n/10) (t+n%10)

let rec walk ok todo (seen:Set<int*int>) =
match todo with
| [] -> ok
| (x,y)::tl when seen.Contains((x,y)) -> walk ok tl (seen.Add((x,y)))
| (x,y)::tl when (sum x 0) + (sum y 0) >21 -> walk ok tl (seen.Add((x,y)))
| (x,y)::tl ->

print_any (walk 0 [(1000,1000)](Set.empty<int*int>)
By on 5/18/2009 11:43 AM ()

Hello,

Even faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#light

open System

let sum n =
let rec proc  n t =
if n < 0 then proc (-n) t
else if n=0 then t
else proc (n/10) (t+n%10)
proc n 0

let nMin = 999
let nMax = 1996

type Elem = {visited:bool ref ; sum:int}

let rec walk (lattice:Elem array array) i j k n =
let elem = lattice.[i].[j]
if (!elem.visited)
then  k n
else elem.visited := true
if (elem.sum <= 21)
then   let c1 n = walk lattice i (j+1) k n
let c2 n = walk lattice i (j-1) c1 n
let c3 n = walk lattice (i+1) j c2 n
walk lattice (i-1) j  c3 (n+1)
else  k n

let lattice = Seq.to_array (seq {for i in nMin .. nMax ->
Seq.to_array(seq {for j in nMin .. nMax ->
{visited=ref false ; sum= sum i + sum j}} )})

Array.iter (fun a -> Array.iter (fun e -> e.visited:=false) a) lattice

let r = let t0 = DateTime.Now
let r = walk lattice 1 1 (fun x -> x ) 0
let dt = (DateTime.Now - t0).TotalSeconds
printfn "Time = %A, Nb = %A" dt r
r

Regards

J-C

By on 5/20/2009 11:38 AM ()