Last active
August 29, 2015 14:25
-
-
Save perey/03d1b7255e20b115dd4d to your computer and use it in GitHub Desktop.
Langford sequence coding challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python3 | |
| """Daily Programmer Challenge #224 [Hard] Langford Strings | |
| https://www.reddit.com/r/dailyprogrammer/ | |
| """ | |
| from string import ascii_uppercase | |
| from copy import copy | |
| def position_pair(token, dist, seq, reverse=False): | |
| r"""Insert a pair of tokens into a sequence. | |
| Available positions in the sequence must be occupied by None. The | |
| pair of tokens will be separated by the given distance. | |
| >>> print(*position_pair(1, 2, | |
| ... [None, 0, None, None, None, None]), | |
| ... sep='\n') | |
| [1, 0, None, 1, None, None] | |
| [None, 0, 1, None, None, 1] | |
| Possible positions will be tested from left to right, unless the | |
| optional reverse argument is True. | |
| >>> print(*position_pair(1, 2, | |
| ... [None, 0, None, None, None, None], | |
| ... reverse=True), | |
| ... sep='\n') | |
| [None, 0, 1, None, None, 1] | |
| [1, 0, None, 1, None, None] | |
| """ | |
| possible_positions = len(seq) - dist - 1 | |
| start_positions = (range(possible_positions - 1, -1, -1) if reverse else | |
| range(possible_positions)) | |
| for start_pos in start_positions: | |
| end_pos = start_pos + dist + 1 | |
| if seq[start_pos] is not None or seq[end_pos] is not None: | |
| continue | |
| result = copy(seq) | |
| result[start_pos] = token | |
| result[end_pos] = token | |
| yield result | |
| def langford(n, alphabet=ascii_uppercase): | |
| r"""Generate all Langford sequences of a given order. | |
| Sequences are represented by tokens from the supplied alphabet | |
| (which defaults to the 26 uppercase ASCII letters). They are not | |
| generated in lexicographic order (alas). | |
| >>> print(*langford(3), sep='\n') | |
| ['B', 'C', 'A', 'B', 'A', 'C'] | |
| ['C', 'A', 'B', 'A', 'C', 'B'] | |
| Langford sequences only exist for order n such that n % 4 = 0 or 3. | |
| >>> print(*langford(2), sep='\n') | |
| Traceback (most recent call last): | |
| ... | |
| ValueError: order-2 Langford sequences are not possible | |
| A ValueError is also raised if the chosen alphabet is too short for | |
| the desired order. | |
| >>> print(*langford(4, '123'), sep='\n') | |
| Traceback (most recent call last): | |
| ... | |
| ValueError: cannot generate order-4 sequences with only 3 tokens | |
| Keyword arguments: | |
| n -- The order of Langford sequences to be generated. | |
| alphabet -- The set of tokens to use for each position. Defaults | |
| to the set of 26 uppercase ASCII letters. | |
| """ | |
| if n % 4 not in (0, 3): | |
| raise ValueError('order-{} Langford sequences are not ' | |
| 'possible'.format(n % 4)) | |
| elif n > len(alphabet): | |
| raise ValueError('cannot generate order-{} sequences with only {} ' | |
| 'tokens'.format(n, len(alphabet))) | |
| def add_another_token(pos, seq_so_far): | |
| """Position another token in the sequence.""" | |
| for intermediate_seq in position_pair(alphabet[pos], pos + 1, | |
| seq_so_far, reverse=True): | |
| if pos == 0: | |
| yield intermediate_seq | |
| else: | |
| for seq in add_another_token(pos - 1, intermediate_seq): | |
| yield seq | |
| empty_seq = [None] * (2 * n) | |
| for seq in add_another_token(n - 1, empty_seq): | |
| yield seq | |
| if __name__ == '__main__': | |
| import doctest | |
| doctest.testmod() | |
| # OEIS sequence A014552. | |
| expected_lengths = [0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0] | |
| for n, expect_length in enumerate(expected_lengths): | |
| try: | |
| length = len(list(langford(n + 1))) | |
| except ValueError: | |
| length = 0 | |
| # Since we generate sequences both forwards and backwards, whereas the | |
| # OEIS list only counts reversed sequences once, double the expected | |
| # length. | |
| expect_length *= 2 | |
| assert expect_length == length, ('got {} order-{} sequences, ' | |
| 'expected {}'.format(length, n + 1, | |
| expect_length)) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python3 | |
| """Daily Programmer Challenge #224 [Hard] Langford Strings | |
| https://www.reddit.com/r/dailyprogrammer/ | |
| """ | |
| from string import ascii_uppercase | |
| from copy import copy | |
| def langford(n, alphabet=ascii_uppercase): | |
| r"""Generate all Langford sequences of a given order. | |
| Sequences are generated in lexicographic order, according to the | |
| order of the supplied alphabet (which defaults to the 26 uppercase | |
| ASCII letters). | |
| >>> print(*langford(3), sep='\n') | |
| ['B', 'C', 'A', 'B', 'A', 'C'] | |
| ['C', 'A', 'B', 'A', 'C', 'B'] | |
| Langford sequences only exist for order n such that n % 4 = 0 or 3. | |
| >>> print(*langford(2), sep='\n') | |
| Traceback (most recent call last): | |
| ... | |
| ValueError: order-2 Langford sequences are not possible | |
| A ValueError is also raised if the chosen alphabet is too short for | |
| the desired order. | |
| >>> print(*langford(4, '123'), sep='\n') | |
| Traceback (most recent call last): | |
| ... | |
| ValueError: cannot generate order-4 sequences with only 3 tokens | |
| Keyword arguments: | |
| n -- The order of Langford sequences to be generated. | |
| alphabet -- The set of tokens to use for each position. Defaults | |
| to the set of 26 uppercase ASCII letters. | |
| """ | |
| if n % 4 not in (0, 3): | |
| raise ValueError('order-{} Langford sequences are not ' | |
| 'possible'.format(n % 4)) | |
| elif n > len(alphabet): | |
| raise ValueError('cannot generate order-{} sequences with only {} ' | |
| 'tokens'.format(n, len(alphabet))) | |
| def fill_sequence(seq, tokens): | |
| """Fill each position with tokens that can occupy it.""" | |
| # Find the first empty position. | |
| first_empty = seq.index(None) | |
| for pos, candidate_token in enumerate(tokens): | |
| dist = alphabet.index(candidate_token) + 2 | |
| if first_empty + dist >= len(seq): | |
| # This token can't go anywhere in the sequence, and therefore | |
| # no later one (with a necessarily greater distance between its | |
| # two occurrences) will be able to either. | |
| break | |
| elif seq[first_empty + dist] == None: | |
| # It fits! | |
| new_seq = copy(seq) | |
| new_seq[first_empty] = candidate_token | |
| new_seq[first_empty + dist] = candidate_token | |
| if len(tokens) == 1: | |
| # Sequence is full now. | |
| yield new_seq | |
| else: | |
| # Remove this token from those available. | |
| remaining_tokens = copy(tokens) | |
| del remaining_tokens[pos] | |
| for filled_seq in fill_sequence(new_seq, remaining_tokens): | |
| yield filled_seq | |
| empty_seq = [None] * (2 * n) | |
| for seq in fill_sequence(empty_seq, list(alphabet[:n])): | |
| yield seq | |
| if __name__ == '__main__': | |
| import doctest | |
| doctest.testmod() | |
| # OEIS sequence A014552. | |
| expected_lengths = [0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0] | |
| for n, expect_length in enumerate(expected_lengths): | |
| try: | |
| length = len(list(langford(n + 1))) | |
| except ValueError: | |
| length = 0 | |
| # Since we generate sequences both forwards and backwards, whereas the | |
| # OEIS list only counts reversed sequences once, double the expected | |
| # length. | |
| expect_length *= 2 | |
| assert expect_length == length, ('got {} order-{} sequences, ' | |
| 'expected {}'.format(length, n + 1, | |
| expect_length)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| >>> for seq in langford(4): | |
| ... print(''.join(seq)) | |
| ... | |
| BCDBACAD | |
| DACABDCB | |
| >>> for seq in langford(8): | |
| ... print(''.join(seq)) | |
| ... | |
| AEADFGHEDBCFBGCH | |
| AEAFDGHECDFBCGBH | |
| CEFDCGHEDFABAGBH | |
| CFDECGHDFEABAGBH | |
| ACAFGCHEBDFBGEDH | |
| AEAFGCHEDCFBGDBH | |
| DAFAGDHCEFBCGBEH | |
| DAFAGDHEBFCBGECH | |
| AFACGEHCFDBEGBDH | |
| FAEAGDHFECDBGCBH | |
| ACAGECHFDBEGBDFH | |
| DBEGBDHFECAGACFH | |
| AEAGCFHECDBGFBDH | |
| DEFGCDHECFBGABAH | |
| CFBGCBHEFDAGAEDH | |
| DFAGADHEFBCGBECH | |
| FBEGBDHFECDGACAH | |
| FCEGDCHFEDBGABAH | |
| CAGACEHFDBGEBDFH | |
| DBGEBDHFCEGACAFH | |
| CAGACFHEBDGBFEDH | |
| BEGBCFHECDGAFADH | |
| BEGBFCHEDCGFADAH | |
| FBGDBEHFDCGEACAH | |
| AGACEFHCDGEBFDBH | |
| DGECFDHCEGBFABAH | |
| CGBFCBHDEGFADAEH | |
| DGAFADHECGFBCEBH | |
| GADAEFHDGCEBFCBH | |
| GBDEBFHDGECAFACH | |
| GCDEFCHDGEBFABAH | |
| GBDFBEHDGCFEACAH | |
| ADAEFHDGCEBFCBHG | |
| BDEBFHDGECAFACHG | |
| CDEFCHDGEBFABAHG | |
| BDFBEHDGCFEACAHG | |
| ADAEGHDCFEBCGBHF | |
| AEAFGHBEDBFCGDHC | |
| BDFBGHDEAFACGEHC | |
| EAFAGHEBDFBCGDHC | |
| AFACGHDCFEBDGBHE | |
| BFDBGHCDFECAGAHE | |
| BFCBGHCEFADAGEHD | |
| EBDGBHEDFCAGACHF | |
| AEAGCHFECBDGBFHD | |
| CDFGCHDEAFAGBEHB | |
| AFAGDHCEFDCGBEHB | |
| AFAGBHEBFCDGECHD | |
| FBCGBHCFDEAGADHE | |
| FDAGAHDFCEBGCBHE | |
| CAGACHDEFBGDBEHF | |
| CAGACHFDBEGBDFHE | |
| CEGDCHFEDAGABFHB | |
| CFGBCHBDFEGADAHE | |
| BFGBDHECFDGCEAHA | |
| EFGCDHECFDGABAHB | |
| FBGEBHDFCEGDCAHA | |
| FDGECHDFCEGABAHB | |
| BGCBEHCDFGEADAHF | |
| AGADEHFCDGECBFHB | |
| AGABFHBECGDFCEHD | |
| AGADFHCEDGCFBEHB | |
| BGEBFHCDEGCFDAHA | |
| AGAFCHDECGFDBEHB | |
| AGAFBHEBDGFCEDHC | |
| CGDFCHEDBGFBEAHA | |
| EGAFAHECDGFCBDHB | |
| EGDFCHEDCGFABAHB | |
| FGADAHEFDGBCEBHC | |
| FGCDEHCFDGEABAHB | |
| GADAEHFDGBECBFHC | |
| GBDEBHFDGEACAFHC | |
| GACAFHCDGEBFDBHE | |
| GACAFHCEGBDFBEHD | |
| GBCFBHCDGEFADAHE | |
| GDAFAHDEGBFCBEHC | |
| GEAFAHDEGCFDBCHB | |
| GECFDHCEGDFABAHB | |
| GBFCBHECGFDAEAHD | |
| GDFCEHDCGFEABAHB | |
| ADAEHFDGBECBFHCG | |
| BDEBHFDGEACAFHCG | |
| ACAFHCDGEBFDBHEG | |
| ACAFHCEGBDFBEHDG | |
| BCFBHCDGEFADAHEG | |
| DAFAHDEGBFCBEHCG | |
| EAFAHDEGCFDBCHBG | |
| ECFDHCEGDFABAHBG | |
| BFCBHECGFDAEAHDG | |
| DFCEHDCGFEABAHBG | |
| ACAFHCGDBEFBDHGE | |
| AFACHEGCFBDEBHGD | |
| AFAEHDGCFEDCBHGB | |
| FAEAHDGFEBDCBHGC | |
| ACAGHCEBFDBGEHDF | |
| DEFGHDAEAFCGBHCB | |
| DFCGHDCBFEBGAHAE | |
| FCEGHCBFEBDGAHAD | |
| BEGBHCDEFCGDAHAF | |
| EAGAHCEDFCGBDHBF | |
| ECGDHCEFDAGABHFB | |
| BDGBHFDAEAGCFHEC | |
| BEGBHFAEADGCFHDC | |
| DFGBHDBCFEGCAHAE | |
| BFGBHAEAFDGCEHDC | |
| EFGAHAECFDGCBHDB | |
| FDGAHADFCEGBCHBE | |
| FAGAHCDFECGDBHEB | |
| FDGAHADFEBGCBHEC | |
| FAGAHBEFBDGCEHDC | |
| FDGEHBDFBEGCAHAC | |
| AGACHDECFGDBEHBF | |
| AGABHEBDFGCEDHCF | |
| BGDBHECDFGCEAHAF | |
| AGABHEBFCGDECHFD | |
| AGADHECFDGCEBHFB | |
| DGEBHDBFEGACAHFC | |
| EGBDHBEFDGACAHFC | |
| AGABHFBCEGDCFHED | |
| EGDFHBEDBGFCAHAC | |
| FGEAHADFEGCDBHCB | |
| FGEBHDBFEGDCAHAC | |
| GACAHECFGBDEBHFD | |
| GDBEHBDFGEACAHFC | |
| GADAHFCDGECBFHBE | |
| GDBFHBDCGEFCAHAE | |
| GEFAHADEGFCDBHCB | |
| GEFBHDBEGFDCAHAC | |
| ACAHECFGBDEBHFDG | |
| DBEHBDFGEACAHFCG | |
| ADAHFCDGECBFHBEG | |
| DBFHBDCGEFCAHAEG | |
| EFAHADEGFCDBHCBG | |
| EFBHDBEGFDCAHACG | |
| ACAHFCGBDEBFHDGE | |
| AEAHFBGEBCDFHCGD | |
| DBFHBDGEAFACHEGC | |
| CEFHCBGEBFDAHAGD | |
| CEFHCDGEBFDBHAGA | |
| DFAHADGCFEBCHBGE | |
| CFBHCBGEFADAHEGD | |
| AFAHBEGBFCDEHCGD | |
| FBEHBCGFECDAHAGD | |
| AEAHDGCEFDCBHGBF | |
| EBDHBGEDFACAHGCF | |
| CEFHCGAEAFDBHGBD | |
| AFAHBGDBFECDHGCE | |
| EFAHAGEBFDBCHGDC | |
| FDAHAGDFBECBHGCE | |
| FBCHBGCFEADAHGED | |
| DEGHADAEFCGBHCBF | |
| ECGHBCEBFDGAHADF | |
| CDGHCBDFBEGAHAFE | |
| ECGHDCEFBDGBHAFA | |
| DBGHBDFAEAGCHFEC | |
| FCGHACAFDEGBHDBE | |
| FBGHBCDFECGDHAEA | |
| DGAHADCEFGCBHEBF | |
| DGCHEDCFBGEBHAFA | |
| DGEHADAFEGBCHBFC | |
| EGBHCBEFCGDAHAFD | |
| AGAHBDFBEGDCHFEC | |
| DGAHADFBEGBCHFEC | |
| CGEHCAFAEGDBHFBD | |
| DGCHFDCBEGBFHAEA | |
| EGDHFBEDBGCFHACA | |
| GCAHACDFGEBDHBFE | |
| GBCHBDCFGEDAHAFE | |
| GEAHACFEGCDBHFBD | |
| GEBHFBCEGDCFHADA | |
| GCFHACAEGFDBHEBD | |
| GDFHBEDBGFCEHACA | |
| CAHACDFGEBDHBFEG | |
| BCHBDCFGEDAHAFEG | |
| EAHACFEGCDBHFBDG | |
| EBHFBCEGDCFHADAG | |
| CFHACAEGFDBHEBDG | |
| DFHBEDBGFCEHACAG | |
| CAHACDGEFBDHBEGF | |
| BCHBDCGEFDAHAEGF | |
| CAHACFGBDEBHFDGE | |
| DEHFCDGECBFHBAGA | |
| CFHACAGDFEBHDBGE | |
| CFHACAGEFBDHBEGD | |
| BFHBECGDFCEHDAGA | |
| DFHCEDGCFBEHBAGA | |
| FAHAECGFDCEHBDGB | |
| FCHDECGFDBEHBAGA | |
| FBHEBDGFCEDHCAGA | |
| CAHACGEBFDBHEGDF | |
| CDHECGDBFEBHAGAF | |
| CEHBCGBEFDAHAGDF | |
| BEHBDGCEFDCHAGAF | |
| EBHCBGECFDAHAGDF | |
| BDHBCGDFCEAHAGFE | |
| CDHECGDFAEAHBGFB | |
| EAHACGEFCBDHBGFD | |
| CDHFCGDAEAFHBGEB | |
| CEHFCGAEADFHBGDB | |
| BFHBAGADFECHDGCE | |
| FBHDBGCFDECHAGAE | |
| FAHADGCFEDCHBGEB | |
| DAHAGDBEFBCHGECF | |
| EAHAGBEFBCDHGCFD | |
| BCHBGCFAEADHGFED | |
| FDHEGBDFBECHGACA | |
| CGHBCDBEFGDHAEAF | |
| BGHBCDEFCGDHEAFA | |
| DGHBEDBFCGEHCAFA | |
| EGHDBFEBDGCHFACA | |
| GBHABAEFGCDHECFD | |
| GDHAEADFGCEHBCFB | |
| GBHABAFDGECHDFCE | |
| GBHCBDFCGEDHAFAE | |
| GCHEBCFBGEDHAFAD | |
| GEHADAFEGDCHBFCB | |
| GDHEBFDBGECHFACA | |
| GEHBDFBEGDCHFACA | |
| GCHFACAEGDFHBEDB | |
| GCHFBCEBGDFHEADA | |
| BHABAEFGCDHECFDG | |
| DHAEADFGCEHBCFBG | |
| BHABAFDGECHDFCEG | |
| BHCBDFCGEDHAFAEG | |
| CHEBCFBGEDHAFADG | |
| EHADAFEGDCHBFCBG | |
| DHEBFDBGECHFACAG | |
| EHBDFBEGDCHFACAG | |
| CHFACAEGDFHBEDBG | |
| CHFBCEBGDFHEADAG | |
| BHABAEGDFCHEDCGF | |
| CHBECBGDFEHADAGF | |
| BHABAFGCDEHCFDGE | |
| BHDBCFGDCEHAFAGE | |
| AHAEBFGBDEHCFDGC | |
| CHDECFGDBEHBFAGA | |
| BHEBDFGCEDHCFAGA | |
| AHADFCGEDCHFBEGB | |
| BHEBFCGDECHFDAGA | |
| DHECFDGCEBHFBAGA | |
| BHFBCEGDCFHEDAGA | |
| FHADAEGFDCHEBCGB | |
| BHABAGECFDHCEGDF | |
| AHACDGECFDHBEGBF | |
| BHABAGDFCEHDCGFE | |
| AHAECGDFCEHDBGFB | |
| EHADAGEFDBHCBGFC | |
| BHFBAGADEFHCDGEC | |
| EHFDBGEBDFHCAGAC | |
| FHEBDGBFEDHCAGAC | |
| EHBCGBECFDHAGADF | |
| EHDAGAEDFCHBGCBF | |
| DHCEGDCFBEHBGAFA | |
| BHEBGCDFECHDGAFA | |
| BHEBGAFAEDHCGFDC | |
| DHFBGDBCEFHCGAEA | |
| FHCAGACFDEHBGDBE | |
| DHEGADAFECHGBCFB | |
| EHAGACEFDCHGBDFB | |
| EHBGDBEFCDHGCAFA | |
| CHDGCBFDBEHGAFAE | |
| CHEGCAFAEDHGBFDB | |
| CHDGCFBDEBHGFAEA | |
| FHBGCBEFCDHGEADA | |
| GHACAEFCGDHEBFDB | |
| GHABAFBEGDHCFEDC | |
| GHCAFACEGDHFBEDB | |
| GHBCFBECGDHFEADA | |
| HACAEFCGDHEBFDBG | |
| HABAFBEGDHCFEDCG | |
| HCAFACEGDHFBEDBG | |
| HBCFBECGDHFEADAG | |
| HBECBFGCEHDAFAGD | |
| HEADAFGEDHBCFBGC | |
| HABAFBGECHDFCEGD | |
| HBDFBEGDCHFECAGA | |
| HACAEGCDFHEBDGBF | |
| HADAFGCDEHCFBGEB | |
| HDAFAGDCEHFCBGEB | |
| HDEFBGDBEHFCAGAC | |
| HFACAGECFHDBEGBD | |
| HFDBEGBDFHECAGAC | |
| HABAGBDEFHCDGECF | |
| HACAGDCEFHDBGEBF | |
| HCEBGCBFEHDAGAFD | |
| HDEAGADFEHBCGBFC | |
| HABAGBFCEHDCGFED | |
| HDBFGBDCEHFCGAEA | |
| HFCAGACEFHDBGEBD | |
| HFDBGEBDFHCEGACA | |
| HBCGBDCEFHDGAEAF | |
| HDBGEBDFCHEGCAFA | |
| HCEGBCFBEHDGAFAD | |
| HEBGCBFECHDGAFAD | |
| HBDGBFCDEHCGFAEA | |
| HDEGBFDBEHCGFACA | |
| HBGABAEFDHGCEDFC | |
| HBGABAFDEHGCDFEC | |
| HBGCBFDCEHGDFAEA | |
| HCGBFCBDEHGFDAEA | |
| >>> for n, seq in enumerate(langford(20)): | |
| ... print(''.join(seq)) | |
| ... if n == 9: | |
| ... break | |
| ... | |
| FGHBCDBFCGDHLMNPQSTROIJKELAMANEIPJQKOSRT | |
| GDHFBCDBGCFHLMNPQSTROIJKELAMANEIPJQKOSRT | |
| FHCGDBCFBDHGLMNPQSTROIJKELAMANEIPJQKOSRT | |
| GHDBFCBDGCHFLMNPQSTROIJKELAMANEIPJQKOSRT | |
| HFCGBDCBFHDGLMNPQSTROIJKELAMANEIPJQKOSRT | |
| HDGCFBDCBHGFLMNPQSTROIJKELAMANEIPJQKOSRT | |
| EIGCDBECBDGILMNPQSTROHJKFLAMANHFPJQKOSRT | |
| EIGDBCEBDCGILMNPQSTROHJKFLAMANHFPJQKOSRT | |
| FIGEABAFBEGILMNPQSTROHJKCLDMCNHDPJQKOSRT | |
| GIDBECBDGCEILMNPQSTROHJKFLAMANHFPJQKOSRT |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| >>> for seq in langford(4): | |
| ... print(''.join(seq)) | |
| ... | |
| BCDBACAD | |
| DACABDCB | |
| >>> for seq in langford(8): | |
| ... print(''.join(seq)) | |
| ... | |
| ACAFGCHEBDFBGEDH | |
| ACAFHCDGEBFDBHEG | |
| ACAFHCEGBDFBEHDG | |
| ACAFHCGDBEFBDHGE | |
| ACAGECHFDBEGBDFH | |
| ACAGHCEBFDBGEHDF | |
| ACAHECFGBDEBHFDG | |
| ACAHFCGBDEBFHDGE | |
| ADAEFHDGCEBFCBHG | |
| ADAEGHDCFEBCGBHF | |
| ADAEHFDGBECBFHCG | |
| ADAHFCDGECBFHBEG | |
| AEADFGHEDBCFBGCH | |
| AEAFDGHECDFBCGBH | |
| AEAFGCHEDCFBGDBH | |
| AEAFGHBEDBFCGDHC | |
| AEAGCFHECDBGFBDH | |
| AEAGCHFECBDGBFHD | |
| AEAHDGCEFDCBHGBF | |
| AEAHFBGEBCDFHCGD | |
| AFACGEHCFDBEGBDH | |
| AFACGHDCFEBDGBHE | |
| AFACHEGCFBDEBHGD | |
| AFAEHDGCFEDCBHGB | |
| AFAGBHEBFCDGECHD | |
| AFAGDHCEFDCGBEHB | |
| AFAHBEGBFCDEHCGD | |
| AFAHBGDBFECDHGCE | |
| AGABFHBECGDFCEHD | |
| AGABHEBDFGCEDHCF | |
| AGABHEBFCGDECHFD | |
| AGABHFBCEGDCFHED | |
| AGACEFHCDGEBFDBH | |
| AGACHDECFGDBEHBF | |
| AGADEHFCDGECBFHB | |
| AGADFHCEDGCFBEHB | |
| AGADHECFDGCEBHFB | |
| AGAFBHEBDGFCEDHC | |
| AGAFCHDECGFDBEHB | |
| AGAHBDFBEGDCHFEC | |
| AHACDGECFDHBEGBF | |
| AHADFCGEDCHFBEGB | |
| AHAEBFGBDEHCFDGC | |
| AHAECGDFCEHDBGFB | |
| BCFBHCDGEFADAHEG | |
| BCHBDCFGEDAHAFEG | |
| BCHBDCGEFDAHAEGF | |
| BCHBGCFAEADHGFED | |
| BDEBFHDGECAFACHG | |
| BDEBHFDGEACAFHCG | |
| BDFBEHDGCFEACAHG | |
| BDFBGHDEAFACGEHC | |
| BDGBHFDAEAGCFHEC | |
| BDHBCGDFCEAHAGFE | |
| BEGBCFHECDGAFADH | |
| BEGBFCHEDCGFADAH | |
| BEGBHCDEFCGDAHAF | |
| BEGBHFAEADGCFHDC | |
| BEHBDGCEFDCHAGAF | |
| BFCBGHCEFADAGEHD | |
| BFCBHECGFDAEAHDG | |
| BFDBGHCDFECAGAHE | |
| BFGBDHECFDGCEAHA | |
| BFGBHAEAFDGCEHDC | |
| BFHBAGADFECHDGCE | |
| BFHBECGDFCEHDAGA | |
| BGCBEHCDFGEADAHF | |
| BGDBHECDFGCEAHAF | |
| BGEBFHCDEGCFDAHA | |
| BGHBCDEFCGDHEAFA | |
| BHABAEFGCDHECFDG | |
| BHABAEGDFCHEDCGF | |
| BHABAFDGECHDFCEG | |
| BHABAFGCDEHCFDGE | |
| BHABAGDFCEHDCGFE | |
| BHABAGECFDHCEGDF | |
| BHCBDFCGEDHAFAEG | |
| BHDBCFGDCEHAFAGE | |
| BHEBDFGCEDHCFAGA | |
| BHEBFCGDECHFDAGA | |
| BHEBGAFAEDHCGFDC | |
| BHEBGCDFECHDGAFA | |
| BHFBAGADEFHCDGEC | |
| BHFBCEGDCFHEDAGA | |
| CAGACEHFDBGEBDFH | |
| CAGACFHEBDGBFEDH | |
| CAGACHDEFBGDBEHF | |
| CAGACHFDBEGBDFHE | |
| CAHACDFGEBDHBFEG | |
| CAHACDGEFBDHBEGF | |
| CAHACFGBDEBHFDGE | |
| CAHACGEBFDBHEGDF | |
| CDEFCHDGEBFABAHG | |
| CDFGCHDEAFAGBEHB | |
| CDGHCBDFBEGAHAFE | |
| CDHECGDBFEBHAGAF | |
| CDHECGDFAEAHBGFB | |
| CDHFCGDAEAFHBGEB | |
| CEFDCGHEDFABAGBH | |
| CEFHCBGEBFDAHAGD | |
| CEFHCDGEBFDBHAGA | |
| CEFHCGAEAFDBHGBD | |
| CEGDCHFEDAGABFHB | |
| CEHBCGBEFDAHAGDF | |
| CEHFCGAEADFHBGDB | |
| CFBGCBHEFDAGAEDH | |
| CFBHCBGEFADAHEGD | |
| CFDECGHDFEABAGBH | |
| CFGBCHBDFEGADAHE | |
| CFHACAEGFDBHEBDG | |
| CFHACAGDFEBHDBGE | |
| CFHACAGEFBDHBEGD | |
| CGBFCBHDEGFADAEH | |
| CGDFCHEDBGFBEAHA | |
| CGEHCAFAEGDBHFBD | |
| CGHBCDBEFGDHAEAF | |
| CHBECBGDFEHADAGF | |
| CHDECFGDBEHBFAGA | |
| CHDGCBFDBEHGAFAE | |
| CHDGCFBDEBHGFAEA | |
| CHEBCFBGEDHAFADG | |
| CHEGCAFAEDHGBFDB | |
| CHFACAEGDFHBEDBG | |
| CHFBCEBGDFHEADAG | |
| DAFAGDHCEFBCGBEH | |
| DAFAGDHEBFCBGECH | |
| DAFAHDEGBFCBEHCG | |
| DAHAGDBEFBCHGECF | |
| DBEGBDHFECAGACFH | |
| DBEHBDFGEACAHFCG | |
| DBFHBDCGEFCAHAEG | |
| DBFHBDGEAFACHEGC | |
| DBGEBDHFCEGACAFH | |
| DBGHBDFAEAGCHFEC | |
| DEFGCDHECFBGABAH | |
| DEFGHDAEAFCGBHCB | |
| DEGHADAEFCGBHCBF | |
| DEHFCDGECBFHBAGA | |
| DFAGADHEFBCGBECH | |
| DFAHADGCFEBCHBGE | |
| DFCEHDCGFEABAHBG | |
| DFCGHDCBFEBGAHAE | |
| DFGBHDBCFEGCAHAE | |
| DFHBEDBGFCEHACAG | |
| DFHCEDGCFBEHBAGA | |
| DGAFADHECGFBCEBH | |
| DGAHADCEFGCBHEBF | |
| DGAHADFBEGBCHFEC | |
| DGCHEDCFBGEBHAFA | |
| DGCHFDCBEGBFHAEA | |
| DGEBHDBFEGACAHFC | |
| DGECFDHCEGBFABAH | |
| DGEHADAFEGBCHBFC | |
| DGHBEDBFCGEHCAFA | |
| DHAEADFGCEHBCFBG | |
| DHCEGDCFBEHBGAFA | |
| DHEBFDBGECHFACAG | |
| DHECFDGCEBHFBAGA | |
| DHEGADAFECHGBCFB | |
| DHFBGDBCEFHCGAEA | |
| EAFAGHEBDFBCGDHC | |
| EAFAHDEGCFDBCHBG | |
| EAGAHCEDFCGBDHBF | |
| EAHACFEGCDBHFBDG | |
| EAHACGEFCBDHBGFD | |
| EAHAGBEFBCDHGCFD | |
| EBDGBHEDFCAGACHF | |
| EBDHBGEDFACAHGCF | |
| EBHCBGECFDAHAGDF | |
| EBHFBCEGDCFHADAG | |
| ECFDHCEGDFABAHBG | |
| ECGDHCEFDAGABHFB | |
| ECGHBCEBFDGAHADF | |
| ECGHDCEFBDGBHAFA | |
| EFAHADEGFCDBHCBG | |
| EFAHAGEBFDBCHGDC | |
| EFBHDBEGFDCAHACG | |
| EFGAHAECFDGCBHDB | |
| EFGCDHECFDGABAHB | |
| EGAFAHECDGFCBDHB | |
| EGBDHBEFDGACAHFC | |
| EGBHCBEFCGDAHAFD | |
| EGDFCHEDCGFABAHB | |
| EGDFHBEDBGFCAHAC | |
| EGDHFBEDBGCFHACA | |
| EGHDBFEBDGCHFACA | |
| EHADAFEGDCHBFCBG | |
| EHADAGEFDBHCBGFC | |
| EHAGACEFDCHGBDFB | |
| EHBCGBECFDHAGADF | |
| EHBDFBEGDCHFACAG | |
| EHBGDBEFCDHGCAFA | |
| EHDAGAEDFCHBGCBF | |
| EHFDBGEBDFHCAGAC | |
| FAEAGDHFECDBGCBH | |
| FAEAHDGFEBDCBHGC | |
| FAGAHBEFBDGCEHDC | |
| FAGAHCDFECGDBHEB | |
| FAHADGCFEDCHBGEB | |
| FAHAECGFDCEHBDGB | |
| FBCGBHCFDEAGADHE | |
| FBCHBGCFEADAHGED | |
| FBEGBDHFECDGACAH | |
| FBEHBCGFECDAHAGD | |
| FBGDBEHFDCGEACAH | |
| FBGEBHDFCEGDCAHA | |
| FBGHBCDFECGDHAEA | |
| FBHDBGCFDECHAGAE | |
| FBHEBDGFCEDHCAGA | |
| FCEGDCHFEDBGABAH | |
| FCEGHCBFEBDGAHAD | |
| FCGHACAFDEGBHDBE | |
| FCHDECGFDBEHBAGA | |
| FDAGAHDFCEBGCBHE | |
| FDAHAGDFBECBHGCE | |
| FDGAHADFCEGBCHBE | |
| FDGAHADFEBGCBHEC | |
| FDGECHDFCEGABAHB | |
| FDGEHBDFBEGCAHAC | |
| FDHEGBDFBECHGACA | |
| FGADAHEFDGBCEBHC | |
| FGCDEHCFDGEABAHB | |
| FGEAHADFEGCDBHCB | |
| FGEBHDBFEGDCAHAC | |
| FHADAEGFDCHEBCGB | |
| FHBGCBEFCDHGEADA | |
| FHCAGACFDEHBGDBE | |
| FHEBDGBFEDHCAGAC | |
| GACAFHCDGEBFDBHE | |
| GACAFHCEGBDFBEHD | |
| GACAHECFGBDEBHFD | |
| GADAEFHDGCEBFCBH | |
| GADAEHFDGBECBFHC | |
| GADAHFCDGECBFHBE | |
| GBCFBHCDGEFADAHE | |
| GBCHBDCFGEDAHAFE | |
| GBDEBFHDGECAFACH | |
| GBDEBHFDGEACAFHC | |
| GBDFBEHDGCFEACAH | |
| GBFCBHECGFDAEAHD | |
| GBHABAEFGCDHECFD | |
| GBHABAFDGECHDFCE | |
| GBHCBDFCGEDHAFAE | |
| GCAHACDFGEBDHBFE | |
| GCDEFCHDGEBFABAH | |
| GCFHACAEGFDBHEBD | |
| GCHEBCFBGEDHAFAD | |
| GCHFACAEGDFHBEDB | |
| GCHFBCEBGDFHEADA | |
| GDAFAHDEGBFCBEHC | |
| GDBEHBDFGEACAHFC | |
| GDBFHBDCGEFCAHAE | |
| GDFCEHDCGFEABAHB | |
| GDFHBEDBGFCEHACA | |
| GDHAEADFGCEHBCFB | |
| GDHEBFDBGECHFACA | |
| GEAFAHDEGCFDBCHB | |
| GEAHACFEGCDBHFBD | |
| GEBHFBCEGDCFHADA | |
| GECFDHCEGDFABAHB | |
| GEFAHADEGFCDBHCB | |
| GEFBHDBEGFDCAHAC | |
| GEHADAFEGDCHBFCB | |
| GEHBDFBEGDCHFACA | |
| GHABAFBEGDHCFEDC | |
| GHACAEFCGDHEBFDB | |
| GHBCFBECGDHFEADA | |
| GHCAFACEGDHFBEDB | |
| HABAFBEGDHCFEDCG | |
| HABAFBGECHDFCEGD | |
| HABAGBDEFHCDGECF | |
| HABAGBFCEHDCGFED | |
| HACAEFCGDHEBFDBG | |
| HACAEGCDFHEBDGBF | |
| HACAGDCEFHDBGEBF | |
| HADAFGCDEHCFBGEB | |
| HBCFBECGDHFEADAG | |
| HBCGBDCEFHDGAEAF | |
| HBDFBEGDCHFECAGA | |
| HBDGBFCDEHCGFAEA | |
| HBECBFGCEHDAFAGD | |
| HBGABAEFDHGCEDFC | |
| HBGABAFDEHGCDFEC | |
| HBGCBFDCEHGDFAEA | |
| HCAFACEGDHFBEDBG | |
| HCEBGCBFEHDAGAFD | |
| HCEGBCFBEHDGAFAD | |
| HCGBFCBDEHGFDAEA | |
| HDAFAGDCEHFCBGEB | |
| HDBFGBDCEHFCGAEA | |
| HDBGEBDFCHEGCAFA | |
| HDEAGADFEHBCGBFC | |
| HDEFBGDBEHFCAGAC | |
| HDEGBFDBEHCGFACA | |
| HEADAFGEDHBCFBGC | |
| HEBGCBFECHDGAFAD | |
| HFACAGECFHDBEGBD | |
| HFCAGACEFHDBGEBD | |
| HFDBEGBDFHECAGAC | |
| HFDBGEBDFHCEGACA | |
| >>> for n, seq in enumerate(langford(20)): | |
| ... print(''.join(seq)) | |
| ... if n == 9: | |
| ... break | |
| ... | |
| ABACBDECFPDOENQFLSTRIKMGJHPONLIGQKHJMSRT | |
| ABACBDECFPDOENQFLSTRIMHJKGPONLIHQGJMKSRT | |
| ABACBDECFPDOENQFLSTRIMJGKHPONLIGQJHMKSRT | |
| ABACBDECFPDOENQFLSTRIMKGHJPONLIGQHKMJSRT | |
| ABACBDECFPDOENQFLSTRJHMKIGPONLHJQGIKMSRT | |
| ABACBDECFPDOENQFLSTRJMGIKHPONLGJQIHMKSRT | |
| ABACBDECFPDOENQFLSTRMHJGKIPONLHGQJMIKSRT | |
| ABACBDECFPDOENQFLSTRMIGKHJPONLGIQHMKJSRT | |
| ABACBDECFPDOENQFLTRSIKMGJHPONLIGQKHJMRTS | |
| ABACBDECFPDOENQFLTRSIMHJKGPONLIHQGJMKRTS |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment