競技プログラミング向けテスタ
なんかそのうちライブラリとかにうつしたい。
ソースの名前はmain.cppを仮定
Makefile
CPP = clang++ CPP_FILE = main.cpp TEST_SH = ./test.sh CFLAGS = -O2 -std=c++11 -Wall PROGRAM = ./main all: $(PROGRAM) $(PROGRAM):$(CPP_FILE) $(CPP) $(CFLAGS) $(CPP_FILE) -o $(PROGRAM) PHONY: check-syntax test check-syntax: $(CPP) -fsyntax-only $(CFLAGS) $(CHK_SOURCES) test:$(PROGRAM) $(TEST_SH) $(PROGRAM)
test.sh
#!/bin/sh # put test.sh ,input files and output files in the same folder. # $ ls # test.sh main.cpp 1.in 1.out 2.in 2.out INPUTS=`find . -type f -name "*.in" | sort` PROG=$1 if [ $# -eq 0 ] then echo "Pass program as first argument." echo "ex: ./test.sh ./a.out" exit 1 fi cnt=0 suc=0 for input in $INPUTS do cnt=`expr $cnt + 1` body=${input%.*} output=$body.out echo "$input - $output" if [ -e $output ] then tmp=`mktemp` $PROG < $input > $tmp d=`diff $output $tmp -Z` if [ ${#d} -eq 0 ] then echo -e "\033[0;32mCorrect\033[0;39m" suc=`expr $suc + 1` else echo -e "\033[0;31mFailed\033[0;39m" echo "Expected:" cat $output echo "Output:" cat $tmp fi rm $tmp else echo -e "\033[0;31mFailed <- $output not found\033[0;39m" fi done if [ $cnt -eq $suc ] then echo -e "\033[0;32mAll test Passed!!\033[0;39m" else echo -e "\033[0;31mSome test failed.("`expr $cnt - $suc`"/$cnt)\033[0;39m" fi
音を使ったデバッグ
というのもあるのかなぁという妄想をした。 こう、HDDがカリカリなってたら、なんかヤバいとかそんな感じ。 まぁ、新規性もないようなので、
Linuxだと、mpg123とか、aplayを使うのが手頃だと思われる。例えば
#include <iostream> #include <string> #include <cstdlib> // run on linux. void play_mp3(const std::string &path){ std::string command = "mpg123 -q " + path; system(command.c_str()); } int main(int argc,char **argv){ play_mp3("~/Dropbox/codes/kc_downloader/voice/236/2.mp3"); // something heavy here. int n = 100000000; int s = 0; for(int i=0;i<n;i++){ s += i; } play_mp3("~/Dropbox/codes/kc_downloader/voice/236/4.mp3"); return 0; }
こんな感じ。 もうこの手法に新規性はないけど、これを新しい方向性で使うことができれば、新規性もあるのかもしれないなぁ。 (例えば、録音しておいて、後で再生できるようにするとかね)
予測型構文解析で記述できるかどうかを判定する
タイガーブックのをC++で実装してみた。 ちゃんとできてるんかな……。
#include <iostream> #include <vector> #include <set> #include <map> using namespace std; struct Rule{ char from; vector<char> to; Rule(char from_,vector<char> to_) : from(from_),to(to_){ } }; bool operator==(const Rule& lhs, const Rule& rhs){ if(lhs.from != rhs.from or lhs.to.size() != rhs.to.size()){ return false; } for(size_t i=0;i<lhs.to.size();i++){ if(lhs.to[i] != rhs.to[i]){ return false; } } return true; } bool operator<(const Rule& lhs, const Rule& rhs){ if(lhs.from != rhs.from){ return lhs.from < rhs.from; } if(lhs.to.size() != rhs.to.size()){ return lhs.to.size() < rhs.to.size(); } for(size_t i=0;i<lhs.to.size();i++){ if(lhs.to[i] != rhs.to[i]){ return lhs.to[i] < rhs.to[i]; } } return false; } bool operator>(const Rule& lhs, const Rule& rhs){ return not(lhs == rhs) and not(lhs < rhs); } ostream& operator<<(ostream& os,Rule r){ os << r.from << "->"; for(char c : r.to){ os << " " << c; } return os; } template<typename T> ostream& operator<<(ostream& os,set<T> s){ os << "{"; for(T v : s){ os << v << ","; } os << "}"; return os; } // can be written in recursive descent parsing? // see tiger book(p.46). bool can_be_written_in_recursive_descent_parsing(const set<char>& terminal, const set<char>& non_terminal, const vector<Rule>& rules){ for(Rule r : rules){ cerr << r << endl; } map<char,bool> nullable; map<char,set<char>> first,follow; for(char c : non_terminal){ nullable[c] = false; first[c] = {}; follow[c] = {}; } for(char c : terminal){ nullable[c] = false; first[c] = {c}; follow = {}; } { bool changed; do{ changed = false; for(Rule r : rules){ bool all_nullable = true; for(char t : r.to){ all_nullable = all_nullable and nullable[t]; } if(all_nullable and not nullable[r.from]){ nullable[r.from] = true; changed = true; } for(size_t i=0;i<r.to.size();i++){ bool nul = true; for(size_t k=0;k<i;k++){ nul = nul and nullable[r.to[k]]; } if(nul){ size_t bef = first[r.from].size(); first[r.from].insert(first[r.to[i]].begin(), first[r.to[i]].end()); changed = changed or (bef != first[r.from].size()); } } for(size_t i=0;i<r.to.size();i++){ // nullable[y[k]] for k <- [i+1,] bool nul = true; for(int k=i+1;k<(int)r.to.size();k++){ nul = nul and nullable[r.to[k]]; } if(nul){ size_t bef = follow[r.to[i]].size(); follow[r.to[i]].insert(follow[r.from].begin(), follow[r.from].end()); changed = changed or (bef != follow[r.to[i]].size()); } } for(size_t i=0;i<r.to.size();i++){ for(size_t j=i+1;j<r.to.size();j++){ // nullable[y[k]] for k <- [i+1,j-1] bool nul = true; for(size_t k=i+1;k<j;k++){ nul = nul and nullable[r.to[k]]; } if(nul){ size_t bef = follow[r.to[i]].size(); follow[r.to[i]].insert(first[r.to[j]].begin(), first[r.to[j]].end()); changed = changed or (bef != follow[r.to[i]].size()); } } } } }while(changed); } for(char c : non_terminal){ cerr << c << endl << "nullable? " << nullable[c] << endl << "first " << first[c] << endl << "follow " << follow[c] << endl; } map<char,map<char,set<Rule>>> maps; for(Rule r : rules){ // check r.to is nullable or not. // and collect first. set<char> to_first; bool to_nullable = true; for(char t : r.to){ to_first.insert(first[t].begin(),first[t].end()); to_nullable = to_nullable and nullable[t]; if(not to_nullable) break; } for(char tf : to_first){ maps[r.from][tf].insert(r); } if(to_nullable){ for(char t : follow[r.from]){ maps[r.from][t].insert(r); } } } cerr << "Map" << endl; bool dup = false; for(const pair<char,map<char,set<Rule>>> m : maps){ int from = m.first; for(const pair<char,set<Rule>> p : m.second){ int to = p.first; cerr << char(from) << " " << char(to) << " " << p.second << endl; dup = dup or p.second.size() > 1; } } return not dup; } int main(){ set<char> terminal; set<char> non_terminal; { // terminal; int n;cin >> n; for(int i=0;i<n;i++){ char c;cin >> c; terminal.insert(c); } } { // non_terminal; int n;cin >> n; for(int i=0;i<n;i++){ char c;cin >> c; non_terminal.insert(c); } } // number of rule. int n; cin >> n; vector<Rule> rules; for(int i=0;i<n;i++){ int k;cin >> k; char from;cin >> from; vector<char> to(k); for(int j=0;j<k;j++){ cin >> to[j]; } rules.push_back(Rule(from,to)); } cout << can_be_written_in_recursive_descent_parsing(terminal,non_terminal,rules) << endl; return 0; } // 9 // 9 // 3 // $ + - * / i n ( ) // $ + - * / i n ( ) // a c d // 3 // 6 // 3 // S E T // S E T D U F // X Y Z // 10 // 12 // 6 // 2 S E $ // 2 S E $ // 1 X Y // 3 E E p T // 2 E T D // 1 X a // 3 E E m T // 3 D + T D // 0 Y // 1 E T // 3 D - T D // 1 Y c // 3 T T * F // 0 D // 1 Z d // 3 T T / F // 2 T F U // 3 Z X Y Z // 1 T F // 3 U * F U // -> 0 // 1 F i // 3 U / F U // 1 F n // 0 U // 3 F ( E ) // 1 F i // -> 0 // 1 F n // 3 F ( E ) // -> 1
POJ 3662 Telephone Lines
解を二分探索 + ダイクストラ
// compile in C++11. use -std=c++11. #include <iostream> #include <iomanip> #include <vector> #include <valarray> #include <map> #include <set> #include <list> #include <queue> #include <stack> #include <bitset> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <complex> #include <string> #include <sstream> #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> using namespace std; #define all(c) c.begin(),c.end() #define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++) #define debug(x) #x << "=" << (x) #define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl struct Edge{ int to,cost; Edge(int to_,int cost_) : to(to_),cost(cost_) { } }; int mydijkstra(const int start,const int goal,const int u, const vector<vector<Edge> > &graph){ typedef pair<int,int> pii; int N = graph.size(); vector<char> visited(N,false); // cost where priority_queue<pii,vector<pii>,greater<pii> > que; que.push(make_pair(0,start)); while(not que.empty()){ int cost,where; cost = que.top().first; where = que.top().second; que.pop(); if(visited[where]) continue; if(where == goal) return cost; visited[where] = true; for(int j=0;j<(int)graph[where].size();j++){ if(graph[where][j].cost <= u){ que.push(make_pair(cost,graph[where][j].to)); }else{ que.push(make_pair(1+cost,graph[where][j].to)); } } } return -1; } int solve(const int N,const int P,const int K, const vector<int> &A, const vector<int> &B, const vector<int> &L){ const int INF = 1000001; int lower = 0; int upper = INF; // いくら払うかで二分探索。 // K本ただで貰える。 -> K+1本目の枝 vector<vector<Edge> > graph(N); repeat(i,P){ graph[A[i]].push_back(Edge(B[i],L[i])); graph[B[i]].push_back(Edge(A[i],L[i])); } repeat(bin_search,20){ int mid = (lower+upper)/2; int d = mydijkstra(0,N-1,mid,graph); // ok if(0 <= d and d <= K){ upper = mid; }else{ lower = mid; } } if(upper >= INF) return -1; return upper; } int main(){ int N,P,K; cin >> N >> P >> K; vector<int> A(P),B(P),L(P); repeat(i,P){ scanf("%d %d %d",&A[i],&B[i],&L[i]); A[i]--; B[i]--; } cout << solve(N,P,K,A,B,L) << endl; return 0; }
linuxでニコニコ生放送をする。
これだけ。 他の記事のを色々試したが、すべてうまくいかなかった。
#!/bin/sh # https://trac.ffmpeg.org/wiki/StreamingGuide ffmpeg -f x11grab -s 1440x900 -r 15 -i :0.0 -f alsa -ac 2 -i default \ -c:v libx264 -preset fast -pix_fmt yuv420p -s 1440x900 -c:a libmp3lame \ -ab 96k -ar 22050 -threads 0 -f flv "$1/$2"
今年
去年書いた、「来年やること」はまったく達成されませんでした。 ただまぁ、20歳になったときの黄色コーダーになる、っていうのは達成された模様です。
マジ、今年は何もやってない。 来年から本気だす。
