Skip to content

My solutions for AoC 2017, using Nim, OCaml, and Python

License

Notifications You must be signed in to change notification settings

narimiran/AdventOfCode2017

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Advent of Code 2017

All my Advent of Code repos:

 

Solutions

My aim is to provide clean and readable, yet idiomatic, solutions in all three languages. If you have any comment/suggestion/advice, please let me know!

Originally, I've solved all tasks in Nim and Python as they were released. OCaml solutions were added in November 2019 as a preparation for AoC 2019 (these were my first steps in OCaml).

Task Nim solution OCaml solution Python solution Note
Day 1: Inverse Captcha day01.nim day01.ml day01.py Taking advantage of Python's negative indices.
Day 2: Corruption Checksum day02.nim day02.ml day02.py
Day 3: Spiral Memory day03.nim day03.ml day03.py Building a spiral with table/map/dict in all three versions; using iterators in Nim and Python.
Day 4: High-Entropy Passphrases day04.nim day04.ml day04.py
Day 5: A Maze of Twisty Trampolines, All Alike day05.nim day05.ml day05.py Used try-except in Python for some nice speed improvement.
Day 6: Memory Reallocation day06.nim day06.ml day06.py Python doesn't have OrderedSet (had to use OrderedDict).
Day 7: Recursive Circus day07.nim day07.ml day07.py Python's Counter.most_common() is quite helpful/useful here.
Day 8: I Heard You Like Registers day08.nim day08.ml day08.py
Day 9: Stream Processing day09.nim day09.ml day09.py
Day 10: Knot Hash day10.nim day10.ml day10.py Changed solutions to be reusable for Day 14. Python version uses deque with pop, rotate, and insert. Nim version is a more 'traditional' one.
Day 11: Hex Ed day11.nim day11.ml day11.py Python version uses cube coordinates, Nim and OCaml versions use axial coordinates.
Day 12: Digital Plumber day12.nim day12.ml day12.py BFS in Python, DFS in Nim and OCaml.
Day 13: Packet Scanners day13.nim day13.ml day13.py All three versions precalculate possible values of delay using Chinese remainder theorem to gain a significant speedup.
Day 14: Disk Defragmentation day14.nim day14.ml day14.py
Day 15: Dueling Generators day15.nim day15.ml day15.py Python: generator generator generating generator's values. In Nim, using bit masking gives great speed boost.
Day 16: Permutation Promenade day16.nim day16.ml day16.py
Day 17: Spinlock day17.nim day17.ml day17.py Brute force in Python, using deque.rotate. The expected version in Nim, optimized.
Day 18: Duet day18.nim day18.ml day18.py
Day 19: A Series of Tubes day19.nim day19.ml day19.py All three solutions use complex numbers, which are great for the rotations in 2D plane.
Day 20: Particle Swarm day20.nim day20.ml day20.py
Day 21: Fractal Art day21.nim day21.ml day21.py Unoptimized solution in OCaml. Nim and Python solutions are optimized for the second part. Python version uses numpy and expands the grid (3 steps at once), Nim version counts the number of times each pattern is present after 18 iterations.
Day 22: Sporifica Virus day22.nim day22.ml day22.py OCaml: sum types and pattern matching is the name of the game. Python version uses a dict and a complex plane, Nim version uses an array (faster than a table) of a regular 2D plane with enum for the rotating directions.
Day 23: Coprocessor Conflagration day23.nim day23.ml day23.py
Day 24: Electromagnetic Moat day24.nim day24.ml day24.py BFS in Python. A recursive search in Nim and OCaml, optimized.
Day 25: The Halting Problem day25.nim day25.ml day25.py Python version uses (default)dict. Nim version uses arrays, which are much faster than tables.
Total time: 0.49 sec 1.01 sec* 16.1 sec* * OCaml: unoptimized day21.ml. Python: without the brute-forced day17.py, and day15.py was run in pypy3. For the detailed run times, see below.

 

Run times

  • Nim version: 1.6.6
  • OCaml version: 4.13.1
  • Python version: 3.8.2
  • CPU: AMD Ryzen 3700x @ 3.6 GHz (Linux 5.15)

Times are in milliseconds, the reported results are the average of 20 runs.

day nim ocaml python
01 0.3 0.8 13.3
02 0.5 0.8 13.2
03 0.4 0.7 13.6
04 2.3 2.4 15.7
05 69.0 63.8 2732.1
06 2.4 3.6 32.6
07 2.4 3.9 20.9
08 1.2 1.5 14.5
09 0.4 1.9 17.2
10 0.5 1.4 24.7
11 0.6 1.3 19.5
12 1.8 2.3 16.7
13 1.4 17.4 21.5
14 8.8 32.3 566.2
15 195.4 383.2 2083*
16 6.8 71.0 143.5
17 0.9 4.8 -*
18 0.7 4.6 88.8
19 0.8 1.2 21.4
20 9.2 18.2 1622.5
21 0.5 145.0 197.1
22 50.4 139.3 3555.9
23 0.5 1.0 15.1
24 10.8 52.1 1242.2
25 48.8 52.3 3649.1

OCaml Day21 was not optimized.
Python Day15 was run with pypy3, Python Day17 was brute-forced.