Większy niż mniej niż większy niż coś podejrzanego

45

Biorąc pod uwagę ciąg N długości mniejszy niż i większy niż znaki ( <, >), wstaw liczby całkowite od 0 do N na początku i na końcu oraz pomiędzy każdą parą znaków, aby wszystkie nierówności zostały spełnione. Wyprowadza wynikowy ciąg. Jeśli istnieje wiele prawidłowych wyników, wypisz dowolne (i tylko jedno) z nich.

Na przykład

<<><><<

ma 7 znaków, więc należy wstawić wszystkie cyfry od 0 do 7 włącznie. Prawidłowe wyjście to

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

ponieważ wszystkie nierówności były podejmowane pojedynczo

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

są prawdziwe.

W razie potrzeby na wyjściu mogą znajdować się spacje otaczające znaki, np 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7.

Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

Pierwszy wiersz po pustym wierszu jest wejściem, a następne wiersze są prawidłowymi przykładami danych wyjściowych.

[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
Hobby Calvina
źródło
4
Czy zawsze będzie prawidłowy wynik?
mbomb007
3
@ mbomb007 Tak. Zawsze jest co najmniej jeden.
Calvin's Hobbies
23
Chcę zobaczyć, jak ktoś to programuje w> <>! To byłoby niesamowite (i ironiczne, jak sądzę?)
Soren
To było naprawdę zabawne, ale po prostu wyzwanie, dzięki op
Shaun Wild

Odpowiedzi:

29

Siatkówka , 20 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.


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

Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).

Wyjaśnienie

Prostym sposobem na znalezienie prawidłowej permutacji jest rozpoczęcie od wstawienia liczb od 0do Nw kolejności, a następnie odwrócenie liczb otaczających każdy podciąg >s. Weź <><<>>><<jako przykład:

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

Oba te zadania są dość proste w Retinie, mimo że wszystko, z czym naprawdę możemy pracować, to łańcuchy. Możemy zaoszczędzić dodatkowy bajt, wstawiając liczby od Ndołu do 0i odwracając otaczające sekcje <, ale zasada jest taka sama.

Etap 1: Zmiana


$.'

Zaczynamy od wstawienia długości $'(sufiksu, czyli wszystkiego po dopasowaniu) w każdej możliwej pozycji na wejściu. To wstawia liczby od Ndo 0.

Etap 2: Podział

S`>

Podzieliliśmy dane wejściowe >na osobne linie, więc każda linia jest albo indywidualną liczbą, albo listą liczb połączonych <.

Etap 3: Sortuj

%O#`\d+

W obrębie każdej linii ( %) sortujemy ( O) liczby ( \d#) według ich wartości liczbowej ( #). Ponieważ wstawiliśmy liczbę w odwrotnej kolejności numerycznej, powoduje to ich odwrócenie.

Etap 4: Zmiana

¶
>

Zamieniamy >ponownie źródła linii, aby połączyć wszystko z powrotem w jedną linię. Otóż ​​to.

Na marginesie chciałem dodać sposób zastosowania %do innych ograniczników niż linie. Gdybym to zrobił, przesłanie to miałoby 14 bajtów, ponieważ wówczas trzy ostatnie etapy zostałyby zredukowane do jednego:

%'>O#`\d+
Martin Ender
źródło
Jak to jest, że jeden ósmy mojego rozmiaru? Dobra robota.
ThreeFx
@ThreeFx Ponieważ nie używam brutalnej siły. ;) Wyjaśnienie za chwilę.
Martin Ender
22

> <> , 46 43 35 + 4 dla  -s== 39 bajtów

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

Jest to implementacja algorytmu xnor w> <>.

Pobiera ciąg wejściowy na stosie ( -sflaga ze standardowym interpreterem).

Możesz to wypróbować na tłumaczu online .

Aaron
źródło
2
> <> wydaje się być odpowiednim językiem dla tego wyzwania.
anaximander
21

> <> , 26 + 4 = 30 bajtów

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

Wypróbuj online! +4 bajty dla -s=flagi - jeśli tylko -sjest w porządku (oznaczałoby to, że flaga musiałaby zostać całkowicie usunięta z powodu pustych danych wejściowych), to zamiast tego byłoby +3.

Zakłada, że ​​wejście STDIN jest puste, więc idaje -1 (co robi na EOF). Program popełnił błąd podczas próby wydrukowania tego -1 jako znaku.

Wykorzystuje podejście max-of-nums-dotychczas-dotychczas-for- >, min-of-nums-dotychczas-dotychczas-for- <.

[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, który kończy się czysto i nie przyjmuje założenia o STDIN, ma 4 dodatkowe bajty:

l22p0rv
p:?!;o>:3%::2g:n$-1+$2
Sp3000
źródło
12

CJam , 16 bajtów

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

Wypróbuj online!

Port mojej odpowiedzi Retina .

Wyjaśnienie

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
źródło
11

Perl, 29 bajtów

Obejmuje +2 za -lp

Uruchom z wejściem na STDIN, np

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

Wynik:

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

order.pl:

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

Wyjaśnienie

Posiadaj dwa liczniki, maks. Zaczynając od długości łańcucha, min zaczynając od 0. Następnie na każdej granicy (w tym na początku i na końcu łańcucha), jeśli jest tuż przed <wstawieniem minimum tam i zwiększ o 1, w przeciwnym razie umieść tam maksimum i zmniejsz o 1 (na końcu ciągu nie ma znaczenia, który licznik bierzesz, ponieważ oba są takie same)

Ton Hospel
źródło
s{}{/\G/...}Nigdy wcześniej tego nie widziałem, jest genialny.
primo
10

Python 2, 67 bajtów

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

Funkcja rekurencyjna. Spełnia każdy operator kolejno oddanie najmniejszą niewykorzystaną wartość xdla x<a największe dla x>. Najmniejsza nieużywana wartość jest przechowywana ii aktualizowana, a największa nieużywana wartość jest wywnioskowana na ipodstawie pozostałej długości.

xnor
źródło
1
Myślę, że możesz zrobić (s>'=')zamiast (s>='>')zaoszczędzić bajt?
mathmandan
@mathmandan Thanks! To dziwne <i >nie są to kolejne punkty kodowe.
xnor
Zgoda! Ale wydaje mi się, że widzę, jak sensowne byłoby mieć =między <a >.
matmandan
8

Python 2, 163 137 bajtów

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)

Tasuje liczby, aż oświadczenie przejdzie do True.

Spróbuj.

atlasolog
źródło
Jest to zdecydowanie najbardziej sensowna ze wszystkich odpowiedzi.
moopet
7

APL, 33 bajty

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

⍋⍋ jest niezwykle przydatny.

Wyjaśnienie

⍞←(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
źródło
3
Co robią choinki ( ⍋⍋)?
Conor O'Brien
to ocena w górę, która zwraca wskaźniki w posortowanej kolejności. Robiąc to dwa razy, dostajesz, 1gdzie była najmniejsza liczba, 2gdzie była następna najmniejsza liczba, itd.
Zwei,
@ ConorO'Brien edytowany z krótkim wyjaśnieniem.
Oberon
Tak, bardzo krótko ._.
Conor O'Brien
7

JavaScript (ES6), 74 56 bajtów

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

Zaczyna się od zestawu liczb 0...N. Na każdym etapie po prostu bierze największą ( l) lub najmniejszą ( j) z pozostałych liczb; następny numer musi być z definicji mniejszy lub większy niż ten. Edycja: Zaoszczędź 18 bajtów dzięki @Arnauld.

Neil
źródło
3
Można użyć replace? Możes=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
Arnauld
@Arnauld ... i myślałem, że dobrze sobie radzę w golfa po mojej pierwszej próbie (której nie można zastąpić replace) do 74 bajtów ...
Neil
5

Pyth - 19 bajtów

Brawo dla łączenia łańcuchów!

!QZhv#ms.idQ.p`Mhl

Nie działa online, ponieważ istnieje absolutne bezpieczeństwo.

Maltysen
źródło
4

2sable , 20 bajtów

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

Wyjaśnienie

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

Wypróbuj online!

Dla N <10 może to być 14 bajtów:

ÎvyN>}J'<¡í'<ý
Emigna
źródło
4

C #, 102 99 bajtów

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

Nie golfowany:

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
źródło
Jestem zmęczony, więc mogłem coś przeoczyć, ale czy nie zmieniłbym r = r +części na złożone zadanie , gdyby nie kilka bajtów?
Carcigenicate
2
Nie - r+część po prawej stronie informuje kompilator, że cała rzecz jest ciągiem, dlatego cużywana jest reprezentacja ciągu . Gdybym użył r+=, ?:część byłaby oceniana na int, cdodawana byłaby do niej wartość porządkowa , i tylko wtedy byłaby konwertowana na reprezentację ciągu.
Scepheo,
4

Java 8, 126 125 bajtów

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

Nie sądzę, że to nawet działa hehe

Nie testowany program testowy

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
źródło
Można zmienić .replaceAll, aby .replacei usuń nawiasy wokół (c+"")zaoszczędzić 5 bajtów.
Kevin Cruijssen
@KevinCruijssen Nie wynosił około 5 bajtów hahah.
Shaun Wild,
Przy stosowaniu odpowiedniego języka golfowego 5 bajtów stanowi różnicę między 5. a 2. miejscem. W Javie jest to różnica między ostatnim miejscem a ostatnim miejscem.
Shaun Wild,
Java prawie zawsze będzie ostatnia z wyzwaniami związanymi z golfem, ale powodem, dla którego publikujemy odpowiedzi na Javę, jest przyjemność pisania jej tak krótko, jak to możliwe. Osobiście jestem już szczęśliwy, jeśli mój kod Java zmienia się z 500 na 499 pod względem bajtów. ; P
Kevin Cruijssen
Zasadniczo ignorujemy wszystkich konkurentów i po prostu konkurujemy ze zgłoszeniami Java / C # itp.
Shaun Wild,
4

Galaretka , 27 14 12 bajtów

Port rozwiązania @Martin Enders CJam
-2 bajty dzięki @Dennis

żJ0;µFṣ”<Uj”<

Przetestuj w TryItOnline

W jaki sposób?

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

Poprzednia metoda była interesująca matematycznie, ale nie tak golfowa ...

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

Wykorzystuje on system bazowy silni do znalezienia indeksu permutacji [0, N], który spełni równanie.

Jonathan Allan
źródło
1
Uwektoryzuje, więc nie potrzebujesz . żJ0;zapisuje kolejny bajt.
Dennis
4

Clojure, 152 132 126 bajtów

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

Zaoszczędził sporo bajtów, eliminując tyle spacji, ile mogłem. Uświadomiłem sobie, że białe znaki nie są konieczne do oddzielenia nawiasu od innej postaci.

Zasadniczo port Clojure odpowiedzi @ Scepheo. Działa identycznie.

Te recurpołączenia są zabójcze! Podejrzewam, że mógłbym użyć atomów do oczyszczenia go. Do swap!połączenia wymagane do korzystania atomów dodany do hrabiego: /

Dzięki @amalloy za uratowanie mi kilku bajtów.

Nie golfowany:

(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
źródło
Witamy na stronie!
DJMcMayhem
@DJMcMayhem Dzięki. Mam nadzieję, że następnym razem będę mógł wymyślić własne rozwiązanie zamiast po prostu przesłać inną odpowiedź.
Carcigenicate
Możesz zapisać jeszcze dwa spacje w looppowiązaniu, przed si po a. Można również golić trochę zastępując ifdrzewa z case: (case c \< (recur ...) nil (str ...) (recur ...)). I oczywiście crmoże to być krótsza nazwa.
amalloy
@amalloy Dobre punkty, dziękuję. Będę aktualizować, kiedy wejdę na laptopa.
Carcigenicate 9.09.16
3

Haskell, 162 bajty

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

To jest cholernie długie.

ThreeFx
źródło
3

Perl (107 + 1 dla -p) 108

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

Algorytm skradzione Martin Ender ♦ 's odpowiedź

Riley
źródło
2

Rubin, 135 bajtów

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

Uwaga: złożoność czasu jest duża (O (n!)).

cia_rana
źródło
2

Python 2, 176 172 bajtów

Nie jest bardzo krótki w porównaniu do innych, ale cieszę się, że rozwiązałem go tak szybko.

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

Wypróbuj online

Nie golfowany:

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

Wypróbuj online

mbomb007
źródło
część z przeplotem może być znacznie krótszazip
Maltysen
@Maltysen Nie tona krócej, ponieważ listy nie są tej samej długości (wciąż muszę pop), ale są nieco krótsze. Gdybym N<10mógł skrócić sznurowanie.
mbomb007,
1

PHP, 190 bajtów

losowe odtwarzanie losowe do momentu znalezienia prawidłowego rozwiązania

$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 bajtów dostaje wszystkie rozwiązania i wybiera jedno

<?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
źródło