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.

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

40 = 2³ * 5. The number 8 arises because a factor can include 2 0-3 times and 5 0-1 times, 4 options and 2 options, 4*2 = 8.

2²⁶ * 5 * 7⁵ * 11². 27*2*6*3 = 972.