open safe

open_safe.py

__author__ = 'leonmax'

'''
You are given a SAFE, with 4 dials on it

dials are numbered 0-9, continuous, integral

key to this safe -> can *only* be opened in the
fewest number of turns

"turn" -> picking *any* dial, rotating 1 unit clock/counterclockwise
0 -> 4 = 4 turns, not 1 turn

starting combo -> 3926

(blacklist) -> 9236, 8323, 9632, 2369, 2353, 3927

opening combo -> 9639
'''

DIALS = 4


def turn(combo, pos, clockwise=True):
    base = 10 ** (DIALS - pos -1)
    # extract the value at this pos
    digit = int(combo / base) % 10
    # rotate and taking care of edges
    change = 1 if clockwise else -1
    if digit == 9 and clockwise:
        change = - 9
    elif digit == 0 and not clockwise:
        change = 9
    return combo + change * base


def neighbors(combo):
    for pos in range(DIALS):
        for clockwise in [True, False]:
            yield turn(combo, pos, clockwise)


def validate(combo):
    limit = 10 ** DIALS - 1
    assert 0 <= combo <= limit, "combo %s is out of range [0, %s]" % (combo, limit)


def open_safe(starting, opening, blacklist):
    # validate input
    validate(starting)
    validate(opening)
    map(validate, blacklist)
    # if opening is in blacklist, return None immediately
    if opening in blacklist:
        return None

    # CORE ALGORITHM
    visited = set(blacklist + [starting])
    queue = [(starting, [starting])]
    while queue:
        (combo, path) = queue.pop(0)
        if combo == opening:
            return path
        # if combo == 939: print([i for i in neighbors(combo)])
        for neighbor in set(neighbors(combo)) - visited:
            visited.add(neighbor)
            queue.append((neighbor, path + [neighbor]))

    # just for readability, if no path found, return None
    return None

if __name__ == "__main__":
    # when destination is in blacklist, return None
    assert open_safe(3926, 9236, [9236, 8323, 9632, 2369, 2353, 3927]) is None
    
    for i in open_safe(3926, 9639, [9236, 8323, 9632, 2369, 2353, 3927]):
        print(str(i).zfill(4))

it's now generic in terms of how many DIALS it supports