views:

1049

answers:

10

I'm practicing for the upcoming ACM programming competition in a week and I've gotten stumped on this programming problem.

The problem is as follows:


You have a puzzle consisting of a square grid of size 4. Each grid square holds a single coin; each coin is showing either heads (H) and tails (T). One such puzzle is shown here:

H H H H
T T T T
H T H T
T T H T

Any coin that is current showing Tails (T) can be flipped to Heads (H). However, any time we flip a coin, we must also flip the adjacent coins direct above, below and to the left and right in the same row. Thus if we flip the second coin in the second row we must also flip 4 other coins, giving us this arrangment (coins that changed are shown in bold).

H T H H
H H H T
H H H T
T T H T

If a coin is at the edge of the puzzle, so there is no coin on one side or the other, then we flip fewer coins. We do not "wrap around" to the other side. For example, if we flipped the bottom right coin of the arragnement above we would get:

H T H H
H H H T
H H H H
T T T H

Note: Only coins showing (T) tails can be selected for flipping. However, anytime we flip such a coin, adjacent coins are also flipped, regardless of their state.

The goal of the puzzle is to have all coins show heads. While it is possible for some arragnements to not have solutions, all the problems given will have solutions. The answer we are looking for is, for any given 4x4 grid of coins what is the least number of flips in order to make the grid entirely heads.

For Example the grid:
H T H H
T T T H
H T H T
H H T T

The answer to this grid is: 2 flips.


What I have done so far:

I'm storing our grids as two-dimensional array of booleans. Heads = true, tails = false. I have a flip(int row, int col) method that will flip the adjacent coins according the rules above and I have a isSolved() method that will determine if the puzzle is in a solved state (all heads). So we have our "mechanics" in place.

The part we are having problems with is how should we loop through, going an the least amount of times deep?

+5  A: 

EDIT: I hadn't noticed that you can't use a coin as the primary move unless it's showing tails. That does indeed make order important. I'll leave this answer here, but look into writing another one as well.

No pseudo-code here, but think about this: can you ever imagine yourself flipping a coin twice? What would be the effect?

Alternative, write down some arbitrary board (literally, write it down). Set up some real world coins, and pick two arbitrary ones, X and Y. Do an "X flip", then a "Y flip" then another "X flip". Write down the result. Now reset the board to the starting version, and just do a "Y flip". Compare the results, and think about what's happened. Try it a few times, sometimes with X and Y close together, sometimes not. Become confident in your conclusion.

That line of thought should lead you to a way of determining a finite set of possible solutions. You can test all of them fairly easily.

Hope this hint wasn't too blatant - I'll keep an eye on this question to see if you need more help. It's a nice puzzle.

As for recursion: you could use recursion. Personally, I wouldn't in this case.

EDIT: Actually, on second thoughts I probably would use recursion. It could make life a lot simpler.


Okay, perhaps that wasn't obvious enough. Let's label the coins A-P, like this:

ABCD
EFGH
IJKL
MNOP

Flipping F will always involve the following coins changing state: BEFGJ.

Flipping J will always involve the following coins changing state: FIJKN.

What happens if you flip a coin twice? The two flips cancel each other out, no matter what other flips occur.

In other words, flipping F and then J is the same as flipping J and then F. Flipping F and then J and then F again is the same as just flipping J to start with.

So any solution isn't really a path of "flip A then F then J" - it's "flip <these coins>; don't flip <these coins>". (It's unfortunate that the word "flip" is used for both the primary coin to flip and the secondary coins which change state for a particular move, but never mind - hopefully it's clear what I mean.)

Each coin will either be used as a primary move or not, 0 or 1. There are 16 coins, so 2^16 possibilities. So 0 might represent "don't do anything"; 1 might represent "just A"; 2 might represent "just B"; 3 "A and B" etc.

Test each combination. If (somehow) there's more than one solution, count the number of bits in each solution to find the least number.

Implementation hint: the "current state" can be represented as a 16 bit number as well. Using a particular coin as a primary move will always XOR the current state with a fixed number (for that coin). This makes it really easy to work out the effect of any particular combination of moves.


Okay, here's the solution in C#. It shows how many moves were required for each solution it finds, but it doesn't keep track of which moves those were, or what the least number of moves is. That's a SMOP :)

The input is a list of which coins are showing tails to start with - so for the example in the question, you'd start the program with an argument of "BEFGJLOP". Code:

using System;

public class CoinFlip
{
    // All ints could really be ushorts, but ints are easier 
    // to work with
    static readonly int[] MoveTransitions = CalculateMoveTransitions();

    static int[] CalculateMoveTransitions()
    {
        int[] ret = new int[16];
        for (int i=0; i < 16; i++)
        {
            int row = i / 4;
            int col = i % 4;
            ret[i] = PositionToBit(row, col) +
                PositionToBit(row-1, col) +
                PositionToBit(row+1, col) +
                PositionToBit(row, col-1) +
                PositionToBit(row, col+1);
        }
        return ret;
    }

    static int PositionToBit(int row, int col)
    {
        if (row < 0 || row > 3 || col < 0 || col > 3)
        {
            // Makes edge detection easier
            return 0;
        }
        return 1 << (row * 4 + col);
    }

    static void Main(string[] args)
    {
        int initial = 0;
        foreach (char c in args[0])
        {
            initial += 1 << (c-'A');
        }
        Console.WriteLine("Initial = {0}", initial);
        ChangeState(initial, 0, 0);
    }

    static void ChangeState(int current, int nextCoin, int currentFlips)
    {
        // Reached the end. Success?
        if (nextCoin == 16)
        {
            if (current == 0)
            {
                // More work required if we want to display the solution :)
                Console.WriteLine("Found solution with {0} flips", currentFlips);
            }
        }
        else
        {
            // Don't flip this coin
            ChangeState(current, nextCoin+1, currentFlips);
            // Or do...
            ChangeState(current ^ MoveTransitions[nextCoin], nextCoin+1, currentFlips+1);
        }
    }
}
Jon Skeet
Well, I state in my problem that we've considered flipping a coin once, checking if it is "Solved", if not.. flipping it back. But thigns get confusing when you are thinking about it taking several layers of flipping inorder to reach a solved state.
Simucal
Well, suppose you flip coin X, then coin Y, then coin X again. Compare the result with just flipping coin Y and never touching X...
Jon Skeet
right, but then we will be flipping all of the adjacent coins to Y also, so even though we have restored the adjacent coins of X to their original state except for Y, we have effected the coins surrounding Y. Right?
Simucal
I don't think I've quite made myself clear - but 300 characters may not be enough. I'll edit my answer.
Jon Skeet
Okay, I'll get more blatant :)
Jon Skeet
You should post your answer Jon in C# that you said you had worked out, I'd be interested to see it.
Simucal
+8  A: 

Your puzzle is a classic Breadth-First Search candidate. This is because you're looking for a solution with the fewest possible 'moves'.

If you knew the number of moves to the goal, then that would be ideal for a Depth-First Search.

Those Wikipedia articles contain plenty of information about the way the searches work, they even contain code samples in several languages.

Either search can be recursive, if you're sure you won't run out of stack space.

Lee Kowalkowski
I'm not sure I'd particularly call this a breadth-first search candidate. I view it as a simple brute force candidate - it's easy to check *all* solutions, and I'm not even sure whether my implementation would count as "breadth first" or "depth first". Arguably depth first..
Jon Skeet
Any model with states and transitions can be treated as a graph problem. At the top of the graph is the starting position. All possible moves can be child nodes. Breadth first makes is easier to remove duplicate states from the search.Blimey, you don't get many characters for a comment, do you?
Lee Kowalkowski
@Lee: No, you don't get many characters :) I would agree with your analysis if it were really transitional in the normal sense. But think about what effect it has to do move X then move Y vs move Y then move X in this particular case.
Jon Skeet
@Jon: Does the fact that XY results in the same state as YX mean this is not transitional? Wouldn't you just have node 1 referencing nodes 1.1 and 1.2, node 1.1 would reference node 1.1.1, and node 1.2.1 could either be disarded as a duplicate of 1.1.1 or 1.2 could reference 1.1.1 directly?
Lee Kowalkowski
It means that there's little point in looking at it as a tree - it makes more sense to look at any one attempt as a *set* of flips instead of a *path* of flips. IMO, anyway :) Working out all possible sets is easier than working out all possible paths.
Jon Skeet
Can you explain how modeling this problem as a graph with the transitions would be non-trival compared to straight bruteforce?
Simucal
Imagine starting at one of 16 places, then choosing another of 16 options, then another, etc. You very, very rapidly have a large set of paths to consider. The straight bruteforce consideration of sets of coins has a small number of possible solutions.
Jon Skeet
@Jon: I see what you mean about a set of flips compared to a path of flips. But we're still interested in all sets that consist of 1 move before we consider sets comprised of 2. If you start at 1 of 16 the next is 1 of 15, not 16. So if it's doable in 1 move, there are only 16 nodes to search.
Lee Kowalkowski
(Cont...) Sorry, just noticed only Tails can ever be selected (How did I miss that?), So it would go from 1 of 16 to 1 of 11. Surely this makes order important? A brute force solution might present a solution that's not possible to perform, how would it be prevented from suggesting invalid moves?
Lee Kowalkowski
@Simucal: Argh! I'll have to up-vote your question, because now I'm really interested to know too! Still in favour of modelling as a graph currently, because you can validate your solution has adhered to the boundaries set out by the rules, trivial or not.
Lee Kowalkowski
@Lee: Now that only tails can be selected, it's definitely a breadth-first job. My current depth-first is taking way too long :(
Jon Skeet
@Jon: Thanks, I knew it, but the more it was challenged, the less I was sure! You can tune the algorithm to try the tails with the most neighbouring tails first, so there are still some heuristics that can be applied. This would find the solution practically straight away in the author's last grid
Lee Kowalkowski
@Lee: Fortunately you don't really need heuristics to solve it in a blink of an eye, when you go breadth-first. I prefer simple to clever wherever possible :)
Jon Skeet
(That's assuming a reasonably small problem, of course.)
Jon Skeet
+2  A: 

The grid, read in row-major order, is nothing more than a 16 bit integer. Both the grid given by the problem and the 16 possible moves (or "generators") can be stored as 16 bit integers, thus the problems amounts to find the least possible number of generators which, summed by means of bitwise XOR, gives the grid itself as the result. I wonder if there's a smarter alternative than trying all the 65536 possibilities.

EDIT: Indeed there is a convenient way to do bruteforcing. You can try all the 1-move patterns, then all the 2-moves patterns, and so on. When a n-moves pattern matches the grid, you can stop, exhibit the winning pattern and say that the solution requires at least n moves. Enumeration of all the n-moves patterns is a recursive problem.

EDIT2: You can bruteforce with something along the lines of the following (probably buggy) recursive pseudocode:

// Tries all the n bit patterns with k bits set to 1
tryAllPatterns(unsigned short n, unsigned short k, unsigned short commonAddend=0)
{
    if(n == 0)
     tryPattern(commonAddend);
    else
    {
     // All the patterns that have the n-th bit set to 1 and k-1 bits
     // set to 1 in the remaining
     tryAllPatterns(n-1, k-1, (2^(n-1) xor commonAddend) );

     // All the patterns that have the n-th bit set to 0 and k bits
     // set to 1 in the remaining
     tryAllPatterns(n-1, k,   commonAddend );
    }
}
Federico Ramponi
Can you elaborate on the structure of a such a bruteforcing method? I'm really looking for at least some pseudo-code to help visualize it. What you are saying with your second method is what I already stated in my problem I wanted to do. I need a little more help getting there
Simucal
My idea of bruteforcing is slightly simpler: there are 65536 possible approaches, easily mapped from numbers 0-65535. I don't *think* there can ever be more than one solution (which only uses each move 0 or 1 time) to any problem, but if there were, determining the number of bits is simple :)
Jon Skeet
If he wants to compete in an ACM contest, probably he is searching for elegant/fast/beautiful solutions, and mine are only suggestions.
Federico Ramponi
Of course, if I wanted to solve the problem in a quick way, I would go for the straight bruteforce one (for i = 0 to 65535 do...) :D
Federico Ramponi
I view the simplest solution as the most elegant, when it's obviously going to run quickly anyway :)
Jon Skeet
And I guess that even my good old pentium4 would solve it in fractions of a second...
Federico Ramponi
So they tell me, "premature optimization is the root of all evil". ARGH! :D
Federico Ramponi
I was wrong in comment 2 above - there can be more than one solution.
Jon Skeet
Jon, there can be many solutions and there can also be NO solutions for a given board.. but my problems will never be ones with no solutions.
Simucal
Yup, I've got that now. Full implementation if you want it. 68 lines of C# including some comments...
Jon Skeet
Simucal: You can write a program to find the shortest solution. I bet that the same program, with minimal changes, can also decide whether solutions exist or not.
Federico Ramponi
Jon, can you post your solution in c#? I'll mark it as solved if it works with my sample data! Thanks!
Simucal
@Simucal: Posted :)
Jon Skeet
+1  A: 

To elaborate on Federico's suggestion, the problem is about finding a set of the 16 generators that xor'ed together gives the starting position.

But if we consider each generator as a vector of integers modulo 2, this becomes finding a linear combination of vectors, that equal the starting position. Solving this should just be a matter of gaussian elimination (mod 2).

EDIT: After thinking a bit more, I think this would work: Build a binary matrix G of all the generators, and let s be the starting state. We are looking for vectors x satisfying Gx=s (mod 2). After doing gaussian elimination, we either end up with such a vector x or we find that there are no solutions.

The problem is then to find the vector y such that Gy = 0 and x^y has as few bits set as possible, and I think the easiest way to find this would be to try all such y. Since they only depend on G, they can be precomputed.

I admit that a brute-force search would be a lot easier to implement, though. =)

CAdaker
A: 

It's a finite state machine, where each "state" is the 16 bit integer corresponding the the value of each coin.

Each state has 16 outbound transitions, corresponding to the state after you flip each coin.

Once you've mapped out all the states and transitions, you have to find the shortest path in the graph from your beginning state to state 1111 1111 1111 1111,

JohnMcG
Considering it as paths of transitions will take a very long time compared with considering it as sets. There's a useful property here - see my other comments :)
Jon Skeet
+3  A: 

I would suggest a breadth first search, as someone else already mentioned.

The big secret here is to have multiple copies of the game board. Don't think of "the board."

I suggest creating a data structure that contains a representation of a board, and an ordered list of moves that got to that board from the starting position. A move is the coordinates of the center coin in a set of flips. I'll call an instance of this data structure a "state" below.

My basic algorithm would look something like this:

Create a queue.
Create a state that contains the start position and an empty list of moves.
Put this state into the queue.
Loop forever:
    Pull first state off of queue.
    For each coin showing tails on the board:
        Create a new state by flipping that coin and the appropriate others around it.
        Add the coordinates of that coin to the list of moves in the new state.
        If the new state shows all heads:
            Rejoice, you are done.
        Push the new state into the end of the queue.

If you like, you could add a limit to the length of the queue or the length of move lists, to pick a place to give up. You could also keep track of boards that you have already seen in order to detect loops. If the queue empties and you haven't found any solutions, then none exist.

Also, a few of the comments already made seem to ignore the fact that the problem only allows coins that show tails to be in the middle of a move. This means that order very much does matter. If the first move flips a coin from heads to tails, then that coin can be the center of the second move, but it could not have been the center of the first move. Similarly, if the first move flips a coin from tails to heads, then that coin cannot be the center of the second move, even though it could have been the center of the first move.

Glomek
Ah, that's interesting... yes, I hadn't noticed that restriction at all - well spotted.
Jon Skeet
+2  A: 

Okay, here's an answer now that I've read the rules properly :)

It's a breadth-first search using a queue of states and the moves taken to get there. It doesn't make any attempt to prevent cycles, but you have to specify a maximum number of iterations to try, so it can't go on forever.

This implementation creates a lot of strings - an immutable linked list of moves would be neater on this front, but I don't have time for that right now.

using System;
using System.Collections.Generic;

public class CoinFlip
{
    struct Position
    {
        readonly string moves;
        readonly int state;

        public Position(string moves, int state)
        {
            this.moves = moves;
            this.state = state;
        }

        public string Moves { get { return moves; } } 
        public int State { get { return state; } }

        public IEnumerable<Position> GetNextPositions()
        {
            for (int move = 0; move < 16; move++)
            {
                if ((state & (1 << move)) == 0)
                {                    
                    continue; // Not allowed - it's already heads
                }
                int newState = state ^ MoveTransitions[move];
                yield return new Position(moves + (char)(move+'A'), newState);
            }
        }
    }

    // All ints could really be ushorts, but ints are easier 
    // to work with
    static readonly int[] MoveTransitions = CalculateMoveTransitions();

    static int[] CalculateMoveTransitions()
    {
        int[] ret = new int[16];
        for (int i=0; i < 16; i++)
        {
            int row = i / 4;
            int col = i % 4;
            ret[i] = PositionToBit(row, col) +
                PositionToBit(row-1, col) +
                PositionToBit(row+1, col) +
                PositionToBit(row, col-1) +
                PositionToBit(row, col+1);
        }
        return ret;
    }

    static int PositionToBit(int row, int col)
    {
        if (row < 0 || row > 3 || col < 0 || col > 3)
        {
            return 0;
        }
        return 1 << (row * 4 + col);
    }

    static void Main(string[] args)
    {
        int initial = 0;
        foreach (char c in args[0])
        {
            initial += 1 << (c-'A');
        }

        int maxDepth = int.Parse(args[1]);

        Queue<Position> queue = new Queue<Position>();
        queue.Enqueue(new Position("", initial));

        while (queue.Count != 0)
        {
            Position current = queue.Dequeue();
            if (current.State == 0)
            {
                Console.WriteLine("Found solution in {0} moves: {1}",
                                  current.Moves.Length, current.Moves);
                return;
            }
            if (current.Moves.Length == maxDepth)
            {
                continue;
            }
            // Shame Queue<T> doesn't have EnqueueRange :(
            foreach (Position nextPosition in current.GetNextPositions())
            {
                queue.Enqueue(nextPosition);
            }
        }
        Console.WriteLine("No solutions");
    }
}
Jon Skeet
A: 

If you are practicing for the ACM, I would consider this puzzle also for non-trivial boards, say 1000x1000. Brute force / greedy may still work, but be careful to avoid exponential blow-up.

Ron
A: 

I sat down and attempted my own solution to this problem (based on the help I received in this thread). I'm using a 2d array of booleans, so it isn't as nice as the people using 16bit integers with bit manipulation.

In any case, here is my solution in Java:

import java.util.*;

class Node
{
    public boolean[][] Value;
    public Node Parent;

    public Node (boolean[][] value, Node parent)
    {
        this.Value = value;
        this.Parent = parent;
    }
}


public class CoinFlip
{
    public static void main(String[] args)
    {
        boolean[][] startState =  {{true, false, true, true},
                                   {false, false, false, true},
                                   {true, false, true, false},
                                   {true, true, false, false}};


        List<boolean[][]> solutionPath = search(startState);

        System.out.println("Solution Depth: " + solutionPath.size());
        for(int i = 0; i < solutionPath.size(); i++)
        {
            System.out.println("Transition " + (i+1) + ":");
            print2DArray(solutionPath.get(i));
        }

    }

    public static List<boolean[][]> search(boolean[][] startState)
    {
        Queue<Node> Open = new LinkedList<Node>();
        Queue<Node> Closed = new LinkedList<Node>();

        Node StartNode = new Node(startState, null);
        Open.add(StartNode);

          while(!Open.isEmpty())
          {
              Node nextState = Open.remove();

              System.out.println("Considering: ");
              print2DArray(nextState.Value);

              if (isComplete(nextState.Value))
              {
                  System.out.println("Solution Found!");
                  return constructPath(nextState);
              }
              else
              {
                List<Node> children = generateChildren(nextState);
                Closed.add(nextState);

                for(Node child : children)
                {
                 if (!Open.contains(child))
                  Open.add(child);
                }
              }

          }

          return new ArrayList<boolean[][]>();

    }

    public static List<boolean[][]> constructPath(Node node)
    {
        List<boolean[][]> solutionPath = new ArrayList<boolean[][]>();

        while(node.Parent != null)
        {
         solutionPath.add(node.Value);
         node = node.Parent;
        }
        Collections.reverse(solutionPath);

        return solutionPath;
    }

    public static List<Node> generateChildren(Node parent)
    {
        System.out.println("Generating Children...");
        List<Node> children = new ArrayList<Node>();

        boolean[][] coinState = parent.Value;

        for(int i = 0; i < coinState.length; i++)
        {
            for(int j = 0; j < coinState[i].length; j++)
            {
             if (!coinState[i][j])
             {
              boolean[][] child = arrayDeepCopy(coinState);
              flip(child, i, j);
              children.add(new Node(child, parent));

             }
            }
        }

        return children;
    }

    public static boolean[][] arrayDeepCopy(boolean[][] original)
    {
         boolean[][] r = new boolean[original.length][original[0].length];
         for(int i=0; i < original.length; i++)
                 for (int j=0; j < original[0].length; j++)
                       r[i][j] = original[i][j];

         return r;
    }

    public static void flip(boolean[][] grid, int i, int j)
    {
        //System.out.println("Flip("+i+","+j+")");
        // if (i,j) is on the grid, and it is tails
        if ((i >= 0 && i < grid.length) && (j >= 0 && j <= grid[i].length))
        {
            // flip (i,j)
            grid[i][j] = !grid[i][j];
            // flip 1 to the right
            if (i+1 >= 0 && i+1 < grid.length) grid[i+1][j] = !grid[i+1][j];
            // flip 1 down
            if (j+1 >= 0 && j+1 < grid[i].length) grid[i][j+1] = !grid[i][j+1];
            // flip 1 to the left
            if (i-1 >= 0 && i-1 < grid.length) grid[i-1][j] = !grid[i-1][j];
            // flip 1 up
            if (j-1 >= 0 && j-1 < grid[i].length) grid[i][j-1] = !grid[i][j-1];
        }
    }

    public static boolean isComplete(boolean[][] coins)
    {
        boolean complete = true;

        for(int i = 0; i < coins.length; i++)
        {
            for(int j = 0; j < coins[i].length; j++)
            {
             if (coins[i][j] == false) complete = false; 
            }

        }
        return complete;
    }

    public static void print2DArray(boolean[][] array) 
    {
        for (int row=0; row < array.length; row++) 
        {
         for (int col=0; col < array[row].length; col++)
         {
             System.out.print((array[row][col] ? "H" : "T") + " ");
            }
            System.out.println();
        }
    }

}
Simucal
+1  A: 

The is the classic "Lights Out" problem. There is actually an easy O(2^N) brute force solution, where N is either the width or the height, whichever is smaller.

Let's assume the following works on the width, since you can transpose it.

One observation is that you don't need to press the same button twice - it just cancels out.

The key concept is just that you only need to determine if you want to press the button for each item on the first row. Every other button press is uniquely determined by one thing - whether the light above the considered button is on. If you're looking at cell (x,y), and cell (x,y-1) is on, there's only one way to turn it off, by pressing (x,y). Iterate through the rows from top to bottom and if there are no lights left on at the end, you have a solution there. You can then take the min of all the tries.

Larry

related questions