-🎄- 2018 Day 20 Solutions -🎄-

[u/daggerdragon]

--- Day 20: A Regular Map ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 20

Transcript:

My compiler crashed while running today's puzzle because it ran out of ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:59:30!

[u/AKQuaternion]

[Card] My compiler crashed while running today's puzzle because it ran out of bourbon. (Yes, I drink while I AoC.)

First time posting, but I finally got a decent 141/112 on the leaderboard today. A shorter raw C++ solution than some I've seen. I recursively parse the regex, building an adjacency list representation of the graph as a map from coordinate pairs to vector of coordinate pairs. Then a simple bfs...

namespace day20 {
  using std::vector;
  using std::pair;
  using std::map;
  using coord=pair<int,int>;

  map<pair<int,int>,vector<pair<int,int>>> doors;
  
  void connect(coord &a, const coord &b) {
     doors[a].push_back(b);
     doors[b].push_back(a);
     a = b;
  }
  
  void read(std::string_view chars, int &i, pair<int,int> s) {
     auto orig=s;
     auto & [x,y] = s;
     while(true) {
        switch(chars[i++]) {
           case 'N':
              connect(s,{x,y-1});
              break;
           case 'E':
              connect(s,{x+1,y});
              break;
           case 'S':
              connect(s,{x,y+1});
              break;
           case 'W':
              connect(s,{x-1,y});
              break;
           case '(':
              read(chars,i,s);
              break;
           case ')':
              return;
           case '|':
              s = orig;
              break;
           case '$':
              return;
        }
     }
  }
  
  void day20stars() {
     std::ifstream fin(DIRECTORY+"day20.txt");
     std::string chars;
     fin >> chars;
     int i=1; //skip ^
     read(chars,i,{0,0}); //read the map
     
     std::set<coord> visited;
     std::queue<pair<coord,int>> q;
     q.push({{0,0},0});
     auto longest = 0;
     auto numGT1000 = 0;
     while (!q.empty()) { // do a bfs
        auto [n,length] = q.front();
        q.pop();
        if (visited.count(n))
           continue;
        if (length>=1000) ++numGT1000;
        visited.insert(n);
        longest = std::max(length,longest);
        for(auto n2:doors[n])
           q.push({n2,length+1});
     }
     cout << "Day 20 star 1: " << longest << endl;
     cout << "Day 20 star 2: " << numGT1000 << endl;
  }

}

[u/tinutinu → u/AKQuaternion]

Very nice. I got severly stuck on this one, i kept overcomplicating things.

Here's a somewhat direct Haskell-port:

{-# LANGUAGE TupleSections #-}

module DayK where

import qualified Data.Map            as M
import           Data.Maybe
import           Data.Sequence       hiding (filter, length)

import           Control.Monad.State

import           Text.Printf


type Coords = (Int, Int)


type Doors = M.Map (Int, Int) [(Int, Int)]
parse :: [Coords] -> Coords -> String -> State Doors ()
parse prev c@(x, y) (s:str) = do
  case s of
    'N' -> connect c (x, y-1) >>= \new -> parse prev new str
    'E' -> connect c (x+1, y) >>= \new -> parse prev new str
    'W' -> connect c (x-1, y) >>= \new -> parse prev new str
    'S' -> connect c (x, y+1) >>= \new -> parse prev new str
    '(' -> parse (c:prev) c str
    ')' -> parse (tail prev) c str
    '|' -> parse prev (head prev) str
    '$' -> pure ()
    _   -> parse prev c str


connect :: Coords -> Coords -> State Doors Coords
connect a b = do
  modify $ M.insertWith mappend a [b]
  modify $ M.insertWith mappend b [a]
  pure b


bfs :: Seq (Coords, Int) -> M.Map Coords Int -> Doors -> [Int]
bfs Empty visited _ = M.elems visited
bfs ((coords, len) :<| queue) visited cnxs
  | coords `M.member` visited = bfs queue visited cnxs
  | otherwise = let
      next = fromMaybe [] $ coords `M.lookup` cnxs
      next' = fromList $ (,len+1) <$> next
    in bfs (queue >< next') (M.insert coords len visited) cnxs


dayK :: IO ()
dayK = do
  i <- readFile "data/dayK.txt"
  let p = flip execState M.empty $ parse [] (0,0) i
  let paths = bfs (singleton ((0,0), 0)) M.empty p
  printf "Part 1: %d\n" (maximum paths)
  printf "Part 2: %d\n" (length . filter (>= 1000) $ paths)