Bioniclegenius Bioniclegenius - 4 months ago 35
Python Question

Mathematical algorithm failing but seems correct

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)
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?


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.