Please Help - Logical Thinking Question

[Ranjith2523]

Hi Friends,

This is my first post in this forum. Can someone please help me to understand this question (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

 

[Skydiver]

We are not here to do your homework for you. We can guide you along, though. Tell us what you have thought about so far and what you have tried.

Hint: When you have a base 10 number like 349; and how do you determine how many ones, tens, and hundreds there are? The problem above just happens to be base 37 rather than base 10.

 

[Ranjith2523]

We are not here to do your homework for you. We can guide you along, though. Tell us what you have thought about so far and what you have tried.

Hint: When you have a base 10 number like 349; and how do you determine how many ones, tens, and hundreds there are? The problem above just happens to be base 37 rather than base 10.

Mr. Skydriver, You may be a super genius but don't be RUDE with the people. If you don't want to reply then don't reply. Even I can respond even harsher but I will not do that because there should a key difference between you and me. I never asked you to do my HOMEWORK, one of my colleagues asked me this question which I don't understand hence seeking help from people who have knowledge in this particular area. This was my post in this forum and will also be my last post.

 

[Skydiver]

It was not meant to be rude. Just a statement of fact.

Goodbye. Sorry to see you leave.

 

[cjard]

Look at the problem more simply. Let's just use 5 letters and multiply by 10

String letters = "abcde";
...
    outputNumber = (outputNumber* 10 + letters.IndexOf (inputString
[index]));

Let's have a message of bbbdddcece

First letter is b, it is at index 1 in `letters`.. Ouput number is 0. 0*10 is 0, plus index 1, is 1

Output number is now 1. Then it becomes 1*10 + 1:

11
111

That's the bbb done

Then it becomes

1113
11133
111333

That's the bbbddd done

1113332
11133324
111333242
1113332424

We are done. And you hopefully can see it's a simple numeric translation of the letters; the multiply by 10 just moves the existing number along to the left by one place so we have space to add another translated character

We can get away with times 10 because there are only 5 characters. If there were 10 chars it would also be fine, but just imagine if there were 11 or more chars to encode; things would start to go wrong because if you look at an output number of "20" encoding letters of ABCDEFGHIJK (which is 11 chars) we can't tell if 20 is CA or BK

CA = 2*10 + 0
BK = 1*10 + 10

Both these sums add up to 20. If we have 10 or more letter, multiplying by ten isn't enough to "move the existing number out of the way" so that we can add the 10th letter without smushing it into the other digits

Hopefully now you can see that so long as you multiply by any number greater than the amount of different letters you have, you move the existing number out of the way sufficiently that no letter addition collides with the existing number hash

Getting the number back to letters is the reverse operation

We've been multiplying by 10 every time and adding some number less than 10

If we were to divide by 10 instead and look at the remainder, it would give us the last addition we made

Let's go back to our hash of bbbdddcece:

1113332424

Divide by ten and what is the remainder?

4

What letter is at index 4?

e

What is left after we divide by ten?

111333242

Divide that by ten. Remainder is 2. 2 relates to c (a is zero, b is one, c is two...)

Keep going. We built this number by multiplying by ten over and over and adding on some number less than 10 (a remainder) so divide divide divide, by ten, and look at the remainder each time

Keep going until you've divided the 1113332424 number all the way to 0, the reminder each time is the letter

1113332424 / 10 = 111333242 r 4 (e)
111333242 / 10 = 11133324 r 2 (c)
11133324 / 10 = 1113332 r 4 (e)
1113332 / 10 = 111333 r 2 (c)
111333 / 10 = 11133 r 3 (d)
11133 / 10 = 1113 r 3 (d)
1113 / 10 = 111 r 3 (d)
111 / 10 = 11 r 1 (b)
11 / 10 = 1 r 1 (b)
1 / 10 = 0 r 1 (b)

We are done. Read up the rows for the letter in brackets and see that we get our original message back: bbbdddcece

Doing it times ten makes it simple to see but it's just a number. If you swap in 37 it will still work the same.

In c# you can get the remainder of a divide by using the % operator

107 % 10 gives 7

38 % 37 gives 1

If your output number was 38, and your multiplier was 37, your letters input must have been BB; 38 is 1*37 + 1, and B is 1

 

[Skydiver]

And then after that, the last thing to account for is that the outputNumber is initialized to 7 instead of 0. Still relatively easy to figure out.

 

[Ranjith2523]

Look at the problem more simply. Let's just use 5 letters and multiply by 10

String letters = "abcde";
...
    outputNumber = (outputNumber* 10 + letters.IndexOf (inputString
[index]));

Let's have a message of bbbdddcece

First letter is b, it is at index 1 in `letters`.. Ouput number is 0. 0*10 is 0, plus index 1, is 1

Output number is now 1. Then it becomes 1*10 + 1:

11
111

That's the bbb done

Then it becomes

1113
11133
111333

That's the bbbddd done

1113332
11133324
111333242
1113332424

We are done. And you hopefully can see it's a simple numeric translation of the letters; the multiply by 10 just moves the existing number along to the left by one place so we have space to add another translated character

We can get away with times 10 because there are only 5 characters. If there were 10 chars it would also be fine, but just imagine if there were 11 or more chars to encode; things would start to go wrong because if you look at an output number of "20" encoding letters of ABCDEFGHIJK (which is 11 chars) we can't tell if 20 is CA or BK

CA = 2*10 + 0
BK = 1*10 + 10

Both these sums add up to 20. If we have 10 or more letter, multiplying by ten isn't enough to "move the existing number out of the way" so that we can add the 10th letter without smushing it into the other digits

Hopefully now you can see that so long as you multiply by any number greater than the amount of different letters you have, you move the existing number out of the way sufficiently that no letter addition collides with the existing number hash

Getting the number back to letters is the reverse operation

We've been multiplying by 10 every time and adding some number less than 10

If we were to divide by 10 instead and look at the remainder, it would give us the last addition we made

Let's go back to our hash of bbbdddcece:

1113332424

Divide by ten and what is the remainder?

4

What letter is at index 4?

e

What is left after we divide by ten?

111333242

Divide that by ten. Remainder is 2. 2 relates to c (a is zero, b is one, c is two...)

Keep going. We built this number by multiplying by ten over and over and adding on some number less than 10 (a remainder) so divide divide divide, by ten, and look at the remainder each time

Keep going until you've divided the 1113332424 number all the way to 0, the reminder each time is the letter

1113332424 / 10 = 111333242 r 4 (e)
111333242 / 10 = 11133324 r 2 (c)
11133324 / 10 = 1113332 r 4 (e)
1113332 / 10 = 111333 r 2 (c)
111333 / 10 = 11133 r 3 (d)
11133 / 10 = 1113 r 3 (d)
1113 / 10 = 111 r 3 (d)
111 / 10 = 11 r 1 (b)
11 / 10 = 1 r 1 (b)
1 / 10 = 0 r 1 (b)

We are done. Read up the rows for the letter in brackets and see that we get our original message back: bbbdddcece

Doing it times ten makes it simple to see but it's just a number. If you swap in 37 it will still work the same.

In c# you can get the remainder of a divide by using the % operator

107 % 10 gives 7

38 % 37 gives 1

If your output number was 38, and your multiplier was 37, your letters input must have been BB; 38 is 1*37 + 1, and B is 1

First thing I would like to say a BIG THANKS to you for spending some time and helping the people like me to gain their knowledge. Yes, your example is evident and easy to understand. I need to learn a lot and I am sure I will learn soon when I have such good people like you. Thank you so much again for your help and time.

 

[cjard]

You're welcome!

A small forum etiquette tip - you should generally avoid using the quote function, especially on a long post, if you just want express thanks for the post or ask a small related question. Quote is really good for having little bits of a post you want to respond to, like below, but a bit overkill if an entire post is quoted:

your example is evident and easy to understand

Great, any problems you get following it just let us know

I need to learn a lot and I am sure I will learn soon when I have such good people like you

Don't forget to give your tutor feedback too; they use it to guide you and inform on how to teach their classes - if the students all just disappear off onto the internet and come back with working solutions the tutor might think that everyone understood it well.. Letting them know feedback that you found it tricky and got some extra help will help them design future challenges