Moja córka miała zadanie domowe z matematyki. Wyobraź sobie sześciu przyjaciół żyjących na linii o nazwach E, F, G, H, J i K. Ich pozycje na linii są takie, jak wskazano (nie w skali) poniżej:

Zatem F mieszka pięć jednostek z E i dwie jednostki z G i tak dalej.

Twoje zadanie: stworzyć program, który identyfikuje ścieżkę, która odwiedza każdego przyjaciela dokładnie raz, o całkowitej długości n jednostek, przyjmując lokalizacje znajomych i n jako dane wejściowe. Powinien zgłosić ścieżkę, jeśli ją znajdzie (na przykład dla długości 17 może zgłosić „E, F, G, H, J, K” i powinien wyjść z gracją, jeśli nie ma rozwiązania. Dla tego, co jest warte, ukończyłem nierozwiązane rozwiązanie w Mathematica w 271 bajtach. Podejrzewam, że jest to o wiele bardziej zwięzłe.

J, 54 bajty

Wyprowadza jedną poprawną trasę. Jeśli żadna trasa nie istnieje, nic nie wyprowadza.

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

   62 f 0 5 7 13 16 17
GJEKFH

52-bajtowy kod, który wyprowadza wszystkie trasy (jedna na linię):

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

38-bajtowy kod, który wyświetla pozycje zamiast liter:

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

Mathematica, 55 lub 90 bajtów

Mathematica powiedziałeś? ;)

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

Jest to anonimowa funkcja, która najpierw przyjmuje pozycje znajomych (w dowolnej kolejności), a następnie długość docelową. Zwraca Missing[NotFound], jeśli taka ścieżka nie istnieje.

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

Mogę zapisać cztery bajty, jeśli dozwolone jest zwrócenie wszystkich prawidłowych ścieżek ( FirstCase-> Cases).

Zwracanie tablicy ciągów jest nieco bardziej kłopotliwe:

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

Python 2, 154 148 bajtów

(lub 118 bajtów dla rozwiązania ogólnego)

Ten program akceptuje linię z listą i liczbą całkowitą taką jak „[0, 5, 7, 13, 16, 17], n” na standardowym wyjściu i wypisuje ścieżkę na wyjściu o długości n lub nic, jeśli jest to niemożliwe.

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

Pisanie małych programów w Pythonie, które wymagają permutacji, jest trudne. Ten import i użycie jest bardzo kosztowne.

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

Źródło wymagania OP przed minifikatorem:

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

Ogólne rozwiązanie (nie zminimalizowane):

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

Ze względu na prosty algorytm i ogromną liczbę kombinacji wykonanie dla ponad 20 pozycji początkowych będzie bardzo wolne.

J (48 lub 65)

Podejrzewam, że można pograć w golfa o wiele więcej. Możesz to wykorzystać jako punkt wyjścia do dalszej gry w golfa

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

Lub z literami:

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

Co to robi:

   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

(Mam nadzieję, że ten format I / O jest w porządku ...)

Jak to robi:

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

Generuje wszystkie permutacje danych wejściowych

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

Oblicza odległość

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

Widzi, które wyniki są takie same jak dane wejściowe, i ponownie generuje te permutacje (podejrzewam, że niektóre znaki można tutaj zgolić)

Z literami:

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

Utwórz listę pierwszych n liter, gdzie n jest długością listy wprowadzania

indices A. [: letters ]

robi to samo co powyżej

Oktawa, 73

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

Naprawdę nie ma takiej gry w golfa, więc pozwól mi wyjaśnić ... od wewnątrz do zewnątrz, permutujemy wszystkie odległości, a następnie dla każdej permutacji bierzemy różnice między domami, przyjmujemy wartość bezwzględną jako odległość, dodajemy je w górę, znajdź indeks pierwszej permutacji z żądaną odległością i permutuj litery i znajdź tę konkretną permutację liter.

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

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

(puste dla niemożliwych danych wejściowych)

Matlab (86)

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

Przykład, w którym istnieje rozwiązanie:

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

Przykład, w którym rozwiązanie nie istnieje:

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

Jeśli format wyjściowy można złagodzić , tworząc pozycje zamiast liter i tworząc pustą macierz, jeśli nie ma rozwiązania:

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

Przykład, w którym istnieje rozwiązanie:

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

Przykład, w którym rozwiązanie nie istnieje:

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

Jeśli program może podać wszystkie prawidłowe ścieżki :

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

Przykład, w którym istnieje rozwiązanie:

>> 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 bajtów

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

Przykład użycia: 17 # [0, 5, 7, 13, 16, 17]który wyprowadza wszystkie prawidłowe ścieżki, tj ["EFGHIJ","JIHGFE"]. Jeśli nie ma prawidłowej ścieżki, []zwracana jest pusta lista .

Lista listów zawiera I(mam nadzieję, że w porządku).

Jak to działa: utwórz listę (name, position)par, permutuj i weź te, w których długość ścieżki jest równa, ni usuń część pozycji.