7
\$\begingroup\$

I solved a problem which you can read about here, but it gives me "time limit exceeded" even though it runs in 4 seconds. I really don't understand why.

I don't think my code can be any simpler, basically it has as many functions as there are solutions I think. At the start of my code I find the first letter matching the first letter of the word I am searching for, then when it finds it, it checks in 8 directions if it can make the whole word without going out of the crossword.

program ideone;
var
kar:array[1..1000, 1..1000] of char;
konacno:int64;
i2,i3,n,xx,yy:integer;
s:string;
procedure trag(y:integer; x:integer; y1:integer; x1:integer; i:integer);
        var
        x2,y2:integer;
    begin
    x2:=x+x1;
    y2:=y+y1;
    while (x2<=n) and (x2>0) and (y2<=n) and (y2>0) do begin
        if kar[y2,x2]=s[i+1] then
            if i=length(s)-1 then
            konacno:=konacno+1
            else
            trag(y2,x2,y1,x1,i+1);

    x2:=x2+x1;
    y2:=y2+y1;
    end;
    end;
begin
readln(n,s);
delete(s,1,1);
xx:=1;
yy:=1;
for i2:=1 to n do begin
for i3:=1 to n do
read(kar[i2,i3]);
readln();
end;
konacno:=0;

for i2:=1 to n*n do begin
    if kar[yy][xx]=s[1] then begin
        trag(yy,xx,-1,-1,1);
        trag(yy,xx,-1,0,1);
        trag(yy,xx,-1,1,1);
        trag(yy,xx,0,1,1);
        trag(yy,xx,1,1,1);
        trag(yy,xx,1,0,1);
        trag(yy,xx,1,-1,1);
        trag(yy,xx,0,-1,1);
    end;
    xx:=xx+1;
    if xx>n then begin
    xx:=1;
    yy:=yy+1;
    end;


end;

writeln(konacno);

end.

If you have any tips please tell me, I am new to Pascal, so I don't know all the tricks for speeding up the program, and I don't want to use C or C++.

\$\endgroup\$
  • \$\begingroup\$ Say your word to find is three characters long. Then you would not need to search to the right if you are less than three characters from the right edge of the array because you could not possibly find the rest of the word there. Apply that idea to the rest of the directions, and you will have somewhat less searching to do. \$\endgroup\$ – Andrew Morton Apr 12 '14 at 16:33
  • \$\begingroup\$ Okay I will try now, also I have changed the program so at the start I find out if the work I am searching for is a palindrome, if it is, I cut down 4 procedures and multiply the final result by 2 \$\endgroup\$ – user40582 Apr 12 '14 at 16:35
  • \$\begingroup\$ 5 edits but no one helps me hahaha \$\endgroup\$ – user40582 Apr 12 '14 at 18:30
  • 2
    \$\begingroup\$ Please be patient. Reviews can come at any time (some days are slower than others), and there may not be too many people familiar with this language. \$\endgroup\$ – Jamal Apr 12 '14 at 20:15
  • \$\begingroup\$ To go off of @Jamal's point, pascal-script isn't that popular of a language, so not that many people will be able to review this code. That only increases review time. \$\endgroup\$ – syb0rg Apr 12 '14 at 20:21
3
\$\begingroup\$

First you can change those non-required letters to a specific character like '.'.

Turning the 2D array into a string or array of byte. For example:

1234
5678
90ab
cdef
=>
string1: 1234
string2: 5678
string3: 90ab
string4: cdef

Remove '.' in these string so that later u can check faster.

Also doing this with other rows, column, and oblique.

Scan result in -> or <- direction only.

Related algorithm you may find here.

Moreover, you can omit some impossible cases such as:

input:

8 aaaa
aaaaoooo
oooooooo
oooooooo
oooooooo
oooooooo
oooooooo
oooooooo
oooooooo

Find those which never touch required characters like the last three rows in this case and do not trag() with it.

I suggest using this algorithm to scan it:

For rows:

var 
    ignore: array[1..1000, 1..1000] of boolean;
    counter: integer;
counter:=0;
for i:=1 to n do
    while j<=n do
    begin
        ignore[i, j]:=false;
        if kar[i, j] = '.' then
        begin
             count:=count+1;
             ignore[i, j]:=counter> length(s);
             break;
        end
        else
            counter:=0;
    end;
\$\endgroup\$
  • \$\begingroup\$ thank you for expanding this into a full answer, we appreciate all the users that contribute to CodeReview \$\endgroup\$ – Malachi May 25 '14 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.