Finn Zink

Dogbunny puzzle creator

Back in September of 2022, a puzzle game called dogbunny was posted on Hacker News. Like many in the HN crowd, this game nerdsniped me immediately. I hadn’t seen many puzzles like this before - super intuitive to play but still challenging.

Puzzles were posted daily for a bit, but then the creator stopped posting them. At some point, the site went offline entirely.

Since the site went offline, I’ve been thinking on and off about if I could generate these sorts of puzzles automatically. I tried many different approaches, but none of them worked well - I couldn’t find good heuristics that created interesting puzzles. If I optimized for creating puzzles with a long solutions, the generated puzzles were trivial to solve.

So, I decided instead to make a site to make your own dogbunny puzzles. It’s live at the following cloudfront url:

Try it out here!

If you just want to play the original dogbunny puzzle from the original HN post, it is recreated there as well. Overall, I am pretty happy with it!

The site sorta speaks for itself and the underlying code is not super complex, but in this post, I’ll walk through a few of the (in my opinion) more interesting ideas.

The Puzzle Solver

One of the core components of the editor is the “game state tree”. This tree represents all possible states of the puzzle, ie positions of dogs and bunnies on the game graph, connected by edges representing valid moves. This allows for the user to see the “shape” of the puzzle solution space visually in the UI.

(Note: the game state is actually a graph, not a tree, since there can be multiple paths to the same state. However, the tree is far better as a visualization tool, and still shows the minimal path to every possible state from the initial state.)

This tree is constructed using a classic breadth-first search algorithm in the PuzzleSolver component.

The heart of the PuzzleSolver is the generateGameTree function:

const generateGameTree = useCallback((
  initialState: GameState,
  puzzle: Puzzle
): GameState => {
  const queue: GameState[] = [initialState];
  const globalVisited = new Set<string>();
  const initialStateKey = getStateKey(initialState.characters);
  globalVisited.add(initialStateKey);

  while (queue.length > 0) {
    const currentState = queue.shift()!;
    const validMoves = getValidMoves(currentState, puzzle);

    currentState.children = validMoves.filter(move => {
      const moveKey = getStateKey(move.characters);
      if (globalVisited.has(moveKey)) {
        return false;
      }
      return true;
    });

    currentState.children.forEach(child => {
      const childKey = getStateKey(child.characters);
      globalVisited.add(childKey);
      queue.push(child);
    });
  }

  return initialState;
}, [getStateKey]);

This is classic BFS: it starts with an initial state and explores all possible moves, creating child states for each valid move. To avoid infinite loops and duplicate states, a globalVisited set keeps track of already seen states.

Puzzle ownership without login

I hate logging in to websites I just want to try out quickly. It interrupts your use of the site, but also forces you to give your email to some random website you are probably only going to use once.

Instead of forcing users to create accounts and log in, a unique key is generated for each user:

useEffect(() => {
  let storedKey = localStorage.getItem('puzzleOwnerKey');
  if (!storedKey) {
    storedKey = generateRandomKey();
    localStorage.setItem('puzzleOwnerKey', storedKey);
  }
  setUserKey(storedKey);
}, []);

const generateRandomKey = () => {
  return Math.random().toString(36).substring(2, 15) + Math.random().toString(36).substring(2, 15);
};

This key is stored in the browser’s local storage and sent with API requests to identify the user. It’s a simple yet effective way to maintain user-specific data without the overhead of a full authentication system.

The key system allows for the implementation of puzzle ownership and basic security measures:

const handleDelete = async (puzzleId: string, puzzleName: string) => {
  const isConfirmed = window.confirm(`Are you sure you want to delete the puzzle "${puzzleName}"?`);
  
  if (isConfirmed) {
    try {
      await axios.delete(`${API_BASE_URL}/puzzles/${puzzleId}?userKey=${userKey}`);
      setPuzzles(puzzles.filter(puzzle => puzzle.id !== puzzleId));
    } catch (error) {
      console.error('Error deleting puzzle:', error);
      setError('Failed to delete puzzle. Please try again later.');
    }
  }
};

When deleting a puzzle, the user’s key is included in the request. The backend can then verify if the user has the right to perform this action. This approach provides a good balance between user convenience and data security.

Hope this was interesting and you give the puzzle building site a try!

🫡