4
$\begingroup$

For the problem I'm considering, I'm looking at a sport (it's baseball) where:

  • Two teams play a game against each other, head to head.
  • Each team has a finite, integer score (called "Runs") at the end of the game; this value is >= 0.
  • Games cannot end in a tie. We can assume the algorithm will not have to handle input with tie games.

Given as input, a list of Games with the following data:

  • Game ID (usually a number, or date on which game was played)
  • Final number of runs scored by "our" team - hereafter RS (Runs Scored)
  • Final number of runs scored by "opponent" team - hereafter RA (Runs Allowed)

And given these terms:

  • A "Win" is defined as RS > RA.
  • A "Loss" is defined as RA > RS.
  • Note: Due to the impossibility of tie games, every game will either be a Win or a Loss for "our" team.

My goal is to design an algorithm that will redistribute whole RS values from one game to another until a maximum number of possible Wins is found for our team. A single game's RS value can be substituted for another game's RS value, but the algorithm cannot take "partial" amounts of RS from one game and distribute them among multiple games.

In the process of "donating" game A's RS (in its entirety) to another game B, you must then decide:

  • Which other game C should donate its RS to game A?
  • Which other game D should receive the original RS from game B?

In intuitive terms, the goal is to distribute the scores so that games are won by the narrrowest of margins, and lost by the widest of margins.

The algorithm cannot stop until every game meets one of the following conditions:

  • The game has neither donated nor received another game's RS (the game's original score stands as-is.)
  • The game has received an RS value from another game; it is the only game that has received that game's RS value; it has donated its RS value to another game; and that recipient is the only game to have received this game's original RS.
    • In other words, every original RS value must be used for exactly one game.

Additional descriptions of how the algorithm should work:

  • Input bounds: The algorithm should run in a reasonable amount of real time on modern computers for data sets up to 162 games. There's no need to be able to handle more games than that with any sort of reasonable performance. Basically, it needs to run in a human scale of time. An hour is fine; a week is stretching it. Anything longer is just too long.
  • "Equivalent" or "redundant" donations should be detected and avoided. In other words, if a given exchange of RS does not improve the overall number of wins of the team, then the exchange should not have occurred. Examples: Avoid exchanging RS when the "from" and "to" RS values are equal. Also avoid exchanging RS when it just makes one game go from a loss to a win, but another game to go from a win to a loss.
  • If there are multiple equivalent solutions to the problem (e.g., due to duplicate RA/RS pairs across several games) that have the same number of substitutions and wins, we'll just choose one arbitrarily. There's no value to the order of the wins or losses in the list.
  • An algorithm with analogous rules but shuffling around RA would probably work too, but I arbitrarily chose shuffling RS.

Here is some sample data:

  • Game 1: RS 3, RA 4 (L)
  • Game 2: RS 9, RA 1 (W)
  • Game 3: RS 6, RA 7 (L)
  • Game 4: RS 2, RA 1 (W)
  • Game 5: RS 0, RA 2 (L)
  • Game 6: RS 8, RA 10 (L)
  • Game 7: RS 3, RA 8 (L)

Wins: 2. Losses: 5.

One way to use the available RS values to maximize wins is:

  • Game 1 <- Game 3. RS 6, RA 4 (W)
  • Game 2 <- Game 7. RS 3, RA 1 (W)
  • Game 3 <- Game 6. RS 8, RA 7 (W)
  • Game 4 unchanged. RS 2, RA 1 (W)
  • Game 5 <- Game 1. RS 3, RA 2 (W)
  • Game 6 <- Game 5. RS 0, RA 10 (L)
  • Game 7 <- Game 2. RS 9, RA 8 (W)

Wins: 6. Losses: 1.

What I think is the hard part: There may be several solutions that have the same win/loss record, but we want the one that involves the greatest number of "unchanged" games out of all possible solutions with the same (maximal) win/loss record. This is basically what I mean by avoiding needless juggling around of RS.

A few observations about the dynamic of the scores that may or may not need to be in the algorithm's logic:

  • Sometimes you do want to donate a score from a winning game. In the example, we sent the 9 RS from Game 2 to Game 7, causing us to win Game 7, 9 to 8. Then the 3 RS from Game 7 were enough to win Game 2, 3 to 1.
  • If you do not even have an RS value large enough to exceed a given RA, you probably want to take the lowest available RS and tack it to that game, because you can't win no matter what. In our example, we took the 0 RS from Game 5 game and put them in Game 6, then sent Game 6's original 8 RS to Game 3 to convert Game 3 from a loss to a win.
  • There is no requirement that the RS have to be swapped. In the example, Game 3 gets its new RS from Game 6, but Game 6 gets its new RS from Game 5. Then Game 5 gets from Game 1, and Game 1 gets from Game 3. This completes the "cycle" in a sense: now we have a cyclic digraph. That's the "end state". If it's acyclic (excepting nodes that are unchanged from their original score), our algorithm is wrong.

I've been hacking on this for a few hours here. I'm leaving the code up in a static, usable state with correct input data and string parsing, but the algorithm that builds the results is most certainly deficient in a number of ways, not the least of which is the unnecessary substitutions.

Questions

  • I'm looking for a way to analyze/frame this problem more clearly so that it's easy to understand how to implement it.
  • Is this just an analogue of another mathematically-equivalent problem with a textbook solution? If so, elaborate.
  • What are the best data structures to set up the problem and organize the data? I've looked at lists, stacks, and digraphs so far, but I haven't found any clear winner yet. I even thought about recursion and using two lists (one for "donors" and one for "orphaned games" needing an RS) at one point, but I wasn't able to figure out what to do in all situations.
  • When looking for the "best" (fewest number of substitutions) solution, is it possible to efficiently find this solution, or do you have to compute every possible solution set with the maximum wins and then calculate which one has the minimum substitutions?
$\endgroup$
  • $\begingroup$ There are a lot of questions here. Usual rule is one question per post, and I get that two separate posts with all description that differ only by question at the end is not way to go either, but this platform doesn't work well with 4 big questions. Maybe you could merge first two into one and post (search) about computation independently? After framing the task in some terms (possibly equivalent problem) the method of evaluation would emerge? The third question should be answered with first one. $\endgroup$ – Evil Apr 29 '18 at 19:39
1
$\begingroup$

The usual rule here is to ask one question per post. I'll explain how to formalize this problem and suggest an efficient algorithm for solving the problem. Here is a formalization of the problem:

Given: arrays $A[1..n]$, $B[1..n]$
Goal: find a permutation of $A$, call it $A'$, that maximizes the number of indices $i$ such that $A'[i] > B[i]$.

This can be viewed as an instance of bipartite matching, a problem which has efficient algorithms. In particular, draw a bipartite graph with an edge from vertex $i$ to vertex $j$ if $A[i] > B[j]$. Now the maximum matching in this graph corresponds to a permutation of $A$ that yields the maximum number of wins. Thus you can use standard algorithms for bipartite matching, e.g., Hopcroft-Karp.

Alternatively, I think you can use a greedy algorithm. Sort the arrays $A$ and $B$ into decreasing order. Look at the first element of $A$, namely $A[1]$. If $A[1] > B[1]$, then match up $A[1]$ and $B[1]$ and discard both $A[1]$ and $B[1]$, and continue (next comparing $A[2]$ to $B[2]$). Otherwise, discard $B[1]$ and continue (next comparing $A[1]$ to $B[2]$). This involves an iterative scan through the sorted arrays. I think this should yield an optimal solution, and it is much easier to implement and more efficient too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.