Mayor que menor que mayor que algo sospechoso

45

Dada una longitud N cadena de signos menor que y mayor que ( <, >), inserte los enteros 0 a N al principio y al final y entre cada par de signos de manera que se satisfagan todas las desigualdades. Salida de la cadena resultante. Si hay varias salidas válidas, envíe una (y solo una) de ellas.

Por ejemplo

<<><><<

tiene 7 caracteres, por lo que deben insertarse todos los números del 0 al 7 inclusive. Una salida válida es

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

porque todas las desigualdades se toman una a la vez

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

son verdaderas.

Si lo desea, la salida puede tener espacios alrededor de los signos, por ejemplo 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7.

El código más corto en bytes gana.

Casos de prueba

La primera línea después de una línea vacía es la entrada y las siguientes líneas son ejemplos de salida válidos.

[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
Pasatiempos de Calvin
fuente
44
¿Habrá siempre una salida válida?
mbomb007
3
@ mbomb007 Sí. Siempre hay al menos uno.
Aficiones de Calvin
23
¡Quiero ver a alguien programar esto en> <>! Eso sería increíble (¿e irónico, supongo?)
Soren
Este fue un desafío realmente divertido, pero simple, gracias op
Shaun Wild

Respuestas:

29

Retina , 20 bytes

El recuento de bytes asume la codificación ISO 8859-1.


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

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Explicación

Una manera simple de encontrar una permutación válida es comenzar insertando los números de 0a Nen orden y luego invertir los números que rodean cada subcadena de >s. Toma <><<>>><<como ejemplo:

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

Ambas tareas son bastante simples en Retina, a pesar de que todo lo que realmente podemos trabajar son cadenas. Podemos guardar un byte adicional insertando los números desde Nabajo 0e invirtiendo las secciones que lo rodean <, pero el principio es el mismo.

Etapa 1: sustitución


$.'

Comenzamos insertando la longitud de $'(el sufijo, es decir, todo después del partido) en cada posición posible en la entrada. Esto inserta los números de Nabajo a 0.

Etapa 2: Split

S`>

Dividimos la entrada >en líneas separadas, por lo que cada línea es un número individual o una lista de números unidos <.

Etapa 3: ordenar

%O#`\d+

Dentro de cada línea ( %) clasificamos ( O) los números ( \d#) por su valor numérico ( #). Como insertamos el número en orden numérico inverso, esto los invierte.

Etapa 4: sustitución

¶
>

Convertimos los avances de línea >nuevamente para unir todo en una sola línea. Eso es.

Como nota al margen, he tenido la intención de agregar una forma de aplicar %a otros delimitadores que no sean los avances de línea. Si ya lo hubiera hecho, este envío habría sido de 14 bytes, porque las últimas tres etapas se habrían reducido a una sola:

%'>O#`\d+
Martin Ender
fuente
¿Cómo es eso como un octavo de mi tamaño? Buen trabajo.
ThreeFx
@ThreeFx Porque no uso la fuerza bruta. ;) Explicación en un minuto.
Martin Ender
22

> <> , 46 43 35 + 4 para  -s== 39 bytes

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

Esta es una implementación del algoritmo de xnor en> <>.

Toma la cadena de entrada en la pila ( -smarca con el intérprete estándar).

Puede probarlo en el intérprete en línea .

Aaron
fuente
2
> <> parece un lenguaje apropiado para este desafío.
anaximandro
21

> <> , 26 + 4 = 30 bytes

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

Pruébalo en línea! +4 bytes para el -s=indicador: si solo -sestá bien (significaría que el indicador debería eliminarse por completo para la entrada vacía), entonces sería +3 en su lugar.

Asume que la entrada STDIN está vacía, de modo que iproduce -1 (lo que hace en EOF). El programa comete errores al intentar imprimir este -1 como un carácter.

Utiliza el enfoque max-of-nums-so-far-far- for >, min-of-nums-so-far-far-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)

Un programa que sale limpiamente y no supone que STDIN tiene 4 bytes adicionales:

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

CJam , 16 bytes

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

Pruébalo en línea!

Un puerto de mi respuesta Retina .

Explicación

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

Perl, 29 bytes

Incluye +2 para -lp

Ejecutar con entrada en STDIN, por ejemplo

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

Salida:

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

order.pl:

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

Explicación

Tenga dos contadores, el máximo comienza con la longitud de la cadena, el mínimo comienza con 0. Luego, en cada límite (incluido el inicio y el final de la cadena) si está justo antes de <poner el mínimo allí y aumentar en 1; de lo contrario, ponga el máximo allí y disminuya por 1 (al final de la cadena no importa qué contador tome, ya que ambos son iguales)

Ton Hospel
fuente
s{}{/\G/...}Nunca había visto eso antes, es brillante.
primo
10

Python 2, 67 bytes

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

Una función recursiva. Satisface a cada operador por turno poniendo el valor más pequeño sin usar xpara x<y el más grande para x>. El valor no utilizado más pequeño se almacena iy actualiza, y el valor no utilizado más grande se deduce de iy la longitud restante.

xnor
fuente
1
Creo que podría hacer en (s>'=')lugar de (s>='>')guardar un byte?
mathmandan
@mathmandan ¡Gracias! Es extraño eso <y >no son puntos de código consecutivos.
xnor
¡Convenido! Pero supongo que puedo ver cómo tendría sentido tener =entre <y >.
Mathmandan
8

Python 2, 163 137 bytes

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)

Baraja los números hasta que la instrucción evalúe True.

Intentalo.

atlasólogo
fuente
Esta es claramente la más sensata de todas las respuestas.
moopet
7

APL, 33 bytes

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

⍋⍋ es inusualmente útil

Explicación

⍞←(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
fuente
3
¿Qué hacen los árboles de Navidad ( ⍋⍋)?
Conor O'Brien
es subir de grado, que devuelve indicaciones en orden ordenado. Al hacerlo dos veces, obtienes 1dónde estaba el número más pequeño, 2dónde estaba el siguiente número más pequeño, etc.
Zwei
@ ConorO'Brien editado con una breve explicación.
Oberon
Sí, muy corto ._.
Conor O'Brien
7

JavaScript (ES6), 74 56 bytes

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

Comienza con el conjunto de números 0...N. En cada etapa simplemente toma el mayor ( l) o el menor ( j) de los números restantes; el siguiente número debe, por definición, ser menor o mayor que eso. Editar: ahorró 18 bytes masivos gracias a @Arnauld.

Neil
fuente
3
Puedes usar replace? Quizáss=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
Arnauld
@Arnauld ... y pensé que estaba haciendo bien en mi primer intento de golf (que no era posible reemplazarlo replace) hasta 74 bytes ...
Neil
5

Pyth - 19 bytes

¡Hurra por el encadenamiento de comparación!

!QZhv#ms.idQ.p`Mhl

No funciona en línea porque evalúa la seguridad.

Maltysen
fuente
4

2sable , 20 bytes

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

Explicación

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

Pruébalo en línea!

Para N <10 esto podría haber sido 14 bytes:

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

C #, 102 99 bytes

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

Sin golf:

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
fuente
Estoy cansado, así que podría estar perdiendo algo, pero ¿no cambiaría la r = r +parte a una asignación compuesta, salvo un par de bytes?
Carcigenicate
2
No, la r+parte en el lado derecho le dice al compilador que todo es una cadena, por lo que cse utiliza la representación de cadena . Si lo usara r+=, la ?:parte se evaluaría en an int, el valor ordinal de cse agregaría a eso y solo entonces se convertiría a su representación de cadena.
Scepheo
4

Java 8, 126125 bytes

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

No creo que esto funcione incluso jeje

Programa de prueba sin golf

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
fuente
Se puede cambiar el .replaceAlla .replacey quitar el paréntesis alrededor (c+"")de ahorrar 5 bytes.
Kevin Cruijssen
@KevinCruijssen No se ha emitido aproximadamente 5 bytes jaja.
Shaun Wild
Cuando se utiliza un lenguaje de golf adecuado, 5 bytes son la diferencia entre el quinto y el segundo lugar. Con Java, es la diferencia entre el último lugar con diferencia y el último lugar.
Shaun Wild
Java casi siempre será el último en desafíos de golf de código, pero la razón por la que publicamos las respuestas de Java para empezar es por la diversión de escribirlo lo más breve posible. Personalmente, ya estoy contento si mi código Java pasa de 500 a 499 en términos de bytes. ; P
Kevin Cruijssen
Básicamente ignoramos a todos los competidores y solo competimos con envíos de Java / C #, etc.
Shaun Wild
4

Gelatina , 27 14 12 bytes

Puerto de la solución @Martin Enders CJam
-2 bytes gracias a @Dennis

żJ0;µFṣ”<Uj”<

Pruébelo en TryItOnline

¿Cómo?

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

El método anterior era matemáticamente interesante, pero no tan golfoso ...

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

Esto utiliza el sistema de base factorial para encontrar un índice de las permutaciones de [0, N] que satisfará la ecuación.

Jonathan Allan
fuente
1
Uvectoriza, por lo que no necesitas . żJ0;guarda otro byte.
Dennis
4

Clojure, 152 132 126 bytes

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

Ahorré una buena cantidad de bytes al eliminar tanto espacio en blanco como pude. Me di cuenta de que el espacio en blanco no es necesario para separar un paréntesis de otro personaje.

Básicamente un puerto Clojure de la respuesta de @ Scepheo. Funciona de manera idéntica.

¡Esas recurllamadas son asesinas! Supongo que podría haber usado átomos para limpiarlo. Las swap!llamadas requeridas para usar átomos agregados al conteo: /

Gracias a @amalloy por salvarme unos pocos bytes.

Sin golf:

(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
fuente
Bienvenido al sitio!
DJMcMayhem
@DJMcMayhem Gracias. Espero que la próxima vez pueda llegar a mi propia solución en lugar de simplemente portar otra respuesta.
Carcigenicate
Puede guardar dos espacios más en el loopenlace, antes sy después a. También podría recortar un poco reemplazando el ifárbol con un case: (case c \< (recur ...) nil (str ...) (recur ...)). Y, por supuesto, crpodría ser un nombre más corto.
amalloy
@amalloy Buenos puntos, gracias. Actualizaré cuando llegue a mi computadora portátil.
Carcigenicate
3

Haskell, 162 bytes

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

Esto es jodidamente largo.

ThreeFx
fuente
3

Perl (107 + 1 para -p) 108

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

Algoritmo robado de la respuesta de Martin Ender ♦

Riley
fuente
2

Ruby, 135 bytes

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

Nota: La complejidad del tiempo es grande (O (n!)).

cia_rana
fuente
2

Python 2, 176 172 bytes

No es muy corto en comparación con los demás, pero estoy feliz de haberlo resuelto tan rápido.

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

Pruébalo en línea

Sin golf:

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

Pruébalo en línea

mbomb007
fuente
la parte de entrelazado prolly puede ser mucho más corto realiza a través dezip
Maltysen
@Maltysen No es mucho más corto, porque las listas no tienen la misma longitud (todavía tengo que hacerlo pop), pero es un poco más corto. Si N<10, podría acortar la cadena.
mbomb007
1

PHP, 190 bytes

barajar aleatoriamente hasta que exista una solución válida

$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 obtienen todas las soluciones y eligen una

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