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:
- I was placing the triads along the sides first (vs in the middle). Thus using a constraint of the sides to eliminate some of the infeasible options early on
- When I was unable to place a triad, I would go back and try some other option; backtracking
- The three corners (marked in red above) can be ignored from the solution as they always have the same triad placement
- Every triad can only be placed in one of two ways. Either pointing up like a pyramid or pointing down
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:
- Don’t calculate the next dot by scanning all the items again. Rather have a pre-determined path and follow that
- Use a search path for dots that start on the edges of the grid. That way many infeasible options can be ruled out early on
- Pre-fill the corners with triads, as these placements are known
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
Similar Posts on this website
How-to Import an Excel file into SQLite and back to Excel again
Solving the Jane Street puzzle of December 2022
Why I created Scrumdog - a program to download Jira Issues to a local database
Jane Street puzzle Feb 2021 SOLVED! OCaml to the rescue
Solving the Jane Street puzzle of Dec 2020 - Backtracking with OCaml
Automate your Jira reporting with Python and Excel