Putri saya mendapat tugas berikut untuk mengerjakan PR matematika. Bayangkan enam teman yang hidup dalam sebuah garis, bernama E, F, G, H, J, dan K. Posisi mereka di garis adalah seperti yang ditunjukkan (bukan untuk skala) di bawah:

Jadi, F hidup lima unit dari E, dan dua unit dari G, dan sebagainya.

Tugas Anda: buat program yang mengidentifikasi jalur yang mengunjungi setiap teman tepat sekali dengan total panjang n unit, dengan mengambil lokasi teman dan n sebagai input. Seharusnya melaporkan jalan jika menemukannya (misalnya, untuk panjang 17 itu mungkin melaporkan "E, F, G, H, J, K", dan itu harus keluar dengan anggun jika tidak ada solusi. Untuk apa nilainya, saya menyelesaikan sebuah solusi yang tidak dikenali di Mathematica dalam 271 bytes. Saya kira itu mungkin jauh lebih singkat dari itu.

J, 54 byte

Menghasilkan satu rute yang benar. Jika tidak ada rute itu tidak menghasilkan apa-apa.

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

   62 f 0 5 7 13 16 17
GJEKFH

Kode 52-byte yang menampilkan semua rute (satu per baris):

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

Kode 38-byte yang menampilkan posisi alih-alih huruf:

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

Mathematica, 55 atau 90 byte

Mathematica, katamu? ;)

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

Ini adalah fungsi anonim yang pertama mengambil posisi teman-teman (dalam urutan apa pun), dan kemudian panjang target. Itu kembali Missing[NotFound], jika tidak ada jalan seperti itu.

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

Saya dapat menyimpan empat byte jika mengembalikan semua jalur yang valid diizinkan ( FirstCase-> Cases).

Mengembalikan serangkaian string sedikit lebih rumit:

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

Python 2, 154 148 byte

(atau 118 byte untuk solusi umum)

Program ini menerima baris dengan daftar dan bilangan bulat seperti '[0, 5, 7, 13, 16, 17], n' pada stdin dan mencetak jalur pada output dengan panjang n atau tidak sama sekali jika tidak mungkin.

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

Sangat sulit untuk menulis program kecil dengan Python yang membutuhkan permutasi. Impor dan penggunaan itu sangat mahal.

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

Sumber untuk persyaratan OP sebelum 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

Solusi umum (tidak diperkecil):

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

Karena algoritma sederhana dan sejumlah besar kombinasi, eksekusi untuk lebih dari 20 posisi awal akan sangat lambat.

J (48 atau 65)

Saya berhipotesis bahwa ini bisa menjadi golf lebih banyak. Jangan ragu untuk menggunakan ini sebagai titik awal untuk bermain golf lebih jauh

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

Atau dengan surat:

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

Apa fungsinya:

   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

(Saya harap format I / O ini baik-baik saja ...)

Bagaimana cara kerjanya:

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

Menghasilkan semua permutasi dari input

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

Hitung jaraknya

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

Melihat hasil yang sama dengan input, dan menghasilkan kembali permutasi tersebut (saya menduga beberapa karakter dapat dicukur di sini)

Dengan surat:

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

Buat daftar n huruf pertama, di mana n adalah panjang daftar input

indices A. [: letters ]

melakukan hal yang sama seperti di atas

Oktaf, 73

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

Benar-benar tidak ada larangan bermain golf, jadi izinkan saya mencoba menjelaskan ... dari dalam ke luar, kami mengubah semua jarak, lalu untuk setiap permutasi, kami mengambil perbedaan antara rumah, mengambil nilai absolut sebagai jarak, menambahkannya Facebook, temukan indeks permutasi pertama dengan jarak yang diinginkan, dan permutasi huruf dan temukan permutasi huruf tertentu.

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

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

(kosong untuk input yang tidak mungkin)

Matlab (86)

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

Contoh di mana ada solusi:

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

Contoh di mana solusi tidak ada:

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

Jika format output dapat dilonggarkan dengan menghasilkan posisi alih-alih huruf, dan menghasilkan matriks kosong jika tidak ada solusi:

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

Contoh di mana ada solusi:

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

Contoh di mana solusi tidak ada:

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

Jika dapat diterima, program akan menyediakan semua jalur yang valid :

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

Contoh di mana ada solusi:

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

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

Contoh penggunaan: 17 # [0, 5, 7, 13, 16, 17] yang menampilkan semua jalur yang valid, yaitu ["EFGHIJ","JIHGFE"]. Jika tidak ada jalur yang valid, daftar kosong []dikembalikan.

Daftar surat termasuk I (harapan itu baik-baik saja).

Cara kerjanya: buat daftar (name, position)pasangan, permutasi, dan ambil pasangan yang panjang jalurnya sama ndan hapus bagian posisi.