24
\$\begingroup\$

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

grid with colored regions
-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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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)? \$\endgroup\$ – Jonathan Allan May 13 at 16:26
  • \$\begingroup\$ @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"? \$\endgroup\$ – Domenico Modica May 13 at 17:11
  • 1
    \$\begingroup\$ Integers are not printable characters, although some languages (or implementations thereof) will implicitly interpret the digits as integers. \$\endgroup\$ – Jonathan Allan May 13 at 17:12
  • 1
    \$\begingroup\$ @Jonathan Allan Ok, I've added them, thanks! \$\endgroup\$ – Domenico Modica May 13 at 17:16
  • 1
    \$\begingroup\$ Nice challenge. What's the explanation of your avatar? \$\endgroup\$ – Jonah May 14 at 4:11
10
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice. Just out of curiosity, why did you decide to do this one in Java? \$\endgroup\$ – Jonah May 14 at 4:08
  • 2
    \$\begingroup\$ @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. ;) \$\endgroup\$ – Kevin Cruijssen May 14 at 6:39
5
\$\begingroup\$

K (ngn/k), 99 bytes

{l,'@[&*/s;c;+;1][h]-l:#'c h:*'?c:{x@<x:(x?a@*|x)_x}'{?x,a x}'/a::s/s!'(+(,/-:\|:\!2)@,/x)+!s:2##x}

Try it online!

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

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]
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ The grid is guaranteed to be square, so you don't need X. \$\endgroup\$ – Arnauld May 14 at 8:31
  • \$\begingroup\$ @Arnauld Beat you considering rectangle \$\endgroup\$ – l4m2 May 14 at 9:49
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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