Letters from Garcia

Ok, so in the early morning hours I think the response to your question
which I so painstakingly crafted has disappeared into the ether.. so
lets try again, Round 2:

First of all, the good news is that this program doesn't require any
fancy mucking with pointers or using malloc, so from that standpoint,
things are good. However, it is a rather ambitious program for only a
week or two experience with C, so here are some tips to get you started:

1) Don't worry about trying to find a fancy algorithm to solve the
problem, a brute force solution will work just fine. The key
observation for this is that pushing a button is a commutative operation
(ie it can be done in any order and give the same result). So, since
you don't have to worry about specific ordering, enumerating all the
possible solutions isn't too bad.

2) Try to think of the matrix as a linear bitstring (like a short or an
unsigned int). This is the easiest way to represent the problem and
allows for efficient operations to be performed.

3) Decompose the problem by thinking about what bitwise operations are
analogous to pushing a button on the board. What will this do the
neighbors?

4) Before you barrel into coding up a general solution, make sure you
have a pseudo-code solution that seems to make sense, and then test the
individual operations in code before tackling the larger solution.

5) Write some general purpose routines for doing stuff that is logically
separate (like converting from a character string of 0's and 1's to a
number and back). This is just good programming practice.

So, in summary, think about how you can represent the problem in an
efficient, easy to manipulate manner. Think about what operations are
necessary to simulate a button push. And, think about how you could
enumerate possible solutions to find an answer. Its a bit tricky, but
once you start to break it down, the answer isn't terribly hard. If you
are still having trouble, I'm sure Prof. Garcia will discuss this a bit
tomorrow in lecture, and I will make sure to talk about it in
discussion. You might also want to see my week 2 notes on bitwise
operations (http://inst.eecs.berkeley.edu/~cs61c-tb/week2_discussion.pdf)

Hope that helps, happy hacking.

Andrew

Perhaps I spoke too soon (a bit of early morning brain cloud). The
actually finding of solutions doesn't necessarily require lots of
pointers or using malloc, but they can come in handy when doing other
stuff (like sorting and storing solutions). Just wanted to make sure I
didn't put anyone on the wrong path.

Andrew

> 3) Decompose the problem by thinking about what bitwise operations are
> analogous to pushing a button on the board. What will this do the
> neighbors?

It seems like, regardless of our representation of the board, we have a good
deal of special cases we need to concern ourselves with.

void PushButton(int n) // nth position on the board
{
if We are at left edge
don't preform left toggle
preform other steps as usual
if We are at right edge
don't preform right toggle
preform other steps as usual
if We are at bottom
bottom toggle toggles up
preform other steps as usual
if We are at top
top toggle toggles down
preform other steps as usual
else
preform the usual steps
}

Where toggles are seen as doing a partiucular bitwise operator with the board
state and a number which describes the board transtion and whose sum is
uniquely determined by which button we're pushing. (I'm being vague here to
avoid giving away potential solutions, which I would imagine is bad move)

Those since the board is finite and there are only 16 such transition numbers
,it might just make sense to compute these ahead of time and store them in an
array. Which would save time tremendously in the long-run since (from what I
gather from the homework), we're not only bruteforcing a solution
(2^16 solutions possible), we're bruteforcing over our bruteforced solutions
to analyze the game (2^16 boards possible). So individal comparisons at this
level become crucially important for determining whether we'll ever get a
solution or not :).

Seems like regardless of our implementation we need to be concerned with
these special cases (which actually comprise a majority of the board), is
there a way to limit these special cases that I'm not seeing? 4 comparisons
per push while brute forcing a solution is pretty bad.

- Jason S. McGuirk6 Sep 2004

Thanks to our friends down south, here's a link to a page containing 
some great "Learning C" resources: a 45-page "Essential C : A 45-page 
summary of the C language" and "Pointers and Memory : A 31-page summary of 
pointers and memory usage". These are meant as a supplement, not 
replacement, to your K&R reading assignment this coming week.

http://cslibrary.stanford.edu/101/

Hope you're enjoying your long (hot) weekend,

Dan

p.s. please do not reply to this message