Download the file : VCL Last Gunman Standing

The puzzle: n people stand in a circle. The first has a gun, shoots the next person still alive and passes the gun on. Who is the last one standing? It is the classic Josephus problem with every second person removed.

The download contains full source for two VCL projects that solve it by simulation, with the same form in each. Last_Standing_1 uses a TList<Int64>: each shot removes a person and the circle is rebuilt in a new list with the shooter moved to the end. Last_Standing_2 uses a TQueue<Int64>: the shooter is dequeued, the next person is dequeued and dropped, and the shooter goes to the back of the queue - three queue operations per shot instead of copying the whole list, so it is far faster for large n.

Enter a value of n from 2 to 100,000 and click Run for n. Tick Step By Step to see the circle after every shot (for n below 10). Only the standard VCL and System.Generics.Collections are used; the project files are from Delphi 11.

To check the answers: write n as 2^m + L, where 2^m is the largest power of two not above n. The survivor is 2L + 1. For n = 10, that is 8 + 2, so person 5 is left standing.