Question

C++ please asap

2. In the game of 15, square pieces numbered I through 15 are situated in a 4 by 4 tray, with one empty slot, so the pieces can be moved incrementally with the goal of placing them in ascending order (1,2,3, 4 in the first row etc. 4, 5,6,7 in the second row etc.). To represent the current configuration, we use a four by four array of int in which the unique values 0 through 15 are stored (where 0 represents the empty slot). Write a perfect hash function for the trays. Your function is not required to be minimal. unsigned int hash (int tray 11 14], unsigned int tableSize) t

Answer 1

Well, I think I can help you out on this. You just need a perfect hashing algorithm that can uniquely identify the different tray matrices. The different tray matrices arise from moving the '0' piece accordingly. (I hope I understood the question in the correct way). So basically we need a hash function to uniquely identify a matrix. Hey, we can use polynomial hashing, heard about it? If not, no problem I will explain it to you. We need a base prime number 'p' and a bigger modulo prime 'P', where P>>p (i.e modulo prime should be much much bigger than the base prime). Now, all we need is a polynomial that uses these two primes and produces a collision-free hash value. Well from my little experience I can give you a hash function that has proved helpful for me over time in preventing collisions. The polynomial goes as follows:-

f(x)-(f(x-1) +ar(i) * p)%P f(0) ar(0)

Hold on, it might look scary but is extremely easy. Suppose we have an array ar[] = {1, 2, 3} and we want to uniquely represent this array by a single number, so let us apply this formula, shall we? let us select p = 5, P = 1000000007. Now f(0) = ar(0) = 1, f(1) = (f(0) + ar(1) * 5¹ ) % 1000000007, calculating this gives us f(1) = (1 + 2 * 5¹) % 1000000007 => f(1) = 11. Now that we have f(1) we can calculate f(2) = (f(1) + ar(2) * 5²) % 1000000007 => f(2) = (11 + 3 * 5²) % 1000000007 => 86. Thus f(3) = 86 is the unique representation number for the array {1, 2, 3}. That is the array {1, 2, 3} is equivalent to 86. Now there can be collisions but lets not get into that as that would be deviating much farthar away from the topic.

So, we have at our hand a matrix, a polynomial hashing function, and we also know how its working is done, except for the fact that we know its working on only 1-D arrays but instead, we have a 2-D array at hand. No worries things won't change at all if we traverse the matrix row-wise and keep on adding the values in the polynomial. What I mean to say is that first start out from the first row and keep on calculating the hash value, once the row is finished just move on to the next row and keep on adding to the polynomial. What we are trying to do is flattening out the matrix. This won't produce changes at all because of the most important factor in this problem that is all the values in the tray matrix are different, if there have been repeated values, we would have gotten into a bit of trouble, but we don't need to worry about that. So I have given you the polynomial hashing algorithm, shown you how it works, explained why it would also work on a matrix, all we need now is the code, which I am going to give it to you. But before that one last thing, how should we select p and P where p is called as the base prime and P is called the modulo prime. Again there is a lot of heavy maths involved around selecting the precise values for a precise problem, I am going to give you a little secret from my little experience that p = 2 and P = 1000000007 works out fine in most of the problems. Enough talking here is the code in c++ for you. I am providing you with the code that will go inside your given function hash():-
   long long p = 2;
   long long P = 1000000007;
   long long hesh = 0;
   int idx = 0;
   for(int i = 0; i < 4; i++)
   {
       for(int j = 0; j < 4; j++)
       {
           int val = tray[i][j];
           long long Pow = pow(2, idx);
           hesh = (hesh + (val % P * Pow % P)) % P;
           idx++;
       }
   }
   return hesh;

Now, I hope i did justice to your question. One more thing before ending, if two different tray matrices produce the same hash value then we say collision has occurred between the hash value and then I will teach you about double hashing in which case we will use a total of four primes, but given the distinctivity of the values I don't think collision would occur.

If you have any kind of doubt just leave a comment down below about what is bothering you and I will be more than happy to help you out any time. Thank you.