https://adventofcode.com/2023/day/14

day14.py

def tilt(ls):
    for i in range(len(ls)):
        for j in range(len(ls[0])):
            if ls[i][j]!='O': continue
            new_loc = 0
            for k in range(i-1, -1, -1):
                if ls[k][j]=='.': continue
                new_loc = k+1
                break
            ls[i][j] = '.'
            ls[new_loc][j] = 'O'


def rotate(ls):  # rotate clockwise
    return [list(l) for l in zip(*ls[::-1])]


def copy(ls):
    return [l[:] for l in ls]


def step(ls):
    ls = copy(ls)
    for _ in range(4):
        tilt(ls)
        ls = rotate(ls)
    return ls


def floyd(f, x0):
    tortoise = f(x0)
    hare = f(f(x0))

    while tortoise!=hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    mu = 0
    tortoise = x0
    while tortoise!=hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    lam = 1
    hare = f(tortoise)
    while tortoise!=hare:
        hare = f(hare)
        lam += 1

    return lam, mu


def brent(f, x0):
    power = lam = 1
    tortoise = x0
    hare = f(x0)

    while tortoise!=hare:
        if power==lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    mu = 0
    tortoise = hare = x0
    for _ in range(lam):
        hare = f(hare)
    while tortoise!=hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    return lam, mu


def number_of_leading_zeros32(n):
    return 35-len(bin(-n))& -n>>32


def number_of_trailing_zeros32(n):
    return 31-number_of_leading_zeros32(n& -n)


def gosper(f, x0):
    tortoises = [None for _ in range(33)]
    tortoises[0] = x0
    xn = x0
    n = 1
    while True:
        cycle_found = None
        xn = f(xn)
        # 31 minus number of leading zeros in n
        kmax = 31-number_of_leading_zeros32(n)
        for k in range(kmax+1):
            if xn==tortoises[k]:
                cycle_found = k
                break

        if cycle_found is not None: break
        n += 1
        tortoises[number_of_trailing_zeros32(n)] = xn
    k = cycle_found
    m = ((((n>>k)-1)|1)<<k)-1
    lam = n-m
    lgl = 31-number_of_leading_zeros32(lam-1)
    mu_u = m
    mu_l = m-max(1, 1<<lgl)+1

    return lam, mu_u, mu_l


def solve1(ls):
    tilt(ls)
    return ls


def solve2(ls):
    # lam, mu = floyd(step, copy(ls))
    # lam, mu = brent(step, copy(ls))
    lam, mu, _ = gosper(step, copy(ls))  # fastest
    for _ in range(mu+(1000000000-mu)%lam):
        ls = step(ls)
    return ls


ls = [list(l.strip()) for l in open(0)]
print(sum(l.count('O')*(len(ls)-i) for i, l in enumerate(solve2(ls))))