Day 13: Point of Incidence

# Advent of Code 2023
# Day 13: Point of Incidence

def find_vertical_reflection(pattern, compare):
    for x in range(1, len(pattern[0])):
        left_side = [row[:x] for row in pattern]
        right_side = [list(reversed(row[x:])) for row in pattern]

        left_width = len(left_side[0])
        right_width = len(right_side[0])

        if left_width > right_width:
            difference = left_width - right_width
            left_side_adjusted = [row[difference:] for row in left_side]
            right_side_adjusted = right_side
        elif right_width > left_width:
            difference = right_width - left_width
            left_side_adjusted = left_side
            right_side_adjusted = [row[difference:] for row in right_side]
        else:
            left_side_adjusted = left_side
            right_side_adjusted = right_side

        if compare(left_side_adjusted, right_side_adjusted):
            return left_width

    return 0

def smudged_compare(left_side, right_side):
    left_side = [char for row in left_side for char in row]
    right_side = [char for row in right_side for char in row]

    return sum(
        left_side[i] != right_side[i] for i in range(len(left_side))
    ) == 1

notes_sum = 0
notes_sum_smudged = 0

with open("inputs/day_13.txt") as file:
    for pattern in file.read().split("\n\n"):
        pattern = [list(row.rstrip("\n")) for row in pattern.splitlines()]

        notes_sum += find_vertical_reflection(pattern, list.__eq__)
        notes_sum += find_vertical_reflection(
            [list(row) for row in list(zip(*pattern))[::-1]], list.__eq__
        ) * 100

        notes_sum_smudged += find_vertical_reflection(pattern, smudged_compare)
        notes_sum_smudged += find_vertical_reflection(
            [list(row) for row in list(zip(*pattern))[::-1]], smudged_compare
        ) * 100

print(f"Part 1: {notes_sum}")
print(f"Part 2: {notes_sum_smudged}")

I found it simplest to transpose the pattern and just a have a row-oriented algorithm. Using a row of strings as a data structure made part 1 really easy, and since the patterns are pretty small, feasible for part 2. The main trick for Part 2 is that it is just part 1 but with the cumulative number of differences bounded to 1 instead of exact equality.

<?php
$input = trim(file_get_contents($argv[1]));
$input = explode("\n\n", $input);

function solve1H(array $problem): int {
	for($i = 0; $i < count($problem) - 1; $i++){
		if (!isReflection($problem, $i)) {
			continue;
		}
		return $i;
	}

	return -1;
}

function isReflection(array $problem, int $point): bool {
	$upDistance = $point;
	$downDistance = count($problem) - 1 - 1 - $point;
	$maxDistance = min($upDistance, $downDistance);
	echo "start up $upDistance down $downDistance\n";
	$foundSmudge = true; // true for part 1
	for($i = 0; $i <= $maxDistance; $i++){
		$diff = lineDiff($problem[$point - $i], $problem[$point + 1 + $i]);
		echo "\trow " . ((string) $point-$i) . " vs row " . ((string) $point+1+$i) . " diff $diff smudge $foundSmudge\n";
		if (!$foundSmudge && $diff == 1) {
			$foundSmudge = true;
		}else if ($diff != 0) {
			return false;
		}
	}
	return $foundSmudge;
}

function lineDiff(string $a, string $b): int {
	$out = 0;
	for($i = 0; $i < strlen($a); $i++) {
		if($a[$i] != $b[$i]) {
			$out++;
		}
	}
	return $out;
}

function rotateCW(array $problem): array {
	$out = [];
	$height = count($problem) - 1;
	for($i = 0; $i < count($problem); $i++){
		for($j = 0; $j < strlen($problem[$i]); $j++){
			$out[$j][$height - $i] = $problem[$i][$j];
		}
	}
	for($i = 0; $i < count($out); $i++){
		// the array is still keyed, need to sort first...
		ksort($out[$i], SORT_NUMERIC);
		$out[$i] = implode("", $out[$i]);
	}
	return $out;
}

function printProblem(array $problem) {
	foreach($problem as $line){
		echo $line."\n";
	}
}

$accum = 0 ;
foreach($input as $i => $problem) {
	echo "problem $i\n";
	$lines = explode("\n", $problem);
	$reflection = solve1H($lines);

	if($reflection == -1){
		echo "\tchecking V\n";
		$rotated = rotateCW($lines);
		// printProblem($rotated);
		// it is a vertical line
		$reflection = solve1H($rotated);
		if ($reflection == -1) {
			throw new Error("no solution for problem $i");
		}
		echo "\treflection V $reflection\n";
		$accum += $reflection + 1;
	}else{
		echo "\treflection H $reflection\n";
		// it is a horizontal line
		$accum += ($reflection + 1) * 100;
	}
}

echo $accum . "\n";