mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-11-08, 02:48   #34
0scar
 
Jan 2020

2×3×5 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
Our goal is to find better and efficient solutions everywhere
As an example, we can try to minimize code length.
In this sense, published solutions are hard to beat.
For base problem, we can save one line by applying the CHAOS trick described in post #23.
After some cleaning, I got 11 lines:

10 A = a
20 B = b
30 JMP_ZERO B 90
40 X = A % B
50 A = B
60 B = X
70 JMP_ZERO B 110
80 JMP 40
90 CHAOS 90, 100, 110
100 CHAOS 90, 100, 110
110 RETURN A

This implementation works for every pair of non-negative integers; if a<b, the first loop from line 40 to line 80 simply swaps A and B.

Last fiddled with by 0scar on 2020-11-08 at 02:55
0scar is offline   Reply With Quote
Old 2020-11-08, 07:57   #35
0scar
 
Jan 2020

2·3·5 Posts
Default

For bonus problem, there's some trade-off between code length and code speed.
The published solution uses 12 lines and needs 16 steps to reach 1970 paths.
I worked on minimizing the number of steps (keeping length within the 20-line costraint).
Here are my fastest solutions, as I submitted them.
Line 30 can be dropped, by rewriting lines 40 to 90 like in previous base solution.

"BASE-5" SOLUTION: 17 LINES, 7 STEPS.

10 A = a
20 B = b
30 C = A % B
40 JMP_ZERO C 100
50 A = B
60 B = C
70 C = A % B
80 JMP_ZERO C 150
90 JMP 50
100 CHAOS 100, 110, 120, 130, 140
110 CHAOS 100, 110, 120, 130, 140
120 CHAOS 100, 110, 120, 130, 140, 150, 170
130 CHAOS 100, 110, 120, 130, 140, 150, 170
140 CHAOS 100, 110, 120, 130, 140, 150, 170
150 JMP 160
160 CHAOS 160, 170
170 RETURN B


Path counting sequence: 0, 0, 3, 16, 79, 395, 1970

This solution relies on the base-5 representation of 1968 as 30333.
Lines 100 to 140 are used to generate the powers 5^k.
Line 150 "stores" the values 3*5^k, with a one-step delay.
Line 160 "stores" the cumulative sum of such values, with a two-step delay.
Due to line 80, the value at line 150 is increased by 1 at even steps, achieving the +2 cumulative correction needed to reach 1970 at step seven.


"NEAR-BASE-7" SOLUTION: 18 LINES, 6 STEPS

10 A = a
20 B = b
30 C = A % B
40 JMP_ZERO C 100
50 A = B
60 B = C
70 C = A % B
80 JMP_ZERO C 110
90 JMP 50
100 CHAOS 110, 120, 130, 140, 150, 160
110 CHAOS 100, 110, 120, 130, 140, 150, 160
120 CHAOS 100, 110, 120, 130, 140, 150, 160, 170, 180
130 CHAOS 100, 110, 120, 130, 140, 150, 160, 170, 180
140 CHAOS 100, 110, 120, 130, 140, 150, 160, 170, 180
150 CHAOS 100, 110, 120, 130, 140, 150, 160, 170, 180
160 CHAOS 100, 110, 120, 130, 140, 150, 160, 170, 180
170 CHAOS 170, 180
180 RETURN B

Path counting sequence: 0, 0, 5, 40, 285, 1970.

This solution relies on the representation of 1970 as 5555, using weights 1, 7, 49, and 337 (slightly smaller than 7^3 = 343).
Lines 100 to 160 are used to generate the weighs w(k).
Line 160 "stores" the cumulative sum of the terms 5*w(k), with one-step delay.

Last fiddled with by 0scar on 2020-11-08 at 08:32
0scar is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
October 2019 Xyzzy Puzzles 21 2019-11-07 13:13
October 2016 R. Gerbicz Puzzles 10 2016-11-01 13:35
October 2015 LaurV Puzzles 3 2015-11-02 15:22
October 2014 Xyzzy Puzzles 8 2014-11-02 19:03
13 October is approaching! Joe O Prime Sierpinski Project 1 2010-10-09 06:12

All times are UTC. The time now is 07:18.

Sat Feb 27 07:18:16 UTC 2021 up 86 days, 3:29, 0 users, load averages: 2.21, 1.92, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.