11
\$\begingroup\$

I'm doing some programming challenges over at CodeEval and came across a pretty straight forward simple one:

Given numbers x and n, where n is a power of 2, print out the smallest multiple of n which is greater than or equal to x. Do not use division or modulo operator.

So the input looks something like this: 13, 8 first number being x second number being n. My first instinct was to use a while loop and return the result of multiplying the number once the loop hits the correct result, so:

 8 * 0 = 0
 8 * 1 = 8
 8 * 2 = 16; break because it's greater then 13

My question is, is it considered bad form to use float("inf") instead of a set number to multiply up to?

import sys


def multiply(x, y):
    max_multiple_try = 0
    while max_multiple_try != float("inf"):
        res = x * max_multiple_try
        if res != x and res >= y:
            return res
        else:
            max_multiple_try += 1


if __name__ == '__main__':
    with open(sys.argv[1]) as data:
        for line in data.readlines():
            numbers = line.rstrip().split(",")
            print(multiply(int(numbers[1]), int(numbers[0])))
\$\endgroup\$
  • \$\begingroup\$ What are the serious problems that you expect? \$\endgroup\$ – Nikolas Rieble Nov 17 '16 at 16:50
  • \$\begingroup\$ @NikolasRieble Well I was actually going back through my idea and I guess me saying "serious problems" doesn't make sense, since the loop ends the second the multiple is higher. \$\endgroup\$ – papasmurf Nov 17 '16 at 16:57
  • \$\begingroup\$ You can make an implicit float('inf') check as in my answer, if you want avoid the explicit one. Is there anything else that you want to change/improve ? \$\endgroup\$ – Nikolas Rieble Nov 17 '16 at 17:00
  • 2
    \$\begingroup\$ This use case just begs for bit twiddling. Drop back to C. (My advice.) :) \$\endgroup\$ – Wildcard Nov 18 '16 at 3:46
  • 1
    \$\begingroup\$ @papasmurf I'm one of those recommending to go on CodeReview when applicable. I do it for the quality of the answers I usually see here, I hope it's not too often taken as a criticism by the poster :-/ \$\endgroup\$ – Aaron Nov 18 '16 at 5:18
10
\$\begingroup\$

Function interface

First of all, it is good that you used a function to contain the code solving the problem!

However, there are some shortcomings:

  • It is very confusing that the function parameter representing \$n\$ from the problem description is named x, and the one representing \$x\$ is named y.

  • The function is badly named, as it doesn't multiply the two arguments. A better name would be smallest_multiple or similar.

  • The function lacks a docstring which describes what it does. It is therefore hard to check if it is implemented correctly. The first sentence of the problem description would make a good docstring (replacing "print out" with "return").

Bug

The function returns the wrong result if both arguments are the same, for example:

>>> multiply(8, 8)
16

But the smallest multiple of 8 which is greater than or equal to 8 should be 8, not 16.

(Maybe you thought that 8 is not considered a multiple of 8?)

The bug is fixed by removing the res != x condition.

Loop exit condition

Let's ignore everything that doesn't affect the max_multiple_try variable:

max_multiple_try = 0
while max_multiple_try != float("inf"):
    …
    if …:
        …
    else:
        max_multiple_try += 1

We can see that it is always an integer (which has unlimited size in Python). Therefore it can never be equal to the special float('inf') value, and the loop could as well have been written using while True: ….

However, as max_multiple_try simply counts the loop iterations, this pattern would be better written as a for loop using itertools.count (and using a simpler and more descriptive name):

from itertools import count
…
for factor in count():  # factor = 0, 1, 2, …
    res = x * factor
    if res >= y:
        return res

Top-level code

Congratulations on using if __name__ == '__main__' and using with to open a file!

Here are some improvements:

  • Iterate directly over data instead of using readlines.

  • Use tuple assignment:

    x, n = line.rstrip().split(",")
    print(multiply(int(n), int(x)))
    

Alternative algorithm

The problem states that the value of \$n\$ is constrained to powers of two. While your solution actually solves the more general problem for any value of \$n\$, this description probably aims for a different algorithm which makes use of the constraint.

Hint: What does the binary representation of powers of two look like? How could you solve the problem if \$n\$ were constrained to powers of ten?

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for making me laugh with the bug, I caught that bug not to long ago and figured it wouldn't get caught. So thank you for that. The interface is a good valid point, I didn't really expect myself to post this, but I thought someone would have some suggestions over float("inf"), I like the tuple idea as well. Great answer, thank you! \$\endgroup\$ – papasmurf Nov 17 '16 at 18:18
  • 2
    \$\begingroup\$ very nice and complete analysis \$\endgroup\$ – Nikolas Rieble Nov 17 '16 at 19:00
2
\$\begingroup\$

As someone hinted before, the 'n' is limited to powers of 2. I'm no python expert, but I assume python ints are 64 bit and that number will be big enough not to worry about overflow. And you certainly don't need floating point.

def findMultiple(maxx, powern):
    res = powern
    while res < maxx:
        res = res + powern;
    return res
\$\endgroup\$
  • \$\begingroup\$ That limits the possible factors of \$n\$ to powers of two and therefore often produces the wrong result! For example, findMultiple(23, 8) gives 32 = 4·8 when it should be 24 = 3·8. \$\endgroup\$ – mkrieger1 Nov 18 '16 at 13:23
  • \$\begingroup\$ @mkrieger1 Perhaps you should read the original question which explicitly states "where n is a power of 2". Read first, call people wrong only after reading! \$\endgroup\$ – Evan Langlois Dec 4 '16 at 12:51
  • \$\begingroup\$ Yes, \$n\$ (you call it powern) is a power of two, but the factors of \$n\$ need not be. For example, given \$n = 8\$ (a power of two), your program will compare 8, 16, 32, 64, 128, etc., to maxx, when it should be comparing 8, 16, 24, 32, 40, 48, etc. \$\endgroup\$ – mkrieger1 Dec 4 '16 at 13:05
  • \$\begingroup\$ @mkrieger Yes, you are right, sorry. Changed answer, but untested \$\endgroup\$ – Evan Langlois Dec 5 '16 at 21:33
1
\$\begingroup\$

If you want to avoid explicitly calling float('inf'), you can bypass it as follows:

def multiply(x, y):
    max_multiple_try = 0

    while True:       

        res = x * max_multiple_try

        if res != x and res >= y:
            return res
        else:
            max_multiple_try += 1

        if res+1 == res: ###implicit float('inf') check

            return 'not found'
\$\endgroup\$
  • 2
    \$\begingroup\$ Since res is an arbitrary-size integer, res + 1 will never be equal to res and you could as well write if False: return 'not found' (or just leave it away). It has nothing to do with the float('inf') value. \$\endgroup\$ – mkrieger1 Nov 17 '16 at 17:02
  • \$\begingroup\$ Yet when I use float('inf') as x in multiply(x,y), then the condition hits and "not found" is returned \$\endgroup\$ – Nikolas Rieble Nov 17 '16 at 17:03
  • \$\begingroup\$ Alright, I understand. That means, that the check in the original question did not make any sense neither? \$\endgroup\$ – Nikolas Rieble Nov 17 '16 at 17:04
  • \$\begingroup\$ Well, if you pass a float value as x then it might actually make sense to compare res to float('inf'), but in the original code max_multiple_try is compared, which is definitely an integer. \$\endgroup\$ – mkrieger1 Nov 17 '16 at 17:07

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.