# 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 on other sites
I may not be understanding the question correctly, but could you not just go down the tree, counting what level you are on. The just use the path that has the most levels?

Matt Hughson

##### 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 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 on other sites
I have solved my problem! Thanks to all those who helped.
In the words of the n00b: "kthxbye".

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628301
• Total Posts
2981906

• 9
• 11
• 11
• 10
• 10