授業の課題でコードゴルフをした
こんばんは、かささぎです。
授業でLZSS符号を復号するプログラムを作れって課題が出ました。
割と単純にできると感じ、そのまま解くのも面白くないのでコードゴルフをしてみることにしました。
コードゴルフとはどれだけソースコードを短く書けるかを競う競技です。
メソッドが豊富で短く書きやすいといわれるRubyで挑戦することにしました。
制約
- 参照部5bit、符号化部2bitで符号化されたLZSS符号(Algorithms with Python / LZ77 符号 (LZSS 符号))を復号する
- 暗号化したデータをアスキーコードで出力したファイル"test1.enc"を読み取り、復号を行う
- 出力にはputsを用いる(pやppはデバッグ用のため)
- Windows環境
ソースコード
コードの短縮においては、こちらのページを参考にさせて頂きました→RubyのコードゴルフのTips - Qiita。
r="";File.open("test1.enc","rb").read.chars.map{|i|i=~/\w/?i:(i.bytes[0]-128).divmod(4)}.each{|v|r+=v.size==1?v:(r[v[0]..-1]*4)[0,v[1]+1]};puts r
145bytesで書けました。思ったより短くなりました。
解説
LZSSのアルゴリズムではなく、コードゴルフに重きを置いて解説していきます。
作成したコードをわかりやすく書くとこんな感じになります。
r = "" f = File.open("test2.enc","rb") d = f.read.chars d.map!{|i| i.match(/\w/) ? i : (i.bytes[0]-2**7).divmod(4) } d.each do|v| r+=v if v.size==1 if v.size==2 then l = r[v[0]..-1].to_s * 4 r += l[0,v[1]+1] end end puts r
変数rに復号で得られた文字を追加していって、最後に出力するという構造です。
File.open()の第二引数は文字コードを指定しています。Windowsの文字コードでは"rb"とする必要があります。
UNIX系では"r"のみでいいようなので、もう1byte短縮できますね。
Windowsでは改行の文字コードが2bytesらしいので、セミコロンで連結することによって1byteで抑えました。
RubyでのコードゴルフにWindowsは向いてなさそうですね。。。
取り出した文字が\w(単語を構成する文字)に引っかかるかどうかで、dに格納するデータを分岐します。
divmodメソッドは割り算の商と余りをリストとして出力してくれます。このメソッド好き。
ちなみに、matchメソッドは=~と置き換えることができたので、6bytes短くできました。
あとはdのデータをeachでループして、データサイズごとに処理を変えています。
3項演算子を用いてかなり短く書くことができました。
3項演算子は、
- 可読性が死ぬから悪だ
- 絶対に使うな
- if,else大量に使うよりはいいだろ
- 1行で収まる範囲ならOK
- PHPではやめとけ
など論争が続いていますが、コードゴルフにおいては正義です。たぶん。
感想
始めてコードゴルフをやってみたのですが、結構楽しかったです。
Rubyは多数のメソッドがあり、短いものに置き換えれることがあるという点で、いろいろ調べたりして実装するのが勉強になりました。
またRubyでは()やスペースをかなり省略できることを知り、驚きました。たぶんこれをやらなかったら気づきませんでした。
もとはこちらの記事→Ruby FizzBuzz最短コードメモ (51bytes) ネタバレ注意 - Qiitaでfizzbuzzのコードを見て、なんだこれってなって興味を持ちました。
このコードほど可読性を落とすことはできなかったのですが(可読性を落とすことが目的ではない)、コードゴルフのおもしろさというものを実感できた気がします。
まだここを改善できるみたいな点がありましたら、教えてください。
それでは。
procon29参加記
こんにちは、かささぎです。
10月27~28日に開催された第29回高専プログラミングコンテストに参加してきました。
今回はこの参加記を書いていきます。
移動部門
最寄駅から金沢まで鈍行、金沢からサンダーバードで大阪、大阪から徳島までバスという感じで移動しました。
サンダーバード内では作成したシステムのデバッグをしてました。
プロコンってなんやかんや移動中の作業が一番捗る気がしませんかね?
イベントループの構造を大幅に変えるという大がかりな修正になりましたが、無事完了しました。
今回はよく旅に携帯する無印のネッククッションを研究室においてきたため、移動中に寝るのが辛かったです。
二つ目の購入を考えてるほどいいものなので、みんなも買おう!(ダイマ)→
https://www.muji.net/store/cmdty/detail/4550002125325?searchno=1
クソ揺れるバスに乗って3時間ほどで、徳島につきました。
ついた#procon29 pic.twitter.com/R0j0KvWl6Y
— かささぎ (@hrt9092) 2018年10月26日
四国初上陸です。
3車線道路や駅前を見ると結構都会かなと思ったけど、駅から歩いて少し離れると、うん、って感じでした。あと会場遠い。
競技アイデア募集企画
今回はこれに参加するためにプロコンに来ました。
これは、次年度以降の競技部門でこのような競技をやりたい、というアイデアを提案するものです。
競技部門25回目の記念として(最近の競技の評判が悪いため)開催されたようです。
私達のチームは「数揃えなサイ」というアイデアで参加しました。
敷き詰めたサイコロを回転させて目標の目にそろえるというパズルを競技として提案しました。
自由部門や課題部門のように、見に来た人に説明したりデモをしたりしてました。
企業の方がたくさん来られた印象がありました。
また、競技名の元ネタにした競技参加者の方にも来ていただき、サイコロトークをしたりしてました。
サイコロにオスメスがあるとは。。。
説明はだいたいうまくできましたが、Micr〇s〇ftの方に「この問題結構簡単じゃない?」って突っ込まれました。
そこそこな難易度はあるのではないかと考えていたのですが、つよい方に言われるとそうなのかもなってなります。
そのあと同じことを、某ネクタイが光ってる社長さんにも突っ込まれました。
つよいひとこわい#procon29
— かささぎ (@hrt9092) 2018年10月28日
自分でも解くためのアルゴリズムは一応考えていたので、ソルバを作ってみて計算量を把握しておけばよかったと反省しました。
結果ですが、競技部門の決勝の前に発表がありました。
優秀賞をいただきました。
優秀賞頂きました#procon29 pic.twitter.com/my63H7slHD
— かささぎ (@hrt9092) 2018年10月28日
最優秀賞は沼津高専OB,優秀賞に自分たちのほかに長野高専OBが選ばれてました。
OBっょぃ。ヵてなぃ。。。
ブースに見に来てくれた方、ありがとうございました。
ABC109 D - Make Them Even
こんばんは、久しぶりにABC4完でき、嬉しかったのでwrite upします。
最近は4完どころか3完すらままならないことが稀によくあります。。。C問題の難化激しくないですかね。
さて、問題はこちら。
「偶数枚のコインが置かれたマスの数を最大化してください」
ということから、奇数枚のコインがあるマス二つの間を移動すればいいことがわかります。
最初は出力方法が複雑だけど簡単だなーって解いたんですが、WA。
問題をよく読み返してみると
「まだ選んだことのないマス」
という制約がありました。2WAでようやく気付いた←
考えた結果、このような方向に従ってコインを移動すれば、ルートが被り同じマスを2度選ぶ必要がないことがわかりました。
左上からスタートし、右へ進んでいって、改行したら次は左へ進んでいきます。
たとえば、4*4のマスで(1,2)のコインを(2,1)へ移したいときは、
(1,2) → (1,3) → (1,4) → (2,4) → (2,3) → (2,2) → (2,1) と移動することになります。
これを、奇数のマスが2つ未満になるまで繰り返せばACです。
時間ギリギリで、いいコードにはできませんでしたが、とりあえず解けたので良かったです。
opencsvで区切り文字を指定して読み込み
こんにちは、かささぎです。絶賛ニート中です。
今回はjavaでopencsvを用いてCSVファイルを読み込む話をしていきます。
CSVファイルとは
カンマ区切りとも呼ばれる、カンマで値を区切ったデータファイルです。
基本的な読み込み
こんな感じです。
try{ FileReader fileReader = new FileReader(new File("hoge.csv") ); CSVReader reader = new CSVReader(fileReader); List<String []> datas = reader.readAll(); }catch(Exception e){ e.printStackTrace(); }
これを実行すると、datasにlistとして一行ずつデータが格納されていきます。
区切り文字等の設定
CSVは基本的にカンマ区切りですが、スペースやタブなど、他の文字で区切りたいこともあると思います。
その際にはCSVReaderの第二引数に区切り文字を設定して...と思ったのですが、
Intellijさんに横棒を付けられました。
実行してみると推奨されなくなったみたいです。
ggると、
http://opencsv.sourceforge.net/apidocs/com/opencsv/CSVReader.html
代わりにCSVReaderBuilderを使えって書いてありました。
これをもとにソースを苦しみながら解読して実装しました。
区切り文字をスペースにする例は以下のようになります。
try{ FileReader fileReader = new FileReader(new File("hoge.csv") ); CSVPerser parser = new CSVParserBuilder().withSeparator(' ').build(); CSVReader reader = new CSVReaderBuilder(fileReader).withCSVPerser(parser).build(); List<String []> datas = reader.readAll(); }catch(Exception e){ e.printStackTrace(); }
解説します。
CSVReaderBuilder().build() と CSVReader() は同じものを表すようです。
withCSVParser() でparserの設定を加えることができるようです。
parserもreader同様、Builder().build()にする必要があります。
withSeparator(char) でセパレータ(区切り文字)を設定できます。
この前後に.でつなぐことで、他にもいろいろな設定ができるみたいです。
例えば、withQuoteChar(char)で引用符の文字を設定したり、
withIgnoreQuotations(true)で引用符を無視する設定にできたりします。
他にもReaderで先頭n行をとばす設定ができたりと、いろいろ用意されているので、
是非調べてみてください。
それでは。
応用情報技術者試験に合格しました
こんばんは、かささぎです。
今年の春に応用情報技術者試験を受けていたのですが、受かってました。
受験記を軽くまとめていきます。
受験二か月前
参考書を買いました。
バイブルです。。。日本語が読めるなら買うべき。。。
~受験前日
一応まじめに勉強しました。
午前は過去問をとりあえず全部解き、間違えたところを分野別にまとめ理解しようとしました。
そのあとにもう一度解いて、まあ合格ラインぐらいは行けるかなって感じになりました。
午後は必須選択のセキュリティの用語だけ覚えました。
正直午前対策だけで時間が無くなりました。
とっかかりが遅すぎましたね。
結局、出たとこ勝負で挑むことにしました。諦めの境地ですね。
当日
午前は問題にUSB typeCが出てきたり、仮想通貨が出てきたりで結構予想外でした。
所感としては、過去問に比べやや難しい気がしました。
午後はとりあえずセキュリティと、開始前から必ず選択することを決めていたプログラミングを解きました。
プログラミングはナイトの巡歴問題が出ました。これが簡単だったので救われた感があります。解答例を見る限りはたぶん満点が取れたと思います。
後の3つの選択は、解けそうなのを5個ほど解いて、その中で点数の取れそうなものを3つ取りました。
経営戦略・システムアーキテクチャ・組込みシステムを選びました。
経営戦略は国語のテストみたいな感じで、文章の抜き出しなどが多く割といけました。
システムアーキテクチャはクラウドに関しての問題が出ました。結果はぼちぼちでした。
組み込みシステモは知りません。。。。。
結果
午前・午後ともギリギリで受かっていたみたいです。
参考書は過去問を解いてパターンをつかむ感じで行くといい気がしました。
実際の試験では過去問になく突然出てくるような問題(仮想通貨など)もありましたが、そのような問題の対策より、頻出する内容を重点的に取り組んだほうが良いと感じました。
午後の試験では、多くの問いを深く考えすぎずスピーディーに解いていったのが功を奏した結果になりました。
また問題文中にヒントがあることが多かったので、時間が余ったら諦めずに読んでみるのもいいかなと思いました。
こんな感じでなっているかわからないアドバイスは終えて、試験を総括します。
_________________________________________
今回はこれ
で何とかなったけど、次回からの試験では真面目に勉強する。
_________________________________________
それでは。
processingからjsonを解析した
こんにちは、かささぎです。就活とかテストとか一段落して、急に暇になって虚無感がつのっています。
今回はProcessingでJSONを触ります。私のブログのアクセス数がトップの記事はこちらの記事で、javaでJSONを利用するものです。アクセスの半分くらいがこれなので、試しにエゴサしてみたところ、
「Java JSON」で検索すると、この記事が1ページ目に表示されました。
「Processing JSON」では上位にヒットしませんでした。
そこで、Processing向けのJSON利用について試して、書いていくことにしました。
jsonとは
可読性が高いというメリットがあるデータの形式です。こんな感じのデータです。
{ "items":[ { "name" : "apple", "id" : "A01", "price" : 150}, { "name" : "grape", "id" : "A02", "price" : 300 }, { "name" : "onion", "id" : "B01", "price" : 50 } ] }
以降は、このデータをサンプルとして説明していきます。
Processingでの利用
jsonの解析には一般的にはライブラリを用いますが、ProcessingではJSONObjectというクラスが標準で実装されています。大きなデータの処理などが必要な際はjsonライブラリを利用してもよいですが、今回はライブラリのインポートや利用法を学ぶのがめんどくさいので難しい処理はしないので標準ライブラリを利用します。
- JSONデータの読み込み
読み込みにはloadJSONObject関数を利用します。引数にはファイル名かURLを入れます。
jsonのファイルをdata.jsonとすると、
JSONObject json = loadJSONObject("data.json");
となります。jsonをprintすると、jsonファイルと同じものが表示されます。
- JSON配列の取得
jsonでは、{}で囲まれたものをJSONObject、[]で囲まれたものをJSONArrayと呼びます。JSONArrayでは複数の要素を格納することができます。
JSONArrayの取得にはgetJSONArrayメソッドを用います。今回のデータでは"items"というタグの中のJSONArrayを取得するので、以下のようになります。
JSONArray jarr = json.getJSONArray("items");
これをprintしてみると、以下のようになります。
[ { "price": 150, "name": "apple", "id": "A01" }, { "price": 300, "name": "grape", "id": "A02" }, { "price": 50, "name": "onion", "id": "B01" } ]
- JSONオブジェクトの取得
続いて、{}で囲まれたJSONobjectを取得します。取得にはgetJSONObject関数を用います。引数には要素数を入れます。
例の"apple"が入っているデータを取得する際には、
JSONObject j0 = jarr.getJSONObject(0);
で取得できます。これをprintすると
{ "price": 150, "name": "apple", "id": "A01" }
と表示されます。
- 要素の取得
要素の取得にはgetString関数、getInt関数、getBoolean関数などを利用します。取得する値の型によって使い分ける必要があります。引数にはタグをString型で入れます。
String name = j0.getString("name"); int price = j0.getInt("price");
以上でProcessingでのJSONの解析ができました。
WebAPIを利用して天気予報を表示
JSON形式は、WebAPIにおいても利用されることが多いです。
そこで今回はJSONでのWebAPIを提供している、Livedoor Weather Web Serviceを利用して、天気予報をProcessingのスケッチに表示するプログラムを作成してみました。
ホームページのAPIの仕様を見ながら作成していきました。
ソースコード・実行結果を以下に載せます。
<ソースコード>
gist95d733118d8f8eadc42a9f17a85d413b
<実行結果>
長いので、解説は簡単にしていきます。
city = ? の?を変えることで、天気予報の都市を設定することできます。
JSONデータの概形の取得はloadJson関数で行いました。URLでの利用は、通信がうまくいかないときのためにtry,catchで例外処理をしておくとよいです。
このAPIにはアイコン画像のデータもあったので、PImage関数でURLを指定して読み込んでみました。
やはり画像をロードするためか、やや実行時間がかかりました。
電車の時刻になったら通知を飛ばすシステム Growlで通知編
どうもかささぎです。ヒンナヒンナ。
前回の記事の続きです。
時刻表のデータを取得することができ、これをもとに通知する部分を作ったのでその部分を書きます。
Growl for Windows
Windowsの通知にはGrowlを利用することにしました。
本当はWindowsの通知センターに直接表示できる通知を送りたかったのですが、どうやらC#のプログラムでないと厳しそうなのでGrowlという通知を送ることができるソフトウェアを利用することにしました。
以下のHPからダウンロード&インストールします。
http://www.growlforwindows.com/gfw/
その後コマンドラインで以下のコマンドを実行し、ruby_gntpというライブラリを実行できるようにします。
gem install ruby_gntp
Hash
Rubyでは連想配列としてHashクラスが用意されています。連想配列とは名前を付けられる配列のようなものです。
前回出力したCSVのデータ構造は以下の通りです。
5,27 6,14 7,4,29 8,10 ...
これを行の先頭の値をkey,残りを配列としてvalueに格納することにします。
コードは以下のようになりました。
data = CSV.read("TimeTable.csv") data.map! { |item| [item[0].to_i,item[1..item.length].map! { |i| i.to_i } ] } table = Hash[*data.flatten(1)]
CSV.readは以下のような構造で取得できます。
[["5","27"],["6","14"],["7","4","29"],["8","10"],…]
数値ではなく文字列型となります。
次の行ではブロックごとに処理を行い、戻り値で配列を生成して返すmapメソッドを利用しています。
長さが2の配列で、最初の要素は元データの先頭の値、次の要素には元データの先頭以外を配列にしたものを格納しています。
また、同時にデータとして扱いやすいようint型にキャストしています。
これを行った時のdataは以下の通りです。
[[5,[27]],[6,[14]],[7,[4,29]],[8,[10]],…]
最後の行では配列をHashに変換するHashメソッドを用いています。
これはこちらの記事を参考にさせて頂きました→
ArrayからHashに変換する方法いろいろ
最終的にtableは以下のような感じになります。
{5=>[27], 6=>[14], 7=>[4, 29], 8=>[10],…}
実装
学校から駅まで徒歩で15分ほどかかるので、余裕を持たせて20分前に通知を飛ばすことにしました。
<ソースコード>
gist2564d5b69bcffe5382c2ccd75d0bb0e9
GNTP.nontifyメソッドで通知を送ることができます。
app_name → アプリ名、
title → 通知のタイトル、
text → 通知の内容、
icon → アイコン画像、
sticky → クリックするまで通知を出したままにするかどうか
を設定することができます。
<実行結果>
とりあえずやりたいことは完成することができました。
あとはこれをタスクスケジューラでトリガを1分毎に設定し…と思っていたのですが。。。
トリガは最短でも5分間隔でしか設定できないみたいですね。
まあ20分を切ったら通知のようにしてもよいのですが、なんだか思ってたのと違うなって感じです。
やはりユーザサイドでなくサーバサイドで実装するべきだった気がします。
余裕があったらAWSかAzureでも利用して作り直してみたいと思います。
それでは。