King Arthur's knights

The solution to this problem is a perfect example of a good time to use a Linked List. In its simplest form, a linked list is a collection of nodes, each containing a value and a "Link" (pointer) to the next node.

This structure is helpful to this problem because it can be used to make a circular Linked List, where the last node points back to the first (as this would simulate Arthur going past the last knight and "rolling over" to the first one).

For example, for C(2, 4), proceed as follows:

• Create a circular Linked List of the specified length but keep an exterior pointer to a dummy node pointing to the first one as a placeholder. Each node's value is the number of the knight with which it is associated.

Your structure should look like this:

current -----> [0] --> [1] --> [2] --> [3] --> [4] --> Loop back to [1]

• WIHLE there is more than one knight remaining (this can be checked by seeing if the current node's next next field points to itself), do the following:

• Move forward by the number of knights specified by $r$ then stop. Keep track of the last node you were at as you go.

For example, after the first iteration, your pointers should look like:

            last      current
[0] ------> [1] ------> [2] ------> [3] ------> [4] ------> Back to [1]

• Set the last node's next pointer to the current's next pointer.

Now the structure looks like:

           last
[0] ------> [1] ------> [3] ------> [4] ------> Back to [1]
            [2] ------>
          current

(Current points to [2] which points to [3].)

You have now effectively removed [2] since no other nodes point to it.

When you enter the next iteration, the count will terminate when you reach [4] and that node will be removed. The same will happen to [3] on the third iteration.

At that point the pointers look like this:

                                   last
                        [0] ------> [1] ------> Back to [1]
[2] ------> [4] ------> [3] ------>
                     current

Now the while loop terminates because current.next.next == current.next. It returns the value current.next (here, 1).

Finally, there is one special case to add to the beginning of the function - if $r = 1$ , return the number of knights, as the last one will always win (the pointer shuffling fails if the gap between knights is 1).

Finally, solving for our answer:

$C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3) \\ = 511 + 119 + 2 + 11 + 88 \\ = \fbox{731}$

I created a list that contained all knights. Then I did the following process $p-1$ times, in order to be left with the last knight:

• Take the first $r$ knights and move them to the back of the list. Because the $r$ th knight of the original list needed to be popped off, he is now in the last position of the list.
• Remove the last knight of the list.

Note that after each time this process is done, the first knight in the list is where King Arthur starts to count again. Here's my python code:

def c(p,r):
    knights = range(1,p+1) #create the list of knights

    for n in range(p-1):
        moved = knights[ 0 : 1 + ( (r-1) % len(knights) ) ] # copying
        del knights[ 0 : 1 + ( (r-1) % len(knights) ) ] # removing
        knights.extend(moved) # putting knights at the end
        knights.pop() # removing the last knight

    return knights[0]

c(999,11) + c(121,12) + c(2,1) + c(15,16) + c(99,3)
>>> 731

Note : I had to use the modulo operator ( % ) because $r$ can be larger than $p$ .

The answer is $731$ . I basically defined what $C(p,r)$ is.

I first made a set of $p$ knights referring each knight to a number in the range $(1,p+1)$ . Then I made a loop that keeps on redefining the set Knight. In the loop, it goes through the set and after every $r$ steps it defines Knight as a set that has all the elements of Knight (the previous set 'Knight') except it doesn't have the element that the loop currently was on. If the loop reaches the end of the set but yet, had more than $1$ element, then it would start over. [I don't know how to talk about codes without sounding weird. I just code away! Talking about it way tougher!]

Well, this is my code. It's in python 3.3.0:

def C(p,r):
    Knight=[x for x in range(1,p+1)] #Defining the set of Knights.
    N_K = str(Knight).count(",")+1 #N_K refers to the number of elements of the set "Knight".

    i=0
    c=1
    while N_K is not 1:
        a=Knight[i]
        if (c)%r==0:
            Knight=[Knight[x] for x in range(0,N_K) if not (x==(i))] 
            i=i-1 
        N_K = str(Knight).count(",")+1
        if i==N_K-1:
            i=-1

        i=i+1
        c=c+1

    return(Knight[0])
T=C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3)
print(T)

The MatLab entry is:

$C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3)$

where $C(p,r)$ is the function below.

$function [A]= C( p,r ) \\ A=1:p; \\ tbr=1; \\ while \quad length(A)>1 \\ \quad l=length(A); \\ \quad if \quad rem(tbr+r-1,l)==0 \\ \qquad tbr=l; \\ \qquad A(:,tbr)=[]; \\ \qquad tbr=1;\\ \quad else\\ \qquad tbr=rem(tbr+r-1,l);\\ \qquad A(:,tbr)=[];\\ \quad end\\ \quad end\\ end \\$

which returns 731 .

This is a perl code:

sub C{
my $p=shift;
my $r=shift;
my @k=(1..$p);
for (1..$p-1){
    for (1..$r-1){
        $t=shift @k;
        push @k,$t;
    }
    shift @k;
}
return $k[0];
}

sub Knight{
    $T=C(999,11)+C(121,12)+2+C(15,16)+C(99,3);
print "$T\n";
}

This is the Josephus problem. I wrote the following code in VBA to solve it: Function josephus(n As Integer, k As Integer) Dim r, i As Integer

r = 0
i = 2

While i <= n
    r = (r + k) Mod i
    i = i + 1
Wend

josephus = r + 1

End Function

I played around with some things I don't tend to use much in C# but which suited this problem - Tuples , Linked Lists , and recursion .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RoundTable
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Tuple<int, int>> test = new List<Tuple<int, int>> {
                new Tuple<int, int>(999, 11), new Tuple<int, int>(121, 12),
                new Tuple<int, int>(2, 1),new Tuple<int, int>(15, 16),new Tuple<int, int>(99, 3)
            };
            var sum = test.Sum(x => WhichKnightIsTheLeader(x.Item1, x.Item2));
            Console.WriteLine("The answer is {0}", sum);
            Console.ReadLine();
        }
        /// <summary>
        /// Given a number of knights at a round table (numberOfKnightsAtTable) where the first knight is #1, the second knight #2, etc. this function
        /// removes every nth knight (removeEveryNthKnight) from the round table until there is only one left.  
        /// </summary>
        /// <param name="numberOfKnightsAtTable"></param>
        /// <param name="removeEveryNthKnight"></param>
        /// <param name="currentKnight">Used internally during recursion - set to null on first call</param>
        /// <returns>The number of the remaining knight (the leader) after all others have been removed</returns>
        private static int WhichKnightIsTheLeader(int numberOfKnightsAtTable, int removeEveryNthKnight, LinkedListNode<int> currentKnight = null)
        {
            LinkedList<int> roundTable = null;
            if (currentKnight == null)
            {
                roundTable = new LinkedList<int>();
                currentKnight = new LinkedListNode<int>(1);
                roundTable.AddFirst(currentKnight);
                for (int i = 2; i < numberOfKnightsAtTable+1; i++)
                {
                    currentKnight = roundTable.AddAfter(currentKnight, i);
                }
                currentKnight = roundTable.First;
            }

            roundTable = currentKnight.List;
            //base case
            if (roundTable.Count == 1)
            {
                Console.WriteLine("{0},{1} = {2}", numberOfKnightsAtTable, removeEveryNthKnight, currentKnight.Value);
                return currentKnight.Value ;
            }
            else
            {
                for (int i = 1; i < removeEveryNthKnight; i++)
                {
                    currentKnight = currentKnight.NextOrFirst();
                }
                var nextKnight = currentKnight.NextOrFirst();
                roundTable.Remove(currentKnight);
                return WhichKnightIsTheLeader(numberOfKnightsAtTable, removeEveryNthKnight, nextKnight);
            }
        }
    }
    static class CircularLinkedList
    {
        public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
        {
            return current.Next ?? current.List.First;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def remains(n,m):
    n+=1
    array=[]
    for i in range(1,n):
        array.append(i)
    num=m-1    
    while len(array)>1:
        num=(num%len(array))
        array.remove(array[num])
        num+=(m-1)
    return array[0] 
print(remains(999,11)+remains(121,12)+remains(2,1)+remains(15,16)+remains(99,3))

Love this is very similar to what I used for this .

Josephus Problem Solution>> int josephus(int p, int r) { if (p == 1) return 1; else return (josephus(p- 1, r) + r-1) % p+ 1; }

function [ n ] = arthur( p,r ) %UNTITLED2 Summary of this function goes here % Detailed explanation goes here A=1:p;

count=p; l=((mod(r,p)==0)*p)+mod(r,p); while((length(A))>1)

B=[A(1:l-1) A((l+1):length(A))];
A=B;
clear 'B';
l1=((mod(l+r-1,length(A))==0)*length(A))+mod(l+r-1,length(A));

l=l1;

end n=A;

end

(Matlab code)

In AutoHotkey

msgbox % AK(999, 11) + AK(121, 12) + AK(2, 1) + AK(15, 16) + AK(99, 3)
return

AK(p, r){
    obj := {}
    loop % p
        obj.Insert(A_index)
    ps := 1 , ct := p
    while ( obj.maxIndex() - obj.minIndex() )
        ps := ps-1 + r , ps := !mod(ps,ct) ? ct : mod(ps,ct)
        , obj.remove(ps) , ct -= 1
    for k,v in obj
        return v
}

Similar to Josephus problem of devil eating out everyone. :-P

A non-recursive solution to the problem.

def kaleader(p, r):
    n = 0
    i = 1
    while i <= p:
        n = (n + r) % i
        i+= 1
    return n+1

print kaleader(999,11) + kaleader(121,12) + kaleader(2,1) + kaleader(15,16) + kaleader(99,3)

C++ Solution :

#include <iostream>

using namespace std;

int C(int m, int n)
{
    int r = 0, i = 2;
    while(i <= m)
    {
        r = (r + n)%i;
        i += 1;
    }
    return (r + 1);
}
int main()
{
    cout << C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3)  << endl;
    return 0;
}

Very simple brute force problem. Solution in python-

def C(p, r):
    knights = range(1, p+1)
    i = 0
    while len(knights) > 1:
        i = (i+r-1)%len(knights)
        del knights[i]
    return knights[0]

and then print the answer by-

print C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3)

Python code:

def nextnumber(x,deletedlist,p):
    while True:
        x += 1
        x = x % p
        if x not in deletedlist:
            return x

def C(p,r):
    dummy = 1
    x = 1
    deletedlist = []
    while True:
        if x % r == 0:
            deletedlist.append(dummy)
        if len(deletedlist) == p-1:
            for i in range(1,p+1):
                if i not in deletedlist:
                    return i
        dummy = nextnumber(dummy,deletedlist,p)
        x += 1

print(str(C(999,11) + C(121,12) + C(2,1) + C(15,16) + C(99,3)))

A simply python code does the trick:

def C(p,r):

    generated_list = []
    for i in range(1, p+1):
        generated_list.append(i)
    starting_index = -1 % len(generated_list)
    for removals in range(0,p-1):
        starting_index = (starting_index + r) % len(generated_list)
        generated_list.remove(generated_list[starting_index])
        starting_index = (starting_index -1) % len(generated_list)
    return generated_list[0]

T = C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3)

print T

The general idea is just to simulate the process. Check out this code written in Go: http://goo.gl/CMEuM

def c(p, r):
    a = [i for i in range(1,p+1)]
    pos = 0
    while p > 1:
        pos = (pos+r-1)%p
        del a[pos]
        p -= 1
    return a[0]

print c(999,11)+c(121,12)+c(2,1)+c(15,16)+c(99,3)

int ans = 0; for(int i=1;i<p;i++) ans = (ans+r)%(i+1); print ans+1;

def C(p,r):

n = [i for i in range(0,p+1)]
c = 0
i = 1
j = 0
while c != p-1:

    if i > p:
        i = 1

    if n[i] != -1:
        j += 1

    if j == r:
        n[i] = -1
        j = 0
        c += 1

    i += 1

for i in range(1,p+1):
    if n[i] != -1:
        return n[i]

print(C(999,11) + C(121,12) + C(2,1) + C(15,16) + C(99,3))

Done in Mathematica with a fuction CC [p, r] . Creates list roundtable of all the knights, and then changes the knights value to 0 if he is dismissed. Makes sure to skip a knight if he has already been dismissed, and to return to the beginning of roundtable if iterater exceeds p .

CC[p_Integer, r_Integer] := (
    roundtable = Table[i, {i, 1, p}];
    iterator = 0;
    Do[
        Do[
            iterator++;
            If[iterator > Length[roundtable],
                iterator = 1;
            ];
            While[roundtable[[iterator]] == 0,
                iterator++;
                If[iterator > Length[roundtable],
                    iterator = 1;
                ];
            ];
        , {j, 1, r}];
        roundtable = ReplacePart[roundtable, iterator -> 0];
    , {i, 1, p - 1}];
    Sum[roundtable[[i]], {i, 1, Length[roundtable]}]
)

CC[999, 11] + CC[121, 12] + CC[2, 1] + CC[15, 16] + CC[99, 3]

def C(p, r):
    knights = range(1, p+1)
    pos = -1
    for i in range(p):
        for j in range(r):
            pos += 1
            pos %= p
            while knights[pos] is None:
                pos += 1
                pos %= p
        knights[pos] = None
    return pos + 1

T = C(999,11) + C(121,12) + C(2,1) + C(15,16) + C(99,3)

def C(p,r):
    knights = range(1,p+1)
    ndx = 0
    while len(knights) > 1:
        ndx += r-1 #ndx points at last removed knight, -1 since he doesn't count towards r
        ndx %= len(knights)
        knights.pop(ndx)
    return knights[0]

print C(999,11) + C(121,12) + C(2,1) + C(15,16) + C(99,3)

def C(p, r):
    contenders = [i for i in range(1, p+1)]
    i = 1
    while len(contenders) != 1:
        if i % r != 0:
            survivor = contenders.pop(0)
            contenders.append(survivor)
        else:
            del contenders[0]
        i += 1
    return contenders[0]
print C(999,11) + C(121,12) + C(2,1) + C(15,16) + C(99,3)

$i$ keeps track of the elements' turns. A queue is made, where every element is either obliterated or kept (sending it to the back of the list). The function returns the integer that wins $C(p, r)$ according to rules.

Had some confusion about what "rth" meant but the example helped. Python:

def C(p, r):
    t = range(1, p + 1)
    c = (r - 1) % len(t)
    while True:
        del t[c]
        if len(t) == 1:
            return t[0]
        c = (c + r - 1) % len(t)

print C(999, 11) + C(121, 12) + C(2, 1) + C(15, 16) + C(99, 3)

Class "Knight" is a double linked list where each instance stores a value "Seat". The createtable(int p) function creates an array of Knight classes and then uses the array to go back and link the knights together into their double linked list.

    //In Java
    Knight[] Knights;

    class Knight{
      int Seat;
      Knight next, previous;
      Knight(int temp){
        Seat = temp;
      }
      void remove(){
        //skip this knight
        previous.next = next;
        next.previous = previous;
      }
    }

    void createtable(int p){
      //Place nights in list;  
      Knights = new Knight[p];
      for (int i = 0; i < p; i++){
        Knights[i] = new Knight(i + 1);
      }
      //Create linked list
      for (int i = 0; i < p-1; i++){
        Knight a = Knights[i];
        Knight b = Knights[i+1];
        a.next = b;   
        b.previous = a;
      }
      Knights[p-2].next = Knights[p-1];
      Knights[p-1].previous = Knights[p-2];
      { //Wrap around
        Knight a = Knights[p-1];
        Knight b = Knights[0];
        a.next = b;  
        b.previous = a;
      }
    }

    int C(int p, int r){
      createtable(p);
      int step = 0;
      Knight CurrentKnight = Knights[0];
      while (CurrentKnight.Seat != CurrentKnight.next.Seat){
        step++;
        println("Seat " + CurrentKnight.Seat + " on step " + step);    
        if (step > p*30){
          return step;
        }
        if (step%r == 0){     
          CurrentKnight.remove(); 
        }
        CurrentKnight = CurrentKnight.next;   
      }

        return(CurrentKnight.Seat);

    }

def C(p,r):
    a = range(1,p+1)
    b = list(a)
    i = 0
    while len(b) > 1:
        c = list(b)
        for x in c:
            i += 1
            if not i % r:
                if len(b) > 1:
                    b.pop(b.index(x))
    return b[0]
print(C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3))