Fractals and Automatons

_list.md

1. Koch Snowflake
2. Toothpick Pattern
3. Ulam Warburton Cellular Automaton
4. Hilbert's Curve

hilbert.js

m = [
    [' ', ' ', ' ', ' ', ' ', ' '],
    [' ', '*', '*', '*', '*', ' '],
    [' ', '*', ' ', ' ', '*', ' '],
    [' ', '*', ' ', ' ', '*', ' '],
    [' ', '*', ' ', ' ', '*', ' '],
    [' ', ' ', ' ', ' ', ' ', ' ']
]

function merge2(m) {
  let [m1, m2] = m
  m1 = m1.reduce((acc, x, i) => [...acc, (acc[i]||[]).concat(x)], [])
  m2 = m2.reduce((acc, x, i) => [...acc, (m1[i]||[]).concat(x)], [])
  return m2
}
function merge(m) {
  let [m1, m2] = m
  mm1 = merge2(m1)
  mm2 = merge2(m2)
  
  n = mm1.length
  mm1[n-2][n-1]   = '*'
  mm1[n-2][n]     = '*'
  mm1[n-1][1]     = '*'
  mm1[n-1][2*n-2] = '*'
  mm2[0][1]       = '*'
  mm2[0][n*2-2]   = '*'
  
  return mm1.concat(mm2)
}
function pretty(xs) {
  console.log(xs.map(ys => ys.join(' ')).join('\n'))
}
function box(m) {
  return [[m, m], [rotate(m), transpose(m)]]
}
function transpose(m) {
  let n = m.length
  let t =Array(n).fill(0).map(_ => Array(n).map(_ => 0))
  for (let i=0;i<n;i++) {
    for (let j=0;j<n;j++) {
      t[j][i] = m[i][j]  
    }
  }
  return t
}
function rotate(m) {
  let n = m.length
  let t =Array(n).fill(0).map(_ => Array(n).map(_ => 0))
  for (let i=0;i<n;i++) {
    for (let j=0;j<n;j++) {
      t[i][j] = m[n-1-j][i]  
    }
  }
  return t
}

pretty(merge(box(merge(box(m)))))
// pretty(merge(box(merge(box(merge(box(merge(box(m)))))))))

// REPL.IT: https://repl.it/@MelwynSaldanha/HilbertsCurveASCII

koch.p5.js

const slope = ([x1, y1], [x2, y2]) => (y2 - y1) / (x2 - x1);
const square = x => x * x;
const distance = ([x1, y1], [x2, y2]) => Math.sqrt(square(x2 - x1) + square(y2 - y1));

const ROOT_3 = 1.732;
const TWO_ROOT_3 = 2 * ROOT_3;

const MIN_SIDE_LENGTH = 3;

const Queue = () => {
  const queue = [];
  return {
    enqueue: x => queue.push(x),
    dequeue: () => queue.shift(),
    isEmpty: () => queue.length === 0,
    size: () => queue.length,
  };
};

const queue = Queue();

const drawLine = ([x1, y1], [x2, y2]) => line(x1, y1, x2, y2);

const isInsideTriangle = (px, p1, p2, p3) => {
  const length = distance(p1, p2);
  const l1 = distance(px, p1);
  const l2 = distance(px, p2);
  const l3 = distance(px, p3);
  return l1 < length && l2 < length && l3 < length;
}

const explore = (p1, p2, p3, getPoints) => {
  stroke(200);
  drawLine(p1, p2);
  
  stroke(0);
  const length = distance(p1, p2);
  const [_p1, _p2, _p3, _px, _py] = getPoints(p1, p2, p3, length);  
  if (+Math.floor(distance(_p1, _p2)) > MIN_SIDE_LENGTH) {
    queue.enqueue([p1, _p1, _px]);
    queue.enqueue([p2, _p2, _py]);
    queue.enqueue([_p1, _p3, _p2]);
    queue.enqueue([_p2, _p3, _p1]);
  }
  drawLine(p1, _p1);
  drawLine(p2, _p2);
  drawLine(_p1, _p3)
  drawLine(_p2, _p3)
}

const getPointsZeroSlope = (p1, p2, p3, length) => {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  const _p1 = [x1 - length/3, y1];
  const _p2 = [x2 + length/3, y2];
  let _p3 = [x2 + (length/2), y2 + (length/TWO_ROOT_3)]; 

  let _px, _py;
  if (isInsideTriangle(_p3, p1, p2, p3)) {
    _px = [x1 - length/6, y1 + (length/TWO_ROOT_3)];
    _py = [x2 + length/6, y2 + (length/TWO_ROOT_3)];
    _p3 = [x2 + (length/2), y2 - (length/TWO_ROOT_3)];
  } else {
    _px = [x1 - length/6, y1 - (length/TWO_ROOT_3)];
    _py = [x2 + length/6, y2 - (length/TWO_ROOT_3)];
    _p3 = [x2 + (length/2), y2 + (length/TWO_ROOT_3)];
  }
  return [_p1, _p2, _p3, _px, _py];
}

const getPointsNegativeSlope = (p1, p2, p3, length) => {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  const _p1 = [x1 + length/6, y1 - (length/TWO_ROOT_3)];
  const _p2 = [x1 + length/3, y1 - (length/ROOT_3)];
  let _p3 = [x1, y1 - (length/ROOT_3)]; 
  
  let _px, _py;
  if (isInsideTriangle(_p3, p1, p2, p3)) {
    _px = [x1 - length/6, y1 - length/TWO_ROOT_3];
    _py = [x1 + length/6, y2];
    _p3 = [x1 + length/2, y1 - (length/TWO_ROOT_3)];
  } else {
    _px = [x1 + length/3, y1];
    _py = [x1 + 2*length/3, y1 - (length/ROOT_3)];
    _p3 = [x1, y1 - (length/ROOT_3)];
  }
  return [_p1, _p2, _p3, _px, _py];
}

const getPointsPositiveSlope = (p1, p2, p3, length) => {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  const _p1 = [x1 - length/6, y1 - (length/TWO_ROOT_3)];
  const _p2 = [x1 - length/3, y1 - (length/ROOT_3)];
  let _p3 = [x1, y1 - (length/ROOT_3)]; 
  
  let _px, _py;
  if (isInsideTriangle(_p3, p1, p2, p3)) {
    _px = [x1 + length/6, y1 - length/TWO_ROOT_3];
    _py = [x1 - length/6, y2];
    _p3 = [x1 - length/2, y1 - (length/TWO_ROOT_3)];
  } else {
    _px = [x1 - length/3, y1];
    _py = [x1 - 2*length/3, y1 - (length/ROOT_3)];
    _p3 = [x1, y1 - (length/ROOT_3)];
  }
  return [_p1, _p2, _p3, _px, _py];
}

const baseLogic = (points) => {
  const [p1, p2, p3] = getOrder(points);
  const m = slope(p1, p2);
  if (m == 0) explore(p1, p2, p3, getPointsZeroSlope);
  if (m < 0) explore(p1, p2, p3, getPointsNegativeSlope);
  if (m > 0) explore(p1, p2, p3, getPointsPositiveSlope);
}

const getOrder = ([p1, p2, p3]) => {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  if (y1 === y2) {
    if (x1 > x2) return [p1, p2, p3];
    return [p2, p1, p3];
  } else {
    if (y1 > y2) return [p1, p2, p3];
    return [p2, p1, p3];
  }
}

function setup() {
  createCanvas(500, 400);
  background(200);
  
  const p1 = [400, 300];
  const p2 = [100, 300];
  const length = distance(p1, p2);
  const p3 = [p2[0] + (length/2), p2[1] - (1.732/2) * length];
  queue.enqueue([p2, p1, p3]);
  queue.enqueue([p3, p2, p1]);
  queue.enqueue([p3, p1, p2]);
  
  
  while (!queue.isEmpty()) {
    baseLogic(queue.dequeue());  
  }
}

toothpick.p5.js

const WIDTH = 400;
const HEIGHT = 400;
const FRAME_RATE = 20;
const GENERATIONS = 128;
const TOOTHPICK = 7;
let horizontal = true;
let currentGeneration = 1;
let newFreeEnds = [
  [WIDTH / 2, HEIGHT / 2],
  [WIDTH / 2, HEIGHT / 2 + TOOTHPICK]
];

function Set() {
  const set = {};
  return {
    exists: v => !!set[v],
    add: v => set[v] = true,
    print: () => console.log(Object.keys(set))
  }
}

const $set = new Set();
const k = (x, y) => `${x}_${y}`;

function getLineEnds(x1, y1, orientation) {
  return orientation ? [
    [x1 - TOOTHPICK / 2, y1],
    [x1 + TOOTHPICK / 2, y1]
  ] : [
    [x1, y1 - TOOTHPICK / 2],
    [x1, y1 + TOOTHPICK / 2]
  ]
}

function toothpick(freeEnds) {
  if (currentGeneration === GENERATIONS) return noLoop();
  const pointsToRemove = [];
  const newFreeEnds = freeEnds.flatMap(([x, y]) => {
    const [
      [x1, y1],
      [x2, y2]
    ] = getLineEnds(x, y, horizontal);
    line(x1, y1, x2, y2);
    if ($set.exists(k(x1, y1))) pointsToRemove.push(k(x1, y1));
    if ($set.exists(k(x2, y2))) pointsToRemove.push(k(x2, y2));
    $set.add(k(x1, y1));
    $set.add(k(x2, y2));
    return [
      [x1, y1],
      [x2, y2]
    ];
  }).filter(([x, y]) => !pointsToRemove.includes(k(x, y)))
  horizontal = !horizontal;
  currentGeneration++;
  return newFreeEnds;
}

function setup() {
  frameRate(FRAME_RATE);
  createCanvas(WIDTH, HEIGHT);

  background(220);
  line(WIDTH / 2, HEIGHT / 2, WIDTH / 2, HEIGHT / 2 + TOOTHPICK);
  $set.add(k(WIDTH / 2, HEIGHT / 2));
  $set.add(k(WIDTH / 2, HEIGHT / 2 + TOOTHPICK));
}

function draw() {
  newFreeEnds = toothpick(newFreeEnds);
}

ulam_warburton.p5.js

const SIDE = 5;
const HEIGHT = 400;
const WIDTH = 400;
const FRAME_RATE = 10;
const GENERATIONS = 32;
let currentGeneration = 0;

const cells = Array.from(Array(WIDTH + 1), _ => Array.from(Array(HEIGHT + 1), _ => 0))

const drawPoint = (x, y) => {
  if (cells[x][y] === 1) {
    fill('blue');
    rect(x, y, SIDE, SIDE);
    $set.add(k(x, y));
  }
}

function Queue() {
  const queue = [];
  return {
    enqueue: v => queue.push(v),
    dequeue: () => queue.shift(),
  }
}

function Set() {
  const set = {};
  return {
    exists: v => !!set[v],
    add: v => set[v] = true,
    print: () => console.log(Object.keys(set))
  }
}

const $queue = new Queue();
const $set = new Set();
const k = (x, y) => `${x}_${y}`;

const neighbours = (x, y) => {
  const n = [];
  if (!$set.exists(k(x+SIDE, y))) {
    ++cells[x+SIDE][y]
    n.push([x+SIDE, y])
  }
  if (!$set.exists(k(x-SIDE, y))) {
    ++cells[x-SIDE][y]
    n.push([x-SIDE, y])
  }
  if (!$set.exists(k(x, y+SIDE))) {
    ++cells[x][y+SIDE]
    n.push([x, y+SIDE])
  }
  if (!$set.exists(k(x, y-SIDE))) {
    ++cells[x][y-SIDE]
    n.push([x, y-SIDE])
  }
  return n;
};

function setup() {
  frameRate(FRAME_RATE);
  createCanvas(WIDTH, HEIGHT);
  background(220);

  $queue.enqueue([WIDTH/2, HEIGHT/2]);
  cells[WIDTH/2][HEIGHT/2] = 1;
}

function draw() {
  if (currentGeneration > GENERATIONS) return noLoop();
  const ns = [];
  while (true) {
    const p = $queue.dequeue();
    if (!p) break;
    const [x, y] = p;
    drawPoint(x, y);
    const n = neighbours(x, y);
    ns.push(n);
  }
  ns.flatMap(xs => xs).forEach(([x, y]) => cells[x][y] === 1 && $queue.enqueue([x, y]));
  currentGeneration++;
}