light
27 solved.
Loading data by Light.exe, and enjoy it. you will get the flag if all blocks become green. Please submit the flag like RCTF{flag}.
The RCTF 2017 end a week,but nobody share the solution.in this holliday i really have time to do some research.this game is the famous lightoff game,but different from the standard game.
In standard game,when touch one light,it will affect 5 lights, as you see,this challenge affect 8 lights at most,so the coefficient of the matrix is different from the standard.
the challenge's matrix is 128*128,so it's impossible to brute force it. we can make a matrix equation,and use gaussian elimination to slove it.
#include "stdio.h"
#include <iostream>
using namespace std;
#define N 128
#define M N*N
int pt_to_index(int x,int y)
{
if(x<0)
{
return -1;
}
return x*N+y;
}
void reset(int* m1,int x,int y)
{
if(x<0 || y>N-1 || x > N-1 || y < 0)
{
return ;
}
int pt = pt_to_index(x,y);
if(pt < 0)
return ;
//printf("reset(%d,%d)\n",x,y);
int v = m1[pt];
int d= v==1?0 :1;
m1[pt] = d;
}
void index_to_pt(int pt,int* x,int*y)
{
*x =pt/N;
*y =pt%N;
}
void build_matrix(int** m1, unsigned char* data)
{
int x,y;
for(int i = 0 ; i < M; i++)
{
index_to_pt(i,&x,&y);
reset(m1[i],x-2,y);
reset(m1[i],x-1,y-1);
reset(m1[i],x-1,y+1);
reset(m1[i],x,y-2);
reset(m1[i],x,y+2);
reset(m1[i],x+1,y-1);
reset(m1[i],x+1,y+1);
reset(m1[i],x+2,y);
}
for(int i = 0 ; i < M; i++)
{
m1[i][M] = data[i];
}
}
void slove(int** matrix) //高斯消元
{
int *solution = new int[M];
int i,j,k,x,y=0,rand_coefficient,rand_matrix,rank1,rank2,inc=0;
for(k=0; k< M && y<M; k++,y++) //增广矩阵转换为阶梯矩阵
{
x=k;
for(i=k+1; i< M; i++)
if(matrix[i][y]>matrix[x][y])
x=i;
if(x-k) //交换矩阵行数据
for(j=y; j< M+1; j++)
{
matrix[k][j]=matrix[k][j]^matrix[x][j];
matrix[x][j]=matrix[k][j]^matrix[x][j];
matrix[k][j]=matrix[k][j]^matrix[x][j];
}
if(matrix[k][y]==0)
{
k--;
continue;
}
for(i=k+1; i< M; i++) //消元
if(matrix[i][y])
for(j=y; j<M+1; j++)
matrix[i][j]^=matrix[k][j];
}
for(rand_coefficient=rand_matrix=i=0; i< M; i++) //计算系数矩阵的秩和增广矩阵的秩
{
for(rank1=rank2=j=0; j<= M; j++)
{
if( j< M)rank1|=matrix[i][j];
rank2|=matrix[i][j];
}
rand_coefficient+=rank1;
rand_matrix+=rank2;
}
if(rand_coefficient<rand_matrix) //系数矩阵秩小于增广矩阵秩，局面无解
cout<<"no solution!\n\n";
else //枚举并回代求解
{
for(k=1<<(M-rand_coefficient); k>0; k--)
{
for(i=M-1; i>rand_coefficient; i--)
{
matrix[i-1][M]+=matrix[i][M]>>1;
matrix[i][M]&=1;
}
for(i= 0; i< M; i++)
solution[i]=matrix[i][M];
for(i= M-1; i>= 0; i--) //回代
for(j=i-1; j>=0; j--)
if(matrix[j][i])
solution[j]^=solution[i];
for(i=0; i< M; i++) //输出答案
(i%N)?cout<<solution[i]<<",":cout<<endl<<solution[i]<<",";
inc++;
printf("\n");
matrix[M-1][M]++;
break;
}
cout<<"\ntotal "<<inc<<"\n";
}
delete [] solution;
}
int main(int argc,char* argv[])
{
FILE* fd =fopen(argv[1],"rb");
if(fd == 0 )
return 0;
unsigned char* buf = new unsigned char[128*128+8];
fread(buf,1,128*128+8,fd);
fclose(fd);
clock_t t1=clock();
int** m1 = new int*[M];
for(int i =0;i < M;i++)
m1[i] = new int[M+1];
build_matrix(m1,&buf[8]);
slove(m1);
clock_t t2=clock();
cout<<"TotalTime:"<<(t2-t1)/CLOCKS_PER_SEC<<"s"<<endl;
delete [] m1;
delete [] buf;
return 0;
}it take me 30s to get the solution matrix on my laptop.
00011101110100011001010111001100001110101100111000111000011100000001110110000100010011111010101001111111111100111111011100011111
10001001000111101010010001110011001110111110010010101010100111101011101010001110001000011111000100100101011000000100010110000101
00110001101001000001010101001111011001011110111011011111010110011000010010110000010000011001001010001111111100011000011110001000
11010111101001001101011100000010011000001010001101010000010011001101111000100010011101000111101000011010100100011110000100000101
10101011110100000110111000101010010011011111001010011111110000111011100111001010110001010111010010100001011000000001111001111011
10010010101111010011111001011101011100100110001110011000101000100101110101110001010100110100100101000010100101100000000011000010
01000001000100011111101010101111111001000101100111001100110000010110011111111111000100000001000100101110001111010101011101000100
01000001001101111111110000010010010011011000000111111000010110111010110111110110011110111110100101001010011011111101000101011101
01010100000110001001011001110011000100100010011101110100001010010101011011101100011111011110101011010101001111100100101111001001
11001010110110100011111001010101110100101111000100000011111100101001010010011110001111110011001001001011001001111010000010000001
01001110111000110011010101101101110100010000110001011110010010010110001011110110011010011110101001011011000001110010001100000101
00001101010111001000111000010010100010001110001001101000001011011110001101000000001001001111010001011111000011101001010010001011
00101101010011100011101111010110100100111110100011011100100101110110010001100011110001000010010110110000000110110010101111111010
10111011110000111100000111110000111000001110000000010100000010110011110100101011101011111011011001000101011101110111110111000000
10101001011011001000010000010011011101110101011000010011001101111111110011010100100100100011100011110111000001011101001100011111
11011011011010101100101101011001100001110111010001110010001000001100000010001100001111110000001011101110110010110101100101001011
01100101110101110001110111000100111111100001100001011110001000001100100100111000001110001110010101100000111010010010001101110111
11011110011010000010011100110010011000101100110110001101100001000111101110011101110001101100011011111010000001010100000011101110
01101001111111110100000001000000010010001010000000001101011111111000100100100001110110100111100110001110110110011011101001000010
01001010011110101011111111111011000111110111110111000001100100101110011010101010011001110001011111100110011011011101010111000111
01010111010010010010011110001000101100000000000101110110100010010000100101000011010100011011101111011101100101010101100111010000
00100001101110010011001001011010100001010001000011000101101101000100010100001111010010000001000010110110011000110000101110001011
00110100100101100010101100110100011000100101101111001000000001100110000000010010100010110101111000011010101111010111001001000101
00010001111000010010101001110000011000101000101001111100110100001110011010000000110001110100100001110011011110001110111101011010
01011011011010010111000001010011000011000110011101101011101001111110011101101001110111111001111010001001000000100001000101011101
10110101110001110000100110010010001000111000000100111101110110101010110001000101110010011101000010001101100001101101000110110101
00011101011100101010110101010000110110000001110001010110100011110011011110001101010000101101000000000100001011000101011101001100
00001111001001101111101011000011101100011010000001100101111101111010111011001100000001100010001000000011100100101011110101101001
10000101111110000110111011010111001111011111010101011110001100111010010111000001000011010111010100101011100001001011111001000110
01110011001011001111000000001011101111100110111110001001101100101110011100010111101010010001001111010100101000010000101101111000
01011101000110111110011111101000001110010100101001111110110100010100000111010000110111011010010000101111011110011110011011011110
10100101111111110111110101110101000101010110111010101100010111000110110001111010100000011100000100000010110000100111001101100111
10101110110111111101001011111101000010110101111111001010101101010101010011010100010000101000111011011001100100011000001110111101
11110000011110011011111000010001000011101000110000100100010100011001000011101110110001100110000010011111010111110000100001100001
00001100100011011101010110111011111100010110000101000100011011001011011101000001111110001110000010101110010100101110110100100101
01110100011010001001000010101001000110110000101110110001110111110111110000110010110110101101011111100110011010110100011001101011
00101110110100100000011000010011111000001110000110001001110101111011100010111010111001010111111101100010011001101100010101011000
00111101000011100100101000010110010101110111100000100001111010011111101100011010101001010000011100010010001011111111010010001111
01001111001110000010111000110011111011010000011110110000011011010001101011011100111001000111100100100101100100100011100000001000
11011011010010010010010111100001110101011110111000000111111000100100010001111011000000110000100010100110101011100110110101101011
01010111001110100011010001111100100111101111100000111111100000011010110000000011010010000010111101000000111110110100001001100011
10101110100111100101001000011001100101111111110111001010010001100001101100011100110011101001101110110111101110111011110100110000
10111011010000011000000011000110010011001111010101110011111100010101111001010001111101010001001000000010010011111110011001110111
01010101011101100111001101110100110111010110001011100000001100011001110000111100011010101001010001110101111011001011111010111000
11010000111001000011101111000010101100100111100101001011000010101101100101101100010111111110011011110011111110110000011001001101
00111001011011011111110111110011010001011011111010111010011110100101111111011111100000001010000000011011111000100100101101010101
01001111101110110101111100011111010000111001100001101000001110001001000100100010110100110000100011001110110101001011011000100101
11001010110011011101100000001100110011000011010110100110001111011111011110011101011110011010101101011101101100010010000001101000
01000110010111010111011101101000010101100001000101011110101010100100010110110110000111101101100000100110001100000011110111110011
10101011000101101111010111110010110010110110101010000010110011000111010110011000101001011011110001010001011111000111011011101001
11000100001111000110111111001000010110110011001100011001001110001101111111000011010001101100110010010001011100010010011000110100
11110111110110000100110011011000001011000011011011001110100110001101000100010000100110011010010011001100000101010010011010100110
10010111100101100101101010010010110000010000010010001011000000000111110111101101100100101101100100110000001011001101000010111001
00111010110111100011101101011110001001111001011110100110000100110110011111001000111111010001110101110000111100101101001001001011
11000000001000001011110110001100101111001111010101011000011001011000111110000001111011010011001011010100010000101100110010101010
11110111101011011110001001001101001100000100111110011101001011011100001110000111101111000100001000011101111011100110000110010000
01111001111010100100101001010011010000110001010010111101000010001011100101110010011010111001100110010000110100101001000101011101
01111110110110000011100011001111100001001010000010101100000110100000011100000010101101011101011011111111111010001000110110111110
11010100011010001100001011001011111101101101001111110011000010010100011001010001111100011101100001011111011000110000101001010000
11010110110110111100000011001111011000010100000111101001100101101000101011000010010001100011101110011100100110101011001001010011
00100000000111100011011010100010110000100111100010000000101010101011000011010011010110100110100010010100001111001101111110000110
01110100011100011001000110100110011010111001111000100010010000000101111000011010000010111110001010010000011010001000010000000110
00100001001101010001111100111111100101101110001001011000000111100011101101010011100001000110111010100101100000000100000001001011
00100000001000111001010111010100001111100111101010001110001110100001001011000111011100110110001010001001110001010011100001110110
00010101111001110010001001100010101101011010110001001001011001011001000100010111100110110100100100100100011010010111110110110110
11001101011101110110011110110001111011100000110010100101001111001101101110100101001001111101100101101010100111100111001000011111
01011101111100110101010100010101000001101111101100110101000101100011111100001011110010000111100000100110110110110010111111110111
11110001010000011100110100110101100101000111000111111001101111111110001101001010111011011011000010001100100101000100100001010010
10001111000101110010111000000001001001001001100010110100011011011110110100110101100000000101000011110101101101000111111010101010
00011001101100010010000011100100000010101101101010001011000110011011111001101110011101101000010101001000000001100101010000111101
11110000011100100100001001010000011000010100111110100100000100110011111111000100111010100000011110101001011110000111111100001100
00010011010011101010100111000001111001110111001010001100001101000001110101000100010000111000001111110010110011011110000111110010
11111111010100101010101111101011110001010111101000101010100000011011011110001100100010011111100000101111010001000011111010111100
00101001101010001001010000111101011100010011100111100010101111111001000011001001001011110000111101001000000000100101000011101111
01100011100000011110011101101100110000110010110010100100000100010011111011011101001000101111001010001111001000001100100111001000
11100101111001010010010100010101111110001101001111100111010010111101011111011110011000101100000001000111010010110101111100011100
01110101110101111110100100010111011111100101011100110101000001011011110111011010011101010101001001110101100100010101001010110000
01111001110101111011001100111110101101001110001000110000101000011110001110111001011100111001011011101000100100001011001110101101
01111100010001011111010101011100011101111111110110011111111001000110010001110001110101001110101011100010100000001011100101011101
10111001010011111110011101111111111100001110011001010111100101110111010000010010001110001011001110111001001011011010001100010111
10011010101011000100010011000001011111000011010110110101001111110111110101010011111001010000010111000001100111101010100001100111
11001100110000111010001110000010111111011000111001001111010000011011111010110111010111001110011011110110011110111111110110011110
01100110111001001000000101101000001100110101111001100100001000011011101101001111011011111011000000100000100001101111000101001111
10100000000110011101001100000000010101010011000111100000001111101111001110100100110111100111101011001010011110011000100001100010
01010011000101101100111100010010100110111000001011111010110101000011110111101010111011100001101011011001010010110001100101011110
10010111011000100010010100011110010111100100011111111110101011101010011100001101101101101001010000101000000110011101111100101011
11101001111101011010001011010001011000000001001110101001001010000100100001001000000001000110000001010101000010100010011010100000
01010010001011000101111111001001100111001010101000100010111101100010111000111111101111101000101011101000011111110010100011001010
00000001001101011001010001100101111110110101111100100000001001001010010011000110011011010101111101010110100100100001100111110000
10000111101101111000011011010011000110000001110100111100011100001100111001010001111001100011111111110110011110100111110000000101
01010110010100000110011010111011111000100111101101111101000001111111010100110101000110010010011111100000101100000001010010101101
00000001111110001001010000101010011000011110101000001100110011001100001110011001000110010101011111010010000101101001011011001000
11101001000111100001001100111010011100010100001010011101001110110111001011100111111100001100100001001101101100010001101111000000
10101110011110010011100100001101010001101110100110110110010101110010011011000101001001001011110100011100011011100110001111001100
10111110110000001111111100100001010111011110101010101101100111000000100001100000010001111000101100001111101010000101110100011001
11001110100110100000010010001111110000111011111001011110101011100011100101010011010011001011000101011111011001000010000110011101
00001110101011111001011000100110001110001001100000000011101010011001101010111011111000101010101100000001101011100011110010010101
00101111001111101100110001001110100100111100000110111010110110111110110111101101000101110111100110110111111010111011101101111001
01111000101010101000111010001000011110010011110001110100000001100110111000000110010110110100011110001101111101001011001011000010
10100010101010001011001000101101010010011101101001101111010110101000100100000101100101101101011100110100110100100110010110110001
00111011110001111110000111111010001100101110000101100010010100101000010000011011001100101110001010011101110110110101011001011000
01010010100000101001101110010100011011011000001110100101110111011110011010000111010010100001111011011000010101111000111010010001
10111001110000101010100111001101100100011110000111001110111101100011111010101000011000101101010001000110111111110100111001100100
11111011010100110000000111111010101000011111110011101000111011001101010000010100111010011011100111011011100100101010100001110111
01100011001110111011011010001001100010011100101010011010111000011011110100100001000010110100100000101111000110110010101001001001
00111110111100010011000000110100010010000000001100101110011111111010101100011010101000111000110101111001001000111110010101001000
01011000000101110100000000000001010101000000100110000110000011000011111010000001111111010101011011111001111110111011000111111011
11101000110100111010101001110001111110010010000100100000010001001110010111101100111111011101111100111110101011111101100001101000
10100010110110100010101001011001001101001101010010000111000110101011110111111100011111000110110000000000100110110010111101001100
10001111001101010001100110001000010001101101111011101101000000110011101101011100101110101000001100111110100110100110001000100001
11011010111110111010100101110011110011100110010100001101000101000110010011110000101110011110000100111001010101011100110011110011
10010001000010100101010111000011010001100100100000010100110100110010100100101010110100101110100110000010010010100000100011100000
00101011100110111000100000011101010100110011001011011100110001001000100111011011100010100010110000010000001010100111010110111111
00110100101100000100100001111010001110101010011110110001100110110010110110010111010011111010111011011010101001010101111110100111
10010001100110111011100001000101000010110011101011011100000010110101000001001101110010010100110110000011001000000001101010000100
01011100000001010110000001110001111100010000100110010110001110111010101110010101011010000001011001100001100110100010101001100011
01010001000110100011101001000101110110110110111001001101011101100001100011101111111111010000100011100110011010100000011011110001
10011000011100010111010111010100010001101000100011111110010010010111111111111000001010001010011001010000110001011010011011000101
11000101101011011000001011111110111110011010000110000010000101100101000101100011011011011100111001100100101010100000011000111110
01001001011100101001000010010010111111010100000111010000101011100110000001001110001111011111010000110000101100101111101111111010
10011110000011111011100111110000010111110001100101100010100010100001100101101101111110010011000100011110110010111101010100110000
00101000001110101100011110110110100010100111111000010111010101010011111001101011011101011110101110100111111111000001001011101101
01111011010001111110101101000011100101111100001011001101010011111100010110101001000000010101111001000010001001110110111101101111
11100010111110111010011101000010011010010110010010011010010101100000001010010101101000011110000011001000001001111101111111110111
11000000000001000000010011011000000111010011011000010100011111110111111111010001110101011111101000101010001000100101100010001001
00101011000001101100010100111000001010000101101111101111101000011100010111110000010111111010100101111100111001110101110111010000
10111000010100010010001100110000000111011010101110001001111100111111010000110010111001100011111101101110110100011100110101010011
00111111000010111101100100011100011111000010110000111111110110110110100110101101001101110011100100111100010001000010010000100100
when you get the solution of the matrix,you can use FindWindow and SendMessage to turn all the lights green,and it will popup the flag window.
finally,the flag should be RCTF{Gaussian_elimination_ks_awesome!},i have not test, because the game is over!
reference:关灯游戏 Lights out (三)(线性代数+高斯消元，搜索全部解)