12
\$\begingroup\$

When multiplying monomials in the Milnor basis for the Steenrod algebra, part of the algorithm involves enumerating certain "allowable matrices".

Given two lists of nonnegative integers r1, ... ,rm and s1, ... ,sn, a matrix of nonnegative integers X

a matrix

is allowable if

  1. The sum of the jth column is less than or equal to sj:

    column sums constraint

  2. The sum of the ith row weighted by powers of 2 is less than or equal to ri:

    row sums constraint

Task

Write a program which takes a pair of lists r1, ... ,rm and s1, s1, ... ,sn and computes the number of allowable matrices for these lists. Your program may optionally take m and n as additional arguments if need be.

  • These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else.

  • Output should be a positive integer

  • Standard loopholes apply.

Scoring

This is code golf: Shortest solution in bytes wins.

Examples:

For [2] and [1], there are two allowable matrices:

example 1

For [4] and [1,1] there are three allowable matrices:

example 2

For [2,4] and [1,1] there are five allowable matrices:

example 3

Test cases:

   Input: [1], [2]
   Output: 1

   Input: [2], [1]
   Output: 2

   Input: [4], [1,1]
   Output: 3

   Input: [2,4], [1,1]   
   Output: 5      

   Input: [3,5,7], [1,2]
   Output: 14

   Input: [7, 10], [1, 1, 1]
   Output: 15       

   Input: [3, 6, 16, 33], [0, 1, 1, 1, 1]
   Output: 38      

   Input: [7, 8], [3, 3, 1]
   Output: 44

   Input: [2, 6, 15, 18], [1, 1, 1, 1, 1]
   Output: 90       

   Input: [2, 6, 7, 16], [1, 3, 2]
   Output: 128

   Input: [2, 7, 16], [3, 3, 1, 1]
   Output: 175
\$\endgroup\$
  • 1
    \$\begingroup\$ IMO the definition would be easier to understand if you lose the first row and column of the matrices, index from 1, and use <= instead of ==. \$\endgroup\$ – Peter Taylor Jan 18 '18 at 12:45
  • \$\begingroup\$ Okay, will do. I just copied the definition out of a math textbook and it had an actual use for those entries. \$\endgroup\$ – Hood Jan 18 '18 at 17:00
3
\$\begingroup\$

JavaScript (ES7), 163 bytes

f=([R,...x],s)=>1/R?[...Array(R**s.length)].reduce((k,_,n)=>(a=s.map((_,i)=>n/R**i%R|0)).some(c=>(p+=c<<++j)>R,p=j=0)?k:k+f(x,s.map((v,i)=>v-a[i])),0):!/-/.test(s)

Test cases

NB: I've removed the two most time-consuming test cases from this snippet, but they should pass as well.

f=([R,...x],s)=>1/R?[...Array(R**s.length)].reduce((k,_,n)=>(a=s.map((_,i)=>n/R**i%R|0)).some(c=>(p+=c<<++j)>R,p=j=0)?k:k+f(x,s.map((v,i)=>v-a[i])),0):!/-/.test(s)

console.log(f([1],[2]))            // 1
console.log(f([2],[1]))            // 2
console.log(f([4],[1,1]))          // 3
console.log(f([2,4],[1,1]   ))     // 5      
console.log(f([3,5,7],[1,2]))      // 14
console.log(f([7,10],[1,1,1]))     // 15       
console.log(f([7,8],[3,3,1]))      // 44
console.log(f([2,6,7,16],[1,3,2])) // 128
console.log(f([2,7,16],[3,3,1,1])) // 175

Commented

f = (                               // f = recursive function taking:
  [R,                               //   - the input array r[] splitted into:
      ...x],                        //     R = next element / x = remaining elements
  s                                 //   - the input array s[]
) =>                                //
  1 / R ?                           // if R is defined:
    [...Array(R**s.length)]         //   for each n in [0, ..., R**s.length - 1],
    .reduce((k, _, n) =>            //   using k as an accumulator:
      (a =                          //     build the next combination a[] of
        s.map((_, i) =>             //     N elements in [0, ..., R - 1]
          n / R**i % R | 0          //     where N is the length of s[]
        )                           //
      ).some(c =>                   //     for each element c in a[]:
        (p += c << ++j)             //       increment j; add c * (2**j) to p
        > R,                        //       exit with a truthy value if p > R
        p = j = 0                   //       start with p = j = 0
      ) ?                           //     end of some(); if truthy:
        k                           //       just return k unchanged
      :                             //     else:
        k +                         //       add to k the result of
        f(                          //       a recursive call to f() with:
          x,                        //         the remaining elements of r[]
          s.map((v, i) => v - a[i]) //         s[] updated by subtracting the values of a[]
        ),                          //       end of recursive call
      0                             //     initial value of the accumulator k
    )                               //   end of reduce()
  :                                 // else:
    !/-/.test(s)                    //   return true if there's no negative value in s[]
\$\endgroup\$
1
\$\begingroup\$

Jelly, 26 bytes

UḄ€Ḥ>⁴
0rŒpṗ⁴L¤µS>³;ÇẸµÐḟL

A full program taking S, R which prints the count

Try it online!

How?

UḄ€Ḥ>⁴ - Link 1, row-wise comparisons: list of lists, M
U      - upend (reverse each)
 Ḅ€    - convert €ach from binary (note bit-domain is unrestricted, e.g. [3,4,5] -> 12+8+5)
   Ḥ   - double (vectorises) (equivalent to the required pre-bit-shift by one)
     ⁴ - program's 2nd input, R
    >  - greater than? (vectorises)

0rŒpṗ⁴L¤µS>³;ÇẸµÐḟL - Main link: list S, list R
0r                  - inclusive range from 0 to s for s in S
  Œp                - Cartesian product of those lists
       ¤            - nilad followed by link(s) as a nilad:
     ⁴              -   program's 2nd input, R
      L             -   length
    ṗ               - Cartesian power = all M with len(R) rows & column values in [0,s]
        µ      µÐḟ  - filter discard if:
         S          -   sum (vectorises) = column sums
           ³        -   program's 1st input, S
          >         -   greater than? (vectorises) = column sum > s for s in S
             Ç      -   call the last link (1) as a monad = sum(2^j × row) > r for r in R
            ;       -   concatenate
              Ẹ     -   any truthy?
                  L - length
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 101 bytes

Let Mathematica solve it as a system of inequalities over the integers. I set up a symbolic array in f and thread over three sets of inequalities. Join@@ just flattens the list for Solve.

Length@Solve[Join@@Thread/@{Tr/@(t=f~Array~{q=(l=Length)@#2,l@#})<=#2,2^Range@q.t<=#,t>=0},Integers]&

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Mathematica 139 bytes

Tr@Boole[k=Length[a=#]+1;AllTrue[a-Rest[##+0],#>=0&]&@@@Tuples[BinCounts[#,{2r~Prepend~0}]&/@IntegerPartitions[#,All,r=2^Range@k/2]&/@#2]]&

Try it online

Explanation: Partitions each of the ri into powers of 2 and then makes all tuples with one decomposition into powers of two for each integer, subtract the column totals from the list of the si. Count the number of tuples that make all remaining entries are positive.

\$\endgroup\$
  • 2
    \$\begingroup\$ typically it's discouraged to answer your own challenge until others have submitted in that language already. \$\endgroup\$ – HyperNeutrino Jan 18 '18 at 2:05
  • \$\begingroup\$ @HyperNeutrino I can delete it if you think that's a good idea. This isn't super carefully golfed, so it's very likely others can do better. \$\endgroup\$ – Hood Jan 18 '18 at 2:51
  • 3
    \$\begingroup\$ While it's not a bad thing to be able to prove it's solvable, I don't recommend spoiling the solution so quickly. Maybe wait for a week first or something. \$\endgroup\$ – Erik the Outgolfer Jan 18 '18 at 12:18
  • \$\begingroup\$ So should I delete it or leave it now that I posted it? \$\endgroup\$ – Hood Jan 18 '18 at 17:00
  • \$\begingroup\$ I would leave it. Pace Erik I don't think it spoils anything: the existence of a solution is obvious from the fact that the matrices respecting the column sum constraint are finite and easily generated. \$\endgroup\$ – Peter Taylor Jan 18 '18 at 17:14

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.