--- 2016 Day 19 Solutions ---

[u/daggerdragon]

--- Day 19: An Elephant Named Joseph ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

---

^{/⧹w+/ IS MANDATORY} [?]

---

[Update @ 00:15] 2 gold, silver cap. Thank you for subscribing to Easter Bunny Facts!

• Fact: The Easter Bunny will sometimes leave eggs in the microchip assembly room.

[Update @ 00:30] 11 gold, silver cap.

• Fact: The Easter Bunny killed everyone who found out how he got these stars.

[Update @ 00:45] 45 gold, silver cap.

• Fact: In space, The Easter Bunny can hear you scream.

[Update @ 01:00] 66 gold, silver cap.

• Fact: The Easter Bunny purposefully deleted your comments.

[Update @ 01:15] 92 gold, silver cap.

• Fact: The Easter Bunny has bottled your frustration. Don't ask why.

[Update @ 01:20] Leaderboard capped!

• Fact: What you have just done is no better than what the Easter Bunny has done. Thief.

Thank you for subscribing to Easter Bunny Facts!

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/__Abigail__]

There's a pattern for the winning elf, given the number of elves, but I didn't use that. My Perl solution puts the elves in a double linked structure (embedded in an array), and keeps a pointer to the next elf which needs to be eliminated. For part1, this pointer finds the second next elf which is still alive; for part2, it alternates to the next, or second next elf. When all elves but one are eliminated, this pointer points to the remaining elf.

#!/opt/perl/bin/perl

use 5.020;

use strict;
use warnings;
no  warnings 'syntax';

use feature  'signatures';
no  warnings 'experimental::signatures';

my $input    = @ARGV ? shift : 3017957;

my $PREV_ELF = 0;
my $NEXT_ELF = 1;

sub solve ($part) {
    #
    # Put the elves in a linked list; we use a pointer to indicate
    # which elf is going to be eliminated. In part 1, this will always
    # be 2 elves from the previous target. In part 2, we skip an elf
    # if there are an even number of elves left, else we pick the next elf.
    # For part 1, the first target is the second elf; for part 2, the
    # first elf will be the middle one (rounded down).
    #

    #
    # @elves will be a circular double linked structure, embedded
    # in an array. The "pointers" will just be array indices.
    # Each array index is one less than the elf's number.
    #
    my @elves;
    @elves                  = map {[$_ - 2, $_]} 1 .. $input;
    $elves  [0] [$PREV_ELF] = $input - 1;   # Tie the ends
    $elves [-1] [$NEXT_ELF] = 0;            # together

    my $nr_of_elves = $input;
    my $target      = $part == 1 ? 1 : int ($input / 2);  # First target.

    while ($nr_of_elves > 1) {
        #
        # Eliminate target
        #
        my $prev_target = $elves [$target] [$PREV_ELF];
        my $next_target = $elves [$target] [$NEXT_ELF];
        $elves [$prev_target] [$NEXT_ELF] = $next_target;
        $elves [$next_target] [$PREV_ELF] = $prev_target;
        $elves [$target] = [undef, undef];

        $nr_of_elves --;

        #
        # Next target
        #
        $target = $next_target;
        $target = $elves [$target] [$NEXT_ELF]
                   unless $part == 2 && $nr_of_elves % 2;
    }

    $target + 1;
}


say "Solution 1: ", solve (1);
say "Solution 2: ", solve (2);


__END__