Riddler Express - Holiday Party (https://fivethirtyeight.com/features/can-you-find-a-matching-pair-of-socks/)

1_explanation.md

Riddler Express

https://fivethirtyeight.com/features/can-you-find-a-matching-pair-of-socks/

Methodology

I've implemented a greedy algorithm that simulates every voter in the office being able to vote for any combination of options A, B, or C. By adding voters until the percentages are reached, we can find the least number of voters possible.

2_holidayParty.py

import math

if __name__ == '__main__':
    a_target = 73
    b_target = 58
    c_target = 32

    a, b, c = 0, 0, 0
    a_percent, b_percent, c_percent = 0, 0, 0
    total = 0

    while a_percent != a_target or b_percent != b_target or c_percent != c_target:
        # Perform one vote, to the option that is furthest from the target
        a_diff = a_target - a_percent
        b_diff = b_target - b_percent
        c_diff = c_target - c_percent

        if a_diff > 0:
            # vote for a
            a += 1
        if b_diff > 0:
            # vote for b
            b += 1
        if c_diff > 0:
            # vote for c
            c += 1
        total += 1

        # Recalculate all percents
        a_percent = math.floor(a / total * 100)
        b_percent = math.floor(b / total * 100)
        c_percent = math.floor(c / total * 100)
        print(f'A: {a} votes -> {a_percent}%')
        print(f'B: {b} votes -> {b_percent}%')
        print(f'C: {c} votes -> {c_percent}%')
        print(total)
        print(f'{a_percent}, {b_percent}, {c_percent}')
        # time.sleep(5)

    print(f'The number of people in office: {total}')
    print(f'A: {a} votes - {a_percent}%')
    print(f'B: {b} votes - {b_percent}%')
    print(f'C: {c} votes - {c_percent}%')

3_output.txt

A: 1 votes -> 100%
B: 1 votes -> 100%
C: 1 votes -> 100%
1
100, 100, 100
A: 1 votes -> 50%
B: 1 votes -> 50%
C: 1 votes -> 50%
2
50, 50, 50
A: 2 votes -> 66%
B: 2 votes -> 66%
C: 1 votes -> 33%
3
66, 66, 33
A: 3 votes -> 75%
B: 2 votes -> 50%
C: 1 votes -> 25%
4
75, 50, 25
A: 3 votes -> 60%
B: 3 votes -> 60%
C: 2 votes -> 40%
5
60, 60, 40
A: 4 votes -> 66%
B: 3 votes -> 50%
C: 2 votes -> 33%
6
66, 50, 33
A: 5 votes -> 71%
B: 4 votes -> 57%
C: 2 votes -> 28%
7
71, 57, 28
A: 6 votes -> 75%
B: 5 votes -> 62%
C: 3 votes -> 37%
8
75, 62, 37
A: 6 votes -> 66%
B: 5 votes -> 55%
C: 3 votes -> 33%
9
66, 55, 33
A: 7 votes -> 70%
B: 6 votes -> 60%
C: 3 votes -> 30%
10
70, 60, 30
A: 8 votes -> 72%
B: 6 votes -> 54%
C: 4 votes -> 36%
11
72, 54, 36
A: 9 votes -> 75%
B: 7 votes -> 58%
C: 4 votes -> 33%
12
75, 58, 33
A: 9 votes -> 69%
B: 7 votes -> 53%
C: 4 votes -> 30%
13
69, 53, 30
A: 10 votes -> 71%
B: 8 votes -> 57%
C: 5 votes -> 35%
14
71, 57, 35
A: 11 votes -> 73%
B: 9 votes -> 60%
C: 5 votes -> 33%
15
73, 60, 33
A: 11 votes -> 68%
B: 9 votes -> 56%
C: 5 votes -> 31%
16
68, 56, 31
A: 12 votes -> 70%
B: 10 votes -> 58%
C: 6 votes -> 35%
17
70, 58, 35
A: 13 votes -> 72%
B: 10 votes -> 55%
C: 6 votes -> 33%
18
72, 55, 33
A: 14 votes -> 73%
B: 11 votes -> 57%
C: 6 votes -> 31%
19
73, 57, 31
A: 14 votes -> 70%
B: 12 votes -> 60%
C: 7 votes -> 35%
20
70, 60, 35
A: 15 votes -> 71%
B: 12 votes -> 57%
C: 7 votes -> 33%
21
71, 57, 33
A: 16 votes -> 72%
B: 13 votes -> 59%
C: 7 votes -> 31%
22
72, 59, 31
A: 17 votes -> 73%
B: 13 votes -> 56%
C: 8 votes -> 34%
23
73, 56, 34
A: 17 votes -> 70%
B: 14 votes -> 58%
C: 8 votes -> 33%
24
70, 58, 33
A: 18 votes -> 72%
B: 14 votes -> 56%
C: 8 votes -> 32%
25
72, 56, 32
A: 19 votes -> 73%
B: 15 votes -> 57%
C: 8 votes -> 30%
26
73, 57, 30
A: 19 votes -> 70%
B: 16 votes -> 59%
C: 9 votes -> 33%
27
70, 59, 33
A: 20 votes -> 71%
B: 16 votes -> 57%
C: 9 votes -> 32%
28
71, 57, 32
A: 21 votes -> 72%
B: 17 votes -> 58%
C: 9 votes -> 31%
29
72, 58, 31
A: 22 votes -> 73%
B: 17 votes -> 56%
C: 10 votes -> 33%
30
73, 56, 33
A: 22 votes -> 70%
B: 18 votes -> 58%
C: 10 votes -> 32%
31
70, 58, 32
A: 23 votes -> 71%
B: 18 votes -> 56%
C: 10 votes -> 31%
32
71, 56, 31
A: 24 votes -> 72%
B: 19 votes -> 57%
C: 11 votes -> 33%
33
72, 57, 33
A: 25 votes -> 73%
B: 20 votes -> 58%
C: 11 votes -> 32%
34
73, 58, 32
The number of people in office: 34
A: 25 votes - 73%
B: 20 votes - 58%
C: 11 votes - 32%

4_explanation_extra_credit.md

Extra Credit

The following code counts down from 10000 until you find a number of coworkers that doesn't let you satisfy the percentages. We calculate the optimal number of votes by taking ceiling after calculating the target percentage, and multiplying by the number of coworkers. This value is the ideal number of votes (note it cannot be a non-whole number) cast for that holiday party option. Then, we divide by the total coworkers and take the floor to simulate writing down the percentage up to the decimal point. If this value is not equal to the target for each of the holiday options, then that number of coworkers does not contain a possible solution

Answer

By running the below code, we find that the largest number of coworkers where the percentages are not possible is 66.

Here's a list of all the impossible numbers of coworkers: 66, 54, 47, 44, 35, 33, 32, 27, 22, 21, 20, 18, 16, 14, 13, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

5_extra_credit_code.py

import math

import numpy as np

if __name__ == '__main__':
    coworkers = np.arange(100000, 0, -1)
    a_target = 73
    b_target = 58
    c_target = 32

    for t in coworkers:
        # Choose an a that will get you as close as possible to the target
        a = math.ceil(a_target / 100 * t)
        b = math.ceil(b_target / 100 * t)
        c = math.ceil(c_target / 100 * t)

        a_percent = math.floor(a / t * 100)
        b_percent = math.floor(b / t * 100)
        c_percent = math.floor(c / t * 100)

        if (a_percent != a_target and b_percent != b_target and c_percent != c_target):
            print(f'Found the largest number of coworkers where it is impossible: {t}')

            print(f'A = {a_percent}%')
            print(f'B = {b_percent}%')
            print(f'C = {c_percent}%')
            break

6_extra_credit_output.txt

Found the largest number of coworkers where it is impossible: 66
A = 74%
B = 59%
C = 33%