| Bytes | Lang | Time | Link |
|---|---|---|---|
| 456 | Python3 | 250310T224609Z | Ajax1234 |
| 415 | Scala | 230810T092731Z | 138 Aspe |
| 081 | K ngn/k | 200513T201437Z | ngn |
| 078 | J | 210118T224813Z | xash |
| 390 | R | 200519T075320Z | Xi'a |
| 196 | JavaScript Node.js | 200514T050047Z | l4m2 |
| 364 | Java 10 | 200513T175850Z | Kevin Cr |
| 041 | Jelly | 200513T203952Z | Jonathan |
| 235 | Python 2 | 200513T204006Z | Surculos |
Python3, 456 bytes
E=enumerate
def f(m):
u=int(len(m)**.5)
m=[m[i:i+u]for i in range(0,len(m),u)]
Q={(x,y)for x,r in E(m)for y,v in E(r)}
def M(x,y):J,K=[(-1,0),(0,1),(1,0),(0,-1)][int(m[x][y])-1];return(x+J)%u,(y+K)%u
W=[]
while Q:
(x,y),*Q=Q;D={(x,y):1}
while D[(x,y)]<3:x,y=M(x,y);D[(x,y)]=D.get((x,y),0)+1
while 1:
Q,F={*Q}-{*D},1
for x,y in Q:
if M(x,y)in D:D[(x,y)]=1;F=0
if F:
I=[0,0]
for i in D:I[D[i]<2]+=1
W+=[I];break
return W
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)
}
}
}
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}
down,right,up,left in the input are encoded as 0 1 2 3
J, 78 bytes
[:(#~1<{."1)@((=([,-~)&(+/)0=|)"{~~.)@,](]*.[{"p..0|:((,-)=0 1)|.])^:_ p:@i.@$
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
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)
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!
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]]))
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]]))
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]]
)
)
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.
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)
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
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]))
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.