Greater than less than greater than something fishy

Question

Given a length N string of less-than and greater-than signs (<, >), insert the integers 0 through N at the start and end and in between each pair of signs such that all the inequalities are satisfied. Output the resulting string. If there are multiple valid outputs, output any one (and just one) of them.

For example

<<><><<

has 7 characters so all the numbers from 0 to 7 inclusive must be inserted. A valid output is

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

because all the inequalities taken one at a time

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

are true.

If desired, the output may have spaces surrounding the signs, e.g. 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7.

The shortest code in bytes wins.

Test Cases

The first line after an empty line is the input and the next line(s) are each valid output examples.

[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

Answer 1

Retina, 20 bytes

Byte count assumes ISO 8859-1 encoding.

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

Try it online! (The first line enables a linefeed-separated test-suite.)

Explanation

A simple way to find a valid permutation is to start by inserting the numbers from 0 to N in order, and then to reverse the numbers surrounding each substring of >s. Take <><<>>><< as an example:

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

Both of those tasks are fairly simple in Retina, even though all we can really work with are strings. We can save an additional byte by inserting the numbers from N down to 0 and reversing the sections surrounding < instead, but the principle is the same.

Stage 1: Substitution

$.'

We start by inserting the length of $' (the suffix, i.e. everything after the match) into every possible position in the input. This inserts the numbers from N down to 0.

Stage 2: Split

S`>

We split the input around > into separate lines, so each line is either an individual number or a list of numbers joined with <.

Stage 3: Sort

%O#`\d+

Within each line (%) we sort (O) the numbers (\d#) by their numerical value (#). Since we inserted the number in reverse numerical order, this reverses them.

Stage 4: Substitution

¶
>

We turn the linefeeds into > again to join everything back into a single line. That's it.

As a side note, I've been meaning to add a way to apply % to other delimiters than linefeeds. Had I already done that, this submission would have been 14 bytes, because then the last three stages would have been reduced to a single one:

%'>O#`\d+

Answer 2

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

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

This is an implementation of xnor's algorithm in ><>.

It takes the input string on the stack (-s flag with the standard interpreter).

You can try it out on the online interpreter.

Answer 3

><>, 26 + 4 = 30 bytes

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

Try it online! +4 bytes for the -s= flag - if just -s is okay (it would mean that the flag would need to be dropped entirely for empty input), then that would be +3 instead.

Assumes that STDIN input is empty so that i produces -1 (which it does on EOF). The program errors out trying to print this -1 as a char.

Uses the max-of-nums-so-far-for->, min-of-nums-so-far-for-< approach.

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

A program which exits cleanly and does not make the assumption about STDIN is 4 extra bytes:

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

Answer 4

CJam, 16 bytes

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

Try it online!

A port of my Retina answer.

Explanation

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 '<'.

Answer 5

Perl, 29 bytes

Includes +2 for -lp

Run with input on STDIN, e.g.

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

Output:

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

order.pl:

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

Explanation

Have two counters, max starting with the string length, min starting with 0. Then at each boundary (including start and end of string) if it is just before a < put the minimum there and increase by 1, otherwise put the maximum there and decrease by 1 (at the end of the string it doesn't matter which counter you take since they are both the same)

Answer 6

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)

Shuffles the numbers until the statement evals to True.

Try it.

Answer 7

Python 2, 67 bytes

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

A recursive function. Satisfies each operator in turn by putting the smallest unused value x for x< and greatest for x>. The smallest unused value is stored in i and updated, and the largest unused value is inferred from i and the remaining length.

Answer 8

APL, 33 bytes

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

⍋⍋ is unusually useful.

Explanation

⍞←(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

Answer 9

JavaScript (ES6), 74 56 bytes

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

Starts with the set of numbers 0...N. At each stage simply takes the greatest (l) or least (j) of the remaining numbers; the next number must by definition be less than or greater than that. Edit: Saved a massive 18 bytes thanks to @Arnauld.

Answer 10

Pyth - 19 bytes

Hooray for comparison chaining!

!QZhv#ms.idQ.p`Mhl

Doesn't work online cuz of eval safety.

Answer 11

2sable, 20 bytes

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

Explanation

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

Try it online!

For N<10 this could have been 14 bytes:

ÎvyN>}J'<¡í'<ý

Answer 12

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

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

Answer 13

Java 8, 126 125 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;};

I don't think this even works hehe

Ungolfed test program

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(">><><>>"));
}

Answer 14

Jelly, 27 14 12 bytes

Port of @Martin Enders CJam solution
-2 bytes thanks to @Dennis

żJ0;µFṣ”<Uj”<

Test it at TryItOnline

How?

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

Previous method was interesting mathematically, but not so golfy...

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

This uses the factorial base system to find an index of the permutations of [0,N] that will satisfy the equation.

Answer 15

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

Saved a fair number of bytes by eliminating as much whitespace as I could. I realized whitespace isn't necessary to separate a parenthesis from another character.

Basically a Clojure port of @Scepheo's answer. Works identically.

Those recur calls are killer! I suppose I could have used atoms to clean it up. The swap! calls required to use atoms added to the count :/

Thanks to @amalloy for saving me a few bytes.

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

Answer 16

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

This is friggin' long.

Answer 17

Perl (107 + 1 for -p) 108

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

Algorithm stolen from Martin Ender♦'s answer

Answer 18

05AB1E, 13 12 bytes

õª€N'<¡íJ'<ý

Port of @MartinEnder's CJam answer, so make sure to upvote him as well!
-1 byte thanks to @Grimmy.

Try it online or verify all test cases.

Explanation:

õª            # Append an empty string to the (implicit) input-string as list,
              # which also converts the input-string to a list of characters
              #  i.e. "><>" → [">","<",">",""]
  €N          # Insert the 0-based index before each character in this list
              #  → [0,">",1,"<",2,">",3,""]
    '<¡      '# Split this list on "<"
              #  → [[0,">",1,],[2,">",3,""]]
       í      # Reverse the items of each inner list
              #  → [[1,">",0],["",3,">",2]]
        J     # Join each inner list into a string
              #  → ["1>0","3>2"]
         '<ý '# And join this list of strings with "<" delimiter
              #  → "1>0<3>2"
              # (after which the resulting string is output implicitly as result)

Answer 19

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

Note: Time complexity is large (O(n!)).

Answer 20

Python 2, 176 172 bytes

It's not very short compared to the others, but I'm happy that I solved it so quickly.

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

Try it online

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

Try it online

Answer 21

PHP , 190 Bytes

random shuffle till a valid solution exists

$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 get all solutions and pick one

<?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)];

Answer 22

Javascript (node.js), 94 bytes

Try it online

s=>[[0],...s].reduce((x,v,i)=>v>'<'?[...x.map(v=>v+1),0]:[...x,i]).reduce((x,v,i)=>x+s[i-1]+v)

Ungolfed:

s =>
  [[0],...s].reduce((x, v, i) =>
    v > '<' ?
      [...x.map(v => v + 1), 0] :
      [...x, i])
    .reduce((x, v, i) => x + s[i-1] + v)

Answer 23

Burlesque, 38 bytes

sarzPp{J'>=={PPl_}{PPg_j}x/iePp}]mPP?+

Try it online!

Using xnor's algorithm

sarz                      # Generate range [0,N_comp]
Pp                        # Push this into state stack
{
 J'>==                    # Non destructive test if is ">"
 {PPl_}{PPg_j}x/ie        # If it is, take the head of the range
                          # Else take the tail
 Pp                       # Push the remainder back to the state stack
}]m                       # Apply to each character and map result to string
PP                        # Take the remaining element from state stack
?+                        # Append it to the string

Burlesque, 61 bytes

)'.2co)PIsarzr@{2CO}m[jbcz[{**FL(&&)[+}^m:e!{~]3co{x/}^mgn}m[

Try it online!

A method using actually evaluating permutations of ints, longer partially due to trying to format the final answer sensibly.

)'.     # Add a "." before each character (.> is comparison in Burlesque)
2co)PI  # Split into comparison operators
sarzr@  # Create all permutations of [0,N_comp]
{2CO}m[ # Create ngrams of length 2 ({abc} -> {ab bc}
jbcz[   # Zip with the operators
{
 **FL   # Merge to form an operation of the form {a b .> b c .<}
 (&&)[+ # Append a bitwise and
}^m     # Apply to each element
:e!     # Filter for those which when evaluated produce true
{
 ~]     # Drop last element (&&)
 3co    # Split into chunks of three
 {x/}^m # Cycle and push each block
 gn     # Delete duplicate consecutive elements
}m[     # Apply to each group

Answer 24

Haskell, 95 bytes

s=show
('<':y)!(a:b)=s a++'<':y!b
(x:y)!z=s(last z)++x:y!init z
_!(y:_)=s y
f x=x![0..length x]

Try it online!

Answer 25

PHP, 165 156 110 bytes

$o=[$j=$i=$s=$m=0];for(;$i<strlen($n=$argn);)$o[]=$n[$i++]=='<'?++$m:--$s;for(;$j<=$i;)echo$o[$j]-$s,$n[$j++];

Try it online!

Ungolfed

<?php

$min=0;
$max=0;
$current=0;

$order = [0];

for ($i=0;$i<strlen($argn);$i++){
    $compare=$argn[$i];
    if ($compare=='<') {
        $max++;
        $current=$max;
    } else {
        $min--;
        $current=$min;
    }
    $order[] = $current;
}

for ($i=0;$i<=strlen($argn);$i++){
    echo ($order[$i]-$min);
    if ($i<strlen($argn)) echo $argn[$i];
}

Answer 26

Excel (Ver. 1911), 199 Bytes

Using iterative calculation (max iterations set to 1024)

B2 'Input
B3 =IF(B3=4^5,1,B3+1)
B4 =B3-1
C2 =SEQUENCE(LEN(B2))
D2 =ROW(C2#:C1)-1
E2 =IF(B4,IF(C2#=B4,IF(F2#=">",@SORT(G2#,,-1),G2),E2#),-C2#)
F2 =MID(B2,C2#,1)
G2 =FILTER(D2#,NOT(MMULT(N(D2#=TRANSPOSE(E2#)),C2#/C2#)))
H2 =CONCAT(E2#:F2#,G2) ' Output

Explanation

B2 'Input
B3 =IF(B3=4^5,1,B3+1) ' Keeps track of iteration number
B4 =B3-1 ' 0 index the iteration counter
C2 =SEQUENCE(LEN(B2)) ' Generate sequence to index input string
D2 =ROW(C2#:C1)-1 ' Create sequence [0..N]
E2 =IF(B4,IF(C2#=B4,IF(F2#=">",@SORT(G2#,,-1),G2),E2#),-C2#)
      ' On each iteration check if the current char is ">" pull the largest unused number,
      ' else pull the smallest
F2 =MID(B2,C2#,1) ' Break the input string into separate rows
G2 =FILTER(D2#,NOT(MMULT(N(D2#=TRANSPOSE(E2#)),C2#/C2#))) ' Set of unused numbers
H2 =CONCAT(E2#:F2#,G2) ' Concatenate numbers, gt/lt signs, and last unused number

Test Sample