Coding Challenge #2 – Polynomial

in coding-challenge •  7 years ago  (edited)

Welcome to the second Coding Challenge.

Here I will post a coding challenge every few days that you can solve. There will be easy ones and hard ones, pretty mixed.

How does it work?

  • Try to solve the challenge in whatever language you find fitting
    • You can use a new language you always wanted to learn or show off your golfing skills
  • Post a comment with a link to your code (use https://repl.it or similar sites that allow execution of your code) and some info on how the code works or what is remarkable
  • Optional: Create a post with the tag #coding-solution
    • In that post walk other users through the process of solving your challenge. That way they can learn and try it out on the next one
  • Optional: Read and review other peoples code, try to find bugs, give feedback and learn

Why even bother?

  • Training is everything, the more you train your mind to think in code, the better you are prepared
  • You may learn a few new tricks from reading other solutions
  • I will send tips for really good solutions (and use the liquid rewards of this post for it too)
  • You may get recruited if someone likes your code (f.e. I am looking for talents)

Challenge #2 – Polynomial

This challenge will be an interesting one, easy to do but hard to get right.

Wikipedia context: https://en.wikipedia.org/wiki/Polynomial

Implement a Polynomial class taking an a string formula that abides to these specifications:

  • parse the polynomial given as a string, f.e. +1x^0 -5x^1 +3x^2
  • implement a few methods, add, substract, multiply, divide
  • implement the standart to-string method of you language to give back a polynomial in above format

Remarks:

  • The format is pretty easy to parse. If you want a challenge, try accepting more loose polynomials like 1+2x or 3x^{12}-6 x^2.
  • Try adding more methods, derive and integrate will be fun.
  • Bonus points for:
    • handling edge cases
    • good coding practices and modularity
    • useful and meaningful tests
    • beautiful (readable, self-documenting) code

Please keep the #coding-challenge tag clean of solutions.

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

Here you go:
https://steemit.com/coding-challenge/@philosophist/coding-challenge-2-polynomial

Hope that fits a good bit of what you were looking for @reggaemuffin

Definitely :)

  ·  7 years ago (edited)

Haha, you said the next challenge would be a bit harder than FizzBuzz, but this is quite the brain teaser. I'm not even sure if I'm going to fully implement it, but I'm working on a solution that's definitely going to take me a while.

Expect a post about it though, it's definitely good practice and I'm having fun solving this one.

My main problem right now is parsing the input and output in more loose styles, omitting things like x^0.

A few tips: Only the first + can be omitted, so after that a + or - is a delimiter. if no x is present, use x^0 and if x is present, use x^1.

so I would first split by +I- and then work on each number. If you want to allow x^{-1} then ignore +I- inside {}. Each number can be split at the x and the left part is the number, the right part (if exist) the x^y.

I'll be keeping this challenge on for a bit so you have time to complete it :)

Thanks for the hints! I actually got the input parsing solved already, clean output is almost done but I'm moving on to the problem of adding now. Making progress :)

Thanks....... upvote and follow

I've only implemented the parsing. The code is accessible at https://repl.it/KQWN. Since I used a parsec library, you cannot run it there. :/

I don't parse the variable names, so it's possible to use multiple variables mistakenly.

poly.png

This is pretty cool! Can you elaborate a bit on what language you used, how you build up the grammar etc.?

There are three parsers related to polynomials: poly term and number.

Line 15: All parsers remove the trailing spaces, so the main parser poly should remove the leading whitespace. It basically states: skip the whitespace, poly is made of many terms and you arrive to the end of the input.

Line 18: term is a tuple of a number and another number. The second number is located after an identifier and the symbol ^.

Line 21-25: number is either negative or positive. <|> stands for either. For the second case the number may not start with the sign +, option takes care of that. f computes the value of the string of numbers.

Line 28: We run the parser poly on the sample input. It prints out the result as a tuple of terms as indicated in the parser descriptions.

Thank you for the explanation! Parsec is really strong, looking forward to leaning more about it :)

It is and I'm using it in very basic form. There're very good documents at https://github.com/haskell/parsec

I implemented showPoly, add, subtractPoly, and multiply functions.

poly2.png

Oh snap, the simplify looks crazy! It would be so cool if you could make a post explaining how each little piece works in many details, once you are finished.

There are basically three transformations.

  1. sortOn snd poly
    poly is a list of tuples of two numbers for each polynomial term's coefficient and power. First step sorts the list of tuple by its second element which is power.
  2. groupBy ...
    We group all terms by their power. groupBy returns a list of lists. Each list represent a power value.
  3. map f
    For each list of lists we foldl the list which is basically reducing the list to a single value. For instance if we have 5x^2-3x^2+x^2 it evaluates to 3x^2.

Once you get used to functional programming, most things will look very clear. ;)
Take a look: http://learnyouahaskell.com

I would agree.

meep

beep loves coding ? :D

meep

  ·  7 years ago 

I think this is Functional Programming.....
looks like Haskell or F#... not sure.

Checking the author is is most likely Haskell, that was the language he submitted the last challenge in.

It's Haskell. The links provide the information but it wasn't clear at first sight.

Whew, all done. Here's my post about it: https://steemit.com/coding-solution/@pilcrow/javascript-solution-coding-challenge-2-polynomial

It became pretty long, but as it's the first complete answer maybe it could help other developers out?

I am looking forward to see some Solutions. Unfortunately this is above my head.

@raggaemuffin I'm not sure what you are asking us to code here. We take a string that is a polynomial, change it to a math code, and then return the same string we started with? Are we factoring, simplifying, solving, or plugging in a solution value for x?

I understand it like this:

  1. you get a polynomial (like described) and parse it.
  2. implement functions 'add', 'subtract', ... etc.
  3. implement toString() method (to see the result of implemented operations).

Am I correct on this one?

So, does it come with a second input to plug in for x, then?

@bandli is correct. You get a string representation of a polynomial and should implement a class that parses that and allows to fo math with it:

a = Polynomial('3x^2')
b = Polynomial('5x^4')
c = a.multiply(b)
c.toString => '15x^6'

If you want to have an evaluate method that could be fun too

It might help a lot if you have one or two examples like this in your post, so we can include them in our test cases. It makes understanding the problem at hand a bit easier. In the real world I would say "specifications unclear" and send it back to the Product Owner ;)

You are right! I wanted to post it and probably should have refined the specification a bit before that. Next challenge I'll see to make up to that

Oh! You want us to create a polynomial class and return an object of that given polynomial! Is that it?

I want you to create a polynomial class that has a constructor accepting a string :)

Wonderful topic I hope to follow up https://steemit.com/@safamostaafa

wow....very interesting,i just started learning coding a few weeks back.still learning html and css .i hope to participate in subsequent one.let see how this one goes.

42

This post is very steady and interesting, also very useful ....

This is so cool..I'm starting my coding academy in September...I hope to participate in future challenges ^_^

dude give us some real world challenges not academic intellectual masturbation on nonsense math challenges from introduction courses on programming

If you want to implement http://www.wolframalpha.com/ then I have bad news for you ;)

Ok, you proved your googling skills, but... can you code?

I already told my opinion on this kind of challenge. its unnecessary intellectual masturbation and its like reinventing the wheel for what?

and yet they're useful for improving your thought processes and being able to do stuff in code that isn't 're-inventing the wheel'.

In a workplace, sure you go and find code that does what you want that is available for use so you don't re-invent solutions that others have already come up with and done the work on, but only because it's quicker than just writing it yourself.

When you're trying to improve your knowledge base though, be it learning a new language or doing stuff you haven't done before, one of the best ways is to do these sort of exercises, and reading how others do them.

But if we're just too beginner level coders, maybe you should educate us with your solutions to them so those trying to learn something can.

Or provide some kind of description about how numpy's solution works and why it's a good way of doing things even rather than just running down reggaemuffin's initiative that clearly says it will have some easy and some hard challenges.

Or you could run your own challenges if you think these are too academic and not real world enough

Thank you! Exactly what was on my mind, have a tip!

Hi @ratticus! You have just received a 0.5 SBD tip from @reggaemuffin!

From @reggaemuffin : If You Like What I Do, Vote Me For Witness :)


@tipU quick guide | How to check your pending payouts.

This is awe-inspiring.

You've got an incredible gift.

  ·  7 years ago (edited)

What about fun? Also from time to time new ways to do things can be found. Even the wheel gets reinvented.

However, I would also like to see some more applicable real world stuff. I get your point.

Why don't you suggest a real world challenge? Open for suggestions what to do next so if you have a certain direction you want to go to, tell me.

Ah, so

import polynomial

lol

Let me see if I can get my skills out of storage. Seems pretty straightforward will look at it later.

Looking forward to seeing your solution :)

I was looking into some challenges and found this one. My first reaction was lets do this! Then, after reading my snake tail was already in a knot! I sucked at math and I sure as hell can't code or anything close to that! The only code I ever used was to make letters dance on the screen in repeat. Something with 10 go to 20.... Thats about how far my knowledge goes. Never the less I upvoted because I think challenges are amazing! Me as an art, poet sometimes weird snake need to take my hat off for those who can solve this!
Good luck!