A Thinking Ape - Algorithm

Inspiration

passion for solving problems

What it does

solve the proposed circle of people problem (Challenge #15 of A Thinking Ape)

How I built it

To solve this problem i did the following 4 steps:

STEP 1 Generated some samples to understand the patterns

1 2

1 2 3

1 2 3 4

1 2 3 4 5

1 2 3 4 5 6

1 2 3 4 5 6 7

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10 11

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12 13

1 2 3 4 5 6 7 8 9 10 11 12 13 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

STEP 2. Analyzed and made some conclusions

Looking the samples, i could find 3 relevant patterns:

always the remaining person will be in an odd position;
as well the number of people increases, the remaining position increases too, until reset;
every time the number of people is a power of 2, the remaining person will be the first one again(reset).

STEP 3 i made the algorithm to find the remaining position/person

Some definitions:

RP - Remaining person

N - The number of people in the circle

NP2 - Nearest power of two

TRUNC() - Truncate a non-integer number (Ex: TRUNC(2.3333) == 2.0)

LOG2() - Calculate the logarithm in base 2 from a number (Ex.: LOG2(8) == 3)

The algorithm:

find the nearest power of 2 before the number of people in the circle. (Ex: if N is 9, the NP2 is 8 (2^3) )
Knowing that the remaining person for the NP2 is 1th, and for NP2 + 1 is 3th, and so on, just calculate the next odd number X times (X is the difference between N and NP2) to find the remaining person.

STEP 4 Constructed solution based on algorithm

To find the NP2 from N, we need to calculate the Log2 (logarithm in base 2) from N to find the exponent of NP2. But if N is not a power of 2, the result won’t be an integer number. In this case the integer part of the result will be exactly the exponent of the Nearest Power of 2 before N. So, to find NP2 it’s just needed to truncate the result of Log2(N) and apply the exponent to calculate 2^exp. So:

NP2 = 2^TRUNC(LOG2(N));

Now, knowing that to find a next odd number i need to add 2 (Ex: for 1, the next odd number is 1 + 2 = 3, for 3, 3 + 2 = 5…) I conclude that to find the last odd number in a sequence, i need to multiply the number of numbers in the sequence by 2 and add 1 (add 1 because every number multiplied by 2 is even, so the next is the odd one). So, finally i can conclude that:

RP = [(N - NP2) * 2] + 1; where NP2 = TRUNC(LOG2(N));

Putting all together i have the SOLUTION to the challenge:

RP = [(N - 2^TRUNC(LOG2(N))) * 2] + 1

To validate, fill free to run the following codes using python or c:

ata-cc.py (Ex.: python ata-cc.py 11)
ata-cc.c (Ex.: gcc -o ata-cc ata-cc.c && ./ata-cc 11)

Challenges I ran into

understand the logic pattern based in some samples

Accomplishments that I'm proud of

i took some time to solve this problem, but i'm proud because i really had to put it all in a paper, analyze the patterns and develop the formula to solve it.