I have to find a php code to solve a math problem.
This is the problem description:
Players A and B are playing a new game of stones. There are N stones placed on the ground, forming a sequence. The stones are labeled from 1 to N. Players A and B play in turns take exactly two consecutive stones on the ground until there are no consecutive stones on the ground. That is, each player can take stone i and stone i+1, where 1≤i≤N−1. If the number of stone left is odd, A wins. Otherwise, B wins. Assume both A and B play optimally and A plays first, do you know who the winner is?
The line has N stones and are indexed from 1 to N --> N (1 ≤ N ≤ 10 000 000)
If the number of stone left is odd, A wins. Otherwise, B wins.
This is my code. It does work, but it is not correct.
<?php
$nStones = rand(1, 10000000);
$string = ("i");
$start = rand(1, 10000000);
$length = 2;
while($nStones > 0) {
substr( $nStones , $start [, $length ]): string;
}
if ($nStones % 2 == 1) {
echo "A";
} else {
echo "B";
}
?>
I think am missing the alternant subtraction of two consecutive stones by A & B, while $nStones > 0. Furthermore, the problem description mentions an optima subtraction until there is only one stone left. Therefore I guess the stones move together to their closest stones (the gaps disappear and are replaced by the closest stones).
I've made a start here:
<?php
class GameOfStones
{
const STONE_PAIR = 'OO';
const GAP_PAIR = '__';
public $line;
public function __construct($length)
{
$this->line = str_pad('', $length, self::STONE_PAIR);
}
// Removes a pair of stones from the line at nth location.
public function remove($n)
{
if(substr($this->line, $n-1, 2) == self::STONE_PAIR)
$this->line =
substr_replace($this->line, self::GAP_PAIR , $n-1, 2);
else
throw new Exception('Invalid move.');
}
// Check if there are no further possible moves.
public function is_finished()
{
return strpos($this->line, self::STONE_PAIR) === false;
}
// Representation of line.
public function __toString()
{
return implode('.', str_split($this->line)) ."
";
}
};
$game = new GameOfStones(6);
echo $game;
var_dump($game->is_finished());
$game->remove(5);
echo $game;
var_dump($game->is_finished());
$game->remove(2);
echo $game;
var_dump($game->is_finished());
Output:
O.O.O.O.O.O
bool(false)
O.O.O.O._._
bool(false)
O._._.O._._
bool(true)
Currently this class starts by making a line which is a string of 'O' characters.
So if the length was 5, the line would be a string like this:
OOOOO
The remove method takes an index. If that index was 1, first the line is checked at the string's 0 index (your n-1) for two consecutive O's. In other words 'are there stones to remove at a given position?'. If there are stones, we do a string replacement at that position, and swap the two Os for two _s.
The is_finished method checks the line for the first occurance of two Os. In other words if there are two consecutive stones there is still a move on the line to play.
The magic method __toString, is the string representation of a GameOfStones object. That's used as a way to visualise the state of the game.
O.O.O.O._._
The above shows four stones and two gaps (I'm not sure if the dot separators are necessary - the underscores can bleed into each other that's why I've used them).
I have added example use of the code, where (two) pairs of stones are removed from a line of six stones. After each removal we check if there is another possible move, or rather if the game has ended.
There is no player attribution currently, that's left to you.
Your last rule:
'If the number of stone left is odd, A wins. Otherwise, B wins.'
I am struggling with. See these examples:
i) Line of length 3:
OOO
O__ A (1)
End: one (odd) stone left.
ii) Line of length 4:
OOOO
OO__ A (3)
____ B (1)
End: zero (even) stones left.
ii) Line of length 7:
OOOOOOO
O__OOOO A(1)
O__O__O B(5)
End: three (odd) stones left.
I'd say that the person that removes the pair so the next player can't go is the winner. In game ii) above if A had played at position 1 (O__O), then they would prevent B from playing.