October 2020
 

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/October2020.html[/url]


This one looks complicated

The control graph example image at the end ("Here's a sample program, along with its control-flow graph:") doesn't seem to load.

The question is also ill-posed, needs many clarifications. For example: how does the algorithm will work for negative integers? Return value of modulo operation changes from one programming language to another.

Here are the different results of modulo operation for negative numbers in some commonly known languages:

[URL="https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/"]https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/[/URL]

Possible hint if I understand the question correctly (I agree that the language is not very clear).

[SPOILER]
Hint: https://cs.stackexchange.com/questions/63572/what-is-the-mathcal-o-of-subtraction-based-gcd-algorithm
[/SPOILER]

Can anyone explain to me
- why the ** in "**20** lines"?
- why the $ in "length $n$"?
- which other path than 10-20-30-40-70-90 is possible in the sample program?
- what will say "the number of paths ... is the sequence 0,2,2,...?" Isn't the number dependent of a,b? Does 0 make sense?
Perhaps I'm the only one who doesn't understand this.

[QUOTE=Dieter;558925]Can anyone explain to me
- why the ** in "**20** lines"?
- why the $ in "length $n$"?
- which other path than 10-20-30-40-70-90 is possible in the sample program?
- what will say "the number of paths ... is the sequence 0,2,2,...?" Isn't the number dependent of a,b? Does 0 make sense?
Perhaps I'm the only one who doesn't understand this.[/QUOTE]

Trust me, you are not the only one.

I think ** and $ is just for formatting, and you can ignore.

The sample program is not an indicator of what to expect from the real problem, let alone the missing image is not helping at all.

Its similar to assembly codes :smile:
[SPOILER]I think its about how to make jump below( jump condition on a>b or a<b) logic within 20lines[/SPOILER]
btw I still dont know why they added chaos operator

It's no problem to write a code with 20 lines (not using "chaos lines", of course) for the search of the gcd, if I take a>b>0 for granted, and to draw the control-flow graph. But the paths are dependent of a and b, and so I don't know how to achieve the given sequence. And the zero!

I interpreted it as creating the control-flow graph based only on the existence of jump commands, so it does not depend on values of a and b. Actual behavior of the program will depend on those, but the graph won't.

I believe the sequence 0, 2, 2, ... starts from 1 for path length (that's another kind-of-flaw in the problem description, as it links to an OEIS sequence with a definition that doesn't match, without mentioning that you need a different offset). The 0 means that there is no direct path from the starting node in the graph to the end node, then 2 means there are 2 possible paths with 2 steps.

[QUOTE=uau;558979]I interpreted it as creating the control-flow graph based only on the existence of jump commands, so it does not depend on values of a and b. Actual behavior of the program will depend on those, but the graph won't.

I believe the sequence 0, 2, 2, ... starts from 1 for path length (that's another kind-of-flaw in the problem description, as it links to an OEIS sequence with a definition that doesn't match, without mentioning that you need a different offset). The 0 means that there is no direct path from the starting node in the graph to the end node, then 2 means there are 2 possible paths with 2 steps.[/QUOTE]

Thank you. Good explanation. The length of a path from the entry node to the exit node is the number of needed edges. a6 = 17 will say that there are 17 different paths from entry to exit needing 6 edges.
Meanwhile the cfg of the example can be seen, and it were a good exercise to write down the sequence:
0,0,0,1,... (there is no path of length 1,2,3 and only one path of length 4)
Unfortunately I don't understand the edge from 60 to 70.

The task makes sense only, if for a given set of commands the cfg is unique.

If I want to code "if x=0 then goto y else goto z", I have to write:

JMP_ZERO x y
JMP z

JMP_ZERO x y ends the actual block. JMP z can only be at the end a block, too.
So JMP z has to be a new single statement block?

[QUOTE=Dieter;558982]
Unfortunately I don't understand the edge from 60 to 70.[/QUOTE]

That's clearly a mistake in the figure.

[QUOTE=SmartMersenne;559012]That's clearly a mistake in the figure.[/QUOTE]

Unless it implies that the chaos operator can let the program move to next instruction or force a jump to an instruction from the list, an even more "chaotic" (and undocumented) behaviour.

[QUOTE=0scar;559029]Unless it implies that the chaos operator can let the program move to next instruction or force a jump to an instruction from the list, an even more "chaotic" (and undocumented) behaviour.[/QUOTE]

I would normally call you "paranoid" but now I wouldn't be surprised given the low quality of the website recently.

[QUOTE=Dieter;559009]The task makes sense only, if for a given set of commands the cfg is unique.

If I want to code "if x=0 then goto y else goto z", I have to write:

JMP_ZERO x y
JMP z

JMP_ZERO x y ends the actual block. JMP z can only be at the end a block, too.
So JMP z has to be a new single statement block?[/QUOTE]

Yes, because you can't have any jump statements (JMP_ZERO above) in the middle of a block.

7 solvers on the 11th of the month! In May 2019 (several people want to cross a river, but there are restrictions...) there were 5 solvers on the 10th. Oded gave one more month to solve the challenge. At last there were 24 solvers on the end of the second month.
By the way - Gadi has removed the edge from 60 to 70 in the sample program.

[QUOTE=Dieter;559660]Gadi has removed the edge from 60 to 70 in the sample program.[/QUOTE]

"I think I'm paranoid / And complicated..."
(Garbage, Version 2.0, 1998)

At least, now the text seems unambiguous enough to ponder this problem...

[QUOTE=0scar;559669]"I think I'm paranoid / And complicated..."
(Garbage, Version 2.0, 1998)

At least, now the text seems unambiguous enough to ponder this problem...[/QUOTE]
[url]https://www.youtube.com/watch?v=foSMxgcYL6U[/url]

Very nice song have not know it before

[QUOTE=Dieter;559660]7 solvers on the 11th of the month! In May 2019 (several people want to cross a river, but there are restrictions...) there were 5 solvers on the 10th.[/QUOTE]
In my opinion, May19 and Oct18 (different area triangles) were much harder than Oct20.
Perhaps now many frequent solvers actually submitted wrong solutions or no solutions at all due to the unclear/contradictory problem explanation.
At least, this is my case.
As soon as the picture was fixed, the number of correct solutions roughly doubled,
I guess it will further increase in few days, and this month will end up with about as many solvers as July20.

[QUOTE=0scar;559840]In my opinion, May19 and Oct18 (different area triangles) were much harder than Oct20.
Perhaps now many frequent solvers actually submitted wrong solutions or no solutions at all due to the unclear/contradictory problem explanation.
At least, this is my case.
As soon as the picture was fixed, the number of correct solutions roughly doubled,
I guess it will further increase in few days, and this month will end up with about as many solvers as July20.[/QUOTE]

For me, the explanation of uau (#10) was the breakthrough for the understanding of the challenge.

[QUOTE=0scar;559840]In my opinion, May19 and Oct18 (different area triangles) were much harder than Oct20.
Perhaps now many frequent solvers actually submitted wrong solutions or no solutions at all due to the unclear/contradictory problem explanation.
At least, this is my case.
As soon as the picture was fixed, the number of correct solutions roughly doubled,
I guess it will further increase in few days, and this month will end up with about as many solvers as July20.[/QUOTE]

I really doubt that it will come anywhere close to July20.

[QUOTE=SmartMersenne;560230]I really doubt that it will come anywhere close to July20.[/QUOTE]

I wish I could call you "pessimistic".
Looking at the past three years, Oct20 seems somehow similar to Nov17, another "find-constrained-algorithm" challenge. Nov17 was actually solved by 23 people only.
On the other hand, both Oct20 and July20 deal with linear-recurrenced sequences, candidate solutions can be analyzed with similar linear algebra methods.

About CHAOS, I found it useful to know that the following kind of instruction is permitted:
30 CHAOS 30, 40, 50, ...
so that the control flow graph has an edge from a one-line block to itself.

[QUOTE=0scar;560480]I wish I could call you "pessimistic".
Looking at the past three years, Oct20 seems somehow similar to Nov17, another "find-constrained-algorithm" challenge. Nov17 was actually solved by 23 people only.
On the other hand, both Oct20 and July20 deal with linear-recurrenced sequences, candidate solutions can be analyzed with similar linear algebra methods.

About CHAOS, I found it useful to know that the following kind of instruction is permitted:
30 CHAOS 30, 40, 50, ...
so that the control flow graph has an edge from a one-line block to itself.[/QUOTE]

But that isn't necessary! There are solutions for both problems (0,2,2,... and 1970) without using this trick.

[QUOTE=Dieter;560493]But that isn't necessary! There are solutions for both problems (0,2,2,... and 1970) without using this trick.[/QUOTE]

I agree at 100% with you.
Had it been necessary, writing it would have been too spoiling.
I only wrote that I found it useful (shorter code, faster reaching 1970)

[QUOTE=0scar;560515]I agree at 100% with you.
Had it been necessary, writing it would have been too spoiling.
I only wrote that I found it useful (shorter code, faster reaching 1970)[/QUOTE]

How fast? My fastest is 1970 = 10th value of the sequence, but I search no more.

[QUOTE=Dieter;560521]How fast? My fastest is 1970 = 10th value of the sequence, but I search no more.[/QUOTE]

The "trick" itself is just one more degree of freedom in writing code.
Of course I can remove all "tricky" edges from my solutions; the easiest way requires to keep the same number of incoming/outcoming edges by adding suitable nodes as new sources/destinations, which means some more CHAOS lines.
As an example, the length of my 7-step bonus solution grows from 17 to 19, not a problem, but I judge the "tricky" version more efficient.
So far, I found no "untricky" solutions which fit both the 6-step and the 20-line constraints.

I don't fully understand the second block of code within published base solution.
I suppose that new code lines must be inserted as follows:

[QUOTE]10 A = a
20 B = b
24 Z = 42
25 JMP_ZERO A 75
30 JMP_ZERO B 80
40 X = A % B
50 A = B
60 B = X
70 JMP 30
75 CHAOS 76, 77, 80
76 CHAOS 75, 77, 80
77 CHAOS 75, 76, 80
80 RETURN A[/QUOTE]

If a and b are non-negative integers with a >= b, it makes sense.

What about line 24?
I argue that Gadi's program also computes the Answer to Life, the Universe, and Everything.
But it won't be returned before seven and a half million years...

[QUOTE=0scar;562196]I don't fully understand the second block of code within published base solution.
I suppose that new code lines must be inserted as follows:



If a and b are non-negative integers with a >= b, it makes sense.

What about line 24?
I argue that Gadi's program also computes the Answer to Life, the Universe, and Everything.
But it won't be returned before seven and a half million years...[/QUOTE]

The question was stupid to start with. Our goal is to find better and efficient solutions everywhere but in this question, we are intentionally adding stupidity (chaos) to the solution.

[QUOTE=0scar;560480]I wish I could call you "pessimistic".
Looking at the past three years, Oct20 seems somehow similar to Nov17, another "find-constrained-algorithm" challenge. Nov17 was actually solved by 23 people only.
On the other hand, both Oct20 and July20 deal with linear-recurrenced sequences, candidate solutions can be analyzed with similar linear algebra methods.
[/QUOTE]

Yup, the number of solvers was barely able to reach 25, so clarification didn't have a special boost.

[QUOTE=SmartMersenne;562211]The question was stupid to start with. Our goal is to find better and efficient solutions everywhere but in this question, we are intentionally adding stupidity (chaos) to the solution.[/QUOTE]
[QUOTE=SmartMersenne;562215]Yup, the number of solvers was barely able to reach 25, so clarification didn't have a special boost.[/QUOTE]

As a joke, we could say that few people were stupid enough to solve the puzzle

[QUOTE=0scar;562196]I don't fully understand the second block of code within published base solution.
I suppose that new code lines must be inserted as follows:



If a and b are non-negative integers with a >= b, it makes sense.

What about line 24?
I argue that Gadi's program also computes the Answer to Life, the Universe, and Everything.
But it won't be returned before seven and a half million years...[/QUOTE]

Perhaps line 24 contains a hint for the november challenge...

[QUOTE=Dieter;562257]Perhaps line 24 contains a hint for the november challenge...[/QUOTE]

I still believe that variable "Z" stands for "Zaphod Beeblebrox" :-)

[QUOTE=SmartMersenne;562211]Our goal is to find better and efficient solutions everywhere[/QUOTE]
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:

[FONT="Courier New"]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
[/FONT]
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.

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.

[FONT="Courier New"] 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[/FONT]

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

[FONT="Courier New"] 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
[/FONT]
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.