silverhand.py

#!/usr/bin/env python3

__title__ = 'silverhand'
__description__ = 'breach protocol puzzle solver'
__copyright__ = 'Copyright 2020 Gianni Tedesco'
__author__ = 'Gianni Tedesco'
__author_email__ = 'gianni@scaramanga.co.uk'
__license__ = 'MIT'

from collections import defaultdict


def gen_sequences(sequences):
    """
    Generate all permutations of the sequences. Also produce shorter versions
    where we have overlaps, eg. given sequences (1, 2, 3) and (3, 4, 5),
    produce (1, 2, 3, 4, 5) as well as (1, 2, 3, 3, 4, 5)

    Algorithm is off the top off my head. This isn't debrujin sequences but
    it's similar. I wonder if this problem has a name or known solutions?
    """

    stk = []
        
    def do_gen_sequences(sequences):
        if not sequences:
            yield tuple(stk)

        for item in sequences:
            nxt = sequences - frozenset({item})

            item_len = len(item)

            for i in range(1, item_len):
                prefix = item[:i]
                suffix = tuple(stk[-len(prefix):])

                if prefix == suffix:
                    novel = item[i:]
                    stk.extend(novel)
                    yield from do_gen_sequences(nxt)
                    del stk[-len(novel):]

            stk.extend(item)
            yield from do_gen_sequences(nxt)
            del stk[-item_len:]

    yield from do_gen_sequences(sequences)


class PuzzleMatrix:
    """
    Given a code-matrix, build some lookup tables. The lookup tables allow the
    validate() method to work.

    The validate() method finds a solution in the puzzle matrix (starting
    from row zero) when given a code sequence. It either returns a sequence of
    coordinates if the code sequence was found or None if not.
    """

    __slots__ = (
        '_mat',
        '_init',
        '_pos',
        '_order',
        '_col_map',
        '_row_map',
    )

    def __init__(self, code_matrix):
        self._mat = code_matrix
        self._init = ()
        self._pos = 0

        # must be a sequare matrix, no real reason but sizing it from the input
        xmax = ymax = len(code_matrix)
        self._order = xmax

        col_map = defaultdict(list)
        row_map = defaultdict(list)

        for x in range(xmax):
            for y in range(ymax):
                val = code_matrix[x][y]
                row_map[x, val].append(y)
                col_map[y, val].append(x)

        self._row_map = {k: tuple(v) for k, v in row_map.items()}
        self._col_map = {k: tuple(v) for k, v in col_map.items()}

    def __len__(self):
        return self._order

    def __getitem__(self, coord):
        x, y = coord
        return self._mat[x][y]

    def set_init_seq(self, init_seq):
        self._init = init_seq

        xtop, ytop = init_seq[-1]
        if len(init_seq) & 1:
            self._pos = ytop
        else:
            self._pos = xtop

    def validate(self, seq):
        stk = []
        stk.extend(self._init)

        cm = self._col_map
        rm = self._row_map

        def do_validate(pos, seq):
            if not seq:
                return True

            cnt = len(stk)

            if cnt & 1:
                name = 'col'
                tbl = cm
            else:
                name = 'row'
                tbl = rm

            val = seq[0]

            try:
                nxt = tbl[pos, val]
            except KeyError:
                return False

            nxt_cnt = cnt + 1
            nxt_seq = seq[1:]
            for step in nxt:
                if cnt & 1:
                    coord = (step, pos)
                else:
                    coord = (pos, step)

                if coord in stk:
                    # ok so it's quadratic, but these are small, we could add a
                    # set if we wanted to solve gargantuan versions of these
                    # puzzles
                    continue

                stk.append(coord)
                if do_validate(step, nxt_seq):
                    return True
                stk.pop()

            return False

        if do_validate(self._pos, seq):
            return stk

        return None


def solve(puzzle, sequences):
    validate = puzzle.validate

    seq_set = frozenset(sequences)
    seqs = sorted(gen_sequences(sequences), key=len)
    for seq in seqs:
        path = validate(seq)
        if path is not None:
            return path, seq

    # We didn't find any of the sequences so lets try picking duds on the
    # first row and try from there
    for i in range(len(puzzle)):
        init_seq = (
            (0, i),
        )

        puzzle.set_init_seq(init_seq)
        path = validate(seq)
        if path is not None:
            return path, (puzzle[0, i],) + seq


def main():
    puzzle = PuzzleMatrix((
        (0xbd, 0x1c, 0x55, 0x7a, 0xe9, 0x55),
        (0xbd, 0x55, 0x55, 0x7a, 0x1c, 0x1c),
        (0xe9, 0x7a, 0xbd, 0x1c, 0x55, 0x55),
        (0x55, 0x1c, 0x7a, 0x1c, 0xe9, 0x7a),
        (0x7a, 0x55, 0x1c, 0x55, 0xbd, 0x7a),
        (0x55, 0x1c, 0x55, 0x1c, 0x1c, 0x7a),
    ))

    sequences = frozenset((
        (0x55, 0x1c, 0xe9),
        (0xbd, 0xe9, 0x55),
    ))

    res = solve(puzzle, sequences)
    if res is None:
        raise SystemExit(1)

    path, seq = res

    # print('sequence:', ' '.join(('%.2x' % p for p in seq)))
    # print('path:', ' '.join(str(p) for p in path))
    for (x, y), val in zip(path, seq):
        print(f'row {x} col {y} -> {val:02x}')
    print()



if __name__ == '__main__':
    main()