LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-29-2021, 01:53 AM   #76
shruggy
Senior Member
 
Registered: Mar 2020
Posts: 2,321

Rep: Reputation: Disabled

Quote:
Originally Posted by igadoter View Post
How do I split the file into separate files?
Code:
csplit WonderRing.1.2.txt /Start/ '{*}'
 
3 members found this post helpful.
Old 04-29-2021, 04:12 AM   #77
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
I knew there must be solution. It would be a shame to have to by hand cut the file into pieces. With LibreOffice.
 
Old 04-29-2021, 05:23 AM   #78
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Just a hint on sharing multi-file code in one file.

Assuming your source is in a subdir called 'myproject' in the current directory, you can use a unified diff against /var/empty to pack it up into one patch file.
e.g.
diff -Nur --strip-trailing-cr /var/empty/ myproject/ > project.patch.txt

Which could then be unpacked into the current directory with
patch -p1 < project.patch.txt


To make it slightly easier for your recipients to unpack (patch has some weird rules about choosing target files), one can replace /var/empty in the patch file with the target directory.

I wrote a bash function to make life easier:
Code:
diff_bundle()
{
  local olddir=/var/empty
  local newdir=${1:-.}

  diff -Nur --strip-trailing-cr "$olddir" "$newdir" \
    | sed "/^--- / s:$olddir:${newdir%/}:"
}
Bundles up current directory by default, with diff to stdout.

I wasn't aware of csplit. I'll have to investigate that.

Last edited by GazL; 04-29-2021 at 05:25 AM.
 
1 members found this post helpful.
Old 04-29-2021, 08:21 PM   #79
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
Ok hold fast - I posted about amazing circle from 101 numbers. And what about amazing circle from - wait - 24348 numbers? I compiled circle.c - played a little - is fast as light
Code:
$ time ./a.out 24348 43 > /dev/null

real	0m39.165s
user	0m39.121s
sys	0m0.022s
I tested output for amazing circle from 10456 numbers
Code:
$ ./a.out 10456 11
- looks ok. Can't build @dogpatch programm. I got compilation errors about missing #include <cstring> and some other errors.
 
Old 04-30-2021, 12:28 AM   #80
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,490

Rep: Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532
Quote:
Originally Posted by igadoter View Post
Ok hold fast - I posted about amazing circle from 101 numbers. And what about amazing circle from - wait - 24348 numbers? I compiled circle.c - played a little - is fast as light
Code:
$ time ./a.out 24348 43 > /dev/null

real	0m39.165s
user	0m39.121s
sys	0m0.022s
I tested output for amazing circle from 10456 numbers
Code:
$ ./a.out 10456 11
- looks ok.
The problem is not really to find the first solution, because it is relatively easy [and fast]. But to find all the different circles.

It looks like we always have a solution if the number [of numbers] is big enough. And what is the smallest circle?
 
Old 04-30-2021, 10:57 AM   #81
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Quote:
Originally Posted by shruggy View Post
Code:
csplit WonderRing.1.2.txt /Start/ '{*}'
Thank you, shruggy! The best part of this solution is that it seems to be part of basic Linux, even in my old system, without downloading a nifty utility, and without writing a clever bash script.

I will remember this next time I upload multiple files, and will use something other than 'Start' in the separator lines. Fortunately in this case, none of my code nor comments used the word 'Start' with upper case 'S'.
 
Old 04-30-2021, 10:58 AM   #82
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Quote:
Originally Posted by pan64 View Post
And what is the smallest circle?
32 is the smallest valid ring of data for square numbers. Other data rings, such as for prime numbers or triangular numbers are quite different (of course).

Last edited by dogpatch; 04-30-2021 at 11:16 AM. Reason: add qualifying remark
 
Old 04-30-2021, 11:12 AM   #83
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Question

Quote:
Originally Posted by igadoter View Post
Can't build @dogpatch programm. I got compilation errors about missing #include <cstring> and some other errors.
Yes, as noted above, you may have to add (or remove?) some header files. My GCC compiler is very old, and the header file requirements have changed since then.

Try removing
Code:
#include malloc.h
from DataRing.h, and add
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
to WonderRing.cpp.

Maybe replace <string> with <string.h>??

These are guesses; impossible for me to test with my old system. Sorry.
 
Old 04-30-2021, 11:13 AM   #84
shruggy
Senior Member
 
Registered: Mar 2020
Posts: 2,321

Rep: Reputation: Disabled
Quote:
Originally Posted by dogpatch View Post
Fortunately in this case, none of my code nor comments used the word 'Start' with upper case 'S'.
Well, the part between slashes is a regular expression, so '/\* Start /' would also do, but was unnecessary in this case. Actually, more correct splitting would be achieved with
Code:
csplit WonderRing.1.2.txt %Start% /Start/ {\*}
as this would exclude the first part.

And yes, as igadoter said above doing this with awk is fun and gives you more control:
Code:
#!/usr/bin/awk -f
/\* Start /{f=$3; next}
/\* End /{f=0; next}
f{print >f}
or in one line
Code:
awk '/\* End /{f=0}f{print>f}/\* Start /{f=$3}' WonderRing.1.2.txt

Last edited by shruggy; 05-01-2021 at 02:33 AM.
 
1 members found this post helpful.
Old 05-01-2021, 05:33 AM   #85
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
I spent a little time yesterday evening reworking my circle program.
As part of that I added a routine to try and guess a good seed value based on finding a seed with the lowest number of neighbour candidates. I wondered whether it would speed it up, but the results weren't what I expected, so I started to investigate (really should have done that before writing the code ).

These are the cpu times for a circle of 50, for each seed.
Code:
Seed 1::::::::::::::::::::::::::::::
user 3.12
Seed 2::::::::::::::::::::::::::::::
user 0.00
Seed 3::::::::::::::::::::::::::::::
user 0.00
Seed 4::::::::::::::::::::::::::::::
user 0.02
Seed 5::::::::::::::::::::::::::::::
user 0.00
Seed 6::::::::::::::::::::::::::::::
user 0.15
Seed 7::::::::::::::::::::::::::::::
user 0.03
Seed 8::::::::::::::::::::::::::::::
user 0.01
Seed 9::::::::::::::::::::::::::::::
user 0.14
Seed 10::::::::::::::::::::::::::::::
user 0.61
Seed 11::::::::::::::::::::::::::::::
user 0.74
Seed 12::::::::::::::::::::::::::::::
user 1.76
Seed 13::::::::::::::::::::::::::::::
user 2.56
Seed 14::::::::::::::::::::::::::::::
user 6.35
Seed 15::::::::::::::::::::::::::::::
user 0.23
Seed 16::::::::::::::::::::::::::::::
user 4.83
Seed 17::::::::::::::::::::::::::::::
user 0.16
Seed 18::::::::::::::::::::::::::::::
user 0.00
Seed 19::::::::::::::::::::::::::::::
user 0.00
Seed 20::::::::::::::::::::::::::::::
user 0.00
Seed 21::::::::::::::::::::::::::::::
user 0.00
Seed 22::::::::::::::::::::::::::::::
user 0.02
Seed 23::::::::::::::::::::::::::::::
user 0.01
Seed 24::::::::::::::::::::::::::::::
user 0.11
Seed 25::::::::::::::::::::::::::::::
user 0.41
Seed 26::::::::::::::::::::::::::::::
user 0.93
Seed 27::::::::::::::::::::::::::::::
user 0.01
Seed 28::::::::::::::::::::::::::::::
user 0.02
Seed 29::::::::::::::::::::::::::::::
user 0.06
Seed 30::::::::::::::::::::::::::::::
user 0.16
Seed 31::::::::::::::::::::::::::::::
user 43.35
Seed 32::::::::::::::::::::::::::::::
user 97.73
Seed 33::::::::::::::::::::::::::::::
user 1.23
Seed 34::::::::::::::::::::::::::::::
user 0.07
Seed 35::::::::::::::::::::::::::::::
user 0.11
Seed 36::::::::::::::::::::::::::::::
user 0.02
Seed 37::::::::::::::::::::::::::::::
user 0.01
Seed 38::::::::::::::::::::::::::::::
user 1.41
Seed 39::::::::::::::::::::::::::::::
user 0.75
Seed 40::::::::::::::::::::::::::::::
user 0.33
Seed 41::::::::::::::::::::::::::::::
user 0.06
Seed 42::::::::::::::::::::::::::::::
user 0.05
Seed 43::::::::::::::::::::::::::::::
user 0.00
Seed 44::::::::::::::::::::::::::::::
user 0.00
Seed 45::::::::::::::::::::::::::::::
user 0.00
Seed 46::::::::::::::::::::::::::::::
user 0.00
Seed 47::::::::::::::::::::::::::::::
user 0.00
Seed 48::::::::::::::::::::::::::::::
user 10.20
Seed 49::::::::::::::::::::::::::::::
user 0.34
Seed 50::::::::::::::::::::::::::::::
user 28.93
Seeds 31, 32, 48 and 50 stand out, with 32 being the worst of all, while seeds 2 and 5 are so fast they don't even register cpu-time.
So, lets look at their possible neighbours:
Code:
2: 47 34 23 14 7
5: 44 31 20 11 4
31: 50 33 18 5
32: 49 17 4
48: 33 16 1
50: 31 14
My seed guessing code would pick 50 in this case as it only has two candidates, but apparently, less neighbours doesn't necessarily mean a faster result. Back to the drawing board.

I wonder what makes 32 so bad, and 2 and 5 so good.

Changes in this version:
  • Refactored, and split into modules.
  • Uses a bucket structure to hold neighbour candidates rather than the link list of pairs plus an index. (Doesn't have much effect on runtime as it's essentially the same in operation, but code is tidier).
  • seed is now specified with an option: -s
  • Includes suggest_seed() function: which it turns out doesn't help any, but if we can come up with a scheme that does work, there's a function to slap it in.

To disable the useless seed guessing code I added, set DEFAULT_SEED_VALUE in circle.c to 1 rather than 0.


New reworked version of circle is attached in diff format for anyone that wants it. Unpack with
patch -p0 < circle-3.1.diff.txt
Attached Files
File Type: txt circle-3.1.diff.txt (12.7 KB, 10 views)

Last edited by GazL; 05-01-2021 at 05:46 AM.
 
1 members found this post helpful.
Old 05-01-2021, 05:39 AM   #86
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,490

Rep: Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532
Quote:
Originally Posted by GazL View Post
Seeds 31, 32, 48 and 50 stand out, with 32 being the worst of all, while seeds 2 and 5 are so fast they don't even register cpu-time.
So, lets look at their possible neighbours:
Code:
2: 47 34 23 14 7
5: 44 31 20 11 4
31: 50 33 18 5
32: 49 17 4
48: 33 16 1
50: 31 14
My seed guessing code would pick 50 in this case as it only has two candidates, but apparently, less neighbours doesn't necessarily mean a faster result. Back to the drawing board.

I wonder what makes 32 so bad, and 2 and 5 so good.
Good work!
I guess we need to take into account [not only the first but] the second and/or third neighbours too.
 
Old 05-01-2021, 08:56 AM   #87
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Quote:
Originally Posted by GazL View Post
I added a routine to try and guess a good seed value. . .
This looks very much like what i tried to do a few days ago. May you have better success! I tried various algorithms, some similar to yours, but failed to find a way to predict the optimal seed for any given ring size. So i finally concluded that the best algorithm was to simply try to generate the first ring for every ring size, and dump the results. Anyway, here is my list of pairs, optimized as best as i can, for ring size 50, which seems to be the size you are concentrating on:
Code:
order change for '1': '15'<->'8'
order change for '31': '33'<->'18'
order change for '46': '35'<->'18'
186 pairs generated
 1: 48 35 24 8 15 3
 2: 47 34 23 14 7
 3: 46 33 22 13 6 1
 4: 45 32 21 12 5
 5: 44 31 20 11 4
 6: 43 30 19 10 3
 7: 42 29 18 9 2
 8: 41 28 17 1
 9: 40 27 16 7
10: 39 26 15 6
11: 38 25 14 5
12: 37 24 13 4
13: 36 23 12 3
14: 50 35 22 11 2
15: 49 34 21 10 1
16: 48 33 20 9
17: 47 32 19 8
18: 46 31 7
19: 45 30 17 6
20: 44 29 16 5
21: 43 28 15 4
22: 42 27 14 3
23: 41 26 13 2
24: 40 25 12 1
25: 39 24 11
26: 38 23 10
27: 37 22 9
28: 36 21 8
29: 35 20 7
30: 34 19 6
31: 50 18 33 5
32: 49 17 4
33: 48 31 16 3
34: 47 30 15 2
35: 46 29 14 1
36: 45 28 13
37: 44 27 12
38: 43 26 11
39: 42 25 10
40: 41 24 9
41: 40 23 8
42: 39 22 7
43: 38 21 6
44: 37 20 5
45: 36 19 4
46: 18 35 3
47: 34 17 2
48: 33 16 1
49: 32 15
50: 31 14
... and the result of my brute force speed test for ring size 50:
Code:
050 000000Begin
050 0000217 002
050 0000233 047
050 0000480 014
050 0001046 050
050 0002447 019
050 0003431 018
050 0006920 045
050 0033371 021
050 0051589 020
050 0084151 003
050 0084155 043
050 0096164 005
050 0166748 044
050 0458607 027
050 0479123 046
050 0480074 037
050 0815690 008
050 0820156 023
050 1008194 022
050 1210275 028
050 1222623 004
050 1259218 036
050 1367831 007
050 2530394 042
050 2739107 041
050 3229208 029
050 999999*End*
The first column is the ring size, the second column is the number of recursions to generate the first ring, and the third column the seed number. So, seed 2 is the fastest, then 47, 14, etc. I set an arbitrary limit of 3400000 recursions, beyond which the speed test abandoned that seed and tried the next. If you can find an algorithm which will connect the spped test results to the array of pairs, an algorithm that works for every ring size, and thus predict the optimal seed(s) without doing a similar brute force run, i'll buy you a beer. See post #61 above for more details, and download WonderRing.1.1.txt from post #60 to get, among other things, SRopt.array, the condensed single-column array of best seeds for ring sizes 43 through 130. If you're interested, and if i have coinnection minutes later, i may try to assemble and upload the uncondensed 3-column array for ring sizes 43 through 130, which, like the above, includes the recursion value, the reliable indicator of relative speed to generate the first ring for a given ring size.
 
1 members found this post helpful.
Old 05-01-2021, 09:15 AM   #88
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
This whole exercise reminds me of my work of a couple years ago to make my sudoku analyzer run more efficiently. It's very easy and fast to generate the first possible solution for a sudoku grids with none or very few solved cells, and for one that has many solved cells. The tough sudoku to analyze is one with between about 15 to 20 cells solved. In these cases, it makes a huge difference which unsolved cell you start with, and the order in which you work from cell to cell. Working out an acceptable way to get a decent response time took me several weeks and resulted in some fairly complex code. Turns out, i had to try my best algorithm, then, if it failed within a prescribed number of processing loops, try the second algorithm, then a third...
 
2 members found this post helpful.
Old 05-01-2021, 10:53 AM   #89
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Yeah, I think finding a formula for this is going to be beyond my abilities, so I guess I'll be staying thirsty.

I tried some of the obvious approaches and non of them really worked out. 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 rather than calculate them if you do that. So, to be honest, I think I'm dead-ended at this point.
 
1 members found this post helpful.
Old 05-01-2021, 02:49 PM   #90
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
Interesting discussion!

I too have been working on this problem but with no result worth posting so far...

At some point I too, realized that trying to pick a "best" starting point based on possible pairings was not going to be always successful (though starting at the highest end, fewer pairs end of the range is weighted in your favor most often I think).

My thoughts have been to try to add an intermediate test condition to attempt earliest detection of dead end conditions rather than having to wait until the dead ended number appears for evaluation. For a contrived example, suppose the left neighbor of your seed has five possible pair partners, and successive evaluation proceeds to the right. Then suppose within a few iterations of the pairing selection you pair each of those five possibilities with other partners, never using the left-of-seed neighbor. The left neighbor is now dead ended but you will not detect that condition until some point later in the process. Surely we can manage to detect that earlier, possibly when it occurs... but my limited attempts to turn that into code based on Gazl's 2.x base have not been successful so far.

Last edited by astrogeek; 05-01-2021 at 02:50 PM. Reason: tpoys
 
2 members found this post helpful.
  


Reply

Tags
circle, perfect square, programming challenge, ring, ring data type


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
damnit!!! i cant see what im typing.. fonts are squares iLLuSionZ Linux - Newbie 22 11-18-2003 03:36 PM
characters as squares in mozilla icyfire Linux - Software 4 09-18-2003 04:22 PM
white squares appear on screen saver? bongo.hickup Linux - Hardware 0 06-13-2003 03:51 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 01:22 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration