How much are homework assignments going for nowadays?  :-)

[snip]

At least you didn't ask someone to design a weapons system for you. :-)

I am trying to decide if this is a troll or a homework assignment.

Assuming that it's the latter, paying someone to do your homework for
you is only a short term solution. Part of doing homework is learning
_how_ to solve problems.

When people want help with homework, they usually ask a very specific
question, along with posting the code that they have tried to date.

If you are stuck on the problem as a whole, can't your tutor give you
some guidance on getting started ?

Sorry that I can't be more help, but we've all faced these problems
while learning, and learning how to overcome them is a required part of
the learning process.

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP      
Microsoft: The Standard Oil Company of the 21st century

I'm trying to figure out what badness is, here. Or a bad citizen.
So far I have learned that in English, "He's bad!" can be a statement
approving of someone's favorable qualities. OTOH, the political
pendulum is currently swinging to the watchers side, so we might
be witnessing another large scale surveillance project.

Could someone do me a favor and elucidate?

TIA,
Georg

When you're done, I want to run this program to measure the badness of
Michael Jackson.

How many groups might a given citizen belong too?  With 10**6 citizens,
there are potentially 2**(10**6) subgroups (subtract 10**6 if loners
are not considered groups).

I don't think this is homework; I think it's worse than that.  Some
unknown group of unknown people are asking us to write a database
containing actual person records in it.  We don't know what country
the database will run in, what people will have their records in it,
what is the definition of "badness", and, most importantly, we don't
even know what this unknown group of people is planning to do with the
"bad" people.

"strictly_mk", who are you anyway?  If you don't have the time to
learn Ada, that's fine and fair but could you please elaborate on the
more important questions I raised?

--
Ludovic Brenta.

Sounds good. I could do it for only $20 million, cash, in new $100 bills.

spam.vcf < 1K Download

  "Group" is misleading here.  Your "procedure Associate" leads to a
symmetric boolean N x N matrix where M(I,J) is True iff person I and
person J have ever been associated.  Finding the worst citizen in the same
"group" as citizen X means finding everyone X knows, then for each of X's
associates, finding all their associates, for each of those finding all
their associates, etc etc, and noting the worst person you come across.
If this is a brand new police database, then there are probably very few
known associations, so that's not too terrible in either storage or time.
  If you've been monitoring all associations between any two people over
the last many years, everybody is "associated" with several hundred
others, each of whom is associated with several hundred, and so forth.
Evemtually you'll find that, as in "six degrees of Kevin Bacon",
everyone except for a few cloistered nuns is associated with Kevin Bacon,
and thus with each other, so there are only two groups - those citizens
"associated" with Kevin Bacon and those in the nunnery.  Assuming there's
someone more dangerous than the nuns, Next_Member will simply be an
enumeration of all non-nuns.  Is that useful?

news:1122305318.728942.304120@f14g2000cwb.googlegroups.com...

Sorry I don't have enough time to write the whole thing write now, but
here's a start (maybe someone else will step in to fill in another routine):

with Ada.Unchecked_Deallocation;
package body POP is

  type
  RO0O is record  lll1 : ID;  ll1l : Rating; end record; type
  ROO0 is array( positive range <> ) of
  RO0O; type R0OO is access all ROO0;

  procedure RO00 is new Ada.Unchecked_Deallocation( ROO0, R0OO );

  R00O : R0OO;  R0O0 : Natural := 0;

   procedure Associate (Citizen_1, Citizen_2 : in ID) is
   begin
      null;
   end Associate;

   function More_In_Group return Boolean is
   begin
      return More_In_Group;
   end More_In_Group;

   function Most_Dangerous return ID is
   begin
      return Most_Dangerous;
   end Most_Dangerous;

   function Next_Member return ID is
   begin
      return Next_Member;
   end Next_Member;

   procedure Rate
     (Citizen : in ID; Badness : in Rating)  is  begin
    if R0O0 = 0 then R00O := new ROO0( 1 .. 100 ); end if;
    if R0O0 + 1 > R00O.all'length then
    declare R000 : R0OO; begin R000 := new
    ROO0( 1 .. R0O0 + 100 ); R000.all( 1 .. R0O0 ) :=
    R00O.all( 1 .. R0O0 ); RO00( R00O ); R00O :=
    R000; end; end if; R0O0 := R0O0 + 1;
    R00O( R0O0 ).lll1 := citizen; R00O( R0O0 ).ll1l := badness; end
    Rate;

   procedure  reset is
   begin
      null;
   end reset;

end POP;

Steve
(The Duck)

And me for only $15 million :)

Pascal.

--

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

  If you are a humanities major just trying to pass a required science
course, and just want something to barely "get by", forget priority queues
and databases and just use arrays.  If there aren't many citizens that
will work fine in both speed and storage.  If type ID is (<>); is for
instance "range 1 ..  100" just declare your arrays with ID as their
subscripts.  If ID is too big (eg, Integer), you can have a separate
lookup list to translate between ID and a (small) subscript value.
Even the "find all the associates of all the associates of ... of all
the associates of X can be done with a simple recursion and a check-off
list of citizens already looked at.
  In general, sitting back and asking "what information is required here?"
is a better start than "which of these complicated tools that I don't
really understand all that well, should I use?".  OTOH, be aware that more
than one dot-com company started with a simple implementation cooked up in
a dorm room that turned out not to scale up.

Great, bidding war. Don't listen to Pascal, he won't deliver the quality
you'll get from me.

OK, $14.9 million, but that's my final offer.

spam.vcf < 1K Download

Euros?

No $15 million is fine, but I'm ok for 15 million euros of course :)

Pascal.

--

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

It's cheaper to buy in Europe,

http://www.ecb.int/stats/exchange/eurofxref/html/eurofxref-graph-usd....

Are you sure you need a pointer.  Most Ada compilers won't have a problem
creating the even a large array in static memory:

http://en.wikibooks.org/wiki/Programming:Ada:Types:array

Do you really need "access all"

http://en.wikibooks.org/wiki/Programming:Ada:Types:access#Access_vs._...

And last not least: there is no "new" to be seen anywhere:

http://en.wikibooks.org/wiki/Programming:Ada:Types:access#Creating_ob...

Martin

--
mailto://krisc...@users.sourceforge.net
Ada programming at: http://ada.krischik.com

You could make Individual.Associate a packed array (1 .. 1_000_000) of
Boolean, set True if there's an Association .. though since
Association is symmetric as far as I can tell it might be better to
have a separate two-dimensional array for this.

I take it that ID is range 1 .. 1_000_000? if so you should index
Society by ID.

Why do you have pointers? you could just have an array of individuals.

Names are very important. "Pointer" is a very unhelpful name for the
concept you have in mind!

  type Individuals is array (ID) of Indivuals;
  Society : Individuals;

How are you going to know whether a given Individual exists? (has been
Rated, I think?)

--S

I'd probably use PragmARC.Skip_List_Unbounded for the collection of
rated innocent victims (appox O(log N) for insertion and lookup), each
having a list of associates. Then finding the highest rated is O(1), and
visiting each of her associates would be approx O(log N).

--
Jeff Carter
"Why don't you bore a hole in yourself and let the sap run out?"
Horse Feathers
49

  And visiting all the associates of each of those ...
IIRC Warshall's algorithm for transitive closure is O(n**3).
Is there a faster way?

news:1122475184.849564.159870@g44g2000cwa.googlegroups.com...

Now that you're asking for help, and not for someone to do it for you, as
you can see, you get a lot more positive response.

If the array is going to be fixed in size, why not just use:

  type Society is array( 1 .. 1000000 ) of Individual;

  Society_Buffer : Society;

  In my original response I used a pointer because I dynamically allocated
an array to store individuals.  When the array became full, I dynamically
allocated a new larger array, copied the values from the original array to
the new larger array and then deallocated the original array.  It is
certainly simpler to just go with a fixed maximum size.

  Just a note: One of the features I really like about Ada is the ability to
do record assignments, so this Rate function could be:

  Counter := Counter + 1;
  Pointer( Counter ) := ( Person => Citizen, Rating => Badness, Associate =>
null, Reported => False );

One way to handle the "associates" is to create an association code for each
individual.  When two citizens are associated, make the id's of the
associates the same.

You might, for example start out with an association id of 0 indicating no
association.  When the Associate procedure is called, find the location of
each of the citizens and handle each of the cases:
  If both associates have no association, create a new association id, and
assign it to both.
  If just one of the associates has a non-zero association id, assign it to
the other.
  If both of the associates have a non-zero association id (ie: A and B),
then change the association ID of all citizens that are currently B to A.

I am assuming that:
  if A associated with B and B associated with C it is implied that A
associated with C.

I hope this helps,
Steve
(The Duck)

I thought the requirement was only to visit all the associates of the
highest rated individual. If you have to visit associates of associates
of associates of ... then it becomes a little more time intensive.

--
Jeffrey Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail
E-mail: jeffrey_r_carter-nr [commercial-at]
         raytheon [period | full stop] com

Whoa, everyone seems to be going over the top, I think the solution
can be much simpler.

generic
    type ID is (<>); --some discrete type to be put here
package POP is
   --update database
  type Rating is new Integer range 0..255;
  procedure Rate (Citizen : in ID;
                  Badness : in Rating);
  procedure Associate (Citizen_1, Citizen_2 : in ID);
  --query the database
  function Most_Dangerous return ID;
  function Next_Member return ID;
  function More_In_Group return Boolean;
  --administrative
  procedure reset;
end POP;

Since the type ID is discrete, why not just use that as the array index type?

package body POP is
   Society : array (ID) of Rating := (others => Rating'First);
   Associacion : array (ID, ID) of Boolean := (others => others => False));
   pragma Pack (Association);

   Last_Reported : ID := ID'First;

   procedure Rate (Citizen : in ID;
                   Badness : in Rating) is
   begin
      Society (Citizen) := Rating;
   end Rate;

   procedure Associate (Citizen_1, Citizen_2 : in ID) is
   begin
      Association (Citizen_1, Citizen_2) := True;
   end Associate;

   function Most_Dagerous return ID is
      Result : ID := ID'First;
   begin
      for J in Society'Range loop
         if Society (J) > Result then
            Result := J;
         end if;
      end loop;
      return Result;
   end Most_Dangerous;

   function Next_Member return ID is
      J : constant ID := Most_Dangerous;
   begin
      if Last_Reported = ID'First then
         Last_Reported := J;
      end if;
      for K in ID'Succ (Last_Reported) .. Association'Last (2) loop
         if Association (J, K) then
            Last_Reported := K;
            exit;
         end loop;
      end loop;
      return Last_Reported;
   end Next_Member;

   function More_In_Group return Boolean is    
      J : constant ID := Most_Dangerous;
      Result : Boolean := False;
   begin
      for K in ID'Succ (Last_Reported) .. Association'Last (2) loop
         if Association (J, K) then
            Result := True;
            exit;
         end loop;
      end loop;
      return Result;
   end More_In_Group;

   procedure Reset is
   begin
      Society := (others => Rating'First);
      Association := (others => others => False));
      Last_Reported := ID'First;
   end Reset;
end POP;

Of course, the above solution is outrageously inefficient, both
memory- and CPU-wise.  Optimisations are left as an exercise to the
reader.

--
Ludovic Brenta.

Nice and clean but:

Most_Dangerous = 10
Last_Reported = 20
Citizens 5 and 6 are associated.
then re-rate Citizen 5 as even more dangerous than 10.
Citizen 6 will not be noticed by Next_Member or More_In_Group.

Associate as written is not symmetric - is that what's wanted?

association is not transitive - is that what's wanted?

I would also change type Rating to Rating_Levels and array Society to
Rating.  Then "if Rating(J) > " reads better than "if Society(J) > ".

I notice a couple of typos, but the compiler will point them out.

news:1122547648.069514.63520@g14g2000cwa.googlegroups.com...
In your original post you indiciated:
  "The procedure rest resets the database to its original state."

So, I think all you need to do is set your counts and indexes back to 0.

Steve
(The Duck)

  Remember that a symmetric array A(1 .. N, 1 .. N) can be stored in half
the space as a vector V(1 .. (N*(N+1))/2), where A(i,j) is at
V((max(i,j)*(max(i,j)-1))/2+min(i,j))