day5

Day 5: Supply Stacks

The elves want to know which crate will end up on top of each stack.

The input is a picture of the crates and a list of crane instructions for moving them. See below.

Note

Crates are moved one at a time.

Example:

Here is the starting position:

example = """
    [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
""".strip("\n")   # Drop leading blank
print(example)

    [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

Okay, this is really two inputs separated by a blank line (\n\n).

• state is in the top, columns 1, 5, 9, …, \(N-1\). Count by 4
• plan or move list is in the bottom, in basically CSV #, from_col, to_col.

Stack 1 has two crates: [N] and [Z]. Stack 2 has 3 crates; stack 3 has 1.

• Step 1: move 1 crate (D) from stack 2 to stack 1.
• Step 2: move 3 crates (DNZ) from 1 to 3 (becoming ZNDP).

Starting Position

# Split so it's like readlines.
start = example.split("\n")
# Confirm the blanks go to the end of row
assert start[0][9] == " "

Code

def get_state(rowdata: list[str]  # Data as if readlines
            )-> list[list[str]]:  # Row-oriented list, top-down
    ncols = len(rowdata[0])
    nrows = rowdata.index("") - 1
    return [[row[i] 
             for i in range(1, ncols, 4)]
            for row in rowdata[:nrows]]

def print_state(state: list[list[str]])-> None:
    """Print a picture of the state. Stacks should be vertical."""
    print("\n".join(" ".join(x) for x in state))
    print(" ".join(f"{i+1}" for i in range(len(state[0]))))

---

source

print_state

 print_state (state:list[list[str]])

Print a picture of the state. Stacks should be vertical.

---

source

get_state

 get_state (rowdata:list[str])

	Type	Details
rowdata	list	Data as if readlines
Returns	list	Row-oriented list, top-down

state = get_state(start)
print_state(state)

  D  
N C  
Z M P
1 2 3

But it became clear I’d want that as actual stacks.

Convert picture to list of stacks, removing blanks. If we kept the blanks this would be a simple .T transpose in numpy, but we want ragged stacks or we will stack crates on air.

Code

from collections import deque

def stackify(state: list[list] # Crate state in visual format
            )-> list[deque]:   # State as list of stacks, no blanks
    """Convert row-oriented input to compact stacks, top=right."""
    nrows, ncols = len(state), len(state[0])
    return [deque([state[row][col] for row in range(nrows-1,-1,-1)
                if state[row][col] != " "])
            for col in range(ncols)]

def print_stacks(stacks: list[deque])-> None:
    """Print a horizontally-oriented picture of stacks"""
    N = max(len(row) for row in stacks)
    pad = ["  "*(N - len(row)) for row in stacks]
    for i, stack in enumerate(stacks):
        print(f"{(i+1)} {' '.join(stack)}{pad[i]}")

---

source

print_stacks

 print_stacks (stacks:list[collections.deque])

Print a horizontally-oriented picture of stacks

---

source

stackify

 stackify (state:list[list])

Convert row-oriented input to compact stacks, top=right.

	Type	Details
state	list	Crate state in visual format
Returns	list	State as list of stacks, no blanks

_ = [[' ', 'D', ' '],
     ['N', 'C', ' '],
     ['Z', 'M', 'P'],
     ['1', '2', '3']]

assert stackify(_) == [deque(['1', 'Z', 'N']), deque(['2', 'M', 'C', 'D']), deque(['3', 'P'])]

stacks = stackify(state)
print_stacks(stacks)

1 Z N  
2 M C D
3 P    

Move List

---

source

print_moves

 print_moves (moves:list[list[int]])

Verbosely print a terse movelist.

---

source

get_moves

 get_moves (rowdata:list[str])

Extract move data from input

	Type	Details
rowdata	list	As from readlines
Returns	list	[[n, from_col, to_col], …

moves = get_moves(start)
print_moves(moves)

Move 1 from 2 to 1
Move 3 from 1 to 3
Move 2 from 2 to 1
Move 1 from 1 to 2

What is it to do a move? Line 1 moves the top crate D from stack 2 to stack 1. Iterated on these with some REPL. Quickly became clear I wanted state to be stacks so made a quick change to rotate the lists 90º and use deque. (Really could just use lists.)

Note the -1 to correct for 0-indexing. Would be nicer to include a hidden stack 0 so we don’t need that. Later.

Code

def move(
    n:    int|str,     # Move this many
    from_col: int|str, # From this stack
    to_col:   int|str, # To this stack
    pos:  list,        # Position -> Will be CHANGED!
    )-> None:
    """Move `n` crates from `from_col` to `to_col`. Modifies in place."""
    n, from_col, to_col = int(n), int(from_col), int(to_col)
    for i in range(n):
        move1box(pos[from_col - 1], pos[to_col - 1])

def move1box(
    from_stack: deque, # From this stack
    to_stack:   deque, # To this stack
    )-> None:          # Modifies in place
    """Move 1 crates from `from_stack` to `to_stack`."""
    to_stack.append(from_stack.pop())

---

source

move1box

 move1box (from_stack:collections.deque, to_stack:collections.deque)

Move 1 crates from from_stack to to_stack.

	Type	Details
from_stack	deque	From this stack
to_stack	deque	To this stack
Returns	None	Modifies in place

---

source

move

 move (n:int|str, from_col:int|str, to_col:int|str, pos:list)

Move n crates from from_col to to_col. Modifies in place.

	Type	Details
n	int | str	Move this many
from_col	int | str	From this stack
to_col	int | str	To this stack
pos	list	Position -> Will be CHANGED!
Returns	None

Note

Took about 45min to get to this point with the first versions of move and move1box, then had to stop for work. Given how straightforward this is, I’m suprised how long it takes me - documenting, thinking, little iterations & tests.

stacks = stackify(state)
move(2, 1, 2, stacks)
stacks

[deque([]), deque(['M', 'C', 'D', 'N', 'Z']), deque(['P'])]

Solve Example

After Step 1:

Should be

step1 = """
[D]        
[N] [C]    
[Z] [M] [P]
 1   2   3 
 """

stacks = stackify(state)
move(*moves[0], stacks)
print_stacks(stacks)

1 Z N D
2 M C  
3 P    

After Step 2:

step2 = """
        [Z]
        [N]
    [C] [D]
    [M] [P]
 1   2   3
 """

move(*moves[1], stacks)
print_stacks(stacks)

1         
2 M C    
3 P D N Z

After Step 3:

step3 = """
        [Z]
        [N]
[M]     [D]
[C]     [P]
 1   2   3
 """

move(*moves[2], stacks)
print_stacks(stacks)

1 C M    
2         
3 P D N Z

End, after Step 4:

step4 = """
        [Z]
        [N]
        [D]
[C] [M] [P]
 1   2   3
 """

move(*moves[3], stacks)
print_stacks(stacks)

1 C      
2 M      
3 P D N Z

Crates on top are: [C] [M] [Z].

Answer would be CMZ.

Code

def top_crates(stacks: list[deque]  # List of stacks
              )-> str:              # Crates on top
    """Find the crates on top of each stack"""
    return "".join(stack[-1] for stack in stacks)

---

source

top_crates

 top_crates (stacks:list[collections.deque])

Find the crates on top of each stack

	Type	Details
stacks	list	List of stacks
Returns	str	Crates on top

Test that

assert top_crates(stacks) == "CMZ"

Part 1

Get the data

with open("data/day5_input.txt") as f:
    data = [x.strip() for x in f.readlines()]
data[:3]

['[B]                     [N]     [H]',
 '[V]         [P] [T]     [V]     [P]',
 '[W]     [C] [T] [S]     [H]     [N]']

Run

stacks = stackify(get_state(data))
for _ in get_moves(data):
    move(*_, stacks)
top_crates(stacks)

'PSNRGBTFT'

Part 2

Warning

Oops! This crane can pick up all the boxen at once! It doesn’t have to go one at a time.

Write a moveall, rerun, and say what the top crates will be.

Don’t want to rewrite the parsing, so popping to a temp stack should work. Let’s try:

d = deque([3,4,5,6])
e = deque([1])
for x in reversed([d.pop() for i in range(3)]):
    e.append(x)
e

deque([1, 4, 5, 6])

Okay, implement that.

Code

def moveall(
    n:    int|str,     # Move this many
    from_col: int|str, # From this stack
    to_col:   int|str, # To this stack
    pos:  list,        # Position -> Will be CHANGED!
    )-> None:
    """Move `n` crates from `from_col` to `to_col` AS A GROUP."""
    n, from_col, to_col = int(n), int(from_col), int(to_col)
    old, new = pos[from_col - 1], pos[to_col - 1]
    for x in reversed([old.pop() for i in range(n)]):
        new.append(x)

---

source

moveall

 moveall (n:int|str, from_col:int|str, to_col:int|str, pos:list)

Move n crates from from_col to to_col AS A GROUP.

	Type	Details
n	int | str	Move this many
from_col	int | str	From this stack
to_col	int | str	To this stack
pos	list	Position -> Will be CHANGED!
Returns	None

Run

stacks = stackify(get_state(data))
for _ in get_moves(data):
    moveall(*_, stacks)
top_crates(stacks)

'BNTZFPMMW'