WasteLand: Grafinio slaptažodžio atspėjimo galimybė

Android operacinę sistemą naudojančiuose telefonuose galime užsidėti grafinį slaptažodį. Tai tam tikrų paspaudžiamų simbolių grupė, kuri ir sudaro slaptažodį.

Taigi kokia galimybė yra atspėti tokį slaptažodį? Pati logiškiausia mintis yra sugalvoti matematinį metodą apskaičiuojant derinius.

Tai yra, reikia nustatyti pradines sąlygas:

Kryptis turi vertę;
Kiekvieną tašką galima pereiti tik kartą;
Kad sujungtume du taškus, jie turi būti vienas prie kito. Tai yra pirmas taškas gali būti sujungtas tik su antru, o ne su trečiu;
Viso taškų: nuo 5 iki 9.

Kitas žingsnis: atrinkimas. Mintis surasti reguliarumą.

1 sujungimas = 56 variantai;

2 sujungimai = 320 variantų;

3 sujungimai = 1624 variantai;

4 sujungimai = 7152 variantai;

5 sujungimai = rezultatas neaiškus.

Penkiems sujungimams žmogaus protui jau per sudėtinga. Taigi tam galima pasiremti programavimu. Paskalio programavimo kalboje galima pasinaudoti tokiu programos kodu:

Program First;
Uses Crt;

VAR
i,j,k,cur_i,cur_j,hop_count:byte;
A:array[1..3,1..3] of byte;
Bom:Array[1..10000,1..5] of byte;
path_num,total,m,n:longint;


Procedure PATH(cur_i,cur_j:byte; k:byte);
VAR
i,j:byte;
m,n:integer;

begin

{We will calclate only path amount, but not detailed paths, because of
limitation to array size.
Actually you can make detailed path up to 5 hops. You just should uncomment
calculating of array 'Bom'}

A[cur_i,cur_j]:=1;
for i:=1 to 3 do
begin
    for j:=1 to 3 do
    begin

{        Bom[path_num,k]:=cur_i*10+cur_j;}
        if k1)and(A[i,2]=0))
             or
             ((j=cur_j)and(abs(i-cur_i)>1)and(A[2,j]=0))
             or
             ( (abs(i-cur_i)>1) and (abs(j-cur_j)>1) and (A[2,2]=0))

             )
             then
                begin

                     {We will enlarge path number if hop amount in path is
                     qual to actual hop amount only}
                     if k=hop_count then
                     begin
                          path_num:=path_num+1;
{                          Bom[path_num,k+1]:=i*10+j;}
                     end;
                     A[i,j]:=1;
                     {Recursive running of path calculation}
                     PATH(i,j,k+1);
                     A[i,j]:=0;
                end;
        end
        else
        begin
             if (A[i,j]=0)and

             not(

             ((i=cur_i)and(abs(j-cur_j)>1)and(A[i,2]=0))
             or
             ((j=cur_j)and(abs(i-cur_i)>1)and(A[2,j]=0))
             or
             ( (abs(i-cur_i)>1) and (abs(j-cur_j)>1) and (A[2,2]=0))

             )
             then
             begin
             {Enlarge path number after exit out of procedure}
{                     Bom[path_num,k+1]:=i*10+j;}
                     path_num:=path_num+1;
             end;

        end;
    end;
end;
end;



begin

{A[x,y] - Array of 0 and 1.
0 - this point isn't in path yet. You can move here.
1 - this point is in path already. You can't move here.
}
ClrScr;
writeln ('Let','''','s count amount of Android Graphical passwords.');
writeln;

i:=1;
j:=1;
k:=1;

for hop_count:=4 to 8 do
begin

     path_num:=1;
     for i:=1 to 3 do
         for j:=1 to 3 do
         begin
{            Bom[path_num,k]:=10*i+j;}

            PATH(i,j,k);
            a[i,j]:=0;
         end;
     writeln('Hops: ',hop_count,'. Path amount: ',path_num-1);
     total:=total+path_num-1;


end;

writeln('===========================');
writeln('Total amount:         ',total);


{Output of full list of paths.}

{for m:=1 to path_num do
begin
    write('Path ', m,': (');
    for n:=1 to hop_count+1 do
    begin
         write(Bom[m,n],' ');
    end;
    writeln(')');

    readln;
end;{}
readln;
end.

Taigi gauname kiekį variantų kiekvienam sujungimo skaičiui. Nuo 1 iki 4 sujungimų gaunamas beveik tikslus skaičius su apskaičiuotu. O naudojant daugiau nei 8 sujungimus - atspėti galimybės nėra.

Paskalis turi 64 kb masyvo dydžio apribojimą. Todėl masyvas su dešimt tūkstančių elementų yra neįmanomas. Taigi apskaičiuoti duomenis galima tik iki 4 sujungimų: