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

… we’ll be looking at a model for a cyclist’s speed v as a function of their pedaling power P, their mass m, and the ground’s angle of inclination 𝜃:

$v=\frac{P}{m\sin{\theta}+10}$

(For the purposes of this puzzle, you needn’t worry about the units for power, mass, or speed. If you’re curious, they’re typically given in Watts, kilograms, and kilometers per hour or miles per hour, respectively.)

In cycling, roads are marked with a gradient g, which is a hill’s slope, typically expressed as a percentage. Thus, an incredibly steep 45-degree incline has a gradient of 1, or “100 percent.”

Consider the following two riders:

– A “climber,” who has a power of 300 and a mass of 60 – A “sprinter,” who has a power of 325 and a mass of 80

At what gradient will the climber and sprinter cycle at the same speed? (You can give your answer as a value between 0 and 1 or as a percentage.)

And for extra credit:

The climber and the sprinter are racing up a perfectly sinusoidal hill. They go from the base, where the gradient is 0 percent, to the peak, where the gradient is again 0 percent. For them to reach the top at the same time, what should the maximum gradient of the hill be? (You can give your answer as a value between 0 and 1 or as a percentage.)

Importantly, note that the formula for v given above is for a rider’s speed along the ground. Thus, when the ground is inclined, the same speed will cover less horizontal distance per unit time.

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 .

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.