Minha filha teve a seguinte tarefa para a lição de matemática. Imagine seis amigos vivendo em uma linha, denominados E, F, G, H, J e K. Suas posições na linha são as indicadas abaixo (sem escala):

Assim, F vive cinco unidades de E, e duas unidades de G, e assim por diante.

Sua tarefa: crie um programa que identifique um caminho que visite cada amigo exatamente uma vez com um comprimento total de n unidades, tomando as localizações dos amigos en como entradas. Ele deve relatar o caminho se o encontrar (por exemplo, para o comprimento 17, pode ser "E, F, G, H, J, K", e deve sair normalmente se não houver solução. Pelo que vale a pena, concluí uma solução não destruída no Mathematica em 271 bytes.Eu suspeito que seja possível de forma muito mais concisa do que isso.

J, 54 bytes

Produz uma rota correta. Se nenhuma rota existir, ela não gera nada.

   f=.4 :'{.(x=+/|:2|@-/\"#.s A.y)#(s=.i.!6)A.''EFGHJK'''

   62 f 0 5 7 13 16 17
GJEKFH

Código de 52 bytes que gera todas as rotas (uma por linha):

f=.4 :'(x=+/|:2|@-/\"#.s A.y)#(s=.i.!6)A.''EFGHJK'''

Código de 38 bytes que gera posições em vez de letras:

f=.4 :'p#~x=+/|:2|@-/\"#.p=.(i.!6)A.y'

Mathematica, 55 ou 90 bytes

Mathematica você disse? ;)

FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&

Essa é uma função anônima que primeiro assume as posições dos amigos (em qualquer ordem) e depois o comprimento do alvo. Ele retorna Missing[NotFound], se esse caminho não existir.

FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&[{0, 5, 7, 13, 16, 17}, 62]
(* {7, 16, 0, 17, 5, 13} *)

Posso salvar quatro bytes se o retorno de todos os caminhos válidos for permitido ( FirstCase-> Cases).

Retornar uma matriz de strings é um pouco mais complicado:

FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&

Python 2, 154 148 bytes

(ou 118 bytes para a solução geral)

Este programa aceita uma linha com uma lista e um número inteiro como '[0, 5, 7, 13, 16, 17], n' on stdin e imprime um caminho na saída de comprimento n ou nada, se impossível.

# echo "[0, 5, 7, 13, 16, 17], 62" | python soln.py 
['G', 'J', 'E', 'K', 'F', 'H']

É um desafio escrever pequenos programas em Python que exijam permutações. Essa importação e uso são muito caros.

from itertools import*
a,c=input()
for b in permutations(a):
 if sum(abs(p-q)for p,q in zip(b[1:],b))==c:print['EFGHJK'[a.index(n)]for n in b];break

A fonte do requisito de OP antes do minificador:

from itertools import*

puzzle, goal = input()
for option in permutations(puzzle):
    if sum(abs(p-q) for p,q in zip(option[1:], option)) == goal :
        print ['EFGHJK'[puzzle.index(n)] for n in option];
        break

A solução geral (não minificada):

from itertools import*

puzzle, goal = input()
for option in permutations(puzzle):
    if sum(abs(p-q) for p,q in zip(option[1:], option)) == goal :
        print option;
        break

Devido ao algoritmo simples e ao grande número de combinações, a execução para mais de 20 posições iniciais será muito lenta.

J (48 ou 65)

Eu suponho que isso possa ser jogado muito mais. Sinta-se livre para usar isso como um ponto de partida para jogar ainda mais

]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))

Ou com letras:

([:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#)))))A.[:(a.{~65+[:i.#)]

O que faz:

   62 (]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))) 0 5 7 13 16 17
 7 16  0 17  5 13
 7 16  5 17  0 13
 7 17  0 16  5 13
 7 17  5 16  0 13
13  0 16  5 17  7
13  0 17  5 16  7
13  5 16  0 17  7
13  5 17  0 16  7

(Espero que este formato de E / S esteja bem ...)

Como faz:

(A.~([:i.[:!#))

Gera todas as permutações da entrada

([:+/}:([:|-)}.)"1

Calcula a distância

(]A.~[: I. (= ([:distance perms)))

Vê quais resultados são os mesmos da entrada e gera novamente essas permutações (suspeito que alguns caracteres possam ser raspados aqui)

Com letras:

((a.{~65+[:i.#))

Crie uma lista das primeiras n letras, em que n é o comprimento da lista de entrada

indices A. [: letters ]

faz o mesmo que acima

Oitava, 73

function r=t(l,d,s)r=perms(l)(find(sum(abs(diff(perms(d)')))==s,1),:);end

Realmente não é possível cancelar o jogo, então deixe-me tentar explicar ... de dentro para fora, permutamos todas as distâncias; depois, para cada permutação, pegamos as diferenças entre casas, pegamos o valor absoluto à distância, adicionamos-as para cima, encontre o índice da primeira permutação com a distância desejada e permute as letras e encontre essa permutação específica de letras.

octave:15> t(["E" "F" "G" "H" "J" "K"],[0 5 7 13 16 17],62)
ans = HEJFKG

que é 13-0-16-5-17-7 => 13 + 16 + 11 + 12 + 10 = 62.

octave:16> t(["E" "F" "G" "H" "J" "K"],[0 5 7 13 16 17],2)
ans = 

(em branco para entradas impossíveis)

Matlab (86)

x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))

Exemplo no qual existe uma solução:

>> x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))
[0, 5, 7, 13, 16, 17]
62
DBFAEC
>>

Exemplo no qual uma solução não existe:

>> x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))
[0, 5, 7, 13, 16, 17]
100
>> 

Matlab (62)

Se o formato de saída puder ser relaxado produzindo posições em vez de letras e produzindo uma matriz vazia se não houver solução:

X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)

Exemplo no qual existe uma solução:

>> X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)
[0, 5, 7, 13, 16, 17]
62
ans =
    13     5    17     0    16     7

Exemplo no qual uma solução não existe:

>> X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)
[0, 5, 7, 13, 16, 17]
62
ans =
   Empty matrix: 0-by-6

Matlab (54)

Se for aceitável que o programa forneça todos os caminhos válidos :

X=perms(input(''));X(sum(abs(diff(X.')))==input(''),:)

Exemplo no qual existe uma solução:

>> X=perms(input(''));X(sum(abs(diff(X.')))==input(''),:)
[0, 5, 7, 13, 16, 17]
62
ans =
    13     5    17     0    16     7
    13     5    16     0    17     7
    13     0    17     5    16     7
    13     0    16     5    17     7
     7    16     5    17     0    13
     7    16     0    17     5    13
     7    17     5    16     0    13
     7    17     0    16     5    13

Haskell, 109 bytes

import Data.List
a%b=abs$snd a-snd b
n#l=[map(fst)p|p<-permutations(zip['E'..]l),n==sum(zipWith(%)p(tail p))]

Exemplo de uso: 17 # [0, 5, 7, 13, 16, 17]que exibe todos os caminhos válidos, ie ["EFGHIJ","JIHGFE"]. Se não houver um caminho válido, a lista vazia []será retornada.

A lista de cartas inclui I(espero que esteja tudo bem).

Como funciona: faça uma lista de (name, position)pares, permute e leve aqueles onde o comprimento do caminho é igual ne remova a parte da posição.