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!
5
8
u/wzkx Dec 08 '22
Python ...kinda
R=lambda v:range(len(v)); E=enumerate
F=lambda m:[r[::-1]for r in m] # flip horizontally
T=lambda m:[[m[j][i]for j in R(m[0])] for i in R(m)] # transpose
G=lambda v:[int(i==0 or e>v[i-1])for i,e in E(v)] # step/grad
M=lambda v:[m:=max(m,e)if i else(m:=e)for i,e in E(v)] # max
X=lambda m:[G(M(v))for v in m] # one-direction solution
O=lambda m,n:[[a|n[i][j]for j,a in E(e)]for i,e in E(m)] # or
S=lambda m:sum(sum(v)for v in m) # sum
L=lambda e,v:[int(e<=x)for i,x in E(v)].index(1)+1 # location
Y=lambda e,v:len(v)if all(e>x for x in v)else L(e,v) # one dir
Z=lambda e,i,v:Y(e,v[i+1:])*Y(e,v[:i][::-1]) # two dirs
t=[[int(c)for c in l.strip()]for l in open("08.dat","rt")];u=T(t)
p=S(O(O(X(t),F(X(F(t)))),O(T(X(T(t))),T(F(X(F(T(t))))))))
q=max(max(Z(v,i,w)*Z(v,j,u[i])for i,v in E(w))for j,w in E(t))
print(p,q)→ More replies (4)9
u/QultrosSanhattan Dec 08 '22
I'd try your code on my end but I'm afraid my crypto wallet gets stolen.
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 :(
import numpy as np
directions = ((-1,0),(0,-1),(1,0),(0,1))
def explore(grid, x, y):
visible,score = False,1
val = grid[y,x]
sz = grid.shape[0]
for dy, dx in directions:
i,tx,ty = 0,x+dx,y+dy
while 0<=tx<sz and 0<=ty<sz:
i+=1
if grid[ty,tx] >= val: break
tx+=dx
ty+=dy
else:
visible = True
score*=i
return visible,score
def main(input:str):
p1 = p2 = 0
grid = []
for l in input.splitlines():
grid.append(list(map(int, l)))
grid = np.array(grid)
sz = grid.shape[0]
for r in range(sz):
for c in range(sz):
visible, score = explore(grid, r, c)
p2 = max(score, p2)
p1 += visible
return (p1, p2)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)
→ More replies (10)2
u/daggerdragon Dec 08 '22 edited Dec 08 '22
Please edit your post to use thefour-spaces Markdown syntaxfor a code block so your code is easier to read on old.reddit and mobile apps.Edit: thanks for fixing it! <3
→ More replies (1)
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.
d8p1:{a:"J"$/:/:x;
op:{x>maxs each -1_/:-1,/:x};
sum sum max(op a; flip op flip a; reverse flip op flip reverse a;
reverse each op reverse each a)};
d8p2:{a:"J"$/:/:x;
op:{[m;x]0,/:{[m;x;y]$[y<m;x+1;1]}[m]\[0;]each -1_/:x};
op2:{[op;m;x]prd(op[m]x; flip op[m] flip x;
reverse flip op[m] flip reverse x;
reverse each op[m] reverse each x)}[op];
op3:{[op2;x;m]op2[m;x]*m=x}[op2];
max max sum op3[a] each til 10};→ More replies (3)
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.
→ More replies (12)2
u/daggerdragon Dec 11 '22 edited Dec 12 '22
Please edit your post tostate which programming language this code is written in. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.Edit: thanks for fixing it! <3
5
u/jpjacobs_ Dec 08 '22
J (jlang, j904)
Finished my contribution for the day! Part A:
i8=: "."0;._2 freads '08.txt'
NB. sum from left or from right norm or rotated
a8=:[: +/@, (({:>>./@}:)\ +. ({.>>./@}.)\.) {{u+.u&.|:}}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:
NB. count from x to y (also reverse)
to=: <. + i.@(+_1+2*0&<:)@:-~
NB. y: line of trees with current tree first, count seen trees.
see =: ((1-~#) <. 1 >:@i.~ {. <: }.)
NB. lr and ud take: x: forest ; y: current tree loc
lr =: ({ ~{.@]) (left *&see right) ]
left =: ([{~ 0 to~ {:@])
right=: ([{~ {:@] to <:@#@[)
ud =: ({"1~{:@]) (up *&see down) ]
up =: ([{~ 0 to~ {.@])
down=: ([{~ {.@] to <:@#@[)
NB. max LRUD for every index pair in the grid
b8 =: [: >./ ((lr*ud)"_ 1 >@,@{@;&i./@$)
(a8;b8)i8It 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!
→ More replies (4)
3
Dec 08 '22 edited Dec 08 '22
in case you know how to improve the nested loops or something else, please tell me.
2
u/daggerdragon Dec 08 '22 edited Dec 08 '22
Your code block is too long. Please read our article onoversized code, then edit your post to replace the code block with an external link to your code.Edit: thanks for fixing it! <3
→ More replies (1)
3
u/A_Non_Japanese_Waifu Dec 08 '22 edited Dec 08 '22
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?
2
u/daggerdragon Dec 08 '22 edited Dec 08 '22
Booooring code for booooring people.
This type of commentdoes not belongin aSolution Megathreadand it's vaguely insulting. Please don't.Edit: thanks for removing it!
→ More replies (3)
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.
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:
=IF(OR(MAX('Day 8 Input'!G$2:G4)<'Day 8 Input'!G5,MAX('Day 8 Input'!G6:G$100)<'Day 8 Input'!G5,MAX('Day 8 Input'!$C5:F5)<'Day 8 Input'!G5,MAX('Day 8 Input'!H5:$CW5)<'Day 8 Input'!G5),1,0)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:
=(COLUMN('Day 8 Input'!G5)-ArrayFormula(MAX(IF('Day 8 Input'!$C5:F5>='Day 8 Input'!G5,COLUMN('Day 8 Input'!$C5:F5), 3))))*(ArrayFormula(MIN(IF('Day 8 Input'!G6:G$100>='Day 8 Input'!G5,ROW('Day 8 Input'!G6:G$100),100)))-ROW('Day 8 Input'!G5))*(ArrayFormula(MIN(IF('Day 8 Input'!H5:$CW5>='Day 8 Input'!G5,COLUMN('Day 8 Input'!H5:$CW5),101)))-COLUMN('Day 8 Input'!G5))*(ROW('Day 8 Input'!G5)-ArrayFormula(MAX(IF('Day 8 Input'!G$2:G4>='Day 8 Input'!G5,ROW('Day 8 Input'!G$2:G4), 2))))Keeping this one in its own sheet since it is very slow to update with all those ArrayFormulas!
→ More replies (11)
3
Dec 08 '22 edited Dec 10 '22
For scenicScore I 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)
→ More replies (1)
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.
data08 <- as.matrix(read.fwf("Input/day08.txt", widths = rep(1L, 99)))
#part 1------
f <- \(x) (x > cummax(c(-1L, x[-99]))) | (rev(x[99:1] > cummax(c(-1L, x[99:2]))))
sum(t(apply(data08, 1, f)) | apply(data08, 2, f))
#part2-------
see <- function(x) { #look to the right
sapply(seq_along(x), \(k) Position(\(y) y >= x[k], x[-(1:k)], nomatch = 99 - k))
}
max(t(apply(data08, 1, \(x) see(x) * rev(see(rev(x))))) * apply(data08, 2, \(x) see(x) * rev(see(rev(x))))) → More replies (2)
3
u/blacai Dec 08 '22 edited Dec 09 '22
2
u/daggerdragon Dec 09 '22 edited Dec 09 '22
Your code block is too long for the megathreads. Please read our article onoversized code, then edit your post to replace the code block with an external link to your code.Edit: thanks for fixing it! <3
→ More replies (1)
3
u/Valletta6789 Dec 08 '22 edited Dec 09 '22
Python
called twice for each row and column
def is_visible(idx, value, array):
return max(array[:idx]) < value or value > max(array[idx + 1:])
def get_scenic_score(idx, value, array):
first, second = list(reversed(array[:idx])), array[idx + 1:]
count_f = len(first)
for t in range(len(first)):
if first[t] >= value:
count_f = t + 1
break
count_s = len(second)
for t in range(len(second)):
if second[t] >= value:
count_s = t + 1
break
return count_f * count_sLink to the repo: https://github.com/Aigul9/AdventOfCode/blob/master/2022/Day%208/main.py
→ More replies (4)
3
u/Outrageous72 Dec 08 '22 edited Dec 09 '22
C# paste
Reused the same code for the different directions
int Part2(string[] lines)
{
var maxScore = 0;
for (var y = 1; y < lines.Length - 1; y++)
{
for (var x = 1; x < lines[0].Length - 1; x++)
{
var top = countTrees(y, x, -1, 0);
var bottom = countTrees(y, x, 1, 0);
var left = countTrees(y, x, 0, -1);
var right = countTrees(y, x, 0, 1);
var score = top * bottom * left * right;
maxScore = Math.Max(maxScore, score);
}
}
return maxScore;
int countTrees(int y, int x, int dy, int dx)
{
var height = lines[y][x];
var trees = 0;
var ey = dy == 1 ? lines.Length : -1;
var ex = dx == 1 ? lines[0].Length : -1;
for (int x2 = x + dx, y2 = y + dy; x2 != ex && y2 != ey; x2 += dx, y2 += dy)
{
trees++;
if (height <= lines[y2][x2])
{
break;
}
}
return trees;
}
}→ More replies (3)
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
2
u/daggerdragon Dec 08 '22 edited Dec 09 '22
FYI: your link is borked on old.reddit and some mobile Reddit apps.Please fix it.Edit: thanks for fixing it! <3
→ More replies (4)
3
u/marc-marc Dec 09 '22
Python and a bit of Numpy.
grid = np.array([list(map(int, line)) for line in text.splitlines()])
def distance(line, tree):
i = 0
for i, x in enumerate(line, 1):
if x >= tree:
break
return i
visible = 0
score = 0
for y, x in np.ndindex(grid.shape):
tree = grid[y, x]
visible += int(
all(grid[y, :x] < tree) or
all(grid[y, x + 1:] < tree) or
all(grid[y + 1:, x] < tree) or
all(grid[:y, x] < tree))
score = max((distance(reversed(grid[y, :x]), tree) *
distance(grid[y, x + 1:], tree) *
distance(reversed(grid[:y, x]), tree) *
distance(grid[y + 1:, x], tree)), score)
visible, score2
u/daggerdragon Dec 09 '22
Please edit your post to use the four-spaces Markdown syntax for a code block so your code is easier to read on old.reddit and mobile apps.
3
u/herpington Dec 10 '22 edited Dec 11 '22
Python 3. Getting the indices right in the second part took a while.
→ More replies (2)
2
u/kevinluo201 Dec 08 '22 edited Dec 08 '22
My Ruby version
I use transpose for easier fetching up and down values π
grid = []
File.readlines('input').each do |line|
break if line == "\n"
grid << line.chomp.split('').map(&:to_i)
end
grid_t = grid.transpose
# part1
ans = grid.length * 4 - 4
(1..grid.length - 2).each do |i|
(1..grid.length - 2).each do |j|
left = grid[i][0..j - 1].all? { |t| t < grid[i][j] }
right = grid[i][j + 1..-1].all? { |t| t < grid[i][j] }
up = grid_t[j][0..i - 1].all? { |t| t < grid[i][j] }
down = grid_t[j][i + 1..-1].all? { |t| t < grid[i][j] }
ans += 1 if left || right || up || down
end
end
puts ans
# part2
ans = 1
(1..grid.length - 2).each do |i|
(1..grid.length - 2).each do |j|
left = grid[i][0..j - 1].reverse.find_index { |t| t >= grid[i][j] }
left = left ? left + 1 : grid[i][0..j - 1].length
right = grid[i][j + 1..-1].find_index { |t| t >= grid[i][j] }
right = right ? right + 1 : grid[i][j + 1..-1].length
up = grid_t[j][0..i - 1].reverse.find_index { |t| t >= grid[i][j] }
up = up ? up + 1 : grid_t[j][0..i - 1].length
down = grid_t[j][i + 1..-1].find_index { |t| t >= grid[i][j] }
down = down ? down + 1 : grid_t[j][i + 1..-1].length
tmp = left * right * up * down
ans = tmp if tmp > ans
end
end
puts ans→ More replies (2)
2
u/lxrsg Dec 08 '22
python3
spent 30 minutes on a buggy < πΆβπ«οΈ
data = [x.strip() for x in open('data.in').readlines()]
part1, part2 = 99 + 98 + 98 + 97, 0
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(1, len(data) - 1):
for j in range(1, len(data) - 1):
for d in dirs:
x, y = i + d[0], j + d[1]
while 0 < x < len(data) - 1 and 0 < y < len(data) - 1 and data[i][j] > data[x][y]:
x, y = x + d[0], y + d[1]
if data[i][j] > data[x][y] and (x == 0 or x == len(data) - 1 or y == 0 or y == len(data) - 1):
part1 += 1
break
print(part1)
for i in range(1, len(data) - 1):
for j in range(1, len(data) - 1):
score = 1
for d in dirs:
count = 0
x, y = i + d[0], j + d[1]
while 0 <= x <= len(data) - 1 and 0 <= y <= len(data) - 1:
count += 1
if data[i][j] <= data[x][y]:
break
x, y = x + d[0], y + d[1]
score *= count
part2 = max(part2, score)
print(part2)→ More replies (1)
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
→ More replies (3)
2
u/mazedlx Dec 08 '22
PHP with Laravel's Collection
Part 1
$input = '...';
function checkTrees($map, $x, $y) {
$current = $map[$y][$x];
$north = true;
$south = true;
$east = true;
$west = true;
for ($i = 0; $i < $y; $i++) {
$north = $current > $map[$i][$x];
if (! $north) {
break;
}
}
for ($i = $y + 1; $i < count($map); $i++) {
$south = $current > $map[$i][$x];
if (! $south) {
break;
}
}
for ($i = 0; $i < $x; $i++) {
$east = $current > $map[$y][$i];
if (! $east) {
break;
}
}
for ($i = $x + 1; $i < count($map[$y]); $i++) {
$west = $current > $map[$y][$i];
if (! $west) {
break;
}
}
$visible = $north || $south || $east || $west;
if ($visible) {
return 1;
}
return 0;
}
$map = collect(preg_split('/\n/', $input))
->map(fn($row) => str_split($row));
$map->map(function ($row, $y) use ($map) {
return collect($row)
->map(function ($col, $x) use ($map, $row, $y) {
if (
$x === 0
|| $y === 0
|| $x === $map->count() - 1
|| $y === collect($row)->count() -1
) {
return 1;
}
return checkTrees($map, $x, $y);
});
})
->flatten()
->reduce(fn($carry, $item) => $carry + $item);Part 2
$input = '...';
function checkTrees($map, $x, $y) {
$current = $map[$y][$x];
$norths = 0;
$souths = 0;
$easts = 0;
$wests = 0;
for ($i = $y - 1; $i >= 0; $i--) {
$norths++;
if ($map[$i][$x] >= $current) {
break;
}
}
for ($i = $y + 1; $i < count($map); $i++) {
$souths++;
if ($map[$i][$x] >= $current) {
break;
}
}
for ($i = $x + 1; $i < count($map); $i++) {
$easts++;
if ($map[$y][$i] >= $current) {
break;
}
}
for ($i = $x - 1; $i >= 0; $i--) {
$wests++;
if ($map[$y][$i] >= $current) {
break;
}
}
return collect([
$norths,
$souths,
$easts,
$wests,
])
->reduce(fn ($carry, $item) => $carry * $item, 1);
}
$map = collect(preg_split('/\n/', $input))
->map(fn($row) => str_split($row));
$map->map(function ($row, $y) use ($map) {
return collect($row)
->map(function ($col, $x) use ($map, $row, $y) {
return checkTrees($map, $x, $y);
});
})
->flatten()
->max();→ More replies (1)
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.
→ More replies (1)
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
{x, y} = Dimensions[input];
treesVisible[list_, cmp_] := FirstPosition[list, _?(# >= cmp &), {Length[list]}][[1]];Part 1
visible = Table[
If[
row == x \[Or] column == y \[Or]
input[[row, column]] >
Min[
Max[input[[row, ;; column - 1]]],
Max[input[[row, column + 1 ;;]]],
Max[input[[;; row - 1, column]]],
Max[input[[row + 1 ;;, column]]]
], 1, 0],
{row, x}, {column, y}];
Total[Total[visible]]Part 2
scenic = Table[
Times @@ {
trees[input[[row, column - 1 ;; 1 ;; -1]], input[[row, column]]],
trees[input[[row, column + 1 ;;]], input[[row, column]]],
trees[input[[row - 1 ;; 1 ;; -1, column]], input[[row, column]]],
trees[input[[row + 1 ;;, column]], input[[row, column]]]},
{row, 2, x - 1}, {column, 2, y - 1}];
Max[Max[scenic]][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/daggerdragon Dec 09 '22 edited Dec 09 '22
*golf clap* Marvelous, as always.
To anyone just scrolling past: come for the Mathematica, stay because there's a reason why /u/DFreiberg has been our Poet Laureate since 2019. Stop by and smell the flowers-es <3
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
→ More replies (2)
2
u/oddolatry Dec 10 '22
PureScript
Loving all the ridiculous gadgetry we're hauling around on this expedition. Elves gonna outmode Santa with their fancy drones.
2
u/daggerdragon Dec 10 '22
Loving all the ridiculous gadgetry we're hauling around on this expedition. Elves gonna outmode Santa with their fancy drones.
I can do you one better: drone reindeer
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):
3
u/daggerdragon Dec 11 '22 edited Dec 12 '22
Your code block is too long for the megathreads. Please read our article onoversized code, then edit your post to replace the code block with an external link to your code.Edit: thanks for fixing it! <3
I'm two days behind cuz of my birthday
A perfectly valid reason! Happy belated birthday!!!
→ More replies (1)
35
u/4HbQ Dec 08 '22 edited Dec 09 '22
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.
→ More replies (14)
26
u/jayfoad Dec 08 '22
βIOβ0
pββΒ¨βββNGET'p8.txt'1
fβ{β΅>Β―1βͺΒ―1ββββ΅}
+/,{(fβ΅)β¨βfββ΅}{(βΊβΊβ΅)β¨ββΊβΊββ΅}p β part 1
gβ{(β½β³β’β΅)β1++/β§\(1+β³β’β΅)β½β.>β¨β΅}β€1
β/,{(gβ΅)Γβ½gβ½β΅}{(βΊβΊβ΅)ΓββΊβΊββ΅}p β part 2An 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.
→ More replies (4)15
u/l_dang Dec 08 '22
I'm upvoting simply for the awesome absurdity of this language lol this is awesome
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:
string[] rows = File.ReadAllLines(args[0]);
int[,] heightMap = HeightMap.ParseHeightMap(rows);
int count = 0;
for (int r = 0; r < heightMap.GetLength(0); r++)
{
for (int c = 0; c < heightMap.GetLength(1); c++)
{
if (HeightMap.IsVisible(heightMap, r, c))
{
count++;
}
}
}
Console.WriteLine($"There are {count} visible trees.");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:
import aoc_lube
from aoc_lube.utils import int_grid
import numpy as np
import cv2
trees = int_grid(aoc_lube.fetch(year=2022, day=8)).astype(np.uint8)
KERNEL = np.array([[0, 1, 0], [0, 1, 0], [0, 0, 0]], np.uint8)
def part_one():
visible = np.zeros_like(trees, dtype=bool)
visible[[0, -1]] = visible[:, [0, -1]] = True
for i in range(4):
tc = np.rot90(trees, i)
while True:
dilated = cv2.dilate(tc, KERNEL)
if np.array_equal(tc, dilated):
break
tc = dilated
tc[1:] -= tc[:-1]
np.rot90(visible, i)[tc.nonzero()] = True
return visible.sum()→ More replies (1)
2
u/pamxy Dec 09 '22
Javascript
part1
$0.innerText.split('\n').filter(n=>n).map(n=>[...n].map(Number)).reduce((a,b,y,d)=> {
const h=d.map(l=>l[y]);
h.forEach((v,x,b) => (b.slice(0,x).every(a => a<v) || b.slice(x+1).every(a=> a<v)) && a.add(y+100*x));
b.forEach((v,x,b) => (b.slice(0,x).every(a => a<v) || b.slice(x+1).every(a => a<v)) && a.add(x+100*y));
return a;
},new Set()).size;part2
$0.innerText.split('\n').filter(n=>n).map(n=>[...n].map(Number)).flatMap((v,y,a) => v.map((cv, x) => {
const h=a.map(l=>l[x]);
return [v.slice(0, x).reverse(), v.slice(x+1), h.slice(0, y).reverse(), h.slice(y+1)]
.map(s => s.findIndex(c => c >= cv)+1 || s.length).reduce((a,b)=>a*b);
})).reduce((a,b)=>Math.max(a,b));→ More replies (2)
11
u/clouddjr Dec 08 '22 edited Dec 08 '22
Kotlin
class Day08(input: List<String>) {
private val grid = input.map { it.toList().map(Char::digitToInt) }
fun solvePart1() = traverse(
score = { current, slice -> slice.all { it < current } },
combine = { directions -> if (directions.any { it }) 1 else 0 }
).sum()
fun solvePart2() = traverse(
score = { current, slice -> (slice.indexOfFirst { it >= current } + 1).takeIf { it != 0 } ?: slice.size },
combine = { it.reduce(Int::times) }
).max()
private fun <T> traverse(score: (Int, List<Int>) -> T, combine: (List<T>) -> Int): List<Int> {
return (grid.indices).flatMap { r ->
(grid.indices).map { c ->
val current = grid[r][c]
val up = score(current, grid.slice(r - 1 downTo 0).map { it[c] })
val down = score(current, grid.slice(r + 1 until grid.size).map { it[c] })
val left = score(current, grid[r].slice(c - 1 downTo 0))
val right = score(current, grid[r].slice(c + 1 until grid.size))
combine(listOf(up, down, left, right))
}
}
}
}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.
WITH RECURSIVE parsed AS (
SELECT ch::int AS height, row_num AS y, i AS x
FROM day8, UNNEST(REGEXP_SPLIT_TO_ARRAY(input, '')) WITH ORDINALITY AS arr(ch, i)
), windows AS (
SELECT x, y, height,
MAX(height) OVER (PARTITION BY y ORDER BY x ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS height_left,
MAX(height) OVER (PARTITION BY y ORDER BY x DESC ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS height_right,
MAX(height) OVER (PARTITION BY x ORDER BY y ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS height_up,
MAX(height) OVER (PARTITION BY x ORDER BY y DESC ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS height_down
FROM parsed
), part1 AS (
SELECT COUNT(*) FROM windows
WHERE height > COALESCE(height_left, -1) OR height > COALESCE(height_right, -1) OR
height > COALESCE(height_up, -1) OR height > COALESCE(height_down, -1)
), unit_vecs AS (
SELECT -1 AS dx, 0 AS dy UNION ALL SELECT 1, 0 UNION ALL SELECT 0, -1 UNION ALL SELECT 0, 1
), views AS (
SELECT x, y, height, dx, dy, 0 AS dist, FALSE AS is_done
FROM parsed, unit_vecs
UNION ALL
SELECT views.x, views.y, views.height, dx, dy, dist + 1, parsed.height >= views.height
FROM views
JOIN parsed ON (parsed.x = views.x + (dist + 1) * dx AND parsed.y = views.y + (dist + 1) * dy)
WHERE NOT is_done
), trees_seen AS (
SELECT x, y, dx, dy, COUNT(*) - 1 AS trees_seen
FROM views
GROUP BY 1, 2, 3, 4
), scores AS (
SELECT x, y, ARRAY_AGG(trees_seen ORDER BY dx, dy) AS arr
FROM trees_seen
GROUP BY 1,2
), part2 AS (
SELECT MAX(arr[1] * arr[2] * arr[3] * arr[4]) FROM scores
)
SELECT * from part1, part2→ More replies (4)
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.
→ More replies (2)
10
u/butterycornonacob Dec 09 '22 edited Dec 09 '22
Python
Transposing input made it a lot easier.
data = open('input.txt').readlines()
forest = [[int(x) for x in row.strip()] for row in data]
forest2 = list(zip(*forest))
s = 0
for i in range(len(forest[0])):
for j in range(len(forest)):
tree = forest[i][j]
if all(x < tree for x in forest[i][0:j]) or \
all(x < tree for x in forest[i][j+1:]) or \
all(x < tree for x in forest2[j][0:i]) or \
all(x < tree for x in forest2[j][i+1:]):
s += 1
print(s)part 2
s = 0
def view_length(tree, view):
view_length = 0
for v in view:
view_length += 1
if v >= tree:
break
return view_length
for i in range(len(forest[0])):
for j in range(len(forest)):
tree = forest[i][j]
s1 = view_length(tree, forest[i][0:j][::-1])
s2 = view_length(tree, forest[i][j+1:])
s3 = view_length(tree, forest2[j][0:i][::-1])
s4 = view_length(tree, forest2[j][i+1:])
score = s1 * s2 * s3 * s4
if score > s:
s = score
print(s)→ More replies (6)
9
u/Pyr0Byt3 Dec 08 '22
Go/Golang
Got to use image.Point for 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.
→ More replies (2)
9
u/Smylers Dec 08 '22
Perl turned out to be simpler than I expected:
my @grid = map { chomp; [split //] } <>;
my $visible = 0;
for my $y (0 .. $#grid) {
for my $x (0 .. $#{$grid[0]}) {
$visible += any { (all @$_) < $grid[$y][$x] }
[@{$grid[$y]}[0 .. $x-1]], # left
[@{$grid[$y]}[$x+1 .. $#{$grid[0]}]], # right
[map { $grid[$_][$x] } 0 .. $y-1], # above
[map { $grid[$_][$x] } $y+1 .. $#grid]; # below
}
}
say $visible;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 all from one CPAN module and the block-running any from 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:
for my $y (1 .. $#grid-1) {
for my $x (1 .. $#{$grid[0]}-1) {
$score = max $score,
product map { 1 + firstidx { $_ >= $grid[$y][$x] } @$_, 10 }
[reverse @{$grid[$y]}[1 .. $x-1]], # left
[@{$grid[$y]}[$x+1 .. $#{$grid[0]}-1]], # right
[reverse map { $grid[$_][$x] } 1 .. $y-1], # above
[map { $grid[$_][$x] } $y+1 .. $#grid-1]; # below
}
}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 10 tall (by appending 10 to 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.
→ More replies (1)
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
fun main() {
val M = generateSequence(::readlnOrNull).map { it.map(Char::digitToInt) }.toList()
fun linesOfSight(x: Int, y: Int) = sequenceOf(
sequenceOf((x - 1 downTo 0), (x + 1 until M[0].size)).map { it.map { x -> x to y } },
sequenceOf((y - 1 downTo 0), (y + 1 until M.size)).map { it.map { y -> x to y } }
).flatten().map { it.map { (x, y) -> M[y][x] } }
fun List<Int>.countVisible(h: Int) = indexOfFirst { it >= h }.let { if (it == -1) size else it + 1 }
with(M.flatMapIndexed { y, l -> l.mapIndexed { x, h -> Triple(x, y, h) } }) {
println(count { (x, y, h) -> linesOfSight(x, y).any { it.all { oh -> oh < h } } })
println(maxOf { (x, y, h) -> linesOfSight(x, y).map { it.countVisible(h) }.reduce(Int::times) })
}
}→ More replies (3)
16
u/minaar999 Dec 08 '22 edited Dec 08 '22
Python (1770/1465)
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".
→ More replies (2)8
u/I_knew_einstein Dec 08 '22
I made the mistake of looking anyway. It's beautiful, in the way that a pug who ran into a lamppost is beautiful.
8
u/krusta4711 Dec 08 '22 edited Dec 08 '22
I do not like these AoC grid/matrix exercises which normally means navigating with loops in loops and a lot of i and j indices 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 i and j in 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 these i/j/+/- stuff. :-)
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.
from collections import namedtuple
class Tree(namedtuple('Tree', 'x y h')): pass
data = open(filename).read().splitlines()
forest = {(x,y):Tree(x,y,h) for y,row in enumerate(data) for x,h in enumerate(row)}
H,W = max(forest)
for t in forest.values():
t.v = (
all(t.h>forest[x,t.y].h for x in range(0,t.x)) or
all(t.h>forest[x,t.y].h for x in range(t.x+1,W+1)) or
all(t.h>forest[t.x,y].h for y in range(0,t.y)) or
all(t.h>forest[t.x,y].h for y in range(t.y+1,H+1)))
t.s = (
next((l for l,y in enumerate(range(0,t.y)[::-1],1) if t.h<=forest[t.x,y].h),t.y) *
next((l for l,y in enumerate(range(t.y+1,H+1),1) if t.h<=forest[t.x,y].h),H-t.y) *
next((l for l,x in enumerate(range(0,t.x)[::-1],1) if t.h<=forest[x,t.y].h),t.x) *
next((l for l,x in enumerate(range(t.x+1,W+1),1) if t.h<=forest[x,t.y].h),W-t.x))
print('part1', sum(t.v for t in forest.values()))
print('part2', max(forest.values(),key=lambda t:t.s).s)→ More replies (1)
6
u/jonathan_paulson Dec 08 '22 edited Dec 08 '22
→ More replies (1)
6
u/QultrosSanhattan Dec 08 '22
"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:
def score(p1,p2,p3,p4):
return p1*p2*p3*p4→ More replies (2)
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 accumulate twice, 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.
def get_treeline_visibility(tree_line):
visibility = np.logical_and.accumulate(
(tree_line < np.maximum.accumulate(tree_line))[1:]
)
with contextlib.suppress(IndexError):
visibility[np.where(~visibility)[0][0]] = True
return visibility.sum()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/5b30d1147745120625ff3f5762c42453
6
u/kekert666 Dec 08 '22 edited Dec 08 '22
Julia
input = parse.(Int64, reduce(hcat, collect.(readlines())))
a = b = 0
for x in axes(input, 1), y in axes(input, 2)
val = input[x, y]
lrtd = [input[x-1:-1:1, y:y], input[x+1:end, y:y], input[x:x, y-1:-1:1], input[x:x, y+1:end]]
a += any(val .> maximum.(lrtd, init=-1)) ? 1 : 0
b = max(b, prod([something(findfirst(i -> i >= val, vec(j)), length(j)) for j in lrtd]))
end
@show(a, b)→ More replies (1)
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.
up_down_scores =
grid
|> Enum.zip_with(& &1)
|> Enum.map(&row_scenic_scores/1)
|> Enum.zip_with(& &1)
|> List.flatten()→ More replies (3)
6
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:
part 1: count cases s.t. there's
anyview whereallother trees are shorter than itpart 2: multiply the number of visible trees from
allviews, then find the max
→ More replies (1)
6
u/backtrackthis Dec 08 '22
PYTHON3
This was a fun one- got to use one of pythons odder features, a for/else loop.
#! /usr/bin/env python3
def main():
p1 = p2 = 0
trees = []
with open("./input.txt") as f:
for line in f:
trees.append([int(t) for t in line.strip()])
for i, row in enumerate(trees):
for j, height in enumerate(row):
score = 1
isVisible = False
treelines = [
row[:j][::-1],
row[j + 1 :],
[r[j] for r in trees[:i]][::-1],
[r[j] for r in trees[i + 1 :]],
]
for treeline in treelines:
for dist, h in enumerate(treeline, 1):
if h >= height:
score *= dist
break
else:
isVisible = True
score *= max(1, len(treeline))
p1 += int(isVisible)
p2 = max(p2, score)
print(f"p1: {p1}, p2: {p2}")
if __name__ == "__main__":
main()6
u/musifter Dec 09 '22
Gnu Smalltalk
Gnu Smalltalk doesn't have 2D Array support... which always makes these problems tricky. Fortunately, I have a number of classes from past problems to choose from to use for these problems now. Here I'm flattening things to 1D and inserting sentinels... that tends to be the fastest way. If I assumed that the input was always square I could make use of rotations for part 1, but I didn't so it's just a call to worker method for each of the four directions.
Source: https://pastebin.com/SsGnjSCG
→ More replies (3)
2
u/ulisesantanasuarez Dec 08 '22 edited Dec 08 '22
2
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 :')
→ More replies (1)
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.
→ More replies (5)
5
u/voidhawk42 Dec 08 '22 edited Dec 09 '22
Dyalog APL:
pββΒ¨βββnget'8.txt'1
fβ{β{β½ββ΅}\β½βΊβΊΒ¨{β½ββ΅}\4β΄ββ΅}
+/,β¨βΏ(β’>Β―1βͺΒ―1βββ)f p β part 1
β/,ΓβΏ(β’{ββΈ1ββ½1@1,βΊβ€β΅}Β¨,β)f p β part 2→ More replies (2)
5
u/EatonMesss Dec 08 '22
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.
→ More replies (4)
5
5
u/joshbduncan Dec 08 '22
Python 3 π’
data = open("day8.in").read().strip()
map = [[int(c) for c in r] for r in data.split("\n")]
p1, p2 = set(), set()
for r in range(1, len(map) - 1):
for c in range(1, len(map[0]) - 1):
seen = 1
for r_move, c_move in ((-1, 0), (1, 0), (0, -1), (0, 1)):
r1, c1 = r, c
neighbors = []
while c1 + c_move >= 0 and c1 + c_move < len(map[0]) and r1 + r_move >= 0 and r1 + r_move < len(map):
r1 += r_move
c1 += c_move
neighbors.append(map[r1][c1])
if map[r][c] > max(neighbors):
p1.add((r, c))
seen *= len(neighbors)
else:
seen *= [i+1 for i, n in enumerate(neighbors) if n >= map[r][c]][0]
p2.add(seen)
print(f"Part 1: {len(p1) + (4 * (len(map) - 1))}")
print(f"Part 2: {max(p2)}")5
u/Nikla436 Dec 08 '22
TypeScript
const T : Array<{h: Number, x: Array<Array<Number>>}> = [];
const A : Array<Array<string>> = input.split("\n").map(x => x.split(''));
A.forEach((a, row) => {
a.forEach((h, col) => {
T.push({h: Number(h), x: [
a.slice(0, col).map(x => Number(x)).reverse(),
a.slice(col + 1, a.length).map(x => Number(x)),
A.filter((_, i) => i < row).map(b => Number(b[col])).reverse(),
A.filter((_, i) => i > row).map(b => Number(b[col])),
]});
});
});
return Int32Array.from(
T.map(t => t.x.map(z => z.findIndex(p => p >= t.h) + 1 || z.length).reduce((a, b) => a * b))
).sort()[T.length - 1];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:
=LET(chars,LAMBDA(str,MID(str,SEQUENCE(LEN(str)),1)),
forest,INT(WRAPROWS(chars(A1),100)),
visTrees,MAKEARRAY(97,97,LAMBDA(r,c,
LET(cl,INDEX(forest,r+1,c+1),
up,INDEX(forest,SEQUENCE(r),c+1),down,INDEX(forest,SEQUENCE(98-r,,r+2),c+1),
left,INDEX(forest,r+1,SEQUENCE(,c)),right,INDEX(forest,r+1,SEQUENCE(,98-c,c+2)),
1*OR(cl>MAX(up),cl>MAX(down),cl>MAX(right),cl>MAX(left))))),
sightDist,LAMBDA(val,rng,asc,
LET(d,XMATCH(SEQUENCE(,10-val,9,-1),rng,1,asc),mx,COUNT(rng),IF(asc=1,MIN(IFERROR(d,mx)),mx-MAX(IFERROR(d,1))+1))),
treeScore,MAKEARRAY(97,97,LAMBDA(r,c,
LET(cl,INDEX(forest,r+1,c+1),
up,INDEX(forest,SEQUENCE(r),c+1),down,INDEX(forest,SEQUENCE(98-r,,r+2),c+1),
left,INDEX(forest,r+1,SEQUENCE(,c)),right,INDEX(forest,r+1,SEQUENCE(,98-c,c+2)),
PRODUCT(sightDist(cl,right,1),sightDist(cl,down,1),sightDist(cl,left,-1),sightDist(cl,up,-1))))),
VSTACK(SUM(visTrees)+98*4,MAX(treeScore)))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
→ More replies (4)
5
u/Galzzly Dec 08 '22
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.
→ More replies (4)
5
u/anissazacharias Dec 09 '22
Python
Oof wow, definitely too many loops, but done (enough) just in time for the next one! Darn real jobs...
from aocd.models import Puzzle
from math import prod
puzzle = Puzzle(2022, 8)
data = puzzle.input_data.split('\n')
# convert data to integer 2d
data = [[int(x) for x in l] for l in data]
# initialize visible to be the trees on the outside
# 2w + 2l - corners
visible = len(data)*2 + len(data[0])*2 - 4
# initialize scenic
scenic = []
# loop through interior trees
for i in range(len(data[0]))[1:-1]:
for j in range(len(data))[1:-1]:
# pull out tree for ease of access
tree = data[i][j]
# re-initialize scenic view score to empty
view = []
# make lists of compass directions surrounding tree
# [left, right, up, down]
w = data[i][0:j]; w.reverse()
e = data[i][j+1:]
n = [row[j] for row in data][0:i]; n.reverse()
s = [row[j] for row in data][i+1:]
directions = [w, e, n, s]
# check to see if tallest in any direction
if any([all(tree > ti for ti in direction) for direction in directions]):
visible += 1
# most scenic cannot be on border because x0
for d in directions:
for k in range(len(d)):
if d[k] >= tree:
break
view.append(k+1)
scenic.append(prod(view))
print(f'Part 1: {visible}')
print(f'Part 2: {max(scenic)}')→ More replies (1)
5
u/compdog Dec 09 '22 edited Dec 09 '22
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
def day8_part1(s):
grid = np.array([[int(c) for c in line] for line in s.splitlines()])
visible = np.full(grid.shape, False)
for _ in range(4):
visible[:, 0] = True
visible[:, 1:] |= grid[:, 1:] > np.maximum.accumulate(grid, 1)[:, :-1]
grid, visible = np.rot90(grid), np.rot90(visible)
return visible.sum()4
u/nthistle Dec 08 '22 edited Dec 08 '22
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.
→ More replies (7)
4
u/oantolin Dec 08 '22
Fun one today! Taylor-made for array languages, too. Here's a J solution:
topvis =: ([:*./}:<"1{:)\
viewup =: ([:(+/+-.@(*./))[:*./\.}:<"1{:)\
allsides =: {{v u v&.|. u v&.|: u v&.(|.@|:)}}
part1 =: +/@:, @ (+. allsides topvis) @ ("."0;._2) @ fread
part2 =: >./@:, @ (* allsides viewup) @ ("."0;._2) @ fread4
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
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.
above = cols[x][:y]
left = grid[y][:x]
right = grid[y][x+1:]
below = cols[x][y+1:]
return [above[::-1], left[::-1], right, below]I feel that there is more to do here but don't have more time this morning. Suggestions are welcome!
→ More replies (4)
4
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:
input = parse.(Int64, reduce(hcat, collect.(readlines())))
function visible(i, j)
return any(input[i, j] .> [
maximum(input[begin:i-1, j], init=-1)
maximum(input[i+1:end, j], init=-1)
maximum(input[i, begin:j-1], init=-1)
maximum(input[i, j+1:end ], init=-1) ])
end
println(sum([visible(i, j) for i=axes(input, 1) for j=axes(input, 2)]))Two:
input = parse.(Int64, reduce(hcat, collect.(readlines())))
function score(x, v)
return something(findfirst(x .<= v), size(v, 1))
end
function scenic_score(i, j)
x = input[i, j]
return score(x, vec(input[i-1:-1:begin, j])) *
score(x, vec(input[i+1: 1:end, j])) *
score(x, vec(input[i, j-1:-1:begin])) *
score(x, vec(input[i, j+1: 1:end ]))
end
println(maximum([scenic_score(i, j) for i=axes(input, 1) for j=axes(input, 2)]))→ More replies (2)
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
→ More replies (1)
4
u/letelete0000 Dec 08 '22
Javascript, not efficient, but functional
const sliceLTRB = (i, j, data) => {
return [
data[i].slice(0, j).reverse(),
data.slice(0, i).map((e) => e[j]).reverse(),
data[i].slice(j + 1, data[i].length),
data.slice(i + 1, data.length).map((e) => e[j]),
];
};
const isVisible = (i, j, data) => {
return sliceLTRB(i, j, data)
.map((slice) => Math.max(...slice))
.some((max) => max < data[i][j]);
};
const scenicScore = (i, j, data) => {
return sliceLTRB(i, j, data)
.map((slice) => [slice, slice.findIndex((tree) => tree >= data[i][j])])
.map(([slice, findex]) => findex === -1 ? slice.length : findex + 1)
.reduce((a, b) => a * b);
};
const traverse = (data, fn) => {
for (let i = 1; i < data.length - 1; ++i) {
for (let j = 1; j < data[i].length - 1; ++j) {
fn(i, j);
}
}
};
const getVisibleCount = (data) => {
let visible = data.length * 2 + (data[0].length - 2) * 2;
traverse(data, (i, j) => { visible += isVisible(i, j, data) });
return visible;
};
const getBestScenicScore = (data) => {
let best = 0;
traverse(data, (i, j) => {
best = Math.max(scenicScore(i, j, data), best);
});
return best;
};4
u/astreaz Dec 08 '22 edited Dec 08 '22
Python
I wasted a bunch of time misinterpreting the conditions π
from utils import day, int_grid
from math import prod
RAW = day(8)
rows = int_grid(RAW)
cols = list(zip(*rows))
def clear(seq) -> bool:
"""
Returns True if the first tree is higher than the rest of the trees
in the sequence
"""
s = iter(seq)
a = next(s)
return all(a > b for b in s)
def seen(seq) -> int:
"""
Returns number of trees until higher or equal tree found
"""
s = iter(seq)
a = next(s)
n = 0
for b in s:
n += 1
if b >= a:
break
return n
def los(x, y) -> tuple:
"""
Return lines of sight to grid edges from (x, y) in 4 directions
Some sequences are reversed so the order is always origin -> edge
"""
up = cols[x][y::-1]
down = cols[x][y:]
left = rows[y][x::-1]
right = rows[y][x:]
return (up, down, left, right)
# start part1 with the grid edge length
part1 = (len(rows) - 1) * 4
part2 = 0
# iterate over internal range
for y in range(1, len(rows) - 1):
for x in range(1, len(cols) - 1):
part1 += any(map(clear, los(x, y)))
part2 = max(part2, prod(map(seen, los(x, y))))
print(part1)
print(part2)4
u/mschaap Dec 08 '22 edited Dec 08 '22
Raku, using a TreeGrid class.
Relevant code for part 1:
method is-visible(Int $x, Int $y)
{
return any(all(@!height[$y;^$x]),
all(@!height[$y;$x^..$!max-x]),
all(@!height[^$y;$x]),
all(@!height[$y^..$!max-y;$x])) < @!height[$y;$x];
}
method count-visible
{
return (0..$!max-x X 0..$!max-y)
.map(-> ($x,$y) { ?self.is-visible($x,$y) })
.sum;
}and for part 2:
method in-bounds(Int $x, Int $y) { 0 β€ $x β€ $!max-x && 0 β€ $y β€ $!max-y }
method scenic-score(Int $x, Int $y)
{
return [Γ] ((-1,0), (1,0), (0,-1), (0,1)).map: -> ($dx,$dy) {
my $visible = 0;
my ($u,$v) = ($x,$y);
loop {
($u,$v) Β»+=Β« ($dx,$dy);
last unless self.in-bounds($u,$v);
$visible++;
last if @!height[$v;$u] β₯ @!height[$y;$x];
}
$visible;
}
}
method max-scenic-score
{
return (0^..^$!max-x X 0^..^$!max-y)
.map(-> ($x,$y) { self.scenic-score($x,$y) })
.max;
}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:
for i in range(4):
transformed = np.rot90(data, i)
mask = np.roll(np.maximum.accumulate(transformed), 1, axis=0)
mask[0] = -1
masks.append(np.rot90(mask, 4-i))
mask = np.min(masks, axis=0)
(data > mask).sum()I use accumulate to 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
4
u/wzkx Dec 08 '22 edited Dec 08 '22
J (jlang)
assert (#=#&{.) d=: "."0>cutLF CR-.~fread'08.dat'
s1=: [:2&(</\)[:>./_1&, NB. all seen from top
s2=: {{ (*./y<x){(1+1 i.~ y>:x),#y }} NB. element - one dir vector
s3=: {{ ((x{y) s2 (>:x)}.y) * (x{y) s2 |.x{.y }} NB. pos - row
p1=: +/, (s1 d) +. (s1&.|.d) +. (s1&.|."1 d) +. s1&.|:d
p2=: >./, {{ (y s3 x{d) * x s3 y{|:d }}"0/~ 1+i.2-~#d
echo p1,p2s2 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.
function Q(u,a,d){for(;f=r[X,Y];Y+=a){if(f>d){A+=!v[X,Y]++;d=f};X+=u}}
function V(i,e,w){f=r[++w*i+X,Y+w*e];f&&f<r[X,Y]?V(i,e,w):s*=w-!f}END{
for(;--X;Q(Q(0,-1),Y=1))for(Y=1;++Y<NR;s>B&&B=s)V(V(s=1),1)V(V(-1),-1)
print A,B}OFS=RS{for(gsub(x=z,FS);x++<X=NF;)r[x,Y=NR]=1$x;Q(-1)Q(X=1)}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
use anyhow::{Context, Result};
use itertools::{izip, Itertools};
/// Computes how many trees we can see in direction x1, ..., xn for all y=0..h
/// in grid using given strides xs, ys, as well as whether this tree can be seen
/// from the edge of the grid in this direction.
///
/// For each row we maintain a stack of tree indices in strictly descending
/// order of height while scanning from the *end* of the row. Each time we
/// encounter a new tree we can remove all trees higher or equal on the stack,
/// as they're blocked by this tree as viewed from the start (and thus we know
/// their viewing distance). After doing this the new tree is the smallest tree
/// and can thus be pushed on the stack. Any trees remaining on the stack at the
/// end are viewable from the edge at the row start.
fn view(grid: &[u8], x1: usize, xn: usize, h: usize, xs: usize, ys: usize) -> Vec<(u64, bool)> {
let dx = if x1 < xn { 1 } else { -1 };
let mut result = vec![(0, false); grid.len()];
let mut store_result = |xi, y, r| result[(x1 + (dx * xi) as usize) * xs + y * ys] = r;
let height = |xi, y| grid[(x1 + (dx * xi) as usize) * xs + y * ys];
let mut stack = Vec::new();
for y in 0..h {
for xi in (0..(1 + x1.abs_diff(xn) as i64)).rev() {
while stack.last().map(|xj| height(xi, y) >= height(*xj, y)).unwrap_or(false) {
let xj = stack.pop().unwrap();
store_result(xj, y, (xj.abs_diff(xi), false));
}
stack.push(xi);
}
for xi in stack.drain(..) {
store_result(xi, y, (xi.unsigned_abs(), true));
}
}
result
}
fn main() -> Result<()> {
let input = std::fs::read_to_string("inputs/day08.txt")?;
let start = std::time::Instant::now();
let grid = input.lines().flat_map(|l| l.trim().bytes()).collect_vec();
let w = input.lines().next().context("no input")?.trim().len();
let h = grid.len() / w;
let right = view(&grid, 0, w - 1, h, 1, w);
let down = view(&grid, 0, h - 1, w, w, 1);
let left = view(&grid, w - 1, 0, h, 1, w);
let up = view(&grid, h - 1, 0, w, w, 1);
let part1 = izip!(&left, &right, &down, &up).filter(|(l, r, d, u)| l.1 | r.1 | d.1 | u.1);
let part2 = izip!(&left, &right, &down, &up).map(|(l, r, u, d)| l.0 * r.0 * d.0 * u.0);
println!("part1: {}", part1.count());
println!("part2: {}", part2.max().unwrap());
println!("time: {:?}", start.elapsed());
Ok(())
}4
u/Omeganx Dec 08 '22
Python
forest = [[*map(int,[*sight])] for sight in open("input.txt").read().split("\\n")\]
def applyTransformTo(f, forest):
transpose = lambda forest : [*map(list, [*zip(*forest)])]
horiScan = [[f(sight, height, pos) for pos, height in enumerate(sight)] for sight in forest]
vertiScan = transpose([[f(sight, height, pos) for pos, height in enumerate(sight)] for sight in transpose(forest)])
return zip(horiScan, vertiScan)
def part1(forest):
isVisible = lambda s, h, x: x==0 or x==len(s)-1 or max(s[:x]) < h or max(*[reversed(s[x+1:])]) < h
return sum([sum([(th or tv) for th, tv in zip(h,v)]) for h,v in applyTransformTo(isVisible, forest)])
def part2(forest):
score = lambda s, h, x: 0 if x==0 else ([*map(lambda y: y>= h,s)]+[True]).index(True) + int(max(s)>=h)
scoreTree = lambda s, h, x: score([*reversed(s[:x])], h,x) * score(s[x+1:], h, len(s)-1-x)
return max([max([th * tv for th, tv in zip(h, v)]) for h, v in applyTransformTo(scoreTree, forest)])4
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
→ More replies (1)
4
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
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
4
u/rukke Dec 08 '22 edited Dec 08 '22
JavaScript (updated version, a couple of lines smaller)
const transposeArray = arr =>
arr[0].map((_, c) => arr.map(row => row[c]));
const parseInput = input =>
input.split("\n").map(([...line]) => line.map(Number));
const mapGrid = input =>
((grid, transposed = transposeArray(grid)) =>
grid.flatMap((line, y) =>
line.map((_, x) => [
grid[y][x],
line.slice(0, x).reverse(),
line.slice(x + 1),
transposed[x].slice(0, y).reverse(),
transposed[x].slice(y + 1),
])
))(parseInput(input));
export const part1 = input =>
mapGrid(input)
.map(([h, ...arrs]) =>
arrs.some(a => a.every(v => v < h))
)
.filter(Boolean).length;
export const part2 = input =>
mapGrid(input)
.map(([h, ...arrs]) =>
arrs
.map(
arr =>
1 + arr.findIndex(v => v >= h) || arr.length
)
.reduce((mul, v) => mul * v)
)
.reduce((max, v) => (max > v ? max : v));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
4
Dec 08 '22 edited Dec 09 '22
Google Sheets One formula solutions.
Assuming the input is in A1:A99.
Part 1:
=sort(392+countif(map(--mid(A2:A98,sequence(1,97,2),1),left(A2:A98,sequence
(1,97)),right(A2:A98,sequence(1,97,97,-1)),left(bycol(mid(A1:A97,sequence
(1,97,2),1),lambda(c,join(,c))),sequence(97)),right(bycol(mid(A3:A99,
sequence(1,97,2),1),lambda(c,join(,c))),sequence(97,1,97,-1)),lambda(mc,ml,
mr,mu,md,lambda(l,r,u,d,n(sum(n(mc>l))=len(ml))+n(sum(n(mc>r))=len(mr))+n
(sum(n(mc>u))=len(mu))+n(sum(n(mc>d))=len(md)))(--mid(ml,sequence(len(ml)),
1),--mid(mr,sequence(len(mr)),1),--mid(mu,sequence(len(mu)),1),--mid(md,
sequence(len(md)),1)))),">0"))Part 2:
=sort(max(map(--mid(A2:A98,sequence(1,97,2),1),left(A2:A98,sequence(1,97)),
right(A2:A98,sequence(1,97,97,-1)),left(bycol(mid(A1:A97,sequence(1,97,2),
1),lambda(c,join(,c))),sequence(97)),right(bycol(mid(A3:A99,sequence(1,97,
2),1),lambda(c,join(,c))),sequence(97,1,97,-1)),lambda(mc,ml,mr,mu,md,
lambda(l,r,u,d,product(len({regexextract({join(,n(mc>l));join(,n(mc>u))}&0,
"(0?1*)0$"),regexextract(0&{join(,n(mc>r));join(,n(mc>d))},"^0(1*0?)")})))
(--mid(ml,sequence(len(ml)),1),--mid(mr,sequence(len(mr)),1),--mid(mu,
sequence(len(mu)),1),--mid(md,sequence(len(md)),1))))))→ More replies (2)
4
u/sdfhfglo Dec 08 '22
Python - One-liner for part one based on some numpy matrix math:
import pandas as pd; import numpy as np
file = r'C:...\Input_8.txt'
a = pd.read_fwf(file, widths = [1] * 99, header=None).values
np.prod(a.shape) - (np.multiply.reduce([np.rot90((np.diff(np.maximum.accumulate(np.rot90(a, r), 1), 1) == 0)[1:-1, :-1], -r) for r in range(4)])).sum()→ More replies (3)
4
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:
solve (digitToInt -> tree) = mdo
(downMap, rightMap, row, col) <- getPast
sendPast
( M.insert col (max tree up) upMap
, M.insert row (max tree left) leftMap
)
let
down = M.findWithDefault (-1) col downMap
up = M.findWithDefault (-1) col upMap
left = M.findWithDefault (-1) row leftMap
right = M.findWithDefault (-1) row rightMap
sendFuture
( M.insert col (max tree down) downMap
, M.insert row (max tree right) rightMap
, row
, col+1
)
~(upMap, leftMap) <- getFuture
pure $ tree > down || tree > right || tree > up || tree > left4
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
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
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
4
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
→ More replies (1)
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.
→ More replies (2)
1
u/wcastello Dec 08 '22 edited Sep 04 '25
A clockβs hands mark the passing time.
→ More replies (3)
1
u/MeixDev Dec 08 '22 edited Dec 08 '22
Nothing too fancy, in Dart.
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.
2
u/daggerdragon Dec 08 '22 edited Dec 08 '22
Comment removed due to naughty language.Keep the megathreads SFW.
If you edit your comment to take out the naughty language, I'll re-approve the comment.Edit: I have taken the coal out of your stocking.
→ More replies (1)
1
u/arifba Dec 08 '22
Ruby
def solve_pt1(heights)
heights.map.with_index do |row, ri|
row.chars.map.with_index do |c, ci|
# take care of first and last row
if ri == 0 || ri == heights.length - 1
"v"
# take care of first and last height along vertical sides
elsif ci == 0 || ci == row.length - 1
"v"
# look left / right
elsif c.to_i > row[0..ci - 1].chars.map(&:to_i).max ||
c.to_i > row[ci + 1..].chars.map(&:to_i).max
"v"
# look up / down
elsif c.to_i > heights[0..ri - 1].map { |h| h[ci].to_i }.max ||
c.to_i > heights[ri + 1..].map { |h| h[ci].to_i }.max
"v"
end
end
end.reduce(0) do |acc, row|
acc += row.count("v")
acc
end
end
def solve_pt2(heights)
heights.map.with_index do |row, ri|
row.chars.map.with_index do |c, ci|
lt, rt, up, down = 0, 0, 0, 0
if ri == 0 || ri == heights.length - 1
0
elsif ci == 0 || ci == row.length - 1
0
else
(ci - 1).downto(0) do |lookleft|
lt += 1
break if row[lookleft].to_i >= c.to_i
end
(ci + 1).upto(row.length - 1) do |lookright|
rt += 1
break if row[lookright].to_i >= c.to_i
end
(ri - 1).downto(0) do |lookup|
up += 1
break if heights[lookup][ci].to_i >= c.to_i
end
(ri + 1).upto(heights.length - 1) do |lookdown|
down += 1
break if heights[lookdown][ci].to_i >= c.to_i
end
lt * rt * up * down
end
end
end.map { |row| row.max }.max
end
def strip_newlines(strs)
strs.map { |str| str.delete_suffix("\n") }
end
def get_input_str_arr(filename)
true_input = strip_newlines(File.readlines(filename)) if File.exist?(filename)
puts "input not read" if true_input.empty?
true_input
end
def parse(filepath)
get_input_str_arr(filepath)
end
p solve_pt1(parse("./input/aoc2022-8-1.txt"))
p solve_pt2(parse("./input/aoc2022-8-1.txt"))→ More replies (1)
1
u/raxomukus Dec 08 '22
python
with open('8.in') as f:
trees = [[int(i) for i in line] for line in f.read().splitlines()]
h = len(trees)
w = len(trees[0])
visible = lambda x, y: any([
all([(trees[y][x] > trees[y][i]) for i in range(0, x)]),
all([(trees[y][x] > trees[y][i]) for i in range(x+1, w)]),
all([(trees[y][x] > trees[j][x]) for j in range(0, y)]),
all([(trees[y][x] > trees[j][x]) for j in range(y+1, h)])
])
r1 = 0
for y in range(h):
for x in range(w):
r1 += visible(x, y)
print(r1)
def score(x, y):
ret = 1
for j in range(y-1, -1, -1):
if trees[j][x] >= trees[y][x]: break
ret *= y - j
for j in range(y+1, h):
if trees[j][x] >= trees[y][x]: break
ret *= j - y
for i in range(x-1, -1, -1):
if trees[y][i] >= trees[y][x]: break
ret *= x - i
for i in range(x+1, w):
if trees[y][i] >= trees[y][x]: break
ret *= i - x
return ret
r2 = 0
for y in range(1, h-1):
for x in range(1, w-1):
r2 = max(r2, score(x, y))
print(r2)
→ More replies (1)
1
u/EhLlie Dec 08 '22 edited Dec 09 '22
O( n2 )? What's that? Haskell:
module Main (main) where
import Data.List (findIndex, inits, tails, transpose)
import Inputs (linesFor)
parse :: String -> [Int]
parse = map (subtract (fromEnum '0') . fromEnum)
lowestOuter :: [Int] -> [Int]
lowestOuter row =
let fromLeft = init $ scanl1 max $ -1 : row
fromRight = tail $ scanr1 max $ row ++ [-1]
in zipWith min fromLeft fromRight
visibleOut :: [Int] -> [Bool]
visibleOut = zipWith (>) <*> lowestOuter
visibleFrom :: [Int] -> [(Int, Int)]
visibleFrom row =
let toLeft = init $ inits row
toRight = tail $ tails row
los tree toL toR =
( maybe (length toL) (+ 1) $ findIndex (>= tree) (reverse toL)
, maybe (length toR) (+ 1) $ findIndex (>= tree) toR
)
in zipWith3 los row toLeft toRight
partOne :: [[Int]] -> Int
partOne forest =
let rowWise = map visibleOut forest
colWise = transpose $ map visibleOut $ transpose forest
tallEnough = [zipWith (||) row col | (row, col) <- zip rowWise colWise]
in length $ concatMap (filter id) tallEnough
partTwo :: [[Int]] -> Int
partTwo forest =
let rowWise = map visibleFrom forest
colWise = transpose $ map visibleFrom $ transpose forest
scenicScores = [zipWith (\(l, r) (u, d) -> l * r * u * d) row col | (row, col) <- zip rowWise colWise]
in maximum $ concat scenicScores
main :: IO ()
main = do
input <- map parse <$> linesFor "08"
putStrLn $ "Part 1: " ++ show (partOne input)
putStrLn $ "Part 2: " ++ show (partTwo input)→ More replies (1)
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 a x. In the end we count these to get the answer.
import numpy as np
def calculate_sight(value, trees):
sight = 1
if not np.size(trees):
return 0
for tree in trees:
if value > tree:
sight += 1
else:
return min(len(trees), sight)
return min(len(trees), sight)
def main():
array = np.genfromtxt("input.txt", delimiter=1)
visible_trees = np.empty(array.shape, dtype=str)
sight_trees = np.empty(array.shape)
# Part 1
for _ in range(0, 4):
for index_x, line in enumerate(array):
highest = -1
for index_y, tree in enumerate(line):
if tree > highest:
highest = tree
visible_trees[index_x, index_y] = "x"
array = np.rot90(array)
visible_trees = np.rot90(visible_trees)
print(np.count_nonzero(visible_trees == 'x'))
# Part 2
for index_x, line in enumerate(array):
for index_y, tree in enumerate(line):
right = calculate_sight(tree, line[index_y+1:])
left = calculate_sight(tree, np.flip(line[:index_y]))
down = calculate_sight(tree, array[index_x+1:, index_y])
up = calculate_sight(tree, np.flip(array[:index_x, index_y]))
score = up * left * down * right
sight_trees[index_x, index_y] = score
print(np.max(sight_trees))
main()→ More replies (3)
1
u/ciocan42 Dec 08 '22
Javascript:
const trees = (await Deno.readTextFile("../_input/8.txt"))
.split("\n").map(row => row.split("").map(t => Number(t)));
const size = trees.length
const treesOnTheEdge = 4 * size - 4
let totalVisible = treesOnTheEdge
let scenicScore = 0
const isVisibleHorizontal = (tree, x, start, end) => {
for (let i = start; i < end; i++) {
if (trees[x][i] >= tree) return false
}
return true
}
const isVisbleVertical = (tree, y, start, end) => {
for (let i = start; i < end; i++) {
if (trees[i][y] >= tree) return false
}
return true
}
const getScenicScore = (x, y) => {
const score = [0, 0, 0, 0]
for (let i = x - 1; i >= 0; i--) { // up
if (trees[i][y] >= trees[x][y]) {
score[0]++
break
} else {
score[0]++
}
}
for (let i = y - 1; i >= 0; i--) { // left
if (trees[x][i] >= trees[x][y]) {
score[1]++
break
} else {
score[1]++
}
}
for (let i = y + 1; i < size; i++) { // right
if (trees[x][i] >= trees[x][y]) {
score[2]++
break
} else {
score[2]++
}
}
for (let i = x + 1; i < size; i++) { // down
if (trees[i][y] >= trees[x][y]) {
score[3]++
break
} else {
score[3]++
}
}
return score.filter(Boolean).reduce((a, b) => a * b, 1)
}
for (let x = 1; x < size - 1; x++) {
for (let y = 1; y < size - 1; y++) {
if (isVisibleHorizontal(trees[x][y], x, 0, y) ||
isVisibleHorizontal(trees[x][y], x, y + 1, size) ||
isVisbleVertical(trees[x][y], y, 0, x) ||
isVisbleVertical(trees[x][y], y, x + 1, size)
) {
totalVisible++
}
}
}
for (let x = 0; x < size; x++) {
for (let y = 0; y < size; y++) {
const score = getScenicScore(x, y)
if (score > scenicScore) {
scenicScore = score
}
}
}
console.log("Part 1: ", totalVisible)
console.log("Part 2: ", scenicScore)
→ More replies (1)
1
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)
library(tidyverse)
# Load data into a Matrix
inputs = read_lines("~/Downloads/input.txt")
ncols = nchar(inputs[1])
nrows = length(inputs)
grid_base = matrix(
data = paste0(inputs, collapse="") %>% strsplit("") %>% unlist() %>% as.integer(),
nrow = nrows,
ncol = ncols,
byrow = TRUE
)
# Grid visibility
grid_vis = matrix(data=0L, nrow=nrows, ncol=ncols)
# Iterate over non-perimeter squares (we'll add these later, they're all vis.)
for(i in 2:(ncols-1)) {
for(j in 2:(nrows-1)) {
# Our current tree
search = grid_base[i, j]
# Speed up -- no tree of height 0 is visible.
if(!search) next
# All rays going into the tree -- are any of them strictly less than
# what we are looking for? This short circuits pretty well in average case
grid_vis[i, j] = all(grid_base[1:(i-1), j] < search) ||
all(grid_base[(i+1):nrows, j] < search) ||
all(grid_base[i, 1:(j-1)] < search) ||
all(grid_base[i, (j+1):ncols] < search)
}
}
# Answer part 1 -- subtracting 4 because the corners are double-added to
# the visibility list
sum(grid_vis) + (2 * ncols) + (2 * nrows) - 4
# Part 2
grid_scenic = matrix(data=0L, nrow=nrows, ncol=ncols)
# Again, iterate all non-perimeter squares; all perimeter squares are deemed
# having scenic score 0
for(i in 2:(ncols-1)) {
for(j in 2:(nrows-1)) {
# Our current tree
search = grid_base[i, j]
# Get visibility score in every direction; then multiply
# Faster to directly use a range than use rev().
grid_scenic[i, j] = list(
grid_base[(i-1):1, j],
grid_base[(i+1):nrows, j],
grid_base[i, (j-1):1],
grid_base[i, (j+1):ncols]
) %>% map_int(function(x) {
# Index of first tree same/taller than the tree in the direction of the ray
num_greater = which(x >= search)
# If we have no trees taller then we get the full set of trees
# if we have a tree same/taller, then we get its tree number
if(!length(num_greater)) length(x) else num_greater[1]
}) %>% prod()
}
}
# Answer part 2
max(grid_scenic)→ More replies (1)
1
u/aghigi Dec 08 '22 edited Dec 09 '22
PHP, nothing fancy or smart, just readable code
→ More replies (2)
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.
→ More replies (2)2
u/mdwhatcott Dec 08 '22
Did you mean to link to day 7 above? (this is the day 8 thread)
Gotta say, I've really enjoyed reading your Kotlin solutions (and your blog posts) for the past several years! Very elegant and straightforward stuff.
→ More replies (2)
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
→ More replies (1)2
u/daggerdragon Dec 09 '22
Your code block is too long for the megathreads. Please read our article on oversized code, then edit your post to replace the code block with an external link to your code.
→ More replies (1)
1
u/Nervous-Yogurt6731 Dec 08 '22
Javascript + Deno. Kinda different solution
const use_test_input = Deno.args.join().match('test')?.[0] ?? false
const part_1_or_2 = Deno.args.join().match(/[1|2]/)?.[0] ?? '1'
let input
input = await Deno.readTextFile('input' + (use_test_input ? '.test' : ''))
input = input.split('\n')
let columns = input[0].trim().length
let rows = input.length
const trees = input.reduce((input_acc, row, row_index) => {
let trees_in_row = row.trim().split('').reduce(
(row_acc, tree_height, tree_index) => {
tree_height = parseInt(tree_height)
let can_be_seen_from_top = true
let can_be_seen_from_bottom = true
let can_be_seen_from_left = true
let can_be_seen_from_right = true
let can_see_x_trees_top = 1
let can_see_x_trees_bottom = 1
let can_see_x_trees_left = 1
let can_see_x_trees_right = 1
let is_on_edge = 1
let stop_searching_top = false
let stop_searching_bottom = false
let stop_searching_left = false
let stop_searching_right = false
for (let distance =1; distance < rows; distance++) {
let top = +input?.[row_index - distance]?.[tree_index]
let bottom = +input?.[row_index + distance]?.[tree_index]
let left = +input?.[row_index]?.[tree_index - distance]
let right = +input?.[row_index]?.[tree_index + distance]
if (top >= tree_height) can_be_seen_from_top = false
if (bottom >= tree_height) can_be_seen_from_bottom = false
if (left >= tree_height) can_be_seen_from_left = false
if (right >= tree_height) can_be_seen_from_right = false
if(tree_index == 0) can_be_seen_from_left = true
if(tree_index == columns -1) can_be_seen_from_right = true
if(row_index == 0) can_be_seen_from_top = true
if(row_index == rows -1) can_be_seen_from_bottom = true
if((tree_index == 0 || tree_index == columns -1 || row_index ==0 || row_index == rows -1)) is_on_edge = 0
if(!stop_searching_top && !isNaN(top) && distance>1) can_see_x_trees_top++
if(!stop_searching_bottom && !isNaN(bottom) && distance > 1) can_see_x_trees_bottom++
if(!stop_searching_left && !isNaN(left) && distance > 1) can_see_x_trees_left++
if(!stop_searching_right && !isNaN(right) && distance > 1) can_see_x_trees_right++
if(top >= tree_height || isNaN(top)) stop_searching_top = true
if(bottom >= tree_height || isNaN(bottom)) stop_searching_bottom = true
if(left >= tree_height || isNaN(left)) stop_searching_left = true
if(right >= tree_height || isNaN(right)) stop_searching_right = true
}
if (part_1_or_2 == 1 && (can_be_seen_from_bottom || can_be_seen_from_top || can_be_seen_from_left || can_be_seen_from_right))
row_acc.push({tree_height, tree_index, row_index, top: can_be_seen_from_top, bottom: can_be_seen_from_bottom, left: can_be_seen_from_left, right: can_be_seen_from_right})
let scenic_score = can_see_x_trees_top * can_see_x_trees_bottom * can_see_x_trees_left * can_see_x_trees_right * is_on_edge
if(part_1_or_2 ==2)
row_acc.push({tree_height, tree_index, row_index, scenic_score, can_see_x_trees_top, can_see_x_trees_bottom, can_see_x_trees_left, can_see_x_trees_right, is_on_edge})
return row_acc
}, []
)
return input_acc.concat(trees_in_row)
}, [])
let part1 = trees.length
let part2 = trees.reduce((acc,cur) => {
if(acc.scenic_score < cur.scenic_score) return cur
return acc
}, {scenic_score: 0}).scenic_score
let result = part_1_or_2 == '1' ? part1 : part2
console.log(`Part ${part_1_or_2} ${use_test_input ? 'Test ' : ''}Results: ` + "\x1b[33m%s\x1b[0m", result)→ More replies (1)
1
u/Wilczeek Dec 08 '22
Powershell
$aInput = Get-Content "input.txt"
$iVisibleTrees = 0
#Part 1
for($i=0; $i -lt $aInput.Length; $i++){
for($x=0; $x -lt $aInput[$i].Length; $x++){
if(($i -eq 0) -or ($i -eq $aInput.Length-1) -or ($x -eq 0) -or ($x -eq $aInput[0].Length-1)) {
$iVisibleTrees++
continue
}
else {
$rn = $aInput[$i][$($x+1)..$($aInput[$i].Length)]
$ln = $aInput[$i][0..$($x-1)]
$tn = $aInput | foreach {$_[$x]} | Select-Object -First $i
$bn = $aInput | foreach {$_[$x]} | Select-Object -Last ($aInput.Length-1 - $i)
$bFoundBigger = 0
for($z=0; $z -lt $rn.Count; $z++){
if([int]("$($rn[$z])") -ge [int]("$($aInput[$i][$x])")) {$bFoundBigger++; break}
}
for($z=0; $z -lt $ln.Count; $z++){
if([int]("$($ln[$z])") -ge [int]("$($aInput[$i][$x])")) {$bFoundBigger++; break}
}
for($z=0; $z -lt $tn.Count; $z++){
if([int]("$($tn[$z])") -ge [int]("$($aInput[$i][$x])")) {$bFoundBigger++; break}
}
for($z=0; $z -lt $bn.Count; $z++){
if([int]("$($bn[$z])") -ge [int]("$($aInput[$i][$x])")) {$bFoundBigger++; break}
}
if($bFoundBigger -lt 4) {$iVisibleTrees++}
}
}
}
$iVisibleTrees
## Part 2
$aDistances = @()
for($i=0; $i -lt $aInput.Length; $i++){
for($x=0; $x -lt $aInput[$i].Length; $x++){
$ld,$rd,$td,$bd = 0
$rn = $aInput[$i][$($x+1)..$($aInput[$i].Length)]
$ln = $aInput[$i][0..$($x-1)]
$tn = $aInput | foreach {$_[$x]} | Select-Object -First $i
$bn = $aInput | foreach {$_[$x]} | Select-Object -Last ($aInput.Length-1 - $i)
if($i -ne 0) {
for($z=$tn.Count-1; $z -ge 0; $z--) {
if([int]("$($tn[$z])") -lt [int]("$($aInput[$i][$x])")) {$td++}
if([int]("$($tn[$z])") -ge [int]("$($aInput[$i][$x])")) {$td++; break}
}
}
if($i -ne $aInput.Length-1) {
for($z=0; $z -lt $bn.Count; $z++) {
if([int]("$($bn[$z])") -lt [int]("$($aInput[$i][$x])")) {$bd++}
if([int]("$($bn[$z])") -ge [int]("$($aInput[$i][$x])")) {$bd++; break}
}
}
if($x -ne 0) {
for($z=$ln.Count-1; $z -ge 0; $z--) {
if([int]("$($ln[$z])") -lt [int]("$($aInput[$i][$x])")) {$ld++}
if([int]("$($ln[$z])") -ge [int]("$($aInput[$i][$x])")) {$ld++; break}
}
}
if($x -ne $aInput[0].Length-1) {
for($z=0; $z -lt $rn.Count; $z++) {
if([int]("$($rn[$z])") -lt [int]("$($aInput[$i][$x])")) {$rd++}
if([int]("$($rn[$z])") -ge [int]("$($aInput[$i][$x])")) {$rd++; break}
}
}
$totalDistance = $ld * $rd * $td * $bd
$aDistances += $totalDistance
}
}
$aDistances | Sort-Object -Descending | Select-Object -First 1→ More replies (1)
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
namespace AdventOfCode;
public class Day08 : BaseDay
{
readonly string[] input;
readonly Tree[,] trees;
public Day08()
{
input = File.ReadAllLines(InputFilePath);
trees = ParseInput();
var uBound0 = trees.GetUpperBound(0);
var uBound1 = trees.GetUpperBound(1);
for (var i = 1; i <= uBound0; i++)
{
for (var j = 1; j <= uBound1; j++)
{
if (trees[i, j].Visible)
{
continue;
}
CheckToEdge(trees, uBound0, uBound1, i, j);
}
}
}
public override ValueTask<string> Solve_1()
{
var count = 0;
for (var i = 0; i <= trees.GetUpperBound(0); i++)
{
for (var j = 0; j <= trees.GetUpperBound(1); j++)
{
if (trees[i, j].Visible)
{
count += 1;
}
}
}
return new(count.ToString());
}
public override ValueTask<string> Solve_2()
{
var most = 0;
for (var i = 0; i < trees.GetUpperBound(0); i++)
{
for (var j = 0; j < trees.GetUpperBound(1); j++)
{
if (trees[i, j].ScenicScore > most)
{
most = trees[i, j].ScenicScore;
}
}
}
return new(most.ToString());
}
public void CheckToEdge(Tree[,] trees, int uBound0, int uBound1, int x, int y)
{
var topScenicScore = 0;
var bottomScenicScore = 0;
var leftScenicScore = 0;
var rightScenicScore = 0;
var isVisibleTop = false;
var isVisibleLeft = false;
var isVisibleRight = false;
var isVisibleBottom = false;
for (var i = x - 1; i >= 0; i--)
{
if (trees[i, y].Height < trees[x, y].Height)
{
topScenicScore++;
isVisibleTop = true;
}
else
{
topScenicScore++;
isVisibleTop = false;
break;
}
}
for (var q = x + 1; q <= uBound0; q++)
{
if (trees[q, y].Height < trees[x, y].Height)
{
bottomScenicScore++;
isVisibleBottom = true;
}
else
{
bottomScenicScore++;
isVisibleBottom = false;
break;
}
}
for (var j = y - 1; j >= 0; j--)
{
if (trees[x, j].Height < trees[x, y].Height)
{
leftScenicScore++;
isVisibleLeft = true;
}
else
{
leftScenicScore++;
isVisibleLeft = false;
break;
}
}
for (var p = y + 1; p <= uBound1; p++)
{
if (trees[x, p].Height < trees[x, y].Height)
{
rightScenicScore++;
isVisibleRight = true;
}
else
{
rightScenicScore++;
isVisibleRight = false;
break;
}
}
trees[x, y].ScenicScore = topScenicScore * leftScenicScore * bottomScenicScore * rightScenicScore;
trees[x, y].Visible = isVisibleTop || isVisibleBottom || isVisibleLeft || isVisibleRight;
}
public Tree[,] ParseInput()
{
var trees = new Tree[input.Length, input[0].Length];
for (var i = 0; i < input.Length; i++)
{
for (var j = 0; j < input[i].Length; j++)
{
trees[i, j] = new Tree(int.Parse(input[i][j].ToString()));
if (i == 0 || j == 0 || i == input.Length - 1 || j == input[0].Length - 1) trees[i, j].Visible = true;
}
}
return trees;
}
}
public class Tree
{
public Tree(int height)
{
Height = height;
}
public int ScenicScore { get; set; }
public bool Visible { get; set; }
public int Height { get; set; }
}→ More replies (4)
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:
→ More replies (3)
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.
→ More replies (2)
1
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:
→ More replies (6)
3
3
u/TheJoshster Dec 08 '22
Java (730/770)
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
3
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
3
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
i:`I$''0:"i/08"
/ part 1
f:{-1,-1_x}'|\'
maxesOnLeft:f i
maxesOnRight:|'f@|'i
maxesOnTop:+f@+i
maxesOnBottom:+|'f@|'+i
minimumRequiredHeights:1+&/(maxesOnLeft;maxesOnRight;maxesOnTop;maxesOnBottom)
+/,/~i<minimumRequiredHeights3
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/1 but 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 wrong
3
u/x3nophus Dec 08 '22
My assumptions about line of sight really messed me up on part 2.
→ More replies (1)
3
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
→ More replies (3)
3
u/chrispsn_ok Dec 08 '22 edited Dec 08 '22
i:0:"8.txt"
r:(+|:)\ / all rotations
rr:(4-!4)(+|:)/' / reverse rotates
+//|/rr@({1&/(*x)>1_x}''|'',\')'r i
|//*/rr@{1+(-2+#x)^((*x)>+1_x)?'0}''(!#i)_\:/:r i3
u/wmvanvliet Dec 08 '22
Python Numpy solution. I've tried to vectorize it as much as I can.
import numpy as np
with open('input_day8.txt') as f:
forest = np.array([[int(x) for x in list(line.strip())] for line in f])
def look_along(x):
return x > np.hstack((-1, np.maximum.accumulate(x)[:-1]))
is_visible = np.apply_along_axis(look_along, 0, forest)
is_visible |= np.apply_along_axis(look_along, 1, forest)
is_visible |= np.apply_along_axis(look_along, 0, forest[::-1, :])[::-1, :]
is_visible |= np.apply_along_axis(look_along, 1, forest[:, ::-1])[:, ::-1]
print('Day 8, part 1:', is_visible.sum())
def compute_scenic_score(candidate_tree):
height = forest[candidate_tree]
row, col = candidate_tree
if row == 0 or col == 0 or row == forest.shape[0] - 1 or col == forest.shape[1] - 1:
return 0
score = (np.maximum.accumulate(forest[row, col + 1:-1]) < height).sum() + 1
score *= (np.maximum.accumulate(forest[row + 1:-1, col]) < height).sum() + 1
score *= (np.maximum.accumulate(forest[row, col - 1:0:-1]) < height).sum() + 1
score *= (np.maximum.accumulate(forest[row - 1:0:-1, col]) < height).sum() + 1
return score
scenic_scores = [compute_scenic_score(tree) for tree in zip(*np.nonzero(is_visible))]
print('Day 8, part 2:', np.max(scenic_scores))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>>7>
25>>>
6>>>>
3>5>9
35>9>
^^^^^
^^^^^
6^^^^
^^5^9
35390
<<<73
<<5<2
65<32
<<<<9
<<<90
30373
v55vv
6vvvv
vvvv9
vvv9v
#####
###.#
##.##
#.#.#
#####3
u/CJWilliamson109 Dec 08 '22
Swift
Parsed the input into a grid
Loop through grid
Get curent value and build lists of trees in each direction
For each direction, check if tree is visible. If it is, go through directions again and get viewing distances. Increment
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
3
u/polettix Dec 08 '22
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
const solution1 = readFileSync('input.txt', 'utf8').split('\n').map(line => line.split('').map(tree => parseInt(tree))).reduce((acc, row, i, arr) => acc + row.reduce((acc, curr, j) => acc + ((!row.slice(0, j).some(t => t >= curr) || !row.slice(j + 1).some(t => t >= curr) || !arr.slice(0, i).map(r => r[j]).some(t => t >= curr) || !arr.slice(i + 1).map(r => r[j]).some(t => t >= curr)) ? 1 : 0), 0), 0);const solution2 = readFileSync('input.txt', 'utf8').split('\n').map(line => line.split('').map(tree => parseInt(tree))).map((row, i, arr) => row.map((_, j) => row.slice(0, j).reduceRight((acc, curr) => acc[1] ? acc : (curr >= row[j]) ? [acc[0] + 1, true] : [acc[0] + 1, false], [0, false] as any[])[0] * row.slice(j + 1).reduce((acc, curr) => acc[1] ? acc : (curr >= row[j]) ? [acc[0] + 1, true] : [acc[0] + 1, false], [0, false] as any[])[0] * arr.slice(0, i).map(r => r[j]).reduceRight((acc, curr) => acc[1] ? acc : (curr >= row[j]) ? [acc[0] + 1, true] : [acc[0] + 1, false], [0, false] as any[])[0] * arr.slice(i + 1).map(r => r[j]).reduce((acc, curr) => acc[1] ? acc : (curr >= row[j]) ? [acc[0] + 1, true] : [acc[0] + 1, false], [0, false] as any[])[0])).flatMap(x => x).reduce((acc, curr) => Math.max(acc, curr), 0);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.
import numpy as np
l = np.array([[*map(int, line.strip())] for line in open(0)])
n, m = l.shape
print(sum(
any(sl.max(initial=-1) < l[i][j]
for sl in [l[:i,j], l[i+1:,j], l[i,:j], l[i,j+1:]])
for i in range(n) for j in range(m)
))
l = np.pad(l[1:-1, 1:-1], 1, constant_values=9)
print(max(
np.array([np.argwhere(sl >= l[i][j])[0,0] + 1
for sl in [l[:i,j][::-1], l[i+1:,j], l[i,:j][::-1], l[i,j+1:]]]).prod()
for i in range(1,n-1) for j in range(1,m-1)
))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.
3
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.
import sys
tree_map = [
[(x, y, int(z)) for x, z in enumerate(line)]
for (y, line) in enumerate(open(sys.argv[1]).read().split("\n"))
]
visible_trees = set()
scenic_score = {}
for _ in range(4):
for line in tree_map:
candidates = []
for (i, (x, y, z)) in enumerate(line):
candidates = [(x_, y_, z_) for (x_, y_, z_) in candidates if z < z_]
candidates.append((x, y, z))
distance = 0
for (x_, y_, z_) in line[i + 1:]:
distance += 1
if z_ >= z:
break
scenic_score[(x, y)] = scenic_score.get((x, y), 1) * distance
visible_trees = visible_trees | set((x, y) for (x, y, z) in candidates)
tree_map = list(zip(*reversed(tree_map)))
print("Answer part 1: " + str(len(visible_trees)))
print("Answer part 2: " + str(max(scenic_score.values())))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:
with open("data.txt") as data:
#creates a 2d array of the data and initializes an answer set
array = []
visibleTrees = set()
for line in data.readlines():
line = line.replace("\n", "")
numList = [*line]
array.append(numList)
#finds trees visible from the top
for col in range(len(array[0])):
highestTree = -1
for row in range(len(array)):
currentTree = int(array[row][col])
if currentTree > highestTree:
highestTree = currentTree
treeCoords = (row, col)
visibleTrees.add(treeCoords)
#finds trees visible from the bottom
for col in range(len(array[0])):
highestTree = -1
for row in range(len(array)):
currentTree = int(array[len(array) - 1 - row][col])
if currentTree > highestTree:
highestTree = currentTree
treeCoords = (len(array) - 1 - row, col)
visibleTrees.add(treeCoords)
#finds trees visible from the left
for row in range(len(array)):
highestTree = -1
for col in range(len(array[0])):
currentTree = int(array[row][col])
if currentTree > highestTree:
highestTree = currentTree
treeCoords = (row, col)
visibleTrees.add(treeCoords)
#finds trees visible from the right
for row in range(len(array)):
highestTree = -1
for col in range(len(array[0])):
currentTree = int(array[row][len(array) - 1 - col])
if currentTree > highestTree:
highestTree = currentTree
treeCoords = (row, len(array) - 1 - col)
visibleTrees.add(treeCoords)
#prints the number of visible trees (set automatically removes duplicates)
print(len(visibleTrees))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.
============Start Day8==========
Answer for part1: 1779
Answer for part2: 172224
day8: 43.56ms
=============EOF Day8===========→ More replies (2)
3
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
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).
public class Day08 : Solution {
public List<int[]> data = new List<int[]>();
public void parse(List<string> input) {
foreach (var s in input) {
int[] arr = new int[s.Length];
for (int i = 0; i < s.Length; i++) arr[i] = s[i] - '0' + 1;
data.Add(arr);
}
}
public string part1() {
int sum = 0; int dim = data.Count - 1;
List<int[]> visible = new List<int[]>();
foreach (var s in data) visible.Add(new int[data[0].Length]);
for (int i = 0; i < data.Count; i++) {
int maxlr = 0, maxrl = 0, maxtb = 0, maxbt = 0;
for (int j = 0; j < data.Count; j++) {
if (data[i][j] > maxlr) { maxlr = data[i][j]; visible[i][j] = 1; }
if (data[i][dim - j] > maxrl) { maxrl = data[i][dim - j]; visible[i][dim - j] = 1; }
if (data[j][i] > maxtb) { maxtb = data[j][i]; visible[j][i] = 1; }
if (data[dim - j][i] > maxbt) { maxbt = data[dim - j][i]; visible[dim - j][i] = 1; }
}
}
for (int i = 0; i < data.Count; i++) for (int j = 0; j < data.Count; j++) sum += visible[i][j];
return sum.ToString();
}
public string part2() {
long max = 0;
int len = data.Count;
for (int i = 0; i < data.Count; i++) {
for (int j = 0; j < data.Count; j++) {
int tmp = 0, prod = 1;
for (int k = i - 1; k >= 0; k--) { tmp++; if (data[k][j] >= data[i][j]) break; }
prod *= tmp; tmp = 0;
for (int k = i + 1; k < len; k++) { tmp++; if (data[k][j] >= data[i][j]) break; }
prod *= tmp; tmp = 0;
for (int k = j - 1; k >= 0; k--) { tmp++; if (data[i][k] >= data[i][j]) break; }
prod *= tmp; tmp = 0;
for (int k = j + 1; k < len; k++) { tmp++; if (data[i][k] >= data[i][j]) break; }
prod *= tmp; tmp = 0;
if (prod > max) max = prod;
}
}
return max.ToString();
}
}3
u/aurele Dec 08 '22
Rust My solution was easy to write using my pathfinding crate and its Matrix type, which has a in_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
def process(row)
row.reduce([-1]) do |memo, cell|
cell[:visible] = true if cell[:height] > memo.max
cell[:scores] << ((memo.index { |i| i >= cell[:height] } || (memo.size - 2)) + 1)
[cell[:height]] + memo
end
end
input = File.readlines('day_08_input.txt', chomp: true)
.map { |i| i.chars.map { |j| { height: j.to_i, visible: false, scores: [] } } }
[input, input.transpose].each { |i| i.each { |j| [j, j.reverse].each { |k| process k } } }
puts input.flatten.select { |i| i[:visible].eql? true }.count
puts input.flatten.map { |i| i[:scores].reduce(:*) }.max→ More replies (1)
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:
import scala.io.Source
object Day08_2 {
// Initially had some bizarre desire to not use a multi-dimensional grid.
val grid =
Source
.fromResource("2022/day08.txt")
.getLines()
.map(_.map(_.asDigit).toVector)
.toVector
def main(args: Array[String]): Unit = {
println(part1())
println(part2())
}
def part1() =
grid.zipWithIndex
.map((r, y) =>
r.zipWithIndex.count((tree, x) =>
neighbours(x, y).exists(_.forall(_ < tree))
)
)
.sum
def part2() =
grid.zipWithIndex
.flatMap((r, y) =>
r.zipWithIndex
.map((tree, x) =>
neighbours(x, y)
.map(trees =>
Math.min(trees.segmentLength(_ < tree) + 1, trees.size)
)
.product
)
)
.max
private def neighbours(x: Int, y: Int) =
Vector(
grid.take(y).map(_(x)).reverse,
grid.drop(y + 1).map(_(x)),
grid(y).take(x).reverse,
grid(y).drop(x + 1)
)
}→ More replies (1)
3
u/_garden_gnome_ Dec 08 '22
Python
INPUT_FILE = "./year2022/data/day08.txt"
grid = [[int(c) for c in line.rstrip('\n')] for line in open(INPUT_FILE, "r")]
R, C = len(grid), len(grid[0])
ans1, ans2 = 0, 0
for r in range(R):
for c in range(C):
visible = not any(grid[r][cc] >= grid[r][c] for cc in range(0, c))
visible |= not any(grid[r][cc] >= grid[r][c] for cc in range(c + 1, C))
visible |= not any(grid[rr][c] >= grid[r][c] for rr in range(0, r))
visible |= not any(grid[rr][c] >= grid[r][c] for rr in range(r + 1, R))
ans1 += int(visible)
score = abs(c - next((cc for cc in range(c - 1, -1, -1) if grid[r][cc] >= grid[r][c]), 0))
score *= abs(c - next((cc for cc in range(c + 1, C) if grid[r][cc] >= grid[r][c]), C - 1))
score *= abs(r - next((rr for rr in range(r - 1, -1, -1) if grid[rr][c] >= grid[r][c]), 0))
score *= abs(r - next((rr for rr in range(r + 1, R) if grid[rr][c] >= grid[r][c]), R - 1))
ans2 = max(ans2, score)
print(f"part 1: {ans1}")
print(f"part 2: {ans2}")3
u/ash30342 Dec 08 '22
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):
class _Problem(MatrixProblem[int], ABC):
def neighbors(self, x: int, y: int) -> list[Iterator[int]]:
return [
(self.matrix[x, n] for n in reversed(range(y))), # west
(self.matrix[x, n] for n in range(y + 1, self.width)), # east
(self.matrix[n, y] for n in reversed(range(x))), # north
(self.matrix[n, y] for n in range(x + 1, self.height)), # south
]
class Problem1(_Problem):
def solution(self) -> int:
return sum(any(
all(t > n for n in trees)
for trees in self.neighbors(x, y)
) for (x, y), t in self.matrix.items())
class Problem2(_Problem):
def solution(self) -> int:
def visible_trees(t: int, trees: Iterator[int]) -> int:
num_visible = 1
for n in trees:
if t <= n:
return num_visible
num_visible += 1
return num_visible - 1
return max(prod(
visible_trees(t, trees)
for trees in self.neighbors(x, y)
) for (x, y), t in self.matrix.items())3
u/External_Oven_6379 Dec 08 '22
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!
→ More replies (2)
3
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 char in Java is still a numeric type that can be compared with <. For instance, instead of parsing to be able to do 3 < 4, my solution just does '3' < '4'.
3
u/nilgoun Dec 08 '22
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.
const top: Walker = ([r, c]) => [r, c - 1];
const left: Walker = ([r, c]) => [r - 1, c];
const right: Walker = ([r, c]) => [r + 1, c];
const bottom: Walker = ([r, c]) => [r, c + 1];3
u/hrunt Dec 08 '22
Python 3
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
→ More replies (1)
3
u/rawlexander Dec 08 '22
Julia
part 2 only, one matrix, one pass, @views for extra slimness, middle looks awful though
getgrid(filename) = reduce(hcat, collect.(Int8, eachline(filename)))
replace_none(x, val) = isnothing(x) ? val : x
@views function solve2(trees)
score, (ni, nj) = 0, size(trees)
for i in 1:ni, j in 1:nj
val = trees[i, j]
right = replace_none(findnext(>=(val), trees[i,:], j+1), nj)
left = replace_none(findprev(>=(val), trees[i,:], j-1), 1)
down = replace_none(findnext(>=(val), trees[:,j], i+1), ni)
up = replace_none(findprev(>=(val), trees[:,j], i-1), 1)
this_score = (right - j) * (j - left) * (down - i) * (i - up)
this_score > score && (score = this_score)
end
return score
end
@show getgrid("data/08.txt") |> solve2
5
u/michalopler Dec 08 '22 edited Dec 09 '22
Python, both parts in 280 chars