IWebThereforeIAm

Programming challenge #10 has been posted at dev102.com.

If all the numbers 1..n were present, then they would sum to n(n+1)/2. If some x is absent, then they will sum to n(n+1)/2 - x. So to determine which number is missing, subtract the sum of the series from the expected sum.

This python code finds the missing number in the series named values:

def test(values) :
	max_val = len(values) + 1
	expected_sum = max_val*(max_val + 1) / 2
	return expected_sum - sum(values)

Here is a complete test:

import random
def test(values) :
	max_val = len(values) + 1
	expected_sum = max_val*(max_val + 1) / 2
	return expected_sum - sum(values)

test_range = 200
for i in range(1,test_range) :
	a = range(1, i) + range(i+1, test_range+1)
	random.shuffle(a)
	x = test(a)
	if x != i :
		print "Failed at ", i
		print a
		print sum(a)
		break

I traded for two Denver coins: Michigan and Wisconsin.

I've updated my list of missing Denver mint coins to reflect this.

This is a video with sound of an internal systems support guy's fictional morning. It is so funny. Comic gold:

• remote desktop'ing into a salesguy's machine to discover that all the icons on his desktop form a penis outline
• deleting boss's email from his sent mail to support denial of never having seen the message
• attacking coworkers in Halo game

Programming challenge #9 has been posted at dev102.com. I think that this is about the shortest solution possible.

I initially did this recursively, but I needed two functions: one for the base case using the root and one for all other cases. Here, I just set up the preconditions in variables outside the loop and iterate over the left and right nodes. Which node is second last depends upon whether we went left or right in the last iteration: if left, then the current; if right, then the parent.

Node secondLast(Node root)
{
 boolean wentRight = true;
 Node parent = NULL, current = root;
 while (current->left && current->right)
 {
  parent = current;
  wentRight = (current->right != NULL);
  current = wentRight ? current->right : current->left;
 }
 return (wentRight ? parent : current);
}

I suppose I could be perverse and write the loop with a body of a single line, assigning to parent, wentRight, and current within a single ternary operator statement:

  current = (wentRight = ((parent = current)->right != NULL)) ?
   current->right : current->left;

I think that's a bit obscure just for the sake of brevity.

2008-06-24: I could even drop the wentRight variable and use the parent variable to record which way we went:

 while (current->left && current->right)
 {
  parent = (current->right != NULL) ? current : NULL;
  current = (parent == NULL) ? current->right : current->left;
 }
 return (parent != NULL) ? parent : current;

Now we're down to a loop with just two variables. I don't think I can make the code shorter and simpler than that.

Jeff Atwood (of CodingHorror) has a great article for programmers pursuing self-directed learning. He has lots of ideas on how to practice programming.

Here are some recent resources I found for ETFs. Of particular interest are sites that list current ETFs.

• MasterData
• Yahoo ETF list
• ETF Connect
• ETF Zone

2008-06-25: MoneyCentral also has an ETF list. Unfortunately, you have to page through them 20 at a time. You can't download them all at once.

Recently, I came across some good resources on NHibernate on an email list I subscribe to. Summer of NHibernate is a continuing series of webcasts that are used to teach developers about NHibernate. Here are the current links to webcasts:

• Session 01: Basic Setup and Usage Pattern
• Session 02: Exploring Query Methods and Syntaxes

[Using NHibernate with Stored Procedures]

Not entirely on the mark. Some of these sites maintain real open source projects. Others, like CodeProject, are write-only sites with no collaboration.

• [CodePlex]
  CodePlex is Microsoft's open source project hosting web site.
• [SourceForge]
  SourceForge.net is the world's largest Open Source software development web site. SourceForge.net provides free hosting to Open Source software development projects with a centralized resource for managing projects, issues, communications, and code.
• [Apache Software Foundation]
  The Apache Software Foundation provides support for the Apache community of open-source software projects. The Apache projects are characterized by a collaborative, consensus based development process, an open and pragmatic software license, and a desire to create high quality software that leads the way in its field.
• [FreshMeat]
  freshmeat maintains the Web's largest index of Unix and cross-platform software, themes and related "eye-candy", and Palm OS software. Thousands of applications, which are preferably released under an open source license, are meticulously cataloged in the freshmeat database, and links to new applications are added daily. Each entry provides a description of the software, links to download it and to obtain more information, and a history of the project's releases, so readers can keep up-to-date on the latest developments.
• [CodeProject]
  The Code Project was formed to provide developers with a place to meet and exchange ideas. We hope to provide developers with all the resources they need to help them in their day to day programming, as well as helping them keep up to date with the latest technologies.

I came across a great programming article on how to calculate the combinations of states to produce 270 or more electoral college votes. I've honestly never done any dynamic programming problems like this. At least, I haven't done them the dynamic programming way; I've done them by brute force, and often I haven't gotten an answer because brute force is too slow.

With this in mind, I'll be revisiting some of the Project Euler problems because with this method and insight, so many more problems will be tractable. In particular, I expect this one will succumb to a dynamic programming solution.

In the meantime, here is the python code to solve the problem:

votes = [55, 34, 31, 27, 21, 21, 20, 17, 15, 15,
    15, 13, 12, 11, 11, 11, 11, 10, 10, 10,
    10,  9,  9,  9,  8,  8,  7,  7,  7,  7,
     6,  6,  6,  5,  5,  5,  5,  5,  4,  4,
     4,  4,  4,  3,  3,  3,  3,  3,  3,  3,
     3,
]
import collections
ways = collections.defaultdict(int)
ways[0] = 1
for n in xrange(len(votes)) :
    for v in xrange(270+votes[n]-1, votes[n]-1, -1) :
        ways[v] += ways[v-votes[n]]
print sum(ways[k] for k in ways.iterkeys() if k >= 270)

[CodeFetch] allows developers to search programming books online for code samples in the language of their choice.

Say you wanted to find a C# code sample that implements a priority queue, like I did here. You could get several implementations from CodeFetch with a simple search. Mind you, the implementations I'm seeing are a bit bizarre. Would you really implement a priority queue by maintaining a sorted array?