Seuraa 
Viestejä956

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

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. 

mdmx
Seuraa 
Viestejä6415

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ä.

Sisältö jatkuu mainoksen alla
Sisältö jatkuu mainoksen alla
pöhl
Seuraa 
Viestejä956

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

Sisältö jatkuu mainoksen alla

Uusimmat

Suosituimmat