Genuary 2025 day 25

// By Roni Kaufman

// https://ronikaufman.github.io

​

// Made for Genuary 2025

// Day 25: One line that may or may not intersect itself.

​

const M = 8, N = M;

let path = [], p;

​

function setup() {

  createCanvas(500, 500);

  pixelDensity(2);

  noFill();

  stroke(5);

  strokeWeight(3);

  p = [2*~~random(M/2), 2*~~random(N/2)]; // starting point

}

​

function draw() {

  background("#fffbe6");

  let eventualNeighbors = possibleNeighbors(p, M, N);

  shuffle(eventualNeighbors, true);

  let neighbors = [[], []];

  for (let neigh of eventualNeighbors) {

    let projectedPath = [...path, p, neigh];

    let count = countDeadends(projectedPath, possibleNeighbors(neigh, M, N), M, N);

    if (!inArray(neigh, path) && !disjointed(projectedPath, M, N) && count < 2 && !cursedCorners(projectedPath, M, N)) {

      neighbors[count].push(neigh);

    }

  }

  neighbors = neighbors.flat(1);

  while (neighbors.length == 0) {

    // backtracking

    let previous = path.pop();

    p = [previous[0], previous[1]];

    neighbors = previous[2];

  }

  let pNext = neighbors.shift();

  path.push([...p, neighbors]);

  p = pNext;

  let drawnPath = getDrawnPath(path, p);

  let margin = 50;

  let nLines = 5;

  let step = 1/nLines;

  let c = step/2;

  //strokeWeight(step*(width-2*margin)/(2*M));

  for (let i = 0; i < drawnPath.length; i++) {

    for (let j = 0; j < nLines; j++) {

      let v = (2*j+1)*step-1;

      let connectingExtremity = j % 2 == 0 && j < nLines-1;

      drawPathPortion(drawnPath, i, margin, margin, width-2*margin, height-2*margin, M, N, v, c, step, connectingExtremity);

    }

  }

  if (path.length == M*N-1) {

    noLoop();

  }

}

​

// computing

​

function possibleNeighbors([i, j], m, n) {

  let possibilities = [];

  if (j < n-1) possibilities.push([i, j+1]);

  if (j > 0) possibilities.push([i, j-1]);

  if (i < m-1) possibilities.push([i+1, j]);

  if (i > 0) possibilities.push([i-1, j]);

  return possibilities;

}

​

function inArray([i, j], arr) {

  for (let e of arr) {

    if (e[0] == i && e[1] == j) return true;

  }

  return false;

}

​

// does arr disjoint the m*n grid?

function disjointed(arr, m, n) {

  if (arr.length >= m*n) {

    return false;

  }

  // choose initial point

  let p;

  do {

    p = [~~random(m), ~~random(n)];

  } while (inArray(p, arr))

  // traverse the m*n grid where arr was removed, through a DFS

  let discovered = [];

  let stack = [p];

  while (stack.length > 0) {

    p = stack.pop();

    if (!inArray(p, discovered)) {

      discovered.push(p);

      let neighbors = possibleNeighbors(p, m, n);

      for (let neigh of neighbors) {

        if (!inArray(neigh, arr)) stack.push(neigh);

      }

    }

  }

  return discovered.length != m*n-arr.length;

}

​

function countDeadends(arr, ignoreMe, m, n) {

  let count = 0;

  for (let i = 0; i < m; i++) {

    for (let j = 0; j < n; j++) {

      if (!inArray([i, j], arr) && !inArray([i, j], ignoreMe)) {

        let eventualNeighbors = possibleNeighbors([i, j], m, n);

        let neighbors = [];

        for (let neigh of eventualNeighbors) {

          if (!inArray(neigh, arr)) neighbors.push(neigh);

        }

        if (neighbors.length < 2) {

          count++;

        }

      }

    }

  }

  return count;

}

​

function cursedCorners(arr, M, N) {

  let corner1 = !inArray([0, 0], arr) && !inArray([1, 0], arr) && !inArray([0, 1], arr) && !inArray([1, 1], arr) && !inArray([2, 0], arr) && !inArray([0, 2], arr) && inArray([2, 1], arr) && inArray([1, 2], arr) && inArray([2, 2], arr);

  let corner2 = !inArray([M-1, 0], arr) && !inArray([M-2, 0], arr) && !inArray([M-1, 1], arr) && !inArray([M-2, 1], arr) && !inArray([M-3, 0], arr) && !inArray([M-1, 2], arr) && inArray([M-3, 1], arr) && inArray([M-2, 2], arr) && inArray([M-3, 2], arr);

  let corner3 = !inArray([M-1, N-1], arr) && !inArray([M-2, N-1], arr) && !inArray([M-1, N-2], arr) && !inArray([M-2, N-2], arr) && !inArray([M-3, N-1], arr) && !inArray([M-1, N-3], arr) && inArray([M-3, N-2], arr) && inArray([M-2, N-3], arr) && inArray([M-3, N-3], arr);

  let corner4 = !inArray([0, N-1], arr) && !inArray([1, N-1], arr) && !inArray([0, N-2], arr) && !inArray([1, N-2], arr) && !inArray([2, N-1], arr) && !inArray([0, N-3], arr) && inArray([2, N-2], arr) && inArray([1, N-3], arr) && inArray([2, N-3], arr);

  return corner1 || corner2 || corner3 || corner4;

}

​

function connected(arr, e1, e2) {

  for (let k = 0; k < arr.length-1; k++) {

    let a1 = arr[k], a2 = arr[k+1];

    if (((a1[0] == e1[0] && a1[1] == e1[1]) && (a2[0] == e2[0] && a2[1] == e2[1])) || ((a2[0] == e1[0] && a2[1] == e1[1]) && (a1[0] == e2[0] && a1[1] == e2[1])))

      return true;

  }

  return false;

}

​

// drawing

​

function getDrawnPath(path, p) {

  let drawnPath = [];

  for (let k = 0; k < path.length-1; k++) {

    let p0 = path[k], p1 = path[k+1];

    drawnPath.push(p0);

    if (abs(p0[0]-p1[0]) > 1 || abs(p0[1]-p1[1]) > 1) {

      drawnPath.push([(p0[0]+p1[0])/2, (p0[1]+p1[1])/2]);

    }

  }

  drawnPath.push(path[path.length-1]);

  drawnPath.push(p);

  return drawnPath;

}

​

function getDirection(pA, pB) {

  if (pA[0] == pB[0]) {

    if (pA[1] > pB[1]) return "down";

    else return "up";

  } else {

    if (pA[0] > pB[0]) return "right";

    else return "left";

  }

}

​

function drawExtremity(path, start, sx, sy, v, c, d, connectingExtremity, otherExtremitysDir) {

  let i = 0, j = 1;

  if (!start) {

    i = path.length-1;

    j = path.length-2;

  }

  let p0 = path[i];

  let p1 = path[j];

  let dir = getDirection(p0, p1);

  strokeCap(PROJECT);

  if (dir == "down") {

    if (start) {

      line((p0[0]+(1+v)/2)*sx, p0[1]*sy, (p0[0]+(1+v)/2)*sx, (p0[1]+1-c)*sy);

    } else {

      line((p0[0]+(1-v)/2)*sx, p0[1]*sy, (p0[0]+(1-v)/2)*sx, (p0[1]+1-c)*sy);

    }

    let offset = 0;

    if (!start && (otherExtremitysDir == "up" || otherExtremitysDir == "right")) offset = d;

    if (connectingExtremity) line((p0[0]+(1+v)/2+offset)*sx, (p0[1]+1-c)*sy, (p0[0]+(1+v)/2+d+offset)*sx, (p0[1]+1-c)*sy);

  } else if (dir == "up") {

    if (start) {

      line((p0[0]+(1-v)/2)*sx, (p0[1]+c)*sy, (p0[0]+(1-v)/2)*sx, (p0[1]+1)*sy);

    } else {

      line((p0[0]+(1+v)/2)*sx, (p0[1]+c)*sy, (p0[0]+(1+v)/2)*sx, (p0[1]+1)*sy);

    }

    let offset = 0;

    if (!start && (otherExtremitysDir == "down" || otherExtremitysDir == "left")) offset = d;

    if (connectingExtremity) line((p0[0]+(1+v)/2+offset)*sx, (p0[1]+c)*sy, (p0[0]+(1+v)/2+d+offset)*sx, (p0[1]+c)*sy);

  } else if (dir == "left") {

    if (start) {

      line((p0[0]+c)*sx, (p0[1]+(1+v)/2)*sy, (p0[0]+1)*sx, (p0[1]+(1+v)/2)*sy);

    } else {

      line((p0[0]+c)*sx, (p0[1]+(1-v)/2)*sy, (p0[0]+1)*sx, (p0[1]+(1-v)/2)*sy);

    }

    let offset = 0;

    if (!start && (otherExtremitysDir == "right" || otherExtremitysDir == "up")) offset = d;

    if (connectingExtremity) line((p0[0]+c)*sx, (p0[1]+(1+v)/2+offset)*sy, (p0[0]+c)*sx, (p0[1]+(1+v)/2+d+offset)*sy);

  } else {

    if (start) {

      line(p0[0]*sx, (p0[1]+(1-v)/2)*sy, (p0[0]+1-c)*sx, (p0[1]+(1-v)/2)*sy);

    } else {

      line(p0[0]*sx, (p0[1]+(1+v)/2)*sy, (p0[0]+1-c)*sx, (p0[1]+(1+v)/2)*sy);

    }

    let offset = 0;

    if (!start && (otherExtremitysDir == "left" || otherExtremitysDir == "down")) offset = d;

    if (connectingExtremity) line((p0[0]+1-c)*sx, (p0[1]+(1+v)/2+offset)*sy, (p0[0]+1-c)*sx, (p0[1]+(1+v)/2+d+offset)*sy);

  }

}

​

function drawPathPortion(path, k, x0, y0, w, h, m, n, v, c, d, connectingExtremity) {

  push();

  translate(x0, y0);

  let sx = w/m, sy = h/n;

  if (k == 0) {

    let otherExtremitysDir = getDirection(path[path.length-1], path[path.length-2]);

    drawExtremity(path, true, sx, sy, v, c, d, connectingExtremity, otherExtremitysDir);

  } else if (k == path.length-1) {

    let otherExtremitysDir = getDirection(path[0], path[1]);

    drawExtremity(path, false, sx, sy, v, c, d, connectingExtremity, otherExtremitysDir);

  } else {

    let p0 = path[k-1];

    let p1 = path[k];

    let p2 = path[k+1];

    let dir01 = getDirection(p0, p1);

    let dir12 = getDirection(p1, p2);

    if (dir01 == dir12) {

      if (dir01 == "down") {

        line((p1[0]+(1+v)/2)*sx, p1[1]*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+1)*sy);

      } else if (dir01 == "up") {

        line((p1[0]+(1-v)/2)*sx, p1[1]*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+1)*sy);

      } else if (dir01 == "left") {

        line(p1[0]*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+1)*sx, (p1[1]+(1+v)/2)*sy);

      } else {

        line(p1[0]*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+1)*sx, (p1[1]+(1-v)/2)*sy);

      }

    } else {

      strokeCap(PROJECT);

      if (dir01 == "up" && dir12 == "right") {

        line((p1[0]+(1-v)/2)*sx, p1[1]*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+(1-v)/2)*sy);

        line(p1[0]*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+(1-v)/2)*sy);

      } else if (dir01 == "left" && dir12 == "down") {

        line(p1[0]*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+(1+v)/2)*sy);

        line((p1[0]+(1+v)/2)*sx, p1[1]*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+(1+v)/2)*sy);

      } else if (dir01 == "right" && dir12 == "down") {

        line((p1[0]+(1+v)/2)*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+1)*sx, (p1[1]+(1-v)/2)*sy);

        line((p1[0]+(1+v)/2)*sx, p1[1]*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+(1-v)/2)*sy);

      } else if (dir01 == "up" && dir12 == "left") {

        line((p1[0]+(1-v)/2)*sx, p1[1]*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+(1+v)/2)*sy);

        line((p1[0]+(1-v)/2)*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+1)*sx, (p1[1]+(1+v)/2)*sy);

      } else if (dir01 == "down" && dir12 == "left") {

        line((p1[0]+(1+v)/2)*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+1)*sy);

        line((p1[0]+(1+v)/2)*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+1)*sx, (p1[1]+(1+v)/2)*sy);

      } else if (dir01 == "right" && dir12 == "up") {

        line((p1[0]+(1-v)/2)*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+1)*sx, (p1[1]+(1-v)/2)*sy);

        line((p1[0]+(1-v)/2)*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+1)*sy);

      } else if (dir01 == "left" && dir12 == "up") {

        line(p1[0]*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+(1+v)/2)*sy);

        line((p1[0]+(1-v)/2)*sx, (p1[1]+(1+v)/2)*sy, (p1[0]+(1-v)/2)*sx, (p1[1]+1)*sy);

      } else {

        line((p1[0]+(1+v)/2)*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+1)*sy);

        line(p1[0]*sx, (p1[1]+(1-v)/2)*sy, (p1[0]+(1+v)/2)*sx, (p1[1]+(1-v)/2)*sy);

      }

    }

  }

  pop();

}