Entries for Matthew van Eerde

No "Microsoft employee" chiclet? [No "Microsoft employee" chiclet?]

Matthew van Eerde — Fri, 25 Jul 2008 23:35:38 GMT

There doesn't seem to be any (non-spoofable) indication that Microsoft employees are Microsoft employees. Are there plans to bring this back?

in reply to No "Microsoft employee" chiclet?

Page navigation broken in FF 3 [Page navigation broken in FF 3]

Matthew van Eerde — Fri, 13 Jun 2008 17:52:52 GMT

The "pencil" view on the editor is broken too, but the "<>" works for me (I'm comfortable typing in HTML)

in reply to Page navigation broken in FF 3

Niner "recent blog posts" [Niner "recent blog posts"]

Matthew van Eerde — Thu, 12 Jun 2008 15:26:04 GMT

Just noticed the "Recent Blog Posts" section on the Niner profile page. Very cool.

in reply to Niner "recent blog posts"

minesweeper - place your bets [minesweeper - place your bets]

Matthew van Eerde — Sat, 10 May 2008 15:49:46 GMT

in reply to minesweeper - place your bets

DomainKeys Identified Mail is RFC 4871 [DomainKeys Identified Mail is RFC 4871]

Matthew van Eerde — Fri, 25 May 2007 19:14:18 GMT

Note the May news on dkim.org

RFC 4871

in reply to DomainKeys Identified Mail is RFC 4871

Graph theory - Secret Santa problem [Graph theory - Secret Santa problem]

Matthew van Eerde — Fri, 19 Jan 2007 20:03:02 GMT

There's a blog post on Steve Rowe's blog that I've been following, applying graph theory to the Secret Santa tradition:

Secret Santa is NP-complete

Eugen Buehler proposed a constraint that got me thinking. I couldn't come up with an answer immediately, and the post is interesting as a whole, so I thought I'd extend the audience to C9/Techoff.

The general problem (in English and Mathematician-ese:)

Given a bunch of people
(Given a set of vertices V)

... and a set of rules as to who-can-give-to-whom...
(And a set of allowable edges E... thus creating a graph (G, V, E))

... is there a fast algorithm to print out a list of who should give to whom...
(Find a subgraph S in polynomial time)

... so that...
(where)

THE HAMILTONIAN PROBLEM
a) ... the chain forms a single circle?
(S is a single cycle of degree |V|)

THE PASS-THE-HAT PROBLEM
b) ... everyone gives to someone else?
(every vertex in V has degree 2 in S)

EUGEN'S PROBLEM
c) ... everyone gives to someone else, and no-one gives to the person who gave to them?
(every vertex in V has degree 2 in S, and there are no two-cycles in S)

THE ANSWERS

a) seems to be "no", unless you can add additional constraints... for example, if every vertex has degree at least |V|/2, then you're fine. If you do find a polynomial algorithm for this, you're on the short list for a Fields medal!

b) seems to be "yes", by the pass-the-hat algorithm

c) is the interesting bit. Any takers?

in reply to Graph theory - Secret Santa problem

Bill Gates for President [Bill Gates for President]

Matthew van Eerde — Fri, 22 Dec 2006 17:35:38 GMT

Mmmm.... animated favicons...

http://www.billgatesforpresident.net/

in reply to Bill Gates for President

Math question - how much of the watermelon is water? [Math question - how much of the watermelon is water?]

Matthew van Eerde — Tue, 12 Dec 2006 18:56:42 GMT

My son got the following math problem on a homework assignment. We had a bit of fun discussing it, drawing diagrams, coming up with sanity checks, etc.

But then his teacher marked it wrong -- she pointed out that the teacher's guide had a different answer. I asked her which answer she thought was right, and she sided with the teacher's guide.

I'm trying to convince myself that my understanding of the problem is wrong -- or that the problem is ambiguous -- but I don't see it.

What do you think? Here's the problem statement:

18. A farmer raised a watermelon that weighed 20 lb. From his experience with raising watermelons, he estimated that 95% of the watermelon's weight is water.

a. How much of the watermelon is water?

b. How much of the watermelon is not water?

c. The watermelon was shipped off to market. There it sat, until it had dehydrated (lost water). If the watermelon is still 90% water, what percent of it is not water?

d. The solid part of the watermelon still weighs the same. What was the weight of the watermelon at this point?

To avoid poisoning the well, I will hold off on revealing my son's answer and the teacher's guide answer for now.

in reply to Math question - how much of the watermelon is water?

Challenge: shortest patterns that match everything, nothing [Challenge: shortest patterns that match everything, nothing]

Matthew van Eerde — Sun, 24 Sep 2006 01:01:50 GMT

I'm working on a project where I get to use XPath, .NET regular expressions, and SQL LIKE patterns. Lots of fun :)

I'm wondering what the shortest possible patterns are in each of these pattern-matching languages that either a) match every expression or b) fail to match every expression.

I've got the "match everything" expressions down for two of them, I think:

// (regex, match everything)
If the null pattern is disallowed (suppose this is javascript) then I'm not sure... /.*/ works, and perhaps /^/ is worth considering.

'%' (LIKE, match everything)

The "match nothing" cases are harder. I've come up with some to beat:

/a\bc/ (regex, match nothing)

'[]' (LIKE, match nothing)

in reply to Challenge: shortest patterns that match everything, nothing

Template inheritance question [Template inheritance question]

Matthew van Eerde — Mon, 03 Jul 2006 02:13:47 GMT

So I'm writing an XML document tree-walker that goes node-by-node, starting at the root, depth-first.
I'm writing it in C++/COM.

I have the algorithm all figured out, including a function
HRESULT HandleTree(CComPtr<IXMLDOMNode> &pNode)
which handles that node, its children, and siblings.

I also have the document itself in a CComPtr<IXMLDOMDocument> pointer.

but... I'm running into trouble trying to do this:

HRESULT HandleDocument() {
   CComPtr<IXMLDOMDocument> pDoc;
   // set pDoc...
   hr = HandleTree(pDoc); // PROBLEM LINE
   // deal with hr...
   return hr;
}

That HandleTree call doesn't work because...
although IXMLDOMDocument inherits from IXMLDOMNode...
CComPtr<IXMLDOMDocument> does not inherit from CComPtr<IXMLDOMNode> (of course.)

So far the best idea I've come up with is this:
Given the root, call .firstChild to get the first node; then call .parentNode on that to get the root back again.

I'm not particularly impressed with this idea, and I have this nagging feeling I'm missing something obvious.

If there was a .rootNode property of XMLDOMDocument objects, that would solve my problem.

Any ideas?

in reply to Template inheritance question