On Wednesday, 15 August 2012 at 20:13:10 UTC, Era Scarecrow wrote:
On Wednesday, 15 August 2012 at 15:39:26 UTC, ixid wrote:
Could you supply your code? Which one are you using as the
hardest? If you're solving the 1400 second one in 12 seconds
that's very impressive, I can't get it below 240
The puzzle unflipped is extra hard as the solution to the first row is
987 654 321. Come to think of it, one could add a new function flip
that mutates the sudoku according to well known rules and maybe
something like unflip for when the sudoku was finnished.
New techniques could certainly be
On Saturday, 25 August 2012 at 13:33:27 UTC, maarten van damme
wrote:
While trying to use Array!bool I noticed this:
import std.container;
void main(){
Array!bool test;
test[0]=false;
}
gives an assertion failure without any information.
Also, why on earth can't I instantiate
maarten van damme:
Ok, I'll try with Array!bool instead of bool.
There is also a BitVector, but it's heap-allocated, so probably
it's not a good idea. A ucent used as bit vector on a 64 bit
system is maybe the best way to implement that :-) But we don't
have ucents yet.
So maybe you have to
struct MaxArray(T, size_t maxLen) {
...
void opAssign(T[] a) {
I forgot ==
struct MaxArray(T, size_t maxLen) {
...
void opAssign(T[] a) pure nothrow {
Bye,
bearophile
And now your backtrack() function too can be nothrow :-)
Bye,
bearophile
Congratulations, you have found a compiler bug. I have found
maybe one hundred of those. Please minimize the code and submit
it to Bugzilla :-)
Oh, but try playing around with static and dynamic arrays. You'll be
able to find plenty more :p
By changing both squareWidth and squareHeight to
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
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
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
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,
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
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
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.
and everythingPossible should also be changed to something ala 2 ^(side) -1
2012/8/25 Timon Gehr timon.g...@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
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.
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
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
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
On Saturday, 25 August 2012 at 00:51:23 UTC, Chris Cain wrote:
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
2012/8/17, Chris Cain clc...@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
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
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:
On Monday, 20 August 2012 at 20:43:54 UTC, maarten van damme
wrote:
Yes, but these techniques have a drawback : they are not
guaranteed to find solutions yet they are guaranteed to
increase the time a run takes.
The extra time it takes via a planned route rather than brute
forcing is well
On Monday, 20 August 2012 at 20:43:54 UTC, maarten van damme
wrote:
And Vera, why are you using exceptions instead of return
values? I think it's slowing your solver down considerably.
Wow... Just Wow...
Optimized I had the code at 5 seconds in my recently updated
format, however now it
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
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
Great, i tried to get rid of the dynamic array possibilities by
representing it using a static array of bools. This approach made it 4
times faster :)
When i have a solid wifi connection I'm going to install dmd 2.60 to
compile timon's code. In the meantime I've started beautifying the source
so
my code is located at http://dpaste.dzfl.pl/93cd5f45
2012/8/19, maarten van damme maartenvd1...@gmail.com:
Great, i tried to get rid of the dynamic array possibilities by
representing it using a static array of bools. This approach made it 4
times faster :)
When i have a solid wifi
On Sunday, 19 August 2012 at 09:39:53 UTC, maarten van damme
wrote:
Great, I tried to get rid of the dynamic array possibilities
by representing it using a static array of bools. This approach
made it 4 times faster :)
When I have a solid wifi connection I'm going to install dmd
2.60 to
The infinite loop was my mistake. I was looking at your outer while loop
but because you use exceptions instead of return values it indeed throws an
exception, my bad :)
By replacing ref by const ref my program slowed down (looked over a period
of 10_000 runs). Not considerably but noticeable.
On Sunday, 19 August 2012 at 21:24:26 UTC, maarten van damme
wrote:
The infinite loop was my mistake. I was looking at your outer
while loop but because you use exceptions instead of return
values it indeed throws an exception, my bad :)
I have a revised version that only does 2 calls for
I'm using a static array.
I'm hesitating though if I should store possibilities in a precalculated
array or calculate them in-place. If i precalculate the possibilities i'd
have to copy them over and over so i don't know if it's smart.
Going even further I could even store a filled-in value as
On Monday, 20 August 2012 at 00:13:41 UTC, maarten van damme
wrote:
I'm using a static array.
Good good..
I'm hesitating though if I should store possibilities in a
precalculated array or calculate them in-place. If I
precalculate the possibilities I'd have to copy them over and
over so I
Depends. Do you plan on doing more than brute force? Having it
bulk copy them may not be that bad if it's all in one place, and
if you do it like that you have all the combinations that carry
forward to the next level and if you back out it undoes them all
automatically.
No, I think doing
On Monday, 20 August 2012 at 01:29:06 UTC, maarten van damme
wrote:
Depends. Do you plan on doing more than brute force? Having it
bulk copy them may not be that bad if it's all in one place,
and if you do it like that you have all the combinations that
carry forward to the next level and if
I've now ran in something odd. Using a slight variant from my program on
dpaste (can't upload modified version atm but changes are minimal) it takes
0.6 seconds to solve the hard puzzle the python version took 180 seconds
for. Yet on the last puzzle, the impossible one, python takes 1800 seconds
On 08/16/2012 09:52 PM, maarten van damme wrote:
I've now ran in something odd. Using a slight variant from my program on
dpaste (can't upload modified version atm but changes are minimal) it
takes 0.6 seconds to solve the hard puzzle the python version took 180
seconds for.
This is because
This is because your specific solution is slow.
Mine takes 20ms on the 'hard' puzzle and ~13s on the impossible one.
(~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline
-noboundscheck.)
There is a constant factor between those two solutions.
I've compiled it using dmd on my
On 08/16/2012 11:51 PM, maarten van damme wrote:
This is because your specific solution is slow.
Mine takes 20ms on the 'hard' puzzle and ~13s on the impossible one.
(~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline
-noboundscheck.)
There is a constant factor between those
great, going to play around with it tomorrow.
Caching the possibilities is going to look really ugly but you're
right, it's going to give quiet a boost in performance.
I'm also going to format your source code a bit more and see if I can
follow it's logic as it seems to be way more efficient.
On Thursday, 16 August 2012 at 23:13:56 UTC, maarten van damme
wrote:
great, going to play around with it tomorrow.
Caching the possibilities is going to look really ugly but
you're
right, it's going to give quiet a boost in performance.
I'm also going to format your source code a bit more
On 08/17/2012 01:13 AM, maarten van damme wrote:
great, going to play around with it tomorrow.
Caching the possibilities is going to look really ugly but you're
right, it's going to give quiet a boost in performance.
I'm also going to format your source code a bit more and see if I can
follow
On Tuesday, 14 August 2012 at 22:31:16 UTC, bearophile wrote:
http://www.reddit.com/r/cpp/comments/y6gwk/norvigs_python_sudoku_solver_ported_to_c11/
http://nonchalantlytyped.net/blog/2012/08/13/sudoku-solver-in-c11/
His C++11 port is 316 lines long:
https://gist.github.com/3345676
How many
On 08/15/2012 03:01 AM, Era Scarecrow wrote:
Not Golfed? I don't recognize that term. I don't see the python source
off hand, but I don't understand python anyways.
It refers to code golf, where you try to solve a problem with the
smallest program possible (one-letter variable names, no
On Tuesday, 14 August 2012 at 22:31:16 UTC, bearophile wrote:
http://www.reddit.com/r/cpp/comments/y6gwk/norvigs_python_sudoku_solver_ported_to_c11/
http://nonchalantlytyped.net/blog/2012/08/13/sudoku-solver-in-c11/
His C++11 port is 316 lines long:
https://gist.github.com/3345676
How many
Era Scarecrow:
I don't see the python source off hand,
The original Python code:
http://norvig.com/sudopy.shtml
Bye,
bearophile
Could you supply your code? Which one are you using as the
hardest? If you're solving the 1400 second one in 12 seconds
that's very impressive, I can't get it below 240 seconds.
On Wednesday, 15 August 2012 at 15:39:26 UTC, ixid wrote:
Could you supply your code? Which one are you using as the
hardest? If you're solving the 1400 second one in 12 seconds
that's very impressive, I can't get it below 240 seconds.
1400 seconds? Well my CPU is a quad-core 3.2Ghz, but
On Wednesday, 15 August 2012 at 15:39:26 UTC, ixid wrote:
Could you supply your code? Which one are you using as the
hardest? If you're solving the 1400 second one in 12 seconds
that's very impressive, I can't get it below 240 seconds.
Expanded to 225 lines after comments and refactoring for
On Wednesday, August 15, 2012 21:14:07 Era Scarecrow wrote:
I have made a C version a while back that solves any sudoku
puzzle in 1/8th of a second. The code for that though was
considerably longer and involved several forms of pattern
matching and detecting how to solve the puzzle before it
On Wednesday, 15 August 2012 at 20:28:19 UTC, Jonathan M Davis
wrote:
Brute force is so fast that there's no really any point in
trying to solve it any other way except for the challenge of
doing so. I answered a question on this using D at
codegolf.stackexchange.com a while back:
On Wednesday, 15 August 2012 at 20:13:10 UTC, Era Scarecrow wrote:
On Wednesday, 15 August 2012 at 15:39:26 UTC, ixid wrote:
Could you supply your code? Which one are you using as the
hardest? If you're solving the 1400 second one in 12 seconds
that's very impressive, I can't get it below 240
Jonathan M Davis:
and the code is lightning fast. It would probably have to be
tweaked to match
whatever Bearophile's code does though as far is input goes (I
haven't looked
at the code that he linked to). It also makes no attempt at
being compact
(e.g. it actually checks the command line
Jonathan M Davis:
It would probably have to be tweaked to match
whatever Bearophile's code does though as far is input goes (I
haven't looked at the code that he linked to).
And the original Python code is not mine, it's from the AI
researcher Peter Norvig :-)
Bye,
bearophile
On 08/15/2012 12:31 AM, bearophile wrote:
http://www.reddit.com/r/cpp/comments/y6gwk/norvigs_python_sudoku_solver_ported_to_c11/
http://nonchalantlytyped.net/blog/2012/08/13/sudoku-solver-in-c11/
His C++11 port is 316 lines long:
https://gist.github.com/3345676
How many lines for a (not
On Wednesday, 15 August 2012 at 22:38:58 UTC, ixid wrote:
How many solutions do you find for that one?
Don't know, it actually just stops after finding the first one.
Modifying it to give all possible outputs wouldn't be too hard...
So far having it running it's found over 23k+ combinations
On Thursday, 16 August 2012 at 01:05:20 UTC, Era Scarecrow wrote:
So far having it running it's found over 23k+ combinations
after about 3 minutes.
Unless I introduced a bug... Now I'll have to speed it up to
make sure and won't take an afternoon to calculate.
This is my attempt at a D solver, it's a pretty direct
translation of a C++ version I wrote but it's a lot slower in D,
around 1/4 the speed sadly, 2x because of the compiler I think
and 2x because in C++ I can use proper bitfields which seem to
give another 2x speed up (halving the size of
Hmm, sorry odd things have happened to the formatting. Visual D's
spacing doesn't seem to work very well outside of itself.
solving sudoku's well too : http://dpaste.dzfl.pl/903e34b5
I have one question though, how can you make it find all possible solutions?
2012/8/16, Era Scarecrow rtcv...@yahoo.com:
On Thursday, 16 August 2012 at 01:05:20 UTC, Era Scarecrow wrote:
So far having it running it's found over 23k+
http://www.reddit.com/r/cpp/comments/y6gwk/norvigs_python_sudoku_solver_ported_to_c11/
http://nonchalantlytyped.net/blog/2012/08/13/sudoku-solver-in-c11/
His C++11 port is 316 lines long:
https://gist.github.com/3345676
How many lines for a (not golfed) D translation of the original
Python
63 matches
Mail list logo
