Cycles on the torus

Question

Challenge

This challenge will have you write a program that takes in two integers n and m and outputs the number non-intersecting loops on the n by m torus made by starting at (0,0) and only taking steps up and to the right. You can think of torus as the grid with wraparound both at the top and the bottom and on the sides.

This is code-golf so fewest bytes wins.

Example

For example, if the input is n=m=5, one valid walk is

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3) -> (2,4) -> 
(2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3) -> 
(0,3) -> (1,3) -> (1,4) -> 
(1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3) -> (3,4) -> (4,4) -> 
(0,4) -> (0,0)

as shown in the graphic.

A loop on the torus.

Some example input/outputs

f(1,1) = 2 (up or right)
f(1,2) = 2 (up or right-right)
f(2,2) = 4 (up-up, up-right-up-right, right-right, right-up-right-up)
f(2,3) = 7
f(3,3) = 22
f(2,4) = 13
f(3,4) = 66
f(4,4) = 258

• Arnauld: I was willing to bet that this sequence was on OEIS for at least \$m=n\,ドル but apparently it's not (yet).
• Erik the Outgolfer: I think a torus also has a left-right wraparound. Should we assume it only has up-down wraparound instead? The example image doesn't seem to imply as such.
• Arnauld: @EriktheOutgolfer The image does show the orange path wrapping around from right to left, doesn't it?
• Erik the Outgolfer: @Arnauld Yes, but it doesn't look consistent with the challenge's description ("You can think of torus as the grid with wraparound both at the top and the bottom.")
• Arnauld: @EriktheOutgolfer That's true. And now that you mention it, the blue path is wrong. It should first wraparound from right to left and then from top to bottom.

Answer 1

Python 2, 87 bytes

f=lambda m,n,z=0,l=[]:z==0if z in l else sum(f(m,n,(z+d)%m%(n*1j),l+[z])for d in(1,1j))

Try it online!

The interesting thing here is using a complex number z to store the coordinate of the current position. We can move up by adding 1 and move right by adding 1j. To my surprise, modulo works on complex numbers in a way that lets us handle the wrapping for each dimension separately: doing %m acts on the real part, and %(n*1j) acts on the imaginary part.

• Arnauld: Nicely done. FWIW, my best attempt without using a complex number is 91 bytes in Python 3.8.
• xnor: @Arnauld Interesting idea with the k:=x+y*m. It makes me wonder if it would be shorter to use k directly for (x,y), using x+y*m rather than x+y*1j. Too bad Python 3 doesn't allow complex modulus.
• xnor: @Arnauld 87 bytes: tio.run/##XckxDoIwFIDh3VN0wfTRR0JbBkMsJ@ASGGkkry0NspgYr14lDhaHf/…
• Arnauld: This approach saves 5 bytes in JS. :)

Answer 2

JavaScript (ES6), 67 bytes

This shorter version is derived from a Python 3.8 alternate version found by @xnor. However, this works only for \$m\times n<32\$ in JS.

Takes input as (m)(n).

m=>n=>(g=(k,l)=>l>>k&1?!k:g((k+m)%(m*n),l|=1<<k)+g(k-~k%m-k%m,l))``

Try it online!

To have it work for any input, we could use BigInts for 73 bytes:

m=>n=>(g=(k,l=k)=>l&(b=1n<<k)?!k:g((k+m)%(m*n),l|=b)+g(k-~k%m-k%m,l))(0n)

Try it online!

---

JavaScript (ES6), (削除) 76 73 (削除ここまで) 72 bytes

Takes input as (m)(n).

m=>n=>(g=(x,y)=>g[x+=y*m]?!x:g(-~x%m,y,g[x]=1)+g(x%m,-~y%n)+--g[x])(0,0)

Try it online!

Commented

m => n => ( // m = width; n = height
 g = ( // g is a recursive function taking:
 x, y // the current coordinates (x, y) on the torus
 ) => //
 g[ // the surrounding object of g is also used for storage
 x += y * m // turn x into a key for the current coordinates
 ] ? // if this cell was already visited:
 !x // return 1 if we're back to (0, 0), or 0 otherwise
 : // else:
 g( // first recursive call:
 -~x % m, // move to the right
 y, // leave y unchanged
 g[x] = 1 // mark the current cell as visited by setting the flag g[x]
 ) + // add the result of
 g( // a second recursive call:
 x % m, // restore x in [0...m-1]
 -~y % n // move up
 ) + //
 --g[x] // clear the flag on the current cell
)(0, 0) // initial call to g with (x, y) = (0, 0)

Answer 3

Jelly, 28 bytes

ạƝ§=1Ȧ
2‘p/’ŒPÇƇḢÐṂ%8QƑƇṪÐṂL

A monadic Link accepting a list, [m,n], which yields the count.

TIO-jt1qe1v9 ...although there is little point, it's way too inefficient.
(I can't even run [2,3] locally with 16GB ram)!

How?

Brute force - creates coordinates of a tiled version big enough then filters the power-set of these points to those paths with neighbours only increasing by one in a single direction, then filters to those starting at a minimal coordinate (i.e. the origin) and, at the same time, removes this start coordinate from each. Then uses modulo arithmetic to wrap back to a torus and filters out any containing duplicate coordinates (i.e. those containing intersections) and, finally, filters to those with minimal ending coordinates (i.e. ending back at the origin) and yields the result's length.

ạƝ§=1Ȧ - Link 1: all neighbours differ by 1 in exactly one direction
 Ɲ - for neighbours:
ạ - absolute difference
 § - sum each
 =1 - equal to one (vectorises)
 Ȧ - any and all? (falsey if empty or contains a falsey value when flattened)
2‘p/’ŒPÇƇḢÐṂ%8QƑƇṪÐṂL - Main Link: list of integers, [m,n]
2 - square (vectorises) -> [m*m, n*n]
 ‘ - increment (vectorises) -> [m*m+1, n*n+1]
 / - reduce with:
 p - Cartesian product
 ’ - decrement (vectorises) -> all the coordinates of an m*m by n*n grid
 - including [0, 0] and [m*m, n*n] 
 ŒP - power-set -> all paths going either up OR right at each step, but not
 - necessarily by only 1, and
 - necessarily both up and right (e.g. [...[1,3],[5,7],[6,2],...])
 Ƈ - filter keep those for which:
 Ç - call last Link (1) as a monad
 - ...now all remaining paths do only go in steps
 - of one up or one right
 ÐṂ - filter keep those minimal under:
 Ḣ - head - removes the 1st coordinate from each and yields them for the filter
 - ...so only those which started at [0,0] but without it
 %8 - modulo by the left argument ([m,n]) (vectorises)
 Ƈ - filter keep those for which:
 Ƒ - is invariant when:
 Q - de-duplicated
 - ...so no repetitions of torus coordinates (and we already removed
 - the first [0,0] which must be present exactly twice)
 ÐṂ - filter keep those minimal under:
 Ṫ - tail
 - ...so only those which ended at [0,0] 
 L - length

Answer 4

Haskell, (削除) 88 (削除ここまで) 80 bytes

n#m|let(x!y)a|elem(x,y)a=0^(x+y)|b<-(x,y):a=(mod(x+1)n!y)b+(x!mod(y+1)m)b=0!0$[]

Try it online!

Simple brute force: try all up/right combinations, dropping those which intersect (we keep all positions we've visited in list a) and counting those which eventually hit positition (0,0) again.

The base case of the recursion is when we visit a position a second time (elem(x,y)a). The result is 0^0 = 1 when the position is (0,0) and counts towards the numbers of loops or 0 (0^x, with x non-zero) otherwise and doesn't increase the number of loops.

Edit: -8 bytes thanks to @xnor.

• xnor: The base cases can be combined into |elem(x,y)a=0^(x+y), and (0!0)[] can be 0!0$[].

Answer 5

Jelly, 44 bytes

×ばつƝṪ2*Ḥ_2Rḃ2ドルċⱮØ1⁄2%3¬ẠƲƇịØ.Ṛ,Ø.¤ZÄZ%€ʋ3ドルŒQẠ$€S

Try it online!

Works for 4,4, but has complexity \$O({2^m}^n)\$ so won’t scale that well.

This works by finding all possible routes of up to \$mn\$ length, filtering out those that don’t end at 0,0, and then excluding those that pass the same point twice.

Answer 6

Java 8, 120 bytes

n->m->g(n,m,0,0);int g(int n,int m,int k,int l){return(l>>k)%2>0?k<1?1:0:g(n,m,(k+m)%(m*n),l|=1<<k)+g(n,m,k-~k%m-k%m,l);}

Port of @Arnauld's JavaScript answer, and also only works for inputs where \$n*m<32\$.

Try it online.

Answer 7

CJam (50 chars)

q~]:M:!a{9Yb2/\f{_W=@.+M.%a+_)a#g"WAR"=~}}:R~e_We=

Online demo. This is a program which takes two inputs from stdin.

Finally we have an answer to the question

War, huh, what is it good for?

---

Dissection

q~]:M e# Parse input, collect in array, store in M (for moduli)
:!a e# Zero and wrap in array for starting position (0, 0)
{ e# Define recursive block R
 9Yb2/ e# Push [[1 0][0 1]], an array of movements
 \f{ e# For each of those movements, with the current path,
 _W=@.+ e# Add the movement to the last position in the path
 M.% e# Apply the wrapping
 a+ e# Add to one copy of the path
 _)a# e# And find its index in another copy
 g"WAR"=~ e# Switch on the sign of the index:
 e# If the sign is -1, position not found, make a recursive call
 e# If the sign is 0, found at start, push -1 to the stack
 e# If the sign is 1, we have a self-intersection. We push 10 to
 e# the stack for no other reason than to make the bad joke above
 }
}:R
~ e# Execute R
e_We= e# Count the -1s which we pushed as sentinels

Answer 8

Jelly, (削除) 54 (削除ここまで) 39 bytes

ḣ2æ.2ị3¤+4
‘Ç;\¦%3Ç=4ƊÑÇị$?
çⱮØ1⁄2S
’Ñ0xÇ

Try it online!

I’ve posted this as a separate answer to my other Jelly one because it’s a completely different method. This is closer in principle to @Arnauld’s answer. It uses a recursive function that works through every possible path until it reaches a point it’s already got to, and then returns the result of a check whether it’s back to the start. I suspect a few more bytes could be shaved off. Now changed to using slice operator. It works well for up to 5x5. The recursion depth should be at most m x n.

Answer 9

Python3, 198 bytes

def f(n,m):
 q,c=[(0,0,[(0,0)])],0
 for x,y,p in q:
 if p[1:]and(x,y)==p[0]:c+=1;continue
 if(J:=(x,(y+1)%m))not in p[1:]:q+=[(*J,p+[J])]
 if(K:=((x+1)%n,y))not in p[1:]:q+=[(*K,p+[K])]
 return c

Try it online!

• ceilingcat: 164 bytes