Adobe Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
What do you do in case of 1,2,3,3,3 ?
I haven't given much thought, just a quick one: If there are even no. of matchboxes with highest number of matchsticks, you pick all from one of them. If there are odd no. of such matchboxes, there is no winning move except if there is only one then you do same as (K-L).
But again whether it is a winning move would depend if you can get in similar situation again (i.e. more than 2 matchboxes with highest number of matchsticks). So, I guess we'll need to solve it to the last move to confirm if it is a winning move.
Find the last move for the win?
That would be:
All boxes empty except one, and last move being emptying last box.
Done. No coding needed?
#include <stdio.h>
typedef enum {false, true} bool;
int boxes[] = {1,1,2,1}; //boxes of sticks
#define N sizeof(boxes)/sizeof(*boxes)
/* mutually recursive functions our_move and opp_move return true
if 'we' are guaranteed a win with the right choices from that state;
can do this win 1 function (track "depth" recursion even vs. odd),
but mentally easier for me to think of 2 players*/
bool our_move();
bool opp_move()
{
bool opp_wins=false; //can opp. win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( !our_move() ) opp_wins=true; //opp. can win
boxes[i] += j;
if(opp_wins) return false; //we are not guaranteed win
}
}
return true; //boxes already empty, or we always win
}
bool our_move()
{
bool our_wins=false; //can we win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( opp_move() ) our_wins=true; //we "can" win
boxes[i] += j;
if(our_wins) return true; //we are guaranteed win
}
}
return false; //boxes already empty, or all choices lose
}
int main(void) {
int i, j;
/* we make our possible first moves and see if they guarantee win
(i.e, guarantee opp. loss ) */
for(i=0; i<N; i++)
for(j=1; j<=boxes[i]; j++)
{
boxes[i] -= j;
printf("First move <remove %d sticks from box %d>"
"can%s guarantee win\n",
j, i+1, (opp_move())?"":"not");
boxes[i] += j;
}
return 0;
}
My interpretation of your question. QA it Mr. "Solve Me Some Quadratic Equations" (code 123).
ideone.com/cfGilp
#include <stdio.h>
typedef enum {false, true} bool;
int boxes[] = {1,1,2,1}; //boxes of sticks
#define N sizeof(boxes)/sizeof(*boxes)
/* mutually recursive functions our_move and opp_move return true
if 'we' are guaranteed a win with the right choices from that state;
can do this win 1 function (track "depth" recursion even vs. odd),
but mentally easier for me to think of 2 players*/
bool our_move();
bool opp_move()
{
bool opp_wins=false; //can opp. win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( !our_move() ) opp_wins=true; //opp. can win
boxes[i] += j;
if(opp_wins) return false; //we are not guaranteed win
}
}
return true; //boxes already empty, or we always win
}
bool our_move()
{
bool our_wins=false; //can we win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( opp_move() ) our_wins=true; //we "can" win
boxes[i] += j;
if(our_wins) return true; //we are guaranteed win
}
}
return false; //boxes already empty, or all choices lose
}
int main(void) {
int i, j;
/* we make our possible first moves and see if they guarantee win
(i.e, guarantee opp. loss ) */
for(i=0; i<N; i++)
for(j=1; j<=boxes[i]; j++)
{
boxes[i] -= j;
printf("First move <remove %d sticks from box %d>"
"can%s guarantee win\n",
j, i+1, (opp_move())?"":"not");
boxes[i] += j;
}
return 0;
}
If N = 1, starting move is trivial.
- Subrat October 30, 2013For N > 1, the winning condition is to leave the opponent in a position that he will always has two boxes with same no. of sticks which are highest among all boxes. (e.g. 1, 2 , 3, 3)
Algorithm:
If the highest stick containing box has K sticks and second highest stick containing box has L sticks, pick up K - L sticks from the highest containing box. By doing this, you are reducing the problem size, and ensuring that you always have the control for winning condition. This way, the opponent can never put you in the same situation. In the end, the game will come down to X, X and ultimately reduce to 1, 1 with the opponent to play. This is where you will win the game.
Caveat:
If the game already starts with winning condition, and you have to play first, you don't have a chance to win (given the opponent is aware of the winning algorithm).