# Analyze the flow

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.

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 , so the shortest code wins.

• I know you've stated "character", but could our inputs be integers? How about allowing pairs (e.g. '^' as (1,0), < as (-1,0), etc.) to? What about complex numbers (probably a useful one here)? May 13, 2020 at 16:26
• @Jonathan Allan The input would be too exploitable and also detrimental to the "easy-to-use" feature... One character should be sufficent to directly using it in the program. I can think (1,2,3,6) so only 2 test are needed (%2 and %3). Are integers implied in "printable characters"? May 13, 2020 at 17:11
• Integers are not printable characters, although some languages (or implementations thereof) will implicitly interpret the digits as integers. May 13, 2020 at 17:12
• @Jonathan Allan Ok, I've added them, thanks! May 13, 2020 at 17:16
• Nice challenge. What's the explanation of your avatar? May 14, 2020 at 4:11

# Java 10, 374371 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:
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)

• Nice. Just out of curiosity, why did you decide to do this one in Java? May 14, 2020 at 4:08
• @Jonah The languages I'm most skilled in are Java, 05AB1E, and Whitespace. And usually when I deem a challenge relatively hard, I will use Java. I'll try it later on in 05AB1E as well, but 05AB1E isn't too great for matrices or checking/going to a certain neighbor in a matrix. But we'll see when I have some time to work on it how well it really does I guess. ;) May 14, 2020 at 6:39

# 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

• Sorry, function argument should only be the matrix configuration May 13, 2020 at 20:42
• @DomenicoModica i assumed dimensions+data is a valid representation of a matrix. i'll fix later.
– ngn
May 14, 2020 at 6:30
• fixed. it's a single arg now - the matrix split into rows.
– ngn
May 14, 2020 at 8:54
• Perfect. Awesome answer! May 14, 2020 at 9:31

# 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]  # 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. # 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! • The grid is guaranteed to be square, so you don't need X. May 14, 2020 at 8:31 • @Arnauld Beat you considering rectangle – l4m2 May 14, 2020 at 9:49 # J, 78 bytes [:(#~1<{."1)@((=([,-~)&(+/)0=|)"{~~.)@,](]*.[{"p..0|:((,-)=0 1)|.])^:_ p:@i.@$


Try it online!

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  # R435 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! # 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)
}
}
}