SECCON 2015 - Nonogram - 300 point Programming Challenge

#!/usr/bin/python
# -*- coding: utf-8 -*-

import requests 
import re
from itertools import izip
import PIL
from PIL import ImageFont,Image,ImageDraw
import subprocess
import sys
from ortools.constraint_solver import pywrapcp

URL = 'http://qrlogic.pwn.seccon.jp:10080/game/'

#
# Make a transition (automaton) list of tuples from a
# single pattern, e.g. [3,2,1]
#
def make_transition_tuples(pattern):
  p_len = len(pattern)
  num_states = p_len + sum(pattern)

  tuples = []

  # this is for handling 0-clues. It generates
  # just the minimal state
  if num_states == :
    tuples.append((1, , 1))
    return (tuples, 1)

  # convert pattern to a 0/1 pattern for easy handling of
  # the states
  tmp = []
  c = 
  for pattern_index in range(p_len):
    tmp.extend([1] * pattern[pattern_index])
    tmp.append()

  for i in range(num_states):
    state = i + 1
    if tmp[i] == :
      tuples.append((state, , state))
      tuples.append((state, 1, state + 1))
    else:
      if i < num_states - 1:
        if tmp[i + 1] == 1:
          tuples.append((state, 1, state + 1))
        else:
          tuples.append((state, , state + 1))
  tuples.append((num_states, , num_states))
  return (tuples, num_states)


#
# check each rule by creating an automaton and transition constraint.
#
def check_rule(rules, y):
  cleaned_rule = [rules[i] for i in range(len(rules)) if rules[i] > ]
  (transition_tuples, last_state) = make_transition_tuples(cleaned_rule)

  initial_state = 1
  accepting_states = [last_state]

  solver = y[].solver()
  solver.Add(solver.TransitionConstraint(y,
                                         transition_tuples,
                                         initial_state,
                                         accepting_states))
 
def silly(rows, row_rule_len, row_rules, cols, col_rule_len, col_rules):
  font = ImageFont.truetype('clacon.ttf')
  img = Image.new("RGBA", (300,1500),(255,255,255))
  draw = ImageDraw.Draw(img)
  y_text = 8

  # Create the solver.
  solver = pywrapcp.Solver('Nonogram')

  #
  # variables
  #
  board = {}
  for i in range(rows):
    for j in range(cols):
      board[i, j] = solver.IntVar(, 1, 'board[%i, %i]' % (i, j))

  board_flat = [board[i, j] for i in range(rows) for j in range(cols)]

  # Flattened board for labeling.
  # This labeling was inspired by a suggestion from
  # Pascal Van Hentenryck about my (hakank's) Comet
  # nonogram model.
  board_label = []
  if rows * row_rule_len < cols * col_rule_len:
    for i in range(rows):
      for j in range(cols):
        board_label.append(board[i, j])
  else:
    for j in range(cols):
      for i in range(rows):
        board_label.append(board[i, j])

  #
  # constraints
  #
  for i in range(rows):
    check_rule(row_rules[i], [board[i, j] for j in range(cols)])

  for j in range(cols):
    check_rule(col_rules[j], [board[i, j] for i in range(rows)])

  #
  # solution and search
  #
  parameters = pywrapcp.DefaultPhaseParameters()
  parameters.heuristic_period = 200000

  db = solver.DefaultPhase(board_label, parameters)

  solver.NewSearch(db)

  num_solutions = 
  while solver.NextSolution():
    num_solutions += 1
    for i in range(rows):
      row = [board[i, j].Value() for j in range(cols)]
      row_pres = []
      for j in row:
        if j == 1:
          row_pres.append('█')
        else:
          row_pres.append(' ')
      outline = ''.join(row_pres)
      outline = unicode(outline,"utf-8")
      width, height = font.getsize(outline)
      draw.text((,y_text),outline,(,,),font=font)
      y_text += height
      draw = ImageDraw.Draw(img)

    draw.text((,y_text)," ",(,,),font=font)
    y_text += height
    draw.text((,y_text)," ",(,,),font=font)
    y_text += height
    draw.text((,y_text)," ",(,,),font=font)
    y_text += height

    if num_solutions >= 6:
      break

  solver.EndSearch()
  img = img.resize((700,2000))
  img.show()  

def mainloop(answer):

 if answer:
  print "[*] Posting result: " + answer
  payload = { 'ans' : answer }
  r = s.post(URL, data=payload)
 else:
  print "[*] Using GET Method to get first challenge..."
  r = s.get(URL)

 toprow = []
 firstcolumn = []

 for line in r.content.splitlines():
  if 'Stage:' in line:
   thestage = line.split(" ")[1]
   print "[*] Stage: " + thestage + " / 30"

  if ''</span> in line:
   headerblocks = line.split("</th>")
   p = re.compile("(.*?)")
   for block in headerblocks:
    columnnums = []
    if ''</span> in block:
     break

    subblocks = block.split("
")
    for subblock in subblocks: 
     m = p.search(subblock)
     if m:
      columnnums.append(int(m.group(1),10))
   
    if len(columnnums) > :
     toprow.append(columnnums)

  if ''</span> in line:
   if ''</span> in line:
    line = line.split(''</span>)[1]

   headerblocks = line.split("</th>")
   p = re.compile("(.*?)")
   for block in headerblocks:
    columnnums = []
    subblocks = block.split(" ")
    for subblock in subblocks: 
     m = p.search(subblock)
     if m:
      columnnums.append(int(m.group(1),10))
   
    if len(columnnums) > :
     firstcolumn.append(columnnums)

 # hacked together since the Google CP engine needs more than the old engine 
        rulelen = 
        for x in toprow:
                if len(x) > rulelen:
                        rulelen = len(x)
 # zero pad the rules
 for x in toprow:
  while len(x) < rulelen:
   x.insert(,)

        rulelen2 = 
        for x in firstcolumn:
                if len(x) > rulelen2:
                        rulelen2 = len(x)

 # zero pad the rules
 for x in firstcolumn:
  while len(x) < rulelen2:
   x.insert(,)


 silly(len(firstcolumn), rulelen, firstcolumn, len(toprow), rulelen2, toprow)


s = requests.Session()
ans = ""

# super ugly 
while(1):
 mainloop(ans)
 
 try:
  thedata = subprocess.check_output(["zbarimg -q /tmp/tmp*"],shell=True).split(":")[1].strip().splitlines()[]
 except:
  thedata = ""

 print "[*] Decoded QR: " + thedata

 if thedata == "":
  # maybe try and scan it on your phone or something :P 
  ans = raw_input("Enter QR Code result> ")
 else:
  ans = thedata

 try:
  subprocess.check_output(["killall","-9","display"])
 except:
  pass