It's maybe whatever the geek equivalent of mansplaining is to comment thus, but: Something like the second solution is going to be idiomatic in most languages that have a functional flavor. Here are Python and Ruby, respectively.
'-'.join(map(lambda (i,x): x.upper() + x.lower()*i, enumerate(s)))
s.split(//).each_with_index.map{|c,i| c.upcase + c.downcase*i}.join("-")
Ogged, if it makes you feel better, up until very recently, your version of the function would have been the appropriate one to pick for production. "map" is one of those newfangled JavaScript 1.6 capabilities, and we are only now slowly emerging into the post IE 8 era, where its safe to actually use it.
I kept searching for an elegant mathematical solution to capitalizing only the first letter of each fragment, but my math sucks and finally I said fuck it.
I'm not going to say this is an ironclad rule, but in general if you find yourself trying to solve a problem like this with math I'd say you're overthinking it. I probably wouldn't have come up with something quite as succinct as lambchop's solution, but the way I'd have solved it without thinking would be roughly the same: create a list where the number of elements is equal to the number of each letter you need, then call .toUpperCase() or .upper() or whatever on list[0]. No math involved.
It would make me feel better if I'd thought of the second one but couldn't use it. The real problem was not the functional stuff, which I actually have a decent handle on*, but that I didn't think to use Array(index+1) to populate an array with empty slots.
*The entrance interview for the bootcamp is basically to write several underscore functions from scratch and use them to solve problems.
if you find yourself trying to solve a problem like this with math I'd say you're overthinking it
This seems like solid advice.
Actually, I'll go even further: you can take out the "like this".
Also, if I can give you a little unsolicited feedback on your code: you're mushing together the solution to two distinct problems in it. Problem #1 is "give me the correct string for each letter in the input", problem #2 is "give me the complete string of all of the substrings glued together". Your code would be cleaner (and frankly in my mind preferable to the map() solution) if you broke those two problems out and solved them individually.
In SAS, you'd have to use a substring with an array or maybe macro.
You shouldn't kick yourself for not joining an array of nulls on the character to repeat. That's the kind of clever I'd reject in a code review. Sometimes things like that become idiomatic but I'd be surprised if a typical JS programmer would come up with it.
Both the math trick and the one-liners exemplify tendencies I've noticed in myself that I've worked to avoid. They're optimal in some senses (processing overhead and wordiness, respectively) but their use makes code hard to read or expand upon.
feedback on your code
Always appreciated, but it was midnight, I had a kid sleeping on my arm, and like I said, I gave up on a nice solution and just wanted to type something in that would unlock the clever stuff.
PS "Do something different for the first element in a sequence," is almost always annoyingly inelegant. "Separate a list with commas" is a common example, when you don't have a join() in the stdlib.
Of the solutions up at CodeWars, the one that seems to me most clever without being "clever" is this one.
function accum(str) {
var res = [];
for(var i = 0; i
var row = '';
for(var j = 0; j
row += j===0 ? str[i].toUpperCase() : str[i].toLowerCase();
}
res.push(row);
}
return res.join('-');
}
"Separate a list with commas" is a common example,
I've always loved my solution to this, though I don't claim its elegant.
list = ["foo","bar","baz"];
comma = "";
str = "";
for (blat in list){
str = str + comma + blat;
comma = ",";
}
But that said, lambchop has convinced me that it's just a matter of familiarity with the functional style.
Bunch of stuff got stripped from 13, but you get the idea.
That's the kind of clever I'd reject in a code review.
+1
Like I said, elegant is not the word I would choose for that solution. But super easy to remember.
ogged: Submit a version that actually works for non-ASCII code points and bask in smugness.
The past few days I've been slowly grinding my way through this Udacity course on parallel programming. Its been difficult because it turns out I don't actually know C.
So, if you were going to implement this thing with a parallel algorithm, the first thing you would do would be to calculate the length of the output string, and allocate the appropriate amount of memory on the GPU. Then you would spin up a number of threads equal to the length of the input string. Working simultaneously, each thread would grab one letter, and calculate the appropriate location at which to insert the capital and lowercase letters and dashes, and then drop them into that spot in the GPUs memory. At the end, you would copy the memory range containing the output string over to the CPU.
Ok, but do any of yours work on infinite lists?
import Data.Char (toUpper, toLower)
enumerate xs = zip [1..] xs
butlast [] = error "butlast on empty list"
butlast xs = go xs
where
go [] = error "impossible"
go [x] = []
go (x:xs) = x : go xs
accum = butlast . foldr go [] . enumerate
where
go (count, char) acc = concat [[toUpper char], map toLower $ take (count - 1) $ repeat char, "-", acc]
I'm not sure why I started the enumeration at 1, but whatever.
There aren't enough wedgies in the world...
17: you can solve most collection-processing problems with map, reduce, and filter (though the full range of functions Underscore provides can add brevity and clearer intent). For almost any string-processing problem in JS, some combination of splitting it into an array, chaining those collection-processing functions, then joining again will get you shorter, if not more readable solutuions. Learning to work with them is also good for handling JSON data from an API.
Since lists can be encoded as reduction functions, you ought to be able to solve all list-processing problems with reduce. (Map and filter can themselves be expressed in terms of reduce.)
The function you use as an argument to reduce might become quite complicated, of course.
This makes me miss swimming posts.
I should go back to swimming. Easier on the tendons.
Python, not my most idiomatic language, but the string processing in C would be butt-ugly.
def accum(str):
l=[]
for i in xrange(0,len(str)):
l.append(str[i].upper()+i*str[i].lower())
return '-'.join(l)
27: All you need is s and k--everything else is semantic sugar. I'll spot you i, though.
Pretty stingy, dalriata, considering how easy i is to define in terms of s and k.
Thanks for helping with one of my New Year's resolutions -- keep it up.
Did your neighborhood win, Tigre, or are you celebrating the nerdification of the blog?
I haven't murdered anyone either. I should probably make a sticker chart and earn rewards. It might be easier than the one I half-jokingly did for a load of laundry a day. Ugh, laundry!
I'm hoping not to stay up long enough to debate this kind of thing, but at this point it feels like a moral failing that I don't know any programming languages, or at least that I'm hopelessly out of date. I suspect that will get worse the more ogged posts, but I'm not sure if it will drive me to actually start or try to pick Turkish back up or actually finish the quilt I need to fix and bind since I already have out-of-date hobbies or what.
By the way, Criminally, I sent you an email, but I'm never sure the unfogged email is working correctly (neb is very clever, but not always slavish with his unpaid volunteer duties), so let me know if you didn't receive it.
I sure hope not knowing any programming languages doesn't count as a moral failing.
I'm not saying it's my ONLY or biggest moral failing! But I feel shame about it. That said, I was supposed to start studying trivia stuff in January and haven't so far and should get on that.
So far from being a moral or any other kind of failing.
Here is my javascript solution that uses a variation on the goofy comma trick, with a dash playing the part of the comma. Also the Elvis operator.
function accum(str){
out = "";
sub = "";
for (i = 0; i < str.length; i++){
for (k = 0; k <= i; k++){
sub += (k == 0) ? str[i].toUpperCase():str[i].toLowerCase();
}
out += sub;
sub = "-";
}
return out;
}
with a dash playing the part of the comma
Every night I get tickets, the understudy is in for the lead.
Not knowing how to program is most certainly not a moral failing. If anything, given how much evil is done via programming, one should be suspicious of known programmers until there's evidence to the contrary.
35: Very stingy. Sometimes when I'm bored I'll rewrite Haskell functions to be pointless via s and k and a few intermediate functions defined off of them. It's aesthetically pleasing, in a perverse way.
I wrote a standard imperative implementation, but I found it to be a pain to write a functionalish one using Java's new Streams library--we only upgraded to 8 recently so I haven't properly familiarized myself with them. Still giving it a go, tho'.
Java: even if you try to do it the efficient way, it gets boilerplatey. I'm praying to the gods of code-formatting on this...
import java.util.*; import java.util.stream.*;
public class Accum {
public static String accum(String in) {
return IntStream.range(0, in.length()).boxed()
.map(i-> {
String c = in.substring(i,i+1);
return Collections.nCopies(i,c.toLowerCase())
.stream()
.reduce(c.toUpperCase(), (a,b)->a+b);
})
.collect(Collectors.joining("-"));
}
public static void main(String[] args) {
Stream.of("abcd", "RqaEzty", "cwAt")
.map(Accum::accum)
.forEach(System.out::println);
}
}
By the way, Criminally, I sent you an email,
Yes, got it. Will respond tomorrow.
Since lists can be encoded as reduction functions
With an empty list as primitive?
(Map and filter can themselves be expressed in terms of reduce.)
Using Array.prototype.concat, it's pretty clean in JS:
Array.prototype.map = function(mappingRelation){
return this.reduce(function(accumulator, value){
return accumulator.concat(mappingRelation(value));
}, []);
}
Array.prototype.filter = function(predicate){
return this.reduce(function(accumulator, value){
return predicate(value) ? accumulator.concat(value) : accumulator;
}, []);
}
53 tells me that apparently there is a lot of new shit in Java I need to get up to speed on.
55: Java 8 added lambdas! It's like a real language now! So many anonymous inner classes, for e.g. event handlers, are now pretty one-liners. Also the Streams library, which I have yet to decide how clunky I find it. Oh, and default implementations, which is why I was able to do List.stream(). Things are different now.
So many anonymous inner classes, for e.g. event handlers, are now pretty one-liners.
Sounds nice. Anonymous inner classes are certainly one of the uglier things about Java code.
I sure hope not knowing any programming languages doesn't count as a moral failing.
After death, when you arrive at the pearly gates St. Peter will give you 10 minutes to complete the FizzBuzz test. If you fail, you get sent to the Other Place.
The joy of the blessed shall only be the greater for the pleasure of watching the damned struggle on the phone with tech support. "Any key? Where's the 'any' key?"
If you fail you get sent to work at Facebook? That explains a lot.
Here's mine:
function accum(input) {
return input.split('').map(function(letter, i) {
return letter.toUpperCase() + Array(i).fill(letter.toLowerCase()).join('');
}).join('-');
}
$ perl -e '$n = 0 ; $ARGV[0] =~ s/./uc($&) . lc($&) x ($n++). "-"/ge; chop $ARGV[0]; print $ARGV[0]."\n";' cwAt
C-Ww-Aaa-Tttt
$ perl -e '$n = 0 ; $ARGV[0] =~ s/./uc($&) . lc($&) x ($n++). "-"/ge; chop $ARGV[0]; print $ARGV[0]."\n";' RqaEzty
R-Qq-Aaa-Eeee-Zzzzz-Tttttt-Yyyyyyy
Amateurs.
OK, that's just a joke. Really, my point is similar to 9 (Yawnoc)'s -- sure, you should learn the functional style. Sure, you might want to learn to separate the two tasks of "iterate over the chars of a string" and "do something interesting to this char, based upon its position in the string". But .... "concatenate N copies by using an array of nulls"?? Nopes. Nopes. And Nopes. That's -insanely- language-specific.
Writing lovely readable, maintainable Perl code, does not follow from being able to cook up stuff like I did above. Truly it does not.
I could enumerate the multiple ickinesses of the code above, but .... well, "brevity is not always coincident with clarity". Hell, brevity in the small is not always coincident with brevity in the large, for that matter.
I don't think anyone has tried it as a dumb, directly recursive implementation yet:
module Accum where
import Data.Char
accum s = accumInternal s 0
accumInternal [] _ = [] accumInternal (c:[]) 0 = [toUpper c] accumInternal (c:[]) n = accumInternal (c:[]) (n-1) ++ [toLower c] accumInternal (c:cs) n = accumInternal (c:[]) n ++ ['-'] ++ accumInternal cs (n+1)
Here's a straightfoward go version, because last time I did interviews I mostly coded in C++, and whiteboard coding C++ is obnoxious, and I should really get some practice in a higher level language since everything I do for work is lower level.
func accum(ins string) (res string) {
separator := ""
for i, c := range ins {
res += separator +
strings.ToUpper(string(c)) +
strings.Repeat(strings.ToLower(string(c)), i)
separator = "-"
}
return
}
Redefining separator is silly and I should probably be more explicit or use join. Obvs, I agree with everyone else about avoiding cleverness.
56. I miss the relatively simple Java syntax of yore. Well, really I miss the syntax of Lisp, which could parse itself in relatively few lines of cleverness.
This is why my brain always goes "ick" when I try to play with Haskell et al.
I admit I am growing fonder of Java Streams, if only my fingers would agree...
65. The thing to remember about whiteboard coding (for interviews anyway) is that the interviewers just want to know you get the algorithm. If they are not idiots they will not care about the syntax and formatting details. If they are idiots you don't want to work there.
I am not looking forward to whiteboarding this month while job hunting. I am pretty reliant on having an open repl as a scratch pad.
The kinds of things I test out in a REPL are also the kinds of things I wouldn't ding you for in a whiteboard interview. I let candidates make up standard library functions, as long as they can tell me what the expected input/output behavior is.
It's not knowing what REPL and its like mean that make me fear job hunting.
REPL is a weird term, in that it was a Lisp term that just recently went mainstream. (It just means command-line interpreter for a language. A basic Lisp command-line interpreter -- in Lisp itself -- would be (loop (print (eval (read)))). If you read it inside out, you get the acronym.)
67: Yeah, I just feel weird about not writing things out, especially at companies where the interviewers record what you write down and send it to a hiring committee. So I end up writing out junk like like std::unordered_map>>.
I know I can abbreviate that with "using", or doing what all the algorithms competitors do (short #defines for everything), but, again, I just feel weird about doing that in an interview.
The trick about interview coding is to be as explicit as necessary, but no more. If they're requiring you to be too explicit--or requiring you to know too much about libraries that you'd just in practice look up--as someone said above, you don't want to work there.
here's my C++ version:
std::string accum(char *p)
{
std::string a;
for (int z=0;z<strlen(p);z++)
a = a + (z ? "-" : "") + (char)toupper(p[z]) + std::string (z, p[z]);
return a;
}
oh yeah, need a tolower on that last bit:
std::string (z, tolower(p[z]))
I wonder how many of these solutions fall into the accidentally quadratic trap of right-associated string appends.
My Haskell one does, and my Java one does the Java equivalent of looping over string concatenations. An efficient imperative Java implementation would use a StringBuilder, which doesn't allocate memory for the combined string until you're done. A functionalish implementation could also use that, although it'd be more verbose.
Er, left-associated, rather.
A functionalish implementation could also use that, although it'd be more verbose.
I don't think it would be more verbose.
I mean more verbose than the one I attempted above, since there aren't specialized Collectors, etc. for StringBuilder. Unless Collector.joining already uses StringBuilder, which fair point. Probably not what you meant, but that would be a nebbish way of pointing that out.
Oh, you meant functionalish in Java. Now I get it.
31 is pretty close to what I'd have done, I think.
I mostly use Python but I don't really write it idiomatically, or as tersely like the Python solution in 1.
Yeah, 31 is pretty much it. Using "str" as the argument shadows the builtin and enumerate is arguably simpler, but whatever.
def accum(s):
l = []
for i, c in enumerate(s):
l.append(c.upper() + c.lower() * i)
return '-'.join(l)
72,74: as someone on the interviewer side of a bunch of interviews, the trick is to be explicit about how explicit you're being. deliberately skipping over boilerplate that the compiler will catch in the interest of time is one thing; copying/pasting a code block and only changing three of the four instances of "s1" to "s2" is a problem.
73: I don't think you can auto function params, can you?
N: I had an interview at Jane Street where I got dinged for saying that I'm not sure how thing X works and I'd play with it if it wasn't an interview. It's normally hard to tell why you get rejected, but the incredibly condescending response about how at Jane Street, they only hire people who can think through problems and really understand their code because it's important for them avoid bugs before they happen in production made it pretty clear.
That's sort of a funny thing to say to me in particular because I've spent my entire career on systems with much higher reliability requirements than most software folks are used to. In seven years at my first company, we shipped one user-visible bug that anyone noticed. And at my current job, my team's on-call rotation has never been paged because it's never even looked like we might have a bug (in infrastructure at a large cloud company that gets deployed to every machine we own). I considered explaining this to the interviewer but I at that point I didn't think I wanted to work there and just mumbled something polite and went on with the rest of the interview even though it was pretty clear that I'd already failed.
Next time, I might just politely thank them for their time and stop, although I'm not sure there's really any polite way to bail on an interview.
Oh, I see that I didn't escape things properly in 72 and destroyed 80% of my declaration. No wonder I failed that last interview I mentioned!
the accidentally quadratic trap of right-associated string appends
You mean Schliemel the Painter's algorithm?
I had an interview at Jane Street where I got dinged for saying that I'm not sure how thing X works and I'd play with it if it wasn't an interview.
I recently had an interview where I was given a problem (with the constraints that a couple of operations had to happen in constant time) and told I could use any language I wanted. Then the interviewer said that the (built-in) data structure I chose wouldn't support constant time. After a *very* painful hour of whiteboarding a different solution and a couple of other sessions with other folks, the original interviewer came back and said that, well, he'd looked at the documentation and my original solution was actually completely correct.
I still didn't get the job though.
It's not knowing what REPL and its like mean that make me fear job hunting.
That was my reaction as well. I know that the work I'm doing is in a weird little niche, but this thread is a reminder of that fact.
[T]he original interviewer came back and said that, well, he'd looked at the documentation and my original solution was actually completely correct.
I imagine that what you were feeling at that moment was not "satisfaction at being correct."
I imagine that what you were feeling at that moment was not "satisfaction at being correct."
Actually that was pretty much my exact reaction!
Oh, well that's good. I was thinking that frustration might have been the stronger reaction, but I'm glad that wasn't the case.
I'm definitely in a weird little niche. But I'm not sure who isn't. Maybe full-stack web devs? I don't even know what passes for non-niche.
Maybe full-stack web devs?
No, they get dinged for not being specialized enough. (I can fairly bill myself as a full-stack web dev. I tell people that means that I'm equally incompetent at all levels of the stack.)
Re: 79
Yaknow, Perl's ".=" does the right thing and gives linear perf, e.g.
time perl -e 'for($i=0;$i
is pretty much linear in the number you provide, but
time perl -e 'for($i=0;$i
.... well that takes pretty much forever (b/c of course, the runtime can't tell that you're going to discard $y, and hence, $x really is a single reference.
Refcounting FTW!
Aarg, looks like some sort of escaping blew out my Perl code! wah! This time, without the dollar-signs on the variables in the obvious spots.
time perl -e 'for(i=0;i
vs.
time perl -e 'for(i=0;i
OK, looks like I can post the code.
hmmm...
C++ but with only two passes over the input, one string allocation, and no string concats:
std::string accum(char *pIn)
{
size_t len = 0, inlen = strlen(pIn);
for (size_t i=0; i < inlen; i++)
{
len = len + (i + 1);
if (i) len += 1;
}
std::string a;
a.resize(len);
char *p = pIn;
size_t z = 0;
while (*p)
{
if (z)
a[z++] = '-';
for (size_t i = 0; i <= (size_t)(p-pIn); i++)
a[z++] = i ? tolower(*p) : toupper(*p);
p++;
}
return a;
}
getting vewy vewy close to C, now.
The final length will always be (inlen*(inlen+1))/2 + (inlen - 1), right? You don't need the loop.
As in this very similar Rust version.
(inlen*(inlen+1))/2 + (inlen - 1)
alternately: (inlen^2 + inlen) / 2
97 could be made less C-like by using reserve instead of resize and then using the standard C++ string functions. It should also be marginally faster because reserve doesn't initialize the memory.
100: those are not equivalent.
True, I was just counting the letters, not the hyphens.
the Java equivalent of looping over string concatenations.
Is that really still a problem? I thought compilers took care of that shit these days.
It was, last time I checked, still reported as questionable in FindBugs, the static analysis utility. That was within the last two years.
But I think you're right--I just wrote a trivial class that did such string concatenation and there's a reference to StringBuilder in the .class output. Yay!
Somehow that seems more magical and spooky (and likely brittle) than things like stream or foldr/build fusion, though I guess it's no more so than something like GHC's rewrite rules.
Yeah, I saw some benchmark that had essentially the same times for a long loop of String concatenation vs. a long loop using StringBuffer.
I tend to avoid it String concatenation in loops, though, on the grounds that the code may one day end up running through a lame compiler which doesn't have that feature. Still, knowing that helps me feel better about not using StringBuffer when I'm just contacting a few strings.
98.
yeah. i remembered that you can reduce a summation series after i posted 97. hadn't found a reason to do one of those in 25 years!
Since this is the string-processing thread. . .
I should walk back what I said to Ogged in 25: there are plenty of instances in which split/join and chaining reduce/map/filter is not terser than an imperative approach (at least in JavaScript, using built-in reduce/map/filter). Mainly, because for certain operations, it produces multiple passes through a collection and code to handle each pass, whereas a straightforward imperative approach iterating through the string would not. I am sure more sophisticated functionalish programming handles that problem, but that's not in my locker.
Brought to mind while writing a string permutation function this morning as interview-whiteboarding practice,
function permutations(str){
if(str.length === 1) return [str];
return str
.split('')
.reduce(function(perms, chValOuter, chIndOuter, chArr){
return perms.concat(
permutations(
chArr
.filter(function(chValInner, chIndInner){
return chIndOuter !== chIndInner;
})
.join('')
)
.map(function(innerPerm){
return chValOuter + innerPerm;
})
);
}, [])
.sort();
}
function permutations(str){
if(str.length === 1) return [str];
var outerPerms = [];
for(var i = 0; i < str.length; i++){
var innerPerms = permutations(str.slice(0, i) + str.slice(i + 1));
for(var j = 0; j < innerPerms.length; j++){
outerPerms.push(str[i] + innerPerms[j]);
}
}
return outerPerms.sort();
}
Well, the algorithm looks fine, but in an interview I would definitely hold against you the lack of curly braces in the single line "if" statements. Skipping curly braces opens up a whole class of bug that is completely unnecessary.