Четвертое занятие по математике на неделю: самый неэффективный коммивояжёр

10

У моей дочери было следующее задание по математике. Представьте себе шестерых друзей, живущих на линии с именами E, F, G, H, J и K. Их позиции на линии такие, как указано (не в масштабе) ниже:

Таким образом, F живет в пяти единицах от E и двух единицах от G и так далее.

Ваше задание: создайте программу, которая идентифицирует путь, который посещает каждого друга ровно один раз, с общей длиной n единиц, принимая местоположение друзей и n в качестве входных данных. Он должен сообщить путь, если он его найдет (например, для длины 17 он может сообщить «E, F, G, H, J, K»), и он должен выйти изящно, если решения не существует. Для чего он стоит, я выполнил решение без математики в Mathematica в 271 байт. Я подозреваю, что это возможно гораздо более кратко, чем это.

code-golf graph-theory path-finding Майкл Стерн
источник
3
Это может быть лучше, поскольку программа принимает входные данные (например, [0, 5, 7, 13, 16, 17]и 62), чтобы вы могли убедиться, что она не имеет особой жесткости в этом случае.
Дверная ручка
@ Doorknob, хорошая мысль. Я скорректировал назначение соответственно.
Майкл Стерн
1
Путь начинается у любого друга?
xnor
1
Могу ли я определить формат строк ввода и вывода? Ввод как "[0, 5, 7, 13, 16, 17], 62"и выход в "(7, 16, 0, 17, 5, 13)"порядке?
Логика Найт
1
@ Geobits просто небрежно с моей стороны. Исправлено.
Майкл Стерн

Ответы:

1

J 54 байта

Выводит один правильный маршрут. Если маршрут не существует, он ничего не выводит.

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

   62 f 0 5 7 13 16 17
GJEKFH

52-байтовый код, который выводит все маршруты (по одному на строку):

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

38-байтовый код, который выводит позиции вместо букв:

f=.4 :'p#~x=+/|:2|@-/\"#.p=.(i.!6)A.y'
randomra
источник
Я не могу проверить код, но, по вашему мнению, это самая короткая запись, которая выполняет все, что требуется для решения проблемы.
Майкл Стерн
6

Mathematica, 55 или 90 байт

Mathematica вы сказали? ;)

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

Это анонимная функция, которая сначала занимает позиции друзей (в любом порядке), а затем целевую длину. Возвращается Missing[NotFound], если такого пути не существует.

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

Я могу сохранить четыре байта, если разрешен возврат всех допустимых путей ( FirstCase-> Cases).

Возвращать массив строк немного сложнее:

FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&
Мартин Эндер
источник
Не могли бы вы настроить так, чтобы он отвечал буквами, а не только местоположениями?
Майкл Стерн
@MichaelStern Не совсем понятно из вопроса, сколько должно быть жестко закодировано и сколько должно быть частью параметров? Должен ли ввод быть чем-то вроде сопоставления букв и позиций?
Мартин Эндер
Предположим, что буквы всегда в порядке, указанном в числовой строке выше (E, F, G, H, J, K). Расстояния между ними должны быть переданы функции, как вы делаете это в своем решении.
Майкл Стерн
@MichaelStern Я добавил версию, которая возвращает массив строк. Он поддерживает любое количество позиций в списке, но после Zбудет продолжать со следующими символами ASCII (не то, что вы все равно хотите запустить мой код для n> 20: D).
Мартин Эндер
5

Python 2, 154 148 байт

(или 118 байт для общего решения)

Эта программа принимает строку со списком и целым числом типа '[0, 5, 7, 13, 16, 17], n' в stdin и печатает путь на выходе длины n или ничего, если это невозможно.

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

Сложно писать небольшие программы на Python, которые требуют перестановок. Этот импорт и использование очень дорого.

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

Источник для требования OP перед 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

Общее решение (не минимизированное):

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

Из-за простого алгоритма и большого количества комбинаций выполнение более 20 начальных позиций будет очень медленным.

Логика Найт
источник
Вы можете сохранить несколько байтов с from itertools import*. Кроме того, Python 3 может быть короче, input()и *a,c=map(...)если он может работать с остальной частью вашей программы.
GRC
Спасибо за совет по импорту. Я сопротивляюсь установке py3 и преобразованию моей базы кода. Я жду, пока каждый сторонний модуль, который я использую, будет доступен и стабилен под py3 (я использую много старых и малоизвестных).
Логика Найт
Не могли бы вы настроить так, чтобы он отвечал буквами, а не только местоположениями?
Майкл Стерн
chr(a.index(n)+69)?
Мартин Эндер
Хорошая оптимизация. Но я думаю, что @MichaelStern действительно хочет увидеть 'EFGHJK', и это было достаточно просто, поэтому я написал код таким образом.
Логика Найт
4

J (48 или 65)

Я предполагаю, что это может быть чертовски много. Не стесняйтесь использовать это как отправную точку для игры в гольф дальше

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

Или с буквами: 

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

Что оно делает:

   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

(Я надеюсь, что этот формат ввода / вывода в порядке ...)

Как оно это делает:

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

Генерирует все перестановки ввода

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

Рассчитывает расстояние

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

Видит, что результаты совпадают с входными данными, и заново генерирует эти перестановки (я подозреваю, что некоторые символы могут быть выбриты здесь)

С буквами:

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

Создайте список из первых n букв, где n - длина списка ввода

indices A. [: letters ]

делает то же самое, что и выше

ɐɔıʇǝɥʇuʎs
источник
Можете ли вы настроить его, чтобы сообщить ответ в виде букв?
Майкл Стерн
@MichaelStern Я мог бы, но это добавило бы немного к количеству символов (J ужасен со строками). Я попробую сейчас, чтобы увидеть, какой может быть ущерб.
Febı
3

Октава, 73

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

На самом деле этого нет, поэтому позвольте мне объяснить ... изнутри наружу, мы переставляем все расстояния, затем для каждой перестановки мы берем различия между домами, принимаем абсолютное значение как расстояние, добавляем их вверх, найдите индекс первой перестановки с нужным расстоянием, переставьте буквы и найдите эту конкретную перестановку букв.

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

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 =

(пусто для невозможных вводов)

dcsohl
источник
Я не знаю, в чем дело, но perms()в Octave 3.6.2 на ideone.com возникают проблемы с вектором строк.
Алекс А.
Интересно. У меня 3.8.1 локально.
dcsohl
2

Матлаб (86)

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

Пример, в котором существует решение:

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

Пример, в котором решение не существует:

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

Матлаб (62)

Если выходной формат может быть ослаблен путем создания позиций вместо букв и создания пустой матрицы, если решения не существует:

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

Пример, в котором существует решение:

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

Пример, в котором решение не существует:

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

Матлаб (54)

Если для программы допустимо указывать все допустимые пути :

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

Пример, в котором существует решение:

>> 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
Луис Мендо
источник
1

Haskell, 109 байт

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

Пример использования: 17 # [0, 5, 7, 13, 16, 17]который выводит все допустимые пути, то есть ["EFGHIJ","JIHGFE"]. Если нет допустимого пути, пустой список[] возвращается .

Список писем включает в себя I(надеюсь, что все в порядке).

Как это работает: составьте список (name, position) пар, переставьте и возьмите те, у которых длина пути равна, nи удалите часть позиции.

Ними
источник