Help me choose appropriate data structure

[bigbang]

Hi all,
I'm trying to implement some game logic. First i would like to give an
example.
We have 3 different colors of cards. In each color there are 504 cards
(numbered from 0 to 503).
Now each player is given some cards. The cards given to each player
shall be represented by a combination of following
a). Individual card number
b). Range of card numbers.
c) Note: each player will have cards belonging to only one color. one
player cannot have same color cards as another player.
eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
player 2 has : green cards (1-100, 301-305, 499)

I want to implement a structure which can represent the cards each
player has.

typedef struct
{
T_COLOR color;
int length; /*length of absolute card numbers */
int *num; /* array of standalone numbers, ie not represented by
ranges */
int num of range; /*length of number of ranges */
int *start; /* indicate start of each range */
int *end; /* indicate end of each range */
}

For examplelayer 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
This is represented in the above structure like,
{
color = YELLOW
length = 3;
num = [1,3,99]
num_of_range = 2
start = [20,200]
end = [30,310]
}


Adding some complexity on top of this is, i should be able to
dyanmically add and remove number of cards to each player. Again this
dynamic input is represented by
eg: Add the following cards for player 1 : Yellow cards (320, 401-419)
remove the following cards for player 2: green cards (40-50, 301)


I thought of implementing this in bitmaps. But memory is of concern
here (sometimes a player can have only one card, so pre-allocating a
bitmap of size 504 seemed overkill). Can someone comment on the
structure ? Is there a better way to implement these ?


Thanks

 

[Richard Bos]

We have 3 different colors of cards. In each color there are 504 cards
(numbered from 0 to 503).

eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
player 2 has : green cards (1-100, 301-305, 499)
Adding some complexity on top of this is, i should be able to
dyanmically add and remove number of cards to each player. Again this

I thought of implementing this in bitmaps. But memory is of concern
here (sometimes a player can have only one card, so pre-allocating a
bitmap of size 504 seemed overkill). Can someone comment on the
structure ? Is there a better way to implement these ?

If you have reason to believe that this can change to virtual cards of
thousands of colours, with thousands of values for each, maybe use a
linked list of struct range {int start; int end;} for each player. If
keeping the hands sorted is important, and you expect tens of thousands
of cards per colour, use a tree of some kind.
If, OTOH, you know that you will at most have a reasonable dozen of
colours, of less than a thousand cards each, a bitmap simply is not as
much overkill as it seems. Remember that it will probably keep the code
simpler, and therefore smaller.

Richard

 

[bart.c]

We have 3 different colors of cards. In each color there are 504 cards
(numbered from 0 to 503).
Now each player is given some cards. The cards given to each player
shall be represented by a combination of following
a). Individual card number
b). Range of card numbers.
c) Note: each player will have cards belonging to only one color. one
player cannot have same color cards as another player.
eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
player 2 has : green cards (1-100, 301-305, 499)

typedef struct
{
T_COLOR color;
int length; /*length of absolute card numbers */
int *num; /* array of standalone numbers, ie not represented by
ranges */
int num of range; /*length of number of ranges */
int *start; /* indicate start of each range */
int *end; /* indicate end of each range */
}

For examplelayer 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
This is represented in the above structure like,
{
color = YELLOW
length = 3;
num = [1,3,99]
num_of_range = 2
start = [20,200]
end = [30,310]
}


Adding some complexity on top of this is, i should be able to
dyanmically add and remove number of cards to each player. Again this
dynamic input is represented by
eg: Add the following cards for player 1 : Yellow cards (320, 401-419)
remove the following cards for player 2: green cards (40-50, 301)


I thought of implementing this in bitmaps. But memory is of concern
here (sometimes a player can have only one card, so pre-allocating a
bitmap of size 504 seemed overkill). Can someone comment on the
structure ? Is there a better way to implement these ?

Having separate representations for individual cards, and ranges, seems
overcomplex. For example if you have card 17, and add card 18, suddenly you
have a range. And vice versa.

There are any number of ways of representing an abitrary collection of the
numbers from 0 to 503. If I didn't need to use C, I would choose a language
that implemented Pascal-type sets:

type cards: 0..503; (or whatever the syntax happens to be);

cards a,b,c;
a=[1,3,20..30,50,99,200..310];

Now adding extra cards is easy:

a = a+[4..10,17..19,100] //assuming no duplicates allowed

Now a will be [1,3..10,17..30,50,99..100,200..310]

I don't think it's that hard to implement something similar in C

Personally I would just go with a bytemap of 504 bytes (char a[504]); the
0.5KB memory is of no consequence on most processors. Any anyway your data
structure, in the worst case, could use a lot more (eg. the set
[0,2,4,8,.... 502]).

 

[Denis McMahon]

For examplelayer 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
This is represented in the above structure like,
{
color = YELLOW
length = 3;
num = [1,3,99]
num_of_range = 2
start = [20,200]
end = [30,310]
}

so an array of 3 ints, and 2 arrays of 2 ints, plus 2 ints. And 1 int
for the colour.

That's 10 ints. 4 bytes per int? 40 bytes.

Add a few more cards and ranges, and you're soon over 64 bytes.

In addition, adding or removing a card has to check for any effect on
existing ranges, for example if taking a card out in the middle of
range, or creating of new ones. If you take a card out of a range, you
may break it into a card + range, or range + range. Adding a card might
extend a range, just be a new card, join two ranges, or fit between a
single card and a range (eg if you have 21, 23 - 27 and add 22). You
have to detect all of this and update data structures accordingly.

I thought of implementing this in bitmaps. But memory is of concern
here (sometimes a player can have only one card, so pre-allocating a
bitmap of size 504 seemed overkill). Can someone comment on the
structure ? Is there a better way to implement these ?

64 (8 bit) bytes = 512 bits gives you 504 card indicators and 8 bits for
colour, which could be 1 of 256 colours. And adding and removing a card
is as simple as setting or clearing a bit. 512 bits is, in most
architectures, likely to be an easily defined block using eg "unsigned
char * cards[16];" for an 8 bit char architecture.

I think it will be better in terms of both data size and code size in
the long run to use bitfields, any saving in data storage for small
numbers of cards is probably going to be offset by the increase in code
size to handle the additional complexity of managing the more complex
structures.

Rgds

Denis McMahon

 

[James Dow Allen]

I think it will be better in terms of both data size and code size in
the long run to use bitfields ...

Perhaps. I suppose you meant "bitmap" when you wrote "bitfield."

There are some other alternatives for various size/simplicity
tradeoffs. A general bitmap codec (probably overkill for OP's
needs) is available at
http://fabpedigree.com/james/sofa.c
(License would be needed for commercial use.)

James

 

[Keith Thompson]

I'm trying to implement some game logic. First i would like to give an
example.
We have 3 different colors of cards. In each color there are 504 cards
(numbered from 0 to 503).
Now each player is given some cards. The cards given to each player
shall be represented by a combination of following
a). Individual card number
b). Range of card numbers.
c) Note: each player will have cards belonging to only one color. one
player cannot have same color cards as another player.
eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
player 2 has : green cards (1-100, 301-305, 499)

[snip]

Is this homework?

 

[Kenny McCormack]

I'm trying to implement some game logic. First i would like to give an
example.
We have 3 different colors of cards. In each color there are 504 cards
(numbered from 0 to 503).
Now each player is given some cards. The cards given to each player
shall be represented by a combination of following
a). Individual card number
b). Range of card numbers.
c) Note: each player will have cards belonging to only one color. one
player cannot have same color cards as another player.
eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
player 2 has : green cards (1-100, 301-305, 499)

[snip]

Is this homework?

Suppose it is. Please explain why that is a problem (if, as I gather
from your tone, you think that it is).

If you work it through, you will see that homework is precisely what we
*should* be answering here in this newsgroup. I just don't see it as a
problem.

--

No, I haven't, that's why I'm asking questions. If you won't help me,
why don't you just go find your lost manhood elsewhere.

CLC in a nutshell.

 

[Malcolm McLean]

Hi all,
Can someone comment on the
structure ? Is there a better way to implement these ?

You have about 1500 cards. On a modern machine, memory efficiency
isn't a concern. The window manager will use far more memory
displaying results to the user than you use in storing the cards,
whatever sane representation you use.
The obvious structure to use is a flat list of cards, then dynamic
lists of indices giving the cards held by each player, in discard
heaps, and so on. This is because such a data structure is reasonably
fast, and intuitive.

However if you need extra space / storage efficiency then you need to
analyse how you index the cards. There are always tradeoffs between
ease of implementation, speed, and memory usage. For instance if space
is the only constraint, you can have a flat list of cards, compressed
in memory, and traverse the list each time you need to pull out a
card, decompressing on the fly. A non-compressed but compact flat list
is the next stage up, giving considerable improvements in ease of
implementation and access speed, but still potentially O(N) each time
you need to check whether a player has a card. However if N is only
1500, O(N) isn't too bad.

 

[Tom St Denis]

Suppose it is.  Please explain why that is a problem (if, as I gather
from your tone, you think that it is).

If you work it through, you will see that homework is precisely what we
*should* be answering here in this newsgroup.  I just don't see it as a
problem.

People should be working out their own homework that's the point. I
think most people would be ok if people tried to work out a solution
and THEN asked for advice. The OP seems [to me] to be borderline
homework answer seeking and legitimate question. Thing is the OP
really hasn't shown their code yet, just some small useless fragment
and then asking if there is a better way.

Thing is people like Keith or Richard have likely seen all forms of
homework questions float around here, which is why they're quick to
sniff it out.

Let me ask you something, what service do you suppose you're providing
if you do peoples homework and they don't ever learn anything?

Tom

 

[Malcolm McLean]

Let me ask you something, what service do you suppose you're providing
if you do peoples homework and they don't ever learn anything?

There's a difference, admittedly sometimes a fine one, between doing
the homework and telling them how to do it.

 

[Kenny McCormack]

Let me ask you something, what service do you suppose you're providing
if you do peoples homework and they don't ever learn anything?

Well, that's a very loaded question, but I will ignore most of its
underlying meaning for the moment. By the way, do you still beat your
wife??? (I'm here all week, tell your friends, try the veal...)

Anyway, the point is that the regs mentality, like the C standard, makes
perfect sense when viewed through the lens of the groupthink in this
newsgroup. But, when you remove that groupthink, you see at an instant
how absurd it all is. So, I won't bother trying to convince you -
because I give you credit that if you simply step back and view it like
a normal person (not a CLC reg) would, you'll see it very clearly. But
if you can't (or won't), then nothing I can say will change your view.

But consider this one point: If we assume that all of life is a learning
process - a view popular in the the CLC groupthink - that is, that
learning begins the day we are born (some say the most important
learning of our lives is ages 0-3), continues through the formal
schooling period (kindergarten, grade school, high school, college, grad
school, post grad), onto our first job, our second job and so on until
we die, then what is the difference between helping someone with a
problem they face in formal schooling vs. helping them with a problem
they face on the job? Aren't both forms of help helping them unfairly
vs. their peers?

 

[Tom St Denis]

Well, that's a very loaded question, but I will ignore most of its
underlying meaning for the moment.  By the way, do you still beat your
wife??? (I'm here all week, tell your friends, try the veal...)

It's not loaded. I'm asking you what's the value in doing other
peoples homework. You're maintaining a line that the "regs" [of which
you are one btw] are somehow doing these people a disservice by
sniffing out homework questions and calling the posters on it. I want
to know what disservice that is.

Anyway, the point is that the regs mentality, like the C standard, makes
perfect sense when viewed through the lens of the groupthink in this

I have never met ANYONE from clc. There is no "groupthink" here other
than those of us with half a clue realize there is merit in people
learning their craft [e.g. so they're not shit developers who then
doom humanity].

But consider this one point: If we assume that all of life is a learning
process - a view popular in the the CLC groupthink - that is, that
learning begins the day we are born (some say the most important
learning of our lives is ages 0-3), continues through the formal
schooling period (kindergarten, grade school, high school, college, grad
school, post grad), onto our first job, our second job and so on until
we die, then what is the difference between helping someone with a
problem they face in formal schooling vs. helping them with a problem
they face on the job?  Aren't both forms of help helping them unfairly
vs. their peers?

Well you are right that the learning never stops. But I would not
accept lame "Please discuss the merits of globals versus local
variables" style questions from someone out of school either.

The constructive people here asks questions like "here's a snippet of
code, can anyone help me find the problem with it?" whereas people
like the OP [and other people who ask "homework" questions] don't do
any of the initial legwork themselves. They just want the answer and
not the learning experience from it.

What's so wrong with taking a bit of personal responsibility.
Presumably you're asking questions in clc because you need/want to
learn C. So why not LEARN C as opposed to going through the motions
to pass an exam and then be yet another useless person with a degree?

 

[Malcolm McLean]

what is the difference between helping someone with a
problem they face in formal schooling vs. helping them with a problem
they face on the job?  Aren't both forms of help helping them unfairly
vs. their peers?

The schooling problem is an artifical one. It has been created by the
teacher so that the pupil, required to solve it, will in the process
learn about C. A work problem is nt artifical. It has arisen because
of the task at hand. Whilst the novice progammer may learn more by
solving the problem himself, it hasn't been specially designed so that
that will happen.

Of course students are always wanting certification rather than
education. It's a huge drawback to our current system. But solving
that one is far beyond the remit of a C programming newsgroup.

 

[Keith Thompson]

There's a difference, admittedly sometimes a fine one, between doing
the homework and telling them how to do it.

Which is why it's good to know whether a given question is homework
or not; it can strongly affect the nature of the answer. I still
try to provide some background along with the answer, but if it's
homework I'll try harder not to answer directly.

 

[Kenny McCormack]

Which is why it's good to know whether a given question is homework
or not; it can strongly affect the nature of the answer. I still
try to provide some background along with the answer, but if it's
homework I'll try harder not to answer directly.

Please explain why there is a qualitative difference between helping
someone "cheat" on "homework" vs. getting ahead at work unfairly.

 

[Gene]

Please explain why there is a qualitative difference between helping
someone "cheat" on "homework" vs. getting ahead at work unfairly.

I teach people for a living and have thought about this a lot. The
difference is the ethics of the social contract involved in learning
in the school setting. The student enters into the contract with the
object of learning. The teacher enters in order to help the student
learn.

The learning process requires assessment of student efforts for two
reasons: 1) to help the student by providing feedback on how he or she
is doing so appropriate adjustments of effort can occur and 2) to
record some kind of formal indicator (a grade or mark) useful for
others who need to know what the student knows. This is also part of
the social contract -- an information service provided by most
educational institutions through transcripts.

It's often the case - especially early in the learning process where
the concepts to be learned are simple for experienced people but hard
for the learner - that getting outside help hurts learning by -- in
addition to preventing some thought and other effort needed by the
studenty -- invalidating the whole assessment process.

If the student is paying his or her own way, you can make a great case
that 1) above is a non-issue. The student is shooting her or himself
in the foot. Who cares? Of course, if someone else is paying the bills
for the learning (if you are paying your kids' college tuition, for
example), then even 1) presents an ethical problem. If I'm paying
several thousand dollars (as I have done) for my kid to take a
beginning programming course at an Ivy League school, I don't want
USENET folks doing the homework problems so the teacher for whom I'm
paying good money is providing feedback on said USENET user's code
instead of my kid's.

The clearest problem however is with 2). Like or not, people can
obtain an unfair advantage in life by getting an unearned good grade.
In this sense, the outside help is obviously unethical.

The workplace is different because the objective isn't learning. Nor
do many workplaces provide information as a service regarding what
their employees know. Rather, work is about meeting the requirement
of the day. Unless the requirement is to solve a problem with no help
- maybe for IP reasons - getting help is part of the job. In fact, an
employee who can convince a USENET guru to solve an industrial problem
is someone I'd want on my team.

This is probably a personal blog about a philosophy for integrating
the Internet as part of education. Certainly our world, by the _end_
of a college education, we should be giving homework where getting
answers on USENET _is_ fine. The course I just taught to undergrad
seniors, for example, allowed _any_ reference information, including
the Internet, for all projects and the term end exam (all properly
documented, of course, and guidelines connecting level of help
received to grades were clear from the outset).

Unfortunately, though, there are educational tasks--gaining
fundamental concepts--that can't be completed unless communication
with others is circumscribed. The student has to get over those humps
in the road independently. A sports metaphor--that students seem to
get intuitively--is that one needs to learn to hit the ball in order
to play baseball or tennis. Until you get the basic skill on your
own, playing on teams is useless, and no fun, either.

 

[yugeswar deenoo]

I teach people for a living and have thought about this a lot.  The
difference is the ethics of the social contract involved in learning
in the school setting. The student enters into the contract with the
object of learning.  The teacher enters in order to help the student
learn.

The learning process requires assessment of student efforts for two
reasons: 1) to help the student by providing feedback on how he or she
is doing so appropriate adjustments of effort can occur and 2) to
record some kind of formal indicator (a grade or mark) useful for
others who need to know what the student knows.  This is also part of
the social contract -- an information service provided by most
educational institutions through transcripts.

It's often the case - especially early in the learning process where
the concepts to be learned are simple for experienced people but hard
for the learner - that getting outside help hurts learning by -- in
addition to preventing some thought and other effort needed by the
studenty -- invalidating the whole assessment process.

If the student is paying his or her own way, you can make a great case
that 1) above is a non-issue. The student is shooting her or himself
in the foot. Who cares? Of course, if someone else is paying the bills
for the learning (if you are paying your kids' college tuition, for
example), then even 1) presents an ethical problem. If I'm paying
several thousand dollars (as I have done) for my kid to take a
beginning programming course at an Ivy League school, I don't want
USENET folks doing the homework problems so the teacher for whom I'm
paying good money is providing feedback on said USENET user's code
instead of my kid's.

The clearest problem however is with 2).  Like or not, people can
obtain an unfair advantage in life by getting an unearned good grade.
In this sense, the outside help is obviously unethical.

The workplace is different because the objective isn't learning. Nor
do many workplaces provide information as a service regarding what
their employees know.  Rather, work is about meeting the requirement
of the day. Unless the requirement is to solve a problem with no help
- maybe for IP reasons - getting help is part of the job.  In fact, an
employee who can convince a USENET guru to solve an industrial problem
is someone I'd want on my team.

This is probably a personal blog about a philosophy for integrating
the Internet as part of education. Certainly our world, by the _end_
of a college education, we should be giving homework where getting
answers on USENET _is_ fine.  The course I just taught to undergrad
seniors, for example, allowed _any_ reference information, including
the Internet, for all projects and the term end exam (all properly
documented, of course, and guidelines connecting level of help
received to grades were clear from the outset).

Unfortunately, though, there are educational tasks--gaining
fundamental concepts--that can't be completed unless communication
with others is circumscribed.  The student has to get over those humps
in the road independently.  A sports metaphor--that students seem to
get intuitively--is that one needs to learn to hit the ball in order
to play baseball or tennis.  Until you get the basic skill on your
own, playing on teams is useless, and no fun, either.

Thank you all for the replies so far.
This is definitely not my homework.
I just had a dilemma whether to implement in bitmaps or linked lists
(or arrays).
Now i tend to favor bitmaps over linked lists (or arrays)
I will try writing some code to implement in bitmaps and post it in
this forum, for your comments.
Once again thank you all !

 

[bigbang]

On Jun 1, 3:32 pm, (e-mail address removed) (Kenny McCormack) wrote:

Thank you all for the replies so far.
This is definitely not my homework.
I just had a dilemma whether to implement in bitmaps or linked lists
(or arrays).
Now i tend to favor bitmaps over linked lists (or arrays)
I will try writing some code to implement in bitmaps and post it in
this forum, for your comments.
Once again thank you all !

Hi, sorry, i was posting the above message from my friends laptop and
he had his google id signed in already.

 

[bart.c]

Don't forget bytemaps (unless that's what you meant by arrays). They take a
bit more memory, but have some advantages over bitmaps (less fiddly to
implement, and the ability to store other attributes per-card such as
colour).

 

[bigbang]

#include<stdio.h>

#define MAX_CARD 503
#define MAX_CARD_BITMAP 64

typedef struct
{
unsigned char card_bitmap[MAX_CARD_BITMAP];
}LIST;

typedef struct _ABS_CARD_LIST
{
uint16 card;
_ABS_CARD_LIST *next;
}ABS_CARD_LIST;

typedef struct _CARD_RANGE
{
uint8 num_ranges;
uint16 *start;
uint16 *end;
}CARD_RANGE;


void init_cards(LIST *list)
{
int i;
for(i=0;i<MAX_CARD_BITMAP;i++)
{
list->card_bitmap = 0;
}
}

void add_card(LIST *list, uint16 card)
{
if(card > MAX_CARD) { assert(0); }
list->card_bitmap[card>>3] |= 1<<(card&7);
}


void add_card_list(LIST *list, ABS_CARD_LIST *card)
{
ABS_CARD_LIST *temp = card;
while(temp)
{
add_card(temp->card);
temp = temp->next;
}
}

void add_card_range(LIST *list, CARD_RANGE *range)
{
int i;
uint16 j;
for(i=0;i<range->num_ranges;i++)
{
for(j=range->start;j<range->end;j++)
{
add_card(j);
}
}
}

This is my first draft version of code. The goal here is to add either
absolute list of card numbers (eq. 1,5,100,203) or numbers in range
(eg, 100-200, 300-400) to a final list of cards. This final list is
represented by bitmaps.
I'm just a beginner. So pardon me if i have done some mistakes.