aoc2022-problem-17

aoc2022-problem17.py

#from aocd import submit

from util import ints, sign, neighbors

from collections import defaultdict

filename = "17"
# proble input is jet pattern

# rocks spawn 3 units above the last rock or the floor if there isnt a highest rock there
# use a lowest var

rocks = [
        [(0,0),(1,0),(2,0),(3,0)], # -
        [(1,0),(0,1),(1,1),(2,1), (1,2)], # +
        [(2,0),(2,1),(0,2),(1,2),(2,2)], # L
        [(0,0),(0,1),(0,2),(0,3)], # line
        [(0,0),(1,0),(0,1),(1,1)], # block
]

heights = [1,3,3,4,2]

L = [l.strip() for l in open(filename, 'r')]
jet = L[0]

rockIdx = 0 # index

G = defaultdict(bool)
floor = 0

# width is 7 units wide
# they all spawn at X=2
gfloor = None
def place(rock): # floor is y
    global gfloor
    for coord in rock:
        G[coord] = True
        if gfloor is None:
            gfloor = coord[1]
        else:
            gfloor = min(gfloor, coord[1])

def newrock(rock, floor, rockHeight): # floor is y
    # placed by order of bottom edge
    # place at yidx+y-heights[rock]
    # floor-3-heights[rock] = startY
    startY = floor-3-rockHeight
    startX = 2
    Q = []
    for coord in rock:
        P = (coord[0]+startX, coord[1]+startY)
        Q.append(P)
    return Q

def move(rock, dx, dy):
    for coord in rock:
        x, y = coord
        P = (x+dx,y+dy)
        if P in G or (x + dx <= -1 or x + dx >= 7 or y+dy >= 1):
            return False
    return True

# returns moved rock coords
def apply(rock, dx, dy):
    rock2 = []
    for coord in rock:
        x, y = coord
        P = (x+dx,y+dy)
        rock2.append(P)
    return rock2

def getfloor():
    lowest = None
    for P in G:
        if lowest is None:
            lowest = P[1]
        elif P[1] < lowest:
            lowest = P[1]

    if lowest is None:
        return 1

    return lowest
    

def printgraph():
    out = ""
    m = getfloor()-1
    for y in range(m, m+30, 1):
        row = ""
        for x in range(0, 7):
            P = (x,y)
            if P in G:
                row += "#"
            else:
                row += "."
        out += row + "\n"
    return out



numRocks = 0
jetidx = 0
h = []
boards = set([])
import time
last = time.time()
lastboard = defaultdict(list)

# 573065902 times 
while numRocks <1000000000000:
    if gfloor is not None:
        floor = gfloor
    else:
        floor = getfloor()
    #print("FLOOR IS", floor)
    currentRock = rocks[rockIdx%len(rocks)].copy()
    r = newrock(currentRock, floor, heights[rockIdx%len(rocks)])
    #print("SPAWNED AT", r)
    # spawn rock
    # move rock based on jet
    # move rock down
    t = 0
    jetstart = jetidx
    while True:
        if t%2 == 0: #jet
            c = jet[jetidx%len(jet)]
            jetidx += 1
            if c == "<":
                dx = -1
            else:
                dx = 1
            dy = 0
            #print("JET DIX",jetidx)
            if move(r, dx, dy):
                #print("Pushed",dx,t)
                r = apply(r, dx, dy)
        else: # fall
            dx = 0
            dy = 1
            if move(r, dx, dy):
                #print("ROCK FALLS 1 unit")
                r = apply(r, dx, dy)
            else:
                #print("STOPPED MOVING ROCK", rockIdx)
                place(r)
                break
        t += 1

        #printgraph()

    #printgraph()
    b = printgraph()
    h.append(abs(gfloor+1))
    if b not in boards:
        print(len(boards))
        boards.add(b)
        lastboard[b].append((numRocks+1, abs(gfloor)+1))
    else:
        print("FOUND CYCLE", numRocks+1-(lastboard[b][-1][0]), "height", abs(gfloor)+1, numRocks+1, jetidx%len(jet))
        print(lastboard[b])
        if len(h) >= 1184:
            lastboard[b].append((numRocks+1, abs(gfloor)+1,jetidx%len(jet), rockIdx%len(rocks),
                                 h[len(h)-1]-h[len(h)-1-1183]))
            print(b)
            N = 1000000000000
            cycle_len = numRocks+1-lastboard[b][-2][0]
            ND = N-(numRocks+1)
            height_diff = abs(gfloor)+1-lastboard[b][-2][1]
            # height_diff*(ND//cycle_len)
            new_h = abs(gfloor)+1
            new_h += height_diff*(ND//cycle_len)
            remaining = ND%cycle_len  # remaining blocks we have to place
            if remaining == 0 and height_diff != 0:
                print("answer",new_h)
                break
            hd =h[len(h)-1]-h[len(h)-1-remaining]
            new_h += hd
            print("metrics",N,cycle_len,height_diff,remaining)
    #print("----")

    #h.append(gfloor+1) # figure out the length of this cycle

    rockIdx += 1
    # need code to determine if new pos collides
    # if it does stop
    numRocks += 1

# num rocks falling is 19022, height is 30260
# height increases by 2778 every 1745 rocks
# reload board state with jet idx
# jetidx = 1810
# rockIdx = 2, will need to be 3 on the next step
# rockIdx = 3
# 573065891*1745
# 573065891*1745 rocks need to fall
# height increases by 573065891*2778
# height is 19021+1591977045198  = 1591977064219
# allow 1183 more rocks to fall which is 1903 rocks

print(abs(gfloor)+1)
#submit(abs(gfloor)+1)