あいつの日誌β

人生はお酒があれば何とかなります。 drunkard.tokyo

Bash から Zsh を起動しようとすると command not found: complete

以下のようなメッセージが出てくる

$ zsh
/Users/okamuuu/.anyenv/libexec/../completions/anyenv.bash:16: command not found: complete
/Users/okamuuu/.anyenv/envs/ndenv/libexec/../completions/ndenv.bash:16: command not found: complete
/Users/okamuuu/.anyenv/envs/pyenv/libexec/../completions/pyenv.bash:16: command not found: complete
/Users/okamuuu/.anyenv/envs/rbenv/libexec/../completions/rbenv.bash:16: command not found: complete

このようにしたら治りました

export PATH="$HOME/.anyenv/bin:$PATH"
- eval "$(anyenv init -)"
+ eval "$(anyenv init - zsh)"

screen が起動直後に screen is terminating してしまう

screen terminates immediately

screen 起動直後に screen が終了してしまう

okamuuunoMacBook-Pro:run okamuuu$ screen
[screen is terminating]

原因を調査するために .screenrc の項目を一つづつコメントアウトしたところ shell zsh に問題があった

startup_message off 
defscrollback 10000
escape ^Tt 
vbell off 
hardstatus alwayslastline " %'%-w%{=b bw}%n %t%{-}%+w"
autodetach on
defutf8 on
bind ^k kill
shell zsh 

zsh を実行すると以下のようなエラーが表示される。screen が何も言わずに終了するのはつらいですね。

$ zsh
dyld: Library not loaded: /usr/local/opt/gdbm/lib/libgdbm.5.dylib
  Referenced from: /usr/local/bin/zsh
  Reason: image not found
Abort trap: 6

以下のコマンドを実行したら治った

brew reinstall zsh && brew unlink zsh && brew link zsh

おしまい

Hachiojipm#72 に参加してきた

八王子で開催されるエンジニアの飲み会に参加してきました。73回目の開催だそうです。今回の会場はペルー料理の Misty です。

f:id:okamuuu:20180603115044j:plain

雑談

いつものようにお酒をのみながらプログラムの話をしました。

LT

お酒飲んでいたので記憶がぼんやりとしているのですがみなさんのお話は大体こんな感じ。敬称略です。

hkoba@cpan

Perl を使って Template Engine をつくる仕事をしているとの事。

Kikuchi.N et al.

化学のプログラミングで Perl を使い始めたとの事。お気に入りのタンパク質を紹介してくれました。

f:id:okamuuu:20180603115118j:plain

shim0mura

サーバレスアーキテクチャに興味があるけど AWS のサービス多すぎてとっつきづらいとの事。

f:id:okamuuu:20180603115234j:plain

私が Tutorial を書いていますのでぜひご覧下さい。

kkotaro0111

動画編集での字幕のお話。動画編集している人にとって字幕の処理は作業が多いらしく、いろいろと悩ましい問題らしいです。

macopy

kuiperbelt のお話。そこから派生して Yanca では websocket ではブラウザがパケットが全て転送されるまえにパケットを廃棄してしまうときがあるのでデータを受け取れない時があるとのこと。対策としてはアプリケーション側でシーケンスを保持して抜けている場合は Ajax などで補う必要があるので面倒だとか。

kei kamikawa

Go の Coroutines のテストがつらいのでこうやって書きたいとのこと。Coroutines で書かれたコードのリファクタリングに悪戦苦闘しているそうです。大変そう。

okamuuu

最近将棋にはまっていて将棋のアプリを作っています。 https://okamuuu.github.io/react-shogi-board/

uzulla

PHP の framework swoole を紹介。PHP の特徴として非同期処理を書くのは辛いとのこと。なんですがこの framework は簡単に書ける。すごい。怖い。

uzulla さん曰く、「日本でこの framework を使っているのを自分以外に知らない」とのこと。

makamaka_at_donzoko

課金API の Stripe が開発者フレンドリーですごく良いとのこと。ちなみにLTを始めますよ、と言われた瞬間に真っ白なPowerPoint を開いて資料を作成していました。

f:id:okamuuu:20180602201721j:plain

まとめ

以前 hachiojipm で Yancha というチャットを開発されていたのですがその時に困った事を聞けてよかったです。自分が実装する番が来たら思い出そうと思います。

居酒屋でお酒を飲みながらLTする、というスタイルは hachiojipm ならではだと思うので、そういう勉強会に参加した事がない方は一度参加するとたのしいと思います。

おしまい。

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

Puzzle 3: You Can Read Minds (with a little calibration) も面白かったのでなんとなくブログにします。

www.youtube.com

クイズ

教授が助手に命じて生徒たちに52枚のトランプカードからランダムに5枚引いてもらう。助手はそのうち4枚を順番に教授に見せて、残り1枚がどのカードなのかを推測し、それを当てて見せた。

教授曰く、これはアルゴリズムを使っている。どんな方法を使えば良いだろうか?

隠すカードを選ぶ

選ばれた5枚のうち、4枚を並べて表示する。この方法によって助手は教授に最後に隠されたカードに関する情報を伝えています。

単純に4枚数のカードを並び替えると 4! = 4 * 3 * 2 * 1 = 24 通り の情報を付与できますが、52枚のカードから4枚引くと、残りのカードは48通りです。この差分を埋めるためにどんな工夫ができるのでしょうか?

最初のポイントは最初に並べるカードと隠すカードを選ぶことです。5枚のカードを選んだ時点で必ず同じ絵柄のカードが選ばれます。最初に並べるカードと隠すカードの絵柄を揃える事で隠されたカードの絵柄を特定する事ができます。

この時点で残り12通りに特定できます。(1から13までの数字のうち、いずれかの数字は最初に並べるカードで使用されている)

ただし、残り3枚のカードを使って情報を付与できるのは 3! = 3 * 2 * 1 = 6通り です。

最初のカードと隠すカードの数字の差を考える

例えば以下のような配置ではどうでしょう。この場合は絵柄のペアが diamond だけなので必然的に最初に並べるカードと隠すカードは 3_diamond, 5_diamond のみとなります。

3_diamond, 1_heart, 6_spade, 4_club, 5_diamond

そういえば 3 と 5 の差は2です。このように差が1から6の場合は残りの3枚の並び方に意味を持たせるとマジックは成立しそうです。では以下の場合はどうでしょう。

1_diamond, 1_heart, 6_spade, 4_club, 12_diamond

ところで最初のカードと隠すカードの数字の差は普通に考えれば1 から 12 なので 11 です。

しかし、考え方を変えると、12 から 1 まで差はいくつでしょう?13を超えた場合は1に戻ると考えれば12と1の差は 2 です

もし、最初に並べるカードと隠すカードが2と7の場合は最初に並べるカードは2です。もし2と9の組み合わせの場合は9です。

残り3枚に意味をもたせる

ここまでくればあとは簡単です。数字の大きさによって残り3枚数を並べてみましょう。例えば Small, Medium, Large を以下のように並べると良いでしょう。

S M L => 1
S L M => 2
M S L => 3
M L S => 4
L S M => 5
L M S => 6

同じ絵柄の場合はポーカーのように スペード、ハート、ダイヤ、クラブ の順番にすればよいでしょう。

実装

少し雑ですがこのような感じになりました。

const _ = require('lodash');

function _num(card) {
  return parseInt(card.split('_')[0], 10);
}

function _suit(card) {
  return card.split('_')[1];
}

const suitOrders = ["Spade", "Heart", "Diamond", "Club"].reverse();

function _order(a, b) {
  if (_num(a) === _num(b)) {
    const aIndex = suitOrders.indexOf(_suit(a));
    const bIndex = suitOrders.indexOf(_suit(b));
    return aIndex - bIndex;
  }
  return _num(a) - _num(b);
}

function getCards() {
  return _.flatten(
    _.times(13).map(n => ["Spade", "Heart", "Diamond", "Club"].map(suit => `${n+1}_${suit}`))
  )
}

function getSameSuitCards(cards) {
  const suitOf = {
    "Spade": null,
    "Heart": null,
    "Diamond": null,
    "Club": null,
  };

  let pair;
  for (let i = 0; i < cards.length; i++) {
    const card = cards[i];
    const suit = _suit(card);
    if (suitOf[suit]) {
      return [suitOf[suit], card];
    }
    suitOf[suit] = card;
  };

  throw new Error("omg");
}

function selectShouldHiddenCard(cards) {
  // 先頭のカードが大きい
  if (_num(cards[0]) > _num(cards[1])) {
    return _num(cards[0]) - _num(cards[1]) > 6 ? cards[1] : cards[0];
  }
  return _num(cards[1]) - _num(cards[0]) > 6 ? cards[0] : cards[1];
}

function getDiffNumber(firstCard, hiddenCard) {
  if (_num(hiddenCard) > _num(firstCard)) {
    return _num(hiddenCard) - _num(firstCard);
  }
  return 13 - _num(firstCard) + _num(hiddenCard);
}

function reordereThreeCards(threeCards, diff) {
  const indexes = {
    1: [0, 1, 2],  // S, M, L
    2: [0, 2, 1],  // S, L, M
    3: [1, 0, 2],  // M, S, L
    4: [1, 2, 0],  // M, L, S
    5: [2, 0, 1],  // L, S, M
    6: [2, 1, 0]   // L, M, S
  }[diff]

  return indexes.map(i => threeCards[i]);
}

function main() {
  const cards = getCards();

  const fiveCards = _.sampleSize(cards, 5);
  console.log({fiveCards});

  const sameSuitCards = getSameSuitCards(fiveCards);
  console.log({sameSuitCards});

  const hiddenCard = selectShouldHiddenCard(sameSuitCards);
  console.log({hiddenCard});

  const firstCard = _.without(sameSuitCards, hiddenCard)[0];
  console.log({firstCard});

  const restThreeCards = _.without(fiveCards, firstCard, hiddenCard);
  console.log({restThreeCards});

  const orderedThreeCards = restThreeCards.sort(_order);
  console.log({orderedThreeCards});

  const diff = getDiffNumber(firstCard, hiddenCard);
  console.log({diff});

  const reorderedThreeCards = reordereThreeCards(restThreeCards, diff);
  console.log(reorderedThreeCards);
}

main();

実行結果

{ fiveCards: [ '7_Diamond', '13_Club', '6_Club', '3_Club', '12_Diamond' ] }
{ sameSuitCards: [ '13_Club', '6_Club' ] }
{ hiddenCard: '6_Club' }
{ firstCard: '13_Club' }
{ restThreeCards: [ '7_Diamond', '3_Club', '12_Diamond' ] }
{ orderedThreeCards: [ '3_Club', '7_Diamond', '12_Diamond' ] }
{ diff: 6 }
{ reorderedThreeCards: [ '12_Diamond', '7_Diamond', '3_Club' ] }

上記の結果ですと最初のカードが13のクラブなので最後に隠されたカードもクラブです。そのあとに続くカードは L, M, S の順番なので 13 との差は6です。13 の次は 1 なので、最後に隠されたカードはクラブの6です。

まとめ

最近 MIT OpenCourseWare の Programming for the Puzzled を気に入っていて良く見ています。無料でこういう動画が見れるなんて本当にいい時代になったものです。というわけで他にも面白い動画がないか探索しようと思います。

react-dnd の使い方

あらすじ

react-dnd を使いました。いつものように、きっと思い出せなくなる自分の為にTutorial を書きました。

つくるもの

  • 9マスの BOX を左から右へ向かってコマを進める。
  • コマは最大2マス進めるが、後ろには戻れない。
  • コマを選択する(isDragging)と、コマの右隣かもう一つ隣のマスが光る
  • コマを移動可能なマスへ移動させる(drop)と、コマの移動が完了する。
  • 最終的に一番右のマスへ移動すれば終了となる

完成したものはこちら: https://okamuuu.github.io/tutorial-react-dnd/

ソースコード: GitHub - okamuuu/tutorial-react-dnd

大まかな流れ

src/components の配下に Stateless Component である Board, Box, Piece を配備します。

次に src/Game にそれらを配備して盤上のマスの上にあるコマを移動させる処理を用意します。この時、move, canMove といった関数を用意します。state 管理には react-easy-state を使用します。理由は後述します。

この後 Board, Box, Piece を Draggable で Droppable な Component に変換する為に react-dnd で wrap して src/Game.js に再配備します。

この wrap されたコンポーネントが Drag and Drop が行われる際にイベントを発火しているのですが、それぞれのイベントがコンポーネント毎に発火しています。Game に state を持たせてしまうと、このイベントが発火するポイントまで state を伝播させるのが大変です。とはいえ redux を導入するほどの規模ではないので react-eazy-state を使っています。

準備

create-react-app tutorial-react-dnd && cd $_
mkdir src/components
touch src/components/{Board.js,Box.js,Piece.js}
touch src/Game.js
yarn add styled-components react-dnd react-dnd-html5-backend react-easy-state lodash --save

Stateless な components を用意する

とりあえず src/components/{Board.js,Box.js,Piece.js} を用意します。

create src/components/Board.js

import styled from "styled-components";

const baseColor = "#666";

export default styled.div`
  margin: 0 auto;
  width: 450px;
  height: 50px;
  color: #fff;
  border-bottom: 1px solid ${baseColor};
  border-left: 1px solid ${baseColor};
  display: grid;
  grid-template: repeat(1, 1fr) / repeat(9, 1fr)
`

create src/components/Box.js

import styled from "styled-components";

const borderColor = "#666";

export default styled.div`
  background-color: #eee;
  border-top: 1px solid ${borderColor};
  border-right: 1px solid ${borderColor};
  font-family: Helvetica;
  font-weight: bold;
  font-size: 1em;
  display: flex;
  justify-content: center;
  align-items: center;
`

create src/components/Piece.js

import styled from "styled-components";

export default styled.div`
  cursor: pointer;
  padding: 20px;
  background-color: #222;
`

edit src/App.js

import React, { Component } from 'react';
import Board from './components/Board';
import Box from './components/Box';
import Piece from './components/Piece';

class App extends Component {
  render() {
    return (
      <div style={{padding: "15px"}}>
        <Board>
          <Box><Piece /></Box>
          <Box />
          <Box />
          <Box />
          <Box />
          <Box />
          <Box />
          <Box />
          <Box />
        </Board>
      </div>
    );  
  }
}

export default App;

動作確認。このような画面になっていると思います。

f:id:okamuuu:20180523231819p:plain

Business Logic を追加

Drag And Drop を実装する前に、ひとまずクリックした箇所にコマを移動させるようにします。

create src/Game.js

import React, { Component } from 'react';
import { store, view } from 'react-easy-state';
import _ from 'lodash';

import Board from './components/Board';
import Box from './components/Box';
import Piece from './components/Piece';

const state = store({ position: 0 });

function move(position) {
  if (canMove(position)) {
    state.position = position;
  }
}

function canMove(position) {
  return position > state.position && position - state.position <= 2;
}

class Game extends Component {

  render() {
    const boxes = _.times(9, n => {
      const piece = state.position === n ? <Piece /> : null;
      return (<Box onClick={() => move(n)} key={n} position={n}>{piece}</Box>)
    });

    return (
      <Board>
        {boxes}
      </Board>
    );
  }
}

export default view(Game);

edit src/App.js

import React, { Component } from 'react';
import Game from './Game';

class App extends Component {
  render() {
    return (
      <div style={{padding: "15px"}}>
        <Game />
      </div>
    );  
  }
}

export default App;

クリックするとコマが移動します。右側にしか移動できないので右端まで進んだらリロードしてください。

コンポーネントをドラッグする

というわけでやっと本題です。大まかに説明すると以下のような作業が発生します。

  • Board に DragDropContext を適用する
  • Piece を Droaggable な component にする
  • Box に Draggable な component を drop したらイベントを発火させるようにする

意外と記述する内容が多いので、まずは コマをドラッグする だけをやってみます。

diff --git a/src/Game.js b/src/Game.js
index 97efcd5..42726ef 100644
--- a/src/Game.js
+++ b/src/Game.js
@@ -6,6 +6,9 @@ import Board from './components/Board';
 import Box from './components/Box';
 import Piece from './components/Piece';
 
+import { DragDropContext, DragSource } from 'react-dnd';
+import HTML5Backend from 'react-dnd-html5-backend';
+
 const state = store({ position: 0 });
 
 function move(position) {
@@ -18,18 +21,44 @@ function canMove(position) {
   return position > state.position && position - state.position <= 2;
 }
 
+const Types = {
+  PIECE: 'piece'
+};
+
+// Board
+const DndBoard = DragDropContext(HTML5Backend)(Board);
+
+// Board
+
+// Piece
+const dragSource = {
+  beginDrag(props) {
+    return {}
+  },
+  endDrag(props) {
+    return {}
+  }
+};
+
+const ConnectedSource = props => {
+  const {connectDragSource} = props;
+  return (<Piece {...props} innerRef={instance=>connectDragSource(instance)}></Piece>)
+}
+
+const DndPiece = DragSource(Types.PIECE, dragSource, connect => ({
+  connectDragSource: connect.dragSource(),
+}))(ConnectedSource);
+
+
 class Game extends Component {
 
   render() {
     const boxes = _.times(9, n => {
-      const piece = state.position === n ? <Piece /> : null;
+      const piece = state.position === n ? <DndPiece /> : null;
       return (<Box onClick={() => move(n)} key={n} position={n}>{piece}</Box>)
     });
 
     return (
-      <Board>
+      <DndBoard>
         {boxes}
-      </Board>
+      </DndBoard>
     );
   }
 }

ひとまず Drag だけできるようになっていると思います。ドラッグ開始と終了のイベントは拾えますが、Drop したときのイベントはまだ拾えません。

さて、以下の箇所を補足しておきます。これはエラーを回避する為にこのような書き方をしています。ポイントは connectDragSource 関数を実行する場所を変えている事と children を含めた Props を展開して渡しているところです。

const ConnectedSource = props => {
  const {connectDragSource} = props;
  return (<Piece {...props} innerRef={instance=>connectDragSource(instance)}></Piece>)
}

これを return connectDragSource(<Piece />) と書くと次のようなエラーが出ます。

Error: Only native element nodes can now be passed to React DnD connectors.You can either wrap styled.div into a <div>, or turn it into a drag source or a drop target itself.

https://github.com/react-dnd/react-dnd/issues/1021

ドラッグしたコンポーネントをドロップする

少し駆け足になりますが src/Game.js を以下のように修正します。

diff --git a/src/Game.js b/src/Game.js
index aea4133..475b8d7 100644
--- a/src/Game.js
+++ b/src/Game.js
@@ -6,7 +6,7 @@ import Board from './components/Board';
 import Box from './components/Box';
 import Piece from './components/Piece';
 
-import { DragDropContext, DragSource } from 'react-dnd';
+import { DragDropContext, DragSource, DropTarget } from 'react-dnd';
 import HTML5Backend from 'react-dnd-html5-backend';
 
 const state = store({ position: 0 });
@@ -28,7 +28,51 @@ const Types = {
 // Board
 const DndBoard = DragDropContext(HTML5Backend)(Board);
 
-// Board
+// Box
+const dropTarget = {
+  drop(props, monitor) {
+    const { position } = props;
+    state.position = position;
+    return {};
+  },
+  canDrop(props, monitor) {
+    return canMove(props.position);
+  }
+};
+
+const ConnectedTarget = props => {
+  const {canDrop, children, connectDropTarget} = props;
+  const renderOverlay = (color) => {
+    return (
+      <div style={{
+        position: 'absolute',
+        top: 0,
+        left: 0,
+        height: '100%',
+        width: '100%',
+        zIndex: 1,
+        opacity: 0.5,
+        backgroundColor: color,
+      }} />
+    );
+  }
+  return (
+    <Box {...props} innerRef={instance=>connectDropTarget(instance)}>
+      {children}
+      { !children && canDrop &&
+        <div style={{position: 'relative', width: '100%', height: '100%'}}>
+          {renderOverlay('yellow')}
+        </div>
+      }
+    </Box>
+  )
+}
+
+const DndBox = DropTarget(Types.PIECE, dropTarget, (connect, monitor) => {
+  return {
+    connectDropTarget: connect.dropTarget(),
+    canDrop: monitor.canDrop(),
+}})(ConnectedTarget);
 
 // Piece
 const dragSource = {
@@ -56,7 +100,7 @@ class Game extends Component {
   render() {
     const boxes = _.times(9, n => {
       const piece = state.position === n ? <DndPiece /> : null;
-      return (<Box onClick={() => move(n)} key={n} position={n}>{piece}</Box>)
+      return (<DndBox onClick={() => move(n)} key={n} position={n}>{piece}</DndBox>)
     });
 
     return (

以上です。もう少し良い書き方だったり変数名があったりすると思いますが、そのへんは各自で工夫してください。

まとめ

react-dnd はイベントがあちこちで発火して、戻り値のハンドリングが意外と大変でしたが react-dnd 関連の処理を一つの component(この場合は stateful になって良い)にまとめてしまって state の処理を react-easy-state に任せるとそこまでごちゃごちゃしなくて良いと思いました。おしまい。

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

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

f:id:okamuuu:20180518121058j:plain

なぜ松本市

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

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

tabi-shiro

tabi-shiro.com

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

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

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

www.evensi.jp

松本城

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

f:id:okamuuu:20180518122042j:plain

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

ロップ家

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

travelife100.com

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

丸山珈琲 信州MEDIA GARDEN

f:id:okamuuu:20180518121238j:plain

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

ブックカフェ 栞日(shioribi)

sioribi.jp

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

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

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

松本ブルワリー

f:id:okamuuu:20180518121420j:plain

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

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

f:id:okamuuu:20180518121512j:plain

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

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

ばんざい屋

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

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

スタンディング 8オンス

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

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

エオンタ

f:id:okamuuu:20180518121606j:plain

正統派のジャズ喫茶です。こちらも松本ブルワリーで紹介してもらい訪問。お酒も出ます。店内には高音質の 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 ではない