PALMA junior, Programovanie, ALgoritmy, MAtematika, súťaž pre mladých programátorov v Imagine

	PALMA junior

Úloha o o skladaní reťazcov

Autorské riešenie
[stiahni imp : py]

Počet riešiteľov: 2 / 15 = 13,3 %
Úspešnosť riešenia: 5 / 6 = 83,3 %

Úloha o skladaní reťazcov vychádza reálneho procesu, ktorý sa anglicky nazýva assembly. Autorské riešenie predpokladá, že zo vstupných sekvencií existuje len jedno možné pospájanie, pričom sa použijú všetky vstupné sekvencie. Vstupné sekvencie sú uložené v zozname. Tento zoznam však bude rad, čo je dátová štruktúra FIFO (First In, First Out). Znamená to, že sú povolené 2 operácie: vloženie prvku na poslednú pozíciu a výber prvku na prvej pozícii.

Úlohu riešili 2 riešitelia. Obaja ju riešili v Python-e, pričom jeden vyriešil celú úlohu správne. Druhému riešiteľovi fungoval program správne len v prípade, ak boli vstupné reťazce zoradené tak, aké má byť výsledné pospájanie. Maximálny počet bodov za úlohu bolo 6.

V autorskom riešení má funkcia assembly 2 parametre. Prvým je zoznam vstupných sekvencií a druhým je počet písmen, na základe ktorých vieme spojiť 2 reťazce.

V prvom kroku si vyberieme prvý reťazec zo zoznamu a uložíme ho do pomocnej premennej, ktorá bude reprezentovať výsledný reťazec. Na sleduje cyklus while (kým), ktorý bude bežať dovtedy, kým sa nepospájajú všetky reťazce, čiže vstupný zoznam nebude prázdny.

V každej iterácii cyklu while vyberieme zo zoznamu prvú sekvenciu a zistíme, či ju nemôžeme pripojiť na pravú alebo ľavú stranu výsledného reťazca. Ak áno, pripojíme ju a ak nie, tak sekvenciu vložíme na koniec zoznamu. Takýmto spôsobom sa po určitom počte krokov pospájajú všetky vstupné sekvencie do výslednej sekvencie.

Poznámka k riešeniam: Riešenie v Python-e je jednoduchšie a prehľadnejšie ako v Imagin-e.

;Imagine logo
viem assembly :zoznam :n
urobTu "ret prvy :zoznam
urobTu "zoznam bezPr :zoznam
urobTu "velkostZoz pocet :zoznam

kym [:velkostZoz > 0] [
    urobTu "pom prvy :zoznam
    urobTu "zoznam bezPr :zoznam
    urobTu "d pocet :pom

    urobTu "x :ret
    urobTu "zac "
    opakuj :n [
    urobTu "zac (slovo :zac prvy :x)
    urobTu "x bezPr :x
]

urobTu "x :pom
urobTu "kon "
urobTu "y :d-:n
urobTu "z 1
opakuj :d [
    ak :z > :y [
      urobTu "kon (slovo :kon prvy :x)
    ]
    urobTu "x bezPr :x
    urobTu "z :z+1
]

ak2 :zac = :kon[
    opakuj :n [
      urobTu "ret bezPr :ret
    ]
    urobTu "ret (slovo :pom :ret)
][
    urobTu "d pocet :ret
    urobTu "x :pom
    urobTu "zac "
    opakuj :n [
      urobTu "zac (slovo :zac prvy :x)
      urobTu "x bezPr :x
    ]

    urobTu "x :ret
    urobTu "kon "
    urobTu "y :d-:n
    urobTu "z 1
    opakuj :d [
      ak :z > :y[
        urobTu "kon (slovo :kon prvy :x)]
        urobTu "x bezPr :x
        urobTu "z :z+1
      ]

    ak2 :zac = :kon [
      opakuj :n [
        urobTu "pom bezPr :pom
      ]
      urobTu "ret (slovo :ret :pom)
    ][
      vlozPosledny :pom :zoznam]
    ]
    zobraz :ret
]
koniec

#Python
#vstupne parametre: zoznam sekvencii, pocet pismen na zaklade ktorych spajame retazce
def assembly(zoznam,n):
    #vyberieme prvy retazec zo zoznamu
    ret = zoznam.pop(0)
    while len(zoznam) > 0:
        #vyberieme prvy retazec zo zoznamu
        pom = zoznam.pop(0)
        d = len(pom)
        #zistime, ci ho mozeme pripojit na lavu stranu
        if ret[0:n] == pom[d-n:d]:
            #ak ano, pripojime
            ret = pom[0:d-n] + ret
        #ak nie
        else:
            d = len(ret)
            #zistime, ci ho mozeme pripojit na pravu stranu
            if ret[d-n:d] == pom[0:n]:
                #ak ano, pripojime
                ret = ret[0:d-n] + pom
            #ak nie, vlozime ho na koniec zoznamu
            else:
                zoznam.append(pom)
    #vysledny retazec vratime
    return ret

retazce = []
ret = []
f = open('retazce.txt','r')
for line in f:
    retazce.append(line)
f.close()
f = open('celeRetazce.txt','a')
for i in retazce:
    ret = i.split(" ")
    ret.pop()
    f.write("%s\n" % assembly(ret,4))

Vaše zaujímavé riešenia a najčastejšie chyby

Ako už bolo spomínané v úvode, úlohu riešili 2 riešitelia. Obidve riešenia boli riešené iným spôsobom ako autorské riešenie. Musím vyzdvihnúť, že riešenia boli celkom prehľadné a hlavne dobre okomentované.

PALMA junior

Úloha o o skladaní reťazcov