## Last Man Standing

### August 16, 2019

This is easy, but I had a lot of trouble keeping track mentally of which item in the circular list was the current item; it took more tries than I will ever admit to get it right:

(define (f xs k) (define (last-pair xs) (if (null? (cdr xs)) xs (last-pair (cdr xs)))) (define (cycle xs) (set-cdr! (last-pair xs) xs) xs) (let loop ((k (- k 1)) (xs (cycle xs))) (cond ((= (car xs) (cadr xs)) (car xs)) ((zero? k) (let ((k (cadr xs))) (set-cdr! xs (cddr xs)) (loop k xs))) (else (loop (- k 1) (cdr xs))))))

> (f '(6 2 3 1 4 7 5) 3) 3

This is similar to the Flavius Josephus exercise we did over ten years ago, except that the increment varies rather than remaining fixed throughout the program. You can run the program at https://ideone.com/ypJdx6.

I started down the same “circular path” as @programmingpraxis but then

realized it is easier to use plain lists and modulo. Here’s the result

in standard R7RS scheme plus a couple of SRFI helpers.

Here’s an array-based solution in Python.

It would be interesting to compare the performance of an array versus linked list solution. I suppose it would depend on various factors, including how large the numbers are in the list. The following video reports interesting results for a related analysis:

Output:

There was an off-by-one error in my preceding solution (on line 6).

Here’s the update.

Output:

from collections import deque

def last_standing(seq, k):

dq = deque(seq)

while len(dq) > 1:

dq.rotate(-k)

k = dq.popleft()

Simple Python solution using a deque:

Here’s a solution that uses a binary tree (as a heap array, so that the children of node i are nodes 2i and 2i+1) to store the set of undeleted elements of the original array. Each node contains the count of undeleted elements in the corresponding subtree so we can find the nth undeleted element, and add or delete an element in log n time.

For eg. 1000000 elements, the final element is calculated in 0.5 seconds, against 2 minutes or so for a simple array shuffling solution:

And here’s another idea – use a bitset to keep track of the deleted values. See: https://stackoverflow.com/questions/7669057/find-nth-set-bit-in-an-int for a discussion of ways of finding the index of the nth set bit in an integer – we can do it very efficiently on Haswell with the the pdep instruction, or in a loop as here (using code from sth on that Stack Overflow page).

Of course, this limits the size of the array we can handle, but we could combine with the previous solution and use a binary tree with bitsets at the leaves.

Output:

Rust version using an iterator:

Link to Rust Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=12278c57ce468bb904d47fcfaefc7bc9

Rust version in the spirit of Daniel’s Python version above: