2022-12-08

# Day 08: Treetop Tree House

Description:
--- Day 8: Treetop Tree House ---

The expedition comes across a peculiar patch of tall trees all planted carefully in a grid. The Elves explain that a previous expedition planted these trees as a reforestation effort. Now, they're curious if this would be a good location for a tree house.

First, determine whether there is enough tree cover here to keep a tree house hidden. To do this, you need to count the number of trees that are visible from outside the grid when looking directly along a row or column.

The Elves have already launched a quadcopter to generate a map with the height of each tree (your puzzle input). For example:

30373
25512
65332
33549
35390

Each tree is represented as a single digit whose value is its height, where 0 is the shortest and 9 is the tallest.

A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.

All of the trees around the edge of the grid are visible - since they are already on the edge, there are no trees to block the view. In this example, that only leaves the interior nine trees to consider:

The top-left 5 is visible from the left and top. (It isn't visible from the right or bottom since other trees of height 5 are in the way.)
The top-middle 5 is visible from the top and right.
The top-right 1 is not visible from any direction; for it to be visible, there would need to only be trees of height 0 between it and an edge.
The left-middle 5 is visible, but only from the right.
The center 3 is not visible from any direction; for it to be visible, there would need to be only trees of at most height 2 between it and an edge.
The right-middle 3 is visible from the right.
In the bottom row, the middle 5 is visible, but the 3 and 4 are not.

With 16 trees visible on the edge and another 5 visible in the interior, a total of 21 trees are visible in this arrangement.

Consider your map; how many trees are visible from outside the grid?

--- Part Two ---

Content with the amount of tree cover available, the Elves just need to know the best spot to build their tree house: they would like to be able to see a lot of trees.

To measure the viewing distance from a given tree, look up, down, left, and right from that tree; stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration. (If a tree is right on the edge, at least one of its viewing distances will be zero.)

The Elves don't care about distant trees taller than those found by the rules above; the proposed tree house has large eaves to keep it dry, so they wouldn't be able to see higher than the tree house anyway.

In the example above, consider the middle 5 in the second row:

30373
25512
65332
33549
35390

Looking up, its view is not blocked; it can see 1 tree (of height 3).
Looking left, its view is blocked immediately; it can see only 1 tree (of height 5, right next to it).
Looking right, its view is not blocked; it can see 2 trees.
Looking down, its view is blocked eventually; it can see 2 trees (one of height 3, then the tree of height 5 that blocks its view).

A tree's scenic score is found by multiplying together its viewing distance in each of the four directions. For this tree, this is 4 (found by multiplying 1 * 1 * 2 * 2).

However, you can do even better: consider the tree of height 5 in the middle of the fourth row:

30373
25512
65332
33549
35390

Looking up, its view is blocked at 2 trees (by another tree with a height of 5).
Looking left, its view is not blocked; it can see 2 trees.
Looking down, its view is also not blocked; it can see 1 tree.
Looking right, its view is blocked at 2 trees (by a massive tree of height 9).

This tree's scenic score is 8 (2 * 2 * 1 * 2); this is the ideal spot for the tree house.

Consider each tree on your map. What is the highest scenic score possible for any tree?

Input:
202210010310302121322210423201220000314024242432211425434422230130411300321324302223011311211020120
110110101310322320101034033124303343031143435122351113353455142421341123420341013300312303121102011
022222013123323313404200430243020022232555432244334344444542122134130133413044342230233130022021112
112111200212221204100121022244121453412414141145154551512445525421435232112124343223122023223002202
010223032133232313122112411243113131542422453412413325334141424132125341004123403342031113000321021
120203310013001113014232132353322341235134523424131353554135433255424414441323410043113010210021012
001321033020303133033413032514323122112454135451341114535233523552111335315303411442413103332313030
102233001100013210130402551555541521113335452154222626521451545151431543531541120332311401123233002
000012220223113031313123321342142243351454565666666364326432622135251241345515402410441240003203231
323120110213212212143353534544223242346225556633526325233365442515315454452135521422031032430131220
010220310331203330225142431325531126553665336562254653354425352265653122233143242323103214302312331
123101224243131422134414233423334544425633524646243233362664535663664554135351555324200233211032302
100333303112401243331523125333225424454222662442543663456556432565564235231542334341022204140131010
222320010441120114425514454524226565533325532623432265362636256446244663333511523325400304340133002
001134131023140453514341254322262544543344626564433544326342336243252564355555514153411041322321023
303032023104304131222142562326266256323662554334643363347342242532462534263352425422433133134401332
020340310211345254242454444265454332565537636676554374476536357464242334364525332231411442341304333
010424244214451151434435346345243633344375647763655474336663454733535632266334124355143530400222002
020104234232554141451622326322264263647735447654367457344444465643453634336365231214525124433022444
204201130004331123325262634265424363534754356365344543544653337444375665555552553542414222233041401
231313304412112545143543446626577766674444573674633355336777737535543536546633462414421512204234400
033341420245341341444352655236656744666536473763766674637573737455777566262423256254341313453322144
440314332142235331442343546273646373345664657448647878767773563537357677642454354424141113554434301
002021425352244536243253565466455346736677674884448677865868476765656674742534363462451133433430431
312244242113113354564554337535376574767786648687855878644777578636677645574425532235315311343242411
233122245155144565255556333557536764847587685667467874688477765747736733566463344232665353434242041
022220452513455555322662755373537664785775876754758887458644778857853773647663236626545124422424320
022230332331242525645255575733445554454765688768654845485674575556756764377537266433342513111411334
120341111522144552663266354477644845848748677677644558776677456646677433474757754324325455254224404
334433112533124466362636446457755674575647767878689757997654655557447467734646643623663324241123341
044044511253635465446534354447476746444884889989857597797866787787888747443665545532456524224131143
342122313235634465626773753655655586857767998568657675697899684787888655564663564432663444345124541
300241415543242222674376454758578748859965896985789659878795778758468578856474655622353223553421340
432555555434536525465544664745745888686778996656856565599757587746755745784533654644233622425515434
004155142463225235434575577777764766596665569657879795765857577596467458644447634453564363532531433
315114345132332442746733438647847847577597775567596889586878967997655654786546753744554456313434213
323554311133626266375345655745865485788569878887677897756998589576556656784677663746632663332532151
315144132232553537533354554654464598875898876799867967877875556975854576455736577735632354543155134
222334432553634533666733477687556985579999867776999997898668878678867858466445453753652435255552353
341334452524465435553736485655557568559699788977996667669999667955587886767744364375524653661522332
413445246252544336676458575775678988988586687776978669888789889868875866467477435474464653535223233
113143446226365337646448856475467575668778966797986666789967987866989544578754333667436355422314512
323412424644366374665378846687555957879987766978769867869789986867696554454854656763756625325241145
323421115545525643633547858847889999697776668979678976769897999899659875558684777565446323544324251
432334334444542573375354656474858797778897676698987797799688968867795956877875445655545264424345232
313421526625464654745784667555655877667866889997977998979899968958766968688884745767745342336522224
122211264264562763544488484689975989588788879988798787779667786859558567878485674347334443246223344
255242155636622443335485578658568685878777677999787778898767686987558788876846566435373364366424533
413344156256433653574768654788878777978699969878998798887869869888598888664446534547775236363642425
342124563455467737457658485456878998989988979899998897787987866875698669856575853463673655444534341
232551266232426674334688468579688769898979978897788788899798868699975575444474737764445664236253252
525112465464323755636656578776889996878689879787788998889987978986957695855668736377766252323353255
335335445554653644563344554685858987978878788987977879778999967667869567488847763473767565562443553
545321524224436644545685678886975585679878668999989988977889988665666777667584866437364423354233323
111423266342443746543667554476875575666977668887778798797767868895568959486564657554473632445655344
524212552355364477347365556488688656986668766897897789886896688988559599878748555366373562653454121
131154335433422345634645655457568556886876787789779979987866669967997578577754745577462646226445314
235252452335234564367678476887687995897898668678778786687699867598786667847747567563645652263343425
223253143456366656767765746865557567566666767869789987989986887557956998685474637637366352326243542
022325555334456567353758847454499775865697766886666678799897866988858868887447554444762544422112415
343144416534333377537365468647569967688667888678877876698688967696987958488474576533553236464222515
041455413553636645474356566857777797955967797767896696888698558569799657885773667663642263333432225
314232125326436446553663846575645898685777676969798987998978856859686786577445377553744443245432243
321243223546455364367743474758777659578658777997668897788989566685788888684476563345423344554443231
415125254422442527666573645787574596577688978657789966586986685976985678486637347667436525212454543
414235135545633363666356438757467669858969857687755898578857676858688644547753747345432366312551541
440114242344345546336647565757454586855999757667866776678779875958488554786743465373523322335324440
122344413244444335537455544748467554578788577997879979696958696984755857587433556336643245424414511
404152532353256326373573456764878788486665786786686989885788858787846674744354647343463555324212243
430052142415544522224767753334887658877858987557899587585858774486467688656755647656562452215444341
340214451142655354335334667467484748684647966577756797796876564684745486774456744624442332555544214
202003423413136555225554443743364668647485745965556658974868564455687766677646333424563244225312413
124244252232546632354435547477575454458474888785648855588868547656747434644644562666356425513552234
110004343225254552232245333753757468577454458667486664868686776847774656744433232645435354515511001
114110243523312246646633667657446557887764577875444674586445668855646455464673426355246121241420242
144004022115232335325233544457463354556577558686866645777668486456344336776563552654224535341204000
421204313533552465364335665657756377478687485747568464457586578433533665377544334436324115345110242
310213102455533546266535624345334376363684858775467657685555747353643644472546632522545411333203111
114430325255224412546642432664757677554453367648667474866563366653547673545643556525445241221014044
101202024124311141332246625344457736763773743567676364434654335437667673333633334533321141144401343
022314412343141552545426345523734644465534437755555546366776455573555736346566554523431445312041141
310102320115113413255662622463666645774475764474763576347553464576657544655232265213412332113321240
103421443124221314341526656425352447567466347367455546655457665443752365626234642233144534440401232
012242102421432341212413443326266462435353334443757554636776575352564544364326345342233211400021132
222333320014022434154332424323323222343565375555437333746365455224462465255645335454253531041200430
203301220423445445245343333566523444245653734664355375366356543225425453566551115535422214404241002
302324443031122331441331256335344224253636533556756445434643354532564454235413132113211343002133211
311312211414143323513134241534622563433242365626656422526345223354546364435315451551101023211412130
222110343401032043553425111312244654332653464666435423342453322663424243153233322113032023202020223
323230200411432130355525221321433355242633433225442453325522522622364253311533334354031100222010013
310222312143433114242431355515315554643534324342445656666436353223444231435453241400213321330130010
333003032313304033243534455111112214234262552344526635435332246231323535122413441024143242102302110
113023202303413323324054115321135342223354425566256536556255312115424353351151533010221413210330113
201002101132013010411214525353534241113423251253436544643553152152432455455322331331310031222312310
010000023323114442204233214145222453523254543111213112525444545451354241122320331344023330301010000
020221201301204043241340212025231451554512545355544454355334235544331435121232034423404333303220120
211200133121002321411044312343241534545415435535214551522523534521342510432012433211020132222223110
001010111333021232114033432123014243143421131445211232544521554534542030434313341020033312233321020
110102200233103010320200140144034422131352541143533213514525422131220112004103004000011012120121220

Part 1:
``````import std/strutils
import std/sequtils

proc grid_hidden(grid: seq[seq[int]], cx: int, cy: int, width: int, height: int): bool =
let cv = grid[cy][cx]

if cx == 0 or cy == 0 or cx == width-1 or cy == height-1:
return false

if not (cx+1 ..< width).toSeq().any(proc(x:int):bool = grid[cy][x] >= cv):
return false

if not (0 ..< cx).toSeq().any(proc(x:int):bool = grid[cy][x] >= cv):
return false

if not (cy+1 ..< height).toSeq().any(proc(y:int):bool = grid[y][cx] >= cv):
return false

if not (0 ..< cy).toSeq().any(proc(y:int):bool = grid[y][cx] >= cv):
return false

return true

proc run08_1(): string =

let grid = splitLines(input)
.filterIt(it != "")
.mapIt(it.toSeq().map(proc(p:char):int = parseInt(p.repeat(1))))

# echo grid

let width = grid[0].len()
let height = grid.len()

# echo width, "x", height

var visible = 0

for y in 0 ..< height:
for x in 0 ..< width:
let hidden = grid_hidden(grid, x, y, width, height)
#if hidden:
#    io.stdout.write "#"
#else:
#    io.stdout.write "."
if not hidden: visible += 1
#io.stdout.write "\n"

return intToStr(visible)

when not defined(js):
echo run08_1()
else:
proc js_run08_1(): cstring {.exportc.} =
return cstring(run08_1())
``````
Result: 1823

Part 2:
``````import std/strutils
import std/sequtils

proc direction_score(grid: seq[seq[int]], icx: int, icy: int, width: int, height: int, dx: int, dy: int): int =
let v = grid[icy][icx]
var cx = icx
var cy = icy
var c = 0
while true:
cx += dx
cy += dy
if cx < 0 or cy < 0 or cx >= width or cy >= height:
return c
c += 1
if grid[cy][cx] >= v:
return c

proc scenic_score(grid: seq[seq[int]], cx: int, cy: int, width: int, height: int): int =
let x_pos = direction_score(grid, cx, cy, width, height, +1, 00)
let x_neg = direction_score(grid, cx, cy, width, height, -1, 00)
let y_pos = direction_score(grid, cx, cy, width, height, 00, +1)
let y_neg = direction_score(grid, cx, cy, width, height, 00, -1)

return x_pos * x_neg * y_pos * y_neg

proc run08_2(): string =

let grid = splitLines(input)
.filterIt(it != "")
.mapIt(it.toSeq().map(proc(p:char):int = parseInt(p.repeat(1))))

# echo grid

let width = grid[0].len()
let height = grid.len()

# echo width, "x", height

var max_score = 0

for y in 0 ..< height:
for x in 0 ..< width:
let ss = scenic_score(grid, x, y, width, height)
# echo "[", x, ",", y, "]: ", ss
if ss > max_score: max_score = ss

return intToStr(max_score)

when not defined(js):
echo run08_2()
else:
proc js_run08_2(): cstring {.exportc.} =
return cstring(run08_2())
``````
Result: 211680

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript