10
\$\begingroup\$

Intro

So I've been wasting my time again researching suffix sorting algorithms, evaluating new ideas by hand and in code. But I always struggle to remember the type of my suffixes! Can you tell me which type my suffixes are?

Left-most what?

A lot of suffix sorting algorithms (SAIS, KA, my own daware) group suffixes into different types in order to sort them. There are two basic types: S-type and L-type suffixes. S-type suffixes are suffixes that are lexicographically less (Smaller) than the following suffix and L-type if it is lexicographically greater (Larger). A left-most S-type (LMS-type) is just that: A S-type suffix that is preceeded by a L-type suffix.

The special thing about these LMS-type suffixes is that once we sorted them we can sorted all the other suffixes in linear time ! Isn't that awesome?

The challenge

Given a string assume it is terminated by a special character that is less than any other character in that string (e.g. smaller than even the null byte). Output a type corrosponding char for each suffix.

You can freely choose which char to use for which type but I'd prefer L, S and * for L-, S- and LMS-type as long as they are all printable (0x20 - 0x7E).

Example

Given the string mmiissiissiippi output (when using L, S and *):

 LL*SLL*SLL*SLLL

For example the first L is due to the fact that mmiissiissiippi$ is lexicographically greater than miissiissiippi$ (the $ represents the added minimal character):

L - mmiissiissiippi$ > miissiissiippi$
L - miissiissiippi$  > iissiissiippi$
* - iissiissiippi$   < issiissiippi     and preceeded by L
S - issiissiippi$    < ssiissiippi$
L - ssiissiippi$     > siissiippi$
L - siissiippi$      > iissiippi$
* - iissiippi$       < issiippi$        and preceeded by L
S - issiippi$        < ssiippi$
L - ssiippi$         > siippi$
L - siippi$          > iippi$
* - iippi$           < ippi$            and preceeded by L
S - ippi$            < ppi$
L - ppi$             > pi$
L - pi$              > i$
L - i$               > $

Some more examples:

"hello world" -> "L*SSL*L*LLL"
"Hello World" -> "SSSSL*SSLLL"
"53Ab§%5qS"   -> "L*SSL*SLL"

Goal

I'm not here to annoy Peter Cordes (I'm so gonna do this on stackoverflow sometime); I'm just very lazy so this is of course ! The shortest answer in bytes wins.


Edit: The order of the chars is given by their byte value. That means compare should be like C's strcmp.

Edit2: Like stated in the comments output should be a single character for each input character. While I assumed that would be understood as "return a string" it seems at least 1 answer returns a list of single characters. In order to not invalidate the existing answers I will allow you to return a list of single characters (or integers which when printed result in only 1 char).


Tips for linear time:

  1. It can be done in 2 parallel forward iterations or in a single backward iteration.
  2. The state of each suffix depends only on the first 2 chars and the type of the second.
  3. Scanning the input in reverse direction you can determine L or S like this: $t=$c<=>$d?:$t (PHP 7), where $c is the current char $d the previous and $t the previous type.
  4. See my PHP answer. Tomorrow I will award the bounty.
\$\endgroup\$
  • \$\begingroup\$ This is my first question :) Sandbox got two upvotes and no comments so I think its ready to be posted. Feel free to make suggestions ! \$\endgroup\$ – Christoph Jun 13 '17 at 5:55
  • \$\begingroup\$ What characters can appear in the input? \$\endgroup\$ – Martin Ender Jun 13 '17 at 5:58
  • \$\begingroup\$ @MartinEnder all chars your string supports e.g. even the null byte for c++ style strings. Think of it as binary data. \$\endgroup\$ – Christoph Jun 13 '17 at 5:59
  • \$\begingroup\$ What does * mean? \$\endgroup\$ – Leaky Nun Jun 13 '17 at 6:03
  • \$\begingroup\$ @LeakyNun * means the corresponding suffix is of type left most s-type. A S-type suffix that is preceeded by a L-type suffix.. \$\endgroup\$ – Christoph Jun 13 '17 at 6:05

10 Answers 10

7
\$\begingroup\$

Haskell, 64 53 48 42 bytes

(0!)
k!(x:y)|x:y>y=1:2!y|2>1=k:0!y
_![]=[]

Try it online!

Ungolfed, with Char instead of Int:

suffixes :: String -> String
suffixes = go 'S'
 where
   go :: Char -> String -> String
   go _ "" = ""
   go lorstar s | s > tail s = 'L' : go '*' (tail s)
                | otherwise  = lorstar : go 'S' (tail s)
\$\endgroup\$
  • \$\begingroup\$ Anonymous functions are allowed, so the z= can be removed. \$\endgroup\$ – Ørjan Johansen Jun 13 '17 at 15:17
  • \$\begingroup\$ I just can't read Haskell. Would you mind giving me a brief explaination? \$\endgroup\$ – Christoph Jun 13 '17 at 17:04
  • 1
    \$\begingroup\$ @Christoph : the go function takes two arguments. The first is the character that represents what should be used to describe the S situation. The second is a string. It goes through that string recursively, removing the first character at each step (that's what tail does). The trick is that the first argument is set to * when the previous result was a L, or S otherwise. That way, in the case where an * or an S should be used, that first argument can be used directly. Hope that makes sense. \$\endgroup\$ – bartavelle Jun 13 '17 at 20:58
  • \$\begingroup\$ That's quite a nice idea ! I'm hoping to see more clever ideas :) \$\endgroup\$ – Christoph Jun 13 '17 at 21:04
  • \$\begingroup\$ @ØrjanJohansen how am I supposed to prepare the result in TIO? \$\endgroup\$ – bartavelle Jun 13 '17 at 21:36
6
\$\begingroup\$

Jelly,  25 23 21 20  19 bytes

Ṛ;\UỤỤIṠµI2n×ịØDṚ;0

A full program that prints the list of characters, using:

L: 0
S: 8
*: 9

(As a link it returns a list where all items are characters except the last one, which is a zero.)

Try it online! or see the test suite (with conversion to LS*).

How?

Ṛ;\UỤỤIṠµI2n×ịØDṚ;0 - Link: list of characters, s  e.g. "cast"
Ṛ                   - reverse                           "tsac"
  \                 - cumulative reduce by:
 ;                  -   concatenation                   ["t","ts","tsa","tsac"]
   U                - upend (reverse each)              ["t","st","ast","cast"] (suffixes)
    Ụ               - sort indexes by value             [3,4,2,1] (lexicographical order)
     Ụ              - sort indexes by value             [4,3,1,2] (order of that)
      I             - incremental differences           [-1,-2,1] (change)
       Ṡ            - sign                              [-1,-1,1] (comparisons)
        µ           - monadic chain separation, call that x
         I          - incremental differences           [0,2] (only (-1,1) produce 2s)
          2         - literal 2                         2
           n        - not equal?                        [1,0] (indexes of * will be 0)
            ×       - multiply by x (vectorises)        [-1,0,1] (make indexes of *s 0)
              ØD    - decimal yield                     "0123456789"
             ị      - index into (1-indexed & modular)  ['8','9','0']
                Ṛ   - reverse                           ['0','9','8']
                 ;0 - concatenate a zero                ['0','9','8',0]
                    - implicit print                     0980
                    -                              i.e. "L*SL"
\$\endgroup\$
  • \$\begingroup\$ Would you mind adding a small explaination for me ? \$\endgroup\$ – Christoph Jun 13 '17 at 7:37
  • 2
    \$\begingroup\$ I will do of course - I am thinking about possible golfs first... \$\endgroup\$ – Jonathan Allan Jun 13 '17 at 7:37
  • \$\begingroup\$ 17 bytes \$\endgroup\$ – Leaky Nun Jun 13 '17 at 9:42
  • \$\begingroup\$ @LeakyNun How did you work that out?! You are using a bug there I think + on strings seems to vectorise but the underlying results are not actually Jelly iterables but strings (!) (e.g. try +@/L€ or +@/L€€ or ...) \$\endgroup\$ – Jonathan Allan Jun 13 '17 at 10:48
  • \$\begingroup\$ @JonathanAllan yes, + produces actual string. This is an undocumented feature, or what you call bug. \$\endgroup\$ – Leaky Nun Jun 13 '17 at 10:51
3
\$\begingroup\$

Python 3, 92 87 74 69 65 bytes

s=input()
c=1
while s:d=s<s[1:];print(d+(c<d),end='');s=s[1:];c=d

Uses 0 for L, 1 for S, and 2 for *. Wrap the input string in quote characters; I believe this is allowed by convention.

Try it online!

Example use:

mmiissiissiippi
002100210021000

saved 5 bytes thanks to Leaky Nun, 4 bytes thanks to ovs

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

JavaScript (ES6), 51 45 bytes

f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d)

Saved 6 bytes thanks to @Neil.

A recursive solution to the exercise.

f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d)

console.log(f('mmiissiissiippi')); //LL*SLL*SLL*SLLL   002100210021000
console.log(f('hello world'));     //L*SSL*L*LLL       02110202000
console.log(f('Hello World'));     //SSSSL*SSLLL       11110211000
console.log(f('53Ab§%5qS'));       //L*SSL*SLL         021102100

\$\endgroup\$
  • \$\begingroup\$ Save 6 bytes: f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d) \$\endgroup\$ – Neil Jun 13 '17 at 18:38
  • \$\begingroup\$ Thanks, @Neil, I knew there had to be an optimization in there somewhere. \$\endgroup\$ – Rick Hitchcock Jun 13 '17 at 18:53
2
\$\begingroup\$

JavaScript (ES6), 52 bytes

f=
s=>s.replace(/./g,_=>(c<(c=s<(s=s.slice(1))))+c,c=1)
<input oninput=o.textContent=f(this.value)><pre id=o>

Port of @L3viathan's answer.

\$\endgroup\$
  • 1
    \$\begingroup\$ @RickHitchcock Oops, somehow I managed to port c=1 as c=0... \$\endgroup\$ – Neil Jun 13 '17 at 18:35
1
\$\begingroup\$

C (clang), 88 bytes

S(S,A,I)char*S,*A;{for(;strlen(S);A=S,S++,printf("%c",I=strcmp(A,S)>0?76:I==76?42:83));}

Try it online!

\$\endgroup\$
1
+50
\$\begingroup\$

Haskell, 77 75 bytes, linear time

f(a:b:c)|let g"L"|a<b="SL";g"S"|a>b="L*";g d=d++d;d:e=f$b:c=g[d]++e
f _="L"

Try it online!

How it works

This uses recursion, stripping off one character at a time from the beginning of the string. (The Haskell string type is a singly-linked list of characters, so each of these steps is constant-time.)

  • For a string abc where a and b are single characters and c is any (possibly empty) string,
    • f(abc) = SLe, if f(bc) = Le and a < b;
    • f(abc) = L*e, if f(bc) = Se and a > b;
    • f(abc) = LLe, if f(bc) = Le and ab;
    • f(abc) = SSe, if f(bc) = Se and ab.
  • For a single-character string a, f(a) = L.
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you please provide an explanation? \$\endgroup\$ – R. Kap Jun 19 '17 at 20:32
  • \$\begingroup\$ Please provide a description so I can validate that this runs in linear time. \$\endgroup\$ – Christoph Jun 22 '17 at 5:51
  • \$\begingroup\$ @Christoph Added. \$\endgroup\$ – Anders Kaseorg Jun 22 '17 at 6:54
  • \$\begingroup\$ @AndersKaseorg thanks for adding ! Sadly this seems quite verbose compared to the other Haskell answer. Could this be golfed further by not using S, L and *? \$\endgroup\$ – Christoph Jun 22 '17 at 7:16
  • 1
    \$\begingroup\$ @Christoph To be clear, [1,1,2,0,1,1,2,0,1,1,2,0,1,1,1] is a list of single-digit numbers, not a list of single chars. In my case, I think outputting a list of numbers would not save me any bytes. \$\endgroup\$ – Anders Kaseorg Jun 22 '17 at 9:19
1
\$\begingroup\$

Python 2, 65 55 bytes

Recursive version, based on L3viathan's answer, using 012 as LS*:

def g(s,d=2):c=s<s[1:];return s and`c+(d<c)`+g(s[1:],c)

Try it online!

Python 3, 65 59 bytes

Recursive solution using L, S, and *:

f=lambda s:s and('LS'[s<s[1:]]+f(s[1:])).replace('LS','L*')

Runs through the string from the front, and replaces all instances of LSwith L*

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ blah if s else''s and blah saves six bytes. In Python 2, str(blah)`blah` saves another three bytes on the second solution. \$\endgroup\$ – Anders Kaseorg Jun 22 '17 at 9:58
1
\$\begingroup\$

PHP, 82 byte, linear time

for($a=$argn;a&$c=$a[$i-=1];$d=$c)$a[$i]=2+$t=$d<=>$c?:$t;echo strtr($a,[13=>12]);

Walks over the input from right to left and replaces each char with the type.

$t=$d<=>$c?:$t

Calculates the type given the current and the previous char (-1 or 1). If equal the type doesn't change.

\$\endgroup\$
  • \$\begingroup\$ +1 for the idea with strtr \$\endgroup\$ – Jörg Hülsermann Jun 24 '17 at 12:58
1
\$\begingroup\$

PHP, 70 bytes

L = 1, S = 0 , * = 2

Multibyte Support is needed for the last Testcase with the § +3 Bytes mb_substr instead substr

for(;$s=&$argn;$s=$u)$r.=$l=($l&1)+(1&$l^($s>$u=substr($s,1)));echo$r;

Try it online!

PHP, 71 bytes

L = 1, S = 0 , * = 2

for(;$s=&$argn;$s=$u)$r.=+($s>$u=substr($s,1));echo strtr($r,[10=>12]);

Try it online!

PHP, 74 bytes

for(;$s=&$argn;$s=$u)$r.=SL[$s>$u=substr($s,1)];echo strtr($r,[LS=>"L*"]);

Try it online!

\$\endgroup\$
  • \$\begingroup\$ $s=&$argn quite clever ! I'm pretty sure there is a better answer though ;) Hopefully someone comes up with it :) \$\endgroup\$ – Christoph Jun 13 '17 at 16:56
  • \$\begingroup\$ @Christoph I have the feeling that I am miss something. I have try to store the last LS* in a varibale but it is longer \$\endgroup\$ – Jörg Hülsermann Jun 13 '17 at 17:01
  • \$\begingroup\$ @Christoph mean you like so? I coul not really seen why the last testcase is false Try it online! \$\endgroup\$ – Jörg Hülsermann Jun 13 '17 at 20:08
  • \$\begingroup\$ @Christoph Okay I have seen it why it not works for the last testcase I must use mb_substr instead of substr if the input is not in the simple ascii range. Is it necessary to support the last testcase? \$\endgroup\$ – Jörg Hülsermann Jun 13 '17 at 20:51
  • 1
    \$\begingroup\$ @Christoph Thank You In this case I ignore the last testcase with the § \$\endgroup\$ – Jörg Hülsermann Jun 13 '17 at 21:05

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.