McCaw won the part 3 steps competition.

And the program:

START ********** S000  ********** SDULULLDUD
S000  AA__****** S001  PP_******* RRRSUUDDUD
S001  A____**_** S01A  ___******* RRRSRSSRUD
S01A  B____**___ S01A  P__******* RRRSRSSRRR
S01A  CA___**___ S01A  PPPPP***** RRRLRSSRRR
S01A  DC________ S01A  PPPPPPPPPP RRRLRLLRRR
S01A  _____**___ STOP  ___******* RRRSRSSRRR

The golf for the whole program is 1829. 1 rule to spread the heads a little. S000 and S001 each spreads them a little more. And then S01A goes through the rest of the line. At 1st glance, there are 21 rules with S000 and S001 each. S000 writes 2 P’s, probably with the idea, that they might be deleted later.

From what I can tell, the purpose of a rule like S032 is to say “remember to write 32 more P’s”. (Maybe that 32 is in hex?) Let’s look at the extreme example. Note that the program keeps running for a while after the D’s end.

And the program:

START ********** S000  ********** SDULULLDUD
S000  DD__****** S007  PPPP****** RRRLUUDDUD
S007  DD______** S026  PPPPPPPP** RRRLRLLRUD
S026  DD________ S028  PPPPPPPPPP RRRLRLLRRR
S028  DD________ S02A  PPPPPPPPPP RRRLRLLRRR
...
S056  DD________ S058  PPPPPPPPPP RRRLRLLRRR
S058  DD________ S05A  PPPPPPPPPP RRRLRLLRRR
S05A  __________ S050  PPPPPPPPPP RRRLRLLRRR
S050  __________ S046  PPPPPPPPPP RRRLRLLRRR
...
S032  __________ S028  PPPPPPPPPP RRRLRLLRRR
S028  __________ S01C  PPPPPPPPPP RRRLRLLRRR
S01C  _____**___ STOP  PPPP****** RRRLRSSRRR

The first rule spreads the heads. The next rule writes 4 P’s, as the heads have only spread to 4 positions. Go to S007, meaning 8 P’s are owed? S007 spreads the heads even more, and now the 10 heads are at 10 different positions. Meanwhile 8 P’s are written and we go to S026. From there on, each rule writes 10 P’s, but as the input is DD, that means the debt rises with 2 P’s, so we go from S026 to S028 to S02A etc. At S05A we finally run out of D’s, and the rest of the rules write P’s as fast as possible. I guess some of the optimization here is, that instead of using the 10 heads to write 12 P’s in 2 steps, all the debt is written at the end. I’m not sure about the numbering of those rules. 26_hex = 38_dec doesn’t quite mean 38 P’s are owed. So maybe there’s an overlap, where S01C means S018 + S004, 18_hex to signify some state and 4 to signify writing 4 more P’s. The 1st example stays in S01A, and nothing is ever owed.

I looked a tiny bit at Peter’s solution, coming in at no. 2. He operates with MOVE6, MOVE8 and MOVE10, each meaning 6, 8 or 10 P’s are owed. But then at MOVE10 and when encountering DD, let the reading heads stay at these DD, write 8 P’s and go to MOVE2. A nice way for the debt not to grow too large.

Code .

This week the #puzzle is: Can You Fit the Stars on the Flag? #coding #bisection #desmos

When designing her new nation’s flag, Retsy Boss wanted to compactly arrange some stars. These stars were positioned along a square grid, but she only wanted to include stars whose centers were at most two units away from some point on the plane.

For example, if she had centered the circle on a star itself, then she could have placed a total of 13 stars on the flag, as shown below:

What is the greatest number of stars Retsy could have placed on the flag?

And for extra credit:

After 250 years, the nation has commissioned Retsy Boss VIII to design a new flag with one star for each of the nation’s current 58 states. As an homage to the original flag design, Retsy wants to select 58 stars from the square grid that are all at most some distance R from a point on the plane.

What is the minimum distance R that Retsy can use?

Can You Fit the Stars on the Flag?

Solution, possibly incorrect:

Desmos Program

Method 1: Recreate the situation in Desmos and mess around. First define a function to count the number of stars (the stars have integer coordinates). The center of the circle:

The distance to the center from another point:

Use rounded values for the other point:

This function will be 1, if the middle of a unit square is within the circle with radius r₁:

Compute the area of all the unit squares:

Method 2: Create a program to go through a lot of options.

Result 1: 14 (x1: 0.063600, y1: 0.499700)

Result: 14 stars.

And for extra credit:

Same methods.

My program is surprisingly sensitive to $\Delta$, the distance between different (x,y) combinations to try. I employ bisection to fine tune the solution.

Max stars for r = 4.155180, d = 0.000100: 57
                        (x1: 0.000000, y1: 0.000000)
Max stars for r = 4.155190, d = 0.000100: 57
                        (x1: 0.000000, y1: 0.000000)
Max stars for r = 4.155200, d = 0.000100: 58
                        (x1: 0.125000, y1: 0.500000)
Max stars for r = 4.155210, d = 0.000100: 58
                        (x1: 0.125000, y1: 0.500000)

4.1550000 < r < 4.1560000
4.1550000 < r < 4.1555000
4.1550000 < r < 4.1552500
4.1551250 < r < 4.1552500
4.1551875 < r < 4.1552500
4.1551875 < r < 4.1552188
4.1551875 < r < 4.1552031

Result 2: 4.1551875 - 4.1551953
                        (x1: 0.125000, y1: 0.500000)

The 2 methods largely agree. Result: A radius of 4.1552.

Peter won the part 2 steps competition. Let’s take a look.

And also let’s look at the rules actually used.

START A****A**** PREP  _****_**** RUDUDLUDUD
PREP  D****A**** MOVE3 P****P**** RRRUDLLLUD
MOVE3 B****A**** MOVE  PPP**P**** RRRRRLLLLL
MOVE  D****B**** MOVE  PPPPPP**** RRRRRLLLLL
MOVE  A****D**** MOVE  PPPP*P**** RRRRRLLLLL
MOVE  P****P**** STOP  ********** RRRRRLLLLL

Head 1 and 6 are reading. In the 1st step, there are 2 A’s, so they’re just deleted. Meanwhile the heads are spreading. In the 2nd step, there’s DA. Write 2 P’s and remember, that we need 3 more / go to state MOVE3.

Other cases employ PREP1, still preparing everything, and we need 1 more P. This goes up to PREP8. Similarly there’s a MOVE10. And whole families of MOVEC and MOVED. There’s nothing very complicated here, looking at each group of rules. There’s just a lot. 454 rules in all.

This one is in a perpetual debt, owing 8 P’s in the preparation rule and 4 in the move rules.

START   D****D**** PREP8   P****P**** RUDUDLUDUD
PREP8   D****D**** MOVED_4 PPP**PPP** RRRUDLLLUD
MOVED_4 D****D**** MOVED_4 PPPPPPPPPP RRRRRLLLLL
MOVED_4 P****P**** S       ***PP***PP SSSRRSSSLL
S       ********** STOP    PPPPPPPPPP RRRRRLLLLL

Code .

Fox was 1 of 3 to get the best score in part 1.

Or in slow motion:

I’m sure this program was generated, it has 367 lines. It has a lot of lines like this:

S_AB B*****B*** S_ABBB _PP_**____ RUDLUDLUDR

2 heads begin at the ends and work their way in. The states keep track of what was just seen and what is here now. Also there are 10 heads in all, so there’s a lot of places to write the P’s. In the example above, there’s actually some backtracking. In the final step, 1 P is deleted. Let me just find which rules were actually used in this example (I added a little formatting):

START    A*****C*** S_AC     P*****P*** RUDLLLLUDR
S_AC     B*****A*** S_ACBA   _PP_**____ RUDLUDLUDR
S_ACBA   B*****B*** S_ACBABB _PP***_*** RUDLRRLUDR
S_ACBABB _*****_*** STOP     ****_***** RUDLSSLUDR

For the 2 reading heads, ABBAC is seen as AC-BA-BB. (ABCDE would be seen as AE-BD-CC.) The 1st rule writes 2 P’s — that’s all it can do, as the heads haven’t spread out yet. So remember, we need to write 1 more P at some point. The 2nd rule writes 2 P’s, and we’re square. The 3rd rule writes 2 P’s, because it’s seeing 2 B’s. But then the final rule sees, that it was only 1 B seen by 2 heads and deletes a P. And done!

Let’s look at case 2.

And the corresponding program.

START        C*****C*** S_CC         P*****P*** RUDLLLLUDR
S_CC         A*****A*** REMAIN_1_ODD _PPP**_P__ RUDLUDLUDR
REMAIN_1_ODD B*****B*** STOP         _P****_*** RUDLSSLUDR

I’m actually not quite sure how this program detects, that BB is 1 B seen by 2 heads and therefore a stopping condition… Or how it detects, that there’s only 1 character left? Maybe this whole program is very specifically tailored to the input and knows, that CC-AA means, there’s only 1 character left? With larger strings, we run into stuff like:

REMAIN_2_EVEN A*****A*** REMAIN_1_EVEN _*****_*** RUDLSSLUDR

Keeping track of how many steps are left. Wow.

Code .

progheal won the part 3 rules competition.

This time there are a lot of heads. In the gif above, it’s especially visible, that the left and right vertical sides are done simultaneously. Something similar is true about the top and bottom horizontal sides. And I think it’s a feature in this part, that the 2 vertical sides are actually equal, and the same for the horizontal sides, because that means fewer rules. (Though it actually leads to fewer rules needed to be written, the number of used rules isn’t affected.)

Code .

Zach won the part 2 rules competition.

I don’t know, whether that saves rules, but I do notice, that this solution does the horizontal bit first, and then the vertical.

Code .

For et par dage siden anbefalede Zach Wissner-Gross fra Fiddler on the Proof langnovellen “Understudies” af #GregEgan, og nu har jeg fået den læst. Wow! For fans af fiddler-opgaver og den slags, så er det her en gave. Og lad mig med det samme indrømme, jeg løste altså ikke alle opgaverne i teksten, mens jeg læste. De er svære!

Fiddler on the Proof “Understudies”

Specielt en af opgaverne fangede mig, fordi jeg ikke helt kunne forstå løsningen. Så i det her indlæg vil jeg prøve at læse opgave og løsning, indtil jeg forstår det.

“A few years before the fall of the Berlin Wall,” she said, “an English journalist was imprisoned in East Germany. She was able to exchange letters with her husband, but they knew their mail was being read by authorities. Among the first things her husband sent her was a computer printout of a poem, written by their twelve-year-old daughter, which the journalist kept pinned to the wall of her prison cell. It read:

“Evening light fades / Quiet descends / The joking boy relaxed / Sweetly amazed / Night promises peaceful dreams / Until morning.

“Historians studying the correspondence between the couple found that the words of this poem showed up in their letters far more often than would have been expected, and so might have played a part in a code they used.

“Once, in response to a letter where her husband used ‘joking,’ ‘descends,’ ‘quiet,’ ‘fades,’ and ‘light,’ in that order, the journalist responded by using ‘evening,’ ‘amazed,’ ‘boy’ three times, ‘amazed,’ ‘evening,’ ‘joking’ twice, ‘relaxed,’ ‘sweetly,’ ‘amazed,’ ‘sweetly,’ then ‘relaxed.’

“What was she communicating?”

Og den korrekte løsning:

“The husband wasn’t saying anything in his letter,” she explained. “He was providing a key that the journalist could use to help encode her own message. She took his numbers—five, four, three, two, one, by their position in the poem, with ‘evening’ as zero and ‘the’ omitted—then used the dot matrix printout of the poem, with each letter of the alphabet forming a grid five dots wide, to transform them into a number for each row, adding up those with a matching dot, leaving out the rest. The lowercase letters ‘o’ and ‘k’ provided her response. She was saying ‘okay.’ ”

Lad os tage den igen, langsomt.

Digtet kan også skrives således:

0	Evening	4	descends	8	Sweetly	12	peaceful
1	light	5	joking	9	amazed	13	dreams
2	fades	6	boy	10	Night	14	Until
3	Quiet	7	relaxed	11	promises	15	morning

Det første brev:

“a letter where her husband used ‘joking,’ ‘descends,’ ‘quiet,’ ‘fades,’ and ‘light,’ in that order, …’ ”

Det bliver altså til 5, 4, 3, 2 og 1.

Og det andet brev:

“… the journalist responded by using ‘evening,’ ‘amazed,’ ‘boy’ three times, ‘amazed,’ ‘evening,’ ‘joking’ twice, ‘relaxed,’ ‘sweetly,’ ‘amazed,’ ‘sweetly,’ then ‘relaxed.’ ”

Dette svarer til 0, 9, 6, 6, 6, 9, 0, 5, 5, 7, 8, 9, 8, 7.

Jeg kan se, at der er noget struktur her, der passer med o og k. I første omgang med et tilfældigt bud på en font.

     x
 xx  x
x  x x  x
x  x x x
x  x xx
 xx  x x
     x  x

Eller:

0         5 x
9  xx     5 x
6 x  x    7 x  x
6 x  x    8 x x
6 x  x    9 xx
9  xx     8 x x
0         7 x  x

Ja, noget her fungerer. Samme linje af pixler i det samme bogstav giver det samme tal.

Men jeg har ikke brugt 5, 4, 3, 2, 1 til det her? Hov, jeg prøver lige igen, med en bedre font.

0          5 x
9  xxx     5 x
6 x   x    7 x  x
6 x   x    8 x x
6 x   x    9 xx
9  xxx     8 x x
0          7 x  x

Ja, nu virker det.

“_xxx_” bliver parret sammen med “54321”. Det giver “04320”. Og tværsummen af det er 9. Og således bliver toppen af o’et til 9. “x___x” bliver til “50001”, bliver til 6. Osv.

Jeg tror, jeg forstår den!

Zach won the rules competitions for part 2 and 3. For part 2 there are 4 heads. In phase 1 the red head looks at the nails, and the yellow head looks for the top and bottom nails. When a nail head is detected and we go into phase 2, the green and yellow heads come running and fix the wrong nails.

A little extra work for part 3. When a nail head has been detected, there’s a marker written ($) for that nail, to keep track of it.

Code .

No. 2 in part 1, rules section, is actually kind of familiar to me in structure.

Do the very elegant solution of hammering the log instead of the nails, and do it from both ends of the log. There’s an extra little dance with the heads, when a nail is all head, no shaft.

Code .

Her er årets nominerede romaner, med samt link til mine anmeldelser:

Death of the Author by Nnedi Okorafor	##-	Forfatterens død
A Drop of Corruption by Robert Jackson Bennett	###	Korruptionsdråben
The Everlasting by Alix E. Harrow	##-	Den evige
The Incandescent by Emily Tesh	###	Den strålende
The Raven Scholar by Antonia Hodgson	##-	Ravnelærd
Shroud by Adrian Tchaikovsky	#–	Slør

Det bliver dråben, der løber med sejren her. Det var bare så rart at tage en tur til i det her univers.