The Josephus puzzle – using arrays

While recursion is one way of solving the Josephus puzzle – arrays, or rather circular arrays, are another way. The program below, in C, uses arrays to solve the Josephus puzzle, visually depicting what happens.

Here is the first part of the program. The function objects_left() determines how people people are left in the circle. The procedure print_circle(), prints out the circle in linear form.

#include <stdio.h>
#define MAXPEOPLE 80

int objects_left(int j[], int m){
   int i,sum=0;
   for (i=0; i<m; i=i+1)
      if (j[i] == 1)
         sum = sum + 1;
      return sum;
}

void print_circle(int j[], int m){
   int i;
   for (i=0; i<m; i=i+1)
      printf("%d", j[i]);
      printf("\n");
}

The next part of the program does the actually processing, using the number of people, and step count provided by the user.

int main (void){
   int i,j,pos,MAXP,M;
   int josephus[MAXPEOPLE];

   printf("Number of people: ");
   scanf("%d", &MAXP);
   printf("Step count: ");
   scanf("%d", &M);
   for (i=0; i<MAXP; i=i+1)
      josephus[i] = 1;
   j = 0;
   while (objects_left(josephus,MAXP) > 1) {
      pos = 0;
      while (pos < M){
         if (j >= MAXP)
            j = 0;
         if (josephus[j] == 1)
            pos = pos + 1;
         j = j + 1;
      }
      josephus[j-1] = 0;
      printf("Deleting : %d\n",j);
      print_circle(josephus,MAXP);
   }
   for (i=0; i<MAXP; i=i+1)
      if (josephus[i] == 1)
         printf("The last object = %d\n", i+1);
   return 0;
}

Here is what happens:

Lines 8-9: Set all objects that exist in the array to 1. So for example if the number of people is 12, then the array would look like: 111111111111
Lines 12-24 (loop): Circle thru the array until the number of objects that remain = 1. pos represents the elimination position. The loop uses the function objects_left() as the loop condition.
Line 13: Set the step counter to 0.
Lines 15-16: Reset j if it’s value exceeds the number of people.
Lines 17-18: If the object (i.e. person) exists, increment the object counter.
Line 19: Increment position counter.
Line 21: Eliminate the object.
Lines 25-27: identify the last object.

Here is what the output looks like (the 0’s represent the deleted objects).

Number of people: 41
Step count: 3
Deleting : 3
11011111111111111111111111111111111111111
Deleting : 6
11011011111111111111111111111111111111111
Deleting : 9
11011011011111111111111111111111111111111
Deleting : 12
11011011011011111111111111111111111111111
Deleting : 15
11011011011011011111111111111111111111111
Deleting : 18
11011011011011011011111111111111111111111
Deleting : 21
11011011011011011011011111111111111111111
Deleting : 24
11011011011011011011011011111111111111111
Deleting : 27
11011011011011011011011011011111111111111
Deleting : 30
11011011011011011011011011011011111111111
Deleting : 33
11011011011011011011011011011011011111111
Deleting : 36
11011011011011011011011011011011011011111
Deleting : 39
11011011011011011011011011011011011011011
Deleting : 1
01011011011011011011011011011011011011011
Deleting : 5
01010011011011011011011011011011011011011
Deleting : 10
01010011001011011011011011011011011011011
Deleting : 14
01010011001010011011011011011011011011011
Deleting : 19
01010011001010011001011011011011011011011
Deleting : 23
01010011001010011001010011011011011011011
Deleting : 28
01010011001010011001010011001011011011011
Deleting : 32
01010011001010011001010011001010011011011
Deleting : 37
01010011001010011001010011001010011001011
Deleting : 41
01010011001010011001010011001010011001010
Deleting : 7
01010001001010011001010011001010011001010
Deleting : 13
01010001001000011001010011001010011001010
Deleting : 20
01010001001000011000010011001010011001010
Deleting : 26
01010001001000011000010010001010011001010
Deleting : 34
01010001001000011000010010001010001001010
Deleting : 40
01010001001000011000010010001010001001000
Deleting : 8
01010000001000011000010010001010001001000
Deleting : 17
01010000001000010000010010001010001001000
Deleting : 29
01010000001000010000010010000010001001000
Deleting : 38
01010000001000010000010010000010001000000
Deleting : 11
01010000000000010000010010000010001000000
Deleting : 25
01010000000000010000010000000010001000000
Deleting : 2
00010000000000010000010000000010001000000
Deleting : 22
00010000000000010000000000000010001000000
Deleting : 4
00000000000000010000000000000010001000000
Deleting : 35
00000000000000010000000000000010000000000
Deleting : 16
00000000000000000000000000000010000000000
The last object = 31

The Josephus puzzle – using recursion

A generic solution for the Josephus puzzle, which works for any value of n (number of people) and k (step size), can be formed in an iterative manner:

int josephusI(int n, int k) {
   int i , pos=1;
   for (i=1; i<=n; i=i+1)
      pos = (pos + k) % i; 
   return pos + 1 ;
}

This calculates r as the position of the last remaining person (starting at position 0) by cycling through each value of i.

The basic puzzle can be solved using dynamic programming. If we start the index from one, then the person at k positions from the first person is at position ((k − 1) mod n) + 1, where n is the total number of people. If f(n,k) denotes the position of the survivor, then after the k^th person is dispatched, a circle of n-1 people remains. The next shift then starts with the person whose number in the original problem was (k mod n) + 1. The position of the survivor in the remaining circle is then f(n-1,k), and shifting this to take into account the fact that the starting point is now (k mod n) + 1 yields the following recurrence:

f(1,k) = 0
f(n,k) = ((f(n−1,k) + k-1) mod n) + 1

This provides students with experience converting an iterative construct into a recurrence relation, which can then be implemented as a recursive function, with a starting position of 1 (shown here in Fortran).

recursive function josephusR(n,k) result(r)
   integer, intent(in) :: n, k
   integer :: r
   if (n == 1) then
      r = 1
   else
      r = mod((josephusR(n-1, k) + k-1), n) + 1
   end if
end function josephusR

The Josephus puzzle

The Josephus puzzle originates from Roman historian Flavius Josephus (37- 100 AD). It was mentioned in modern times by W.W. Rouse Ball in his book entitled ”Mathematical Recreations and Essays” [1], first published in 1892. In the section on antique problems he discusses the idea of decimation, a not uncommon punishment in the early Roman Army. Rouse Ball cites the work of Hegesippus, who authored a Latin adaptation of the Jewish War of Josephus, under the title De bello Judaico et excidio urbis Hierosolymitanae. During the Roman-Jewish conflict of AD67, the Romans captured the town of Jotapata. Josephus and forty companions escaped and took refuge in a cave. Josephus discovered that all but himself and another man were resolved to kill themselves to prevent being captured by the Romans. Fearing to show their opposition too openly, they declared that the operation should be carried out in an orderly way, and suggested that they should arrange themselves in a circle and that counting around the circle, every third person should be killed until until there was only one survivor, who would kill himself. It is alleged that he placed himself and the other man in the 31st and 16th place respectively, thus saving their lives. The Romans spared Josephus, and he later became a Roman citizen.

The puzzle involves finding the position of the last survivor, and can be expressed as follows: A group of n people are standing in a circle, numbered consecutively clockwise from 1 to n. Starting with the first person, every k^th person is removed, proceeding clockwise. The task is to determine the position of the remaining survivor, J_k(n). For example, if n=6, and k=2, then people are removed in the following order 2, 4, 6, 3, 1, and the last person remaining is number 5. The process of removing people is known as reduction using a step of size k[2]. The puzzle was first generalized by Euler in 1775 [3], and British scientist P.G. Tait introduced a general algorithmic rule for the Josephus puzzle in 1898 [4]. The puzzle was first cited in the context if algorithms by Knuth in 1968 [5] who explored a formula for k=2. A formula can be derived for the position of the last person, values of the sequence J_k(n), for a circle of n participants, in which every k^th participant is eliminated.

*A example of the Josephus puzzle with `n=6`, and `k=2`, with the final position being 5.*

The hailstone sequence and mutual recursion

Due to its mutually exclusive nature, Hailstone is also a good candidate to illustrate the notion of mutual recursion, whereby one of more functions call each other. A simplistic example is shown below which uses two additional functions to perform the tasks of calculating the hailstone sequence. The function hs_mutual() calls either hs_odd() or hs_even() depending on whether x is odd or even. The function called then calls hs_mutual() in turn, which again calls the appropriate mutual function, and so on. Below is the sequence in Fortran.

program collatz
   implicit none
   integer :: hs, r
   write(*,*) "Hailstone seed? "
   read(*,*) hs
   r = hs_mutual(hs)

contains

integer function hs_mutual(x)
   integer, intent(in) :: x
   write(*,"(i4,' ')",advance="no") x
   if (x /= 1) then
      if (mod(x,2) == 1) then
         hs_mutual = hs_odd(x)
      else
         hs_mutual = hs_even(x)
      end if
   end if
end function hs_mutual

integer function hs_even(x)
   integer, intent(in) :: x
   hs_even = hs_mutual(x/2)
end function hs_even

integer function hs_odd(x)
   integer, intent(in) :: x
   hs_odd = hs_mutual(3*x+1)
end function hs_odd

end program collatz

The hailstone sequence and recursion

The January 1984 issue of Scientific American contained an article on a sequence of numbers known as a hailstone sequence, also known as the Collatz Conjecture, the 3n+1 problem, the Syracuse problem, Hasse’s algorithm, and Kakutani’s problem. It is credited to German mathematician Lothar Collatz in 1937, however Collatz did not publish anything on the conjecture until 1986 [1], stating that he did not publish anything earlier because he could not solve the problem. The Collatz Conjecture states that “starting from any positive integer n, repeated iteration of [the Collatz function] eventually produces the value 1” [2]. This has been shown for every number just shy of 260 [3]. The series is formed in the following manner:

Pick a number.
If its odd, triple the number and add one.
If its even, divide the number by two.

Why is the sequence likened to a hailstone? It is so named because the values are subject to multiple ascents and descents, akin to hailstone formation in a cloud. Also, once the value hits a power of two, it moves towards termination in a rapid manner, as does a hailstone. As a function it can be defined in the following manner:

For example, starting with n = 11, the sequence takes longer to reach 1: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. In reality, it has no real world application, but it provides an interesting exercise in the structure of recursion.

Recursively, it is also easy to define, because the task of deriving a hailstone series is involved with processing a number a series of times until its value turns to 1. Here is a Fortran program to solve the hailstone sequence recursively:

program collatz
   implicit none
   integer :: h

   write(*,*) "Hailstone seed? "
   read(*,*) h
   call hailstone_r(h)
   write(*,*)

contains

recursive subroutine hailstone_r(n)
   integer, intent(in) :: n

   write(*,"(i4,' ')",advance="no") n
   if (n /= 1) then
      if (mod(n,2) == 1) then
         call hailstone_r(3*n+1)
      else
         call hailstone_r(n/2)
      end if
   end if

end subroutine hailstone_r

end program collatz

Note that the first if statement in the function hailstone_r() terminates the sequence. If this is not performed, the sequence 4, 2, 1 will be repeated infinitely (eventually causing the recursion to crash). Here is the sequence for n=57:

57  172   86   43  130   65  196   98   49  148   
74   37  112   56   28   14    7   22   11   34   
17   52   26   13   40   20   10    5   16    8    
4    2    1

Recursion – The monkey in the well puzzle

A somewhat nonsensical problem which can be solved by recursion. For some reason, a monkey is at the bottom of a 30-foot well. Every day the monkey climbs up three feet and slides back two feet. When does he reach the top? (The answer is the 28th day)

#include <stdio.h>
int monkey_climb(int well, int day){
   if (well > 27)
      return day;
   else
      return monkey_climb(well+3-2,day+1);
}

int main(void){
   int days;
   days = monkey_climb(0,0);
   printf("It takes the monkey %d days\n", days);
   return 0;
}

The function monkey_climb(), is initially called using parameter (0,0), i.e. 0 feet and 0 days. If the distance climbed up the well is greater than 27 feet, then the recursion ends, returning the number of days it took, otherwise the function calls itself with plus 3 and minus two feet (essentially a 1 foot increment every day), and one additional day.

Why I’m glad to be done teaching

I’ve just finished teaching the last university course I will ever teach. People often say “never say never”, but I know for certain that I won’t go back to teach “one off” courses once I’m retired. In fact I’ve never known anyone to do that. I mean, why would you? But after 25-odd years of teaching, I can honestly say that I’m worn out. Or maybe to put it a better way, I’m tired of teaching the way teaching is today – there is almost some level of mindlessness associated with modern teaching. You can try to do the best job you can, put 120% effort into creating a fantastic learning environment, but the reality is I doubt many students really care. A reasonable amount of students these days care about the end grade, and not really about learning anything. They write a couple of programs in a language, and add it to their CV as a skill. Hardly. Some people absorb nothing through the course of a semester, others have no clue how to follow the most basic instructions. Worse are students that think they should get 100% for an assessment when in reality their work is mediocre at best.

How have we gotten to this point? It’s not hard to decipher. Some people in university got there on hyper-inflated grades, a sad reality on how some high-schools operate. But the problem is much deeper than that, it starts at elementary schools where everyone gets good grades – there is an award for everyone. So there are some people who get to university and hit a wall because they can’t handle the fact that they might not do as well. There is no reward for handing in a crappy assignment. For some it’s because they can’t really write an essay or do basic math… and some always seem to think they are right. Some have few, if any, problem solving skills. They are also suppose to be the “technological” generation – hardly, many have no clue how to use Google (or even care to try) – not surprising because having the ability to use social media does not translate to being technological savvy. Using your finger to flip a screen on an iPhone is not really a transferable skill.

Now I’m not talking about *all* students, there are always intelligent, dedicated students. But there does seem to be students who don’t seem to want to work. I don’t quite understand how you achieve things in life if you don’t do some work. And it’s not all education’s fault either, as parents also have to take a portion of the blame. Overbearing helicopter (snowplow, etc) parents can hinder the success of students. A recent article found that students that grow up with helicopter parents have a tougher time transitioning from school to the real world. The real world is one where there aren’t 101 winners in a race, just one. That’s not to say that some university grades haven’t been inflated either, but that’s another story.

When I started in computer science as an undergrad it was because it was the only thing I was really good at. I found the rest of the subjects in my science degree somewhat boring, except perhaps geography. Computer science was interesting because you could analyze and decipher problems, and implement their solutions in programming languages. Languages were themselves new and evolving. Now students aren’t interested in learning in as much as just “getting the grade”. I’d like to say that maybe it was just CS, but I think it is endemic in higher education. I have taught large classes of 700 students, I have taught mid-sized classes, distance-education classes, and boutique classes of 20 students. I had high hopes for the 20-student course, which was an experiential seminar course on the history of food. But even there a few students couldn’t be bothered showing up, or didn’t interact. It was honestly a bit disheartening.

What I have learnt is that for every one student that want to learn, there are likely 2-3 that are impassive, not the least bit interested. But this is higher education today – in many fields. Is there a solution to this? Perhaps, but it is one that has to be initiated from the lower echelons of education. Then institutions of higher education would have to develop better ways of learning, implemented using smaller class sizes. Maybe more experiential, real-life courses, more co-op, and shorter, 3-year degrees. More experienced individuals needed to be engaged to teach these students, and we need to do away with the notion that you need a PhD to be able to teach (it’s a fallacy, anyone with experience, and passion for teaching can teach – you don’t need a series of graduate degrees, none of which include any notion of pedagogical training).

Maybe someday education will evolve into something better. But that is for others to figure out, I’m glad to be done my teaching career and move onto something else, perhaps a little more rewarding.

Software is really quite forgettable

As I have gotten older, I find I don’t code much anymore. I just don’t find it interesting anymore. Yes, there are snippets of code here and there, but they don’t amount to much. In fact I’ll be honest and say that I’ve never built a large piece of software, most academics haven’t. Academia just really doesn’t qualify as a good place to build large scale software, and I honestly never really felt the need. What would I develop? Nothing really made a lot of sense. Besides which, life is too short to worry about making something that isn’t that relevant.

That’s inherently the problem with software – it’s a little bit forgettable. You could spend a lifetime writing software, but how useful would it be? It only lasts as long as the device or operating system does, or as long as it is relevant (well unless it’s written in Cobol). It’s not like being an architect where you can actively see the fruits of your work, work that should be eternal, well probably not in the same context as what the Romans built, or the Egyptians. As humans we don’t really build anything monumental anymore… I mean large sure, but nothing as organic or functional as the pyramids (whatever part of the world you’re looking at pyramids), or let’s face it, just about anything built in the 19th century.

That’s not to say that software doesn’t do remarkable things, because some of it does. It can perform calculations far faster and more in depth than any human can. And people always call out bad software for its inability to do things… but nobody praises good software. It just exists, does its thing, and then disappears. Take digital cameras for example, nobody ever talks about the software that runs cameras – good, bad or indifferent, it just exists. It controls things like autonomous trains etc, and does a good job of processing things (without the need for AI). It has allowed us to share information across the world, via the internet (sometimes I don’t think this has worked out as well as it could have, e.g. things like disinformation).

The problem lies with the fact that most people don’t really care about software. They care that it works, but they don’t give much thought to how or why it works. Maybe I shouldn’t be surprised, many people buy houses and don’t give one iota of a thought to how the utilities like the sewer work function (and whether the pipes have actually been maintained). If you watch TV, do you care about the hardware and software inside it? I bet you don’t. That’s why I think it’s hard to spend a lifetime writing software – it’s just too forgettable.

The Eight Queens Puzzle (iv) – non-recursive

This program solves the Eight Queens problem using a non-recursive backtracking algorithm. It is adapted from Korsh’s book on algorithms and data structures [1], and re-written in Fortran. This algorithm treats the backtracking problem as a modification of a general tree preorder traversal algorithm.

Note that a 2D array could be used to represent the board, however if this approach were used, the row, column and diagonals specified by row and col would have to be traversed in their entirety. This could lead to inefficiencies in the algorithm. For diagCHK1 (row+col) = (row+1)+(col-1) = (row-1)+(col+1), i.e. all entries on this diagonal have the same row+col sum. For diagCHK2 (row-col) = (row-1)-(col-1) = (row+1)-(col+1), i.e. all entries on this diagonal have the same row-col difference.

program eightQueensNR
   use stackADT

   integer :: i, row, col, N
   logical :: rowCHK(1:8), diagCHK1(2:16), diagCHK2(-7:7), found
   type (stack) :: ST

   ! Specify the size of the board
   N = 8

   ! Initialize the column and row indices and the checking arrays
   row = 1
   col = 1
   rowCHK(1:N) = .true.
   diagCHK1(2:N*2) = .true.
   diagCHK2(-(N-1):(N-1)) = .true.

   found = .false.

   ! Initialize the stack
   call setStack(ST)

   do while (((col <= N) .and. (row <= N)) .or. (.not. stackEmpty(ST)))
       if ((col <= N) .and. (row <= N)) then
           if (feasible(row,col)) then
               call process(row,col,found,ST)
               call push(row,ST)
               rowCHK(row) = .false.
               diagCHK1(row+col) = .false.
               diagCHK2(row-col) = .false.
               col = col + 1
               row = 1
           else
               row = row + 1
           end if
       else
           call pop(ST,row)
           col = col - 1
           rowCHK(row) = .true.
           diagCHK1(row+col) = .true.
           diagCHK2(row-col) = .true.
           row = row + 1
       end if
   end do
   if (.not. found) then
       write(*,*) "No solutions"
   end if

contains
   ! See functions below
end program eightQueensNR

The function feasible() is used to determine whether the placement of a Queen is feasible. It determines whether placing a queen in the position specified by row and col will allow it to “take” one of the currently placed queens. If a queen may be taken it returns false, otherwise true.

rowCHK(i) = true if the current board configuration has no queen on the ith row, and false otherwise.
diagCHK1(i+j) = true if the current board configuration has no queen along the diagonal D1 with i+j sum, and false otherwise.
diagCHK2(i-j) = true if the current board configuration has no queen along the diagonal D2 with i-j difference, and false otherwise.

logical function feasible(row,col)
   integer :: row, col
   if (rowCHK(row) .and. (diagCHK1(row+col)) .and. diagCHK2(row-col)) then
      feasible = .true.
   else
      feasible = .false.
   end if
end function feasible

The subroutine process() is used to implement the printing of a solution by printing the sequence of values stored on the stack.

subroutine process(row, col, found, S)
   integer, intent(in) :: row, col
   logical, intent(inout) :: found
   type (stack), intent(in) :: S
   integer :: i
   if (col == N) then
      do i = N-1,1,-1
         write (*,"(I2)",advance="no") stackItem(S,i)
      end do
      write (*,"(I2)") row
      found = .true.
   end if
end subroutine process

Here is a sample of the first four lines of output:

 1 5 8 6 3 7 2 4
 1 6 8 3 7 4 2 5
 1 7 4 6 8 2 5 3
 1 7 5 8 2 4 6 3

I don’t want to sail with this ship of fools

There are many things I don’t understand about the modern computer science curriculum. We have had three decades to make good changes, and somehow modernize the way we teach computer science, way beyond what it is. It should be a much more experiential experience, but it isn’t. Computer science education has become stagnant.

A great example is the fact that many schools still offer courses on compiler construction. Look, I get it, in the 80’s people were still writing a lot of compilers, or at least academics thought that compiler construction was of interest, and maybe it was. But now? Sure, there are things you could learn from a compilers course… like how to write better, more efficient code. Programmers would have a better understanding of compiler optimizations etc. But the thing is that very few people wrote compilers in the 1980s, and fewer still write them now. Modern compilers are much more complex because the languages themselves have become complex, the so-called “everything but the kitchen sink” type of languages. In the 1980s it was easier to understand the relevance of efficiency when designing a compiler because the machines had limited resources. Besides which compilers has to be one of the most boring courses imaginable in CS to teach.

It isn’t only compilers, people still harp on about calculus, and courses on hardware etc. They just aren’t as relevant as they once were (unless you want to specialize). More relevant would be for students to have a better understanding of languages beyond the bounds of the C-based lineage. The world runs on many languages, yet many students become what is essentially monolingual. Some perhaps even a better understanding of C – how many people really understand pointers and memory management in C? In the age of AI, we should be emphasizing creativity, dynamic decision-making, and other uniquely human skills. We should be focusing on large-scale team projects building real software. We should be emphasizing problem-solving as the crux of a CS degree. But who does?

Sure throw in a few courses on AI, or cybersecurity because they’re the latest fads – you can never provide enough courses to really make a true impact on these topics, they are just appetizers so to speak. That doesn’t make degrees anywhere near innovative. Who has an innovative CS degree? I mean don’t go on the basis of those “best” lists, they aren’t that meaningful. They usually try to make the degrees seem important by offering a whole bunch of nonsensical options, which are just different combinations of courses. The basic structure of these degrees is all the same. Do innovative computer science programs exist? I haven’t been able to find any that don’t follow the same formula that every CS department does everywhere. True innovation would mean stepping away from the way traditional CS programs run, and that I’m afraid would be way too radical.

P.S. For those really interested in compilers, Niklaus Wirth included a simple compiler for a small rudimentary language in Algorithms + Data Structures = Programs.

The Craft of Coding

Musings on programming and education