Viewing Program

Program Data

Program thumbnail for "{props.program.title}"

Title	symmetry
ID	4700425557557248
Created	5 months ago, 1722455941382
Updated	5 months ago, 1722458930359
Code	/** * Jentacular Gent * symmetry */ // jshint ignore:start const WIDTH = 5, HEIGHT = 6; function possibleBoards(board) { const boards = []; let x = 0, y = 0; for(let i = 0; i < board.length; i += 1) { if(board[i] === "1") { const possible = []; if(y > 0) possible.push(-WIDTH); if(y < HEIGHT - 1) possible.push(WIDTH); if(x > 0) possible.push(-1); if(x < WIDTH - 1) possible.push(1); for(let j = 0; j < possible.length; j += 1) { const offset = possible[j]; const newPosition = i + offset; if(board[newPosition] === "0") { let newBoard = board.substr(0, i) + "0" + board.substr(i + 1); newBoard = newBoard.substr(0, newPosition) + "1" + newBoard.substr(newPosition + 1) boards.push(newBoard); } } } x += 1; if(x >= WIDTH) { x = 0; y += 1; } } return boards; } function closest(board, already, x, y, match) { const explored = {}; const start = y WIDTH + x; let queue = [[0, start]]; explored[start] = true; while(queue.length) { const parent = queue.shift(); const y = (parent[1] / WIDTH) \| 0, x = parent[1] - y * WIDTH; const children = []; if(x > 0) children.push(parent[1] - 1); if(x < WIDTH - 1) children.push(parent[1] + 1); if(y > 0) children.push(parent[1] - WIDTH); if(y < HEIGHT - 1) children.push(parent[1] + WIDTH); for(let i = 0; i < children.length; i += 1) { const child = children[i]; if(board[child] === match && already[child] !== match) { return parent[0] + 1; } queue.push([parent[0] + 1, child]); } } } function distance(board, goal) { let cost = 0; let x = 0, y = 0; for(let i = 0; i < goal.length; i += 1) { // cost += (goal[i] === "1" && board[i] === "0"); if(goal[i] === "1" && board[i] === "0") { cost += closest(board, goal, x, y, "1"); } if(goal[i] === "0" && board[i] === "1") { cost += closest(goal, board, x, y, "1"); } x += 1; if(x >= WIDTH) { x = 0; y += 1; } } return cost; } // let start = [ // "11111", // "10011", // "11011", // "01000", // "10101", // "00110", // ].join(""); // let goal = [ // "11111", // "10101", // "01010", // "10101", // "01010", // "10101", // ].join(""); let start = Array(WIDTH * HEIGHT).fill("0"); let goal = Array(WIDTH * HEIGHT).fill("0"); const NUM_BLOCKS = random(WIDTH * HEIGHT / 2, WIDTH * HEIGHT / 2) \| 0; for(let i = 0; i < NUM_BLOCKS; i += 1) { { let j = (Math.random() * WIDTH * HEIGHT) \| 0; while(goal[j] === "1") { j = (Math.random() * WIDTH * HEIGHT) \| 0; } goal[j] = "1"; } { let j = (Math.random() * WIDTH * HEIGHT) \| 0; while(start[j] === "1") { j = (Math.random() * WIDTH * HEIGHT) \| 0; } start[j] = "1"; } } start = start.join(""); goal = goal.join(""); function solve(start, goal) { if(start === goal) { return [goal]; } const cache = [start]; let tree = {}; let score = {}; score[start] = 0; tree[start] = 1; let queue = [[0, start]]; let t = 0; while(t < 2000 && queue.length) { const newNext = []; // use an efficient priority queue implementation instead let parent = 0; for(let i = 1; i < queue.length; i += 1) { if(queue[i][0] < queue[parent][0]) parent = i; } parent = queue.splice(parent, 1)[0]; const children = possibleBoards(parent[1]); for(let i = 0; i < children.length; i += 1) { const child = children[i]; if(child === goal) { parent = parent[1]; const path = [parent, goal]; while(parent !== start) { parent = tree[parent]; path.unshift(parent); } println("searched " + t + " states") return path; } if(tree[child]) continue; tree[child] = parent[1]; score[child] = score[parent[1]] + 1; const cost = score[child] + distance(child, goal); queue.push([cost, child]); } t += 1; } println(queue.length); } const solution = solve(start, goal); if(!solution) { println("uh oh"); } let frame = 0; function mouseClicked() { frame = (frame + 1) % solution.length; } function draw() { background(255); const board = solution ? solution[frame] : start; const SIZE = 50; const totalWidth = WIDTH * SIZE, totalHeight = HEIGHT * SIZE; const xStart = width / 2 - totalWidth / 2, yStart = height / 2 - totalHeight / 2; let x = 0, y = 0; fill(0); textSize(50); textAlign(CENTER, CENTER); text(frame, width / 2, height * 0.15); noStroke(); for(let i = 0; i < board.length; i += 1) { if(board[i] === "1" && goal[i] === "0") fill(255, 0, 0); else if(board[i] === "1" && goal[i] === "1") fill(0, 255, 0); else if(board[i] === "0" && goal[i] === "1") fill(0, 0, 255, 20); if(board[i] === "1" \|\| goal[i] === "1") rect(xStart + x * SIZE + 10, yStart + y * SIZE + 10, SIZE - 20, SIZE - 20, 10); x += 1; if(x >= WIDTH) { x = 0; y += 1; } } } random();
Folds
Fork	false
Key	ag5zfmtoYW4tYWNhZGVteXIXCxIKU2NyYXRjaHBhZBiAgJvdseCsCAw
Votes	1
Spin-Offs	0
Type	PJS
Width	600
Height	600
User Flagged	false
Origin Scratchpad	null
Hidden From Hotlist	false
Restricted Posting	true
By Child	false
Author Nick	JentGent
Author Name	JentacularGent
Author ID	kaid_1111444645373975142506044
Author Profile Access	COACH

Archive Data

Added	5 months ago, 1722459125359
Updated	5 months ago, 1722459125359
Source Deleted	unknown