I decided to take D for a spin with a very old problem I tried to solve my freshmen year in Computer Science.  I was using Java, and back then with only version 1.4.2 it didn't get very far, or very fast, either.

So when I came back to the same problem, I tried to use some more D features than my previous Java attempts.  I came up with a working solution extremely quickly (four hours).  That was cool.  (1)

Then I decided to write a D program to make SVG images to illustrate the solutions. (2)  I reverse-engineered the SVG images from an existing Wikipedia image script written in Perl, embellishing it to handle variable sized grids.  That took about six hours, since I had to write a parser.

All in all, it took around 1,000 microseconds to generate the solution sets, and around half a second to generate all the images. (3)

Complete success.

I thought some people here might like to see it, since it's in D.  I didn't exactly think it big enough for digitalmars.D.announce, either.

I hope someone likes it!

1. http://www.fsdev.net/browser/Knights_Challenge/Intelligent/8x8/Miller.d
2. http://www.fsdev.net/browser/Knights_Challenge/tools/SVGMaker.d
3. http://www.fsdev.net/wiki/knights-tour/Miller1

Chris Miller wrote:
> I decided to take D for a spin with a very old problem I tried to solve my freshmen year in Computer Science.  I was using Java, and back then with only version 1.4.2 it didn't get very far, or very fast, either.
> 
> So when I came back to the same problem, I tried to use some more D features than my previous Java attempts.  I came up with a working solution extremely quickly (four hours).  That was cool.  (1)
> 
> Then I decided to write a D program to make SVG images to illustrate the solutions. (2)  I reverse-engineered the SVG images from an existing Wikipedia image script written in Perl, embellishing it to handle variable sized grids.  That took about six hours, since I had to write a parser.
> 
> All in all, it took around 1,000 microseconds to generate the solution sets, and around half a second to generate all the images. (3)
> 
> Complete success.
> 
> I thought some people here might like to see it, since it's in D.  I didn't exactly think it big enough for digitalmars.D.announce, either.
> 
> I hope someone likes it!
> 
> 1. http://www.fsdev.net/browser/Knights_Challenge/Intelligent/8x8/Miller.d
> 2. http://www.fsdev.net/browser/Knights_Challenge/tools/SVGMaker.d
> 3. http://www.fsdev.net/wiki/knights-tour/Miller1

Great Stuff!

Ill give it a run -Chess being one of my passions .
Didn't see a statement of the problem as you first saw it so don't yet know what it does . I hope t find out .

Looked at your site and forum but could not leave a pst there so I guess you have to register for that and I don't join forums which are not free speech forums.

I quote from the site and thought the following pretty well says it all.

Free Advice -- If you are keen you will take comments and criticism from any source and work to fix them avidly . When you lay down rules which say " if you don't post where I want it  I will ignore it " that tells me immediately your not likely to succeed. The advice ? change your attitude quickly.

 [quote]
We prefer that you try to contact us on the forum. It's there for a reason. If you have a suggestion or a bug for our software, please, use the ticket system. We tend to ignore things that are placed where they shouldn't be.

We also have a public mailing list which we use for internal announcements.

If you absolutely have to get a hold of someone, there is also the #fsdev IRC room on freenode.

If nothing else works, you can try to email Lord Sauron directly. It's just lord_sauron at fsdev dot net.

If that still doesn't work, it's very possible that we're directly ignoring you. [/quote]

In knightstour.SVGMaker I had to change line 12 to......... txtUtil = tango.text.Util; Capital U in my distribution of Tango Snapshot-08-03-2008

I got some solutions printed in the console but how do I get the ssSVG diagrams like you get please?

To help you improve your D skills here are few notes on the first D program (the solver):
- I suggest you to put as many globals inside functions/structs as possible, to reduce global namespace pollution, so 'access' can go in loc (Loc) and vectors in 'get_legal_moves'.
- to improve readability you can put a space around operators, like in isLegalLocation.
- you may want to use a global const N = 8 instead of putting 8 everywhere.
- print_solution() shows why Python syntax is better, you can replace the first long ugly line with something like:
print "  ".join("%2d" % el for el in row)
You can do something similar with a functional lib, but it gets a bit too much hairy:
putr( map((int el){ return format("%2d", el);}, row).join("  ") );
- generally try to use less for() and more foreach, so 'clear_board' can contain just:
foreach (ref row; board)
    row[] = -1;
- opCmp can be simplified, removing the other struct method.
- Some time is spent sorting, so using a faster sort (like my fastSort) you can reduce running time. The running time for this first program goes from 0.85 s to 0.53 s on my old PC.
- In the attach there is the version with those changes (for Phobos!).

The code of your SVGmaker isn't nice looking at all (and it doesn't show the point of the arrow), the Perl version is much more readable and short (despite Perl being generally not much readable). Probably Perl is better for that kind of code, so you may want to keep it in Perl (and use D for the generation of solutions. Sometimes two languages are better than one). In alternative you can avoid most of the the parsing, creating a second printing function in the first program like this:

void print_moves(int start_loc_x, int start_loc_y) {
    char[2 * N * N] moves;
    foreach(r, row; board)
        foreach(c, el; row) {
            moves[el * 2] = '0' + r;
            moves[el * 2 + 1] = '0' + c;
        }
    writefln(moves);
}


>I was using Java, and back then with only version 1.4.2 it didn't get very far, or very fast, either.<

What's the running time of a Java version?

Bye,
bearophile

Tower  Ty Wrote:

> I got some solutions printed in the console but how do I get the ssSVG diagrams like you get please?

I put the run output into a file, Miller.txt.

Then you take SVGMaker and run it with these command line settings:

SVGMaker.exe f -file"path/to/file"

In the same directory as it was run you should get SVG images named like this:

svg0.svg
svg1.svg
svg2.svg
...

They're in the order of the output.  They're sorta fun to look at, and great for seeing if your algorithm is really working.  Sometimes looking at the numbers scroll by can be boring.

I'm planning on adding support for specifying different output paths.

If you run it without arguments it should print out a default SVG to the console for the closed solution first specified by The Turk.

bearophile Wrote:

> To help you improve your D skills here are few notes on the first D program (the solver):
> - I suggest you to put as many globals inside functions/structs as possible, to reduce global namespace pollution, so 'access' can go in loc (Loc) and vectors in 'get_legal_moves'.

I didn't know I could put something static into a struct.  Most of this was translated from memory from another (failed) attempt in C.

> - to improve readability you can put a space around operators, like in isLegalLocation.

Perhaps.  I wrote this down first on paper because I wasn't at a computer.  Normally I adhere to Java standards, but this was more like writing C, so my inexperience rubbed off on it.

> - you may want to use a global const N = 8 instead of putting 8 everywhere.

Yes, revision 2 will be interesting.

> - print_solution() shows why Python syntax is better, you can replace the first long ugly line with something like:
> print "  ".join("%2d" % el for el in row)
> You can do something similar with a functional lib, but it gets a bit too much hairy:
> putr( map((int el){ return format("%2d", el);}, row).join("  ") );

So does any of that have a practical application for D?

> - generally try to use less for() and more foreach, so 'clear_board' can contain just:
> foreach (ref row; board)
>     row[] = -1;

I did not know I could do that with an array.  I was under the impression that I would have to do something more complicated to prevent assigning an integer to a pointer to an array of integers.

> - opCmp can be simplified, removing the other struct method.

One of those was from when I was first learning how to overload opCmp.  That I could overload it with a struct and something that isn't an object was quite a revelation to me!

> - Some time is spent sorting, so using a faster sort (like my fastSort) you can reduce running time. The running time for this first program goes from 0.85 s to 0.53 s on my old PC.

I have written numerous implementations of sorting algorithms.  I just didn't feel like writing a shell sort by insertion (which I have found to be the fastest for this particular data set) just then.

> The code of your SVGmaker isn't nice looking at all (and it doesn't show the point of the arrow), the Perl version is much more readable and short (despite Perl being generally not much readable). Probably Perl is better for that kind

You're probably viewing the default run, which bothers to close the path.  The circle blots out most of the arrow.

I agree that the Perl version is more readable.  I just needed something in D, since I don't know Perl, nor do I have a Perl interpreter handy.  My D version also can handle variable sized boards, which the Perl version cannot.  I did not feel like learning enough Perl to make it handle variable sized boards, either.

> of code, so you may want to keep it in Perl (and use D for the generation of solutions. Sometimes two languages are better than one). In alternative you can avoid most of the the parsing, creating a second printing function in the first program like this:
> 
> void print_moves(int start_loc_x, int start_loc_y) {
>     char[2 * N * N] moves;
>     foreach(r, row; board)
>         foreach(c, el; row) {
>             moves[el * 2] = '0' + r;
>             moves[el * 2 + 1] = '0' + c;
>         }
>     writefln(moves);
> }

I considered ammending my rules to say that, however, the way it outputs now is nice Wiki Syntax, so I can just throw it into the Wiki without editing it.  That means I can put the SVGs in when I finally get a free moment.

The Wiki output is also a lot easier to read for debugging purposes.

> >I was using Java, and back then with only version 1.4.2 it didn't get very far, or very fast, either.<
> 
> What's the running time of a Java version?

On a 1000MHz Pentium M ULV, it was about fifteen seconds for the first solution set, 30 for the second, and a stack overflow on the third.  I beat the problem until I figured out that it was a limitation of the VM and the garbage management.  I could of course force a garbage collection call more frequently, perhaps in a separate thread, but that would be a little more involved than I was willing to get.  I was a first year CS student, don't blame me!

Java 1.6 is much faster and more robust.  I'm sure that same code (with a few migration changes, eg. the "new" for loop) would run far better with the newer language additions.  I'm not using Java now, I'm learning D.  It was a problem I was familiar with, so I made an implementation in the new language.  It was fun.

Tower  Ty Wrote:

> Ill give it a run -Chess being one of my passions .

My brother refuses to play me, and has since he was ten.  Six years later I still can't convince him to play me.

Perhaps I should make a future project of mine an online multiplayer chess game (in D, using DWT)?  It could be fun to write, and of course, to "debug".

> Didn't see a statement of the problem as you first saw it so don't yet know what it does . I hope t find out .

There's a good article on Wikipedia.  I'm afraid I lost the original document which I first got the problem from.

> Looked at your site and forum but could not leave a pst there so I guess you have to register for that and I don't join forums which are not free speech forums.

Hmm...  Excellent point.  I'll have to rethink my submission mechanism.  I was going to give an email address, though sadly whenever I put it on the 'net in one more location, that invariably creates more spam for me.

I wouldn't really call my forum non "free speech."  I just want to make sure that speech is put in the right category so when you're looking for speech, it's where it should be.  I also keep it closed to prevent the inevitable: spam.

Spam happens everywhere.  I just don't want it on my site, and I don't want to leave it open.  I don't want to spend my time deleting spam.

And obviously I censor speech that isn't legal in the United States, and stuff that would violate my web hosting contract.  If you don't like that, well, all I can say is "take it up with Uncle Sam."

> I quote from the site and thought the following pretty well says it all.
> 
> Free Advice -- If you are keen you will take comments and criticism from any source and work to fix them avidly . When you lay down rules which say " if you don't post where I want it  I will ignore it " that tells me immediately your not likely to succeed. The advice ? change your attitude quickly.

I have learned that from sad experience.  I have run forums, mailing lists, and sites where users just plain put things in the wrong place.  It's extremely annoying, and I desperately want to spend more time coding and less time playing admin.

Also, I do think it says that I tend to ignore things that aren't in the right place.

I shall amend the rules, since you do make a good point.  I really don't want too many people registering on my site, anyways.  The more passwords I'm entrusted to keep secret and away from prying eyes, the more stress on me to ensure proper security and hashing technique.  A total mess, in other words.

>  [quote]
> We prefer that you try to contact us on the forum. It's there for a reason. If you have a suggestion or a bug for our software, please, use the ticket system. We tend to ignore things that are placed where they shouldn't be.
> 
> We also have a public mailing list which we use for internal announcements.
> 
> If you absolutely have to get a hold of someone, there is also the #fsdev IRC room on freenode.
> 
> If nothing else works, you can try to email Lord Sauron directly. It's just lord_sauron at fsdev dot net.
> 
> If that still doesn't work, it's very possible that we're directly ignoring you. [/quote]

And no, I really don't ignore people very often.  Heck, I can't remember the last time I ignored someone.  Well, excluding spammers.

I just put it there to prevent any kind of conceivable liability issues.  Better safe than sorry!

Chris Miller:

>> putr( map((int el){ return format("%2d", el);}, row).join("  ") );
>So does any of that have a practical application for D?

1) This is a D forum, and lot of people here like various languages. I like many languages. I don't think adding few extra lines in my post may hurt.
2) D is an evolving language, and new things may be added to it in the future. If you don't discuss things you only keep C/C++ as a reference, and you may end with a C++-like-only language.
3) I think functional programming will become more important in the future. The last version (the one starting with putr) is actual D code you can run with my D libs. It's hairy, so it shows why a better syntax is very useful for that kind of programming. AST macros may help there. There is an alternative syntax you can use, plus the map of std.algorithms of D 2.x, and the tools by downs, etc.


>I just didn't feel like writing a shell sort by insertion (which I have found to be the fastest for this particular data set) just then.<

Probably there are other ways to improve that (a priority queue? Fibonacci Heaps? etc), but fastSort is already written...


>I agree that the Perl version is more readable.  I just needed something in D, since I don't know Perl, nor do I have a Perl interpreter handy.  My D version also can handle variable sized boards, which the Perl version cannot.<

I think a better-looking (and higher-level) D version can be written.


>I did not feel like learning enough Perl to make it handle variable sized boards, either.<

I see, then you can translate that Perl code to Python instead to D ;-)


>I'm learning D.  It was a problem I was familiar with, so I made an implementation in the new language.  It was fun.<

Good :-)

Bye,
bearophile