2022-04-24

Quartus Prime Lite Version 21.1のインストール

Quartus Prime Liteをインストールしてみたけど、最新のバージョン（19あたりからか？)のはまりどころが多い感じなのでメモ。

１．Questa Intel FPGA Starter Edition (ModelSim-Altera Starter Editionからの置き換え）

まず、ModelSim→Questaに名前が変わっている。Mentor GraphicsがSiemensに買収されたのでブランド名が変更になったらしい。まあバージョンアップとしては連続性があるもののようだけど、いろいろ細かい違いがある。

・Starterライセンス

まず、無料で使えるStarter Editionが、ModelSimのときはそのまま使えた（ライセンス登録しなければ制限付き無償版）のが、Starter Editionにも無償版のライセンス登録が必要になったらしい。なので、単にインストールするだけだと動かない。手順はマクニカのWebサイトに割と丁寧に解説されている

→Questa* - Intel® FPGA Starter Edition ライセンスファイルの取得および設定方法 - 半導体事業 - マクニカ (macnica.co.jp)

（これに限らずマクニカのサイト、Intel (旧Altera）FPGAの解説記事が充実している）

ここで自分の時はもう一つ落とし穴があって、上記のリンク先の記事の通り、Intelサイトに登録しないとStarter Editionライセンスの請求ができないんだけど、単に手順通り登録した直後は、機能制限のあるユーザ扱いで（ドキュメント閲覧のみ？）ライセンス請求のメニューが出てこなかった。どうしたら権限が変わるのかわからなかったけど、翌日には追加のメニューが表示されるようになったので、登録後に時間待ちが必要なのかもしれない。

・シミュレーション実行時の内部信号観測

Questaでシミュレーション実行後に信号を観測するとき、ModelSimの解説記事なんかの手順通りにやると波形観測の信号選択ができない。どうも後から内部信号の観測はできない最適化が行われるらしく、波形表示画面で任意の信号表示するには、内部信号の可視性を維持するモードにしないといけないようだ。

以前のバージョンではデフォルトで内部信号が可視になっていたのが、Questaではデフォルトが変わったらしい。

コマンドでは、voptコマンドで+accオプションを指定する。HDLのコンパイル後に、トップレベルモジュールを指定して

vopt -L <ライブラリ参照> +acc <トップレベルモジュール> -o <モジュール名_opt>

とし、モジュール名_optをシミュレータで読み込む。

vsim -L <ライブラリ参照> -c <デザインライブラリ>.<モジュール名_opt>

2. Nios II IDE

・インストール

Nios IIの開発ツール、EclipseベースだがEclipse本体のインストールは別途手動で行わなくてはいけない。Quartusのインストーラは、Nios II IDEのメニュー項目は作るが、Ecipseインストール前にそのメニュー項目から起動しようとしても何も起こらない。コマンドラインから実行ファイルをたたくと、Eclipseが起動できないとのエラーメッセージが出ている。

手動インストールの手順は、Nios II IDEのインストール先

C:\intelFPGA_lite\21.1\nios2eds\bin\README

にあるREADMEファイルに書かれている。Eclipse本体をダウンロード、展開し、eclipse_nios2にフォルダ名を変えてプラグインを上書き展開する。

・WSLのセットアップ

Nios II IDEはどうもUnix環境を前提にしたスクリプト群を含んでいるらしく、以前のインストールにはCygwinが含まれていたとのこと。しかし現在のバージョンでは、WSLの存在を前提としている。事前にWSLを有効化し、Ubuntu環境もインストールしておく必要がある。

さらに追加で以下のステップが必要。

dos2unixのインストール
WSLENV環境変数の設定

まず一つ目、Nios II IDEのスクリプトがWSLのdos2unixを呼び出すため、インストールしておく必要がある。Ubuntuなら、

sudo apt install dos2unix

でOK。二つ目、インストーラなりが設定してくれない環境変数がある。設定→詳細情報→システムの詳細設定→環境変数から、以下の環境変数とその値を設定する。

変数名: WSLENV

値: SOPC_KIT_NIOS2/p

これはWSL環境とWindows側で環境変数を共有する仕組みらしく、SOPC_KIT_NIOS2が共有が必要な環境変数。この環境変数自体の設定はNios II IDE自体がやっている。さらに、環境変数名に"/p"がつくことでパス名表記の変換をしてくれるらしい。

とりあえずここまでやったら、Quartus Prime Lite 21.1で論理合成からRTLシミュレーション、プログラム、Nios IIプログラム作成を行うことができた。Nios IIシステムの論理シミュレーションはどうかな...

2009-12-27

ファイルサーバ検索システムを作る

オープンソース HyperEstraier

職場でHyperEstraierを使わせてもらっているので、自分が引っかかっていろいろ試したことなど、この日記に何度か書いてきました。
でも、トピックごとにばらばらに書き散らしていただけだったので、ここらで一度、基本的な手順のまとめなど書いてみます。

なぜHyperEstraierか

ファイルサーバにいろいろな文書ファイルが降り積もってくると、どうしても必要なファイルを見つけ出すのが困難になってきて、「googleみたいに」検索して探したくなります。これを実現するのが全文検索エンジンと呼ばれるソフトウェアですが、それこそgoogle自身が販売している”イントラネットにつなげばgoogleで検索ができる”代物から、数十万オーダーの市販品、そして無償で利用できるオープンソースのプロダクトまで、いろいろとあります。
オープンソースの全文検索エンジンとしては、長くNamazuが定番でしたが、2005年あたりから、次世代をうたう全文検索エンジンが登場してきました。HyperEstraierはその一つで、Namazuに対して次のようなアドバンテージがあります。

Namazuのような辞書ベースの単語抽出を利用したシステムと違い、検索漏れが生じにくい
インデックスの生成・更新が高速
設置が簡単

設置の容易さについては、HyperEstraierはチュートリアル・ドキュメントもしっかりしているのですが、作者の平林さんがblogに書かれた、典型的なケースでの使用例の短い紹介が印象的でした。今は読めなくなっているようですが*1、ほんの数パラグラフの手順だけで、Windowsベースのファイルサーバ検索システムが構築できてしまいました。
ということで、それに代わる、とまでは言えませんが、最短のステップで検索システムを構築する手順をメモしておきます。

簡単な設置手順

１．パッケージのダウンロードとインストール

まずインストールですが、公式サイトからWindows用のバイナリパッケージをダウンロードして展開します。インストーラは特にないので、展開したフォルダ（estcmd.exeなどがある）にパスを通せばインストールは終わりです。

HyperEstraierは最新バージョン1.4.13までが公開されていますが、Windows用バイナリは1.4.10までしか置かれていません。1.4.10でもそれほど違いはありませんが、検索するとWindowsで最新版を独自にビルドして配布している方もおられるので、それを使用してもよいと思います。

私のビルドしたバージョン1.4.13も置いておきます*2。

２．IISのインストールとセットアップ

ファイルサーバ検索をWebブラウザから実行できるようにするため、Webサーバをインストールします。

HyperEstraierの検索ユーザインターフェイスは、CGIが使用できればWebサーバはなんでもいいのですが、すでにほかのWebサーバが稼働しているのでなければ、Windowsで標準的に利用されているIISでいいでしょう。

インストール時に注意する点としては、

ファイアウォールの例外設定で、80番ポートの解放をする必要があるかも
Vista以降のバージョンに付属のIIS（Ver.7.0以降？）は、CGIサポートがオプションになっているので、「Windowsの機能の有効化」を実行するときにチェックを加える

の2点ぐらいです。

次に、検索ユーザインターフェイスを提供する仮想ディレクトリを作成しておきます。IISの管理ツールから、”仮想ディレクトリの作成”を実行し、適当なエイリアス名（例として'searchpc'とします）とフォルダ（同じく'c:\inetpub\searchpc'とします)を設定します。このとき、ウィザードの途中のアクセス許可で、"CGIの実行"を許可しておきます。

３．最初のインデックス生成

２．で準備したフォルダ（c:\inetpub\searchpc）に移動して、検索のためのインデックスを作成します。検索の対象になるファイルサーバが"\\fserver\doc"でアクセスできるなら、バッチファイル'makeindex.bat'として以下の内容のファイルを作成し、実行します。

if not exist casket estcmd create -xl -attr _lreal seq -attr @cdate num -attr @size num casket
estcmd gather -cl -fx .pdf,.rtf,.doc,.xls,.ppt T@estxfilt -fz -ic CP932 -pc CP932 -sd -cm -cs 512 casket \\fserver\doc\
estcmd extkeys -um casket

2行目の'estcmd gather'で検索対象の共有フォルダを指定しています（共有名の場合は末尾に'\'が必要なようです）。複数の共有フォルダを検索対象とする場合、この行を複数並べることになります。

これで、カレントフォルダ下に'casket'というインデックスが作成されました。次のコマンドラインで、検索のテストを実行できます。

estcmd search -vh casket "検索キーワード" | estcmd iconv -oc cp932

４．検索Webインターフェイスの作成

最後に、検索のためのユーザインターフェイスを用意します。３．でインデックスを作成したフォルダは、IISからアクセスできるように設定しているので、HyperEstraierのインストールフォルダから、Webインターフェイス用のファイルとしてestseek.*と*.dllをコピーします。

さらに、コピーした設定ファイル'estseek.conf'の、'showlreal: false'という行を'showlreal: true'に変更しておきます。これで、検索結果に表示されるアンカータグの参照先がUNCパスそのままになります。

あとは、Webブラウザから'http://hostname/searchpc/estseek.cgi'にアクセスすれば、ファイルサーバ検索システムの出来上がりです。
インデックスの更新のために、３．で作った'makeindex.bat'を定期的に実行する必要がありますが、これは'コントロールパネル'→'タスク'に登録しておけば自動でやってくれます。
ついでに、インデックスの不要データ削除を実行する次のコマンドもバッチファイル'optindex.bat'にしておき、タスクに登録しておきましょう。

estcmd purge casket
estcmd optimize casket

自動実行の間隔は、makeindex.batが1日ごと、optindex.batが週一回程度でよいはずです。

ちょっとした問題点とその対処

以上のように、ちょっとした部門内ファイルサーバの検索システムであれば、わずか数ステップの作業で構築できてしまいます。この手軽さと、インデックス更新の速さはHyperEstraierの強力な利点ですが、使ってみると気付く問題点もいくつかあります。

一部のフォルダ名の下にあるファイルが、検索の対象にならない

公式配布のパッケージでは、”〜表”のような、文字コードの末尾に'0x5c'が来るような名前のフォルダ以下のファイルが検索の対象になりません。

フォルダ名の取り扱いの問題のようで、この日記の以前のエントリで調査と修正について記述しました。上でリンクした、私のビルドしたバージョン1.4.13では、この修正を行っているので、問題は生じないはずです。

検索結果のリンクにあらわれる一部の文字が化ける

ファイル名のパスに、WindowsのUnicode・マルチバイト変換で問題が生じる一部の文字が入っていると、パス情報が文字化けしてしまう場合があるようです。

私の場合、ファイルサーバ上の"〜"を含んだフォルダ名以下のファイルが、検索の結果に含まれるリンクからアクセスできなくなってしまいました（検索システムの持っているパス名の"〜"が、逆向きの記号になってしまう）。

これは文字コード変換ライブラリiconvとWindowsの仕様が食い違っているために生じる問題で、iconvをWindowsの動作に合わせるパッチもあるようですが、とりあえず簡単な解決策として、estseek.cgiの設定で変換することで回避しました。
estseek.confに以下の設定を入れています（手抜き）。

replace: 〜{{!}}〜

（と思って、ここに書いたら両方"〜"に変換されてしまいました...　右側は波ダッシュでなく、全角チルダ？です。なにか書き込む方法あるのかな？）

ファイルの種類やソート順の指定が難しい

検索のWebインターフェイスは、"MS Officeの文書を種類（Word/Excel/Powerpoint）を指定して検索したい" "検索結果のソート順をいろいろ変更したい"といった場合に、属性検索式を入力する必要があるなど、ちょっと難しい場合があります。

estseek.cgiに相当するプログラムを自分で書けばいいのでしょうが、なかなかそこまでできないので、estseek.cgiが使用するHTMLテンプレートに、Javascriptのコードを仕込んで多少の細工をしてみました。

かなり適当なので、私の手元の環境以外でどこまで動くか不明ですが、一応さらしておきます→estseek.tmpl改造版

IIS 7.0では追加の設定が必要（2010/1/13追記）

上の「IISのセットアップ」のところではスルーしてしまいましたが、Vista以降に付属のIIS 7.0では、estseek.cgiを実行するにはこれだけではだめなようです（そもそも”仮想ディレクトリの作成ウィザード”の中で、CGIの一括許可ができない）。必要な処置は：

追加した仮想ディレクトり（上記の例のsearchpc）で、拡張子*.cgiをCgiModuleに結び付けるマップを追加
IIS全体の設定で、特に指定していないEXEファイルのCGI実行を許可

の2つになります。どちらも、コントロールパネル→管理ツール→IISマネージャから設定します。

（１）拡張子CGIのマップ追加

IISマネージャ左のツリーから、<ホスト名>→サイト→Default Web Site→<仮想ディレクトリ名>を選び、このときの中央ペインで「ハンドラマッピング」をダブルクリックします。
右の操作一覧から、「モジュールマップの追加...」を選択します。
表示されるダイアログで、”要求パス”に"*.cgi"、”モジュール”からCgiModuleを選択し、”名前”欄に"CGI実行(*.cgi)"と入力してOKを押します。

（２）指定のないEXEの実行を許可

IISマネージャ左のツリーから、<ホスト名>欄を選び、中央のペインの「ISAPIおよびCGIの制限」をダブルクリックします。
右の操作一覧から、「機能設定の編集...」を選択します。
表示されるダイアログで、"特定できないCGIモジュールを許可する"にチェックを入れてOKを押します。

（１）、（２）の2つを実行して初めて、estseek.cgiがIISの元でCGIとして実行できるようになります。

*1:Internet Archiveには残っています。

*2:このパッケージは公式配布のものからJava/Rubyのサポートを除き、後で触れるディレクトリスキャン動作の問題の修正パッチをあてたものです。ライセンス・配布条件などはオリジナルに従いますが、公式配布と完全に同等であることは保障できません。特に、クローラ周りは全くチェックしていませんので、ご利用の場合はその点をご注意ください。

2009-12-08

xdoc2txtを使用しないテキスト抽出

HyperEstraier オープンソースプログラミング

勤め先の部門内ファイルサーバで、ずっとHyperEstraierによる検索システムを使用していたのですが、ここしばらく止めてしまっていました。

停止した直接のきっかけはサーバのクラッシュだったのですが、検索システムの再稼働を先延ばしにしていたのは、インデックス更新処理が止まらなくなるトラブルが起きていたからです。

インデックス更新処理トラブルの現象

現象としては、

ある特定のPDFファイル（とりあえず2つだけ）のxdoc2txtによるテキスト抽出処理が、CPUを使いきったまま停止しなくなる

というものでした。
問題が生じるのは数百GByteは消費しているファイルサーバ中のたった2つのファイルですが、何しろ止まらないので、夜間にインデックス更新させようとしても翌朝更新処理が終わっていないことになります。
気付いた時点でxdoc2txtを強制終了するのですが、今度はそこから残りのインデックス更新がはじまってしまいます。Hudsonによる定期ビルドも同じマシンでやっているので、高負荷になる処理の終了時間が読めなくなるのは大変にまずいです。

xdoc2txtを使用しないテキスト抽出

とりあえず該当のPDFファイルを（使ってなさそうだったので）ファイル名を変えてestcmd gatherが見に行かないようにしていましたが、今後同様のファイルが出ないとも限りません。できれば、よりトラブルが出にくいと思われる方法でテキスト抽出をするように変更したいところです。

そこで、第16回テキスト情報の抽出［その3］：検索エンジンを作る｜gihyo.jp … 技術評論社で触れられているWindows Desktop Searchが使用しているIFilterを使用することにしました。IFilterコンポーネントを使用すれば：

Office用のIFilterはMicrosoftから提供されているので、Officeデータファイルのテキスト抽出については安定した動作が期待できる
Windows環境での標準のテキスト抽出I/Fといえるので、ほかのフォーマットについても豊富にフィルタが供給されることが期待できる

といったメリットが考えられます。

インデックス更新処理バッチコマンドの変更

IFilterの実体はCOMのインターフェイスなので、本来の手順としては、処理対象のファイルに対応するフィルタをアクティブにし、IFilterインターフェイスのメソッドを適切に呼び出す必要があります。

しかし、単にテキスト抽出をするだけであれば、上記のURLで触れられているIFilterのデバッグ用ツールである、filtdump.exeが使用できます。

filtdump.exeは、MicrosoftのWindows Search SDKパッケージ（http://www.microsoft.com/downloads/details.aspx?FamilyID=645300AE-5E7A-4CE7-95F0-49793F8F76E8&displaylang=enからダウンロード可能）に含まれています。
使い方は、

filtdump.exe -b -o <出力ファイル名> <入力ファイル名>

のようにして呼び出せば、<入力ファイル名>のフォーマットに応じたフィルタを呼び出し、<出力ファイル名>に抽出されたプレーンテキストのみを書き出してくれます。

このとき、<出力ファイル>はUTF-16LEで書き出されるので注意が必要です。

また、filtdump.exeはほかにPlatform SDKやVisual Studioに含まれるものなど、いくつかのバージョンがあるようですが、比較的新しい、上記のWindows Search SDKに含まれるバージョンでは、<入力ファイル名>のパスが日本語文字列を含んでいると問題が起きる（フォーマットから対応するフィルタの決定に失敗する）ようです。

今回はestcmd gatherから呼び出すだけで、estcmdはフィルタに引き渡すファイルをデータベースフォルダ内に一時的にコピーしてそのパスを渡すので、HyperEstraierのデータベースを日本語を含まないパス内に配置しておけば問題になりません。

実際の使い方として、私はHyperEstraier付属のestxfilt.batから次の内容のestifilt.batを作りました。

@echo off
filtdump.exe -b -o %2 %1

そして、インデックス更新バッチコマンドの方は、estxfilt.batの代わりに上記を使用するように、

estcmd gather -fx .pdf,.rtf,.doc,.xls,.ppt T@estifilt -fz -ic UTF-16LE -pc CP932 -sd -cl -cm [catalog] [directory]

としました。MS-Officeの各ファイルとPDFに対してestifiltを使用し、その出力の文字コードはUTF-16LEとして扱います。

PDFファイルについてはまだ問題が...

以上の様に変更してテストをしてみたのですが、問題のPDFファイルの一つについては、IFilterで処理しても本文部分が文字化けしてしまい、内容の抽出がうまくできませんでした。

元のPDFファイルが部分的に異なるエンコードでも使用しているのか、原因はわかりませんが、少なくとも停止してしまうということはなくなったので、とりあえずよしとすることにします:-P*1

2010-01-06追記

この記事については、コメント欄でいろいろと教えていただきました。通りすがりさん、A-chanさん、ありがとうございました。
年を越してしまいましたが、本文の方にまとめておきます。

・xdoc2txtの更新

まず、IFilterを試すきっかけになった、xdoc2txtのトラブルですが、xdoc2txtは結構頻繁にアップデートされています。更新履歴を見ると、

・破損したPDFで異常終了するケースを修正 
・破損したPDFで無限ループになるケースがあるのを修正

などとありますから、今回のようなトラブルではまず、xdoc2txtだけでもアップデートしてみるのがいいでしょう。
ただ、今回問題になった2つのPDFファイルでCPU 100%のまま終了しなくなる現象は、Ver.1.35でも変わりませんでした。

・PDF用のフィルタプログラム

IFilterによる処理で文字化けするケースについては、A-chanさんにご指摘いただいたように、フォントのサブセットの埋め込みによって起こる現象のようです。本文の適当な文字列をコピーしても文字化けしてしまいますが、それを検索欄にペーストすると、正しく元の文字列にマッチします。

フォントのサブセットを埋め込む際に、元の文字コードの情報を完全に落とすというのもおかしな実装のような気もしますが、標準のPDF用IFilterをfiltdump.exe経由で使用しているだけではどうしようもないようです。

また、A-chanさんからは、このときのfiltdumpの挙動などから、PDFについてはpdftotextを使った方がよいのではないか？との情報をいただきました。今度試してみようと思います。

・0x5cワークアラウンド入りhyperestraier-1.4.13-win32

こちらの記事でとりあげたestcmd.exeのディレクトリスキャンルーチンが0x5cで終わるフォルダ名をうまく扱えない問題のワークアラウンドパッチ入りバイナリは、こちらからダウンロードできます。

記事中のパッチを当てて再ビルドしただけですが、再ビルドの過程でなにか問題が混入してしまっている可能性もありますので、あくまで非公式ビルドということでご利用ください。また、公式パッケージに含まれるruby/Java バインディングは取り除いてあり、クローラ関係は全くテストしていません。

また、パッチによらずにディレクトリスキャンを別のコマンドで実行する方法ですが、

cmd /c "for /R \\server\share %i in (*.*) do @echo %i" | estcmd gather casket -

とかでいいのでは、と思っていたのですが、、、うまく動きませんでした。今度調べてみます。。。

・Namazuとの比較について

本記事の内容とは離れてしまうのですが、コメント欄でA-chanさんにNamazuとHyperEstraierの比較について質問させていただきました（こちらの記事でNamazuに対するメリットを書きたかったためでした→id:aenomoto:20091227:1261932844）。

Namazuの辞書ベースのキーワード抽出が、辞書にない専門用語が多い文書では検索精度の低下を起こすこと
Namazuはインデクサがperlで実装されているが、これについても日本語を含むパス名に絡む問題があること
HyperEstraierの方がインストール〜設定が容易であること

などをコメント頂きました。ありがとうございます。

分かち書きとN-gram法の検索エンジンの方式の違いが、普通に使うだけでも実感できる程度のものなのか気なっていたのですが（当然文書の内容にもよるでしょうが）、辞書にない単語が多い文書で効いてくるというのは確かに納得できるところです。

Namazuでも日本語パス名がらみの問題があるというのはちょっと意外でした（NamazuはWindows環境も含めて、長い実績があると思っていたので）。ただ、perlの文字コード関係は、5.6と5.8以降でも全く違うし、5.8以降でスクリプトはUTF-8 エンコードを使用してもパス名関係は問題が出るようですので、確かに難しいのかもしれません。

・リンクまとめ

最後に、記事中の外部サイトへのリンクをまとめておきます。

内容	URL
IFilterの簡単な利用方法	http://gihyo.jp/dev/serial/01/make-findspot/0016
Windows Search SDK (filtdump.exeを含む)	[http://www.microsoft.com/downloads/details.aspx?FamilyID=645300AE-5E7A-4CE7-95F0-49793F8F76E8&displaylang=en
xdoc2txt本家	http://www31.ocn.ne.jp/~h_ishida/xdoc2txt.html
Xpdf本家 (pdftotext)	http://www.foolabs.com/xpdf/download.html
0x5cワークアラウンド入りhyperestraier-1.4.13-win32	http://www.hi-ho.ne.jp/a-enomoto/hatena/hyperestraier-1.4.13-win32.zip

*1:フォントの埋め込みによって、元の文字コードの情報がなくなっている(?)ようです。コメント欄と下の追記を参照。

2009-10-11

TopCoder SRM144 DIV1 (550)

プログラミング C++ TopCoder

次の550点問題は、組合せの問題です。
・いろいろな種類の数当てゲームがある。ゲームのルールのリストが入力されるので、それを「当てやすい順」に並べ替えて返せ。
・ゲームのルールは、「使用する数の範囲（１から10〜100）」「当てる数の個数（1〜8組）」「必ず昇順で現れるとするか」「同じ数値が2度以上現れるか」の4組のパラメータで与えられる。
ということで、各ルールのパターンごとに数値の組合せの数を計算すればいいようです。「必ず昇順」のルールがない場合は簡単で、そのままべき乗と順列です。
しかし、「必ず昇順で現れる」の場合がわからなくて困りました。「同じ数値が2度以上現れる」と組み合わさった場合だと、どこも降順にならなければいいので、同じ数値の連続も入れて考える必要があります。
で、しばらく悩んだ結果、「当てる数」を順に決定していくとして、b番目に使用する数がcであるような場合の数を $P(b,c)$ とすると、
$P(b,c)=\sum^c_{k=1}P(b-1,k)$
$P(1,c)=1$
という風に1つ前の数を決める場合の数で表せるので、これを「当てる数の個数」まで繰り返し計算し、最後に合計をとることで求めました。
こうすると、「必ず昇順」かつ「同じ数値は現れない」場合はこの変形で、
$P(b,c)=\sum^{c-1}_{k=1}P(b-1,k)$
$P(1,c)=1$
として同様に計算できます。
結果、作成したのがこのコード：

#include <iostream>

#include <vector>
#include <algorithm>
#include <string>

#define NUMBER_OF_ARRAY(array) (sizeof(array)/(sizeof(array[0])))

using namespace std;

class Lottery {
	class LessPtnrsRule;

	class Rule {
		string m_name;
		int m_choice, m_blanks;
		bool m_sorted, m_unique;

		bool read_from_str(const char* in_str) {
			unsigned char c1, c2;

			if (! in_str) return false;
			const char* pos_sep = strchr(in_str, ':');
			if (pos_sep && in_str < pos_sep) {
				m_name = string(in_str, pos_sep - in_str);
				if (sscanf(pos_sep, ": %d %d %c %c", &m_choice, &m_blanks, &c1, &c2) == 4) {
					m_sorted = c1 == 'T' ? true : false;
					m_unique = c2 == 'T' ? true : false;
					return true;
				}
				else {
					return false;
				}
			}
			else {
				return false;
			}
		}

	public:
		//typedef unsigned long counter_t;
		typedef unsigned long long counter_t;

		Rule(const char* in_str = NULL) : m_choice(), m_blanks() { read_from_str(in_str); }
		Rule(string& in_str) : m_choice(), m_blanks() { read_from_str(in_str.c_str()); }

		int GetChoice() const { return m_choice; }
		int GetBlanks() const { return m_blanks; }
		bool IsSorted() const { return m_sorted; }
		bool IsUnique() const { return m_unique; }
		const char* GetName() const { return m_name.c_str(); }

		counter_t num_of_patterns() const {
			counter_t num_ptrns = 0;

			if (m_choice < 10 || 100 < m_choice) return 0;
			if (m_blanks < 1 || 8 < m_blanks) return 0;

			if (! m_sorted) {
				num_ptrns = m_choice;

				counter_t n_choice = m_choice;
				for (int i = 1; i < m_blanks; ++i) {
					if (m_unique) --n_choice;
					num_ptrns *= n_choice;
				}
				return num_ptrns;
			}
			else { // m_sorted is true
				vector<counter_t> path_cnt_prev(m_choice, 1);
				vector<counter_t> path_cnt(m_choice, 1);

				for (int i = 1; i < m_blanks; ++i) {
					for (int i = 0; i < path_cnt.size(); ++i) path_cnt[i] = 0;
					
					for (int c = 1; c <= m_choice; ++c) {
						if (! m_unique) {
							for (int k = 1; k <= c; ++k) {
								path_cnt[c - 1] += path_cnt_prev[k - 1];
							}
						}
						else {
							for (int k = 1; k <= c - 1; ++k) {
								path_cnt[c - 1] += path_cnt_prev[k - 1];
							}
						}
					}
					path_cnt_prev.assign(path_cnt.begin(), path_cnt.end());
				}

				for (int i = 0; i < path_cnt.size(); ++i) {
					num_ptrns += path_cnt[i];
				}

				return num_ptrns;			
			}
		}

		friend class Lottery;
		friend class Lottery::LessPtnrsRule;
	};

	struct LessPtnrsRule {
		bool operator() (const Rule* lhs, const Rule* rhs) const {
			Rule::counter_t lhs_ptrn = lhs->num_of_patterns();
			Rule::counter_t rhs_ptrn = rhs->num_of_patterns();

			if (lhs_ptrn == rhs_ptrn) {
				return lhs->m_name < rhs->m_name;
			}
			else {
				return lhs_ptrn < rhs_ptrn;
			}
		}
	};

public:
	vector<string> sortByOdds(vector<string> rules) {
		vector<Rule*> ptrn_list(rules.size());

		for (int i = 0; i < rules.size(); ++i) {
			ptrn_list[i] = new Rule(rules[i]);
		}
		sort(ptrn_list.begin(), ptrn_list.end(), LessPtnrsRule());

		vector<string> result_list(rules.size());
		for (int i = 0; i < rules.size(); ++i) {
			result_list[i] = ptrn_list[i]->GetName();
		}

		return result_list;
	}
};

submit後に気付いたこと：

「必ず昇順」かつ「同じ数値は現れない」場合は、ただのコンビネーション( ${}_c%5Cmathrm{C}_b$ )になることに、他の人のコードを見て気付いた。
Practiceでは、メニューからすぐにシステムテストを走らせることができる（メイン画面のPractice Options→Run System Test）。やってみたら、1カ所初期値を間違えていて「当てる数の個数」が1個のときに間違った答えになっていた...（上のコードは直したもの）

これを時間制限付きでやるのはなかなかしんどそうです。また今度トライしてみよう。

2009-10-11

TopCoder SRM144 DIV1 (300)

プログラミング C++ TopCoder

やっぱりちゃんと勉強しなきゃ、ということでTopCoder SRMに挑戦してみることにしました。でもまだ自信がないのでPracticeだけ。
登録の手順などは、こちらを参考にさせていただきました。→ http://d.hatena.ne.jp/gnarl/20080828/1219893152

まずは、Practice Rooms→SRMsで一番最初にある、SRM144 DIV1から。
300点問題の概要は：

文字列表記された2進数を暗号化する手順が定義されている。
手順は、「各桁ごとに、前後合わせた３桁分の数字を合計した数に置き換える」というもの。
この暗号化された数値列（定義から0〜3が現れる）を入力として、元の2進数を復元して返す関数を書け。

とういもの。
親切なことに、実装すべきアルゴリズムが問題文中で実例付きで解説されています。基本的にはそれをそのままコードに落とせばよさそうなのですが...ループへのまとめ方とか、境界条件の取り方とか細かいところで迷って時間がかかってしまいました。
コンテストでは、プラグインをインストールして自前のエディタとの連携やテストコードの自動生成をやる人が多いようですが、まずは様子を見るつもりで単に横でMS Visual Studioを立ち上げ、コンソールアプリのプロジェクトを作ってそこにコードを切り貼りして試しました。
ということでこんなコード：

#include <iostream>

#include <vector>
#include <string>

using namespace std;

class BinaryCode {
  string decode_with_assume(int p0, string message) {
    string result_str;
    result_str.append(1, p0 + '0');

    int pv = p0, ppv = 0, d = p0;
    for (size_t i = 0; i < message.size(); ++i) {
		int q = message[i] - '0';
		int p = q - d;
		if (i == message.size() - 1) {
			if (q == d)
				return result_str;
			else
				return string("NONE");
		}

		if (p == 0 || p == 1)
			result_str.append(1, p + '0');
		else 
			return string("NONE");

		d += p;
		d -= ppv;
		ppv = pv;
		pv = p;
    }
    return result_str;
  }

  public:
    vector<string> decode(string message) {
		vector<string> result_cons;

		result_cons.push_back(decode_with_assume(0, message));
		result_cons.push_back(decode_with_assume(1, message));
		return result_cons;
    }
};

2009-07-28

設定ファイルのバックアップ重要

プログラミング Trac

職場で、Trac Lightningを使わせてもらっています。

先日、使っていた2.2.3 → 2.2.5へアップデートとしたのですが、プロジェクトのバックアップを取った後、うっかりApacheのhttpd.confはバックアップを取らずに上書きインストールしてしまいました。

一応、インストーラのオプションで「Apacheの設定を上書きする」をOFFにしたのですが、再起動してみるとサービスの起動ができません。httpd.confのエラーになるので、内容を見てみると、

...
# at a local disk.  If you wish to share the same ServerRoot for multiple
# httpd daemons, you will need to change at least LockFile and PidFile.
#
ServerRoot "C:\Program Files\CollabNet Subversion Server/httpd"
...

設定上書きオプションをOFFにしても、CollabNet Subversion Serverパッケージのhttpd.confがコピーされてしまうようです。Hyper Estraierの検索ページとか、globalの生成したソースコードインデックスとか、いろいろ追記していたのに...

教訓：データのバックアップを取ったら、合わせて重要な設定ファイルのバックアップも取ること。アップデートのときは特に。

多分、http://sourceforge.jp/forum/forum.php?thread_id=19942&forum_id=11624 と同じ現象ですね。レポートしてみよう。

めも日記

Quartus Prime Lite Version 21.1のインストール

１．Questa Intel FPGA Starter Edition (ModelSim-Altera Starter Editionからの置き換え）

・Starterライセンス

・シミュレーション実行時の内部信号観測

2. Nios II IDE

・インストール

・WSLのセットアップ

ファイルサーバ検索システムを作る

なぜHyperEstraierか

簡単な設置手順

ちょっとした問題点とその対処

一部のフォルダ名の下にあるファイルが、検索の対象にならない

検索結果のリンクにあらわれる一部の文字が化ける

ファイルの種類やソート順の指定が難しい

IIS 7.0では追加の設定が必要（2010/1/13追記）

最近のヒット

xdoc2txtを使用しないテキスト抽出

インデックス更新処理トラブルの現象

xdoc2txtを使用しないテキスト抽出

インデックス更新処理バッチコマンドの変更

PDFファイルについてはまだ問題が...

2010-01-06追記

・xdoc2txtの更新

・PDF用のフィルタプログラム

・0x5cワークアラウンド入りhyperestraier-1.4.13-win32

・Namazuとの比較について

・リンクまとめ

TopCoder SRM144 DIV1 (550)

TopCoder SRM144 DIV1 (300)

設定ファイルのバックアップ重要