was: A little programming chalenge: My solution, the principle



#5

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


#6

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


#7

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

#8

Hi Dave,

How is your progress?

Patrice


Possibly Related Threads...
Thread Author Replies Views Last Post
  [HP-PIRME] BUG Pretty Print, Solution: abs => |...|, ABS => ||...|| CompSystems 2 329 12-13-2013, 09:36 AM
Last Post: CompSystems
  [OT] engineering student chalenge cyrille de Brébisson 1 218 11-25-2013, 10:06 PM
Last Post: FORTIN Pascal
  [HP-Prime xCAS] Arrays: Programming Commands (solution to the ambiguity) CompSystems 6 392 08-30-2013, 06:32 PM
Last Post: CompSystems
  HP-Prime: Solution to ambiguity with [ ... ] & another BUGs CompSystems 12 511 08-28-2013, 08:48 AM
Last Post: CompSystems
  Advanced User's Manual and solution to the ambiguity of data types [HP-Prime xCAS] CompSystems 15 802 08-20-2013, 03:37 PM
Last Post: Thomas Klemm
  HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution Jeff O. 32 1,312 10-12-2012, 01:41 AM
Last Post: Paul Dale
  41CL: Linux/Mac connection solution (soon) Geir Isene 28 958 06-10-2012, 01:21 PM
Last Post: Ángel Martin
  71B vs 41CL The HP "Certainty Principle" John W Kercheval 12 420 05-06-2012, 09:47 AM
Last Post: John W Kercheval
  [WP34S] Cheap Overlay Solution Courtesy of Kinkos Les Wright 5 242 11-28-2011, 02:38 PM
Last Post: Walter B
  The solution to the quartic equation on the HP50g, revisited Crawl 0 94 10-12-2011, 07:33 PM
Last Post: Crawl

Forum Jump: