mersenneforum.org October 2020
 Register FAQ Search Today's Posts Mark Forums Read

2020-11-08, 02:48   #34
0scar

Jan 2020

31 Posts

Quote:
 Originally Posted by SmartMersenne 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

 2020-11-08, 07:57 #35 0scar   Jan 2020 31 Posts 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

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

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

Sun May 9 07:59:44 UTC 2021 up 31 days, 2:40, 0 users, load averages: 2.82, 3.11, 3.21