5 files changed, 500 insertions, 0 deletions
diff --git a/src/18/input b/src/18/input
new file mode 100644
index 0000000..0f62ca5
--- /dev/null
+++ b/src/18/input
@@ -0,0 +1,50 @@
+|...||..|....|..#..|.|..#.|......#|.||.||.|..|....
+.#.....#....#|||#|#..||..|.#..|....#...||.#.#|.|.|
+.|...|#..|||..|.#....#..|.|....|...||...#.#|...|#.
+.........|.|.#||.##.#|.||.|#..||..||...##.##......
+..|.||.#.|.|.|....||#.....|.|.||##.#|##.|....|.#..
+#..#|#..|#...|...#...#....#|##......#..|||#..#.#..
+...#.#.#|...||...|.#...||#.....|##|||.....#.#.#.|.
+.#..|.###|#.|.##......||..#...#.#..|#.|.##.#.#.|..
+..||.|.|.....###...#|...###..##|.#.#....#|..##.|.|
+.##..#.|.#....##...||.|#..#.####..|#..##.|...#....
+..#...#|..|..|.|.#|#.|.|..|..||......#|.|...##..|.
+..||...##|#.....#|..|..|.|.##.|.##.|#|.##|.||...#.
+..|.||......#...#......|......|.##...|..|.|.#...#.
+||#.#|...#.......#......|..|#.#.|.....#...#.|##..|
+.....||.|..|##.#|..#..#|..#|.##....##|.##.||...###
+#|..#..#....|...|.|....#.##...#..|.|..#........|#|
+....#.|.....##.|..##.....##..#.....|#.|.#.|.#.###.
+...###........|.....|..|#..#..|##..###.....#||..||
+#.#...#|..##...|..|||#.....|#|.......#..#.......#|
+#.....||||.#..##.|..|#|.#..|.......|##.|#|#....#.|
+#..##|...|....#.#.#.||.|..|.....#|...|....#|..##|#
+#..|||#..#..|..#|....#.........#...#...#...|.|...#
+.........|.|...#...|...#|##..#.....#.|.#..||.#...#
+.|#...#|...#.###.|#.||.|..#..#.####..#..||.#.#|..|
+.|#....||#|#|.|.|#....##..||.##|....#....#||...|.|
+...|....|...|.||#...#...........#..#....##|.#....|
+....#|#..#....|##...#..|#..#.|......|#........|#..
+.|..#...|..#.|.#....#....#.|...#..|........|..|...
+...##|....||...##...|......|#..|..#..|.........##.
+..##.|.#..........##.|....|##|.....|.#.#.|.....|.#
+#|.|.......#|..#..#.#.|..|.|.#.||#.#...|.#..|.....
+||.#............#...|...#..|#|..||##...#.|#|##|.#|
+..|..||####.|....|##.#.|...|||#..|.|.|.........##.
+...|....|..||.#..##||.|||#..|..#...#.##...||.|..||
+....|...|##...#|.|.|..#|..|#|..##.|....||..|.|.||.
+#..#.......|.#..#..||...#|..#.....#|#..|..|...##..
+#...#..##..|.#...#.....|......###|..|...||.....|..
+#.|..#..|#..|#|..#..||#......|#.......|.#....###..
+#...#||...##|.#.#|####|...|......|.#.#..|#.##...|.
+|.#..#....#..#.....|#..|#.|..##.#..|#|##........||
+#.........##..|....|#.........||..||##...||.|..|.|
+.#....#.......#..|#.|...|....#.#.#........##.##.|.
+.#.#..|.|#..|..#..###...|.#......|.|#.|.##..|.|##.
+..||..|.##.##|...|....#||##....#..#.|#|.|#||#..|..
+.......#|#||.....|.||.|##..|.|....|....|.#...#..|.
+#||##|.||..|##.|..|#.#.|.|....#|.#|.....|||..#.||.
+.||#.|#...||#.#..#..|.|#.....#.#.|#.|...#..#...#..
+#........|..#...|#..###.|.#|...#..#...........#.|#
+.|...#|....||.|...#.|..|.||##.|..#|.#|..|.#....#..
+||....###...#...|||.||..#.|.....||.#|..###..|....#
diff --git a/src/18/part1 b/src/18/part1
new file mode 100644
index 0000000..02322ac
--- /dev/null
+++ b/src/18/part1
@@ -0,0 +1,175 @@
+--- Day 18: Settlers of The North Pole ---
+
+On the outskirts of the North Pole base construction project, many Elves are collecting lumber.
+
+The lumber collection area is 50 acres by 50 acres; each acre can be either [1m[97mopen ground[0m (.),
+[1m[97mtrees[0m (|), or a [1m[97mlumberyard[0m (#). You take a scan of the area (your puzzle input).
+
+Strange magic is at work here: each minute, the landscape looks entirely different. In exactly
+[1m[97mone minute[0m, an open acre can fill with trees, a wooded acre can be converted to a lumberyard, or a
+lumberyard can be cleared to open ground (the lumber having been sent to other projects).
+
+The change to each acre is based entirely on [1m[97mthe contents of that acre[0m as well as [1m[97mthe number of
+open, wooded, or lumberyard acres adjacent to it[0m at the start of each minute. Here, "adjacent" means
+any of the eight acres surrounding that acre. (Acres on the edges of the lumber collection area
+might have fewer than eight adjacent acres; the missing acres aren't counted.)
+
+In particular:
+
+
+ - An [1m[97mopen[0m acre will become filled with [1m[97mtrees[0m if [1m[97mthree or more[0m adjacent acres contained trees.
+Otherwise, nothing happens.
+
+ - An acre filled with [1m[97mtrees[0m will become a [1m[97mlumberyard[0m if [1m[97mthree or more[0m adjacent acres were
+lumberyards. Otherwise, nothing happens.
+
+ - An acre containing a [1m[97mlumberyard[0m will remain a [1m[97mlumberyard[0m if it was adjacent to [1m[97mat least one other
+lumberyard and at least one acre containing trees[0m. Otherwise, it becomes [1m[97mopen[0m.
+
+
+These changes happen across all acres [1m[97msimultaneously[0m, each of them using the state of all acres at
+the beginning of the minute and changing to their new form by the end of that same minute. Changes
+that happen during the minute don't affect each other.
+
+For example, suppose the lumber collection area is instead only 10 by 10 acres with this initial
+configuration:
+
+Initial state:
+.#.#...|#.
+.....#|##|
+.|..|...#.
+..|#.....#
+#.#|||#|#|
+...#.||...
+.|....|...
+||...#|.#|
+|.||||..|.
+...#.|..|.
+
+After 1 minute:
+.......##.
+......|###
+.|..|...#.
+..|#||...#
+..##||.|#|
+...#||||..
+||...|||..
+|||||.||.|
+||||||||||
+....||..|.
+
+After 2 minutes:
+.......#..
+......|#..
+.|.|||....
+..##|||..#
+..###|||#|
+...#|||||.
+|||||||||.
+||||||||||
+||||||||||
+.|||||||||
+
+After 3 minutes:
+.......#..
+....|||#..
+.|.||||...
+..###|||.#
+...##|||#|
+.||##|||||
+||||||||||
+||||||||||
+||||||||||
+||||||||||
+
+After 4 minutes:
+.....|.#..
+...||||#..
+.|.#||||..
+..###||||#
+...###||#|
+|||##|||||
+||||||||||
+||||||||||
+||||||||||
+||||||||||
+
+After 5 minutes:
+....|||#..
+...||||#..
+.|.##||||.
+..####|||#
+.|.###||#|
+|||###||||
+||||||||||
+||||||||||
+||||||||||
+||||||||||
+
+After 6 minutes:
+...||||#..
+...||||#..
+.|.###|||.
+..#.##|||#
+|||#.##|#|
+|||###||||
+||||#|||||
+||||||||||
+||||||||||
+||||||||||
+
+After 7 minutes:
+...||||#..
+..||#|##..
+.|.####||.
+||#..##||#
+||##.##|#|
+|||####|||
+|||###||||
+||||||||||
+||||||||||
+||||||||||
+
+After 8 minutes:
+..||||##..
+..|#####..
+|||#####|.
+||#...##|#
+||##..###|
+||##.###||
+|||####|||
+||||#|||||
+||||||||||
+||||||||||
+
+After 9 minutes:
+..||###...
+.||#####..
+||##...##.
+||#....###
+|##....##|
+||##..###|
+||######||
+|||###||||
+||||||||||
+||||||||||
+
+After 10 minutes:
+.||##.....
+||###.....
+||##......
+|##.....##
+|##.....##
+|##....##|
+||##.####|
+||#####|||
+||||#|||||
+||||||||||
+
+After 10 minutes, there are 37 wooded acres and 31 lumberyards.  Multiplying the number of wooded
+acres by the number of lumberyards gives the total [1m[97mresource value[0m after ten minutes: 37 * 31 =
+[1m[97m1147[0m.
+
+[1m[97mWhat will the total resource value of the lumber collection area be after 10 minutes?[0m
+
+
diff --git a/src/18/part2 b/src/18/part2
new file mode 100644
index 0000000..c37ea49
--- /dev/null
+++ b/src/18/part2
@@ -0,0 +1,184 @@
+--- Part Two ---
+
+You arrive at the vault only to discover that there is not one vault, but [1m[97mfour[0m - each with its own
+entrance.
+
+On your map, find the area in the middle that looks like this:
+
+...
+.@.
+...
+
+Update your map to instead use the correct data:
+
+@#@
+###
+@#@
+
+This change will split your map into four separate sections, each with its own entrance:
+
+#######       #######
+#a.#Cd#       #a.#Cd#
+##...##       ##[1m[97m@#@[0m##
+##.@.##  -->  ##[1m[97m###[0m##
+##...##       ##[1m[97m@#@[0m##
+#cB#Ab#       #cB#Ab#
+#######       #######
+
+Because some of the keys are for doors in other vaults, it would take much too long to collect all
+of the keys by yourself.  Instead, you deploy four remote-controlled robots. Each starts at one of
+the entrances (@).
+
+Your goal is still to [1m[97mcollect all of the keys in the fewest steps[0m, but now, each robot has its own
+position and can move independently.  You can only remotely control a single robot at a time.
+Collecting a key instantly unlocks any corresponding doors, regardless of the vault in which the key
+or door is found.
+
+For example, in the map above, the top-left robot first collects key a, unlocking door A in the
+bottom-right vault:
+
+#######
+#@.#Cd#
+##.#@##
+#######
+##@#@##
+#cB#.b#
+#######
+
+Then, the bottom-right robot collects key b, unlocking door B in the bottom-left vault:
+
+#######
+#@.#Cd#
+##.#@##
+#######
+##@#.##
+#c.#.@#
+#######
+
+Then, the bottom-left robot collects key c:
+
+#######
+#@.#.d#
+##.#@##
+#######
+##.#.##
+#@.#.@#
+#######
+
+Finally, the top-right robot collects key d:
+
+#######
+#@.#.@#
+##.#.##
+#######
+##.#.##
+#@.#.@#
+#######
+
+In this example, it only took [1m[97m8[0m steps to collect all of the keys.
+
+Sometimes, multiple robots might have keys available, or a robot might have to wait for multiple
+keys to be collected:
+
+###############
+#d.ABC.#.....a#
+######@#@######
+###############
+######@#@######
+#b.....#.....c#
+###############
+
+First, the top-right, bottom-left, and bottom-right robots take turns collecting keys a, b, and c, a
+total of 6 + 6 + 6 = 18 steps. Then, the top-left robot can access key d, spending another 6 steps;
+collecting all of the keys here takes a minimum of [1m[97m24[0m steps.
+
+Here's a more complex example:
+
+#############
+#DcBa.#.GhKl#
+#.###@#@#I###
+#e#d#####j#k#
+###C#@#@###J#
+#fEbA.#.FgHi#
+#############
+
+
+ - Top-left robot collects key a.
+
+ - Bottom-left robot collects key b.
+
+ - Top-left robot collects key c.
+
+ - Bottom-left robot collects key d.
+
+ - Top-left robot collects key e.
+
+ - Bottom-left robot collects key f.
+
+ - Bottom-right robot collects key g.
+
+ - Top-right robot collects key h.
+
+ - Bottom-right robot collects key i.
+
+ - Top-right robot collects key j.
+
+ - Bottom-right robot collects key k.
+
+ - Top-right robot collects key l.
+
+
+In the above example, the fewest steps to collect all of the keys is [1m[97m32[0m.
+
+Here's an example with more choices:
+
+#############
+#g#f.D#..h#l#
+#F###e#E###.#
+#dCba@#@BcIJ#
+#############
+#nK.L@#@G...#
+#M###N#H###.#
+#o#m..#i#jk.#
+#############
+
+One solution with the fewest steps is:
+
+
+ - Top-left robot collects key e.
+
+ - Top-right robot collects key h.
+
+ - Bottom-right robot collects key i.
+
+ - Top-left robot collects key a.
+
+ - Top-left robot collects key b.
+
+ - Top-right robot collects key c.
+
+ - Top-left robot collects key d.
+
+ - Top-left robot collects key f.
+
+ - Top-left robot collects key g.
+
+ - Bottom-right robot collects key k.
+
+ - Bottom-right robot collects key j.
+
+ - Top-right robot collects key l.
+
+ - Bottom-left robot collects key n.
+
+ - Bottom-left robot collects key m.
+
+ - Bottom-left robot collects key o.
+
+
+This example requires at least [1m[97m72[0m steps to collect all keys.
+
+After updating your map and using the remote-controlled robots, [1m[97mwhat is the fewest steps necessary
+to collect all of the keys?[0m
+
+
diff --git a/src/18/solve.py b/src/18/solve.py
new file mode 100644
index 0000000..f209429
--- /dev/null
+++ b/src/18/solve.py
@@ -0,0 +1,81 @@
+import sys
+sys.path.append("../common")
+import aoc
+from copy import deepcopy
+from collections import deque
+
+states = (".", "|", "#")
+
+ivals = dict()
+ivals["#"] = 0
+ivals["."] = 0
+ivals["|"] = 0
+
+def pasrse_line(l):
+    return tuple([states.index(c) for c in l])
+
+vmap = [pasrse_line(l) for l in aoc.data.split("\n")]
+xlen, ylen = len(vmap[0]), len(vmap)
+
+def get_at(x, y):
+    if y < 0 or y >= ylen or x < 0 or x >= xlen:
+        return None
+    return vmap[y][x]
+
+def next(x, y):
+    v = vmap[y][x]
+    around = list()
+    [[around.append(get_at(x+i-1, y+j-1)) for j in range(3) if not (i == 1 and j == 1)] for i in range(3)]
+    if v == 0:
+        if len([v for v in around if v == 1]) >= 3:
+            return 1
+    elif v == 1:
+        if len([v for v in around if v == 2]) >= 3:
+            return 2
+    elif v == 2:
+        if len([v for v in around if v == 1]) < 1 or len([v for v in around if v == 2]) < 1:
+            return 0
+    return v
+
+def get_vals():
+    vals = [0 for x in range(3)]
+    for y in range(ylen):
+        for x in range(xlen):
+            vals[vmap[y][x]] += 1
+    return vals
+
+def draw_map(cmap):
+    for y in range(ylen):
+        aoc.debug("".join([str(c) for c in cmap[y]]))
+
+def iterate(n):
+    global vmap
+    for i in range(n):
+        omap = [deque() for y in range(ylen)]
+        for y in range(ylen):
+            for x in range(xlen):
+                omap[y].append(next(x, y))
+        vmap = omap
+
+def get_res():
+    vals = get_vals()
+    return (vals[1] * vals[2])
+
+def solve1(args):
+    iterate(10)
+    vals = get_vals()
+    return vals[1] * vals[2]
+
+def solve2(args):
+    iterate(1000)
+    omap = deepcopy(vmap)
+    counter = 0
+    while True:
+        iterate(1)
+        counter += 1
+        if vmap == omap:
+            break
+
+    return get_res()
+
+aoc.run(solve1, solve2, sols=[574590, 183787])
diff --git a/src/18/test1 b/src/18/test1
new file mode 100644
index 0000000..13d299d
--- /dev/null
+++ b/src/18/test1
@@ -0,0 +1,10 @@
+.#.#...|#.
+.....#|##|
+.|..|...#.
+..|#.....#
+#.#|||#|#|
+...#.||...
+.|....|...
+||...#|.#|
+|.||||..|.
+...#.|..|.