Исследование решения игры "пятнашки"

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

Хотя алгоритм поиска решения я сделал (он не идеальный, но достаточно хороший для тех условий, в которых он будет применяться), пятнашки затянули, и мне захотелось перебрать
все возможные расстановки пятнашек. Тогда можно было бы, например, проверить,
действительно ли максимум ­– 80 ходов. Так как количество вариантов –– 16! (это
примерно 20,9 триллиона), необходимо либо значительно сократить пространство
перебора (это – интересная задача для математика), либо оптимизировать хранение
информации о пройдённых вариантах. Эта оптимизация мне, как программисту,
показалась очень интересной задачей. Я потратил достаточно много времени на
неё, но пока не сделал. Так как практического смысла в ней уже нет, я её
отложил и ради развлечения перебрал все варианты для варианта пятнашек 4 на 3.
Т.е. когда необходимо собрать поле

1	2	3	4
5	6	7	8
9	10	11

Результатами этого эксперимента я и хочу поделиться.

Итак, для пятнашек 4*3 существует 12! вариантов, это чуть больше 479 миллионов. Ровно для половины этих вариантов не существует решения, так как у них другая чётность, чем у комбинации, приведённой выше. При таком количестве вариантов достаточно было завести три битовых массива по 60 МБ и реализовать функции для кодирования расстановки числом и
раскодирования обратно. Для задачи 4*4 я пробовал разные варианты такой функции, чтобы добиться большей локальности, т.е. чтобы расстановки, получаемые за один ход из текущей имели коды, как можно более близкие числовые к коду текущей расстановки. Для 4*3 это не имеет существенного значения. Главное, чтобы любое число от 0 до 12!-1 соответствовало одной своей комбинации.

Поиск шёл в ширину, начиная с расстановки-решения.

Максимальное количество ходов, необходимое для решения любой комбинации правильной чётности оказалось равно 53. Достаточно неплохо, учитывая, что максимум суммы расстояний от каждой плашки до её места в решении равен 37. Т.е. если можно было бы каждый ход перемещать любую плашку на одну клетку не взирая на то, что клетка занята, то максимальное количество ходов было бы 37.

Количество вариантов, решаемых за n и менее шагов (обозначим его S(n)), при увеличении n
сначала растёт быстро, затем всё медленнее: до 5 шагов – в два и более раза за шаг, до 27 шагов – в 1.5 и более раза. Если обозначить количество вариантов, которые можно решить ровно за n шагов за С(n), то максимум C(n) будет около 22 миллионов. N при этом равно 36. Меня это удивило, я думал будет симметрично, т.е. С(n) будет равно C(n_max- n).

Для пятнашек 4*4 S(n) растёт быстрее, чем степень двойки довольно долго – до 13 шага включительно. Мне удалось построить варианты для 4*4 до 29-го шага. Там S(29) равно примерно 822 миллионам, S(28) – 465 млн., т.е. в 1.74 раза меньше.

Количество комбинаций, решаемых за 53 хода – не 1, как я предполагал, а 18. У всех у них сумма расстояний по горизонтали от каждой плашки до её места в решении равна 21 (максимально возможное – 22).

До 28 шагов включительно попадаются комбинации, в которых сумма расстояний по вертикали от каждой плашки до её места в решении равно 4. Например, надо 28 шагов чтобы решить

5	2	3	8
1	6	7	4
9	10	11

В общем, вот, такая занимательная задачка и такие занимательные результаты. Если у кого есть идеи, как за разумное время перебрать варианты для 4*4 – интересно было бы услышать. Мне удалось придумать только как сократить количество вариантов с 20,9 до 6,5 триллионов. Соответственно, для перебора понадобится 1,6 терабайта памяти. Если бы удалось придумать хорошую функцию перестановка -> число, которая обеспечила бы близкие значения для близких перестановок, можно было бы хранить данные на диске без больших потерь в производительности. Кто что может предложить?
Михаил Машуков. 
Так же см. https://docs.google.com/document/pub?id=1Z3wx4s4lHqJ656iXmDNdUuLNR_MkIAb-qRFodh-UA8c

Как поменять тип .net проекта

Use case - имеется созданный проект, имеющий какой-то тип, например C# Class Library, необходимо изменить тип проекта, например C# WPF User Control Library. Такое изменение даст IDE понять, что можно создавать соответствующие WPF элементы, например ResourceDictionary.

Как мы знаем, меню Properties у студии очень небогато и, в частности, там нет опции, позволяющей сменить тип проекта. Есть только меню, позволяющее менять так называемые Output type - Class Library, Console Application, Windows Application.
Ключи, определяющие тип проекта – это GUID, которые прописаны в реестре по адресу

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\VisualStudio\10.0\Projects\.

Для нашего случая, если проект имеет тип C# Class Library, то эта информация будет записана в файле solution следующим образом:

Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "", "RelativePath\.csproj", ""

Где FAE04EC0-301F-11D3-BF4B-00C04F79EFBC означает, что это C# проект.
Отличие от WPF проекта в том, что в последнем помимо аналогичной строки в sln еще есть строка в файле проекта:

{60dc8134-eba5-43b8-bcc9-bb4bc16c2548};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}

Где 60dc8134-eba5-43b8-bcc9-bb4bc16c2548 означает поддержку WPF.
Итак, чтобы решить задачу нужно открыть файл проекта, и найти там . Если их нет, то добавить строку -

{60dc8134-eba5-43b8-bcc9-bb4bc16c2548};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}.

Аналогично решаются проблемы с другими типами проектов.

WPF wizard control с поддержкой динамической загрузки страниц

Захотелось мне тут сделать Wizard UserControl, да так чтобы к нему можно было добавлять страницы во время инициализации. Те клиентский код будет создавать мой Wizard, инициализировать его своими страницами – читай usercontrol – и работать с ним.

Сначала я написал Wizard так, что все страницы были реализованы в том же проекте что и Wizard и привязаны статически к нему. При этом я, как и всякий православный WPF программист, строго придерживался MVVM. Я создал UserControl WizardView, который содержит стили, DataTemplates и прочее. WizardView агрегирует экземпляр WizardViewModel, который содержит список страниц. Схематически дизайн изображен на диаграмме ниже:

У класса WizardViewModel есть метод CurrentPage, который возвращает PageViewModelBase. По нажатию кнопки Next происходит смена CurrentPage на следующую в списке. Возникает дилемма – как сделать так, чтобы как только сменилась страница, те PageViewModel,  менялось и View. Те как сделать отображение PageViewModel <->PageView.

Самый простой метод, при котором не нужно писать ни строчки кода на C#, это использовать DataType DataTemplate:

  <DataTemplate DataType="{x:Type viewModel:SomePageViewModel}">

  <view:SomePageView /> 

DataTemplate> 

Прописываем этот код для каждой страницы в Wizard и – все магическим образом работает.

Но что если страницы приходят из клиентского кода, то что делать? Самое очевидное и простое решение добавить в код конструктора WizardView добавление соответствующих шаблонов к ресурсам.

Для начала напишем функцию, которая будет создавать DataTemplate нужного вида и добавлять его в Window.Resources:

///

/// Add DataType DataTemplates to the Resources.

/// It provides mapping between Vew and ViewModel.

/// Note that it must be called before the call of method InitializeComponent.

///

private void AddTemplateToResources(Type pageView, Type pageViewModel)

{

    //generate the following xaml code:

    //

    //    < pageView />

    //

    FrameworkElementFactory fef = new FrameworkElementFactory(pageView);

    DataTemplate dataTemplate = new DataTemplate();

    dataTemplate.DataType = pageViewModel;

    dataTemplate.VisualTree = fef;

    DataTemplateKey dtKey = new DataTemplateKey(pageViewModel);

    this.Resources.Add(dtKey, dataTemplate);

}

Fef - это содержимое DataTempalate, dtKey - это ключ для ResourceDictionary, так как Window.Resource это именно этот класс.

Далее напишем такой код в конструкторе:

    public partial class WizardDialog : Window

    {

        readonly WizardViewModel m_wizardViewModel;

        public WizardDialog(IEnumerable<WizardPage> wizardPages)

        {

            foreach (var page in wizardPages)

            {

                AddTemplateToResources(page.View.GetType(),

                   page.ViewModel.GetType());

            }

            InitializeComponent();

            …

        }

…

Важно чтобы ресурсы добавлялись до вызова InitializeComponent.

Как работать с ftp с использованием PowerShell

Несмотря на то, что PowerShell – мощное средство для автоматизации работы системных администраторов и, иногда, разработчиков и тестеров, с ним “в коробке” нет cmdlet’ов для работы с ftp. И когда я столкнулся с необходимостью автоматизации скачивания с ftp сервера, мне пришлось долго и нудно гуглить и читать манны. Надеюсь, что этот урок сэкономит вам время, если вы столкнетесь с аналогичной задачей.

Реализация функций для работы с  ftp сервером может быть выполнена по-разному.

Один из очевидных вариантов – подключить какую-нибудь  .net сборку, содержащую класс, инкапсулирующий нужный функционал. Готовых классов для этого, опять-таки, нет. Но есть, написанный Dan Glass, класс FtpClient [1].  Код очень простой и более чем прозрачный, так что легко добавить нужные вам методы, если их нет.

Например, вам нужно проверить существует ли файл на сервере:

public bool DoesFileExist(string mask)

{

    if (!this.loggedin) this.Login();

    Socket cSocket = createDataSocket();

    this.sendCommand("NLST " + mask);

    //if it doesn't exist the code is 550

    //550 Requested action not taken.

    //File unavailable (e.g., file not found, no access).

    if (!(this.resultCode == 150 || this.resultCode == 125))

        return false;

    return true;

}

Единственное, что нужно знать это команды FTP и что обозначают коды возврата – их там не так много, так что это не составит труда [2].

Но у этой библиотеки есть большой недостаток – она явно рассчитана на “домашнее” использование. В ней нет поддержки многих нужных команд, а те которые поддерживаются, часто недостаточно функциональны. Например, если вам нужно скачивать с сервера в несколько потоков, то придется либо думать, как дописывать этот класс, либо брать какую-нибудь хорошую консольную утилиту, например aria2 [3]. Так же в библиотеке есть ошибки, например, в методе DeleteFile следует считать оба кода возврата 250 и 226 приемлемыми [2]:

public void DeleteFile(string fileName)

{

    if ( !this.loggedin ) this.Login();

    this.sendCommand( "DELE " + fileName );

    if (this.resultCode != 250 && this.resultCode != 226)

        throw new FtpException(this.result.Substring(4));

    Debug.WriteLine( "Deleted file " + fileName, "FtpClient" );

}

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

Наиболее адекватным вариантом, на мой вкус, оказалась связка двух консольных утилит – aria2 [3] и утилиты, поставляемая с Windows, для работы с ftp [4].

Я рекомендую использовать именно aria2 по ряду причин:

·       Работает как под *nix так и под windows

·       Поддерживает многие продвинутые опции – многопоточное скачивание, докачка, и так далее,

·       Одна из наиболее быстрых утилит среди подобных.

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

Наиболее интересны два способа –

·       Запуск через .net класс Diagnostics.Process:

    $process = [Diagnostics.Process]::Start($application, $arguments)

    #lets wait

    do

    {

    } while (!$process.HasExited)

                 Этот способ с точки зрения пользователя примечателен тем, что для приложения будет запущено новое окно, где у пользователя появляется возможность, в случае надобности, просто               нажать на “крестик” и, таким образом, покончить с процессом.

·       Запуск через консоль:

cmd /c (($application + " " + $arguments)

При таком подходе все сообщения, поступающие от приложения, будут писаться в output PowerShell IDE.

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

Так будет выглядеть код функции, предназначенной для работы с Aria2:

             $scriptsDir = (Split-Path -parent $MyInvocation.MyCommand.Definition) + "\"

function AriaDownload

{

    param($filename, $scriptsDir)

    $downloadmanager = $scriptsDir + "aria2c.exe"

    $destPath = $scriptsDir.Substring(0, $scriptsDir.length - 1) #get rid of the symbol '\' - it won't work with it

    #$FtpUserName = "username”

    #$FtpPassword = “password”

    $streamCount = 5

    $FtpServerFullPath = "ftp://ftp.youftp.com/yourfoler/" + $filename

    $dm_arguments  = ' --dir=' + $destPath + " --ftp-user=" + $FtpUserName + " --ftp-passwd=" + $FtpPassword + " -j" + $streamCount + " " + $FtpServerFullPath

   

    write-host ("Downloading file " + $filename + " is started")

    cmd /c ($downloadmanager + " " + $dm_arguments)

    write-host "Downloading is completed"

              }

              $filename = “your_file_name”

              $scriptsDir = Env:temp

              AriaDownload ($filename) $scriptsDir

Первая строка заносит в $scriptsDir путь к скрипту, те то, что в bat вы бы получили через %0. В функции прописано, что исполняемый файл aria2 лежит в директории скрипта.

Замечу, что функция названа не по правилам, те не глагол-существительное, как советуют разработчики PowerShell.

Далее напишем функцию для работы с ftp:

$_ftpName = " ftp.youftp.com "

$_ftpLogin = “login"

$_ftpPassword = '"password"'

$_ftpDir = "/yourfoler "

$_tempFolder = $Env:temp + "\"

$_scrFileName = $_tempFolder + "ftp_scenario"

function form-ftpScript

{

    param($command, $fileName)

    $text = 'open ' + $_ftpName + "`n"

    $text += 'user ' + $_ftpLogin + ' ' + $_ftpPassword + "`n"

    $text += 'cd ' + $_ftpDir + "`n"

    $text += $command + ' ' + $fileName + "`n"

    $text += 'quit'

    $text

}

function exe-ftpCom

{

    param($command, $fileName)

    remove-item $_scrFileName

    new-item -type "file" $_scrFileName

    $text = form-ftpScript $command $fileName

    out-file -filepath $_scrFileName -inputobject $text -encoding ASCII

    $cmdCommand = 'ftp -n -s:' + $_scrFileName

    cmd /c $cmdCommand

    remove-item $_scrFileName

              }

              exe-ftpCom "delete" $filename

Код выше делает следующее – создает файл сценария работы с ftp и затем запускает поставляемую с windows утилиту для работы с ftp.

Функция exe-ftpCom позволяет добавить нужную команду – например delete, put или какую-то еще.

[1] FTP client library for C#.

[2] FTP Command and Extension Registry.

[3] Aria2.

[4] Window’s console FTP client.