October 2020 - Solution

<< September November >>

October 2020 Challenge

The GCD algorithm is very easy to implement (which is why it was chosen) and is presented in the first block of code. On top of such an implementation, an alternative path in the CFG can be added that contains a loop, enabling the amplification of the number of paths required (this is the second block of code):

10 A = a
20 B = b
30 JMP_ZERO B 80
40 X = A % B
50 A = B
60 B = X
70 JMP 30
80 RETURN A

24 Z = 42
25 JMP_ZERO A 75
75 CHAOS 76, 77, 80
76 CHAOS 75, 77, 80
77 CHAOS 75, 76, 80

And a program with 1970 paths is:

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