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
0
in 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, alternative approach
The x and y coordinates of robots are independent. 101 and 103 are prime. So, the pattern of x coordinates will repeat every 101 ticks, and the pattern of y coordinates every 103 ticks.
For the first 101 ticks, take the histogram of x-coordinates and test it to see if it’s roughly randomly scattered by performing a chi-squared test using a uniform distrobution as the basis. [That code’s not given below, but it’s a trivial transliteration of the formula on wikipedia, for instance.] In my case I found a massive peak at t=99.
Same for the first 103 ticks and y coordinates. Mine showed up at t=58.
You’re then just looking for solutions of t = 101m + 99, t = 103n + 58 [in this case]. I’ve a library function, maybeCombineDiophantine, which computes the intersection of these things if any exist; again, this is basic wikipedia stuff.
day14b ls =
let
rs = parse ls
size = (101, 103)
positions = map (\t -> process size t rs) [0..]
-- analyse x coordinates. These should have period 101
xs = zip [0..(fst size)] $ map (\rs -> map (\(p,_) -> fst p) rs & C.count & chi_squared (fst size)) positions
xMax = xs & sortOn snd & last & fst
-- analyse y coordinates. These should have period 103
ys = zip [0..(snd size)] $ map (\rs -> map (\(p,_) -> snd p) rs & C.count & chi_squared (snd size)) positions
yMax = ys & sortOn snd & last & fst
-- Find intersections of: t = 101 m + xMax, t = 103 n + yMax
ans = do
(s,t) <- maybeCombineDiophantine (fromIntegral (fst size), fromIntegral xMax)
(fromIntegral (snd size), fromIntegral yMax)
pure $ minNonNegative s t
in
trace ("xs distributions: " ++ show (sortOn snd xs)) $
trace ("ys distributions: " ++ show (sortOn snd ys)) $
trace ("xMax = " ++ show xMax ++ ", yMax = " ++ show yMax) $
trace ("answer could be " ++ show ans) $
ans
Very cool, taking a statistical approach to discern random noise from picture.
Thanks. It was the third thing I tried - began by looking for mostly-symmetrical, then asked myself “what does a christmas tree look like?” and wiring together some rudimentary heuristics. When those both failed (and I’d stopped for a coffee) the alternative struck me. It seems like a new avenue into the same diophantine fonisher that’s pretty popular in these puzzles - quite an interesting one.
This day’s puzzle is clearly begging for some inventive viaualisations.
C
Solved part 1 without a grid, looked at part 2, almost spit out my coffee. Didn’t see that coming!
I used my visualisation mini-library to generate video with ffmpeg, stepped through it a bit, then thought better of it - this is a programming puzzle after all!
So I wrote a heuristic to find frames low on entropy (specifically: having many robots in the same line of column), where each record-breaking frame number was printed. That pointed right at the correct frame!
It was pretty slow though (.2 secs or such) because it required marking spots on a grid. I noticed the Christmas tree was neatly tucked into a corner, concluded that wasn’t an accident, and rewrote the heuristic to check for a high concentration in a single quadrant. Reverted this because the tree-in-quadrant assumption proved incorrect for other inputs. Would’ve been cool though!
Code
#include "common.h"
#define SAMPLE 0
#define GW (SAMPLE ? 11 : 101)
#define GH (SAMPLE ? 7 : 103)
#define NR 501
int
main(int argc, char **argv)
{
static char g[GH][GW];
static int px[NR],py[NR], vx[NR],vy[NR];
int p1=0, n=0, sec, i, x,y, q[4]={}, run;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (; scanf(" p=%d,%d v=%d,%d", px+n,py+n, vx+n,vy+n)==4; n++)
assert(n+1 < NR);
for (sec=1; !SAMPLE || sec <= 100; sec++) {
memset(g, 0, sizeof(g));
memset(q, 0, sizeof(q));
for (i=0; i<n; i++) {
px[i] = (px[i] + vx[i] + GW) % GW;
py[i] = (py[i] + vy[i] + GH) % GH;
g[py[i]][px[i]] = 1;
if (sec == 100) {
if (px[i] < GW/2) {
if (py[i] < GH/2) q[0]++; else
if (py[i] > GH/2) q[1]++;
} else if (px[i] > GW/2) {
if (py[i] < GH/2) q[2]++; else
if (py[i] > GH/2) q[3]++;
}
}
}
if (sec == 100)
p1 = q[0]*q[1]*q[2]*q[3];
for (y=0; y<GH; y++)
for (x=0, run=0; x<GW; x++)
if (!g[y][x])
run = 0;
else if (++run >= 10)
goto found_p2;
}
found_p2:
printf("14: %d %d\n", p1, sec);
return 0;
}
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]
]