こけめも

メモみたいなもの

GDD2011のDevQuizにチャレンジしたのでコード晒し (〜分野クイズ編)

DevQuizへの挑戦


今年になって存在を知ったGDDとDevQuiz。
今年は是非参加したいと思いながら事前登録を忘れており、公開から遅れること数日、9/1に登録してチャレンジ開始です。

ウォームアップクイズ

ウォームアップクイズはググったりChrome拡張使ったりで、2回目でクリア。
Googleの画像検索って画像ファイルをもとに検索できるのね。こりゃ便利。
知人に教えたところ「長年の疑問が解消された」と感謝されてしまいました。
まんまとGoogleの策略にはまってる気がする…
Search by Image – Inside Search – Google


○参考ページ:
HTML5 Forms Status - The Chromium ProjectsChromeHTML5対応状況?


分野別クイズ

どのコードも言語の特徴を生かせていない、正直晒すと株が下がりそうなコードばかりですが、自分への戒めも込めて公開してみます。
次はもっと質やメンテナンス性、テストのしやすさも向上させたいです。


ソースコードは下記でも公開しています。
https://github.com/kokemono/GDD2011_DevQuiz

Web Game

まずは一番上にある「Web Game」からチャレンジ。
ひとまずヒントをダウンロードして動作させてみることにしました。


一昔前のFirefox拡張はいじったことあるのですが、Chromeは未体験です。
とりあえずChrome拡張機能をのぞいてみると「デベロッパーモード」→「パッケージ化されていない拡張機能を読み込む」というものが。
修正内容がすぐに反映されるし、開発中は助かる機能ですね。


上記機能でヒントを解凍したフォルダを選択すると、一枚目のカードをめくってその色を表示するサンプルが実行されました。
ヒントのスクリプトから要素の取得方法、カードのクリック(めくり)方法、 色の取得方法がわかります。
これらを参考に、一度全部のカードをめくって色を記憶し、その後同じ色のカードをめくっていくようにしました。
一発で最後まで解けたのでまあまあかと思っていたら、他の人はもっとスマートな回答してますね…反省
たしかに3回もループ回しちゃってるしムダだったな。


なお、manifest.json はノータッチです。

var elements = document.getElementsByClassName("card");
if (elements == null) {
  alert('Card element is not found. Check element id.');
} else {
  var res;
  var element;

  //クリックイベント作成
  var myevent = document.createEvent('MouseEvents');
  myevent.initEvent('click', false, true);

  var cardlist = [];
  //各Cardの背景色取得
  for( var j=0; j<elements.length; j++ ) {
    //res += elements.item(j).nodeName + ":" + elements.item(j).className + ":" + elements.item(j).id + "\n";
    element = elements.item(j);
    element.dispatchEvent(myevent);
    var cardinfo = {};
    cardinfo["color"] = element.style.backgroundColor;
    cardinfo["opened"] = false;
    cardlist[j] = cardinfo;
  }
  //Open済かどうかチェック
  for( var j=0; j<elements.length; j++ ) {
    element = elements.item(j);
    var style = element.style.backgroundColor;
    if(style == cardlist[j]["color"]) {
      cardlist[j]["opened"] = true;
    }
  }

  //色が同じCardを開けていく
  for( var j=0; j<elements.length; j++ ) {
    if(cardlist[j]["opened"] == false) {
      var temp = cardlist[j]["color"];
      for( var k=j; k<elements.length; k++ ) {
        if(cardlist[k]["color"] == temp) {
          elements.item(j).dispatchEvent(myevent);
          elements.item(k).dispatchEvent(myevent);
          cardlist[j]["opened"] = true;
          cardlist[k]["opened"] = true;
        }
      }
    }
  }
}


参考文献
特になし

Google Apps Script

次にチャレンジしたのがGoogle Apps Script。
javascriptで組めるというのと、VBAみたいなもんだろう、というのが選んだ理由です。


jsonの取得(HTTP通信)、セルへの書き込み方法、書式の設定方法が分かれば特に問題ありませんでした。
なお、もともとあったシートは手動で削除しました^_^;


書式については、手動で書式設定したセルに対して getNumberFormat して得た値を設定するようにしました。


他の人のコード見てて気づいたけど、jsonをパースするAPIGoogle Apps Script側で用意されていたようです。
WebAPIとの連携が意識されているんでしょうね。
http://www5d.biglobe.ne.jp/~pog/utilities_services/class_utilities.html#jsonParse

function myFunction() {

  //データ取得
  var response = UrlFetchApp.fetch("http://gdd-2011-quiz-japan.appspot.com/apps_script/data?param=-4693790266312240589");
  //Browser.msgBox(response.getContentText());
  if(response == null) {
    return;
  }

  //JSONデータを配列に変換
  var jsondata = eval("("+response.getContentText()+")");
  if(jsondata == null) {
    return;
  }

  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet = SpreadsheetApp.getActiveSheet();
  //Browser.msgBox(sheet.getRange(2, 3).getNumberFormats());

  for( var i=0; i<jsondata.length; i++ ) {
  //for( var i=0; i<1; i++ ) {
    //都市名でシート作成し、作成したシートを取得
    ss.insertSheet(jsondata[i].city_name)
    sheet = ss.getSheetByName(jsondata[i].city_name);
    for( var j=0; j<jsondata[i].data.length; j++ ) {
    //for( var j=0; j<1; j++ ) {
      sheet.getRange(j+1, 1).setValue(jsondata[i].data[j].capacity);
      sheet.getRange(j+1, 2).setValue(jsondata[i].data[j].usage);
      //C列には計算式を記載
      sheet.getRange(j+1, 3).setValue("=" + sheet.getRange(j+1, 2).getValue() + "/" + sheet.getRange(j+1, 1).getValue());
      //sheet.getRange(j+1, 3).setNumberFormat("0.00%");
    }
    //サンプルを見ると、データは数値だったり式であったりしたが、
    //表示形式は"0.00%"に統一されているようなのでここで設定
    sheet.getRange("C1:C"+j).setNumberFormat("0.00%");
  }
}


○参考ページ:
JSONってなにもの? | Think IT(シンクイット)jsonの勉強
http://www5d.biglobe.ne.jp/~pog/index.htmlAPIリファレンスとして
→特にSpreadsheetrange
初心者のためのGoogle Apps Scriptプログラミング入門:サンプル


Android

分野別問題2つ解いたし次はチャレンジクイズだ!とも思ったんですが、他の分野別クイズが気になって集中できないので、先に分野別問題を片付けることにしました。


Androidは触ったことあるんですが、正直サンプル程度で本問題の回答はさっぱりです。


まずは、エミュレータGoogleが用意したアプリをインストールするところから。
エミュレータ起動した状態で下記コマンド実行します。

adb install "apkのパス"


無事インストールできたので、エミュレータ上でアプリ起動しメールアドレス等を登録。


あとはこのアプリ(サービス)にアクセスしてコードを取得するのですが、どうにもさっぱり…
そこで日経ソフトウェア2010年7,8月号でAndroidのサービスをざっくり勉強したあと、「他の人が作ったサービスを使うための手法」を検索しました。


結果的に、参考ページにあるような方法でAIDLを組み込んでやるとうまくいきました。
本問題のポイントは「AIDLを読み込ませてinterfaceを自動生成する」というところだと思います。
一応、interface自動生成後のソース晒しときます。

package com.kokemono.android.gdd2011;

import com.google.android.apps.gddquiz.IQuizService;

import android.app.Activity;
import android.os.Bundle;
import android.os.IBinder;
import android.os.RemoteException;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.content.ComponentName;
import android.content.Context;
import android.content.Intent;
import android.content.ServiceConnection;



public class MainActivity extends Activity {

     private EditText mEditText;
     private Button mButton;

     private IQuizService mQuizService = null;

     private ServiceConnection svcConn = new ServiceConnection() {

          @Override
          public void onServiceDisconnected(ComponentName name) {
               mQuizService = null;
          }

          @Override
          public void onServiceConnected(ComponentName name, IBinder service) {
               mQuizService = IQuizService.Stub.asInterface(service);
          }
     };

    /** Called when the activity is first created. */
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);
        mEditText = (EditText)findViewById(R.id.editText1);
        mButton = (Button)findViewById(R.id.button1);

        Intent intent = new Intent(IQuizService.class.getName());
        bindService(intent, svcConn, Context.BIND_AUTO_CREATE);

        mButton.setOnClickListener(new View.OnClickListener() {

               @Override
               public void onClick(View v) {
                    // TODO 自動生成されたメソッド・スタブ
                  try {
                         String devcode = mQuizService.getCode();
                         mEditText.setText(devcode);
                    } catch (RemoteException e) {
                         // TODO 自動生成された catch ブロック
                         e.printStackTrace();
                    }

               }
          });


   }
    public void onDestroy() {
        super.onDestroy();

        unbindService(svcConn);
    }

}

○参考ページ:
AndroidのRemote Serviceについて(+作り方) - adsaria mood
他のアプリ(パッケージ)からもアクセスできるServiceを作る - terurouメモ

Go

まずはWindowsに開発環境を整えることからスタートです。
Windows環境なのでwingo使用。VmWare上のCentOSでインストールしようとしたらうまくいきませんでした…


HelloWorldが表示できることを確認したあと、いよいよコード着手です。
今回も日経ソフトウェアの過去記事が参考になりました。
日経ソフトウェア 2010年11月号に、「sliceを駆使して画像処理プログラムを作ろう」というど真ん中な連載記事が。
これ見た瞬間に「楽勝!」と思ったんですが、使えるプロパティが記事と違うところがありすんなりとは行きませんでした。


まあちょっと調べながらなんとかクリアです。


意外と困ったのが、importしたimage/pngパッケージを使いたくても、仮引数ですでに「png」が使われていると言う点。
きっと出題者もあえてこのような名前にしているのでしょう。
自分の場合下記ページを参考に別の名前(限定付き識別子?エイリアス?)をつけてやることで解決しています。


Go言語仕様翻訳(part12) - golang.jp


もちろん、関数の仮引数名を変更しても正解のようです。


後から見直して大変カッコ悪いんですが、色の組み合わせをキーにして連想配列を作る際、「0埋めして文字列作らないと一意にならない」と思い込みから「よく分からんから10未満100未満でやっちゃえ」としてしまった点。
他の方の回答見た時、RGB各値の間に":"挟んだりしてるのをみて「そりゃそうか」と思わず納得してしまいました。


最終的な数も連想配列のlenではなくカウントで取得してるのがまたカッコ悪い。

package main

import (
     "fmt"
     "io"
     "strings"
     "image"
     p "image/png"
     "strconv"
     /* add more */
)


/* ----- これらの関数は提出時に自動挿入されます。----- */
func main() {
     png := GetPngBinary()
     cnt := CountColor(png)
     fmt.Println(cnt)
}

func GetPngBinary() io.Reader {
     // img_strの中身は提出するたびに変化します。
     img_str := "\x89PNG\r\n\x1a\n\x00\x00\x00\rIHDR\x00\x00\x00\x18\x00\x00\x00\x08\x08\x06\x00\x00\x00\xe3\xa1?c\x00\x00\x02\xeeiCCPICC Profile\x00\x00x\x01\x85T\xcfk\x13A\x14\xfe6n\xa9\xd0\"\x08Zk\x0e\xb2x\x90\"IY\xabhE\xd46\xfd\x11bk\x0c\xdb\x1f\xb6E\x90d3I\xd6n6\xeb\xee&\xb5\xa5\x88\xe4\xe2\xd1*\xdeE\xed\xa1\x07\xff\x80\x1ez\xf0d/J\x85ZE(\xde\xab(b\xa1\x17-\xf1\xcdnL\xb6\xa5\xea\xc0\xce~\xf3\xde7\xef}ov\xdf\x00\rr\xd24\xf5\x80\x04\xe4\r\xc7R\xa2\x11il|Bj\xfc\x88\x00\x8e\xa2\tA4%U\xdb\xecN$\x06A\x83s\xf9{\xe7\xd8z\x0f\x81[V\xc3{\xfbw\xb2w\xad\x9a\xd2\xb6\x9a\x07\x84\xfd@\xe0G\x9a\xd9*\xb0\xef\x17q\nY\x12\x02\x88<\xdf\xa1)\xc7t\x08\xdf\xe3\xd8\xf2\xec\x8f9Nyx\xc1\xb5\x0f+=\xc4Y\"|@5-\xce\x7fM\xb8S\xcd%\xd3@\x83H8\x94\xf5qR>\x9c\xd7\x8b\x94\xd7\x1d\x07inf\xc6\xc8\x10\xbdO\x90\xa6\xbb\xcc\xee\xabb\xa1\x9cN\xf6\x0e\x90\xbd\x9d\xf4~N\xb3\xde>\xc2!\xc2\x0b\x19\xad?F\xb8\x8d\x9e\xf5\x8c\xd5?\xe2a\xe1\xa4\xe6\xc4\x86=\x1c\x185\xf4\xf8`\x15\xb7\x1a\xa9\xf85\xc2\x14_\x10M'\xa2Tq\xd9.\r\xf1\x98\xae\xfdV\xf2J\x82p\x908\xcada\x80sZHO\xd7Ln\xf8\xba\x87\x05}&\xd7\x13\xaf\xe2wVQ\xe1y\x8f\x13g\xde\xd4\xdd\xefE\xda\x02\xaf0\x0e\x1d\x0c\x1a\x0c\x9a\rHP\x10E\x04a\x98\xb0P@\x86<\x1a14\xb2r?#\xab\x06\x1b\x93{2u$j\xbbtbD\xb1A{6\xdc=\xb7Q\xa4\xdd<\xfe(\"q\x94C\xb5\x08\x92\xfcA\xfe*\xaf\xc9O\xe5y\xf9\xcb\\\xb0\xd8V\xf7\x94\xad\x9b\x9a\xba\xf2\xe0;\xc5\xe5\x99\xb9\x1a\x1e\xd7\xd3\xc8\xe3sM^|\x95\xd4v\x93WG\x96\xacyz\xbc\x9a\xec\x1a?\xecW\x971\xe6\x825\x8f\xc4s\xb0\xfb\xf1-_\x95\xcc\x97)\x8c\x14\xc5\xe3U\xf3\xeaK\x84uZ17\xdf\x9fl\x7f;=\xe2.\xcf.\xb5\xd6s\xad\x89\x8b7V\x9b\x97g\xfdjH\xfb\xee\xaa\xbc\x93\xe6U\xf9O^\xf5\xf1\xfcg\xcd\xc4c\xe2)1&v\x8a\xe7!\x89\x97\xc5.\xf1\x92\xd8K\xab\x0b\xe2`m\xc7\x08\x9d\x95\x86)\xd2m\x91\xfa$\xd5``\x9a\xbc\xf5/]?[x\xbdF\x7f\x0c\xf5Q\x94\x19\xcc\xd2T\x89\xf7\x7f\xc2*d4\x9d\xb9\x0eo\xfa\x8f\xdb\xc7\xfc\x17\xe4\xf7\x8a\xe7\x9f(\x02/l\xe0\xc8\x99\xbamSq\xef\x10\xa1e\xa5ns\xae\x02\x17\xbf\xd1}\xf0\xb6nk\xa3~8\xfc\x04X<\xab\x16\xadR5\x9f \xbc\x01\x1cv\x87z\x1e\xe8)\x98\xd3\x96\x96\xcd9R\x87,\x9f\x93\xba\xe9\xcabR\xccP\xdbCRR\xd7%\xd7eK\x16\xb3\x99Ub\xe9v\xd8\x99\xd3\x1dn\x1c\xa19B\xf7\xc4\xa7Je\x93\xfa\xaf\xf1\x11\xb0\xfd\xb0R\xf9\xf9\xacR\xd9~N\x1a\xd6\x81\x97\xfao\xc0\xbc\xfdE\xc0x\x8b\x89\x00\x00\x00\x97IDAT(\x15\x9d\x92\x81\x0e\x80 \x08D\xa5\xf9m\xf5Y\xad\xcf\xaa\x9f#nz$\xba\xb9\xca\xad\x85\xc1\xbd\x03S\xd4\x96H\xf2\xa5\xea\xe1\xeb@\x8e\x02\xd0}\x14/\x80\x03\xca\xa75{\xeb0\x80\x01\xa9\xa0\xdcC|\x02:\xf1\xc3U\xc7\\K\x97}\xda9HPcq0pQ\x8aE\xe94y\x05'3\x92M[\x86\xc7\xc1\xa4n\x82\x01\x8ci\xe2\xc5\x7f\x02N`\xda\xdcCK\xaeqbqsD\xbd\x86=\xe0g\xdb\x9dy\xba\xb4Xp\x8bX\xf0\xe7\x8d\x89g\x84pD_\x0cx\x9438x7\xa4yC\r7\x04z\xae\x00\x00\x00\x00IEND\xaeB`\x82"
     return strings.NewReader(img_str)
}
/* ----- これらの関数は提出時に自動挿入されます。----- */


func CountColor(png io.Reader) int {
     var pic image.Image
     var color image.Color
    
     pic,e := p.Decode(png)
     if e != nil {
          fmt.Printf("Error %v\n", e)
          return 0
     }
    
     cnt := 0
    
     colormap := make(map[string] int)
     for y:= 0; y < pic.Bounds().Size().Y; y++ {
          for x:= 0; x < pic.Bounds().Size().X; x++ {
               color = pic.At(x,y)
               r,g,b,_ := color.RGBA()
               key := ""
               if uint8(r) < 10 {
                    key += "00"+ strconv.Uitoa(uint(uint8(r)))
               } else if uint8(r) < 100 {
                    key += "0"+ strconv.Uitoa(uint(uint8(r)))
               } else {
                    key += strconv.Uitoa(uint(uint8(r)))
               }
              
               if uint8(g) < 10 {
                    key += "00"+ strconv.Uitoa(uint(uint8(g)))
               } else if uint8(g) < 100 {
                    key += "0"+ strconv.Uitoa(uint(uint8(g)))
               } else {
                    key += strconv.Uitoa(uint(uint8(g)))
               }

               if uint8(b) < 10 {
                    key += "00"+ strconv.Uitoa(uint(uint8(b)))
               } else if uint8(b) < 100 {
                    key += "0"+ strconv.Uitoa(uint(uint8(b)))
               } else {
                    key += strconv.Uitoa(uint(uint8(b)))
               }
              
               if val, exist := colormap[key]; exist {
                    colormap[key] = val + 1
               } else {
                    colormap[key] = 1
                    cnt ++
               }
              
          }
     }
    
     return cnt
}


○参考ページ
WindowsでGo言語::インストールWindowsでGoコンパイル環境を整えるのに
Goプログラミング言語のチュートリアル - golang.jp:日本語チュートリアル。基本が詰まっています。
image/png パッケージ - golang.jp:image/pngパッケージのリファレンス。あとはimageとstrconvについて参照


一人ゲーム

分野別クイズではこれが一番苦労しました。


一般的なアルゴリズム詳しくない、「『二分木探索?』『幅優先探索?』なにそれおいしいの?」という状態からのスタートです。
プログラム歴=社会人歴で、これまで目の前の仕事片付けるのに精一杯だったことが悔やまれます。


言語は、最近勉強中のPythonを使うことにしました。
Python2.5、Python2.7での動作を確認しています。


とりあえず、適当な公式を考えだしてチャレンジするものの、さっぱり正解しません。
ちゃんと経路探索の手法を勉強してみることにしましょう。


その際に 広井 誠 氏のサイト、特にM.Hiroi's Home Page / Puzzle De ProgrammingAlgorithms with Pythonが大変参考になりました。
これはチャレンジクイズの「スライドパズル」でも同様で、こちらの解説がなければ100点止まりだったと思います。
この場を借りてお礼申し上げます。


閑話休題
今回は、この問題を「幅優先探索」で解いてみることにしました。
簡易的なQueueとしてリストを使用しています。


・処理の流れ
Queueから取り出す→すべて5の倍数であれば終了→そうでなければ取り出した値について「すべて2で割ったもの」と「5の倍数削除したもの」を追加しQueueに追加

# coding: utf-8
import os.path

#全て5の倍数、もしくは0であれば0を返す。そうでないなら-1
def isAllMultipleOf5(array):
     for x in array:
          if x % 5 != 0:
               return -1
     return 0

#与えられた数を半分にしていき、5の倍数がでるまでの回数を返す
def countDivToMultipleOf5(num):
     i = 0
     while num % 5 != 0:
          num = num /2
          i += 1
     return i

#与えられた数値を指定の回数だけ半分にする
def divideNum(num, count):
     for i in xrange(count):
          num = num /2
     return num

#5を含んでいれば0を返す。そうでないなら-1
def isContainMultipleOf5(array):
     for x in array:
          if x % 5 == 0:
               return 0
     return -1

#5 の倍数 (0 を含む) を全て取り除く
def clearMultipleOf5(array):
     i=0
     while i < len(array):
          if array[i] % 5 == 0:
               array.pop(i)
               i -= 1
          i += 1
     return array

#全ての数を半分にする(端数は切り捨て)
def divAllNum(array):
     return map((lambda x:x/2),array)
    
def solver(array):
     #文字列から数値に変換
     arrayint = map(int, array.split(' '))

     #メイン処理
     #とれる手段は以下の2つ
     # 1. 全ての数を半分にする(端数は切り捨て)
     # 2. 5 の倍数 (0 を含む) を全て取り除く
     cnt = 0
     q = [arrayint]
     while len(q) > 0:
          flg = False
          #dequeu
          arraypop = q.pop(0)
          arraylast = []          #探索中の最新手
          if isinstance(arraypop, list) == True:
               if isinstance(arraypop[0], list) == True:
                    arraylast = arraypop[len(arraypop)-1]     #二次元配列状態[[10,22,30],[5,11,15],[]]
               else:
                    flg = True
                    arraylast = arraypop[:]                         #数字の配列=一手目
          else:
               print "error"
         
          if isAllMultipleOf5(arraylast) == 0:
               #全ての数が5の倍数である場合
               if flg == True:
                    #一手目
                    cnt = 1
               else:
                    cnt = len(arraypop)
               return str(cnt)
          else:
               if flg == True:     #数字の配列
                    #queueから取得した状態に「全ての数を2で割った」手を追加する
                    div_array = []     #全てを2で割った配列
                    div_array.append(arraypop)
                    div_array.append(divAllNum(arraylast))
                    q.append(div_array)
                   
                    #queueから取得した状態に「5の倍数を削除した」手を追加する
                    if isContainMultipleOf5(arraylast) == 0:
                         #5の倍数を含む場合のみ
                         del_array = []     #5の倍数を除去した配列
                         del_array.append(arraypop)
                         new_array = arraylast[:]
                         del_array.append(clearMultipleOf5(new_array))
                         q.append(del_array)
               else:               #配列の配列
                    #queueから取得した状態に「全ての数を2で割った」手を追加する
                    div_array = arraypop[:]
                    div_array.append(divAllNum(arraylast))
                    q.append(div_array)
                   
                    #queueから取得した状態に「5の倍数を削除した」手を追加する
                    if isContainMultipleOf5(arraylast) == 0:
                         #5の倍数を含む場合のみ
                         del_array = arraypop[:]
                         new_array = arraylast[:]
                         del_array.append(clearMultipleOf5(new_array))
                         q.append(del_array)

#メイン処理

#入力データ取得
inputfile = "input.data"
if os.path.exists(inputfile):
     fi = open(inputfile, 'r')
else:
     exit()

#出力ファイル作成
outputfile = "answer.data"
fo =  open(outputfile, 'w')


#テストケース数
T = fi.readline()
i = 0
while i < int(T):
     N = fi.readline()
     a = fi.readline()
     print str(i+1) + u"問目"
     fo.write(solver(a) + '\n')
     i += 1

fi.close()
fo.close()