Need help with pseudecode in C (circular doubly linked list)

[Bluga]

My pseudocode in C is the following ( i will implement this as "circular" doubly linked list ), i'm having trouble
figuring out the traverse part, how do i know the node i have alreadt traversed?and I also have
trouble in the bold part of the question. Thanks for any help :
=======================================================================
void get_node(name_of_list *a); /*initialize*/

void insert_end(name_of_list *a); /* insert at end */

void traverse_clockwise(); <==== how to implement this function???
{
find the Nth elemet, Mark it,
then start counting N times again
delete the last one
}

void traverse_counterclock()

/****************************************************/
main()
{
while (insert_data != 9999) /* insert the data */
{
insert_end ( ) / *insert data at end */
M = M + 1 /* Missionary count */
}
scanf (N) /* pick a number */
if ( M %2 == 0) /* even number, clockwise*/
{
for (i = 1 to M-1)
traverse_clockewise(N) /* traverse and delete */
}
else /* odd number, counterclock */
{
for ( i = 1 to M-1)
traverse_counterclock( N ) /* traverse and delete */
}
}

============================================================
The following is the problem, Thanks for any help:

A band of M missionaries is surrounded by a tribe of cannibals. The cannibals, being folks of small appetite,
only demand one of them for dinner each day. The missionaries find drawing straws distasteful for people
of their learning and sophistication. Instead, they form a circle and pick an integer N out of a hat. Then
beginning with the first missionary in circle (We will tell you who the first one is), they start to count from
one to N. The direction in which the count proceeds depends on the initial number of missionaries in the
circle. If there are an even number of them, the count goes clockwise; otherwise, it goes counter-clockwise.
Whenever N is reached, that missionary steps out of the circle and the count re-starts with the next
person (note that the direction of the count does not change until the dinner du jour is decided).
This process repeats until only one missionary is left in the ``circle'', who is the unfortunate one.

For example, say that you have four missionaries A, B, C and D forming a circle clockwise in that order:
On the first day, they pick 3. There are four of them so the count goes clockwise for the day. C is the first
person out of the circle, B is the second and D is the third; A is consumed. On the second day, the new
circle is C, B, D, and the count goes counter-clockwise. They pick 6. B is the first one out and D the
second; C is consumed. On the third day, the new circle is B,D. They pick 1. B is the first one out and
D is eaten. On the last day, B is consumed. So the order in which they are consumed is A,C,D,B.

 

[manly]

Traversal goes something like this:

while (missionary is not the victim) {

for (i from 1 to N) {

go to next missionary

}

Free the Nth missionary

}


I'm showing the pseudo-code at a very high level for two reasons. First to illustrate the intent of the code, and secondly to encourage you to break your code into many little functions.

I know that from my personal habit, I do a horrible job of commenting source code, and breaking functions up. If you write high-level pseudo-code, that pseudo-code really becomes a strong framework for readable code.


Discussion:
You know the current missionary is the victim when he's the last one standing (i.e. the only node in the circular list).

The other two functions are simple as well. Going to the next missionary is just following the correct node pointer to the next node in the list. Freeing the Nth missionary is just removing the current node from the list.

I'll assume you have a good algorithms reference discussing exactly how to implement circular linked lists.

By breaking the code into small functional units, you can easily change your choice of data structure without changing everything.

Now to answer your question about how do you know the node you've already traversed. There are two ways to look at this.

The first way is that the linked list is a temporary data structure. When you get to the Nth missionary, you remove a node from the list. So you don't have to keep track of missionaries that are not the eventual victim.

The second way is that the linked list's nodes are preserved throughout the operations. In this case, you basically have to keep a lot more state information. I won't describe exactly how to do this because it's clearly the inferior choice.


Read Steve McConnell's Code Complete for a good treatment of high-level pseudo-code (I believe he calls it PDL). Computer science god Donald Knuth advances this to an art form in the functional language he created called CWEB.

 

[m0ti]

actually, I'd recommend that you go with two linked lists. Each is a doubly linked list (using a sentinel for the head/tail). As you remove missionaries from the circle you add them to the other list. When there's only one left (you know this since it's next and prev are both sentinel) you have found the missionary which will be eaten. After you remove him, you can start working on the other list for the next round (basically, swap your pointers to the removed list and the now empty candidate list. Meaning that all the other missionaries are now candidates, and there are no missionaries who have been removed from the candidate list).

 

[HigherGround]

why would you want to use sentinel nodes around in each list, instead of depleting them to exhaustion ( in which case the test for the consumed missionary would be (m->next == m or m->prev == m) where m is a missionary node )

 

[Bluga]

<< while (missionary is not the victim) {

for (i from 1 to N) {

go to next missionary

}

Free the Nth missionary
}

The first way is that the linked list is a temporary data structure. When you get to the Nth missionary, you remove a node from the list. So you don't have to keep track of missionaries that are not the eventual victim.{ >>



If i "Remove" the Nth missionary, i'd only be able do it for one day, one person right? However the problem requires to do it for M-1 days, ie day 1, day 2, .......... how can i keep track of the list i deleted? Should i use another list? Thank you.

 

[Bluga]

<< After you remove him, you can start working on the other list for the next round (basically, swap your pointers to the removed list and the now empty candidate list. Meaning that all the other missionaries are now candidates, and there are no missionaries who have been removed from the candidate list).
>>



Could you please elaborate that? For example how can i delete and add at the same time? Thank you.

 

[Bluga]

.

 

[manly]

The problem with the dual linked-list swapping strategy suggested is that it doesn't preserve the order of the missionaries in the circle.

Which is why I stated that the circular linked list is a temporary data structure; i.e. you build it for each run (day). Like HigherGround said, you don't need a sentinel.

The original data structure could be a vector or another linked list; whatever's appropriate based on how the data is coming in.

If you want to start with just one circular doubly-linked list, and always operate on just that one data structure, then each node will have to keep extra state, and the tests are more tricky to implement.

 

[m0ti]

yes, you don't need the sentinel, it just makes things easier.

if you notice the example that he gave, the ordering for the second day is defined by the order in which the missionaries were removed on the first day. Thus, it's simplest to remove them from the one list and add them into the other until there's only one left. That last one is removed (and eaten) and then the pointers to the two lists can be swapped for the next day.

 

[manly]

m0ti,

Ahh you're right. I missed that subtlety. Two circular lists looks like a good choice.

I'm still not convinced a sentinel is important because the termination test is based on the number N.

 

[m0ti]

a sentinel isn't really necessary, I just find that it's more convenient to work with them, though actually in this case, you are right. Since we want to go around the circle, counting as we go, the sentinel just is a nuisance since it doesn't need to be counted.

to save even further, we could even use two circular singly linked lists, though the savings on doubly linked lists is really minor. the one thing that can be done to reasonably save time is to maintain a counter of how many missionary candidates are left (M), and each time take N%M steps (one can optimize this in the doubly linked case so that one never has to traverse more than M/2 elements), and remove that missionary.

 

[Bluga]

ok does the structure of my code look correct? thanks a bunch.

for (i = 1; i<j-1 ; i++) /* For j-1 days */
{
if (j%2==0) /*if even, clockwise*/
{
while (node != node->next)
{
m = fscanf(fp1, "%d", &n); /*read the numbers */
for (i = 1; i < m; i++)
{
node = list2;
node = node->next;
}
list2 = CDLListInsert (list2, node->data);
j = j-1;
}

}
else /* odd, counterclockwise */
{
while (node != node->previous)
{
m = fscanf(fp1, "%d", &n); /*read the numbers */
for (i = 1; i < m; i++)
{
node = list2;
node = node->previous;
}
list2 = CDLListInsert (list2, node->data);
j = j-1;
}
fprintf(fp2, "%c", &s);
}

}

 

[Bluga]

bump.

 

[Bluga]

^^

 

[vec]

I wasn't really paying attention to the algorithm, but from a code review standpoint, you have redundant code that could be centralized into a function:



<< while (node != node->next)
{
m = fscanf(fp1, "%d", &n); /*read the numbers */
for (i = 1; i < m; i++)
{
node = list2;
node = node->next;
}
list2 = CDLListInsert (list2, node->data);
j = j-1;
} >>



You should be able to pass j as the arg and have the check in there. Based upon the odd/even state of j, use node->next or node->prev accordingly.

Edit:

I think the for loop should be this?

node = list2;
for (i = 1; i < m; i++)
{
node = node->next;
}

If j really needs to be decremented (j-- works too) then make sure to pass it by reference (pointer) and not value.

just MHO

 

[HigherGround]

well, it's been a slow evening ( both Simposons episodes sucked ), anyway here's my solution to your problem, it's hardly readable code ( due to my sloppiness and forum formatting style ), so feel free to ask any question. It compiles and seem to run fine on Solaris 7.
edit: formatting, example output

example output:


day 1 : circle 1 : mary tom eve bart carol frank dan al maya jen [al was eaten]
day 2 : circle 2 : mary tom eve bart carol frank dan maya jen [carol was eaten]
day 3 : circle 1 : mary tom eve bart frank dan maya jen [mary was eaten]
day 4 : circle 2 : tom eve bart frank dan maya jen [tom was eaten]
day 5 : circle 1 : eve bart frank dan maya jen [eve was eaten]
day 6 : circle 2 : bart frank dan maya jen [frank was eaten]
day 7 : circle 1 : bart dan maya jen [bart was eaten]
day 8 : circle 2 : dan maya jen [dan was eaten]
day 9 : circle 1 : maya jen [maya was eaten]
day 10 : circle 2 : jen [jen was eaten]



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

typedef struct _missionary
{
struct _missionary* next;
struct _missionary* prev;
char* name;
int pos;
} missionary;

typedef struct _circle
{
missionary* first;
int count;
char* name;
} circle;

typedef enum _direction
{
CW = 0,
CCW
} direction;

int circle_append(circle* c, missionary* m)
{
if(c->first == NULL) { /* first missionary in the circle */
c->first = m->next = m->prev = m;
} else { /* add clockwise */
c->first->prev->next = m;
m->prev = c->first->prev;
c->first->prev = m;
m->next = c->first;
}
m->pos = m->prev->pos+1;
return ++c->count;
}

int circle_insert(circle* c, missionary* m)
{
missionary* n;
if(c->first == NULL) { /* first missionary in the circle */
c->first = m->next = m->prev = m;
} else {
n = c->first;
do {
if((m->pos > n->pos && m->pos < n->next->pos) || n->next == c->first) {
m->next = n->next;
n->next = m;
m->prev = n;
m->next->prev = m;
if(m->next == c->first && m->pos < m->next->pos)
c->first = m;
return ++c->count;
}
n = n->next;
} while(n != c->first);
}
return ++c->count;
}

void circle_print(int day, circle* c)
{
missionary* n = c->first;
if(!n)
return;
printf(" day %2d : circle %s : ", day, c->name);
do {
printf("%s ", n->name);
n = n->next;
} while(n != c->first);
}

/* remove missionary m from circle c, if missionary was the first
in circle nf becomes a new first */
int circle_remove(circle* c, circle* e, missionary* m, missionary* nf)
{
if(m->next == m) { /* last missionary is gone */
printf(" [%s was eaten]\n", m->name);
c->first = NULL;
} else { /* remove the requested missionary */
m->next->prev = m->prev;
m->prev->next = m->next;
if(m == c->first) /*if the missionary was first in circle, assign a new first */
c->first = nf;
circle_insert(e, m);
}
return --c->count;
}

/* remove a missionary in position p from circle c,
count in direction d */
int circle_remove_missionary(circle* c, circle* e, int p, direction d)
{
int ccp = 1;
missionary* m = c->first;

if(!m) /* empty circle */
return 0;
do {
if(ccp++ == p)
return circle_remove(c, e, m, d == CW ? c->first->next : c->first->prev);
m = d == CW ? m->next : m->prev;
} while(m != c->first);
return c->count;
}

int main(int argc, char* argv[])
{
int k = 0;
struct timeval seed; /* seed for rand */

/* make some missionaries */
missionary missionaries[] = {
{ NULL, NULL, "mary", 0 },
{ NULL, NULL, "tom", 0 },
{ NULL, NULL, "eve", 0 },
{ NULL, NULL, "bart", 0 },
{ NULL, NULL, "carol", 0 },
{ NULL, NULL, "frank", 0 },
{ NULL, NULL, "dan", 0 },
{ NULL, NULL, "al", 0 },
{ NULL, NULL, "maya", 0 },
{ NULL, NULL, "jen", 0 },
{ NULL, NULL, NULL, 0 }
};

/* form 2 circles */
circle circles[] = {
{ NULL, 0, "1" },
{ NULL, 0, "2" },
};

/* make a new pseudo rand seed */
gettimeofday(&seed, NULL);
srand((unsigned int)seed.tv_usec);

/* add missionaries to the first circle */
while(missionaries[k].name)
circle_append(&circles[0], &missionaries[k++]);

/* eat them one by one */
k = 0;
while(circles[(++k)%2].first || circles[!(k%2)].first) {
circle_print(k-1, &circles[k%2]);
while(circle_remove_missionary(&circles[k%2], &circles[!(k%2)],
1+(int)(1.*circles[k%2].count*rand( )/(RAND_MAX+1.)),
(direction)(circles[k%2].count%2)));
}
return 0;
}