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) 

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>)