felix021提到的算法小练习

#! /usr/bin/env python3
# NOTE: This program is a quick & dirty snippet.
# CONTAINS A LOT OF ASSUME, AND BARELY NO EXCEPTION HANDLING.
# Problem URL: http://blog.segmentfault.com/felix021/1190000000399153
# License: public domain


def full_hash(matrix):
    # Unsigned, 20bit (=1048576) MAX
    hash_result = 0
    pos_white = None
    for irow in range(4):
        for icol in range(4):
            hash_result <<= 1
            if matrix[irow][icol] == 'r':
                hash_result |= 1
            elif matrix[irow][icol] == 'b':
                hash_result |= 0
            elif matrix[irow][icol] == 'w':
                hash_result |= 0
                pos_white = irow * 4 + icol
            else:
                raise ValueError
    hash_result <<= 4
    hash_result |= pos_white
    return hash_result


def pos2dig(pos):
    return (16 - pos - 1) + 4


def move_action(pattern, new_pos):
    curr_pos = pattern & 0x0F
    new_pos_color = 1 if (pattern & (1 << pos2dig(new_pos))) else 0
    # Move color of new grid to curr white grid
    pattern &= ~(1 << pos2dig(curr_pos))
    if new_pos_color:
        pattern |= 1 << pos2dig(curr_pos)
    # Clear color of new grid
    pattern &= ~(1 << pos2dig(new_pos))
    # Move position to new grid
    pattern &= ~0x0F
    pattern |= new_pos
    return pattern


def bucket_compare(element1, element2):
    if element1 == element2:
        return 0
    elif element1 is None:
        return 1
    elif element2 is None:
        return -1
    else:
        return element1['distance'] - element2['distance']


def bucket_update(bucket, pattern, distance, previous_pattern,
    previous_movement):
    bucket_new_value = {
        'distance': distance,
        'previous_pattern': previous_pattern,
        'previous_movement': previous_movement,
    }
    if bucket_compare(bucket_new_value, bucket[pattern]) < 0:
        bucket[pattern] = bucket_new_value
        return True
    else:
        return False


def queue_append(queue, pattern, distance, previous_pattern,
    previous_movement):
    queue.append({
        'pattern': pattern,
        'distance': distance,
        'previous_pattern': previous_pattern,
        'previous_movement': previous_movement,
    })


def move_position(position, movement):
    row = position // 4
    col = position % 4
    if movement == 'U':
        row -= 1
    elif movement == 'D':
        row += 1
    elif movement == 'L':
        col -= 1
    elif movement == 'R':
        col += 1
    else:
        raise ValueError

    if (row >= 0 and row < 4) and (col >= 0 and col < 4):
        return (row * 4 + col)
    else:
        raise ValueError

start_pos = 0
start_patt = (0x4CCC << 4) | start_pos
goal_pos = 0
goal_patt = (0x25A5 << 4) | goal_pos
bucket_length = 1 << 20
bucket = [None] * bucket_length

import collections
queue = collections.deque()

queue_append(queue, start_patt, 0, start_patt, 'N')

while len(queue) > 0:
    queue_item = queue.popleft()

    curr_patt = queue_item['pattern']
    curr_pos = curr_patt & 0x0F
    curr_dist = queue_item['distance']
    prev_patt = queue_item['previous_pattern']
    prev_move = queue_item['previous_movement']

    updated = bucket_update(bucket, curr_patt, curr_dist, prev_patt, prev_move)
    if not updated:
        continue

    for movement in 'UDLR':
        try:
            new_pos = move_position(curr_pos, movement)
        except ValueError:
            continue
        new_patt = move_action(curr_patt, new_pos)
        new_dist = curr_dist + 1
        queue_append(queue, new_patt, new_dist, curr_patt, movement)

path = collections.deque()
curr_patt = goal_patt
while curr_patt != start_patt:
    path.appendleft(bucket[curr_patt]['previous_movement'])
    curr_patt = bucket[curr_patt]['previous_pattern']
for node in path:
    print(node, end=' ')
print()