178 lines
4.8 KiB
Forth
178 lines
4.8 KiB
Forth
# Day 3: Toboggan Trajectory
|
|
|
|
With the toboggan login problems resolved, you set off
|
|
toward the airport. While travel by toboggan might be
|
|
easy, it's certainly not safe: there's very minimal
|
|
steering and the area is covered in trees. You'll need
|
|
to see which angles will take you near the fewest trees.
|
|
|
|
Due to the local geology, trees in this area only grow on
|
|
exact integer coordinates in a grid. You make a map (your
|
|
puzzle input) of the open squares (.) and trees (#) you can
|
|
see. For example:
|
|
|
|
..##.......
|
|
#...#...#..
|
|
.#....#..#.
|
|
..#.#...#.#
|
|
.#...##..#.
|
|
..#.##.....
|
|
.#.#.#....#
|
|
.#........#
|
|
#.##...#...
|
|
#...##....#
|
|
.#..#...#.#
|
|
|
|
These aren't the only trees, though; due to something you
|
|
read about once involving arboreal genetics and biome
|
|
stability, the same pattern repeats to the right many times:
|
|
|
|
..##.........##.........##.........##.........##.......
|
|
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
|
|
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
|
|
|
|
You start on the open square (.) in the top-left corner and
|
|
need to reach the bottom (below the bottom-most row on your
|
|
map).
|
|
|
|
The toboggan can only follow a few specific slopes (you opted
|
|
for a cheaper model that prefers rational numbers); start by
|
|
counting all the trees you would encounter for the slope right
|
|
3, down 1:
|
|
|
|
From your starting position at the top-left, check the
|
|
position that is right 3 and down 1. Then, check the position
|
|
that is right 3 and down 1 from there, and so on until you go
|
|
past the bottom of the map.
|
|
|
|
The locations you'd check in the above example are marked here
|
|
with O where there was an open square and X where there was a
|
|
tree:
|
|
|
|
..##.........##.........##.........##.........##.......
|
|
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..
|
|
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#.
|
|
|
|
In this example, traversing the map using this slope would
|
|
cause you to encounter 7 trees.
|
|
|
|
Starting at the top-left corner of your map and following a
|
|
slope of right 3 and down 1, how many trees would you
|
|
encounter?
|
|
|
|
----
|
|
|
|
This will need more memory than a default Retro build has,
|
|
so start by building a version with a much larger memory
|
|
footprint and support for 64-bit cells:
|
|
|
|
make CFLAGS="-DIMAGE_SIZE=8000000 -O2 -DBIT64"
|
|
|
|
I am doing this in a simple way, constructing a large enough
|
|
map that I can just iterate through.
|
|
|
|
Some math.
|
|
|
|
My input file has 323 lines with 31 characters per line. With
|
|
a horizontal distance of 3 per row, the last position will be
|
|
at 969 characters out. So the lines need to be a little over
|
|
31 times longer than they are by default.
|
|
|
|
The easy way to do this is to duplicate the pointer and use
|
|
`s:append` to concat them until I get it long enough. Five
|
|
iterations is plenty, but I'll do a bit more since I suspect
|
|
that I'll need a larger map for the second half.
|
|
|
|
~~~
|
|
:extend (s-s)
|
|
#7 [ dup s:append ] times s:keep ;
|
|
~~~
|
|
|
|
We also need to raise the limit on temporary string size.
|
|
|
|
~~~
|
|
#4096 !TempStringMax
|
|
~~~
|
|
|
|
With this, I can create an array for the inputs:
|
|
|
|
~~~
|
|
'input-day-3 'INPUT s:const
|
|
|
|
(Count_the_number_of_lines)
|
|
#0 INPUT [ drop n:inc ] file:for-each-line
|
|
|
|
(Create_the_array,_and_reserve_space)
|
|
'MAP d:create dup , allot
|
|
|
|
(Fill_in_the_array)
|
|
MAP n:inc INPUT [ extend over store n:inc ] file:for-each-line drop
|
|
~~~
|
|
|
|
Now all that's left is to quickly iterate through it, increasing a
|
|
counter for the horizontal distance.
|
|
|
|
~~~
|
|
#0 #0 MAP [ over + fetch $# eq? [ &n:inc dip ] if #3 + ] a:for-each
|
|
drop n:put nl
|
|
~~~
|
|
|
|
----
|
|
|
|
# Part 2
|
|
|
|
Time to check the rest of the slopes - you need to minimize the
|
|
probability of a sudden arboreal stop, after all.
|
|
|
|
Determine the number of trees you would encounter if, for each
|
|
of the following slopes, you start at the top-left corner and
|
|
traverse the map all the way to the bottom:
|
|
|
|
Right 1, down 1.
|
|
Right 3, down 1. (This is the slope you already checked.)
|
|
Right 5, down 1.
|
|
Right 7, down 1.
|
|
Right 1, down 2.
|
|
|
|
In the above example, these slopes would find 2, 7, 3, 4, and
|
|
2 tree(s) respectively; multiplied together, these produce the
|
|
answer 336.
|
|
|
|
What do you get if you multiply together the number of trees
|
|
encountered on each of the listed slopes?
|
|
|
|
----
|
|
|
|
This is pretty much the same, except for the last one, which
|
|
needs to ignore every other line.
|
|
|
|
I start by just running through each of the trivial slopes,
|
|
reducing down the products.
|
|
|
|
~~~
|
|
'Right var
|
|
|
|
:calculate
|
|
!Right
|
|
#0 #0 MAP [ over + fetch $# eq? [ &n:inc dip ] if @Right + ] a:for-each
|
|
drop ;
|
|
|
|
{ #1 #3 #5 #7 } #1 [ calculate * ] a:reduce
|
|
~~~
|
|
|
|
Then create a new MAP, discarding the odd lines.
|
|
|
|
~~~
|
|
{ #0 MAP [ swap dup n:odd? [ nip ] if n:inc ] a:for-each } 'MAP const
|
|
~~~
|
|
|
|
And finally run through the final slope, multiplying by the
|
|
other products to get the final answer.
|
|
|
|
~~~
|
|
#0 #0 MAP [ over + fetch $# eq? [ &n:inc dip ] if #1 + ] a:for-each
|
|
drop *
|
|
|
|
n:put nl
|
|
~~~
|
|
|