9
\$\begingroup\$

The dice game Mia introduces a very non-trivial order of sets of size two:

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

In general, the order within a tuple does not matter {x,y}={y,x}, {1,2} is greater than anything else, Pairs are greater than non-pairs and the numeric value decides in case of a tie.

Now suppose you want to use n dice. Also, the dices have m faces.

Example:

  • {1,5,3,4} < {1,2,6,3} since 5431 < 6321
  • {1,2,3,5} < {1,1,5,6} < {1,1,5,5}, {1,1,6,6} < {1,1,1,3} < {2,2,2,3} < {1,1,1,1} < {1,2,3,4}
  • {2,2,5} < {1,1,6} since both sets have each one pair and 611 > 522

In a nutshell, {1, ..., n} is greater than anything else. Let p > q, then p-of-a-kind is greater than q-of-a-kind. In case of a tie, the second(, third, ...)-longest of-a-kind wins. Finally, if no decision could be made yet, the greatest numerical value wins. The numerical value of a set is the largest integer you can build from the available numbers in the set, using concatenation. Example:

  • {2,5,4,3} becomes 5432
  • {4,11,3,4} becomes B443 (>6-faced dice are allowed, B=11)

Your task is to write the smallest possible program (i.e. function) in the language of your choice, that, given two containers (list, array, set, ...) returns whether the first or the second one wins.

Note: you can assume that the two containers have the same length and contain only positive integers, but nothing else. Especially they may be not sorted. The return value could be anything, e.g. {-1, 0, 1} for {first wins, tie, second wins}.

\$\endgroup\$
  • 1
    \$\begingroup\$ Which one wins of {1,1,6}, {2,2,5}? Do you compare the numerical value of the largest p-of-a-kind or of any dice? \$\endgroup\$ – Martin Ender Mar 4 '17 at 17:47
  • 1
    \$\begingroup\$ Let me check if my understanding of the ordering is right: First, {1, ..., n} is highest. For each list, take the most common value, and of equally common values take the biggest one. If one list has more of that, it wins. If equally common, whichever is greater wins. If equal both in commonness and value, remove all those from each list and compare again. \$\endgroup\$ – xnor Mar 4 '17 at 17:51
  • \$\begingroup\$ @Martin: Excellent Question. I guess there is no "canonical" decision on that, and since my julia program says {1,1,6} wins over {2,2,5}, then it's just that. \$\endgroup\$ – pasbi Mar 4 '17 at 18:17
  • \$\begingroup\$ @xnor: Yes, however consider martin's comment and my answer. \$\endgroup\$ – pasbi Mar 4 '17 at 18:31
  • \$\begingroup\$ @oVooVo Oh yeah, that actually makes sense considering your example where you simply sort them by numerical value after sorting the digits from largest to smallest. \$\endgroup\$ – Martin Ender Mar 4 '17 at 18:38
2
\$\begingroup\$

Jelly, 16 bytes

ṢŒrUṢṚZ
Ṣ⁼J;ǵÐṀ

Takes a list of lists each of which represents a roll (so can be more than two if wanted) and returns a list of the winner(s).

Try it online! ...alternatively here is a version which sorts the rolls from weakest to strongest instead.

How?

Ṣ⁼J;ǵÐṀ - Main link: list of list of dice rolls, L
     µÐṀ - filter keep maximal (i.e. sort L by the previous link as a key and keep maximums)
         -                                            e.g. [5,3,1,3]
Ṣ        -     sort roll                                   [1,3,3,5]
  J      -     range(length(roll))                         [1,2,3,4]
 ⁼       -     equal? [1,2,3,...n] beats everything        0
    Ç    -     call last link as a monad with input roll   [[2,1,1],[3,5,1]]
   ;     -     concatenate                                 [0,[2,1,1],[3,5,1]]

ṢŒrUṢṚZ - Link 1, rest of sort key: dice rolls        e.g. [5,3,1,3]
Ṣ       - sort the roll                                    [1,3,3,5]
 Œr     - run length encode                                [[1,1],[3,2],[5,1]]
   U    - upend (reverse each)                             [[1,1],[2,3],[1,5]]
    Ṣ   - sort                                             [[1,1],[1,5],[2,3]]
     Ṛ  - reverse                                          [[2,3],[1,5],[1,1]]
      Z - transpose                                        [[2,1,1],[3,5,1]]
        -     ...this is a list of: 1) the group sizes descending; and
                 2) the face values of each group, descending across equal group sizes
\$\endgroup\$
  • \$\begingroup\$ @oVooVo While trying to golf this more I noticed that 1,1,2 and 1,2,2 are deemed equal, but the spec does not currently distinguish them either. \$\endgroup\$ – Jonathan Allan Mar 5 '17 at 17:19
  • \$\begingroup\$ @oVooVo upon further inspection the example has {1,1,5,6} < {1,1,5,5} where 6 > 5. Could you clarify? \$\endgroup\$ – Jonathan Allan Mar 5 '17 at 17:30
  • \$\begingroup\$ @oVooVo Maybe it should be like this - I have replaced the "maximal selection", ÐṀ, with a sort, Þ, for testing purposes - using the items from the example it sorts them into the same order. The ordering used is: first by if it's "top-dog", then by counts of equal faces descending and finally by unique faces descending. \$\endgroup\$ – Jonathan Allan Mar 5 '17 at 17:46
  • \$\begingroup\$ {1,1,5,5} has two "2-of-a-kind": (1,1) and (5,5). {1,1,5,6} has only one "2-of-a-kind". Hence {1,1,5,5} wins. The value does not matter here. Similarly, {1,1,2,2} > {4,5,6,6}. \$\endgroup\$ – pasbi Mar 6 '17 at 11:30
  • \$\begingroup\$ {1,2,2} > {1,1,2}. Because both have one 2-of-a-kind, numeric tie-breaking applies. {1,2,2}=>221 and {1,1,2}=>211. Obviously 221 is greater than 211. I will clarify this in the specs. \$\endgroup\$ – pasbi Mar 6 '17 at 11:34
2
\$\begingroup\$

JavaScript (ES6), 162 bytes

(a,b,g=a=>a.map(n=>e[n]=e[n]+1||1,e=[1])&&[[...e].every(n=>n==1),...e.filter(i=x=>x).sort(h=(a,b)=>b-a),...a.sort(h)],c=g(a),d=g(b))=>d.map((n,i)=>n-c[i]).find(i)

Explanation: Takes two arrays as parameters. g converts each array into a list of counts. The list is then checked to see whether it corresponds to a set 1..n. The counts are sorted and the sorted values are concatenated. The two results are then compared. The return value is a positive integer if the second array wins and a negative integer if the first array wins, otherwise the falsy JavaScript value undefined is returned.

\$\endgroup\$
  • \$\begingroup\$ Your program says {1,1,6} < {2,2,5}, which is wrong. \$\endgroup\$ – pasbi Mar 5 '17 at 14:58
  • \$\begingroup\$ @oVooVo Sorry, I must have misunderstood the rules (I thought you broke ties based on the numeric value of the longest-of-a-kind). \$\endgroup\$ – Neil Mar 5 '17 at 16:10
0
\$\begingroup\$

PHP 333 Bytes

I assume that there are fewer dices then faces for the highest value as street beginning with 1

I make a little more. Input is an array with more then two values. Output is the sorted array.

<? $m=$_GET[m];foreach($m as$k=>$v){rsort($v);$m[$k]=$v;}function t($a,$b){if($a==$r=range($x=count($a),1))return 1;elseif($b==$r)return-1;$c=array_pad(array_values(array_count_values($a)),$x,0);$d=array_pad(array_values(array_count_values($b)),$x,0);rsort($c);rsort($d);if($e=$c<=>$d)return$e;return$a<=>$b;}usort($m,t);print_r($m);

Breakdown

$m=$_GET["m"]; # Array as Input
foreach($m as$k=>$v){
    rsort($v); # reverse sort of an item
    $m[$k]=$v; # replace the sort item
}
function t($a,$b){ #sorting algorithm
    if($a==$r=range($x=count($a),1))return 1; # $a is highest value
    elseif($b==$r)return-1; # $b is highest value
    $c=array_pad(array_values(array_count_values($a)),$x,0); 
# prepare check multiple values for fist value
    $d=array_pad(array_values(array_count_values($b)),$x,0); 
# prepare check multiple values for second value
    rsort($c);
    rsort($d);
    if($e=$c<=>$d)return$e; # compare first and second multiples
    return$a<=>$b; # compare dices
}
usort($m,"t"); # start sort
print_r($m); #print sorted array from low to high
\$\endgroup\$
0
\$\begingroup\$

Julia (489 Bytes)

function a(x,y)l=length;g=collect;s=sort;m=maximum;r=repmat;function b(z)w=sum(r(z,1,m(z)).==r(g(1:m(z))',l(z),1),1);u=zeros(m(w));map(i->if i>0 u[i]+=1;end,w);return u end;function c(x,y)if l(x)>l(y)return-1 elseif l(x)<l(y)return 1 else for i=l(x):-1:1 if x[i]>y[i] return-1 elseif x[i]<y[i] return 1 end end;return 0;end end;x=s(x);y=s(y);if x==y return 0;elseif x==g(1:l(x));return-1 elseif y==g(1:l(y))return 1 else d=c(b(x),b(y));if d==0 return c(x,y);else return d;end end end

Readable:

  1 function a(ds1, ds2)
  2     function countNOfAKind(ds)
  3         # return array. n-th value is number of occurences of n-of-a-kind.
  4         # e.g. findNOfAKind([1, 1, 1, 2, 2, 3, 3]) == [0, 2, 1]
  5         ps = sum(repmat(ds, 1, maximum(ds)) .== repmat(collect(1:maximum(ds))', length(ds), 1), 1);
  6         ls = zeros(maximum(ps));
  7         map(i -> if i>0 ls[i] += 1 end, ps);
  8         return ls
  9     end
 10 
 11     function cmpLex(ds1, ds2)
 12         # compare ds1, ds2 reverse-lexicographically, i.e. compare last distinct value.
 13         if length(ds1) > length(ds2)
 14             return -1
 15         elseif length(ds1) < length(ds2)
 16             return 1
 17         else
 18             for i = length(ds1):-1:1
 19                 if ds1[i] > ds2[i]
 20                     return -1
 21                 elseif ds1[i] < ds2[i]
 22                     return 1
 23                 end
 24             end
 25             return 0;
 26         end
 27     end
 28     
 29     ds1=sort(ds1);
 30     ds2=sort(ds2);
 31     if ds1 == ds2
 32         return 0;
 33     elseif ds1 == collect(1:length(ds1))
 34         return -1
 35     elseif ds2 == collect(1:length(ds2))
 36         return 1
 37     else
 38         d = cmpLex(countNOfAKind(ds1), countNOfAKind(ds2))
 39         if d == 0
 40             return cmpLex(ds1, ds2);
 41         else
 42             return d;
 43         end
 44     end
 45 end
\$\endgroup\$
  • \$\begingroup\$ Why are you comparing lengths? The instructions say "the two containers have the same length". Am I missing something? \$\endgroup\$ – DavidC Mar 4 '17 at 22:24
  • \$\begingroup\$ I removed the length comparison in line 31. It was not necessary but did not hurt either. The comparison in line 15 is necessary, since cmpLex is not only used in line 40 to compare the raw inputs, but also in line 38 to compare the result of countNOfAKind. That function however may produce different-sized outputs for equally-sized inputs: countNOfAKind([3,2]) = [2] (because there are two lonely numbers (3 and 2)), countNOfAKind([2,2]) = [0, 1] (because there is no lonely number and one pair. \$\endgroup\$ – pasbi Mar 4 '17 at 22:45

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.