20
2
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.
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
1I was willing to bet that this sequence was on OEIS for at least $m=n$, but apparently it's not (yet). – Arnauld – 2019-03-09T09:24:56.550
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. – Erik the Outgolfer – 2019-03-09T11:12:39.220
@EriktheOutgolfer The image does show the orange path wrapping around from right to left, doesn't it? – Arnauld – 2019-03-09T11:19:53.190
@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.") – Erik the Outgolfer – 2019-03-09T11:20:59.793
@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. – Arnauld – 2019-03-09T11:24:39.293
I'm confused.
f(1,1)
should also admit "up-right" and "right-up" as paths, for a total of4
, and there are plenty of other paths in the other examples that seem like they exist but aren't listed. – imallett – 2019-03-09T18:56:25.367@imallett, for
f(1,1)
, starting at(0,0)
and taking a step up places you at(0,1) = (0,0)
, completing the loop. Your suggestion of "up-right" would return you to(0,0)
after the first step and again after the second step (two concatenated loops). – Peter Kagey – 2019-03-09T19:01:03.513i really like the idea of this puzzle but im super confused. on 2x2 for example... do the loops you get by "shifting" the starting point not count? i would imagine there were three different "up-up" paths that would be loops on a torus. thanks. – don bright – 2019-03-10T01:00:02.270
Always start at (0,0). So loops you get by shifting the starting point don’t count. – Peter Kagey – 2019-03-10T02:32:06.730
I'm a little confused, what counts as a loop? In the shown image I can only see one loop, but we could easily make a bunch of loops, but they would always intersect since we need to start at 0,0. It seems like we care more about the length of one loop? But I can't figure out what we want even with the tests. – Post Rock Garf Hunter – 2019-03-11T21:03:45.570
We want exactly one (non-intersecting) loop starting at (0,0). That is the coordinates only equal (0,0) on the first and last step and are all distinct in the middle. – Peter Kagey – 2019-03-11T21:15:57.797