5 ms·

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 (r

by pge 2y ago

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!

Vampiero 2y ago
In hindsight it should have been fairly obvious that it would immediately explode into a combinatorics problem
- pge 2y ago
  yes, 30 seconds of math would have told me that, but I foolishly jumped in without doing that calculation…
  - madcaptenor 2y ago
    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.)
    - joelwilliamson 2y ago
      A month of programming can save an hour of planning.
consf 2y ago
Sometimes the unintended lessons are the most memorable
- lukan 2y ago
  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.
  - consf 2y ago
    But sometimes, watching a teacher work through a problem can actually demystify the process
    - bqmjjx0kac 2y ago
      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.
      - intelVISA 2y ago
        Sounds great, much better than rote drugery imo!
Suppafly 2y ago
>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.
_flux 2y ago
Does this also happen if you select the branches that are closest to the solved state?
sebtron 2y ago
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 https://www.jaapsch.net/puzzles/compcube.htm

by pge 2y ago

Vampiero 2y ago

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

pge 2y ago
yes, 30 seconds of math would have told me that, but I foolishly jumped in without doing that calculation…
- madcaptenor 2y ago
  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.)
  - joelwilliamson 2y ago
    A month of programming can save an hour of planning.

consf 2y ago

Sometimes the unintended lessons are the most memorable

lukan 2y ago
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.
- consf 2y ago
  But sometimes, watching a teacher work through a problem can actually demystify the process
  - bqmjjx0kac 2y ago
    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.
    - intelVISA 2y ago
      Sounds great, much better than rote drugery imo!

Suppafly 2y ago

>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.

_flux 2y ago

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

sebtron 2y ago

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 https://www.jaapsch.net/puzzles/compcube.htm