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.

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

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

 Value  Row
------ ----
    1     1
    2    75
    3     2
    4     5
    5     3
    6     9
    7     4
    8    17
    9    20
   10     7
   11   416   <==== answer
   12     6
   13   132
   14    27
   15    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



Edit