This December I participated in Advent of Code.

This one had me thinking.

• In part 1, I need to create program copies of areas defined by their common letter. For this I create a list of the letters represented, make a copy of the map for each letter, and throw away all but one letter from each map.
• But then I have to test, whether each area is actually connected or there are 2 (or more) areas with the same letter, so my program copy has to be split up. For this I use a little recursion, because a split area may need to be split some more. Also, I think I finally became friends with global variables! And side effects, oh yeah… But, I have a function starting in a random place, marking all the places it can reach in the map, and then it’s easy to ask, was the whole map converted?
• Next, I have to figure out the size (easy) and periphery (hard) of each map. For the periphery I visit all the parts of the map. If this part of the map is in the area, and a neighboring part isn’t, we’ve found a part of the periphery.
• For part 2, I additionally test, whether someone before me already registered this part of the periphery.

Part 1:

<?php
$input = file_get_contents('./d12input1.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>2) {
    $map[] = str_split($line);
  }
}
$mapx = sizeof($map);
$mapy = sizeof($map[0]);
// name possible areas
$names = array();
for($i=0;$i<sizeof($map);$i++) {
  for($j=0;$j<sizeof($map[$i]);$j++) {
    $names[$map[$i][$j]] = 1;
  }
}
// convert names
$names2 = array();
foreach($names as $key => $val) {
  $names2[] = $key;
}
$names = $names2;
// thin areas out
$areas = array();
for($k=0;$k<sizeof($names);$k++) {
  $lett = $names[$k];
  $tmp = $map;
  for($i=0;$i<$mapx;$i++) {
    for($j=0;$j<$mapy;$j++) {
      if($tmp[$i][$j] != $lett) {
        unset($tmp[$i][$j]);
      }
    }
  }
  $areas[$k] = $tmp;
}
function subtst($i, $j) {
  global $tmpb;
  //print_r($tmpb);
  if(isset($tmpb[$i-1][$j])) {
    if($tmpb[$i-1][$j] != "*") {
      $tmpb[$i-1][$j] = "*";
      subtst($i-1, $j);
    }
  }
  if(isset($tmpb[$i+1][$j])) {
    if($tmpb[$i+1][$j] != "*") {
      $tmpb[$i+1][$j] = "*";
      subtst($i+1, $j);
    }
  }
  if(isset($tmpb[$i][$j-1])) {
    if($tmpb[$i][$j-1] != "*") {
      $tmpb[$i][$j-1] = "*";
      subtst($i, $j-1);
    }
  }
  if(isset($tmpb[$i][$j+1])) {
    if($tmpb[$i][$j+1] != "*") {
      $tmpb[$i][$j+1] = "*";
      subtst($i, $j+1);
    }
  }
}
function atst() {
  global $tmp, $map, $tmpb, $key, $mapx, $mapy, $areas;
  // grab random beginning point
  $lett = "";
  for($i=0;$i<$mapx;$i++) {
    for($j=0;$j<$mapy;$j++) {
      if(isset($tmp[$i][$j])) {
        $lett = $tmp[$i][$j];
        $x = $i;
        $y = $j;
        break 2;
      }
    }
  }
  // can I reach all points from here?
  $tmpb = $tmp;
  $tmpb[$x][$y] = "*";
  subtst($x, $y);
  if(sizeof(array_count_values(array_merge(...$tmpb))) > 1) {
    $new1 = $tmpb;
    for($i=0;$i<$mapx;$i++) {
      for($j=0;$j<$mapy;$j++) {
        if(isset($new1[$i][$j])) {
          if($new1[$i][$j] == $lett) {
            unset($new1[$i][$j]);
          } else {
            $new1[$i][$j] = $lett;
          }
        }
      }
    }
    $new2 = $tmpb;
    for($i=0;$i<$mapx;$i++) {
      for($j=0;$j<$mapy;$j++) {
        if(isset($new2[$i][$j])) {
          if($new2[$i][$j] != $lett) {
            unset($new2[$i][$j]);
          }
        }
      }
    }
    $areas[$key] = $new1;
    $areas[] = $new2;
  }
}
// if areas aren't actually connected, split up
$areaz = 0;
while($areaz < sizeof($areas)) {
  $areaz = sizeof($areas);
  foreach($areas as $key => $area) {
    $tmp = $area;
    atst();
  }  
}
$sum = 0;
foreach($areas as $key => $area) {
  $sz1 = array_count_values(array_merge(...$area));
  $sz2 = array_pop($sz1);
  $per = 0;
  for($i=0;$i<$mapx;$i++) {
    for($j=0;$j<$mapy;$j++) {
      if(isset($area[$i][$j])) {
        if(!isset($area[$i-1][$j])) {
          $per++;
        }
        if(!isset($area[$i+1][$j])) {
          $per++;
        }
        if(!isset($area[$i][$j-1])) {
          $per++;
        }
        if(!isset($area[$i][$j+1])) {
          $per++;
        }
      }
    }
  }
  $sum += $sz2 * $per;
}  
print("$sum\n");
?>

Part 2:

<?php
$input = file_get_contents('./d12input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
  if(strlen($line)>2) {
    $map[] = str_split($line);
  }
}
$mapx = sizeof($map);
$mapy = sizeof($map[0]);
// name possible areas
$names = array();
for($i=0;$i<sizeof($map);$i++) {
  for($j=0;$j<sizeof($map[$i]);$j++) {
    $names[$map[$i][$j]] = 1;
  }
}
// convert names
$names2 = array();
foreach($names as $key => $val) {
  $names2[] = $key;
}
$names = $names2;
// thin areas out
$areas = array();
for($k=0;$k<sizeof($names);$k++) {
  $lett = $names[$k];
  $tmp = $map;
  for($i=0;$i<$mapx;$i++) {
    for($j=0;$j<$mapy;$j++) {
      if($tmp[$i][$j] != $lett) {
        unset($tmp[$i][$j]);
      }
    }
  }
  $areas[$k] = $tmp;
}
//print_r($areas);
function subtst($i, $j) {
  global $tmpb;
  if(isset($tmpb[$i-1][$j])) {
    if($tmpb[$i-1][$j] != "*") {
      $tmpb[$i-1][$j] = "*";
      subtst($i-1, $j);
    }
  }
  if(isset($tmpb[$i+1][$j])) {
    if($tmpb[$i+1][$j] != "*") {
      $tmpb[$i+1][$j] = "*";
      subtst($i+1, $j);
    }
  }
  if(isset($tmpb[$i][$j-1])) {
    if($tmpb[$i][$j-1] != "*") {
      $tmpb[$i][$j-1] = "*";
      subtst($i, $j-1);
    }
  }
  if(isset($tmpb[$i][$j+1])) {
    if($tmpb[$i][$j+1] != "*") {
      $tmpb[$i][$j+1] = "*";
      subtst($i, $j+1);
    }
  }
}
function atst() {
  global $tmp, $map, $tmpb, $key, $mapx, $mapy, $areas;
  // grab random beginning point
  $lett = "";
  for($i=0;$i<$mapx;$i++) {
    for($j=0;$j<$mapy;$j++) {
      if(isset($tmp[$i][$j])) {
        $lett = $tmp[$i][$j];
        $x = $i;
        $y = $j;
        break 2;
      }
    }
  }
  // can I reach all points from here?
  $tmpb = $tmp;
  $tmpb[$x][$y] = "*";
  subtst($x, $y);
  if(sizeof(array_count_values(array_merge(...$tmpb))) > 1) {
    //print("alert\n");
    $new1 = $tmpb;
    for($i=0;$i<$mapx;$i++) {
      for($j=0;$j<$mapy;$j++) {
        if(isset($new1[$i][$j])) {
          if($new1[$i][$j] == $lett) {
            unset($new1[$i][$j]);
          } else {
            $new1[$i][$j] = $lett;
          }
        }
      }
    }
    $new2 = $tmpb;
    for($i=0;$i<$mapx;$i++) {
      for($j=0;$j<$mapy;$j++) {
        if(isset($new2[$i][$j])) {
          if($new2[$i][$j] != $lett) {
            unset($new2[$i][$j]);
          }
        }
      }
    }
    $areas[$key] = $new1;
    $areas[] = $new2;
  }
}
// if areas aren't actually connected, split up
$areaz = 0;
while($areaz < sizeof($areas)) {
  $areaz = sizeof($areas);
  foreach($areas as $key => $area) {
    $tmp = $area;
    atst();
  }  
}
$sum = 0;
foreach($areas as $key => $area) {
  $sz1 = array_count_values(array_merge(...$area));
  $sz2 = array_pop($sz1);
  $per = 0;
  for($i=0;$i<$mapx;$i++) {
    for($j=0;$j<$mapy;$j++) {
      if(isset($area[$i][$j])) {
        // above
        if(!isset($area[$i-1][$j])) {
          // already counted?
          if(isset($area[$i][$j-1]) && !isset($area[$i-1][$j-1])) {
          } else {
            $per++;
          }
        }
        // below
        if(!isset($area[$i+1][$j])) {
          // already counted?
          if(isset($area[$i][$j-1]) && !isset($area[$i+1][$j-1])) {
          } else {
            $per++;
          }
        }
        // to the left
        if(!isset($area[$i][$j-1])) {
          // already counted?
          if(isset($area[$i-1][$j]) && !isset($area[$i-1][$j-1])) {
          } else {
            $per++;
          }
        }
        // to the right
        if(!isset($area[$i][$j+1])) {
          // already counted?
          if(isset($area[$i-1][$j]) && !isset($area[$i-1][$j+1])) {
          } else {
            $per++;
          }
        }
      }
    }
  }
  $sum += $sz2 * $per;
}  
print("$sum\n");
?>

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

Holly picks the 3-digit number abc. Then she removes either a, b or c to get a new 2-digit number. Adding these 2 numbers together gets 309. 309 is odd, therefore removing a digit from abc can’t preserve c as the last digit, as that would make the sum even. So we have:

309 = abc + ab

• c + b = 9 (can’t be 19)
• b + a = 10 or 0
• a = 3 or a + 1 = 3

If b + a = 0, a = 3 is impossible.

• c + b = 9
• b + a = 10
• a + 1 = 3

Therefore a = 2, b = 8, c = 1. So abc = 281.

This December I participated in Advent of Code.

This is a case of, part 1 can be brute forced, part 2 can’t. Part 1 is straightforward. Simply keep a list of the numbers from each step. In part 2 it matters, that the order doesn’t matter. If I may say so. Instead of keeping a list of the numbers, I keep a count. How many 0s, how many 1s etc. So e.g. in a step I say, I previously had x 0s, now I have x 1s. I previously had y 1s, now I have y 2024s. I previously had z 2024s, now I have z 20s and z 24s. Etc. Adding everything up, because there might be more than one source for the numbers in the next step.

I liked this one!

Part 1:

<?php

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

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

/*

    If the stone is engraved with the number 0, it is replaced by a stone engraved with the number 1.
    If the stone is engraved with a number that has an even number of digits, it is replaced by two stones. The left half of the digits are engraved on the new left stone, and the right half of the digits are engraved on the new right stone. (The new numbers don't keep extra leading zeroes: 1000 would become stones 10 and 0.)
    If none of the other rules apply, the stone is replaced by a new stone; the old stone's number multiplied by 2024 is engraved on the new stone.

*/

for($i=0;$i<25;$i++) { 
	for($j=0;$j<sizeof($num1);$j++) { 
		$num = $num1[$j];
		if($num == 0) {
			$num2[] = 1;
			continue;
		}
		$numl = strlen((string) $num);
		if($numl % 2 == 0) {
			$num2[] = (int) substr((string) $num, 0, $numl/2);
			$num2[] = (int) substr((string) $num, $numl/2, $numl/2);
			continue;
		}
		$num2[] = $num * 2024;
	} 
	$num1 = $num2;
	$num2 = array();
}

print(sizeof($num1)."\n");

?>

Part 2:

<?php

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

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

for($j=0;$j<sizeof($num1);$j++) {
	$num = $num1[$j];
	if(isset($num2[$num])) {
		$num2[$num]++;
	} else {
		$num2[$num] = 1;
	}
}
$num1 = $num2;
$num2 = array();

/*

    If the stone is engraved with the number 0, it is replaced by a stone engraved with the number 1.
    If the stone is engraved with a number that has an even number of digits, it is replaced by two stones. The left half of the digits are engraved on the new left stone, and the right half of the digits are engraved on the new right stone. (The new numbers don't keep extra leading zeroes: 1000 would become stones 10 and 0.)
    If none of the other rules apply, the stone is replaced by a new stone; the old stone's number multiplied by 2024 is engraved on the new stone.

*/

for($i=0;$i<75;$i++) { 
	foreach($num1 as $num => $nom) { 
		if($num == 0) {
			if(isset($num2[1])) {
				$num2[1] += $nom;
			} else {
				$num2[1] = $nom;
			}
			continue;
		}
		$numl = strlen((string) $num);
		if($numl % 2 == 0) {
			$numa = (int) substr((string) $num, 0, $numl/2);
			if(isset($num2[$numa])) {
				$num2[$numa] += $nom;
			} else {
				$num2[$numa] = $nom;
			}
			$numb = (int) substr((string) $num, $numl/2, $numl/2);
			if(isset($num2[$numb])) {
				$num2[$numb] += $nom;
			} else {
				$num2[$numb] = $nom;
			}
			continue;
		}
		$numc = $num * 2024;
		if(isset($num2[$numc])) {
			$num2[$numc] += $nom;
		} else {
			$num2[$numc] = $nom;
		}
	} 
	$num1 = $num2;
	$num2 = array();
}

print(array_sum($num1)."\n");

?>

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

Out of the 11 available integers, 5 is the 5th, with 4 integers before it and 6 after. A set of integers is well formed, if 5 is the middle integer, with n integers before it and n after.

n = 0, 1 way to do that.

n = 1, 4 choices in front, 6 choices after, 4*6 = 24 ways to do that.

n = 2, (4 c 2) choices in front, (6 c 2) choices after, (4 c 2) * (6 c 2) = 4*3/2 * 6*5/2 = 6*15 = 90 ways to do that.

n = 3, (4 c 3) choices in front, (6 c 3) choices after, (4 c 3) * (6 * 3) = 4 * 6*5*4/(3*2) = 4*20 = 80 ways to do that.

n = 4, 1 choice in front, (6 c 4) choices after, 6*5/2 = 15 ways to do that.

1+24+90+80+15 = 210.

This December I participated in Advent of Code.

Days 7-10 saw me really trying (most days) to get a good ranking. (A good ranking turned out to be “a 4 digit number”.) I would be ready when the new puzzle dropped, sitting at my PC. And I would get the programming done! This later flagged, when the puzzles got harder, and I had to spend time simply trying to figure out what coding to do. But in this period, it was very much possible to get a good ranking. (From day 16 and forward, I was trying to catch up. It was a struggle to get the program done within 24 hours, and I wanted to solve the puzzles in the right order.)

      --------Part 1--------   --------Part 2--------
Day       Time   Rank  Score       Time   Rank  Score
 25       >24h  22113      0       >24h  14148      0
 24       >24h  23368      0       >24h  15862      0
 23       >24h  23812      0       >24h  21472      0
 22       >24h  25204      0       >24h  21799      0
 21       >24h  19594      0       >24h  16355      0
 20       >24h  24815      0       >24h  21577      0
 19       >24h  28005      0       >24h  25333      0
 18       >24h  27991      0       >24h  27338      0
 17       >24h  28700      0       >24h  20591      0
 16       >24h  24090      0       >24h  25303      0
 15   01:19:07   5843      0   07:18:20   8861      0
 14   01:28:12   7258      0   02:13:42   6000      0
 13   03:04:50  11545      0   03:08:52   7714      0
 12   03:55:52  14298      0   04:04:26   7259      0
 11   00:24:58   6479      0   01:09:10   5330      0
 10   00:44:34   6515      0   00:48:19   6013      0
  9   01:26:25   9059      0   02:59:32   8039      0
  8   01:53:25  10087      0   02:04:40   9294      0
  7   17:55:39  47349      0   18:02:03  44377      0
  6   00:45:55   8375      0   02:18:28   8078      0
  5   13:07:46  55110      0   13:13:45  44839      0
  4   01:51:36  15622      0   02:06:52  13570      0
  3   16:51:27  91593      0   17:04:46  80436      0
  2   12:11:26  78108      0   13:30:49  60978      0
  1   17:12:43  92846      0   17:24:33  87414      0

Day 9 I had a question. The answer turned out to be: I had a check in part 1, that I lost when I restructured the code for part 2. Oops.

Day 7: wonderful recursion! Day 10: more wonderful recursion!

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

The candidate numbers all have 2 digits, ab. A palindrome number of this kind has a = b. So the palindrome numbers are 11, 22, …, 99.

11 + 22 + … + 99 =

(1+2+…+9)*11 =

9*5*11 =

495

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

Oh goody, time to use my fairly new cross sum skills.

Going left to right, top to bottom, name the boxes a-i.

• R2, C3 (*) = f is an integer dividing 9, therefore one of 1, 3, 9.
• R3, C3 = i, same argument, same result.
• Still R3, C3 = i: the result of a division, c/f, divided by i, is 3. If i = 1, c/f = 3, it’s one of 3/1, 6/2, 9/3. First would require duplication, throw it away. If i = 3, c/f = 9, that would be 9/1. If i = 9, c/f = 27, impossible. New result: one of 1, 3.
• R3, C1 = g is an integer dividing 12, therefore one of 2, 3, 4, 6. (Can’t be 1, that would require the subtraction above, a/d to be 12; can’t be 12, that’s not a digit.)
• R3, C2 = h has to combine with 2, 3, 4, 6 to the left and 1, 3 to the right. g/h*i = 9. g/h must be 3 or 9. 9 is impossible, so it must be 3. Therefore i = 3. Therefore g/h must be 6/2. (It can’t be 3/1 because of duplication.) So g = 6, h = 2.
• Going back to C3, c = 9, f = 1.
• R2, d + e = 9. Of the digits left, it must be 4 and 5.
• R1, a – b = -1. The last digits are 7 and 8. a = 7, b = 8.
• C1, (7-d)*6 = 12. d = 5, e = 4.

(*) Row 2, column 3.

The digits in the boxes are 7, 9 and 4. 7*9*4 = 252.

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

Official answer: “By adding a point inside a triangle, you can turn one triangle into three triangles. By adding a point outside all the current triangles, you can add either one or two more triangles. As we are after the maximum number of triangles, we will choose to add two triangles for each point we add. Four points make 3 triangles. Adding 286 more points will add 572 more triangles, giving a total of 575.”

I think, but I can’t quite prove, the construction of the most triangles possible goes like this:

1. Begin with 2 points and the line between them.
2. Add 2 points close to this and construct the 3 triangles possible.
3. Choose one of the outside lines of the figure.
4. Go back to #2 and repeat.

This means: 2 points, 0 triangles; 4 points, 3 triangles; 6 points, 6 triangles; … ; 2(n+1) points, 3n triangles.

290 = 2(n+1)

145 = n+1

144 = n

432 = 3n

The answer is 432.

This week the question is: Can You Squeeze the Sheets?

Two large planar sheets have parallel semicircular cylindrical ridges with radius 1. Neighboring ridges are separated by a distance L ≥ 2. The sheets are placed so that the ridges extrude toward each other, and so that the sheets cannot shift relative to each other in the horizontal direction, as shown in the cross-section below:

Which value of L (again, that’s the spacing between ridges) maximizes the empty space between the sheets?

To be clear, you are maximizing the volume of empty space per unit area of one flat sheet. In the cross-section shown above, that’s equivalent to maximizing the area of empty space per unit length of one flat sheet.

And for extra credit:

Instead of cylindrical ridges, now suppose the sheets have any number (greater than zero) of hemispherical deformations with radius 1 that extrude toward each other. This time, the sheets need not be the same as each other.

As before, the distance between the centers of any two deformations on the same sheet must be at least 2. What is the minimum empty space, again expressed as volume per unit area of one flat sheet?

Highlight to reveal (possibly incorrect) solution:

Video. Figure 1, 2, 3 and 4.

Construct (in the cross section of the 2 sheets) a triangle. 1 side is horizontal, 1 side vertical, and 1 side connects the centres of 2 neighboring ridges-semicircles.

The horizontal side is L/2. The hypotenuse is exactly 2. Therefore the vertical side is √(4 – L²/4). Let’s call that h for height.

Looking at a rectangle containing 2 of these triangles, its area (again, a cross section of the real 3d situation) is hL/2. Some of this area is taken up by circle parts; exactly π/2. The rest is empty: hL/2 – π/2. We want to normalize this, to correspond to a unit step in the horizontal direction. This gives (hL/2 – π/2)/(L/2). This function has a maximum for about L = 2.6581.

And for extra credit:

Figure 1, 2, 3 and 4.

Option a: This is the same solution as the optimal stacking of balls. In my figures there’s a triangle between the centres of the 3 blue hemispheres. The base of the triangle is 2, and the height is √3. Adding the centre of the red hemisphere, we get a tetrahedron. This has height 2√2/√3.

Looking at the volume with the 2 green triangles as the base, we have a complete red hemisphere (the bits chopped off have friends included elsewhere) and a complete blue hemisphere (2 x 1/3 and 2 x 1/6). The space taken up is π4/3, appr. 4.19. The complete space is 2*√3*2*√2/√3 = 4*√2, appr. 5.66. The empty space is appr. 1.45. The base of the volume is 2*√3, appr. 3.46. The empty volume pr. unit area is 1.45/3.46, appr. 0.42.

Calculations and animation.

Option b: Let L be the distance between 2 centres of hemispheres on a sheet. Vary L and find a minimum. Oh! That minimum occurs when L = 2, so we get the same solution, appr. 0.42.

Option c: Defies the my imagination.

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

The circle all around is 360°.

The angle to the minute hand, corresponding to 22 minutes is 360 * 22/60 = 132.

The angle to the hour hand, going clockwise, corresponding to 8 hours and 22 minutes is 360 * (8 + 22/60) / 12 = 251.

The angle between the hands is 251 – 132 = 119.