Math shortcuts in problems should not be allowed

Back to General discussions forum

coldnorth     2016-07-11 06:05:04

Hi all,

I noticed a few problems such as "Duel Chances" that have a mathematical shortcut to find the answer with a short formula. I chose not to look calculate the formula as this would mean spending more than half of time working on equations as opposed to coding. As coding is the point of this excercise, implementing a coding solution that adding incremental probabilities until the sum converges would be more intersting. These types of problems should be eliminated or changed slightly. For example this problem could have the probablity for each player chosen randomly from a pool of values, e.g. instead of .30 for player A, it could be one of [.30, .42, .19]

Quandray     2016-07-12 06:12:01
User avatar

While writing code to solve a problem, the main aim is to get the correct answer. A secondary aim is for the code to produce the answer quickly. With some problems, the only way to get code to produce an answer quickly, is to find a shortcut.

Mohamed Aziz     2016-07-12 21:50:59
User avatar

Is coming up with a clever solution considered cheating now ? By the way I solved the problem with the same solution you stated but after seeing others code I feel humiliated because I have a weak mathematical background and maybe because I'm dumb?

Matthew Cole     2016-07-14 16:41:18

There are two problems with this proposal:

  • Feasibility
  • Intent

Feasibility

Consider that in order to ban mathematical tricks, we would have to have some way to spot said mathematical tricks. The Code Abbey code evaluation tool does not give us the ability to do that. All it does is consume an input, and compare the canonical solution's output to your output. If they match, you've solved the problem.

There's no way to verify the means of how the problem was solved. If you don't believe me on this, go to this problem, copy and paste the following into the your solution: box...

ἡμεῖς τοίνυν οὔτε αὐτοὶ μετ᾽ ὀνομάτων καλῶν, ὡς ἢ δικαίως τὸν Μῆδον καταλύσαντες ἄρχομεν ἢ ἀδικούμενοι νῦν ἐπεξερχόμεθα, λόγων μῆκος ἄπιστον παρέξομεν, οὔθ᾽ ὑμᾶς ἀξιοῦμεν ἢ ὅτι Λακεδαιμονίων ἄποικοι ὄντες οὐ ξυνεστρατεύσατε ἢ ὡς ἡμᾶς οὐδὲν ἠδικήκατε λέγοντας οἴεσθαι πείσειν, τὰ δυνατὰ δ᾽ ἐξ ὧν ἑκάτεροι ἀληθῶς φρονοῦμεν διαπράσσεσθαι, ἐπισταμένους πρὸς εἰδότας ὅτι δίκαια μὲν ἐν τῷ ἀνθρωπείῳ λόγῳ ἀπὸ τῆς ἴσης ἀνάγκης κρίνεται, δυνατὰ δὲ οἱ προύχοντες πράσσουσι καὶ οἱ ἀσθενεῖς ξυγχωροῦσιν.

And then directly compute the answer, placing that in Your answer:. The checker will tell you that you have solved the problem, even though your "source code" was an excerpt from Thucydides' Melian Dialogue

It turns out that even if the checker gave us some sort of means to examine the source code, determining which algorithm was used is a tough problem to solve. There has been considerable research in trying to determine similarity between two pieces of source code at the instruction level (called Measure of Software Similarity, or MOSS). My current research includes detecting design patterns in source code. Nonetheless, even the most advanced of these solutions is not able to identify solutions at the algorithm level reliably.

Intent

As Quandray pointed out, sometimes being clever is the goal. For example, consider that in cryptography modular division is frequently used, but if the modulus is a power of 2, applying bitwise arithmetic is much faster (modular division is an expensive operation at the instruction level). x mod 2^n == x & ((2^n) - 1))

Likewise, in this problem, it is possible to use some sort of set builder with an iteration tool to generate every ticket, then compute the value of each half ticket, then discard unsatisfactory tickets. But when you try to apply the same strategy to this problem's advanced version, you'll quickly become overcome by the size of the input. You have to solve the advanced version of the problem using dynamic programming or some similar math trick.

But I thought I was learning programming, not math!

At sufficiently advanced levels, computer science is math. My research field involves analyzing source code and optimizing compililation infrastructure to apply security transformations to the original program. Although I work with millions of lines of code, I think in the last six months I've written maybe a couple-hundred lines of code myself. Most of my work happens on a chalkboard!

This isn't to say that if you write a brute force algorithm to solve a problem here that you've done wrong, or haven't learned as much. Instead, view refactoring as an opportunity to more thoroughly understand a problem and the language of your choice. I encourage you to look at others' solutions and compare methodology to yours.

Besides, learning how to brute force a problem's solution, then seeing the elegant direct computation using combinatorics or calculus will help you better understand how the elegant solution might have been derived by a mathematician. If you don't believe me, check out Project Euler. Although the problems can all be solved by computer program, most were solved initially by a mathematician on paper!

Goodwin Lu     2016-07-24 01:08:47

I find it interesting that there is even research on what is similar to the legendary "plagiarism" problem posed on CodeEval.

Please login and solve 5 problems to be able to post at forum