DaedTech

Stories about Software

Jun
29

By

P, NP And Decision Problems (Really, It’s Not that Bad)

Category: Practical Math | 5 Comments

After a relatively lengthy hiatus from this series, I’m going to bring back the Practical Math series, but with two changes. First, in spite of my rather intense predilection for symmetry and order, I’m going to dispense with the stock set of headers to fill out and get a little more free form with these. And secondly, I’m going to expand it to kind of be “Practical Math for Programmers but also Practical Computer Science and all of the Discrete-Mathy things in between.” With the former concession, my aim is to remove my own blockage from writing these posts — the template is good for consistency, but it sort of sucked the fun out of it and I’d stare at the headers and think, “ugh, okay, that’s a lot to do.” With the latter concession, I mean to acknowledge that computer science and a lot of the algorithms involved are fundamentally “mathy” and that’s okay. We’ll work together to make this thing approchable.

One of the coolest concepts that I ever encountered as a student or in life was NP Complete problems. It’s a rather mind blowing subject and it’s simultaneously philosophically complex and simple to approach.  I’d also like to offer the caveat here that I’m a long, long way removed from formal study of this topic, so what I’m posting here is my recollection of the topic combined with a hodgepodge of visits to various .edu sites to refresh my memory on some of the finer points.  The intention here is to give an approachable introduction to those programmers who’ve never really had formal CS backgrounds and not to defend a PhD thesis.  I’ve made a good faith effort to keep things accurate, but let no one confuse this with a textbook.

Now, lest I scare anyone off too quickly with that disclaimer, let’s do some grade school math. What are the prime factors of 12,317? You’ve got 20 seconds. Ready, set, go!!!

(In my best Alex Trebeck voice) Oh, no, sorry — you’re out of time. Let’s try a different one. How about 109 x 113? Bet you can hammer that one out in 20 seconds either by firing up Calc.exe or just doing it longhand. Well, look at that, 12,317. Whaddya know? And both of those are prime factors, so you now have the answer to the last question too. But… why is it so much harder to reduce a composite number to prime factors than to do multiplication. I mean, 5 x 5 isn’t a whole lot harder than 25/5. Why is factoring so much harder than multiplying? Kind of interesting to think about, huh? And just like that, you’ve dipped your toe into the waters of pretty heavy discrete math and computer science theory.

See, it’s not that bad. Let’s consider some concepts now before we give them names. I think the names get pretty weird pretty fast if you don’t first understand the concepts. Thinking about the idea of factoring versus multiplication and contemplating the nature of the uneven difficulty level, you might think as follows. Multiplication is a problem that you can solve pretty easily. Prime factoring is a problem that you can solve, but not as easily. However, given a number and a candidate prime factor, what you can do is check really easily. In other words, when you were trying to find the prime factors of 12,317, you were doing something like, “let’s see, is it divisible by 2… no… 3… nope… 5… etc.” But if someone came along and said, “is 109 a factor of 12,317,” you would say, “wow, it sure is, and now I’ve also found the only other prime factor to boot. Thanks man!” So we can differentiate between whether a problem can be solved easily (e.g. multiplication but not factoring) and whether a prospective solution for a problem can be checked easily (e.g. both factoring and multiplication). And we can also phrase our approaches to these problems in yes or no forms, requiring a decision to be rendered: “Is 109 a factor of 12,317 — yes or no?” or perhaps, “do any smaller prime factors of 12,317 exist?”

With me so far? Good. Let’s not confuse things any more quite yet, opting instead to give voice to the reasonable question, “alright, whatever, but who cares?”  Well, for starters, the NSA and cares and so should you’re concerned about the degree to which they trample on your various rights.  The reason for this is that the imbalance between time required to solve multiplication and factoring plays a crucial role in a number of public key encryption schemes.  If you want to go beyond the realm of encryption and civil liberties, consider the implications of the discovery of a fast, polynomial time solution to NP Complete problems: you’d basically solve all of mankind’s problems.  Aside from personal glory and every conceivable medal/prize under the sun, you’d be able to answer the question, “how do I build the fastest possible fighter jet” in relatively short order, especially when compared to the way we’d currently need to approach the problem, which would be to build every possible fighter jet and see which one is best (perhaps applying some limited heuristics).

If this sounds comically grandiose, it sort of is, but also, it’s sort of not.  It’s unknown whether this unicorn solution (fast polynomial time algorithm for NP Complete problems) is even theoretically possible, but if it is and then it were solved, it would probably be the most ground breaking mathematical discovery in the history of mathematics.  But if you’re the sort who likes practical answers to “why should I care?” then consider the ability to recognize problems NP problems as a sort of “road closed” sign when looking for algorithmic efficiency.  If you realize that a problem is NP Complete, you can give up on finding a slick way to do it and realize that it’s either time to go with brute force or time to seriously reconsider what you’re doing.

So what is this P and NP and NP Complete and all that?  Well before we go back to some of the discoverable concepts from the factoring example and before things get all formal, let’s consider an example of an NP Complete problem.  Things are always easier by example than by mathematical definition, so let’s talk about a salesman and his travels.

Let’s say that there are a bunch of cities that are on a salesman’s route, and that the salesman has to visit each city exactly once.  Obviously, there is a mileage distance associated with each trip between cities, and let’s say that our salesman can only fly on one particular airline and that it’s not a given that there are flights between any two cities.  So, to review, one airline, all cities visited exactly once (which theoretically may or may not actually be possible, depending on the cities involved), mileage tabulated along the way.  The question that is then NP Complete is, “is there an itinerary for the salesman that results in him traveling less than X miles?”

I like this because it’s pretty simple to understand what’s being asked, as far as examples of heady discrete math concepts go.  And, it’s also possible to understand where the subtle complexity creeps in.  Can you think of a way to solve this other than brute force through all possible routes and then checking to see if a given one is less than X?  (If you can, email me your solution and tell no one about this!  I’ll see that it winds up in good hands.)  Can you also see that, while answering the question is a matter of brute force, checking the answer is a simple, polynomial time proposition (walk the given path adding up the miles and then see if the total is less than X)?

Okay, so let’s finally get to some definitions, but I’m going to keep them colloquial rather than mathematically rigorous, given the theme of this series.  First off, as touched on earlier, there is the concept of a decision problem.  A decision problem is simply a problem in which an algorithm is applied to some set of inputs and will produce an answer of “yes” or no.”  Examples include “do any smaller prime factors of 12,317 exist?” and “is there any sales route to be traveled where the salesman can fly less than 120,000 miles?”

Now to spice things up a bit.  P problems are a class of decision problems where the decision can be rendered in a time that is polynomial in relation to the input.  This means that in O notation terms, you’d be talking about things like O(n), O(n^3), O(n^20), etc.  The time might be awful, but it wouldn’t be exponential like O(2^n) or combinatorial like O(n!).  NP problems are a class of decision problems where a proposed solution can be verified in time that is polynomial in relation to the input.  Conceptually, P problems are a subset of NP problems, which makes sense.  After all, if you can answer whether or not there’s any path that the salesman can travel in short order, you can certainly check one particular path in pretty short order too (and, conceptually, if you can enumerate all of them in polynomial time, you could simply solve the verification problem by just paying attention when you happened to get to the proposed solution).

Now, at this point you might wonder whether P is more than a subset of NP, but actually the same as NP.  This puts you in good company with the entirety of those who study theoretical computer science.  This is one of the most important problems in the field in need of a solution.  Okay, so what’s NP Complete, exactly, since we’ve been talking about it?  To answer that, I’m going to reach back to an old post where I talked about this concept obliquely.

I don’t have a fast (polynomial time) solution for the traveling salesman problem, but let’s say that I did.  Let’s say that I had some magical oracle that solved this in short order.  Since the traveling salesman problem is NP Complete and I have an oracle that can solve it quickly, it means that I can use my oracle to solve any other NP problem quickly (polynomial) as well.  To be a little more rigorous, I could, in polynomial time, transform my oracle into a solution for any other NP problem, in polynomial time.  So NP Complete problems are those where if you find such an oracle, you win life.  If a problem is not in NP complete, your oracle is a bronze medal.

There is a lot more that could be covered, but I think this is probably a good stopping point on the subject.  For more reading, here are some interesting links:

Jun
26

By

TDD Chess Game Part 8: Hail to the King

Category: You Asked For It Tags: , , , | 8 Comments

Today’s episode is one with a pretty directed focus. I’m actually typing this prior to doing the screen capture, but I know what I want to do ahead of time. I want to implement the King piece, and I have a relatively good idea how to do it.

Here’s what I accomplish in this clip:

  • Implement King with GetMovesFrom()

Here are some lessons to take away:

  • Sometimes you’ll go into a coding session with a discrete, obvious goal, and other times you’ll have to break a nebulous goal into discrete, obvious ones.  But you always want discrete, obvious ones if you can.
  • If you can save yourself using the mouse via being proficient with keyboard shortcuts, I’d definitely go this route.  The time savings amortize over lots of coding.
  • For “simplest thing” in TDD, it doesn’t always mean that you have to bang out a line of code.  Maybe you can pull an existing method to a common ancestor and use it, or instantiate and use some other object.
  • “Simplest thing” is kind of an art form geared toward your best productivity.  If you’re new to the process of TDD, you probably want to keep it really simple before you’re experienced enough to be discerning.  Once you’ve established it and gotten good at the basics, you can adjust to situational taste.  Perhaps sometimes you’re stuck and need to get really simple while, in other cases, you have a good grasp on what comes next and being obtuse would just be busy-word.  Practice and use your judgment.
  • If you’re using a continuous testing tool (and specifically C#), pay attention to coverage with IEnumerables.  It seems trivial, but it’s really better if you’re executing every line, even if it just means calling ToList() somewhere.

Jun
25

By

Honesty and the Workaday Blogger’s Connundrum

Category: You Asked For It Tags: | 2 Comments

Last night I got an email asking for some perspective on something, and it’s prompting me to go “meta” and write a post about being a techie blogger. The question basically boiled down to “how do I make a cathartic blog post about Expert Beginner coworkers without getting myself in hot water at work?” If you’re a blogger with a 9-5 and coworkers, this is a pretty valid concern. After all, your coworkers will certainly provide you with the most material about which to write, simply by virtue of the fact that so much of your relevant experience will involve them directly. Add to that the fact that blogging (really, writing in general) can be a nice outlet for saying things that are politically untenable in situ, and this is something that matters to bloggers.

So, here are my thoughts on the subject.

Is This Thing On?

First up is asking yourself the sometimes awkward question, “is anyone even reading this?” In the first year or so that I was blogging, I’m pretty sure almost no one was reading except for spam bots and search engine spiders. If none of your coworkers are likely to read your blog in the near future, it’s a moot point and you can probably write whatever you want.

Now, you may think to yourself, “sure, but what about later if it becomes more popular with them or in general?” That’s a possibility (and in terms of readership a good problem to have), but it’s actually kind of unrealistic to think that people/coworkers are going to peruse everything in your archives in encyclopedic fashion. Most likely they’ll think, “look at that, Erik has a blog — I’ll go read half of a post.” If the title isn’t somehow indicative of the conflict/subject-matter, it’s not likely to attract notice. Additionally, Expert Beginner types tend not to spend a lot of time reading blogs and concerning themselves with the opinions of others, so they’re even less likely than the average person to go browsing through your opinions.

Of course, there is always a risk when you take the “whatever, no one will notice” attitude.

Surely That’s Not Me

This won’t apply if you’re relating an anecdote, but if you’re describing personality traits, never underestimate someone’s ability to gloss over their own shortcomings. For instance, let’s say you write a post describing someone as:

  • Short-sighted and myopic in big picture thinking.
  • Averse to new ideas and afraid of change.
  • An organizational cancer.
  • A passive aggressive malingerer.
  • An unending source of misery for coworkers.

It’s not very likely that someone will read that and think, “oh, that must be me.”  A lot of people have a blindspot for not only their weaknesses but for how they are perceived by others.  This is often doubly true of the kind of tone-deaf people that go around upsetting those around them — self-perception and external perception are often wildly out of touch.

Like the previous section, this is no guarantee that people won’t know who you’re talking about.  If you supply an anecdote making it clear who the parties involved are or if your antipathy toward that person is commonly known, they might recognize themselves being described.  But they honestly, really might not.

Obfuscate

I have myself submitted entries to The Daily WTF, so I can speak to the anonymyzing that takes place when you do so. They change details about your story while leaving intact in terms of meaning. So maybe the language is Java instead of C++ where applicable. Maybe a telecom client becomes an aerospace client. Maybe a female coworker becomes a male. When they’re done, you recognize your story but take comfort knowing that nobody else would. At best, they’d think, “that’s weird, I remember something similar but in different circumstances.”

Anonymous

You can do that with your blog too. Take a current story and superimpose it over the people and techs at your previous job. Be nebulous about dates when something happened recently — “some time back, I…” Make the “Project Manager” a “Business Analyst” or describe a “Software Engineer” as a “Senior Software Engineer.” You can also insert some vivid details that are false flags but not important to the meaning of the story.

The line you walk when doing this is the line of sacrificing an element of how genuine you are. Personally, when I’ve obfuscated to protect the people involved (or myself), I’ve done so more with intentional vagueness of timelines and places than anything else. As far as strategies for not suffering blowback go, this is a pretty effective one. Even if the person/people in question suspect, you have complete plausible deniability. But you do sacrifice an element of honesty.

Whatever, I Do What I Want!

Short, sweet, simple. Print it and make no attempt to hide it. Go forward with the mantra that people doing stupid things ought to be called out for their behavior. The blowback for this may be intense, but so too, I’d imagine, is the catharsis. And hey, perhaps it’s the fire you need to light under yourself to move things along a bit toward a better option if you’re really unhappy.

Cartman

Type it Up, Leave it in Drafts

Finally, here’s an option for you. You can type up the most scathing, biting post imaginable, omitting no details. View it as a preview and read and re-read it, relishing in the dressing down that you’re issuing. And then… leave it in your drafts folder for a rainy day. Maybe that day comes when you put in your notice. Maybe it comes a month later. Maybe a year later. Or, maybe you read it after a lot of elapsed time and wonder what you were so upset about.

Time smooths over a lot of wrinkles, and time may be your best ally for for sorting out, in retrospect, whether you were having a bad week or whether you really have something important to say about workplace dynamics and technical discussions. And, it almost goes without saying that this is the option with the least potential fallout for you.

Of course, if all else fails, you can always go to the preposterously elaborate length of starting a twitter account that tweets all of the dumb things to which you’ve been subjected over the years in 140 character increments. But you’d probably have to be pretty demented to do something like that.

Jun
20

By

Creating a Word Document from Code with Spire

Category: .NET Tags: , | 2 Comments

I’d like to tell you a harrowing, cautionary tale of my experience with the MS Office Interop libraries and then turn it into a story of redemption. Just to set the stage, these interop libraries are basically a way of programatically creating and modifying MS Office files such as Word documents and Excel spreadsheets. The intended usage of these libraries is in a desktop environment from a given user account in the user space. The reason for this is that what they actually do is launch MS Word and start piping commands to it, telling it what to do to the current document. This legacy approach works reasonably well, albeit pretty awkwardly from a user account. But what happens when you want to go from a legacy Winforms app to a legacy Webforms app and do this on a web server?

Microsoft has the following to say:

Microsoft does not currently recommend, and does not support, Automation of Microsoft Office applications from any unattended, non-interactive client application or component (including ASP, ASP.NET, DCOM, and NT Services), because Office may exhibit unstable behavior and/or deadlock when Office is run in this environment.

Microsoft says, “yikes, don’t do that, and if you do, caveat emptor.” And, that makes sense. It’s not a great idea to allow service processes to communicate directly with Office documents anyway because of the ability to embed executable code in them.

Sometime back, I inherited an ecosystem of legacy Winforms and Webforms applications and one common thread was the use of these Interop libraries in both places. Presumably, the original author wasn’t aware of Microsoft’s stance on this topic and had gone ahead with using Interop on the web server, getting it working for the moment. I didn’t touch this legacy code since it wasn’t causing any issues, but one day a server update came down the pipeline and *poof* no more functioning Interop. This functionality was fairly important to people, so my team was left to do some scrambling to re-implement the functionality using PDF instead of MS Word. It was all good after a few weeks, but it was a stressful few weeks and I developed battle scars around not only doing things with those Interop libraries and their clunky API (see below) but with automating anything with Office at all. Use SSRS or generate a PDF or something. Anything but Word!

Interop

But recently I was contacted by E-iceblue, who makes document management and conversion software in the .NET space. They asked if I’d take a look at their offering and write-up my thoughts on it. I agreed, as I do agree to requests like this from time to time, but always with the caveat that I’ll write about my experience in earnest and not serve as a platform for a print-based commercial. Given my Interop horror story, the first thing I asked was whether the libraries could work on a server or not, and I was told that they could (presumably, although I haven’t verified, this is because they use the Open XML format rather than the legacy Interop paradigm). So, that was already a win.

I put this request in my back pocket for a bit because I’m already pretty back-logged with post requests and other assorted work, but I wound up having a great chance to try it out. I have a project up on Github that I’ve been pushing code to in order to help with my Pluralsight course authorship. Gist of it is that I create a directory and file structure for my courses as I work on them, and then another for submission, and I want to automate the busy-work. And one thing that I do for every module of every course is create a power point document and a word document for scripting. So, serendipity — I had a reason to generate word documents and thus to try out E-iceblue’s product, Spire.

Rather than a long post with screenshots and all of that, I did a video capture. I want to stress that what you’re seeing here is me, having no prior knowledge of the product at all, and armed only with a link to tutorials that my contact there sent to me. Take a look at the video and see what it’s like. I spend about 4-5 minutes getting setup and, at the end of it, I’m using a nice, clean API to successfully generate a Word document.

I’ll probably have some more posts in the hopper with this as I start doing more things with it (Power Point, more complex Word interaction, conversion, etc). Early returns on this suggest it’s worth checking out, and, as you can see, the barriers to entry are quite low, and I’ve barely scratched the surface of just one line of offerings.

Jun
17

By

Code Reviews Should Be about Incremental Improvement

Category: The Life of a Programmer Tags: , | 4 Comments

Persuasion tends to happen at the micro-level, in terms of information volume and breadth. For instance, if I explain that I use “var x = 6” instead of “int x = 6” because a productivity add-in squawks if I don’t, you’re likely to be swayed if you find my case persuasive. If, instead, I explain that sometimes I use implicit typing and sometimes I don’t, and then I proceed to list dozens of heuristics, you’re most likely to tune out and, if I’m lucky, process and be swayed by one or two individual bullets that I mention. In these cases the grain of the subject matter is fine, but it works for coarser grained concepts as well: I may sway you on whether or not to write unit tests, onion versus layered architecture, or C# over Java. It isn’t the scope of the topic that matters, but rather the relative narrowness of information and message. Persuasion simply works better when the thesis is clear, and the arguments convincing and too the point.

This bit of human nature is incredibly important to understand when sitting for code reviews, both as a reviewer and reviewee. When I review code and someone starts telling me all in a rush about design patterns that they like and why these six classes communicate over a conceptual bus implementation and why there’s a private method in each class called “PreserveInvariants()” and so on, I’m overloaded with information. Are some of these things good ideas? Probably, I imagine. Are all of them good ideas? I don’t know — slow down. I’m not smart enough to leap instantly into a shared context in which the last several weeks of your design decisions and thinking are jacked into my brain, The Matrix style.

Neo

You’re not going to solve the world’s problems in a given code review. Really, you’re probably not even going to solve all of that many of the code bases’s problems either. But, you can decisively solve or address a few. Much as TDD forces you to focus on one problem at a time, I think well done code reviews follow suit. Aim for a handful of ways in which you can make the code better and upon which all parties agree, and consider that a win for the day. This limtiation to a handful of things to cover will keep the scope of the persuasion narrow enough to be effective, whether it’s the reviewee persuading the reviewer to agree with the choices or the reviewer convincing the reviewee to change things. Or, perhaps it will wind up being a bit of both.

As a reviewer, I generally read through the code, offering first blush impressions and asking questions. “Wow, this method seems pretty big.” “Why did you decide to make that method public rather than private?” There, now there’s one narrow point to address in each case, and we can make our attempts at convincing one another. You can explain by describing where this fits in within the big picture or by whatever means you feel available. This dialog lets us explore your code, style and reasoning together. But if you tell me up front, without prompting, the entire philosophy of your approach and all of your decisions, it will be overload, and you’ll fail to persuade. You’ll succeed only in confusing me. I know it’s tempting to address people’s possible objections before they can raise them (gives the feeling of control), but that’s usually just confusing.

As someone whose code is being reviewed, I let the reviewer process the code under review before the dialog begins. I try to resist the impulse to jump in and explain every facet of my design because it will fall on deaf ears until the code has really been groked, and maybe even after if I’m bombarding the reviewer with information. If I want to provide this information, a writeup is definitely the preferred way to do it since this allows the reviewer to pull the information as desired, rather than having it sprayed like a firehose.

So, code reviews ought to cover a handful of concepts only, to allow for the maximum back and forth of persuasion as necessary. All well and good, but you have a lot of code to cover, right? Well, to address this concern, have the code reviews more frequently or even do semi-regular or regular pairing sessions. If your code only gets reviewed once per quarter, there’s a natural tendency for the review to become a performance evaluation of you as a programmer. But that’s a terrible vehicle for narrow, focused persuasion. If you’re having your code reviewed three times per day, then when the reviewer notices a fourth point of discussion, he’s more likely to say, “meh, three is enough for now — we’ll get this other one next time.”

In the end, code reviews are about persuasion. And effectiveness is really what’s important when trying to persuade someone that your way of thinking makes sense. It pretty much goes without saying that the most important part of being persuasive is making a good case, but I’d argue that a close second is the narrowness of focus on the subject for persuasion. I’m unlikely to persuade you that you should copy every facet of my life, but I might just be able to persuade you pick your battles in code reviews.

« Older Posts
Newer Posts »