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
Uiua
Ok, so part one wasn’t too hard, and since uiua also takes negative values for accessing arrays, I didn’t even have to care about converting my modulus results (though I did later for part two).
I’m a bit conflicted about the way I detected the quadrants the robots are in, or rather the way the creation of the mask-array happens. I basically made a 11x7 field of 0’s, then picked out each quadrant and added 1-4 respectively. Uiua’s group (⊕) function then takes care of putting all the robots in separate arrays for each quadrant. Simple.
For part two, I didn’t even think long before I came here to see other’s approaches. The idea to look for the first occurrence where no robots’ positions overlapped was my starting point for what follows.
Example input stuff
Run with example input here
$ p=0,4 v=3,-3
$ p=6,3 v=-1,-3
$ p=10,3 v=-1,2
$ p=2,0 v=2,-1
$ p=0,0 v=1,3
$ p=3,0 v=-2,-2
$ p=7,6 v=-1,-3
$ p=3,0 v=-1,-2
$ p=9,3 v=2,3
$ p=7,3 v=-1,2
$ p=2,4 v=2,-3
$ p=9,5 v=-3,-3
.
PartOne ← (
# &rs ∞ &fo "input-14.txt"
⊜(↯2_2⋕regex"-?\\d+")≠@\n.
≡(⍜⌵(◿11_7)+°⊟⍜⊡₁×₁₀₀)
↯⟜(▽×°⊟)7_11 0
⍜↙₃(⍜≡↙₅+₁⍜≡↘₆+₂)
⍜↘₄(⍜≡↙₅+₃⍜≡↘₆+₄)
/×≡◇⧻⊕□-₁⊸(⊡:)⍉
)
PartTwo ← (
# &rs ∞ &fo "input-14.txt"
⊜(↯2_2⋕regex"-?\\d+")≠@\n.
0 # number of seconds to start at
0_0
⍢(◡(≡(⍜⌵(◿11_7)+°⊟⍜⊡₁×):)◌
◿[11_7]≡+[11_7]
⊙+₁
| ≠⊙(⧻◴)⧻.)
⊙◌◌
-₁
)
&p "Day 14:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo
Now on to the more layered approach of how I got my solution.
In my case, there’s two occasions of non-overlapping positions before the christmas tree appears.
I had some fun trying to get those frames and kept messing up with going back and forth between 7x11 vs 103x101 fields, often forgetting to adjust the modulus and other parts, so that was great.
In the end, I uploaded my input to the online uiua pad to make visualizing possible frames easier since uiua is able to output media if the arrays match a defined format.
Try it out yourself with your input
- Open the uiua pad with code here
- Replace the
0in the first line with your solution for part two - If necessary, change the name of the file containing your input
- Drag a file containing your input onto the pad to upload it and run the code
- An image should be displayed
I used this code to find the occurrence of non-overlapping positions (running this locally):
&rs ∞ &fo "input-14.txt"
⊜(↯2_2⋕regex"-?\\d+")≠@\n.
0 # number of seconds to start at
0_0
⍢(◡(≡(⍜⌵(◿101_103)+°⊟⍜⊡₁×):)◌
◿[101_103]≡+[101_103]
⊙+₁
| ≠⊙(⧻◴)⧻.)
⊙◌◌
-₁
Whenever a new case was found, I put the result into the code in the online pad to check the generated image, and finally got this at the third try:
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;
}
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
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
J
Had to actually render output! What is this “user interface” of which you speak?
J doesn’t have meaningful identifiers for system interfaces built into the core language because why would you ever do that. It’s all routed through the “foreign conjunction” !:. There are aliases in the library, like fread, but if the documentation gives a list of all of them, I haven’t found it. We’re doing 1980 style system calls by number here. 1 !: 2 is write(), so x (1 !: 2) 2 writes x (which must be a list of characters) to stdout. (6 !: 3) y is sleep for y seconds.
It’s inefficient to compute, but I looked for low spots in the mean distance between robots to find the pattern for part 2. The magic numbers (11 and 101) were derived by staring at the entire series for a little bit.
load 'regex'
data_file_name =: '14.data'
raw =: cutopen fread data_file_name
NB. a b sublist y gives elements [a..a+b) of y
sublist =: ({~(+i.)/)~"1 _
parse_line =: monad define
match =: 'p=(-?[[:digit:]]+),(-?[[:digit:]]+) v=(-?[[:digit:]]+),(-?[[:digit:]]+)' rxmatch y
2 2 $ ". y sublist~ }. match
)
initial_state =: parse_line"1 > raw
'positions velocities' =: ({."2 ; {:"2) initial_state
steps =: 100
size =: 101 103
step =: (size & |) @: +
travel =: step (steps & *)
quadrant =: (> & (<. size % 2)) - (< & (<. size % 2))
final_quadrants =: quadrant"1 @: travel"1
quadrant_ids =: 4 2 $ 1 1 _1 1 1 _1 _1 _1
result1 =: */ +/"1 quadrant_ids -:"1/ positions final_quadrants velocities
render =: monad define
|: 'O' (<"1 y)} size $ '.'
)
pair_distances =: monad : 'y (| @: j./ @: -/"1)/ y'
loop =: dyad define
positions =. positions step"1 (velocities * x)
for_i. i. 1000 do.
time_number =. x + i * y
mean_distance =. (+/ % #) , pair_distances positions
if. mean_distance < 50 do.
(render positions) (1!:2) 2
(": time_number, mean_distance) (1!:2) 2
(6!:3) 1
end.
if. mean_distance < 35 do. break. end.
positions =. positions step"1 (velocities * y)
end.
time_number
result2 =: 11 loop 101
