Willem Hoek

Solving the Jane Street Puzzle of May 2020; Expelled with OCaml

Jun 01, 2020

Leonardo da Vinci, The last Supper, 1495 - 1498

Expelled

Every month, Jane Street Capital post a puzzle on their website. This was the puzzle for May 2020.

Approach

First, lets see how the table provided is composed.

OK – so now we just need to find out what logic to use to add another row.

The value to the left of the diagonal (in red) is the first column in next row
The value to the right of the diagonal (in red) is the second column in next row
And so it goes on (left / right / left / right) until all the values to the left have been transferred to the next row

Solving with a few lines of code

Initially I thought of using Excel but writing a few lines of code was just SO much easier. Here are the final results.

Grid
----

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

 Value  Row
------ ----
   1
  75
   2
   5
   3
   9
   4
  17
  20
   7
 416   <==== answer
   6
 132
  27
  11

Below is the code I used, which was done in OCaml. If you don’t have an OCaml compiler, you can execute the same code by using one of the online notebooks such as https://sketch.sh/new/ml.

The create_grid function is actually all that is required. The bulk of code were simply to print the results.

let create_grid n =
  (* create matrix with n numbers; y is rows, x is series of numbers *)
  let grid = Array.init n
      (fun y -> Array.init n
          (fun x -> x + y - 1)) in
  (* copy values from left & right of diagonal z to next row y *)
  for z = 3 to n / 2 do
    for x = 1 to z - 2  do
      grid.(x * 2 - 1).(z) <- grid.(z - 1 - x).(z - 1);   (* L *)
      grid.(x * 2).(z) <- grid.(z - 1 + x).(z - 1);       (* R *)
    done
  done;
  grid

let print_grid grid size =
  let min_size = min size (Array.length grid - 1) in
  for y = 1 to min_size  do
    for x = 1 to min_size  do
      Printf.printf "%3i%!" grid.(x).(y)
    done;
    Printf.printf "\n%!"
  done

let print_answer grid size =
  for n = 1 to size do
    for  z = 1 to Array.length grid - 1 do
      if n = grid.(z).(z)  
      then Printf.printf "%5i %5i \n%!" n z
    done
  done

let main () =
  let a = create_grid 1000 in
  print_grid a 9;
  print_string "\n";
  print_answer a 15
  
let () = main ()

Commands used to test and compile the code.

# testing
ocaml may.ml

# compile final version, not that it was required
ocamlopt -o may.exe may.ml

I submitted the answer on 2nd of May and my name was 30th on the list of “Correct Submissions” – so this was quite an easy question. Anyway, it still was a lot of fun. Thanks to Jane Street for posting this.

References and further reading

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

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

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

[4] Arrays in Ocaml https://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html. Retrieved 2020-05-01