AFL solved

[Albert]

Imagine the swap function has been implemented, making using namespace
std unecessary in this C99 code. And remember
http://groups.google.com.au/group/c...ad/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 = 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 == FALSE)
currlength++;
if (i == nseats || seats == true) {
if (currlength == 0)
continue;
ngroups++;
g[ngroups].length = currlength;
g[ngroups].fseat = i - currlength;
if (i == nseats && seats == 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;
}

 

[Bart]

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?

 

[Lew Pitcher]

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. ------

 

[Lew Pitcher]

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

 

[Bart]

In




....

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;
  }

} ....
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.

 

[Ben Bacarisse]

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>

 

[Bart]

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?

 

[Ben Bacarisse]

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.

 

[Bart]

Bart <[email protected]> writes:

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!


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.

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.

 

[Albert]

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 == 0)
currlength++;
if (i == nseats || seats == 1) {
ngroups++;
g[ngroups].length = currlength;
g[ngroups].fseat = i - currlength;
if (i == nseats && seats == 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 = 0;
for (i = 1; i <= nbookedseats; i++) {
fscanf(in, "%d", &x);
seats[x] = 1;
}
repinput();
handlebookings();
return 0;
}

 

[Albert]

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.)

 

[user923005]

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 == 0)
            currlength++;
        if (i == nseats || seats == 1) {
            ngroups++;
            g[ngroups].length = currlength;
            g[ngroups].fseat = i - currlength;
            if (i == nseats && seats == 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 = 0;
    for (i = 1; i <= nbookedseats; i++) {
        fscanf(in, "%d", &x);
        seats[x] = 1;
    }
    repinput();
    handlebookings();
    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 = *g;
*g = *h;
*h = 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.

 

[Albert]

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.

 

[Albert]

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.

Could you provide an example please?

 

[user923005]

Could you provide an example please?

The query:
http://www.google.com/search?hl=en&...riables+are+evil&rlz=1W1GGLD_en&aq=f&oq=&aqi=
had 74,400 hits, including these:

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

 

[Albert]

The query:http://www.google.com/search?hl=en&source=hp&q=global+variables+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?

 

[user923005]

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.

 

[Willem]

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

 

[Willem]

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

 

[Albert]

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=gst&q=albert#) in your final post does not crush
the bug.