Iterate over strings II

Question

This is a successor to a previous challenge.

Input

An integer \$1 \leq n \leq 5\$.

Task

Your code should produce all strings that satisfy the following properties:

• Your string should contain exactly two each of the first \$n\$ letters of the alphabet.
• It should not contain the same letter twice in a row
• It must start with the letter a.
• If there is a letter at index i in the string, all the letters earlier in the alphabet must occur somewhere at the indices 1..i-1. This means, for example, that the first c can't come before the first b.
• It must contain exactly \$2n\$ zeros.
• For each zero there must exist a pair of identical letters so that one of the pair is somewhere to its left and one of the pair is somewhere to its right in the string.
• It must not contain anything other than zeros and the lower case letters.

Examples

n=1,`a00a` is the only valid output.

n=2,`a0ab000b`and `ab0000ab` are both valid outputs.  `a0bab000` and `a0a0b00b` are not valid.

n=3,`a0bc0b0a000c` and `a0b000ca0b0c`  are both valid outputs.  ` a0cb0b0a000c` and `a0b000ba0c0c` are not valid.

Answer 1

Charcoal, 61 bytes

Ｎθ⊞υωＦ×⁴θ≔ΣＥυ⁺κ⁺Ｅ∧‹№κ0⊗θ⊙β⁼¹№κμ0Φ⪪…βθ¹∧⁻μΦ⮌κ¬π∧‹№κμ²⬤…βν№κξυυ

Attempt This Online! Link is to verbose version of code. Explanation: Based on my answer to Iterate over all non-equivalent strings.

Ｎθ

Input n.

⊞υω

Start with an empty string.

Ｆ×⁴θ

Loop 4n times.

≔ΣＥυ⁺κ⁺Ｅ∧‹№κ0⊗θ⊙β⁼¹№κμ0Φ⪪…βθ¹∧⁻μΦ⮌κ¬π∧‹№κμ²⬤…βν№κξυ

For each string so far, create strings with zero and all of the first n lowercase letters appended to it, but exclude those that fail to satisfy the criteria.

υ

Output the final strings.

There are two criteria that are checked before a zero can be appended:

• There must be fewer than 2n zeros already in the string.
• There must be a letter that appears exactly once in the string.

Answer 2

JavaScript (V8), 139 bytes

The criterion on 0's is borrowed from Neil's answer. ("There must be a letter that appears exactly once" before a zero.)

Prints the strings.

f=(n,s='',m=1,q=0,p,g=i=>~i&&g(i-1,(b=1<<i*4,i?i!=p:q&1118480&&n)*2>q/b%16&&f(n,s+"0abcde"[i],m+(i==m&m<n),q+b,i)))=>s[4*n-1]?print(s):g(m)

Try it online!

Hacked version printing the number of solutions up to \$n=4\$

How?

Because we have \$n\le5\$ and because a character may not appear more than \$10\$ times, we can store the character counts in a bitmask \$q\$ of \$6\times4\$ bits:

0000 0000 0000 0000 0000 0000
\__/ \__/ \__/ \__/ \__/ \__/
  e    d    c    b    a    0

The 4-bit width is actually only required for 0's. The possible values for letter nibbles are 0000, 0001 and 0010.

When inserting a zero, we need to test whether there's at least one letter that appears exactly once. This is achieved by doing a bitwise AND of \$q\$ with:

0001 0001 0001 0001 0001 0000 = 1118480

All in all, this is shorter and faster than my previous method that was using an array.

Commented

f = (                   // f is a recursive function taking:
  n,                    //   n = input
  s = '',               //   s = output string
  m = 1,                //   m = upper character bound
  q = 0,                //   q = bitmask keeping track of char. counts
  p,                    //   p = previous character index
  g = i =>              //   g is a recursive function taking a counter i
  ~i && g(              //   unless i = -1, do a recursive call to g:
    i - 1,              //     decrement i
    (                   //     compute the max. count for this character:
      b = 1 << i * 4,   //       b = LSB of the character nibble
      i ?               //       if this is a letter:
        i != p          //         the max. count is 2 if i != p
      :                 //       else (this is a zero):
        q & 1118480     //         the max. count is 2n if it's preceded
        && n            //         by a letter appearing exactly once
    ) * 2 > q / b % 16  //     abort if this char. appeared too many times
    && f(               //     otherwise, do a recursive call to f:
      n,                //       pass n unchanged
      s + "0abcde"[i],  //       append the new character to s
      m +               //       increment m if ...
      (i == m & m < n), //       ... i = m and m < n
      q + b,            //       update the bitmask
      i                 //       set the previous character index to i
    )                   //     end of recursive call
  )                     //   end of recursive call
) =>                    //
s[4 * n - 1] ?          // if the target length is reached:
  print(s)              //   print s
:                       // else:
  g(m)                  //   call g to generate more characters

Answer 3

05AB1E, 40 bytes

A£©Î×ì2לÙʒáÙ®Q}ʒÔág;Q}ʒS>ƶ©þε®s¡`áÃgĀ}P

Brute-force, so very slow. Is able to output the result for \$n=2\$ in about 20 seconds on TIO.

Try it online.

Explanation:

Step 1: Create a string with the correct characters, to comply to the first and sixth rules ("Your string should contain exactly two each of the first \$n\$ letters of the alphabet." and "It must contain exactly \$2n\$ zeros."), and get all its unique permutations:

A               # Push the lowercase alphabet
 £              # Pop and leave the (implicit) input amount of leading characters
  ©             # Store it in variable `®` (without popping)
   Î            # Push 0 and the input-integer
    ×           # Pop both, and push a string with the input amount of 0s
     ì          # Prepend it to the string
      2×        # Double the entire string
œ               # Pop and push a list of all its permutations
 Ù              # Uniquify this list

Try just step 1 online.

Step 2: Verify the fifth rule ("If there is a letter at index i in the string, all the letters earlier in the alphabet must occur somewhere at the indices 1..i-1."):

ʒ    }          # Filter this list of strings by:
 á              #  Only keep its letters, removing the 0s
  Ù             #  Uniquify it
   ®Q           #  Check whether it's equal to string `®` of step 1

Try the first two steps online.

Step 3: Verify the second rule ("It should not contain the same letter twice in a row"):

ʒ     }         # Filter it again by:
 Ô              #  Connected uniquify its characters
  á             #  Then remove all 0s again by keeping letters
   g;           #  Pop and push its length, and halve it
     Q          #  Check if halve this length equals the (implicit) input-integer

Try the first three steps online.

Step 4: Verify the seventh rule ("For each zero there must exist a pair of identical letters so that one of the pair is somewhere to its left and one of the pair is somewhere to its right in the string."), which implicitly also verifies the third and fourth rules at the same time ("It must start with the letter a." and "It must end with a letter"), and output the result:

ʒ               # Filter it once more:
 S              #  Convert the string to a list of characters
  >             #  Increase all 0s to 1s (and keep the letters unchanged)
   ƶ            #  Multiply all values by their 1-based index
    ©           #  Store this list as new variable `®` (without popping)
     þ          #  Pop and keep just its digits, removing the letters
      ε         #  Map over this list of integers:
       ®        #   Push list `®`
        s       #   Swap so the current integer is at the top
         ¡      #   Split list `®` by the current integer, leaving a pair of lists
          `     #   Pop and push both lists to the stack
           á    #   Only keep the letters of the second string
            Ã   #   Only keep the letters from the first string that are also in the second
             gĀ #   Check if what remains is NOT empty
      }P        #  After the map: product to check if all are truthy
                # (after which the result is output implicitly)

Answer 4

Haskell, 215 bytes

import Data.List
f n|c<-"__">>take n['a'..]=[x|x<-permutations$c++(c>>"0"),x!!0=='a',all(\i->not$isInfixOf[i,i]x)c,all((\(f,z:s)->last$(any(>z)$intersect f s):[all(`elem`z:f)['a'..z]|z>'0']).(`splitAt`x))[0..4*n-1]]

Attempt This Online!

Answer 5

Perl 5, 238 bytes

sub{$_=substr(10**$_[0].abcdefghij,1,2*pop)x2;my%r;1while s/^(.*)(.)(.*)(.)(??{$t="$1$4$3$2$'";my%a;$t=~m,(\D).*(0).*\1(??{$a{$-[2]}++;X}),;y|||c!=2*keys%a||$t=~m,(\D)(\1|.*(\D).*\3(??{$1lt$3})),||$r{$t}++;$s{$t}++||''})/$1$4$3$2/;keys%r}

Try it online!

Returns arrays of 1, 28, 1816, 180143 strings for n = 1,2,3,4. Spent more than half an hour for n=4.

Answer 6

Retina, 114 bytes

.+
*
Y`\_`l
.+
<$&>$&$.&*2*0
/>./+Lrv$`(?(2)(\3.+))<(.+)?([a-z])|(\6.*)<(.+([a-z]).*)(0)\b
$%`$1$4$3$7<$2$5$%'
<>

Try it online! Explanation: Based on my answer to Iterate over all non-equivalent strings.

.+
*
Y`\_`l

Generate the first n lowercase letters.

.+
<$&>$&$.&*2*0

Make a duplicate set, wrap the first set in < and >, and also append 2n 0s to the second set.

Lrv$`(?(2)(\3.+))<(.+)?([a-z])|(\6.*)<(.+([a-z]).*)(0)\b
$%`$1$4$3$7<$2$5$%'

For each string, make new strings by either a) moving the first letter from the first set or b) moving a letter from the second set that was moved from the first set but not in the immediately previous iteration c) moving the last zero, if there is a letter still in the second set that was moved from the first set.

/>./+`

Repeat until the second set is empty for all strings.

<>

Remove the <> markers.

Answer 7

Jelly, 35 bytes

Øaḣx2;Œ!ḟQṢƑɗƇɗJ$⁼ƝÐṂṣⱮf/ƇƑ¥ƇḤOnaƊQ

A monadic Link that accepts \$n\$ and yields a list of lists of characters.

Try it online! (Will time out for anything above two though!)

How?

Constructs all strings fulfilling the conditions with natural numbers in the place of zeros by filtering all permutations of the letters and numbers that, when deduplicated have their letters in order, maps the numbers back to zeros, and then deduplicates.

Øaḣx2;Œ!ḟQṢƑɗƇɗJ$⁼ƝÐṂṣⱮf/ƇƑ¥ƇḤOnaƊQ - Link: n
Øa                                  - alphabet
  ḣ                                 - head to {n}
   x2                               - times two -> "aabb..."
                $                   - last two links as a monad f(Letters):
               J                    -   indices -> [1..2n]
              ɗ                     -   last three links as a dyad - f(Letters, Indices)
     ;                              -   {Letters} concatenate {Indices} -> e.g. ['a','a','b','b',1,2,3,4]
      Œ!                            -   all permutations
             Ƈ                      -   keep those {Permuations} for which:
            ɗ                       -     last three links as a dyad - f(Permutation, indices)
        ḟ                           -       {Permutation} filter-discard {indices}
         Q                          -       deduplicate
           Ƒ                        -       is invariant under:
          Ṣ                         -         sort
                   ÐṂ               - keep those {Alphabet-Increaing-Permutations} minimal under:
                  Ɲ                 -   for neighbouring pairs:
                 ⁼                  -     equal?
                            Ƈ       - keep those {Alphabet-Increasing-Adjacency-Different-Permutations} for which:
                           ¥ Ḥ      -   last two links as a dyad - f(Permutation, 2n):
                      Ɱ             -     map across {i in [1..2n]} with:
                     ṣ              -       split {Permutation} at occurrence of {i}
                          Ƒ         -     is that list of Splits invariant under?:
                         Ƈ          -       filter keep {Splits} for which:
                        /           -         reduce {Split=[L,R]} by:
                       f            -           {L} filter keep {R}
                                 Ɗ  - last three links as a monad - f(Valid-Permutations):
                              O     -   cast {ValidPermutations} to ordinals (a no-op for integers) -> Ords
                               n    -   {Ords} not equal {ValidPermutations} (vectorises) -> Mask
                                a   -   {Mask} logical AND {ValidPermutations} (vectorises)
                                  Q - deduplicate

Answer 8

JavaScript (V8), 148 bytes

n=>(g=(i,j,t,s=[])=>s.map(_=>g(i,j,t+_,s.filter(r=>r!=_)),s+s&&j&&g(i,j-1,t+0,s),i<n?g(i+1,j,t+(c='abcde'[i]),[...s,c]):j||s+s||print(t)))(0,2*n,'')

Try it online!

As comparison to the 139 one