kitchen_sorting.py

#!/usr/bin/env python3

# Script to solve "Kitchen Sorting" puzzles at GameSnacks.com
# (https://gamesnacks.com/games/757entlesmh4g) but presumably generalizable
# to any similar sorting game.
#
# Define the puzzle by creating a text file where each line in the file
# represents a tube in the game and is either a single hyphen to indicate that
# the tube starts empty or a whitespace separated list of the items in the
# tube. Change the `puzzle_file` variable below to the file name containing the
# puzzle.
#
# This isn't great code, but it's certainly not worth the time to optimize or
# clean up.
#
# By Jonathan Kamens, public domain, enjoy.

import copy
import os
import pprint
import sys

learned = {}
seen = []
successful = None
puzzle_file = 'puzzle151'
orig_tubes = []
tube_size = None


def read_puzzle():
    global tube_size
    with open(puzzle_file) as f:
        for line in f:
            line = line.strip()
            if line == '-':
                orig_tubes.append([])
            else:
                orig_tubes.append(line.split())
    tube_size = max(len(t) for t in orig_tubes)


def write_puzzle():
    with open(f'{puzzle_file}.new', 'w') as f:
        for tube in orig_tubes:
            print(' '.join(tube) if len(tube) else '-', file=f)
    os.rename(f'{puzzle_file}.new', puzzle_file)


def find_moves(tubes):
    moves = []
    for from_tube_number in (i for i in range(1, len(tubes) + 1)
                             if tubes[i - 1] is not None
                             and len(tubes[i - 1]) > 0):
        from_tube = tubes[from_tube_number - 1]
        for to_tube_number in (i for i in range(1, len(tubes) + 1) if
                               tubes[i - 1] is not None and
                               i != from_tube_number and
                               len(tubes[i - 1]) < tube_size):
            to_tube = tubes[to_tube_number - 1]
            if len(to_tube) > 0 and to_tube[0] != from_tube[0]:
                continue
            moves.append([from_tube_number, to_tube_number])
    return moves


def format_move(move):
    return f'{move[0]} => {move[1]}'


def format_moves(moves):
    return ', '.join((format_move(m) for m in moves))


def make_move(moves_so_far, tubes, move):
    tubes = copy.deepcopy(tubes)
    from_tube_number = move[0]
    from_tube = tubes[from_tube_number - 1]
    to_tube_number = move[1]
    to_tube = tubes[to_tube_number - 1]
    space_available = tube_size - len(to_tube)
    num_available = 1
    for i in range(1, len(from_tube)):
        if from_tube[0] != from_tube[i]:
            break
        num_available += 1
    num_to_move = min(num_available, space_available)
    to_tube[0:0] = from_tube[0:num_to_move]
    from_tube[0:num_to_move] = []
    if len(from_tube) and from_tube[0] == "hidden":
        learn_key = (from_tube_number, len(from_tube))
        if learn_key in learned:
            from_tube[0] = learned[learn_key]
        else:
            print('So far: ', format_moves(moves_so_far + [move]))
            from_tube[0] = input(f'What is {len(from_tube)} from the bottom of tube {from_tube_number}? ')
            learned[learn_key] = from_tube[0]
            orig_tubes[from_tube_number - 1][-len(from_tube)] = from_tube[0]
            write_puzzle()
    if len(to_tube) == tube_size and all(to_tube[0] == to_tube[i]
                                         for i in range(tube_size)):
        tubes[to_tube_number - 1] = None
    return tubes


def canonicalize(tubes):
    tubes = [t for t in tubes if t is not None]
    tubes.sort()
    return str(tubes)


def work_it_out(moves_so_far, tubes):
    global successful
    if successful and len(moves_so_far) == len(successful):
        print("SHORT-CIRCUIT")
        return
    if all(t is None or len(t) == 0 for t in tubes):
        print("SUCCESS!")
        if successful is None or len(successful) > len(moves_so_far):
            successful = moves_so_far
        return
    for move in find_moves(tubes):
        print(format_move(move))
        new_tubes = make_move(moves_so_far, tubes, move)
        canon = canonicalize(new_tubes)
        if canon in seen:
            print("SEEN")
        else:
            seen.append(canon)
            work_it_out(moves_so_far + [move], new_tubes)
        print("UNDO")


read_puzzle()
work_it_out([], orig_tubes)
print(format_moves(successful))