1

I've been given a problem in which a function is fed in A and B. These are target numbers from 1, 1, whereby B may only increase by A and A may only increase by B (Ex, 1 1 -> 2 1 or 1 2. 2 1 -> 3 1 or 2 3. 2 3 -> 5 3 or 2 5). This creates a binary tree. In the problem, given the target numbers, I need to find the "minimum" number of generations that have passed to reach that number, or if the number is possible to reach (for example, 2 4 is impossible to reach). Here's the solution I've come up with, and it's passing every test case I throw at it:

import math

def answer(M, F):
    m = int(M)
    f = int(F)
    numgen=0
    if f==1 and m==1:
        return "0"
    while f>=1 and m>=1:
        if f > m:
            m, f = f, m
        if f==1:
            return str( numgen + m - 1 )
        if m>f:
            numgen += math.floor( m / f )
            m = m % f
    return "impossible"

I'm semi-code-golfing it, and I feel like my solution is highly elegant and fairly efficient. Everything I throw at it within ten generations is correct, and if I throw large numbers (upper limits are stated to be 10^50th on inputs), those work just fine as well. When submitted and run against unknown test cases, three of the five fail. In essence, my question is more wanting to know what kinds of cases fail here.

I have a few assumptions I can't prove but am fairly certain are accurate:

  • There are no duplicates within the binary tree. I haven't found any cases, and I suspect it's mathematically proveable.
  • The tree's right and left halves can be mirrored without affecting the number of generations - this one's actually pretty proven.
  • There is only one route to reach any given combination (a property of binary trees where there are no duplicates) - This relies on assumption 1, but if assumption 1 is true, then this must also be true.
  • One of the two numbers is always a prime. This doesn't really affect the algorithm, and I haven't proven it, but it always seems to be the case. An interesting tidbit.

Where is this solution wrong?

Bioniclegenius
  • 129
  • 12
  • can it be something as stupid as the `int(M)` returning a `TypeError` for example? – Ma0 Sep 20 '16 at 15:09
  • Unfortunately, no. The inputs are always positive integers contained within strings, and guaranteed to be valid. They aren't throwing bad inputs at it. Furthermore, they do inform me if an exception is thrown, and no exceptions are being hit. – Bioniclegenius Sep 20 '16 at 15:10
  • 1
    how about printing the input they are throwing at it to see the cases in which it fails? – Ma0 Sep 20 '16 at 15:11
  • Tried, doesn't work. Nothing is displayed back to me except if a test case passes or fails, or an exception is thrown. Or, of course, if the program times out - time limit is ten seconds. Used to have an issue with that in earlier versions of my solution, it's passing easily now. – Bioniclegenius Sep 20 '16 at 15:12
  • do you have a link from which we can look at the problem description because i don't quite get it yet.. – Ma0 Sep 20 '16 at 15:17
  • Here's a pastebin of the full description: http://pastebin.com/wAfBFRNs – Bioniclegenius Sep 20 '16 at 15:18
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/123801/discussion-between-bioniclegenius-and-ev-kounis). – Bioniclegenius Sep 20 '16 at 15:23
  • You say, "One of the two numbers is always a prime." That is incorrect. Consider (1,1) -> (1, 2) -> (1, 3) -> (1, 4). Neither 1 nor 4 are prime. – rossum Sep 20 '16 at 15:26
  • Where are you submitting this? I'd like to try it there myself... – Stefan Pochmann Sep 20 '16 at 15:51
  • It's Google's foobar thing. You sadly can't get in without them inviting you, and the problems are all randomized. – Bioniclegenius Sep 20 '16 at 16:05

2 Answers2

2

You didn't say whether you're using Python 2 or Python 3, but the math.floor( m / f ) only makes sense in Python 3. There the m / f is a float, which is imprecise. You'd better simply use integer division: numgen += m // f. An example where it matters is M, F = str(10**30), '3', where you compute 333333333333333316505293553666 but with integer division you'd get 333333333333333333333333333335.

Stefan Pochmann
  • 27,593
  • 8
  • 44
  • 107
  • This actually nailed it. I wasn't aware this was a difference in Python, assuming that math.floor() would always return an int, but changing that one line fixed all the test cases I was failing before. – Bioniclegenius Sep 20 '16 at 16:06
  • @Bioniclegenius In Python 3, `math.floor` does always return an int. But the problem is **the division**, so **the input** to `math.floor` is already wrong. And if it's wrong by more than 0.5, you got a problem. – Stefan Pochmann Sep 20 '16 at 16:13
  • In what way? Shouldn't int(float) be the same as cutting off after the decimal of the float? That's where I'm getting a little confused about the difference. – Bioniclegenius Sep 20 '16 at 16:15
  • Okay, now this is getting weirder and weirder. 10**17/7-10**17//7 isn't even less than one, it's 2.0. Doesn't that mean that there's an error in Python somewhere? The math should still be approximately the same. – Bioniclegenius Sep 20 '16 at 16:19
  • 1
    @Bioniclegenius Because floats don't have arbitrary precision. The first 15 or so digits should be correct, but after that it's "random". For example, `10**30 // 3` is 333333333333333333333333333333 but `10**30 / 3` is 333333333333333316505293553664. – Stefan Pochmann Sep 20 '16 at 16:19
  • Oh, that is brilliant. So it's just that python doesn't store enough bits for the mantissa or something. – Bioniclegenius Sep 20 '16 at 16:20
  • 1
    @Bioniclegenius Yeah, the usual. See http://stackoverflow.com/questions/588004/is-floating-point-math-broken if you don't know it yet. – Stefan Pochmann Sep 20 '16 at 16:21
  • That is absolutely something I will keep an eye out for in the future. Expect me to never have this kind of mistake again! – Bioniclegenius Sep 20 '16 at 16:21
1

Your solution was too complicated for what it is in my honest opinion. Take a look at this:

def answer(M, F):
    my_bombs = [int(M), int(F)]
    my_bombs.sort()
    generations = 0
    while my_bombs != [1, 1]:
        if my_bombs[0] == 1:
            return str(generations + my_bombs[1] - 1)
        if my_bombs[0] < 1 or my_bombs[0] == my_bombs[1]:
            return "impossible"
        print(my_bombs, generations)
        n = my_bombs[1] // my_bombs[0]
        my_bombs[1] -= my_bombs[0] * n
        generations += n
        my_bombs.sort()
    return str(generations)
Ma0
  • 15,057
  • 4
  • 35
  • 65