Advent of Code 2022 - Day 5

Day 5: Supply Stacks

Useful Links

‹›

• 2022 Main Page
• My solution code

Concepts and Packages Demonstrated

regexmaplist comprehensiondeepcopy

Page Navigation

• Problem Intro
• Part 1
• Part 2
• Results

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_width to 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.

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, using map().
• Since Python indexes lists starting with 0, but our stack numbers start with 1, I’m reducing the from_where and to_where stack numbers by 1.
• Finally, we append the three numbers - i.e. how_many, from_where, to_where to the movements list, 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 pop the last create off the end of the from_where stack, as many times as required. Each item we pop is appended to the to_where stack.

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 than append(), because a slice returns a new list. 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_where stack 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

‹›