Imagine the swap function has been implemented, making using namespace
std unecessary in this C99 code. And remember
http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6cf98ca39c45ce7b/124648c23bd40ace?hl=en&q=
? This scores 100%. It took me over the span of a year (coming back to
the problem every so often) to debug it from a 99% solution. How could
I have written _the code below_ so it would have taken less time to
debug?

#include <stdio.h>
#include <assert.h>
using namespace std;
const int MAXSEATS = 30050;
const int TRUE = 1;
const int FALSE = 0;
struct Group {
    int fseat, length;
} g[MAXSEATS];
Group pop();
void adjust_push();
int ngroups = 0;
int main() {
    FILE* in = fopen("aflin.txt", "r");   /* file containing input */
    assert(in != NULL);
    FILE* out = fopen("aflout.txt", "w"); /* file for writing output
to */
    assert(out != NULL);
    int nseats;
    assert(fscanf(in, "%d", &nseats) == 1);
    int nbookedseats;
    assert(fscanf(in, "%d", &nbookedseats) == 1);
    bool seats[MAXSEATS + 10];
    int i;
    for (i = 1; i <= nseats; i++)
        seats[i] = FALSE;
    for (i = 1; i <= nbookedseats; i++) {
        int temp;
        assert(fscanf(in, "%d", &temp) == 1);
        seats[temp] = TRUE;
    }
    int currlength = 0;
    for (i = 1; i <= nseats; i++) {
        if (seats[i] == FALSE)
            currlength++;
        if (i == nseats || seats[i] == true) {
            if (currlength == 0)
                continue;
            ngroups++;
            g[ngroups].length = currlength;
            g[ngroups].fseat = i - currlength;
            if (i == nseats && seats[i] == false)
                g[ngroups].fseat++;
            currlength = 0;
            adjust_push();
        }
    }
    int b;
    assert(fscanf(in, "%d", &b) == 1);
    for (int i = 1; i <= b; i++) {
        int length;
        assert(fscanf(in, "%d", &length) == 1);
        Group temp = pop();
        fprintf(out, "%d\n", temp.fseat);
        if (temp.length - length == 0)
            continue;
        ngroups++;
        g[ngroups].length = temp.length - length;
        g[ngroups].fseat = temp.fseat + length;
        adjust_push();
    }
    return 0;
}

Group pop() {
    Group temp = g[1];
    g[1] = g[ngroups];
    ngroups--;
    int idx = 1;
    int child;
    while(1) {
        if (idx * 2 > ngroups)
            return temp;
        if (idx * 2 + 1 <= ngroups) {
            if (g[idx * 2].length == g[idx * 2 + 1].length)
                if (g[idx * 2].fseat < g[idx * 2 + 1].fseat)
                    child = idx * 2;
                else
                    child = idx * 2 + 1;
            if (g[idx * 2].length < g[idx * 2 + 1].length)
                child = idx * 2 + 1;
            else if (g[idx * 2].length > g[idx * 2 + 1].length)
                child = idx * 2;
        }
        else
            child = idx * 2;
        if (g[idx].length == g[child].length)
            if (g[idx].fseat > g[child].fseat)
                swap(g[idx], g[child]);
        if (g[idx].length < g[child].length)
            swap(g[idx], g[child]);
        idx = child;
    }
    return temp;
}
void adjust_push() {
    int idx = ngroups;
    while (1) {
        int parent;
        if (idx > 1)
            parent = idx / 2;
        else
            return;
        if (g[idx].length == g[parent].length)
            if (g[idx].fseat < g[parent].fseat)
                swap(g[idx], g[parent]);
        if (g[idx].length > g[parent].length)
            swap(g[idx], g[parent]);
        idx = parent;
}

In 
<eb49fe62-e1d3-4d43-afaa-f761870f2760@x25g2000prf.googlegroups.com>, 
Albert wrote:

> Imagine the swap function has been implemented, making using
> namespace std unecessary in this C99 code. And remember
> 
http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6cf98ca39c45ce7b/124648c23bd40ace?hl=en&q=
> ? This scores 100%. It took me over the span of a year (coming back
> to the problem every so often) to debug it from a 99% solution. How
> could I have written _the code below_ so it would have taken less
> time to debug?

I'm going to resist the temptation to rewrite it, but I think the 
biggest ease-of-debugging win would have been better functional 
decomposition. Try rewriting it such that no function is more than 
ten lines long - and especially main(). Ten lines is overly 
restrictive, of course, but it'll be excellent practice.

<code snipped>

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

On Sep 11, 10:44=A0am, Albert <albert.xtheunkno...@gmail.com> wrote:

> the problem every so often) to debug it from a 99% solution. How could
> I have written _the code below_ so it would have taken less time to
> debug?

> void adjust_push() {
> =A0 =A0 int idx =3D ngroups;
> =A0 =A0 while (1) {
> =A0 =A0 =A0 =A0 int parent;
> =A0 =A0 =A0 =A0 if (idx > 1)
> =A0 =A0 =A0 =A0 =A0 =A0 parent =3D idx / 2;
> =A0 =A0 =A0 =A0 else
> =A0 =A0 =A0 =A0 =A0 =A0 return;
> =A0 =A0 =A0 =A0 if (g[idx].length =3D=3D g[parent].length)
> =A0 =A0 =A0 =A0 =A0 =A0 if (g[idx].fseat < g[parent].fseat)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 swap(g[idx], g[parent]);
> =A0 =A0 =A0 =A0 if (g[idx].length > g[parent].length)
> =A0 =A0 =A0 =A0 =A0 =A0 swap(g[idx], g[parent]);
> =A0 =A0 =A0 =A0 idx =3D parent;
> }

I was trying to apply RH's advice and reduce this 15-line function
into several functions of no more than 10 lines each. But where's does
that while-loop end?

--
Bartc

On September 11, 2009 05:44, in comp.lang.c, Albert
(albert.xtheunknown0@gmail.com) wrote:

> Imagine the swap function has been implemented, making using namespace
> std unecessary in this C99 code. And remember

I think you worded this in a less-than-optimal way. The way I read this, you
seem to claim that the code you presented was C99 compliant /and/ used a
  using namespace std;
to incorporate a swap() function. Since C99 doesn't provide a way to alter
the compiler's view of name spaces, the
  using namespace std;
statement means that your code is not "C99 code."

Perhaps you meant to say
 "Imagine that a swap() function existed such that rather than the C++ code
  below, I could have coded this in C99."

[snip]
> #include <stdio.h>
> #include <assert.h>
> using namespace std;

Like others, I would be interested in seeing your complete and correct
program. I'm not going to attempt to refactor it or even compile it,
though, as it doesn't seem to be syntactically correct C99 code in several
ways.

Sorry


[snip]
-- 
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/   | GPG public key available by request
----------      Slackware - Because I know what I'm doing.          ------

On Sep 11, 5:44=A0am, Albert <albert.xtheunkno...@gmail.com> wrote:
> Imagine the swap function has been implemented, making using namespace
> std unecessary in this C99 code. And rememberhttp://groups.google.com.au/=
group/comp.lang.c/browse_thread/thread/6c...
> ? This scores 100%. It took me over the span of a year (coming back to
> the problem every so often) to debug it from a 99% solution. How could
> I have written _the code below_ so it would have taken less time to
> debug?
[snip]

There are a number of techniques in program design that might have
helped. For me, the "top-down" "stepwise refinement" iterative
technique works best.

Typically, I start with a high-level description of what I want to do,
and (after proving the correctness of that description) code to that.
Complex functionality gets roughed in as stub function calls, along
with corresponding stub functions in code. After suitable review to
ensure that I haven't missed anything important, I compile and test
this high-level code. I revise, recompile, and retest until the high-
level code works to the design.

Afterwards, I tackle each of the stub functions, using the same
technique of rough-in, compile, test, fix/recompile/retest.

Hope this helps

In 
<a556a800-460b-4aad-886e-7f47048f360f@d23g2000vbm.googlegroups.com>, 
Bart wrote:

> On Sep 11, 10:44 am, Albert <albert.xtheunkno...@gmail.com> wrote:
> 
>> the problem every so often) to debug it from a 99% solution. How
>> could I have written _the code below_ so it would have taken less
>> time to debug?
> 
>> void adjust_push() {
>> int idx = ngroups;
>> while (1) {
>> int parent;
>> if (idx > 1)
>> parent = idx / 2;
>> else
>> return;
>> if (g[idx].length == g[parent].length)
>> if (g[idx].fseat < g[parent].fseat)
>> swap(g[idx], g[parent]);
>> if (g[idx].length > g[parent].length)
>> swap(g[idx], g[parent]);
>> idx = parent;
>> }
> 
> I was trying to apply RH's advice and reduce this 15-line function
> into several functions of no more than 10 lines each. But where's
> does that while-loop end?

Hmmm, that /was/ a tough call, wasn't it? Never mind the loop-end - we 
can work that out for ourselves, right? But getting 15 lines down to 
10... it's tempting to try this without further decomposition, yes? 
But that will just make the code /harder/ to debug. So let's look at 
how we can sensibly decompose it. To do this, first I'm going to 
rewrite it, to clarify the logic for my own benefit.

void adjust_push(void)
{
  int idx = ngroups;
  while(idx > 1)
  {
    int parent = idx / 2;
    if((g[idx].length == g[parent].length &&
        g[idx].fseat < g[parent].fseat)   ||
       (g[idx].length > g[parent].length))
    {
      swap(g[idx], g[parent]); /* hmmm, not using pointers here? */
    }
    idx = parent;
  }
}

The next job is to reduce the function to ten lines ("shhh... the 
maestro is decomposing" - Gary Larson).

For counting purposes, I'm going to ignore declarators, whitespace, 
comments, and braces. The above contains only four (logical) or six 
(physical) lines that do not fall into any of those categories, so 
we're done here.

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

On Sep 11, 9:13=A0pm, Richard Heathfield <r...@see.sig.invalid> wrote:
> In
> <a556a800-460b-4aad-886e-7f47048f3...@d23g2000vbm.googlegroups.com>,
>
>
>
>
>
> Bart wrote:
> > On Sep 11, 10:44 am, Albert <albert.xtheunkno...@gmail.com> wrote:

> >> while (1) {
....

> > I was trying to apply RH's advice and reduce this 15-line function
> > into several functions of no more than 10 lines each. But where's
> > does that while-loop end?
>
> Hmmm, that /was/ a tough call, wasn't it? Never mind the loop-end - we
> can work that out for ourselves, right? But getting 15 lines down to
> 10... it's tempting to try this without further decomposition, yes?
> But that will just make the code /harder/ to debug. So let's look at
> how we can sensibly decompose it. To do this, first I'm going to
> rewrite it, to clarify the logic for my own benefit.
>
> void adjust_push(void)
> {
> =A0 int idx =3D ngroups;
> =A0 while(idx > 1)
> =A0 {
> =A0 =A0 int parent =3D idx / 2;
> =A0 =A0 if((g[idx].length =3D=3D g[parent].length &&
> =A0 =A0 =A0 =A0 g[idx].fseat < g[parent].fseat) =A0 ||
> =A0 =A0 =A0 =A0(g[idx].length > g[parent].length))
> =A0 =A0 {
> =A0 =A0 =A0 swap(g[idx], g[parent]); /* hmmm, not using pointers here? */
> =A0 =A0 }
> =A0 =A0 idx =3D parent;
> =A0 }
>
> }
....
> For counting purposes, I'm going to ignore declarators, whitespace,
> comments, and braces. The above contains only four (logical) or six
> (physical) lines that do not fall into any of those categories, so
> we're done here.

Nice work. Perhaps you could have squeezed that if-condition onto a
single line too.

But, I would still have investigated that missing loop-end brace, in
case there was something else amiss.

--
Bartc

On Fri, 11 Sep 2009 02:44:53 -0700 (PDT), Albert
<albert.xtheunknown0@gmail.com> wrote:

>Imagine the swap function has been implemented, making using namespace
>std unecessary in this C99 code. And remember
>http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6cf98ca39c45ce7b/124648c23bd40ace?hl=en&q=
>? This scores 100%. It took me over the span of a year (coming back to
>the problem every so often) to debug it from a 99% solution. How could
>I have written _the code below_ so it would have taken less time to
>debug?

The short answer is that you shouldn't have written this code.
:-)

In truth, I suspect that it is not correct, despite the fact that
it scored 100%.  First of all a heap is not the right data
structure for this problem.  Basically what you have is a set of
intervals of varying lengths; each interval has two parameters,
length and initial address (seat number).  There is a natural
order; if A and B are two intervals A precedes B if the length of
A is less than the length of B or if they have the same length
but the address of A is less than the address of B.  Now the
problem with using a heap is that it only provides the minimum.
What you are searching for is the first interval above a certain
threshold value.  A heap doesn't provide that information
although there are hacks that will almost work.  (There is such a
thing as a heap structured search tree, but that is for another
time.)  It's a red flag that earlier you talked about adjusting
the heap.

There are other red flags.  For example, where did the 10 come
from in the line
   bool seats[MAXSEATS + 10];

This is a typical mysterious magic number.  Why 10?  It smells
like a misinterpretation of the problem statement, which I quote:

   Each of these lines will contain a single integer k
   representing the number of seats to be booked (1 <= k <= n).

If you thought "a single integer" meant "a single digit" that
might account for it.  Then again, there might be some other
explanation.  The rule is: Always document your magic numbers.

The only comments are in the two lines that don't need comments.

The main program has two major sections, one to do initializing
of initial seat assignments and one that responds to bookings.
It would be advisable to put them in separate functions -
functions documented by their purpose and operation.

Another red flag is the persistent of one based loops, e.g.,
    for (i = 1; i <= nseats; i++) {...}
This particular one would have caused an array overflow if it
weren't for that mysterious +10.  I understand why you used them
- seat numbers start with 1 - but it is a dangerous practice.
The thing is, if you allocate N items for array A, A[N] is out of
bounds.

There are some minor flakiness.  For example you define TRUE and
FALSE, and then use true and false in some places.

I don't use C99 so "using namespace std;" might be a bit of C99
but it looks like C++ to me.  In any case you don't need it.
Writing swap out in full is not exactly an onerous task.

To be honest, I find your code to be ugly and hard to read.  I
don't like the formatting and I don't like the naming
conventions.  I'm not sure that you have all of your bits and
pieces correct.  Mind you, you might not like code I write -
people have different styles - but you might think about it.

At this point you may be asking, how would you do it Mr. Smarty
Pants.  It all depends on whether I wanted to do some high
performance code or whether I just wanted something simple that
works.

The simple thing is to put the predefined seat positions in a
heap, compute the intervals and put them in a binary search tree
using the natural order, and then feed the requests into a
booking routine which searches for the correct interval, extracts
it from the tree, takes the desired booking out of the interval,
and enters the remnant, if any, back in the tree.  The reason
this is simple is that the data structures are all available as
canned utilities.  The actual code that requires thought is about
a dozen lines of code.

Now if I wanted to play with performance I probably do something
like an array of heaps, with each array index corresponding to a
request length.  The heaps would have left most addresses at
their head.  The upshot would be that almost bookings would be
O(1) whereas using trees would be O(log n) where n is the number
of intervals.

Oh, yes, as one final thing in debugging, test your program with 
MAXSEATS equal something like 100 and a lot of test cases.  It
makes it a lot easier when you come up with some result that you
don't quite understand.

And as another final point, it pays to write a bonehead version
that is really simple even if it is slow.  Run your program
against the bonehead version.  All discrepancies are bugs in one
version or the other.

 



>
>#include <stdio.h>
>#include <assert.h>
>using namespace std;
>const int MAXSEATS = 30050;
>const int TRUE = 1;
>const int FALSE = 0;
>struct Group {
>    int fseat, length;
>} g[MAXSEATS];
>Group pop();
>void adjust_push();
>int ngroups = 0;
>int main() {
>    FILE* in = fopen("aflin.txt", "r");   /* file containing input */
>    assert(in != NULL);
>    FILE* out = fopen("aflout.txt", "w"); /* file for writing output
>to */
>    assert(out != NULL);
>    int nseats;
>    assert(fscanf(in, "%d", &nseats) == 1);
>    int nbookedseats;
>    assert(fscanf(in, "%d", &nbookedseats) == 1);
>    bool seats[MAXSEATS + 10];
>    int i;
>    for (i = 1; i <= nseats; i++)
>        seats[i] = FALSE;
>    for (i = 1; i <= nbookedseats; i++) {
>        int temp;
>        assert(fscanf(in, "%d", &temp) == 1);
>        seats[temp] = TRUE;
>    }
>    int currlength = 0;
>    for (i = 1; i <= nseats; i++) {
>        if (seats[i] == FALSE)
>            currlength++;
>        if (i == nseats || seats[i] == true) {
>            if (currlength == 0)
>                continue;
>            ngroups++;
>            g[ngroups].length = currlength;
>            g[ngroups].fseat = i - currlength;
>            if (i == nseats && seats[i] == false)
>                g[ngroups].fseat++;
>            currlength = 0;
>            adjust_push();
>        }
>    }
>    int b;
>    assert(fscanf(in, "%d", &b) == 1);
>    for (int i = 1; i <= b; i++) {
>        int length;
>        assert(fscanf(in, "%d", &length) == 1);
>        Group temp = pop();
>        fprintf(out, "%d\n", temp.fseat);
>        if (temp.length - length == 0)
>            continue;
>        ngroups++;
>        g[ngroups].length = temp.length - length;
>        g[ngroups].fseat = temp.fseat + length;
>        adjust_push();
>    }
>    return 0;
>}
>
>Group pop() {
>    Group temp = g[1];
>    g[1] = g[ngroups];
>    ngroups--;
>    int idx = 1;
>    int child;
>    while(1) {
>        if (idx * 2 > ngroups)
>            return temp;
>        if (idx * 2 + 1 <= ngroups) {
>            if (g[idx * 2].length == g[idx * 2 + 1].length)
>                if (g[idx * 2].fseat < g[idx * 2 + 1].fseat)
>                    child = idx * 2;
>                else
>                    child = idx * 2 + 1;
>            if (g[idx * 2].length < g[idx * 2 + 1].length)
>                child = idx * 2 + 1;
>            else if (g[idx * 2].length > g[idx * 2 + 1].length)
>                child = idx * 2;
>        }
>        else
>            child = idx * 2;
>        if (g[idx].length == g[child].length)
>            if (g[idx].fseat > g[child].fseat)
>                swap(g[idx], g[child]);
>        if (g[idx].length < g[child].length)
>            swap(g[idx], g[child]);
>        idx = child;
>    }
>    return temp;
>}
>void adjust_push() {
>    int idx = ngroups;
>    while (1) {
>        int parent;
>        if (idx > 1)
>            parent = idx / 2;
>        else
>            return;
>        if (g[idx].length == g[parent].length)
>            if (g[idx].fseat < g[parent].fseat)
>                swap(g[idx], g[parent]);
>        if (g[idx].length > g[parent].length)
>            swap(g[idx], g[parent]);
>        idx = parent;
>}

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!

In <4aaad050.53519234@text.giganews.com>, Richard Harter wrote:

> On Fri, 11 Sep 2009 02:44:53 -0700 (PDT), Albert
> <albert.xtheunknown0@gmail.com> wrote:
> 
>>Imagine the swap function has been implemented, making using
>>namespace std unecessary in this C99 code. And remember
>>http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6cf98ca39c45ce7b/124648c23bd40ace?hl=en&q=
>>? This scores 100%. It took me over the span of a year (coming back
>>to the problem every so often) to debug it from a 99% solution. How
>>could I have written _the code below_ so it would have taken less
>>time to debug?
> 
> The short answer is that you shouldn't have written this code.
> :-)

To be fair, the specification is broken too. Let's say you have a 
current occupancy as follows:

X-------------X-X

A customer books a single seat. The spec's rules call for you to 
allocate the leftmost seat in the longest unbroken sequence of empty 
seats:

XX------------X-X

completely ignoring the single-seat space near the right-hand end. 
This means that you have to turn away the next customer, who wants 13 
contiguous seats, whereas you *could* have accommodated the larger 
order if you'd done the Right Thing with the first customer. (The 
spec claims this never happens, but forgets to add "I hope...".)

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

cri@tiac.net (Richard Harter) writes:
<snip>
> In truth, I suspect that it is not correct, despite the fact that
> it scored 100%.  First of all a heap is not the right data
> structure for this problem.

I am not so sure...

>  Basically what you have is a set of
> intervals of varying lengths; each interval has two parameters,
> length and initial address (seat number).  There is a natural
> order; if A and B are two intervals A precedes B if the length of
> A is less than the length of B or if they have the same length
> but the address of A is less than the address of B.  Now the
> problem with using a heap is that it only provides the minimum.
> What you are searching for is the first interval above a certain
> threshold value.

The specification calls for allocating the seats from the largest
interval.  All the test data sets are designed so that this strategy
works.  That's not to say that a heap is optimal, but it does provide
O(1) access to the desired interval.

>  A heap doesn't provide that information
> although there are hacks that will almost work.  (There is such a
> thing as a heap structured search tree, but that is for another
> time.)  It's a red flag that earlier you talked about adjusting
> the heap.

<snip>
-- 
Ben.

On Sep 12, 3:33=A0am, Richard Heathfield <r...@see.sig.invalid> wrote:
> In <4aaad050.53519...@text.giganews.com>, Richard Harter wrote:
>
> > On Fri, 11 Sep 2009 02:44:53 -0700 (PDT), Albert
> > <albert.xtheunkno...@gmail.com> wrote:
>
> >>Imagine the swap function has been implemented, making using
> >>namespace std unecessary in this C99 code. And remember
> >>http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6c..=
..
> >>? This scores 100%. It took me over the span of a year (coming back
> >>to the problem every so often) to debug it from a 99% solution. How
> >>could I have written _the code below_ so it would have taken less
> >>time to debug?
>
> > The short answer is that you shouldn't have written this code.
> > :-)
>
> To be fair, the specification is broken too. Let's say you have a
> current occupancy as follows:
>
> X-------------X-X
>
> A customer books a single seat. The spec's rules call for you to
> allocate the leftmost seat in the longest unbroken sequence of empty
> seats:
>
> XX------------X-X
>
> completely ignoring the single-seat space near the right-hand end.
> This means that you have to turn away the next customer, who wants 13
> contiguous seats, whereas you *could* have accommodated the larger
> order if you'd done the Right Thing with the first customer. (The
> spec claims this never happens, but forgets to add "I hope...".)

If it's really that simple I can't see the need for all these arrays
of heaps being talked about; just a char array representing the seats
will do. And the score should be always 100% unless 100% is impossible
anyway when applying their strategy to their (hidden) input.

I can't see this taking a year to figure out. Or am I missing
something?

--
Bartc

Bart <bc@freeuk.com> writes:

> On Sep 12, 3:33 am, Richard Heathfield <r...@see.sig.invalid> wrote:
>> In <4aaad050.53519...@text.giganews.com>, Richard Harter wrote:
>>
>> > On Fri, 11 Sep 2009 02:44:53 -0700 (PDT), Albert
>> > <albert.xtheunkno...@gmail.com> wrote:
>>
>> >>Imagine the swap function has been implemented, making using
>> >>namespace std unecessary in this C99 code. And remember
>> >>http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6c...
>> >>? This scores 100%. It took me over the span of a year (coming back
>> >>to the problem every so often) to debug it from a 99% solution. How
>> >>could I have written _the code below_ so it would have taken less
>> >>time to debug?
>>
>> > The short answer is that you shouldn't have written this code.
>> > :-)
>>
>> To be fair, the specification is broken too. Let's say you have a
>> current occupancy as follows:
>>
>> X-------------X-X
>>
>> A customer books a single seat. The spec's rules call for you to
>> allocate the leftmost seat in the longest unbroken sequence of empty
>> seats:
>>
>> XX------------X-X
>>
>> completely ignoring the single-seat space near the right-hand end.
>> This means that you have to turn away the next customer, who wants 13
>> contiguous seats, whereas you *could* have accommodated the larger
>> order if you'd done the Right Thing with the first customer. (The
>> spec claims this never happens, but forgets to add "I hope...".)
>
> If it's really that simple I can't see the need for all these arrays
> of heaps being talked about; just a char array representing the seats
> will do. And the score should be always 100% unless 100% is impossible
> anyway when applying their strategy to their (hidden) input.

You get 0% (for that one input set) if the program is too slow.  You
can register and try out your own solution -- it's fun!

> I can't see this taking a year to figure out. Or am I missing
> something?

The OP is learning but (IIRC) not studying CS formally.  What you may
be missing is getting a solution fast enough.  A slow correct one is
quite easy.

-- 
Ben.

On Sat, 12 Sep 2009 02:33:37 +0000, Richard Heathfield
<rjh@see.sig.invalid> wrote:

>In <4aaad050.53519234@text.giganews.com>, Richard Harter wrote:
>
>> On Fri, 11 Sep 2009 02:44:53 -0700 (PDT), Albert
>> <albert.xtheunknown0@gmail.com> wrote:
>> 
>>>Imagine the swap function has been implemented, making using
>>>namespace std unecessary in this C99 code. And remember
>>>http://groups.google.com.au/group/comp.lang.c/browse_thread/thread/6cf98ca39c45ce7b/124648c23bd40ace?hl=en&q=
>>>? This scores 100%. It took me over the span of a year (coming back
>>>to the problem every so often) to debug it from a 99% solution. How
>>>could I have written _the code below_ so it would have taken less
>>>time to debug?
>> 
>> The short answer is that you shouldn't have written this code.
>> :-)
>
>To be fair, the specification is broken too. Let's say you have a 
>current occupancy as follows:
>
>X-------------X-X
>
>A customer books a single seat. The spec's rules call for you to 
>allocate the leftmost seat in the longest unbroken sequence of empty 
>seats:
>
>XX------------X-X
>
>completely ignoring the single-seat space near the right-hand end. 
>This means that you have to turn away the next customer, who wants 13 
>contiguous seats, whereas you *could* have accommodated the larger 
>order if you'd done the Right Thing with the first customer. (The 
>spec claims this never happens, but forgets to add "I hope...".)

You are quite right.  In actual fact I glossed over that.  My
bad.  It doesn't really matter as far as my comments go, except
that I was picturing the wrong problem.  With their requirement
our hapless programmer is right to use a heap, since he always
wants the longest interval at the top of the heap.

My apologies.

Where I went wrong is that I was thinking of the corresponding
storage allocation strategy, this problem being a thinly
disguised version of take from longest.  The advantage of take
from longest is that you can have long runs of very cheap
allocations - just chop another bit off the old sausage.  In the
long run, though, it does the nasty on fragmentation.

Given a correct reading of the requirement, the problem is
simpler than I had assumed.  OP's code is still a mess, though.

  
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!

On Sat, 12 Sep 2009 03:48:56 +0100, Ben Bacarisse
<ben.usenet@bsb.me.uk> wrote:

>cri@tiac.net (Richard Harter) writes:
><snip>
>> In truth, I suspect that it is not correct, despite the fact that
>> it scored 100%.  First of all a heap is not the right data
>> structure for this problem.
>
>I am not so sure...
>
>>  Basically what you have is a set of
>> intervals of varying lengths; each interval has two parameters,
>> length and initial address (seat number).  There is a natural
>> order; if A and B are two intervals A precedes B if the length of
>> A is less than the length of B or if they have the same length
>> but the address of A is less than the address of B.  Now the
>> problem with using a heap is that it only provides the minimum.
>> What you are searching for is the first interval above a certain
>> threshold value.
>
>The specification calls for allocating the seats from the largest
>interval.  All the test data sets are designed so that this strategy
>works.  That's not to say that a heap is optimal, but it does provide
>O(1) access to the desired interval.

Quite right.  I misread the spec.  I got a 0%.  :-)

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!

On Sep 12, 4:08=A0am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> Bart <b...@freeuk.com> writes:

>
> You get 0% (for that one input set) if the program is too slow. =A0You
> can register and try out your own solution -- it's fun!
>
> > I can't see this taking a year to figure out. Or am I missing
> > something?
>
> The OP is learning but (IIRC) not studying CS formally. =A0What you may
> be missing is getting a solution fast enough. =A0A slow correct one is
> quite easy.

You're right. If the 'row' has 100,000 seats, and bookings are one
seat at a time, then it may involve checking seats billions of times,
and even C might only manage a few hundred million per second. The
time limit I remember was one second, on a machine with unknown
performance.

So yes there's a good case for something a bit more elaborate,
maintaining a sorted list of empty blocks or whatever.

--
Bartc

Richard Heathfield wrote:
> For counting purposes, I'm going to ignore declarators, whitespace,
> comments, and braces. The above contains only four (logical) or six
> (physical) lines that do not fall into any of those categories, so
> we're done here.

11 lines max.

#include <stdio.h>
#include <assert.h>
enum { MAXSEATS = 30010 };

struct Group {
    int fseat, length;
} g[MAXSEATS];

FILE *in, *out;
int ngroups = 0;
int nseats, seats[MAXSEATS];

void swap(struct Group *g, struct Group *h) {
    struct Group i = *g;
    *g = *h;
    *h = i;
}

void adjust_push() {
  int idx = ngroups;
  while(idx > 1) {
    int parent = idx / 2;
    if ((g[idx].length == g[parent].length && g[idx].fseat < g
[parent].fseat) || g[idx].length > g[parent].length)
      swap(&g[idx], &g[parent]);
    idx = parent;
  }
}

struct Group pop() {
  swap(&g[1], &g[ngroups]);
  ngroups--;
  int idx = 1, child;
  while (idx * 2 <= ngroups) {
    if (idx * 2 + 1 > ngroups || (idx * 2 + 1 <= ngroups && ((g[idx *
2].length == g[idx * 2 + 1].length && g[idx * 2].fseat < g[idx * 2 +
1].fseat) || g[idx * 2].length > g[idx * 2 + 1].length)))
      child = idx * 2;
    else
      child = idx * 2 + 1;
    if ((g[idx].length == g[child].length && g[idx].fseat > g
[child].fseat) || g[idx].length < g[child].length)
      swap(&g[idx], &g[child]);
    idx = child;
  }
  return g[ngroups + 1];
}

void repinput() {
    int i;
    int currlength = 0;
    for (i = 1; i <= nseats; i++) {
        if (seats[i] == 0)
            currlength++;
        if (i == nseats || seats[i] == 1) {
            ngroups++;
            g[ngroups].length = currlength;
            g[ngroups].fseat = i - currlength;
            if (i == nseats && seats[i] == 0)
                g[ngroups].fseat++;
            currlength = 0;
            adjust_push();
        }
    }
}

void handlebookings() {
  int i, b, x;
  fscanf(in, "%d", &b);
  for (i = 1; i <= b; i++) {
    fscanf(in, "%d", &x);
    struct Group temp = pop();
    fprintf(out, "%d\n", temp.fseat);
    ngroups++;
    g[ngroups].length = temp.length - x;
    g[ngroups].fseat = temp.fseat + x;
    adjust_push();
  }
}

int main() {
    in = fopen("aflin.txt", "r");
    out = fopen("aflout.txt", "w");
    int nbookedseats, i, x, b;
    fscanf(in, "%d %d", &nseats, &nbookedseats);
    for (i = 1; i <= nseats; i++)
        seats[i] = 0;
    for (i = 1; i <= nbookedseats; i++) {
        fscanf(in, "%d", &x);
        seats[x] = 1;
    }
    repinput();
    handlebookings();
    return 0;
}

Bart wrote:
> I can't see this taking a year to figure out.

I don't think you should be able to.

> Or am I missing something?

Yes, when I mentioned that I've received 99%, it meant that my program
delivered the wrong output a few times. Specificially, it scored 99%
on input #27, 77% on input #38 and 60% on input #49. All other 46
inputs were handled correctly.

Note: The inputs will _always_ remain secret.

Which was darn fustrating. Having written a heap that works 99% on
_their_ test cases, 100% of the time in your own thought up test cases
(lots of equal-lengthed Groups, alternating booked seats, using the
maximums seen in the specfication etc.)

On Sep 11, 10:47=A0pm, Albert <albert.xtheunkno...@gmail.com> wrote:
> Richard Heathfield wrote:
> > For counting purposes, I'm going to ignore declarators, whitespace,
> > comments, and braces. The above contains only four (logical) or six
> > (physical) lines that do not fall into any of those categories, so
> > we're done here.
>
> 11 lines max.
>
> #include <stdio.h>
> #include <assert.h>
> enum { MAXSEATS =3D 30010 };
>
> struct Group {
> =A0 =A0 int fseat, length;
>
> } g[MAXSEATS];
>
> FILE *in, *out;
> int ngroups =3D 0;
> int nseats, seats[MAXSEATS];
>
> void swap(struct Group *g, struct Group *h) {
> =A0 =A0 struct Group i =3D *g;
> =A0 =A0 *g =3D *h;
> =A0 =A0 *h =3D i;
>
> }
>
> void adjust_push() {
> =A0 int idx =3D ngroups;
> =A0 while(idx > 1) {
> =A0 =A0 int parent =3D idx / 2;
> =A0 =A0 if ((g[idx].length =3D=3D g[parent].length && g[idx].fseat < g
> [parent].fseat) || g[idx].length > g[parent].length)
> =A0 =A0 =A0 swap(&g[idx], &g[parent]);
> =A0 =A0 idx =3D parent;
> =A0 }
>
> }
>
> struct Group pop() {
> =A0 swap(&g[1], &g[ngroups]);
> =A0 ngroups--;
> =A0 int idx =3D 1, child;
> =A0 while (idx * 2 <=3D ngroups) {
> =A0 =A0 if (idx * 2 + 1 > ngroups || (idx * 2 + 1 <=3D ngroups && ((g[idx=
 *
> 2].length =3D=3D g[idx * 2 + 1].length && g[idx * 2].fseat < g[idx * 2 +
> 1].fseat) || g[idx * 2].length > g[idx * 2 + 1].length)))
> =A0 =A0 =A0 child =3D idx * 2;
> =A0 =A0 else
> =A0 =A0 =A0 child =3D idx * 2 + 1;
> =A0 =A0 if ((g[idx].length =3D=3D g[child].length && g[idx].fseat > g
> [child].fseat) || g[idx].length < g[child].length)
> =A0 =A0 =A0 swap(&g[idx], &g[child]);
> =A0 =A0 idx =3D child;
> =A0 }
> =A0 return g[ngroups + 1];
>
> }
>
> void repinput() {
> =A0 =A0 int i;
> =A0 =A0 int currlength =3D 0;
> =A0 =A0 for (i =3D 1; i <=3D nseats; i++) {
> =A0 =A0 =A0 =A0 if (seats[i] =3D=3D 0)
> =A0 =A0 =A0 =A0 =A0 =A0 currlength++;
> =A0 =A0 =A0 =A0 if (i =3D=3D nseats || seats[i] =3D=3D 1) {
> =A0 =A0 =A0 =A0 =A0 =A0 ngroups++;
> =A0 =A0 =A0 =A0 =A0 =A0 g[ngroups].length =3D currlength;
> =A0 =A0 =A0 =A0 =A0 =A0 g[ngroups].fseat =3D i - currlength;
> =A0 =A0 =A0 =A0 =A0 =A0 if (i =3D=3D nseats && seats[i] =3D=3D 0)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 g[ngroups].fseat++;
> =A0 =A0 =A0 =A0 =A0 =A0 currlength =3D 0;
> =A0 =A0 =A0 =A0 =A0 =A0 adjust_push();
> =A0 =A0 =A0 =A0 }
> =A0 =A0 }
>
> }
>
> void handlebookings() {
> =A0 int i, b, x;
> =A0 fscanf(in, "%d", &b);
> =A0 for (i =3D 1; i <=3D b; i++) {
> =A0 =A0 fscanf(in, "%d", &x);
> =A0 =A0 struct Group temp =3D pop();
> =A0 =A0 fprintf(out, "%d\n", temp.fseat);
> =A0 =A0 ngroups++;
> =A0 =A0 g[ngroups].length =3D temp.length - x;
> =A0 =A0 g[ngroups].fseat =3D temp.fseat + x;
> =A0 =A0 adjust_push();
> =A0 }
>
> }
>
> int main() {
> =A0 =A0 in =3D fopen("aflin.txt", "r");
> =A0 =A0 out =3D fopen("aflout.txt", "w");
> =A0 =A0 int nbookedseats, i, x, b;
> =A0 =A0 fscanf(in, "%d %d", &nseats, &nbookedseats);
> =A0 =A0 for (i =3D 1; i <=3D nseats; i++)
> =A0 =A0 =A0 =A0 seats[i] =3D 0;
> =A0 =A0 for (i =3D 1; i <=3D nbookedseats; i++) {
> =A0 =A0 =A0 =A0 fscanf(in, "%d", &x);
> =A0 =A0 =A0 =A0 seats[x] =3D 1;
> =A0 =A0 }
> =A0 =A0 repinput();
> =A0 =A0 handlebookings();
> =A0 =A0 return 0;
>
>
>
> }

Here you declare a static duration array of struct group called seats:

struct Group {
    int             fseat,
                    length;
}  g[MAXSEATS];

Here you pass in a parameter called g, which overrides the public
symbol:

void            swap(struct Group * g, struct Group * h)
{
    struct Group    i =3D *g;
    *g =3D *h;
    *h =3D i;
}

This can be confusing.  You will probably use it on elements of the
struct array, but it would be better make g local to main.  Lacking
that option, it would be better to avoid passing g, since it is the
global object list anyway.

Comments -- in general...
You use public symbols when they could be auto variables in main() or
lower.  It's not a problem in a teeny program like this, but it will
become a big problem in non-trivial functions.  You should break out
of this habit as soon as possible.

You can easily generalize some of the things that are hardwired.

For instance, if you pass the file names in on the command line, then
the program will be more flexible to accept different names or
locations.

Bart wrote:
> You're right. If the 'row' has 100,000 seats, and bookings are one
> seat at a time, then it may involve checking seats billions of times,
> and even C might only manage a few hundred million per second. The
> time limit I remember was one second, on a machine with unknown
> performance.

_We_ assume a computer can perform 100 million operations per second.

user923005 wrote:
> You use public symbols when they could be auto variables in main() or
> lower. =A0It's not a problem in a teeny program like this, but it will
> become a big problem in non-trivial functions. =A0You should break out
> of this habit as soon as possible.

Could you provide an example please?

On Sep 11, 11:08=A0pm, Albert <albert.xtheunkno...@gmail.com> wrote:
> user923005 wrote:
> > You use public symbols when they could be auto variables in main() or
> > lower. =A0It's not a problem in a teeny program like this, but it will
> > become a big problem in non-trivial functions. =A0You should break out
> > of this habit as soon as possible.
>
> Could you provide an example please?

The query:
http://www.google.com/search?hl=3Den&source=3Dhp&q=3Dglobal+variables+are+e=
vil&rlz=3D1W1GGLD_en&aq=3Df&oq=3D&aqi=3D
had 74,400 hits, including these:

http://www.cs.usfca.edu/~wolber/courses/110/lectures/globals.htm
http://ubuntuforums.org/showthread.php?t=3D658778
http://www.learncpp.com/cpp-tutorial/42-global-variables/

user923005 wrote:
> On Sep 11, 11:08=A0pm, Albert <albert.xtheunkno...@gmail.com> wrote:
>
> > user923005 wrote:
> > > You use public symbols when they could be auto variables in main() or
> > > lower. =A0It's not a problem in a teeny program like this, but it wil=
l
> > > become a big problem in non-trivial functions. =A0You should break ou=
t
> > > of this habit as soon as possible.
>
> > Could you provide an example please?
>
> The query:http://www.google.com/search?hl=3Den&source=3Dhp&q=3Dglobal+var=
iables+are+e...

My bad: I didn't know public symbols meant global variables.

The global variable ngroups is accessed by 4 functions. Wouldn't the
program run slower if all 4 of these functions needed ngroups to be
passed to be them?

On Sep 12, 12:21=A0am, Albert <albert.xtheunkno...@gmail.com> wrote:
> user923005 wrote:
> > On Sep 11, 11:08=A0pm, Albert <albert.xtheunkno...@gmail.com> wrote:
>
> > > user923005 wrote:
> > > > You use public symbols when they could be auto variables in main() =
or
> > > > lower. =A0It's not a problem in a teeny program like this, but it w=
ill
> > > > become a big problem in non-trivial functions. =A0You should break =
out
> > > > of this habit as soon as possible.
>
> > > Could you provide an example please?
>
> > The query:http://www.google.com/search?hl=3Den&source=3Dhp&q=3Dglobal+v=
ariables+are+e...
>
> My bad: I didn't know public symbols meant global variables.
>
> The global variable ngroups is accessed by 4 functions. Wouldn't the
> program run slower if all 4 of these functions needed ngroups to be
> passed to be them?

The speed of the program will be dominated by the fundamental nature
of the algorithm.

You will not be able to measure any speed change going from public
symbols to auto variables in your program.

Never microoptimize code because you think it might be faster if it is
less clear or harder to debug than the simpler idea.

Your goal should be this:
Write the clearest code that is possible so you know that it is
correct.  Your code should be as easy to debug as possible.

You may have some ideas about what bits of the code will be slow, so
in your design, choose an optimal algorithm for these.

If profiles turn up slow spots, then improve the algorithm for those
slow spots.

80% of the cost of software is maintenance.  It is very important to
write code that is easy to maintain.

Richard Harter wrote:
) In truth, I suspect that it is not correct, despite the fact that
) it scored 100%.  First of all a heap is not the right data
) structure for this problem.

Read the problem spec again, you seem to have misunderstood it.

It specifically describes the algorithm for finding the correct seats.

That algorithm is to take the longest sequence, and if there are more
of equal length, take the leftmost of those.  Nothing more, nothing less.

) Basically what you have is a set of
) intervals of varying lengths; each interval has two parameters,
) length and initial address (seat number).  There is a natural
) order; if A and B are two intervals A precedes B if the length of
) A is less than the length of B or if they have the same length
) but the address of A is less than the address of B.  Now the
) problem with using a heap is that it only provides the minimum.

Exactly.  And given the problem description, this is all you have to find.

) What you are searching for is the first interval above a certain
) threshold value.

What threshold value ?


For the record: the OP's code looks almost correct, there is
a simple bug in it which I pointed out crossthread.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

In <4200aa94-9b43-4ebb-be9b-2851ae3d0ae5@x5g2000prf.googlegroups.com>, 
Albert wrote:

> Richard Heathfield wrote:
>> For counting purposes, I'm going to ignore declarators, whitespace,
>> comments, and braces. The above contains only four (logical) or six
>> (physical) lines that do not fall into any of those categories, so
>> we're done here.
> 
> 11 lines max.

Much better, but there is still room for improvement. (I am talking 
specifically about functional decomposition here - user923005 has 
made some other relevant comments.)

<snip>

> void swap(struct Group *g, struct Group *h) {

Fine.

> void adjust_push() {

Fine, although I suggest getting into the habit of being specific 
about taking no parameters: void adjust_push(void)

Better still, take parameters, so that the function has data to work 
on!

> struct Group pop() {
>   swap(&g[1], &g[ngroups]);
>   ngroups--;
>   int idx = 1, child;
>   while (idx * 2 <= ngroups) {
>     if (idx * 2 + 1 > ngroups || (idx * 2 + 1 <= ngroups && ((g[idx
>     *
> 2].length == g[idx * 2 + 1].length && g[idx * 2].fseat < g[idx * 2 +
> 1].fseat) || g[idx * 2].length > g[idx * 2 + 1].length)))
>       child = idx * 2;
>     else
>       child = idx * 2 + 1;
>     if ((g[idx].length == g[child].length && g[idx].fseat > g
> [child].fseat) || g[idx].length < g[child].length)
>       swap(&g[idx], &g[child]);
>     idx = child;
>   }
>   return g[ngroups + 1];
> }

Fairly short, but still quite hard to read. Consider this alternative 
(which still has issues; in this reply I am dealing ONLY with 
functional  decomposition, so any other problems in the code will 
still be there in my suggested replacement).

static int selectchild(int idx)
{
  int cca = idx * 2; /* Child Candidate A */
  int ccb = cca + 1; /* Child Candidate B */
 
 
 if(ccb > ngroups ||
    (ccb <= ngroups && /* <=== rjh: redundant test */
    ((g[cca].length == g[ccb].length &&
      g[cca].fseat < g[ccb].fseat) ||
       g[cca].length > g[ccb].length)))
  {
    child = cca;
  }
  else
  {
    child = ccb;
  }
  return child;
}

static int rearrange(int idx)
{
  int child = selectchild(idx);

  if ((g[idx].length == g[child].length &&
       g[idx].fseat > g[child].fseat) ||
      g[idx].length < g[child].length)
  {
    swap(&g[idx], &g[child]);
  }
  idx = child;
  return idx;
}

struct Group pop(void)
{
  int idx = 1;
  swap(&g[1], &g[ngroups]);
  ngroups--;
  while(idx * 2 <= ngroups)
  {
    idx = rearrange(idx);
  }
  return g[ngroups + 1];
}

Notice how much simpler pop() is as a result of these changes. And the 
guts of the loop (now in rearrange()) is clearer (and therefore 
easier to debug) because, instead of doing two jobs, it's now doing 
one job - the job of selecting the child has been factored out into 
its own function. It was only in the course of refactoring 
rearrange() that I discovered the redundant test (see above comment); 
beforehand, it was buried in a sea of syntax.

<snip>

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

Richard Heathfield wrote:
) static int selectchild(int idx)
) {
)   int cca = idx * 2; /* Child Candidate A */
)   int ccb = cca + 1; /* Child Candidate B */
)  
)  
)  if(ccb > ngroups ||
)     (ccb <= ngroups && /* <=== rjh: redundant test */
)     ((g[cca].length == g[ccb].length &&
)       g[cca].fseat < g[ccb].fseat) ||
)        g[cca].length > g[ccb].length)))
)   {
)     child = cca;
)   }
)   else
)   {
)     child = ccb;
)   }
)   return child;
) }

Why not factor out the comparison ?

  static int group_gt(Group a, Group b)
  {
    if (a.length > b.length) return 1;
    if (a.length < b.length) return 0;
    return (a.fseat < b.fseat);
  }

  ...

  if((child + 1) <= ngroups && group_gt(g[child + 1], g[child]))
    child++;

  ...

  if (group_gt(g[child], g[idx])
    swap(&g[idx], &g[child]);
   
  ...


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

In <slrnhamnd2.jut.willem@turtle.stack.nl>, Willem wrote:

<snip>
 
> Why not factor out the comparison ?

Good call.

<snip>

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

On Sep 12, 6:05=A0pm, Willem <wil...@stack.nl> wrote:
> For the record: the OP's code looks almost correct

The latest code that I have posted is 100% correct.

> there is a simple bug in it which I pointed out
> crossthread.

The code you suggested (http://groups.google.com/group/
comp.programming/browse_thread/thread/1ae9e3b35cb475b2/
e3a293e5099fcc46?lnk=3Dgst&q=3Dalbert#) in your final post does not crush
the bug.

On Sep 12, 6:36=A0pm, Willem <wil...@stack.nl> wrote:
> Richard Heathfield wrote:
> static int selectchild(int idx)

<snip>

I can't submit more than one source file, therefore I don't find
static helpful.

> =A0 static int group_gt(Group a, Group b)
> =A0 {
> =A0 =A0 if (a.length > b.length) return 1;
> =A0 =A0 if (a.length < b.length) return 0;
> =A0 =A0 return (a.fseat < b.fseat);
> =A0 }

Sorry - what does gt mean?

In 
<580fece6-e553-4190-91dc-81bee6b81159@b25g2000prb.googlegroups.com>, 
Albert wrote:

> On Sep 12, 6:36 pm, Willem <wil...@stack.nl> wrote:
>> Richard Heathfield wrote:
>> static int selectchild(int idx)
> 
> <snip>
> 
> I can't submit more than one source file, therefore I don't find
> static helpful.

<shrug> I find it helpful to adopt code patterns that minimise scope. 
The question, I suppose, is which interests you more: doing well in a 
competition that appears to have been held some years ago, or 
learning how to write good C programs.

> 
>> static int group_gt(Group a, Group b)
>> {
>> if (a.length > b.length) return 1;
>> if (a.length < b.length) return 0;
>> return (a.fseat < b.fseat);
>> }
> 
> Sorry - what does gt mean?

I'm tempted to say "guess" - it isn't difficult - but I'll give you 
this one: "greater than".

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

Well, I think I understand how to go about breaking up parts of the
algorithms I have to write for informatics problems. Thanks to
everyone who gave me advice I've tried to implement :)

I'm tired of AFL. I've received 100%, but there are plenty more
problems that need to be solved so I'll try to implement advice on
this thread in future source files.

Albert