FireCode math

[SLARRA]

Dear Excel Eggheads (and I say that with the most sincere admiration),

Here's a gnarly little problem set whose solutions elude me... We assign a unique string identifier, called a FireCode, to every federal wildland fire. The FireCode business and syntax rules are as follows:

1. Every FireCode is comprised of (only) 4 characters.
2. The eligible characters are the numeric digits 0 thru 9, and the letters (case insensitive) A thru Z, excluding I and O (to avoid confusion with the digits 1 and 0).
3. Every FireCode must include at least one letter character and one numeric digit. That is, no FireCode can be comprised entirely of letters or entirely of numbers.
4. FireCodes are issued in sequence. If you put all the eligible characters in a ordered list of issuance, the letter sequence (A thru Z, excluding I and O) comes first, followed by the number sequence (0 thru 9). Accordingly, the first FireCode ever issued was AAA0 (couldn't be AAAA because it has to have at least one digit), followed by AAA1. After AA99, the next FireCode issued was AAB0, and so on.

So... this basically boils down to a number system in Base 34 (24 letters + 10 digits). If it wasn't for those pesky business rules that render certain FireCode strings as ineligible (i.e. no 4-letter or 4-number sequences), I could handle the math. But, those rules really confound things!

There are 3 things that I'd like to do in Excel:
1. (most important): Calculate the number of FireCodes between two given FireCodes. Example: How many FireCodes were issued between EG1F and H54X?
2. Tell me what FireCode lies x positions from a given FireCode. Example: What will be the 20,000th FireCode issued after H54X?
3. (least important, surely involves code?): Generate the list, in proper sequence, of valid FireCodes that occur between two given FireCodes. Example: List all the FireCodes between EG1F and H54X.

This is not an urgent problem and I would not ask anyone to spend serious time on the solutions. But, if you have some ideas on how this could be approached, I'd love to hear them.

Thanks!

SDL

 

[shg]

Just a change in the order of appearance of symbols:

       ----A---- ----------------B-----------------
   1   AAA0      A1: Input                         
   2   999Z      A2: Input                         
   3    994,559  A3: =FireCodeDistance(A1, A2)     
   4                                               
   5   EG1F      A5: Input                         
   6   H54X      A6: Input                         
   7     93,354  A7: =FireCodeDistance(A5, A6)     
   8                                               
   9   H54X      A9: Input                         
  10     20,000  A10: Input                        
  11   J1DR      A11: =FireCodeAdd(A9, A10)        
  12                                               
  13   A4BZ      A13: Input                        
  14   A4B0      A14 and down: =FireCodeAdd(A13, 1)
  15   A4B1                                        
  16   A4B2                                        
  17   A4B3                                        
  18   A4B4                                        
  19   A4B5                                        
  20   A4B6                                        
  21   A4B7                                        
  22   A4B8                                        
  23   A4B9                                        
  24   A4CA                                        
  25   A4CB

Option Explicit</SPAN>
 
'======================= F I R E C O D E   M A T H =============================</SPAN>
' A FireCode is a 4-character base 34 string, neither all alpha nor all numeric,</SPAN>
' using the symbols A-Z (excluding I and O), and 0-9</SPAN>
 
' Note that, unlike hex, numeric symbols are larger than the alpha symbols.</SPAN>
 
' Considering the symbols and rules, valid FireCodes are AAA0 through 999Z.</SPAN>
' So although the codespace is 34^4 = 1,336,336, the exclusion of the 10,000</SPAN>
' numeric-only strings and the 26^4 = 331,776 alpha-only strings leaves</SPAN>
' 994,560 valid FireCodes.</SPAN>
 
Const sSym          As String = "ABCDEFGHJKLMNPQRSTUVWXYZ0123456789"</SPAN>
 
Function FireCodeAdd(sNum As String, ByVal iOfs As Long) As String</SPAN>
    ' shg 2012</SPAN>
 
    ' Returns the FireCode that is offset iOfs from sNum1</SPAN>
 
    Dim iNum        As Long</SPAN>
    Dim iSgn        As Long</SPAN>
 
    iNum = B34ToLng(sNum)</SPAN>
    iSgn = Sgn(iOfs)</SPAN>
 
    Do While iOfs</SPAN>
        iNum = iNum + iSgn</SPAN>
        FireCodeAdd = LngToB34(iNum)</SPAN>
        If IsFireCode(FireCodeAdd) Then iOfs = iOfs - iSgn</SPAN>
    Loop</SPAN>
End Function</SPAN>
 
Function FireCodeDistance(ByVal sNum1 As String, ByVal sNum2 As String) As Long</SPAN>
    ' shg 2012</SPAN>
 
    ' Returns the distance from sNum1 to sNum2</SPAN>
 
    Dim iSgn        As Long</SPAN>
    Dim iDif        As Long</SPAN>
 
    If sNum1 = sNum2 Then Exit Function</SPAN>
    If Not IsFireCode(sNum:=sNum1, bSure:=True) Then Exit Function</SPAN>
    If Not IsFireCode(sNum:=sNum2, bSure:=True) Then Exit Function</SPAN>
 
    iSgn = Sgn(B34ToLng(sNum2) - B34ToLng(sNum1))</SPAN>
 
    Do Until sNum1 = sNum2</SPAN>
        sNum1 = FireCodeAdd(sNum1, iSgn)</SPAN>
        iDif = iDif + iSgn</SPAN>
    Loop</SPAN>
 
    FireCodeDistance = iDif</SPAN>
End Function</SPAN>
 
Function IsFireCode(sNum As String, Optional bSure As Boolean = False) As Boolean</SPAN>
    ' shg 2012</SPAN>
   
    ' Returns True if sNum is a valid FireCode</SPAN>
 
    Const sLikeA    As String = "[A-Z][A-Z][A-Z][A-Z]"</SPAN>
    Const sLike0    As String = "####"</SPAN>
    Dim i           As Long</SPAN>
 
    If bSure Then</SPAN>
        If Len(sNum) <> 4 Then Exit Function</SPAN>
        For i = 1 To 4</SPAN>
            If InStr(sSym, Mid(sSym, i, 1)) = 0 Then Exit Function</SPAN>
        Next i</SPAN>
    End If</SPAN>
 
    If sNum Like sLikeA Then Exit Function</SPAN>
    If sNum Like sLike0 Then Exit Function</SPAN>
 
    IsFireCode = True</SPAN>
End Function</SPAN>
 
Function B34ToLng(sNum As String) As Long</SPAN>
    ' shg 2012</SPAN>
 
    ' Converts the base 34 string sNum to a Long</SPAN>
    Dim iFac        As Long</SPAN>
    Dim iChr        As Long</SPAN>
 
    iFac = 1</SPAN>
 
    For iChr = Len(sNum) To 1& Step -1&</SPAN>
        B34ToLng = B34ToLng + (InStr(sSym, Mid(sNum, iChr, 1&)) - 1&) * iFac</SPAN>
        iFac = iFac * 34&</SPAN>
    Next iChr</SPAN>
End Function</SPAN>
 
Function LngToB34(ByVal i As Long) As String</SPAN>
    ' shg 2012</SPAN>
 
    ' Returns the string conversion of 0 <= i <= 1336325 to the FireCode Base</SPAN>
    ' The result may well not be a valid firecode.</SPAN>
    Dim s0          As String</SPAN>
 
    If i < 0& Or i > 1336325 Then</SPAN>
        LngToB34 = "Valid numbers are 0 to 1336325"</SPAN>
 
    Else</SPAN>
        s0 = Left$(sSym, 1&)</SPAN>
 
        Do</SPAN>
            LngToB34 = Mid$(sSym, (i - (i \ 34&) * 34& + 1&), 1&) & LngToB34</SPAN>
            i = i \ 34&</SPAN>
        Loop While i</SPAN>
 
        If Len(LngToB34) < 4 Then</SPAN>
            LngToB34 = String$(4& - Len(LngToB34), s0) & LngToB34</SPAN>
        End If</SPAN>
    End If</SPAN>
End Function</SPAN>

The routines could be made much faster using a binary search rather than the brute-force counting method.

 

[SLARRA]

Wow, SHG - I'm impressed. This works wonderfully. I wish I understood your methodology - and I will, given enough time to examine your code and learn more about VBA. In the meantime, tho, I'm set, thanks to you!

 

[shg]

You're welcome, good luck.