12
\$\begingroup\$

A polynomial is divisible by a factor (x-n) if f(n)=0 for a function f. Your job: to determine if a polynomial function f(x) is divisible by (x-n).

The input

The input is in the form of (x-n), (Polynomial). Remember, if n is negative, (x-n) will be in the input form of (x+n). For the polynomial, all exponents will be put in as ^. Coefficients will be written next to the variable x. An example polynomial could be 2x^2 + x^1. There will be no spaces between anything. The term x will be inputed as x^1. So what would "normally" look like (x - 1) will be (x^1-1). The coefficients and powers will always be integers. The coefficient one will be implicit if it is just x. I.e., x can be interpreted as 1x

The output

A boolean value. Truthy, or Falsey.

Thanks to @AlexA. For helping me clarify this!

Examples

Input:(x^1-1),(x^1-1)
Output: True

Input: (x^1+2),(2x^2+4x^1+2)
Output: False

Input: (x^1+7),(x^2-49)
Output: True

Rules

  • This is , so shortest code in bytes wins

Unfortunately, I don't know how to implement the snippet leaderboard. If anyone knows how, feel free to edit the post.

\$\endgroup\$
15
  • \$\begingroup\$ Will the input be a string with that exact form, i.e. parens around the divisor candidate, a comma with zero or one space, and parens around the polynomial? \$\endgroup\$
    – Alex A.
    Dec 1, 2015 at 0:39
  • 3
    \$\begingroup\$ Possible duplicate \$\endgroup\$ Dec 1, 2015 at 0:39
  • \$\begingroup\$ Definitely not a duplicate of that. \$\endgroup\$ Dec 1, 2015 at 0:40
  • \$\begingroup\$ @intrepidcoder This isn't a duplicate because the question isn't to factor a polynomial. It is to see if a polynomial can be divided by a linear factor. \$\endgroup\$ Dec 1, 2015 at 0:48
  • \$\begingroup\$ Will polynomial coefficients always be integers? \$\endgroup\$ Dec 1, 2015 at 1:15

6 Answers 6

5
\$\begingroup\$

Pyth - 39 bytes

This is a monstrous combination of regexp and eval. I like the approach, but will try to improve the implementation.

It uses the Polynomial Remainder Theorem.

K_sPe:z"-|\+"3!v.ssXPtw,\^\x,"**""*K"\*

Doesn't work online because of eval use.

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

Casio Basic, 19 bytes

judge(mod(b,a)=0

As it turns out, the fx-CP400 can do mod on algebraic expressions!

Polynomial and factor should be entered as expressions. 16 bytes for the code, 3 bytes to enter a,b into the parameter value box.

\$\endgroup\$
1
\$\begingroup\$

MATLAB, 103 99 97 95 93 bytes

I'm trying some different things, and got this to work to save a couple of bytes:

eval([regexprep(input(''),{'.+?1(.+)\),','(\d)x'},{'x=str2num(''$1'');disp(~','$1\*x'}) 41]);

If I can reduce that down even further, I will post an explanation.


Old code an explanation

t=sscanf(input(''),'(x^1%d),%s')';x=-t(1);disp(~eval(regexprep([t(2:end) ''],'(\d)x','$1\*x')))

This also works with Octave. You can try it online. I've save the program as a script named isFactor.m, so you can just enter isFactor at the prompt. [Note: in Octave spits out a warning while running - MATLAB doesn't generate this].

The input must be in the format '(x^1+7),(x^2-49)' as per the question. The quotes marks are added so MATLAB/Octave knows it is a string.

The output is either a 0 or a 1 depending on whether or not it is true or false.


So, the code works as follows. First we request an input, and then parse it. The parsing string extracts the signed number after the first (x^1 in the string - this is our value of n. Then it continues to extract the string (%s) after the ), in the input - this is our expression.

t=sscanf(input(''),'(x^1%d),%s')';

Next, we extract the value of n and set x equal to it - we are going to evaluate whether the expression equals zero when n==x, so this is why we store the value to x. Also we negate the extracted number, because of the minus sign when parsing.

x=-t(1);

We will then display the output which is a boolean

disp(

The output is basically the logical negation of our evaluated equation. If f(x) is zero, this will return 1, otherwise it will result in zero.

     ~eval(

We are evaluating the input expression, but to do this, we need to reformat it slightly so that MATLAB can understand. When we read the string, it is actually an array of double type, so we need to convert that to a character array. Before the conversion we also get rid of the first element as that is what we used for n. We then need to replace any occurrence of x which is preceded by a number (e.g 4x) by the same thing but with a multiplication (*) sign in between so MATLAB can calculate it.

           regexprep(char([t(2:end) ''],'(\d)x','$1\*x')
     )
)
\$\endgroup\$
1
\$\begingroup\$

VBScript, 118 116 bytes

a=inputbox(""):for i=0 to 9:a=replace(a,i&"x",i&"*x"):next:b=split(a,","):x=-eval(b(0)):msgbox not cbool(eval(b(1)))

Since we know that the first part of the input is a linear polynomial, we only need to check if its root matches that of the second polynomial; and we need to prepare the term for eval by inserting * as needed.

\$\endgroup\$
1
\$\begingroup\$

Axiom 77 180 Bytes

f(a:UP(x,INT),b:UP(x,INT)):Boolean==(ground?(a)or ground?(b)=>false;p:=b;r:=a;if degree(a::POLY INT,x)>degree(b::POLY INT,x)then(p:=a;r:=b);(p rem r)$UP(x,FRAC INT)~=0=>false;true)

the previous solution

v(a,b)==(ground?(a) or ground?(b) or (b rem a)$UP(x,FRAC INT)~=0=>false;true)

was wrong because it assume degree(b)>=degree(a) one bug i wrote... test and results

(3) -> f(x^1-1,x^1-1)
   (3)  true
                                                            Type: Boolean
(4) -> f(x^1+1,2*x^2+4*x^1+2)
   (4)  true
                                                            Type: Boolean
(5) -> f(x^1+2,2*x^2+4*x^1+2)
   (5)  false
                                                            Type: Boolean
(6) -> f(x^1+7,x^2-49)
   (6)  true
                                                            Type: Boolean
(7) -> f(1, 1)
   (7)  false
                                                            Type: Boolean
(8) -> f(1, x^2+1)
   (8)  false
                                                            Type: Boolean
(9) -> f(x^8-1, x^2-1)
   (9)  true
                
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 30 bytes

Try it online!

PolynomialRemainder[#2,#,x]<1&
\$\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.