## Re: I Am Not Proud

1

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("-")

Posted by: lambchop | Link to this comment | 01- 2-16 4:33 PM
2

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.

Posted by: Spike | Link to this comment | 01- 2-16 4:44 PM
3

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.

Posted by: Josh | Link to this comment | 01- 2-16 4:47 PM
4

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.

Posted by: ogged | Link to this comment | 01- 2-16 4:48 PM
5

if you find yourself trying to solve a problem like this with math I'd say you're overthinking it

Posted by: ogged | Link to this comment | 01- 2-16 4:54 PM
6

Actually, I'll go even further: you can take out the "like this".

Posted by: Josh | Link to this comment | 01- 2-16 4:55 PM
7

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.

Posted by: Josh | Link to this comment | 01- 2-16 5:00 PM
8

In SAS, you'd have to use a substring with an array or maybe macro.

Posted by: Moby Hick | Link to this comment | 01- 2-16 5:07 PM
9

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.

Posted by: Yawnoc | Link to this comment | 01- 2-16 5:08 PM
10

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.

Posted by: Eggplant | Link to this comment | 01- 2-16 5:10 PM
11

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.

Posted by: ogged | Link to this comment | 01- 2-16 5:11 PM
12

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.

Posted by: Yawnoc | Link to this comment | 01- 2-16 5:12 PM
13

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('-');
}

Posted by: ogged | Link to this comment | 01- 2-16 5:16 PM
14

"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 = ",";
}
```

Posted by: Spike | Link to this comment | 01- 2-16 5:17 PM
15

But that said, lambchop has convinced me that it's just a matter of familiarity with the functional style.

Posted by: ogged | Link to this comment | 01- 2-16 5:22 PM
16

comma = ""
ಠ_ಠ

Posted by: Yawnoc | Link to this comment | 01- 2-16 5:22 PM
17

Bunch of stuff got stripped from 13, but you get the idea.

Posted by: ogged | Link to this comment | 01- 2-16 5:23 PM
18

That's the kind of clever I'd reject in a code review.

+1

Posted by: Josh | Link to this comment | 01- 2-16 5:24 PM
19

Like I said, elegant is not the word I would choose for that solution. But super easy to remember.

Posted by: Spike | Link to this comment | 01- 2-16 5:28 PM
20

ogged: Submit a version that actually works for non-ASCII code points and bask in smugness.

Posted by: Yawnoc | Link to this comment | 01- 2-16 5:40 PM
21

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.

Posted by: Spike | Link to this comment | 01- 2-16 5:50 PM
22

Ok, but do any of yours work on infinite lists?

`import Data.Char (toUpper, toLower)enumerate xs = zip [1..] xsbutlast [] = error "butlast on empty list"butlast xs = go xs  where    go [] = error "impossible"    go [x] = []    go (x:xs) = x : go xsaccum = butlast . foldr go [] . enumerate  where    go (count, char) acc = concat [[toUpper char], map toLower \$ take (count - 1) \$ repeat char, "-", acc]`

Posted by: nosflow | Link to this comment | 01- 2-16 5:51 PM
23

I'm not sure why I started the enumeration at 1, but whatever.

Posted by: nosflow | Link to this comment | 01- 2-16 5:53 PM
24

There aren't enough wedgies in the world...

Posted by: Yawnoc | Link to this comment | 01- 2-16 5:55 PM
25

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.

Posted by: Criminally Bulgur | Link to this comment | 01- 2-16 6:24 PM
26

.25 should have been to 15

Posted by: Criminally Bulgur | Link to this comment | 01- 2-16 6:29 PM
27

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

Posted by: nosflow | Link to this comment | 01- 2-16 6:29 PM
28

The function you use as an argument to reduce might become quite complicated, of course.

Posted by: nosflow | Link to this comment | 01- 2-16 6:29 PM
29

This makes me miss swimming posts.

Posted by: apostropher | Link to this comment | 01- 2-16 6:37 PM
30

I should go back to swimming. Easier on the tendons.

Posted by: Moby Hick | Link to this comment | 01- 2-16 6:47 PM
31

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)

Posted by: Nathan Williams | Link to this comment | 01- 2-16 6:49 PM
32

29: Preach it.

Posted by: gswift | Link to this comment | 01- 2-16 7:35 PM
33

Rust.

Posted by: nosflow | Link to this comment | 01- 2-16 7:42 PM
34

27: All you need is s and k--everything else is semantic sugar. I'll spot you i, though.

Posted by: dalriata | Link to this comment | 01- 2-16 7:43 PM
35

Pretty stingy, dalriata, considering how easy i is to define in terms of s and k.

Posted by: nosflow | Link to this comment | 01- 2-16 7:44 PM
36

Thanks for helping with one of my New Year's resolutions -- keep it up.

Posted by: RT | Link to this comment | 01- 2-16 8:06 PM
37

Learn to code, hippy.

Posted by: ogged | Link to this comment | 01- 2-16 8:15 PM
38

Hippie?

Posted by: ogged | Link to this comment | 01- 2-16 8:15 PM
39

Did your neighborhood win, Tigre, or are you celebrating the nerdification of the blog?

Posted by: Thorn | Link to this comment | 01- 2-16 8:23 PM
40

Both! No murdering, probably.

Posted by: RT | Link to this comment | 01- 2-16 8:25 PM
41

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!

Posted by: Thorn | Link to this comment | 01- 2-16 8:31 PM
42

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.

Posted by: Thorn | Link to this comment | 01- 2-16 8:48 PM
43

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.

Posted by: ogged | Link to this comment | 01- 2-16 8:52 PM
44

I sure hope not knowing any programming languages doesn't count as a moral failing.

Posted by: teofilo | Link to this comment | 01- 2-16 8:53 PM
46

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.

Posted by: Thorn | Link to this comment | 01- 2-16 9:07 PM
47

So far from being a moral or any other kind of failing.

Posted by: nosflow | Link to this comment | 01- 2-16 9:08 PM
48

Well that's a relief.

Posted by: teofilo | Link to this comment | 01- 2-16 9:10 PM
49

And I would know.

Posted by: nosflow | Link to this comment | 01- 2-16 9:12 PM
50

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;
}```

Posted by: Spike | Link to this comment | 01- 2-16 9:15 PM
51

with a dash playing the part of the comma

Every night I get tickets, the understudy is in for the lead.

Posted by: Moby Hick | Link to this comment | 01- 2-16 9:28 PM
52

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

Posted by: dalriata | Link to this comment | 01- 2-16 9:58 PM
53

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);
}
}
```

Posted by: dalriata | Link to this comment | 01- 2-16 10:27 PM
54

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;
}, []);
}
```

Posted by: Criminally Bulgur | Link to this comment | 01- 3-16 12:18 AM
55

53 tells me that apparently there is a lot of new shit in Java I need to get up to speed on.

Posted by: Spike | Link to this comment | 01- 3-16 5:24 AM
56

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.

Posted by: dalriata | Link to this comment | 01- 3-16 6:35 AM
57

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.

Posted by: Spike | Link to this comment | 01- 3-16 6:50 AM
58

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.

Posted by: AcademicLurker | Link to this comment | 01- 3-16 7:23 AM
59

"Say, you need some paper?"

Posted by: Kreskin | Link to this comment | 01- 3-16 7:56 AM
60

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?"

Posted by: Flippanter | Link to this comment | 01- 3-16 8:07 AM
61

If you fail you get sent to work at Facebook? That explains a lot.

Posted by: fake accent | Link to this comment | 01- 3-16 12:53 PM
62

Here's mine:

function accum(input) {
return input.split('').map(function(letter, i) {
return letter.toUpperCase() + Array(i).fill(letter.toLowerCase()).join('');
}).join('-');
}

Posted by: | Link to this comment | 01- 3-16 1:09 PM
63

\$ 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.

Posted by: Chet Murthy | Link to this comment | 01- 3-16 3:24 PM
64

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)
```

Posted by: dalriata | Link to this comment | 01- 3-16 4:22 PM
65

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.

Posted by: sral | Link to this comment | 01- 3-16 4:37 PM
66

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

Posted by: DaveLMA | Link to this comment | 01- 3-16 7:32 PM
67

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.

Posted by: DaveLMA | Link to this comment | 01- 3-16 7:35 PM
68

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.

Posted by: Criminally Bulgur | Link to this comment | 01- 3-16 8:40 PM
69

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.

Posted by: Yawnoc | Link to this comment | 01- 3-16 10:11 PM
70

It's not knowing what REPL and its like mean that make me fear job hunting.

Posted by: Eggplant | Link to this comment | 01- 3-16 11:16 PM
71

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

Posted by: Walt Someguy | Link to this comment | 01- 4-16 1:15 AM
72

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.

Posted by: sral | Link to this comment | 01- 4-16 1:26 AM
73

Posted by: Yawnoc | Link to this comment | 01- 4-16 7:22 AM
74

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.

Posted by: dalriata | Link to this comment | 01- 4-16 7:49 AM
75

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;
}
```

Posted by: cleek | Link to this comment | 01- 4-16 11:02 AM
76

oh yeah, need a tolower on that last bit:

std::string (z, tolower(p[z]))

Posted by: cleek | Link to this comment | 01- 4-16 11:07 AM
77

I wonder how many of these solutions fall into the accidentally quadratic trap of right-associated string appends.

Posted by: nosflow | Link to this comment | 01- 4-16 11:10 AM
78

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.

Posted by: dalriata | Link to this comment | 01- 4-16 11:42 AM
79

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.

Posted by: nosflow | Link to this comment | 01- 4-16 11:47 AM
80

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.

Posted by: dalriata | Link to this comment | 01- 4-16 11:52 AM
81

Oh, you meant functionalish in Java. Now I get it.

Posted by: nosflow | Link to this comment | 01- 4-16 12:14 PM
82

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.

Posted by: nattarGcM ttaM | Link to this comment | 01- 4-16 1:33 PM
83

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.

Posted by: Jake | Link to this comment | 01- 4-16 2:05 PM
84

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.

Posted by: sral | Link to this comment | 01- 4-16 2:09 PM
85

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!

Posted by: sral | Link to this comment | 01- 4-16 2:11 PM
86

the accidentally quadratic trap of right-associated string appends

Posted by: Yawnoc | Link to this comment | 01- 4-16 2:17 PM
87

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.

Posted by: Josh | Link to this comment | 01- 4-16 2:23 PM
88

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

Posted by: NickS | Link to this comment | 01- 4-16 2:27 PM
89

I imagine that what you were feeling at that moment was not "satisfaction at being correct."

Actually that was pretty much my exact reaction!

Posted by: Josh | Link to this comment | 01- 4-16 2:33 PM
90

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.

Posted by: NickS | Link to this comment | 01- 4-16 2:47 PM
91

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.

Posted by: sral | Link to this comment | 01- 4-16 2:48 PM
92

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

Posted by: Josh | Link to this comment | 01- 4-16 3:00 PM
93

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!

Posted by: Chet Murthy | Link to this comment | 01- 4-16 3:09 PM
94

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

Posted by: Chet Murthy | Link to this comment | 01- 4-16 3:11 PM
95

OK, looks like I can post the code.

Posted by: Chet Murthy | Link to this comment | 01- 4-16 3:11 PM
96

can't.

Posted by: Chet Murthy | Link to this comment | 01- 4-16 3:12 PM
97

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.

Posted by: cleek | Link to this comment | 01- 4-16 3:14 PM
98

The final length will always be (inlen*(inlen+1))/2 + (inlen - 1), right? You don't need the loop.

Posted by: nosflow | Link to this comment | 01- 4-16 3:22 PM
99
Posted by: nosflow | Link to this comment | 01- 4-16 3:40 PM
100

(inlen*(inlen+1))/2 + (inlen - 1)

alternately: (inlen^2 + inlen) / 2

Posted by: NickS | Link to this comment | 01- 4-16 3:41 PM
101

Wait, this is superior.

100: those are not equivalent.

Posted by: nosflow | Link to this comment | 01- 4-16 3:43 PM
102

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.

Posted by: sral | Link to this comment | 01- 4-16 3:48 PM
103

100: those are not equivalent.

True, I was just counting the letters, not the hyphens.

Posted by: NickS | Link to this comment | 01- 4-16 4:17 PM
104

the Java equivalent of looping over string concatenations.

Is that really still a problem? I thought compilers took care of that shit these days.

Posted by: Spike | Link to this comment | 01- 4-16 5:02 PM
105

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!

Posted by: dalriata | Link to this comment | 01- 4-16 5:08 PM
106

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.

Posted by: nosflow | Link to this comment | 01- 4-16 5:16 PM
107

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.

Posted by: Spike | Link to this comment | 01- 4-16 5:43 PM
108

101: ääääh I think not

Posted by: NW | Link to this comment | 01- 5-16 1:49 AM
109

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!

Posted by: cleek | Link to this comment | 01- 5-16 7:59 AM
110

108: what's the problem?

Posted by: nosflow | Link to this comment | 01- 5-16 8:43 AM
111

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();
}
```

Posted by: Criminally Bulgur | Link to this comment | 01- 5-16 9:19 AM
112

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.

Posted by: Spike | Link to this comment | 01- 5-16 5:23 PM