import { describe, it, expect } from 'vitest';
import { slide, slideWithHazards, solve, isSolvable, getOptimalMoveCount } from './solver.js';
import type { PuzzleData, Position } from './types.js';
function makeBasicPuzzle(overrides?: Partial<PuzzleData>): PuzzleData {
return {
id: 'test',
name: 'Test Level',
theme: 'ice',
width: 8,
height: 6,
par: 0,
start: { x: 1, y: 4 },
goal: { x: 6, y: 1 },
obstacles: [],
...overrides,
};
}
describe('slide (basic)', () => {
it('should slide right until hitting wall', () => {
const puzzle = makeBasicPuzzle();
const result = slide({ x: 1, y: 1 }, 'right', puzzle);
expect(result).toEqual({ x: 6, y: 1 }); // Stops at width-2
});
it('should slide down until hitting wall', () => {
const puzzle = makeBasicPuzzle();
const result = slide({ x: 1, y: 1 }, 'down', puzzle);
expect(result).toEqual({ x: 1, y: 4 }); // Stops at height-2
});
it('should stop before rock', () => {
const puzzle = makeBasicPuzzle({
obstacles: [{ x: 4, y: 1, type: 'rock' }],
});
const result = slide({ x: 1, y: 1 }, 'right', puzzle);
expect(result).toEqual({ x: 3, y: 1 }); // Stops before rock
});
it('should stop before hot coals in basic slide mode', () => {
const puzzle = makeBasicPuzzle({
obstacles: [{ x: 3, y: 1, type: 'hot_coals' }],
});
const result = slide({ x: 1, y: 1 }, 'right', puzzle);
expect(result).toEqual({ x: 2, y: 1 }); // Stops before hot coals in basic mode
});
it('should stop at goal', () => {
const puzzle = makeBasicPuzzle({ goal: { x: 3, y: 1 } });
const result = slide({ x: 1, y: 1 }, 'right', puzzle);
expect(result).toEqual({ x: 3, y: 1 });
});
it('should not move if already against wall in that direction', () => {
const puzzle = makeBasicPuzzle();
const result = slide({ x: 1, y: 1 }, 'left', puzzle);
expect(result).toEqual({ x: 1, y: 1 }); // Can't go left from x=1 (wall at x=0)
});
});
describe('slideWithHazards', () => {
it('should detect lava death', () => {
const puzzle = makeBasicPuzzle({
obstacles: [{ x: 3, y: 1, type: 'lava' }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.hitLava).toBe(true);
expect(result.position).toEqual({ x: 3, y: 1 });
});
it('should detect hot coals hit', () => {
const puzzle = makeBasicPuzzle({
obstacles: [{ x: 3, y: 1, type: 'hot_coals' }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.hitHotCoals).toBe(true);
expect(result.position).toEqual({ x: 3, y: 1 });
});
it('should treat spike obstacle as hot coals alias', () => {
const puzzle = makeBasicPuzzle({
obstacles: [{ x: 3, y: 1, type: 'spike' as any }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.hitHotCoals).toBe(true);
expect(result.position).toEqual({ x: 3, y: 1 });
});
it('should detect falling in broken thin ice hole', () => {
const puzzle = makeBasicPuzzle({
thinIceTiles: [{ x: 3, y: 1 }],
});
const brokenIce = [{ x: 3, y: 1 }]; // Already broken
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle, brokenIce);
expect(result.fellInHole).toBe(true);
expect(result.position).toEqual({ x: 3, y: 1 });
});
it('should slide over unbroken thin ice', () => {
const puzzle = makeBasicPuzzle({
thinIceTiles: [{ x: 3, y: 1 }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.fellInHole).toBe(false);
expect(result.position.x).toBeGreaterThan(3); // Passed over it
});
it('should handle warp teleportation', () => {
const puzzle = makeBasicPuzzle({
warps: [
{ x: 3, y: 1, id: 'w1' },
{ x: 3, y: 4, id: 'w1' },
],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.warpDestination).toEqual({ x: 3, y: 4 });
// Warp-stop semantics: move ends at paired warp destination.
expect(result.position).toEqual({ x: 3, y: 4 });
});
it('should push pushable rock', () => {
const puzzle = makeBasicPuzzle({
pushableRocks: [{ x: 3, y: 1 }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.pushedRock).not.toBeNull();
expect(result.pushedRock!.from).toEqual({ x: 3, y: 1 });
expect(result.pushedRock!.to).toEqual({ x: 4, y: 1 });
// Player stops where the rock was
expect(result.position).toEqual({ x: 2, y: 1 });
});
it('should not push rock against wall', () => {
const puzzle = makeBasicPuzzle({
pushableRocks: [{ x: 6, y: 1 }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
// Rock can't be pushed (wall behind it), player stops before
expect(result.pushedRock).toBeNull();
expect(result.position).toEqual({ x: 5, y: 1 });
});
it('should handle pressure plate activation', () => {
const puzzle = makeBasicPuzzle({
pressurePlate: { x: 3, y: 1 },
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.crossedPressurePlate).toBe(true);
});
it('should hit active barrier', () => {
const puzzle = makeBasicPuzzle({
barrier: { x: 3, y: 1 },
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.hitBarrier).toBe(true);
});
it('should pass through deactivated barrier', () => {
const puzzle = makeBasicPuzzle({
barrier: { x: 3, y: 1 },
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle, [], [], true);
expect(result.hitBarrier).toBe(false);
expect(result.position.x).toBeGreaterThan(3);
});
it('should allow goal on edge', () => {
const puzzle = makeBasicPuzzle({
goal: { x: 7, y: 1 }, // On the wall/edge
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.position).toEqual({ x: 7, y: 1 });
});
});
describe('solve', () => {
it('should solve simple level (straight line to goal)', () => {
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 1 },
goal: { x: 6, y: 1 },
});
const result = solve(puzzle);
expect(result.solvable).toBe(true);
expect(result.moves).toBe(1); // Just slide right
expect(result.solution).toEqual(['right']);
});
it('should solve 2-move level', () => {
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 4 },
goal: { x: 6, y: 1 },
obstacles: [{ x: 6, y: 3, type: 'rock' }],
});
const result = solve(puzzle);
expect(result.solvable).toBe(true);
// Need a rock to stop sliding, then go to goal
});
it('should return unsolvable for impossible level', () => {
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 4 },
goal: { x: 6, y: 1 },
obstacles: [
// Wall of rocks blocking all paths
{ x: 1, y: 2, type: 'rock' },
{ x: 2, y: 2, type: 'rock' },
{ x: 3, y: 2, type: 'rock' },
{ x: 4, y: 2, type: 'rock' },
{ x: 5, y: 2, type: 'rock' },
{ x: 6, y: 2, type: 'rock' },
],
});
const result = solve(puzzle);
// This may or may not be solvable depending on exact geometry
// But the solve function should terminate
expect(typeof result.solvable).toBe('boolean');
expect(result.iterations).toBeGreaterThan(0);
});
it('should solve level with lava avoidance', () => {
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 4 },
goal: { x: 6, y: 1 },
obstacles: [
{ x: 3, y: 4, type: 'lava' }, // Can't go right from start
{ x: 1, y: 1, type: 'rock' }, // Stop point
],
});
const result = solve(puzzle);
// Solver should find path avoiding lava
if (result.solvable) {
// Verify solution doesn't include dying
expect(result.solution).not.toBeNull();
}
});
it('should handle level with thin ice state tracking', () => {
const puzzle = makeBasicPuzzle({
width: 10,
height: 8,
start: { x: 1, y: 6 },
goal: { x: 8, y: 1 },
thinIceTiles: [{ x: 4, y: 6 }],
obstacles: [
{ x: 5, y: 6, type: 'rock' },
{ x: 8, y: 3, type: 'rock' },
],
});
const result = solve(puzzle);
expect(typeof result.solvable).toBe('boolean');
});
it('isSolvable should return boolean', () => {
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 1 },
goal: { x: 6, y: 1 },
});
expect(isSolvable(puzzle)).toBe(true);
});
it('getOptimalMoveCount should return number for solvable puzzle', () => {
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 1 },
goal: { x: 6, y: 1 },
});
expect(getOptimalMoveCount(puzzle)).toBe(1);
});
it('getOptimalMoveCount should return null for unsolvable puzzle', () => {
// Completely surrounded start
const puzzle = makeBasicPuzzle({
width: 5,
height: 5,
start: { x: 2, y: 2 },
goal: { x: 3, y: 1 },
obstacles: [
{ x: 1, y: 2, type: 'rock' },
{ x: 3, y: 2, type: 'rock' },
{ x: 2, y: 1, type: 'rock' },
{ x: 2, y: 3, type: 'rock' },
],
});
expect(getOptimalMoveCount(puzzle)).toBeNull();
});
});
describe('mechanic interaction edge cases', () => {
it('should handle pushable rock pushed into lava (rock destroyed)', () => {
// Rock at (3,1), lava at (4,1). Pushing rock right destroys it.
const puzzle = makeBasicPuzzle({
pushableRocks: [{ x: 3, y: 1 }],
obstacles: [{ x: 4, y: 1, type: 'lava' }],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.pushedRock).not.toBeNull();
expect(result.pushedRock!.from).toEqual({ x: 3, y: 1 });
expect(result.pushedRock!.to).toEqual({ x: 4, y: 1 });
// Player stops where rock was
expect(result.position).toEqual({ x: 2, y: 1 });
});
it('should track destroyed rock in solver BFS state', () => {
// Setup: rock blocks path. Push rock into lava to clear path.
const puzzle = makeBasicPuzzle({
width: 10,
height: 8,
start: { x: 1, y: 6 },
goal: { x: 8, y: 1 },
pushableRocks: [{ x: 3, y: 6 }],
obstacles: [
{ x: 4, y: 6, type: 'lava' }, // Rock pushed into lava -> destroyed
{ x: 8, y: 3, type: 'rock' }, // Stop point
],
});
const result = solve(puzzle);
expect(typeof result.solvable).toBe('boolean');
// Solver should handle the destroyed rock state correctly
expect(result.iterations).toBeGreaterThan(0);
});
it('should NOT teleport pushable rocks through warps', () => {
// Rock at (3,1), warp at (4,1) paired with (4,4)
// Rock should NOT teleport - it stops at warp position
const puzzle = makeBasicPuzzle({
pushableRocks: [{ x: 3, y: 1 }],
warps: [
{ x: 4, y: 1, id: 'w1' },
{ x: 4, y: 4, id: 'w1' },
],
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
// Rock should be pushed to warp position but NOT teleport
if (result.pushedRock) {
expect(result.pushedRock.to).toEqual({ x: 4, y: 1 });
}
});
it('should handle pressure plate activation then pass through barrier', () => {
// Plate at (3,1), barrier at (5,1). Slide right: cross plate, then pass barrier.
const puzzle = makeBasicPuzzle({
pressurePlate: { x: 3, y: 1 },
barrier: { x: 5, y: 1 },
});
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.crossedPressurePlate).toBe(true);
expect(result.hitBarrier).toBe(false);
// Should pass through barrier since plate was crossed in same slide
expect(result.position.x).toBeGreaterThanOrEqual(5);
});
it('should handle consecutive hot coals collisions across moves', () => {
// First hot coals stops player, so only one hot coals hit can occur per slide.
const puzzle = makeBasicPuzzle({
obstacles: [
{ x: 3, y: 1, type: 'hot_coals' },
{ x: 5, y: 1, type: 'hot_coals' },
],
});
// First slide: hit hot coals at (3,1)
const result1 = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result1.hitHotCoals).toBe(true);
expect(result1.position).toEqual({ x: 3, y: 1 });
// Second slide from hot coals position: hit hot coals at (5,1)
const result2 = slideWithHazards({ x: 3, y: 1 }, 'right', puzzle);
expect(result2.hitHotCoals).toBe(true);
expect(result2.position).toEqual({ x: 5, y: 1 });
});
it('should solve level requiring double hot coals (HP management)', () => {
// Level where optimal path goes through exactly one hot coals
const puzzle = makeBasicPuzzle({
obstacles: [
{ x: 3, y: 4, type: 'hot_coals' }, // On the way
{ x: 6, y: 4, type: 'rock' }, // Stop point
{ x: 6, y: 2, type: 'rock' }, // Stop point
],
});
const result = solve(puzzle);
// Should be solvable even with hot coals damage
if (result.solvable) {
expect(result.moves).toBeGreaterThan(0);
}
});
it('should support three hot coals landings with 5-damage hot coals model', () => {
const puzzle = makeBasicPuzzle({
width: 12,
height: 3,
start: { x: 1, y: 1 },
goal: { x: 10, y: 1 },
obstacles: [
{ x: 3, y: 1, type: 'hot_coals' },
{ x: 5, y: 1, type: 'hot_coals' },
{ x: 7, y: 1, type: 'hot_coals' },
],
});
const result = solve(puzzle);
expect(result.solvable).toBe(true);
expect(result.solution).toEqual(['right', 'right', 'right', 'right']);
});
it('should handle thin ice breaking along slide path', () => {
// Thin ice at (2,1) and (3,1). First pass breaks them.
// Second pass through same tiles should fall in hole.
const puzzle = makeBasicPuzzle({
thinIceTiles: [{ x: 2, y: 1 }, { x: 3, y: 1 }],
obstacles: [{ x: 5, y: 1, type: 'rock' }], // Stop point
});
// First slide: pass over thin ice (doesn't break in slideWithHazards, tracked by solver)
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.fellInHole).toBe(false);
expect(result.position).toEqual({ x: 4, y: 1 });
// Second slide with broken ice: should fall in hole
const brokenIce = [{ x: 2, y: 1 }, { x: 3, y: 1 }];
const result2 = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle, brokenIce);
expect(result2.fellInHole).toBe(true);
expect(result2.position).toEqual({ x: 2, y: 1 }); // Falls at first hole
});
it('should handle warp + thin ice (ice breaks on pre-warp path)', () => {
const puzzle = makeBasicPuzzle({
width: 10,
height: 8,
start: { x: 1, y: 1 },
goal: { x: 8, y: 6 },
thinIceTiles: [{ x: 2, y: 1 }], // Before warp
warps: [
{ x: 4, y: 1, id: 'w1' },
{ x: 4, y: 6, id: 'w1' },
],
});
// Slide right: cross thin ice at (2,1), hit warp at (4,1), teleport to (4,6)
const result = slideWithHazards({ x: 1, y: 1 }, 'right', puzzle);
expect(result.warpDestination).toEqual({ x: 4, y: 6 });
// Thin ice was crossed but not broken in slideWithHazards (solver tracks this)
expect(result.fellInHole).toBe(false);
});
it('solver should handle large state space without crashing', () => {
// 15x15 grid with multiple mechanics - verify solver terminates
const puzzle = makeBasicPuzzle({
width: 15,
height: 15,
start: { x: 1, y: 13 },
goal: { x: 13, y: 1 },
obstacles: [
{ x: 5, y: 13, type: 'rock' },
{ x: 5, y: 8, type: 'rock' },
{ x: 10, y: 8, type: 'rock' },
{ x: 10, y: 3, type: 'rock' },
{ x: 3, y: 3, type: 'hot_coals' },
],
thinIceTiles: [{ x: 7, y: 13 }],
pushableRocks: [{ x: 8, y: 8 }],
warps: [
{ x: 1, y: 8, id: 'w1' },
{ x: 13, y: 8, id: 'w1' },
],
});
const result = solve(puzzle);
expect(typeof result.solvable).toBe('boolean');
expect(result.iterations).toBeGreaterThan(0);
expect(result.iterations).toBeLessThanOrEqual(200000);
});
it('should not set exhausted flag for normal solvable puzzle', () => {
// Normal solvable puzzle should complete well before iteration limit
const puzzle = makeBasicPuzzle({
start: { x: 1, y: 1 },
goal: { x: 6, y: 1 },
});
const result = solve(puzzle);
expect(result.solvable).toBe(true);
// exhausted should be undefined or false for a simple solvable puzzle
expect(result.exhausted).toBeFalsy();
expect(result.iterations).toBeLessThan(200000);
});
});
