Teaser 2731: City snarl-up
From The Sunday Times, 25th January 2015 [link]
I had to drive the six miles from my home into the city centre. The first mile was completed at a steady whole number of miles per hour (and not exceeding the 20mph speed limit). Then each succeeding mile was completed at a lower steady speed than the previous mile, again at a whole number of miles per hour.
After two miles of the journey my average speed had been a whole number of miles per hour, and indeed the same was true after three miles, after four miles, after five miles, and at the end of my journey.
How long did the journey take?
[teaser2731]
Frits are discussing. 
John Crabtree are discussing. 
GeoffR are discussing. 
Hugh+Casement and 
S2T2 
Jim Randell 3:02 pm on 13 September 2020 Permalink |
My first program looked at all sequences of 6 decreasing speeds in the range 1 to 20 mph. It was short but took 474ms to run.
But it’s not much more work to write a recursive program that checks the average speeds as it builds up the sequence.
This Python 3 program runs in 50ms.
Run: [ @repl.it ]
from enigma import (Rational, irange, as_int, catch, printf) Q = Rational() # select a rational implementation # check speeds for distance d, give a whole number average check = lambda d, vs: catch(as_int, Q(d, sum(Q(1, v) for v in vs))) # solve for k decreasing speeds, speed limit m def solve(k, m, vs=[]): n = len(vs) # are we done? if n == k: yield vs else: # add a new speed for v in irange(m, 1, step=-1): vs_ = vs + [v] if n < 1 or check(n + 1, vs_): yield from solve(k, v - 1, vs_) # find a set of 6 speeds, not exceeding 20mph for vs in solve(6, 20): # calculate journey time (= dist / avg speed) t = Q(6, check(6, vs)) printf("speeds = {vs} -> time = {t} hours")Solution: The journey took 2 hours in total.
The speeds for each mile are: 20mph, 12mph, 6mph, 5mph, 2mph, 1mph.
Giving the following times for each mile:
And the following overall average speeds:
LikeLike
Frits 1:40 pm on 16 September 2020 Permalink |
With a decent elapsed time.
from enigma import SubstitutedExpression # is average speed a whole number def avg_int(li): miles = len(li) time = 0 # Add times (1 mile / speed) for i in range(miles): time += 1 / li[i] #return miles % time == 0 return (miles / time).is_integer() p = SubstitutedExpression([ "AB <= 20", # no zero speeds allowed "KL > 0", # speeds are descending "AB > CD", "CD > EF", "EF > GH", "GH > IJ", "IJ > KL", # average speeds must be whole numbers "avg_int([AB, CD])", "avg_int([AB, CD, EF])", "avg_int([AB, CD, EF, GH])", "avg_int([AB, CD, EF, GH, IJ])", "avg_int([AB, CD, EF, GH, IJ, KL])", ], verbose=0, answer="(AB, CD, EF, GH, IJ, KL, \ 60/AB + 60/CD + 60/EF + 60/GH + 60/IJ + 60/KL)", env=dict(avg_int=avg_int), # external functions d2i="", # allow number respresentations to start with 0 distinct="", # letters may have same values ) # Solve and print answer for (_, ans) in p.solve(): print("Speeds:", ", ".join(str(x) for x in ans[:-1])) print(f"Minutes: {round(ans[6])}") # Output: # # Speeds: 20, 12, 6, 5, 2, 1 # Minutes: 120@Jim, do you discourage the use of / for division?
Is there a better way to check that a division by a float is a whole number?
I tried divmod(p, r) but sometimes r is close to zero like x E-19.
(miles % time == 0) also failed.
LikeLike
Jim Randell 2:39 pm on 16 September 2020 Permalink |
@Frits
I am careful about my use of / for division, as it behaves differently in Python 2 and Python 3 (and I do generally still attempt to write code that works in both Python 2 and Python 3 – although the day when Python 2 is abandoned completely seems to be getting closer).
But I do tend to avoid using
float()objects unless I have to. Floating point numbers are only ever approximations to a real number, so you have to allow some tolerance when you compare them, and rounding errors can build up in complex expressions. (Python recently addedmath.isclose()to help with comparing floats).On the other hand, I am a big fan of the Python
fractionsmodule, which can represent rational numbers and operate on them to give exact answers. So if I can’t keep a problem within the integers (which Python also will represent exactly) I tend to usefraction.Fractionif possible.(The only problem is that it is a bit slower, but for applications that need more speed
gmpy2.mpq()can be used, which gives a faster implementation of rationals. I might add aRational()function to enigma.py to search for an appropriate rational implementation).LikeLike
Jim Randell 4:46 pm on 16 September 2020 Permalink |
I have added code to enigma.py to allow selecting of a class for rational numbers.
So now instead of using:
You can import the function
Rational()from enigma.py and then use it to select a rational implementation:Setting the
verboseparameter will make it display which implementation is being used.I’ve got
gmpy2installed on my system and this change improved the runtime of my original code from 448ms (usingfractions.Fractionunder PyPy 7.3.1) to 153ms (usinggmpy2.mpqunder CPython 2.7.18).LikeLike