Množice


Besede

besede, besede ... Kaj sploh je beseda? Osnovni delček komunikacije? Orožje? Zaporedje črk? Za nas bo beseda poljubno zaporedje znakov, torej niz!

1. podnaloga

Sestavi funkcijo podobna(beseda, sezBesed), ki kot argument sprejme besedo in kot rezultat vrne prvo med tistimi besedami iz sezBesed, v kateri se pojavi čim več črk, ki se pojavijo tudi v dani besedi. Teh črk je seveda lahko tudi 0 ;-) !Vsako ujemajočo se črko štejemo le enkrat, tudi če se v obeh besedah pojavi večkrat. Funkcija naj deluje tako, da ne razlikuje med malimi in velikimi črkami. Če take sploh besede ni, vrni None.

  >>> besede = ["ana", "berta", "cilka", "dani", "ema", "fanči", "greta", "hilda"]
  >>> podobna("merjasec", besede)
  'berta'
  >>> podobna("zmaj", besede)
  'ema'
  >>> podobna("Krava", besede)
  'berta'

Ana in krava se ujemata v eni črki, namreč črki a in ne v dveh, pa čeprav imata po dva a-ja (tudi če bi napisali ana). Opomba: vsaka podobnost med Berto in merjascem je zgolj naključna.

Uradna rešitev

def podobna(beseda, sezBesed):
    '''Katera  beseda v sezBesed ima največ skupnih črk z besedo `beseda`'''
    beseda = beseda.lower() 
    bs = set(beseda) # množica vseh črk (različnih seveda ;-) )
    naj_crk = -1
    najBeseda = None # nimamo še najboljše besede
    for enaBeseda in sezBesed:
        skupnih = len(bs & set(enaBeseda.lower())) # velikost preseka mniožic
        if skupnih > naj_crk: # smo našli boljšega kandidata?
            naj_crk = skupnih
            najBeseda = enaBeseda
    return najBeseda

2. podnaloga

Napiši funkcijo najraznolika(bes), ki kot argument prejme neprazen seznam nizov in kot rezultat vrne niz, ki ima največ različnih znakov. Male in velike črke upoštevaj kot iste znake - beseda "MamA" ima samo dva različna znaka. Če obstaja več besed z enakim številom različnih znakov, naj vrne zadnjo (glede na položaj v seznamu) med njimi.

  >>> besede = ["RABarbara", "izpit", "zmagA"]
  >>> najraznolika(besede)
  zmagA

Uradna rešitev

def najraznolika(sezBesed):
     '''Kateri niz v sezBesed ima največ različnih znakov'''
     najZnakov = 0
     for enNiz in sezBesed:
         crk = len(set(enNiz.lower())) # število različnih znakov
         if crk >= najZnakov: # boljši kandidat (= ker hočemo zadnjega!)
              najZnakov = crk
              najNiz = enNiz
     return najNiz

3. podnaloga

Dan je seznam besed. Napiši funkcijo sameRazličneČrke(sezBesed), ki vrne urejen (kot ureja sorted) seznam tistih besed, ki imajo vse črke različne. Pri tem upoštevaj le črke angleške abecede! Male in velike črke razlikujemo! Vsako besedo upoštevaj le enkrat. Morda prav pride

  >>> import string
  >>> string.ascii_letters
  'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

Zgled uporabe funkcije

  >>> besede = ["Rabarbara", "kralj", "Kok", "čmrlj!!", "11-isto", "zmaga", "kralj", "konec"]
  >>> sameRazličneČrke(besede)
  ['11-isto', 'Kok', 'konec', 'kralj', 'čmrlj!!']

Uradna rešitev

def ohraniČrke(niz):
    '''vrne niz, ki vsebuje le še črke angleške abecede.
    '''
    import string
    vseČrke = set(string.ascii_letters)
    novNiz = ""
    for znak in niz:
        if znak in vseČrke: # črka angleške abesede
            novNiz += znak
    return novNiz

def sameRazličneČrke(sezBesed):
     '''vrne po abecedi urejen seznam tistih besed, ki imajo vse črke različne.'''
     množicaNovih = set()
     for beseda in sezBesed:
         oklBeseda = ohraniČrke(beseda)
         crk = len(set(oklBeseda)) # število različnih znakov
         if crk >= len(oklBeseda): # različnih črkl je toliko kot vseh
              množicaNovih.add(beseda)
     novSeznam = list(množicaNovih) # iz množice v seznam
     return sorted(novSeznam)

4. podnaloga

Program

   import urllib.request
   naslov = "http://splasho.com/upgoer5/phpspellcheck" 
   naslov += "/dictionaries/1000.dicin"
   vir = urllib.request.urlopen(naslov)
   for vr in vir:
       vrstica = vr.decode()
       print(vrstica, end='')

izpiše po abecedi urejenih 1000 najpogostejših angleških besed Napiši funkcijo najraznolikaAngBeseda(), ki vrne po abecedi urejen seznam vseh tistih med temi 1000 najpogostejšimi angleškimi besedami, ki imajo največ različnih črk.

Uradna rešitev

def najraznolikaAngBeseda():
     '''Katere med pogostimi angl. besedami imajo največ različnih znakov'''
     import urllib.request
     naslov = "http://splasho.com/upgoer5/phpspellcheck" 
     naslov += "/dictionaries/1000.dicin"
     vir = urllib.request.urlopen(naslov)
     najZnakov = 0
     for beseda in vir:
         enNiz = beseda.decode()[:-1] # odstranimo \n
         crk = len(set(enNiz.lower())) # število različnih znakov
         if crk == najZnakov: # enakovredni kandidat
              najZnakov = crk
              najNizi.append(enNiz)
         elif crk > najZnakov: # boljši kandidat
              najZnakov = crk
              najNizi = [enNiz]
     return najNizi # urejanje ni potrebno, ker so že besede urejene

5. podnaloga

Napiši funkcijo vse_crke(beseda, črke), ki pove, ali množica crke vsebuje vse črke, ki se pojavijo v podani besedi. Pri tem sme množica vsebovati tudi črke, ki se v besedi ne pojavijo.

  >>> vse_crke("AMFITEATER", set(["A", "M"]))
  False
  >>> vse_crke("AMFITEATER", set(["A", "M", "F", "I", "T", "E"]))
  False
  >>> vse_crke("AMFITEATER", set(["A", "M", "F", "I", "T", "E", "R"]))
  True
  >>> vse_crke("AMFITEATER", set(["A", "M", "F", "I", "T", "E", "R", "X",
  "O", "B", "L"]))
  True

Uradna rešitev

def vse_crke(beseda, črke):
    '''Ali množica črke vsebuje vse črke, ki se pojavijo v besedi'''
    return not (set(beseda) - setrke))

Vislice

Naloga sposojena od tu in malček predelana.

1. podnaloga

Program

   import urllib.request
   naslov = "http://lokar.fmf.uni-lj.si/JAVNO/samostalniki.txt" 
   vir = urllib.request.urlopen(naslov)
   vse = vir.read().decode()
   print(vse[:297])

izpiše prvih nekaj samostalnikov, ki so na datoteki na ustreznem naslovu Sestavi funkcijo vrniSamostalnik(n), ki vrne n-ti samostalnik iz te datoteke. Če je n npr. 1012 in je na datoteki le 300 samostalnikov, dobimo 112 tega.

  >>> vrniSamostalnik(1)
  DOGODEK

Uradna rešitev

def vrniSamostalnik(n):
    '''vrne n-ti samostalnik z datoteke'''
    import urllib.request
    naslov = "http://lokar.fmf.uni-lj.si/JAVNO/samostalniki.txt" 
    vir = urllib.request.urlopen(naslov)
    vse = vir.read().decode()
    samostalniki = vse.split()
    koliko = len(samostalniki)
    return samostalniki[(n - 1) % koliko]

2. podnaloga

Napiši funkcijo kjeJeZnak(beseda, znak), ki vrne urejen seznam mest v besedi beseda, na katerih nastopa podana črka znak. Funkcija naj ne izpisuje ničesar, le rezultat naj vrača!

    >>> kjeJeZnak("PONUDNIK","N")
    [2, 5]
    >>> kjeJeZnak("RABARBARA", "R")
    [0, 4, 7]
    >>> kjeJeZnak("AMFITEATER", "O")
    []

Uradna rešitev

def kjeJeZnak(beseda, crka):
    '''seznam indeksov, kjer v besedi nastošpa črka'''
    mesta = []
    for i in range(len(beseda)):
        if beseda[i] == crka:
            mesta.append(i)
    return mesta

# krajša rešitev z izpeljanimi seznami - preštudiraj!
def kjeJeZnak(beseda, crka):
    '''seznam indeksov, kjer v besedi nastošpa črka'''
    return [i for i, c in enumerate(beseda) if c==crka]

3. podnaloga

Napiši funkcijo imaVseZnake(beseda, znaki), ki pove, ali množica znaki vsebuje vse črke, ki se pojavijo v besedi beseda. Opomba: množica sme vsebovati tudi črke, ki se v besedi ne pojavijo.

    >>> imaVseZnake("AMFITEATER", {"A", "M"})
    False
    >>> imaVseZnake("AMFITEATER", {"A", "M", "F", "I", "T", "E"})
    False
    >>> imaVseZnake("AMFITEATER", {"A", "M", "F", "I", "T", "E", "R"})
    True
    >>> imaVseZnake("AMFITEATER", {"A", "M", "F", "I", "T", "E", "R", "X", "O", "B", "L"})
    True

Uradna rešitev

def imaVseZnake(beseda, crke):
    '''ali množica znaki vsebuje vse črke, ki se pojavijo v besedi beseda'''
    for c in beseda:
        if not c in crke:
            return False
    return True

# z množicami gre enostavneje
def imaVseZnake(beseda, crke):
    '''ali množica znaki vsebuje vse črke, ki se pojavijo v besedi beseda'''
    return set(beseda) <=  crke

4. podnaloga

Napiši funkcijo pokaziZnake(beseda, znaki), ki kot argument sprejme besedo beseda in množico (set) črk znaki. Funkcijo mora vrniti besedo, v kateri so vse črke, ki ne nastopajo v množici znaki, spremenjene v pike.

    >>> pokaziZnake("PONUDNIK", {"O", "N"})
    '.ON..N..'
    >>> pokaziZnake("PONUDNIK", {"O", "I", "K"})
    '.O....IK'
    >>> pokaziZnake("PONUDNIK", set())
    '........'
    >>> pokaziZnake("PONUDNIK", {"P", "O", "N", "I", "K", "U"})
    'PONU.NIK'

Uradna rešitev

def pokaziZnake(beseda, crke):
    "vrne besedo, v kateri so vse črke, ki ne nastopajo v množici znaki, spremenjene v pike."
    bes = ""
    for c in beseda:
        if c in crke:
            bes += c
        else:
            bes += "."
    return bes

# z izpeljanimi seznami gre tudi v eni vrstici ...
def pokaziZnake(beseda, crke):
    "vrne besedo, v kateri so vse črke, ki ne nastopajo v množici znaki, spremenjene v pike."    
    return "".join([c if c in crke else "." for c in beseda])

5. podnaloga

Napiši igro "vislice". Pri tem uporabljajte funkcije, ki ste jih napisali prej. Igra poteka tako, da računalnik izbere naključno besedo iz datoteke s samostalniki. Nato izpisuje besedo tako, da črke, ki jih igralec še ni uganil, zamenja s piko. Igralec vnese znak (pri čemer pazite na to, da lahko vnaša tudi male tiskane črke - spremenite jih v velike). Če beseda vsebuje vnešeni znak, se ti znaki v besedi "razkrijejo". Če beseda ne vsebuje želenega znaka, pa igralec "izgubi eno življenje". V začetku ima igralec 6 življenj; življenja se izpisujejo za besedo, med besedo in številom življenj mora biti en presledek. Igre je konec, ko igralec bodisi ugane vse črke, ki jih vsebuje beseda, bodisi izgubi vseh šest življenj. V prvem primeru mora računalnik izpisati "Bravo!" v drugem pa "Konec, iskana beseda je RESITEV.", kjer namesto RESITEV izpise besedo, ki smo jo (neuspešno) ugibali. Uspešna igra naj bo videti takole:

    ...... 6
    a
    .A.... 6
    e
    .A.... 5
    i
    .A.... 4
    o
    .A..O. 4
    r
    .A..O. 3
    l
    .A..O. 2
    k
    .A..O. 1
    t
    .A.TO. 1
    s
    .ASTO. 1
    n
    NASTO. 1
    p
    NASTOP 1
    Bravo!

Neuspešna pa bo takšna.

    ....... 6
    a
    ....... 5
    b
    ....... 4
    c
    ....... 3
    d
    D...D.. 3
    e
    D...DE. 3
    f
    D...DE. 2
    g
    D.G.DE. 2
    h
    D.G.DE. 1
    i
    Konec, iskana beseda je DOGODEK.

NALOGA NIMA TESTA

Uradna rešitev

import random
def igra():
    kolikoJihJe = 8175 # smo pokukali ...
    beseda = vrniSamostalnik(random.randint(1, kolikoJihJe))
    izbrane = set()
    zivljenj = 6
    while zivljenj:
        print(pokaziZnake(beseda, izbrane), zivljenj)
        if imaVseZnake(beseda, izbrane):
            print("Bravo!")
            break
        crka = input().upper()
        if not kjeJeZnak(beseda, crka):
            zivljenj -= 1
        izbrane.add(crka)
    if not zivljenj:
        print("Konec, iskana beseda je {}.".format(beseda))

Gimnazija

Janko ne mara matematike, je pa navdušen programer. In ker je v šoli dobil cel kup matematičnih nalog iz množic, jih bo rajši rešil tako, da bo napisal ustrezne programe v Pythonu.

1. podnaloga

Sestavi funkcijo vrniTri(a, b), ki vrne nabor (A, B, C), kjer so A, B in C naslednje množice:

$$A = \{30n; n \in \mathbb{N}, n < a\}$$ $$B = \{n^3; n \in \mathbb{N}, 5n < b\}$$ $$C = \{5n; n \in \mathbb{N}, n^3 < a * b\}$$

Pri tem vemo, da velja $a \in \mathbb{N}$ in $b \in \mathbb{N}$

Uradna rešitev

def vrniTri(a, b):
    '''vrne nabor treh matematično opisanih množic'''
    A = set()
    for n in range(1, a):
        A.add(30*n)
    B = set()
    n = 1
    while 5*n < b:
        B.add(n*n*n)
        n += 1
    C = set()
    n = 1
    while n*n*n < a*b:
        C.add(5*n)
        n += 1
    return (A, B, C)

2. podnaloga

Sestavi funkcijo računi(A, B, C), ki vrne nabor (X, Y, Z), kjer so X, Y in Z naslednje množice:

$$X = A \cap B \cap C$$ $$Y = A \setminus (B \cup C)$$ $$Z = (A \setminus B) \cup C$$

  >>> računi({2, 4, 6, 8, 10}, {1, 2, 3, 4}, {4, 6, 5})
  ({4}, {8, 10}, {4, 5, 6, 8, 10})

Uradna rešitev

def računi(A, B, C):
    '''Računamo z množicvami ...'''
    X = A & B & C
    Y = A - (B | C)
    Z = (A - B) | C
    return (X, Y, Z)

3. podnaloga

Sestavi funkcijo kartezični(A, B), ki vrne nabor (X, Y), kjer sta X in Y množici:

$$X = A \times B$$ $$Y = B \times B$$

  >>> kartezični({1, 2, 3}, {3, 4})
  ({(1,3), (1,4), (2,3), (2,4), (3,3), (3,4)}, {(3,3), (3,4), (4,3), (4,4)})

Uradna rešitev

def kartezični(A, B):
    '''vrne nabor (X, Y), kjer X = A x B in Y = B x B'''
    X = set()
    for el1 in A:
        for el2 in B:
            X.add((el1, el2))
    Y = set()
    for el1 in B:
        for el2 in B:
            Y.add((el1, el2))            
    return (X, Y)

4. podnaloga

Dane so množice $$A = \{x; x \in \mathbb{N} \land x < a\}$$ $$B = \{x; x \in \mathbb{N} \land x > b\}$$ $$C = \{2a + 1; a \in \mathbb{N}\}$$ Sestavi funkcijo vrniD(a, b), ki vrne $$D = (A \cap B) \setminus C\prime$$

  >>> vrniD(20, 13)
  {15,17,19}

Uradna rešitev

def vrniD(a, b):
    '''A = {x, x € N & x < a)
       B = {x, x € N & x > b)
       C = {2a + 1, a € N}
       D = (A /\ B) - C'
    '''
    D = set()
    # v preseku so naravna števila med b in a
    # zaradi - C' ohranimo le liha števila, razen 1! 
    for x in range(b + 1, a):
        if x % 2 == 1:
            D.add(x)
    # znebimo morebitne 1
    D.discard(1) # ne smemo uporabiti remove!
    return D

Mirko si želi dekle

1. podnaloga

Mirko (saj veste kateri - tu je cel film o njem si ogleduje spisek vseh deklet, ki so mu všeč:

Ker sta s Slavkom tudi po vojni ostala "nerazdvojna druga", Mirko ne želi hoditi z nobeno od Slavkovih bivših deklet. Slavko mu je poslal spisek svojih bivših.

Pomagaj Mirku in sestavi funkcijo toBoMojeDekle(spisekKandidatk, spisekSlavkovih) ki dobi dva seznama in vrne po abcedi urejen seznam deklet, med katerimi bo izbiral Mirko. A šarmerja, kot sta, imata izjemno dolga spiska. Zato bo "enostavna" rešitev

   for dekle in spisekKandidatk:
      if dekle not in spisekSlavkovih:
          kandidatke.append(dekle)

prepočasna. Sestavi torej metodo, kjer ne boš uporabil zanke (ne while in ne for, seveda pa tudi ne rekurzije)

   >>> toBoMojeDekle(['Jožica', 'Marjetka', 'Anja', 'Petra', 'Marija'],
                     ['Cilka', 'Petra', 'Pepca', 'Francka', 'Marija'])
   ['Anja', 'Jožica', 'Marjetka']

Uradna rešitev

def toBoMojeDekle(sezKand, sezSlavko):
    '''Vrne seznam možnih deklet za Mirka.
       Dejansko vrne seznam elementov tistih iz sezKand, ki
       niso v sezSlavko '''
    mnoMirko = set(sezKand)
    mnoSlavko = set(sezSlavko)
    katere = mnoMirko - mnoSlavko # razlika množic
    return sorted(katere) # želimo urejen seznam

Slovenske besede

1. podnaloga

Na http://bos.zrc-sazu.si/sbsj.html je 354.205 različnih besed iz gesel zbirke Besede slovenskega jezika. Program

   import urllib.request
   naslov = "http://bos.zrc-sazu.si/sbsj.html" 
   vir = urllib.request.urlopen(naslov)
   vse = vir.read().decode()
   besede = vse.split('\n')[15:]

poskuša iz te datoteke narediti seznam vseh besed. Ampak kot vidimo, smo na začetku odrezali premalo. Prav tako se nismo znebili konca ... Sestavi funkcijo vrniBesedo(n), ki vrne n-ti besedo iz te datoteke. Pri tem naj se n obnaša kot indeks v seznamu!

    >>> vrniBesedo(354204)
    žžžžk
    >>> vrniBesedo(354205)      
    Traceback (most recent call last):
    ...
    IndexError: list index out of range
    >>> vrniBesedo(0)
    a
    >>> vrniBesedo(-1)
    žžžžk

Uradna rešitev

def odst(niz):
    '''Iz niza odstrani <br>\r'''
    return niz[:-5]

def vrniBesedo(n):
    '''Vrne n-to besedo. Rešitev predpostavlja, da se besede začno v 15. vrstici in nehajo 13 vrstic pred koncem.
       Taka struktura je bila konec l. 2015
       Namenoma ni uporabljano iskanje prve (a) oz. zadnje besede ('žžžžk')
    '''
    import urllib.request
    naslov = "http://bos.zrc-sazu.si/sbsj.html" 
    vir = urllib.request.urlopen(naslov)
    vse = vir.read().decode()
    besede = vse.split('\n')[15:-13]
    slečene = list(map(odst, besede))
    return slečene[n]

2. podnaloga

Sestavi funkcijo sameRazlične(zač), ki vrne množico vseh tistih slovenskih besed, ki se začno z nizom zač in jih sestavljajo same različne črke!

   >>> sameRazlične('mate')
   {'mate', 'maternik', 'materski', 'matec', 'matenski',
    'matek', 'maten', 'matevž', 'maternski', 'mater', 'materin'}

Uradna rešitev

def odst(niz):
    '''Iz niza odstrani <br>\r'''
    return niz[:-5]

def vrniBesede():
    '''Vrne vse besede is SSKJ. Rešitev predpostavlja, da se besede začno v 15. vrstici in nehajo 13 vrstic pred koncem.
       Taka struktura je bila konec l. 2015
       Namenoma ni uporabljano iskanje prve (a) oz. zadnje besede ('žžžžk')
    '''
    import urllib.request
    naslov = "http://bos.zrc-sazu.si/sbsj.html" 
    vir = urllib.request.urlopen(naslov)
    vse = vir.read().decode()
    besede = vse.split('\n')[15:-13]
    slečene = list(map(odst, besede))
    return slečene

def enakeČrke(niz):
    '''Ali je niz sestavljen iz samih različnih črk'''
    return len(niz) == len(set(niz))

def sameRazlične(zač):
    '''Vrne množico tistih slovenskih besed, ki so sestavljene i
       z samih enakih črk in se začno z zač'''
    vseBesede = vrniBesede()
    mnBesed = set()
    for beseda in vseBesede:
        if beseda.startswith(zač) and enakeČrke(beseda):
            mnBesed.add(beseda)
    return(mnBesed)