Leftpad

March 25, 2016

Large portions of the internet failed a few days ago when a program called leftpad, which pads a string to a given length by adding spaces or other characters at the left of the string, was suddenly removed from its repository. The whole episode is sad, and brings nothing but shame on everyone involved (though everyone involved seems to think they acted properly throughout), and all of the web sites that broke were created by fools (you don’t rely on unknown third parties to maintain code critical to your application at some unknown place on the internet). You can read more about what happened at these links: good overview of what happened, Azer’s statement, NPM’s statement, and satire. The code that caused the problem is shown below:

module.exports = leftpad;

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

Your task is to write a proper version of leftpad; make sure yours operates in linear time instead of the quadratic time caused by the string concatenation in Azer’s code. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

12 Responses to “Leftpad”

  1. d1rge said

    Why not use just use R5RS make-string?

    (define (leftpad str len ch)
      (let ((prefix (- len (string-length str))))
        (if (positive? prefix)
            (string-append (make-string prefix ch) str)
            str)))
    
  2. John Cowan said

    Or indeed SRFI 13 string-pad.

  3. Globules said

    A Haskell version. I use a “Maybe Char” to represent the optional character argument.

    leftpad :: String -> Int -> Maybe Char -> String
    leftpad str len ch = let n = len - length str
                             c = maybe ' ' id ch
                         in replicate n c ++ str
    
    main :: IO ()
    main = do
      putStrLn $ leftpad "foo" 0 (Just 'z')
      putStrLn $ leftpad "foo" 5 (Just 'z')
      putStrLn $ leftpad "foo" 5 Nothing
    
    $ ./leftpad 
    foo
    zzfoo
      foo
    
  4. John said

    A version in Factor:

    :: left-pad ( seq n elt — newseq )
    seq n seq length [-] elt <repetition> prepend ;

    http://re-factor.blogspot.com/2016/03/left-pad.html

  5. kernelbob said

    Here’s a Bash implementation. I guess I think we need more satire.


    #!/bin/bash

    curl -s "https://api.left-pad.io/?str=$1&len=$2${3+&ch=$3}" 2>/dev/null | \
        sed -Ee 's/^{"[^"]*":"//' -e 's/"[^"]*$//'

    And here it is in action.


    tmp$ ./leftpad.bash test 10
          test
    tmp$ ./leftpad.bash test 10 \~
    ~~~~~~test

  6. matthew said

    Here’s an attempt at a better Javascript implementation that is linear (uses Array..prototype.join() to assemble the actual string) and that tries to handle Unicode properly (strings internally are UTF-16 in Javascript, so we need to take account of surrogate pairs):

    function issurrogate(codepoint) {
        return codepoint >= 0xD800 && codepoint < (0xD800 + 0x4000);
    }
    
    function length16(str) {
        var len = 0;
        // Assumes well-formed UTF-16
        for (var i = 0; i < str.length; i++) {
            len++;
            if (issurrogate(str.charCodeAt(i))) i++;
        }
        return len;
    }
    
    function leftpad (str, len, ch) {
        str = String(str);
        len -= length16(str);
        if (len <= 0) return str;
        if (ch == undefined) ch = ' ';
        else ch = String(ch);
        if (length16(ch) != 1) {
            console.log("leftpad: not single UTF-16 character: " + ch);
            return null;
        }
        var pad = []
        for (var i = 0; i < len; i++) pad.push(ch);
        pad.push(str);
        return pad.join("");
    }
    
    function test() {
        console.log(leftpad('foo',10));
        console.log(leftpad('foo',10,'$'));
        console.log(leftpad('foo',0,'$'));
        console.log(leftpad('1234',10,0));
        console.log(leftpad('foo',10,'πŸ˜ƒ'));
        console.log(leftpad('𐌰𐌳𐌴𐌡', 10,'𐎘'));
    }
    
    test();
    
  7. Jussi Piitulainen said

    Pure Bash solution. I failed to find a really nice way to generate a padding string of given length. This overgenerates in expected cases, and undergenerates (is incorrect) in unexpectedly long cases:

    leftpad () {
        old=${#1}
        new=$2
        cha=${3:-#}
        xs=$cha$cha$cha
        xs=$xs$xs$xs$xs
        xs=$xs$xs$xs$xs
        xs=$xs$xs$xs$xs
        pad=${xs:0:(new > old ? new - old : 0)}
        echo "${pad}$1"
    }
    

    It also trusts the caller that the padding character actually is a character and not a longer string.

    Testing:

    for k in {0..8}
    do
        echo $k $(leftpad foo $k '$')
    done
    

    Test result:

    0 foo
    1 foo
    2 foo
    3 foo
    4 $foo
    5 $$foo
    6 $$$foo
    7 $$$$foo
    8 $$$$$foo
    
  8. Andrei said

    With modern Javascript, this is basically a oneliner.

    function leftpad(str, len, chr = ' ') {
        return chr.repeat(len >= str.length ? len-str.length : 0) + str;
    }
    
  9. Jos Koot said

    (define (leftpad str len ch)
    (let ((n (string-length str)))
    (string-append (make-string (max 0 (- len n)) ch) str)))

  10. matthew said

    @Andrei – for sure, and ES6 makes the Unicode handling much more straightforward too (though I suppose to do that properly we should handle combining characters & normalization and it all starts to get a bit complicated).

  11. pmarfleet said

    Solution in C#. The .NET String class already provides a PadLeft method. Using that would defeat the purpose of the exercise however, so here is an alternative implementation using an Extension Method:

    public static string LeftPad(this string input, int width, char ch)
            {
                var array = new char[width];
                var offset = width - input.Length;
                int i;
    
                for (i = 0; i < offset; i++)
                {
                    array[i] = ch;
                }
    
                for (; i < width; i++)
                {
                    array[i] = input[i - offset];
                }
    
                return new string(array);
            }
    
  12. Jason Orendorff said

    JavaScript engines have an optimization that causes repeated string `+=` to take linear time rather than quadratic.

    Still, what leftpad does is not the best way to do it. There’s a neat trick that lets you build the same string with fewer `+=` operations, and Firefox’s implementation of `String.prototype.repeat` uses that trick:

    https://hg.mozilla.org/mozilla-central/file/4292da9df16b/js/src/builtin/String.js#l531

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: