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

Ответ 1

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

Если бы вы знали количество ходов к цели, то это было бы идеально для Depth-First Search.

Эти статьи в Википедии содержат много информации о том, как работают поисковые запросы, даже содержат образцы кода на нескольких языках.

Любой поиск может быть рекурсивным, если вы уверены, что не закончите пространство стека.

Ответ 2

РЕДАКТИРОВАТЬ: Я не заметил, что вы не можете использовать монету в качестве основного хода, если она не показывает хвосты. Это действительно делает порядок важным. Я оставлю этот ответ здесь, но задумайтесь над тем, как писать еще один.

Здесь нет псевдокода, но подумайте об этом: можете ли вы представить себе, что вы дважды переворачиваете монету? Каким будет эффект?

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

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

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

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

EDIT: Вообще-то, по-моему, я бы использовал рекурсию. Это может сделать жизнь намного проще.

Хорошо, возможно, это было недостаточно очевидно. Пусть обозначают монеты A-P, например:

ABCD
EFGH
IJKL
MNOP

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

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

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

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

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

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

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

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

Хорошо, здесь решение в С#. Он показывает, сколько ходов было необходимо для каждого найденного решения, но оно не отслеживает, какие движения это были или какое меньшее количество ходов. Это 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);
        }
    }
}

Ответ 3

Я предлагаю широкий поиск по первой, как уже упоминалось ранее.

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

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

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

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.

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

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

Ответ 4

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

EDIT: Действительно, есть удобный способ сделать грубую работу. Вы можете попробовать все шаблоны с 1 движением, затем все шаблоны с двумя ходами и т.д. Когда шаблон n-move соответствует сетке, вы можете остановиться, показать выигрышный шаблон и сказать, что для решения требуется не менее 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 );
    }
}

Ответ 5

Чтобы уточнить предложение Federico, проблема состоит в том, чтобы найти набор из 16 генераторов, которые вместе взятые дают начальную позицию.

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

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

Ответ 8

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

Допустим следующие работы по ширине, так как вы можете транспонировать его.

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

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

Ответ 9

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

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

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

Ответ 10

Я сел и попытался самостоятельно решить эту проблему (на основе той помощи, которую я получил в этом потоке). Я использую 2d массив логических значений, поэтому он не так хорош, как люди, использующие 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();
        }
    }

}