aboutsummaryrefslogtreecommitdiff
path: root/20/day6/grader.cc
diff options
context:
space:
mode:
Diffstat (limited to '20/day6/grader.cc')
-rw-r--r--20/day6/grader.cc467
1 files changed, 467 insertions, 0 deletions
diff --git a/20/day6/grader.cc b/20/day6/grader.cc
new file mode 100644
index 0000000..b1c32c0
--- /dev/null
+++ b/20/day6/grader.cc
@@ -0,0 +1,467 @@
+#include <iostream>
+#include <vector>
+#include <cassert>
+#include <cstdlib>
+#include <set>
+#include <map>
+#include <csignal>
+#include <cstdio>
+#include <fstream>
+#include <cmath>
+#include <sstream>
+#include <functional>
+#include <random>
+#include <tuple>
+#include <deque>
+
+int TRACE = -1;
+
+using ll = long long;
+using namespace std;
+
+ostream& operator<<(ostream& o, const deque<char>& ARRAY) {
+ for(int i=0; i<ARRAY.size(); i++) {
+ o << ARRAY[i];
+ }
+ return o;
+}
+ll r(ll lo, ll hi) {
+ static default_random_engine RNG(0);
+ return uniform_int_distribution<ll>(lo,hi)(RNG);
+}
+
+void fassert(bool b, const string& msg) {
+ if(!b) {
+ cerr << msg << endl;
+ cout << "W" << endl;
+ assert(false);
+ }
+}
+
+// STATE CHARACTER -> NEW_STATE NEW_CHARACTER {L(EFT),R(IGHT),S(TAY),H(ALT)}
+using Cowputer = map<string,map<char,tuple<string,char,char>>>;
+constexpr ll LIMIT = static_cast<ll>(1e6);
+
+set<char> symbols(const Cowputer& M) {
+ set<char> ans;
+ for(auto& kv : M) {
+ for(auto& kv2 : kv.second) {
+ string new_state; char new_char; char action;
+ std::tie(new_state, new_char, action) = kv2.second;
+ ans.insert(kv2.first);
+ ans.insert(new_char);
+ }
+ }
+ return ans;
+}
+
+struct State {
+ State(Cowputer m, deque<char>& START, bool trace_) : RULES(m), ARRAY(START), pos(0), state("0"), time(0), tle(false), trace(trace_) {
+ if(ARRAY.size() == 0) {
+ ARRAY.push_back('X');
+ }
+ }
+ deque<char>& ARRAY;
+ int pos;
+ string state;
+ int time;
+ Cowputer RULES;
+ bool tle;
+
+ bool trace;
+
+ bool run() {
+ if(trace) {
+ cerr << "TRACE: STARTING ARRAY=" << ARRAY << endl;
+ }
+ while(!step(trace)) {}
+ if(trace) {
+ cerr << "TRACE: ENDING ARRAY=" << ARRAY << endl;
+ }
+ return tle;
+ }
+
+ bool step(bool trace) {
+ if(time == LIMIT) {
+ tle = true;
+ return true;
+ }
+ if(trace) { cerr << "TRACE: " << show() << endl; }
+ fassert(0<=pos && pos<ARRAY.size(), "INTERNAL ERROR pos="+std::to_string(pos)+" ARRAY.size="+std::to_string(ARRAY.size()));
+ char seen = ARRAY[pos];
+ fassert(RULES.count(state)==1, "MISSING RULE FOR state="+state+" seen="+std::string(1, seen));
+ fassert(RULES[state].count(seen)==1, "MISSING RULE FOR state="+state+" seen="+std::string(1, seen));
+ string new_state; char new_char; char action;
+ std::tie(new_state, new_char, action) = RULES[state][seen];
+ ARRAY[pos] = new_char;
+ state = new_state;
+ if(action == 'H') {
+ return true;
+ } else if(action == 'L') {
+ pos--;
+ } else if(action == 'R') {
+ pos++;
+ } else {
+ assert(action == 'S');
+ }
+ if(pos == -1) {
+ ARRAY.push_front('X');
+ pos = 0;
+ }
+ if(pos == ARRAY.size()) {
+ ARRAY.push_back('X');
+ }
+ time++;
+ return false;
+ }
+
+ string show() {
+ stringstream o;
+ o << "t=" << time << " state=" << state << " ";
+ for(int i=0; i<ARRAY.size(); i++) {
+ if(i == pos) {
+ o << "[";
+ }
+ o << ARRAY[i];
+ if(i == pos) {
+ o << "]";
+ }
+ }
+ return o.str();
+ }
+};
+
+deque<char> ll_to_array(ll n) {
+ deque<char> ARRAY;
+ ll tmp = n;
+ while(tmp > 0) {
+ ARRAY.push_front(static_cast<char>('0'+(tmp%2)));
+ tmp /= 2;
+ }
+ return ARRAY;
+}
+
+// Trim X off left and right
+string read_array(const deque<char>& ARRAY) {
+ stringstream ans;
+ ll start = 0;
+ while(start<ARRAY.size() && ARRAY[start]=='X') { start++; }
+ ll end = ARRAY.size()-1;
+ while(end>=0 && ARRAY[end]=='X') { end--; }
+ for(ll i=start; i<=end; i++) {
+ ans << ARRAY[i];
+ }
+ return ans.str();
+}
+
+// Reads the first integer in binary on the array
+ll from_binary(const string& S) {
+ ll ans = 0;
+ for(ll i=0; i<S.size(); i++) {
+ if(S[i]=='0') {
+ ans = ans*2;
+ } else if(S[i]=='1') {
+ ans = ans*2+1;
+ } else {
+ fassert(false, "Expected binary answer, got S="+S);
+ }
+ }
+ return ans;
+}
+
+// Times Two
+ll task1(const Cowputer& RULES, bool trace) {
+ for(int t=0; t<100; t++) {
+ ll n = r(1, 1000);
+ deque<char> ARRAY = ll_to_array(n);
+ bool tle = State(RULES, ARRAY, trace).run();
+
+ ll ret = from_binary(read_array(ARRAY));
+ if(tle) {
+ cerr << "TLE TASK 1 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+ return 0;
+ }
+ if(ret != 2*n) {
+ cerr << "WA TASK 1 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+ return 0;
+ }
+ }
+ return 5;
+}
+
+// Add1
+ll task2(const Cowputer& RULES, bool trace) {
+ for(int t=0; t<100; t++) {
+ ll n = r(1, 1000);
+ deque<char> ARRAY = ll_to_array(n);
+ bool tle = State(RULES, ARRAY, trace).run();
+
+ ll ret = from_binary(read_array(ARRAY));
+ if(tle) {
+ cerr << "TLE TASK 2 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+ return 0;
+ }
+ if(ret != n+1) {
+ cerr << "WA TASK 2 n=" << n << " ret=" << ret << " ARRAY=" << ARRAY << endl;
+ return 0;
+ }
+ }
+ return 10;
+}
+
+// Swap - swap every pair of bits
+ll task3(const Cowputer& RULES, bool trace) {
+ for(ll t=0; t<100; t++) {
+ deque<char> ARRAY;
+ ll len = r(1,100)*2;
+ for(ll i=0; i<len; i++) {
+ ARRAY.push_back(r(0,1)==0?'0':'1');
+ }
+ if(trace) {
+ cerr << "STARTING ARRAY: " << ARRAY << endl;
+ }
+
+ deque<char> GOAL;
+ for(ll i=0; i<ARRAY.size(); i+=2) {
+ GOAL.push_back(ARRAY[i+1]);
+ GOAL.push_back(ARRAY[i]);
+ }
+
+ bool tle = State(RULES, ARRAY, trace).run();
+ string GOT = read_array(ARRAY);
+ if(tle) {
+ cerr << "TLE TASK 3 GOAL=" << GOAL << " GOT=" << GOT << endl;
+ return 0;
+ }
+ if(GOT.size() != GOAL.size()) {
+ cerr << "WA TASK 3 GOAL=" << GOAL << " GOT=" << GOT << endl;
+ return 0;
+ }
+ for(ll i=0; i<GOT.size(); i++) {
+ if(GOT[i]!=GOAL[i]) {
+ cerr << "WA TASK 3 GOAL=" << GOAL << " GOT=" << GOT << endl;
+ return 0;
+ }
+ }
+ }
+ return 10;
+}
+
+
+// Reverse
+ll task4(const Cowputer& RULES, bool trace) {
+ for(int t=0; t<100; t++) {
+ ll len = r(1,20);
+ deque<char> ARRAY;
+ for(ll i=0; i<len; i++) {
+ ARRAY.push_back(r(0,1)==0 ? '0' : '1');
+ }
+ if(trace) {
+ cerr << "STARTING ARRAY: " << ARRAY << endl;
+ }
+
+ deque<char> GOAL;
+ for(ll i=0; i<ARRAY.size(); i++) {
+ GOAL.push_front(ARRAY[i]);
+ }
+
+ bool tle = State(RULES, ARRAY, trace).run();
+
+ string GOT = read_array(ARRAY);
+ if(tle) {
+ cerr << "TLE TASK 4 GOAL=" << GOAL << " GOT=" << GOT << endl;
+ return 0;
+ }
+ if(GOT.size() != GOAL.size()) {
+ cerr << "WA TASK 4 GOAL=" << GOAL << " GOT=" << GOT << endl;
+ return 0;
+ }
+ for(ll i=0; i<GOT.size(); i++) {
+ if(GOT[i]!=GOAL[i]) {
+ cerr << "WA TASK 4 GOAL=" << GOAL << " GOT=" << GOT << endl;
+ return 0;
+ }
+ }
+ }
+ return 15;
+}
+
+// Add
+ll task5(const Cowputer& RULES, bool trace) {
+ for(int t=0; t<100; t++) {
+ ll a = r(1,1000);
+ ll b = r(1,1000);
+ deque<char> ARRAY = ll_to_array(a);
+ ARRAY.push_front('S');
+ deque<char> B = ll_to_array(b);
+ ARRAY.push_back('S');
+ for(ll i=0; i<B.size(); i++) {
+ ARRAY.push_back(B[i]);
+ }
+ ARRAY.push_back('S');
+
+ bool tle = State(RULES, ARRAY, trace).run();
+
+ ll c = a+b;
+ ll got = from_binary(read_array(ARRAY));
+ if(tle) {
+ cerr << "TLE TASK 5 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+ return 0;
+ }
+ if(c != got) {
+ cerr << "WA TASK 5 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+ return 0;
+ }
+ }
+ return 20;
+}
+
+// Multiply
+ll task6(const Cowputer& RULES, bool trace) {
+ for(int t=0; t<100; t++) {
+ ll a = r(1,1000);
+ ll b = r(1,1000);
+ deque<char> ARRAY = ll_to_array(a);
+ ARRAY.push_front('S');
+ deque<char> B = ll_to_array(b);
+ ARRAY.push_back('S');
+ for(ll i=0; i<B.size(); i++) {
+ ARRAY.push_back(B[i]);
+ }
+ ARRAY.push_back('S');
+
+ bool tle = State(RULES, ARRAY, trace).run();
+
+ ll c = a*b;
+ ll got = from_binary(read_array(ARRAY));
+ if(tle) {
+ cerr << "TLE TASK 6 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+ return 0;
+ }
+ if(c != got) {
+ cerr << "WA TASK 6 a=" << a << " b=" << b << " expected=" << c << " got=" << got << endl;
+ return 0;
+ }
+ }
+ return 35;
+}
+
+ll task7(const Cowputer& RULES, bool trace) {
+ if(RULES.size() > 5) {
+ cerr << "Only 5 states are allowed for task 7" << endl;
+ return 0;
+ }
+ set<char> syms = symbols(RULES);
+ if(syms.size() > 3) {
+ cerr << "Only 3 characters allowed for task 7" << endl;
+ }
+
+ deque<char> ARRAY;
+ State START(RULES,ARRAY,trace);
+ bool tle = START.run();
+ if(tle) {
+ cerr << "TLE TASK 7" << endl;
+ return 0;
+ }
+ ll score = START.time;
+ if(trace) {
+ cerr << "TASK 7: TOOK " << score << " steps" << endl;
+ }
+ if(score >= 10000) {
+ return 5;
+ } else if(score >= 1000) {
+ return 4;
+ } else if(score >= 500) {
+ return 3;
+ } else if(score >= 100) {
+ return 2;
+ } else if(score >= 20) {
+ return 1;
+ } else {
+ return 0;
+ }
+}
+
+int main() {
+ ifstream in;
+ in.open("output");
+ if (!in) {
+ cerr << "No \"output\" file" << endl;
+ cout << "W" << endl;
+ exit(0);
+ }
+ using Checker = std::function<ll(const Cowputer&,bool)>;
+ vector<Checker> TASKS{
+ {task1},
+ {task2},
+ {task3},
+ {task4},
+ {task5},
+ {task6},
+ {task7},
+ };
+
+ map<ll,Cowputer> MS;
+ Cowputer RULES;
+ ll task = -1;
+ while(!in.eof()) {
+ string line;
+ getline(in, line);
+ string PREFIX = "# TASK";
+ if(line.find(PREFIX)==0) {
+ stringstream ss(line);
+ if(task != -1) {
+ fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task));
+ MS[task] = RULES;
+ RULES.clear();
+ }
+ string hash; string label; ll new_task;
+ ss >> hash >> label >> new_task;
+ fassert(hash == "#", "TASK LINE must start with '# TASK' line="+line);
+ fassert(label == "TASK", "TASK LINE must start with '# TASK' line="+line);
+ fassert(1<=new_task && new_task<=TASKS.size(), "Unknown TASK="+std::to_string(new_task));
+ task = new_task-1;
+ }
+ bool isempty = true;
+ for(ll i=0; i<line.size(); i++) {
+ if(!isspace(line[i])) {
+ isempty = false;
+ }
+ }
+ if(isempty || line[0]=='#') { continue; }
+ fassert(task!=-1, "Must have '# TASK' line before any rules task="+std::to_string(task));
+
+ stringstream ss(line);
+ string state; char seen; string arrow; string new_state; char write; char action;
+ ss >> state >> seen >> arrow >> new_state >> write >> action;
+ fassert(('A'<=seen && seen<='Z') || ('a'<=seen && seen<='z') || ('0'<=seen && seen<='9'), "SYMBOL must be alphanumeric got="+std::string(1,seen));
+ fassert(('A'<=write && write<='Z') || ('a'<=write && write<='z') || ('0'<=write && write<='9'), "new SYMBOL must be alphanumeric got="+std::string(1,write));
+ fassert(arrow == "->", "BAD ARROW line="+line+" arrow=" + arrow);
+ assert(arrow == "->");
+ if(RULES.count(state)==0) {
+ RULES[state] = map<char,tuple<string,char,char>>{};
+ }
+ fassert(set<char>{'L', 'R', 'S', 'H'}.count(action)==1, "Action must be one of L(EFT) R(IGHT) S(TAY) H(ALT) got="+std::to_string(action));
+ fassert(RULES[state].count(seen)==0, "Duplicate rule detected state="+state+" char="+std::string(1, seen));
+ RULES[state][seen] = make_tuple(new_state, write, action);
+ }
+ if(task != -1) {
+ fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task));
+ MS[task] = RULES;
+ }
+
+ ll score = 0;
+ for(auto& kv : MS) {
+ ll task; Cowputer M;
+ std::tie(task, M) = kv;
+ if(M.size() > 1000) {
+ cerr << "You used more than 1000 internal states for task=" << task << endl;
+ continue;
+ }
+ Checker check = TASKS[task];
+ ll points = check(M, TRACE==task+1);
+ score += points;
+ cerr << "Task " << (task+1) << ": " << points << endl;
+ }
+ cout << score << endl;
+}
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2024-12-22 23:58:42 +0000