mgroves

I’ve been cranking away at Euler problems lately.  It’s kinda addicting.

Problem 14 is about the Collatz Conjecture, which just so happens to be the subject of a recent xkcd comic:

But there’s nothing special about the sequence when solving this problem, really.  I did learn a neat trick after solving this problem: normally to check if a number was even, I would just look at its modulus of 2—if it’s 0 then it’s even.  But there’s a faster way to do it: do a bitwise ‘and’ with the number and 1, if the result is 0 then it’s even (and bitwise operations are certainly faster than division operations).  This trick isn’t exactly obvious to the code reader, so I put it into the MathHelper class as an “IsEven” method.

p>Problem 15 is about finding all possible paths through a grid.  I struggled a bit with this one.  I tried a recursive solution, but the answer never seemed to be right.  I kept getting this nagging feeling that there’s some pattern that I was missing, so I Googled about it and discovered that you can actually take Pascal’s triangle, turn it sideways, and lay it directly over a grid.  The corresponding corner value is the answer.  So, once again, I put a PascalTriangle method into MathHelper.

Problem 16 is yet another problem that’s easy to solve with a BigInteger class.  Performing an exponential operation on it is just like with regular numbers: using a “shift” operator is faster than performing actual multiplication.  Then it’s just a matter of going through every digit and getting the sum.

And finally, problem 17, which was fun.  I again tried a recursive solution, and then it was just a matter of defining the minimum amount of rules (one – nineteen, twenty, thirty, … ninety, and one thousand).  Writing tests made this problem a breeze.

That’s all for now.  Remember, you can check out the source code at CodePlex.  Also, check out my nifty new WinForms UI for running the tests.

“The first rule of functions is that they should be small. The second rule of functions is that they should be smaller than that." (page 34)  When I was first learning programming, it was my understanding that functions should be used whenever you have a piece of code that you will reuse.  If you aren’t going to reuse it, it doesn’t need to be a function.  However, this overlooks an important feature of functions: their names.  Even if a function is only used once, even if doesn’t return anything, even if it doesn’t take parameters, it’s still useful to take a block of code and name it according to its intent.  Does this lead to a lot of functions?  Maybe.  So what?  It’s easier to read and maintain.

Functions shouldn’t have a lot of parameters.  A bunch of ‘out’ or ‘ref’ parameters is usually a clear sign that maybe another class should be created.  A function with one parameter is called a monad.  A function with two parameters is called a dyad.  A function with three parameters is called a triad.  A function with four or more parameters is called epic fail.

This chapter is a very good one, with lots of great guidelines for writing functions, and a lot of the stuff in this chapter can also be applied to objects & systems (as I’ve read in later chapters).

I’m not a big fan of ASP.NET WebForms, and one of my pain points is form validation.  It seems a bit heavy-handed and clumsy compared to, say, Dynamic Data or MVC.  Generally, it’s adequate.

To validate that a textbox is required is easy enough, just use a RequiredFieldValidator.  To validate the text is in some specific format seems easy enough too, just use RegularExpressionValidator.  But the “gotcha” that may not be immediately apparent is that using the RegularExpressionValidator as is requires you to violate DRY, since you must specify the ValidationExpression each time you use it.  With this, you get all the standard pitfalls of DRY, including the possibility of a phone number formatting on Form1.aspx being totally different than the phone number formatting on Form2.aspx.  So, wat do?

Here’s what I did: create a more specific implementation of RegularExpressionValidator called PhoneValidator

using System.Web.UI;
using System.Web.UI.WebControls;

namespace Whatever
{
    [ToolboxData("<{0}:PhoneValidator runat=\"server\" />")]
    public class PhoneValidator : RegularExpressionValidator
    {
        public PhoneValidator()
        {
            ValidationExpression = @"^([\(]{1}[0-9]{3}[\)]{1 ... $";
        }
    }
}

And now you can use PhoneValidator just as you would RegularExpressionValidator, except the ValidationExpression only exists in one place for consistency and ease of change.  Don’t forget to register the assembly that the above class is in on your page:

<%@ Register assembly="WhateverAssembly" namespace="Whatever" tagprefix="MyValidator" %>

(Or you could register it in your web.config for use in the whole app).  Once it’s registered, just do this (it should appear in intellisense as well):

<MyValidator:PhoneValidator ControlToValidate="txt_phone_number" runat="server" />

As always, you can find my source code at CodePlex.

Problem 11 has given me all kinds of trouble.  So much so that I haven’t actually solved it.  I’ve tried 2 or 3 different methods, I’ve Google it, I’ve tried cheating, I’ve tried guessing.  Nothing is working for me.  I gave up after many, many tries.  I’m so sure that I’m doing it right, but I must be missing one minor thing somewhere.

Problem 12 was kinda fun.  The meat of the problem is figuring out the factors of a given number.  Once I had that (which was easy to brute force, and a little tricky to slim down), the rest is just a couple of for-loops.  I used the given example as a single test case.

Problem 13 involves very, very large numbers.  Larger than 32-bits can represent.  So, since I was still using .NET 3.5 at the time, I scratched out a very rudimentary “BigInt” class that only performed addition on itself.  It was just as much a pain in the neck as it was 10 years in Introduction to C++ class, except this time I only implemented one operator.  Once I switched the Project Euler solution over to VS2010 and .NET 4, I went back and switched this solution to use the BigInteger class, which, by the way, is new to .NET (obviously) and lives in System.Numerics.  Anyway, once you have your own BigInt or BigInteger (or some language like Ruby that handles all that nonsense for you), Problem 13 is a piece of cake: just do some adding up and some parsing.  I wrote a couple of tests that used long.MaxValue—I left them in, even though it’s generally quite silly to test a class built into the framework.

If you guys have any ideas for Problem 11, I would love a fresh set of eyes.

I love jQuery for many reasons, the primary one being that it abstracts all the cross-browser pain of writing plain old javascript away to a dark corner where I don’t have to look at it, and can instead focus on the positives of javascript (the same could be said for prototype, dojo, etc).

Until today, jQuery has performed admirably in this role, and has a  fantastic selection/manipulation to boot.  Until today.

You see, there’s this weird event called “beforeunload”, which triggers right as a user is navigating away from a page, but before they actually leave the page.  The sole purpose of this event is to confirm with the user that they want to leave, that they might lose unsaved changes, etc.  It’s not exactly a standard event: some browsers support it, some don’t, and the implementations can be subtly different.  So, naive me, I thought this would be a great place to use jQuery, and abstract away all that cross-browser pain that has bitten me so many times before.

No can do.  Craig Stuntz and I got into a brief discussion today on Twitter, and along with some googling and a quick spike that I did, I learned that jQuery has no truck with onbeforeunload, and if you want to use it, you’re stuck with plain old javascript and cross-browser pain.  Booo.  Fortunately, rare is the occasion where you should use this non-standard event (if ever).

Phil Karlton famously said, “There are only two hard things in Computer Science: cache invalidation and naming things”.  If your code will ever be read by anybody (including yourself) anytime after it’s first written, naming is important.  A variable named “x” has no meaning in most contexts, and neither does “thingWhichDoesSomething”.  Chapter 2 lays down a lot of rules (of thumb) for naming variables, classes, methods, interfaces, etc.

One of the rules states that interfaces/implementations should not be named “ISomething” and “Something”, but rather “Something” and “SomethingImpl”.  This rule stood out from the other rules because it’s one that I disagree with.  I think this is mainly due to me being a .NET developer, where “ISomething” interfaces are common in the framework itself (IEnumerable, IList, etc).  Clean Code uses mainly Java examples, so this might be a convention that’s widely accepted outside of the Microsoft world.  Of course, in Ruby, Python, etc, this isn’t even an issue.  I totally understand Uncle Bob’s reasoning, and I’ve even seen the “Impl” naming used in .NET apps before, but I think I still prefer the “ISomething” naming.

A book that I read some time ago, Framework Design Guidelines, details many of the naming conventions and styles that the .NET framework developers used.  I found this a very entertaining read, and I think it provides a great baseline for .NET developers to work from, even if they aren’t writing frameworks/APIs all the time.  I think Chapter 2 is also a good baseline, but in the end, naming is about communication with other developers, and following a particular language/platform idioms is important to reducing confusion.

This is just a quick post to tell you about one of my favorite development tools: WampServer.  “Wamp” is an acronym for “Windows-Apache-MySQL-PHP”.  WampServer is simply an all-in-one package that will have you up and running data-driven PHP apps locally in no time.  It’s cheaper than IIS (as in, it don’t cost nothin), and easier than installing them all on your own individually.  WampServer will put a little icon in your task tray which you can right-click on to mess with the configuration (individual apache/php modules, etc), but the default configuration is pretty good already.  So uh, go download it.

I purchased Clean Code by Robert “Uncle Bob” Martin, and I’ve been reading it as part of a) one of my goals set as part of my mentor program, and b) a book-club that I’ve co-started among a small group of developers in downtown Columbus.  As I am typing this, I’m currently at Chapter 8, but as a review and as a personal exercise, I thought I would go back and blog about one or two specific things, per chapter, that stood out as interesting or important.  Even though I’m not even halfway through, I think I could easily recommend this book to any developer who is passionate about coding, no matter their experience level.

Chapter 1 simply lays out the case for clean code: the whats, whys, and hows.  The most interesting part of this chapter is that Martin gets quotes from various prominent contemporaries about their personal definitions of “clean code”.  I won’t give them all to you, but I particularly liked this part of Michael Feather’s definition: “Clean code always looks like it was written by someone who cares”.  I don’t think any code is perfect, but clean code at least strives for perfection.  It’s not only expertise, but effort that can be seen in clean code.  That’s what I think when reading Feather’s definition, anyway.

The other interesting point that Martin makes is that There Will Be Code.  Which is to say, despite the efforts of model-driven development, domain-specific languages, etc, there will always be a need for programming and programmers.  The reasoning for this is pretty sound, I think: until there is some software that can detect intentions (not instructions), those intensions will have to be translated into formal instructions.  Technology will change,  software will change, computers will change, but someone will always need to be around to program them.  I don’t think he’s making a point about job security, but rather one about the necessity of craftsmanship, quality, and clean code: code is always going to be around, so let’s make it good code.

Just a quick Project Euler update.  Number 8 was pretty straightforward, I just went through and got each product and then found the max.  For Number 9, I created a Triplet class with an IsPythagorean method.  I then use three loops (nested) to go start from 1 and go up to a given n.  It’s not entirely brute force, because the 2nd number must be greater than the 1st, and the 3rd number can be calculated using the Pythagorean theorum.  Then, if that Triplet sums to the given n, I add it to a list, and return that list at the end.  The Triplet with the highest sum is the answer.  Since the problem says there is only one that sums to 1000, I simply return .Single() of the list.

Number 10 was yet another prime-numbers problem.  I used the IsPrime method from before, and simply looped from 1 to a million, and added the primes to a list.  Linq can be used then to sum up the list, and done.

As before, check out all the source on CodePlex.

One of the interesting phenomena arising from the web and its widespread use by programmers is a disconnect between technical words/jargon and how to pronounce them. If you read a word instead of hearing it from someone, you still make up an arbitrary pronunciation. This can make for awkward moments when the word finally does come up between programmers in person (which does happen, honest!).

Here are some examples.  Read them aloud:

• Tuple
• C#
• SQL
• CAPTCHA
• WSDL
• GUID
• .GIF
• pwned
• char
• varchar

I’ve heard all of the above terms pronounced at least two different ways.  GIF even has a long history of controversy about its pronunciation.  I think I’ve heard “varchar” pronounced about 6 different ways (vair/var + care/car/char).

So, what to do? Even if you are sure that "Tuple" is pronounced "toople" instead of "tupple", it seems petty and annoying to call someone incorrect.  If the intent is understood, then I guess it comes down to a matter of prescriptive vs descriptive linguistics. If you lean towards descriptive linguistics, then it really doesn’t matter if you pronounce CAPTCHA as "cuh-pahtch-uh", as long as your audience knows what you’re talking about. If you are in the prescriptive camp, then C# must be “see-sharp”, and “see-pound” is unacceptable.

Personally, I would lean towards descriptive, so long as there is no possibility of ambiguity. However, I totally sympathize for the prescriptive’s point of view, since in many cases, the pronunciation is not emergent, but defined (as in GIF’s case).

So, what are some other terms (computer-related or otherwise), that have put you into a similar awkward situation?