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
code-golf
math
arithmetic
permutations
integer
Pasatiempos de Calvin
fuente
fuente
Respuestas:
Retina , 20 bytes
El recuento de bytes asume la codificación ISO 8859-1.
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
0
aN
en orden y luego invertir los números que rodean cada subcadena de>
s. Toma<><<>>><<
como ejemplo: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
N
abajo0
e 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 deN
abajo a0
.Etapa 2: Split
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
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:fuente
> <> ,
464335 + 4 para-s=
= 39 bytesEsta es una implementación del algoritmo de xnor en> <>.
Toma la cadena de entrada en la pila (
-s
marca con el intérprete estándar).Puede probarlo en el intérprete en línea .
fuente
> <> , 26 + 4 = 30 bytes
Pruébalo en línea! +4 bytes para el
-s=
indicador: si solo-s
está 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
i
produce -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-<
.Un programa que sale limpiamente y no supone que STDIN tiene 4 bytes adicionales:
fuente
CJam , 16 bytes
Pruébalo en línea!
Un puerto de mi respuesta Retina .
Explicación
fuente
Perl, 29 bytes
Incluye +2 para
-lp
Ejecutar con entrada en STDIN, por ejemplo
Salida:
order.pl
: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)fuente
s{}{/\G/...}
Nunca había visto eso antes, es brillante.Python 2, 67 bytes
Una función recursiva. Satisface a cada operador por turno poniendo el valor más pequeño sin usar
x
parax<
y el más grande parax>
. El valor no utilizado más pequeño se almacenai
y actualiza, y el valor no utilizado más grande se deduce dei
y la longitud restante.fuente
(s>'=')
lugar de(s>='>')
guardar un byte?<
y>
no son puntos de código consecutivos.=
entre<
y>
.Python 2,
163137 bytesBaraja los números hasta que la instrucción evalúe
True
.Intentalo.
fuente
APL, 33 bytes
⍋⍋
es inusualmente útilExplicación
fuente
⍋⍋
)?⍋
es subir de grado, que devuelve indicaciones en orden ordenado. Al hacerlo dos veces, obtienes1
dónde estaba el número más pequeño,2
dónde estaba el siguiente número más pequeño, etc.JavaScript (ES6),
7456 bytesComienza 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.fuente
replace
? Quizáss=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
replace
) hasta 74 bytes ...Pyth - 19 bytes
¡Hurra por el encadenamiento de comparación!
No funciona en línea porque evalúa la seguridad.
fuente
2sable , 20 bytes
Explicación
Pruébalo en línea!
Para N <10 esto podría haber sido 14 bytes:
fuente
C #,
10299 bytesSin golf:
fuente
r = r +
parte a una asignación compuesta, salvo un par de bytes?r+
parte en el lado derecho le dice al compilador que todo es una cadena, por lo quec
se utiliza la representación de cadena . Si lo usarar+=
, la?:
parte se evaluaría en anint
, el valor ordinal dec
se agregaría a eso y solo entonces se convertiría a su representación de cadena.Java 8,
126125bytesNo creo que esto funcione incluso jeje
Programa de prueba sin golf
fuente
.replaceAll
a.replace
y quitar el paréntesis alrededor(c+"")
de ahorrar 5 bytes.Gelatina ,
27 1412 bytesPuerto de la solución @Martin Enders CJam
-2 bytes gracias a @Dennis
Pruébelo en TryItOnline
¿Cómo?
El método anterior era matemáticamente interesante, pero no tan golfoso ...
Esto utiliza el sistema de base factorial para encontrar un índice de las permutaciones de [0, N] que satisfará la ecuación.
fuente
U
vectoriza, por lo que no necesitas€
.żJ0;
guarda otro byte.Clojure,
152132126 bytesAhorré 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
recur
llamadas son asesinas!Supongo que podría haber usado átomos para limpiarlo.Lasswap!
llamadas requeridas para usar átomos agregados al conteo: /Gracias a @amalloy por salvarme unos pocos bytes.
Sin golf:
fuente
loop
enlace, antess
y despuésa
. También podría recortar un poco reemplazando elif
árbol con uncase
:(case c \< (recur ...) nil (str ...) (recur ...))
. Y, por supuesto,cr
podría ser un nombre más corto.Haskell, 162 bytes
Esto es jodidamente largo.
fuente
Perl (107 + 1 para -p) 108
Algoritmo robado de la respuesta de Martin Ender ♦
fuente
Ruby, 135 bytes
Nota: La complejidad del tiempo es grande (O (n!)).
fuente
Python 2,
176172 bytesNo es muy corto en comparación con los demás, pero estoy feliz de haberlo resuelto tan rápido.
Pruébalo en línea
Sin golf:
Pruébalo en línea
fuente
zip
pop
), pero es un poco más corto. SiN<10
, podría acortar la cadena.PHP, 190 bytes
barajar aleatoriamente hasta que exista una solución válida
381 bytes obtienen todas las soluciones y eligen una
fuente