En osaa millään: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu ja https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2
Onpas ohjelmointi vaikeaa
vaikeaaon
24
84
Vastaukset
Mielenkiintoinen tehtävä, millä kielellä koodailet? Vaikka ei kai sillä niin väliä ole vaan algoritmistä kyse.
Itse lähdin kokeilemaan vain laittaa niitä neliöitä ruudukkoon (ruudukon kokoa manuaalisesti koittellen). Se on periaatteessa "rekursiivinen back-trackeri": https://en.wikipedia.org/wiki/Backtracking eli oikeastaan brute-force metodi. Aluksi näytti, että ei näillä metodein onnistu, mutta loppupeleissä kaiken eron teki se, että lähteekin koittamaan lopusta päin eli pitempiä lukuja (ekassa tapauksessa 400:sta) ensin. Lisäksi turhia lukuja voi siivota pois (jotka sisältyvät jo toisiin, esim 1 on 100:ssa ja 4 on 400:ssa).
Joka vaiheessa kun uutta lukua koitetaan laittaa, tutkitaan kaikki paikat mihin sen voisi laittaa ja tallennettaan kaikki uudet numerot ja paikat (ns. asettelu tieto), mitä näin laittamalla ruudukkoon kirjoitetaan (jotta ne voi valintaa peruttaessa pyyhkiä pois, eikä lähde sellaisia, jotka olivat tulleet jo muista luvuista).
Ekaan löysin tuon 20 ruudun (4x5) ratkaisun, mikä näyttäisi luultavasti olevan optimaalinen.
Tokaan löysin 165 ruudun (11x15). Pienemmille ei ihan hetkessä löytynyt mitään, varmaan tarvitaan parempia metodeja tähän kakkoseen...
Hmmm... onkohan tuo jlairen ratkaisu 117 muotoa 9x13 vai 3x39?
Niin ja mun koodi, jos haluat kattoa, niin: https://jsfiddle.net/rybLk4je/- vaikeaaon
"Mielenkiintoinen tehtävä, millä kielellä koodailet?"
Pythonilla ja Javalla.
"Hmmm... onkohan tuo jlairen ratkaisu 117 muotoa 9x13 vai 3x39?"
Veikkaisin, että 9x13. Mutta enpä tiedä.
Mä olen miettinyt, että toimisiko joku geneettinen algoritmi tai simuloitu jäähdytys tai bin packing -algoritmi? En vaan osaa kunnolla toteuttaa sellaista vaikeaaon kirjoitti:
"Mielenkiintoinen tehtävä, millä kielellä koodailet?"
Pythonilla ja Javalla.
"Hmmm... onkohan tuo jlairen ratkaisu 117 muotoa 9x13 vai 3x39?"
Veikkaisin, että 9x13. Mutta enpä tiedä.
Mä olen miettinyt, että toimisiko joku geneettinen algoritmi tai simuloitu jäähdytys tai bin packing -algoritmi? En vaan osaa kunnolla toteuttaa sellaistaKokeilin vähän geneettistä, sillä pelin, että "geenit" ovat paikat ja suunnat mihin neliöluvut laitetaan ruudukossa (jonka koko on fiksattu).
Javascripti-koodini: https://github.com/minkkilaukku/ahdas-ruudukko
Tiedosto grid1.js on tuo Grid-luokka, grid2:ssa yritin sitten toisenlaista, että geenit=2d-taulu, jossa numerot. Geneettinen algo tiedostossa genetics.js.
Kyllä se tuon pienemmän tapauksen ratkaisee (tai joskus näyttää jäävän jumiin, että on yksi virhe), mutta isommille ei taida oikein hyvä ainakaan vielä olla.
Kolmas tapa, jota mietin olisi että laitetaan kaikki neliöluvut johonkin ruudukkoon eikä sallita virheitä (eli vääriä päällekkäisyyksiä), mutta miten sitten kaksi tällaista paritetaan keskenään. Jostain kohdastahan niitä pitäisi leikellä ja liimata, mutta miten?
Simuloitu änniilinki -kokeilu, ei järin hyvä: https://github.com/minkkilaukku/ahdas-ruudukko-annealing
Laitoin tuohon nyt silleen, että vääriä päällekkäisyyksiä ei sallita vaan jos luku ei mahdu mihinkään paikkaan, ruudukkoa on pakko laajentaa ja laittaa luku sinne reunaan. Näin siis ruudukon kokokaan ei ole fiksattu vaan se muodostetaan dynaamisesti lukuja lisättäessä ja siirreltäessä.
Steppi (eli naapuruus-relaatio) on siten, että otetaan jokin luku ja laitetaan uuteen satunnaiseen paikkaan, jonka seurauksena sen kanssa ristiriidassa olevat luvut täytyy sijoittaa uudelleen (ja laajentavat ruudukkoa, jos niitä ei voi muuaalle sijoittaa).
Energia lasketaan ruudukon koko 0.23*( reunimmaiset rivi ja sarake (kuinka monta ruutua siellä täytetty * sen pituus)). Pitäisikö tähän olla parempaa kaavaa?
Miten tuon T:n ("lämpötila") pienennys pitäisi oikein suorittaa? Nyt se vain kerrotaan aina steppi tehdessä (oikeasti se hyväksyttäessä) 0.95:llä.
Tällaisenaan ei oikein hyviä ratkaisuja löydä. Tuntuu, että T pienenee liian nopeasti.Muutin energian lasku tapaa: Meillä on haluttu koko ruudukolle ja lasketaan tämän yli menevät ruudut (tai kuinka monta numeroa ruudussa on ja se vielä toiseen) yhteen.
Nyt se jopa ratkaisi tapauksen k=20 lopulta!
Vei 41089 iteraatiota ja tehtiin 1280 siirtymää.
Tällasen ruudukon se lopulta löysi:
12169
19054
68024
32421
Tapaus k=100, ei luonnistu, siellä se pysyy 16x18 hujakoilla. On tässä jotain parannusta kyllä edelliseen, joka ei useinkaan päässyt 18x19:aa paremmaksi (jos nyt ei tuurillaan).Parannus: Valitaan step:issä aina luku, joka koskettaa reunaa.
Ei se keskilukujen purjaus kannata, ja satunnaisuutta siinä kyllä tulee aina mukaan, kun laitetaan satunnaiseen kohtaan (vai kannataisiko tässäkin valita sellainen paikka, että se syrjäyttää mahdollisimin harvan luvun??).
Satanen menee jo 16x17:aan.
No just meni tätä kirjoittaessani 15x17.
Huonohan se on yhä, mutta parannusta...
- netistälöytänyt
11x11 tapaus ratkaistu osoitteessa https://stackoverflow.com/questions/3382859/solving-a-recreational-square-packing-problem . Käyttää jotain puolisatunnaista etsintää, en ole muualla tuollaiseen törmännyt.
Ootteko koittanu tuolla löytää sitä 9x13:aa (jos nyt oletetaan, että se alkaa olemaan sitten melko optimaalinen)?
Ehkä tälleen toimis SA:kin. Steppi: muutetaan yksi numero ruudukossa satunnaisesti numeroiden jakauman mukaan. Energia: kuinka monta lukua löytyy (ehkä myös lasketaan jos löytyy useamman kerran ja pituudella paimotettuna).
- Anonyymi
minkkilaukku kirjoitti:
Ootteko koittanu tuolla löytää sitä 9x13:aa (jos nyt oletetaan, että se alkaa olemaan sitten melko optimaalinen)?
En osaa tarpeeksi ohjelmointia, että osaisin muokata koodia pienemmälle ruudukolle.
Anonyymi kirjoitti:
En osaa tarpeeksi ohjelmointia, että osaisin muokata koodia pienemmälle ruudukolle.
Muokkasin sitä käyttämään parametrejä M ja N ruudukon kooksi. Koodi osoitteessa https://github.com/minkkilaukku/square-packing , tiedosto sqBackMB.py.
Pääsin 9x13 ruudukolle 94:ään asti parhaimmillaan, mutta en uskalla jättää konetta ratkomaan, kun tällä on vähän ylikuumenemisongelmia.
Tein myös JS-kopion (samassa osoitteessa, tiedosto ahdRuu3.js) mutta en ymmärrä kuollaksenikaan miksi se ei toimi yhtä hyvin, vaikka pitäisi olla melko lailla kopio. Ei, joku virhe siellä täytyy olla, kun se ei ratkaise edes 4x5:sta 20:lle neliölle.minkkilaukku kirjoitti:
Muokkasin sitä käyttämään parametrejä M ja N ruudukon kooksi. Koodi osoitteessa https://github.com/minkkilaukku/square-packing , tiedosto sqBackMB.py.
Pääsin 9x13 ruudukolle 94:ään asti parhaimmillaan, mutta en uskalla jättää konetta ratkomaan, kun tällä on vähän ylikuumenemisongelmia.
Tein myös JS-kopion (samassa osoitteessa, tiedosto ahdRuu3.js) mutta en ymmärrä kuollaksenikaan miksi se ei toimi yhtä hyvin, vaikka pitäisi olla melko lailla kopio. Ei, joku virhe siellä täytyy olla, kun se ei ratkaise edes 4x5:sta 20:lle neliölle.Nyt tajusin, mistä JS-kopioni virhe johtuu!
Rivillä 199 ei tietenkään saa olla aitoa suurempi kuin-merkkiä vaan yhtäsuuruus mukana.- Anonyymi
minkkilaukku kirjoitti:
Ootteko koittanu tuolla löytää sitä 9x13:aa (jos nyt oletetaan, että se alkaa olemaan sitten melko optimaalinen)?
Joo. Tekemäsi Python-koodi ratkoo tapauksen 9x13.
Anonyymi kirjoitti:
Joo. Tekemäsi Python-koodi ratkoo tapauksen 9x13.
No hyvä. Eihän se kyllä minun tekemä ollu, vähän vaan tuosta alkuperäisestä muokkasin.
Menikö miten pitkään ennen kuin löyty?- Anonyymi
Muokkasin ohjelmaa siten, että tulostaa ajan, pelkän loppuratkaisun ja että toimii Python 3:lla. Kone on Asus GL553VW ja Ubuntu 19.04. Ajoaika oli 1 h 52 min 11 s.
- Anonyymi
Anonyymi kirjoitti:
Muokkasin ohjelmaa siten, että tulostaa ajan, pelkän loppuratkaisun ja että toimii Python 3:lla. Kone on Asus GL553VW ja Ubuntu 19.04. Ajoaika oli 1 h 52 min 11 s.
Ahaa, nyt käsitän miksi ratkaisuja löytyy, Ubuntu 19.04, ja Ubuntun käyttäjä puikoissa.
- Anonyymi
Anonyymi kirjoitti:
Muokkasin ohjelmaa siten, että tulostaa ajan, pelkän loppuratkaisun ja että toimii Python 3:lla. Kone on Asus GL553VW ja Ubuntu 19.04. Ajoaika oli 1 h 52 min 11 s.
"Testissä Ubuntu 19.04 Disco Dingo: kaunis ja buginen"
Mikrobitissä oli tuollainen teksti, toimiiko siinä kumminkin jokin? - Anonyymi
Anonyymi kirjoitti:
"Testissä Ubuntu 19.04 Disco Dingo: kaunis ja buginen"
Mikrobitissä oli tuollainen teksti, toimiiko siinä kumminkin jokin?Ei toimi mikään kunnolla, jorpakkoon joutaa koko kurttaus. Kokeilkaa niin pientä ruudukkoa että kykenette tuloksen oikeellisuuden tarkaistamaan käsin.
Olisi tästä mitään hyötyä: https://aijaa.com/KosA1X ?
Tostaku ne vaa jotenki puristas kasaan limittäin ja lomittain ja ratkasu ois siinä!
Siellä on siis 81 lukua (3 vielä pysty pudottamaan pois edellisistä 84:stä, unohdin kattoo myös takaperin).
Yks tapa mitä vielä ajattelin: katottas ryhmät missä on paljon samoja ja niistä tehtäs omia pienempiä blokkejaan ja sitten yritettäs näitä yhdistellä, vähän niinkuin "nested annealing". Ei, ei.
Ehkä yritän vielä sellasta anniilinkiä, jossa ruudukko on tiukka haluttu ja ne saa mennä päällekkäin ja energia on kuinka paljon menee päällekkäin. Voishan siinä sen alkutilan jotenkin yrittää tuosta graafista, joka siis on eräällä tavalla minimaalinen virittäjäpuu graafille, jossa on 1-vahvuinen linkki, jos luvuissa on sama numero ja t-vahvuinen, jos niissä on päissä t:n pituinen jakso, joka voi mennä päällekkäin, muodostaa(?)- vaikeaaon
Tuskin paljoakaan on hyötyä. Mietin joskus tehtävää verkkoteorian avulla. En keksinyt oiken järkevää lähestymistapaa. Mutta keskustelun perusteella olen parempi ohjelmoimaan kuin minä. En tiedä millainen olisi sopiva "puristamisalgoritmi".
- vaikeaaon
vaikeaaon kirjoitti:
Tuskin paljoakaan on hyötyä. Mietin joskus tehtävää verkkoteorian avulla. En keksinyt oiken järkevää lähestymistapaa. Mutta keskustelun perusteella olen parempi ohjelmoimaan kuin minä. En tiedä millainen olisi sopiva "puristamisalgoritmi".
Siis sinä olet parempi ohjelmoimaan kuin minä.
Hei, kerkesin lukemaan tuon poistetun viestin ja kattelin vähän sitä Tomozovin paperia. Yksi juttu mistä siellä puhuttiin on "forward checking" ja sitäkin olin jo koittanut toteutella ja kattonu esimerkkiä karttojen värityksestä. Siinähän on helppo, kun vierekkäinen ei saa olla samaa väriä, mutta tämä on kyllä hankalampi.
Tässä jos muuttujat on jokaiselle neliöluvulle paikka ja suunta mihin se laitetaan, niin eikös se ole erittäin epätehokasta joka kerta kun uusi luku laitetaan paikoilleen, niin tarkastaa mitkä putoaa toisten domaineista pois ja sitten valita se jolla vähiten vaihtoehtoja? Ja lisäksi, pitäskö ne tallettaa että mitkä vaihtoehdot putosi pois kustakin, että backtracattäessä osataan sitten laittaa sopivat takaisin (tuo on oikeastaan minulta siinä kartan väritys esimerkissäkin ymmärtämättä, että miten ne sitten tarkastetaan backträkättäessä, kun eihän sitä tiedä lähtikö väri jostain naapurista tämän juuri käsitellyn takia vai onko se jo kielletty jonkun toisen naapurin toimesta).
SA:han en tuolta oikein löytänyt mitään uutta ideaa. Vähän erilainen tehtävähän siellä on, kun ilmeisesti sanat on (harvoissa) ennalta määrätyissä paikoissa ja sanakirja on sitten iso, kun vastaavasti tässä sanoja (eli ne neliöluvut) on vähän, mutta paikkoja, mihin pistää, paljon.Tein nyt vielä yhden SA-version, joka perustuu tuohon StackOverflow-vastauksen koodiin. Vaikuttaisi olevan paras tähän mennessä. En ole kuitenkaan vielä edes sille 11x11:lle löytänyt ratkaisua, mutta en ole pitkään kyllä koittanutkaan. Mutta joo, noin se on ehkä parempi, että otetaan avaruudeksi ruudukot, eikä niitten lukujen asetteluja. Niitä ruudukkojahan on näin "pienille" m,n jopa itseasiassa vähemmän kuin asetteluja:
10^(11*11) = 10^121
(8*11*11)^81 = 7.176e 241
(kaikki 8*11*11 asettelua eivät ole sanan pituudesta johtuen mahdollisia, mutta reunat tulevat ruudukon kasvaessa merkityksettömimmiksi)
Ensimmäinen on kuitenkin ruudukon koon kasvaessa eksponentiaalinen, mutta jälkimmäin vain, no (mn)^81.
Jos taas k:ta kasvatetaan, niin sitten on jälkimmäinen eksponentiaalinen.
https://github.com/minkkilaukku/sa-sqpack
Laitoin tuohon siten, että tietyn iteraatiomäärän jälkeen SA resetöidään jos se näin pomppaisi pois lokaalista loukusta eli oikeastaan sama idea kuin alkuperäisessä algoritmissä.Täällä voi testata: https://codepen.io/minkkilaukku/full/zXjaZm
Ai niin, yksi juttu mitä vielä mietin on, että kannattaakohan niitä "turhia" lukuja siivotakkaan pois vaan itse asiassa laittaa lisää lukujen osasanoja mukaan, jotta nämä laskisivat ratkaisun sitä paremmaksi vaikka jokin tietty luku ei olisikaan mukana mutta jos osa siitä on. Nykyversiossakin painotetaan luvun pituudella, mutta jos lukua ei yhdellä muutoksella voi saada mukaan, niin se ei auta.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Miehille kysymys
Onko näin, että jos miestä kiinnostaa tarpeeksi niin hän kyllä ottaa vaikka riskin pakeista ja osoittaa sen kiinnostukse1343879- 851905
Olen tosi outo....
Päättelen palstajuttujen perusteella mitä mieltä minun kaipauksen kohde minusta on. Joskus kuvittelen tänne selkeitä tap151771Haluaisin jo
Myöntää nämä tunteet sinulle face to face. En uskalla vain nolata itseäni enää. Enkä pysty elämäänkin näiden kanssa jos541412Kotkalainen Demari Riku Pirinen vangittu Saksassa lapsipornosta
https://www.kymensanomat.fi/paikalliset/8081054 Kotkalainen Demari Riku Pirinen vangittu Saksassa lapsipornon hallussapi461337Ylen uutiset Haapaveden yt:stä.
Olipas kamalaa luettavaa kaupungin irtisanomisista. Työttömiä lisää 10 tai enempikin( Mieluskylän opettajat). Muuttavat1301323VENÄJÄ muuttanut tänään ydinasetroktiinia
Venäjän presidentti Vladimir Putin hyväksyi tiistaina päivitetyn ydinasedoktriinin, kertoo uutistoimisto Reuters. Sen mu991280- 701166
- 691033
Hommaatko kinkkua jouluksi?
Itse tein pakastimeen n. 3Kg:n murekkeen sienillä ja juustokuorrutuksella. Voihan se olla, että jonkun pienen, valmiin k1131022