13
\$\begingroup\$

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2020 Day 3.


On the way to vacation, you're traveling through a forest on an airplane. For some biological and geological reasons, the trees in this forest grow only at the exact integer coordinates on a grid, and the entire forest repeats itself infinitely to the right. For example, if the map (input) looks like this (# for trees and . for empty spaces):

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

the forest actually looks like this:

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

Starting at the top-left corner of this forest and moving at a rational slope (e.g. 3/2 represents two units to the right and 3 units down), how many trees will you encounter until you escape the forest through the bottom row? (You encounter a tree if your path goes through the exact integer coordinates of that tree.)

Input: A rectangular grid representing the map, and a rational number (non-zero, non-infinity) representing the slope of your movement. You can use any two distinct values (numbers/chars) to represent trees and empty spaces respectively. You can take two positive integers for the slope instead of a rational number, and the two numbers are guaranteed to be coprime.

Output: The number of trees you will encounter during the flight.

Standard rules apply. The shortest code in bytes wins.

Test cases

Grid:
.##
#.#
##.
down/right -> trees
1/1 -> 0
99/1 -> 0
2/1 -> 1
2/3 -> 1
1/2 -> 2
1/3 -> 2
1/99 -> 2

Grid:
##.#
.###
##..
..##
down/right -> trees
1/1 -> 3
1/2 -> 4
1/3 -> 2
2/3 -> 1
3/4 -> 1

Grid: (the one shown at the top)
down/right -> trees
1/1 -> 2
1/3 -> 7
1/5 -> 3
1/7 -> 4
2/1 -> 2
\$\endgroup\$
9
  • \$\begingroup\$ Could you add a test case where the top left corner contains a tree? \$\endgroup\$
    – DLosc
    Dec 21, 2021 at 0:23
  • 1
    \$\begingroup\$ Can we take the transposition of the grid as input? I.e. an array of columns, instead of an array of rows \$\endgroup\$
    – tjjfvi
    Dec 21, 2021 at 1:07
  • \$\begingroup\$ @tjjfvi No, it is not allowed. \$\endgroup\$
    – Bubbler
    Dec 21, 2021 at 1:29
  • 1
    \$\begingroup\$ Duplicate? (the shortest [Jelly] answer to that transplants directly here...) \$\endgroup\$ Dec 21, 2021 at 21:01
  • 2
    \$\begingroup\$ Should we dupe this one to that one or do reverse? \$\endgroup\$
    – tsh
    Dec 22, 2021 at 1:22

15 Answers 15

7
\$\begingroup\$

JavaScript (Node.js), 51 bytes

(a,x,y)=>a.map((r,i)=>t+=r[i*x/y%r.length]|0,t=0)|t

Try it online!

Input an 2d 0/1 array where 1 means tree, and step x, y.

Use the fact that you can index an array with non-integer value without causing errors in JavaScript. You will get non-harmful undefined which may be convert to 0 safely by any bitwise operator. And as you are keeping moving south, you may only encounter at most 1 tree each row. So we just sum all tree encountered each row. And that's all we need to make it working.

\$\endgroup\$
4
\$\begingroup\$

Whython, 59 57 bytes

f=lambda F,a,b,x=0:F[a-1][x%len(F[0])]+f(F[a:],a,b,x+b)?0

Attempt This Online!

Inputs a 2D array of booleans, and 2 integers.

Normal Python, 69 bytes

f=lambda F,a,b,x=0:F[a-1:]>[]and F[a-1][x%len(F[0])]+f(F[a:],a,b,x+b)

Attempt This Online!

\$\endgroup\$
2
  • \$\begingroup\$ Why Whython when Python is shorter :P \$\endgroup\$
    – Bubbler
    Dec 21, 2021 at 0:50
  • \$\begingroup\$ @Bubbler Ython? \$\endgroup\$
    – pxeger
    Dec 21, 2021 at 0:51
3
\$\begingroup\$

Haskell, 60 bytes

f g a b=sum[cycle(g!!(a*t))!!(b*t)|t<-[0..div(length g-1)a]]

Try it Online!

Takes input as a list of lists, followed by the down and right numbers. Trees are represented as 1s, blanks spaces are represented by 0s.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ First Haskell answer for AoCG2021! \$\endgroup\$
    – alephalpha
    Dec 21, 2021 at 2:15
3
\$\begingroup\$

Jelly,  11  10 bytes

-1 thanks to Dominic van Essen (Avoid multi-link chaining by getting the m-slice result again when needed.)

mJ’×⁵‘ị"mS

A full program accepting a list of lists of 1s (trees) and 0s (clearings), the Down amount, and the Right amount that prints the result.

Try it online!

How?

mJ’×⁵‘ị"mS - Main Link: Map, Down (Right is the third program argument)
m          - modular slice Map's rows using Down
              -> list of the rows on which we could hit trees
 J         - range of length -> [1, 2, 3, ..., length of slice result]
  ’        - decrement -> [0, 1, 2, ..., n-1]
    ⁵      - program's third argument, Right
   ×       - multiply -> [0, Right, 2×Right, ..., (n-1)×Right]
     ‘     - increment -> [1, Right+1, 2×Right+1, ..., (n-1)×Right+1
        m  - modular slice Map's rows using Down
       "   - zip with (f(value, row) for row in m-slice result):
      ị    -   index into that row
         S - sum
\$\endgroup\$
2
  • \$\begingroup\$ This seems to be 1 byte shorter. No idea how it works, though... \$\endgroup\$ Dec 21, 2021 at 21:07
  • \$\begingroup\$ Thanks @DominicvanEssen, changed mine using what saves the byte (getting the result of m again when needed to avoid chaining quicks). \$\endgroup\$ Dec 21, 2021 at 22:11
2
\$\begingroup\$

Pip, 29 bytes

g@>:2Wy<#g{i+:g@y@xy+:ax+:b}i

Full program; takes dy, dx, and each row of the grid as arguments. The grid should use 0 for no tree and 1 for tree. Try it online!

Explanation

g@>:2Wy<#g{i+:g@y@xy+:ax+:b}i
                               For our purposes, y, x, & i can be considered to start at 0
g                              List of arguments
 @>:2                          Remove the first two
                               g is now just the grid
     Wy<#g{                }   While y coordinate is less than number of rows in g:
              g@y@x             Get the value (1 or 0) at coordinates (x,y) in g
                                (using cyclical indexing)
           i+:                  Add it to running total i
                   y+:a         Increment y by first program argument
                       x+:b     Increment x by second program argument
                            i  After the loop, autoprint the number of trees encountered
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 57 bytes

Expects (grid, dy, dx), where grid is a binary matrix.

(G,v,h)=>(g=y=>(r=G[y])?r[x%r.length]+g(y+v,x+=h):0)(x=0)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 45 bytes

(a,b,c)->sum(i=0,(#a-1)/b,a[b*i+1,c*i%#a~+1])

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Rust, 80 bytes

|i:&[Vec<_>],a,b|i.iter().step_by(b).fold((0,0),|(x,t),v|(x+a,t+v[x%v.len()])).1

Try it online!

Takes input as a slice of vectors of ones and zeroes.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 56 ... 51 bytes

->v,y,x{z=0;v.each_slice(y).sum{|l,|(l*z+=x)[z-x]}}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python, 57, 54 bytes (@GB)

lambda a,y,x,i=0:sum((r*(i:=i+x))[i-x]for r in a[::y])

Attempt This Online!

Old version

lambda a,y,x,i=0:sum(r[(i:=i%len(r)+x)-x]for r in a[::y])

Attempt This Online!

Expects a list of lists of 0s and 1s plus two integers.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ @JonathanAllan I thought of that but x=y=1 and a taller than wide forest looks like a counter example to me. I think to get this approach right one cannot avoid using a len at some point. \$\endgroup\$
    – loopy walt
    Dec 21, 2021 at 4:33
  • \$\begingroup\$ You're right I'm thinking of height * width of forrest :( \$\endgroup\$ Dec 21, 2021 at 4:34
  • \$\begingroup\$ 54 bytes \$\endgroup\$
    – G B
    Dec 21, 2021 at 13:05
  • \$\begingroup\$ @GB NIce one! I was toying with the idea but couldn't get it to work. Kinda cool that that annoying +x-x can be made to pay for itself that way. \$\endgroup\$
    – loopy walt
    Dec 21, 2021 at 15:11
2
\$\begingroup\$

05AB1E, 15 9 bytes

ιнε³N*è}O

-6 bytes, by using the exact same program as @ovs' used in the related challenge.. :/ (thanks for letting me know @DominicVanEssen)

Takes the inputs in the order \$right\$, \$grid\$, \$down\$, where \$grid\$ is a matrix of 0 for empty spots and 1 for trees.

Try it online or verify all test cases.

Explanation:

ι          # Uninterleave the second (implicit) input-matrix with the first (implicit)
           # input right-slope as step-size
 н         # Only leave the first inner matrix
  ε        # Map over each row:
   ³       #  Take the third input down-slope
    N*     #  Multiply it by the 0-based map-index
      è    #  Use it to 0-based modular index into the row
  }        # After the map:
   O       # Sum the list together to get the amount of trees encountered
           # (which is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 6 bytes shorter...? \$\endgroup\$ Dec 21, 2021 at 21:10
  • 1
    \$\begingroup\$ @DominicvanEssen Thanks. Hadn't even looked at the related challenge.. Funny how it's literally the EXACT same. :/ \$\endgroup\$ Dec 21, 2021 at 21:36
1
\$\begingroup\$

TypeScript Types, 298 bytes

//@ts-ignore
type a<T,N=[]>=T extends N["length"]?N:a<T,[...N,{}]>;type b<T,N>=N extends[{},...infer M]?T extends[infer A,...infer U]?b<[...U,A],M>:0:T;type M<G,Y,X,N=[],>=G extends[]?N["length"]:M<{[K in keyof G]:b<G[K],a<X>>}extends[...a<Y>,...infer Rest]?Rest:[],Y,X,G[0][0]extends 1?[...N,0]:N>

Try It Online!

Ungolfed / Explanation

// Convert a number literal to a tuple of {} of equal length
type NumToTopTuple<T,N=[]> = T extends N["length"] ? N : NumToTopTuple<T,[...N,{}]>

// Cycles a non-empty tuple T to the left N times
type CycleLeft<T, N> = N extends [{}, ...infer M] ? T extends [infer A, ...infer U] ? CycleLeft<[...U,A],M> : 0 : T

type Main<
  Grid,
  Y,
  X,
  Trees=[],
> =
  Grid extends []
    // If there are no more rows left, return Trees
    ? Trees["length"]
    // Otherwise, recurse:
    : Main<
      // Map over Grid and cycle its rows X times to the left. Then, remove the first Y rows
      {
        [K in keyof Grid]: CycleLeft<Grid[K], NumToTopTuple<X>>
      } extends [...NumToTopTuple<Y>, ...infer Rest] ? Rest : [],
      Y,
      X,
      // If there's a tree at (0,0), increment Trees
      Grid[0][0] extends 1 ? [...Trees, 0] : Trees
    >
\$\endgroup\$
1
\$\begingroup\$

R, 68 bytes

function(g,d,r,n=1:(nrow(g)/d)-1)sum(g[1+cbind(n*d,(n*r)%%ncol(g))])

Try it online!

Ungolfed

ntrees=function(g,d,r)  # ntrees = function with arguments
                        # g = grid, d = down, r = right
 n=1:(nrow(g)/d)-1      # first calculate n = 0 ... number of moves we'll make
                        # (number of moves is rounded-down to an integer)
 sum(                   # now calculate the sum of all trees 
  g[                    # at positions of g given by
   1+                   # 1+ = R uses 1-based indexing
    cbind(              # cbind = combind 2 vectors, to use as 2d indices to a matrix
     n*d,               # x-coordinates are just d * n
     (n*r)%%ncol(g))])  # y-coordinates are r * n, modulo the number of columns in g
\$\endgroup\$
0
\$\begingroup\$

Python3, 84 bytes:

f=lambda b,d,r,y=1,x=1:0if y-1>=len(b)else(b[y-1][(x-1)%len(b[0])]+f(b,d,r,d+y,r+x))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 24 bytes

NθNηWS⊞υιI№E✂υ⁰Lυθ§ι×ηκ#

Try it online! Link is to verbose version of code. Takes input as an array of newline-terminated strings. Explanation:

NθNη

Input the slope as two positive integers y and x.

WS⊞υι

Input the grid.

I№E✂υ⁰Lυθ§ι×ηκ#

Take every yth element of the grid, and from those rows, take every xth element respectively. Count how many of them are #s.

\$\endgroup\$
2
  • \$\begingroup\$ 21 bytes by using your exact† answer here? †: well, almost exact.. The integer inputs are in reversed order. \$\endgroup\$ Dec 21, 2021 at 21:46
  • 1
    \$\begingroup\$ @KevinCruijssen The grid size is hard-coded in that answer. \$\endgroup\$
    – Neil
    Dec 21, 2021 at 22:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.