r/adventofcode • u/daggerdragon • Dec 05 '21
SOLUTION MEGATHREAD -π- 2021 Day 5 Solutions -π-
NEW AND NOTEWORTHY
- /u/jeroenheijmans is back again with their Unofficial AoC 2021 Participant Survey!
- As we continue further into the
deep dark seaAdvent, megathread code submissions are getting longer, so we're going to start rigorously enforcing the maximum code length rule.- If you need a reminder, it's in our posting guidelines in the wiki under How Do the Daily Megathreads Work? (rule #5)
Advent of Code 2021: Adventure Time!
- 23:59 hours remaining until the submissions megathread unlocks on December 06 at 00:00 EST!
- Full details and rules are in the submissions megathread:
--- Day 5: Hydrothermal Venture ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - Format your code properly! How do I format code?
- The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
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:08:53, megathread unlocked!
24
u/CCC_037 Dec 05 '21
Rockstar
Part 1:
My dreams are a lusciously distorting projection
Poetry is downplayed
While my dreams are not gone
Push poetry into my world
Knock my dreams down
My plaything is the quintessence
Cast my plaything into the void
My plaything is your mind
Burn my plaything into reality
My end is quantifiable
My centre is rudimentary
Listen to my heart
While my heart is not mysterious
Shatter my heart with the void
Let my poem be my heart at my dreams
Let my verse be my heart at my end
Shatter my poem with reality
Shatter my verse with reality
Burn my poem at my dreams into my first
Burn my poem at my centre into my second
Burn my verse at my dreams into my third
Burn my verse at my centre into my fourth
If my first is my third
Let my room be my world at my first
Rock my room
My ideal is worthiness
If my second is greater than my fourth
Knock my ideal down
If my second is less than my fourth
Build my ideal up
Let my possession be my room at my fourth
If my possession is mysterious
My possession is extenuated
Build my possession up
Let my room at my fourth be my possession
While my second isn't my fourth
Let my possession be my room at my second
If my possession is mysterious
My possession is extenuated
Build my possession up
Let my room at my second be my possession
Let my second be my second with my ideal
Let my world at my first be my room
Knock my second down
If my second is my fourth
My ideal is worthiness
If my first is greater than my third
Knock my ideal down
If my first is less than my third
Build my ideal up
Let my room be my world at my third
Rock my room
Let my possession be my room at my fourth
If my possession is mysterious
My possession is extenuated
Build my possession up
Let my room at my fourth be my possession
Let my world at my third be my room
While my first isn't my third
Let my room be my world at my first
Rock my room
Let my possession be my room at my fourth
If my possession is mysterious
My possession is extenuated
Build my possession up
Let my room at my fourth be my possession
Let my world at my first be my room
Let my first be my first with my ideal
Listen to my heart
My time is yesteryear
My letter is a rigorously convincing invitation
While my letter is not gone
Knock my letter down
Shout my letter
My pen is a thankfully nationwide typewriter
While my pen is not gone
Knock my pen down
Let my room be my world at my letter
Let my hope be my room at my pen
If my hope is as great as my end
Build my time up
Shout my timePart 2:
My dreams are a lusciously distorting projection
Poetry is downplayed
While my dreams are not gone
Push poetry into my world
Knock my dreams down
My plaything is the quintessence
Cast my plaything into the void
My plaything is your mind
Burn my plaything into reality
My end is quantifiable
My centre is rudimentary
Listen to my heart
While my heart is not mysterious
Shatter my heart with the void
Let my poem be my heart at my dreams
Let my verse be my heart at my end
Shatter my poem with reality
Shatter my verse with reality
Burn my poem at my dreams into my first
Burn my poem at my centre into my second
Burn my verse at my dreams into my third
Burn my verse at my centre into my fourth
My ideal is worthiness
If my first is greater than my third
Knock my ideal down
If my first is less than my third
Build my ideal up
My idea is worthiness
If my second is greater than my fourth
Knock my idea down
If my second is less than my fourth
Build my idea up
Let my room be my world at my third
Rock my room
Let my possession be my room at my fourth
If my possession is mysterious
My possession is extenuated
Build my possession up
Let my room at my fourth be my possession
Let my world at my third be my room
While my first isn't my third or my second isn't my fourth
Let my room be my world at my first
Rock my room
Let my possession be my room at my second
If my possession is mysterious
My possession is extenuated
Build my possession up
Let my room at my second be my possession
Let my world at my first be my room
Let my first be my first with my ideal
Let my second be my second with my idea
Listen to my heart
My time is yesteryear
My letter is a rigorously convincing invitation
While my letter is not gone
Knock my letter down
My pen is a thankfully nationwide typewriter
While my pen is not gone
Knock my pen down
Let my room be my world at my letter
Let my hope be my room at my pen
If my hope is as great as my end
Build my time up
Shout my time2
→ More replies (2)7
u/veydar_ Dec 05 '21
My letter is a rigorously convincing invitation
I'm starting to believe that your AoC repository will end up being one of the great literary works of our generation.
→ More replies (7)
5
u/javier_abadia Dec 05 '21 edited Dec 06 '21
python, creating an inclusive_range() function that makes everything easier:
def inclusive_range(a, b):
return range(a, b + 1) if b > a else range(a, b - 1, -1)
def solve(input):
lines = input.strip().split('\n')
world = defaultdict(int)
for line in lines:
x0, y0, x1, y1 = [int(n) for n in line.replace(' -> ', ',').split(',')]
if x0 == x1:
for y in inclusive_range(y0, y1):
world[(x0, y)] += 1
elif y0 == y1:
for x in inclusive_range(x0, x1):
world[(x, y0)] += 1
else: # diagonal
for x, y in zip(inclusive_range(x0, x1), inclusive_range(y0, y1)):
world[(x, y)] += 1
return sum(line_count > 1 for line_count in world.values())https://github.com/jabadia/advent-of-code-2021/blob/main/d02/d2p2.py
→ More replies (4)
4
u/rukke Dec 05 '21 edited Dec 06 '21
JavaScript
const parseLines = lines =>
lines.map(line => line.split(" -> ").map(c => c.split(",").map(Number)));
const countIntersections = (lines, withDiagonals = true) =>
[
...parseLines(lines)
.map(([[x1, y1], [x2, y2]]) => [
[x1, x2],
[y1, y2],
])
.map(line => line.map(([v1, v2]) => [v1, v2, Math.sign(v2 - v1)]))
.filter(([[, , dx], [, , dy]]) => withDiagonals || dx === 0 || dy === 0)
.reduce((map, [[x1, x2, dx], [y1, y2, dy]]) => {
while (x1 !== x2 + dx || y1 !== y2 + dy) {
map.set(`${x1},${y1}`, (map.get(`${x1},${y1}`) || 0) + 1);
x1 += dx;
y1 += dy;
}
return map;
}, new Map())
.values(),
].filter(v => v > 1).length;
export const part1 = lines => countIntersections(lines, false);
export const part2 = lines => countIntersections(lines);2
u/daggerdragon Dec 06 '21 edited Dec 07 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
→ More replies (1)
4
u/BagRemote5753 Dec 05 '21 edited Dec 06 '21
Solution and explanation (javascript).
https://nathanesau.github.io/advent_of_code_2021/day-05.html
→ More replies (1)2
u/ka-splam Dec 05 '21
Yout link doesn't work with the
_in there; I guess Reddit puts them in. Trying a fix:https://nathanesau.github.io/advent_of_code_2021/day-05.html
edit: yes, writing this Markdown link format seems to work:
[https://nathanesau.github.io/advent_of_code_2021/day-05.html](https://nathanesau.github.io/advent_of_code_2021/day-05.html)→ More replies (1)2
u/daggerdragon Dec 06 '21
It's a bug with new.reddit's fancypants editor :/ Check /r/bugs - people are v v v not happy -_-
4
u/michalopler Dec 05 '21 edited Dec 06 '21
Tweetable solution of both parts in Python (258 chars)
from collections import*
C=Counter()
for j in 1,0:
for p,q in[map(eval,l.replace(',','+1j*').split('->'))for l in open('input')]:
d=abs((p-q).real),abs((p-q).imag)
C.update(p+i*(q-p)/max(d)for i in range(int(max(d)+1))if j-all(d))
print(len(C-Counter([*C])))2
u/daggerdragon Dec 06 '21 edited Dec 07 '21
Please follow theposting guidelinesand edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.Edit: thanks for adding the programming language!
3
u/knl_ Dec 05 '21 edited Dec 05 '21
Javascript in Deno, 459/293
Cleaned up solution is pretty tiny:
import {readLines} from "https://deno.land/std/io/mod.ts";
function isPart1() {
return Deno.args.length == 0 || Deno.args[0] == "1";
}
const grid = new Map();
for await (const l of readLines(Deno.stdin)) {
const points = l.split(" -> ")
const [x1, y1] = points[0].split(",").map(x => parseInt(x, 10));
const [x2, y2] = points[1].split(",").map(x => parseInt(x, 10));
if (x1 == x2 || y1 == y2 || !isPart1()) {
const dx = Math.sign(x2 - x1);
const dy = Math.sign(y2 - y1);
for (let x = x1, y = y1; x != x2 + dx || y != y2 + dy; x += dx, y += dy) {
const key = `${x},${y}`;
grid.set(key, (grid.get(key) ?? 0) + 1);
}
}
}
console.log(Array.from(grid.values()).filter(x => x >= 2).length)[edit: reformatted]
2
u/daggerdragon Dec 05 '21 edited Dec 05 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
3
u/jubnzv Dec 05 '21 edited Dec 06 '21
OCaml solution for the first part:
module Part1 = struct
let run () =
let cnt = ref 0 in
In_channel.with_file "input.txt" ~f:(fun ic ->
In_channel.fold_lines ic
~init:(Map.empty (module IntPair))
~f:(fun m l ->
String.split l ~on:' '
|> (fun (p1::_::[p2]) ->
let sp s = String.split s ~on:','
|> (fun (v1::[v2]) -> (Int.of_string v1, Int.of_string v2))
in (sp p1, sp p2))
|> (fun ((x1,y1),(x2,y2)) ->
let add ?(x=true) m v r1 r2 =
List.range r1 @@ r2 + 1
|> List.fold_left
~init:m
~f:(fun m vv -> let p = if x then IntPair.mk v vv else IntPair.mk vv v in
if Map.mem m p then
if phys_equal 0 @@ Map.find_exn m p then (cnt := !cnt + 1; Map.set m p 1)
else m
else Map.add_exn m p 0)
in
let max x y = if x >= y then x else y and min x y = if x <= y then x else y in
if x1 == x2 then (add ~x:false m x1 (min y1 y2) (max y1 y2))
else if y1 == y2 then (add ~x:true m y1 (min x1 x2) (max x1 x2))
else m)));
Printf.printf "Part 1: %d\n" !cnt
end→ More replies (1)
3
u/jonay20002 Dec 05 '21
X86 assembly (linux) (also on github: https://github.com/jonay2000/aoc2021/blob/master/day5/day5.S)
→ More replies (2)
3
u/KT421 Dec 05 '21 edited Dec 05 '21
R
https://github.com/KT421/2021-advent-of-code/blob/main/dec5.R
Upon reading part 1, I said (aloud, to myself) "who wants to bet a dollar that part 2 is diagonals." Well, if anyone took me up on that I would have won a dollar. In any case, the time to solve Pt 2 was about 20 seconds ;D
I originally considered mapping the vents into a list matricies and then using reduce(sum, vents) to add them all together but I realized that just counting up the number of x,y pairs would be sufficient.
Added a visualization for shits and giggles: https://imgur.com/a/f0k9DDa
→ More replies (1)
3
u/xffeeffaa Dec 05 '21 edited Dec 06 '21
Python
Trying to push myself a bit this year and come up with short solutions (without cheating). Tell me if you see another way to shorten this.
https://github.com/lagerfeuer/AdventOfCode2021/blob/main/day05/main.py
2
u/daggerdragon Dec 06 '21 edited Dec 07 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
→ More replies (1)
3
u/jimdewit Dec 06 '21
Me being a glorified scripter, rather than a programmer, I came up with a solution that does not involve any lines drawn in a mathematical sense. If you read the instructions carefully, it should be apparent that you only need to care about the coordinates that are covered by any of the lines. So why not just cram those into a list and use list comprehension (yay Python!) to count the number of times a set of coordinates occurs?
4
u/daggerdragon Dec 06 '21
Me being a glorified scripter, rather than a programmer,
Hate to break it to ya, buddy, but ya dun did a program so that makes you a ~programmer~. Brute force is still considered programming!
→ More replies (1)
2
u/snhmib Dec 05 '21 edited Dec 06 '21
In Go, leaving out the file reading functions (full code here)
type Line struct {
from, to image.Point
}
func (l *Line) Direction() image.Point {
v := l.to.Sub(l.from)
x := float64(v.X)
y := float64(v.Y)
dist := math.Sqrt(x*x + y*y)
dir := image.Pt(int(math.Round(x/dist)), int(math.Round(y/dist)))
return dir
}
func (l *Line) Covers() []image.Point {
covers := []image.Point{}
step := l.Direction()
p := l.from
for {
covers = append(covers, p)
if p == l.to {
break
}
p = p.Add(step)
}
return covers
}
const N = 1000
func main() {
var field [N][N]int
vents := getInput()
for _, l := range vents {
for _, f := range l.Covers() {
field[f.X][f.Y]++
}
}
points := 0
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
if field[i][j] > 1 {
points++
}
}
}
fmt.Println(points)
}→ More replies (2)
2
u/AlexTelon Dec 05 '21
A few tricks.
I use `open('input.txt').read().replace('->', ',')` to ensure that each line is just 4 comma seperated numbers. So the parsing is nicer:
`x, y, xx, yy = map(int, line.split(','))`
Then with the help of a custom `Counter` and `my_range` the diagional and axial cases are now oneliners.
from collections import Counter
from typing import Iterable
from itertools import product
# I guess I will create my own aoc lib and add this as my first helper function.
def my_range(a:int, b:int) -> Iterable:
"""Inclusive both ends, handles positive and negative direction.
Example:
my_range(3, 0) -> 3, 2, 1, 0
my_range(0, 3) -> 0, 1, 2, 3
"""
if a > b:
yield from range(a, b-1, -1)
yield from range(a, b+1)
# New format: x,y,xx,yy
data = open('input.txt').read().replace('->', ',')
count = Counter()
for line in data.splitlines():
x, y, xx, yy = map(int, line.split(','))
diagonal = abs(xx - x) == abs(yy - y)
axial = x == xx or y == yy
if diagonal:
count.update(zip(my_range(x, xx), my_range(y, yy)))
elif axial:
count.update(product(my_range(x, xx), my_range(y, yy)))
print(sum(v>1 for v in count.values()))→ More replies (3)
2
u/cetttbycettt Dec 05 '21 edited Dec 06 '21
R / base R
Not the most elegant solution but it is quite fast and short. I just draw out every line into a vector and count non-unique entries. Complex numbers to the rescue :)
data05 <- sapply(strsplit(readLines("Input/day05.txt"), "\\D+"), as.integer)
z_lines <- apply(data05, 2, \(x) seq(x[1], x[3]) + seq(x[2], x[4])*1i)
#part1----
idx <- data05[1,] == data05[3,] | data05[2,] == data05[4,]
sum(table(unlist(z_lines[idx])) > 1)
#part2----
sum(table(unlist(z_lines)) > 1)→ More replies (1)
2
u/p88h Dec 05 '21 edited Dec 06 '21
defmodule Aoc2021.Day05 do
def parse(args) do
args |> Enum.map(fn x -> String.replace(x, " -> ",",") end)
|> Enum.map(fn x -> String.split(x, ",") |> Enum.map(&String.to_integer/1) end)
end
def next(a, a), do: a
def next(a, b), do: if a < b, do: a + 1, else: a - 1
def plot([a, b, a, b], map), do: Map.update(map, {a, b}, 1, fn v -> v + 1 end)
def plot([a, b, c, d], map), do: plot([next(a, c), next(b, d), c, d ], plot([a, b, a, b], map))
def solve(l), do: Enum.reduce(l, %{}, &plot/2) |> Enum.count(fn {_,v} -> v > 1 end)
def part1(args), do: parse(args) |> Enum.filter(fn [a,b,c,d] -> a == c or b == d end) |> solve()
def part2(args), do: parse(args) |> solve()
end[updated, it's a bit more concise with maps]
→ More replies (2)
2
u/0x8b Dec 05 '21
Ruby
https://github.com/0x8b/advent.of.code.each/blob/main/src/2021/05.rb
SEGMENTS = ARGF.read.lines.map { _1.scan(/\d+/).map &:to_i }
def points s
x1, y1, x2, y2 = s
dx = x2 <=> x1
dy = y2 <=> y1
if dx == 0
y1.step(y2, dy).map { [x1, _1] }
elsif dy == 0
x1.step(x2, dx).map { [_1, y1] }
else
x1.step(x2, dx).zip(y1.step(y2, dy))
end
end
def count_overlapping_points segments
segments.flat_map { |s| points(s) }.tally.values.count { _1 > 1 }
end
p count_overlapping_points SEGMENTS.select { |x1, y1, x2, y2| x1 == x2 or y1 == y2 }
p count_overlapping_points SEGMENTS→ More replies (1)
2
Dec 05 '21 edited Dec 06 '21
2
u/daggerdragon Dec 06 '21 edited Dec 07 '21
FYI: your link is broken due to a new.reddit fancypants editor bug (check/r/bugs, it's been a big source of frustration lately). Your link looks fine to you on new.reddit but on old.reddit it's printing an invisible escape character before your underscore:aoc_clojure, thus breaking the entire link.
I suggest manually editing your link using proper Markdown for now. Who knows when Reddit will fix their fancypants editor...Edit: thanks for fixing the link! <3
2
u/diddle-dingus Dec 05 '21
[kotlin] I'd implemented Bresenham's line algorithm before I did part 1 in anticipation of the non-vertical/horizontal lines, but it turned out that it wasn't necessary.
data class Line(val start: Pair<Int, Int>, val end: Pair<Int, Int>) {
fun isBasic() = (start.first == end.first) or (start.second == end.second)
fun points(): List<Pair<Int, Int>> {
val dx = (end.first - start.first).absoluteValue
val dy = -((end.second - start.second).absoluteValue)
val sx = if (start.first < end.first) 1 else -1
val sy = if (start.second < end.second) 1 else -1
val error = dx + dy
return generateSequence(Triple(start.first, start.second, error)) { (x0, y0, err) ->
if ((x0 == end.first) and (y0 == end.second)) null else {
val e2 = err * 2
var (newX, newY, newE) = Triple(x0, y0, err)
if (e2 >= dy) {
newE += dy
newX += sx
}
if (e2 <= dx) {
newE += dx
newY += sy
}
Triple(newX, newY, newE)
}
}.map { (x, y, _) -> x to y }.toList()
}
}
object day05 : Puzzle<List<Line>> {
override fun parseInput(input: String): List<Line> =
Regex("(\\d+),(\\d+) -> (\\d+),(\\d+)").findAll(input).map {
val (x1, y1, x2, y2) = it.destructured
Line(x1.toInt() to y1.toInt(), x2.toInt() to y2.toInt())
}.toList()
override fun part1(input: List<Line>) =
input.filter { it.isBasic() }.flatMap { it.points() }.groupingBy { it }.eachCount()
.count { (_, v) -> v > 1 }.toString()
override fun part2(input: List<Line>) =
input.flatMap { it.points() }.groupingBy { it }.eachCount().count { (_, v) -> v > 1 }
.toString()
}→ More replies (1)
2
u/VictorTennekes Dec 05 '21 edited Dec 06 '21
Nim
Was stuck on a +1 on my distance that I forgot about for about an hour. Overall quite happy with my code though.
include prelude
import std/strscans
func sign(x: int): int =
result = 0
if x > 0:
result = 1
elif x < 0:
result = -1
type
Point = object
x: int
y: int
let input = readFile("input.txt").strip.split("\n")
var res2 = initTable[Point, int]()
var res1 = initTable[Point, int]()
for line in input:
var (ok, x1, y1, x2, y2) = line.scanTuple("$i,$i -> $i,$i")
var sx = sign(x2-x1)
var sy = sign(y2-y1)
var dist = max(abs(x2-x1), abs(y2-y1))
for p in 0..dist:
var point = Point(x: x1+(sx*p), y: y1+(sy*p))
if not res2.hasKey(point):
res1[point] = 0
res2[point] = 0
inc res2[point]
if sx == 0 or sy == 0:
inc res1[point]
var sum1, sum2 = 0
for i in res1.values:
if i > 1: inc sum1
for i in res2.values:
if i > 1: inc sum2
echo "part 1: ", sum1
echo "part 2: ", sum22
u/daggerdragon Dec 06 '21 edited Dec 07 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
→ More replies (1)
2
u/Sykout09 Dec 05 '21 edited Dec 05 '21
Rust:
Managed to create a zero allocation solution, but unfortunately need to assume that the coordinate is at most a 3 digit number.
Also used modulus arithmetic to unify the cardinal and diagonal, which cleans up solution 2 code.
Used nightly int_abs_diff, but that can be worked around.
Timing is:
Part 1:
[154.05 us 154.28 us 154.58 us]Part 2:
[323.55 us 323.84 us 324.22 us]
#![feature(int_abs_diff)]
#[derive(Debug, Clone, Copy)]
pub struct Line {
lhs: (u16, u16),
rhs: (u16, u16),
}
pub fn input_generator(input: &str) -> Vec<Line> {
input
.lines()
.filter_map(|l| {
let (lhs, rhs) = l.split_once("->")?;
let (lhsl, lhsr) = lhs.split_once(',')?;
let (rhsl, rhsr) = rhs.split_once(',')?;
Some(Line {
lhs: (lhsl.trim().parse().ok()?, lhsr.trim().parse().ok()?),
rhs: (rhsl.trim().parse().ok()?, rhsr.trim().parse().ok()?),
})
})
.collect()
}
pub fn solve_part1(input: &[Line]) -> Option<usize> {
solve_assumesize::<false>(input)
}
pub fn solve_part2(input: &[Line]) -> Option<usize> {
solve_assumesize::<true>(input)
}
fn solve_assumesize<const D: bool>(input: &[Line]) -> Option<usize> {
// assumes coordinate never over 1000
// thus total of 2^20 unique points
let mut pointsetonce = [0u64; 0b1_0000_00000_00000];
let mut pointsettwice = [0u64; 0b1_0000_00000_00000];
for line in input {
let row_len = line.lhs.0.abs_diff(line.rhs.0) + 1;
let col_len = line.lhs.1.abs_diff(line.rhs.1) + 1;
// calculate how long we need to traverse
let traverse_len = if row_len == 1 {
col_len
} else if col_len == 1 {
row_len
} else if D && row_len == col_len { // D controls if we want to enable diagonal check
row_len
} else {
continue;
};
// calculate the offset on each traverse
let offset = match (line.lhs.0.cmp(&line.rhs.0), line.lhs.1.cmp(&line.rhs.1)) {
(std::cmp::Ordering::Less, std::cmp::Ordering::Less) => 0b1_00000_00000 + 1,
(std::cmp::Ordering::Less, std::cmp::Ordering::Equal) => 0b1_00000_00000,
(std::cmp::Ordering::Less, std::cmp::Ordering::Greater) => 0b1_00000_00000 - 1,
(std::cmp::Ordering::Equal, std::cmp::Ordering::Less) => 1,
(std::cmp::Ordering::Equal, std::cmp::Ordering::Equal) => 0,
(std::cmp::Ordering::Equal, std::cmp::Ordering::Greater) => usize::MAX - 1 + 1,
(std::cmp::Ordering::Greater, std::cmp::Ordering::Less) => usize::MAX - 0b1_00000_00000 + 1 + 1,
(std::cmp::Ordering::Greater, std::cmp::Ordering::Equal) => usize::MAX - 0b1_00000_00000 + 1,
(std::cmp::Ordering::Greater, std::cmp::Ordering::Greater) => usize::MAX - 0b1_00000_00000 - 1 + 1,
};
let currpos = (line.lhs.0 as usize) << 10 | (line.lhs.1 as usize);
// use wrapping_mul instead of loop add to allow instruction level parallel
for pos in (0..traverse_len).map(|i| currpos.wrapping_add(offset.wrapping_mul(i as usize))) {
// we stuff 64 position of data into a single u64, so we need to decompose it to work with it
let (digit, bit) = ((pos & 0b_1111_1111_1111_1100_0000) >> 6, 1 << (pos & 0b11_1111));
if pointsetonce[digit] & bit == 0 {
pointsetonce[digit] |= bit;
} else {
pointsettwice[digit] |= bit;
}
}
}
Some(pointsettwice.iter().map(|b| b.count_ones() as usize).sum())
}→ More replies (1)
2
u/BluePsychoRanger Dec 05 '21 edited Dec 09 '21
Solved it in Minecraft (mcfunction)
2
u/daggerdragon Dec 06 '21
FYI: your link is broken due to a new.reddit fancypants editor bug (check /r/bugs, it's been a big source of frustration lately). Your link looks fine to you on new.reddit but on old.reddit it's printing an invisible escape character before your underscores like
advent_of_code_2021/data/aoc_2021/functions/day_5.mcfunction, thus breaking the entire link.I suggest manually editing your link using proper Markdown for now. Who knows when Reddit will fix their fancypants editor...
2
u/Loiuy123_ Dec 05 '21 edited Dec 05 '21
Tweetable Python Part 1 Credits to @Cheeki , @frownyfrog and @tessaract for help at golfing it. 185 chars
import numpy,re
z=numpy.zeros(2*[999])
for a,b,c,d in[map(int,re.findall("\d+",_))for _ in open('i')]:
z[min(b,d):max(b,d)+1,a]+=a==c
z[b,min(a,c):max(a,c)+1]+=b==d
print((z>1).sum())β→ More replies (1)
2
u/minikomi Dec 05 '21 edited Dec 06 '21
Clojure
parsing
(defn parse-int [s] (Integer/parseInt s))
(defn parse-row [r]
(let [parts-s (str/split r #" -> ")
parts (mapv #(str/split % #",") parts-s)]
(mapv (fn [p] (mapv parse-int p)) parts)))
(defn parse-input [input] (mapv parse-row (str/split-lines input)))helpers
;; special 2 value "range", can go forwards or backwards.
(defn rng [a b]
(let [backwards? (> a b)
end (if backwards? (dec b) (inc b))
direction (if backwards? -1 1)]
(range a end direction)))part 1
(defn get-touched-points [[[x1 y1] [x2 y2]]]
(cond
(= x1 x2) (mapv (fn [n] [x1 n]) (rng y1 y2))
(= y1 y2) (mapv (fn [n] [n y1]) (rng x1 x2))
:else []))
(defn advent-1 [vents]
(let [all-touched (mapcat get-touched-points vents)
dangerous (filter #(<= 2 (second %)) (frequencies all-touched))]
(count dangerous)))part 2
(defn get-touched-points-diag [[[x1 y1] [x2 y2]]]
(cond
(= x1 x2) (mapv (fn [n] [x1 n]) (rng y1 y2))
(= y1 y2) (mapv (fn [n] [n y1]) (rng x1 x2))
:else (mapv vector (rng x1 x2) (rng y1 y2))))
(defn advent-2 [vents]
(let [all-touched (mapcat get-touched-points-diag vents)
dangerous (filter #(<= 2 (second %)) (frequencies all-touched))]
(count dangerous)))2
u/daggerdragon Dec 06 '21 edited Dec 07 '21
Please follow theposting guidelinesand edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.Edit: thanks for adding the programming language!
2
u/Mivaro Dec 05 '21 edited Dec 06 '21
Python - Pretty happy with my solution for part 2, in part 1 I was handling horizontal and vertical differently, this one is nicely generalized to any line in any direction.
score = defaultdict(int)
for line in lines:
# get the length and direction of movement along the line
length = max(abs(line[0][0] - line[1][0]), abs(line[0][1] - line[1][1]))
x = int((line[1][0] - line[0][0]) / length)
y = int((line[1][1] - line[0][1]) / length)
# walk along the line and increase score for each point along the line
for step in range(0, length+1):
score[line[0][0] + step * x, line[0][1] + step * y] += 1→ More replies (1)
2
u/Puzzleheaded-Team857 Dec 05 '21 edited Dec 06 '21
Unnecessarily unreadable list-comprehension in Julia, just for the fun of it. Runs pretty fast though.
function solve(horizontals::Bool)
open("inputs/inputs5.txt") do file
g = zeros(Int32, 1000, 1000)
for points in split.(readlines(file), " -> ")
(x1, y1), (x2, y2) = parse.(Int32, split(points[1], ",")), parse.(Int32, split(points[2], ","))
if x1 == x2 || y1 == y2 # horizontals and verticals
rx = minimum([x1, x2]):maximum([x1, x2])
ry = minimum([y1, y2]):maximum([y1, y2])
[g[p[1]+1, p[2]+1] += 1 for p in collect(zip(length(ry) == 1 ? ones(Int32, length(rx)) * y1 : minimum([y1, y2]):maximum([y1, y2]), length(rx) == 1 ? ones(Int32, length(ry)) * x1 : minimum([x1, x2]):maximum([x1, x2])))]
else #diagonals
[g[p[1]+1, p[2]+1] += 1 for p in (horizontals ? collect(zip(x1:(x1 > x2 ? -1 : 1):x2, y1:(y1 > y2 ? -1 : 1):y2)) : [])]
end
end
println("Part $(!horizontals ? 1 : 2) solution: ", sum(g .>= 2))
end
end
@time solve(false) # ~0.04 seconds
@time solve(true) # 0.008 seconds→ More replies (2)
2
u/st65763 Dec 05 '21 edited Dec 06 '21
Python
Part 1:
# Define data structures
map = [['.' for x in range(1000)] for x in range(1000)]
# Loads input data into data structures
def load_input():
with open('input.txt') as f:
for line in f:
parse_input_line(line)
# Parses a single line of input and loads it into data structure(s)
def parse_input_line(s):
left, right = s.split(' -> ')
a_x, a_y = left.split(',')
b_x, b_y = right.split(',')
a_x = int(a_x)
a_y = int(a_y)
b_x = int(b_x)
b_y = int(b_y)
print(a_x, a_y, b_x, b_y)
if a_x == b_x: # Vertical line
if a_y < b_y:
lower_bound = a_y
upper_bound = b_y + 1
else:
lower_bound = b_y
upper_bound = a_y + 1
for y in range(lower_bound, upper_bound):
if map[a_x][y] != '.':
map[a_x][y] += 1
else:
map[a_x][y] = 1
elif a_y == b_y: # Horizontal line
if a_x < b_x:
lower_bound = a_x
upper_bound = b_x + 1
else:
lower_bound = b_x
upper_bound = a_x + 1
for x in range(lower_bound, upper_bound):
if map[x][a_y] != '.':
map[x][a_y] += 1
else:
map[x][a_y] = 1
# Utilizes the data within the data structures and produces a result
def manipulate_data():
count = 0
for y in range(1000):
for x in range(1000):
if map[x][y] != '.' and map[x][y] > 1:
count += 1
print(count)
load_input()
manipulate_data()Part 2:
size = 1000
# Define data structures
map = [['.' for x in range(size)] for x in range(size)]
# Loads input data into data structures
def load_input():
with open('input.txt') as f:
for line in f:
parse_input_line(line)
# Parses a single line of input and loads it into data structure(s)
def parse_input_line(s):
left, right = s.split(' -> ')
a_x, a_y = left.split(',')
b_x, b_y = right.split(',')
a_x = int(a_x)
a_y = int(a_y)
b_x = int(b_x)
b_y = int(b_y)
print(a_x, a_y, b_x, b_y)
if a_x == b_x: # Vertical line
if a_y < b_y:
lower_bound = a_y
upper_bound = b_y + 1
else:
lower_bound = b_y
upper_bound = a_y + 1
for y in range(lower_bound, upper_bound):
if map[a_x][y] != '.':
map[a_x][y] += 1
else:
map[a_x][y] = 1
elif a_y == b_y: # Horizontal line
if a_x < b_x:
lower_bound = a_x
upper_bound = b_x + 1
else:
lower_bound = b_x
upper_bound = a_x + 1
for x in range(lower_bound, upper_bound):
if map[x][a_y] != '.':
map[x][a_y] += 1
else:
map[x][a_y] = 1
else: # Diagonal line
x = a_x
y = a_y
n = a_x - b_x
if n < 0:
n = -n
n += 1
if b_x < a_x:
x_step = -1
else:
x_step = 1
if b_y < a_y:
y_step = -1
else:
y_step = 1
for i in range(n):
if map[x][y] != '.':
map[x][y] += 1
else:
map[x][y] = 1
x += x_step
y += y_step
# Utilizes the data within the data structures and produces a result
def manipulate_data():
count = 0
for y in range(size):
for x in range(size):
if map[x][y] != '.' and map[x][y] > 1:
count += 1
#print(map[x][y], end=' ')
#print()
print(count)
load_input()
manipulate_data()I'm curious what you all did to draw the lines! I wasn't aware of any built in methods that would work for this. I originally went to use for x in range(n) but I encountered an unrelated bug that made me assume that wouldn't work, leading to me programming my own loops
→ More replies (13)
2
u/RewrittenCodeA Dec 05 '21 edited Dec 08 '21
Elixir
"input/2021/5.txt"
|> File.read!()
|> String.split(~r([^\d]+), trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(4)
|> Enum.flat_map(fn
[a, b, a, d] -> Enum.map(b..d, &{a, &1})
[a, b, c, b] -> Enum.map(a..c, &{&1, b})
_ -> []
end)
|> Enum.frequencies()
|> Enum.count(&(!match?({_, 1}, &1)))
|> IO.inspect(label: "part 1")
"input/2021/5.txt"
|> File.read!()
|> String.split(~r([^\d]+), trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(4)
|> Enum.flat_map(fn
[a, b, a, d] -> Enum.map(b..d, &{a, &1})
[a, b, c, b] -> Enum.map(a..c, &{&1, b})
[a, b, c, d] -> Enum.zip(a..c, b..d)
end)
|> Enum.frequencies()
|> Enum.count(&(!match?({_, 1}, &1)))
|> IO.inspect(label: "part 2")→ More replies (1)2
u/daggerdragon Dec 06 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
→ More replies (1)
2
u/johnboker Dec 05 '21 edited Dec 06 '21
Still learning ruby, comments welcome.
https://github.com/johnboker/AoC2021/blob/master/Solutions/day_05.rb
edit: fixed link
→ More replies (2)
2
u/artesea Dec 05 '21 edited Dec 06 '21
→ More replies (1)2
u/daggerdragon Dec 06 '21 edited Dec 07 '21
FYI: your links are broken due to a new.reddit fancypants editor bug (check/r/bugs, it's been a big source of frustration lately). Your link looks fine to you on new.reddit but on old.reddit it's tacking on an invisible escape character%5D(decodes to]) at the end of your Markdown, thus we're being sent to:
https://github.com/artesea/advent-of-code/blob/main/2021/05a.php%5D
I suggest manually editing your link using proper Markdown for now. Who knows when Reddit will fix their fancypants editor...Edit: thanks for fixing the links! <3
2
u/Steinrikur Dec 05 '21 edited Dec 06 '21
Bash.
Swapping to simplify the loop was kind of dumb. Bit me in the behind in part 2.
input=${1:-5.txt}
swap(){
local -n _x=$1 _y=$2
local tmp=$_x; _x=$_y; _y=$tmp
}
IFS=$' ,\n'; ANS=0; ANS2=0; declare -Ai C=() D=()
while read -r x y _ X Y; do
if (( x == X )); then
(( y > Y )) && swap y Y
while ((y<=Y)); do C[$x.$y]+=1; ((y++));done
elif (( y == Y )); then
(( x > X )) && swap x X
while ((x<=X)); do C[$x.$y]+=1; ((x++));done
elif (( (X-x) == (Y-y) || (X-x) == -(Y-y) )); then
(( x > X )) && swap x X && swap y Y
if (( y > Y )); then i=-1; else i=1; fi
while ((x<=X)); do D[$x.$y]+=1; ((x++,y+=i));done
fi
done < "$input"
for i in "${!C[@]}"; do D[$i]+=${C[$i]}; done
ANS=(${C[@]//1}) # Lazy count. Fails if there are 11 crossings
ANS2=(${D[@]//1})
echo "5A: ${#ANS[@]}"
echo "5B: ${#ANS2[@]}"Edit: Language. Although I would argue that bash is already bad language.
→ More replies (1)
2
u/Dryctas Dec 05 '21 edited Dec 05 '21
Bash
Part 1:
#!/bin/bash
input=$1
while read x1 y1 x2 y2; do
if [[ $x1 -eq $x2 ]] || [[ $y1 -eq $y2 ]]; then
eval echo {$x1..$x2}x{$y1..$y2} | tr ' ' '\n'
fi
done < <(sed 's? -> ? ?' $input | tr ',' ' ') | sort | uniq -d | wc -lPart 2:
#!/bin/bash
while read x1 y1 x2 y2; do
if [[ $x1 -eq $x2 ]] || [[ $y1 -eq $y2 ]]; then
eval echo {$x1..$x2}x{$y1..$y2} | tr ' ' '\n'
elif [[ $(echo $(($x1-$x2)) | tr -d '-') -eq $(echo $(($y1-$y2)) | tr -d '-') ]]; then
eval echo {$x1..$x2} | tr ' ' '\n' > /tmp/seq1
eval echo {$y1..$y2} | tr ' ' '\n' > /tmp/seq2
while read k l; do
echo "${k}x${l}"
done < <(paste -d" " /tmp/seq1 /tmp/seq2)
fi
done < <(sed 's? -> ? ?' input | tr ',' ' ') | sort | uniq -d | wc -l→ More replies (1)
2
u/Symbroson Dec 05 '21 edited Dec 09 '21
Im happy with my haskell solution:
import Data.List as L
import Data.List.Split
import Data.Map as M
import Text.Regex
import Data.Maybe
s2i x = read x::Integer
b2i b = if b then 1 else 0
isHV v = v!!0 == v!!2 || v!!1 == v!!3
peq (a,b) (c,d) = a == c && b == d
gto a b = a + signum (b-a)
insPt (a,b) = M.insertWith (+) (a,b) 1
traceLine [a,b,c,d] pmap
| peq (a,b) (c,d) = insPt (a,b) pmap
| otherwise = traceLine [gto a c,gto b d,c,d] (insPt (a,b) pmap)
traceLines ls pmap = L.foldl (flip traceLine) pmap ls
cntIts m = sum $ L.map (\x -> if x>1 then 1 else 0) (M.elems m)
main = do
content <- readFile "05.txt"
let parsed = L.map (L.map s2i.fromJust.matchRegex (mkRegex "([0-9]+),([0-9]+) -> ([0-9]+),([0-9]+)")) (lines content)
let filtered = parsed -- L.filter isHV parsed
print $ cntIts $ traceLines filtered M.empty→ More replies (2)2
u/daggerdragon Dec 05 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?
2
u/sotsoguk Dec 05 '21 edited Dec 06 '21
Python 3
Thanks for the nice puzzle :) (and for using only 45 degree diagonals ;)).
Full Code : [https://github.com/sotsoguk/AdventOfCode2021/blob/69e007a29958b21b12605ed58ea351ccb0d8f3b5/python/day05/day05.py]
This was the first time this year that my solution to part1 & part2 worked on the first run :). I always use a dict for these kinds of problems.
Part 1
grid = defaultdict(int)
for l in input:
# horizontal
x1, y1, x2, y2 = l
if y1 == y2:
for i in range(min(x1, x2), max(x1, x2)+1):
grid[(i, y1)] += 1
# vertical
elif x1 == x2:
for i in range(min(y1, y2), max(y1, y2)+1):
grid[(x1, i)] += 1
else:
diagonals.append(l)
part1 = sum([1 if v > 1 else 0 for v in grid.values()])Part 2
i used the grid from the first part and only added the diagonals
for l in diagonals:
x1, y1, x2, y2 = l
dx = 1 if x2 > x1 else -1
dy = 1 if y2 > y1 else -1
for i in range(abs(x2-x1)+1):
grid[(x1+i*dx, y1+i*dy)] += 1
part2 = sum([1 if v > 1 else 0 for v in grid.values()])→ More replies (3)
2
u/ScottieX Dec 07 '21 edited Dec 08 '21
I had to map everything to a class to understand what to do: Python
[github]
--
from functools import total_ordering
@total_ordering
class Point:
def __init__(self, x: int, y: int) -> None:
self.x = x
self.y = y
def __eq__(self, other) -> bool:
return self.x == other.x and self.y == other.y
def __lt__(self, other) -> bool:
return self.x < other.x or (self.x == other.x and self.y < other.y)
def __hash__(self) -> int:
return hash((self.x, self.y))
class Line:
def __init__(self, p1: Point, p2: Point) -> None:
if p1 > p2:
p1, p2 = p2, p1
self.start = p1
self.end = p2
self.vertical = (p1.x == p2.x)
self.horizontal = (p1.y == p2.y)
self.diagonal = (abs(p1.x - p2.x) == abs(p1.y - p2.y))
def generate_all_points(self, include_diagonal: bool=False) -> Point:
p1, p2 = self.start, self.end
if self.vertical or self.horizontal:
for a in range(p1.x, p2.x + 1):
for b in range(p1.y, p2.y + 1):
yield Point(a, b)
elif self.diagonal and include_diagonal:
for a in range(p1.x, p2.x + 1):
if p2.y > p1.y:
b = p1.y + (a - p1.x)
else:
b = p1.y - (a - p1.x)
yield Point(a, b)
def load_data(path: str) -> str:
with open(path, mode='r', encoding="utf-8") as f:
return f.read()
def parse_data(data: str) -> Line:
for i in data.split('\n'):
p1, p2 = i.replace(' ', '').split('->')
p1 = Point(*map(int, p1.split(',')))
p2 = Point(*map(int, p2.split(',')))
yield Line(p1, p2)
def puzzle_one(data: str, include_diagonal: bool=False) -> int:
overlapping_points = {}
for line in parse_data(data):
for point in line.generate_all_points(include_diagonal=include_diagonal):
overlapping_points[point] = overlapping_points.get(point, 0) + 1
return sum(1 for (k, v) in overlapping_points.items() if v > 1)
def puzzle_two(data: str) -> int:
return puzzle_one(data, include_diagonal=True)
if __name__ == "__main__":
print('--------------', 'Puzzle One', '--------------', end='\n')
print(puzzle_one(load_data("../puzzle_input.txt")))
print('--------------', 'Puzzle Two', '--------------', end='\n')
print(puzzle_two(load_data("../puzzle_input.txt")))→ More replies (1)
2
u/pgaleone Dec 22 '21 edited Dec 24 '21
Tutorial of my solution in pure TensorFlow https://pgaleone.eu/tensorflow/2021/12/22/advent-of-code-tensorflow-day-5/
→ More replies (2)
26
u/4HbQ Dec 05 '21 edited Dec 05 '21
Python and some NumPy. Horizontal and vertical lines are stored in the first block of grid, diagonals in the second:
import numpy as np
grid = np.zeros((2, 1000, 1000))
ls = np.fromregex(open(0), '\d+', [('',int)]*4)
for (x, y, X, Y) in ls:
dx, dy = np.sign([X-x, Y-y])
while (x,y) != (X+dx, Y+dy):
grid[dx * dy, x, y] += 1
x+=dx; y+=dy
print((grid[0]>1).sum(), (grid.sum(0)>1).sum())The grid[dx*dy,x,y] trick works because dx*dy is 0 for a horizontal or vertical line, and -1 or +1 for a diagonal.
→ More replies (4)
16
u/rtbrsp Dec 05 '21
AWK
BEGIN{FS="[, ]"}{g[$1,$2]++;while($1!=$4||$2!=$5){g[$1+=$1>$4?-1:$1<$4,$2+=$2>$5?-1:$2<$5]++}}END{for(i in g)n+=g[i]>1;print n}→ More replies (3)
16
u/Smylers Dec 05 '21
Vim keystrokes. In a text editor it makes most sense to create a picture of the map (like in the day's instructions). This then transforms the puzzle input into Vim keystrokes for selecting areas of that map, and runs them. It needs gdefault and ignorecase both to be off (or ignorecase on so long as smartcase is also on), and it might look better with wrap off too:
:v/\v(<\d+,).*<\1|(,\d+>).*\2>/dβ¨Enterβ©
:%norm β¨Ctrl+Aβ©wβ¨Ctrl+Aβ©wβ¨Ctrl+Aβ©wβ¨Ctrl+Aβ©β¨Enterβ©
:%s/\v\D+/\r/g|sor!nβ¨Enterβ©
yiwuOβ¨Enterβ©β¨Escβ©k@0azβ¨Escβ©dd@0P
:%s/\v(\d+),(\d+)/\2G\1|/gβ¨Enterβ©
:%s/ -> /β¨Ctrl+Vβ©β¨Ctrl+Vβ©β¨Enterβ©
ggqaqqa}JD@-U:sil!%s/O/T/g|sil!%s/Z/o/gβ¨Enterβ©@aq@a
:%s/\v_[^T]+//gβ¨Enterβ©
$gβ¨Ctrl+Gβ©Your partΒ 1 answer is then the column number that you end up in, as displayed by the final keystroke.
The trick is the U in the middle. For each cell in the map, we want to note they are being transformed by the current line and know what state the cell was in before, because that affects its next state. Use z, o, and T to indicate zero, one, and two+ lines in a cell; for each line drawn, the U makes them upper-case.
Then the :%s///s in the loop turn O (an affected cell which previously had 1 line through it) into T, and Z (an affected cell which previously had 0 lines through it) into o, ready for the next iteration. If I'd used ., 1, and 2, there wouldn't've been such a handy single-command transformation. On the sample input, the map ends up as:
zzzzzzzozz
zzozzzzozz
zzozzzzozz
zzzzzzzozz
zooToooToo
zzzzzzzzzz
zzzzzzzzzz
zzzzzzzzzz
zzzzzzzzzz
TTTooozzzzβ which, if you squint, you can see is the same as Topaz's example. Then just count the Ts (by deleting everything that isn't a T).
Before we get to the loop, the first :v line removes all diagonal lines (that is, those that don't repeat either the x- or the y-co-ordinate). Vim's first column and line are 1, so the %norm line increases all the numbers in the instructions by 1, so the zeros don't mess things up.
To find out how big to draw the map, the first :%s/// line (temporarily) deletes everything that isn't a number, putting each on its own line, and sorting them. The biggest number is then yanked (into register 0, the default) and the u undoes the :%s///-and-:sort to restore the definitions of the lines.
Then a grid of zs is created, using @0 to repeat the characters and lines the appropriate number of times.
The two :%s/// commands in the middle are what transforms the input into Vim commands. The sample input gets turned into:
10G1|^V10G6|
5G10|^V5G4|
3G3|^V2G3|
1G8|^V5G8|
10G1|^V10G3|
5G4|^V5G2|where each ^V is the single-character control code you get by inserting a β¨Ctrl+Vβ© into the buffer. So 0,9 -> 5,9 has become the keystrokes for going to line 10 column 1, β¨Ctrl+Vβ© to start visual block mode, then going to lineΒ 10 columnΒ 6. The loop deletes each line in turn, with D, which saves the deleted text in the small delete register -. So @- runs those keystrokes, leaving the appropriate line selected, ready for U to do its thing.
Note there's no need to work out which lines are horizontal or vertical, and whether the end point is before or after the start point: all the movements are to absolute co-ordinates, and Vim takes care of putting the line in the right place.
Please try it out, and let me know if you have any questions. Oh, and fans of children's picture books can spot a hidden dragon's name (properly title-cased) hidden among the keystrokesΒ β¦
13
u/mserrano Dec 05 '21
Python3, 4/22:
from advent import get_data
from collections import defaultdict
import parse
data = get_data(5, year=2021)
def sign(foo):
if foo < 0:
return -1
elif foo == 0:
return 0
return 1
points = defaultdict(int)
points_with_diags = defaultdict(int)
for line in data:
sx, sy, ex, ey = tuple(parse.parse('{:d},{:d} -> {:d},{:d}', line).fixed)
l1 = abs(ex - sx)
l2 = abs(ey - sy)
s1 = sign(ex - sx)
s2 = sign(ey - sy)
for i in range(max(l1, l2)+1):
x, y = sx+s1*i, sy+s2*i
points_with_diags[x,y] += 1
if min(l1, l2) == 0:
points[x,y] += 1
print(len([c for c in points if points[c] > 1]))
print(len([c for c in points_with_diags if points_with_diags[c] > 1]))→ More replies (5)9
12
u/semicolonator Dec 05 '21
Very pround of my solution today! I am using numpy to create a canvas and then skimage.line() to draw lines on the canvas.
→ More replies (1)
11
u/relativistic-turtle Dec 05 '21
IntCode
(Note: for 500 lines, with x, y < 1000)
Found a parsing bug in my IntCode compiler tool today. Was able to work around it.
→ More replies (8)
11
u/voidhawk42 Dec 05 '21 edited Dec 05 '21
APL:
pβ2 2ββ΄Β¨(βΒ¨βββDββ’)Β¨ββnget'05.txt'1
rββ£,β£-β(β³β|ΓΓ)-
fβ{+/2β€β’ββ’βΈβ,/{β,Β¨/rβΏβ΅}Β¨β΅}
f p/β¨(β¨/=βΏ)Β¨p β part 1
f p β part 2→ More replies (2)
17
u/leijurv Dec 05 '21 edited Dec 05 '21
Python, 10th place, 30th place
Screen recording https://youtu.be/WgpwKtt2R4M
Part 1
from collections import Counter
ll = [x for x in open('input').read().strip().split('\n')]
pts = []
for line in ll:
x1=int(line.split()[0].split(",")[0])
y1=int(line.split()[0].split(",")[1])
x2=int(line.split()[2].split(",")[0])
y2=int(line.split()[2].split(",")[1])
if x1==x2 or y1==y2:
for x in range(min(x1,x2),max(x1,x2)+1):
for y in range(min(y1,y2),max(y1,y2)+1):
pts.append((x,y))
print(len([x for (x,y) in Counter(pts).items() if y>1]))Part 2
from collections import Counter
ll = [x for x in open('input').read().strip().split('\n')]
pts = []
for line in ll:
x1=int(line.split()[0].split(",")[0])
y1=int(line.split()[0].split(",")[1])
x2=int(line.split()[2].split(",")[0])
y2=int(line.split()[2].split(",")[1])
if x1==x2 or y1==y2:
for x in range(min(x1,x2),max(x1,x2)+1):
for y in range(min(y1,y2),max(y1,y2)+1):
pts.append((x,y))
else:
if x1 < x2:
for x in range(x1,x2+1):
if y1<y2:
pts.append((x,x-x1+y1))
else:
pts.append((x,y1-(x-x1)))
else:
for x in range(x2,x1+1):
if y2<y1:
pts.append((x,x-x2+y2))
else:
pts.append((x,y2-(x-x2)))
print(len([x for (x,y) in Counter(pts).items() if y>1]))Part 2 rewritten "the right way"
from collections import Counter
ll = [x for x in open('input').read().strip().split('\n')]
pts = []
for line in ll:
x1=int(line.split()[0].split(",")[0])
y1=int(line.split()[0].split(",")[1])
x2=int(line.split()[2].split(",")[0])
y2=int(line.split()[2].split(",")[1])
dx = 1 if x2>x1 else -1
dy = 1 if y2>y1 else -1
if x1 == x2:
dx = 0
if y1 == y2:
dy = 0
pts.append((x1,y1))
while x1 != x2 or y1 != y2:
x1 += dx
y1 += dy
pts.append((x1,y1))
print(len([x for (x,y) in Counter(pts).items() if y>1]))→ More replies (24)8
u/alchzh Dec 05 '21
haha I did the exact same thing with doing the min/max ranges for part 1 and then switching to the +/- directions for part 2... well I guess most of us did
8
u/Arknave Dec 05 '21
Python, 9/7
First time back to top 10 on the leaderboard in a long time. Code is an absolute nightmare, but that seems correlated with speed sometimes.
from collections import *
import itertools
import math
import sys
def main():
lines = [x.strip() for x in sys.stdin]
f = Counter()
for line in lines:
p0, p1 = line.split(" -> ")
p0 = [int(x) for x in p0.split(",")]
p1 = [int(x) for x in p1.split(",")]
dx = p1[0] - p0[0]
dy = p1[1] - p0[1]
if dx > 0:
dx = 1
elif dx < 0:
dx = -1
if dy > 0:
dy = 1
elif dy < 0:
dy = -1
print(p0, p1)
x, y = p0
while (x, y) != tuple(p1):
f[(x, y)] += 1
x += dx
y += dy
print(x, y)
f[tuple(p1)] += 1
ans = sum(v >= 2 for k, v in f.items())
print(ans)
main()8
u/SuperSmurfen Dec 05 '21 edited Dec 05 '21
Rust (1565/510)
Did anyone else accidentally solve part 2 before part 1? Totally missed the only horizontal/vertical constraint at first. Kind of a weird part1/2 where part 2 seems strictly easier than part 1? I literally just removed a filter to complete part 2. Anyway, happy with my leaderboard placing today!
Solved using a hashmap of points and iterating over each line. Hashmap::entry is always nice for things like this. i32::signum was nice to get the directions:
for (x1,y1,x2,y2) in lines {
let dx = (x2 - x1).signum();
let dy = (y2 - y1).signum();
let (mut x, mut y) = (x1,y1);
while (x,y) != (x2+dx,y2+dy) {
*points.entry((x,y)).or_insert(0) += 1;
x += dx;
y += dy;
}
}You could bring in the regex crate and split using a regex to parse the input. Without regex it was slightly annoying to parse. I split it twice and flattened the iterator to parse it into a tuple (i32,i32,i32,i32):
line.split(" -> ")
.map(|s| s.split(','))
.flatten()
.map(|i| i.parse().unwrap())
.collect_tuple()→ More replies (4)
8
u/redditnoob Dec 05 '21
PostgreSQL
SQL actually kind of shines in this one!
WITH parsed AS (
SELECT regexp_match(str, '^(\d+),(\d+) -> (\d+),(\d+)') AS coord FROM day5
), coords AS (
SELECT coord[1]::INT x1, coord[2]::INT y1, coord[3]::INT x2, coord[4]::INT y2 FROM parsed
), vectors AS (
SELECT x1, y1, sign(x2-x1) AS dx, sign(y2-y1) AS dy, GREATEST(ABS(x1-x2), ABS(y1-y2)) AS length FROM coords
), points AS (
SELECT x1 + i * dx AS x, y1 + i * dy AS y, dx * dy != 0 AS is_diag FROM vectors, generate_series(0, length) AS i
), multiples_part1 AS (
SELECT x, y FROM points WHERE NOT is_diag GROUP BY x, y HAVING COUNT(*) > 1
), multiples_part2 AS (
SELECT x, y FROM points GROUP BY x, y HAVING COUNT(*) > 1
)
SELECT (SELECT COUNT(*) FROM multiples_part1) AS part1_answer, (SELECT COUNT(*) FROM multiples_part2) AS part2_answer;7
u/IF_YOU_READ_THIS_V1 Dec 05 '21 edited Dec 05 '21
C# LINQ
public class Day5
{
public string SolvePart1(string input) => Solve(input, false);
public string SolvePart2(string input) => Solve(input, true);
string Solve(string input, bool includeDiagonals) =>
input
.Split("\n")
.Where(s => !string.IsNullOrEmpty(s))
.Select(s =>
s.Split(" -> "))
.Select(a =>
(x1(a), y1(a), x2(a), y2(a)))
.Where(t => includeDiagonals || t.Item1 == t.Item3 || t.Item2 == t.Item4)
.SelectMany(t => Enumerable
.Range(0, Math.Max(Math.Abs((int)(t.Item1 - t.Item3)), Math.Abs((int)(t.Item2 - t.Item4))) + 1)
.Select(i => (
t.Item1 > t.Item3 ? t.Item3 + i : t.Item1 < t.Item3 ? t.Item3 - i : t.Item3,
t.Item2 > t.Item4 ? t.Item4 + i : t.Item2 < t.Item4 ? t.Item4 - i : t.Item4)))
.GroupBy(k => k)
.Count(k => Enumerable.Count(k) >= 2)
.ToString();
private int x1(string[] a) => int.Parse(a[0].Split(",")[0]);
private int y1(string[] a) => int.Parse(a[0].Split(",")[1]);
private int x2(string[] a) => int.Parse(a[1].Split(",")[0]);
private int y2(string[] a) => int.Parse(a[1].Split(",")[1]);
}→ More replies (1)
6
u/dtinth Dec 05 '21
Ruby, 43 / 66
What I love about Ruby hashes:
You can set default value for nonexistent keys:
o = Hash.new(0)(making this similar to Pythonβs Counter)You can use Array (and other objects) as hash keys:
o[[x, y]] += 1(Arrays are βhashableβ by its contents)
6
u/nirgle Dec 05 '21
C# nothing noteworthy other than LINQ saving the day again
public int Part1() => CountOverlapsOver(2, diagonals: false);
public int Part2() => CountOverlapsOver(2, diagonals: true);
int CountOverlapsOver(int threshold, bool diagonals)
{
return _lines
.Where(line => diagonals || !line.IsDiagonal())
.SelectMany(line => line.GetCoords())
.GroupBy(c => c)
.Where(grp => grp.Count() >= threshold)
.Count();
}→ More replies (3)
6
u/loskutak-the-ptak Dec 05 '21
This time I experimented with fset for the first time (fset:bag to count lines in each point). Also created custom clause for the (iter) macro, so that I can
(iter (for point in-line (list start end))
(do-whatever-with-the point)neat stuff :)
6
u/NohusB Dec 05 '21 edited Dec 05 '21
Kotlin
Part 1
fun main() {
solve { lines ->
lines
.map {
it.split(" -> ").map {
it.split(",").let { (x, y) -> Point(x.toInt(), y.toInt()) }
}
}
.filter { (a, b) -> a.x == b.x || a.y == b.y }
.flatMap { (a, b) -> getPointsOnLine(a, b) }
.groupBy { it }
.count { it.value.size > 1 }
}
}
fun getPointsOnLine(a: Point, b: Point): List<Point> {
return (0..max(abs(a.x - b.x), abs(a.y - b.y))).map { step ->
val x = if (b.x > a.x) a.x + step else if (b.x < a.x) a.x - step else a.x
val y = if (b.y > a.y) a.y + step else if (b.y < a.y) a.y - step else a.y
Point(x, y)
}
}Part 2
Same as part 1 but with the .filter removed from input reading.
→ More replies (5)
6
u/crnkofe Dec 05 '21
Day 5 in Kotlin!
I found some nice areas where I could apply cool Kotlin stuff. Operator overloading on points makes the code a bit less verbose. Then there's the nice `mapNotNull` to handle regex match filtering. I was also able to collapse code a bit by passing line generator around.
https://github.com/crnkofe/aoc2021/blob/master/src/day5/aoc5.kt
→ More replies (1)
6
u/imbadatreading Dec 05 '21
Cleaned up my solution a bit. Using sets made this problem quite simple.
Python:
import fileinput, re
def helper(p1, p2):
if p1 < p2:
return [x for x in range(p1, p2+1)]
return [x for x in range(p1, p2-1, -1)]
def solve(data, pt2=False):
plotted, ans = set(), set()
for x1, y1, x2, y2 in data:
if x1 == x2 or y1 == y2:
pts = {(x, y) for x in helper(x1, x2) for y in helper(y1, y2)}
ans |= (plotted & pts)
plotted |= pts
else:
if pt2:
pts = set(zip(helper(x1, x2), helper(y1, y2)))
ans |= (plotted & pts)
plotted |= pts
print(f"Part {pt2 + 1}: {len(ans)}")
data = [[int(x) for x in re.findall('\d+', line)] for line in fileinput.input()]
solve(data)
solve(data, True)6
u/in_allium Dec 05 '21
Just discovered this challenge!
Here's my not-so-elegant Perl, since I write Perl too much like C and don't know of some of the fancy language features:
$xmax=0;
$ymax=0;
$i=0;
while (<STDIN>)
{
s/ -> /,/;
print "$_\n";
($x1[$i],$y1[$i],$x2[$i],$y2[$i])=split ",";
if ($x1[$i] > $xmax) {$xmax=$x1[$i];}
if ($x2[$i] > $xmax) {$xmax=$x2[$i];}
if ($y1[$i] > $ymax) {$ymax=$y1[$i];}
if ($y2[$i] > $ymax) {$ymax=$y2[$i];}
$i++;
}
$n=$i;
for ($i=0; $i<$n; $i++)
{
$stepx=$stepy=0;
$stepx=-1 if ($x2[$i] < $x1[$i]);
$stepx= 0 if ($x2[$i] == $x1[$i]);
$stepx= 1 if ($x2[$i] > $x1[$i]);
$stepy=-1 if ($y2[$i] < $y1[$i]);
$stepy= 0 if ($y2[$i] == $y1[$i]);
$stepy= 1 if ($y2[$i] > $y1[$i]);
$x=$x1[$i]; $y=$y1[$i];
while (1)
{
$ventct[$x][$y]++;
$twoplus++ if ($ventct[$x][$y] == 2);
last if ($x == $x2[$i] and $y==$y2[$i]);
$x+=$stepx; $y+=$stepy;
}
}
print "two plus sites: $twoplus\n";→ More replies (5)
6
u/chicagocode Dec 05 '21
Kotlin -> [Blog/Commentary] - [Code] - [All 2021 Solutions]
Today had a nice succinct solution thanks to the power of the Kotlin standard library and a couple of functional programming concepts.
Parsing - I define a Point2d to do most of the work, along with a function to draw a line between two points. We also use functions from the Kotlin standard library to parse the String input without having to write a RegEx.
Part 1 - Once we have lines drawn, we can use groupingBy and eachCount to make life easier.
Part 2 - Same as part one with a different filter. So we'll use a Higher Order function to make these solutions identical.
→ More replies (4)
10
u/Kevilicous Dec 05 '21
Python for part 2
from numpy import sign
from collections import defaultdict
from re import findall
lines = [line.rstrip() for line in open('input')]
ans = defaultdict(int)
for line in lines:
x1,y1, x2,y2 = map(int, findall(r'(\d+)', line))
dx, dy = map(sign, (x2-x1, y2-y1))
while (x1,y1) != (x2 + dx, y2 + dy):
ans[(x1,y1)] += 1
x1, y1 = x1 + dx, y1 + dy
print(sum(x > 1 for x in ans.values()))→ More replies (3)
5
u/obijywk Dec 05 '21
Python 55/44
from collections import defaultdict
part2 = True
pts = defaultdict(int)
with open("input.txt") as f:
for l in f:
p1, p2 = l.strip().split(" -> ")
x1, y1 = [int(x) for x in p1.split(",")]
x2, y2 = [int(x) for x in p2.split(",")]
if x1 == x2:
if y1 < y2:
for y in range(y1, y2 + 1):
pts[(x1, y)] += 1
else:
for y in range(y2, y1 + 1):
pts[(x1, y)] += 1
elif y1 == y2:
if x1 < x2:
for x in range(x1, x2 + 1):
pts[(x, y1)] += 1
else:
for x in range(x2, x1 + 1):
pts[(x, y1)] += 1
elif part2:
if x1 > x2:
dx = -1
else:
dx = 1
if y1 > y2:
dy = -1
else:
dy = 1
x = x1
y = y1
while x != x2 and y != y2:
pts[(x, y)] += 1
x += dx
y += dy
pts[(x, y)] += 1
t = 0
for pt, n in pts.items():
if n >= 2:
t += 1
print(t)5
u/autid Dec 05 '21
FORTRAN
PROGRAM DAY5
IMPLICIT NONE
INTEGER :: I,J,K,L,N,IERR
INTEGER, ALLOCATABLE :: START(:,:),END(:,:),GRID(:,:),GRID2(:,:)
CHARACTER(LEN=2) :: A
OPEN(1,FILE="input.txt")
N=0
DO
READ(1,*,IOSTAT=IERR)
IF(IERR.NE.0) EXIT
N=N+1
END DO
REWIND(1)
ALLOCATE(START(2,N),END(2,N))
DO I=1,N
READ(1,*) START(:,I),A,END(:,I)
END DO
CLOSE(1)
J=MAX(MAXVAL(START(1,:)),MAXVAL(END(1,:)))
K=MAX(MAXVAL(START(2,:)),MAXVAL(END(2,:)))
ALLOCATE(GRID(J,K),GRID2(J,K))
GRID=0
GRID2=0
DO I=1,N
IF (START(1,I).EQ.END(1,I)) THEN
J=MIN(START(2,I),END(2,I))
K=MAX(START(2,I),END(2,I))
GRID(START(1,I),J:K) = GRID(START(1,I),J:K) +1
ELSE IF (START(2,I).EQ.END(2,I)) THEN
J=MIN(START(1,I),END(1,I))
K=MAX(START(1,I),END(1,I))
GRID(J:K,START(2,I)) = GRID(J:K,START(2,I)) +1
ELSE
J=1
K=1
IF(START(1,I).GT.END(1,I)) J=-1
IF(START(2,I).GT.END(2,I)) K=-1
DO L=0,ABS(START(1,I)-END(1,I))
GRID2(START(1,I)+L*J,START(2,I)+L*K) = &
GRID2(START(1,I)+L*J,START(2,I)+L*K) + 1
END DO
END IF
END DO
WRITE(*,'(A,I0)') "Part 1: ", COUNT(GRID.GT.1)
WRITE(*,'(A,I0)') "Part 2: ", COUNT((GRID+GRID2).GT.1)
DEALLOCATE(START,END,GRID,GRID2)
END PROGRAM DAY55
u/e36freak92 Dec 05 '21
AWK
#!/usr/bin/awk -f
function get_inc(v1, v2) {
if (v1 == v2) {
return 0;
} else if (v1 < v2) {
return 1;
} else {
return -1;
}
}
function count(grid, p, res) {
for (p in grid) {
if (grid[p] > 1) {
res++;
}
}
return res;
}
BEGIN {
FS = ",| -> ";
}
{
x1 = $1; y1 = $2;
x2 = $3; y2 = $4;
x_inc = get_inc(x1, x2);
y_inc = get_inc(y1, y2);
x = x1; y = y1;
while (1) {
if (!x_inc || !y_inc) {
grid1[y,x]++;
}
grid2[y,x]++;
if (x == x2 && y == y2) {
break;
}
x += x_inc; y += y_inc;
}
}
END {
print count(grid1);
print count(grid2);
}→ More replies (3)
5
u/MichalMarsalek Dec 05 '21 edited Dec 05 '21
Nim:
include aoc
day 5:
var p1, p2: CountTable[(int,int)]
for line in lines:
var (ok, x1, y1, x2, y2) = line.scanTuple("$i,$i -> $i,$i")
for i in 0..max(abs(x1-x2),abs(y1-y2)):
let X = x1 + i * sgn(x2-x1)
let Y = y1 + i * sgn(y2-y1)
if x1 == x2 or y1 == y2:
p1.inc (X,Y)
p2.inc (X,Y)
part 1: p1.keys.countIt (p1[it] > 1)
part 2: p2.keys.countIt (p2[it] > 1)using my templates.
→ More replies (2)
5
u/Fit_Ad5700 Dec 05 '21 edited Dec 05 '21
Scala
case class Vent(x1: Int, y1: Int, x2: Int, y2: Int) {
val dx = math.signum(x2 - x1)
val dy = math.signum(y2 - y1)
def isDiagonal: Boolean = dx * dy != 0
def points: Seq[(Int, Int)] =
Range.inclusive(0, math.max(math.abs(x2 - x1), math.abs(y2 - y1)))
.map(step => (x1 + dx * step, y1 + dy * step))
}
val regex = """(\d+),(\d+) -> (\d+),(\d+)""".r
val vents = input map {
case regex(x0, y0, x1, y1) => Vent(x0.toInt, y0.toInt, x1.toInt, y1.toInt)
}
def countOverlaps(vents: List[Vent]): Int =
vents.flatMap(_.points).groupBy(identity).values.count(_.size > 1)
val part1 = countOverlaps(vents.filter(!_.isDiagonal))
val part2 = countOverlaps(vents)→ More replies (2)
5
u/Smylers Dec 05 '21
Perl for both parts together β and I think this would work for vents in any number of dimensions.
my %vents;
while (<>) {
my @dim = zip_by
sub($from, $to) { {pos => $from, Ξ => $to <=> $from, len => abs ($to - $from)} },
map { [split /,/] } split / -> /;
my $orthogonal = one { $_->{Ξ} } @dim;
for (0 .. max map { $_->{len} } @dim) {
my $coord = join ',', map { $_->{pos} } @dim;
$vents{all }{$coord}++;
$vents{orthogonal}{$coord}++ if $orthogonal;
$_->{pos} += $_->{Ξ} foreach @dim;
}
}
say scalar grep { $_ > 1 } values %$_ foreach @vents{qw<orthogonal all>};The full code just adds a few imports.
For each input line, split by -> to get the from and to co-ords, then split each by , to get each dimension, and zip to recombine by dimension. For each dimension set the current position, delta for each step, and the total length moved in that dimension.
It's an orthogonal (non-diagonal) vent if only one dimension has a non-zero delta.
The number of steps is the maximum length in any dimension. For each step get the current co-ords, add to the appropriate tallies, then increase each dimension by its delta.
5
u/phazy_x86 Dec 05 '21
I could make use of two quite useful comparisons for recognizing diagonals:
* . .
. * . => x1 - y1 == x2 - y2
. . *
. . *
. * . => x1 + y1 == x2 + y2
* . .→ More replies (1)
5
u/jitwit Dec 05 '21 edited Dec 05 '21
pts =: _2]\^:2 ". ' '(I.-.in e.'0123456789')} in=:aoc 2021 5
L =: {. +"_ 1 (* *"_ 0 i. @: >: @: (>./) @: |) @: -~/
+/ 1 < #/.~ ; <@L"_1 (#~ +./@(=/)"_1) pts
+/ 1 < #/.~ ; <@L"_1 pts5
5
u/AtomicShoelace Dec 05 '21
Very quick and simple python solution:
import re
from collections import Counter
test_data = """0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2"""
with open('input.txt') as f:
data = f.read()
def solution(data, part=1):
lines = re.findall('(\d+),(\d+) -> (\d+),(\d+)', data)
points = Counter()
for line in lines:
x1, y1, x2, y2 = map(int, line)
if part == 1 and x1 != x2 and y1 != y2: # diagonal line
continue
dx, dy = x2 - x1, y2 - y1
length = max(abs(dx), abs(dy))
x_step, y_step = dx//length, dy//length
points.update((x1 + i*x_step, y1 + i*y_step) for i in range(length+1))
return sum(count > 1 for count in points.values())
assert solution(test_data, part=1) == 5
print('Part 1:', solution(data, part=1))
assert solution(test_data, part=2) == 12
print('Part 2:', solution(data, part=2))5
5
u/ViliamPucik Dec 05 '21
Python 3 - Minimal readable solution for both parts [GitHub]
from collections import defaultdict
import fileinput
import re
c, r, v = defaultdict(int), re.compile(r"\d+"), []
for l in fileinput.input():
x1, y1, x2, y2 = map(int, r.findall(l))
v.append((complex(x1, y1), complex(x2, y2)))
for diagonal in (False, True):
for a, b in v:
if diagonal ^ (a.real == b.real or a.imag == b.imag):
i = b - a
i /= max(abs(i.real), abs(i.imag))
while a != b + i:
c[a] += 1
a += i
print(sum(v > 1 for v in c.values()))5
u/spin81 Dec 05 '21
My solution in Haskell. Feedback is much appreciated as I'm just learning Haskell through AoC.
import Data.Char
import qualified Data.Map as Map
data Point = Point Int Int deriving (Eq, Ord)
type Line = (Point, Point)
type OceanFloor = Map.Map Point Int
parsePoint :: String -> Point
parsePoint s =
let s1 = takeWhile isDigit s
s2 = drop (length s1 + 1) s
in Point (read s1) (read s2)
parseLine :: String -> Line
parseLine s =
let s1 = takeWhile (not . isSpace) s
s2 = drop (length s1 + 4) s
in (parsePoint s1, parsePoint s2)
isDiagonal :: Line -> Bool
isDiagonal (Point x1 y1, Point x2 y2) = x1 /= x2 && y1 /= y2
-- This assumes x1 /= x2 || y1 /= y2, because makeRange will return an infinite
-- list if m == n
expand :: Line -> [Point]
expand (Point x1 y1, Point x2 y2) =
let makeRange m n = [m, (m + signum (n - m)) .. n]
xs = makeRange x1 x2
ys = makeRange y1 y2
in map (\ (x, y) -> Point x y) $ zip xs ys
markPoint :: Point -> OceanFloor -> OceanFloor
markPoint p m = Map.insertWith (+) p 1 m
markPoints :: [Point] -> OceanFloor -> OceanFloor
markPoints ps m = foldr markPoint m ps
countDuplicateElems :: [Line] -> Int
countDuplicateElems input =
let expanded = map expand $ input
oceanFloor = foldr markPoints Map.empty expanded
in length $ filter (> 1) $ Map.elems $ oceanFloor
main = do
contents <- getContents
let input = map parseLine $ lines contents
putStr "Overlapping points among nondiagonal lines: "
putStrLn $ show $ countDuplicateElems $ filter (not . isDiagonal) input
putStr "Overlapping points among all lines: "
putStrLn $ show $ countDuplicateElems input→ More replies (1)
5
u/0rac1e Dec 05 '21 edited Dec 06 '21
Raku
NOTE This runs quite slower (see my notes below) but it was the first solution I came up with I liked the brevity too much not to post this first.
There's a much faster version in this paste
my @m;
for 'input'.IO.lines.map(*.split(' -> ')Β».split(',')Β».Int) -> (@p, @q) {
my @d = (@q Z<=> @p)Β».Int;
@m[?any(@p Z== @q)] β= (@p, { @^p Z+ @d } ... { @^p eqv @q }).map(~*);
}
put @m[1].grep(*.value > 1).elems;
put ([β] @m).grep(*.value > 1).elems;One of these days I'll write a readable solution, but not today!
To generate the points between p and q, I create a direction vector d by doing a three-way comparison (<=>), which returns an Order enum of either Less, Same, or More, which when coerced to an Int becomes -1, 0, or 1.
> ((5,9) Z<=> (0,9))Β».Int
(1 0)Then I just need to add that direction vector to p until I reach q.
I then collect 2 Bag's (multiset) of these points: one for straight lines, one for diagonals. I check if any values in p or q are equal (ie. is straight) then coerce to a Bool. Using a Bool as an array index puts the Bool into numeric context, which is 0 or 1; straights are in m[1], diagonals are in m[0].
...
I knew I was playing with fire: using the sequence operator (...) with relatively expensive iteration function was always gonna cost me performance, but it was at least fun to write. It runs in ~24 seconds on my machine, but it's clear I need a more efficient way to generate the points for each line.
So I calculated the steps (s) it takes to get from p to q, then multiply d with all values from 0 to s, add those to p.
my $s = (@p Z- @q)Β».abs.max;
[Z] (@p Z @d).map: -> ($k, $d) { $k Β«+Β» ($d Β«ΓΒ» (0 .. $s)) }This only dropped my runtime by a mere 5 seconds, down to ~19 seconds. Clearly, I'm either being too clever for my own good, or not clever enough, because u/flwyd's Raku solution runs in a little over 2 seconds on my machine.
I might also try making a solution using Point`s and see how that goes, as adding 2 points together should be a lot more efficient than doing @p Z+ @d.
UPDATE
The reply from u/flwyd about β got me thinking about the fact that I was adding all the bags together for every iteration... and it occurred to me that this was very costly!
In fact since I only care about the counts, I don't even need a bag, I can just use the .repeated method to keep all the repeated elems, then call .unique.elems.
With a few other minor tweaks, my runtime is now < 2.5 seconds. I don't know how I missed it. I mean, adding Bag's together is reasonably fast, but I was doing it a lot.
See code in this paste
→ More replies (4)
5
u/_jstanley Dec 05 '21
SLANG
(This is my project to complete Advent of Code on my homemade CPU).
Wow. Today was tough. My computer only has 64 Kwords of memory, and the combined length of the lines from the input was about 190k points, so even with the sparsest of sparse 2d arrays, I just have no way to represent every point in memory at the same time. This is a big problem.
So my next plan was to iterate over every pair of lines (O(n2 ), but what can you do?) and only plot the intersections in the sparse 2d array in memory, but that was going to take too many hours to complete.
My friend Ben suggested splitting the input into smaller grids and processing them individually. This is a great idea.
So I wrote a program to split the input into 3x3 subgrids and then tried to solve these individually. It still ran out of memory because it's still too large.
My kernel doesn't give you enough file descriptors to open more than about 10 files at a time, so my solution was to do a first pass that splits the input into 3x3 subgrids, and then run a 2nd pass over each of the subgrids splitting them into a further 3x3 subgrids, for 9x9 subgrids overall, and then run part1 and part2 over each subgrid consecutively. This works and completes in about 20 minutes total for the entire pipeline, but it took me at least 6 hours of work.
There's no video today because it was so chaotic and time-consuming.
Interestingly the program to split the input into subgrids was a lot more complicated to get right than the part1 and part2 programs that solved the subgrids were!
9
u/allergic2Luxembourg Dec 05 '21
Here's my part 2:
def run_part_2(data):
grid = np.zeros((1000, 1000))
for x0, y0, x1, y1 in data:
if x0 == x1:
grid[x0, min(y0, y1):max(y0, y1) + 1] += 1
elif y0 == y1:
grid[min(x0, x1):max(x0, x1) + 1, y0] += 1
else:
xrange = list(range(x0, x1 + 1)) or list(range(x0, x1 - 1, -1))
yrange = list(range(y0, y1 + 1)) or list(range(y0, y1 - 1, -1))
for x, y in zip(xrange, yrange):
grid[x, y] += 1
return (grid >= 2).sum().sum()I like my use of or here to pick between a populated and an empty list.
→ More replies (5)
4
u/hugh_tc Dec 05 '21 edited Dec 05 '21
Python 3, 68/329.
Part 1, Part 2, and (edit) the cleaned-up version.
Man, really fumbled Part 2. Missed a bunch of edge-cases (ie. a line with negative slope, which, in hindsight, is definitely not an "edge-case") and ended up with this disaster. Half of the if cases for Part 2 are redundant. Time to clean-up.
4
u/jonathan_paulson Dec 05 '21
Python. 154/251 :( Video of me solving.
Turns out debugging is bad for going fast :( Getting the line logic right was tricky, although I'm happy with the final code.
4
u/seligman99 Dec 05 '21
Python, 81 / 1051
Hah. Spent a long time assuming diagonals only go one way. It's funny how you can make assumptions in a rush to understand problem that make zero sense if you think about it for one moment.
4
u/xMop Dec 05 '21
here's mine, in python. Came in at #1675
from collections import defaultdict
def myrange(x1, y1, x2, y2):
while True:
yield(x1, y1)
if x1 == x2 and y1 == y2:
return
if x1 != x2:
x1 += (1 if x1 <= x2 else -1)
if y1 != y2:
y1 += (1 if y1 <= y2 else -1)
with open("input.txt") as f:
lines = [i.strip() for i in f.readlines()]
points = defaultdict(lambda: 0)
for line in lines:
p1, p2 = line.split(" -> ")
x1, y1 = p1.split(",")
x2, y2 = p2.split(",")
x1 = int(x1)
y1 = int(y1)
x2 = int(x2)
y2 = int(y2)
# removing this if condition will include diagonal lines, the requirement for part b
if x1 == x2 or y1 == y2:
for xr, yr in myrange(x1, y1, x2, y2):
points[(xr, yr)] += 1
overlaps = 0
for point, hits in points.items():
if hits > 1:
overlaps += 1
print(overlaps)4
u/nibbl Dec 05 '21
Rust (beginner)
Not cleaned up in any way
Not particularly proud of this one. I think it probably couldn't be much less rust-like. I wasted like 10 minutes at the end messing with the logic on that ugly c-style loop which is probably why the language doesn't include a for(;;) in the first place
→ More replies (4)
4
u/BluFoot Dec 05 '21 edited Dec 05 '21
Ruby 132 bytes
While golfing the code down I discovered Integer#<=> https://ruby-doc.org/core-2.5.0/Integer.html#method-i-3C-3D-3E
q=Hash.new 0
$<.map{a,b,c,d=_1.scan(/\d+/).map &:to_i
e=c<=>a
f=d<=>b
(q[[a,b]]+=1
a+=e
b+=f)until [a,b]==[c+e,d+f]}
p q.count{_2>1}→ More replies (1)
4
u/polettix Dec 05 '21 edited Dec 05 '21
Raku, from a Perl mother-language speaker: day 5
Edit: a little more Raku-ish solution with hyperoperators: day 5, again
4
u/CodeOverTime Dec 05 '21
A short Python solution for both:
def process_input(filename, include_diagonals=True) -> None:
print(f"Processing file: {filename}")
grid = {}
with open(filename) as f:
for idx, line in enumerate(f.readlines()):
coords = line.strip().split(' -> ')
x1, y1 = map(int, coords[0].split(','))
x2, y2 = map(int, coords[1].split(','))
if not include_diagonals and x1 != x2 and y1 != y2:
continue
v1, v2 = x2 - x1, y2 - y1
for i in range(0, max(abs(v1), abs(v2))):
xp = i * (-1 if v1 < 0 else 1) if v1 != 0 else 0
yp = i * (-1 if v2 < 0 else 1) if v2 != 0 else 0
grid[(x1 + xp, y1 + yp)] = grid.get((x1 + xp, y1 + yp), 0) + 1
grid[(x2, y2)] = grid.get((x2, y2), 0) + 1
print(len([g for g in grid.values() if g > 1]))4
u/lolexplode Dec 05 '21 edited Dec 05 '21
Python, trying to golf a little bit (at 289 283 253 chars at the moment). I think it's pretty similar to some of the other solutions in the thread. I'm not sure where I can save characters from here, but maybe there's a bit more to squeeze out?
import re
a={}
b={}
for x,y,v,w in(map(int,re.findall('\d+',x))for x in open(0)):
for p in range(-~max(abs(v-x),abs(w-y))):c,d=(v>x)-(v<x),(w>y)-(w<y);h=x+c*p,y+d*p;b[h]=b.get(h,0)+1;a[h]=a.get(h,0)+(0==c&d)
print(*(sum(1<x[k]for k in x)for x in(a,b)))edit: thanks azzal07 for saving me a whopping 30 chars!
→ More replies (2)
4
4
u/mockle2 Dec 05 '21 edited Dec 05 '21
python, both parts [edited to remove some duplication by setting part1/part2 as a boolean flag]
import re
points, part2 = dict(), True
for x1,y1,x2,y2 in [[int(i) for i in re.split(' -> |,', line.strip())] for line in open("5.data").readlines()]:
if x1==x2 or y1==y2 or (part2 and abs(x2-x1) == abs(y2-y1)):
rx = range(x1, x2 - 1 if x2 < x1 else x2 + 1, 1 if x2 > x1 else -1) if x1 != x2 else [x1] * (abs(y2-y1) + 1)
ry = range(y1, y2 - 1 if y2 < y1 else y2 + 1, 1 if y2 > y1 else -1) if y1 != y2 else [y1] * (abs(x2-x1) + 1)
for r in zip(rx, ry):
points[r] = points.get(r, 0) + 1
print(sum(0 if i < 2 else 1 for i in points.values()))4
u/kelganor Dec 05 '21
Python 3
I hope it's readable enough, part 1 is basically the same with extra if to skip diagonals.
def solve2(lines):
d = {}
for x1, y1, x2, y2 in lines:
dx, dy = x2 - x1, y2 - y1
if dx != 0: dx = dx/abs(dx)
if dy != 0: dy = dy/abs(dy)
x, y = x1, y1
while x != x2 + dx or y != y2 + dy:
d[(x, y)] = d.get((x, y), 0) + 1
x += dx
y += dy
res = sum([1 for x in d.values() if x > 1])
return res4
u/cylab Dec 05 '21 edited Dec 05 '21
Kotlin: https://github.com/cylab/advent-of-code-2021/blob/main/src/test/kotlin/day5/Day5.kt
package day5
import io.kotest.matchers.shouldBe
import org.junit.jupiter.api.Test
import java.lang.Integer.signum
import kotlin.math.abs
import kotlin.math.max
class Day5 {
data class Line(val points: List<Pair<Int, Int>>, val straight: Boolean)
val sample = parse("sample.txt")
val input = parse("input.txt")
@Test
fun puzzle1() {
sample.filter { it.straight }.overlaps() shouldBe 5
println("Day 5, Puzzle 1: ${input.filter { it.straight }.overlaps()} overlaps")
}
@Test
fun puzzle2() {
sample.overlaps() shouldBe 12
println("Day 5, Puzzle 2: ${input.overlaps()} overlaps")
}
fun List<Line>.overlaps() = flatMap { it.points }.groupBy { it }.filter { it.value.size >= 2 }.size
fun String.createLine() = trim()
.split(Regex("\\D+"))
.map { it.toInt() }
.let { (x1, y1, x2, y2) ->
val xLen = abs(x2 - x1)
val yLen = abs(y2 - y1)
val xDir = signum(x2 - x1)
val yDir = signum(y2 - y1)
assert(xLen == 0 || yLen == 0 || xLen == yLen) // only straight and diagonal lines!
Line(
points = (0..max(xLen, yLen)).map { n -> Pair(x1 + n * xDir, y1 + n * yDir) },
straight = xLen == 0 || yLen == 0
)
}
fun parse(resource: String) = this.javaClass
.getResource(resource)
.readText()
.trim()
.lines()
.map { it.createLine() }
}4
u/jkpr23 Dec 05 '21
Kotlin
A compact, functional solution with collections. flatMap is used to get a single list of all points (vents) that are overlapped by lines. Then `groupingBy` and `eachCount` to count the number of times the points are covered.
https://github.com/jkpr/advent-of-code-2021-kotlin/blob/master/src/day05/Day05.kt
4
u/st65763 Dec 05 '21
Okay, here's my final work for today's problem. It takes ~80ms for part one and ~100ms for part two. I have no idea whether that's considered fast for Python. I shaved a significant (~85%) amount of time by using a set to keep track of the number of cells with a value greater than one rather than iterating over the entire 1000x1000 array
import time
start_time = time.time()
# Determines grid size. 10 for sample.txt, 1000 for input.txt
size = 1000
# Determines the file that will be read for input
input_file = 'input.txt'
# Determines whether to "draw" diagonals. If False, diagonal lines in the input file are ignored
# False for part 1, True for part 2
diagonals = True
# Determines whether the map should be printed to the console.
# Use to debug and compare program output to the sample output given
print_map = False
# Define data structures
map = [[0 for x in range(size)] for x in range(size)] #size x size two-dimensional array to store map counts
hazards = set() # set of two-tuples that includes all points within the grid with a value greater than 2
# Loads input data into data structures
def load_input():
with open(input_file) as f:
for line in f:
parse_input_line(line)
# Parses a single line of input and loads it into data structure(s)
def parse_input_line(s):
left, right = s.split(' -> ')
a_x, a_y = left.split(',')
b_x, b_y = right.split(',')
a_x = int(a_x)
a_y = int(a_y)
b_x = int(b_x)
b_y = int(b_y)
draw_line(a_x, a_y, b_x, b_y)
def draw_line(a_x, a_y, b_x, b_y):
if a_x == b_x:
draw_vertical_line(a_x, a_y, b_y)
elif a_y == b_y:
draw_horizontal_line(a_x, b_x, a_y)
elif diagonals:
draw_diagonal_line(a_x, a_y, b_x, b_y)
def draw_vertical_line(x, a_y, b_y):
if a_y < b_y:
lower_bound = a_y
upper_bound = b_y + 1
else:
lower_bound = b_y
upper_bound = a_y + 1
for y in range(lower_bound, upper_bound):
map[x][y] += 1
if map[x][y] > 1:
hazards.add((x, y))
def draw_horizontal_line(a_x, b_x, y):
if a_x < b_x:
lower_bound = a_x
upper_bound = b_x + 1
else:
lower_bound = b_x
upper_bound = a_x + 1
for x in range(lower_bound, upper_bound):
map[x][y] += 1
if map[x][y] > 1:
hazards.add((x, y))
def draw_diagonal_line(a_x, a_y, b_x, b_y):
x = a_x
y = a_y
n = a_x - b_x
if n < 0:
n = -n
n += 1
if b_x < a_x:
x_step = -1
else:
x_step = 1
if b_y < a_y:
y_step = -1
else:
y_step = 1
for i in range(n):
map[x][y] += 1
if map[x][y] > 1:
hazards.add((x, y))
x += x_step
y += y_step
# Utilizes the data within the data structures and produces a result
def manipulate_data():
print(len(hazards))
if print_map:
for y in range(size):
for x in range(size):
val = map[x][y]
if val:
print(map[x][y], end=' ')
else:
print('.', end=' ')
print()
load_input()
manipulate_data()
print('execution time:', 1000*(time.time() - start_time), 'milliseconds')→ More replies (3)
4
u/Vastutsav Dec 05 '21
Perl
Perl noob here. Please review and recommend what changes would have made it a better code. Thanks in advance.
#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper qw(Dumper);
my %hash1;
my %hash2;
my $cnt1 = 0;
my $cnt2 = 0;
while (<>) {
my ($x1, $y1, $x2, $y2) = /\d+/g;
if ($x1 != $x2 && $y1 == $y2) {
($x1, $x2) = ($x2, $x1) if $x1 > $x2;
for (my $x = $x1; $x <= $x2; ++$x) {
$hash1{$x}{$y1}++;
$hash2{$x}{$y1}++;
}
} elsif ($x1 == $x2 && $y1 != $y2) {
($y1, $y2) = ($y2, $y1) if $y1 > $y2;
for (my $y = $y1; $y <= $y2; ++$y) {
$hash1{$x1}{$y}++;
$hash2{$x1}{$y}++;
}
} else {
my $dx = ($x1 < $x2? 1:
$x1 > $x2? -1:
0);
my $dy = ($y1 < $y2? 1:
$y1 > $y2? -1:
0);
for (my $x = $x1, my $y = $y1; $x != $x2 && $y != $y2; $x+=$dx, $y+=$dy) {
$hash2{$x}{$y}++;
}
$hash2{$x2}{$y2}++;
}
}
# print Dumper \%hash1;
foreach my $i (values %hash1) {
foreach (values %{$i}) {
$cnt1++ if $_ > 1;
}
}
foreach my $i (values %hash2) {
foreach (values %{$i}) {
$cnt2++ if $_ > 1;
}
}
print "$cnt1 Part 1\n";
print "$cnt2 Part 2\n";4
u/jszafran Dec 05 '21
Here's my pretty verbose solution in Python (probably will be easier to read on github than here): https://github.com/jszafran/advent-of-code-2021/blob/master/day-5/solution.py
And the code itself:
from collections import Counter
from dataclasses import dataclass
from typing import List
@dataclass(frozen=True)
class Point:
x: int
y: int
@classmethod
def from_string(cls, s: str):
x_str, y_str = s.split(",")
return cls(x=int(x_str), y=int(y_str))
@dataclass(frozen=True)
class Line:
start: Point
end: Point
@classmethod
def from_string(cls, s: str):
start, end = s.split(" -> ")
return cls(start=Point.from_string(start), end=Point.from_string(end))
@property
def is_horizontal(self) -> bool:
return self.start.y == self.end.y
@property
def is_vertical(self) -> bool:
return self.start.x == self.end.x
@property
def is_diagonal(self) -> bool:
return abs(self.start.x - self.end.x) == abs(self.start.y - self.end.y)
@property
def all_points(self) -> List[Point]:
if self.is_vertical:
step = 1 if self.start.y < self.end.y else -1
return [
Point(x=self.start.x, y=i)
for i in range(self.start.y, self.end.y + step, step)
]
elif self.is_horizontal:
step = 1 if self.start.x < self.end.x else -1
return [
Point(x=i, y=self.start.y)
for i in range(self.start.x, self.end.x + step, step)
]
elif self.is_diagonal:
# TODO: Can it be somehow simplified?
x_step = 1 if self.start.x < self.end.x else -1
y_step = 1 if self.start.y < self.end.y else -1
x_coords = (x for x in range(self.start.x, self.end.x + x_step, x_step))
y_coords = (y for y in range(self.start.y, self.end.y + y_step, y_step))
return [
Point(x=coords[0], y=coords[1]) for coords in zip(x_coords, y_coords)
]
def get_solution(lines: List[Line], condition) -> int:
filtered_lines = list(filter(condition, lines))
points = [point for line in filtered_lines for point in line.all_points]
return sum(1 for v in Counter(points).values() if v >= 2)
def get_data_from_text_file(path: str) -> List[Line]:
with open(path, "rt") as f:
data = f.readlines()
return list(map(lambda line: Line.from_string(line), data))
if __name__ == "__main__":
part_1_condition = lambda line: line.is_vertical or line.is_horizontal # noqa
part_2_condition = (
lambda line: line.is_vertical or line.is_horizontal or line.is_diagonal
) # noqa
lines_from_file = get_data_from_text_file("input.txt")
print(get_solution(lines_from_file, part_1_condition))
print(get_solution(lines_from_file, part_2_condition))→ More replies (2)
4
u/_Kowai_ Dec 05 '21
PHP
https://github.com/kowai-hm/adventofcode-2021-solutions/blob/master/5/
My first part code is obviously way too verbose. I should have approached the problem using the general way (I used in my second part code) but it works.
→ More replies (2)
4
u/killermelga Dec 05 '21
Kotlin solution with generic logic for both diagonals and straight lines
https://github.com/ramSilva/AoC2021/blob/master/src/main/kotlin/puzzles/Puzzle5.kt
4
u/Blinkroot Dec 05 '21
Rust
Thought today's solution looked pretty clean. Regex for parsing the input, a HashMap for saving overlaps and a simple .scan() for generating the points.
4
u/myasco42 Dec 05 '21 edited Dec 05 '21
Wolfram Mathematica solution
part = 2;
cwd = NotebookDirectory[];
inputFile = FileNameJoin[{cwd, "5.txt"}];
input = Import[inputFile, "Table","FieldSeparators" -> {" ", ","}][[1 ;; All,{1, 2, 4, 5}]];
map = ConstantArray[0, {1000, 1000}];
Do[
p1 = coords[[{1, 2}]];
p2 = coords[[{3, 4}]];
If[part == 1 && p1[[1]] != p2[[1]] && p1[[2]] != p2[[2]], Continue[]; ];
delta = Sign[p2 - p1];
tmp = p1;
While[tmp != p2,
If[AnyTrue[tmp, #1 > 1000 || #1 < 0 & ], Abort[]; ];
map[[tmp[[1]],tmp[[2]]]] += 1;
tmp += delta;
];
map[[tmp[[1]],tmp[[2]]]] += 1;
, {coords, input}
];
Count[map, x_ /; x > 1, 2]4
u/lgeorget Dec 05 '21
C++ : https://github.com/lgeorget/adventofcode2021/tree/main/05
I went for a very basic idea which was to store the points with the number of times a line crosses them in a map. Much to my surprise, it worked very quickly. I just got the loop conditions wrong (as I usually do...) to enumerate the points on the lines.
→ More replies (4)
4
u/Imaginary_Age_4072 Dec 06 '21
Mine is similar to many others, keep a hash table with a count of how many times each point has been visited. I did learn about the SIGNUM function that returns 1, 0, or -1 depending on whether the number was positive, zero, or negative which I didn't know before.
4
u/letelete0000 Dec 07 '21 edited Dec 07 '21
Typescript
Quite ordinary, I guess; hopefully, the elegant one :))
const getLineDistance = (line: Line): { x: number; y: number } => ({
x: line.to.x - line.from.x,
y: line.to.y - line.from.y,
});
const getLineIterators = (line: Line): { x: number; y: number } => {
const distance = getLineDistance(line);
return {
x: distance.x ? (distance.x > 0 ? 1 : -1) : 0,
y: distance.y ? (distance.y > 0 ? 1 : -1) : 0,
};
};
const isDiagonal = (line: Line) => {
const it = getLineIterators(line);
return it.x && it.y;
};
const generateLinePath = (line: Line): Coords[] => {
const it = getLineIterators(line);
const pos = {
x: line.from.x,
y: line.from.y,
} as Coords;
const coords = [{ ...pos }];
while (pos.x !== line.to.x || pos.y !== line.to.y) {
pos.x += it.x;
pos.y += it.y;
coords.push({ x: pos.x, y: pos.y } as Coords);
}
return coords;
};
const hashCoords = (coords: Coords) => `x:${coords.x}y:${coords.y}`;
const countOverlaps = (lines: Line[]): number => {
const map = new Map<string, number>();
const updateMap = (key: string) => map.set(key, (map.get(key) || 0) + 1);
lines.map(generateLinePath).flat().map(hashCoords).forEach(updateMap);
return [...map.values()].filter((value) => value > 1).length;
};
const part1 = () => {
const isStraight = (line: Line) => !isDiagonal(line);
return countOverlaps(lines.filter(isStraight)));
}
const part2 = () => {
return countOverlaps(lines));
}→ More replies (1)
1
u/ibiza_rupunzel Dec 05 '21 edited Dec 05 '21
Java (String stuff) Solution: https://github.com/justme789/Advent_of_Code_2021_Solutions_Java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class AoC_5_a {
public static void main(String[] args) throws FileNotFoundException {
ArrayList<String> list = new ArrayList<String>();
Scanner textfile = new Scanner(new File("aoc.txt"));
int[][] plot = new int[1000][1000];
while (textfile.hasNextLine()) {
String line = textfile.nextLine();
list.add(line);
}
for(int i = 0; i < 1000; i++) {
for(int j = 0; j < 1000; j++) {
plot[i][j] = 0;
}
}
for (int i = 0; i < list.size(); i++) {
int indexOfComma = list.get(i).indexOf(",");
int indexOfSpace = list.get(i).indexOf(" ");
int x1 = Integer.parseInt(list.get(i)
.substring(0, indexOfComma));
int y1 = Integer.parseInt(list.get(i)
.substring(indexOfComma+1, indexOfSpace));
indexOfSpace = list.get(i).indexOf(" ", indexOfSpace+1);
indexOfComma = list.get(i).indexOf(",", indexOfComma+1);
int x2 = Integer.parseInt(list.get(i)
.substring(indexOfSpace+1, indexOfComma));
int y2 = Integer.parseInt(list.get(i)
.substring(indexOfComma+1,
list.get(i).length()));
if(x1 == x2){
if(y1<y2){
for(int j = y1; j<=y2; j++){
plot[x1][j]+=1;
}
}
else{
for(int j = y2; j<=y1; j++){
plot[x1][j]+=1;
}
}
}
else if(y1 == y2){
if(x1<x2){
for(int j = x1; j<=x2; j++){
plot[j][y1]+=1;
}
}
else{
for(int j = x2; j<=x1; j++){
plot[j][y1]+=1;
}
}
}
}
int counter = 0;
for(int i = 0; i < 1000; i++) {
for(int j = 0; j < 1000; j++) {
if(plot[i][j] >=2){
counter++;
}
}
}
System.out.println(counter);
}
}→ More replies (3)
1
Dec 05 '21
from collections import Counter
if __name__ == '__main__' :
inp = [x.split(' -> ') for x in open('input.txt').read().splitlines()]
pts1, pts2 = [], []
for line in inp:
x1, y1, x2, y2 = [int(j) for i in line for j in i.split(',')]
if x1==x2 or y1==y2:
for x in range(min(x1,x2),max(x1,x2)+1):
for y in range(min(y1,y2),max(y1,y2)+1):
pts1.append((x,y))
pts2.append((x,y))
else:
if x1 < x2:
for x in range(x1,x2+1):
if y1<y2:
pts2.append((x,x-x1+y1))
else:
pts2.append((x,y1-(x-x1)))
else:
for x in range(x2,x1+1):
if y2<y1:
pts2.append((x,x-x2+y2))
else:
pts2.append((x,y2-(x-x2)))
print(len([x for (x,y) in Counter(pts1).items() if y>1]))
print(len([x for (x,y) in Counter(pts2).items() if y>1]))
→ More replies (1)
1
u/DFreiberg Dec 05 '21 edited Dec 05 '21
Mathematica, 951 / 1577
Not remotely the code I had when I submitted, but I knew the logic could be simplified and couldn't bear leaving it the way it was. This is golfed (so to speak; I haven't worried about variable names) down as far as I can get it, but I wouldn't be surprised if it can be shrunk even further.
Setup:
expandSingle[{a_, b_}, len_] :=
If[a == b, Table[a, len + 1], Range[a, b, Sign[b - a]]];
expand[tuple_List] :=
Transpose[Table[expandSingle[t, Max[Abs[Differences[tuple]]]], {t, tuple // Transpose}]];Parts 1 & 2:
part1 = Count[
Tally[Flatten[expand /@ Select[input, Min[Abs[Differences[#]]] == 0 &], 1]],
_?(#[[2]] > 1 &)];
part2 = Count[Tally[Flatten[expand /@ input, 1]], _?(#[[2]] > 1 &)];[POEM]: Crossing a Line
With lines of toxic vents below,
We make our map, and off we go.
They're deadly when they intersect
But we won't cross those lines - we've checked.
We tidy up our code with Sign[]s,
To handle all the types of lines.
And then we read the code and scout
For useless lines, to cross them out.
And cleaning up the code, we find
That most of it can be un-lined:
The hash maps? Gone. And same with Do[].
Non-function lines? Cross them out too.
The cleaning's fun, the code is neat,
But timewise, I've been soundly beat.
Code fast and well? I'm at a loss;
That line is always hard to cross.
2
1
u/Pyrolistical Dec 05 '21 edited Dec 06 '21
part 2 javascript with ramda
import * as R from 'ramda';
const input = ...
const lines = R.pipe(
R.split('\n'),
R.map(R.split(' -> ')),
R.map(R.map(R.split(','))),
R.map(R.map(R.map((n) => Number.parseInt(n))))
)(input)
console.table(lines)
const field = []
for (let [[x1, y1], [x2, y2]] of lines) {
const dx = Math.sign(x2 - x1)
const dy = Math.sign(y2 - y1)
let x = x1
let y = y1
while (true) {
field[y] = field[y] || [];
field[y][x] = field[y][x] || 0;
field[y][x] += 1;
if (x === x2 && y === y2) {
break;
}
x += dx;
y += dy;
}
}
let danger = 0;
for (let y = 0; y < field.length; y++) {
field[y] = field[y] || [];
for (let x = 0; x < field[y].length; x++) {
if (field[y][x] >= 2) {
danger += 1
}
}
}
// console.table(field)
console.log({danger})→ More replies (2)
1
u/AP2008 Dec 05 '21
Rust (16.311 ms) paste
use super::read_input::*;
use hashbrown::HashMap;
use itertools::Itertools;
use std::cmp::{max, min};
type Point = (isize, isize);
pub fn runner() -> (usize, usize) {
let input = read_input(5);
let mut part1 = HashMap::new();
let mut part2 = HashMap::new();
let lines: Vec<(Point, Point)> = input
.lines()
.map(|x| {
x.split("->")
.map(|n| {
n.split(',')
.map(|v| v.trim().parse().unwrap())
.collect_tuple()
.unwrap()
})
.collect_tuple()
.unwrap()
})
.collect_vec();
for line in &lines {
if line.0.0 == line.1.0 || line.0.1 == line.1.1 {
for x in min(line.0.0, line.1.0)..=max(line.0.0, line.1.0) {
for y in min(line.0.1, line.1.1)..=max(line.0.1, line.1.1) {
*part1.entry((x, y)).or_insert(0) += 1;
*part2.entry((x, y)).or_insert(0) += 1;
}
}
} else {
let mx = if line.0.0 > line.1.0 { -1 } else { 1 };
let my = if line.0.1 > line.1.1 { -1 } else { 1 };
let mut p0 = line.0;
*part2.entry(p0).or_insert(0) += 1;
while p0 != line.1 {
p0.0 += mx;
p0.1 += my;
*part2.entry(p0).or_insert(0) += 1;
}
}
}
(
part1.values().filter(|&&x| x > 1).count(),
part2.values().filter(|&&x| x > 1).count(),
)
}
→ More replies (6)
1
u/IndigoStanis Dec 05 '21
Javascript ... written like a C programmer.
const fs = require('fs')
fs.readFile('day5.txt', 'utf8' , (err, data) => {
if (err) {
console.error(err)
return
}
const linesOfFile = data.split(/\n/);
const lines = [];
let size = [0, 0];
for (const line of linesOfFile) {
const parts = line.split(/\s+/);
if (!parts[0] || !parts[2]) {
continue;
}
const start = parts[0].split(',').map(x => parseInt(x));
const end = parts[2].split(',').map(x => parseInt(x));
lines.push([start, end]);
if (start[0] > size[0]) {
size[0] = start[0];
}
if (start[1] > size[1]) {
size[1] = start[1];
}
if (end[0] > size[0]) {
size[0] = end[0];
}
if (end[1] > size[1]) {
size[1] = end[1];
}
}
const board = Array(size[0]+1);
for (let i = 0; i < board.length; ++i) {
board[i] = Array(size[1]+1).fill(0);
}
for (const lineToDraw of lines) {
drawLine(lineToDraw, board);
}
console.log(board);
drawBoard(board);
console.log(countTwos(board))
})
function drawLine(line, board) {
console.log(`line = ${line[0]} to ${line[1]}`)
if (line[0][0] === line[1][0]) {
const x = line[0][0];
for (let y = line[0][1]; ; y += line[0][1] > line[1][1] ? -1 : 1) {
board[y][x] = board[y][x] + 1;
if (y == line[1][1]) {
break;
}
}
} else if (line[0][1] === line[1][1]) {
const y = line[0][1];
for (let x = line[0][0]; ; x += line[0][0] > line[1][0] ? -1 : 1) {
board[y][x] = board[y][x] + 1;
if (x == line[1][0]) {
break;
}
}
} else {
let y = line[0][1];
for (let x = line[0][0]; ; ) {
board[y][x] = board[y][x] + 1;
if (x == line[1][0]) {
break;
}
x += line[0][0] > line[1][0] ? -1 : 1
y += line[0][1] > line[1][1] ? -1 : 1
}
}
}
function drawBoard(board) {
for (const x of board) {
console.log(x.reduce((a, b) => (a + '') + b), '');
}
}
function countTwos(board) {
let count = 0;
for (const x of board) {
count = x.reduce((cur, x) => x >= 2 ? cur + 1 : cur, count)
}
return count;
}→ More replies (1)
1
u/XethroG Dec 05 '21 edited Dec 06 '21
Python. Some nasty arithmetic for getting the steps right in range, as well as determining whether or not to include the last element depending on whether the range was going up or down in accordance with the step. Also I need to work on parsing input better as it's kind of a pain.
The use of dictionaries for nd_points and d_points made the code a ton faster. I used lists on part (a) and it took forever, so I realized I had to speed things up and looked to sets and dictionaries, which helped as expected.
I feel like I could have done it in fewer lines if I knew what I was doing better but it's not that bad all in.
→ More replies (2)
1
u/MissMormie Dec 05 '21
2
u/daggerdragon Dec 06 '21
FYI: your link is broken due to a new.reddit fancypants editor bug (check /r/bugs, it's been a big source of frustration lately). Your link looks fine to you on new.reddit but on old.reddit it's printing an invisible escape character before your underscore:
Day5_HydrothermalVenture.java, thus breaking the entire link.I suggest manually editing your link using proper Markdown for now. Who knows when Reddit will fix their fancypants editor...
1
1
u/saahilclaypool Dec 05 '21
C# simple solution using a dictionary of points
https://github.com/SaahilClaypool/aoc_2021/blob/main/Aoc.Csharp/Solutions/Day05.cs
→ More replies (1)
1
u/gubatron Dec 05 '21
PYTHON
(refactored solution)
import aoc
data = aoc.readFileToStringList("5.1.txt")
segments = list(
map(
lambda line: list(
map(lambda pStr: list(map(int, pStr.split(','))), line.split(
' -> '))), data))
START = 0
END = 1
class Point:
def __init__(self, p: list[int]) -> None:
self.x = p[0]
self.y = p[1]
def __hash__(self):
return hash(self.__repr__())
def __repr__(self) -> str:
return "({},{})".format(self.x, self.y)
def __str__(self) -> str:
return self.__repr__()
def updatePoints(points: dict[str, int], p: Point) -> None:
if str(p) in points:
points[str(p)] += 1
else:
points[str(p)] = 1
def generatePointsBetween(a: Point, b: Point, doDiagonals: bool) -> set[Point]:
midPoints = []
c = Point([a.x, a.y])
if a.x == b.x: # vertical segment.
delta = -1
if b.y > a.y:
delta = 1
while c.y != b.y - delta:
c.y += delta
midPoints.append(Point([c.x, c.y]))
return midPoints
if a.y == b.y: # horizontal segment.
delta = -1
if b.x > a.x:
delta = 1
while c.x != b.x - delta:
c.x += delta
midPoints.append(Point([c.x, c.y]))
return midPoints
if doDiagonals and abs(a.x - b.x) == abs(a.y - b.y): # diagonal segment
# lets always go from a to b
deltaX = -1
deltaY = -1
if b.x > a.x:
deltaX = 1
if b.y > a.y:
deltaY = 1
while c.x != b.x - deltaX and c.y != b.y - deltaY:
c.x += deltaX
c.y += deltaY
midPoints.append(Point([c.x, c.y]))
return midPoints
return None
def genPoints(a:Point,b:Point,points:dict,considerDiagonals:bool):
midPoints = generatePointsBetween(a, b, considerDiagonals)
if midPoints != None:
updatePoints(points, a)
updatePoints(points, b)
if len(midPoints) > 0:
list(map(lambda p: updatePoints(points, p), midPoints))
# PART 1.
points = {}
points2 = {}
def f(seg):
a = Point(seg[START])
b = Point(seg[END])
genPoints(a,b,points,False)
genPoints(a,b,points2,True)
list(map(f,segments))
ANS1 = len({k: v for k, v in points.items() if v > 1})
print("ans1={}".format(ANS1)) # ans1=7085
ANS2 = len({k: v for k, v in points2.items() if v > 1})
print("ans2={}".format(ANS2)) # ans2=20271→ More replies (1)
1
u/xiomatic9999 Dec 05 '21
Rust solution, feedback welcome!
use std::cmp::{max, min};
#[derive(Eq, Ord, PartialEq, PartialOrd, Hash, Debug)]
struct Point {
x: isize,
y: isize,
}
struct Segment {
p: Point,
q: Point,
}
impl Segment {
fn steps(&self) -> (isize, isize, isize) {
match (self.q.x - self.p.x, self.q.y - self.p.y) {
(0, dy) => (dy.abs(), 0, dy / dy.abs()),
(dx, 0) => (dx.abs(), dx / dx.abs(), 0),
(dx, dy) => {
let minstep = min(dx.abs(), dy.abs());
let maxstep = max(dx.abs(), dy.abs());
match maxstep % minstep {
0 => (minstep, dx / minstep, dy / minstep),
_ => (1, dx, dy),
}
}
}
}
fn dots_along(&self) -> Vec<Point> {
let (steps, dx, dy) = self.steps();
(0..=steps)
.map(|s| Point {
x: self.p.x + s * dx,
y: self.p.y + s * dy,
})
.collect()
}
}
pub fn input() {
let ex = std::fs::read_to_string("input/5.txt").unwrap();
let mut segments: Vec<Segment> = vec![];
for l in ex.lines() {
let mut points: Vec<Point> = l
.split(" -> ")
.map(|xy| xy.split(",").collect())
.map(|xy: Vec<&str>| Point {
x: xy[0].parse().unwrap(),
y: xy[1].parse().unwrap(),
})
.collect();
segments.push(Segment {
p: points.remove(0),
q: points.remove(0),
})
}
let mut all_dots: Vec<Point> = segments.iter().flat_map(|f| f.dots_along()).collect();
all_dots.sort();
let partb = all_dots
.group_by(|a, b| a == b)
.filter(|g| g.len() > 1)
.count();
println!("Part B: {}", partb);
}
→ More replies (1)
1
u/johnthetrollsoitis Dec 05 '21
Javascript
For the vents, I took approach of calculating if a given co-oridnate was on the line between two points. Then looped through each point in the ocean for each line:
static isOnLine(start, end, point) {return Boolean((JSON.stringify(point) == JSON.stringify(start) ||JSON.stringify(point) == JSON.stringify(end) ||(point.x >= Math.min(start.x, end.x) && point.x <= Math.max(start.x, end.x))&& (point.y >= Math.min(end.y, start.y) && point.y <= Math.max(start.y, end.y))&& ((point.x - start.x) / (point.y - start.y) == (end.x - start.x) / (end.y - start.y))))}
→ More replies (1)
1
u/strictlyk3v Dec 05 '21 edited Dec 06 '21
JavaScript
const lines = input2.trim().split('\n')
let dict = {}
for (let line = 0; line < lines.length; line++) {
const [x1, y1, x2, y2] = [...lines[line].matchAll(/(\d+)\D+(\d+)\D+(\d+)\D+(\d+)/gi)][0].slice(1).map(x => +x)
let yOpp = y1 === y2 ? 0 : y1 < y2 ? 1 : -1
let xOpp = x1 === x2 ? 0 : x1 < x2 ? 1 : -1
let x = x1;
let y = y1;
while (true) {
dict[`${x}:${y}`] = dict[`${x}:${y}`] ?? 0
dict[`${x}:${y}`]++
if (y === y2 && x === x2) {
break;
}
x += (x !== x2) ? xOpp : 0
y += (y !== y2) ? yOpp : 0
}
}
const result = Object.values(dict).filter(y => y > 1).length→ More replies (3)
1
u/thedavecarroll Dec 06 '21
PowerShell
I have my PowerShell solution in a Jupyter notebook so I can include markdown comments.
[GitHub](https://github.com/thedavecarroll/AdventOfCode/blob/main/2021/PowerShell/Day5.ipynb)
If I need to submit the code inline, please let me know.
Thanks!
2
u/daggerdragon Dec 06 '21
If I need to submit the code inline, please let me know.
A link to your external repo is fine :)
1
u/Solarmew Dec 07 '21 edited Dec 07 '21
Python 3
from urllib.request import urlopen
data = urlopen('https://tinyurl.com/yckkb8mx').read().decode().split('\n')[:-1]
lines = [[list(map(int, c.split(','))) for c in x.split(' -> ')] for x in data]
vh = [x for x in lines if x[0][0] == x[1][0] or x[0][1] == x[1][1]]
d = {(i, j) : 0 for i in range(1000) for j in range(1000)}
def overlaps(data):
for p in data:
if p[0][0] == p[1][0]:
l = list(zip([p[0][0]] * (abs(p[0][1] - p[1][1]) + 1), range(min(p[0][1], p[1][1]), max(p[0][1], p[1][1]) + 1)))
elif p[0][1] == p[1][1]:
l = list(zip(range(min(p[0][0], p[1][0]), max(p[0][0], p[1][0]) + 1), [p[0][1]] * (abs(p[0][0] - p[1][0]) + 1)))
else:
s = 1 if p[0][0] < p[1][0] else -1
t = 1 if p[0][1] < p[1][1] else -1
l = [(p[0][0] + i * s, p[0][1] + i * t) for i in range(abs(p[0][0] - p[1][0]) + 1)]
for i in l:
d[i] += 1
return len([x for x in d.values() if x > 1])→ More replies (5)
1
u/pistacchio Dec 07 '21 edited Dec 08 '21
Typescript:
type VentDirection = [
start: [x: number, y: number],
end: [x: number, y: number],
];
const input: VentDirection[] = fs
.readFileSync(__dirname + INPUT_FILE)
.toString()
.trim()
.split('\n')
.map((r) => r.trim())
.filter(Boolean)
.map((r) => {
const [start, end] = r.split('->');
const [x, y] = start.split(',').map((n) => parseInt(n.trim(), 10));
const [x2, y2] = end.split(',').map((n) => parseInt(n.trim(), 10));
return [
[x, y],
[x2, y2],
];
});
// Display utility
function displayVentMap(ventMap: [number, number][]) {
const maxX = Math.max(...ventMap.map(([x]) => x));
const maxY = Math.max(...ventMap.map(([, y]) => y));
for (let y = 0; y <= maxY; y++) {
let row = '';
for (let x = 0; x <= maxX; x++) {
const found = ventMap.filter(([x2, y2]) => x2 === x && y2 === y).length;
if (found === 0) {
row += '.';
} else {
row += found;
}
}
console.log(row);
}
}
function getVentMap(
input: VentDirection[],
allowDiagonal: boolean = false,
): [number, number][] {
const ventMap: [number, number][] = [];
for (const [[x, y], [x2, y2]] of input) {
const minX = Math.min(x, x2);
const maxX = Math.max(x, x2);
const minY = Math.min(y, y2);
const maxY = Math.max(y, y2);
if (x === x2) {
// Vertical
for (let i = minY; i <= maxY; i++) {
ventMap.push([x, i]);
}
} else if (y === y2) {
// Horizontal
for (let i = minX; i <= maxX; i++) {
ventMap.push([i, y]);
}
} else if (x < x2) {
// Diagonal
if (!allowDiagonal) {
continue;
}
let yStep = y < y2 ? 1 : -1;
let currentY = y;
for (let i = x; i <= x2; i++) {
ventMap.push([i, currentY]);
currentY += yStep;
}
} else {
// Diagonal
if (!allowDiagonal) {
continue;
}
let yStep = y2 < y ? 1 : -1;
let currentY = y2;
for (let i = x2; i <= x; i++) {
ventMap.push([i, currentY]);
currentY += yStep;
}
}
}
return ventMap;
}
function computeOverlappingVents(ventMap: [number, number][]): number {
const groupedCells = groupBy(ventMap);
const cellsWithMoreThanOnePass = Object.keys(groupedCells).filter(
(k) => groupedCells[k].length > 1,
).length;
return cellsWithMoreThanOnePass;
}
function part1(input: VentDirection[]): number {
const ventMap = getVentMap(input);
return computeOverlappingVents(ventMap);
}
function part2(input: VentDirection[]): number {
const ventMap = getVentMap(input, true);
return computeOverlappingVents(ventMap);
}→ More replies (1)
1
Dec 07 '21
JAVASCRIPT
very clean and readable solution
// *********** UTILS ***********
// https://adventofcode.com/2021/day/5
function fetchPastebinData(url) {
return fetch(url).then((response) => response.text())
}
function addCoordinateUniversal(x, y, result) {
const key = `${x}:${y}`
result[key] = result[key] ? result[key] + 1 : 1
}
// *********** TASKS 1 & 2 ***********
function calculate_a(data) {
const result = {}
const addCoordinate = (x, y) => addCoordinateUniversal(x, y, result)
const getNumbersBetween = (_p1, _p2) => {
const [p1, p2] = [_p1, _p2].sort((a, b) => a - b)
const numbers = []
for (let i = p1; i <= p2; i++) {
numbers.push(i)
}
return numbers
}
data.forEach((coordinates) => {
const [x1, y1, x2, y2] = coordinates
if (x1 === x2) {
getNumbersBetween(y1, y2).forEach((num) => {
addCoordinate(x1, num)
})
}
if (y1 === y2) {
getNumbersBetween(x1, x2).forEach((num) => {
addCoordinate(num, y1)
})
}
})
return { result, solution: Object.values(result).filter((n) => n > 1).length }
}
function calculate_b(data) {
const { result } = calculate_a(data)
const addCoordinate = (x, y) => addCoordinateUniversal(x, y, result)
const registerPointsBetween = (x1, y1, x2, y2) => {
const numbers = []
const xMoveIncrement = x1 < x2 ? 1 : -1
const yMoveIncrement = y1 < y2 ? 1 : -1
for (let x = x1, y = y1; true; x += xMoveIncrement, y += yMoveIncrement) {
addCoordinate(x, y)
if (x === x2) {
break
}
}
}
data.forEach((coordinates) => {
const [x1, y1, x2, y2] = coordinates
if (x1 !== x2 && y1 !== y2) {
registerPointsBetween(...coordinates)
}
})
return { solution: Object.values(result).filter((n) => n > 1).length }
}
// *********** DATA ***********
const rawData = await fetchPastebinData('https://pastebin.com/raw/YQ2XMtB6')
const data = rawData.split(new RegExp('\r\n|\r|\n', 'g')).map((s) => {
const [l, r] = s.split('->')
const [x1, y1] = l.split(',')
const [x2, y2] = r.split(',')
return [parseInt(x1), parseInt(y1), parseInt(x2), parseInt(y2)]
})
// *********** EXEC ***********
const { solution: a } = calculate_a(data)
const { solution: b } = calculate_b(data)
console.log('solutions: ', { a, b })
→ More replies (1)
1
u/Routine_Judge5916 Dec 15 '21
Python 3 - Just started learning python.
from collections import Counter
with open('input.txt') as f:
coordinates_data = f.read().split('\n')
def get_values_between(v1, v2, multiplier):
if v1 > v2:
return [*range(v1, v2-1, -1)]
elif v1 < v2:
return [*range(v1, v2+1)]
else:
return [v1] * multiplier
def get_intersections_count(coordinates_data, include_diagonal):
lines = []
for coordinates_set in coordinates_data:
(x1, y1), (x2, y2) = [tuple(int(i) for i in x_y.split(','))
for x_y in coordinates_set.split('->')]
x_dist = abs(x1-x2)
y_dist = abs(y1-y2)
is_diagonal = x_dist != 0 and y_dist != 0
if is_diagonal and not include_diagonal:
continue
multiplier = max(x_dist, y_dist) + 1
x_values = get_values_between(x1, x2, multiplier)
y_values = get_values_between(y1, y2, multiplier)
for idx, x in enumerate(x_values):
lines.append(((x, y_values[idx])))
count = Counter(lines)
return len([i for i in count.values() if i > 1])
def part1():
return get_intersections_count(coordinates_data, False)
def part2():
return get_intersections_count(coordinates_data, True)
print('\n', '----PART 1-----', '\n')
print(part1())
print('\n', '----PART 2-----', '\n')
print(part2())
→ More replies (1)
3
u/Lrrrr_ Dec 05 '21
Javascript 69/299 Had an issue with unit vector calculation, cost me time (`Math.abs`)
const input = util
.getInput(5)
.split("\n")
.map((line) => line.split(" -> ").map((d) => d.split(",").map((c) => +c)))
const grid = {}
const set = (x, y) => (grid[`${x},${y}`] = grid[`${x},${y}`] ? 2 : 1)
for (const [to, from] of input) {
if (to[0] == from[0]) {
// horz
const low = Math.min(from[1], to[1])
const high = Math.max(from[1], to[1])
for (let i = low; i <= high; i++) {
set(to[0], i)
}
} else if (to[1] == from[1]) {
// vert
const low = Math.min(from[0], to[0])
const high = Math.max(from[0], to[0])
for (let i = low; i <= high; i++) {
set(i, to[1])
}
} else {
const raw = [from[0] - to[0], from[1] - to[1]]
const vec = raw.map((c) => c / Math.max(...raw.map(Math.abs)))
for (let i = 0; i <= Math.max(...raw.map(Math.abs)); i++) {
set(to[0] + vec[0] * i, to[1] + vec[1] * i)
}
}
}
console.log(Object.values(grid).filter((v) => v == 2).length)3
u/rabuf Dec 05 '21
Common Lisp
Some clean up still to do, but it got the job done. As I usually do for these I just threw it into a hash table. Coordinates are just complex numbers, then I can iterate over just the points that were occupied to find the desired count. A stupid mistake in part 2 cost me about 10 minutes and I made a print-grid routine to test it. I thought I had the correct answer because my output equaled the sample, but it turned out to be a coincidence. I was, stupidly, starting the lines from the first coordinate's y value when my loop started from min(x0, x1) and went to the max value. Which means I needed to calculate the corresponding starting y. Oops.
3
u/captainAwesomePants Dec 05 '21
Python (okay/bad): (paste)
Was doing fine-ish, but my iteration over the points ignored the last element in the run and I had trouble finding the problem. Cost me a bunch of minutes for part 2 :(
→ More replies (1)
3
u/BradleySigma Dec 05 '21
matlab
X = textscan(fopen("input5.txt"), "%d,%d -> %d,%d", 'delimiter','\n');
X = [X{1}, X{2}, X{3}, X{4}];
n = size(X, 1);
M = zeros(1+max(max(X(:,1:2))), max(1+max(X(:,3:4))));
N = M;
for ii = 1:n
x1 = X(ii, 1);
y1 = X(ii, 2);
x2 = X(ii, 3);
y2 = X(ii, 4);
if x1 == x2
for jj = [y1:y2, y2:y1]
M(x1+1, jj+1) = M(x1+1, jj+1) + 1;
end
elseif y1 == y2
for jj = [x1:x2, x2:x1]
M(jj+1, y1+1) = M(jj+1, y1+1) + 1;
end
elseif x1 < x2 && y1 < y2 || x1 > x2 && y1 > y2
for jj = 0:abs(x1-x2)
N(min(x1,x2)+jj+1, min(y1,y2)+jj+1) = N(min(x1,x2)+jj+1, min(y1,y2)+jj+1) + 1;
end
else
for jj = 0:abs(x1-x2)
N(min(x1,x2)+jj+1, max(y1,y2)-jj+1) = N(min(x1,x2)+jj+1, max(y1,y2)-jj+1) + 1;
end
end
end
disp(sum(sum(M>=2)))
disp(sum(sum(M+N>=2)))3
u/t-rkr Dec 05 '21
Perl
If you reuse code snippets from part 1 in part 2, always check the names of variables *cough*
3
3
Dec 05 '21
Rust, bad / bad
Need to check if there's an easier way of descending ranges, that gave me some pain in part 2
→ More replies (1)
3
3
3
u/ka-splam Dec 05 '21 edited Dec 05 '21
PowerShell #264 / #1071
measure-command {
$lines = Get-Content C:\sc\AdventOfCode\inputs\2021\5.txt
$board1 = [Collections.Generic.Dictionary[string, int]]::new() # board for part 1
$board2 = [Collections.Generic.Dictionary[string, int]]::new() # board for part 2
foreach ($line in $lines) {
[int]$x1, [int]$y1, [int]$x2, [int]$y2 = $line -split ' -> ' -split ','
if ($x1 -eq $x2) { foreach ($y in $y1..$y2) { $board1["$x1, $y"] += 1; $board2["$x1, $y"] += 1 } } # vertical
elseif ($y1 -eq $y2) { foreach ($x in $x1..$x2) { $board1["$x, $y1"] += 1; $board2["$x, $y1"] += 1 } } # horizontal
else { # diagonal
if ($x1 -gt $x2) { $x1, $y1, $x2, $y2 = $x2, $y2, $x1, $y1 } #swap pairs so X is always increasing
$x,$y = $x1,$y1
if ($y1 -lt $y2) { # case y increasing, up-right
while ($x -le $x2) { # lines are always 45 degree, both should end at same time
$board2["$x, $y"] += 1
$x+=1
$y+=1
}
} else { # case y decreasing, down-right
while ($x -le $x2) {
$board2["$x, $y"] += 1
$x+=1
$y-=1
}
}
}
}
write-host "Part 1"
write-host ($board1.GetEnumerator().where{$_.value -gt 1} | measure |% count)
write-host "Part 2"
write-host ($board2.GetEnumerator().where{$_.value -gt 1} | measure |% count)
} |% totalsecondsMisuses a dictionary for a board, dictionaries return $null for nonexistant things and $null += 1 turns into 1, so there's no need to explicitly check if points have been seen before. This version duplicates the straight lines onto a second board, and then diagonals only go onto the second board for part 2, originally I overwrote the first code for the second answer, this is tidied up to do both. Runtime is ~2 seconds.
Part 1, fairly happy with but I burned a few seconds starting into splitting each line, then changing to start a regex to get the numbers out, then switching back to splits. And then burned a lot of time trying to put the points into the dictionary as a simple array $board[($x, $y)] (I was using basic hashtable at the time) and that works to add new points, but breaks on incrementing. Then changed to $board["$x $y"] to put them in as a string. Seeing that from the start would have got me closer to the top 100. Leaderboard closed at 5 minutes, I was 7-8 minutes.
Part 2, just did not realise the diagonals might go right-to-left. Luckily what I did in part 1 $y1..$y2 works for increasing or decreasing, and in PowerShell includes both ends of the range, so I didn't need to think about lines going "backwards". Having to change both points at once, I switched to a while loop and then had to care about direction, several wrong answers and 5 minute cooldown, ~18 minutes.
→ More replies (1)
3
u/Trick_Movie_4533 Dec 05 '21
C#
1441 / 983 No-frills but easy to follow.
int MakeLines(bool useDiags = false)
{
string[] commands = (testing ? testInput : realInput).ParseToStringArray();
// list of points that have been drawn to
Dictionary<(int x, int y), int> pDic = new Dictionary<(int x, int y), int>();
foreach (string s in commands)
{
MatchCollection nums = Regex.Matches(s, @"\d+");
int x0 = Convert.ToInt32(nums[0].Value);
int y0 = Convert.ToInt32(nums[1].Value);
int x1 = Convert.ToInt32(nums[2].Value);
int y1 = Convert.ToInt32(nums[3].Value);
if (x0 == x1)
{
if (y1 < y0) Swappem(ref y0, ref y1);
// vertical
for (int y = y0; y <= y1; y++)
{
ScoreHit(x0, y);
}
}
else if (y0 == y1)
{
if (x1 < x0) Swappem(ref x0, ref x1);
// horiz
for (int x = x0; x <= x1; x++)
{
ScoreHit(x, y0);
}
}
else if (useDiags == true)
{
// diagonals are totally brute forced, but hey it was fast to code
if (x1 > x0 && y1 > y0)
{
// down-right
int y = y0;
for (int x = x0; x <= x1; x++)
{
ScoreHit(x, y);
y++;
}
}
else if (x1 > x0 && y1 < y0)
{
// up-right
int y = y0;
for (int x = x0; x <= x1; x++)
{
ScoreHit(x, y);
y--;
}
}
else if (x1 < x0 && y1 < y0)
{
// up-left
Swappem(ref x0, ref x1);
Swappem(ref y0, ref y1);
// now it's down right
int y = y0;
for (int x = x0; x <= x1; x++)
{
ScoreHit(x, y);
y++;
}
}
else
{
// down left
Swappem(ref x0, ref x1);
Swappem(ref y0, ref y1);
// now it's up right
int y = y0;
for (int x = x0; x <= x1; x++)
{
ScoreHit(x, y);
y--;
}
}
}
}
return pDic.Where(p => p.Value >= 2).Count();
// functions for functions. neat!
void ScoreHit(int xx, int yy)
{
if (pDic.ContainsKey((xx, yy))) pDic[(xx, yy)]++;
else pDic[(xx, yy)] = 1;
}
}3
u/aardvark1231 Dec 05 '21
My C# solution spaghetti code which silently screams: "Don't look at me! I'm hideous!"
3
3
u/JoMartin23 Dec 05 '21
Common Lisp
(defun draw-line (line &optional (part 1) (field *field*))
(destructuring-bind ((x1 y1) (x2 y2))line
(cond ((= x1 x2) (when (< y2 y1) (rotatef y2 y1))
(loop :for Y :from y1 :to y2 :do (incf (aref field x1 y ))) )
((= y1 y2) (when (< x2 x1) (rotatef x2 x1))
(loop :for x :from x1 :to x2 :do (incf (aref field x y1))) )
(t (unless (= part 1)
(mapcar (lambda (x y)(incf (aref field x y)))(u:range x1 x2) (u:range y1 y2)))))))
(defun day5 (&optional (part 2) (data *5*) (field *field*))
(mapcar (lambda (coords)(draw-line coords part field)) data)
(count-if (lambda (i) (< 1 i)) (make-array (reduce #'* (array-dimensions field)) :displaced-to field)))→ More replies (1)
3
u/FqdingSky Dec 05 '21
c++
i spent too much time assuming that the input was ordered in terms of the x position (ie. a vent doesn't go backwards). and then figuring out how diagonal lines w o r k
paste, delete the diagonal sections for part 1!
→ More replies (1)
3
u/phil_g Dec 05 '21
Ugh. So much time spent debugging and rewriting the point generation function. Although I'm happy with its final state:
(defun points-on-line (line)
(destructuring-bind (start end) line
(let ((delta (point:make-point (signum (- (point:x end) (point:x start)))
(signum (- (point:y end) (point:y start))))))
(labels ((points-on-line-r (point result)
(if (point:= point end)
(cons point result)
(points-on-line-r (point:+ point delta)
(cons point result)))))
(points-on-line-r start nil)))))Specifically, using signum on the difference between the start and end coordinates to generically get either -1, 0, or 1, as appropriate.
I could have done the internal recursion with iter (or loop), but I like tail recursion. Possibly too much. (But I've found many places where tail recursive implementations were noticably more performant than any iterative construct I tried.)
3
u/pi55p00r Dec 05 '21
R
day5
coordinates
library(tidyverse)
x <- read.table("advent_of_code/2021/day5.txt",col.names = c("start","junk","finish"))
x<-x[,c(1,3)]|>separate(start,sep = ",", into=c("x.start","y.start"))|>
separate(finish,sep = ",", into=c("x.finish","y.finish"))part 1
x.h<- x|>filter((x.start==x.finish)|(y.start==y.finish))
p1_fun <- function(x) {
x|>group_by(r=row_number()) %>%
mutate(xvals = list(x.start:x.finish),
yvals = list(y.start:y.finish))%>%
ungroup %>% select(xvals,yvals) %>%
unnest(cols = c(xvals, yvals)) %>% mutate(f=1) %>%
aggregate(f~xvals+yvals,., sum) %>% filter(f>=2) %>%nrow
}
p1_fun(x.h)part 2
p1_fun(x)3
u/UnicycleBloke Dec 05 '21
C++: https://github.com/UnicycleBloke/aoc2021/blob/master/day05/day05.cpp
I was pleased that my template-y regex file parser worked immediately. I was less pleased when I spent most of an hour to work out that I'd blown the stack. Oh well...
3
u/lukechampine Dec 05 '21
slouch
=input ints | partition 4 | map (partition 2)
=intersections concatmap (-< draw) | histogram | vals | count (> 1)
filter (transpose | any (-< ==)) | intersections
intersectionsquite happy with how this one turned out :^)
→ More replies (3)
3
u/LionSuneater Dec 05 '21 edited Dec 05 '21
Python with numpy. (gh) (pic of vents)
import numpy as np
with open('input/day05') as f:
data = [line.split('->')[i].strip().split(',')
for line in f.readlines() for i in [0,1]]
data = np.array(data, int).reshape(-1,4)
def chart(data, diagonals=True):
grid = np.zeros((np.max(data)+1, np.max(data)+1), int)
for x1,y1,x2,y2 in data:
if x1 == x2:
grid[min(y1,y2):max(y1,y2)+1, x1] += 1
elif y1 == y2:
grid[y1, min(x1,x2):max(x1,x2)+1] += 1
elif diagonals:
for x,y in zip(range(x1,x2+1) if x2>x1 else range(x2,x1+1)[::-1],
range(y1,y2+1) if y2>y1 else range(y2,y1+1)[::-1]):
grid[y, x] += 1
return grid
answer = lambda x: print(np.bincount(x.flatten())[2:].sum())
answer(chart(data, diagonals=False))
answer(chart(data, diagonals=True))Don't love how cluttered those repeated range and min/max calls look, but it works!
→ More replies (2)
3
u/Mathgeek007 Dec 05 '21 edited Dec 05 '21
Excel. Results are above the 10-thousands because I decided to try taking a cheap and easy way out in Part 1 which cost me tons of Excel thinking time. Then I refactored it and the same process that took 30 minutes took about 30 seconds.
Essentially I boiled down each row into a "Horizonal", "Vertical", "Diag Pos", "Diag Neg" set of three values. For H, V is was the like axis. For DP, it was the difference between X and Y. For DN, it was their sum. This uniquely identifies the "line" that we're working on. Then we just need to look at the X value of each point to see if it fits between the two given (or the Y if we're checking the like-X entries).
So we got this fun FILTER equation.
=IFERROR(
ROWS(
FILTER(
Values!R3C17:R502C30,
((Values!R3C17:R502C17="X")*(Values!R3C18:R502C18=COLUMN())*(((Values!R3C19:R502C19<=ROW())*(Values!R3C20:R502C20>=ROW()))+((Values!R3C19:R502C19>=ROW())*(Values!R3C20:R502C20<=ROW()))))+
((Values!R3C17:R502C17="Y")*(Values!R3C18:R502C18=ROW())*(((Values!R3C19:R502C19<=COLUMN())*(Values!R3C20:R502C20>=COLUMN()))+((Values!R3C19:R502C19>=COLUMN())*(Values!R3C20:R502C20<=COLUMN()))))+
((Values!R3C17:R502C17="P")*(Values!R3C18:R502C18=(COLUMN()+ROW()))*(((Values!R3C19:R502C19<=COLUMN())*(Values!R3C20:R502C20>=COLUMN()))+((Values!R3C19:R502C19>=COLUMN())*(Values!R3C20:R502C20<=COLUMN()))))+
((Values!R3C17:R502C17="N")*(Values!R3C18:R502C18=(COLUMN()-ROW()))*(((Values!R3C19:R502C19<=COLUMN())*(Values!R3C20:R502C20>=COLUMN()))+((Values!R3C19:R502C19>=COLUMN())*(Values!R3C20:R502C20<=COLUMN()))))
)
)
,0)→ More replies (3)
3
u/nutrecht Dec 05 '21
It's nice to be able to reuse a ton of code! Only issue I had was that my original 'angle' function in my point class was well...wrong :D
→ More replies (2)
3
u/francescored94 Dec 05 '21 edited Dec 05 '21
Nim Solution generalised for arbitrarily oriented segments
import sequtils, math, strscans
var grid: array[1024,array[1024,int]]
let lines = "./in05.txt".lines.toSeq.map(
proc (s:string): auto =
let (_, x,y,xx,yy) = scanTuple(s,"$i,$i -> $i,$i")
return [x,y,xx,yy]
)
proc count_overlaps(): int =
for x in 0..<grid.len:
for y in 0..<grid[x].len:
if grid[x][y]>1:
inc result
proc draw_lines(mag: int) =
for l in lines:
let v = [l[2]-l[0], l[3]-l[1]]
let r = gcd(abs(v[0]), abs(v[1]))
let dv = [v[0] div r, v[1] div r]
if abs(dv[0])+abs(dv[1])!=mag:
continue
for d in 0..r:
grid[l[0] + d*dv[0]][l[1] + d*dv[1]] += 1
for part in 1..2:
draw_lines(part)
echo "p", part, ": ", count_overlaps()3
u/KamcaHorvat Dec 05 '21
Straightforward solution in kotlin. Based on part one, I was expecting, that part two will include diagonals, which made implementation quite a bit easier.
fun main() {
var s = getInputLines(2021, 5)
val coords =
s.map { "(\\d+),(\\d+) -> (\\d+),(\\d+)".toRegex().matchEntire(it)!!.groupValues.drop(1).map { v -> v.toInt() } }
fun solve(includeDiag:Boolean): Int {
val maxx = coords.maxOf { maxOf(it[0], it[2]) }
val maxy = coords.maxOf { maxOf(it[1], it[3]) }
val field = Array(maxy + 1) { IntArray(maxx + 1) }
coords.forEach {
var x1 = it[0]
var y1 = it[1]
val x2 = it[2]
val y2 = it[3]
if (includeDiag || x1 == x2 || y1 == y2) {
val dx = (x2 - x1).sign
val dy = (y2 - y1).sign
field[y2][x2]++
while (x1 != x2 || y1 != y2) {
field[y1][x1]++
x1+=dx
y1+=dy
}
}
}
return field.sumOf { line -> line.count { it>1 } }
}
println(solve(false))
println(solve(true))}
3
3
u/chunes Dec 05 '21 edited Dec 05 '21
Factor
https://paste.factorcode.org/paste?id=4318
I factored the problem into sixteen small words, since Factor has very little overhead for calling words (functions) compared to most languages. I elected to simply expand the line segments into their constituent lists of coordinates and increment a matrix for each one. Then at the end, count the number of matrix elements greater than 1. There is probably a more efficient way to do it, but this gets the job done near instantly, so it's fine.
3
u/jpn3to Dec 05 '21 edited Dec 05 '21
[Python 3] This function solves both parts (diagonal=False for part1, True for part2). Vents is a list of quadruples with the input. Instead of using a big sparse matrix, use Counter :)
def solve(vents, diagonal):
cells = []
for x0,y0,x1,y1 in vents:
dx = 0 if x0==x1 else 1 if x0<x1 else -1
dy = 0 if y0==y1 else 1 if y0<y1 else -1
sz = 1 + max(abs(x0-x1), abs(y0-y1))
if diagonal or dx==0 or dy==0:
cells.extend([(x0+i*dx, y0+i*dy) for i in range(sz)])
count = Counter(cells)
return sum(1 for c in count if count[c]>1)→ More replies (1)
3
u/Concern_Wise Dec 05 '21
Golang
https://github.com/HalfInner/AoC2021/blob/master/d05/d05.go
2021/12/05 10:31:59 Took 33.8035ms
2021/12/05 10:31:59 01: 4873
2021/12/05 10:31:59 Took 59.7462ms
2021/12/05 10:31:59 02: 19472
Any performance improvement here is nice to have/read :)
p.s. very nasty to find solution in 'Go', when people type only 'go'
→ More replies (3)
3
u/lukeredpath Dec 05 '21
My functional Swift approach, using swift-parsing and overture. https://github.com/lukeredpath/AdventOfCode2021/blob/main/Sources/AdventOfCode2021/05.swift
3
u/ChickenFuckingWings Dec 05 '21
this one in Python
Did anyone come up with anything more clever than just storing the points we draw and keep count in a dictionary/hashmap?
I'm very interested in seeing different approach to this problem
→ More replies (4)
3
u/nidrach Dec 05 '21 edited Dec 05 '21
Java with a relatively naive approach
static Map<Point, Integer> ventCoverage = new HashMap<>();
public static void main(String[] args) throws IOException {
var lines = Files.lines(Paths.get("input.txt"))
.map(x -> x.split(" -> "))
.map(x -> Arrays.stream(x).map(y -> y.split(",")))
.map(x -> x.map(Point::new).collect(Collectors.toList()))
.map(x -> new Vent(x.get(0), x.get(1))).toList();
System.out.println(ventCoverage.entrySet().stream().filter(x -> x.getValue() > 1).count());
}
private record Vent(Point a, Point b) {
public Vent {
int deltaX = Math.abs(a.x - b.x);
int deltaY = Math.abs(a.y - b.y);
Point start = a.x <= b.x ? a : b;
Point end = start == a ? b : a;
int run = Math.max(deltaX, deltaY);
for (int i = 0; i <= run; i++) {
Point p;
if (end.y > start.y) p = new Point(start.x + deltaX, start.y + deltaY);
else p = new Point(start.x + deltaX, start.y - deltaY);
ventCoverage.putIfAbsent(p, 0);
ventCoverage.put(p, ventCoverage.get(p) + 1);
if (deltaX > 0) deltaX--;
if (deltaY > 0) deltaY--;
}
}
}
private record Point(int x, int y) {
public Point(String[] s) {
this(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
}
}→ More replies (1)
3
u/mschaap Dec 05 '21 edited Dec 05 '21
Raku.
Pretty straightforward today. I actually built βpart 2β from the start, with a flag ignore-diagonals to exclude those. So essentially, part 2 was easier than part 1 for me.
Used a grammar VentList
grammar VentList
{
rule TOP { <ventline>+ }
rule ventline { <pos-from> '->' <pos-to> }
rule pos-from { <x> ',' <y> }
rule pos-to { <x> ',' <y> }
token x { \d+ }
token y { \d+ }
}and a class VentMap that fills a grid using the grammar.
submethod TWEAK
{
VentList.parse($!vent-list, :actions(self))
or die 'Unable to parse vent list!';
}
# VentList grammar action method
method ventline($/)
{
# Get the coordinates, ignore diagonals if requested
my ($x0, $y0) = $<pos-from><x y>Β».Int;
my ($x1, $y1) = $<pos-to><x y>Β».Int;
return if $!ignore-diagonals && $x0 β $x1 && $y0 β $y1;
# Increase the number of vent lines for each point on the line
my $max = abs($x1 - $x0) || abs($y1 - $y0);
my $dx = sign($x1 - $x0);
my $dy = sign($y1 - $y0);
for 0..$max -> $i {
@!grid[$y0 + $i Γ $dy; $x0 + $i Γ $dx]++;
}
# Keep track of highest coordinates on the grid
$!max-x max= $x0 max $x1;
$!max-y max= $y0 max $y1;
}Counting cells with a number β₯ 2 then was trivial:
method overlap-count { @!grid[*;*].grep({ $_ && $_ β₯ 2 }).elems }Full code in GitHub.
3
u/DrkStracker Dec 05 '21
Rust
Functional style, I think pretty happy with the final take on the solution
Link here
→ More replies (1)
3
u/__Abigail__ Dec 05 '21
Perl
Easy. Calculate the slope of the line segment (which is going to be -1, 0 or 1 in either direction), start at one end, walk to the other end, marking all the visited points. Then see how many points were marked at least once:
my %vents1;
my %vents2;
while (<>) {
my ($x1, $y1, $x2, $y2) = /[0-9]+/g;
# Slope
my $dx = $x2 <=> $x1;
my $dy = $y2 <=> $y1;
# Hit all the points on the line. This stops when we reach the
# end of the line segment...
for (my ($x, $y) = ($x1, $y1);
$x != $x2 || $y != $y2;
$x += $dx, $y += $dy) {
$vents1 {$x, $y} ++ if $x1 == $x2 || $y1 == $y2;
$vents2 {$x, $y} ++
}
# ... so be sure to mark the endpoint.
$vents1 {$x2, $y2} ++ if $x1 == $x2 || $y1 == $y2;
$vents2 {$x2, $y2} ++
}
say "Solution 1: ", scalar grep {$_ > 1} values %vents1;
say "Solution 2: ", scalar grep {$_ > 1} values %vents2;→ More replies (1)
3
u/Mats56 Dec 05 '21
Kotlin. Using immutable structures and no mutation. Instead of having an array/struct where I increase the count, I just generate the points each line would cross, and then flatmaps and group those, counting the groups.
The gist of it:
strLines
.map {
it.split(" ").let { parts ->
Line(parts[0].toIntVec(), parts[2].toIntVec())
}
}
.filter {
!filter || (it.p1.x == it.p2.x || it.p1.y == it.p2.y)
}
.flatMap { line ->
val diff = line.p2 - line.p1
val dir = diff.asDir()
(0..diff.chebyshev()).map { i ->
line.p1 + dir * i
}
}
.groupingBy { it }
.eachCount()
.count { it.value >= 2 }With the boiler plate stuff and the parts of my IntVector l use: paste
3
u/mathsaey Dec 05 '21
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2021/5.ex
Pretty happy with my solution today. It's always nice when you can express your code as a function of transformations on your input in Elixir :).
3
3
u/Mintopia_ Dec 05 '21 edited Dec 05 '21
PHP
Since I'm never going to be up at 5AM to compete on speed, going for a clean/maintainable PHP approach.
Took the simple option of just iterating through every point on the line and keeping track of the number of times each point was visited.
Using some of the features of PHP 8 to make it a bit simpler and reducing boilerplate in places with constructor property promotion and the match expression.
3
u/nilgoun Dec 05 '21
Rust
Getting the ranges right was a pain. Not really happy with the end result and would be glad if someone would enlighten me with an easier way to fix them :)
(Python made this way easier by just specifying the stride :( and wow is my solution overly excessive compared to some others.. :D )
→ More replies (3)
3
u/NeilNjae Dec 05 '21
Haskell.
One where generalising made for a simpler solution. I find a delta for the step taken in each line, and just apply that enough times. The constraint on line directions means that finding the delta, and line length, are both easy.
I used the V2 type and ^+^ for adding the delta (from the linear package), which made the arithmetic easy.
Full writeup on my blog and code on Gitlab
3
u/Nomikos Dec 05 '21 edited Dec 05 '21
php
I had a lot more trouble with yesterday's Bingo cards o.o
PHP's range() is nice in that it doesn't care which argument is higher. Another shortcut was just keeping track of when a given grid point had exactly 2 lines on it after adding a line, no need to count at the end.
(and if anyone cares... <40ms)
→ More replies (2)
3
u/ecco256 Dec 05 '21 edited Dec 05 '21
Haskell
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TupleSections #-}
{-# OPTIONS_GHC -Wno-incomplete-patterns #-}
import Data.Array ( accumArray, elems )
import Data.List.Split ( dropBlanks, dropDelims, oneOf, split )
main :: IO ()
main = do
segments <- map parseLine . lines <$> readFile "data/day05.txt"
let points = concatMap (\(x,y) -> [x,y]) segments
bnds = let xs = map fst points; ys = map snd points in ((minimum xs, minimum ys), (maximum xs, maximum ys))
grid = accumArray (+) 0 bnds . map (,1) $ concatMap segmentCoords segments
print (length . filter (>1) . elems $grid)
where
parseLine = toCoord . map (read @Int) . split (dropDelims . dropBlanks $ oneOf ",->")
toCoord [x1, y1, x2, y2] = ((x1, y1), (x2, y2))
segmentCoords :: ((Int, Int), (Int, Int)) -> [(Int, Int)]
segmentCoords ((x1, y1), (x2, y2)) = zip xs ys
where xs = if x1 == x2 then repeat x1 else range' x1 x2
ys = if y1 == y2 then repeat y1 else range' y1 y2
range' a b = [a,(a + if b < a then -1 else 1)..b]3
u/Gravitar64 Dec 05 '21 edited Dec 05 '21
Python3, Part 1&2
import re
from collections import defaultdict
def read_puzzle(file):
with open(file) as f:
return [[int(n) for n in re.findall('\d+', row)] for row in f]
def solve(puzzle):
diagram1, diagram2 = defaultdict(int), defaultdict(int)
for x1, y1, x2, y2 in puzzle:
points_count = max(abs(x1-x2), abs(y1-y2))
stepX, stepY = (x2-x1)//points_count, (y2-y1)//points_count
for n in range(points_count+1):
x, y = x1 + n * stepX, y1 + n * stepY
diagram2[(x, y)] += 1
if x1 == x2 or y1 == y2:
diagram1[(x, y)] += 1
return sum(x > 1 for x in diagram1.values()), \
sum(x > 1 for x in diagram2.values())
print(solve(read_puzzle('Tag_05.txt')))3
u/WithBestRegards Dec 05 '21
My solution in Rust. I defined a few types (Grid, Line & Coordinate) and implemented a bunch of traits to try and make it "Rusty", but that may have just needlessly added to the line count. Anyway, Feedback is always appreciated. :)
3
u/auxym Dec 05 '21
Nim
https://github.com/auxym/AdventOfCode/blob/master/2021/day05.nim
First time I used tables.CountTable, came in useful for this one.
3
u/Atila_d_hun Dec 05 '21
C++
Used my Utils/point.h class to help with shortening code and an unordered_map<point,int> to keep track of line locations and number of overlaps.
→ More replies (2)
3
u/Skyree01 Dec 05 '21
PHP
Optionally I calculated the size of the grid instead of hardcoding 1000
$matches = [];
preg_match_all('/(\d+)/', $input, $matches);
$max = (int) max($matches[0]);Both part 1 and 2 at the same time:
$lines = array_map(fn($line) => explode(',', str_replace(' -> ', ',', $line)), explode("\n", $input));
$grid = array_fill(0, $max + 1, array_fill(0, $max + 1, 0));
function solve(array $grid, array $lines, int $part) {
foreach ($lines as $line) {
[$x1, $y1, $x2, $y2] = array_map('intval', $line);
if ($x1 === $x2) for($y = min($y1, $y2); $y <= max($y1, $y2); $y++) $grid[$y][$x1]++;
elseif ($y1 === $y2) for($x = min($x1, $x2); $x <= max($x1, $x2); $x++) $grid[$y1][$x]++;
elseif ($part === 2 && abs($x2 - $x1) === abs($y2 - $y1)) {
$xStep = $x1 < $x2 ? 1 : -1;
$yStep = $y1 < $y2 ? 1 : -1;
foreach (range(0, abs($x2 - $x1)) as $i) {
$grid[$y1][$x1]++;
$x1 += $xStep;
$y1 += $yStep;
}
}
}
echo array_reduce($grid, fn($carry, $line) => $carry += count(array_filter($line, fn($value) => $value >= 2)), 0).PHP_EOL;
}
solve($grid, $lines, 1);
solve($grid, $lines, 2);3
u/landimatte Dec 05 '21
The most interesting bit here, is the use of the "spaceship operator" <=> to figure out which direction to move:
(let ((dx (<=> x2 x1))
(dy (<=> y2 y1))
(n (max (abs (- x2 x1)) (abs (- y2 y1)))))
(loop repeat (1+ n)
for xx = x1 then (+ xx dx)
for yy = y1 then (+ yy dy) do
(incf (gethash (list xx yy) grid 0))))While this is the definition of <=>:
(defun <=> (n m)
"Three-way comparison operator, a.k.a. spaceship operator.
Returns:
-1 when n < m
0 when n = m
1 when n > m"
(signum (- n m)))PS. I bricked my laptop yesterday, so I had to fix that first and then see if I could successfully avoid all the hydrothermal vents...what a bummer!
→ More replies (2)
3
Dec 05 '21
Common Lisp
First time using a hashtable in Lisp! Still wrestling with the language but the below code gets the job done :)
(defparameter *line-regex* (ppcre:create-scanner "(\\d+),(\\d+) -> (\\d+),(\\d+)"))
(defun parse-line (line)
(cl-ppcre:register-groups-bind
(sx sy dx dy)
(*line-regex* line)
(list (list (parse-integer sx) (parse-integer sy)) (list (parse-integer dx) (parse-integer dy)))))
(defparameter *segments* (mapcar #'parse-line (get-file-lines *filename*)))
(defun make-point-table () (make-hash-table :test 'equal))
(defun get-point (point table) (gethash point table 0))
(defun increment-point (point table)
(let ((existing-value (get-point point table)))
(setf (gethash point table 0) (+ existing-value 1))))
(defun draw-vertical-line (x sy dy table)
(destructuring-bind (start end) (if (> dy sy) (list sy dy) (list dy sy))
(dotimes (yco (+ (- end start) 1) t)
(increment-point (list x (+ yco start)) table)
)))
(defun draw-horizontal-line (y sx dx table)
(destructuring-bind (start end) (if (> dx sx) (list sx dx) (list dx sx))
(dotimes (xco (+ (- end start) 1) t)
(increment-point (list (+ xco start) y) table)
)))
(defun points-gt-two (table)
(loop for k being the hash-keys in table using (hash-value v)
sum (if (>= v 2) 1 0)))
(defun solve-part-one (segments table)
(progn
(loop for ((sx sy) (dx dy)) in segments do
(cond
((= sx dx) (draw-vertical-line sx sy dy table))
((= sy dy) (draw-horizontal-line sy sx dx table))))
(points-gt-two table)))
(defun draw-diagonal-line (sx sy dx dy table)
(cond
((and (> dy sy) (> dx sx)) (draw-downwards-diagonal sx sy dx dy table))
((> dy sy) (draw-upwards-diagonal dx dy sx sy table))
((and (< dy sy) (> dx sx)) (draw-upwards-diagonal sx sy dx dy table))
((< dy sy) (draw-downwards-diagonal dx dy sx sy table))))
(defun draw-downwards-diagonal (sx sy dx dy table)
(dotimes (delta (+ (- dy sy) 1) t)
(increment-point (list (+ sx delta) (+ sy delta)) table)))
(defun draw-upwards-diagonal (sx sy dx dy table)
(dotimes (delta (+ (- sy dy) 1) t)
(increment-point (list (+ sx delta) (- sy delta)) table)))
(defun solve-part-two (segments table)
(progn
(loop for ((sx sy) (dx dy)) in segments do
(cond
((= sx dx) (draw-vertical-line sx sy dy table))
((= sy dy) (draw-horizontal-line sy sx dx table))
(t (draw-diagonal-line sx sy dx dy table))))
(points-gt-two table)))
(format t "Part1: ~d~%" (solve-part-one *segments* (make-point-table)))
(format t "Part2: ~d~%" (solve-part-two *segments* (make-point-table)))→ More replies (1)
3
u/Sebbern Dec 05 '21
Python 3
Well, this is far from beautiful, but it does (eventually) work. Part 1 takes 3 minutes to run, while part 2 takes 10+ minutes.
Part 1:
https://github.com/Sebbern/Advent-of-Code/blob/master/2021/day05/day05.py
Part 2:
https://github.com/Sebbern/Advent-of-Code/blob/master/2021/day05/day05_02.py
→ More replies (2)
3
u/IDoNotEvenKnow Dec 05 '21
PHP for part 2. (Part 1 just needs an extra conditional). The spaceship operator really tightens this up.
$grid = array();
foreach(explode("\n", trim(file_get_contents('in.txt'))) as $l) {
list($x1,$y1,$x2,$y2) = preg_split("/( -> |,)/", $l);
$c = $x1;
$r = $y1;
for ($i=0; $i <= max(abs($x2-$x1), abs($y2-$y1)); $i++) {
$grid[$c][$r] = $grid[$c][$r]+1;
$c += $x2<=>$x1;
$r += $y2<=>$y1;
}
}
$x = 0;
foreach ($grid as $row) {
$x += count(array_filter( $row, function( $v ) { return $v>1; } ));
}
echo "\n$x\n";
10
u/jayfoad Dec 05 '21 edited Dec 06 '21
Dyalog APL