Fourth grade math homework for the week: A most inefficient traveling salesman
Mathematica, 55 or 90 bytes
Mathematica you said? ;)
FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&
This is an anonymous function that first takes the positions of the friends (in any order), and then the target length. It returns Missing[NotFound]
, if no such path exists.
FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&[{0, 5, 7, 13, 16, 17}, 62]
(* {7, 16, 0, 17, 5, 13} *)
I can save four bytes if returning all valid paths is allowed (FirstCase
-> Cases
).
Returning an array of strings is a bit more cumbersome:
FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&
Python 2, 154 148 bytes
(or 118 bytes for the general solution)
This program accepts a line with a list and an integer like '[0, 5, 7, 13, 16, 17], n' on stdin and prints a path on the output of length n or nothing if impossible.
# echo "[0, 5, 7, 13, 16, 17], 62" | python soln.py
['G', 'J', 'E', 'K', 'F', 'H']
It is challenging to write small programs in Python that require permutations. That import and use is very costly.
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
The source for the OP requirement before the minifier:
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
The general solution (not minified):
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
Due to the simple algorithm and vast number of combinations, execution for more than 20 initial positions will be very slow.
J (48 or 65)
I hypothesize that this can be golfed a hell of a lot more. Feel free to use this as a jumping off point to golf it further
]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))
Or with letters:
([:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#)))))A.[:(a.{~65+[:i.#)]
What it does:
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
(I hope this I/O format is okay...)
How it does it:
(A.~([:i.[:!#))
Generates all permutations of the input
([:+/}:([:|-)}.)"1
Calculates the distance
(]A.~[: I. (= ([:distance perms)))
Sees which results are the same as the input, and re-generates those permutations (I suspect some characters can be shaved off here)
With letters:
((a.{~65+[:i.#))
Create a list of the first n letters, where n is the length of the input list
indices A. [: letters ]
does the same as above