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:

Figure 1 and 2. Program.

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!

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

?>

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.

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";
?>

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 + cx²? This is similar to the blue line, so maybe we choose p(x) = x² – 2x + 2 – a-little-bit. This would always be under the blue line. First guess: p(x) = x² – 2x + 1.

Is this above the red line? That’s equivalent to this being true:

4x – 9 < x² – 2x + 1 <=>

0 < x² – 6x + 10 <=>

0 < x² – 6x + 9 + 1 <=>

0 < (x – 3)² + 1

And yes, this is always true.

I haven’t checked whether this is the only solution.

p(23) = 23² – 2*23 + 1 = 484.

A closeup:

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

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, 2⁸ = 256.

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

?>

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 = 2²*7

756 = 108*7 = 2²*3³*7

28*756/(28+756) =

2²*7*2²*3³*7/(4*7+108*7) =

2⁴*3³*7²/(112*7) =

2⁴*3³*7²/(2⁴*7²) =

3³, integer

This December I participated in Advent of Code.

Part 1 was easy, satisfying, kind of nice to do.

Part 2 on the other hand… I tried a lot of different approaches. What ended up working for me was a combination of spreadsheet and paper. My input is reproduced below in full, as I can’t really explain this without it.

First I translated a bit of the program, say “2,4”, into something I could understand, B = A modulo 8. In the pictures below you find this in cell b19 and k4. I kept going, until I had the whole program. I then filtered out some stuff. The second picture represents the core program. (B3 = 7-B1 is a shortcut I discovered along the way.) The only variables at this point are B1 and C1, the rest depend on these 2. So I create the full table, with all the possible values of B1 and C1. I also create the binary column: This will be part of the number in A from the beginning (let’s call it AA). I throw away some combinations that won’t work, because a bit can’t have 2 values at the same time. Then I go hunting.

My expected output (let’s call it OO) ends with a 0. My full table suggests the smallest possible input (part of AA) is 7, because this only contributes 7 to AA. I register (on paper) 7 (in octal) and ????000111 (in binary) and keep going. The next part of OO is 3. The corresponding input can’t be 0 (the 111 from the previous step would then have to also be 100), but 4 works. This is the smallest option. I register 74 (in octal) and ????000111100 (in binary) and keep going.

And that’s it! That’s how I build AA. The only exception is, that sometimes there are no options for a part of the number, then I go back and choose a bigger part of the input in a previously settled spot. 740 doesn’t work for the next part? Try 741.

Phew!

Part 1:

<?php
$input = file_get_contents('./d17input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
	if(preg_match("/Register A/",$line,$matches)) {
		if(preg_match("/(\d+)/",$line,$matches)) {
			$a = $matches[0];
		}
	}
	if(preg_match("/Register B/",$line,$matches)) {
		if(preg_match("/(\d+)/",$line,$matches)) {
			$b = $matches[0];
		}
	}
	if(preg_match("/Register C/",$line,$matches)) {
		if(preg_match("/(\d+)/",$line,$matches)) {
			$c = $matches[0];
		}
	}
	if(preg_match("/Program/",$line,$matches)) {
		if(preg_match_all("/(\d+)/",$line,$matches)) {
			$prg = $matches[0];
		}
	}
}
$inspoi = 0;
$prgend = sizeof($prg);
$commas = "";
while($inspoi < $prgend) {
	$opcode = $prg[$inspoi];
	$operand = $prg[$inspoi+1];
/*
There are two types of operands; each instruction specifies the type of its operand. The value of a literal operand is the operand itself. For example, the value of the literal operand 7 is the number 7. The value of a combo operand can be found as follows:
    Combo operands 0 through 3 represent literal values 0 through 3.
    Combo operand 4 represents the value of register A.
    Combo operand 5 represents the value of register B.
    Combo operand 6 represents the value of register C.
    Combo operand 7 is reserved and will not appear in valid programs.
*/
	switch($operand) {
		case 0:
		case 1:
		case 2:
		case 3:
			$combo = $operand;
			break;
		case 4:
			$combo = $a;
			break;
		case 5:
			$combo = $b;
			break;
		case 6:
			$combo = $c;
			break;
	}
/*The adv instruction (opcode 0) performs division. The numerator is the value in the A register. The denominator is found by raising 2 to the power of the instruction's combo operand. (So, an operand of 2 would divide A by 4 (2^2); an operand of 5 would divide A by 2^B.) The result of the division operation is truncated to an integer and then written to the A register.*/
	if($opcode == 0) {
		$a = (int) ($a / pow(2, $combo));
	}
/*The bxl instruction (opcode 1) calculates the bitwise XOR of register B and the instruction's literal operand, then stores the result in register B.*/
	if($opcode == 1) {
		$b = $b ^ $operand;
	}
/*The bst instruction (opcode 2) calculates the value of its combo operand modulo 8 (thereby keeping only its lowest 3 bits), then writes that value to the B register.*/
	if($opcode == 2) {
		$b = $combo % 8;
	}
/*The jnz instruction (opcode 3) does nothing if the A register is 0. However, if the A register is not zero, it jumps by setting the instruction pointer to the value of its literal operand; if this instruction jumps, the instruction pointer is not increased by 2 after this instruction.*/
	if($opcode == 3) {
		if($a != 0) {
			$inspoi = $operand;
			continue;
		}
	}
/*The bxc instruction (opcode 4) calculates the bitwise XOR of register B and register C, then stores the result in register B. (For legacy reasons, this instruction reads an operand but ignores it.)*/
	if($opcode == 4) {
		$b = $b ^ $c;
	}
/*The out instruction (opcode 5) calculates the value of its combo operand modulo 8, then outputs that value. (If a program outputs multiple values, they are separated by commas.)*/
	if($opcode == 5) {
		$tmp = $combo % 8;
		echo "$commas$tmp";
		if($commas == "") {
			$commas = ",";
		}
	}
/*The bdv instruction (opcode 6) works exactly like the adv instruction except that the result is stored in the B register. (The numerator is still read from the A register.)*/
	if($opcode == 6) {
		$b = (int) ($a / pow(2, $combo));
	}
/*The cdv instruction (opcode 7) works exactly like the adv instruction except that the result is stored in the C register. (The numerator is still read from the A register.)*/
	if($opcode == 7) {
		$c = (int) ($a / pow(2, $combo));
	}
	$inspoi = $inspoi + 2;
}
echo "\n";
?>

Part 2:

Input:

Register A: 50230824
Register B: 0
Register C: 0
Program: 2,4,1,3,7,5,0,3,1,4,4,7,5,5,3,0

Spreadsheet.