Uusi putkaposti on ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Kyseessä on jo Putkapostin 50. tehtävä!
lainaus:
4x4-ruudukossa on yhteensä 30 alineliötä, joten tuloksen teoreettinen maksimi on 30.
Teoreettinen maksimi on kyllä vähemmän kuin 30, koska jotta 4x4 ruudukko antaisi 30 niin siellä täytyy olla monta samaa lukua ( summa 1 -> 64 > 30) jolloin jokaisessa 1x1 ruudussa ei voi olla eri numeroa.
Grez kirjoitti:
Teoreettinen maksimi on kyllä vähemmän kuin 30, koska jotta 4x4 ruudukko antaisi 30 niin siellä täytyy olla monta samaa lukua ( summa 1 -> 64 > 30) jolloin jokaisessa 1x1 ruudussa ei voi olla eri numeroa.
Ei eri numero joka ruutuun olekaan vaatimuksena?
Putkaposti: 50 kirjoitti:
Voit sijoittaa ruudukkoon mitä tahansa kokonaislukuja.
Teuro kirjoitti:
Ei eri numero joka ruutuun olekaan vaatimuksena?
En ole väittänyt mitään sen suuntaistakaan.
Sanoin että tuohon 30:een pääsemiseen vaadittaisiin, että jokaisessa aliruudussa olisi eri summa. Mikäli 1x1 aliruuduissa on samoja summia, niin silloinhan jokaisessa ei ole eri summa.
Tehtävänannon teoreettinen maksimi ei ole tosiaan tiukin mahdollinen. Parempaa maksimia saa ehdottaa. :)
Maksimi kuulostaa siltä, että se on mahdollinen saavuttaa. Itse sanoisin tuota vain ylärajaksi.
Hyvä idea, muutin maksimi -> yläraja.
Maksimia tai siis ylärajaa voi arvioida melko helposti seuraavalla tavalla.
Tutkitaan tapauksia, joissa ruudukossa on erillisiä kokonaislukuja väliltä 1-30 n kappaletta. Määrä n on väliltä 0 - 16, koska ruudukossa on 16 ruutua.
Ensin tapaus n = 16. Jos ruudukossa on 16 eri lukua ym. väliltä, on niiden summa vähintään sum [1 .. 16] = 136. Ruudukko jakautuu neljään erilliseen 2×2-aliruudukkoon. Koska koko ruudukon summa on 136, on tällaisen aliruudukon keskimääräinen summa ainakin 34. Tämä on yli 30, joten ainakin yhden aliruudukon summa on myös yli 30. Lisäksi koko ruudukon summa on yli 30, joten tässä tapauksessa lukuja väliltä 1-30 ei voi esiintyä yli 28:aa kappaletta. (Ylärajan näkee helposti tässä tapauksessa pienemmäksi, mutta tämä riittää meille.)
Tämän osan argumentista inspiroi Grezin esittämä päättely. Kiitos Grez.
Sitten tapaus n = 15. Nyt koko ruudukon summa voi olla väliltä 1-30 vain, jos yksi luku on sopiva negatiivinen kokonaisluku ja muut erillisiä lukuja välltä 1-30. Muiden lukujen summa on nyt vähintään sum [1 .. 15] = 120. Ylimääräinen luku on siis oltava k <= -90, jotta koko ruudukon summa olisi halutulta väliltä. Mikäli koko ruudukon summa ei ole tällä välillä, on summia korkeintaan 28, mihin tähtäänkin tällä argumentillä. Pitää siis olettaa, että k toteuttaa tämän ehdon, ja jatkaa päättelyä minne se viekin.
Jos toivottu k on ruudukossa, on luku k osa jotakin 2×2-aliruudukkoa, jonka summa puolestaan voi olla väliltä 1-30, mikäli sen kolme muuta alkiota a, b ja c toteuttavat ehdon a+b+c > 90. Tämän summan termien keskiarvo on kuitenkin yli 30, joten ainakin yksi niistä, sanotaan vaikka c > 30. Tämä on kuitenkin ristiriidassa oletuksen kanssa, että vain k ei ole välillä 1-30. Näin ollen ruudukon kaikissa 2×2-aliruudukoissa ei voi olla halutulta väliltä oleva summa tapauksessa n = 15.
Siispä tapauksessa n = 15 ei taulukossa voi olla yli 28:aa halutun välin summaa.
Jos taas erillisiä kokonaislukuja on 14 tai vähemmän, ei kaikkia summia voi olla yli 28:aa, koska kaksi lukua väliltä 1-30 puuttuu jo oletuksen nojalla.
Siispä sain teoreettiseksi ylärajaksi 28 tällä hienolla argumentoinnilla. Voin kuvitella, miten työlästä olisi soveltaa tätä päättelyä yritykseen laskea yläraja 27:ään. Jätänkin tehtävän pohdinnan omalta osalta tähän tällä kertaa.
Näyttää nyt siltä, että paras mahdollinen ratkaisu on siis välillä 24-28 nykyisten tietojemme nojalla. Parantakaapa vielä jompaakumpaa rajaa.
Niin, jokainen sama luku vähentäisi mahdollisuuksia 30:stä. Jokainen negatiivinen luku vähentää samalla tavalla. Numerot 1..16 muodostavat väkisinkin neliöihin summia jotka ylittävät 30. Näitä muodostuu 2x2 neliöihin vähintään kaksi, josta seuraa että 3x3 neliöissäkin niitä on lisää. Sitten vielä kaikkien summa on yli 30, joten kaikki nämä tapaukset vähennetään 30 niin on takuulla alle 28 kpl. Negatiivisia lukuja käyttäen voi saada tulosta paranemaan? Tuntuu että tuo 24 joka on saavutettu olisi aika lähellä lopullista ennätystä.
Pikkuvihjeenä, sisältyykö saavutettuihin 21-24 tuloksiin negatiivisia lukuja? :)
Minun kokeilussa sisältyy. Älä kerro kenellekään :-)
Olen löytänyt mm. tuloksen 18 antavia ratkaisuja, joissa vain puolet luvuista on positiivisia. Jotenkin en ihan tällaista odottanut. :)
Miten olis lisähaaste isommalla taululla?
tkok kirjoitti:
Miten olis lisähaaste isommalla taululla?
Kunhan nyt tuon normaalin version saisi ratkaistua*... intuitioni mukaan hyvien ratkaisujen luonne (kuinka paljon negatiivisia lukuja suhteessa positiivisiin lukuihin) vaikuttaisi muuttuvan huomattavasti taulun koon kasvaessa.
*ratkaistua <-> alin teoreettinen yläraja == paras tunnettu ratkaisu.
Mitään varmuuttahan ei ole, että yli 24 löytyy. Itse veikkaan että ainakaan 26 yli ei mennä.
En tiedä, että millaiset säännöt putkaposteihin liittyvässä keskustelussa on, niin en esitä päätelmiäni tarkemmin (antavat selkeitä rajoja tehtävän ratkaisulle), mutta on osoitettavissa, että 28 on mahdoton, jolloin yläraja olisi 27 tai alle.
24 tulee menetelmälläni (erittäin naiivi menetelmä) helposti ja olen löytänyt muutamia eri kombinaatioita, jotka tuottavat tuon 24. Epäilisin, että 24-25 saattaisi olla maksimi.
jtha kirjoitti:
Numerot 1..16 muodostavat väkisinkin neliöihin summia jotka ylittävät 30. Näitä muodostuu 2x2 neliöihin vähintään kaksi, josta seuraa että 3x3 neliöissäkin niitä on lisää.
sum(1..9) > 30, joten kaikki 3x3-neliöt ovat liian isoja. Eli jos käytetään luvut 1..16, löysä yläraja on 16 (1x1-neliöt) + 7 (2x2-neliöt) = 23, ja edes tuo 7 ei ole käytännössä mahdollinen. Tarkkaa rajaa en vielä tiedä, mutta naiivi brute hyrrää tuossa taustalla (16!).
Minulla on yli 1000 erilaista 24-ruudukkoa, mutta monet ovat suhteellisen triviaaleja variaatioita (ei kuitenkaan symmetrisesti samoja).
rot13-pohdintaa:
Gäexräg xlflzlxfrg bing n) zvgra zbagn 1..a yhxhn xälgrgääa, o) zvgä artngvvivfvä yhxhwn inyvgnna, wn p) zvgra yhihg fvwbvgrgnna. Byra inyvaahg yhcnnivn cnenzrgrewä xbugvva (n) wn (o) bfvggnva neinvyrznyyn wn bfvggnva fnghaanvfgra unxhwra crehfgrryyn, wn xbugnna (p) byra xbxrvyyhg fnghaanvfvn crezhgnngvbvgn gnv gälqryyvfgä oehgrn. Gäuäa ibvfv xälggää svxfhzcnnxva unxhn, wbxn onpxgenpxää xha >24 rv byr raää znuqbyyvara, zhggn ra byr wnxfnahg xbbqngn zbvfgn.
Artngvvivfgra yhxhwra fvwnna ibv unexvgn abyynn gnv cvravä cbfvgvvivfvn yhxhwn. Frxääa rv byr xvirra xvewbvgrggh, rggä gälgll xälggää 1..a rvxä rfvz. 1..a, a+2..x, zhggn ra wnxfn bggnn gäyynvfvn "fryiäfgv" uhbabwn vqrbvgn uhbzvbba. ;)
Cloudanger kirjoitti:
En tiedä, että millaiset säännöt putkaposteihin liittyvässä keskustelussa on, niin en esitä päätelmiäni tarkemmin (antavat selkeitä rajoja tehtävän ratkaisulle), mutta on osoitettavissa, että 28 on mahdoton, jolloin yläraja olisi 27 tai alle.
Voit mielellään perustella tuloksen 28 mahdottomuuden keskustelussa.
Ajoin yksinkertaisen rekursioratkaisun mielekkääksi katsomallani lukuvälillä, ja yli 24:n ratkaisuja ei löytynyt. Toki koodissani voi olla jokin virhe (en miettinyt optimointejani kovin perusteellisesti) tai saatoin valita liian pienen lukuvälin. Tapaukset 27–30 tutkin hieman laajemmalla lukuvälillä, joten ainakaan niiden suhteen en usko ihmeitä tapahtuvan.
Jälleen, kuten edellisessäkin tehtävässä, täytyy hämmästellä, kuinka GCC tuottaa noin 15 prosenttia hitaamman ohjelman kuin Clang. :o
Aihe on jo aika vanha, joten et voi enää vastata siihen.