Smaller Strings in Printable ASCII base

Question

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 code-golf 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', ' {', ' |', ' }', ' ~']

Answer 1

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

Answer 2

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.

Answer 3

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)

Answer 4

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.

Answer 5

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.

Answer 6

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!

Answer 7

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

Answer 8

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.

Answer 9

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.

Answer 10

Charcoal, 21 bytes

ＵＴＥΦＥ⍘⁺!θＳ⍘ιγ⁼§ι⁰!✂ι¹

Try it online! Link is to verbose version of code. I don't know whether I should include the ＵＴ 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:

ＵＴ

Turn off padding.

     !              Literal `!`
    ⁺               Concatenated with
      Ｓ             Input string
   ⍘   γ            Base conversion using printable ASCII as base 95
  Ｅ                 Map over implicit range
        ⍘ιγ         Convert current value to base 95 as printable ASCII
 Φ                   Filter where
            §ι⁰      First character
           ⁼   !     Equals literal `!`
Ｅ                   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.

Answer 11

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!