Keskustelu: Ohjelmointiputka: Putkaposti 46: Peltotutkimus

Tässä tulee uusi putkaposti:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=petu

Esim. OpenOffice.orgin Draw:lla voi kätevästi sommitella eri kokoisia neliöitä mahdollisimman tiiviiseen kasaan. Snap to grid auttaa.

Ja jottei ohjelmointipalstan tehtävä mene paheksuttavasti täysin ilman koodausta, voi tehdä pienen skriptin auttamaan pinta-alan laskemisessa:

Python, suorakulmiossa tiukasti vierekkäin palikat ABCD, allekkain BF:

>>> sivut = dict(zip('ABCDEFGHIJ', range(10, 0, -1)))
>>> def ala(s, t):
...     return sum(sivut[k] for k in s) * sum(sivut[k] for k in t)
...
>>> ala('ABCD', 'BF')
476

Ratkaisuja on tullut jo kiitettävää tahtia. Onko joku varma siitä, että nykyinen ratkaisu on optimaalinen?

Jos joku kokee seuraavan perustelun kovasti spoilaavaksi, jättäköön lukematta. Tiedot voi joka tapauksessa todeta kokeellisesti.

Neliöiden yhteispinta-ala on 385, ja suurimman neliön takia alle 10 ruudun sivunpituus ei tule kyseeseen. Riittää siis tutkia tapaukset, joissa lyhyempi sivu on 10–20 ruutua. (Jos lyhyempi sivu on 21, tuloskin on vähintään 441.)

Eri pituuksille voi helposti muodostaa varmoja alarajoja. Esimerkiksi lyhyemmän sivun pituuden ollessa 14 joudutaan laittamaan neliöt 10, 9, 8 ja 7 peräkkäin, koska mitkä tahansa näistä rinnakkain olisivat jo yli 14 ruutua. Pitkä sivu on siis ainakin 34 ja lopputulos siten ainakin 476. Sama päättely soveltuu muihinkin tapauksiin, joskin tapauksissa 17–20 täytyy miettiä vähän myös rinnakkaisia neliöitä.

Parannusta ei siis ole luvassa.

Tuli pitkästä aikaa ratkaistua Putkaposti ja se olikin kovin helppo.

Lisäksi kanssa päättelin, ettei parempaa ratkaisua ole olemassa, tosin hieman eri tavalla kuin Metabolix.

Metabolix: Tossa sun taulukossa on virhe 12 leveyden kohdalla. Siinäkin pitäisi olla + 6

Grez, taulukon ei ole tarkoituskaan antaa parasta mahdollista tulosta vaan jokin optimistinen arvio, jonka perusteella voidaan todeta, että nykyistä tulosta ei voi parantaa. Tuossa kohti peli on jo menetetty, joten kuutosta ei tarvitse edes ajatella.

Jaa, luulin että siinä oli listattu edellisessä kappaleessa kuvaamasi logiikan mukaiset tapaukset.

Logiikkahan on aivan sama, vaikka kaikkia siitä johdettavia päätelmiä ei lueteltaisi. Vai väitätkö, että kyseisessä tapauksessa ei jouduta laittamaan neliöitä 10, 9, 8 ja 7 mainitulla tavalla mainitusta syystä? :)

Mielesätni siinä joudutaan laittamaan neliöt 10, 9, 8, 7 ja 6 peräkkäin, koska mitkä tahansa näistä olisivat rinnakkain jo yli 12 ruutua.

Ja minusta silloin on jo jouduttu laittamaan myös neliöt 10, 9, 8 ja 7 peräkkäin, koska mitkä tahansa näistäkin olisivat rinnakkain jo yli 12 ruutua.

Ajattele nyt professoriparkaa, joka joutuu kaivamaan ylimääräisen 36 neliön pellon, ennen kuin huomaa virheensä.

Toki, mutta miksi sitten esimerkiksi tuossa 11 kohdassa on laitettu se kuutonenkin mukaan?

Siis ei tässä mitään ongelmaa sinänsä ole. Kuten sanoin, niin ymmärsin aluksi väärin mitä siinä taulukossa haettiin. Luulin että siinä haettiin ilmeisiä alarajoja. Ymmärsin jo että siinä haetaankin mitä vaan perusteltavissa olevaa yli 405 menevää vähimmäismäärää.

Eli siis 408 on riittävän hyvä "alaraja", vaikka onkin annetun esimerkin perusteella selvää, että alle 480 ei ole mahdollinen.

Koska (10 + 9 + 8 + 7) * 11 = 374, jolloin ei ole vielä todistettu, etteikö tästä saataisi väännettyä uutta ennätysratkaisua. Tarkoitus on siis listata vähimmäismäärä neliöitä, joiden jälkeen selvästi nähdään, että uutta ennätystä ei tule. Tätähän Antti kysyi.