mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-10-01, 11:32   #1
tgan
 
Jul 2015

24 Posts
rolleyes October 2020

https://www.research.ibm.com/haifa/p...tober2020.html


This one looks complicated
tgan is offline   Reply With Quote
Old 2020-10-01, 13:28   #2
uau
 
Jan 2017

1178 Posts
Default

The control graph example image at the end ("Here's a sample program, along with its control-flow graph:") doesn't seem to load.
uau is offline   Reply With Quote
Old 2020-10-01, 18:46   #3
SmartMersenne
 
Sep 2017

22×3×7 Posts
Default

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.
SmartMersenne is offline   Reply With Quote
Old 2020-10-01, 19:57   #4
SmartMersenne
 
Sep 2017

8410 Posts
Default

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

https://torstencurdt.com/tech/posts/...ative-numbers/
SmartMersenne is offline   Reply With Quote
Old 2020-10-02, 05:47   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

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


Hint: https://cs.stackexchange.com/questions/63572/what-is-the-mathcal-o-of-subtraction-based-gcd-algorithm
Citrix is offline   Reply With Quote
Old 2020-10-05, 08:13   #6
Dieter
 
Oct 2017

97 Posts
Default

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.
Dieter is offline   Reply With Quote
Old 2020-10-05, 09:40   #7
SmartMersenne
 
Sep 2017

22·3·7 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
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.
SmartMersenne is offline   Reply With Quote
Old 2020-10-05, 09:47   #8
virgo
 
Apr 2020

516 Posts
Smile

Its similar to assembly codes
I think its about how to make jump below( jump condition on a>b or a<b) logic within 20lines
btw I still dont know why they added chaos operator
virgo is offline   Reply With Quote
Old 2020-10-05, 10:17   #9
Dieter
 
Oct 2017

97 Posts
Default

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!
Dieter is offline   Reply With Quote
Old 2020-10-05, 19:22   #10
uau
 
Jan 2017

79 Posts
Default

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.
uau is offline   Reply With Quote
Old 2020-10-05, 20:56   #11
Dieter
 
Oct 2017

97 Posts
Default

Quote:
Originally Posted by uau View Post
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.
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.
Dieter 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 01:49.

Sat Oct 31 01:49:08 UTC 2020 up 50 days, 23 hrs, 2 users, load averages: 1.75, 1.75, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.