Проблема ACM: зеркальное отражение монеты, помогите мне определить тип проблемы, которая это

Я предложил бы поиск в ширину, как кто-то еще уже упомянул.

Большой секрет здесь состоит в том, чтобы иметь несколько копий игровой доски. Не думайте "о плате".

Я предлагаю создать структуру данных, которая содержит представление платы и заказанный список перемещений, которые добрались до той платы от стартовой позиции. Перемещение является координатами центральной монеты в ряде зеркальных отражений. Я назову экземпляр этой структуры данных "состоянием" ниже.

Мой основной алгоритм выглядел бы примерно так:

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.

Если Вам нравится, Вы могли бы добавить предел длине очереди или длине списков перемещения, для выбора места для отказа. Вы могли также отслеживать платы, которые Вы уже видели для обнаружения циклов. Если порожняя тара очереди и Вы не нашли решений, то ни один не существует.

Кроме того, несколько комментариев, уже сделанных, кажется, игнорируют то, что проблема только позволяет монеты, которые показывают хвосты, чтобы быть посреди перемещения. Это означает, что порядок очень имеет значение. Если первый шаг бросает монетку от глав к хвостам, то та монета может быть центром второго перемещения, но это, возможно, не был центр первого шага. Точно так же, если первый шаг бросает монетку от хвостов до голов, то та монета не может быть центром второго перемещения, даже при том, что это, возможно, был центр первого шага.

Править: Я не заметил, что Вы не можете использовать монету в качестве основного перемещения, если оно не показывает хвосты. Это действительно делает порядок важным. Я оставлю этот ответ здесь, но изучу запись другого также.

Никакой псевдокод здесь, но думают об этом: можно ли когда-либо воображать себя бросающий монетку дважды? Каков был бы эффект?

Альтернатива, запишите некоторую произвольную плату (буквально, запишите ее). Настройте некоторые монеты реального мира и выберите два произвольных, X и Y. Сделайте "X зеркальных отражений", затем "Y зеркально отражают" затем другие "X зеркальных отражений". Запишите результат. Теперь сбросьте плату к стартовой версии и просто сделайте "Y зеркальное отражение". Сравните результаты и думайте о том, что произошло. Попробуйте его несколько раз, иногда с X и Y близко друг к другу, иногда нет. Станьте уверенными в своем заключении.

Тот ход мыслей должен привести Вас к способу определить конечное множество возможных решений. Можно протестировать всех их довольно легко.

Надеюсь, что эта подсказка не была слишком явной - я буду следить за этим вопросом видеть, нуждаетесь ли Вы в большем количестве помощи. Это - хорошая загадка.

Что касается рекурсии: Вы могли использовать рекурсию. Лично, я не был бы в этом случае.

Править: На самом деле поразмыслив я, вероятно, использовал бы рекурсию. Это могло сделать жизнь намного более простой.

Хорошо, возможно, это не было достаточно очевидно. Давайте маркируем монеты A-P, как это:

ABCD
EFGH
IJKL
MNOP

Зеркальное отражение F будет всегда включать следующие монеты, изменяющие состояние: BEFGJ.

Зеркальное отражение J будет всегда включать следующие монеты, изменяющие состояние: FIJKN.

Что происходит, если Вы бросаете монетку дважды? Два зеркальных отражения уравновешивают друг друга, независимо от того, что происходят другие зеркальные отражения.

Другими словами, зеркально отражая F и затем J совпадает с зеркальным отражением J и затем F. Зеркальное отражение F и затем J и затем F снова совпадает только с зеркальным отражением J для запуска с.

Таким образом, любым решением не является действительно путь "зеркального отражения затем F затем J" - это - "зеркальное отражение <эти монеты>; не бросайте <эти монетки>". (Неудачно, что слово "зеркальное отражение" используется и для основной монеты для зеркального отражения и для вторичные монеты, которые изменяют состояние для конкретного перемещения, но не берут в голову - надо надеяться, ясно, что я имею в виду.)

Каждая монета будет или использоваться в качестве основного перемещения или нет, 0 или 1. Существует 16 монет, таким образом, 2^16 возможности. Так 0 мог бы представить, "ничего не делают"; 1 мог бы представить "просто A"; 2 мог бы представить "просто B"; 3 "A и B" и т.д.

Протестируйте каждую комбинацию. Если (так или иначе) существует больше чем одно решение, считайте число битов в каждом решении найти наименьшее количество числа.

Подсказка реализации: "текущее состояние" может быть представлено как число на 16 битов также. Используя конкретную монету, поскольку основное перемещение всегда будет XOR текущее состояние с постоянным числом (для той монеты). Это делает действительно легким разработать эффект какой-то конкретной комбинации перемещений.

Хорошо, вот решение в C#. Это показывает, сколько перемещений требовалось для каждого решения, которое это находит, но это не отслеживает, которых перемещается, это было, или каково наименьшее количество количества перемещений. Это - SMOP :)

Вход является списком, которого монеты показывают хвосты для запуска с - так для примера в вопросе, Вы запустили бы программу с аргументом "BEFGJLOP". Код:

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

Для разработки предложение Federico проблема о нахождении ряда 16 генераторов, что xor'ed вместе дает стартовую позицию.

Но если мы рассматриваем каждый генератор как вектор целых чисел по модулю 2, это становится нахождением линейной комбинации векторов, это равняется стартовой позиции. Решение этого должно просто быть вопросом исключения Гаусса (модификация 2).

Править: После размышления немного больше, я думаю, что это работало бы: Создайте двоичную матрицу G из всех генераторов, и позволяют s будьте начальным состоянием. Мы ищем векторы x удовлетворение Gx=s (модификация 2). После выполнения исключения Гаусса мы любой заканчивает с таким вектором x или мы находим, что нет никаких решений.

Проблема состоит в том, чтобы затем найти вектор y таким образом, что Gy = 0 и x^y имеет как можно меньше набора битов, и я думаю самый легкий способ найти, что это должно было бы попробовать весь такой y. Так как они только зависят от G, они могут быть предварительно вычислены.

Я признаю, что поиск "в лоб" было бы намного легче реализовать, все же.=)

Сетка, считанная в главном строкой порядке, является ничем больше чем целое число на 16 битов. И сетка, данная проблемой и 16 возможных перемещений (или "генераторы"), могут быть сохранены как целые числа на 16 битов, таким образом проблемы составляют для нахождения наименее возможного количества генераторов, которое, суммированный посредством поразрядного XOR, дает саму сетку как результат. Интересно, существует ли более умная альтернатива, чем попытка всех этих 65 536 возможностей.

Править: Действительно существует удобный способ сделать bruteforcing. Можно попробовать все шаблоны с 1 перемещением, затем все шаблоны с 2 перемещениями, и так далее. Когда шаблон n-перемещений соответствует сетке, можно остановить, показать шаблон победы и сказать, что решение требует, по крайней мере, n перемещений. Перечисление всех шаблонов n-перемещений является рекурсивной проблемой.

EDIT2: Вы можете "в лоб" с чем-то вроде следующего (вероятно, багги) рекурсивный псевдокод:

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

Если бы Вы практикуете для ACM, я рассмотрел бы эту загадку также для нетривиальных плат, сказал бы 1000x1000. Грубая сила / жадный может все еще работать, но стараться избежать экспоненциального взрыва.

Хорошо, вот ответ теперь, когда я прочитал правила правильно :)

Это - поиск в ширину с помощью очереди состояний и перемещений, взятых для получения там. Это не предпринимает попытки предотвратить циклы, но необходимо указать максимальное количество повторений для попытки, таким образом, это не может продолжиться навсегда.

Эта реализация создает много строк - неизменный связанный список перемещений был бы более опрятным на этой передней стороне, но у меня нет времени для этого прямо сейчас.

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

Это - конечный автомат, где каждое "состояние" является целочисленным соответствием на 16 битов значение каждой монеты.

Каждое состояние имеет 16 исходящих переходов, соответствуя состоянию после того, как Вы бросите каждую монетку.

После того как Вы планировали все состояния и переходы, необходимо найти, что кратчайший путь в графике от состояния начала указывает 1111 1111 года 1111 года 1111,

Я сел и попробовал свое собственное решение этой проблемы (на основе помощи, которую я получил в этом потоке). Я использую двумерный массив логических значений, поэтому он не так хорош, как люди, использующие 16-битные целые числа с битовыми манипуляциями.

В любом случае, вот мое решение на 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();
        }
    }

}

Это классическая задача «Отключить свет». На самом деле существует простое решение методом грубой силы O (2 ^ N) , где N - это либо ширина, либо высота, в зависимости от того, что меньше.

Предположим, что с шириной работает следующее: вы можете транспонировать ее.

Одно наблюдение заключается в том, что вам не нужно нажимать одну и ту же кнопку дважды - это просто отменяется.

Основная идея заключается в том, что вам нужно только определить, хотите ли вы нажимать кнопку для каждого элемента в первой строке. Каждое другое нажатие кнопки однозначно определяется одним - горит ли лампочка над рассматриваемой кнопкой. Если вы смотрите на ячейку (x, y) , а ячейка (x, y-1) включена, есть только один способ выключить ее, нажав ] (х, у) . Пройдите по строкам сверху вниз, и если в конце не осталось лампочек, у вас есть решение. Затем вы можете взять минимум всех попыток.