Analyze the flow

Question

On a toroidal square grid (you can wrap around) where each cell indicates one direction (^ > v <) if we pick a cell and start to walk following these directions, we will eventually get stuck in a loop.
We may end up in a different loop, depending on our starting cell.

Not all the cells we encounter constitute our terminal loop: these are said to be tributary to that loop.

Task

Given a square grid configuration, count for each loop \$L_i\$:

• How many cells is it made up with? \$n_i\$
• How many tributary cells does it have? \$t_i\$

Input

You choose the set of 4 printable characters or integers you'll use as directions.

• A square matrix having set elements as entries (can be a string)

Output

• List of \$(n_i,t_i)\$ for each \$L_i\$

The pairs can be in any order.

Example

input urdrurllruuuulrududllurdu

-vivid color: loop
-pale color: tributary
In this configuration there are 3 loops (orange, blue, green) of lengths (2, 2, 6) with (0, 10, 5) tributary cells.

output 6 5 2 10 2 0

Alternative inputs:
    1232124421111421313441231
    [[^,>,v,>,^],[>,<,<,>,^],[^,^,^,<,>],[^,v,^,v,<],[<,^,>,v,^]]

Valid outputs:
    2 10 2 0 6 5
    (2, 10), (6, 5), (2, 0)

Non valid outputs:
    10 2 2 0 6 5
    (0, 2), (10, 2), (6, 5)

This is code-golf, so the shortest code wins.

Answer 1

Java 10, 374 371 364 bytes

import java.util.*;m->{var L=new HashSet<Set>();int l=m.length,R=l*l,r,c,d;for(Set S;R-->0;S.add(r==R/l&c==R%l?-1:-2),L.add(S))for(S=new TreeSet(),r=R/l,c=R%l;S.add(r*l+c);r=(r-(d-d%3*d)/2+l)%l,c=(c-(d<2?1-2*d:0)+l)%l)d=m[r][c];for(Set z:L){if(z.remove(-1)){c=0;for(Set q:L)if(q.remove(-2)){if(q.containsAll(z))c++;q.add(-2);}System.out.println(z.size()+","+c);}}}

-10 bytes thanks to @ceilingcat.

Uses a matrix of integers 0,1,2,3 for <,>,v,^ respectively.

Try it online.

Explanation:

import java.util.*;        // Required import for Set, HashSet, and TreeSet
m->{                       // Method with integer-matrix parameter and no return-type
  var L=new HashSet<Set>();//  Create a Set of Sets `L`, starting empty
  int l=m.length,          //  Set `l` to the dimensions of the input-matrix
      R=l*l,               //  Index integer `R` to loop over the cells
      r,c,                 //  Temp-integers `r,c` for the row and column
      d;                   //  Temp-integer `d` for the direction
  for(Set S;               //  Temp Set `S`, starting uninitialized
      R-->0                //  Loop `R` in the range (`l*l`, 0] over all cells:
      ;                    //     After every iteration:
       S.add(r==R/l&c==R%l?//      If `r,c` is still cell `R`:
              -1           //       Add -1 to Set `S`
             :             //      Else:
              -2),         //       Add -2 instead
       L.add(S))           //      And then add `S` to Set `L`
      for(S=new TreeSet(), //    Set `S` to a new empty sorted-Set
          r=R/l,c=R%l;     //    Set `r,c` to cell `R`
          S.add(r*l+c)     //    Add `r,c` as cell-index to Set `S` every iteration
                           //    and continue looping as long as it wasn't in `S` yet:
          ;                //      After every iteration:
           r=(r-(d-d%3*d)/2//       If `d` is 3:
                           //        Go to the cell above
                           //       Else-if `d` is 2:
                           //        Go to the cell below
              +l)%l        //       Adjust row wraparounds when we're out of bounds
           c=(c-(d<2?1-2*d:0)
                           //       Else-if `d` is 0:
                           //        Go to the cell left
                           //       Else-if `d` is 1:
                           //        Go to the cell right
             +l)%l         //       Adjust column wraparounds when we're out of bounds
        d=m[r][c];         //     Set `d` to the current direction of cell `r,c`
  // After we've determined all paths per cell:
  for(Set z:L){            //  Loop `z` over each path of Set `L`:
    if(z.remove(-1)){      //   Remove a -1 (if present),
                           //   and if it indeed contained a -1 (infinite path):
      c=0;                 //    Use `c` as counter, starting at 0
      for(Set q:L)         //    Inner loop `q` over each path of Set `L`:
        if(q.remove(-2)){  //     Remove a -2 (if present),
                           //     and if it indeed contained a -2 (tributary path):
          if(q.containsAll(z))
                           //      If `q` contains all values of `z`:
            c++;           //       Increase the counter by 1
          q.add(-2);}      //      Add -2 back to `q` for the next iteration of loop `z`
      System.out.println(  //    Print with trailing newline:
        z.size()           //     The size of path `z`
        +","+c);}}}        //     and the counter (comma-separated)

Answer 2

K (ngn/k), 99 81 bytes

thanks @bstrat for -18 bytes!

{l,'(#'.c)-l:#'!c:={x@<x:(x?a@*|x)_x}'{?x,a@x}/'a::s/s!'(+(,/-:\=2)@,/x)+!s:2##x}

Try it online!

down,right,up,left in the input are encoded as 0 1 2 3

Answer 3

Jelly,  44  41 bytes

^{-3 as the grid is guaranteed to be square.}

ŒṪœịı*ÆiƊ+⁸ʋƬ⁺⁹ɗ€⁸%LḞQ€LÞḢṢƲ€¹ƙ$Ẉ€µḟṂLṭṂ)

A monadic Link accepting a list of lists of integers which yields a list of lists of integers (each being a [loop_size, tributary_count] - i.e. \$(n_i, t_i)\$).

The directions in the input are:

^  2
>  1
V  4
<  3

Try it online!

How?

ŒṪœịı*ÆiƊ+⁸ʋƬ⁺⁹ɗ€⁸%L...  - Link: list, X
ŒṪ                       - truthy multi-dimensional indices -> [[1,1],[1,2],...,[h,w]]
                €        - for each:
               ɗ         -   last three links as a dyadic chain:
              ⁹          -     use chain's right argument as right argument
            Ƭ            -     collect up until no change occurs with:
           ʋ             -       last four links as a dyadic chain:
  œị                     -         multi-dimensional index into X
        Ɗ                -         last three links as a monadic chain:
    ı                    -           square root of -1
     *                   -           exponentiate
      Æi                 -           [real part, imaginary part] -> move deltas
          ⁸              -         chain's left argument -> the current position
         +               -         add together -> the new position
             ⁺           -     repeat the Ƭ-collection, use the entire result
                   L     - length of X
                  %      - modulo -> making all results have the same domain

...ḞQ€LÞḢṢƲ€¹ƙ$Ẉ€µḟṂLṭṂ) - ...continued
   Ḟ                     - floor (we had a mix of ints and floats, but ƙ uses
                                  Python's repr, this makes them all ints again)
    Q€                   - deduplicate each
              $          - last two links as a monadic chain:
            ¹ƙ           - group by:
           €             -   for each
          Ʋ              -     last four links as a monadic chain:
       Þ                 -       sort by...
      L                  -       length
        Ḣ                -       head
         Ṣ               -       sorted
               Ẉ€        - length of each of each
                 µ     ) - for each:
                   Ṃ     -   minimum -> loop length
                  ḟ      -   filter discard (keeping only tributary lengths)
                    L    -   length -> number of tributaries
                      Ṃ  -   minimum -> loop length
                     ṭ   -   tack -> [loop length, number of tributaries]

Answer 4

Python 2, 250 247 235 bytes

Thanks Arnauld for pointing out that the grid is guaranteed to be square, saving 12 bytes!

G=input()
n=len(G)
N={}
T={}
t=0
exec"j=t%n;i=t/n;A=[]\nwhile(i,j)not in A:A=[(i,j)]+A;d=G[i][j];i+=d/3-1;j+=d%3-1;i%=n;j%=n\nk=A.index((i,j))+1;x=min(A[:k]);N[x]=k;T[x]=T.get(x,[])+A[k:];t+=1;"*n*n
for x in N:print N[x],len(set(T[x]))

Try it online!

Takes input as a 2D list from STDIN, where up, right, down, left are encoded as the integers 1, 5, 7, 3 respectively.

For each cell in the grid, the program follows the directions starting from that cell until a loop is found. The loop length is stored in the dictionary N, and the list of tributary cells is stored in the dictionary T. The keys for both dictionaries are the min indices of each loop.

Answer 5

JavaScript (Node.js), 196 bytes if width=height

m=>m[Q='flatMap'](U=(y,I)=>y[Q]((x,j)=>U[T=[...m+0,Y=m.length,i=I][Q](_=>0+[j=(c=m[i][j]-2,j+Y-~c%2)%Y,i=(i+Y+c%2)%Y])[k=0,Q](S=c=>(S[c]=-~S[c])==2&&++k&&c).sort()]?(++U[T][0],[]):[U[T]=[1-k,k]]))

Try it online!

JavaScript (Node.js), 205 bytes

m=>m[Q='flatMap'](U=(y,I)=>y[Q]((x,j)=>U[T=[...m+0,Y=m[W='length'],X=m[W],i=I][Q](_=>0+[j=(c=m[i][j]-2,j+Y-~c%2)%Y,i=(i+Y+c%2)%Y]).sort().filter(S=c=>(S[c]=-~S[c])==2)]?(++U[T][1],[]):[U[T]=[k=T[W],1-k]]))

Try it online!

Ungolfed version

m=>m.flatMap(
  U=(y,I)=>y.flatMap(
    (x,j)=>
      U[
        T=[...m+0,Y=m.length,X=y.length,i=I].map(_=>(
          c=m[i][j],c%2?(i=(i+Y-2+c)%Y):(j=(j+X-1+c)%X),
          i*X+j
        )).sort().filter((c,k,S)=>S[k-1]!=c&S[k+1]==c)
      ]?(++U[T][1],[]):[U[T]=[k=T.length,1-k]]
  )
)

Try it online!

Answer 6

J, 78 bytes

[:(#~1<{."1)@((=([,-~)&(+/)0=|)"{~~.)@,](]*.[{"p..0|:((,-)=0 1)|.])^:_ p:@i.@$

Try it online!

How it works

We map each index to the corresponding prime p:@i.@$:

 2  3  5  7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97

Then shift this board by the 4 directions ((,-)=0 1)|.]), and calculate the least common multiple between the tile x and the direction x is heading ]*.[{"p..0|:. We do this until the board does not change anymore (…)^:_:

461677248802 62985        20995    3162172937  3162172937
         221   221         4199 2109169348979 91703015173
        6851  8177       172159       7402837      321997
      363103  4661     10501699    3162172937  3162172937
230838624401  4661 262460353771    3162172937  3162172937

For each unique ~. number we can then count how often it occures and how many other tiles it divides: = …&(1#.,) 0=|. We need the first number and the difference for the result: ([,-~):

…
6  5
2 10
1  5
…
2  0
1  0

We then take only the ones where the first column is greater than 1 (#~1<{."1):

6  5
2 10
2  0

Answer 7

R 435 414 395 390 bytes

Entering the excursion map as a matrix, e.g.

n=3;M=matrix(sample(1:4,n^2,rep=T),n)

where 1,2,3,4 stand for down, up, right, and left, the following heavy-going code produces rows of lengths and tributaries for the different loops

j=cbind;l=sum;a=apply
m=l(!!M);n=m^.5
g=function(A,r=M[A])A+c((r<2)*(1-n*(A[,1]==n))-(r==2)*(1-n*(A[,1]<2)),(r==3)*(1-n*(A[,2]==n))-(r>3)*(1-n*(A[,2]<2)))
I=c()
for(i in d<-1:n)I=rbind(I,j(i*d/d,d))
for(t in b<-1:m)I=g(I)
p=function(i)i[,1]+n*i[,2]-n-1
K=matrix(0,m,m)
for(t in b)K[b+m*p(I<-g(I))]=1
s=o=a(u<-unique(K),1,l)
for(k in 1:l(!!s))s[k]=l(!a(!!sweep(K,2,u[k,],'-'),1,l))
j(o,s-o)

Try it online!

Some comments

m=l(!!M);n=m^.5 #m=n^2
#moving all points in the square by the corresponding moves in M
g=function(A,r=M[A])A+cbind((r<2)*(1-n*(A[,1]==n))-(r==2)*(1-n*(A[,1]<2)),(r==3)*(1-n*(A[,2]==n))-(r>3)*(1-n*(A[,2]<2)))
#matrix of the (i,j) coordinates for all points in the square
I=c()#NULL
for(i in 1:n)I=rbind(I,cbind(rep(i,n),1:n))
#move long enough to remove transient points
for(t in b<-1:m)I=g(I)
#turns 2D coordinates into a single integer 
p=function(i)i[,1]+n*i[,2]-n-1
K=matrix(0,m,m) #matrix of visited coordinates
for(t in b)K[b+m*p(I<-g(I))]=1
#loop length (o) and associated number of transients (s)
s=o=apply(u<-unique(K),1,sum)
#sum over all loops (length(o))
for(k in 1:sum(!!s))s[k]=sum(!a(!!sweep(K,2,u[k,],'-'),1,sum))
cbind(o,s-o)

Now, I spent too much time on this code already but I fear the parts

I=c()
for(i in 1:n)I=rbind(I,cbind(rep(i,n),1:n))

creating the matrix of all starting coordinates and

p=function(i)i[,1]+n*i[,2]-n-1

switching from the coordinates to a single index could be further code-golfed!

Answer 8

Scala, 415 bytes

415 bytes, maybe more. It can be golfed much more.

Port of @Kevin Cruijssen' Java 10 answer in Scala.

---

Golfed version. Try it online!

val L=new HashSet[Set[Int]]()
val l=m.length
val R=l*l
for(i<-0 until R){var r=i/l
var c=i%l
val S=new TreeSet[Int]()
do{S.add(r*l+c)
val d=m(r)(c)
r=(r-(d-d%3*d)/2+l)%l
c=(c-(if(d<2)1-2*d else 0)+l)%l}while(S.add(r*l+c))
if(r==i/l&&c==i%l)S.add(-1)else S.add(-2)
L.add(S)}
for(z<-L.asScala){if(z.remove(-1)){var c=0
for(q<-L.asScala){if(q.remove(-2)){if(q.containsAll(z))c+=1
q.add(-2)}}
println(s"${z.size},$c")}}

Ungolfed version. Try it online!

import java.util.{HashSet, TreeSet, Set}
import scala.collection.JavaConverters._

object Main {

  trait N {
    def c(m: Array[Array[Int]]): Unit
  }

  val n: N = new N {
    def c(m: Array[Array[Int]]): Unit = {
      val L = new HashSet[Set[Int]]()
      val l = m.length
      val R = l * l
      
      for (i <- 0 until R) {
        var r = i / l
        var c = i % l
        val S = new TreeSet[Int]()
        do {
          S.add(r * l + c)
          val d = m(r)(c)
          r = (r - (d - d % 3 * d) / 2 + l) % l
          c = (c - (if (d < 2) 1 - 2 * d else 0) + l) % l
        } while (S.add(r * l + c))
        if (r == i / l && c == i % l) S.add(-1) else S.add(-2)
        L.add(S)
      }

      for (z <- L.asScala) {
        if (z.remove(-1)) {
          var c = 0
          for (q <- L.asScala) {
            if (q.remove(-2)) {
              if (q.containsAll(z)) c += 1
              q.add(-2)
            }
          }
          println(s"${z.size},$c")
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {
    test(Array(Array(3, 1, 2, 1, 3), Array(1, 0, 0, 1, 3), Array(3, 3, 3, 0, 1), Array(3, 2, 3, 2, 0), Array(0, 3, 1, 2, 3)))
    test(Array(Array(1, 2), Array(3, 0)))
    test(Array(Array(1, 2, 2), Array(3, 0, 0), Array(1, 0, 2)))
  }

  def test(m: Array[Array[Int]]): Unit = {
    println(s"Input: ${m.map(_.mkString(",")).mkString("Array(", ", ", ")")}")
    println("Pretty-printed: ")
    prettyPrint(m)
    println("Output: ")
    n.c(m)
    println()
  }

  def prettyPrint(m: Array[Array[Int]]): Unit = {
    for (r <- m) {
      println(r.map(v => "<>v^".charAt(v)).mkString)
    }
  }
}