Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
All Math solution in Speedy category for Feed Pigeons by macfreek
#!/usr/bin/env python3.2
# -*- coding: utf-8 -*-
from math import pow, sqrt, ceil
def cuberoot(x):
"""Return the cubic root of x. Assumes x>=0."""
return x**(1.0/3.0)
def triangular(t):
"""Return the triangular number of t. See http://oeis.org/A000217."""
return t * (t-1) // 2
def tetrahedral(t):
"""Return the tetrahedral number of t. See http://oeis.org/A000292."""
return (t * (t+1) * (t+2)) // 6
def checkio(food):
"""Amount of food needed to feed all pigeons at a given time t:
t=1: pigeons=1 food=1 (0+1)
t=2: pigeons=3 food=4 (1+3)
t=3: pigeons=6 food=10 (4+6)
t=4: pigeons=10 food=20 (10+10)
t=5: pigeons=15 food=35 (20+15)
t=6: pigeons=21 food=56 (35+21)
t=7: pigeons=28 food=84 (56+28)
t=8: pigeons=36 food=120 (84+36)
Thus:
pigeons(t) = t * (t+1) / 2 (the triangular numbers, http://oeis.org/A000217 in OEIS)
food(t) = food(t-1) + pigeons(t) = t * (t+1) * (t+2) / 6.
(These form the Tetrahedral numbers. see http://oeis.org/A000292)
Given the amount of food, we like to know at what time step we run out.
For that, we need to solve this cubic polynomial for t:
food = t * (t+1) * (t+2) / 6 => t^3 + 3*t^2 + 2*t - 6*food = 0
The exact solution to this problem is:
t = cuberoot(u) + cuberoot(v) - 1
with:
u = 3*food + y
v = 3*food - y
y = squareroot(9 * food^2 - 1/27)
t = (3*f + sqrt((3*f)^2 - 1/27))^(1/3) + (3*f - sqrt((3*f)^2 - 1/27))^(1/3) - 1
Unfortunately, an issue with this (exact) solution is that it is rather
prone to rounding errors, especially for (very) large values of food.
Instead, we will make an estimate of t:
t >≈ cuberoot(6*food + 1) - 1
and
t < cuberoot(6*food + 1)
Thus, we can easily leaving two options for t, and use
food = t * (t+1) * (t+2) / 6
to get the exact solution.
We can estimate the lower boundary using
t * (t+2) = (t+1)^2 - 1
and
t > 0
Thus:
6*food = t * (t+1) * (t+2) = (t+1)^3 - (t+1) <≈ (t+1)^3 - 1
t >≈ cuberoot(6*food + 1) - 1
We can estimate the upper boundary using:
t > 0
3*t^2 + 2*t + 1 > 0
t^3 + 3*t^2 + 2*t > t^3 - 1
6*food > t^3 - 1
t^3 < 6*food + 1
t < cuberoot(6*food + 1)
It can be shown that the lower boundary is off by at most 0.0871133,
for food = 0.922607.
Thus:
t > cuberoot(6*food + 1) - 1
t <= cuberoot(6*food + 1) - 1 + 0.0871133
Since you are reading this anyway, let's calculate this upper boundary,
and see if it really is only 0.0871133 higher than the lower boundary.
This problem can be reduced to finding the lowest possible value for x,
for which the following equation always holds (with t > 0 and x > 0):
t <= cuberoot(6*food + 1) - 1 + x
(t+1-x) <= cuberoot(6*food + 1)
(t+1-x)^3 <= 6*food + 1
6*food >= (t+1-x)^3 - 1
t^3 + 3*t^2 + 2*t >= (t+1-x)^3 - 1
t^3 + 3*t^2 + 2*t >= t^3 - 3*t^2*x + 3*t^2 + 3*t*x^2 - 6*t*x + 3*t - x^3 + 3*x^2 - 3*x + 1 - 1
3*t^2*x - 3*t*x^2 + 6*t*x - t + x^3 - 3*x^2 + 3*x >= 0
3x*t^2 + (6x - 3x^2 - 1)*t + (x^3 - 3*x^2 + 3*x) >= 0
This is a simple second-degree polynomial. To calculate the x for which
this is true, we first want to know the value of t for which this formula
is at a local minimum. To do this, we find where the derivative of the
above is 0, and fill in this solution into the equation:
Derivative:
6x*t + (6x - 3x^2 - 1) = 0
t = x/2 - 1 + 1/(6*x)
Putting this into the formula:
3x*(x/2 - 1 + 1/(6*x))^2 + (6x - 3x^2 - 1)*(x/2 - 1 + 1/(6*x)) + (x^3 - 3*x^2 + 3*x) >= 0
which reduces to:
( 3*x^4 - 6*x^2 + 12*x - 1 ) / ( 12*x ) >= 0
Using x > 0:
3*x^4 - 6*x^2 + 12*x - 1 >= 0
It is possible, though non-trivial, to solve a quartic equation.
Without further ado, this is the exact solution:
x = 1 / sqrt( 6 / (4-cbrt(46) + 6*sqrt( 6 / (2+cbrt(46)) ) ) ) - sqrt( 1 / 6 (2 + cbrt(46)) ) ≈ 0.087113
with sqrt the square root and cbrt the cubic root.
Amound of time and food needed to feed pigeon p:
p=1: t=1 food=1
p=2: t=2 food=3
p=3: t=2 food=4
p=4: t=3 food=5
p=4: t=3 food=7
p=4: t=3 food=8
p=5: t=3 food=9
p=6: t=3 food=10
p=7: t=4 food=17
p=8: t=4 food=18
p=9: t=4 food=19
p=10: t=4 food=20
p=11: t=5 food=31
p=12: t=5 food=32
p=12: t=5 food=33
p=12: t=5 food=34
p=12: t=5 food=35
p=12: t=6 food=36
p=12: t=6 food=55
p=12: t=6 food=56
p=12: t=7 food=57
p=12: t=7 food=83
p=12: t=7 food=84
p=12: t=8 food=85
p=12: t=8 food=119
p=12: t=8 food=120
p=12: t=9 food=121
"""
def time_from_food(food):
"""
Given an amount of food, return the timestamp at which will be depleted.
"""
# Estimate the time step. This is a lower boundary.
time = ceil((6*food + 1)**(1/3.0) - 1)
# Check if the estimate if good or too low.
food_needed = tetrahedral(time)
if food > food_needed:
# estimate is too low. Add 1.
return time + 1
else:
return time
time = time_from_food(food)
food_previous = tetrahedral(time - 1)
previous_pigeons = triangular(time)
# In the previous round 'previous_pigeons' have been fed.
# In this round (food - food_previous) food is available,
# and thus food - food_previous pigeons are fed.
# The highest of the two is the number of different pigeons
# that have been fed.
feeded_pigeons = max(food - food_previous, previous_pigeons)
return feeded_pigeons
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio(1) == 1, "1st example"
assert checkio(2) == 1, "2nd example"
assert checkio(5) == 3, "3rd example"
assert checkio(10) == 6, "4th example"
assert checkio(11) == 6, "5th example"
assert checkio( 0) == 0
assert checkio( 1) == 1
assert checkio( 2) == 1
assert checkio( 3) == 2
assert checkio( 4) == 3
assert checkio( 5) == 3
assert checkio( 9) == 5
assert checkio( 10) == 6
assert checkio( 11) == 6
assert checkio( 19) == 9
assert checkio( 20) == 10
assert checkio( 21) == 10
assert checkio( 22) == 10
assert checkio( 34) == 14
assert checkio( 35) == 15
assert checkio( 36) == 15
assert checkio( 55) == 20
assert checkio( 56) == 21
assert checkio( 57) == 21
assert checkio( 83) == 27
assert checkio( 84) == 28
assert checkio( 85) == 28
assert checkio( 100) == 28
assert checkio( 119) == 35
assert checkio( 120) == 36
assert checkio( 121) == 36
assert checkio( 1000) == 153
assert checkio( 10000) == 741
assert checkio(100000) == 3486
April 2, 2014
Comments:
