24
\$\begingroup\$

A stochastic matrix is a matrix of probabilities used in the context of Markov chains.

A right stochastic matrix is a matrix where each row sums to 1.

A left stochastic matrix is a matrix where each column sums to 1.

A doubly stochastic matrix is a matrix where each row and each column sums to 1.

In this challenge, we will represent the probabilities in percent using integers. A row or column must in that case sum to 100 and not 1.

Your goal is to write a program or function which, given a square matrix of integers as input, outputs one of four values indicating that the matrix is either right stochastic, left stochastic, doubly stochastic or none of those.

Input

You may use any proper representation of a matrix that is natural for your language for the input. For example, a list of lists, a string of comma separated values with rows separated by linebreaks, etc.

The input matrix will always be square and will only contain non-negative integers. The input matrix will always be at least 1×1.

You may pass the input using STDIN, as a function argument, or anything similar.

Output

You must choose four distinct outputs that correspond to right stochastic, left stochastic, doubly stochastic or none of those. Those outputs must be constant regardless of what input is passed. Your program may not return different outputs for the same case, e.g. saying that any negative number corresponds to none of those is not valid.

In short, there must be a 1-to-1 correspondence between your output an the four possible cases. Some examples of those four outputs would be {1, 2, 3, 4} or {[1,0], [0,1], [1,1], [0,0]} or even {right, left, doubly, none}.

Please indicate in your answer the four outputs your program uses.

If a matrix is doubly stochastic, then you must return the output corresponding to doubly stochastic, and not right or left stochastic.

You may print the output to STDOUT, return it from a function, or anything similar.

Test cases

[100]               => Doubly stochastic

[42]                => None of those

[100  0  ]          => Doubly stochastic
[0    100]

[4   8   15]
[16  23  42]        => Left stochastic
[80  69  43]

[99  1 ]            => Right stochastic
[2   98]

[1   2   3   4 ]
[5   6   7   8 ]    => None of those
[9   10  11  12]
[13  14  15  16]

Scoring

This is , so the shortest answer in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can I take an input determining the size of the matrix first? \$\endgroup\$ – HyperNeutrino Nov 18 '16 at 18:02
  • \$\begingroup\$ @AlexL. No, this would be unfair to change the specs at this point. \$\endgroup\$ – Fatalize Nov 18 '16 at 18:05

17 Answers 17

9
\$\begingroup\$

05AB1E, 13 11 10 bytes

Right stochastic: [0,1]
Left stochastic: [1,0]
Doubly stochastic: [1,1]
None of those: [0,0]

Dø2FOTnQPˆ

Try it online!

Explanation

D            # duplicate input
 ø           # transpose the copy
  2F         # 2 times do (once for each matrix)
    O        # sum of the rows
     TnQ     # is equal to 100
        P    # product
         ˆ   # add to global list
             # implicitly print global list at the end of the program
\$\endgroup\$
14
\$\begingroup\$

Haskell, 57 55 bytes

import Data.List
s a=all((==100).sum)<$>[transpose a,a]

Input of type (Eq a, Num a) => [[a]]. Outputs boolean list [left-stochastic, right-stochastic]

Thanks to @proudhaskeller for saving 2 bytes

\$\endgroup\$
  • \$\begingroup\$ Couldn't you save some bytes by making the function pointfree? e.g. with [transpose,id]<*> (then you could omit the s a= as anynomous functions are allowed) \$\endgroup\$ – flawr Nov 18 '16 at 9:57
  • \$\begingroup\$ @flawr possibly, but [transpose,id]<*> has a type of [[[a]]]->[[[a]]], which needs another layer of map and a pure/return/(:[]) or a input of type [[[Int]]], which isn't natural. Best I got is map(all(==100).map sum).(<$>[transpose,id]).flip id \$\endgroup\$ – Angs Nov 18 '16 at 10:20
  • \$\begingroup\$ Ah right, thank you for the explanation! \$\endgroup\$ – flawr Nov 18 '16 at 10:46
  • \$\begingroup\$ How about all((==100).sum) instead of all(==100).map sum? \$\endgroup\$ – proud haskeller Nov 21 '16 at 19:21
  • \$\begingroup\$ @proudhaskeller of course! all does a mapping in itself. \$\endgroup\$ – Angs Nov 21 '16 at 19:25
11
\$\begingroup\$

R, 55 bytes

function(m)c(all(colSums(m)==100),all(rowSums(m)==100))

Unnamed function where m is assumed to be an R-matrix.

Output:

  • [1] TRUE FALSE: Left stochastic
  • [1] FALSE TRUE: Right stochastic
  • [1] TRUE TRUE: Doubly
  • [1] FALSE FALSE: None
\$\endgroup\$
  • \$\begingroup\$ any(colSums(m)-100) and likewise for the rowSums will drop you two bytes while inverting all the outputs, so if you'd like to keep those, you can always put a ! in front for net -1 byte. \$\endgroup\$ – Giuseppe Oct 14 '17 at 15:24
7
\$\begingroup\$

Octave, 35 34 32 31 bytes

@(n)any([sum(n);sum(n')]-100,2)

Call it like this:

f(100)
f(42)
f([4,8,15; 16,23,42; 80,69,43])
f([99,1;2,98])
f([1,2,3,4;5,6,7,8;9,10,11,12;13,14,15,16])

Test it here.

Saved 2 bytes thanks to flawr initially, but went for another approach that was 1 byte shorter.

This outputs the following for the different cases:

0    Doubly
0    

1    None
1

0    Left
1

1    Right
0

The last ,2 would be unnecessary if single digits weren't included. Also, if this summed to 1 instead of 100 (as it could have), it would save another 4 bytes.

\$\endgroup\$
6
\$\begingroup\$

Mathematica 29 Bytes

{}⋃Tr/@#=={100}&/@{#,#}&

substituting the =U+F3C7=[\Transpose] character. This code snippet will paste correctly into Mathematica.

Same truthiness convention with {lefttruth, righttruth} as output

\$\endgroup\$
  • \$\begingroup\$ {}⋃ saves one byte over Union@ \$\endgroup\$ – A Simmons Nov 21 '16 at 14:02
  • \$\begingroup\$ @ASimmons, thanks for the tip! Put it in and corrected an error in my byte total. \$\endgroup\$ – Kelly Lowder Nov 21 '16 at 16:39
  • \$\begingroup\$ Also I think if you make your output {righttruth, lefttruth}, then replacing Total@ with Tr/@ will save a further 2 bytes. \$\endgroup\$ – A Simmons Nov 21 '16 at 16:47
  • \$\begingroup\$ Or equivalently reverse the two matrices so the solution becomes {}⋃Tr/@#=={100}&/@{#,#}& \$\endgroup\$ – A Simmons Nov 21 '16 at 17:00
  • \$\begingroup\$ @ASimmons, Yes, that saved another 2. Thanks! \$\endgroup\$ – Kelly Lowder Nov 21 '16 at 17:09
6
\$\begingroup\$

k, 21 19 bytes

{min'100=+/'(x;+x)}

Output

  • 00b none
  • 10b left
  • 01b right
  • 11b both

Example:

k)f:{min'100=+/'(x;+x)} //store function as f
k)f(100 0;98 2)
01b

edit: reduce byte count by 3 - function does not need to be enclosed in a lambda

edit: reduce bytecount by 2 - H/T @Simon Major

\$\endgroup\$
  • 1
    \$\begingroup\$ You can actually save a byte by enclosing in a lambda: {min'100=+/'(x;+:x)} \$\endgroup\$ – Simon Major Nov 20 '16 at 21:51
5
\$\begingroup\$

MATL, 12 bytes

sG!sv!100=XA

Output is two zero/one values. First indicates if the matrix is left-stochastic, second if it is right-stochastic.

Try it online! Or verify all test cases

s      % Implicitly input N×N matrix. Sum of each column. Gives a 1×N vector
G!     % Push input transposed
s      % Sum of each column. Gives a 1×N vector
v      % Concatenate vertically. Gives a 2×N matrix
!      % Transpose. N×2
100=   % Does each entry equal 100?
XA     % True for columns that contain only "true". Gives 1×2 vector. Implicitly display
\$\endgroup\$
  • \$\begingroup\$ Man that 100 was expensive, good answer though. \$\endgroup\$ – Magic Octopus Urn Nov 18 '16 at 15:16
5
\$\begingroup\$

Mathematica, 46 43 bytes

AllTrue[#==100&]/@Apply[Plus,{#,#},{1}]&

As with other answers, the outputs are

{False, False} for non-stochastic

{True, False} for left-stochastic

{False, True} for right-stochastic

{True, True} for doubly stochastic

Saved 3 bytes by switching to the operator form of AllTrue

\$\endgroup\$
  • \$\begingroup\$ Use U+F3C7 (private use) for \[Transpose] \$\endgroup\$ – lastresort Nov 18 '16 at 12:55
  • \$\begingroup\$ I considered it but thought that was less enlightening \$\endgroup\$ – A Simmons Nov 18 '16 at 13:15
  • \$\begingroup\$ Also there's an extra @ at the end \$\endgroup\$ – lastresort Nov 18 '16 at 13:17
4
\$\begingroup\$

PHP, 104 bytes

function($a){for($s=array_sum;$a[+$i];)$o|=$s($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;}

An anonymous function that echos 0 => both, 1=> left, 2=> right, 3=> neither.
Use like:

php -r "$c=function($a){for($s=array_sum;$a[+$i];)$o|=$s($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;};$c(json_decode($argv[1]));" "[[4,8,15],[16,23,42],[80,69,43]]"

A command line program version at 114 bytes:

for($a=json_decode($argv[1]);$a[+$i];)$o|=($s=array_sum)($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;

Used like:

 php -r "for($a=json_decode($argv[1]);$a[+$i];)$o|=($s=array_sum)($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;" "[[4,8,15],[16,23,42],[80,69,43]]"
\$\endgroup\$
4
\$\begingroup\$

Python 2, 70 64 Bytes

Nothing crazy here, just making use of splatting in zip to transpose the matrix :) The outputs are as follows:

0 - not stochastic
1 - right stochastic
2 - left stochastic
3 - doubly stochastic

And here's the code :)

k=lambda m:all(sum(x)==100for x in m)
lambda n:k(n)+2*k(zip(*n))
\$\endgroup\$
  • \$\begingroup\$ Is the star in (*n a mistake? \$\endgroup\$ – hhh Nov 18 '16 at 19:02
  • 1
    \$\begingroup\$ @hhh No, that's the splat operator :) Essentially that's what is letting me transpose the matrix :) \$\endgroup\$ – Kade Nov 18 '16 at 19:12
4
\$\begingroup\$

C#, 205 203 183 bytes

Golfed:

int F(int[,]m){int x,i,j,r,c,e,w;x=m.GetLength(0);e=w=1;for(i=0;i<x;i++){r=c=0;for(j=0;j<x;j++){r+=m[i,j];c+=m[j,i];}if(r!=100)e=0;if(c!=100)w=0;}return e==1&&w==1?3:e==1?1:w==1?2:4;}

Ungolfed with comments:

    int F(int[,] m)
    {
        //x - matrix size
        //i, j - loop control variables
        //r, c - row/column sum
        //e, w - east/west, pseudo-bool values indicate right/left stochastic
        int x, i, j, r, c, e, w;
        x = m.GetLength(0);
        e = w = 1;

        for (i = 0; i < x; i++)
        {
            r = c = 0;

            for (j = 0; j < x; j++)
            {
                r += m[i, j];
                c += m[j, i];
            }

            if (r != 100)
                e = 0;

            if (c != 100)
                w = 0;
        }

        return e == 1 && w == 1 ? 3 : e == 1 ? 1 : w == 1 ? 2 : 4;
    }

Output key: 1 - right stochastic 2 - left stochastic 3 - double stochastic 4 - none

Try it: http://rextester.com/PKYS11433

EDIT1: r=0;c=0; => r=c=0;

EDIT2: Nested ternary operators. Credits goes to @Yodle.

\$\endgroup\$
  • 2
    \$\begingroup\$ if(e==1&&w==1)return 3;if(e==1)return 1;return w==1?2:4; Since e and w can only be 1 or 0, it can be changed to return w<<1|e; and redefine none==0. \$\endgroup\$ – Link Ng Nov 18 '16 at 14:08
  • 1
    \$\begingroup\$ You can shorten yours by 30 if you turn some of those if statements into ternary operations and just return an integer at the end. Idunno if I should post my solution since it's so similar. \$\endgroup\$ – Yodle Nov 18 '16 at 19:23
  • \$\begingroup\$ @LinkNg Very nice. I don't want to write code without understanding. I'm not familiar with binary operators. \$\endgroup\$ – paldir Nov 20 '16 at 19:52
  • \$\begingroup\$ @Yodle Thank you, I changed my solution. Feel free to post your even if it is very similar. \$\endgroup\$ – paldir Nov 20 '16 at 19:53
3
\$\begingroup\$

JavaScript (ES6), 83 bytes

a=>[a.some(a=>a.reduce((l,r)=>l-r,100)),a.some((_,i)=>a.reduce((l,a)=>l-a[i],100))]

Just to be contrary, not only does this output the right stoachistic result on the left, but the booleans are also inverted, so an output of [false, true] still means right stoachistic.

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

C#6, 130 bytes

using System.Linq;bool[]F(int[][]a)=>new[]{a.Where((_,i)=>a.Select(x=>x[i]).Sum()==100).Count()==a.Length,a.All(x=>x.Sum()==100)};

{False, False} for non-stochastic
{True, False} for left-stochastic
{False, True} for right-stochastic
{True, True} for doubly stochastic

repl.it demo

Ungolfed

bool[]F(int[][]a)=>
    // Return new array of two bools. Array type is inferred from arguments
    new[]
    {
        // Left:
        // Count the no. of columns which sums up to 100
        a.Where((_,i)=>a.Select(x=>x[i]).Sum()==100).Count()
            // Then check if no. of such columns equal to total column count
            ==a.Length,
        // Right: Do all rows sum up to 100?
        // Can't use this trick for left because no overload of All() accept Func<TSource,int,bool> like Where() does
        a.All(x=>x.Sum()==100)
    };
\$\endgroup\$
3
\$\begingroup\$

Groovy, 57

{a={it.every{it.sum()==100}};[a(it),a(it.transpose())]}​

Output

[0,0] if neither.

[1,0] if right.

[0,1] if left.

[1,1] if both.

\$\endgroup\$
2
\$\begingroup\$

Pip, 17 bytes

In an unexpected twist, this submission is a function.

{[h]=UQ$+_M[Zaa]}

Returns a list of two 0/1 values: [0 0] = not stochastic, [0 1] = left stochastic, [1 0] = right stochastic, [1 1] = doubly stochastic. Try it online!

Explanation

{               }  A function:
              a    Function argument (nested list)
           [Za ]   Create a list containing a's transpose and a
          M        Map this function to each of the above:
       $+_           Sum down the columns
     UQ              Get unique elements
 [h]=                If stochastic, the result should be [100]
\$\endgroup\$
2
\$\begingroup\$

Dyalog APL, 16 bytes

{∧/100=+/↑⍵(⍉⍵)}

{ } direct function definition (aka "dfn"), is the argument

⍵(⍉⍵) the matrix alongside its transposition

mix them into a single 2×n×n array

+/ sum along last axis, get a 2×n matrix

100= which elements are 100 (booleans are 0 1)

∧/ "and"-reduction along last axis, get 2 booleans for left,right stochastic

\$\endgroup\$
2
\$\begingroup\$

C++14, 139 136 133 130 bytes

-3 bytes for s=M.size(), -3 bytes for returning by reference parameter, -3 bytes as a unnamed lambda

[](auto M,int&r){int a,b,i,j,s=M.size();r=3;for(i=-1;++i<s;){for(j=-1,a=b=0;++j<s;a+=M[i][j],b+=M[j][i]);r&=(a==100)+2*(b==100);}}

Assumes input to be like vector<vector<int>>. Returns 3,2,1,0 for doubly, left, right, none stochastic.

Ungolfed:

auto f=
[](auto M, int& r){
  int a,b,i,j,s=M.size();
  r=3;
  for(i=-1;++i<s;){
    for(j=-1,a=b=0;++j<s;
      a+=M[i][j],
      b+=M[j][i]);
    r&=(a==100)+2*(b==100);
  }
}
;
\$\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.