21
\$\begingroup\$

Please note the special scoring for this challenge.

Given a non-empty string made of a-z, output the string immediately before it in the shortlex order.

Shortlex order

We enumerate strings in shortlex order by first listing the strings of length 0, then those of length 1, then length 2, and so on, putting them in alphabetical order for each length. This gives an infinite list of all strings. Said a bit differently, this sorts strings by length, tiebroken alphabetically.

For strings a-z as used in the challenge, this list goes (abridged):

(empty string)
a
b
c
...
z
aa
ab
...
az
ba
bb
...
zy
zz
aaa
aab
...

Scoring

Answers will be compared in shortlex order, with earlier being better.

Like in code golf, fewest bytes wins, but there's a tiebreak for same-length answers in favor of coming first alphabetically. This means that you'll want to further "golf" your answer to use characters with lower code points where this doesn't hurt its length. Characters nearer to the start are more important.

For non-ASCII languages, answers are treated as a sequence of bytes. Use the byte order of the code page to compare characters, not their UTF encoding.

For your answer's header, you can just put the code's length and say when you've outgolfed a same-length answer in the same language. You could also put the code's position in shortlex order if that number is not too long.

Input and output

The input string will be between 1 and 10 characters long, and consist only of letters a-z. As per site defaults, you may do I/O with strings as lists of characters or code points. The letters should be lowercase (code points 97-122).

Test cases

The first output is the empty string.

a -> 
c -> b
z -> y
aa -> z
az -> ay
ba -> az
aaa -> zz
zaa -> yzz
golf -> gole 
bzaaaaaaaa -> byzzzzzzzz
zzzzzzzzzz -> zzzzzzzzzy

Related: Smaller Strings in Printable ASCII base, Counting in bijective base 62

Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ A real life example of this in use is the names of the columns in a spreadsheet. LibreOffice/OpenOffice Calc have a limit of AMJ columns. I think that Microsoft Excel 2019 has a limit of ZZZ columns... \$\endgroup\$ – Ismael Miguel Jun 15 '20 at 9:20

21 Answers 21

Active Oldest Votes
7
\$\begingroup\$

Haskell, 64, 63, 56, 55 bytes

  • c is an infinite list of all strings composed of 97..122 in shortlex order.
  • \x y -> last$fst$span(/=x)y gives the predecessor of x in y
a b=last$fst$span(/=b)c
c=[]:[d++[e]|d<-c,e<-[97..122]]

Try it online!

  • 1 byte saved by using code points: [97..122] vs. ['a'..'z']
  • 9 bytes saved by ovs
  • 1 bytes saved by Laikoni

Shortlex optimality

To get the lowest-ordered version of this code:

  • Each variable is chosen to be the smallest, front-to-back
  • The two lines are sorted (' ' < '=')
Improve this answer
\$\endgroup\$
3
  • 2
    \$\begingroup\$ You need to put brackets around &s to make it a valid function. But you can write the predecessor function shorter as f x=last$takeWhile(/=x)s: Try it online!. \$\endgroup\$ – ovs Jun 13 '20 at 11:06
  • 1
    \$\begingroup\$ Note the scoring of the challenge. You can use smaller letters for instance. \$\endgroup\$ – xnor Jun 13 '20 at 16:03
  • 2
    \$\begingroup\$ f x=last$fst$span(/=x)s saves another byte. \$\endgroup\$ – Laikoni Jun 15 '20 at 7:05
6
\$\begingroup\$

Pyth, 8 bytes

ef!-TGrN

Try it online!

Throws an error for input a, but outputs nothing to STDOUT, which is technically the correct output.

Explanation

ef!-TGrN
      rN   Build a string range from the string '"' to the implicit input
 f         Filter for strings of this range satisfying:
  !         - the string becomes empty...
   -TG      - ...when all lowercase letters are removed
e          Take the last element

Note: N was used to start the range rather than d or k since it has a lower codepoint.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Ruby -pl, 29 13 bytes

*,$_=*?a...$_

Try it online!

Ironically, this task is essentially the opposite of Ruby's next (or alternatively succ) method on strings, however this potential previous method is not available out of the box. Therefore, to take advantage of existing functionality we have to loop through the range of strings (which is constructed using succ) from "a" all the way to the input (non-inclusive), and take the last position. Obviously, this will be too slow for the longer test cases.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I'm curious, how does this know to use only letters up to z? \$\endgroup\$ – xnor Jun 14 '20 at 19:53
  • \$\begingroup\$ @xnor It's implemented in such way that letters and digits cycle separately, you can see some examples in the docs \$\endgroup\$ – Kirill L. Jun 14 '20 at 19:57
6
\$\begingroup\$

Python 3.8, 67 65 bytes

Thanks @xnor for helping me get my shortlex score down!

A=lambda	B:(C:=B.pop())>97and	B+[C-1]or	A(B)+[122]if	B>[97]else[]

Try it online!

A recursive function that takes in a list of code points, and returns a list of code points.

Note that all spaces are replaced with tabs for smaller shortlex score.

Let C be the last character of the string, and B be the prefix. If C == "a", then the result is A(B) + "z". If C != "a", then the result is B + "{C-1}". The base case is when the string is "" or `"a", in which case the function returns the empty string.

Same idea, but this function takes in and returns proper strings.

Python 3.8, 73 72 bytes

A=lambda	B:B>"a"and[B[:-1]+chr(C:=ord(B[-1])-1),A(B[:-1])+"z"][97>C]or""

Try it online!

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Note the scoring of the challenge, which favors smaller variable names for instance. \$\endgroup\$ – xnor Jun 13 '20 at 16:03
  • 2
    \$\begingroup\$ Looks like underscore is actually bigger than capital letters. \$\endgroup\$ – xnor Jun 14 '20 at 18:54
  • \$\begingroup\$ @xnor You're right! I might have confused it with hyphen. \$\endgroup\$ – Surculose Sputum Jun 14 '20 at 21:39
  • 2
    \$\begingroup\$ Turns out, tabs are smaller than spaces \$\endgroup\$ – xnor Jun 15 '20 at 5:27
5
\$\begingroup\$

Retina 0.8.2, 22 bytes

(?=a+$)^a

T`l`zl`.a*$

Try it online! Link includes test cases. Explanation:

(?=a+$)^a

Remove one of the as if all of the letters are as. The lookahead is naturally placed before the anchor as it has a lower ASCII code.

T`l`zl`.a*$

Cyclically decrement any the trailing as and the previous letter.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Jelly, 14 13 bytes

LØaṗṪṖṭƊði’ị⁸

Try it online!

-1 byte thanks to Jonathan Allan reminding me of the Cartesian power builtin.

A new different approach using raw enumeration instead of math. LØaṗṖL¦ði’ị⁸ is a byte shorter, but doesn't correctly produce the empty string for some reason. It's not quite so efficient as the first solution, so I've abridged the longer test cases...

 Øaṗ             Take the Cartesian product of the lowercase alphabet with itself
L                a number of times equal to the length of the input.
    Ṫ            Take the last element of the product (e.g. "zzzz"),
     Ṗ           remove its last element ("zzzz" -> "zzz"),
      ṭƊ         and re-append it to the product.
        ð        Given that product and the original input,
         i       find the input's index in the product,
          ’      subtract 1,
           ị⁸    and index back into the product.
                 Since Jelly uses modular 1-indexing, if the input is the least
                 string of its length, its index of 1 will decrement to 0, which
                 then maps it back to the end of the enumeration, which has been
                 truncated appropriately.

Jelly, 21 bytes

O_96µJṚ’26*×µS’ḃ26ịØa

Try it online!

There's probably a shorter conversion from bijective base 26 out there, but I figured I may as well write my own before taking someone else's.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Product using the length saves one byte: TIO \$\endgroup\$ – Jonathan Allan Jun 13 '20 at 16:03
4
\$\begingroup\$

Factor, 115 bytes

: а ( s -- s ) >array [ 96 - ] map reverse
dup length [0,b] [ 26 swap ^ ] map [ * ] 2map
sum 1 - bijective-base26 ;

A naive implementation using bijective-base26 which does half the work. This solution doesn't work in TIO, because it apparently doesn't include the html-help dictionary.

Here's a screenshot from my desktop Factor Listener: Shortlex predecessor

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @xnor Thank you! I have totally forgotten about the scoring - of course the function can be renamed to a., \$\endgroup\$ – Galen Ivanov Jun 13 '20 at 18:08
4
\$\begingroup\$

JavaScript (ES6),  65 64  62 bytes

I/O: array of code points

$=>$.reduceRight((A,B,C)=>!C&($=$&&--B<97)?A:[$*26+B,...A],[])

Try it online!

Commented

$ =>                  // $[] = input array, reused for the carry
  $.reduceRight(      // for each
    (A, B, C) =>      // code point B at position C, using A[] as the accumulator:
    !C &              //   is it the leading 'digit'?
    ( $ = $ && --B    //   if the carry is set, decrement B
               < 97 ) //   and set it again if the result is 96 (just below 'a')
    ?                 //   if this is the leading 'digit' and the carry is set:
      A               //     leave A[] unchanged
    :                 //   else:
      [ $ * 26 + B,   //     prepend B if there's no carry or B + 26 otherwise
        ...A ],       //     (which gives 122, or 'z')
    []                //   initialize the accumulator to an empty array
  )                   // end of reduceRight()
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 2, 81 bytes

A="";B=1
for C in input()[::-1]:A=chr((ord(C)-97-B)%26+97)+A;B*=C<"b"
print A[B:]

Try it online!

72 bytes with lists of code points as input and output:

A=[];B=1
for C in input()[::-1]:A=[(C-97-B)%26+97]+A;B*=C<98
print A[B:]

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Note the scoring of the challenge, which favors smaller variable names for instance. \$\endgroup\$ – xnor Jun 13 '20 at 16:04
  • \$\begingroup\$ @xnor thanks for reminding me. Although this probably won't affect any ranking, my score is now only half as high. ;) \$\endgroup\$ – ovs Jun 13 '20 at 18:50
3
\$\begingroup\$

J, 39 36 35 31 26 bytes

-5 when using codepoints

*/@:=&97}.<:&.(26#.2,-&97)

Try it online!

How it works

*/@:=&97}.<:&.(26#.2,-&97)
                     -&97  a->0,b->1,..
               26#.2,      append 2 and convert from base 26
          <:&.(          ) execute right side, then decrement,
                           then inverse of right side
               26#.2,      convert to base 26 and drop the 2
                     -&97  convert back to string
*/@:=&97                   does input string only contain a's?
        }.                 drop 0 or 1 letters
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Very nice use of &.! \$\endgroup\$ – Galen Ivanov Jun 13 '20 at 14:39
  • 2
    \$\begingroup\$ Sadly the version with only one &. is shorter. :-) \$\endgroup\$ – xash Jun 13 '20 at 15:15
3
\$\begingroup\$

Haskell, 56 bytes

a.b.a
a=reverse
b"a"=""
b('a':a)='z':b a
b(a:b)=pred a:b

Try it online! The identifier names are a bit confusing (i.e. a appears as the current character, the rest of the string, and as shorthand for reverse) in order to use low code points.

Currently beats the other Haskell answer, though I already submitted an one byte improvement there which will put it into the lead again.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 35 bytes

{`c$97+1_26\-1+26/2,{(~+/x)_x}x-97}

Try it online!

Strongly inspired by @xash's J solution - don't forget to upvote it!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

PHP, 35 bytes

for($a=a;$a!=$argn;$b=$a++);echo$b;

Try it online!

who knew strings incrementing would serve one day? Too bad decrementing doesn't work..

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I was surprised when I found out it doesn't work too, I've had to implement it manually a long time ago. But the naive approach of incrementing until the desired result is a good idea. Also, you probably could do $a<$argn instead of $a!=$argn. PHP will check if the character value is lower. For example, a < b is true in PHP. This saves you 1 byte. \$\endgroup\$ – Ismael Miguel Jun 15 '20 at 9:18
  • \$\begingroup\$ @IsmaelMiguel nice suggestion, I tried but unfortunately it stops prematurely, as for the example of "golf" it displays "g" because "h">"golf" is true \$\endgroup\$ – Kaddath Jun 15 '20 at 10:29
  • \$\begingroup\$ ... That's pretty dumb ... I know what PHP is doing ... It's checking if the substring $a is lower than $argn. It's kinda like assuming that 2 is higher than 1234 because it starts with 2... I'm out of ideas to improve your code. I guess this is the optimal solution in PHP? Not even range() works here! \$\endgroup\$ – Ismael Miguel Jun 15 '20 at 10:57
  • \$\begingroup\$ @IsmaelMiguel I would have liked to avoid being obliged to use a second var $b value save but I couldn't find any shorter than this so far.. \$\endgroup\$ – Kaddath Jun 15 '20 at 15:13
  • \$\begingroup\$ I can't find any shorter either... I'm pretty sure this is optimal. \$\endgroup\$ – Ismael Miguel Jun 15 '20 at 15:18
2
\$\begingroup\$

05AB1E, 10 bytes

āAδã˜s¡нθJ

Try it online or verify all (short) test cases. (Times out for any test cases with a length above 5 due to the ã builtin.)

Explanation:

ā           # Push a list in the range [1, (implicit) input-length] (without popping)
 A          # Push the lowercase alphabet
  δ         # Apply double-vectorized:
   ã        #  Take the cartesian product
    ˜       # Flatten this list of lists
     s      # Swap so the input is at the top of the stack
      ¡     # Split this list of strings on the input
       н    # Only leave the first list
        θ   # And leave the last string of that first list
         J  # Join (for the edge case 'a', which will result in an empty list [])
            # (after which it is output implicitly as result)

NOTE: In this solution I'm alternatively able to change the н to ć/¬; θ to ¤; and/or J to » without changing the functionality. However, all of those would only negatively effect the score, since нθJ are earlier in the 05AB1E encoding.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

SimpleTemplate, 25 bytes

I loved PHP's feature where incrementing 'a' woud give 'b', and incrementing 'z' would give 'aa'.

So, since very early in the creating, I've decided to emulate that functionality, but PHP doesn't support decrementing.
That had to be implemented manually, a long time ago...

Anyway, this is the code for the task:

{@incby-1argv}{@echoargv}

The code is incredibly simple: Increment all values in argv by -1 (decrement) and output it (without a separator).

An ungolfed version of the code isn't much different:

{@inc by -1 argv}{@echo argv}

(Note: argv is the default variable that contains all arguments passed, both to the script as well as to a function. Converting to a function is trivial.)

You can try it on: http://sandbox.onlinephpfunctions.com/code/05d4f13a1d27480d119e516c446b9d001d1111d8

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

perl -M5.010 -nl, 46 bytes

$"=a;say/^$"$/?"":do{{$,=$"++;/^$"$/||redo}$,}

Try it online!

Very slow. Starting with a, it iterates over all the strings consisting of lower case letters, in shortlex order. If it matches the input, it prints the previous string. Some bytes are wasted to deal with the input of a, which should return the empty string.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 19 bytes

{{∧Ẓ∋}ᵐ|b↰}ᶠs[?,.]∧

Try it online!

I expect to be able to outgolf this.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 85 bytes

Works backwards from the end, overwriting the string as it goes along. If the previous digit borrowed (which the first character processed always does), then decrement the current digit, wrapping if required. If the final digit processed wrapped, then return the next character in the string.

A,B,C;D(char*E){for(A=1,B=strlen(E);B--;E[B]=(A=C<97)?B?122:0:C)C=E[B]-A;return E+A;}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -pl, 42 bytes

-1 byte, thanks to @Abigail!

s/(.)(a*)$/$1=~y!b-za!a-y!dr.$2=~y!a!z!r/e

Try it online!

Explanation

Mostly just using Regex here. First, match any character followed by a (greedy match of 0 or more) as. In the replacement, return $1, tr///anslating (y///) chars to those directly preceding them (/deleting any as), followed by $2, translating as to zs.

This should work for any length input.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Replace z x length$ with $2=~y!a!z!r to save a byte. Try it online \$\endgroup\$ – Abigail Jun 15 '20 at 8:12
  • \$\begingroup\$ @Abigail Ah, nice! I tested s/./z/gr thinking I needed to catch all chars, but of course, it's only as! Thank you! \$\endgroup\$ – Dom Hastings Jun 15 '20 at 8:28
1
\$\begingroup\$

Husk, 14 bytes

→←xṁOmπ…'a'zΘN

Try it online! Uses a strategy similar to the one in Kevin Cruijssen's answer.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 33 bytes

≔⪪Ｓ¹θＷ›θ⟦a⟧«≔⊟θι←§β⊖⌕βι¿›ιa«↑θ≔υθ

Try it online! Link is to verbose version of code. Vaguely based on @SurculoseSputum's answer. Explanation:

≔⪪Ｓ¹θ

Split the input into characters.

Ｗ›θ⟦a⟧«

Repeat until we only have a or nothing left.

≔⊟θι

Get the last remaining letter.

←§β⊖⌕βι

Print its cyclic decrement leftwards.

¿›ιa«

If there is no borrow, ...

↑θ

... print the remaining list in reverse, ...

≔υθ

... and clear the list to exit the loop.

Improve this answer
\$\endgroup\$

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.