5 ms·
> It turns out that this is exactly the problem I was trying to solve. Imagine my Secret Santa problem as a graph where each person is a node and there are e
by Jtsummers 11y ago
> It turns out that this is exactly the problem I was trying to solve. Imagine my Secret Santa problem as a graph where each person is a node and there are edges between all nodes that are not blacklisted. In this view of the problem, I'm trying to find a path around the graph, [visiting] each node once.
This is one of the fun things, to me, about having a background/interest in the more theoretical sides of CS/mathematics as a programmer. The day you realize that half the problems you're working on are really already solved (or related to) problems on graphs or some other structure, and if you reorganize your models around this you can get a much cleaner implementation. Come up with a representation of your problem using a graph, run a well-known algorithm from a graph library, solution found (hopefully before Christmas).
This is the one major gap I've noticed between professional programmers with a CS academic background versus those from an engineering academic background. The gap is easily closed, but the engineers lack the random bits of extra discrete maths or CS theory to make these kind of connections. OTOH, I'm sure programmers from an engineering background can easily say the same from the other side using some other set of knowledge.
- thaumasiotes 11y agoThe moral drawn from this particular case is a little less inspiring. The author was mistaken in drawing equivalence between his problem and the NP-complete one, and published a conclusion which was factually wrong. The mistake of equivalence is pointed out in the (years-old) comments, but no one knows whether it's significant. Meanwhile, graph theory was aware of a polynomial-time solution to the guy's actual problem all along.