Tag Info

7

Python, N = 7 Using variable neighborhood search over elementary row and column operations. Not every seed works quickly (or at all?), but seed 9 finds a solution for N = 7 in a few seconds. $time python3 search.py 7 9 [[0 3 6 6 1 6 6] [0 1 5 5 0 5 5] [1 3 1 2 1 8 1] [0 0 1 0 0 1 0] [1 7 9 9 0 9 9] [1 3 1 1 1 0 1] [0 0 1 1 0 1 1]] [[5 5 1 1 0 4 0] [... 5 APL (Dyalog Classic), 59 bytes {a b c d←⍵⋄l,2 1∘.○¯3○b÷⍨a-⍨l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d} Derivation of formula for eigenvalues:$$det|A-\lambda I|=0 \\ det\left|\begin{pmatrix} a & b \\ c & d \end{pmatrix}- \begin{pmatrix} \lambda & 0 \\ 0 & \lambda \end{pmatrix}\right|=0 \\ det\left|\begin{pmatrix} a-\lambda & b \\ c & d-\lambda ... 4 Wolfram Language (Mathematica), 23 bytes MatrixRank@*Differences Try it online! Alternative: (23 bytes, 21 characters) MatrixRank[#&@@#-#]& Try it online! SingularValueDecomposition in Mathematica is already 26 bytes long. 4 MATL, 12 bytes t1Y)-X$&Yvoz Input is a matrix, where each row defines a point. Try it online! Or verify all test cases. Explanation The code uses the singular value decomposition of a matrix, which is done symbolically to prevent floating-point issues. The rank of a matrix equals the number of non-zero singular values. t % Implicit input: matrix of ...

3

N = 2 This is a naive brute force approach in R: randomvalid <- function(N) { while (T) { X <- matrix(sample(10,N*N,T)-1,N) if (sum(X==0) < N*N/2 && qr(X)$rank == N) return(X) } } tryforever <- function(N) { i <- 1 while (T) { i <- i + 1 if (i %% 100000 == 0) print(sprintf("after %d tries...",... 3 APL (Dyalog Extended), 19 bytes {×/-∊(⍳≢⍵)↓¨↓∘.-⍨⍵} Dfn producing the pairs, then taking the product. ↓∘.-⍨⍵ all pairs (with repeats) (⍳≢⍵) range from 1 to the length of the input ↓¨ drop 1 2 3 4... elements to avoid repeats -∊ flatten and negate ×/ take the product Try it online! 2 JavaScript (Node.js), 121 119 117 115 101 bytes A=>(F=(a,t,r)=>{a--?A[t].map((x,i)=>F[i]=F[i]||F(F[i]=a,i,a%2?r:r*x/(a+2))):s+=r})(A.length,s=0,1)||s Try it online! Explanation & Ungolfed function hafnian(A) { // Main function taking an array return ( F = function( // Helper function, and also a temporary ... 2 JavaScript (ES6), 187 bytes There's probably a much shorter way. This is using the matrix rank method. m=>m[m=m.map(r=>r.map((v,i)=>v-m[0][i])),n=0].map((_,i)=>(R=m.find((r,k)=>r[i]&&r[j=~k]^(r[j]=1)))&&m.map(r=>++j*r[i]&&R.map((v,k)=>r[k]-=k>i&&v*r[i]),n++,R=R.map((v,k)=>k>i?v/R[i]:v)))|n Try ... 2 Julia 0.7, 18 bytes m->rank(m.-m[:,1]) Try it online! Analogous approach in R is slightly longer (3 bytes saved by Giuseppe): R, 27 24 bytes function(m)qr(m-m[,1])$r Try it online!

2

APL (Dyalog Unicode), 17 bytes ≢⍸1≠1+2⊃8415⌶2-⌿⎕ Try it online! Happens to be a mix of existing MATL and Mathematica solutions. Performs Singular Value Decomposition on pairwise differences of the rows, and counts nonzero eigenvalues in the result of SVD. Since APL does not have symbolic computation, we use "significantly different from zero" ...

2

N = 4, Swi-Prolog After all the math, my best result so far is a relatively naive solution in prolog. :- use_module(library(clpfd)). % N is the dot product of lists V1 and V2. dot(V1, V2, N) :- maplist(product,V1,V2,P), my_sumlist(P,N). product(N1,N2,N3) :- N3 #= N1*N2. my_sumlist([], 0). my_sumlist([H|T], N) :- my_sumlist(T, X), N #= X + H. my_scamul(_, ...

1

Julia, 9 I identify a class of full rank matrices for which the criterion A*B = 10A + B can be checked in constant time, nxn-matrices of the form a b b b . . . b b a b b . b b a b . b b b a . . . . . . . . a b b . . . . . b a Then I do a random search for those matrices in this class ...

1

JavaScript (Node.js), 87 86 bytes f=A=>A[0]?A[0].reduce((y,x,i)=>i&&y+x*f((g=B=>B.filter((_,j)=>j&&i-j))(A).map(g)),0):1 Try it online! This is a port of Kirill's algorithm, and this turns out to be shorter than the naive approach! However I'm retaining my original answer and posting this as a separate one. Explanation f = A =...

1

R, 98 86 bytes function(x,y,+=array)aperm(apply(x,1:2,*,y)+c(w<-dim(y),v<-dim(x)),c(1,3,2,4))+v*w Try it online! Reimplementation of .kronecker and outer for matrices. I do think there's a golfier approach out there, maybe using apply? 6 bytes golfed using apply and array thanks to Dominic van Essen! The builtins are %x% for kronecker(A,B,"*&...

1

Husk, 12 9 bytes ΠΣ→½∂↔´Ṫ- Try it online! (Apparently the only one of the three which was correct) -3 bytes by calculating difference instead of pairs. Explanation ΠΣ→½∂↔´Ṫ- Ṫ- cartesian difference of pairs of the array ´ double: f x = f x x ↔ reverse ∂ take antidiagonals →½ halve and take the last part (triangle) Σ ...

1

Desmos, 10+39=49 bytes n=a.length \prod_{i=1}^n\prod_{j=i+1}^n(a[j]-a[i]) View it in Desmos There's not a lot to be golfed here other than "caching" a.length in an array, but I would like to point out that Desmos can handle the ... notation in arrays!

1

05AB1E, 6 bytes η-€¨˜P Try it online! Commented: η # prefixes of the input - # subtract those from the input € # for each sublist: ¨ # remove the last element (i=j) ˜ # flatten the list P # take the product There are a few alternatives at the same length, such as ηõš-˜P.

1

Japt v1.4.5, 8 bytes à2 ®rnÃ× Try it (includes all test cases) à2 ®raÃ× :Implicit input of array à2 :Combinations of length 2 (using v1.4.5 avoids a bug here in later versions) ® :Map r : Reduce by n : Inverse subtraction Ã :End map × :Reduce by multiplication

Only top voted, non community-wiki answers of a minimum length are eligible