4
\$\begingroup\$

I wrote a simple Polynomial class:

class Polynomial
  def initialize(coefficients)
    @coefficients = coefficients.reverse
  end

  def to_s
    return '0' if @coefficients.all?(&:zero?)
    @coefficients.map.with_index do |k, index| 
      " #{Polynomial.sign(k)} #{k.abs}x^#{index}"
    end.reverse.join.strip          # removes whitespace at the front
    .gsub(/\A\+\s/, '')             # removes + if first coefficient is positive
    .gsub(/x\^0/, '')               # removes x to the power of 0
    .gsub(/\s(\+|-)\s0x\^\d/, '')   # removes 0 coefficients
    .gsub(/\s(\+|-)\s0/, '')        # removes 0 at the end of the expression
    .gsub(/\^1/, '')                # removes power of 1
    .gsub(/1x/, 'x')
  end

  def evaluate(x)
    @coefficients.map.with_index { |k, index| k * (x**index) }.reduce(0, :+)
  end

  private

  def self.sign(integer)
    integer >= 0 ? '+' : '-'
  end
end

There are a few things that bother me in the to_s method:

  1. Is it bad that I wrote the short comments explaining what each gsub does? Bad in terms of "Would you do this in production code?".
  2. Since all but one of the gsubs do the same, I could replace them with a single gsub, containing a long regexp with lots of ors (|):

    .gsub(/\A\+\s|x\^0|\s(\+|-)\s0x\^\d|\s(\+|-)\s0|\^1/, '')
    

    In that case though the regexp become quite unreadable. Which of the two is better?

  3. Regarding the map.with_index part:

    • I use do/end, but than the chaining of methods on the end doesn't look good.
    • If I use curly braces on multiple lines, I break the convention curly braces for single-line blocks, do/end for multi-line blocks.
    • If I use curly braces with a single-line block, the line will be more than 80 characters long. So which of the three variants would you use?
\$\endgroup\$
  • 1
    \$\begingroup\$ some bugs: a power of x^10 will be replaced with x0, just like 11x will be replaced with 1x. In other words you never account for multi digit coefficients or powers \$\endgroup\$ – ratchet freak Dec 12 '13 at 9:34
  • \$\begingroup\$ @ratchetfreak, thanks for noticing that, I corrected my code. \$\endgroup\$ – Alex Popov Dec 12 '13 at 10:20
  • \$\begingroup\$ The "removes 0 coefficients" substitution leaves junk for terms where the power is greater than 9. \$\endgroup\$ – 200_success Jan 13 '14 at 17:38
2
\$\begingroup\$

Is it bad that I wrote the short comments explaining what each gsub does?

In my opinion, no. Given the complexity Regular Expressions can reach, it is wise to comment them in one way or the other so that somebody who can not instantly parse/read Regular Expressions at least gets a faint idea what it is doing.

Which of the two is better?

Personal preference, I fear. If the Regular Expression is self-explaining/obvious there's no need to comment it, but that's seldom the case, so we should comment on them. There are two possibilities, do it like you did, or copy the Regular Expression into a comment and split and document it there.

In your case, given that you only would join the Regular Expressions together with or, you do not gain anything by making it one big, so I consider your split-approach a very elegant and valid solution.

As I never did Ruby I can't review your code any further, sorry. See this is as a long comment.

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think it's personal preference. For example, the \A anchor in the second .gsub() is not the same as the \A anchor in the first .gsub(). Furthermore, separate substitutions would be much more readable. \$\endgroup\$ – 200_success Jan 13 '14 at 17:44
3
\$\begingroup\$

Rather than construct the polynomial string incorrectly, then fix it with regex's, it may be easier to contruct it directly. This is one way you could do that.

class Polynomial
  def initialize(coefficients)
    @coefficients = coefficients
  end

  def to_s
    coeffs = @coefficients.each_with_index.select { |c,k| c.nonzero? || k==0 }.reverse
    coeffs.each_with_object('') do |(c,k), s|
      cneg = (c.to_f < 0.0)
      if [c,k] == coeffs.first
        s << '-' if cneg
      else
        s << (cneg ? ' - ' : ' + ')
      end
      s << "#{c.abs}" unless (c.abs.to_f == 1.0 && k > 0)
      s << "x" if k > 0
      s << "^#{k}" if k > 1
    end
  end
end                   

coefficients = [2.1, 3, 1.0, 0, -6.1, 1, -5.3, 0.2]
p Polynomial.new(coefficients).to_s
  # => 0.2x^7 - 5.3x^6 + x^5 - 6.1x^4 + x^2 + 3x + 2.1

For this example value of coefficients, this is what's happening:

First save each coeffient's index with its value:

a = @coefficients.each_with_index
  # => [[2.1,0], [3,1], [1.0,2], [0,3], [-6.1,4], [1,5], [-5.3,6], [0.2,7]] 

Next, select only pairs for which the value is non-zero or the exponent is zero:

b = a.select { |c,k| c.nonzero? || k==0 }
  # => [[2.1, 0], [3, 1], [1.0, 2], [-6.1, 4], [1, 5], [-5.3, 6], [0.2, 7]]

Notice that [0,3] has been removed. Now reverse the elements of the array:

coeffs = b.reverse
  # => [[0.2, 7], [-5.3, 6], [1, 5], [-6.1, 4], [1.0, 2], [3, 1], [2.1, 0]]

each_with_object('') creates an empty string, designated s in the block. It is then a simple matter to consider each element of each term in the polynomial to build up the string.

I'm not certain if I followed the formatting rules exactly, but if I did not, it should be easy to modify the code to conform.

(Edited to fix boo-boos spotted by @200_success.)

\$\endgroup\$
  • \$\begingroup\$ Polynomial.new([1]).to_s evaluates to an empty string. Also, Polynomial.new([0, 1, 0]) produces ` + x`. \$\endgroup\$ – 200_success Jan 13 '14 at 9:17
  • \$\begingroup\$ Polynomial.new([0]).to_s also evaluates to an empty string. \$\endgroup\$ – 200_success Jan 13 '14 at 18:30
2
\$\begingroup\$

your evaluate can be made a bit more efficient by reversing and using a straight reduce:

  def evaluate(x)
    @coefficients.reverse.inject(0){ | res, coef | res * x + coef }
  end

this works because a4*x^4+a3*x^3+a2*x^2+a1*x^1+a0*x^0 is equivalent to (((((a4)*x+a3)*x+a2)*x+a1)*x+a0)

this avoids the ** power operation

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

I agree with @CarySwoveland that you should build the string correctly instead of manipulating it with string substitutions afterwards. However, I would make one exception to strip a + from the leading coefficient using a string substitution because it's simple and robust in the case of degenerate situations where it takes some work to determine the leading coefficient, such as @coefficients = [0, 1, 0].

I'd write it this way:

  def to_s(var='x')
    return '0' if @coefficients.all?(&:zero?)
    @coefficients.each_with_index
      .find_all { |coeff, power| coeff != 0 }
      .reverse    
      .map do |coeff, power|
        (
          (coeff == -1 && power != 0) ? '- ' :
          (coeff == +1 && power != 0) ? '+ ' :
          (coeff < 0) ? "- #{-coeff}" : "+ #{coeff}"
        ) + (
          case power
            when 0; ''
            when 1; var
            else;   "#{var}^#{power}"
          end
        )
      end
      .join(' ')
      .sub(/\A\+ /, '')
  end
\$\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.