5
$\begingroup$

I have an unusual programming problem and the math side of it has me stumped. It's probably a simple answer but math isn't my strongest area.

I've generated a unique string of 7 characters which are each randomly selected from these possibilities: ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789 for example A6HJ92B and I need to convert it to a unique number value. When converted, no two versions of this random string can be the name number.

I could just generate a number rather than including letters in the original id, but of course that means I have to increase the length of my string, and it's possible that the user of my application may want to type this string, as it identifies his "session" in an application, so I want to keep it short.

So my idea was to build a table like this:

A : 1,
B : 2,
C : 3,
D : 4,
E : 5,
F : 6,
G : 7,
H : 8,

... you get the idea ...

5 : 31,
6 : 32,
7 : 33,
8 : 34,
9 : 35

And then I'd add all of the numbers up...

A6HJ92B:

A : 1
6 : 32
H : 8
J : 10
9 : 35
2 : 28
B : 2

1+32+8+10+35+28+2 = 116

...but I realized this is a flawed idea because many possible strings will "collide" or equal the same number. I need each unique string to equal a unique number.

So even if I multiplied each character's value (1*32*8*10*35*28*2 = 5,017,600), I'm thinking there might be possible collisions there too.

Is there a way to calculate this in a way that eliminates collisions? If the collisions cant be eliminated, what methods can I use to minimize them?

$\endgroup$
2
7
$\begingroup$

You have $35$ characters, so you can effectively convert the string to an integer in base $35$. It would be better to start counting from $0$ instead of $1$ to get values from $0$ to $34$:

A :  0
B :  1
C :  2
 ...
9 : 34

Now for a given string $a_6a_5a_4\ldots a_1a_0$, your function can be $$a_635^6 + a_535^5 + \ldots + a_135 + a_0.$$ Your example of A6HJ92B would correspond to: $$0\cdot35^6 + 31\cdot35^5 + 7\cdot35^4 + 9\cdot35^3 + 34\cdot35^2 + 27\cdot35+1 = 1\ 639\ 110\ 971.$$ Is there a reason you don't include the digit 0? It would seem more natural to include it (thus counting in base 36) and to order the symbols 0123456789ABC...Z.

$\endgroup$
7
  • 1
    $\begingroup$ Yes there was a reason for it. I'm considering that "older folks" might not know the copy/paste function and choose to type the code, and I wanted to avoid confusion between O and zero. I might even do better do exclude both O and zero. $\endgroup$
    – J.Todd
    Mar 5 '16 at 22:49
  • 1
    $\begingroup$ @Viziionary Ah, I see. In that case, you could consider eliminating other characters as well to avoid confusion (e.g., O/Q, 1/I/L, U/V). $\endgroup$
    – Théophile
    Mar 6 '16 at 0:48
  • 1
    $\begingroup$ Yeah that's a good idea. Thanks for your answer. $\endgroup$
    – J.Todd
    Mar 6 '16 at 1:30
  • 1
    $\begingroup$ @user217648 Glad to help. To convert back, we first need to know the highest power of $35$ that will fit inside $n = 1 639 110 971$. Using logarithms, $$\log_{35}n = \frac{\log{n}}{\log{35}} = 5.967\ldots$$ so $n$ is slightly smaller than $35^6$. Now find the largest multiple of $35^5$ that fits inside $n$: $$\frac{n}{35^5} = 31.2\ldots$$ So we have $n = 31\cdot35^5 + \cdots$. Next subtract to get $n_1 = n - 31\cdot35 = 10 932 846$ and calculate $$\frac{n_1}{35^4} = 7.28\cdots,$$ so the next coefficient is $7$, etc. $\endgroup$
    – Théophile
    Jun 1 '18 at 11:41
  • 1
    $\begingroup$ @user217648 In the original problem, we knew that the code is $7$ characters long, so in fact the first coefficient (corresponding to $35^6$) is $0$, meaning character $A$. $\endgroup$
    – Théophile
    Jun 1 '18 at 11:44
2
$\begingroup$

Hope this java program helps you:

     int i=0;
     int total=1;
     String[] input = new String[35];
     String inputString = "A6HJ92B";
     char[] inputChar = inputString.toCharArray();
     for(char a = 'A' ; a<='Z' ; a++ ){
         i++;
         input[i-1] = a+":"+i;
     }
     for(char b = '1';b<='9';b++){
         i++;
         input[i-1] = String.valueOf(b)+":"+i;
     }

   for(int k=0;k<inputChar.length;k++){
       for(int j = 0;j<input.length;j++){
           if(input[j].charAt(0)==inputChar[k]){

               total*=Integer.parseInt(input[j].substring(input[j].indexOf(':')+1,input[j].length()));
           }
       }
   }  System.out.println(total);
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.