Jump to content

Probability Puzzle #2

Gargamel

By Gargamel
in Science & Spaceflight

 Share

Recommended Posts

Gargamel

Gargamel

Posted
Posted (edited)

With the other thread in mind:

 

I'll post up this question. Starting a new thread to keep the discussions separate, as they are different.   Again some of you will get this quickly, some won't, so spoiler tags please if you don't mind. 

Since we're on a PG rated forum, I'm going to go less Deer Hunter here, and more Toy Story.  I believe I first read about this as one of those stupid interview questions the big tech companies used to ask. 

You and a competitor are given a (one) revolver that has 6 chambers in the cylinder.   The Game master has loaded 2 bullets, in consecutive chambers into and spun the cylinder so that the chamber that rests under the firing hammer is random (purely random).   The gun is mounted so that when the trigger is pulled, it will always hit the target.    The object of the game is to be the last person to hit the target.  You have no way of knowing the location of the bullets in the cylinder. 

You win the coin toss, and are allowed to choose if you want to shoot first or second.

What do you choose and why?

Edited by Gargamel
Link to comment
Share on other sites
Superfluous J

Superfluous J

Posted
Posted

If somoene tells me that because of some sort of expectance-based theory of whateveritis that my analysis is incorrect, I'm going to go all Deer Hunter on you.
 

Spoiler

 

Well there are 6 possibilities, B for Bullet, E for Empty:

  1. BBEEEE - First pull shoots, first person loses.
  2. BEEEEB - First pull shoots, first person loses.
  3. EEEEBB - 5th pull shoots, first person loses.
  4. EEEBBE - 4th pull shoots, second person loses.
  5. EEBBEE - 3rd pull shoots, first person loses.
  6. EBBEEE - 2nd pull shoots, second person loses.

So you want to go 2nd.

 

 

Link to comment
Share on other sites
Xd the great

Xd the great

Posted
Posted

Shoot first?

If the hammer hits one of the bullet chamber, boom! I win.

If the hammer hits 2 or 4 spaces from the first bullet, I win.

So thats 4/6, or 2/3 of winning.

Case closed.

I assumed that the revolver cannot be spun and that it always rotates in the same direction, which is usually the normal life.

Link to comment
Share on other sites
magnemoe

magnemoe

Posted
Posted
2 hours ago, 5thHorseman said:

If somoene tells me that because of some sort of expectance-based theory of whateveritis that my analysis is incorrect, I'm going to go all Deer Hunter on you.
 

  Hide contents

 

Well there are 6 possibilities, B for Bullet, E for Empty:

  1. BBEEEE - First pull shoots, first person loses.
  2. BEEEEB - First pull shoots, first person loses.
  3. EEEEBB - 5th pull shoots, first person loses.
  4. EEEBBE - 4th pull shoots, second person loses.
  5. EEBBEE - 3rd pull shoots, first person loses.
  6. EBBEEE - 2nd pull shoots, second person loses.

So you want to go 2nd.

 

 

You are correct, intuitive I wanted to go first, But see that second is far better as if first fire you win. 

Link to comment
Share on other sites
K^2

K^2

Posted
Posted

Yeah, this problem is solved by brute force the easiest. There's some clever math one can do to arrive at the same result, which may generalize better, but I don't see a reason to bother with it.

Link to comment
Share on other sites
Cunjo Carl

Cunjo Carl

Posted
Posted (edited)

Hey, this was a fun one! I got a formula for probability I'm happy with. I'll pose a follow-on question, though... Is it better for you if the ordeal is done with a 5-shooter or a 6-shooter?

My answer:

Spoiler

Prob for second player win = 1+floor(numChambers/2)/numChambers

6 shooter narrowly edges out 5.

 

Edited by Cunjo Carl
Fixing a poor variable name choice. We've all been there!
Link to comment
Share on other sites
Superfluous J

Superfluous J

Posted
Posted
29 minutes ago, Cunjo Carl said:

Hey, this was a fun one! I got a formula for probability I'm happy with. I'll pose a follow-on question, though... Is it better for you if the ordeal is done with a 5-shooter or a 6-shooter?

Same analysis I did for the first question below.

Spoiler
  1. BBEEE - first loses
  2. BEEEB - first loses
  3. EEEBB - second loses
  4. EEBBE - first loses
  5. EBBEE -second loses

So you still want to go second.

 

Link to comment
Share on other sites
Reactordrone

Reactordrone

Posted
Posted (edited)
Spoiler

if you label the chambers with rounds in as 1 and 2, if you go first the second shooter wins when the hammer drops first on chambers 6,4,2 and 1. That's four out of six so better to go second.

Seems logical.

Edited by Reactordrone
Link to comment
Share on other sites
kerbiloid

kerbiloid

Posted
Posted

Heh-heh, formula-schmormula.

Only Monte-Carlo, only hardcore.

Spoiler 

#include <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>

int const
	DEFAULT_TEST_COUNT = 100,
	DEFAULT_CHAMBER_COUNT = 6,
	DEFAULT_ROUND_COUNT = 2,
	DEFAULT_PLAYER_COUNT = 2;

char const
	MARK_EMPTY = '.',
	MARK_LOADED = 'o',

	MARK_CLICK = '.',
	MARK_BANG = '*',

	SEPARATOR = '\t';

std::string const
	TXT_PLAYER = "\tPlayer #",
	TXT_WINS = " wins!",

	TXT_NO_CHAMPION = "No champion.",
	TXT_CHAMPION = "The champion is ";


class CTest final
	{
	private:

		static std::vector <int> m_arrResult;

		static int m_nPlayerCount;

		int m_nWinner = -1;

		std::vector <bool> m_arrChamber;

	public:

		CTest(int const nChamberCount)
			{
			m_arrChamber.resize(nChamberCount, false);
			}

		static void run
			(
			int const nPlayerCount,
			int const nChamberCount,
			int const nRoundCount,
			int const nTestCount
			)
			{
			m_nPlayerCount = nPlayerCount;

			std::srand(std::time(nullptr));

			m_arrResult.resize(nPlayerCount, 0);

			int nPlayerIndex;

			for (int i = 0 ; i < nTestCount; ++i)
				{
				CTest objTest(nChamberCount);

				objTest.load(nRoundCount);

				std::cout << i << SEPARATOR;

				nPlayerIndex = objTest.runTest();

				m_arrResult[nPlayerIndex]++;

				std::cout << TXT_PLAYER << nPlayerIndex << TXT_WINS << std::endl << std::endl;
				}


			showResult();
			}


		void load(int nRoundCount)
			{
			if (nRoundCount <= 0)
				return;

			int const nChamberCount = m_arrChamber.size();

			if (nRoundCount >= nChamberCount)
				{
				m_arrChamber = std::vector <bool> (m_arrChamber.size(), true);

				return;
				}

			int nChamberIndex = std::rand() % nChamberCount;

			for (; nRoundCount > 0; --nRoundCount)
				{
				m_arrChamber[nChamberIndex] = true;

				if (++nChamberIndex >= nChamberCount)
					nChamberIndex = 0;
				}
			}

		void showChambers()
			{
			for (bool const bLoaded : m_arrChamber)
				std::cout << (bLoaded ? MARK_LOADED : MARK_EMPTY);

			std::cout << SEPARATOR;
			}

		int runTest()
			{
			showChambers();

			bool bLoaded;

			int nPlayerIndex = 0;

			for (int i = 0, n = m_arrChamber.size(); i < n; ++i)
				{
				bLoaded = m_arrChamber.at(i);

				std::cout << (bLoaded ? MARK_BANG : MARK_CLICK);

				if (bLoaded)
					return nPlayerIndex;

				if (++nPlayerIndex >= m_nPlayerCount)
					nPlayerIndex = 0;
				}

			return -1;
			}


		static void showResult()
			{
			int nResult, nMaxResult = -1;

			int const n = m_arrResult.size();

			for (int i = 0; i < n; ++i)
				{
				nResult = m_arrResult.at(i);

				if (nResult > nMaxResult)
					nMaxResult = nResult;

				std::cout << TXT_PLAYER << i << SEPARATOR << nResult << std::endl;
				}

			int nChampionIndex = -1;

			if (nMaxResult >= 0)
				{
				for (int i = 0; i < n; ++i)
					{
					nResult = m_arrResult.at(i);

					if (nResult < nMaxResult)
						continue;

					if (nResult > nMaxResult)
						{
						nChampionIndex = i;

						continue;
						}

					nChampionIndex = nChampionIndex < 0 ? i : -1;
					}
				}

			std::cout << std::endl;

			if (nChampionIndex >= 0)
				std::cout << TXT_CHAMPION << TXT_PLAYER << nChampionIndex;
			else
				std::cout << TXT_NO_CHAMPION;

			std::cout << std::endl;
			}


	};


std::vector <int> CTest::m_arrResult;

int CTest::m_nPlayerCount = 0;


int main()
	{
	CTest::run
		(
		DEFAULT_PLAYER_COUNT,
		DEFAULT_CHAMBER_COUNT,
		DEFAULT_ROUND_COUNT,
		DEFAULT_TEST_COUNT
		);

	return 0;
	}

 

Results.
 

Spoiler 

0	o....o	*	Player #0 wins!

1	.oo...	.*	Player #1 wins!

2	o....o	*	Player #0 wins!

3	...oo.	...*	Player #1 wins!

4	oo....	*	Player #0 wins!

5	o....o	*	Player #0 wins!

6	.oo...	.*	Player #1 wins!

7	o....o	*	Player #0 wins!

8	o....o	*	Player #0 wins!

9	....oo	....*	Player #0 wins!

10	o....o	*	Player #0 wins!

11	.oo...	.*	Player #1 wins!

12	..oo..	..*	Player #0 wins!

13	...oo.	...*	Player #1 wins!

14	o....o	*	Player #0 wins!

15	o....o	*	Player #0 wins!

16	...oo.	...*	Player #1 wins!

17	...oo.	...*	Player #1 wins!

18	o....o	*	Player #0 wins!

19	...oo.	...*	Player #1 wins!

20	.oo...	.*	Player #1 wins!

21	.oo...	.*	Player #1 wins!

22	.oo...	.*	Player #1 wins!

23	.oo...	.*	Player #1 wins!

24	oo....	*	Player #0 wins!

25	oo....	*	Player #0 wins!

26	....oo	....*	Player #0 wins!

27	..oo..	..*	Player #0 wins!

28	..oo..	..*	Player #0 wins!

29	o....o	*	Player #0 wins!

30	..oo..	..*	Player #0 wins!

31	....oo	....*	Player #0 wins!

32	oo....	*	Player #0 wins!

33	...oo.	...*	Player #1 wins!

34	...oo.	...*	Player #1 wins!

35	....oo	....*	Player #0 wins!

36	...oo.	...*	Player #1 wins!

37	...oo.	...*	Player #1 wins!

38	....oo	....*	Player #0 wins!

39	o....o	*	Player #0 wins!

40	o....o	*	Player #0 wins!

41	....oo	....*	Player #0 wins!

42	..oo..	..*	Player #0 wins!

43	...oo.	...*	Player #1 wins!

44	.oo...	.*	Player #1 wins!

45	o....o	*	Player #0 wins!

46	oo....	*	Player #0 wins!

47	..oo..	..*	Player #0 wins!

48	....oo	....*	Player #0 wins!

49	...oo.	...*	Player #1 wins!

50	.oo...	.*	Player #1 wins!

51	....oo	....*	Player #0 wins!

52	....oo	....*	Player #0 wins!

53	..oo..	..*	Player #0 wins!

54	...oo.	...*	Player #1 wins!

55	..oo..	..*	Player #0 wins!

56	oo....	*	Player #0 wins!

57	...oo.	...*	Player #1 wins!

58	.oo...	.*	Player #1 wins!

59	oo....	*	Player #0 wins!

60	....oo	....*	Player #0 wins!

61	...oo.	...*	Player #1 wins!

62	oo....	*	Player #0 wins!

63	...oo.	...*	Player #1 wins!

64	oo....	*	Player #0 wins!

65	o....o	*	Player #0 wins!

66	o....o	*	Player #0 wins!

67	oo....	*	Player #0 wins!

68	.oo...	.*	Player #1 wins!

69	....oo	....*	Player #0 wins!

70	..oo..	..*	Player #0 wins!

71	.oo...	.*	Player #1 wins!

72	..oo..	..*	Player #0 wins!

73	oo....	*	Player #0 wins!

74	..oo..	..*	Player #0 wins!

75	o....o	*	Player #0 wins!

76	..oo..	..*	Player #0 wins!

77	o....o	*	Player #0 wins!

78	o....o	*	Player #0 wins!

79	..oo..	..*	Player #0 wins!

80	..oo..	..*	Player #0 wins!

81	....oo	....*	Player #0 wins!

82	..oo..	..*	Player #0 wins!

83	...oo.	...*	Player #1 wins!

84	..oo..	..*	Player #0 wins!

85	.oo...	.*	Player #1 wins!

86	..oo..	..*	Player #0 wins!

87	o....o	*	Player #0 wins!

88	.oo...	.*	Player #1 wins!

89	.oo...	.*	Player #1 wins!

90	oo....	*	Player #0 wins!

91	.oo...	.*	Player #1 wins!

92	.oo...	.*	Player #1 wins!

93	oo....	*	Player #0 wins!

94	oo....	*	Player #0 wins!

95	...oo.	...*	Player #1 wins!

96	.oo...	.*	Player #1 wins!

97	..oo..	..*	Player #0 wins!

98	....oo	....*	Player #0 wins!

99	.oo...	.*	Player #1 wins!

	Player #0	64
	Player #1	36

The champion is 	Player #0

 

Spoiler 

0	o....o	*	Player #0 wins!

1	.oo...	.*	Player #1 wins!

2	....oo	....*	Player #0 wins!

3	oo....	*	Player #0 wins!

4	..oo..	..*	Player #0 wins!

5	....oo	....*	Player #0 wins!

6	...oo.	...*	Player #1 wins!

7	.oo...	.*	Player #1 wins!

8	....oo	....*	Player #0 wins!

9	.oo...	.*	Player #1 wins!

10	o....o	*	Player #0 wins!

11	...oo.	...*	Player #1 wins!

12	....oo	....*	Player #0 wins!

13	.oo...	.*	Player #1 wins!

14	...oo.	...*	Player #1 wins!

15	.oo...	.*	Player #1 wins!

16	...oo.	...*	Player #1 wins!

17	.oo...	.*	Player #1 wins!

18	o....o	*	Player #0 wins!

19	...oo.	...*	Player #1 wins!

20	....oo	....*	Player #0 wins!

21	oo....	*	Player #0 wins!

22	...oo.	...*	Player #1 wins!

23	..oo..	..*	Player #0 wins!

24	..oo..	..*	Player #0 wins!

25	o....o	*	Player #0 wins!

26	o....o	*	Player #0 wins!

27	o....o	*	Player #0 wins!

28	..oo..	..*	Player #0 wins!

29	...oo.	...*	Player #1 wins!

30	.oo...	.*	Player #1 wins!

31	..oo..	..*	Player #0 wins!

32	.oo...	.*	Player #1 wins!

33	....oo	....*	Player #0 wins!

34	...oo.	...*	Player #1 wins!

35	.oo...	.*	Player #1 wins!

36	...oo.	...*	Player #1 wins!

37	...oo.	...*	Player #1 wins!

38	...oo.	...*	Player #1 wins!

39	....oo	....*	Player #0 wins!

40	...oo.	...*	Player #1 wins!

41	o....o	*	Player #0 wins!

42	...oo.	...*	Player #1 wins!

43	...oo.	...*	Player #1 wins!

44	.oo...	.*	Player #1 wins!

45	..oo..	..*	Player #0 wins!

46	oo....	*	Player #0 wins!

47	o....o	*	Player #0 wins!

48	..oo..	..*	Player #0 wins!

49	o....o	*	Player #0 wins!

50	.oo...	.*	Player #1 wins!

51	.oo...	.*	Player #1 wins!

52	..oo..	..*	Player #0 wins!

53	..oo..	..*	Player #0 wins!

54	oo....	*	Player #0 wins!

55	.oo...	.*	Player #1 wins!

56	..oo..	..*	Player #0 wins!

57	...oo.	...*	Player #1 wins!

58	oo....	*	Player #0 wins!

59	...oo.	...*	Player #1 wins!

60	..oo..	..*	Player #0 wins!

61	o....o	*	Player #0 wins!

62	oo....	*	Player #0 wins!

63	oo....	*	Player #0 wins!

64	....oo	....*	Player #0 wins!

65	...oo.	...*	Player #1 wins!

66	..oo..	..*	Player #0 wins!

67	..oo..	..*	Player #0 wins!

68	o....o	*	Player #0 wins!

69	.oo...	.*	Player #1 wins!

70	..oo..	..*	Player #0 wins!

71	o....o	*	Player #0 wins!

72	....oo	....*	Player #0 wins!

73	..oo..	..*	Player #0 wins!

74	..oo..	..*	Player #0 wins!

75	oo....	*	Player #0 wins!

76	.oo...	.*	Player #1 wins!

77	.oo...	.*	Player #1 wins!

78	.oo...	.*	Player #1 wins!

79	oo....	*	Player #0 wins!

80	.oo...	.*	Player #1 wins!

81	oo....	*	Player #0 wins!

82	...oo.	...*	Player #1 wins!

83	oo....	*	Player #0 wins!

84	.oo...	.*	Player #1 wins!

85	....oo	....*	Player #0 wins!

86	oo....	*	Player #0 wins!

87	.oo...	.*	Player #1 wins!

88	oo....	*	Player #0 wins!

89	oo....	*	Player #0 wins!

90	...oo.	...*	Player #1 wins!

91	....oo	....*	Player #0 wins!

92	....oo	....*	Player #0 wins!

93	....oo	....*	Player #0 wins!

94	...oo.	...*	Player #1 wins!

95	....oo	....*	Player #0 wins!

96	.oo...	.*	Player #1 wins!

97	....oo	....*	Player #0 wins!

98	.oo...	.*	Player #1 wins!

99	..oo..	..*	Player #0 wins!

	Player #0	58
	Player #1	42

The champion is 	Player #0

 

Spoiler 

0	oo....	*	Player #0 wins!

1	...oo.	...*	Player #1 wins!

2	oo....	*	Player #0 wins!

3	oo....	*	Player #0 wins!

4	oo....	*	Player #0 wins!

5	.oo...	.*	Player #1 wins!

6	.oo...	.*	Player #1 wins!

7	...oo.	...*	Player #1 wins!

8	.oo...	.*	Player #1 wins!

9	...oo.	...*	Player #1 wins!

10	.oo...	.*	Player #1 wins!

11	...oo.	...*	Player #1 wins!

12	.oo...	.*	Player #1 wins!

13	..oo..	..*	Player #0 wins!

14	o....o	*	Player #0 wins!

15	....oo	....*	Player #0 wins!

16	oo....	*	Player #0 wins!

17	oo....	*	Player #0 wins!

18	..oo..	..*	Player #0 wins!

19	...oo.	...*	Player #1 wins!

20	oo....	*	Player #0 wins!

21	.oo...	.*	Player #1 wins!

22	....oo	....*	Player #0 wins!

23	...oo.	...*	Player #1 wins!

24	...oo.	...*	Player #1 wins!

25	..oo..	..*	Player #0 wins!

26	oo....	*	Player #0 wins!

27	oo....	*	Player #0 wins!

28	oo....	*	Player #0 wins!

29	..oo..	..*	Player #0 wins!

30	....oo	....*	Player #0 wins!

31	..oo..	..*	Player #0 wins!

32	o....o	*	Player #0 wins!

33	o....o	*	Player #0 wins!

34	....oo	....*	Player #0 wins!

35	....oo	....*	Player #0 wins!

36	..oo..	..*	Player #0 wins!

37	...oo.	...*	Player #1 wins!

38	....oo	....*	Player #0 wins!

39	oo....	*	Player #0 wins!

40	.oo...	.*	Player #1 wins!

41	oo....	*	Player #0 wins!

42	....oo	....*	Player #0 wins!

43	oo....	*	Player #0 wins!

44	o....o	*	Player #0 wins!

45	....oo	....*	Player #0 wins!

46	o....o	*	Player #0 wins!

47	o....o	*	Player #0 wins!

48	....oo	....*	Player #0 wins!

49	...oo.	...*	Player #1 wins!

50	oo....	*	Player #0 wins!

51	....oo	....*	Player #0 wins!

52	....oo	....*	Player #0 wins!

53	..oo..	..*	Player #0 wins!

54	....oo	....*	Player #0 wins!

55	oo....	*	Player #0 wins!

56	..oo..	..*	Player #0 wins!

57	oo....	*	Player #0 wins!

58	....oo	....*	Player #0 wins!

59	o....o	*	Player #0 wins!

60	.oo...	.*	Player #1 wins!

61	..oo..	..*	Player #0 wins!

62	oo....	*	Player #0 wins!

63	.oo...	.*	Player #1 wins!

64	..oo..	..*	Player #0 wins!

65	.oo...	.*	Player #1 wins!

66	...oo.	...*	Player #1 wins!

67	oo....	*	Player #0 wins!

68	.oo...	.*	Player #1 wins!

69	...oo.	...*	Player #1 wins!

70	o....o	*	Player #0 wins!

71	.oo...	.*	Player #1 wins!

72	o....o	*	Player #0 wins!

73	...oo.	...*	Player #1 wins!

74	..oo..	..*	Player #0 wins!

75	...oo.	...*	Player #1 wins!

76	..oo..	..*	Player #0 wins!

77	o....o	*	Player #0 wins!

78	oo....	*	Player #0 wins!

79	o....o	*	Player #0 wins!

80	..oo..	..*	Player #0 wins!

81	o....o	*	Player #0 wins!

82	..oo..	..*	Player #0 wins!

83	..oo..	..*	Player #0 wins!

84	....oo	....*	Player #0 wins!

85	...oo.	...*	Player #1 wins!

86	..oo..	..*	Player #0 wins!

87	...oo.	...*	Player #1 wins!

88	.oo...	.*	Player #1 wins!

89	oo....	*	Player #0 wins!

90	.oo...	.*	Player #1 wins!

91	o....o	*	Player #0 wins!

92	o....o	*	Player #0 wins!

93	..oo..	..*	Player #0 wins!

94	....oo	....*	Player #0 wins!

95	.oo...	.*	Player #1 wins!

96	..oo..	..*	Player #0 wins!

97	....oo	....*	Player #0 wins!

98	.oo...	.*	Player #1 wins!

99	o....o	*	Player #0 wins!

	Player #0	69
	Player #1	31

The champion is 	Player #0

 

 

3:0

Game master wins.

Link to comment
Share on other sites
Gargamel

Gargamel

Posted
  • Author
Posted
7 minutes ago, kerbiloid said:

Only Monte-Carlo, only hardcore.

Very cool, overly complicated way to do it, but very cool.

Aside from, I believe, you have the win condition backwards.    First person to fire the gun loses. 

6 hours ago, Cunjo Carl said:

Is it better for you if the ordeal is done with a 5-shooter or a 6-shooter?

I think you fell into the trap of the question.  Not sure though. 

Link to comment
Share on other sites
kerbiloid

kerbiloid

Posted
Posted
Just now, Gargamel said:

Aside from, I believe, you have the win condition backwards.    First person to fire the gun loses. 

Hm... Yes, you are right.
I thought they are shooting each other or playing Russian roulette, so in this case the first = the last.

Link to comment
Share on other sites
K^2

K^2

Posted
Posted
1 hour ago, kerbiloid said:

 

  


char const
	MARK_EMPTY = '.',
	MARK_LOADED = 'o',

	MARK_CLICK = '.',
	MARK_BANG = '*',

	SEPARATOR = '\t';

Prefer: 

enum class Mark : char
{
	EMPTY = '.',
	LOADED = 'o',
 	CLICK = '.',
	BANG = '*',
	SEPARATOR = '\t'
};

// And purely for convenience
std::ostream& operator<<(std::ostream& stream, const Mark mark)
{
	return stream << static_cast<char>(mark);
}

Placing defaults in global scope is also not great. When you're forced to do something like this, consider at least putting them into anonymous namespace. That will at least prevent linker from trying to keep track of them. Using constexpr is another good way to reduce overhead of global constants.

1 hour ago, kerbiloid said:

  


int const nChamberCount = m_arrChamber.size();

 

Prefer: 

const size_t nChamberCount = m_arrChamber.size();

Using int will force a completely unnecessary type conversion. Some people would also argue for use of auto here, but I can see both sides. Specifying size_t is more informative.

In general, most places people use int, they should probably be using size_t. It will automatically conform to the size of register, and because of that, optimizes much, much better. If you have a simple counter loop, you almost always want to have size_t as your counter. Notable exceptions: You need signed value or that 32 bit footprint for cache-heavy applications.

1 hour ago, kerbiloid said:

  


m_arrChamber = std::vector <bool> (m_arrChamber.size(), true);

  

m_arrChamber.assign(m_arrChamber.size(), true);
1 hour ago, kerbiloid said:

  


int nChamberIndex = std::rand() % nChamberCount;
 
for (; nRoundCount > 0; --nRoundCount)
	{
		m_arrChamber[nChamberIndex] = true;
 
		if (++nChamberIndex >= nChamberCount)
			nChamberIndex = 0;
	}

 

Besides the fact that this should probably use <random> rather than std::rand, using branches in loops like this, when you have wraparound, is rarely a good idea. Predictions on these kinds of branches tend to be bad, and it's a lot cheaper to use a bit of extra algebra. 

for (size_t i = 0; i < nRoundCount; ++i)
{
	m_arrChamber[(nChamberIndex + i) % nChamberCount] = true;
}
1 hour ago, kerbiloid said:

  


for (int i = 0 ; i < nTestCount; ++i)
	{
		CTest objTest(nChamberCount);
		//...
	}

 

This is entirely unnecessary. Each constructor of CTest implicitly constructs a std::vector, followed by explicit resizing, and destroys all of that in the destructor. So you end up with nTestCount malloc/free pairs, where one would fully suffice. The array can be trivially reused with a call to std::vector::assign for a fraction of a cost of a malloc.

There's also zero reason not to use for-each-style loop in runTest(), like you did in showChambers(). They have an identical structure with respect to their use of the bLoaded value.

Link to comment
Share on other sites
kerbiloid

kerbiloid

Posted
Posted (edited)
Spoiler
1 hour ago, K^2 said:

Prefer: 



enum class Mark : char
{
	EMPTY = '.',
	LOADED = 'o',
 	CLICK = '.',
	BANG = '*',
	SEPARATOR = '\t'
};

A matter of taste.
I find disgusting using enums like consts (because there is no enumeration here, and because in real project I would read them from settings storing in a map).
Though I'm aware about such style.

1 hour ago, K^2 said:

// And purely for convenience std::ostream& operator<<(std::ostream& stream, const Mark mark) { return stream << static_cast<char>(mark); }

Unnecessary complication.
I don't need to implement a separate type, while I would store these values in a map in  real project.

1 hour ago, K^2 said:

Placing defaults in global scope is also not great.

So, don't place them in a multi-module project.
Here is a single-file Hello World, without headers or so. We should not complicate it unduly. Though you may if you wish.

1 hour ago, K^2 said:

When you're forced to do something like this, consider at least putting them into anonymous namespace.

Anonymous namespaces are the way to chaos. I always name them.

1 hour ago, K^2 said:

Using constexpr is another good way to reduce overhead of global constants.

Don't forget to do this writing a hundred-files emulator of revolver shooting.

1 hour ago, K^2 said:

Using int will force a completely unnecessary type conversion.

This type conversion happens once on compilation.
I don't argue that size_t is more common, but I prefer to avoid excessive macros when possible.
All three compilers and frameworks which I've used, treat this alike, and I don't need to guess about their difference.

Though, I don't argue against size_t itself. In my experience I prefer clear types.

(You don't need to tell me about different containers with different possible types of size_t or particular features of Watcom-C or so).

1 hour ago, K^2 said:

Besides the fact that this should probably use <random> 

Besides the fact that it should definitely use a normal sane library implementation of randoms (like Alglib or so) if it were a serious project.

1 hour ago, K^2 said:

using branches in loops like this, when you have wraparound, is rarely a good idea.

This is exactly that case when it's a good idea.

1 hour ago, K^2 said:

This is entirely unnecessary. Each constructor of CTest implicitly constructs a std::vector, followed by explicit resizing, and destroys all of that in the destructor. So you end up with nTestCount malloc/free pairs, where one would fully suffice. The array can be trivially reused with a call to std::vector::assign for a fraction of a cost of a malloc.

Every time you use a local string in a loop, one kitten dies somewhere. Functors and lambdas just kill'em with fire.

With 10 mln tests it works just fine, about 20 s (with commented output).
Let me don't check at 1 bln, as unlike you I don't want to wait maybe an hour when it finishes.

1 hour ago, K^2 said:

There's also zero reason not to use for-each-style loop in runTest(), like you did in showChambers().

There was exactly one reason to do this because originally "i" was used there, and then left it as is.
But undoubtedly your heroic efforts put on checking someone's half-hour breakfast helloworld do you credit.

 

Edited by kerbiloid
Link to comment
Share on other sites
Superfluous J

Superfluous J

Posted
Posted
2 hours ago, K^2 said:

Placing defaults in global scope is also not great...

Using int will force a completely unnecessary type conversion...

...most places people use int, they should probably be using size_t.

...this should probably use <random> rather than std::rand...

The array can be trivially reused with a call to std::vector::assign for a fraction of a cost of a malloc.

There's also zero reason not to use for-each-style loop...

This is why I don't like to open source my code.

Link to comment
Share on other sites
K^2

K^2

Posted
Posted
42 minutes ago, kerbiloid said:

This type conversion happens once on compilation.

Nonsense. std::vector::size does a trivial return on a size_t member holding occupancy. Compiled to an x64 target, that's a 64 bit field. And since it's a template class, compiler has full access to the internals in every translation unit. Writing const size_t size = m_vector.size() simply creates an alias if there are no side effects. (e.g. resizing). That means the same register will be used whether it's your code using this alias variable, or internal code of the std::vector class. When you write const int size = m_vector.size(), compiler is still probably going to keep it in the register, but now it is forced to use distinct registers for your int value and internal size_t value, even if there are no side effects that would warrant it. And that dramatically reduces ability of the optimizer to make your code better. There are only so many registers to go around, and at some point, it will mean that memory is being accessed when it doesn't need to be. On a critical path, that's a 10x loss in performance, because you thought the type conversion is taken care of by compiler.

Coding styles exist for a reason. Some of it is purely readability, like "const int" vs "int const". But a lot of it is performance-driven. And because not all of us dive into specs and compiler design deep enough to know exactly how each case is going to be handled, maintaining good style must be adhered to as matter of habit. If your excuse for writing sloppy code is that it's not critical for it to be clean or efficient, then you'll write crap code in places where it does need to be clean and efficient.

42 minutes ago, kerbiloid said:

Every time you use a local string in a loop, one kitten dies somewhere.

Small strings are allocated on the stack. This is implementation-specific, but on most compilers you can expect at least 15 characters for free. So declaring them in a loop or creating a bunch of temps is perfectly fine. Instantiating a class in a loop because you didn't think to use vector::assign isn't. Not only is it cleaner, idiomatic code, it would be literally easier to write.

Link to comment
Share on other sites
kerbiloid

kerbiloid

Posted
Posted (edited)
Spoiler
17 hours ago, K^2 said:

Nonsense

happens when you have to convert your nice and pure size_t into an int used by something another which clearly uses signed int.
So, either you convert it in the loop defiinition, or in situ. Both cases are bad.
So, you would address your complains to frameworks developers. I just follow the path appeared to be less painful in my practice.

17 hours ago, K^2 said:

Coding styles exist for a reason.

Exactly! Don't forget to recall this before criticising someone's coding style.

17 hours ago, K^2 said:

Some of it is purely readability, like "const int" vs "int const".

Exactly this is not purely. Almost, but not absolutely.
Originally I was using "const type", until some guru (not you) had demonstrated cases when this leads to ambiguity.
But mostly they are equal, yes.

17 hours ago, K^2 said:

But a lot of it is performance-driven. 

And in most cases your style means nothing in comparison with some, say, ADO call.
Or when you use a recommended stream instead of old-style printf and realize that it works much slower.

17 hours ago, K^2 said:

And because not all of us dive into specs and compiler design deep enough to know exactly how each case is going to be handled, maintaining good style must be adhered to as matter of habit.

And sometimes this includes ignoring of purists' fantasies having a little common with real practice.

17 hours ago, K^2 said:

Small strings are allocated on the stack. This is implementation-specific, but on most compilers you can expect at least 15 characters for free. So declaring them in a loop or creating a bunch of temps is perfectly fine. Instantiating a class in a loop because you didn't think to use vector::assign isn't. Not only is it cleaner, idiomatic code, it would be literally easier to write.

Indeed. I should spend two hours more optimizing a helloworld.

IRL a programmer should find a balance between efforts and overoptimization.

P.S.

Spoiler

@K^2

Mwahaha. "size_t-schmize_t", blah-blah-blah

Here is the definition of std::vector.size() in my IDE: 


    inline int size() const { return d->size; }

So, int which I use is by definition the native type for this loop.
Code purists are a kind of grammar pedants.

 

Edited by kerbiloid
Link to comment
Share on other sites
Cunjo Carl

Cunjo Carl

Posted
Posted (edited)
On 7/22/2018 at 10:23 PM, Gargamel said:

I think you fell into the trap of the question.  Not sure though. 

Hmm... Well, mind checking my analysis? It feels right, so if my result is wrong, it's probably because my understanding of the problem statement is wrong. Maybe you can spot where?
 

Spoiler

 

Now since we can't make circles out of text, imagine we have the chambers laid out in a row, starting from the first chamber to be fired and proceeding so that they'll be fired (or dry fired) in the order they're written. (For mental images, on a S&W, this would be starting on the top-right chamber and proceeding clockwise). Laid out, it might look like this

X O O O O X  In which case player 2 will win, or it may look like this
O O O X X O  In which case player 1 will win.

Key:
X Chamber has live round in it
O Chamber is empty

Let's write out who will win for each starting position. Chambers (again) fired from left to right.

O O O O X X   6 chamber
2 1 2 1 2 2

O O O X X     5 chamber
1 2 1 2 2

Now we notice the pattern, two positions will always win for player 2, and the remaining will win in an alternating pattern starting with player 1. So, we can write out the formula and simplify.

 O O O O O O O O X X
[ <- 2 1 2 1 2 1]2 2   (The pattern)

numPositionsPlayerTwoWinsFrom = numBullets+floor((numChambers-numBullets)/2)
Plugging in 2 bullets, and simplifying:
numPositionsPlayerTwoWinsFrom = 1+floor(numChambers/2)

Finally, converting this into a win chance by normalizing (dividing by the total number of starting positions)...
playerTwoWinChance = 1+floor(numChambers/2) / numChambers

5-shot = 3/5 = 60%
6-shot = 4/6 = 67%
7-shot = 4/7 = 57%
8-shot = 5/8 = 63%
9-shot = 5/9 = 56% (surprisingly a real thing)
...
n-shot = 1/2 = 50% (isn't a real thing, but should be)

Now of course the real winners will be the people who figure out you can, without firing, repeatedly cycle most double-action revolvers onto the next round by pulling the trigger 3/4 the way and slowly releasing! Just always pick the same chamber your opponent did last time, and you're guaranteed a win! (Said to be a silly, don't really do this plz,thx.)

 

 

Edited by Cunjo Carl
cleanup
Link to comment
Share on other sites
Gargamel

Gargamel

Posted
  • Author
Posted

There's a much simpler way to go about it.
 

Spoiler

 

Player one is given a random cylinder, so it's a 2/6 chance he will fire a bullet.   So 1/3. 

Now, we need to look at the layout of the gun.

XX0000

Since we know that the second player will only get a turn if the first player does not fire, that eliminates the possibility that the cylinder is currently on chamber 2.

So now we have 4 empty chambers, and 1 full chamber left as possibilities.

So player two has a 1/5 chance of firing a bullet. 


 

@Cunjo Carl Where I think you fell into the trap, and I say I think, because I don't really follow your explanation, is that if you do the the math without considering the cylinder and bullet positions, you still get 1/3 for the first player, but if you eliminate one empty chamber, then the math becomes 2/5. 

Link to comment
Share on other sites
Cunjo Carl

Cunjo Carl

Posted
Posted (edited)

Oh, cool! There's a difference between our results so it looks like we'll get to have the question turned around on its asker :D . Nothing to do but keep going back and forth to see who hits their target first, eh?

Yeah, whether you attack the problem constructively or deductively I guess is a matter of taste. I went constructive because I wanted the general solution, and as always, it took 10 times longer to write out than it did to scratch on paper! I agree, it looks more complicated written out. Either works of course, but I think there's a little wrinkle missing from yours...
 

Spoiler

 

That being that the position isn't randomized each time, instead we're firing the chambers in sequential order. If player one didn't hit a live round on her first try, then she must have started over one of the four empties. Only one of these 4 empties has a live round following it (because the live rounds are adjacent), so player two will actually only have a 1 in 4 chance of hitting a live round on her first try! Looking at the whole thing:

Round    Player      LossChance   LossChance(distributed)
  1        1         2/6 = 1/3     2/6  =  2/6
  2        2            1/4        2/12 =  1/6   = (1 - 1/3)*(1/4)
  3        1            1/3        6/36 =  1/6   = (1 - 1/3)*(1 - 1/4)*(1/3)
  4        2            1/2       12/72 =  1/6   = (1 - 1/3)*(1 - 1/4)*(1 - 1/3)*(1/2)
  5        1             1        12/72 =  1/6   = (1 - 1/3)*(1 - 1/4)*(1 - 1/3)*(1 - 1/2)*1

Here "LossChance" is the chance of this player losing given we're already on this round. LossChance(distributed) is the chance of losing on this particular round from the start of the game. Summing up the player 1 loss chances (player 2 win chances) we get 4/6 or a 66% chance!  There's an interesting symmetry that pops up... that 1/6 just seems to fall out of the math from this perspective.

Hopefully the idea is passing across, but if it's not let me know and I'll give it another go. Cheers!

 

 

Edited by Cunjo Carl
cleanup
Link to comment
Share on other sites
This thread is quite old. Please consider starting a new thread rather than reviving this one.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
 Share
Go to topic listing
×
×
  • Create New...