4
\$\begingroup\$

A polynomial over a variable x is a function of the form

p(x) = anxn + an-1xn-1 + ... + a1x + a0

where a0 ... an are the coefficients. In the simplest case, the coefficients are integers, e.g.

p1(x) = 3x2 + 4x + 1

By allowing the coefficients to be polynomials over another variable, we can define polynomials over multiple variables. For example, here is a polynomial over x whose coefficients are polynomials over y with integer coefficients.

p2(x,y) = (2y + 1)x2 + (3y2 - 5y + 1)x + (-4y + 7)

However, we often prefer to write these fully expanded as

p2(x,y) = 2x2y + x2 + 3xy2 - 5xy + x - 4y + 7

Your task is to write a program that will pretty-print a given polynomial in this format.

Input

Your program will receive a single line on standard input* describing a polynomial over multiple variables in the following format.

<name> <variables> <coefficients>
  • <name> is one or more arbitrary non-whitespace characters.
  • <variables> is one or more characters between a and z inclusive, each representing a variable. There are no duplicates, but note that the order is significant, as it affects how the terms should be ordered in the output.
  • <coefficients> is one or more coefficients, separated by spaces, in order of increasing degree.

Each coefficient is either an integer in the usual base 10 notation, or another list of coefficients between square brackets. The different variables correspond to the nesting level of the coefficients, with the "outermost" list corresponding to the first variable and so on. The number of nesting levels will never exceed the number of variables.

For example, the polynomials p1 and p2 above can be represented as follows.

p1 x 1 4 3
p2 xy [7 -4] [1 -5 3] [1 2]

Since constant polynomials can be interpreted as polynomials over any set of variables, some polynomials may be written in multiple ways. For example, the coefficients of p3(x,y,z) = 4 can be written as 4, [4] or [[4]].

Output

Your program should pretty-print the input polynomial on standard output* in the following format.

<name>(<variables>) = <terms>
  • <name> is the name of the polynomial as received.
  • <variables> is the list of variables in the order received, interspersed with commas.
  • <terms> are the terms of the fully expanded polynomial, formatted according to the rules below.

  • Each term is an integer coefficient followed by powers of each variable in the order defined in the input, all separated by a single space. The general format is <variable>^<exponent>.

  • The terms are sorted by the exponents of the variables in decreasing lexicographical order. For example, 3 x^2 y^4 z^3 should come before 9 x^2 y z^13 because 2 4 3 > 2 1 13 lexicographically.

  • Omit terms where the integer coefficient is zero, unless the whole polynomial is zero.

  • Omit the integer coefficient if its absolute value is one, i.e. write x instead of 1 x, unless this is a constant term.

  • When the exponent of a variable in a term is zero, omit the variable from that term.

  • Similarly, when the exponent of a variable is one, omit the exponent.

  • The terms should be separated by + or - signs, with a space on each side, according to the sign of the integer coefficient. Similarly, include the sign in front of the first term if it's negative.

Examples

Input                             Output
================================  =======================================================
p1 x 1 4 3                        p1(x) = 3 x^2 + 4 x + 1
p2 xy [7 -4] [1 -5 3] [1 2]       p2(x,y) = 2 x^2 y + x^2 + 3 x y^2 - 5 x y + x - 4 y + 7
p3 xyz [4]                        p3(x,y,z) = 4
foo bar [0 2 [0 1]] [[3] [5 -1]]  foo(b,a,r) = - b a r + 5 b a + 3 b + a^2 r + 2 a
quux y 0 0 0 0 0 1337             quux(y) = 1337 y^5
cheese xyz [[0 1]]                cheese(x,y,z) = z
zero x 0                          zero(x) = 0

Winning criteria

This is code golf. The shortest program wins. Standard code golf rules apply.

Bonus challenge

Write another program which does the reverse operation, i.e. takes the pretty-printed output of your original program and gives you back one of the possible corresponding inputs. This is purely for bragging rights and has no effect on your score.

* If your chosen programming language doesn't support standard input/output, you may specify how I/O is handled.

\$\endgroup\$
  • \$\begingroup\$ Did I misunderstand or is the bonus challenge impossible? There are many ways to ugly-print a pretty polynomial. \$\endgroup\$ – Superbest May 2 '12 at 20:10
  • \$\begingroup\$ @Superbest: Any ugly version of the polynomial will do. I've added a clarification. \$\endgroup\$ – hammar May 2 '12 at 20:13
  • \$\begingroup\$ Does appending "+1-1" not constitute a trivial solution? \$\endgroup\$ – Superbest May 2 '12 at 20:16
  • \$\begingroup\$ @Superbest: Read the specification of the input format (which your current program doesn't support). \$\endgroup\$ – hammar May 2 '12 at 20:17
  • \$\begingroup\$ Your p1 and quux examples are inconsistent. p1 doesn't have brackets and quux does. Which is right? \$\endgroup\$ – Keith Randall May 2 '12 at 23:32
2
\$\begingroup\$

Mathematica:

Expand[Input[]] // TraditionalForm

will produce the expanded form.

Example input:

(2y + 1)x^2 + (3y^2 - 5y + 1)x + (-4y + 7)

Into the input prompt, click OK. Observe pretty output.

\$\endgroup\$
2
\$\begingroup\$

Python, 323 chars

I=raw_input().split()
print'%s(%s) ='%(I[0],','.join(I[1])),
def P(L,p,f):
 if type(L)==list:
  for i in range(len(L))[::-1]:P(L[i],p+[i],f);f=0
 elif L or f:A=abs(L);print'+-\0-'[2*f+(L<0)]+[(' %d '%A)[f:],' '][A==1and sum(p)>0]+' '.join([v,v+'^%d'%e][e>1]for v,e in zip(I[1],p)if e),
P(eval('['+','.join(I[2:])+']'),[],1)
\$\endgroup\$
  • \$\begingroup\$ Your sorting is wrong: p yx [0 1] 1 gives y x, should be x y. Also spaces aren't 100% - p x 1 -2 gives p(x) = -2 x + 1, p x 0 1 gives p(x) = x. \$\endgroup\$ – ugoren May 6 '12 at 7:28
0
\$\begingroup\$

Python, 252 460 chars

Significantly longer than Keith Randall's, but matches the specifications better.
I copied type(o)==list from Keith. There are other similarities, but they were reached independently.
Sensitive to whitespace in the input. Particularly, space after [ or before ] breaks it.

e=lambda o,v,p:type(o)==list and[x for y in [e(c,v[1:],p+[(v[0],i)])for i,c in enumerate(o)]for x in y]or[(o,p)]
def f(x,y):z=" ".join(("%s^%d"%(a,b),a)[b<2]for a,b in y if b);return "+-"[x<0]+(" %d "%abs(x)," ")[z>"" and abs(x)==1]+z
l=raw_input().split()
t=" ".join(f(*x)for x in sorted(e(eval("["+",".join(l[2:])+"]"),l[1],[]),key=lambda x:[-dict(x[1]).get(a,0)for a in l[1]])if x[0])or'0'
print"%s(%s) = %s"%(l[0],",".join(l[1]),t[2*(t[0]=='+'):])

Logic:
Build a list of numbers/lists by replacing whitespace with commas and using eval (so 1 [2 3] becomes eval("[1,[2,3]]").
e converts the nested lists to a single list, with elements list (3,[('x',2),('y',1)]) (for 3 x^2 y).
I sort the list, with a key function that converts ('x',2),('y',1) to 2,1, by lexicographical order.
f prints each element in the list, preceded with +/-, and considering ones and zeros.
Just before printing, a preceding + is removed.

\$\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.