Tuesday, December 8, 2015

Advent of Code 2015, Day 9

The Day 9 Puzzle of the 2015 Advent of Code asks for the length of the shortest and longest hamiltonian path on a graph. The vertices are cities and the edges between adjacent cities are labelled with the distance between the cities.

Here's a solution ts.lp in AnsProlog using the Potassco ASP toolkit:

% The distance relation is symmetric.
dist(B, A, N) :- dist(A, B, N).

% Two cities are "adjacent" if there is a defined distance between them.
adjacent(A, B) :- dist(A, B, _).

% A city exists if it has a distance defined to it from somewhere.
city(A) :- adjacent(A, _).

% Assign a city to each stop on the path from 1..n.
1 { path(N, C): city(C) } 1 :- N = 1..n.

% No city can occur twice in the path.
:- path(N, C), path(M, C), N != M.

% There must be a defined distance between successive cities on the path.
:- path(N, C), path(N+1, D), not adjacent(C, D).

% Minimize the sum of distances between successive cities in the path.
#minimize { X, N : path(N, C), path(N+1, D), dist(C,D,X), N = 1..n }.
#show path/2.
It requires the following data file city.lp as input:
dist(faerun, norrath, 129).
dist(faerun, tristram, 58).
dist(faerun, alphacentauri, 13).
dist(faerun, arbre, 24).
dist(faerun, snowdin, 60).
dist(faerun, tambi, 71).
dist(faerun, straylight, 67).
dist(norrath, tristram, 142).
dist(norrath, alphacentauri, 15).
dist(norrath, arbre, 135).
dist(norrath, snowdin, 75).
dist(norrath, tambi, 82).
dist(norrath, straylight, 54).
dist(tristram, alphacentauri, 118).
dist(tristram, arbre, 122).
dist(tristram, snowdin, 103).
dist(tristram, tambi, 49).
dist(tristram, straylight, 97).
dist(alphacentauri, arbre, 116).
dist(alphacentauri, snowdin, 12).
dist(alphacentauri, tambi, 18).
dist(alphacentauri, straylight, 91).
dist(arbre, snowdin, 129).
dist(arbre, tambi, 53).
dist(arbre, straylight, 40).
dist(snowdin, tambi, 15).
dist(snowdin, straylight, 99).
dist(tambi, straylight, 70).
city(alphacentauri;arbre;faerun;norrath;snowdin;straylight;tambi;tristram).
#const n = 8.
Here's the output from running it:
$ clingo city.lp ts.lp clingo version 4.4.0 Reading from city.lp ... Solving... Answer: 1 path(1,faerun) path(3,norrath) path(8,tristram) path(2,alphacentauri) path(6,arbre) path(5,snowdin) path(4,tambi) path(7,straylight) Optimization: 391 Answer: 2 path(8,faerun) path(3,norrath) path(5,tristram) path(2,alphacentauri) path(6,arbre) path(1,snowdin) path(4,tambi) path(7,straylight) Optimization: 387 Answer: 3 path(5,faerun) path(3,norrath) path(8,tristram) path(2,alphacentauri) path(6,arbre) path(1,snowdin) path(4,tambi) path(7,straylight) Optimization: 341 Answer: 4 path(5,faerun) path(1,norrath) path(6,tristram) path(2,alphacentauri) path(8,arbre) path(3,snowdin) path(4,tambi) path(7,straylight) Optimization: 308 Answer: 5 path(5,faerun) path(1,norrath) path(8,tristram) path(2,alphacentauri) path(6,arbre) path(3,snowdin) path(4,tambi) path(7,straylight) Optimization: 274 Answer: 6 path(7,faerun) path(5,norrath) path(1,tristram) path(6,alphacentauri) path(8,arbre) path(3,snowdin) path(2,tambi) path(4,straylight) Optimization: 269 Answer: 7 path(7,faerun) path(5,norrath) path(8,tristram) path(6,alphacentauri) path(3,arbre) path(1,snowdin) path(2,tambi) path(4,straylight) Optimization: 248 Answer: 8 path(2,faerun) path(5,norrath) path(1,tristram) path(6,alphacentauri) path(3,arbre) path(7,snowdin) path(8,tambi) path(4,straylight) Optimization: 218 Answer: 9 path(5,faerun) path(8,norrath) path(1,tristram) path(4,alphacentauri) path(6,arbre) path(3,snowdin) path(2,tambi) path(7,straylight) Optimization: 207 OPTIMUM FOUND Models : 9 Optimum : yes Optimization : 207 Calls : 1 Time : 0.050s (Solving: 0.04s 1st Model: 0.00s Unsat: 0.03s) CPU Time : 0.040s
So the shortest path is from Faerun-Norrath-Tristram-AlphaCentauri-Arbre-Snowdin-Tambi-Straylight with a length of 207.

Changing #minimize to #maximize in ts.lp yields a longest path of Norrath-Tristram-AlphaCentauri-Arbre-Snowdin-Tambi-Straylight, with a length of 804.

Friday, November 20, 2015

Brute-force Sudoku solver in JavaScript

// Brute-force Sudoku solver by Josh Jordan (public domain):

// https://tentorcupu.wordpress.com/2013/11/08/just-another-extreme-sudoku-solution/
var coly013= [
  0, 0, 0, 0, 9, 0, 0, 5, 0,
  0, 1, 0, 0, 0, 0, 0, 3, 0,
  0, 0, 2, 3, 0, 0, 7, 0, 0,
  0, 0, 4, 5, 0, 0, 0, 7, 0,
  8, 0, 0, 0, 0, 0, 2, 0, 0,
  0, 0, 0, 0, 0, 6, 4, 0, 0,
  0, 9, 0, 0, 1, 0, 0, 0, 0,
  0, 8, 0, 0, 6, 0, 0, 0, 0,
  0, 0, 5, 4, 0, 0, 0, 0, 7,
];

// https://tentorcupu.wordpress.com/2013/11/08/just-another-extreme-sudoku-solution/
var tarx0134 = [
  0, 0, 0, 0, 0, 0, 0, 0, 8,
  0, 0, 3, 0, 0, 0, 4, 0, 0,
  0, 9, 0, 0, 2, 0, 0, 6, 0,
  0, 0, 0, 0, 7, 9, 0, 0, 0,
  0, 0, 0, 0, 6, 1, 2, 0, 0, 
  0, 6, 0, 5, 0, 2, 0, 7, 0,
  0, 0, 8, 0, 0, 0, 5, 0, 0,
  0, 1, 0, 0, 0, 0, 0, 2, 0,
  4, 0, 5, 0, 0, 0, 0, 0, 3,
];

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

// "Golden Nugget... accepted by many sources as the world's hardest sudoku
// puzzle" - http://www.sudokusnake.com/goldennugget.php
var golden_nugget = [
  0, 0, 0, 0, 0, 0, 0, 3, 9,
  0, 0, 0, 0, 1, 0, 0, 0, 5,
  0, 0, 3, 0, 0, 5, 8, 0, 0,
  0, 0, 8, 0, 0, 9, 0, 0, 6,
  0, 7, 0, 0, 2, 0, 0, 0, 0,
  1, 0, 0, 4, 0, 0, 0, 0, 0,
  0, 0, 9, 0, 0, 8, 0, 5, 0,
  0, 2, 0, 0, 0, 0, 6, 0, 0,
  4, 0, 0, 7, 0, 0, 0, 0, 0,
];

// Arto Inkala's "Hardest Sudoko" from 2010
// http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-can-you-242294
var inkala2010 = [
  0, 0, 5, 3, 0, 0, 0, 0, 0,
  8, 0, 0, 0, 0, 0, 0, 2,  ,
  0, 7, 0, 0, 1, 0, 5, 0, 0,
  4, 0, 0, 0, 0, 5, 3, 0, 0,
  0, 1, 0, 0, 7, 0, 0, 0, 6,
  0, 0, 3, 2, 0, 0, 0, 8, 0,
  0, 6, 0, 5, 0, 0, 0, 0, 9,
  0, 0, 4, 0, 0, 0, 0, 3, 0,
  0, 0, 0, 0, 0, 9, 7, 0, 0,
];

// Peter Norvig's "hardest (for my program) of the million random puzzles"
// http://norvig.com/sudoku.html
var norvig_hard = "000006000059000008200008000045000000003000000006003054000325006000000000000000000".split('').map(function(x) { return +x})

// Peter Norvig's impossible sudoko (has no solutions) from
// http://norvig.com/sudoku.html
var norvig_impossible = [
0, 0, 0, 0, 0, 5, 0, 8, 0,
0, 0, 0, 6, 0, 1, 0, 4, 3,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 5, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 6, 0, 0, 0,
3, 0, 0, 0, 0, 0, 0, 0, 5,
5, 3, 0, 0, 0, 0, 0, 6, 1,
0, 0, 0, 0, 0, 0, 0, 0, 4,
0, 0, 0, 0, 0, 0, 0, 0, 0,
];

var box_grid;

function initBoxGrid() {
box_grid = [];
for (var i = 0; i < 9; i++) {
box_grid[i] = []
}
for (var i = 0; i < 81; i++) {
box_grid[cell_box(i)].push(i);
}
}

function solveable(board) {
return solveable_r(board.slice(), 80);
}

function solveable_r(board, i) {
  if (box_grid === undefined) {
initBoxGrid();
}
if (i < 0) {
console.log(board); // show the solution
return board;
}
if (board[i] > 0) {
return solveable_r(board, i-1);
}
for (var j = 1; j < 10; j++) {
board[i] = j;
if(valid(board, i) && solveable_r(board, i-1)) {
return true;
}
board[i] = 0;
}
return false;
}

function valid(board, cell) {
return valid_row(board, cell_row(cell))
  && valid_col(board, cell_col(cell))
  && valid_box(board, cell_box(cell));
}

// Given a cell (0-80), return the number of the row to which it belongs (0-8).
function cell_row(i) {
return Math.floor(i / 9);
}

// Given a cell (0-80), return the number of the column to which it belongs (0-8).
function cell_col(i) {
return i % 9;
}

// Given a cell (0-80), return the number of the box to which it belongs (0-8).
function cell_box(i) {
return 3 * Math.floor(cell_row(i) / 3) + Math.floor(cell_col(i) / 3)
}

function valid_row(board, row) {
  return valid_line(board, row, 9, 1);
}

function valid_col(board, col) {
return valid_line(board, col, 1, 9);
}

function valid_line(board, row, a, b) {
var seen = 0;
for (var i = 0; i < 9; i++) {
j = board[row * a + i * b];
if (j == 0) continue;
if (seen & (1 << j)) {
return false;
}
seen = seen | (1 << j);
}
return true;
}

function valid_box(board, b) {
var seen = 0;
for (var i = 0; i < 9; i++) {
j = board[box_grid[b][i]];
if (j == 0) continue;
if (seen & (1 << j)) {
return false;
}
seen = seen | (1 << j);
}
return true;
}

console.log(solveable(coly013));
console.log(solveable(platinum_blonde));
console.log(solveable(tarx0134));
console.log(solveable(golden_nugget));
console.log(solveable(inkala2010));
console.log(solveable(norvig_hard));
console.log(solveable(norvig_impossible));

Thursday, February 12, 2015

0hn0.com solver

Below is a solver for the puzzles at 0hn0.com. Using it I calculated that an empty 2x2 puzzle can be solved in 10 different ways, an empty 3x3 puzzle can be solved in 250 different ways, and an empty 4x4 puzzle can be solved in in 22946 different ways.

% uses clingo ASP solver from http://potassco.sourceforge.net/
% USAGE: clingo thisfile.txt
% The solution is in the squarecolor(Y,X,blue;red) terms in the output.

% problem specification; example 8x8 puzzle from 0hn0.com:
% - * 6 - 5 - - -
% - * - * - - 5 -
% - - - - - 4 8 -
% 4 - * - * - - -
% - - 5 - * 2 - -
% - - - - - 7 - 3
% 3 - - 7 6 - - -


% begin problem description in ASP
% num(Y,X,N) means the number in square (Y,X) is N
% (squares with numbers are all initially blue.)
% red(Y,X) means square (Y,X) is initially red.
#const ysize=8.
#const xsize=8.


num(1,1,1).
num(1,2,1).
num(1,5,2).
num(1,8,1).
red(2,2).
num(2,3,6).
num(2,5,5).
red(3,2).
red(3,4).
num(3,7,5).
num(4,6,4).
num(4,7,8).
num(5,1,4).
red(5,3).
red(5,5).
num(6,3,5).
red(6,5).
num(6,6,2).
num(7,6,7).
num(7,8,3).
num(8,1,3).
num(8,4,7).
num(8,5,6).

% end ASP problem description
% nothing below this line needs to be edited

% list the valid colors and directions
color(red;blue).
dir(up;down;left;right).

% squares with numbers are blue
squarecolor(Y,X,blue) :- num(Y,X).

% squares specified as red in the initial problem are red in the solution
squarecolor(Y,X,red) :- red(Y,X).

% num(Y,X) :- square(Y,X) was assigned a number in the initial problem
num(Y,X) :- num(Y,X,C).

% choose a color for each initially-empty square
1 { squarecolor(Y,X,C) : color(C) } 1 :- square(Y,X), not num(Y,X), not red(Y,X).

% dir(Y,X,D,YD,XD) = (YD,XD) is 1 square in direction D from (Y,X)
% square 0,0 is used to represent an invalid square, e.g. going up
% from a square in the top row.
row(1..ysize).
col(1..xsize).
square(Y,X) :- row(Y), col(X).
dirok(Y,X, up, Y-1,X) :- square(Y,X).
dirok(Y,X, down, Y+1,X) :- square(Y,X).
dirok(Y,X, left, Y,X-1) :- square(Y,X).
dirok(Y,X, right, Y,X+1) :- square(Y,X).
dir(Y,X,D, 0,0) :- square(Y,X), dir(D), dirok(Y,X,D,YD,XD), not square(YD,XD).
dir(Y,X,D, YD,XD) :- square(Y,X), dir(D), dirok(Y,X,D,YD,XD), square(YD,XD).

% consider any invalid square (0,0) to be colored red.
squarecolor(0,0,red).


% seendir(Y,X,D,N) = N blue squares can be seen in direction D from square (Y,X)
seendir(Y,X,D,1+SD) :- squarecolor(Y,X,blue), dir(D), dir(Y,X,D,YD,XD), seendir(YD,XD,D,SD).

% red squares block vision, so nothing can be seen in any direction from a red square.
seendir(Y,X,D,0) :- squarecolor(Y,X,red), dir(D).

% seen(Y,X,N) = Blue square (Y,X) can see N blue discs in all directions.
seen(Y,X,U+D+L+R-4) :- square(Y,X), squarecolor(Y,X,blue), seendir(Y,X,up,U),
                seendir(Y,X,down,D), seendir(Y,X,left,L), seendir(Y,X,right,R).


% each blue square must see at least 1 other blue square (can't see only 0)
:- squarecolor(Y,X,blue), seen(Y,X,0).

% every blue square must see a number of neighbors equal to the number written on it.
:- num(Y,X,C), seen(Y,X,D), C != D.

Saturday, January 17, 2015

Counting steno strokes

How many different strokes are possible on a steno keyboard, using the conventional fingering?

Background

The world's fastest typists can type more than 200 words per minute, and they all use steno keyboards. On these keyboards, it's usual to press more than one key at the same time. The act of pressing one or more keys simultaneously is called a stroke. Each stroke is automatically converted to text by a computer, using a digital dictionary. A particular stroke could represent a letter, a symbol, a word, a phrase, or even an instruction such as "capitalize the next word." To learn more about how steno works, see How court reporting is done from the U.S. Bureau of Labor, or watch Plover: Thought to Text at 240 WPM by Mirabai Knight.

Counting strokes

How many different strokes are possible? To answer the question, I'll assume that each finger operates independently, count the number of different places each finger can be during a stroke, and multiply those numbers together to get the answer. This way of counting includes an "empty stroke" in which every finger is off the keyboard, but this doesn't count as stroke, so we'll subtract 1 at the end to account for that.

Steno keyboards and fingers

A steno keyboard is arranged as in the diagram below. In any particular stroke, each finger can press zero or more keys. Except for the number bar, which we'll deal with below, the conventional fingering assigns each key to one finger. (Some unconventional fingering techniques like the Philadelphia Shift allow the same key to be pressed by different fingers, but I won't consider them here.) For some reason, steno keyboards have two keys (both labelled '*') in the 5th column, but in terms of the text that comes out on the screen, it never matters which one of those two is pressed. So in this note, I'll consider the 5th column to have only one key.

The diagram shows the 23 keys of a steno keyboard, with an oval for each finger. A solid red disc in the middle of a key represents the possibility that a finger is pressing only that key. A solid red disc between two keys indicates that a finger can press both keys at once. The right pinky can press 4 keys at once; this is indicated by a solid red disc in the middle of those 4 keys. There is also an empty circle for each finger to represent the possibility that the finger isn't pressing a key.

Counting the number bar and the left pinky

The long key at the top of the steno keyboard is called the number bar. For the purposes of counting steno strokes, it doesn't matter which finger presses it. To simplify the counting, and without sacrificing accuracy, we'll assume that if the number bar is pressed, it's pressed by the left pinky. How do we know that it's always possible for the left pinky to press the number bar? Not counting the number bar, the left pinky can be doing one of 2 things: either pressing the key in the first column, or doing nothing. No matter which of those it's doing, it could also be pressing the number key at the same time.

Counting the other fingers

Moving on, the left 3rd finger can be doing one of 4 things: (1) pressing the top key in the 2nd column, (2) pressing both keys in the 2nd column, (3) pressing the bottom key in the 2nd column, or (4) not pressing any key. Continuing on like this, we get to the right 1st finger, which can be doing any of 8 things, including pressing the key in the 5th column in various combinations with the top and bottom keys in the 6th column, or not pressing any key. Finally, we get to the right pinky, which can be in any of 10 possible places during a stroke, and the two thumbs, which can each be in any of 4 places.

And the answer is...

To count the number of possible strokes, multiply the number of possibilities for each individual finger together, and subtract 1 for the "empty stroke" when no keys are pressed: 4•4•4•4•8•4•4•10•4•4 - 1. That equals 5242879, or around 5.25 million.

Or is it?

A Google search for ["5242879" steno OR stenotype] turns up no results. Did I made a mistake somewhere? Let me know.

Followers

Contributors