Teka-teki Kata Pemintal

10

Ini adalah teka-teki kata.

Program Anda harus menerima dua kata pada input standar.
Kata pertama adalah kata awal. Kata dua adalah kata akhir.

Dari kata awal Anda harus mencapai kata akhir yang mengubah / menambah / menghapus satu huruf sekaligus. Setelah setiap modifikasi itu harus membentuk kata yang valid baru. Surat yang ditambahkan ditambahkan ke awal atau akhir. Anda dapat menghapus huruf dari lokasi mana pun (tetapi panjangnya kata tidak boleh lebih dari tiga huruf). Catatan: Anda tidak dapat mengatur ulang huruf untuk membentuk kata.

Output dari program ini adalah urutan kata-kata yang akan didapat dari kata awal hingga kata akhir.

Contoh:

Input:
    Post Shot

Output:
    Post
    cost
    coat
    goat
    got
    hot
    shot

Pemenang:

  • Program harus berjalan dalam waktu yang wajar (kurang dari 10 detik).
  • Program yang dapat menghasilkan urutan output terpendek ke kata-kata hadiah.
    • Zink -> Silikon
  • Jika lebih dari satu program mendapat urutan terpendek maka program terpendek dalam karakter (mengabaikan ruang putih).
  • Jika kita masih memiliki lebih dari satu tanggal / waktu pengiriman program akan digunakan.

Catatan:

Martin York
sumber
mungkin "post-> pot-> hot-> shot" lebih pendek.
KAMU
@ S.Mark: Lalu algoritme Anda mengalahkan milik saya dan Anda menang. Di atas adalah contoh dari solusi yang mungkin. Solusi yang lebih pendek mengalahkan solusi yang lebih lama.
Martin York
sengaja? maaf, saya baru saja salah.
ANDA
2
Bisakah saya menyelesaikannya di Whitespace untuk ukuran program 0?
@Tim Nordenfur: Saya akan senang melihat implementasi ruang putih. Catatan. ada dua aturan sebelum panjang program untuk memutuskan pemenang. Tetapi jika Anda memenuhi persyaratan itu :-)
Martin York

Jawaban:

2

Python, 288 karakter

(tidak termasuk baris pembacaan kamus)

X=set(open('websters-dictionary').read().upper().split())

(S,E)=raw_input().upper().split()
G={S:0}
def A(w,x):
 if x not in G and x in X:G[x]=w
while E not in G:
 for w in G.copy():
  for i in range(len(w)):
   for c in"ABCDEFGHIJKLMNOPQRSTUVWXYZ":A(w,w[:i]+c+w[i+1:]);A(w,w[:i]+w[i+1:]);A(w,c+w);A(w,w+c)
s=''
while E:s=E+'\n'+s;E=G[E]
print s

untuk tantangan zinkuntuk silicon:

ZINK
PINK
PANK
PANI
PANIC
PINIC
SINIC
SINICO
SILICO
SILICON

Ada beberapa kata aneh di kamus itu ...

Keith Randall
sumber
Saya sebenarnya tidak memeriksa konten. Saya hanya mencoba menemukan kamus yang dapat digunakan semua orang.
Martin York
coba dengan guester overturn(membutuhkan waktu) atau regatta gyrally(tidak kembali) ;-)
Arnaud Le Blanc
Ya, beberapa kombinasi memerlukan waktu. Waktu semakin lama karena solusi terpendek semakin lama. Dan yang terakhir tidak memiliki solusi - tidak ada spesifikasi untuk apa yang harus terjadi dalam kasus itu :) Cukup mudah untuk memodifikasi untuk menanganinya (menyimpan pegangan ke G. copy () dan membandingkan G dengan itu di akhir loop ).
Keith Randall
16

traceroute - 10 karakter

traceroute 

detail

post#traceroute shot

Type escape sequence to abort.
Tracing the route to shot (1.1.4.2)

  1 pot (1.1.1.2) 40 msec 68 msec 24 msec
  2 hot (1.1.3.2) 16 msec 32 msec 24 msec
  3 shot (1.1.4.2) 52 msec *  92 msec

Router sudah dikonfigurasikan sebelumnya dengan OSPF diaktifkan dan diatur dengan cara ini.

masukkan deskripsi gambar di sini

Dan ya, saya membutuhkan 23.314 router untuk sepenuhnya mendukung semua kata. :-)

KAMU
sumber
Sangat pintar tetapi Anda gagal aturan 10 detik. Anda akan membutuhkan waktu lebih dari 10 detik untuk mengkonfigurasi semua router. :-) Whats rute dari: Zink -> Silicon
Martin York
@ Martin, tolong abaikan untuk waktu konfigurasi, itu seperti membangun kamus, heheh, rute untuk Zink -> Silicon adalah zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->siliconsaya benar-benar mencoba dengan algoritma Dijkstra (yang digunakan dalam OSPF) dan dapat menemukan jalur sekitar 1s, saya akan posting di pos terpisah nanti, setelah saya bermain golf.
ANDA
3

PHP - 886 689 644 612

Memuat kamus:

<?php foreach(file('websters-dictionary') as $line) {
    $word = strtolower(trim($line));
    if (strlen($word) < 3) continue;
    $c[$word] = 1;
}

Kode aktual (hanya untuk keduanya):

list($d,$e)=explode(' ',strtolower(trim(`cat`)));$f=range(@a,@z);function w($a,&$g){global$c;if(isset($c[$a]))$g[]=$a;}$h[$d]=$b=@levenshtein;$i=new SplPriorityQueue;$i->insert($d,0);$j[$d]=0;$k[$d]=$b($d,$e);while($h){if(isset($c[$l=$i->extract()])){unset($h[$l],$c[$l]);if($l==$e){for(;$m=@$n[$o[]=$l];$l=$m);die(implode("\n",array_reverse($o)));}for($p=strlen($l),$g=array();$p--;){w(substr_replace($q=$l,"",$p,1),$g);foreach($f as$r){$q[$p]=$r;w($q,$g);w($r.$l,$g);w($l.$r,$g);}}foreach($g as$m){$s=$j[$l]+1;if(!isset($h[$m])||$s<$j[$m]){$n[$m]=$l;$i->insert($m,-(($k[$m]=$b($m,$e))+$j[$m]=$s));}$h[$m]=1;}}}

pemakaian:

php puzzle.php <<< 'Zink Silicon'
# or
echo 'Zink Silicon'|php puzzle.php

Hasil:

zink
pink
pank
pani
panic
pinic
sinic
sinico
silico
silicon
(0.23s)

Ini harus berjalan dalam waktu kurang dari 0,5 detik untuk 'Zink Silicon', dan kurang dari 1 detik untuk sebagian besar kasus (kadang-kadang lebih lama ketika tidak ada solusi, tetapi masih kembali).

Ini menggunakan algoritma A * dengan levenshtein distance untuk memperkirakan batas jarak yang lebih rendah.

Beberapa tes simpang:

  • vas arm-> vas bas bar barm arm(dengan kata yang lebih panjang dari awal dan akhir)
  • oxy pom -> oxy poxy poy pom
  • regatta gyrally -> (tidak ada, tetapi skrip berakhir dengan benar)
  • aal presolution -> +8 karakter
  • lenticulated aal -> -9 karakter
  • acarology lowness -> 46 hop
  • caniniform lowness -> 51 hop
  • cauliform lowness -> 52 hop
  • overfoul lowness -> 54 hop
  • dance facia -> beberapa kata di jalur memiliki 4 karakter lebih banyak daripada keduanya mulai / berakhir
pengguna300
sumber
Coba Zink Silicon
Martin York
Ini seharusnya bekerja, sekarang :-)
Arnaud Le Blanc
Saya akan menemukan mesin yang lebih besar:PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes)
Martin York
Anda baru saja menekan pengaturan 128M memory_limit ;-) Coba dengan php -dmemory_limit=256M.
Arnaud Le Blanc
had->handbukan langkah yang valid, Anda hanya dapat menambahkan surat ke awal atau akhir. Sama untuk vest->verst:-)
Arnaud Le Blanc
3

Python

Karena saya tidak bisa memasukkan kode golf untuk dikompres ke beberapa ratus byte, ini adalah versi saya yang tidak diklik.

import sys, heapq, time

# dijkstra algorithm from 
# http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
def dijkstra(G, start, end):
   def flatten(L):
      while len(L) > 0:
         yield L[0]
         L = L[1]

   q = [(0, start, ())]
   visited = set()
   while True:
      (cost, v1, path) = heapq.heappop(q)
      if v1 not in visited:
         visited.add(v1)
         if v1 == end:
            return list(flatten(path))[::-1] + [v1]
         path = (v1, path)
         for (v2, cost2) in G[v1].iteritems():
            if v2 not in visited:
               heapq.heappush(q, (cost + cost2, v2, path))

nodes = tuple(sys.argv[1:])

print "Generating connections,",
current_time = time.time()

words = set(x for x in open("websters-dictionary", "rb").read().lower().split() if 3 <= len(x) <= max(5, *[len(l)+1 for l in nodes]))

print len(words), "nodes found"

def error():
    sys.exit("Unreachable Route between '%s' and '%s'" % nodes)

if not all(node in words for node in nodes):
    error()

# following codes are modified version of
# http://norvig.com/spell-correct.html
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits(word):
   splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes = [a + b[1:] for a, b in splits if b]
   replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   prepends = [c+word for c in alphabet]
   appends = [word+c for c in alphabet]
   return words & set(deletes + replaces + prepends + appends)

# Generate connections between nodes to pass to dijkstra algorithm
G = dict((x, dict((y, 1) for y in edits(x))) for x in words)

print "All connections generated, %0.2fs taken" % (time.time() - current_time)
current_time = time.time()

try:
    route = dijkstra(G, *nodes)
    print '\n'.join(route)
    print "%d hops, %0.2fs taken to search shortest path between '%s' & '%s'" % (len(route), time.time() - current_time, nodes[0], nodes[1])
except IndexError:
    error()

Tes

$ python codegolf-693.py post shot
Generating connections, 15930 nodes found
All connections generated, 2.09s taken
post
host
hot
shot
4 hops, 0.04s taken to search shortest path between 'post' & 'shot'

$ python codegolf-693.py zink silicon
Generating connections, 86565 nodes found
All connections generated, 13.91s taken
zink
pink
pank
pani
panic
pinic
sinic
sinico
silico
silicon
10 hops, 0.75s taken to search shortest path between 'zink' & 'silicon'

Menambahkan Tes user300

$ python codegolf-693.py vas arm
Generating connections, 15930 nodes found
All connections generated, 2.06s taken
vas
bas
bam
aam
arm
5 hops, 0.07s taken to search shortest path between 'vas' & 'arm'

$ python codegolf-693.py oxy pom
Generating connections, 15930 nodes found
All connections generated, 2.05s taken
oxy
poxy
pox
pom
4 hops, 0.01s taken to search shortest path between 'oxy' & 'pom'

$ python codegolf-693.py regatta gyrally
Generating connections, 86565 nodes found
All connections generated, 13.95s taken
Unreachable Route between 'regatta' and 'gyrally'

Lebih lagi

$ python codegolf-693.py gap shrend
Generating connections, 56783 nodes found
All connections generated, 8.16s taken
gap
rap
crap
craw
crew
screw
shrew
shrewd
shrend
9 hops, 0.67s taken to search shortest path between 'gap' & 'shrend'

$ python codegolf-693.py guester overturn
Generating connections, 118828 nodes found
All connections generated, 19.63s taken
guester
guesten
gesten
geste
gest
gast
east
ease
erse
verse
verset
overset
oversee
overseed
oversend
oversand
overhand
overhard
overcard
overcare
overtare
overture
overturn
23 hops, 0.82s taken to search shortest path between 'guester' & 'overturn'
KAMU
sumber
3 <= len(x) <= max(map(len, [nodea, nodeb]))apakah dijamin bahwa jalan setapak tidak akan pernah melewati kata yang lebih lama dari kata awal dan akhir?
Arnaud Le Blanc
Coba dengan oxy pom; jalur terpendek adalah oxy->poxy->poy->pom. Juga tampaknya Anda mengizinkan permutasi dan penyisipan di mana saja, yang tidak diizinkan :-)
Arnaud Le Blanc
@ user300, memperbaiki permutasi dan memasukkan bagian, saya salin-tempel terlalu banyak, terima kasih ;-) dan saya menetapkan batas awal hingga 5 karakter dan memungkinkan +1 lebih banyak karakter memulai dan mengakhiri kata-kata, beri tahu saya jika itu masih menjadi masalah. Terima kasih.
ANDA