Page Navigation
Problem Intro
We’re told we have stacks of crates that we need to rearrange.
The input data looks something like this:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
I.e. the first part of the input data is the configuration of crates, and the second part is the instructions to move crates between stacks.
Part 1
We’re told our crate moving machine is able to move crates from the top of one stack, to the top of another stack. It can only move one crate at a time.
After the rearrangement procedure completes, what crate ends up on top of each stack?
This is a pretty simple exercise. It’s really just about popping items from a stack, and appending those items to a different stack.
If anything, parsing the original configuration is the toughest part!
First, I read the data and split it into two portions:
with open(INPUT_FILE, mode="rt") as f:
stack_data, instructions = f.read().split("\n\n")
stacks = process_stack_data(stack_data.splitlines())
movements = read_instructions(instructions.splitlines())
Here’s the code that parses the original stack configuration:
def process_stack_data(stack_data: list[str]) -> list[list]:
""" Data looks like...
[D]
[N] [C]
[Z] [M] [P]
1 2 3
Return: [['Z', 'N'], ['M', 'C', 'D'], ['P']]
"""
stack_width = 4
p = re.compile(r"[A-Z]")
# reverse it, so we've got the stack numbers at the top
stack_data = stack_data[::-1]
num_stacks = len(stack_data[0].split())
stacks = [[] for _ in range(num_stacks)] # empty list for each stack
# proces the stacks
for stack_row in stack_data[1:]: # starting at the row of crates
for stack_num in range(num_stacks):
match = p.search(stack_row[stack_num * stack_width:(stack_num+1) * stack_width])
if match:
stacks[stack_num].append(match.group())
return stacks
How does it work?
- First, we define
stack_widthto be 4, since this is the width of a string like"[N] ". - Then we reverse the list that makes up our stack configuration, using the
[::-1]construct. Thus, we now have our stack numbers at the top. - Then we count how many stacks we have. I’ve done this by splitting all the stack numbers wherevre there is white space, and counting how many items are returned.
- Then, using list comprehension I create a list of empty stacks, to hold the crates for each stack.
- Then we iterate through the remaining rows, starting at the first row of crate information.
- For each row, we’ll have data that looks something like
"[Z] [M] [P]". - We iterate through each stack, i.e. 1, 2, 3, etc.
- We multiply the current stack number by the
stack_width, in order to create a slice of the current row that only contains a single crate. - Then we extract this single crate using some simple regex.
- If we’ve found a crate, add it to the current stack. If we haven’t, then there’s no crate in this position, for this stack.
- For each row, we’ll have data that looks something like
Here’s the code that reads the remaining data, i.e. the instructions:
def read_instructions(instructions: list[str]) -> list[tuple[int, int, int]]:
""" Instructions look like: 'move 3 from 8 to 6' """
p = re.compile(r"move (\d+) from (\d+) to (\d+)")
movements = []
for line in instructions:
how_many, from_where, to_where = list(map(int, p.findall(line)[0]))
from_where -= 1 # we need it to be 0-indexed
to_where -= 1 # we need it to be 0-indexed
movements.append((how_many, from_where, to_where))
return movements
- The regex here is pretty simple and doesn’t really need any explanation.
- We’ve also converted all of the digits we’ve read into
int, usingmap(). - Since Python indexes lists starting with 0, but our stack numbers start with 1,
I’m reducing the
from_whereandto_wherestack numbers by 1. - Finally, we append the three numbers - i.e.
how_many,from_where,to_whereto themovementslist, as a tuple.
Now we’ve parsed all the data, it’s time to solve Part 1. Here’s my code:
# Part 1
# make a copy, since we need to reset the stack for Part 2
part1_stack = deepcopy(stacks)
for how_many, from_where, to_where in movements:
# pop items off the end, for how_many times
for _ in range(how_many):
part1_stack[to_where].append(part1_stack[from_where].pop())
stack_message = "".join(a_stack[-1] for a_stack in part1_stack)
print(f"Part 1: {stack_message}")
How does it work?
- We start by making a deep copy of the starting stack configuration. I’m doing this, because we’ll need the original stacks for Part 2 later. So I don’t want to mess with them here!
- Iterate over each instruction, and
popthe last create off the end of thefrom_wherestack, as many times as required. Each item we pop is appended to theto_wherestack.
That’s it!
Finally, we just need to print the value of the top item in each stack, which we can do using a_stack[-1] to reference the last item. Also, I’m using list comprehension here to do this for every stack. This returns a list, which I think convert to a str using the join() method.
Part 2
We’re told that our crate moving machine doesn’t work quite how we thought! This is the CrateMover 9001, and it moves multiple crates at a time. It picks them up in a pile, and moves them to the target stack in the same order that they were lifted.
After the rearrangement procedure completes, what crate ends up on top of each stack?
Here’s my solution code:
# Part 2
for how_many, from_where, to_where in movements:
# slice items off the end and move to the target stack
stacks[to_where].extend(stacks[from_where][-how_many:])
stacks[from_where][-how_many:] = [] # and then delete the items
stack_message = "".join(a_stack[-1] for a_stack in stacks)
print(f"Part 2: {stack_message}")
The only difference here is that rather than popping a crate off the end n times, I’m now slicing multiple crates off the end with each move.
- Note that I’m using
extend()rather thanappend(), because a slice returns a newlist. We want to add the items from that new list, rather than the list itself. - After a slice to get the crates at the end, I set that slice in the
from_wherestack to be empty. This is the technique I’m using to remove those crates.
All done!
Results
The final solution code looks like this:
from copy import deepcopy
from pathlib import Path
import re
import time
SCRIPT_DIR = Path(__file__).parent
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
def main():
with open(INPUT_FILE, mode="rt") as f:
stack_data, instructions = f.read().split("\n\n")
stacks = process_stack_data(stack_data.splitlines())
movements = read_instructions(instructions.splitlines())
# Part 1
# make a copy, since we need to reset the stack for Part 2
part1_stack = deepcopy(stacks)
for how_many, from_where, to_where in movements:
# pop items off the end, for how_many times
for _ in range(how_many):
part1_stack[to_where].append(part1_stack[from_where].pop())
stack_message = "".join(a_stack[-1] for a_stack in part1_stack)
print(f"Part 1: {stack_message}")
# Part 2
for how_many, from_where, to_where in movements:
# slice items off the end and move to the target stack
stacks[to_where].extend(stacks[from_where][-how_many:])
stacks[from_where][-how_many:] = [] # and then delete the items
stack_message = "".join(a_stack[-1] for a_stack in stacks)
print(f"Part 2: {stack_message}")
def process_stack_data(stack_data: list[str]) -> list[list]:
""" Data looks like...
[D]
[N] [C]
[Z] [M] [P]
1 2 3
Return: [['Z', 'N'], ['M', 'C', 'D'], ['P']]
"""
stack_width = 4
p = re.compile(r"[A-Z]")
# reverse it, so we've got the stack numbers at the top
stack_data = stack_data[::-1]
num_stacks = len(stack_data[0].split())
stacks = []
for stack_num in range(num_stacks):
this_stack = []
stacks.append(this_stack)
# proces the stacks
for stack_row in stack_data[1:]: # starting at the row of crates
for stack_num in range(num_stacks):
match = p.search(stack_row[stack_num * stack_width:(stack_num+1) * stack_width])
if match:
stacks[stack_num].append(match.group())
return stacks
def read_instructions(instructions: list[str]) -> list[tuple[int, int, int]]:
""" Instructions look like: 'move 3 from 8 to 6' """
p = re.compile(r"move (\d+) from (\d+) to (\d+)")
movements = []
for line in instructions:
how_many, from_where, to_where = list(map(int, p.findall(line)[0]))
from_where -= 1 # we need it to be 0-indexed
to_where -= 1 # we need it to be 0-indexed
movements.append((how_many, from_where, to_where))
return movements
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
And the output looks like this:
Part 1: JCMHLVGMG
Part 2: LVMRWSSPZ
Execution time: 0.0017 seconds