ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし。たまにカメラの話や競馬の話も書きます。

JavaScriptのundefined判定、jQueryのdomが見つからなかった時の判定

Javascriptのundefined判定

if(hoge === undefined) {
  //
}

ただし、 undefined の再定義ができるので、注意が必要だが、普通そんなことしないので、基本的には undefined と === 比較したらいいと思います。

例えば行かのようにundefinedの再定義ができます

undefined = 1;

古いJSとかだとできるらしいですが、普通はしないとおもうので === undefined での比較でいいと思います。

jQueryのdomが見つからなかった時の判定

これが一番シンプルで分かりやすいと個人的には思っています。

var dom = $('#title-description');
if(dom.length === 0) {
  //
}

Ansibleで構築したVagrant上のLaravel環境を使ってlocal開発環境を整える

この記事の続きてきなやつです

yoshiki-utakata.hatenablog.com

local環境で書いたLaravelのコードをすぐにvagrant上で動作確認したい

  • 開発しているPCにPHP7を入れるのはめんどいので動作確認はVagrant上でした
  • 書いたコードが即VagrantVMに反映されて動作確認できるようにしたい

これらを実現します。

新しいユーザーを作成する

アプリケーションを動作させる用のユーザーを作成します。

Vagrantのsynced_folderの設定をする

いまディレクトリはこうなっています

Vagrantfile
ansible/ -- ansibleが入っているディレクトリ

とりあえずここに適当なディレクトリを作ります。

Vagrantfile
ansible/
applications/

この applications ディレクトリをVagrantVMと共有します。以下をVagrantfileに追記します。

# coding: utf-8
# -*- mode: ruby -*-
# vi: set ft=ruby :

Vagrant.configure(2) do |config|
  
  ...

  # ホストとディレクトリを同期する
  config.vm.synced_folder "applications", "/home/vagrant/applications", create: true, mount_options: ["uid=vagrant,gid=vagrant"]

end

vagrant reload します。

vagrant側にディレクトリが出来ていることを確認します。

$ vagrant ssh

[vagrant@vagrant ~]$ ls -l
total 0
drwxr-xr-x 1 vagrant vagrant 68 Dec  7 06:46 applications

共有フォルダ上でアプリケーションを作成する

これでLaravel 5.5開発もお手の物です。例えばlocalで*1 Laravel 5.5 のアプリケーションを作成しようとすると

$ composer create-project laravel/laravel myapp "5.5.*"

  [InvalidArgumentException]
  Could not find package laravel/laravel with version 5.5.* in a version installable using your PHP version 5.6.22.

local環境はPHP 5.6.22なので無理だとよ言われてしまい作成できません。そこで、vagrant上でLaravel 5.5 のアプリケーションを作成します。先程 synced_fonder の設定をした /home/vagrant/applications 上でLaravel 5.5のアプリケーションを作成します。

$ vagrant ssh

[vagrant@vagrant ~]$ cd applications/
[vagrant@vagrant applications]$ composer create-project laravel/laravel myapp "5.5.*"

こうするとホストOS側でもlaravelのアプリケーションのディレクトリができています。

$ ls applications
myapp/

Apacheの設定を書き換える

アプリケーションのパスが変わったのでApacheの設定を書き換えます。

diff --git a/roles/apache2_4/templates/laravel.conf.j2 b/roles/apache2_4/templates/laravel.conf.j2
index cdc7831..bb14ec9 100644
--- a/roles/apache2_4/templates/laravel.conf.j2
+++ b/roles/apache2_4/templates/laravel.conf.j2
@@ -1,10 +1,10 @@
 <VirtualHost *:80>
-        DocumentRoot /home/vagrant/myapp/public
+        DocumentRoot /home/vagrant/applications/myapp/public

         ErrorLog /etc/httpd/logs/laravel_error.log
         CustomLog /etc/httpd/logs/laravel_access.log combined

-        <Directory "/home/vagrant/myapp/public">
+        <Directory "/home/vagrant/applications/myapp/public">
                 AllowOverride All
                 Require all granted
         </Directory>

vagrant provision して http://localhost:58080 にアクセスしてみます。Laravelのページが表示されるはずです。

適当に変更を加えてみる

Laravelのアプリに軽く変更を加えてみます。

ルーティングの設定は myall/routes あたりに書かれています。例えば、http://localhost:58080 にアクセスした時のルーティングは routes/web.php

<?php

/*
|--------------------------------------------------------------------------
| Web Routes
|--------------------------------------------------------------------------
|
| Here is where you can register web routes for your application. These
| routes are loaded by the RouteServiceProvider within a group which
| contains the "web" middleware group. Now create something great!
|
*/

Route::get('/', function () {
    return view('welcome');
});

view('welcone'); に対応するビューは myapp/resources/views/welcome.blade.php です。これを少し書き換えてみます。

その前にまず git init します

cd myapp
git init
git status
git add .
git commit

`resources/views/welcome.blade.php を編集してみます。

diff --git a/resources/views/welcome.blade.php b/resources/views/welcome.blade.php
index a246e10..33e4a38 100644
--- a/resources/views/welcome.blade.php
+++ b/resources/views/welcome.blade.php
@@ -79,7 +79,7 @@

             <div class="content">
                 <div class="title m-b-md">
-                    Laravel
+                    Laravel 5.5
                 </div>

                 <div class="links">

http://localhost:58080 にアクセスしてみます。

f:id:yoshiki_utakata:20171207180222p:plain

まとめ

Ansibleはちょっと雑なところがありますが、だいたいこんな感じで開発は進めていけると思います。Laravelかなり便利なフレームワークなので皆使っていきましょう。

*1:VagrantではないホストOS上

Ansibleを使ってPHP7環境をVagrant上に構築してLaravelに入門

この記事は Laravel Advent Calender 2017 7日目の記事です。

昨日の記事は LaravelのControllerクラスって何やってるの? - Qiita でした

Laravel DI からはじまり何もかもが揃っていてグッドなフルスタックフレームワークLaravelを使っていきましょう。Ansibleで環境構築してLaravelが動くまでをやっていきたいと思います。

なんでHomestead使わないの?

Laravel Homestead っていう、Laravelがいい感じに動くVagrant Boxみたいなのがあるんですが

  • Homestead ブラックボックスすぎてよく分かってないからちゃんと理解した
  • Ansible 勉強したい
  • 実際動かす際には仮想環境じゃないときもある

とまあれこれあるので、AnsibleでPHP7 + Laravelが動く環境を頑張って作ってみたいなとおもいます。

Vagrant使ってますが、Ansible流れればいいのでVagrantである必要は)ないです。

とりあえずVagrantつくる

まずは最小構成で。 vagrant up できて vagrant ssh できる程度のもの適当に作ります。Cent OS 7.1 で。

$ cat Vagrantfile
# coding: utf-8
# -*- mode: ruby -*-
# vi: set ft=ruby :

Vagrant.configure(2) do |config|
  config.vm.box = "centos/7"
  config.vm.hostname = "vagrant"

  # ipアドレス ipは適当に変更しておk
  config.vm.network :private_network, ip: "192.168.33.11"
  config.ssh.insert_key = false
  config.ssh.forward_agent = true
end

$ vagrant up
# なんやかんや

$ vagrant ssh
[vagrant@vagrant ~]$

できた。

Vagrant に Ansible を流せるようにする

ディレクトリ構成こんな感じで

Vagrantfile
ansible/
 └playbook.yml

VagrantfileにAnsibleの設定を追記

$ cat Vagrantfile
# coding: utf-8
# -*- mode: ruby -*-
# vi: set ft=ruby :

Vagrant.configure(2) do |config|
  config.vm.box = "centos/7"
  config.vm.hostname = "vagrant"

  # ipアドレス ipは適当に変更しておk
  config.vm.network :private_network, ip: "192.168.33.11"
  config.ssh.insert_key = false
  config.ssh.forward_agent = true

  # ansibleの設定
  config.vm.provision "ansible" do |ansible|
    ansible.playbook = "ansible/playbook.yml"
  end
end

vagrantが起動している状態で

$ ls
Vagrantfile   ansible/

$ cat ansible/playbook.yml
- hosts: all
  sudo: true
  user: vagrant

$ vagrant provision
==> default: [vagrant-hostsupdater] Checking for host entries
==> default: [vagrant-hostsupdater]   found entry for: 192.168.33.11 vagrant
==> default: Running provisioner: ansible...
    default: Running ansible-playbook...
[DEPRECATION WARNING]: Instead of sudo/sudo_user, use become/become_user and
make sure become_method is 'sudo' (default).
This feature will be removed in a
future release. Deprecation warnings can be disabled by setting
deprecation_warnings=False in ansible.cfg.

PLAY [all] *********************************************************************

TASK [Gathering Facts] *********************************************************
ok: [default]

PLAY RECAP *********************************************************************
default                    : ok=1    changed=0    unreachable=0    failed=0

まあ何も書いてないので changed=0 ですがとりあえずOKになるのを確認。

このタイミングで初めて知ったのですが、 sudo: true はAnsible 1.9 からはDeprecatedらしいので become: true に書き換えます。

$ cat ansible/playbook.yml
- hosts: all
  become: true

Ansible で gitを入れてみる

Ansibleでgitを入れます。ほんとはソースをダウンロードしてビルドすると、バージョンが固定されて良い気がするのですが、めんどいのでyumで入れてしまいます。Ansibleの動作確認も兼ねてます。

Ansibleはだいたいディレクトリ構成が決められています。基本的には「gitのインストール」「Apacheのインストール」といった単位でモジュール化して、roles というディレクトリ以下に置きます。以下のリポジトリに実際に出来たAnsibleを置いておいたので、これをみてもらうと分かりやすいかと思います。

github.com

ansible/
+playbook.yml
+roles/
 +tasks/
  +git/
   +main.yml

roles/git/tasks/main.yml *1 にgitのインストール用のAnsibleを書きます。

$ cat ansible/roles/git/tasks/main.yml
- name: install git
  yum: name=git state=installed

yumを使ってgitをinstalledな状態にするということです。

続いてplaybook.ymlに以下を追記します。

$ cat ansible/playbook.yml
- hosts: all
  become: true
  user: vagrant
  roles:
  - git

roles に git を追加することで。roles/git/tasks/main.yml が実行されます。

$ vagrant provision
==> default: [vagrant-hostsupdater] Checking for host entries
==> default: [vagrant-hostsupdater]   found entry for: 192.168.33.11 vagrant
==> default: Running provisioner: ansible...
    default: Running ansible-playbook...

PLAY [all] *********************************************************************

TASK [Gathering Facts] *********************************************************
ok: [default]

TASK [git : install git] *******************************************************
changed: [default]

PLAY RECAP *********************************************************************
default                    : ok=2    changed=1    unreachable=0    failed=0

changed=1 となりました。gitが入っているか確かめてみます。

$ vagrant ssh
Last login: Mon Dec  4 22:57:06 2017 from 10.0.2.2
[vagrant@vagrant ~]$ git

AnsibleでPHP7

PHPはgitと違って、デプロイしたコードの動作に差異が出る可能性があるので、これこそソースからビルドしたほうがいいのですが、やはり面倒なのでyumで入れてしまいます。

roles以下にphp7を作成します。

$ cat ansible/roles/php7/tasks/main.yml
---
- name: yum install epel-repease
  yum: name=epel-release state=installed

- name: add remi-repo repository
  command: rpm -ih http://rpms.famillecollet.com/enterprise/remi-release-7.rpm creates=/etc/yum.repos.d/remi.repo

- name: install php 7.1
  yum: name={{ item }} enablerepo=remi,remi-php71 state=installed
  with_items:
    - php
    - php-devel
    - php-fpm
    - php-gd
    - php-mbstring
    - php-mcrypt
    - php-mysqlnd
    - php-pdo
    - php-xml
    - php-zip

$ cat ansible/playbook.yml
- hosts: all
  become: true
  user: vagrant
  roles:
  - git
  - php7

$ vagrant provision

パッケージはなんとなく使いそうなのを適当にチョイスしてインストールしています。 vagrant ssh して php -v すると php がインストールされているはずです。phpの設定ファイル php.ini もAnsibleで管理されているのが望ましいので、ansible管理するようにします。

roles/php7/templates/php.ini.j2 に php.ini のテンプレートを配置して、roles/php7/tasks/main.yml に、このテンプレートをデプロイするコマンドを書きます。

基本的にはデフォルトのテンプレートでよいのですが、timezoneだけちゃんと設定されていることを確認してください https://github.com/yoshikyoto/php7-ansible/blob/41c103ef61ee6488c2293ff2327eb7c2ebb372aa/roles/php7/templates/php.ini.j2#L903

- name: deploy php.ini
  template:
    src: php.ini.j2
    dest: /etc/php.ini

詳しくは先程紹介したリポジトリを見て下さい。 php.ini をデプロイして php が正しく動くことを確認します。

$ vagrant provision

$ vagrant ssh
[vagrant@vagrant ~]$ ls -la /etc/php.ini
-rw-r--r-- 1 root root 62433 Dec  4 23:21 /etc/php.ini # きっとタイムスタンプが更新されている

[vagrant@vagrant ~]$ php -i
# ちゃんと設定ファイルが読み込まれているか

AnsibleでApache

AnsibleでApacheをソースからビルドして入れようと思ったのですが、Vagrantcentos/7 は最初からApacheが入っているらしく、ソースからビルドしようとするとちょっと複雑なことに...ということで、ソースのビルドのあたりはなんとなく適当に書きました。。。まあconfigさえちゃんとデプロイできれば問題ないので...

ソースのビルド&インストールは https://github.com/yoshikyoto/php7-ansible/blob/1ebf06244a94ee02cbe7a66996c4fecb4a6b807e/roles/apache2_4/tasks/install.yml みたいな感じですね。

roles/apache2_4/tasls/main.yml には以下を書いておきます。

---
- name: check if exist apache
  command: service httpd status
  ignore_errors: True
  register: check_apache

# Apacheのインストール
- include: install.yml
  when: check_apache|failed

- name: enable apache
service: name=httpd enabled=yes

service httpd status 叩いてみて Apache がインストールされて無さそうだったらインストールします。そして、OS起動時にApacheも起動するように設定しておきます。

ApacheのconfigをAnsibleで管理する

roles/apache2_4/templates 以下に Apache の config のテンプレートを置いておきます。

https://github.com/yoshikyoto/php7-ansible/blob/1ebf06244a94ee02cbe7a66996c4fecb4a6b807e/roles/apache2_4/templates/httpd.conf.j2

基本的にはデフォルトのままですが、Apacheの起動ユーザーだけvagrantに変更しています。*2

https://github.com/yoshikyoto/php7-ansible/blob/1ebf06244a94ee02cbe7a66996c4fecb4a6b807e/roles/apache2_4/templates/httpd.conf.j2#L66-L67

User vagrant
Group vagrant

さて、このconfigをデプロイします。

ここで問題があります。ソースからビルドした場合、 ApacheのConfigファイルは /usr/local/apache2/conf 以下にあったりするのですが、もとから入っているやつとかyumで入れたやつは /etc/httpd/conf 以下にあったりします。一応両方に対応しておきます。

#####
# httpd.confのデプロイ
#####
- name: check existance /etc/httpd/conf
  stat: path=/etc/httpd/conf
  register: etc_httpd_conf

- name: deploy /etc/httpd/conf/httpd.conf
  template: src=httpd.conf.j2 dest=/etc/httpd/conf/httpd.conf
  when: etc_httpd_conf.stat.exists

- name: check existance /usr/local/apache2/conf
  stat: path=/usr/local/apache2/conf
  register: usr_local_apache_conf

- name: deploy /usr/local/apache2/conf/httpd.conf
  template: src=httpd.conf.j2 dest=/usr/local/apache2/conf/httpd.conf
  when: usr_local_apache_conf.stat.exists

Apache動作確認

Apacheがインストールされていることを確認します。

[vagrant@vagrant ~]$ service httpd status
Redirecting to /bin/systemctl status httpd.service
● httpd.service - The Apache HTTP Server
   Loaded: loaded (/usr/lib/systemd/system/httpd.service; enabled; vendor preset: disabled)
   Active: active (running) since Tue 2017-12-05 02:52:01 UTC; 1min 32s ago
     Docs: man:httpd(8)
           man:apachectl(8)
 Main PID: 19685 (httpd)
   Status: "Total requests: 0; Current requests/sec: 0; Current traffic:   0 B/sec"
   CGroup: /system.slice/httpd.service
           ├─19685 /usr/sbin/httpd -DFOREGROUND
           ├─19686 /usr/sbin/httpd -DFOREGROUND
           ├─19687 /usr/sbin/httpd -DFOREGROUND
           ├─19688 /usr/sbin/httpd -DFOREGROUND
           ├─19689 /usr/sbin/httpd -DFOREGROUND
           └─19690 /usr/sbin/httpd -DFOREGROUND

さてここで、Apacheを入れたので、Webページにアクセスしてみたいところです。Vagrantfileに以下を追記したうえで vagrant reload します。

config.vm.network "forwarded_port", guest: 80, host: 58080

これを行うと、hostの58080ポートがvagrantの80ポートにフォワーディングされるようになります。 localhost:58080 にアクセスしてみまよう。

f:id:yoshiki_utakata:20171207134409p:plain

Apacheが動いていることがわかりました。

Apache で php7 が動いていることを確認する

vagrantのbox centos/7の設定がそうなっているのか、すでにPHP7がApache上で動いているみたいです。 vagrant ssh してみて、Apache上でphpが動いているか軽く確認します。

vagrant@vagrant ~]$ sudo su -
Last login: Thu Dec  7 01:45:48 UTC 2017 on pts/1
[root@vagrant ~]# vi /var/www/html/test.php
[root@vagrant ~]# cat /var/www/html/test.php
<?php

phpinfo();

これで http://localhost:58080/test.php にアクセスしてみます。

f:id:yoshiki_utakata:20171207134620p:plain

PHPのバージョンなどが確認できます。

composer のインストール

PHP開発するならcomposerもインストールしておきたいです。PHP7をインストールする時に composer も同時にインストールされるようにしました。以下をAnsibleのrole/php7以下のタスクに追加します。((本当はshell: curlじゃなくてちゃんとインストールしたい...)

- name: install composer
  shell: curl -sS https://getcomposer.org/installer | php -- --install-dir=/usr/bin && mv /usr/bin/composer.phar /usr/bin/composer
         creates=/usr/bin/composer

Laravelのプロジェクト作成

composerを入れたことにより、Laravelプロジェクトを作成できるようになりました。vagrantのホームディレクトリ以下に適当なLaravelプロジェクトを作成してみます。 vagrant ssh して以下のコマンドで作成できます。

[vagrant@vagrant ~]$ composer create-project laravel/laravel myapp 5.5.*

これで Laravel 5.5 でプロジェクトが作成されます。初回はパッケージのインストールなどで時間がかかります。

ApacheでLaravelを動かすための設定を入れる

ApacheでLaravelを動かすための設定を入れます。

今回は、 roles/apache2_4/templates/laravel.conf.j2 というものを作成しました。

<VirtualHost *:80>
        DocumentRoot /home/vagrant/myapp/public

        ErrorLog /etc/httpd/logs/laravel_error.log
        CustomLog /etc/httpd/logs/laravel_access.log combined

        <Directory "/home/vagrant/myapp/public">
                AllowOverride All
                Require all granted
        </Directory>
</VirtualHost>

ApacheでLaravelのプロジェクトを動かすためには、 AllowOverride All の設定を入れる必要があるので注意です。

この config を apache の conf.d ディレクトリにデプロイするようにします。

https://github.com/yoshikyoto/php7-ansible/blob/1ebf06244a94ee02cbe7a66996c4fecb4a6b807e/roles/apache2_4/tasks/config.yml#L22-L39

#####
# laravel.conf のデプロイ
#####
- name: check existance /etc/httpd/conf.d
  stat: path=/etc/httpd/conf.d
  register: etc_httpd_conf_d

- name: deploy /etc/httpd/conf.d/laravel.conf
  template: src=laravel.conf.j2 dest=/etc/httpd/conf.d/laravel.conf
  when: etc_httpd_conf_d.stat.exists

- name: check existance /usr/local/apache2/conf.d
  stat: path=/usr/local/apache2/conf.d
  register: usr_local_httpd_conf_d

- name: deploy config
  template: src=laravel.conf.j2 dest=/usr/local/apache2/conf.d/laravel.conf
when: usr_local_httpd_conf_d.stat.exists

これで http://localhost:58080/ にアクセスすると... Forbidden になってしまいます

SELinuxを無効化する

SELinuxというのがジャマをしているらしいです。これを無効化するのが良いのかドウか微妙ですが…とりあえず無効化します。

適当にlaravelというroleを作成して(ドンドン雑になってきましたが気にしない...)、SELinuxを無効化する設定を Ansible にいれます。

https://github.com/yoshikyoto/php7-ansible/blob/1ebf06244a94ee02cbe7a66996c4fecb4a6b807e/roles/laravel/tasks/main.yml

####
# Laravel動かすためにSELinuxを無効化したほうがよさげ
####
- name: install libselinux-python
  yum: name=libselinux-python state=latest

- name: disable SELinux
selinux: state=disabled

最終的に playbook.yml はこうなりました。

https://github.com/yoshikyoto/php7-ansible/blob/1ebf06244a94ee02cbe7a66996c4fecb4a6b807e/playbook.yml

これを vagrant provision で流して、 http://localhost:58080/ にアクセスすると...

f:id:yoshiki_utakata:20171207135701p:plain

Laravelが動くようになりました!

ここから開発とかしていくにはどうしたらいいのか

とりあえずAnsibleでLaravel環境を構築するまでを書きましたが、実際に開発する際には、Vagrantのsynced_folderとかを使って開発していくのが良いと思います。長くなってしまいましたのでここまで。synced folder については別記事でかくかもしれないです!これでLaravelの開発環境が整ったぞ!

*1:ディレクトリは必ず複数形に!

*2:本当はvagrantじゃなくてちゃんとapache用のユーザーを作ったほうがいいのですが、今回は簡単のためにvagrantユーザーで起動します。

Code Quest 「毒沼ノ試練」を頑張って探索してクリアする

この記事は 〇〇勉強してみた Advent Calendar 2017 の6日目の記事です。

昨日も書いた Code Quest の記事ですが、今回は皆が一番苦戦したであろう「毒沼ノ試練」について書こうと思います。

Code Quest

プログラミング学習用ゲーム的な、あるいはプログラミングコンテスト的なサムシングです。

geek-out.jp

毒沼の試練

f:id:yoshiki_utakata:20171204161930p:plain

クリアしたコード

手動でやってみると、HP49まではいくのですが、なかなか50にならなくてクリアできません。ということで、プログラムに探索させることにしました。 実際クリアしたコードはgithub上に置いておきました。以下のコードを、メモリ8GBくらい与えた上で実行させ、寝ておきたらクリアしていました(解くのに5〜6時間くらいかかった?)。

github.com

このコードにメモリを8GBくらい与えて放置します。

php -d memory_limit=-8196M  poison_maze.php

とりあえす放置して寝たらクリアしていると思います。

このコードに至るまでのいきさつ

まず普通に深さ優先探索する

とりあえずダメ元で深さ優先探索させますがダメでした。当然ながら時間がかかりすぎます。

最初のHPより低くはならないように枝刈り

次に実施したのが枝刈りです。最初のHPが36なので、HPが35以下になってしまった場合は探索を打ち切ります(実際のコードでは少し余裕を持って34以下にしてあります)。結構切れるかなと思ったのですがこれでもダメでした。

一旦 Priority Queue を使った探索に切り替える。

深さ優先探索の場合、探索効率が悪いな、ということで、PriorityQueueを使った探索に変更します。PriorityQueueのPriorityには現在の体力を採用します。つまり、HPが高くなるようなルートから優先的に探索を進めていくようにします。

さて、深さ優先探索に比べて Priority Queue を使った探索(あるいは幅優先探索)は、探索効率がよくなる変わりにメモリを多く消費するという欠点があります。HP35以上という条件は残したまま Priority Queue 探索を進めていたのですが、メモリが足りず最後まで探索できませんでした。今時分が使っているPCの限界を攻めて、8GBのメモリを与えてやりましたが無理でした。そこでもっと枝刈りを強化します。

さらに枝刈りを強化

そこで最後に入れた枝刈りがこちらです。

if((35 + (count($state->history) / 5)) > $state->life) return;

現在、単純に HP が 35 以下の枝を買っていますが、この枝刈りだと、 HP36 -> 42 -> 36 -> 40 のように、一旦増えた体力をまた減らして、そしてまた増えて、... みたいなルートまで探索しています。HPは、移動を重ねるほど増えることが期待されるので、 35 + (移動回数 / 5) 以下のHPになるような枝を刈るようにしました。

この枝刈りを施したプログラムを回したまま寝落ちしてしまったのですが、起きたら問題が解かれていました。

どうでもいいTips

この問題、勇者と魔王の位置関係的に、勇者->魔王 までたどり着くには偶数回の移動をする必要があります。つまり、魔王の隣に行くには奇数回の移動をする必要があります。一回の移動でHPは +1, -1 のどちらかが加算されます。初期HPが偶数ですので、奇数回の移動をした後のHPは必ず奇数になります。最後の魔王のマスに移動する時はHPの増減はありませんので、魔王と戦う時のHPはかならず奇数になりますよね。ということで、HP50ピッタリで魔王にたどり着くことはできず、かならずHP51になります。HP49、一見惜しいように見えますが、こう考えると、あとHPを2も確保しなければならないので、案外惜しくないことがわかります。

エクストラモードは?

時間がなくて解けていませんが、死神が移動するだけなので、ほぼおなじコードでクリアできるはずです。

基本的な方針は同じでPriority Queueを使えばよいと思います。ただ、メモリと実行時間の問題があるので、もう少し効率の良い枝刈りができるのではないでしょうか。

Code Quest の「圧縮ノ試練」を何のひねりもなく頑張ってクリアする

この記事は 文字 Advent Calendar 2017 5日目の記事です。果して「文字アドベントカレンダー」に投稿していいのか、よくわからないですが、開いていたので投稿させてもらうことにしました。

一つ前(3日目)の記事 → Twitterの文字数カウントの新仕様について - Qiita

Code Quest とは

geek-out.jp

GeekOutさんが公開した、プログラミング学習用ゲームみたいなものです。今回はこの中から「圧縮ノ試練」を解こうと思います。

圧縮の試練

Code Quest にある4つの試練の1つです。ノーマルとエクストラの2つのレベルがあります。

ノーマル

f:id:yoshiki_utakata:20171204153647p:plain

gg?aag??aa??gaa

パット見て (gggaa)3 で行けるなって気づいたので (g3a2)3 で7文字クリアです。圧縮の試練はプログラム書いて説かせるよりも自分で考えたほうが早いなと思いました。

エクストラ

f:id:yoshiki_utakata:20171204154016p:plain

g??g?a?gaa?g?agg?a?gga?ggaag?g?aggaa?gaa?g?aa

まずパット見た感じ、 ggaa あるいは aagg が多そうに見えたので、 (aagg)X または (ggaa)X *1 でなんとか圧縮できないかなと思いました。そこでなんとなく、 (aagg)X でまとめられそうなところを抜き出してみます

g??g                 <- ここはaaggの形にはできない
?a?g aa?g ?agg ?a?g  <- (aagg)4 にできる
g                    <- gがあまり
a?gg aag?            <- (aagg)2
g                    <- gがあまり
?agg aa?g aa?g       <- (aagg)3
?aa                  <- あまり

しかしこれでは g4(aagg)4g(aagg)2g(aagg)3a3 27文字で、15文字には全く届きません。。ただ、g が余るケースが多いので、 ((aagg)Xg)Y *2 の形に出来ないかなと、つまり ((aagg)3g)3 みたいなのを目指そうと思います。すると、

g??g
?a?g aa?g ?agg ?  <- (aagg)3g
a?gg a?gg aag? g  <- (aagg)3g
?agg aa?g aa?g ?  <- (aagg)3g
aa

こうできることに気づきました。最終的には g4((aagg)3g)3aa とできて15文字ピッタリでクリアできました。*3

圧縮の試練以外の問題もクリアしたので、随時記事にしていこうと思います。

*1:Xは数字

*2:X, Y は数字

*3:gg と g2 は文字数が同じなのでどちらで書いても良い