August 24, 2012
maarten van damme:

> http://dpaste.dzfl.pl/8a2aef5b

Some suggestions about the code:
- Put a space before and after operators, after a commas and semicolon, around "..", etc.
- Compile with "-wi -property";
- Try to add pure/const/nothrow/immutable where possible;
- Minimize the need of cast();
- Sometimes it's useful to localize the imports (stdio e datetime are used just by the main);
- Minimize the usage of magical constants like 0b10_0000_0000, possibly define it only once. And often adding underscores inside long numbers is handy (here I have put them every 4 digits because it's binary);
- Repeating things like "short[81]" in many function signatures is quite bad. Better to define a global type with alias (or someday better with std.typecons.Typedef when it will work), and then use it;
- Generally it's better to use unsigned values for array indexes;
- If you look for performance and your program is single thread, then it's better to annotate global variables with __gshared;

- This:
    ubyte[81] taken = false;
is better than this:
    ubyte[81] taken;
    taken[] = false;


This is your code modified, it's also a little faster:
http://dpaste.dzfl.pl/06510dcd

I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection.

Bye,
bearophile
August 24, 2012
> I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection.

Yeah, it's a bit faster, but not a lot:
http://dpaste.dzfl.pl/b04a0127

Bye,
bearophile
August 24, 2012
> Some suggestions about the code:
Thank you very much for your criticism, there are indeed a lot of points where I have to improve on.

> - Put a space before and after operators, after a commas and semicolon,
> around "..", etc.
> - Compile with "-wi -property";
> - Try to add pure/const/nothrow/immutable where possible;

I realize the usefullness of keywords like these but having to type
them over and over again tends to become rather annoying. There are
functions where the implementation is shorter than it's declaration...
Is there a special reason I should use them in little programs like these?

> - Minimize the need of cast();
> - Sometimes it's useful to localize the imports (stdio e datetime are used
> just by the main);
> - Minimize the usage of magical constants like 0b10_0000_0000, possibly
> define it only once. And often adding underscores inside long numbers is
> handy (here I have put them every 4 digits because it's binary);
> - Repeating things like "short[81]" in many function signatures is quite
> bad. Better to define a global type with alias (or someday better with
> std.typecons.Typedef when it will work), and then use it;
> - Generally it's better to use unsigned values for array indexes;
> - If you look for performance and your program is single thread, then it's
> better to annotate global variables with __gshared;

I'm not all that familiar with __gshared, why does it increase performance?

>
> - This:
>     ubyte[81] taken = false;
> is better than this:
>     ubyte[81] taken;
>     taken[] = false;

I know and I think I can even leave false out because the default value of ubyte is 0 => false. I had a big in my code and it took me a long time to find it. That line is a leftover of a desperate attempt at finding it :) (as is line 101)

I even tried using array!bool but even instantiating failed so I gave up. Would performance increase be noticeable? I guess not.
>
>
> This is your code modified, it's also a little faster: http://dpaste.dzfl.pl/06510dcd
>

Thank you. I see you also used contracts, looks better now :)
(using contracts is really something I should start doing...)

> I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection.
>
> Bye,
> bearophile


I should also add a little check to see if every value I put is indeed numerical.
August 24, 2012
On 08/24/2012 09:32 PM, maarten van damme wrote:
> I've distiled what I understood from your source and the resulting
> executable managed to solve the impossible one in 27 seconds while
> your source takes 41 seconds.
>

It is 10s vs 13s with GDC on my machine.

August 24, 2012
and everythingPossible should also be changed to something ala 2 ^(side) -1
August 24, 2012
2012/8/25 Timon Gehr <timon.gehr@gmx.ch>:
> On 08/24/2012 09:32 PM, maarten van damme wrote:
>>
>> I've distiled what I understood from your source and the resulting executable managed to solve the impossible one in 27 seconds while your source takes 41 seconds.
>>
>
> It is 10s vs 13s with GDC on my machine.
>

I've only tried dmd but I'm installing gdc on this laptop too.
When that's done I'm going to see how they both perform on this puzzle
: http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg
August 25, 2012
maarten van damme:

> Is there a special reason I should use them in little programs like these?

In my experience small programs contain lot of the issues and ideas contained in large programs. Using things like "pure" and "const/immutable" helps avoid/catch some bugs even in small programs.
Generally try to make your code as strong as possible, to avoid chances of introducing bugs.


> I'm not all that familiar with __gshared, why does it increase performance?

That implements global variables as in C. Take a look at the D docs, about thread-local memory, etc.


> Would performance increase be noticeable? I guess not.

In your code I have seen performance increase replacing ubyte[] with bool[].


> (using contracts is really something I should start doing...)

Yep. It's a matter of self-training.


> I should also add a little check to see if every value I put is indeed numerical.

That's very easy to do:

    if (args[1].length != size || args[1].countchars("0-9") != args[1].length) {
        writeln("A sudoku is 81 0-9 digits, not ", args[1].length, " digits");
        return;
    }

Bye,
bearophile
August 25, 2012
On 08/25/2012 01:01 AM, Timon Gehr wrote:
> On 08/24/2012 09:32 PM, maarten van damme wrote:
>> I've distiled what I understood from your source and the resulting
>> executable managed to solve the impossible one in 27 seconds while
>> your source takes 41 seconds.
>>
>
> It is 10s vs 13s with GDC on my machine.
>

I have inlined some ranges.

http://dpaste.dzfl.pl/4a7e4038

I now measure 10.5s vs 6.7s (GDC) and 20s vs 12s (DMD).
August 25, 2012
On 08/25/2012 02:38 AM, Timon Gehr wrote:
> On 08/25/2012 01:01 AM, Timon Gehr wrote:
>> On 08/24/2012 09:32 PM, maarten van damme wrote:
>>> I've distiled what I understood from your source and the resulting
>>> executable managed to solve the impossible one in 27 seconds while
>>> your source takes 41 seconds.
>>>
>>
>> It is 10s vs 13s with GDC on my machine.
>>
>
> I have inlined some ranges.
>
> http://dpaste.dzfl.pl/4a7e4038
>
> I now measure 10.5s vs 6.7s (GDC) and 20s vs 12s (DMD).

I meant to paste this: http://dpaste.dzfl.pl/8fa23a97
August 25, 2012
On Friday, 24 August 2012 at 23:14:02 UTC, maarten van damme wrote:
> http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg

It occurs to me that one of the main reasons why this particular puzzle would be hard for brute force is that the first line is blank and more than half of the second line is blank, and it seems like it is designed to have as many choices as possible before a set square is encountered.

I bet it could be solved much quicker by a computer by doing it in reverse.

I've got some ideas, maybe I'll write a solution to this myself. :)
1 2 3 4 5 6 7 8
Top | Discussion index | About this forum | D home