Curta 12 Labyrinth solver

curta12.py

import sha3
import heapq

my_address = "00000000000000000000000097735c60c5e3c2788b7ee570306775e687095d19"
my_address_bytes = bytes.fromhex(my_address)
current_block = 17372613


def find_steps(start):
    valid_steps = []
    for i in range(-255, 1):
        valid_steps.append(i)

    for i in range(0, 256):
        check = start >> i
        if check & 0x1 == 0:
            valid_steps.append(i)
    return valid_steps

def connect_steps(steps):
    start = 0
    target = 255
    step_op_pairs = [(0, 2), (1, 1), (16, 3)]
    used_steps = set()
    used_steps.add(start)
    # Create a priority queue
    queue = []
    # Push the initial node to the queue
    heapq.heappush(queue, (0, start, [start], []))
    while queue:
        prio, current, path, op_chain = heapq.heappop(queue)



        if len(path) > 128:
            continue
        if current == target:
            solution = 0
            for index, op in enumerate(op_chain):
                new_op = op << (index * 2)
                solution = solution | new_op
            solution = hex(solution)[2:].zfill(64)
            return (path, solution)

        for step_val, op in step_op_pairs:
            next_step = 0
            if op == 1:
                if (current + 1) % 16 == 0:
                    continue
                else:
                    pass
                next_step = current + step_val
            elif op == 2:
                if current % 16 == 0:
                    continue
                next_step = -current + 1
            elif op == 3:
                if ((current < -16) or (current > 240)):
                    continue
                next_step = current + step_val

            if next_step in steps and next_step not in used_steps:
                used_steps.add(next_step)
                cost = len(path)
                priority = cost + heuristic(current, next_step, target)  # Compute the priority using a heuristic function
                heapq.heappush(queue, (priority, next_step, path + [next_step], op_chain + [op]))

    return (None, None)

def heuristic(current, next_step, target):
    # Define a heuristic function to estimate the cost from the current node to the target
    return target - abs(next_step)

def main():
    global my_address, my_address_bytes, current_block

    sol_count = 0
    blocks_to_test = 10_000
    for block_number in range(current_block, current_block + blocks_to_test):
        k = sha3.keccak_256()
        t_block_number = hex(block_number)[2:].zfill(64)
        my_address_bytes = bytes.fromhex(my_address)
        block_number_bytes = bytes.fromhex(t_block_number)
        k.update(my_address_bytes + block_number_bytes)
        start_hash = k.hexdigest()
        start = int(start_hash, 16)
        steps = find_steps(start)
        (path, solution) = connect_steps(steps)
        if path:
            sol_count += 1
            print("block_number: %d, solution: 31468f06000000000000000000000000000000000000000000000000000000000000000c%s" % (block_number, solution))
    
if __name__ == '__main__':
    main()