9 replies to this topic

[Dan Berliner]

I'm currently making a scrabble like game, the AI is the topic of this week. Basically the computer goes though and finds every possible place it can make a move. I handle this data with the below struct
[source lang="cpp"]struct Move{ int startx,starty, score, dir; std::string word;};[/source]

While the string and score are there for later reasons, any object with the same starting points and direction must be the same word. My algorithm for finding possible moves takes on duplicates so I'm using std::set to store it. To do this, however, I need a way to compare one Move from another. Dir ranges from 0-1, startx and starty both range from 0 to 15 (in theory they can be expanded, unlikely ever more than 100 though). Here is what I am currently using

[source lang="cpp"]bool operator<(const Move &a, const Move &b){ return (a.dir + a.startx*10 + a.starty*1000) < (b.dir + b.startx*10 + b.starty*1000);}[/source]

As long as the starting X position is under 100 I don't see any way to produce false-duplicates.

Is there a better way to do this?

[wqking]

if(a.dir > b.dir) {

    return false;

}

if(a.startx > b.startx) {

    return false;

}

if(a.starty > b.starty) {

    return false;

}

return true;

Not sure if it's want you want.
My code returns true only whan a's all fields are less than b's

[Dan Berliner]

That's roughly the same idea, I like your approach better. Thanks.

The exact order it sorts in is unimportant, it just needs some way to do so.

Edited by Dan Berliner, 16 December 2012 - 09:03 PM.

[SiCrane]

My code returns true only whan a's all fields are less than b's

This isn't a legal comparison for use with std::set. A valid comparison needs to be a strict weak ordering. One of the properties of a strict weak ordering is that if you have three objects A, B and C if A and B are equivalent and B and C are equivalent then A and C must also be equivalent. However, with this kind of comparison this property doesn't hold. One way to do this is to use a lexicographical comparison. Ex:

if (a.dir < b.dir) return true;
if (a.dir > b.dir) return false;
if (a.startx < b.startx) return true;
if (a.startx > b.startx) return false;
return a.starty < b.starty;

[Dan Berliner]

My code returns true only whan a's all fields are less than b's

This isn't a legal comparison for use with std::set. A valid comparison needs to be a strict weak ordering. One of the properties of a strict weak ordering is that if you have three objects A, B and C if A and B are equivalent and B and C are equivalent then A and C must also be equivalent. However, with this kind of comparison this property doesn't hold. One way to do this is to use a lexicographical comparison. Ex:

if (a.dir < b.dir) return true;
if (a.dir > b.dir) return false;
if (a.startx < b.startx) return true;
if (a.startx > b.startx) return false;
return a.starty < b.starty;

Interesting, thanks for sharing.

Edited by Dan Berliner, 16 December 2012 - 09:55 PM.

[Álvaro]

I do it like this (just a bit more compact):

if (a.dir != b.dir) return a.dir < b.dir;
if (a.startx != b.startx) return a.startx < b.startx;
return a.starty < b.starty;

EDIT: Or even this:

return a.dir != b.dir ? a.dir < b.dir
       : a.startx != b.startx ? a.startx < b.startx
       : a.starty < b.starty;

Edited by Álvaro, 16 December 2012 - 10:30 PM.

[BeerNutts]

EDIT: Or even this:
?
1
2
3
return a.dir != b.dir ? a.dir < b.dir
: a.startx != b.startx ? a.startx < b.startx
: a.starty < b.starty;

What's the point? It's much more complicated to read with no processing time benefit.

[Cornstalks]

If you're using C++11, there's std::tie and you can just do:

return std::tie(a.dir, a.startx, a.starty) < std::tie(b.dir, b.startx, b.starty);

[Álvaro]

What's the point? It's much more complicated to read with no processing time benefit.

Of course there is no processing time benefit, but I would argue that it is [slightly] less complicated.

`if' is used to change program flow conditionally, but here we are only using `if' to return one value or another. Using a single `return' and the ternary operator expresses this better. The structure of (condition1 ? value1 : condition2 ? value2 : value_else) is identical to a chain of if-else statements, and it's equally readable if you get used to it.

I concede that people are often more familiar with if-else than with chains of ternary operators, so perhaps in practice the other solution is better. But perhaps we can educate code readers a bit too...

Perhaps better formatting would make my code more clear. Wikipedia has this example of very readable use of concatenated ternary operators:

vehicle = arg == 'B' ? bus :
		  arg == 'A' ? airplane :
		  arg == 'T' ? train :
		  arg == 'C' ? car :
		  arg == 'H' ? horse :
					   feet;

EDIT: Let's try:

return a.dir	!= b.dir	? a.dir    < b.dir :
	   a.startx != b.startx ? a.startx < b.startx :
	 						  a.starty < b.starty;

Edited by Álvaro, 18 December 2012 - 01:31 PM.

[C0lumbo]

At the risk of this thread derailing into code style wars, I wouldn't like to debug any code with such excessive and chained use of the ternary operator - it's also a precedence minefield. (Or the suggestions where the 'return' ends up on the same line as the 'if' for that matter).