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 ->
            walk (ok+1) ((x+1,y)::(x-1,y)::(x,y+1)::(x,y-1)::tl) (seen.Add((x,y)))
        
                    
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 ()
IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us
Built with WebSharper