fallingblocks.cpp

#include <vector>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <array>
#include <string>

using namespace std;

using Row = array<bool,3>;
using Block = array<Row,3>;
Block get_block(char c){
	switch(c){
		case 'T':
			return Block{Row{1,1,1},
						 Row{0,1,0},
						 Row{0,1,0}};
		case 'X':
			return Block{Row{0,1,0},
						 Row{1,1,1},
						 Row{0,1,0}};	
		case 'R':
			return Block{Row{0,1,1},
						 Row{1,1,0},
						 Row{0,1,0}};
		case 'S':
			return Block{Row{0,1,1},
						 Row{0,1,0},
						 Row{1,1,0}};
		case 'Z':
			return Block{Row{1,1,0},
						 Row{0,1,0},
						 Row{0,1,1}};
		case 'V':
			return Block{Row{1,0,0},
						 Row{1,0,0},
						 Row{1,1,1}};
		case '7':
			return Block{Row{1,1,0},
						 Row{0,1,1},
						 Row{0,1,0}};
		case 'W':
			return Block{Row{1,0,0},
						 Row{1,1,0},
						 Row{0,1,1}};
	}
}
Block rotate(Block in){
	return  Block{Row{in[0][2],in[1][2],in[2][2]},
				  Row{in[0][1],in[1][1],in[2][1]},
				  Row{in[0][0],in[1][0],in[2][0]}};
}
int to_int(Block b){
	int idx = 0;
	int res = 0;
	for(int y = 2; y >= 0; y--){
		for(int x = 0; x < 3; x++){
			res += (int(b[y][x]) << idx);
			idx++;
		}
	}
	return res;
}
int block_int[256][4];
void calc_tables(){
	string chars = "TXRSZV7W";
	for(char c : chars){
		Block b = get_block(c);
		for(int i = 0; i < 4; i++){
			block_int[c][i] = to_int(b);
			b = rotate(b);
		}
	}
}
int place_on_table(int table,int origblock){
	int block = origblock;
	block <<= 21;
	while(block != origblock){
		//cout << block << endl;
		int downblock = block >> 3;
		if (downblock & table){
			break;
		}
		block = downblock;
	}
	int newtable = block | table;
	//cout << newtable;
	int rowscreen = 0x7;
	int bottomscreen = 0;
	for(int i = 0; i < 10; ){
		int antitopscreen = bottomscreen | rowscreen;
		if((rowscreen & newtable) == rowscreen){
			int abv = newtable & (~antitopscreen);
			int bel = newtable & bottomscreen;
			newtable = bel | (abv >> 3);
		}
		else{
			bottomscreen = antitopscreen;
			rowscreen <<= 3;
			i++;
		}
	}
	//cout << ' ' << newtable << endl;
	return newtable;
}
const int maxsize = (1 << 21);
const char PENDING = -1;
using VI = vector<int>;
using VV = vector<VI>;
VV dataarr;
string seq;
const int FOREVVAL = (1 << 30)+1;

int nexti(int i){
	i += 1;
	i %= seq.size();
	return i;
}
bool table_ended(int table){
	return table >= maxsize;
}
int calc_max(int curi,int curtable){
	int & mydata = dataarr[curi][curtable];
	if(mydata == PENDING){
		return FOREVVAL;
	}
	else if(mydata != 0){
		return mydata;
	}
	dataarr[curi][curtable] = PENDING;
	
	int ni = nexti(curi);
	int maxval = 1;
	for(int r = 0; r < 4; r++){
		int block = block_int[seq[curi]][r];
		int newtable = place_on_table(curtable,block);
		if(!table_ended(newtable)){
			maxval = max(maxval,1+calc_max(ni,newtable));
		}
	}
	
	dataarr[curi][curtable] = maxval;
	
	return maxval;
}
int calc(){
	calc_tables();
	dataarr = VV(seq.size(),VI(maxsize,0));
	return calc_max(0,0);
}
bool solve(){
	cin >> seq;
	if(!cin.good()){
		return false;
	}
	int calcres = calc();
	if(calcres >= FOREVVAL){
		cout << "forever\n";
	}
	else{
		cout << calc() << "\n";		
	}
	return true;
}
int main(){
	while(solve());
	return 0;
}