[Advent Of Code 2022] Day 14: Regolith Reservoir [SPOILERS]

Programming
1

Count how many grains fit in a reservoir!

Code: Latest – Get It Done

Once again, I ran into a small bug in my code that took ages to debug. In Python, indentation matters, and I had an else attached to the wrong level.

Indentation Bug 
# What I meant to do:
while can_move and cur.imag < max_y:
    for d in directions:
        if cur + d not in rocks and (cur + d).imag < max_y:
            cur += d
            break
    else:
        can_move = False

# What I did do:
while can_move and cur.imag < max_y:
    for d in directions:
        if cur + d not in rocks and (cur + d).imag < max_y:
            cur += d
            break
        else:
            can_move = False
Python Solver (one function, both parts) 
    def solver(self, rocks: InputType, first_to_the_floor: bool) -> int:
        """Simulate sand filling a reservoir. Return which grain passes the floor or stops falling."""
        # Sand moves in these directions, in this order of preference.
        movement_directions = (complex(0, 1), complex(-1, 1), complex(1, 1))
        starting_point = complex(500, 0)

        # Use the input to build a set of rock points and compute the lowest points.
        rocks_and_sand = set()
        lowest_rock = 0
        for points in rocks:
            lowest_rock = max(lowest_rock, max(p.imag for p in points))
            for start, end in zip(points[:-1], points[1:]):
                for point in aoc.Line.from_complex(start, end).points():
                    rocks_and_sand.add(complex(point))
        # The lowest position a grain may occupy.
        lowest_position = lowest_rock + 1

        # Simulate the grains.
        for grain in itertools.count():
            cur = starting_point
            # Grains can drop until they hit the lowest_position.
            while cur.imag < lowest_position:
                for d in movement_directions:
                    if cur + d not in rocks_and_sand:
                        cur += d
                        break
                else:
                    break
            rocks_and_sand.add(cur)
            if first_to_the_floor and cur.imag == lowest_position:
                # Part 1: return the grain prior to the first to pass the lowest rock.
                return grain
            elif cur == starting_point:
                # Part 2: return the grain which stops at the starting_point.
                return grain + 1
2

I slapped some backtracking logic onto my code for optimizing.

It was three lines of code … and changed the solve time from 88ms/2501ms to 38ms/109ms!

3

Is that else only entered, when the d is empty? Never seen that. Pretty cool.

4

The loop variable, d, is never “empty”.

The for-else is discussed in the break and continue Statements, and else Clauses on Loops section of " More Control Flow Tools":

Loop statements may have an else clause; it is executed when the loop terminates through exhaustion of the iterable (with for) or when the condition becomes false (with while), but not when the loop is terminated by a break statement.

The else block occurs if a break does not occur.

When used with a loop, the else clause has more in common with the else clause of a try statement than it does with that of if statements: a try statement’s else clause runs when no exception occurs, and a loop’s else clause runs when no break occurs. For more on the try statement and exceptions, see Handling Exceptions.

Yes, try-except-else also exists :slight_smile:

try:
    var = some_function()
catch Exception:
    logging.exception("Something happened")
else:
    do_something_with(var)
5

Not terribly happy with my solution, but :person_shrugging:

Ruby Solution 
require 'set'

def parse_cave
  File.readlines('inputs/14.txt', chomp: true).each_with_object(Set.new) do |path, cave|
    path.scan(/(\d+),(\d+)/).map { _1.map(&:to_i) }.each_cons(2).map(&:sort).each do |(from, to)|
      cave.merge(from[0].upto(to[0]).to_a.product(from[1].upto(to[1]).to_a))
    end
  end
end

POUR_POINT = [500, 0].freeze
POUR_DIRECTIONS = [[0, 1], [-1, 1], [1, 1]].freeze

def simulate(end_condition)
  cave = parse_cave
  bottom = cave.map(&:last).max
  num_rocks = cave.size

  while true
    sand = POUR_POINT.dup

    while true
      break if sand[1] == bottom + 1
      break unless POUR_DIRECTIONS.map {|(dx, dy)| [sand[0] + dx, sand[1] + dy] }.find { !cave.include?(_1) }&.tap { sand = _1 }
    end

    cave << sand
    return cave.size - num_rocks if end_condition.call(sand[1] == bottom + 1, sand == POUR_POINT)
  end
end

a = simulate(-> (on_bottom, _on_top) { on_bottom }) - 1
b = simulate(-> (_on_bottom, on_top) { on_top })

require 'minitest/autorun'

describe 'day 14' do
  it 'part a' do assert_equal 692, a end
  it 'part b' do assert_equal 31_706, b end
end