# Wraps and Loops—Which Sequences are Admissible?

If you take a non-intersecting closed loop on a torus (that is to say, a path which ends where it starts and does not cross over itself, drawn inside a square whose edges "wrap" left to right and top to bottom), you can use it to infinitely tile the plane in a lined pattern:

Example loop (w/ basepoint), and the corresponding tiling in the plane

Moreover, if we take our basepoint and follow the path produced on the plane diagram until we hit a basepoint once again, we find that we move through a series of tiles, perhaps not ending up where we started:

Extracting the arrow sequence from the loop (w/ given basepoint and travel direction)

In this way, we say that the sequence ↑←↓↓←↑→↓ is admissible. However, not all sequences of arrows can be produced this way; a diagram producing the sequence simply cannot be drawn. Those sequences are called inadmissible. Can you find an effective means for determining if a provided sequence is admissible or inadmissible?

Here are some example cases to get you started (which your algorithm should correctly label as admissible or inadmissible):

1. ↓←→↓↑→←↓
2. ↑↑↑→↑←
3. ↑↑↓→←↑→↑→

UPDATE: As a reference I've written a super dumb brute force algo which just tries all possible permutations of the horizontal and vertical boundary crossings.

Here are the results for the four test cases:

End of UPDATE.

Note: The core of the algorithm is still rather sketchy, so this may be regarded as a partial answer.

Sketch of decision "algorithm":

     input: ULDDLURD
1) form pairs, wrapping around: UL,LD,DD,DL,LU,UR,RD,DU
if both UU and LL occur return FALSE
pool U,D->V and L,R->H and for each try to find an
ordering such that
for all pairs made in (1,2) the following is satisfied
if there are two pairs U1L1,U2L2 then U1<U2 <=> L1<L2
and similar for DR
if there are two pairs L1D1,L2D2 then L1<L2 <=> D1>D2
and similar for RU
if there are two pairs U1U2,U2U3 then U1<U2 <=> U2<U3
and similar for LL
for any pair U1D1 (or D1U1) all V such that U1<V<D1 are
also part of a UD (or DU) pair
and similar for LR (or RL)
for any two pairs U1L1,L2D2 we have L2>L1
and similar for R1U1,U2L2, for R1U1,U2U3,
for U1U3,U2L2, for U1L1,L2L3 and for L1L3,L2D2
for any two pairs D1R1,R2U2 we have R2<R1
and similar for L1D1,D2R2, for L1D1,U3U2,
for U3U1,D2R2, for D1R1,R3R2 and for R3R1,R2U2
return TRUE if such two orderings exists otherwise
return FALSE


Remarks:

1. The orderings in the algorithm, of course, directly correspond to the (spatial) order of crossings along tile boundaries
2. The rules spelt out are just a rundown of what needs to hold so no segments cross
3. Admittedly, the actual algorithmic test for/construction of the orderings is a challenge in itself.

• The first thing I don't understand is where the pairs from "discard direction" are coming from, or what "pool U,D->V and L,R->H" mean. I'll give you the same test case (not already elaborated by diagrammatic example) that I gave Vicky: What does your algorithm say about ↓←→↓↑→←↓? Is it admissible or inadmissible? Apr 24, 2021 at 21:15
• @Feryll, U,D->V means up,down->vertical. They naturally pool because they both are crossings of the horizontal tile boundary. Similarly, if we discard direction then for example UL and RD are the same, they describe the same class of trajectories backward or forward. I'm pretty sure algo says no to your new example because a pair of orderings with the necessary properties does not exist. I'll try and rephrase a bit to hopefully make things a bit clearer. Apr 24, 2021 at 21:54
• Here are another couple of test cases, if you're interested: ↑↑↑→↑← and ↑↑↓→←↑→↑→ Apr 25, 2021 at 2:20
• @Feryll Actually, I'm beginning to think that I have only reformulated but not really solved the problem... Apr 25, 2021 at 3:15
• If you can describe an algorithm that at least terminates in finite time on every input and correctly answers "admissible" or "inadmissible," then I would probably wind up accepting the answer. However, ideally I would like either a polynomial time solution, or a proof that the problem is NP-hard. Apr 25, 2021 at 4:09