This week the #puzzle is: Can You Win the World Cup? #montecarlo #coding #probabilities

And for extra credit:

Can You Win the World Cup?

Solution, possibly incorrect:

Program

Method: Monte Carlo.

• I write a program to simulate the tournament a lot of times.
• A complete strategy is to choose a number for the 1st game. E.g., if I choose 10% for the 1st game, there’s 90% left for the 2nd, no further choices.
• I actually make a mistake the 1st time with my program, because I just assume my opponent in the final used a random amount of energy in the semifinal. An extra element here is, that my opponent also won the 1st game. The result of this is, that they probably used “a lot of energy” in the semifinal, and therefore doesn’t have “a lot” left. I write an extra function to simulate that other part of the tournament.

Curve of the result:

If I use 1% energy in the 1st game, about 1000 out of 100000 simulated tournaments are won. The best result is 58% energy, with 38.696% win ratio. But there’s a little group of results close to that, so that’s just an estimate.

Result: 39%. (See below, 38.5 or 38.6.)

And for extra credit:

Tweak program and go again. Let me just read that 1 more time… Yes. The whole strategy has to be chosen before the 1st game. Heat maps:

If I use 53% in the 1st game and 21% in the 2nd, I win 28328 of 100000 simulated tournaments. But there’s a whole cloud of results in the vicinity.

Result: 28%. (See below, 28.2 or 28.3.)

Trying to become better at making heat maps – now with better numbers on the axis, and the last 2 were made with more accuracy (more loops):

Also, the results with more loops – 38.5 and 38.6 seem probable, as does 28.2 and 28.3:

Result 1, max wins: 0.38572

E1: 0.5540 E2: 0.4460 Wins: 0.3845400
E1: 0.5560 E2: 0.4440 Wins: 0.3845750
E1: 0.5570 E2: 0.4430 Wins: 0.3846450
E1: 0.5600 E2: 0.4400 Wins: 0.3852190 -
E1: 0.5610 E2: 0.4390 Wins: 0.3843620
E1: 0.5630 E2: 0.4370 Wins: 0.3847120
E1: 0.5640 E2: 0.4360 Wins: 0.3844680
E1: 0.5650 E2: 0.4350 Wins: 0.3849760
E1: 0.5660 E2: 0.4340 Wins: 0.3841780
E1: 0.5670 E2: 0.4330 Wins: 0.3851480 -
E1: 0.5680 E2: 0.4320 Wins: 0.3849550
E1: 0.5690 E2: 0.4310 Wins: 0.3844520
E1: 0.5700 E2: 0.4300 Wins: 0.3843820
E1: 0.5710 E2: 0.4290 Wins: 0.3846120
E1: 0.5720 E2: 0.4280 Wins: 0.3843730
E1: 0.5730 E2: 0.4270 Wins: 0.3843730
E1: 0.5740 E2: 0.4260 Wins: 0.3855780 -
E1: 0.5750 E2: 0.4250 Wins: 0.3849750
E1: 0.5760 E2: 0.4240 Wins: 0.3842780
E1: 0.5780 E2: 0.4220 Wins: 0.3847780
E1: 0.5790 E2: 0.4210 Wins: 0.3854960 -
E1: 0.5800 E2: 0.4200 Wins: 0.3851070 -
E1: 0.5810 E2: 0.4190 Wins: 0.3849570
E1: 0.5830 E2: 0.4170 Wins: 0.3847470
E1: 0.5840 E2: 0.4160 Wins: 0.3850320 -
E1: 0.5850 E2: 0.4150 Wins: 0.3844100
E1: 0.5860 E2: 0.4140 Wins: 0.3841980
E1: 0.5870 E2: 0.4130 Wins: 0.3845960
E1: 0.5890 E2: 0.4110 Wins: 0.3847450
E1: 0.5900 E2: 0.4100 Wins: 0.3846460
E1: 0.5910 E2: 0.4090 Wins: 0.3842120
E1: 0.5920 E2: 0.4080 Wins: 0.3846600
E1: 0.5930 E2: 0.4070 Wins: 0.3857210 *
E1: 0.5940 E2: 0.4060 Wins: 0.3849330
E1: 0.5960 E2: 0.4040 Wins: 0.3843630
E1: 0.5980 E2: 0.4020 Wins: 0.3841920
E1: 0.5990 E2: 0.4010 Wins: 0.3840440
E1: 0.6000 E2: 0.4000 Wins: 0.3840040
E1: 0.6030 E2: 0.3970 Wins: 0.3842700

Result 2, max wins: 0.28273

E1: 0.4990 E2: 0.2300 Wins: 0.2822620
E1: 0.5030 E2: 0.2320 Wins: 0.2821100
E1: 0.5040 E2: 0.2300 Wins: 0.2821480
E1: 0.5040 E2: 0.2350 Wins: 0.2822040
E1: 0.5060 E2: 0.2450 Wins: 0.2825120 -
E1: 0.5070 E2: 0.2370 Wins: 0.2821200
E1: 0.5080 E2: 0.2220 Wins: 0.2823350
E1: 0.5080 E2: 0.2410 Wins: 0.2821320
E1: 0.5100 E2: 0.2400 Wins: 0.2822310
E1: 0.5100 E2: 0.2430 Wins: 0.2821000
E1: 0.5110 E2: 0.2230 Wins: 0.2821650
E1: 0.5110 E2: 0.2350 Wins: 0.2821200
E1: 0.5120 E2: 0.2280 Wins: 0.2824650 -
E1: 0.5120 E2: 0.2390 Wins: 0.2822870
E1: 0.5130 E2: 0.2280 Wins: 0.2821010
E1: 0.5150 E2: 0.2310 Wins: 0.2822700
E1: 0.5160 E2: 0.2320 Wins: 0.2821560
E1: 0.5160 E2: 0.2340 Wins: 0.2827280 *
E1: 0.5160 E2: 0.2390 Wins: 0.2822090
E1: 0.5170 E2: 0.2330 Wins: 0.2821160
E1: 0.5170 E2: 0.2340 Wins: 0.2822440
E1: 0.5180 E2: 0.2250 Wins: 0.2821520
E1: 0.5180 E2: 0.2340 Wins: 0.2824180 -
E1: 0.5200 E2: 0.2220 Wins: 0.2824470 -
E1: 0.5200 E2: 0.2240 Wins: 0.2822010
E1: 0.5200 E2: 0.2340 Wins: 0.2821920
E1: 0.5200 E2: 0.2350 Wins: 0.2822610
E1: 0.5210 E2: 0.2340 Wins: 0.2821350
E1: 0.5230 E2: 0.2280 Wins: 0.2822700
E1: 0.5230 E2: 0.2290 Wins: 0.2824650 -
E1: 0.5240 E2: 0.2220 Wins: 0.2821440
E1: 0.5250 E2: 0.2250 Wins: 0.2821790
E1: 0.5250 E2: 0.2320 Wins: 0.2824380 -
E1: 0.5260 E2: 0.2210 Wins: 0.2822790
E1: 0.5260 E2: 0.2250 Wins: 0.2821760
E1: 0.5270 E2: 0.2210 Wins: 0.2823230
E1: 0.5270 E2: 0.2260 Wins: 0.2823710
E1: 0.5280 E2: 0.2200 Wins: 0.2821080
E1: 0.5280 E2: 0.2260 Wins: 0.2824000 -
E1: 0.5280 E2: 0.2290 Wins: 0.2826180 -
E1: 0.5280 E2: 0.2320 Wins: 0.2822990
E1: 0.5290 E2: 0.2210 Wins: 0.2821120
E1: 0.5300 E2: 0.2180 Wins: 0.2821250
E1: 0.5310 E2: 0.2170 Wins: 0.2824390 -
E1: 0.5310 E2: 0.2290 Wins: 0.2822880
E1: 0.5330 E2: 0.2180 Wins: 0.2821450
E1: 0.5330 E2: 0.2230 Wins: 0.2822540
E1: 0.5360 E2: 0.2240 Wins: 0.2824160 -

To round off my look at solutions for GridOS 1, here a few more general thoughts.

Characteristics of a good rules program:

• Delay some of the processing of the input until later. Like, if I see a D now, add a C at the end of string for later processing and do the difference between C and D now (write 2 P’s). (Details.) A lot of the time, the rule invoked for the delayed processing would already have been in use, so we don’t add an extra rule.
• Split the program into subprograms, that run in different situations. Like, if the 1st character is a B, only certain rules will be used. (Details.) For each case, there are a limited number of rules in use. And it might handle the situation, where separate rules to spread the heads and process the 1st input uses up a lot of rules.
• Consider “write a lot now, be prepared to delete some later”. (Details.) Writing a lot at the beginning might save a step/rule later. It might also be, that the logic to write/delete is easier than wait/do nothing.
• It’s probably better to have a “complicated move right, easy move left and down” way to handle multiple lines of input. (Details.) It might be possible to have 1 rule to handle the “move left” part.
• Consider efficiency, not beauty. Write that output wherever. At the end of the line, or for no particular reason above and below the input.
• Find a shortcut. Can the puzzle be turned on its head? Can the output be written in a non-obvious place? (Details.)
• Use a structure of the input. Like, the input might actually be symmetrical/mirrored/rotated in some way. (Details.)

Characteristics of a good steps program:

• Generate the code.
• Use recursion.
• Work in more than 1 area at the same time, like doing both ends of string.
• Use as many heads as possible.
• Find an elegant solution combining these 2. (Details.)
• Tailor the program to the input? (Details.)
• Combine spreading the heads with the processing. (Details.)
• Delay some of the processing, but only a little. (Details.)
• Split the program into subprograms. (Details.)
• Write the output wherever. (Details.)
• Use a structure of the input. (Details.)

Not surprisingly there’s an overlap between the 2 lists. Not surprisingly, I was not the only one to discover the top 4 of good step strategies.

I feel ready for the next competition!

This week the #puzzle is: Can You Power up the Hill? #trigonometry #root

And for extra credit:

Can You Power up the Hill?

Solution, possibly incorrect:

Desmos

I create 2 graphs, 1 for each rider. The x axis is the angle of the slope, y is the speed. Then I note where the graphs cross.

Result: A slope of 0.055584. This gives both riders a speed of 22.5.

The slope corresponds to a gradient of 0.0556413145901. Let’s say 0.05564 = 5.564%.

And for extra credit:

Something with trigonometry? Maybe an integral? I think I need a reverse function, going from gradient to slope, and I don’t quite see how to do that. Sigh.

Peter won the part 3, steps competition.

Tricks:

• Not generated code — the golf is 56! I think this program uses the feature, that the top/bottom lines are the same, and the left/right lines are the same.
• 2 3 head combinations going down, 2 2 head combinations going right.

Wonderful!

This will be my last review of a specific puzzle, but I plan on drawing some conclusions from the whole competition tomorrow.

Code . I have become aware, that the code is only available, if you’re logged in.

McCaw won the part 2, steps competition. Behold:

Let me see…

• Generated code — a golf of 6565.
• Coming from both ends and twice from the middle at the same time.

Yeah, I guess that’s it! But, just for fun, let’s look at the case 2 program, ignoring all the rules not used.

HEADS AAABBBBCCC
START .......... S000  ***+*+**** SDDLLDDSLL
S000  .......... S001  ***+*+**** SSDLLDDSSL
S001  .......... S002  +******+++ RRRSDSLUUU
S002  .@*.....@* S044  +**+++++** RRRDDLLUUU
S044  ...+.+.... S04D  +++*+*++++ RRRLLDDUUU
S04D  *@.@.@.*@. S04D  **+*+*+**+ RRRLLDDUUU
S04D  **+*+*+**+ STOP  ********** SSSSSSSSSS

2 steps to spread the heads, and writing the 1st +’s in the corner as well. And then we go! There are a lot of rules for S04D. The 3 head combinations from the ends can always move closer to the corner. The 2 head combinations beginning in the corner have to dance a little (!), when they maneuver through a hole between the barrels.

Code .

Peter won the part 3, steps competition.

Again, something very familiar about these 9- row cases. The 1st action is to count the rows, initially by replacing the # at the beginning with a number. And then … all heads travel right? In the 3 row case, they even separate a little before going right?

But then, those 10+ row cases.

As the rows have been counted, the 10 row case is like the previous cases. But for 13 rows, there’s, let me see, 3 heads in the top, 4 in the bottom, and in the middle 3 heads traveling up and down. Slightly different way to solve that particular problem. Looks more elegant. And apparently it saves steps. Or at least, the complete strategy for 3-13 rows saves steps.

Code .

Fox was no. 1 in the part 2, steps competition. Let’s look at it.

Without spending a lot of time looking at the code (generated, golf 3529), I get the sense, that this is one of those “in fact different programs for different numbers of rows”. The 2 cases above look very like mine. But then we cross the border to 10+ rows.

There’s a little dance, when the nail heads are written. And when there are more than 10 heads, there’s a little extra cleanup at the end.

Code .

As I am a Dane 🇩🇰, I of course noticed the other Dane 🇩🇰 in the field. Who consistently got very good times and placed 4th in that category (2 hours and 40 minutes to write 15 programs). And who got other good results in other categories as well. Though I see I beat him in a few cases! I am surprised! But then I guess it was a bit of a surprise, that the competition worked in a new way in the non-times categories. Hm. I don’t see a leaderboard split into countries. But the regular everybody.codes has that, and whenever I actually got a few points, I would admire my position no. 2, way behind Feld.

His steps solution for part 1 placed best.

It’s a variation on hammer the log, not the nail, and doing it from both ends at once. Also, 3 heads from each direction and an interesting way of spreading the heads. And a very short program. A golf of 23.

Code .

McCaw won the steps competition for part 2 and placed 2nd for part 3. Part 2:

Oh, some cool ideas here.

• Generated code to handle all the possible cases.
• Coming from both ends.
• Being able to handle all the necessary information with states + 5 heads.
• Reading the string, rewriting it 1 row above.

And part 3:

This one has a sort of exploding wave front. The 1st time a “=” is encountered, replace it with “~”, but also send some heads 1 row down. As long as a new “=” is encountered, keep doing that. This of course has to stop when all 10 heads are on different rows, so there’s a different mechanism to finish the deep ponds in that case. V’s and B’s to keep track of how much is left to do. Oh, and a funny “with the very deep ponds, keep 1 head on the top row, and when the deep pond is finished, let that head travel again, alone for a while”.

I don’t quite know what to say. It’s elegant. And a lot of people used similar techniques to get good scores.

Code .

Peter placed no. 1 in the steps competition. Here’s an example of part 1:

And the corresponding program, only the rules actually used:

HEADS AABBA
START ***** MOVE0 ***** SRLSU
MOVE0 ABAB* MOVE1 _ba_* RRLLS
MOVE1 bBAa* MOVE2 @ba@* RRLLS
MOVE2 baba* STOP  _**_* RRLLS

Use a step to spread the heads. Then use 2×2 heads to read new and previous information. With this string, ABBAAB, the first time this is AB-AB. Delete the outer characters and replace the inner characters with lower case copies. Next time it’s bB-Aa. As bB and Aa represent pairs, 2 @’s are written. Again, the inner characters are changed to lower case. In the next step we get ba-ba, actually the same ba seen twice. Write nothing, delete the characters, stop.

A slightly longer example, ABBABBABBB.

And the program:

HEADS AABBA
START ***** MOVE0 ***** SRLSU
MOVE0 ABBB* MOVE1 _bb@* RRLLS
MOVE1 bBBb* MOVE2 @bb@* RRLLS
MOVE2 bAAb* MOVE3 _aa_* RRLLS
MOVE3 aBBb* MOVE4 _bb@* RRLLS
MOVE4 bbbb* STOP  @**_* RRLLS

Apparently there’s a set of rules for each step. Yeah, from what I can tell, the MOVE1 group is almost exactly a duplicate of the MOVE0 group etc. So, this program was quick and easy to write, but could easily have been shorter. However! Right now we’re counting steps, and then it doesn’t matter.

For part 2, more than 1 string of characters is possible.

With 1 string, the program seems to be the same as before. With 2 strings, there are 2×4 heads, and the strings are still processed from both ends at the same time. But with 3-5 strings…

The 4 heads at the end of the strings are simply left there, useless.

The program for case 30:

HEADS     AAADDABBCC
START     A**B****** PREPAB    _**_****** RDDRURLDLU
PREPAB    B_*B*!BBAA MOVE_BBBA *@**_**_*_ RRSRRRLLLL
MOVE_BBBA A**B*!A*B* MOVE_ABAB a@*b_*a_b_ RRSRRRLLLL
MOVE_ABAB B**B*!B*A* MOVE_BBBA b@*b_*b_a_ RRSRRRLLLL
MOVE_BBBA B**B*!B*B* MOVE_BBBB b@*b@*b@b_ RRSRRRLLLL
MOVE_BBBB A**A*!B*B* MOVE_AABB a_*a_*b@b@ RRSRRRLLLL
MOVE_AABB B**A*!B*A* MOVE_BABA b@*a_*b@a_ RRSRRRLLLL
MOVE_BABA _a**b***** STOP      *_**_***** SSSSSSSSSS

The 1st rule spreads the heads a little. A and B are deleted, but remembered in the state name. The 2nd rule encounters a blank space, and this must just have been created by the 1st rule. So we move into 2 string mode.

The program for case 50:

HEADS     AAADDABBCC
START     A**B****** PREPAB    _**_****** RDDRURLDLU
PREPAB    *A**A!**** PREPAAAB  *_**_***** SRDSRRSSSS
PREPAAAB  AB_BB***** MOVEABBB  @_*@_***** RRRRRRSSSS
MOVEABBB  BB*BB!**** MOVEBBBB  _@*@@***** RRRRRRSSSS
MOVEABBB  BB*BB!**** MOVEBBBB  _@*@@***** RRRRRRSSSS
MOVEBBBB  AB*BB!**** MOVEABBB  _@*@@***** RRRRRRSSSS
MOVEABBB  BA*AA!**** MOVEBAAA  __*__***** RRRRRRSSSS
MOVEBAAA  BB*AB!**** MOVEBBBA  @_*@_***** RRRRRRSSSS
MOVEBBBA  BB*AB!**** MOVEBBBA  @@*@@***** RRRRRRSSSS
MOVEBBBA  BA*BA!**** MOVEBAAB  @_*__***** RRRRRRSSSS
MOVEBAAB  AB*BB!**** MOVEABBB  __*@_***** RRRRRRSSSS
MOVEABBB  BB*AB!**** MOVEBBBA  _@*_@***** RRRRRRSSSS
MOVEBBBA  AB*BB!**** MOVEABBB  _@*_@***** RRRRRRSSSS
MOVEABBB  AA*AA!**** MOVEAAAA  @_*__***** RRRRRRSSSS
MOVEAAAA  AB*BB!**** MOVEABBB  @_*__***** RRRRRRSSSS
MOVEABBB  BB*AB!**** MOVEBBBA  _@*_@***** RRRRRRSSSS
MOVEBBBA  AB*BB!**** MOVEABBB  _@*_@***** RRRRRRSSSS
MOVEABBB  BB*AB!**** MOVEBBBA  _@*_@***** RRRRRRSSSS
MOVEBBBA  BA*AA_**** STOP      @_*@_***** RRRRRRSSSS

PREPAB does not see a blank space in front of head 2, so we go a different path.

Finally, for part 3, pairs are counted both horizontally and vertically.

Apart from a few things in the beginning to detect the number of strings, this feels very familiar. Once we’re set, 4 heads look at the situation and react accordingly. Extra @’s can be written in front of the strings.

Code .