Willem Hoek  »  Solving the Jane Street Puzzle of April 2020; Backtrack with OCaml

May 01, 2020


Wassily Kandinsky, Composition VIII, 1923

Triads

Every month, Jane Street Capital post a puzzle on their website. This was the puzzle for April 2020. [1]

Approach

I started to solve the puzzle by hand in order to understand the problem space better and to find patterns. Solving the triangular grid by hand is quite easy for lower value of N. Example for N=9.

Some observations:

A solution is only possible if the number of dots is multiple of 3. This reduced the problem space by a third.

Number of dots      = (N + 1) * N / 2
Number of triads    = dots / 3 
                    = (N + 1) * N / 6

N        dots     triads
--       ----  -----------
 1	   1	0.333333333
 2	   3	1
 3	   6	2
 4	  10	3.333333333   <--- infeasible, as the number of dots is not divisible by 3
 5	  15	5
 6	  21	7
 7	  28	9.333333333
 8	  36	12
 9	  45	15
10	  55	18.33333333
11	  66	22
.
.
37	 703	234.3333333
38	 741	247
39	 780	260

Backtracking my way into the solution

At this point my thinking was to automate the manual (by hand) method by creating a program based on the depth-first search (DFS) backtracking algorithm. Backtracking can be used to solve many well known problems such as suduko [6] and the eight queens puzzle.

A concern was that the run-time might be very long for high values of N. Worse case the run-time is polynomial - O(n^k), with k somewhere between 2-4. However with the known constraints such as the the sides and corners, it might not be so bad.

The program I created was called triad.exe. More about the program a bit later.

Running triad.exe

  N      dots    triads  solve  
 --   -------   -------  -----  
  1         1       0.3      - 
  2         3       1.0      1 
  3         6       2.0      - 
  4        10       3.3      - 
  5        15       5.0      - 
  6        21       7.0      - 
  7        28       9.3      - 
  8        36      12.0      - 
  9        45      15.0      1   <----- solve = 1 means that a valid solution exists
 10        55      18.3      - 
 11        66      22.0      1 
 12        78      26.0      1 
 13        91      30.3      - 
 14       105      35.0      1 
 15       120      40.0      - 
 16       136      45.3      - 
 17       153      51.0      - 
 18       171      57.0      - 
 19       190      63.3      - 
 20       210      70.0      - 
 21       231      77.0      1 
 22       253      84.3      - 
 23       276      92.0      1 
 24       300     100.0      1 
 25       325     108.3      - 
 26       351     117.0      1 
 ^C

It took less than a second to solve up until N=26. For N=27 – the calculation took way too long, so I stopped it. However, I spotted a pattern. It can be solved for N = 9, 11, 12 & 14 and then again for 21, 23, 24 & 26. It appears that this pattern might repeat itself for every 12th value of N. With this in mind I tested it for N=33 onwards (which is N=21 +12)

triad.exe 33

  N      dots    triads  solve
 --   -------   -------  -----
 33       561     187.0      1
 34       595     198.3      -
 35       630     210.0      1
 36       666     222.0      1
 37       703     234.3      -
 38       741     247.0      1
 ^C

Bingo! What about from N=45, which is +12 from N=33?

triad.exe 45

  N      dots    triads  solve
 --   -------   -------  -----
 45      1035     345.0      1     
 46      1081     360.3      -     
 47      1128     376.0      1     
 48      1176     392.0      1     
 49      1225     408.3      -     
 50      1275     425.0      1     
 ^C

Same story. Why this pattern and what about the values inbetween these? I was not 100% sure at this stage. But, with the clock ticking and some confidence I submitted my answer which got my name on the Correct Submissions list.

284, which is 2 + 9 + 11 + 12 + 14 + 21 + 23 + 24 + 26 + 33 + 35 + 36 + 38

Patterns

So why does the pattern repeat and what about the other values?

We already know that N=9 is valid - as it was solved by hand. By simply adding rows of triads, we can extend the valid solutions to N=11 and also for N=12 and N=14.

Similarly, the N=21 triangle can be build up from other triangles that are all valid solutions. Starting with N=9 and adding triangles where N=9 and N=12. As per initial obervations the corner triads can be ignored if need be. This same pattern repeats every 12th row.

So the backtracking program was probably not required, but it was definitely a good way to validate the solution.

Using OCaml

I mostly use Python for this kind of puzzles. However, similar to my solution to the February 2020 Jane Street Puzzle, I decided to rather use OCaml. This was mainly to improve my OCaml skills but also for performance.

An Array is used to model the triangular grid which is created with the create_grid function in the code.

   Grid Coordinates

   |  1  2  3  4
  -+-----------------> x-value
   |
1  !  0  1  1  1           Every 0 is a dot in the triangular grid
   |                       Sample here is where N=4
2  |  0  0  1  1
   |                       If grid value is:
3  |  0  0  0  1           0 -> empty, available to place a triad
   |                       1 -> occupied / unavailable
4  |  0  0  0  0  
   | 
y-value

Triads can be placed in the grid pointing Up (like a pyramid) or Down (inverted pyramid). This is done by the change_grid function. The X in diagram below refer to the dot being evaluated. The coordinate of X is determined by the next_dot function. A triad placement is_valid if all three points of the triad are empty (0).

     Up         Down

      X         X 0          
     0 0         0                 

See below for the the full program. I used the OCaml for Windows [3] compiler. If you don’t have an OCaml compiler, you can run the code by using one of the online notebooks such as https://sketch.sh/new/ml.

(* triangle is marked with 0's, borders with 1's *)
let create_grid size =
  let grid = Array.make_matrix (size + 2) (size + 2) 1 in
  for y = 1 to size  do
    for x = 1 to size do
      if x <= y then grid.(x).(y) <- 0
    done
  done;
  grid

(* find next open space for triad placement *)
let next_dot grid =
  let x' = ref 0 in
  let y' = ref 0 in
  let size = Array.length grid - 2 in
  try
    for x = 1 to size do
      for y = 1 to size do
        if grid.(x).(y) = 0 then
          begin
            y' := y;
            x' := x;
            raise Exit
          end
      done
    done;
    None
  with Exit -> Some (!x', !y')

type triad = Up | Down

let is_valid x y placement grid =
  assert (grid.(x).(y) = 0); 
  match placement with
  | Up -> grid.(x).(y+1) = 0 && grid.(x+1).(y+1) = 0
  | Down -> grid.(x+1).(y) = 0 && grid.(x+1).(y+1) = 0

(* place or remove the triad *)
let change_grid x y placement grid value =
  match placement with
  | Up -> grid.(x).(y) <- value;
          grid.(x).(y+1) <- value;
          grid.(x+1).(y+1) <- value
  | Down -> grid.(x).(y) <- value;
            grid.(x+1).(y) <- value;
            grid.(x+1).(y+1) <- value

let rec solve grid =
  let dot = next_dot grid in
  match dot with
  | None -> true
  | Some (x, y) ->
     let check placement =
       if is_valid x y placement grid then
         begin
           change_grid x y placement grid 1;
           if solve grid then true else
             begin
               change_grid x y placement grid 0;
               false
             end
         end
       else false in
     List.exists (fun z -> check z) [Up; Down]

let print_header () =
  Format.printf "  N      dots    triads  solve\n%!";
  Format.printf " --   -------   -------  -----\n%!"

let () =
  print_header ();
  for n = 1 to 26 do
    let dots = (n + 1) * n / 2 in
    let triads = float_of_int dots /. 3. in
    let result  =
      if (dots mod 3 = 0) && (create_grid n |> solve)
      then "1" else "-" in
    Format.printf "%3i %9i %9.1f %6s \n%!" n dots triads result
  done

In my case I set the start value with a command line argument and used the Unix.gettimeofday() function to measure execution time. This was excluded from the code above as the Sys and Unix module will only work on local installations of OCaml (including Windows).

let () =
  let i = try int_of_string Sys.argv.(1) |> max 1 with _ -> 1 in
  let t = Unix.gettimeofday () in
  print_header ();
  for n = i to 99 do
    let dots = (n + 1) * n / 2 in
    let triads = float_of_int dots /. 3. in
    let result  =
      if (dots mod 3 = 0) && (create_grid n |> solve)
      then "1" else "-" in
    Format.printf "%3i %9i %9.1f %6s %10.1f \n%!"
      n dots triads result (Unix.gettimeofday () -. t)
  done

Commands used to test, compile or profile the code.

# testing
utop triad.ml

# final version
ocamlfind ocamlopt -o triad.exe -linkpkg -package unix triad.ml
ocamlfind ocamlopt -o triad.exe  -linkpkg -package unix -noassert -rectypes -inline 1000 triad.ml

# Profiling
ocamlfind ocamloptp -o triad.exe  -linkpkg -package unix -noassert -rectypes -inline 1000 triad.ml
./triad.exe
ocamlprof triad.ml

Although the program above assisted me to find the correct answer, it was very inefficient. Here are some of the obvious changes that can be made:

A comment on style. I used ‘Exceptions’ in my code - see the use of raise in the next_dot function. This approach is seen as not good style. As per Jane Street Style Guide:

Although raising is fine, one should not write code that depends on which exception is raised.

Another possible improvement area is not to use an Array to keep track of the solution space.

This was a lot of fun. Thanks to Jane Street Capital for posting the puzzle. If you can suggest changes to the code or have also solved this puzzle, let me know.

References and further reading

[1] Jane Street - Puzzle Archive.
https://www.janestreet.com/puzzles/archive/. Retrieved: 2020-04-03

[2] Source code for this post on Github.
https://github.com/whoek/janestreet-puzzles/tree/master/2020-04. Retrieved: 2020-05-01

[3] OCaml for Windows - Graphical Installer
https://fdopen.github.io/opam-repository-mingw/installation/. Retrieved 2020-05-01

[4] Backtracking Iterators, Jean-Christophe Filliatre
https://www.lri.fr/~filliatr/publis/enum2.pdf. Retrieved: 2020-04-10

[5] Functional Programming - Lecture 6: Folding and Backtracking, by Łukasz Stafiniak
http://www.ii.uni.wroc.pl/~lukstafi/pmwiki/uploads/Functional/functional-lecture06.pdf. Retrieved 2020-04-10

[6] OCaml - Sudoku par backtrack
https://openclassrooms.com/forum/sujet/ocaml-sudoku-par-backtrack



Edit