16
\$\begingroup\$

Consider a zero-sum game with 2 contestants. Each round, each contestant chooses, independently of each other, one of \$n \ge 2\$ different choices. Depending on the two chosen choices, one player is awarded an amount from the other player's pot. For example, the following table shows the gains (positive integers) and losses (negative integers) for Player 1 for each of \$9\$ possible choices:

$$\begin{array}{c|c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses B} & \text{Player 1 chooses C} \\ \hline \text{Player 2 chooses A} & 1 & 2 & 2 \\ \hline \text{Player 2 chooses B} & -2 & 1 & 2 \\ \hline \text{Player 2 chooses C} & 3 & -1 & 0 \\ \end{array}$$

For example, if Player 1 chooses \$A\$ and Player 2 chooses \$C\$, Player 1 gains \$3\$ and Player 2 loses \$3\$.

However, this table is needlessly complex. We can see that, assuming both players are playing to win, some choices are always suboptimal. For example, Player 1 would never choose \$B\$. No matter what Player 2 chooses, Player 1 choosing \$C\$ will produce a result that is either better or equal to \$B\$, as each element in \$C\$ is greater than or equal to its corresponding element in \$B\$. Therefore, we can say that \$C\$ dominates \$B\$, and we can remove \$\text{Player 1 chooses B}\$ from our matrix:

$$\begin{array}{c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses C} \\ \hline \text{Player 2 chooses A} & 1 & 2 \\ \hline \text{Player 2 chooses B} & -2 & 2 \\ \hline \text{Player 2 chooses C} & 3 & 0 \\ \end{array}$$

Additionally, we can see that Player 2 would never choose \$A\$ over \$B\$, as their payoff is always higher or equal from \$B\$ than it is from \$A\$, as each value in \$B\$ is less than or equal to it's corresponding element in \$A\$. So if Player 1 chooses \$A\$, then Player 2 either loses \$1\$ (\$A\$), gains \$2\$ (\$B\$) or loses \$3\$ (\$C\$). If Player 1 instead chooses \$C\$, then Player 2 either loses \$2\$ (\$A\$), loses \$2\$ (\$B\$) or gains \$0\$ (\$C\$). In either case, Player 2 would choose \$B\$ over \$A\$, as their result would never be worse when choosing \$B\$.

Therefore, we can say that \$B\$ dominates \$A\$, and we can remove \$\text{Player 2 chooses A}\$ from the matrix:

$$\begin{array}{c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses C} \\ \hline \hline \text{Player 2 chooses B} & -2 & 2 \\ \hline \text{Player 2 chooses C} & 3 & 0 \\ \end{array}$$

Here however, no more choices dominate. This is our final matrix, and would be the output for this input.


You are to take a rectangular matrix \$n\times m\$, where \$n, m \ge 2\$, and output the same matrix with all dominated options removed. You may also take the matrix transposed and/or with reversed signs from the examples provided in the question.

The matrices will only contain integers between \$-9\$ and \$9\$ (inclusive). You may also take \$n\$ and/or \$m\$ as input if you wish. The matrix is not guaranteed to contain any dominated options. The matrix may be reduced to a \$1\times1\$ matrix, at which point there are no more dominated options.

You may input and output in any convenient format. If there is more than one valid output, you may output any valid one. This is so the shortest code in bytes wins.

Test cases

Done by hand, don't hesitate to point out mistakes or suggest more

Input
Output
Explanation

[[ 1  2  2]
 [-2  1  2]
 [ 3 -1  0]]
[[-2  2]
 [ 3  0]]
Column C dominates Column B, Row B dominates Row A

[[ 2  1  3  3]
 [ 0  0 -1  0]
 [ 1  1  0  0]]
[[0]]
Column A dominates B, Column D dominates C, Row B dominates Rows A+C, Column B dominates Column D (or vice versa)

[[ 2  0  4  1  2]
 [-1  6  0 -3  3]
 [ 0 -2  1 -1  1]
 [ 4 -2  1  2  3]]
[[1]]
Column E dominates Column D, Row C dominates Row D, Column E dominates Column A, Row C dominates Row A, Column E dominates Column E, Row C dominates Row B, Column E dominates Column B

[[ 7 -3 -5 -9 -8 -2]
 [ 6  7  6 -1  2  0]
 [-5 -8  3 -1 -8 -8]
 [-8  8  1  0  9 -2]
 [-3  0 -1 -4  8  1]
 [-2  2 -4  3 -7 -2]
 [ 4  8  1  8 -9 -9]
 [-1 -6 -4  1  9  5]]
[[ 7 -3 -5 -9 -8 -2]
 [-5 -8  3 -1 -8 -8]
 [-8  8  1  0  9 -2]
 [-3  0 -1 -4  8  1]
 [-2  2 -4  3 -7 -2]
 [ 4  8  1  8 -9 -9]
 [-1 -6 -4  1  9  5]]
Row C dominates Row B

[[  4 -6  2  ]
 [ -2 -5 -9  ]
 [  6 -2 -2  ]
 [  8  0  7  ]
 [ -9  4  2  ]]
[[ 4 -6  2]
 [-2 -5 -9]
 [-9  4  2]]
Row C dominates Row D, Row B dominates Row C

[[ 9 -7]
 [ 2  4]]
[[ 9 -7]
 [ 2  4]]
No rows or columns dominate

[[ 2  2  2]
 [ 2  3  2]
 [ 2  2  2]]
[[2]]
 Column B dominates Columns A+C, Row A dominates Rows B+C

[[ 1  4]
 [ 2  0]
 [ 1  4]]
[[ 2  0]  or [[ 1  4] 
 [ 1  4]]     [ 2  0]]
 Rows A and C are equal so we remove one of them. Either output is OK, but removing both rows isn't.

Note that for the 7th test case, there are many different ways to get to the final version

\$\endgroup\$
9
  • \$\begingroup\$ About the order: In the 2nd test case, if the 3rd column is put in the first position, my answer would return [[-1]] instead of [[0]]. So, either the order does matter, either my answer is wrong. A third option is that [[-1]] and [[0]] are both acceptable answers for these 2 matrices. \$\endgroup\$
    – Arnauld
    Apr 3 at 21:30
  • 4
    \$\begingroup\$ I have now strong reasons to suspect that order does not matter. A full proof won't fit in a comment, but the idea is that deleting a dominated row (or column) will not prevent any move that would have been possible without the deletion. If I delete row \$b\$ which is dominated by row \$a\$, and later row \$c\$ would be dominated by \$b\$, then it would also be dominated by \$a\$ and can thus be removed. Column domination is not affected by removing rows. \$\endgroup\$
    – Delfad0r
    Apr 3 at 22:01
  • 1
    \$\begingroup\$ I think the removal order can technically matter if the matrix has, say, two equal rows that aren't consecutive, so that after removal the remaining one can be in two different places. But, this only changes things up to a permutation. By the way, I think some test cases of a situation like this would be good, to check that the two equal rows aren't both removed. \$\endgroup\$
    – xnor
    Apr 3 at 22:14
  • 1
    \$\begingroup\$ @ChartZBelatedly I added a test case. Is this how you want it to work? \$\endgroup\$
    – xnor
    Apr 3 at 22:21
  • 1
    \$\begingroup\$ @Delfad0r Oops, nice catch, fixed it I think. \$\endgroup\$
    – xnor
    Apr 3 at 22:26
5
\$\begingroup\$

J, 43 41 40 39 bytes

f=.(#~1=1#.]*/ .>:|:)@~.
f&.:-&.|:@f^:_

Try it online!

tldr how

Create a function f to filter out dominated rows.

Apply plain f, followed by f "under" a negative transpose, until we reach a fixed point.

\$\endgroup\$
4
\$\begingroup\$

Jelly,  22  21 bytes

Qµ>Ạ€TLʋ€’ỊTịNZ
Ç⁺$ƬṪ

Try it online! Or see the test-suite.

How?

Ç⁺$ƬṪ - Link: matrix
   Ƭ  - collect up inputs to this until no change:
  $   -   last two links as a monad:
Ç     -     call Link 1 (see below)
 ⁺    -     repeat that
    Ṫ - tail

Qµ>Ạ€TLʋ€’ỊTịNZ - Link 1: matrix
Q               - de-duplicate (since one of any repeats wants keeping)
 µ              - start a new monadic chain, call that X
         ’      - with a decremented version of X, say Z, on the right:
       ʋ€       -   for each row in X:
  >             -     (row) greater than (Z) (vectorises)
   Ạ€           -     for each comparison: all truthy?
     T          -     truthy indices (i.e. indices in X which dominate row,
                                      including the index of row itself)
      L         -     length
          Ị     - insignificant? (vectorises) (i.e. 1 if no other row dominates, else 0)
           T    - truthy indices
            ị   - index into:
             N  -   negated (X)
              Z - transpose

As a single Link (21):
Qµ>Ạ€TLʋ€’ỊTịNZµ$⁺$ƬṪ
...or:
Qµ>Ạ€TLʋ€’ỊTịNZµ$Ƭm2Ṫ

\$\endgroup\$
3
\$\begingroup\$

Haskell, 106 101 100 bytes

  • -5 bytes thanks to kops.
until=<<((==)<*>)$g.g
g m=transpose.map(map(0-))$nub m\\(m>>=tail.mapM(\i->[i..9]))
import Data.List

Try it online!

The relevant function is until=<<((==)<*>)$g.g, which takes as input a matrix in the format described in the statement (not transposed and without flipped signs).

Very slow, but hey, we are codegolfing! See below for a (much) more efficient version.

How?

Most of the work is done by g. This function takes a matrix m as input and returns the matrix obtained after "half an operation". To be more specific, g takes m, removes dominated rows, then transposes m and flips all the signs. These last two operations are basically equivalent to swapping the roles of Player 1 and Player 2. It's not hard to see that applying g twice performs a full iteration: dominated rows and columns are removed, the two transpositions cancel out, and so do the two sign flipping. Let's now look at the code.

g m=                            -- the function g takes a matrix m and returns
    transpose.                  -- the transpose of
    map(map(0-))$               -- the matrix obtained by flipping the signs of
    nub m                       --   m with duplicate rows removed
    \\(                         --   to which we also remove
        m>>=                    --   any row obtained by taking a row of m (say r)
            tail.               --   and taking any but the first
            mapM(               --   list whose j-th entry
                \i->[i..9]))    --   lies between i and 9 (where i is the j-th entry of r)

nub m yields m with duplicate rows deleted; this is necessary since otherwise duplicate rows could potentially stick around forever. m>>=tail.mapM(\i->[i..9]) basically generates a list of all the possible rows (strictly) dominated by some row of m (this is obviously the slow part, since there can be up to \$\approx m\cdot19^n\$ such rows).


The anonymous function until=<<((==)<*>)$g.g (courtesy of kops) iterates g.g until the resulting matrix stops changing.

Haskell, 107 102 101 bytes, much faster

  • -5 bytes thanks to kops.
    until=<<((==)<*>)$g.g
    g m=transpose[(0-)<$>r|r<-nub m,all(or.zipWith(<)r)$m\\(r<$m)]
    import Data.List

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ This trick should save you 1 byte in your first solution, and 4 in your second (by reusing zipWith) \$\endgroup\$
    – kops
    Apr 3 at 21:58
  • 1
    \$\begingroup\$ Also, in both cases you can rewrite f as f=until((==)<*>g.g)(g.g) Try it online! (also lets you anonymize f if you want, once the import is gone) \$\endgroup\$
    – kops
    Apr 3 at 21:59
  • \$\begingroup\$ @kops Unfortunately the transpose trick wouldn't save me any bytes, since I need Data.List for nub and (\\) as well. Your second comment, however, is amazing, thank you! \$\endgroup\$
    – Delfad0r
    Apr 3 at 22:04
  • 1
    \$\begingroup\$ Ah, good point. I had a similar solution I was working on without \\ or nub (though I think the latter was a bug!) and I was just blindly merging my ideas with yours :) \$\endgroup\$
    – kops
    Apr 3 at 22:05
  • 1
    \$\begingroup\$ @kops Well don't stop working on your solution, I'm sure mine is still far from optimal! \$\endgroup\$
    – Delfad0r
    Apr 3 at 22:16
1
\$\begingroup\$

Charcoal, 40 bytes

F⊗L⁺θ§θ⁰≔E§θ⁰±EΦθ⬤θ⎇⁼μνπ⊙μ‹ρ§ξς§μλθIθ

Try it online! Link is to verbose version of code. Outputs using Charcoal's default format (each cell on its own line with rows double-spaced from each other). Explanation:

F⊗L⁺θ§θ⁰

Loop a large enough number of times (twice the number of rows and columns; probably overkill, so 4 bytes could be saved if this is the case).

Φθ⬤θ⎇⁼μνπ⊙μ‹ρ§ξς

Keep rows which, for each row, have at least one cell less than the corresponding cell from the other row, unless the two rows are equal, in which case keep the first of the duplicates.

≔E§θ⁰±E...§μλθ

Transpose and negate the filtered matrix. (Actually to save bytes the matrix is filtered for each column of the transpose. Fortunately this doesn't result in enough nesting to trouble the buggy deverbosifier on the version of Charcoal currently on TIO.)

Iθ

Output the remaining matrix.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 112 ... 102 bytes

->m{1until m==[:min,:max].map{|x|m=m.transpose|[];m-=m.combination(2).map{|a,b|a.zip(b).map &x}}[1];m}

Try it online!

\$\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.