10
$\begingroup$

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:

enter image description here 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:

enter image description here 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. ↑↑↓→←↑→↑→
$\endgroup$
2
$\begingroup$

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:

enter image description here

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
     2) discard direction: UL,LD,UU,RU,DR,LD,UL,UD
     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.

$\endgroup$
13
  • $\begingroup$ 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? $\endgroup$
    – Feryll
    Apr 24 at 21:15
  • $\begingroup$ @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. $\endgroup$
    – loopy walt
    Apr 24 at 21:54
  • $\begingroup$ Here are another couple of test cases, if you're interested: ↑↑↑→↑← and ↑↑↓→←↑→↑→ $\endgroup$
    – Feryll
    Apr 25 at 2:20
  • $\begingroup$ @Feryll Actually, I'm beginning to think that I have only reformulated but not really solved the problem... $\endgroup$
    – loopy walt
    Apr 25 at 3:15
  • $\begingroup$ 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. $\endgroup$
    – Feryll
    Apr 25 at 4:09

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.