Plus que moins que plus que quelque chose de louche

45

Soit une chaîne de longueur N de signes inférieur et supérieur ( <, >), insérez les nombres entiers de 0 à N au début et à la fin et entre chaque paire de signes de sorte que toutes les inégalités soient satisfaites. Affiche la chaîne résultante. S'il existe plusieurs sorties valides, indiquez-en une (et une seule).

Par exemple

<<><><<

a 7 caractères donc tous les nombres de 0 à 7 inclus doivent être insérés. Une sortie valide est

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

parce que toutes les inégalités prises un à la fois

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

sont vrai.

Si vous le souhaitez, la sortie peut comporter des espaces entourant les signes, par exemple 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7.

Le code le plus court en octets gagne.

Cas de test

La première ligne après une ligne vide correspond à l'entrée et les lignes suivantes sont chacune des exemples de sortie valides.

[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
Les passe-temps de Calvin
la source
4
Y aura-t-il toujours une sortie valide?
mbomb007
3
@ mbomb007 Oui. Il y en a toujours au moins un.
Passe-temps de Calvin
23
Je veux voir quelqu'un programmer ceci dans> <>! Ce serait génial (et ironique je suppose?)
Soren
C'était un vrai plaisir, mais tout simplement un défi, merci
Shaun Wild le

Réponses:

29

Rétine , 20 octets

Le nombre d'octets suppose un codage ISO 8859-1.


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

Essayez-le en ligne! (La première ligne active une suite de tests séparée par saut de ligne.)

Explication

Un moyen simple de trouver une permutation valide consiste à commencer par insérer les nombres de 0à Ndans l'ordre, puis à inverser les nombres entourant chaque sous-chaîne de >s. Prenons <><<>>><<comme exemple:

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

Ces deux tâches sont relativement simples dans Retina, même si nous ne pouvons vraiment travailler qu'avec des chaînes. Nous pouvons enregistrer un octet supplémentaire en insérant les nombres de Nbas en bas 0et en inversant les sections environnantes <, mais le principe est le même.

Étape 1: substitution


$.'

Nous commençons par insérer la longueur de $'(le suffixe, c'est-à-dire tout ce qui suit le match) dans toutes les positions possibles de l'entrée. Cela insère les nombres de Nbas en 0.

Étape 2: Split

S`>

Nous >séparons les entrées en lignes distinctes. Chaque ligne est donc un numéro individuel ou une liste de nombres associés <.

Étape 3: Trier

%O#`\d+

Dans chaque ligne ( %), nous trions ( O) les nombres ( \d#) par leur valeur numérique ( #). Puisque nous avons inséré le nombre dans l'ordre numérique inverse, cela les inverse.

Étape 4: substitution

¶
>

Nous reconvertissons les sauts de ligne >afin de tout relier en une seule ligne. C'est ça.

En passant, j'ai voulu ajouter un moyen de l'appliquer %à d'autres délimiteurs que les sauts de ligne. Si j'avais déjà fait cela, cette soumission aurait été de 14 octets, car alors les trois dernières étapes auraient été réduites à une seule:

%'>O#`\d+
Martin Ender
la source
Comment est-ce que cela ressemble à un huit ma taille? Bon travail.
ThreeFx
@ThreeFx Parce que je n'utilise pas la force brute. ;) Explication venant dans une minute.
Martin Ender
22

> <> , 46 43 35 + 4 pour  -s== 39 octets

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

Ceci est une implémentation de l'algorithme de xnor dans> <>.

Il prend la chaîne d'entrée sur la pile ( -sindicateur avec l'interpréteur standard).

Vous pouvez l'essayer sur l' interprète en ligne .

Aaron
la source
2
> <> semble être un langage approprié pour ce défi.
Anaximander
21

> <> , 26 + 4 = 30 octets

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

Essayez-le en ligne! +4 octets pour le -s=drapeau - si cela vous -sconvient (cela voudrait dire que le drapeau devra être entièrement supprimé pour une entrée vide), il s'agira plutôt de +3.

Suppose que l'entrée STDIN est vide, ce qui iproduit -1 (ce qui est le cas avec EOF). Le programme fait une erreur en essayant d’imprimer ce -1 en tant que caractère.

Utilise l'approche max-of-nums-so-far-for- >, min-num-of-nums-so-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 programme qui se termine proprement et ne part pas de l'hypothèse à propos de STDIN est de 4 octets supplémentaires:

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

CJam , 16 octets

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

Essayez-le en ligne!

Un port de ma rétine répond .

Explication

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
la source
11

Perl, 29 octets

Comprend +2 pour -lp

Exécuter avec une entrée sur STDIN, par exemple

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

Sortie:

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

order.pl:

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

Explication

Avoir deux compteurs, max commençant par la longueur de la chaîne, min commençant par 0. Puis à chaque limite (y compris le début et la fin de la chaîne) s'il se trouve juste avant une valeur <minimum et augmenter de 1, sinon placer le maximum et diminuer par 1 (à la fin de la chaîne, le compteur que vous prenez n'a pas d'importance, car ils sont identiques)

Ton Hospel
la source
s{}{/\G/...}Je n'ai jamais vu ça auparavant, c'est génial.
Primo
10

Python 2, 67 octets

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

Une fonction récursive. Chaque opérateur répond à son tour en mettant la plus petite valeur non utilisée xpour x<et le plus grand pour x>. La plus petite valeur inutilisée est stockée iet mise à jour, et la plus grande valeur inutilisée est déduite de ila longueur restante.

Xnor
la source
1
Je pense que vous pourriez faire (s>'=')au lieu de (s>='>')sauvegarder un octet?
mathmandan
@mathmandan Merci! C'est bizarre <et ce >ne sont pas des points de code consécutifs.
xnor
D'accord! Mais je suppose que je peux voir comment il serait logique d'avoir =entre <et >.
mathmandan
8

Python 2, 163 137 octets

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)

Mélange les chiffres jusqu'à ce que la déclaration soit évaluée à True.

Essayez-le

atlasologue
la source
C'est clairement la plus sensée de toutes les réponses.
Moopet
7

APL, 33 octets

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

⍋⍋ est inhabituellement utile.

Explication

⍞←(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
la source
3
Que font les arbres de Noël ( ⍋⍋)?
Conor O'Brien
is grade up, qui renvoie les indicateurs dans l'ordre de tri. En le faisant deux fois, vous obtenez 1où le nombre le plus petit était, 2où le nombre le plus petit suivant était, ect.
Zwei
@ ConorO'Brien édité avec une courte explication.
Oberon
Oui, très court.
Conor O'Brien
7

JavaScript (ES6), 74 56 octets

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

Commence avec l'ensemble des nombres 0...N. À chaque étape, prend simplement le plus grand ( l) ou le plus petit ( j) des nombres restants; le nombre suivant doit par définition être inférieur ou supérieur à celui. Edit: Sauvegardé un énorme 18 octets grâce à @Arnauld.

Neil
la source
3
Pouvez-vous utiliser replace? Peuts=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
Arnauld
@Arnauld ... et je pensais bien faire du golf ma première tentative (qui ne pouvait pas être remplacée par replace) jusqu'à 74 octets ...
Neil
5

Pyth - 19 octets

Hourra pour la comparaison chaînage!

!QZhv#ms.idQ.p`Mhl

Ne fonctionne pas en ligne car de sécurité eval.

Maltysen
la source
4

2sable , 20 octets

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

Explication

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

Essayez-le en ligne!

Pour N <10, cela aurait pu être 14 octets:

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

C #, 102 à 99 octets

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

Ungolfed:

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
la source
Je suis fatigué, alors il se peut que je manque quelque chose, mais ne changerais-t-il pas la r = r +partie en une assignation composée, économiser quelques octets?
Carcigenicate
2
Non - la r+partie du côté droit indique au compilateur que le tout est une chaîne, donc la représentation de chaîne de cest utilisée. Si je l'utilisais r+=, la ?:partie serait évaluée à un int, la valeur ordinale de cserait ajoutée à celle-ci et alors seulement elle serait convertie en sa représentation sous forme de chaîne.
Scepheo
4

Java 8, 126 à 125 octets

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

Je ne pense pas que cela fonctionne même hehe

Programme de test non-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
la source
Vous pouvez modifier le .replaceAllpour .replaceet enlevez les parenthèses autour (c+"")de sauver 5 octets.
Kevin Cruijssen
@KevinCruijssen Pas arsed environ 5 octets hahah.
Shaun Wild
Lorsque vous utilisez une langue de golf appropriée, 5 octets représentent la différence entre la 5ème et la 2ème place. Avec Java, c'est la différence entre la dernière place de loin et juste la dernière place.
Shaun Wild
Java sera presque toujours dernier avec les défis liés au code-golf, mais la raison pour laquelle nous publions des réponses en Java est tout d'abord pour le plaisir de l'écrire aussi court que possible. Personnellement, je suis déjà heureux si mon code Java passe de 500 à 499 octets. ; P
Kevin Cruijssen
Nous ignorons fondamentalement tous les concurrents et ne faisons que rivaliser avec les soumissions Java / C #, etc.
Shaun Wild
4

Jelly , 27 14 12 bytes

Port de la solution CJam de @Martin Enders
-2 octets grâce à @Dennis

żJ0;µFṣ”<Uj”<

Testez-le sur TryItOnline

Comment?

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

La méthode précédente était intéressante du point de vue mathématique, mais pas si géniale ...

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

Ceci utilise le système de base factorielle pour trouver un index des permutations de [0, N] qui satisfera l’équation.

Jonathan Allan
la source
1
Uvectorise, de sorte que vous n'avez pas besoin . żJ0;enregistre un autre octet.
Dennis
4

Clojure, 152 132 126 octets

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

J'ai économisé un bon nombre d'octets en éliminant autant d'espaces que possible. J'ai réalisé que les espaces ne sont pas nécessaires pour séparer une parenthèse d'un autre personnage.

Fondamentalement, un portage Clojure de la réponse de @ Scepheo. Fonctionne de manière identique.

Ces recurappels sont tueurs! Je suppose que j'aurais pu utiliser des atomes pour le nettoyer. Les swap!appels nécessaires pour utiliser les atomes ajoutés au compte: /

Merci à @amalloy de m'avoir économisé quelques octets.

Ungolfed:

(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
la source
Bienvenue sur le site!
DJMcMayhem
@DJMcMayhem Merci. Espérons que la prochaine fois, je pourrai proposer ma propre solution au lieu de simplement porter une autre réponse.
Carcigenicate
Vous pouvez enregistrer deux autres espaces dans la loopliaison, avant set après a. Vous pouvez également vous raser un peu en remplaçant l' ifarbre avec case: (case c \< (recur ...) nil (str ...) (recur ...)). Et bien sûr, crpourrait être un nom plus court.
Amalloy
@ amalloy Bons points, merci. Je mettrai à jour lorsque je serai sur mon ordinateur portable.
Carcigenicate
3

Haskell, 162 octets

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

C'est friggin 'long.

ThreeFx
la source
3

Perl (107 + 1 pour -p) 108

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

Algorithme volé à la réponse de Martin Ender ♦

Riley
la source
2

Ruby, 135 octets

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

Remarque: la complexité temporelle est grande (O (n!)).

cia_rana
la source
2

Python 2, 176 172 octets

Ce n'est pas très court comparé aux autres, mais je suis heureux de l'avoir résolu si rapidement.

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

Essayez-le en ligne

Ungolfed:

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

Essayez-le en ligne

mbomb007
la source
la partie entrelacée peut être beaucoup plus courtezip
Maltysen
@Maltysen Pas beaucoup plus court, parce que les listes ne sont pas de la même longueur (je le dois toujours pop), mais c'est un peu plus court. Si N<10, je pouvais faire un stringing plus court.
mbomb007
1

PHP, 190 octets

mélange aléatoire jusqu'à ce qu'une solution valide existe

$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 octets ont toutes les solutions et en choisissent une

<?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
la source