diff options
| -rw-r--r-- | 2020/day-11/README.org | 806 | ||||
| -rwxr-xr-x | 2020/day-11/day-11.partial.raku | 102 | ||||
| -rwxr-xr-x | 2020/day-11/day-11.raku | 133 | ||||
| -rw-r--r-- | 2020/day-11/input | 97 |
4 files changed, 1138 insertions, 0 deletions
diff --git a/2020/day-11/README.org b/2020/day-11/README.org new file mode 100644 index 0000000..c60b82b --- /dev/null +++ b/2020/day-11/README.org @@ -0,0 +1,806 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-3.org +#+HTML_LINK_UP: ../../index.html#2020 +#+OPTIONS: toc:1 +#+EXPORT_FILE_NAME: index +#+TITLE: Day 11 - Seating System + +* Puzzle +- This puzzle is taken from: https://adventofcode.com/2020/day/11 + +Your plane lands with plenty of time to spare. The final leg of your +journey is a ferry that goes directly to the tropical island where you +can finally start your vacation. As you reach the waiting area to board +the ferry, you realize you're so early, nobody else has even arrived +yet! + +By modeling the process people use to choose (or abandon) their seat in +the waiting area, you're pretty sure you can predict the best place to +sit. You make a quick map of the seat layout (your puzzle input). + +The seat layout fits neatly on a grid. Each position is either floor +(.), an empty seat (L), or an occupied seat (#). For example, the +initial seat layout might look like this: +#+BEGIN_SRC +L.LL.LL.LL +LLLLLLL.LL +L.L.L..L.. +LLLL.LL.LL +L.LL.LL.LL +L.LLLLL.LL +..L.L..... +LLLLLLLLLL +L.LLLLLL.L +L.LLLLL.LL +#+END_SRC + +Now, you just need to model the people who will be arriving shortly. +Fortunately, people are entirely predictable and always follow a simple +set of rules. All decisions are based on the number of occupied seats +adjacent to a given seat (one of the eight positions immediately up, +down, left, right, or diagonal from the seat). The following rules are +applied to every seat simultaneously: + +- If a seat is empty (L) and there are no occupied seats adjacent to it, + the seat becomes occupied. +- If a seat is occupied (#) and four or more seats adjacent to it are + also occupied, the seat becomes empty. +- Otherwise, the seat's state does not change. + +Floor (.) never changes; seats don't move, and nobody sits on the floor. + +After one round of these rules, every seat in the example layout becomes +occupied: +#+BEGIN_SRC +#.##.##.## +#######.## +#.#.#..#.. +####.##.## +#.##.##.## +#.#####.## +..#.#..... +########## +#.######.# +#.#####.## +#+END_SRC + +After a second round, the seats with four or more occupied adjacent +seats become empty again: +#+BEGIN_SRC +#.LL.L#.## +#LLLLLL.L# +L.L.L..L.. +#LLL.LL.L# +#.LL.LL.LL +#.LLLL#.## +..L.L..... +#LLLLLLLL# +#.LLLLLL.L +#.#LLLL.## +#+END_SRC + +This process continues for three more rounds: +#+BEGIN_SRC +#.##.L#.## +#L###LL.L# +L.#.#..#.. +#L##.##.L# +#.##.LL.LL +#.###L#.## +..#.#..... +#L######L# +#.LL###L.L +#.#L###.## +#+END_SRC +#+BEGIN_SRC +#.#L.L#.## +#LLL#LL.L# +L.L.L..#.. +#LLL.##.L# +#.LL.LL.LL +#.LL#L#.## +..L.L..... +#L#LLLL#L# +#.LLLLLL.L +#.#L#L#.## +#+END_SRC +#+BEGIN_SRC +#.#L.L#.## +#LLL#LL.L# +L.#.L..#.. +#L##.##.L# +#.#L.LL.LL +#.#L#L#.## +..L.L..... +#L#L##L#L# +#.LLLLLL.L +#.#L#L#.## +#+END_SRC + +At this point, something interesting happens: the chaos stabilizes and +further applications of these rules cause no seats to change state! Once +people stop moving around, you count 37 occupied seats. + +Simulate your seating area by applying the seating rules repeatedly +until no seats change state. How many seats end up occupied? +** Part 2 +As soon as people start to arrive, you realize your mistake. People +don't just care about adjacent seats - they care about the first seat +they can see in each of those eight directions! + +Now, instead of considering just the eight immediately adjacent seats, +consider the first seat in each of those eight directions. For example, +the empty seat below would see eight occupied seats: +#+BEGIN_SRC +.......#. +...#..... +.#....... +......... +..#L....# +....#.... +......... +#........ +...#..... +#+END_SRC + +The leftmost empty seat below would only see one empty seat, but cannot +see any of the occupied ones: +#+BEGIN_SRC +............. +.L.L.#.#.#.#. +............. +#+END_SRC + +The empty seat below would see no occupied seats: +#+BEGIN_SRC +.##.##. +#.#.#.# +##...## +...L... +##...## +#.#.#.# +.##.##. +#+END_SRC + +Also, people seem to be more tolerant than you expected: it now takes +five or more visible occupied seats for an occupied seat to become empty +(rather than four or more from the previous rules). The other rules +still apply: empty seats that see no occupied seats become occupied, +seats matching no rule don't change, and floor never changes. + +Given the same starting layout as above, these new rules cause the +seating area to shift around as follows: +#+BEGIN_SRC +L.LL.LL.LL +LLLLLLL.LL +L.L.L..L.. +LLLL.LL.LL +L.LL.LL.LL +L.LLLLL.LL +..L.L..... +LLLLLLLLLL +L.LLLLLL.L +L.LLLLL.LL +#+END_SRC +#+BEGIN_SRC +#.##.##.## +#######.## +#.#.#..#.. +####.##.## +#.##.##.## +#.#####.## +..#.#..... +########## +#.######.# +#.#####.## +#+END_SRC +#+BEGIN_SRC +#.LL.LL.L# +#LLLLLL.LL +L.L.L..L.. +LLLL.LL.LL +L.LL.LL.LL +L.LLLLL.LL +..L.L..... +LLLLLLLLL# +#.LLLLLL.L +#.LLLLL.L# +#+END_SRC +#+BEGIN_SRC +#.L#.##.L# +#L#####.LL +L.#.#..#.. +##L#.##.## +#.##.#L.## +#.#####.#L +..#.#..... +LLL####LL# +#.L#####.L +#.L####.L# +#+END_SRC +#+BEGIN_SRC +#.L#.L#.L# +#LLLLLL.LL +L.L.L..#.. +##LL.LL.L# +L.LL.LL.L# +#.LLLLL.LL +..L.L..... +LLLLLLLLL# +#.LLLLL#.L +#.L#LL#.L# +#+END_SRC +#+BEGIN_SRC +#.L#.L#.L# +#LLLLLL.LL +L.L.L..#.. +##L#.#L.L# +L.L#.#L.L# +#.L####.LL +..#.#..... +LLL###LLL# +#.LLLLL#.L +#.L#LL#.L# +#+END_SRC +#+BEGIN_SRC +#.L#.L#.L# +#LLLLLL.LL +L.L.L..#.. +##L#.#L.L# +L.L#.LL.L# +#.LLLL#.LL +..#.L..... +LLL###LLL# +#.LLLLL#.L +#.L#LL#.L# +#+END_SRC + +Again, at this point, people stop shifting around and the seating area +reaches equilibrium. Once this occurs, you count 26 occupied seats. + +Given the new visibility method and the rule change for occupied seats +becoming empty, once equilibrium is reached, how many seats end up +occupied? +* Solution +=@seats= will hold an Array of Arrays, where each element will represent a +seat. +#+BEGIN_SRC raku +unit sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +); + +my @seats = "input".IO.lines.map(*.comb.cache.Array); +my Int ($x-max, $y-max) = (@seats[0].end, @seats.end); +#+END_SRC + +Part 1 & 2 are so similar that we just need to change 2 variables to get +other part's solution. =$visibility= is of type Num which holds the +visibility range, as discussed in part 2 of the puzzle above. For part +1, this value is just 1 but increases to Infinity for part 2. + +The other variable is =$tolerance=, for part 2 we change it to 5. +#+BEGIN_SRC raku +my Num $visibility = 1e0; +my Int $tolerance = 4; + +# Infinite visibility & increased tolerance for part 2. +($visibility, $tolerance) = (Inf, 5) if $part == 2; +#+END_SRC + +=@directions= is an Array of Lists, where each List holds the values of =$y= +& =$x= required to get to the immediate neighbor. It contains 8 Lists, +each for a direction as shown below. +#+BEGIN_SRC raku +my List @directions[8] = ( + # $y, $x + ( +1, +0 ), # bottom + ( +1, +1 ), # bottom-right + ( +1, -1 ), # bottom-left + ( -1, +0 ), # top + ( -1, +1 ), # top-right + ( -1, -1 ), # top-left + ( +0, +1 ), # right + ( +0, -1 ), # left +); +#+END_SRC + +=$round= is just a nice addition, it'll print the number of rounds we pass +as the code progresses. The outer loop just repeats the =INNER= loop until +=@changed= equals =@seats=. The =INNER= loop is what handles all the seating +arrangement changes & stores them in =@changed=. I've documented the =INNER= +loop after this. + +A little note about =eqv= operator here: I don't know what it does but +it's very smart. I removed =eqv= & added a Bool flag that was set to True +whenever something was changed & checked that instead of comparing with +=eqv=. But the code didn't run much faster, =eqv= code was equally as fast. + +I compared this by profiling the code with =raku --profile=. I just +compared the times & did it only once, so maybe the load was higher +during Bool profiling so it ran slower but yeah the change wasn't much. +And there wasn't much interval between both profilings so I think =eqv= is +actually very smart. +#+BEGIN_SRC raku +my Int $round = 0; +loop { + $round++; + print "Round $round.\r"; + + my Int ($x, $y) = (-1, 0); + my @changed; + INNER: loop { + ... + } + # If seats didn't change then exit the loop. + last if @seats eqv @changed; + + for 0 .. @changed.end -> $y { + for 0.. @changed[0].end -> $x { + @seats[$y][$x] = @changed[$y][$x]; + } + } +} +#+END_SRC + +This is the =INNER= loop. It handles the changes in arrangements & stores +them in =@changed=. It loops over each seat one by one & decides if they +need to be changed. The =given/when= is doing the changing. It simply +follows the rules listed in the puzzle above. + +As for why changes are recorded in =@changed= & not =@seats=, because people +seat at once & not one by one. =adjacent-occupied= returns whether the +seat is occupied or not in case of "L" whereas it returns the number of +seats that are occupied in case of "#". + +This is done because number of seats occupied is not required for "L". +The fifth argument that is being passes is True in case of "L", that +signals =adjacent-occupied= that we just need to know if any adjacent is +occupied or not & not the number of adjacents occupied. + +The subroutine =adjacent-occupied= is discussed after this. +#+BEGIN_SRC raku +if $x == $x-max { + $x = 0; + # goto next row if not in the last row. + last INNER if $y == $y-max; + $y += 1; +} else { + $x += 1; +} + +@changed[$y][$x] = @seats[$y][$x]; +given @seats[$y][$x] { + when '.' { next INNER; } + when 'L' { + unless adjacent-occupied(@seats, $x, $y, $visibility, True) { + @changed[$y][$x] = '#'; + } + } + when '#' { + if adjacent-occupied(@seats, $x, $y, + $visibility, False) >= $tolerance { + @changed[$y][$x] = 'L'; + } + } +} +#+END_SRC + +For the solution, we just print the number of "#" in =@seats=. +#+BEGIN_SRC raku +say "Part $part: ", @seats.join.comb('#').elems; +#+END_SRC + +=adjacent-occupied= returns the number of adjacent cells that have been +occupied by others. =$visibility= should be 1 if only directly adjacent +seats are to be counted. Make it Inf for infinite visibility. It ignores +floors ('.'). + +If =$only-bool= is set then a Bool will be returned which will indicate +whether any adjacent seat it occupied or not. It handles this by +including an early return statement which is only executed if =$only-bool= +is set to True & it returns when we find the first occupied seat. + +=Occupied= subset validates the return value, it should only be Int or a +Bool. + +It loops over the neighbors returned by the =neighbors= subroutine. That +sub returns the list of neighbors of a particular seat. It only returns +the indexes of neighbors and not their value. We just loop over the +indexes & check if the it's occupied & increment =$occupied= if it is. +#+BEGIN_SRC raku +subset Occupied where Int|Bool; +sub adjacent-occupied ( + @seats, Int $x, Int $y, Num $visibility, Bool $only-bool = False + --> Occupied +) { + my Int $occupied = 0; + for neighbors(@seats, $x, $y, $visibility).List -> $neighbor { + if @seats[$neighbor[0]][$neighbor[1]] eq '#' { + return True if $only-bool; + $occupied++ ; + } + } + return $occupied; +} +#+END_SRC + +=neighbors= returns the neighbors of given index. It doesn't account for +=$visibility= when caching the results. So, if =$visibility= changes & it +has a cached result then the return value might be wrong. So, you can't +solve both part 1 & 2 at once because =$visibility= changes between the +two. This can be solved easily by just accounting for =$visibility= when +caching the neighbors. + +Initially this subroutine didn't exist and it's logic was a part of the +=adjacent-occupied= sub. =coldpress= on freenode suggested me to cache the +results. I can't paste the whole chat, it was direct message, I'll quote +a part of it. +#+BEGIN_QUOTE +You should not recompute the indexes of each neighbor in your for-for +loop, but you should check the state of each neighbor in your for-for +loop +#+END_QUOTE + +Before this =$pos-y= & =$pos-x= which hold the position of neighbors were +being recomputed everytime but we don't need to do that. The indexes of +each neighbor stays the same & only the value might change. So we cache +the indexes. And that's what =neighbors= sub does, it caches the indexes +of each seat's neighbors. + +=@neighbors= is an Array of Arrays, it's a =state= variable, which means +that the values will persist on each =neighbors= subroutine call. When +this is called, we just checked if we have the indexes of neighbors +cached, if not then we compute & save it for later. If yes then we just +return from cache. +#+BEGIN_SRC raku +sub neighbors ( + @seats, Int $x, Int $y, Num $visibility --> List +) { + state Array @neighbors; + + unless @neighbors[$y][$x] { + my Int $pos-x; + my Int $pos-y; + + DIRECTION: for @directions -> $direction { + $pos-x = $x; + $pos-y = $y; + SEAT: for 1 .. $visibility { + $pos-y += $direction[0]; + $pos-x += $direction[1]; + + next DIRECTION unless @seats[$pos-y][$pos-x]; + given @seats[$pos-y][$pos-x] { + # Don't care about floors, no need to check those. + when '.' { next SEAT; } + when 'L'|'#' { + push @neighbors[$y][$x], [$pos-y, $pos-x]; + next DIRECTION; + } + } + } + } + } + + return @neighbors[$y][$x]; +} +#+END_SRC + +About the computing neighbors part, we loop over =@directions= & then loop +over =1 .. $visibility=, if the visibility is 1 then the =SEAT= for loop +just runs once. The =SEAT= for loop increments the value of =$pos-x= & +=$pos-y= in given direction. So, if the visibility is Infinite then we'll +keep incrementing. + +To prevent infinite loop over there we add a check. If the seat doesn't +exist then we just move on to next =DIRECTION=. This is handled by the +=unless= block. If the seat does exist then we check if it's floor, if +true then we just ignore it & move on to next =SEAT=. Note that if +=$visibility= is set to 1 then we will just exit the =SEAT= for loop. + +This means that we simply don't check in that direction in +=adjacent-occupied= subroutine, it's fine because the floors don't move as +stated in the puzzle. If it's not a floor then we cache the indexes and +move on to next =DIRECTION=. + +We move to next =DIRECTION= because the puzzle notes this in part 2: +#+BEGIN_QUOTE +People don't just care about adjacent seats - they care about the first +seat they can see in each of those eight directions! +#+END_QUOTE + +The people care about first seat they see in each direction, so we move +on to next direction after reaching the first seat. +** Part 2 +Only 2 variables are changed to get part 2 solution. +#+BEGIN_SRC raku +# Infinite visibility & increased tolerance for part 2. +($visibility, $tolerance) = (Inf, 5) if $part == 2; +#+END_SRC +* Notes +This note is about this piece of code in =neighbors= subroutine: +#+BEGIN_SRC raku +push @neighbors[$y][$x], [$pos-y, $pos-x]; +#+END_SRC + +Note how I'm pushing an Array =[]=, instead of a List =()=. Pushing a list +will cause undesired behavior. + +According to https://docs.raku.org/language/list#Assigning: +#+BEGIN_QUOTE +Assignment of a list to an Array is eager. The list will be entirely +evaluated, and should not be infinite or the program may hang. [...] +#+END_QUOTE + +I'm not sure if this is why this weird behavior happens. When I change +the .Array below to .List it'll cause undesired behavior. It'll push the +same thing. + +=coldpress= on =#raku@freenode= guessed it correctly: +#+BEGIN_QUOTE +<coldpress> my guess is: the wrong behavior is because all elements +refer to the same object, pass-by-reference. The correct behavior with +.Array is because each element now refers to different objects. +#+END_QUOTE + +I confirmed that with changing the value without pushing. That confirmed +that it was not weird push behaviour. What I was pushing was a reference +to the same object, so when I changed it above in =$pos-y= & =$pos-x= the +whole thing changed. + +=raiph= clears this up on =#raku@freenode= later: +#+BEGIN_QUOTE +<raiph> notandinus: An `Array` is a subtype of `List` but their +behaviours are also complementary. + +`Array`s zig in several ways where `List`s zag. This is true of their +literals. + +If you switch your code from pushing `($pos-y, $pos-x)` to `[$pos-y, +$pos-x]` you'll find it works. + +This is because the `Array` literal constructor just takes the *values* +contained in the Scalar`s `$pos-x` and `$pos-y` and puts those values +into its own fresh `Scalar`s. + +Whereas the `List` literal constructor does *not* by default put values in +`Scalar`s -- but if you list one, it stores that instead of the value it +contains. +#+END_QUOTE +* Optimizations +This records the optimizations I made to this day's solution. Some have +already been discussed in the solution, I'll discuss the rest here. I've +profiled the code after significant changes & I'll include information +from the profile too. + +Note that I'm writing this on 2020-12-12 but this thing was done +yesterday, more than 24 hours have passed so I don't remember much. I +was giving feedback on =#raku@freenode= after each profile so I'll be able +to co-relate after looking at IRC logs & created timestamps of profile +files. + +=tyil=, =tadzik=, =lizmat=, =coldpress=, =m6locks= and others on =#raku@freenode= +helped me optimize this code. + +These are values from each profile: +| Value | Profile 1 | Profile 2 | Profile 3 | Profile 4 | +|-------------------------+-------------+-------------+-------------+-------------| +| runtime | 600864.29ms | 410946.37ms | 394648.55ms | 119883.87ms | +| executing code | 553554.21ms | 374743.72ms | 359771.16ms | 105375.88ms | +| D-optimization | 1076.63ms | 982.01ms | 1106.14ms | 697.79ms | +|-------------------------+-------------+-------------+-------------+-------------| +| GC time | 47310.08ms | 36202.65ms | 34877.39ms | 14507.99ms | +| collections | 1248 | 1220 | 1095 | 686 | +| full collections | 7 | 7 | 7 | 3 | +| nursery collection time | 34.27ms | 25.89ms | 27.68ms | 18.79ms | +| full collection time | 683.38ms | 684.92ms | 679.89ms | 557.17ms | +|-------------------------+-------------+-------------+-------------+-------------| +| entered C-frames | 102699610 | 73313599 | 64911620 | 20752434 | +| eliminated C-frames | 141047998 | 98109798 | 74733815 | 43446172 | +| interpreted frames | 21205734 | 11607457 | 13106524 | 104217 | +| specialized frames | 758246 | 718619 | 758310 | 504276 | +| jit-compiled frames | 221783628 | 159097321 | 125780601 | 63590113 | +|-------------------------+-------------+-------------+-------------+-------------| +| eliminated allocations | 78450 | 78500 | 78550 | - | +| deoptimizations | 405912 | 487180 | 487175 | 240735 | +| on-stack replacements | 138 | 144 | 138 | 65 | + ++ C-frames stands for call frames. ++ eliminated C-frames were by inlining. ++ D-optimization stands for dynamic optimization. ++ eliminated allocations were by Scalar replacement. + ++ runtime = executing code + dynamic optimization ++ (jit-compiled + specialized + interpreted = entered) call frames ++ (eliminated + entered = total) call frames + +*Note*: I'm writing this on 2020-12-14, I don't remember anything so +everything below is just from IRC logs. + +Initially I had defined the =@directions= block inside of +=adjacent-occupied= subroutine, note that at this point =neighbors= +subroutine didn't exist. So, =@directions= was being created & destroyed +continously. I changed it to a =state= variable & noticed significant +improvements. + +** Profile 1 +This was the initial Profile, I don't have the code. The structure was +not much different from what it is now, just too inefficient. + +** Profile 2 +I was declaring the =@directions= array inside of =adjacent-occupied= +subroutine. I changed it to a =state= variable. + +** Profile 3 +I made =@directions= a global array. + +** Profile 4 +I put =adjacent-occupied= inside of =MAIN= subroutine along with +=@directions=. + +* Partial solution +I tried solving this another way but it was way too complex so I gave +up. I made it work on sample input given in puzzle but it didn't work on +my actual input. I couldn't point out the error so I just left it as is. +The code is stored in =day-11.partial.raku=. I'll paste it below. + +The idea was to use a single dimension array instead of Array of Arrays. +This made things a bit complicated but would've been faster if I could +get it working. This only dealt with part 1 before I stopped working on +it & went back to Array of Arrays. + +We have 3 different arrays instead of a single =@directions= array +because I was relying on the fact that if I cross the boundary then the +seat wouldn't exist & we won't check for it. But in this case there are +only 2 boundaries, index 0 & last index. + +So, instead we have 3 arrays, one =@non-left-corner= which contains the +directions that left corner can't follow. It can't go "up-left", "left" +or "down-left". And we have similar array for directions that right +corner elements can't follow. + +I'm not sure what is wrong with the code. This solution would've been +interesting. I'm pasting some useful information that might help in +debugging. + +This is what the partial & actual solution print in case of sample input +given in puzzle: +#+BEGIN_SRC +Part 1: 71 +Part 1: 20 +Part 1: 51 +Part 1: 30 +Part 1: 37 +Part 1: 37 +#+END_SRC + +Those were the number of "#" after each round. This is what they print +when I test it with the actual input: +#+BEGIN_SRC +Part 1: 7311 +Part 1: 568 +Part 1: 5524 +Part 1: 1502 +Part 1: 3907 +Part 1: 2198 +Part 1: 3058 +#+END_SRC + +That was partial solution's output, here is actual solution's output: +#+BEGIN_SRC +Part 1: 7311 +Part 1: 194 +Part 1: 6768 +Part 1: 414 +Part 1: 6204 +Part 1: 610 +Part 1: 5739 +Part 1: 809 +Part 1: 5322 +#+END_SRC + +They diverge right after first round. I'm not sure what went wrong, I +can print the seat layout & try to debug but I don't have the energy to +do that currently. Maybe I'll do it sometime later. + +#+BEGIN_SRC raku +sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +) { + my @input = "input".IO.lines; + my Int $x-max = @input[0].chars - 1; + my Int $row-length = $x-max + 1; + + my @seats = @input.join.comb; + my $max-seats = @seats.end; + + my @directions = (+$row-length, -$row-length); # down, up + + # @non-left-corner contains directions that left corner can't + # follow. It should only be followed by non-left corner seats. + my @non-left-corner = ( + -$row-length - 1, # up-left + -1, # left + +$row-length - 1, # down-left + ); + + # @non-right-corner contains directions that right corner can't + # follow. It should only be followed by non-right corner seats. + my @non-right-corner = ( + -$row-length + 1, # up-right + +1, # right + +$row-length + 1, # down-right + ); + + my Int $round = 0; + loop { + my @changed; + my Bool $change = False; + + INNER: for @seats.kv -> $idx, $seat { + @changed[$idx] = $seat; + given $seat { + when '.' { next INNER; } + when 'L' { + if adjacent-occupied($idx, 1) == 0 { + @changed[$idx] = '#'; + $change = True; + } + } + when '#' { + if adjacent-occupied($idx, 1) >= 4 { + @changed[$idx] = 'L'; + $change = True; + } + } + } + } + $round++; + print "Round $round.\r"; + + last unless $change; + + for @changed.kv -> $idx, $changed_seat { + @seats[$idx] = $changed_seat; + } + } + + my Int $occupied = @seats.comb('#').elems; + say "Part $part: ", $occupied; + + # adjacent-occupied returns the number of adjacent cells that have + # been occupied by others. $visibility_range should be 1 if only + # directly adjacent seats are to be counted. Make it -1 for + # infinite visibility. It ignores floors ('.'). + sub adjacent-occupied ( + Int $idx, Int $visibility_range --> Int + ) { + my Int $occupied = 0; + + for @directions -> $direction { + with @seats[$idx + $direction] { + $occupied++ if $_ eq '#'; + } + } + + # Elements in right corner can't follow @non-right-corner. + unless ($idx + 1) % 10 == 0 { + for @non-right-corner -> $direction { + with @seats[$idx + $direction] { + $occupied++ if $_ eq '#'; + } + } + } + + # Elements in left corner can't follow @non-left-corner. + unless $idx % 10 == 0 { + for @non-left-corner -> $direction { + with @seats[$idx + $direction] { + $occupied++ if $_ eq '#'; + } + } + } + + return $occupied; + } +} +#+END_SRC diff --git a/2020/day-11/day-11.partial.raku b/2020/day-11/day-11.partial.raku new file mode 100755 index 0000000..2f5e48e --- /dev/null +++ b/2020/day-11/day-11.partial.raku @@ -0,0 +1,102 @@ +#!/usr/bin/env raku + +sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +) { + my @input = "input".IO.lines; + my Int $x-max = @input[0].chars - 1; + my Int $row-length = $x-max + 1; + + my @seats = @input.join.comb; + my $max-seats = @seats.end; + + my @directions = (+$row-length, -$row-length); # down, up + + # @non-left-corner contains directions that left corner can't + # follow. It should only be followed by non-left corner seats. + my @non-left-corner = ( + -$row-length - 1, # up-left + -1, # left + +$row-length - 1, # down-left + ); + + # @non-right-corner contains directions that right corner can't + # follow. It should only be followed by non-right corner seats. + my @non-right-corner = ( + -$row-length + 1, # up-right + +1, # right + +$row-length + 1, # down-right + ); + + my Int $round = 0; + loop { + my @changed; + my Bool $change = False; + + INNER: for @seats.kv -> $idx, $seat { + @changed[$idx] = $seat; + given $seat { + when '.' { next INNER; } + when 'L' { + if adjacent-occupied($idx, 1) == 0 { + @changed[$idx] = '#'; + $change = True; + } + } + when '#' { + if adjacent-occupied($idx, 1) >= 4 { + @changed[$idx] = 'L'; + $change = True; + } + } + } + } + $round++; + print "Round $round.\r"; + + last unless $change; + + for @changed.kv -> $idx, $changed_seat { + @seats[$idx] = $changed_seat; + } + } + + my Int $occupied = @seats.comb('#').elems; + say "Part $part: ", $occupied; + + # adjacent-occupied returns the number of adjacent cells that have + # been occupied by others. $visibility_range should be 1 if only + # directly adjacent seats are to be counted. Make it -1 for + # infinite visibility. It ignores floors ('.'). + sub adjacent-occupied ( + Int $idx, Int $visibility_range --> Int + ) { + my Int $occupied = 0; + + for @directions -> $direction { + with @seats[$idx + $direction] { + $occupied++ if $_ eq '#'; + } + } + + # Elements in right corner can't follow @non-right-corner. + unless ($idx + 1) % 10 == 0 { + for @non-right-corner -> $direction { + with @seats[$idx + $direction] { + $occupied++ if $_ eq '#'; + } + } + } + + # Elements in left corner can't follow @non-left-corner. + unless $idx % 10 == 0 { + for @non-left-corner -> $direction { + with @seats[$idx + $direction] { + $occupied++ if $_ eq '#'; + } + } + } + + return $occupied; + } +} diff --git a/2020/day-11/day-11.raku b/2020/day-11/day-11.raku new file mode 100755 index 0000000..00abe6c --- /dev/null +++ b/2020/day-11/day-11.raku @@ -0,0 +1,133 @@ +#!/usr/bin/env raku + +unit sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +); + +my @seats = "input".IO.lines.map(*.comb.cache.Array); +my Int ($x-max, $y-max) = (@seats[0].end, @seats.end); + +my Num $visibility = 1e0; +my Int $tolerance = 4; + +# Infinite visibility & increased tolerance for part 2. +($visibility, $tolerance) = (Inf, 5) if $part == 2; + +my List @directions[8] = ( + # $y, $x + ( +1, +0 ), # bottom + ( +1, +1 ), # bottom-right + ( +1, -1 ), # bottom-left + ( -1, +0 ), # top + ( -1, +1 ), # top-right + ( -1, -1 ), # top-left + ( +0, +1 ), # right + ( +0, -1 ), # left +); + +my Int $round = 0; +loop { + $round++; + print "Round $round.\r"; + + my Int ($x, $y) = (-1, 0); + my @changed; + INNER: loop { + if $x == $x-max { + $x = 0; + # goto next row if not in the last row. + last INNER if $y == $y-max; + $y += 1; + } else { + $x += 1; + } + + @changed[$y][$x] = @seats[$y][$x]; + given @seats[$y][$x] { + when '.' { next INNER; } + when 'L' { + unless adjacent-occupied(@seats, $x, $y, $visibility, True) { + @changed[$y][$x] = '#'; + } + } + when '#' { + if adjacent-occupied(@seats, $x, $y, + $visibility, False) >= $tolerance { + @changed[$y][$x] = 'L'; + } + } + } + } + # If seats didn't change then exit the loop. + last if @seats eqv @changed; + + for 0 .. @changed.end -> $y { + for 0.. @changed[0].end -> $x { + @seats[$y][$x] = @changed[$y][$x]; + } + } +} + +say "Part $part: ", @seats.join.comb('#').elems; + +# adjacent-occupied returns the number of adjacent cells that have +# been occupied by others. +# +# $visibility should be 1 if only directly adjacent seats are to be +# counted. Make it Inf for infinite visibility. It ignores floors +# ('.'). +# +# If $only-bool is set then a Bool will be returned which will +# indicate whether any adjacent seat it occupied or not. +subset Occupied where Int|Bool; +sub adjacent-occupied ( + @seats, Int $x, Int $y, Num $visibility, Bool $only-bool = False + --> Occupied +) { + my Int $occupied = 0; + for neighbors(@seats, $x, $y, $visibility).List -> $neighbor { + if @seats[$neighbor[0]][$neighbor[1]] eq '#' { + return True if $only-bool; + $occupied++ ; + } + } + return $occupied; +} + +# neighbors returns the neighbors of given index. It doesn't account +# for $visibility when caching the results. So, if $visibility changes +# & it has a cached result then the return value might be wrong. So, +# you can't solve both part 1 & 2 at once because $visibility changes +# between the two. This can be solved easily by just accounting for +# $visibility when caching the neighbors. +sub neighbors ( + @seats, Int $x, Int $y, Num $visibility --> List +) { + state Array @neighbors; + + unless @neighbors[$y][$x] { + my Int $pos-x; + my Int $pos-y; + + DIRECTION: for @directions -> $direction { + $pos-x = $x; + $pos-y = $y; + SEAT: for 1 .. $visibility { + $pos-y += $direction[0]; + $pos-x += $direction[1]; + + next DIRECTION unless @seats[$pos-y][$pos-x]; + given @seats[$pos-y][$pos-x] { + # Don't care about floors, no need to check those. + when '.' { next SEAT; } + when 'L'|'#' { + push @neighbors[$y][$x], [$pos-y, $pos-x]; + next DIRECTION; + } + } + } + } + } + + return @neighbors[$y][$x]; +} diff --git a/2020/day-11/input b/2020/day-11/input new file mode 100644 index 0000000..8584e8b --- /dev/null +++ b/2020/day-11/input @@ -0,0 +1,97 @@ +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLL.LL.LLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLL.LLLL.LLLL.LLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLL.LLL.LLLL.LLLLLLLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLLLLLLLLLLL..LLLLLLL..LLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLLLLLLLLLLLLL.LL.LLLLL.LLLLLLLLLLLLLLLLLLLLL..LLLLLLLLLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLLLLLLLL..LLL.LLLLLLLLLLLLLLL.LLLLLLL.LLLLLL.LLLLLLLLLLLLL.L.LL.L..LLLLL.LLLLLLLL +LLLLLLLLL.LLLLLLLLLLL.LLLL.LLL.LLLLL.LLLLLLLL.LL.L.LLLLLL..LL.LLLLLL.LLLL..LLL.LLLLLL.LLLLLL.L +LLLLLLLL..LLLLL.LLLLL.LLLL.LLLLLLLLLLLLLLL.LLLLLLL.LL.LLL.LLLLLLLLLLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLL.LLL..LLLLLL.LL.LLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLL.LLLLLLLLLL +.LLL..L..........L.LL.LL..L..L.....L.....L.....L..L..L....L..L..LL..L.L..L..LLL..LL...L.LLLLL. +.LLLLLLLL.LL.L.LLLLLL.LLL..LLLLLLLLL.LLLLLLLLL.LLL.LLLLLLLLLL.L.L.LLLLLLLLLLLL.LLLLLLLLLLLLLLL +LLL.LLLLL.LLL.L.L.LLLLLLLL.LLLL.LLLL.LLLLLLLL...LL.LLLLLLLLLLLLLL.LLLLLLLLLL.L..LLL..LLLLLLLLL +LLLLLLLLLLLLLLLLLLLLL.L.LL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLL +LLLLLLLLLLLLLLL.LLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LLLLLLLLL. +LLLLLLLLL.LLLLL.LLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLL.L.LLLL.LLLL.LLLLLLLLLL +...LL.L......LL.......LLL...L.LL.LLL.L..L...L.L.LL...L.LLL.....L...L..L......L..LLLL........L. +LLLLLLLLL.LLLLLLLLLLL.LLLL.LLLLLLLLL.LLLLLL.L.LLLL.LL.LL..LLLL.LL.LLLLLLL.LLLL.LLLL..LLLL.LLLL +LLLLLLL.L.LLLLLLLLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLL.LLLL.LLLLLL.LLL +.LL.LLLLL.LLLLLLLLLLL.LLLLLLLLLLLLLL.L.LLLLLL.LLLL.LLL.LL.LLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLL +LLLLLLLLL.LLLLLLLLLLL.LLLL.LLLLLLLL..LLLLLLLL.LLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLL.LLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLL..LLL.LLLLLLLLL.L.LLLLLL.LLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLL.LLLLLLLLLLLL.LL +LLLLLLLLL.LLLL..LLLLL.LLLL.LLLLLLLLLLLLLLL.LL.LLLL.LLLLLL.LL..LLLLLLLLLLL.LLLLLLLLL.LLLLLLLLLL +LL...L.L.LL.L....LL..L..L.L.LL.L..L.L...L.LL..L.L..L....L.....L.L.L.L.......L....L.....L..LLLL +LLLLLLLLL..LLLLLLLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLLLLLLLLL.L.LLLLL.LLLLLL..L.LLLLLLLLLLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLL..LLLLLLLLLLLLLLLLLLL +LLLLLLLLL.LLL.LLLLLL..LLLL.LLLLLLLLL.L.LLLLLL...LL.L.LLL..LLLLLLL.LLLLL.L.LLL.LLLLLLLLLLL.LLLL +LLLLLLLLLLLLLLL.LLLLL.LL.LLLLLLLLLLL.LLL.LLLL.LLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLLLLLL.LLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL +.L..LL.L.L......LL..L..L....LL.LLLLL.L.L.L.....L.L...LLL.LL...LL..L......L....L.LL..L...L.L... +LLLLLLLLL.LLLLL.LLLLL..LLL.LLLLLLLLL.LLLLLLLL.L.LL.LLLLLLLLL.LLLL.LLLLLLL.LLLLLLLLL.LLLLLLLLLL +LLLLLLLLLLLLLLL.LLLLLLLLLL.LLLLLLLLL.LLLLL.LL.LLLL.LLLLLLLLLLLLLL.LLL.LLL.LLLL.LLLL.LLLLLLLLLL +.LLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LL..LLLLLLL.LLLLLLL.LLLLLLL.LLL..LLLL.L.LLLLLLLL +L.LLLLLLL.LLLLL.LLLLL.LLLLLLLLLLLLLL.LLLL.LLL.LL.L.LLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLL.LL +LLLL.LLLLLLLLLL.LLLLL.LLLL.LLLLLLLL..LLLLLLLLLLLLL.LLLLLL.LLL.LLL.L.LLLLLLLLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLLLL.LLL.LL.LLLLLLL.LLLLLLL.LLLLLLLLL.LLLLLLLLLL +L.LLLLLLL.LLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLL.LLL.LLLL.L +LLLLLLLLL.LL.LL.LLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLL.LLLLLL.LLLLL.L.LLLLLLLLLLLL.LLLL.LLLLLLLLLL +LL..L.L.LL..L..L.LLLLL.L.L......L..L.....L..LLL.L...LL.........L...L.........LL...LL...L..L... +L.LLLLLLLLLLL.L.LLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LLLLLLLLLL +LLLLLLLLL..LLLL.LLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLL.LLL.LL.LLLLLLL.LLLLL +LLLLLLL.L.LLLLLLLLLLL.LLLL.LL.LLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLLLLL.LLLLLLL.LLLL +LLLLLLLLL.LLLLL..LLLLLLLLL.LLLLLLLLL.LLLLL.LLLLLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLL.LLLL.LLLLL.LLLL +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLL.LL.LLLLLLLLLLL.LLLLLLL.L.LL.LLLL.LL.LLLLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLLLLLLLLLLLLLL.L.LLLLLL.LLLLLLLLLL.LLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLLLLLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLL.LLLLLL.LLLLLLLLL.LLLLL.LLLLLLLL.LLLLLLLLLLL +...L......L.L...L...L...LL..LL..LLLL..L....LLLL....L...L.L.....LL..LL...LL........LL..L.L...LL +LLLLLLLLLLLLLLL.LLLLL.LLLL.LLLLLLLLL.LL.LLLLL.LLLLLLLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL..LLL.LLLL.L +LLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLLLLLLL.LLLLLLL.LL +LLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LL.LLL.L.LLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLL.LLLLLLLLLL +..L.L..LL.....L....LL.L.L.L..LLL......L..LLL..L..L....LL..L.LLL..L.....LL.L.L...........L..L.. +LLLLLLLLLLLLLL.L.LLLL.LLLL.LL.LLLLLL.LLLLLLL..LLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLL.LLLL.LLLLLL.L.L +.LLLLLLLL.L.LLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLL.LLLLLLLLL.LLLLLLLLLL +LLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLL.LLLLLLLLL.LL.LLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLL. +..LLLLLLL.LLLLLLLLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLL +.L..L..LL..L.L.L.L...L..LL............L..LL..LL.L.L.........LL.....L...L.L.LLL.L.L..........L. +LLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLL..LLLL.LLLLLL.L.LLLLL.LLLLLLL.LLLL.LLLLLLLLLLLLLLL +LLLLLLLLL.LLLLL.L.LLL.LLLL.LLLLLLLLLLLLLLLL.L.LLLL..LLLLLLLLLLLLL.LLLLLLL.LLLL.LL.L.LLLLLL.LLL +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLL.L.LLLLLL.LLLL.LLLL.L.LLLLLLL.LLLLLLLL.LLLLLLLL.LLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLL.LLL.LL.LLLLLLL.LLLLLLL.LLLL.LLLL.L.LLLLLLLL +LLLLLLLLLLLLLLLLLLLLL.LLLL..LL.LLLLLLL.LLLLLL.LLLLLLLLLLL.LL.LLLL.LLLLLLL.LLLLLLLLL.LLLLLLLLLL +LLLLLLLLLLLLLLL.LLLLLLLLLLLL.LLLLLLL.LL.LLLLLLLL.L.LLLLLL.LLLLLLL.LLL.L.LLLLLL.LLLL.LLLLLLLLLL +LLL.LLL.LLLLLLL.LLLLL..LLLLLLLLLLLLL.LLLLLLLLLLLL.LLLL.LL.LLLLLLL.LLLLLL..LLLLLLLLL.LLLLLLLLLL +....L.L..L.L..L....L.L..L............LL.............L......L.L....L....L..L.LL.........LLL..L. +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLL.L.LLLLLLLLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLLLLLLLL.LLLL.LL.LLLLLLLLLLLLLLL.LLLL.LLLLLLLLLLLLLLLLLLLLLL..LLL.LLLL.LLLLLL.LLL +LLLLLLLLL.LLLLL.LL.LLLLLLL.LLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLL.L.LLLLLLL.LLLL.LLLLLLLLLLLLLLL +LLLLLLLLL.LL..LLLLLLLLLLLL.LLLLLLLLLLLLLLLLLL.LLLL.LLLLLLL.LLLLL..LLLLLLL.LLLLLLLLL.LLLLLLL.LL +.LL..L..L..LLL...L..LL.L...LL..L.....L.L...L.L...L.L..L.L........L.L..L.L..L....L.....L..L..LL +LLLLLLLLL.LLLLLLLLLL..LLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLL.LL.L.LL.LLLLLLL +LLLLLLLLL.LLL.L.LLLLLLLLLL.L.LLLLLLLLLLLLLLLLLLLLL.LL.LLL.LLLLLLL.LLLLL.LLL.LL.LLLL.LLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLL.LLLL.LLLLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLLLLL..LL.LLLLLLLLLLLLL.LLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLL.LLLLLLLLLL.LLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LLLLLLLLLL +LLL.LLLLLLLL.LL.LLLLL.LLLL.LLLLLLLL.LLLLLLLLL.LLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLL +..L....L........L....LL..L...LL.L.....L.LL.L..L....L....LL......L.L.....L.L..LL..L.....L.LLL.L +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLL.LLLL.LLLLLLLLLL.LLLL.L.LLLLLLL.LLLLLLLL.LLLL.L.LLLL.LLLLLLLLLLLLLLLLLLLLLLLL..LLLLLLLLLL +LL.LLLLLL.LLLLL.LLL.LL.LLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLL.LLL.LLLLLLLLLLLL.LLLL.LLLLLLLL.L +LLLLLLLLLLLLLLL.LLLLL.LLLL.LLLLLLL.LLLLLLLLLL.LLLLLLLLLLL.LLLLLL.L.LLLLLL.LLLL.LLLL.LLLLLLL.LL +LLL.LLLL..LLLLLLLLLLL.LLLL.LLLLLLLLL..LLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLLLLLLLLLLL.LLLLL..LLLLLLLLLLLLL.LLLLLLLLL.LLL.LLLLLL.LLLLLLL.LLLLLLLLLLLL.LLL..LLLLLLLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL..LLLLLL.LLLLLLLLL.LLLLLLLLLLLLLLLLLL +LLLLLLLLL.LLL.LLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLLL.L.LL.LLLLL.LL.LLLLLLL.LLLLLLLL +LLLLLLLLLLL.LLL.LLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLLLLLLLLLLL.L +...LL.L..L...LL...LLL.........L.L.L..L.....LLLL.LL....L..L...L...LL..L..L......L..LLLL....L..L +LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLL.LLLL.L.LLLLLL.LLLL.LLLL.L.LLL.LLLLLLLLLLL.LLLL.LLLL.LLLLLLLLLL +LLLLL.LLL.LLL.L.LL.LL.LLLL.LLLLLLLLLLLLLLLLLL.LLLL.LLLLLLL.LLLL.L.LLLLLLL..LLL.LLLL.L.LLLLLLLL +LLLLLLLLLLLLL.L.LLLLL.LLLLL.LLLLLLLL.LLLLLLLLLLLLL..LL.L..LLLLLLL.LLLL.LL.LLLL.LLLL.LLLLLLLLLL +LLLLLLLL..LLLLLLLLLLL.L.LLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLLL..LL.LLLLLL.L..LLL.LLLLLLLLLL +LLLLLLLLLLLLLLL.LLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLL.LLLL.L.LLLLLLLL +.L....L.LL...L...LL......LL..........L.LLL...L...L..........L.........LL..L.L.L...L..L........ +LLLLLLLLL.LLLLLLLLL.L.LLLL.LLLLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL..LLLLLLLLL +LLLLLLLLL.LLLLL.LL.LL.LLLL.LLLL.LLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLL +LL.LLLLLL.LLLLL.LLLLL.LLLL.LL.LLLLLL.LLLLL.LL.LLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLL.LLLLL.LLLLLLLLL +LLLLLLLLL.LLLLL.LLLLL.LLLL.LLLLLLLLL.LL.LLLLL.LLLL.LL.LLLLLL.LLLL.LLLLLLL.LLLLLLLLLLLLLLLLL.LL +LLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLLL..LLL.LLLLLL.LLLLLLL.LLLLLLL.LLLL.LL.LLLLLLLLLLLL +LLLLLLLLLL.L.LL.LLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLL.LLLLLL.LLLLLLL.L.LLLLL.LLLL.LLLLLLLLLLLLLLL |