Microsoft Interview Question
SDE1sTeam: Outlook
Country: United States
I can't seem to edit my answer. I have a much more elegant solution which uses a maximum of 10 bits, based upon pretonesio's 11 bit solution:
1. If the two pieces are on opposite vertical halves, the first 5 bits should represent the location of the piece in the first half and the next 5 bits should represent the location of the piece in the second half = 10 bits
2. If the pieces are in the same vertical half but in different quarters, use 1 bit to represent which half they are in, the next 4 bits to represent location of piece in upper quarter, next 4 for location of lower quarter piece = 9 bits
3. If they are in the same quarter but in different vertical eighths, use 2 bits to represent which quarter they are in, next 3 bits for location of piece in left eighth and next 3 bits of location of piece in right eighth = 8 bits
4. If they are in the same vertical eighth but in different sixteenth, use 3 bits for the eighth they are in, 2 bits for the piece in upper sixteenth and 2 bits for the piece in lower sixteenth = 7 bits
5. If they are in the same sixteenth but in different vertical thirtysecondths, use 4 bits for the sixteenth and 1 bit each for the location of each piece in respective thirtysecondth = 6 bits
6. If they are in the same thirtysecondth, use 5 bits to represent the location of that thirtysecondth = 5 bits
... As nice and elegant as this is, you still have to have a preconceived idea of where they are in order to decode from any given bit representation among all of them... which would require more bits to store that info. X_X
I mean if having extra information outside of the bit-representation is allowed this is a wonderful solution. If not, then you're trying to mash 2016 different combinations into a bit representation that at max holds 1024 and I'm not entirely sure if its possible.
Edit: tl;dr Given only the bit-representation, there is no schema to fit 2016 explicit combinations into 1024 slots using bit-representation.
You're treating space differently from 0, which means your number system is not strictly base 2, and your solution cannot qualify as using only 10 bits.
@Brennahan: it is not possible to mash 2016 combinations into a bit representation that holds 1024 combinations at max. Consider any function that maps a 10-bit value to a set of 2 positions. Clearly, since there are only 1024 possible inputs, there are only 1024 possible outputs. Some of the 2016 sets of 2 positions therefore have no 10-bit value that can represent them.
@brennahan: The limitation you're talking about is true for any encoding/decoding scheme. Even the 11 and 12 bits schemes. If you're using the 12 bit scheme, you have to know which 6 bits stand for the first piece's location and which for the second's. And how the locations are encoded to 6 bits. When you're using the 1 bit representation, you have to specify the combination that '0' represents and the combination that '1' represents. Which can also be phrased like this: It is not possible to have an encoding/decoding scheme whose decoder is an empty program.
@eugene.yaravoi: Yes you're correct, the solution is not strictly base 2. You cannot use a 10 bit integer datatype to represent all 2016 configurations. However, it seemed to me that the phrasing of the question allowed for this solution.
One way of doing it with 11 bits is like the following:
You use 6 bits to represent your first position, and you use 5 bits to represent your second. You first position is represented by a simple x,y bit scheme. The second position will be represented as follows:
If 5 bits for the second position are passed in, make a x,y grid on the opposite half of the board and use the 5 bits to locate the second position.
If 4 bits are passed in, do the same thing as previously but in the opposite quadrant on the same half of the first picked point.
If 3 bits, use them to find it on the opposite eight on the same quadrant
If 2 bits , on the opposite sixteenth of the same eight
If 1, on the same thirtysecondth of the same sixteenth
if no bits, the second position is right below/above the first one
So basically you exploit the fact that no 2 pieces can be in the same place and save a bit
(I am Bren, just logged in to acct.)
The only other way I can think of is the case where order does not matter. In this case, you can have a base piece and a moving piece. The base piece sits on a spot, and the moving piece would cover the rest of the "NEW" combinations of spots. This mean you just have a summation for the total combination. 63 summation comes out to 2016 possible combinations, though again, you would still need 11 bits to cover it all.
Exactly! But I know there is a way of solving the problem with only 10 bits. However I'm not sure how.
how are u concerned about two adjacent positions, two positions could be any where in chess board
@pretonesio.
>> If 5 bits for the second position are passed in, make a x,y grid on the opposite half of the board and use the 5 bits to locate the second position.
Could you please define/elaborate what you mean by 'opposite half of the board'?
If the first piece is located at position (0,0) and the second piece is located at (8,8), how will 5 bits suffice to identify the second piece relative to the first? Please clarify.
@m@}{: your solution seems to be the most elegant one if I am not missing anything.
3 bits - to represent 'quarter' (0,1,2,3)
3 bits - to represent 'x' inside quarter (0,1,2,3)
3 bits - to represent 'y' inside quarter (0,1,2,3)
Let's consider how many ways there are to place two pieces on an 8x8 chessboard. The first piece can be placed in one of 64 locations. The second piece can be placed in any one of the 63 remaining locations. Then, assuming you don't care about the order of locations, every pair of locations (i, j) is equivalent to the pair (j, i), so to get the total number of different pairs of locations, we need to divide by 2.
We get 64 * 63 / 2 = 2016.
There is therefore no way to do this with 10 bits, since a 10-bit value can only have one of 2^10 = 1024 possible values. With only 10 bits, only 1024 of the 2016 possibilities could have a representation. All the claims in this thread that you can do it with 10 bits are groundless.
With 11 bits, you can represent 2048 values, which is sufficient. The algorithm for encoding two locations as an 11-bit value is relatively straightforward. Give each chess square a number from 1 to 64. Then represent a pair of locations as the smaller number followed by the larger number. Map an integer to each pair in order, like this:
(1, 2) -> 0
(1, 3) -> 1
...
(1, 64) -> 62
(2, 3) -> 63
(2, 4) -> 64
...
(2, 64) -> 124
(3, 4) -> 125
...
(63, 64) -> 2015
You can do some simple math to compute the mapping efficiently.
The locations then have a 1-to-1 correspondence with integers between 0 and 2015. 11 bits are necessary and sufficient to represent these.
what if you consider 00010 and 10 as two different numbers then the whole argument you made will not hold good..
If you consider 10 and 00010 as two different numbers, you are not working in base 2. You've implicitly introduced a third type of symbol: the space. The designation "bit" applies to a 0 or 1 symbol in base 2.
yes you are right but if you take any bit compactness .. golomb , exp golomb..you would use start and end symbol which inherently will give you space symbol
The idea of some compression schemes is that you can save space on frequently-occurring bit sequences by encoding them with shorter bit sequences. You would then save on the more frequently-occurring bit sequences at the expense of the less frequently-occurring ones.
That's not really what we're talking about, though. To represent just one object (just one selection of two positions on an 8x8 chessboard), if you want to be able to represent all 2016 possibilities, you cannot do it in less than ceil (log_2(2016)) = 11 bits. There is no way around this.
For that matter, even if we talk about space usage when you need to store N objects, you can't be guaranteed to be able to represent N such objects in less than (roughly) 11N bits. Compression schemes are only effective when some objects occur more frequently than others. Unless you know for a fact that your distribution of objects is non-random, you can't be guaranteed any space savings.
There are 4,032 total combinations for 2 different positions on a chessboard (=64*63(2 pieces can't occupy the same space assuming chess rules)) 2^12 would be 4096 so we would need 12 bits in order to cover all possibilities for the 2 positions.
In terms of determining the exact positions from the bit representation, you would need to set up a schema to translate(i.e. the first 6 bits determine where the first position is and the later 6 bits represent the second position is.)
It is true that a naive way can use 12 bits. All you need to do is label the different rows and columns of the board from 0-7 and use that as a x,y guide. That way, just like you described, you can use 12 bits. However, I know there is a way of doing it with only 10 bits. I'm just not sure how.
6 bits.. bcz.. on an 8x8 chess board... there can be 64 boxes... thus... in the worst case... we need atleast 6 bits.. to distinguish all d boxes dintinctly
lets see the possible number of combinations possible
8*8*8*8/2 = if positions mutually independent = 12 bits
otherwise
8*8*(8*8-1)/2 = 2016 combinations
total number of combinations possible with 3 bits=
0,1,00,01,10,11,000,001,010,011,100,101,110,111
2+2^2+2^3 = 14 = 2 (2^3-1)
total combination with 10 bits=
2(2^10-1)= 2046 combinations.. i will update the answer with a logical division or some1 can work it out
There are 64 squares and 32 pieces.
I take it, that 2 positions means the state of ALL of the white and black pieces at a given time or a "snapshot".
To represent 2 positions: won't you need 32 longs (each with 64 bits), so that each long represents a chess piece and each bit (long has 64 bits) in that long represents the position on any one of the 64 squares.
what do you thing about this solution:
we can use 5 bits for the white squares and 5 bit for the black squares.
then you have another bit to tell if you need to refer to a white or a black square
i think even you can do this only with 6 bits:
one bit is for the color and let say if color is white then you go to the 5 bit positions by starting at 00000 and if is black you start at 00001 then each loop you move two positions
I dont know where you all get those ideas...
An 8x8 chessboard with two pieces, where each position is represented as tuple (x,y) and the two pieces using two tuples as a set (since order does not matter), like {(x1,y1),(x2,y2)}...
That is the basic mathematic abstraction of the input space. Now for the real question. We are to find the number of all possible, different tuple-sets, which is given by
256!/(254! 2!) - 256 = 32384
Minus 256 in the end, because thats the amount of tuple-sets, where both tuples are equal, a case that is not possible.
Now that makes 14 < log2(32384) <15, so we can conclude that we can save one bit, that is encode the whole thing with 15 bits instead of the obvious 16...
You realize, with the way this question is asked, the answer of '2 bits' suffices. You are only asking bits to represent two positions out of 64 positions, not every possible combination of the 2 positions on the board...
You can represent 2^n values with n bits.
However, you can represent
2^n + 2^(n-1) + 2^(n-2) + ... 1 = 2^(n+1) - 1
values with *atmost* n bits
So you can represent 2^11 - 1 = 2047 different values using just 10 bits.
Now here's the catch in the problem, as brennahan already mentioned - the order of the pieces doesn't matter.
So there are 64C2 = 2016 possible ways to arrange two pieces on an 8x8 chessboard.
Therefore, it should definitely be possible to represent 2016 ways using 10 bits.
In fact, you can represent 2016 values using all 5, 6, 7, 8, 9 and 10 bit sequences.
Here's one method:
Consider all possible relative positionings:
Just keep on repeating this procedure, using all sequences of 5, 6, 7, 8, 9 and 10 bits
You should be able to represent 32 + 64 + 128 + 256 + 512 + 1024 = 2016 ways to arrange the pieces.
Edit: I just wrote a program to automatically assign bit sequences to every possible configuration. There are a lot of them for 8x8 so I'll just show a solution for a 4x4 chessboard(120 configurations) using atmost 6 bits:
- anotherguy August 29, 2013