Advent of Code: Day 8 Haunted Wasteland (incomplete Pt2)

Day 8: Haunted Wasteland
link to challenge

I found Part 1 straightforward, however Part 2, I had a brute force attempt, however, it was taking so long to complete, that it would time out.

I was unable to solve Part 2 for this reason (even though my code passed the for smaller volume sample text for this section). I’m not hugely mathematically inclined , however those that are may be able to build upon my solution for Part 1 and implement a more algorithmic solution for Part 2.

Below is my code solution for Part 1:

Solution - Part 1

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
  static void Main()
  {
    SolvePuzzle("puzzle.txt");
  }

  static void SolvePuzzle(string filePath)
  {
    var lines = File.ReadAllLines(filePath);

    char[] instructions = lines[0].ToCharArray();
    var nodes = lines.Skip(2).Select(NextStep.Parse).ToList();

    Dictionary<string, NextStep> mappings = nodes.ToDictionary(node => node.Key, node => node.Step);

    string key = "AAA"; // defined starting point.
    long currentIndex = 0;
    long stepsTaken = 0;

    while (key != "ZZZ")
    {
      key = instructions[currentIndex] == 'L' ? mappings[key].Left : mappings[key].Right;
      stepsTaken++;
      currentIndex = (currentIndex + 1) % instructions.Length;
    }

    Console.WriteLine(stepsTaken);
  }

  public record NextStep(string Left, string Right)
  {
    private static readonly Regex regex = new Regex(@"(?<key>\w{3}) = \((?<left>\w{3}), (?<right>\w{3})\)");

    public static (string Key, NextStep Step) Parse(string line)
    {
      Match match = regex.Match(line);

      var key = match.Groups["key"].Value;
      var left = match.Groups["left"].Value;
      var right = match.Groups["right"].Value;

      return (key, new NextStep(left, right));
    }
  }
}

Hopefully the code is simple to understand. But the main concepts are:

Read all the lines from the input file, and map these to a Tuple of string, NextStep, creating a Dictionary from these tuples. Storing the key for lookup, along with the Left and Right keys for further lookups.
We know the starting point needed to be AAA and the endpoint was ZZZ so can create a while loop which will continue to execute the inner code until that condition is met.
Inner code - work out if the Left or Right value needs to be used as the next map key, based on whether the current instruction is 'L' or 'R', as we map through them.
Increase steps taken so can keep track of how many steps were used before getting to ZZZ.
Update the current index using the modulus operator, so that it, in essence, continues to go around and around if we run out of instructions and the while condition isn't met.

Finish - Solved the Part 1 of the challenge.

Part 2 - Incomplete Brute Force:

As I've said this works on the smaller sample of code, but on the larger puzzle input, a timeout occurs (using brute force).

Nevertheless, here's my code so far for Part 2:


 static void Part2(string filePath)
  {
    var lines = File.ReadAllLines(filePath);
    char[] instructions = lines[0].ToCharArray();
    var nodes = lines.Skip(2).Select(NextStep.Parse).ToList();
    Dictionary<string, NextStep> mappings = nodes.ToDictionary(node => node.Key, node => node.Step);

    string[] currentPoints = mappings
          .Where(p => p.Key.EndsWith('A'))
          .Select(x => x.Key)
          .ToArray();

    long currentIndex = 0;
    long stepsTaken = 0;
    while (!currentPoints.All(x => x.EndsWith('Z')))
    {
      for (int i = 0; i < currentPoints.Length; i++)
      {
        currentPoints[i] = instructions[currentIndex] == 'L' ? mappings[currentPoints[i]].Left : mappings[currentPoints[i]].Right;

      }
      stepsTaken++;
      currentIndex = (currentIndex + 1) % instructions.Length;

    }

    Console.WriteLine(stepsTaken);
  }

Blog

Advent of Code: Day 8 Haunted Wasteland (incomplete Pt2)

Grant Riordan

Solution - Part 1

Part 2 - Incomplete Brute Force:

Join Our Newsletter. No Spam, Only the good stuff.

Related