puzzle-utils

Overview

This C#.NET repository contains utility code that I found helpful in solving programming puzzles like advent-of-code and everybody-codes. The repository contains two projects:

1. Utilities: A class library with various utility functions and classes.
2. Utilties.Tests: A unit test library for the main Utilities project.

Examples

Vector Types (Vec2D, Vec3D, and Vec4D)

Integral vector types with common operations and utilities for 2D/3D/4D spatial calculations:

using Utilities.Geometry.Euclidean;

// Basic vector operations
var pos = new Vec2D(3, 4);
var velocity = Vec2D.Up + Vec2D.Right;  // (1, 1)
var newPos = pos + velocity;            // (4, 5)

// Distance calculations
var manhattan = Vec2D.Distance(Vec2D.Zero, pos, Metric.Taxicab);     // 7
var chebyshev = Vec2D.Distance(Vec2D.Zero, pos, Metric.Chebyshev);   // 4

// 3D vectors work similarly
var pos3D = new Vec3D(1, 2, 3);
var direction = Vec3D.Forward * 2;      // (0, 0, 2)

// 3D rotations using quaternions
var point = new Vec3D(1, 0, 0);
var rotated = point.Rotate(Rot3D.P90Z);  // Rotate 90° around Z-axis → (0, 1, 0)

2D Grid (Grid2D<T>)

Generic 2D grid data structure with flexible indexing and string parsing:

using Utilities.Geometry.Euclidean;

// Create grid from string array (common in puzzles)
var map = new[] {
    "###",
    "#.#",
    "###"
};
var grid = Grid2D<char>.MapChars(map, c => c);

// Access elements using Vec2D or coordinates
var center = grid[new Vec2D(1, 1)];     // '.'
var corner = grid[0, 0];                // '#'

// Check bounds and iterate
if (grid.Contains(new Vec2D(1, 1)))
{
    foreach (var pos in grid)
    {
        char cell = grid[pos];
        // Process each position in the grid
    }
}

// Create empty grid with dimensions
var emptyGrid = Grid2D<int>.WithDimensions(rows: 5, cols: 5);

Axis-Aligned Bounding Boxes (Aabb2D and Aabb3D)

2D and 3D rectangular regions with overlap detection and iteration:

using Utilities.Geometry.Euclidean;

// Create bounding boxes
var box1 = new Aabb2D(min: new Vec2D(0, 0), max: new Vec2D(5, 5));
var box2 = new Aabb2D(xMin: 3, xMax: 8, yMin: 3, yMax: 8);

// Check for overlaps
if (Aabb2D.Overlap(box1, box2, out var intersection))
{
    Console.WriteLine($"Overlap area: {intersection.Area}");  // 9
}

// Iterate over all points in the box
foreach (var point in box1)
{
    // Process each Vec2D point from (0,0) to (5,5)
}

Numeric Ranges (Range<T>)

Generic integral intervals with overlap detection and enumeration:

using Utilities.Numerics;

// Create ranges
var range1 = new Range<int>(min: 1, max: 10);
var range2 = new Range<int>(min: 5, max: 15);

// Check overlaps
if (Range<int>.Overlap(range1, range2, out var overlap))
{
    Console.WriteLine($"Overlap: {overlap.Min}-{overlap.Max}");  // 5-10
}

// Enumerate values
foreach (var value in range1)
{
    // Iterate from 1 to 10 (inclusive)
}

Disjoint Set (Union-Find) (DisjointSet<T>)

Efficient data structure for tracking connected components:

using Utilities.Collections;

var ds = new DisjointSet<string>();

// Add elements
ds.MakeSet("A");
ds.MakeSet("B");
ds.MakeSet("C");

// Union operations
ds.Union("A", "B");  // Connect A and B

Console.WriteLine($"Components: {ds.PartitionsCount}");  // 2

Default Dictionary (DefaultDict<TKey, TValue>)

Dictionary that returns default values for missing keys:

using Utilities.Collections;

// Dictionary with default value of 0
var counter = new DefaultDict<string, int>(defaultValue: 0);

// Count occurrences without checking Contains()
counter["apple"]++;
counter["banana"]++;
counter["apple"]++;

Console.WriteLine(counter["apple"]);    // 2
Console.WriteLine(counter["orange"]);   // 0 (default)

// Dictionary with generated defaults
var listDict = new DefaultDict<string, List<int>>(defaultSelector: _ => new List<int>());
listDict["numbers"].Add(42);  // Automatically creates new list

Linear System Solver (LinearSolver)

Solve systems of linear equations:

using Utilities.Numerics;

// Solve: 2x + y = 5, x - y = 1
// Augmented matrix: [2,  1, 5]
//                   [1, -1, 1]
var matrix = new double[,] {
    { 2.0,  1.0, 5.0 },
    { 1.0, -1.0, 1.0 }
};

var solution = LinearSolver.Solve(matrix, epsilon: 1e-10);
// solution[0] = x = 2, solution[1] = y = 1

Context-Free Grammar Parser (CykParser)

Cocke-Younger-Kasami algorithm for parsing context-free grammars with automatic CNF conversion:

using Utilities.Language.ContextFree;

// Define grammar productions (any CFG format)
var productions = new[]
{
    new Production("S", ["NP", "VP"]),         // S → NP VP
    new Production("NP", ["Det", "Adj", "N"]), // NP → Det Adj N (will be converted to CNF)
    new Production("VP", ["V", "NP"]),         // VP → V NP
    new Production("Det", ["the", "a"]),       // Det → "the" | "a"
    new Production("Adj", ["big", "small"]),   // Adj → "big" | "small"
    new Production("N", ["cat", "dog"]),       // N → "cat" | "dog"
    new Production("V", ["sees", "chases"])    // V → "sees" | "chases"
};

var grammar = new Grammar(start: "S", productions);

// Convert to CNF automatically if needed
var cnfGrammar = grammar.IsInCnf ? grammar : CnfConverter.Convert(grammar);
var parser = new CykParser(cnfGrammar);

// Parse sentences
var sentence = new[] { "the", "big", "cat", "sees", "a", "dog" };
bool isValid = parser.Recognize(sentence);  // true

// Get parse tree if needed
if (parser.Recognize(sentence, out var parseTree))
{
    // parseTree contains the syntactic structure
}