A new December and a new bunch of puzzles from mscroggs.co.uk.
Without comment, the solution.
And the 3 digit number is 651.
Scroggs, day 22
Author Archives: Lise Andreasen
#ThisWeeksFiddler, 20250117
This week the question is: Can You Break the Bell Curve?
Bean machines can famously produce bell-shaped curves. But today, we’re going to change all that!
Suppose you have a board like the one shown below. The board’s topmost row has three pins (and two slots for a ball to pass through), while the bottommost row has two pins (and three slots for a ball to pass through). The remaining rows alternate between having three pins and two pins.
But instead of the 12 rows of pins in the illustrative diagram, suppose the board has many, many rows. And at the very bottom of the board, just below the two bottommost pins, are three buckets, labeled A, B, and C from left to right. [Picture rotated counter clockwise.]
Whenever a ball encounters one of the leftmost pins, it travels down the right side of it to the next row. And whenever a ball encounters one of the rightmost pins, it travels down the left side of it to the next row.
But this isn’t your garden variety bean machine. Whenever a ball encounters any of the other pins, it has a 75 percent chance of traveling down the right side of that pin, and a 25 percent chance of traveling down the left side of that pin.
A single ball is about to be dropped into the left slot at the top of the board. What is the probability that the ball ultimately lands in bucket A, the leftmost slot at the bottom?
And for extra credit:
Suppose you have the board below, which starts with a row with six pins (and five slots), followed by a row with five pins (and six slots), and then back to six pins in an alternating pattern. Balls are only allowed to enter through the middle three slots on top. This time around, the pins that aren’t on the far left or far right behave normally, meaning each ball is equally likely to go around it via the left side or the right side.
Your goal is to create a trapezoidal distribution along one of the rows with six slots, which have been highlighted with dotted lines in the diagram above. More precisely, the frequency of balls passing through the six slots from left to right should be x−y, x, x+y, x+y, x, x−y, for some values of x and y with x ≥ y.
Suppose the ratio by which you drop balls into the top three middle slots, from left to right, is a : b : c, with a + b + c = 1. Find all ordered triples (a, b, c) that result in a trapezoidal distribution in at least one row with six slots.
Highlight to reveal (possibly incorrect) solution:
Assumptions:
- After many rows, the state of the bean machine will reach an equilibrium. The values for the row just above the A, B and C bins will be the same as for the 2 pin row just above that.
- This equilibrium is independent of the beginning state.
First let’s name some things. (Figure 1.)
Before reaching the last row, a ball travels through the state A’, B’ or C’. Then it goes through one of the states of the next row, let’s call them X and Y. And finally it reaches A, B or C. p(S) is the probability, that the ball reached this state, S.
p(A) = p(X) * 1/4
p(B) = p(X) * 3/4 + p(Y) * 1/4
p(C) = p(Y) * 3/4
p(X) = p(A’) + p(B’) * 1/4
p(Y) = p(B’) * 3/4 + p(C’)
Using the assumptions:
p(A) = p(A’) etc.
Further: p(A) + p(B) + p(C) = 1. WolframAlpha is happy to solve this system of equations for me. (Figure 2.)
The answer we’re looking for is p(A) = 0.025 = 1/40. A small program confirms this.
And for extra credit:
Assumptions:
- The 5 pin states converge rather quickly into (0.1, 0.2, 0.2, 0.2, 0.2, 0.1). If we want something radically different (and we do), it has to be found within the first maybe 10 pairs of rows. So let’s just look at these early, non-equilibrium states.
- We’re looking for a symmetric state (x−y, x, x+y, x+y, x, x−y). Therefore the beginning state must also be symmetric. Not (a, b, c), but (a, b, a). Therefore b = 1 – 2a, 0 <= a <= 0.5, 0 <= b, <= 1. We’re just looking for a.
- Adding up the sixth sought after probabilities, we get 6x. 6x = 1, so x = 1/6.
- A symmetric state, where the 2nd and 5th probabilities were 1/6, would represent a solution.
Let’s look at some probabilities. Each filled out cell is a position between 2 pins in a row. I only show the left part of the table, as the right part is simply a mirror of the left part. Our potential x = 1/6 will show up in the 3rd column.
| 0 | a | b | |||
| 0 | a/2 | a/2+b/2 | |||
| a/4 | a/2+b/4 | a/2+b/2 | |||
| a/8 | 3a/8+b/8 | a/2+3b/8 | |||
| 5a/16+b/16 | 7a/16+b/4 | a/2+3b/8 | |||
| 5a/32+b/32 | 3a/8+5b/32 | 15a/32+3b/8 | |||
| 11a/32+7b/64 | 27a/64+17b/64 | 15a/32+3b/8 | |||
| 11a/64+7b/128 | 49a/128+3b/16 | 57a/128+41b/128 | |||
| 93a/256+19b/128 | 53a/128+65b/256 | 57a/128+41b/128 | |||
| 93a/512+19b/256 | 199a/512+103b/512 | 55a/128+147b/512 |
It is possible to have a/2 = 1/6? Yes it is, a = 1/3.
Is it possible to have 3a/8+b/8 = 1/6?
- 3a/8 + b/8 = 1/6
- 3a + b = 8/6 = 4/3
- 9a + 3b = 4
- 9a + 3(1-2a) = 4
- 9a + 3 – 6a = 4
- 3a = 1
- a = 1/3
The same solution, a = 1/3.
Is it possible to have 3a/8+5b/32 = 1/6?
- 3a/8 + 5b/32 = 1/6
- 12a + 5b = 32/6
- 72a + 30b = 32
- 72a + 30(1-2a) = 32
- 72a + 30 – 60a = 32
- 12a = 2
- a = 1/6
A new solution, a = 1/6.
Is it possible to have 49a/128+3b/16 = 1/6?
- 49a/128 + 3b/16 = 1/6
- 49a + 24b = 128/6 = 64/3
- 147a + 72b = 64
- 147a + 72(1-2a) = 64
- 147a + 72 – 144a = 64
- 3a = -8
- a = -8/3
This won’t do, a has to be positive.
Is it possible to have 199a/512+103b/512 = 1/6?
- 199a/512 + 103b/512 = 1/6
- 199a + 103b = 512/6 = 256/3
- 597a + 309b = 256
- 597a + 309(1-2a) = 256
- 597a + 309 – 618a = 256
- 53 = 21a
- a = 53/21
As we go along, we will keep getting weird solutions. Therefore the whole set of solutions is:
(1/3, 1/3, 1/3), (1/6, 2/3, 1/6).
Phew!
Advent of Code, day 21
This December I participated in Advent of Code.
For me there were 2 big hurdles this time. For part 1, it was understanding, that I simply could not cross that empty space. It took a lot of debugging to get that. I avoided that by hand coding (quicker for me) all the safe ways to get from a to b, whatever a and b might be. In part 2, there’s memoization again. The big hurdle here was, that I didn’t store the optimal string, only the length of it. This was possible because every route began and ended the same place, A. Question.
Part 1:
<?php
$trans1["0"]["0"] = array("A");
$trans1["0"]["1"] = array("^<A"); // not the other way around!
$trans1["0"]["2"] = array("^A");
$trans1["0"]["3"] = array("^>A", ">^A");
$trans1["0"]["4"] = array("^^<A", "^<^"); // not left first!
$trans1["0"]["5"] = array("^^A");
$trans1["0"]["6"] = array("^^>A", "^>^A", ">^^");
$trans1["0"]["7"] = array("^^^<A", "^^<^A", "^<^^A"); // not left first!
$trans1["0"]["8"] = array("^^^A");
$trans1["0"]["9"] = array("^^^>A", "^^>^", "^>^^", ">^^^");
$trans1["0"]["A"] = array(">A");
$trans1["1"]["0"] = array(">vA"); // not the other way around!
$trans1["1"]["1"] = array("A");
$trans1["1"]["2"] = array(">A");
$trans1["1"]["3"] = array(">>A");
$trans1["1"]["4"] = array("^A");
$trans1["1"]["5"] = array("^>A", ">^A");
$trans1["1"]["6"] = array("^>>A", ">^>A", ">>^A");
$trans1["1"]["7"] = array("^^A");
$trans1["1"]["8"] = array("^^>A", "^>^A", ">^^A");
$trans1["1"]["9"] = array("^^>>A", "^>^>A", ">^^>A", "^>>^A", ">^>^A", ">>^^A");
$trans1["1"]["A"] = array(">>vA", ">v>A"); // not down first!
$trans1["2"]["0"] = array("vA");
$trans1["2"]["1"] = array("<A");
$trans1["2"]["2"] = array("A");
$trans1["2"]["3"] = array(">A");
$trans1["2"]["4"] = array("^<A", "<^A");
$trans1["2"]["5"] = array("^A");
$trans1["2"]["6"] = array("^>A", ">^A");
$trans1["2"]["7"] = array("^^<A", "^<^A", "<^^A");
$trans1["2"]["8"] = array("^^A");
$trans1["2"]["9"] = array("^^>A", "^>^A", ">^^A");
$trans1["2"]["A"] = array("v>A", ">vA");
$trans1["3"]["0"] = array("<vA", "v<A");
$trans1["3"]["1"] = array("<<A");
$trans1["3"]["2"] = array("<A");
$trans1["3"]["3"] = array("A");
$trans1["3"]["4"] = array("^<<A", "<^<A", "<<^A");
$trans1["3"]["5"] = array("^<A", "<^A");
$trans1["3"]["6"] = array("^A");
$trans1["3"]["7"] = array("^^<<A", "^<^<A", "<^^<A", "^<<^A", "<^<^A", "<<^^A"); // order matters
$trans1["3"]["8"] = array("^^<A", "^<^A", "<^^A");
$trans1["3"]["9"] = array("^^A");
$trans1["3"]["A"] = array("vA");
$trans1["4"]["0"] = array(">vvA", "v>vA"); // not right last!
$trans1["4"]["1"] = array("vA");
$trans1["4"]["2"] = array("v>A", ">vA");
$trans1["4"]["3"] = array("v>>A", ">v>A", ">>vA");
$trans1["4"]["4"] = array("A");
$trans1["4"]["5"] = array(">A");
$trans1["4"]["6"] = array(">>A");
$trans1["4"]["7"] = array("^A");
$trans1["4"]["8"] = array("^>A", ">^A");
$trans1["4"]["9"] = array("^>>A", ">^>A", ">>^A");
$trans1["4"]["A"] = array(">>vvA", ">v>vA", "v>>vA", ">vv>A", "v>v>A"); // not 2 x down first!
$trans1["5"]["0"] = array("vvA");
$trans1["5"]["1"] = array("v<A", "<vA");
$trans1["5"]["2"] = array("vA");
$trans1["5"]["3"] = array("v>A", ">vA");
$trans1["5"]["4"] = array("<A");
$trans1["5"]["5"] = array("A");
$trans1["5"]["6"] = array(">A");
$trans1["5"]["7"] = array("^<A", "<^A");
$trans1["5"]["8"] = array("^A");
$trans1["5"]["9"] = array("^>A", ">^A");
$trans1["5"]["A"] = array("vv>A", "v>vA", ">vvA");
$trans1["6"]["0"] = array("vv<A", "v<vA", "<vvA");
$trans1["6"]["1"] = array("v<<A", "<v<A", "<<vA");
$trans1["6"]["2"] = array("v<A", "<vA");
$trans1["6"]["3"] = array("vA");
$trans1["6"]["4"] = array("<<A");
$trans1["6"]["5"] = array("<A");
$trans1["6"]["6"] = array("A");
$trans1["6"]["7"] = array("^<<A", "<^<A", "<<^A");
$trans1["6"]["8"] = array("^<A", "<^A");
$trans1["6"]["9"] = array("^A");
$trans1["6"]["A"] = array("vvA");
$trans1["7"]["0"] = array(">vvvA", "v>vvA", "vv>vA"); // not right last!
$trans1["7"]["1"] = array("vvA");
$trans1["7"]["2"] = array("vv>A", "v>vA", ">vvA");
$trans1["7"]["3"] = array("vv>>A", "v>v>A", ">vv>A", "v>>vA", ">v>vA", ">>vvA");
$trans1["7"]["4"] = array("vA");
$trans1["7"]["5"] = array("v>A", ">vA");
$trans1["7"]["6"] = array("v>>A", ">v>A", ">>vA");
$trans1["7"]["7"] = array("A");
$trans1["7"]["8"] = array(">A");
$trans1["7"]["9"] = array(">>A");
$trans1["7"]["A"] = array(">>vvvA", ">v>vvA", ">vv>vA", ">vvv>A", "v>>vvA", "v>v>vA", "v>vv>A", "vv>>vA", "vv>v>A"); // not 3 x down first!
$trans1["8"]["0"] = array("vvvA");
$trans1["8"]["1"] = array("vv<A", "v<vA", "<vvA");
$trans1["8"]["2"] = array("vvA");
$trans1["8"]["3"] = array("vv>A", "v>vA", ">vvA");
$trans1["8"]["4"] = array("v<A", "<vA");
$trans1["8"]["5"] = array("vA");
$trans1["8"]["6"] = array("v>A", ">vA");
$trans1["8"]["7"] = array("<A");
$trans1["8"]["8"] = array("A");
$trans1["8"]["9"] = array(">A");
$trans1["8"]["A"] = array(">vvvA", "v>vvA", "vv>vA", "vvv>A");
$trans1["9"]["0"] = array("vvv<A", "vv<vA", "v<vvA", "<vvvA");
$trans1["9"]["1"] = array("vv<<A", "v<v<A", "<vv<A", "v<<vA", "<v<vA", "<<vvA");
$trans1["9"]["2"] = array("vv<A", "v<vA", "<vvA");
$trans1["9"]["3"] = array("vvA");
$trans1["9"]["4"] = array("v<<A", "<v<A", "<<vA");
$trans1["9"]["5"] = array("v<A", "<vA");
$trans1["9"]["6"] = array("vA");
$trans1["9"]["7"] = array("<<A");
$trans1["9"]["8"] = array("<A");
$trans1["9"]["9"] = array("A");
$trans1["9"]["A"] = array("vvvA");
$trans1["A"]["0"] = array("<A");
$trans1["A"]["1"] = array("^<<A", "<^<A"); // not up last!
$trans1["A"]["2"] = array("^<A", "<^A");
$trans1["A"]["3"] = array("^A");
$trans1["A"]["4"] = array("^^<<A", "^<^<A", "<^^<A", "^<<^A", "<^<^A"); // not 2 x left first!
$trans1["A"]["5"] = array("^^<A", "^<^A", "<^^A");
$trans1["A"]["6"] = array("^^A");
$trans1["A"]["7"] = array("^^^<<A", "^^<^<A", "^<^^<A", "<^^^<A", "^^<<^A", "^<^<^A", "<^^<^A", "^<<^^A", "<^<^^A"); // not 2 x left first!
$trans1["A"]["8"] = array("^^^<A", "^^<^A", "^<^^A", "<^^^A");
$trans1["A"]["9"] = array("^^^A");
$trans1["A"]["A"] = array("A");
$trans2["<"]["<"] = array("A");
$trans2["<"]["^"] = array(">^A");
$trans2["<"][">"] = array(">>A");
$trans2["<"]["v"] = array(">A");
$trans2["<"]["A"] = array(">>^A", ">^>A");
$trans2["^"]["<"] = array("v<A");
$trans2["^"]["^"] = array("A");
$trans2["^"][">"] = array("v>A", ">vA");
$trans2["^"]["v"] = array("vA");
$trans2["^"]["A"] = array(">A");
$trans2[">"]["<"] = array("<<A");
$trans2[">"]["^"] = array("<^A", "^<A");
$trans2[">"][">"] = array("A");
$trans2[">"]["v"] = array("<A");
$trans2[">"]["A"] = array("^A");
$trans2["v"]["<"] = array("<A");
$trans2["v"]["^"] = array("^A");
$trans2["v"][">"] = array(">A");
$trans2["v"]["v"] = array("A");
$trans2["v"]["A"] = array("^>A", ">^A");
$trans2["A"]["<"] = array("v<<A", "<v<A");
$trans2["A"]["^"] = array("<A");
$trans2["A"][">"] = array("vA");
$trans2["A"]["v"] = array("v<A", "<vA");
$trans2["A"]["A"] = array("A");
///////////////////////////////////////////////////////////
$input = file_get_contents('./d21input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
if(strlen($line)>2) {
preg_match('/\d+/', $line, $tmp);
$codesorg[] = $tmp[0];
$codes[] = str_split($line);
}
}
function trs3($code3) {
global $trans2, $memo2;
// to directions the last time
$numnext = $code3[0];
$code0 = $trans2["A"][$numnext][0];
$codelgt = sizeof($code3);
for($i=0;$i<$codelgt-1;$i++) {
$num = $code3[$i];
$numnext = $code3[$i+1];
$code0 .= $trans2[$num][$numnext][0];
}
return $code0;
}
function trs2($code2, $level) {
global $trans2, $memo;
if($level == 1) { // n+2 pads with arrows
return trs3($code2);
}
// to directions again
$numnext = $code2[0];
$perms = $trans2["A"][$numnext];
foreach($perms as $key => $perm) {
$postpermtest = trs2(str_split($perm), $level + 1);
if($key == 0 || $postlgt > strlen($postpermtest)) {
$postlgt = strlen($postpermtest);
$postperm = $postpermtest;
}
}
$code0 = $postperm;
$codelgt = sizeof($code2);
for($i=0;$i<$codelgt-1;$i++) {
$num = $code2[$i];
$numnext = $code2[$i+1];
$perms = $trans2[$num][$numnext];
foreach($perms as $key => $perm) {
$postpermtest = trs2(str_split($perm), $level + 1);
if($key == 0 || $postlgt > strlen($postpermtest)) {
$postlgt = strlen($postpermtest);
$postperm = $postpermtest;
}
}
$code0 .= $postperm;
}
return $code0;
}
function trs1($code1) {
global $trans1;
// from numbers to directions
$numnext = $code1[0];
$perms = $trans1["A"][$numnext];
foreach($perms as $key => $perm) {
$postpermtest = trs2(str_split($perm), 0);
if($key == 0 || $postlgt > strlen($postpermtest)) {
$postlgt = strlen($postpermtest);
$postperm = $postpermtest;
}
}
$code0 = $postperm;
$codelgt = sizeof($code1);
for($i=0;$i<$codelgt-1;$i++) {
$num = $code1[$i];
$numnext = $code1[$i+1];
$perms = $trans1[$num][$numnext];
foreach($perms as $key => $perm) {
$postpermtest = trs2(str_split($perm), 0);
if($key == 0 || $postlgt > strlen($postpermtest)) {
$postlgt = strlen($postpermtest);
$postperm = $postpermtest;
}
}
$code0 .= $postperm;
}
return $code0;
}
$sum = 0;
// begin loop
foreach($codes as $key => $code1) {
echo "Number: ".$codesorg[$key]."\n";
$code0 = trs1($code1);
echo "Code: ".strlen($code0)."\n";
$sum += strlen($code0) * $codesorg[$key];
// end loop
}
echo "\n".$sum."\n";
?>Part 2:
<?php
$trans1["0"]["0"] = array("A");
$trans1["0"]["1"] = array("^<A"); // not the other way around!
$trans1["0"]["2"] = array("^A");
$trans1["0"]["3"] = array("^>A", ">^A");
$trans1["0"]["4"] = array("^^<A", "^<^"); // not left first!
$trans1["0"]["5"] = array("^^A");
$trans1["0"]["6"] = array("^^>A", "^>^A", ">^^");
$trans1["0"]["7"] = array("^^^<A", "^^<^A", "^<^^A"); // not left first!
$trans1["0"]["8"] = array("^^^A");
$trans1["0"]["9"] = array("^^^>A", "^^>^", "^>^^", ">^^^");
$trans1["0"]["A"] = array(">A");
$trans1["1"]["0"] = array(">vA"); // not the other way around!
$trans1["1"]["1"] = array("A");
$trans1["1"]["2"] = array(">A");
$trans1["1"]["3"] = array(">>A");
$trans1["1"]["4"] = array("^A");
$trans1["1"]["5"] = array("^>A", ">^A");
$trans1["1"]["6"] = array("^>>A", ">^>A", ">>^A");
$trans1["1"]["7"] = array("^^A");
$trans1["1"]["8"] = array("^^>A", "^>^A", ">^^A");
$trans1["1"]["9"] = array("^^>>A", "^>^>A", ">^^>A", "^>>^A", ">^>^A", ">>^^A");
$trans1["1"]["A"] = array(">>vA", ">v>A"); // not down first!
$trans1["2"]["0"] = array("vA");
$trans1["2"]["1"] = array("<A");
$trans1["2"]["2"] = array("A");
$trans1["2"]["3"] = array(">A");
$trans1["2"]["4"] = array("^<A", "<^A");
$trans1["2"]["5"] = array("^A");
$trans1["2"]["6"] = array("^>A", ">^A");
$trans1["2"]["7"] = array("^^<A", "^<^A", "<^^A");
$trans1["2"]["8"] = array("^^A");
$trans1["2"]["9"] = array("^^>A", "^>^A", ">^^A");
$trans1["2"]["A"] = array("v>A", ">vA");
$trans1["3"]["0"] = array("<vA", "v<A");
$trans1["3"]["1"] = array("<<A");
$trans1["3"]["2"] = array("<A");
$trans1["3"]["3"] = array("A");
$trans1["3"]["4"] = array("^<<A", "<^<A", "<<^A");
$trans1["3"]["5"] = array("^<A", "<^A");
$trans1["3"]["6"] = array("^A");
$trans1["3"]["7"] = array("^^<<A", "^<^<A", "<^^<A", "^<<^A", "<^<^A", "<<^^A"); // order matters
$trans1["3"]["8"] = array("^^<A", "^<^A", "<^^A");
$trans1["3"]["9"] = array("^^A");
$trans1["3"]["A"] = array("vA");
$trans1["4"]["0"] = array(">vvA", "v>vA"); // not right last!
$trans1["4"]["1"] = array("vA");
$trans1["4"]["2"] = array("v>A", ">vA");
$trans1["4"]["3"] = array("v>>A", ">v>A", ">>vA");
$trans1["4"]["4"] = array("A");
$trans1["4"]["5"] = array(">A");
$trans1["4"]["6"] = array(">>A");
$trans1["4"]["7"] = array("^A");
$trans1["4"]["8"] = array("^>A", ">^A");
$trans1["4"]["9"] = array("^>>A", ">^>A", ">>^A");
$trans1["4"]["A"] = array(">>vvA", ">v>vA", "v>>vA", ">vv>A", "v>v>A"); // not 2 x down first!
$trans1["5"]["0"] = array("vvA");
$trans1["5"]["1"] = array("v<A", "<vA");
$trans1["5"]["2"] = array("vA");
$trans1["5"]["3"] = array("v>A", ">vA");
$trans1["5"]["4"] = array("<A");
$trans1["5"]["5"] = array("A");
$trans1["5"]["6"] = array(">A");
$trans1["5"]["7"] = array("^<A", "<^A");
$trans1["5"]["8"] = array("^A");
$trans1["5"]["9"] = array("^>A", ">^A");
$trans1["5"]["A"] = array("vv>A", "v>vA", ">vvA");
$trans1["6"]["0"] = array("vv<A", "v<vA", "<vvA");
$trans1["6"]["1"] = array("v<<A", "<v<A", "<<vA");
$trans1["6"]["2"] = array("v<A", "<vA");
$trans1["6"]["3"] = array("vA");
$trans1["6"]["4"] = array("<<A");
$trans1["6"]["5"] = array("<A");
$trans1["6"]["6"] = array("A");
$trans1["6"]["7"] = array("^<<A", "<^<A", "<<^A");
$trans1["6"]["8"] = array("^<A", "<^A");
$trans1["6"]["9"] = array("^A");
$trans1["6"]["A"] = array("vvA");
$trans1["7"]["0"] = array(">vvvA", "v>vvA", "vv>vA"); // not right last!
$trans1["7"]["1"] = array("vvA");
$trans1["7"]["2"] = array("vv>A", "v>vA", ">vvA");
$trans1["7"]["3"] = array("vv>>A", "v>v>A", ">vv>A", "v>>vA", ">v>vA", ">>vvA");
$trans1["7"]["4"] = array("vA");
$trans1["7"]["5"] = array("v>A", ">vA");
$trans1["7"]["6"] = array("v>>A", ">v>A", ">>vA");
$trans1["7"]["7"] = array("A");
$trans1["7"]["8"] = array(">A");
$trans1["7"]["9"] = array(">>A");
$trans1["7"]["A"] = array(">>vvvA", ">v>vvA", ">vv>vA", ">vvv>A", "v>>vvA", "v>v>vA", "v>vv>A", "vv>>vA", "vv>v>A"); // not 3 x down first!
$trans1["8"]["0"] = array("vvvA");
$trans1["8"]["1"] = array("vv<A", "v<vA", "<vvA");
$trans1["8"]["2"] = array("vvA");
$trans1["8"]["3"] = array("vv>A", "v>vA", ">vvA");
$trans1["8"]["4"] = array("v<A", "<vA");
$trans1["8"]["5"] = array("vA");
$trans1["8"]["6"] = array("v>A", ">vA");
$trans1["8"]["7"] = array("<A");
$trans1["8"]["8"] = array("A");
$trans1["8"]["9"] = array(">A");
$trans1["8"]["A"] = array(">vvvA", "v>vvA", "vv>vA", "vvv>A");
$trans1["9"]["0"] = array("vvv<A", "vv<vA", "v<vvA", "<vvvA");
$trans1["9"]["1"] = array("vv<<A", "v<v<A", "<vv<A", "v<<vA", "<v<vA", "<<vvA");
$trans1["9"]["2"] = array("vv<A", "v<vA", "<vvA");
$trans1["9"]["3"] = array("vvA");
$trans1["9"]["4"] = array("v<<A", "<v<A", "<<vA");
$trans1["9"]["5"] = array("v<A", "<vA");
$trans1["9"]["6"] = array("vA");
$trans1["9"]["7"] = array("<<A");
$trans1["9"]["8"] = array("<A");
$trans1["9"]["9"] = array("A");
$trans1["9"]["A"] = array("vvvA");
$trans1["A"]["0"] = array("<A");
$trans1["A"]["1"] = array("^<<A", "<^<A"); // not up last!
$trans1["A"]["2"] = array("^<A", "<^A");
$trans1["A"]["3"] = array("^A");
$trans1["A"]["4"] = array("^^<<A", "^<^<A", "<^^<A", "^<<^A", "<^<^A"); // not 2 x left first!
$trans1["A"]["5"] = array("^^<A", "^<^A", "<^^A");
$trans1["A"]["6"] = array("^^A");
$trans1["A"]["7"] = array("^^^<<A", "^^<^<A", "^<^^<A", "<^^^<A", "^^<<^A", "^<^<^A", "<^^<^A", "^<<^^A", "<^<^^A"); // not 2 x left first!
$trans1["A"]["8"] = array("^^^<A", "^^<^A", "^<^^A", "<^^^A");
$trans1["A"]["9"] = array("^^^A");
$trans1["A"]["A"] = array("A");
$trans2["<"]["<"] = array("A");
$trans2["<"]["^"] = array(">^A");
$trans2["<"][">"] = array(">>A");
$trans2["<"]["v"] = array(">A");
$trans2["<"]["A"] = array(">>^A", ">^>A");
$trans2["^"]["<"] = array("v<A");
$trans2["^"]["^"] = array("A");
$trans2["^"][">"] = array("v>A", ">vA");
$trans2["^"]["v"] = array("vA");
$trans2["^"]["A"] = array(">A");
$trans2[">"]["<"] = array("<<A");
$trans2[">"]["^"] = array("<^A", "^<A");
$trans2[">"][">"] = array("A");
$trans2[">"]["v"] = array("<A");
$trans2[">"]["A"] = array("^A");
$trans2["v"]["<"] = array("<A");
$trans2["v"]["^"] = array("^A");
$trans2["v"][">"] = array(">A");
$trans2["v"]["v"] = array("A");
$trans2["v"]["A"] = array("^>A", ">^A");
$trans2["A"]["<"] = array("v<<A", "<v<A");
$trans2["A"]["^"] = array("<A");
$trans2["A"][">"] = array("vA");
$trans2["A"]["v"] = array("v<A", "<vA");
$trans2["A"]["A"] = array("A");
///////////////////////////////////////////////////////////
$input = file_get_contents('./d21input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
if(strlen($line)>2) {
preg_match('/\d+/', $line, $tmp);
$codesorg[] = $tmp[0];
$codes[] = str_split($line);
}
}
function trs3($code3) {
global $trans2, $memo2;
$codelgtorg = sizeof($code3);
// to directions the last time
$numnext = $code3[0];
$tmpcode0 = "A".$numnext;
if(!isset($memo2[$tmpcode0])) {
$memo2[$tmpcode0] = strlen($trans2["A"][$numnext][0]);
}
$codelgt = $memo2[$tmpcode0];
for($i=0;$i<$codelgtorg-1;$i++) {
$num = $code3[$i];
$numnext = $code3[$i+1];
$tmpcode0 = $num.$numnext;
if(!isset($memo2[$tmpcode0])) {
$memo2[$tmpcode0] = strlen($trans2[$num][$numnext][0]);
}
$codelgt += $memo2[$tmpcode0];
}
return $codelgt;
}
function trs2($code2, $level) {
global $trans2, $memo;
if($level == 24) { // n+2 pads with arrows
return trs3($code2);
}
// to directions again
$numnext = $code2[0];
$perms = $trans2["A"][$numnext];
$tmpcode0 = "A".$numnext;
if(isset($memo[$tmpcode0][$level])) {
$postlgt = $memo[$tmpcode0][$level];
} else {
foreach($perms as $key => $perm) {
$postlgttmp = trs2(str_split($perm), $level + 1);
if($key == 0 || $postlgt > $postlgttmp) {
$postlgt = $postlgttmp;
}
}
$memo[$tmpcode0][$level] = $postlgt;
}
$permlgt = $postlgt;
$codelgtorg = sizeof($code2);
for($i=0;$i<$codelgtorg-1;$i++) {
$num = $code2[$i];
$numnext = $code2[$i+1];
$perms = $trans2[$num][$numnext];
$tmpcode0 = $num.$numnext;
if(isset($memo[$tmpcode0][$level])) {
$postlgt = $memo[$tmpcode0][$level];
} else {
foreach($perms as $key => $perm) {
$postlgttmp = trs2(str_split($perm), $level + 1);
if($key == 0 || $postlgt > $postlgttmp) {
$postlgt = $postlgttmp;
}
}
$memo[$tmpcode0][$level] = $postlgt;
}
$permlgt += $postlgt;
}
return $permlgt;
}
function trs1($code1) {
global $trans1;
// from numbers to directions
$numnext = $code1[0];
$perms = $trans1["A"][$numnext];
$permlgt = 0;
foreach($perms as $key => $perm) {
$postlgttmp = trs2(str_split($perm), 0);
if($key == 0 || $postlgt > $postlgttmp) {
$postlgt = $postlgttmp;
}
}
$permlgt = $postlgt;
$codelgt = sizeof($code1);
for($i=0;$i<$codelgt-1;$i++) {
$num = $code1[$i];
$numnext = $code1[$i+1];
$perms = $trans1[$num][$numnext];
foreach($perms as $key => $perm) {
$postlgttmp = trs2(str_split($perm), 0);
if($key == 0 || $postlgt > $postlgttmp) {
$postlgt = $postlgttmp;
}
}
$permlgt += $postlgt;
}
return $permlgt;
}
$memo = array();
$memo2 = array();
$sum = 0;
// begin loop
foreach($codes as $key => $code1) {
echo "Number : ".$codesorg[$key]."\n";
$code0 = trs1($code1);
echo "Codelgt: ".$code0."\n";
$sum += $code0 * $codesorg[$key];
// end loop
}
echo "\n".$sum."\n";
?>Scroggs, day 21
A new December and a new bunch of puzzles from mscroggs.co.uk.
The 2 3-digit numbers will be axb and cxd. We want a*x*b = c*x*d, and 99 < axb < cxd. Then the answer is axb.
a*x*b = c*x*d <=>
a*b = c*d
These 4 digits are all different. A possible solution is 1*6 = 2*3 = 6. Then a would be as small as possible, 1. And 6 is the smallest number, that can be factorized in 2 very different ways. So my guess is axb = 1×6.
For x just choose the smallest digit available, 4.
axb = 146.
When I got a hint, that this answer was wrong, I looked at it again. We get something smaller, if x is smaller than 4. This is possible for x = 3, axb = 138, cxd = 234 or 432.
Advent of Code, day 20
This December I participated in Advent of Code.
More Dijkstra! Part 1 was sort of easy: Remove one wall part and try again. But what I ended up with in part 2 runs for both parts, and much better, and also is much closer to what the puzzle said in words. Though I struggled a bit with interpreting the rules: Question. And with an off by one error: Question.
Part 1 and 2:
<?php
function find($char) {
global $map, $mapwid, $maphei;
for($x=0;$x<$mapwid;$x++) {
for($y=0;$y<$maphei;$y++) {
if($map[$y][$x] == $char) {
return array($x,$y);
}
}
}
}
////////////////////////////////////////////////////////////////
$input = file_get_contents('./d20input2.txt', true);
// limit: how many steps saved, before a route counts
// part 1, test: 2, actual: 100
// part 2: test: 50, actual: 100
$limit = 100;
// cheat: how many steps in a row can ignore walls
// part 1: 2
// part 2: testa: 4, testb: 20, actual: 20
$cheat = 20;
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
if(strlen($line)>2) {
$map[] = str_split($line);
}
}
$maphei = sizeof($map);
$mapwid = sizeof($map[0]);
$coords = find("S");
$orgx = $coords[0];
$orgy = $coords[1];
function dijkstra($map) {
global $orgx, $orgy, $maphei, $mapwid, $visit;
$unvis[] = array($orgx, $orgy, 0, array());
// Create a set of all unvisited nodes: the unvisited set.
// Assign to every node a distance from start.
for($x=0;$x<$mapwid;$x++) {
for($y=0;$y<$maphei;$y++) {
if($map[$y][$x] == "." || $map[$y][$x] == "E") {
$unvis[] = array($x, $y, 1000000, array());
}
}
}
$wearedone = 0;
while($wearedone == 0) {
//From the unvisited set, select the current node to be the one with the smallest (finite) distance
$dist = 1000000;
foreach($unvis as $key => $node) {
if($node[2] < $dist) {
$dist = $node[2];
$x = $node[0];
$y = $node[1];
$mykey = $key;
}
}
// For the current node, consider all of its unvisited neighbors and update their distances through the current node
foreach($unvis as $key => $node) {
$neighb = abs($x - $node[0]) + abs($y - $node[1]);
if($neighb == 1) {
//print("neighbour:\n");
//print_r($node);
if($x - $node[0] == 1) {
// neighbour to the left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = array($x, $y);
}
}
if($x - $node[0] == -1) {
// neighbour to the right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = array($x, $y);
}
}
if($y - $node[1] == 1) {
// neighbour above
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = array($x, $y);
}
}
if($y - $node[1] == -1) {
// neighbour below
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = array($x, $y);
}
}
}
}
// the current node is removed from the unvisited set
$visit[$x][$y][] = $unvis[$mykey];
unset($unvis[$mykey]);
if($map[$y][$x] == "E") {
return $dist;
}
}
}
$best = dijkstra($map);
for($i=1;$i<$maphei-1;$i++) {
for($j=1;$j<$mapwid-1;$j++) {
// if i am a free cell, no. 0
// my cheat begins
// my destination will be at most n cells away
// but still has to be on the map
// check all free cells within n steps distance
// always assume efficient routes
// as meandering ones will be longer
if($map[$i][$j] == "#") {
continue;
}
for($a=max($i-$cheat,0);$a<=min($i+$cheat,$maphei-1);$a++) {
for($b=max($j-$cheat,0);$b<=min($j+$cheat,$mapwid-1);$b++) {
$ytmp = abs($a-$i);
$xtmp = abs($b-$j);
$alltmp = $xtmp + $ytmp;
if(1<$alltmp && $alltmp<=$cheat) {
// we have a candidate!
if($map[$a][$b] != "#") {
$newdist = $best - ($visit[$j][$i][0][2] - $visit[$b][$a][0][2]) + $alltmp;
if(isset($alldist[$newdist])) {
$alldist[$newdist]++;
} else {
$alldist[$newdist] = 1;
}
}
}
}
} // end big loop
}
}
$cheats = 0;
for($i=0;$i<10000;$i+=2) {
if(!isset($alldist[$i])) {
$alldist[$i] = 0;
}
}
for($i=$best-$limit;$i>0;$i-=2) {
$lgt = $i;
$no = $alldist[$i];
if($no > 0) {
print("There are $no cheats that save ".$best-$lgt." picoseconds.\n");
}
if($lgt <= $best - $limit) {
$cheats += $no;
}
}
echo $cheats."\n";
?>Scroggs, day 20
A new December and a new bunch of puzzles from mscroggs.co.uk.
First let’s look at this landscape. For now ignore the green curve.
A solution p(x) has to fit between the blue and the red lines. It has to fit under the blue and over the red.
Could p(x) = a? No, a straight horizontal line wouldn’t be able to stay over the red line always.
Could p(x) = a + bx? Then p(0) = a, a positive integer. Then p(1) = a + b. The blue line goes through (1,1). And p(1) is an integer, at most 0. So this p(x) goes through (0,a), down to (1,a+b) and then up, up, up to stay above the red line. Not possible.
Could p(x) = a + bx + cx2? This is similar to the blue line, so maybe we choose p(x) = x2 – 2x + 2 – a-little-bit. This would always be under the blue line. First guess: p(x) = x2 – 2x + 1.
Is this above the red line? That’s equivalent to this being true:
4x – 9 < x2 – 2x + 1 <=>
0 < x2 – 6x + 10 <=>
0 < x2 – 6x + 9 + 1 <=>
0 < (x – 3)2 + 1
And yes, this is always true.
I haven’t checked whether this is the only solution.
p(23) = 232 – 2*23 + 1 = 484.
A closeup:
Advent of Code, day 19
This December I participated in Advent of Code.
The program was rather easy to build. This day I had to learn a new trick to scale it: Memoization. Question, early version of part 1. I only show part 2 below, because the only difference between the 2 parts is a bit at the end of the program. (Probably there were more differences originally, but I forgot to save the part 1 version.)
Part 2:
<?php
function dig($design, $level) {
// towels are at most 8 characters long
global $towels, $dug;
if(isset($dug[$design])) {
return $dug[$design];
}
$hit = 0;
for($i=8;$i>0;$i--) {
// if the beginning of this design is towel
if(in_array(substr($design, 0, $i), $towels)) {
if(strlen($design) == $i) {
$dug[$design] = 1;
$hit += 1;
}
$tmphit = dig(substr($design, $i), $level+1);
if($tmphit > 0) {
$dug[$design] = $tmphit;
$hit += $tmphit;
}
}
}
$dug[$design] = $hit;
return $hit;
}
///////////////////////////////////////////////////////////
$input = file_get_contents('./d19input2.txt', true);
$phase = 1;
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
if(strlen($line)>2) {
if($phase == 1) {
$towels = explode(", ", $line);
} else {
$designs[] = $line;
}
} else {
$phase = 2;
}
}
$hits = 0;
foreach($designs as $design) {
echo "$design\n";
$tmphit = dig($design, 0);
if($tmphit > 0) {
// part 1:
//$hits++;
// part 2:
$hits += $tmphit;
}
}
echo $hits."\n";Scroggs, day 19
A new December and a new bunch of puzzles from mscroggs.co.uk.
I actually did this in a slow way and then realized, there was a quick way.
Slow way: how many ways can you do a 1 digit number (1, the number 9), a 2 digit number (8, the numbers 18, 27, 36 etc.), a 3 digit number etc. Add these together: 1+8+… = 256.
Quick way: This is stars and bars like. Imagine we have 9 stars. *********
If we add no bars, this represents the number 9. All the stars end up in the same bin.
If we add 1 bar, this is a 2 digit number. **|******* represents 27, 2 stars in the first bin, 7 in the second.
If we add 8 bars, it represents the 9 digit number 111111111. Every star is alone in a bin.
With 9 stars, there are 8 positions available between them, 8 ways to add 1 bar between 2 stars. For every one of these 8 positions, we make a decision: add a bar, yes or no? 8 choices, each with 2 options, 28 = 256.
Advent of Code, day 18
This December I participated in Advent of Code.
More Dijkstra! I just modified some program from an earlier day for part 1. For part 2, I added functionality to walk x steps, and then played around with x, until I rather quickly got what I wanted, the coordinates of the offending byte.
Part 1:
<?php
// array of coordinates in
function print_coords() {
global $map, $coords, $mapwid, $maphei;
$done = 0;
foreach($coords as $coord) {
$x = $coord[0];
$y = $coord[1];
$map[$x][$y] = "#";
$done++;
if($done == 1024) {
break;
}
}
print_map();
}
function print_map() {
global $map, $mapwid, $maphei;
for($y=-1;$y<=$maphei;$y++) {
for($x=-1;$x<=$mapwid;$x++) {
if(isset($map[$x][$y])) {
echo $map[$x][$y];
} else {
echo ".";
}
}
echo "\n";
}
echo "\n";
}
function find($char) {
global $map, $mapwid, $maphei;
for($x=0;$x<$mapwid;$x++) {
for($y=0;$y<$maphei;$y++) {
if($map[$y][$x] == $char) {
return array($x,$y);
}
}
}
}
////////////////////////////////////////////////////////////////
$input = file_get_contents('./d18input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
if(strlen($line)>2) {
preg_match_all('/-?\d+/', $line, $byte);
$coords[] = $byte[0];
}
}
// test: 0-6, actual: 0-70
$maphei = 71;
$mapwid = 71;
for($i=0;$i<$mapwid;$i++) {
for($j=0;$j<$maphei;$j++) {
$map[$j][$i] = ".";
}
}
for($i=-1;$i<=$mapwid;$i++) {
$map[-1][$i] = "#";
$map[$maphei][$i] = "#";
}
for($j=-1;$j<=$maphei;$j++) {
$map[$j][-1] = "#";
$map[$j][$mapwid] = "#";
}
$map[0][0] = "S";
$map[70][70] = "E";
print_coords($map);
$coords = find("S");
$x = $coords[0];
$y = $coords[1];
$unvis[] = array($x, $y, 0, ">");
// Create a set of all unvisited nodes: the unvisited set.
// Assign to every node a distance from start.
for($x=0;$x<$mapwid;$x++) {
for($y=0;$y<$maphei;$y++) {
if($map[$y][$x] == "." || $map[$y][$x] == "E") {
$unvis[] = array($x, $y, 1000000, ".");
}
}
}
$wearedone = 0;
while($wearedone == 0) {
//From the unvisited set, select the current node to be the one with the smallest (finite) distance
$dist = 1000000;
foreach($unvis as $key => $node) {
if($node[2] < $dist) {
$dist = $node[2];
$x = $node[0];
$y = $node[1];
$dir = $node[3];
$mykey = $key;
}
}
// shortest path: 83432
if($dist > 83435) {
$wearedone = 1;
continue;
}
// For the current node, consider all of its unvisited neighbors and update their distances through the current node
foreach($unvis as $key => $node) {
$neighb = abs($x - $node[0]) + abs($y - $node[1]);
if($neighb == 1) {
//print("neighbour:\n");
//print_r($node);
if($x - $node[0] == 1) {
// neighbour to the left
if($dir == "<") {
// i am headed left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "<";
}
}
if($dir == "^") {
// i am headed up
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "<";
}
}
if($dir == "v") {
// i am headed down
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "<";
}
}
}
if($x - $node[0] == -1) {
// neighbour to the right
if($dir == ">") {
// i am headed right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = ">";
}
}
if($dir == "^") {
// i am headed up
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = ">";
}
}
if($dir == "v") {
// i am headed down
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = ">";
}
}
}
if($y - $node[1] == 1) {
// neighbour above
if($dir == "^") {
// i am headed up
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "^";
}
}
if($dir == "<") {
// i am headed left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "^";
}
}
if($dir == ">") {
// i am headed right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "^";
}
}
}
if($y - $node[1] == -1) {
// neighbour below
if($dir == "v") {
// i am headed down
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "v";
}
}
if($dir == "<") {
// i am headed left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "v";
}
}
if($dir == ">") {
// i am headed right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "v";
}
}
}
}
}
// the current node is removed from the unvisited set
$visit[] = array($x, $y, $dist, $dir);
unset($unvis[$mykey]);
if($map[$y][$x] == "E") {
print_map();
print("shortest path: $dist\n");
$wearedone = 1;
continue;
}
}
?>Part 2:
<?php
// test: 0-6, actual: 0-70
$actual = 1;
if($actual == 0) {
// test
$donemax = 12;
$maxsz = 6;
$inputfile = './d18input1.txt';
} else {
// actual
$donemax = 1024;
$maxsz = 70;
$inputfile = './d18input2.txt';
}
function add_coord($now) {
global $map, $coords, $newestcoord;
$x = $coords[$now][0];
$y = $coords[$now][1];
$map[$x][$y] = "#";
$newestcoord = "($x,$y)";
}
// array of coordinates in
function print_coords() {
global $map, $coords, $mapwid, $maphei, $donemax;
$done = 0;
foreach($coords as $coord) {
$x = $coord[0];
$y = $coord[1];
$map[$x][$y] = "#";
$done++;
if($done == $donemax) {
break;
}
}
print_map();
}
function print_map() {
global $map, $mapwid, $maphei;
for($y=-1;$y<=$maphei;$y++) {
for($x=-1;$x<=$mapwid;$x++) {
if(isset($map[$x][$y])) {
echo $map[$x][$y];
} else {
echo ".";
}
}
echo "\n";
}
echo "\n";
}
function find($char) {
global $map, $mapwid, $maphei;
for($x=0;$x<$mapwid;$x++) {
for($y=0;$y<$maphei;$y++) {
if($map[$y][$x] == $char) {
return array($x,$y);
}
}
}
}
////////////////////////////////////////////////////////////////
$input = file_get_contents($inputfile, true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
if(strlen($line)>2) {
preg_match_all('/-?\d+/', $line, $byte);
$coords[] = $byte[0];
}
}
$maphei = $maxsz + 1;
$mapwid = $maxsz + 1;
for($i=0;$i<$mapwid;$i++) {
for($j=0;$j<$maphei;$j++) {
$map[$j][$i] = ".";
}
}
for($i=-1;$i<=$mapwid;$i++) {
$map[-1][$i] = "#";
$map[$maphei][$i] = "#";
}
for($j=-1;$j<=$maphei;$j++) {
$map[$j][-1] = "#";
$map[$j][$mapwid] = "#";
}
$map[0][0] = "S";
$map[$maxsz][$maxsz] = "E";
$xy = find("S");
$orgx = $xy[0];
$orgy = $xy[1];
function dijkstra() {
global $map, $orgx, $orgy, $mapwid, $maphei;
$x = $orgx;
$y = $orgy;
$wearedone = 0;
// Create a set of all unvisited nodes: the unvisited set.
// Assign to every node a distance from start.
$unvis[] = array($orgx, $orgy, 0, ">");
for($x=0;$x<$mapwid;$x++) {
for($y=0;$y<$maphei;$y++) {
if($map[$y][$x] == "." || $map[$y][$x] == "E") {
$unvis[] = array($x, $y, 1000000, ".");
}
}
}
while($wearedone == 0) {
//From the unvisited set, select the current node to be the one with the smallest (finite) distance
$dist = 1000000;
foreach($unvis as $key => $node) {
if($node[2] < $dist) {
$dist = $node[2];
$x = $node[0];
$y = $node[1];
$dir = $node[3];
$mykey = $key;
}
}
// shortest path: 83432
if($dist > 83435) {
$wearedone = 1;
continue;
}
// For the current node, consider all of its unvisited neighbors and update their distances through the current node
foreach($unvis as $key => $node) {
$neighb = abs($x - $node[0]) + abs($y - $node[1]);
if($neighb == 1) {
//print("neighbour:\n");
//print_r($node);
if($x - $node[0] == 1) {
// neighbour to the left
if($dir == "<") {
// i am headed left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "<";
}
}
if($dir == "^") {
// i am headed up
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "<";
}
}
if($dir == "v") {
// i am headed down
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "<";
}
}
}
if($x - $node[0] == -1) {
// neighbour to the right
if($dir == ">") {
// i am headed right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = ">";
}
}
if($dir == "^") {
// i am headed up
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = ">";
}
}
if($dir == "v") {
// i am headed down
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = ">";
}
}
}
if($y - $node[1] == 1) {
// neighbour above
if($dir == "^") {
// i am headed up
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "^";
}
}
if($dir == "<") {
// i am headed left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "^";
}
}
if($dir == ">") {
// i am headed right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "^";
}
}
}
if($y - $node[1] == -1) {
// neighbour below
if($dir == "v") {
// i am headed down
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "v";
}
}
if($dir == "<") {
// i am headed left
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "v";
}
}
if($dir == ">") {
// i am headed right
$newdist = $dist + 1;
if($newdist < $node[2]) {
$unvis[$key][2] = $newdist;
$unvis[$key][3] = "v";
}
}
}
}
}
// the current node is removed from the unvisited set
$visit[] = array($x, $y, $dist, $dir);
unset($unvis[$mykey]);
if($map[$y][$x] == "E") {
return $dist;
$wearedone = 1;
continue;
}
}
return 1000000;
}
$now = 0;
$newdist = 0;
$newestcoord = "";
for($i=0;$i<2750;$i++) {
add_coord($now);
$now++;
}
while($newdist < 1000000) {
add_coord($now);
$now++;
$newdist = dijkstra();
echo $newdist." ";
}
echo "\n".$newestcoord."\n";
?>Scroggs, day 18
A new December and a new bunch of puzzles from mscroggs.co.uk.
I don’t quite know how to get to this logically, so I wrote a program. k = 756.
28 = 22*7
756 = 108*7 = 22*33*7
28*756/(28+756) =
22*7*22*33*7/(4*7+108*7) =
24*33*72/(112*7) =
24*33*72/(24*72) =
33, integer
Stuff from ommadawn.dk (Lise Andreasen) 
