Case Study: Guessing Birthdays in C++

Guessing birthdays is an interesting problem with a simple programming solution.

You can determine the day of the month when your friend was born by asking five questions. Each question asks whether the day is in one of the following five sets of numbers.

The birthday is the sum of the first numbers in the sets where the day appears. For example, if the birthday is 19, it appears in Set1, Set2, and Set5. The first numbers in these three sets are 1, 2, and 16. Their sum is 19.

Listing 4.4 gives a program that prompts the user to answer whether the day is in Set1 (lines 10-16), in Set2 (lines 22-28), in Set3 (lines 34-40), in Set4 (lines 46-52), and in Set5 (lines 58-64). If the number is in the set, the program adds the first number in the set to day (lines 19, 31, 43, 55, 67).

Listing 4.4 GuessBirthday.cpp

1 #include <iostream>

2 using namespace std;

3

4 int main()

5 {

6    int day = 0; // Day to be determined

7    char answer;

8

9    // Prompt the user for Set1

10    cout << “Is your birthday in Set1?” << endl;

11    cout << ” 1 3 5 7\n” <<

12    ” 9 11 13 15\n” <<

13    “17 19 21 23\n” <<

14    “25 27 29 31” << endl;

15    cout << “Enter N/n for No and Y/y for Yes: “;

16    cin >> answer;

17

18    if (answer == ‘Y’ || answer == ‘y’)

19    day += 1;

20

21    // Prompt the user for Set2

22    cout << “\nIs your birthday in Set2?” << endl;

23    cout << ” 2 3 6 7\n” <<

24    “10 11 14 15\n” <<

25    “18 19 22 23\n” <<

26    “26 27 30 31” << endl;

27    cout << “Enter N/n for No and Y/y for Yes: “;

28    cin >> answer;

29

30    if (answer == ‘Y’ || answer == ‘y’)

31    day += 2;

32

33    // Prompt the user for Set3

34    cout << “\nIs your birthday in Set3?” << endl;

35    cout << ” 4 5 6 7\n” <<

36    “12 13 14 15\n” <<

37    “20 21 22 23\n” <<

38    “28 29 30 31” << endl;

39    cout << “Enter N/n for No and Y/y for Yes: “;

40    cin >> answer;

41

42    if (answer == ‘Y’ || answer == ‘y’)

43    day += 4;

44

45    // Prompt the user for Set4

46    cout << “\nIs your birthday in Set4?” << endl;

47    cout << ” 8 9 10 11\n” <<

48    “12 13 14 15\n” <<

49    “24 25 26 27\n” <<

50    “28 29 30 31” << endl;

51    cout << “Enter N/n for No and Y/y for Yes: “;

52    cin >> answer;

53

54    if (answer == ‘Y’ || answer == ‘y’)

55    day += 8;

56

57    // Prompt the user for Set5

58    cout << “\nIs your birthday in Set5?” << endl;

59    cout << “16 17 18 19\n” <<

60    “20 21 22 23\n” <<

61    “24 25 26 27\n” <<

62    “28 29 30 31” << endl;

63    cout << “Enter N/n for No and Y/y for Yes: “;

64    cin >> answer;

65

66    if (answer == ‘Y’ || answer == ‘y’)

67    day += 16;

68

69    cout << “Your birthday is ” << day << endl;

70

71    return 0;

72 }

This game is easy to program. You may wonder how the game was created. The mathematics mathematics behind the game behind the game is actually quite simple. The numbers are not grouped together by accident— the way they are placed in the five sets is deliberate. The starting numbers in the five sets are 1, 2, 4, 8, and 16, which correspond to 1, 10, 100, 1000, and 10000 in binary (binary num­bers are introduced in Appendix D, Number Systems). A binary number for decimal integers between 1 and 31 has at most five digits, as shown in Figure 4.1a. Let it be b₅b₄b₃b₂b₁. Thus, b₅b₄b₃b₂b = b₅0000 + b₄000 + b₃00 + b₂0 + b₁, as shown in Figure 4.1b. If a day’s binary number has a digit 1 in b_k, the number should appear in Setk. For example, number 19 is binary 10011, so it appears in Setl, Set2, and Set5. It is binary 1 + 10 + 10000 = 10011 or decimal 1 + 2 + 16 = 19. Number 31 is binary 11111, so it appears in Setl, Set2, Set3, Set4, and Set5.

Figure 4.1 (a) A number between 1 and 31 can be represented using a 5-digit binary
number. (b) A 5-digit binary number can be obtained by adding binary numbers 1, 10, 100,
1000, or 10000.

Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.