this post was submitted on 24 Dec 2024
13 points (100.0% liked)

Advent Of Code

920 readers
3 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
13
๐Ÿค– - 2024 DAY 24 SOLUTIONS - ๐Ÿค– (programming.dev)
submitted 1 week ago* (last edited 1 week ago) by [email protected] to c/[email protected]
16 comments fedilink hide all child comments
 

Day 24: Crossed Wires

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

you are viewing a single comment's thread
view the rest of the comments
[โ€“] LeixB 3 points 1 week ago

Haskell

For part2 I compared the bits in the solution of part1 with the sum of x and y. With that, I could check the bits that did not match in a graphviz diagram and work from there.

code

import Control.Arrow
import Control.Monad.RWS
import Data.Bits (shiftL)
import Data.Char (digitToInt)
import Data.Functor
import Data.List
import Data.Map qualified as M
import Data.Tuple
import Text.ParserCombinators.ReadP hiding (get)
import Text.ParserCombinators.ReadP qualified as ReadP

type Cable = String
data Connection = And Cable Cable | Or Cable Cable | Xor Cable Cable deriving (Show)

cable = count 3 ReadP.get
eol = char '\n'
initial :: ReadP (M.Map Cable Bool)
initial = M.fromList <$> endBy ((,) <$> cable <*> (string ": " *> (toEnum . digitToInt <$> ReadP.get))) eol
wires = M.fromList <$> endBy wire eol

wire = do
    a <- cable <* char ' '
    op <- choice [string "AND" $> And, string "OR" $> Or, string "XOR" $> Xor]
    b <- char ' ' *> cable
    c <- string " -> " *> cable
    return (c, op a b)

parse = fst . last . readP_to_S ((,) <$> initial <*> (eol *> wires <* eof))

type Problem = RWS (M.Map Cable Connection) () (M.Map Cable Bool)

getConnection :: Connection -> Problem Bool
getConnection (And a b) = (&&) <$> getWire a <*> getWire b
getConnection (Or a b) = (||) <$> getWire a <*> getWire b
getConnection (Xor a b) = xor <$> getWire a <*> getWire b

xor True False = True
xor False True = True
xor _ _ = False

getWire :: Cable -> Problem Bool
getWire cable = do
    let computed = do
            a <- asks (M.! cable) >>= getConnection
            modify (M.insert cable a)
            return a
    gets (M.!? cable) >>= maybe computed return

fromBin :: [Bool] -> Int
fromBin = sum . fmap fst . filter snd . zip (iterate (`shiftL` 1) 1)

toBin :: Int -> [Bool]
toBin = unfoldr (\v -> if v == 0 then Nothing else Just (first (== 1) (swap (divMod v 2))))

part1 initial wiring = fst $ evalRWS (mapM getWire zs) wiring initial
  where
    zs = filter ((== 'z') . head) . sort $ M.keys wiring

part2 initial wiring = fmap fst . filter snd $ zip [0..] (zipWith (/=) p1 expect)
  where
    xs = fromBin . fmap (initial M.!) . filter ((== 'x') . head) $ sort $ M.keys initial
    ys = fromBin . fmap (initial M.!) . filter ((== 'y') . head) $ sort $ M.keys initial
    zs = filter ((== 'z') . head) . sort $ M.keys wiring

    p1 = part1 initial wiring
    expect = toBin $ xs + ys

main = getContents >>= print . (fromBin . uncurry part1 &&& uncurry part2) . parse