Problema de ACM: Coin-Flipping, ayúdame a identificar el tipo de problema que es

Question

Estoy practicando para la próxima competencia de programación de ACM en una semana y me he quedado perplejo con este problema de programación.

El problema es el siguiente:

---

Tienes un puzzle que consiste en una rejilla cuadrada de tamaño 4. Cada cuadrado de la cuadrícula tiene una sola moneda; cada moneda muestra cabezas (H) y colas (T). Uno de tales rompecabezas se muestra aquí:

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

Cualquier moneda que es actual, mostrando las colas (T) puede ser volteado para Jefes (H). Sin embargo, cada vez que volteamos una moneda, también debemos voltear las monedas adyacentes directamente arriba, abajo y hacia la izquierda y derecha en la misma fila. Por lo tanto, si volteamos la segunda moneda en la segunda fila también debemos voltear otras 4 monedas, dándonos este arreglo (las monedas que cambiaron se muestran en negrita).

H T HH
HHH T
H H HT
TTHT

Si una moneda está en el borde del rompecabezas, para que no haya monedas en un lado o en el otro, entonces tiramos menos monedas. No nos "envolvemos" al otro lado. Por ejemplo, si nos volteado la moneda inferior derecha de la arragnement anterior obtendríamos:

HtHh
HHHT
HHH H
TT TH

Nota : Solo se pueden seleccionar monedas que muestren (T) colas para voltear. Sin embargo, cada vez que volteamos una moneda de este tipo, las monedas adyacentes también se voltean, independientemente de su estado.

El objetivo del rompecabezas es que todas las monedas muestren cabezas. Si bien es posible que algunos arreglos no tengan soluciones, todos los problemas brindados tendrán soluciones. La respuesta que estamos buscando es, para cualquier cuadrícula de monedas 4x4 determinada, cuál es el menor número de volteos para hacer que la grilla se dirija por completo.

Por ejemplo, la cuadrícula:
H T H H
T T T H
H T H T
H H T T

La respuesta a esta rejilla es: 2 lanzamientos.

---

Lo que he hecho hasta ahora:

Estoy almacenando nuestras redes como matriz bidimensional de booleanos. Cabezas = verdadero, cruz = falso. Tengo flip (int fila, int col) método que invertirá las monedas adyacentes según las reglas anteriores y tengo isSolved() método que determinará si el rompecabezas está en un estado resuelto (todas las cabezas) . Entonces tenemos nuestra "mecánica" en su lugar.

La parte con la que estamos teniendo problemas es ¿cómo debemos atravesarla, yendo un mínimo de veces?

Answer 1

Su rompecabezas es un clásico Breadth-First Search candidato. Esto se debe a que está buscando una solución con el menor número posible de 'movimientos'.

Si supiera el número de movimientos hacia la meta, entonces sería ideal para un Depth-First Search.

Los artículos de Wikipedia contienen mucha información sobre el funcionamiento de las búsquedas, incluso contienen ejemplos de código en varios idiomas.

Cualquiera de las búsquedas puede ser recursiva, si está seguro de que no se quedará sin espacio en la pila.

Answer 2

EDITAR: No me había dado cuenta de que no se puede usar una moneda como movimiento principal a menos que muestre las colas. Eso sí que hace que el orden sea importante. Dejaré esta respuesta aquí, pero buscaré escribir otra también.

No hay pseudocódigo aquí, pero piense en esto: ¿alguna vez puede imaginarse tirar una moneda dos veces? ¿Cuál sería el efecto?

Alternativa, anote algún tablero arbitrario (literalmente, anótelo). Configure algunas monedas del mundo real, y elija dos arbitrarias, X e Y. Haga un "X flip", luego un "Y flip" y luego otro "X flip". Escriba el resultado. Ahora restablece la placa a la versión de inicio, y simplemente haz una "Y flip". Compare los resultados y piense en lo que sucedió. Pruébalo algunas veces, a veces con X e Y muy juntos, a veces no. Confía en tu conclusión.

Esa línea de pensamiento debería llevarlo a una forma de determinar un conjunto finito de posibles soluciones. Puedes probarlos con bastante facilidad.

Espero que esta sugerencia no fuera demasiado descarada. Estaré pendiente de esta pregunta para ver si necesitas más ayuda. Es un buen rompecabezas.

En cuanto a la recursión: podría utilizar recursion. Personalmente, no lo haría en este caso.

EDITAR: En realidad, pensándolo bien, probablemente usaría recursion. Podría hacer la vida mucho más simple.

---

Bien, quizás eso no fue lo suficientemente obvio. Vamos a etiquetar las monedas A-P, como este:

ABCD 
EFGH 
IJKL 
MNOP 

voltear F siempre implicará las siguientes monedas de cambio de estado: BEFGJ.

Voltear J siempre implicará las siguientes monedas cambiando de estado: FIJKN.

¿Qué sucede si das vuelta una moneda dos veces? Los dos lanzamientos se cancelan entre sí, sin importar qué otros lanzamientos se produzcan.

En otras palabras, voltear F y luego J es lo mismo que mover J y luego F. Voltear F y luego J y luego F nuevamente es lo mismo que simplemente voltear J para comenzar.

Así que cualquier solución no es realmente una ruta de "voltear A, luego F y luego J" - es "voltear < estas monedas>; no voltear < estas monedas>".(Es desafortunado que la palabra "voltear" se use tanto para la moneda principal como para las monedas secundarias que cambian de estado para un movimiento en particular, pero no importa, espero que quede claro lo que quiero decir).

Cada moneda ser usado como un movimiento primario o no, 0 o 1. Hay 16 monedas, entonces 2^16 posibilidades. Entonces 0 podría representar "no hacer nada"; 1 podría representar "solo A"; 2 podría representar "solo B"; 3 "A y B", etc.

Pruebe cada combinación. Si (de alguna manera) hay más de una solución, cuente el número de bits en cada solución para encontrar el menor número.

Indicación de implementación: el "estado actual" se puede representar también como un número de 16 bits. Usar una moneda en particular como movimiento primario siempre XOR el estado actual con un número fijo (para esa moneda). Esto hace que sea realmente fácil calcular el efecto de cualquier combinación particular de movimientos.

---

Bien, aquí está la solución en C#. Muestra cuántos movimientos se necesitaron para cada solución que encuentra, pero no realiza un seguimiento de qué movimientos fueron o cuál es el menor número de movimientos. Eso es un SMOP :)

La entrada es una lista de las monedas que muestran las colas para empezar, por lo que para el ejemplo en la pregunta, iniciarías el programa con un argumento de "BEFGJLOP". Código:

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); 
     } 
    } 
} 

Answer 3

La cuadrícula, leída en orden de fila mayor, no es más que un entero de 16 bits. Tanto la cuadrícula dada por el problema como los 16 movimientos posibles (o "generadores") se pueden almacenar como enteros de 16 bits, por lo tanto, el problema es encontrar el menor número posible de generadores que, sumados mediante bit XOR, da la grilla misma como resultado. Me pregunto si existe una alternativa más inteligente que intentar todas las 65536 posibilidades.

EDITAR: De hecho, hay una manera conveniente de hacer fuerza bruta. Puede probar todos los patrones de 1 movimiento, luego todos los patrones de 2 movimientos, y así sucesivamente. Cuando un patrón de n-moves coincide con la grilla, puede detenerse, exhibir el patrón ganador y decir que la solución requiere al menos n movimientos. La enumeración de todos los patrones de n-moves es un problema recursivo.

Edit2: Puede ataque de fuerza bruta con algo en la línea de lo siguiente (probablemente con errores) pseudocódigo recursiva:

// 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); 
    } 
} 

Answer 4

Para más detalles sobre la sugerencia de Federico, el problema consiste en encontrar un conjunto de los 16 generadores que XOR 'ed juntos da la posición inicial.

Pero si consideramos cada generador como un vector de enteros módulo 2, esto se convierte en encontrar una combinación lineal de vectores, que iguale la posición inicial. Resolver esto solo debería ser una cuestión de eliminación gaussiana (mod 2).

EDIT: Después de pensar un poco más, creo que esto funcionaría: Construir una matriz binaria G de todos los generadores, y vamos a s sea el estado inicial. Estamos buscando vectores x satisfaciendo Gx=s (mod 2). Después de hacer la eliminación gaussiana, o bien terminamos con un vector x o encontramos que no hay soluciones.

El problema consiste entonces en encontrar el vector y tal que Gy = 0 y x^y tiene el menor número de bits puestos como sea posible, y creo que la forma más fácil de encontrar este sería tratar todos esos y. Dado que solo dependen de G, se pueden precalcular.

Admito que una búsqueda de fuerza bruta sería mucho más fácil de implementar, sin embargo. =)

Answer 5

Es un finite state machine, donde cada "estado" es el entero de 16 bits que corresponde al valor de cada moneda.

Cada estado tiene 16 transiciones de salida, que corresponden al estado después de voltear cada moneda.

Una vez que haya trazado todos los estados y transiciones, que tienen que encontrar el camino más corto en el gráfico desde su estado inicial al estado de 1111 1111 1111 1111,

Answer 6

que sugeriría una búsqueda en anchura, como se alguien más ya mencionado.

El gran secreto aquí es tener varias copias del tablero de juego. No pienses en "el tablero".

Sugiero crear una estructura de datos que contenga una representación de un tablero, y una lista ordenada de movimientos que llegaron a ese tablero desde la posición de inicio. Un movimiento es las coordenadas de la moneda central en un conjunto de volteos. Voy a llamar a una instancia de esta estructura de datos un "estado" a continuación.

Mi algoritmo básico sería algo como esto:

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. 

Si lo desea, puede añadir un límite a la longitud de la cola o la longitud de las listas de movimiento, para elegir un lugar para darse por vencido. También puede realizar un seguimiento de las tablas que ya ha visto para detectar bucles. Si la cola se vacía y no ha encontrado ninguna solución, entonces no existe ninguna.

Además, algunos de los comentarios ya hechos parecen ignorar el hecho de que el problema solo permite que las monedas que muestran las colas estén en el medio de un movimiento. Esto significa que el orden importa mucho. Si el primer movimiento arroja una moneda de las cabezas a las colas, entonces esa moneda puede ser el centro del segundo movimiento, pero no pudo haber sido el centro del primer movimiento. De manera similar, si el primer movimiento arroja una moneda de las colas a las cabezas, entonces esa moneda no puede ser el centro del segundo movimiento, aunque podría haber sido el centro del primer movimiento.

Answer 7

bien, aquí es una respuesta ahora que he leído las reglas correctamente :)

Es una búsqueda en amplitud utilizando una cola de los Estados y los pasos dados para llegar allí. No intenta prevenir los ciclos, pero debe especificar un número máximo de iteraciones para probar, por lo que no puede continuar para siempre.

Esta implementación crea un lote de cadenas - una lista inmutable de movimientos vinculados sería más clara en este frente, pero no tengo tiempo para eso en este momento.

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"); 
    } 
} 

Answer 8

Si está practicando para el ACM, consideraría este rompecabezas también para tableros no triviales, digamos 1000x1000. La fuerza bruta/codiciosa todavía puede funcionar, pero tenga cuidado de evitar el estallido exponencial.

Answer 9

Me senté e intenté con mi propia solución a este problema (según la ayuda que recibí en este hilo). Estoy usando una matriz 2D de booleanos, por lo que no es tan agradable como las personas que usan enteros de 16 bits con manipulación de bits.

En cualquier caso, aquí está mi solución en 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(); 
     } 
    } 

} 

Answer 10

El es el clásico "Lights Out" problema. En realidad, existe una solución de fuerza bruta O(2^N), donde N tiene el ancho o la altura, el que sea más pequeño.

Supongamos que los siguientes trabajos funcionan sobre el ancho, ya que puede transponerlo.

Una observación es que no es necesario presionar el mismo botón dos veces, simplemente cancela.

El concepto clave es solo que solo necesita determinar si desea presionar el botón para cada elemento en la primera fila. Cada otra pulsación de botón está determinada de forma única por una cosa: si la luz sobre el botón considerado está activada. Si está mirando la celda (x,y), y la celda (x,y-1) está activada, solo hay una manera de desactivarla presionando (x,y). Itere a través de las filas de arriba hacia abajo y si al final no quedan luces encendidas, tiene una solución allí. A continuación, puede tomar el mínimo de todos los intentos.