Question

Implement Hot Potato game

A group of people, numbered 1 to N, are sitting in a circle. Starting at person 1, a hot potato is passed. After X passes, the person holding the hot potato is eliminated, the circle closes ranks, and the game continues with the person who was sitting after the eliminated person picking up the hot potato. The last remaining person wins.

For example:

• if X = 0 and N = 5, players are eliminated in order, and player 5 wins
• If X = 1 and N = 5, the order of elimination is 2, 4, 1, 5.   

Write a program for general values of X and N.

• Ask a user for number of people and number of passes
• To speed up input, debugging, store names of the people in a file. Make sure no two names start the same letter ( Alex and Ana are not OK)
• Output number and/or the name of a person being eliminated
• Output number and the name of the winner
• Allow user to play the game as many times as user wants
• Node and List should be classes
• use try/catch to check dynamic memory allocation
• Make sure each function has a description, post and pre-conditions

Answer 1

The problem statement given is basically called as the josephus problem or the suicide circle problem and is an application of the queue.

The above diagram shows the execution of this problem.

The formula we use to resolve this problem is

josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1

  josephus(1, k) = 1

After the first person (kth from beginning) is killed, n-1 persons are left. So we call josephus(n – 1, k) to get the position with n-1 persons. But the position returned by josephus(n – 1, k) will consider the position starting from k%n + 1. So, we must make adjustments to the position returned by josephus(n – 1, k).

Program for this problem

// CPP program to find last man standing

#include<bits/stdc++.h>

using namespace std;

  

/* structure for a node in circular

   linked list */

struct Node

{

    int data;

    struct Node *next;

};

  

// To create a new node of circular

// linked list

Node *newNode(int data)

{

   Node *temp = new Node;

   temp->next = temp;

   temp->data = data;

}

  

/* Function to find the only person left

   after one in every m-th node is killed

   in a circle of n nodes */

void getJosephusPosition(int m, int n)

{

    // Create a circular linked list of

    // size N.

    Node *head = newNode(1);

    Node *prev = head;

    for (int i = 2; i <= n; i++)

    {

        prev->next = newNode(i);

        prev = prev->next;

    }

    prev->next = head; // Connect last

                       // node to first

  

    /* while only one node is left in the

    linked list*/

    Node *ptr1 = head, *ptr2 = head;

    while (ptr1->next != ptr1)

    {

        // Find m-th node

        int count = 1;

        while (count != m)

        {

            ptr2 = ptr1;

            ptr1 = ptr1->next;

            count++;

        }

  

        /* Remove the m-th node */

        ptr2->next = ptr1->next;

        free(ptr1);

        ptr1 = ptr2->next;

    }

  

    printf ("Last person left standing "

            "(Josephus Position) is %d\n ",

            ptr1->data);

}

  

/* Driver program to test above functions */

int main()

{

    int n = 14, m = 2;

    getJosephusPosition(m, n);

    return 0;

}

The last man standing (josephus position) = 13