Posted on by and filed under BaltCTF 2013.

If you ncat into the server for this challenge, you’re given instructions on how to play a game. This game is a direct copy of lights out, a computer science challenge. You can provide a series of coordinates to toggle, and this will toggle all of the adjacent cells. The goal is to have the entire board on or off. For this, we contacted the UCF Programming Team, and Antony quickly pumped out a Java solver. I wrapped this in python and we let it run, after ~100? times it gave us the flag. Our source code is below:
import socket
import re
import os
 
# Handle connection
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("194.106.195.60", 9502))
 
# Log everything to a file
def logdat(stuff):
    tempf = open("maplog.txt" % (mapcount), 'a')
    tempf.write(stuff)
 
# Dump the map to a text file and run the compiled java class from earlier
def gomap(mapstr):
    f = open('map.txt', 'w')
    f.write(mapstr)
    f.close()
    
    print "running generator"
    os.system("java pluses")
 
    print "sending shortest path"
    shortestpath = open('map.out', 'r').read()
    print shortestpath + "n"
    s.sendall(shortestpath)    
 
 
# parse/log captcha
data = s.recv(1024)
captcha_str = repr(data)
print 'Received:', captcha_str

m_count = 0;
# if we receive the chunk below, map is done being sent.
end_regex = re.compile('(?:Solved!!! Have a fun and finally you will get a flagn)*(.+n.+n.+n.+n.+n.+n.+n.+n.+n.+)n')
map_data = ''
 
while 1:
    data = s.recv(1024)
    logdat(data)
    
    if not data:
        break
    
    map_data += data
 
    # got the last chunk of the map
    searcher = end_regex.search(map_data)
    if searcher:
        m_count+=1
        gomap(searcher.group(1)) # run the solver
        map_data = ''

data = s.recv(1024)
print 'data: ', data, 'n'
logshit(data)
 
print 'Connection closed.n'
s.close()
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class pluses {
	public static void main(String[] args) throws IOException {
		// my own testing code, insert good stuff here
		String[] board = {"++++++++--",
				  		  "-+-+-----+",
				  		  "---++----+",
				  		  "-+++------",
				  		  "--+--+-++-",
				  		  "--+-+-+-+-",
				  		  "--+++----+",
				  		  "-+-++-+---",
				  		  "+--++--+--",
				  		  "++-+--+--+"};
		
		Scanner in = new Scanner(new FileReader(new File("map.txt")));
		PrintWriter out = new PrintWriter(new FileWriter(new File("map.out")));
		
		int i=0;
		while(in.hasNext()) { board[i] = in.nextLine().trim(); i++; }
		
//		for(int i=0;i<10;i++) {
//		board[i] = in.nextLine().trim();
//		System.out.println(board[i]);
//		}
		
		out.printf("%s", solve(board));
		out.close();
	}
	
	// solves an instance of the game
	static int n,m;
	static int[] dx = {-1,0,1,0,0}, dy = {0,1,0,-1,0};
	static String solve(String[] board) {
		n = board.length;
		m = board[0].length();
		boolean[][] v = new boolean[n][m];
		for(int i=0; i<n; i++)
			for(int j=0; j<m; j++)
				v[i][j] = board[i].charAt(j)=='-';
		// goal is to get v to all FALSE
		
		String best = null;
		
		// try all moves in the top row
		for(int i=0; i<1<<m; i++) {
			boolean[][] cpy = copy(v);
			String temp = "";
			for(int j=0; j<m; j++)
				if(isSet(i,j)) {
					temp += 0+""+j;
					flip(cpy,0,j);
				}
			String rest = finish(cpy);
			if(rest == null) continue;
			temp += rest;
			if(best == null || best.length() > temp.length())
				best = temp;
		}
		
		return best;
	}
	// a partially finished board
	// no moves are allowed on the first row, so
	// a greedy algo works
	static String finish(boolean[][] v) {
		String temp = "";
		for(int i=1; i<v.length; i++)
			for(int j=0; j<v[0].length; j++)
				if(v[i-1][j]) {
					flip(v,i,j);
					temp += i+""+j;
				}
		// check if the board was solvable
		for(int j=0; j<v[0].length; j++)
			if(v[v.length-1][j])
				temp = null;
		return temp;
	}
	static boolean isSet(int x, int p) {
		return (x&(1<<p)) != 0;
	}
	static void flip(boolean[][] v, int x, int y) {
		for(int i=0; i<dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(!ok(nx,ny)) continue;
			v[nx][ny] ^= true;
		}
	}
	static boolean ok(int x, int y) {
		return x>=0 && y>=0 && x<n && y<m;
	}
	static boolean[][] copy(boolean[][] v) {
		boolean[][] w = new boolean[v.length][v[0].length];
		for(int i=0; i<v.length; i++)
			for(int j=0; j<v[0].length; j++)
				w[i][j] = v[i][j];
		return w;
	}
}
Credits: Antony Stabile, Ditmar Wendt