2010-08-23
2-legged OAuth
| 
import httplib,urllib,urllib2
import oauth
url = "http://gdd-2010-quiz-japan.appspot.com/oauth/########################"
params = { 'hello': 'world' }
consumer_key = '########################'
secret_key = '########################'
consumer = oauth.OAuthConsumer(consumer_key, secret_key)
request = oauth.OAuthRequest.from_consumer_and_token(consumer, http_method='POST', http_url=url, parameters=params)
request.sign_request(oauth.OAuthSignatureMethod_HMAC_SHA1(), consumer, None)
print request.to_url()
print request.to_header()
conn = httplib.HTTPConnection("gdd-2010-quiz-japan.appspot.com")
conn.request("POST", "/oauth/########################", urllib.urlencode(params), request.to_header('devquiz'))
response = conn.getresponse()
print response.status, response.reason
data = response.read()
conn.close()
print data
MAPS API
| 
- A地点を出発し、A地点に戻ってくる
- A地点→B地点, B地点→A地点 では所要時間が異なる場合がある（と問題文で教えてくれていた）
- 全部で最大10地点 → 経路候補は全部で9!通りしかない。permutation全部調べても余裕でしょ →Gaucheで簡単なスクリプトを書いた
- APIから所要時間を引っ張ってくるのが面倒だった
- xmlきれいなのでsedで抜いてきたとか
- ソース全部まとめてアップロードしてエラーが起きないとは思えなかった（ZIPのバイナリをだらだらと表示しかねないと思った）ので、gaucheで書いた肝の部分のみアップ
BEGIN {
M=0
# awk -f lookup.awk -v level=1 < level1.dat
# awk -f lookup.awk -v level=2 < level2.dat
# awk -f lookup.awk -v level=3 < level3.dat
}
{
split($0,ar," ")
name[M] = ar[1]
lat[M] = ar[2]
long[M] = ar[3]
M++
}
END{
for(i=0;i<M;i++){
for(j=0;j<M;j++){
if (i==j) continue;
cmd = sprintf("wget \"http://maps.google.com/maps/api/directions/xml?origin=%9.6f,%10.6f&destination=%9.6f,%10.6f&language=ja&sensor=false\" -O level%d_from%02d_to%02d.xml", lat[i],long[i], lat[j],long[j], level,i,j)
system(cmd)
print cmd
}
}
}
(use srfi-1)
(use util.combinations)
;;
;; level 3
;;
(define cities
#(
("東京タワー" 35.658570 139.745484)
("首里城" 26.216991 127.719362)
("松山城" 33.842035 132.764806)
("青葉城跡" 38.251127 140.855294)
("五条大橋" 34.995682 135.767890)
("日光東照宮" 36.758051 139.598899)
("日本銀行" 35.686839 139.771438)
("海ほたる" 35.464380 139.874407)
("日本科学未来館" 35.619415 139.776550)
("東京大学" 35.712940 139.759590)
))
;;
;; 各点間の所要時間は別スクリプトでAPIを呼び出して調べました。
;;
(define durations-data
'(
((0 . 1) . 150131)
((0 . 2) . 40217)
((0 . 3) . 18011)
((0 . 4) . 21655)
((0 . 5) . 9716)
((0 . 6) . 821)
((0 . 7) . 2365)
((0 . 8) . 1071)
((0 . 9) . 1314)
((1 . 0) . 150327)
((1 . 2) . 121112)
((1 . 3) . 165946)
((1 . 4) . 129338)
((1 . 5) . 158930)
((1 . 6) . 150307)
((1 . 7) . 151256)
((1 . 8) . 150658)
((1 . 9) . 150769)
((2 . 0) . 40689)
((2 . 1) . 121187)
((2 . 3) . 56308)
((2 . 4) . 19700)
((2 . 5) . 49292)
((2 . 6) . 40669)
((2 . 7) . 41618)
((2 . 8) . 41020)
((2 . 9) . 41131)
((3 . 0) . 18369)
((3 . 1) . 166422)
((3 . 2) . 56508)
((3 . 4) . 37946)
((3 . 5) . 14511)
((3 . 6) . 18114)
((3 . 7) . 20094)
((3 . 8) . 18732)
((3 . 9) . 18043)
((4 . 0) . 21981)
((4 . 1) . 129354)
((4 . 2) . 19440)
((4 . 3) . 37600)
((4 . 5) . 30584)
((4 . 6) . 21961)
((4 . 7) . 22910)
((4 . 8) . 22312)
((4 . 9) . 22423)
((5 . 0) . 9730)
((5 . 1) . 159016)
((5 . 2) . 49102)
((5 . 3) . 14135)
((5 . 4) . 30540)
((5 . 6) . 9475)
((5 . 7) . 11455)
((5 . 8) . 10093)
((5 . 9) . 9404)
((6 . 0) . 937)
((6 . 1) . 150406)
((6 . 2) . 40492)
((6 . 3) . 17702)
((6 . 4) . 21930)
((6 . 5) . 9407)
((6 . 7) . 2379)
((6 . 8) . 1085)
((6 . 9) . 854)
((7 . 0) . 2658)
((7 . 1) . 151693)
((7 . 2) . 41779)
((7 . 3) . 19913)
((7 . 4) . 23217)
((7 . 5) . 11618)
((7 . 6) . 2559)
((7 . 8) . 2291)
((7 . 9) . 3112)
((8 . 0) . 1189)
((8 . 1) . 150658)
((8 . 2) . 40744)
((8 . 3) . 18444)
((8 . 4) . 22182)
((8 . 5) . 10149)
((8 . 6) . 1090)
((8 . 7) . 1912)
((8 . 9) . 1643)
((9 . 0) . 1170)
((9 . 1) . 150703)
((9 . 2) . 40789)
((9 . 3) . 17837)
((9 . 4) . 22227)
((9 . 5) . 9542)
((9 . 6) . 681)
((9 . 7) . 2816)
((9 . 8) . 1522)
))
(define M (vector-length cities))
(define shortest-time 999999999999999999)
(define shortest-route '())
(permutations-for-each
(lambda (p)
;; (print p) maybe 1 minute
(let1 route (cons 0 (append p '(0)))
(let loop ((a (car route)) (rest (cdr route)) (res '()))
(if (null? rest)
(let1 time (apply + (reverse! res))
(when (< time shortest-time)
(set! shortest-time time)
(set! shortest-route route)))
(let* ((key (cons a (car rest)))
(dur (cdr (assoc key durations-data))))
(loop (car rest) (cdr rest) (cons dur res)))))))
(iota (- M 1) 1))
(format #t "~a\t~d\n"
(string-join
(map (lambda (ix) (car (vector-ref cities ix))) shortest-route)
" ")
shortest-time)
しりとり
| 
- 一応プログラムで
- けどlevel 3のグラフ構造は読み切れないのでlevel3のグラフは手書き
- level 1, 2 は適当にやっても勝てるけど、level 3は向こうも勝ちに来るので
- これまでの履歴と、相手が出してきた手から最善手を教えてくれるっぽいプログラムを書いた
- level 3 はなんというかステージ１、ステージ２があって、ステージ１から先に抜けた方が負け、な感じ
- ステージ1: d,e,f,g,i,j,q,s,w の中での移動
- なのでステージ１の語だけ拾いだして上のプログラムを適用
- （ステージ２に行ったら同じ文字に追い込めば勝てる！）
//...
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))
#define RFOR(var,from,to) for(int var=(to);var>=(from);var--)
//#include "cout.h"
typedef pair<char,char> cc;
int arc[26][26];
long long trial=0LL;
typedef pair<int,int> ii;
#define LIM 5000000LL
int sub(int now, vector<int>& route)
{
trial++; //if (trial%5000000LL == 0) printf("[%lld]\n", trial);
if (trial >= LIM) {
if (trial == LIM) printf("too deep. break.\n");
return 0;
}
int way=0, res=0;
rep(next,26){
if (arc[now][next]){
way++;
arc[now][next]--;
res = sub(next, route);
arc[now][next]++;
if (res < 0) {
route.pb(-1);
route.pb(now); return next;
}
}
}
if (way==0) {
route.clear(); route.pb(now);
return -1;
}
route.pb(now);
return res ? -1 : 0;
}
void dump(int last)
{
printf("\n%c.. ", 'a'+last);
rep(c,26) printf(" %c", 'a'+c);
printf("\n");
rep(r,26){
printf("%c ->", 'a'+r);
rep(c,26){
if (arc[r][c])
printf(" %d", arc[r][c]);
else
printf(" -");
}
printf("\n");
}
printf("\n");
}
main(int argc, char **argv)
{
rep(i,26) rep(j,26) arc[i][j]=0;
int wn=0;
if (argc != 2) {
printf("usage: %s <word-list>\n", argv[0]);
return 0;
}
FILE *fp = fopen(argv[1], "r"); if (!fp) return 0;
char buf[256], first_str[256];
while (fgets(buf,256,fp) != NULL) {
//string s; cin >> s;
int len = strlen(buf);
while (len>0 && buf[len-1]<' ') buf[--len]=0;
int b=buf[0]-'a', e=buf[len-1]-'a';
if (wn == 0) strcpy(first_str, buf);
arc[b][e]++; wn++;
}
fclose(fp);
set<int> candidates;
int last = 0, b, e;
for (int wi=wn; wi>0; wi-=2) {
if (wi < wn) {
candidates.clear();
rep(i,26) if (arc[last][i]) candidates.insert(i);
if (candidates.empty()) {
printf("YOU WIN!!\n"); break;
}
}
printf("[%d] Which word did Google consume? ", wi);
if (wi == wn) {
printf("(%s) ", first_str);
} else {
printf("%c..[", 'a'+last);
tr(candidates,it) printf("%c,", 'a'+*it);
printf("] : "); fflush(NULL);
}
fflush(NULL);
string s; cin >> s;
switch (sz(s)) {
case 0:
b=last;
rep(i,26) if (arc[last][i]) { e=i; break; }
break;
case 1:
b=last; e=s[0]-'a'; break;
case 2: default:
b=s[0]-'a', e=lastc(s)-'a'; break;
}
arc[b][e]--;
dump(last=e);
vector<int> route; trial = 0LL;
int res = sub(last, route);
if (res) {
if (sz(route)>0) route.pop_back();
reverse(all(route));
tr(route,it) printf(" -> %c", 'a' + *it);
}
candidates.clear();
rep(i,26) if (arc[last][i]) candidates.insert(i);
if (candidates.empty()) {
printf("GOOGLE WINS!!\n"); break;
}
printf("\n[%d] Your choice (input last char): %c..[", wi-1, 'a'+last);
tr(candidates,it) printf("%c,", 'a'+*it);
printf("] : "); fflush(NULL);
cin >> s;
b = last, e = s[0]-'a'; arc[b][e]--;
dump(last=e);
}
}
pac-man
| 
- SuperHackerコースの目玉。総当りで行けるのはLevel1までか
- 探索順をランダムに
- 一定の探索ステップ数に達したら中断
- 探索打ち切り数はT*1.3〜1.5ぐらいで適当にやってた
- ラップタイム毎の最高スコア（後に４位まで）を得たルートを記憶しておいて、時々（ランダムに）、過去に保存したあるラップタイム（ランダム）の保存ルートから再開する
- これはちょっとGAっぽい
- 移動可能な方向を毎回ステップ毎に調べてるのは馬鹿なので、
- グラフ構造を把握して、ある点からある点への距離（ステップ数）をdijkstraか何かで全部調べておく
- Level3だとちょっと時間がかかるので、この距離テーブルはファイルに保存しておく
- 目先にえさがない場合、残りのえさ全てからの「重力」の合計の大きい方からDFS
- この程度のことで500は簡単に行くようになった。
- しかし520前後までしか伸びない…
問題ファイル例 (level2)
300 20 17 #################### ###.....L..........# ###.##.##.##L##.##.# ###.##.##.##.##.##.# #.L................# #.##.##.##.##.##.### #.##.##L##.##.##.### #.................L# #.#.#.#J####J#.#.#.# #L.................# ###.##.##.##.##.##.# ###.##.##R##.##.##.# #................R.# #.##.##.##.##R##.### #.##.##.##.##.##.### #@....R..........### ####################
最後の頃のコード
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
//#include "cout.h"
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
const int infty = 987654321;
template <typename T> T infsum(T a, T b){
return (a == infty || b == infty)? infty : (a + b);
}
#include <stdlib.h>
#include <libgen.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#define DEFAULT_STEP_LIMIT 5000
#define DEFAULT_RAND_FREQ 20
#define DEFAULT_VH_WEIGHT 0 //.003
int rand_freq = DEFAULT_RAND_FREQ, step_limit = DEFAULT_STEP_LIMIT, hiscore = 0;
double vh_weight = DEFAULT_VH_WEIGHT;
vector<string> rawmap;
int T, H, W;
int meIdx, t=0, score=0, timebonus=0, esamax=0;
int dirx[5] = { 0, -1, 0, 1, 0 }, diry[5] = { 1, 0, -1, 0, 0 }; // CW: 下 左 上 右 .
char dirt[5] = { 'j', 'h', 'k', 'l', '.' };
vector<int> aIdx, aType, aToggle, ldir; int aN;
vector<int> hist;
char map_name[128];
int N; // number of nodes
vector<int> esa;
vector<char> trans;
vector<vector<int> > route;
vector<int> route_cnt;
vector<int> ord_to_idx, idx_to_ord;
vector<vector<int> > arc, distances;
class Frame {
public:
int _meIdx, _t, _score, _aN;
vector<int> _aIdx, _aType, _aToggle, _ldir, _hist;
vector<int> _esa;
public:
Frame(){
_meIdx = meIdx; _t = t; _score = score;
_aN = aN;
_aIdx.assign(all(aIdx)); _aType.assign(all(aType)); _aToggle.assign(all(aToggle));
_ldir.assign(all(ldir)); _hist.assign(all(hist));
_esa.assign(all(esa));
}
void call() {
meIdx = _meIdx; t = _t; score = _score;
aN = _aN;
aIdx.assign(all(_aIdx)); aType.assign(all(_aType)); aToggle.assign(all(_aToggle));
ldir.assign(all(_ldir)); hist.assign(all(_hist));
esa.assign(all(_esa));
}
~Frame() {
_aIdx.clear(); _aType.clear(); _aToggle.clear();
_ldir.clear(); _score = score;
_esa.clear();
}
string dump() {
stringstream ss;
ss << "t=" << _t << ", score=" << _score;
return ss.str();
}
};
int steps;
vector<int> hihi, memo_i;
Frame *memo[701][4], *frame_for_reset;
bool random_mode = false;
inline bool coince(int m0, int m1, int a0, int a1) {
return (a1==m1 || (a0==m1 && a1==m0));
}
inline double drand(){
return 1.0 / 65536 * (rand() % 65536);
}
vector<int> dijkstra(int start_v)
{
vector<int> distance(N, infty);
//vector<int> predecessor(N, -1);
set<int> S;
S.insert(start_v);
distance[start_v] = 0;
rep(v,N){
if (v == start_v) continue;
if (arc[start_v][v] == infty) continue;
distance[v] = arc[start_v][v];
//predecessor[v] = start_v;
}
while (S.size() < N) { // 各点へ
// find v* from V\S with distance(v*) = min{distance(v):v from V\S}
int v_ = -1;
int d_ = infty;
rep(v,N){
if (found(S,v)) continue;
// V\S
if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
}
if (v_ == -1) break;
S.insert(v_);
rep(v,N){ // FOR ALL v from V\S DO
if (found(S,v)) continue;
// V\S
int d_ = infsum(distance[v_], arc[v_][v]);
if (d_ < distance[v]) {
distance[v] = d_;
//predecessor[v] = v_;
}
}
}
return distance;
}
// MONITOR
void mon_(FILE *oport)
{
fprintf(oport, "\n%d score=%d timebonus=%d\n", T-t, score, timebonus);
vector<vector<char> > screen(H,vector<char>(W,'+'));
rep(idx,N){
int ord=idx_to_ord[idx], c=ord%W, r=ord/W;
screen[r][c] = esa[idx] ? '.' : ' ';
rep(i,aN){
if (idx==aIdx[i]) screen[r][c] = aType[i];
}
if (idx==meIdx) screen[r][c] = '@';
}
rep(r,H){
rep(c,W) fputc(screen[r][c], oport);
fputc('\n', oport);
}
fprintf(oport, "> ");
rep(i,t) fputc(hist[i], oport);
fputc('\n', oport);
}
void mon()
{
mon_(stdout);
}
void save()
{
if (!map_name[0]) return;
char path[256];
// ここではmkdirしないので先に自分で作ってね
sprintf(path, "ans/%s/%03d.scr", map_name, score+timebonus);
printf("path: %s\n", path);
FILE *fp = fopen(path, "wx"); // exclusive!!
if (fp != NULL) {
mon_(fp);
fclose(fp);
}
}
//
// 地図をファイルから読み取り
//
bool load_rawmap(char *path)
{
FILE *fp = fopen(path, "r");
if (fp == NULL){
cerr << "Read Error" << endl;
return false;
}
int dm0 = fscanf(fp, "%d%d%d", &T,&W,&H);
char rowbuf[256], *dm1;
dm1 = fgets(rowbuf,256,fp); // eat a crlf
rep(r,H){
dm1 = fgets(rowbuf,256,fp);
rawmap.pb(string(rowbuf));
}
fclose(fp);
//
esa.clear(); esamax = 0;
trans.clear();
route.clear(); route_cnt.clear();
ord_to_idx.assign(H*W,-1); idx_to_ord.clear();
aIdx.clear(); aType.clear(); // aToggle.clear();
aN = 0;
int idx = 0;
rep(r,H) rep(c,W) {
char ch = rawmap[r][c];
if (ch == '#') continue;
trans.pb(ch);
int ord = r*W + c;
idx_to_ord.pb(ord); ord_to_idx[ord] = idx;
bool esa_p = false;
switch (ch) {
case '.': esa_p = true; esamax++; break;
case ' ': break;
case '@': meIdx = idx; break;
default:
aIdx.pb(idx); aType.pb(ch); aN++; break;
}
esa.pb(esa_p ? 1 : 0);
route.pb(vector<int>(4,-1)); int cnt=0;
// CW: 下 左 上 右 .
if (rawmap[r+1][c] != '#') { route[idx][0] = ord+W; cnt++; }
if (rawmap[r][c-1] != '#') { route[idx][1] = ord-1; cnt++; }
if (rawmap[r-1][c] != '#') { route[idx][2] = ord-W; cnt++; }
if (rawmap[r][c+1] != '#') { route[idx][3] = ord+1; cnt++; }
route_cnt.pb(cnt);
idx++;
}
N = idx;
aToggle.assign(aN,0);
ldir.resize(aN);
// ord(y*W+x)-> idx
rep(i,N) {
rep(d,4) if (route[i][d] >= 0) route[i][d] = ord_to_idx[route[i][d]];
}
// arc
arc.assign(N, vector<int>(N,infty)); distances.clear();
rep(i,N) arc[i][i]=0;
rep(i,N){
rep(d,4){
int j = route[i][d];
if (j>=0) arc[i][j] = arc[j][i] = 1;
}
}
mon(); // 初期状態マップを表示。dijkstraを待ってる間の退屈しのぎ
string path_d(path); path_d += ".d";
int fd_d = open(path_d.c_str(), O_RDONLY);
if (fd_d != -1) {
short N_;
int e = read(fd_d, &N_, sizeof(short));
short *buf = (short *)malloc(sizeof(N_)*N*N);
if (buf != NULL) {
e = read(fd_d, buf, sizeof(short)*N*N);
distances.assign(N,vector<int>(N,infty));
rep(i,N) distances[i][i] = 0;
for(int i=0;i<N-1;++i)
for(int j=i+1;j<N;++j) {
short v = buf[i*N+j];
if (v >= 0) distances[i][j] = distances[j][i] = v;
}
free(buf);
}
close(fd_d);
} else {
// 各ノード間の距離（総当り）を求める。dijkstraですが。
rep(i,N) {
distances.pb(dijkstra(i));
printf("\rdijkstra #%3d/%d...", 1+i,N);
fflush(stdout);
}
printf("\r \r");
fd_d = creat(path_d.c_str(),0644);// open(path_d.c_str(), O_CREAT|O_WRONLY|O_TRUNC, 0644);
if (fd_d != -1) {
short N_ = N, *buf = (short *)malloc(sizeof(N)*N*N);
int e = write(fd_d, &N_, sizeof(short));
if (buf != NULL) {
rep(i,N) rep(j,N) {
int v = distances[i][j];
buf[i*N+j] = (v == infty)? -1 : (short)v;
}
e = write(fd_d, buf, sizeof(short)*N*N);
free(buf);
}
}
close(fd_d);
}
return true;
}
void reset(){
frame_for_reset->call();
}
//
// 敵機（全部）の動きを計算; ax[], ay[], ldir[]
//
int teki()
{
int me_ord=idx_to_ord[meIdx], me_x=me_ord%W, me_y=me_ord/W;
rep(i,aN){
int idx=aIdx[i], ord=idx_to_ord[idx], x=ord%W, y=ord/W;
if (t==0) {
/// t==0; 下、左、上、右
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d]; ldir[i] = d;
break;
}
} else {
/// t>=1
int rcnt = route_cnt[idx];
if (rcnt == 1) {
// 行き止まりマス
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d]; ldir[i] = d;
break;
}
} else if (rcnt == 2) {
// 通路マス
int ng_dir = (ldir[i]+2)%4;
rep(d,4){
if (route[idx][d]<0) continue;
if (d == ng_dir) continue;
aIdx[i] = route[idx][d]; ldir[i] = d;
break;
}
} else {
//交差点マス
int dx=me_x - x, dy=me_y - y;
int ux=dx?(dx>0?1:-1):0, uy=dy?(dy>0?1:-1):0;
int dir_x = ux>0?3:1, dir_y = uy>0?0:2;
int at=aType[i];
aToggle[i]++;
switch (at){
case 'V':
if (dy != 0 && route[idx][dir_y]>=0) {
aIdx[i] = route[idx][dir_y];
ldir[i] = dir_y;
} else if (dx != 0 && route[idx][dir_x]>=0) {
aIdx[i] = route[idx][dir_x];
ldir[i] = dir_x;
} else {
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
case 'H':
if (dx != 0 && route[idx][dir_x]>=0) {
aIdx[i] = route[idx][dir_x];
ldir[i] = dir_x;
} else if (dy != 0 && route[idx][dir_y]>=0) {
aIdx[i] = route[idx][dir_y];
ldir[i] = dir_y;
} else {
rep(d,4){
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
case 'L': goto mode_l;
case 'R': goto mode_r;
case 'J': if (aToggle[i] & 1) goto mode_l; else goto mode_r;
//default: break;
mode_l:
{
int dz[3] = { (ldir[i]+3)%4, ldir[i], (ldir[i]+1)%4 };
rep(j,3){ int d=dz[j];
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
mode_r:
{
int dz[3] = { (ldir[i]+1)%4, ldir[i], (ldir[i]+3)%4 };
rep(j,3){ int d=dz[j];
if (route[idx][d]<0) continue;
aIdx[i] = route[idx][d];
ldir[i] = d;
break;
}
}
break;
}
}
}
}
}
ptrdiff_t myrandom(ptrdiff_t i){ return rand()%i; }
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
int sub()
{
if (++steps >= step_limit) return -2; // ABORT
if (steps % 10000 == 0) { printf("\r[%d] t=%d score=%d ",steps,t,score); fflush(stdout); }
if (score==esamax) {
timebonus = T - t;
if (score+timebonus > hiscore) {
mon(); save();
hiscore = score+timebonus;
steps = -step_limit*3;
printf("t=%d (CLEARED), score=%d+%d/%d (NEW RECORD)\n", t, score,timebonus,hiscore);
}
return -3;
} else if (t==T) {
//printf("!!TIME UP!!\n");
if (score > hiscore) {
timebonus = 0;
mon(); save();
hiscore = score;
steps = -step_limit*3;
printf("t=%d (TIME UP), score=%d/%d (NEW RECORD)\n", t, score,hiscore);
}
return 1;
}
if (hihi[t] <= score) {
hihi[t] = score;
if (t < 0 || 700 < t) {
printf("OUT OF BOUNDS... t=%d\n", t);
return -3;
}
// int j = rand() % 4;
int j = memo_i[t]++ % 4;
if (memo[t][j]) delete memo[t][j];
memo[t][j] = new Frame();
}
// 敵の動きをrollbackする為のもの。当たり判定にも利用
vector<int> aIdx_keep(all(aIdx)), aToggle_keep(all(aToggle)), ldir_keep(all(ldir));
// 先に敵の動きを決めれる
teki();
int safecount=0;
vector<int> tmp1, tmp0;
rep(d,4){
int nextIdx = route[meIdx][d]; if (nextIdx<0) continue; // SAFETY
if (esa[nextIdx]) tmp1.pb(d); else tmp0.pb(d);
}
vector<int> choices;
if (sz(tmp1) > 0) {
random_shuffle(all(tmp1), p_myrandom);
tr(tmp1,it) choices.pb(*it);
if (sz(tmp0)) {
random_shuffle(all(tmp0), p_myrandom);
tr(tmp0,it) choices.pb(*it);
}
choices.pb(4);
} else {
vector<pair<double,int> > cx;
int denom = esamax - score; if (denom == 0) denom = 1;
double dist_here = 0.0;
rep(idx,N) {
if (idx == meIdx) continue;
int d_ = distances[meIdx][idx];
if (esa[idx]) dist_here += 1.0 / d_ / d_; //denom;
}
rep(i,aN){
if (aType[i]!='V' && aType[i]!='H') continue;
int d_ = distances[meIdx][aIdx[i]];
dist_here -= vh_weight / d_ / d_;
}
rep(d,4){
int nextIdx = route[meIdx][d]; if (nextIdx<0) continue; // SAFETY
double dist = 0.0;
rep(idx,N) {
if (idx == nextIdx) continue;
int d_ = distances[nextIdx][idx];
if (esa[idx]) dist += 1.0 / d_ / d_; //denom;
}
rep(i,aN){
if (aType[i]!='V' && aType[i]!='H') continue;
int d_ = distances[nextIdx][aIdx[i]];
dist -= vh_weight / d_ / d_;
}
double dist_score = (dist - dist_here);
if (dist_score > .5) dist_score = .5;
if (esa[nextIdx]) dist_score += 0.75;
dist_score += 0.01 * drand();
cx.pb(make_pair(-dist_score,d));
}
cx.pb(make_pair(1.0, 4));
if (random_mode || (rand() % rand_freq == 0)) {
// cx.pb(make_pair(0.005-.00001*(rand() % 1000), 4));
tr(cx,it) it->first += 0.1 * drand();
}
sort(all(cx));
tr(cx,it) choices.pb(it->second);
}
tr(choices,ct){
int d=*ct;
int lmeIdx = meIdx; // 現時点(lme_x,lme_y)で生きている
if (d<4) meIdx = route[meIdx][d]; // MODIFIED (me_x,me_y)
bool safe=true;
rep(i,aN){
if (coince(lmeIdx, meIdx, aIdx_keep[i], aIdx[i])) { safe=false; break; }
}
if (safe) {
safecount++;
int eaten=0;
if (esa[meIdx]) { score++; eaten=1; esa[meIdx]=0; }
hist[t++] = dirt[d];
int res = sub();
t--;
if (res <= -2) {
return res; // abort
}
if (eaten) { esa[meIdx]=1; score--; }
} else {
;
}
meIdx = lmeIdx; // ROLLBACK (me_x,me_y)
}
if (safecount==0) {
if (score > hiscore) {
mon(); save();
hiscore = score;
printf("t=%d (GAMEOVER), score=%d/%d (higher)\n", t, score,hiscore);
} else {
;
}
}
// 敵の動きをrollback
aIdx.assign(all(aIdx_keep));
aToggle.assign(all(aToggle_keep));
ldir.assign(all(ldir_keep));
return safecount ? safecount : -1;
}
main(int argc, char **argv)
{
if (argc < 4){
printf("usage: %s <map_file> <hi_score> <step_limit> [<rand_freq> <vh_weight%%>]\n", basename(argv[0]));
// map_file には地図ファイルのpathを。(eg. problem/pacman_1)
// hi_score を設定しておくとそれ未満のものを表示しない。最初は0でok
// step_limit は試行打ち切り回数。大体T以上の値を設定。800〜1000とか
// 結果は画面表示だけでなく ans/pacman_1/41.scr のようなファイルにも保存される
return 0;
}
srand( (unsigned)time(NULL) );
if (!load_rawmap(argv[1])) return 0;
frame_for_reset = new Frame();
strcpy(map_name, basename(argv[1]));
hihi.assign(T+1,0); memo_i.assign(T+1,0);
rep(z,701) rep(j,4) memo[z][j] = NULL;
hiscore = atoi(argv[2]); if (hiscore < 0) hiscore = 0;
step_limit = atoi(argv[3]); if (step_limit < 0) step_limit = DEFAULT_STEP_LIMIT;
if (argc >= 5) {
rand_freq = atoi(argv[4]); if (rand_freq < 0) rand_freq = DEFAULT_RAND_FREQ;
}
if (argc >= 6) {
int vh_weight_percent = atoi(argv[5]); vh_weight = 0.01 * vh_weight_percent;
}
for (int trial=0; ;++trial){
steps = 0; // step_limit = 500000;
bool inited=false;
if (trial % 2 == 0) {
int z = rand() % T;
if (2<z && hihi[z]) {
int j = rand() % 4;
if (z < 0 || 700 < z) {
printf("OUT OF BOUNDS... t=%d\n", z);
return -3;
}
if (memo[z][j]) {
memo[z][j]->call(); // resume
inited = true;
}
}
}
if (!inited) {
reset();
hist.resize(T); t=0, score=0, timebonus=0;
}
random_mode = (rand() % rand_freq == 0);
int res = sub();
printf("\r// steps=%d, t=%d, score=%d+%d/%d ", steps,t,score,timebonus,hiscore ); fflush(stdout);
}
// dealloc
rep(z,701) rep(j,4) if (memo[z][j]) delete memo[z][j];
delete frame_for_reset;
}
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100823