Last Man Standing

August 16, 2019

Today’s exercise is a fun task for a lazy summer Friday:

Given a circular array X of positive integers and a starting index k of the array, delete the element at k and jump X[k] steps in the circular array. Repeat until only a single element remains. Find the last remaining element.

For example, with array 6 2 3 1 4 7 5 and k = 3, the last man standing is 3, computed as shown below, with the item to be deleted at each step marked with brackets and the list rotated at each step to bring the new head of the list to the front:

6 2 3 [1] 4 7 5
4 [7] 5 6 2 3
5 6 [2] 3 4
3 4 [5] 6
6 3 [4]
[6] 3
3

Your task is to write a program to find the last remaining element. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

9 Responses to “Last Man Standing”

  1. chaw said

    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.

    (import (scheme base)
            (scheme write)
            (only (srfi 1)
                  split-at)
            (only (srfi 8)
                  receive))
    
    (define (last-man-standing items start trace?)
      (let loop ((survivors items)
                 (len (length items))
                 (idx start))
        (when trace?
          (display survivors)
          (display idx)
          (newline))
        (if (<= len 1)
            survivors
            (receive (l r) (split-at survivors (modulo idx len))
              (loop (append (cdr r) l)
                    (- len 1)
                    (car r))))))
    
    (last-man-standing '(6 2 3 1 4 7 5) 3 #t)
    

    (6 2 3 1 4 7 5) 3
    (4 7 5 6 2 3) 1
    (5 6 2 3 4) 7
    (3 4 5 6) 2
    (6 3 4) 5
    (6 3) 4
    (3) 6
    (3)
    

  2. Daniel said

    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:

    def last(l, k):
        assert l, 'empty list'
        l = [x for x in l]  # copy list
        while len(l) > 1:
            k %= len(l)
            k += l.pop(k) - 1
        return l[0]
    
    l = [6, 2, 3, 1, 4, 7, 5]
    print(last(l, 3))
    

    Output:

    3
    
  3. Daniel said

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

    Here’s the update.

    def last(l, k):
        assert l, 'empty list'
        l = [x for x in l]  # copy list
        while len(l) > 1:
            k %= len(l)
            k += l.pop(k)
        return l[0]
    
    l = [6, 2, 3, 1, 4, 7, 5]
    print(last(l, 3))
    

    Output:

    3
    
  4. Mike said

    from collections import deque

    def last_standing(seq, k):
    dq = deque(seq)
    while len(dq) > 1:
    dq.rotate(-k)
    k = dq.popleft()

    return dq.pop()
    
  5. Mike said

    Simple Python solution using a deque:

    from collections import deque
    
    def last_standing(seq, k):
        dq = deque(seq)
    
        while len(dq) > 1:
            dq.rotate(-k)
            k = dq.popleft()
    
        return dq.pop()
    
  6. matthew said

    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:

    #include <vector>
    #include <iostream>
    #include <assert.h>
    
    int nextpowerof2(int n) {
      return 1 << (8*sizeof(n)-__builtin_clz(n-1));
    }
    
    class IndexableSet {
    public:
      IndexableSet(int n) : k(nextpowerof2(n)),counts(2*k) {}
      void set(int i) {   // Add element with index i
        i += k;
        assert(counts[i] == 0);
        counts[i]++;
        while (i > 1) {
          i /= 2;
          counts[i]++;
        }
      }
      void clear(int i) {   // Remove element with index i
        i += k;
        assert(counts[i] > 0);
        counts[i]--;
        while (i > 1) {
          i /= 2;
          counts[i]--;
        }
      }
      int nth(int n) {   // Return index of nth element
        assert(n < size());
        int i = 1;
        while(i < k) {
          i *= 2;
          if (n >= counts[i]) {
            n -= counts[i];
            i++;
          }
        }
        return i-k;
      }
      int size() { return counts[1]; }
    private:
      int k;
      std::vector<int> counts;
    };
    
    int main() {
      int N = 7;
      int a[N] = { 6,2,3,1,4,7,5 };
      IndexableSet iset(N);
      for (int i = 0; i < N; i++) iset.set(i);
      int k = 3;
      for (int i = 0; i < N-1; i++) {
        int j = iset.nth(k);
        iset.clear(j);
        std::cout << "Removing " << a[j] << " at " << j << "\n";
        k = (k + a[j]) % iset.size();
      }
      std::cout << a[iset.nth(0)] << "\n";
    }
    
  7. matthew said

    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.

    #include <iostream>
    #include <stdint.h>
    
    uint32_t nthset(uint32_t v, int n) {
      // Original function by sth
      for (int i = 0; i < n; i++) {
        v &= v-1; // remove the least significant bit
      }
      v &= ~(v-1); // extract the least significant bit
      return __builtin_popcount(v-1); // get its index
    }
    
    int main() {
      int N = 7;
      int a[N] = { 6,2,3,1,4,7,5 };
      uint32_t bset = (1<<7)-1;
      int k = 3;
      for (int i = 0; i < N-1; i++) {
        int index = nthset(bset,k);
        int n = a[index];
        std::cout << n << " 0x" << std::hex << bset << "\n";
        bset &= ~(1<<index);
        k = (k+n)%(N-i-1);
      }
      std::cout << a[nthset(bset,0)] << "\n";
    }
    

    Output:

    1 0x7f
    7 0x77
    2 0x57
    5 0x55
    4 0x15
    6 0x5
    3
    
  8. Bill Wood said

    Rust version using an iterator:

    /*  Author Bill Wood
        Elements are tracked using a vec called next_elem - a circular list.
        Removing an element doesn't require any allocations or copying.
    */
    struct Lastman<'a> {
        elements: &'a [usize],
        next_elem: Vec<usize>,
        index: usize,
        count: usize,
        prev: usize,
    }
    
    impl<'a> Iterator for Lastman<'a> {
        type Item = usize;
        fn next(&mut self) -> Option<Self::Item> {
            if self.count == 0 {
                return None
            }
            let steps = self.elements[self.index];
            self.index = self.next_elem[self.index];
            self.next_elem[self.prev] = self.index;
            for _i in 0..steps {
                self.prev = self.index;
                self.index = self.next_elem[self.index];
            }
            self.count -= 1;
            Some(steps)
        }
    }
    
    impl<'a> Lastman<'a> {
        fn new(index: usize, elements: &'a [usize]) -> Self {
            let size = elements.len();
            let mut l = Lastman { elements, count: size, index, prev: if index == 0 { size - 1 } else { index - 1 }, next_elem: Vec::with_capacity(size) };
            for i in 0..size - 1 {
                l.next_elem.push(i + 1);
            }
            l.next_elem.push(0);
            l
        }
    }
    
    fn main() {
        let x = vec!(6, 2, 3, 1, 4, 7, 5, );
        let mut x = Lastman::new(3, &x).peekable();
        while let Some(p) = x.next() {
            if x.peek().is_none() {
                println!("\nfinal value = {}", p, )
            } else {
                print!("{} ", p, );
            }
        }
    }
    

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

  9. Bill Wood said

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

    fn last(l: &[usize], mut k: usize) -> usize {
        let mut l = l.to_vec();
        while l.len() > 1 {
            k %= l.len();
            k += l.remove(k);
        }
        l[0]
    }
    
    fn main() {
        let x = vec!(6, 2, 3, 1, 4, 7, 5, );
        println!("{}", last(&x, 3));
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: