Public
Edited
Dec 14, 2022
2 forks
2 stars
Insert cell
Insert cell
test = `498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
`
Insert cell
testPaths = parsePaths(test)
Insert cell
function parsePaths(input) {
return input.trim().split("\n").map(parsePath);
}
Insert cell
function parsePath(input) {
return input.split(" -> ").map(parseCoordinate);
}
Insert cell
function parseCoordinate(input) {
return input.split(",").map(Number);
}
Insert cell
visualizePaths(testPaths)
Insert cell
function visualizePaths(paths) {
return Plot.plot({
grid: true,
inset: 10,
y: {
reverse: true
},
marks: [
Plot.dot({length: 1}, {x: [500], y: [0], stroke: "red", symbol: "plus"}), // sand origin
paths.map((path) => Plot.line(path))
]
});
}
Insert cell
testGrid = createGrid(testPaths)
Insert cell
function createGrid(paths) {
const [x1, x2] = d3.extent(paths.flat(), ([x]) => x);
const y1 = 0;
const [, y2] = d3.extent(paths.flat(), ([, y]) => y);
const n = y2 - y1 + 1;
const m = x2 - x1 + 1;
const values = new Array(n * m).fill(null);
const grid = new Grid({x1, y1, x2, y2, values});
for (const i of traversePaths(grid, paths)) values[i] = "rock";
values[grid.indexAt(500, 0)] = "source";
return grid;
}
Insert cell
class Grid {
constructor({x1, y1, x2, y2, values}) {
this.x1 = x1;
this.x2 = x2;
this.y1 = y1;
this.y2 = y2;
this.n = y2 - y1 + 1;
this.m = x2 - x1 + 1;
this.values = values;
}
valueAt(x, y) {
return this.values[this.indexAt(x, y)];
}
indexAt(x, y) {
if (this.x1 <= x && x <= this.x2 && this.y1 <= y && y <= this.y2) {
return (y - this.y1) * this.m + (x - this.x1);
}
}
copy() {
return new Grid({...this, values: this.values.slice()});
}
}
Insert cell
function* traversePaths(grid, paths) {
for (const path of paths) {
yield* traversePath(grid, path);
}
}
Insert cell
function* traversePath(grid, path) {
const n = path.length;
let [x, y] = path[0];
let index = grid.indexAt(x, y);
yield index;
for (let i = 1; i < n; ++i) {
const [xi, yi] = path[i];
while (y > yi) x, --y, yield index -= grid.m;
while (y < yi) x, ++y, yield index += grid.m;
while (x > xi) --x, y, yield --index;
while (x < xi) ++x, y, yield ++index;
}
}
Insert cell
visualizeGrid(testGrid)
Insert cell
function visualizeGrid(grid, {width = 640, ...options} = {}) {
const plot = Plot.plot({
grid: true,
round: true,
width,
height: Math.floor((grid.n / grid.m) * width * 0.8) + 20,
...options,
x: {domain: [grid.x1 - 0.5, grid.x2 + 0.5]},
y: {domain: [grid.y2 + 0.5, -0.5]},
color: {
domain: ["rock", "sand", "source"],
range: ["#5a4d41", "#c2b280", "red"]
},
marks: [
Plot.rect(grid.values, {
x1: (d, i) => grid.x1 + i % grid.m - 0.5,
y1: (d, i) => grid.y1 + Math.floor(i / grid.m) - 0.5,
x2: (d, i) => grid.x1 + i % grid.m + 0.5,
y2: (d, i) => grid.y1 + Math.floor(i / grid.m) + 0.5,
fill: (d) => d
})
]
});
plot.value = grid;
return plot;
}
Insert cell
{
for (const g of simulate(testGrid)) {
yield visualizeGrid(g);
}
}
Insert cell
function* simulate(grid, ox = 500, oy = 0) {
let grains = 0;
grid = grid.copy();
while (true) {
let x = ox;
let y = oy;
let value = "source";
grid.grains = grains;
while (true) {
yield grid;
let x1 = x;
let y1 = y;
if (!grid.valueAt(x, y + 1)) ++y1;
else if (!grid.valueAt(x - 1, y + 1)) --x1, ++y1;
else if (!grid.valueAt(x + 1, y + 1)) ++x1, ++y1;
else if (x === ox && y === oy) return; // full
else break; // sand at rest
if (x !== ox || y !== oy) grid.values[grid.indexAt(x, y)] = null;
if (x1 < grid.x1 || x1 > grid.x2 || y1 > grid.y2) return yield grid; // into the void
grid.values[grid.indexAt(x = x1, y = y1)] = "sand";
}
++grains;
}
}
Insert cell
input = FileAttachment("input.txt").text()
Insert cell
paths = parsePaths(input)
Insert cell
grid = createGrid(paths)
Insert cell
{
let i = 0;
for (const g of simulate(grid)) {
if (++i % 40 === 0) {
yield visualizeGrid(g);
}
}
}
Insert cell
{
let grains;
for (const g of simulate(grid)) {
grains = g.grains;
}
return grains;
}
Insert cell
function createGridWithFloor(paths) {
let [x1, x2] = d3.extent(paths.flat(), ([x]) => x);
const y1 = 0;
const y2 = d3.max(paths.flat(), ([, y]) => y) + 2;
x1 = 500 - y2;
x2 = 500 + y2;
const n = y2 - y1 + 1;
const m = x2 - x1 + 1;
const values = new Array(n * m).fill(null);
const grid = new Grid({x1, y1, x2, y2, values});
for (const i of traversePaths(grid, paths)) values[i] = "rock";
for (const i of traversePath(grid, [[x1, y2], [x2, y2]])) values[i] = "rock"; // floor
values[grid.indexAt(500, 0)] = "source";
return grid;
}
Insert cell
testGrid2 = createGridWithFloor(testPaths)
Insert cell
viewof testSimulation = {
let i = 0;
for (const g of simulate(testGrid2)) {
yield visualizeGrid(g);
}
}
Insert cell
testSimulation.grains
Insert cell
grid2 = createGridWithFloor(paths)
Insert cell
{
let i = 0;
let grains;
for (const g of simulate(grid2)) {
grains = g.grains;
}
yield grains + 1;
}
Insert cell
{
let i = 0;
for (const g of simulate(grid2)) {
if (++i % 10000 === 0) {
// yield visualizeGrid(g, {width: 1152});
}
}
}
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more