VolgaCTF 2015 mathproblem

@mrexcessive WHA

The problem

nc mathproblem.2015.volgactf.ru 8888


Greetings, neonate! Let us check if you can solve one particular problem!
You're given a set of integer numbers x0,x1,...,xn and y.
Using parenthesis '(' and ')' and regular arithmetic operations '\*','/','+','-' over integer numbers
you need to find a mathematical expression that involves each and every xi and evaluates to y.

Sending the correct expression advances you to the next round.
E.g. if the problem says '137 421 700 746 equals 1395'
your solution may look like this '(700-421)\*(746/137)'.
N.b. Division operation is done according to regular integer division rules,
so 746/137 == 5
and (700-421)\*(746/137) != (700-421)\*746/137.

Round 0. Solve!
23 228 543 931 equals 931

The solution

OK lets check python eval agrees with those things, to be safe...

Yes
>>> 746/137 == 5
True
>>> (700-421)*(746/137)
1395
>>> (700-421)*746/137
1519

So...
Split at equals into params, answer
Split out numbers at spaces
int() everything

Now... hmmm...
use... all of them... permute... ?

itertools.permutations ftw!

...and eval!

...and nested perm on the operations and brackets

Can use eval ?

>>> a = eval("(1+21423)/(3+4)")
3060

Yep

OK
Run this version with all four numbers permuted and all 4 operations tried in each of the three possible slots between pairs of numbers. Also has no-bracketing, bracketing first pair, last pair or both pairs as options.

...

Code is answering a lot now, but needs final bracketing rule for (abc)d and a(bcd)
I think the permuting abcd order will cover every other possible...

final Python code:

#!/usr/bin/python
# @mrexcessive @WHA - solving algos and python

import os, sys, code
import readline, rlcompleter
import socket,time
import random
import re
import itertools
import subprocess
import operator

SERVER = "mathproblem.2015.volgactf.ru"
PORT = 8888
s = None

logfname="logTries.txt"
repeatOnFail = True

debug = True
debugLots = True
flagGoInteractive = True        # go interactive after running stuff
alphanums = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
printables =   alphanums + ".,<>?/!$%^&*()_-+=@'#][{}`#"


#useful
def Log(s,alwaysLog = False):
   if logfname <> None:
      f=open(logfname,"a")
      f.write("%s\n" % s)
      f.close
   if debug and (alwaysLog or debugLots):
      print s

def DoConnect():
   global s
   s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
   s.connect((SERVER,PORT))
   assert(s <> None)

def GetResponse(timeout=1):
   global s
   s.setblocking(0)
   total_data=[]
   begin = time.time()
   while True:
      if total_data and time.time() - begin > timeout:      # wait timeout sec if we have something
         break
      elif time.time() - begin > timeout * 2:               # wait 2xtimeout if nothing
         break
      try:
         data = s.recv(1024)
         if data:
            total_data.append(data)
            begin = time.time()
         else:
            time.sleep(0.1)
      except:
         pass
   return ''.join(total_data)

def SendAnswer(a):
   # a is a string...
   s.send(a)

def GetProblem(timeout=1):
   # returns ([params],expectedanswer)
   global s
   p = GetResponse()
   Log(p)
   assert("Solve!" in p)
   drop,p = p.split("Solve!")
   assert("equals" in p)
   p1,p2 = p.split("equals")
   sparr = p1.split()
   result = int(p2)
   params = []
   for sp in sparr:
      params.append(int(sp))
   problem = (params,result)
   Log("found problem %s" % str(problem))
   return problem

def GetAnswer(p):
   nums,result = p
   done = False
   print nums
   for brackets in (0,1,2,3,4):         # 0 is no brackets, 1 is bracket the middle pair, 2 is bracket both outer pairs, 3 is first three numbers, 4 is last three numbers
      if brackets == 0:
         b1A = ""
         b1B = ""
         b2A = ""
         b2B = ""
         b2C = ""
         b2D = ""
      elif brackets == 1:
         b1A = "("
         b1B = ")"
         b2A = ""
         b2B = ""
         b2C = ""
         b2D = ""
      elif brackets == 2:
         b1A = ""
         b1B = ""
         b2A = "("
         b2B = ")"
         b2C = "("
         b2D = ")"
      elif brackets == 3:
         b1A = ""
         b1B = ")"
         b2A = "("
         b2B = ""
         b2C = ""
         b2D = ""
      elif brackets == 4:
         b1A = "("
         b1B = ""
         b2A = ""
         b2B = ""
         b2C = ""
         b2D = ")"
      if done: break
      for aperm in list(itertools.permutations(nums)):
         if done: break
         operations = ["+","-","*","/"]
         for opA in operations:
            if done: break
            for opB in operations:
               if done: break
               for opC in operations:
                  if done: break
                  expr = b2A + str(aperm[0]) + opA + b1A + str(aperm[1]) + b2B + opB + b2C + str(aperm[2]) + b1B + opC + str(aperm[3]) + b2D
                  try:
                     ans = eval(expr)
                  except ZeroDivisionError:
                     continue
                  Log("%s = %i" % (expr,ans),False)
                  if ans == result:
                     done = True
                     break
   if not done:
      Log("could not solve for %s = %i" % (nums,result))
   assert(done)
   Log("Got answer [%s]" % expr)
   return expr

if __name__ == "__main__":
   vars = globals()
   vars.update(locals())
   readline.set_completer(rlcompleter.Completer(vars).complete)
   readline.parse_and_bind("tab: complete")
   shell = code.InteractiveConsole(vars)

   DoConnect()
   while True:
      p = GetProblem()
      a = GetAnswer(p)   
      SendAnswer(a)

   # go interactive   
   if flagGoInteractive:
      shell.interact()

After about 25 times around loop...

That's incredible! You've passed! Here's your flag: {you_count_as_fast_as_a_calculator}