Hacker News Reader

Comment by pge | Hacker News Reader

This reminds of the time I decided to teach one of my kids about computer programming, and suggested we write a program to solve a rubik's cube as an example (rubik's cubes were popular at her school at the time). Only after we had written a really simple depth-first search did I realize that it would take several lifetimes to run. Great lesson, but not the one I meant to impart!

View on HN

In hindsight it should have been fairly obvious that it would immediately explode into a combinatorics problem

yes, 30 seconds of math would have told me that, but I foolishly jumped in without doing that calculation…

Chemists have a saying about this: "A month in the laboratory can save an hour in the library." (The time units can vary, but yes, I did write that correctly.)

A month of programming can save an hour of planning.

If you just care about finding any solution, you can consider a multi-step approach such as Thistlethwaithe's algorithm.

If insead you want to find the shortest possible solution for any giveb configuration, that indeed is much harder! The best optimal solvers at the moment use very large pruning tables to help the brute-force search.

A nice exercise could be solving a 2x2x2 cube. That one is much more manageable.

This page is great is you want to learn more: https://www.jaapsch.net/puzzles/compcube.htm

>Only after we had written a really simple depth-first search did I realize that it would take several lifetimes to run.

I wonder if just making random moves over and over would be faster.

Sometimes the unintended lessons are the most memorable

Yes, but usually it is pretty bad for the learning experience, if the teacher stumbles and needs time for himself to figure things out. It can work out to become a deep lesson, if the student is highly motivated and the teacher good at explaining his thought processes - otherwise the student will stand aside and get bored and loose interest, as the problem is way beyond his level to understand.

But sometimes, watching a teacher work through a problem can actually demystify the process

In college, I took a discrete math course with the world's most unprepared, distractible professor. It was incredible. He would come in with nothing planned in particular, we could ask about concepts from the textbook and he would invent a problem on the spot. Then he'd run through various problem-solving strategies until one worked. I learned so much about how a mathematician thinks from this class.

This was in sharp contrast to my calculus classes where the results were basically thrown at you fully-formed. If you're lucky, you might get to walk through a proof with the professor, but you're never going to see how they mentally navigate the search space.

Sounds great, much better than rote drugery imo!

Does this also happen if you select the branches that are closest to the solved state?

Reply on news.ycombinator.com