Word Aligned - Latest Comments

Re: The Maximum Sum contiguous subsequence problem

tag — Sun, 14 Mar 2010 04:05:17 -0000

Warning: it's a tough problem! In the second edition of Programming Pearls, Jon Bentley writes: "the two-dimensional problem remains open ... Readers who feel that the linear-time algorithm for the one-dimensional problem is 'obvious' are therefore urged to find an 'obvious' algorithm for problem 13!" (Problem 13 is a statement of the 2D problem).
I do not know if any efficient algorithm for the 2D problem has been discovered since. To answer your question: I haven't found one.

Re: The Maximum Sum contiguous subsequence problem

RyanBalfanz — Sat, 13 Mar 2010 20:51:18 -0000

If/when I get some time, I'll have to do that. Have you done it yourself?

Re: The Maximum Sum contiguous subsequence problem

tag — Sat, 13 Mar 2010 04:07:04 -0000

Thanks, Ryan. If you're feeling inspired, why not try the 2 dimensional version? Find the maximum sum of a rectangular subarray of a 2D array of numbers.

Re: The Maximum Sum contiguous subsequence problem

RyanBalfanz — Fri, 12 Mar 2010 22:07:17 -0000

I recently was asked to solve this problem, which oddly I'd never encountered before (or forgotten). Thanks for such a great description of the problem and explanation of how to solve it. The programmatic solutions are great, but the visual representation really take the explanation to the next level!

Re: One svnserve, multiple repositories

Rafael Cotta — Sat, 20 Feb 2010 15:41:13 -0000

For those running under xinetd, remember to remove the "-d" and add the "-i" flag (one stands for "daemon mode" and the other for "inetd mode"). This seems to be obvious, but for those that don't really know what's going on (my case), it will save much time.

I also wanted to password protect my repository. For that I had to change passwd and svnserve.conf under the repository's "conf" directory (you must change the settings for each repository you'll create).

Thanks a lot for this post!

Re: Joined Output and the Fencepost Problem

tag — Thu, 18 Feb 2010 16:09:35 -0000

Thanks for the bug-fix mmocny.

Re: Joined Output and the Fencepost Problem

mmocny — Thu, 18 Feb 2010 11:32:45 -0000

There is a bug in your first example using a BidirectionalIterator, when you do --last a second time. This bug does not exist in the final version of your code.
Also, I would have replaced the assert( first != last ); with if (first == last) return;

Thanks for the article, I have certainly run into this problem before. Most often it is with text output, like here, but it can crop up in any loop where the last iteration produces *less* side effects than the other iterations. Most often the last iteration produces *more* side effects and that code just follows after the loop ends.

Re: When you comment on a comment

tag — Thu, 18 Feb 2010 03:59:02 -0000

Thanks for your comment lorg.

> Well, I don't use disqus, so currently I don't have anything much to say about them one way or the other. Yet the "commenter's rights" quote reads a lot like a feature list. Why *should* commenters have these rights?

Usually they don't! But Disqus are trying to change that. "Commenter's rights" is putting it strongly, but I guess it all comes down to opinion.

> Personally, as a blog owner, I think that having comments on the actual article as opposed to comments on reddit/other social websites has great value. These comments *keep*. They are also visible to anyone reading the article, regardless of where he came from.

Yes, an important comment should be easy to find from the original. Often, though, it seems that people read the comments first. Disqus *does* let you include reactions from reddit etc to on your blog. I've got it turned off at the moment. Bloggers can also link back to reddit if they think the discussion there is interesting.

> I think that most important right a commenter should have is that the comment will not be edited without his permission (barring special circumstances such as ungarbling code, closing tags, etc...). However, this is a case of blogging ethics, and not a technological issue.

Yes, I agree.

Re: When you comment on a comment

lorg — Mon, 15 Feb 2010 04:44:37 -0000

Heya
Well, I don't use disqus, so currently I don't have anything much to say about them one way or the other. Yet the "commenter's rights" quote reads a lot like a feature list. Why *should* commenters have these rights?

When thinking about it. I think it's a lot like a power-play. Who wants the comment more, the website, or the commenter? If the website wants it more, and they think having these features will help get it, they'll implement it. If the commenter wants it more, he will comment even in a website that doesn't give that right.

Personally, as a blog owner, I think that having comments on the actual article as opposed to comments on reddit/other social websites has great value. These comments *keep*. They are also visible to anyone reading the article, regardless of where he came from.

Furthermore, I'm not sure I agree with these rights in principle. I don't think that I'm obliged to keep a copy of the comments in case I shut down my blog. I also don't give any guarantee that the comments there will be kept.

I think that most important right a commenter should have is that the comment will not be edited without his permission (barring special circumstances such as ungarbling code, closing tags, etc...). However, this is a case of blogging ethics, and not a technological issue.

Re: When you comment on a comment

tag — Fri, 12 Feb 2010 04:26:08 -0000

Hi Paul. Yes, I had noticed a few evals creeping in recently: I don't think you've messed up, I think they're a good example of when they're useful.

Re: When you comment on a comment

Stephan202 — Fri, 12 Feb 2010 02:49:11 -0000

I do read all comments on this site (even have a separate RSS feed for them). Kudos to you for the fitting description "trolling teenager" :D.

Re: When you comment on a comment

Paul Thomas — Thu, 11 Feb 2010 17:49:48 -0000

It's not that I particularly like comments but if you hadn't mentioned the recent comment activity on your site, I wouldn't have gone looking, found the trolling teenager, then read the article with the eval etc. (It looked like a lisp thing at first glance - I tend to ignore them). So I wouldn't have thought to warn you that there are a couple of cheeky evals in a certain code base you and I are hoping to put into production soon. Maybe you should review them some time, make sure I haven't messed up!

Yay for comments.

Re: When you comment on a comment

bretthoerner — Wed, 10 Feb 2010 17:48:21 -0000

I know of at least a couple DISQUS developers that follow your blog, so the feeling is mutual. :)

Re: Longest common subsequence

tag — Wed, 10 Feb 2010 13:53:28 -0000

Ravi, thanks for your kind words. No, I'm not aware if your "hierarchical search algorithms" idea is used anywhere: this article includes most of what I know about this particular problem. Of course, the algorithm doesn't need to be used on characters - it works equally well finding longest common word subsequences.

Re: Longest common subsequence

Ravi Annaswamy — Wed, 10 Feb 2010 06:03:55 -0000

Excellent document and teaches on a variety of levels and topics so nicely introducing so many things so well and aptly. I am now a fan of your writing.
Many many many thanks for taking the time and willingness to write out such
great material that would benefit next generations, introducing them to the best
thoughts and practices.

Question on the lcs: one would think that before character-by-character match on a long string, one would try to split it up into 'words' and tokenize them and then match the tokens. In other words, from the alphabet soup of dna string one could create ngrams and shorten the strings.

Or if the texts to be matched are english, one would tokenize, replacing each word with a hash key and so on. The idea is that 'chunks are matched against chunks, instead of always a character by character match'.

Are you aware of such 'hierarchical search algorithms'?

Re: String literals and regular expressions

John — Sat, 06 Feb 2010 06:59:52 -0000

"A complete C++ string literal matcher"
--------

You seem to forgot string declarations like :

const char* test = "this is a multiline"
"test, it compiles, but your regexp doesn't seem"
"to work with this kind of example :) ";

In there "regex_replace" example boost uses this example to match literals strings :

"\"(?:[^\\\\\"]|\\\\.)*\""
source : http://www.boost.org/doc/libs/1_42_0/libs/regex...

It's realy close of your example, but this one doesn't work for the case above.

I don't know how to complete your regexp to match my example..
Do you have an idea?

Nice work, usefull article, thanks. :)

Re: Ignoring .svn directories

aaron — Wed, 03 Feb 2010 12:35:40 -0000

very cool find command and emacs integration! ty for you help and useful descriptions!

Re: Power programming

bestform — Mon, 01 Feb 2010 17:34:20 -0000

I don't see, where he didn't solve the problem - and I am not talking about the elegance of his solution. This is - as we all might have recognized by now - a little bit subjective. The description of the problem doesn't mention anywhere, that you should write a recursive parser. Of course, that's what you obviously might expect as a solution, but it's not what's being asked for explicitly.
And even IF the challenge did mention something about the way it is expected to be solved, he still could use this very example to show, that there exists a way of solving it without writing a parser. This doesn't mean, that it's a good idea. And it certainly doesn't mean, that you should like it. But it's perfectly legit to prove a point. Which it did.
And by the way. You know, that Guido van Rossum works at google and might have had some influence in this challenges? The way the input is formated might not accidentally be like it is. I think it's possible, that they thought, there might be someone out there who solves the parsing with a simple eval, just for fun. Who knows.

@emphasis: he marked "can't" in bold while you marked "c++". I don't blame you for "reading it wrong", you just put the emphasis on a different word by marking a different word. If you want to blame someone for being picky the wrong way when blaming someone for being picky the wrong way, do it right. (yeah, I know that it's getting pretty silly at this point but ICNR)

And one last thing: we indeed agree, that we've equally valid opinions, and we merely disagree. Let's keep it on this level.

Re: Power programming

John Haugeland — Sun, 31 Jan 2010 17:04:20 -0000

Funny, when the man himself replied, he didn't raise that point. I suppose that, yes, C++ cannot embed an entire programming language for the purpose of parsing one string that resembles but is not the problem description.

That does not, however, affect any of the things I said to the man, which were about that he failed to understand the purpose of the challenge in the first place, which was to write the recursive descent parser, and instead did something that whereas might be seen as a convenient hack nonetheless didn't even solve the problem in the first place.

Horseshoes and hand-grenades, and all that jazz. It'd be a more compelling hack if it actually solved the problem. If you really want a compelling hack, write the one-liner regexp that makes this actually work. It will still get a resounding yawn, because it's neither difficult nor anything short of tremendously obvious.

My criticism stands: this has nothing to do with elegance. This is the exact opposite of elegance. This is a ridiculous approach, and it isn't even finished, because it's one line of code short of solving the actual problem.

And by the way: we disagree on his emphasis, and you aren't the original speaker, so don't presume to comment on that I'm wrong in my reading of his words. We've equally valid opinions, and we merely disagree. If you want to pick on someone for being picky, do it right.

Re: Removing duplicates using itertools.groupby

stockrt — Sun, 31 Jan 2010 00:31:04 -0000

Really good stuff.

I would like to post here how do I do the "sort | uniq" and "sort | uniq -c | sort -n" kind of things:

def sortuniq(lista):
return sorted([a for a,b in itertools.groupby(sorted(lista))])

def sortuniqc(lista):
return sorted([(len(list(b)), a) for a, b in itertools.groupby(sorted(lista))])

Examples:
muscle = ['charger', 'charger', 'dart', 'fury', 'mustang', 'camaro', 'mustang']

utils.sortuniq(muscle)
['camaro', 'charger', 'dart', 'fury', 'mustang']

utils.sortuniqc(muscle)
[(1, 'camaro'), (1, 'dart'), (1, 'fury'), (2, 'charger'), (2, 'mustang')]

Best regards!
Rogério Schneider (http://stockrt.github.com)

Re: Power programming

bestform — Sat, 30 Jan 2010 16:16:49 -0000

@commas: sorry for not being a native speaker. I hope you can forgive me.

@"something c++ can't do": he didn't say, that c++ couldn't solve the problem. He just showed, that it can't do it in a certain way. You don't have to like that way (using something like eval), but it is something c++ can't do. Live with it. I know you can.

And by the way: his emphasis in the original text was on "can't", not "C++". If you want to be picky, do it right.

Re: Power programming

John Haugeland — Fri, 29 Jan 2010 17:56:41 -0000

"I think a linked list is an elegant data structure."

... really?

I think you use that word much, much too easily.

Re: Power programming

John Haugeland — Fri, 29 Jan 2010 17:55:36 -0000

"But in this article I wanted to discuss something C++ can’t do."

Emphasis his. Way to miss my point.

"Try to calm down and realize, that it's not about string parsing or use of libraries."

We don't agree. Commas are difficult, aren't they?

Re: Power programming

bestform — Fri, 29 Jan 2010 17:19:58 -0000

Dude, seriously. Calm down.

You seem to be someone, who wrote two or three lines of code in his life for sure. You know your job. But what you write is just bitter. Tag shows us his excitement for different approaches to solving a simple problem. It's fun to explore different possibilities and languages, just for the sake of it.

That doesn't mean that you would ever solve such a problem in this way in production code. But that wasn't the motivation at all.

To say, he didn't solve the problem in python is not the way I'd put it. It was a code challenge. There is an input and there is an expected output. To "solve" the challenge you have to present a solution which takes a clearly specified input and gives you an expected answer. His solution does exactly that. That you in particular don't like his approach and feel, that it's cheating, is kind of sad and tells a lot about your lost fascination for unusual problem solving, which any coder should try to preserve.
Remember: this is a code challenge and it's meant to be fun and a possibility to explore techniques you probably wouldn't use in your everyday production code.

Try to calm down and realize, that it's not about string parsing or use of libraries. Tag represents a spirit, that is honorable and that should be in all of us coders. Instead of calling him a beginner with no sense for elegance, you could just have presented your sense of elegance and your way of solving the problem.

Re: Power programming

tag — Wed, 27 Jan 2010 19:41:04 -0000

I think a linked list is an elegant data structure. I think a heapq is an elegant data structure. I don't think this is a difficult problem at all: I was just using it to talk about some things which interest me.