[SOLVED] 'Circle of Squares' programming challenge
ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
just because we could save more than 100M calls to len.
I guess we can improve more again by storing that len in an additional variable and follow path instead of recalculating length. Probably I will try that later....
From the other hand I like that python implementation very much.
you can see the method len was invoked a lot, almost 7 times more than anything else.
A small modification:
Code:
# while not (len(path) == 1 and a == term): # instead of this
while not (a == term and len(path) == 1): # in line 48
will significantly improve the speed (15 %):
...
...
just because we could save more than 100M calls to len.
I guess we can improve more again by storing that len in an additional variable and follow path instead of recalculating length. Probably I will try that later....
I tried your improvement:
Code:
$ time ./PathFinderCircleOfSquares.py 40 >/dev/null
real 3m41.601s
user 3m41.468s
sys 0m0.016s
$ time ./improved_PathFinderCircleOfSquares.py 40 >/dev/null
real 3m33.675s
user 3m33.526s
sys 0m0.008s
Is a 3.6 % time reduction on my computer, but nonetheless.
Quote:
Originally Posted by pan64
From the other hand I like that python implementation very much.
that was the default python3 profiling module, cProfile. Nothing else. It looks like profilers will influence timings .... Or probably depends on the version of python?
And what about this:
Code:
# Find circle
path = [1]
a = 0
term = len(possq[1])
while not (a == term and len(path) == 1):
while True:
try:
c = possq[path[-1]][a]
if c not in path:
path.append(c)
a = 0
if len(path) == high:
print(*path, sep=' ')
break
a += 1
except:
b = path.pop()
a = possq[path[-1]].index(b) + 1
break
that was the default python3 profiling module, cProfile.
Thanks. Found it.
That's an interesting use of try except.
I thought it was kind of "expensive" to use try except. I wouldn't have thought of using it. But it works.
Quote:
Originally Posted by pan64
And what about this:
Code:
# Find circle
path = [1]
a = 0
term = len(possq[1])
while not (a == term and len(path) == 1):
while True:
try:
c = possq[path[-1]][a]
if c not in path:
path.append(c)
a = 0
if len(path) == high:
print(*path, sep=' ')
break
a += 1
except:
b = path.pop()
a = possq[path[-1]].index(b) + 1
break
Are you catching the IndexError in this line?
Code:
c = possq[path[-1]][a]
Testing:
Code:
$ time ./PathFinderCircleOfSquares.py 40 >/dev/null
real 3m33.675s
user 3m33.526s
sys 0m0.008s
$ time ./pan64_PathFinderCircleOfSquares.py 40 >/dev/null # With try except.
real 3m15.360s # That's a time saver!
user 3m15.265s
sys 0m0.004s
Yes, that will raise an exception if a was too high. Identical [more or less] to
Code:
while a < len(possq[path[-1]]):
But do not need to calculate the condition, it will automatically break the loop. Probably this is even better:
Code:
while not (a == term and len(path) == 1):
try:
while True:
c = possq[path[-1]][a]
if c not in path:
path.append(c)
a = 0
if len(path) == high:
print(*path, sep=' ')
break
a += 1
except:
b = path.pop()
a = possq[path[-1]].index(b) + 1
m = [ [0]*high ]
mr = [ [0]*high ]
for key in possq.keys():
l = possq[key]
while len(l) < high:
l.append(0)
m.append(l)
k = [0]*high
for i in range(high):
if l[i]:
k[l[i]-1] = i+1
mr.append(k)
mr is a reverse lookup matrix to speed up index calls
the loop will be quite simple:
Code:
def circle():
path = [1]
a = 0
term = len(possq[1])
while not (a == term and len(path) == 1):
while True:
c = m[path[-1]][a] # = possq[path[-1]][a]
if c == 0:
b = path.pop()
a = mr[path[-1]][b-1] # = possq[path[-1]].index(b) + 1
break;
if c not in path:
path.append(c)
a = 0
if len(path) == high:
print(*path, sep=' ')
break
a += 1
And I think it is really definitely faster now.
And if you use numpy martices it will be much slower.....
2. Each element in the ring must be within the defined limits. In this case, between 1 and 32, with each number occurring exactly once (in any order).
Hello, please share with your mathematician friend my view that 1 and 2 are not "numbers" but "functions" (additionally to "+" "-" "*"). Perhaps it will making thinking differently in his problem.
1: is an "Increment" (some others were representing/using this as a dirac impulse) in sense of combination with "+" and "invariant" in sense of use with "*"
2: is a "Doubling" in the sense of "elliptical" thinking in combination with "*"
And I would be interested to see the result of some "circles" by taking them out.
Last edited by floppy_stuttgart; 05-09-2021 at 03:04 AM.
Hello, please share with your mathematician friend my view that 1 and 2 are not "numbers" but "functions" (additionally to "+" "-" "*"). Perhaps it will making thinking differently in his problem.
1: is an "Increment" (some others were representing/using this as a dirac impulse) in sense of combination with "+" and "invariant" in sense of use with "*"
2: is a "Doubling" in the sense of "elliptical" thinking in combination with "*"
And I would be interested to see the result of some "circles" by taking them out.
Probably it is about me. Here in this thread there is c program. With help of it I generated amazing circle containing ca 24 thousands of numbers. And essentially I was little bored to look for larger sequences. The problem is of mathematics of course - but here main point is set on programming tools. About your concept numbers to be functions please elaborate little more.
m = [ [0]*high ]
mr = [ [0]*high ]
for key in possq.keys():
l = possq[key]
while len(l) < high:
l.append(0)
m.append(l)
k = [0]*high
for i in range(high):
if l[i]:
k[l[i]-1] = i+1
mr.append(k)
I like the way how you've used 0 to control the loop. Saves a lot of len() calls.
I changed your lookup lists into dictionaries. That sped things up some more.
Code:
$ time old_circleOfSquares.py 40 >/dev/null
real 2m33.655s
user 2m33.544s
sys 0m0.053s
$ time new_circleOfSquares.py 40 >/dev/null
real 2m6.746s
user 2m5.758s
sys 0m0.168s
$ time ./circle -va 40 |grep results
64 results returned.
real 0m0.814s
user 0m0.817s
sys 0m0.000s
$ time ./circle -va 41 |grep results
464 results returned.
real 0m2.531s
user 0m2.532s
sys 0m0.004s
$ time ./circle -va 42 |grep results
1062 results returned.
real 0m7.798s
user 0m7.800s
sys 0m0.001s
For those of you running your own code, do those "results returned" numbers agree with what you get?
Yes, i get the same counts 64 464 1062 for ring sizes 40 41 42. Didn't try -a all rings beyond 42, but assume would agree there as well. (These are numbers without mirrors, or duplicates, right?)
Yes, i get the same counts 64 464 1062 for ring sizes 40 41 42. Didn't try -a all rings beyond 42, but assume would agree there as well. (These are numbers without mirrors, or duplicates, right?)
Thanks for the confirmation.
Yes, these totals exclude mirrored results, which the latest version of my program no longer finds. Also, I don't believe that it was possible for my code to return a non-mirrored duplicate result, even before I changed it.
I'll share the new version once I've had time to clean it up a little.
I was all set to upload my latest code, but LQ's new security feature won't let me. May try another way to make it available. Meanwhile, here's my progress report:
A couple performance improvements:
Rather than try various strategems for ordering the array of pairs, am now using a single multi-layered approach. Ordering the pairs in reverse order, favoring larger values first, is generally more efficient because larger numbers tend to have fewer associated pairs. It makes even more sense to favor those target numbers that occur less frequently, which is not alwys the same thing. Using the target frequency method gives me fast results in most ring size / seed cases. Most, but not all.
Quote:
Originally Posted by GazL
. . .I don't really see the point in using an array of pre-determined seed values as one may as well have a array of full results. . .
hmmm. . . an interesting thought. Well, as noted above, i've abandoned the kludgy array of pre-set seed values. But if the program were to quickly pre-set an entire valid array. . .
The target frequency method gives fast results in so many ring size / seed cases that for pretty much all ring sizes there are seed values for which it can give a very fast result. (Tested thoroughly for ring sizes up to 400, spot checked up to 1000.) Using this confidence, my program now solves for a given ring size / seed by trying several seeds in a quick loop until it gets a valid result. The sequence of pairs thus generated is then used to optimize the global pairs array so that the 'real' logic can generate the first valid ring for the 'real' seed with minimal recursions.
This, of course, is only beneficial for the first generated ring; it does not appreciably affect the speed to generate all rings for a given size.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.
May try another way to make it available. Meanwhile, here's my progress report:
