72 lines
1.5 KiB
Text
72 lines
1.5 KiB
Text
10 DEFINT A-Z
|
|
20 K = 10: N = 4
|
|
30 DIM A(K*N), S(K^N+N), T(5), P(5), V(K^N\8)
|
|
40 GOSUB 200
|
|
50 PRINT "Length: ",S
|
|
60 PRINT "First 130:"
|
|
70 FOR I=0 TO 129: PRINT USING "#";S(I);: NEXT
|
|
80 PRINT: PRINT "Last 130:"
|
|
90 FOR I=S-130 TO S-1: PRINT USING "#";S(I);: NEXT
|
|
100 PRINT
|
|
110 GOSUB 600
|
|
120 PRINT "Reversing...": GOSUB 500: GOSUB 600: GOSUB 500
|
|
130 PRINT USING "Replacing 4444'th element (#):";S(4443)
|
|
140 S(4443) = -1 : REM 0-indexed, and using integers
|
|
150 GOSUB 600
|
|
160 END
|
|
200 REM Generate De Bruijn sequence given K and N
|
|
210 T(R) = 1: P(R) = 1
|
|
220 IF T(R) > N GOTO 380
|
|
230 A(T(R)) = A(T(R)-P(R))
|
|
240 R = R+1
|
|
250 T(R) = T(R-1)+1
|
|
260 P(R) = P(R-1)
|
|
270 GOSUB 220
|
|
280 R = R-1
|
|
290 FOR J = A(T(R)-P(R))+1 TO K-1
|
|
300 A(T(R)) = J
|
|
310 R = R+1
|
|
320 T(R) = T(R-1)+1
|
|
330 P(R) = T(R-1)
|
|
340 GOSUB 220
|
|
350 R = R-1
|
|
355 J = A(T(R))
|
|
360 NEXT
|
|
370 RETURN
|
|
380 IF N MOD P(R) THEN RETURN
|
|
390 FOR I = 1 TO P(R)
|
|
400 S(S) = A(I)
|
|
410 S = S+1
|
|
420 NEXT
|
|
430 RETURN
|
|
500 REM Reverse the sequence
|
|
510 FOR I=0 TO S\2
|
|
520 J = S(I)
|
|
530 S(I) = S(S-I)
|
|
540 S(S-I) = J
|
|
550 NEXT
|
|
560 RETURN
|
|
600 REM Validate the sequence (uses bit packing to save memory)
|
|
610 PRINT "Validating...";
|
|
620 FOR I=0 TO N-1: S(S+I)=S(I): NEXT
|
|
630 FOR I=0 TO K^N\8-1: V(I)=0: NEXT
|
|
640 FOR I=0 TO S
|
|
650 P=0
|
|
660 FOR J=0 TO N-1
|
|
662 D=S(I+J)
|
|
663 IF D<0 GOTO 690
|
|
665 P=K*P+D
|
|
669 NEXT J
|
|
670 X=P\8
|
|
680 V(X) = V(X) OR 2^(P AND 7)
|
|
690 NEXT I
|
|
700 M=1
|
|
710 FOR I=0 TO K^N\8-1
|
|
720 IF V(I)=255 GOTO 760
|
|
730 FOR J=0 TO 7
|
|
740 IF (V(I) AND 2^J)=0 THEN M=0: PRINT USING " ####";I*8+J;
|
|
750 NEXT
|
|
760 NEXT
|
|
770 IF M THEN PRINT " none";
|
|
780 PRINT " missing."
|
|
790 RETURN
|