長野県松本市二泊三日の旅をした

働きながら旅をするシリーズ。今回は長野県松本市です。

なぜ松本市

博多に遊びに行った時に感じたことは「コンパクトシティ最高だなあ」でした。それ以来コンパクトシティに大きな可能性を感じていて、松本市もそうだと聞いて興味津々。

そしてネットで調べているとなぜかセンスの良さそうなお店がたくさん見つかるのでこれは行かねばならないと思ったので行ってまいりました。スーパーあずさで新宿から2時間半ほどです。

tabi-shiro

tabi-shiro.com

旅行するときはだいたいゲストハウスに泊まるようにしています。仕事しながらだと個室の方が良いと思いますが今回はそんなに仕事立て込んでないのでドミトリーにしました。

2段ベッドでしたが頑丈な作りだったので別の段の人の寝返りなどそんなに気になりませんでした。

このゲストハウスは夫婦で経営されていて、高橋歩さんの影響を受けているらしく、6月27日にご本人を招待してイベントを開催されるそうです。

https://www.evensi.jp/%E9%AB%98%E6%A9%8B%E6%AD%A9%E3%83%88%E3%83%BC%E3%82%AF%E3%83%A9%E3%82%A4%E3%83%96-%E9%A3%B2%E3%81%BF%E4%BC%9A2018-%E6%9D%BE%E6%9C%AC-%E3%81%82%E3%81%8C%E3%81%9F%E3%81%AE%E6%A3%AE%E5%85%AC%E5%9C%92/250695784www.evensi.jp

松本城

初日にゲストハウスにチェックインした後、17時ぐらいに訪問。お城の中には入れなかったので翌日再度訪れる。お城の天守閣に入ったのは初めてかもしれない。入場料が大人610円、階段が狭く、急な上に段差がそれぞれ微妙に違うので思ったよりも足腰の負担が大きいです。運動不足の方はお気をつけ下さい。

鉄砲に関する資料がたくさん展示されてました。

ロップ家

今回の訪問にはもう一つ大きな理由があって、それがロップ家に遊びに行く事です。ロップ家については主催者のブログをご覧ください。

https://travelife100.com/roppuyatohatravelife100.com

私が今回訪問した時期はちょうど副代表が滞在していたので遊びに行って来ました。かなり見晴らしの良い高台にある戸建住宅で、忙しい日々を忘れるには最高のロケーションでした。また遊びに行こうと思います。

丸山珈琲 信州MEDIA GARDEN

信州MEDIA GARDENという洒落乙な建物には感度の高いお店が入っています。愛想の良い店員さんに招かれて入店。ここはシングルオリジンのコーヒーを提供しているお店です。私はガブリエルさんのコーヒーを頼みました。味に関してはまあまあ酸味があって美味しいです。私はフレンチプレスで飲みましたがサイフォンでも提供してくれます。*1

ブックカフェ 栞日(shioribi)

sioribi.jp

ロップ家の副代表におすすめのカフェを聞いたところアミジョクと栞日をおすすめして頂いたので行って来ました。残念ながらアミジョクは定休日だしたがかわりに栞日でゆったりとした時間を過ごしました。

ちなみに松本市にやたらとセンスの良い個人商店が多い理由として外部から商売をはじめにやってくる人が多いらしく、そのきっかけとなっているのが栞日らしいです。

そんなわけで松本市のイマが濃縮されている場所だと思いますのでもし旅行される方がいればお立ち寄りする事をお勧めします。

松本ブルワリー

立ち飲み屋さんですがなぜか営業時間が13時から19時。2階には椅子あります。こちらのお店で松本市について色々と情報収集をしました*2。

もつ焼・煮込み 河内屋 駅前店

やたらと美味しいレバーが出て来てびっくり。アミレバは絶品。ネギレバはごま油がとんでもない存在感を放つ一品でした。

こちらのお店は最近この辺りで勢力を拡大中のお店らしいです。

ばんざい屋

馬刺し、山賊焼き、ソーセージを頂きました。山賊焼がおいしく、ボリュームがあって最高です。

ちなみに風林火山という居酒屋の姉妹店です。地元の方に人気があるようです。

スタンディング 8オンス

松本ブルワリーで紹介してもらい訪問。ノーチャージでジントニック1杯300円っていう価格設定が尋常ではないお店です。

どうやらお隣が酒屋らしく、それで原価が安いとか。

エオンタ

正統派のジャズ喫茶です。こちらも松本ブルワリーで紹介してもらい訪問。お酒も出ます。店内には高音質の JAZZ が流れていて優雅な時間を味わいました。

まとめ

というわけで松本市を2白3日して来ました。松本市は想定してたよりも街全体のセンスが良かったです。

あと tabi-shiro がポテンシャルを感じました。大体のゲストハウスは単純に宿泊所なんですが、旅人同士の HUB になりそうな、そんな雰囲気がありました。まあ宿泊者の主義とか利用目的に依るんでしょうけど。

ロップ家は想像よりものどかな場所でした。時々都会の喧騒に疲れた人が訪れて傷を癒す、本当に素敵な場所でした。利用するかどうか、じっくり検討したいと思います。

というわけで今回の旅でまたひとつ可能性を感じる街を発見しました、そんな感じです。

*1:試験管とビーカーみたいなかっこいい器具で抽出する

*2:主に飲み屋

フィボナッチ数列で学ぶ Dynamic Programming

あらすじ

最近求職活動をしているのですが、ホワイトボードにフィボナッチ数列を書いて下さいって言われた時に備えておこうと思いました。しばらく書いてないとどうやって書いていいかわからなくなるので焦る。

そういうわけでフィボナッチ関数の記事を書いていたらいつのまにか Dynamic Programming の記事っぽくなった。

要約

フィボナッチ関数を以下の3段階でグレードアップしていきます。こういう手順踏むと　Dynamic Programming ぽいです。という雰囲気をお伝えしたいと思います。

• とりあえず素直に再帰処理で書いてみる
• メモアイズしつつ再帰処理
• ボトムアップして再帰処理を無くす

フィボナッチ数列について

イタリアの数学者フィボナッチにちなんで名付けられた数列です。 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 みたいななんかそんなの。

A: とりあえず素直に再帰処理で書いてみる

オーソドックスな書き方は以下の通り。だいたいの面接はここまでで十分です。面接官はホワイトボードにコードを書き出せるかどうかしか見ない気がします。

// const _ = require('lodash');
let count = 0;
function fib(n) {
  count++;
  if (n === 1 || n === 2) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

// const numbers = _.times(10, i => fib(i+1));
console.log(fib(20), count);

結果は以下の通り

6765 13529

さて、これだとO(2**n) なので n の数が増えると大変な事になります。 というわけで memoise*1 します。

B: メモアイズしつつ再帰処理

memoize しましょう

const _ = require('lodash');
let count = 0;

function fib(n, memo) {
  count++;
  if (memo[n]) {
    return memo[n]
  }

  let result;
  if (n === 1 || n === 2) {
    result = 1;
  } else {
    result = fib(n-1, memo) + fib(n-2, memo);
  }
  memo[n] = result;
  return result;
}

console.log(fib(20, []), count);

実行結果

6765 37

関数を呼び出す関数が劇的に減りました。これでどんな n が来ても勝てる！

とはなりません。

再帰処理は n の数を const result = fib(10000, []); みたいに増やすと以下のようなエラーが出ます。さてどうしよう。

function fib(n, memo) {
            ^

RangeError: Maximum call stack size exceeded

C: ボトムアップして再帰処理を無くす

というわけでさっきまでは関数呼んで、呼ばれた関数がメモアイズしている値を返していたのですが時々重複した fib(n) を呼び出しています。これを解消してみます。

const _ = require('lodash');

function fib(n) {
  const memo = []; 
  if (n === 1 || n === 2) {
    return 1;
  }
  memo[1] = 1;
  memo[2] = 1;

  for (let i = 3; i <= n; i++) {
    memo[i] = memo[i-1] + memo[i-2];
  }
  return memo[n];
}

console.log(fib(20), count);

実行結果。 n = 10000 にしても RangeError でなくなりました。やったね。

6765 1

まとめ

というわけで以下のようにアルゴリズムを改良したことによって処理が高速になりました。

A: 再帰処理による関数の呼び出し回数が尋常ではない B: Memoize によって関数を呼び出す回数が激減 C: トップダウンからボトムアップの処理に変更

というわけでフィボナッチ関数の記事書いてたらいつの間にか Dynamic Programming の記事っぽくなりましたとさ。おしまい。

*1:momorise ではない

memoize するときに array in array な table を作りたい

最近英語の勉強するために英語でアルゴリズムを解説している動画を youtube で見ています。 計算量が増えないように memorize する事が多いようです。 さて、memoize 用の連想配列を頑張って書くのいやなので([[],[],[],[]]みたいなの)関数にしてみました。

こんな感じで良いかな？ m, n が 0 から始まるのか 1 から始まるのかによって m, n の箇所が変わると思いますが、まあ少しぐらい多めにマッピングしておいてもいいのかな。もっと良い書き方、もしくはライブラリ化されているのをご存知の方はぜひご教授ください。

const _ = require('lodash');

const getArrayInArray = (m, n) => _.times(m + 1, () =>
  _.times(n + 1, _.constant())
);

const memoTable = getArrayInArray(2, 3); 

memoTable[2][3] = "memo";
console.log(memoTable[2][3]);

Redux について思う事

あらすじ

最近 React 案件の商談が多いのですが「Redux で書かれたビジネスロジックのテストもお願いしたい」とか言われて、んん？となったのでなんとなくブログにします。

ビジネスロジック と Redux が混在する？何故？

Redux はおおざっぱにいうと以下の概念で動きます。

Actions -> Reducers -> Store

そして Redux の3原則は以下のとおり

• Single source of truth
• State is read-only
• Changes are made with pure functions

そう、Redux は基本的に pure function を使います。そして pure function は以下のような関数の事です

function square(x) {
  return x * x;
}

function squareAll(items) {
  return items.map(square);
}

そして以下は pure function ではないです。

function square(x) {
  updateXInDatabase(x);
  return x * x;
}

function suareAll(items) {
  for (let i = 0; i < items.length; i++) {
    items[i] = square(items[i]);
  }
}

これは作者が動画で説明しています

https://egghead.io/lessons/react-redux-pure-and-impure-functions

pure function だと何がどれぐらいうれしいのか、という話は私はあまり関心がないので気になる方はリンク先の動画をたくさんご覧ください。

いずれにせよ reducer も action も pure function になると私は思っているので「Redux で書かれたビジネスロジック」と言われてもピンとこない。私の解釈だとビジネスロジックは Action の前で実行を終えているはず。

[Bussiness Logic] -> [Actions -> Reducers -> Store]

なので Bussiness Logic は分離してテストを書けば良いのではないかなあと思うわけです。つまり actions.js には pure function だけを書く。

ただし、私の考えが公式サイトの Tutorial とそぐわない

公式サイトにある Async function の Tutorial には fetchPosts という関数が actions.js に書かれています。

https://redux.js.org/advanced/async-actions

そもそも非同期処理は pure function なのか？

そもそも非同期処理は Pure function ではないはず。なのでそれを dispatch するのは問題なのではないかなあと思います。非同期処理が終わってから結果を dispatch すればいいはず。なんですがそれをせずに middleware で Redux の非同期処理については私は疑問があります。似た考え方をする人もいるようですし

React+Reduxで簡単な勉強会イベント検索アプリを作って公開してみる - Qiita

そうでない方もいると思います。

Reduxのmiddlewareを積極的に使っていく - Qiita

メリットとデメリットの捉え方が人それぞれだし状況も違うのでどちらが優れているとも思いませんが、この辺りって2018年現在ではどのような論調になってるんでしょう？

redux-saga

私が redux を使わないで Single Page Application を作る Tutorial - Qiita を書いたのはこれがきっかけです。どうしても redux-saga とはそりが合いませんでした。

もしかすると冒頭の「Redux で書かれたビジネスロジックのテストもお願いしたい」というのは redux-saga の事だったのかなあ？それはいやだなあ。

もちろんメリットがあるのであれば頑張りますが、物事を複雑にしがちだし、対して得られる恩恵が少なそう、というのが私の redux-saga に対する見解です。こういう事書くと使いこなせいお前が悪い、という話にもなりそうですがそう思って頂いて結構です。

まとめ

そんなわけで Redux はすごくシンプルなのでミニマリスト志向な私はとても好きな概念なんですが非同期処理とかビジネスロジックとかがやってきて私の好きな Redux で無くなるのがいや、そんな感じ。

Youtube で MIT OpenCourseWare でやっている Programming for the Puzzled が面白い

あらすじ

そろそろ英語の勉強しないといけないのでとりあえず Youtube で英語に慣れよう、エンジニアだしMITの動画でも見てみようかな。と思って見たらえらい面白かったので講義の内容をなんとなくブログにします。

www.youtube.com

問題: coin row game

コインを集めるゲームが題材です。例えば以下のようにコインが並んでいるとすると全部集めるといくらになるでしょうか？

[14, 3, 27, 4, 5, 15, 1]

答えは以下の通りです。

const _ = require('lodash');
const result = _.sum([14, 3, 27, 4, 5, 15, 1]);
console.log(result); // 69

とはえいこれではゲームにならないので制約を加えます。拾ったコインのすぐ次のコインは拾えない です。この制約下においてもっとも大きな値となるようにコインを集める関数を考える、というゲームです。

coins([14, 3, 27, 4, 5, 15, 1]) // 14 + 27 + 15 = 56
coins([14, 3, 27, 4, 5, 15, 11]) // 14 + 27 + 5 + 11 = 57

動画では考え方と解法が解説されています。言語は Python ですが私は Node.js で書いています。

サブセットを用意する

サブセットという概念を説明します。たとえば [1, 2] からは 2の2乗のサブセットが作成できます。

[1, 2] => {}, {1}, {2}, {1, 2}

[1, 2, 3] からだと2の3乗のサブセットができます。コードで説明したほうが分かりやすいので以下をご覧ください。

function getSubsets(items) {
  var subset = [];
  helper(items, subset, 0);
}

function helper(items, subset, i) {
  // n 番目の階層に到着したら標準出力
  if (items.length === i) {
    console.log(subset);
  }
  // 分岐が 
  else {
    // empty の場合
    subset[i] = null;
    helper(items, subset, i + 1);

    // 数値を代入する場合
    subset[i] = items[i];
    helper(items, subset, i + 1);
  }
}

getSubsets([1, 2, 3])

上記を実行すると以下のようになります。これを見ればコインを拾ったか、スキップしたかがわかると思います。

[ null, null, null ]
[ null, null, 3 ]
[ null, 2, null ]
[ null, 2, 3 ]
[ 1, null, null ]
[ 1, null, 3 ]
[ 1, 2, null ]
[ 1, 2, 3 ]

Pick or Skip

この coin row game で実行できる事は基本的に Pick するか、 Skip するかの2つしかありません。これを 0 と 1 で表現します。

Skip: 0
Pick: 1

Pick or Skip を2進数で表現すると以下のようにすることができます。

0000
0001
0101
1111

さて、先頭の数字から順番に処理する際に、基本的に以下の選択肢があります。

• 直前のコインを Pick している場合 => Skip only
• 直前のコインを Pick していない場合 => Pick or Skip

上記の条件を考えると先ほど2進数で表現した Pick or Skip では制約に違反しているものがあります。一番下の 1111 です。

という事で並んだコインを Pick or Skip したサブセットを全て取得して、制約に違反していないサブセットから拾ったコインの合計値を求めると問題を解決できそうです。 このロジックでも問題は解決できますが、コインの数が増えれば増えるほど分岐する tree が深くなっていきます。ネズミ算式に増えるイメージです。

もしコインが 50 個並んでいたらサブセットの数は以下の通りです。

> 2 ** 50
1125899906842624

必要なサブセットだけを取得する

今回のゲームは コインを Pick した後は必ずスキップ する必要がありますので取得しなくても良いサブセットが存在します。

ということでこれを踏まえてサブセットを取得する方法を考えます。

完成

いわゆる再帰呼び出しを使って以下のように書けます。

function coins(row, table) {

  // no coins
  if (row.length == 0) {
    table[0] = 0;
    return {result: 0, table}
  // one coin
  } else if (row.length == 1) {
    table[1] = row[0];
    return {result: row[0], table};
  }

  // pick the coin, and skip next coin -> slice(2)
  const pick = row[0] + coins(row.slice(2), table).result

  // skip the coin -> slice(1)
  const skip = coins(row.slice(1), table).result;

  const result = _.max([pick, skip]);
  table[row.length] = result;

  return { result, table };
}

const coinRow = [14, 3, 27, 4, 5, 15, 1];
const {result, table} = coins(coinRow, {});

console.log({result, table});

結果は以下の通り。result が求めている答えです。

{ 
  result: 56,
  table: { '0': 0,
     '1': 1,
     '2': 15,
     '3': 15,
     '4': 19,
     '5': 42,
     '6': 42,
     '7': 56 
  } 
}

動画では traceback する関数を用意して table を解析しています。興味がある方は動画をご覧ください。

まとめ

MIT の動画はとても面白いのでおすすめです。

ブロックチェーンはじめました

あらすじ

スマートコントラクトからマネーのオイニーがしてきたので素振りしておきました。

やってみた

以下を参考にやってみた

Full Stack Hello World Voting Ethereum Dapp Tutorial — Part 1 | by Mahesh Murthy | Medium

mkdir practice-dapp && cd $_
yarn init -y
yarn add solc --save
yarn add web3@0.20.6 --save
mkdir contracts script
touch contracts/Voting.sol script/vote.js

create contracts/Voting.sol

pragma solidity ^0.4.18;
// We have to specify what version of compiler this code will compile with

contract Voting {
  /* mapping field below is equivalent to an associative array or hash.
  The key of the mapping is candidate name stored as type bytes32 and value is
  an unsigned integer to store the vote count
  */

  mapping (bytes32 => uint8) public votesReceived;

  /* Solidity doesn't let you pass in an array of strings in the constructor (yet).
  We will use an array of bytes32 instead to store the list of candidates
  */

  bytes32[] public candidateList;

  /* This is the constructor which will be called once when you
  deploy the contract to the blockchain. When we deploy the contract,
  we will pass an array of candidates who will be contesting in the election
  */
  function Voting(bytes32[] candidateNames) public {
    candidateList = candidateNames;
  }

  // This function returns the total votes a candidate has received so far
  function totalVotesFor(bytes32 candidate) view public returns (uint8) {
    require(validCandidate(candidate));
    return votesReceived[candidate];
  }

  // This function increments the vote count for the specified candidate. This
  // is equivalent to casting a vote
  function voteForCandidate(bytes32 candidate) public {
    require(validCandidate(candidate));
    votesReceived[candidate] += 1;
  }

  function validCandidate(bytes32 candidate) view public returns (bool) {
    for(uint i = 0; i < candidateList.length; i++) {
      if (candidateList[i] == candidate) {
        return true;
      }
    }
    return false;
  }
}

create script/vote.js

const fs = require('fs');
const solc = require('solc');
const Web3 = require("web3");

main();

function sleep(ms = 0) {
  return new Promise(r => setTimeout(r, ms));
}

async function main(err, blockchain) {

  // ganeche を起動しておく
  const web3 = new Web3(new Web3.providers.HttpProvider("http://localhost:7545"));

  // 登録済みのアカウントを確認
  const accounts = web3.eth.accounts;
  console.log(accounts);

  // compile 開始
  const code = fs.readFileSync('./contracts/Voting.sol').toString();
  const compiledCode = solc.compile(code);
  const abiDefinition = JSON.parse(compiledCode.contracts[':Voting'].interface);
  const byteCode = compiledCode.contracts[':Voting'].bytecode;

  // deploy 開始
  const VotingContract = web3.eth.contract(abiDefinition);
  const deployedContract = VotingContract.new(
    ['Rama','Nick','Jose'],
    { data: byteCode, from: web3.eth.accounts[0], gas: 4700000 }
  )

  // deploy 中
  while (!deployedContract.address) {
    console.log("wait a minute...");
    await sleep(1000);
  }

  // deploy 完了
  console.log(deployedContract.address);

  // 投票開始
  const contractInstance = VotingContract.at(deployedContract.address)

  // 投票数を見る view なので gas を消費しない(transaction が発生しない)
  let result = contractInstance.totalVotesFor.call('Rama');
  console.log(result);

  // transaction が発生する
  contractInstance.voteForCandidate('Rama', {from: web3.eth.accounts[0]});
  contractInstance.voteForCandidate('Rama', {from: web3.eth.accounts[0]});
  contractInstance.voteForCandidate('Rama', {from: web3.eth.accounts[0]});
  result = contractInstance.totalVotesFor.call('Rama').toLocaleString();
  console.log(result);
}

感想

version 指定しないで yarn add web3 すると 1.0 の version をインストールするけどこれは不安定なのでお気をつけ下さい。 そして web3 の 0.2.x 系のドキュメントはここ

JavaScript API · ethereum/wiki Wiki · GitHub

gyp ERR! stack Error: Python executable \"/usr/local/bin/python\" is v3.6.4, which is not supported by gyp.

yarn add sha3 しようとすると gyp が Python のバージョンに対して不服がある模様。

gyp ERR! stack Error: Python executable \"/usr/local/bin/python\" is v3.6.4, which is not supported by gyp.

https://github.com/Homebrew/homebrew-core/issues/24869#issuecomment-371765216

上記のコメントを参考にして npmrc に追記した。

echo "python = /usr/bin/python" >> ~/.npmrc

おしまい