Laboratorium 10: Omówienie zadania zaliczeniowego 3

program wp10zad3;
 
const
    ROZMIAR = 8;
    MAX_PIONOW = ROZMIAR * ROZMIAR;
    ZNAK_BIALEGO = 'b';
    ZNAK_CZARNEGO = 'c';
    ZNAK_PUSTEGO = '-';
    BIALY = -1;
    PUSTE = 0;
    CZARNY = 1;
 
type
    Gracz = BIALY .. CZARNY;
    PozycjaNaPlanszy = 0 .. ROZMIAR * (ROZMIAR + 2) - 1;
    NumerPiona = -MAX_PIONOW .. MAX_PIONOW;
    Kierunek = -1 .. 1;
 
var plansza : array [PozycjaNaPlanszy] of NumerPiona;
    pozycje : array [NumerPiona] of PozycjaNaPlanszy;
    ostatni : array [Gracz] of NumerPiona;
 
procedure wczytaj;
var i, j, aktualna : Integer;
    c : Char;
    kto : Gracz;
begin
    for i := BIALY to CZARNY do
        ostatni[i] := 0;
    aktualna := 1;
    for i := 1 to ROZMIAR do begin
        plansza[aktualna - 1] := PUSTE;
        for j := 1 to ROZMIAR do begin
            read(c);
            kto := ord(c = ZNAK_CZARNEGO) - ord(c = ZNAK_BIALEGO);
            assert((kto = PUSTE) = (c = ZNAK_PUSTEGO));
            assert((kto <> BIALY) or (i <> 1));
            assert((kto <> CZARNY) or (i <> ROZMIAR));
            inc(ostatni[kto], kto);
            plansza[aktualna] := ostatni[kto];
            pozycje[plansza[aktualna]] := aktualna;
            inc(aktualna)
        end;
        assert(eoln);
        readln;
        plansza[aktualna] := PUSTE;
        inc(aktualna, 2)
    end;
    assert(eof)
end;
 
function wygraRuchem(kto : Gracz; czym: NumerPiona; jak : Kierunek;
                     zmianaRzedu : Integer; cel : Integer) : Boolean;
var docelowe : Integer;
    skad, pozycjaOstatniego : PozycjaNaPlanszy;
    ostatniPrzeciwnika, naDocelowym, pionPrzeciwnika : NumerPiona;
    przeciwnikMozeWygrac : Boolean;
    ruchPrzeciwnika : Kierunek;
begin
    wygraRuchem := false;
    skad := pozycje[czym];
    docelowe := skad + zmianaRzedu + jak;
    naDocelowym := plansza[docelowe];
    if (jak = 0) and (naDocelowym = PUSTE) or
            (jak <> 0) and (naDocelowym * czym < 0) then
        if docelowe div (ROZMIAR + 2) = cel then
            wygraRuchem := true
        else begin
            plansza[skad] := PUSTE;
            pozycje[czym] := docelowe;
            if jak <> 0 then begin
                ostatniPrzeciwnika := ostatni[-kto];
                pozycjaOstatniego := pozycje[ostatniPrzeciwnika];
                plansza[pozycjaOstatniego] := naDocelowym;
                pozycje[naDocelowym] := pozycjaOstatniego;
                Dec(ostatni[-kto], -kto)
            end;
            plansza[docelowe] := czym;
            ruchPrzeciwnika := -1;
            pionPrzeciwnika := ostatni[-kto];
            przeciwnikMozeWygrac := false;
            while not przeciwnikMozeWygrac and (pionPrzeciwnika <> 0) do begin
                przeciwnikMozeWygrac := wygraRuchem(-kto, pionPrzeciwnika,
                    ruchPrzeciwnika, -zmianaRzedu, 7 - cel);
                ruchPrzeciwnika := (ruchPrzeciwnika + 2) mod 3 - 1;
                if ruchPrzeciwnika = -1 then
                    inc(pionPrzeciwnika, kto)
            end;
            wygraRuchem := not przeciwnikMozeWygrac;
            if jak <> 0 then begin
                inc(ostatni[-kto], -kto);
                plansza[pozycjaOstatniego] := ostatniPrzeciwnika;
                pozycje[naDocelowym] := docelowe
            end;
            plansza[docelowe] := naDocelowym;
            pozycje[czym] := skad;
            plansza[skad] := czym
        end
end;
 
procedure wypisz;
var i, j, k, aktualna : Integer;
    pion : NumerPiona;
    kod : 0 .. 7;
begin
    aktualna := 1;
    for i := 1 to ROZMIAR do begin
        for j := 1 to ROZMIAR do begin
            pion := plansza[aktualna];
            inc(aktualna);
            if pion > 0 then
                write(ZNAK_CZARNEGO)
            else if pion = 0 then
                write(ZNAK_PUSTEGO)
            else begin
                kod := 0;
                for k := -1 to 1 do
                    kod := 2 * kod + ord(wygraRuchem(BIALY, pion, k,
                                                     -(ROZMIAR + 2), 0));
                write(kod)
            end
        end;
        inc(aktualna, 2);
        writeln
    end
end;
 
begin
    wczytaj;
    wypisz
end.

wxaybab{cwwxwxbx}yc

program wp09zad3;
 
const
    SZEROKOSC_STRONY = 595;
    WYSOKOSC_STRONY = 842;
    MARGINES_POZIOMY = 20;
    SRODEK_SZEROKOSCI = SZEROKOSC_STRONY / 2;
    SZEROKOSC_LABIRYNTU = SZEROKOSC_STRONY - 2 * MARGINES_POZIOMY;
    WYSOKOSC_LABIRYNTU = SZEROKOSC_LABIRYNTU * sqrt(3) / 2;
    MARGINES_PIONOWY = (WYSOKOSC_STRONY - WYSOKOSC_LABIRYNTU)  / 2;
    LICZBA_POZIOMOW = 61;
    BOK_KOMORKI = SZEROKOSC_LABIRYNTU / LICZBA_POZIOMOW;
    WYSOKOSC_KOMORKI = WYSOKOSC_LABIRYNTU / LICZBA_POZIOMOW;
    ODLEGLOSC_SRODKOW = WYSOKOSC_KOMORKI * 2 / 3;
    LICZBA_KOMOREK = sqr(LICZBA_POZIOMOW);
    INDEKS_WYJSCIA = LICZBA_KOMOREK - LICZBA_POZIOMOW;
    SZEROKOSC_PNIA = 30;
    WYSOKOSC_PNIA = 40;
    LICZBA_KIERUNKOW = 3;
    LEWO = 0;
    GORA_DOL = 1;
    PRAWO = 2;
 
type
    Kierunek = LEWO .. PRAWO;
    Komorka = record
        jestSciana : array [Kierunek] of Boolean;
        znacznik : Boolean
    end;
 
var
    odwiedzona : Boolean;
    komorki : array [0 .. LICZBA_KOMOREK - 1] of Komorka;
 
function indeks(poziom, numer : Integer) : Integer;
begin
    indeks := sqr(poziom) + numer
end;
 
procedure poziomNumer(indeks : Integer; var poziom, numer : Integer);
begin
    poziom := trunc(sqrt(indeks));
    numer := indeks - sqr(poziom)
end;
 
procedure moveto(x, y : Real);
begin
    writeln(x, ' ', y, ' moveto')
end;
 
procedure rmoveto(x, y : Real);
begin
    writeln(x, ' ', y, ' rmoveto')
end;
 
procedure rlineto(x, y : Real);
begin
    writeln(x, ' ', y, ' rlineto')
end;
 
procedure rysujParzystaKomorke(poziom, numer : Integer);
begin
    moveto(SRODEK_SZEROKOSCI - (poziom - numer) * BOK_KOMORKI / 2,
           WYSOKOSC_STRONY - MARGINES_PIONOWY - poziom * WYSOKOSC_KOMORKI);
    if komorki[indeks(poziom, numer)].jestSciana[LEWO] then
        rlineto(- BOK_KOMORKI / 2, - WYSOKOSC_KOMORKI)
    else
        rmoveto(- BOK_KOMORKI / 2, - WYSOKOSC_KOMORKI);
    if komorki[indeks(poziom, numer)].jestSciana[GORA_DOL] then
        rlineto(BOK_KOMORKI, 0)
    else
        rmoveto(BOK_KOMORKI, 0);
    if komorki[indeks(poziom, numer)].jestSciana[PRAWO] then
        rlineto(- BOK_KOMORKI / 2, WYSOKOSC_KOMORKI)
end;
 
procedure rysujLabirynt;
var i, j : Integer;
begin
    moveto(SRODEK_SZEROKOSCI - SZEROKOSC_PNIA / 2, MARGINES_PIONOWY);
    rlineto(0, - WYSOKOSC_PNIA);
    rlineto(SZEROKOSC_PNIA, 0);
    rlineto(0, WYSOKOSC_PNIA);
    for i := 0 to LICZBA_POZIOMOW - 1 do
        for j := 0 to i do
            rysujParzystaKomorke(i, 2 * j);
    writeln('stroke')
end;
 
function nieodwiedzonaKomorka(i, j : Integer) : Boolean;
begin
    if (i < 0) or (i > LICZBA_POZIOMOW - 1) or (j < 0) or (j > 2 * i) then
        nieodwiedzonaKomorka := false
    else
        nieodwiedzonaKomorka := komorki[indeks(i, j)].znacznik <> odwiedzona
end;
 
procedure sasiad(x, y : Integer; k : Kierunek; var a, b : Integer);
begin
    case k of
        LEWO : begin
            a := x;
            b := y - 1
        end;
        GORA_DOL :
            if odd(y) then begin
                a := x - 1;
                b := y - 1
            end else begin
                a := x + 1;
                b := y + 1
            end;
        PRAWO : begin
            a := x;
            b := y + 1
        end
    end
end;
 
function przeciwny(k : Kierunek) : Kierunek;
begin
    przeciwny := LICZBA_KIERUNKOW - 1 - k
end;
 
procedure przebijajSciany(x, y : Integer);
var i, pozycjaWybranego, a, b : Integer;
    s, wybrany : Kierunek;
    doSprawdzenia : array [0 .. LICZBA_KIERUNKOW - 1] of Kierunek;
begin
    komorki[indeks(x, y)].znacznik := odwiedzona;
    for s := LEWO to PRAWO do
        doSprawdzenia[s] := s;
    for i := 0 to LICZBA_KIERUNKOW - 1 do begin
        pozycjaWybranego := i + random(LICZBA_KIERUNKOW - i);
        wybrany := doSprawdzenia[pozycjaWybranego];
        doSprawdzenia[pozycjaWybranego] := doSprawdzenia[i];
        sasiad(x, y, wybrany, a, b);
        if nieodwiedzonaKomorka(a, b) then begin
            komorki[indeks(x, y)].jestSciana[wybrany] := false;
            komorki[indeks(a, b)].jestSciana[przeciwny(wybrany)] := false;
            przebijajSciany(a, b)
        end
    end
end;
 
procedure stworzLabirynt;
var i, x, y : Integer;
    k : Kierunek;
begin
    for i := 0 to LICZBA_KOMOREK-1 do begin
        for k := LEWO to PRAWO do
            komorki[i].jestSciana[k] := true;
        komorki[i].znacznik := false
    end;
    odwiedzona := true;
    poziomNumer(random(LICZBA_KOMOREK), x, y);
    przebijajSciany(x, y);
    komorki[INDEKS_WYJSCIA].jestSciana[GORA_DOL] := false
end;
 
procedure zacznijRysowanieDrogi;
begin
    moveto(SRODEK_SZEROKOSCI, MARGINES_PIONOWY - WYSOKOSC_PNIA / 2);
    rlineto(0, WYSOKOSC_PNIA / 2 + ODLEGLOSC_SRODKOW / 2)
end;
 
procedure rysujKrok(odbicie : Integer; k : Kierunek);
begin
    rlineto(ODLEGLOSC_SRODKOW * cos(PI * (4 * k - 1) / 6),
            odbicie * ODLEGLOSC_SRODKOW * sin(PI * (4 * k - 1) / 6))
end;
 
function jestRozwiazanie(x, y : Integer) : Boolean;
var znalezione : Boolean;
    k, a, b : Integer;
begin
    if not nieodwiedzonaKomorka(x, y) then
        jestRozwiazanie := false
    else begin
        komorki[indeks(x, y)].znacznik := odwiedzona;
        if indeks(x, y) = INDEKS_WYJSCIA then begin
            zacznijRysowanieDrogi;
            jestRozwiazanie := true
        end else begin
            znalezione := false;
            k := LEWO;
            while (k <= PRAWO) and not znalezione do begin
                if not komorki[indeks(x, y)].jestSciana[k] then begin
                    sasiad(x, y, k, a, b);
                    if jestRozwiazanie(a, b) then begin
                        rysujKrok((b mod 2) * 2 - 1, k);
                        znalezione := true
                    end
                end;
                k := k + 1
            end;
            jestRozwiazanie := znalezione
        end
    end
end;
 
procedure rozwiazLabirynt;
begin
    odwiedzona := not odwiedzona;
    writeln('[2] 0 setdash');
    if not jestRozwiazanie(0, 0) then
        writeln('% Blad algorytmu budujacego labirynt');
    writeln('stroke')
end;
 
begin
    randomize;
    writeln('%!PS');
    stworzLabirynt;
    rysujLabirynt;
    writeln('showpage');
    rysujLabirynt;
    rozwiazLabirynt;
    writeln('showpage')
end.

ALA_MA_KOTA_ALE_NIE_MA_MYSZY

./wp08lab_zad3 K N

./wp08lab_zad3 1 50

ALA_MA_KOTA_ALE_NIE_MA_MYSZY

ALE_MA_KOTALALE_NIE_NIE_ALE_NIE_ALE_A_ALE_A_NIE_MY

./wp08lab_zad3 0 200 <wp08lab_zad1.txt

WwPpeBxyt}oATuxprsspJZZ.g""|pijNyTZT1tS-Iaw{Pchdd ywt<W
WjldpCwA}iBrzgityCPt|b"xZTmPrw<|ce1G
C.kaeGuh}u<iT}J1pGwy|"
ltjg|x"NNxBy
TGkugmNrGhIy<1kh.y|nZkdlJNbrzIpIypWIW:.pS
AJBeAso}}hytatx  ."e,hs G-kot

./wp08lab_zad3 1 200 <wp08lab_zad1.txt

Wserzwnioleprelico,zc kcz}", ksabiespusami:
g
Inciczw. sich:
semo,},T ie:
Pomakamu. wnt,A>|CCCC},Sbelubeg
GraSym ->},{B>Blu. uzakodywilnnilowypo.
Inkaw,bS->,zy}"{"wi:
Na,blicedejdozpicicna
Zaci tu, la

./wp08lab_zad3 2 200 <wp08lab_zad1.txt

Wsty wy stu pow.
S - zapis z
pram, lu, grawnyc matow.
S - niczapisementych, lu "w" tory zami "|". W symi, a do slicz
tyklady cwiej jeslitekstrogramaty,z},A>
 
Zakamy,S->w", cwielonegolnosty, od z sach.

./wp08lab_zad3 3 200 <wp08lab_zad1.txt

Wstepuja wykladane pusty, rozdzi, elementy znaczego by danych znakiemy zadnych
T - zapisz tekstowa pusty, ciag
znajdujemy symbol pomocniczego. Slowo przykladane danie "A" to ma
wypisywaliczenty ciag p

./wp08lab_zad3 4 200 <wp08lab_zad1.txt

Wstep do produkcja.
 
Przyjmujemy, byc moze puste jest, programatyki bezkontekstu z
poprawdzi, czy znakiem "}". Pomiedzy tymi
znakow, oprocz
tych strona produkcji postaci "A->w", gdzie "A" to symbol po

./wp08lab_zad3 5 200 <wp08lab_zad1.txt

Wstep do program, ktory sprawdzi, czy na wejsciu znajduje sie wiersz tekstu z
poprawne dane
 
w przecinkami, elementy zbioru symboli konczy znaku "{" a koncowych
P - zapisem gramatyki bezkontekstowej.

program wp08zad3;
 
const
    MAX_ZNAK = 255;
 
type
    Konteksty = ^Wezel;
    Wezel = record
        koncowy : Char;
        ile : Integer;
        nastepne : array [Char] of Konteksty;
        znaki : array [0 .. MAX_ZNAK] of Char;
        slad, kolejny : Konteksty
    end;
 
var aktualny, lista, graf, drzewo, akt, w : Konteksty;
    i, rzad, ograniczenie : Longint;
    kodBledu : Word;
    c, znak : Char;
 
function nowyWezel : konteksty;
var pom : Konteksty;
    c : Char;
begin
    new(pom);
    pom^.koncowy := chr(0);
    pom^.ile := 0;
    for c := chr(0) to chr(MAX_ZNAK) do
        pom^.nastepne[c] := nil;
    pom^.slad := nil;
    pom^.kolejny := lista;
    lista := pom;
    nowyWezel := pom
end;
 
begin
    randomize;
    if (paramcount <> 2) then begin
        writeln('Program oczekuje dwoch argumentow');
        halt
    end;
    rzad := 0;
    val(paramstr(1), rzad, kodBledu);
    if (kodBledu <> 0) or (rzad < 0) then begin
        writeln('Dlugosc kontekstu powinna byc nieujemna liczba calkowita');
        halt
    end;
    ograniczenie := 0;
    val(paramstr(2), ograniczenie, kodBledu);
    if (kodBledu <> 0) or (ograniczenie < 0) then begin
        writeln('Ograniczenie powinno byc nieujemna liczba calkowita');
        halt
    end;
    lista := nil;
    graf := nowyWezel;
    graf^.slad := graf;
    drzewo := nowyWezel;
    aktualny := graf;
    while not eof do begin
        read(znak);
        if aktualny^.nastepne[znak] = nil then begin
            w := drzewo;
            akt := aktualny;
            c := znak;
            for i := 1 to rzad do begin
                if w^.nastepne[c] = nil then
                    w^.nastepne[c] := nowyWezel;
                w := w^.nastepne[c];
                c := akt^.koncowy;
                akt := akt^.slad
            end;
            w^.slad := aktualny;
            w^.koncowy := znak;
            aktualny^.nastepne[znak] := w;
            aktualny^.znaki[aktualny^.ile] := znak;
            aktualny^.ile := aktualny^.ile + 1
        end;
        aktualny := aktualny^.nastepne[znak]
    end;
    aktualny := graf;
    while (aktualny^.ile <> 0) and (ograniczenie > 0) do begin
        znak := aktualny^.znaki[random(aktualny^.ile)];
        write(znak);
        ograniczenie := ograniczenie - 1;
        aktualny := aktualny^.nastepne[znak]
    end;
    while lista <> nil do begin
        aktualny := lista;
        lista := lista^.kolejny;
        dispose(aktualny)
    end
end.

type
    Lista = ^ElementListy;
    ElementListy = record
        w : Integer;
        nast : Lista
    end;
var a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z : Lista;

p^.nast...^.nast

new(SCIEZKA)

dispose(SCIEZKA)

SCIEZKA:=nil

SCIEZKA:=SCIEZKA

_:=SCIEZKA^.w

SCIEZKA^.w:=_

new(p)
new(p^.nast)
q:=p
dispose(q^.nast)
_:=p^.nast^.w
dispose(p)

Blad w instrukcji 5

new(p)
q:=p
new(r)
q^.nast:=r
dispose(p)

Wyciek pamieci

new(p)
new(p^.nast)
q:=p^.nast
q^.w:=_
p^.nast^.w:=_
new(p^.nast^.nast)
p^.nast^.nast^.nast:=p
_:=q^.nast^.nast^.nast^.w
dispose(q^.nast^.nast)
dispose(q^.nast)
dispose(q)
p:=nil

program wp07zad3;
 
const
    ROZMIAR_PAMIECI = 100;
    PUSTE = 0;
    NIEOKRESLONE = -1;
    OKRESLONE = 1;
 
var zmienne : array ['a' .. 'z'] of Integer;
    heap : array [1 .. ROZMIAR_PAMIECI] of record
        w : Integer;
        nast : Integer
    end;
    c : Char;
    s : String;
    num, i, co, wolne : Integer;
 
procedure blad;
begin
    writeln('Blad w instrukcji ', num);
    halt
end;
 
function odczytaj(pocz, kon : Integer) : Integer;
var i, wynik : Integer;
begin
    if (kon = pocz + 2) and (s[kon] = 'l') then
        odczytaj := PUSTE
    else begin
        wynik := zmienne[s[pocz]];
        for i := 1 to (kon - pocz) div 6 do begin
            if wynik = NIEOKRESLONE then
                blad;
            wynik := heap[wynik].nast;
        end;
        if wynik = NIEOKRESLONE then
            blad
        else
            odczytaj := wynik
    end
end;
 
procedure zapisz(pocz, kon, wartosc : Integer);
begin
    if pocz = kon then
        zmienne[s[pocz]] := wartosc
    else
        heap[odczytaj(pocz, kon - 6)].nast := wartosc
end;
 
begin
    for c := 'a' to 'z' do
        zmienne[c] := NIEOKRESLONE;
    for i := 1 to ROZMIAR_PAMIECI do
        heap[i].w := PUSTE;
    wolne := ROZMIAR_PAMIECI;
    num := 1;
    readln(s);
    while s <> '' do begin
        if s[2] = 'e' then begin
            if wolne = 0 then
                blad
            else begin
                i := 1;
                while heap[i].w <> PUSTE do
                    i := i + 1;
                heap[i].w := NIEOKRESLONE;
                heap[i].nast := NIEOKRESLONE;
                wolne := wolne - 1;
                zapisz(5, pos(')', s) - 1, i)
            end
        end else if s[2] = 'i' then begin
            co := odczytaj(9, pos(')', s) - 1);
            if (co = NIEOKRESLONE) or (co = PUSTE) then
                blad;
            for c := 'a' to 'z' do
                if zmienne[c] = co then
                    zmienne[c] := NIEOKRESLONE;
            for i := 1 to ROZMIAR_PAMIECI do
                if heap[i].nast = co then
                    heap[i].nast := NIEOKRESLONE;
            heap[co].w := PUSTE;
            wolne := wolne + 1
        end else if s[1] = '_' then begin
            co := odczytaj(4, length(s) - 3);
            if (co = PUSTE) or (co = NIEOKRESLONE) then
                blad;
            if heap[odczytaj(4, length(s) - 3)].w = NIEOKRESLONE then
                blad
        end else if s[length(s)] = '_' then
            heap[odczytaj(1, length(s) - 6)].w := OKRESLONE
        else
            zapisz(1, pos(':', s) - 1, odczytaj(pos('=', s) + 1, length(s)));
        num := num + 1;
        readln(s)
    end;
    if wolne <> ROZMIAR_PAMIECI then
        writeln('Wyciek pamieci')
end.