stone division code
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: stone division code

  1. #1
    Join Date
    Jul 2017
    Posts
    1

    stone division code

    Consider the following game:

    There are two players, First and Second, sitting in front of a pile of stones. First always plays first.
    There is a set, , of distinct integers defined as .
    The players move in alternating turns. During each turn, a player chooses some and splits one of the piles into exactly smaller piles of equal size. If no exists that will split one of the available piles into exactly equal smaller piles, the player loses.
    Both players always play optimally.

    Given , , and the contents of , find and print the winner of the game. If First wins, print First; otherwise, print Second.

    Input Format

    The first line contains two space-separated integers describing the respective values of (the size of the initial pile) and (the size of the set).
    The second line contains distinct space-separated integers describing the respective values of .

    Constraints

    Output Format

    Print First if the First player wins the game; otherwise, print Second.

    Sample Input 0

    15 3
    5 2 3

    Sample Output 0

    Second

    Explanation 0

    The initial pile has stones, and . During First's initial turn, they have two options:

    Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
    stone-division.png
    Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
    stone-division-2.png

    Because First never has any possible move that puts them on the path to winning, we print Second as our answer.

    Submissions: 214

    Max Score:

    50

    Difficulty:

    Hard

    Rate This Challenge:
    More


    my code is this but it not pass all the test cases
    so i need answer for this


    Code:
    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
        int n,m;
        int flag=0;
        cin>>n;
        
        cin>>m;
        int arr[m];
        for(int i=0;i<m;i++){
            cin>>arr[i];
        }
        for(int i=0;i<m;i++){
            if(n%arr[i]==0){
                int a=arr[i];
                if(a%2!=0){
                    flag=1;
                }
                else
                {
                    flag=0;
                }
                  
                
            }    
        }
        if(flag==1){
            cout<<"Second";
        }
        else{
            cout<<"First";
        }
        
        return 0;
    }
    Last edited by 2kaud; July 30th, 2017 at 11:45 AM. Reason: Added code tags

  2. #2
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,837

    Re: stone division code

    When posting code, please use code tags so that the code is readable. Go Advanced, select the formatted code and click '#'.

    For the test cases where your code doesn't provide the correct answer, have you traced through the code with the debugger to see why?
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.4.4)

  3. #3
    Join Date
    Feb 2017
    Posts
    165

    Re: stone division code

    Quote Originally Posted by mandeepsingh1616 View Post
    my code is this but it not pass all the test cases
    so i need answer for this
    Here's what seems like the original description of the problem:

    https://www.hackerrank.com/challenges/stone-division

    I don't see anything in your code suggesting there are two players (taking turns at splitting piles)?

    One approach would be to introduce a sequence of piles (SoP) where each pile is an integer telling how many stones are in that pile. All possible splits of SoPs can then be generated recursively until no further split is possible (whereby the recursive path up to that point represents one game the player on turn has lost.)

    I can think of a way to implement the SoPs quite densely but it's still an exhaustive combinatorial solution. There may be some number theoretical or combinatorial results available that could simplify things. I don't know really. Also I don't quite understand what's meant by "both players play optimally"? It's not quite clear to me who wins if both players can win?

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,837

    Re: stone division code

    Also I don't quite understand what's meant by "both players play optimally"
    A player always makes the best possible move that would enable that player to win. ie a player can't play to loose or to give advantage to the other player or to lessen their own chances of winning.

    There is actually no need to play out the game from a starting point. All that is needed is to determine which player can't win from a position. If a player can't win, then the other player by default is the winner.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.4.4)

  5. #5
    Join Date
    Feb 2017
    Posts
    165

    Re: stone division code

    Quote Originally Posted by 2kaud View Post
    A player always makes the best possible move that would enable that player to win. ie a player can't play to loose or to give advantage to the other player or to lessen their own chances of winning.

    There is actually no need to play out the game from a starting point. All that is needed is to determine which player can't win from a position. If a player can't win, then the other player by default is the winner.
    I'm not so sure about that, or rather it depends on what is meant by playing "optimally".

    I've implemented the game with optimal playing defined by these rules: A player must, if possible,

    1. split a single pile into unsplittable piles (instant winning move)
    2. split a pile to produce an even number of once-splittable piles (deferred winning move)
    3. not split a pile to produce an odd number of once-splittable piles (deferred losing move)

    With this quite reasonable definition a optimal playing the game can still be won by both players depending on how the splitting unfolds so to me it looks like all possible games have to be investigated.

    It cannot be ruled out that there exists an optimal strategy for this game like it does for the Game of Nim for example, but that's a different ballgame. It cannot be expected from participants in a programming contest to come up with a thorough math analysis of a non-trivial game. On the other hand the constrains specified for this game potentially can give rise to a "combinatorial explosion" so one cannot rule out that there's some clever shortcut available.

    Anyway here is my implementation. It recursively generates all possible outcomes of the game. The objective was to be able to follow the behavior of the game, not to optimize speed. As I mentioned, both players can win and I cannot tell whether this is due to a mistake in the implementation or the way it should be. Unfortunately I've had only one officially verified test-case available (given in the game description). The program starts in the test() function. I've used Visual Studio 2017 Community:

    Code:
    #include <vector>
    #include <set>
    #include <string>
    #include <iostream>
    #include <algorithm>
    
    using Pile = int; // a pile
    using SoP = std::vector<Pile>; // sequence of piles
    using SoPstack = std::vector<SoP>; // stack of SoPs
    using Set = std::vector<int>; // set of divisors
    
    bool splittable(Pile pile, int divisor) { // pile is splittable by this divisor?
    	return (pile % divisor) == 0;
    }
    
    Pile split(Pile pile, int divisor) { // do split
    	return pile / divisor;
    }
    
    bool splittable(Pile pile,  const Set& set) { // pile is plittable by some divisor?
    	for (const int divisor : set) {
    		if (splittable(pile, divisor)) return true;
    	}
    	return false;
    }
    
    bool splittable(const SoP& sop, const Set& set) { // is there at least one splittable pile in this SoP?
    	for (const Pile pile : sop) { 
    		if (splittable(pile, set)) return true;
    	}
    	return false;
    }
    
    bool once_splittable(Pile pile, const Set& set) { // pile is splittable exactly once?
    	for (const int divisor : set) {
    		if (splittable(pile, divisor)) { // splittable once - OK
    			Pile p = split(pile, divisor);
    			if (splittable(p, set)) return false; // splittable twice - bad
    		}
    	}
    	return true;
    }
    
    int num_once_splittable(const SoP& sop, const Set& set) { // count number of once_splittable piles in SoP
    	int piles = 0;
    	for (const Pile pile : sop) { 
    		if (once_splittable(pile, set)) ++piles;
    	}
    	return piles;
    }
    
    
    void printgame(int depth, int& count, int&first, SoPstack& stack, const SoP& winner) { // print game and update counters
    	++count;
    	std::cout << "new game " << (count) << std::endl;
    	int level = 0;
    	for (const SoP& sop : stack) {
    		std::cout << ">" << (level++) << ": ";
    		for (Pile pile : sop) std::cout << pile << " ";
    		std::cout << std::endl;
    	}
    	std::cout << ">" << (level) << ": ";
    	for (Pile pile : winner) std::cout << pile << " ";
    	std::cout << std::endl;
    
    	if (((level % 2) == 1)) {
    		++first;
    		std::cout << "game over, first won" << std::endl;
    	} else {
    		std::cout << "game over, second won" << std::endl;
    	}
    }
    
    	// each recursive call is one turn of the game
    void play(const SoP& sop, const Set& set, int depth, int& count, int&first, SoPstack& stack) {
    
    	stack.push_back(sop); // push current SoP
    
    	std::set<Pile> unique;
    	for (const Pile pile : sop) unique.insert(pile); // extract set of unique piles
    
    	SoPstack moves;
    	for (const Pile pile : unique) { // collect all valid splits (moves)
    		SoP nxt = sop;
    		nxt.erase(std::find(nxt.begin(),nxt.end(), pile)); // remove pile to be split
    
    		for (const int divisor : set) { 
    			if (splittable(pile, divisor)) { // split pile with valid divisors
    				Pile p = split(pile, divisor); // do split
    				SoP move = nxt;
    				if (splittable(p, set)) {
    					for (int i=0; i<divisor; ++i) move.push_back(p); // add on split piles (if splittable)
    				}
    				moves.push_back(move);
    			}
    		}
    	}
    
    	bool endgame = false;
    
    	if (!endgame) {  // find winning split (last pile split to non-splittable piles)
    		for (const SoP& move : moves) {
    			if (move.empty()) {
    				printgame(depth, count, first, stack, move);
    				std::cout << "(by splitting final pile into non-splittable piles)" << std::endl;
    				endgame = true;
    				break;
    			}
    		}
    	}
    
    	if (!endgame) { // find winning split (even number of once-splittable piles)
    		for (const SoP& move : moves) {
    			int piles = num_once_splittable(move, set);
    			if (piles != move.size()) piles = 0; // all piles must be once-splittable
    
    			if ((piles != 0) && ((piles % 2) == 0)) { // even number of piles
    				printgame(depth, count, first, stack, move);
    				std::cout << "(by leaving an even number of once-splittable piles)" << std::endl;
    				endgame = true;
    				break;
    			}
    		}
    	}
    
    	if (!endgame) { // avoid a losing split (odd number of once-splittable piles)
    
    		SoPstack moves2;
    		for (const SoP& move : moves) {
    			int piles = num_once_splittable(move, set);
    			if (piles != move.size()) piles = 0; // all piles must be once-splittable
    
    			if ((piles == 0) || (piles % 2) == 0) moves2.push_back(move); // not a losing move
    		}
    
    		if (!moves2.empty()) moves = std::move(moves2); // no losing moves
    	}
    
    	if (!endgame) { // no winning split - investigate all valid splits (moves)
    		for (const SoP& move : moves) {
    			play(move, set, depth+1, count, first, stack); // next game level
    		}
    	}
    
    	stack.pop_back(); // pop current SoP
    }
    
    void stone_division(const SoP& sop, const Set& set) {
    	if (sop.empty() || set.empty()) {
    		std::cout << "Stone Division: Invalid input !!!" << std::endl;
    		return;
    	}
    	std::cout << "*** Stone Division ***" << std::endl;
    	int count=0, first=0;
    	play(sop, set, 0, count, first, SoPstack{});
    	std::cout << "*** End ***" << std::endl;
    	std::cout << "total games=" << (count);
    	std::cout << ", first won=" << (first) << std::endl;
    }
    
    void test() {
    	stone_division(SoP{Pile(15)}, Set{5,2,3});
    //	stone_division(SoP{Pile(15)}, Set{15,5});
    //	stone_division(SoP{Pile(8)}, Set{4,2});
    //	stone_division(SoP{Pile(12)}, Set{4,3,2});
    //	stone_division(SoP{Pile(9)}, Set{3});
    //	stone_division(SoP{Pile(45)}, Set{15,5,3});
    }
    Last edited by wolle; August 4th, 2017 at 05:25 AM.

  6. #6
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,837

    Re: stone division code

    Anyway here is my implementation
    As it's a programming challenge, that's why I haven't posted a solution!
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.4.4)

  7. #7
    Join Date
    Feb 2017
    Posts
    165

    Re: stone division code

    Quote Originally Posted by 2kaud View Post
    As it's a programming challenge, that's why I haven't posted a solution!
    It's a challenge, not a contest. It's like the difference between a voluntary exercise and a grade-affecting homework. The challenge is publicly available in the "practice" department at HackerRank and there's even a "reveal solutions" button for members. But okay I'll discuss the solution I think I've found in general terms only.

    I have used the implementation in my previous post to test a well known optimal strategy in game theory. I call it Strategy X not to reveal too much. It seems to work but to rely on it one must first formally prove that it works for this game indeed.

    Anyway I now understand the meaning of "both players play optimally". The rules 1-3 (see my previous post) only stipulate the obvious namely that a player must make a winning move whenever possible. But to play optimally a player must also play according to a global winning strategy if one exists for the game, like Strategy X.

    Applying Strategy X means each player tries to make a split that sets the player on a winning path the other player cannot break. So the game reduces to the question of which player can first make the winning strategic split. Jostling for this split typically ends quickly. If the first player cannot make it in the first turn of the game the second player usually can make it in the next (if the first player hasn't anticipated that and made a preventive split).

    A proper solution to this game would be;

    1. Prove that Strategy X applies to the game.
    2. Write a program that generates all possible outcomes of the game according to rules 1-3 and Strategy X.

    And it looks like Strategy X is stronger than the rules 1-3 so 2 becomes,

    2. Write a program that generates all possible outcomes of the game according to Strategy X.

    Finally here's a tutorial on this kind of games,

    https://www.topcoder.com/community/d...gorithm-games/
    Last edited by wolle; August 8th, 2017 at 12:14 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)