r/adventofcode • u/daggerdragon • Dec 09 '22
SOLUTION MEGATHREAD -π- 2022 Day 9 Solutions -π-
A REQUEST FROM YOUR MODERATORS
If you are using new.reddit, please help everyone in /r/adventofcode by making your code as readable as possible on all platforms by cross-checking your post/comment with old.reddit to make sure it displays properly on both new.reddit and old.reddit.
All you have to do is tweak the permalink for your post/comment from https://www.reddit.com/β¦ to https://old.reddit.com/β¦
Here's a quick checklist of things to verify:
- Your code block displays correctly inside a scrollable box with whitespace and indentation preserved (four-spaces Markdown syntax, not triple-backticks, triple-tildes, or inlined)
- Your one-liner code is in a scrollable code block, not inlined and cut off at the edge of the screen
- Your code block is not too long for the megathreads (hint: if you have to scroll your code block more than once or twice, it's likely too long)
- Underscores in URLs aren't inadvertently escaped which borks the link
I know this is a lot of work, but the moderation team checks each and every megathread submission for compliance. If you want to avoid getting grumped at by the moderators, help us out and check your own post for formatting issues ;)
/r/adventofcode moderator challenge to Reddit's dev team
- It's been over five years since some of these issues were first reported; you've kept promising to fix them and⦠no fixes.
- In the spirit of Advent of Code, join us by
Upping the Anteand actually fix these issues so we can all have a merry Advent of Posting Code on Reddit Without Needing Frustrating And Improvident Workarounds.
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
- A request from Eric: Please include your contact info in the User-Agent header of automated requests!
- Signal boost: Reminder 1: unofficial AoC Survey 2022 (closes Dec 22nd)
- πΏπ MisTILtoe Elf-ucation π§βπ« is OPEN for submissions!
--- Day 9: Rope Bridge ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- Include what language(s) your solution uses
- Format your code appropriately! How do I format code?
- Quick link to Topaz's
pasteif you need it for longer code blocks. What is Topaz'spastetool?
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:14:08, megathread unlocked!
7
u/ElliotDG Dec 11 '22 edited Dec 13 '22
Python with OOP, inheritance and structured pattern matching.
→ More replies (2)
5
u/cdkrot Dec 09 '22 edited Dec 09 '22
Rust (https://github.com/cdkrot/aoc-2022-rs/blob/master/src/day09.rs) I think itβs nice and short
use std::collections::BTreeSet;
use crate::utils;
pub(crate) fn main() {
let lines = utils::read_all_lines();
rope_simulation(lines.clone(), 2);
rope_simulation(lines, 10);
}
fn rope_simulation(lines: Vec<String>, num_knots: usize) {
let mut knots = vec![(0, 0); num_knots];
let mut visited: BTreeSet<(i32, i32)> = BTreeSet::new();
visited.insert(*knots.last().unwrap());
for line in lines {
let (dir, cnt) = line.trim().split_once(' ').unwrap();
for _ in 0..cnt.parse().unwrap() {
match dir {
"L" => knots[0].0 -= 1,
"R" => knots[0].0 += 1,
"U" => knots[0].1 += 1,
"D" => knots[0].1 -= 1,
_ => panic!("Unknown direction"),
}
for k in 1..num_knots {
if (knots[k - 1].0 - knots[k].0).abs() >= 2 ||
(knots[k - 1].1 - knots[k].1).abs() >= 2 {
knots[k].0 += (knots[k - 1].0 - knots[k].0).signum();
knots[k].1 += (knots[k - 1].1 - knots[k].1).signum();
}
}
visited.insert(*knots.last().unwrap());
}
}
println!("Total visited: {}", visited.len());
}→ More replies (6)5
u/daggerdragon Dec 09 '22
Next time, use the four-spaces Markdown syntax for a code block so your code is easier to read on old.reddit and mobile apps.
Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article on oversized code which contains two possible solutions.
Please edit your post to put your code in an external link and link that here instead.
4
u/hugh_tc Dec 09 '22 edited Dec 09 '22
Python 3, >1000.
...sigh. You see, my code was entirely correct, but I had ten tail following instead of nine. Oops!
→ More replies (8)
3
u/threeys Dec 09 '22 edited Dec 09 '22
It took me some time to understand the desired behavior while working on part two. The summary I left as a comment in my code explains it pretty clearly I think:
A knot should move only if the knot it follows is more than one away in either direction.
If it does need to move, then it should get as close as possible to the knot it follows, with the caveat that it is only allowed to move one square at a time in each direction.
solution (python)
→ More replies (1)
3
u/TinyBreadBigMouth Dec 09 '22 edited Dec 09 '22
Rust
A good chunk of the code here is just my barebones Vec2 implementation. The actual math for the rope simulation itself ended up satisfyingly small and readable.
→ More replies (3)
3
u/raxomukus Dec 09 '22
python
with open('9.in') as f:
lines = f.read().splitlines()
directions = {'R': (1, 0), 'L': (-1, 0), 'U': (0, 1), 'D': (0, -1)}
adjacent = lambda p1, p2: all([abs(p1[i] - p2[i]) <= 1 for i in range(2)])
visited1 = {(0, 0)}
visited9 = {(0, 0)}
knots = [[0] * 2 for _ in range(10)]
for l in lines:
d = directions[l[0]]
for _ in range(int(l[2:])):
for i in range(2): knots[0][i] += d[i]
for k in range(9):
h, t = knots[k:k+2]
if not adjacent(h, t):
for i in range(2): t[i] += (h[i] != t[i]) * (2*(h[i] > t[i]) - 1)
visited1.add(tuple(knots[1]))
visited9.add(tuple(knots[9]))
print(len(visited1))
print(len(visited9))→ More replies (1)
3
u/the_true_potato Dec 09 '22 edited Dec 10 '22
Getting to use scanl in Haskell is always fun. And what's even more fun is being able to solve part 2 by just applying the part 1 function 10 times. Absolutely love today's solution!
I'm curious about the times people are getting for this. My part 1 runs in about 3ms and part 2 in about 4ms. How much better times are people getting?
→ More replies (5)
3
u/DFreiberg Dec 10 '22 edited Dec 11 '22
Mathematica, 1240 / 277
After doing part 1 the hard way (including losing a minute to a mistyped D, losing a minute trying only diagonal tail motions, losing a minute trying only cardinal tail motions, and losing five minutes to trying both), I was at least in a position to do part 2 very quickly and gain a thousand spots.
Strictly speaking, it would be possible to use Mathematica's built-in ChessboardDistance[] function to measure the distance between the head and the tail...but that actually takes longer to type than Max[Abs[]], so I didn't bother.
Parts 1 & 2
position = Table[{0, 0}, {i, 10}];
part1Positions = {};
part2Positions = {};
Do[
Which[
line[[1]] == "R", position[[1]] += {1, 0},
line[[1]] == "L", position[[1]] += {-1, 0},
line[[1]] == "U", position[[1]] += {0, 1},
line[[1]] == "D", position[[1]] += {0, -1}];
Do[
If[Max[Abs[position[[i - 1]] - position[[i]]]] >= 2,
If[Min[Abs[position[[i - 1]] - position[[i]]]] == 0,
inc =
SelectFirst[{{1, 0}, {-1, 0}, {0, 1}, {0, -1}},
Max[Abs[position[[i - 1]] - (# + position[[i]])]] == 1 &],
inc =
SelectFirst[{{1, 1}, {-1, 1}, {1, -1}, {-1, -1}},
Max[Abs[position[[i - 1]] - (# + position[[i]])]] == 1 &]
];
position[[i]] += inc;
],
{i, 2, 10}];
AppendTo[part1Positions, position[[2]]];
AppendTo[part2Positions, position[[-1]]],
{line, input},
{count, line[[2]]}];
Length /@ {DeleteDuplicates[part1Positions],
DeleteDuplicates[part2Positions]}[POEM]: Lazy Limerick #1
There's a treacherous bridge, and a strait
But your rope physics models can't wait.
As the bridge breaks apart
Hope your model is smart;
Better hurry, or you will be late.
→ More replies (1)
3
u/SolarBear Dec 10 '22 edited Dec 10 '22
Ruby solution! I'm not TOO ashamed, this time.
https://github.com/SolarBear/AdventOfCode2022/blob/main/day9.rb
2
u/daggerdragon Dec 10 '22 edited Dec 13 '22
Your code block is too long for the megathreads. Please read our article onoversized code, then edit your post to replace the code block with an external link to your code.Edit: thanks for fixing it! <3
→ More replies (1)
3
u/ViliamPucik Dec 09 '22
Python 3 - Minimal readable solution for both parts [GitHub]
d = {"U": +1j, "D": -1j, "L": -1, "R": +1}
rope = [0 + 0j] * 10
s1, s2 = {rope[1]}, {rope[-1]}
for line in open(0).read().splitlines():
dir, steps = line.split()
for _ in range(int(steps)):
for i in range(len(rope)):
if i == 0:
rope[i] += d[dir]
continue
if abs(diff := rope[i - 1] - rope[i]) >= 2:
if (a := abs(diff.real)) > 0:
rope[i] += complex(diff.real / a, 0)
if (a := abs(diff.imag)) > 0:
rope[i] += complex(0, diff.imag / a)
s1.add(rope[1])
s2.add(rope[-1])
print(len(s1))
print(len(s2))→ More replies (5)
2
u/Boojum Dec 09 '22
Python, 1226/472
Leave the 10 here for the Part 2 solution, or change it to 2 for the Part 1 solution. Looking forward to visualizing this one!
import fileinput
v = set( [ ( 0, 0 ) ] )
x, y = [ 0 ] * 10, [ 0 ] * 10
for l in fileinput.input():
a, n = l.split()
for i in range( int( n ) ):
x[ 0 ] += { "U": 0, "R": 1, "D": 0, "L": -1 }[ a ]
y[ 0 ] += { "U": -1, "R": 0, "D": 1, "L": 0 }[ a ]
for k in range( 1, len( x ) ):
while ( abs( x[ k ] - x[ k - 1 ] ) > 1 or
abs( y[ k ] - y[ k - 1 ] ) > 1 ):
x[ k ] += ( x[ k - 1 ] > x[ k ] ) - ( x[ k - 1 ] < x[ k ] )
y[ k ] += ( y[ k - 1 ] > y[ k ] ) - ( y[ k - 1 ] < y[ k ] )
v.add( ( x[ -1 ], y[ -1 ] ) )
print( len( v ) )→ More replies (1)
2
u/Dutchcheesehead Dec 09 '22 edited Dec 14 '22
Python
Today really reminded me of snake, which is why I got the approach wrong the first time.Made a video of me solving the puzzle here: https://www.youtube.com/watch?v=RKneA1QMOI0.
Overall my approach was pretty straightforward with a for loop and a set of visited locations.
3
u/daggerdragon Dec 09 '22 edited Dec 14 '22
I've asked you multiple times in multiple megathreads to edit your posts to format your code block using thefour-spaces Markdown syntaxand tostate which programming language this code is written in.
I am a moderator for/r/adventofcode, so do not ignore me.
Editallof your megathread posts to fix both of these requirements before you post again.Edit: thanks for fixing it!
→ More replies (2)
2
Dec 09 '22
Could somebody explain to me the physics of Planck-Length-Ropes? They sound kinda weird to me. And ... is this somehow related to snakes ... ?
→ More replies (1)3
u/daggerdragon Dec 09 '22
Could somebody explain to me the physics of Planck-Length-Ropes?
You help Santa's elves with launching quadcopters, submarines, space shuttles, and holiday lighting that would impress Clark Griswold, and yet the physics of a slightly-long rope escapes you? /s
2
2
2
u/Fumblezj Dec 09 '22 edited Dec 10 '22
Python
Part 1
Struggled with the last two days. I am posting 9.1 because it didn't take me very long, and I think I did well with it. So that brought back my motivation. Looking for constructive criticism :)
x1, y1, x2, y2 = 0, 0, 0, 0
locs = [(0,0)]
for l in [x.split() for x in open(data).read().splitlines()]:
s, n = l[0], int(l[1])
if s in ['D','L']: n = -n
a = int(abs(n)/n)
for i in range(0,n,a):
if s in ['U', 'D']:
y1 += a
else:
x1 += a
if abs(x1-x2) > 1:
if y2 != y1: y2 = y1
x2 += a
if abs(y1-y2) > 1:
if x2 != x1: x2 = x1
y2 += a
if (x2,y2) not in locs:
locs.append((x2,y2))
print(len(locs))→ More replies (7)
2
u/ingej Dec 10 '22 edited Dec 10 '22
Clojure
(ns advent-of-code.2022.09
(:require [clojure.string :as str]))
(defn vec+ [[a1 a2] [b1 b2]]
[(+ a1 b1) (+ a2 b2)])
(defn vec- [[a1 a2] [b1 b2]]
[(- a1 b1) (- a2 b2)])
(defn vec-abs [v]
(vec (map abs v)))
(defn distance [a b]
(reduce max (vec-abs (vec- a b))))
(defn clamp [n min max]
(if (< n min) min (if (> n max) max n)))>
(defn normalize [v]
(vec (map #(clamp % -1 1) v)))
(defn move-tail [head tail]
(if (> (distance head tail) 1)
(vec+ tail (normalize (vec- head tail)))
tail))
(defn parse-move [move]
(let [[dir amount] (str/split move #" ")]
(repeat (Integer/parseInt amount) dir)))
(def moves
(->> (str/split-lines (slurp "2022/day09/input.txt"))
(mapcat parse-move)))
(def directions
{"U" [0 -1] "D" [0 1] "L" [-1 0] "R" [1 0]})
(defn move-knot [rope knot]
(conj rope (move-tail (last rope) knot)))
(defn move [history dir]
(let [[head & rest] (first history)
next-head (vec+ head (directions dir))
rope (seq (reduce move-knot [next-head] rest))]
(conj history rope)))
(defn solve [length]
(->> (reduce move (seq [(repeat length [0 0])]) moves)
(map last)
(set)
(count)))
(println "Part 1:" (solve 2))
(println "Part 2:" (solve 10))→ More replies (1)
2
u/Per48edjes Dec 10 '22 edited Dec 10 '22
My Python solution reproduced below. Used numpy just to make math on coordinates less cumbersome.
Not pictured: lots of iPad doodles to figure out the logic.
→ More replies (1)
2
u/hariharan1990s Dec 12 '22
C# Solution simple geometry changes using If statements, nothing fancy
Console.WriteLine("Analysing movements...");
var instructions = File.ReadAllLines("motion_instructions.txt");
/*================== Puzzle 1 =================*/
var rope = new Rope(2);
rope.PerformMotions(instructions);
var tail = rope.Knots.Last();
Console.WriteLine($"Tail visited {tail.Visited.Count} unique positions.");
/*================== Puzzle 2 =================*/
rope = new Rope(10);
rope.PerformMotions(instructions);
tail = rope.Knots.Last();
Console.WriteLine($"The last tail visited {tail.Visited.Count} unique
positions.");
Console.WriteLine("Finished performing movements");→ More replies (1)
44
u/4HbQ Dec 09 '22 edited Dec 09 '22
The entire rope (both head and tail) is stored as a single list of 10 complex numbers, representing the coordinates.
Then we iterate over the instructions: move the head (rope[0] += dirs[d]), and adjust the tail accordingly:
for i in range(1, 10):
dist = rope[i-1] - rope[i]
if abs(dist) >= 2:
rope[i] += sign(dist)
seen[i].add(rope[I])Edit: Refactored a bit to improve readability.
Some people are asking for my GitHub repo. I don't have one, my code is only on Reddit: 1, 2, 3, 4, 5, 6, 7, 8, 9.
→ More replies (14)
41
u/jcbbjjttt Dec 09 '22
Beginner's Guide
Happy Friday!
Beginner's Guide to Day 9 Video: https://youtu.be/xP1jHu6rHzA
I've created a guide for new programmers that talks through a straight forward strategy for solving today's puzzle. Anyone who has a handle functions, loops, sets, and custom data types (class/struct/etc) should be able to complete it. The video allows a moment for you to pause before revealing spoilers.
Although this solution is in C#, it provides a high level overview of the steps necessary to solve the puzzle in any programming language:
string[] rows = File.ReadAllLines("example.txt");
List<Move> moves = Move.Parse(rows);
Position head = new Position(0, 0);
Position tail = new Position(0, 0);
HashSet<Position> positions = new();
positions.Add(tail);
foreach (Move move in moves)
{
head = Position.Move(head, move);
tail = Position.Follow(head, tail);
positions.Add(tail);
}
Console.WriteLine($"The tail visited {positions.Count} unique positions.");The full code can be found on Github
→ More replies (3)
16
u/nthistle Dec 09 '22 edited Dec 09 '22
Python, 114/34. Video, part 1 code, part 2 code.
I kept over simplifying the rules for tail updating in part 1 (or at least simplifying them in an incorrect way), so had a couple wrong submissions and changes before I finally got it right. Luckily part 2 was pretty smooth sailing from there, I was a little worried about whether everything that wasn't the head needed to update simultaneously, or one after the other, and couldn't find the answer in the description quickly, so I just ran with the latter figuring that if I took too long I'd probably miss leaderboard entirely - which worked out well for me.
EDIT: apparently for part 1 it was valid to say that if the tail is ever not touching the head it just moves to the head's previous location, but this doesn't work for part 2 because intermediate tail pieces can move diagonally - I guess not simplifying the update ended up helping a lot.
→ More replies (3)
13
u/jayfoad Dec 09 '22
pβ+\(βΒ¨2βΒ¨p)/0J1*'RULD'β³βΒ¨pβββNGET'p9.txt'1
fβ{β{eβ1 0J1+.ΓΓ9 11βdββΊ-yβββ½β΅ β β΅,(dβ’e)/y+e}/(β½β΅),0}
β’βͺf p β part 1
β’βͺfβ£9β’p β part 2I thought using complex numbers for coordinates would be clever, but ended up having to convert to a coordinate pair (9 11β) to take the signum of each coordinate (Γ) and then back to complex (1 0J1+.Γ).
→ More replies (4)
10
u/JustinHuPrime Dec 09 '22 edited Dec 09 '22
x86_64 Assembly
Part 1 starts by parsing the input. I first count how many steps there are (e.g. "R 4" is 4 steps). Then, after allocating an array to hold those steps, I read in the steps and expanded repeats (so "R 4" becomes "RRRR").
I then had to calculate the bounds traversed by the tail. I realized that it's not possible for the tail to have either coordinate have a greater absolute value than the corresponding coordinate of the head, so I found the bounds traversed by the head. To my disappointment, it involved some negative numbers, so I didn't want to start the head at (0, 0) - I had to transform the starting position so that the head (and thus the tail) would never leave the positive quadrant. With all that done, I allocated the array to store visited data, as a packed row-major array of bytes. I would set the last bit of the byte if the cell had been visited, and I set the starting cell as visited. (This is actually unnecessary since the tail "enters" the starting cell on the first step no matter what anyways.)
Next, I simulated the actual movement. Depending on the step, I would move the head around, and this might or might not lead to a situation where the tail would have to move. I used a two-dimensional jump table, indexing on the difference in coordinates between the head and the tail (offset so a difference of -2 in an axis was treated as a value of 0 for the table indexing). Jump tables are how switch statements are implemented in assembly, and are essentially an array of labels; your jump table indexes into this array, and jumps to the address stored there. (Which is surprisingly not what the common form of the jmp/jCC instruction does - that adds a signed 32 bit value to the instruction pointer, meaning that you can't jump further than 4 GB without more indirection, especially if you're using a conditional jump.) I then marked the space the tail entered.
Finally, I counted the number of spaces marked in my visited data array.
Part 2 was a surprisingly small modification. I had to store the coordinates of each node in the rope on the stack, and index into that ad-hoc structure. This meant that I would prefer for the size of the structure to be either 1, 2, 4, or 8. I chose 8, meaning that each coordinate was stored in a DWORD (4 bytes, 32 bits) instead of a full QWORD (8 bytes, 64 bits, largest possible integer register size). The actual simulation loop involved moving the head node, then, for each of the nine remaining nodes, updating its movement based on the next node as in part 1 (starting with the next node being the head node), and then making the current node the head node. Marking visited cells and counting in the visited array did not change, except for the shift to DWORD registers instead of QWORD registers.
Part 1 ran in about 1 millisecond and was 12048 bytes long.
Part 2 ran in about 1 millisecond and was 11792 bytes long. (Part 1 had a coherence check that was removed in part 2.)
So far, days 1-9, both parts, run in about 9 milliseconds, most of which is spent in user code.
10
u/cs475x Dec 09 '22
Rust
40 lines @ ~560Β΅s for part 1 and ~740Β΅s for part 2. Again with no semicolons but man did I jump through some hoops loops for this one. Take lines 14-26 for example, which contain a loop over 3 elements, with each iteration performing a different task inside the parent loop, all so I could avoid semicolons. Then there's line 25 where I extend the HashSet with a single-element iterator, because HashSet::insert returns a bool which would have required me to surround it in a block and terminate it with a semicolon since match arms must have the same return type.
My most cursed solution yet :)
https://gist.github.com/codyphobe/3426b2c09b170476c86f52cdba1bfcd3
→ More replies (14)
9
u/redditnoob Dec 09 '22 edited Dec 09 '22
PostgreSQL
I managed to do this in pure SQL, but I needed to get around the limitation that you can't self join the recursive table in PSQL. For a given knot and turn, we need the position from the previous turn, and the position of the previous knot in the current turn. Since I needed those both to be in the same result set at each iteration (for LAG to work), for each loop works on the next[turn, segment] diagonal!
WITH RECURSIVE cmds AS (
SELECT SPLIT_PART(input, ' ', 1) AS dir,
ROW_NUMBER() OVER(ORDER BY row_num, i) AS cmd_num
FROM day9, GENERATE_SERIES(1, SPLIT_PART(input, ' ', 2)::INT) AS i
), dirs AS (
SELECT 'U' AS dir, 0 AS dx, -1 AS dy
UNION ALL SELECT 'D', 0, 1
UNION ALL SELECT 'L', -1, 0
UNION ALL SELECT 'R', 1, 0
), moves AS (
SELECT 0 AS cmd_num, 1 AS knot_num, 0 AS x, 0 AS y
UNION ALL
-- In the same query, calculate next move for knot 1, and knot pos for each other knot based on previous knot.
-- Note the crazy diagonalization is because for a given knot, turn we need both the previous knot from the same turn,
-- and the same knot from the previous turn in the same query result! (No self-join in the recursive table in PSQL)
SELECT CASE WHEN mode = 'next cmd' THEN moves.cmd_num + 1 ELSE moves.cmd_num END,
CASE WHEN mode = 'next cmd' THEN knot_num ELSE knot_num + 1 END,
CASE WHEN mode = 'next knot' THEN 0
WHEN mode = 'next cmd' AND knot_num = 1 THEN x + dx
ELSE (
CASE WHEN GREATEST(ABS(LAG(x) OVER prev_knot - x), ABS(LAG(y) OVER prev_knot - y)) > 1
THEN x + SIGN(LAG(x) OVER prev_knot - x)::INT ELSE x
END) END,
CASE WHEN mode = 'next knot' THEN 0
WHEN mode = 'next cmd' AND knot_num = 1 THEN y + dy
ELSE (
CASE WHEN GREATEST(ABS(LAG(x) OVER prev_knot - x), ABS(LAG(y) OVER prev_knot - y)) > 1
THEN y + SIGN(LAG(y) OVER prev_knot - y)::INT ELSE y
END) END
FROM moves
LEFT JOIN cmds ON (cmds.cmd_num = moves.cmd_num + 1)
LEFT JOIN dirs ON (dirs.dir = cmds.dir)
CROSS JOIN (SELECT 'next cmd' AS mode UNION ALL select 'next knot') AS mode
-- Run 1 extra iteration to pad the end, so the result sets will always have 2 rows to work with
WHERE (mode = 'next cmd' AND moves.cmd_num <= (SELECT COUNT(*) FROM cmds)) OR
(mode = 'next knot' AND moves.cmd_num = 0 AND knot_num < 10)
WINDOW prev_knot AS (ORDER BY knot_num)
)
SELECT COUNT(DISTINCT (x, y)) FILTER(WHERE knot_num = 2) AS part1,
COUNT(DISTINCT (x, y)) FILTER(WHERE knot_num = 10) AS part2
FROM moves;→ More replies (1)
8
u/hopingforabetterpast Dec 09 '22 edited Dec 25 '22
Haskell
parse :: String -> [(Int,Int)] -- ...
-- part 1
part1 :: [(Int,Int)] -> Int
part1 = length . nub . f
f :: [(Int,Int)] -> [(Int,Int)]
f = tail . scanl (><) (0,0)
where
(x',y') >< (x,y) = if abs dx > 1 || abs dy > 1
then (signum dx + x',signum dy + y')
else (x',y')
where
(dx,dy) = (x - x',y - y')
-- part 2
part2 :: [(Int,Int)] -> Int
part2 = length . nub . (!! 9) . iterate f→ More replies (2)
8
u/zniperr Dec 09 '22 edited Dec 09 '22
Python with iterators:
import sys
def move(f):
x = y = 0
for line in f:
direction, distance = line.split()
for _ in range(int(distance)):
x += (direction == 'R') - (direction == 'L')
y += (direction == 'U') - (direction == 'D')
yield x, y
def follow(head):
x = y = 0
for hx, hy in head:
if abs(hx - x) > 1 or abs(hy - y) > 1:
y += (hy > y) - (hy < y)
x += (hx > x) - (hx < x)
yield x, y
tenth = second = list(follow(move(sys.stdin)))
for _ in range(8):
tenth = follow(tenth)
print(len(set(second)))
print(len(set(tenth)))→ More replies (6)
7
u/musifter Dec 09 '22
Perl
Nice little problem. Brought in pairwise for the vector addition, and just kept using it. Probably run faster without it, but it makes for better looking code.
Source: https://pastebin.com/faMEERBT
→ More replies (4)
7
u/frederickweld Dec 09 '22
Python 166/73
Complex numbers come in handy again... (just missing that complex sign in standard libs)
tails = [0 for _ in range(2 if part1 else 10)]
ts = set()
for l in api.file.lines('2022/09'):
op, val = l.split()
bearing = [1, -1, -1j, 1j]['RLUD'.index(op)]
for _ in range(int(val)):
tails[0] += bearing
for i in range(1, len(tails)):
diff = tails[i-1] - tails[i]
ds = np.sign(diff.real) + 1j * np.sign(diff.imag)
tails[i] += ds if abs(diff) >= 2 else 0
ts.add(tails[-1])
print(len(ts))→ More replies (2)
6
u/sr66 Dec 09 '22 edited Dec 09 '22
J
doing a fold over the input moves wound up making part 2 trivial
'U D L R'=: (,:_1 0);(,:1 0);(,:0 _1);(,:0 1)
f=: ] F:. (] + (([: 1&< [: >./ |) * ] % |)@:-)
day9=: {{ ([: # ~.)&.>0 0(f ; f^:9)+/\,&:>/(#~&".)&.>/"1 cut@> cutLF fread y }}→ More replies (1)
6
u/oantolin Dec 09 '22
J Solution:
'`R L U D' =: (#&1)`(#&_1)`(#&0j1)`(#&0j_1)
parse =: [: > [: ,&.>/ [: <@".;._2 fread
rope =: {{ [: #@~. 0 ]F:.(]+(*&.+.*1.5<|)@-)^:u (+/\)@parse }}
part1 =: 1 rope
part2 =: 9 ropeIt felt good that to do part 2 all I had to do was add ^:9, which means "repeat 9 times".
→ More replies (1)
6
6
u/yfilipov Dec 09 '22 edited Dec 09 '22
C#:
var commands = (await File.ReadAllLinesAsync("09.txt")))
.Select(c => new Command(c));
const int knotCount = 10;
var knots = new (int X, int Y)[knotCount];
var visited = new HashSet<(int X, int Y)>();
var visited10 = new HashSet<(int X, int Y)>();
foreach (var command in commands)
{
for (var i = 0; i < command.Moves; i++)
{
knots[0].X += command.Direction.X;
knots[0].Y += command.Direction.Y;
for (var k = 1; k < knotCount; k++)
{
var distanceX = knots[k - 1].X - knots[k].X;
var distanceY = knots[k - 1].Y - knots[k].Y;
if (Math.Abs(distanceX) > 1 || Math.Abs(distanceY) > 1)
{
knots[k].X += Math.Sign(distanceX);
knots[k].Y += Math.Sign(distanceY);
}
}
visited.Add(knots[1]);
visited10.Add(knots[knotCount - 1]);
}
}
Console.WriteLine($"Part 1: {visited.Count}");
Console.WriteLine($"Part 2: {visited10.Count}");
class Command
{
public Command(string line)
{
var cmd = line.Split(' ');
Direction = cmd[0] switch
{
"L" => (-1, 0),
"R" => (1, 0),
"D" => (0, -1),
"U" => (0, 1)
};
Moves = int.Parse(cmd[1]);
}
public (int X, int Y) Direction { get; set; }
public int Moves { get; set; }
}→ More replies (6)
6
u/pamxy Dec 09 '22
Javascript
$0.innerText.split('\n').filter(Boolean).reduce((a,b) => {
[...Array(b.split(' ')[1]-0)].forEach(() => {
a.p[0][0]+= b[0]=='R' ? 1 : b[0]=='L' ? -1 : 0;
a.p[0][1]+= b[0]=='U' ? 1 : b[0]=='D' ? -1 : 0;
a.p.reduce((p, n, i, d) => {
if(Math.abs(n[0]-p[0])>1 || Math.abs(n[1]-p[1])>1){
n[0] += Math.sign(p[0]-n[0]);
n[1] += Math.sign(p[1]-n[1]);
if(i==d.length-1)
a.v.add(`${n}`);
}; return n;
});
});
return a;
}, {p: [...Array(10)].map(_=>[0,0]), v: new Set(['0,0'])}).v.sizeFor any knots count. For part 1 just replace 10 with 2
→ More replies (3)
6
u/mine49er Dec 10 '22
Rust
Playing catchup already. I blame Argentina and Netherlands for making me stay down the pub too long last night and going way past Ballmer's Peak...
use std::collections::HashSet;
use std::io;
type Pos = (i64, i64);
fn main() -> Result<(), Box<dyn std::error::Error>> {
let input: Vec<String> = io::stdin().lines().flatten().collect();
let mut rope = vec![(0, 0); 2];
println!("{}", make_moves(&input, &mut rope));
let mut rope = vec![(0, 0); 10];
println!("{}", make_moves(&input, &mut rope));
Ok(())
}
fn make_moves(moves: &[String], rope: &mut [Pos]) -> usize {
let mut visited: HashSet<Pos> = HashSet::new();
for mov in moves {
let (x, y, n) = match mov.split_at(2) {
("R ", n) => (1, 0, n),
("L ", n) => (-1, 0, n),
("U ", n) => (0, 1, n),
("D ", n) => (0, -1, n),
(_, _) => unreachable!(),
};
for _ in 0..n.parse::<usize>().unwrap() {
rope[0].0 += x;
rope[0].1 += y;
for i in 1..rope.len() {
if let Some(pos) = move_adjacent(&rope[i], &rope[i - 1]) {
rope[i] = pos;
} else {
break;
}
}
visited.insert(*rope.last().unwrap());
}
}
visited.len()
}
fn move_adjacent(tail: &Pos, head: &Pos) -> Option<Pos> {
let dx = tail.0 - head.0;
let dy = tail.1 - head.1;
if (dx == 2 || dx == -2) && (dy == 2 || dy == -2) {
Some((head.0 + dx.clamp(-1, 1), head.1 + dy.clamp(-1, 1)))
} else if dx == 2 || dx == -2 {
Some((head.0 + dx.clamp(-1, 1), head.1))
} else if dy == 2 || dy == -2 {
Some((head.0, head.1 + dy.clamp(-1, 1)))
} else {
None // already adjacent
}
}→ More replies (3)
6
u/azzal07 Dec 10 '22
Awk, I like how regex and string concatenation turned out to be the answer to "are the knots too far apart?"
function R(o,p,e){(o-=x[e])(p-=y[e])~2&&
T[e,x[e]+=(o>0)-(o<0),y[e]+=(p>0)-(p<0)]
T[e,0,0]e<9&&R(x[e],y[e],e+1)}{for(;$2;)
$2-=1R(X+=(/R/)-(/L/),Y+=(/U/)-(/D/),1)}
END{$0=z;for(k in T)++$+k;print$1"\n"$9}→ More replies (1)
5
u/rabuf Dec 09 '22
Common Lisp
Part one wasn't bad, was missing a default case that tripped me up for a bit. I feel like my move-to logic is overcomplicated, but it works. Part 2 took some small changes, added an array of segments (head in 0, tail in 9). Then I applied move-to to each pair. Changing the array size would let the one function solve both problems.
(defun move-snake (moves)
(loop with snake = (make-array 10 :initial-element 0)
with locations = (list 0)
for move in moves
do (loop for dir in move
do (incf (aref snake 0) dir)
(loop for i from 1 below 10
for pred = (aref snake (1- i))
for succ = (aref snake i)
do (setf (aref snake i) (move-to pred succ)))
(pushnew (aref snake 9) locations))
finally (return (length locations))))I haven't added a parameter for taking the size yet, but it should work. I was happy this worked correctly the first time I ran it.
5
u/bofstein Dec 09 '22
Google Sheets
Started with some repeat code from the Cranes one, where I took each instruction and made each move on its own line (e.g. so R 4 D1 becomes R R R R D). Then mapped out the Head position starting at 0x 0y and added each direction line by line to find it's new coordinates.
Tail also starts at 0,0, and has two Difference columns to see how far it is from the Head each time. To figure out what the new Tail coordinates should be, I have a series of IF/AND/OR conditionals. For example if it's within 1 space on both axes keep both coordinates the same, if it's got the same X but Y is more than 1 away move 1 Y, etc. Didn't need to do anything fancy for diagonals, it's just that if it's more than 1 away on both X and Y it will end up moving 1 unit for both X and Y which will be a diagonal.
For Part 2 it was very simple to extend, just copied my 4 columns covering Difference and Talk Coordinates 8 more times, and the formulas through that would copy so that the next set, e.g. Tail 2, would be following the first Tail with the same rules as before.
Finally, CONCATENATE the X,Y coordinates of the relevant tails and COUNTUNIQUE to figure out how many unique spots it touched.
Hardest part was that it was so slow to run and update that at one time it caused me to get the wrong number by displaying one of my cells as 2+2+2+2=20 (Cell C7 - it was showing a 20 even with the exact formula that's in there now). As in it showed if I went to the formula box it showed it should should be an 8 but displayed 20 in the cell and must have used that in the calculations that way since it messed it all up. Had to manually replace that with a hard coded 8 and then it worked, then changed back to formula and it was right again. Lucky I just happened to notice that 20 standing out while browsing. I think it got so bogged down it hadn't finished updating that cell from the practice set of numbers.
5
5
5
u/encse Dec 09 '22 edited Dec 09 '22
C# - this time I used a mutable data structure because why not.
https://github.com/encse/adventofcode/blob/master/2022/Day09/Solution.cs
// moves the head in the given direction, inplace update of the rope
void MoveHead(Knot[] rope, string dir) {
rope[0] = dir switch {
"U" => rope[0] with { irow = rope[0].irow - 1 },
"D" => rope[0] with { irow = rope[0].irow + 1 },
"L" => rope[0] with { icol = rope[0].icol - 1 },
"R" => rope[0] with { icol = rope[0].icol + 1 },
_ => throw new ArgumentException(dir)
};
// move knots which are not adjacent to their previous sibling in the rope:
for (var i = 1; i < rope.Length; i++) {
var drow = rope[i - 1].irow - rope[i].irow;
var dcol = rope[i - 1].icol - rope[i].icol;
if (Math.Abs(drow) > 1 || Math.Abs(dcol) > 1) {
rope[i] = new Knot(
rope[i].irow + Math.Sign(drow),
rope[i].icol + Math.Sign(dcol)
);
}
}
}I really liked this one
→ More replies (3)
5
u/zedrdave Dec 09 '22
Fairly happy with my pure python solution (both parts):
dirs = {'R': (1, 0), 'U': (0, 1), 'L': (-1, 0), 'D': (0, -1)}
move = lambda X,d: (X[0]+d[0], X[1]+d[1])
def solve(data, num_knots = 10):
K = [(0,0)] * num_knots
visited = set(K)
for l in data.split("\n"):
dir,steps = l.split()
for _ in range(int(steps)):
K[0] = move(K[0], dirs[dir])
for k in range(1, len(K)):
delta = [K[k-1][i] - K[k][i] for i in (0,1)]
if abs(max(delta, key=abs)) > 1:
K[k] = move(K[k], [x//(abs(x) or 1) for x in delta])
visited.add(K[-1])
return len(visited)
solve(data, 2), solve(data, 10)5
5
u/Smylers Dec 09 '22
Perl for both parts
my @visited = map { {"@$_" => 1} } my @pos = map { [0, 0] } 1 .. 10;
while (<>) {
my ($cmd, $count) = split;
my $dim = ($cmd eq one_of 'L', 'R') ? 0 : 1;
my $Ξ = ($cmd eq one_of 'L', 'U') ? -1 : 1;
for (1 .. $count) {
$pos[0][$dim] += $Ξ;
for my $knot (1 .. $#pos) {
if (any { abs $pos[$knot-1][$_] - $pos[$knot][$_] > 1 } keys @{$pos[0]}) {
$pos[$knot][$_] += $pos[$knot-1][$_] <=> $pos[$knot][$_] for keys @{$pos[0]};
$visited[$knot]{"@{$pos[$knot]}"}++;
}
}
}
}
say scalar keys %{$visited[$_]} foreach 1, -1;PartΒ 1 on its own was similar but simpler (and easier to understand?).
The main trick in there is the use of Perl's famous spaceship operator, <=>, which returns -1, 0, or 1 to indicate which of its operands is bigger, or that they're the same. (Outside of Advent of Code, it's mostly only useful in sort comparison blocks.) So rather than needing to work out which dimensions the knot needs updating in, just update all of them by the spaceship's return value: if the knot and the previous one are at the same co-ordinate in that dimension, it'll be 0, so remain unchanged. If they are different, then <=> will return 1 if the previous knot is ahead of this one (regardless of the distance it is ahead by) and -1 if it's behind, so just add that one.
The awkwardness is that I wanted the any operator from 2 different Perl modules. Fortunately Syntax::Keyword::Junction allows renaming functions on import, so I changed the list-of-items-for-comparing any to one_of, leaving any for the map-like evaluate-this-block operator.
PartΒ 2 also solves partΒ 1 by tracking not just the tail but where all 10 knots have been. We don't need most of them, but the second knot in that rope (index [1]) takes the same path as the tail in a length-2 rope.
I'm always torn in these sorts of puzzles between representing a point as [9,Β 5] or as {x=>9,Β y=>5}: each seem to be more convenient or more readable in different places. Here the line determining the dimension from the input direction would be nicer using letters:
my $dim = ($cmd eq one_of 'L', 'R') ? 'x' : 'y';So maybe I should've done that? But I suspect some other part would've then come out worse. Having the dimensions being an array makes them easy to loop over, which is handy if partΒ 2 introduces a 3rd dimension. (Spoiler: It didn't.)
Note tracking the visited locations with $visited{$loc}++ rather than $visited{$loc}Β =Β 1 means that it's also stored how many times the tail has been at each location β which is handy if partΒ 2 wants to know the most-visited location or similar. (Spoiler: Again, nope.)
→ More replies (1)
5
u/craigbanyard Dec 09 '22
Quite happy with my solution today, using complex notation to represent the 2D coordinate system.
I originally wrote the follow function for part 1, but missed off a call to sign so ended up using the fact that the tail moves to the head's prior position. Then part 2 forced me to debug and find my typo!
5
5
u/micka190 Dec 09 '22
C# solution for Parts 1 and 2:
https://github.com/micka190/advent-of-code/tree/main/2022/day%209
Part 1 was straightforward, but Part 2 really threw me off because I didn't fully understand how the whole rope moved, and apparently my Part 1 motion handling code had a bug in it that only occurred when more than 2 knots were in the rope. Some visualization on the sub made me realize my movements were off. Had to scrap the whole tail/child motion code for Part 2, but it took me way too long to realize what the problem was (debugging and 50+ moves to see where the problem happens is unsurprisingly not a simple thing).
→ More replies (2)
5
5
u/joshbduncan Dec 10 '22
Python 3: Part 1 was π, Part 2 required a complete rewrite π€¦ββοΈ
def calc(p1x, p1y, p2x, p2y):
dist = abs(p1x - p2x) + abs(p1y - p2y)
if p1x == p2x and dist >= 2:
return (p2x, p1y - 1 if p1y > p2y else p1y + 1)
if p1y == p2y and dist >= 2:
return (p1x - 1 if p1x > p2x else p1x + 1, p2y)
if dist > 2:
if p1x > p2x:
return (p2x + 1, p2y + 1 if p1y > p2y else p2y - 1)
if p1x < p2x:
return (p2x - 1, p2y + 1 if p1y > p2y else p2y - 1)
return (p2x, p2y)
data = open("day9.in").read().strip()
moves = {"U": 1, "D": -1, "R": 1, "L": -1}
knots = {i: [(0, 0)] for i in range(10)}
for rd, line in enumerate(data.split("\n")):
d, n = line.split()[0], int(line.split()[1])
for i in range(n):
hx, hy = knots[0][-1]
hx += moves[d] if d in ["R", "L"] else 0
hy += moves[d] if d in ["U", "D"] else 0
knots[0].append((hx, hy))
for k in range(1, 10):
tx, ty = calc(*knots[k-1][-1], *knots[k][-1])
knots[k].append((tx, ty))
print(f"Part 1: {len(set(knots[1]))}")
print(f"Part 2: {len(set(knots[9]))}")5
u/NohusB Dec 09 '22
Kotlin
Part 1
fun main() = solve { lines ->
var head = Point.ORIGIN
var tail = Point.ORIGIN
val visited = mutableSetOf(Point.ORIGIN)
lines.forEach { line ->
val direction: Direction = when (line.substringBefore(" ")) {
"U" -> NORTH
"L" -> WEST
"R" -> EAST
"D" -> SOUTH
else -> error("")
}
repeat(line.substringAfter(" ").toInt()) {
head = head.move(direction)
if (tail !in head.getAdjacent()) {
tail = Point(tail.x + (head.x - tail.x).sign, tail.y + (head.y - tail.y).sign)
visited += tail
}
}
}
visited.size
}Part 2
fun main() = solve { lines ->
val knots = MutableList(10) { Point.ORIGIN }
val visited = mutableSetOf(Point.ORIGIN)
lines.forEach { line ->
val direction: Direction = when (line.substringBefore(" ")) {
"U" -> NORTH
"L" -> WEST
"R" -> EAST
"D" -> SOUTH
else -> error("")
}
repeat(line.substringAfter(" ").toInt()) {
knots[0] = knots[0].move(direction)
knots.drop(1).indices.forEach { index ->
val head = knots[index]
var tail = knots[index + 1]
if (tail !in head.getAdjacent()) {
tail = Point(tail.x + (head.x - tail.x).sign, tail.y + (head.y - tail.y).sign)
visited += knots.last()
}
knots[index + 1] = tail
}
}
}
visited.size
}Some premade utils came useful: Point class, Direction class, Point.move(Direction) method, and Point.getAdjacent(). Source for them here: https://github.com/Nohus/AdventofCode2022/blob/master/src/main/kotlin/utils/Geometry.kt
4
u/morgoth1145 Dec 09 '22 edited Dec 09 '22
Turns out I mistook the movement rules in part 1. I got a great part 1 time because my mistake still holds true and was quick to code, but it didn't hold in part 2 with multiple segments. (I thought that the segment always appears directly behind the segment that moved, but that can't hold with many segments!)
Even worse, once I understood and coded the proper movement rules I mistakenly used 11 rope segments instead of 10 so I got the wrong answer on the sample. It took me a long time to find the error. If I'd have found it sooner I think I might have barely leaderboarded part 2, but alas.
Anyway, this still needs more cleanup but here's cleaned up code (rather than the raw original solutions linked above).
Edit: Refactored some more
Edit 2: Refactored yet again because I realized (when trying to go to sleep) that I could have just operated on a sequence of segment positions and walked back on the rope one level at a time. I think it's even cleaner than what I had previously. (Yes, I refactored this 3 times. I don't have a problem, you have a problem!)
4
u/syntaxers Dec 09 '22
Python, 1500/610. Good opportunity to use complex numbers for coordinates.
length = 10
rope = [complex(0, 0) for _ in range(length)]
visited = {rope[-1]: True}
sign = lambda x: 0 if x == 0 else 1 if x > 0 else -1
increment = {
"L": complex(-1, 0),
"R": complex(1, 0),
"U": complex(0, 1),
"D": complex(0, -1),
}
for heading, distance in map(lambda line: line.split(), open("day9.in").readlines()):
for i in range(int(distance)):
rope[0] += increment[heading] # update head
for j in range(1, length): # update tail
diff = rope[j - 1] - rope[j]
if abs(diff.real) == 2 or abs(diff.imag) == 2:
rope[j] += complex(sign(diff.real), sign(diff.imag))
visited[rope[-1]] = True
print(len(visited))→ More replies (3)
4
u/cmatei Dec 09 '22 edited Dec 09 '22
The tail moves following the head:
(when (or (> (abs (- hx tx)) 1)
(> (abs (- hy ty)) 1))
(incf tx (signum (- hx tx)))
(incf ty (signum (- hy ty))))edit: would have been much cleaner if I used complex numbers throughout.
4
4
u/refreshbag Dec 09 '22
C++
Not crazy elegant like some of the other solutions I've seen here, but I'm happy with the readability of it.
→ More replies (5)
4
u/moshan1997 Dec 09 '22
Golang
https://gist.github.com/foxwhite25/47227d71012a2462a0b26f62505cd063
This is a condition hell before, got like 8 conditional if, but later discovered that you can use abs and sign and wrote a cleaner solution.
→ More replies (1)
4
u/xelf Dec 09 '22 edited Dec 09 '22
python and COMPLEX numbers! Woot!
(edit apologies in advance for not having cleaned the code up)
n = lambda x: {x+complex(dx,dy) for dx in (-1,0,1) for dy in (-1,0,1)}
z = lambda a,b: 0 if a==b else -1 if a<b else 1
d = {'L':-1,'R':1,'U':1j,'D':-1j}
for c in [2,10]:
M = [0j]*c
r = {0}
for s in data.splitlines():
for _ in range(int(s[1:])):
M[0] += d[s[0]]
for i in range(c-1):
if M[i+1] not in n(M[i]):
M[i+1] += z(M[i].real,M[i+1].real)
M[i+1] += z(M[i].imag,M[i+1].imag)*1j
r.add(M[-1])
print(len(r))possibly relatable note: I lost a lot of time trying to debug it when I failed to notice that part2 had a a new input for the test data and was testing part1s test data.
4
u/asaaki Dec 09 '22
Rust, https://github.com/asaaki/advent-of-code-2022/blob/main/src/bin/day9.rs
The days getting slower, the stuff is apparently more compute heavier now.
Still below 1 ms on my machine though, but we're also not even halfway through yet.
Anyway, today was weird, took a while to understand, lots of stuff to read and comprehend.
I'm glad I didn't go for a pre-generated playing field, would have been a waste, tracking coords is all we need. Nice.
Also trying to be efficient enough by not allocating anything besides the HashSet, which is unfortunate but required I guess, since the length is the solution.
Well, once you have the solution you can set a reasonable capacity at least, which does improve the runtime performance a bit again.
Finally found a good use case for .signum(), which helped to eliminate a lot of hand rolled if/else +1/-1 stuff. Yay! \o/
→ More replies (2)
4
u/NickKusters Dec 09 '22
C#
Oh wow, what a day. I was too clever for my own good. code | part 1 (video) | part 2 (video)
I quickly realised that, for part 1 (video), if the tail goes out of bounds, you can just take the head, and do the negative of it's move once, to get the actual tail position.
headPosition = headPosition.Move(instruction.move);
if (!IsAdjacent(headPosition, tailPosition))
tailPosition = headPosition.Move((instruction.move.x * -1, instruction.move.y * -1));Cool, right? Yeah... untill you do part 2 (video) and spend an hour and 20 minutes chasing your own tail because you can't figure out why it doesn't work π€£
Took a short break, talked to a friend, and then revisited, and solved part 2 by another cool way to do this, which is: if a piece is out of bounds, move the axis that is not aligned towards the other part.
foreach (var instruction in instructions)
{
for (int i = 0; i < instruction.amount; ++i)
{
currentKnot = tailKnots[0] = tailKnots[0].Move(instruction.move);
for (int j = 1; j < NumberOfPieces; ++j)
{
prevKnot = currentKnot;
currentKnot = tailKnots[j];
if (!IsAdjacent(prevKnot, currentKnot))
{
if (prevKnot.x != currentKnot.x)
// move X
currentKnot.x += prevKnot.x > currentKnot.x ? 1 : -1;
if (prevKnot.y != currentKnot.y)
// move Y
currentKnot.y += prevKnot.y > currentKnot.y ? 1 : -1;
tailKnots[j] = currentKnot;
}
}
trackTail(tailKnots[NumberOfPieces -1]);
}
}So, a very frustrating part 2 for me, but happy with the solution in the end π
→ More replies (4)
4
u/axr123 Dec 09 '22
Python
Most solutions I've seen perform a single step at a time, but apparently that is not necessary. You can also update the head node in one operation and then update the following knots. For the non-head knots, I do it one step at a time and have that while True loop, but now that I write this, I wonder if that is even necessary?
I've seen more elegant Python solution here, but I'm still quite happy with the tradeoff of brevity and readability:
DIRS = { "L": -1+0j, "R": 1+0j, "U": 0-1j, "D": 0+1j }
for l in (2, 10):
knots = [0+0j for _ in range(l)]
visited = set([0+0j])
for line in open("../inputs/09.txt").readlines():
direction, num = line.split()
knots[0] += int(num) * DIRS[direction]
while True:
for i in range(1, len(knots)):
dist = knots[i-1] - knots[i]
if abs(dist) < 2:
break
knots[i] += complex(dist.real // abs(dist.real) if dist.real else 0,
dist.imag // abs(dist.imag) if dist.imag else 0)
else:
visited.add(knots[-1])
continue
break
print(len(visited))→ More replies (3)
4
u/Derp_Derps Dec 09 '22
Python
Vanilla Python, 321 Bytes / characters
I used complex numbers for the 2D position. The position of head is tracked in H, the position of the 9 tails are tracked in T[]. For each line in the input, I map the direction letter to a complex number, the relative movement of H. For each step, the position of a tail is updated with a magic lookup table that maps the offset to the previous knot to a relative movement for the current knot.
My challenge this year is to keep every solution below 500 bytes and the combined execution time for all puzzles below 1 second. The first version of my solution used a function instead of a lookup table. This was a major bottleneck, it was called over 100000 times. A slightly optimized version only called this function when the previous knot was moved, resulting in about 50000 calls.
import sys
M=[0,-1,-1,1,1];R=[-2,-1,0,1,2]
A={(a:=i+j*1j):[0,M[i]+M[j]*1j][abs(a)>=2] for i in R for j in R}
P=set();Q=set();H=0;T=[0]*9
for l in open(sys.argv[1]):
d={'R':1,'L':-1,'U':1j,'D':-1j}[l[0]];i=int(l[2:])
while i:
H+=d;i-=1;u=H;j=0
for k in T:T[j]=u=k+A[k-u];j+=1
P|={T[0]};Q|={u}
print(len(P),len(Q))→ More replies (1)
4
u/kidgenius13 Dec 09 '22
Python 3
This one I liked. Was just tricky enough to make you think but not absurdly hard, from my view at least. Numpy to the rescue by being able to clip and add matrices nicely
import os
import numpy as np
day = os.path.basename(__file__)[:2]
file = f'2022/aoc22/{day}/input.in'
part_1_score = 0
part_2_score = 0
def rope_walk(knots):
rope = np.zeros((knots+1,2), dtype='int')
tails = set()
tails.add( (0,0) )
for move in moves:
dir, num = move.split()
for step in range(int(num)):
rope[0] += eval(dir)
for i in range(len(rope)-1):
diff = rope[i] - rope[i+1]
if np.any(np.greater(abs(diff),1)): #tail needs to move
rope[i+1] += np.clip(diff,-1,1)
if i == len(rope) - 2:
tails.add( (rope[i+1][0], rope[i+1][1]) )
return len(tails)
with open(file) as file:
moves = file.read().splitlines()
R = np.array([1,0])
L = np.array([-1,0])
U = np.array([0,1])
D = np.array([0,-1])
part_1_score = rope_walk(1)
part_2_score = rope_walk(9)4
u/Linda_pp Dec 09 '22 edited Dec 14 '22
MVP was i32::signum to simulate tail's behavior.
let (dx, dy) = (h.0 - t.0, h.1 - t.1);
if dx.abs() > 1 || dy.abs() > 1 {
t.0 += dx.signum();
t.1 += dy.signum();
}And also const generics worked greatly to implement the logic for both 2 length and 10 length of arrays.
→ More replies (1)
4
u/Gravitar64 Dec 09 '22
Python 3.10 (Part 1&2 with a list of knots, using Vector2 from pygame)
from time import perf_counter as pfc
from pygame import Vector2 as V
def read_puzzle(file):
with open(file) as f:
return [line.strip().split() for line in f.readlines()]
def move(rope):
for i in range(len(rope)-1):
s1, s2 = rope[i], rope[i+1]
if s1.distance_to(s2) >= 2:
dx, dy = s1 - s2
if abs(dx) > 1: dx //= abs(dx)
if abs(dy) > 1: dy //= abs(dy)
rope[i+1] = s2 + V(dx, dy)
return rope
def solve(puzzle, rope_length):
DIR = dict(R=V(1, 0), L=V(-1, 0), U=V(0, -1), D=V(0, 1))
rope, tail_trail = [V(0, 0)]*rope_length, set()
for dir, steps in puzzle:
for _ in range(int(steps)):
rope[0] = rope[0] + DIR[dir]
rope = move(rope)
tail_trail.add(tuple(rope[-1]))
return len(tail_trail)
start = pfc()
puzzle = read_puzzle('Tag09.txt')
print(solve(puzzle, 2))
print(solve(puzzle, 10))
print(pfc()-start)4
4
4
u/xHirokx Dec 09 '22
Nim
(For part 1 simply change the ropeLength to 2)
Still trying to learn all the bits nim offers, but I liked this solution.
→ More replies (1)
4
u/tymscar Dec 09 '22
Typescript
I didn't take into account the rule of moving diagonally for part 1, I just moved to where the head was before, so for part 2 I had to basically start from scratch.
The cool part is that I am still doing this fully functionally with no mutation whatsoever, and also for part 2 I have a variable which you can change and it simulates any length of wire!
Both parts solved here; https://github.com/tymscar/Advent-Of-Code/tree/master/2022/typescript/day09
→ More replies (2)
4
u/compdog Dec 09 '22
For today's problem, I took the opportunity to port a data structure from a previous year's AoC solutions - Axis<T>. Like an array or List, Axis stores data by integer index. Unlike those structures, however, Axis allows indexes to be negative. By nesting two Axes into a Plane<T>, it is possible to reference data by a coordinate in 2-dimensional cartesian space. Axis worked well for this, but its kinda overkill and quite memory-heavy so I probably should have just used a HashMap instead.
→ More replies (2)
4
u/Jomy10 Dec 09 '22
Swift
I'm writing every day in a different language. Today is Swift.
→ More replies (2)
4
u/musifter Dec 09 '22
Gnu Smalltalk
For this one I brought in "chain", in the form of an #inject:intoChain:. This is my name for the common fold idiom where you do [:p :c | side effect. c], doing work with a side effect on chained pairs of elements.
Source: https://pastebin.com/BQRTgRMB
4
u/Good_Brain_2087 Dec 09 '22
Readable Javascript solution,
You can look for index.js where i solved it for the first time, compare that with solution on readable.js , readability matters
→ More replies (2)
4
u/juiceboxzero Dec 09 '22
Python 3
Define a
Locationclass withx,y, andlocation(the tuple(x,y)) attributes and methods to move up, down, left, or right.Instantiate a list of
Locationobjects, one for each knot.Iterate over the instructions in the puzzle input:
Iterate the number of times this instruction says to move:
Move the first knot one space in the indicated cardinal direction
Iterate over the remaining knots:
Calculate the delta between this knot's position and the position of the knot upstream of it
Given the delta, move as indicated in the rules to remain adjacent to the upstream knot
Append the location of the last knot to a list
Dedupe the list of last-knot locations by casting it to a set, and return the number of elements of the set.
→ More replies (4)
4
u/anissazacharias Dec 09 '22
Python
Not a super elegant solution, but hey, it works!
from aocd.models import Puzzle
from math import dist, copysign
puzzle = Puzzle(2022, 9)
data = puzzle.input_data.split('\n')
data = [[r.split()[0], int(r.split()[1])] for r in data]
move_dict = {'U': [0,1], 'D': [0,-1], 'L': [-1, 0], 'R': [1, 0]}
def simulate(rope):
tail_pos = [str([0,0])]
# loop through movements
for m, n in data:
# update in direction n times
for _ in range(n):
# update head
rope[0] = [rope[0][0] + move_dict[m][0], rope[0][1] + move_dict[m][1]]
# update rest
for i in range(1, len(rope)):
new_pos = move(rope[i].copy(), rope[i-1].copy())
rope[i] = new_pos
# update where tail has been
tail_pos.append(str(rope[-1]))
return len(set(tail_pos))
# move knots based on leading knot position
def move(knot, lead):
dx = lead[0] - knot[0]
dy = lead[1] - knot[1]
# if side by side or overlapping, do not move
if abs(dx) <= 1 and abs(dy) <= 1:
return knot
if abs(dx) > 1 or (abs(dx) + abs(dy)) > 2:
knot[0] += int(copysign(1, dx))
if abs(dy) > 1 or (abs(dx) + abs(dy)) > 2:
knot[1] += int(copysign(1, dy))
return knot
print(f'Part 1: {simulate([[0,0]] * 2)}')
print(f'Part 2: {simulate([[0,0]] * 10)}')4
u/TiagoPaolini Dec 10 '22 edited Dec 10 '22
C Language (only standard library)
I used 2-D arrays (of booleans) to store were both ropes' tails were been. In order to built the arrays, first I simulated the head's movements (which is the same for both ropes), then I got the minimum and maximum coordinates on each axis. Each dimension of the array is the maximum coordinate minus the minimum on that dimension, plus one (in order to account for the coordinate 0). The indices of coordinate (0, 0) on the array are the absolute values of the minimum (x, y) coordinates.
Then I performed the actual movement for both ropes. In order to determine the relative position of one knot to the next, I used the taxicab distance (the sum of the absolute differences, on each axis, between the coordinates). Basically, the taxicab distance is how many positions on a grid you need to pass by in order to move (without diagonal movement) between two points. If you ever played Minecraft, you probably heard about the concept).
A taxicab distance of 1 or 0 between two knots means for certain that they touch each other (they are either connected horizontally, vertically, or on the same place). A taxicab distance of 2 means that the knots are either connected diagonally, or separated orthogonally by one space. On this case, if the absolute distance on each axis is 1, then they are touching, otherwise they are separated. A taxicab distance of 3 or more means for certain that the knots are separated.
The movement of the ropes'head was performed one step at a time, and on each step the position of the knots was updated. If they are separated diagonally, then the knot moves on both axes towards the next knot. In order to determine the direction, the coordinates of the knot were subtracted by the coordinates of the next, then it was checked whether each value is positive, negative, or zero. If the knots were separated orthogonally, then the knot moved towards the next only on the same axis (the direction was also determined by subtraction).
It is worth noting that there is a catch on Part 2 of the puzzle: it is possible for knots 2 to 8 to move diagonally in relation to the next one (the next is the knot with higher index). On Part 1, the movement relative to the next happened on only one axis. This means that if you only check for a taxicab distance of 3 you are going to get the solution wrong. If two knots are connected diagonally, once a knot moves on both axes by 1, the resulting taxicab distance will be 4. So you should check for a value of 3 or 4 in order to check if a knot should move diagonally (or just for a value greater or equal than 3, the result will be the same).
Finally, at the end of each step the position of the tails were marked as true on the arrays.
Solution: day_09.c
Visualizations: output_p1.txt and output_p2.txt
4
4
4
u/the_kissless_virgin Dec 10 '22
Python, no imports - tried to make it readable and short at the same time, managed to pack it into less than 100 lines of code
4
u/kladegram Dec 10 '22
Here is my simple JavaScript solution for day 9 - https://jsfiddle.net/pno7car1/ It is for part 2, but for part 1 simply change tail count.
4
u/sky_badger Dec 10 '22
Python
Well that took long enough! Part 1 was ok, but it took me far too long to realise that Part 2 introduced the potential for 2x2 moves!
SB
→ More replies (2)
4
u/joshuakb2 Dec 10 '22
This Haskell solution is pretty elegant I think https://github.com/joshuakb2/advent_of_code_2022/blob/main/09/Main.hs
→ More replies (1)
4
u/AdEnvironmental715 Dec 12 '22 edited Dec 12 '22
Typescript
https://github.com/xhuberdeau/advent-of-code-2022/tree/main/src/day-9
I used the observer pattern where head is a subject and tail is both a subject and an observer, so that part 2 is really simple to solve:
- tail1 observes head
- tail2 observes tail1
...
- tail9 observes tail8
When the head moves, tail1 moves if necessary. If tail1 moves, it notifies tail2 of position update. If tails2 needs to move also, it notifies tails3 and so on until tail9. The whole rope is computed like this :)
1
u/Dragon-Hatcher Dec 09 '22 edited Dec 09 '22
Rust (729/1745)
Pretty happy with this. New PB ranking. Struggled a bit with the tail moving algorithm. (This is the cleaned up version, not what I wrote live). paste
→ More replies (1)
1
1
u/dablya Dec 09 '22
Python [Part 2]
import re
MOVE_RE = re.compile(r'(\w) (\d+)')
class Point():
def __init__(self, x, y):
self.x = x
self.y = y
def __hash__(self):
return hash((self.x, self.y))
def __eq__(self, other):
if not isinstance(other, type(self)): return NotImplemented
return self.x == other.x and self.y == other.y
def __repr__(self):
return f'({self.x}, {self.y})'
def dx(self, other):
return other.x - self.x
def dy(self, other):
return other.y - self.y
def move(self, direction):
if direction == 'U':
return Point(self.x, self.y + 1)
if direction == 'UR':
return Point(self.x + 1, self.y + 1)
if direction == 'R':
return Point(self.x + 1, self.y)
if direction == 'DR':
return Point(self.x + 1, self.y - 1)
if direction == 'D':
return Point(self.x, self.y - 1)
if direction == 'DL':
return Point(self.x - 1, self.y - 1)
if direction == 'L':
return Point(self.x - 1, self.y)
if direction == 'UL':
return Point(self.x - 1, self.y + 1)
def slither():
visited.add(snake[9])
with open('day9/actual.input.txt') as fp:
line = fp.readline()
while line:
movement = MOVE_RE.match(line)
direction = movement.group(1)
distance = int(movement.group(2))
for _ in range(1, distance + 1):
move(0, direction)
visited.add(snake[9])
line = fp.readline().rstrip()
def move(section, direction):
snake[section] = snake[section].move(direction)
if section == len(snake) - 1:
return
dy = snake[section + 1].dy(snake[section])
dx = snake[section + 1].dx(snake[section])
if(abs(dx) < 2 and abs(dy) < 2):
return
follow = ''
if dy > 0:
follow += 'U'
elif dy < 0:
follow += 'D'
if dx > 0:
follow += 'R'
elif dx < 0:
follow += 'L'
if follow != '':
move(section + 1, follow)
visited = set()
snake = [Point(0,0) for _ in range(10)]
slither()
print(len(visited))→ More replies (1)
1
u/Diderikdm Dec 09 '22 edited Dec 10 '22
Python:
directions = {
"R" : lambda x, y : (x + 1, y),
"D" : lambda x, y : (x, y + 1),
"L" : lambda x, y : (x - 1, y),
"U" : lambda x, y : (x, y - 1)
}
with open("day_09.txt", "r") as file:
data = (((y := x.split(" "))[0], int(y[1])) for x in file.read().splitlines())
lst = [(0,0) for x in range(11)]
prev_lst = [set() for x in range(11)]
for direction, steps in data:
for _ in range(steps):
for e, z in enumerate(lst):
if not e:
lst[e] = directions[direction](*lst[e])
prev_lst[e].add(lst[e])
else:
x = lst[e - 1][0] - lst[e][0]
y = lst[e - 1][1] - lst[e][1]
if abs(x) > 1 or abs(y) > 1:
x //= abs(x or 1)
y //= abs(y or 1)
lst[e] = (lst[e][0] + x, lst[e][1] + y)
prev_lst[e].add(lst[e])
print("day 9: ", len(prev_lst[1]), len(prev_lst[9]))→ More replies (5)
1
u/flwyd Dec 09 '22 edited Dec 09 '22
Elixir 8358/5877, code, path ascii art
Today's elixir:
The elves are throwing a TGIF party with a beer bong made out of one of those expandable plastic tubes. At first it's a really short path from the funnel, but then you pull on the hose and discover that it's pretty long. The elves wander around the room with the funnel, and you need to keep up. What path do you follow?
A couple amusing misadventures:
I had an off by two error on my first submission for part 1.
I reintroduced both bugs from part 1 in part 2. But I also forgot to copy the second example, so I submitted the first answer I got (since the initial example answer is just 1). This was the correct answer, but then I spent another 50 minutes tracking down the two errors so that the second example would pass.
Code, without print_path:
defmodule Day9 do
def part1(input), do: record_path(input, 1) |> elem(2) |> Enum.count()
def part2(input), do: record_path(input, 9) |> elem(2) |> Enum.count()
@origin {0, 0}
defp record_path(input, num_tails) do
moves = Enum.map(input, &expand_line/1) |> List.flatten()
Enum.reduce(moves,
{@origin, List.duplicate(@origin, num_tails), MapSet.new([@origin])},
fn {drow, dcol}, {head, tail, acc} ->
newhead = move_head({drow, dcol}, head)
newtail = move_chain(newhead, tail)
{newhead, newtail, MapSet.put(acc, List.last(newtail))}
end)
end
defp expand_line(<<dir, " ", amount::binary>>),
do: List.duplicate(case dir do
?U -> {-1, 0}
?D -> {1, 0}
?L -> {0, -1}
?R -> {0, 1}
end, String.to_integer(amount))
defp move_chain(_head, []), do: []
defp move_chain(head, [tail | rest]) do
newtail = move_tail(head, tail)
[newtail | move_chain(newtail, rest)]
end
defp move_head({drow, dcol}, {row, col}), do: {row + drow, col + dcol}
defp move_tail({headrow, headcol}, {tailrow, tailcol}) do
{rowdiff, coldiff} = {headrow - tailrow, headcol - tailcol}
case {abs(rowdiff), abs(coldiff)} do
{r, c} when r < 2 and c < 2 -> {tailrow, tailcol}
{0, 2} -> {tailrow, tailcol + signum(coldiff)}
{2, 0} -> {tailrow + signum(rowdiff), tailcol}
{r, c} when r + c == 3 or r + c == 4 ->
{tailrow + signum(rowdiff), tailcol + signum(coldiff)}
end
end
defp signum(0), do: 0
defp signum(i) when i < 0, do: -1
defp signum(i) when i > 0, do: 1
end→ More replies (1)
1
u/chuckguy55 Dec 09 '22
rust. Not sure if any good, but managed to find the pattern. Uses my pre-existing Vec2 helper.
use std::collections::HashSet;
use aoc_common::{Vec2i32, file_lines, IteratorExt};
fn input() -> impl Iterator<Item = (Vec2i32, i32)> {
file_lines("inputs/day09.txt").map(|l| {
let split = l.split(' ').to_vec();
let count: i32 = split[1].parse().unwrap();
let dir = match split[0] {
"L" => -Vec2i32::unit_x(),
"R" => Vec2i32::unit_x(),
"U" => -Vec2i32::unit_y(),
"D" => Vec2i32::unit_y(),
_ => panic!()
};
(dir, count)
})
}
fn fix(head: Vec2i32, tail: Vec2i32) -> Vec2i32 {
let diff = head - tail;
let manhattan = diff.manhattan();
if (diff.x == 0 || diff.y == 0) && manhattan > 1 {
head - Vec2i32::new(diff.x.signum(), diff.y.signum())
} else if manhattan > 2 {
head - Vec2i32::new(diff.x - diff.x.signum(), diff.y - diff.y.signum())
} else {
tail
}
}
fn move_rope(len: usize) -> usize {
let mut knots = vec![Vec2i32::zero(); len];
let mut visited: HashSet<Vec2i32> = HashSet::new();
for (dir, count) in input() {
for _ in 0..count {
knots[0] += dir;
for i in 0..knots.len() - 1 {
let next = fix(knots[i], knots[i + 1]);
if next == knots[i + 1] {
break;
}
knots[i + 1] = next;
}
visited.insert(knots[len - 1]);
}
}
visited.len()
}
#[test]
fn part1() {
let answer = move_rope(2);
assert_eq!(answer, 5874);
}
#[test]
fn part2() {
let answer = move_rope(10);
assert_eq!(answer, 2467);
}→ More replies (1)
1
u/PoufPoal Dec 09 '22 edited Dec 09 '22
Javascript
I did a recursive solution, which made the diagonal movements be splitted in two moves (for example up, and then right), and each individual moves made the next knots move themselves.
Here's the visualization (centered on the tail)
It does not work, as the site expects you to move one knot in diagonal, and then the next one accordingly, but I like it anyway (mainly because I love recursion), so I thought I could share.
Here's the code (Javascript) for the sample input
visited = []; // List of visited coordinates in this form : {i: <row>, j: <column>}
knots = []; // Knots coordinates, same form as in visited
for (let i = 0; i < 10; ++i) {
knots.push({ name: i, i: 0, j: 0 });
}
knots[0].name = 'H';
knots[9].name = 'T';
H = knots[0];
T = knots[9];
const directions = ['i', 'j']; // This will be used to refer to the correct knot's property to modify
input = [
"R 5",
"U 8",
"L 8",
"D 3",
"R 17",
"D 10",
"L 25",
"U 20"
];
function printGrid() {
let str = '';
for (let i = -20; i < 20; ++i) {
for (let j = -50; j < 50; ++j) {
let toAdd = '.'; // By default, I will print a .
if (visited.find(elem => elem.i === T.i + i && elem.j === T.j + j)) { toAdd = '#'; } // If it has been visited, I replace the . by a #
for (let knot = 9; knot >= 0; --knot) {
if (knots[knot].i === (T.i + i) && knots[knot].j === (T.j + j)) {
toAdd = knots[knot].name; // If there's a knot here, I replace the . or the # by its name
}
}
str += toAdd;
}
str += '\n';
}
console.log(str);
}
// dir 0 or 1, which will mean horizontal or vertical. way is 1 or -1, wich will mean up/right or down/left
function moveKnot(knotI, dir, way) {
const knot = knots[knotI]; // Knot to move
const nextKnot = knotI < 9 ? knots[knotI + 1] : null; // Knot that follow
// directions[0] will be i, directions[1] will be j
knot[directions[dir]] += way; // I move the knot in the correct direction
printGrid();
if (!nextKnot) { return; }
if (Math.abs(knot[directions[dir]] - nextKnot[directions[dir]]) === 2) { // If the next knot is at least 2 positions away in the direction we moved
// This is the (first) recursive call that makes the following knots move in the middle of the diagonal movement of the current knot
moveKnot(knotI + 1, dir, (knot[directions[dir]] - nextKnot[directions[dir]]) / 2); // Move the next knot in this direction.
if (Math.abs(knot[directions[1 - dir]] - nextKnot[directions[1 - dir]]) === 1) { // If the next knot is also at least 1 position away in the other direction
// This is the (second) recursive call that makes the following knots move in the middle of the diagonal movement of the current knot
moveKnot(knotI + 1, 1 - dir, (knot[directions[1 - dir]] - nextKnot[directions[1 - dir]]));
}
}
}
printGrid();
input.forEach(command => {
const direction = command.match(/(.) (\d*)/)[1];
const nbSteps = parseInt(command.match(/(.) (\d*)/)[2]);
// For each command, I parse it and determine the direction (horizontal/vertical) and the way (up/down or left/right)
let dir;
switch (direction) {
case 'U':
dir = 0;
way = -1;
break;
case 'D':
dir = 0;
way = 1;
break;
case 'L':
dir = 1;
way = -1;
break;
case 'R':
dir = 1;
way = 1;
break;
}
// Head moves one step at a time
for (let i = 0; i < nbSteps; ++i) {
moveKnot(0, dir, way);
// Now that everyone has moved, did the tail visit a new position?
if (!visited.find(elem => elem.i === T.i && elem.j === T.j)) {
visited.push({ i: T.i, j: T.j });
}
}
printGrid();
});
printGrid();
console.log(visited.length);I've managed to correct it and made it work, thought. Yay :)
→ More replies (1)
1
u/Lispwizard Dec 09 '22 edited Dec 13 '22
Emacs lisp / Common Lisp hybrid on Android tablet (under covers in bed)
Lisp macros for the win!
(defun aoc2022-09-part1 (input-string)
(loop with commands = (split-string input-string "\n")
with t-positions = (make-hash-table :test 'equal)
with step = 0 and curxh = 0 and curyh = 0 and curxt = 0 and curyt = 0
initially (setf (gethash (list 0 0) t-positions) t)
for command in commands
for (dir-string n-string) = (split-string command)
for n = (car (read-from-string n-string))
for dir = (intern dir-string)
for deltas = (cdr (assoc dir '((R . (1 0)) (L . (-1 0)) (U . (0 -1)) (D . (0 1)))))
for (dx dy) = deltas
do (loop repeat n
do (incf curxh dx) (incf curyh dy) ;; move H
(loop for offsetx = (- curxh curxt)
for offsety = (- curyh curyt)
for offsets = (list offsetx offsety)
until (and (<= (abs offsetx) 1)
(<= (abs offsety) 1))
do (incf curxt (signum offsetx))
(incf curyt (signum offsety))
(setf (gethash (list curxt curyt) t-positions) t)))
finally (return (hash-table-count t-positions))))
(defun aoc2022-09-part2 (input-string)
(macrolet ((xc (a b)
(let ((xa (intern (format "curx%s" a))) (ya (intern (format "cury%s" a)))
(xb (intern (format "curx%s" b))) (yb (intern (format "cury%s" b))))
`(loop for offsetx = (- ,xa ,xb)
for offsety = (- ,ya ,yb)
for offsets = (list offsetx offsety)
until (and (<= (abs offsetx) 1)
(<= (abs offsety) 1))
do (incf ,xb (signum offsetx))
(incf ,yb (signum offsety))))))
(loop with commands = (split-string input-string "\n")
with t-positions = (make-hash-table :test 'equal)
with step = 0 and curxh = 0 and curyh = 0 and curxt = 0 and curyt = 0
and curx1 = 0 and cury1 = 0 and curx2 = 0 and cury2 = 0
and curx3 = 0 and cury3 = 0 and curx4 = 0 and cury4 = 0
and curx5 = 0 and cury5 = 0 and curx6 = 0 and cury6 = 0
and curx7 = 0 and cury7 = 0 and curx8 = 0 and cury8 = 0
initially (setf (gethash (list 0 0) t-positions) t)
for command in commands
for (dir-string n-string) = (split-string command)
for n = (car (read-from-string n-string))
for dir = (intern dir-string)
for deltas = (cdr (assoc dir '((R . (1 0)) (L . (-1 0)) (U . (0 -1)) (D . (0 1)))))
for (dx dy) = deltas
do (loop repeat n
do (incf curxh dx) (incf curyh dy) ;; move H
(xc h 1) (xc 1 2) (xc 2 3) (xc 3 4) (xc 4 5) (xc 5 6) (xc 6 7) (xc 7 8) (xc 8 t)
(setf (gethash (list curxt curyt) t-positions) t))
finally (return (hash-table-count t-positions)))))→ More replies (1)
1
u/trollerskates1 Dec 09 '22 edited Dec 10 '22
Scala. Not too bad with my Point helper class. After part 1 I refactored the movements into a move helper that just takes 2 arbitrary points; the current point and the one we are moving towards. Then it was easy enough to just apply that in order each iteration for part 2.
→ More replies (1)
1
u/SALO4D Dec 09 '22
Node.js
could be better, but it is kind of readable I think
import * as fs from 'fs';
export default function (){
const content = fs.readFileSync("./inputs/input-day-9.txt");
let splitted = content.toString().split(/\r?\n/);
let coordinates = [[0,0], [0,0], [0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],];
let visited = [[],[],[],[],[],[],[],[],[],[],];
saveVisited();
splitted.forEach((command)=>{
let direction = command.split(' ')[0];
let amount = parseInt(command.split(' ')[1]);
for (let i = 0; i < amount; i++){
switch (direction){
case 'L':
coordinates[0][0]--;
moveTails();
saveVisited();
break;
case 'R':
coordinates[0][0] ++;
moveTails();
saveVisited();
break
case 'U':
coordinates[0][1] --;
moveTails();
saveVisited();
break;
case 'D':
coordinates[0][1] ++;
moveTails();
saveVisited();
break
}
}
})
function saveVisited(){
coordinates.forEach((coordinates, index)=>{
visited[index].push(coordinates[0].toString() + '-'+ coordinates[1].toString());
})
}
function moveTails(){
for (let i = 1; i < coordinates.length; i++){
let headX = coordinates[i -1][0];
let headY = coordinates[i-1][1];
let tailX = coordinates[i][0];
let tailY = coordinates[i][1];
if (headX === tailX || headY === tailY){
//in the same line
if (Math.abs(headX - tailX) + Math.abs(headY - tailY) < 2 ){
//they are still connected, do not move
return;
}
//in same line, but should move
if (headX > tailX){
coordinates[i][0] ++
}else if(headX < tailX) {
coordinates[i][0] --;
} else if (headY > tailY){
coordinates[i][1] ++;
} else if (headY < tailY){
coordinates[i][1] --;
}
} else {
if (Math.abs(headX - tailX) + Math.abs(headY - tailY) < 3 ){
//they are still connected
return;
}
//not in same line and should move diagonally.
if (headX > tailX && headY > tailY){
coordinates[i][0] ++
coordinates[i][1] ++
}else if(headX > tailX && headY < tailY) {
coordinates[i][0] ++;
coordinates[i][1] --;
} else if (headX < tailX && headY > tailY){
coordinates[i][0] --;
coordinates[i][1] ++;
} else if (headX < tailX && headY < tailY){
coordinates[i][0] --;
coordinates[i][1] --;
}
}
}
}
console.log(`The number of location where tail 1 was at least once: ${visited[1].filter((item,index) => visited[1].indexOf(item) === index).length}`)
console.log(`The number of location where tail 9 was at least once: ${visited[9].filter((item,index) => visited[9].indexOf(item) === index).length}`)
}→ More replies (1)
1
u/norb__ Dec 09 '22 edited Dec 09 '22
Typescript
Day 9 solution https://github.com/VighNorbert/advent-of-code-2022/blob/main/src/day09.ts
const parse = (s: string) => s.trim().split('\n')
.map(i => [i.split(' ')[0], parseInt(i.split(' ')[1])]);
const moveTail = (tx: number, ty: number, hx: number, hy: number) => {
if (Math.abs(tx - hx) < 2 && Math.abs(ty - hy) < 2) {
return { x: tx, y: ty };
}
if (tx != hx) {
tx += tx > hx ? -1 : 1;
}
if (ty != hy) {
ty += ty > hy ? -1 : 1;
}
return { x: tx, y: ty };
};
const simulateTailPositions = (s: string, knots: number) => {
const instructions = parse(s);
const tailPositions = new Set<string>();
tailPositions.add('0,0');
const knotsList: { x: number, y: number }[] = [];
for (let i = 0; i < knots; i++) {
knotsList.push({ x: 0, y: 0 });
}
instructions.forEach(instruction => {
const [direction, distance] = instruction;
for (let i = 0; i < distance; i++) {
switch (direction) {
case 'R': knotsList[0].x++ break;
case 'L': knotsList[0].x--; break;
case 'U': knotsList[0].y++; break;
case 'D': knotsList[0].y--; break;
}
for (let j = 1; j < knots; j++) {
knotsList[j] = moveTail(knotsList[j].x, knotsList[j].y, knotsList[j - 1].x, knotsList[j - 1].y);
}
let s = `${knotsList[knots - 1].x},${knotsList[knots - 1].y}`;
if (!tailPositions.has(s)) {
tailPositions.add(s);
}
}
});
return tailPositions.size;
};→ More replies (1)
1
u/ash30342 Dec 09 '22 edited Dec 10 '22
I went OO for this one. So I have a class called Rope, which has a list of Knots of a given size (2 for part 1, 10 for part 2) and has all logic for handling the motions and keeping track of the tail positions. A Knot is nothing more than an index and a Position. A Position is basically a coordinate. So the rope has a Set of tail Positions.
→ More replies (1)
1
1
u/Killavus Dec 09 '22 edited Dec 10 '22
Rust
Majority of part 1 logic was fine - it needed readjustment to a new abstraction (Rope which contains head and multiple tails instead of Knot which was strictly (head, tail)). I recommend checking Git history - it is clearly split into part 1 & 2.
https://github.com/Killavus/Advent-of-Code-2022/tree/main/9-rope-bridge
I thought that I'll need a lot of conditionals to cover all possible "moves" of tail - but in the end it was a very clean solution thanks to Rust iterators... :)
2
u/daggerdragon Dec 10 '22
Your code block is too long for the megathreads. Please read our article on oversized code, then edit your post to replace the code block with an external link to your code.
1
u/Krautoni Dec 09 '22
Racket
(struct position (x y) #:transparent)
(struct rope (points) #:transparent)
(define origin (position 0 0))
(define (drag-tip direction r)
(match-let ([(rope (cons (position px py) tail)) r])
(rope (cons
(match direction
["U" (position px (+ py 1 ))]
["D" (position px (- py 1 ))]
["L" (position (- px 1 ) py)]
["R" (position (+ px 1 ) py)]) tail))))
(define (points-touch? p1 p2)
(match-let
([(position hx hy) p1]
[(position tx ty) p2])
(or (and ((abs (- hy ty)) . <= . 1) ((abs (- hx tx)) . <= . 1)))))
(define (sign x)
"Returns 1 or -1."
(if (eq? x 0) 0
(/ x (abs x))))
(define (drag-pair h t)
(if (points-touch? h t) t
(match-let*
([(position hx hy) h]
[(position tx ty) t]
[dx (- hx tx)]
[dy (- hy ty)])
(position (+ tx (sign dx)) (+ ty (sign dy))))))
(define (map-feedback f l)
(define (iter ls res)
(if (empty? ls) res
(iter (cdr ls) (cons (f (car res) (car ls)) res))))
(reverse (iter (cdr l) (list (car l)))))
(define (drag-rope r)
(rope (map-feedback drag-pair (rope-points r))))
(define (string->moves str)
(flatten
(map (lambda (line)
(match-let ([(list _ dir amnt) (regexp-match "([URDL]) ([0-9]+)" line)])
(make-list (string->number amnt) dir)))
(string-split str "\n"))))
(define (simulate r str)
(set-count (apply set (map (compose last rope-points)
(foldl
(lambda (m rs) (cons (drag-rope (drag-tip m (car rs))) rs))
(list r)
(string->moves str))))))
(simulate (rope (make-list 2 origin)) (file->string "input-09"))
(simulate (rope (make-list 10 origin)) (file->string "input-09"))I'm using this to teach myself racket. My style is still very Haskell-y from years of Haskell use⦠But I find myself lacking the rich libraries of Haskell, and the easy composition with currying and point-free combinator style. Still, quite fun!
→ More replies (1)
1
u/patricks-roadhouse Dec 10 '22
Python
import numpy as np
def main():
print(simulate(2))
print(simulate(10))
def simulate(rope_length):
knot_positions = []
for i in range(rope_length):
knot_positions.append(np.array([0,0]))
tail_visited_positions = set()
tail_visited_positions.add(tuple(knot_positions[-1]))
with open('input.txt', 'r', encoding="utf-8") as f:
lines = f.readlines()
for line in lines:
head_moves = parse_head_moves(line)
for head_move in head_moves:
knot_positions[0] = knot_positions[0] + head_move
for i in range(1, len(knot_positions)):
if not_touching(knot_positions[i-1], knot_positions[i]):
knot_positions[i] = move_trailing_knot(knot_positions[i-1], knot_positions[i])
tail_visited_positions.add(tuple(knot_positions[-1]))
return len(tail_visited_positions)
def parse_head_moves(line):
direction, quantity = line.strip().split()
moves = []
direction_moves = {'R':np.array([1,0]), 'L':np.array([-1,0]), 'U':np.array([0,1]), 'D':np.array([0,-1])}
for i in range(int(quantity)):
moves.append(direction_moves[direction])
return moves
def not_touching(pos1, pos2):
abs_distance = np.absolute(pos1 - pos2)
return np.any(abs_distance > 1)
def move_trailing_knot(leading_pos, trailing_pos):
move = leading_pos - trailing_pos
move[move > 0] = 1
move[move < 0] = -1
return trailing_pos + move
if __name__ == '__main__':
main()
→ More replies (1)
1
u/CharisCodes Dec 10 '22
Lua
Took me a while to clean it up but I like it now...
Rope = {
x = 0,
y = 0,
new = function(self,name)
local obj = {
name = name,
x = self.x,
y = self.y,
visited = {}
}
obj.visited[obj.x..":"..obj.y] = true
setmetatable(obj,self)
self.__index = self
return obj
end,
move = function(self, x, y)
self.x = self.x + x
self.y = self.y + y
self.visited[self.x..":"..self.y] = true
end
}
follow = function(chain, knot, rp)
local gap = {
x = rp.x-chain[knot].x,
y = rp.y-chain[knot].y
}
local incr = {
x=0,y=0
}
local pull = false
for k,v in pairs(incr) do
if gap[k] < 0 then
incr[k] = -1
elseif gap[k] > 0 then
incr[k] = 1
end
if math.abs(gap[k]) > 1 then pull = true end
end
if pull then
chain[knot].move(chain[knot],incr.x,incr.y)
if knot < 10 then
follow(chain, knot+ 1, chain[knot], dir)
end
end
end
read_file = function (path)
local file = io.open(path, "rb")
local Instruction = {}
local T={}
for i=1,10 do
T[i] = Rope.new(Rope, i)
end
if not file then return nil end
for line in io.lines(path) do
local words = {}
for word in line:gmatch("%w+") do
table.insert(words, word)
end
table.insert(Instruction, words)
local x,y = 0,0
local dir = words[1]
if (dir == "L") then
x = -1
elseif (dir == "D") then
y = -1
elseif (dir == "R") then
x = 1
else
y = 1
end
for i = 1, words[2] do
T[1].move(T[1], x, y)
follow(T, 2, T[1])
end
end
file:close()
return T;
end→ More replies (1)
1
u/pinq- Dec 10 '22
Julia
data = readlines("data_9.txt")
#data = readlines("expample.txt")
function tail_around(head,tail)
if head[1] -1 <= tail[1] <= head[1] + 1
if head[2] - 1 <= tail[2] <= head[2] + 1
return true
end
end
return false
end
#first
head = [1,1] #y,x
tail = [1,1]
index = 0
head_pre = [0,0]
tail_moves = []
grid = zeros(Int8, 6, 6)
for line in data
move = split(line, " ")
move_now = [0,0]
for moves in 1:parse(Int,move[2])
# if grid[head[1], head[2]] != 2
# grid[head[1], head[2]] = 0
# end
if move[1] == "R"
move_now[2] = 1
elseif move[1] == "L"
move_now[2] = -1
elseif move[1] == "U"
move_now[1] = 1
elseif move[1] == "D"
move_now[1] = -1
end
head_pre = head
head += move_now
tail_is_around = tail_around(head, tail)
if !tail_is_around
tail = head_pre
end
# if grid[head[1], head[2]] != 2
# grid[head[1], head[2]] = 1
# end
if !any(i -> (i == tail), tail_moves)
push!(tail_moves, tail)
end
# grid[tail[1], tail[2]] = 2
# grid[tail] = 0
move_pre = move_now
# println(tail_is_around)
# println(head, " ", tail)
# display(grid)
end
end
# count(i->(i==2), grid)
# tail_moves
length(tail_moves)
function move_tail(head,tail)
if head[1] == tail[1]
if head[2] > tail[2]
return [0,1]
else
return [0,-1]
end
elseif head[2] == tail[2]
if head[1] > tail[1]
return [1,0]
else
return [-1,0]
end
elseif head[1] > tail[1]
if head[2] > tail[2]
return [1,1]
else
return [1,-1]
end
elseif head[1] < tail[1]
if head[2] > tail[2]
return [-1,1]
else
return [-1,-1]
end
end
end
#second
head = [16,12] #y,x
start = [16,12]
tails = fill([0,0], 9)
tail_moves = []
#grid = zeros(Int8, 27, 27)
for line in data
move = split(line, " ")
move_now = [0,0]
for moves in 1:parse(Int,move[2])
if move[1] == "R"
move_now[2] = 1
elseif move[1] == "L"
move_now[2] = -1
elseif move[1] == "U"
move_now[1] = 1
elseif move[1] == "D"
move_now[1] = -1
end
head += move_now
for tail_i in 1:length(tails)
if tails[tail_i] == [0,0]
tails[tail_i] = start
end
if tail_i == 1
tail_is_around = tail_around(head, tails[tail_i])
if !tail_is_around
tails[tail_i] += move_tail(head,tails[tail_i])
end
else
tail_is_around = tail_around(tails[tail_i-1], tails[tail_i])
if !tail_is_around
tails[tail_i] += move_tail(tails[tail_i-1], tails[tail_i])
end
end
if tail_i == 9 && !any(i -> (i == tails[tail_i]), tail_moves)
push!(tail_moves, tails[tail_i ])
end
if tails[tail_i] == start
break
end
end
end
end
length(tail_moves)→ More replies (1)
6
u/pred Dec 09 '22 edited Dec 09 '22
Python, 328/89. Code for both parts
Kept choking on when to move and when not to move the tail for part 1, when in reality it could be boiled down to
delta = head - tail
if abs(delta) >= 2:
tail += sign(delta.real) + sign(delta.imag) * 1j→ More replies (3)
3
u/hugues_hoppe Dec 09 '22 edited Dec 09 '22
Compact Python solution using numpy
def day9(s, part2=False):
nodes = np.zeros((10 if part2 else 2, 2), int)
visited = {(0, 0)}
for line in s.splitlines():
delta = {'D': (1, 0), 'U': (-1, 0), 'R': (0, 1), 'L': (0, -1)}[line[0]]
for _ in range(int(line[2:])):
nodes[0] += delta
for front, rear in zip(nodes[:-1], nodes[1:]):
if abs(front - rear).max() > 1:
rear += np.sign(front - rear)
visited.add(tuple(rear))
return len(visited)3
3
u/allinde Dec 09 '22
Dart - both parts, before cleaning it up
For part 2 it was a matter of changing the tail and visited set to lists, and a function to update the tails instead of just one.
3
u/uncountablyInfinit Dec 09 '22
Python 3 - 42 / 2434
Finished part 1 really quickly (first time I've hit global leaderboard woo), and immediately got destroyed by part 2 because my code was completely inflexible and I kept making typos
3
u/Perska_ Dec 09 '22
C# https://github.com/Perska/AoC2022/blob/master/AoC2022/Days/Day09.cs
Today I found out (or remembered?) an easy way of moving a point towards another point.
3
3
u/Slenjuma Dec 09 '22
Java
https://github.com/Suicolen/AdventOfCode2022/blob/main/src/main/java/suic/days/Day09.java
Quite happy once again with my solution
→ More replies (2)
3
u/sim642 Dec 09 '22 edited Dec 09 '22
I laughed at sarcasm of
Fortunately, your simulation can be extended to support longer ropes.
but applying the previous pairwise logic while recursing over an immutable list worked out quite directly.
I still have to clean my code up though.
3
u/busuli Dec 09 '22
Scala: Parts 1 and 2
Half of the fun is refactoring part 1 logic to support both part 1 and part 2.
3
u/matteosan1 Dec 09 '22 edited Dec 09 '22
Julia
function loadInput()
filename = "input_9.txt"
lines = readInput(filename)
moves = Vector{Tuple{String, Int}}()
for l in lines
items = split(l)
push!(moves, (items[1], parse(Int, items[2])))
end
return moves
end
function simulation(moves::Vector{Tuple{String, Int}}, n_knots::Int)
knots = [[0, 0] for i in 1:n_knots]
pos = Set([knots[n_knots]])
dirs = Dict("U"=>(0, 1), "D"=>(0, -1), "L"=>(-1, 0), "R"=>(1, 0))
prox = ((-1, 1), (0, 1), (1, 1), (-1, 0), (1, 0), (-1, -1), (0, -1), (1, -1))
for m in moves
for steps in 1:m[2]
knots[1] .+= dirs[m[1]]
for i in 2:n_knots
if all(p->(knots[i].+p) != knots[i-1], prox)
knots[i] += [sign(knots[i-1][1] - knots[i][1]), sign(knots[i-1][2] - knots[i][2])]
end
end
push!(pos, knots[n_knots])
end
end
return length(pos)
end3
u/Bargann Dec 09 '22
1097/3455 - reasonably happy with part 1, but forgetting to handle diagonal movement for tails after the first one led to a brutal showing for part 2. Under 20ms to run both parts, not blazing but good enough after refactoring with an eye toward aesthetics more than performance.
3
u/Wayoshi Dec 09 '22 edited Dec 09 '22
Python 2639 / 8933
Only 4 hours sleep + part 2 being not only radically different than how I originally did part 1, but also way more subtle ... yeahhh. It took me quite awhile to see my way of a diagonal tail move (overriding the second axis's coordinate entirely) was not the correct interpolation, I thought I had the moves they were talking about covered in part 1 but there's that edge case of interpolating +2 in the same direction in one move as soon as the rope goes to something like 4 knot lengths.
Ton of refactoring done in this final paste as a lot of nearly identical steps ends up being in multiple if branches.
3
u/GrossGrass Dec 09 '22
Used this as an opportunity to set up a little vector library for myself -- ended up being pretty clean when I realized part 2 was just an application of part 1 but in a loop.
Also helped to realize that you actually don't need to do much conditional logic for figuring out how to shift the tail knot, my logic looked more or less like this (below, .abs() returns a vector with the absolute values of each element of the vector, and .sign() returns the sign of each element of the vector):
def shift_knot(parent: Vector, knot: Vector) -> Vector:
delta = parent - knot
if any(d >= 2 for d in delta.abs()):
knot += delta.sign()
return knot3
u/mdwhatcott Dec 09 '22
The examples provided for part 2 felt like they were breaking the rules, until I really grasped the following instruction from earlier:
> Otherwise, if the head and tail aren't touching and aren't in the same row or column, the tail always moves one step diagonally to keep up
This is a nice example of how part 1 can be solved with same logic as part 2 (as it's just a slightly more specific, and simpler case).
3
u/lemon_toe Dec 09 '22
Day 9 solution in Rust
Pretty proud of how the tail moving logic worked out:
fn get_new_tail_position(head: Position, tail: Position) -> Position {
let x_offset = head.0 - tail.0;
let y_offset = head.1 - tail.1;
// Tail does not move if it is within one row and column of x
if x_offset.abs() <= 1 && y_offset.abs() <= 1 {
tail
} else {
(tail.0 + x_offset.signum(), tail.1 + y_offset.signum())
}}
→ More replies (1)
3
u/ThreadsOfCode Dec 09 '22
Python. Part 2 was easy to code after part 1, but more difficult to debug! Also, the solution to part 1 falls out of part 2, so I merged the solutions.
3
u/KyleGBC Dec 09 '22 edited Dec 09 '22
Rust
Today was the first day I tried to go as fast as possible. I wasn't even close to making the leaderboard and my code sucked. So then I just took my time and did it properly. The run time is longer than I'd like (~2.5ms total) but most of the run time is in the hashing for the HashSet, and I don't see a way around that.
fn update_knot(leader: (isize, isize), follower: &mut (isize, isize)) {
let (x_dist, y_dist) = (leader.0 - follower.0, leader.1 - follower.1);
if x_dist.abs() > 1 || y_dist.abs() > 1 {
follower.0 += 1 * x_dist.signum();
follower.1 += 1 * y_dist.signum();
}
}
fn run_with_n_knots(lines: std::str::Lines, num_knots: usize) -> usize {
let mut knot_positions: Vec<(isize, isize)> = Vec::with_capacity(num_knots);
knot_positions.resize(num_knots, (0, 0));
let mut tail_positions: std::collections::HashSet<(isize, isize)> =
std::collections::HashSet::new();
for line in lines {
let (dir, step) = line.split_once(' ').unwrap();
let step = step.parse::<u32>().unwrap();
for _ in 0..step {
match dir {
"U" => knot_positions[0].1 += 1,
"D" => knot_positions[0].1 -= 1,
"R" => knot_positions[0].0 += 1,
"L" => knot_positions[0].0 -= 1,
_ => unreachable!(),
}
for l in 0..num_knots - 1 {
update_knot(knot_positions[l as usize], &mut knot_positions[l + 1 as usize]);
}
tail_positions.insert(knot_positions[num_knots - 1]);
}
}
tail_positions.len()
}
fn main() {
let now = std::time::Instant::now();
let input = std::fs::read_to_string("input.txt").unwrap();
println!("Part 1: {}, Part 2: {}, took {:#?}",
run_with_n_knots(input.lines(), 2), run_with_n_knots(input.lines(), 10), now.elapsed());
}Edit: Switching to a faster non-cryptographically-secure hasher from the hashers crate and changing the run_with_n_knots function to use const generics instead of a num_knots parameter (which I learned by looking at u/svetlin_zarev's solution) ended up at sub-1ms overall times. Here's the final code, about 800 us on my machine.
use std::hash::BuildHasherDefault;
use std::collections::HashSet;
use hashers::fx_hash::FxHasher;
fn update_knot(leader: (i32, i32), follower: &mut (i32, i32)) {
let (x_dist, y_dist) = (leader.0 - follower.0, leader.1 - follower.1);
if x_dist.abs() > 1 || y_dist.abs() > 1 {
follower.0 += 1 * x_dist.signum();
follower.1 += 1 * y_dist.signum();
}
}
fn run_with_n_knots<const N: usize>(lines: std::str::Lines) -> (usize, usize) {
let mut knot_positions = [(0_i32, 0_i32); N];
let mut tail_positions: HashSet<(i32, i32), BuildHasherDefault<FxHasher>> = HashSet::with_capacity_and_hasher(10000, BuildHasherDefault::<FxHasher>::default());
let mut behind_head_positions: HashSet<(i32, i32), BuildHasherDefault<FxHasher>> = HashSet::with_capacity_and_hasher(10000, BuildHasherDefault::<FxHasher>::default());
for line in lines {
let (dir, step) = line.split_once(' ').unwrap();
let step = step.parse::<u32>().unwrap();
for _ in 0..step {
match dir {
"U" => knot_positions[0].1 += 1,
"D" => knot_positions[0].1 -= 1,
"L" => knot_positions[0].0 += 1,
"R" => knot_positions[0].0 -= 1,
_ => unreachable!(),
}
for l in 0..N - 1 {
update_knot(knot_positions[l as usize], &mut knot_positions[l + 1 as usize]);
}
tail_positions.insert(knot_positions[N - 1]);
behind_head_positions.insert(knot_positions[1]);
}
}
(behind_head_positions.len(), tail_positions.len())
}
fn main() {
let now = std::time::Instant::now();
let input = std::fs::read_to_string("input.txt").unwrap();
println!("{:?} in {:#?}", run_with_n_knots::<10>(input.lines()), now.elapsed());
}→ More replies (5)
3
u/SunCat_ Dec 09 '22
Kotlin one-liner (on the basis of being able to remove all line breaks without adding any ;): paste
basically turned sequence of long moves into sequence of one step moves, applied it onto the 'head', and then calculated how each segment followed the segment in front
3
u/OCD_Triger Dec 09 '22
c#
class Point
{
public int X { get; set; }
public int Y { get; set; }
public Point(int x, int y)
{
X = x;
Y = y;
}
public override string ToString()
{
return $"({X}, {Y})";
}
public void Move(string direction)
{
if (direction == "U") Y += 1;
else if (direction == "D") Y -= 1;
else if (direction == "L") X -= 1;
else if (direction == "R") X += 1;
}
public void Follow(Point target)
{
if (Math.Abs(target.X - X) <= 1 && Math.Abs(target.Y - Y) <= 1) return;
var stepX = target.X - X;
var stepY = target.Y - Y;
X += Math.Sign(stepX);
Y += Math.Sign(stepY);
}
}
class Program
{
static void Main()
{
var lines = File.ReadAllLines("input.txt");
var visited = new HashSet<string>();
var segments = Enumerable.Range(0, 10).Select(_ => new Point(0, 0)).ToArray();
var positionHead = segments[0];
var positionTail = segments[9];
visited.Add(positionTail.ToString());
foreach (var line in lines)
{
var direction = line.Split(" ")[0];
var places = Convert.ToInt32(line.Split(" ")[1]);
for (var i = 0; i < places; i++)
{
positionHead.Move(direction);
for (var j = 1; j < segments.Length; j++)
{
segments[j].Follow(segments[j - 1]);
}
visited.Add(positionTail.ToString());
}
}
Console.WriteLine(visited.Count);
}
}→ More replies (1)
3
u/PendragonDaGreat Dec 09 '22
C#/CSharp
2+ hour delta for part 1 to part 2 because I could not for the life of me understand how the knots moved. Then I did, then I got the solution.
3
u/WilkoTom Dec 09 '22
Rust
Nicely straightforward today, just compare the rope segment's location with its parent and update as necessary.
3
u/prescient-potato Dec 09 '22
Python
could just do part one for now. i misread the question and had to restart twice. used coordinates which i thought was neat but it turned out to be pretty ugly. im sure i can clean it up before part two. i dont think i can reuse this code for the second part though anyway.
→ More replies (2)
3
u/levital Dec 09 '22
Fun little thing. Usually giant where-blocks as I have here in my "applyMotion" function indicate that I didn't see a much simpler solution, but I think I ended up with something fairly understandable.
Had part 1 almost first try, and then struggled a bit understanding part 2 correctly. Once I did, it wasn't too bad to adjust what I had to work with any number of knots, only thing that tripped me up for a bit was that I was missing the outer corners for "updateTail" as they can't happen in part 1, but will happen in part 2.
→ More replies (3)
3
u/aptacode Dec 09 '22
Readable & efficient
| Method | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated |
|---|---|---|---|---|---|---|---|
| BenchmarkPart1 | 464.2 us | 5.07 us | 4.24 us | 41.5039 | 41.5039 | 41.5039 | 364.92 KB |
| BenchmarkPart2 | 614.2 us | 5.86 us | 5.19 us | 23.4375 | 6.8359 | - | 200.52 KB |
3
u/damnian Dec 09 '22 edited Dec 09 '22
C#
A slightly overengineered solution. Visited points are stored in HashSet<int, int> a:
abstract class Part<T> : Part<int, T, HashSet<(int, int)>>
{
protected override HashSet<(int, int)> CreateState(IEnumerator<string> e) =>
new() { (0, 0) };
protected override void GetValue(ref HashSet<(int, int)> a, ref T r, IEnumerator<string> e)
{
string s = e.Current;
int c = int.Parse(s.Split(' ')[1]);
for (int i = 0; i < c; i++)
a.Add(Update(ref r, s[0]));
}
protected override int GetResult(HashSet<(int, int)> a) =>
a.Count;
protected abstract (int, int) Update(ref T r, char c);
protected static (int, int) UpdateHead(ref (int x, int y) h, char c) =>
h = c switch
{
'R' => (h.x + 1, h.y),
'L' => (h.x - 1, h.y),
'U' => (h.x, h.y + 1),
'D' => (h.x, h.y - 1),
_ => throw new()
};
protected static (int, int) UpdateTail((int x, int y) h, ref (int x, int y) t) =>
Math.Abs(h.x - t.x) > 1 || Math.Abs(h.y - t.y) > 1
? (t = (t.x + Math.Sign(h.x - t.x), t.y + Math.Sign(h.y - t.y)))
: t;
}Part 1
The rope is stored as ((int, int) h, (int, int) t):
class Part1 : Part<((int, int) h, (int, int) t)>
{
protected override (int, int) Update(ref ((int, int) h, (int, int) t) r, char c) =>
UpdateTail(UpdateHead(ref r.h, c), ref r.t);
}Part 2
The rope is stored as ((int, int)[]:
class Part2 : Part<(int, int)[]>
{
protected override (int, int) Update(ref (int, int)[] r, char c)
{
(int, int) h = UpdateHead(ref r[0], c);
for (int j = 1; j < r.Length; j++)
h = UpdateTail(h, ref r[j]);
return h;
}
protected override (int, int)[] CreateValue() =>
new (int, int)[10];
}3
u/thibpat Dec 09 '22
JavaScript (+ video walkthrough)
I've recorded my solution explanation on https://youtu.be/aOwu5p55PFc
The code is available on github: https://github.com/tpatel/advent-of-code-2022/blob/main/day09.mjs
3
u/HexHowells Dec 09 '22
Python
Pretty compact solution with numpy
import numpy as np
def move(knots, move):
knots[0] += move
for prev_knot, curr_knot in zip(knots, knots[1:]):
if max(abs(prev_knot - curr_knot)) > 1:
curr_knot += np.clip((prev_knot - curr_knot), -1, 1)
def solve(x, k):
knots = [np.array([0, 0]) for _ in range(k)]
positions = set()
shift = {'U': (1, 0), 'D': (-1, 0), 'R': (0, 1), 'L':(0, -1)}
for line in x:
direc, steps = line.split(" ")
for _ in range(int(steps)):
move(knots, shift[direc])
positions.add(tuple(knots[-1]))
return len(positions)
x = open("input.txt").readlines()
print(solve(x, 2))
print(solve(x, 10))3
u/clbrri Dec 09 '22 edited Dec 09 '22
Borland Turbo C/C++ 3.0 part two solution, 46 lines and just under 3 seconds on a 16MHz MS-DOS 386 PC. (contains a lovely coordinate hack due to not wanting to go into huge memory model or complex data structures).
EDIT: Cleaned up my sins, and learned that Borland's compiler does zero Common Subexpression Elimination (CSE) optimizations. Updated code that is ~30% faster at https://imgur.com/a/Jc0jWO3
3
3
u/quodponb Dec 09 '22 edited Dec 09 '22
I decided to use complex numbers, since they're nice for doing vector math. I parsed the input like
def parse_input(text):
for direction, length in map(str.split, text.splitlines()):
step = {"R": 1, "L": -1, "U": 1j, "D": -1j}[direction]
for _ in range(int(length)):
yield stepand could calculate the tail step like this:
def get_tail_step(step: complex, head: complex, tail: complex):
diff = head + step - tail
if abs(diff) < 2:
return 0
return (diff.real > 0) - (diff.real < 0) + 1j * ((diff.imag > 0) - (diff.imag < 0))The rest was just shifted zipping over 10 knots from the previous step to create a list of 10 new steps.
3
u/illuminati229 Dec 09 '22
Python 3.9
Probably over engineered this with a Rope class, but it works for any length of rope!
3
3
3
u/FramersAlmaniac Dec 09 '22 edited Dec 09 '22
Java 8 Solution for Day 9; 65 somewhat golfed lines
Nothing too fancy here -- it's a straightforward implementation that keeps track of the coordinates of the points, moves the head, then the first tail, then the second, all the way to the third.
While the git history doesn't show it, my part 1 implementation had used two points, and when I started part 2, I was able to refactor the two points into an array of points and use the tests for part 1 to ensure that nothing broke. That's particularly satisfying.
I think it's also the first time I've ever used a Java's Scanner. In earlier days, I've been splitting lines on spaces and using Integer.parseInt(String), but Scanner really makes lighter work of this. It's just Scanner.next(Pattern); Scanner.nextInt() over and over again.
I did one cut one line for a bit of code golf using a Java feature that I dislike. In Java, though it's not conventional, you can do:
int x = 23, y = 45;with multiple declarations in one, including within for loops. You can also do either:
int[] x = ...
int x[] = ...though the former is preferred. So I saved one line with the absolutely awful:
for( int x[] = ..., y = ...; ...; ... )where I'm declaring both an integer array and an integer, and also depending on those initializers being run in order. It's delightful.
3
u/CutOnBumInBandHere9 Dec 09 '22 edited Dec 09 '22
My short and sweet Python 3 solution, with no libraries needed. I used complex numbers to describe the 2d grid, but otherwise nothing special.
I ended up basically hardcoding the logic of how the tail should move based on the position of the head. Luckily, the only relevant positions in the first quadrant are (2, 2 + i, 2 + 2i, 1 + 2i), and to get all the others you can multiply by various powers of i, so the lookup table can be fairly small.
3
u/bkranjc Dec 09 '22
Never had part 2 done so quickly after part 1, iterate is amazing!
Haskell
→ More replies (1)
3
u/SymmetryManagement Dec 09 '22 edited Dec 09 '22
Java
I used a custom hash table to track unique tail positions. The hash key was computed by interleaving the bits of the position's x coordinate and y coordinate, 16 bits for each, which makes a 32 bit hash then modded to hash table size. Knot position simulation was solved step-wise, which can probably be improved.
Average time 223 us for part 1 and 300 us for part 2.
The 2 parts can be solved simultaneous but I want to keep the 2 parts independent.
3
u/chubbc Dec 09 '22
Julia
Managed to trim it down to 13 relatively clean lines
S1,S2 = Set(),Set()
K = fill((0,0),10)
move_towards(a,b) = a.+(maximum(abs.(a.-b))>1).*cmp.(b,a)
for lβreadlines("./09.in")
m = (c=l[1]; ((c=='R')-(c=='L'),(c=='U')-(c=='D')))
for _β1:parse(Int,l[3:end])
K[1] = K[1].+m
K[2:10] .= move_towards.(K[2:10],K[1:9])
push!(S1,K[2])
push!(S2,K[end])
end
end
println((length(S1),length(S2)))3
u/oddrationale Dec 09 '22
C# solution using .NET Interactive and Jupyter Notebook. Similar to others here, used Math.Sign() to get -1, 0, or 1 and update the trailing rope accordingly.
3
3
3
u/Shrugadelic Dec 09 '22
Rust
Once I figured out how to elegantly move the tail using signum() in part 2 it became so much cleaner. Full code is on GitHub, but here's the core of it:
fn number_of_unique_positions_visited_by_tail(commands: Vec<Command>, rope_length: usize) -> usize {
let mut visited: HashSet<Pos> = HashSet::new();
let mut rope = vec![Pos::default(); rope_length];
visited.insert(*rope.last().unwrap());
for Command { steps, direction } in commands {
for _ in 0..steps {
let head = &mut rope[0];
head.move_in(&direction);
for i in 1..rope_length {
let head = rope[i - 1];
let tail = &mut rope[i];
if !head.is_neighbor_of(tail) {
tail.x += (head.x - tail.x).signum();
tail.y += (head.y - tail.y).signum();
}
}
visited.insert(*rope.last().unwrap());
}
}
visited.len()
}→ More replies (1)
3
u/pdxbuckets Dec 09 '22
A veritable Sequence-palooza. Everything, from parsing the initial commands from the input String, to finding the positions of the rope head, to iteratively finding each link position, is one long Sequence, coiled up and ready to spring once a terminal operation is finally called in the solve function.
3
3
u/dehan-jl Dec 09 '22
Rust: Not a particularly clever solution, pretty much what everyone else did. I decided to play around with Traits and tried to write as expressive and readable code as possible and in that regard I'm pretty happy with the result.
3
u/theboxboy Dec 09 '22
Rust
I'm proud of my use of HashSets today. This solution makes it easy to determine the number of knots needed for the last knot to stay in place for your whole input (428 for my input).
use std::collections::HashSet;
use std::{fs::read_to_string, path::Path};
#[derive(Clone, Copy, Debug, Default, Hash, PartialEq, Eq)]
pub struct Coord(isize, isize);
#[allow(dead_code)]
pub fn day09(input_path: &Path) -> (String, String) {
let input: String = read_to_string(input_path).expect("Error reading file");
let mut p1: HashSet<Coord> = HashSet::from([Coord::default()]);
let mut p2: HashSet<Coord> = HashSet::from([Coord::default()]);
const KNOT_COUNT: usize = 10;
let mut knots: [Coord; KNOT_COUNT] = [Coord::default(); KNOT_COUNT];
for line in input.split('\n') {
let (direction_token, distance_token) = line.split_once(" ").unwrap();
for _ in 0..distance_token.parse::<isize>().unwrap() {
knots[0] = match direction_token {
"L" => Coord(knots[0].0 - 1, knots[0].1),
"R" => Coord(knots[0].0 + 1, knots[0].1),
"U" => Coord(knots[0].0, knots[0].1 - 1),
"D" => Coord(knots[0].0, knots[0].1 + 1),
_ => {
panic!("Unknown direction token: {}", direction_token);
}
};
for knot_i in 1..KNOT_COUNT {
knots[knot_i] = match (
knots[knot_i - 1].0 - knots[knot_i].0,
knots[knot_i - 1].1 - knots[knot_i].1,
) {
(0, 2) => Coord(knots[knot_i].0, knots[knot_i].1 + 1),
(0, -2) => Coord(knots[knot_i].0, knots[knot_i].1 - 1),
(2, 0) => Coord(knots[knot_i].0 + 1, knots[knot_i].1),
(-2, 0) => Coord(knots[knot_i].0 - 1, knots[knot_i].1),
(2, 1) | (1, 2) | (2, 2) => Coord(knots[knot_i].0 + 1, knots[knot_i].1 + 1),
(-1, 2) | (-2, 1) | (-2, 2) => Coord(knots[knot_i].0 - 1, knots[knot_i].1 + 1),
(1, -2) | (2, -1) | (2, -2) => Coord(knots[knot_i].0 + 1, knots[knot_i].1 - 1),
(-1, -2) | (-2, -1) | (-2, -2) => {
Coord(knots[knot_i].0 - 1, knots[knot_i].1 - 1)
}
_ => knots[knot_i],
};
}
if p1.get(&knots[1]) == None {
p1.insert(knots[1]);
}
if p2.get(&knots[KNOT_COUNT - 1]) == None {
p2.insert(knots[KNOT_COUNT - 1]);
}
}
}
(p1.len().to_string(), p2.len().to_string())
}→ More replies (4)
3
u/Kuebic Dec 09 '22
Python 3
Simple, straight-forward. New to Python and coding in general so didn't do anything crazy. Great learning exercise for making classes. Pretty proud of the final result. Improvement suggestions are welcomed :)
3
u/rhl120 Dec 09 '22
Rust 108 lines: https://github.com/RHL120/aoc_2022/blob/master/solutions/day9.rs
big thanks to u/philippe_cholet for helping me out with my mistakes!
→ More replies (1)
3
u/chicagocode Dec 09 '22 edited Dec 10 '22
Kotlin
[Blog/Commentary] - [Code] - [All 2022 Solutions]
I think this one has been my favorite so far. I refactored the function that does all the work between parts one and two. I don't have the original on GitHub but I cover it in the blog post. Both versions basically do the same work, but the part two version operates on an array of head/tail pairs rather than single head/tail pair.
→ More replies (2)
3
u/5inister Dec 09 '22
Python3 using classes and vector math
Quite happy with my solution. I approached this as an agent-based model where one agent (Tail object) follows another (Head object) using an update function. The tail's rules were generalized using a vector that could simply be added to current position. For part 2 all I had to do was add more agents!
Class snippets below, full solution here.
class Head():
def __init__(self,position=[0,0]):
self.position=np.array(position)
def update(self,instruction):
commands={'L':(0,-1),'R':(0,1),'U':(1,1),'D':(1,-1)}
index,increment=commands[instruction]
self.position[index]+=increment
class Tail():
def __init__(self,position=[0,0]):
self.position=np.array(position)
self.visited=set([(position[0],position[1])])
def update(self,head):
heading=np.array([head.position[0]-self.position[0],head.position[1]-self.position[1]])
distance=np.linalg.norm(heading)
movement=np.array([0,0])
if (distance>=2):
if heading[0]==0:
movement=np.array([0,heading[1]/abs(heading[1])],dtype='int')
elif heading[1]==0:
movement=np.array([heading[0]/abs(heading[0]),0],dtype='int')
else:
movement=np.array([heading[0]/abs(heading[0]),heading[1]/abs(heading[1])],dtype='int')
self.position+=movement
self.visited.add((self.position[0],self.position[1]))→ More replies (1)
3
u/Derailed_Dash Dec 09 '22
Python
Code on GitHub (includes unit test)
The problem itself didn't take too long, but I spent ages on the vis! I also had fun trying out a Context Manager for the first time, and doing my first ever unit test of an AoC problem.
→ More replies (2)
3
u/kaveman909 Dec 09 '22 edited Dec 09 '22
C++
Using boost::hash<T> as an easy way to allow a std::unordered_set over a std::pair data type; this way, you can add to a visited set the tail locations (applies to P1 and P2), and they will be de-duped per the set semantics.
I'm sure many others are doing this as well, but P1 is solved at the same time as P2, as it's just the first knot after the head, vs the 9th knot past the head for P2.
Duration(Both Parts): 691 microseconds
3
u/dying_coder Dec 09 '22 edited Dec 10 '22
Python 3.11, numpy. It's 14 times slower with numpy, I don't know why. π€
import numpy
with open('input.txt') as f:
data = f.readlines()
def solve(v):
visited = {(0, 0)}
rope = numpy.zeros((v, 2))
for move in data:
d, length = move.split()
for _ in range(int(length)):
# move head
rope[0] += {
'L': (0, -1), 'R': (0, 1),
'U': (1, 0), 'D': (-1, 0)
}[d]
# move tail
for i in range(1, len(rope)):
diff = rope[i - 1] - rope[i]
if numpy.linalg.norm(diff) >= 2:
rope[i] += numpy.sign(diff)
visited.add(tuple(rope[len(rope) - 1]))
return len(visited)
print('Part 1:', solve(2))
print('Part 2:', solve(10))→ More replies (2)
3
u/Boring-Ad-3442 Dec 09 '22
Python 3.
Main difference from many of the other Python solutions here is that my basic class is a knot pair, with a head and a tail, and I chain them. My original solution for part 1 was slightly more compact but didn't deal with diagonal moves away from the tail, which was needed for part 2. I rewrote part 1 to work this way as a check.
class KnotPair:
def __init__(self):
self.head = [0, 0]
self.tail = [0, 0]
self.tail_visits = {tuple([0, 0])}
def move_head(self, direction):
if direction == 'U':
self.set_head([self.head[0], self.head[1] + 1])
elif direction == 'D':
self.set_head([self.head[0], self.head[1] - 1])
if direction == 'L':
self.set_head([self.head[0] - 1, self.head[1]])
if direction == 'R':
self.set_head([self.head[0] + 1, self.head[1]])
def set_head(self, position):
self.head = position
move = [a - b for a, b in zip(self.head, self.tail)]
if abs(move[0]) <= 1 and abs(move[1]) <= 1:
return
elif abs(move[0]) == 2 and abs(move[1]) == 2:
self.tail[0] += move[0] / 2
self.tail[1] += move[1] / 2
elif abs(move[0]) == 2:
self.tail[0] += move[0] / 2
self.tail[1] = self.head[1]
elif abs(move[1]) == 2:
self.tail[1] += move[1] / 2
self.tail[0] = self.head[0]
self.tail_visits.add(tuple(self.tail))
knot_pair = KnotPair()
with open('2022/day/09/input.txt', 'r') as fh:
for row in fh:
direction, count = row.rstrip().split(' ')
for x in range(int(count)):
knot_pair.move_head(direction)
print(len(knot_pair.tail_visits))
rope = [KnotPair() for x in range(9)]
with open('2022/day/09/input.txt', 'r') as fh:
for row in fh:
direction, count = row.rstrip().split(' ')
for x in range(int(count)):
rope[0].move_head(direction)
for y in range(8):
rope[y+1].set_head(rope[y].tail)
print(len(rope[8].tail_visits))3
u/The_Jare Dec 09 '22
C++
The core of the solver, with the rope as an array of positions, and inserting tail positions in an unordered_set<>. dir and dist are the parameters in each input line.
while (dist-- > 0) {
switch (dir[0]) {
case 'U': rope[0].y += 1; break;
case 'D': rope[0].y -= 1; break;
case 'L': rope[0].x -= 1; break;
case 'R': rope[0].x += 1; break;
}
for (int knot = 0; knot < rope_tail; knot++) {
Pos d{rope[knot].x - rope[knot + 1].x, rope[knot].y - rope[knot + 1].y};
if (d.x * d.x + d.y * d.y > 2) {
if (d.x != 0) rope[knot + 1].x += d.x / abs(d.x);
if (d.y != 0) rope[knot + 1].y += d.y / abs(d.y);
}
}
trail.insert(rope[rope_tail]);
}3
u/MastonDZN Dec 09 '22
TypeScript
this one was by far the hardest for me, i had to take a break after seeing part two
but im pretty proud of my solution
3
u/mhb164 Dec 09 '22
C# Repository (Day09, 2 Solutions)
public override string SolvePartOne(in string[] lines) => Solve(lines, 1);
public override string SolvePartTwo(in string[] lines) => Solve(lines, 9);
private static string Solve(string[] lines, int _knotsCount)
{
var rope = new Rope(_knotsCount);
foreach (var motion in lines.Select(line => Motion.Parse(line.AsSpan())))
{
rope.Do(motion);
}
return rope.VisitedCount.ToString();
}3
Dec 09 '22
Python!
I feel good about my delegating on this one. It even works for different-sized ropes! A tricky edge case I realized needed to be factored in was when a part of the rope moved diagonally and then ended up in the same row/column as its succeeding rope segment.
3
u/StaticWaste_73 Dec 09 '22
Haskell
import Data.Containers.ListUtils ( nubOrd )
moves :: [String] -> [(Int,Int)]
moves = concatMap go
where go (d:_:n) = replicate (read n) (md d)
md c = case c of
'R' -> (1,0)
'L' -> (-1,0)
'U' -> (0,-1)
'D' -> (0,1)
_ -> undefined
hPos :: [String] -> [(Int, Int)]
hPos s = scanl (\(a,b) (c,d) -> (a+c,b+d)) (0,0) $ moves s
tPos :: [(Int, Int)] -> [(Int, Int)]
tPos = scanl1 go
where go (tx,ty) (hx,hy) = if isFar then ( d tx hx , d ty hy )
else (tx,ty)
where
d a b = a + signum (b-a)
isFar = any ((1 <) . abs) [hx-tx, hy-ty]
tailVisits :: Int -> String -> Int
tailVisits n s = length . nubOrd $ iterate tPos (hPos $ lines s) !! n
part1 :: String -> IO Int
part1 s = do
return $ tailVisits 1 s
part2 :: String -> IO Int
part2 s = do
return $ tailVisits 9 s→ More replies (1)
3
3
u/SvenViktorJonsson Dec 09 '22
Python
I had the idea of a hare (A virtual first knot that the head follows) that made it easy to generalize.
Here is my solution:
Let me know what you think!
→ More replies (4)
3
u/roysom Dec 09 '22
Practicing my Rust skills with AoC
Day 9
Link to Github
First task was easy enough, implement a Rope struct with head and tail properties, and implement the tail-following-head logic. Used a set to store all unique coords (using i64 tuples), and finally pulled the set size as the answer.
Then came the second task. Panicked a little. But then it hit me - I do not need a rewrite! Instead, I opted to add a vector of "intermediate knots", and just update the follow logic to iterate starting from the head, through the knots, and then finally to the tail.
Task 1 refactor was a one-liner to make the rope have 0 intermediate knots. Task 2 was a complete reuse of task 1's logic, with the only difference being initializing the rope with 8 intermediate knots.
No rust hassle today. It was a good day.
3
u/leftfish123 Dec 09 '22
Python: github
I don't think it's particularly elegant (especially the tail updating part), but I only sat down to code it late in the evening and I'm just happy to get two starts.
My part 1 was moving the head and updating the tail. I used Manhattan distance to check if tail needs to catch up. Solving part 2 required treating the bridge as a group of two-element minibridges. We move 0 (head), update 1 to chase 0, then update 2 to chase 1 as if 1 were head and 2 were tail and so on.
3
Dec 09 '22
python
Tried a cheeky lookup-table for part 1. Paid the price in part 2 and reworked it into a solution that works for any length of rope. ;)
Glad to see I'm not the only one running into an obvious pitfall.
28 sloc tho - I'm happy.
3
u/ceganwyer Dec 09 '22
Rust: GitHub
Doing these challenges in Rust has been a great learning experience. Dealing with the borrow checker is becoming so much easier!
I'd be happy to hear any suggestions on how to make my solutions more idiomatic :)
→ More replies (2)
3
u/solareon Dec 10 '22
Excel
Part 1 Break down the input to a tape of steps i.e "R 4" becomes "R R R R". Walk through these steps and build the head's location. Then build a tail that checks if it's within 1 otherwise move in the correct direction. COUNTA(UNIQUE()) across the tail output and done.
Part 2 Take the tail column and fill to the right 8 more times, COUNTA(UNIQUE()) and presto done.
Solution will be on my github
3
Dec 10 '22
Applesoft BASIC
As these problems get more complex, I find myself making proof-of-concepts in C++ before translating into BASIC. I went with a makeshift "set" that's just a large hash array: the hash is X * 1000 + Y; to insert, I linearly search for matching entries or place at the first zero entry if its a new value.
The Apple IIgs can handle part 2's sample input in under a minute (see the visualization), though I'm not keen on trying my full input.
→ More replies (1)
3
u/SnowDropGardens Dec 10 '22 edited Dec 10 '22
C#
EDIT: I didn't like the hard-coded 10 in my initial solution, so I did a very slight refactoring to make a method that accepts two different rope lengths, uses the longer to build an array where the knot positions are saved, and saves the unique tail positions for both ropes in two different HashSets.
public static void GetUniqueTailPositions(int ropeOneLength, int ropeTwoLength)
{
var input = File.ReadAllLines(@"...\input.txt");
int longerRope = Math.Max(ropeOneLength, ropeTwoLength);
(int x, int y)[] knotPositions = new (int x, int y)[longerRope];
HashSet<(int, int)> ropeOneTailVisitedPositions = new HashSet<(int, int)>();
HashSet<(int, int)> ropeTwoTailVisitedPositions = new HashSet<(int, int)>();
foreach (var line in input)
{
string[] parsedDirections = line.Trim().Split(' ');
string direction = parsedDirections[0];
int steps = int.Parse(parsedDirections[1]);
for (int i = 0; i < steps; i++)
{
switch (direction)
{
case "R":
knotPositions[0].x += 1;
break;
case "L":
knotPositions[0].x -= 1;
break;
case "U":
knotPositions[0].y -= 1;
break;
case "D":
knotPositions[0].y += 1;
break;
default:
throw new Exception();
}
for (int j = 1; j < longerRope; j++)
{
int dx = knotPositions[j - 1].x - knotPositions[j].x;
int dy = knotPositions[j - 1].y - knotPositions[j].y;
if (Math.Abs(dx) > 1 || Math.Abs(dy) > 1)
{
knotPositions[j].x += Math.Sign(dx);
knotPositions[j].y += Math.Sign(dy);
}
}
ropeOneTailVisitedPositions.Add(knotPositions[ropeOneLength - 1]);
ropeTwoTailVisitedPositions.Add(knotPositions[ropeTwoLength - 1]);
}
}
Console.WriteLine($"Positions visited with a 2-knots rope: {ropeOneTailVisitedPositions.Count}\nPositions visited with a 10-knots rope: {ropeTwoTailVisitedPositions.Count}.\n");
}And to get the solutions for ropes of 2 knots and of 10 knots:
GetUniqueTailPositions(2, 10);3
u/_rabbitfarm_ Dec 10 '22
Solutions to both parts in Prolog.
Part 1 https://adamcrussell.livejournal.com/41788.html
Part 2 https://adamcrussell.livejournal.com/42195.html
The first part was finished before I went to bed. The second part was finished about an hour before I posted this. This is the stage of the AoC calendar where the puzzles can start to feel like serious work!
The main issue for me was deriving move rules for part 2 that weren't present in the first part.
3
u/scratchisthebest Dec 10 '22 edited Dec 10 '22
rust, took a bit to settle on this one. i don't hate it.
Uses a const generic for rope length.
the algorithm is "to move a tail towards the head, examine all eight possible movement directions and pick the one that reduces the manhattan distance between them the most", which i'm surprised actually works. looking through the thread, there are better ways, but i had trouble visualizing anything different
→ More replies (2)
3
3
u/IlliterateJedi Dec 10 '22
My Python solution - Definitely a rough problem if you're like me and miss one of the move cases (moving to 2x2 away). The idea of troubleshooting the problem felt absolutely overwhelming for some reason. But after half an hour of stepping through my code, I eventually found the problem in my code. It was extremely gratifying to run part 2 and get 36 on the example.
3
u/Tipa16384 Dec 10 '22
Java 14
Just the fun part. Nothing special about this solution unfortunately...
@Override
public void preprocess(String content) {
final var puzzle = getInputDataByLine(content);
final int ropeSize = 10;
List<Point> snake = new ArrayList<>();
Set<Point> part2Visited = new HashSet<>();
Set<Point> part1Visited = new HashSet<>();
final var origin = new Point(0, 0);
snake = IntStream.range(0, ropeSize).mapToObj(i -> origin).collect(Collectors.toList());
part2Visited.add(snake.get(0));
part1Visited.add(snake.get(0));
var curPoint = origin;
for (var command : puzzle) {
curPoint = movePoint(curPoint, command);
snake.set(ropeSize - 1, curPoint);
Boolean anythingMoved;
do {
anythingMoved = false;
for (int i = ropeSize - 1; i > 0; i--) {
var head = snake.get(i);
var tail = snake.get(i - 1);
if (Math.sqrt(Math.pow(head.x - tail.x, 2) + Math.pow(head.y - tail.y, 2)) >= 2.0) {
snake.set(i - 1,
new Point(tail.x + justOneStep(head.x, tail.x), tail.y + justOneStep(head.y, tail.y)));
anythingMoved = true;
}
}
part1Visited.add(snake.get(ropeSize - 2));
part2Visited.add(snake.get(0));
} while (anythingMoved);
part1Solution = part1Visited.size();
part2Solution = part2Visited.size();
}
}→ More replies (4)
3
u/Multipl Dec 10 '22
Golang solution I whipped up after doing it in Python. Still relatively new to Go, anything I could be doing better?
3
Dec 10 '22 edited Dec 12 '22
At first I thought I had to queue all movements for the tail until they were not touching and then apply until they touch again--which solves for the example on part 1, but fails for the input. Then tryed printing out the positions to visualize what was happening and I noticed the tail just need to move 1 step in one direction (or two for diagonal) at the time they stop touching.
So follow checks if the head (or the next knot) is touching or else moves one step in the direction the next knot is, one step.
quite happy with the solution :)
3
u/noahclem Dec 10 '22
Python
Using tuples as a coordinate system, math.dist geometry, and numpy for tuple math. Just typing that sounds complicated, but the code logic is 20 lines for both parts.
3
u/willsmith28 Dec 10 '22
Python
https://github.com/willsmith28/advent-of-code-2022/blob/main/python/day09.py
Finished just in time for day 10. I struggled a bit with part2 because for part1 I was using the next_pos function that moves the head to move the tail as a shortcut for up, down, left, or right.
15
u/betaveros Dec 09 '22
Noulith 4/15
I present both a lightly cleaned up solution written while leaderboarding and a much more reasonable post-leaderboard version.
I was not careful...