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.
We first build the prefix, then perform a single append:
(define (leftpad str len ch)
(let loop ((n (- len (string-length str)))
(prefix (list)))
(if (positive? n)
(loop (- n 1) (cons ch prefix))
(string-append (list->string prefix) str))))
> (leftpad "hello" 7 #\@)
"@@hello"
You can run the program at http://ideone.com/zPY6S6.
David Thompson
MMN-o ✅⃠
All Chirp! content and data are available under the