Mi hija tenía la siguiente tarea para su tarea de matemáticas. Imagine seis amigos que viven en una línea, llamados E, F, G, H, J y K. Sus posiciones en la línea son las indicadas (no a escala) a continuación:

Por lo tanto, F vive cinco unidades de E, y dos unidades de G, y así sucesivamente.

Su tarea: cree un programa que identifique una ruta que visite a cada amigo exactamente una vez con una longitud total de n unidades, tomando las ubicaciones de los amigos yn como entradas. Debería informar la ruta si la encuentra (por ejemplo, para la longitud 17 podría informar "E, F, G, H, J, K", y debería salir con gracia si no existe una solución. Por lo que vale, completé una solución no adaptada en Mathematica en 271 bytes. Sospecho que es posible de manera mucho más concisa que eso.

J, 54 bytes

Emite una ruta correcta. Si no existe una ruta, no genera 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 genera todas las rutas (una por línea):

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

Código de 38 bytes que genera posiciones en lugar de letras:

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

Mathematica, 55 o 90 bytes

Mathematica que dijiste? ;)

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

Esta es una función anónima que primero toma las posiciones de los amigos (en cualquier orden) y luego la longitud del objetivo. Regresa Missing[NotFound], si no existe tal camino.

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

Puedo guardar cuatro bytes si se permite devolver todas las rutas válidas ( FirstCase-> Cases).

Devolver una serie de cadenas es un poco más engorroso:

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

Python 2, 154 148 bytes

(o 118 bytes para la solución general)

Este programa acepta una línea con una lista y un número entero como '[0, 5, 7, 13, 16, 17], n' en stdin e imprime una ruta en la salida de longitud n o nada si es imposible.

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

Es un desafío escribir pequeños programas en Python que requieren permutaciones. Esa importación y uso es muy costoso.

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

La fuente del requisito de OP antes del 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

La solución general (no 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

Debido al algoritmo simple y al gran número de combinaciones, la ejecución de más de 20 posiciones iniciales será muy lenta.

J (48 o 65)

Supongo que esto se puede jugar mucho más al golf. Siéntase libre de usar esto como un punto de partida para jugar más golf

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

O con letras:

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

Que hace:

   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 esté bien ...)

Como lo hace:

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

Genera todas las permutaciones de la entrada.

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

Calcula la distancia

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

Ve qué resultados son los mismos que los de entrada y vuelve a generar esas permutaciones (sospecho que algunos caracteres se pueden eliminar aquí)

Con letras:

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

Cree una lista de las primeras n letras, donde n es la longitud de la lista de entrada

indices A. [: letters ]

hace lo mismo que arriba

Octava, 73

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

Realmente no hay que deshacer el golf, así que déjenme tratar de explicarlo ... de adentro hacia afuera, permutamos todas las distancias, luego, para cada permutación, tomamos las diferencias entre las casas, tomamos el valor absoluto como una distancia, los sumamos arriba, encuentre el índice de la primera permutación con la distancia deseada, y permute las letras y encuentre esa permutación particular de letras.

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

que es 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 = 

(en blanco para entradas imposibles)

Matlab (86)

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

Ejemplo en el que existe una solución:

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

Ejemplo en el que no existe una solución:

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

Si el formato de salida se puede relajar produciendo posiciones en lugar de letras y produciendo una matriz vacía si no existe una solución:

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

Ejemplo en el que existe una solución:

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

Ejemplo en el que no existe una solución:

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

Si es aceptable que el programa proporcione todas las rutas válidas :

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

Ejemplo en el que existe una solución:

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

Ejemplo de uso: 17 # [0, 5, 7, 13, 16, 17]que genera todas las rutas válidas, es decir ["EFGHIJ","JIHGFE"]. Si no hay una ruta válida, []se devuelve la lista vacía .

La lista de letras incluye I(espero que esté bien).

Cómo funciona: haga una lista de (name, position)pares, permute y tome aquellos donde la longitud del camino sea igual ny elimine la parte de posición.