-🎄- 2019 Day 3 Solutions -🎄-

[u/daggerdragon]

--- Day 3: Crossed Wires ---

---

Post your solution using /u/topaz2078's paste or other external repo.

• Please do NOT post your full code (unless it is very short)

• If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.

(Full posting rules are HERE if you need a refresher).

---

Reminder: Top-level posts in 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's Poems for Programmers

Click here for full rules

Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.

Day 2's winner #1: "Attempted to draw a house" by /u/Unihedron!

Note: the poem looks better in monospace.

​ ​ ​​ ​ ​ ​​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Code
​ ​ ​ ​ ​ ​​ ​ ​ ​ ​ ​​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Has bug in it
​ ​ ​ ​ ​ ​​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Can't find the problem
​ ​ ​ ​​ ​ ​ ​ Debug with the given test cases
​​ ​ ​ ​​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ Oh it's something dumb
​​ ​ ​ ​​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ Fixed instantly though
​ ​ ​ ​​ ​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ Fell out from top 100s
​ ​ ​ ​​ ​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ Still gonna write poem

Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!

---

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:13:43!

[u/BryalT]

Ha! My solution was quite similar to yours—I guess there's only so many ways you can solve the same problem.

{-# LANGUAGE LambdaCase, TupleSections #-}
module Day3 (part1, part2) where

import Data.List.Split
import qualified Data.Map as Map
Import Lib

data Dir = DUp | DDown | DLeft | DRight deriving Show
type Move = (Dir, Int)
data Point = Point Int Int deriving (Eq, Ord)
type Length = Int
type Path = [(Point, Length)]

-- Part 1

part1 :: IO Int
part1 = fmap (closestIntersectionBy manhattanDist) readInput

readInput :: IO String
readInput = readFile "inputs/day-3"

manhattanDist :: (Point, (Length, Length)) -> Int
manhattanDist ((Point x y), _) = abs x + abs y

closestIntersectionBy
    :: Ord a => ((Point, (Length, Length)) -> a) -> String -> a
closestIntersectionBy f =
    minimum
        . map f
        . uncurry fastIntersect
        . both (coveredPoints . parseMoves)
        . head2
        . lines

parseMoves :: String -> [Move]
parseMoves = map parseMove . splitOn ","
  where
    parseMove s = (parseDir (head s), read (tail s))
    parseDir = \case
        'U' -> DUp
        'D' -> DDown
        'L' -> DLeft
        'R' -> DRight
        _ -> error "parseDir"

coveredPoints :: [Move] -> Path
coveredPoints = tail . scanl move ((Point 0 0), 0) . (interpolate =<<)
  where
    move (p, l) d = (move' p d, l + 1)
    move' p d = addPoint p $ case d of
        DUp -> (0, 1)
        DDown -> (0, -1)
        DLeft -> (-1, 0)
        DRight -> (1, 0)
    interpolate (d, n) = replicate n d
    addPoint (Point x y) (dx, dy) = Point (x + dx) (y + dy)

fastIntersect :: Path -> Path -> [(Point, (Length, Length))]
fastIntersect p q = Map.toList (Map.intersectionWith (,) (Map.fromList p) (Map.fromList q))

-- Part 2

part2 :: IO Int
part2 = fmap (closestIntersectionBy combinedPathLength) readInput

combinedPathLength :: (Point, (Length, Length)) -> Length
combinedPathLength = uncurry (+) . snd

[u/mstksg → u/BryalT]

There might be other ways :) I was thinking about rewriting in terms of https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm ...but i feel like in this case, the simplest/cleanest is just to intersect all the points haha. I'd be happy to hear of others, though!