In [1]:
with open("input/day11.txt", "r") as f:
inputLines = tuple(line.strip() for line in f)
In [2]:
import itertools
import re
In [3]:
floors = {
"first" : 1,
"second" : 2,
"third" : 3,
"fourth" : 4,
}
In [4]:
def parseItem(item):
microchipMatch = re.fullmatch("([a-z]+)-compatible microchip", item)
if microchipMatch is not None:
return microchipMatch.group(1), "M"
generatorMatch = re.fullmatch("([a-z]+) generator", item)
assert generatorMatch is not None
return generatorMatch.group(1), "G"
assert parseItem("hydrogen-compatible microchip") == ("hydrogen", "M")
assert parseItem("lithium generator") == ("lithium", "G")
In [5]:
def parseFloor(line):
m = re.fullmatch("The ([a-z]+) floor contains (.*).", line)
floor, itemsStr = m.groups()
return tuple(sorted(parseItem(item[2:]) + (floors[floor],)
for item in re.split("(?:,\ )?(?:\ ?and\ )?", itemsStr)
if item.startswith("a ")))
assert (parseFloor("The first floor contains a hydrogen-compatible microchip and a lithium generator.") ==
(("hydrogen", "M", 1),
("lithium", "G", 1)))
assert (parseFloor("The second floor contains a hydrogen generator, and a lithium-compatible microchip.") ==
(("hydrogen", "G", 2),
("lithium", "M", 2)))
assert (parseFloor("The second floor contains a hydrogen generator.") ==
(("hydrogen", "G", 2),))
assert (parseFloor("The third floor contains a lithium-compatible microchip.") ==
(("lithium", "M", 3),))
assert (parseFloor("The fourth floor contains nothing relevant.") ==
())
In [6]:
initialItems = tuple(sorted(itertools.chain.from_iterable(parseFloor(line) for line in inputLines)))
print(initialItems)
Our current representation of the positions of the microchips and generators is inefficient. Assuming that there is exactly one microchip and one generator per element, we can make the following simplifications:
((2, 3), (1, 1)) or ((1, 1), (2, 3)).tupleForElement
In [7]:
# Takes an iterable that yields two (element, type, floor) tuples, where
# * the element should be the same for both tuples,
# * the first item should be a generator (type 'G'),
# * the second item should be a microchip (type 'M').
# Returns a tuple that contains only the floors where the generator and the microchip are.
def tupleForElement(items):
result = tuple(floor for element, itemType, floor in items)
assert len(result) == 2
return result
assert tupleForElement((("iron", "G", 3), ("iron", "M", 1))) == (3, 1)
In [8]:
def compressedItems(items):
return tuple(sorted(tupleForElement(itemsForElement)
for _, itemsForElement in itertools.groupby(items, lambda t: t[0])))
assert (compressedItems((("copper", "G", 4), ("copper", "M", 2), ("iron", "G", 1), ("iron", "M", 3)))
== ((1, 3), (4, 2)))
In [9]:
initialState = (1, compressedItems(initialItems))
print(initialState)
In [10]:
def isFinalState(state, targetFloor=4):
currentFloor, items = state
return currentFloor == targetFloor and all(item == (targetFloor, targetFloor) for item in items)
In [11]:
def isValidState(state):
currentFloor, items = state
floorsWithGenerators = set(generatorFloor for generatorFloor, microchipFloor in items)
floorsWithVulnerableMicrochips = set(microchipFloor
for generatorFloor, microchipFloor in items
if generatorFloor != microchipFloor)
return len(floorsWithGenerators & floorsWithVulnerableMicrochips) == 0
assert isValidState((1, ((2, 2), (2, 3), (4, 3), (4, 4))))
assert not isValidState((1, ((2, 2), (2, 3), (4, 2), (4, 4))))
In [12]:
def nextStates(state):
currentFloor, items = state
# Put all item positions into a flat list for easier manipulation
flattenedPositions = tuple(itertools.chain.from_iterable(items))
# Find the index (in flattenedPositions) of all items that are on the current floor
onCurrentFloor = tuple(index
for index, pos in enumerate(flattenedPositions)
if pos == currentFloor)
# Each combination of items that can be moved by the elevator from the current floor is
# represented by a tuple in 'candidatesForMoving'.
# Note that the elevator can take either one or two items.
candidatesForMoving = (tuple((i,) for i in onCurrentFloor) +
tuple(itertools.combinations(onCurrentFloor, 2)))
# Calculate the possible new states for each direction (-1: down, +1: up)
for direction in (-1, 1):
newFloor = currentFloor + direction
if newFloor < 1 or newFloor > 4:
continue
for movedIndices in candidatesForMoving:
# 'movedIndices' is a tuple that contains either one index, or two indices (in the list
# 'flattenedPositions') of the items which are moved by the elevator.
# Find the 'flattenedPositions' for the next state if the items in 'candidate' are moved
# to 'newFloor'.
newFlattenedPositions = tuple(newFloor if index in movedIndices else pos
for index, pos in enumerate(flattenedPositions))
# Convert 'newFlattenedPositions' to the compressed format (see above) by
# * grouping neighboring items to 2-element tuples,
# * sorting the list of these tuples.
newItems = tuple(
sorted(tuple(p for _, p in ps)
for _, ps in itertools.groupby(enumerate(newFlattenedPositions),
lambda x: x[0] // 2)))
newState = (newFloor, newItems)
# Only yield the new state if it is valid.
if isValidState(newState):
yield newState
# If there are two microchips and generators on the first floor initially, the elevator can move
# * both microchips, or
# * both generators, or
# * one microchip, or
# * one microchip and its generator
# to the second floor. Moving one generator without its microchip is not possible because this would
# leave this microchip vulnerable on the first floor.
assert set(nextStates((1, ((1, 1), (1, 1))))) == {(2, ((1, 2), (1, 2))),
(2, ((2, 1), (2, 1))),
(2, ((1, 1), (1, 2))),
(2, ((1, 1), (2, 2)))}
In [13]:
def movesToFinish(initialState):
currentStates = {initialState}
seenStates = {initialState}
for numberOfMoves in itertools.count():
if any(isFinalState(state) for state in currentStates):
return numberOfMoves
currentStates = set(newState
for state in currentStates
for newState in nextStates(state)
if not newState in seenStates)
seenStates |= currentStates
In [14]:
movesToFinish(initialState)
Out[14]:
In [15]:
initialItems2 = compressedItems(initialItems) + ((1, 1), (1, 1))
initialState2 = (1, initialItems2)
In [16]:
movesToFinish(initialState2)
Out[16]: