Strangely Consistent

Musings about programming, Perl 6, and programming Perl 6

Longcat (epoq diary 002)

I just need to share this cute story.

A few weeks back, my son and I discovered Fancade. Highly recommended, this iOS app consists of a number of smaller subgames. As far as I understand, the user can even create their own levels (although we haven't been able to do this yet, possibly due to regional restrictions). All in all, it looks like a thriving little platform, with a nice solid basis of built-in games, and lots of user contributions.

We're only at the beginning so far. But we've already steered around the following things:

LongCat quickly turned out to be my favorite. It's one of those "a minute to learn, a lifetime to master" kind of games. Here's a typical level from the game:

#######
#     #
#     #
# C   #
#   # #
#     #
#######

Ok, so that's the cat there (C), and an internal wall. Now here are the rules:

Incidentally, we got stuck at the level depicted above. I think it was level 15, but I'm not sure. We tried again and again and again, until it felt like there really wasn't a way to solve this level.

Eventually I told my son "hold on, let me try a thing". I broke out an old code base, which has a solver for generic puzzle-like problems. Here is the solver in its entirety, written in TypeScript:

function solve <State> (puzzle: Puzzle<State>): void {
    let queue = [{ state: puzzle.initialState, trace: [puzzle.initialDescription] }];
    let queuedSet = new Set([hash(puzzle.initialState)]);

    let elem: { state: State, trace: string[] };

    while (elem = queue.shift()!) {
        let { state, trace } = elem;

        if (puzzle.winningCondition(state)) {
            for (let step of trace) {
                console.log(step);
            }
            console.log(puzzle.winningDescription);
            return;
        }

        for (let { newState, description } of puzzle.validMoves(state)) {
            if (queuedSet.has(hash(newState))) {
                continue;
            }
            queue.push({
                state: newState,
                trace: [...trace, description],
            });
            queuedSet.add(hash(newState));
        }
    }

    console.log("There's no solution.");
}

I love this code. I'm proud of it. Every line of it is somehow in support of the narrative.

Specifically, this is a general problem solver. I can't emphasize this enough. If you have a certain type of problem (I'll get to the specifics of this) you can enter it into this function, and it will spit out a solution. There's something about this arrangement that just thrills me to no end. I think it has something to do with an old, already-antiquated view of computers: as some huge behemoth that you feed a data tape with a problem, and it spits out another data tape with a solution. Computers no longer feel that way, but... this function kinda feels that way, I think.

The function essentially says this:

There's nothing really new or revoluationary about any of this. What we are doing is just executing a Breadth-First Search on the implicit graph formed by all the possible states and their "valid move" state transitions. My repository is even called puzzle-bfs for this reason.

The nice thing, if I were to try and put it into words, is that the above function manages to make a pretty clean separation between the generic problem solving and the specifics of the problem itself. That is, the function manages to solve any problem of this kind, without knowing the specifics of the problem. I guess it just feels like an especially successful factoring.

Again, this solver is something I wrote two years ago and haven't thought much about since. Now, suddenly, I turned to it to help solve this seemingly impossible LongCat level.

Here's how I coded up the problem:

interface Level {
    catX: number;
    catY: number;
    sizeX: 5,
    sizeY: 5,
    level: boolean[][];
}

function clone2dArray(array: boolean[][]) {
    return array.map((row) => [...row]);
}

function moveUp(state: Level) {
    let { catX, catY, level } = state;
    level = clone2dArray(level);
    while (catY > 0 && !level[catY-1][catX]) {
        catY--;
        level[catY][catX] = true;
    }
    return { ...state, catY, level };
}

function moveDown(state: Level) {
    let { catX, catY, level, sizeY } = state;
    level = clone2dArray(level);
    while (catY < sizeY - 1 && !level[catY+1][catX]) {
        catY++;
        level[catY][catX] = true;
    }
    return { ...state, catY, level };
}

function moveLeft(state: Level) {
    let { catX, catY, level } = state;
    level = clone2dArray(level);
    while (catX > 0 && !level[catY][catX-1]) {
        catX--;
        level[catY][catX] = true;
    }
    return { ...state, catX, level };
}

function moveRight(state: Level) {
    let { catX, catY, level, sizeX } = state;
    level = clone2dArray(level);
    while (catX < sizeX - 1 && !level[catY][catX+1]) {
        catX++;
        level[catY][catX] = true;
    }
    return { ...state, catX, level };
}

let puzzle4: Puzzle<Level> = {
    initialDescription: "The cat is in its starting position.",
    initialState: {
        catX: 1,
        catY: 2,
        sizeX: 5,
        sizeY: 5,
        level: [
            [false, false, false, false, false],
            [false, false, false, false, false],
            [false, true, false, false, false],
            [false, false, false, true, false],
            [false, false, false, false, false],
        ],
    },

    validMoves: (state: Level) => [
        {
            description: "Move up.",
            newState: moveUp(state),
        },
        {
            description: "Move down.",
            newState: moveDown(state),
        },
        {
            description: "Move left.",
            newState: moveLeft(state),
        },
        {
            description: "Move right.",
            newState: moveRight(state),
        },
    ].filter(({ newState }) => newState.catX != state.catX || newState.catY != state.catY),

    winningDescription: "The whole level is filled.",
    winningCondition: (state: Level) => state.level.every((row) => row.every((cell) => cell)),
};

solve(puzzle4);

I did this essentially with my son watching. (He's five, so I give him full points on patience; even though I was explaining along the way, it was a bit too much code for his wish for instant gratification.) Then we run it, and the Big Machine printed this output:

The cat is in its starting position.
Move left.
Move down.
Move right.
Move up.
Move left.
Move down.
Move right.
Move down.
Move left.
Move down.
Move left.
The whole level is filled.

Personally I was a little bit stunned that it had worked at all. Next up, we tried these stepwise instructions on level 15, and...

...they worked! The puzzle solver had solved our puzzle!

Man, that felt good! 哈哈

This is what computers are meant to be like, all the time! You feed them an apparently impossible problem, and they immediately spit out a nice solution. Your live quality improves, and you tip your hat to the Big Machine and get on with your day.

Other takeaways:

I have this other simmering idea, which I might as well mention: that of taking this solver, and plugging it into a bigger system, one which can generate puzzles. Because when you think about it, being able to solve these puzzles is a modular subpart of being able to generate puzzles in the first place. When you generate these puzzles, it's good to know that a puzzle has a unique solution (maybe up to some isomorphism). Unique solutions are not an absolute requirement, but they do make the puzzle itself nicer.

Other desirable properties include:

My feeling is that all of the above properties can be encoded, maybe not in a generic way but at the very least for each particular problem domain. And at that point, we could essentially churn out interesting puzzles/levels to solve.

For a while now, I've been wanting to try that for both Theseus and Little Red Riding Hood, both of which I think would yield interesting new levels. Quite possibly Sokoban would also be fun to try this on.