Vanhassa Suomen Kuvalehdessä (20-luvulta!) oli mainio laskutehtävä, josta on varmaan iloa teillekin.
Kuinka monella tavalla seuraavasta ruudukosta voi lukea sanan SAIPPUAKAUPPIAS?
SAIPPUAKAUPPIAS AIPPUAKAUPPIASA IPPUAKAUPPIASAI PPUAKAUPPIASAIP PUAKAUPPIASAIPP UAKAUPPIASAIPPU AKAUPPIASAIPPUA KAUPPIASAIPPUAK AUPPIASAIPPUAKA UPPIASAIPPUAKAU PPIASAIPPUAKAUP PIASAIPPUAKAUPP IASAIPPUAKAUPPI ASAIPPUAKAUPPIA SAIPPUAKAUPPIAS
Sana saa alkaa mistä tahansa, ruudukossa saa edetä pysty- ja vaakasuuntaan, ja samaan kohtaan saa mennä monta kertaa.
Vastauksia ja ratkaisutapoja saa lähettää tähän keskusteluun.
Vaikutti aluksi helpolta, mutta kun luki eteenpäin Antin selostusta, tulinkin toisiin aatoksiin. Mutta sanon tässä pelkän vastauksen sen mitä aluksi tajusin 2. riviltä Antin viestistä
32
Onkyllä toinen vaihtoehto, mutta tämä saa kelvata aluksi, kun en oo kovin haka tämmösissä vielä ;)
Vastaan 327675, missä voi olla vähän liikaa koska en jaksa lähteä miettimään asiaa sen enempää kuin että aivan tolkuttomasti noita kuitenkin tulee, jos saa kääntyillä "mielivaltaisesti" aina lähimpään sopivaan kirjaimeen.
Muoks!
Lisämietinnällä päivitetty toistamiseen. Jaksaisikin koodata tuon selvittäjän, parempi tekemään semmoisen kuin laskemaan omassa päässä.
No ihan tyhmää, nyt tämä estää jo muokkaamisen kun sekoilen kahden vaiheilla väsyneenä :P Elikkä no, se toinen veikkaus joka oli jo jonkun aikaa aiemmin esillä on 491520.
Itse sain pikaisella viritelmällä 680488. Liekö sitten jossain tullut virhe, en tiedä.
Oikeaa vastausta ei ole vielä tullut, mutta yksi on ollut aika lähellä...
No jos arvaan jälkimmäiselleni nyt sitten 491492 kun en edelleenkään jaksa koodata tarkistajaa. Tai ehkä vain teen sen ja annan laskea paremmin puolestani. Ehkä pitäisi nukkua pidemmät unet tällekin päivälle.
32768?
Kenties 334544?
(334544 == 2* Summa_{i käy 0:sta 7:ään} [(2^7 + (7 yli iin))^2] )
VilleP kirjoitti:
Kenties 334544?
Oikein meni! Aika lyhyen laskukaavankin sait aikaan.
Olisi kiva kuulla kaavan perustelut, niin oppisin itsekin laskemaan tuollaisia kombinatoriikan tehtäviä.
Tässäpä vieläkin lyhyempi kaava: 2^16+2^18+2*(14 yli 7:n). Tuon sain tosin perusteltua helpoiten sieventämällä alkuperäistä kaavaa, joten en sanoisi sitä varsinaiseksi parannukseksi.
Jaskalle täsmennystä, perusideana oli laskea erikseen jokaiselle K-kirjaimiselle ruudulle, kuinka monella tavalla siitä lähtien voidaan muodostaa tehtävän mukaisesti liikkumalla sana KAUPPIAS. Jos tämä lukumäärä on jollekin K-ruudulle N, niin tällöin sana SAIPPUAKAUPPIAS saadaan muodostettua (käyttämällä kyseenomaista K-ruutua SAIPPUAKAUPPIAS-sanan keskimmäisenä Koona) N^2 eri tavalla. Tämä johtuu siitä, että kullakin SAIPPUAKAUPPIAS-reitillä on ensin 'peruutettava' jotain KAUPPIASta pitkin ensimmäisestä ässästä K-kirjaimeen, ja tämän jälkeen jatkettava eteenpäin jotain KAUPPIASta (samaa tai eri kuin alussa) pitkin K:sta viimeiseen ässään.
Koska K-ruutuja on 16 kpl, saadaan lopulliseksi lukumääräksi Summa{i=0..15}[N_i ^2]. Ruudukko on pistesymmetrinen keskipisteensä suhteen, joten lkm on itse asiassa 2*Summa{i=0..7}[N_i ^2], kun K-ruudut numeroidaan ilmiselvässä järjestyksessä (ylhäältä alas, vasemmalta oikealle).
Ongelmaksi jää enää laskea erikseen kukin N_i. Tässä auttaa, kun huomataan, että siirryttäessä ruudukossa yhden ruudun verran alas tai oikealle, siirtyy vastaavan kirjaimen kohta sanassa SAIPPUAKAUPPIAS aina yhden kirjaimen verran oikealle/eteenpäin. Esim. jos kuljetaan vasemmasta ylänurkasta reittiä alas/oikea/alas/o/o/a/o/a..., ovat vastaavat kirjaimet S->A->I->P->P->U->A->K->... . Vastaavasti, kun liikutaan ruudukossa ylös tai vasemmalle, siirrytään SAIPPUAKAUPPIAS-kirjaimissa aina yhden verran taaksepäin/vasemmalle.
Helposti voi nähdä, että esimerkiksi ylhäältä laskettuna kolmannesta K-ruudusta (vastaa indeksiä i = 2) saadaan aikaiseksi oikeaoppinen KAUPPIAS-reitti ainoastaan kulkemalla joko koko ajan oikealle_tai_alas, tai vaihtoehtoisesti koko ajan vasemmalle_tai_ylös, astumatta kuitenkaan ruudukon reunan yli. Oikealle/alas -reittejä on 2^7 erilaista kappaletta ja vasemmalle/ylös -reittejä on (7 yli i) = (7 yli 2) kappaletta. Jälkimmäisen voi nähdä siitä, että ylöspäin siirtymisiä on oikeaoppisella vasemmalle/ylös -reitillä oltava tasan 2 kappaletta (jotta päästäisiin vasemman ylänurkan S-kirjaimeen asti ensimmäiselle riville), ja kaiken kaikkiaan siirtymisiä yhteensä on ko. reitillä oltava yhtä monta kuin KAUPPIAS-sanassa on kirjaimia - 1 eli 8-1=7, joten tapoja valita oikeaoppinen ylös/vasen -reitti on sama kuin tapoja valita 2 käännöstä 7:stä eli (7 yli 2). Kun tuon yleistää jokaiselle vasemman yläalueen K-kirjaimelle, saadaan alunperin esitetty kaava.
Täytyy varmaan odotella pari vuotta että ymmärtää nuo ^^
=D
Tuloksen voi tarkistaa yksinkertaisella syvyyshaulla.
Optimointi ei ole mielekästä, sillä ohjelma toimii jo nyt salamannopeasti.
#include <iostream>
using namespace std;
char *word="SAIPPUAKAUPPIAS";
char *map="SAIPPUAKAUPPIAS"
"AIPPUAKAUPPIASA"
"IPPUAKAUPPIASAI"
"PPUAKAUPPIASAIP"
"PUAKAUPPIASAIPP"
"UAKAUPPIASAIPPU"
"AKAUPPIASAIPPUA"
"KAUPPIASAIPPUAK"
"AUPPIASAIPPUAKA"
"UPPIASAIPPUAKAU"
"PPIASAIPPUAKAUP"
"PIASAIPPUAKAUPP"
"IASAIPPUAKAUPPI"
"ASAIPPUAKAUPPIA"
"SAIPPUAKAUPPIAS";
int dfs(int x, int y, int c){ //c on nykyisen merkin indeksi sanassa 'saippuakauppias'
if(x<0 || x>14 || y<0 || y>14 || map[y*15+x]!=word[c])
return 0;
if(c==14)
return 1;
return dfs(x-1,y,c+1) + dfs(x+1,y,c+1) + dfs(x,y-1,c+1) + dfs(x,y+1,c+1);
}
int main(int argc, char* argv[]){
int x,y,count;
count=0;
for(y=0;y<15;y++){
for(x=0;x<15;x++){
count+=dfs(x,y,0);
}
}
cout << count << endl;
}Ja tulokseksi tulee sama 334544
Pisteet VilleP:lle ja lukujenVihaajalle selkeistä ratkaisuista.
Mahdollinen lisätehtävä tuli mieleeni.
Polut voi luokitella sen mukaan, kuinka monta käännöstä niissä tehdään. Käännös on sellainen kohta polussa, jossa siirrytään eri suuntaan kuin edellisellä kerralla. Aivan ensimmäinen valinta ei voi olla käännös, joten SAIPPUAKAUPPIAS-sanan pituuden 15 nojalla käännöksiä voidaan tehdä 0-14 kpl. (Jos käännöksiä on nolla, on silloin jokainen siirtyminen samaan suuntaan.)
Jos ei tehdä yhtään käännöstä, pitää aloittaa nurkasta ja mennä toiseen, koska reunalla on S-kirjain vain nurkissa ja 15x15-taulukossa 15:n pituisen suoran täytyy koskea reunoja. Näitä mahdollisuuksia on kaksi per nurkka, eli yhteensä 8.
Mitenkä sitten jatketaan? Montako erilaista polkua on käännöksien lukumäärän ollessa 1-14?
(näitä arvoja voi nimittää n:nen asteen madonluvuiksi...)
Juu. Noinhan tuo meneekin. On kyllä kombinatoriikan taidot päässeet rapistumaan, kun ei ole YO-kirjoitusten jälkeen kovinkaan paljoa tarvinnut.
N:n pituisessa madossa on tietenkin [0..n-2] mutkaa, eli 0-13 on tehtävän väli. Huoh.
juha127 kirjoitti:
Täytyy varmaan odotella pari vuotta että ymmärtää nuo
Tai sitten ei tarvitse. Kokemuksesta voin sanoa, että vaikeitakin asioita voi opiskella nopeasti, jos on motivaatiota ottaa asioista selvää. Voithan kysella kohdista, jotka tuntuvat vaikeilta vaikka tällä palstalla. Joku voi selventää noita juttuja jo parin minuutin päästä, ja opit asioita paljon nopeammin kuin odottamalla lukion kombinatoriikan kurssia. Minä olen aina opiskellut paljon matematiikkaa etukäteen ja mielestäni se on kannattanut.
Kopeekka:
n Madonluku ------------------ 0 8 1 172 2 1392 3 6560 4 20040 5 42596 6 65456 7 74392 8 62488 9 38484 10 16896 11 5064 12 920 13 76
Juu, mitätön, mutta tuhoisa kirjoitusvirhehän se vääristi ohjelmani tuloksen. Todellinen ratkaisu on kuitenkin juuri kynän ja peperin avulla, kuten varmaan tuolloin 20-luvulla. :)
Kiitän lukujenVihaajaa ongelmaani tarttumisesta. En keksinyt hyvää kombinatorista tapaa ratkaista ongelmaani paperilla, joten esitän vain ohjelmallisen ratkaisun. Jos joku keksii elegantin tavan (tuon VilleP:n esittämän kaltaisen), kertokoon.
Voi olla, että sellaista ei ole.
Tässä on Haskell-koodini. Se on kauheaa minustakin. :-)
-- Madonluvut.hs -- Pekka Karjalainen 2006
-- lisenssi: public domain
-- yksinkertainen ratkaisu madonluvut-ongelmaan
-- joka esiintyi Ohjelmointiputkan keskustelussa
-- (Pekan itse esittamana)
module Main where
import Data.Array
import Data.List
data Suunta = Ylos | Vas | Oik | Alas deriving (Eq, Show)
data Paikka = Paikka Int Int
data Rajat = Rajat (Int, Int) (Int, Int)
kaikkiSuunnat = [Ylos, Vas, Oik, Alas]
onkoRajoissa (Rajat (minx, maxx) (miny, maxy)) (Paikka x y) =
minx <= x && x <= maxx && miny <= y && y <= maxy
astu (Paikka x y) s = case s of
Ylos -> Paikka x (y-1)
Vas -> Paikka (x-1) y
Oik -> Paikka (x+1) y
Alas -> Paikka x (y+1)
-- taman voisi jotenkin kirjoittaa paremmin, mutta kun ei keksi miten
vaihtojenLkm [] = error "Vilahti nulli-lista tuloksiin!"
vaihtojenLkm lista = length $ filter (uncurry (/=)) $ zip lista (tail lista)
-- indeksini alkavat yhdesta
indeksiksi (Paikka x y) = (y-1)*15+x
kirjaimet = "SAIPPUAKAUPPIAS"
pituus = length kirjaimet
pitNelio = pituus*pituus
sana = listArray (1,pituus) kirjaimet
taulu = listArray (1,pitNelio) $ take (pitNelio) toisto
where toisto = (init kirjaimet) ++ toisto
oikeaPaikka pari syvyys = taulu ! i == sana ! syvyys
where i = indeksiksi pari
onkoTaulussa = onkoRajoissa $ Rajat (1,pituus) (1,pituus)
-- tehdaanpa sitten negaatiot kuitenkin
eiOikeaPaikka pari syvyys = not $ oikeaPaikka pari syvyys
eiTaulussa = not . onkoTaulussa
bfs paikka suunnat syvyys
| eiTaulussa paikka = [[]]
| eiOikeaPaikka paikka syvyys = [[]]
| syvyys == pituus = [suunnat]
| otherwise = syvenna
where syvenna = [seuraava | s <- kaikkiSuunnat,
let p = astu paikka s,
seuraava <- bfs p (s:suunnat) (syvyys+1),
not $ null seuraava ]
-- tassa ratkaisussa on pieni puute - nimittain se palauttaa nulli-listoja
-- kun aloitetaan paikasta, jossa ei ole S-kirjainta. muuten nulli-osalistat
-- karsitaan haussa pois, joten listat ovat joko taydellisia 14:n suunnan
-- listoja tai nulleja.
-- ratkesi sitten niin, että filtteroin alla (not . null):in avulla ne veks,
-- mutta ratkaisua ei voi pitaa kovin eleganttina. kelvatkoon minulle.
alut = map ($[]) [ bfs $ Paikka x y | x <- [1..15], y <- [1..15]]
tulokset = filter (not . null) $ concatMap ($1) alut
mutkat = map vaihtojenLkm tulokset
tilasto = map length $ group (sort mutkat)
otsikko = "n\tMadonluku\n" ++
"------------------"
tulostus a b = show a ++ "\t" ++ show b
main = do putStrLn otsikko;
mapM putStrLn $ zipWith tulostus [0..] tilasto
-- loppui vihdoin!Saattaapa huomata, että korjailin sen tulostusmuotoilua ennen julkaisua, koska tulostus käy näin hyvin yhteen lV:n esittämään (riippuu tietenkin miten nuo tabit siirtyvät tänne Putkan keskusteluun). Tässä on tulostus ajosta. Meni pieni hetki, en jaksanut mitata montako sekuntia.
n Madonluku ------------------ 0 8 1 172 2 1392 3 6560 4 20040 5 42596 6 65456 7 74392 8 62488 9 38484 10 16896 11 5064 12 920 13 76
Summaksi tulee tietenkin tuo ym. 334544, jonka jokainen voi itse tarkistaa.
MUOKKAUS: oli jotain ohjelman siirtelyn aiheuttamia skandivammoja, jotka toivottavasti nyt on kaikki korjattu. Siitä johtuu kummallinen äö-kirjainten puute suurimmalta osalta. Ja sitten selvisi, että ne olisivat toimineet oikein täällä. Grr tuota MS-DOS-lootaa.
Aihe on jo aika vanha, joten et voi enää vastata siihen.