みくにまるのブログ

意識低い系ブロガー、みくにまるが送るブログ。

Debian/Ubuntu で起動時に「Failed to start Raise network interfaces」と出た時の対応【メモ】

Debian Linux

Debianで唐突に起動時に

Failed to start Raise network interfaces

といった表示が出できて起動にものすごく時間がかかるようになりました。

 

その時の対応策を検索して導き出したのでメモしておきます。

なお、根本的な解決になっているかどうかは不明ですので

実行する際には自己責任でお願いします。

 

1./etc/network/interfaces.d/setup を削除

いかにも削除したらマズそうなファイルですが削除します。

2./etc/network/interfaces を編集

上記のファイルを「sudo gedit /etc/network/interfaces」等で適当に開いて

内容を

auto lo
iface lo inet loopback

という二行だけに変更します。

私の場合は、他の行を#でコメントアウトする事で対応しました。

3.再起動

ビビりながら再起動。

無事にサクサク起動するDebianに戻りました。

めでたしめでたし。

 

参考にしたページを貼っておきます。

こちらの方が詳しく載っているので

実際に試す前には原文の方を読むことをオススメします。

unix.stackexchange.com

Linux (Debian/Ubuntu) でShogiGUIを使ってApery、やねうら王、技巧などの将棋ソフトを動かそう！！

Debian Linux コンピュータ将棋 将棋 暮らしの小技

今回はLinuxでの将棋ソフトの使い方を紹介します

google検索をしてみると意外とヒットしなかったので

備忘録も兼ねて記事にしたいと思います。

 

私のLinux環境はDebianなのでDebian用の方式になりますが

Ubuntuの方でも同じ方法で動くはずです。

 

STEP1 ShogiGUIを動かす

下準備

まずは将棋ソフトを動かす為のGUIツールである

ShogiGUIをLinuxで動かします。

この為にはwineとmonoと呼ばれる2つのソフトをインストールする必要があります。

参考 Debianでmonoを使う方法 - みくにまるのブログ

 

ターミナルを開いて以下を打ち込んで下さい。

Ubuntuの場合

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF
echo "deb http://download.mono-project.com/repo/ubuntu stable-xenial main" | sudo tee /etc/apt/sources.list.d/mono-official-stable.list
sudo apt-get update

sudo apt-get install wine mono-devel

Debianの場合

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF
echo "deb http://download.mono-project.com/repo/debian stable-stretch main" | sudo tee /etc/apt/sources.list.d/mono-official-stable.list
sudo apt-get update

sudo apt install wine mono-devel

これでwineとmonoはインストールされました。

 

ShogiGUIのダウンロード

下準備が終わったので

次にShogiGUIをダウンロードしましょう。

 

公式サイトからzip版をダウンロードして下さい。 

f:id:mikunimaru:20180222231114j:plain

 

最後に解凍したフォルダの実行ファイルを右クリックして

「別のアプリから開く」からMono  Runtimeを選択します。

 

f:id:mikunimaru:20180222232933j:plain

 

 無事に起動しました。

f:id:mikunimaru:20180222233443j:plain

 

 STEP2 やねうら王をLinux用にコンパイル

公式の実行ファイルはWindows用ですので

このままでは動きません。

そこでやねうら王をLinux用にコンパイルします。

下準備としてclangをインストール

やねうら王のコンパイルにはmakeとclangが必要なので

初めにmakeとclangをインストールします。

sudo apt install make clang

やねうら王のコンパイル

まずは任意のフォルダに移動してソースコードを落としてコンパイルします。

git clone https://github.com/yaneurao/YaneuraOu.git

cd ./YaneuraOu/source/ 

make avx2

出来上がった実行ファイルをShogiGUIのenフォルダに移動

Yaneuraou/sourceフォルダ内に実行ファイルが出来上がっているので

これをShogiGUIを解凍したフォルダの中にあるenフォルダ内に入れます。

f:id:mikunimaru:20180223005050j:plain

evalフォルダを作る

次にenフォルダ内に「eval」という名前のフォルダを作成します。

この中にダウンロードした評価関数を入れていく事になります。

f:id:mikunimaru:20180223005441j:plain

評価関数ファイルを投入する

次に、制作したevalフォルダの中に

評価関数ファイルを入れましょう。

評価関数ファイルは様々ですので各自でお気に入りの評価関数ファイルを入れましょう。

ここでは過去記事で紹介をしたapery-qhapaq評価関数を使うことを前提に話を進めます。

ダウンロードした評価関数ファイルをevalフォルダ内に移しましょう。

f:id:mikunimaru:20180223010001j:plain

 STEP3 将棋ソフトを動かそう！！

いよいよ最後のSTEPです。

ShogiGUIを起動して、エンジン設定を開きます。

f:id:mikunimaru:20180223010544j:plain

 

するとエンジン設定の画面が出てくるので

先程のenフォルダからやねうら王の実行ファイルを選択しましょう。

f:id:mikunimaru:20180223011011j:plain

やねうら王の初期設定

登録が完了するとやねうら王の設定画面が登場します。

任意ですが、2箇所の設定を変更する事をオススメします。

 

f:id:mikunimaru:20180223011544j:plain

ConsiderationMode これをTrueにすると検討時に長い読み筋が表示されるようになります

Hash この値が小さいと、長時間の検討時に読み筋が途切れます。数時間の検討を行う場合、更に数値を大きくしても良いでしょう。

 将棋ソフトを動かそう！！

以上で手順は終了です。

あとは将棋ソフトを動かすだけです。

一例として検討モードを動かしてみましょう。

f:id:mikunimaru:20180223012440j:plain

「検討」タブをクリックすると検討の設定画面が出現します。

そのままですとエンジンがGPS将棋になっていますので

やねうら王に変更しましょう。

また、検討する候補手の数も変更する事が可能です。

狭く深く読みたいのか、広い手を読みたいのか、用途によって各自変更して下さい。

最後に「検討開始」ボタンをクリックすると検討がスタートします。

 

Linuxでの将棋ソフトの使い方は以上です！！ 

これで将棋ソフトの為だけにWindowsを起動する必要はなくなります！！

最後まで読んで頂きありがとうございました！！

Debianでmonoを使う方法

Debian Linux

Debianでmonoを使おうとしても

公式のリポジトリに存在しないので困ってしまいます。

そこで自分なりに調べた方法をメモ代わりに掲載します。

 

リポジトリの追加

シンプルに追加しましょう。

下記の中からどれか一つを選んで追加します。

Stable（安定版）

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF
echo "deb http://download.mono-project.com/repo/debian stable-stretch main" | sudo tee /etc/apt/sources.list.d/mono-official-stable.list
sudo apt-get update

Preview

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF
echo "deb http://download.mono-project.com/repo/debian preview-stretch main" | sudo tee /etc/apt/sources.list.d/mono-official-preview.list
sudo apt-get update

Nightly

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF
echo "deb http://download.mono-project.com/repo/debian nightly-stretch main" | sudo tee /etc/apt/sources.list.d/mono-official-nightly.list
echo "deb http://download.mono-project.com/repo/debian preview-stretch main" | sudo tee /etc/apt/sources.list.d/mono-official-preview.list
sudo apt-get update

インストール

あとはシンプルにインストールするだけ

sudo apt install mono-devel

 

以上です！！

 

参考文献

Download - Stable | Mono

COPYTRACKが仮想通貨イーサリアムでの資金集めを開始！！用途は一体！？？

当ブログでも度々紹介している
著作権の侵害を無料で解決してくれるサービスCOPYTRUCKが
今度は仮想通貨イーサリアムでの資金集めを始めたようです。

https://copytrack.io/

CPYはブロックチェーンプラットフォームのネイティブトークンになります。当社の柔軟でまとまったライセンスシステムでの支払いに使用されます。これにより当社の分かりやすく使いやすいインターフェースで自分自身で設定したライセンスに基づいて著作権者に自動的に支払いが行われます。<<

公式サイトから引用しましたが
使い道がイマイチピンと来ません。

著作権の違反者に対して
著作権料の支払いを仮想通貨で行うように通告するのでしょうか？

とりあえず本記事は速報という事で
詳細に関しては判明次第記事化します。

※当ブログは投資や仮想通貨の購入を推奨するものではありません。
現金を取り扱う際にはご自身の責任の下での情報の再確認をお願いします。

Debian/UbuntuでWifiを有効にするとBluetoothのマウスが反応しない問題とその解決策

Linux 暮らしの小技

DebianとUbuntuでBluetoothのマウスが反応しない現象が一部で発生しています。

原因はズバリ、カーネル。

 

カーネルを4.13に上げるとこの不具合が発生するようです。

4.14でも同様の不具合を確認しております。

上記の不具合が発生した方はカーネルを4.12に戻しましょう。

そうする事でBluetooth絡みの不具合は一応は解決するはずです。

googleが最強の将棋ソフトAlphaZeroを開発！！わずか12時間の学習で既存の最強ソフトを上回る

将棋 人工知能 ネットサーフィン感想文(海外)

電王戦が終了して

将棋ソフト界隈の動きも一段落したところですが

とんでもないニュースが飛び込んできました！！！

googleが将棋ソフトに参戦

なんとAlphaGoで有名なgoogleが

将棋ソフトもこっそり開発していたのです！！

[1712.01815] Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

f:id:mikunimaru:20180530010328g:plain

 

あっという間にelmoのレーティングを超えてしまう図

 

 

f:id:mikunimaru:20171206134656j:plain

 最終的にはelmoに9割勝てるようになる図

 

ちなみに現在の最強ソフトであるapery-qhapaqは

elmoに対して勝率81%ですので

この勝率9割というのが偶然でなければ

現状の最強ソフトよりも強いという事になります。

www.mikunimaru.com

 

対最強チェスソフトには無敗

 strongest skill level using 64 threads and a hash size of 1GB. AlphaZero convincingly defeated
all opponents, losing zero games to Stockfish and eight games to Elmo

64スレッドでハッシュ1GBのelmo及びStockfish(チェスソフト)と100局対戦したようです。 

elmoは8勝、Stockfishは0勝。

・・・むしろ将棋代表のelmoは頑張ってる方という感想。

思考時間は1手1分

Each program was given 1 minute
of thinking time per move

64スレッドで1手1分ですから相当深く読ませての対戦ですね。

おそらく電王トーナメントの棋譜よりも濃密でしょう。

探索量は1/8000未満でこの強さ

 . AlphaZero searches just
80 thousand positions per second in chess and 40 thousand in shogi, compared to 70 million
for Stockfish and 35 million for Elmo

1秒辺りの探索局面数は

elmoが35,000,000局面なのに対して

AlphaZeroは僅かに40,000局面の探索となっています。

探索の量ではなく質の高さで強さを発揮している事が分かります。

12時間の学習で超える

f:id:mikunimaru:20171206141820j:plain

上記の強さは12時間の学習によって到達したようです。

強さ以外に何が凄いの？

Stockfishもelmoも

探索部分は手作業での非常に細かいチューニングが施されています。

コンピュータソフトとは言っても

熟練プログラマの職人芸のような部分が大きかったのです。

計算力さえあればいい

今回のAlphaZeroの場合は

AlphaZeroの制作そのものは高度な知識が必要だったと思われますが

一度AlphaZeroが完成した後はチェスや将棋への最適化を行わなくても

ルールを教えた後は延々と学習を回していくだけで

勝手に職人芸的なチューニングをされた既存ソフトよりも強くなりました。

AlphaZero, to the games of chess and shogi as well as Go, without any additional domain
knowledge except the rules of the game, demonstrating that a general-purpose reinforcement
learning algorithm can achieve, tabula rasa, superhuman performance across many challenging
domains.

つまりAlphaZeroさえあれば

ゲーム毎に細かいチューニングをする

熟練プログラマの手を借りる必要はないのです。

google一強時代へ

今回のAlphaZeroの登場によって

囲碁将棋チェスと

主要ボードゲーム全てで

google製のソフトが最強となりました。

 

しかも学習時間はわずかに12時間ですからね。

本腰入れたら更にぶち抜かれるのは目に見えています。

果たして最新の将棋ソフトはこの勝率に追いつけるのか・・・

次回のコンピュータ将棋選手権も注目です。

ゲルケンウンをゲルカヤノと比較レビュー 膝への負担も少なくクッション性最強のランニングシューズが登場！！

感想文（レビュー）

アシックス GEL-KENUNを購入してみた

日頃からクッション性の高いゲルカヤノを愛用しているたですが

インターネットで情報を見ると

ゲルケンウンという新たなゲルシリーズが登場しているではありませんか！！

早速注文をしてみたのでゲルカヤノとの比較を中心にレビューしたいと思います。

 

ゲルケンウンとは？

http://img.abc-mart.net/img/event/2/1001354.jpg

 アシックス（asics）は、かかと部に大型のゲルを採用した「ゲルケンウン（ＧＥＬ-ＫＥＮＵＮ）」「レディゲルケンウン（ＬＡＤＹ ＧＥＬ-ＫＥＮＵＮ）」を7月1日から「アシックスストア」各店、オンラインストア、全国のスポーツ用品店で順次発売する。
アシックスのレーシングを除くランニングシューズは、フルマラソンを4時間前後で走るための「FAST」、完走目標・5時間前後で走るための「ROAD」、そして“いつでもどこでも”をキーワードにする「EASY」という3つのラインで構成される。
今作「ゲルケンウン」はその中の「EASY」ラインに属する。

 

「アシックス」から“雲の上”を走るような履き心地の新作ラニングシューズ  |  some(z)up

 

ざっくりと言うと

普段履きようのシューズですね。

レース本番でタイムを出すためというよりも

普段の履き心地に全振りしたようなシューズとなっているようです。

早速履いてみた

ネットで注文をしたゲルケンウンが翌日に届いたので早速履きます。

サイズは普段から履いていたカヤノと同じものを選びました。

ワイドでなくてもゆったり感

ゲルカヤノではスーパーワイドを履いていたので

ケンウンだと細すぎないか心配でしたが

いざ履いてみるとその心配は不要でしたね。

フィット感がありながら締め付けのないゆったりとした履き心地となっています。

別格のクッション性

履いた瞬間に最強のクッション性を実感しました、はい。

 

元々ゲルカヤノを履いていた事もあり

並大抵のクッション性では驚きもしないのですが

このゲルケンウンに関しては未体験のクッション性で衝撃を受けています。

膝への負担ゼロ

ケンウンの名は伊達ではないですね。

本当に雲の上を歩いているような感覚に陥ります。

 

かかとから設置すると膝への負担は殆ど無いんではないでしょうか？

 

ゲルカヤノであっても

グニュッの後に緩和されているとはいえ一気に衝撃が来るタイミングが存在しますが

ゲルケンウンの場合には

時間あたりの衝撃がしっかりと分散されていて、最後にドスンと来る部分がないのです。

 

これはビックリですね。

全てのシューズで改善不可能なのかと思っていたので

ここまで衝撃吸収出来るとは・・・

 

普段から着地の負担に悩まされている方は

ゲルケンウン一択でしょう。

デザイン色々

ゲルケンウンはデザインも豊富です。

特にその中でも、白と黒が入っているのがポイント。

普段履きに使われることを意識して制作されていると感じます。

https://asics.scene7.com/is/image/asics/T7L0N_4901_0010309124_LT?$zoom$

直営限定ですが上記のような青いデザインも存在します。

唯一の弱点

そんなゲルケンウンですが

唯一と言ってもいい弱点があります。

 

購入したてですと

かかとの接地部分の素材の関係で

ツルツルの床を歩くと

「キュッキュッ」という音がしてしまうのです。

 

この音は苦手な人はとことん苦手なタイプの音でしょうから

最初は近所の地面やアスファルトで慣らしてから街履きをする事をオススメします。

クッション性を求めているなら買い

弱点もありますが

クッション性に関しては間違いなく天下一品です。

足への負担を和らげたい方、靴にクッション性を求める方は

ゲルケンウンへの履き替えをオススメします。

 

最後まで読んで頂きありがとうございました。

2017年最強将棋ソフト「apery-qhapaq（aperypaq）」が公開される。ダウンロード方法や強さを紹介

将棋

2018年の最強ソフトはこちら　↓

2018年最強ソフト NNUE (TNK (たぬき))のダウンロードと使い方 - みくにまるのブログ

 

将棋ソフトQhapaqの作者の方が

ブログでAperyの評価関数をベースとした新たな評価関数を公開なさったようです。

qhapaq.hatenablog.com

 

その棋力はなんとAperyに対して勝率58%！！

短期間でここまで強くなるなんてビックリですね。

 

ダウンロード方法

評価関数は作者の方のGithubに置かれています。

Release qhapaq学習機によるコラボ関数群 · qhapaq-49/qhapaq-bin · GitHub

上記のリンクからダウンロードしましょう。

使い方

上記の評価関数をダウンロードした後に

やねうら王をダウンロードして評価関数の入れ替えを行います。

動作には「apery-qhapaq評価関数」「やねうら王」「Shogi-GUI」という3つのソフトが必要になります。

ひと手間かかりますので後日記事にします。

（最新のやねうら王が公開された頃を予定）

Haskellで最長増加部分列（LIS）IOArrayやData.Setで試行錯誤

プログラミング Haskell AOJ

今度もAOJの練習問題から
最長増加部分列の問題に挑む。
最長増加部分列 | 動的計画法 | Aizu Online Judge
 
コードを書く練習と割り切っているので
考え方は素直にググる。

thさんという方のブログに
分かりやすい考え方が載っていたので
これをHaskellで実装する事にした。

;; 最後の要素から順番に、各要素を先頭とするLIS長を求めていく。
;; 計算を具体的に手でやってみると、次のような流れになる（リストに作用させる関数をfとおく）。
(f 15) => 1
(f 7 15) => 2 ;7 < 15 なので (f 15) + 1 => 1 + 1
(f 11 7 15) => 2 ;11 < 15 なので (f 15) + 1 => 1 + 1
(f 3 11 7 15) => 3 ;3より大きい11,7,15で始まるLISはそれぞれ長さが2,2,1。maxの2に1加えて3
(f 13 3 11 7 15) => 2 ;13 < 15 なので (f 15) + 1 => 1 + 1
(f 5 13 3 11 7 15) => 3 ;5より大きい13か11か7で始まるLISが最長で2。それに1加えて3
(f 9 5 13 3 11 7 15) => 3 ;9より大きい13か11で始まるLISが最長で2。それに1加えて3
(f 1 9 5 13 3 11 7 15) => 4 ;1より大きい9や5で始まるLISが最長で3。それに1加えて4
(f 14 1 9 5 13 3 11 7 15) => 2 ;14 < 15 なので (f 15) + 1 => 1 + 1
(f 6 14 1 9 5 13 3 11 7 15) => 4 ;6より大きい数のうち、9で始まるLISが最長で3。それに1加えて4
(f 10 6 14 ...略) => 3 ;10より大きい11,13のLISが最長で2。それに1加えて3
(f 2 10 6 ...略) => 5 ;2より大きい6のLISが最長で4。それに1加えて5
(f 12 2 10 ...略) => 3 ;12より大きい13, 14のLISが最長で4。それに1加えて3
(f 4 12 2 ...略) => 5 ;5より大きい数のうち、6で始まるLISが最長で4。それに1加えて5
(f 8 4 12 ...略) => 4 ;8より大きい12,10,9のLISが最長で3。それに1加えて4
(f 0 8 4 ...略) => 6 ;0より大きい数のうち、2で始まるLISが最長で5。それに1加えて6

Technical Memorandum: 最長増加部分列の長さ in Elisp

Arrayで書いてみる

最初は数字と最長がいくつなのかの2つの数をArrayに収める事を考えてみた。

import Control.Applicative
import Data.Array
import Data,List (foldl')

main = do
  len <- (read :: String -> Int) <$> getLine
  xs <- map (read :: String -> Int) . lines <$> getContents
  let arr = listArray (1,len) (zip xs [0,0..])
  print $ ans $syorinaiyou arr len

ans arr = maximum $ map snd $ elems $ arr

syorinaiyou :: Array Int (Int, Int) -> Int -> Array Int (Int, Int)
syorinaiyou arr len = foldl' keisan arr (reverse [1..len])
    where
      keisan :: Array Int (Int, Int) -> Int -> Array Int (Int, Int)
      keisan arr m
        | m == len = arr // [(m,(a,1))]
        | 1==1     = fst $ foldl' seisa' (arr,1) [m..(len+1)]
        where
          (a,_) = arr ! len
          seisa' (arr,x) t
            | t > len  = (koushin,x)
            | fstarr m < fstarr t = (arr,hikaku)
            | otherwise          = (arr,x)
            where
              fstarr r = fst $ arr ! r
              sndarr r = snd $ arr ! r
              hikaku = max x ((sndarr t)+1)
              koushin = arr // [(m,(fstarr m,x))]

（叩き台として書いていたので変数名が酷い）

早速提出する
f:id:mikunimaru:20171118082828j:plain
安定のMLE。

        | m == len = arr // [(m,(a,1))]
              koushin = arr // [(m,(fstarr m,x))]

原因は多分この辺り。
Haskellの配列は更新のコストが高すぎるので
破壊的代入をしないならMap一択なのかもしれない。

という訳でMapで書き直す。

import Control.Applicative
import qualified Data.Map.Strict as Map
import Data.List (foldl')

main = do
  len <- (read :: String -> Int) <$> getLine
  xs <- map (read :: String -> Int) . lines <$> getContents
  let arr = Map.fromList $ zip [1..len] (zip xs [0,0..])
  print $ ans $ syorinaiyou arr len

ans arr = maximum $ map (snd . snd)  $ Map.toList $ arr

syorinaiyou arr len = foldl' keisan arr (reverse [1..len])
    where
      keisan arr m
        | m == len = Map.insert m (a,1) arr
        | 1==1     = fst $ foldl' seisa' (arr,1) [m..(len+1)]
        where
          (a,_) = arr Map.! len
          seisa' (arr,x) t
            | t > len  = (koushin,x)
            | fstarr m < fstarr t = (arr,hikaku)
            | otherwise          = (arr,x)
            where
              fstarr r = fst $ arr Map.! r
              sndarr r = snd $ arr Map.! r
              hikaku = max x ((sndarr t)+1)
              koushin = Map.insert m (fstarr m,x) arr

小さな修正で済んだ。

早速再提出。
f:id:mikunimaru:20171118101032j:plain
うーむ駄目。

IOArrayを試す

テストケースを見てみると
どうも要素数が1万もあるので、更新云々の問題でもなさそうだ。
まあせっかくなのでIOArrayで再実装したパターンも試してみる。


〜コンパイルエラーと格闘する事 ２日間〜

import Control.Applicative
import Data.Array.IO
import Control.Monad (mapM_)
import Data.IORef

main = do
  len <- (read :: String -> Int) <$> getLine
  xs <- map (read :: String -> Int) . lines <$> getContents
  arr <- newListArray (1,len) (zip xs [0,0..]) :: IO (IOArray Int (Int,Int))
  syorinaiyou arr len
  x <- newIORef 0
  ans arr x
  print =<< readIORef x

ans :: IOArray Int (Int, Int) -> IORef Int -> IO ()
ans arr x = do
  xs <- getElems arr
  writeIORef x (maximum $ map snd  xs)


syorinaiyou :: IOArray Int (Int, Int) -> Int -> IO ()
syorinaiyou arr len = do mapM_ (keisan arr) (reverse [1..len])
    where
      keisan :: IOArray Int (Int, Int) -> Int -> IO ()
      keisan arr m = do
          x <- newIORef 1
          mapM_ (seisa' (arr,x)) [m..(len+1)]
        where
          seisa' :: (IOArray Int (Int, Int), IORef Int) -> Int -> IO ()
          seisa' (arr,x) t
            | t > len  = koushin
            | otherwise = do
              m'' <- readArray arr m
              let m' = fst m''
              t'' <- readArray arr t
              let t' = fst t''
              if m' < t' then hikaku
                         else return ()
            where
              hikaku = do
                x' <- readIORef x
                t'' <- readArray arr t
                let t' = snd t''
                writeIORef x (max x' (t'+1))
              koushin = do
                x' <- readIORef x
                m'' <- readArray arr m
                let m' = fst m''
                writeArray arr m (m',x')


doだらけのコードがようやく完成。
折角なのでArrayで書いたコードをIOArrayで書き直す時に苦労したポイントをメモしておく。

  arr <- newListArray (1,len) (zip xs [0,0..]) :: IO (IOArray Int (Int,Int))

まずここ。
型注釈「:: IO (IOArray Int (Int,Int))」がないとコンパイルエラーになる。
IOArrayなのかIOUArrayなのかコンパイラが判別出来ないからだ。

seisa' (arr,x) t
  | t > len  = koushin
  | otherwise = do
    m'' <- readArray arr m
    let m' = fst m''
    t'' <- readArray arr t
    let t' = fst t''
    if m' < t' then hikaku
     else return ()

もとのコードと比較して一番汚く冗長になったこの部分。
初めはfstarr m < fstarr tとして
fstarr内でIOArrayから取得した値を返そうとしたのだが
非純粋？な関数から純粋な関数に値を渡す事は出来ないようで
仕方なくdoブロックを作ってブロック内で値を取り出してから
if then else で条件別に振り分けた。

後半の方は「t''」みたいな投げやりな変数名になってしまったが動いたので満足。
・・・はせずに、ブログ執筆用も兼ねて変数名で意味が分かるように修正。
こんな1文字の変数名では自分でも意味不明なので。

import Control.Applicative
import Data.Array.IO
import Control.Monad (mapM_)
import Data.IORef

main = do
  len <- (read :: String -> Int) <$> getLine
  xs <- map (read :: String -> Int) . lines <$> getContents
  arr <- newListArray (1,len) (zip xs [1,1..]) :: IO (IOArray Int (Int,Int))
  syorinaiyou arr len
  lengthLIS <- newIORef 0
  ans arr lengthLIS
  print =<< readIORef lengthLIS

ans :: IOArray Int (Int, Int) -> IORef Int -> IO ()
ans arr lengthLIS = do
  xs <- getElems arr
  writeIORef lengthLIS (maximum $ map snd xs)

syorinaiyou :: IOArray Int (Int, Int) -> Int -> IO ()
syorinaiyou arr len = do mapM_ (keisan arr) (reverse [1..len])
    where
      keisan :: IOArray Int (Int, Int) -> Int -> IO ()
      keisan arr hikaku_moto_Idx = do
          mapM_ (seisa' arr) [hikaku_moto_Idx..(len)]
        where
          seisa' :: IOArray Int (Int, Int) -> Int -> IO ()
          seisa' arr hikaku_saki_Idx = do
              (hikaku_moto,_) <- readArray arr hikaku_moto_Idx
              (hikaku_saki,_) <- readArray arr hikaku_saki_Idx
              if hikaku_moto < hikaku_saki then hikaku
                         else return ()
            where
              hikaku = do
                (_,hikaku_saki_LIS)                  <- readArray arr hikaku_saki_Idx
                (hikaku_moto,hikaku_moto_LIS_zantei) <- readArray arr hikaku_moto_Idx
                if hikaku_saki_LIS + 1 > hikaku_moto_LIS_zantei
                   then do
                     writeArray arr hikaku_moto_Idx (hikaku_moto, (hikaku_saki_LIS + 1))
                   else return ()

だいぶ読みやすくなった。
格好つけても仕方ないので変数名はローマ字にした。
処理の流れが分かりやすくなった事で無断な部分を省く事にも成功。

早速これで提出。
f:id:mikunimaru:20171119174350j:plain
メモリの削減という目的は達成されるも
残念ながらTLE

O2ビルドで強行突破をはかるも少し進んでTLE
f:id:mikunimaru:20171119180105j:plain

秘密兵器Data.Set

そこでData.Setに一度
各要素を先頭とするLIS長を保存し
そこから探索をする事にした。
Data.Set

takeWhileAntitone :: (a -> Bool) -> Set a -> Set a
O(log n). Take while a predicate on the elements holds .

findMax :: Set a -> a
O(log n). The maximal element of a set.

Data.Setはリストに扱い方が似ているが
takeWhileやmaximumをO(log n)で実行できるというスグレモノだ。
早速活用してみる。

修正するべき箇所はここ

      keisan :: IOArray Int (Int, Int) -> Int -> IO ()
      keisan arr hikaku_moto_Idx = do
          mapM_ (seisa' arr) [hikaku_moto_Idx..(len)]
        where
          seisa' :: IOArray Int (Int, Int) -> Int -> IO ()
          seisa' arr hikaku_saki_Idx = do
              (hikaku_moto,_) <- readArray arr hikaku_moto_Idx
              (hikaku_saki,_) <- readArray arr hikaku_saki_Idx
              if hikaku_moto < hikaku_saki then hikaku
                         else return ()
            where
              hikaku = do
                (_,hikaku_saki_LIS) <- readArray arr hikaku_saki_Idx
                (hikaku_moto,hikaku_moto_LIS_zantei) <- readArray arr hikaku_moto_Idx
                if hikaku_saki_LIS + 1 > hikaku_moto_LIS_zantei
                   then do
                     writeArray arr hikaku_moto_Idx (hikaku_moto, (hikaku_saki_LIS + 1))
                   else return ()

この処理というのは
比較元よりも手前かつ大きな数の中で
その要素を先頭にするLIS長が一番長いものを探し出すというもの。

lookupMax $ takeWhileAntitone (>hikaku_moto) (これまでのLIS長のData.Set)

こんな完成イメージをもちつつソースを修正していく。

いきなり問題発生

lis.hs:6:57: error:
    Module ‘Data.Set’ does not export ‘dropWhileAntitone’

なんと古いバージョンのData.SetにはtakeWhileやdropWhileにあたる関数がなかったのだ。
仕方ないのでSet.splitを使う。

> b = Set.fromList $ zip [1..10] [1..10]
> b
fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10)]
> Set.split (5,0) b
(fromList [(1,1),(2,2),(3,3),(4,4)],fromList [(5,5),(6,6),(7,7),(8,8),(9,9),(10,10)])
> snd $ Set.split (5,0) b
fromList [(5,5),(6,6),(7,7),(8,8),(9,9),(10,10)]

これでtakeWhileAntitoneとほぼ同じような動作になる。

IOArrayは必要なくなったので
大幅に書き直したのが下のコード

{-# OPTIONS_GHC -O2 #-}
import Control.Applicative
import Data.Array.Unboxed
import Data.List (foldl')
import Data.Foldable (maximumBy)
import Data.Ord (comparing)
import qualified Data.Set as Set

main = do
  len <- (read :: String -> Int) <$> getLine
  xs <- map (read :: String -> Int) . lines <$> getContents
  let arr = listArray (1,len) xs :: UArray Int Int
  print $ snd $ maximumBy (comparing snd) $ syorinaiyou arr len

syorinaiyou arr len =
  foldl' (keisan arr) Set.empty (reverse [1..len])
    where
      keisan arr set n
        | Set.null set =  Set.insert ((arr ! n),1) set
        | otherwise    = seisa arr set n
        where
          seisa arr set n
            | Set.null set' = Set.insert (hikaku_moto,1) set
            | otherwise     = Set.insert (hikaku_moto, oldLIS + 1) set
            where
              hikaku_moto = arr ! n
              set'   = snd $ Set.split (hikaku_moto + 1 , 0) set
              oldLIS = snd $ maximumBy (comparing snd) set'  

maximumBy (comparing snd)

この部分はData.Setに収納されたタプルのsndが最大の要素を抽出する処理。
Data.Foldableはfoldableなら何でも適用できる便利な関数が入ったライブラリ。
Data.Foldable

lookupMaxは癖があったので今回は叩き台という事もあって採用しなかった。

早速再提出してみる。
f:id:mikunimaru:20171127041309j:plain
IOArrayの頃よりは進んだが、まだ突破は出来ず・・・

原因を探る

探らなくても薄々わかっている

snd $ maximumBy (comparing snd) set'

この処理がボトルネックになっていると見た。

そこでsetが長くならないように修正

seisa arr set n
    | Set.null set' = Set.insert (hikaku_moto,1) set
    | otherwise     = Set.insert (hikaku_moto, oldLIS + 1) set2
    where
      hikaku_moto = arr ! n
      (set1, set') = Set.split (hikaku_moto + 1 , 0) set
      (old,oldLIS) = maximumBy (comparing snd) set'
      set2         = Set.union set1 (snd (Set.split (old,oldLIS-1) set'))

再提出
f:id:mikunimaru:20171127054601j:plain
うーん、あと一息。

もう一度修正

 (old,oldLIS) = Set.elemAt 0 set'

この部分は先頭＝最長なので
maximumByを使う必要はなかった。


再提出
f:id:mikunimaru:20171127065518j:plain
色々と間違えていたらしい。
とりあえず継ぎ接ぎで修正して再提出。
f:id:mikunimaru:20171127065748j:plain
通った！！

最後の方にはヤケクソ感が漂うコードになってしまった。

{-# OPTIONS_GHC -O2 #-}
import Control.Applicative
import Data.Array.Unboxed
import Data.List (foldl')
import Data.Foldable (maximumBy)
import Data.Ord (comparing)
import qualified Data.Set as Set

main = do
  len <- (read :: String -> Int) <$> getLine
  xs <- map (read :: String -> Int) . lines <$> getContents
  let arr = listArray (1,len) xs :: UArray Int Int
  print $ snd $ maximumBy (comparing snd) $ syorinaiyou arr len

syorinaiyou arr len =
  foldl' (keisan arr) Set.empty (reverse [1..len])
    where
      keisan arr set n
        | Set.null set = Set.insert ((arr ! n),1) set
        | otherwise    = seisa arr set n
        where
          seisa arr set n
            | Set.null set'      = Set.insert (hikaku_moto,1) set
            | Set.size set1 <= 1 =  Set.insert (hikaku_moto, oldLIS + 1) set'
            | otherwise = Set.insert (hikaku_moto, oldLIS + 1) set2
            where
              hikaku_moto = arr ! n
              (set1, set') = Set.split (hikaku_moto + 1 , 0) set
              (old,oldLIS) = Set.elemAt 0 set'
              set2         = Set.union (Set.delete (Set.elemAt ((Set.size set1)-1) set1) set1) (snd (Set.split (old,oldLIS-1) set'))

一応解決。
最終的には破壊的代入とか要らなかった。
IOArrayの為に格闘していた時間は一体・・・

クラウドファンディングで参考になりそうなサイト5選

暮らしの疑問

ちょっとした資金を集めるのに活用されているクラウドファンディング

今回の記事ではクラウドファンディングをする際に役立ちそうなサイトを並べてみました。

 

 

とりあえずサイト一覧

クラウドファンディングを行っているサイトを一覧化しました。

ググってもあまりピンと来ないでしょうからこの中から探しましょう。

一覧化されているいい感じのサイトがあったのでそちらを紹介します。

100サイト以上のクラウドファンディングサイトがまとめられています。

多すぎでしょ

眺めてみた思ったのですが

乱立・・・してますね。

本当に成立してるのかというようなサイトもチラホラあります。

SNSなどで自ら拡散する力があるなら特にサイト選びは気にしなくても良いでしょうか

そうでない方はやはりどこで募集するかが重要になりそうです。

Makuakeが強い

色々と調べてみるとこのようなページに辿り着きます。

クラウドファンディングの大型資金調達額ランキングトップ10｜ferret [フェレット]

2015年の記事ですが、実際にクラウドファンディングで大型の資金調達に成功した事例をランキング形式で紹介しています。

日本の主要クラウドファンディング 支援額ランキングトップ100 | ビジュアライジング・インフォ

こちらは2016年時点でのベスト100

トップ20のサイトを見ると

 

Makuake 10例

READYFOR 5例

CAMPFIRE 3例

 

といった割合になっています。

どうも調達資金額に関してはMakuakeが圧倒的に強そうです。

クラウドファンディング - Makuake（マクアケ）：サイバーエージェントグループ

ランキング形式で盛り上がっているプロジェクトが分かるサイトもある

ランクラウドというサイトが

国内の主要なクラウドファンディングサイトから

今、盛り上がっているクラウドファンディングを一覧化しています。

クラウドファンディングの比較ランキングサイト「ランクラウド」を提供開始
－ ランクラウドは日本の主要クラウドファンディングサイトとプロジェクトをまとめた、比較ランキングサイトです。 

クラウドファンディング比較ランキングサイト | ランクラウド

 

まあこのサイトで見てもMakuakeが圧倒的に強いですね。

どうやら本気で資金調達をするならMakuakeにしておくのが無難みたいです。

具体的な手順

ググっても全然ない！！

「テーマを考えよう」みたいな抽象的な情報しかHITしません。

スクショ付きで具体的な手順を解説しているサイトが全く見当たらない。

彼らは本当にクラウドファンディングをしてるのか？？？

 

ググっても引っかからないので

本気で始める人は素直に各サイトのチュートリアルを読んで

わからない事はメールで質問する事をオススメします。

というかお金が絡む以上は直接のやり取りも挟みたいところですし。

【結論】双方向的な方法で情報を得た方が良さげ

ググってもググっても情報不足。

盛り上がっていそうで意外と盛り上がってないようです。

 

私が調べてみた範囲ですと

元々自分自身で集客料があるか

拡散力のある知り合いに広めて貰えるアテがある場合でないと

あまりうまく行かないという印象を受けました。

 

そういったツテが無い場合ですと

SNSで勝手に広まりそうなテーマを選ぶという事になります。

 

う〜む、しかし具体的な手順がさっぱり分からない。

クラウドファンディングをしている人たちは

検索しても大した情報が入らない中で見切り発車しているのでしょうか？

プロジェクトの内容を見ても、確かにそういう

とりあえずやってみよう的な精神を持った方のブロジェクトが大半な気がします。

まあ、実際に資金を調達しているのは練り込まれたプロジェクトなのですが・・・

 

ネットの情報ではなく

双方向的なやり取りでアドバイスを貰ってから始めることを強く推奨したいですね。

インターネット検索も万能という訳でもないなと再認識した事例でした。

Haskellで動的計画法 ナップサック問題を解く

プログラミング Haskell AOJ

Haskellでナップサック問題を解く時のメモ

ナップザック問題 | 動的計画法 | Aizu Online Judge


とりあえずAOJのこの問題で通るコードを目標にする。

まずは叩き台

{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative
import Data.Array

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ maximum $ elems (resolve capa (listArray (0,capa) [0,0..]) goods)

resolve :: Int -> Array Int Int -> [[Int]] -> Array Int Int
resolve capa capaArr ([v,w]:xs)
  | xs == [] = koushin capaArr [v,w] (capa-w)
  | otherwise = resolve capa (koushin capaArr [v,w] (capa-w)) xs
  where
    koushin :: Array Int Int -> [Int] -> Int -> Array Int Int
    koushin capaArr [v,w] n
      | n == 0 && capaArr ! w <= v      = capaArr // [( w , v)]
      | n == 0                          = capaArr
      | oldValue == 0                   = next
      | capaArr ! (n+w) >= v + oldValue = next
      | otherwise = koushin (capaArr // [( n + w , v + oldValue)]) [v,w] (n-1)
      where
        oldValue = capaArr ! n
        next     = koushin capaArr [v,w] (n-1)

叩き台として書いたのが上記のコード

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ maximum $ elems (resolve capa (listArray (0,capa) [0,0..]) goods)

入力を受け取る部分
容量をcapa、品物のリストをgoodsとして受取り

listArray (0,capa) [0,0..])

listArrayで、[(0,0),(1,0)・・・,(capa,0)]
までの配列を作ってresolve関数に送る。

resolve capa capaArr ([v,w]:xs)
  | xs == [] = koushin capaArr [v,w] (capa-w)
  | otherwise = resolve capa (koushin capaArr [v,w] (capa-w)) xs

resolve関数では品物1つ1つについて
koushin関数で配列を更新していく

原理については下の「最強最速アルゴリズマー養成講座」という記事が分かりやすい。(画像は下記サイトから)
病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ
http://image.itmedia.co.jp/enterprise/articles/1005/15/tnalgfig5.gif

koushin capaArr [v,w] n
  | n == 0 && capaArr ! w <= v        = capaArr // [( w , v)]
  | n == 0                            = capaArr
  | oldValue == 0                     = next
  | capaArr ! (n+w) >= v + oldValue   = next
  | otherwise = koushin (capaArr // [( n + w , v + oldValue)]) [v,w] (n-1)
  where
    oldValue = capaArr ! n
    next     = koushin capaArr [v,w] (n-1)

上記の画像のような配列の更新をしていく関数。

改善をしていく

f:id:mikunimaru:20171115212203j:plain
このまま提出をすると遅すぎる＆メモリを使いすぎるので通らなかった。

主に原因となっているのは
(//)が実は配列をまるごとコピーして再生成している事だろう。

Mapを使ってみる

{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative
import qualified Data.Map.Strict as Map
import Data.List (maximumBy)
import Data.Ord (compare)
import Data.Function (on)

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ snd $ maximumBy (compare `on` snd) $ Map.toList (resolve capa (Map.fromList (zip [0..capa] [0,0..])) goods)

resolve capa capaMap ([v,w]:xs)
  | xs == [] = koushin'
  | otherwise = resolve capa koushin' xs
  where
    koushin' =  koushin capaMap [v,w] (capa-w)
    koushin capaMap [v,w] n
      | n == 0 && capaMap Map.! w <= v        = Map.insert w v capaMap
      | n == 0                                = capaMap
      | oldValue == 0                         = next
      | capaMap Map.! (n+w) >= v + oldValue   = next
      | otherwise = koushin (Map.insert (n+w) (v + oldValue) capaMap) [v,w] (n-1)
      where
        oldValue = capaMap Map.! n
        next     = koushin capaMap [v,w] (n-1)

Data.Mapのinsert関数はO(log n)なので配列のコピーよりも高速。
とりあえず叩き台のコードを配列からMapに書き換えてみた。

maximumBy (compare `on` snd)

この部分はリストの中身にsnd関数を適用した値が最大の要素を抜き出す関数
そのせいでimportが大袈裟になってしまった。
普通に

 maximum $ map snd

とした方が分かりやすかったか。

とりあえず上記のコードでもう一度提出してみると・・・
f:id:mikunimaru:20171116013649j:plain
（やべっ通っちゃった）

通らないと思って提出したので
{-# LANGUAGE FlexibleContexts #-}
みたいな余計な文字まで入ってる有り様・・・

本当はTLEしてもっと頑張る予定だったのだけどまあいいか。

重複可のパターン

import Control.Applicative
import qualified Data.HashMap.Strict as Map

main = do
    [_,capa] <- map (read :: String -> Int) . words <$> getLine
    goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
    print $ maximum $ map snd $ Map.toList (resolve capa (Map.fromList (zip [0..capa] [0,0..])) goods)

resolve capa capaMap ([v,w]:xs)
  | xs == []  = koushin'
  | otherwise = resolve capa koushin' xs
  where
    koushin' =  koushin capaMap [v,w] 0
    koushin capaMap [v,w] n
      | n > (capa - w)                      = capaMap
      | n == 0 && capaMap Map.! w <= v      = next'
      | capaMap Map.! (n+w) >= v + oldValue = next
      | otherwise                           = next'
      where
        oldValue = capaMap Map.! n
        next     = koushin capaMap [v,w] (n+1)
        next'    = koushin (Map.insert (n+w) (v + oldValue) capaMap) [v,w] (n+1)

先程のコードは簡単な改造で重複可のナップザック問題にも対応できる。
AOJには重複可のナップザック問題もあったので上記のコードで提出をしてみる。
Knapsack Problem | Aizu Online Judge
無事に通ってひと安心
f:id:mikunimaru:20171116024104j:plain
Data.HashMap.Strictの方が通常のMap.Strictよりも高速。
HashMap.Strictだと00.25sだがMap.Strictだと00:46s

ここからが本題

まあ上記は当然ながら練習問題。
本番の問題はこちら

0-1 Knapsack Problem II | Aizu Online Judge

文章は冒頭の問題と同じだが
容量の範囲が10万倍、品物の重さの範囲も1万倍になっている。

同じようなコードで提出をしてみると
当然のようにTLE
f:id:mikunimaru:20171116031152j:plain
更に高速なコードが必要となる。

ちなみにこの問題
執筆時点ではHaskellでパスした回答はゼロ件だった。
f:id:mikunimaru:20171116032654j:plain
うん、頑張ろう。

Vectorを使ってみる

改善をしていく

import Control.Applicative
import qualified Data.HashMap.Strict as Map
 
main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ maximum $ map snd $ Map.toList (resolve capa (Map.fromList (zip [0..capa] [0,0..])) goods)
 
resolve capa capaMap ([v,w]:xs)
  | xs == []  = koushin'
  | otherwise = resolve capa koushin' xs
  where
    koushin'
      | capa < w  = capaMap
      | otherwise = koushin capaMap [v,w] (capa-w)
    koushin capaMap [v,w] n
      | n == 0 && capaMap Map.! w <= v        = Map.insert w v capaMap
      | n == 0                                = capaMap
      | oldValue == 0                         = next
      | capaMap Map.! (n+w) >= v + oldValue   = next
      | otherwise = koushin (Map.insert (n+w) (v + oldValue) capaMap) [v,w] (n-1)
      where
        oldValue = capaMap Map.! n
        next     = koushin capaMap [v,w] (n-1)

提出したコード

    koushin capaMap [v,w] n
      | n == 0 && capaMap Map.! w <= v        = Map.insert w v capaMap
      | n == 0                                = capaMap
      | oldValue == 0                         = next
      | capaMap Map.! (n+w) >= v + oldValue   = next
      | otherwise = koushin (Map.insert (n+w) (v + oldValue) capaMap) [v,w] (n-1)

おそらくマズいのはこの部分。
Map.insertを下手するとナップサックの容量回近く繰り返すコードになっている。


更新する項目をリストにしておいて一発で変更したほうが効率が良さそうだ。
となると今度はMap.!で値を参照するのに毎回O(log n)掛かるのが無駄なので
Vectorで書き直す事にした

新たな叩き台

import Control.Applicative
import qualified Data.Vector.Unboxed as V

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ V.maximum (resolve capa (V.enumFromStepN 0 0 (capa+1)) goods)

resolve capa capaV ([v,w]:xs)
  | xs == [] = koushin'
  | otherwise = resolve capa koushin' xs
  where
    koushin'
      | capa < w  = capaV
      | otherwise = koushin capaV [v,w] (capa-w)
    koushin capaV [v,w] n
      | n == 0 && capaV V.! w <= v      = capaV V.// [( w , v)]
      | n == 0                          = capaV
      | oldValue == 0                   = next
      | capaV V.! (n+w) >= v + oldValue = next
      | otherwise = koushin (capaV V.// [( n + w , v + oldValue)]) [v,w] (n-1)
      where
        oldValue = capaV V.! n
        next     = koushin capaV [v,w] (n-1)

さっそくここから修正していく

    koushin'
      | capa < w  = capaV
      | otherwise = koushin capaV [v,w] (capa-w) []
    koushin capaV [v,w] n koushinList
      | n == 0 && capaV V.! w <= v      = capaV V.// ((w,v):koushinList)
      | n == 0                          = capaV V.// koushinList
      | oldValue == 0                   = next
      | capaV V.! (n+w) >= v + oldValue = next
      | otherwise = koushin capaV [v,w] (n-1) ((n + w, v + oldValue):koushinList)
      where
        oldValue = capaV V.! n
        next     = koushin capaV [v,w] (n-1) koushinList

koushinListに一度にまとめてから
最後に V.// koushinListを使いO(n)で処理するようにしてみた。
ローマ字かよという突っ込みが入りそうだが気にしない

早速再提出してみる。
f:id:mikunimaru:20171116060314j:plain
でたー、MLE。
Haskellではお馴染み。
こうなると思い当たる方法はひとつしかない。

破壊的代入に挑戦

メモリや実行時間がカツカツの状況では
遅延評価だの再代入禁止だのと言っている暇はない。

さっそくIORefとVector.Mutableを使って
コードを書いてみた。

import Control.Applicative
import Data.IORef
import qualified Data.Vector.Mutable as VM

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  capaVM <- VM.replicate (capa+1) 0
  ans <- newIORef 0
  resolve capa capaVM goods ans
  print =<< readIORef ans

resolve capa capaVM ([v,w]:xs) ans =
  if null xs
     then koushin'
     else  do
       koushin'
       resolve capa capaVM xs ans
       where
         koushin' =
           if capa < w
              then return ()
              else koushin [v,w] (capa-w)
         koushin [v,w] n = do
           oldValue <- VM.read capaVM n
           newValue <- VM.read capaVM (n+w)
           judge oldValue newValue
             where
               judge oldValue newValue
                 | n == 0 && newValue <= v  = next'
                 | n ==0                    = return ()
                 | newValue >= v + oldValue = next
                 | otherwise  = next''
                 where
                   next  = koushin [v,w] (n-1)
                   next' = do
                     VM.write capaVM (n+w) (v + oldValue)
                     ans' <- readIORef ans
                     writeIORef ans (max ans' (v + oldValue))
                   next'' = do
                     next'
                     koushin [v,w] (n-1)

・・・ツッコミどころは多いが
とりあえず動くものが出来上がったので提出してみる。
f:id:mikunimaru:20171116120131j:plain
？？？
何故か前回のコードよりもメモリ消費が悪化している

Data.Vector.Unboxed.Mutableにしてもう一度提出。
f:id:mikunimaru:20171116120916j:plain
これも駄目。

原因を探る

コードを眺めたところ

resolve capa capaVM ([v,w]:xs)

どうもこの辺りが怪しい。
そこでリストをVectorに変更して
処理の最中に大きなリストを使わないようにしてみた

import qualified Data.Vector as V

main = do
  [kosuu,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  let goodsV = V.fromList goods
  capaVM <- VM.replicate (capa+1) 0
  ans <- newIORef 0
  resolve capa capaVM goodsV ans 0 kosuu
  print =<< readIORef ans

resolve capa capaVM goodsV ans n kosuu =
  if n == (kosuu- 1)
     then koushin'
     else  do
       koushin'
       resolve capa capaVM goodsV ans (n+1) kosuu
       where
         koushin' =
           if capa < last (goodsV V.! n)
              then return ()
              else koushin [(head (goodsV  V.! n)),(last (goodsV V.! n))] (capa-(last (goodsV V.! n)))

最後のkoushin関数では
リストを使うが、要素2なのでなんとかなるだろう。
という訳で訂正したコードで再提出。


f:id:mikunimaru:20171116224121j:plain
・・・駄目みたいですね。

もう一度原因を探る

どうも見当違いな場所を修正していたようなので
じっくりソースを眺めてもう一度メモリを使っているのはどの場所か精査してみた。
すると怪しいポイントを発見

koushin [v,w] n = do
  oldValue <- VM.read capaVM n
  newValue <- VM.read capaVM (n+w)
  judge oldValue newValue
    where
      judge oldValue newValue
        | n == 0 && newValue <= v  = next'
        | n == 0 = return ()
        | newValue >= v + oldValue = next
        | otherwise  = next''
        where
 next  = koushin [v,w] (n-1)
 next' = do
   VM.write capaVM (n+w) (v + oldValue)
   ans' <- readIORef ans
   writeIORef ans (max ans' (v + oldValue))
 next'' = do
   next'
   koushin [v,w] (n-1)

再帰してますねぇ・・・

秘密兵器mapM_

そこで再帰部分をmapM_を使って書き直す事にした。
わかりやすくする為にリストの方のコードをベースにする。

import Control.Applicative
import Data.IORef
import qualified Data.Vector.Mutable as VM
import Control.Monad

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  capaVM <- VM.replicate (capa+1) 0
  ans <- newIORef 0
  mapM_ (resolve capa capaVM ans) goods
  print =<< readIORef ans

resolve capa capaVM ans [v,w] =
  if capa < w
    then return ()
    else mapM_ (koushin [v,w]) (reverse [0..(capa-w)])
       where
         koushin [v,w] n = do
           oldValue <- VM.read capaVM n
           newValue <- VM.read capaVM (n+w)
           judge oldValue newValue
             where
               judge oldValue newValue
                 | n == 0 && newValue <= v  = kakikae
                 | n ==0                    = return ()
                 | newValue >= v + oldValue = return ()
                 | otherwise  = kakikae
                 where
                   kakikae = do
                     VM.write capaVM (n+w) (v + oldValue)
                     ans' <- readIORef ans
                     writeIORef ans (max ans' (v + oldValue))

だいぶコードがスッキリした。

mapM_ (koushin [v,w]) (reverse [0..(capa-w)])

このコードの意味は
仮に(capa-w)が2だとすると
koushin [v,w] 2
koushin [v,w] 1
koushin [v,w] 0
と順番に処理せよという意味。
resolveも同様に書き換えて再帰を排除（多分）
今度こそ行けるだろうと再提出をしてみた・・・

f:id:mikunimaru:20171116235532j:plain
ぐはっ！！

またまた原因を探る

方向性は間違っていたようだが
コードが読みやすくなり修正の労力は低減された。


次に狙いを定めたのはこの部分

  else mapM_ (koushin [v,w]) (reverse [0..(capa-w)])

[0..(capa-w)]が少々あやしい気がする。
この問題ではcapa = 1,000,000,000まで与えられるので
毎回生成をしていたらメモリの消費が半端ではない。
参照するコストも大きいだろう。

・・・という訳でひとまずここをVector.Unboxedにする事にした。

    else V.mapM_ (koushin [v,w]) (V.enumFromStepN (capa-w) (-1) (capa-w+1))

> V.enumFromStepN 1 (-1) 5
[1,0,-1,-2,-3]

そして再提出。
f:id:mikunimaru:20171117002922j:plain
えぇ・・・

根本的に間違えていた

途方に暮れて色々と調べてみると
どうもナップサック問題はナップサックの容量が巨大な時には
価値をベースにしてプログラムを組むらしい。

という訳で
初期のMapを使ったコードをベースに書き直してみた。

import Control.Applicative
import qualified Data.IntMap.Strict as Map
import Data.List (sort)

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <-map (map (read :: String -> Int) . words) . lines <$> getContents
  let maxValue = foldl1 (+) $ map head goods
  let ans = resolve capa maxValue (Map.fromList (zip [0..maxValue] [0,0..])) (reverse (sort goods))
  print $ if Map.null ans then 0 else fst $ Map.findMax ans

resolve capa maxValue valueMap ([v,w]:xs)
  | xs == []  = Map.filter (>0) koushin'
  | otherwise = resolve capa maxValue koushin' xs
  where
    koushin'
      | capa < w  = valueMap
      | otherwise = koushin valueMap [v,w] (maxValue-v)
    koushin valueMap [v,w] n
      | n == 0 && valueMap Map.! v > w        = Map.insert v w valueMap
      | n == 0 && oldWight == 0              = Map.insert v w valueMap
      | n == 0                                = valueMap
      | oldWight == 0                         = next
      | w + oldWight > capa                  = next
      | (w + oldWight >= newWight) && newWight /= 0 = next
      | otherwise = koushin (Map.insert (n+v) (w + oldWight) valueMap) [v,w] (n-1)
      where
        oldWight = valueMap Map.! n
        newWight =valueMap Map.! (n+v)
        next     = koushin valueMap [v,w] (n-1)

価値の高い順にソートしてから処理しているのがポイント。
提出してみる。
f:id:mikunimaru:20171117044101j:plain
f:id:mikunimaru:20171117045252j:plain
通った！！

処理の方法でこんなにも違うとはビックリ。
回り道はしたけども勉強になった。

もちろん更なる高速化の余地はありまくりなので
参考までにという事で。

Firefox Quantumでアドオンが使えない！！？過去のアドオンを利用する方法！！Waterfoxのダウンロードでサクサク＆アドオン復活へ！！

暮らしの疑問

いよいよFifefox Quantumがリリースしました

これにより、過去の高機能アドオンが

多数利用できなくなるという事態が発生しています。

諦めるしかないの？

しかし！！

firefoxはオープンソースのブラウザです。

 

オープンソースという事は

有志の手による改造も可能という事なんです。

 

今回はFirefoxの旧アドオンを使える上に

以前のFirefoxよりも高速化されるWaterfoxを紹介します。

Waterfoxのダウンロード方法

Waterfox Logo (redesigned 2015).png

まずはてっとり早くダウンロードリンクを貼っておきます。

 

www.waterfoxproject.org

Windows Linux Android macOSに対応しています。

 

ほぼ全ての環境で利用が可能です。

Waterfoxとは？

そもそもWaterfoxとは何なのでしょうか

firefoxはかつて32bit版のバイナリしか配布していなかったため

非公式ながら64bitに対応して、かつ様々な高速化オプションを付与してビルドしたのがWaterfoxです。

 

現在では公式でも64bit版のfirefoxが配布されていますが

Waterfoxほどの高速化はされていないのでバージョンが同じならこちらの方がサクサク動きます。

 

それだけですと売りが弱いのですが

今回firefoxが過去のアドオンの互換性を切った事で

Waterfoxは高速＋過去の資産活用という独自性を見出す事に成功したのです。

 

アドオンの使えないfirefoxはいくら高速化されたとしても

あまりメリットがありませんから

しばらくはWaterfoxのような旧アドオン互換ブラウザが乱立する事が予想されます。

 

みなさんもFirefoxの旧アドオンが使えなくなった際にはこちらに乗り換えて旧アドオンを復活させましょう。

将棋電王トーナメントで平成将棋合戦ぽんぽこが優勝！！Apery、やねうら王、Qhapaqなど各ソフトのダウンロード方法も紹介

将棋

先日行われた将棋電王トーナメントで

平成将棋合戦ぽんぽこが優勝した。

 

早速開発者の方々も最新のソフトをアップロードしてくれているようだ

今回はそれぞれのソフトのダウンロードリンクを紹介する。

 

関連スレ

2018年最強ソフト NNUE (TNK (たぬき))のダウンロードと使い方 - みくにまるのブログ

 

Apery

本体

http://hiraokatakuya.github.io/apery/

評価関数(やねうら王形式)

apery_sdt5_eval_twig_format.zip - Google ドライブ

やねうら王

まだ上がっていないけど多分ここに上がるはず

Releases · yaneurao/YaneuraOu · GitHub

Qhapaq

Release qhapaqの評価関数群 · qhapaq-49/qhapaq-bin · GitHub

Qhapaqの評価関数も公開されたようです。

GitHubのqhapaq-sdt5.zipというリンクからダウンロード出来ます。

平成将棋合戦ぽんぽこ

Releases · nodchip/hakubishin- · GitHub

優勝ソフトの平成将棋合戦ぽんぽこの評価関数は上記のリンクからダウンロード出来ます。

読み太

githubで公開されました。

Releases · TukamotoRyuzo/Yomita · GitHub

上記のリンクからダウンロード出来ます。

HoneyWaffle

しばらく先に公開予定とのこと

人造人間18号

KPPT型の評価関数を用いて

低スペックでも動作する庶民に優しいソフト。

18gou_sdt5 - Google ドライブ　評価関数

GitHub - Tama4649/18gou_bin: 人造棋士18号の実行ファイル

elmo

DeepLearningShogi

ディープラーニングを使った将棋ソフトも今回公開された

Pythonの設定が必要だったりと動かすまでに結構な知識が必要。

Releases · TadaoYamaoka/DeepLearningShogi · GitHub

ねね将棋

ディープラーニング勢

windowsで使うにはPythonのインストールが必要だ。

GitHub - select766/neneshogi: NEural NEtwork Shogi

海底

Releases · SakodaShintaro/kaitei · GitHub

開発者ツイッターまとめ

ソフトが公開されるかどうかを見るのが大変なので

自分用のメモも兼ねて開発者のツイッターアカウントをまとめる

 

平岡 拓也‹‹\(´･_･` )/›› (@HiraokaTakuya) | Twitter　Apery

やねうら王 (@yaneuraou) | Twitter

Qhapaq (@Qhapaq_49) | Twitter

nodchip@tanuki- (@nodchip) | Twitter　平成将棋合戦ぽんぽこ

48@shotgun (@bleu48) | Twitter　shotgun　48's diary

瀧澤 誠@elmo (@mktakizawa) | Twitter

みつひこ＠HoneyWaffle (@shiroi_gohanP) | Twitter

カツ丼将棋@五段(24基準) (@katsudonshogi) | Twitter

将棋ソフト「mEssiah」公式 (@messiah_ai) | Twitter

Yasuhiro Ike (@YasuhiroIke) | Twitter　うさぴょん

たま＠人造棋士18号(電王T13位) (@mm_Tamachan_mm) | Twitter

すえよし＠十六式いろは改公式 (@16shiki168) | Twitter

Hiroyuki Yamanouchi (@HiroYokohama) | Twitter SilverBullet

手塚規雄 (@noriwo_t) | Twitter SilverBullet

SilverBullet (@silverbullet_0) | Twitter

sako@海底 (@kaitei_shogi) | Twitter

山本一成@Ponanza (@issei_y) | Twitter

select766@ねね将棋 (@select766) | Twitter

だるま (@daruma3940) | Twitter　daruma3940の日記

むずでょ＠きふわらべ将棋電王T42位 (@muzudho1) | Twitter

香上 智＠Labyrinthus＋囲参戦 (@kagami_tomo) | Twitter

wandre@w@ndre@SDT5_19位 (@ihme_vaeltaa) | Twitter

名人コブラ (@meijincobra) | Twitter

HaskellでAOJ ITP1_6_B不足しているカードの発見

プログラミング Haskell AOJ

なくなったカードの発見 | プログラミング入門 | Aizu Online Judge

nput

最初の行に太郎が持っているカードの枚数 n (n ≤ 52)が与えられます。

続いて n 組のカードがそれぞれ１行に与えられます。各組は１つの空白で区切られた文字と整数です。文字はカードの絵柄を表し、スペードが'S'、ハートが'H'、クラブが'C'、ダイヤが'D'で表されています。整数はそのカードのランク(1 ～ 13)を表しています。

Output

足りないカードをそれぞれ1行に出力して下さい。各カードは入力と同様に１つの空白で区切られた文字と整数です。出力するカードの順番は以下のとおりとします：

絵柄がスペード、ハート、クラブ、ダイヤの順番で優先的に出力する。
絵柄が同じ場合は、ランクが小さい順に出力する。

初見での方針は
全カードのリストを作って
そこと与えられたカードとの差分を取る事。

ところが全カードのリストを作るスマートな方法が分からない。
["S","H","C","D"] と[1..13]を組み合わせたいがググって方法を探る。
日本語でググってもあまり情報が出て来ないので
hackageのData.Listと睨めっこする事にした。
しかしそんな都合のいい操作は見当たらず・・・

allcards = zip (repeat "H") [1..13] ++
           zip (repeat "D") [1..13] ++
           zip (repeat "S") [1..13] ++
           zip (repeat "C") [1..13]

仕方なく作ったのが上の関数。
・・・いくら何でもダサすぎる。
多少格好をつける為にも共通部分をくくる事にした。

allcards = cards "H" ++
           cards "D" ++
           cards "S" ++
           cards "C"
             where
               cards s = zip (repeat s) [1..13]

まだくくれる。

allcards = concat $ map cards ["H","D","S","C"]
             where
               cards s = zip (repeat s) [1..13]

なんとかそれっぽくなって一安心。


扱いにくいので
タプルをリストにする関数も作成。

tupleToList :: (String, Integer) -> [String]
tupleToList (s,n) = [s, show n]

allcardsList :: [[String]]
allcardsList = map tupleToList allcards


ここで
["D","13"]のようなリストよりも
"D 13"のような一つのStringにした方が更に扱いやすい事に気付く。
という訳でtoupleToListを改造。

tupleToString :: ([Char], Integer) -> String
tupleToString (s,n) = s ++ " " ++ show n

allcardsList :: [String]
allcardsList = map tupleToString allcards

こういった方針転換を簡単に出来るのがHaskellの良さだ。
出力では順番にとなっているので
最初に全カードを作る時の関数を順番通りになるように変更。

import Data.List ((\\))

allcards :: [([Char], Integer)]
allcards = concat $ map cards ["S","H","C","D"]
             where
               cards s = zip (repeat s) [1..13]


tupleToString :: ([Char], Integer) -> String
tupleToString (s,n) = s ++ " " ++ show n

allcardsList :: [String]
allcardsList = map tupleToString allcards

main = do
  s' <- getContents
  let s = tail $ lines s'
  putStr $ unlines $ allcardsList \\ s

最終的に上記のコードで通ったので
答え合わせに達人達のコードを拝見

r = [x | x <- [(s : ' ' : (show n)) | s <- "SHCD", n <- [1..13]]

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1716949#1
リスト内包表記でスマートに書けたようだ。

Prelude> [x | x <- [(s : ' ' : (show n)) | s <- "SHCD", n <- [1..13]]]
["S 1","S 2","S 3","S 4","S 5","S 6","S 7","S 8","S 9","S 10","S 11","S 12","S 13","H 1","H 2","H 3","H 4","H 5","H 6","H 7","H 8","H 9","H 10","H 11","H 12","H 13","C 1","C 2","C 3","C 4","C 5","C 6","C 7","C 8","C 9","C 10","C 11","C 12","C 13","D 1","D 2","D 3","D 4","D 5","D 6","D 7","D 8","D 9","D 10","D 11","D 12","D 13"]

う〜む、これは美しい。勉強になった。

HaskellでEOFを受け取るまで処理を繰り返すのに苦労したのでメモ

プログラミング Haskell AOJ

４つの整数の和 | Aizu Online Judge

50 以下の正の整数 n を入力し、0 ～ 9 の範囲の整数 a,b,c,d の組で

a+b+c+d=n

を満たすものの組み合わせ数を出力するプログラムを作成して下さい。

とりあえずパパっと作ったコードがこれ

combinations n = [[a,b,c,d] |a<-[0..9],
                             b<-[0..9],
                             c<-[0..9],
                             d<-[0..9],
                             a+b+c+d==n ]
main = do
  n <- readLn
  print $ length $ combinations n

ところがWrong Answer
試しに手元にテスト用のファイルを作って実験すると
50行ほど入力してみるも1行分の答えしか出力しない。
それではまずい。

単にgetContensするのも面白くないので
EOFを受け取ってから停止するように書き換えてみた

import System.IO

combinations n = [[a,b,c,d] |a<-[0..9],
                             b<-[0..9],
                             c<-[0..9],
                             d<-[0..9],
                             a+b+c+d==n ]
main = do
  n <- getLine
  print $ length $ combinations (read n)
  eof <- isEOF
  if eof then return ()
         else do
           main

EOFを受け取ったら終了
そうでなかったらgetLineを繰り返すプログラムだ。

最初はhIsEOFにして失敗したりで
完成までに丸1日かかってしまった。

参考
haskell - Why isEOF doesn't work? - Stack Overflow
System.IO モジュール(8) isEOF, hIsEOF : tnomuraのブログ
各言語の標準入出力サンプル｜CodeIQ│CodeIQ