On Monday, 20 August 2012 at 23:59:44 UTC, Era Scarecrow wrote:
> Optimized I had the code at 5 seconds in my recently updated format, however now it increased to 31 seconds.  That makes it 6-7 times slower by not using the two potential exceptions.

 Correction, bug in my code. That dropped it to 300ms. Once again, Pleasantly Wow... :P

On 08/19/2012 02:39 AM, maarten van damme wrote:

> -is it normal that const ref is slower then ref?

Not normal but it can be arranged. :p

import std.stdio;
import core.thread;

struct S
{
    void foo()
    {}

    void foo() const
    {
        Thread.sleep(dur!("seconds")(3));
    }
}

void takes_ref(ref S s)
{
    s.foo();
}

void takes_const_ref(const ref S s)
{
    s.foo();
}

void main()
{
    auto s = S();
    takes_ref(s);
    takes_const_ref(s);
}

Ali

2012/8/17, Chris Cain <clcain@uncg.edu>:
>
> Gonna chime in a bit here:
>
> There's a lot of factors at play when deciding to use shorts vs bytes vs native-sized ints. The best way to decide is to time all of them and see which works best overall.
>
> With caching on a larger problem, I'd guess that the smaller you go, the better. The reason is that you run the risk of your data getting large enough that it can't all fit in the L2 cache and waiting for information to come from memory takes forever (comparatively speaking).
>
> Also, I just looked at your solution (not Mr. Gehr's solution), but it looks like you could approach this much more efficiently.
>
> It seems like you're storing a lot of information in arrays of ints. At least some of that could be stored in a bitmap/bitset (http://en.wikipedia.org/wiki/Bit_array) and give you significantly better memory efficiency. Array!bool in std.container will actually do the correct thing and store things like a bitset, so you don't necessarily have to implement your own (however, I think that it stores it in an int when you could use a short to hold 1-9 ... but it's not enough to really worry about).
>

I've been using my phone the last few days to check my emails and overlooked this message. I've never heard about std.container but this could indeed be a more efficient solution. I'm now storing a lot in bytes but that's still 8 times too much :)

> Try this:
> http://dpaste.dzfl.pl/23b1b6e2

Thank you very much, this makes everything more clearer. I'm not very
familiar with binary operators so the comments help out a lot.
Would you mind it if I shamelessly copy your solution of using shorts
to store possibilities in?

I'm also a bit confused. How come the int's you change from a square passed from squ are stilled referenced to the original array? I thought it lost that reference as soon as you did any operations (like concenating) on it?

> Was that sarcasm? My own code only uses copying when it's working in the next section of brute force, otherwise it's all referenced.

No, that wasn't sarastic. If you look at my last code you see that I "compose" the squares using something like [....] ~ [.....] ~ [.....] Using a foreach loop and copying the values was 10 times faster...

>  I only use exceptions twice and both when it would be unable to find a solution; I suppose I can try putting nothrow on everything and return a bool if it had an error for solving, or when it had to, inside a structure. Mmmm... I'll give it a try.

Yes but when your solver reaches a solution that is wrong, you get a whole "branch" of numbers falling of, all throwing a "broken sudoku" exception. It will rarely be called once.

> Not normal but it can be arranged. :p

But I used it in my getRegion code where I do simple calculations on the contents of that array. It is slower there...

On Tuesday, 21 August 2012 at 15:55:08 UTC, maarten van damme wrote:
> Thank you very much, this makes everything more clearer. I'm not very familiar with binary operators so the comments help out a lot. Would you mind it if I shamelessly copy your solution of using shorts to store possibilities in?

 Binary operators are fun :) Once you get the hang of it you know exactly what you're doing. Think of AND = Keep only, OR = Set, Xor = switch state. so.

 AND &
 source  0 0 1 1
 data    0 1 0 1
 result  0 0 0 1

 OR |
 source  0 0 1 1
 data    0 1 0 1
 result  0 1 1 1

 Xor ^
 source  0 0 1 1
 data    0 1 0 1
 result  0 1 1 0

>> Was that sarcasm? My own code only uses copying when it's working in the next section of brute force, otherwise it's all referenced.

> No, that wasn't sarastic. If you look at my last code you see that I "compose" the squares using something like [....] ~ [.....] ~ [.....] Using a foreach loop and copying the values was 10 times faster...

 Curious. With fixed array sizes it should do a bulk memory copy, unless you are going from static/fixed to dynamic. Also curious is in my code it allowed me to do a forced struct copy (move?) when I found a success and just copied the result to the current structure. I'll post my two revisions up later.

>> I only use exceptions twice and both when it would be unable to find a solution; I suppose I can try putting nothrow on everything and return a bool if it had an error for solving, or when it had to, inside a structure. Mmmm... I'll give it a try.

> Yes but when your solver reaches a solution that is wrong, you get a whole "branch" of numbers falling of, all throwing a "broken sudoku" exception. It will rarely be called once.

 True. I already tried removing it, and curiously enough the code performs 10x-200x faster. Except all my debugging statements now fail since they aren't nothrow :P

>> Not normal but it can be arranged. :p
>
> But I used it in my getRegion code where I do simple calculations on the contents of that array. It is slower there...

On 08/21/2012 05:52 PM, maarten van damme wrote:
> > On 08/20/2012 11:49 PM, Timon Gehr wrote:> On 08/20/2012 10:43 PM, 
maarten van damme wrote:
>>>
>>> Still it comes nowhere near beating timons solution. Is the logic of
>>> that documented somewhere because I don't understand it.
>>>
>>
>> Try this:
>> http://dpaste.dzfl.pl/23b1b6e2
>
> Thank you very much, this makes everything more clearer. I'm not very
> familiar with binary operators so the comments help out a lot.
> Would you mind it if I shamelessly copy your solution of using shorts
> to store possibilities in?
>

Not at all.

> I'm also a bit confused. How come the int's you change from a square
> passed from squ are stilled referenced to the original array? I
> thought it lost that reference as soon as you did any operations (like
> concenating) on it?
>

The used ranges just express patterns of iteration. They replace manual
for-loops. The data source has assignable elements, and the relevant
range operations in Phobos all propagate this capability to their
result.

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.

I've probably violated every D guideline concerning the use of static,
pure, nothrow,... but it works perfectly :)
It does fail to compile on dpaste, I have no idea why. It does compile
on my machine though...

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

2012/8/21, Timon Gehr <timon.gehr@gmx.ch>:
> On 08/21/2012 05:52 PM, maarten van damme wrote:
>> > On 08/20/2012 11:49 PM, Timon Gehr wrote:> On 08/20/2012 10:43 PM,
> maarten van damme wrote:
>>>>
>>>> Still it comes nowhere near beating timons solution. Is the logic of that documented somewhere because I don't understand it.
>>>>
>>>
>>> Try this:
>>> http://dpaste.dzfl.pl/23b1b6e2
>>
>> Thank you very much, this makes everything more clearer. I'm not very
>> familiar with binary operators so the comments help out a lot.
>> Would you mind it if I shamelessly copy your solution of using shorts
>> to store possibilities in?
>>
>
> Not at all.
>
>> I'm also a bit confused. How come the int's you change from a square passed from squ are stilled referenced to the original array? I thought it lost that reference as soon as you did any operations (like concenating) on it?
>>
>
> The used ranges just express patterns of iteration. They replace manual for-loops. The data source has assignable elements, and the relevant range operations in Phobos all propagate this capability to their result.
>
>

On Friday, 24 August 2012 at 19:32:53 UTC, 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.
>
> I've probably violated every D guideline concerning the use of static,
> pure, nothrow,... but it works perfectly :)

Nice job! I looked at it quickly, but it seems like a good solution.

> It does fail to compile on dpaste, I have no idea why. It does compile
> on my machine though...
>
> http://dpaste.dzfl.pl/8a2aef5b

It's because dpaste is compiling for 64-bit and you're compiling it for 32-bit. length is a size_t which is uint in 32-bit environments and ulong in 64-bit. A long/ulong isn't implicitly convertable to int/uint in D. On line 119, either you need to use an explicit cast or you can change the type of curLength to long, ulong, or size_t.

In this case, since you expect curLength to be fairly small (much smaller than an int), I'd just stick a cast in there. Though, in general, changing the type to a size_t is better.

On Friday, 24 August 2012 at 19:32:53 UTC, 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.
>
> I've probably violated every D guideline concerning the use of static,
> pure, nothrow,... but it works perfectly :)
> It does fail to compile on dpaste, I have no idea why. It does compile
> on my machine though...
>
> http://dpaste.dzfl.pl/8a2aef5b
>
> 2012/8/21, Timon Gehr <timon.gehr@gmx.ch>:
>> On 08/21/2012 05:52 PM, maarten van damme wrote:
>>> > On 08/20/2012 11:49 PM, Timon Gehr wrote:> On 08/20/2012 10:43 PM,
>> maarten van damme wrote:
>>>>>
>>>>> Still it comes nowhere near beating timons solution. Is the logic of
>>>>> that documented somewhere because I don't understand it.
>>>>>
>>>>
>>>> Try this:
>>>> http://dpaste.dzfl.pl/23b1b6e2
>>>
>>> Thank you very much, this makes everything more clearer. I'm not very
>>> familiar with binary operators so the comments help out a lot.
>>> Would you mind it if I shamelessly copy your solution of using shorts
>>> to store possibilities in?
>>>
>>
>> Not at all.
>>
>>> I'm also a bit confused. How come the int's you change from a square
>>> passed from squ are stilled referenced to the original array? I
>>> thought it lost that reference as soon as you did any operations (like
>>> concenating) on it?
>>>
>>
>> The used ranges just express patterns of iteration. They replace manual
>> for-loops. The data source has assignable elements, and the relevant
>> range operations in Phobos all propagate this capability to their
>> result.

Your code is 32bitish, while you picked 64bit mode on dpaste.

Here's your code with m32: http://dpaste.dzfl.pl/b4a01f57
Working nice!

Thank you very much.
I changed line 119 to an explicit cast to int and removed an unneeded
cast at line 63.
It now happily compiles with 64bit mode : http://dpaste.dzfl.pl/63666f07.
It's kind off odd though that compiling with -inline seems to slow it
a bit down.

I'm unsure if searching for the field with the least possibilities was a smart move because now I have to carry that "taken" array through all my functions and optimize has to check the whole sudoku instead of a slice. (come to think of it, taken should've been named occupied)

Still, I'm really pleased with the results. I should write a prettyPrint method that prints sudoku's in a prettier format and returns the solution instead of the shorts containing the solutions hidden in bitfields :)

> I'm unsure if searching for the field with the least possibilities was a smart move because now I have to carry that "taken" array through all my functions and optimize has to check the whole sudoku instead of a slice. (come to think of it, taken should've been named occupied)

I take that back, having tried it out, it is more then 3 times slower...