Solved

Determining the final winners and all of its losers in a list of win/lose pairs

Posted on 2011-09-10
6
497 Views
Last Modified: 2012-05-12
I'm having trouble figuring out the logic for the following problem - the application is a de-duping process that has to merge the contents of the duplicates:

I have a list of pairs of winners and losers

e.g.

9962261 wins over 9962260
9962263 wins over 9962261
9962263 wins over 9962260

In this example,  9962263  is the winner, and wins out over 9962260 and 9962261.

imagine thousands of such contests expressed as records like this

how do i algorithmically end up with an array of the form

winner1, [list of losers]
winner2, [list of losers]
winner3,  [list of losers]

such that there is no winner that is also a loser.

My logic fails me.
0
Comment
Question by:metalaureate
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
6 Comments
 
LVL 110

Expert Comment

by:Ray Paseur
ID: 36516929
Just looking at this...

9962261 wins over 9962260
9962263 wins over 9962261
9962263 wins over 9962260

It would seem that you can take all the numbers in the right column and remove any instance of them from the left column.  That will tell you the winners who are not also losers.

Not sure I understand the other part.  How would you know whether 9962263 eliminated 9962260 before 9962261 eliminated 9962260.  That detail would seem to have an effect on whatever you wanted to put into the list of losers.
0
 
LVL 31

Expert Comment

by:Marco Gasi
ID: 36516930
I don't know if I'm able enough to help you, but sure I (and all other experts, I think) need to know how is formatted your original list: is it an ssociative array where the key is the winner and the value the looser? Or is it something else?

And the result you wish is, following your example, an array of array as the following one?

 9962263 => array(9962260, 9962261)
 9962261 => array(9962260)
 9962260 => array()

Cheers
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 500 total points
ID: 36516999
I don't know exactly what you are trying to do with this, but here is how I would most likely approach the problem.

Build a tree structure. Have one root node that originally has every person as a child node. Then, any time one person wins over another, move the loser off the root node and under the winner node. This way you don't have any duplication in the tree (each player is only one node) but you have the outcome of every match stored.
Also your idea of a list of losers under each undefeated winner is maintained in the entire tree under the winner.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 59

Expert Comment

by:Kevin Cross
ID: 36517231
How is the database laid out. Is it two columns: '9962261', '9962260' (where the right is the loser). Or is it one column: '9962261 wins over 9962260'?

Either way, I would implement a WHERE clause that only pulled values on the LEFT that do not appear on the RIGHT. For one field, you can use LEFT() with an INSTR, CHARINDEX, or similar type method depending on your database platform -- what is that by the way? -- then to compare to the other side, you can use similar functions to pull the right portion or use REGEXP if MySQL.

From there, you can use a GROUP BY and database specific tricks like GROUP_CONCAT or FOR XML to generate a common-delimited list for the losers.
0
 

Author Closing Comment

by:metalaureate
ID: 36517455
Ingenious. Thanks to all who helped.
0
 
LVL 110

Expert Comment

by:Ray Paseur
ID: 36517516
Please show us the data structure and how you programmed the solution, thanks. ~Ray
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Build an array called $myWeek which will hold the array elements Today, Yesterday and then builds up the rest of the week by the name of the day going back 1 week.   (CODE) (CODE) Then you just need to pass your date to the function. If i…
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
The viewer will learn how to count occurrences of each item in an array.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

756 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question