読者です 読者をやめる 読者になる 読者になる

オフトゥン大好き

惰眠系プログラマの作業ログで( ˘ω˘ ) スヤァ…

No.227 簡単ポーカー 解法

プログラミング 解説 アルゴリズム 有限オートマトン yukicoder

No.227 簡単ポーカー - yukicoderを解いた。

手札の役を作る処理は決定性有限オートマトンに置き換えられる。

開始状態はNO HANDとし、空のスタックを用意してソートした入力リストを先頭から順に積んでいく。ソートは同じ値をグループ化するために行なっているので昇順でも降順でも構わない。

  • 入力リストから取り出した値がスタックtopと同じならそのまま積む
  • 入力リストから取り出した値がスタックtopと異なるならスタックサイズを入力として状態遷移し、スタックを空にしてから値を積む

状態遷移表は次のようになる。TWO PAIRが必要ないのは入力リストから取り出した値がスタックtopと同じであるかぎり積んでいくのでTWO PAIR => FULL HOUSEという遷移はあり得ないため。

# \ s NO HAND ONE PAIR THREE CARD
2 ONE PAIR TWO PAIR FULL HOUSE
3 THREE CARD FULL HOUSE -

(#:スタックサイズ, s:現在の状態)

これを元にパスを作っていくと次のような状態遷移図が出来上がる。

f:id:nukosuke:20161023162936p:plain:w320

これをPerlで実装した。

sub trans {
  my ($state, $stack_size) = @_;
  if    ($state eq "NO HAND"    && $stack_size == 2) { return "ONE PAIR";   }
  elsif ($state eq "NO HAND"    && $stack_size == 3) { return "THREE CARD"; }
  elsif ($state eq "ONE PAIR"   && $stack_size == 2) { return "TWO PAIR";   }
  elsif ($state eq "ONE PAIR"   && $stack_size == 3) { return "FULL HOUSE"; }
  elsif ($state eq "THREE CARD" && $stack_size == 2) { return "FULL HOUSE"; }
  else  { return $state; }
}

my @A = sort { $a <=> $b } map { $_ + 0 } split ' ', <>;
my $state = "NO HAND";
my @stack = ();

foreach (@A) {
  if ($#stack >= 0 && $_ != $stack[$#stack]) {
    $state = trans($state, $#stack+1);
    @stack = ();
  }
  push @stack, $_;
}
print(trans($state, $#stack+1) . "\n");

関連記事

No.231 めぐるはめぐる (1) 解法

プログラミング アルゴリズム yukicoder 解説

No.231 めぐるはめぐる (1) - yukicoderを解いた。
面倒なので解説にあるとおり、一番簡単な解法を選ぶ。

一番効率のいい狩場に6時間行って,可能ならそれ,不可能なら不可能が一番楽です.

6時間で経験値3000000以上を得られるダンジョンが存在するかどうか、存在する場合は何行目のダンジョンかという情報が必要になる。
よって下記のように答えが求まる。

my $N   = <> + 0;
for (1..$N) {
  my ($G, $D) = map { $_ + 0 } split ' ', <>;
  if (($G - 30000 * $D) * 6 >= 3000000) {
    print("YES\n" . "$_\n" x 6);
    exit(0);
  }
}
print "NO\n";

JavaScriptテスト環境セットアップ: Node.js編

プログラミング Node.js テスト mocha chai sinon

Node.jsでテスト書くためのスタックとか設定を書く。
あくまで僕がいつも使ってるやつなので他にもっといいのあったら教えてください。

スタック

Node.jsのテストはだいたい次の4つのパッケージで完結してる。フロントのテストはもっとめんどくさい。

name description
mocha Node.jsのテストランナー
chai BDD/TDDスタイルでテストを書くためのライブラリ
sinon JavaScriptのモックライブラリ
sinon-chai chaiでsinonを使うためのchaiプラグイン
$ npm install mocha chai sinon sinon-chai -D

セットアップ

globalにテスト中に使う変数を入れておく

僕はいつもExpect形式で書くのだけど、そのままだとテストファイルの冒頭に以下のような設定を毎回書かないといけない。

const chai  = require('chai');
const sinon = require('sinon');
const sinonChai = require('sinon-chai');
chai.use(sinonChai);

それは面倒だし、メンテナンス性も悪いので別ファイルにまとめておいて、mocha起動時にそれを読み込ませる。例えば/test/globals.jsというファイルを作ってglobalにexpectを突っ込んでおく。

const chai  = require('chai');
const sinon = require('sinon');
const sinonChai = require('sinon-chai');

chai.use(sinonChai);
global.expect = chai.expect;



npm testを定義する

作成したglobal.jsをテスト前に読み込むにはpackage.jsonscripts:test項目に次のようにコマンドを割り当てておく。

"scripts": {
    "test:main": "$(npm bin)/mocha './test/**/*.spec.js' -r ./test/globals --recursive"
}

すると'./test/globals.js'がrequireされた状態でテストが開始するので書くファイルにexpectの宣言を書かずに使用できる。
こんな感じで。

const API = require('./api');

describe('create API client', () => {

    const client = new API();

    it('fetch user info successfully', done => {
        const user = client.getUserInfo();
        
        expect(user)
            .to.have.property('name')
            .that.is.a('string');

        done();
    });
});



Travis CI

追加でTravis CIの設定をして自動化する。
とはいってもここまでやるともう雑な.travis.ymlを用意するだけで良い。

language: node_js
node_js:
  - 6
  - 5
  - 4



次はフロント側のテストについて書く。

関連記事

npmプロジェクトを0からはじめるメモ - オフトゥン大好き

homebrew-caskの書き方とpull-requestの出し方

プログラミング mac homebrew homebrew-cask

GitHub - caskroom/homebrew-cask: A CLI workflow for the administration of Mac applications distributed as binaries

Mac使いならほとんどの人がお世話になっているHomebrew。 その拡張であるHomebrew Caskは以前なら別途インストールする必要があったが、色々ゴタゴタがあった末に本体に統合された模様。

僕は環境構築をできる限り自動化していてMacのプロビジョニングを行うにあたってはこれがないと結構面倒だ。もしHomebrew Caskのリポジトリに必要なCaskがなければ自分で作ってプルリクを出したら他にも幸せになる人がいるかもしれない。今回Windowsで使っていた3DモデリングソフトがいつのまにかMacに対応していたのでCaskに固めてみた次第。

Caskを作成する

まず最新のHomebrewが導入された状態で次のコマンドを実行する。hogehogeは作成するCaskの名前に読み替えてほしい。

$ brew cask create hogehoge

するとhogehoge.rbができるのでこれに必要な情報を書き加えていく。

cask 'hogehoge' do
  version ''
  sha256 ''

  url ''
  name ''
  homepage ''

  app ''
end
項目 内容
version アプリケーションのバージョンを指定する
sha256 改ざんや破損検知のためSHA256でイメージやアーカイブチェックサムを取る場合、ここにハッシュを入れておく。スキップする場合は:no_checkシンボルを指定する。
url ダウンロードするファイルのURL。CDNなどを利用していてhomepageで指定するドメインと異なる場合は# <ダウンロード先のドメイン> was verified as official when first introduced to the caskというコメントを一行上につけないとLintで弾かれる。
name アプリケーションの名前を指定する。
homepage アプリケーションのホームページを指定する。多くの場合はコーポレートサイトの製品ページなど。
app .appファイルの名前を書いておくと.dmgがマウントされた後にこれが/Applicationにコピーされる。

Macのアプリケーションは様々なインストール手段があるので、appでは対応できないことがある。例えば.dmgの中身が.pkg形式のインストーラだった場合。appではなくpkgを使用する。

また、この場合uninstallの項目にベンダーのIDを指定する必要があるが、これはhomebrew-caskのリポジトリにあるスクリプトで確認できる。

$ ./developer/bin/list_recent_pkg_ids
com.tetraface.Metasequoia.pkg
com.microsoft.OneDrive-mac
com.autodesk.mas.123ddesign
com.agilebits.onepassword-osx
com.microsoft.office.all.core.pkg.14.6.8.update
com.microsoft.office.all.dcc.pkg.14.6.8.update
com.microsoft.office.all.excel.pkg.14.6.8.update
com.microsoft.office.all.fix_permissions.pkg.14.6.8
com.microsoft.office.all.outlook.pkg.14.6.8.update
com.microsoft.office.all.powerpoint.pkg.14.6.8.update

最終的には以下のような状態になる。

cask 'hogehoge' do
  version '1.0.0'
  sha256 '0cd88d99379bdf8dfa42fd13ee970d8921f6d5eb3d892f76e4a7c76d68dc9e6d'

  # cdn.hogehoge.net was verified as official when first introduced to the cask
  url "https://cdn.hogehoge.net/download/Hogehoge-#{version}-Installer.dmg"
  name 'Hogehoge'
  homepage 'https://www.hogehoge.com/'

  pkg "Hogehoge-#{version}-Installer.pkg"

  uninstall pkgutil: 'com.pkg.hogehoge'
end

プルリクを出す

結構ガイドラインが細かったりするので目を通しておいた方がいいが、プルリク時のテンプレートにチェックボックスが用意されていて基本的にはこれを満たしていれば問題ない。

  • brew cask audit --download {{cask_file}}でエラーが出ないかどうか
  • brew cask style --fix {{cask_file}}でエラーが出ないかどうか
  • コミットメッセージにCaskの名前とバージョンを記載しているか
  • token referenceに沿って名前を付けているか
  • brew cask install {{cask_file}}でエラーが出ないかどうか
  • brew cask uninstall {{cask_file}}が正常に動くかどうか
  • すでに同じアプリケーションのプルリクが出ていたり過去に却下されていないか

本体のリポジトリにマージされるとbrew cask install hogehogeでインストールできるようになるので、ansibleのplaybookには

homebrew_cask_packages:
  - { name: hogehoge }

とか書いておくと新型に買い換えたときの環境構築で幸せになれる。

Facebookが公開した新しいJavaScriptパッケージマネージャ: Yarn

プログラミング JavaScript Node.js npm Yarn

元記事:

素敵やーん。

日本時間で12日、ちょうど日付が変わったくらいにFacebookが前述の記事を公開した。内容は「JavaScriptコミュニティで圧倒的に力を持っているnpmの代替となる新しいパッケージマネージャ、Yarnを作ったぜ!」というもの。代替といってもYarnはnpmクライアントを完全に置き換えるものではなくて、上位互換を持ったものらしい。

npmに対して、Facebookはかなり前から依存パッケージのインストールにかかる時間を問題視していたみたいだ。これは僕や周囲のエンジニアの反応とも一致するし極めて妥当な感じがする。今回のYarn開発に関するモチベーションはそれだけではなく、同社のJavaScriptコードベースがエンジニアの数と共に肥大化していったことも述べていて、開発にグーグルが協力していることからも大規模サービスにおいてコード管理がいかに負担になっているかを物語っていると思う。

アーキテクチャ

Yarnは3つのステップで依存パッケージのインストールを行う。グローバルキャッシュを用意してそこにパッケージを保存しておくのが従来のnpmクライアントとの違い。

  1. Resolution:
    npmレジストリへのリクエストによってそれぞれの依存関係を再帰的に解決していく。

  2. Fetching:
    次に、ダウンロードすべきパッケージがすでにグローバルキャッシュに存在しているかを確認し、もしなければtarballをグローバルキャッシュに保存する。これによってこのパッケージはオフラインでも利用可能になり、再びダウンロードする必要がなくなる。

  3. Linking:
    最後にYarnは必要なファイルをグローバルキャッシュからnode_modulesディレクトリにコピーする。

なるほど、という感じだ。

インストール

npmでインストールできる。

$ npm install -g yarn

使い方

次のようにnpmのサブコマンドに対応するらしい。個人的には、ここはあえて変えずにそのまま置き換えられるようにして欲しかった。

  • npm installyarn

  • npm install --save <name>yarn add <name>

速度比較

適当に選んだ自作nodeプロジェクトの依存項目のみ抜粋したものがこちら。

{
  "dependencies": {
    "es6-promise": "^4.0.5",
    "isomorphic-fetch": "^2.2.1",
    "qs": "^6.2.1"
  },
  "devDependencies": {
    "babel-preset-es2015": "^6.16.0",
    "chai": "^3.5.0",
    "karma": "^1.3.0",
    "karma-babel-preprocessor": "^6.0.1",
    "karma-chai": "^0.1.0",
    "karma-mocha": "^1.2.0",
    "karma-mocha-reporter": "^2.2.0",
    "karma-phantomjs-launcher": "^1.0.2",
    "karma-sinon-chai": "^1.2.4",
    "karma-webpack": "^1.8.0",
    "mocha": "^3.1.0",
    "phantomjs-prebuilt": "^2.1.12",
    "sinon": "^1.17.6",
    "sinon-chai": "^2.8.0",
    "ts-loader": "^0.8.2",
    "tslint": "^3.15.1",
    "typedoc": "^0.4.5",
    "typescript": "^2.0.3",
    "typings": "^1.4.0",
    "webpack": "^1.13.2"
  }
}

これをnpmとYarnで比較してみる。Yarnはキャッシュの効果も知りたいので1回目でコピーされたnode_modulesを削除してもう一度実行した結果もみる。

manager time result
npm npm install 44.20s user 11.06s system 28% cpu 3:11.75 total
Yarn (1回目) yarn 38.63s user 19.57s system 98% cpu 59.047 total
Yarn (2回目) yarn 23.46s user 11.32s system 116% cpu 29.961 total

Yarnはとにかく速い。そして、Yarnは2回目でダウンロードの時間が省けるのでさらに速くなる。ちなみにキャッシュは~/.yarn-cache/に保存されるようだ。

感想

速度が向上するのはいいことだけど、僕としてはオフラインでも作業できるようになるのが一番のメリットだと思う。 一度ローカルにnpmをミラーしようとして挫折したことがある。

とにかくYarn素敵。使わない理由はない。

GitHub - yarnpkg/yarn: 📦🐈 Fast, reliable, and secure dependency management for JavaScript.

関連記事