# Paint the rectangle with least movement

There is a painting brush tool that can paint a circle area of $1$ unit radius. What is the shortest paint track for painting at least a $100*100$ units rectangle area on wall? How much did the brush moved in total?

Rules:

• Brush must touch wall only once. (It says that painting should be continues and you have only one shot)
• Painting can start and finish anywhere.
• Painting outside the rectangle does not matter. (Actually it is inevitable to paint some of the outer area of rectangle)

Example:

Here's a naive try for a $10*10$ rectangle and the same brush with radius of $1$ unit result is $58$ units for $10*10$ rectangle and $(n*m)+2m-2$ for $n*2m$ rectangle

• Do you need to 'fill' the 4 corners aswell? Round things don't tend to fill rectangles unless you go outside the borders.. – Tim Couwelier Oct 7 '14 at 8:25
• @TimCouwelier, painting outside the rectangle does not matter. (It is inevitable to paint some of outer area). Thanks – Rafe Oct 7 '14 at 8:31
• Quick heads up as to why I deleted my post: length of a diagonal was not sqrt(2)/2 x side but sqrt(2) x side, which ruined the calculations.. alot. – Tim Couwelier Oct 7 '14 at 9:11
• I don't get it, why would any solution be better than the trivial snake solution that Elgert mentioned? It seems like the length of the path is just a function of how much paint you use, so any solution which minimizes wasted paint works – Ben Aaronson Oct 7 '14 at 12:08
• @Moyli, Exactly! I think Tim thought about sharp tuens that tried to find a spiral path – Rafe Oct 7 '14 at 13:48

The best I can do (so far) is a total track length of 5083.592 (see below).

Update: You can also do away with the final returning curved path in my final solution, which chops off pi/4, so the total length is reduced to 5082.807 • Nicely done! best answer for now... but how did you calculate that number? – Rafe Oct 8 '14 at 6:28
• Is it better to do this spiral path instead of going back and forth? – DarioP Oct 8 '14 at 9:36
• Why do you use circular curves of radius one? I would think the two constraints on the path are that it reach the outside corner, and that it reach the vertical/horizontal lines soon enough to avoid leaving gaps at the inside corner. I would think replacing the two curves with straight (but angled) segments would reduce the required distance. – supercat Jan 12 '15 at 23:44
• Unless I'm missing something, that approach should improve the optimal distance to about 5064.3--a noticeable improvement. – supercat Jan 13 '15 at 0:57
• Yes, you might be right. A while after I made my edit i had the feeling that I got it a bit wrong, but haven't got back to update it. – Penguino Jan 15 '15 at 0:16

I hope this helps you better visualize it • How are you going to fill the gaps shown in this picture: i.imgur.com/6OFDVuo.png – Moyli Oct 7 '14 at 13:02
• wow great - i think thats better than the old 'written' answer! i thought about your path and i find it more and more attractive! (i'll have to check length and compare again, but i like it!!) – Martin Frank Oct 7 '14 at 13:32
• @Moyli that was the same what i was thinking!! but honestly i really like this picture as a base of conversation! – Martin Frank Oct 7 '14 at 13:36
• @Moyli Just move the paint brush up until the gap is gone, then again repeat the diagonal movement inwards – Ben Aaronson Oct 7 '14 at 13:36
• I thought about that. The only problem this method has is that if you start with a diagonal move second line will not cover that easily. – Rafe Oct 7 '14 at 13:44

A solution much better than Penguino's "spiral" can be achieved by starting with Penguino's zig-zag (the one with length 5098) but adjusting it slightly. Looking at the first place the line comes toward the left from the right, it extends all the way to (0,3) and then (0,5) for the purpose of being within one unit of (0,2) and (0,6), but for any x and y in the range (0,1) such that x²+y²≤1, those points could be reached by having the line extend to (1+x,1), (x,2+y), (x,6-y), and (1+x,5) before returning to the right. Penguino's zig-zag is a special case for x=0,y=1 but x=0.6 y=0.8 yields a much better result (assuming the right side is treated similarly, it will reduce the amount of x excursion per row by 1.2, but adds only 0.8 worth of y excursion, with about half of that being on shallow diagonals). The net effect is a total length under 5060.5--a noticeable savings.

The slight tweak used for the above number entails starting at (x,2-y), then moving to (x,y), and going to (1+x,1) and all subsequent points in normal fashion. Note that things must be drawn in that order to avoid leaving an unpainted area on the top. Note also that using slightly different coordinates could improve things a bit, but further improvements are apt to be fairly slight.

if you draw a circle you will be NEVER able to fill the rectangle...

if you FILL circles you might need w/2 x h/2 filled circles (even filled circles) on the first run and then need (w-1)/2 x (h-1)/2 filled circles (odd filled circles) to fill the gaps between... you can 'cut' pathes when you draw a even line and then switch to an odd line...

lenght of even line = 100; length of odd line = 99; path to switch from odd to even (and back) = Math.Squrt(2) (i'll say it's 1.4 for terms of easier use)...

so you have 100 x 100 + 99 x 99 + 99*1.4 = 10'000 + 9801 + 138.6 = 19939.6 (having rounding erros) BLACK  = even circles
RED    = odd circles
PURPLE = rectangle
GREEN  = path


i can't proof that this path would be shorter: ## update:

ok ok, after learning that that paint tool sprays continously i show another path... Draw a cross (starts NorthWest -> SouthEast -> SouthWest -> NorthEast) on step back and then make the loop into the center

• The question says "circle area," not circle. Elgert's solution is 50 x 100 + 49 x 2 = 5098 so almost 4 times shorter. – Moyli Oct 7 '14 at 11:07
• you describe the amount of circled areas - noth the length of the path... – Martin Frank Oct 7 '14 at 11:15
• grml - i put so much effort into this hahahaa.... ok ok, thanks for clearing THAT out ^^\$ – Martin Frank Oct 7 '14 at 11:45
• Don't think the spiral answer works either. Assume the first three lengths to be 98 98 98, then you'll 'bump into' the lines you already had and the next series will be 96 96 96, then 94 94 94 etc etc. In total you'll end up with 3 times the sum of (2;4;6;..;90;92;94;96;98), or 7350, plus the length of the cross, which undoubtedly puts you over the previously mentioned value of 5098. – Tim Couwelier Oct 7 '14 at 12:07
• You're both wrong, actually. It's 98, 98, 98, 96, 96, 94, 94, ... to a total of 4998 (plus or minus a couple units -- I can't tell off the top of my head how the spiral ends.) You can see the idea in this 10x10 square where the pattern is 8, 8, 8, 6, 6, 4, 4, 2, 2: i.imgur.com/ISBhYOw.png – Moyli Oct 7 '14 at 17:43