Sivulla https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=junar on annettu ohjelmointitehtävä, jota en saanut tehtyä. Yritin laskea, paljonko kukin vaihto pienentää keräyskierroksia. Jostain syystä tarkastin sanoo, että
Virhe rivillä "50 23 7"!
Miksi koodini osoitteessa https://pastecode.xyz/view/91e2323a antaa väärän tuloksen?
Putkaposti junanrata ei onnistu
Anonyymi
23
57
Vastaukset
- Anonyymi
onko liikaa sinolia jo ryypiskelty? seillä sainaan yksiöissä.
- Anonyymi
Lopetitko tuohon virheeseen?
Minittäin pahin virhe löytyi riviltä:
(100000, 50104, 16814)
Aikaa tuon löytämiseen meni:
real 4m32,457s
Olet Python taituri, ja synnynnäinen nero.
T. Urpo- Anonyymi
Kyllä ohjelma laskee kaikki tapaukset, mutta Ohjelmointiputkassa olevan tarkistimen mukaan arvot ovat pielessä. En vaan keksi tapaa debugata virhettä. Neroudesta en tiedä. Koetin vain vääntää eri tapoja tehtävään. Lopulta löytyi sellainen, joka kertoo ainakin alkupään arvoilla, miten homma toimii. Mutta ehkä noissa if-lauseissa on joku ehto pielessä.
Tuo algoritmi ei taida toimia, sillä se on vain yksi luuppi [1..n] ja kasvattaa vastausta korkeintaan yhdellä joka kierros.
Täytyy katsoa jokaiselle mihin paikkoihin siirrettäessä se vähentää kierroksia (kutsutaan niitä nyt toConsider[i], kun minä koodissani tein).
Sen jälkeen käydä ne uudestaan läpi ja nyt sisäluupissa käydä toConsider[i] läpi ja katsoa vähentääkö myös sen vastapari (ja jos vastapari on vierekkäinen luku, niin silloin dropsi ei ole kuin 1, joten niitä ei huomioida). Tämä on nyt mahdollista, koska jokaiselle on löydetty ne paikat.
ToConsider[i]:n tallentamiseen kannattaa käyttää joukkoa, joka ottaa välejä kokonaislukuja (IntvalSet). Jokainen toConsider[i] koostuu korkeintaan kahdesta välistä, joten niiden itse välien käsittelyä ei enemmin tarvitse optimoida.
Muuten, kannattaa ehdottomasti vain kerran laskea nuo lista.index():t kaikille ja tallentaa ne muistiin (minulla: poss). Se nopeuttaa huomattavasti! Pieni vaara on että menee ajatuksissa indeksit ja itse luvut sekaisin, mutta kun sen joka kerta miettii, niin pitäisi selvitä.
Tässä minun koodini, siellä on vielä kommentteja välissä: https://membolicsythod.home.blog/2020/01/16/junarata-tehtava/
Se on Python 2.7:aan tehty, mutta saattaa olla 3:sta sellaisenaan (jos ei printtien ympäriltä unohtunut sulkeita, joku Counterin metodi saattaa olla vähän eri, mutta se nyt olikin vain tuolla random-testeissä)
[Joo, mä käytän yhä Python 2:sta, ja lisäksi vielä Windows 7:aa!]
Se ratkaisee kaikki tapaukset, mutta viimeinen vei 19 minuuttia (voi minun koneraasua :D)
--
Jos satunnaista n-permutaatiota mietitään, niin odotettu kierrosten määrä on n/2, sillä jokainen luku k tuottaa uuden kierroksen, joss poss[k 1] < poss[k], ja satunnaisessahan tämä tapahtuu 50/50.
2-score vaihtojen odotusarvo näyttäisi olevan noin (nC2)/30. Jakauma n=100:lle näyttäisi tältä: https://aijaa.com/7lU8mg , ehkä rajalla Gammajakauma(?)- Anonyymi
Ota välillä sinolia,,,
- Anonyymi
Niin. Ajattelin, että yksi silmukka riittää. Siis tarkastelen lukukolmikkoja muotoa i, i 1 ja i 2. Näiden keskinäinen järjestys määrää, miten kierroksia vähenee. Ehkä sen saisi jotenkin toimimaan, kun ehtolauseet olisivat oikein.
Joo, mutta jotenkin se on laskettava kuinka moneen paikkaan siirtämällä kukin tuottaa 2 kierroksen parannuksen. (Se on yleensä yli 1: vaihdettavien parien määrä on yli n, yleensä about 1/60*n(n-1).) Ehkä niitä varmasti vääriä voisi jotenkin karsia valmiiksi pois. Mutta joka tapauksessa, kun ratkaisu on noin kolmaskymmenesosa kaikkien parien määrästä, ja ne yksi kerrallaan lasketaan, niin O(n^2) -algoritmihan tuo on joka tapauksessa.
- Anonyymi
minkkilaukku kirjoitti:
Joo, mutta jotenkin se on laskettava kuinka moneen paikkaan siirtämällä kukin tuottaa 2 kierroksen parannuksen. (Se on yleensä yli 1: vaihdettavien parien määrä on yli n, yleensä about 1/60*n(n-1).) Ehkä niitä varmasti vääriä voisi jotenkin karsia valmiiksi pois. Mutta joka tapauksessa, kun ratkaisu on noin kolmaskymmenesosa kaikkien parien määrästä, ja ne yksi kerrallaan lasketaan, niin O(n^2) -algoritmihan tuo on joka tapauksessa.
Jos hyvin huonosti tai toisin sanoen hyvin perältä löytyy tuo pienin kierrosmäärä, saattaa ratkaisun löytyminen kestää minun koneella yli 729 vuotta, näin pahimmillaan.
Tähän tulokseen pääsin kun ajoin tuon junar9.in tiedoston läpi paikkoja vaihtelematta, jolloin kierroksia tuli 25057 kpl ja tuohon tuhlaantui aikaa reilut 4 sekuntia (real 0m4,602s).
Näin saatua kierrosmäärää voidaan pitää maksimi kierrosmääränä, joka vähenee jokaisen paremman tuloksen aikaansaamana. Eli python Scriptin suoritus katkaistaan siihen kun MAX kierrosmäärä ylittyy, näin säästetään systemaattisen läpikäynnin aikaa. Laskettu aika (729 vuotta) lyhenee sitä enemmän mitä varhaisemmassa vaiheessa törmätään pieneen kierrosmäärään, eli oikeaan osuneeseen taulujen vaihtoon.
jos tauluja olisi 3 niin vaihtoja olisi 3
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 2 <-> 3
jos tauluja olisi 4 niin vaihtoja olisi 6
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 2 <-> 3
5 ) 2 <-> 4
6 ) 3 <-> 4
jos tauluja olisi 5 niin vaihtoja olisi 10
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 1 <-> 5
5 ) 2 <-> 3
6 ) 2 <-> 4
7 ) 2 <-> 5
8 ) 3 <-> 4
9 ) 3 <-> 5
10 ) 4 <-> 5
Näin ei tule turhia vaihtoja. Mutta siitä huolimatta systemaattinen taulujen vaihto tuottaa 100 000 taulun kanssa 499 9950 000 vaihtoa. Nyt meillä on tarpeeksi tietoa laskea maksimi aika tehtävälle seuraavasti:
1 Asetelma vie 4,602 sekuntia
100000 taulun systemaattinen taulujen vaihto tarjoaa 499 9950 000 vaihtoehtoa joten
499 9950 000 x 4,602 sekuntia = 23009769900 sekuntia
23009769900 / 60 = 383496165 minuuttia
383496165 / 60 = 6391602,75 tuntia
6391602,75 / 24 = 266316,78125 vuorokautta
266316,78125 / 365 = 729,635017123 vuotta
T. Urpo - Anonyymi
Anonyymi kirjoitti:
Jos hyvin huonosti tai toisin sanoen hyvin perältä löytyy tuo pienin kierrosmäärä, saattaa ratkaisun löytyminen kestää minun koneella yli 729 vuotta, näin pahimmillaan.
Tähän tulokseen pääsin kun ajoin tuon junar9.in tiedoston läpi paikkoja vaihtelematta, jolloin kierroksia tuli 25057 kpl ja tuohon tuhlaantui aikaa reilut 4 sekuntia (real 0m4,602s).
Näin saatua kierrosmäärää voidaan pitää maksimi kierrosmääränä, joka vähenee jokaisen paremman tuloksen aikaansaamana. Eli python Scriptin suoritus katkaistaan siihen kun MAX kierrosmäärä ylittyy, näin säästetään systemaattisen läpikäynnin aikaa. Laskettu aika (729 vuotta) lyhenee sitä enemmän mitä varhaisemmassa vaiheessa törmätään pieneen kierrosmäärään, eli oikeaan osuneeseen taulujen vaihtoon.
jos tauluja olisi 3 niin vaihtoja olisi 3
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 2 <-> 3
jos tauluja olisi 4 niin vaihtoja olisi 6
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 2 <-> 3
5 ) 2 <-> 4
6 ) 3 <-> 4
jos tauluja olisi 5 niin vaihtoja olisi 10
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 1 <-> 5
5 ) 2 <-> 3
6 ) 2 <-> 4
7 ) 2 <-> 5
8 ) 3 <-> 4
9 ) 3 <-> 5
10 ) 4 <-> 5
Näin ei tule turhia vaihtoja. Mutta siitä huolimatta systemaattinen taulujen vaihto tuottaa 100 000 taulun kanssa 499 9950 000 vaihtoa. Nyt meillä on tarpeeksi tietoa laskea maksimi aika tehtävälle seuraavasti:
1 Asetelma vie 4,602 sekuntia
100000 taulun systemaattinen taulujen vaihto tarjoaa 499 9950 000 vaihtoehtoa joten
499 9950 000 x 4,602 sekuntia = 23009769900 sekuntia
23009769900 / 60 = 383496165 minuuttia
383496165 / 60 = 6391602,75 tuntia
6391602,75 / 24 = 266316,78125 vuorokautta
266316,78125 / 365 = 729,635017123 vuotta
T. UrpoMillä ihmeen 286 koneella lasket?
- Anonyymi
Anonyymi kirjoitti:
Millä ihmeen 286 koneella lasket?
Ei ole mikään ihmekone, eikä edes 286, vaan ihan tavallinen 7 - 11 vuotta vanha, kun en muista koska hankin, enkä tähän hätään viitsi sen parempaa selvitystyötä hankinta ajankohdasta tehdä.
- Anonyymi
Anonyymi kirjoitti:
Ei ole mikään ihmekone, eikä edes 286, vaan ihan tavallinen 7 - 11 vuotta vanha, kun en muista koska hankin, enkä tähän hätään viitsi sen parempaa selvitystyötä hankinta ajankohdasta tehdä.
Sinolia kupissa, ei kokista.
- Anonyymi
Anonyymi kirjoitti:
Jos hyvin huonosti tai toisin sanoen hyvin perältä löytyy tuo pienin kierrosmäärä, saattaa ratkaisun löytyminen kestää minun koneella yli 729 vuotta, näin pahimmillaan.
Tähän tulokseen pääsin kun ajoin tuon junar9.in tiedoston läpi paikkoja vaihtelematta, jolloin kierroksia tuli 25057 kpl ja tuohon tuhlaantui aikaa reilut 4 sekuntia (real 0m4,602s).
Näin saatua kierrosmäärää voidaan pitää maksimi kierrosmääränä, joka vähenee jokaisen paremman tuloksen aikaansaamana. Eli python Scriptin suoritus katkaistaan siihen kun MAX kierrosmäärä ylittyy, näin säästetään systemaattisen läpikäynnin aikaa. Laskettu aika (729 vuotta) lyhenee sitä enemmän mitä varhaisemmassa vaiheessa törmätään pieneen kierrosmäärään, eli oikeaan osuneeseen taulujen vaihtoon.
jos tauluja olisi 3 niin vaihtoja olisi 3
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 2 <-> 3
jos tauluja olisi 4 niin vaihtoja olisi 6
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 2 <-> 3
5 ) 2 <-> 4
6 ) 3 <-> 4
jos tauluja olisi 5 niin vaihtoja olisi 10
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 1 <-> 5
5 ) 2 <-> 3
6 ) 2 <-> 4
7 ) 2 <-> 5
8 ) 3 <-> 4
9 ) 3 <-> 5
10 ) 4 <-> 5
Näin ei tule turhia vaihtoja. Mutta siitä huolimatta systemaattinen taulujen vaihto tuottaa 100 000 taulun kanssa 499 9950 000 vaihtoa. Nyt meillä on tarpeeksi tietoa laskea maksimi aika tehtävälle seuraavasti:
1 Asetelma vie 4,602 sekuntia
100000 taulun systemaattinen taulujen vaihto tarjoaa 499 9950 000 vaihtoehtoa joten
499 9950 000 x 4,602 sekuntia = 23009769900 sekuntia
23009769900 / 60 = 383496165 minuuttia
383496165 / 60 = 6391602,75 tuntia
6391602,75 / 24 = 266316,78125 vuorokautta
266316,78125 / 365 = 729,635017123 vuotta
T. UrpoMaituuko sinoli?
- Anonyymi
Anonyymi kirjoitti:
Jos hyvin huonosti tai toisin sanoen hyvin perältä löytyy tuo pienin kierrosmäärä, saattaa ratkaisun löytyminen kestää minun koneella yli 729 vuotta, näin pahimmillaan.
Tähän tulokseen pääsin kun ajoin tuon junar9.in tiedoston läpi paikkoja vaihtelematta, jolloin kierroksia tuli 25057 kpl ja tuohon tuhlaantui aikaa reilut 4 sekuntia (real 0m4,602s).
Näin saatua kierrosmäärää voidaan pitää maksimi kierrosmääränä, joka vähenee jokaisen paremman tuloksen aikaansaamana. Eli python Scriptin suoritus katkaistaan siihen kun MAX kierrosmäärä ylittyy, näin säästetään systemaattisen läpikäynnin aikaa. Laskettu aika (729 vuotta) lyhenee sitä enemmän mitä varhaisemmassa vaiheessa törmätään pieneen kierrosmäärään, eli oikeaan osuneeseen taulujen vaihtoon.
jos tauluja olisi 3 niin vaihtoja olisi 3
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 2 <-> 3
jos tauluja olisi 4 niin vaihtoja olisi 6
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 2 <-> 3
5 ) 2 <-> 4
6 ) 3 <-> 4
jos tauluja olisi 5 niin vaihtoja olisi 10
1 ) 1 <-> 2
2 ) 1 <-> 3
3 ) 1 <-> 4
4 ) 1 <-> 5
5 ) 2 <-> 3
6 ) 2 <-> 4
7 ) 2 <-> 5
8 ) 3 <-> 4
9 ) 3 <-> 5
10 ) 4 <-> 5
Näin ei tule turhia vaihtoja. Mutta siitä huolimatta systemaattinen taulujen vaihto tuottaa 100 000 taulun kanssa 499 9950 000 vaihtoa. Nyt meillä on tarpeeksi tietoa laskea maksimi aika tehtävälle seuraavasti:
1 Asetelma vie 4,602 sekuntia
100000 taulun systemaattinen taulujen vaihto tarjoaa 499 9950 000 vaihtoehtoa joten
499 9950 000 x 4,602 sekuntia = 23009769900 sekuntia
23009769900 / 60 = 383496165 minuuttia
383496165 / 60 = 6391602,75 tuntia
6391602,75 / 24 = 266316,78125 vuorokautta
266316,78125 / 365 = 729,635017123 vuotta
T. UrpoMaituuko sinoli?
- Anonyymi
Tuolla on juttua, että n log n -algoritmi olisi mahdollista löytää, https://www.ohjelmointiputka.net/keskustelu/12520-putkaposti-7-junarata/sivu-1
Aloin ajattelemaan tuota laskua niin, että ne hyvät siirrot olisivat matriisin riveinä. Silloin ongelma redusoituu tämän matriisin toisen potenssin jäljen laskemiseksi. Eihän tämä sitä laskua mihinkään muuta, mutta se helpottaa asian ymmärtämistä.
En kuitenkaan siitä sitten osannut edetä, joten kysyin neuvoa tuolta isomman maailman rattaista: https://stackoverflow.com/questions/59799872/binary-matrix-with-max-2-contiguous-blocks-of-1s-as-rows-calculate-trace-of/
Sieltä tuli vastaus: käytetään Fenwick-puuta ja järjestään "tapahtumat" (ykkösputkien alkamiset ja loppumiset) sarakkeen mukaan ja summataan. Tämä antaa O(n*log(n)) -algoritmin.
Tässä uusi versio: https://membolicsythod.home.blog/2020/01/18/junarata-tehtava-2/
viimeinen tapaus vei nyt vain 6 sekuntia.- Anonyymi
Ei Pata jätkä osaa koodata eikä se mistään mitään muutenkaan tiedä! valehtee vaan !
- Anonyymi
Mitä te tavoittelette tämän tehtävän kanssa, sitäkö miten pythonilla löydetään ratkaisu, vai jotain laskukaavaa jolla ratkaisu löytyy laskemalla, vai jotain muuta.
Minä tein tuohon jo ohjelman joka käy systemaattisesti, kaikki vaihtoehdot läpi, mutta aikaa ei ole niin paljon että tuon junar9.in tiedoston sisältämät 100 000 numerotaulun läpi käynti onnistuisi. Reilut 4 minuuttia menee jo tuon 1 000 numerotaulun läpi käyntiin, nuo tauluthan oli tiedostossa junar5.in.
Yritin myös tuota sinun koodiasi, mutta jotain puuttui minulta, etten onnistunut ajamaan sitä sellaisenaan, ja olisin joutunut syventymään siihen tarkemmin selvittääkseni missä vika.
T. Urpo - Anonyymi
Anonyymi kirjoitti:
Mitä te tavoittelette tämän tehtävän kanssa, sitäkö miten pythonilla löydetään ratkaisu, vai jotain laskukaavaa jolla ratkaisu löytyy laskemalla, vai jotain muuta.
Minä tein tuohon jo ohjelman joka käy systemaattisesti, kaikki vaihtoehdot läpi, mutta aikaa ei ole niin paljon että tuon junar9.in tiedoston sisältämät 100 000 numerotaulun läpi käynti onnistuisi. Reilut 4 minuuttia menee jo tuon 1 000 numerotaulun läpi käyntiin, nuo tauluthan oli tiedostossa junar5.in.
Yritin myös tuota sinun koodiasi, mutta jotain puuttui minulta, etten onnistunut ajamaan sitä sellaisenaan, ja olisin joutunut syventymään siihen tarkemmin selvittääkseni missä vika.
T. Urpoliikaa sinolia, ei tosta mitään tuu saimaalla!
Anonyymi kirjoitti:
Mitä te tavoittelette tämän tehtävän kanssa, sitäkö miten pythonilla löydetään ratkaisu, vai jotain laskukaavaa jolla ratkaisu löytyy laskemalla, vai jotain muuta.
Minä tein tuohon jo ohjelman joka käy systemaattisesti, kaikki vaihtoehdot läpi, mutta aikaa ei ole niin paljon että tuon junar9.in tiedoston sisältämät 100 000 numerotaulun läpi käynti onnistuisi. Reilut 4 minuuttia menee jo tuon 1 000 numerotaulun läpi käyntiin, nuo tauluthan oli tiedostossa junar5.in.
Yritin myös tuota sinun koodiasi, mutta jotain puuttui minulta, etten onnistunut ajamaan sitä sellaisenaan, ja olisin joutunut syventymään siihen tarkemmin selvittääkseni missä vika.
T. UrpoTavoitteena tietenkin tehokas algoritmit. Siinä samalla sitten oppii uusia juttujakin, niinkuin esim tuo Fenwick-puu oli itselleni täysin uusi tuttavuus. Yllättävän helppo koodata.
Joo, jos jokainen pari käydään läpi ja testataan Θ(n) -algoritmilla, niin siitähän tulee Θ(n^3), joten n=10^5 on auttamatta liian iso. Parin testaushan oli jo saatu vakioaikaiseksi, mutta tämä jälkimmäinen algoritmi nopeuttaa vielä tätä suotuisten parien summaamista.
Ai, mitä se herjaa, ettei onnistu? Kyllä se pitäisi Python 3:llakin toimia, ainakin täällä toimii: https://repl.it/repls/ActiveOblongMetrics
Olisin suoraan laittanutkin tuonne repl.ittiin, mutta Google ei päästä minua kirjautumaan sisään.- Anonyymi
minkkilaukku kirjoitti:
Tavoitteena tietenkin tehokas algoritmit. Siinä samalla sitten oppii uusia juttujakin, niinkuin esim tuo Fenwick-puu oli itselleni täysin uusi tuttavuus. Yllättävän helppo koodata.
Joo, jos jokainen pari käydään läpi ja testataan Θ(n) -algoritmilla, niin siitähän tulee Θ(n^3), joten n=10^5 on auttamatta liian iso. Parin testaushan oli jo saatu vakioaikaiseksi, mutta tämä jälkimmäinen algoritmi nopeuttaa vielä tätä suotuisten parien summaamista.
Ai, mitä se herjaa, ettei onnistu? Kyllä se pitäisi Python 3:llakin toimia, ainakin täällä toimii: https://repl.it/repls/ActiveOblongMetrics
Olisin suoraan laittanutkin tuonne repl.ittiin, mutta Google ei päästä minua kirjautumaan sisään.Ei hitto, 10,x sekuntia tuon junar9.in tiedoston sisältämien 100 000 numerotaulun läpi käynti, ei kai. Nyt on jo pakko ruveta tarkastelemaan tuota oikein kunnolla, mitä hittoa se oikeastaan tekee.
Palaan astialle jos jotain saan selville.
T. Urpo - Anonyymi
Anonyymi kirjoitti:
Ei hitto, 10,x sekuntia tuon junar9.in tiedoston sisältämien 100 000 numerotaulun läpi käynti, ei kai. Nyt on jo pakko ruveta tarkastelemaan tuota oikein kunnolla, mitä hittoa se oikeastaan tekee.
Palaan astialle jos jotain saan selville.
T. UrpoKirjoitin jo eilen tähän jatkoa, mutta toimimaton moderointi poisti.
enumerate, permutation käsitteet jääneet vähemmälle, avautuu, mutta hitaasti.
- Anonyymi
Minusta Trio merkkinen on paras. Puinen ja helppo kasata.
- Anonyymi
Siis Brio.
Ketjusta on poistettu 3 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
- 2678906
Minä itkin kotona kun tajusin että
Pelkuruuteni takia kun en lähestynyt vaikka järjestit otollisen hetken ja myöhemmin huomasin lasittuneen katseesi miten152806- 562066
Ylen jälkiviisaat estotonta Kamala Harris suitsutusta
Kolme samanmielistä naikkosta hehkutti Kamala Harrisia ja haukkui Trumpia estottomasti. Nyt oli tarkoituksella valittu3561840- 791798
Onko jotain sanottavaa vielä, nyt voi kertoa
Poistun kohta täältä ja unohdan ajatuksen naimisiin menosta. Mieheltä291789Muistutus t-Naiselle.
Olet ilkeä ja narsistinen k-pää. Annat itsestäsi kiltin kuvan ulospäin kelataksesi ihmiset ansaan. Sitten päsmäröit, hau1531744Oiskohan se aika
Selvittää pää vihdoin ja viimein. Minun kaivattu ei todellakaan käy täällä ja piste. Ei ole mitään järkeä enää tuhlata t81701Oho! Varmistusta odotellaan.
Pitäneekö paikkansa? "🇺🇦Ukrainian drones hit a 🇷🇺Russian Tu-22M3 bomber at the Olenya airfield,"1601694- 391649