Thanks, Dodicat!
¡Señor Valdez! That's a very good, very interesting site. Thank you very much! I was hoping I could get in touch with some math enthusiasts and professionals because I love these problems. Of course, I also love programming, so it'd be nice to give the two focuses.
By the way, guys... I achieved something. Look:
Code: Select all
'Comment to make it instant
#define USEDELAY 1
Sub Plot(n As Short, c As Long)
Dim As Byte x, y
x = n Mod 100
y = n \ 100
Line (6 * x, 6 * y)- Step (5, 5), c, BF
End Sub
Type Triplet
lead As Byte
trail As Byte
End Type
Dim triplet(0 To 999) As Triplet
Dim symbolchain As String, seed As Short
Dim code(0 To 9999) As Byte, codesleft As Short = 10000
Dim i As Long, s As String, v As Long, w As Long
Dim t As Double
ScreenRes 800, 600, 32
Width 100, 600 \ 16
'Initialise all triplets. For each, there are 10 codes in which it's
'leading and 10 codes in which it's trailing
For i = 0 To 999
triplet(i).lead = 10
triplet(i).trail = 10
Next i
'Prompt the user for a starting code (seed)
Input "Enter a seeding code: ", seed
seed = Abs(seed Mod 10000)
'Initialise chain with the starting code
symbolchain = Right("000" + Trim(Str(seed)), 4)
'Decrement the values for the first code
triplet(seed \ 10).lead -= 1
triplet(seed Mod 1000).trail -= 1
code(seed) = -1
codesleft -= 1
Plot seed, RGB(200, 200, 200)
Do
s = InKey
If Len(s) Then Exit Do
'Try to append a code at the end
v = ValInt(Right(symbolchain, 3))
If triplet(v).lead Then
For i = 0 To 9 'Try each of the possible codes
w = v * 10 + i 'Each is lead by the v triplet
If code(w) = 0 Then 'Found an unused one
Plot w, RGB(0, 200, 0)
symbolchain &= Trim(Str(i)) 'Add to the chain
code(w) = -1 'Mark as used
triplet(v).lead -= 1 'One less with v leading
v = w Mod 1000 'But what's the trailing triplet for it?
triplet(v).trail -= 1 'That one must be decremented too
codesleft -= 1 'One more code has been used
Exit For
End If
Next i
'No more to append on the right. Try on the left
Else
v = ValInt(Left(symbolchain, 3)) 'Get chain's leading triplet
If triplet(v).trail Then
For i = 0 To 9 'Try each of the possible codes
w = i * 1000 + v 'Each has the v triplet trailing
If code(w) = 0 Then 'Found an unused one
Plot w, RGB(0, 200, 0)
symbolchain = Trim(Str(i)) & symbolchain 'Add to the chain
code(w) = -1 'Mark as used
triplet(v).trail -= 1 'One less with v trailing
v = w \ 10 'But what's the leading triplet for it?
triplet(v).lead -= 1 'That one must be decremented too
codesleft -= 1 'One more code has been used
Exit For
End If
Next i
Else
'Since there are codes left, there must exist a triplet
'that has been used, but not exhausted. Let's look up
For i = 0 To 999
If triplet(i).trail < 10 And triplet(i).trail > 0 Then
'Found one for trailing. Let's find where the chain
'contains this triplet, cut it there and join it at
'the old ends
v = i
i = InStr(symbolchain, Right("00" + Trim(Str(v)), 3))
s = Mid(symbolchain, i) 'Right part of the string
'For the left part, we need to include the triplet again
symbolchain = Left(symbolchain, i + 2)
'Drop the old first three digits, as they are the same
'as on the other end
symbolchain = Mid(symbolchain, 4)
'Connect the new chain
symbolchain = s & symbolchain
'Mark so that we know we've found one
i = -1
Exit For
End If
Next i
If i <> -1 Then
Print
Print "Stuck!"
Exit Do
End If
End If
End If
#ifdef USEDELAY
t = Timer
Do : Loop Until Timer > t + .001
#endif
Loop Until codesleft = 0
Print "Symbol chain length: "; Len(symbolchain)
'If any of the codes were not present, it'd be shown
For i = 0 To 9999
If InStr(symbolchain, Right("000" + Trim(Str(i)), 4)) = 0 Then Print i
Next i
Open "chain.txt" For Output As 1
Print #1, symbolchain;
Close 1
GetKey
This program I made, apparently,
always finds a solution and it can do it virtually instantly! It doesn't do any random guess. By default, it's not instant, because it has a graphical display showing how codes are being grabbed and pushed into the chain. If you comment the definition at the beginning of the code, it'll shoot to maximum speed.
You begin by entering a seed, a starting 4-digit code. The procedure will begin adding codes to the right of the string whenever possible. Once it can't find one that goes on the right, it will continue to the left (usually, by the time one side is exhausted, the other side is as well because of the wonderful symmetry of this problem... which I still don't completely understand, ha, ha). Once there are no more codes that can fit either side, if there are remainin codes, the program will look up a triplet that's been used somewhere in the string at least once, but of which there are still some instances left to insert. It will split the chain at that point and join the other two ends, so that execution can continue to add to the new ends. To do this, because this symmetry also means that whenever you get stuck, both the leading and trailing triplets are identical, it will remove one of the two triplets and instead, will insert a copy of the new leading triplet at the end, so the chain is again ending and starting with the same triplet.
All the codes I have tested end up being resolved. The final chain is written to a file you can check. Looking at the graphic is hypnotising, ha, ha. If you guys find any bug or encounter a seed that ends in a failure, let me know. Of course, the fact that this program always seems to work and it follows a procedure instead of using brute force (notice that it never backs up returning a previously pushed code to the stack) doesn't mean the program constinutes a proof. I have not tested all 10000 seeds and even if I did, I would like a comprehensive demonstration. Besides, I want to prove this for all
n and all
b.