Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Hierarchical Data Structures

by Sang (Acolyte)
on Mar 11, 2004 at 03:57 UTC ( [id://335698]=perlquestion: print w/replies, xml ) Need Help??

Sang has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to figure out the optimum approach for a pyramid game:

Player A can appoint 3 people below them, players B-D can each appoint 3 people below them, etc. with the end result being seven tiers and a maximum of 1093 players.

Each person accumulates points, calculated daily for 14 days, according to how many people are below them and, after earning at least 49 points, they 'win'. Each person can demote themselves to switch places with the person immediately below them. For the most people to win I need to calculate how many points are earned by each person and the the optimum rotation of positions.

Any suggestions on a good approach or module to learn for a beginner? I've looked at Tree:MultiNode but didn't seem quite what I needed...

Replies are listed 'Best First'.
Re: Hierarchical Data Structures
by gmax (Abbot) on Mar 11, 2004 at 08:08 UTC
    Each person accumulates points, calculated daily for 14 days, according to how many people are below them

    Tree::DAG_Node can help you to represent such structure quite easily. I've written an Introduction to Tree::DAG_Node where there is an example of such calculation made with the tree's methods.

    To get you started, here is a sample hierarchy with its graphic representation and the score calculation. Swapping places and calculating optimum strategies is left as an exercise for you :).

    #!/usr/bin/perl -w use strict; use Tree::DAG_Node; my $playerA = Tree::DAG_Node->new; $playerA->name('A'); $playerA->new_daughter->name('A1'); my $a2 = Tree::DAG_Node->new; $playerA->add_daughter($a2); $a2->name('A2'); $a2->new_daughter->name('A2a'); $a2->new_daughter->name('A2b'); $playerA->new_daughter->name('A3'); print map "$_\n", @{$playerA->draw_ascii_tree},"\n"; print $playerA->dump_names; my $playerB = Tree::DAG_Node->new; $playerB->name('B'); $playerB->new_daughter->name('B1'); my $b2 = Tree::DAG_Node->new; $playerB->add_daughter($b2); $b2->name('B2'); $b2->new_daughter->name('B2a'); $b2->new_daughter->name('B2b'); $b2->new_daughter->name('B2c'); my $b3 = Tree::DAG_Node->new; $playerB->add_daughter($b3); $b3->name('B3'); $b3->new_daughter->name('B3a'); my $b4 = Tree::DAG_Node->new; $b4->name('B4'); $b4->new_daughter->name('B4a'); $b4->new_daughter->name('B4b'); $b3->add_daughter($b4); $b3->new_daughter->name('B3b'); print map "$_\n", @{$playerB->draw_ascii_tree},"\n"; print $playerB->dump_names; $playerB->self_and_descendants, "\n"; print "A score: ", scalar $playerA->self_and_descendants, "\n"; print "B score: ", scalar $playerB->self_and_descendants, "\n"; print "B2 score: ", scalar $b2->self_and_descendants, "\n"; __END__ | <A> /--------+-------\ | | | <A1> <A2> <A3> /-----\ | | <A2a> <A2b> 'A' 'A1' 'A2' 'A2a' 'A2b' 'A3' | <B> /-----------+--------------------\ | | | <B1> <B2> <B3> /-----+-----\ /--------+--------\ | | | | | | <B2a> <B2b> <B2c> <B3a> <B4> <B3b> /-----\ | | <B4a> <B4b> 'B' 'B1' 'B2' 'B2a' 'B2b' 'B2c' 'B3' 'B3a' 'B4' 'B4a' 'B4b' 'B3b' A score: 6 B score: 12 B2 score: 4

    I would recommend this module also because the documentation is exceptionally clear and informative. I've used Tree::DAG_Node in several projects.

     _  _ _  _  
    (_|| | |(_|><
     _|   
    
Re: Hierarchical Data Structures
by kvale (Monsignor) on Mar 11, 2004 at 05:57 UTC
    The relationships between players is clearly a tree structure, but you didn't say why Tree:MultiNode isn't good for you...

    So I will suggest a hash based approach. Each player has a boss (except for the top player), three subordinates, and points. A suitable hierarchical data structure is like the following

    my %player; $player{1}{boss} = 0; # top player has no boss $player{2}{boss} = 1; # etc. $player{1}{slave}[0] = 2; $player{1}{slave}[1] = 3; $player{1}{slave}[2] = 4; $player{1}{points} = 42;
    Obviously, you will want to use loops to populate %players, the assignments above were just to be clear on the structure.

    Given this structure, you can determine points by iterating through all the players and collecting points from his slaves. To exchange positions, you smply swap bosses and slaves for the two positions.

    -Mark

Re: Hierarchical Data Structures
by NetWallah (Canon) on Mar 11, 2004 at 06:12 UTC
    Here is a basic outline for one way to do it:

    You can use Class::Struct to construct the basic "Player" object. Then the properties "Parent", and 3 "Child" player can each be assigned new Player objects. You can create traversal methods.

Re: Hierarchical Data Structures
by ehdonhon (Curate) on Mar 11, 2004 at 07:02 UTC

    Does player A have to appoint all 3 people below it, or can it choose to only appoint one or two?

    When play A swaps, does it have to be with player B, or does it have the choice of also swapping with players C or D? Can it then immediately swap with one of the grandchildren (which would mean that you can basically put every piece in any position any day)?

    After you have objects to represent all of this, how do you plan on solving it? It sounds to me like one of those problems that isn't going to be solvable with brute force.

      Any problem is solvable by brute force, given enough time ... for some definition of enough.

      --
      TTTATCGGTCGTTATATAGATGTTTGCA

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://335698]
Approved by kvale
Front-paged by cchampion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (2)
As of 2024-04-20 05:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found