Re: AFL solved
- From: cri@xxxxxxxx (Richard Harter)
- Date: Sat, 12 Sep 2009 03:30:20 GMT
On Sat, 12 Sep 2009 02:33:37 +0000, Richard Heathfield
<rjh@xxxxxxxxxxxxxxx> wrote:
In <4aaad050.53519234@xxxxxxxxxxxxxxxxx>, Richard Harter wrote:
On Fri, 11 Sep 2009 02:44:53 -0700 (PDT), Albert
<albert.xtheunknown0@xxxxxxxxx> 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@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!
.
- References:
- AFL solved
- From: Albert
- Re: AFL solved
- From: Richard Harter
- Re: AFL solved
- From: Richard Heathfield
- AFL solved
- Prev by Date: Re: When will C have an object model?
- Next by Date: Re: C coding guidelines
- Previous by thread: Re: AFL solved
- Next by thread: Re: AFL solved
- Index(es):
Relevant Pages
|
Loading
