Solving a colour puzzle programmatically

[pbuk]

My intuition tells me this is entirely academic. Any tile that is not in the correct place can become the head of a chain - whether it is a half-solved chain or a new unsolved chain (since they're closed loops).

So it does not help the solver to solve the puzzle. Just be sure you are always moving at least one unsolved tile into the correct place. Which is the obvious tactic anyway.

I agree (with my highlighted amendment). Chains don't help you solve the puzzle, they just prove the minimum number of swaps you need.

 

[wle]

My intuition tells me this is entirely academic. Any tile that is not in the correct place can become the head of a chain - whether it is a half-solved chain or a new unsolved chain (since they're closed loops).

So it does not help the solver to solve the puzzle. Just be sure you are always moving at least one unsolved tile into the correct place. Which is the obvious tactic anyway.

I agree (with my highlighted amendment). Chains don't help you solve the puzzle, they just prove the minimum number of swaps you need.

If you have a bunch of items you need to rearrange and you know where they need to go then this is the optimal thing to do.

I am not sure about the terminology people are using here but if you want to rearrange objects to their correct locations (and you know what that is in advance) then you want to apply a permutation, which you can decompose into swaps of two elements, and the question is what is the minimum number of swaps needed. The answer is just the number of objects you have minus the number of cycles there are in the permutation you have to apply. (Objects that are already in the right place count as cycles of one element).

For example, let's say you have objects [B G F A E C H D] and they need to be put in order [A B C D E F G H]. This means you want to apply the permutation $$\sigma = \begin{pmatrix}
\mathrm{A} & \mathrm{B} &\mathrm{C} &\mathrm{D} &\mathrm{E} &\mathrm{F} &\mathrm{G} &\mathrm{H} \\ \mathrm{B} & \mathrm{G} &\mathrm{F} &\mathrm{A} &\mathrm{E} &\mathrm{C} &\mathrm{H} &\mathrm{D} \end{pmatrix}$$ (meaning A needs to go where B is, B needs to go where G is, C needs to go where F is, etc.). Like any permutation, this one can be decomposed into disjoint cycles; in this case $$\sigma = \begin{pmatrix} \mathrm{A} & \mathrm{B} & \mathrm{G} & \mathrm{H} & \mathrm{D} \end{pmatrix} \circ
\begin{pmatrix} \mathrm{C} & \mathrm{F} \end{pmatrix} \circ \begin{pmatrix} \mathrm{E} \end{pmatrix} \,,$$ i.e., there are three cycles with five, two, and one elements. Each cycle of $n$ elements can be done with $n - 1$ swaps, so we know that we can get all the objects in the right place with $$\text{number of elements} - \text{number of cycles} = 8 - 3 = 5$$ swaps. Furthermore, any swap that puts an object in the right final place will simply reduce the length of one of the cycles by one. For example, swapping G and H to put G in the right place just changes the first cycle to $$\begin{pmatrix} \mathrm{A} & \mathrm{B} & \mathrm{G} & \mathrm{H} & \mathrm{D} \end{pmatrix} \mapsto \begin{pmatrix} \mathrm{A} & \mathrm{B} & \mathrm{H} & \mathrm{D} \end{pmatrix} \circ \begin{pmatrix} \mathrm{G} \end{pmatrix} \,,$$ and subsequent swaps, regardless of the order in which they are done, as long as they are always putting one object in the right place, will progressively reduce the original permutation until the permutation left to apply is $$\begin{pmatrix} \mathrm{A} \end{pmatrix} \circ \begin{pmatrix} \mathrm{B} \end{pmatrix} \circ \begin{pmatrix} \mathrm{C} \end{pmatrix} \circ \begin{pmatrix} \mathrm{D} \end{pmatrix} \circ \begin{pmatrix} \mathrm{E} \end{pmatrix} \circ \begin{pmatrix} \mathrm{F} \end{pmatrix} \circ \begin{pmatrix} \mathrm{G} \end{pmatrix} \circ \begin{pmatrix} \mathrm{H} \end{pmatrix} \,,$$ i.e., nothing.

(Actually, the above also shows that swapping any objects in the same cycle will also work in the same number of steps, since this breaks a cycle at each step. E.g., if we swapped A and G in the original list, which doesn't put either object in the right place, it would still break the first cycle into $$\begin{pmatrix} \mathrm{A} & \mathrm{B} & \mathrm{G} & \mathrm{H} & \mathrm{D} \end{pmatrix} \mapsto \begin{pmatrix} \mathrm{A} & \mathrm{B} \end{pmatrix} \circ \begin{pmatrix} \mathrm{D} & \mathrm{G} & \mathrm{H} \end{pmatrix} \,.$$ But this isn't very useful since its the objects that are adjacent to each other in a cycle that are the easiest to determine share a cycle.)

Implementation (for fun):

(defun rearrange (objects target &key (test #'eql))
  (setf objects (copy-seq objects))
  (format t "   ~s~%" objects)
  (let ((count 0)) 
    (dotimes (k (length target))
      (let ((p (position (aref target k) objects :test test)))
        (unless (= k p)
          (rotatef (aref objects k) (aref objects p))
          (format t "=> ~s~%" objects)
          (incf count))))
    count))

CL-USER> (rearrange #(b g f a e c h d)
                    #(a b c d e f g h))
   #(B G F A E C H D)
=> #(A G F B E C H D)
=> #(A B F G E C H D)
=> #(A B C G E F H D)
=> #(A B C D E F H G)
=> #(A B C D E F G H)
5

 

[DaveC426913]

That's just what I was about to say.

 

[Baluncore]

Furthermore, any swap that puts an object in the right final place will simply reduce the length of one of the cycles by one.

A swap between cycles is then precluded because it cannot put any object in the correct place.
It also reduces the economy by joining the two cycles, making one cycle.

 

[DrDu]

Interesting. I am playing around with ore or reflected light microscopy and the colours of ores in reflected light are often very faint and, as in this game, the appearance depends on the surrounding material. However, apparently, as with sound, there seem to exist people who have kind of an "absolute" colour vision, like persons having an absolute pitch.

 

[Bruzote]

Yah, it's a straight sort. The trickiness lies in the fact that the only criteria is colour, and the colour gradients get more and more subtle.

It is confounded by contextual perception - eg. a yellow tile will look peach or green depending on context. And you have no way to compare them before committing to a swap.

eg: these discs are both the same yellow:
View attachment 278997

This is SO unfair to people with color-deficient vision. :-b Well, I suppose I can at least be grateful for having vision. And a computer and a safe home to use it. And...

 

[DaveC426913]

This is SO unfair to people with color-deficient vision. :-b

It is! SO unfair.

This app I downloaded for free for my own amusement should be grey-scale only, to accommodate those with colour deficiencies.

Likewise, football and other sports are SO unfair for those of us with 50-something dad-bods. To be more fair, they should make the games less about athleticism and more about cerebral agility.

:-b

 

[DaveC426913]

So, one wants to be careful what one asks for.

The game developers have released a version 2 of I Love Hue (Too)!

This version provides a 'minimum possible moves' stat for every game.

Which is great - exactly what I wanted.

Except what's happened is it's just raised the bar for me. Rather than setting my personal bar at 'beating the average' it's now 'hitting the minimum possible moves'. Which is harder.

This game is designed to be Zen-calming, but it just gets more stressful.