| De Bruijn Sequence |
Back to Tools
The initial application for the de Bruijn sequance for me was a solution posted as comment to an Youtube video from Robin (8-Bit Show And Tell channel). At that time I wasn't aware of the de Bruijn sequence at all. I just developed the idea to efficently store all possible sequences in a compact way. My first attempt with length 3 was easy to generate, just by trail-and-error. I saw there was space for a length 4 sequence too and even there I created the sequance manually.
After the post someone commented that this is a well-known sequence called the de Bruijn sequence.
Another boost:
0 a=4:a$="...MNMNNNNMMMMNNMNMMNM":forb=16to.step.:printmid$(a$,a+b*rnd(.),a);next
(M is the shift+m graphic symbol), N is the shift+n graphic symbol)
The M is the graphic backslash, N the graphic slash (shifted M, N on the keyboard). The se quence gives all 16 possible variations (2^4) of 2 symbols on 4 places by indexing from 4 to 19 (16 + 3 symbols). This index is randomized, selecting one of the 16 different 4 char acter sequences.
The dots are a filler to be able to use variable A (primarily needed as string length) als
o as some offset, because MID$ needs something > 0. A is defined earlier for faster access
, because it is referenced twice, A$ and B only once.
This takes on my PAL C64 171 jiffies or 2.85 seconds.
This seems the maximum possible if keyed in via screen editor (with abbreviations).
If we dismiss the line limit of the screen editor this game could played further as far as
we keep A$ limited to the maximum of 255 characters (the line length is unlimited, but a
re-chaining of the program must not happen).
If an appropriate A$ can be composed, the a possible for A and B would be 7 and 128, givin
g a length of 140 for A$.
This task is left to the readers (or Robin), to push it to the extremes ... ;)
Just for comparison and analysis: Saw @csbruce's MID$ approach later skimming through the comments, but it is limited to a 3 character sequence. The above one accomplishes a 4 char acter sequence by using a overlapping structure of all needed 4 char sequences which have 1 index distance (saving a multiplication too).
The BASIC V2 implementation is not recursive as the high-level implementions on geeksforgeeks.org. To come over recursions, I replaced it with stacks organized as an array. The recursion cannot be replace with a simple loop because it's not a tail-end-recursion.
The first implementation is string-based but it has severe limits because of the maximum length with 255 characters The numerical variant (de-bruijn-a.bas) uses integer arrays, to get an element range limited only by the free Basic memory, which enhances the possible solutions depending on length and base.
See Wikipedia: de Bruijn sequance (Wikipedia: De-Bruijn-Folge - german)
|
|
zurück zur Startseite |