The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

was: A little programming chalenge: My solution, the principle
Message #1 Posted by Patrice on 16 Oct 2010, 8:25 p.m.

Hi all,

Contrary to what I expected, I did not present my solution at HHC 2010 because the schedule was too tight. Instead, I presented it after the conference in short comity.

As said previously, one sub-problem is to know how many cells can be filled for the current shape.

Said otherwise, the whole thing is about having a tool that tells you that you canít reach the maximum as soon as possible, in order to abort useless search as soon as possible.

My solution is to build a table which answers the 2 problems. When the table is filled, it tells the maximum number of cells that can be filled for the current shape.

I build the table cell by cell, starting by the last cell and going backward, so the part of the table already built is useful to build itself for the previous cell. And the process is repeated until the table is full.

I build the table by asking a question: while adding 1 more cell, can I find a filling order which allow 1 more cell filled?

Do you need more details?

Is it efficient? Yes it is! A square of 9*9 is filled in less than a second (actually it is closer to 0.1 second)

Patrice

      
Re: was: A little programming chalenge: My solution, the principle
Message #2 Posted by David Hayden on 21 Oct 2010, 9:15 a.m.,
in response to message #1 by Patrice

Hi Patrice,

Yes, more details please. I have tried to fill in the details based on what you've said and it seems to me to be more complicated than you imply. I'm probably missing something. Perhaps if you give an example.

Thanks, Dave

            
Re: was: A little programming chalenge: My solution, the principle
Message #3 Posted by Patrice on 21 Oct 2010, 3:08 p.m.,
in response to message #2 by David Hayden

Hi all,

The following is to be saved as a csv file and then opened in excel. This sample data is from the filling of a square of 9*9.

maxx;maxy;topx;topy;botx;boty;realx;realy
0;81;0;0;0;0;0;0
81;0;0;1;1;0;1;0
;;0;2;1;1;1;1
;;0;3;1;2;1;2
;;1;3;1;3;1;3
;;1;4;2;3;2;3
;;1;5;2;4;2;4
;;1;6;2;5;2;5
;;2;6;3;5;2;6
;;2;7;3;6;3;6
;;2;8;4;6;3;7
;;2;9;4;7;3;8
;;2;10;4;8;4;8
;;3;10;4;9;4;9
;;3;11;5;9;4;10
;;3;12;5;10;4;11
;;3;13;5;11;5;11
;;4;13;5;12;5;12
;;4;14;6;12;5;13
;;4;15;6;13;5;14
;;4;16;7;13;6;14
;;4;17;7;14;6;15
;;5;17;7;15;6;16
;;5;18;8;15;6;17
;;5;19;9;15;7;17
;;5;20;9;16;7;18
;;6;20;9;17;8;18
;;6;21;9;18;8;19
;;7;21;10;18;8;20
;;7;22;10;19;8;21
;;7;23;10;20;9;21
;;7;24;10;21;10;21
;;8;24;11;21;10;22
;;8;25;11;22;11;22
;;9;25;11;23;11;23
;;9;26;11;24;11;24
;;10;26;12;24;11;25
;;11;26;12;25;12;25
;;11;27;12;26;12;26
;;11;28;13;26;12;27
;;12;28;13;27;12;28
;;12;29;13;28;13;28
;;12;30;14;28;13;29
;;13;30;14;29;13;30
;;13;31;14;30;13;31
;;13;32;15;30;14;31
;;14;32;16;30;14;32
;;14;33;16;31;14;33
;;14;34;17;31;14;34
;;14;35;17;32;15;34
;;15;35;18;32;15;35
;;15;36;18;33;16;35
;;15;37;18;34;17;35
;;15;38;18;35;17;36
;;16;38;19;35;17;37
;;16;39;19;36;17;38
;;16;40;20;36;18;38
;;16;41;20;37;18;39
;;17;41;20;38;19;39
;;18;41;20;39;19;40
;;18;42;21;39;19;41
;;18;43;21;40;19;42
;;19;43;21;41;20;42
;;19;44;21;42;20;43
;;20;44;21;43;20;44
;;20;45;22;43;20;45
;;20;46;22;44;21;45
;;20;47;22;45;21;46
;;21;47;22;46;21;47
;;21;48;23;46;21;48
;;21;49;23;47;22;48
;;21;50;23;48;22;49
;;22;50;23;49;22;50
;;22;51;23;50;23;50
;;23;51;24;50;23;51
;;23;52;24;51;23;52
;;23;53;24;52;23;53
;;24;53;24;53;24;53
;;24;54;25;53;24;54
;;24;55;25;54;24;55
;;24;56;25;55;24;56
;;25;56;25;56;25;56

It contains 4 pairs of columns, each pair is the data for a serie in a graphic, the type of graphic is cloud of points, choose the sub type with line between points.

The principle of the graphic is to move up every time you fill a cell, and move left every time a cell is empty.

The max curve: shows the ending point of a filling depending on how many cells are filled.

The top curve: each point shows how many filled cells can be fitted in the beginning of the shape. It is not possible to preform better than the max curve without breaking the rules. Each point says for the x fist cells, you can fill y cells without breaking the rules.

The bot curve: is the top curve rotated a half turn.

The real curve: is the only path leading to the only filling with the maximum score.

All the trick is the bot curve, for every point, it says: in the last x cells, you can fill y cells to the maximum. if ever your current path goes right to this curve, you will never be able to reach the maximum, you can abort the search and backtrack.

How does it work ? simple! when you begin the fill the shape or a part, you perform better than the bot curve, just count the difference between your path and the curve, if negative, you are on the right of the bot curve.

Every time you check a cell in the shape, you look at the corresponding cell in your table.
if you can fill the cell and the table says true, the path and curve are parallel.
if you can not fill the cell and the table says false, the path and curve are parallel.
if you can fill the cell and the table says false, you gain 1 spare filled cell.
if you can not fill the cell and the table says true, you loose 1 spare filled cell.
as long as the number of spare cells in not negative, you can continue the search.

The main search program is a binary tree explorer deep first, the alternatives are a cell filled or empty. what is not standard is the code to keep track of the spare cells.

Whishing this helps

For more details, just tell which part is not clear.

Patrice

            
Re: was: A little programming chalenge: My solution, the principle
Message #4 Posted by Patrice on 25 Oct 2010, 1:30 p.m.,
in response to message #2 by David Hayden

Hi Dave,

How is your progress?

Patrice


[ Return to Index | Top of Index ]

Go back to the main exhibit hall