Problem-Solving
I've been spending some time learning and reviewing algorithms recently. For example graph theory (Djikstra's algorithm, Prim's algorithm), Markov chains and Bayesian inference, the Simplex algorithm, and dynamical systems.
This has become surprisingly entertaining for me, primarily because my habitual problem-solving method is not at all similar to how these kinds of problems are solved. It's hard to explain, but it seems like by playing around with all these abstract techniques, it kind of forces me to start thinking of problems more abstractly; in terms of structure, rather than semantics.
For example, suppose I'm trying to write a Minesweeper clone.
My normal problem-solving technique would be to start with the concept of a "cell", which has "neighbors", and a "nearby-bomb-count", etc. This cell concept feels like a concrete, solid thing, almost as if it could inhabit physical space.
In contrast, after reading about lots of algorithms, I want to break the problem down by starting with the concept of a "grid", which is an abstract concept but is represented visually on the screen. The representation of each cell of the grid is some function of multiple state spaces, which are then combined in a Cartesian product. For example, whether the cell is covered or uncovered is one state space, and the grid of bomb locations is another state space. Rather than combining both of those states as member variables in the same "cell" class, I think of them as being represented in completely unrelated data structures. The visual representation of a cell, then, is a function of both data structures.
I'm not sure what exactly is the qualitative difference between these two views, except that the first view seems more intuitive, while the second view seems more decoupled and extensible.
Posted on December 8, 2004 03:46 PM
More programming articles
the minesweeper example and talk of "grids" as opposed to cells reminds me a lot of some cellular automata work i was doing a while back. to implement a CA in a language like python and have it perform at all well requires this kind of approach. for my stuff, i created "bit planes" as 2-d Numeric arrays and built some infrastructure to allow me to manipulate them. the result is that you can (for the most part) specify CA rules as if they applied to a single "cell" but have them applied to an entire plane at once in a pretty efficient manner. for some example code, see: http://www2.ccnmtl.columbia.edu/cat/index.xml.
Posted by: anders at December 8, 2004 04:26 PMI think one of the differences is that the first follows directly from an object-oriented mindset, one that most programmers nowadays start out with; whereas the second is perhaps a more functional approach.
I remember going through several similar mini-revelations when I started plodding through SICP a while ago — a project that was sadly soon abandoned.
-K
Posted by: Kaushik at December 8, 2004 06:03 PMI've decided that the main difference, from my perspective, is that the second approach involves an extra level of indirection. That is:
first approach: data -> screen
second approach: data -> translation -> screen
The second approach feels better because unlike the first approach, there's room for things that aren't immediately visible.
For example, in the first approach I would have ended up storing the location of each bomb as an instance variable on the cell -- because there's no conceptual room for any data that isn't immedatiately visible. In contrast, the second approach would have no problem representing the bombs as a list of coordinates. This might be a much better representation, since you can simply omit cells that don't have a bomb on them -- which reduces the state space, and therefore simplifies the program.
Posted by: Kim at December 12, 2004 06:46 AMI want to learn about programming language C
Posted by: babuni at April 17, 2008 12:36 AM