一万円を崩す方法(Haskell)

一万円を両替して崩す方法は何通りあるだろうか.ただし:
・百円玉,五百円玉,千円札を自由に(好きなだけ)使って良い.
・五百円記念硬貨は10枚までしか使えない.
・二千円札は2枚までしか使えない.

この問題は以前の千円を崩す方法(Haskell)の変種である.新しい要素は五百円記念硬貨(普通の五百円玉と区別される)と二千円札である.どちらも個数(枚数)に制限がある.

答えは1561通りになるはず.

以前の記事では組み合わせ的な考察だけから漸化式を導いて解いたが,今回は母関数を使わねば漸化式を導くことができなかった.

これを求めためのHaskellプログラムは次のようになる:

p n = if n < 0 then 0
      else if n `rem` 100 == 0 then 1
      else 0
q n | (n < 0) = 0
    | otherwise = p n + q (n-500)
r n | (n < 0) = 0
    | otherwise = q n + r (n-1000)
s n | (n < 0) = 0
    | otherwise = r n - r (n-5500) + s (n-500)
t n | (n < 0) = 0
    | otherwise = s n - s (n-6000) + t (n-2000)

問題の答えは t 10000として求まる.

ブログに数式を書くのが面倒になったので,数列を母関数を通して扱う話からはじめて,このプログラムを導く過程をPDFにまとめてみた.(文字を大きくしておいたのでスマホでも読めると思う):数列と母関数

広告

切手を貼る方法(Haskell)

■問題:2セント,4セント,6セント,8セントの切手を封筒に一列に貼って10セントにしたい.何通りの方法があるか?(異なる並べ方は違う方法としてカウントする).

■注意:つまり「2,2,4,2」と「4,2,2,2」は違う方法としてカウントされる.

■問題出典:Pólya & Szegöの “Problems and Theorems in Analysis I”の問題3である.

{b_n}によって,『{n}セントを支払う方法の数』を表す.組み合わせについての簡単な考察により

{b_0 = 1.}
・負の添字に対して {b_n = 0.}
{b_n = b_{n-2} + b_{n-4} + b_{n-6} + b_{n-8}.}

がわかる.これを素直にHaskellのコードに移すと:

b :: Int -> Int
b n | (n < 0) = 0
    | (n ==0) = 1
    | otherwise = b (n-2) + b (n-4) + b (n-6) + b (n-8)

となる.よって b 10 を求めればよい.

$ ghci
Prelude> :l b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )

Ok, modules loaded: Main.
*Main> b 10
15

答えは15通りである.

■ Pólya & Szegöの “Problems and Theorems in Analysis I” では,さらに数列 {b_n}の母関数の閉じた式が扱われている.(今回は必要ないので扱わない.)

SSDのデータサルベージ

■要約:「KURO-DACHI/CLONE/U3」で故障したSSDからデータを吸い上げられた.
※いつでもうまくいくわけではなく,私の場合うまく行ったという体験談です.

随分昔から重要なデータだけは外付けのSSDにsvnリポジトリで管理するようにしている.そのうちの一台がついに一切アクセスできなくなった.たまたま,少し容量の大きなSSDが余っていたのでダメ元で玄人志向「KURO-DACHI/CLONE/U3」で「丸ごとコピー」を試したところ,見事にコピーできた.

C94:『簡約!?λカ娘(11)』が出ました+正誤表

C94の1日目(2018/08/10)でλカ娘11巻を頒布しました.今回も超準解析の記事ですが,前回までの超準集合論に基づくものではなく,一番ポピュラーだと思われる上部構造による超準解析の記事となっています.

印刷後に数箇所の誤りを見つけました.このリンク→に私の記事の正誤表を掲げておきます.

表紙絵はこちらです(pixiv):夢幻召喚セイバー衣装のイカ娘

Cドライブの交換(作業メモ)

■要約:「KURO-DACHI/CLONE/U3」とAOMEI Partition Assistant でCドライブの交換を楽にすませた.1000円ぐらいのSSD用外付けケースもあると便利.

ずっと使っているパソコンのCドライブが300GBで手狭になってきたので交換することにした.
交換先として2TBのSSD(SanDisk Ultra | 3D SSD)を買った.SSDと一緒に玄人志向「KURO-DACHI/CLONE/U3」(以下では「KURO」と略す)というのを買った.

この「KURO」には3.5inchのHDD二台を同時に差し込むことができる.電源だけ入れて(USBでパソコンにつないでいない状態)「clone」というスイッチを押すだけで簡単にHDD1からHDD2にまるごとコピーできるというのが売りらしい.以前DドライブをバックアップしたときにはUbuntuを使って面倒な作業をしたけれど,これなら疲れていて集中力が落ちていても失敗しないだろうと考えた.

■「この手順でやればよかったな」というコピーの流れ:
1.自分のCドライブがMBRなのかGPTなのか確認する.(「mbr gpt 確認」でググってほしい).忘れないようにメモしておく.少し古いPCだと大抵MBRだと思う.
2.新品のSSDを外付け用ケースに入れてPCに接続し,自分のPCに合わせて MBR, NTFSで初期化する.
3.古い300GBのSSDを「KURO」の「HDD1」に,新しく買った2TBのSSDを「HDD2」に挿入し,「KURO」の電源を入れる.そして小さな「clone」というボタンを押す.正面四つのランプが左右に行き来する感じにオレンジ色に点滅する.
4.コピーが完了(四つのランプが同時に点滅を繰り返す状態)したら「KURO」の電源を切って2TBのSSDをPCにつなぎ,起動する.

■実際に試行錯誤しながらやったコピー作業:
1.メインPCの電源を切り,電源を抜く.
2.PCの筐体を開け,CドライブSSDを取り出す.(ドライバが必要になる作業)
3.古い300GBのSSDを「KURO」の「HDD1」に,新しく買った2TBのSSDを「HDD2」に挿入し,「KURO」の電源を入れる.そして小さな「clone」というボタンを押す.

これでコピーが始まるはずだったのだが,データの転送を示すLEDの点滅が始まらない.

なんらかの方法でSSDを初期化しないといけなかったらしい.(他の人が書いた体験記などを読むとどうも初期化なんかいらないというようなことも書いてある.こちらの条件と何が違うのかよくわからない.なにか私が読み落としたのかもしれない).それはともかく,私がやったのは:

4.2TBのSSDを「KURO」から取り出し,簡単な(1000円ぐらいの)ケースに入れてノートPC(メインじゃない方)に接続した.そして「Windowsマークを右クリック –> ディスクの管理」を開いてSSDをMBR,NTFSで初期化した.(これは自分の古いPCに合わせた.自分のCドライブがMBRなのかGPTなのかは前もって確認しておく必要がある).

5.2TBのSSDを再び「KURO」に戻し,「copy」ボタンを押した.するとコピーが始まった.数十分でコピーは完了する.(正面四つのランプが同期してオレンジ色に点滅し続けるのが完了の合図).
6.「KURO」の電源を切り,2TB SSD をメインPCに刺し,全てのケーブルを元通りにつなぐ.
7.メインPCの電源をつなぎ,起動テストする.

何事もなく「Resume From Hibernation」と表示されたのを見て「この子自分の脳が交換されたのに気づいてないんだろうな」と思ってちょっと面白かった.

■コピー後の作業:
さて,「KURO」の「丸ごとコピー」では全てがそのままコピーされるので,新しいCドライブも300GBまでしか認識されていない.「Windowsマークを右クリック –> ディスクの管理」を通じてその様子が確認できる.

System Reserved | Windows (C:) | 回復パーティション | 未割当て(1.5TB)

のようになっており,ここの未割当の1.5TBを割り当てても,間の「回復パーティション」で隔てられていてCドライブを大きくすることができない.「回復パーティション 移動」で検索し,AOMEI Partition Assistant の無料バージョンでパーティションの移動を行った.GUIですっとパーティションを動かして「確定」するだけで作業が完了するので衝撃を受けた.

32ビット?64ビット?(自分用メモ)

■gccが32ビットか64ビットか:
gcc -v の出力の Target: のところを見る.

32ビットの場合 Target: mingw32
64ビットの場合 Target: x86_64-pc-msys

などのようになる.システムの細かな差異によって文字列は少しずつ違うが,64ビットの場合 x86_64 が部分文字列としてしばしば含まれる.

■ghcが32ビットか64ビットか:
次のようなファイルを作る:

main = print ()

そして

$ ghc --make foo.hs
[1 of 1] Compiling Main             ( foo.hs, foo.o )
Linking foo.exe ...

$ file foo.exe

32ビットの場合には
PE32 executable (console) Intel 80386, for MS Windows

64ビットの場合には 
PE32+ executable (console) x86-64, for MS Windows

のようになる.

■おまけ:
自分がどの gcc を使ってるのかわからなくなった場合などは
which -a gcc
すればよい.使い分けをしたい場合は適宜 .bashrc に alias を張ればよさそう.

HaskellからFFIでCの配列を扱う(マーシャリング)

HaskellのFFIについてはこのブログでも例えばこんな記事で扱っている.

今回はその記事では触れなかったマーシャリングについて扱う.まずは次のようなCの関数があったとしよう:

#include <stdlib.h>
#include <stdio.h>
#include "c_header.h"

/*
int sum(int* p);

int fib(int** pp, int n);
*/

int sum(int* p, size_t n)
{
  if(n == 0){ return 0; }
  size_t i;
  int retval = 0;
  for(i = 0; i < n; ++i)
  {
    retval += p[i];
  }
  return retval;
}

int fib(int** pp, int n)
{
  if(n<=0){ return 1;}
  *pp = malloc(n * sizeof(int));
  if(n>=1){ (*pp)[0] = 1;}
  if(n>=2){ (*pp)[1] = 1;}
  if(n>=3){
    int i;
    for(i=2; i < n; ++i)
    {
      (*pp)[i] = (*pp)[i-1] + (*pp)[i-2];
    }
  }
  return 0;
}

これらのコードは次のように使われる:

#include <stdio.h>
#include <stdlib.h>
#include "src/c_header.h"

#define N 10
int main(void)
{
  int array[] = {1,2,3,4,5,6,7,8,9,10};

  int s = sum(array, sizeof(array)/sizeof(array[0]));
  printf("sum=%d\n",s);

  int* p = 0;
  int r = fib(&p,N);
  if(r==1){ printf("failed"); }
  else{
    int i;
    for(i=0; i < N; ++i)
    {
      printf("fib(%d)=%d\n",i,p[i]);
    }
  }
  free(p);
  return 0;
}

sumやfibは次のようにHaskellから扱える:

module Lib
    where

import Foreign.C.Types
import Foreign.Ptr
import Foreign.Marshal.Array
import Foreign

-- int sum(int* p, size_t n);
foreign import ccall "c_header.h sum" cSum
  :: Ptr CInt -> CSize -> IO CInt

hSum :: [Int] -> IO Int
hSum xs =
  let
    xs' = fromIntegral <$> xs :: [CInt]
    len   = fromIntegral $ length xs :: CSize
  in
  do
    arr <- newArray xs' :: IO (Ptr CInt)
    l <- return len  :: IO CSize
    ret <- cSum arr l :: IO CInt
    return $ fromIntegral ret

-- int fib(int** pp, int n);
foreign import ccall "c_header.h fib" c_fib
  :: Ptr (Ptr CInt) -> CInt -> IO CInt

hFib :: Int -> IO [Int]
hFib n =
    do
      ptrOut <- malloc  :: IO (Ptr (Ptr CInt))
      n' <- return $ fromIntegral n :: IO CInt
      ret <- c_fib  ptrOut  n' :: IO CInt
      out <- peekArray n =<< peek ptrOut :: IO [CInt]
      free =<< peek ptrOut
      free ptrOut
      return (fromIntegral <$> out) :: IO [Int]

cSum と hSum, c_fibとhFibのシグネチャは結構ずれている.
関数cSumは sum と同様にポインタとサイズを受け取る.hSum ではサイズを配列から計算しているので長さを引数にする必要がない.
また,c_fib では二重ポインタと長さを引数にしているが,hFibでは長さだけが引数となっている.c_fib の引数となっている二重ポインタは出力用の変数だからである.

次のコードはhSum,hFibの使用例である.

module Main where

import Lib

main :: IO ()
main =
  do
    a <- hSum [1,2,3,4]
    print a
    xs <- hFib 15
    print xs

stack でこのコードをビルドする場合,stack.yaml に次のような行を加えねばならない:

c-sources:  src/c_impl.c

optparse-generic (Haskell)

自分用メモ.

必要なことはすべて https://github.com/Gabriel439/Haskell-Optparse-Generic-Library から辿れるhttp://hackage.haskell.org/package/optparse-generic/docs/Options-Generic.htmlに載っている.

■optparse-genericとは何ですか?:コマンドライン引数を処理するライブラリの一つです.

■インストール:stack install optparse-generic

■サンプル:

{-# LANGUAGE DataKinds          #-}
{-# LANGUAGE DeriveGeneric      #-}
{-# LANGUAGE FlexibleInstances  #-}  -- One more extension.
{-# LANGUAGE OverloadedStrings  #-}
{-# LANGUAGE StandaloneDeriving #-}  -- To derive Show
{-# LANGUAGE TypeOperators      #-}

import Options.Generic --stack install optparse-generic

data OptionInput  w = OptionInput
  { foo :: w ::: Int            <?>"Documentation for the foo flag"
  , bar :: w ::: Double         <?>"Documentation for the bar flag"
  , baz :: w ::: String         <?>"Documentation for the baz flag"
  , qux :: w ::: Maybe String   <?>"Documentation for the qux flag"
  , quux :: w ::: Bool          <?>"Documentation for the quux flag"
  } deriving (Generic)

instance ParseRecord (OptionInput Wrapped)
deriving instance Show (OptionInput Unwrapped)

main = do
    x <- unwrapRecord "program short description"
    let i = foo x :: Int
    let d = bar x :: Double
    let s = baz x :: String
    let s' = qux x :: Maybe String
    let b = quux x :: Bool
    print (x :: OptionInput Unwrapped)

■サンプルのビルド:stack ghc optiontest.hs
必要に応じて,package.yaml で
dependencies:
– optparse-generic

■サンプルを動かす:optiontest.exe --foo 2 --bar 3.478 --baz "hoge" --qux "fuga"

github メモ

自分用メモです.

■開発作業
git checkout -b hoge #作業用ブランチを作成
★自由にコード等を編集する.
git commit -m "fix bug" #変更内容をコミット
git push origin hoge #自分のレポジトリにプッシュ
★github ページに言ってPull Request を作る.
★権威ある人に merge してもらう.

■自分のレポジトリを最新の状態に更新する
(git remote add upstream git@github.com:foo/bar.git)← upstream の登録は一度やればいい
git checkout master #作業ブランチを master に
git pull upstream master
git push origin master #自分のレポジトリにpush

■開発ブランチにmasterの内容を適用する
git checkout master
git pull origin master
git checkout hoge
git rebase master

★叱られたらファイルを修正して
git rebase –continue

■何がうまくいかない場合とりあえず現状を把握する
git status

■Updates were rejected because the tip of your current branch
is behind とか言われた場合
git pull origin yourLocalBranchName

■ローカルでの変更が邪魔して pull できない場合
git stash save "some-name"

■作業ブランチの確認
git branch

■ブランチ一覧
git branch -a

■リモートブランチの一覧
git branch --remote

■リモートブランチ foo の削除
git push origin :foo

■リモートブランチ foo にある hoge ファイルだけ取ってくる
git fetch
git checkout origin/foo -- path-to-file

■作業ブランチをhogeに変更
git checkout hoge

■作業ブランチの名称を fuga に変更
git branch -m fuga

■手元のブランチ piyo をリモートに登録する
git push -u origin piyo

■git管理下にあるファイル一覧
git ls-files

■git管理下にあるファイルをすべてadd
git add .

■git管理下にあるファイルのリネーム
git mv aaa.txt bbb.txt

■出したプルリクを取り下げる
remoteにpush済みのブランチを削除することで紐づくpull requestを削除出来ます
git push --delete origin hoge

■url の確認
git remote -v

■git管理下にあるファイルを削除
git rm hogehoge
(ディレクトリごと:git rm -r hogedir )

■ファイルをローカルに残したままgit管理下からファイルを除く
(1) git rm --cached hogehoge
(2) .gitignore に追記する

■originの変更
git remote set-url origin git@github.com:foo/bar.git

■upstreamの変更
git remote set-url upstream git@github.com:foo/bar.git

■自分がコミットしたところだけログを見る
git log --author=differential.engine@gmail.com

こうやって
commit 23985b88d43328a72bacafb784d7e30f78357f83
Author: dif_engine
Date: Fri Jul 6 23:00:00 2018 +0900

だったとき
git diff 23985b88d43328a72bacafb784d7e30f78357f83 > hoge.txt
とするとコミット 23985b88d43328a72bacafb784d7e30f78357f83 から HEAD までの差分が手に入る.一般には
git diff COMMIT-ID1:COMMIT-ID2 > out.txt

uniq 的な関数(Haskell)

Haskell のリストから重複要素を除去する関数はnubである.「同じかどうか」を判定する関数を引数に取る nubBy を使いたい場合もある.これらの関数はリスト全体を舐めて重複要素を除去する.

扱っている配列がソート済みである場合も多い.その場合,隣接要素だけ見ていけば重複要素を除去できるはずである.そうすれば少しだけ効率が良いかも知れない.そう考えてこんな関数を書いてみた:

uniq :: (Eq a) => [a] -> [a]
uniq = foldr  uniqAux []
  where uniqAux :: (Eq a) => a -> [a] -> [a]
        uniqAux t [] = [t]
        uniqAux t (u:us) = (if t == u then [u] else [t,u]) ++ us

uniqBy を作るのも簡単である.

※効率がどうこうと言ったが,性能比較はまだしていない.