13
\$\begingroup\$

Input

A matrix M represented as two space separated lines of integers. Each line will have the same number of integers and each integer will be either -1 or 1. The number of integers per line will be at most 20. M will therefore be 2 by n where n is the number of integers on each of the two lines.

Your code should be a complete program. and accept the input either on standard in or from a file (that is your choice). You can accept input from standard in, from a file or simply as a parameter. However, if you do the latter please give an explicit example of how your code should work and remember that it must be a complete program and how the matrix M will be represented in the input. In other words, you are likely to have to do some parsing.

Output

The binary Shannon entropy of the distribution of M*x where the elements of x are uniformly and independently chosen from {-1,1}. x is an n-dimensional column vector.

The entropy of a discrete probability distribution is

- sum p_i log_2(p_i)

In this case, p_i is the probability of the ith unique possible M*x.

Example and helpful hints

As a worked example, let the matrix M be

-1 1
-1 -1

Now look at all 2^2 different possible vectors x. For each one we compute M*x and put all the results in an array (a 4-element array of 2-component vectors). Although for each of the 4 vectors the probability of it occurring is 1/2^2 = 1/4, we are only interested in the number of times each unique resultant vector M*x occurs, and so we sum up the individual probabilities of the configurations leading to the same unique vectors. In other words, the possible unique M*x vectors describe the outcomes of the distribution we're investigating, and we have to determine the probability of each of these outcomes (which will, by construction, always be an integer multiple of 1/2^2, or 1/2^n in general) to compute the entropy.

In the general n case, depending on M the possible outcomes of M*x can range from "all different" (in this case we have n values of i in p_i, and each p_i is equal to 1/2^n), to "all the same" (in this case there is a single possible outcome, and p_1 = 1).

Specifically, for the above 2x2 matrix M we can find by multiplying it with the four possible configurations ([+-1; +-1]), that each resulting vector is different. So in this case there are four outcomes, and consequently p_1 = p_2 = p_3 = p_4 = 1/2^2 = 1/4. Recalling that log_2(1/4) = -2 we have:

- sum p_i log_2(p_i) = -(4*(-2)/4) = 2

So the final output for this matrix is 2.

Test cases

Input:

-1 -1 
-1 -1

Output:

1.5

Input:

-1 -1 -1 -1
-1 -1 -1 -1

Output:

2.03063906223

Input:

-1  -1  -1  1
1  -1  -1  -1

Output:

3
\$\endgroup\$
  • 7
    \$\begingroup\$ 1. What are the dimensions of x? 2. In the interests of making the question self-contained, how is the binary Shannon entropy of Mx defined? \$\endgroup\$ – Peter Taylor Dec 30 '15 at 10:37
  • 4
    \$\begingroup\$ @Peter's comment exactly explains the downvotes. I skimmed the article on entropy, and I can't immediately find out what to implement. You should specify exactly what the formula/algorithm is to compute Shannon entropy. \$\endgroup\$ – Lynn Dec 30 '15 at 14:10
  • 5
    \$\begingroup\$ Questions should be self-contained, anyway; it's unlikely that Wikipedia will suddenly go offline, but it would be ideal to not have to click through to another page to be able to understand the full specification of the challenge. \$\endgroup\$ – Doorknob Dec 30 '15 at 14:17
  • 2
    \$\begingroup\$ By default, functions are a valid alternatives to programs. You are allowed to overrule that, but it will make some languages very sad because it takes lots of boilerplate to take file or stdin input. More broadly, I recommend against having such a restrictive input format on a mathematical challenge. Allowing the language's natural list type would make people happier to participate. \$\endgroup\$ – xnor Dec 30 '15 at 18:38
  • 3
    \$\begingroup\$ @dorothy note that it's not that "log_2(0) is 0 for convenience", but rather "lim_{p->0} p*log(p)==0". So "log_2(0)" is still -inf. \$\endgroup\$ – Andras Deak Dec 30 '15 at 20:35
3
\$\begingroup\$

Mathematica, 48 68 bytes

Edit: Preprocess is added for accepting string as the parameter.

With the help of Tuples and Entropy, the implementation is both concise and readable.

Entropy[2,{-1,1}~Tuples~Length@#.#]&@Thread@ImportString[#,"Table"]&

where Tuples[{-1,1},n] gives all possible n-tuples from {-1,1}, and Entropy[2,list] gives the base-2 information entropy.

One of the cool things is that Mathematica will actually return an accurate expression:

%["-1 -1 \n -1 -1"]
(* 3/2 *)

Approximate result can be achieved with an extra . added (Entropy[2., ...).

\$\endgroup\$
  • \$\begingroup\$ Mathematica is ridiculous :) However your answer doesn't quite fit the spec. The input is space separated so some parsing will be needed. See the latest update. \$\endgroup\$ – dorothy Jan 1 '16 at 15:18
3
\$\begingroup\$

Perl, 160 159 141 bytes

includes +1 for -p since 141 byte update

@y=(@z=/\S+/g)x 2**@z;@{$.}=map{evals/.1/"+".$&*pop@y/egr}glob"{-1,+1}"x@z}{$H{$_.$2[$i++]}++for@1;$\-=$_*log($_/=1<<@z)/log 2 for values%H;

The input is expected on STDIN as 2 lines consisting of space-separated 1 or -1.
Run as perl -p 140.pl < inputfile.

It won't win any prizes, but I thought I'd share my effort.
Explained:

    @y=                             # @y is (@z) x (1<<$n)
       (@z = /\S+/g)                # construct a matrix row from non-WS
       x 2**@z;                     # repeat @z 2^$n times
    @{$.} = map {                   # $.=$INPUT_LINE_NUMBER: set @1 or @2
      eval s/.1/"+".$&*pop@y/egr    # multiply matrix row with vector
    } glob "{-1,+1}" x @z           # produce all possible vectors

}{                                  # `-p` trick: end `while(<>)`, reset `$_`

$H{ $_ . $2[$i++] }++               # count unique M*x columns
    for @1;

$\ -= $_ * log($_/=1<<@z) / log 2   # sum entropy distribution
        for values %H;

DATA

  • update 159: save 1 by eliminating () by using ** instead of <<.
  • update 141: save 18 by using $. and -p.
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you! We don't have enough perl answers on ppcg imho \$\endgroup\$ – dorothy Jan 2 '16 at 19:16
  • \$\begingroup\$ @dorothy It's because code-golfers loathe Perl, for the most part. \$\endgroup\$ – Addison Crump Jan 4 '16 at 12:09
  • \$\begingroup\$ @FlagAsSpam But, but.. perl is incomprehensible, succinct and borderline insane. How could it be more suitable for code-golf? \$\endgroup\$ – dorothy Jan 4 '16 at 12:10
  • \$\begingroup\$ @dorothy ¯\_(ツ)_/¯ We avoid it like the plague. Dunno why, really. \$\endgroup\$ – Addison Crump Jan 4 '16 at 12:11
2
\$\begingroup\$

Pyth, 37 bytes

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8

Test suite

This is somewhat trickier when you have to manually implement matrix multiplication.

Explanation:

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8
       JrR7.z                            Parse input into matrix, assign to J.
  _B1                                    [1, -1]
K^   lhJ                                 All +-1 vectors of length n, assign to K.
                           m       K     Map over K
                            m     J      Map over the rows of J
                             s*Vdk       Sum of vector product of vector and row.
                          S              Sort
                         r          8    Run length encode.
                       hM                Take just occurrence counts.
                   cRlK                  Divide by len(K) to get probabilities.
               *Lld                      Multiply each probabiliity by its log.
              s                          Sum.
             _                           Negate. Print implicitly.
\$\endgroup\$
  • \$\begingroup\$ Wow! :) This looks like a lot of work. Now where are the cjam people..... ? \$\endgroup\$ – dorothy Jan 3 '16 at 16:06
1
\$\begingroup\$

MATLAB, 196 194 187 184 126 154 bytes

(The extra 28 bytes from 126 to 154 are due to input parsing: now the code accepts the input as two lines of whitespace-separated numbers.)

f=@()str2num(input('','s'));M=[f();f()];n=size(M,2);x=(dec2bin(0:n^2-1,n)-48.5)*2*M';[~,~,c]=unique(x,'rows');p=accumarray(c,1)/2^n;disp(-sum(p.*log2(p)))

Ungolfed version:

f=@()str2num(input('','s'));        % shorthand for "read a line as vector"
M=[f();f()];                        % read matrix
n=size(M,2);                        % get lenght of vectors

x=(dec2bin(0:n^2-1,n)-48.5)*2*M';   % generate every configuration
                                    %    using binary encoding
[~,~,c]=unique(x,'rows');           % get unique rows of (Mx)^T
p=accumarray(c,1)/2^n;              % count multiplicities and normalize
disp(-sum(p.*log2(p)))              % use definition of entropy

I could do away with 6 bytes if an "ans = ..." type of output was allowed, I'm never sure about this.

I'm sorry to say that my original and surely witty solution was way too ungolfed compared to my current solution. This is also the first time I'm using accumarray. A six-input-parameter application still has to wait, though:)

Outputs (following format long):

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
   1.500000000000000

[-1 -1 -1 -1
-1 -1 -1 -1]
   2.030639062229566

[-1  -1  -1  1
1  -1  -1  -1]
     3

Outputs with the default format short g:

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
          1.5

[-1 -1 -1 -1
-1 -1 -1 -1]
       2.0306

[-1  -1  -1  1
1  -1  -1  -1]
     3
\$\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.