14
\$\begingroup\$

You have a number of polynomials who are lonely, so make them some companions (who won’t threaten to stab)!

For a polynomial of degree n, there is an n by n companion cube matrix for it. You need to make a function that accepts a list of coefficients for a polynomial in either ascending (a + bx +cx^2 + …) or descending (ax^n + bx^(n-1) + cx^(n-2)+…) order (but not both) and output the companion matrix.

for a polynomial c0 + c1x + c2x^2 + ... + cn-1x^(n-1) + x^n, its companion matrix is 

     (0, 0, 0, ..., -c0  ),
     (1, 0, 0, ..., -c1  ),
     (0, 1, 0, ..., -c2  ),
     (...................),
     (0, 0, ..., 1, -cn-1)

note that the coefficient for x^n is 1. For any other value, divide all the rest of the coefficients by x^n's. Additionally, the 1's are offset from the diagonal.

If the language you’re using already contains a function or module that does this, you can’t use it – you must write your own.

For instance, if you had 4x^2 – 7x + 12, the coefficients in ascending order are (12, -7, 4) and descending order (4, -7, 12). The function or program should output [(0, -3.0), (1, 1.75)] for either order. Specify which order your code accepts. Minimum polynomial should be a quadratic. Coefficients are restricted to real numbers.

Below are examples – your output does not have to match the pretty formatting but it should output the rows (in the ()) of the matrix in order.

Ascending order:

input:
    [3., 7., -5., 4., 1.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [-4., -7., 13.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [23., 1., 92., 8., -45., 88., 88.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

Descending order:

input:
    [1., 4., -5., 7., 3.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [13., -7., -4.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [88., 88., -45., 8., 92.,1., 23.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

Dennis wins with 20 bytes!

Improve this question
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Coefficients are real (not complex), right? \$\endgroup\$
    – Luis Mendo
    Oct 4, 2015 at 3:45
  • 1
    \$\begingroup\$ Are programs valid, or is it functions only? (Keep in mind that restricting the contest to functions disallows interesting langauges without functions.) \$\endgroup\$
    – lirtosiast
    Oct 4, 2015 at 4:17
  • 1
    \$\begingroup\$ What's the minimum degree polynomial we have to account for? \$\endgroup\$
    – Alex A.
    Oct 4, 2015 at 4:19

12 Answers 12

Reset to default
3
\$\begingroup\$

CJam, 23 20 bytes

{)W*f/_,,_ff=1f>\.+}

This is a function that pops the input (ascending order) from the stack and pushes the output in return.

Try it online in the CJam interpreter.

How it works

)   e# Pop the last element from the input array.
W*  e# Multiply it by -1.
f/  e# Divide the remaining array elements by this product.
_,  e# Push a copy of the array and compute its length (L).
,_  e# Push [0 ... L-1] twice.
ff= e# For each I in [0 ... L-1]:
    e#   For each J in [0 ... L-1]:
    e#     Push (I==J).
    e# This pushes the L x L identity matrix.
1f> e# Discard the first element of each row, i.e., the first column.
\   e# Swap the result with the modified input.
.+  e# Vectorized append; append the input as a new column.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

CJam, 32 31 28 bytes

0q~)f/f-_,(_,\0a*1+fm<~]W%z

Try it online

This takes the input in ascending order, using the CJam list format. Sample input:

[-4.0 -7.0 13.0]

Explanation:

0     Push a 0 for later sign inversion.
q~    Get and interpret input.
)     Pop off last value.
f/    Divide all other values by it.
f-    Invert sign of values.
_,    Get count of values, which corresponds to n.
(     Decrement by 1.
_,    Create list of offsets [0 1 ... n-1] for later.
\     Swap n-1 back to top.
0a*   Create list of n-1 zeros.
1+    Append a 1. This is the second-but-last column [0 0 ... 0 1].
fm<   Apply rotation with all offsets [0 1 ... n-1] to column.
~     Unwrap the list of 0/1 columns.
]     Wrap all columns
W%    Invert their order from last-to-first to first-to last.
z     Transpose to get final matrix.
`     Convert to string for output.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

APL, 40 30 bytes

{(-n↑⍵÷⊃⊖⍵),⍨⍉1↓⍉∘.=⍨⍳n←1-⍨≢⍵}

Accepts input in ascending order.

Explanation:

{
                        n←1-⍨≢⍵    ⍝ Define n = length(input)-1
                   ∘.=⍨⍳           ⍝ Create an n×n identity matrix
               ⍉1↓⍉                ⍝ Drop the leftmost column
            ,⍨                     ⍝ Append on the right:
  (-n↑⍵                            ⍝ n negated coefficients,
       ÷⊃⊖⍵)                       ⍝ divided by the n+1st
}

Try it online

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Julia, 43 bytes

c->rot180([-c[2:(n=end)]/c[] eye(n-1,n-2)])

This uses descending order for the input. It constructs the matrix rotated 180 degrees, in order to enable more efficient use of "eye", then rotates the matrix into the right orientation.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Julia, 64 44 bytes

c->(k=c[n=end];[eye(n-=1)[:,2:n] -c[1:n]/k])

Accepts a vector of the coefficients in ascending order.

Ungolfed:

function f(c::Array)
    # Simultaneously define k = the last element of c and
    # n = the length of c
    k = c[n = end]

    # Decrement n, create an n×n identity matrix, and exclude the
    # first column. Horizontally append the negated coefficients.
    [eye(n-=1)[:,2:n] -c[1:n]/k]
end

Try it online

Saved 20 bytes thanks to Glen O!

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

R, 71 59 bytes

Takes input in ascending order.

function(x)cbind(diag(n<-length(x)-1)[,2:n],-x[1:n]/x[n+1])

Ungolfed:

f <- function(x) {
    # Get the length of the input
    n <- length(x)-1

    # Create an identity matrix and exclude the first column
    i <- diag(n)[, 2:n]

    # Horizontally append the negated coefficients divided
    # by the last one
    cbind(i, -x[1:n]/x[n+1])
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Matlab, 66 bytes

function y=f(c)
n=numel(c);y=[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)];

It uses ascending order for the input, with format [3., 7., -5., 4., 1.] or [3. 7. -5. 4. 1.].

Try it online (in Octave).

Example (in Matlab):

>> f([23., 1., 92., 8., -45., 88., 88.])
ans =
                   0                   0                   0                   0                   0  -0.261363636363636
   1.000000000000000                   0                   0                   0                   0  -0.011363636363636
                   0   1.000000000000000                   0                   0                   0  -1.045454545454545
                   0                   0   1.000000000000000                   0                   0  -0.090909090909091
                   0                   0                   0   1.000000000000000                   0   0.511363636363636
                   0                   0                   0                   0   1.000000000000000  -1.000000000000000

If a program is valid (instead of a function), with stdin and stdout:

Matlab, 59 bytes

c=input('');n=numel(c);[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)]
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I think you can do n=numel(c=input('')); \$\endgroup\$
    – lirtosiast
    Oct 4, 2015 at 4:15
  • \$\begingroup\$ @ThomasKwa Thanks! However, that's not valid syntax in Matlab. n=numel(input('')) would be valid, but I need to use c again later \$\endgroup\$
    – Luis Mendo
    Oct 4, 2015 at 4:40
  • \$\begingroup\$ Sorry; it worked in Octave where I tested it. \$\endgroup\$
    – lirtosiast
    Oct 4, 2015 at 4:45
1
\$\begingroup\$

Octave, 45 44 bytes

Assuming c is a column vector with the coefficient of the highest power of x at the end.

@(c)[eye(n=rows(c)-1)(:,2:n),-c(1:n)/c(end)]

Old version:

@(c)[eye(n=numel(c)-1)(:,2:n),-c(1:n)/c(end)]

High five, Julia!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 141 bytes

My own attempt:

def C(p):
 c,r=p.pop(0),range;d=[-i/c for i in p];n=len(d);m=[[0]*n for i in r(n)]
 for i in r(n-1):m[i][i+1]=1
 m[-1]=d[::-1];return zip(*m)

Takes a list of the coefficients in descending order and first builds the transpose of the companion matrix - known for stabbing and being talkative. The return uses zip to produce the transpose of this transpose to get the actual matrix.

>>> C([1., 4., -5., 7., 3.])
[(0, 0, 0, -3.0), (1, 0, 0, -7.0), (0, 1, 0, 5.0), (0, 0, 1, -4.0)]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6) 85

Ascending order.

Test running the snippet below in any EcmaScript 6 compliant browser.

f=c=>alert(c.map((v,i)=>c.map((x,j)=>++j-i?j-c.length?0:-v/m:1),m=c.pop()).join(`
`))

// test
// redefine alert to write into the snippet body
alert=x=>O.innerHTML+=x+'\n'

function test() {
  v=I.value.match(/\d+/g)
  I.value=v+''
  alert(v)
  f(v)
}  

test()
<input value='23.,1.,92.,8.,-45.,88.,88.' id=I><button onclick="test()">-></button>
<pre id=O></pre>

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

TI-BASIC, 50 bytes

Ans→X
List▶matr(ΔList(Ans-cumSum(Ans)),[A]
dim(Ans
augment(augment(0randM(Ans-2,1),identity(Ans-2))ᵀ,[A]∟X(Ans)⁻¹

Takes input in ascending order. Note that this will not work for polynomials of degree <2, because TI-BASIC does not support empty matrices or lists. Pending a ruling from OP, I can fix this at the cost of a few bytes.

First, we store the list into ∟X to use the last element later; then, we calculate ΔList(Ans-cumSum(Ans)), which is just the negated list with the last element chopped off, and convert it to a column vector. Since List▶matr( doesn't modify Ans, we can use the next line to take the dimension of the list, which we use thrice. TI-BASIC doesn't have vertical concatenation, so we need to take transposes and horizontally concatenate. In the last line, [A]/∟X(Ans wouldn't work because matrices can be multiplied by scalars but not divided.

An aside: To generate the row vector of zeros, we take advantage of the rarely useful randM( command. randM( creates a random matrix, but its entries are always random integers between -9 and 9 (!), so it's really only useful to create zero matrices.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 42 bytes

p->concat(matid(#p-1),-p[^#p]~/p[#p])[,^1]

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.