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.

Lad os tage et kig på de Nebula-nominerede noveller, det nyeste kuld.

Måske er jeg ekstra gnaven i år? Det kan man jo ikke afvise. I hvert fald er der ikke noget, der lige får mig op at ringe. Men blandt alt det næstbedste, så er det “Five Views”, der ligger øverst.

Jeg har skrevet om Hugo- og Nebula-tekster før.

Anmeldelse af “Why Don’t We Just Kill the Kid In
the Omelas Hole” (gratis), af Isabel J. Kim. Novelle. 2024. Nebula-nomineret, Hugo-finalist.

Skitse: Nogen myrder barnet i hullet i Omelas, og så sker der alle mulige ulykker, og så bliver et nyt barn proppet i hullet, og alting er godt igen.

Er det science fiction? Tja?

Temaer: Omelas, hele dagen, alle vegne! #JeSuisOmelas

Selvom alle er lykkelige og lige og alt det der, så er nogle huse alligevel lidt pænere end de andre. Måske er der en modsætning mellem de rige (?) og de gode (?)?

Historien virker meget moderne, nutidig.

Er det godt? Hm. Jeg kan ikke helt se, hvad den her version tilfører af nyt. 👽👽☠️