Java Reference
In-Depth Information
It is recommended to write a few auxiliary functions, as follows:
- compute the required number
k
of bits,
- build an array
int
[][]
storing the binary decompositions of values
stored in
decimalTab
,
- compute the Grundy function in binary.
Those functions can be reused in the remainder.
-
We shall make use of the following (admitted without proof) result:
Let a Nim game configuration be denoted by
x
0
,
x
1
,
...
,
x
m−
1
fruits
in respective bins. Then the current player has a winning strategy if
and only if
Grundy
(
x
0
,...,x
m−
1
)
=0.
In case we have
Grundy
(
x
0
,...,x
m−
1
)
= 0, the winning move is
described by the following steps:
-
We consider
Grundy
(
x
0
,...,x
m−
1
) in base 2, and we select the
maximum index
j
of a bit with value 1 in the decomposition. Such
a bit necessarily exits because of
Grundy
(
x
1
,...,x
m−
1
)
=0.
-
We search for an index
i
corresponding to a bin containing
x
i
fruits,
where
j
denotes the bit index of the binary decomposition of
x
i
with
corresponding bit value 1. Such an index
i
necessarily exists from
the Grundy function. Fruits will be removed from the bin
i
.
-
We shall remove from bin
i
a number of fruits such that the
remaining number of fruits
x
i
shall satisfy for all rank
h
:
x
i
[
h
]=
1
x
i
[
h
] f
grundy
[
h
]=1
x
i
[
h
]
−
otherwise.
In the example given in the former question, the index
j
is 3 and the
bin to select fruits from has index 1 (containing 9 fruits). We remove
4 fruits so that it remains exactly 5 fruits.
-
Write a function
pick
that takes as its argument an integer array
denoting a game configuration, and returns an integer array of size
2: the first integer shall report the index of the bin to select fruits
from, and the second integer shall give the number of fruits to remove
from the selected bin. In case the Grundy function is zero (we know we
are going to loose), we shall remove a fruit from the first non-empty
bin.
Search WWH ::
Custom Search