11
\$\begingroup\$

Challenge description

A Langford string of order N is defined as follows:

  • The length of the string is equal to 2*N,
  • The string contains first N letters of the English alphabet, each letter appearing twice,
  • For each pair of the same letters, there are M letters between them, where M is that letter's position in the alphabet (A = 1, B = 2, ..., Z = 26).

For instance, the only two possible Langford strings of order 3 are BCABAC and CABACB. As you can see, in both of these strings there is one letter between two A's, two letters between B's and three letters between C's. Given a positive integer N, output all Langford strings of order N (in any reasonable format: print them one by one separated by a newline, return a list/array...).

Sample inputs / outputs

3: [CABACB, BCABAC]
4: [DACABDCB, BCDBACAD]
5: # no output #
7: [GCFBECBDGFEADA, GBFCBDECGFDAEA, GBDFBCEDGCFAEA, GCAFACDEGBFDBE, GADAFCEDGCBFEB, GACAFDCEGBDFBE, GDAEAFDCGEBCFB, GBDEBFCDGECAFA, EGBFCBEDCGFADA, CGDFCBEDBGFAEA, EGDAFAEDCGBFCB, EGBCFBECDGAFAD, AGABFDBECGDFCE, EGADAFECDGBCFB, AGABEFBCDGECFD, BGDBCEFDCGAEAF, FBGDBCEFDCGAEA, BFGBAEADFCGEDC, CFGACADEFBGDBE, EAGAFBEDBCGFDC, BCGBFCEADAGFED, DAGAFDBECBGFCE, EBGCBFECDAGAFD, CEGDCFBEDBGAFA, CEGBCFBEDAGAFD, BDGBCFDECAGAFE, EFAGACEDFCBGDB, DFAGADEBFCBGEC, AFAGBDEBFCDGEC, DFAGADCEFBCGBE, ECFGBCEBDFAGAD, DEFGADAECFBGCB, CDFGCBDEBFAGAE, EBDGBFEDACAGFC, CDEGCFDAEABGFB, AEAGCDFECBDGBF, FAEAGCDFECBDGB, DFCEGDCBFEBAGA, BFCBGDCEFADAGE, ECFDGCEBDFBAGA, DAFAGDCEBFCBGE, BCFBGCDEAFADGE, AEAFGBDEBCFDGC, ADAFGCDEBCFBGE, AFACEGDCFBEDBG, BFCBEGCDFAEADG, EBFDBGECDFACAG, BEFBCGDECFADAG, EBDFBGEDCAFACG, AEAFCGDECBFDBG, AEADFGCEDBCFBG, ADAEFGDBCEBFCG]
12: # <216288 strings> #

Notes

  • Langford strings of order N can only be produced when N ≡ 0 (mod 4) or N ≡ 3 (mod 4),
  • You can use both lower-case and upper-case letters,
  • You may use subsequent numbers as well (012... or 123... instead of ABC...)
  • Order of strings in which they should appear as output is unspecified,
  • Output can be quite lengthy (for instance, there are over 5 trillion distinct Langford strings of order 20), so your program doesn't actually need to output them all, but it has to work in theory (given enough time and memory).
  • This challenge has been taken from /r/dailyprogrammer, all credit goes to /u/XenophonOfAthens
\$\endgroup\$
4
  • 4
    \$\begingroup\$ There's a closely related challenge in the sandbox. While in no way required it's usually a good idea and probably polite to check there as well for duplicates. \$\endgroup\$ Aug 14, 2016 at 14:17
  • \$\begingroup\$ Can we just output an array of numbers? \$\endgroup\$
    – Leaky Nun
    Aug 14, 2016 at 14:18
  • \$\begingroup\$ @LeakyNun: Sure, why not. I updated the description. \$\endgroup\$
    – shooqie
    Aug 14, 2016 at 14:33
  • 1
    \$\begingroup\$ I refer to this (run the program) \$\endgroup\$
    – Leaky Nun
    Aug 14, 2016 at 14:50

2 Answers 2

3
\$\begingroup\$

CJam (23 bytes)

{,2*e!{__f{\a/1=,(}=},}

Online demo. This is an anonymous block (function) which takes input on the stack and leaves output on the stack in the form of an array of arrays of 0-based sequential integers.

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

Brachylog, 43 bytes

:1fd.
ybB:1jp.,B:[.]z:2a
:3f-+$_~h?
t:.m~h?

Try it 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.