25
\$\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\$
6
  • 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\$ May 13 '20 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
    May 13 '20 at 17:11
  • 1
    \$\begingroup\$ Integers are not printable characters, although some languages (or implementations thereof) will implicitly interpret the digits as integers. \$\endgroup\$ May 13 '20 at 17:12
  • 1
    \$\begingroup\$ @Jonathan Allan Ok, I've added them, thanks! \$\endgroup\$
    – Domenico
    May 13 '20 at 17:16
  • 1
    \$\begingroup\$ Nice challenge. What's the explanation of your avatar? \$\endgroup\$
    – Jonah
    May 14 '20 at 4:11
11
\$\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)
\$\endgroup\$
2
  • \$\begingroup\$ Nice. Just out of curiosity, why did you decide to do this one in Java? \$\endgroup\$
    – Jonah
    May 14 '20 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\$ May 14 '20 at 6:39
7
\$\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!

\$\endgroup\$
4
  • \$\begingroup\$ Sorry, function argument should only be the matrix configuration \$\endgroup\$
    – Domenico
    May 13 '20 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 '20 at 6:30
  • 1
    \$\begingroup\$ fixed. it's a single arg now - the matrix split into rows. \$\endgroup\$
    – ngn
    May 14 '20 at 8:54
  • \$\begingroup\$ Perfect. Awesome answer! \$\endgroup\$
    – Domenico
    May 14 '20 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]
\$\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.

\$\endgroup\$
0
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!

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

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
\$\endgroup\$
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!

\$\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.