Stitch Bersama Palindrome dari Palindromic Substrings

14

Mengingat string l, menemukan semua substring palindromic pdari l(termasuk duplikat dan string karakter tunggal). Selanjutnya, atur ulang semua sub-string pmenjadi palindrome yang valid (mungkin ada beberapa jawaban yang benar). Jika tidak mungkin untuk mengatur ulang pmenjadi satu palindrom tunggal, program Anda mungkin memiliki perilaku yang tidak terdefinisi (kesalahan, stack-overflow, keluar, menggantung / pembunuhan John Dvorak, dll ...)


Contohnya

Kasus Uji yang valid

l = anaa
p = ['a', 'n', 'a', 'a', 'aa', 'ana']
result = anaaaaana or aanaaanaa or aaananaaa

l = 1213235
p = ['1', '2', '1', '3', '2', '3', '5', '121', '323']
result = 1213235323121

l = racecar
p = ['r', 'a', 'c', 'e', 'c', 'a', 'r', 'cec', 'aceca', 'racecar']
result = racecarcecaacecracecar (there are others)

l = 11233
p = ['1', '11', '1', '2', '3', '33', '3']
result = 113323311 or 331121133

l = abbccdd
p = ['a', 'b', 'bb', 'b', 'c', 'cc', 'c', 'd', 'dd', 'd']
result = bbccddaddccbb or ccbbddaddbbcc or (etc...)

l = a
p = ['a']
result = a

Kasus Uji Tidak Valid (Tidak Mungkin)

l = 123456789
p = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = <not possible, behavior undefined>

l = hjjkl
p = ['h', 'j', 'jj', 'j', 'k', 'l']
result = <not possible, behavior undefined>

l = xjmjj
p = ['x', 'j', 'jmj', 'm', 'j', 'jj', 'j']
result = <not possible, behavior undefined>

Aturan

  • Jika kata input adalah palindrome itu sendiri, itu akan selalu berlaku sebagai input.
  • Hanya satu substring yang harus dikembalikan, mana yang Anda pilih sewenang-wenang asalkan valid.
  • Jika input tidak memiliki output yang layak, kode Anda mungkin memiliki perilaku yang tidak terdefinisi.
  • Input hanya akan berisi karakter ASCII-Printable 0x20-0x7E.
  • Ini adalah , byte-count terendah adalah pemenangnya.
Guci Gurita Ajaib
sumber
1
Usulan hasil pertama "abbccdd"adalah salah: dua huruf terakhir seharusnya "bb", bukan "dd".
Fatalkan
Bisakah kita mengembalikan array substring, bukan string tunggal?
Shaggy
Bisakah saya mengambil daftar karakter sebagai input?
alephalpha
1
Dengan menggantung sebagai perilaku yang dapat diterima, maksud Anda menggantung orang yang memberikannya input?
John Dvorak
@JohnDvorak diklarifikasi.
Magic Octopus Mm

Jawaban:

8

Brachylog , 10 byte

{s.↔}ᶠpc.↔

Cobalah online!

Gagal (yaitu mencetak false.) jika tidak memungkinkan.

Penjelasan

{   }ᶠ         Find all…
 s.              …substrings of the input…
  .↔             …which are their own reverse
      p        Take a permutation of this list of palindromes
       c.      The output is the concatenation of this permutation
        .↔     The output is its own reverse
Fatalisasi
sumber
3

Kelapa , 140 byte

s->p(map(''.join,permutations(p(v for k in n(s)for v in n(k[::-1])))))[0]
from itertools import*
n=scan$((+))
p=list..filter$(x->x==x[::-1])

Cobalah online!

ovs
sumber
3

JavaScript (ES6), 193 byte

"Dengar, Ma, tidak ada permutasi yang terpasang!" (Jadi ya ... itu panjang ...)

Mengembalikan array kosong jika tidak ada solusi.

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

Demo

Bagaimana?

Mari kita membagi kode menjadi bagian-bagian yang lebih kecil.

Kami mendefinisikan P () , fungsi yang mengembalikan s jika s adalah palindrome, atau false sebaliknya.

P = s => [...s].reverse().join`` == s && s

Kami menghitung semua substring dari string input s . Menggunakan P () , kami mengisolasi palindrom non-kosong dan menyimpannya dalam array a .

a = [].concat(...[...s].map((_, i, a) => a.map((_, j) => s.slice(i, j + 1)))).filter(P)

Utama rekursif fungsi f () mengambil sebuah sebagai masukan dan menghitung semua permutasi nya. Itu update S setiap kali permutasi itu sendiri adalah palindrom (pernah bergabung), dan akhirnya mengembalikan nilai akhir dari S .

f = (                        // given:
  a,                         //   a[] = input array
  m = S = []                 //   m[] = current permutation of a[]
) =>                         //   and S initialized to []
  S = a.map((_, i) =>        // for each element at position i in a[]:
    f(                       //   do a recursive call with:
      b = [...a],            //     b[] = copy of a[] without the i-th element
      [...m, b.splice(i, 1)] //     the element extracted from a[] added to m[]
    )                        //   end of recursive call
  ) > '' ?                   // if a[] was not empty:
    S                        //   let S unchanged
  :                          // else:
    P(m.join``) || S         //   update S to m.join('') if it's a palindrome
Arnauld
sumber
2

Jelly , 13 byte

ŒḂÐf
ẆÇŒ!F€ÇḢ

Cobalah online!

Mencetak 0dalam case yang tidak valid.

HyperNeutrino
sumber
2

05AB1E , 13 12 byte

ŒʒÂQ}œJʒÂQ}¤

Cobalah online!

-1 byte, terima kasih untuk Magic Octopus Mm dan Enigma.

Kaldo
sumber
Jsecara otomatis faktorisasi sehingga Anda tidak perlu €Jhanya J; juga, Anda seharusnya mengembalikan salah satu palindrom, tidak semua. Cobalah online! berlaku untuk byte-count yang sama.
Magic Octopus Urn
@ MagicOctopusUrn Diperbaiki, terima kasih!
Kaldo
Ùćbisa jadi ¤(atau sejumlah opsi lain)
Emigna
@Emigna tidak yakin mengapa saya tidak melihat yang Ùtidak diperlukan.
Magic Octopus Urn
Teka-teki buruk saya, untuk alasan yang tidak diketahui saya pikir kami seharusnya menampilkan semua palindrom unik, karenanya Ù asli. Terima kasih atas tipnya, tetap!
Kaldo
2

Stax , 13 byte

绬►Ö∞j∞:Æ╘τδ

Jalankan test case (Diperlukan sekitar 10 detik pada mesin saya saat ini)

Ini adalah representasi ascii yang sesuai dari program yang sama.

:e{cr=fw|Nc$cr=!

Ini bukan brute-force murni , tapi hanya sekecil implementasi brute-force yang saya tulis. Yang itu crash browser saya setelah sekitar 10 menit. Bagaimanapun, ini cara kerjanya.

:e                  Get all contiguous substrings
  {cr=f             Keep only those that are palindromes
       w            Run the rest of the program repeatedly while a truth value is produced.
        |N          Get the next permutation.
          c$        Copy and flatten the permutation.
            cr=!    Test if it's palindrome.  If not, repeat.
                    The last permutation produced will be implicitly printed.
rekursif
sumber
2

Ruby , 131 123 120 byte

->s{m=->t{t==t.reverse}
(1..z=s.size).flat_map{|l|(0..z-l).map{|i|s[i,l]}}.select(&m).permutation.map(&:join).detect &m}

Cobalah online!

Lambda menerima string dan mengembalikan string. Kembali nilketika tidak ada solusi.

-5 byte: Ganti select{|t|l[t]}denganselect(&l)

-3 byte: Ganti map{..}.flattendenganflat_map{...}

-1 byte: Ulangi panjang substring dan mulai substring, alih-alih mulai substring dan akhir substring

-2 byte: Deklarasikan zpada penggunaan pertama dan bukan sebelumnya

->s{
  l=->t{t==t.reverse}        # Lambda to test for palindromes
  (1..z=s.size).flat_map{|l| # For each substring length
    (0..z-l).map{|i|         # For each substring start index
      s[i,l]                 # Take the substring
    }
  }                          # flat_map flattens the list of lists of substrings
  .select(&l)                # Filter to include only palindromic substrings
  .permutation               # Take all orderings of substrings
  .map(&:join)               # Flatten each substring ordering into a string
  .detect &l                 # Find the first palindrome
}
benj2240
sumber
1

Pyth , 13 byte

h_I#sM.p_I#.:

Cobalah online!

-1 byte terima kasih kepada Tn. Xcoder

HyperNeutrino
sumber
Lol Saya sangat yakin tidak ada orang lain yang menggunakan Pyth sehingga saya mengirimkan jawaban saya sendiri (sekarang dihapus) sebelum melihat milik Anda. Anda dapat menggunakan h_I#sM.p_I#.:atau e_IDsM.p_I#.:selama 13 byte.
Tn. Xcoder
@ Mr.Xcoder Oh haha: P ya saya jarang menggunakan Pyth, tidak tahu mengapa saya memutuskan untuk menggunakannya. Terima kasih!
HyperNeutrino
1

Python 3 , 167 byte

lambda a:g(sum(k,[])for k in permutations(g(a[i:j+1]for i in range(len(a))for j in range(i,len(a)))))[0]
g=lambda k:[e for e in k if e==e[::-1]]
from itertools import*

Cobalah online!

-2 byte terima kasih kepada Tn. Xcoder

HyperNeutrino
sumber
Anda dapat menggunakan a[i:j+1]jika Anda kemudian menggunakan for j in range(i,len(a)), untuk -2 byte.
Tn. Xcoder
1

Japt , 19 byte

Terhambat oleh Japt belum (belum) bisa mendapatkan semua substring dari string (dan sebagian lagi oleh tingkat kelelahan saya saat ini!).

Keluaran undefinedjika tidak ada solusi.

Êõ@ãX fêQÃc á m¬æêQ

Cobalah


Penjelasan

                        :Implicit input of string U
Ê                       :Length of U
 õ                      :Range [1,Ê]
  @      Ã              :Pass each X through a function
   ãX                   :  Substrings of U of length X
      f                 :  Filter
       êQ               :    Is it a palindrome?
          c             :Flatten
            á           :Permutations
              m         :Map
               ¬        :  Join to a string
                æêQ     :Get first element that is a palindrome
Shaggy
sumber
1
Apakah pertanyaan Anda tentang daftar substring hanya untuk menghapus ¬dari jawaban Anda: P?
Magic Gurita Guci
1
Kupikir aku bisa menghapus tapi kemudian aku akan membutuhkannya æ_¬êQsehingga tidak akan menyimpan byte apa pun!
Shaggy
Hahaha, saya akan memastikan mewaspadai cara byte-saving Anda mulai sekarang;). Saya mencoba menghapusnya sendiri untuk memeriksa, tetapi menyadari perintah japt tidak bekerja seperti saya pikir mereka bekerja lol.
Magic Octopus Urn
1

Sekam , 12 byte

ḟS=↔mΣPfS=↔Q

Cobalah online!

Penjelasan

ḟS=↔mΣPfS=↔Q  Implicit input, a string.
           Q  List of substrings.
       f      Keep those
        S=↔   that are palindromic (equal to their reversal).
      P       Permutations of this list.
    mΣ        Flatten each.
ḟ             Find an element
 S=↔          that is palindromic.
Zgarb
sumber
0

J , 53 byte

[:{:@(#~b"1)@(i.@!@#;@A.])@(#~(0<#*b=.]-:|.)&>)@,<\\.

Cobalah online!

Galen Ivanov
sumber