Lebih besar dari kurang dari lebih dari sesuatu yang mencurigakan

45

Dengan panjang N string kurang dari dan lebih besar dari tanda ( <, >), masukkan bilangan bulat 0 sampai N pada awal dan akhir dan di antara setiap pasangan tanda sedemikian rupa sehingga semua ketidaksetaraan dipenuhi. Keluarkan string yang dihasilkan. Jika ada beberapa output yang valid, output salah satu (dan hanya satu) dari mereka.

Sebagai contoh

<<><><<

memiliki 7 karakter sehingga semua angka dari 0 hingga 7 harus dimasukkan. Output yang valid adalah

2<3<4>1<5>0<6<7

karena semua ketidaksetaraan diambil satu per satu

2<3
3<4
4>1
1<5
5>0
0<6
6<7

itu benar.

Jika diinginkan, output mungkin memiliki ruang di sekitar tanda, misalnya 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7.

Kode terpendek dalam byte menang.

Uji Kasus

Baris pertama setelah baris kosong adalah input dan baris berikutnya adalah masing-masing contoh output yang valid.

[empty string]
0

<
0<1

>
1>0

<<
0<1<2

<>
1<2>0

><
1>0<2
2>0<1

>>
2>1>0

<<<
0<1<2<3

><>
1>0<3>2

>><
3>2>0<1
3>1>0<2
2>1>0<3

>>>
3>2>1>0

>>><<<
3>2>1>0<4<5<6
6>3>1>0<2<4<5
4>2>1>0<3<5<6
4>3>1>0<2<5<6

<<><><<
2<3<4>1<5>0<6<7

>><><>>
7>6>0<5>1<4>3>2

<<<<<<<<<<<<<<
0<1<2<3<4<5<6<7<8<9<10<11<12<13<14

>><<<<><>><><<
6>5>4<7<8<9<10>3<11>2>1<12>0<13<14
14>5>4<7<8<9<10>3<11>2>1<12>0<13<6
Hobi Calvin
sumber
4
Apakah akan selalu ada output yang valid?
mbomb007
3
@ mbomb007 Ya. Paling tidak selalu ada satu.
Calvin Hobbies
23
Saya ingin melihat seseorang memprogram ini di> <>! Itu akan luar biasa (dan ironisnya saya kira?)
Soren
Ini benar-benar menyenangkan tetapi hanya tantangan, terima kasih op
Shaun Wild

Jawaban:

29

Retina , 20 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.


$.'
S`>
%O#`\d+
¶
>

Cobalah online! (Baris pertama memungkinkan test-suite yang dipisahkan dengan linefeed.)

Penjelasan

Cara sederhana untuk menemukan permutasi yang valid adalah mulai dengan memasukkan angka dari 0ke Ndalam urutan, dan kemudian membalikkan angka yang mengelilingi setiap substring dari >s. Ambil <><<>>><<sebagai contoh:

0<1>2<3<4>5>6>7<8<9
  ---   -------      these sections are wrong, so we reverse them
0<2>1<3<7>6>5>4<8<9

Kedua tugas itu cukup sederhana di Retina, meskipun yang benar-benar dapat kita kerjakan adalah string. Kita dapat menyimpan byte tambahan dengan memasukkan angka-angka dari Nbawah ke 0dan membalikkan bagian di sekitarnya <sebagai gantinya, tetapi prinsipnya sama.

Tahap 1: Substitusi


$.'

Kami mulai dengan memasukkan panjang $'(sufiks, yaitu semuanya setelah pertandingan) ke setiap posisi yang mungkin dalam input. Ini memasukkan angka dari Nbawah ke 0.

Tahap 2: Berpisah

S`>

Kami membagi input >menjadi beberapa baris terpisah, sehingga setiap baris terdiri dari nomor individual atau daftar nomor yang digabungkan <.

Tahap 3: Sortir

%O#`\d+

Dalam setiap baris ( %) kami mengurutkan ( O) angka ( \d#) berdasarkan nilai numeriknya ( #). Karena kami memasukkan angka dalam urutan angka terbalik, ini membalikkannya.

Tahap 4: Substitusi

¶
>

Kami mengubah umpan baris menjadi >lagi untuk menggabungkan semuanya kembali menjadi satu baris. Itu dia.

Sebagai catatan, saya bermaksud menambahkan cara untuk diterapkan %ke pembatas selain dari linefeeds. Seandainya saya sudah melakukan itu, pengiriman ini akan menjadi 14 byte, karena kemudian tiga tahap terakhir akan dikurangi menjadi satu:

%'>O#`\d+
Martin Ender
sumber
Bagaimana itu seperti ukuran sepersepuluh dari ukuran saya? Kerja bagus.
ThreeFx
@ThreeFx Karena saya tidak menggunakan kekerasan. ;) Penjelasan datang sebentar lagi.
Martin Ender
22

> <> , 46 43 35 + 4 untuk  -s== 39 byte

0&l?!v:3%?\&:n1+$o!
+nf0.>&n; >l&:@

Ini adalah implementasi dari algoritma xnor di> <>.

Dibutuhkan string input pada tumpukan ( -sditandai dengan penerjemah standar).

Anda dapat mencobanya di juru bahasa online .

Harun
sumber
2
> <> sepertinya bahasa yang pas untuk tantangan ini.
anaximander
21

> <> , 26 + 4 = 30 byte

l22pirv
1+$2po>:3%::2g:n$-

Cobalah online! +4 byte untuk -s=flag - jika -stidak apa-apa (itu berarti bahwa flag harus dihapus seluruhnya untuk input kosong), maka itu akan menjadi +3.

Mengasumsikan bahwa input STDIN kosong sehingga imenghasilkan -1 (yang dilakukannya pada EOF). Program gagal mencoba mencetak -1 ini sebagai char.

Menggunakan pendekatan max-of-nums-so-far-for- >, min-of-nums-so-far-for-far <.

[Setup]
l22p         Place (length of stack) = (length of input) into position (2, 2) of
             the codebox. Codebox values are initialised to 0, so (0, 2) will
             contain the other value we need.
i            Push -1 due to EOF so that we error out later
r            Reverse the stack
v            Move down to the next line
>            Change IP direction to rightward

[Loop]
:3%          Take code point of '<' or '>' mod 3, giving 0 or 2 respectively
             (call this value c)
:            Duplicate
:2g          Fetch the value v at (c, 2)
:n           Output it as a number
$-1+         Calculate v-c+1 to update v
$2p          Place the updated value into (c, 2)
o            Output the '<' or '>' as a char (or error out here outputting -1)

Program yang keluar dengan bersih dan tidak membuat asumsi tentang STDIN adalah 4 byte tambahan:

l22p0rv
p:?!;o>:3%::2g:n$-1+$2
Sp3000
sumber
12

CJam , 16 byte

l_,),.\'</Wf%'<*

Cobalah online!

Port jawaban Retina saya .

Penjelasan

l    e# Read input.
_,   e# Duplicate, get length N.
),   e# Get range [0 1 2 ... N].
.\   e# Riffle input string into this range.
'</  e# Split around '<'.
Wf%  e# Reverse each chunk.
'<*  e# Join with '<'.
Martin Ender
sumber
11

Perl, 29 byte

Termasuk +2 untuk -lp

Jalankan dengan input pada STDIN, mis

order.pl <<< "<<><><<"

Keluaran:

0<1<7>2<6>3<4<5

order.pl:

#!/usr/bin/perl -lp
s%%/\G</?$a++:y///c-$b++%eg

Penjelasan

Memiliki dua penghitung, maks dimulai dengan panjang string, min dimulai dengan 0. Kemudian pada setiap batas (termasuk awal dan akhir string) jika itu tepat sebelum <menempatkan minimum di sana dan meningkat sebesar 1, jika tidak menempatkan maksimum di sana dan mengurangi dengan 1 (pada akhir string tidak masalah yang Anda ambil karena keduanya sama)

Ton Hospel
sumber
s{}{/\G/...}Saya belum pernah melihat itu sebelumnya, ini brilian.
Primo
10

Python 2, 67 byte

f=lambda s,i=0:s and`i+len(s)*(s>'=')`+s[0]+f(s[1:],i+(s<'>'))or`i`

Fungsi rekursif. Memenuhi masing-masing operator pada gilirannya dengan menempatkan nilai terkecil yang tidak digunakan xuntuk x<dan terbesar untuk x>. Nilai terkecil yang tidak digunakan disimpan idan diperbarui, dan nilai terbesar yang tidak terpakai disimpulkan dari idan panjang yang tersisa.

Tidak
sumber
1
Saya pikir Anda bisa melakukan (s>'=')alih - alih (s>='>')menyimpan byte?
mathmandan
@mathmandan Terima kasih! Aneh <dan >tidak ada codepoint yang berurutan.
xnor
Sepakat! Tapi saya kira saya bisa melihat bagaimana masuk akal untuk memiliki =antara <dan >.
mathmandan
8

Python 2, 163 137 byte

from random import*
def f(v):l=len(v)+1;N=''.join(sum(zip(sample(map(str,range(l)),l),v+' '),()));return N if eval(N)or len(v)<1else f(v)

Kocok nomor-nomornya sampai pernyataannya diubah True.

Cobalah.

ahli atlasologi
sumber
Ini jelas yang paling masuk akal dari semua jawaban.
moopet
7

APL, 33 byte

⍞←(S,⊂''),.,⍨-1-⍋⍋+\0,1-2×'>'=S←⍞

⍋⍋ berguna luar biasa.

Penjelasan

⍞←(S,⊂''),.,⍨-1-⍋⍋+\0,1-2×'>'=S←⍞
                                   ⍞ read a string from stdin      '<<><><<'
                                 S←   store it in variable S
                             '>'=     test each character for eq.   0 0 1 0 1 0 0
                         1-2×         1-2×0 = 1, 1-2×1 = ¯1         1 1 ¯1 1 ¯1 1 1
                                      (thus, 1 if < else ¯1)
                       0,             concatenate 0 to the vector   0 1 1 ¯1 1 ¯1 1 1
                     +\               calculate its running sum     0 1 2 1 2 1 2 3
                   ⍋                 create a vector of indices    1 2 4 6 3 5 7 8
                                      that sort the vector in
                                      ascending order
                 ⍋                   do it again: the compound ⍋⍋ 1 2 5 3 6 4 7 8
                                      maps a vector V to another
                                      vector V', one permutation of
                                      the set of the indices of V,
                                      such that
                                            V > V  => V' > V'.
                                             i   j     i    j
                                      due to this property, V and V'
                                      get sorted in the same way:
                                          ⍋V = ⍋V' = ⍋⍋⍋V.
              -1-                     decrement by one              0 1 4 2 5 3 6 7
      ⊂''                            void character vector         ⊂''
    S,                                concatenate input string     '<<><><<' ⊂''
   (     ),.,⍨                       first concatenate each        0 '<' 1 '<' 4 '>' 2 \
                                     element of the result vector  '<' 5 '>' 3 '<' 6 '<' \
                                     with the cordisponding        7 ⊂''
                                     element in the input string,
                                     then concatenate each result
⍞←                                  write to stdout
Oberon
sumber
3
Apa yang dilakukan pohon Natal ( ⍋⍋)?
Conor O'Brien
naik peringkat, yang mengembalikan indeks dalam urutan terurut. Dengan melakukannya dua kali, Anda mendapatkan di 1mana angka terkecil, di 2mana angka terkecil berikutnya, dll.
Zwei
@ ConorO'Brien diedit dengan penjelasan singkat.
Oberon
Ya, sangat singkat ._.
Conor O'Brien
7

JavaScript (ES6), 74 56 byte

s=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j

Mulai dengan set angka 0...N. Pada setiap tahap hanya mengambil yang terbesar ( l) atau paling sedikit ( j) dari angka yang tersisa; angka berikutnya harus kurang dari atau lebih besar dari itu. Sunting: Disimpan sebesar 18 byte berkat @Arnauld.

Neil
sumber
3
Dapatkah Anda menggunakan replace? Mungkins=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
Arnauld
@Arnauld ... dan saya pikir saya baik-baik saja untuk bermain golf pada upaya pertama saya (yang tidak setuju untuk diganti oleh replace) turun menjadi 74 byte ...
Neil
5

Pyth - 19 byte

Hore untuk perbandingan rantai!

!QZhv#ms.idQ.p`Mhl

Tidak bekerja secara online karena aman dari eval.

Maltysen
sumber
4

2sable , 20 byte

gUvy'<Qi¾¼ëXD<U}y}XJ

Penjelasan

gU                     # store input length in variable X
  v              }     # for each char in input
   y'<Qi               # if current char is "<"
        ¾¼             # push counter (initialized as 0), increase counter
          ëXD<U}       # else, push X and decrease value in variable X
                y      # push current char
                  XJ   # push the final number and join the stack

Cobalah online!

Untuk N <10 ini bisa jadi 14 byte:

ÎvyN>}J'<¡í'<ý
Emigna
sumber
4

C #, 102 99 byte

string f(string s){int i=0,j=s.Length;var r="";foreach(var c in s)r=r+(c<61?i++:j--)+c;return r+i;}

Tidak Disatukan:

string f(string s)
{
    int i = 0, j = s.Length;    // Used to track the lowest and highest unused number.
    var r = "";                 // Start with the empty string.

    foreach (var c in s)        // For each character in the input string:
        r = r +                 // Append to the result:
            (c < 61             // If the current character is '<':
                ? i++           // Insert the lowest unused number,
                : j--)          // otherwise, insert the highest unused number.
            + c;                // And append the current character.

    return r + i;               // Return the result with the last unused number appended.
}
Scepheo
sumber
Saya lelah, jadi saya bisa melewatkan sesuatu, tetapi tidakkah mengubah r = r +bagian menjadi tugas gabungan menghemat beberapa byte?
Carcigenicate
2
Tidak - r+bagian di sebelah kanan memberi tahu kompiler bahwa semuanya adalah string, jadi representasi string cdigunakan. Jika saya menggunakan r+=, ?:bagian akan mengevaluasi ke int, nilai ordinal cakan ditambahkan ke itu dan hanya kemudian akan dikonversi ke representasi stringnya.
Scepheo
4

Java 8, 126 125 byte

s->{int t=s.replaceAll("<","").length(),y=t-1;String r=t+++"";for(char c:s.toCharArray())r+=(c+"")+(c<61?t++:y--);return r;};

Saya tidak berpikir ini bekerja hehe

Program tes tidak digabungkan

public static void main(String[] args) {
    Function<String, String> function = s -> {
        int t = s.replaceAll("<", "").length(), y = t - 1;
        String r = t++ + "";
        for (char c : s.toCharArray()) {
            r += (c + "") + (c < 61 ? t++ : y--);
        }
        return r;
    };

    System.out.println(function.apply("<<><><<"));
    System.out.println(function.apply(">>><<<"));
    System.out.println(function.apply(">>>"));
    System.out.println(function.apply("<<<"));
    System.out.println(function.apply(">><><>>"));
}
Shaun Wild
sumber
Anda dapat mengubah .replaceAllto .replacedan menghapus tanda kurung sekitar (c+"")untuk menghemat 5 byte.
Kevin Cruijssen
@KevinCruijssen Tidak arsed sekitar 5 byte hahah.
Shaun Wild
Saat menggunakan bahasa golf yang tepat, 5 byte adalah perbedaan antara tempat ke-5 dan ke-2. Dengan java itu perbedaan antara tempat terakhir sejauh ini dan hanya tempat terakhir.
Shaun Wild
Java hampir selalu menjadi yang terakhir dengan tantangan kode-golf, tetapi alasan kami memposting jawaban Java adalah untuk bersenang-senang menulisnya sesingkat mungkin. Saya pribadi sudah senang jika kode Java saya beralih dari 500 ke 499 dalam hal byte. ; P
Kevin Cruijssen
Kami pada dasarnya mengabaikan semua pesaing dan hanya bersaing dengan atau pengiriman Java / C # dll.
Shaun Wild
4

Jelly , 27 14 12 byte

Port solusi @Martin Enders CJam
-2 bytes berkat @Dennis

żJ0;µFṣ”<Uj”<

Uji di TryItOnline

Bagaimana?

żJ0;Fṣ”<Uj”< - main link takes an argument, the string, e.g. ><>
 J           - range(length(input)), e.g. [1,2,3]
  0          - literal 0
   ;         - concatenate, e.g. [0,1,2,3]
ż            - zip with input, e.g. [[0],">1","<2",">3"]
    F        - flatten, list, e.g. "0>1<2>3"
      ”<  ”< - the character '<'
     ṣ       - split, e.g. ["0>1","2>3"]
        U    - upend (reverse) (implicit vectorization), e.g. ["1>0","3>2"]
         j   - join, e.g. "1>0<3>2"

Metode sebelumnya menarik secara matematis, tetapi tidak begitu ...

=”>U
LR!×ÇĖP€S‘
L‘ḶŒ!ị@ÇðżF

Ini menggunakan sistem basis faktorial untuk menemukan indeks permutasi [0, N] yang akan memenuhi persamaan.

Jonathan Allan
sumber
1
Uvektorisasi, jadi Anda tidak perlu . żJ0;menyimpan byte lain.
Dennis
4

Clojure, 152 132 126 byte

(defn f[s](loop[l 0 h(count s)[c & r]s a""](if c(case c\<(recur(inc l)h r(str a l c))(recur l(dec h)r(str a h c)))(str a l))))

Menyimpan jumlah byte yang adil dengan menghilangkan spasi sebanyak mungkin. Saya menyadari spasi tidak diperlukan untuk memisahkan tanda kurung dari karakter lain.

Pada dasarnya port Clojure dari jawaban @ Scepheo. Bekerja secara identik.

Mereka recurpanggilan pembunuh! Saya kira saya bisa menggunakan atom untuk membersihkannya. The swap!panggilan yang dibutuhkan untuk atom penggunaan ditambahkan ke hitungan: /

Terima kasih kepada @amalloy karena telah menyelamatkan saya beberapa byte.

Tidak Disatukan:

(defn comp-chain [chain-str]
  (loop [l 0 ; Lowest number
         h (count chain-str) ; Highest number
         [c & cr] chain-str ; Deconstruct the remaining list
         a ""] ; Accumulator
    (if c ; If there's any <>'s left
      (if (= c \<) ; If current char is a <...
        (recur (inc l) h cr (str a l c)) ; Add l to a, and inc l
        (recur l (dec h) cr (str a h c))) ; Add h to a, and dec h
      (str a l)))) ; Add on the remaining lowest number, and return
Carcigenicate
sumber
Selamat datang di situs ini!
DJMcMayhem
@DJMcMayhem Terima kasih. Mudah-mudahan nanti lain kali saya dapat menemukan solusi saya sendiri daripada hanya mengirim jawaban lain.
Carcigenicate
Anda dapat menyimpan dua ruang lagi di looppenjilidan, sebelum sdan sesudah a. Anda juga bisa mencukur sedikit dengan mengganti ifpohon dengan case: (case c \< (recur ...) nil (str ...) (recur ...)). Dan tentu saja crbisa menjadi nama yang lebih pendek.
amalloy
@amalloy Poin bagus, terima kasih. Saya akan memperbarui ketika saya mendapatkan di laptop saya.
Carcigenicate
3

Haskell, 162 byte

import Data.List
(a:b)%(c:d)=show c++a:b%d
_%[x]=show x
f l=map(l%).filter(l#)$permutations[0..length l]
(e:f)#(x:y:z)=(e!x)y&&f#(y:z)
_#_=0<1
'>'!x=(>)x
_!x=(<)x

Ini sangat panjang.

ThreeFx
sumber
3

Perl (107 + 1 untuk -p) 108

for$c(split''){$s.=$i++.$c;}
for$b(split'<',$s.$i){$h[$j]=join'>',reverse split'>',$b;$j++;}
$_=join'<',@h;

Algoritma dicuri dari jawaban Martin Ender

Riley
sumber
2

Ruby, 135 byte

g=gets
puts g.nil?? 0:[*0..s=g.size].permutation.map{|a|a.zip(g.chars)*""if s.times.map{|i|eval"%s"*3%[a[i],g[i],a[i+1]]}.all?}.compact

Catatan: Kompleksitas waktu besar (O (n!)).

cia_rana
sumber
2

Python 2, 176 172 byte

Ini tidak terlalu singkat dibandingkan dengan yang lain, tapi saya senang saya menyelesaikannya dengan cepat.

from itertools import*
def f(s):
 for p in permutations(range(len(s)+1)):
    n=list(s);p=list(p);t=[p.pop()]+list(chain(*zip(n,p)));r="".join(map(str,t))
    if eval(r):return r

Cobalah online

Tidak Disatukan:

from itertools import*
def f(s):
    n=list(s);R=range(len(s)+1)
    for p in permutations(R):
        p=list(p)
        r=[p.pop()]
        t=n+p
        t[::2]=n
        t[1::2]=p
        r="".join(map(str,r+t))
        if eval(r):return r

Cobalah online

mbomb007
sumber
bagian interlace bisa jauh lebih pendek dilakukan melaluizip
Maltysen
@ Malaltysen Tidak satu ton lebih pendek, karena daftar tidak panjang yang sama (saya masih harus pop), tetapi sedikit lebih pendek. Jika N<10, saya bisa membuat pengerasan menjadi lebih pendek.
mbomb007
1

PHP, 190 Bytes

acak acak hingga ada solusi yang valid

$x=range(0,$l=strlen($q=$argv[1]));while(!$b){$b=1;$t="";shuffle($x);for($i=0;$i<$l;){$t.=$x[$i].$q[$i];if(($q[$i]==">"&$x[$i]<$x[$i+1])|($q[$i]=="<"&$x[$i]>$x[1+$i++]))$b=0;}}echo$t.$x[$i];

381 Bytes dapatkan semua solusi dan pilih satu

<?php $d=range(0,strlen($q=$argv[1]));echo $q."\n";$e=[];function f($t=""){global$e,$d,$q;foreach($d as$z){preg_match_all("#\d+#",$t,$y);if(in_array($z,$y[0]))continue;$p=preg_match_all("#[<>]#",$t);$g="";if(preg_match("#\d+$#",$t,$x)){if(($q[$p]==">"&$x[0]<$z)|($q[$p]=="<"&$x[0]>$z))continue;$g=$q[$p];}strlen($q)==$p+1|!$q?$e[]=$t.$g.$z:f($t.$g.$z);}}f();echo$e[array_rand($e)];
Jörg Hülsermann
sumber