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. 👽👽☠️

This week the #puzzle is: Can You Permeate the Pyramid?

Consider the following figure, which shows 16 points arranged in a rhombus shape and connected to their neighbors by edges. How many distinct paths are there from the top point to the bottom along the edges such that:

– You never visit the same point twice. – You only move downward or sideways—never upward.

And for extra credit:

Consider the following figure, which shows 30 points arranged in a three-dimensional triangular bipyramid. As before, points are connected to their neighbors by edges. How many distinct paths are there from the top point to the bottom along the edges such that:

– You never visit the same point twice. – You only move downward or sideways—never upward.

Highlight to reveal (possibly incorrect) solution:

Program 1.

Let’s number the layers from the top, 1, 2, … 7.

How many paths from layer 6 to 7? Let’s call layer 6 h and i, and layer 7 x.

From h I can go directly to x or through i. For symmetry reasons, i is similar. So, 2 paths from h to x, 2 from i to x. (2 * 2 = 4 in all.)

How many paths from layer 5 to 7? Let’s call layer 5 a, b and c.

From a I can go directly to h or through b. From b I can go directly to h or through a. From c I can go through b to h or through b and a to h. Similarly there are 2 paths from a to i, 2 from b to i and 2 from c to i. When I get to layer 6, there are 2 possible paths to get to x. So, 2 * 2 = 4 paths from a to layer 6, and the same for b and c. All the way from a to x is 4 * 2 = 8. (3 * 8 = 24 in all.)

Let’s write this differently.

Let p(n) be the number of paths from an element in a layer with n elements to layer 7. (Layer 4-7.)

p(1) = 1. There’s only 1 way to do this, stand very still.

p(2) = 2, as we’ve seen.

p(3) = 8 = 2 * 2 * p(2).

In general this is p(n+1) = 2n * p(n).

p(4) = 2 * 3 * 8 = 48.

Now we have to go the other way.

Time to rename the elements.

How many paths from layer 3 to 7? Let’s call layer 3 a, b and c, and layer 4 w, x, y and z.

I can go from a directly to w. From a to x directly or through b. From a to y through b or through b and c. From a to z through b and c. 6 paths from a to layer 4. The same for c.

I can go from b to w through a. From b to x directly or through a. From b to y directly or through c. From b to z through c. Again, 6 paths from b to layer 4.

Let q(n) be the number of paths from an element in a layer with n elements to layer 7. (Layer 1-4.)

q(4) = p(4) = 48.

q(3) = 6 * q(4) = 6 * 48 = 288.

In general this is q(n-1) = 2 * (n-1) * q(n).

q(2) = 2 * 2 * 288 = 1152.

q(1) = 2 * 1 * 1152 = 2304.

q(1) was the number we were looking for. I confirm 2304 is the correct number with a program.

And for extra credit:

Program 2. Program 3. Program 4.

I keep working with the program I wrote earlier. I write versions with 3, 5 and 7 layers. This time I generate the graph by hand. (It’s easier for me to draw it than to write the code.) I also optimize the code a little, only storing the number of paths instead of the paths themselves.

For 3 layers, there are 15 paths. For 5 layers, there are 11,475 paths. (Both of these fit with other programs, I tested out first.) And for 7 layers, there are 1,093,007,025 paths.

Anmeldelse af “We Will Teach You How to Read | We Will Teach You How to Read” (gratis), af Caroline M. Yoachim. Novelle. 2024. Nebula-nomineret, Hugo-finalist.

Skitse: Nogen (rumvæsner?) forsøger at kommunikere med os, men det er svært, fordi deres egen form for kommunikation er helt anderledes end vores.

Er det science fiction? Måske.

Temaer: Udover det her med at kommunikere på en helt anden måde, så hører vi også snipper af, at deres samfund er ved at dø, og at de unge ikke længere lærer at læse.

Er det godt? Tja. 👽👽☠️

Anmeldelse af “The Witch Trap”, af Jennifer Hudak . Novelle. 2024. Nebula-nomineret.

Skitse: En sko under gulvet holder heksen væk.

Er det science fiction? Nix. Mest fantasy.

Temaer: Vi hopper rundt mellem forskellige tekster, der handler om hekse. Det skal vist forestille, at gulvets ejer researcher fænomenet. Og så beslutter, hvad der skal ske med skoen.

I øvrigt synes hekse: Ned med patriarkatet.

Er det godt? Tjo. Af gode grunde fragmentarisk. 👽👽☠️

Anmeldelse af “The V*mpire” (gratis), af PH Lee. Novelle. 2024. Nebula-nomineret.

Skitse: Det er 2012 og på tumblr, og du er 14, og det giver bare mening at sige, at du er en pige. Er det okay at lade som om? Hvad er det der med trans? Og hvorfor er det forskelsbehandling ikke bare at invitere alle vampyrer ind i sit hjem?

Er det science fiction? Nix. Fantasy/horror.

Temaer: Øj, en ordentlig omgang “jamen, hvad er det okay at sige?”. Fordi det er ikke kun “de gode”, der retter dig. Og er det ikke altid okay at kalde, æhm, problematiske personer ved det navn? Være intolerant overfor de intolerante.

Psykisk og fysisk vold. Nok til at teksten starter med en advarsel.

Er det godt? Åh, den rammer noget. Sådan, lidt for meget. Av. 👽👽⭐

Anmeldelse af “Five Views of the Planet Tartarus” (gratis), af Rachael K. Jones. Novelle. 2024. Nebula-nomineret, Hugo-finalist.

Skitse: Et rumskib fyldt med fanger ankommer til planeten Tartarus og Orfeus-fabrikken.

Er det science fiction? Nemlig.

Temaer: Det er kun hvert 10. år, sådan et rumskib er der. Min fornemmelse er, at vi taler om uhyrlige forbrydelser og utænkelig straf, men det fremgår ikke eksplicit. En del af mekanismen er, at fabrikken giver evigt liv.

Teksten er ganske kort. Det virker som et godt valg.

Er det godt? Tja. 👽👽☠️

Anmeldelse af “Evan: A Remainder”  (gratis), af Jordan Kurella. Novelle. 2024. Nebula-nomineret.

Skitse: Da Evan sagde højt, at han faktisk er en mand, førte det til en skilsmisse og et nyt liv i en grim lejlighed. Han bliver optaget af en blodplet på gulvet, der bare ikke vil gå af, og af at spytte tænder (?) ud.

Er det science fiction? Det kan man vist ikke påstå. Horror, nutid.

Temaer: Noget med transformation. Noget med at acceptere hvem man er og har været.

Noget med knogler.

Noget med kærlighed.

Formen har hop i tid.

Er det godt? Jeg ved ikke, om det her er nyskabende. Det er i hvert fald ikke lige mig. 👽👽☠️