Word Spinner Puzzle

10

Este é um quebra-cabeça de palavras.

Seu programa deve aceitar duas palavras na entrada padrão.
A primeira palavra é a palavra inicial. A palavra dois é a palavra final.

Desde a palavra inicial, você deve chegar à palavra final alterando / adicionando / removendo uma letra de cada vez. Após cada modificação, ele deve formar uma nova palavra válida. As letras adicionadas são adicionadas ao começo ou ao fim. Você pode remover letras de qualquer local (mas a palavra não deve ficar abaixo de três letras). Nota: Você não pode reorganizar as letras para formar uma palavra.

A saída do programa é a sequência de palavras que vão da palavra inicial à palavra final.

Exemplo:

Input:
    Post Shot

Output:
    Post
    cost
    coat
    goat
    got
    hot
    shot

Vencedora:

  • O programa deve ser executado em um tempo razoável (menos de 10 segundos).
  • O programa que pode gerar a menor sequência de saída para as palavras do prêmio.
    • Zink -> Silício
  • Se mais de um programa obtiver a menor sequência, o menor programa em caracteres (ignorando o espaço em branco).
  • Se ainda tivermos mais de uma data / hora de envio do programa, será usada.

Notas:

Martin York
fonte
pode ser "pós-> panela-> quente-> injeção" é mais curto.
VOCÊ
@ S.Mark: Então seu algoritmo vence o meu e você vence. O exemplo acima é um exemplo de uma possível solução. Uma solução mais curta supera uma solução mais longa.
Martin York
intencionalmente? desculpe, eu só entendi errado.
VOCÊ
2
Eu poderia resolvê-lo no espaço em branco para o tamanho do programa 0?
@ Tim Nordenfur: Eu adoraria ver uma implementação de espaço em branco. Nota. Existem duas regras antes da duração do programa para decidir o vencedor. Mas se você atender a esses requisitos :-)
Martin York

Respostas:

2

Python, 288 caracteres

(sem contar a linha de leitura do dicionário)

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

para o desafio zinkde silicon:

ZINK
PINK
PANK
PANI
PANIC
PINIC
SINIC
SINICO
SILICO
SILICON

Existem algumas palavras estranhas nesse dicionário ...

Keith Randall
fonte
Na verdade, eu não verifiquei o conteúdo. Eu apenas tentei encontrar um dicionário que todo mundo pudesse usar.
Martin York
tentar com guester overturn(leva algum tempo) ou regatta gyrally(não retorna) ;-)
Arnaud Le Blanc
Sim, algumas combinações demoram um pouco. O tempo aumenta, à medida que a solução mais curta aumenta. E o último não tem solução - não há especificações para o que deve acontecer nesse caso :) É bem fácil modificar para manipulá-lo (salve um identificador em G.copy () e compare G com ele no final do loop )
21411 Keith Randall
16

traceroute - 10 caracteres

traceroute 

detalhe

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

Os roteadores são pré-configurados com o OSPF ativado e organizados dessa maneira.

insira a descrição da imagem aqui

E sim, preciso de 233614 roteadores para dar suporte total a todas as palavras. :-)

VOCÊ
fonte
Muito esperto, mas você falha na regra dos 10 segundos. Você levará mais de 10 segundos para configurar todos os roteadores. :-) Qual é a rota de: Zink -> Silicon
Martin York
@ Martin, por favor, ignore o tempo de configuração, assim como criar dicionário, heheh, rotas para o Zink -> Silicon é que zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->siliconeu estou realmente tentando com o algoritmo Dijkstra (que é usado no OSPF) e ele pode encontrar esse caminho em torno de 1s, postá-lo em post separado mais tarde, uma vez que eu jogava golfe.
VOCÊ
3

PHP - 886 689 644 612

Carregamento do dicionário:

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

Código real (concat apenas ambos):

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;}}}

uso:

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

Resultado:

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

Isso deve ser executado em menos de 0,5 segundo para o 'Zink Silicon' e menos de 1 segundo na maioria dos casos (às vezes mais quando não existe solução, mas a soleira volta).

Isso usa o algoritmo A * com distância de levenshtein para estimar os limites mais baixos das distâncias.

Alguns testes interessantes:

  • vas arm-> vas bas bar barm arm(com uma palavra maior que o início e o fim)
  • oxy pom -> oxy poxy poy pom
  • regatta gyrally -> (nenhum, mas o script termina corretamente)
  • aal presolution -> +8 caracteres
  • lenticulated aal -> -9 caracteres
  • acarology lowness -> 46 saltos
  • caniniform lowness -> 51 saltos
  • cauliform lowness -> 52 saltos
  • overfoul lowness -> 54 saltos
  • dance facia -> algumas palavras no caminho têm mais 4 caracteres do que o início / fim
user300
fonte
Tente Zink Silicon
Martin York
Isso deve funcionar, agora :-)
Arnaud Le Blanc
Vou encontrar uma máquina maior:PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes)
Martin York
Você acabou de atingir a configuração 128M memory_limit ;-) Tente com php -dmemory_limit=256M.
Arnaud Le Blanc
had->handnão é uma jogada válida, você só pode adicionar uma letra ao começo ou ao fim. Mesmo para vest->verst:-)
Arnaud Le Blanc
3

Pitão

Como eu não conseguia usar códigos dijkstra de golfe para compactar até algumas centenas de bytes, aqui está a minha versão não destruída.

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()

Testes

$ 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'

Adicionados testes do 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'

Um pouco mais

$ 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'
VOCÊ
fonte
3 <= len(x) <= max(map(len, [nodea, nodeb]))é garantido que o caminho nunca passará por uma palavra mais do que as palavras inicial e final?
Arnaud Le Blanc
Tente com oxy pom; caminho mais curto é oxy->poxy->poy->pom. Também é Parece que você permitir permutações e inserções em qualquer lugar, que não são permitidos :-)
Arnaud Le Blanc
@ user300, permutações fixas e partes de inserções, copiei demais, obrigado ;-) e estou definindo o limite inicial para 5 caracteres e permitindo que mais 1 caractere inicie e termine palavras, deixe-me saber se isso ainda é um problema. obrigado.
VOCÊ