feat: impl day 9

4 files changed, 2186 insertions, 1 deletions

diff --git a/aoc_2022/input/day_9.txt b/aoc_2022/input/day_9.txt
new file mode 100644
index 0000000..d5e15df
--- /dev/null
+++ b/aoc_2022/input/day_9.txt
@@ -0,0 +1,2000 @@
+U 2
+L 1
+U 1
+D 2
+L 2
+D 1
+L 2
+R 2
+D 2
+U 2
+L 2
+D 1
+L 2
+U 1
+R 2
+D 2
+R 1
+U 1
+R 1
+L 1
+D 2
+R 1
+D 2
+R 2
+D 2
+L 2
+U 1
+R 1
+L 1
+D 2
+L 1
+R 1
+U 1
+D 1
+R 1
+D 2
+R 2
+L 1
+R 2
+L 2
+U 1
+L 1
+D 2
+U 2
+D 1
+R 2
+L 2
+D 1
+R 1
+D 2
+U 1
+D 2
+R 2
+U 2
+L 2
+D 2
+R 2
+L 1
+D 2
+L 1
+U 2
+R 1
+L 2
+U 1
+R 2
+U 1
+D 2
+R 2
+U 1
+D 2
+L 2
+D 2
+L 1
+R 1
+D 1
+L 2
+D 2
+U 2
+R 1
+U 1
+R 2
+U 2
+L 2
+R 2
+L 2
+R 1
+U 2
+L 2
+R 1
+D 1
+L 1
+D 1
+U 2
+R 1
+U 2
+R 2
+U 2
+L 2
+U 2
+L 2
+U 1
+R 1
+U 2
+R 2
+L 2
+R 2
+U 1
+R 1
+D 1
+U 1
+L 2
+R 3
+L 2
+U 3
+L 1
+R 1
+U 1
+D 1
+U 1
+D 1
+R 3
+U 3
+L 3
+U 1
+R 2
+D 1
+U 2
+D 2
+U 3
+L 2
+U 3
+R 1
+L 2
+U 1
+L 2
+D 2
+U 3
+D 1
+R 3
+U 3
+R 3
+L 1
+D 2
+U 2
+D 3
+U 1
+R 2
+L 1
+D 1
+L 1
+D 3
+R 1
+U 2
+L 2
+D 2
+U 3
+D 2
+U 1
+D 3
+U 2
+L 3
+R 2
+D 2
+R 3
+L 3
+R 1
+D 1
+L 2
+R 1
+D 2
+L 3
+R 2
+U 1
+L 3
+D 2
+R 3
+D 3
+U 1
+L 1
+D 3
+U 3
+D 3
+R 3
+U 1
+D 1
+L 1
+R 3
+L 3
+U 1
+D 3
+R 1
+L 3
+R 3
+D 2
+L 3
+D 3
+U 3
+L 1
+U 1
+L 2
+D 3
+L 2
+U 3
+L 3
+U 1
+R 2
+D 3
+U 2
+R 2
+U 1
+L 2
+D 2
+L 2
+D 1
+U 3
+D 1
+L 1
+U 2
+D 1
+R 2
+L 2
+R 3
+L 2
+R 1
+D 1
+R 1
+D 2
+L 4
+D 3
+R 3
+D 4
+L 3
+D 1
+U 2
+D 1
+L 4
+R 4
+L 3
+R 2
+L 1
+R 2
+D 1
+R 1
+D 4
+U 1
+D 2
+R 3
+D 3
+R 2
+U 1
+D 2
+U 2
+L 1
+D 3
+U 4
+L 3
+U 2
+L 4
+D 4
+L 1
+U 3
+D 2
+R 3
+D 2
+L 2
+U 3
+L 3
+R 2
+D 2
+R 2
+U 3
+L 2
+R 4
+L 4
+U 1
+D 3
+L 2
+R 3
+L 2
+R 3
+D 4
+R 1
+L 1
+U 1
+L 2
+D 3
+L 4
+R 2
+D 2
+U 3
+D 4
+L 3
+R 1
+U 4
+L 3
+D 4
+L 1
+D 3
+L 4
+R 2
+L 1
+R 4
+L 4
+U 3
+D 4
+U 1
+R 2
+D 3
+U 3
+R 2
+L 2
+R 2
+U 4
+L 4
+D 4
+L 3
+D 3
+U 1
+D 1
+U 4
+R 1
+L 2
+U 2
+L 3
+U 3
+L 3
+D 1
+L 2
+U 3
+L 3
+U 2
+L 2
+U 2
+L 4
+R 1
+L 2
+D 2
+R 3
+L 5
+U 1
+R 5
+D 3
+L 5
+U 3
+D 1
+L 3
+R 2
+D 2
+U 3
+R 5
+D 5
+R 1
+D 4
+U 1
+R 1
+L 4
+D 1
+U 3
+D 4
+L 1
+D 1
+L 2
+U 1
+L 3
+R 1
+D 1
+U 1
+D 2
+L 5
+U 2
+R 3
+D 4
+L 4
+R 1
+L 4
+R 5
+D 4
+R 4
+L 4
+U 3
+L 3
+R 1
+D 1
+R 4
+U 1
+R 3
+U 5
+R 5
+D 2
+R 4
+D 5
+L 2
+D 4
+U 4
+R 3
+D 2
+L 5
+R 4
+D 4
+L 1
+D 4
+L 4
+D 4
+R 2
+D 5
+L 4
+U 3
+D 5
+U 5
+L 1
+U 3
+L 2
+U 2
+R 2
+U 3
+D 3
+R 1
+L 3
+R 1
+U 4
+D 1
+R 1
+L 1
+R 4
+L 1
+R 3
+D 4
+U 5
+L 4
+U 5
+L 5
+U 4
+L 3
+D 2
+L 1
+U 1
+R 4
+L 5
+D 3
+U 3
+L 2
+D 1
+L 1
+U 4
+R 6
+U 5
+L 4
+R 3
+U 4
+L 5
+U 3
+D 1
+U 3
+R 4
+L 3
+D 6
+R 1
+L 2
+U 6
+D 6
+R 2
+L 4
+D 1
+R 5
+L 3
+D 1
+R 2
+D 3
+L 6
+U 5
+D 1
+U 2
+R 2
+L 5
+U 1
+D 3
+R 5
+D 2
+L 1
+D 6
+R 4
+D 5
+L 1
+R 2
+L 3
+R 4
+L 6
+U 5
+L 3
+D 4
+R 4
+U 1
+D 3
+R 4
+L 4
+R 1
+U 2
+R 6
+D 1
+L 4
+R 2
+D 5
+R 6
+D 3
+R 5
+L 1
+R 2
+U 2
+D 2
+L 4
+D 6
+L 1
+R 2
+U 3
+D 6
+L 1
+R 3
+L 1
+D 1
+R 6
+D 6
+L 1
+U 4
+L 4
+U 6
+R 6
+L 6
+D 1
+U 2
+R 6
+L 6
+U 6
+D 1
+R 5
+U 4
+R 2
+L 2
+R 5
+U 5
+R 6
+U 2
+D 3
+R 6
+D 2
+R 3
+L 6
+U 5
+R 2
+D 5
+L 3
+D 5
+U 2
+D 4
+L 1
+D 3
+U 1
+L 4
+D 2
+L 3
+U 5
+R 5
+L 3
+D 7
+R 5
+L 5
+U 5
+L 7
+U 3
+L 2
+R 5
+D 1
+R 4
+U 1
+R 5
+U 6
+R 1
+L 3
+U 7
+L 6
+R 2
+L 3
+U 6
+L 4
+D 1
+L 6
+U 2
+L 6
+U 2
+L 4
+U 2
+L 4
+U 4
+D 3
+U 1
+R 1
+U 5
+L 2
+R 3
+D 7
+R 4
+U 4
+R 1
+D 1
+L 7
+R 2
+U 3
+D 1
+U 1
+D 1
+L 2
+R 5
+U 2
+R 5
+U 7
+L 2
+R 6
+U 2
+R 1
+L 7
+U 2
+R 3
+U 2
+R 7
+D 7
+R 6
+U 4
+L 1
+R 1
+U 6
+R 6
+U 1
+L 7
+R 6
+L 2
+U 5
+L 3
+R 4
+D 4
+R 6
+L 5
+D 1
+U 4
+D 6
+L 4
+R 4
+D 1
+L 3
+U 2
+L 7
+R 2
+U 7
+R 3
+L 6
+D 6
+U 3
+D 7
+U 7
+D 7
+R 7
+U 5
+L 2
+U 5
+D 4
+L 4
+U 2
+L 6
+U 4
+D 3
+L 6
+U 7
+R 3
+D 2
+U 2
+L 7
+D 5
+L 2
+U 6
+R 8
+D 7
+R 5
+U 5
+R 3
+L 1
+U 6
+R 3
+D 7
+U 3
+R 4
+U 5
+D 4
+R 1
+D 6
+L 7
+D 2
+R 5
+U 4
+L 1
+R 1
+L 7
+U 6
+D 1
+L 1
+D 8
+U 1
+L 7
+R 1
+U 6
+D 6
+L 4
+U 1
+L 3
+D 6
+R 6
+D 3
+R 7
+U 3
+L 7
+R 6
+L 3
+D 2
+L 4
+U 1
+R 1
+D 7
+L 8
+R 1
+L 7
+D 1
+L 1
+R 3
+U 1
+R 8
+L 6
+D 3
+U 3
+R 2
+D 7
+R 6
+L 2
+R 1
+U 4
+R 6
+L 6
+D 4
+L 4
+U 6
+L 2
+U 7
+D 3
+R 3
+L 5
+R 7
+D 7
+U 8
+L 6
+U 6
+D 7
+L 8
+U 8
+L 6
+U 1
+D 1
+U 8
+D 5
+R 5
+U 7
+D 3
+U 3
+D 2
+U 4
+L 6
+D 6
+L 2
+D 4
+R 2
+L 7
+R 4
+U 4
+D 6
+R 7
+D 6
+U 1
+D 2
+U 1
+D 4
+L 2
+R 4
+L 7
+U 5
+L 3
+D 6
+U 5
+L 6
+U 3
+L 3
+U 1
+D 1
+L 6
+U 3
+L 8
+D 3
+R 7
+L 2
+U 8
+R 5
+U 8
+R 9
+U 9
+L 8
+U 5
+D 3
+U 4
+R 8
+U 4
+L 6
+R 6
+L 8
+R 8
+U 2
+L 2
+R 5
+D 7
+L 3
+D 4
+L 5
+D 1
+R 7
+D 6
+R 6
+D 2
+R 8
+U 8
+R 2
+D 4
+U 3
+R 4
+U 2
+L 3
+U 4
+D 5
+R 4
+U 9
+D 4
+R 7
+L 1
+D 7
+U 6
+L 1
+U 3
+D 8
+R 3
+U 4
+D 2
+L 6
+R 8
+D 5
+R 5
+D 1
+U 2
+L 7
+D 7
+U 6
+D 3
+U 6
+R 9
+U 2
+L 7
+U 4
+L 7
+U 4
+D 3
+U 9
+R 5
+D 2
+U 1
+L 6
+D 2
+L 8
+U 5
+R 3
+U 9
+R 2
+U 9
+L 7
+D 6
+L 4
+R 1
+L 4
+D 5
+R 5
+L 1
+R 8
+L 7
+U 2
+R 9
+L 1
+R 2
+D 4
+U 5
+R 5
+L 10
+D 7
+U 7
+R 9
+L 1
+R 9
+D 7
+U 4
+L 8
+U 9
+R 10
+D 3
+U 2
+D 2
+L 10
+R 7
+L 2
+R 4
+U 10
+R 7
+D 5
+L 7
+R 8
+D 6
+R 6
+U 1
+R 1
+L 4
+D 7
+R 10
+L 3
+U 4
+D 10
+L 5
+R 10
+D 7
+U 2
+D 8
+L 5
+R 2
+D 5
+U 9
+R 6
+L 6
+U 5
+L 3
+R 3
+D 6
+L 3
+U 4
+D 10
+L 6
+U 7
+L 4
+D 5
+L 4
+D 8
+R 5
+U 8
+R 8
+L 1
+D 4
+R 7
+U 5
+D 3
+L 5
+D 3
+L 7
+U 7
+R 4
+U 1
+R 7
+L 3
+R 3
+D 2
+U 6
+D 6
+U 1
+R 6
+D 1
+U 4
+R 5
+D 3
+R 8
+L 2
+D 10
+L 7
+D 10
+U 9
+D 6
+U 3
+L 8
+U 9
+R 10
+D 10
+R 5
+L 10
+D 6
+L 6
+R 11
+D 6
+L 1
+R 8
+U 10
+R 8
+L 8
+R 10
+U 8
+R 4
+L 8
+D 7
+U 4
+L 1
+R 10
+U 10
+L 6
+R 10
+L 6
+U 8
+R 11
+D 9
+L 1
+R 2
+D 10
+L 4
+U 8
+D 9
+L 11
+R 7
+U 7
+L 2
+D 1
+R 8
+U 11
+D 5
+R 4
+U 7
+L 8
+D 7
+R 10
+D 1
+R 5
+U 4
+D 3
+U 4
+D 11
+L 8
+R 10
+D 7
+U 1
+D 11
+U 1
+D 10
+R 5
+L 2
+R 10
+U 9
+D 8
+L 3
+U 6
+R 11
+L 4
+U 4
+R 3
+L 3
+U 2
+R 8
+U 6
+R 7
+D 6
+U 1
+R 3
+L 6
+D 4
+L 2
+D 8
+U 2
+D 3
+R 10
+D 10
+R 1
+L 2
+R 4
+D 10
+L 1
+U 3
+D 1
+R 7
+D 9
+R 1
+L 10
+R 9
+U 11
+R 1
+L 5
+U 7
+R 8
+L 3
+D 5
+R 11
+D 4
+R 2
+U 6
+D 11
+L 5
+D 5
+L 3
+U 7
+R 5
+L 11
+U 11
+L 10
+R 9
+D 2
+U 2
+R 2
+D 11
+L 3
+U 4
+R 3
+U 5
+D 5
+L 5
+U 5
+D 3
+U 5
+D 7
+R 9
+L 1
+D 11
+U 11
+L 5
+R 10
+L 3
+U 12
+L 8
+U 4
+R 12
+U 12
+D 6
+U 1
+L 11
+R 8
+U 8
+R 12
+U 2
+D 12
+R 4
+L 1
+U 12
+R 1
+L 8
+R 5
+U 11
+L 8
+R 2
+L 10
+R 3
+D 11
+L 2
+U 11
+D 7
+L 5
+R 8
+L 5
+U 7
+R 10
+U 3
+L 6
+U 1
+R 9
+D 12
+R 10
+D 3
+R 2
+D 8
+R 2
+D 3
+U 2
+L 12
+D 8
+L 4
+U 8
+D 10
+U 11
+R 11
+U 6
+L 10
+U 3
+L 5
+U 12
+L 9
+R 8
+L 12
+R 3
+D 11
+U 11
+L 9
+R 8
+L 1
+U 2
+L 6
+R 6
+D 5
+R 1
+D 7
+L 3
+U 8
+R 1
+U 12
+R 6
+L 9
+U 6
+R 2
+D 8
+L 11
+U 1
+R 2
+L 3
+U 4
+L 12
+U 1
+D 7
+U 3
+D 10
+L 6
+D 1
+R 2
+U 7
+L 3
+U 2
+D 6
+R 5
+L 11
+R 9
+D 5
+R 8
+L 6
+D 3
+U 7
+L 6
+D 10
+U 4
+L 9
+R 2
+D 8
+U 2
+L 7
+D 13
+R 6
+L 6
+U 3
+D 9
+L 5
+R 11
+D 13
+U 6
+D 8
+L 7
+U 13
+L 3
+D 2
+U 7
+D 12
+L 3
+R 10
+L 8
+D 8
+U 5
+R 4
+U 12
+R 2
+D 11
+L 12
+D 12
+L 11
+D 1
+R 10
+D 10
+U 10
+D 2
+L 2
+R 7
+L 13
+U 5
+L 10
+U 5
+R 5
+L 13
+D 7
+R 9
+U 2
+D 11
+U 4
+R 1
+L 5
+D 7
+L 5
+D 6
+U 7
+R 8
+U 10
+D 12
+R 2
+U 6
+L 12
+D 12
+L 8
+U 1
+D 8
+U 9
+D 11
+U 8
+D 1
+L 9
+R 10
+U 4
+D 4
+U 12
+L 9
+D 13
+L 12
+R 12
+L 11
+D 12
+U 9
+D 1
+R 4
+U 5
+R 8
+U 6
+R 10
+U 1
+L 7
+D 12
+R 13
+D 10
+L 1
+U 9
+L 9
+R 2
+L 14
+R 8
+U 6
+D 7
+R 4
+L 9
+D 3
+L 11
+R 13
+U 6
+D 6
+L 2
+R 6
+U 1
+L 13
+R 9
+D 9
+L 5
+R 9
+D 4
+U 13
+L 9
+D 7
+U 8
+D 1
+U 11
+L 12
+U 4
+D 7
+R 6
+D 13
+L 12
+R 8
+L 6
+U 1
+R 13
+U 9
+D 2
+U 2
+D 1
+U 6
+R 8
+U 2
+R 6
+D 8
+L 10
+D 14
+U 6
+D 8
+L 3
+R 2
+U 4
+D 10
+U 13
+R 1
+L 11
+D 2
+L 6
+D 14
+U 8
+D 11
+R 1
+L 8
+R 12
+U 1
+D 4
+U 10
+L 9
+D 11
+L 10
+U 13
+D 7
+U 4
+L 11
+U 8
+R 12
+D 4
+L 1
+U 7
+D 5
+U 6
+R 7
+L 8
+U 13
+L 1
+D 8
+U 14
+D 5
+U 10
+D 14
+L 6
+U 4
+L 9
+D 6
+U 7
+L 14
+R 13
+D 11
+R 6
+D 10
+U 6
+R 8
+D 14
+U 14
+L 4
+U 2
+L 4
+R 8
+U 14
+D 2
+L 15
+U 4
+D 6
+R 3
+U 3
+L 12
+U 4
+D 8
+R 14
+U 15
+R 3
+D 10
+R 14
+L 15
+R 9
+D 9
+L 10
+U 7
+L 13
+R 4
+U 4
+D 13
+L 14
+U 7
+L 4
+R 5
+D 7
+R 4
+D 15
+R 15
+U 1
+L 2
+R 14
+L 7
+U 13
+R 12
+L 5
+U 8
+L 15
+U 6
+R 11
+L 12
+U 13
+R 4
+U 15
+D 5
+R 14
+L 6
+U 1
+D 5
+L 7
+U 13
+D 8
+U 2
+D 11
+L 6
+R 2
+L 10
+R 6
+L 14
+D 7
+R 6
+L 10
+R 4
+U 1
+L 3
+R 6
+L 8
+D 14
+R 3
+D 15
+L 9
+D 10
+U 11
+R 5
+D 11
+U 4
+R 2
+D 2
+U 6
+L 7
+D 5
+L 12
+U 3
+R 8
+D 13
+R 9
+D 1
+L 3
+R 14
+L 3
+D 13
+L 15
+U 2
+L 2
+U 12
+D 1
+L 9
+U 2
+D 8
+R 12
+L 5
+R 9
+U 15
+D 4
+R 7
+U 9
+R 13
+U 14
+L 1
+U 1
+R 15
+D 1
+R 2
+U 11
+R 8
+D 9
+R 1
+U 13
+D 3
+L 4
+U 6
+L 12
+U 5
+L 2
+R 11
+L 5
+R 4
+D 11
+L 9
+U 15
+L 12
+U 16
+L 12
+D 6
+L 3
+D 12
+U 2
+L 4
+R 15
+U 16
+D 13
+L 14
+U 13
+D 11
+R 14
+L 13
+U 9
+L 9
+D 15
+R 1
+D 4
+L 8
+R 1
+D 12
+U 1
+L 13
+D 8
+U 7
+D 7
+L 12
+D 11
+L 7
+U 5
+R 14
+L 6
+R 8
+L 15
+U 12
+R 13
+U 7
+L 1
+D 12
+U 16
+L 8
+U 1
+L 1
+U 6
+D 14
+U 2
+R 9
+L 15
+R 4
+D 5
+U 10
+R 7
+L 15
+R 5
+D 1
+L 1
+D 4
+L 1
+R 4
+D 10
+U 13
+L 1
+R 13
+U 16
+R 15
+D 5
+U 6
+D 1
+R 5
+D 4
+U 6
+R 8
+L 1
+D 3
+U 13
+D 14
+U 11
+D 7
+U 12
+L 1
+D 3
+U 1
+R 2
+U 9
+R 2
+D 5
+L 8
+U 4
+D 1
+L 9
+R 5
+D 12
+R 12
+L 12
+R 16
+L 10
+R 15
+U 7
+D 13
+R 14
+D 12
+R 2
+L 7
+U 5
+L 15
+D 5
+R 12
+U 14
+D 2
+U 11
+R 8
+U 2
+L 5
+D 10
+U 7
+L 3
+U 15
+R 2
+U 11
+L 10
+D 4
+U 6
+D 15
+L 9
+D 8
+U 11
+L 10
+R 17
+D 2
+U 1
+R 7
+U 9
+L 4
+R 5
+L 11
+U 11
+R 13
+L 7
+D 17
+U 10
+D 5
+U 17
+L 1
+U 3
+D 4
+U 16
+D 17
+U 10
+D 12
+U 1
+R 4
+D 2
+U 1
+D 1
+L 9
+D 6
+L 1
+U 8
+L 2
+D 1
+U 10
+L 14
+U 17
+D 12
+U 1
+R 1
+D 8
+L 7
+D 10
+L 15
+R 15
+D 14
+R 12
+D 5
+L 1
+R 14
+L 2
+D 8
+R 15
+U 6
+L 4
+R 5
+D 11
+L 16
+R 11
+D 14
+L 14
+R 16
+U 12
+R 2
+U 16
+L 3
+R 4
+U 15
+R 15
+D 3
+U 17
+R 5
+L 2
+R 15
+D 13
+L 2
+U 4
+L 6
+R 5
+L 5
+R 4
+L 9
+U 3
+L 9
+R 15
+L 4
+R 1
+U 3
+L 1
+D 3
+R 9
+D 9
+L 10
+R 14
+L 18
+U 7
+R 11
+L 6
+R 16
+U 9
+R 5
+U 5
+R 9
+D 9
+L 12
+D 18
+L 11
+D 18
+L 2
+D 8
+R 6
+L 1
+U 11
+L 6
+U 18
+L 8
+D 12
+L 8
+R 15
+L 15
+R 13
+L 10
+D 15
+R 10
+L 11
+R 14
+D 6
+L 9
+U 3
+R 10
+U 18
+R 9
+L 9
+D 4
+L 17
+D 16
+U 10
+R 14
+L 15
+R 5
+U 2
+L 4
+R 15
+U 2
+D 2
+R 9
+U 14
+D 17
+U 5
+R 1
+U 15
+R 17
+D 4
+R 7
+L 4
+R 16
+L 11
+U 10
+R 3
+D 2
+L 5
+R 14
+L 4
+D 11
+L 11
+U 6
+R 9
+U 3
+R 17
+D 16
+R 18
+L 10
+R 15
+L 14
+R 16
+L 12
+U 3
+R 9
+D 17
+R 6
+L 1
+R 16
+L 8
+U 16
+R 6
+L 1
+U 4
+L 17
+R 4
+U 15
+R 19
+D 7
+R 18
+L 16
+R 18
+U 2
+D 11
+L 17
+R 2
+L 10
+U 17
+D 11
+R 17
+U 1
+D 15
+U 6
+D 19
+R 16
+D 12
+L 7
+R 13
+D 14
+L 12
+U 14
+L 5
+R 5
+D 3
+L 10
+U 16
+R 14
+D 16
+L 9
+D 16
+L 10
+R 11
+D 11
+U 19
+L 4
+D 16
+R 8
+D 1
+U 4
+L 15
+R 5
+D 1
+L 19
+D 19
+R 12
+L 18
+D 13
+L 4
+U 6
+R 5
+D 12
+R 15
+D 9
+L 9
+U 16
+D 1
+R 16
+L 7
+R 6
+D 12
+L 7
+R 8
+U 17
+L 12
+D 9
+L 8
+D 16
+R 8
+D 9
+L 17
+R 3
+U 6
+D 1
+R 7
+L 4
+D 10
+U 7
+R 13
+L 10
+D 19
+U 7
+D 10
+L 17
+R 18
+D 15
+R 6
+L 7
+R 8
+U 16
+R 6
+D 3
+L 19
+D 10
+R 12
+U 13
+L 11
diff --git a/aoc_2022/src/day_9.rs b/aoc_2022/src/day_9.rs
new file mode 100644
index 0000000..3d521af
--- /dev/null
+++ b/aoc_2022/src/day_9.rs
@@ -0,0 +1,182 @@
+use std::{cmp::Ordering, collections::HashSet, fmt::Display, str::FromStr};
+
+use aoc::{Problem, Solution};
+
+type Unit = isize;
+type Position = (Unit, Unit);
+
+enum Motion {
+    Up(Unit),
+    Down(Unit),
+    Left(Unit),
+    Right(Unit),
+}
+
+impl FromStr for Motion {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        match s.split_once(' ') {
+            Some(("U", n)) => Ok(Motion::Up(n.parse()?)),
+            Some(("D", n)) => Ok(Motion::Down(n.parse()?)),
+            Some(("L", n)) => Ok(Motion::Left(n.parse()?)),
+            Some(("R", n)) => Ok(Motion::Right(n.parse()?)),
+            _ => Err(anyhow::format_err!("Improper motion format: {}", s)),
+        }
+    }
+}
+
+impl Display for Motion {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Motion::Up(n) => write!(f, "U {}", n),
+            Motion::Down(n) => write!(f, "D {}", n),
+            Motion::Left(n) => write!(f, "L {}", n),
+            Motion::Right(n) => write!(f, "R {}", n),
+        }
+    }
+}
+
+#[derive(Clone)]
+enum List {
+    Cons(Position, Box<List>),
+    None,
+}
+
+impl List {
+    fn new() -> Self {
+        Self::None
+    }
+
+    fn prepend(self) -> List {
+        Self::Cons(Default::default(), Box::new(self))
+    }
+
+    fn update_from_motion(&mut self, motion: Motion) -> Vec<Position> {
+        let Self::Cons(position, next) = self else {
+            panic!("update_from_motion must be called on a head with at least one tail.");
+        };
+
+        let (dx, dy, count) = match motion {
+            Motion::Up(n) => (0, 1, n),
+            Motion::Down(n) => (0, -1, n),
+            Motion::Left(n) => (-1, 0, n),
+            Motion::Right(n) => (1, 0, n),
+        };
+
+        let mut visited = Vec::new();
+        for _ in 0..count {
+            position.0 += dx;
+            position.1 += dy;
+            visited.push(next.as_mut().update_from_position(position));
+        }
+
+        visited
+    }
+
+    fn update_from_position(&mut self, head: &Position) -> Position {
+        let Self::Cons(position, next) = self else {
+            return *head;
+        };
+
+        if position.0.abs_diff(head.0) > 1 || position.1.abs_diff(head.1) > 1 {
+            match position.0.cmp(&head.0) {
+                Ordering::Less => position.0 += 1,
+                Ordering::Equal => {}
+                Ordering::Greater => position.0 -= 1,
+            }
+
+            match position.1.cmp(&head.1) {
+                Ordering::Less => position.1 += 1,
+                Ordering::Equal => {}
+                Ordering::Greater => position.1 -= 1,
+            }
+        }
+
+        next.as_mut().update_from_position(position)
+    }
+}
+
+pub struct Day9;
+
+impl Problem for Day9 {
+    const DAY: u8 = 9;
+
+    const INPUT: &'static str = include_str!("../input/day_9.txt");
+}
+
+impl Solution for Day9 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> Result<Self::Answer1, anyhow::Error> {
+        let mut head = List::new();
+        head = head.prepend();
+        head = head.prepend();
+
+        input
+            .lines()
+            .flat_map(Motion::from_str)
+            .flat_map(|motion| head.update_from_motion(motion))
+            .try_fold(HashSet::new(), |mut set, pos| {
+                set.insert(pos);
+                Ok(set)
+            })
+            .map(|s| s.len())
+    }
+
+    fn part_2(input: &str) -> Result<Self::Answer2, anyhow::Error> {
+        let mut head = List::new();
+        for _ in 0..10 {
+            head = head.prepend();
+        }
+
+        input
+            .lines()
+            .flat_map(Motion::from_str)
+            .flat_map(|motion| head.update_from_motion(motion))
+            .try_fold(HashSet::new(), |mut set, pos| {
+                set.insert(pos);
+                Ok(set)
+            })
+            .map(|s| s.len())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_part_1_example() -> Result<(), anyhow::Error> {
+        let test_input = indoc::indoc! {r#"
+            R 4
+            U 4
+            L 3
+            D 1
+            R 4
+            D 1
+            L 5
+            R 2
+        "#};
+
+        Ok(assert_eq!(13, Day9::part_1(test_input)?))
+    }
+
+    #[test]
+    fn test_part_2_example() -> Result<(), anyhow::Error> {
+        let test_input = indoc::indoc! {r#"
+            R 5
+            U 8
+            L 8
+            D 3
+            R 17
+            D 10
+            L 25
+            U 20
+        "#};
+
+        Ok(assert_eq!(36, Day9::part_2(test_input)?))
+    }
+}
diff --git a/aoc_2022/src/lib.rs b/aoc_2022/src/lib.rs
index d3d4aea..09de695 100644
--- a/aoc_2022/src/lib.rs
+++ b/aoc_2022/src/lib.rs
@@ -1,5 +1,6 @@
 #![feature(iterator_try_collect)]
 #![feature(iter_next_chunk)]
+#![feature(is_some_and)]
 
 pub mod day_1;
 pub mod day_2;
@@ -9,3 +10,4 @@ pub mod day_5;
 pub mod day_6;
 pub mod day_7;
 pub mod day_8;
+pub mod day_9;
diff --git a/aoc_2022/src/main.rs b/aoc_2022/src/main.rs
index 3c26a16..f791a30 100644
--- a/aoc_2022/src/main.rs
+++ b/aoc_2022/src/main.rs
@@ -2,7 +2,7 @@ use anyhow::Result;
 use aoc::Solution;
 use aoc_2022::{
     day_1::Day1, day_2::Day2, day_3::Day3, day_4::Day4, day_5::Day5, day_6::Day6, day_7::Day7,
-    day_8::Day8,
+    day_8::Day8, day_9::Day9,
 };
 
 fn main() -> Result<()> {
@@ -14,6 +14,7 @@ fn main() -> Result<()> {
     Day6::solve()?;
     Day7::solve()?;
     Day8::solve()?;
+    Day9::solve()?;
 
     Ok(())
 }