Seuraa 
Viestejä919
Liittynyt19.3.2005

Näin netissä tällaisen ongelman vailla vastausta: Onko olemassa 9x13 -matriisia, jonka jokainen alkio on kokonaisluku väliltä 0,...,9 ja josta voidaan lukea lukujen 1,...,100 neliöt? Tässä lukeminen tarkoittaa sitä, että kiinnitetään alkukohta ja mennään 0-5 askelta kiinnitettyyn suuntaan ja katenoidaan luvut. Siis jos löytyy peräkkäiset luvut 1,0,0,0,0, on löydetty luvun 100 neliö. Miten tällainen ratkaistaan? Ilmeisesti vaatii ohjelmointia ja jonkun tehokkaan algoritmin.

Kommentit (5)

kfa
Seuraa 
Viestejä2517
Liittynyt13.3.2008

Tuo on sanaristikon luomista. Haku sanoilla Crossword puzzle algorithm kertoo että ongelma kuuluu luokkaan NP-complete. Ei mikään ihme että ongelmaan ei ole esitetty ratkaisua. 

Kim Fallström kfa+news@iki.fi

mdmx
Seuraa 
Viestejä5267
Liittynyt23.11.2009

Jos on tarpeeksi aikaa käytössä, voi tietysti iteroida kaikki 10^(9*13) vaihtoehtoa ja tarkastaa vain löytyykö tarvittavat numero jonot.

Mutta tuo on senverta monimutkainen että miljoona iteraatio sekunnissa on jo aika kova. Ja sillä vauhdilla iteroinnissa kestäisi ~3.17e+103 vuotta.

Ensimmäinen steppi olisi optimoida niin että pyöritellään matriisissa aina vain niitä numeroita jotka esiintyvät 1...100 neliöissä. Ensin voisi vaikka pistää nuo neliöt listaan ja laskea montako kertaa jokainen numero 0..9 niissä yhteensä esiintyy. Sit voisi ehkä painotella ton mukaan.

Listalta voisi hakea myös kahden numeron sarjoja.

Ei tää kyllä ihan pala kakkua ole suorittaa missään järjellisessä ajassa. Jos on ~3.17e+103 vuotta aikaa ajella simulaatioo niin sit koodin kirjoittaisi päivässä.

pöhl
Seuraa 
Viestejä919
Liittynyt19.3.2005

mdmx kirjoitti:

Ensimmäinen steppi olisi optimoida niin että pyöritellään matriisissa aina vain niitä numeroita jotka esiintyvät 1...100 neliöissä. Ensin voisi vaikka pistää nuo neliöt listaan ja laskea montako kertaa jokainen numero 0..9 niissä yhteensä esiintyy. Sit voisi ehkä painotella ton mukaan.

No mun eka optimointi oli poistaa listasta kaikki ne jotka esiintyvät toisen neliön alimerkkijonoina

def substringSieve(string_list):
string_list.sort(key=lambda s: len(s), reverse=True)
out = []
for s in string_list:
if not any([s in o for o in out] ) and not any([s[::-1] in o for o in out]):
out.append(s)
return out

A = list()
for i in range(1,101):
A.append(str(i*i))
B = substringSieve(A)
print(B)
print(len(B))

Tulosti

['10000', '1024', '1089', '1156', '1225', '1296', '1369', '1444', '1521', '1600', '1681', '1764', '1849', '1936', '2025', '2116', '2209', '2304', '2401', '2500', '2601', '2704', '2809', '2916', '3025', '3136', '3249', '3364', '3481', '3600', '3721', '3844', '3969', '4096', '4225', '4356', '4489', '4624', '4761', '4900', '5041', '5184', '5329', '5476', '5625', '5776', '5929', '6084', '6241', '6400', '6561', '6724', '6889', '7056', '7225', '7396', '7569', '7744', '7921', '8100', '8281', '8464', '8649', '8836', '9025', '9216', '9409', '9604', '121', '169', '196', '256', '289', '361', '484', '529', '576', '676', '729', '784', '841']
81

Mutta mietin jotain sopivaa best-first searchia tai A*:ä. Paljonkohan kestäisi? Vissiin liikaa. Ongelmaan on ratkaisu 11x11-ruudukossa, http://stackoverflow.com/questions/3382859/solving-a-recreational-square... , mutta miten helppoa tuo on muuttaa pienempään ruudukkoon?

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat