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*.