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.

This week the #puzzle is: Can You Tile the Hexagon? #counting #hexagon #tiling #macmahon #coding #memoization

I’m redoing my kitchen floor using rhombus-shaped tiles composed of two congruent equilateral triangles. One such tile is shown in blue below. How many distinct ways can I use these to tile the outlined region below, which consists of 24 equilateral triangles arranged in a regular hexagon?

And for extra credit:

I’m also redoing my patio, using similar rhombus-shaped stones. How many distinct ways can I tile the outlined region below, which consists of 54 equilateral triangles?

Can You Tile the Hexagon?

Solution, possibly incorrect:

Program

Method 1: I quickly whip up a program. And I add memoization to it. And it arrives at a state, where it can find the answer in 3 minutes.

Result: 20.

I also produce a video, documenting all the possible tilings. (Beware: this post has a lot of videos and images.)

And just to go nuts, I produce screenshots from that video. Yes, I know, you don’t have to thank me.

I go through my notes and end up producing small families of solutions, where each family is connected by rotations. Like this one, with 6 rotations of the same solution.

Or this one:

A smaller family.

And an even smaller.

Like this one:

And finally a singleton.

Mirrors just end of producing the same results as rotations.

I will get back to the fiddler again later.

And for extra credit:

Wikipedia YouTube

Method 1: Run the program again. Ehm. That will take too long. Sigh.

Method 2: Search internet. Hey, what’s this?

“the total number ${\displaystyle N_1(r,s,t)}$ of plane partitions that fit in the ${\displaystyle r\times s\times t}$ box ${\displaystyle \mathcal{B}(r,s,t)}$:”

I think the box is if the hexagon tiling is viewed in a 3d way. The “box” has the same side lengths as the hexagon. The plane partitions correspond to the tilings. Yeah, this one confirms it:

And just to make sure, the fiddler has a 2x2x2 box.

Or, from the other formulation of the count:

Awesome! And the video already did the calculation we want. $\underline{N=980}$.

More extra credit later.

The fiddler, again

Studying the sources mentioned above, I find a different method to produce the same solutions, with slightly squinked rhombi:

This set is numbered like xy: x cubes, the yth way.

The 2 sets of solutions correspond. To make me (and probably nobody else) happy, here’s the full correspondence description.

01	1	11	2	21	7	22	4
23	3	31	9	32	8	33	5
41	15	42	10	43	12	44	6
51	16	52	13	53	11	61	18
62	17	63	14	71	19	81	20

And just to show that these are the same solutions, here’s a comparison of 2 versions of the same, 9 and 31:

Or maybe it’s easier to compare these 2 prettier versions of the same solution:

I then proceed to create a new program, to make really pretty versions of these tilings. Here’s you go, fiddler:

And extra credit:

The top “few rules” solution in part 1:

Like other solutions doing well in this category, there’s an element of “write a lot, possibly delete it later”. Elegant. (Zach’s solution to this one is almost identical.) If the (yellow) reading head sees a =, write a wave below and in front. If it sees a #, delete behind, as too much was written.

Code .

In quest 2, Zach won all 3 rules competitions. Let’s first look at part 1. In this gif, I’ve actually added a rule and changed 2 others to keep everything nice and horizontal. Originally the @’s went up and down.

Features:

1. There are 5 heads. 1 to read the string, 2 to write @’s for A pairs and 2 to write @’s for B pairs.
2. When there’s an A in the string, an @ is written above the string and an @ might be deleted below the string. If there are 2 A’s in a row, the written @ for the 1st A is left alone. And vice versa.

Part 2 is similar. There’s an extra rule to go back to the beginning of a line.

For part 3, again there are new features. Going down and up a column are very different. There are different mechanisms for the horizontal and vertical pairs.

Truth be told, I haven’t quite wrapped my head around part 2 and 3 here. But I see the general features.

Code .