Reorder days into src

10 files changed, 705 insertions, 0 deletions

diff --git a/src/15/input b/src/15/input
new file mode 100644
index 0000000..c6ec342
--- /dev/null
+++ b/src/15/input
@@ -0,0 +1,32 @@
+################################

+###############.##...###########

+##############..#...G.#..#######

+##############.............#####

+###############....G....G......#

+##########..........#..........#

+##########................##..##

+######...##..G...G.......####..#

+####..G..#G...............####.#

+#######......G....G.....G#####E#

+#######.................E.######

+########..G...............######

+######....G...#####E...G....####

+######..G..G.#######........####

+###.........#########.......E.##

+###..#..#...#########...E.....##

+######......#########.......####

+#####...G...#########.....######

+#####G......#########.....######

+#...#G..G....#######......######

+###...##......#####.......######

+####..##..G........E...E..######

+#####.####.....######...########

+###########..#...####...E.######

+###############...####..#...####

+###############...###...#.E.####

+#####################.#E....####

+#####################.#...######

+###################...##.#######

+##################..############

+##################...###########

+################################

diff --git a/src/15/part1 b/src/15/part1
new file mode 100644
index 0000000..34c087d
--- /dev/null
+++ b/src/15/part1
@@ -0,0 +1,343 @@
+--- Day 15: Beverage Bandits ---
+
+Having perfected their hot chocolate, the Elves have a new problem: the Goblins that live in these
+caves will do anything to steal it. Looks like they're here for a fight.
+
+You scan the area, generating a map of the walls (#), open cavern (.), and starting position of
+every Goblin (G) and Elf (E) (your puzzle input).
+
+Combat proceeds in rounds; in each round, each unit that is still alive takes a turn, resolving all
+of its actions before the next unit's turn begins. On each unit's turn, it tries to
+move into range of an enemy (if it isn't already) and then attack (if it is in range).
+
+All units are very disciplined and always follow very strict combat rules. Units never move or
+attack diagonally, as doing so would be dishonorable. When multiple choices are equally valid, ties
+are broken in reading order: top-to-bottom, then left-to-right.  For instance, the order in which
+units take their turns within a round is the reading order of their starting positions in that
+round, regardless of the type of unit or whether other units have moved after the round started. 
+For example:
+
+                 would take their
+These units:   turns in this order:
+  #######           #######
+  #.G.E.#           #.1.2.#
+  #E.G.E#           #3.4.5#
+  #.G.E.#           #.6.7.#
+  #######           #######
+
+Each unit begins its turn by identifying all possible targets (enemy units). If no targets remain,
+combat ends.
+
+Then, the unit identifies all of the open squares (.) that are in range of each target; these are
+the squares which are adjacent (immediately up, down, left, or right) to any target and which aren't
+already occupied by a wall or another unit. Alternatively, the unit might already be in range of a
+target. If the unit is not already in range of a target, and there are no open squares which are in
+range of a target, the unit ends its turn.
+
+If the unit is already in range of a target, it does not move, but continues its turn with an
+attack. Otherwise, since it is not in range of a target, it moves.
+
+To move, the unit first considers the squares that are in range and determines which of those
+squares it could reach in the fewest steps. A step is a single movement to any adjacent (immediately
+up, down, left, or right) open (.) square. Units cannot move into walls or other units. The unit
+does this while considering the current positions of units and does not do any prediction about
+where units will be later. If the unit cannot reach (find an open path to) any of the squares that
+are in range, it ends its turn. If multiple squares are in range and tied for being reachable in the
+fewest steps, the square which is first in reading order is chosen. For example:
+
+Targets:      In range:     Reachable:    Nearest:      Chosen:
+#######       #######       #######       #######       #######
+#E..G.#       #E.?G?#       #E.@G.#       #E.!G.#       #E.+G.#
+#...#.#  -->  #.?.#?#  -->  #.@.#.#  -->  #.!.#.#  -->  #...#.#
+#.G.#G#       #?G?#G#       #@G@#G#       #!G.#G#       #.G.#G#
+#######       #######       #######       #######       #######
+
+In the above scenario, the Elf has three targets (the three Goblins):
+
+
+ - Each of the Goblins has open, adjacent squares which are in range (marked with a ? on the map).
+
+ - Of those squares, four are reachable (marked @); the other two (on the right) would require
+moving through a wall or unit to reach.
+
+ - Three of these reachable squares are nearest, requiring the fewest steps (only 2) to reach
+(marked !).
+
+ - Of those, the square which is first in reading order is chosen (+).
+
+
+The unit then takes a single step toward the chosen square along the shortest path to that square.
+If multiple steps would put the unit equally closer to its destination, the unit chooses the step
+which is first in reading order. (This requires knowing when there is more than one shortest
+path so that you can consider the first step of each such path.) For example:
+
+In range:     Nearest:      Chosen:       Distance:     Step:
+#######       #######       #######       #######       #######
+#.E...#       #.E...#       #.E...#       #4E212#       #..E..#
+#...?.#  -->  #...!.#  -->  #...+.#  -->  #32101#  -->  #.....#
+#..?G?#       #..!G.#       #...G.#       #432G2#       #...G.#
+#######       #######       #######       #######       #######
+
+The Elf sees three squares in range of a target (?), two of which are nearest (!), and so the first
+in reading order is chosen (+). Under "Distance", each open square is marked with its distance from
+the destination square; the two squares to which the Elf could move on this turn (down and to the
+right) are both equally good moves and would leave the Elf 2 steps from being in range of the
+Goblin. Because the step which is first in reading order is chosen, the Elf moves right one square.
+
+Here's a larger example of movement:
+
+Initially:
+#########
+#G..G..G#
+#.......#
+#.......#
+#G..E..G#
+#.......#
+#.......#
+#G..G..G#
+#########
+
+After 1 round:
+#########
+#.G...G.#
+#...G...#
+#...E..G#
+#.G.....#
+#.......#
+#G..G..G#
+#.......#
+#########
+
+After 2 rounds:
+#########
+#..G.G..#
+#...G...#
+#.G.E.G.#
+#.......#
+#G..G..G#
+#.......#
+#.......#
+#########
+
+After 3 rounds:
+#########
+#.......#
+#..GGG..#
+#..GEG..#
+#G..G...#
+#......G#
+#.......#
+#.......#
+#########
+
+Once the Goblins and Elf reach the positions above, they all are either in range of a target or
+cannot find any square in range of a target, and so none of the units can move until a unit dies.
+
+After moving (or if the unit began its turn in range of a target), the unit attacks.
+
+To attack, the unit first determines all of the targets that are in range of it by being immediately
+adjacent to it. If there are no such targets, the unit ends its turn. Otherwise, the adjacent target
+with the fewest hit points is selected; in a tie, the adjacent target with the fewest hit points
+which is first in reading order is selected.
+
+The unit deals damage equal to its attack power to the selected target, reducing its hit points by
+that amount. If this reduces its hit points to 0 or fewer, the selected target dies: its square
+becomes . and it takes no further turns.
+
+Each unit, either Goblin or Elf, has 3 attack power and starts with 200 hit points.
+
+For example, suppose the only Elf is about to attack:
+
+       HP:            HP:
+G....  9       G....  9  
+..G..  4       ..G..  4  
+..EG.  2  -->  ..E..     
+..G..  2       ..G..  2  
+...G.  1       ...G.  1  
+
+The "HP" column shows the hit points of the Goblin to the left in the corresponding row. The Elf is
+in range of three targets: the Goblin above it (with 4 hit points), the Goblin to its right (with 2
+hit points), and the Goblin below it (also with 2 hit points). Because three targets are in range,
+the ones with the lowest hit points are selected: the two Goblins with 2 hit points each (one to the
+right of the Elf and one below the Elf). Of those, the Goblin first in reading order (the one to the
+right of the Elf) is selected. The selected Goblin's hit points (2) are reduced by the Elf's attack
+power (3), reducing its hit points to -1, killing it.
+
+After attacking, the unit's turn ends.  Regardless of how the unit's turn ends, the next unit in the
+round takes its turn.  If all units have taken turns in this round, the round ends, and a new round
+begins.
+
+The Elves look quite outnumbered.  You need to determine the outcome of the battle: the
+number of full rounds that were completed (not counting the round in which combat ends) multiplied
+by the sum of the hit points of all remaining units at the moment combat ends. (Combat only ends
+when a unit finds no targets during its turn.)
+
+Below is an entire sample combat. Next to each map, each row's units' hit points are listed from
+left to right.
+
+Initially:
+#######   
+#.G...#   G(200)
+#...EG#   E(200), G(200)
+#.#.#G#   G(200)
+#..G#E#   G(200), E(200)
+#.....#   
+#######   
+
+After 1 round:
+#######   
+#..G..#   G(200)
+#...EG#   E(197), G(197)
+#.#G#G#   G(200), G(197)
+#...#E#   E(197)
+#.....#   
+#######   
+
+After 2 rounds:
+#######   
+#...G.#   G(200)
+#..GEG#   G(200), E(188), G(194)
+#.#.#G#   G(194)
+#...#E#   E(194)
+#.....#   
+#######   
+
+Combat ensues; eventually, the top Elf dies:
+
+After 23 rounds:
+#######   
+#...G.#   G(200)
+#..G.G#   G(200), G(131)
+#.#.#G#   G(131)
+#...#E#   E(131)
+#.....#   
+#######   
+
+After 24 rounds:
+#######   
+#..G..#   G(200)
+#...G.#   G(131)
+#.#G#G#   G(200), G(128)
+#...#E#   E(128)
+#.....#   
+#######   
+
+After 25 rounds:
+#######   
+#.G...#   G(200)
+#..G..#   G(131)
+#.#.#G#   G(125)
+#..G#E#   G(200), E(125)
+#.....#   
+#######   
+
+After 26 rounds:
+#######   
+#G....#   G(200)
+#.G...#   G(131)
+#.#.#G#   G(122)
+#...#E#   E(122)
+#..G..#   G(200)
+#######   
+
+After 27 rounds:
+#######   
+#G....#   G(200)
+#.G...#   G(131)
+#.#.#G#   G(119)
+#...#E#   E(119)
+#...G.#   G(200)
+#######   
+
+After 28 rounds:
+#######   
+#G....#   G(200)
+#.G...#   G(131)
+#.#.#G#   G(116)
+#...#E#   E(113)
+#....G#   G(200)
+#######   
+
+More combat ensues; eventually, the bottom Elf dies:
+
+After 47 rounds:
+#######   
+#G....#   G(200)
+#.G...#   G(131)
+#.#.#G#   G(59)
+#...#.#   
+#....G#   G(200)
+#######   
+
+Before the 48th round can finish, the top-left Goblin finds that there are no targets remaining, and
+so combat ends. So, the number of full rounds that were completed is 47, and the sum of the hit
+points of all remaining units is 200+131+59+200 = 590. From these, the outcome of the battle is 47 *
+590 = 27730.
+
+Here are a few example summarized combats:
+
+#######       #######
+#G..#E#       #...#E#   E(200)
+#E#E.E#       #E#...#   E(197)
+#G.##.#  -->  #.E##.#   E(185)
+#...#E#       #E..#E#   E(200), E(200)
+#...E.#       #.....#
+#######       #######
+
+Combat ends after 37 full rounds
+Elves win with 982 total hit points left
+Outcome: 37 * 982 = 36334
+
+#######       #######   
+#E..EG#       #.E.E.#   E(164), E(197)
+#.#G.E#       #.#E..#   E(200)
+#E.##E#  -->  #E.##.#   E(98)
+#G..#.#       #.E.#.#   E(200)
+#..E#.#       #...#.#   
+#######       #######   
+
+Combat ends after 46 full rounds
+Elves win with 859 total hit points left
+Outcome: 46 * 859 = 39514
+
+#######       #######   
+#E.G#.#       #G.G#.#   G(200), G(98)
+#.#G..#       #.#G..#   G(200)
+#G.#.G#  -->  #..#..#   
+#G..#.#       #...#G#   G(95)
+#...E.#       #...G.#   G(200)
+#######       #######   
+
+Combat ends after 35 full rounds
+Goblins win with 793 total hit points left
+Outcome: 35 * 793 = 27755
+
+#######       #######   
+#.E...#       #.....#   
+#.#..G#       #.#G..#   G(200)
+#.###.#  -->  #.###.#   
+#E#G#G#       #.#.#.#   
+#...#G#       #G.G#G#   G(98), G(38), G(200)
+#######       #######   
+
+Combat ends after 54 full rounds
+Goblins win with 536 total hit points left
+Outcome: 54 * 536 = 28944
+
+#########       #########   
+#G......#       #.G.....#   G(137)
+#.E.#...#       #G.G#...#   G(200), G(200)
+#..##..G#       #.G##...#   G(200)
+#...##..#  -->  #...##..#   
+#...#...#       #.G.#...#   G(200)
+#.G...G.#       #.......#   
+#.....G.#       #.......#   
+#########       #########   
+
+Combat ends after 20 full rounds
+Goblins win with 937 total hit points left
+Outcome: 20 * 937 = 18740
+
+What is the outcome of the combat described in your puzzle input?
+
+
diff --git a/src/15/part2 b/src/15/part2
new file mode 100644
index 0000000..749d947
--- /dev/null
+++ b/src/15/part2
@@ -0,0 +1,57 @@
+--- Part Two ---
+
+You quickly repair the oxygen system; oxygen gradually fills the area.
+
+Oxygen starts in the location containing the repaired oxygen system. It takes one minute for oxygen
+to spread to all open locations that are adjacent to a location that already contains oxygen.
+Diagonal locations are not adjacent.
+
+In the example above, suppose you've used the droid to explore the area fully and have the following
+map (where locations that currently contain oxygen are marked O):
+
+ ##   
+#..## 
+#.#..#
+#.O.# 
+ ###  
+
+Initially, the only location which contains oxygen is the location of the repaired oxygen system. 
+However, after one minute, the oxygen spreads to all open (.) locations that are adjacent to a
+location containing oxygen:
+
+ ##   
+#..## 
+#.#..#
+#OOO# 
+ ###  
+
+After a total of two minutes, the map looks like this:
+
+ ##   
+#..## 
+#O#O.#
+#OOO# 
+ ###  
+
+After a total of three minutes:
+
+ ##   
+#O.## 
+#O#OO#
+#OOO# 
+ ###  
+
+And finally, the whole region is full of oxygen after a total of four minutes:
+
+ ##   
+#OO## 
+#O#OO#
+#OOO# 
+ ###  
+
+So, in this example, all locations contain oxygen after 4 minutes.
+
+Use the repair droid to get a complete map of the area. How many minutes will it take to fill with
+oxygen?
+
+
diff --git a/src/15/solve.py b/src/15/solve.py
new file mode 100644
index 0000000..cc16c9d
--- /dev/null
+++ b/src/15/solve.py
@@ -0,0 +1,229 @@
+import sys

+sys.path.append("../common")

+import aoc

+

+data = aoc.data.split("\n")

+actors = list()

+

+def parse_entity(x, y):

+    global actors

+    c = data[y][x]

+    if c == "#":

+        return 1

+    else:

+        if c == "G":

+            actors.append([x, y, 200, 1, len(actors), 3])

+        elif c == "E":

+            actors.append([x, y, 200, 0, len(actors), 3])

+        return 0

+

+ylen = len(data)

+xlen = len(data[0])

+

+adjacent = [[0, -1], [-1, 0], [1, 0], [0, 1]] # first in reading order

+vmap = list()

+

+def set_game():

+    global vmap, actors

+    actors = list()

+    vmap = [[parse_entity(x, y) for x in range(xlen)] for y in range(ylen)]

+

+

+def inmap(cmap, cx, cy):

+    for i in range(len(cmap)):

+        ent = cmap[i]

+        if ent[0] == cx and ent[1] == cy:

+            return i

+    return None

+

+def iswall(x,y):

+    return vmap[y][x] != 0

+

+def isblocked(x, y):

+    return (vmap[y][x] != 0 or inmap(actors, x, y) != None)

+

+def freeAdjacent(x, y):

+    poslist = list()

+    for dir in adjacent:

+        nx = x + dir[0]

+        ny = y + dir[1]

+        if not isblocked(nx, ny):

+            poslist.append((nx,ny))

+    return poslist

+

+def flatten(l):

+    flat = list()

+    for ll in l:

+        flat += ll

+    return flat

+

+def drawMap():

+    global actors

+

+    for y in range(ylen):

+        for x in range(xlen):

+            ind = inmap(actors, x, y)

+            aoc.debug(("G" if actors[ind][3] == 1 else "E") \

+                if ind != None else ("." if vmap[y][x] == 0 else "#"), end="")

+        aoc.debug()

+

+def getSteps(cmap, a1):

+    # adjacent squares

+    npos = [[a1[0] + dir[0], a1[1] + dir[1]] for dir in adjacent]

+

+    # pos of enemy and distance

+    steps = [[np[0], np[1], cmap[np[0], np[1]]] for np in npos if (np[0], np[1]) in cmap]

+

+    return steps

+

+def closestStep(a1, a2):

+    countmap = dict()

+    next = dict()

+    next[(a2[0], a2[1])] = 0

+    counter = 0

+    steps = list()

+    while len(next) > 0 and len(steps) == 0: # first steps available will be shortest

+        countmap = {**countmap, **next} # merge dictionaries

+        counter += 1

+        temp = dict()

+        for n in next:

+            for dir in adjacent:

+                nx = n[0]+dir[0]

+                ny = n[1]+dir[1]

+                if not isblocked(nx, ny) and (nx, ny) not in countmap and (nx, ny) not in temp:

+                    temp[(nx,ny)] = counter

+        next = temp

+        steps = getSteps(countmap, a1)

+

+    # if reachable

+    if len(steps) != 0:

+        return sorted(steps, key = lambda x : (x[1], x[0]))[0]

+    else:

+        return [None]

+

+def move(a):

+    global actors

+

+    # best steps from enemies

+    steps = [[na[0], na[1]] + closestStep(a, na) for na in actors if na[3] != a[3]]

+

+    # only where step is possible

+    steps = [s for s in steps if s[2] != None]

+

+    # skip when none possible

+    if len(steps) == 0:

+        return

+

+    # best move

+    bestmove = sorted(steps, key = lambda x : (x[4], x[1], x[0]))[0]

+    a[0] = bestmove[2]

+    a[1] = bestmove[3]

+

+def getInrange(a):

+    global actors

+

+    inrange = list()

+    for dir in adjacent:

+        nx = a[0] + dir[0]

+        ny = a[1] + dir[1]

+        ind = inmap(actors, nx, ny)

+        if ind != None and actors[ind][3] != a[3]:

+            inrange.append(ind)

+    return inrange

+

+def next_tick(tick):

+    global actors

+

+    actors = sorted(actors, key=lambda x: (x[1], x[0]), reverse=True)

+    i = len(actors)-1

+

+    while i >= 0:

+        a = actors[i]

+        inrange = getInrange(a) # get enemies in range

+        if len(inrange) == 0:

+            move(a)

+            inrange = getInrange(a)

+

+        if len(inrange) != 0:

+            inrange = [actors[ai] + [ai] for ai in inrange]

+

+            # lowest health in reading order

+            cai = sorted(inrange, key = lambda x : (x[2], x[1], x[0]))[0][-1]

+

+            # attack player

+            actors[cai][2] -= a[5] # attack

+            if actors[cai][2] <= 0:

+                actors.pop(cai) # dead

+                aoc.debug("death -",cai)

+                if min_alive() == 0 and i != 0: # incomplete round

+                    return False

+                if cai < i: i -= 1

+

+        if aoc.debug_lvl and False:

+            aoc.debug()

+            aoc.debug("small step -",a[4])

+            drawMap()

+            status_report()

+        i -= 1

+

+    if aoc.debug_lvl:

+        aoc.debug()

+        aoc.debug("tick:", tick)

+        drawMap()

+        status_report()

+    else:

+        aoc.debug(tick)

+

+    return True

+

+def min_alive():

+    alive = [0,0]

+    for a in actors:

+        alive[1 * (a[3] == 0)] += 1

+    return min(alive)

+

+def sum_hp():

+    return sum(a[2] for a in actors)

+

+def status_report():

+    global actors

+

+    sactors = sorted(actors, key = lambda x:x[4])

+    for a in sactors:

+        aoc.debug("HP:", a[2])

+    aoc.debug()

+

+def elves_alive():

+    return len([a for a in actors if a[3] == 0])

+

+def start_battle(eap):

+    global actors

+

+    set_game()

+    for a in actors:

+        if a[3] == 0:

+            a[5] = eap

+

+    elfcount = elves_alive()

+

+    ticks = 0

+    while min_alive() > 0:

+        if next_tick(ticks):

+            ticks += 1

+    status_report()

+

+    return ((sum_hp() * ticks), (elfcount - elves_alive()))

+

+def solve1(args):

+    res = start_battle(3)

+    return res[0]

+

+def solve2(args):

+    eap = 4

+    res = start_battle(eap)

+    while res[1] != 0:

+        eap += 1

+        res = start_battle(eap)

+    return res[0]

+

+aoc.run(solve1, solve2, sols=[229798, 52972])

diff --git a/src/15/test1 b/src/15/test1
new file mode 100644
index 0000000..ac399d6
--- /dev/null
+++ b/src/15/test1
@@ -0,0 +1,7 @@
+#######
+#G..#E#
+#E#E.E#
+#G.##.#
+#...#E#
+#...E.#
+#######
diff --git a/src/15/test2 b/src/15/test2
new file mode 100644
index 0000000..58f778d
--- /dev/null
+++ b/src/15/test2
@@ -0,0 +1,7 @@
+#######
+#E..EG#
+#.#G.E#
+#E.##E#
+#G..#.#
+#..E#.#
+#######
diff --git a/src/15/test3 b/src/15/test3
new file mode 100644
index 0000000..6dc1c08
--- /dev/null
+++ b/src/15/test3
@@ -0,0 +1,7 @@
+#######
+#E.G#.#
+#.#G..#
+#G.#.G#
+#G..#.#
+#...E.#
+#######
diff --git a/src/15/test4 b/src/15/test4
new file mode 100644
index 0000000..2343d7b
--- /dev/null
+++ b/src/15/test4
@@ -0,0 +1,7 @@
+#######
+#.E...#
+#.#..G#
+#.###.#
+#E#G#G#
+#...#G#
+#######
diff --git a/src/15/test5 b/src/15/test5
new file mode 100644
index 0000000..95882b2
--- /dev/null
+++ b/src/15/test5
@@ -0,0 +1,9 @@
+#########
+#G......#
+#.E.#...#
+#..##..G#
+#...##..#
+#...#...#
+#.G...G.#
+#.....G.#
+#########
diff --git a/src/15/test6 b/src/15/test6
new file mode 100644
index 0000000..291d351
--- /dev/null
+++ b/src/15/test6
@@ -0,0 +1,7 @@
+#######
+#.G...#
+#...EG#
+#.#.#G#
+#..G#E#
+#.....#
+#######