PALMA junior
Úloha o diskotéke

Autorské riešenie
[stiahni imp : py]

• Počet riešiteľov: 17 / 18= 94%

• Úspešnosť riešenia: 4,41 / 6 = 74 %

Pri riešení tejto úlohy bolo potrebné zvoliť vhodné parametre procedúry/funkcie:

• zoznam skladieb, ktoré máme k dispozícii,
• počet skladieb, ktoré majú zaznieť.

Jednotlivé skladby budeme reprezentovať napr. číslami 1, 2, 3... a na manipuláciu s nimi použijeme štruktúru zoznam.

Počet skladieb - ak máme splniť dané podmienky - musí byť aspoň rovný počtu skladieb, ktoré máme k dispozícii (podmienka "Každá skladba zaznie aspoň raz."), a zároveň nesmie byť väčší ako dvojnásobok počtu skladieb, ktoré máme k dispozícii (podmienka "Každá skladba zaznie najviac dva krát."). To, či parameter spĺňa tieto podmienky, môžeme ošetriť pomocou generovania výnimiek alebo pomocou podmienky if.

Prvá myšlienka riešenia sa zdá byť jednoduchá:

Ku skladbám, ktoré máme k dispozícii, pridáme chýbajúci počet skladieb (do počtu, ktorý sa požaduje) a náhodne ich zamiešame.

Dôležitým momentom je však podmienka, že skladba nesmie zaznieť hneď po sebe. Preto je potrebné takto vytvorený zoznam skontrolovať - porovnať dve po sebe idúce skladby a zvoliť vhodnú stratégiu, čo robiť v prípade, ak sú rovnaké.

V našom riešení zvolíme takýto postup:

Ak sa dve po sebe idúce skladby zhodujú (označme ich indexy v rámci zoznamu i a i+1), vymeníme druhú z nich s ďalšou, po nej nasledujúcou skladbou (teda skladbu s indexom i+1 vymeníme so skladbou i+2). Ak je skladba s indexom i+1 posledná v zozname, vymeníme ju s prvou skladbou zoznamu.

Keďže v špeciálnom prípade sa po tejto výmene (výmene posledného s prvým prvkom zoznamu) môže stať, že sa prvá a druhá skladba (s indexmi 0 a 1) budú zhodovať, porovnáme ešte tieto dve skladby a v prípade potreby zopakujeme výmenu skladieb s indexmi 0 a 1.

Ide o konkrétne o situáciu, keď k dispozícii máme dva skladby a chceme vygenerovať zoznam troch skladieb. Napríklad, v prvom kroku získame zoznam [2, 1, 1]. Po výmene získame zoznam [1, 1, 2], preto je potrebné ešte skontrolovať prvé dva prvky zoznamu, čím získame výsledný zoznam [1, 2, 1].

viem vytvor_playlist :zoznam :pocet
 urobtu "dlzka počet :zoznam 
 ak2 (nieje (zároveň (:pocet >= :dlzka) (:pocet <= 2 * :dlzka)))
 [vy "|Chybný počet skladieb, playlist nie je možné vytvoriť.|]
 [
 urobtu "playlist :zoznam
 ak2 počet :playlist < :pocet
  [urobtu "zoznam pomiešaj :zoznam
   opakuj :pocet - (počet :playlist)
    [urobtu "playlist veta :playlist prvy :zoznam
     urobtu "zoznam bezPrvého :zoznam]  
   urobtu "playlist pomiešaj :playlist
   opakuj počet :playlist
   [ak prvok počítadlo :playlist = prvok (počítadlo + 1) :playlist
     [ak2 počítadlo + 1 <> počet :playlist
      [urobtu "pomocna prvok (počítadlo + 1) :playlist
       urobtu "playlist nahraď (počítadlo + 1) :playlist prvok (počítadlo + 2) :playlist
       urobtu "playlist nahraď (počítadlo + 2) :playlist :pomocna
      ]
      [urobtu "pomocna prvok 1 :playlist
       urobtu "playlist nahraď 1 :playlist prvok (počítadlo + 1) :playlist
       urobtu "playlist nahraď (počítadlo + 1) :playlist :pomocna
      ]
     ]
    ]
    ak prvok 1 :playlist = prvok 2 :playlist
     [urobtu "pomocna prvok 1 :playlist
      urobtu "playlist nahraď 1 :playlist prvok 2 :playlist
      urobtu "playlist nahraď 1 :playlist :pomocna
     ]
    ]
  [urobtu "playlist pomiešaj :playlist]
  vy :playlist
 ]
 
koniec

# Python
import random


def vytvor_playlist(zoznam, pocet):
    if not(len(zoznam <= pocet <= len(zoznam) * 2):
        raise ValueError('Nesprávny počet skladieb.')
    playlist = zoznam.copy()
    if len(playlist) < pocet:
        random.shuffle(zoznam)
        playlist += zoznam[:(pocet - len(playlist))]
        random.shuffle(playlist)
        for i in range(len(playlist) - 1):
            if playlist[i] == playlist[i+1]:
                if i + 1 != len(playlist)-1:
                    playlist[i+1], playlist[i+2] = playlist[i+2], playlist[i+1]
                else:
                    playlist[i + 1], playlist[0] = playlist[0], playlist[i + 1]
        if playlist[0] == playlist[1]:
            playlist[1], playlist[2] = playlist[2], playlist[1]
    else:
        random.shuffle(playlist)
    return playlist


try:
    print(vytvor_playlist([1, 2], 3))
except ValueError as chyba:
    print(chyba)

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

Zaujímavé bolo, že každé odovzdané riešenie bolo originálne - niektorí z Vás použili na reprezentáciu playlistu zoznam, ďalší množinu či reťazec. Rovnako rôzne boli algoritmy tvorby playlistu - aj keď mali niektoré rovnaký základ, to dotiahnutie jednotlivých podmienok bolo veľmi rôznorodé.

Najčastejšou chybou bolo to, že ste sa pri generovaní playlistu úplne spoľahli na náhodu - z čoho sa napokon mohol stať nekonečný program. Napríklad, vyberali ste novú skladbu zo zoznamu dostupných, a testovali ste, či sa už v zozname nenachádza dva krát, prípadne či by sa pred ňou neocitla rovnaká skladba. Alebo ste pre danú skladbu, ktorú ste chceli vložiť do playlistu, generovali náhodnú pozíciu dovtedy, kým neboli splnené všetky podmienky.

Niektorí z Vás pochopili slovné spojenie "iný počet skladieb" ako "náhodný počet skladieb", a teda program pri každom spustení generoval rôzne dlhé playlisty. Takýto program je z hľadiska použ