Qsort-ing structures

[Albert]

Hi:

I did a 4-hour programming contest this morning-early afternoon and I
had the following problem which I'll put in a nutshell, hopefully
that's enough to get even the vaguest idea as to what my code (when I
post it) was to intentionally do

--
You love playing Space Invaders. It's where ONE row of enemy bots are
on the top of the screen. You're on the bottom and may move only
horizontally. When you fire, you fire straight up till the bullet
destroys an enemy. You love the game so much that you stay all night
playing it. Therefore, you eventually get to the last and hardest
level. In this level, some of the screen is covered with polygons. If
the polygon happens to cover a particular column, firing at that
column won't do anything. So if the input tells you how wide and how
tall the screen is (I believe it was from 3 -> 10^7 for both
dimensions) and you assume that the whole top row is covered with
enemies, and in the input you're given the number of polygons and the
points of the corners of them, work out how many enemies you can
destroy on this static screen save your maneuvering of your bot.
--

What I ended up doing was creating a struct representing a polygon. It
stored the number of points needed to describe the polygon (which was
part of the input data), it had an array of all the x coordinate
values inputted for this particular polygon and stored also the
smallest and largest x value in the array. The reason I didn't store
the y coordinate is because it's not needed in my algorithm (which I
believe is correct, would have been fast enough had I managed to code
it properly...).

Once you've stored all the input into an array of ships (I declared my
type as struct ship {...} ships [10^5 + 2] you sort the ships[] from
ship with the lowest x coordinate to the highest (ie by the ship's sx
[smallest x] increasing).

Then, essentially you sweep from the leftmost ship to the rightmost
ship. You find the difference of each ship's smallest and largest x
coordinate and subtract it from the variable, nfire (the number of
enemies you can destroy which starts off as the width inputted) and at
the end of the algorithm you output nfire.

The catch is when one ship is in front of another. Or, one ship's x
coordinate is in between another ship's smallest and largest x
coordinate. In this case, subtracting differences of smallest and
largest values from nfire wouldn't work because there will surely be
test cases where the ships 'overlap'. So - that's why I wantED to sort
my ships array. Continually searching through each ship for similar x
coordinates would timeout. A maximum of 10^5 ships can be described
and such an algorithm would take O(nships^2) which is unusable,
considering the assumption that a computer can process approximately
10^8 (but really it should be 3 * 10^8 but we like powers of ten)
instructions per second (and the time limit in most problems in this
olympiad are 1 second). So I thought the inbuilt qsort() would work
but I couldn't get it to work.

Let's simplify the problem before I get the full problem statement
again (can't access it outside the competition times anymore until
sometime) and my code which I left saved on the school network.

struct ship {
int sx;
} ships[10^5];

fscanf()....//into ships.sx

qsort(ships, 10^5, //comparison function//);

How do I get qsort to sort the array of structures accordign to sx?

Thanks
Albert

 

[CBFalconer]

Once you've stored all the input into an array of ships (I
declared my type as struct ship {...} ships [10^5 + 2] you
sort the ships[] from ship with the lowest x coordinate to the
highest (ie by the ship's sx [smallest x] increasing).

You do realize, don't you, that 10^5 as a C expression is not
10000 but a much smaller number? ^ is not an exponentiation
operator in C. If you declared your array as somestruct[10^5],
you're going to have a massive array overflow if you read in
10000 data points.

Who, may I ask, is 'you'?

 

[Albert]

Let's simplify the problem before I get the full problem statement
again...[M]y code [was] saved on the school network*
[snip]

The 'full problem statement' and the code which I have since typed up
from scratch is at http://albert.xtheunknown0.googlepages.com/spaceinvaders

Note that the code currently deals with the input only. I've been
trying to divide this program into several functions and I'm trying to
get the design right for now.
I've been fiddling around with header files and #include's; I can't
get the files to all compile because I don't really understand how all
these declartions work across multiple files. Could you please suggest
as to how to split the current source code into files and how to
#include them in each of the files?

@richard: Thanks for the code; I got three out of 20 test cases
correct without a sort (and that O(n) algorithm has been putting me
off lately) since I had the correct algorithm, but strictly given non-
overlapping polygons. I was expecting to have a problem in coming up
with slow algorithms but instead I couldn't get a sort to work for a
correct AND a O(nlog(n)) algorithm!

@Burditt: Actually I didn't realise that during the contest. I think
that's why my results said (for around the first 10 cases) my program
generated either the incorrect answer or that it crashed...

@CBFalconer: Is that a rhetorical question?

*I saved my source files along with a temp copy of Dev-cpp portable in
the C:\ during the contest; logging off automatically wiped (and
wipes) any changes made on a school computer. I forgot to keep a copy
of my original source file on my USB :|

Thanks a lot,
Albert

 

[Albert]

When I try to compile each of the .c files at
http://albert.xtheunknown0.googlepages.com/spaceinvaders, I get errors
- why?

 

[Nate Eldredge]

When I try to compile each of the .c files at
http://albert.xtheunknown0.googlepages.com/spaceinvaders, I get errors
- why?

main.c should #include "setup.h". The other files compile fine for me.

What errors do you get, what compiler are you using, and how are you
running it? There might be something wrong in that process.

 

[Ike Naar]

When I try to compile each of the .c files at
http://albert.xtheunknown0.googlepages.com/spaceinvaders, I get errors
- why?

For me, it compiles fine (using gcc).
How do you compile it, and what errors do you get?

 

[Albert]

main.c should #include "setup.h".  The other files compile fine for me.

Added
#include "setup.h"
to main.c

What errors do you get what compiler are you using, and how are you

running it? There might be something wrong in that process.
gcc errchk.c
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

gcc main.c
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x3a): undefined reference to
`open_file'
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x48): undefined reference to
`setup'
collect2: ld returned 1 exit status

gcc setup.c
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0x5b): undefined reference
to `read_num'
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xa2): undefined reference
to `read_num'
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xb4): undefined reference
to `read_num'
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

 

[Nate Eldredge]

Added
#include "setup.h"
to main.c

running it? There might be something wrong in that process.
gcc errchk.c
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

Running `gcc' on a file without other arguments tries to compile that
file into its own program. None of those files constitutes a complete
program by itself, which is why this doesn't work.

Try

gcc -o myprog.exe errchk.c main.c setup.c

 

[Ike Naar]

gcc errchk.c
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

gcc main.c
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x3a): undefined reference to
`open_file'
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x48): undefined reference to
`setup'
collect2: ld returned 1 exit status

gcc setup.c
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0x5b): undefined reference
to `read_num'
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xa2): undefined reference
to `read_num'
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xb4): undefined reference
to `read_num'
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

Try this:
gcc main.c errchk.c setup.c

 

[Albert]

Try

gcc -o myprog.exe errchk.c main.c setup.c

I just did. Your suggestion worked. Thank you.

 

[Albert]

Now I need a
struct mship ms[MAXMSHIPS+1] that setup() and main() can access
instead of a local array that only setup() manipulates. How do I get
the external declarations and definitions right?

 

[Barry Schwarz]

Now I need a
struct mship ms[MAXMSHIPS+1] that setup() and main() can access
instead of a local array that only setup() manipulates. How do I get
the external declarations and definitions right?

No external declarations needed. Define ms in main and pass it as an
argument to setup. If main and setup are in different translation
units, define struct mship in a header and #include that header in
both source files.

 

[Albert]

Define ms in main and pass it as an argument to setup.

I've now done that.
In the first for loop in setup.c, will ms.left = INT_MAX;
become (ms+i)->left = INT_MAX?

Thanks
Albert

 

[Ben Bacarisse]

Define ms in main and pass it as an argument to setup.

I've now done that.
In the first for loop in setup.c, will ms.left = INT_MAX;
become (ms+i)->left = INT_MAX?

No need. I'd use the first form always.

 

[Albert]

In the first for loop in setup.c, will ms.left = INT_MAX;
become (ms+i)->left = INT_MAX?

No need.  I'd use the first form always.

Is it the same???

 

[Barry Schwarz]

Define ms in main and pass it as an argument to setup.

I've now done that.
In the first for loop in setup.c, will ms.left = INT_MAX;
become (ms+i)->left = INT_MAX?

Without any context (most of aren't going to bother remembering the
details of your post from days ago), the answer is who knows.

ms is defined to be *(ms+i) but simply substituting one for the
other runs afoul of precedence and associativity. The compiler is
smart to figure it out so that the expression ms.left will be
evaluated as (*(ms+i)).left. I think this is equivalent to your
expression (ms+i)->left. Whether the generated code tries to do it
this way is an implementation detail.

 

[Ben Bacarisse]

In the first for loop in setup.c, will ms.left = INT_MAX;
become (ms+i)->left = INT_MAX?

No need.  I'd use the first form always.

Is it the same???

Why don't you tell me what you think each one means. I find a diagram
helps, but drawing in Usenet posts is a pain.