13
\$\begingroup\$

Dedicated to Martin Gardner, taken from his book

Background

In the old days, the Slavs had a divination method for finding out whether a girl would get married. The girl would clutch six straws in her hand so that the ends would poke out the top and bottom of her fist. Then her friend would join together the ends of pairs of straws, first at the top and then at the bottom. If after all ends had been joined, the straws formed a single cycle/loop, then the girl would get married.

enter image description here

Goal of challenge

Given the number of straws \$N\$ and the binding scheme (how the ends of the straws are tied together), determine whether the straws form a single cycle/loop. In the scheme, every straw is described with a unique index from \$1\$ to \$N\$.

Input

  • Number of straws \$N\$ (which is an even integer \$\geq 2\$)
  • Two schemes for top and bottom links. It may be nested arrays of pairs[[1, 4], [2, 5], [6, 3]]; or a list of values from \$1\$ to \$N/2\$ where paired indices have the same value; or any format suitable for your language.

You may suppose that schemes are valid. For example in 1-indexed format every scheme has \$N/2\$ sublists with length \$2\$ and contains all (and only) numbers from \$1\$ to \$N\$. No self-links ([1, 1]); no tautologies ([[1, 2], [2, 1], …]), no broken lists ([[1], [ ], …]), no missing pairs etc.
UPD
For this reason, the number of straws \$N\$ is not required as input and can be derived from the length of schemas, if it shortens your code.

Please note, that pairs are unordered, so e.g. [[1, 4], [2, 5], [6, 3]] and [[4, 1], [2, 5], [3, 6]] are both valid (and equivalent) schemes.

Output

Any two distinct symbols for "No/many loops" and "Single loop" cases. Suitable for golfing on your language:

  • -1, 1
  • False, True etc.

Example

Number of straws: 4
Top links: [[1, 4], [3, 2]] (At the top, straw #1 is linked with straw #4, and #3 with #2)
Bottom links: [[3, 1], [2, 4]] (At the bottom, straw #1 is linked with straw #3, and #2 with #4)
We can start from #1 at the top (or any other straw) and move from top to bottom and back according to the links: 1 → 4 → 2 → 3 → 1. For this input we get the loop, that include all straws, so the answer is True.

Test cases

N: 2, TopLinks: [[1, 2]], BottomLinks: [[2, 1]]  → True

N: 4, TopLinks: [[1, 2], [3, 4]], BottomLinks: [[2, 1], [3, 4]]  → False

N: 4, TopLinks: [[1, 4], [3, 2]], BottomLinks: [[3, 1], [2, 4]] → True

N: 8, TopLinks: [[1, 2], [3, 4], [6, 5], [7, 8]],
BottomLinks: [[8, 1], [3, 2], [4, 5], [7, 6]]  → True
\$\endgroup\$
12
  • 4
    \$\begingroup\$ I’ve read it several times and I don’t understand what is being asked. Is it just me? \$\endgroup\$
    – Luis Mendo
    Commented Mar 9, 2023 at 19:09
  • 1
    \$\begingroup\$ Which book? He wrote so many... \$\endgroup\$
    – Neil
    Commented Mar 9, 2023 at 19:29
  • 1
    \$\begingroup\$ I don’t understand what you mean by “pairing the straws”, “ring-tagged”, “binding scheme”, “single-hole cycle”, or how all that is related to the drawings. So I don’t understand the general idea of the challenge. Could you rephrase / explain / add some example…? \$\endgroup\$
    – Luis Mendo
    Commented Mar 9, 2023 at 19:58
  • 2
    \$\begingroup\$ The worked example you added helps a lot. Thank you. \$\endgroup\$
    – chunes
    Commented Mar 9, 2023 at 20:50
  • 5
    \$\begingroup\$ Let me try phrasing the challenge mathematically. We're given an undirected graph as a list of edges on vertices 1 through n, and need to determine whether it's a single cycle or multiple cycles. The graph has additional structure, in that we're given the edges split into "top" and "bottom" where each half has each vertex appear on an edge exactly once. But probably the important consequence of this is just that each vertex has degree 2, so the graph decomposes into cycles. \$\endgroup\$
    – xnor
    Commented Mar 9, 2023 at 20:57

7 Answers 7

7
\$\begingroup\$

Wolfram Language (Mathematica), 22 bytes

ConnectedGraphQ@*Graph

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Can you describe the input format? \$\endgroup\$ Commented Mar 11, 2023 at 21:23
  • \$\begingroup\$ @GregMartin have a look at TIO link. It is pretty clear \$\endgroup\$
    – ZaMoC
    Commented Mar 11, 2023 at 21:32
7
\$\begingroup\$

05AB1E, 10 bytes

æʒ˜D¢ÈP}g<

Try it online!

Takes as input a list of pairs such that two straws have the same first element if they are connected at the top, and the same second element if they are connected at the bottom. Requires the top and bottom values to be disjoint. Can take them as two separate lists at a cost of +1 byte.

Returns an 05AB1E boolean, which is 1 for true and any other value for false. Can be made to return a 1 or 0 by adding Θ (05AB1E truthified) at the end.

Explanation

We return the number of subsets of straws which aren't connected to any straw not in the subset minus one. Those subsets are the ones which can be partitioned to cycles. If there is a single cycle, the only such subsets will be the entire set and the empty set, and we will return 1. However, if there are any more cycles, there will be more than 2 such sets (for example - the empty set, all the straws, and the straws in any cycle), so we will return a number greater than 1 which is falsey in 05AB1E

æ     for all subsets of straws
ʒ     only keep those such that:
 ˜     after flattening the pairs
 D     if we duplicate the list
 ¢     and count the number of occurrences of each value
 È     and check that it's even
 P     the product will be 1 - that is, all values appear an even number of times
}
g     count how many such sets are there
<     decrease it by 1 (and implicitly output)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Did I understand correctly that eg for 6 straws schemes in my notation like this [[[1, 3], [2, 4], [5, 6]], [[1, 2], [3, 5], [4, 6]] equivalent [[1, 4], [2, 4], [1, 5], [2, 6], [3, 5], [3, 6]] in yours? This is an interesting and certainly suitable format! \$\endgroup\$
    – lesobrod
    Commented Mar 10, 2023 at 6:43
4
\$\begingroup\$

Arturo, 58 56 bytes

$[a,b,n][∨∧n=2a<>b every? a'x->every? b=>[[]<>--x&]]

Try it

$[a,b,n][               ; a function taking three arguments
    ∨∧n=2a<>b           ; is n equal to 2 and a not equal to b? or is...
    every? a'x->        ; every pair from a
        every? b=>[     ; paired with every pair from b
            []<>--x&    ; not empty when their set difference is taken?
        ]               ; end every
]                       ; end function
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 33 bytes

F§θ⁰⊞υιWΦE⁺θη⁻κυ⁼¹LκFι⊞υ⊟κ⊙⁺θη⁻ιυ

Try it online! Link is to verbose version of code. Outputs an inverted Charcoal boolean, i.e. nothing if the straws are linked, - if they are not. Explanation:

F§θ⁰⊞υι

Make a copy of the first link.

WΦE⁺θη⁻κυ⁼¹Lκ

While links between previously linked straws and as yet unlinked straws exist...

Fι⊞υ⊟κ

... push all newly linked straws to the list.

⊙⁺θη⁻ιυ

Check whether any unlinked straws remain.

Note that the input format guarantees that if the straws are all linked then they will be in a single cycle.

\$\endgroup\$
2
  • \$\begingroup\$ Your last note is not quite right eg [[[1,2],[3,4]], [[1,2],[3,4]]] is valid input, all straws are linked, and we have 2 loops: 1-2 and 3-4. But your code works well in this case! \$\endgroup\$
    – lesobrod
    Commented Mar 9, 2023 at 23:22
  • \$\begingroup\$ @lesobrod Sorry for being unclear, I meant that if they are in a single connected graph then the input format ensures that this graph is in fact a single cycle. \$\endgroup\$
    – Neil
    Commented Mar 10, 2023 at 0:39
3
\$\begingroup\$

JavaScript (ES6), 68 bytes

Expects (N)(list), where list contains all 0-indexed pairs. Returns \$0\$ or \$1\$.

(n,m=1)=>g=a=>a.some(([x,y,q=1<<x|1<<y])=>m&q&&m^(m|=q))?g(a):m+1>>n

Try it online!

Commented

(              // outer function taking:
  n,           //   n = number of straws
  m = 1        //   m = bit mask, initialized to 1
) =>           //
g = a =>       // inner recursive function taking the array of links a[]
a.some(([      // for each link
  x, y,        // with x, y = straw indices
  q = 1 << x | // and q = corresponding bit mask for these indices:
      1 << y   //
]) =>          //
  m & q &&     //   if m and q have at least one bit in common:
    m ^        //     test whether m is changed when
    (m |= q)   //     the bits of q are merged with those of m
)              // end of some()
?              // if truthy:
  g(a)         //   do a recursive call
:              // else:
  m + 1 >> n   //   return 1 if the n least significant bits of m are set

65 bytes

Same input format, but returns \$1\$ for true and some integer \$>1\$ for false.

(n,m=1)=>g=a=>a.some(([x,y,q=1<<x|1<<y])=>m&q&&m^(m|=q))?g(a)-1:n

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 17 bytes A

vṅ÷:Ld1$(voÞṡḣ‟)₃

Input: nested array, output: 1(True), 0(False)

vṅ                  # Convert all pairs to strings
  ÷:L               # Split and find length of one list
     d              # Double length (get number of straws N)
      1$            # Push 1 (may be any straw number 1..N) and swap
        (           # Begin "for" loop N times
         vo         # Remove index of current straw
            Þṡ      # Sort by length
              ḣ‟    # Extract head (next index) and rotate
                )₃  # End loop and compare length with 1

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

SageMath, 20 bytes

Run it on SageMathCell!

g=Graph.is_connected
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.