algorithm - google - Problema de ACM: Coin-Flipping, me ayuda a identificar el tipo de problema que esto es
flip a coin & roll a die (10)
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 rompecabezas que consiste en una cuadrícula cuadrada de tamaño 4. Cada cuadrícula contiene una sola moneda; cada moneda muestra cabezas (H) y colas (T). Uno de estos rompecabezas se muestra aquí:
HHHH
TTTT
HTHT
TTHT
Cualquier moneda que muestre Tails (T) actual puede voltearse a Heads (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
H H H T
H H HT
TTHT
Si una moneda está en el borde del rompecabezas, por lo que no hay monedas en un lado o en el otro, entonces tiramos menos monedas. No nos "envolvemos" al otro lado. Por ejemplo, si volteamos la moneda de la parte inferior derecha del arrácteo anterior obtendríamos:
HTHH
HHHT
HHH H
TT T H
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 hacer 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 4x4 dada, cuál es el menor número de volteos para hacer que la grilla se dirija por completo.
Por ejemplo, la grilla:
HTHH
TTTH
HTHT
HHTT
La respuesta a esta grilla es: 2 volteos.
Lo que he hecho hasta ahora
Estoy almacenando nuestras grillas como una matriz bidimensional de booleanos. Cabezas = verdadero, cruz = falso. Tengo un método flip (int row, int col) que voltea las monedas adyacentes según las reglas anteriores y tengo un método isSolved () 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 recorrerla, yendo un mínimo de veces?
Es una máquina de estados finitos , 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 las transiciones, debe encontrar la ruta más corta en el gráfico desde su estado inicial al estado 1111 1111 1111 1111,
La grilla, leída en orden de fila mayor, no es más que un entero de 16 bits. Tanto la grilla 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 a través de un bit XOR, proporcione la grilla como el resultado Me pregunto si hay una alternativa más inteligente que probar 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: Puedes aplicar fuerza bruta con algo parecido al siguiente pseudocódigo recursivo (probablemente con errores):
// 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 );
}
}
Para dar más detalles sobre la sugerencia de Federico, el problema es encontrar un conjunto de los 16 generadores que xor''ed juntos da la posición de partida.
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. Solucionar esto solo debería ser una cuestión de eliminación gaussiana (mod 2).
EDITAR: Después de pensar un poco más, creo que esto funcionaría: construye una matriz binaria G de todos los generadores, y seamos el estado de partida. Estamos buscando vectores x satisfagan Gx=s (mod 2). Después de hacer la eliminación gaussiana, o terminamos con un vector x o encontramos que no hay soluciones.
El problema es entonces encontrar el vector y tal que Gy = 0 y x^y tenga el menor número posible de bits, y creo que la forma más fácil de encontrar esto sería probar todo eso y . Como solo dependen de G , pueden ser precalculados.
Sin embargo, admito que una búsqueda de fuerza bruta sería mucho más fácil de implementar. =)
Su rompecabezas es un clásico candidato de búsqueda de amplitud . Esto se debe a que está buscando una solución con el menor número posible de ''movimientos''.
Si supiera la cantidad de movimientos hacia la meta, entonces sería ideal para una Búsqueda de profundidad .
Esos artículos de Wikipedia contienen mucha información sobre la forma en que funcionan las búsquedas, incluso contienen muestras 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.
Bien, aquí hay una respuesta ahora que he leído las reglas correctamente :)
Es una búsqueda de amplitud utilizando una cola de estados y los movimientos necesarios 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 muchas 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");
}
}
Yo sugeriría una primera búsqueda de amplitud, como alguien más ya mencionado.
El gran secreto aquí es tener múltiples 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 se vería así:
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 agregar un límite a la longitud de la cola o la longitud de las listas de movimientos, para elegir un lugar donde 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.
EDITAR: No me había dado cuenta de que no puedes 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: ¿puede imaginarse a sí mismo arrojando una moneda dos veces? ¿Cuál sería el efecto?
Alternativa, escriba 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 soluciones posibles . Puedes probarlos con bastante facilidad.
Espero que esta pista no sea demasiado descarada. Estaré pendiente de esta pregunta para ver si necesitas más ayuda. Es un buen rompecabezas.
En cuanto a la recursión: puede usar la recursión. Personalmente, no lo haría en este caso.
EDITAR: En realidad, en segundo lugar, probablemente usaría la recursión. Podría hacer la vida mucho más simple.
De acuerdo, tal vez eso no fue lo suficientemente obvio. Etiquetemos las monedas AP, así:
ABCD
EFGH
IJKL
MNOP
Al voltear F, siempre estarán las siguientes monedas cambiando de estado: BEFGJ.
Voltear J siempre implicará las siguientes monedas cambiando de estado: FIJKN.
¿Qué pasa 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 de nuevo es lo mismo que simplemente voltear J para comenzar.
Entonces, cualquier solución no es realmente una ruta de "voltear A, luego F, luego J" - es "voltear <estas monedas>; no voltear <estas monedas>". (Es desafortunado que la palabra "voltear" se use tanto para la moneda principal para voltear como para las monedas secundarias que cambian de estado para un movimiento en particular, pero no importa, espero que quede claro a qué me refiero).
Cada moneda se usará como 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" también se puede representar 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 comenzar, por lo que para el ejemplo en la pregunta, comenzarí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);
}
}
}
Si está practicando para el ACM, consideraría este acertijo también para tableros no triviales, digamos 1000x1000. La fuerza bruta / codiciosa todavía puede funcionar, pero tenga cuidado de evitar el estallido exponencial.
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();
}
}
}
El es el clásico problema "Lights Out". En realidad, hay una solución de fuerza bruta O(2^N) fácil, donde N es 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 forma 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.