Sign in to follow this  
Julian Spillane

Some algorithm logic questions...

Recommended Posts

Hey all. This question is a bit of an elaboration on my previous one. Well, it's related, anyhow. I was commissioned to code the selecting "AI" for an individual's dominos game. Initially he wanted, from an arbitrary hand, the computer to choose the chain with the highest score attached to it. I got that working beautifully, and then he changed his mind. He now wants the longest possible train of dominos that can be made from a specific hand. Now I spent quite a while racking my brain on how to tackle this, and I eventually decided to store it all in a tree structure like so: (0, starting value) (start, 2) (start, 5) (start, 3) (2, 7) (2, 1) (7,4) etc. Anyways, I had no trouble populating the tree with the right logic and whatnot, but I am now finding it impossible to determine which branching would yield the longest chain. Now obviously in this case it would be (0,n)(n,2)(2,7)(7,4), but I don't know how I'd do that programmatically. I can't use any of the traditional traversal algorithms, as that would really just get me nowhere. Any suggestions on how I can solve this problem? If it involves scrapping the tree idea, then I'm game. I'm just stuck in a bit of a mental rut, and I need some other coders' opinions to jump start me back into it.

Share this post


Link to post
Share on other sites
...wow...I kind of thought of working with that method, but I haven't slept well in days, so I'm pretty much a human zombie. Now, what do you think would be the best way of keeping track of the number of levels? Storing it in the node and then incrementing by one with each addition?

Thanks a lot, by the way.

Share this post


Link to post
Share on other sites
Alright, I'm getting there, but I'm still having a little bit of a logical problem. Here's my code, if it's at all helpful:

Pair class

class tPair
{
public:
int index;
int x;
int y;
int imageNum;
int prevX;
int prevY;

tPair(int one, int two, int three, int four, int five) { x = one; y = two; imageNum = three; prevX = four; prevY = five;}
tPair() {}
inline void Swap() { int temp = x; x = y; y = temp; }
};


Populate the tree

class CHasStartValue
{
public:
CHasStartValue(int iStart) : m_iStart(iStart){}
bool operator() (tPair val) const
{
if(val.x == m_iStart || val.y == m_iStart)
return true;
return false;
}
private:
const int m_iStart;
};

void PopulateTree(CTree<tPair>* tree, std::vector<tPair>* vHand, int iStart)
{
bool bFinished = false;

while(bFinished == false)
{
CTree<tPair>* temp = new CTree<tPair>;

tPair tempPair;

std::vector<tPair>::iterator tempIt;

tempIt = std::find_if(vHand->begin(), vHand->end(), CHasStartValue(iStart));

if(tempIt >= vHand->end())
bFinished = true;
else
{
if((*tempIt).x == iStart || (*tempIt).y == iStart)
{
if((*tempIt).x == iStart)
{
temp->m_data.x = (*tempIt).x;
temp->m_data.y = (*tempIt).y;
}
else if((*tempIt).y == iStart)
{
temp->m_data.x = (*tempIt).y;
temp->m_data.y = (*tempIt).x;
}

temp->m_pParent = tree;
temp->m_iLevel = tree->m_iLevel+1;

temp->m_data.prevX = (*tempIt).prevX;
temp->m_data.prevY = (*tempIt).prevY;
temp->m_data.imageNum = (*tempIt).imageNum;

tree->m_pChildren.push_back(temp);

vHand->erase(tempIt);

for(int i = 0; i < tree->m_pChildren.size(); i++)
{
PopulateTree(tree->m_pChildren[i], vHand, temp->m_data.y);
}
}
}

}
}


void BestPath(CTree<tPair>* tree, std::vector<tPair>* path)
{
static int iHigh = -1000;

path->push_back(tree->m_data);

for(int i = 0; i < tree->m_pChildren.size(); i++)
{
if(tree->m_pChildren[i]->m_iLevel > iHigh && (tree->m_pChildren[i]->m_data.x == tree->m_data.y || tree->m_pChildren[i]->m_data.y == tree->m_data.y))
{
iHigh = tree->m_pChildren[i]->m_iLevel;
BestPath(tree->m_pChildren[i], path);
}
}
}


Now, the problem is that it now sometimes returns the best data set, but other times it doesn't. The problem lies in my BestPath function, I know, but I don't know how to solve it.

Using exact data, this is what's happening:

(0,2)(0,3)(0,4)(0,5)(0,6)(0,7)(6,8)(7,9)(7,10)(8,12)

Now, the longest path should be (0,6)(6,8)(8,12). I get (0,2).
The reason being is that it hits that path first. But I can't quite seem to work out the logic behind it right now. I'm a little stumped as to where to go from here.

Any help would be greatly appreciated. Thank you.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this