diff options
Diffstat (limited to '2021')
57 files changed, 2822 insertions, 0 deletions
diff --git a/2021/.envrc b/2021/.envrc new file mode 100644 index 0000000..051d09d --- /dev/null +++ b/2021/.envrc @@ -0,0 +1 @@ +eval "$(lorri direnv)" diff --git a/2021/.gitignore b/2021/.gitignore new file mode 100644 index 0000000..889aef8 --- /dev/null +++ b/2021/.gitignore @@ -0,0 +1,57 @@ +inputs/ + +# Created by https://www.toptal.com/developers/gitignore/api/racket +# Edit at https://www.toptal.com/developers/gitignore?templates=racket + +### Racket ### +# gitignore template for the Racket language +# website: http://www.racket-lang.org/ + +# DrRacket autosave files +*.rkt~ +*.rkt.bak +\#*.rkt# +\#*.rkt#*# + +# Compiled racket bytecode +compiled/ +*.zo + +# Dependency tracking files +*.dep + +# End of https://www.toptal.com/developers/gitignore/api/racket + +*/input +*/input_test + + +# Created by https://www.toptal.com/developers/gitignore/api/haskell +# Edit at https://www.toptal.com/developers/gitignore?templates=haskell + +### Haskell ### +dist +dist-* +cabal-dev +*.o +*.hi +*.hie +*.chi +*.chs.h +*.dyn_o +*.dyn_hi +.hpc +.hsenv +.cabal-sandbox/ +cabal.sandbox.config +*.prof +*.aux +*.hp +*.eventlog +.stack-work/ +cabal.project.local +cabal.project.local~ +.HTF/ +.ghc.environment.* + +# End of https://www.toptal.com/developers/gitignore/api/haskell diff --git a/2021/day1/01a.rkt b/2021/day1/01a.rkt new file mode 100644 index 0000000..5f3ea26 --- /dev/null +++ b/2021/day1/01a.rkt @@ -0,0 +1,18 @@ +#lang racket +(require threading) + +(define input (file->lines "input")) + +(define (map-differing-lengths f . arrs) + (define minLength (apply min (map length arrs))) + (define newLists (map (lambda (x) (take x minLength)) arrs)) + (apply map (cons f newLists))) + +(define (diff-pairs xs) + (map-differing-lengths - (cdr xs) xs)) + +(~>> input + (map string->number) + (diff-pairs) + (filter positive?) + (length _)) diff --git a/2021/day1/01b.rkt b/2021/day1/01b.rkt new file mode 100644 index 0000000..40337a4 --- /dev/null +++ b/2021/day1/01b.rkt @@ -0,0 +1,23 @@ +#lang racket +(require threading) + +(define input (file->lines "input")) + +(define (map-differing-lengths f . arrs) + (define minLength (apply min (map length arrs))) + (define newLists (map (lambda (x) (take x minLength)) arrs)) + (apply map (cons f newLists))) + +(define (build-windows xs) + (map-differing-lengths list xs (cdr xs) (drop xs 2))) + +(define (diff-pairs xs) + (map-differing-lengths - (cdr xs) xs)) + +(~>> input + (map string->number) + (build-windows) + (map (lambda (x) (apply + x))) + (diff-pairs) + (filter positive?) + (length _)) diff --git a/2021/day10/10a.hs b/2021/day10/10a.hs new file mode 100644 index 0000000..7dadbce --- /dev/null +++ b/2021/day10/10a.hs @@ -0,0 +1,50 @@ +module Main where + +isStartParen :: Char -> Bool +isStartParen '(' = True +isStartParen '[' = True +isStartParen '{' = True +isStartParen '<' = True +isStartParen _ = False + +isEndParen :: Char -> Bool +isEndParen ')' = True +isEndParen ']' = True +isEndParen '}' = True +isEndParen '>' = True +isEndParen _ = False + +flipParen :: Char -> Char +flipParen '(' = ')' +flipParen ')' = '(' +flipParen '[' = ']' +flipParen ']' = '[' +flipParen '{' = '}' +flipParen '}' = '{' +flipParen '<' = '>' +flipParen '>' = '<' +flipParen _ = undefined + +getScore :: Char -> Int +getScore ')' = 3 +getScore ']' = 57 +getScore '}' = 1197 +getScore '>' = 25137 + +consumeBlock :: Char -> String -> Either Char String +consumeBlock t "" = Right "" +consumeBlock t (c:cs) | c == flipParen t = Right cs + | isStartParen c = (consumeBlock c cs) >>= (consumeBlock t) + | otherwise = Left c + +corruptionScore :: String -> Int +corruptionScore "" = 0 +corruptionScore (c:cs) = case consumeBlock c cs of + Left c -> getScore c + Right s -> corruptionScore s + +main :: IO () +main = do + s <- readFile "./input" + let notCorrupted = foldr (+) 0 $ map corruptionScore (lines s) + print notCorrupted diff --git a/2021/day10/10b.hs b/2021/day10/10b.hs new file mode 100644 index 0000000..39b427f --- /dev/null +++ b/2021/day10/10b.hs @@ -0,0 +1,66 @@ +module Main where + +import Data.List (sort) + +isStartParen :: Char -> Bool +isStartParen '(' = True +isStartParen '[' = True +isStartParen '{' = True +isStartParen '<' = True +isStartParen _ = False + +isEndParen :: Char -> Bool +isEndParen ')' = True +isEndParen ']' = True +isEndParen '}' = True +isEndParen '>' = True +isEndParen _ = False + +flipParen :: Char -> Char +flipParen '(' = ')' +flipParen ')' = '(' +flipParen '[' = ']' +flipParen ']' = '[' +flipParen '{' = '}' +flipParen '}' = '{' +flipParen '<' = '>' +flipParen '>' = '<' +flipParen _ = undefined + +getScore :: Char -> Int +getScore ')' = 3 +getScore ']' = 57 +getScore '}' = 1197 +getScore '>' = 25137 + +completionScore :: Char -> Int +completionScore ')' = 1 +completionScore ']' = 2 +completionScore '}' = 3 +completionScore '>' = 4 +completionScore _ = undefined + +consumeBlock :: Char -> String -> Either Char String +consumeBlock t "" = Right "" +consumeBlock t (c:cs) | c == flipParen t = Right cs + | isStartParen c = (consumeBlock c cs) >>= (consumeBlock t) + | otherwise = Left c + +corruptionScore :: String -> Int +corruptionScore "" = 0 +corruptionScore (c:cs) = case consumeBlock c cs of + Left c -> getScore c + Right s -> corruptionScore s + +getCompletion :: String -> String -> String +getCompletion stack "" = map flipParen stack +getCompletion stack (c:cs) | isStartParen c = getCompletion (c : stack) cs + | otherwise = getCompletion (tail stack) cs + +main :: IO () +main = do + s <- readFile "./input" + let notCorrupted = filter ((== 0) . corruptionScore) (lines s) + let scores = sort $ map ((foldl (\acc x -> (acc * 5) + (completionScore x)) 0) . getCompletion "") notCorrupted + + print $ scores !! (div (length scores) 2) diff --git a/2021/day11/11a.py b/2021/day11/11a.py new file mode 100644 index 0000000..1c6d096 --- /dev/null +++ b/2021/day11/11a.py @@ -0,0 +1,42 @@ +def adjacent(coord, arr): + x, y = coord + max_x = len(arr[y]) - 1 + max_y = len(arr) - 1 + for dx in [-1, 0, 1]: + for dy in [-1, 0, 1]: + xp, yp = (x + dx, y + dy) + if ((xp, yp) == coord or min(xp, yp) < 0 or xp > max_x or yp > max_y): + continue + yield (xp, yp) + +def flash(coord, arr, flashed): + flashed.add(coord) + for (x, y) in adjacent(coord, arr): + arr[y][x] += 1 + visit((x, y), arr, flashed) + +def visit(coord, arr, flashed): + x, y = coord + v = arr[y][x] + if v > 9 and coord not in flashed: + flash(coord, arr, flashed) + +def step(arr): + flashed = set() + for (x,y) in ((x,y) for (y,l) in enumerate(arr) for (x,_) in enumerate(l)): + arr[y][x] = arr[y][x] + 1 + visit((x,y), arr, flashed) + for (x,y) in flashed: + arr[y][x] = 0 + return len(flashed) + +def print_board(arr): + print("\n".join(["".join(map(str, l)) for l in arr])) + +state = [[int(n) for n in l] for l in open("./input").read().strip().split("\n")] +total_flashes = 0 +for _ in range(0, 100): + flashes = step(state) + total_flashes += flashes + +print(total_flashes) diff --git a/2021/day11/11b.py b/2021/day11/11b.py new file mode 100644 index 0000000..18b45d4 --- /dev/null +++ b/2021/day11/11b.py @@ -0,0 +1,44 @@ +def adjacent(coord, arr): + x, y = coord + max_x = len(arr[y]) - 1 + max_y = len(arr) - 1 + for dx in [-1, 0, 1]: + for dy in [-1, 0, 1]: + xp, yp = (x + dx, y + dy) + if ((xp, yp) == coord or min(xp, yp) < 0 or xp > max_x or yp > max_y): + continue + yield (xp, yp) + +def flash(coord, arr, flashed): + flashed.add(coord) + for (x, y) in adjacent(coord, arr): + arr[y][x] += 1 + visit((x, y), arr, flashed) + +def visit(coord, arr, flashed): + x, y = coord + v = arr[y][x] + if v > 9 and coord not in flashed: + flash(coord, arr, flashed) + +def step(arr): + flashed = set() + for (x,y) in ((x,y) for (y,l) in enumerate(arr) for (x,_) in enumerate(l)): + arr[y][x] = arr[y][x] + 1 + visit((x,y), arr, flashed) + for (x,y) in flashed: + arr[y][x] = 0 + return len(flashed) + +def print_board(arr): + print("\n".join(["".join(map(str, l)) for l in arr])) + +state = [[int(n) for n in l] for l in open("./input").read().strip().split("\n")] +total_squares = sum([len(l) for l in state]) +n = 0 +while True: + n += 1 + if step(state) == total_squares: + break + +print(n) diff --git a/2021/day12/12a.py b/2021/day12/12a.py new file mode 100644 index 0000000..5d1adba --- /dev/null +++ b/2021/day12/12a.py @@ -0,0 +1,34 @@ +from collections import deque + +def parseInput(contents): + edges = [l.split("-") for l in contents.strip().split("\n")] + edges_set = set([]) + for (f, t) in edges: + edges_set.add((f, t)) + if t != "end" and f != "start": + edges_set.add((t, f)) + + return edges_set + +def visitableNeighbours(edges, loc): + fr = loc[0] + banned = [e for e in loc if e.islower()] + for (f, t) in edges: + if f == fr and t not in banned: + yield t + + +edges = parseInput(open("./input").read()) + +locs = deque() # each element is a list of all the visited nodes +finished = set() +locs.append(["start"]) +while len(locs) > 0: + l = locs.pop() + if l[0] == "end": + finished.add("-".join(l)) + else: + for neighbour in visitableNeighbours(edges, l): + locs.append([neighbour] + l) + +print(len(finished)) diff --git a/2021/day12/12b.py b/2021/day12/12b.py new file mode 100644 index 0000000..149749e --- /dev/null +++ b/2021/day12/12b.py @@ -0,0 +1,32 @@ +from collections import deque + +def parseInput(contents): + edges = [l.split("-") for l in contents.strip().split("\n")] + edges_set = set([]) + for (f, t) in edges: + edges_set.add((f, t)) + if t != "end" and f != "start": + edges_set.add((t, f)) + + return edges_set + +def visitableNeighbours(edges, path, doubleVisited): + curr = path[0] + banned = [e for e in path if e.islower()] if doubleVisited else ["start"] + for (f, t) in edges: + if f == curr and t not in banned: + yield t + + +edges = parseInput(open("./input").read()) + +locs = deque() # each element is a tuple of (double visited, list of all the visited nodes) +finished = set() +locs.append((False, ["start"])) +while len(locs) > 0: + doubleVisited, path = locs.pop() + if path[0] == "end": + finished.add("-".join(path)) + else: + for neighbour in visitableNeighbours(edges, path, doubleVisited): + locs.append((doubleVisited or (neighbour.islower() and neighbour in path), [neighbour] + path)) diff --git a/2021/day13/13a.hs b/2021/day13/13a.hs new file mode 100644 index 0000000..79af7ae --- /dev/null +++ b/2021/day13/13a.hs @@ -0,0 +1,34 @@ +{-# LANGUAGE ViewPatterns #-} +{-# LANGUAGE OverloadedStrings #-} +module Main where + +import qualified Data.Text as T +import Data.Set (Set) +import Data.List +import qualified Data.Set as S + +type Coord = (Int, Int) +data FoldInstr = Fold Axis Int deriving (Show, Eq, Ord) +data Axis = XAxis | YAxis deriving (Show, Eq, Ord) + +parseCoords :: String -> Coord +parseCoords s = (read x, read y) + where [x, y] = map T.unpack $ T.splitOn "," (T.pack s) + +parseFold :: String -> FoldInstr +parseFold (stripPrefix "fold along y=" -> Just cs) = Fold YAxis (read cs) +parseFold (stripPrefix "fold along x=" -> Just cs) = Fold XAxis (read cs) + +parseFile :: String -> (Set Coord, [FoldInstr]) +parseFile s = (S.fromList $ map parseCoords (lines coordSection), map parseFold (lines foldSection)) + where [coordSection, foldSection] = map T.unpack $ T.splitOn "\n\n" (T.pack s) + +performFold :: Set Coord -> FoldInstr -> Set Coord +performFold coords (Fold YAxis ye) = S.map (\(x, y) -> (x, -(abs (y - ye)) + ye)) coords +performFold coords (Fold XAxis xe) = S.map (\(x, y) -> (-(abs (x - xe)) + xe, y)) coords + +main :: IO () +main = do + f <- readFile "./input" + let (coords, instrs) = parseFile f; + print $ length $ performFold coords (head instrs) diff --git a/2021/day13/13b.hs b/2021/day13/13b.hs new file mode 100644 index 0000000..32d29de --- /dev/null +++ b/2021/day13/13b.hs @@ -0,0 +1,45 @@ +{-# LANGUAGE ViewPatterns #-} +{-# LANGUAGE OverloadedStrings #-} +module Main where + +import qualified Data.Text as T +import Data.Set (Set) +import Data.List +import qualified Data.Set as S + +type Coord = (Int, Int) +data FoldInstr = Fold Axis Int deriving (Show, Eq, Ord) +data Axis = XAxis | YAxis deriving (Show, Eq, Ord) + +parseCoords :: String -> Coord +parseCoords s = (read x, read y) + where [x, y] = map T.unpack $ T.splitOn "," (T.pack s) + +parseFold :: String -> FoldInstr +parseFold (stripPrefix "fold along y=" -> Just cs) = Fold YAxis (read cs) +parseFold (stripPrefix "fold along x=" -> Just cs) = Fold XAxis (read cs) + +parseFile :: String -> (Set Coord, [FoldInstr]) +parseFile s = (S.fromList $ map parseCoords (lines coordSection), map parseFold (lines foldSection)) + where [coordSection, foldSection] = map T.unpack $ T.splitOn "\n\n" (T.pack s) + +performFold :: Set Coord -> FoldInstr -> Set Coord +performFold coords (Fold YAxis ye) = S.map (\(x, y) -> (x, -(abs (y - ye)) + ye)) coords +performFold coords (Fold XAxis xe) = S.map (\(x, y) -> (-(abs (x - xe)) + xe, y)) coords + +displayCoords :: Set Coord -> String +displayCoords coords = intercalate "\n" (map displayLine [sy..ey]) + where sx = minimum (S.map fst coords) + ex = maximum (S.map fst coords) + sy = minimum (S.map snd coords) + ey = maximum (S.map snd coords) + displayLine y = map (displayCoord y) [sx..ex] + displayCoord y x | S.member (x, y) coords = '#' + | otherwise = '.' + +main :: IO () +main = do + f <- readFile "./input" + let (coords, instrs) = parseFile f; + let result = foldl performFold coords instrs; + putStrLn $ displayCoords result diff --git a/2021/day14/14.hs b/2021/day14/14.hs new file mode 100644 index 0000000..3221655 --- /dev/null +++ b/2021/day14/14.hs @@ -0,0 +1,43 @@ +{-# LANGUAGE OverloadedStrings #-} +module Main where + +import Data.Map (Map) +import qualified Data.Map as M +import qualified Data.Text as T + +type Pair = (Char, Char) + +doSubstitutions :: Map Pair Char -> Map Pair Int -> Map Pair Int +doSubstitutions rules s = M.fromListWith (+) $ concatMap checkPair (M.toList s) + where checkPair ((a, b), count) = case M.lookup (a, b) rules of + Just v -> [((a, v), count), ((v, b), count)] + Nothing -> [((a, b), count)] + +stringToPairs :: String -> Map Pair Int +stringToPairs s = M.fromListWith (+) $ [((a, b), 1) | (a, b) <- (zip s (tail s))] ++ [((last s, '_'), 1)] + +countLetters :: Map Pair Int -> Map Char Int +countLetters m = M.fromListWith (+) [(a, count) | ((a, _), count) <- M.toList m] + +parseRuleEntry :: String -> (Pair, Char) +parseRuleEntry s = ((a, b), head $ T.unpack r) + where [t, r] = T.splitOn " -> " (T.pack s) + [a, b] = T.unpack t + +parseFile :: String -> (Map Pair Int, Map Pair Char) +parseFile s = (stringToPairs (T.unpack initial), M.fromList $ map parseRuleEntry rules) + where [initial, rulesSection] = T.splitOn "\n\n" (T.pack s) + rules = lines (T.unpack rulesSection) + + +main :: IO () +main = do + input <- readFile "./input" + let (initial, rules) = parseFile input + let result = foldr (\_ acc -> doSubstitutions rules acc) initial [1..40] + let counts = countLetters result + + let mx = maximum (M.elems counts) + let mi = minimum (M.elems counts) + print (mx, mi) + print $ mx - mi diff --git a/2021/day15/15a.py b/2021/day15/15a.py new file mode 100644 index 0000000..d7c984b --- /dev/null +++ b/2021/day15/15a.py @@ -0,0 +1,63 @@ +import heapq + +grid = [[int(x) for x in l] for l in open("./input").read().strip().split("\n")] + +def in_bounds(c): + x, y = c + return x >= 0 and y >= 0 and y < len(grid) and x < len(grid[y]) + +def next_steps(path): + sx, sy = path[0] + for c in [(sx + 1, sy), (sx - 1, sy), (sx, sy + 1), (sx, sy - 1)]: + if c not in path and in_bounds(c): + yield c + +def step_path(path): + for c in next_steps(path): + yield [c] + path + +def total_risk(path): + acc = 0 + for x, y in path: + if (x, y) == (0, 0): + continue + risk = grid[y][x] + acc += risk + + return acc + +def manhattan(a, b): + dx = abs(a[0] - b[0]) + dy = abs(a[1] - b[1]) + return dx + dy + +def heuristic(path): + return total_risk(path) - manhattan(path[0], (len(grid), len(grid[0]))) + +class HeapItem: + def __init__(self, path): + self.heur = heuristic(path) + self.path = path + + def __lt__(self, other): + return self.heur < other.heur + +def find_path(start): + q = [] + visited = set() + heapq.heappush(q, HeapItem([start])) + while True: + path = heapq.heappop(q).path + if path[0] == (len(grid) - 1, len(grid[0]) - 1): + return path + + if path[0] in visited: + continue + visited.add(path[0]) + + for new in step_path(path): + heapq.heappush(q, HeapItem(new)) + +path = find_path((0, 0)) +print(path) +print(total_risk(path)) diff --git a/2021/day15/15b.py b/2021/day15/15b.py new file mode 100644 index 0000000..534eb3f --- /dev/null +++ b/2021/day15/15b.py @@ -0,0 +1,80 @@ +import heapq + +grid = [[int(x) for x in l] for l in open("./input").read().strip().split("\n")] +GRID_SIZE_X = len(grid) +GRID_SIZE_Y = len(grid[0]) + +def in_bounds(c, tiles): + x, y = c + return x >= 0 and y >= 0 and y < (GRID_SIZE_Y * tiles) and x < (GRID_SIZE_X * tiles) + +def next_steps(path, tiles): + sx, sy = path[0] + for c in [(sx + 1, sy), (sx - 1, sy), (sx, sy + 1), (sx, sy - 1)]: + if c not in path and in_bounds(c, tiles): + yield c + +def step_path(path, tiles): + for c in next_steps(path, tiles): + yield [c] + path + +def risk_for(x, y): + tile_x = x // GRID_SIZE_X + tile_y = y // GRID_SIZE_Y + delta = tile_x + tile_y + risk = grid[y % GRID_SIZE_Y][x % GRID_SIZE_X] + delta + while risk > 9: + risk -= 9 + return risk + +def total_risk(path): + acc = 0 + for x, y in path: + if (x, y) == (0, 0): + continue + risk = risk_for(x, y) + acc += risk + + return acc + +def manhattan(a, b): + dx = abs(a[0] - b[0]) + dy = abs(a[1] - b[1]) + return dx + dy + +def heuristic(path, dst): + return total_risk(path) - manhattan(path[0], dst) + +class HeapItem: + def __init__(self, heur, path): + self.heur = heur + self.path = path + + def __lt__(self, other): + return self.heur < other.heur + +def find_path(start, tiles): + q = [] + max_x = (GRID_SIZE_X * tiles) - 1 + max_y = (GRID_SIZE_Y * tiles) - 1 + dst = (max_x, max_y) + visited = set() + heapq.heappush(q, HeapItem(0, [start])) + while True: + i = heapq.heappop(q) + heur = i.heur + path = i.path + if path[0] == (max_x, max_y): + return path + + if path[0] in visited: + continue + visited.add(path[0]) + + for new in step_path(path, tiles): + loc = new[0] + heapq.heappush(q, HeapItem(heur + risk_for(loc[0], loc[1]), new)) + +path = find_path((0, 0), 5) +print(path) +print(total_risk(path)) diff --git a/2021/day16/16.hs b/2021/day16/16.hs new file mode 100644 index 0000000..f38240a --- /dev/null +++ b/2021/day16/16.hs @@ -0,0 +1,87 @@ +module Main where + +import Numeric (readHex) +import Text.Printf (printf) +import Data.Char (digitToInt) +import Data.List (foldl') + + +readInt :: Int -> [Bool] -> (Integer, [Bool]) +readInt n bs = (foldl' (\acc x -> acc * 2 + boolToDigit x) 0 (take n bs), drop n bs) + where boolToDigit True = 1 + boolToDigit False = 0 + +hexToBits :: String -> [Bool] +hexToBits "" = [] +hexToBits (c:cs) = case readHex [c] of + (x, _):_ -> (map binToBool $ printf "%04b" (x :: Int)) ++ hexToBits cs + _ -> [] + where binToBool '1' = True + binToBool _ = False + +data Packet = Literal Integer Integer Integer | + Operator Integer Integer [Packet] | + Padding + deriving (Show, Eq, Ord) + + +parseHexPacket :: String -> (Packet, [Bool]) +parseHexPacket = parsePacket . hexToBits + +parseHeader :: [Bool] -> (Integer, Integer, [Bool]) +parseHeader bs = (version, typ, body) + where (version, afterVersion) = readInt 3 bs + (typ, body) = readInt 3 afterVersion + +parsePacket :: [Bool] -> (Packet, [Bool]) +parsePacket bs = case parseHeader bs of + (ver, 4, body) -> let (val, rest) = readLiteralInner body + in (Literal ver 4 val, rest) + (ver, op, body) -> let (val, rest) = readOpInner body + in (Operator ver op val, rest) + +readLiteralInner :: [Bool] -> (Integer, [Bool]) +readLiteralInner bs = readLiteralBlock 0 bs + where readLiteralBlock acc (cont:bs) | cont = readLiteralBlock acc' rest + | otherwise = (acc', rest) + where (val, rest) = readInt 4 bs + acc' = (16 * acc) + val + +readOpInner :: [Bool] -> ([Packet], [Bool]) +readOpInner (False:header) = (parseAllPackets (take (fromIntegral len) body), drop (fromIntegral len) body) + where (len, body) = readInt 15 header + parseAllPackets [] = [] + parseAllPackets bs = let (parsed, remaining) = parsePacket bs + in parsed : parseAllPackets remaining +readOpInner (True:header) = parseNPackets n body + where (n, body) = readInt 11 header + parseNPackets 0 b = ([], b) + parseNPackets n bs = let (parsed, remaining) = parsePacket bs + (restParsed, endRemaining) = parseNPackets (n - 1) remaining + in (parsed : restParsed, endRemaining) + +sumVersion :: Packet -> Integer +sumVersion (Literal v _ _) = v +sumVersion (Operator v _ ps) = v + (foldr (+) 0 (map sumVersion ps)) +sumVersion Padding = 0 + +eval :: Packet -> Integer +eval (Literal _ _ v) = v +eval (Operator _ 0 ps) = sum (map eval ps) +eval (Operator _ 1 ps) = product (map eval ps) +eval (Operator _ 2 ps) = minimum (map eval ps) +eval (Operator _ 3 ps) = maximum (map eval ps) +eval (Operator _ 5 ps) = if a > b then 1 else 0 + where [a, b] = map eval ps +eval (Operator _ 6 ps) = if a < b then 1 else 0 + where [a, b] = map eval ps +eval (Operator _ 7 ps) = if a == b then 1 else 0 + where [a, b] = map eval ps + + +main :: IO () +main = do + input <- readFile "./input" + let (parsed, _) = parseHexPacket input + print $ sumVersion parsed + print $ eval parsed diff --git a/2021/day17/.gitignore b/2021/day17/.gitignore new file mode 100644 index 0000000..9f97022 --- /dev/null +++ b/2021/day17/.gitignore @@ -0,0 +1 @@ +target/
\ No newline at end of file diff --git a/2021/day17/Cargo.lock b/2021/day17/Cargo.lock new file mode 100644 index 0000000..b5feb35 --- /dev/null +++ b/2021/day17/Cargo.lock @@ -0,0 +1,42 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aho-corasick" +version = "0.7.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e37cfd5e7657ada45f742d6e99ca5788580b5c529dc78faf11ece6dc702656f" +dependencies = [ + "memchr", +] + +[[package]] +name = "day17" +version = "0.1.0" +dependencies = [ + "regex", +] + +[[package]] +name = "memchr" +version = "2.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "308cc39be01b73d0d18f82a0e7b2a3df85245f84af96fdddc5d202d27e47b86a" + +[[package]] +name = "regex" +version = "1.5.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d07a8629359eb56f1e2fb1652bb04212c072a87ba68546a04065d525673ac461" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-syntax" +version = "0.6.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f497285884f3fcff424ffc933e56d7cbca511def0c9831a7f9b5f6153e3cc89b" diff --git a/2021/day17/Cargo.toml b/2021/day17/Cargo.toml new file mode 100644 index 0000000..0f39b6d --- /dev/null +++ b/2021/day17/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "day17" +version = "0.1.0" +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +regex = "1" diff --git a/2021/day17/src/main.rs b/2021/day17/src/main.rs new file mode 100644 index 0000000..641962e --- /dev/null +++ b/2021/day17/src/main.rs @@ -0,0 +1,90 @@ +use regex::Regex; +use std::{fs::read_to_string, ops::Range}; + +#[derive(Debug, Clone, Copy)] +struct Coord(isize, isize); + +#[derive(Debug, Clone)] +struct TargetArea(pub Range<isize>, pub Range<isize>); +impl TargetArea { + fn contains(&self, c: Coord) -> bool { + self.0.contains(&c.0) && self.1.contains(&c.1) + } +} + +fn parse_target_area(line: &str) -> TargetArea { + let x_caps = Regex::new(r"x=([-\d]*)..([-\d]*)") + .unwrap() + .captures(line) + .unwrap(); + let y_caps = Regex::new(r"y=([-\d]*)..([-\d]*)") + .unwrap() + .captures(line) + .unwrap(); + + TargetArea( + x_caps[1].parse().unwrap()..x_caps[2].parse::<isize>().unwrap() + 1isize, + y_caps[1].parse().unwrap()..y_caps[2].parse::<isize>().unwrap() + 1isize, + ) +} + +fn does_intersect(mut vx: isize, mut vy: isize, area: &TargetArea) -> bool { + let mut x = 0; + let mut y = 0; + for _ in 0.. { + x += vx; + y += vy; + + vx = if vx > 0 { + vx - 1 + } else if vx < 0 { + vx + 1 + } else { + 0 + }; + vy -= 1; + if area.contains(Coord(x, y)) { + return true; + } else if x > area.0.end || y < area.1.start { + return false; + } + } + + unreachable!() +} + +fn max_y(mut vy: isize) -> isize { + let mut y = 0; + for _ in 0.. { + y += vy; + vy -= 1; + + if vy <= 0 { + return y; + } + } + + unreachable!() +} + +fn main() { + let area = parse_target_area(&read_to_string("./input").unwrap()); + + let mut max_y_found = 0; + let mut max_y_vel = Coord(0, 0); + let mut num_valid = 0; + for vx in 0..=area.0.end * 2 { + for vy in -area.1.start.abs() * 2..=area.1.start.abs() * 2 { + if does_intersect(vx, vy, &area) { + if max_y(vy) > max_y_found { + max_y_found = max_y(vy); + max_y_vel = Coord(vx, vy); + } + num_valid += 1; + } + } + } + + println!("part 1: {} with velocity {:?}", max_y_found, max_y_vel); + println!("part 2: {} possible velocities", num_valid); +} diff --git a/2021/day18/18.py b/2021/day18/18.py new file mode 100644 index 0000000..88ebf5e --- /dev/null +++ b/2021/day18/18.py @@ -0,0 +1,132 @@ +from math import ceil + +class SnailfishItem: + def __init__(self, parent, contents): + self.parent = parent + self.atomic = not isinstance(contents, list) + if not self.atomic: + if isinstance(contents[0], SnailfishItem): + self.left = contents[0] + self.left.parent = self + else: + self.left = SnailfishItem(self, contents[0]) + if isinstance(contents[1], SnailfishItem): + self.right = contents[1] + self.right.parent = self + else: + self.right = SnailfishItem(self, contents[1]) + else: + self.contents = contents + + def __str__(self): + if self.atomic: + return str(self.contents) + else: + return "[%s, %s]" % (str(self.left), str(self.right)) + + def add(self, other): + if self.atomic and other.atomic: + self.contents += other.contents + else: + if self.atomic: + self.left = SnailfishItem(self, self.contents) + else: + self.left = SnailfishItem(self, [self.left, self.right]) + self.atomic = False + self.right = other + other.parent = self + self.contents = None + while self.reduce(): + pass + + def check_explodes(self, n=0): + if self.atomic: + return False + elif n < 4: + return self.left.check_explodes(n+1) or self.right.check_explodes(n+1) + + self.explode_left() + self.explode_right() + + self.atomic = True + self.contents = 0 + self.left = None + self.right = None + + return True + + def check_splits(self): + if not self.atomic: + return self.left.check_splits() or self.right.check_splits() + elif self.contents < 10: + return False + + self.atomic = False + self.left = SnailfishItem(self, self.contents // 2) + self.right = SnailfishItem(self, ceil(self.contents / 2)) + self.contents = None + return True + + def reduce(self, n=0): + if not self.atomic: + return self.check_explodes(n) or self.check_splits() + else: + return self.check_splits() + + def explode_left(self): + last_node = self + node = self.parent + while node != None and node.left == last_node: + last_node = node + node = last_node.parent + + if node == None: + return # leftmost element of tree + + node = node.left + while not node.atomic: + node = node.right + + node.add(self.left) + + def explode_right(self): + last_node = self + node = self.parent + while node != None and node.right == last_node: + last_node = node + node = last_node.parent + + if node == None: + return # rightmost element of tree + + node = node.right + while not node.atomic: + node = node.left + + node.add(self.right) + + def magnitude(self): + if self.atomic: + return self.contents + else: + return (3 * self.left.magnitude()) + (2 * self.right.magnitude()) + +lines = open("./input").read().strip().split("\n") +val = SnailfishItem(None, eval(lines[0])) # cope, seethe, mald, etc. +for line in lines[1:]: + val.add(SnailfishItem(None, eval(line))) + +print("Part 1: %d" % val.magnitude()) + +max_mag = 0 +for x_str in lines: + for y_str in lines: + if x_str == y_str: + continue + x = SnailfishItem(None, eval(x_str)) + x.add(SnailfishItem(None, eval(y_str))) + + if x.magnitude() > max_mag: + max_mag = x.magnitude() + +print("Part 2: %d" % max_mag) diff --git a/2021/day19/19.hs b/2021/day19/19.hs new file mode 100644 index 0000000..a2cabb3 --- /dev/null +++ b/2021/day19/19.hs @@ -0,0 +1,108 @@ +{-# LANGUAGE FlexibleInstances #-} +{-# LANGUAGE TypeSynonymInstances #-} +{-# LANGUAGE BlockArguments #-} +{-# LANGUAGE OverloadedStrings #-} +module Main where + +import Data.Monoid (Endo (Endo), appEndo) +import Data.Maybe (listToMaybe, isJust) +import Data.List (isPrefixOf) +import Linear.Vector ((^+^), (^-^)) +import Linear.V3 (V3 (V3)) + +import Data.Set (Set) + +import qualified Data.Set as S +import qualified Data.Map as M +import qualified Data.Text as T + +type Vec3 = V3 Integer +type Transform = Endo Vec3 +data Scanner = Scanner { beacons :: [Vec3] + } deriving (Show, Eq) +data PositionedScanner = PositionedScanner { scanner :: Scanner + ,originOffset :: Vec3 + } deriving (Show) + +instance Show Transform where + show c = show $ appEndo c (V3 0 0 0) + +nullTrans = Endo id +rotX = Endo \(V3 x y z) -> V3 x (- z) y +rotY = Endo \(V3 x y z) -> V3 z y (- x) +rotZ = Endo \(V3 x y z) -> V3 (- y) x z +translate v = Endo (v ^+^) + +rotations :: [Transform] +rotations = [a <> b | a <- ras, b <- rbs] + where ras = [ nullTrans, rotY, rotY <> rotY, rotY <> rotY <> rotY + , rotZ, rotZ <> rotZ <> rotZ] + rbs = [nullTrans, rotX, rotX <> rotX, rotX <> rotX <> rotX] + +threshold :: Integer +threshold = 12 + +firstJust :: [Maybe a] -> Maybe a +firstJust xs | null js = Nothing + | otherwise = (head js) + where js = filter isJust xs + +parseFile :: String -> [[Vec3]] +parseFile s = reverse $ parseLines (tail $ lines s) [[]] + where parseLines [] cs = cs + parseLines (l:ls) (c:cs) | "---" `isPrefixOf` l = parseLines ls ([] : c : cs) + | null l = parseLines ls (c : cs) + | otherwise = parseLines ls ((parseLine l : c) : cs) + parseLine l = V3 x y z + where [x, y, z] = map (read . T.unpack) $ T.splitOn "," $ T.pack l + +commonOffset :: [Vec3] -> [Vec3] -> Maybe Vec3 +commonOffset ys xs = listToMaybe aboveThreshold >>= (Just . fst) + where dists = [x ^-^ y | x <- xs, y <- ys] + distCounts = M.toList $ M.fromListWith (+) [(d, 1) | d <- dists] + aboveThreshold = filter ((>= threshold) . snd) distCounts + +applyTransform :: Transform -> Scanner -> Scanner +applyTransform t (Scanner bs) = Scanner (map (appEndo t) bs) + +-- attempt to get a's offset from b +offsetFrom :: Scanner -> Scanner -> Maybe (Vec3, Scanner) +offsetFrom a b = listToMaybe successes + where attempts = [attemptWith rot | rot <- rotations] + successes = [(a, b) | (Just a, b) <- attempts] + attemptWith rot = (commonOffset (beacons a') (beacons b), a') + where a' = applyTransform rot a + +adjustedOffsetFrom :: PositionedScanner -> Scanner -> Maybe PositionedScanner +adjustedOffsetFrom b a = case a `offsetFrom` (scanner b) of + Just (off, sc) -> Just $ PositionedScanner sc (off ^+^ (originOffset b)) + Nothing -> Nothing + +solveMore :: [PositionedScanner] -> [Scanner] -> ([PositionedScanner], [Scanner]) +solveMore ks us = foldr solveOne (ks, us) us + where solveOne s (ks', us') = case firstJust (map (\k -> adjustedOffsetFrom k s) ks') of + Just d -> (d : ks', filter (/= s) us') + Nothing -> (ks', us') + +calcAllOffsets :: [Scanner] -> [PositionedScanner] +calcAllOffsets (s:ss) = keepSolvingMore ([PositionedScanner s (V3 0 0 0)], ss) + where keepSolvingMore (ks,[]) = ks + keepSolvingMore (ks,us) = keepSolvingMore (solveMore ks us) + +absoluteBeacons :: PositionedScanner -> Set Vec3 +absoluteBeacons (PositionedScanner sc pos) = S.fromList $ map (pos ^+^) (beacons sc) + +manhattan :: Vec3 -> Vec3 -> Integer +manhattan (V3 x y z) (V3 x' y' z') = (abs (x' -x)) + (abs (y' - y)) + (abs (z' - z)) + +main :: IO () +main = do + input <- readFile "./input" + let parsed = map Scanner $ parseFile input + let positioned = calcAllOffsets parsed + let beacons = foldr S.union S.empty $ map absoluteBeacons positioned + + print $ "Part 1: " ++ (show $ S.size beacons) + + let scannerPositions = map originOffset positioned + print $ "Part 2: " ++ (show $ maximum [manhattan a b | a <- scannerPositions, b <- scannerPositions]) diff --git a/2021/day2/02a.rkt b/2021/day2/02a.rkt new file mode 100644 index 0000000..2317a9a --- /dev/null +++ b/2021/day2/02a.rkt @@ -0,0 +1,25 @@ +#lang racket + +(define (parse-line line) + (define split (string-split line " ")) + (cond [(empty? split) + (datum->syntax #f "")] + [else (define command (car split)) + (define arg (second split)) + (datum->syntax #f `(,(string->symbol command) ,(string->number arg)))])) + +(define (read-syntax path port) + (define src-datums (map parse-line (port->lines port))) + (datum->syntax #f `(module day2 racket + (define depth 0) + (define pos 0) + (define (forward x) + (set! pos (+ pos x))) + (define (down x) + (set! depth (+ depth x))) + (define (up x) + (set! depth (- depth x))) + ,@src-datums + (* depth pos)))) + +(provide read-syntax) diff --git a/2021/day2/02b.rkt b/2021/day2/02b.rkt new file mode 100644 index 0000000..7688c1d --- /dev/null +++ b/2021/day2/02b.rkt @@ -0,0 +1,27 @@ +#lang racket + +(define (parse-line line) + (define split (string-split line " ")) + (cond [(empty? split) + (datum->syntax #f "")] + [else (define command (car split)) + (define arg (second split)) + (datum->syntax #f `(,(string->symbol command) ,(string->number arg)))])) + +(define (read-syntax path port) + (define src-datums (map parse-line (port->lines port))) + (datum->syntax #f `(module day2 racket + (define depth 0) + (define pos 0) + (define aim 0) + (define (forward x) + (set! pos (+ pos x)) + (set! depth (+ depth (* aim x)))) + (define (down x) + (set! aim (+ aim x))) + (define (up x) + (set! aim (- aim x))) + ,@src-datums + (* depth pos)))) + +(provide read-syntax) diff --git a/2021/day20/20.hs b/2021/day20/20.hs new file mode 100644 index 0000000..2798214 --- /dev/null +++ b/2021/day20/20.hs @@ -0,0 +1,61 @@ +module Main where + +import Data.List (foldl', intercalate) +import Data.Maybe (fromMaybe) + +type Picture = ([[Bool]], Bool) -- Visible region, colour of all pixels not visible + +readInteger :: [Bool] -> Int +readInteger = foldl' (\acc x -> acc * 2 + boolToDigit x) 0 + where boolToDigit True = 1 + boolToDigit False = 0 + +parseLine :: String -> [Bool] +parseLine = map charToBool + where charToBool '#' = True + charToBool '.' = False + +(!?) :: [a] -> Int -> Maybe a +xs !? n | n < 0 || n >= (length xs) = Nothing + | otherwise = Just (xs!!n) + +getPixel :: Picture -> Int -> Int -> Bool +getPixel (p, d) x y = fromMaybe d $ (p !? y) >>= (!? x) + +getNeighbours :: Picture -> Int -> Int -> [Bool] +getNeighbours p x y = [getPixel p (x + dx) (y + dy) | dy <- [(-1)..1], dx <- [(-1)..1]] + +getNewPixel :: Picture -> [Bool] -> Int -> Int -> Bool +getNewPixel p alg x y = alg !! (readInteger $ getNeighbours p x y) + +printPic :: Picture -> String +printPic = (intercalate "\n") . (map printLine) . fst + where printLine = map printBool + printBool True = '#' + printBool False = '.' + +newDefault :: Bool -> [Bool] -> Bool +newDefault True alg = alg!!511 +newDefault False alg = alg!!0 + +applyAlgorithm :: Picture -> [Bool] -> Picture +applyAlgorithm pic@(vis, def) alg = ([[getNewPixel pic alg x y | x <- [(-1)..mx]] | y <- [(-1)..my]], newDefault def alg) + where mx = length (vis!!0) + 1 + my = length vis + 1 + +parseFile :: String -> ([Bool], Picture) +parseFile s = (parseLine alg, (map parseLine ls, False)) + where (alg:_:ls) = lines s + +countPixels :: Picture -> Int +countPixels = foldr (+) 0 . map (length . filter id) . fst + +main :: IO () +main = do + input <- readFile "./input" + let (alg, pic) = parseFile input + let pic2 = foldr (\_ p -> applyAlgorithm p alg) pic [1..2] + putStrLn $ "Part 1: " ++ (show $ countPixels pic2) + + let pic50 = foldr (\_ p -> applyAlgorithm p alg) pic [1..50] + putStrLn $ "Part 2: " ++ (show $ countPixels pic50) diff --git a/2021/day21/21.py b/2021/day21/21.py new file mode 100644 index 0000000..8cd8307 --- /dev/null +++ b/2021/day21/21.py @@ -0,0 +1,52 @@ + +die_val = 1 +rolls = 0 +def roll(): + global die_val, rolls + x = die_val + + die_val += 1 + if die_val > 100: + die_val = 1 + + rolls += 1 + + return x + + +class Player: + def __init__(self, pos): + self.pos = pos + self.score = 0 + + def move(self, roll): + self.pos += roll + while self.pos > 10: + self.pos -= 10 + + def take_turn(self): + r = sum([roll() for _ in range(0, 3)]) + self.move(r) + self.score += self.pos + + def __str__(self): + return "<Player pos=%d score=%d>" % (self.pos, self.score) + +inp = open("./input").read().split("\n") +p1_start = int(inp[0].split(": ")[1]) +p2_start = int(inp[1].split(": ")[1]) + +p1 = Player(p1_start) +p2 = Player(p2_start) +turn = p1 +while p1.score < 1000 and p2.score < 1000: + turn.take_turn() + if turn == p1: + turn = p2 + else: + turn = p1 + +ans = p1.score * rolls +if p1.score >= 1000: + ans = p2.score * rolls +print("Part 1: %d" % ans) diff --git a/2021/day21/21b.py b/2021/day21/21b.py new file mode 100644 index 0000000..3404c22 --- /dev/null +++ b/2021/day21/21b.py @@ -0,0 +1,55 @@ +from collections import defaultdict + +POSSIBLE_ROLLS = [a + b + c for a in range(1, 4) for b in range(1, 4) for c in range(1, 4)] + +def move(p, roll): + pos, score = p + pos += roll + while pos > 10: + pos -= 10 + + return (pos, score + pos) + +def won(p): + return p[1] >= 21 + +P1_WON_KEY = (-1, -1, True) +P2_WON_KEY = (-1, -1, False) + +def step_universes(d): + nxt = defaultdict(lambda: 0) + nxt[P1_WON_KEY] = d[P1_WON_KEY] + nxt[P2_WON_KEY] = d[P2_WON_KEY] + for ((p1, p2, p1_turn), count) in d.items(): + if p1 == -1: + continue + elif won(p1): + nxt[P1_WON_KEY] += count + continue + elif won(p2): + nxt[P2_WON_KEY] += count + continue + + for roll in POSSIBLE_ROLLS: + if p1_turn: + nxt[(move(p1, roll), p2, False)] += count + else: + nxt[(p1, move(p2, roll), True)] += count + + return nxt + +inp = open("./input").read().split("\n") +p1_start = int(inp[0].split(": ")[1]) +p2_start = int(inp[1].split(": ")[1]) + +d = defaultdict(lambda: 0) +d[((p1_start, 0), (p2_start, 0), True)] = 1 +d = step_universes(d) + +while len(d) > 2: + d = step_universes(d) + +w1 = d[P1_WON_KEY] +w2 = d[P2_WON_KEY] +print("Part 2: %d" % max([w1, w2])) + diff --git a/2021/day22/22a.hs b/2021/day22/22a.hs new file mode 100644 index 0000000..bcf826f --- /dev/null +++ b/2021/day22/22a.hs @@ -0,0 +1,110 @@ +module Main where + +import Text.Parsec +import Data.Set (Set) +import qualified Data.Set as S +import Debug.Trace (trace) + +type Coord = (Int, Int, Int) +data Cuboid = Cuboid Coord Coord deriving (Show, Eq) +data Command = Command Bool Cuboid deriving (Show, Eq) + +onOff = toBool <$> (try (string "on") <|> string "off") + where toBool "on" = True + toBool _ = False + +number = do + sign <- (option '0' (char '-')) + num <- many1 digit + return $ read (sign : num) + +range = do + start <- number + string ".." + end <- number + + return $ (start, end) + +parseLine = do + val <- onOff + string " x=" + (sx, ex) <- range + string ",y=" + (sy, ey) <- range + string ",z=" + (sz, ez) <- range + + let c = Cuboid (sx, sy, sz) (ex, ey, ez) + return $ Command val c +parseFile = endBy parseLine (char '\n') + +intersects1D :: (Int, Int) -> (Int, Int) -> Bool +intersects1D (a1, a2) (b1, b2) = a2 > b1 && b2 > a1 + +zipCoords :: Coord -> Coord -> [(Int, Int)] +zipCoords (x, y, z) (x', y', z') = [(x, x'), (y, y'), (z, z')] + +intersects :: Cuboid -> Cuboid -> Bool +intersects (Cuboid s e) (Cuboid s' e') = any (uncurry intersects1D) (zip (zipCoords s e) (zipCoords s' e')) + +cEmpty :: Cuboid -> Bool +cEmpty (Cuboid (sx, sy, sz) (ex, ey, ez)) = sx > ex || sy > ey || sz > ez + +cVolume :: Cuboid -> Int +cVolume (Cuboid (sx, sy, sz) (ex, ey, ez)) = vx * vy * vz + where vx = abs (sx - (ex + 1)) + vy = abs (sy - (ey + 1)) + vz = abs (sz - (ez + 1)) + +ccVolume :: ChargedCuboid -> Int +ccVolume c | charge c = cVolume (cuboid c) + | otherwise = -(cVolume (cuboid c)) + +cIntersection :: Cuboid -> Cuboid -> Cuboid +cIntersection c1@(Cuboid s1 e1) c2@(Cuboid s2 e2) | not $ intersects c1 c2 = nullCuboid + | otherwise = (Cuboid s' e') + where s' = map3 (uncurry max) (zip3t s1 s2) + e' = map3 (uncurry min) (zip3t e1 e2) + +data ChargedCuboid = ChargedCuboid { charge :: Bool + ,cuboid :: Cuboid + } deriving (Show, Eq) + +performCommand :: [ChargedCuboid] -> Command -> [ChargedCuboid] +performCommand cs (Command val c) | val = (ChargedCuboid val c) : (cs ++ overlaps) + | otherwise = cs ++ overlaps + where overlaps = filter (not . cEmpty . cuboid) $ map invertedIntersection cs + invertedIntersection cc = ChargedCuboid (not (charge cc)) ((cuboid cc) `cIntersection` c) + +threshold = 50 + +interestedCuboid :: Cuboid +interestedCuboid = Cuboid ((-threshold), (-threshold), (-threshold)) (threshold, threshold, threshold) + +nullCuboid :: Cuboid +nullCuboid = Cuboid (0, 0, 0) ((-1), (-1), (-1)) + +map3 :: (a -> b) -> (a, a, a) -> (b, b, b) +map3 f (a, b, c) = (f a, f b, f c) + +zip3t :: (a, a, a) -> (b, b, b) -> ((a, b), (a, b), (a, b)) +zip3t (x, y, z) (x', y', z') = ((x, x'), (y, y'), (z, z')) + +cClamp :: Cuboid -> Cuboid +cClamp (Cuboid ss es) = Cuboid (sx', sy', sz') (ex', ey', ez') + where (sx', sy', sz') = map3 (max (-threshold)) ss + (ex', ey', ez') = map3 (min threshold) es + +minifyCommand :: Command -> Command +minifyCommand (Command v cb) | cEmpty clamped = Command False nullCuboid + | otherwise = Command v (cClamp cb) + where clamped = cClamp cb + +main = do + input <- readFile "./input" + let (Right parsed) = parse parseFile "input" input + let cmds = map minifyCommand parsed + + let cs = foldl performCommand [] cmds + let vol = foldr (+) 0 $ map ccVolume cs + print vol diff --git a/2021/day22/22b.hs b/2021/day22/22b.hs new file mode 100644 index 0000000..9773717 --- /dev/null +++ b/2021/day22/22b.hs @@ -0,0 +1,94 @@ +module Main where + +import Text.Parsec +import Data.Set (Set) +import qualified Data.Set as S +import Debug.Trace (trace) + +type Coord = (Int, Int, Int) +data Cuboid = Cuboid Coord Coord deriving (Show, Eq) +data Command = Command Bool Cuboid deriving (Show, Eq) + +onOff = toBool <$> (try (string "on") <|> string "off") + where toBool "on" = True + toBool _ = False + +number = do + sign <- (option '0' (char '-')) + num <- many1 digit + return $ read (sign : num) + +range = do + start <- number + string ".." + end <- number + + return $ (start, end) + +parseLine = do + val <- onOff + string " x=" + (sx, ex) <- range + string ",y=" + (sy, ey) <- range + string ",z=" + (sz, ez) <- range + + let c = Cuboid (sx, sy, sz) (ex, ey, ez) + return $ Command val c +parseFile = endBy parseLine (char '\n') + +intersects1D :: (Int, Int) -> (Int, Int) -> Bool +intersects1D (a1, a2) (b1, b2) = a2 > b1 && b2 > a1 + +zipCoords :: Coord -> Coord -> [(Int, Int)] +zipCoords (x, y, z) (x', y', z') = [(x, x'), (y, y'), (z, z')] + +intersects :: Cuboid -> Cuboid -> Bool +intersects (Cuboid s e) (Cuboid s' e') = any (uncurry intersects1D) (zip (zipCoords s e) (zipCoords s' e')) + +cEmpty :: Cuboid -> Bool +cEmpty (Cuboid (sx, sy, sz) (ex, ey, ez)) = sx > ex || sy > ey || sz > ez + +cVolume :: Cuboid -> Int +cVolume (Cuboid (sx, sy, sz) (ex, ey, ez)) = vx * vy * vz + where vx = abs (sx - (ex + 1)) + vy = abs (sy - (ey + 1)) + vz = abs (sz - (ez + 1)) + +ccVolume :: ChargedCuboid -> Int +ccVolume c | charge c = cVolume (cuboid c) + | otherwise = -(cVolume (cuboid c)) + +cIntersection :: Cuboid -> Cuboid -> Cuboid +cIntersection c1@(Cuboid s1 e1) c2@(Cuboid s2 e2) | not $ intersects c1 c2 = nullCuboid + | otherwise = (Cuboid s' e') + where s' = map3 (uncurry max) (zip3t s1 s2) + e' = map3 (uncurry min) (zip3t e1 e2) + +data ChargedCuboid = ChargedCuboid { charge :: Bool + ,cuboid :: Cuboid + } deriving (Show, Eq) + +performCommand :: [ChargedCuboid] -> Command -> [ChargedCuboid] +performCommand cs (Command val c) | val = (ChargedCuboid val c) : (cs ++ overlaps) + | otherwise = cs ++ overlaps + where overlaps = filter (not . cEmpty . cuboid) $ map invertedIntersection cs + invertedIntersection cc = ChargedCuboid (not (charge cc)) ((cuboid cc) `cIntersection` c) + +nullCuboid :: Cuboid +nullCuboid = Cuboid (0, 0, 0) ((-1), (-1), (-1)) + +map3 :: (a -> b) -> (a, a, a) -> (b, b, b) +map3 f (a, b, c) = (f a, f b, f c) + +zip3t :: (a, a, a) -> (b, b, b) -> ((a, b), (a, b), (a, b)) +zip3t (x, y, z) (x', y', z') = ((x, x'), (y, y'), (z, z')) + +main = do + input <- readFile "./input" + let (Right cmds) = parse parseFile "input" input + + let cs = foldl performCommand [] cmds + let vol = foldr (+) 0 $ map ccVolume cs + print vol diff --git a/2021/day23/Setup.hs b/2021/day23/Setup.hs new file mode 100644 index 0000000..9a994af --- /dev/null +++ b/2021/day23/Setup.hs @@ -0,0 +1,2 @@ +import Distribution.Simple +main = defaultMain diff --git a/2021/day23/app/Main.hs b/2021/day23/app/Main.hs new file mode 100644 index 0000000..fbce993 --- /dev/null +++ b/2021/day23/app/Main.hs @@ -0,0 +1,138 @@ +{-# LANGUAGE OverloadedStrings #-} +{-# LANGUAGE TupleSections #-} +module Main where + +import Algorithm.Search (dijkstraAssoc) +import qualified Data.Text as T +import Data.Maybe (listToMaybe, catMaybes) +import Data.List (intercalate, transpose) +import Data.Char (isLetter) +import Data.Map (Map) +import qualified Data.Map as M +import Data.Set (Set) +import qualified Data.Set as S + +data Species = Am | Br | Co | De deriving (Show, Eq, Ord) +type Coord = (Int, Int) +type Board = Map Coord Species + +toSpecies :: Char -> Species +toSpecies 'A' = Am +toSpecies 'B' = Br +toSpecies 'C' = Co +toSpecies 'D' = De + +cost :: Species -> Int +cost Am = 1 +cost Br = 10 +cost Co = 100 +cost De = 1000 + +roomX :: Species -> Int +roomX Am = 1 +roomX Br = 3 +roomX Co = 5 +roomX De = 7 + +isRoomX :: Int -> Bool +isRoomX 1 = True +isRoomX 3 = True +isRoomX 5 = True +isRoomX 7 = True +isRoomX _ = False + +lowerBound = (-1) +upperBound = 9 +lowestY = 4 + +inBounds :: Coord -> Bool +inBounds (x, _) = x >= lowerBound && x <= upperBound + +parseFile :: String -> Board +parseFile s = foldl insertRoom M.empty rooms + where letters = transpose $ map (map toSpecies . filter isLetter . T.unpack) $ T.splitOn "\n" (T.pack s) + rooms = zip [Am, Br, Co, De] letters + insertRoom m (s, cs) = (M.fromList [((roomX s, y), c) | (y, c) <- zip [1..] cs]) `M.union` m + +topOfRoom :: Board -> Int -> Maybe Coord +topOfRoom b x = listToMaybe $ filter (`M.member` b) [(x, y) | y <- [1..lowestY]] + +availableHallwaySpaces :: Board -> Int -> [Coord] +availableHallwaySpaces b sx = (exploreWith (+ 1) sx) ++ (exploreWith (+ (-1)) (sx - 1)) + where exploreWith f x | isRoomX x = exploreWith f (f x) + | not (inBounds (x, 0)) = [] + | (x, 0) `M.member` b = [] + | otherwise = (x, 0) : exploreWith f (f x) + +pathToRoom :: Coord -> Species -> [Coord] +pathToRoom (sx, _) es | sx <= ex = map (, 0) [sx + 1..ex] + | otherwise = map (, 0) [ex..sx - 1] + where ex = roomX es + +pathClear :: Board -> [Coord] -> Bool +pathClear b path = all (`M.notMember` b) path + +toTopOfRoom :: Int -> Int +toTopOfRoom x = x - 1 + +movingFromRoom :: Board -> Species -> [(Board, Int)] +movingFromRoom b s = case topOfRoom b (roomX s) of + Just (x, y) -> let withoutTop = (x, y) `M.delete` b + extraCost = toTopOfRoom y + Just movingOut = (x, y) `M.lookup` b + in [(M.insert c movingOut withoutTop, (abs ((fst c) - x) + 1 + extraCost) * cost movingOut) | c <- availableHallwaySpaces b x] + Nothing -> [] + +roomPositions = [1..lowestY] + +movingIntoRoom :: Board -> [(Board, Int)] +movingIntoRoom b = concatMap attemptMoveToRoom [((c, 0), (c, 0) `M.lookup` b) | c <- [lowerBound..upperBound]] + where attemptMoveToRoom (_, Nothing) = [] + attemptMoveToRoom (c, Just s) | not clear = [] + | otherwise = [(b', (length p + 1 + extraCost) * (cost s))] + where p = pathToRoom c s + clear = pathClear b p && hasSpace && isCorrect + occupants = catMaybes [(roomX s, y) `M.lookup` b | y <- roomPositions] + hasSpace = length occupants < lowestY + isCorrect = all (== s) occupants + y' = lowestY - (length occupants) + extraCost = toTopOfRoom y' + c' = (roomX s, y') + b' = M.insert c' s $ M.delete c b + +species = [Am, Br, Co, De] + +nextMoves :: Board -> [(Board, Int)] +nextMoves b = (concatMap (movingFromRoom b) species) ++ movingIntoRoom b + +isFinished :: Board -> Bool +isFinished b = all id [(M.lookup (roomX s, rp) b) == Just s | s <- species, rp <- roomPositions] + +solve :: Board -> Maybe (Int, [Board]) +solve = dijkstraAssoc nextMoves isFinished + +printBoard :: Board -> String +printBoard b = intercalate "\n" [printLine l | l <- [0..lowestY]] + where printLine l = [toChar ((x, l) `M.lookup` b) | x <- [lowerBound..upperBound]] + toChar Nothing = ' ' + toChar (Just Am) = 'A' + toChar (Just Br) = 'B' + toChar (Just Co) = 'C' + toChar (Just De) = 'D' + +printNexts :: [(Board, Int)] -> IO [()] +printNexts = sequence . map printNext + +printNext :: (Board, Int) -> IO () +printNext (b, c) = do + putStrLn $ printBoard b + print c + +main :: IO () +main = do + input <- readFile "./input" + let parsed = parseFile input + let Just (cost, path) = solve parsed + putStrLn $ intercalate "\n---\n" $ map printBoard path + print path + print cost diff --git a/2021/day23/day23.cabal b/2021/day23/day23.cabal new file mode 100644 index 0000000..51b4ad5 --- /dev/null +++ b/2021/day23/day23.cabal @@ -0,0 +1,52 @@ +cabal-version: 1.12 + +-- This file has been generated from package.yaml by hpack version 0.34.5. +-- +-- see: https://github.com/sol/hpack + +name: day23 +version: 0.1.0.0 +description: Please see the README on GitHub at <https://github.com/githubuser/day23#readme> +homepage: https://github.com/githubuser/day23#readme +bug-reports: https://github.com/githubuser/day23/issues +author: Author name here +maintainer: example@example.com +copyright: 2021 Author name here +license: BSD3 +build-type: Simple +extra-source-files: + README.md + ChangeLog.md + +source-repository head + type: git + location: https://github.com/githubuser/day23 + +library + exposed-modules: + Lib + other-modules: + Paths_day23 + hs-source-dirs: + src + build-depends: + base >=4.7 && <5 + , containers + , search-algorithms + , text + default-language: Haskell2010 + +executable day23-exe + main-is: Main.hs + other-modules: + Paths_day23 + hs-source-dirs: + app + ghc-options: -threaded -rtsopts -with-rtsopts=-N + build-depends: + base >=4.7 && <5 + , containers + , day23 + , search-algorithms + , text + default-language: Haskell2010 diff --git a/2021/day23/package.yaml b/2021/day23/package.yaml new file mode 100644 index 0000000..a41ad1f --- /dev/null +++ b/2021/day23/package.yaml @@ -0,0 +1,40 @@ +name: day23 +version: 0.1.0.0 +github: "githubuser/day23" +license: BSD3 +author: "Author name here" +maintainer: "example@example.com" +copyright: "2021 Author name here" + +extra-source-files: +- README.md +- ChangeLog.md + +# Metadata used when publishing your package +# synopsis: Short description of your package +# category: Web + +# To avoid duplicated efforts in documentation and dealing with the +# complications of embedding Haddock markup inside cabal files, it is +# common to point users to the README.md file. +description: Please see the README on GitHub at <https://github.com/githubuser/day23#readme> + +dependencies: +- base >= 4.7 && < 5 +- containers +- text +- search-algorithms + +library: + source-dirs: src + +executables: + day23-exe: + main: Main.hs + source-dirs: app + ghc-options: + - -threaded + - -rtsopts + - -with-rtsopts=-N + dependencies: + - day23 diff --git a/2021/day23/src/Lib.hs b/2021/day23/src/Lib.hs new file mode 100644 index 0000000..d36ff27 --- /dev/null +++ b/2021/day23/src/Lib.hs @@ -0,0 +1,6 @@ +module Lib + ( someFunc + ) where + +someFunc :: IO () +someFunc = putStrLn "someFunc" diff --git a/2021/day23/stack.yaml b/2021/day23/stack.yaml new file mode 100644 index 0000000..920ab59 --- /dev/null +++ b/2021/day23/stack.yaml @@ -0,0 +1,68 @@ +# This file was automatically generated by 'stack init' +# +# Some commonly used options have been documented as comments in this file. +# For advanced use and comprehensive documentation of the format, please see: +# https://docs.haskellstack.org/en/stable/yaml_configuration/ + +# Resolver to choose a 'specific' stackage snapshot or a compiler version. +# A snapshot resolver dictates the compiler version and the set of packages +# to be used for project dependencies. For example: +# +# resolver: lts-3.5 +# resolver: nightly-2015-09-21 +# resolver: ghc-7.10.2 +# +# The location of a snapshot can be provided as a file or url. Stack assumes +# a snapshot provided as a file might change, whereas a url resource does not. +# +# resolver: ./custom-snapshot.yaml +# resolver: https://example.com/snapshots/2018-01-01.yaml +resolver: + url: https://raw.githubusercontent.com/commercialhaskell/stackage-snapshots/master/lts/18/20.yaml + +# User packages to be built. +# Various formats can be used as shown in the example below. +# +# packages: +# - some-directory +# - https://example.com/foo/bar/baz-0.0.2.tar.gz +# subdirs: +# - auto-update +# - wai +packages: +- . +# Dependency packages to be pulled from upstream that are not in the resolver. +# These entries can reference officially published versions as well as +# forks / in-progress versions pinned to a git hash. For example: +# +# extra-deps: +# - acme-missiles-0.3 +# - git: https://github.com/commercialhaskell/stack.git +# commit: e7b331f14bcffb8367cd58fbfc8b40ec7642100a +# +extra-deps: + - search-algorithms-0.3.2 + +# Override default flag values for local packages and extra-deps +# flags: {} + +# Extra package databases containing global packages +# extra-package-dbs: [] + +# Control whether we use the GHC we find on the path +# system-ghc: true +# +# Require a specific version of stack, using version ranges +# require-stack-version: -any # Default +# require-stack-version: ">=2.7" +# +# Override the architecture used by stack, especially useful on Windows +# arch: i386 +# arch: x86_64 +# +# Extra directories used by stack for building +# extra-include-dirs: [/path/to/dir] +# extra-lib-dirs: [/path/to/dir] +# +# Allow a newer minor version of GHC than the snapshot specifies +# compiler-check: newer-minor diff --git a/2021/day23/stack.yaml.lock b/2021/day23/stack.yaml.lock new file mode 100644 index 0000000..1f94557 --- /dev/null +++ b/2021/day23/stack.yaml.lock @@ -0,0 +1,20 @@ +# This file was autogenerated by Stack. +# You should not edit this file by hand. +# For more information, please see the documentation at: +# https://docs.haskellstack.org/en/stable/lock_files + +packages: +- completed: + hackage: search-algorithms-0.3.2@sha256:9d224b9c6b5875598e6fc91497a178f3ca6e45768c637d07d4f874e6211a331b,2203 + pantry-tree: + size: 557 + sha256: 43e9d4344d57a3bad78f67d085156531e0a9b38a14dce9f5137940561fdb3582 + original: + hackage: search-algorithms-0.3.2 +snapshots: +- completed: + size: 586106 + url: https://raw.githubusercontent.com/commercialhaskell/stackage-snapshots/master/lts/18/20.yaml + sha256: 8699812d2b2c1f83d6ad1261de9cf628ed36a1cfc14f19d67188e005e7a3a39d + original: + url: https://raw.githubusercontent.com/commercialhaskell/stackage-snapshots/master/lts/18/20.yaml diff --git a/2021/day24/24_convert.py b/2021/day24/24_convert.py new file mode 100644 index 0000000..c538e1b --- /dev/null +++ b/2021/day24/24_convert.py @@ -0,0 +1,27 @@ +# Converts input to a .dzn file +# Usage: python 24_convert.py | minizinc 24a.mzn - + +cmds = open("./input").read().strip().split("\n") + +def convert_ops(cmds): + for c in cmds: + yield "i_" + c.split(" ")[0] + +def convert_arg(a): + cons = "R" if a in {"x", "y", "z", "w"} else "Imm" + return "%s(%s)" % (cons, a) + +def convert_args(cmds): + for c in cmds: + spl = c.split(" ")[1:] + if len(spl) == 1: + yield (convert_arg(spl[0]), "None") + else: + yield (convert_arg(spl[0]), convert_arg(spl[1])) + + +inp_ops = list(convert_ops(cmds)) +inp_args = list(convert_args(cmds)) + +print("inp_ops = [ %s ];" % ", ".join(inp_ops)) +print("inp_args = [| %s |];" % "|".join([",".join(x) for x in inp_args])) diff --git a/2021/day24/24a.mzn b/2021/day24/24a.mzn new file mode 100644 index 0000000..4ad0d82 --- /dev/null +++ b/2021/day24/24a.mzn @@ -0,0 +1,117 @@ +include "globals.mzn"; + +% Types +enum Operation = { + i_inp, + i_add, + i_mul, + i_div, + i_mod, + i_eql +}; +enum Pos = { Arg1, Arg2 }; +enum Arg = R(Registers) ++ Imm(Immediates) ++ { None }; + +enum Registers = {x, y, z, w}; + +set of int: Immediates = -127..127; +set of int: Digits = 0..9; + +% Input +array[int] of Operation: inp_ops; +array[int, Pos] of Arg: inp_args; + +% Properties derived from input +set of int: Steps = index_set(inp_ops); +set of int: Inputs = 1..count(inp_ops, i_inp); + +set of int: ExtendedSteps = min(Steps)..max(Steps) + 1; +set of int: ExtendedInputs = min(Inputs)..max(Inputs) + 1; + +% State +array[ExtendedSteps, Registers] of var int: regs; +array[Inputs] of var Digits: inputs; + +% Everything is 0 to start with +constraint forall (r in Registers) ( + regs[min(Steps), r] = 0 +); + +% All registers unaffected by the instruction at a given step +function set of Registers: unaffected(Steps: step) = { + r | r in Registers where R(r) != inp_args[step, Arg1] +}; + +% The argument at pos addressed by the instruction at i_step, pointing to the registers at r_step +function var int: arg(Steps: i_step, ExtendedSteps: r_step, Pos: pos) = + if inp_args[i_step, pos] in R(Registers) then + regs[r_step, R^-1(inp_args[i_step, pos])] + elseif inp_args[i_step, pos] in Imm(Immediates) then + Imm^-1(inp_args[i_step, pos]) + else + assert(false, "no value for argument of instruction at step") + endif; + +% Where to write the result of an instruction +function var int: writearg(Steps: step) = arg(step, step + 1, Arg1); + +% Read the argument at pos of instruction at step +function var int: readarg(Steps: step, Pos: pos) = arg(step, step, pos); + +predicate interpret(Steps: step, ExtendedInputs: next_input) = ( + % Constrain state based on instruction at step + if inp_ops[step] = i_inp then + writearg(step) = inputs[next_input] + else + let { + Operation: o = inp_ops[step], + var int: a = readarg(step, Arg1), + var int: b = readarg(step, Arg2), + var int: x = writearg(step), + } in + if o = i_add then + x = a + b + elseif o = i_mul then + x = a * b + elseif o = i_div then + b != 0 /\ + x * b = a - (a mod b) + elseif o = i_mod then + a >= 0 /\ + b > 0 /\ + x = a mod b + elseif o = i_eql then + x = (a = b) + else + assert(false, "unimplemented instruction at ") + endif + endif /\ + % Leave the rest unchanged + forall (r in unaffected(step)) ( + regs[step + 1, r] = regs[step, r] + ) /\ + % Perform induction + if step + 1 in Steps then + interpret(step + 1, next_input + (inp_ops[step] = i_inp)) + else + true + endif +); + +constraint interpret(min(Steps), min(Inputs)); + +% Finish with z = 0 +constraint regs[max(ExtendedSteps), z] = 0; + +% No 0s in serial number +constraint forall (i in Inputs) ( + inputs[i] != 0 +); + +% Find the largest first +solve :: int_search(inputs, input_order, indomain_max) satisfy; + +output [ + "inputs: ", show(inputs), "\n", + "final registers: ", show(regs[max(ExtendedSteps), ..]), "\n", +];
\ No newline at end of file diff --git a/2021/day24/24b.mzn b/2021/day24/24b.mzn new file mode 100644 index 0000000..2e8a9a4 --- /dev/null +++ b/2021/day24/24b.mzn @@ -0,0 +1,117 @@ +include "globals.mzn"; + +% Types +enum Operation = { + i_inp, + i_add, + i_mul, + i_div, + i_mod, + i_eql +}; +enum Pos = { Arg1, Arg2 }; +enum Arg = R(Registers) ++ Imm(Immediates) ++ { None }; + +enum Registers = {x, y, z, w}; + +set of int: Immediates = -127..127; +set of int: Digits = 0..9; + +% Input +array[int] of Operation: inp_ops; +array[int, Pos] of Arg: inp_args; + +% Properties derived from input +set of int: Steps = index_set(inp_ops); +set of int: Inputs = 1..count(inp_ops, i_inp); + +set of int: ExtendedSteps = min(Steps)..max(Steps) + 1; +set of int: ExtendedInputs = min(Inputs)..max(Inputs) + 1; + +% State +array[ExtendedSteps, Registers] of var int: regs; +array[Inputs] of var Digits: inputs; + +% Everything is 0 to start with +constraint forall (r in Registers) ( + regs[min(Steps), r] = 0 +); + +% All registers unaffected by the instruction at a given step +function set of Registers: unaffected(Steps: step) = { + r | r in Registers where R(r) != inp_args[step, Arg1] +}; + +% The argument at pos addressed by the instruction at i_step, pointing to the registers at r_step +function var int: arg(Steps: i_step, ExtendedSteps: r_step, Pos: pos) = + if inp_args[i_step, pos] in R(Registers) then + regs[r_step, R^-1(inp_args[i_step, pos])] + elseif inp_args[i_step, pos] in Imm(Immediates) then + Imm^-1(inp_args[i_step, pos]) + else + assert(false, "no value for argument of instruction at step") + endif; + +% Where to write the result of an instruction +function var int: writearg(Steps: step) = arg(step, step + 1, Arg1); + +% Read the argument at pos of instruction at step +function var int: readarg(Steps: step, Pos: pos) = arg(step, step, pos); + +predicate interpret(Steps: step, ExtendedInputs: next_input) = ( + % Constrain state based on instruction at step + if inp_ops[step] = i_inp then + writearg(step) = inputs[next_input] + else + let { + Operation: o = inp_ops[step], + var int: a = readarg(step, Arg1), + var int: b = readarg(step, Arg2), + var int: x = writearg(step), + } in + if o = i_add then + x = a + b + elseif o = i_mul then + x = a * b + elseif o = i_div then + b != 0 /\ + x * b = a - (a mod b) + elseif o = i_mod then + a >= 0 /\ + b > 0 /\ + x = a mod b + elseif o = i_eql then + x = (a = b) + else + assert(false, "unimplemented instruction at ") + endif + endif /\ + % Leave the rest unchanged + forall (r in unaffected(step)) ( + regs[step + 1, r] = regs[step, r] + ) /\ + % Perform induction + if step + 1 in Steps then + interpret(step + 1, next_input + (inp_ops[step] = i_inp)) + else + true + endif +); + +constraint interpret(min(Steps), min(Inputs)); + +% Finish with z = 0 +constraint regs[max(ExtendedSteps), z] = 0; + +% No 0s in serial number +constraint forall (i in Inputs) ( + inputs[i] != 0 +); + +% Find the largest first +solve :: int_search(inputs, input_order, indomain_min) satisfy; + +output [ + "inputs: ", show(inputs), "\n", + "final registers: ", show(regs[max(ExtendedSteps), ..]), "\n", +];
\ No newline at end of file diff --git a/2021/day25/25a.hs b/2021/day25/25a.hs new file mode 100644 index 0000000..6f0cf1a --- /dev/null +++ b/2021/day25/25a.hs @@ -0,0 +1,87 @@ +module Main where + +import Data.List (intercalate) +import Data.Maybe (fromMaybe) +import Data.Set (Set) +import qualified Data.Set as S + +data Direction = East | South deriving (Show, Eq, Ord) + +type Coord = (Int, Int) + +type Board = Set (Coord, Direction) + +spaceFilled :: Board -> Coord -> Bool +spaceFilled b c = S.member (c, East) b || S.member (c, South) b + +getDirection :: Board -> Coord -> Direction +getDirection b c + | (c, East) `S.member` b = East + | (c, South) `S.member` b = South + | otherwise = undefined + +wrapAround :: Board -> Coord -> Coord +wrapAround b (x, y) = (x', y') + where + x' = if x > mx then 0 else x + y' = if y > my then 0 else y + mx = 138 + my = 136 + +stepOne :: Board -> (Coord, Direction) -> (Coord, Direction) +stepOne b (c@(x, y), d) = (if canMove then newCoord else c, d) + where + newCoord = case d of + East -> wrapAround b (x + 1, y) + South -> wrapAround b (x, y + 1) + canMove = not $ spaceFilled b newCoord + +stepAll :: Board -> Board +stepAll ib = S.map (stepSouth eastStepped) eastStepped + where + eastStepped = S.map (stepEast ib) ib + stepEast b x@(_, East) = stepOne b x + stepEast b x = x + stepSouth b x@(_, South) = stepOne b x + stepSouth b x = x + +stepTillStationary :: Board -> (Board, Int) +stepTillStationary ib = keepStepping ib 0 + where + keepStepping b n + | b == b' = (b, n + 1) + | otherwise = keepStepping b' (n + 1) + where + b' = stepAll b + +parseFile :: String -> Board +parseFile str = S.fromList $ getFilled str 0 0 + where + getFilled [] x y = [] + getFilled ('.' : cs) x y = getFilled cs (x + 1) y + getFilled ('\n' : cs) x y = getFilled cs 0 (y + 1) + getFilled ('>' : cs) x y = ((x, y), East) : getFilled cs (x + 1) y + getFilled ('v' : cs) x y = ((x, y), South) : getFilled cs (x + 1) y + getFilled (_ : cs) x y = undefined + +printBoard :: Board -> String +printBoard b = intercalate "\n" $ map printLine [0 .. 10] + where + printLine y = map (printCell y) [0 .. 10] + printCell y x + | spaceFilled b (x, y) = case getDirection b (x, y) of + East -> '>' + South -> 'v' + | otherwise = '.' + +main :: IO () +main = do + input <- readFile "./input" + let parsed = parseFile input + print $ fromMaybe 0 $ S.lookupMax $ S.map (fst . fst) parsed + print $ fromMaybe 0 $ S.lookupMax $ S.map (snd . fst) parsed + -- putStrLn $ printBoard parsed + -- putStrLn "---" + -- putStrLn $ printBoard $ foldr (\x b -> stepAll b) parsed [0 .. 0] + + print $ snd $ stepTillStationary parsed
\ No newline at end of file diff --git a/2021/day3/03a.rkt b/2021/day3/03a.rkt new file mode 100644 index 0000000..bb42d83 --- /dev/null +++ b/2021/day3/03a.rkt @@ -0,0 +1,30 @@ +#lang racket +(define (mode xs) + (define ht (make-hash)) + (define max-key '0) + (for ([x xs]) + (define new-val (+ 1 (hash-ref ht x 0))) + (hash-set! ht x new-val) + (if (> new-val (hash-ref ht max-key 0)) (set! max-key x) 3)) + max-key) + +(define (transpose xss) + (apply map list xss)) + +(define (flip x) + (cond [(string=? x "0") "1"] + [else "0"])) + +(define input (open-input-file "input")) +(define bit-positions + (transpose (map (lambda (xs) + (map (curry make-string 1) (string->list xs))) + (port->lines input)))) + +(define gamma-str (foldr string-append "" (map mode bit-positions))) +(define epsilon-str (foldr string-append "" (map (compose flip mode) bit-positions))) + +(define gamma (string->number gamma-str 2)) +(define epsilon (string->number epsilon-str 2)) + +(* gamma epsilon) diff --git a/2021/day3/03b.rkt b/2021/day3/03b.rkt new file mode 100644 index 0000000..aea9c86 --- /dev/null +++ b/2021/day3/03b.rkt @@ -0,0 +1,35 @@ +#lang racket + +(define (mode xs) + (define ht (make-hash)) + (define max-key '0) + (for ([x xs]) + (define new-val (+ 1 (hash-ref ht x 0))) + (hash-set! ht x new-val) + (if (> new-val (hash-ref ht max-key 0)) (set! max-key x) 3)) + (cond [(= (hash-ref ht #\0 0) (hash-ref ht #\1 0)) #f] + [else max-key])) + +(define (flip x) + (cond [(char=? x #\0) #\1] + [else #\0])) + +(define (bit-criteria lines least [fallback (cond [least #\0] [else #\1])] [n 0]) + (cond [(= (length lines) 1) (car lines)] + [else + (define bits (map (curryr string-ref n) lines)) + (define bMode (mode bits)) + (define criteria (cond [(not bMode) fallback] + [least (flip bMode)] + [else bMode])) + (bit-criteria (filter (lambda (x) (char=? criteria (string-ref x n))) + lines) + least fallback (+ n 1))])) + +(define input (open-input-file "input")) +(define lines (port->lines input)) + +(define oxy (string->number (bit-criteria lines #f) 2)) +(define co2 (string->number (bit-criteria lines #t) 2)) + +(* oxy co2) diff --git a/2021/day4/04a-alt.rkt b/2021/day4/04a-alt.rkt new file mode 100644 index 0000000..db03881 --- /dev/null +++ b/2021/day4/04a-alt.rkt @@ -0,0 +1,49 @@ +#lang racket + +(require racket/file) + +(define (parse-row x) + (map string->number (filter (lambda (x) (< 0 (string-length x))) (regexp-split #rx" +" x)))) + +(define (parse-board x) + (map parse-row (string-split x "\n"))) + +(define (get-numbers x) + (define number-line (car (string-split x "\n\n"))) + (map string->number (string-split number-line ","))) + +(define (get-boards x) + (define boards (cdr (string-split x "\n\n"))) + (map parse-board boards)) + +(define (subsetOf xs ys) + (subset? (list->set xs) (list->set ys))) + +(define (transpose xs) + (apply map list xs)) + +(define (check-win board numbers) + (define winningColumns (filter (lambda (x) (subsetOf x numbers)) board)) + (define winningRows (filter (lambda (x) (subsetOf x numbers)) (transpose board))) + (cond [(not (null? winningColumns)) (car winningColumns)] + [(not (null? winningRows)) (car winningRows)] + [else #f])) + +(define input (file->string "./input")) +(define numbers (get-numbers input)) +(define boards (get-boards input)) + +(define winningBoard #f) +(define winningRun #f) +(define wonOnRound 0) +(for* ([rnd (length numbers)] + [board boards] + #:unless winningRun + ) + (set! winningRun (check-win board (take numbers rnd))) + (set! winningBoard board) + (set! wonOnRound rnd)) + +(* + (foldr + 0 (filter (lambda (x) (not (member x (take numbers wonOnRound)))) (flatten winningBoard))) + (list-ref numbers (- wonOnRound 1))) diff --git a/2021/day4/04b-alt.rkt b/2021/day4/04b-alt.rkt new file mode 100644 index 0000000..ab32bc2 --- /dev/null +++ b/2021/day4/04b-alt.rkt @@ -0,0 +1,49 @@ +#lang racket + +(require racket/file) + +(define (parse-row x) + (map string->number (filter (lambda (x) (< 0 (string-length x))) (regexp-split #rx" +" x)))) + +(define (parse-board x) + (map parse-row (string-split x "\n"))) + +(define (get-numbers x) + (define number-line (car (string-split x "\n\n"))) + (map string->number (string-split number-line ","))) + +(define (get-boards x) + (define boards (cdr (string-split x "\n\n"))) + (map parse-board boards)) + +(define (subsetOf xs ys) + (subset? (list->set xs) (list->set ys))) + +(define (transpose xs) + (apply map list xs)) + +(define (check-win board numbers) + (define winningColumns (filter (lambda (x) (subsetOf x numbers)) board)) + (define winningRows (filter (lambda (x) (subsetOf x numbers)) (transpose board))) + (cond [(not (null? winningColumns)) (car winningColumns)] + [(not (null? winningRows)) (car winningRows)] + [else #f])) + +(define input (file->string "./input")) +(define numbers (get-numbers input)) +(define boards (get-boards input)) + +(define ht (make-hash)) +(for* ([rnd (length numbers)] + [board boards] + #:unless (hash-ref ht board #f) + ) + (cond [(check-win board (take numbers rnd)) (hash-set! ht board rnd)])) + +(define maxTurn 0) +(define lastBoard #f) +(hash-for-each ht (lambda (k v) (cond [(> v maxTurn) (set! maxTurn v) (set! lastBoard k)]))) + +(* + (foldr + 0 (filter (lambda (x) (not (member x (take numbers maxTurn)))) (flatten lastBoard))) + (list-ref numbers (- maxTurn 1))) diff --git a/2021/day4/04t.rkt b/2021/day4/04t.rkt new file mode 100644 index 0000000..b3f10ad --- /dev/null +++ b/2021/day4/04t.rkt @@ -0,0 +1,9 @@ +#lang reader "reader.rkt" +7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1 + +22 13 17 11 0 + 8 2 23 4 24 +21 9 14 16 7 + 6 10 3 18 5 +1 12 20 15 19 + diff --git a/2021/day4/parser.rkt b/2021/day4/parser.rkt new file mode 100644 index 0000000..449d886 --- /dev/null +++ b/2021/day4/parser.rkt @@ -0,0 +1,8 @@ +#lang brag +file: numbers "\n" "\n" boards +numbers: number ("," number)* +number: digit+ +digit: "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" +boards: board ("\n" board)* +board: row "\n" row "\n" row "\n" row "\n" row "\n" +row: " "+ number " "+ number " "+ number " "+ number " "+ number diff --git a/2021/day4/reader.rkt b/2021/day4/reader.rkt new file mode 100644 index 0000000..b777f92 --- /dev/null +++ b/2021/day4/reader.rkt @@ -0,0 +1,21 @@ +#lang racket + +(require "parser.rkt") +(require brag/support) + +(define (make-tokenizer port) + (define (next-token) + (define bf-lexer + (lexer + [(char-set "\n1234567890, ") lexeme] + [any-char (next-token)])) + (bf-lexer port)) + next-token) + +(define (read-syntax path port) + (define parse-tree (parse path (make-tokenizer port))) + (define module-datum `(module day4 racket + ,parse-tree)) + (datum->syntax #f module-datum)) + +(provide read-syntax) diff --git a/2021/day5/05a.rkt b/2021/day5/05a.rkt new file mode 100644 index 0000000..c24cb49 --- /dev/null +++ b/2021/day5/05a.rkt @@ -0,0 +1,36 @@ +#lang racket + +(require "./05a_grammar.rkt") + +(define ventCounts (make-hash)) + +(define (digit x) + x) + +(define (number . DIGITS) + (string->number (foldr string-append "" DIGITS))) + +(define (coord a _a b) + (list a b)) + +(define (line c1 _b _c _d _e c2) + (define steps (max (abs (- (car c2) (car c1))) + (abs (- (second c2) (second c1))))) + (define mx (/ (- (car c2) (car c1)) steps)) + (define my (/ (- (second c2) (second c1)) steps)) + (cond [(or (= 0 mx) (= 0 my)) (for ([s (+ 1 steps)]) + (define v (list (+ (car c1) (* mx s)) (+ (second c1) (* my s)))) + (hash-set! ventCounts v (+ 1 (hash-ref ventCounts v 0))))] + [else 0])) + + +(define (vents l _a . ls) + (cond [(null? ls) l] + [else (cons l (apply vents ls))])) + +(define-namespace-anchor anc) +(define ns (namespace-anchor->namespace anc)) +(define parsed (parse-to-datum (file->string "./input"))) +(void (eval parsed ns)) + +(length (filter (curry <= 2) (hash-values ventCounts))) diff --git a/2021/day5/05a_grammar.rkt b/2021/day5/05a_grammar.rkt new file mode 100644 index 0000000..cc78e6a --- /dev/null +++ b/2021/day5/05a_grammar.rkt @@ -0,0 +1,6 @@ +#lang brag +vents: (line "\n")* ["\n"] +line: coord " " "-" ">" " " coord +coord: number "," number +number: digit* +digit: "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" diff --git a/2021/day5/05b.rkt b/2021/day5/05b.rkt new file mode 100644 index 0000000..25d6fd6 --- /dev/null +++ b/2021/day5/05b.rkt @@ -0,0 +1,39 @@ +#lang racket + +(require "./05a_grammar.rkt") + +(define ventCounts (make-hash)) + +(define (digit x) + x) + +(define (number . DIGITS) + (string->number (foldr string-append "" DIGITS))) + +(define (coord a _a b) + (list a b)) + +(define (line c1 _b _c _d _e c2) + (define steps (max (abs (- (car c2) (car c1))) + (abs (- (second c2) (second c1))))) + (define mx (/ (- (car c2) (car c1)) steps)) + (define my (/ (- (second c2) (second c1)) steps)) + (for ([s (+ 1 steps)]) + (define v (list (+ (car c1) (* mx s)) (+ (second c1) (* my s)))) + (hash-set! ventCounts v (+ 1 (hash-ref ventCounts v 0))))) + +(define (vents l _a . ls) + (cond [(null? ls) l] + [else (cons l (apply vents ls))])) + +(define (print-board ex ey) + (for ([y ey]) + (for ([x ex]) + (display (hash-ref ventCounts (list x y) "."))) + (display "\n"))) + +(define-namespace-anchor anc) +(define ns (namespace-anchor->namespace anc)) +(define parsed (parse-to-datum (file->string "./input"))) +(void (eval parsed ns)) +(length (filter (curry <= 2) (hash-values ventCounts))) diff --git a/2021/day6/06.clj b/2021/day6/06.clj new file mode 100644 index 0000000..9531425 --- /dev/null +++ b/2021/day6/06.clj @@ -0,0 +1,30 @@ +(ns day-6) + +(require '[clojure.string :as str]) + +(defn add-fish [h days count] + (assoc h days (+ count (or (h days) 0)))) + +(defn simulate-fish [h [days count]] + (if (= 0 days) (-> (add-fish h 6 count) + (add-fish 8 count)) + (add-fish h (- days 1) count))) + +(defn simulate-fishes [h] + (reduce simulate-fish {} h)) + +(def input (as-> (slurp "./input") x + (str/split x #",") + (map str/trim x) + (map #(. Integer parseInt %) x))) + +(def inputMap (reduce (fn [acc days] (add-fish acc days 1)) {} input)) + +(def resultA (reduce (fn [acc _] (simulate-fishes acc)) inputMap (range 80))) +(def resultB (reduce (fn [acc _] (simulate-fishes acc)) inputMap (range 256))) + +(def countA (reduce (fn [acc [_ count]] (+ acc count)) 0 resultA)) +(def countB (reduce (fn [acc [_ count]] (+ acc count)) 0 resultB)) + +(println countA) +(println countB) diff --git a/2021/day7/07a.clj b/2021/day7/07a.clj new file mode 100644 index 0000000..d9cb0f7 --- /dev/null +++ b/2021/day7/07a.clj @@ -0,0 +1,19 @@ +(ns day-7) + +(require '[clojure.string :as str]) + +(defn totalDelta [xs dst] + (reduce + (map (fn [x] (Math/abs ^int (- x dst))) xs))) + +(defn calcIdealPos [xs start] + (def thisDelta (totalDelta xs start)) + (def nextDelta (totalDelta xs (+ 1 start))) + (cond (> nextDelta thisDelta) start + :else (calcIdealDst xs (+ 1 start)))) + +(def input (as-> (slurp "./input") x + (str/split x #",") + (map str/trim x) + (map #(. Integer parseInt %) x))) + +(totalDelta input (calcIdealPos input (apply min input))) diff --git a/2021/day7/07b.clj b/2021/day7/07b.clj new file mode 100644 index 0000000..9e248c8 --- /dev/null +++ b/2021/day7/07b.clj @@ -0,0 +1,22 @@ +(ns day-7) + +(require '[clojure.string :as str]) + +(defn fuelCost [x] + (/ (* x (+ 1 x)) 2)) + +(defn totalDelta [xs dst] + (reduce + (map (fn [x] (fuelCost (Math/abs ^int (- x dst)))) xs))) + +(defn calcIdealPos [xs start] + (def thisDelta (totalDelta xs start)) + (def nextDelta (totalDelta xs (+ 1 start))) + (cond (> nextDelta thisDelta) start + :else (calcIdealDst xs (+ 1 start)))) + +(def input (as-> (slurp "./input") x + (str/split x #",") + (map str/trim x) + (map #(. Integer parseInt %) x))) + +(totalDelta input (calcIdealPos input (apply min input))) diff --git a/2021/day8/08a.clj b/2021/day8/08a.clj new file mode 100644 index 0000000..dc261e5 --- /dev/null +++ b/2021/day8/08a.clj @@ -0,0 +1,12 @@ +(ns day-8) + +(require '[clojure.string :as str]) + +(def input (as-> (slurp "./input") x + (str/split x #"\n") + (map (fn [l] + (map (fn [p] (str/split (str/trim p) #" ")) (str/split l #"\|"))) x))) + +(def onlyOutputs (flatten (map second input))) +(def knownDigits (filter (fn [xs] (contains? (set '(2 4 3 7)) (count xs))) onlyOutputs)) +(println (count knownDigits)) diff --git a/2021/day8/08b.clj b/2021/day8/08b.clj new file mode 100644 index 0000000..067f802 --- /dev/null +++ b/2021/day8/08b.clj @@ -0,0 +1,69 @@ +(ns day-8) + +(require '[clojure.string :as str]) +(require '[clojure.set :as set]) + +(def ALPHABET #{\a \b \c \d \e \f \g}) +(defn decodeWith [signal mapping] + (cond (every? (fn [x] (contains? mapping x)) signal) (set (map (fn [x] (get mapping x)) signal)) + :else false)) + +(def SIGNAL_TO_NUM {#{\a \b \c \e \f \g} 0 + #{\c \f} 1 + #{\a \c \d \e \g} 2 + #{\a \c \d \f \g} 3 + #{\b \c \d \f} 4 + #{\a \b \d \f \g} 5 + #{\a \b \d \e \f \g} 6 + #{\a \c \f} 7 + #{\a \b \c \d \e \f \g} 8 + #{\a \b \c \d \f \g} 9}) + +(defn decodedArrToNum [arr] + (reduce + (map-indexed (fn [idx sig] (* (Math/pow 10 (- (count arr) idx 1)) (SIGNAL_TO_NUM sig))) arr))) + +; characters that haven't been mapped (ie the mapping doesnt specify what they actually should be) +(defn unmappedChars [mapping] + (set/difference ALPHABET (keys mapping))) + +; characters that haven't been used (ie there is no character in the mapping that results in them) +(defn unusedChars [mapping] + (set/difference ALPHABET (vals mapping))) + +(defn validResult [x] + (contains? #{#{\a \b \c \e \f \g} #{\c \f} #{\a \c \d \e \g} #{\a \c \d \f \g} #{\b \c \d \f} #{\a \b \d \f \g} #{\a \b \d \e \f \g}#{\a \c \f} #{\a \b \c \d \e \f \g} #{\a \b \c \d \f \g}} x)) + +(defn tryWith [signals mapping knownValues] + (cond + (not (every? (fn [[in expected]] + (def attemptedDecode (decodeWith in mapping)) + (or (= false attemptedDecode) (= expected attemptedDecode))) + knownValues)) false ; stop considering path if it breaks any known values + (not (every? (fn [in] + (def attemptedDecode (decodeWith in mapping)) + (or (= false attemptedDecode) (validResult attemptedDecode))) + signals)) false ; stop when any of the fully resolved signals are invalid + (every? validResult (map (fn [x] (decodeWith x mapping)) signals)) mapping ; base case - all resolved to valid values + :else (let [tryingToMap (first (unmappedChars mapping))] + (first (filter (comp true? boolean) (for [candidate (unusedChars mapping)] + (do + (tryWith signals (assoc mapping tryingToMap candidate) knownValues)))))))) + +(def KNOWN_VALUES {2 #{\c \f} 4 #{\b \c \d \f} 3 #{\a \c \f} 7 #{\a \b \c \d \e \f \g}}) + +(defn extractKnownValues [signals] + (reduce (fn [m s] (cond (contains? KNOWN_VALUES (count s)) (assoc m s (get KNOWN_VALUES (count s))) + :else m)) {} signals)) + +(def input (as-> (slurp "./input") x + (str/split x #"\n") + (map (fn [l] + (map (fn [p] (map set (str/split (str/trim p) #" "))) (str/split l #"\|"))) x))) + +(def lineMappings (map (fn [l] (let [signals (set (flatten l))] + (tryWith signals {} (extractKnownValues signals)))) input)) +(def decodedOutputs (map (fn [l m] (let [signals (second l)] + (map (fn [x] (decodeWith x m)) signals))) input lineMappings)) +(def outputs (map decodedArrToNum decodedOutputs)) + +(println (reduce + outputs)) diff --git a/2021/day9/09.cpp b/2021/day9/09.cpp new file mode 100644 index 0000000..5026a77 --- /dev/null +++ b/2021/day9/09.cpp @@ -0,0 +1,154 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <cerrno> +#include <vector> +#include <set> +#include <queue> +#include <algorithm> + +using namespace std; + +std::string get_file_contents(const char *filename) +{ + std::ifstream in(filename, std::ios::in | std::ios::binary); + if (!in) + { + throw(errno); + } + + std::string contents; + in.seekg(0, std::ios::end); + contents.resize(in.tellg()); + in.seekg(0, std::ios::beg); + + in.read(&contents[0], contents.size()); + in.close(); + return contents; +} + +using heightmap_t = vector<vector<int>>; + +heightmap_t parse_height_map(const char* input, int len){ + vector<vector<int>> output; + vector<int> currRow; + for (int i = 0; i < len; i++) { + if (input[i] == '\n') { + output.push_back(currRow); + currRow = vector<int>(); + } else { + currRow.push_back(input[i] - '0'); + } + } + if (currRow.size() > 0) { + output.push_back(currRow); + } + + return output; +} + +bool isLowPoint(const heightmap_t &heightmap, int x, int y) { + int point = heightmap[y][x]; + for (int dx = -1; dx < 2; dx++) { + for (int dy = -1; dy < 2; dy++) { + int checkX = x + dx; + int checkY = y + dy; + if ((checkX == x && checkY == y) || + checkX < 0 || checkY < 0 || + checkY >= heightmap.size() || checkX >= heightmap[checkY].size()) + continue; + if (heightmap[checkY][checkX] <= point) { + return false; + } + } + } + return true; +} + +struct coord { + int x; + int y; + + + coord(int x, int y) { + this->x = x; + this->y = y; + } + + int hash() const { + return this->x << 16 | this->y; + } + + bool operator==(const coord &a) const { + return a.x == x && a.y == y; + } + + bool operator<(const coord &a) const { + return this->hash() < a.hash(); + } +}; + +int findBasinSize(const heightmap_t &heightmap, int startX, int startY) { + set<coord> visited; + queue<coord> queue; + queue.emplace(startX, startY); + + int totalSize = 0; + while(!queue.empty()) { + int x = queue.front().x; + int y = queue.front().y; + queue.pop(); + if (x < 0 || y < 0 || y >= heightmap.size() || x >= heightmap[y].size() || heightmap[y][x] == 9 || visited.count({x, y})) { + continue; + } + + totalSize++; + visited.insert({x, y}); + + for (int dx = -1; dx < 2; dx++) { + for (int dy = -1; dy < 2; dy++) { + int checkX = x + dx; + int checkY = y + dy; + if (dx != 0 && dy != 0) // dont allow diagonals / {x, y} + continue; + queue.emplace(checkX, checkY); + } + } + } + + return totalSize; +} + +int main() { + std::string input = get_file_contents("input"); + auto heightmap = parse_height_map(input.c_str(), input.length()); + + int lowPointCount = 0; + int totalRisk = 0; + int topBasins[] = {0, 0, 0}; + for (int y = 0; y < heightmap.size(); y++) { + for (int x = 0; x < heightmap[y].size(); x++) { + if (isLowPoint(heightmap, x, y)) { + lowPointCount++; + totalRisk += heightmap[y][x] + 1; + + int basinSize = findBasinSize(heightmap, x, y); + for (int i = 0; i < 3; i++) { + if (topBasins[i] < basinSize) { + topBasins[i] = basinSize; + break; + } + } + sort(topBasins, topBasins + 3); + } + } + } + + int acc = 1; + for (int i = 0; i < 3; i++) { + acc *= topBasins[i]; + } + printf("Total low points: %d\n", lowPointCount); + printf("Total risk: %d\n", totalRisk); + printf("Part B answer: %d\n", acc); +} diff --git a/2021/shell.nix b/2021/shell.nix new file mode 100644 index 0000000..9e6b4cb --- /dev/null +++ b/2021/shell.nix @@ -0,0 +1,35 @@ +{ pkgs ? import <nixpkgs> {} }: + +pkgs.mkShell { + buildInputs = with pkgs; [ + emacs + (haskellPackages.ghcWithPackages (p: [ + p.linear + p.parsec + ])) + python3 + stack + racket + clojure + leiningen + (minizinc.overrideAttrs (old: let rev = "adaa07456233d9ffe0a1f848917dde41e8c54710"; in { + version = "develop-${rev}"; + src = pkgs.fetchFromGitHub { + owner = "MiniZinc"; + repo = "libminizinc"; + + rev = rev; + sha256 = "sha256-t5/reUj38cc3H7CE1iPWgYD9m+190E5ihFHhft8+Bns="; + }; + })) + (gecode.overrideAttrs (old: let rev = "fec7e9fd99bca98f146416ba8ea8adc278f5a95a"; in { + version = "develop-${rev}"; + src = pkgs.fetchFromGitHub { + owner = "Gecode"; + repo = "gecode"; + sha256 = "sha256-HiYO74RnxY6ga7uppjR3DXMFOgE/8Gs0dvi86qUQcjo="; + rev = rev; + }; + })) + ]; +} |