Diberikan string sebagai input menemukan yang paling berdekatan berdekatan substring yang tidak memiliki karakter dua kali atau lebih. Jika ada beberapa substring seperti itu Anda dapat menampilkan baik. Anda dapat berasumsi bahwa input berada pada kisaran ASCII yang dapat dicetak jika Anda mau.

Mencetak gol

Jawaban pertama-tama akan diberi peringkat berdasarkan panjang substring non-berulang terpanjang mereka sendiri, dan kemudian dengan total panjangnya. Skor yang lebih rendah akan lebih baik untuk kedua kriteria. Tergantung pada bahasanya ini mungkin akan terasa seperti tantangan kode-golf dengan pembatasan sumber.

Keremehan

Dalam beberapa bahasa mencapai skor 1, x (bahasa) atau 2, x (Brain-flak dan tarpit turing lainnya) cukup mudah, namun ada bahasa lain di mana meminimalkan substring non-berulang terpanjang adalah sebuah tantangan. Saya bersenang-senang mendapatkan skor 2 di Haskell, jadi saya mendorong Anda untuk mencari bahasa di mana tugas ini menyenangkan.

Uji kasus

"Good morning, Green orb!" -> "ing, Gre"
"fffffffffff" -> "f"
"oiiiiioiiii" -> "io", "oi"
"1234567890"  -> "1234567890"
"11122324455" -> "324"

Pengiriman skor

Anda dapat menilai program Anda menggunakan cuplikan berikut:

input.addEventListener("input", change);

// note: intentionally verbose :)
function isUnique(str) {
  var maxCount = 0;
  var counts = {};
  for(var i = 0; i < str.length; i++) {
    var c = str.charAt(i);
    counts[c] |= 0;
    counts[c]++;
    if(maxCount < counts[c]) {
      maxCount = counts[c];
    }
  }
  return maxCount <= 1;
}

function maximizeSubstring(str, pred, cost) {
  var mostExpensive = -1;
  // iterate over substrings
  function iterate(start, end) {
    var slice = str.slice(start, end);
    if(pred(slice)) {
      var profit = cost(slice);
      if(profit > mostExpensive) {
        mostExpensive = profit;
      }
    }
    end++;
    if(start >= str.length) {
      return;
    }
    else if(end > str.length) {
      start++;
      iterate(start, start);
    }
    else {
      iterate(start, end);
    }
  }
  iterate(0, 0);
  return mostExpensive;
}

function size(x) {
  return x.length;
}

function longestNonRepeatingSize(str) {
  return maximizeSubstring(str, isUnique, size);
}

function change() {
  var code = input.value;
  output.value = "Your score is: " + longestNonRepeatingSize(code);
}

change();

* {
  font-family: monospace;
}

Input code here:
<br>
<textarea id="input"></textarea>
<br>
<textarea id="output"></textarea>

C, skor 2,  747   720  662 byte

L  [  1  <<  7  ]  ,  *  q  ,  *  r  ,  l  ,  d  ,  i  ,  c  ,  j  ,  s  ,  t  ,  k  =  1  <<  7  ;  h  (  )  {  q  =  s  +  i  +  j  ++  ;  *  q  %  k  &&  !  L  [  *  q  %  k  ]  ++  &&  h  (  ++  c  )  ;  }  g  (  )  {  q  =  s  +  i  ;  *  q  %  k  ?  z  (  k  )  ,  h  (  j  =  c  =  0  )  ,  c  >  d  &&  (  d  =  c  )  &&  (  l  =  i  )  ,  g  (  ++  i  )  :  0  ;  }  f  (  S  ,  T  )  {  s  =  S  ;  l  =  i  =  d  =  0  ;  g  (  t  =  T  )  ;  p  (  i  =  0  )  ;  }  p  (  )  {  q  =  s  +  l  +  i  ;  r  =  t  +  i  ;  i  ++  <  d  ?  p  (  *  r  =  *  q  )  :  (  *  r  =  0  )  ;  }  z  (  i  )  {  L  [  --  i  ]  =  0  ;  i  &&  z  (  i  )  ;  }

Bekerja setidaknya pada MinGW 32-bit (dengan optimasi dinonaktifkan). Tidak menggunakan kata kunci tunggal.

Tampaknya bekerja di TIO dengan gcc dan dentang: Coba online! (Terima kasih @Dennis!)

Telepon dengan:

int main()
{
    char str[1024];

    f("Good morning, Green orb!", str);
    puts(str);

    f("fffffffffff", str);
    puts(str);

    f("oiiiiioiiii", str);
    puts(str);

    f("1234567890", str);
    puts(str);

    f("L  [  1  <<  7  ]  ,  *  q  ,  *  r  ,  l  ,  d  ,  i  ,  c  ,  j  ,  s  ,  t  ,  k  =  1  <<  7  ;  h  (  )  {  q  =  s  +  i  +  j  ++  ;  *  q  %  k  &&  !  L  [  *  q  %  k  ]  ++  &&  h  (  ++  c  )  ;  }  g  (  )  {  q  =  s  +  i  ;  *  q  %  k  ?  z  (  k  )  ,  h  (  j  =  c  =  0  )  ,  c  >  d  &&  (  d  =  c  )  &&  (  l  =  i  )  ,  g  (  ++  i  )  :  0  ;  }  f  (  S  ,  T  )  {  s  =  S  ;  l  =  i  =  d  =  0  ;  g  (  t  =  T  )  ;  p  (  i  =  0  )  ;  }  p  (  )  {  q  =  s  +  l  +  i  ;  r  =  t  +  i  ;  i  ++  <  d  ?  p  (  *  r  =  *  q  )  :  (  *  r  =  0  )  ;  }  z  (  i  )  {  L  [  --  i  ]  =  0  ;  i  &&  z  (  i  )  ;  }");
    puts(str);
}

Keluaran:

Kode dengan pemformatan yang sedikit lebih mudah dibaca:

L[1<<7],
*q, *r, l, d, i, c, j, s, t, k=1<<7;

h()
{
    q = s+i+j++;
    *q%k && !L[*q%k]++ && h(++c);
}

g()
{
    q = s+i;
    *q%k ? z(k), h(j=c=0), c>d && (d=c) && (l=i), g(++i) : 0;
}

f(S, T)
{
    s = S;
    l = i = d = 0;
    g(t=T);
    p(i=0);
}

p()
{
    q = s+l+i;
    r = t+i;
    i++<d ? p(*r=*q) : (*r=0);
}

z(i)
{
    L[--i] = 0;
    i && z(i);
}

Dan ini dapat digunakan untuk menghasilkan spasi yang tepat untuk mendapatkan pemformatan dengan skor 2: Coba online!

C, skor 3, 309 byte

i
,
j
,
l
,
c
,
d
;
f
(
\
c\
\
h\
\
a\
\
r
*
s
)
{
\
f\
\
o\
\
r
\
(
i
=
l
=
d
=
0
;
s
[
i
]
;
c
>
d
&&
(
d
=
c
)
&&
(
l
=
i
)
,
++
i
)
\
f\
\
o\
\
r
(
\
c\
\
h\
\
a\
\
r

L
[
\
1\
\
2\
\
8
\
]
=
{
j
=
c
=
0
}
;
s
[
i
+
j
]
&&
!
L
[
s
[
i
+
j
++
]
]
++
;
++
c
)
;
\
w\
\
r\
\
i\
\
t\
\
e
(
1
,
s
+
l
,
d
)
;
}

Cobalah online!

Haskell , skor 2, 492 ... 307 224 212 209 207 byte

((yy:yyy))??ss|ss==yy  =  ""  |  yy==yy=yy:yyy??ss
ss??sss=ss
ss""=""

ss((ff:fff))  =  ff  :  ss  fff??ff
ff""=""

ff((xxx:xx))  =  ss((xxx:xx))##ff  xx
xx##xxx  |  ((((xx>>xx))<))  $  xxx>>xx=xxx|xx==xx=xx

Cobalah online!

Bermain golf ratusan byte berkat WW dan Ørjan Johansen !

Penjelasan

Fungsi (??)mengambil karakter cdan string sdan mengembalikan awalan terpanjang syang tidak mengandung c. Tidak disatukan dan tidak dioptimalkan untuk skor:

c ?? (y:s)  
    | c==y = ""
    | True = y : c ?? s
c ?? s = s

Fungsi ini ssdigunakan (??)untuk menemukan awalan terpanjang dari karakter unik dari string yang diberikan:

ss (x:r) = x : (x ?? ss r)
ss "" = ""

(##)adalah fungsi yang mengambil dua string dan mengembalikan yang lebih panjang. Perbandingan panjang bekerja dengan mengulangi string xsesering xpanjang ( x>>y) dan sebagaimana ypanjang ( y>>x) dan memeriksa mana dari string yang dihasilkan secara leksikografis lebih besar.

x ## y
  | (x>>x) < (y>>x) = y
  | True = x

Akhirnya ffberulang pada string input, menghasilkan awalan terpanjang dengan ss, secara rekursif menentukan substring non-berulang terpanjang dari ujung string dan mengembalikan yang lebih panjang dari keduanya dengan (##):

ff "" = ""
ff (x:r) = ss(x:r) ## ff r

Lua, skor 3, 274 byte

g='g'..'s'..'u'..'b'  _G  [  'l'..'o'..'a'..'d'  ](  g[g  ](  "s  =...f  o  r d = # s - 1 , 0 , - 1 d  o f  or r = 1 , # s - d d  o t = s :s  ub  (r  ,r  +d  )i  f n  ot t:  fi  nd  '(  .)  .*  %1  't  he  n p  ri  nt  (t  )r  et  ur  n en  d e  n  d e  nd  ","  ",""))(...)

Catatan: Lua 5.2 atau Lua 5.3 diperlukan

Pemakaian:

$ lua lnrs.lua "Good morning, Green orb!"
ing, Gre
$ lua lnrs.lua "fffffffffff"
f
$ lua lnrs.lua "oiiiiioiiii"
oi
$ lua lnrs.lua "1234567890"
1234567890
$ lua lnrs.lua "11122324455"
324

Gagasan utama: interleave semuanya dengan spasi, masukkan " "(dua spasi) untuk membagi pengidentifikasi panjang

Kode tidak dikunci:

g = "gsub"
_G["load"](
   g[g](      -- g[g] == string.gsub - a function for substitution of substrings
      "The source of actual program, but two-space sequences were inserted in some places", 
      "  ",   -- we are replacing all two-space substrings
      ""      -- with an empty string
   )
)(...)

Program aktual (setelah menghapus semua pasangan spasi):

s = ...
for d = #s - 1, 0, -1 do
   for r = 1, #s - d do
      t = s:sub(r, r+d)
      if not t:find"(.).*%1" then
         print(t)
         return
      end
   end
end

BTW, cuplikan JS untuk menghitung skor gagal pada kode saya.

Retina 0.8.2 , 37 byte, skor 9

.
$&$'¶
(.)(?<=\1.+).*

O#$^`
$.&
1G`

Cobalah online! Terjemahan langsung dari jawaban ini ke Retina 1 menghemat satu byte dengan menggunakan Nalih-alih O#. Namun, jika Anda bermain golf dengan Retina 1 dengan jawaban hingga 28 byte, nilainya sebenarnya naik menjadi 10! Penjelasan:

.
$&$'¶

Hasilkan semua sufiks input.

(.)(?<=\1.+).*

Untuk setiap akhiran, ambil awalan hingga karakter duplikat pertama.

O#$^`
$.&

Urutkan string yang tersisa dalam urutan terbalik panjang (yaitu terpanjang pertama).

1G`

Ambil yang terpanjang.

Jelly , skor 2, 14 byte

Ẇµµff  Q  €  Ṫ

Terima kasih kepada @JonathanAllan untuk skor -1, +7 byte dan karena melihat bug.

Cobalah online!

Bagaimana itu bekerja

Ẇµµff  Q  €  Ṫ  Main link. Argument: s (string)

Ẇ               Window; yield all substrings of s, sorted by length.
 µ              Begin a new chain. Argument: A (array of substrings)
  µ             Begin a new chain. Argument: A (array of substrings)
   f            Filter A by presence in itself. Does nothing.
       Q  €     Unique each; deduplicate all strings in A.
    f           Filter A by presence in the array of deduplicated substrings,
                keeping only substrings composed of unique characters.
             Ṫ  Tail; take the last (longest) kept substring.

Bersih , skor 7 5, 276 byte

@[ss:s]=rr(pp[][ss:s])((@s))
@s=s
ee x[rr:xx]|e x rr=True=ee x xx
ee x xx=f
f=e'e'' '
e::!  Char  !  Char  ->Bool
e  _ _=  code  {

eqC
}
pp p[r:rr]|ee r p=p=pp(a r p)rr
pp a _=a
a  x[ll:l]=[ll:a x  l]
a l ll=[l]
l[]rr=e'l''l'
l ff[]=f

l[r:rr][ss:ll]=l rr ll
rr x y|l x y=y=x

Cobalah online! Terima kasih kepada @ Οurous untuk menunjukkan kepada saya bahwa mungkin untuk memanggil kode mesin ABC langsung dari dalam Bersihkan. Ini memungkinkan untuk menyingkirkan leher botol sebelumnyaimport yang menetapkan skor minimal ke 7, tetapi membutuhkan kata kuncicode yang menetapkan skor minimal 5 untuk pendekatan ini.

Versi kode yang tidak dioptimalkan dan tidak dioptimalkan skor dapat ditemukan di sini: Coba online!

Versi sebelumnya dengan skor 7, 158 154 130 byte

import  StdEnv  
@[xx:rr]=c(%[][xx:rr])(@rr)
@e=e
c s b|  length  s<  length  b=b=s
%s[xx:r]|  isMember xx s=s= %(s++[xx])r
%r _=r

Cobalah online!

Dengan importskor tidak dapat pergi di bawah 7. Tanpa impor orang perlu menerapkan kesetaraan pada string atau karakter tanpa fungsi perpustakaan yang mungkin tidak mungkin, seperti yang dapat dilihat pada versi baru di atas.

Python 3 , skor 4, 155 byte

exec(('l=la''mbd''a f'',e=en''ume''rat''e:m''ax''([f[ j  :k]  for  j,i in e ( f)f''or  k,i in e ( f )if  len  ( { *''f[j'':k]''})==k-''j],''key''=le''n)'))

Ini mendefinisikan suatu fungsi l.

Terima kasih kepada @xnor karena menunjukkan bahwa string dengan panjang 3 tidak meningkatkan skor, menghemat 32 byte.

Cobalah online!

Brachylog , skor 2, 19 byte

s  ᶠ  l  ᵒ  ≠  ˢ  t

Cobalah online!

Hanya jawaban "ruang segalanya" yang membosankan. Setidaknya saya mengetahui bahwa metapredicate dapat ditempatkan jauh dari predikat dan masih berfungsi (dan subskrip dan superskrip (parametrik) tidak dapat).

s ᶠ - temukan semua substring dari string yang diberikan

l ᵒ - pesan berdasarkan panjangnya (naik secara default)

≠ ˢ - pilih yang memiliki semua elemen berbeda

t - dapatkan ekor (elemen terakhir) dari itu - yang memiliki panjang terbesar

Pyth , 11 byte, skor 4

Skor -4 berkat Dennis

e lD {I# .:

elD{I#.:Q      Full program, inputs "string" from stdin and outputs to stdout
e              The last element of the list generated by taking
      .:Q      All substrings of the input
     #         Filtered for
   {I          Being invariant over deduplicate i.e. being "non-repeating"
 lD            and sorted by length

Cobalah online!

Sekam , skor 2, 10 byte

►IIËII≠IIQ

Cobalah online!

Penjelasan

Program ini setara dengan ini:

►Ë≠Q  Implicit input.
   Q  List of substrings.
►     Find one that maximizes:
 Ë    all ordered pairs
  ≠   are inequal.

Built-in Ëmengevaluasi ≠pada semua pasangan yang berurutan dari argumennya x, dan kembali length(x)+1jika setiap hasil benar, jika tidak0 . Ketika kami memaksimalkan ini, kami menemukan string terpanjang yang tidak memiliki karakter berulang.

Dalam pengajuan, saya hanya menyisipkan fungsi identitas Iantara masing-masing fungsi, dua kali. Karena IËsama dengan Ë, I≠sama dengan ≠dan seterusnya, ini tidak mengubah semantik. Satu-satunya bahaya adalah bahwa fungsi urutan yang lebih tinggi dapat memutuskan untuk menggunakan salah satu dari Iargumennya, tetapi untungnya hal itu mengarah pada kesalahan ketik dalam program kami, jadi itu tidak terjadi.

Clojure, skor 4

#(  let  [N  (fn  [[_ & r]] r) R  (fn  R [f v c]  (if  c (R f (f v (  nth  c 0))  ( N  c)) v)) C  (fn  C  (  [i]  (C (  seq  i) 0)) ( [i  n]  (if i (C ( N  i )  (  inc n)) n)))  J  (fn  [c  i]  (assoc c (C  c) i)) I  (fn  F [f i n R]  (if ( =  (C  R) n) R (F f (f  i) n ( J  R (f  i)))))] ( apply  str  (R ( fn  [a  b] ( if  (< (C  a)  (C  b)) b a )) "" (  for  [k  (I N % (C  % ) [])]  (R  ( fn [ t  c ] ( if ( or ( = t (  str t) ) ((  set t)c))(apply  str t) ( J  t c)))[]k)))))

Oh man ini menyakitkan! Nmengimplementasikan next, Ris reduce, Cis count, Jis conj(hanya berfungsi untuk vektor) dan Iis iterate. apply strapakah ada dua kali karena kalau tidak input "aaaa" tidak akan mengembalikan string tetapi vektor [\a]. Untungnya saya harus menggunakan applydan assoc, saya tidak tahu Anda bisa membuat satu indeks di luar elemen terakhir vektor: o

Jelly , skor 5, 10 byte

ẆµQQ⁼µÐfµṪ

Cobalah online!

Python 3 , skor 4, 317 byte

exec(('%s'  *58  %(  's=','in','pu','t(',');','pr','in','t(','so','rt','ed','((s','[i',':j',']f','or',' j',' i','n ','ra','ng','e(','1,','le','n(','s)','+1',')f','or',' i',' i','n ','ra','ng','e(','j)','if',' l','en','(s','et','(s','[i',':j',']))','==l','en','(s','[i',':j',']))',',k','ey','=l','en',')[','-1','])')))

Cobalah online!

Kode belum dijawab:

s=input();print(sorted((s[i:j]for j in range(1,len(s)+1)for i in range(j)if len(set(s[i:j]))==len(s[i:j])),key=len)[-1])

lambda aberisi mbda yang memiliki skor 5, dan kebutuhan fungsi returnyang tampaknya tidak bisaexec diedit (sehingga membutuhkan skor setidaknya 5 untuk eturn), sehingga program lengkap diperlukan. Mungkin saja untuk mengurangi ukuran kode yang belum pernah dilakukan sebelumnya, tetapi saya tidak dapat melihat peningkatan yang jelas dan cepat.

Alice , 40 byte

/ii..nn$$@@BBww..DD~~FF..!!nn$$KK??oo@@

(Mengikuti baris baru)

Cobalah online!

Penunjuk instruksi bergerak secara diagonal dalam mode ordinal, jadi hanya setiap karakter lain yang dieksekusi.

[email protected]~F.!n$K?o@

i     take input
.n$@  terminate if empty
B     push all nonempty substrings, with the longest on the top of the stack
w     push return address (start main loop)
.     make copy of current substring
D     deduplicate characters
~     swap: this places the original above the deduplicated copy
F     Push the original string if it is a substring of the deduplicated copy
      (which can only happen if they're equal); otherwise push empty string
.!    place a copy on the tape
n$K   if the empty string was pushed, return to start of loop
o     output
@     terminate

Perl 6 , skor: 15 10 8, panjang: 46 55 62 byte

{~m:ov/(.+)<!{$0.comb.repeated}>/.max(&chars)}

Menguji

{~m:ov/(..*)<!{(($0)).comb.repeated}>{{}}/.max(&chars)}

Menguji

{m:ov:i/(..*)<!{(($0)).comb.repeated}>{{}}/.max((&chars)).Str}

Menguji

Diperluas:

{    # bare block lambda with implicit parameter ｢$_｣

    m                          # match (implicitly against ｢$_｣)
    :overlap                   # in every single way possible
    :ignorecase                # add a ｢:｣ to break up substring
    /

      (..*)                    # match at least one character

      <!{
        (($0)).comb.repeated  # backtrack if there were repeats
      }>

      {{}}                    # anon hash in code block (no-op)
    /

    .max((&chars))            # get the longest

    .Str                      # coerce to a Str (from a Match object)
}

Java 8, skor 9 (384 B) 7 (401 B)

S -> { int s = 0 , e = 0 , l = 0 , x = 0 , y = 0 , b [ ] = new int [ 256 ] ; for ( ; x <S.  length  & y <S.  length  & l <S.  length  - x ; x ++ ) { b [S[x]] = 1 ; for ( y ++ ; y <S.  length  && b [S[y]] < 1 ; b [S[y ++]] = 1 ) ; if ( l < y - x ) { s = x ; e = y ; l = y - x ; } for ( ; y <S.  length  && x < y & S[x] != S[y  ];)b [S[x ++]] = 0 ; }  String g=""; for( ; s<e ; g+= S[s++]);  return  g;}

• Versi awal. Akan turun dari sini. Skor adalah 9 karena "ubstring ", jadi substringakan menjadi bagian pertama yang diganti.
• Skor sekarang 7 karena " length", yang saya mungkin tidak akan dapat mengurangi lebih lanjut .. Saya ragu mungkin untuk menjatuhkan empat penggunaan length. Jika memungkinkan, " eturn"(6) mungkin menurunkan skor dengan 1 sebagai peningkatan akhir, tapi saya kira ini dia (kecuali mungkin pengurangan kecil dalam byte-count ..)

Cobalah online.

Haskell , skor 7

-4 Terima kasih untuk Laikoni.

import  Data.List  
f s=snd $ maximum [ (0<$i ,i)|i<-  tails  =<<inits s, nub i==i]

Cobalah online!

Mathematica, skor 11 9

Length@Last@Select[Subsequences[Characters@#],#==DeleteDuplicates  @#&]&

Memotong beberapa byte dari string terpanjang yang tidak terulang dengan mengaburkan nama fungsi:

Length@Last@Select[Subsequences[Characters  @#],#==(  ToExpression@ 
StringJoin@@FromCharacterCode@{{68},{101},{108},{101},{116},{101},{68},{117},
{112},{108},{105},{99},{97},{116},{101},{115}}))@#&]&

Kotlin , skor: 11 10 9 byte, panjang: 227 246 245 byte

indices
  .flatMap { p -> indices . map { p to p + it } }
  .  filter { (r,i) -> i < length  }
  .map { ( s , a )->substring  (  s,  a  ) }
  .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
  .maxBy { it.length }

Yang terpanjang adalah ubstring , yaitu 9 karakter

Disebut seperti ini:

val c = "Good morning, Green orb!"

fun String.c(): String? = indices
    .flatMap { p -> indices . map { p to p + it } }
    .  filter { (r,i) -> i < length  }
    .map { ( s , a )->substring  (  s,  a  ) }
    .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
    .maxBy { it.length }

fun main(args: Array<String>) {
    val text = """indices
    .flatMap { p -> indices . map { p to p + it } }
    .  filter { (r,i) -> i < length  }
    .map { ( s , a )->substring  (  s,  a  ) }
    .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
    .maxBy { it.length }"""
    val message = text.c()!!
    println(message)
    println(text.length)
    println(message.length)
    println(c.c())
}

Pyth , skor 3 (  18  14 byte)

e  fq  T{T  .:

Cobalah online!

Substring non-berulang terpanjang adalah  .:.

05AB1E , 22 byte | Skor: 2

Œ  ʒ  D  Ù  Q  }  é  ¤

-1 skor + 7 byte berkat HeebyJeeby

Cobalah online!

05AB1E , 15 byte | Nilai: 3

Œ ʒ D Ù Q } é ¤

Cobalah online!

05AB1E , 8 byte | Nilai: 8

ŒʒDÙQ}é¤

Cobalah online!

05AB1E sebenarnya dapat melakukan sesuatu yang agak murah ... menambahkan spasi putih ke 05AB1E tidak melakukan apa-apa.

Jika ada aturan yang menentang ini, saya juga bisa menggunakan ´dan menyukai 7 karakter lainnya.