EternalFire's blog

Hashing a board
By EternalFire, history, 5 years ago, In English

We usually use hash on strings to determine whether they are the same. But now I am wondering how to determine if two sub-board consists of lowercase English letters from (x1, y1) to (x2, y2) are the same. Is it possible to use hash? If yes, then how to get hash value of them?

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Let me take a

Unable to parse markup [type=CF_TEX]

board for the example (numbers written in base 10):

1 2 4 3 6

8 6 2 1 3

9 3 7 2 4

If you want to get hash value of sub-board (2, 2) to (3, 4), you can get the hash value of the string 6|2|1|0|0|3|7|2 (the character | not appear in the real string, I just put it to seperate the numbers).

That string can be built by start at cell (2, 2), read from left to right, top to bottom to cell (3, 4). If you meet a cell which doesn't lie inside the sub-board, you assign it value 0.

So what you need is calculate

Unable to parse markup [type=CF_TEX]

is the hash value from (1, 1) to (i, j). Then for query (x1, y1), (x2, y2) you can use H to calculate the answer easily.

Sorry for my bad English.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I haven't done many problems of this kind but probably you can use an idea similar to string hashing by considering the characters in the sub-board in the row major order and constructing a string using that and then hashing that string. Firstly, for two sub-boards, we must consider their sizes. If their sizes are different, then the sub-boards are also different. Otherwise, use hashing.

→ Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

You extend 1d hashed to 2d the same way you extend 1d prefix sums to 2d. You just need to take different vertical and horizontal base.

For table:

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

and bases p and q, hash table will look like:

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

You calculate it this way:

Unable to parse markup [type=CF_TEX]

And to get hash of an area you use:

Unable to parse markup [type=CF_TEX]

→ Reply