aoc_2016_19_part2.v

// We use a circular double-linked list, and two pointers: one to the current player,
// and another one to their target, the player across the circle.
//
// By using a cicular list, API is intuitive.
//
// By using a double-linked list, deletion is cheap.
//
// By maintaining both pointers in each turn, we avoid seeks.

const (
    input = 3004953
)

struct Player {
    n int
mut:
    prev &Player
    next &Player
}

// Build a circular double-linked list of players.
mut first_player := &Player{1, 0, 0}
mut player := first_player
for n := 2; n <= input; n++ {
    mut next_player := &Player{n, 0, 0}
    player.next = next_player
    next_player.prev = player
    player = next_player
}
player.next = first_player
first_player.prev = player

mut nplayers := input
mut current_player := first_player

// Seek target of player 1.
mut steps := nplayers/2
mut target := current_player
for _ in 0 .. steps {
    target = target.next
}

for nplayers > 1 {
    // Remove the target from the ring.
    target.prev.next = target.next
    target.next.prev = target.prev
    nplayers--

    // Next player.
    current_player = current_player.next

    // Next target.
    steps = nplayers/2
    target = if steps % 2 == 0 { target.next } else { target.next.next }
}

println(current_player)