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.

at No comments:

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));

at No comments:

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.
at No comments:

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.

at No comments:

Wednesday, November 19, 2014

Ripple Effect

Here's a solver for Nikoli's Ripple Effect puzzle. 

% Usage: clingo < rippleffect.lp
%
% Download clingo 4 from http://sourceforge.net/projects/potassco/files/clingo/

% The example puzzle used is from http://en.wikipedia.org/w/index.php?title=Ripple_Effect_(puzzle)&oldid=598393777

% +---+---+---+---+---+---+---+---+---+
% |       |       |                 2 |
% +   +---+---+   +---+---+---+---+   +
% |   |   |   |       |   |       |   |
% +   +   +---+---+   +   +   +   +---+
% |   |           |   |   |           |
% +---+---+---+   +---+---+---+   +---+
% |           |   |           |   |   |
% +---+---+---+---+   +   +---+---+---+
% |   |   |       | 5     |   |       |
% +---+   +   +   +---+---+   +   +   +
% |   |   |       |           |       |
% +   +---+---+---+---+---+---+   +---+
% |       |       |       |       |   |
% +---+---+---+---+   +   +---+---+   +
% |               |       |   |       |
% +---+---+---+---+---+---+   +   +   +
% | 4             |           |       |
% +---+---+---+---+---+---+---+---+---+

%%% inputs

#const size = 9.

% n(S,N) = square S has number N. (0 for blank)

n(11,0). n(12,0). n(13,0). n(14,0). n(15,0). n(16,0). n(17,0). n(18,0). n(19,2).
n(21,0). n(22,0). n(23,0). n(24,0). n(25,0). n(26,0). n(27,0). n(28,0). n(29,0).
n(31,0). n(32,0). n(33,0). n(34,0). n(35,0). n(36,0). n(37,0). n(38,0). n(39,0).
n(41,0). n(42,0). n(43,0). n(44,0). n(45,0). n(46,0). n(47,0). n(48,0). n(49,0).
n(51,0). n(52,0). n(53,0). n(54,0). n(55,5). n(56,0). n(57,0). n(58,0). n(59,0).
n(61,0). n(62,0). n(63,0). n(64,0). n(65,0). n(66,0). n(67,0). n(68,0). n(69,0).
n(71,0). n(72,0). n(73,0). n(74,0). n(75,0). n(76,0). n(77,0). n(78,0). n(79,0).
n(81,0). n(82,0). n(83,0). n(84,0). n(85,0). n(86,0). n(87,0). n(88,0). n(89,0).
n(91,4). n(92,0). n(93,0). n(94,0). n(95,0). n(96,0). n(97,0). n(98,0). n(99,0).

% r(S,R) = square S is in region R. Region symbols are arbitrary.

r(11,a). r(12,a). r(13,b). r(14,b). r(15,c). r(16,c). r(17,c). r(18,c). r(19,c).
r(21,a). r(22,d). r(23,e). r(24,b). r(25,b). r(26,f). r(27,g). r(28,g). r(29,c).
r(31,a). r(32,d). r(33,d). r(34,d). r(35,b). r(36,f). r(37,g). r(38,g). r(39,g).
r(41,h). r(42,h). r(43,h). r(44,d). r(45,i). r(46,i). r(47,i). r(48,g). r(49,j).
r(51,k). r(52,m). r(53,n). r(54,n). r(55,i). r(56,i). r(57,o). r(58,p). r(59,p).
r(61,q). r(62,m). r(63,n). r(64,n). r(65,o). r(66,o). r(67,o). r(68,p). r(69,p).
r(71,q). r(72,q). r(73,r). r(74,r). r(75,s). r(76,s). r(77,p). r(78,p). r(79,t).
r(81,v). r(82,v). r(83,v). r(84,v). r(85,s). r(86,s). r(87,u). r(88,t). r(89,t).
r(91,w). r(92,w). r(93,w). r(94,w). r(95,u). r(96,u). r(97,u). r(98,t). r(99,t).

%%% Solver

% sz(S,C) = the count of the number of squares in the region enclosing square S is C.
sz(S,C) :- C = #count { T : r(T, R) }, r(S,R).

% row(R) = R is a row index (1..size)
row(1..size).

% col(C) = C is a column index (1..size)
col(1..size).

% sq(Y,X,S) - the square at (Y,X) is S. Example: the square at (3,2) is 32.
sq(Y,X,10*Y+X) :- row(Y), col(X).

% nbetween(A,B,N) = A & B are in the same row or column, with N squares in between them.
nbetween(A,B,X2-X1-1) :- row(Y), col(X1), col(X2), X1 < X2, sq(Y,X1,A), sq(Y,X2,B).
nbetween(A,B,Y2-Y1-1) :- col(X), row(Y1), row(Y2), Y1 < Y2, sq(Y1,X,A), sq(Y2,X,B).

% m(S,N) :- in the solution, square S contains the number N.
m(S,N) :- n(S,N), N != 0.

% chose one value for each initially-empty square that does not exceed the size of its region.
1 { m(S,N) : N = 1..C } 1 :- n(S,0), sz(S,C).

% no duplicate values in the same region.
:- m(S1,N), m(S2,N), r(S1,R), r(S2,R), S1 < S2.

% Whenever the number N occurs twice in the same row or column, there must be at least N squares
% between those two occurrences
:- m(S1,N), m(S2,N), nbetween(S1,S2,M), M < N.

#show m/2.
And here's an encoding for the neat puzzle with no numeric clues at http://puzzleparasite.blogspot.com/2011/12/puzzle-71-ripple-effect.html: 
% size of board
#const size = 8.

% n(S,N) = square S has number N. (0 for blank)

n(11,0). n(12,0). n(13,0). n(14,0). n(15,0). n(16,0). n(17,0). n(18,0).
n(21,0). n(22,0). n(23,0). n(24,0). n(25,0). n(26,0). n(27,0). n(28,0).
n(31,0). n(32,0). n(33,0). n(34,0). n(35,0). n(36,0). n(37,0). n(38,0).
n(41,0). n(42,0). n(43,0). n(44,0). n(45,0). n(46,0). n(47,0). n(48,0).
n(51,0). n(52,0). n(53,0). n(54,0). n(55,0). n(56,0). n(57,0). n(58,0).
n(61,0). n(62,0). n(63,0). n(64,0). n(65,0). n(66,0). n(67,0). n(68,0).
n(71,0). n(72,0). n(73,0). n(74,0). n(75,0). n(76,0). n(77,0). n(78,0).
n(81,0). n(82,0). n(83,0). n(84,0). n(85,0). n(86,0). n(87,0). n(88,0).

% r(S,R) = square S is in region R. Region symbols are arbitrary.

r(11,a). r(12,a). r(13,b). r(14,c). r(15,c). r(16,c). r(17,d). r(18,d).
r(21,a). r(22,b). r(23,b). r(24,e). r(25,f). r(26,c). r(27,d). r(28,d).
r(31,b). r(32,b). r(33,e). r(34,e). r(35,f). r(36,g). r(37,h). r(38,h).
r(41,i). r(42,i). r(43,e). r(44,k). r(45,k). r(46,g). r(47,g). r(48,j).
r(51,m). r(52,n). r(53,n). r(54,k). r(55,k). r(56,o). r(57,g). r(58,j).
r(61,m). r(62,p). r(63,q). r(64,q). r(65,o). r(66,o). r(67,j). r(68,j).
r(71,m). r(72,p). r(73,p). r(74,q). r(75,o). r(76,r). r(77,s). r(78,j).
r(81,m). r(82,m). r(83,p). r(84,p). r(85,r). r(86,r). r(87,r). r(88,r).
at No comments:

0hh1

Here's a solver for the puzzles at 0hh1.com. 

% USAGE: clingo -n 0 <thisfile.txt # show all solutions to puzzle
%
% Download from: http://sourceforge.net/projects/potassco/files/clingo/3.0.5/

% Two colors: 1 = red, 2 = blue.  (0 = empty)
color(1). color(2).

#const size = 6.
% coord(Y,X) = Y,X is a valid coordinate of a cell in the puzzle.
coord(0..size-1,0..size-1).

% p(Y,X,C) = cell [Y,X] is color C in the original puzzle.
%- X X - - -
%O - - - - -
%- - - - - -
%- - - - O -
%- - - - - O
%- X - - - -

color(1). color(2).

#const size = 6.
% coord(Y,X) = Y,X is a valid coordinate of a cell in the puzzle.
coord(0..size-1,0..size-1).

% p(Y,X,C) = cell [Y,X] is color C in the original puzzle.
%- X X - - -
%O - - - - -
%- - - - - -
%- - - - O -
%- - - - - O
%- X - - - -

p(0,0,2).  p(0,1,1).  p(0,2,0).  p(0,3,0).  p(0,4,1).  p(0,5,2).
p(1,0,1).  p(1,1,0).  p(1,2,0).  p(1,3,2).  p(1,4,0).  p(1,5,0).
p(2,0,0).  p(2,1,2).  p(2,2,1).  p(2,3,1).  p(2,4,2).  p(2,5,0).
p(3,0,0).  p(3,1,0).  p(3,2,2).  p(3,3,0).  p(3,4,0).  p(3,5,0).
p(4,0,1).  p(4,1,0).  p(4,2,2).  p(4,3,1).  p(4,4,2).  p(4,5,0).
p(5,0,1).  p(5,1,2).  p(5,2,0).  p(5,3,0).  p(5,4,2).  p(5,5,0).

% q(Y,X,C) = cell[Y,X] is color C in the solved puzzle.

% The colors in the original puzzle must not change in the solution.
q(Y,X,C) :- p(Y,X,C); C != 0.

% Each empty square in the original puzzle must be colored red or blue in the solution.
1 { q(Y,X,C) : color(C) } 1 :- p(Y,X,0).

% f(Y,X) = cell(Y,X) is filled with some color.
f(Y,X) :- q(Y,X,C); C != 0.

% Solution cannot have empty squares.
:- coord(Y,X); not f(Y,X).

% Solution cannot have three adjacent cells of the same color horizontally.
:- q(Y,X,C); q(Y,X+1,C); q(Y,X+2,C).

% Solution cannot have three adjacent cells of the same color vertically.
:- q(Y,X,C); q(Y+1,X,C); q(Y+2,X,C).

% Exactly half of the cells in every row in the solution must be red.
:-  coord(Y,_); {coord(Y,X) : q(Y,X,2) } != size/2.

% Exactly half of the cells in every column in the solution must be red.
:- coord(_,X); {coord(Y,X) : q(Y,X,1) } != size/2.

% diffrow(Y1, Y2) = rows Y1 and Y2 differ.
diffrow(Y1, Y2) :- q(Y1,X,C1); q(Y2,X,C2); C1 != C2; coord(Y1,_); coord(Y2,_); Y1 < Y2.

% diffcol(X1, X2) = columns X1 and X2 differ.
diffcol(X1, X2) :- q(Y,X1,C1); q(Y,X2,C2); C1 != C2; coord(_,X1); coord(_,X2); X1 < X2.

% Solution cannot have duplicate rows.
:- coord(Y1,_); coord(Y2,_); Y1 < Y2; not diffrow(Y1, Y2).

% Solution cannot have duplicate columns.
:- coord(_,X1); coord(_,X2); X1 < X2; not diffcol(X1, X2).
at No comments:

Monday, December 30, 2013

Mentally calculating the # of Tuesdays between 1700 and 2014

This note explains one way to calculate, in your head, the number of Tuesdays between Jan 1, 1700 and Jan 1, 2014. The overall approach is to calculate how many days there were in the years 1700, 1701, 1702, ..., 2014, and then divide by 7 to get the number of weeks, which gives the number of Tuesdays.

In this note I will talk about some mental tricks/techniques we can use for this, including:


Let's begin. Overall, there are 2014 - 1700 = 314 years from 1700 to 2014. This works out to 365·314 + L days, where L is the number of leap years in that period.

The first step is to multiply 365·314. We can simplify this with some basic algebra, by noting that (a+b)(a+c) = a(a + b + c) + bc. Letting a = 300, b = 65, and c = 14, we have: 365·314 = (300 + 65)(300 + 14) = 300(300 + 65 + 14) + (65·14)
 = 300·379 + 65·14.

300·379 isn't too bad to do in your head; it's 900 + 210 + 27 = 1137, and then adding two zeros gives 113700. We will need to remember this number for later. Using the mnemonic major system we can remember the first four digits 1137 as "toot mic" (picture someone blowing a horn into a microphone).

Now for 65·14. By writing this as 66·14 - 14, we can use the algebra from above and set a = (66+14)/2 = 40, b = 26, and c = -26, which gives us 66·14 = (40 + 26)(40 - 26) = 402 - 262, a difference of two squares. There are many tricks for doing squares.  One is that ab^2 = 100a2 + 10·2ab + b2, so 262 = 100·4 + 10·24 + 36 = 400 + 240 + 36 = 676, so 402 - 262 works out to 1600-676. It is often simpler to calculate x - y by converting it to x + ~y, where ~y is the "second complement" of y. Here the second complement of 676 is 324 - 1000, so we have 1600 - 676 = 1600 + (324 - 1000) = 600 + 324  = 924. Finally we subtract 14 to get 65·14 = 910, which we can remember as "pots".

Now we need to add the last two steps, "toot mic" (113700) and "pots"(910); the sum is 114610, which we can remember as "toot reach toes" (a trumpeter playing a note with the trumpet reaching down to his toes).

We can check the arithmetic by casting out 11s. To do this we first calculate the value of each number mod 11:

365 = 5 + 3 - 6 = 2 (mod 11)
314 = 4 + 3 - 1 = 6 (mod 11)
114610 = 0 + 6 + 1 - (1 + 4 + 1) = 7 - 6 = 1 (mod 11)

Then we re-do our original problem of 365·314 using the mod 11 values and make sure the answer is correct:

365·314 = 2·6 = 12 = 1 = 114610 (mod 11)

They are equal, so that checks out.

Now, how many leap years were there in that period? My rule for leap years is this:
If the last two digits of the year are 00, throw them away and keep only the first two digits. Otherwise, keep just the last two digits. Then the year is a leap year just when what remains is divisible by 4.
We can use this rule to figure out that there are 24 leap years in each of the 1700s, 1800s, and 1900s, for a total of 72 leap years in 1700, 1701, 1702, ... 1999. Furthermore, 2000, 2004, 2008, and 2012 were leap years, so in total there were 76 leap years in the 314-year period from Jan 1, 1700 through Jan 1, 2014.

Our total so far is 114610, "toot reach toes". Adding on 76 days (1 for each leap year) yields 114686, "toot reach fish" (a trumpeter playing for some fishes in the water).

According to the First Sunday Doomsday Algorithm, Dec 31, 2014 was a Tuesday, so we need to be sure to include that day in the calculation. In order to make the total number of days equal to an integer number of weeks, we need to end on a Thursday, so we add 2 more days to end on Thursday, Jan 2, 2014. This yields a total of 114688 days, which we can remember as "toot reach fife" (a trumpeter playing up to a fife on a shelf).

If the above arithmetic is correct, 114688 will equal an integer number of weeks; that is, it will be divisible by 7. It's easy to test for divisibility by 2 or 5, but 7 is a bit trickier. Wikipedia gives a fast method called Pohlman-Mass test for divisibility by 7, which I haven't seen described anywhere else. According to this method, 7 divides 114688 just when 7 divides (114688 - 114114) = 574. And 7 divides 574 just when 7 divides 57 - 4·2 = 49. And since 7 divides 49, 7 also divides 114688, which is consistent with the previous arithmetic being correct.

Actually carrying out the division mentally, which is kind of a pain, we find that 114688/7 = 16384. It just so happens that this is 214, and so there are 214 Tuesdays between Friday, Jan 1, 1700 and Jan 1, 2014.

For more info on mental calculation, two good books are:
at No comments:
Subscribe to: Posts (Atom)

Followers

Contributors