commit c52c434a5a40d4121f4dc06531b37561dba27548
parent 20c9d752bab453ade281fc814950636577093428
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 2 Apr 2023 15:27:41 -0400
Add day 20
Diffstat:
| A | 20/info.mk | | | 5 | +++++ |
| A | 20/input | | | 124 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 20/part1 | | | 94 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 20/part1.c | | | 256 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 20/part2 | | | 207 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 20/part2.c | | | 308 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 20/test1 | | | 37 | +++++++++++++++++++++++++++++++++++++ |
| A | common/hmap_s.c | | | 48 | ++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | common/hmap_s.h | | | 10 | ++++++++++ |
| A | common/vec_s.c | | | 8 | ++++++++ |
| A | common/vec_s.h | | | 10 | ++++++++++ |
11 files changed, 1107 insertions(+), 0 deletions(-)
diff --git a/20/info.mk b/20/info.mk
@@ -0,0 +1,5 @@
+20_SRC = 20/part1.c 20/part2.c common/main.c common/aoc.c common/util.c
+20_SRC += common/hmap_s.c common/vec_s.c
+20_SRC += lib/libdvec/build/libdvec.a lib/liballoc/build/liballoc.a
+20_SRC += lib/libhmap/build/libhmap.a lib/liblist/build/liblist.a
+20_HDR = common/aoc.h common/util.h
diff --git a/20/input b/20/input
@@ -0,0 +1,124 @@
+ M I A Q Z Z X G P
+ F A F U I Z R C R
+ #####################################.#######.#####.###.#####.#####.###.#####.###.#########################################
+ #.........#.#.#...#...........#.#.#.......#.......#.#.....#.....#...#.....#.#...#.#.....#.........#.....#.......#.......#.#
+ #.#####.###.#.###.#.###.#####.#.#.#######.###.#.###.#.#.###.###.###.#.###.#.#.###.#.#.###.###.###.###.#######.###.#.###.#.#
+ #.#...#...#.#.........#.#.....#.....#.#.#...#.#...#...#...#...#...#...#.#.#...#.....#.......#.#...................#...#...#
+ ###.###.###.###.###########.#.#####.#.#.#.#####.#.#######.###.#####.#.###.###.#######.#.#######.#.#.#######.#.#.#####.###.#
+ #...#.#...........#.........#...#.......#...#...#.#.......#.....#...#.#...#.#...#...#.#.#...#...#.#...#.#.#.#.#.....#...#.#
+ ###.#.#.#####################.#####.###.#.#####.#####.#.###.#############.#.###.#.#.###.#.###.#####.###.#.###.###.#########
+ #.........#...#.#...#.#.#.......#...#.#.....#.....#...#.#...#...#.......#.#.....#.#.........#.#.#...#.......#.#.....#...#.#
+ #.###########.#.###.#.#.#.#####.###.###.#.#.#.###.#.#######.#.#####.###.#.###.###.###.#.#.#####.###.#####.###.#########.#.#
+ #.....#...#...#...........#.........#.#.#.#.#.#...#...#.#.#...#.#.....#...#.....#...#.#.#.......#.....#...#.#.....#.#.#.#.#
+ #.#######.#.#.#####.#.###.#####.#.#.#.###########.#.###.#.###.#.###.#.#####.#####.#.#####.#.###.#######.###.#######.#.#.#.#
+ #.#.......#.#...#...#.#...#...#.#.#.#.....#.#.....#.....#.......#...#.....#.....#.#.#.#.#.#.#.....#...#...#.#.#.#.........#
+ #####.#######.#####.#######.#.#.###.#.#####.###.#.#.#######.###.#####.#.#.###.#.#.###.#.#############.#.###.#.#.#.#######.#
+ #.........#.....#.#.#.#...#.#.....#.....#.#.....#.#.#...#...#.......#.#.#.#...#.#...#...#.....#.......#.............#...#.#
+ #.#.###.###.#.#.#.###.###.###.#####.#####.###.###.#.###.###.###.#######.#.###.#.#.#####.#.#####.#######.#.#####.#.###.#####
+ #.#.#.....#.#.#.#.#.....#.......#.#...#.....#...#.#...#.......#...#.....#.#...#.#...........#.#.....#...#.#...#.#...#.#...#
+ #######.#######.#.###.###.#.#.###.###.#.###.#####.#.#.#####.#########.###.#.#####.###.###.###.#.#######.###.#######.#.###.#
+ #.#.....#...#...#...#...#.#.#...#.#.....#.#.#.....#.#.#.....#.......#.#...#.....#...#.#...........#.#.......#...#.....#...#
+ #.#####.###.#.#####.#.###.#######.#.#.#.#.#.#.###.#.#######.###.#########.###.###.###.#####.#.###.#.#.#.#####.#####.#####.#
+ #.#.#...#.#.....#.#.....#.#.#.#.#...#.#...#.#.#.#.#.#.....#.#.....#.....#.#...#.....#.....#.#.#.#.....#...#.#.#...#.#...#.#
+ #.#.###.#.#####.#.###.#####.#.#.###.###.#######.#.#.#.#.###.###.#####.###.#.#####.#############.###.#.#####.#.###.###.###.#
+ #.#.....#.#.............#...#.....#.#...#.........#.#.#.#.#.......#.#.#...#.#.#...#.#.......#.....#.#.......#...#...#.#...#
+ #.###.#.#.#.#####.#.#.#####.###.#.#.#######.#####.#.###.#.###.#.###.#.###.#.#.###.#.###.###.###.###.#########.###.###.###.#
+ #...#.#...#.#...#.#.#...#.#.....#.....#...#.#.....#.#...#.#...#...#.#.....#.#.#...........#.....#.#...#.....#.#.......#.#.#
+ ###.###.#.#####.###.###.#.#######.#.#####.###.#####.#.#.#.#######.#.#.###.#.#.#####.#.#######.###.#.###.#####.###.#.###.#.#
+ #.......#.#.......#.#...#...#.....#...#.........#.#.#.#.......#...#.....#.#.....#.#.#.......#...#.#.#.#...#.#.....#.#...#.#
+ #.#.#.#######.#.#.###.###.#########.#######.###.#.#.#.###.#.#.###.#.#########.###.#.###.#####.###.###.###.#.#####.###.###.#
+ #.#.#.#.#...#.#.#...#.#.#...#...#.#.#.#.......#.#...#...#.#.#.#...#.....#.#...#.#...#...#...#...#...#.#.#.....#...#...#...#
+ #####.#.#.#######.###.#.###.#.###.#.#.#####.#######.###.#.#####.#.#.#####.#.###.#.#######.#.#####.###.#.#.###.###.#.#####.#
+ #.......#...#.#...#...#.#.............#.......#...#.#...#.#...#.#.#.....#.....#...........#...#.#.#.#.......#.#.....#.#...#
+ #####.#.#.###.###.#.###.#####.#.###.#.#####.#.#.###.#.###.###.#.###.#######.#####.###.#.#######.#.#.#####.#######.###.#.#.#
+ #.#...#...#.#.........#.#.....#.#...#...#...#...#.....#...#.......#.....#.......#.#...#.#.......#...#...#.....#.......#.#.#
+ #.#.#.#####.#####.#####.###.#.#######.#######.#####.###.#####.#########.###.#########.#####.#######.#.###.#######.#######.#
+ #.#.#...#...#.#.....#.#.#...#.#.# Q I G B G T H L #...#.#.......#.....#.#...#.....#
+ #.###.###.#.#.#####.#.#.#######.# U Q O V C X P N #.###.###.#####.#.###.#.#.###.###
+IQ........#.#.#.#...#.#...#.#.#.#.# #...#.#...#.#...#.#.#...#.#...#.#
+ ###.#####.###.###.#.#.###.#.#.#.# #.###.###.#.###.###.###.#.###.#.#
+ #.....#.......#.#.....#...#...#..VI XR........................#.#.#...#
+ #.###.#.#####.#.#.###.#.#.#.#.#.# #.###.#.###.#####.#.#######.#.#.#
+ #.#.#.....#.........#...#...#...# #...#.#...#...#.#.#.....#.#.#.#.#
+ ###.###########.#####.###.####### #.###.#########.###.#####.#.#.#.#
+GD......#.#.....#.....#.#.#...#...# #.#.#.....#.....#...#.....#.#.#.#
+ ###.###.###.#####.#####.#####.#.# ###.#########.#.###.#.#.#.#.#.#.#
+ #.......#.......#.#.....#.....#.# #...#.#.#.#.#.#.#.....#.#.....#..OU
+ #####.#####.#.#####.#######.#.#.# ###.#.#.#.#.#.###########.#######
+ #.....#.#.#.#...#.....#.#.#.#.#..HN #.......................#.#...#..VI
+ ###.###.#.#.###.#.#.###.#.###.#.# ###.#######.###.###.#.#.###.#.#.#
+ #.#...........#...#...........#.# #...#...#.....#.#...#.#.#.#.#...#
+ #.###############.############### ###.#.###.#.###.###.#####.#.#.###
+YC....#...#.......#.#.#.#...#.#.#.# #.......#.#.#...#...#.......#.#.#
+ #.###.#.###.###.###.#.###.#.#.#.# #####.#.#######.###.#.###.#.###.#
+ #.....#.......#..................IA GD......#.#.#.....#.#...#.#.#...#.#
+ ################################# #########.#######.#####.#######.#
+ #.#.......#...............#.....# MF..........#.............#.......#
+ #.#.###.#.#.###.###.#.###.#.###.# #.#######.#.#####.#.###.#####.#.#
+ #.....#.#.#...#.#...#...#.....#.# #.#.#...#.#.#.#.#.#.#.#...#...#.#
+ #.#######.#.###.#.#.#####.#####.# #.#.#####.#.#.#.#####.###.#.#.#.#
+ #.....#...#...#.#.#.#.......#...# #...#.....#...#...#.......#.#.#..DM
+ ###.###.#.#.###################.# #.#.#.#######.#.###.#.#######.#.#
+TX....#.#.#...#...#.#.#.......#....ZI #.#.#...........#...#.........#.#
+ #####.#########.#.#.#.###.#####.# #.#####.#.#####.#################
+ #...........#.......#.#.......#.# #.#.#.#.#.#...#.#................AA
+ #.###.#.###.#.#####.###.###.##### ###.#.#.###.#.###.#.###########.#
+ #.#.#.#.#...#...#...#.....#.....# #...#.#.#...#.....#...........#.#
+ #.#.#######.#.#####.#####.###.### ###.#.#####.###.#.#.###.#.#.#.###
+ #...#...#.........#.#...#.#.....# #.......#...#.#.#.#...#.#.#.#....VD
+ #.#####.###.#######.#.#.#.#.##### #.###.#####.#.#####.#############
+HN..#...#.#.......#.....#...#......AF DM....#.........#.......#.....#.#.#
+ ###.###.###########.#.###.#.##### #######################.#####.#.#
+ #...............#.#.#.#.#.#...#.# #...#.............#.............#
+ ###.#######.###.#.#####.#######.# #.#.#.#######.#########.#.###.###
+UV..#...#.#...#...#...............# #.#.#.....#.........#.#.#...#....GO
+ #.#.###.#.#########.###.#######.# #.#.#.#######.###.###.#.#.#.###.#
+ #.....#.......#.......#...#...#.# #.#.#...#.#...#.#.......#.#.#...#
+ #.#.###.#.###.###.###.#.#.###.#.# #.#.#.###.#####.#.###.#.#######.#
+ #.#...#.#...#.....#.#.#.#.#......XA PR..#.....#.#...#.#...#.#.#...#.#.#
+ #############.###.#.#######.#.### #########.#.#.#.#######.###.#.###
+ #.#.........#.#.#.#.#.....#.#.#.# VD..#.........#.#.....#.#...#.#...#
+ #.#####.#.#####.###.#####.#####.# #.#.#.#####.###.###.#.#####.#.#.#
+XA..#.....#...#...#...#.#.#.#.#.#..YY #.#.#.#.........#.....#.......#..UD
+ #.###.###.###.###.###.#.#.#.#.#.# #.#.#######.#.#.###.###.#######.#
+ #.......#.#...#...#...#.....#...# #.#.....#...#.#.#...........#...#
+ #.###.###.#.#.#.#.#.#.#.###.#.#.# #.#.#####.###.#####.###.#######.#
+ #...#...#...#...#...#.....#...#.# #.....#...#.....#...#.#...#.#...#
+ #.###.###.###.#.#.###.###.###.### U V Q O U Y #.#.#.###.###.#####.#.#.###.#####
+ #.#...#.....#.#.#.#.#...#.#...#.# V J D U D C #.#.#.#.....#.#.#.....#.........#
+ #.#######.###.#.###.#.#.#.###.#.#########.###########.###.#######.#####.#######.###########.#######.#.###.#.#####.#####.#.#
+ #.....#...#...#.#.....#.#.#.........#.#.#.....#.........#.#.#.....#...#.......#.#.........#.....#...#.....#...#.....#...#.#
+ ###.#####.###.#.###.#.#######.###.###.#.#.###.#.#########.#.###.#.#.#.#####.###.#####.###.#########.###.#######.###.#######
+ #.....#.#...#.#.#...#.#.#.....#...#.........#.#.........#.....#.#.#.#.#.....#.#...#.....#...#.........#...#.....#.........#
+ ###.#.#.#.###.###.#.#.#.#####.###.###.###.###.#######.###.#.#.#.###.#.#.#####.#.#####.###########.#.###.#.#.###.#####.###.#
+ #.#.#...#...#...#.#.#.#.#.......#.#...#...#...#.........#.#.#.#.....#.#.......#.....#.#.#.......#.#...#.#.#.#.#.#.....#...#
+ #.###.###.###.#####.###.###.###.#####.#####.###.###.#####.###.#.###.#.###.###.#.#####.#.#.#########.#######.#.###.#.#####.#
+ #.......#...#...#...#.........#.#.#.....#.#...#.#.#.#.....#...#.#.#.#...#...#.#.........#.......#.....#.#.......#.#.#.....#
+ #.###.#.#######.###.#####.#######.#####.#.#.###.#.#.#.#####.#####.###.#######.#.#####.#.#.#########.#.#.###.#######.#####.#
+ #.#...#...#.......#.#.......#.........#.#.....#...#.#.#.....#...#...#...#.....#...#...#...#.#...#...#...#.#.....#.......#.#
+ #####.###.#####.#.###.###.#########.#####.###.###.#.###.#.#.###.#.###.#.#.#####.#.###.###.#.#.#####.#####.#.#.###.#.#.#.#.#
+ #...#...#...#...#.#...#.......#.....#...#.#...#...#...#.#.#...#.....#.#.#.....#.#...#.#.#.........#...#.....#.#...#.#.#.#.#
+ ###.#.###.###.#.###.###.#.#.#.#####.#.#######.#.#############.#####.#.###.###.#.#.#####.###################.#####.###.#.###
+ #.....#...#.#.#...#.#...#.#.#.....#.....#.....#...#.....#.......#.......#.#...#.#.#...................#.......#.....#.#...#
+ #####.#####.###########.#.#########.#.#######.#.#####.#####.#######.#.#####.###.#####.#######.#########.###.###########.#.#
+ #.........#...#.........#...#.......#.#.#.#...#.#.....#...#...#.....#.#.......#.#.#.....#...#.........#.#.......#.#.....#.#
+ ###.#.#######.###.#.#.###.###.###.###.#.#.#.###.###.###.#####.#####.#########.#.#.#.#####.#######.#.#######.###.#.###.#.#.#
+ #...#.#...........#.#.#...#.....#.#.......#...#.......#.#...#...#.......#.#.#.#.............#.....#.#...#.....#.#.....#.#.#
+ #.#.#######.###########.###.#######.###.#.###.#.###.###.###.#.###.#.#####.#.#.#######.###.###########.#####.#.#####.#.#.###
+ #.#...#.....#.#...#...#...#.#...#.#...#.#.....#.#.#.#.........#.#.#...#.......#.#.#...#.........#.#.....#...#...#...#.#...#
+ #.#.#####.#.#.###.###.#########.#.#####.#######.#.#####.#######.#####.#######.#.#.###.###.###.#.#.###.#.###########.###.###
+ #.#...#...#...#.........#.#...#.#...#.......#.....#.....#.....#...#.....#...#.#.....#.#.....#.#...#...#.#...#...#.....#...#
+ #.###.###.#.#####.#####.#.###.#.#.#.###.###.###.#.#####.#.###.#.#.#.#####.###.#.###.#.###.#######.###.#####.#.#####.###.#.#
+ #...#...#.#.#.#...#.............#.#.....#.....#.#.#.....#.#.#.#.#.#.......#...#.#.#.#...#.#...#.....#...#.#.......#...#.#.#
+ ###.###.#####.#.###############.###.#########.#.#####.#.#.#.#.#.#.###.#.###.###.#.#.#.#####.#######.#.###.#.#####.#.###.#.#
+ #...#...#.......#.......#.....#.....#.....#.#.#.....#.#.#.#.#.#.#...#.#.#.....#...#.......#.#...#...............#.#.#.#.#.#
+ #.#######.#######.#.#.#####.#.#.#.#####.#.#.#.#.###.###.#.#.#.#.###.#.#######.#.#.###.###.#.#.#####.#.###.###.#######.###.#
+ #.#.#...#...#.....#.#.......#...#...#...#.....#.#.#.#.#...#.#.#...#.#.....#.#.#.#...#...#.......#...#...#...#...........#.#
+ ###.###.#.#.###.#####.#.#.#####.#.###.###.###.###.#.#.#.#.###.###.#.#.###.#.#.#####.#.#####.###.###.###.###.#.###.#######.#
+ #.........#.#...#.#.#.#.#.#.....#...#...#.#...#...#...#.#...#.#...#.....#.#.......#.#...#.....#...#.#.#.#...#.#.........#.#
+ #.###.#.#.#####.#.#.#.#.###.#######.#.###.###.###.###.#######.#.#############.#####.#########.###.#.#.###.###.#.#####.#.###
+ #.#...#.#...#...#.....#.#.....#.....#.#.....#.#.......#.......#.......#.........#.........#.....#.#...#...#...#.....#.#...#
+ ###########################################.#####.#######.#########.#######.#######.#######################################
+ V B H Y L Q
+ J V P Y N D
+
diff --git a/20/part1 b/20/part1
@@ -0,0 +1,94 @@
+--- Day 20: Donut Maze ---
+
+You notice a strange pattern on the surface of Pluto and land nearby to get a closer look. Upon
+closer inspection, you realize you've come across one of the famous space-warping mazes of the
+long-lost Pluto civilization!
+
+Because there isn't much space on Pluto, the civilization that used to live here thrived by
+inventing a method for folding spacetime. Although the technology is no longer understood, mazes
+like this one provide a small glimpse into the daily life of an ancient Pluto citizen.
+
+This maze is shaped like a donut. Portals along the inner and outer edge of the donut can instantly
+teleport you from one side to the other. For example:
+
+ A
+ A
+ #######.#########
+ #######.........#
+ #######.#######.#
+ #######.#######.#
+ #######.#######.#
+ ##### B ###.#
+BC...## C ###.#
+ ##.## ###.#
+ ##...DE F ###.#
+ ##### G ###.#
+ #########.#####.#
+DE..#######...###.#
+ #.#########.###.#
+FG..#########.....#
+ ###########.#####
+ Z
+ Z
+
+This map of the maze shows solid walls (#) and open passages (.). Every maze on Pluto has a start
+(the open tile next to AA) and an end (the open tile next to ZZ). Mazes on Pluto also have portals;
+this maze has three pairs of portals: BC, DE, and FG. When on an open tile next to one of these
+labels, a single step can take you to the other tile with the same label. (You can only walk on .
+tiles; labels and empty space are not traversable.)
+
+One path through the maze doesn't require any portals. Starting at AA, you could go down 1, right
+8, down 12, left 4, and down 1 to reach ZZ, a total of 26 steps.
+
+However, there is a shorter path: You could walk from AA to the inner BC portal (4 steps), warp to
+the outer BC portal (1 step), walk to the inner DE (6 steps), warp to the outer DE (1 step), walk to
+the outer FG (4 steps), warp to the inner FG (1 step), and finally walk to ZZ (6 steps). In total,
+this is only 23 steps.
+
+Here is a larger example:
+
+ A
+ A
+ #################.#############
+ #.#...#...................#.#.#
+ #.#.#.###.###.###.#########.#.#
+ #.#.#.......#...#.....#.#.#...#
+ #.#########.###.#####.#.#.###.#
+ #.............#.#.....#.......#
+ ###.###########.###.#####.#.#.#
+ #.....# A C #.#.#.#
+ ####### S P #####.#
+ #.#...# #......VT
+ #.#.#.# #.#####
+ #...#.# YN....#.#
+ #.###.# #####.#
+DI....#.# #.....#
+ #####.# #.###.#
+ZZ......# QG....#..AS
+ ###.### #######
+JO..#.#.# #.....#
+ #.#.#.# ###.#.#
+ #...#..DI BU....#..LF
+ #####.# #.#####
+YN......# VT..#....QG
+ #.###.# #.###.#
+ #.#...# #.....#
+ ###.### J L J #.#.###
+ #.....# O F P #.#...#
+ #.###.#####.#.#####.#####.###.#
+ #...#.#.#...#.....#.....#.#...#
+ #.#####.###.###.#.#.#########.#
+ #...#.#.....#...#.#.#.#.....#.#
+ #.###.#####.###.###.#.#.#######
+ #.#.........#...#.............#
+ #########.###.###.#############
+ B J C
+ U P P
+
+Here, AA has no direct path to ZZ, but it does connect to AS and CP. By passing through AS, QG, BU,
+and JO, you can reach ZZ in 58 steps.
+
+In your maze, how many steps does it take to get from the open tile marked AA to the open tile
+marked ZZ?
+
+
diff --git a/20/part1.c b/20/part1.c
@@ -0,0 +1,256 @@
+#include "allocator.h"
+#include "aoc.h"
+#include "hmap.h"
+#include "hmap_s.h"
+#include "vec_s.h"
+#include "util.h"
+#include "list.h"
+
+#include <assert.h>
+#include <ctype.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#define PORTAL_ID(a, b) ((size_t) ((uint8_t) (a) * 100 + (uint8_t) (b)))
+
+struct djk_state {
+ size_t dist;
+ struct vec2i pos;
+
+ struct list_link link;
+};
+
+static bool
+djk_dist_ordering(const struct list_link *l1, const struct list_link *l2)
+{
+ const struct djk_state *s1, *s2;
+
+ s1 = LIST_UPCAST(l1, struct djk_state, link);
+ s2 = LIST_UPCAST(l2, struct djk_state, link);
+
+ return s1->dist < s2->dist;
+}
+
+static void
+load_map(struct hmap *map, const char *input, size_t len)
+{
+ char line[256];
+ const char *lpos, *lend;
+ struct vec2i pos, *key;
+
+ lpos = aoc.input;
+ lend = lpos + aoc.input_size;
+ vec2i_setv(&pos, 0, 0);
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ for (pos.x = 0; line[pos.x]; pos.x++) {
+ if (line[pos.x] == ' ')
+ continue;
+ key = malloc(sizeof(struct vec2i));
+ vec2i_set(key, &pos);
+ hmap_add(map, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.c = line[pos.x]});
+ }
+ pos.y += 1;
+ }
+}
+
+static void
+load_portals(struct hmap *portals, struct hmap *map)
+{
+ struct hmap_link *link1;
+ struct hmap_link *link2;
+ struct hmap_iter iter;
+ struct vec2i pos;
+ struct vec2i npos;
+ struct vec2i *key;
+ size_t i, id;
+
+ for (HMAP_ITER(map, &iter)) {
+ if (!isupper(iter.link->value.c))
+ continue;
+
+ vec2i_set(&pos, iter.link->key.p);
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&npos, &pos, &adj[i]);
+ link1 = hmap_get(map, (struct hmap_key) {.p = &npos});
+ if (link1 && isupper(link1->value.c))
+ break;
+ }
+ if (i != ADJ_SOUTH && i != ADJ_EAST)
+ continue;
+
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&npos, &pos, &adj[i]);
+ link2 = hmap_get(map, (struct hmap_key) {.p = &npos});
+ if (link2 && link2->value.c == '.')
+ break;
+ }
+ if (i == 4) {
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&npos, link1->key.p, &adj[i]);
+ link2 = hmap_get(map, (struct hmap_key) {.p = &npos});
+ if (link2 && link2->value.c == '.')
+ break;
+ }
+ }
+ assert(i != 4);
+
+ aoc_debug("FOUND %c %c\n", iter.link->value.c, link1->value.c);
+
+ key = memdup(link2->key.p, sizeof(struct vec2i));
+ id = PORTAL_ID(iter.link->value.c, link1->value.c);
+ hmap_add(portals, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.s = id});
+ }
+}
+
+static bool
+get_portal(struct hmap *portals, struct vec2i *pos, struct vec2i *skip, size_t id)
+{
+ struct hmap_iter iter;
+
+ for (HMAP_ITER(portals, &iter)) {
+ if (skip && vec2i_eql(skip, iter.link->key.p))
+ continue;
+ if (iter.link->value.s == id) {
+ vec2i_set(pos, iter.link->key.p);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+static void
+add_djk_state(struct list *active, struct hmap *distmap,
+ struct hmap *portals, struct vec2i *pos, size_t dist)
+{
+ struct hmap_link **hmap_linkp;
+ struct djk_state *nstate;
+ struct vec2i *key;
+ bool new;
+
+ hmap_linkp = hmap_link_pos(distmap, (struct hmap_key) {.p = pos});
+ if (!*hmap_linkp) {
+ key = memdup(pos, sizeof(struct vec2i));
+ hmap_link_alloc(distmap, hmap_linkp,
+ (struct hmap_key) {.p = key},
+ (struct hmap_val) {.s = dist});
+ new = true;
+ } else {
+ if (dist < (*hmap_linkp)->value.s) {
+ (*hmap_linkp)->value.s = dist;
+ new = true;
+ } else {
+ new = false;
+ }
+ }
+
+ if (new) {
+ nstate = malloc(sizeof(struct djk_state));
+ nstate->dist = dist;
+ vec2i_set(&nstate->pos, pos);
+ nstate->link = LIST_LINK_INIT;
+ list_insert_sorted(active, &nstate->link,
+ false, djk_dist_ordering);
+ }
+}
+
+static size_t
+min_dist(struct hmap *map, struct hmap *portals,
+ struct vec2i *start, struct vec2i *end)
+{
+ struct list active;
+ struct hmap distmap;
+ struct list_link *list_link;
+ struct hmap_link *hmap_link;
+ struct hmap_iter hmap_iter;
+ struct djk_state *state;
+ struct vec2i *key, npos;
+ size_t i;
+
+ list_init(&active);
+ hmap_init(&distmap, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ state = malloc(sizeof(struct djk_state));
+ state->dist = 0;
+ vec2i_set(&state->pos, start);
+ list_insert_front(&active, &state->link);
+
+ key = memdup(start, sizeof(struct vec2i));
+ hmap_add(&distmap, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.s = 0});
+
+ while (!list_empty(&active)) {
+ list_link = list_pop_front(&active);
+ state = LIST_UPCAST(list_link, struct djk_state, link);
+
+ if (vec2i_eql(&state->pos, end))
+ return state->dist;
+
+ hmap_link = hmap_get(&distmap, (struct hmap_key) {.p = &state->pos});
+ assert(hmap_link);
+ if (state->dist != hmap_link->value.s) {
+ free(state);
+ continue;
+ }
+
+ hmap_link = hmap_get(portals, (struct hmap_key) {.p = &state->pos});
+ if (hmap_link) {
+ if (get_portal(portals, &npos, &state->pos, hmap_link->value.s))
+ add_djk_state(&active, &distmap, portals,
+ &npos, state->dist + 1);
+ }
+
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&npos, &state->pos, &adj[i]);
+ hmap_link = hmap_get(map, (struct hmap_key) {.p = &npos});
+ if (!hmap_link || hmap_link->value.c != '.') continue;
+ add_djk_state(&active, &distmap, portals,
+ &npos, state->dist + 1);
+ }
+
+ free(state);
+ }
+
+ for (HMAP_ITER(&distmap, &hmap_iter)) {
+ free(hmap_iter.link->key._p);
+ }
+ hmap_deinit(&distmap);
+ list_free_items(&active, free, LIST_OFFSET(struct djk_state, link));
+
+ return 0;
+}
+
+void
+part1(void)
+{
+ struct hmap map;
+ struct hmap portals;
+ struct hmap_iter iter;
+ struct vec2i start, end;
+ size_t answer;
+
+ hmap_init(&map, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ hmap_init(&portals, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ load_map(&map, aoc.input, aoc.input_size);
+ load_portals(&portals, &map);
+
+ assert(get_portal(&portals, &start, NULL, PORTAL_ID('A', 'A')));
+ assert(get_portal(&portals, &end, NULL, PORTAL_ID('Z', 'Z')));
+ answer = min_dist(&map, &portals, &start, &end);
+
+ aoc.answer = aprintf("%lu", answer);
+
+ for (HMAP_ITER(&portals, &iter))
+ free(iter.link->key._p);
+ hmap_deinit(&portals);
+ for (HMAP_ITER(&map, &iter))
+ free(iter.link->key._p);
+ hmap_deinit(&map);
+}
diff --git a/20/part2 b/20/part2
@@ -0,0 +1,207 @@
+--- Part Two ---
+
+Strangely, the exit isn't open when you reach it. Then, you remember: the ancient Plutonians were
+famous for building recursive spaces.
+
+The marked connections in the maze aren't portals: they physically connect to a larger or smaller
+copy of the maze. Specifically, the labeled tiles around the inside edge actually connect to a
+smaller copy of the same maze, and the smaller copy's inner labeled tiles connect to yet a smaller
+copy, and so on.
+
+When you enter the maze, you are at the outermost level; when at the outermost level, only the outer
+labels AA and ZZ function (as the start and end, respectively); all other outer labeled tiles are
+effectively walls. At any other level, AA and ZZ count as walls, but the other outer labeled tiles
+bring you one level outward.
+
+Your goal is to find a path through the maze that brings you back to ZZ at the outermost level of
+the maze.
+
+In the first example above, the shortest path is now the loop around the right side. If the starting
+level is 0, then taking the previously-shortest path would pass through BC (to level 1), DE (to
+level 2), and FG (back to level 1). Because this is not the outermost level, ZZ is a wall, and the
+only option is to go back around to BC, which would only send you even deeper into the recursive
+maze.
+
+In the second example above, there is no path that brings you to ZZ at the outermost level.
+
+Here is a more interesting example:
+
+ Z L X W C
+ Z P Q B K
+ ###########.#.#.#.#######.###############
+ #...#.......#.#.......#.#.......#.#.#...#
+ ###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
+ #.#...#.#.#...#.#.#...#...#...#.#.......#
+ #.###.#######.###.###.#.###.###.#.#######
+ #...#.......#.#...#...#.............#...#
+ #.#########.#######.#.#######.#######.###
+ #...#.# F R I Z #.#.#.#
+ #.###.# D E C H #.#.#.#
+ #.#...# #...#.#
+ #.###.# #.###.#
+ #.#....OA WB..#.#..ZH
+ #.###.# #.#.#.#
+CJ......# #.....#
+ ####### #######
+ #.#....CK #......IC
+ #.###.# #.###.#
+ #.....# #...#.#
+ ###.### #.#.#.#
+XF....#.# RF..#.#.#
+ #####.# #######
+ #......CJ NM..#...#
+ ###.#.# #.###.#
+RE....#.# #......RF
+ ###.### X X L #.#.#.#
+ #.....# F Q P #.#.#.#
+ ###.###########.###.#######.#########.###
+ #.....#...#.....#.......#...#.....#.#...#
+ #####.#.###.#######.#######.###.###.#.#.#
+ #.......#.......#.#.#.#.#...#...#...#.#.#
+ #####.###.#####.#.#.#.#.###.###.#.###.###
+ #.......#.....#.#...#...............#...#
+ #############.#.#.###.###################
+ A O F N
+ A A D M
+
+One shortest path through the maze is the following:
+
+
+ - Walk from AA to XF (16 steps)
+
+ - Recurse into level 1 through XF (1 step)
+
+ - Walk from XF to CK (10 steps)
+
+ - Recurse into level 2 through CK (1 step)
+
+ - Walk from CK to ZH (14 steps)
+
+ - Recurse into level 3 through ZH (1 step)
+
+ - Walk from ZH to WB (10 steps)
+
+ - Recurse into level 4 through WB (1 step)
+
+ - Walk from WB to IC (10 steps)
+
+ - Recurse into level 5 through IC (1 step)
+
+ - Walk from IC to RF (10 steps)
+
+ - Recurse into level 6 through RF (1 step)
+
+ - Walk from RF to NM (8 steps)
+
+ - Recurse into level 7 through NM (1 step)
+
+ - Walk from NM to LP (12 steps)
+
+ - Recurse into level 8 through LP (1 step)
+
+ - Walk from LP to FD (24 steps)
+
+ - Recurse into level 9 through FD (1 step)
+
+ - Walk from FD to XQ (8 steps)
+
+ - Recurse into level 10 through XQ (1 step)
+
+ - Walk from XQ to WB (4 steps)
+
+ - Return to level 9 through WB (1 step)
+
+ - Walk from WB to ZH (10 steps)
+
+ - Return to level 8 through ZH (1 step)
+
+ - Walk from ZH to CK (14 steps)
+
+ - Return to level 7 through CK (1 step)
+
+ - Walk from CK to XF (10 steps)
+
+ - Return to level 6 through XF (1 step)
+
+ - Walk from XF to OA (14 steps)
+
+ - Return to level 5 through OA (1 step)
+
+ - Walk from OA to CJ (8 steps)
+
+ - Return to level 4 through CJ (1 step)
+
+ - Walk from CJ to RE (8 steps)
+
+ - Return to level 3 through RE (1 step)
+
+ - Walk from RE to IC (4 steps)
+
+ - Recurse into level 4 through IC (1 step)
+
+ - Walk from IC to RF (10 steps)
+
+ - Recurse into level 5 through RF (1 step)
+
+ - Walk from RF to NM (8 steps)
+
+ - Recurse into level 6 through NM (1 step)
+
+ - Walk from NM to LP (12 steps)
+
+ - Recurse into level 7 through LP (1 step)
+
+ - Walk from LP to FD (24 steps)
+
+ - Recurse into level 8 through FD (1 step)
+
+ - Walk from FD to XQ (8 steps)
+
+ - Recurse into level 9 through XQ (1 step)
+
+ - Walk from XQ to WB (4 steps)
+
+ - Return to level 8 through WB (1 step)
+
+ - Walk from WB to ZH (10 steps)
+
+ - Return to level 7 through ZH (1 step)
+
+ - Walk from ZH to CK (14 steps)
+
+ - Return to level 6 through CK (1 step)
+
+ - Walk from CK to XF (10 steps)
+
+ - Return to level 5 through XF (1 step)
+
+ - Walk from XF to OA (14 steps)
+
+ - Return to level 4 through OA (1 step)
+
+ - Walk from OA to CJ (8 steps)
+
+ - Return to level 3 through CJ (1 step)
+
+ - Walk from CJ to RE (8 steps)
+
+ - Return to level 2 through RE (1 step)
+
+ - Walk from RE to XQ (14 steps)
+
+ - Return to level 1 through XQ (1 step)
+
+ - Walk from XQ to FD (8 steps)
+
+ - Return to level 0 through FD (1 step)
+
+ - Walk from FD to ZZ (18 steps)
+
+
+This path takes a total of 396 steps to move from AA at the outermost layer to ZZ at the outermost
+layer.
+
+In your maze, when accounting for recursion, how many steps does it take to get from the open tile
+marked AA to the open tile marked ZZ, both at the outermost layer?
+
+
diff --git a/20/part2.c b/20/part2.c
@@ -0,0 +1,308 @@
+#include "allocator.h"
+#include "aoc.h"
+#include "hmap.h"
+#include "hmap_s.h"
+#include "vec_s.h"
+#include "util.h"
+#include "list.h"
+
+#include <assert.h>
+#include <ctype.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#define PORTAL_ID(a, b, i) \
+ ((size_t) (((uint8_t) (i) << 16) + ((uint8_t) (a) << 8) + (uint8_t) (b)))
+#define PORTAL_CC_MASK 0xffff
+#define PORTAL_IN_MASK 0x10000
+
+struct djk_state {
+ size_t dist;
+ struct vec3i pos;
+
+ struct list_link link;
+};
+
+void
+vec3i_add_2d(struct vec3i *dst, const struct vec3i *src, const struct vec2i *off)
+{
+ dst->x = src->x + off->x;
+ dst->y = src->y + off->y;
+ dst->z = src->z;
+}
+
+static bool
+djk_dist_ordering(const struct list_link *l1, const struct list_link *l2)
+{
+ const struct djk_state *s1, *s2;
+
+ s1 = LIST_UPCAST(l1, struct djk_state, link);
+ s2 = LIST_UPCAST(l2, struct djk_state, link);
+
+ return s1->dist < s2->dist;
+}
+
+static void
+load_map(struct hmap *map, const char *input, size_t len,
+ struct vec2i *min, struct vec2i *max)
+{
+ char line[256];
+ const char *lpos, *lend;
+ struct vec2i pos, *key;
+
+ lpos = aoc.input;
+ lend = lpos + aoc.input_size;
+ max->x = max->y = 0;
+ vec2i_setv(&pos, 0, 0);
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ for (pos.x = 0; line[pos.x]; pos.x++) {
+ if (line[pos.x] == ' ')
+ continue;
+ if (line[pos.x] == '.') {
+ min->x = min->x ? MIN(min->x, pos.x) : pos.x;
+ min->y = min->y ? MIN(min->y, pos.y) : pos.y;
+ max->x = max->x ? MAX(max->x, pos.x) : pos.x;
+ max->y = max->y ? MAX(max->y, pos.y) : pos.y;
+ }
+ key = malloc(sizeof(struct vec3i));
+ vec2i_set(key, &pos);
+ hmap_add(map, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.c = line[pos.x]});
+ }
+ pos.y += 1;
+ }
+}
+
+static void
+load_portals(struct hmap *portals, struct hmap *map,
+ struct vec2i *min, struct vec2i *max)
+{
+ struct hmap_link *link1;
+ struct hmap_link *link2;
+ struct hmap_iter iter;
+ struct vec2i pos;
+ struct vec2i *key;
+ size_t i, id;
+ bool inner;
+
+ for (HMAP_ITER(map, &iter)) {
+ if (!isupper(iter.link->value.c))
+ continue;
+
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&pos, iter.link->key.p, &adj[i]);
+ link1 = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (link1 && isupper(link1->value.c))
+ break;
+ }
+ if (i != ADJ_SOUTH && i != ADJ_EAST)
+ continue;
+
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&pos, iter.link->key.p, &adj[i]);
+ link2 = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (link2 && link2->value.c == '.')
+ break;
+ }
+ if (i == 4) {
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&pos, link1->key.p, &adj[i]);
+ link2 = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (link2 && link2->value.c == '.')
+ break;
+ }
+ }
+ assert(i != 4);
+ vec2i_set(&pos, link2->key.p);
+
+ inner = pos.x != min->x && pos.y != min->y
+ && pos.x != max->x && pos.y != max->y;
+ aoc_debug("PORTAL %c %c %li %li %i\n",
+ iter.link->value.c, link1->value.c,
+ pos.x, pos.y, inner);
+
+ key = memdup(&pos, sizeof(struct vec2i));
+ id = PORTAL_ID(iter.link->value.c, link1->value.c, inner);
+ hmap_add(portals, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.s = id});
+ }
+}
+
+static bool
+get_portal(struct hmap *portals, struct vec3i *pos, size_t id)
+{
+ struct hmap_iter iter;
+ const struct vec3i *tmp;
+
+ for (HMAP_ITER(portals, &iter)) {
+ tmp = iter.link->key.p;
+ if (iter.link->value.s == id) {
+ pos->x = tmp->x;
+ pos->y = tmp->y;
+ pos->z = 0;
+ return true;
+ }
+ }
+
+ return false;
+}
+
+static void
+add_djk_state(struct list *active, struct hmap *distmap,
+ struct hmap *portals, struct vec3i *pos, size_t dist)
+{
+ struct hmap_link **hmap_linkp;
+ struct djk_state *nstate;
+ struct vec3i *key;
+ bool new;
+
+ hmap_linkp = hmap_link_pos(distmap, (struct hmap_key) {.p = pos});
+ if (!*hmap_linkp) {
+ key = memdup(pos, sizeof(struct vec3i));
+ hmap_link_alloc(distmap, hmap_linkp,
+ (struct hmap_key) {.p = key},
+ (struct hmap_val) {.s = dist});
+ new = true;
+ } else {
+ if (dist < (*hmap_linkp)->value.s) {
+ (*hmap_linkp)->value.s = dist;
+ new = true;
+ } else {
+ new = false;
+ }
+ }
+
+ if (new) {
+ aoc_debug("ADDING NEW\n");
+ nstate = malloc(sizeof(struct djk_state));
+ nstate->dist = dist;
+ vec3i_set(&nstate->pos, pos);
+ nstate->link = LIST_LINK_INIT;
+ list_insert_sorted(active, &nstate->link,
+ false, djk_dist_ordering);
+ }
+}
+
+static size_t
+min_dist(struct hmap *map, struct hmap *portals,
+ struct vec3i *start, struct vec3i *end)
+{
+ struct list active;
+ struct hmap distmap;
+ struct list_link *list_link;
+ struct hmap_link *hmap_link;
+ struct hmap_iter hmap_iter;
+ struct djk_state *state;
+ struct vec3i *key, npos;
+ size_t i, id;
+
+ list_init(&active);
+ hmap_init(&distmap, 256, vec3i_hmap_hash, vec3i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ state = malloc(sizeof(struct djk_state));
+ state->dist = 0;
+ vec3i_set(&state->pos, start);
+ list_insert_front(&active, &state->link);
+
+ key = memdup(start, sizeof(struct vec3i));
+ hmap_add(&distmap, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.s = 0});
+
+ while (!list_empty(&active)) {
+ list_link = list_front(&active);
+ state = LIST_UPCAST(list_link, struct djk_state, link);
+ if (vec3i_eql(&state->pos, end))
+ return state->dist;
+ list_link_pop(list_link);
+
+ aoc_debug("ACTIVE (%lu) %li %li %li\n",
+ state->dist, state->pos.x, state->pos.y, state->pos.z);
+
+ hmap_link = hmap_get(&distmap, (struct hmap_key) {.p = &state->pos});
+ assert(hmap_link);
+ if (state->dist != hmap_link->value.s) {
+ free(state);
+ continue;
+ }
+
+ hmap_link = hmap_get(portals, (struct hmap_key) {.p = &state->pos});
+ if (hmap_link) {
+ id = hmap_link->value.s;
+ if (get_portal(portals, &npos, id ^ PORTAL_IN_MASK)) {
+ if (id) {
+ aoc_debug("PORTAL %c %c %i -> %li %li\n",
+ (id >> 8) & 0xff, id & 0xff,
+ !!(id & PORTAL_IN_MASK), npos.x, npos.y);
+ } else {
+ aoc_debug("NO PORTAL %c %c\n",
+ (hmap_link->value.s >> 8) & 0xff,
+ (hmap_link->value.s >> 0) & 0xff);
+ }
+
+ if (id & PORTAL_IN_MASK) {
+ npos.z = state->pos.z + 1;
+ add_djk_state(&active, &distmap, portals,
+ &npos, state->dist + 1);
+ } else if (id) {
+ npos.z = state->pos.z - 1;
+ if (npos.z >= 0) {
+ add_djk_state(&active, &distmap, portals,
+ &npos, state->dist + 1);
+ }
+ }
+ }
+ }
+
+ for (i = 0; i < 4; i++) {
+ vec3i_add_2d(&npos, &state->pos, &adj[i]);
+ hmap_link = hmap_get(map, (struct hmap_key) {.p = &npos});
+ if (!hmap_link || hmap_link->value.c != '.') continue;
+ add_djk_state(&active, &distmap, portals,
+ &npos, state->dist + 1);
+ }
+
+ free(state);
+ }
+
+ for (HMAP_ITER(&distmap, &hmap_iter)) {
+ free(hmap_iter.link->key._p);
+ }
+ hmap_deinit(&distmap);
+ list_free_items(&active, free, LIST_OFFSET(struct djk_state, link));
+
+ return 0;
+}
+
+void
+part2(void)
+{
+ struct hmap map;
+ struct hmap portals;
+ struct hmap_iter iter;
+ struct vec3i start, end;
+ struct vec2i min, max;
+ size_t answer;
+
+ hmap_init(&map, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ hmap_init(&portals, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ load_map(&map, aoc.input, aoc.input_size, &min, &max);
+ load_portals(&portals, &map, &min, &max);
+
+ assert(get_portal(&portals, &start, PORTAL_ID('A', 'A', 0)));
+ assert(get_portal(&portals, &end, PORTAL_ID('Z', 'Z', 0)));
+ answer = min_dist(&map, &portals, &start, &end);
+
+ aoc.answer = aprintf("%lu", answer);
+
+ for (HMAP_ITER(&portals, &iter))
+ free(iter.link->key._p);
+ hmap_deinit(&portals);
+ for (HMAP_ITER(&map, &iter))
+ free(iter.link->key._p);
+ hmap_deinit(&map);
+}
diff --git a/20/test1 b/20/test1
@@ -0,0 +1,37 @@
+ Z L X W C
+ Z P Q B K
+ ###########.#.#.#.#######.###############
+ #...#.......#.#.......#.#.......#.#.#...#
+ ###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
+ #.#...#.#.#...#.#.#...#...#...#.#.......#
+ #.###.#######.###.###.#.###.###.#.#######
+ #...#.......#.#...#...#.............#...#
+ #.#########.#######.#.#######.#######.###
+ #...#.# F R I Z #.#.#.#
+ #.###.# D E C H #.#.#.#
+ #.#...# #...#.#
+ #.###.# #.###.#
+ #.#....OA WB..#.#..ZH
+ #.###.# #.#.#.#
+CJ......# #.....#
+ ####### #######
+ #.#....CK #......IC
+ #.###.# #.###.#
+ #.....# #...#.#
+ ###.### #.#.#.#
+XF....#.# RF..#.#.#
+ #####.# #######
+ #......CJ NM..#...#
+ ###.#.# #.###.#
+RE....#.# #......RF
+ ###.### X X L #.#.#.#
+ #.....# F Q P #.#.#.#
+ ###.###########.###.#######.#########.###
+ #.....#...#.....#.......#...#.....#.#...#
+ #####.#.###.#######.#######.###.###.#.#.#
+ #.......#.......#.#.#.#.#...#...#...#.#.#
+ #####.###.#####.#.#.#.#.###.###.#.###.###
+ #.......#.....#.#...#...............#...#
+ #############.#.#.###.###################
+ A O F N
+ A A D M
diff --git a/common/hmap_s.c b/common/hmap_s.c
@@ -0,0 +1,48 @@
+#include "hmap_s.h"
+#include "vec.h"
+#include <stdint.h>
+
+uint32_t
+vec2i_hmap_hash(struct hmap_key key)
+{
+ const struct vec2i *v = key.p;
+
+ return (uint32_t) v->x + (uint32_t) v->y * 1337;
+}
+
+bool
+vec2i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ const struct vec2i *v1 = k1.p, *v2 = k2.p;
+
+ return vec2i_eql(v1, v2);
+}
+
+uint32_t
+vec3i_hmap_hash(struct hmap_key key)
+{
+ const struct vec3i *v = key.p;
+
+ return (uint32_t) v->x + (uint32_t) v->y * 1337
+ + (uint32_t) v->z * 1337 * 1337;
+}
+
+bool
+vec3i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ const struct vec3i *v1 = k1.p, *v2 = k2.p;
+
+ return vec3i_eql(v1, v2);
+}
+
+uint32_t
+sizet_hmap_hash(struct hmap_key key)
+{
+ return (uint32_t) key.s * 1737;
+}
+
+bool
+sizet_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ return k1.s == k2.s;
+}
diff --git a/common/hmap_s.h b/common/hmap_s.h
@@ -0,0 +1,10 @@
+#include "hmap.h"
+
+uint32_t vec2i_hmap_hash(struct hmap_key key);
+bool vec2i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
+
+uint32_t vec3i_hmap_hash(struct hmap_key key);
+bool vec3i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
+
+uint32_t sizet_hmap_hash(struct hmap_key key);
+bool sizet_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
diff --git a/common/vec_s.c b/common/vec_s.c
@@ -0,0 +1,8 @@
+#include "vec_s.h"
+
+const struct vec2i adj[] = {
+ { 0, -1 },
+ { 1, 0 },
+ { 0, 1 },
+ { -1, 0 },
+};
diff --git a/common/vec_s.h b/common/vec_s.h
@@ -0,0 +1,10 @@
+#include "vec.h"
+
+enum {
+ ADJ_NORTH,
+ ADJ_EAST,
+ ADJ_SOUTH,
+ ADJ_WEST
+};
+
+extern const struct vec2i adj[4];
