aoc-2022-09.py

# We read the data as just an array of words. No need for line-by-line, although
# that is fine as well.

def test_data_09():
    return open("data/09.1.txt").read().split()

def real_data_09():
    return open("data/09.txt").read().split()

D = test_data_09()
print('Test 1')
print('  ', D)

# It will help to have a long sequence of individual instructions.
# That is, "RRRR" is more useful to us than "R 4".

def direction_sequence(instructions):
    "['R', '3', 'D', '2'] --> R, R, R, D, D (sequence of string)"
    i = 0
    while i < len(instructions):
        letter, n = instructions[i:i+2]
        n = int(n)
        for _ in range(n):
            yield letter
        i = i + 2

print('Test 2')
print('  ', list(direction_sequence(D)))

# Given the positions (x,y) of H' and T, we need to calculate where T' will be.
# Nomenclature: H and T are the original positions of the two objects, and H' and T'
# are the updated positions.
# H -> H' by following an instruction (RLUD).
# T -> T' by calculating a new position.
#
# To calculate the new position we assume the two are never separated by more than
# two units in any direction. By considering absolute difference and using an "average"
# approach, we only have to consider a few cases.

def new_T_pos(Hdash, T):
    "Calculate the position T' based on H' and T."
    hx, hy = Hdash
    tx, ty = T
    diffx = abs(hx - tx)
    diffy = abs(hy - ty)
    if diffx <= 1 and diffy <= 1:
        # T and H' are close enough that T' does not need to move.
        return T
    elif diffx == 2 and diffy == 2:
        # I think this should never happen. Make it abundantly clear if it does.
        raise Exception("H and T' further apart than anticipated")
    elif diffx == 2:
        # T needs to move closer in the X direction _and_ will either be in the same
        # Y position already or will move one step up or down.
        return ((hx+tx)//2, hy)
    elif diffy == 2:
        # T needs to move closer in the Y direction _and_ will either be in the same
        # X position already or will move one step left or right.
        return (hx, (hy+ty)//2)
    else:
        raise Exception("Unhandled case in calculating T' position")

print('Test 3')
print('   At the moment we are just hoping new_T_pos() works')

# We will use a concept from functional programming called _reduce_. Here is a
# way to calculate the product of a list of numbers -- reducing the list to a
# single number.
#
#   reduce 1, (lambda acc,x: acc * x), [4,2,8,7,9]       --> 4032
#
# In real Python, parentheses would be used around the three arguments, of
# course. They are omitted here for clarity.
#
# The first argument (1) is the starting value that is fed into the
# calculation.
#
# The second argument (the lambda) is a function of two parameters: the
# accumulator (which is the current value of the calculation) and a value from
# the list. The result of the function is the new accumulator.
#
# The third argument is of course the collection of numbers whose product we
# want.
#
# The _reduce_ code above is short for
#
#   acc = 1
#   for x in [4,2,8,7,9]:
#     acc = acc * x
#   acc
#
# For our head-tail problem, our starting value is the position of H and T,
# both of which are (0,0). The function is ... well, it hasn't been defined
# yet. So we need a function that takes the current state (the position of H
# and T) and a direction (RLUD) and returns the new state.
#
# Then we can call (pseudo-Python):
#
#   reduce ((0,0), (0,0)), update, direction_sequence
#
# and we will have calculated the final state.
#
# There are only two problems:
#  (1) reduce does not exist in Python. We can import it, but here we will just
#      make it ourselves.
#  (2) reduce will give us only the final state. That's fine if we just need to
#      answer "Where does H end up?" or similar, but in our case, we need to
#      know everywhere that the tail has been. The solution to this is
#      _reductions_, a variant of reduce that gives you all of the intermediate
#      states, not just the last one.

def reduce(init, f, coll):
    acc = init
    for x in coll:
        acc = f(acc, x)
    return acc

print('Test 4a')
print('   Product of [2,6,5,7,3] is', reduce(1, lambda acc,x: acc*x, [2,6,5,7,3]))

def reductions(init, f, coll):
    acc = init
    yield acc
    for x in coll:
        acc = f(acc, x)
        yield acc
    # No return value - the caller must consume all the states that were yielded

print('Test 4b')
print('   Intermediate products of [2,6,5,7,3] are', list(reductions(1, lambda acc,x: acc*x, [2,6,5,7,3])))

# OK, we are now ready to write our update function.
# Remember that the _state_ is simply the H and T values. We will place them in
# a dictionary for clarity.

DELTAS = { 'U': (0,1), 'D': (0,-1), 'L': (-1,0), 'R': (1,0)}

def update(state, direction):
    def new_H_pos():
        hx, hy = H
        dx, dy = DELTAS[direction]
        return (hx+dx, hy+dy)

    H = state['H']
    T = state['T']

    Hdash = new_H_pos()
    Tdash = new_T_pos(Hdash, T)

    return { 'H': Hdash, 'T': Tdash }


def makestate(hx,hy,tx,ty):
    return { 'H': (hx,hy), 'T': (tx,ty) }

print('Test 5a')
print('   H(3,8) T(2,8) dir=L --->', update(makestate(3,8,2,8), 'L'))
print('   H(3,8) T(2,8) dir=R --->', update(makestate(3,8,2,8), 'R'))
print('   H(3,8) T(2,8) dir=U --->', update(makestate(3,8,2,8), 'U'))
print('   H(3,8) T(2,8) dir=D --->', update(makestate(3,8,2,8), 'D'))

print('Test 5b')
print('   H(3,9) T(2,8) dir=L --->', update(makestate(3,9,2,8), 'L'))
print('   H(3,9) T(2,8) dir=L --->', update(makestate(3,9,2,8), 'R'))
print('   H(3,9) T(2,8) dir=L --->', update(makestate(3,9,2,8), 'U'))
print('   H(3,9) T(2,8) dir=L --->', update(makestate(3,9,2,8), 'D'))

# And we will demonstrate the 'reduce' and 'reductions' functions.

print('Test 6')
init = makestate(0,0,0,0)
print("  reduce     from the origin after 'UURRRD':", reduce(init, update, 'UURRRD'))
print("  reductions from the origin after 'UURRRD':", list(reductions(init, update, 'UURRRD')))


# And now we can solve the problem in very few lines of code!

def solve09(data):
    states = reductions(makestate(0,0,0,0),
                        update,
                        direction_sequence(data))
    answer = len(set(s['T'] for s in states))
    return answer

print()
print('Answer for the test data:', solve09(test_data_09()))
print('Answer for the real data:', solve09(real_data_09()))