English Puzzle Solver

A general-purpose puzzle solver using binary bitmask algorithms for efficient letter matching. This component can work with any dataset of words or names to solve puzzles by finding unique letter combinations. The London Underground stations are used as a default example dataset.

Overview

The English Puzzle Solver uses a clever binary bitmask algorithm to quickly match words and solve puzzles. Each letter A-Z is represented as a bit position (0-25) in a 26-bit integer, enabling O(1) letter matching through bitwise operations.

How It Works

1. Binary Encoding: Each item name is converted to a 26-bit mask where each bit represents a letter (A=bit 0, B=bit 1, ..., Z=bit 25)
2. Filter Finding: The algorithm finds the shortest combination of letters that uniquely identifies an item
3. Word Matching: Uses pre-encoded binary word data to instantly find words matching filter criteria
4. Data Visualization: Interactive table showing letter frequency and presence across all items

Example Puzzle (London Underground Dataset)

"Name the only London Underground station that doesn't share any letters with the word 'Mackerel'?"

The answer is St John's Wood - it's the only station that doesn't contain any letters from "Mackerel" (M, A, C, K, E, R, L).

This puzzle solver can work with any dataset - cities, countries, words, or any collection of text items!

Binary Mask Algorithm

The core innovation uses binary masks for O(1) letter matching:

• Each letter A-Z maps to bit position 0-25
• Item names converted to 26-bit masks
• Bitwise AND/OR operations enable instant filtering
• Example: "BANK" = bits 1,0,13,10 set = 0b00000010000010000000000011

Technical Details

// Convert item name to binary mask
function convertToBinaryMask(itemName: string): number {
  let binaryMask = 0;
  for (let char of itemName) {
    binaryMask |= 1 << (char.charCodeAt(0) - 'A'.charCodeAt(0));
  }
  return binaryMask;
}

// Check if filter matches item
const filterMask = convertToBinaryMask("ABC");
const itemMask = convertToBinaryMask("BANK");
const matches = (itemMask & filterMask) === filterMask; // true if item contains all filter letters

Features

• Interactive Quiz: Rotating quiz questions with reveal animations (configurable per dataset)
• Item Filtering: Find unique letter combinations that identify items in your dataset
• Word Matching: Find English words matching filter criteria using binary search
• Data Visualization: Filterable table showing letter presence across all items
• Letter Analysis: Frequency ranking and occurrence counts for each letter
• Configurable: Works with any dataset - just provide CSV data and configuration

Data Generation

The component uses pre-processed data files. For the London Underground example:

1. LND_UG.csv: Station data with line information (can be any CSV with your data)
2. 130k.txt: Processed word list (130,000 words sorted by frequency)
3. words.base64.txt: Binary encoded word data for fast bitwise matching

Data generation scripts are available in /scripts/:

• _processWordList.js: Processes raw word frequency data
• _convertTxtToBinary.js: Converts word list to binary format
• _combinedFilter.js: Testing utility for filter algorithm

You can use your own CSV file - just configure the component with the path and the column key to extract items from.

Details

• Title: English Puzzle Solver - London Underground Edition
• Author: Mangle Kuo
• GitHub: ghcpuman902
• Tags: react, tailwind, london, underground, puzzle, word-matching, binary, algorithm, data-visualization, interactive
• Version: 0.0.1
• Complexity: advanced
• Category: components

Example Usage

Default (London Underground)

import { EnglishPuzzleSolver } from './english-puzzle-solver';

export default function Page() {
  return <EnglishPuzzleSolver />;
}

Custom Dataset

import { EnglishPuzzleSolver, PuzzleConfig } from './english-puzzle-solver';

export default function Page() {
  const config: PuzzleConfig = {
    title: 'World Capitals Puzzle',
    itemName: 'Capital',
    dataSource: {
      csvPath: 'public/data/capitals.csv',
      csvKey: 'Capital',
    },
    wordListPath: 'public/london-underground/130k.txt',
    wordListBinaryPath: 'public/london-underground/words.base64.txt',
    questions: [
      {
        question: "Which capital city doesn't share any letters with 'Tokyo'?",
        answer: 'Paris',
      },
    ],
  };
  
  return <EnglishPuzzleSolver config={config} />;
}

Credits

• Station data: London Underground network
• Word list: Processed from Leipzig Wortschatz (https://wortschatz.uni-leipzig.de/de/download/English)