Intel® Software Network

Another shorter output format will be to output an MD5 hash of the sorted board results

My 11x11 result file is 41MB long but its hash is only 32 characters:
49f9a698f7ae3acc3ad62f5f05b0f372

I use this hash to test non regression of my code. But writing MB of data fast is part of the exercise.

At the moment, my algorithm is not fast enough, the writing represents 0.1 percent of the total runtime. So, no need to use a shorter format.

The proposed grid format is easier to view and helpful to debug your code.

Could you confirm that you obtain the same results as me ?

Thanks.

David.

Sorry, I am still writing the code, even have not started compiling or debugging.

And, as some released result demostrate, the number of solution explodes, so does the time consumption to explore all the possible solution. I wonder whether the judges will use some N as large as 100 for tests. [actually I think any N>=20 will take some unacceptable time to get a full answer, even with the best optimised parallel algorithm].

I think that changing data format to this one would be a good idea, although it would be a bit more difficult to write it efficiently on disk.

It was expected that the I/O would again be a very small fraction of the execution time, so the given output format was formulated to make judging a little easier. Upon further consideration, the output format proposed in the this thread should be easily convertible to the stated output format.  Even more compact would be putting each piece on a consecutive lines with a blank between each board, like:

Q: (4 8) (5 6) (6 3) (7 7) (8 2)
N: (1 4) (2 1) (2 4) (2 5) (3 1)
 
Q: (3 8) (5 2) (6 7) (7 3) (8 6)
N: (1 1) (1 4) (1 5) (2 1) (2 4)

The MD5 hash is getting a bit too condensed.  If a code doesn't get the expected hash, we still need to go in and look to see which boards are incorrect.  (Of course, you are all excellent coders and won't get the wrong answers, so this point should be moot, right? ) 

What if the output format were made optional (either the original version or some condensed format)? In order to do this, there would be a requirement to explain how the condensed form maps into the original format (and it might require an additional utility be coded and included in the entry to take your output format and produce the original board output).  Would there be any objections to amending the contest problem with something like this?

Unanimous approval by the judges will be required before such a change would be made official.  It is early enough in the month that allowing such an alternative output format shouldn't adversely impact anyone's work to this point. (There may be some contestants getting their code done early for a skiing trip to the Alps, so such a change to the problem would need to be made optional. )

--clay

Hello Clay,

madcpbreshe:

It was expected that the I/O would again be a very small fraction of the execution time,

My timing with I/O :
8: 0.0067
9: 0.053
10: 0.346
11: 7.389
12: 51.316

for N>10 we got lot of solutions so the IO is important for the 11 and 12 cases.

timing without IO
8: 0.0063
9: 0.052993
10: 0.343341
11: 6.76894
12: 50.2979

This code is serial so the 11 case will be problematic when going parallel. And more if someone another order of magnitude speedup.

madcpbreshe:

There may be some contestants getting their code done early for a skiing trip to the Alps, so such a change to the problem would need to be made optional.

PS: no snow yet in the Alps but good wind, less tourist -> good conditions for windsurfing :-)

madcpbreshe:

Q: (4 8) (5 6) (6 3) (7 7) (8 2)
N: (1 4) (2 1) (2 4) (2 5) (3 1)
 
Q: (3 8) (5 2) (6 7) (7 3) (8 6)
N: (1 1) (1 4) (1 5) (2 1) (2 4)

Take 11x11 example (7 queens and knights), outputting a board with the original format is
11 * 12 + 1 = 133 characters

The proposed format takes at least 6 characters per element
(7+7) * 6 = 84

But personal condensed format with an utility to uncondense will be a good idea.

David.

hi all

please tell me the standard out put format and points format(with bonus points) also.......... and is it possible to resubmit the code???

 

pradiptaghosh:

hi all

please tell me the standard out put format and points format(with bonus points) also.......... and is it possible to resubmit the code???

 

First of all, welcome to this contest!
I guess the output format is unchanged until the judge allows the alternative format proposed in this thread. Clay would have the final word on this.
As for the points format (you mean scoring criteria, right?), you can find these information in this forum. Judges post the criteria for each month after they announce the winner.
You are free to resubmit the code before the deadline.

It seems to me that it would be pretty easy to add a command line switch that would produce alternate formats, that way people could test using whatever pleases them and the judges could still get the "default" format that is easiest for them to check.

DweeberlyLoom:

It seems to me that it would be pretty easy to add a command line switch that would produce alternate formats, that way people could test using whatever pleases them and the judges could still get the "default" format that is easiest for them to check.

But someone could use a different execution path when using the command line switch and the judge then would not be able that the solving timing is the same as the one with the "default" output format.

So timing with the custom output format and having an external tool to convert it to "default" is a good alternative.

But once again, I/O (relatively) time is small except for the 11x11 case.

Huh!?

I was suggesting that everyone support the requested format for judging (so everything is judged on the same basis).  However, if folks want to use a different format when testing, it would be easy for each of us to support that we prefer with a simple command line switch.

dgeld:

But someone could use a different execution path when using the command line switch and the judge then would not be able that the solving timing is the same as the one with the "default" output format. So timing with the custom output format and having an external tool to convert it to "default" is a good alternative. But once again, I/O (relatively) time is small except for the 11x11 case.

I think that it is worth to require that the program should behave identically with both output formats.

I think it would be useful to have a format of that has each board on a separate line. It could be like the sample without the newlines for each row, or it could be something like FEN: http://en.wikipedia.org/wiki/Board_representation_(chess)

Mark

Use of an alternate format is approved.  Details should be in a modified version of the problem description.  We had also put a copy of the details inthe forum, under a new heading.  But I don't see it here.  I'll repost that tomorrow.

--clay

why do we need the brackets? commas or other single interpunction will separate the pairs well.

madcpbreshe:

It was expected that the I/O would again be a very small fraction of the execution time, so the given output format was formulated to make judging a little easier. Upon further consideration, the output format proposed in the this thread should be easily convertible to the stated output format.  Even more compact would be putting each piece on a consecutive lines with a blank between each board, like:

Q: (4 8) (5 6) (6 3) (7 7) (8 2)
N: (1 4) (2 1) (2 4) (2 5) (3 1)
 
Q: (3 8) (5 2) (6 7) (7 3) (8 6)
N: (1 1) (1 4) (1 5) (2 1) (2 4)

The MD5 hash is getting a bit too condensed.  If a code doesn't get the expected hash, we still need to go in and look to see which boards are incorrect.  (Of course, you are all excellent coders and won't get the wrong answers, so this point should be moot, right? ) 

What if the output format were made optional (either the original version or some condensed format)? In order to do this, there would be a requirement to explain how the condensed form maps into the original format (and it might require an additional utility be coded and included in the entry to take your output format and produce the original board output).  Would there be any objections to amending the contest problem with something like this?

Unanimous approval by the judges will be required before such a change would be made official.  It is early enough in the month that allowing such an alternative output format shouldn't adversely impact anyone's work to this point. (There may be some contestants getting their code done early for a skiing trip to the Alps, so such a change to the problem would need to be made optional. )

--clay

timminn:

why do we need the brackets? commas or other single interpunction will separate the pairs well.

You don't need brackets or commas or any other punctuation.  The format  and separator character is up to you.  I was just giving an example. 

In fact, during my shower last night, I had an idea about using something similar to a dictionary-based compression algorithm.  For the two boards in my previous post, I would have printed them as:

3N4N2NN3N14Q5Q4Q11Q2Q6
N2NN3N2N11Q9Q12Q3Q10Q2
 

Place the rows of the board one after the other as a 1-D array.  Count the blank squares between pieces and write down the number.  Pieces are represented by their single letter. I guess I could have used a '.' after each number to make the number a multiplier.

This compression scheme would be so much easier to grade with a sort and a diff.  We might have to write our own utility to convert the board outputs into this format. (I seem to have quite a few good ideas in the shower.  Maybe if I took more I'd be smarter, or least seem that way.)

--clay

Hello Clay,

guess what, I used a format similar to this one in my yesterday's submission ... I called it RLE (Run Length Encoding).


Q....

..Q..

.....

.....

.N.N.


which then gives
Q6QDN1N1

For simpler implementation, I use only one hexadecimal number to encode spaces and then sums them up.

The one liner format is also easy to grade with sort and diff.

I have written an out2dat perl script (posted in another thread) to transform/sort a QNboardxx.out file to a one liner file which I use in my test suite.

David.