visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
304 experts, 1182 registered users, 1626 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


The DDRK link is back online.
We got a one week service interruption, sorry.
(23-30/01/2010)

Languages :: Pascal :: Need faster solution
By: StillUnAware U.S.A.  Date: 07/05/2003 00:00:00  English  Points: 100 Status: Answered
Quality : Excellent
I have decided to check is it possible to divide any rectangle to the squares, which are all of different sizes. As an example I got this one: Dimmension are: DimX := 33, DimY := 32. And the result is: it is possible to divide the rectangle to 9 squares, and their dimmensions are as follows : 9, 10, 14, 8, 1, 7, 4, 18, 15.
My program already uses dinamic memory, but still works very slowly. My algorithm is the worst :), I know that, and maybe You can help me to optimize the code. I have no more ideas left.
Thank You.
Andrius.
{====================== My program =============================}

Program Rectangle_splitting_to_squares; { Search engine: ascending, }
Uses Crt; { using dinamic memory }
Type SquareLine = array [1..MaxInt div 2] of integer;
rec = ^number;
number = record
num, Count :integer;
back, next :rec;
end;
Var DimX, DimY :integer;
SquareDim :SquareLine;
HowMany :integer;
ii :longint;
jj, tmp :integer;
Sheet :rec;
StartAddress :pointer;

Procedure InRec(var rcd :rec; nm, Counter :integer);
Var rcdi :rec;
Begin
if rcd <> nil then While rcd^.next <> nil do rcd := rcd^.next;
New(rcdi);
rcdi^.next := nil;
rcdi^.num := nm;
rcdi^.Count := Counter;
rcdi^.back := rcd;
rcd^.next := rcdi;
rcd := rcdi;
end;

Procedure Split( var Depth :integer; var SqDim :SquareLine; var rc :rec;
m, n :integer; SA :pointer );
Var i, j, b, Width, z :integer;
Start :pointer;
Cancel :boolean;
Begin
Cancel := false;
write( 'Depth: ', Depth:3, ' Û ' );
for i := 1 to Depth do begin write( SqDim, ' ' ); end;
writeln(' ');
gotoXY( 1, wherey );
rc := SA;
Repeat
if rc^.num = 0 then
Begin
Start := rc;
Width := 1;
while ( rc^.next^.num = 0 ) and ( rc <> nil ) do
begin
rc := rc^.next;
inc( width );
end;
b := 0;
rc := Start;
repeat
b := b + m;
until b > rc^.Count;
b := b - rc^.Count;
if b < width then width := b;
b := n - rc^.Count div m;
if b < width then width := b;
Cancel := true;
end;
if rc = nil then
Begin
writeln( 'This rectangle was splitted into ' , Depth, ' squares' );
write( 'Depth: ', Depth, ' . Squares: ');
for i := 1 to Depth do write( SqDim, ' ' );
writeln;
halt;
end;
rc := rc^.next;
until Cancel;
for i := 1 to Width do
Begin
Cancel := false;
for j := 1 to Depth do if ( SqDim[j] = i ) then Cancel := true;
if not Cancel then
Begin
rc := Start;
for b := 1 to i do
Begin
for j := 1 to i do
begin
rc^.num := i;
rc := rc^.next;
end;
if b < i then for z := 1 to (m - i) do rc := rc^.next;
end;
rc := Start;
inc( Depth );
SqDim[ Depth ] := i;
Split( Depth, SqDim, rc, m, n, SA );
end;
end;
rc := SA;
repeat
if rc^.num = SqDim[ Depth ] then
Break;
rc := rc^.next;
until rc = nil;
for b := 1 to SqDim[Depth] do
Begin
for j := 1 to SqDim[Depth] do
Begin
rc^.num := 0;
rc := rc^.next;
end;
for z := 1 to (m - SqDim[Depth]) do if rc <> nil then rc := rc^.next;
end;
SqDim[ Depth ] := 0;
dec( Depth );
end;

Begin
Write ('Input dimensions for rectangle: ');
Readln( DimX, DimY );
HowMany := 0;
tmp := 0;
for ii := 0 to DimX*DimY - 1 do
InRec( Sheet, 0, ii );
While Sheet^.back <> nil do Sheet := Sheet^.back;
StartAddress := Sheet;
write('Depth: ');
Split( HowMany, SquareDim, Sheet, DimX, DimY, StartAddress );
writeln;
end.

{================================== End of My program ============================}
By: StillUnAware Date: 07/05/2003 22:20:00 English  Type : Comment
I think I should tell what my program does.

1) initializes the two direction list with 0, the number of
varriables in memory is DimX*DimY (length and height of the rectangle), Sheet^.num saves the squares dimension which is graphicaly in the field (m*n), Sheet^.Count shows place of the element.
2) HowMany (Depth) counts how many squares is right now.
3) procedure Split recursively tries to put all rectangles in a row from left to rigth and from top to bottom.

Maybe there is other algorithm to solve the problem.
For example from what size of square to start the recursion.
I have some ideas: squares of sizes 1 and 2 will never be near the "walls" of a rectangle.
Also square can "touch" only two other squares with its one side... ( but this is prety hard to bring to life :)
So in conclusion > I need your adwise ( better algo the most ).

StillUnAware - Andrius
By: VGR Date: 07/05/2003 22:58:00 English  Type : Comment
At least THAT's challenging :D
By: StillUnAware Date: 07/05/2003 23:56:00 English  Type : Comment
I think so.
Do You have any ideas? :)
By: VGR Date: 08/05/2003 00:50:00 English  Type : Comment
yes. a lot. But I don't have a lot of time :/
perhaps later this evening.
By: Okey Date: 08/05/2003 00:57:00 English  Type : Comment
First Idea :
Your dynamic engine is good,
but it is a Heap thing and
so a little bit slower then direct DATA access!
It seems nessecary,
but nothing...

I think your code is well enough to work?, and
you should only cut your Routines to Screensize
(25/50 Lines)

Remember Pascal has been invented to make programming code
more understandable like talking to someone;
so don't be lazy and write expressions completely and you'll be able to read down your proggy and understand it in one ``Shoot´´!

Do you know assembler?

There are all possibilities hidden to make your proggy faster from optimizing Data up to optimizing Code!

Appropos Style :

Good style starts with readabillity of source,
avoids spaghetti-code (Label & Goto)
and avoids recursion as far as possible because it leads to many problems,
futher ...

How shall I explain you here what I learned my Lifetime?
Try this hints and tell me what you want to avoid and why so that we can terll you howto.
I'm sure People won't tell you all their secrets about good Programming technics!
By: Okey Date: 08/05/2003 01:02:00 English  Type : Comment
Sorry I don't understand !

What if Your Rectangle is small like

(2X1; 2x2 or 2X3)

This would always lead to multiple Squares of same size,
and in biger rectangles as well, too!
By: VGR Date: 08/05/2003 01:04:00 English  Type : Comment
okey : there's no label nor goto in his code
and I like recursion if it fits on a 64KB stack ;-)
By: Okey Date: 08/05/2003 19:41:00 English  Type : Answer
Yeah if it fits,
but thats realy not often and
I didn't knew what to write to StillUnAware
By: cuuu Date: 08/05/2003 19:59:00 English  Type : Comment
Hi,
maybe you should use this approach -
recursively generate lengths of squares that
are worth checking - generate combinations of
sqare side lengths that squared give DimX*DimY.

In other words, generate combinations of 1..max(dimx,dimy),
and check whether square sums of these combinations equals
to dimx*dimy. if so, then there is a point to check these
combinations.

Generate those combinations recursively,
say, dimx*dimy=100=total, then your procedure will look like
this:

Var res:array[1..max] of integer; {here we store values
we have chosen so far}
Procedure Generate(toSpare,lastChosen:longint; level:integer);
Var i:longint;
Begin
if tospare=0 then CheckField(level)
else begin
if tospare>lastchosen then
for i:=lastchosen+1 to toSpare do begin
res[level]:=i;
generate(toSpare-i,i,Succ(level));
End;
End;
End;

You will launch it like this:
Generate(100,0,1)
100 means - we have 100 cells to spare,
0 - last chosen element "was" 0 in order to start with 1
1 - start with level 1, we need this argument to know
where to put numbers in the global array

Unimplemented remains Procedure ChekckField -
its job is to try to fit squares
with sizes given in array's res[] 1 .. "level" elements.
this procedure also will be most probably recursive.

Such approach should be far better than full overlook;
hope this helps,
cuuu
By: StillUnAware Date: 08/05/2003 23:00:00 English  Type : Comment
Thank you for your suggestions. I promise I'll try them all.

I really liked the cuuu idea. It may speed up the program pretty well.

All squares in a rectangle must be of different sizes (Okey)

I heard that this problem is solved by using graph theory.
But where to use it, I have no idea. Also I heard that for this exercise are used Kirchhoff's and Ohm's laws. This rectangle is like a conductor, and the squares in it divides the charge(load) and after that adds it again (for example starting from left top corner and ending at right bottom one). Also all this is a mitique for me.

Sorry, I didn't write anything. I am a student, but don't have an InterNet at home, so I use the public computer.
I'll try to be here every day. I am trully interested in this exercise now.

Wish You luck. (If You're lucky, I'm lucky too ;)
By: VGR Date: 08/05/2003 23:20:00 English  Type : Assist
some optimization remarks :

Type SquareLine = array [1..MaxInt div 2] of integer;
>> do you really need so much (static,non-dynamic) memory ?

while ( rc^.next^.num = 0 ) and ( rc <> nil ) do
>> turn shortcircuit boolean evaluation ON or this is supposed to fail as soon as rc is Nil (because then rc^ is undefined and the left operand can't be evaluated). Inverse also the two operands of the AND so that rc=Nil shortcircuits the boolean eval. That's {$B+}

Cancel := false;
for j := 1 to Depth do if ( SqDim[j] = i ) then Cancel := true;
if not Cancel then
>> this can be optimized this way, again with boolean eval optimized (shortcircuited) :
NotCancel:=True;
j:=1; While NotCancel AND j<=Depth Do Begin NotCancel:=SqDim[j]=i; Inc(j); End;
if NotCancel Then


b := 0;
rc := Start;
repeat
b := b + m;
until b > rc^.Count;
>> optimized by stating :
rc := Start;
b := ((rc^.Count DIV m)+1)*m;



rc := SA;
repeat
if rc^.num = SqDim[ Depth ] then
Break;
rc := rc^.next;
until rc = nil;
>> ugly. Should be (still with {$B+} ) :
rc := SA;
while (rc<>Nil)AND(rc^.num <> SqDim[ Depth ]) Do rc := rc^.next;



for z := 1 to (m - SqDim[Depth]) do if rc <> nil then rc := rc^.next;
>> this loop executes (m - SqDim[Depth]) times whatever the condition is ; it should be executed AT MOST that number of times, and at MOST until rc=Nil is encountered. Rewrite it with a while as above



for b := 1 to SqDim[Depth] do
Begin
for j := 1 to SqDim[Depth] do
Begin
rc^.num := 0;
rc := rc^.next;
end;
for z := 1 to (m - SqDim[Depth]) do if rc <> nil then rc := rc^.next;
end;
>> what's the point in those two outer loops ?!??
b is not used inside the loop
j is not used either
so basically you do SqDim[Depth]*SqDim[Depth] times the same thing on the same starting rc (potentially Nil as soon as second outer loop begins, BTW) and I'm not sure at all this is needed...

I think this should be rethinkered and redesigned, IMHO
By: StillUnAware Date: 09/05/2003 02:48:00 English  Type : Comment
Now I even know the name of this exercise. It is called Simple Squared Square, or Squared Rectangle.
But now I think, I have to look for a graph theory all about this, it might be the only solution.

Also I decided to divide not rectangle but square into square, it doesn't change a lot, but is even harder to solve. I looked over internet about this and found that the recent exercise is called Compound Perfect Square.
There are some example solution, but not algorithms, maybe any of you know where to look for such a thing.
By: cuuu Date: 11/05/2003 04:37:00 English  Type : Assist
Square problem cannot be harder to solve than rectangle problem, because square is just a special case of rectangle
By: OpConsole Date: 08/09/2003 13:02:00 English  Type : Comment
StillUnAware:
This old question needs to be finalized -- accept an answer, split points, or get a refund.
By: StillUnAware Date: 09/09/2003 20:50:00 English  Type : Comment
Hi, if you still remember me. I decided to split points like this:

VGR :40
cuuu :40
OKey :20

I hope that would be fear.

BTW. The program itself is working, and I thank you all, but the main reason I've posted here was not the optimization of a routine, but the algorithm. And still thanks.

StillUnAware
By: VGR Date: 09/09/2003 21:12:00 English  Type : Comment
thanks

Do register to be able to answer

 Add This Article To:
 del.icio.usDel.icio.us  diggDigg  googleGoogle  spurlSpurl
 blinkBlink  wongWong  simpySimpy  yahooY! MyWeb 
EContact
browser fav
page generated in 50.705190 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page