// inRange function: Alexander (via Stack Overflow)
// Lesson: Keith Schwarz (via keithschwarz.com)
// Walls do not work, otherwise perfect!
// Shorthand Key:
// p = puzzle
// t = toggle
// x = horizontal index / column number
// y = vertical index / row number
// w = temporary width
// h = temporary height
// i = index
// j = jindex
// next = next free row
//
// Variables
//
// initial matrices
var puzzle = [];
var toggle = [];
var solution = [];
// initial variables
var width = 0;
var height = 0;
var area = 0;
var inputMode = 0;
// elements
const table = document.querySelector("tbody");
const form = document.getElementById("options");
const submit = document.querySelector("caption");
const select = document.querySelector("select");
//
// Matrix Functions
//
// check if coords (x, y) are in bounds
function inBounds(x, y) {
return 0 <= y && y < height && 0 <= x && x < width
}
//
// Create the puzzle and its corresponding arrays
//
// update width, height, and area
function update() {
let formData = new FormData(form);
for (const entry of formData.entries()) {
if (entry[0] == "width") width = Math.round(entry[1]);
if (entry[0] == "height") height = Math.round(entry[1]);
if (entry[0] == "mode") inputMode = entry[1];
}
area = width * height;
}
// update dimensions, populate display
function populate() {
select.value = "lights";
update();
// populate
table.replaceChildren();
puzzle = Array(area).fill(true);
toggle = Array.from({ length: area }, () => Array(area).fill(false));
for (let y = 0; y < height; y++) {
table.insertRow();
for (let x = 0; x < width; x++) {
let i = x + y * width;
// table, puzzle
table.rows[y].insertCell().addEventListener("click", function () {
update();
let cells = table.querySelectorAll("td")
this.classList.remove("solution");
if (inputMode == "lights") {
this.classList.toggle("off");
puzzle[i] = !cells[i].classList.contains("off");
} else if (inputMode == "walls") {
this.classList.toggle("wall");
puzzle[i] = cells[i].classList.contains("wall") ? null : cells[i].classList.contains("off");
} else if (inputMode == "play") {
for (let j = 0; j < toggle[y].length; j++) {
if (toggle[i][j]) {
cells[j].classList.toggle("off");
puzzle[j] = !cells[j].classList.contains("off");
}
}
}
});
// toggle
for (let yOff = -1; yOff <= 1; yOff++) {
for (let xOff = -1; xOff <= 1; xOff++) {
let [xNew, yNew] = [x + xOff, y + yOff];
if (Math.abs(xOff) + Math.abs(yOff) < 2 && inBounds(xNew, yNew)) {
toggle[x + y * width][xNew + yNew * width] = true;
}
}
}
}
};
}
//
// Find Solution
//
// return the solution to a puzzle array using a toggle matrix
function solve(puzzle, toggle) {
// initialize s, create new copies of p and t
let p = puzzle.slice(0);
let t = toggle.map((arr) => {return arr.slice(0)});
let s = new Array(area).fill(false);
// gaussian elimination
let yNext = 0;
for (let x = 0; x < area; x++) {
// find next pivot row
let pivot = -1;
for (let y = yNext; y < area; y++) {
if (t[y][x]) {
pivot = y;
break
}
}
if (pivot == -1) continue
// swap index of pivot row and next row in toggle and puzzle
[t[pivot], t[yNext]] = [t[yNext], t[pivot]];
[p[pivot], p[yNext]] = [p[yNext], p[pivot]];
// apply XOR to each row after the pivot with a true value in the same column
for (let y = pivot + 1; y < area; y++) {
if (t[y][x]) {
for (let i = 0; i < area; i++) {
t[y][i] = t[y][i] ? !t[yNext][i] : t[yNext][i];
}
p[y] = p[y] ? !p[yNext] : p[yNext];
}
}
// increase next row
yNext++;
}
// back substitute
for (let y = area; y-- > 0;) {
// find the next pivot column
let pivot = -1;
for (let x = 0; x < area; x++) {
if (t[y][x]) {
pivot = x;
break
}
}
if (pivot == -1 && p[y]) {
return null
}
// perform back substitution (more magic)
s[y] = p[y];
for (let x = pivot + 1; x < area; x++) {
s[y] = (s[y] != (t[y][x] && s[x]));
}
}
// end
return s
}
//
// Controls
//
form.addEventListener("submit", function (e) {
e.preventDefault();
populate();
});
submit.addEventListener("click", function () {
solution = solve(puzzle, toggle);
// show solution
if (solution == null) {
submit.innerHTML = "No Solution";
} else {
submit.innerHTML = "Done";
select.value = "play";
for (let i = 0; i < area; i++) {
if (solution[i]) {
table.querySelectorAll("td")[i].classList.add("solution");
}
}
}
update();
setTimeout(() => submit.innerHTML = "Solve", 1000);
});
populate();
body {
/* base size */
--mult: 30px;
/* margins */
--margin: calc(var(--mult) * 0.1);
--margin2: calc(var(--margin) * 0.5);
/* space between elements */
--gap: calc(var(--mult) * 0.3);
/* input heights */
--input: calc(var(--mult) * 1.5);
--select: calc(var(--input) * 0.5);
/* colors */
--main-bg: rgb(245, 245, 245);
--ui-bg-on: rgb(235, 235, 235);
--ui-bg-off: rgb(195, 195, 195);
/* default border */
--border: var(--margin) solid rgb(155, 155, 155);
--solution: var(--margin) solid rgb(255, 0, 0);
/* font style */
font-size: 30px;
font-family: Arial, Helvetica, sans-serif;
margin: 0;
#lightsOut {
width: fit-content;
background: var(--main-bg);
border: var(--border);
display: flex;
line-height: var(--input);
#display {
margin: var(--margin);
border-collapse: collapse;
tbody {
tr {
z-index: 0;
td {
cursor: pointer;
position: relative;
box-sizing: border-box;
z-index: 0;
width: var(--input);
height: var(--input);
background: var(--ui-bg-on);
border: var(--border);
&.off {
background: var(--ui-bg-off);
}
&.solution::after {
width: var(--gap);
height: var(--gap);
content: "";
display: flex;
position: relative;
margin: auto;
border-radius: 100%;
background-color: black;
}
&.wall {
background: none;
border: none;
}
}
}
}
caption {
cursor: pointer;
box-sizing: border-box;
caption-side: bottom;
width: 100%;
height: var(--input);
font-size: var(--mult);
background: var(--ui-bg-on);
margin-top: var(--margin);
border: var(--border);
user-select: none;
}
}
#options {
margin: var(--margin);
margin-left: 0;
margin-top: calc(var(--margin) + var(--margin2));
label {
box-sizing: border-box;
height: var(--input);
font-size: var(--mult);
margin: var(--margin2), 0;
display: flex;
user-select: none;
gap: var(--gap);
input[type=number],
select {
flex: right;
width: var(--input);
height: var(--mult);
font-size: var(--mult);
text-align: center;
margin-left: auto;
padding: 0;
margin-top: auto;
margin-bottom: auto;
}
select {
font-size: var(--select);
text-align: left;
width: auto;
}
}
button {
cursor: pointer;
height: var(--input);
font-size: var(--mult);
background: var(--ui-bg-on);
border: var(--border);
margin: var(--margin2), 0;
user-select: none;
width: 100%;
display: block;
}
}
}
}
input[type=number]::-webkit-inner-spin-button,
input[type=number]::-webkit-outer-spin-button {
opacity: 1;
}
<!DOCTYPE html>
<html>
<body>
<div id="lightsOut">
<table id="display">
<tbody>
</tbody>
<caption>
Solve
</caption>
</table>
<form id="options">
<label>
Width:
<input name="width" type="number" value="3" min="3" max="9" required>
</label>
<label>
Height:
<input name="height" type="number" value="3" min="3" max="9" required>
</label>
<button>
Reset
</button>
<label>
Input:
<select name="mode">
<option value="lights">Lights</option>
<option value="walls">Walls</option>
<option value="play">Play</option>
</select>
</label>
</form>
</div>
</body>
<head>
<link rel="stylesheet" href="LO.css">
<script src="LO.js"></script>
</head>
</html>