A problem involving doubly-circular list

The problem is this one (ACM): http://acm.tju.edu.cn/toj/showp1007.html.

This is a relatively simple problem, but the data structure chosen makes all the difference when it comes to its efficiency. The authors picked the input very carefully: use the wrong data structure and your code will run fine for K’s less or equal to 10, but the challenge comes for the K’s in the {11, 12, 13} subset. My first implementation used an array, where upon “killing” one person, I’d just flag that particular position in the array as “used”, but the array cell would remain there for every single calculation, wasting precious time. The array implementation did as well as it could for K’s <= 10, here is the time it took to process each input from 1 to 10:

Array Implementation:
1 => 2 (latency = 0.00s)
2 => 7 (latency = 0.00s)
3 => 5 (latency = 0.00s)
4 => 30 (latency = 0.00s)
5 => 169 (latency = 0.00s)
6 => 441 (latency = 0.00s)
7 => 1872 (latency = 0.02s)
8 => 7632 (latency = 0.24s)
9 => 1740 (latency = 0.02s)
10 => 93313 (latency = 31.91s)

For K = 11, it breaks into the 1h execution time, which isn’t acceptable. A better implementation (perhaps not the best, but definitely better than the array as you shall see) is to use a doubly circular list (DCL). That way when you “kill” someone you just remove that node altogether from the list, hence further calculations and walks thru the list will not go to that node again, saving considerable time. Be careful with the implementation of the DCL – try to make it very efficient by keeping track of the last node in the list (as a private member since it is only used to build the list). The reason you need the list to be a DCL (instead of a singly circular list, or SCL) is two-fold:
a) To quickly remove one node from the list
b) To traverse the list both ways (forward or backwards) – this will become handy for a nice optimization when it comes to traversing the list: you always pick the shortest path (either M moves or {List.Length – M} moves) and go the corresponding direction (forward or backwards)
The execution times for the DCL implementation is considerably faster, easily processing all K’s in the {1..13} set with an execution time of less than 2.5 seconds for the worst case (K = 13), and it can even process larger inputs up to K = 16 with execution time in the one-minute range. Beyond that (K > 16) it gets into the hours-range, intractable for this implementation.

DCL Implementation:
1 => 2 (latency = 0.00s)
2 => 7 (latency = 0.00s)
3 => 5 (latency = 0.00s)
4 => 30 (latency = 0.00s)
5 => 169 (latency = 0.00s)
6 => 441 (latency = 0.00s)
7 => 1872 (latency = 0.00s)
8 => 7632 (latency = 0.01s)
9 => 1740 (latency = 0.00s)
10 => 93313 (latency = 0.07s)
11 => 459901 (latency = 0.38s)
12 => 1358657 (latency = 1.21s)
13 => 2504881 (latency = 2.39s)
14 => 13482720 (latency = 13.76s)
15 => 25779600 (latency = 28.98s)
16 => 68468401 (latency = 79.67s)

Code for the two different implementations is down below:

Program.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Joseph
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length != 2)
            {
                Usage();
                return;
            }
            string fileName = args[0];
            string algo = args[1];
            InputHandler inputHandler = new InputHandler(fileName);
            int? k = inputHandler.ReadNextInput();
            while (k != null)
            {
                switch (algo.ToLower())
                {
                    case "array":
                        JosephArray josephArray = new JosephArray(k);
                        josephArray.Process();
                        break;
                    case "circularlist":
                        JosephDoublyCircularList josephDCL = new JosephDoublyCircularList(k);
                        josephDCL.Process();
                        break;
                    default:
                        Usage();
                        return;
                }
                k = inputHandler.ReadNextInput();
            }
        }
        static void Usage()
        {
            Console.WriteLine("Usage: Joseph.exe <input file> <array OR circularlist>");
            Console.WriteLine("For more info visit http://acm.tju.edu.cn/toj/showp1007.html");
        }
    }
}

InputHandler.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Joseph
{
    class InputHandler
    {
        private FileInfo fi = null;
        private StreamReader sr = null;
        private InputHandler() { }
        public InputHandler(string fileName)
        {
            this.fi = new FileInfo(fileName);
            this.sr = this.fi.OpenText();
        }
        public int? ReadNextInput()
        {
            if (this.sr != null)
            {
                int k = Int32.Parse(this.sr.ReadLine());
                if (k == 0)
                {
                    return null;
                }
                return k;
            }
            else
            {
                return null;
            }
        }
        ~InputHandler()
        {
            if (this.sr != null)
            {
                this.sr.Close();
            }
        }
    }
}

JosephArray.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Joseph
{
    class JosephArray
    {
        private int totalNumberOfGuys;
        private int k;
        private int[] guys;
        private int numberOfBadGuysKilled;
        private const int GOOD_GUY = 0;
        private const int BAD_GUY  = 1;
        private const int NOT_USED = 2;
        private JosephArray() { }
        private void Reset()
        {
            for (int i = 0; i < this.totalNumberOfGuys; i++)
            {
                this.guys[i] = (i < this.k) ? GOOD_GUY : BAD_GUY;
            }
            this.numberOfBadGuysKilled = 0;
        }
        private bool _Process(int m)
        {
            this.Reset();
            int currentIndex = (m - 1) % this.totalNumberOfGuys;
            for(; ; )
            {
                if (this.guys[currentIndex] == GOOD_GUY)
                {
                    break;
                }
                this.guys[currentIndex] = NOT_USED;
                this.numberOfBadGuysKilled++;
                if (this.numberOfBadGuysKilled >= this.k)
                {
                    break;
                }
                int currentIndexIncrementedBy = 0;
                int i = 0;
                for (; ; )
                {
                    i++;
                    int tentativeIndex = (currentIndex + i) % this.totalNumberOfGuys;
                    if (this.guys[tentativeIndex] != NOT_USED)
                    {
                        currentIndexIncrementedBy++;
                    }
                    if (currentIndexIncrementedBy == m)
                    {
                        currentIndex = tentativeIndex;
                        break;
                    }
                }
            }
            return this.numberOfBadGuysKilled >= this.k;
        }
        public JosephArray(int? k)
        {
            if (k == null ||
                k <= 0)
            {
                throw new Exception("Invalid parameter k");
            }
            this.k = (int)k;
            this.totalNumberOfGuys = 2 * this.k;
            this.guys = new int[this.totalNumberOfGuys];
        }
        public void Process()
        {
            int m = 1;
            long ticksBefore = DateTime.Now.Ticks;
            while (!this._Process(m))
            {
                m++;
            }
            long ticksAfter = DateTime.Now.Ticks;
            TimeSpan timeSpan = new TimeSpan(ticksAfter - ticksBefore);
            double latency = timeSpan.TotalMilliseconds / 1000.0;
            Console.WriteLine("{0} => {1} (latency = {2}s)", this.k, m, latency.ToString("F"));
        }
    }
}

JosephDoublyCircularList.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace Joseph
{
    class JosephDoublyCircularList
    {
        private class Node
        {
            public int value;
            public Node next;
            public Node previous;
            private Node() { }
            public Node(int value)
            {
                this.value = value;
                this.next = null;
                this.previous = null;
            }
        }
        private class DCL
        {
            public Node head;
            private Node lastNode = null;
            public DCL()
            {
                this.head = null;
                this.lastNode = this.head;
            }
            public void Add(int value)
            {
                if (this.head == null)
                {
                    this.head = new Node(value);
                    this.lastNode = this.head;
                }
                else
                {
                    this.lastNode.next = new Node(value);
                    this.lastNode.next.previous = this.lastNode;
                    this.lastNode = this.lastNode.next;
                }
               
                //Close the list
                this.lastNode.next = this.head;
                this.head.previous = this.lastNode;
            }
        }
        private int totalNumberOfGuys;
        private int k;
        DCL guys;
        private int numberOfBadGuysKilled;
        private const int GOOD_GUY = 0;
        private const int BAD_GUY  = 1;
        private JosephDoublyCircularList() { }
        private void Reset()
        {
            this.numberOfBadGuysKilled = 0;
            this.totalNumberOfGuys = 2 * this.k;
            this.guys = new DCL();
            for (int i = 0; i < this.totalNumberOfGuys; i++)
            {
                this.guys.Add((i < this.k) ? GOOD_GUY : BAD_GUY);
            }
        }
        private bool _Process(int m)
        {
            this.Reset();
            Node currentNode = this.guys.head;
            int movesFwd = (m - 1) % this.totalNumberOfGuys;
            int movesBwd = this.totalNumberOfGuys - movesFwd;
            if (movesFwd < movesBwd)
            {
                for (int i = 0; i < movesFwd; i++)
                {
                    currentNode = currentNode.next;
                }
            }
            else
            {
                for (int i = 0; i < movesBwd; i++)
                {
                    currentNode = currentNode.previous;
                }
            }
            for (; ; )
            {
                if (currentNode.value == GOOD_GUY)
                {
                    break;
                }
                else
                {
                    this.numberOfBadGuysKilled++;
                    if (this.numberOfBadGuysKilled >= this.k)
                    {
                        break;
                    }
                    currentNode.previous.next = currentNode.next;
                    currentNode.next.previous = currentNode.previous;
                    this.totalNumberOfGuys--;
                    currentNode = currentNode.next;
                    movesFwd = (m - 1) % this.totalNumberOfGuys;
                    movesBwd = this.totalNumberOfGuys - movesFwd;
                    if (movesFwd < movesBwd)
                    {
                        for (int i = 0; i < movesFwd; i++)
                        {
                            currentNode = currentNode.next;
                        }
                    }
                    else
                    {
                        for (int i = 0; i < movesBwd; i++)
                        {
                            currentNode = currentNode.previous;
                        }
                    }
                }
            }
            return this.numberOfBadGuysKilled >= this.k;
        }
        public JosephDoublyCircularList(int? k)
        {
            if (k == null ||
                k <= 0)
            {
                throw new Exception("Invalid parameter k");
            }
            this.k = (int)k;
            this.totalNumberOfGuys = 2 * this.k;
            this.guys = null;
        }
        public void Process()
        {
            int m = 1;
            long ticksBefore = DateTime.Now.Ticks;
            while (!this._Process(m))
            {
                m++;
            }
            long ticksAfter = DateTime.Now.Ticks;
            TimeSpan timeSpan = new TimeSpan(ticksAfter - ticksBefore);
            double latency = timeSpan.TotalMilliseconds / 1000.0;
            Console.WriteLine("{0} => {1} (latency = {2}s)", this.k, m, latency.ToString("F"));
        }
    }
}