This week the #puzzle is: How Greedily Can You Mow the Lawn? #geometry #area #volume #GreedyAlgorithm (Link at the bottom.)

You’re mowing a circular lawn with a radius of 1 unit. You can mow in straight strips that are 1 unit wide.

The fewest number of passes you would need to mow the entire lawn is two, as shown below. In one pass (shown in blue) you can mow half the circle, and in the second pass (shown in red) you can mow the other half of the circle.

However, instead of minimizing the number of passes, you greedily choose how to orient each pass so it cuts as much of the unmowed grass as possible. A pass doesn’t have to go through the center of the circle and can be in any direction, but must be straight and cannot bend.

With this “greedy” approach, how many passes will it take for you to mow the entire lawn?

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Desmos 1

Let us go through what choices we have.

• Obviously the 1st pass is simply symmetrical, the middle of the pass going through the center. If it didn’t go through the center, it would cover less area. In my model this pass is horizontal.
• The 2nd pass might simply be the same, just in the other direction? It would get a lot of the 2 remaining bits, leaving 4 bits behind. If this pass is indeed vertical, again, the middle of it goes through the center, to cover as much area as possible. This area would be 0.9132. [ETA: Oops, should be 2 * 0.9132. Wrong conclusions follow.]
• Then I would need 2 passes to cover the remaining 4 bits, either 2 horizontal (or vertical) passes, covering 2 bits every time, or 2 passes crisscrossing, one going up, the other going down, again covering 2 bits every time.
• That would be 4 passes in all.
• Can it be done in a better way?
• I need at least 3 passes, because I can’t cover the 2 remaining bits after the 1st pass in just 1 more pass.
• What if the 2nd pass simply covered 1 of the remaining bits? This area turns out to be 0.6142. So this wouldn’t happen, as it is less than 0.9132.
• There’s an interesting option. What if the 2nd pass was tilted just right, so that it wouldn’t create 4 remaining bits, but only 2? This covers an area of 1.0472. Yes! This is indeed possible. A 3rd pass, tilted the other way, would cover the rest.
• I don’t know whether this is exactly the optimal way to do things. But it proves, that 3 passes can do the job.

And for extra credit:

Desmos 2 Researchgate

There’s something interesting going on at Researchgate, suggesting that a non-greedy solution would need at least 20 circles / 10 cylinders. Because the angular radius of each circle is 30^o.

This one is just me guessing most of the way, illustrated in Desmod:

• 1st and 2nd pass are symmetrical, with the middle of the cylinder passing through the center. They are also perpendicular.
• I assume the same goes for the 3rd pass.
• The next 4 passes (red in my model) are closing some gaps on the surface of the sphere between the 3 existing passes. E.g. one of these cylinders has x=y=z in the middle.
• This leaves 8 bits. I would need 4 more passes to cover these, again using cylinders passing through the center.
• Using this method, with the whole surface covered and all cylinders passing through the center, all of the volume has been covered.
• This would suggest 11 passes.

***

How Greedily Can You Mow the Lawn?

This week the #puzzle is: Can You Race Against Zeno? #integration #summation #speed #distance #time (Link at the bottom.)

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Desmos 1 – just to be confusing, the definition of t_Zeno1 here is slightly different.

Let’s look at what we know or define:

• d: the full distance (5 km – all we metric centric people thank you)
• t_init: the time spent running with the initial speed all the way (24 m)
• v₀: the initial speed (d/t_init) (also, t_init = d/v₀)
• a: the increase of speed as a factor (1.1)
• t_Zeno1: the time spent running under the new rule

With these definitions in place, let’s go running.

• Run at v₀ to cover the distance d/2^1. (Half of the distance is run at the initial speed.)
• Then run at v₀ * a to cover the distance d/2². (Half of the remaining distance is run after 1 speed increase.)
• Then run at v₀ * a² to cover the distance d/2³.
• Then run at v₀ * a³ to cover the distance d/2⁴.
• In general run at v₀ * aⁱ to cover the distance d/2ⁱ⁺¹.
• In general spend t_i to cover distance d/2ⁱ⁺¹.
• t_i = d/2ⁱ⁺¹ / (v₀ * aⁱ)
• t_i = (d/v₀) / (2ⁱ⁺¹ * aⁱ)
• t_i = t_init / (2ⁱ⁺¹ * aⁱ)
• t_Zeno1 = Σ_i=0 t_i
• t_Zeno1 = Σ_i=0 t_init / (2ⁱ⁺¹ * aⁱ)
• t_Zeno1 = t_init * Σ_i=0 1 / (2ⁱ⁺¹ * aⁱ)
• To get a good approximation, I can let the upper bound be finite, but growing.
• According to Desmos, t_Zeno1 = 22 m.

But seeing I am so close, maybe I can do this in a better way.

• The general formula for v can be written as
• v(t) = a^{(⌊-log₂(1-t)⌋)} * v₀
• Some examples:
  • v(0) = a^{(⌊-log₂(1-0)⌋)} = a^{(⌊-log₂(1)⌋)} = a^(⌊0⌋) = 1 * v₀
  • v(0.4) = a^{(⌊-log₂(1-0.4)⌋)} = a^{(⌊-log₂(0.6)⌋)} = a⁰ = 1 * v₀
  • v(0.5) = a^{(⌊-log₂(1-0.5)⌋)} = a^{(⌊-log₂(0.5)⌋)} = a^{(⌊-(-1)⌋)} = a * v₀
• Instead of the sum I can use an integral.
• t_Zeno1 = t_init * ∫ ₀¹ 1 / (v(t)/v₀) dd
• Because, for a small distance d_j the contribution to the time is:
• t_j = d_j / v(t_j)
• t_Zeno1 = Σ_{all j} t_j
• t_Zeno1 = Σ_{all j} d_j / v(t_j)
• t_Zeno1 = Σ_{all j} d * d_j/d / v(t_j)
• t_Zeno1 = d * Σ_{all j} d_j/d / v(t_j)
• t_Zeno1 = d * ∫ ₀¹ 1 / v(t) dd
• t_Zeno1 = d * ∫ ₀¹ 1 / (a^{(⌊-log₂(1-t)⌋)} * v₀) dd
• t_Zeno1 = d/v₀ * ∫ ₀¹ 1 / a^{(⌊-log₂(1-t)⌋)} dd
• t_Zeno1 = t_init * ∫ ₀¹ 1 / a^{(⌊-log₂(1-t)⌋)} dd
• qed
• Again, desmos calculates this as the integral being 0.916666666667, therefore t_Zeno1 = 24 m * 0.916666666667 = 22 m.

And for extra credit:

Desmos 2

Again, let’s look at what we know:

• v(t) is the speed at any given time.
• v(0) = v(1-1) = v₀ above.
• v(0.5) = v(1-1/2¹) = v₀ * a
• v(0.75) = v(1-1/2²) = v₀ * a²
• v(0.875) = v(1-1/2³) = v₀ * a³
• In general v(1-1/2ⁱ) = v₀ * aⁱ
• And v(t) is a smooth function.
• This calls for a double log system!
• Let’s try simply plugging in some numbers first in Desmos. Looks good.
• Then let’s try to describe this function.
• v(t) = v_opp(1-t) (running the opposite way)
• v_opp(1/2ⁿ) = v₀ * aⁿ
• v_opp(log₂(t)) = v₀ * a^-log₂(t)
• v(t) = v_opp(1-t) = v₀ * a^-log₂(1-t)
• Double log confirms, just writing it as v(t) = v₀ * (1-t)^-0.137504 instead.
• t_Zeno2 = t_init * ∫ ₀¹ 1 / a^-log₂(1-t) dd
• The value of the integral is 0.879118155787, therefore t_Zeno1 = 24 * 0.879118155787 = 21.0988.

***

Can You Race Against Zeno?

This week the #puzzle is: Can You Squeeze the Bubbles? #circles #geometry #area #minimize (Link at the bottom.)

And for extra credit:

But first. Last week I made a booboo. At some point I began trusting my assumption about the probabilities so much, that I didn’t figure out, why my monte carlo results didn’t line up. This again lead to me saying 2 was the correct answer to the extra credit, when in fact… well, as I said, my monte carlo said something else. Something better. This is a detail from my heat map 5.

The lowest values occur, not in the corner (4), but towards the middle of the side (3). And the ratio is something like 2.7. Earlier heat maps actually showed this more clearly. Here’s the 3d image based on my monte carlo data, and for comparison the other 3d image again:

The important feature is that there’s a dip along the lower edge. Corner low, middle of side lower. Sigh. Anyway. Back to the puzzles from this week.

Highlight to reveal (possibly incorrect) solution:

Desmos live Two Circles Calculator Desmos image

So, here’s the big assumption: The best possible choice for the next center is to tuck it as far into the previous circle(s) as possible. 2nd center goes on the periphery of the 1st. 3rd center goes where the 2 first circles cross each other, into the little “fjord”. Etc. See model on Desmos.

(This is among other things assuming, that being on the periphery, being a distance of 1 from the center, isn’t being inside the circle.)

The next question then is: What is the area of this figure? Looking at the image, we have 7 circles. But then we have to subtract 6 green figures, so as not to double count. And 6 blue figures twice. And 6 black figures 3 times. (Also note, 1 green figure = 1 orange figure + 2 black figures; 1 blue figure = 1 orange figure + 1 black figure.)

Area of circle: π 1² = π = 3.14159.

Area of overlap between 2 circles, like the middle circle and the one to the right of it – this is also 2 orange figures and 5 black figures: From Two Circles Calculator, 1.22837.

Area of black figure: From Two Circles Calculator, 0.18122.

Area of orange figure: (1.22837 – 5 * 0.18122) / 2 = 0.161135.

Area of blue figure: 0.161135 + 0.18122 = 0.342355.

Area of green figure: 0.161135 + 2 * 0.18122 = 0.523575.

Area of the whole figure: 7 * 3.14159 – 6 * 0.523575 – 2 * 6 * 0.342355 – 3 * 6 * 0.18122 = 11.479.

And for extra credit:

Desmos image

It’s actually easier to look at hexagons and triangles. Each hexagon consists of 6 triangles. Each triangle is actually part of 3 hexagons. Therefore adding 1 hexagon only contributes 6/3 = 2 new triangles.

The area of such 2 triangles is √ 0.75 = 0.8660. The function f(N) is therefore 0.866 * N.

Test: Going from 7 circles in the above fiddler to 19 (in a symmetrical way) adds 12 circles. The area grows by 3 orange figures and 5 black figures for each new circle “on a corner” and 2 orange figures and 3 black figures for each new circle “on an edge”. This is on average 2.5 * 0.161135 + 4 * 0.18122 = 1.1277175. As N goes up, the edge circles will dominate. An edge circle contributes 2 * 0.161135 + 3 * 0.18122 = 0.86593. QED.

***

Can You Squeeze the Bubbles?

Og vi skal selvfølgelig også betragte Hugo-finalist-novellerne fra i år.

Allerede noget bedre at vælge mellem. “Three Faces of a Beheading” blev i mit hoved et godt stykke tid, så det er min favorit.

Anmeldelse af “Three Faces of a Beheading” (gratis), af Arkady Martine. Novelle. 2024. Hugo-finalist.

Skitse: En mulighed for et computerspil er, at en enkelt spiller kan have et stort publikum. Det kan derfor også have stor betydning, når en spiller gør noget usædvanligt. I et autoritært samfund gør noget forbudt, noget farligt.

Er det science fiction? Jeps.

Temaer: Det omtalte spil er baseret på noget historisk. Der var en gang en kejser og et oprør. Noget historisk kan fortælles på forskellige måder. En historikers forsøg på at få mening i, hvad der egentlig skete, kan føre et nyt sted hen. Hvad var folks motiver? Hvem havde alliancer? Hvad er fortællingen her? Hvis der er en.

Hvis man ønsker at sige noget om sin samtid, så kan man også vinkle noget historisk på en passende måde.

Min fornemmelse er, at forfatteren er intelligent og veluddannet (fx er der fodnoter til novellen) og har valgt en indviklet metode. Bl.a. er der pudsige skift mellem 1. og 2. person. Jeg læste novellen 2 gange, for at være nogenlunde sikker på det hele.

Er det godt? Ja. Ja, det er det egentlig. 👽👽👽

Anmeldelse af “Stitched to Skin like Family Is” (gratis), af #NghiVo. Novelle. 2024. Hugo-finalist.

Skitse: Sommeren ’31 kan det godt være lidt indviklet at være kinesisk i Illinois, USA. Således også for hende her, der i øvrigt er rigtig god til at lappe tøj og sy det om. (I får mig ikke til at skrive omf*randre! Jeg gør det ikke!) Hun kan også få noget ud af at lytte til tøj. Og så leder hun efter sin bror.

Er det science fiction? Aldeles ikke. Fantasy.

Temaer: Hun kan noget med tøj og sko, specielt hvis hun har haft fat i det før.

Så mærker hun også racisme.

Er det godt? Hm. Det var jo et indviklet spørgsmål. Jeg gættede ikke det hele fra første linje. Jeg har sympati med hovedpersonen. Tjo. 👽👽👽

Anmeldelse af “Marginalia”  (gratis), af #MaryRobinetteKowal. Novelle. 2024. Hugo-finalist.

Skitse: Her til lands er snegle kæmpestore, og man kan sagtens dø af at møde dem eller deres fodspor af syre. Margery skal på en eller anden måde håndtere, at hendes lillebror helt vildt gerne vil se sneglen, og at deres syge mor helst ikke må være alene.

Er det science fiction? Nej. Fantasy.

Temaer: Der går klassekamp i det her. Baronen mener, at han gør det så godt. Men passer han faktisk godt på sine tidligere ansatte? Ved han, hvad de har brug for? Og forstår han godt, at dem “under ham” kan være klogere og mere intelligente?

Er det godt? Ja. Der blev dog ved med at være underlige ting i teksten. Fx at Margery tilsyneladende brygger øl og vasker tøj samtidig. Men alligevel. 👽👽👽

This week the #puzzle is: Can You Weave the Web? #geometry #trigonometry #probability (Link at the bottom.)

A spider weaves a web within a unit square (i.e., a square with side length 1) in the following haphazard manner:

First, the spider picks two points at random inside the square. In particular, it picks the points “uniformly,” meaning any point is equally likely to be picked as any other point.

Next, the spider connects the two points with a strand of silk and extends the strand to two sides of the square. For example, here is a web made of 10 silk strands that were picked as described:

Within the unit square, which point (or points) is most likely to be on a new strand of silk, whose two defining points have not yet been picked?

(While the probability that any specific point winds up being precisely on the new strand is zero, some points and regions are nevertheless more likely to be on the strand than others.)

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Program 1 Program 2 Desmos Heat map 1, 2, 3, 4, 5, 6. 3d image.

Okay, this was a tough one.

The main realization here is: Given the 2 points, the longer the line segment within the square is, the higher the number of points on the segment. So, for any given point I can ask, what lengths of line segments do we have, systematically going all the way around the point? This can again be changed to, what is the distance to the square going all away around the point? The longer the sum of the lengths of the segments, the higher the probability a given point was hit. The sum of the lengths evolves in an area.

The area only tells me something about the probabilities compared to each other! I don’t actually calculate any probabilities directly.

For the fiddler, Desmos just supplied a picture of what was going on. For extra credit I got some useful numbers. I construct a graph for “what is the distance between this point and the square, in all possible directions”. Then I calculate the area under the graph for one turn around the possible angles. Experimentation shows, the area is somewhere between 1.76274717407 and 3.52549434808. (Feel free to play around with model.) The max seems to be right in the middle of the square, and the min in the corners.

In order to be sure of my numbers I use the monte carlo method in program 1. Construct a lot of lines. For each line, note which parts of the square it goes through. (I have subdivided the square into smaller squares.) Again, I get the same max and min positions, and it points towards the middle and the corners of the square.

Finally in program 2 I use the integral method to calculate (more) exact numbers. Max is in smack dab (0.5, 0.5).

As max I get 3.5254943481 and as min 1.7627475763. The ratio is 1 / 0.5000001141 = 1.999999544. I feel pretty confident saying it is actually 2.000. The Desmos numbers confirm this.

I also constructed some fun heat maps of the situation, and a 3d image. And one of my programs hates the number 14?

***

Can You Weave the Web?

This week the #puzzle is: How Long Is the River? #probability (Link at the bottom.)

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Program 1

First the gung-ho approach.

If we’re way out on a long line, everything is very, very random and evenly distributed. It’s therefore safe to assume, we’ve landed on a position somewhere in the sequence “aaa bbbb ” (a 3 letter word, a space, a 4 letter word). Of these 9 characters, 2 are spaces. The probability of landing on a space is 2/9 = 0.222.

Then a slightly more sober approach.

• p(n) is the probability the nth character in the line is a space
• p(1) = 0
• p(2) = 0
• p(3) = 0
• With probability 0.5, the first space is either in position 4 or 5
• p(4) = 0.5
• p(5) = 0.5
• If there’s a space 4 positions away, with p(n-4), and then a 3 letter word, p = 0.5 or a space 5 positions away, with p(n-5), and then a 4 letter word, p = 0.5, then there’s a space at position n
• p(n) = p(n-4) * 0.5 + p(n-5) * 0.5
• p(6) = 0
• p(7) = 0
• p(8) = 0.5 * 0.5 + 0 = 0.25
• p(9) = 0.5 * 0.5 + 0.5 * 0.5 = 0.5
• p(10) = 0 + 0.5 * 0.5 = 0.25
• p(11) = 0
• p(12) = 0.125
• p(13) = 0.375
• p(14) = 0.375
• p(15) = 0.125
• p(16) = 0.0625

And then I plug the formula into a program. p(1000) = 0.222. And that’s the result.

And for extra credit:

Program 2

Probability that the river has length 1, because line 2, position 13 wasn’t a space: 1 – p(13) = 1 – 0.375 = 0.625.

Probability … 2, because line 3, position 14 wasn’t a space: p(13) * (1 – p(14)) = 0.375 * 0.625 = 0.234.

Probability … 3, … 4, position 15 …: p(13) * p(14) * (1 – p(15)) = 0.375 * 0.375 * 0.875 = 0.123.

Probability … 4 …: p(13) * p(14) * p(15) * (1 – (16)) = 0.375 * 0.375 * 0.125 * 0.9375 = 0.016.

And so on.

The expected length of the river is 1 * 0.625 + 2 * 0.234 + 3 * 0.123 + 4 * 0.016 + …

Or 1.526 + some more.

I also plug this into my program and get 1.5347. I also try to Monte Carlo the problem and get about the same result.

***

How Long Is the River?

Just like I participate in a couple of Christmas events (one for math, one for code), this year I participated in an #Easter event (called easters.dev), primarily for #code. And as a reward for completing the #challenge I got these 3 happy eggs:

It took some time, but I’ve essentially solved all 3 x 2 puzzles without outside help. There wasn’t a helpful forum, and I didn’t just want to publish my code and ask for a review. (A lot of places on the leaderboard haven’t been taken yet.)

These are some of my experiences.

On Friday and Saturday, within a reasonable time I got a program solving 1st test case, 1st actual case and 2nd test case and then got stuck. Trying to figure out where the error is is hard!

Sunday I just ran through!

 10101
1.G...
0..O..
1.O...
0G...O
1...G.

Above are the test data for Sunday.

The numbers on top and on the left describe the columns and rows. Like, the 1st 1 says, there will be 1 example of (item) in this column. Part of the puzzle is to place items, so that all the numbers are correct. I’ve seen a lot of games do something similar, like Picross. So I basically tried to solve it like that. I copied the map into a spreadsheet, so that the numbers could automatically be calculated and compared to expectations, and then I solved it by hand.

Some cells are very easy to fill. A number is 0? Go across and mark all the undecided cells as empty. Some you have to work a little harder for.

***

Next I came back to Saturday. I will spare you the debugging details.

123

456

123
789

Above we have some of the test data. This says, if the program (3rd block of digits) contains the target (1st block of numbers), substitute in the replacement (2nd block of numbers). So, in this simple case, 123 would be replaced with 456 in the program.

It’s much more complicated than that, and a lot of stuff has to be checked before a replacement goes through, and the replacement itself might also be complicated.

In writing my code, some of it was: Will there be a replacement? And then a handful of cases, where the answer was no. What I learned from this puzzle was: Create test data for each of these cases.

***

Finally I came back to Friday. It didn’t seem like I could transfer my new coding practice to this puzzle.

In this puzzle strings are translated into other strings. Like, I have to translate “cuzb” into “awa”. There are rules for which translations are possible and how much they cost, and the goal is to find the lowest accumulated cost.

Again, after a lot of tedious debugging, I was halfway there. I had found a case, where my handmade translation was cheaper than the one my program found. But I didn’t know the reason yet.

By the way, creating a handmade translation involved analyzing the rules. The rules were represented by a map, and it was fun to play around with the map and see, that the structure shown was actually something like 8 structures smooshed together, so that they just looked like 1.

So. I fiddled around with my case. At some point I realized, that my handmade translation was much better at handling the final few characters in the string. Fiddle, flail, fiddle. And suddenly I was staring at 5 lines of code, that seemed wrong.

The task is to translate “weeds” (“cuzb”) into a nice pattern of “plants” (“awa”). (Yes, that’s a nice pattern.) I handle this recursively. Given that I want to go from “cuzb” to “awa”, and with a choice of beginning with 1 of 3 different actions, let’s just try all 3!

• I can translate “cuzb” into “acuzb” (as a middle step) by introducing a new plant “a” + translating “cuzb” into “wa”.
• I might be able to transform “c” into “a” + translating “uzb” into “wa”.
• Or I can get rid of “c” + try to translate “uzb” into “awa”.

And then I just repeat for these shorter strings. When I know enough, I can choose the cheapest. Recursion, baby. (Actually fastest.)

So now for my 5 lines of weird code.

If I have 0 weeds and 0 pattern left, I am done. Fine.

If I have some weeds and 0 pattern left, well, my first thought was, that I would be stuck, ending in an impossible situation. But I suddenly realized, that was false. Of course I could handle this situation, by getting rid of the rest of the weeds.

And suddenly my program ran correctly!

***

That was fun. And apparently I have a position on the leaderboard as #3 and can’t be dislodged.

***

Link: easters.dev.