Logical Thinking Question

[ranjith2523]

Hi Friends,

This question is not related to Excel or VBA but my senior told that the peoples who have knowledge on VBA can answer this question. I have little VBA knowledge but I didn't try to find solution for his question.

Can someone please help me to understand the below question (also give me a little simple explanation about this question in easy understandable English) and find out the solution ? Thanks for all your help in advance.

Question:

Find out the input string that was passed to the following hash function
Integer Hash (String inputString)
Integer outputNumber = 7;
String letters = "acdegilmnoprstuw";
Integer index = 0;
Integer lengthOfInputString = inputString.Length;
while (index < lengthOfInputString)
{
outputNumber = (outputNumber* 37+ letters.IndexOf (inputString
[index]));
index = index + 1;
}
return outputNumber;
}
That produced the hashed output (integer value) as
945901726134069
Provided, the input string length was 9 and contains only characters
from the below string
"acdegilmnoprstuw"
Note: You need to reverse engineer the above hash logic and find out the
answer.



HELP:
String - a data type that holds collection of characters, an array of
characters with zero- based index. Hash - Modify an input value to a
different one using which one cannot easily find out the original value.
Dehash - Find the original input value that was modified by hashing.
Function - a code snippet that accepts zero or more number of input
parameters and return either no value or a value. Integer - a data type
that holds both positive and negative full numbers.
<string_variable>.IndexOf - an in-built function in any programming
language that finds out the starting index of any substring (one or more
characters together) inside the value stored in string_variable.
<string_variable>[<integer_variable>] - an expression that returns the
character at the-index specified by the value of integer_variable

 

[sijpie]

Hi Ranjith,

this is a hash function written in C#

Basically what it does

Integer Hash (String inputString)
{
    Integer outputNumber = 7;
    String letters = "acdegilmnoprstuw";
    Integer index = 0;
    Integer lengthOfInputString = inputString.Length;
    while (index < lengthOfInputString)
        {
        outputNumber = (outputNumber* 37+ letters.IndexOf (inputString[index]));
        index = index + 1;
        }
    return outputNumber;
}

The function is passed the string to be hashed
The output number gets started with a value (7)
Letters contains a 'random' string

Then we go into a While loop where for each of the characters in the inputstring the output number is modified by multiplying it with 37 and adding the position of the character in the Letters string.

the position of the first letter =0
for instance position of 'd' in 'acdegilmnoprstuw' =2

So say the input string is 'dam'

Then outputnumber starts being 7

first the 'd' is checked

outputNumber = (outputNumber* 37+ letters.IndexOf (inputString[index]));

outputnumber = (7 * 37 + 2) = 261
now the 'a' is checked
outputnumber = (261 * 37 + 0) = 9657
lastly the 'm' is checked
outputnumber = (9657* 37 + 7) = 357316

So the hash of 'dam' = 357316


You need to reverse the process starting with the hash number 945901726134069
This is a number multiplied by 37 with something added.
So 945901726134069/37= 25564911517137.0
An exact division, so the last letter of the inputstring is 'a'

 

[sijpie]

So now take
25564911517137/37 = 690943554517 with remainder 8. So the (8+1) 9th letter in 'acdegilmnoprstuw' = n

You continue that way and you should get to a 9 letter word. I get 'pramodena'

 

[ranjith2523]

So now take
25564911517137/37 = 690943554517 with remainder 8. So the (8+1) 9th letter in 'acdegilmnoprstuw' = n

You continue that way and you should get to a 9 letter word. I get 'pramodena'

Hello Sijpie,

Thank you so much for your clear explanation.

I understand that we need to start from the output by dividing 37 for each result but I am not clear with the remainder. Will the remainder decrease from 9, 8, 7, 6 so on until we get 1 ?
Yes "pramodena" is the correct but still I am not clear about how we get this. Sorry to bother you.

Regards,
Ranjith

 

[sijpie]

Above I wrote how the formula works to hash the word 'dam'.

Then outputnumber starts being 7

first the 'd' is checked
Formula:
outputNumber = (outputNumber* 37+ letters.IndexOf (inputString[index]));

Note d is the 3rd letter in the random string, so it gets index 2 (as the first letter has index 0)

outputnumber = (7 * 37 + 2) = 261

The next letter is the a, which is the first letter of the random string so gets index 0

now the 'a' is checked
outputnumber = (261 * 37 + 0) = 9657

The m gets index 7 as it is the 8th letter in the string.

lastly the 'm' is checked
outputnumber = (9657* 37 + 7) = 357316

So the hash of 'dam' = 357316

So if we now want to reverse this to find the word from the hash:
357316/37 = 9657 +7
so the last letter of the word has index 7. Look it up in the string 'acdegilmnoprstuw' (starting with 0) so you get the 'm'.
then 9657/37 = 261 +0
so the last but one letter has index 0. this is the 'a'.
Then 261/37 = 7 +2
So the first letter of the word has index 2. This is the 'd'.

As the number now is 7, which is the starting number , it means we have finnished. This is also a good check that you have done the calculation correct. It should be 7 at the end.


so the word is 'dam'

 

[ranjith2523]

Above I wrote how the formula works to hash the word 'dam'.

Note d is the 3rd letter in the random string, so it gets index 2 (as the first letter has index 0)

The next letter is the a, which is the first letter of the random string so gets index 0

The m gets index 7 as it is the 8th letter in the string.


So if we now want to reverse this to find the word from the hash:
357316/37 = 9657 +7
so the last letter of the word has index 7. Look it up in the string 'acdegilmnoprstuw' (starting with 0) so you get the 'm'.
then 9657/37 = 261 +0
so the last but one letter has index 0. this is the 'a'.
Then 261/37 = 7 +2
So the first letter of the word has index 2. This is the 'd'.

As the number now is 7, which is the starting number , it means we have finnished. This is also a good check that you have done the calculation correct. It should be 7 at the end.


so the word is 'dam'

Thank you so much Sijpie for all your effort and time. I will mark this as Solved.