Knight's Challenge in D

[Chris Miller]

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.