Day 14: Restroom Redoubt
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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
2 points
*
Nim
Part 1: there’s no need to simulate each step, final position for each robot is
(position + velocity * iterations) modulo grid
Part 2: I solved it interactively: Maybe I just got lucky, but my input has certain pattern: after 99th iteration every 101st iteration looking very different from other. I printed first couple hundred iterations, noticed a pattern and started looking only at “interesting” grids. It took 7371 iterations (I only had to check 72 manually) to reach an easter egg.
type
Vec2 = tuple[x,y: int]
Robot = object
pos, vel: Vec2
var
GridRows = 101
GridCols = 103
proc examine(robots: seq[Robot]) =
for y in 0..<GridCols:
for x in 0..<GridRows:
let c = robots.countIt(it.pos == (x, y))
stdout.write if c == 0: '.' else: char('0'.ord + c)
stdout.write '\n'
stdout.flushFile()
proc solve(input: string): AOCSolution[int, int] =
var robots: seq[Robot]
for line in input.splitLines():
let parts = line.split({' ',',','='})
robots.add Robot(pos: (parts[1].parseInt,parts[2].parseInt),
vel: (parts[4].parseInt,parts[5].parseInt))
block p1:
var quads: array[4, int]
for robot in robots:
let
newX = (robot.pos.x + robot.vel.x * 100).euclmod GridRows
newY = (robot.pos.y + robot.vel.y * 100).euclmod GridCols
relRow = cmp(newX, GridRows div 2)
relCol = cmp(newY, GridCols div 2)
if relRow == 0 or relCol == 0: continue
inc quads[int(relCol>0)*2 + int(relRow>0)]
result.part1 = quads.foldl(a*b)
block p2:
if GridRows != 101: break p2
var interesting = 99
var interval = 101
var i = 0
while true:
for robot in robots.mitems:
robot.pos.x = (robot.pos.x + robot.vel.x).euclmod GridRows
robot.pos.y = (robot.pos.y + robot.vel.y).euclmod GridCols
inc i
if i == interesting:
robots.examine()
echo "Iteration #", i, "; Do you see an xmas tree?[N/y]"
if stdin.readLine().normalize() == "y":
result.part2 = i
break
interesting += interval
4 points
TypeScript
Part 2 was a major curveball for sure. I was expecting something like the grid size and number of seconds multiplying by a large amount to make iterative solutions unfeasible.
First I was baffled how we’re supposed to know what shape we’re looking for exactly. I just started printing out cases where many robots were next to each other and checked them by hand and eventually found it. For my input the correct picture looked like this:
The Christmas tree
Later it turned out that a much simpler way is to just check for the first time none of the robots are overlapping each other. I cannot say for sure if this works for every input, but I suspect the inputs are generated in such a way that this approach always works.
The code
import fs from "fs";
type Coord = {x: number, y: number};
type Robot = {start: Coord, velocity: Coord};
const SIZE: Coord = {x: 101, y: 103};
const input: Robot[] = fs.readFileSync("./14/input.txt", "utf-8")
.split(/[\r\n]+/)
.map(row => /p=(-?\d+),(-?\d+)\sv=(-?\d+),(-?\d+)/.exec(row))
.filter(matcher => matcher != null)
.map(matcher => {
return {
start: {x: parseInt(matcher[1]), y: parseInt(matcher[2])},
velocity: {x: parseInt(matcher[3]), y: parseInt(matcher[4])}
};
});
console.info("Part 1: " + safetyFactor(input.map(robot => calculatePosition(robot, SIZE, 100)), SIZE));
// Part 2
// Turns out the Christmas tree is arranged the first time none of the robots are overlapping
for (let i = 101; true; i++) {
const positions = input.map(robot => calculatePosition(robot, SIZE, i));
if (positions.every((position, index, arr) => arr.findIndex(pos => pos.x === position.x && pos.y === position.y) === index)) {
console.info("Part 2: " + i);
break;
}
}
function calculatePosition(robot: Robot, size: Coord, seconds: number): Coord {
return {
x: ((robot.start.x + robot.velocity.x * seconds) % size.x + size.x) % size.x,
y: ((robot.start.y + robot.velocity.y * seconds) % size.y + size.y) % size.y
};
}
function safetyFactor(positions: Coord[], size: Coord): number {
const midX = Math.floor(size.x / 2);
const midY = Math.floor(size.y / 2);
let quadrant0 = 0; // Top-left
let quadrant1 = 0; // Top-right
let quadrant2 = 0; // Bottom-left
let quadrant3 = 0; // Bottom-right
for (const {x,y} of positions) {
if (x === midX || y === midY) { continue; }
if (x < midX && y < midY) { quadrant0++; }
else if (x > midX && y < midY) { quadrant1++; }
else if (x < midX && y > midY) { quadrant2++; }
else if (x > midX && y > midY) { quadrant3++; }
}
return quadrant0 * quadrant1 * quadrant2 * quadrant3;
}
2 points
3 points
Haskell
Part 2 could be improved significantly now that I know what to look for, but this is the (very inefficient) heuristic I eventually found the answer with.
Solution
import Control.Arrow
import Data.Char
import Data.List
import Data.Map qualified as Map
import Data.Maybe
import Text.Parsec
(w, h) = (101, 103)
readInput :: String -> [((Int, Int), (Int, Int))]
readInput = either (error . show) id . parse (robot `endBy` newline) ""
where
robot = (,) <$> (string "p=" >> coords) <*> (string " v=" >> coords)
coords = (,) <$> num <* char ',' <*> num
num = read <$> ((++) <$> option "" (string "-") <*> many1 digit)
runBots :: [((Int, Int), (Int, Int))] -> [[(Int, Int)]]
runBots = transpose . map botPath
where
botPath (p, (vx, vy)) = iterate (incWrap w vx *** incWrap h vy) p
incWrap s d = (`mod` s) . (+ d)
safetyFactor :: [(Int, Int)] -> Int
safetyFactor = product . Map.fromListWith (+) . map (,1) . mapMaybe quadrant
where
cx = w `div` 2
cy = h `div` 2
quadrant (x, y)
| x == cx || y == cy = Nothing
| otherwise = Just (x `div` (cx + 1), y `div` (cy + 1))
render :: [(Int, Int)] -> [String]
render bots =
let counts = Map.fromListWith (+) $ map (,1) bots
in flip map [0 .. h - 1] $ \y ->
flip map [0 .. w - 1] $ \x ->
maybe '.' intToDigit $ counts Map.!? (x, y)
isImage :: [String] -> Bool
isImage = (> 4) . length . filter hasRun
where
hasRun = any ((> 3) . length) . filter head . group . map (/= '.')
main = do
positions <- runBots . readInput <$> readFile "input14"
print . safetyFactor $ positions !! 100
let (Just (t, image)) = find (isImage . snd) $ zip [0 ..] $ map render positions
print t
mapM_ putStrLn image
2 points
Haskell
I solved part two interactively, I’m not very happy about it
Reveal Code
import Control.Arrow
import Data.Bifunctor hiding (first, second)
import Control.Monad
import qualified Data.List as List
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Maybe as Maybe
parse :: String -> [((Int, Int), (Int, Int))]
parse = map (break (== ' ') >>> second (drop 1) >>> join bimap (drop 2) >>> join bimap (break (== ',')) >>> join bimap (second (drop 1)) >>> join bimap (join bimap read)) . filter (/= "") . lines
moveRobot ((px, py), (vx, vy)) t = (px + t * vx, py + t * vy)
constrainCoordinates (mx, my) (px, py) = (px `mod` mx, py `mod` my)
coordinateConstraints = (101, 103)
robotQuadrant (mx, my) (px, py)
| px > middleX && py < middleY = Just 1 -- upper right
| px > middleX && py > middleY = Just 2 -- lower right
| px < middleX && py > middleY = Just 3 -- lower left
| px < middleX && py < middleY = Just 4 -- upper left
| otherwise = Nothing
where
middleX = (mx `div` 2)
middleY = (my `div` 2)
countQuadrants (q1, q2, q3, q4) 1 = (succ q1, q2, q3, q4)
countQuadrants (q1, q2, q3, q4) 2 = (q1, succ q2, q3, q4)
countQuadrants (q1, q2, q3, q4) 3 = (q1, q2, succ q3, q4)
countQuadrants (q1, q2, q3, q4) 4 = (q1, q2, q3, succ q4)
part1 = map (flip moveRobot 100 >>> constrainCoordinates coordinateConstraints)
>>> map (robotQuadrant coordinateConstraints)
>>> Maybe.catMaybes
>>> foldl (countQuadrants) (0, 0, 0, 0)
>>> \ (a, b, c, d) -> a * b * c * d
showMaybe (Just i) = head . show $ i
showMaybe Nothing = ' '
buildRobotString robotMap = [ [ showMaybe (robotMap Map.!? (x, y)) | x <- [0..fst coordinateConstraints] ] | y <- [0..snd coordinateConstraints]]
part2 rs t = map (flip moveRobot t >>> constrainCoordinates coordinateConstraints)
>>> flip zip (repeat 1)
>>> Map.fromListWith (+)
>>> buildRobotString
$ rs
showConstellation (i, s) = do
putStrLn (replicate 49 '#' ++ show i ++ replicate 49 '#')
putStrLn $ s
main = do
f <- getContents
let i = parse f
print $ part1 i
let constellations = map (id &&& (part2 i >>> List.intercalate "\n")) . filter ((== 86) . (`mod` 103)) $ [0..1000000]
mapM_ showConstellation constellations
print 7502
3 points
*
Haskell. For part 2 I just wrote 10000 text files and went through them by hand. I quickly noticed that every 103 seconds, an image started to form, so it didn’t take that long to find the tree.
Code
import Data.Maybe
import Text.ParserCombinators.ReadP
import qualified Data.Map.Strict as M
type Coord = (Int, Int)
type Robot = (Coord, Coord)
int :: ReadP Int
int = fmap read $ many1 $ choice $ map char $ '-' : ['0' .. '9']
coord :: ReadP Coord
coord = (,) <$> int <*> (char ',' *> int)
robot :: ReadP Robot
robot = (,) <$> (string "p=" *> coord) <*> (string " v=" *> coord)
robots :: ReadP [Robot]
robots = sepBy robot (char '\n')
simulate :: Coord -> Int -> Robot -> Coord
simulate (x0, y0) t ((x, y), (vx, vy)) =
((x + t * vx) `mod` x0, (y + t * vy) `mod` y0)
quadrant :: Coord -> Coord -> Maybe Int
quadrant (x0, y0) (x, y) = case (compare (2*x + 1) x0, compare (2*y + 1) y0) of
(LT, LT) -> Just 0
(LT, GT) -> Just 1
(GT, LT) -> Just 2
(GT, GT) -> Just 3
_ -> Nothing
freqs :: (Foldable t, Ord a) => t a -> M.Map a Int
freqs = foldr (\x -> M.insertWith (+) x 1) M.empty
solve :: Coord -> Int -> [Robot] -> Int
solve grid t = product . freqs . catMaybes . map (quadrant grid . simulate grid t)
showGrid :: Coord -> [Coord] -> String
showGrid (x0, y0) cs = unlines
[ [if (x, y) `M.member` m then '#' else ' ' | x <- [0 .. x0]]
| let m = M.fromList [(c, ()) | c <- cs]
, y <- [0 .. y0]
]
main :: IO ()
main = do
rs <- fst . last . readP_to_S robots <$> getContents
let g = (101, 103)
print $ solve g 100 rs
sequence_
[ writeFile ("tree_" ++ show t) $ showGrid g $ map (simulate g t) rs
| t <- [0 .. 10000]
]
