Euler Problem 79 asks:
‘for three random characters from a passcode. For example, if the
‘passcode was 531278, they may asked for the 2nd, 3rd, and 5th
‘characters; the expected reply would be: 317.
‘
‘The text file, keylog.txt, contains fifty successful login attempts.
‘
‘Given that the three characters are always asked for in order,
‘analyse the file so as to determine the shortest possible secret
‘passcode of unknown length.
The only reason you need a computer for this problem is to download keylog.txt. I opened keylog.txt to get a grasp of what kind of code to write, and in about a dozen lines of sliding numbers around, had solved it. There is positional consistency from character to character, and from one login attempt to the next. The next 38 lines were just looking for a surprise that didn’t come.
Having solved it, I did want to write code that implemented the algorithm my eye had so readily seen. That was harder. I wanted to use a collection again, because its Add and Remove methods readily accommodate re-arranging data. What collections don’t seem to have is a property that indicates where an item is in the collection (or if it’s there I couldn’t find it. My surmise is that collections are linked lists.) To address this, my first thought was to make a collection of a user-defined type that would have an index field. Though the XL help implies that you can make a collection of almost anything, user-defined types seem to be one of those things that’s on the wrong side of “almost.”
I ended up using an INDEX() array in parallel to the collection and doing my own bookkeeping. This is the code. It runs in what the timer reports out as zero seconds. There are probably better ways to do this bookkeeping, but Remove is done by index, and this is the way that occurred to me. The approach is that if an item is earlier in the PassCode collection that it is in the login attmept, to remove it from the PassCode and then add it back after the item in the attempt.
Dim PassCode As New Collection
Dim Index(0 To 9) As Byte
Dim i As Long, j As Long, k As Long, n As Long
Dim Location As Long, errNum As Long
Dim Item As String * 1, LastItem As String * 1
Dim Key As String * 1, TEMP As String * 1
Dim LogIn(50) As String * 3
Dim Answer As String, T As Single
Const text As String = “C:DownloadsEulerkeylog.txt”
T = Timer
i = 1
Open text For Input As #1
Do While Not EOF(1)
Line Input #1, LogIn(i)
i = i + 1
Loop
Close #1
For i = 1 To 50
For j = 1 To 3
Item = Mid(LogIn(i), j, 1)
Key = Item
n = PassCode.Count
errNum = 0
Err.Clear
On Error Resume Next
TEMP = PassCode.Item(Key)
errNum = CLng(Err.Number)
On Error GoTo 0
If errNum = 5 Then ‘5 means Not in Collection
Index(Item) = n + 1
PassCode.Add Item:=Item, Key:=Key
Else
If j = 1 Then
Location = 1
Else
Location = Index(LastItem)
End If
If Index(Item) LT Location Then ‘shuffle to after LastItem
PassCode.Remove (Index(Item)) ‘Removing Item
For k = 0 To 9 ‘re-indexing
If Index(k) GT Index(Item) Then
Index(k) = Index(k) – 1
End If
Next k
PassCode.Add Item:=Item, Key:=Key, After:=LastItem ‘Adding Item back
Index(Item) = Index(LastItem) + 1
For k = 0 To 9 ‘re-indexing
If k != Item And Index(k) GTE Index(Item) Then
Index(k) = Index(k) + 1
End If
Next k
End If
End If
LastItem = Item
Next j
Next i
For j = 1 To n
Answer = Answer & PassCode.Item(j)
Next j
Debug.Print Answer; ” Time:”; Timer – T
End Sub
The usual substitutions are made for angle brackets. Is there a better way to index a collection? This way will get messy for collections of any appreciable size.
…mrt
“What collections don’t seem to have is a property that indicates where an item is in the collection (or if it’s there I couldn’t find it. “
use a Scripting.Dictionary object.
I just remembered … the other thing I did was to store a variant array in the Item property
and put the index and key in there so the code looks like (OTTOMH)
coll.add Key:=sKey, Item:=array(coll.count+1,sKey,xValue,…)
Note that you can’t insert an item at a specific position with Dictionary.
This proc can be done faster and simpler with just a string.
Dim r As Long, c As Long, i As Long, j As Long, p(3) As Long
Dim s As String, a() As String
Open “c:keylog.txt” For Input As #1
a = Split(Input(LOF(1) – 2, 1), vbCrLf)
Close #1
s = a(0)
For r = 1 To UBound(a)
For c = 1 To 3
p(c) = InStr(s, Mid$(a(r), c, 1))
If p(c) = 0 Then s = s + Mid$(a(r), c, 1): p(c) = Len(s) ‘+ = amp
Next
For i = 1 To 2
For j = i + 1 To 3
If p(i) GT p(j) Then
Mid(s, p(i)) = Mid$(a(r), j, 1)
Mid(s, p(j)) = Mid$(a(r), i, 1)
p(0) = p(i): p(i) = p(j): p(j) = p(0)
End If
Next
Next
Next r
Debug.Print s
End Sub