18
\$\begingroup\$

Consider an arbitrary set of letters \$L\$. It may either be \$\{A, B, C\}\$, \$\{M, N, O, P\}\$, \$\{N, F, K, D\}\$, or even contain all the 26 letters. Given an instance of \$L\$ and a positive integer \$n\$, how many \$n\$-letter words can we build from \$L\$ such that no adjacent letters are the same (so for example ABBC is not allowed from \$\{A, B, C\}\$)?

This can be solved using combinatorics, but what those words are?

Input

A non-empty string \$L\$ and a positive integer \$n > 0\$.

You choose to accept only lowercase letters, only uppercase letters, or both, as input for \$L\$.

Also, note that a valid \$L\$ won't contain any duplicate letters, so ABCA is an invalid input and should not be handled.

Output

A list of all strings of length \$n\$ that can be formed from \$L\$ such that no adjacent letters are the same.

You can repeat letters, so a valid solution for \$L=\{A, B, C\}\$ and \$n=3\$ is ABA, ABC, ACB, ACA, BAC, BCA, BAB, BCB, CAB, CBA, CAC and CBC.

Also note that \$|L| < n\$ is possible, so a valid solution for \$L=\{A, B\}\$ and \$n=3\$ is only ABA and BAB.

And yes, \$|L| > n\$ is also possible, so a valid solution for \$L=\{A, B, C, D\}\$ and \$n=3\$ is ABA, ABC, ABD, ACA, ACB, ACD, ADA, ADB, ADC, BAB, BAC, BAD, BCA, BCB, BCD, BDA, BDB, BDC, CAB, CAC, CAD, CBA, CBC, CBD, CDA, CDB, CDC, DAB, DAC, DAD, DBA, DBC, DBD, DCA, DCB and DCD.

The output doesn't have to be in a particular order.

Test samples

ABC, 3 -> ABA, ABC, ACA, ACB, BAB, BAC, BCA, BCB, CAB, CAC, CBA, CBC
AB, 3 -> ABA, BAB
ABCD, 3 -> ABA, ABC, ABD, ACA, ACB, ACD, ADA, ADB, ADC, BAB, BAC, BAD, BCA, BCB, BCD, BDA, BDB, BDC, CAB, CAC, CAD, CBA, CBC, CBD, CDA, CDB, CDC, DAB, DAC, DAD, DBA, DBC, DBD, DCA, DCB, DCD
OKAY, 2 -> OK, OA, OY, KO, KA, KY, AO, AK, AY, YO, YK, YA
CODEGLF, 3 -> COC, COD, COE, COG, COL, COF, CDC, CDO, CDE, CDG, CDL, CDF, CEC, CEO, CED, CEG, CEL, CEF, CGC, CGO, CGD, CGE, CGL, CGF, CLC, CLO, CLD, CLE, CLG, CLF, CFC, CFO, CFD, CFE, CFG, CFL, OCO, OCD, OCE, OCG, OCL, OCF, ODC, ODO, ODE, ODG, ODL, ODF, OEC, OEO, OED, OEG, OEL, OEF, OGC, OGO, OGD, OGE, OGL, OGF, OLC, OLO, OLD, OLE, OLG, OLF, OFC, OFO, OFD, OFE, OFG, OFL, DCO, DCD, DCE, DCG, DCL, DCF, DOC, DOD, DOE, DOG, DOL, DOF, DEC, DEO, DED, DEG, DEL, DEF, DGC, DGO, DGD, DGE, DGL, DGF, DLC, DLO, DLD, DLE, DLG, DLF, DFC, DFO, DFD, DFE, DFG, DFL, ECO, ECD, ECE, ECG, ECL, ECF, EOC, EOD, EOE, EOG, EOL, EOF, EDC, EDO, EDE, EDG, EDL, EDF, EGC, EGO, EGD, EGE, EGL, EGF, ELC, ELO, ELD, ELE, ELG, ELF, EFC, EFO, EFD, EFE, EFG, EFL, GCO, GCD, GCE, GCG, GCL, GCF, GOC, GOD, GOE, GOG, GOL, GOF, GDC, GDO, GDE, GDG, GDL, GDF, GEC, GEO, GED, GEG, GEL, GEF, GLC, GLO, GLD, GLE, GLG, GLF, GFC, GFO, GFD, GFE, GFG, GFL, LCO, LCD, LCE, LCG, LCL, LCF, LOC, LOD, LOE, LOG, LOL, LOF, LDC, LDO, LDE, LDG, LDL, LDF, LEC, LEO, LED, LEG, LEL, LEF, LGC, LGO, LGD, LGE, LGL, LGF, LFC, LFO, LFD, LFE, LFG, LFL, FCO, FCD, FCE, FCG, FCL, FCF, FOC, FOD, FOE, FOG, FOL, FOF, FDC, FDO, FDE, FDG, FDL, FDF, FEC, FEO, FED, FEG, FEL, FEF, FGC, FGO, FGD, FGE, FGL, FGF, FLC, FLO, FLD, FLE, FLG, FLF
NFKD, 4 -> NFNF, NFNK, NFND, NFKN, NFKF, NFKD, NFDN, NFDF, NFDK, NKNF, NKNK, NKND, NKFN, NKFK, NKFD, NKDN, NKDF, NKDK, NDNF, NDNK, NDND, NDFN, NDFK, NDFD, NDKN, NDKF, NDKD, FNFN, FNFK, FNFD, FNKN, FNKF, FNKD, FNDN, FNDF, FNDK, FKNF, FKNK, FKND, FKFN, FKFK, FKFD, FKDN, FKDF, FKDK, FDNF, FDNK, FDND, FDFN, FDFK, FDFD, FDKN, FDKF, FDKD, KNFN, KNFK, KNFD, KNKN, KNKF, KNKD, KNDN, KNDF, KNDK, KFNF, KFNK, KFND, KFKN, KFKF, KFKD, KFDN, KFDF, KFDK, KDNF, KDNK, KDND, KDFN, KDFK, KDFD, KDKN, KDKF, KDKD, DNFN, DNFK, DNFD, DNKN, DNKF, DNKD, DNDN, DNDF, DNDK, DFNF, DFNK, DFND, DFKN, DFKF, DFKD, DFDN, DFDF, DFDK, DKNF, DKNK, DKND, DKFN, DKFK, DKFD, DKDN, DKDF, DKDK
JOHN, 5 -> JOJOJ, JOJOH, JOJON, JOJHJ, JOJHO, JOJHN, JOJNJ, JOJNO, JOJNH, JOHJO, JOHJH, JOHJN, JOHOJ, JOHOH, JOHON, JOHNJ, JOHNO, JOHNH, JONJO, JONJH, JONJN, JONOJ, JONOH, JONON, JONHJ, JONHO, JONHN, JHJOJ, JHJOH, JHJON, JHJHJ, JHJHO, JHJHN, JHJNJ, JHJNO, JHJNH, JHOJO, JHOJH, JHOJN, JHOHJ, JHOHO, JHOHN, JHONJ, JHONO, JHONH, JHNJO, JHNJH, JHNJN, JHNOJ, JHNOH, JHNON, JHNHJ, JHNHO, JHNHN, JNJOJ, JNJOH, JNJON, JNJHJ, JNJHO, JNJHN, JNJNJ, JNJNO, JNJNH, JNOJO, JNOJH, JNOJN, JNOHJ, JNOHO, JNOHN, JNONJ, JNONO, JNONH, JNHJO, JNHJH, JNHJN, JNHOJ, JNHOH, JNHON, JNHNJ, JNHNO, JNHNH, OJOJO, OJOJH, OJOJN, OJOHJ, OJOHO, OJOHN, OJONJ, OJONO, OJONH, OJHJO, OJHJH, OJHJN, OJHOJ, OJHOH, OJHON, OJHNJ, OJHNO, OJHNH, OJNJO, OJNJH, OJNJN, OJNOJ, OJNOH, OJNON, OJNHJ, OJNHO, OJNHN, OHJOJ, OHJOH, OHJON, OHJHJ, OHJHO, OHJHN, OHJNJ, OHJNO, OHJNH, OHOJO, OHOJH, OHOJN, OHOHJ, OHOHO, OHOHN, OHONJ, OHONO, OHONH, OHNJO, OHNJH, OHNJN, OHNOJ, OHNOH, OHNON, OHNHJ, OHNHO, OHNHN, ONJOJ, ONJOH, ONJON, ONJHJ, ONJHO, ONJHN, ONJNJ, ONJNO, ONJNH, ONOJO, ONOJH, ONOJN, ONOHJ, ONOHO, ONOHN, ONONJ, ONONO, ONONH, ONHJO, ONHJH, ONHJN, ONHOJ, ONHOH, ONHON, ONHNJ, ONHNO, ONHNH, HJOJO, HJOJH, HJOJN, HJOHJ, HJOHO, HJOHN, HJONJ, HJONO, HJONH, HJHJO, HJHJH, HJHJN, HJHOJ, HJHOH, HJHON, HJHNJ, HJHNO, HJHNH, HJNJO, HJNJH, HJNJN, HJNOJ, HJNOH, HJNON, HJNHJ, HJNHO, HJNHN, HOJOJ, HOJOH, HOJON, HOJHJ, HOJHO, HOJHN, HOJNJ, HOJNO, HOJNH, HOHJO, HOHJH, HOHJN, HOHOJ, HOHOH, HOHON, HOHNJ, HOHNO, HOHNH, HONJO, HONJH, HONJN, HONOJ, HONOH, HONON, HONHJ, HONHO, HONHN, HNJOJ, HNJOH, HNJON, HNJHJ, HNJHO, HNJHN, HNJNJ, HNJNO, HNJNH, HNOJO, HNOJH, HNOJN, HNOHJ, HNOHO, HNOHN, HNONJ, HNONO, HNONH, HNHJO, HNHJH, HNHJN, HNHOJ, HNHOH, HNHON, HNHNJ, HNHNO, HNHNH, NJOJO, NJOJH, NJOJN, NJOHJ, NJOHO, NJOHN, NJONJ, NJONO, NJONH, NJHJO, NJHJH, NJHJN, NJHOJ, NJHOH, NJHON, NJHNJ, NJHNO, NJHNH, NJNJO, NJNJH, NJNJN, NJNOJ, NJNOH, NJNON, NJNHJ, NJNHO, NJNHN, NOJOJ, NOJOH, NOJON, NOJHJ, NOJHO, NOJHN, NOJNJ, NOJNO, NOJNH, NOHJO, NOHJH, NOHJN, NOHOJ, NOHOH, NOHON, NOHNJ, NOHNO, NOHNH, NONJO, NONJH, NONJN, NONOJ, NONOH, NONON, NONHJ, NONHO, NONHN, NHJOJ, NHJOH, NHJON, NHJHJ, NHJHO, NHJHN, NHJNJ, NHJNO, NHJNH, NHOJO, NHOJH, NHOJN, NHOHJ, NHOHO, NHOHN, NHONJ, NHONO, NHONH, NHNJO, NHNJH, NHNJN, NHNOJ, NHNOH, NHNON, NHNHJ, NHNHO, NHNHN
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Is A, 2 a valid input that should return an empty list? \$\endgroup\$
    – Arnauld
    Feb 19 at 14:55
  • \$\begingroup\$ Can the input be list? \$\endgroup\$
    – Fmbalbuena
    Feb 19 at 15:12
  • \$\begingroup\$ @Arnauld Yes, it's a valid input and it should return an empty list indeed. In fact, every n > 1 should return an empty list for L being a set with a single letter. \$\endgroup\$
    – enzo
    Feb 19 at 15:27
  • \$\begingroup\$ @Fmbalbuena Yes, it can be a list of characters or a list of strings of length 1. \$\endgroup\$
    – enzo
    Feb 19 at 15:27
  • 1
    \$\begingroup\$ @DomHastings I would say yes, so it's easier to distinguish them. A leading space is allowed though, if it helps. \$\endgroup\$
    – enzo
    Feb 20 at 15:56

25 Answers 25

12
\$\begingroup\$

Husk, 4 bytes

fΛ≠π

Try it online!

Short and straightforward solution, the MVP here is Λ, thanks to its overload that can take a binary function and use it to check pairs of adjacent elements.

Explanation

fΛ≠π
   π    Cartesian power of L and n (generates all possible words)
f       Filter those
 Λ        for which all adjacent letters
  ≠           are different
\$\endgroup\$
8
\$\begingroup\$

Google Sheets, 88 bytes

=let(L,torow(A:A,1),reduce(,sequence(B1),lambda(a,_,sort(tocol(if(left(a)=L,,L&a),1)))))

Put letters \$L\$ in column A:A, the target length \$n\$ in cell B1, and the formula in cell D1.

no adjacent letters.png

The formula generates all possible strings of length \$n\$ from the alphabet \$L\$ with repeats, and while building a string, refuses it if its first character is the same as the one currently being prepended.

Ungolfed:

=let( 
  letters, torow(A1:A, 1), 
  n, B1, 
  blank, iferror(ø), 
  reduce(blank, sequence(n), lambda(acc, curr, 
    sort( 
      tocol(if(left(acc) = letters, blank, letters & acc), 1) 
    ) 
  )) 
)

acc is a vertical array, and letters is a horizontal array. The sort() function is array enabled, which means that the inner comparison and concatenation produce acc × letters results each round. tocol() then flattens the result, weeding out blanks generated by the if().

Hat tip to JvdV for the left(acc) = letters pattern.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Porting my answer to GS gives me =LET(L,TOCOL(A:A,1),SORT(TOCOL(MAP(REDUCE(,SEQUENCE(B1),LAMBDA(r,n,TOROW(r&L))),LAMBDA(s,IFS(AND(ISERR(FIND(L&L,s))),s))),3))) for 126 bytes. A whole wopping 1 byte saved! =) \$\endgroup\$
    – JvdV
    Feb 19 at 16:40
  • 1
    \$\begingroup\$ @JvdV thanks, that made me realize that the array expression and thus also the length test were superfluous. In Sheets, 1-regexmatch() saves more bytes than and(iserr(find())) because it doesn't require map() in filter(). \$\endgroup\$ Feb 20 at 7:12
  • \$\begingroup\$ Yes nice. I been looking at this for a bit and for 112 bytes you could use: =SORT(QUERY(REDUCE(,SEQUENCE(B1),LAMBDA(x,n,TOCOL(x&TOROW(A:A,1)))),"where not Col1 matches'.*(?<c>.)\k<c>.*'")). Though this only saves 1 character when looking at your updated answer. \$\endgroup\$
    – JvdV
    Feb 21 at 15:40
  • \$\begingroup\$ Here I got another option for 90 bytes: =SORT(LET(L,TOROW(A:A,1),REDUCE(,SEQUENCE(B1),LAMBDA(x,n,TOCOL(IFS(RIGHT(x)<>L,x&L),3))))) \$\endgroup\$
    – JvdV
    Feb 21 at 16:00
  • 1
    \$\begingroup\$ @JvdV thanks! Using that pattern now. if() and = save one more byte. \$\endgroup\$ Feb 21 at 18:18
7
\$\begingroup\$

Ruby, 42 bytes

->l,n{(?A*n..?Z*n).grep_v /[^#{l}]|(.)\1/}

Attempt This Online!

Input in uppercase. Start with a list of all \$n\$-letter strings, then remove those containing letters not in \$L\$ or double letters.

\$\endgroup\$
7
\$\begingroup\$

Haskell, 49 47 bytes

l#1=pure<$>l
l#n=[c:a:r|a:r<-l#(n-1),c<-l,a/=c]

Try it online!

Edit: Thanks to @xnor for taking off two bytes! I didn't know you could remove the parentheses in that context

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The (a:r)<- works without parens \$\endgroup\$
    – xnor
    Feb 20 at 3:37
5
\$\begingroup\$

JavaScript (ES10), 54 bytes

Expects (a)(n), where a is an array of characters. Returns an array of strings.

a=>g=(n,o,p)=>n--?a.flatMap(c=>p!=c?g(n,[o]+c,c):[]):o

Try it online!

Commented

a =>             // outer function taking a[]
g = (            // inner recursive function taking:
  n,             //   n = expected length
  o,             //   o = output string, initially undefined
  p              //   p = previous character in the output,
) =>             //       initially undefined
n-- ?            // if we don't have enough characters:
  a.flatMap(c => //   for each character c in a[]:
    p != c ?     //     if the previous char. is not equal to c:
      g(         //       do a recursive call:
        n,       //         pass the updated value of n
        [o] + c, //         coerce o to a string and append c to o
        c        //         set p = c
      )          //       end of recursive call
    :            //     else:
      []         //       abort
  )              //   end of flatMap()
:                // else:
  o              //   return the output
\$\endgroup\$
5
\$\begingroup\$

Vyxal, 5 bytes

↔'ÞǓ⁼

Try it Online!

generates all combinations of length n using the characters in the input string, then filters by those which are equal to the string with all adjacent duplicates removed.

\$\endgroup\$
5
\$\begingroup\$

C (gcc), 168 160 119 114 bytes

-8 Thanks to @corvus_192 for pointing out newline separation between values was allowed, and a massive -41 thanks to @tsh, a further -5 thanks to @ceilingcat

char*l,*c;f(n,i){n?(c[n-1]=l[i])&&(l[i]-c[n]&&f(n-1,0),f(n,i+1)):puts(c);}g(e,n)char*e;{c=calloc(n,2);l=e;f(n,0);}

Try it online!

Prints the newline separated output to STDOUT.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ If you print the output newline-separated, you can replace printf("%s ",c) with puts(c). \$\endgroup\$
    – corvus_192
    Feb 19 at 20:08
  • 1
    \$\begingroup\$ 119 bytes \$\endgroup\$
    – tsh
    Feb 22 at 11:59
5
\$\begingroup\$

K (ngn/k), 22 21 18 bytes:

-1 byte due to @ovs. -3 bytes thanks to @ngn.

{(|/'=':')_+!y#,x}

Try it online

\$\endgroup\$
2
  • 2
    \$\begingroup\$ There is an barely documented feature of odometer here to save a byte: If ! gets a list of string (or a general nested list?), it does x@'!#'x. Doing !y#,x will avoid indexing back into x at the end. \$\endgroup\$
    – ovs
    Feb 20 at 11:50
  • 1
    \$\begingroup\$ replacing list@&mask with "filter" can help shorten this - func#list or its negation func_list (note that func is applied to the entire list, not to its individual items) \$\endgroup\$
    – ngn
    Feb 23 at 13:42
4
\$\begingroup\$

MATL, 9 bytes

Z^t!dXAY)

Try it online!

Explanation

Z^    % Implicit inputs. Cartesian product. Gives a character matrix where 
      % each row is a Cartesian tuple (*)
t!    % Duplicate, transpose
d     % Consecutive differences, computed along vertical dimension
XA    % Vertical-all: gives true for columns that only contain nonzeros
Y)    % Use as logical index into the rows of (*). Implicit display
\$\endgroup\$
4
\$\begingroup\$

R, 70 bytes

\(L,n,x=combn(rep(L,n+1),n))unique(x[,apply(x,2,\(a)all(diff(a)))],,2)

Attempt This Online!

Uses a rather loose definition of string - a vector of character codes. Outputs a matrix with unique words in columns.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 74 67 64 bytes

-7 thanks to @Albert.Lang, -3 thanks to @Mukundan314

f=lambda l,n:[""][n:]or[c+w for w in f(l,n-1)for c in{*l}-{*w[:1]}]

Try it online!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ [...]if n else[''] can be n and[...]or[''] \$\endgroup\$
    – kg583
    Feb 20 at 0:57
  • \$\begingroup\$ 65 bytes: f=lambda l,n:n-1and[b+a for a in f(l,n-1)for b in{*l}-{a[0]}]or l \$\endgroup\$ Feb 20 at 4:46
  • 1
    \$\begingroup\$ @kg583 won't work for testcase A, 2 \$\endgroup\$
    – tsh
    Feb 20 at 11:44
  • 1
    \$\begingroup\$ f=lambda l,n:[""][n:]or[c+w for w in f(l,n-1)for c in{*l}-{*w[:1]}] seems to work. \$\endgroup\$ Feb 20 at 14:05
  • 1
    \$\begingroup\$ 64 bytes: f=lambda l,n:l*(n<2)or[b+a for a in f(l,n-1)for b in{*l}-{a[0]}] (bug fixed) \$\endgroup\$ Feb 20 at 14:18
4
\$\begingroup\$

Perl 5 -nl, 30 bytes

map!/(.)\1/&&say,glob"{$_}"x<>

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Nice! I did wonder about changing the input format for my older version, but I didn't pick up on the map usage! Smart! \$\endgroup\$ Feb 20 at 17:30
  • \$\begingroup\$ Looks like you can remove ! if you change && to || for 29 Try it online! \$\endgroup\$
    – noodle man
    Feb 25 at 5:24
3
\$\begingroup\$

APL+WIN, 42 bytes

Prompts for string followed by n:

n←m←⎕⋄⍎∊(⎕-1)⍴⊂'n←n∘.,m⋄'⋄(0=+/¨2=/¨,n)/,n

Try it online! Thanks to Dyalog Classic

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

Uiua SBCS, 23 21 20 bytes

▽≡(/×≡/≠◫2).⊏☇1⇡▽:⧻,

Try it!

▽≡(/×≡/≠◫2).⊏☇1⇡▽:⧻,
                  ⧻,  # length of the set, call it L
               ⇡▽:    # permutations w/ repetition of [0..n) with length L
             ☇1       # change to rank 2
            ⊏         # index into set
           .          # duplicate
 ≡(       )           # map each row
        ◫2            # windows of length 2
     ≡/≠              # reduce each row by inequality
   /×                 # product
▽                     # keep
\$\endgroup\$
1
  • \$\begingroup\$ huh, /(☇1⊞⊂)↯ does the exact same thing as ⊏☇1⇡▽:⧻, completely differently \$\endgroup\$
    – Tbw
    Feb 21 at 17:07
3
\$\begingroup\$

Jelly, 6 bytes

ṗnƝẠ$Ƈ

A dyadic Link that accepts the alphabet on the left and the word length on the right and yields a list of valid words.

Try it online!

How?

ṗnƝẠ$Ƈ - Link: Alphabet, WordLength
ṗ      - {Alphabet} Cartesian power {WordLength} -> all words
     Ƈ - keep those for which:
    $  -   last two links as a monad - f(Word):
  Ɲ    -     for neighbouring pairs:
 n     -       not equal?
   Ạ   -     all?

...if one didn't need to handle an alphabet of length one, then five bytes would do - ṗnƝÐṀ (keep those words which are maximal under neighbourwise not-equal).

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

Excel ms365, 85 84 bytes

  • -1 thanks to doubleunary's tip to apply LEFT() instead of RIGHT().

Assuming:

  • \$L\$ - Given input in the first row 1:1 starting from A1 onwards;
  • \$n\$ - Given integer in A2.

Formula, thus output, in A4 spilled down:

=LET(L,TOROW(1:1,1),REDUCE("",TAKE(L,,A2),LAMBDA(x,n,TOCOL(IFS(LEFT(x)<>L,L&x),3))))

enter image description here

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Save one more byte: ifs(L<>left(x),L&x). \$\endgroup\$ Feb 23 at 8:57
2
\$\begingroup\$

Charcoal, 20 bytes

⊞υωFN≔ΣEηEΦυ⌕μκ⁺κμυυ

Attempt This Online! Link is to verbose version of code. Explanation:

⊞υω

Start with the empty string.

FN

Loop n times.

≔ΣEηEΦυ⌕μκ⁺κμυ

For each letter of L, prefix it to each string so far that does not begin with that letter, then concatenate all of the results together. (Prefixing each letter of L that the string does not begin with fails when there are no strings in the list.)

υ

Output the final list.

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

05AB1E, 5 bytes

ãʒüÊP

Inputs in the order \$n,L\$.

Try it online or verify all test cases.

Or alternatively:

ãʒDÔQ

Try it online or verify all test cases.

Explanation:

ã      # Cartesian product on both (implicit) inputs to get all n-sized strings using
       # characters from L
 ʒ     # Filter it by:
  ü    #  Map over each overlapping pair:
   Ê   #   Check that they're NOT equal
    P  #  Check that all of them are truthy
       # (after which the filtered list is output implicitly)

  D    #  Duplicate the current string
   Ô   #  Connected uniquify it, collapsing all equal adjacent characters
    Q  #  Check if the connected uniquified string is still the same
\$\endgroup\$
2
\$\begingroup\$

Retina, 41 bytes

"$&"+%Lw$`,.*(.)
$`$1$&$'
\d|,.+

A`(.)\1

Try it online! Link includes test cases. Takes comma-separated input. Explanation:

"$&"+`

Repeat n times...

%Lw$`,.*(.)
$`$1$&$'

Replicate each line for each letter of L but inserting a copy of the letter before the comma.

\d|,.+

Remove the copies of n and L.

A`(.)\1

Remove all lines with duplicate adjacent letters.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice one! You can have a test suite if you use the current string rather than the original input from the history ($0 instead of $+) Try it online! \$\endgroup\$
    – Leo
    Feb 20 at 3:36
  • \$\begingroup\$ @Leo Ah yes, normally I have to delete the input number before the loop, but I was able to get away without that here. \$\endgroup\$
    – Neil
    Feb 20 at 9:05
2
\$\begingroup\$

Perl 5 + -lF -M5.10.0, 40 bytes

!/[^@F]|(.)\1/&&say for A x($;=<>)..Z x$

Try it online!

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

Brachylog, 13 10 bytes

-3 bytes inspired by a suggestion from Fatalize

gʰj₎∋ᵐ.ẹ~ḅ

Generator solution. Takes input as a list containing a string and an integer. Returns solutions as lists of single-character strings. Try it online!

Explanation

This feels like it should be shorter. Part of the problem is that Brachylog starts getting verbose when you have to deal with anything past one input and one output.

gʰj₎∋ᵐ.ẹ~ḅ
             Input: list containing string and number
gʰ           Wrap the first element in a singleton list
  j₎         Concatenate that list with itself (second element) times
    ∋ᵐ       Select one character from each of those strings
      .      This will be the output
       ẹ     Convert each character to a list of its characters (i.e.
              wrap it in a singleton list)
        ~ḅ   Assert that this is the same as the result of partitioning
              some list into runs of identical elements
             ... and that that list is the output

To help clarify the ending bit: The predicate converts each string in its input into a list of its characters. The predicate finds all runs of consecutive identical values in its input. The .ẹ~ḅ structure applies to the list, then unapplies to that result, then requires that result to be the same list we started with. This is the same as saying that and must give the same result when applied to the list. So:

  • Given the list ["a","b","b"], outputs [["a"],["b"],["b"]] and outputs [["a"],["b","b"]]. Those don't match, so the predicate fails.
  • Given the list ["a","b","a"], outputs [["a"],["b"],["a"]] and outputs [["a"],["b"],["a"]]. Those do match, so the predicate succeeds.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ ḅl₁ᵐ is 1 less byte than s₂ᶠ≠ᵐ to check that no two consecutive elements are equal. \$\endgroup\$
    – Fatalize
    Feb 20 at 12:37
  • 1
    \$\begingroup\$ Thanks! I was able to save a couple more bytes with a variation on that idea. \$\endgroup\$
    – DLosc
    Feb 20 at 17:41
2
\$\begingroup\$

Nekomata, 4 bytes

ŧĉᵐz

Attempt This Online!

ŧĉᵐz    Take input L and n
ŧ       Find an n-tuple of elements of L
 ĉ      Split into runs of equal elements
  ᵐ     For each run:
   z        Check that it contains exactly one element, and take that element
\$\endgroup\$
2
\$\begingroup\$

R, 65 64 bytes

\(L,n,A=expand.grid(rep(list(L),n)))A[!rowSums(A[,-n]==A[,-1]),]

Assuming L is a vector of characters.

-1 byte thanks to @pajonk!

Try it online here!

\$\endgroup\$
2
  • \$\begingroup\$ This needs column selector in [ to work (for me): ato.pxeger.com/… BTW, I also changed ==0 to !, so overall -1 byte :) Also, a link in the post to an online repl (like the one linked above) would be nice. \$\endgroup\$
    – pajonk
    Mar 13 at 19:45
  • 1
    \$\begingroup\$ @pajonk Thanks! Love the trick with the ! The column selector for some reason works on one machine, but I can't replicate it in general, will edit. \$\endgroup\$
    – runr
    Mar 17 at 22:43
1
\$\begingroup\$

Scala 3, 128 bytes

A Port of @Arnold Palmer's Python answer in Scala.


Golfed version. Attempt This Online!

type Q=String;
def g(l:Q,n:Int,c:Q=""):Seq[Q]={if(n==0)Seq("");else{for{a<-l if a.toString!=c;b<-g(l,n-1,a.toString)}yield a+b}}

Ungolfed version. Attempt This Online!

def generateCombinations(l: String, n: Int, c: String = ""): Seq[String] = {
    if (n == 0) Seq("")
    else {
      for {
        a <- l
        if a.toString != c
        b <- generateCombinations(l, n - 1, a.toString)
      } yield a + b
    }
  }
\$\endgroup\$
1
  • \$\begingroup\$ My solution was just golfed quite a bit (-10 bytes). Not sure if it translates to Scala, but wanted to let you know in case you could use that to golf yours. \$\endgroup\$ Feb 20 at 14:39
1
\$\begingroup\$

jq, 67 bytes

def f($n):combinations($n)|join("")|select(test("(.)\\1";"x")|not);

Try it online!

Defines a function f which takes \$L\$ as input and \$n\$ as an argument.

\$\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.