2011年9月アーカイブ

今年(2011年)も恒例の Google Developer Day 2011 Japan DevQuiz にチャレンジしました。

 

結果

スライドパズル以外は全問解けましたが、肝心のスライドパズルが時間切れという中途半端な結果。。。

gddj2011_adakoda_result.png

 

回答編 

以下、主なものだけですが、回答の抜粋となります。

 

【Go!】

与えられたランダムなPNG画像が使用している色の数を返すGo言語関数を回答する」問題。

 →  単純に全ピクセルを捜査し、対象のピクセルのRGB値をキーとしてmapに登録することでカウントしました。

 

ハマってしまったのは、PNGのデコードの呼び出し" png.Decode() "で名前が衝突してしまうところ。。。

とりあえず、 import 時に名前空間のエイリアス?をつけられたので、それで回避しました。

package main

import (
    "fmt"
    "io"
    "strings"
    PNG "image/png"
)

func CountColor(png io.Reader) int {
    countmap := make(map[uint32] int)
    img, err := PNG.Decode(png)
    if err == nil {
        bounds := img.Bounds()
        for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
            for x := bounds.Min.X; x < bounds.Max.X; x++ {
                r, g, b, a := img.At(x, y).RGBA()
                countmap[(((r >> 8) << 24) + ((g >> 8) << 16) + ((b >> 8) << 8) + (a >> 8))] = 1
            }
        }
    }
    return len(countmap)
}

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)
}

 

【Google Apps Script】

与えられた JSON ファイルを決められた計算式で計算し、Google Spreadsheets を作成する」問題。

 → Google ドキュメントの「スクリプトエディタ」ツールでスクリプトを作成し、ワークシートを自動作成しました。

 

API リファレンスが見つけにくく、エディタが辛かった印象でしたが、

Excel マクロのように、ルーチンワークを自動化できるので、地味ではあるが、簡単に使えてパワフルと!いう印象でした。

function myFunction() {
  var spreadSheet = SpreadsheetApp.create("gddj2011-answer");
  var jsonString = "[{\"city_name\": \"Amihsukot\", \"data\": [{\"usage\": 363, \"capacity\": 629}, {\"usage\": 501, \"capacity\": 586}, {\"usage\": 331, \"capacity\": 867}, {\"usage\": 670, \"capacity\": 1349}, {\"usage\": 1367, \"capacity\": 1978}, {\"usage\": 1772, \"capacity\": 1842}, {\"usage\": 405, \"capacity\": 523}, {\"usage\": 670, \"capacity\": 777}, {\"usage\": 1005, \"capacity\": 1419}, {\"usage\": 593, \"capacity\": 1281}, {\"usage\": 1190, \"capacity\": 1867}, {\"usage\": 698, \"capacity\": 935}, {\"usage\": 296, \"capacity\": 753}, {\"usage\": 873, \"capacity\": 1063}, {\"usage\": 1566, \"capacity\": 1750}, {\"usage\": 563, \"capacity\": 828}, {\"usage\": 584, \"capacity\": 656}, {\"usage\": 746, \"capacity\": 892}, {\"usage\": 489, \"capacity\": 1609}, {\"usage\": 607, \"capacity\": 937}, {\"usage\": 1288, \"capacity\": 1672}, {\"usage\": 1040, \"capacity\": 1480}, {\"usage\": 731, \"capacity\": 1222}, {\"usage\": 643, \"capacity\": 700}, {\"usage\": 1438, \"capacity\": 1727}, {\"usage\": 261, \"capacity\": 862}, {\"usage\": 364, \"capacity\": 672}, {\"usage\": 1093, \"capacity\": 1347}, {\"usage\": 353, \"capacity\": 1114}, {\"usage\": 600, \"capacity\": 1091}, {\"usage\": 821, \"capacity\": 888}, {\"usage\": 1210, \"capacity\": 1602}, {\"usage\": 940, \"capacity\": 953}, {\"usage\": 1015, \"capacity\": 1334}, {\"usage\": 1438, \"capacity\": 1837}, {\"usage\": 1375, \"capacity\": 1988}, {\"usage\": 744, \"capacity\": 1558}, {\"usage\": 1346, \"capacity\": 1868}, {\"usage\": 911, \"capacity\": 1205}, {\"usage\": 984, \"capacity\": 1744}]}, {\"city_name\": \"Amihsorih\", \"data\": [{\"usage\": 380, \"capacity\": 653}, {\"usage\": 1134, \"capacity\": 1506}, {\"usage\": 570, \"capacity\": 743}, {\"usage\": 912, \"capacity\": 1421}, {\"usage\": 374, \"capacity\": 1052}, {\"usage\": 909, \"capacity\": 1414}, {\"usage\": 365, \"capacity\": 589}, {\"usage\": 527, \"capacity\": 1051}, {\"usage\": 311, \"capacity\": 647}, {\"usage\": 1009, \"capacity\": 1178}, {\"usage\": 770, \"capacity\": 945}, {\"usage\": 479, \"capacity\": 839}, {\"usage\": 666, \"capacity\": 1711}, {\"usage\": 790, \"capacity\": 1049}, {\"usage\": 1222, \"capacity\": 1479}, {\"usage\": 669, \"capacity\": 1356}, {\"usage\": 246, \"capacity\": 616}, {\"usage\": 821, \"capacity\": 917}, {\"usage\": 1488, \"capacity\": 1799}, {\"usage\": 296, \"capacity\": 634}, {\"usage\": 513, \"capacity\": 707}, {\"usage\": 723, \"capacity\": 964}, {\"usage\": 710, \"capacity\": 1199}, {\"usage\": 1138, \"capacity\": 1723}, {\"usage\": 577, \"capacity\": 731}, {\"usage\": 646, \"capacity\": 1045}, {\"usage\": 977, \"capacity\": 1326}, {\"usage\": 1268, \"capacity\": 1464}, {\"usage\": 1671, \"capacity\": 1920}, {\"usage\": 840, \"capacity\": 878}, {\"usage\": 1273, \"capacity\": 1424}, {\"usage\": 1552, \"capacity\": 1994}, {\"usage\": 501, \"capacity\": 1424}, {\"usage\": 1151, \"capacity\": 1423}, {\"usage\": 560, \"capacity\": 882}, {\"usage\": 1435, \"capacity\": 1602}, {\"usage\": 639, \"capacity\": 989}, {\"usage\": 492, \"capacity\": 1211}, {\"usage\": 363, \"capacity\": 987}, {\"usage\": 364, \"capacity\": 1085}]}, {\"city_name\": \"Ihsabeam\", \"data\": [{\"usage\": 1093, \"capacity\": 1135}, {\"usage\": 1038, \"capacity\": 1262}, {\"usage\": 251, \"capacity\": 708}, {\"usage\": 967, \"capacity\": 1216}, {\"usage\": 539, \"capacity\": 572}, {\"usage\": 822, \"capacity\": 944}, {\"usage\": 578, \"capacity\": 996}, {\"usage\": 323, \"capacity\": 513}, {\"usage\": 515, \"capacity\": 562}, {\"usage\": 969, \"capacity\": 979}, {\"usage\": 603, \"capacity\": 1721}, {\"usage\": 581, \"capacity\": 650}, {\"usage\": 354, \"capacity\": 1073}, {\"usage\": 1257, \"capacity\": 1665}, {\"usage\": 1437, \"capacity\": 1836}, {\"usage\": 1448, \"capacity\": 1510}, {\"usage\": 1069, \"capacity\": 1530}, {\"usage\": 645, \"capacity\": 945}, {\"usage\": 1198, \"capacity\": 1245}, {\"usage\": 652, \"capacity\": 740}, {\"usage\": 858, \"capacity\": 966}, {\"usage\": 495, \"capacity\": 1064}, {\"usage\": 1339, \"capacity\": 1703}, {\"usage\": 472, \"capacity\": 1290}, {\"usage\": 1200, \"capacity\": 1645}, {\"usage\": 1153, \"capacity\": 1175}, {\"usage\": 457, \"capacity\": 754}, {\"usage\": 1455, \"capacity\": 1489}, {\"usage\": 1013, \"capacity\": 1236}, {\"usage\": 598, \"capacity\": 1585}, {\"usage\": 569, \"capacity\": 1447}, {\"usage\": 881, \"capacity\": 1173}, {\"usage\": 470, \"capacity\": 688}, {\"usage\": 1492, \"capacity\": 1778}, {\"usage\": 891, \"capacity\": 1972}, {\"usage\": 826, \"capacity\": 1978}, {\"usage\": 810, \"capacity\": 1616}, {\"usage\": 1179, \"capacity\": 1289}, {\"usage\": 731, \"capacity\": 844}, {\"usage\": 1242, \"capacity\": 1726}]}, {\"city_name\": \"Irottot\", \"data\": [{\"usage\": 407, \"capacity\": 1204}, {\"usage\": 1348, \"capacity\": 1841}, {\"usage\": 877, \"capacity\": 1935}, {\"usage\": 751, \"capacity\": 1255}, {\"usage\": 629, \"capacity\": 659}, {\"usage\": 627, \"capacity\": 1842}, {\"usage\": 221, \"capacity\": 576}, {\"usage\": 1517, \"capacity\": 1536}, {\"usage\": 1268, \"capacity\": 1707}, {\"usage\": 287, \"capacity\": 584}, {\"usage\": 609, \"capacity\": 853}, {\"usage\": 755, \"capacity\": 1156}, {\"usage\": 1048, \"capacity\": 1317}, {\"usage\": 301, \"capacity\": 963}, {\"usage\": 700, \"capacity\": 834}, {\"usage\": 1383, \"capacity\": 1920}, {\"usage\": 1626, \"capacity\": 1718}, {\"usage\": 283, \"capacity\": 909}, {\"usage\": 1736, \"capacity\": 1829}, {\"usage\": 679, \"capacity\": 990}, {\"usage\": 528, \"capacity\": 1698}, {\"usage\": 601, \"capacity\": 1125}, {\"usage\": 198, \"capacity\": 647}, {\"usage\": 311, \"capacity\": 510}, {\"usage\": 399, \"capacity\": 695}, {\"usage\": 967, \"capacity\": 1136}, {\"usage\": 976, \"capacity\": 1529}, {\"usage\": 817, \"capacity\": 1424}, {\"usage\": 451, \"capacity\": 640}, {\"usage\": 953, \"capacity\": 980}, {\"usage\": 1048, \"capacity\": 1441}, {\"usage\": 484, \"capacity\": 1204}, {\"usage\": 1121, \"capacity\": 1375}, {\"usage\": 1603, \"capacity\": 1871}, {\"usage\": 1447, \"capacity\": 1633}, {\"usage\": 604, \"capacity\": 1258}, {\"usage\": 769, \"capacity\": 981}, {\"usage\": 630, \"capacity\": 1261}, {\"usage\": 1760, \"capacity\": 1914}, {\"usage\": 800, \"capacity\": 869}]}, {\"city_name\": \"Ikazayim\", \"data\": [{\"usage\": 500, \"capacity\": 1560}, {\"usage\": 963, \"capacity\": 1766}, {\"usage\": 364, \"capacity\": 1109}, {\"usage\": 1211, \"capacity\": 1696}, {\"usage\": 677, \"capacity\": 741}, {\"usage\": 1005, \"capacity\": 1823}, {\"usage\": 1049, \"capacity\": 1309}, {\"usage\": 1713, \"capacity\": 1998}, {\"usage\": 787, \"capacity\": 1982}, {\"usage\": 816, \"capacity\": 1170}, {\"usage\": 1147, \"capacity\": 1460}, {\"usage\": 1127, \"capacity\": 1545}, {\"usage\": 223, \"capacity\": 601}, {\"usage\": 419, \"capacity\": 1379}, {\"usage\": 323, \"capacity\": 610}, {\"usage\": 643, \"capacity\": 1673}, {\"usage\": 254, \"capacity\": 795}, {\"usage\": 535, \"capacity\": 1129}, {\"usage\": 540, \"capacity\": 901}, {\"usage\": 1458, \"capacity\": 1988}, {\"usage\": 1065, \"capacity\": 1627}, {\"usage\": 848, \"capacity\": 1712}, {\"usage\": 370, \"capacity\": 1093}, {\"usage\": 715, \"capacity\": 1021}, {\"usage\": 1798, \"capacity\": 1955}, {\"usage\": 594, \"capacity\": 1071}, {\"usage\": 644, \"capacity\": 827}, {\"usage\": 987, \"capacity\": 1193}, {\"usage\": 288, \"capacity\": 876}, {\"usage\": 1113, \"capacity\": 1738}, {\"usage\": 682, \"capacity\": 1772}, {\"usage\": 1705, \"capacity\": 1850}, {\"usage\": 466, \"capacity\": 1167}, {\"usage\": 1075, \"capacity\": 1592}, {\"usage\": 690, \"capacity\": 938}, {\"usage\": 892, \"capacity\": 1171}, {\"usage\": 858, \"capacity\": 1118}, {\"usage\": 1335, \"capacity\": 1930}, {\"usage\": 661, \"capacity\": 759}, {\"usage\": 1047, \"capacity\": 1613}]}, {\"city_name\": \"Onagan\", \"data\": [{\"usage\": 828, \"capacity\": 1831}, {\"usage\": 1584, \"capacity\": 1884}, {\"usage\": 924, \"capacity\": 1697}, {\"usage\": 555, \"capacity\": 974}, {\"usage\": 469, \"capacity\": 592}, {\"usage\": 245, \"capacity\": 568}, {\"usage\": 1239, \"capacity\": 1978}, {\"usage\": 604, \"capacity\": 1568}, {\"usage\": 913, \"capacity\": 927}, {\"usage\": 618, \"capacity\": 1727}, {\"usage\": 1111, \"capacity\": 1863}, {\"usage\": 1390, \"capacity\": 1577}, {\"usage\": 339, \"capacity\": 888}, {\"usage\": 557, \"capacity\": 645}, {\"usage\": 646, \"capacity\": 935}, {\"usage\": 1131, \"capacity\": 1155}, {\"usage\": 410, \"capacity\": 970}, {\"usage\": 1292, \"capacity\": 1883}, {\"usage\": 827, \"capacity\": 1161}, {\"usage\": 507, \"capacity\": 1446}, {\"usage\": 1290, \"capacity\": 1389}, {\"usage\": 620, \"capacity\": 1121}, {\"usage\": 519, \"capacity\": 1586}, {\"usage\": 1647, \"capacity\": 1805}, {\"usage\": 1023, \"capacity\": 1661}, {\"usage\": 331, \"capacity\": 960}, {\"usage\": 441, \"capacity\": 667}, {\"usage\": 1060, \"capacity\": 1948}, {\"usage\": 578, \"capacity\": 760}, {\"usage\": 583, \"capacity\": 1521}, {\"usage\": 273, \"capacity\": 503}, {\"usage\": 1020, \"capacity\": 1304}, {\"usage\": 1332, \"capacity\": 1612}, {\"usage\": 914, \"capacity\": 1521}, {\"usage\": 1335, \"capacity\": 1475}, {\"usage\": 918, \"capacity\": 1161}, {\"usage\": 468, \"capacity\": 926}, {\"usage\": 821, \"capacity\": 1009}, {\"usage\": 554, \"capacity\": 1789}, {\"usage\": 382, \"capacity\": 643}]}, {\"city_name\": \"Amayakaw\", \"data\": [{\"usage\": 817, \"capacity\": 881}, {\"usage\": 452, \"capacity\": 1203}, {\"usage\": 609, \"capacity\": 679}, {\"usage\": 1280, \"capacity\": 1321}, {\"usage\": 721, \"capacity\": 1514}, {\"usage\": 800, \"capacity\": 1601}, {\"usage\": 581, \"capacity\": 1274}, {\"usage\": 971, \"capacity\": 1208}, {\"usage\": 1438, \"capacity\": 1490}, {\"usage\": 1120, \"capacity\": 1379}, {\"usage\": 1054, \"capacity\": 1077}, {\"usage\": 620, \"capacity\": 1377}, {\"usage\": 914, \"capacity\": 1228}, {\"usage\": 982, \"capacity\": 1646}, {\"usage\": 596, \"capacity\": 1248}, {\"usage\": 428, \"capacity\": 772}, {\"usage\": 1510, \"capacity\": 1834}, {\"usage\": 783, \"capacity\": 1011}, {\"usage\": 996, \"capacity\": 1385}, {\"usage\": 808, \"capacity\": 1496}, {\"usage\": 1031, \"capacity\": 1284}, {\"usage\": 1293, \"capacity\": 1786}, {\"usage\": 1118, \"capacity\": 1593}, {\"usage\": 1310, \"capacity\": 1515}, {\"usage\": 589, \"capacity\": 1080}, {\"usage\": 940, \"capacity\": 1192}, {\"usage\": 1297, \"capacity\": 1654}, {\"usage\": 788, \"capacity\": 818}, {\"usage\": 1471, \"capacity\": 1776}, {\"usage\": 822, \"capacity\": 1435}, {\"usage\": 1696, \"capacity\": 1897}, {\"usage\": 1029, \"capacity\": 1809}, {\"usage\": 524, \"capacity\": 1725}, {\"usage\": 481, \"capacity\": 1273}, {\"usage\": 687, \"capacity\": 1028}, {\"usage\": 426, \"capacity\": 628}, {\"usage\": 697, \"capacity\": 715}, {\"usage\": 692, \"capacity\": 772}, {\"usage\": 480, \"capacity\": 564}, {\"usage\": 827, \"capacity\": 1631}]}, {\"city_name\": \"Oykot\", \"data\": [{\"usage\": 944, \"capacity\": 1097}, {\"usage\": 678, \"capacity\": 1940}, {\"usage\": 784, \"capacity\": 963}, {\"usage\": 1109, \"capacity\": 1245}, {\"usage\": 587, \"capacity\": 1825}, {\"usage\": 382, \"capacity\": 1229}, {\"usage\": 933, \"capacity\": 1091}, {\"usage\": 307, \"capacity\": 529}, {\"usage\": 309, \"capacity\": 857}, {\"usage\": 1117, \"capacity\": 1299}, {\"usage\": 676, \"capacity\": 1457}, {\"usage\": 257, \"capacity\": 650}, {\"usage\": 1473, \"capacity\": 1637}, {\"usage\": 592, \"capacity\": 730}, {\"usage\": 748, \"capacity\": 1513}, {\"usage\": 975, \"capacity\": 1056}, {\"usage\": 590, \"capacity\": 1230}, {\"usage\": 1410, \"capacity\": 1489}, {\"usage\": 1170, \"capacity\": 1564}, {\"usage\": 949, \"capacity\": 993}, {\"usage\": 1929, \"capacity\": 1989}, {\"usage\": 276, \"capacity\": 724}, {\"usage\": 422, \"capacity\": 990}, {\"usage\": 986, \"capacity\": 1085}, {\"usage\": 998, \"capacity\": 1525}, {\"usage\": 1120, \"capacity\": 1978}, {\"usage\": 857, \"capacity\": 1023}, {\"usage\": 713, \"capacity\": 743}, {\"usage\": 609, \"capacity\": 1636}, {\"usage\": 603, \"capacity\": 1598}, {\"usage\": 748, \"capacity\": 1752}, {\"usage\": 672, \"capacity\": 1219}, {\"usage\": 227, \"capacity\": 718}, {\"usage\": 315, \"capacity\": 901}, {\"usage\": 795, \"capacity\": 1564}, {\"usage\": 603, \"capacity\": 636}, {\"usage\": 235, \"capacity\": 569}, {\"usage\": 747, \"capacity\": 1693}, {\"usage\": 451, \"capacity\": 831}, {\"usage\": 743, \"capacity\": 1838}]}, {\"city_name\": \"Usto\", \"data\": [{\"usage\": 594, \"capacity\": 1915}, {\"usage\": 864, \"capacity\": 1126}, {\"usage\": 1337, \"capacity\": 1884}, {\"usage\": 462, \"capacity\": 835}, {\"usage\": 1414, \"capacity\": 1569}, {\"usage\": 1025, \"capacity\": 1629}, {\"usage\": 664, \"capacity\": 1447}, {\"usage\": 441, \"capacity\": 601}, {\"usage\": 740, \"capacity\": 1039}, {\"usage\": 611, \"capacity\": 1764}, {\"usage\": 452, \"capacity\": 570}, {\"usage\": 491, \"capacity\": 835}, {\"usage\": 1033, \"capacity\": 1302}, {\"usage\": 980, \"capacity\": 991}, {\"usage\": 274, \"capacity\": 647}, {\"usage\": 962, \"capacity\": 1924}, {\"usage\": 667, \"capacity\": 1317}, {\"usage\": 1161, \"capacity\": 1344}, {\"usage\": 770, \"capacity\": 973}, {\"usage\": 390, \"capacity\": 1146}, {\"usage\": 669, \"capacity\": 678}, {\"usage\": 902, \"capacity\": 1802}, {\"usage\": 700, \"capacity\": 762}, {\"usage\": 688, \"capacity\": 1478}, {\"usage\": 845, \"capacity\": 1704}, {\"usage\": 1643, \"capacity\": 1815}, {\"usage\": 1171, \"capacity\": 1555}, {\"usage\": 592, \"capacity\": 1461}, {\"usage\": 486, \"capacity\": 1080}, {\"usage\": 953, \"capacity\": 1362}, {\"usage\": 1095, \"capacity\": 1804}, {\"usage\": 785, \"capacity\": 1956}, {\"usage\": 153, \"capacity\": 506}, {\"usage\": 1375, \"capacity\": 1718}, {\"usage\": 283, \"capacity\": 887}, {\"usage\": 426, \"capacity\": 1133}, {\"usage\": 442, \"capacity\": 810}, {\"usage\": 538, \"capacity\": 668}, {\"usage\": 623, \"capacity\": 747}, {\"usage\": 319, \"capacity\": 509}]}, {\"city_name\": \"Otomamuk\", \"data\": [{\"usage\": 796, \"capacity\": 1532}, {\"usage\": 701, \"capacity\": 1088}, {\"usage\": 545, \"capacity\": 1398}, {\"usage\": 359, \"capacity\": 738}, {\"usage\": 507, \"capacity\": 583}, {\"usage\": 1025, \"capacity\": 1677}, {\"usage\": 1473, \"capacity\": 1578}, {\"usage\": 1031, \"capacity\": 1751}, {\"usage\": 1621, \"capacity\": 1877}, {\"usage\": 274, \"capacity\": 552}, {\"usage\": 1376, \"capacity\": 1599}, {\"usage\": 324, \"capacity\": 510}, {\"usage\": 243, \"capacity\": 712}, {\"usage\": 362, \"capacity\": 872}, {\"usage\": 1245, \"capacity\": 1757}, {\"usage\": 516, \"capacity\": 1316}, {\"usage\": 581, \"capacity\": 1868}, {\"usage\": 983, \"capacity\": 1871}, {\"usage\": 411, \"capacity\": 574}, {\"usage\": 275, \"capacity\": 835}, {\"usage\": 1284, \"capacity\": 1761}, {\"usage\": 483, \"capacity\": 1195}, {\"usage\": 846, \"capacity\": 977}, {\"usage\": 445, \"capacity\": 869}, {\"usage\": 1301, \"capacity\": 1352}, {\"usage\": 393, \"capacity\": 980}, {\"usage\": 1114, \"capacity\": 1691}, {\"usage\": 362, \"capacity\": 1085}, {\"usage\": 983, \"capacity\": 1021}, {\"usage\": 390, \"capacity\": 1221}, {\"usage\": 944, \"capacity\": 1158}, {\"usage\": 467, \"capacity\": 1181}, {\"usage\": 1471, \"capacity\": 1735}, {\"usage\": 1407, \"capacity\": 1427}, {\"usage\": 595, \"capacity\": 971}, {\"usage\": 305, \"capacity\": 606}, {\"usage\": 608, \"capacity\": 753}, {\"usage\": 702, \"capacity\": 1746}, {\"usage\": 982, \"capacity\": 1850}, {\"usage\": 1319, \"capacity\": 1627}]}, {\"city_name\": \"Atagiin\", \"data\": [{\"usage\": 956, \"capacity\": 1165}, {\"usage\": 637, \"capacity\": 1448}, {\"usage\": 1090, \"capacity\": 1456}, {\"usage\": 1189, \"capacity\": 1789}, {\"usage\": 560, \"capacity\": 1015}, {\"usage\": 786, \"capacity\": 1885}, {\"usage\": 312, \"capacity\": 767}, {\"usage\": 1178, \"capacity\": 1998}, {\"usage\": 648, \"capacity\": 1613}, {\"usage\": 1562, \"capacity\": 1800}, {\"usage\": 509, \"capacity\": 1635}, {\"usage\": 1684, \"capacity\": 1838}, {\"usage\": 1296, \"capacity\": 1527}, {\"usage\": 640, \"capacity\": 709}, {\"usage\": 920, \"capacity\": 1080}, {\"usage\": 728, \"capacity\": 1392}, {\"usage\": 1404, \"capacity\": 1542}, {\"usage\": 546, \"capacity\": 1077}, {\"usage\": 436, \"capacity\": 726}, {\"usage\": 1009, \"capacity\": 1941}, {\"usage\": 329, \"capacity\": 692}, {\"usage\": 1071, \"capacity\": 1217}, {\"usage\": 323, \"capacity\": 633}, {\"usage\": 866, \"capacity\": 1675}, {\"usage\": 241, \"capacity\": 770}, {\"usage\": 1081, \"capacity\": 1345}, {\"usage\": 508, \"capacity\": 1546}, {\"usage\": 887, \"capacity\": 991}, {\"usage\": 724, \"capacity\": 843}, {\"usage\": 1433, \"capacity\": 1683}, {\"usage\": 306, \"capacity\": 888}, {\"usage\": 608, \"capacity\": 1926}, {\"usage\": 1406, \"capacity\": 1673}, {\"usage\": 752, \"capacity\": 1873}, {\"usage\": 525, \"capacity\": 1736}, {\"usage\": 1462, \"capacity\": 1773}, {\"usage\": 332, \"capacity\": 743}, {\"usage\": 764, \"capacity\": 1050}, {\"usage\": 1095, \"capacity\": 1611}, {\"usage\": 1116, \"capacity\": 1188}]}, {\"city_name\": \"Abihc\", \"data\": [{\"usage\": 505, \"capacity\": 514}, {\"usage\": 596, \"capacity\": 1746}, {\"usage\": 422, \"capacity\": 1051}, {\"usage\": 549, \"capacity\": 1567}, {\"usage\": 1925, \"capacity\": 1994}, {\"usage\": 811, \"capacity\": 1608}, {\"usage\": 1216, \"capacity\": 1298}, {\"usage\": 1124, \"capacity\": 1244}, {\"usage\": 1424, \"capacity\": 1500}, {\"usage\": 725, \"capacity\": 901}, {\"usage\": 1773, \"capacity\": 1998}, {\"usage\": 1344, \"capacity\": 1932}, {\"usage\": 712, \"capacity\": 1028}, {\"usage\": 1064, \"capacity\": 1094}, {\"usage\": 692, \"capacity\": 823}, {\"usage\": 529, \"capacity\": 1180}, {\"usage\": 1754, \"capacity\": 1847}, {\"usage\": 436, \"capacity\": 807}, {\"usage\": 458, \"capacity\": 1267}, {\"usage\": 518, \"capacity\": 1167}, {\"usage\": 1499, \"capacity\": 1983}, {\"usage\": 421, \"capacity\": 1337}, {\"usage\": 1199, \"capacity\": 1233}, {\"usage\": 836, \"capacity\": 1255}, {\"usage\": 923, \"capacity\": 1435}, {\"usage\": 347, \"capacity\": 629}, {\"usage\": 1377, \"capacity\": 1876}, {\"usage\": 343, \"capacity\": 682}, {\"usage\": 1304, \"capacity\": 1743}, {\"usage\": 714, \"capacity\": 1804}, {\"usage\": 813, \"capacity\": 1073}, {\"usage\": 1216, \"capacity\": 1723}, {\"usage\": 548, \"capacity\": 1470}, {\"usage\": 546, \"capacity\": 1640}, {\"usage\": 1293, \"capacity\": 1355}, {\"usage\": 1068, \"capacity\": 1116}, {\"usage\": 399, \"capacity\": 689}, {\"usage\": 1069, \"capacity\": 1329}, {\"usage\": 1432, \"capacity\": 1700}, {\"usage\": 1089, \"capacity\": 1416}]}, {\"city_name\": \"Oroppas\", \"data\": [{\"usage\": 427, \"capacity\": 1045}, {\"usage\": 1292, \"capacity\": 1818}, {\"usage\": 491, \"capacity\": 1217}, {\"usage\": 159, \"capacity\": 502}, {\"usage\": 299, \"capacity\": 970}, {\"usage\": 832, \"capacity\": 1964}, {\"usage\": 796, \"capacity\": 1000}, {\"usage\": 875, \"capacity\": 1192}, {\"usage\": 961, \"capacity\": 1943}, {\"usage\": 792, \"capacity\": 1341}, {\"usage\": 1141, \"capacity\": 1171}, {\"usage\": 420, \"capacity\": 939}, {\"usage\": 1121, \"capacity\": 1478}, {\"usage\": 546, \"capacity\": 901}, {\"usage\": 875, \"capacity\": 1011}, {\"usage\": 1329, \"capacity\": 1766}, {\"usage\": 890, \"capacity\": 1654}, {\"usage\": 979, \"capacity\": 1578}, {\"usage\": 722, \"capacity\": 1307}, {\"usage\": 1253, \"capacity\": 1375}, {\"usage\": 537, \"capacity\": 1607}, {\"usage\": 680, \"capacity\": 1048}, {\"usage\": 766, \"capacity\": 1225}, {\"usage\": 524, \"capacity\": 722}, {\"usage\": 1421, \"capacity\": 1762}, {\"usage\": 944, \"capacity\": 1889}, {\"usage\": 467, \"capacity\": 1512}, {\"usage\": 461, \"capacity\": 643}, {\"usage\": 857, \"capacity\": 1950}, {\"usage\": 818, \"capacity\": 980}, {\"usage\": 1210, \"capacity\": 1356}, {\"usage\": 300, \"capacity\": 502}, {\"usage\": 1924, \"capacity\": 1978}, {\"usage\": 788, \"capacity\": 1077}, {\"usage\": 933, \"capacity\": 1644}, {\"usage\": 1383, \"capacity\": 1619}, {\"usage\": 587, \"capacity\": 1004}, {\"usage\": 1029, \"capacity\": 1512}, {\"usage\": 925, \"capacity\": 1760}, {\"usage\": 338, \"capacity\": 1064}]}, {\"city_name\": \"Amayako\", \"data\": [{\"usage\": 442, \"capacity\": 757}, {\"usage\": 790, \"capacity\": 1519}, {\"usage\": 280, \"capacity\": 737}, {\"usage\": 1205, \"capacity\": 1597}, {\"usage\": 1618, \"capacity\": 1827}, {\"usage\": 1296, \"capacity\": 1481}, {\"usage\": 1054, \"capacity\": 1499}, {\"usage\": 463, \"capacity\": 1126}, {\"usage\": 750, \"capacity\": 869}, {\"usage\": 1290, \"capacity\": 1450}, {\"usage\": 261, \"capacity\": 682}, {\"usage\": 483, \"capacity\": 1197}, {\"usage\": 492, \"capacity\": 502}, {\"usage\": 582, \"capacity\": 757}, {\"usage\": 1282, \"capacity\": 1895}, {\"usage\": 1126, \"capacity\": 1714}, {\"usage\": 480, \"capacity\": 609}, {\"usage\": 564, \"capacity\": 1580}, {\"usage\": 521, \"capacity\": 587}, {\"usage\": 603, \"capacity\": 1295}, {\"usage\": 901, \"capacity\": 1222}, {\"usage\": 777, \"capacity\": 1635}, {\"usage\": 1085, \"capacity\": 1468}, {\"usage\": 485, \"capacity\": 602}, {\"usage\": 328, \"capacity\": 824}, {\"usage\": 439, \"capacity\": 1454}, {\"usage\": 326, \"capacity\": 1053}, {\"usage\": 243, \"capacity\": 541}, {\"usage\": 911, \"capacity\": 1359}, {\"usage\": 422, \"capacity\": 887}, {\"usage\": 607, \"capacity\": 659}, {\"usage\": 686, \"capacity\": 1756}, {\"usage\": 305, \"capacity\": 769}, {\"usage\": 1252, \"capacity\": 1784}, {\"usage\": 878, \"capacity\": 1564}, {\"usage\": 391, \"capacity\": 880}, {\"usage\": 361, \"capacity\": 625}, {\"usage\": 925, \"capacity\": 1218}, {\"usage\": 503, \"capacity\": 786}, {\"usage\": 261, \"capacity\": 513}]}, {\"city_name\": \"Ikasagan\", \"data\": [{\"usage\": 1042, \"capacity\": 1484}, {\"usage\": 439, \"capacity\": 978}, {\"usage\": 529, \"capacity\": 1258}, {\"usage\": 975, \"capacity\": 1989}, {\"usage\": 536, \"capacity\": 1205}, {\"usage\": 402, \"capacity\": 638}, {\"usage\": 968, \"capacity\": 1528}, {\"usage\": 836, \"capacity\": 1758}, {\"usage\": 1562, \"capacity\": 1931}, {\"usage\": 716, \"capacity\": 959}, {\"usage\": 501, \"capacity\": 1121}, {\"usage\": 1258, \"capacity\": 1795}, {\"usage\": 535, \"capacity\": 1488}, {\"usage\": 451, \"capacity\": 1015}, {\"usage\": 689, \"capacity\": 1194}, {\"usage\": 551, \"capacity\": 1161}, {\"usage\": 295, \"capacity\": 651}, {\"usage\": 409, \"capacity\": 689}, {\"usage\": 976, \"capacity\": 1254}, {\"usage\": 663, \"capacity\": 1798}, {\"usage\": 685, \"capacity\": 1021}, {\"usage\": 1227, \"capacity\": 1251}, {\"usage\": 1175, \"capacity\": 1662}, {\"usage\": 573, \"capacity\": 841}, {\"usage\": 772, \"capacity\": 802}, {\"usage\": 930, \"capacity\": 1856}, {\"usage\": 1479, \"capacity\": 1750}, {\"usage\": 1396, \"capacity\": 1698}, {\"usage\": 1259, \"capacity\": 1782}, {\"usage\": 1157, \"capacity\": 1337}, {\"usage\": 588, \"capacity\": 678}, {\"usage\": 278, \"capacity\": 509}, {\"usage\": 745, \"capacity\": 1305}, {\"usage\": 731, \"capacity\": 842}, {\"usage\": 627, \"capacity\": 701}, {\"usage\": 895, \"capacity\": 1663}, {\"usage\": 930, \"capacity\": 1220}, {\"usage\": 1588, \"capacity\": 1805}, {\"usage\": 878, \"capacity\": 1974}, {\"usage\": 1646, \"capacity\": 1862}]}, {\"city_name\": \"Akaso\", \"data\": [{\"usage\": 647, \"capacity\": 860}, {\"usage\": 880, \"capacity\": 1054}, {\"usage\": 1107, \"capacity\": 1576}, {\"usage\": 863, \"capacity\": 955}, {\"usage\": 582, \"capacity\": 710}, {\"usage\": 1376, \"capacity\": 1888}, {\"usage\": 780, \"capacity\": 1109}, {\"usage\": 574, \"capacity\": 1679}, {\"usage\": 778, \"capacity\": 1432}, {\"usage\": 659, \"capacity\": 901}, {\"usage\": 1115, \"capacity\": 1436}, {\"usage\": 598, \"capacity\": 1992}, {\"usage\": 324, \"capacity\": 776}, {\"usage\": 244, \"capacity\": 707}, {\"usage\": 1035, \"capacity\": 1174}, {\"usage\": 917, \"capacity\": 1037}, {\"usage\": 764, \"capacity\": 1522}, {\"usage\": 736, \"capacity\": 1058}, {\"usage\": 280, \"capacity\": 793}, {\"usage\": 444, \"capacity\": 779}, {\"usage\": 1635, \"capacity\": 1858}, {\"usage\": 1001, \"capacity\": 1594}, {\"usage\": 546, \"capacity\": 1397}, {\"usage\": 1042, \"capacity\": 1422}, {\"usage\": 709, \"capacity\": 1185}, {\"usage\": 453, \"capacity\": 980}, {\"usage\": 660, \"capacity\": 1415}, {\"usage\": 789, \"capacity\": 1295}, {\"usage\": 1484, \"capacity\": 1807}, {\"usage\": 546, \"capacity\": 867}, {\"usage\": 1427, \"capacity\": 1699}, {\"usage\": 1118, \"capacity\": 1466}, {\"usage\": 433, \"capacity\": 1279}, {\"usage\": 1685, \"capacity\": 1849}, {\"usage\": 546, \"capacity\": 1696}, {\"usage\": 1168, \"capacity\": 1192}, {\"usage\": 391, \"capacity\": 1140}, {\"usage\": 331, \"capacity\": 528}, {\"usage\": 523, \"capacity\": 1006}, {\"usage\": 1235, \"capacity\": 1784}]}, {\"city_name\": \"Amayustam\", \"data\": [{\"usage\": 497, \"capacity\": 1491}, {\"usage\": 1382, \"capacity\": 1810}, {\"usage\": 1529, \"capacity\": 1964}, {\"usage\": 547, \"capacity\": 1661}, {\"usage\": 1333, \"capacity\": 1714}, {\"usage\": 1347, \"capacity\": 1822}, {\"usage\": 812, \"capacity\": 837}, {\"usage\": 356, \"capacity\": 507}, {\"usage\": 584, \"capacity\": 1336}, {\"usage\": 610, \"capacity\": 653}, {\"usage\": 1444, \"capacity\": 1874}, {\"usage\": 1819, \"capacity\": 1907}, {\"usage\": 1500, \"capacity\": 1645}, {\"usage\": 733, \"capacity\": 1219}, {\"usage\": 376, \"capacity\": 539}, {\"usage\": 726, \"capacity\": 1059}, {\"usage\": 252, \"capacity\": 713}, {\"usage\": 517, \"capacity\": 1005}, {\"usage\": 1095, \"capacity\": 1617}, {\"usage\": 1230, \"capacity\": 1747}, {\"usage\": 596, \"capacity\": 1551}, {\"usage\": 590, \"capacity\": 599}, {\"usage\": 657, \"capacity\": 1161}, {\"usage\": 1716, \"capacity\": 1875}, {\"usage\": 981, \"capacity\": 1806}, {\"usage\": 988, \"capacity\": 1366}, {\"usage\": 579, \"capacity\": 1013}, {\"usage\": 1404, \"capacity\": 1462}, {\"usage\": 588, \"capacity\": 945}, {\"usage\": 655, \"capacity\": 808}, {\"usage\": 280, \"capacity\": 510}, {\"usage\": 322, \"capacity\": 573}, {\"usage\": 708, \"capacity\": 1853}, {\"usage\": 811, \"capacity\": 1494}, {\"usage\": 815, \"capacity\": 1592}, {\"usage\": 578, \"capacity\": 749}, {\"usage\": 392, \"capacity\": 916}, {\"usage\": 1434, \"capacity\": 1986}, {\"usage\": 342, \"capacity\": 543}, {\"usage\": 1276, \"capacity\": 1869}]}, {\"city_name\": \"Atika\", \"data\": [{\"usage\": 371, \"capacity\": 812}, {\"usage\": 539, \"capacity\": 954}, {\"usage\": 1105, \"capacity\": 1577}, {\"usage\": 474, \"capacity\": 906}, {\"usage\": 648, \"capacity\": 1760}, {\"usage\": 914, \"capacity\": 1083}, {\"usage\": 193, \"capacity\": 594}, {\"usage\": 1115, \"capacity\": 1880}, {\"usage\": 1230, \"capacity\": 1297}, {\"usage\": 1502, \"capacity\": 1999}, {\"usage\": 564, \"capacity\": 798}, {\"usage\": 579, \"capacity\": 640}, {\"usage\": 1437, \"capacity\": 1772}, {\"usage\": 768, \"capacity\": 1665}, {\"usage\": 367, \"capacity\": 1201}, {\"usage\": 1261, \"capacity\": 1295}, {\"usage\": 823, \"capacity\": 973}, {\"usage\": 286, \"capacity\": 726}, {\"usage\": 1250, \"capacity\": 1294}, {\"usage\": 494, \"capacity\": 1016}, {\"usage\": 1493, \"capacity\": 1912}, {\"usage\": 1805, \"capacity\": 1884}, {\"usage\": 1011, \"capacity\": 1367}, {\"usage\": 577, \"capacity\": 1876}, {\"usage\": 991, \"capacity\": 1433}, {\"usage\": 1052, \"capacity\": 1705}, {\"usage\": 1269, \"capacity\": 1861}, {\"usage\": 828, \"capacity\": 1299}, {\"usage\": 1339, \"capacity\": 1845}, {\"usage\": 1049, \"capacity\": 1290}, {\"usage\": 533, \"capacity\": 1725}, {\"usage\": 1162, \"capacity\": 1246}, {\"usage\": 693, \"capacity\": 1234}, {\"usage\": 673, \"capacity\": 1970}, {\"usage\": 993, \"capacity\": 1544}, {\"usage\": 1095, \"capacity\": 1899}, {\"usage\": 958, \"capacity\": 1052}, {\"usage\": 919, \"capacity\": 1180}, {\"usage\": 716, \"capacity\": 1107}, {\"usage\": 1155, \"capacity\": 1567}]}, {\"city_name\": \"Aran\", \"data\": [{\"usage\": 869, \"capacity\": 1597}, {\"usage\": 776, \"capacity\": 902}, {\"usage\": 484, \"capacity\": 717}, {\"usage\": 591, \"capacity\": 601}, {\"usage\": 421, \"capacity\": 714}, {\"usage\": 1072, \"capacity\": 1680}, {\"usage\": 1290, \"capacity\": 1850}, {\"usage\": 926, \"capacity\": 1039}, {\"usage\": 309, \"capacity\": 797}, {\"usage\": 466, \"capacity\": 1335}, {\"usage\": 1061, \"capacity\": 1491}, {\"usage\": 621, \"capacity\": 1088}, {\"usage\": 895, \"capacity\": 1613}, {\"usage\": 261, \"capacity\": 648}, {\"usage\": 806, \"capacity\": 1094}, {\"usage\": 650, \"capacity\": 1025}, {\"usage\": 554, \"capacity\": 1215}, {\"usage\": 430, \"capacity\": 1222}, {\"usage\": 478, \"capacity\": 1130}, {\"usage\": 548, \"capacity\": 876}, {\"usage\": 1775, \"capacity\": 1841}, {\"usage\": 1371, \"capacity\": 1913}, {\"usage\": 1946, \"capacity\": 1975}, {\"usage\": 213, \"capacity\": 508}, {\"usage\": 663, \"capacity\": 737}, {\"usage\": 820, \"capacity\": 1366}, {\"usage\": 884, \"capacity\": 1671}, {\"usage\": 1740, \"capacity\": 1854}, {\"usage\": 425, \"capacity\": 798}, {\"usage\": 659, \"capacity\": 1923}, {\"usage\": 300, \"capacity\": 734}, {\"usage\": 436, \"capacity\": 859}, {\"usage\": 521, \"capacity\": 771}, {\"usage\": 961, \"capacity\": 1401}, {\"usage\": 1760, \"capacity\": 1931}, {\"usage\": 1130, \"capacity\": 1337}, {\"usage\": 758, \"capacity\": 1966}, {\"usage\": 1367, \"capacity\": 1443}, {\"usage\": 1037, \"capacity\": 1736}, {\"usage\": 178, \"capacity\": 500}]}, {\"city_name\": \"Amihsukuf\", \"data\": [{\"usage\": 476, \"capacity\": 558}, {\"usage\": 1317, \"capacity\": 1774}, {\"usage\": 1025, \"capacity\": 1888}, {\"usage\": 1028, \"capacity\": 1903}, {\"usage\": 1107, \"capacity\": 1388}, {\"usage\": 1106, \"capacity\": 1743}, {\"usage\": 571, \"capacity\": 939}, {\"usage\": 496, \"capacity\": 604}, {\"usage\": 527, \"capacity\": 654}, {\"usage\": 1137, \"capacity\": 1338}, {\"usage\": 1438, \"capacity\": 1514}, {\"usage\": 339, \"capacity\": 547}, {\"usage\": 295, \"capacity\": 635}, {\"usage\": 1169, \"capacity\": 1736}, {\"usage\": 925, \"capacity\": 1051}, {\"usage\": 215, \"capacity\": 674}, {\"usage\": 608, \"capacity\": 1433}, {\"usage\": 1287, \"capacity\": 1547}, {\"usage\": 1102, \"capacity\": 1509}, {\"usage\": 630, \"capacity\": 677}, {\"usage\": 649, \"capacity\": 1333}, {\"usage\": 513, \"capacity\": 651}, {\"usage\": 623, \"capacity\": 1641}, {\"usage\": 1120, \"capacity\": 1573}, {\"usage\": 314, \"capacity\": 781}, {\"usage\": 615, \"capacity\": 734}, {\"usage\": 568, \"capacity\": 735}, {\"usage\": 1814, \"capacity\": 1860}, {\"usage\": 1480, \"capacity\": 1682}, {\"usage\": 1290, \"capacity\": 1521}, {\"usage\": 505, \"capacity\": 850}, {\"usage\": 906, \"capacity\": 1328}, {\"usage\": 216, \"capacity\": 555}, {\"usage\": 684, \"capacity\": 1518}, {\"usage\": 957, \"capacity\": 1539}, {\"usage\": 997, \"capacity\": 1555}, {\"usage\": 1308, \"capacity\": 1581}, {\"usage\": 465, \"capacity\": 1550}, {\"usage\": 954, \"capacity\": 1856}, {\"usage\": 444, \"capacity\": 741}]}]";
  var jsonObjects = Utilities.jsonParse(jsonString);
  for (var i = 0; i < jsonObjects.length; i++) {
    var jsonObject = jsonObjects[i];
    var sheet = spreadSheet.insertSheet(jsonObject.city_name);
    var row = 1;
    for (var j = 0; j < jsonObject.data.length; j++) {
      var data = jsonObject.data[j];
      sheet.getRange(row, 1).setValue(data.capacity);
      sheet.getRange(row, 2).setValue(data.usage);
      var result = data.usage / data.capacity;
      sheet.getRange(row, 3).setValue(result);
      sheet.getRange(row, 3).setNumberFormat("###.00%");
      row = row + 1;
    }
  }
}

 

【スライドパズル】

3x3 ~ 6x6 のスライドパズル5,000問を回答する(全体の手数制限、スライドできないマスあり)」問題。

 → IDA* の評価関数に MD と LinearConflict (※1)と独自の壁判定で回答しました。

 

回答できたのは、3,422 / 5,000(約68%)で、

使用した手数は、167,348 / 308,017(約54%)でした。。。無念><;

 

試したアルゴリズム

 

参考にしたサイト(お勧め!)

 

工夫した点

当初、評価関数には、マンハッタン距離(MD)のみを使用していたのですが、

同一行で数字の入れ替えを考慮した Linear Conflict (※1)を適用すると、解ける問題が増えました。

また、壁の問題に時間がかかっていたので、

「同一行で数字の入れ替えがあり、かつ、壁をまたいでいる場合に値を +2 する」

という独自ロジックを適用したところ、さらに解ける問題が増えました。

が、評価関数が重すぎたせいで、処理時間がネックとなり、時間切れとなりました。。。

以下、抜粋です。

// IDDFS
private boolean dfs(int state[], int spacePos, int prevStep, int stepCount,
        int depth, int hValue) {
    if (Arrays.equals(mEndState, state) == false) { // ゴール判定
        for (int step = 0; step < 4; step++) { // 予め壁判定された移動可能が4方向に移動
            int newSpacePosOffset = mDirectionCache[spacePos][prevStep][step];
            if (newSpacePosOffset != 0) { // 移動可能なので新しい状態を生成
                int newSpacePos = spacePos + newSpacePosOffset; // 空白の移動
                int newState[] = Arrays.copyOf(state, mCellCount);
                int moveNumber = state[newSpacePos]; // 入れ替える数字
                newState[newSpacePos] = 0; // 空白の移動
                newState[spacePos] = moveNumber; // 数字の移動
                int newHValue = hValue // 新しい評価値の算出
                        - mForeDistances[newSpacePos][moveNumber - 1]
                        + mForeDistances[spacePos][moveNumber - 1];
                // 深さ制限を確認し、再帰呼び出し
                if ((stepCount + 1 + newHValue + h2(newState)) <= depth) {
                    if (dfs(newState, newSpacePos, step, (stepCount + 1),
                            depth, newHValue)) {
                        mResultSteps = STEPS_CHAR[prevStep] + mResultSteps;
                        return true;
                    }
                }
            }
        }
        return false;
    } else {
        mResultSteps = STEPS_CHAR[prevStep] + mResultSteps;
        return true;
    }
}

// 評価関数(キャッシュ済MDを参照)
private static int h(int state[]) {
    int distance = 0;
    int foreDistances[][] = mForeDistances;
    for (int index = 0; index < mCellCount; index++) {
        int number = state[index];
        if (number > 0) {
            distance += foreDistances[index][number - 1];
        }
    }
    return distance;
}

// Linear conflicts に壁判定を加えた評価関数
private static int h2(int state[]) {
    int distance = 0;
    // Linear conflicts row
    {
        int beginIndex = 0;
        for (int row = 0; row < mCellHeight; row++) {
            int endIndex = beginIndex + mCellWidth - 1;
            int beginNumber = beginIndex + 1;
            int endNumber = endIndex + 1;
            for (int index = beginIndex; index < endIndex; index++) {
                for (int searchIndex = (index + 1); searchIndex <= endIndex; searchIndex++) {
                    int number1 = state[index];
                    int number2 = state[searchIndex];
                    if ((beginNumber <= number1) && (number1 <= endNumber)) {
                        int t1 = mForeDistances[index][number1 - 1];
                        if (t1 > 0) {
                            if ((index % mCellWidth) != (mCellWidth - 1)) {
                                if (state[index + 1] == -1) {
                                    distance += 2; // 同一行で壁をまたぐ
                                }
                            }
                        } else if (t1 < 0) {
                            if ((index % mCellWidth) != 0) {
                                if (state[index - 1] == -1) {
                                    distance += 2; // 同一行で壁をまたぐ
                                }
                            }
                        }
                    } else if ((beginNumber <= number1)
                            && (number1 <= endNumber)) {
                        if ((beginNumber <= number2)
                                && (number2 <= endNumber)) {
                            if (number1 > number2) {
                                distance += 2; // 同一行で数字の入れ替え
                            }
                        }
                    }
                }
            }
            beginIndex += mCellWidth;
        }
    }

    // Linear conflicts col
    {
        int lastRowIndex = mCellWidth * (mCellHeight - 1);
        int endIndex = lastRowIndex;
        for (int col = 0; col < mCellWidth; col++) {
            for (int index = col; index <= endIndex; index += mCellWidth) {
                for (int searchIndex = index + mCellWidth; searchIndex <= endIndex; searchIndex += mCellWidth) {
                    int number1 = state[index] + 1;
                    int number2 = state[searchIndex] + 1;
                    boolean tt = false;
                    for (int row = 0; row < mCellHeight; row++) {
                        int number = mNumberConflictsCol[col][row];
                        if (number1 == number) {
                            int t1 = mForeDistances[index][number1 - 1];
                            if (t1 > 0) {
                                if ((index / mCellWidth) != (mCellHeight - 1)) {
                                    if (state[index + mCellWidth] == -1) {
                                        distance += 2; // 同一行で壁をまたぐ
                                        tt = true;
                                        break;
                                    }
                                }
                            } else if (t1 < 0) {
                                if ((index / mCellWidth) != 0) {
                                    if (state[index - mCellWidth] == -1) {
                                        distance += 2; // 同一行で壁をまたぐ
                                        tt = true;
                                        break;
                                    }
                                }
                            }
                        }
                    }
                    boolean number1Exist = false;
                    boolean number2Exist = false;
                    if (tt == false) {
                        for (int row = 0; row < mCellHeight; row++) {
                            int number = mNumberConflictsCol[col][row];
                            if (number1 == number) {
                                number1Exist = true;
                            }
                            if (number2 == number) {
                                number2Exist = true;
                            }
                        }
                        if (number1Exist && number2Exist) {
                            if (number1 > number2) {
                                distance += 2; // 同一行で数字の入れ替え
                            }
                        }
                    }
                }
            }
            endIndex++;
        }
    }
    return distance;
}

// マンハッタン距離のキャッシュ作成(最初に一度だけ作成)
private int[][] getDistanceCache(int[] goalState) {
    int distances[][] = new int[mCellCount][];
    // 入力元のインデックスすべてについて
    for (int index = 0; index < mCellCount; index++) {
        // そのインデックスに入る可能性のあるすべての数字について
        distances[index] = new int[mCellCount];
        for (int number = 1; number < mCellCount; number++) {
            // Goal状態では、その数字は、どのインデックスにあるか?
            for (int searchIndex = 0; searchIndex < mCellCount; searchIndex++) {
                if (goalState[searchIndex] == number) {
                    // 目的の数字のインデックスが見つかった
                    distances[index][number - 1] = getDistance(index,
                            searchIndex, mCellWidth, mCellHeight);
                    break;
                }
            }
        }
    }
    return distances;
}

// マンハッタン距離の算出(キャッシュ作成時のみ呼び出される)
private static int getDistance(int index1, int index2, int cellWidth,
        int cellHeight) {
    int posX1 = index1 % cellWidth;
    int posY1 = index1 / cellHeight;
    int posX2 = index2 % cellWidth;
    int posY2 = index2 / cellHeight;
    int diffX = posX1 - posX2;
    int diffY = posY1 - posY2;
    if (diffX < 0) {
        diffX *= -1;
    }
    if (diffY < 0) {
        diffY *= -1;
    }
    return (diffX + diffY);
}

 

スコア分布

gddj2011_score.png

 

あわせて読みたい

1

2016年8月

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31