13
\$\begingroup\$

A followup to this challenge by Jeremy Collprav, inspired by DLosc solving this in Regenerate. Some sections copied from the linked challenge.

Linking chains

We define a chain to be a string containing exactly one or more of only the - character, or 1 or more of only the _ character, or two chains linked by a =. More formally, a chain follows these 6 criteria:

  1. The type (- or _) of chain must change after each =
  2. Two chains must be linked with an = to change
  3. The chain does not begin or end with a =
  4. No two = may be adjacent
  5. There must be at least 3 characters and both types of chain must appear
  6. The chain must only contain _, - and =

Challenge

This is a challenge, where the sequence is formed by all unique strings that form a valid chain. However, you may choose exactly what order this sequence is in, so long as your program is consistent and deterministic in this order. You must define your order in your answer.

Having chosen an order, you may then do one of the three tasks:

  • Take a non-negative/positive integer \$n\$ as input and output the \$n\$th element in the sequence. This may be 0 or 1 indexed

  • Take a positive integer \$n\$ as input and output the first \$n\$ elements in the sequence, separated by a non-empty character that is not any of -, _ or =

  • Output the entire sequence, separated by a non-empty character that is not any of -, _ or =

    You may output in any format that supports infinite outputs, such as a stream, a generator, or outputting without natural halt (stopping due to physical limitations such as memory is fine). Take a look through the default output methods for other possible methods.

This is a challenge, so the shortest code in bytes in each language wins.


A sample sequence

The most obvious sequence can be constructed by examining all possible links of each ascending length:

-=_
_=-
--=_
-=__
__=-
_=--
---=_
--=__
-=___
-=_=-
___=-
__=--
_=---
_=-=_
----=_
---=__
--=___
--=_=-
-=____
-=__=-
-=_=--
____=-
___=--
__=---
__=-=_

and so on. This sequence is implemented in this brute-force Jelly answer, which you can use to test for larger inputs. The top link was provided by Unrelated String's answer to the linked challenge.

\$\endgroup\$
2
  • \$\begingroup\$ A nice easy 27 byte Jelly answer to beat, linked in the challenge, for brownie points \$\endgroup\$ Jul 8 at 0:13
  • 4
    \$\begingroup\$ I think the number of valid links of length \$n\$ is A019274. \$\endgroup\$
    – Arnauld
    Jul 8 at 0:59

8 Answers 8

6
\$\begingroup\$

Python 3, 59 bytes

*l,e='_-='
for s in l:e in s!=print(s);l+=s[0]+s,l[s>e]+e+s

Try it online!

Prints the sequence forever, sorted by number of non-= characters. Based on Ajax1234's generator. The idea is to do a BFS on valid strings by branching on either prepending a copy of the first character, or the other one of _- separated by an =. Strings without an = aren't printed.

Thanks to Albert.Lang for -5 bytes

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This doesn't seem to break anything. (-3) \$\endgroup\$ Jul 8 at 22:33
4
\$\begingroup\$

JavaScript (ES6), 94 bytes

-1 thanks to @l4m2

Returns the \$n\$-th entry (1-indexed) as a list of characters.

f=(n,k)=>n?f(n-/^(1+0)+1+$/.test(b=(k|1).toString(2)),-~k):[...b].map(x=>"-_="[+x?k&1:k++&&2])

Try it online!

How?

Using the following regular expression, we look for all binary patterns that start and end with a 1, contain at least one 0 and do not contain two adjacent 0's:

/^(1+0)+1+$/

(This is the intersection of A005408, A062289 and A003754.)

By interpreting 0 as the link character (=) and 1 as a chain character (- or _), we can build exactly two valid outputs for each binary pattern. For instance, 1011 gives _=-- and -=__.


JavaScript (ES6), 83 bytes

@l4m2 pointed out that this can work in base 10 just as well. However, the call stack overflow will happen quite early.

f=(n,k)=>n?f(n-/^(1+0)+1+$/.test(b=k|1),-~k):[...b+''].map(x=>"-_="[+x?k&1:k++&&2])

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 94 and likely more \$\endgroup\$
    – l4m2
    Jul 8 at 14:12
  • \$\begingroup\$ What if u use base 10 and reject those matching /[2-9]/? \$\endgroup\$
    – l4m2
    Jul 8 at 14:16
3
\$\begingroup\$

Charcoal, 47 bytes

Nθ≔Φ⮌↨θ²κη≔⁺²↨⮌Φη﹪겦²ζ⪫Eζ×⊕↨⮌Φη⁼﹪μ⊗ζ⊗鲧-_⁺ιθ=

Try it online! Link is to verbose version of code. 0-indexed. Explanation:

Nθ

Input n.

≔Φ⮌↨θ²κη

Convert n to base 2, but lose the LSB, as that will determine whether the chain starts with - or _.

≔⁺²↨⮌Φη﹪겦²ζ

Gather the remaining even bits and convert back from base 2, then add 2. This will be the number of chains.

⪫Eζ×⊕↨⮌Φη⁼﹪μ⊗ζ⊗鲧-_⁺ιθ=

Split the odd bits up among the chains, convert them back from base 2, then add 1. This gives the lengths of each chain. The chains alternate with the first chain character determined by the original LSB. The chains are then joined with =s.

\$\endgroup\$
3
\$\begingroup\$

Python3, 114 bytes

A generator that, when consumed, proceeds to produce the entire sequence.

def f():
 k='_-';q=[*k]
 while q:
  if{*k}&{*(c:=q.pop(0))}=={*k}:yield c
  T=c[-1]=='-'
  q+=[c+'='+k[~T],c+k[T]]

Try it online!

\$\endgroup\$
7
  • 2
    \$\begingroup\$ This doesn't look like it produces any chains with multiple - or _ in a row \$\endgroup\$
    – xnor
    Jul 8 at 6:15
  • \$\begingroup\$ @xnor It does, eventually. c+['_','-'][c[-1]=='-'] is the recursive branch which builds chains by adding additional _ or - as needed. \$\endgroup\$
    – Ajax1234
    Jul 8 at 12:39
  • \$\begingroup\$ It doesn't generate -=__ \$\endgroup\$
    – l4m2
    Jul 8 at 14:20
  • \$\begingroup\$ @l4m2 It does, the original recursive function was infinite, and so you would never see it, but in theory it would be produced. In any case, I added an iterative approach so the results can be seen size-by-size. \$\endgroup\$
    – Ajax1234
    Jul 8 at 15:59
  • \$\begingroup\$ not T => 1-T \$\endgroup\$
    – l4m2
    Jul 8 at 16:15
3
\$\begingroup\$

Vyxal, 153 bitsv1, 19.125 bytes

{n‛=_‹↔'\=~-Ġj=nUṪ∧;⁋,

Try it Online!

Keen readers will notice that this answer includes almost the entirety of my answer to the other question. Uses the mapping defined in the question and outputs infinitely.

I'm having way too much fun with vyncode on this one - same sbcs yet different bit count. This answer started at 25 SBCS bytes/180 bits and is now 25 SBCS bytes/169 bits.

Explained

{n‛=_‹↔Ṡ'\=-Ġṅ\=j=nUṪ∧;⁋,­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁢⁢⁡‏‏​⁡⁠⁡‌⁣⁤​‎‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏‏​⁡⁠⁡‌­
{                          # ‎⁡Forever:
 n    ↔                    # ‎⁢  Generate all combinations w/ repetition with (loop count) characters from
  ‛=_‹                     # ‎⁣  The string "=_" + "-"
       Ṡ                   # ‎⁤  Convert each combination to a string
        '             ;    # ‎⁢⁡  Keep only combinations n where:
         \=-               # ‎⁢⁢    Removing any "="s, then
            Ġṅ             # ‎⁢⁣    Grouping on consecutive characters, then
              \=j=         # ‎⁢⁤    Joining on "="s equals n
                     ∧     # ‎⁣⁡    And
                  nU       # ‎⁣⁢    removing all duplicate characters from n
                    Ṫ      # ‎⁣⁣    leaves more than one item
                       ⁋,  # ‎⁣⁤  Join the list of filtered combinations on newlines and print

💎 Created with the help of Luminespire at https://vyxal.github.io/Luminespire
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 74 bytes

f=(h,i,...j)=>f(...j,h[0]+h,i||print(h),(h<{}?'_=':'-=')+h,0);f(...'_x-x')

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 26 bytes

∞ε…-=_×æyùêʒD'=Kγ'=ýQyË›]˜

Outputs the infinite sequence.
Based on my 05AB1E answer for the base challenge.

Try it online. (Times out for \$n>7\$.)

Explanation:

∞             # Push an infinite positive list: [1,2,3,...]
 ε            # Map each integer to:
  …-=_        #  Push string "-=_"
      ×       #  Repeat it the current integer amount of times
       æ      #  Get the powerset of this string
        yù    #  Only keep the strings with a length of the current integer
          ê   #  Sorted uniquify this list of strings
  ʒ           #  Filter it by:
   D          #   Duplicate the current string
    '=K      '#   Remove all "="
       γ      #   Group the remaining characters ("-" and "_") into groups of adjacent
              #   equivalent characters
        '=ý  '#   Join these groups with "="-delimiter
   D       Q  #   Check if the string is the same as what we started with
   y          #   Push the current string again
    Ë         #   Check if all its characters are the same
   ›          #   Check whether the first check is larger than the second
              #   (aka, the first check is truthy and the second check is falsey)
 ]            # Close both the filter and map
  ˜           # Flatten the infinite list of lists of strings
              # (after which it is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Nekomata, 15 bytes

"-_"Ňŧĉᵗz'=ᵚcjt

Takes no input and outputs all possible results.

Attempt This Online!

"-_"Ňŧĉᵗz'=ᵚcjt
    Ň               Choose a natural number
"-_" ŧ              Choose a string of '-' and '_' of that length
      ĉ             Split the string into runs of identical characters
       ᵗz           Check that there are at least two runs
         '=ᵚc       Prepend '=' to each run
             j      Join the runs together
              t     Remove the first '='

Nekomata before v0.5.0.0, 18 bytes

Ň"-_"ᵚ~ĉᵗz"="ᵚcjjt

Attempt This Online!

\$\endgroup\$

Your Answer

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

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