AoCG2021 Day 21: Blinking through the forest [duplicate]

Question

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 code-golf 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

Answer 1

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.

Answer 2

Whython, ⁵⁹ 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!

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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!

Answer 7

Pari/GP, 45 bytes

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

Try it online!

Answer 8

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.

Answer 9

Ruby, 56 ... 51 bytes

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

Try it online!

Answer 10

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.

Answer 11

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)

Answer 12

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
    >

Answer 13

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

Answer 14

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!

Answer 15

Charcoal, 24 bytes

ＮθＮηＷＳ⊞υιＩ№Ｅ✂υ⁰Ｌυθ§ι×ηκ#

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

ＮθＮη

Input the slope as two positive integers y and x.

ＷＳ⊞υι

Input the grid.

Ｉ№Ｅ✂υ⁰Ｌυθ§ι×ηκ#

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