Painter puzzle - algorithmic estimation from first principles

Question

This problem is based on a puzzle by Joel Spolsky from 2001.

A guy "gets a job as a street painter, painting the dotted lines down the middle of the road." On the first day he finishes up 300 yards, on the second - 150, and on the 3rd even less so. The boss is furious and demands an explanation.

"I can't help it," says the guy. "Every day I get farther and farther away from the paint can!"

My question is, can you estimate the distance he covered in the 3rd day?

One of the comments in the linked thread does derive a precise solution, but my question is about a good enough estimation -- say, 10% -- that is easy to make from the general principles.

clarification: this is about a certain method in analysis of algorithms, not about developing an algorithm, nor code.

Empurple

Answer 1

There are a lot of unknowns here - his walking speed, his painting speed, for how long does the paint in the brush last...

But clearly there are two processes going on here. One is quadratic - it's the walking to and fro between the paint can and the painting point. The other is linear - it's the process of painting, itself.

Thinking about the 10th or even the 100th day, it is clear that the linear component becomes negligible, and the process becomes very nearly quadratic - the walking takes almost all the time. During the first few minutes of the first day, on the contrary, it is close to being linear.

We can thus say that the time t as a function of the distance s follows a power law t ~ s^a with a changing coefficient a = 1.0 ... 2.0. This also means that s ~ t^b, b = 1/a.

Applying the empirical orders of growth analysis:

The b coefficient between day 1 and day 2 is approximated as

    b(1,2) = log (450/300) / log 2 = 0.585     ;; and so,
    a(1,2) = 1/b(1,2) = 1/0.585 = 1.71

Just as expected, the a coefficient is below 2. Going for the time period between day 2 and day 3, we can set it approximately to the middle value between 1.71 and 2.0,

    a(2,3) = 1.85                    ;; a = 1.0 .... 2.0
    b(2,3) = 0.54                    ;; b = 1.0 .... 0.5
    s(3)   = s(2) * (3/2)^b(2,3)
           = 450 * (3/2)^0.54
           = 560 yards

Thus the distance covered in the third day can be estimated as 560 - 450 = 110 yards.

What if the a coefficient had the maximum possible value, 2.0, already (which is impossible)? Then, 450*(3/2)^0.5 = 551 yards. And for the other extreme, if it were the same 1.71 (which it clearly can't be, either), 450*(3/2)^0.585 = 570.

This means that the estimate of 110 yards is plausible, with an error of less than 10 yards on either side.

Empurple

Answer 2

considering four assumptions :-

painting speed = infinity

walking speed = x

he can paint only infinitly small in one brush stroke.

he leaves his can at starting point.



The distance he walks for painting dy road at y distance = 2y

Total distance he walks = intgeration of 2y*dy = y^2 = y^2

Total time he can paint y distance = y^2/x

Time taken to paint 300 yards = 1 day

(300)^2/x = 1

x = 90000 yards/day

Total time he can paint distance y = y^2/90000


(y/300)^2 = 2      after second day

y = 300*2^(1/2) = 424

Day 1 = 300
Day 2 = 424-300 = 124
Day 3 = 300*3^(1/2)-424 = 520 - 424 = 96

Ans : 300/124/96  assuming the first day its 300 

Triadelphous

"assuming the first day its 300 " - there's no assuming; I state that it's 300 in 1st day, and 150 in 2nd. 300/124/96 follows quadratic rule; it means infinite painting speed - seems not likely. – Empurple

@WillNess then what is the speed of painting not mentioned there & there is assuming because the question is asking give me set of numbers which appear to be correct there can be many such number without giving proper information – Triadelphous

the question asked here is different from the one on the linked page, it is only based on it. the question here gives you 2 numbers and is asking for the third. – Empurple