Results 1 to 23 of 23

Thread: Generating ordered 7 digit numbers

  1. #1

    Thread Starter
    Junior Member
    Join Date
    Jan 2014
    Posts
    30

    Generating ordered 7 digit numbers

    Hello all,

    I'm looking to generate a 7 digit number starting from 1,000,000 through 10,000,000. Each generation must increment by 1 but if there are 4 or more consecutive numbers e.g 1,222,234 then it will generate a new number.

    I've done this but not very well and not efficient at all so I wiped my code and thought perhaps vbforums could help me. Thanks in advance!

  2. #2
    Smooth Moperator techgnome's Avatar
    Join Date
    May 2002
    Posts
    34,532

    Re: Generating ordered 7 digit numbers

    if there are 4 or more consecutive numbers e.g 1,222,234 then it will generate a new number.
    Well that's kind of an odd request.

    What DB system are you using?

    -tg


    edit - wait... is this even DB related? I see now that it's in the .NET section.
    * I don't respond to private (PM) requests for help. It's not conducive to the general learning of others.*
    * I also don't respond to friend requests. Save a few bits and don't bother. I'll just end up rejecting anyways.*
    * How to get EFFECTIVE help: The Hitchhiker's Guide to Getting Help at VBF - Removing eels from your hovercraft *
    * How to Use Parameters * Create Disconnected ADO Recordset Clones * Set your VB6 ActiveX Compatibility * Get rid of those pesky VB Line Numbers * I swear I saved my data, where'd it run off to??? *

  3. #3

    Thread Starter
    Junior Member
    Join Date
    Jan 2014
    Posts
    30

    Re: Generating ordered 7 digit numbers

    Quote Originally Posted by techgnome View Post
    Well that's kind of an odd request.

    What DB system are you using?

    -tg


    edit - wait... is this even DB related? I see now that it's in the .NET section.
    [/quote]

    Yes it's a bit of a strange thing to ask but it is crucial to my project. Nothing to do with DB's my friend!

  4. #4
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Generating ordered 7 digit numbers

    You shouldn't have wiped your code. Improving existing code would be less buggy than winging code on the fly.

    The four consecutive digits constraint is a pretty interesting one. It seems like the base problem is simple:

    Code:
    For x = 1000000 To 10000000
     If CheckForFour(x) Then
      'The number is ok, use it.
     End If
    Next
    The bigger problem is the CheckForFour. One solution is to turn it into a string and compare the individual digits, but that means lots of conversion to and from strings along with a bunch of string manipulation, which is always a slow idea. Another alternative might be this:
    Code:
    Private Function CheckForFour(inNo as Integer) as Boolean
     Dim last As Integer = 1
     Dim cnt As Integer
    
     For x = 7 To 1 Step -1
      dim temp As Integer = (inNo Mod (10^x)) \ (10^(x-1))
      If temp-Last = 1 Then
       cnt+=1
      Else
       cnt = 0
      End If
      last = temp
      If cnt = 3 Then
       Return False
      End If
     Next
    
     Return True
    
    End Function
    This isn't tested, and I think it will actually fail for 10,000,000, but it is pretty close and a special case could be written to handle 10,000,000. The key is in calculating temp. The first part takes the number Mod 10^X. So, the first time through, when X is 7, it would come up with inNo Mod 10,000,000, which is the whole number. It would then do an integer divide with 1,000,000, which would result in just the seventh digit. The next time through, it would do inNo Mod 1,000,000, then an integer divide with 100,000, which would result in just the sixth digit, and so on. It then compares the temp value to the last value. If the difference between them is 1, then temp is in sequence with last, in which case the counter is incremented. If the difference between them is anything other than 1, then temp is not in sequence with last, so the counter is cleared. If the counter ever reaches three, then four consecutive numbers have been found, in which case the method returns False. If the loop is completed without the method ever returning False, then no four consecutive numbers were found, so the method returns True.
    My usual boring signature: Nothing

  5. #5
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: Generating ordered 7 digit numbers

    I not sure what Shaggy is referring to in terms of string manipulations and conversion from strings, but here is a simple function that converts the number to a string and tests it.
    Code:
    Private Function HasFourConsecutiveDigits(ByVal num As Int32) As Boolean
       Dim ret As Boolean
       Dim digits As String = num.ToString("G", System.Globalization.CultureInfo.InvariantCulture)
       Dim testChar As Char = digits(0)
       Dim testCount As Int32 = 1
       For i As Int32 = 1 To digits.Length - 1
          If digits(i) = testChar Then
             If testCount = 3 Then ' this is the 4th occurance of testChar
                ret = True
                Exit For
             End If
             testCount += 1
          Else
             testCount = 1
             testChar = digits(i)
          End If
       Next
       Return ret
    End Function
    Last edited by TnTinMN; Jul 30th, 2014 at 02:48 PM. Reason: typo

  6. #6
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Generating ordered 7 digit numbers

    Ah, I see that there are multiple interpretations of "consecutive number". I think that TnTinMn got it right and I got it wrong. I was thinking of consecutive numbers as in 1234 or 3456, rather than consecutive repeating numbers like 2222 or 3333.

    What I was saying about strings is that I have always found string manipulation solutions inferior in performance to programs using numbers. that may not be correct in this case, though.
    My usual boring signature: Nothing

  7. #7

    Thread Starter
    Junior Member
    Join Date
    Jan 2014
    Posts
    30

    Re: Generating ordered 7 digit numbers

    You may have misinterpreted what I was trying to say. Repeating would have been a better word. Thanks for your solution nonetheless and even more so for explaining it to me.

  8. #8
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: Generating ordered 7 digit numbers

    Quote Originally Posted by Vespareum View Post
    Hello all,

    I'm looking to generate a 7 digit number starting from 1,000,000 through 10,000,000. Each generation must increment by 1 but if there are 4 or more consecutive numbers e.g 1,222,234 then it will generate a new number.
    After re-reading this and acknowledging that the number is incremented 1 each time, it should be more efficient to pass a number to a verification routine that will return the number if it passes or the next valid number.

    So with a lower limit of 1000000 and a upper limit of 10,000,000, the first valid number would be 1,000,100 and the last would be 9,998,999.

    I think I have this logic correct. It use two functions to compute a valid number. It returns one of three values:
    • The original number if valid
    • The next valid number.
    • -1 : upper limit exceed

    It recursively tests the number generated until it is either valid or has exceeded the upper limit

    Sample Usage:
    Code:
    Dim num As Int32 = 9990000
    num = ValidNumber(num)
    If num = -1 Then
       'handle it
    End If
    VB.Net Code:
    1. Private Function ValidNumber(ByVal num As Int32) As Int32
    2.    Const UpperLimit As Int32 = 10000000
    3.    If num > UpperLimit Then
    4.       num = -1
    5.    Else
    6.       Dim startPos, digitsLength As Int32
    7.       Dim found As Boolean = HasFourConsecutiveDigits(num, startPos, digitsLength)
    8.       Dim adder As Int32 = 0
    9.       If found Then
    10.          Dim pwr As Int32 = (digitsLength - 1) - startPos
    11.          adder = CInt(10I ^ pwr)
    12.          num = ((num \ adder) * adder) + adder
    13.          num = ValidNumber(num)
    14.       End If
    15.    End If
    16.    Return num
    17. End Function
    18.  
    19. Private Function HasFourConsecutiveDigits(ByVal num As Int32, ByRef startPos As Int32, ByRef digitsLength As Int32) As Boolean
    20.    Dim ret As Boolean
    21.    Dim digits As String = num.ToString("G", System.Globalization.CultureInfo.InvariantCulture)
    22.    digitsLength = digits.Length
    23.    Dim testChar As Char = digits(digits.Length - 1)
    24.    Dim testCount As Int32 = 1
    25.    startPos = digits.Length - 1
    26.    For i As Int32 = digits.Length - 2 To 0 Step -1
    27.       If digits(i) = testChar Then
    28.          If testCount = 3 Then ' this is the 4th occurance of testChar
    29.             ret = True
    30.             Exit For
    31.          End If
    32.          testCount += 1
    33.       Else
    34.          testCount = 1
    35.          testChar = digits(i)
    36.          startPos = i
    37.       End If
    38.    Next
    39.    If Not ret Then startPos = -1
    40.    Return ret
    41. End Function

  9. #9
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Generating ordered 7 digit numbers

    Ummm, I liked your earlier example better.

    By the way, my initial snippet could be modified to work with the different evaluation:

    Code:
    Private Function CheckForFour(inNo as Integer) as Boolean
     Dim last As Integer = 1
     Dim cnt As Integer
    
     For x = 7 To 1 Step -1
      dim temp As Integer = (inNo Mod (10^x)) \ (10^(x-1))
      If temp= Last Then
       cnt += 1
      Else
       cnt = 0
      End If
      last = temp
      If cnt = 3 Then
       Return False
      End If
     Next
    
     Return True
    
    End Function
    My usual boring signature: Nothing

  10. #10
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: Generating ordered 7 digit numbers

    Quote Originally Posted by Shaggy Hiker View Post
    Ummm, I liked your earlier example better.
    It incorporates a modified version of the earlier code. This version eliminates the need to incrementally test potentially thousands of invalid values if the search for a valid one. That assumes that I have correctly understood the OP's logic.

  11. #11
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Generating ordered 7 digit numbers

    Yeah, I'm doing a few thousand unnecessary tests, but they won't take a millisecond. A couple If statements could remove them, unless there are other cases I'm not thinking of. It seems like the method could return true if X reached 3 and cnt > 0, or if X reached 2 and count > 1, or if X reached 1 and count > 2, but I don't see many others that can be ruled out other than the cases on the upper end.
    My usual boring signature: Nothing

  12. #12
    Fanatic Member Flashbond's Avatar
    Join Date
    Jan 2013
    Location
    Istanbul
    Posts
    646

    Re: Generating ordered 7 digit numbers

    Code:
    For i = 1000000 To 10000000
       If Not System.Text.RegularExpressions.Regex.IsMatch(i.ToString, "(.)\1{3}") Then
           'Do your stuff
       End If
    Next
    BTW, it's shorter but nearly 2 times slower than Shaggy's solution. That's why regex is a costly thing.

    EDIT: My method finds 8966700 results -which I am quite sure- while Shaggy's method returns with 8957709 results. I can't evaluate every number so you must figure out which method is the right one. I couldn't make TnTinMN's method work so I have no idea about it. Here, how I tested:

    Create a form and place two buttons. Name one of the buttons as "Flashbond" and the other one as "Shaggy" then paste the code below.
    Code:
    Public Class Form1
        Dim sw As New Stopwatch
        Dim ii As Integer
        Private Sub Flashbond_Click(sender As Object, e As EventArgs) Handles Flashbond.Click
            ii = 0
            sw.Start()
            For i = 1000000 To 10000000
                If Not System.Text.RegularExpressions.Regex.IsMatch(i.ToString, "(.)\1{3}") Then
                    ii += 1
                End If
            Next
            sw.Stop()
            MsgBox(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Sub Shaggy_Click(sender As Object, e As EventArgs) Handles Shaggy.Click
            ii = 0
            sw.Start()
            For i = 1000000 To 10000000
                If CheckForFour(i) Then
                    ii += 1
                End If
            Next
            sw.Stop()
            MsgBox(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Function CheckForFour(inNo As Integer) As Boolean
            Dim last As Integer = 1
            Dim cnt As Integer
            For x = 7 To 1 Step -1
                Dim temp As Integer = (inNo Mod (10 ^ x)) \ (10 ^ (x - 1))
                If temp = last Then
                    cnt += 1
                Else
                    cnt = 0
                End If
                last = temp
                If cnt = 3 Then
                    Return False
                End If
            Next
            Return True
        End Function
    End Class
    EDIT2: Yeah, I am sure Shaggy's method catches some 3 consecutive digits also. That's why it eleminates more than the condition.
    Last edited by Flashbond; Jul 31st, 2014 at 12:57 PM.
    God, are you punishing me because my hair is better than yours? -Jack Donaghy

  13. #13
    Fanatic Member Flashbond's Avatar
    Join Date
    Jan 2013
    Location
    Istanbul
    Posts
    646

    Re: Generating ordered 7 digit numbers

    I made Shaggy's code work with a little touch. Use it, it's 1.5x faster.
    Code:
        Private Function CheckForFour(inNo As Integer) As Boolean
            Dim last As Integer = 1
            Dim cnt As Integer
            For x = 8 To 1 Step -1
                Dim temp As Integer = (inNo Mod (10 ^ x)) \ (10 ^ (x - 1))
                If temp = last Then
                    cnt += 1
                Else
                    cnt = 0
                End If
                last = temp
                If cnt = 3 Then
                    Return False
                End If
            Next
            Return True
        End Function
    God, are you punishing me because my hair is better than yours? -Jack Donaghy

  14. #14
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Generating ordered 7 digit numbers

    Well, that's what I get for freehand.
    My usual boring signature: Nothing

  15. #15
    Fanatic Member Flashbond's Avatar
    Join Date
    Jan 2013
    Location
    Istanbul
    Posts
    646

    Re: Generating ordered 7 digit numbers

    Nice shot!
    God, are you punishing me because my hair is better than yours? -Jack Donaghy

  16. #16
    Frenzied Member
    Join Date
    May 2014
    Location
    Central Europe
    Posts
    1,372

    Re: Generating ordered 7 digit numbers

    so, now take a look at this little one:
    Code:
    Public Class Form1
        Dim sw As New Stopwatch
        Dim ii As Integer
    
        Private btValues(7) As Byte '8 digits
    
        Private Sub Shaman_Click(sender As Object, e As System.EventArgs) Handles Shaman.Click
            btValues = {0, 0, 0, 0, 0, 0, 0, 0}
            ii = 0
            sw.Start()
            Do While btValues(7) = 0    'while there is no 1 on position 7
                IncreaseDigit(0)
                'Debug.Print(IntegerNumber)
                If btValues(6) > 0 Then 'count only from 1,000,000 to 9,999,999
                    ii += 1
                End If
            Loop
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
    
        End Sub
    
        Private Function ConvertToInteger() As Int32
            Dim iResult As Int32
            For i = 0 To 7
                iResult += btValues(i) * 10 ^ i
            Next
            Return iResult
        End Function
    
    
        Private Sub IncreaseDigit(i As Int32)
            If btValues(i) = 9 Then
                btValues(i) = 0
                IncreaseDigit(i + 1)
            Else
                btValues(i) += 1
                'see if there are multiple 0 to the right
                Dim count As Int32 = 0
    
                Do While i - count - 1 >= 0 AndAlso btValues(i - count - 1) = 0
                    count += 1
                    If count = 4 Then
                        'got ya! one more!
                        IncreaseDigit(i - count)
                        Exit Sub
                    End If
                Loop
    
                'see if there are any identical digits to the left
                count = 1
                Do While i + count < btValues.Length AndAlso btValues(i + count) = btValues(i)
                    count = count + 1
                    If count = 4 Then
                        'got ya! one more!
                        IncreaseDigit(i)
                        Exit Sub
                    End If
                Loop
            End If
        End Sub
    
    
        Private Sub Flashbond_Click(sender As Object, e As EventArgs) Handles Flashbond.Click
            ii = 0
            sw.Start()
            For i = 1000000 To 10000000
                If Not System.Text.RegularExpressions.Regex.IsMatch(i.ToString, "(.)\1{3}") Then
                    ii += 1
                End If
            Next
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Sub Shaggy_Click(sender As Object, e As EventArgs) Handles Shaggy.Click
            ii = 0
            sw.Start()
            For i = 1000000 To 10000000
                If CheckForFour(i) Then
                    ii += 1
                End If
            Next
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Function CheckForFour(inNo As Integer) As Boolean
            Dim last As Integer = 1
            Dim cnt As Integer
            For x = 7 To 1 Step -1
                Dim temp As Integer = (inNo Mod (10 ^ x)) \ (10 ^ (x - 1))
                If temp = last Then
                    cnt += 1
                Else
                    cnt = 0
                End If
                last = temp
                If cnt = 3 Then
                    Return False
                End If
            Next
            Return True
        End Function
    
        Private Sub Button2_Click(sender As System.Object, e As System.EventArgs) Handles Button2.Click
    
        End Sub
    End Class
    compare the speed this is a different way to look at numbers and on stuff like this it comes in very handy. note as well, that the function relies on that you start of with a valid number so even though alot faster it also calculates all possible values from 1 to 1,000,000 but does not count them. and my counting result supports flashbonds 8966700. shaggy, i am sorry to say but it seems that your function evaluates 1110001 as invalid - edit i see this was already found.
    Last edited by digitalShaman; Jul 31st, 2014 at 01:26 PM.

  17. #17
    Fanatic Member Flashbond's Avatar
    Join Date
    Jan 2013
    Location
    Istanbul
    Posts
    646

    Re: Generating ordered 7 digit numbers

    Quote Originally Posted by digitalShaman View Post
    compare the speed this is a different way to look at numbers and on stuff like this it comes in very handy.
    Aaah! Very clever! How I didn't think that? You are building the number instead of attempting each to check. Very very clever!

    EDIT: And It's more than 60x faster any of our codes
    God, are you punishing me because my hair is better than yours? -Jack Donaghy

  18. #18
    Frenzied Member
    Join Date
    May 2014
    Location
    Central Europe
    Posts
    1,372

    Re: Generating ordered 7 digit numbers

    EDIT: And It's more than 60x faster any of our codes
    ohh, just a bit

    i also got TnTinMN's code to work and he is second:
    Code:
    Public Class Form1
        Dim sw As New Stopwatch
        Dim ii As Integer
    
        Private btValues(7) As Byte '8 digits
    
        Private Sub Shaman_Click(sender As Object, e As System.EventArgs) Handles Shaman.Click
            btValues = {0, 0, 0, 0, 0, 0, 0, 0}
            ii = 0
            sw.Start()
            Do While btValues(7) = 0    'while there is no 1 on position 7
                IncreaseDigit(0)
                'Debug.Print(ConvertToInteger)
                If btValues(6) > 0 Then 'count only from 1,000,000 to 9,999,999
                    ii += 1
                End If
            Loop
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
    
        End Sub
    
        Private Function ConvertToInteger() As Int32
            Dim iResult As Int32
            For i = 0 To 7
                iResult += btValues(i) * 10 ^ i
            Next
            Return iResult
        End Function
    
    
        Private Sub IncreaseDigit(i As Int32)
            If btValues(i) = 9 Then
                btValues(i) = 0
                IncreaseDigit(i + 1)
            Else
                btValues(i) += 1
                'see if there are multiple 0 to the right
                Dim count As Int32 = 0
    
                Do While i - count - 1 >= 0 AndAlso btValues(i - count - 1) = 0
                    count += 1
                    If count = 4 Then
                        'got ya! one more!
                        IncreaseDigit(i - count)
                        Exit Sub
                    End If
                Loop
    
                'see if there are any identical digits to the left
                count = 1
                Do While i + count < btValues.Length AndAlso btValues(i + count) = btValues(i)
                    count = count + 1
                    If count = 4 Then
                        'got ya! one more!
                        IncreaseDigit(i)
                        Exit Sub
                    End If
                Loop
            End If
        End Sub
    
    
        Private Sub Flashbond_Click(sender As Object, e As EventArgs) Handles Flashbond.Click
            ii = 0
            sw.Start()
            For i = 1000000 To 10000000
                If Not System.Text.RegularExpressions.Regex.IsMatch(i.ToString, "(.)\1{3}") Then
                    ii += 1
                End If
            Next
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Sub Shaggy_Click(sender As Object, e As EventArgs) Handles Shaggy.Click
            ii = 0
            sw.Start()
            For i = 1000000 To 10000000
                If CheckForFour(i) Then
                    ii += 1
                End If
            Next
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Function CheckForFour(inNo As Integer) As Boolean
            Dim last As Integer = 1
            Dim cnt As Integer
            For x = 8 To 1 Step -1
                Dim temp As Integer = (inNo Mod (10 ^ x)) \ (10 ^ (x - 1))
                If temp = last Then
                    cnt += 1
                Else
                    cnt = 0
                End If
                last = temp
                If cnt = 3 Then
                    Return False
                End If
            Next
            Return True
        End Function
    
        Private Sub TnTinMN_Click(sender As System.Object, e As System.EventArgs) Handles TnTinMN.Click
            ii = 0
            sw.Start()
            Dim num As Int32 = ValidNumber(1000000)
            Do
                ii += 1
                num = ValidNumber(num + 1)
            Loop While num <> -1
            sw.Stop()
            MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
            sw.Reset()
        End Sub
        Private Function ValidNumber(ByVal num As Int32) As Int32
            Const UpperLimit As Int32 = 10000000
            If num > UpperLimit Then
                num = -1
            Else
                Dim startPos, digitsLength As Int32
                Dim found As Boolean = HasFourConsecutiveDigits(num, startPos, digitsLength)
                Dim adder As Int32 = 0
                If found Then
                    Dim pwr As Int32 = (digitsLength - 1) - startPos
                    adder = CInt(10I ^ pwr)
                    num = ((num \ adder) * adder) + adder
                    num = ValidNumber(num)
                End If
            End If
            Return num
        End Function
    
        Private Function HasFourConsecutiveDigits(ByVal num As Int32, ByRef startPos As Int32, ByRef digitsLength As Int32) As Boolean
            Dim ret As Boolean
            Dim digits As String = num.ToString("G", System.Globalization.CultureInfo.InvariantCulture)
            digitsLength = digits.Length
            Dim testChar As Char = digits(digits.Length - 1)
            Dim testCount As Int32 = 1
            startPos = digits.Length - 1
            For i As Int32 = digits.Length - 2 To 0 Step -1
                If digits(i) = testChar Then
                    If testCount = 3 Then ' this is the 4th occurance of testChar
                        ret = True
                        Exit For
                    End If
                    testCount += 1
                Else
                    testCount = 1
                    testChar = digits(i)
                    startPos = i
                End If
            Next
            If Not ret Then startPos = -1
            Return ret
        End Function
    End Class
    Last edited by digitalShaman; Jul 31st, 2014 at 02:21 PM.

  19. #19
    Fanatic Member Flashbond's Avatar
    Join Date
    Jan 2013
    Location
    Istanbul
    Posts
    646

    Re: Generating ordered 7 digit numbers

    And there is no reply from the questioner. Interesting
    God, are you punishing me because my hair is better than yours? -Jack Donaghy

  20. #20
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,335

    Re: Generating ordered 7 digit numbers

    @Flashbond: You can get yours to run almost twice as fast with a simple alteration:

    vb.net Code:
    1. Private Sub Flashbond_Click(sender As Object, e As EventArgs) Handles Button1.Click
    2.     ii = 0
    3.  
    4.     Dim rgx As New System.Text.RegularExpressions.Regex("(.)\1{3}", RegexOptions.Compiled)
    5.  
    6.     sw.Start()
    7.     For i = 1000000 To 10000000
    8.         If Not rgx.IsMatch(i.ToString(Globalization.CultureInfo.InvariantCulture)) Then
    9.             ii += 1
    10.         End If
    11.     Next
    12.     sw.Stop()
    13.     MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
    14.     sw.Reset()
    15. End Sub

    That's down from 14.5 seconds to 7.5 seconds on my system compiled to x86 with .NET FW 4.0.

    The Globalization.CultureInfo.InvariantCulture only contributes a fraction to the reduction in execution time, but every little helps.

  21. #21
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,335

    Re: Generating ordered 7 digit numbers

    And for what it's worth, I would do it as (VB2010):
    Code:
     Dim ii As Integer = 0
     Dim sw As New Stopwatch
     Dim disallowed() As Integer = New Integer() {1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999, 0} ' 0 is 0000
    
    
     sw.Start()
     For number As Integer = 1000000 To 10000000 - 1 ' 7 digit numbers only
         If Array.IndexOf(disallowed, number Mod 10000) = -1 AndAlso
            Array.IndexOf(disallowed, (number \ 10) Mod 10000) = -1 AndAlso
            Array.IndexOf(disallowed, (number \ 100) Mod 10000) = -1 AndAlso
            Array.IndexOf(disallowed, (number \ 1000)) = -1 Then
    
             ii += 1
    
         End If
     Next
     sw.Stop()
     MessageBox.Show(ii & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
     sw.Reset()

  22. #22
    Fanatic Member Flashbond's Avatar
    Join Date
    Jan 2013
    Location
    Istanbul
    Posts
    646

    Re: Generating ordered 7 digit numbers

    Quote Originally Posted by Inferrd View Post
    That's down from 14.5 seconds to 7.5 seconds on my system compiled to x86 with .NET FW 4.0.

    The Globalization.CultureInfo.InvariantCulture only contributes a fraction to the reduction in execution time, but every little helps.
    Didnt know that. Thanks!
    God, are you punishing me because my hair is better than yours? -Jack Donaghy

  23. #23
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: Generating ordered 7 digit numbers

    My first thought was to also use a byte array to increment and test the digits, but with a couple of pressing things on the 30th and 31st, I didn't code anything.
    Now that the pressure is off (for a day at least, its Friday), I decided to code up my approach to see how it compared.
    The main idea was that any combination of 4 in a row out of 7 digits will include the middle digit, so just compare the middle digit in each direction to see if we have at least four in a row.

    It seems that the savings gained by adding additional logic to try to reduce the number of compares or to skip ranges of numbers that won't pass (e.g. if you have 2222000, you know you can skip 2222001 to 2222999, so just set the lower three digits to 999 and continue with the next increment) outweighed the gain by a slight margin so simple, straight forward testing of every number won out.
    Using a For loop seems to be slightly faster than Do While b(7) = 0 loop.

    I'm not sure how to express it as a percentage, but on my machine, the average of 10 runs of mine vs digitalShaman's gave the following values (run from the IDE, and from the executable in the Debug directory).
    Interestingly enough, since I'm running Windows 7, 64-bit, I compiled an x64 version, and it ran much slower (at least 50% slower) than the x86 version outside the IDE. Didn't do any Release and/or extra optimization selections.

    In the IDE, I got an average of .3222 seconds, Shaman's .4113 seconds.
    Running the debug/bin/...exe version (x86), I got 0.2037, Shaman's 0.2688.
    Code:
    Public Class Form1
      Dim b(7) As Byte
      Dim sw As New Stopwatch
    
      Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        b = {0, 0, 0, 0, 0, 0, 1, 0}
        Dim totl As Integer
        Dim dups As Integer
    
        sw.Start()
    
        For i As Integer = 1000000 To 9999999
          dups = 0
    
          If b(3) = b(2) Then     'if 4th digit = 3rd
            dups += 1
            If b(3) = b(1) Then   '  if 4th digit = 2nd
              dups += 1
              If b(3) = b(0) Then '    if 4th digit = 1st
                dups += 1         '      four in a row, at this point
              End If
            End If
          End If
    
          If dups < 3 Then          'If we don't have 4 in a row already
            If b(3) = b(4) Then     '  if 4th digit = 5th
              dups += 1
              If b(3) = b(5) Then   '    if 4th digit = 6th
                dups += 1
                If b(3) = b(6) Then '      if 4th digit = 7th
                  dups += 1
                End If
              End If
            End If
          End If
    
          If dups < 3 Then          'If we don't have 4 or more in a row
            totl += 1               '  count it
          End If
    
          IncrementDigit(0)         'Increment the "value"
        Next
    
        sw.Stop()
        MessageBox.Show(totl & " results found in " & sw.ElapsedMilliseconds / 1000 & " seconds.")
        sw.Reset()
      End Sub
    
      Private Sub IncrementDigit(i As Integer)
        Const b1 As Byte = 1 'Option Strict doesn't allow b(i) += 1, so use a byte constant
    
        If b(i) = 9 Then
          b(i) = 0
          IncrementDigit(i + 1)
        Else
          b(i) += b1
        End If
      End Sub
    
    End Class
    p.s. Went ahead and did the increment digit and carry logic in a loop inline, rather than a recursive sub call. That nearly doubled the speed of the x86 version in the IDE
    from .3222 seconds to .1717 seconds (average of 10 runs)

    The x86 executable outside the IDE wasn't as big an increase
    from .2037 to .1655 seconds, but still significant.

    The x64 compile was still much slower in both IDE and executable outside the IDE (over .3 seconds in either case).
    Code:
    'instead of calling IncrementDigit(0), do an inline loop to increment the digit(s)
    
          '  IncrementDigit(0)         'Increment the "value"
          Const b1 As Byte = 1
          Dim d As Integer = 0
          b(d) += b1           'Add 1 to the first digit
          Do While b(d) = 10   'Do while we have a carry
            b(d) = 0           '  Set this digit to 0
            d += 1             '  Point to the next digit
            b(d) += b1         '  Increment it
          Loop
    Last edited by passel; Aug 1st, 2014 at 05:28 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width