I give up the Advent of Code

Posted on December 19, 2022 @ 08:00

Posted under the General category

Posted with the following tags: #Personal

In the last days the Advent of Code went into Advanced of Code.

I give up the Advent of Code — Image by Arek Socha from Pixabay

Sad but true

In the last days (December 16 - 17) I was struggling to solve the tasks of the AoC. They seem to be more difficult than I can solve them with an average web developer knowledge.

Yes, they are only algorithms. Yes, I could figure out the 16th, and the 17th algorithm, and I also wrote it and solved the first part fluently. My solution proved that it works with the second task as well, but only on the example data.

Unfortunately my solutions were so hungry for resources, that they couldn’t deal with the part two of the puzzle with the real input.

Now I feel depressed and disappointed again. But this was the first time, I tried this challenge and I could solve more than the half of it. So in the end of the day, I still can be a bit proud of myself. Maybe, there would be some puzzles in the rest of the days that I could still solve, but this game should be done for fun and relaxation, and not to be nervous and depressed. I already sacrificed two full Saturdays in a row for this challenge, and that’s too much price.

So I think it’s really time to stop here and now. It’s Christmastime, and I must not prefer this coding game over my family.

I will spend the rest of the year with relaxation - hopefully.

The hints

Probably you could find much better solutions than my PHP codes. But hey, it’s the Worst Practice!

16th of December

This task truly fucked my brain through the North Korean border. I have never had to deal with graphs, maybe once on the university twenty-something years ago. So first I had to search the internet which way should I start. This is how I found the Floyd Warshall algorithm.

So I had to build up the graph, then make a distance graph for it, then walk the whole thing:

                
              
                class Valve 
{
    // ...
}

class Cave
{
    //...
    
    private function intiDistanceGraph(): void {
        sort($this->valveNames);
        $this->distanceGraph = array_fill_keys(
            $this->valveNames,
            array_fill_keys($this->valveNames, self::INFINITE)
        );

        $this->applyFloydWarshall();
    }

    private function applyFloydWarshall(): void
    {
        foreach ($this->valves as $name => $valve) {
            foreach ($valve->tunnels as $valveName) {
                $this->distanceGraph[$name][$valveName] = 1;
            }
        }

        foreach ($this->valves as $name1 => $valve1) {
            foreach ($this->valves as $name2 => $valve2) {
                foreach ($this->valves as $name3 => $valve3) {
                    $this->distanceGraph[$name2][$name3] = min(
                        $this->distanceGraph[$name2][$name3],
                        ($this->distanceGraph[$name2][$name1] + $this->distanceGraph[$name1][$name3])
                    );
                }
            }
        }
    }

    public function getHighestReleasablePressure(string $currentValveName = null, int $timeSpent = 0): int
    {
        if (count($this->valvesOpened) === count($this->valvesWithPressure)) {
            return 0;
        }

        if (!$currentValveName) {
            $currentValveName = $this->startPosition;
        }

        $currentValve = $this->valves[$currentValveName];
        $pressure = 0;

        foreach ($this->valvesWithPressure as $targetValveName => $targetValve) {
            if (isset($this->valvesOpened[$targetValveName])) {
                continue;
            }

            $newTimeSpent = $this->distanceGraph[$currentValve->name][$targetValveName] + $timeSpent + 1;

            if ($newTimeSpent < $this->timeLimit) {
                $this->valvesOpened[$targetValveName] = $targetValve;
                $currentReleasePressure = $targetValve->pressure * ($this->timeLimit - $newTimeSpent);
                $targetValveReleasePressure = $this->getHighestReleasablePressure($targetValveName, $newTimeSpent);

                unset($this->valvesOpened[$targetValveName]);

                $pressure = max($pressure, ($currentReleasePressure + $targetValveReleasePressure));
            }
        }

        return $pressure;
    }
}

              
            

        
      
  

Probably this is the least efficient way to solve this puzzle.

17th of December

The base concept of the puzzle is quite interesting. It’s a kind of low budget Tetris game. No turning, no line eliminations. I’m not a game developer, I don’t have any experience with long term, multi-steps game strategies, but I tried my best.

In the end it turned out, probably my best is the worst here, hehehe.

So the game is about falling shapes will pile up. The shapes can be imagined as two-dimensional arrays with zeros and ones. So we need to find a way to merge two arrays to not overlap the ones. OR, how about we represent them as a string and simply do some binary checks? They are zeros and ones for God’s sake!

This is the way I chose to go on. Yes, again: the theory is simple, the solution is not. It turned out to be extremely slow. Probably my code is wrong, and maybe the PHP is not the best platform for these task, I don’t know.

But here is what I made:

    
  
    $line = trim(file_get_contents(__DIR__.'/input.txt'));

$gasFlow = str_split($line);
$rocks = [
    0 => '0000000'.'0000000'.'0000000'.'0011110',
    1 => '0000000'.'0001000'.'0011100'.'0001000',
    2 => '0000000'.'0000100'.'0000100'.'0011100',
    3 => '0010000'.'0010000'.'0010000'.'0010000',
    4 => '0000000'.'0000000'.'0011000'.'0011000',
];

$areaWalls = '1'.'0000000'.'1'.'0000000'.'1'.'0000000'.'1'.'0000000'.'1';

$rocksFallen = 0;
$rockIndex = 0;
$gasFlowIndex = 0;

$emptyArea = array_fill(0, 4, '0000000');
$area = array_fill(0, 7, '0000000');
$actualAreaSlice = $emptyArea;
$actualAreaMask = implode('', $actualAreaSlice);
$totalArea = 0;

do {
    $actualRockMask = $rocks[$rockIndex];
    $actualRockSlice = str_split($actualRockMask, 7);
    $areaIndex = 0;
    $falling = true;

    // Check fall and slide until hit a rock or the ground
    while ($falling) {
        // Pick the next 4 rows
        $nextAreaSlice = array_slice($area, $areaIndex, 4);
        // Make a bitmask like the rocks
        $nextAreaMask = implode('', $nextAreaSlice);

        // If there's a hit with another rock, this step is invalid, quit
        if (bindec($actualRockMask & $nextAreaMask) > 0) {
            // We made sure to always have enough free space "above", so there won't be underflow with the index.
            $areaIndex--;
            break;
        }

        // Apply falling
        $actualAreaSlice = $nextAreaSlice;
        $actualAreaMask = $nextAreaMask;

        // We hit the ground but we can slide once more
        if ($areaIndex === count($area) - 4) {
            $falling = false;
        }

        // Make a bitmask like the area walls by adding placeholders
        $actualAreaMaskWithWalls = '0'. implode('0', $actualAreaSlice).'0';
        // By pre-adding the placeholders for the walls, we can make sure the bit shift won't cause overflow or make floating pont number
        $actualRockMaskWithWalls = '0'. implode('0', $actualRockSlice).'0';

        $nextMove = $gasFlow[$gasFlowIndex];

        if ($nextMove === '<') {
            // Check move left
            $actualRockMaskWithWalls = str_pad(decbin(bindec($actualRockMaskWithWalls) * 2), (28 + 5), '0', STR_PAD_LEFT);
            $multiply = 2;
        } else {
            // Check right
            $actualRockMaskWithWalls = str_pad(decbin(bindec($actualRockMaskWithWalls) / 2), (28 + 5), '0', STR_PAD_LEFT);
            $multiply = 0.5;
        }

        $freeSpaces = $areaWalls | $actualAreaMaskWithWalls;

        // If we don't hit the wall or any rock, we apply the bit shift on the original rock mask
        if (bindec($actualRockMaskWithWalls & $freeSpaces) === 0) {
            $actualRockMask =  str_pad(decbin(bindec($actualRockMask) * $multiply), 28, '0', STR_PAD_LEFT);
            $actualRockSlice = str_split($actualRockMask, 7);
        }

        // try falling and shifting again
        $areaIndex++;
        $gasFlowIndex++;

        if ($gasFlowIndex >= count($gasFlow)) {
            $gasFlowIndex = 0;
        }
    }

    // Make new mask
    $actualAreaAndRockMask = $actualAreaMask | $actualRockMask;
    // Create new slice
    $actualAreaAndRockSlice = str_split($actualAreaAndRockMask, 7);
    // Replace old slice with new
    array_splice($area, $areaIndex, 4, $actualAreaAndRockSlice);

    $rocksFallen++;
    $rockIndex++;

    if ($rockIndex >= 5) {
        $rockIndex = 0;
    }

    $emptyLinesInArea = array_filter($area, function ($row) {
        return $row === '0000000';
    });

    // Add new empty lines if needed
    if (count($emptyLinesInArea) < 7) {
        $num = 7 - count($emptyLinesInArea);
        for ($i = 0; $i < $num; $i++) {
            array_unshift($area,'0000000');
        }
    }
}
while ($rocksFallen < 2022);

$filledLinesInArea = array_filter($area, function ($row) {
    return $row !== '0000000';
});

echo count($filledLinesInArea).PHP_EOL;

  

As an idea, I think it was not that terrible, the solution definitely is. A true Worst Practice.