15
\$\begingroup\$

Task

Given a input string s which contains only printable ascii characters output all strings which contain only printable ascii characters and are strictly smaller than s in any order

String a is strictly smaller than a string b if either of the following is true:

  • len(a) < len(b)
  • len(a) == len(b) and string a is lexicographically smaller than string b

Note: here printable ascii characters refer to the characters which have a ascii value strictly greater than 0x1f and strictly less than 0x7f

Reference Python Implementation

Scoring

This is so shortest bytes wins

Testcases

'' -> []
'%' -> ['$', '', '#', '"', ' ', '!']
' #' -> ['', ' ', '!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.', '/', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ':', ';', '<', '=', '>', '?', '@', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '[', '\\', ']', '^', '_', '`', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}', '~', '  ', ' !', ' "']
'! ' -> ['', ' ', '!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.', '/', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ':', ';', '<', '=', '>', '?', '@', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '[', '\\', ']', '^', '_', '`', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}', '~', '  ', ' !', ' "', ' #', ' $', ' %', ' &', " '", ' (', ' )', ' *', ' +', ' ,', ' -', ' .', ' /', ' 0', ' 1', ' 2', ' 3', ' 4', ' 5', ' 6', ' 7', ' 8', ' 9', ' :', ' ;', ' <', ' =', ' >', ' ?', ' @', ' A', ' B', ' C', ' D', ' E', ' F', ' G', ' H', ' I', ' J', ' K', ' L', ' M', ' N', ' O', ' P', ' Q', ' R', ' S', ' T', ' U', ' V', ' W', ' X', ' Y', ' Z', ' [', ' \\', ' ]', ' ^', ' _', ' `', ' a', ' b', ' c', ' d', ' e', ' f', ' g', ' h', ' i', ' j', ' k', ' l', ' m', ' n', ' o', ' p', ' q', ' r', ' s', ' t', ' u', ' v', ' w', ' x', ' y', ' z', ' {', ' |', ' }', ' ~']
\$\endgroup\$
  • \$\begingroup\$ Does the output have to be sorted? \$\endgroup\$ – RGS Mar 13 at 10:33
  • \$\begingroup\$ @RGS no the output does not need to be sorted \$\endgroup\$ – Mukundan314 Mar 13 at 10:44

11 Answers 11

4
\$\begingroup\$

05AB1E, 11 bytes

-1 byte thanks to @KevinCruijssen

gžQ×æêéI¡н

Try it online!

TIO link is for "abcd" instead of printable ascii since powerset of len(input) printable ascii takes a while to compute...


Explanation

gžQ×                 - repeat printable ascii length of the input times
    æ                - get the powerset of this string 
     êé              - sort and uniquify lexicographically then sort by length
       I¡            - split on the input
         н           - and take the elements that are before it
                     - output these implicitly
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ DIk£ can be I¡н to save a byte. And a version that's better for performance and works with the full printable ASCII range would be this 11-byter, although it is missing it's leading empty string unfortunately which would cost 2 bytes to fix.. :/ \$\endgroup\$ – Kevin Cruijssen Mar 13 at 13:12
3
\$\begingroup\$

Haskell, 64 62 bytes

f s|h:t<-mapM(\_->[' '..'~'])<$>scanr(:)""s=id=<<filter(<s)h:t

Try it online!


Previous 64 byte version with explanation:

f s=[x|x<-mapM(\_->[' '..'~'])=<<scanr(:)""s,(0<$x)<(0<$s)||x<s]

Try it online!

Given an input string s, e.g. s="abc", scanr(:)""s yields all suffixes of s: ["abc","bc","c",""]. mapM(\_->[' '..'~']) takes a string and computes all possible combinations of the printable ASCII characters of the same length as this string. We apply this function to all the suffixes and thus get all possible strings of length 3, 2, 1 and zero. x iterates over all those strings and we keep only those that are smaller in length ((0<$x)<(0<$s) using this Tip) or lexicographically smaller (x<s) than the input s.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Jelly,  11  10 bytes

-1 thanks to Nick Kennedy!

LŻØṖṗẎṣ⁸Ṗj

A monadic Link accepting a list of characters which returns a list of lists of characters.

Try it online! (footer prints each on it's own line, since a full program would implicitly smash and print)

How?

LŻØṖṗẎṣ⁸Ṗj - Link: list of characters (i.e. a string), S
L          - length (S)
 Ż         - zero-range -> [0,1,2,...,length(S)]
  ØṖ       - list of printable ASCII characters
    ṗ      - Cartesian power (vectorises) - i.e. all length n strings for n in [0..len(S)]
     Ẏ     - tighten (join all these lists of strings to one list of strings)
       ⁸   - chain's left argument, S
      ṣ    - split (the list of strings) at occurrences of (S)
        Ṗ  - throw away the rightmost list of strings (those lexicographically greater than S)
         j - join (the resulting list of lists of strings) with (S) (to get a list of strings)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don’t think you need the . \$\endgroup\$ – Nick Kennedy Mar 13 at 23:26
  • 1
    \$\begingroup\$ Ah yes, will vectorise here, thanks! \$\endgroup\$ – Jonathan Allan Mar 13 at 23:29
2
\$\begingroup\$

Python 3, 146 139 138 136 bytes

lambda s:[v for n in range(len(s)+1)for v in g(n)if n<len(s)or v<s]
g=lambda n:n and[s+chr(c+32)for c in range(95)for s in g(n-1)]or[""]

Try it online!

How:

The function g recursively generates all strings of length n. Our main function f only has to generate all the shorter strings and then, for the strings with the same length as the input, only keep the ones that have smaller dictionary order.

Thanks to @SurculoseSputum for fixing a mistake and saving 2 bytes at the same time, plus saving 2 bytes on a different golfing effort.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ -2 bytes by fixing your off-by-1 error. \$\endgroup\$ – Surculose Sputum Mar 13 at 14:26
  • \$\begingroup\$ @SurculoseSputum what was I thinking..? :o \$\endgroup\$ – RGS Mar 13 at 14:39
2
\$\begingroup\$

Python 3, 142 141 135 129 bytes

lambda s:["%c"*n%p for n in range(len(s)+1)for p in product(*tee(range(32,127),n))if n<len(s)or"%c"*n%p<s]
from itertools import*

Try it online!

Takes input as a string s, and outputs a list of strings.

Explanation

The function generates all printable strings of length at most len(s), then keeps the ones that are smaller than s.

lambda s:[
  "%c"*n%p                    # forms string from p - a tuple of n ints (representing ASCII code points)
  for n in range(len(s)+1)    # for each length n from 0 to len(s), inclusive 
  for p in product(*tee(range(32,127),n))
                              # for each possible tuple of n ASCII codepoints
  if n<len(s)or"%c"*n%p<s     # keep only the strings that are smaller than s
]

To generate all printable strings of length r:

  • tee(range(32,127),n) creates n iterators from 32 to 126 inclusive
  • product(*tee(...)) finds the Cartesian product of those n iterators
  • p in product(...): p will be a tuple of n integers, each between 32 and 126 inclusive
  • "%c"*r%p creates a string of n characters from p.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 110 bytes

Prints the strings.

s=>(g=o=>o[k=s.length]||o[g([...o,32]),(n=o.length)<k|(S=Buffer(o)+'')<s&&console_log(S),n-1]++<126&&g(o))([])

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

[Ruby], 111 108 bytes

->s,w=[*32..126]{!s[0]? []:w.product(*([w]*(s.size-1))).map{|a|a.map{|n|n<32 ?"": n.chr}*''}.select{|t|t<s}}

Try it online!

This perplexed me for far too long until I realised that I had the test cases mixed up (D'oh!).

It also creates a Cartesian product of the ASCII characters, and filters those "less than" the input string.

Explanation

w.product(*([w]*(s.size-1))) to get the Cartesian product of the ASCII characters, where w=[*32..126]. Found here

a.map{|n|n<32 ?"": n.chr}*'' to then take those arrays of code points and convert them to characters and join them into strings

.select{|t|t<s}} to filter down to those strings less than the input string.

Edit: Swap out s.empty? for !s[0]. Everything except nil and false are truthy in Ruby, and indexing an array out of bounds returns nil. So if there is a first element, then the array is not empty.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pyth, 10 bytes

f!-Trd\rk

Try it online!

Contains an unprintable after the \ so here's a hex dump:

00000000: 66 21 2d 54 72 64 5c 7f 72 6b        f!-Trd\.rk

Explanation

  • rk(Q) Generate a string range from the empty string to the input string. This is a list of all strings strictly smaller than the input, but it also contains characters outside the printable ASCII range.

  • rd\. Generate a string range from the space character (ascii 32) to the DEL character (ascii 127). This is the range of printable ASCII.

  • f!-T ... Filter for elements of the first range that contain only elements of the second range.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

PHP, 138 bytes

$c=unpack('C*',$argn);for(;$i=count($c);){for(;$i;)if(--$c[$i]<32)$c[$i--]=126;else break;if(!$i)array_pop($c);echo pack('C*',...$c),',';}

Try it online!

The idea is to create an array of ASCII code points and iterate over those.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 21 bytes

UTEΦE⍘⁺!θS⍘ιγ⁼§ι⁰!✂ι¹

Try it online! Link is to verbose version of code. I don't know whether I should include the UT in the byte count but Charcoal's default of padding all lines to the same length does make distinguishing between strings that might end in spaces very tricky. Explanation:

UT

Turn off padding.

     !              Literal `!`
    ⁺               Concatenated with
      S             Input string
   ⍘   γ            Base conversion using printable ASCII as base 95
  E                 Map over implicit range
        ⍘ιγ         Convert current value to base 95 as printable ASCII
 Φ                   Filter where
            §ι⁰      First character
           ⁼   !     Equals literal `!`
E                   Map over results
                ✂ι¹ Slice off first character
                    Implicitly print

If Charcoal had a bijective base conversion function, this could be written Print(Map(BijectiveBaseString(InputString(), g), BijectiveBaseString(i, g))); probably for 9 bytes, but unfortunately it doesn't, so the easiest way to fake it is to prefix all values with the same ASCII character and filter out entries that don't begin with that character.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 90 bytes

s=>(g=(x='',j=32,b=Buffer)=>(s[x.length]?b(95).map(_=>g(x+b([j++]))):x<s)&&console_log(x))

Try it online!

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