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.

This December I participated in Advent of Code.

The day I didn’t finish within 24 hours.

Ah yes. Shortest path. Dijkstra. My first program for part 1 brute forced, but when I saw part 2, I rewrote part 1. And good thing too! I needed that later in the month.

Even then part 2 needed a long think. I ended up building a model of the map, where every cell occurred 4 times. The 4 parts of each cell represented the direction, I was headed. Going from “left” to “up” was expensive. On the other hand, going from my “up” to the cell above me, to its “up” part, was rather cheap. Anyway. Once I broke down and coded this the right way, the program ran fine. It took some time, but it ran. But this was still just part 1! The program I had now written 3 times.

Part 2 was replacing “<” with “<=”. Don’t just register a shortest path, register them all. And remember to register where this path was going. Which neighbor visited me, resulting in a shortest path. Because later, I needed to retrace all these shortest paths. Recursively.

Part 1:

<?php
function print_map() {
  global $map, $mapwid, $maphei;
  for($y=0;$y<$maphei;$y++) {
    for($x=0;$x<$mapwid;$x++) {
      if(isset($map[$y][$x])) {
        echo $map[$y][$x];
      } 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);
      }
    }
  }
}
function find_short() {
  global $unvis, $maphei, $mapwid;
  $dist = 10000000;
  $newx = -1;
  $newy = -1;
  $newdir = "";
  for($x=0;$x<$mapwid;$x++) {
    if(!isset($unvis[$x])) {
      continue;
    }
    for($y=0;$y<$maphei;$y++) {
      if(!isset($unvis[$x][$y])) {
        continue;
      }
      foreach($unvis[$x][$y] as $dir => $val) {
        if($unvis[$x][$y][$dir][1] < $dist) {
          $newx = $x;
          $newy = $y;
          $newdir = $dir;
          $dist = $unvis[$x][$y][$dir][1];
        }
      }
    }
  }
  return array($newx, $newy, $newdir);
}
function isempty($map, $x, $y) {
  if($map[$y][$x] == ".") {
    return 1;
  } else {
    return 0;
  }
}
////////////////////////////////////////////////////////////////
$input = file_get_contents('./d16input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  //print("$line\n");
  if(strlen($line)>2) {
    $map[] = str_split($line);
  }
}
$maphei = sizeof($map);
$mapwid = sizeof($map[0]);
// Assign to every node a distance from start value.
// explode map - every cell turns into 4 cells
// $map[$y][$x]
// $dimap[$x][$y][dir][type,dist,neigh]
for($x=0;$x<$mapwid;$x++) {
  for($y=0;$y<$maphei;$y++) {
    $dimap[$x][$y]["^"] = array($map[$y][$x], 10000000, array());
    $dimap[$x][$y][">"] = array($map[$y][$x], 10000000, array());
    $dimap[$x][$y]["v"] = array($map[$y][$x], 10000000, array());
    $dimap[$x][$y]["<"] = array($map[$y][$x], 10000000, array());
  }
}
// neigh: (x, y, type, dist)
// vertical neigh
for($x=0;$x<$mapwid;$x++) {
  for($y=1;$y<$maphei-1;$y++) {
    // neigh above?
    if($dimap[$x][$y-1]["^"][0] != "#") {
      $dimap[$x][$y]["^"][2][] = array($x, $y-1, "^", 1);
    }
    // neigh below?
    if($dimap[$x][$y+1]["v"][0] != "#") {
      $dimap[$x][$y]["v"][2][] = array($x, $y+1, "v", 1);
    }
  }
}
// horizontal neigh
for($x=1;$x<$mapwid-1;$x++) {
  for($y=0;$y<$maphei;$y++) {
    // neigh to the right?
    if($dimap[$x+1][$y][">"][0] != "#") {
      $dimap[$x][$y][">"][2][] = array($x+1, $y, ">", 1);
    }
    // neigh to the left?
    if($dimap[$x-1][$y]["<"][0] != "#") {
      $dimap[$x][$y]["<"][2][] = array($x-1, $y, "<", 1);
    }
  }
}
// internal neigh
for($x=0;$x<$mapwid;$x++) {
  for($y=0;$y<$maphei;$y++) {
    $dimap[$x][$y]["^"][2][] = array($x, $y, ">", 1000);
    $dimap[$x][$y]["^"][2][] = array($x, $y, "<", 1000);
    $dimap[$x][$y][">"][2][] = array($x, $y, "^", 1000);
    $dimap[$x][$y][">"][2][] = array($x, $y, "v", 1000);
    $dimap[$x][$y]["v"][2][] = array($x, $y, "<", 1000);
    $dimap[$x][$y]["v"][2][] = array($x, $y, ">", 1000);
    $dimap[$x][$y]["<"][2][] = array($x, $y, "^", 1000);
    $dimap[$x][$y]["<"][2][] = array($x, $y, "v", 1000);
  }
}
// Create a set of all unvisited nodes: the unvisited set.
$unvis = $dimap;
// Assign to every node a distance from start value: for the starting node, it is zero.
$coords = find("S");
$x = $coords[0];
$y = $coords[1];
$unvis[$x][$y]["^"][1] = 1000;
$unvis[$x][$y][">"][1] = 0;
$unvis[$x][$y]["v"][1] = 1000;
$unvis[$x][$y]["<"][1] = 10000000;
$dist = 0;
// begin loop
//for($i=0;$i<2;$i++) {
while($dist<83500) {
  $coords = find_short();
  $x = $coords[0];
  $y = $coords[1];
  if($x == -1 || $y == -1) {
    break;
  }
  $dir = $coords[2];
  $dist = $unvis[$x][$y][$dir][1];
if($dist % 100 == 0) {
  echo "$dist ";
}
  if(sizeof($unvis[$x][$y][$dir][2]) > 0) {  
    // For the current node, consider all of its unvisited neighbors
    // and update their distances through the current node
    foreach($unvis[$x][$y][$dir][2] as $num => $neigh) {
      $neighx = $neigh[0];
      $neighy = $neigh[1];
      $neighdir = $neigh[2];
      $dist2neigh = $neigh[3];
      if(isset($unvis[$neighx][$neighy][$neighdir])) {
        $neighcurdist = $unvis[$neighx][$neighy][$neighdir][1];
        if($dist + $dist2neigh < $neighcurdist) {
          $unvis[$neighx][$neighy][$neighdir][1] = $dist + $dist2neigh;
        }
      } else {
        unset($unvis[$x][$y][$dir][2][$num]);
      }
    }
  }
  
  // After considering all of the current node's unvisited neighbors,
  // the current node is removed from the unvisited set.
  $dimap[$x][$y][$dir][1] = $dist;
  if($dimap[$x][$y][$dir][0] == "E") {
    break;
  }
  unset($unvis[$x][$y][$dir]);
// end loop
}
$coords = find("E");
$x = $coords[0];
$y = $coords[1];
print_r($dimap[$x][$y]);
?>

Part 2:

<?php
function print_map() {
  global $map, $mapwid, $maphei;
  for($y=0;$y<$maphei;$y++) {
    for($x=0;$x<$mapwid;$x++) {
      if(isset($map[$y][$x])) {
        echo $map[$y][$x];
      } 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);
      }
    }
  }
}
function find_short() {
  global $unvis, $maphei, $mapwid;
  $dist = 10000000;
  $newx = -1;
  $newy = -1;
  $newdir = "";
  for($x=0;$x<$mapwid;$x++) {
    if(!isset($unvis[$x])) {
      continue;
    }
    for($y=0;$y<$maphei;$y++) {
      if(!isset($unvis[$x][$y])) {
        continue;
      }
      foreach($unvis[$x][$y] as $dir => $val) {
        if($unvis[$x][$y][$dir][1] < $dist) {
          $newx = $x;
          $newy = $y;
          $newdir = $dir;
          $dist = $unvis[$x][$y][$dir][1];
        }
      }
    }
  }
  return array($newx, $newy, $newdir);
}
////////////////////////////////////////////////////////////////
$input = file_get_contents('./d16input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  //print("$line\n");
  if(strlen($line)>2) {
    $map[] = str_split($line);
  }
}
$maphei = sizeof($map);
$mapwid = sizeof($map[0]);
// Assign to every node a distance from start value.
// explode map - every cell turns into 4 cells
// $map[$y][$x]
// $dimap[$x][$y][dir][type,dist,prev,neigh]
for($x=0;$x<$mapwid;$x++) {
  for($y=0;$y<$maphei;$y++) {
    $dimap[$x][$y]["^"] = array($map[$y][$x], 10000000, array(), array());
    $dimap[$x][$y][">"] = array($map[$y][$x], 10000000, array(), array());
    $dimap[$x][$y]["v"] = array($map[$y][$x], 10000000, array(), array());
    $dimap[$x][$y]["<"] = array($map[$y][$x], 10000000, array(), array());
  }
}
// neigh: (x, y, type, dist)
// vertical neigh
for($x=0;$x<$mapwid;$x++) {
  for($y=1;$y<$maphei-1;$y++) {
    // neigh above?
    if($dimap[$x][$y-1]["^"][0] != "#") {
      $dimap[$x][$y]["^"][3][] = array($x, $y-1, "^", 1);
    }
    // neigh below?
    if($dimap[$x][$y+1]["v"][0] != "#") {
      $dimap[$x][$y]["v"][3][] = array($x, $y+1, "v", 1);
    }
  }
}
// horizontal neigh
for($x=1;$x<$mapwid-1;$x++) {
  for($y=0;$y<$maphei;$y++) {
    // neigh to the right?
    if($dimap[$x+1][$y][">"][0] != "#") {
      $dimap[$x][$y][">"][3][] = array($x+1, $y, ">", 1);
    }
    // neigh to the left?
    if($dimap[$x-1][$y]["<"][0] != "#") {
      $dimap[$x][$y]["<"][3][] = array($x-1, $y, "<", 1);
    }
  }
}
// internal neigh
for($x=0;$x<$mapwid;$x++) {
  for($y=0;$y<$maphei;$y++) {
    $dimap[$x][$y]["^"][3][] = array($x, $y, ">", 1000);
    $dimap[$x][$y]["^"][3][] = array($x, $y, "<", 1000);
    $dimap[$x][$y][">"][3][] = array($x, $y, "^", 1000);
    $dimap[$x][$y][">"][3][] = array($x, $y, "v", 1000);
    $dimap[$x][$y]["v"][3][] = array($x, $y, "<", 1000);
    $dimap[$x][$y]["v"][3][] = array($x, $y, ">", 1000);
    $dimap[$x][$y]["<"][3][] = array($x, $y, "^", 1000);
    $dimap[$x][$y]["<"][3][] = array($x, $y, "v", 1000);
  }
}
// Create a set of all unvisited nodes: the unvisited set.
$unvis = $dimap;
// Assign to every node a distance from start value: for the starting node, it is zero.
$coords = find("S");
$x = $coords[0];
$y = $coords[1];
$unvis[$x][$y]["^"][1] = 1000;
$unvis[$x][$y][">"][1] = 0;
$unvis[$x][$y]["v"][1] = 1000;
$unvis[$x][$y]["<"][1] = 10000000;
$dist = 0;
// begin loop
while(0 < 1) {
  $coords = find_short();
  $x = $coords[0];
  $y = $coords[1];
  if($x == -1 || $y == -1) {
    break;
  }
  $dir = $coords[2];
  $dist = $unvis[$x][$y][$dir][1];
if($dist % 100 == 0) {
  echo "$dist ";
}
  if(sizeof($unvis[$x][$y][$dir][3]) > 0) {  
    // For the current node, consider all of its unvisited neighbors
    // and update their distances through the current node
    foreach($unvis[$x][$y][$dir][3] as $num => $neigh) {
      $neighx = $neigh[0];
      $neighy = $neigh[1];
      $neighdir = $neigh[2];
      $dist2neigh = $neigh[3];
      if(isset($unvis[$neighx][$neighy][$neighdir])) {
        $neighcurdist = $unvis[$neighx][$neighy][$neighdir][1];
        if($dist + $dist2neigh <= $neighcurdist) {
          $unvis[$neighx][$neighy][$neighdir][1] = $dist + $dist2neigh;
          // remember previous
          $unvis[$neighx][$neighy][$neighdir][2][] = array($x, $y, $dir);
        }
      } else {
        unset($unvis[$x][$y][$dir][3][$num]);
      }
    }
  }
  
  // After considering all of the current node's unvisited neighbors,
  // the current node is removed from the unvisited set.
  $dimap[$x][$y][$dir][1] = $dist;
  $dimap[$x][$y][$dir][2] = $unvis[$x][$y][$dir][2];
  if($dimap[$x][$y][$dir][0] == "E") {
    break;
  }
  unset($unvis[$x][$y][$dir]);
// end loop
}
// output distance
$coords = find("E");
$x = $coords[0];
$y = $coords[1];
$min = 10000000;
foreach($dimap[$x][$y] as $key => $distarr) {
  if($distarr[1] < $min) {
    $min = $distarr[1];
    $dir = $key;
  }
}
echo "$min\n";
// traverse all the shortest paths
$points = array( array($x, $y, $dir));
// begin loop
while(sizeof($points) > 0) {
  // i just need the first
  foreach($points as $key => $point) {
    $x = $point[0];
    $y = $point[1];
    $dir = $point[2];
    $prev = $dimap[$x][$y][$dir][2];
    break;
  }
  unset($points[$key]);
  $map[$y][$x] = "O";
  foreach($prev as $pre) {
    $points[] = array($pre[0], $pre[1], $pre[2]);
  }
// end loop
}
print_map();
$cells = 0;
for($i=0;$i<sizeof($map);$i++) {
  for($j=0;$j<sizeof($map[$i]);$j++) {
    if($map[$i][$j] == "O") {
      $cells++;
    }
  }
}
print("$cells\n");
?>

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

Let’s name these numbers:

abc
def
ghi

a * b + c = 46: 5*9+1, 9*5+1, 6*7+4, 7*6+4, 5*8+6, 8*5+6

a, b: 5, 6, 7, 8, 9

c: 1, 4, 6

b + e * h = 12: 3+9*1, 4+8*1, 5+7*1, 7+5*1, 8+4*1, 9+3*1, 1+5*2, 5+1*2, 1+2*4, 2+1*4

New b: 5, 7, 8, 9

e: 1, 3, 4, 5, 7

h: 1, 2

a / d / g = 1: 6/2/3, 6/3/2, 8/2/4, 8/4/2

New a: 6, 8

d, g: 2, 3, 4

Because new a and b: a * b + c = 46: 5*9+1, 9*5+1, 6*7+4, 7*6+4, 5*8+6, 8*5+6

New a: 6, 8

New b: 5, 7

Because new b: b + e * h = 12: 3+9*1, 4+8*1, 5+7*1, 7+5*1, 8+4*1, 9+3*1, 1+5*2, 5+1*2, 1+2*4, 2+1*4

e: 1, 5, 7

h: 1, 2

g – h / i = 1, g = 2, 3, 4, h = 1, 2: 3-1/2, 3-2/1, 4-1/3

New g: 2, 3, 4

i: 1, 2, 3

d, g, h and i can only be among 1, 2, 3, 4, therefore a, b, c, e and f can’t

c = 6

a = 8, b = 5

Because new a: a / d / g = 1: 6/2/3, 6/3/2, 8/2/4, 8/4/2

New d, g: 2, 4

e: 7

h = 1

i = 3

g = 4

d = 2

f = 9

856279413

The product of the red digits is 8*6*7 = 336.

This December I participated in Advent of Code.

I don’t remember part 1 being hard. Tedious, but not hard. All that “if this goes left, then…” I might have to code a general “if I am facing left, and looking to my right…” routine some day.

Part 2 on the other hand… Figuring out the correct recursion when going up or down. If I am trying to move up, but there’s a box partially above me, I have to move that first. Only after it’s moved, can I move. This took endless debugging, and trying to get the test case to work correctly.

I am on my way to always having the functions at the top of the code.

Part 1:

<?php

// map in
function print_map() {
  global $map, $mapwid, $maphei;
  for($j=0;$j<$maphei;$j++) {
    for($i=0;$i<$mapwid;$i++) {
      if(isset($map[$j][$j])) {
        echo $map[$j][$i];
      } else {
        echo ".";
      }
    }
    echo "\n";
  }
  echo "\n";
}

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

$map = array();
$phase = 1;
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line) < 3) {
    $phase = 2;
  } else {
    if($phase == 1) {
      $map[] = str_split($line);
    } else {
      $moves[] = str_split($line);
    }
  }
}
$maphei = sizeof($map);
$mapwid = sizeof($map[0]);
$moves = array_merge(...$moves);

// find robot
// find guard
for($i=0;$i<$maphei;$i++) {
  $j = array_search("@", $map[$i]);
  if($j) {
    $robx = $j;
    $roby = $i;
  }
}
print_map();

function movebox($x, $y, $dir) {
  global $map;
  switch ($dir) {
    case "<":
      if($map[$y][$x-1] == "#") {
        return 0;
      }
      if($map[$y][$x-1] == "O") {
        $tmp = movebox($x-1, $y, $dir);
        if($tmp == 1) {
          $map[$y][$x-2] = "O";
          $map[$y][$x-1] = ".";
        }
        return $tmp;
      } else {
        return 1;
      }
      break;
    case "v":
      if($map[$y+1][$x] == "#") {
        return 0;
      }
      if($map[$y+1][$x] == "O") {
        $tmp = movebox($x, $y+1, $dir);
        if($tmp == 1) {
          $map[$y+2][$x] = "O";
          $map[$y+1][$x] = ".";
        }
        return $tmp;
      } else {
        return 1;
      }
      break;
    case ">":
      if($map[$y][$x+1] == "#") {
        return 0;
      }
      if($map[$y][$x+1] == "O") {
        $tmp = movebox($x+1, $y, $dir);
        if($tmp == 1) {
          $map[$y][$x+2] = "O";
          $map[$y][$x+1] = ".";
        }
        return $tmp;
      } else {
        return 1;
      }
      break;
    case "^":
      if($map[$y-1][$x] == "#") {
        return 0;
      }
      if($map[$y-1][$x] == "O") {
        $tmp = movebox($x, $y-1, $dir);
        if($tmp == 1) {
          $map[$y-2][$x] = "O";
          $map[$y-1][$x] = ".";
        }
        return $tmp;
      } else {
        return 1;
      }
      break;
  }
}

// walk the robot
for($i=0;$i<sizeof($moves);$i++) {
  if(movebox($robx, $roby, $moves[$i])) {
    if($moves[$i] == "^") {
      if($map[$roby-1][$robx] != "#") {
        $map[$roby-1][$robx] = "@";
        $map[$roby][$robx] = ".";
        $roby--;
      }
    }
    if($moves[$i] == ">") {
      if($map[$roby][$robx+1] != "#") {
        $map[$roby][$robx+1] = "@";
        $map[$roby][$robx] = ".";
        $robx++;
      }
    }
    if($moves[$i] == "v") {
      if($map[$roby+1][$robx] != "#") {
        $map[$roby+1][$robx] = "@";
        $map[$roby][$robx] = ".";
        $roby++;
      }
    }
    if($moves[$i] == "<") {
      if($map[$roby][$robx-1] != "#") {
        $map[$roby][$robx-1] = "@";
        $map[$roby][$robx] = ".";
        $robx--;
      }
    }
  }
}

print_map();

// calculate gps
$gps = 0;
for($j=0;$j<$maphei;$j++) {
  for($i=0;$i<$mapwid;$i++) {
    if($map[$j][$i] == "O") {
      $gps += 100 * $j + $i;
    }
  }
}
echo "$gps\n";

?>

Part 2:

<?php
// map in
function print_map() {
  global $map, $mapwid, $maphei;
  for($j=0;$j<$maphei;$j++) {
    for($i=0;$i<$mapwid;$i++) {
      if(isset($map[$j][$j])) {
        echo $map[$j][$i];
      } else {
        echo ".";
      }
    }
    echo "\n";
  }
  echo "\n";
}


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

$map = array();
$phase = 1;
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line) < 3) {
    $phase = 2;
  } else {
    if($phase == 1) {
      $map[] = str_split($line);
    } else {
      $moves[] = str_split($line);
    }
  }
}

// make map twice the width
foreach($map as $row) {
  foreach($row as $cell) {
    switch($cell) {
      case "#":
        $r2[] = $cell;
        $r2[] = $cell;
        break;
      case "@":
        $r2[] = $cell;
        $r2[] = ".";
        break;
      case "O":
        $r2[] = "[";
        $r2[] = "]";
        break;
      case ".":
        $r2[] = $cell;
        $r2[] = $cell;
        break;
    }
  }
  $m2[] = $r2;
  $r2 = array();
}
$map = $m2;

$maphei = sizeof($map);
$mapwid = sizeof($map[0]);
$moves = array_merge(...$moves);

// find robot
for($i=0;$i<$maphei;$i++) {
  $j = array_search("@", $map[$i]);
  if($j) {
    //print("$i $j");
    $robx = $j;
    $roby = $i;
  }
}
print_map();

function moveboxupdown($x, $y, $dir, $mywid) {

  global $map;
  // i am on (x,y) and i am mywid wide, going in dir direction
  // if there is a box in front of me, move it, if possible
  // note, adjacent boxes may be moved partially and then rolled back
  // if i am a box, (x,y) is my left part
  
  // first, check for wall
  if($dir == "^" && $map[$y-1][$x] == "#") {
    // wall, abort
    return 0;
  }
  if($dir == "^" && $mywid == 2 && $map[$y-1][$x+1] == "#") {
    // wall, abort
    return 0;
  }
  if($dir == "v" && $map[$y+1][$x] == "#") {
    // wall, abort
    return 0;
  }
  if($dir == "v" && $mywid == 2 && $map[$y+1][$x+1] == "#") {
    // wall, abort
    return 0;
  }

  // next check for further boxes, and move them!
  if($dir == "^" && $map[$y-1][$x-1] == "[") {
    $tmp = moveboxupdown($x-1, $y-1, $dir, 2);
    if($tmp == 0) {
      return 0;
    }
  }
  if($dir == "^" && $map[$y-1][$x] == "[") {
    $tmp = moveboxupdown($x, $y-1, $dir, 2);
    if($tmp == 0) {
      return 0;
    }
  }
  if($dir == "^" && $mywid == 2 && $map[$y-1][$x+1] == "[") {
    $tmp = moveboxupdown($x+1, $y-1, $dir, 2);
    if($tmp == 0) {
      return 0;
    }
  }
  if($dir == "v" && $map[$y+1][$x-1] == "[") {
    $tmp = moveboxupdown($x-1, $y+1, $dir, 2);
    if($tmp == 0) {
      return 0;
    }
  }
  if($dir == "v" && $map[$y+1][$x] == "[") {
    $tmp = moveboxupdown($x, $y+1, $dir, 2);
    if($tmp == 0) {
      return 0;
    }
  }
  if($dir == "v" && $mywid == 2 && $map[$y+1][$x+1] == "[") {
    $tmp = moveboxupdown($x+1, $y+1, $dir, 2);
    if($tmp == 0) {
      return 0;
    }
  }
  
  // if i reached this point, i can move a box
  if($dir == "^" && $mywid == 2) {
    $map[$y-1][$x] = "[";
    $map[$y-1][$x+1] = "]";
    $map[$y][$x] = ".";
    $map[$y][$x+1] = ".";
  }
  if($dir == "v" && $mywid == 2) {
    $map[$y+1][$x] = "[";
    $map[$y+1][$x+1] = "]";
    $map[$y][$x] = ".";
    $map[$y][$x+1] = ".";
  }

  return 1;
}

function moveboxleftright($x, $y, $dir) {
  global $map;
  switch ($dir) {
    case "<":
      if($map[$y][$x-1] == "#") {
        return 0;
      }
      if($map[$y][$x-1] == "]") {
        $tmp = moveboxleftright($x-2, $y, $dir);
        if($tmp == 1) {
          $map[$y][$x-3] = "[";
          $map[$y][$x-2] = "]";
          $map[$y][$x-1] = ".";
        }
        return $tmp;
      } else {
        return 1;
      }
      break;
    case ">":
      if($map[$y][$x+1] == "#") {
        return 0;
      }
      if($map[$y][$x+1] == "[") {
        $tmp = movebox($x+2, $y, $dir);
        if($tmp == 1) {
          $map[$y][$x+3] = "]";
          $map[$y][$x+2] = "[";
          $map[$y][$x+1] = ".";
        }
        return $tmp;
      } else {
        return 1;
      }
      break;
  }
}

function movebox($x, $y, $dir) {
  global $map;
  $backup = $map;
  if($dir == "^" || $dir == "v") {
    $tmp = moveboxupdown($x, $y, $dir, 1);
  } else {
    $tmp = moveboxleftright($x, $y, $dir);
  }
  if($tmp == 0) {
    $map = $backup;
  }
  return $tmp;
}

// walk the robot
for($i=0;$i<sizeof($moves);$i++) {
  if(movebox($robx, $roby, $moves[$i])) {
    if($moves[$i] == "^") {
      if($map[$roby-1][$robx] != "#") {
        $map[$roby-1][$robx] = "@";
        $map[$roby][$robx] = ".";
        $roby--;
      }
    }
    if($moves[$i] == ">") {
      if($map[$roby][$robx+1] != "#") {
        $map[$roby][$robx+1] = "@";
        $map[$roby][$robx] = ".";
        $robx++;
      }
    }
    if($moves[$i] == "v") {
      if($map[$roby+1][$robx] != "#") {
        $map[$roby+1][$robx] = "@";
        $map[$roby][$robx] = ".";
        $roby++;
      }
    }
    if($moves[$i] == "<") {
      if($map[$roby][$robx-1] != "#") {
        $map[$roby][$robx-1] = "@";
        $map[$roby][$robx] = ".";
        $robx--;
      }
    }
  }
}

print_map();

// calculate gps
$gps = 0;
for($j=0;$j<$maphei;$j++) {
  for($i=0;$i<$mapwid;$i++) {
    if($map[$j][$i] == "[") {
      $gps += 100 * $j + $i;
    }
  }
}
echo "$gps\n";
?>

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

We’re looking for a 2 digit number, ab (and the product ab * ba). It can’t be a 1 digit number, a, because a * a wouldn’t have 3 digits. It can’t be a 3 digit number, abc, because abc * cba would have at least 5 digits.

Also, ab is a square. It could be 16, 25, 36, 49, 64, 81. Going through these manually shows 16 * 61 = 976 is the only 3 digit number.

This week the question is: Can You Survive Squid Game (Season 2)?

In Season 2 of Squid Game, contestants play a game of “Mingle” (spoiler alert!). For each round of this game, the contestants all wait in a common area until a number is called. They must then split up into groups of that number. Any contestants not in a group of the correct number after 30 seconds … well, let’s just say bad things happen to them. For now, we’ll refer to contestants who make it through a round in a group of the correct size as having “survived” the round.

Suppose there are initially N contestants.

In the first round, contestants must form groups of 1. Okay, that’s not too hard; everyone survives. In the second round, contestants must form groups of 2. This continues (with groups of k in round k) until the 38th round, when contestants must form groups of 38.

What is the smallest number N such that there is at least one person who survives all 38 rounds?

And for extra credit:

There are N contestants about to play Mingle, where N is less than 500. This time, in each round, the number for group size can be anywhere from 1 to 10, with each number equally likely to be called. Also, the numbers called in the rounds are all independent of each other. It appears this version of Mingle will continue until there are no more survivors.

Before the game starts, one of the contestants, Young-il, does some quick computation. He says to his companion, Gi-hun: “Oh no, it’s too bad we only have N people.” (Of course, Young-il doesn’t actually say “N,” but rather the number that N represents.)

Young-il continues: “If we had started with N+1 people instead, I’d expect the game to last about 10 more rounds, on average.”

What is the value of N?

Highlight to reveal (possibly incorrect) solution:

Program. A little messy.

If we begin with N persons, before round 1, of course, after round 1 there will be f(1) = N persons. After round 2, we need to take N, divide by 2 to get the number of groups, round down to nearest integer if necessary, and then multiply by 2. f(2) = ⌊ f(1)/2 ⌋ * 2. And it goes on like this: f(3) = ⌊ f(2)/3 ⌋ * 3. In general, after round M we have f(M) = ⌊ f(M-1)/M ⌋ * M.

I wrote a program to calculate f(38), given an N. Some trial and error showed, that given N = 500, f(38) > 0. I then rewrote the program to try all possible N from 1, and stop when f(38) was positive the first time. Solution: we were looking for N = 454.

Just for fun I wrote some more code. Going the opposite direction, we might say f(37) = ⌈ f(38)/37 ⌉ * 37. Basing a small algorithm on this, I got the same solution, but I wasn’t sure that wasn’t luck.

Part 2:

Program. Spreadsheet/PDF.

For this I wrote another program. This one really calls out for some Monte Carlo. Try all N from 1 to 500, simulate X executions, calculate the average length of an execution (how many rounds), run the program, export to csv, open in Libre Office Calc, make an extra column with the difference between lengths for this particular N and the one above, some conditional formatting to look for a difference close to 10, and bam! Just to make sure, I looked a little closer at this neighborhood, and it just became clearer, that I was looking in the right place (see PDF above). The solution is N = 359.

I have a suspicion, this is because 360 is such a nice number. Coming from 361, 362, 363 etc., there’s a good chance of landing here. And then only moving on to a lower number, if the random number is 7.

This December I participated in Advent of Code.

Part 1 is rather easy. Let the robots walk.

Part 2 proved much more challenging. How does one detect a picture? I developed a strategy of trying to sense, whether the robots were “clumping”, and then printing the map, to get a visual check. This worked, and I found the picture. Then a little while later I discovered, that the apparently random output from part 1 could be used to detect the picture, but I didn’t implement that fully. Still, I really liked that elegant solution. This version of the program was actually built partially after I know the solution.

I’m getting a bit more systematic. Having all the values, that change between test and actual data at the top.

Part 1:

<?php
$input = file_get_contents('./d14input2.txt', true);
$mapwid = 101;
$maphei = 103;
// test: 11 x 7
// actual: 101 x 103
$robots = array();
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
	if(strlen($line)>2) {
		preg_match_all('/-?\d+/', $line, $robot);
		$robots[] = $robot[0];
	}
}
function print_map() {
	global $robots, $mapwid, $maphei;
	$map = array();
	foreach($robots as $robot) {
		$x = $robot[0];
		$y = $robot[1];
		if(isset($map[$x][$y])) {
			$map[$x][$y]++;
		} else {
			$map[$x][$y] = 1;
		}
	}
	for($j=0;$j<$maphei;$j++) {
		for($i=0;$i<$mapwid;$i++) {
			if(isset($map[$i][$j])) {
				echo $map[$i][$j];
			} else {
				echo ".";
			}
		}
		echo "\n";
	}
	echo "\n";
}
for($i=0;$i<100;$i++) {
// print("$i seconds elapsed\n");
  for($j=0;$j<sizeof($robots);$j++) {
    $robots[$j][0] =
      ($robots[$j][0] + $robots[$j][2] + $mapwid) % $mapwid;
    $robots[$j][1] =
      ($robots[$j][1] + $robots[$j][3] + $maphei) % $maphei;
  }
}
$robx0y0 = 0;
$robx0y1 = 0;
$robx1y0 = 0;
$robx1y1 = 0;
for($j=0;$j<sizeof($robots);$j++) {
	if($robots[$j][0] < ($mapwid-1)/2) {
		if($robots[$j][1] < ($maphei-1)/2) {
			$robx0y0++;
		} else {
			if($robots[$j][1] > ($maphei-1)/2) {
				$robx0y1++;
			}
		}
	} else {
		if($robots[$j][0] > ($mapwid-1)/2) {
			if($robots[$j][1] < ($maphei-1)/2) {
				$robx1y0++;
			} else {
				if($robots[$j][1] > ($maphei-1)/2) {
					$robx1y1++;
				}
			}
		}
	}
}
print("$robx0y0 $robx0y1 $robx1y0 $robx1y1\n");
$prod = $robx0y0 * $robx0y1 * $robx1y0 * $robx1y1;
print("$prod\n");
?>

Part 2:

<?php
$input = file_get_contents('./d14input2.txt', true);
$mapwid = 101;
$maphei = 103;
// test: 11 x 7
// actual: 101 x 103
$robots = array();
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>2) {
    preg_match_all('/-?\d+/', $line, $robot);
    $robots[] = $robot[0];
  }
}
//print_r($robots);
function print_map() {
  global $robots, $mapwid, $maphei;
  $map = array();
  foreach($robots as $robot) {
    $x = $robot[0];
    $y = $robot[1];
    if(isset($map[$x][$y])) {
      $map[$x][$y]++;
    } else {
      $map[$x][$y] = 1;
    }
  }
  for($j=0;$j<$maphei;$j++) {
    for($i=0;$i<$mapwid;$i++) {
      if(isset($map[$i][$j])) {
        echo $map[$i][$j];
      } else {
        echo ".";
      }
    }
    echo "\n";
  }
  echo "\n";
}
function xmas_tst() {
  global $robots, $mapwid, $maphei;
  $robx0y0 = 0;
  $robx0y1 = 0;
  $robx1y0 = 0;
  $robx1y1 = 0;
  for($j=0;$j<sizeof($robots);$j++) {
    if($robots[$j][0] < ($mapwid-1)/2) {
      if($robots[$j][1] < ($maphei-1)/2) {
        $robx0y0++;
      } else {
        if($robots[$j][1] > ($maphei-1)/2) {
          $robx0y1++;
        }
      }
    } else {
      if($robots[$j][0] > ($mapwid-1)/2) {
        if($robots[$j][1] < ($maphei-1)/2) {
          $robx1y0++;
        } else {
          if($robots[$j][1] > ($maphei-1)/2) {
            $robx1y1++;
          }
        }
      }
    }
  }
  if(max($robx0y0,$robx0y1,$robx1y0,$robx1y1) > 150) {
    return 1;
  } else {
    return 0;
  }
}
$handle = fopen ("php://stdin","r");
for($i=0;$i<8258;$i++) {
  for($j=0;$j<sizeof($robots);$j++) {
    $robots[$j][0] =
      ($robots[$j][0] + $robots[$j][2] + $mapwid) % $mapwid;
    $robots[$j][1] =
      ($robots[$j][1] + $robots[$j][3] + $maphei) % $maphei;
  }
  if(xmas_tst()) {
    print_map();
    print($i+1 . " seconds elapsed\n");
    $line = fgets($handle);
  }
}
fclose($handle);
?>