45
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ Will there always be a valid output? \$\endgroup\$ – mbomb007 Sep 6 '16 at 21:51
  • 3
    \$\begingroup\$ @mbomb007 Yes. There always is at least one. \$\endgroup\$ – Calvin's Hobbies Sep 6 '16 at 21:52
  • 23
    \$\begingroup\$ I want to see someone program this in ><>! That would be awesome (and ironic I guess?) \$\endgroup\$ – Soren Sep 6 '16 at 23:25
  • \$\begingroup\$ This was a really fun but simply challenge, thanks op \$\endgroup\$ – Shaun Wild Sep 7 '16 at 15:00

20 Answers 20

10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you could do (s>'=') instead of (s>='>') to save a byte? \$\endgroup\$ – mathmandan Sep 9 '16 at 2:09
  • \$\begingroup\$ @mathmandan Thanks! It's weird that < and > are not consecutive codepoints. \$\endgroup\$ – xnor Sep 10 '16 at 19:00
  • \$\begingroup\$ Agreed! But I guess I can see how it would make sense to have = between < and >. \$\endgroup\$ – mathmandan Sep 11 '16 at 17:11
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is clearly the most sensible of all answers. \$\endgroup\$ – moopet Sep 8 '16 at 8:59
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Welcome to the site! \$\endgroup\$ – DJMcMayhem Sep 7 '16 at 16:34
  • \$\begingroup\$ @DJMcMayhem Thanks. Hopefully next time I'll be able to come up with my own solution instead of just porting another answer. \$\endgroup\$ – Carcigenicate Sep 7 '16 at 16:36
  • \$\begingroup\$ You can save two more spaces in the loop binding, before s and after a. You could also shave a bit by replacing the if tree with a case: (case c \< (recur ...) nil (str ...) (recur ...)). And of course cr could be a shorter name. \$\endgroup\$ – amalloy Sep 9 '16 at 4:22
  • \$\begingroup\$ @amalloy Good points, thank you. I'll update when I get on my laptop. \$\endgroup\$ – Carcigenicate Sep 9 '16 at 13:33
22
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ ><> seems like a fitting language for this challenge. \$\endgroup\$ – anaximander Sep 8 '16 at 10:35
21
\$\begingroup\$

><>, 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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ U vectorizes, so you don't need . żJ0; saves another byte. \$\endgroup\$ – Dennis Sep 7 '16 at 15:16
4
\$\begingroup\$

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(">><><>>"));
}
\$\endgroup\$
  • \$\begingroup\$ You can change the .replaceAll to .replace and remove the parenthesis around (c+"") to save 5 bytes. \$\endgroup\$ – Kevin Cruijssen Sep 8 '16 at 14:38
  • \$\begingroup\$ @KevinCruijssen Not arsed about 5 bytes hahah. \$\endgroup\$ – Shaun Wild Sep 9 '16 at 14:33
  • \$\begingroup\$ When using a proper golfing language, 5 bytes is the difference between 5th and 2nd place. With java it's the difference between last place by far and just last place. \$\endgroup\$ – Shaun Wild Sep 12 '16 at 8:17
  • \$\begingroup\$ Java will almost always be last with code-golfing challenges, but the reason we post Java answers to begin with is for the fun of writing it as short as possible. I personally am already happy if my Java code goes from 500 to 499 in terms of byte. ;P \$\endgroup\$ – Kevin Cruijssen Sep 12 '16 at 9:21
  • \$\begingroup\$ We basically ignore all over competitors and just compete with or Java/ C# submissions etc.. \$\endgroup\$ – Shaun Wild Sep 12 '16 at 11:07
1
\$\begingroup\$

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)];
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ the interlace part can prolly be much shorter done through zip \$\endgroup\$ – Maltysen Sep 6 '16 at 22:44
  • \$\begingroup\$ @Maltysen Not a ton shorter, because the lists aren't the same length (I still have to pop), but it is a bit shorter. If N<10, I could make stringifying shorter. \$\endgroup\$ – mbomb007 Sep 7 '16 at 13:38
4
\$\begingroup\$

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.
}
\$\endgroup\$
  • \$\begingroup\$ I'm tired, so I could be missing something, but wouldn't changing the r = r + part to a compound assignment save a couple bytes? \$\endgroup\$ – Carcigenicate Sep 7 '16 at 15:28
  • 2
    \$\begingroup\$ No - the r+ part on the right-hand side tells the compiler the entire thing is a string, so the string representation of c is used. If I used r+=, the ?: part would evaluate to an int, the ordinal value of c would be added to that and only then would it be converted to its string representation. \$\endgroup\$ – Scepheo Sep 7 '16 at 21:10
4
\$\begingroup\$

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'<¡í'<ý
\$\endgroup\$
11
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ s{}{/\G/...} I've never seen that before, it's brilliant. \$\endgroup\$ – primo Sep 11 '16 at 2:40
7
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Can you use replace? Maybe s=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j \$\endgroup\$ – Arnauld Sep 7 '16 at 0:29
  • \$\begingroup\$ @Arnauld ...and I thought I was doing well to golf my first attempt (which wasn't amenable to replacement by replace) down to 74 bytes... \$\endgroup\$ – Neil Sep 7 '16 at 7:48
3
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ What do the Christmas trees (⍋⍋) do? \$\endgroup\$ – Conor O'Brien Sep 6 '16 at 22:58
  • \$\begingroup\$ is grade up, which returns indicies in sorted order. By doing it twice, you get 1 where the smallest number was, 2 where the next smallest number was, ect. \$\endgroup\$ – Zwei Sep 6 '16 at 23:23
  • \$\begingroup\$ @ConorO'Brien edited with a short explanation. \$\endgroup\$ – Oberon Sep 6 '16 at 23:28
  • \$\begingroup\$ Yes, very short ._. \$\endgroup\$ – Conor O'Brien Sep 6 '16 at 23:44
2
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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 '<'.
\$\endgroup\$
5
\$\begingroup\$

Pyth - 19 bytes

Hooray for comparison chaining!

!QZhv#ms.idQ.p`Mhl

Doesn't work online cuz of eval safety.

\$\endgroup\$
29
\$\begingroup\$

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+
\$\endgroup\$
  • \$\begingroup\$ How is that like one eigth my size? Nice work. \$\endgroup\$ – ThreeFx Sep 6 '16 at 22:14
  • \$\begingroup\$ @ThreeFx Because I don't use brute force. ;) Explanation coming in a minute. \$\endgroup\$ – Martin Ender Sep 6 '16 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.