Kirjautuminen

Haku

Tehtävät

Kilpailu

Murra koodi!
Lue ja osallistu!
Voittajia 1 + yrittäjiä 1

Keskustelu: Ohjelmointiputka: Putkaposti 30: Ahdas ruudukko

Sivun loppuun

Antti Laaksonen [27.04.2009 17:05:26]

#

Tässä tulee uusi putkaposti:

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

Myös vaikeampi versio on saatavilla:

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

Teuro [27.04.2009 18:05:32]

#

Tuntuu mielenkiintoiselta tehtävältä. Päässä mietyttänä tulee näköjään 30 varsin helpolla. Tuosta toki pystyy aika helposti karsimaan ruutuja.

jlaire [27.04.2009 19:57:39]

#

Helpompaan versioon löytyi käsin aika nopeasti 20-ruutuinen ratkaisu, joka toivottavasti on optimaalinen. Vaikeampaan pitää vielä miettiä joku järkevä algoritmi. Mielenkiintoinen tehtävä tosiaan.

Chiman [27.04.2009 20:27:04]

#

Funktion innoittamana etsin itsekin käsin 20-ratkaisun, vaikken tiedä onko se paras mahdollinen. Jos joku pääsee sen alle, täytyy paremmalla ajalla toteuttaa miettimäni algoritmi, joka ratkaisee ainakin helpomman tehtävän optimaalisesti. Vaikeampi versio voi vaatia jotain nerokkaampaa.

Merri [27.04.2009 22:32:54]

#

Säilöökö tuo useampia vastauksia? Ajattelin lähetellä pari erilaista vastausta, jotka pyrkivät välttämään tuon 20-vastauksen.

Antti Laaksonen [27.04.2009 22:56:11]

#

Vain paras lähetetty vastaus näkyy sivulla. Kaikki vastaukset jäävät kyllä tietokantaan, mutta niitä ei toistaiseksi voi katsella mitenkään.

Merri [02.05.2009 14:45:07]

#

Hassua että tuossa 21:n ja 24:n välissä on tyhjä kuoppa johon ei ole tullut yhtään vastauksia. Pitänee antaa vinkki, ettei kukaan ole kieltänyt tekemästä vain yhtä riviä...

Metabolix [02.05.2009 14:46:38]

#

Merri kirjoitti:

Hassua että tuossa 21:n ja 24:n välissä on tyhjä kuoppa johon ei ole tullut yhtään vastauksia.

Miksipä kukaan haluaisi erityisesti tähdätä tuohon väliin, kun parempiakin ratkaisuja on olemassa?

Antti Laaksonen [02.05.2009 15:03:07]

#

Kuitenkin on ihan kiinnostava havainto, että kaikki ruudukon koot 20:stä eteenpäin ovat mahdollisia.

Merri [02.05.2009 17:41:28]

#

Metabolix: ainakin minusta on tylsää pyrkiä semmoiseen johon on tullut jo puolet vastauksista, varsinkin kun tämä ei ole mikään palkintokilpailu (eikä toimisikaan sellaisena). Siksi vaihtoehtoiset haasteet ovat ihan kivoja.

Yksi hauska tempaus olisi tehdä vaikka mahdollisimman pieni kolmio, jossa numerot esiintyvät, tosin pienin kolmio johon kaikki numerot mahtuvat lienee 25 ruudun kokoinen. Siitä seuraavaksi pienemmässä olisi käytettävissä enää 16 ruutua.

    *
   ***
  *****
 *******
*********

jlaire [02.05.2009 18:23:46]

#

Merri kirjoitti:

Yksi hauska tempaus olisi tehdä vaikka mahdollisimman pieni kolmio, jossa numerot esiintyvät

Tai sitten voisi sallia minkä vaan muodon, eli suorakulmion sisään jääviä "reikiä" ei lasketa. Löysin ainakin 19-ruutuisen ratkaisun, parempikin saattaa olla mahdollinen.

Huomasin muuten, että kahden ensimmäisen putkapostin esimerkkivastauksiin ei enää linkitetä tehtäväsivulla, ja niihin saa taas lähettää vastauksia. Ruudukkoanagrammi on tosi hyvä tehtävä.

Merri [02.05.2009 18:29:03]

#

Minunkin ratkaisuni on 19-ruutuinen jos kaksi turhanpäiväistä laskee pois. Ne on samassa läjässä. 18 ruutua lienee mahdollinen jos ihan minkä tahansa muodon sallii.

jlaire [02.05.2009 18:34:05]

#

Merri kirjoitti:

18 ruutua lienee mahdollinen jos ihan minkä tahansa muodon sallii.

Näin on asia. Tämän spoilaaminen tuskin haittaa, koska varsinaiseen tehtävään tästä ei saa kunnon ratkaisua ilman isoja muutoksia.

Rot5:

          6
    8     1
  1   7 3 4
6 5 5 9 9 6
      1 0 7 7
          6

Antti Laaksonen [02.05.2009 18:41:48]

#

Tämä on kiinnostava jatkotehtävä. Ehdoton ratkaisun alaraja on 13 ruutua, koska numeroita 0, 1, 2 ja 4 tarvitaan varmasti kaksi kutakin ja numeroita 3, 5, 6, 8 ja 9 tarvitaan varmasti yksi kutakin.


Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta