Pot po papirju

Pot po papirju

Avtor: Mateja Gorišek, pred. M.Lokar, prenos v NAUK Alja Gligić

Opis problema

Polžek Pepe potuje po papirju. Pot prične v točki (0,0) in nadaljuje v skladu z navodili, zapisanimi v nizu znakov, sestavljeni iz črk L (ki pomeni pomik za eno enoto v levo), R (desno), U (gor) in D (dol). Izračunaj končno točko te poti. Če pot vsebuje cikle, izpiši navodila, ga vodijo po isti poti, a brez nepotrebnih ciklov. Polž se želi vrniti nazaj v izhodišče po najkrajši poti, vendar tako, da na svoji poti ne bo nikoli zavil na desno.

(navodilo.png)

Ideja rešitve

Nalogo sem si najprej narisala na papir (koordinatni sistem in točke).

Nalogo bom rešila s pomočjo točk oziroma kar tabelo točk, v kateri bom imela shranjene tudi vmesne točke in prav tako končno točko. Najprej bom v tabelo shranila začetno točko (koordinatno izhodišče), nato bom računala vmesne vsote točk in te vmesne točke tudi shranjevala v tabelo. Tako se bo za premik v levo, prejšnja točka spremenila za (-1, 0) ali v desno za (1, 0) ali gor za (0, 1) ali dol za (0, -1). Tako bom s pomočjo prejšnje točke izračunala trenutno točko. Končna točka v katero bo prišel Pepe bo zadnja točka v tabeli.

Sedaj, ko imam tabelo točk, bom lahko iz te tabele odstranila vse cikle, da dobim navodila za krajšo pot. Sprehodila se bom po tabeli točk, z dvema števcema, eden bo šel od začetka tabele, drugi od konca tabele. Ko bosta oba števca naletela na enako točko in pri tem ne bosta kazala na isto točko, bom v novo tabelo shranila vse točke do prvega števca in vse točke od drugega števca naprej. Torej bom 'izrezala' cikel iz tabele. Nato bo stara tabela kazala na novo tabelo. Tabelo bom pregledovala toliko časa, dokler prvi števec ne bo kazal na zadnjo točko v tabeli. S tem bom dobila tabelo točk brez ciklov. Nato bom morala iz te tabele dobiti navodila. Sprehodila se bom po tabeli in pri tem primerjala prejšnjo točko s trenutno točko. Glede na to kako se bo točka spremenila, bom v niz shranila pravilen pomik.

Na koncu se mora polžek vrniti še po najkrajši poti nazaj, ne da bi pri tem zavil na desno. Končno točko v katero je prišel polžek, imam v tabeli točk, to je zadnja točka v tej tabeli. Iz zadnje točke izrazim x koordinato in y koordinato. S pomočjo teh dveh koordinat se bo polžek vrnil . Ker se polžek premika po koordinatnem sistemu, bom najprej preverila v katerem kvadrantu v koordinatnem sistemu je polžek. Glede na to v katerem kvadrantu bo polžek, se bo polžek vrnil po navodilih, najprej bo zavil levo in nato gor ali navzdol ali pa obratno, odvisno od x in y koordinate.

Ker bom pri tej nalogi uporabljala tabele, bom morala te tabele še izpisati. Tako bom naredila še eno metodo, ki mi bo iz tabele naredila niz. Torej se bom pri tej metodi sprehodila po tabeli in posamezne točke v tabeli shranjevala v niz, točke bom ločila s presledkom.

Metoda koncnaTocka (koda v C#)

 public static Point[] koncnaTocka(string niz)
        { /* metoda mi vrne v tabeli koordinate skozi katere gre polžek, sprejme pa niz črk*/
            Point[] pozicije = new Point[niz.Length + 1]; // v tabeli pozicije bomo imeli vse točke
            // začetna točka je (0, 0)
            pozicije[0].X = 0;
            pozicije[0].Y = 0;
            int stevec = 1; // števec, ki gre po tabeli, gre od druge točke naprej
            for (int i = 0; i < niz.Length; i++) // z zanko se sprehodimo čez niz
            {
                if (niz[i] == 'L')  // če je i-ti znam enak L
                {
                    pozicije[stevec].X = pozicije[stevec - 1].X - 1; // prejšnjo X koordito točke zmanjšamo za ena, in to je sedaj trenutna točka
                    pozicije[stevec].Y = pozicije[stevec - 1].Y; // Y ostane enak
                    stevec++; // pri tem se poveča tudi števec, ki gre po tabeli
                }
                else if (niz[i] == 'R')  // če je i-ti znak enak R
                {
                    pozicije[stevec].X = pozicije[stevec - 1].X + 1; // prejšnjo X koordinato povečamo za 1 in dobimo trenutno koordinato
                    pozicije[stevec].Y = pozicije[stevec - 1].Y;
                    stevec++;
                }
                else if (niz[i] == 'U')  // če je i-ti znak enak U
                {
                    pozicije[stevec].X = pozicije[stevec - 1].X;
                    pozicije[stevec].Y = pozicije[stevec - 1].Y + 1; // koordinato Y povečamo za ena
                    stevec++;
                }
                else if (niz[i] == 'D')  // če je i-ti znak enak D
                {
                    pozicije[stevec].X = pozicije[stevec - 1].X;
                    pozicije[stevec].Y = pozicije[stevec - 1].Y - 1; // koordinato Y zmanjšamo za ena
                    stevec++;
                }
            }
            return pozicije; // vrnemo tabelo pozicij
        }

Metoda koncnaTocka (razlaga algoritma)

Metoda koncnaTocka(niz):
Metoda mi vrne tabelo točk, skozi katere potuje polžek. Najprej sem deklarirala tabelo točk, ki je za ena večje dolžine kakor podani niz. V to tabelo sem najprej shranila začetno točko, to je koordinatno izhodišče, točka (0, 0). Nato deklariram števec s katerim se bom premikala po tabeli točk. Sedaj se lahko z zanko for sprehodim čez niz, pri tem pa preverjam naslednje:

  • Če je trenutni znak v nizu znak 'L', se je polžek premaknil za eno enoto v levo. To pomeni, da bo trenutna točka za ena manjša kakor prejšnja točka oz. trenutno točko dobim tako, da x koordinato prejšnje točke zmanjšam za ena. Y koordinata točke pri tem ostane enaka. Sedaj ko sem spremenila trenutno točko, se moram premakniti tudi v tabeli točk, torej števec, ki gre po tabeli točk povečam za ena.
  • Če je trenutni znak v nizu znak 'R', se je polžek premaknil za eno enoto v desno. Torej trenutno točko dobim tako, da x koordinato prejšnje točke povečam za ena. Poleg tega povečam tudi števec, ki potuje po tabeli točk.
  • Če je trenutni znak v nizu znak 'U', se je polžek premaknil za eno enota navzgor. Trenutno točko sedaj dobim tako, da prejšnjo y koordinato prejšnje točke povečam za ena. Pri tem pa x koordinata ostane enaka prejšnji. Poleg tega povečam tudi števec, ki potuje po tabeli točk.
  • Če je trenutni znak v nizu znak 'D', se je polžek premaknil za eno enoto navzdol. Torej trenutno točko dobim tako, da od y koordinate prejšnje točke odštejem 1. Pri tem x koordinata točke ostane enaka prejšnji. Poleg tega povečam tudi števec, ki potuje po tabeli točk.

    Ta metoda mi na koncu vrne tabelo točk. Torej, če želim izpisati končno točko v katero je prišel polžek, je to zadnja točka v tabeli točk.

Koda v C#

Metoda koncnaTocka (testni primeri)

Testiranje metode koncnaTocka, ki mi vrne tabelo točk. Na koncu izpišem le končno točko v katero pride polžek Pepe, to je zadnja točka v tabeli točk. Tako bom preverila ali pride polžek v pravilno točko:

  • Najprej metodo testiram na praznem navodilu oz. navodilo sploh ne podam. V tem primeru mora polžek ostati v izhodišču, torej v točki (0, 0).
  • Nato testiram na navodilu, kjer polžka premaknem za eno enoto v eno smer, na primer navzgor. Če bom polžka za eno enoto premaknili navzgor mi mora metoda vrniti točko (0, 1).
  • Nato metodo testiram za primer iz navodila naloge. V tem primeru mi mora metoda vrniti točko (1, 1).
  • Sedaj metodo testiram na primeru, kjer podam navodilo take poti, ki polžka pripelje ponovno v izhodišče V tem primeru mi mora metoda vrniti točko (0, 0).

Testiranje v C#

Metoda koncnaTocka (testiranje))

Metoda krajsaPot (koda v C#)

public static void krajsaPot(Point[] tocke)
        {  /* metoda mi izpiše navodila, ki pripeljejo polžka do iste točke, le po krajši poti */
            int n = tocke.Length;  // n je dolžina tabele točk
            int levo = 0; // števec "levo" gre od prvega do zadnjega elementa v tabeli
            while (levo < n - 1)
            {
                int desno = n - 1; // števec "desno" gre od zadnjega elementa
                while (levo < desno && tocke[levo] != tocke[desno])
                { // števec "desno" zmanjšujemo toliko časa dokler nista neki točki v tabeli enaki in dokler je levi števec večji od desnega
                    desno--;
                }
                if (levo != desno) // če sta števca različna
                {
                    n = n - (desno - levo);
                    Point[] novaTab = new Point[n]; // nova tabela je dolžine n
                    int stevec = 0; // števec, ki potuje po novi tabeli
                    // v novo tabelo shranim vse točke od prve do točke na katero kaže števec levo, vključno z njo
                    for (int i = 0; i <= levo; i++)
                    {
                        novaTab[stevec] = tocke[i];
                        stevec++;
                    }
                    // ter tudi vse od naslednje točke na katero kaže števec "desno" in vse do konca tabele "tocke"
                    for (int j = desno + 1; j < tocke.Length; j++)
                    {
                        novaTab[stevec] = tocke[j];
                        stevec++;
                    }
                    tocke = novaTab; // stara tabela je sedaj nova tabela
                }
                levo++;
            }
            string krajsaPot = ""; // v niz krajsaPot bomo shranili nova navodila za krajšo pot
            for (int k = 1; k < tocke.Length; k++)
            {// k se sprehodi čez tabelo točk, izpusti izhodišče oz. začetno točko v tabeli
                if (tocke[k - 1].X < tocke[k].X) //če je prejšnja x koordinata točke manjša od naslednje
                {
                    krajsaPot += "R"; // v niz shranim "R", gremo desno
                }
                else if (tocke[k - 1].X > tocke[k].X ) // če je prejšnja x koordinata točke večja od naslednje
                {
                    krajsaPot += "L"; // gremo levo --> "L"
                }
                else if (tocke[k - 1].Y < tocke[k].Y) // če je prejšnja y koordinata točke manjša od naslednje
                {
                    krajsaPot += "U";  // gremo gor --> "U"
                }
                else if (tocke[k - 1].Y > tocke[k].Y)  // če je prejšnja y koordinata večja od naslednje
                {
                    krajsaPot += "D";  // gremo dol --> "D"
                }
            }
            Console.WriteLine("Krajša pot je "  + krajsaPot);  // na koncu izpišemo novo navodilo poti
        }

Metoda krajsaPot (razlaga algoritma)

Metoda krajsaPot(tocke):
Metoda sprejme tabelo točk. To je tabela točk, ki jih vrne prejšnja metoda (metoda koncnaTocka). Deklariram spremenljivko n, ki predstavlja dolžino tabele ter števec 'levo', ki bo potoval po tabeli, na začetku je ta števec enak 0. Sedaj se z zanko while sprehodim po tabeli, od prvega do zadnjega elementa. Znotraj te zanke deklariram števec 'desno', ki bo potoval prav tako po tabeli, le da od zadnjega elementa proti prvemu. Nato naredim znotraj zanke še eno zanko while v kateri bom števec 'desno' zmanjševala toliko časa, dokler bo števec 'levo' manjši od števca 'desno' in dokler v tabeli ne naletim na enake točke. Ko v tabeli naletim na enake točke, izstopim iz notranje zanke in števec 'desno', kaže na tisto točko, ki je enaka točki, na katero kaže števec 'levo' ali pa števec 'desno' kaže na enako točko kot števec 'levo'. Če sta pri tem števca različna, ne kažeta na isto točko v tabeli, potem naredim novo tabelo, ki je dolžine n. Pred tem sem dolžino n spremenila tako, da sem iz te dolžine odstranila dolžino cikla. Tako sem dobila novo tabelo dolžine n. V novo tabelo sem nato shranila vse točke do točke na katero kaže števec 'levo', vključno z njo in vse točke od točke na katero kaže števec 'desno'. Stara tabela točk sedaj kaže na novo tabelo točk. Na koncu tega, števec 'levo' povečamo za ena in se iskanje enake točke zopet ponovi. Ko števec 'levo' pride na zadnji element v tabeli se zanka konča. Dobili smo novo tabelo točk brez ciklov.
Iz nove tabele točk bom sedaj naredila niz navodil, ki bo polžka vodil po poti, ki ne vsebuje cikle. Tako najprej deklariram nov niz v katerega bom shranjevala navodila, kam mora polžek zaviti. Tako se sprehodim po tabeli točk. Pri tem pa preverjam, če se trenutna točka razlikuje od prejšnje. Torej preverjam naslednje:

  • Če je x koordinata prejšnje točke manjša od trenutne točke v tabeli, potem se mora polžek za eno enoto premakniti v desno. Eno enoto zato, ker tabela točk predstavlja vse vmesne točke in vse točke se spremenijo za eno enoto. Tako v niz dodam črko 'R'.
  • Če je x koordinata prejšnje točke večja kakor trenutna točka, se mora polžek premakniti za eno enoto v levo. Torej v niz dodam črko 'L'.
  • Če je y koordinata prejšnje točke manjša od y koordinate trenutne točke, potem se mora polžek premakniti za eno enoto navzgor. Tako v niz dodam črko 'U'.
  • Če pa je y koordinata prejšnje točke večja od trenutne y koordinate, potem se mora polžek pomakniti za eno enoto navzdol. Torej v niz dodam črko 'D'. S tem sem dodala v niz 'krajsaPot' navodila po katerih pride polžek do enake točke kot prej, le brez ciklov. Na koncu ta niz še izpišem.

Koda v C#

Metoda krajsaPot (testni primeri)

Testiranje metode krajsaPot, ta metode mi vrne niz navodil, ki polžka vodijo po isti poti do končne točke, le pri tem se izogne vsem ciklom:

  • Najprej metodo testiram na praznem navodilu. V tem primeru mi metoda ne sme vrniti ničesar, saj nismo naredili nobene poti.
  • Nato metodo testiram na primeru, kjer podam samo en znak, torej se polžek premakne le v eno smer. Na primer, da se polžek premakne le navzdol. V tem navodilu poti nimamo ciklov in mora nam metoda vrniti enako navodilo.
  • Nato metodo testiram na navodilu, ki polžka pripelje nazaj v izhodišče. Metoda mi v tem primeru ne sme vrniti ničesar. Saj je polžek naredil cikel, pot ga je pripeljala v isto točko v kateri je začel. Tako mi metoda ne sme vrniti ničesar, saj smo meli v navodilu samo cikel
  • Nato metodo testiram na primeru, ki je podan v navodilu naloge. V tem primeru imamo v navodilu naloge en cikel, katerega mi mora ta metoda odstraniti. Tako mi mora metoda vrniti pot brez ciklov, torej mi v tem primeru vrne navodilo »LURR«.
  • Nato metodo testiram po nizu navodil, kjer mora polžek narediti več ciklov, zadnji cikel je tako velik, da ima znotraj vse manjše cikle po katerih gre polžek. V tem primeru mi mora metoda vrniti pot brez vseh ciklov, ki jih je polžek naredil.
  • Na koncu testiram metodo še na primeru, kjer podam navodilo takšne poti, ki ima dva cikla na različnih mestih. Tako mi mora metoda izbrisati oba cikla iz navodila in vrniti navodilo poti brez teh dveh ciklov.

Testiranje v C#

Metoda krajsaPot (testiranje)

Metoda vracanje (koda v C#)

public static string vracanje(Point[] tocka)
        {  /* metoda mi vrne navodilo poti, po kateri se mora polž vrniti nazaj, na tej poti ne bo nikoli zavil desno */
            // končne točke kamor je prišel so zadnje točke v tabeli
            int x = tocka[tocka.Length - 1].X;
            int y = tocka[tocka.Length - 1].Y;
            string niz_vracanje = "";
            if (x >= 0 && y >= 0)  // če sta obe koordinati večji ali enaki 0
            {
                while (x > 0)
                {
                    niz_vracanje += "L";  // levo se pomikamo toliko časa, dokler x ni enak 0
                    x--;
                }
                while (y > 0)
                {
                    niz_vracanje += "D"; // desno se pomikamo toliko časa dokler y ni enak 0
                    y--;
                }
            }
            else if (x < 0 && y > 0)  // če je x manjši od 0 in y večji od 0
            {
                while (y > 0)
                {
                    niz_vracanje += "D";  // gremo dol tolikokrat dokler y koordinata ni enaka 0
                    y--;
                }
                while (x < 0)
                {
                    niz_vracanje += "L"; // gremo levo tolikokrat dokler je x manjši od 0
                    x++;
                }
            }
            else if (x <= 0 && y <= 0)  // če sta obe koordinati manjši kot 0
            {
                while (x < 0)
                {
                    niz_vracanje += "L";  // gremo levo tolikokrat dokler je x manjši od 0
                    x++;
                }
                while (y < 0)
                {
                    niz_vracanje += "U"; // in gor dokler je y manjši od 0
                    y++;
                }
            }
            else if (x > 0 && y < 0)  // če je x koordinata večja in y koordinata manjša od 0
            {
                while (y < 0)
                {
                    niz_vracanje += "U";  // najprej gremo gor tolikokrat dokler ni y enak 0
                    y++;
                }
                while (x > 0)
                {
                    niz_vracanje += "L"; // in nato levo dokler ni x enak 0
                    x--;
                }
            }
            return niz_vracanje;  // na koncu vrne niz poti, po kateri se Pepe vrne
        }

Metoda vracanje (razlaga algoritma)

Metoda vracanje(tocke):
Ta metoda sprejeme tabelo točk. V tabeli točk imamo shranjene vse točke skozi katere je polžek šel. V tej metodi bom rabila le končno točko v katero je polžek prišel. Tako sem deklarirala spremenljivki tipa int, v katere bom shranila x koordinato končne točke in y koordinato končne točke. Nato deklariram še niz v katerega bom shranjevala niz navodil, po katerih se lahko polžek vrne nazaj v izhodišče. Ker polžek potuje po 'koordinatnem sistemu', sem se odločila, da bom preverila v kateri kvadrant je polžek prišel. Torej bom preverjala kakšna je x in kakšna je y koordinata:

  • Če sta obe koordinati večji ali enaki 0, potem se bo polžek vračal najprej levo('L') toliko časa dokler ne bo x koordinata enaka 0 in nato navzdol('D') dokler ne bo y koordinata enaka 0.
  • Če je x koordinata manjša od 0 in y koordinata večja od 0, potem gre polžek najprej navzdol('D') toliko časa dokler ni y koordinata enaka 0 in nato levo('L') toliko časa dokler x koordinata ni enaka 0.
  • Če sta obe koordinati manjši od 0, potem se najprej vrača levo('L') toliko časa dokler je x koordinata manjša od 0 in nato navzgor('U') dokler je y koordinata manjša od nič.
  • Na koncu pa preverim še, če je x koordinata večja od 0 in y koordinata manjša od nič, potem se najprej vrača navzgor('U') toliko časa dokler ni y koordinata enaka 0 in nato levo('L') dokler ni x koordinata enaka 0. Na koncu te metode vrnemo niz navodil po katerih se polžek vrne.

Koda v C#

Metoda vracanje (testni primeri)

Na koncu testiram še metodo vracanje, ki mi vrne navodilo poti, po kateri se polžek lahko vrne, pri tem pa ne sme nikoli zaviti desno:

  • Najprej metodo testiram na praznem navodilu. V tem primeru mi metoda ne sme vrniti ničesar, saj smo še vedno v izhodišču.
  • Nato metodo testiram na navodilu, kjer se polžek premakne za tri mesta v desno. V tem primeru mi mora metoda vrniti navodilo, kjer mora polžek zaviti v levo za tri mesta.
  • Nato metodo testiram na primeru iz navodila naloge. V tem primeru je točka v katero je prišel polžek (1, 1). Da se polžek vrne v izhodišče, za eno enoto zavije v levo in za eno enoto navzdol ('LD').
  • Nato metodo testiram tudi na primeru, kjer je polžek prišel v tretji kvadrant (x<0 in y<0) (lahko bi testirala tudi, če bi prišel v katerega od ostalih kvadrantov), v tem primeru bo polžek zavil najprej na levo za toliko mest, kolikor je velikost koordinata x in nato navzgor za toliko mest, kolikor je velikost y koordinate. Tako bo polžek prišel v koordinatno izhodišče.

Testiranje v C#

Metoda vracanje (testiranje)

0%
0%