Advent of Code F# — Day 19

ps. look out for all my oth­er solu­tions for Advent of Code chal­lenges here.

 

Day 19

See details of the chal­lenge here.

I ini­tial­ly approached today’s chal­lenge as a dynam­ic pro­gram­ming exer­cise, but it quick­ly tran­spired that there’s a much bet­ter way to do it once I realised that part 1 is in fact the Jose­phus Prob­lem and there’s a sim­ple solu­tion to it.

To under­stand the above, watch the YouTube video in the links sec­tion below.

 

Part 2

Real­iz­ing the fol­ly of their present-exchange rules, the Elves agree to instead
steal presents from the Elf direct­ly across the cir­cle. If two Elves are across
the cir­cle, the one on the left (from the per­spec­tive of the steal­er) is stolen
from. The oth­er rules remain unchanged: Elves with no presents are removed from
the cir­cle entire­ly, and the oth­er elves move in slight­ly to keep the cir­cle
even­ly spaced.

For exam­ple, with five Elves (again num­bered 1 to 5):

  • The Elves sit in a cir­cle; Elf 1 goes first:
  1
5   2
 4 3
  • Elves 3 and 4 are across the cir­cle; Elf 3’s present is stolen, being the one to
    the left. Elf 3 leaves the cir­cle, and the rest of the Elves move in:
  1           1
5   2  -->  5   2
 4 -          4
  • Elf 2 steals from the Elf direct­ly across the cir­cle, Elf 5:
  1         1 
-   2  -->     2
  4         4 
  • Next is Elf 4 who, choos­ing between Elves 1 and 2, steals from Elf 1:
 -          2  
    2  -->
 4          4
  • Final­ly, Elf 2 steals from Elf 4:
 2
    -->  2  
 -

So, with five Elves, the Elf that sits start­ing in posi­tion 2 gets all the
presents.

With the num­ber of Elves giv­en in your puz­zle input, which Elf now gets all the
presents?

I’m not aware of this vari­a­tion to the Jose­phus Prob­lem, but I’d wager that there would be some pat­tern to the results sim­i­lar to part 1, so I put togeth­er a dynam­ic pro­gram­ming solu­tion to get some out­puts. (ps. the solu­tion is not good enough for the input as it’ll take too long to return)

With the help of this I can see a pat­tern emerg­ing:

n : answer

1 : 1
2 : 2
3 : 3
4 : 1
5 : 2
6 : 3
7 : 5
8 : 7
9 : 9
10 : 1
11 : 2
12 : 3
13 : 4
14 : 5
15 : 6
16 : 7
17 : 8
18 : 9
19 : 11
20 : 13
21 : 15
22 : 17
23 : 19
24 : 21
25 : 23
26 : 25
27 : 27
28 : 1
29 : 2
30 : 3

  • where n is a pow­er of 3 then the answer is itself
  • else n can be expressed as m + l where m is a pow­er of 3
  • where l <= m (eg. n = 5 = 3 + 2 where m = 3 and l = 2) then the answer is just l
  • else the answer is m + (l — m) * 2 (eg. n = 7 = 3 + 4 where m = 3 and l = 4 and m + (l — m) * 2 = 5)

 

Links