Euler Problem 79

Euler Problem 79 asks:

‘A common security method used for online banking is to ask the user
‘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.

 Sub Problem_079B()
   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
   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
         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
            If j = 1 Then
               Location = 1
               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.

Posted in Uncategorized

3 thoughts on “Euler Problem 79

  1. “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.

  2. 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,…)

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

    Sub p79()
      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
        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 r
      Debug.Print s
    End Sub

Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.