counting line-pattern paths in 9 dot (3x3) grid

1.md

Problem

How many distinct line-segment patterns -- of varying lengths from 2 dots / 1 segment, up to 9 dots / 8 segments -- can be drawn on those 3x3 dot grids, like the phone unlock screen on Android phones?

Grid

0 1 2
3 4 5
6 7 8

Rules:

• Patterns connect dots/digits in straight line segments -- no curves, no anchors outside the grid, etc
• Patterns must contain at least 1 line segment (2 dots/digits)
• Patterns cannot include the same dot/digit more than once
• However, if a dot/digit is already used in the pattern, that dot/digit can be "skipped over" to reach a dot/digit past it (continuing in a straight line); so a pattern like 1-4-2-0 is legal, because the 2-0 segment "skips over" the 1 that's already in the pattern

Counts / Analysis

There are:

• 56 distinct patterns of exactly 2 dots/digits, and 389,488 distinct patterns of at least 2 dots/digits
• 320 distinct patterns of exactly 3 dots/digits, and 389,432 distinct patterns of at least 3 dots/digits
• 1,624 distinct patterns of exactly 4 dots/digits, and 389,112 distinct patterns of at least 4 dots/digits
• 7,152 distinct patterns of exactly 5 dots/digits, and 387,488 distinct patterns of at least 5 dots/digits
• 26,016 distinct patterns of exactly 6 dots/digits, and 380,336 distinct patterns of at least 6 dots/digits
• 72,912 distinct patterns of exactly 7 dots/digits, and 354,320 distinct patterns of at least 7 dots/digits
• 140,704 distinct patterns of exactly 8 dots/digits, and 281,408 distinct patterns of at least 8 dots/digits
• 140,704 distinct patterns of exactly 9 dots/digits

2.js

// digits (0-9) on a 3x3 grid:
//
//   0   1   2
//   3   4   5
//   6   7   8

// starting from the digit corresponding to the position in this
// array, the indicated digits are reachable
var adjacentDigits = [
  [ 1, 3, 4, 5, 7 ],
  [ 0, 2, 3, 4, 5, 6, 8 ],
  [ 1, 3, 4, 5, 7 ],
  [ 0, 1, 2, 4, 6, 7, 8 ],
  [ 0, 1, 2, 3, 5, 6, 7, 8 ],
  [ 0, 1, 2, 4, 6, 7, 8 ],
  [ 1, 3, 4, 5, 7 ],
  [ 0, 2, 3, 4, 5, 6, 8 ],
  [ 1, 3, 4, 5, 7 ]  
];

// starting from the digit corresponding to the position in this
// array, and skipping a digit that's already in the pattern (the
// first digit of each tuple), the second digit in the tuple is
// also reachable
var skipNextDigits = [
  [ [ 1, 2 ], [ 3, 6 ], [ 4, 8 ] ],
  [ [ 4, 7 ] ],
  [ [ 1, 0 ], [ 4, 6 ], [ 5, 8 ] ],
  [ [ 4, 5 ] ],
  [ ],
  [ [ 4, 3 ] ],
  [ [ 3, 0 ], [ 4, 2 ], [ 7, 8 ] ],
  [ [ 4, 1 ] ],
  [ [ 4, 0 ], [ 5, 2 ], [ 7, 6 ] ]  
];

function reachableDigits(currentPath) {
  var digits = [];
  var currentDigit = currentPath[currentPath.length - 1];
  for (let digit of adjacentDigits[currentDigit]) {
    // digit not yet in path?
    if (!currentPath.includes(digit)) {
      digits.push(digit);
    }
    else {
      // look for next digit, after skipping this digit (in a straight line!)
      for (let [ skipDigit, nextDigit ] of skipNextDigits[currentDigit]) {
        if (digit == skipDigit && !currentPath.includes(nextDigit)) {
          digits.push(nextDigit);
          
          // minor optimization: assert there's only one skip path possible
          // for any pair of digits
          break;
        }
      }
    }
  }
  return digits;
}

function followPath(path,paths) {
  if (path.length == 9) {
    paths.push(path);
    return;
  }
  var nextDigits = reachableDigits(path);
  if (nextDigits.size == 0) {
    paths.push(path);
    return;
  }
  for (let nextDigit of nextDigits) {
    followPath([ ...path, nextDigit ],paths);
  }
}

function countPaths() {
  var paths = [];
  for (let startingDigit = 0; startingDigit < 9; startingDigit++) {
    followPath([ startingDigit ],paths);
  }
  return [
    0,
    0,
    filterPaths(paths,2).length,
    filterPaths(paths,3).length,
    filterPaths(paths,4).length,
    filterPaths(paths,5).length,
    filterPaths(paths,6).length,
    filterPaths(paths,7).length,
    filterPaths(paths,8).length,
    filterPaths(paths,9).length
  ];
}

function filterPaths(paths,pathLength) {
  return [ ...new Set(
    paths.filter(path => path.length >= pathLength).map(path => String(path.slice(0,pathLength)))
  ) ].map(pathStr => pathStr.split(","));
}

countPaths();
// [
//   0,
//   0,
//   56,
//   320,
//   1624,
//   7152,
//   26016,
//   72912,
//   140704,
//   140704
// ]

3.js

// programmatically generating the `adjacentDigits` and `skipNextDigits`
// data structures from 2.js above

var grid = [
  [ 0, 1, 2 ],
  [ 3, 4, 5 ],
  [ 6, 7, 8 ]  
];

function generateAdjacency() {
  var adjacency = [];
  var skipAdjacency = [];
  
  for (let row = 0; row <= 2; row++) {
    for (let col = 0; col <= 2; col++) {
      let currentDigit = grid[row][col];
      let digitAdjacency = [];
      let digitSkipAdjacency = [];
      adjacency[currentDigit] = digitAdjacency;
      skipAdjacency[currentDigit] = digitSkipAdjacency;
      for (let rowDelta of [ -2, -1, 0, 1, 2 ]) {
        for (let colDelta of [ -2, -1, 0, 1, 2 ]) {
          if (
            // not same as current digit?
            (rowDelta != 0 || colDelta != 0) &&
            
            // still on the grid?
            (row + rowDelta) >= 0 &&
            (row + rowDelta) <= 2 &&
            (col + colDelta) >= 0 &&
            (col + colDelta) <= 2
          ) {
            // not crossing over a skip digit?
            if (
              (Math.abs(colDelta) != 2 || Math.abs(rowDelta) == 1) &&
              (Math.abs(rowDelta) != 2 || Math.abs(colDelta) == 1)
            ) {
              digitAdjacency.push(grid[row + rowDelta][col + colDelta]);
            }
            // record a skip-digit adjacency
            // note: here, both rowDelta and colDelta will either
            // be 0 or 2, no 1s
            else {
              let skippedRow = row + (rowDelta / 2);
              let skippedCol = col + (colDelta / 2);
              digitSkipAdjacency.push([
                grid[skippedRow][skippedCol],
                grid[row + rowDelta][col + colDelta]
              ]);
            }
          }
        }
      }
    }
  }
  
  return { adjacency, skipAdjacency };
}

generateAdjacency();
// {
//   adjacency: [
//     [ 1, 3, 4, 5, 7 ],
//     [ 0, 2, 3, 4, 5, 6, 8 ],
//     [ 1, 3, 4, 5, 7 ],
//     [ 0, 1, 2, 4, 6, 7, 8 ],
//     [ 0, 1, 2, 3, 5, 6, 7, 8 ],
//     [ 0, 1, 2, 4, 6, 7, 8 ],
//     [ 1, 3, 4, 5, 7 ],
//     [ 0, 2, 3, 4, 5, 6, 8 ],
//     [ 1, 3, 4, 5, 7 ]
//   ],
//   skipAdjacency: [
//     [ [ 1, 2 ], [ 3, 6 ], [ 4, 8 ] ],
//     [ [ 4, 7 ] ],
//     [ [ 1, 0 ], [ 4, 6 ], [ 5, 8 ] ],
//     [ [ 4, 5 ] ],
//     [],
//     [ [ 4, 3 ] ],
//     [ [ 3, 0 ], [ 4, 2 ], [ 7, 8 ] ],
//     [ [ 4, 1 ] ],
//     [ [ 4, 0 ], [ 5, 2 ], [ 7, 6 ] ]
//   ]
// }