Notes
Contents
11/02/20
On Constructing Fractals
Staring at patterns during a pandemic.
An interesting thing for many fractals has to do with the many ways of constructing them. One thing that I haven't quite noticed is that they're iteratively created using the Kronecker product. For example, the Sierpinski Carpet can be constructed analogously:
\[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \]
So if $M$ is the Moore neighborood, $M^{\otimes n}$ will produce the Sierpinski Carpet.
Same thing with a box-fractal using the von-Neumann neighborhood.
Sooooo, what would happen if I used a $5\times 5$ matrix? With numbers other than 1? Lets say:
$$ \begin{eqnarray*} A &=& \begin{bmatrix} 1 & 2 & 1 & 2 & 1 \\ 2 & 1 & 1 & 1 & 2 \\ 1 & 1 & 3 & 1 & 1 \\ 2 & 1 & 1 & 1 & 2 \\ 1 & 2 & 1 & 2 & 1 \end{bmatrix} \qquad \textrm{then } A^{\otimes 4} = \end{eqnarray*} $$
Cool. Ok, what if the product is reduced $\textrm{ mod } N$ at each iteration?
Thats pretty neat.
09/30/20
Solving a 25-Puzzle In Less Than One Second
Code: On Github
For this variant, even IDA* can take quite a while to find a solution. Among other methods, there are pattern databases which need to be precomputed beforehand. In this case, I'm solving the puzzle in a partial order. Although its relatively straightforward to code the explicit actions needed to move a tile to it's correct slot, it didn't seem too much fun. Instead I've partitioned the search into a search for multiple subgoals (divide and conquer). An upside to this approach is that tiles in their correct states can be omitted from future searches - reducing the search space tremendously. The main drawback is that although the solution is locally optimal, it will not return a globablly optimal solution. This is in part because I use a specific set of "heuristics" to guide the search: \[ d(t_i, t_0) + d(t_i, g_i)\] which is the manhattan distance from the target tile i to the goal and the manhattan distance between the target tile and the blank tile. Since I am not explicitly guiding the search by tossing out actions that don't involve the target, this ensures that actions performed near or on the target tile are less costly.
Once the first 3 tiles are lined up, the heuristics change a bit. In order for (4,5) to get into place, they need to be adjacent to one-another and in a specific order. The goal state can only be reached by branching from a couple of very specific states so the search is guided to a target state such as the ones below.
\[ \def\g1{\color{green}} \def\g2{\color{green}} \def\g3{\color{green}} \def\b4{\color{blue}} \def\b5{\color{blue}} \def\x{\color{red}x} \begin{matrix} \g1 & \g2 & \g3 & x & x \\ \x & \x & \x & x & \b4 \\ \x & \x & \x & x & \b5 \\ \x & \x & \x & \x & \x \\ \x & \x & \x & \x & \x \end{matrix} \qquad \qquad \begin{matrix} \g1 & \g2 & \g3 & x & x \\ \x & \x & \x & \b5 & x \\ \x & \x & \x & \b4 & x \\ \x & \x & \x & \x & \x \\ \x & \x & \x & \x & \x \end{matrix} \]The $x$'s can be any tile including the blank space. The actions are restricted to altering the state of only the allowed tiles. The green entries have reached their respective goal states so no actions removing them from their goal states will be considered. The blue entries are going to be the targets of the heuristic. The red entries are in the state space that will no longer be considered valid.
To reach a partial goal state where the first row is completed, another set of "heuristics" are used:
\[ d(t_4, t_5) + d(t_4, g_4) + d(t_5, g_5) + d(t_0, t_4) + d(t_0, t_5) \]Although I haven't fully determined the admissibility of these heuristics, they do work well. The cost is calculated by the distance between tiles 4 and 5, the distance they are from the goal state, and the distance they are from the blank tile. In other words, it costs more to move 4 away from 5, move away from (4,5), and move (4,5) away from their goal states.
After the first row is completed, the process is essentially repeated until the puzzle is completely solved. For nearly all random states, this has been much less than 1s and returns a solution sequence of typically 300 actions to reach a goal state.