8
\$\begingroup\$

This challenge is adapted from the British Informatics Olympiad.


Dice game

Two players are playing a dice game where they each roll a pair of dice, and the highest sum wins. The pairs of dice have the same number of sides, but do not have to have the same values on each side. Therefore, the game is fair if for both pairs of dice all possible sums can be made with equal probability.

For example, if Player 1 has the following dice:

{1,2,3,4,5,6} {1,2,3,4,5,6}

Then they can produce the following sums:

    1  2  3  4  5  6
 +------------------
1|  2  3  4  5  6  7 
2|  3  4  5  6  7  8
3|  4  5  6  7  8  9
4|  5  6  7  8  9  10
5|  6  7  8  9  10 11
6|  7  8  9  10 11 12

If Player 2 has:

{1,2,2,3,3,4} {1,3,4,5,6,8}

They can produce:

    1  2  2  3  3  4
 +------------------
1|  2  3  3  4  4  5 
3|  4  5  5  6  6  7
4|  5  6  6  7  7  8
5|  6  7  7  8  8  9
6|  7  8  8  9  9  10
8|  9  10 10 11 11 12

This game is fair as the minimum for both is 2, the maximum is 12, and each sum occurs the same number of times, e.g 7 can be made 6 ways with each pair.


Challenge

Write a program/function that takes two dice as input, and optionally an integer representing the number of sides each dice contain, and prints/returns a different pair of dice that could be used to play a fair game with the two input dice, or any falsey value if there is no solution different from the input.


Specifications

  • The number of sides on both dice must be the same, and equal to the number of sides on the input pair of dice. This number will always be an integer greater than or equal to 1.

  • The two dice returned can be the same, but the pair must not be the same as the input pair.

  • Different order pairs are not different; {1,2,3} {4,5,6} is the same as {4,5,6} {1,2,3}.

  • Your program does not need to produce a result quickly, as long as it will eventually produce correct output.

  • The values on the input pair of dice dice will always be integers between 1 and 9 inclusive, but the values returned can be any integer ≥1.

  • If there is more than one possible solution, only one needs to be returned.

  • Input/Output can be in any reasonable format.

Test Cases

6
1 2 2 3 3 4
8 6 5 4 3 1

1 2 3 4 5 6
1 2 3 4 5 6

4
1 1 1 1
1 4 5 8

1 1 4 4
1 1 5 5

3
1 3 5
2 4 6

False

8                    
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

Any of the following:

1 2 2 3 3 4 4 5       |    1 2 2 3 5 6 6 7   |    1 2 3 3 4 4 5 6
1 3 5 5 7 7 9 11      |    1 3 3 5 5 7 7 9   |    1 2 5 5 6 6 9 10
\$\endgroup\$
  • 3
    \$\begingroup\$ 3-sided dice look cool: images2.sw-cdn.net/product/picture/… \$\endgroup\$ – Magic Octopus Urn Mar 14 '17 at 20:26
  • \$\begingroup\$ Will the die only contain digits, or can it also be higher than 9? I only see ruling about the sides being >=1, but is there a max? If it can be higher than 9, would you mind adding a test case for it? \$\endgroup\$ – Kevin Cruijssen Mar 15 '17 at 8:33
  • \$\begingroup\$ @KevinCruijssen Updated, input will only contain digits, output can contain any integer ≥1. \$\endgroup\$ – Trelzevir Mar 15 '17 at 16:45
2
\$\begingroup\$

Jelly, 34 bytes

+þµFṢ
ç©ṀRœċL}Œċµç/⁼®µÐf
,Ṣ€,Ṛ$ḟ@ç

Returns a list of all possible pairs of dice up to ordering of dice and faces* (excluding any that are the same dice as the input pair).

Try it online!

This is a brute-forcer, and is not efficient (too slow to even run the 6-face test case at TIO).

+þµFṢ - Link 1, sorted sums: dieA, dieB
 þ    - outer product with
+     -     addition (make a table of the sums, a list of lists)
  µ   - monadic chain separation
   F  - flatten into one list
    Ṣ - sort

ç©ṀRœċL}Œċµç/⁼®µÐf - Link 2, all possible fair dice pairs (including input): dieA, dieB
ç                  - call the last link (1) as a dyad
 ©                 - save the result to the register for later use too
  Ṁ                - maximum (the largest sum)
   R               - range [1,2,...,maxSum]
       }           - use right argument (dice B) to turn the monad into a dyad:
      L            -     length
    œċ             - all combinations with replacement (i.e. all dice with faces between 1 and maxSum inclusive [overkill, but golfier than less])
        Œċ         - all pairs of these dice
          µ        - monadic chain separation
               µÐf - filter keep:
            /      -     reduce with:
           ç       -         last link (1) as a dyad (the sorted sums of the current pair)
              ®    -     retrieve register value (the sorted sums of the input pair)
             ⁼     -     equal?

,Ṣ€,Ṛ$ḟ@ç - Main link: dieA, dieB
,         - pair - [dieA, dieB]
 Ṣ€       - sort €ach - [dieASorted, dieBSorted]
     $    - last two links as a monad:
    Ṛ     -     reverse - [dieBSorted, dieASorted]
   ,      -     pair - [[dieASorted, dieBSorted], [dieBSorted, dieASorted]]
        ç - call the last link (2) as a dyad (with dieA, dieB)
       @  - reversed @rguments:
      ḟ   -     filter out - removes any results that are equivalent to the input pair.

* i.e. if [[1,1,4,4],[1,1,5,5]] is a possibility (like in one of the examples) there wont be a [[1,1,5,5],[1,1,4,4] or [[1,4,1,4],[1,1,5,5]], etc.

\$\endgroup\$
  • \$\begingroup\$ Hmm, I have actually assumed dice will be in face order (either dice first), is that OK or not? \$\endgroup\$ – Jonathan Allan Mar 14 '17 at 19:57
  • \$\begingroup\$ ...I noticed a test case has a die that is not ordered so I removed the assumption. \$\endgroup\$ – Jonathan Allan Mar 14 '17 at 20:22
1
\$\begingroup\$

C++14, 130 bytes

As unnamed lambda assuming M to be like std::vector<std::vector<int>>. Fair is 0, anything else is unfair.

#include<map>
[](auto&M){auto g=[](auto&v){std::map<int,int>m;for(int x:v)for(int y:v)m[x+y]++;return m;};return g(M[0])-g(M[1]);}

Ungolfed:

#include<map>

auto f=
[](auto&M){
 auto g=[](auto&v){
  std::map<int,int>m;
  for(int x:v)
   for(int y:v)
    m[x+y]++;
  return m;
 };
 return g(M[0])==g(M[1]);
}
;
\$\endgroup\$
1
\$\begingroup\$

Python, 228 bytes

from itertools import*;s,C=lambda x,y:sorted(sum([[i+j for j in y]for i in x],[])),combinations_with_replacement;f=lambda k,l,m:([[*a]for a in C([*C([*range(1,s(l,m)[-1])],k)],2)if(s(l,m)==s(*a))*~-([*a]in[[l,m],[m,l]])]+[0])[0]

This was from a long time ago; I could probably golf this a bit better now.

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