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.
Programming Praxis 
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)))Or indeed SRFI 13 string-pad.
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 NothingA 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
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
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();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 '$') doneTest result:
With modern Javascript, this is basically a oneliner.
function leftpad(str, len, chr = ' ') { return chr.repeat(len >= str.length ? len-str.length : 0) + str; }(define (leftpad str len ch)
(let ((n (string-length str)))
(string-append (make-string (max 0 (- len n)) ch) str)))
@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).
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); }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