Scralphabet
Um pacote normal de ladrilhos de Scrabble contém as seguintes letras ( ?
é um ladrilho em branco, que pode representar qualquer outra letra):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??
As letras têm o seguinte valor:
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
Dada uma pilha normal de peças do Scrabble, construa o conjunto de palavras que não se cruzam com maior pontuação (ou seja, palavras individuais, não em um quadro do Scrabble), considerando as seguintes condições:
- A pontuação para cada palavra é
sum(letter_values) * length(word)
. - Você só pode incluir no máximo uma palavra começando com cada letra do alfabeto (no máximo 26 palavras).
- Somente palavras válidas do Scrabble ( deste dicionário ) podem ser incluídas. Você pode ler o dicionário de um arquivo, codificá-lo (ugh) ou copiá-lo do site.
- Você não precisa usar todos os blocos, mas todos os blocos não utilizados formam uma única palavra, pontuada da mesma maneira, o que subtrai a sua pontuação.
Se desejar, seu código pode aceitar duas entradas: o conteúdo da bolsa como uma string e os valores da letra em algum formato semelhante a um python dict
(como acima); Como alternativa, você pode codificar o conteúdo da bolsa e os valores das letras. Ele deve exibir as palavras em seu conjunto, suas respectivas pontuações e sua pontuação total, em algum formato razoável.
O conjunto de palavras com maior pontuação ganha, com os empates sendo publicados pela primeira vez.
fonte
print"FOO18\nBAR15\nBAZ42\n...\n1523"
?Respostas:
C, 2765 (ideal)
Editar
Agora tudo em um único arquivo C. Isso apenas encontra todas as soluções ideais. Todos eles devem ter 6 palavras de 15 letras e uma palavra de 10 letras composta por 8 letras de valor 1 e dois espaços em branco. Para isso, preciso carregar apenas uma fração do dicionário e não preciso procurar palavras de 15 letras com espaços em branco. O código é uma pesquisa exaustiva simples e profunda.
Uso:
Observe que todas as soluções são impressas duas vezes porque, ao adicionar uma palavra 'W' de 15 letras, dois pedidos são criados porque existem dois blocos 'W'.
A primeira solução encontrada com a repartição de pontos:
Editar: explicação
O que torna possível pesquisar todo o espaço? Ao adicionar uma nova palavra, apenas levo em conta as palavras que têm a letra restante mais rara. De qualquer maneira, esta carta deve conter alguma palavra (e uma palavra de 15 letras, pois não será um valor com 1 valor, embora eu não verifique isso). Então, eu começo com palavras
J, Q, W, W, X, Z
que contêm as que contam50, 100, 100, 100, 200, 500
. Nos níveis mais baixos, recebo mais pontos de corte porque algumas palavras são eliminadas pela falta de letras. Largura da árvore de pesquisa em cada nível:É claro que se obtém muito ponto de corte ao não se verificar soluções não ideais (espaços em branco com 15 letras ou palavras mais curtas). Portanto, é uma sorte que a solução 2765 possa ser alcançada com este dicionário (mas foi por pouco, apenas 2 combinações de palavras de 15 letras dão uma sobra razoável). Por outro lado, é fácil modificar o código para encontrar combinações de pontuação mais baixa, onde nem todas as 10 letras restantes têm valor 1, embora seja mais difícil provar que essa seria uma solução ideal.
Além disso, o código mostra casos clássicos de otimização prematura. Esta versão da
matches
função torna o código apenas 30% mais lento:Eu até descobri como fazer a comparação paralela de bits mágica ainda mais curta do que no meu código original (a mordidela mais alta não pode ser usada nesse caso, mas isso não é um problema, pois eu só preciso de 26 das 32 mordidelas):
Mas dá zero vantagem.
Editar
Ao escrever a explicação acima, percebi que a maior parte do tempo é gasta na varredura da lista de palavras para aquelas que contêm uma letra específica que não está na
matches
função. O cálculo antecipado das listas deu 10x aceleração.fonte
Python 2, pontuação:
18402162Esse programa primeiro encontra a melhor palavra de pontuação disponível com os blocos fornecidos (sem usar caracteres curinga) e, em seguida, faz 10000 tentativas para incluir palavras aleatórias que atendam às restrições do primeiro caractere exclusivo e com blocos disponíveis. Com as constantes atuais, o programa leva 27 segundos para rodar na minha máquina. Usar constantes maiores provavelmente encontraria uma combinação de palavras com pontuação mais alta.
ATUALIZAÇÃO: Agora usa um algoritmo de seleção de 2 estágios, para encontrar o melhor de 50 palavras em cada estágio selecionado. A pontuação da penalidade agora também é usada no algoritmo de avaliação.
Incluo aqui a melhor de algumas corridas:
Observe que eu não uso os curingas e pago uma penalidade maior (devido ao tamanho da palavra). Um aprimoramento futuro pode incluir o uso de curinga.
fonte
Recozimento simulado (pontuação 2246)
Infelizmente isso não é determinístico. Vou tentar consertar isso e encontrar uma semente determinística que dê um valor melhor.
fonte
Python, score
263826752676268926992717Resultado:
Código:
Explicação:
Pesquisa em profundidade, que pesquisa a árvore inteira, escolhendo entre as
picks
melhores palavras principais em cada estágio.Classifico a lista de palavras inteira uma vez por pontuação no início. Depois de escolher cada palavra, para a próxima iteração, filtro todas as palavras que não são mais possíveis agora, preservando a ordem, para que eu não precise classificar a lista a cada etapa. Para lidar com curingas, se houver a possibilidade de um curinga ser necessário, eu escolho os 10000 candidatos principais, substituo as letras ausentes por curingas, se necessário, e re-classifico com base nas novas pontuações (inferiores).
Esta saída é para
picks=5
e foi8m01s
executada na minha máquina de 8 núcleos.fonte
Java 8, pontuação
26412681O programa começa com as 40 melhores palavras. Para cada palavra, encontra as 40 melhores palavras para seguir adiante. Das 1600 combinações, o programa obtém as melhores 40. Para cada combinação, as 40 melhores palavras são encontradas e o ciclo se repete.
Quando restam apenas alguns ladrilhos, as letras restantes são combinadas com os dois espaços em branco da palavra final.
Atualizar
Aumentei o limiar para as 50 melhores palavras. Além disso, cada combinação adiciona apenas palavras menores do que as que já estão presentes. Isso evita múltiplas permutações do mesmo grupo.
O programa:
fonte
Perl, pontuação: 2655
2630Usar:
O uso de espaços em branco, na verdade, não fornece muito, enquanto diminui significativamente a execução:
Depois de adicionar algumas heurísticas:
fonte
Python 3, pontuação 2735
(A pontuação ideal de 2765, "6 palavras de 15 letras e uma palavra de 10 letras consistindo em 8 letras de valor 1 e dois espaços em branco" foi alcançada por nutki .)
Eu usei uma abordagem gananciosa semelhante à dos outros:
Começo com listas de um elemento contendo as principais palavras de pontuação que contêm Q's.
A cada passo de cada elemento da lista, crio
k = 800
novas listas com as melhores palavras legais para a lista. A partir da lista agregada de listas, mantenho ask
listas de pontuação mais alta e repito o processo 10 vezes.Observe que você pode obter os
k
elementos principais de uman
lista -long em O (n + k * log n), que é O (n) se,k<<n
como no nosso caso (k = 800, n ~= 250000
), com uma fila de heap. Eu acho que esse método não é usado em outras submissões, daí osk
valores menores .Uso curingas pelo caminho, se necessário, para as palavras.
O tempo de execução é de alguns minutos
k = 800
. Valores maiores e outras otimizações ainda não produziram melhores resultados.Resultado:
Eu experimentei o produto Descartes das melhores palavras que contêm Q, J e X, pois essas letras mal compartilham palavras. Minha melhor pontuação com este startegy foi 2723 (
DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA
).O código espaguete complicado desnecessário (com traços de experimentação com outros métodos):
fonte