Secret Santa challenge noslēdzies!

Vispār kaut kā nedaudz dīvaini sanāca ar pasākumu, kurš tika pie nosaukuma ‘Secret Santa challenge‘. Kad es attiecīgo ierakstu rakstīju, nebiju īsti izdomājis ko vēlētos redzēt noslēgumā. T.i. – mērķis bija neskaidrs. Zināju, ka būtu interesanti redzēt citu programmētāju pieeju vienas un tās pašas problēmas risināšanai. Tā kā pats parasti runāju par PHP, tad sagaidīju, ka šī valoda būs plašāk pārstāvēta (ja vispār kāds piedalīsies). Bet izrādījās, ka Secret Santa challenge tapa par poliglotu salidojumu. 13 valodas (bija 14, bet viens risinājums atsaukts). Daudzām pa 1 risinājumam. Populārākā Python (4 risinājumi), bet otrā un trešā vieta dalīta starp C# un PHP.

Lielu daļu no iesniegtajiem risinājumiem es pat nespētu novērtēt un saprast cik pieeja laba, jo attiecīgajā valodā neorientējos. Tādēļ nevērtēšu arī tās valodas, kuras saprotu. Tā vietā vienkārši dodu sarakstu ar iesniegtajiem risinājumiem un ļauju jums pašiem skatīties, mācīties, vērtēt. Vienu brīdi bija ienākusi doma, ka varētu taisīt kādu balsošanu par smukāko risinājumu. Bet to atmetu. Ja kādam ir vēlme izteikt uzslavas, tad komentāros.

Vēl tapa skaidras vairākas lietas. Komentāri nav labākā vieta kur iesniegt kodus. Pazudis formatējums, reizēm daļa no koda utt. Gist, Pastebin, vpaste un tamlīdzīgi resursi ir labākā vieta kodam. Ja kāds vēl kādreiz taisa līdzīgu pasākumu, iesaku nedaudz precīzāk definēt uzdevumu. Ņemot vērā daudzos komentārus un manus skaidrojumus tur, nebiju uzdevuma augstumos šajā sakarā.

Ja runājam par pašu uzdevumu, tad tas bija interesants vairāku iemeslu dēļ. Lai gan sākumā tas šķiet elementārs, tā gluži nav. Protams, tas nav arī sarežģīts. Bet viņam ir pāris knifi, kurus ir jāparedz. Neesmu pārbaudījis vai iesniegti varianti ar to tiek galā vai nē. Bet tā kā vairākiem kodiem tika iesniegti labojumi, ir skaidrs, ka gluži triviāli nebija. Izmantotās pieejas bija vairākas. Piemēram, sakārtot visas personas vienā sarakstā un tad iet cauri, paņemot blakus esošos kā dāvinātāju un apdāvināmo. Ja pamana aizliegtu kombināciju blakus, pārģenerē sarakstu. Otrs variants (ar dažādām variācijām), ir taisīt divus sarakstus. Viens ar saņēmējiem, viens ar dāvinātājiem. Tad ejot cauri vienam un otram sarakstam sameklēt atbilstošos variantus. Ja izmanto divu sarakstu pieeju un ar katru izvēlēto pāri tos samazina par 1, tad jāņem vērā, ka beigās var uztrāpīt uz vienu no divām problēmām. Pirmā – katrā sarakstā paliek pa 1 personai (tātad A un A). Otrā – katrā sarakstā paliek pa 2 personām, kuras ir aizliegtais pāris. Un šajā gadījumā vajadzētu pāru meklēšanu sākt no jauna. Cik skatījos, citi to dara. Citi izmet paziņojumu ka īsti nesanāca. Es teiktu, ka skriptam vajadzēja pašam automātiski saprast, ka nav sanācis un veikt pārģenerēšanu. Pieļauju, ka ir arī citas pieejas, bet kā jau teicu – neesmu poliglots.

Iesniegtie varianti sakārtoti alfabētiskā secībā bez vērtējuma no manas puses. Ja kāds bija iesniedzis kodu komentārā vai caur email, tad attiecīgo kodu es ieliku savā Gist kontā ar atsauci uz personu. Ja ir vēlme samainīt uz kādu savu saiti – raksti komentāros.

Šur un tur pavīdēja jautājums par to, kas tad balvā… Nekas taustāms: citu programmētāju atzinība un/vai iespēja apgūt kādu jaunu pieeju attiecīgās problēmas risināšanai!

C#
Mārcis Pinnis https://gist.github.com/Endijs/946addb84f54b24d8433
Pēteris https://gist.github.com/pdonald/85a0877d691e48de01bb (saitē redzams C# un Rust)
Valters http://vpaste.net/Dk7XD

Clojure
Raitis Stengrevics https://gist.github.com/daGrevis/b4b002fe13fec7c7b043

Haskell
Aleksejs Ivanovs https://gist.github.com/ivanovsaleksejs/0048d95401ffa459cd4d

JavaScript
Mareks http://jsfiddle.net/chendler/zx5kmnop/ un http://jsfiddle.net/chendler/gxycxfeg/
Jānis http://pastebin.com/Shd1sqse

Pascal
Mr. V http://vpaste.net/yZE28

Perl
Ramūns Usovs https://gist.github.com/ramuuns/96aa39bdacf96f290f64

PL/SQL
Andris Buhanovskis http://pastebin.com/kFUQh41p

PHP
Briedis https://gist.github.com/briedis/7c5d7da87b6612355e8b
Endijs Lisovskis https://gist.github.com/Endijs/832a1b952f32b48e1e66
Kaspars Foigts https://gist.github.com/laacz/10423b5c3cabef780494

Python
Aigars Mahinovs https://gist.github.com/aigarius/2c99ede12539ca536849
Aija https://gist.github.com/AijaLi/d1bf82baf4a31f36acc6
Fedja https://gist.github.com/anonymous/d1d5aa99efd263597206
Ieva https://gist.github.com/IevaZarina/e48f71d096a59a903a42

R
Aleksis Jurševskis https://gist.github.com/Endijs/22f397dfa8008d69e580 (ar piebildi: Ceru, ka kāds izdomās variantu bez atkārtotas ģenerēšanas, man pietrūka pacietības.)

Ruby
Gatis Tomsons https://gist.github.com/gacha/466a9c45e7386283f5f3

Rust
Pēteris https://gist.github.com/pdonald/85a0877d691e48de01bb (saitē redzams C# un Rust)

Swift
Jānis Kiršteins http://pastebin.com/haPXSsp5

23 comments

  1. Neesmu programmētājs, bet riskēšu teikt, ka Aigara variants ir eleganti kompakts un lasāms salīdzinot ar citām valodām :)

  2. Aigara risinājums ir smuks (kaut gan tā validācija varētu būt īsāka). Bet cik sapratu no uzdevuma – ja Jānis nevar dāvināt Līgai, tad arī Līga nevar dāvināt Jānim. Aigara kods šo neparedz.

    1. Kā rūdīts programmists, es teikšu tā – tā ir fīča! Ja ir aizliegts gan A->B, gan B->A tad manā risinājumā to viegli realizēt iekļaujot aizliegto sarakstā šos divus ierakstus, bet ja ir aizliegts A->B, bet B->A ir pieļaujams, tad mans risinājums piedāvā papildus funkcionalitāti ;)

        1. Piekrītu, neesmu .py pārzinātājs, bet domāju, ka no 6 un 7 rindiņas varētu izvairīties, izmantojot do … while (nosacījums), while vietā.

  3. No Clojure risinājuma: “Brute-force solution with side effects. Problem is NP-complete so sorry, but not sorry.:”

    Kāpēc NPC? Raiti, vai vari, lūdzu, paskaidrot sīkāk?

        1. Tam pašam manam risinājumam vidējais complexity ir apmēram O(3n), jeb O(n). Konstantā laikā šo algoritmu uzrakstīt nav iespējams, bet ir pilnīgi pietiek ar vidējstatisko.
          Es domāju, ka lielāka daļa šeit publicēto risinājumu izpildās lineārā laikā, un vidējais būs tas pats 3n. Un pat ja būtu vidējais 100n, teorētiski tas ir labāk par n^2 (cerams, ka nav jāskaidro kāpēc).

          Tajā linkā cilvēks izmantoja nepareizu risinājumu, jo tas nepareidz visus gadījumus. Tas ir, viņa algoritms nevar saģenerēt visas derīgas kombinācijas. Un viņa algoritms ir NP, bet to uzdevums neprasa.

        2. O nav vidējais compleksity, bet gan maksimālais. Sliktākais gadījums iestājas tad, ja blacklistā ir tik daudz pāru, ka ir būtībā tikai viena derīga kombinācija. Lielākā daļa šeit publicēto algoritmu tādā situācijā izpildītos gandrīz bezgalīgi ilgi, jo tipiskās random funkcijas nav pilnīgas, t.i. tās negarantē ka tās izsaucot daudz reižu tiks uzģenerēti visi iespējamie varianti.

        3. Laikam nepareizi izteicos. Ja piemēram algoritmā random aizvietot ar kādu increment, tad laikam visi šeit publicētie algoritmi beigās saģenerēs visus valīdus masīvus. Tajā linkā cilvēks izmantoja kodu, kas neģenerētu šajā gadījumā visus validus variantus.
          Par complexity – es to 3n dabuju izejot no tā, ka slikto pāru skaits ir 3. un tas ir diezgan aptuvens.
          Jebkurā gadījumā, uzdevums nav NP, un laiks ir lineārs pat tavā aprakstītā worst case.

  4. Protams, par to vēl var pastrīdēties, bet es nevarēju nekādi izdomāt kā uzrakstīt algoritmu, kas izpildītos jebkādā konstantā laikā.

    Ā, un side effects nozīmē, ka nododot X šai funkcijai, vienmēr atpakaļ saņemšu Y. Tā nav, jo funckija izmanto shuffle, kas ir ar side effects, tā kā manai funckijai arī ir side effects.

    1. 1) Aizliegto pāru sarakstā jābūt norādēm uz objektiem cilvēku sarakstā – ietaupa atmiņu, nav jārisina kļūdaini ievadītie vārdi, juceklis ar vairākiem Jāņiem kolektīvā utt…
      2) Saģenerējam visas permutācijas, kuru skaits ir zināms (nav lielu problēmu uzrakstīt pašam vai uzgūglēt iterējošu algoritmu, lai nebūtu bezgalīgi jāizmanto shuffle – piemēram http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list).
      3) Izfiltrējam visas permutācijas un atmetam nederīgās.
      4) sašaflojam atlikušās derīgās.
      5) kamēr ir, dodam lietotājam pirmo ārā, ja nepatīk, dodam nākamo.

      Nekad neiteresēsies mūžīgi un vienmēr izdos kaut kādu rezultātu diezgan konstantā laikā.

      1. Nākamā optimizācija:
        Pārbaudam, vai permutācija derēs iterējošā algoritma vidū. (tb, ja ir A, B, C, D, E un aizliegtais pāris AB, tad redzam, ka AB, BC, CD, DA nederēs un nemaz neģenerējam pārējās kombinācijas, piem. (AB, BD, DC, CA), zinot, ka tās būs nederīgas).

  5. Un kur ir pieejams vismaz viens gatavs rezultāts – gala lietošanai neprogrammētājiem.

    1. Nesmīdini :) Īstiem programmētājiem 90% pavadītā laika pie problēmas rezultāts ir vismaz par 90% gatavs :) Un te visi ir par 90% gatavi risinājumi, pie kuriem vajag vēl 10x vairāk laika pavadīt, lai sapucētu sīkumus un tos varētu arī neprogrammētājs lietot :)

  6. Provēju šodien pielietot scriptu un secināju, ka lielākā daļa (mans tai skaitā) darbojas tikai ja ziemassvētkus svin pāra skaitlis viesu, kas manā gadījumā nederēja.

    1. Manam it kā vajadzētu strādāt arī ar nepāra skaitli. Nosacījumos speciāli biju licis nepāra skaitli, lai skripti mācētu ar šādu situāciju tikt galā. Pats gan skriptus neesmu pārbaudījis, tā ka nezināšu, kurš māk un kurš nē.

Atbildēt

Jūsu e-pasta adrese netiks publicēta.

This site uses Akismet to reduce spam. Learn how your comment data is processed.