Programming Brain Teaser
I’ve titled this post as a “Programming” brain teaser because ideally you could solve it in any language. For the sake of the exercise, I’m going to show sample code in JavaScript, but feel free to use your language of choice.
But first and foremost, the reason I’m writing about this is because I ran into a logic problem last week which I thought I would be able to solve in two seconds. Sadly it wasn’t the case so I’d like to share that same problem (in obfuscated form) with you, the readers. I know what you’re thinking. You’re at work, and you’ve got a few minutes to whip up a simple answer. Cool then, go for it. Be sure to share your answer with the rest of us by linking to it offsite, but do not share code in the comments directly as others will most likely want to solve it themselves.
The problem is simple
First, you have an array. It looks like this:
The array
var arr = ['a', 'b', 'c', 'c', 'd','e', 'e',
'e', 'e', 'e', 'f', 'e', 'f', 'e',
'f', 'a', 'a', 'a', 'f', 'f', 'f'];
Be sure to use the array above in your example. You can iterate through an array easily with a batch function like forEach.
using forEach
arr.forEach(funciton(item, index, ar) {
// do stuff here
});In the end, we’d like to have an output that looks like the following:
The final output
a b c c d e e <span>e e e</span> f e f e f a a <span>a</span> f f <span>f</span>You can use basic string concatenation while looping through the items to build your final output. Be sure to test and compare your output results with the actual results. And last but not least, the rule.
So the rule is this
In English: Group together all duplicate items that occur anytime beyond twice by wrapping them with a tag, naturally “bookending” them.
Simple, right? No, really. Tease your brain for a few minutes, you can fix that bug after lunch.
July 7th, 2008 at 11:19 pm
Is it mandatory to use “forEach†method or we can use simple “for†loop?
July 7th, 2008 at 11:41 pm
Here is my solution if I got the task right: http://dmitry.baranovskiy.com/post/41419429
July 8th, 2008 at 12:08 am
Can’t make the code look, right, look here:
http://pastebin.com/m67157328
July 8th, 2008 at 12:14 am
Hmm, seems the indentation’s gone from my code and the spans have gone from the result. Trust me, it does work!
July 8th, 2008 at 12:44 am
http://www.jaisenmathai.com/blog/2008/07/07/solving-dustin-diaz-programming-brain-teaser/
July 8th, 2008 at 12:57 am
I’ve made it work in PHP.
http://pastebin.com/m30a802e0
Don’t know if it is a good solution. But it works. I’m sure you can have it done alot easyer.
July 8th, 2008 at 1:03 am
Did it in Java, cause that’s what I’m working on right now…
http://paste.bradleygill.com/index.php?paste_id=598
July 8th, 2008 at 1:12 am
Shame on you, RStankov. Didn’t you read the part where he said, “Be sure to share your answer with the rest of us by linking to it offsite”?.
My solution:
http://www.mattryall.net/blog/2008/07/dustins-programming-problem
July 8th, 2008 at 1:27 am
Pah! [in his best Monty Python accent] I laugh in the face of your brain teaser - took 10 minutes :-P
Since you asked for the solution off site (i.e. not in these comments) - here you go:
http://remysharp.com/downloads/brain-teaser-solution.js
I’ve taken a slightly different approach to solving this - in particular, I ignored your advice on the forEach.
Enjoy.
July 8th, 2008 at 1:36 am
Here you go: http://dutchinternetworks.nl/dustins-brain-teaser.html
It took me not very long, but I think I could’ve done it with a little less code. Ah well :)
I like brain teasers like this, Dustin, post some more if you have ‘em!
July 8th, 2008 at 1:50 am
My solution:
http://www.29digital.net/brain-teaser.html
Took about 10 minutes - it’s too early in the morning for regular expressions, though. ;)
July 8th, 2008 at 1:50 am
[...] Diaz told a programmer’s riddle — impossible to leave these things alone. So I wrote a solution. One thing bugs me: the itch [...]
July 8th, 2008 at 1:53 am
[...] response to Dustin Diaz (you’ll need a JavaScript 1.8 capable browser, or [...]
July 8th, 2008 at 1:54 am
Okay, seeing as how I can’t get my code to render here (and I just noticed you want solutions off-site, my bad):
http://blog.jcoglan.com/2008/07/08/brain-teaser/
July 8th, 2008 at 1:57 am
Would have loved to write some beautiful js and avoid looping through the array. That proved more difficult than I thought at first. Follow the link to my site for my attempt at solving this.
July 8th, 2008 at 2:12 am
@Remy: that’s what I meant by avoiding the loop. Nice!
July 8th, 2008 at 3:44 am
http://www.dustindiaz.com/programming-brain-teaser/
changing the first captured group from “.” to another more complex thing teoretically made this code work with words or other token :D
July 8th, 2008 at 3:45 am
lol, i pasted the wrong link :)
corrected one:
http://mykenta.blogspot.com/2008/07/dustin-diaz-programming-brain-teaser.html
July 8th, 2008 at 3:58 am
Hi,
My solution: http://eldebaran.free.fr/miscellaneous/programming-brain-teaser.js
July 8th, 2008 at 5:53 am
Haskell yawns:
http://hpaste.org/8784
July 8th, 2008 at 5:57 am
Haskell makes this almost too easy, with its built-in group function. Someone else already wrote it, though, so I’ll link to that one: http://hpaste.org/8784
July 8th, 2008 at 6:25 am
Good challenge. took about 10 mins using Array.reduce function as documented on mozilla’s site.
http://spudly.shuoink.com/brainteaser.html
July 8th, 2008 at 6:42 am
arr.join(' ').replace(/((\S) \2 )(\2(?: \2)*)/g, '$1<span>$3</span>')July 8th, 2008 at 6:53 am
I am sure there is a better way, but here is my quickie.
http://bin.cakephp.org/view/112169537
July 8th, 2008 at 6:56 am
I took the same approach that remy did but I feel like kenta’s solution could be refined into a two function call (join/replace).
July 8th, 2008 at 7:50 am
Hi All,
Wow. Such amazing responses! For anyone that noticed their response has been removed, it’s because you’ve broken the rule of posting code on the site. Please take them offsite :)
For those that came up with regular expressions, I commend you. You rock in at least one more way than I do :)
And those that tried Array reduce… it hadn’t even occurred to me. Great job!
It’s funny that after spelling out the problem in plain English, it soon became clear what I had to do. It took me “hours” because I was looking within the context of 200 lines of code, and I didn’t quite know what I was solving mentally :/
Perhaps next time I’ll try and come up with a harder one that puts us all on the same playing field :)
July 8th, 2008 at 8:32 am
Remy Sharp, you are a genius.
July 8th, 2008 at 9:01 am
@JSnook:
My code is write in that way to make clear the separation from grouping and presentation parts
(even if i had to use a pair of placeholders ;D ),
Btw if you don’t mind that separation, look at Dmitry solution that’s do a join with a space before and thus is 5x faster than mine
(solving 10000 times this problem take 1s with my method and only 0.2s with Dimitry one)
Actually it can be devided into 3 part
grouping, adding space (presenting) and replace the placeholders :D
July 8th, 2008 at 9:02 am
[...] joined the fun to work on a programming brain teaser by Dustin Diaz (read the original post for details). The general rule is as follows: Group together all duplicate [...]
July 8th, 2008 at 9:03 am
My solution:
http://blog.enrii.com/2008/07/09/programming-brain-teaser/
July 8th, 2008 at 9:04 am
What a great thing to get started with in the morning. Not knowing if you intended the letters to always be 1-word tokens, I added a bit of defensive code to the structure.
http://www.felocity.org/tmp/ded.html
July 8th, 2008 at 10:21 am
I came up with a very very simple algorithm.
I think it’s as simple as it gets without using regular expressions.
http://antunez.no-ip.org/brain-teaser.js
July 8th, 2008 at 11:58 am
Looks like I’m late to the party, but here’s yet another to add to the pile:
http://matt.tarbit.org/2008/07/08/a-minor-morsel
July 8th, 2008 at 12:17 pm
[...] requested by Dustin, I’ve got a solution, in [...]
July 8th, 2008 at 12:26 pm
The brute force approach. Nothing very clever in this code.
http://pastebin.ca/1065805
July 8th, 2008 at 12:31 pm
Well, I haven’t tried to tackle the problem yet, but I think your requirements are not quite accurate:
Group together all duplicate items that occur anytime beyond twice by wrapping them with a tag, naturally “bookending†them.
But your example only shows the bookends when the items appear more than twice in a row:
a b c c d e e e e e f e f e f a a a f f fIf the requirements were followed, and not the example, the ‘e’s interspersed between the ‘f’s would also get wrapped in spans, as would the ‘f’s following the sequence ‘f e f’, and an extra ‘a’ would get captured in a span:
a b c c d e e e e e f e f e f a a a f f fThat looks a bit awkward, and would lead me to ask if the list of items must remain in its original order or if it’s OK that the output be sorted.
It’s easier to fix the requirements:
Group together all duplicate items that occur anytime beyond twice in a row by wrapping them with a tag, naturally “bookending†them.
July 8th, 2008 at 12:40 pm
[...] http://www.dustindiaz.com/programming-brain-teaser/ [...]
July 8th, 2008 at 12:48 pm
I’m really sorry for the first comment with code on it :( , but it was in the early morning :)
So here is my original solution:
http://next.pixeldepo.com/files/programming_brain_teaser.js
July 8th, 2008 at 2:19 pm
@Val: ‘in a row‘ is implied when saying it’s a ‘duplicate’. However this is also why I showed the final desired output so there would be no confusion.
As far as ordering. No sorting allowed.
July 8th, 2008 at 3:54 pm
Here’s another to add to the list.
http://pastebin.com/f2264724c
July 8th, 2008 at 7:06 pm
http://pastie.textmate.org/230365
This only took about 20 minutes because I recently worked on a regular expression that checked for repeating characters in a string. JavaScript made this easier than any PCRE implementation of regular expression because it allows for dynamic counting of back-references. I also learned some new stuff about JavaScript’s string.replace() method and how it allows for references to matched portions.
July 8th, 2008 at 7:14 pm
doh…had a bit of an error in the first…this is better:
http://pastie.textmate.org/230373
July 8th, 2008 at 8:43 pm
[...] last night Dustin Diaz posted a short brain teaser, there are lots of solutions already posted, but I didn’t see any with a similar approach to [...]
July 8th, 2008 at 9:42 pm
didn’t really see an approach like mine, so i thought i would also share my solution
July 9th, 2008 at 2:35 pm
Mine is in Ruby, though it would look pretty similar in JavaScript - http://zpao.com/articles/6-programming_brain_teaser
July 9th, 2008 at 4:06 pm
That last ‘f’ was tricky, but here is a regex solution:
arr.join(’ ‘).replace(/((\w)\s)(\1{1,}\2)/g, ‘$3 $2′).replace(/((\w)\s)(\1)(\2)/g, ‘$2 $3$4′);
July 9th, 2008 at 4:17 pm
Jim A,
I tried a regex very similar to yours at first, but it doesn’t capture that last ‘f’, because there is no ‘ ‘ after ‘f’. My regex doesn’t have that limitation, but you could fix yours by adding a space to the end of ’str’ after doing your join(’ ‘), and removing that space after your replace.
July 9th, 2008 at 9:25 pm
One line of actionscript (and a bunch of MXML so it compiles):
http://flex.joshmcdonald.info/2008/07/what-better-way-to-kick-off-new-blog.html
July 10th, 2008 at 5:33 am
[...] Dustin Diaz (via http://zpao.com/articles/6-programming_brain_teaser”; target=”_blank” [...]
July 10th, 2008 at 5:39 am
You didn’t manage to ruin my lunch :)
http://hackademix.net/2008/07/10/programming-brain-teaser/
July 10th, 2008 at 12:36 pm
[...] is my response to Dustin’s brain teaser. I’m offering a solution without regular expressions. Though after reading the problem I [...]
July 10th, 2008 at 1:44 pm
Remy Sharp’s solution is obvious, since I’m a regex nut. You can save a few chars and cycles like this:
http://stevenlevithan.com/downloads/brain_teaser_solution.js
(I haven’t read through the other responses in this thread.)
July 10th, 2008 at 6:56 pm
Matt Snider,
Great catch, I didn’t even notice. I also don’t like that mine still leaves the trailing space inside the resulting “bookends”. Both could be worked out though.
Thanks,
Jim
July 10th, 2008 at 8:36 pm
I thought of the algorithm so sequentially that it didn’t even occur to me to use regex! What a great idea. Here’s my shot at it.
http://rafb.net/p/hf8FjF47.html
July 11th, 2008 at 1:19 am
don’t think you can beat @Aristotle’s solution.
but if you’re grouping the duplicate items of more than 3, don’t you want them in a group?
Like this:
a b c c d e e e e e f e f e f a a a f f f
July 11th, 2008 at 1:31 am
or rather like this:
a b c c d <span>e e e e e</span> f e f e f <span>a a a</span><span> f f f</span>
July 11th, 2008 at 5:30 am
In php, in less than 10 min. very dirty…
http://pastebin.com/m544fd9bc
July 13th, 2008 at 3:44 pm
[...] Diaz posted a programming brain teaser on his blog. I decided to take a shot at it and came up with this. The solution took me just under [...]
July 13th, 2008 at 10:20 pm
Why not just concatenate the whole array into a string and use regexp to capture and replace a repeated group? problem solved.
July 15th, 2008 at 5:40 am
My solution in Java (just cos I roxors):
http://pastebin.com/m78a7b892
Its ugly and long and I much prefer some of the elegant Javascript solutions, but then I’m not paid to make Java more elegant!
I would like to note that several of the other solutions don’t take account of spaces in the output, wasn’t that part of the task? (its what took most of my time)
July 15th, 2008 at 10:20 am
Here is my solution in js: http://2wit.eu/ciprian-amariei-solution.html
It would be interesting to do some performance tests on all solutions ( for each language of course ) :D.
July 16th, 2008 at 3:09 am
A very simple and short solution (Javascript) without regexp.
http://pastebin.com/m23c326d4
July 16th, 2008 at 3:21 am
Note : my code above works if you replace letters with words. Would it be possible to use a simple regexp that accepts words in the array instead of single letters ?
July 16th, 2008 at 3:25 am
http://pastebin.com/m23c326d4
The above works if you replace letters with words. Would it be possible to use a simple regexp that accepts words in the array instead of single letters ?
(@Dustin sorry for spam, I wanted to add a 2nd comment, didn’t work, then lost my 1st comment, so reposted a 3rd time >< )
August 6th, 2008 at 9:58 am
Here is my solution in ruby (no regex):
http://pastie.org/248575
August 11th, 2008 at 6:21 pm
@Aristotle’s is better than mine, but I basically took the same approach:
http://pastebin.ca/1167177