This December I participated in Advent of Code.

One of those days, where I probably grumbled a lot. Part 1 was easy. I chose an algorithm, where I went through a list of all the expressions, checked whether the gate’s output could be calculated (and if yes, deleted the expression from the list), looped back and did it again, until the list was empty. Part 2… I tried several different approaches. Reading hints from others, I ultimately used a free online diagram tool, Mermaid, that accepts text input. Perfect. I wrote a small program to turn the input into something Mermaid could understand (every value, value, gate, value, turned into 2 x value, arrow, value). Then I tried to analyze this diagram. Printed a lot of full adders. And began copying the diagram on to these. Every time the diagram wouldn’t fit, I’d found a swap. Then it took some thinking to figure out how to swap back. But I got there!

Part 1:

<?php

///////////////////////////////////////

$input = file_get_contents('./d24input2.txt', true);

foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>2) {
    // x00: 1
    if(preg_match("/^(\w+): (\d)$/", $line, $m)) {
      $values[$m[1]] = $m[2];
    }
    // ntg XOR fgs -> mjb
    if(preg_match("/->/", $line, $m)) {
      $m = explode(" ", $line);
      $expr[] = $m;
    }
  }
}

while(sizeof($expr) > 0) {
  foreach($expr as $key => $exp) {
    $val1 = $exp[0];
    $val2 = $exp[2];
    if(isset($values[$val1]) && isset($values[$val2])) {
      $gate = $exp[1];
      $val3 = $exp[4];
      switch($gate) {
        case "AND":
          $values[$val3] =
            $values[$val1] * $values[$val2];
          break;
        case "OR":
          $values[$val3] =
            $values[$val1] + $values[$val2] 
            - $values[$val1] * $values[$val2];
          break;
        case "XOR":
          $values[$val3] =
            ($values[$val1] + $values[$val2]) % 2;
          break;
      }
      unset($expr[$key]);
    }
  }
}

$allzs = $values;
foreach($allzs as $key => $posz) {
  if(!preg_match("/z/", $key, $m)) {
    unset($allzs[$key]);
  }
}

print_r($allzs);

$sum = 0;
foreach($allzs as $key => $z) {
  $pos = (int) str_replace("z", "", $key);
  $sum += $z * pow(2, $pos);
}

print("$sum\n");
?>

Part 2:

Big diagram. Small diagrams.

A new December and a new bunch of puzzles from mscroggs.co.uk.

All the possible 3 digit numbers are here. E.g. we have 111, 211, 311, 411, 511, 611 and 711. For these the mean of the first digit is 4. Expanding this to all the possibilities, the mean for every digit is 4. The result is 444.

This December I participated in Advent of Code.

For part 1, I optimized a little. Like only storing the representation of each 3 way computer group once. Also 3d arrays. For part 2… I flirted a little with BK (ehm, can’t remember what that stands for), but that program seemed to never stop. So I did it differently. Just like part 1 asked me to create all the 3 way groups, I now moved on to create all the 4 way groups, 5 way groups etc. As each computer had about 13 friends, this shouldn’t take forever to get through. I think it took 35 minutes. I stopped when I only had 1 group of the current size. Oh yeah, and I changed the data structure a little. (BK was sort of the other way around. Trying to grow 1 large set greedily.)

Part 1:

<?php

//////////////////////////////////

$input = file_get_contents('./d23input2.txt', true);

foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>2) {
    $conn1[] = explode("-", $line);
  }
}

foreach($conn1 as $comp) {
  $comp1 = $comp[0];
  $comp2 = $comp[1];
  $conn2[$comp1][$comp2] = 1;
  $conn2[$comp2][$comp1] = 1;
}

foreach($conn2 as $comp1 => $c1con) {
  foreach($c1con as $comp2 => $cona) {
    foreach($c1con as $comp3 => $conb) {
      // make sure comp2 and comp3 are different
      if(isset($conn2[$comp2][$comp3])) {
        // only store the 3 way connection alphabetically, so as not to store it 6 times
        if(strcmp($comp1,$comp2) < 0 && strcmp($comp2,$comp3) < 0) {
          // only store this set, if one of the computers begin with t
          if(substr($comp1, 0, 1) == "t" || substr($comp2, 0, 1) == "t" || substr($comp3, 0, 1) == "t") {
            $conn3[$comp1][$comp2][$comp3] = 1;
          }
        }
      }
    }
  }
}

$sum = 0;
foreach($conn3 as $a) {
  foreach($a as $b) {
    foreach($b as $c) {
      $sum += $c;
    }
  }
}
print("$sum\n");

?>

Part 2:

<?php

//////////////////////////////////

$input = file_get_contents('./d23input1.txt', true);

foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>2) {
    $conn1[] = explode("-", $line);
  }
}

foreach($conn1 as $comp) {
  $comp1 = $comp[0];
  $comp2 = $comp[1];
  $conn2[$comp1][$comp2] = 1;
  $conn2[$comp2][$comp1] = 1;
}

foreach($conn2 as $comp1 => $c1con) {
  foreach($c1con as $comp2 => $cona) {
    foreach($c1con as $comp3 => $conb) {
      // make sure comp2 and comp3 are different
      if(isset($conn2[$comp2][$comp3])) {
        // only store the 3 way connection alphabetically, so as not to store it 6 times
        if(strcmp($comp1,$comp2) < 0 && strcmp($comp2,$comp3) < 0) {
          //$conn3[$comp1][$comp2][$comp3] = 1;
          $conn3b[] = array($comp1, $comp2, $comp3);
        }
      }
    }
  }
}

$allcomp = array_keys($conn2);

$multiple = sizeof($conn3b);
$connx = $conn3b;
while($multiple > 1) {
  print("No. of sets in the iteration: $multiple\n");
  $conny = array();
  // build new arrays of length y from length x - y = x+1
  foreach($connx as $wayx) {
    foreach($allcomp as $key => $newcomp) {
      // test that computer is not already in array
      if(!in_array($newcomp, $wayx)) {
        $newgood = 1;
        // test that new is connected to all in wayx
        foreach($wayx as $oldcomp) {
          if(!isset($conn2[$oldcomp][$newcomp])) {
            $newgood = 0;
            break;
          }
        }
        if($newgood == 1) {
          // create new wayy
          $wayytmp = $wayx;
          array_push($wayytmp, $newcomp);
          sort($wayytmp);
          if(!in_array($wayytmp, $conny)) {
            $conny[] = $wayytmp;
          }
        }
      }
    }
  }
  
  $multiple = sizeof($conny);
  if($multiple == 1) {
    print("Max set found!\n");
    print_r($conny);
  }
  $connx = $conny;
}

?>

A new December and a new bunch of puzzles from mscroggs.co.uk.

I don’t really have any ideas for solving this. There’s an official solution at the site by now.

This December I participated in Advent of Code.

For this one, it actually took me a long time to understand the instructions. Hence a big comment in the important function. Once that was established, part 1 was sort of easy. For part 2… Oh, wonderful 5d arrays! I had to calculate the price for each sequence, for each buyer. Then I had to sum for all sequences. A bit fiddly.

Part 1:

<?php

function newsecret($num1) {
  /*
  secret number s1
  multiply s1 by 64 - s2
  mix s2 into s1 - s3
  prune s3 - s4

  divide s4 by 32 - s5
  round s5 down to integer - s6
  mix s6 into into s4 - s7
  prune s7 - s8

  multiply s8 by 2048 - s9
  mix s9 into s8 - s10
  prune s10 - s11

  mix a into b: bitwise xor a and b
  prune a: a % 16777216
  */
  
  $num4 = (($num1 * 64) ^ $num1) % 16777216;
  $num8 = (floor($num4 / 32) ^ $num4) % 16777216;
  $num11 = (($num8 * 2048) ^ $num8) % 16777216;
  return $num11;
}

///////////////////////////////////////////

$input = file_get_contents('./d22input1.txt', true);
$rounds = 2000;

foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>0) {
    $secrets[] = (int) $line;
  }
}

$sum = 0;
foreach($secrets as $num) {
  for($i=0;$i<$rounds;$i++) {
    $num = newsecret($num);
  }
  $sum += $num;
}
print("$sum\n");
?>

Part 2:

<?php

function newsecret($num1) {
  /*
  secret number s1
  multiply s1 by 64 - s2
  mix s2 into s1 - s3
  prune s3 - s4

  divide s4 by 32 - s5
  round s5 down to integer - s6
  mix s6 into into s4 - s7
  prune s7 - s8

  multiply s8 by 2048 - s9
  mix s9 into s8 - s10
  prune s10 - s11

  mix a into b: bitwise xor a and b
  prune a: a % 16777216
  */
  
  $num4 = (($num1 * 64) ^ $num1) % 16777216;
  $num8 = (floor($num4 / 32) ^ $num4) % 16777216;
  $num11 = (($num8 * 2048) ^ $num8) % 16777216;
  return $num11;
}

///////////////////////////////////////////

$input = file_get_contents('./d22input2.txt', true);
$rounds = 2000;

foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>0) {
    $secrets[] = (int) $line;
  }
}

// for each buyer
foreach($secrets as $buyer => $numx) {
  // the last 4 changes in price, init
  $numa = 0;
  $numb = 0;
  $numc = 0;
  $numd = 0;
  $numm = 0;
  // for each new secret price
  for($i=0;$i<$rounds;$i++) {
    $numy = newsecret($numx);
    $numn = $numy % 10;
    $numa = $numb;
    $numb = $numc;
    $numc = $numd;
    $numd = $numn - $numm;
    // only if we have 4 changes / 5 prices / i >= 4
    if($i>=4) {
      if(!isset($changes[$numa][$numb][$numc][$numd][$buyer])) {
        $changes[$numa][$numb][$numc][$numd][$buyer] = $numn;
      }
    }
    $numx = $numy;
    $numm = $numn;
  }
}

$bestsum = 0;
// for each sequence, calculate sum
// remember best sum
for($a=-9;$a<=9;$a++) {
  for($b=-9;$b<=9;$b++) {
    for($c=-9;$c<=9;$c++) {
      for($d=-9;$d<=9;$d++) {
        if(isset($changes[$a][$b][$c][$d])) {
          $tmpsum = array_sum($changes[$a][$b][$c][$d]);
          if($tmpsum > $bestsum) {
            $bestsum = $tmpsum;
            $bestseq = "($a,$b,$c,$d)";
          }
        }
      }
    }
  }
}

print("$bestsum $bestseq\n");

?>

A new December and a new bunch of puzzles from mscroggs.co.uk.

Without comment, the solution.

And the 3 digit number is 651.

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