« 2005年11月 | メイン | 2006年01月 »

2005年12月29日

仕事納め

12/28は仕事納め。
16時から会社の食堂で、宴会開始。人数たくさん。
21時ごろ、湘南台へ移動し、坐わたみで2次会。10数人。
午前1時、善行へ移動し、スナックで3次会。6人。
午前3時、藤沢へ移動し、朝までやってる居酒屋で3次会。3人。
帰ろうか。となったのが、朝の8時。

投稿者 hiranoy : 20:04 | コメント (0)

2005年12月18日

練習会&忘年会に参加

12/17 関東組練習会に参加しました。
今回は、前回と同じ、文京シビックホール。
開始時間が15時からだとばかり思っていて、遅れて行きました。
松ちゃん一家にご挨拶。
Thinkmoverさんの職場がうちの近くらしい。
着いてからさっそくロボカーナにチャレンジすべく、セッティングをしました。
で、ロボカーナにチャレンジしたのですが、途中で転んで、起き上がりもうまく行かないことがあり、完走できませんでした。
完走できないロボット5台で、リレー形式のロボカーナもお遊びで開催していただいたので、第4走者として参加。これは、直線だけだったので、無事完走しました。
石川さん、撮影お疲れ様でした。

練習会終了後、丸の内線で、後楽園→淡路町の移動。そして、ひろしに向かいました。
ひろしでは、バトルが開催。わが「メカボンB」は、道楽さんの「か~る」にさくっと負けました。
ねじ浅井さんに、たくさんねじをいただきました。ありがとうございました。

2次会は、万世橋のそばのいつもの居酒屋ビル。ビッグボスの熱い思いをたくさん聞くことが出来ました。

お開きになったところで時計を見るととっくに終電は無く、えまのんさん、まさゆきさん、石川さんとわたしの4人で朝までカラオケへ。前回の練習会では、カラオケ探して神田まで歩いたのですが、今回は石川さんがリサーチ済みで、秋葉原駅東口側のカラオケボックスに行きました。面子の年代も近いので、完全にリミッター解除状態で、15~25年前のアニソン、特撮、農耕士コンバインなどを歌いまくりでした。楽しゅうございました。

投稿者 hiranoy : 20:43 | コメント (0)

2005年12月16日

公衆無線LANを使ってみた

組み込みDBのセミナーを聞きに仕事で五反田へ。
五反田まで来て会社のPHSと個人の携帯電話を忘れてしまったのに気がついたので、カミさんにPCからメールを送るためマクドナルドの公衆無線LANを使ってみようと、五反田駅の東口でマックを探すも、見つからず。西口まで来てやっと発見。
コーヒーを買って、ノートPCを広げ電波を探すが2階ではだめ、3階も客席なのでそちらに移動したところ、電波をキャッチ。使い方は@Niftyで調べていたので、問題なく接続。無事カミさんへのメールも送り終えました。なかなか快適でした。

投稿者 hiranoy : 22:37 | コメント (0)

2005年12月15日

情報処理技術者試験(ソフト開発)合格!

今日は、ソフト開発技術者試験の合格発表の日。

不合格だと思っていましたが、IPA(情報処理推進機構)のHPで確認すると、合格してました。
合格といっても、自己採点では午前、午後I、午後IIの全部ボーダーラインだと思っていたので、

点数を照会してみると、
---------------
午前試験のスコアは,645 点です。
午後I試験のスコアは,620 点です。
午後II試験のスコアは,610 点です。
---------------
予想通りボーダーライン(600点)すれすれで合格でした。

合計点は、春の方が良かったので、運で受かったようなもんですね。
次の目標は、エンベデッド
エンベデッドの試験内容は、仕事でやってる分野なので、これは一発で合格しないといけないなぁ。

投稿者 hiranoy : 22:03 | コメント (0)

2005年12月13日

アルゴリズム問題、解けるかな?

行きつけのblogで、アルゴリズムの問題が出されていた。

-------------------------------
【問題】 単方向リストがある。ノード数を n とするが、n の値は分からない。リスト中にループ(循環参照)が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは禁じ手とする。
-------------------------------

しかも、「エンジニアを自認している人は是非チャレンジしてみてください。」ときたもので、やらずにはいられません。

循環参照が存在すると、それをたどって何か処理しようとしても、無限ループになるだけなので、「禁じ手」と書いてあるマーキングが一番素直なやり方と思うが、禁じ手なので他を考える。
ベタな方法としては、リストのポインタを、配列にコレクションして行き、新しく追加する要素がすでにコレクションの中にあれば、循環参照となるが、これはコレクションの要素の参照回数が、1,2,3,4と増えていくので、n(n+1) = O(n^2)にはなってしまう。

あれこれ考えて、何とか回答らしき方法が見つかりました。
(私の回答を見たくない人は下の「続きを読む」をクリックしないでください。)

私の答え
「逆方向への単方向リストに変換したときに、変換前のHead が指し示す要素のNextの値がNULLではない場合、循環参照がある」

逆方向への変換に最大約2n回の処理、リストを元に戻すために最大約2n回の処理で、最大約4n回がかかるが、O(n)の表記法だと、O(n)に分類される。

以下、説明。
-----------------
下記のような循環参照の単方向リストがある。

Head 「Next=2」

2 「Next=4」

4 「Next=3」

3 「Next=1」

1 「Next=4」→4へ (←循環参照)

このリストを、逆方向の単方向リストに変換する。まずは、循環していないところまで。

・Headが2を指しているので、2をリストの終端にするため、2の内容を変数に退避し、「Next=NULL」と変更する。退避した内容が、「Next=4」だったので、次に4の処理を行う。
・逆方向のリストだと、直前に処理した2がNext=となるべきなので、4の内容を変数に退避し、「Next=2」と変更する。退避した内容が、「Next=3」だったので、次に3の処理を行う。
・逆方向のリストだと、直前に処理した4がNext=となるべきなので、3の内容を変数に退避し、「Next=4」と変更する。退避した内容が、「Next=1」だったので、次に1の処理を行う。
・逆方向のリストだと、直前に処理した3がNext=となるべきなので、1の内容を変数に退避し、「Next=3」と変更する。退避した内容が、「Next=4」だったので、次に4の処理を行う。

ここまで処理すると以下のようになる。

2 「Next=NULL」

4 「Next=2」

3 「Next=4」

1 「Next=3」 ←ここまで逆方向に変換、1には「Next=4」が入っていたことが分かっている。

さらに循環のところを処理していく。

・逆方向のリストだと、直前に処理した1がNext=となるべきなので、4の内容を変数に退避し、「Next=1」と変更する。退避した内容が、「Next=2」だったので、次に2の処理を行う。
・逆方向のリストだと、直前に処理した4がNext=となるべきなので、2の内容を変数に退避し、「Next=4」と変更する。退避した内容が、「Next=NULL」だったので、ReverseHeadという変数を用意して、そこに2を入れる。これで逆方向への変換は終了する。

すると、以下のようなリストを得る。

Head=2 ReverseHead=2
↓       ↓
2 「Next=4」

4 「Next=1」→1へ

3 「Next=4」

1 「Next=3」

よって、答えは、
「逆方向への単方向リストに変換したときに、Head が指し示す要素のNextの値がNULLではない場合、循環参照がある」
ということになる。

リストを破壊した状態で終了するといけないので、再度ReverseHeadから辿って、逆方向への変換を行うと、リストは元通りになり、本当の意味で処理終了となる。

念のため、循環がない場合の例

Head 「Next=2」

2 「Next=4」

4 「Next=3」

3 「Next=1」

1 「Next=NULL」

逆方向へ変換すると

Head 「Next=2」

2 「Next=NULL」

4 「Next=2」

3 「Next=4」

1 「Next=3」

ReverseHead 「Next=1」

となり、Headが指し示す要素の内容は、「Next=NULL」となる。

-----------------------------

投稿者 hiranoy : 03:44 | コメント (0)

2005年12月09日

SH2-7045F用書き込み制御プログラム

SH2の7045F用の、書き込み制御プログラムを作成しましたので、ソースコードを公開しておきます。(他でも動作すると思いますが、7045Fでのみ動作検証しましたということです)

SH2でいう「書き込み制御プログラム」とは、簡単に言うと、SH2のフラッシュへ書き込む時にSH2側で動作するソフトです。SH2-7045Fのハードウェアマニュアルの22章「256kBフラッシュメモリ(F-ZTAT)」に詳しい説明があります。

全てアセンブラで記述しましたので、コンパクトで内臓RAMの空き領域が多く、機能を追加したい方にはうってつけです。(私も、今後、通信速度の高速化とSH2に繋がったシリアルEEPROMへの書き込み機能を追加する予定です。)

シリアル転送プロトコルは、h8write と同じにしてあります。

使い方:
みついわゆきお氏作 h8write.c の中の bin7045[] 配列の中身を、下記の bin7045.txt の内容をコピペして置き換えて使用します。が、通信速度は9600bpsのままで、そこがボトルネックなので、書き込み速度に関してオリジナルと性能の違いはありません。どちらかというと、ソースがあるので、改造してみたい人用です。

ソースコード bin7045.asm
h8write.c 組み込み用テキストファイル bin7045.txt

投稿者 hiranoy : 03:01 | コメント (0)

2005年12月05日

11/26、11/27のこと

久々の投稿となりました。

11/26 の出来事から。

前の晩から徹夜で、マイクロマウスのソフトの改良。
ターンの角度が不安定なので、お尻をぶつけて姿勢を修正しながら走るようにします。
だいたい出来上がったので、迷路で探索走行をさせてみると、角度は安定したのですが、変なところに壁を作ってしまい、おかしな探索をします。2時間ほど格闘しましたが、原因不明。
じゃあ、少し前のソフトをベースに、お尻ぶつけを作ろうと作業開始。で、まだ作業途中でしたが、出発の時間になってしまいました。
湘南台から戸塚まで地下鉄。戸塚から湘南新宿ラインで大崎。大崎からりんかい線で国際展示場と行く予定が、大崎で寝過ごして恵比寿まで行ってしまいました。もともと家を出るのが遅れたため、予定通りに着いて、受付締め切りが9時40分のところに、国際展示場駅に9時34分着という予定でした。
恵比寿からの時間を再度計算すると、会場に着くのが10時くらいということで、出場をあきらめました。事務局に電話して何とかしてもらうことも出来たのかもしれませんが、去年からほとんど進歩しなかったので、そういうこともする気になりませんでした。
で、睡魔も襲ってきたので、目黒の漫画喫茶でしばし睡眠。午後に、ちょっとだけマイクロマウスの会場に行って、二足の練習会に参加するため、後楽園へ向かいました。

シビックホールへ着くとすぐ分かるだろうと踏んで「18時、シビックホール」としか記憶していなかったら、いやはや建物が大きいこと。しばらくうろうろ探してみましたがやはり会場が分かりません。しょうがないので、ノートPCをネットにつないで、練習会のHPを見て無事会場に到着しました。

ENNUIさんがお持ちになった恐竜ロボットはいろいろ考えさせられました。あれで1万円というのはすごいですし、きちんと歩く。重心が低いからああいうことが出来るのかなぁ。
JinSatoさんが見せてくださった、油圧アクチュエータの4足ロボットもすごい。横から思いっきり蹴られても、倒れる方向に足を出して支えて倒れない。これって、自分も二足で前からやりたい動きなんですよね。まだスキルが追いつきませんが。
メカボンBは、前の週の名古屋モーターショウから何もしていないので、ちょっと動かしてみたのと、あとは点検など。サーボブラケットSC-EZAの青パーツ(サーボホーンとフリーホーンにまたがってつけるこの字型のブラケット)が何箇所かで開き気味になっていて、ネジ止めしてないフリーホーン側が外れそうになってました。フリーホーンの中央から配線を出すと止められないんですよね。どうしたものか。

21時半で練習会を終了して、一行は流浪の民に。水道橋駅までの道すがら、店を探すも、東京ドームでイベントがあったらしく、食べ物屋・居酒屋がすべて満員もしくは22時頃に閉店で入れず。秋葉原の居酒屋へ。
居酒屋では、ロボット談義は、果てしなく続きます。
途中、snさんが、「でぶや」の録画を見せてくださいました。
アニメイダーさんは、「圧倒的な何かが必要だ!」と熱く語っておられました。ハイパワー俺サーボ期待してます。
居酒屋の後は、終電を逃した人たちで、カラオケに。でも探索の結果、秋葉原にはカラオケ屋が無いことが分かり、神田へ。朝まで盛り上がりました。

11/27 の出来事。
家に着いたのが、7時くらい。マイクロマウスの決勝を見に行くことにしていたので、11時半まで寝て、子供をつれて11時半に出発。車ではじめてお台場まで行ってみました。
13時ちょっとすぎだったので、もう決勝が始まっているかとおもったら、「パックマウス」のデモンストレーションをやってました。モンスターは、外周の上空にいるのですが、横から見ていると、パックマウスとの位置関係が分かりにくくて、パックマウスがモンスターにつかまった状態がわかりにくかったです。モンスターをビニール紐みたいなので作って、パックマウスにかぶさるようにすれば分かりやすいのではと思いました。
なんやかやで決勝が始まったのは15時ちょっと前だったでしょうか。今年からライトが強くなったためか、第2走行に成功するマウスが少ない感じです。去年のような、2辺直線というのはありませんでしたが、斜め走行を必要とする箇所がたくさんあったり、横壁が無い櫛型の箇所などがあったりで、姿勢制御に苦労しそうな迷路でした。
予選1位は、昨年優勝のシンガポールのkiatさんで、決勝の最後に登場されたのですが、スタート直後の斜め走行に入るターンが妙に遅く、2位に終わりました。ただ優勝も、シンガポールの方で、またシンガポールの優勝が続くこととなりました。

投稿者 hiranoy : 19:37 | コメント (0)