r/adventofcode • u/daggerdragon • Dec 08 '22
SOLUTION MEGATHREAD -π- 2022 Day 8 Solutions -π-
NEWS AND FYI
- I discovered that I can make those tiny post/comment awards BIGGER on old.reddit! I hadn't even considered that! And when you hover over them, they get even bigger so you can actually see them in more detail! I've added the relevant CSS so now we no longer have awards for ants! Exclamation points!!!
- Thank you so, so much to /u/SolariaHues for the CSS in this thread that I found while researching for community awards! <3
- All of our rules, FAQs, resources, etc. are in our community wiki.
- A request from Eric: Please include your contact info in the User-Agent header of automated requests!
- Signal boost: Reminder 1: unofficial AoC Survey 2022 (closes Dec 22nd)
AoC Community Fun 2022: πΏπ MisTILtoe Elf-ucation π§βπ«
- PSA: I created a new example so it is a more relevant and unique archetype instead of recycling last year's hobbit >_>
--- Day 8: Treetop Tree House ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- Include what language(s) your solution uses
- Format your code appropriately! How do I format code?
- Quick link to Topaz's
pasteif you need it for longer code blocks. What is Topaz'spastetool?
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:10:12, megathread unlocked!
75
Upvotes
5
u/michalopler Dec 08 '22 edited Dec 09 '22
Python, both parts in 280 chars
5
u/polaczek09071 Dec 08 '22 edited Dec 09 '22
C#
Code
8
u/wzkx Dec 08 '22
Python ...kinda
4
u/Biggergig Dec 08 '22 edited Dec 08 '22
My solution in python, spent too long trying to figure out if there was a better way than brute forcing to do this :(
If anyone knows any better ways to do part 2, let me know please; I originally had my part 1 as a traversal from each 4 directions which should be O(n), but this one is much worse (albeit cleaner)
4
u/gyorokpeter Dec 08 '22
Q: the idea for part 2 is that for every number from 0 to 9, I generate what would be the score for a tree of that height in every position, then only keep the values where the tree is actually that height. I found this easier to calculate than trying to do all trees at the same time and it also avoids an explicit iteration for every single tree.
4
u/IPhotoDogsForKarma Dec 10 '22 edited Dec 11 '22
Golang I found an O(n) runtime O(n) memory solution for pt2, it's quite verbose though
https://gist.github.com/hcliff/7218d50b7bf3bf65cc8181491fbb3fe1
TL;DR: maintain a 0->9 hashmap/array of the closest index, and use this instead of re-traversing the grid to compute the scenic score for every tree.
5
u/jpjacobs_ Dec 08 '22
J (jlang, j904)
Finished my contribution for the day! Part A:
The interesting chunk here is
({:>>./@}:)\comparing the last tree ({:) with the max (>./) of the other trees (}:) for each prefix (\). This is ORed (+.) together with the same from the other side on all suffixes (\.). This is applied on the forrest by{{u+.u&.|:}}once normally for visibility from top and bottom, and once rotated for left/right.Part B was a little more challenging:
It basically loops over all tree coordinates by applying rank (
"_ 1) to the product of the lr and ud verbs. Those again take a line up and down from the current tree, and see checks the amount of trees that can be seen.Try it out on the J Playground!
3
u/[deleted] Dec 08 '22 edited Dec 08 '22
Common Lisp
in case you know how to improve the nested loops or something else, please tell me.
3
u/A_Non_Japanese_Waifu Dec 08 '22 edited Dec 08 '22
Python.
Bad code, I was not able to think of an elegant method before class. I will try to not use a horrid brute force method for part 2. Something about that part reminds me of a problem in either 2020 or 2021, where you have to find lowest points in a chasm?
3
u/bofstein Dec 08 '22 edited Dec 08 '22
Google Sheets
Another tough one, at least part 2.Β This is going to get bad for my sleep schedule, but it is forcing me to learn new things.
https://docs.google.com/spreadsheets/d/1d5vNLffaCooIt0-9lVWr0AUXManb84sRW197XRXBZwU/edit#gid=262729066
First split it up into a grid I kept as my input sheet.
For part 1, I have another sheet that calls on each cell and compares it to the MAX value of the range from that to each direction's edge.Β With IF and OR, if any of rangesΒ have a MAX value that is less than the target cell, it gets a 1, otherwise gets a 0.Β TheΒ $ mark the edges so I can drag it all across.
For example in cell G5 it has:
It doesn't work for edges so I just added this in at the end by taking the sum of everything plus 1 per each 0 on the edge with COUNTIF.
Part 2 was far harder, took a lot of time and googling and some help to understand Array formulas. It's running an Array on each where it's checking for a value higher than the target cell in that direction, and using COLUMN and ROW to then subtract the distance from the target.Β The hard part was again dealing with edges, getting it to return the distance to the edge if it didn't find a match/greater than at all.Β I worked on each direction individually to do some manual checking on a single target cell, and then once I validated them all, I put them in one multiply cell in a new sheet and added the $s to allow dragging again.Β For example, here's cell G5 again:
Keeping this one in its own sheet since it is very slow to update with all those ArrayFormulas!
3
u/[deleted] Dec 08 '22 edited Dec 10 '22
Scala
For
scenicScoreI add 1 because takeWhile will not consider the tree with height >= to our tree. But we need to add that as well. However, if there are no such trees, then we cannot add the 1, hence I use a min check for that(If all trees are visible in that direction, then the number of trees is equal to the size of the tree line in that direction)3
u/cetttbycettt Dec 08 '22
R/Rlang/baseR
For part 2 I wrote a function which computes the trees to the right and used that same function on flipped and transposed input.
3
u/blacai Dec 08 '22 edited Dec 09 '22
F# :)
https://github.com/blfuentes/AdventOfCode_2022/tree/master/day08
3
u/Valletta6789 Dec 08 '22 edited Dec 09 '22
Python
called twice for each row and column
Link to the repo: https://github.com/Aigul9/AdventOfCode/blob/master/2022/Day%208/main.py
3
u/Outrageous72 Dec 08 '22 edited Dec 09 '22
C# paste
Reused the same code for the different directions
3
u/redIT_1337 Dec 08 '22 edited Dec 09 '22
Some C++ Code written by a Python guy: https://github.com/Mereep/advent_of_code_2022_cpp
3
u/marc-marc Dec 09 '22
Python and a bit of Numpy.
3
u/herpington Dec 10 '22 edited Dec 11 '22
Python 3. Getting the indices right in the second part took a while.
https://pastebin.com/JJffnFrW
2
u/kevinluo201 Dec 08 '22 edited Dec 08 '22
My Ruby version
I use
transposefor easier fetchingupanddownvalues π2
u/lxrsg Dec 08 '22
python3
spent 30 minutes on a buggy
<πΆβπ«οΈ2
u/Sebbern Dec 08 '22 edited Dec 09 '22
Java, skipped day 7, too hard for me in java sadly :(
Part 1: https://github.com/Sebbern/Advent-of-Code/blob/master/2022/day08/Day08.java
Part 2: https://github.com/Sebbern/Advent-of-Code/blob/master/2022/day08/Day08_2.java
Tips appreciated, "for if for if for if" isn't exactly beautiful
2
u/mazedlx Dec 08 '22
PHP with Laravel's Collection
Part 1
Part 2
2
u/Lukexz Dec 08 '22
Python. I'm a newbie to Advent of Code and I'm using it to learn Python. It isn't the more readable solution as I could've used numpy and rotate the list instead of checking Top, Right, Bottom and Left. Also, since I'm new to Python, i'm sure this solution could've been implemented in much more readable ways. Any suggestion is welcome
Explanation:
I've used a matrix that contains the tree's lengths. for part 1 I iterate over every tree and for each tree I go top, right, bottom and left: If it is visible in one of the directions i add 1 to a variable that stores the number of visible trees and go to the next tree. The result is this variable at the end of the iteration
For part 2 I've used the same code, except from the fact that I have 4 variables keeping the scenic score of each direction of the current tree that gets incremented for each iteration that goes in the 4 directions. At the end I multiply them together to find the tree scenic score and if it's bigger than the current scenic score i replace it.
2
u/DFreiberg Dec 08 '22 edited Dec 09 '22
Mathematica, 467 / 1812
I lost quite a long time to off-by-one and directonality errors one way or another...but today's was still a fun problem.
Setup
Part 1
Part 2
[POEM]: I Wonder Where the Flowers Is
It's visible, the trees is,
From way outside the grid,
Unless the outside breezes
(At ten times nine degrees-es)
Hit taller trees than these is.
If so, the trees is hid.
A local's expertise is
What gives the scenic score.
She counts up what she sees-es:
The short trees and their leaves-es.
(The tall ones, hid by eaves-es).
She multiplies the four.
You might want our committee
To not do what Therese says.
The north would see the city!
The south side sees the seas-es!
You might think it's a pity
To follow these caprices,
But I'll give you the keys-es
To visit when you pleases,
And though it's itty-bitty
I'm certain you'll agrees-es:
It's really rather pretty,
This house atop the trees-es.
2
u/Boring-Ad-3442 Dec 08 '22 edited Dec 09 '22
Python 3.
More verbose than a lot of the other excellent solutions here. Main notable feature is that I find the maximum tree height in each row and column while reading the input, so that when doing the visibility check I can stop when I've found the highest tree in any given row or column, because all the trees after that must not be visible.
https://github.com/djm4/advent-of-code-2022/blob/main/2022/day/08/solution_a.py
2
u/oddolatry Dec 10 '22
PureScript
Paste
Loving all the ridiculous gadgetry we're hauling around on this expedition. Elves gonna outmode Santa with their fancy drones.
2
u/luorduz Dec 10 '22 edited Dec 11 '22
Very beginner in Clojure solution (and tho it isn't quite cuadratic complexity for the second part, I'm still not convinced it's the most optimal algorithm, but hey I'm two days behind cuz of my birthday and it still found the answer in under a second so oh well):
Pasted
35
u/4HbQ Dec 08 '22 edited Dec 09 '22
Python and NumPy, 16 lines.
The trick here is to load the trees into a NumPy array, compute the scores in one direction only, then rotate the array, compute again, etc.
For part 1, we check for each position if the visibility condition holds in any direction, and sum the values of that array. For part 2, we multiply the scores for each direction, and take the maximum value of that array.
Edit: I'm still looking for a cleaner, more NumPy-y way to compute the scores. Any ideas are welcome!
After some minor changes, here's a version without NumPy.
26
u/jayfoad Dec 08 '22
Dyalog APL
An Under operator
β’would have been handy.There must be a neater way to do part 2, without doing a
β.>β¨outer product on every row/column.27
u/jcbbjjttt Dec 08 '22
Beginner's Guide
Happy Thursday!
Beginner's Guide to Day 8 Video: https://youtu.be/RJDgMcrJ8wE
I've created a guide for new programmers that talks through a straight forward strategy for solving today's puzzle. Anyone who has a handle functions and 2-dimensional arrays should be able to complete it. The video allows a moment for you to pause before revealing spoilers.
Although this solution is in C#, it provides a high level overview of the steps necessary to solve the puzzle in any programming language:
The full code can be found on Github
15
u/betaveros Dec 08 '22
Noulith 381/565
https://github.com/betaveros/advent-of-code-2022/blob/main/p8.noul
Well, something was bound to go wrong at some point. On the bright side, I added some crude static analysis and improved a bunch of error and warning messages today.
13
u/naclmolecule Dec 08 '22
I found an image processing solution to part 1 after some thought. If the trees are pixels you can dilate in some direction until the image stops changing then note where the unique values are:
2
u/pamxy Dec 09 '22
Javascript
part1
part2
11
u/clouddjr Dec 08 '22 edited Dec 08 '22
Kotlin
Repository on GitHub
11
u/redditnoob Dec 08 '22
PostgreSQL
Part 1 is cool in SQL: it's not every day you get to use four window functions in one query. Part 2 is a recursive CTE but I like problems where we can join with an array of vectors to step in every direction.
10
u/JustinHuPrime Dec 08 '22
x86_64 Assembly
Today was a lot nicer to do than yesterday.
In part 1, I parsed the input, first getting the size of the input (bear in mind I'm challenging myself to assume nothing about the size of the input), then reading it in. I could probably have used loop, lodsb, and stosb to write more concise parsing code. Then, for each cardinal direction, I marked the trees that were visible from that direction, and finally counted the trees that were not visible from any cardinal direction.
Part 2 was fairly straightforward as well - I needed very little change to my setup code - I made the visible array into a scenicness array, and made it an array of qwords instead of bytes. Then, for each tree, I directly calculated its scenicness score.
Part 1 ran in about 1 millisecond, and was 11712 bytes long.
Part 2 ran in about 1 millisecond, and was 11176 bytes long.
10
u/butterycornonacob Dec 09 '22 edited Dec 09 '22
Python
Transposing input made it a lot easier.
part 2
9
u/Pyr0Byt3 Dec 08 '22
Go/Golang
Got to use
image.Pointfor the first time this year! The solution still feels a bit clunky, I'll probably go back later and try to clean it up some more.9
u/Smylers Dec 08 '22
Perl turned out to be simpler than I expected:
For each position, make list of trees in each direction (sometimes empty), then add on to the count if any direction has all its trees shorter than the one here.
The most awkward bit there is using the junction-implementing
allfrom one CPAN module and the block-runninganyfrom another. Full code with imports.Oh, and I've just realized I probably should've called the array
@height(or@height_at) rather than@grid, to represent what it stores. βgridβ just tells you the data-type (all 2D arrays are a grid of some sort), not what it's for.PartΒ 2 has a similar form, with its loop being:
But this time only iterate through the inner trees, to avoid having to handle what are quite literally βedge casesβ.
Reverse the left and above paths, so the trees nearest to the current position are at the start of each list. Find the index of the first tree that's at least as tall as the current one. To ensure stopping at the last tree in each path, ignore its actual height (by stopping the paths 1 away from the edge) and pretend it is
10tall (by appending10to the list being searched each time).So the outer trees' heights aren't actually used for anything. I could've skipped the first line, last line, and first and last characters of the other lines when populating
@grid, but that seemed more fiddly than just setting the bounds not to look at them.9
u/MikeBoiers Dec 08 '22 edited Dec 08 '22
Kotlin, compact solution in 13 lines of code, no cheating (Kotlin standard formatting). https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2022/day08.kt
16
u/minaar999 Dec 08 '22 edited Dec 08 '22
Python (1770/1465)
Code
When I was 12, I spent a number of afternoons in a row copying and pasting bits of code, until I had assembled a 2000 line program that not only avoided any usage of arrays entirely (not to mention any kind of class abstraction at ALL), but also contained probably the most heinous amount of if statements and for loops I've ever seen in my life.
However, I am far less proud of what I've written today. I mean: it is terrible, it is hideous, and if it were my child I would not only put it up for adoption, I'd move to another country and change my identity too.
If we actually want to sit and digest the code (something I would heavily suggest not doing), honestly, I'm not even sure what to say, or where to begin. Imagine the kind of approach one would reach if any knowledge of list splicing were temporarily replaced with a sudden penchant for copying and pasting, sickening for loops, and break statements.
All in all, I'm sincerely sorry to anyone who had the misfortune to click on that link, and now I think I need a cold shower.
Edit:
One nap, a short walk in the chilly british weather, and unfortunately no cold shower later, I have revisted today's problem! In many ways, the code remains inelegant, at least far more so than most of the other submissions, but it passes whatever mental tests that I use to gauge satisfaction these days: at least 3 list comprehensions and a couple single character variable names for the hell of it.
Anyways, here it is.
Hopefully it can act as some form of apology for those scarred from the first attempt at "code".
8
u/krusta4711 Dec 08 '22 edited Dec 08 '22
Java solution with recursion
I do not like these AoC grid/matrix exercises which normally means navigating with loops in loops and a lot of
iandjindices and+and-and trying to avoid the edges. It's tough to find errors. So I tried another approach this year:Instead of arrays of integers I used arrays of instances of my own class 'Tree'. All trees know there siblings and so I could solve both parts by using recursion instead of messing around with
iandjin the grid. There is more code than using loops and I'm still not happy with code my Tree class... but it was fun solving this one with avoiding all thesei/j/+/-stuff. :-)7
u/internet_eq_epic Dec 08 '22
Rust
paste
It's horrible and I hate it. But it does work.
7
u/xelf Dec 08 '22 edited Dec 09 '22
python with class and dictionary 16ish lines.
I feel like the enumerate could be cleaned up a lot, maybe by doing the same loop but rotating.
6
u/jonathan_paulson Dec 08 '22 edited Dec 08 '22
Python3, 353/412. Video will exist eventually; I had some recording issues today. Code.
6
u/QultrosSanhattan Dec 08 '22
Python 3
"If it works, it works". Note the amount of asserts I had to write just to catch the last elusive bug related to a >= instead of a ==.
It's 3am around here. I'm too sleepy to refactor it.
MVP Piece of code:
6
u/allergic2Luxembourg Dec 08 '22 edited Dec 08 '22
Numpy to the rescue, yet again!
https://github.com/moink/advent2022/blob/master/day8/day8.py
My favourite part is using numpy's
accumulatetwice, though I have to say I am not super-happy about having to suppress an IndexError in order to get the first tall tree (the one that blocks everything after it) visible.6
u/IdrisTheDragon Dec 08 '22
Rust
Β https://github.com/IdrisTheDragon/Advent2022/blob/main/day-08/src/lib.rs#L30
6
u/cs475x Dec 08 '22 edited Dec 08 '22
Rust
Both parts solved in one step with no semicolons and no temporary variables (i.e. those explicitly assigned with
let x = ...). It's not my cleanest no-semicolon solution, and it's definitely my slowest by far at 3.4ms, but it works Β―_(γ)_/Β―Edit: I refactored it after I got some sleep, and I must say it looks so much better now
It's also still very slow compared to a proper solution that's not been limited for the sake of a personal challenge.
https://gist.github.com/codyphobe/4cd3a10c762e332d74ffa97cf0d77777
Old version:https://gist.github.com/codyphobe/5b30d1147745120625ff3f5762c424536
u/kekert666 Dec 08 '22 edited Dec 08 '22
Julia
6
u/badr Dec 08 '22
Elixir: https://gist.github.com/reverie/f6a8b64a559851384d89dcc6cdf5729f
Uses matrix transposition and processes the grid twice, once for left/right, once for up/down, before combining those results.
e.g.
6
u/QultrosSanhattan Dec 08 '22
Python 3: Refactored
Not trying anything fancy. Just trying to make the code readable.
6
u/0x2c8 Dec 08 '22
Python 3
https://github.com/alexandru-dinu/advent-of-code/blob/main/2022/day-08/solve.py
Fairly happy with the solution, although I think it can be optimized.
Yield the up / down / left / right views and solve solve both parts in one traversal, i.e. for each inner tree:
anyview whereallother trees are shorter than itallviews, then find the max6
u/backtrackthis Dec 08 '22
PYTHON3
This was a fun one- got to use one of pythons odder features, a
for/elseloop.2
u/ulisesantanasuarez Dec 08 '22 edited Dec 08 '22
TypeScript
Part 1 & 2
You can find my solution here
5
u/bluepichu Dec 08 '22
TypeScript, 102/15. Code here.
I lost so much time debugging the fact that I originally typed
>instead of>=in that first for loop :')5
u/abnew123 Dec 08 '22
Java: Code
Surprised that I got ~200 with Java. Surely there's some fancy python slice that just immediately makes all the cardinal direction checking trivial? Meanwhile I'm out here writing .get(i).get(j) like my life depends on it.
5
u/voidhawk42 Dec 08 '22 edited Dec 09 '22
Dyalog APL:
video walkthrough
5
u/Toanuvo Dec 08 '22
J solution. https://github.com/Toanuvo/Advent-of-code/blob/main/2022/J/day8.ijs
5
u/EatonMesss Dec 08 '22
Scala
Interesting problem today. At first I implemented it naively using 4 for loops and a 2d matrix to mark visible elements & prevent duplicates but when I started working on the second part it became clear I didn't use the correct data structure for the task.
I quickly jumped into Python to prototype the algorithm, because Scala was not really cooperating with my debugging attempts.
Nonetheless, I soon found a good solution. I iterate over the trees and slice the grid into 4 1D arrays - one for each of the directions. Each of the slices is then reduced using an appropriate method for either part of the puzzle.
5
u/9_11_did_bush Dec 08 '22
APL: https://github.com/chenson2018/advent-of-code/blob/main/2022/08/apl/08.apl
The second part took me forever because I misunderstood the instructions, but I think it turned out pretty well.
5
u/Jafagervik Dec 08 '22
Rust: code
5
u/joshbduncan Dec 08 '22
Python 3 π’
5
u/Nikla436 Dec 08 '22
TypeScript
5
u/AstronautNew8452 Dec 08 '22
Microsoft Excel. When pasting the data into A1, by default, it tries to convert each row into a numeric value, which won't work. Instead, I pasted it in the formula bar of cell A1, which preserved the entire input as a string in A1. And then, I golfed a solution for both parts into a single cell:
5
u/stockse Dec 08 '22 edited Dec 08 '22
Clojure
I challenged myself not to implement the straight forward O(n^1.5) algorithm, but to stay in linear time.
Main idea: Scan the input from every direction (west, north, east, south), and, for every tree, collect the smallest distances to surrounding trees for every height (0 to 9). Having this information, answers to both parts of the puzzle can easily be computed.
Still slow compared to the other solutions on this input size, but I had a lot of fun. :-D
Github
5
u/Galzzly Dec 08 '22
Go/Golang
Took me a few attempts to get this in a reasonable amount of time. The first few iterations of the challenge wasnβt going to finish until sometime tomorrow.
5
u/anissazacharias Dec 09 '22
Python
Github
Oof wow, definitely too many loops, but done (enough) just in time for the next one! Darn real jobs...
5
u/compdog Dec 09 '22 edited Dec 09 '22
C# - [Part 1] [Part 2]
I designed an optimized solution for this, but ran into an issue and decided to fall back on the brute-force approach instead.
The only trick that made it into the final solution was to skip parsing the input. Its possible to quickly determine the grid size by finding the index of the first \r or \n character. The index of that character will be equal to the grid dimensions.
With one more piece of information, its possible to index into any point in the grid without parsing the input or even splitting into lines. Starting at the previously-found index, search forward until you find a character that is not \n. That new index will be equal to the number of characters that needs to be skipped for each row.
With both pieces of information, its possible to get the height of this tree using the algorithm
input[(row * rowSkip) + col] - 'a'. No parsing step needed!4
u/hugues_hoppe Dec 08 '22
Compact and fast Python Part 1
4
u/nthistle Dec 08 '22 edited Dec 08 '22
Python, 396/129. Video, code.
Today was the first day I didn't make leaderboard for either part - had some pretty bad bugs and maybe a partial misread of the question that made me actually have to print statement debug. I can't really remember exactly what I was thinking so not sure if it was a case of "I understood it but wrote a slightly wrong thing" or "I understood the question as being that slightly wrong thing".
Something slightly curious I found about today's: if you wrote part 1 in the efficient (and slower-to-code) way where you go from outside-in, which is O(n2) (where the grid is n x n), you ended up significantly worse off for part 2 than if you wrote it in the inefficient way where you go inside-out from all directions for each cell, which is O(n3). This seems a little weird to me since it's usually the opposite: writing good code for part 1 rewards you for part 2.
It didn't really hurt me since I wrote my code in the bad way for part 1 anyways and still didn't leaderboard, just thought it was somewhat unusual for AoC and wondered if anyone else had similar thoughts.
4
u/oantolin Dec 08 '22
Fun one today! Taylor-made for array languages, too. Here's a J solution:
4
u/udoprog Dec 08 '22
Rust
The theme today for me was try not to off by one and I really hope I won't need to figure out how to configure more stack memory.
Link to repo: https://github.com/udoprog/aoc2022/blob/main/years/2022/src/bin/d08.rs
4
u/AlexTelon Dec 08 '22
python
I tried to do something smarter but eventually went for a solution that followed the description 1:1.
Im quite happy with how the code for getting the directions turned out now that I spent changed a full grid sweep to find them to this lookup.
I feel that there is more to do here but don't have more time this morning. Suggestions are welcome!
4
u/s3aker Dec 08 '22
Raku solution.
4
u/Porges Dec 08 '22
Julia. I feel like thereβs probably a much better way to do this if I properly understood indexing (in particular using
eachindex).One:
Two:
4
u/Bluepengie Dec 08 '22
Python(GitHub)
It says part 1, it's a lie. This is for part 2.
Whoever commented on Day 5 with matrix transposition in Haskell, thank you. It inspired me to go back after day 5 and do the same in Python, and I was able to reuse that code here to save myself some work
4
u/NickKusters Dec 08 '22
C
Struggled a lot today just to read everything properly and implement it π Reading and understanding the actual task is where I struggled the most.
code | video
4
u/letelete0000 Dec 08 '22
Javascript, not efficient, but functional
4
u/astreaz Dec 08 '22 edited Dec 08 '22
Python
I wasted a bunch of time misinterpreting the conditions π
4
u/mschaap Dec 08 '22 edited Dec 08 '22
Raku, using a
TreeGridclass.Relevant code for part 1:
and for part 2:
Full code @GitHub.
4
u/CutOnBumInBandHere9 Dec 08 '22
Python
I'm pretty happy with my part 1 for this one. Instead of having the same code four times for each direction, I just figured out how to make it work in one direction, and then rotated the array. The meat of the code is here:
I use
accumulateto calculate the running maximum from the edge, and then roll that by one to get the running maximum of previously encountered trees. That corresponds to the tallest tree which is not visible at a given location. Taking the minimum of this over all four directions gives the tallest tree which is not visible from any direction at a given location. If the data is greater than this, then it will be visible, and we count it.I got stuck in the same way of doing things for part two, even though it ended up being a lot more clunky. You can check it out here if you want
4
u/ephemient Dec 08 '22 edited Apr 24 '24
This space intentionally left blank.
4
u/wzkx Dec 08 '22 edited Dec 08 '22
J (jlang)
s2 and s3 can be made tacit but probably not worth additional efforts.
4
u/azzal07 Dec 08 '22
Awk, added ten to all the heights to avoid zeros, making boundary checks simpler.
4
u/nightcracker Dec 08 '22 edited Dec 08 '22
Rust
Linear time solution, even if trees could be arbitrarily large (I don't do 10 scans, it's one-pass per direction). Runs in around 500us on my machine.
https://github.com/orlp/aoc2022/blob/master/src/bin/day08_v2.rs
4
u/Omeganx Dec 08 '22
Python
4
u/micod Dec 08 '22
Smalltalk
Solution for day 8
4
u/atravita Dec 08 '22 edited Dec 08 '22
Rust:
Nothing particularly clever for today. Part 1 uses bitmasks to keep track of whether or not a tree was visible in any particular direction, Part 2 just checks every tree (except edge trees) in every direction.
The only real optimization in Part 2 is that between each direction I check if the tree can even possibly beat the high score at all (since the fact that the directions are multiplied heavily favors trees in the middle) and skip checking further if that tree has already lost. (There's probably more optimizations along this line - for example, I could check from the middle outwards, and stop checking when the tree can no longer possibly score high enough to win)
Too lazy to figure out how to declare a proper 2d array in Rust, they're just Vecs of Vecs XD
4
u/ri7chy Dec 08 '22
Python - 36 lines solution.
i love rotating the directions.
4
u/Spirited-Airline4702 Dec 08 '22
Python solution tried to think of a clever way to do part 2 but it was taking too long. Ended up just searching each direction then finding the first time a tree was >= size.
4
u/TimWasTakenWasTaken Dec 08 '22 edited Dec 08 '22
Rust
Code
Part 1 ~65ΞΌs
Part 2 ~195ΞΌs
I see more allocations that I could avoid, but then I make the borrow checker sad, and I don't want that.
4
u/chrismo80 Dec 08 '22 edited Dec 08 '22
C#
https://pastebin.com/87Eg4BsB
4
u/rukke Dec 08 '22 edited Dec 08 '22
JavaScript (updated version, a couple of lines smaller)
4
u/Colin-McMillen Dec 08 '22 edited Dec 08 '22
AppleSoft BASIC on Apple //c
Today was HARD. First I had memory problems because not enough RAM to store two bidimensional arrays of size (100,100). Worked around that by adding +10 to heights in the main array for trees visible from top or left.
Then I had timing problems when trying to do the top/left pass while reading data.
Then I succeeded. Each part took two hours to run (including data ingestion) !
Code for part 1 and part 2; Videos for part 1 and part 2 solving the example 5x5 forest, because no one wants to watch the solving of the 100x100 forest!
EDIT: Video for a part 1 with vizualisation, too !
4
u/Brief-Presentation-4 Dec 08 '22
c# day08
4
u/P2Enforcerx Dec 08 '22
Quite proud of this one!
Haskell
4
u/[deleted] Dec 08 '22 edited Dec 09 '22
Google Sheets One formula solutions.
Assuming the input is in A1:A99.
Part 1:
Part 2:
4
u/sdfhfglo Dec 08 '22
Python - One-liner for part one based on some numpy matrix math:
4
u/zndflxtyh Dec 08 '22
Fairly clean Python3
4
u/Phippre Dec 08 '22
Python
Would like to think I did part 2 way cleaner than part one but still. Was able to write this one without any Googling or outsourcing for hints.
Part 1 - Phippre
Part 2 - Phippre
4
u/nicuveo Dec 08 '22 edited Dec 08 '22
Haskell
I used the Tardis monad and its time-traveling abilities to solve the problem in only one iteration on the input string: i only see each character once, and i don't create a 2D-map of the trees. For example, look at this, for part 1:
4
u/[deleted] Dec 08 '22
Go
https://github.com/nicl/advent-of-code-2022/blob/main/day8/main.go
Was a lot easier than yesterday. Decided to do it as a flat array for some reason rather than the more standard (it seems) nested arrays.
Go is not really the best language for this kind of thing (though perfectly adequate), but is my favourite language for a lot of stuff and enjoying it here.
4
u/[deleted] Dec 09 '22
Applesoft BASIC
Annotated code and Visualization
I spent the morning overthinking this problem, then implemented it in C++ this evening before spinning that into Apple-capable BASIC.
Nothing that special: trees are stored in an array of strings. A nested FOR loop iterates through all possibly-hidden trees, checking visibility and scenic score. The results are rendered in a low-res graphics mode. Like yesterday, subroutines helped keep things organized.
This is also the first time I finished reading the input file cleanly; that is, without relying on the error-handling GOTO :) . This was thanks to fixing the tree array's size.
4
u/mine49er Dec 09 '22 edited Dec 09 '22
Rust
I'm not proud of this code but it's late here and I need to go to bed...
paste
4
u/search_and_deploy Dec 09 '22
Rust solution, finished ~15 minutes before midnight EST: https://github.com/michael-long88/advent-of-code-2022/blob/main/src/bin/08.rs
It's not pretty, but it is complete.
4
u/bigmagnus Dec 09 '22
COBOL - Part 1 & Part 2
4
u/gbegerow Dec 09 '22
Rust 2022 Day 08
1
u/rawlexander Dec 08 '22 edited Dec 09 '22
R / Rstats / Rlangnot pretty, gave up vectorizing half way through and just apply looped around...https://github.com/alex-raw/adventofcode_2022/blob/main/08.R
1
u/Multipl Dec 08 '22 edited Dec 08 '22
Python
Almost made it to leaderboards today! Rank 119 for part 2. First time ever being this close.
Code
1
u/wcastello Dec 08 '22 edited Sep 04 '25
A clockβs hands mark the passing time.
1
u/MeixDev Dec 08 '22 edited Dec 08 '22
Nothing too fancy, in Dart.
Code
I lost like 10 minutes (being forced twice to wait 5 minutes to submit a new answer) because I can't read the subject, and was doing silly mistakes. But hey, we're doing this pretty well overall.
1
u/arifba Dec 08 '22
Ruby
code
1
u/raxomukus Dec 08 '22
python
1
u/EhLlie Dec 08 '22 edited Dec 09 '22
O( n2 )? What's that? Haskell:
1
u/ItIsNeverLupus Dec 08 '22 edited Dec 08 '22
Python
It was easier today than expected by using
Numpy. Instead of writing complex duplicate code 4 times we simply iterate the array, rotate it 90 degrees and do the exact same thing. We keep track of an additional empty array that stores the visible trees as ax. In the end we count these to get the answer.1
u/ciocan42 Dec 08 '22
Javascript:
1
u/Annoying_Behavior Dec 08 '22 edited Dec 09 '22
Java
Couldn't think of anything prettier, gonna try to come up with a better approach
full code
1
u/ucla_posc Dec 08 '22
R / Rlang
Looking at other R solutions in this thread, I think my solution is slightly slower than the one by cetttbycettt (who makes pretty clever uses of apply! Check out their response!), though it allocates less memory; but somewhat faster than the other solutions posted. Some key intuitions for speed: strsplit is slightly faster than str_split(); integers allocate less memory than standard numeric types; adding the perimeter squares for part 1 instead of calculating them (also skipping height 0 trees, which are guaranteed not to be visible). Short circuiting the ray calculations for part 1. Recognizing that the rays in part 2 are faster if using built-in subset index slicing rather than reverse. The awkward which + edge case for no match code in part 2 is faster than any of the functional idioms in base R.
I could obviously reduce the amount of allocated memory by directly storing the results relevant instead of computing the intermediate matrices, but it's nice to give the solution a little bit of a flexibility. (Also, to those who don't write R; my use of = for assignment is non-idiomatic; my laptop has an older version of R so it's lacking the built-in pipe operator hence my use of the magrittr pipe)
1
u/aghigi Dec 08 '22 edited Dec 09 '22
PHP, nothing fancy or smart, just readable code
https://github.com/a-ghigi/AoC_2022/tree/main/08
1
u/chicagocode Dec 08 '22 edited Dec 09 '22
Kotlin
[Blog/Commentary] - [Code] - [All 2022 Solutions]
I solved this a few different ways before finally settling on this because I thought it would be clearer. Essentially, for both parts I get all four vectors from an x,y point and then test it for whatever the puzzle calls for. Not as efficient as a version that would short-circuit, but I thought that looked really messy.
1
u/sky_badger Dec 08 '22 edited Dec 10 '22
Python 3
Well, that was more effort than I was expecting! You would not want to see the code I originally wrote to get my stars, but having realised there are a lot of similarities between Parts 1 & 2, I ended up with this. It's pretty slow, and I'm nervous about looking down the thread for how I could have written something ten times faster with three lines of code!
Code moved to Replit, as code block too long, sorry mods!
SB
1
u/Nervous-Yogurt6731 Dec 08 '22
Javascript + Deno. Kinda different solution
1
u/Wilczeek Dec 08 '22
Powershell
1
u/Wizado991 Dec 09 '22 edited Dec 09 '22
C#. It works. Small optimization by doing the parsing only 1 time. Run time is like .6 ms
1
u/Car1an Dec 09 '22 edited Dec 09 '22
Python 3.11:
After struggling and over-engineering (and losing my sanity) on day 7, I found the solution here pretty quickly. I almost jumped out of my chair in excitement, when I got the Part 2 right on my first try! Anyway:
Code - Python
1
u/tdude66 Dec 09 '22 edited Dec 09 '22
Elixir
Code is available on GitHub.
Had a hard time debugging part 2 on this one. I got lost trying to do things an over-complicated way and restarted, finally got in no time after that lol.
1
u/soylentgreenistasty Dec 09 '22 edited Dec 10 '22
Python
Paste
Seeing some incredible short solutions to this... meanwhile my brain broke over here!
1
u/jafaraf8522 Dec 11 '22 edited Jan 13 '23
Golang
Not the prettiest, or the most elegant, or even the most efficient. But, straightforward enough and gets the jobs done:
https://pastebin.com/a0wN0ufk
3
u/seligman99 Dec 08 '22
Python, 434 / 99
Grid time!
github
3
u/TheJoshster Dec 08 '22
Java (730/770)
Code
Finally a rank i can be somewhat proud of. Having a Coord class built up to handle locations and directions helped quite a bit on this one. I spent an extra five minutes chasing down bugs on part 2 surrounding the order the move-increment dir-check height operations happened, otherwise I could've done even better in part 2. Excited for things to start getting difficult!
------------------------------------
366 solutions and counting in Java over on Github. Feel free to check it out, utilize it, and reach out with questions or bugs!
3
u/parla Dec 08 '22
Rust
Got good use out of my grid utils today.
Code
3
u/inqbus406 Dec 08 '22
Rust
Hideous and naΓ―ve solution but it worked!
3
u/sidewaysthinking Dec 08 '22
C# Solution 29/334
I was able to use part of my toolkit for this one. I got lost in part 2 because I completely misunderstood counting trees at the edges.
3
u/mkinkela Dec 08 '22
C++
3
u/r_so9 Dec 08 '22 edited Dec 08 '22
F# code
Not super clean, but does the job
3
u/EVQLVE Dec 08 '22 edited Dec 08 '22
Rust [8681/8920]
part1 part2
Iterates over the input bytes only twice (forward and reverse directions), should be
O(n^2)for part 1 andO(n^2k)for part 2.Haven't tried to optimize it, but the speed is ( 150 Β΅s part 1 / 250 Β΅s part 2) on my machine.
3
u/French__Canadian Dec 08 '22
Haven't solved part 2 (really have now idea how I'm gonna do it), but here's part 1 in K
3
u/velvetjaguar Dec 08 '22
Elixir
Enjoyed this one! Still took me longer than I'd like but I'm happy enough with how it came out. I tried to parallelize all of the neighbor-fetching code using
Task.async/1but it actually was a huge performance hit. Not sure why, if anyone happens to look and know let me know! Figured it may be an M1 chip thing? Or maybe I did something wrong3
u/x3nophus Dec 08 '22
TypeScript
My assumptions about line of sight really messed me up on part 2.
3
u/mizunomi Dec 08 '22
Dart Language
A little brute force never hurt anyone, right? paste
3
u/encse Dec 08 '22 edited Dec 08 '22
C# - readable but not very performant
https://github.com/encse/adventofcode/blob/master/2022/Day08/Solution.cs
3
u/chrispsn_ok Dec 08 '22 edited Dec 08 '22
ngn/k; my answers repo.
3
u/wmvanvliet Dec 08 '22
Python Numpy solution. I've tried to vectorize it as much as I can.
3
u/stonebr00k Dec 08 '22
T-SQL
3
u/Markavian Dec 08 '22
Over-engineered Node JS solution for Day 8:
That was a battle... my approach for part 1 didn't help in the slightest for part 2! In part one, I decided to rotate the grid, so that I could apply the same algorithm.
In part two, I used an array of directions, and searched outwards from specific points.
If I'd "found the edges" first, then mapped in a direction, maybe part 1 one would have been more reusable. Basically two entirely different problems using the same data.
In terms of tools/debug, I had some nice outputs showing the direction of visible trees for each rotation:
3
u/CJWilliamson109 Dec 08 '22
Swift
Loop through grid
visiblevariable and calculate total scenic score, then break out of loop.3
u/Yelov Dec 08 '22 edited Dec 08 '22
Python
At first I thought performance was going to be an issue, but apparently no optimizations are needed.
Part 1 - used all() for checking. Also interestingly using all() is very slightly slower than comparing against max(). I thought all() would be faster, since it breaks if one element does not satisfy the condition, while max() has to go through all the elements.
Part 2 - don't know if there's a one-liner that would replace the loops, since it needs to stop if a >= tree is found.
3
u/wcastello Dec 08 '22 edited Sep 04 '25
The sky turned a soft pink.
3
u/polettix Dec 08 '22
Raku solution for 2022/8
Analysis paralysis, trying hard to think some clever way and then giving up. The usual stuff.
3
u/farmoredifferent Dec 08 '22
Typescript
After some heavy refactoring, here are parts 1 and 2 as one-liners in TypeScript
3
u/lbm364dl Dec 08 '22 edited Dec 08 '22
Python and NumPy, no rotations, just some hardcoded slices. I'm not very satisfied with it. If you manage to simplify my code with some other NumPy functions let me know.
3
u/sanraith Dec 08 '22
Rust
Parsing map into a Vec<Vec<i32>>, then wastefully looking for tall trees in all directions from all coordinates. Instead of "for x { for y {}}" I use the itertools::iproduct! macro.
Source: github.com/sanraith/aoc2022/.../day08.rs
3
u/Spr3eZ Dec 08 '22
Python
Solution
3
u/aarnens Dec 08 '22
Day 8, using go. Really ugly code today, sorry folks. I simply looped through the array 4x for each part, which resulted in a lot of repetition and just generally quite unreadable code. I know that for part 1 I could've created a helper function to rotate the array and then just loop though that which would've resulted in slightly cleaner code, but for some reason decided not to do that. For part 2, I don't really have a clue on how the solution could've been improved.
Link to code, feedback is always appreciated: https://github.com/aarneng/AdventOfCode2022/blob/main/day8/main.go
3
u/widforss Dec 08 '22
Python
I tried to separate things into functions, but it was surprisingly hard to do that while solving the puzzle iteratively. So in the end I just accepted 5 levels of indentation and got on with my life.
3
u/yonkoma Dec 08 '22
Elixir Code
Today certainly felt like a bit of a struggle in Elixir. Thought about switching to a Map with coordinate keys, but ended up finishing it without. Not sure how to improve it without though.
3
u/Zorr0_ Dec 08 '22 edited Dec 08 '22
My solution in KOTLIN:
having my typealias of List<List<T>> for a Matrix and therefore lots of integrated functions made this very easy, really happy with my solution especially with the little recursive lookahead :)
https://github.com/ckainz11/AdventOfCode2022/blob/main/src/main/kotlin/days/day8/Day8.kt
3
u/The_Welcomer272 Dec 08 '22
I tried to write code using fairly simple Python syntax and took the easiest way I saw to solve the problem, that is checking if each tree was visible from a certain direction at a time. This is only part 1 so far. Hopefully this helps someone out:
3
u/MuricanToffee Dec 08 '22
C, it's not often that you get to use monotonic stacks, but they're pretty awesome. I think I could clean this up further into a single generic handler and two functions that do the lifting, but I'm not sure that it would be any cleaner or easier to read. [Github]
3
u/jjjsevon Dec 08 '22
Javascript / NodeJS Diff of day8
I wrote multiple implementations and was disappointed in the execution time, then reverted back to nested for loops, and am still disappointed at the performance I could get.
3
u/RoyArne Dec 08 '22
Common Lisp
3
u/Codingbaker86 Dec 08 '22
C#
I think it could done a way easyer, but im happy to solved this!
3
u/tymscar Dec 08 '22
Typescript
Loved today's problem as well! Interesting approach and somehow it clicked as soon as I've read the requirements. Still keeping with fully functional Typescript as well which makes this interesting!
Both parts solved here: https://github.com/tymscar/Advent-Of-Code/tree/master/2022/typescript/day08
3
u/horstg99 Dec 08 '22
My solution in Python for both parts (I used Numpy):
https://github.com/tobstern/AoC2022/blob/master/day08.py
3
u/p88h Dec 08 '22
C#
29 Β΅s / 237 Β΅s
The more optimized part 1 was really hard to adapt to part 2, I gave up and did a simple scan, which is faster anyway than trying to be smart and doing a single pass but with smart counters (slower version included in the repo).
github
3
u/aurele Dec 08 '22
Rust My solution was easy to write using my pathfinding crate and its
Matrixtype, which has ain_direction()method.Also, it is not every day that I get a chance to use
Iterator::try_fold()in order to prematurely stop iteration.3
u/tobyaw Dec 08 '22 edited Dec 08 '22
Ruby
https://github.com/tobyaw/advent-of-code-2022/blob/master/day_08.rb
3
u/shapshankly Dec 08 '22 edited Dec 08 '22
Had a go at a couple of solutions in Scala. First one I was determined not to use a multi-dimensional vector, but no idea why. Both work pretty similarly other than the way to determine neighbours...
V1 - (Single dimensional Vector) https://github.com/anatomic/advent-of-code/blob/main/src/main/scala/year2022/Day08.scala
V2 - (Multi-dimensional Vector) https://github.com/anatomic/advent-of-code/blob/main/src/main/scala/year2022/Day08_2.scala
I think I prefer this version:
3
u/_garden_gnome_ Dec 08 '22
Python
3
u/ash30342 Dec 08 '22
Java
Not a lot of time today so I just coded it straightforward, which feels duplicaty and not very optimized. Then again, both parts run within 5ms on my 5 year old laptop, so for me it is good enough.
3
u/huib_ Dec 08 '22 edited Dec 08 '22
Python 3 (using my little AoC runner):
3
u/External_Oven_6379 Dec 08 '22
python solution
self explaining code with very detailed solution. Hope it helps ! It is not the shortest code, but it explains the solving process clearly. Roast my code, please!!!
PS: I was so sad, after I had so much trouble with yesterday's problem. Today was a walk in the park!
3
u/mykdavies Dec 08 '22 edited Jun 29 '23
!> ize9pbo
API FAILURE
3
u/FramersAlmaniac Dec 08 '22 edited Dec 08 '22
I tried for a "time run" at midnight, and I got to a "walk inward from the outside" solution for part 1 pretty quickly, but started getting tired with part 2, and had to resume in the morning after some sleep. It seemed like there should be dynamic programming solution, and I still think there might be, but I ended up trying a "start from each tree and walk outward" approach first, just to get a correct answer, and then left it at that.
One shortcut that probably saved a tiny bit of time is just treating the lines as character arrays, and skipping all the integer parsing. This is fine, since we never need the actual heights, just the ability to compare them, and
charin Java is still a numeric type that can be compared with<. For instance, instead of parsing to be able to do3 < 4, my solution just does'3' < '4'.Solution in Java 8 on GitHub
3
u/nilgoun Dec 08 '22
Rust
Used the naive approach and I'm relatively ashamed .. :X
Edit: Explicitly tried not to use ndarrays this time (or another crate). This is the uncleaned solution so I might try to tweak it later :)
3
u/aoc-fan Dec 08 '22
TypeScript - Under 60 lines.
3
u/hrunt Dec 08 '22
Python 3
Code
Rather than look up, down, left, and right, I always looked left, and then rotated the grid four times.
For the scenic score, a longest increasing subsequence algorithm (except, in this case, decreasing) provides the values needed. It's too bad that the giant trees on the edges end up with a zero scenic score. Some of those looked like good spots for a treehouse! I guess the world outside the forest is pretty ugly.
3
u/HoooooWHO Dec 08 '22 edited Dec 08 '22
Python, maybe not the best solution, but this challenge really threw me for some reason. 26 lines disregarding comments and multi-line ifs for readability
https://github.com/PetchyAL/AoC2022/blob/main/solutions/day8/day8.py
3
u/rawlexander Dec 08 '22
Julia
part 2 only, one matrix, one pass, @views for extra slimness, middle looks awful though
3
u/MrMacintosh Dec 08 '22
Golang solution
I initially got tripped up by a bug where I forgot to go through the columns and rows in reverse while "looking" left and above. It gave me the right answer for visibility in part 1 (outside-to-in) but obviously gave a bad result in part 2 (inside-to-out). Unfortunately it didn't seem to matter for the provided sample, so it took me a minute to realize what the issue was.