Please login or register. Welcome to the Studio, guest!


Quick Links:


newBookmarkLockedFalling

Eric

Eric Avatar



1,442


November 2005
I'm not sure how familiar you guys are with the game twenty four, but basically you take 4 numbers and you can use 3 operators (+,-,*,/) in any given order to make those 4 numbers become 24.

import random

def bin_2_dec(bina):
   a = 0
   num = 0
   for x in bina:
       if x == "1":
           num = num + 2 ** a
       a = a + 1
   return num

class TwentyFour:
   POP_NUM = 30
   MUT_RATE = .1
   REC_RATE = .5
   IDEAL = 24
   CHROMES = 12
   ARRANGEMENTS = [[0,1,2,3],[0,1,3,2],[0,2,1,3],[0,2,3,1],
                   [0,3,1,2],[0,3,2,1],[1,0,2,3],[1,0,3,2],
                   [1,2,0,3],[1,3,0,2],[2,0,1,3],[2,1,0,3]]
   OPS = ["+","-","*","/"]

   def __init__(self, nums):
       self.pop = [""] * TwentyFour.POP_NUM
       self.fill_pop()
       self.nums = nums
   
   def fill_pop(self):
       for x in range(TwentyFour.POP_NUM):
           self.pop[x] = self.gen_rand_chromes()

   def gen_rand_chromes(self):
       chromes = ""
       for x in range(TwentyFour.CHROMES):
           chromes = chromes + str(random.randint(0,1))
       return chromes

   def to_string(self, chromes):
       arrchrome = chromes[0:4]
       orderchrome = chromes[4]
       order2chrome = chromes[5]

       arr = bin_2_dec(arrchrome)
       if arr >= 12:
           arr = arr - 12

       arr = TwentyFour.ARRANGEMENTS[arr]
       op1 = TwentyFour.OPS[bin_2_dec(chromes[6:8])]
       op2 = TwentyFour.OPS[bin_2_dec(chromes[8:10])]
       op3 = TwentyFour.OPS[bin_2_dec(chromes[10:12])]

       stra = str(self.nums[arr[0]])+op1
       if order2chrome == "1":
           stra = stra + "("
       stra = stra + str(self.nums[arr[1]])+op2
       if orderchrome == "1":
           stra = stra + "("
       stra = stra + str(self.nums[arr[2]])+op3+str(self.nums[arr[3]])
       if orderchrome == "1":
           stra = stra + ")"
       if order2chrome == "1":
           stra = stra + ")"
       return stra

   def compute(self, chromes):
       astr = self.to_string(chromes)
       for x in range(1,10):
           astr = astr.replace(str(x), "float("+str(x)+")")
       try:
           return eval(astr)
       except:
           return 0

   def do_op(self, op, num1, num2):
       val = eval("float(num1)"+op+"float(num2)")
       if val < 1:
          1/0
       return val

   def get_error(self, val):
       return abs(float(val - TwentyFour.IDEAL)/TwentyFour.IDEAL)

   def run_trial(self):
       a = random.randint(0, TwentyFour.POP_NUM-1)
       b = random.randint(0, TwentyFour.POP_NUM-1)

       if a == b:
           if b == 0:
               b = b + 1
           else:
               b = b - 1

       ac = self.pop[a]
       bc = self.pop[b]

       av = self.compute(ac)
       bv = self.compute(bc)

       if self.get_error(av) < self.get_error(bv):
           if self.get_error(av) == 0.0:
               return a
           winner = a
           loser = b
       else:
           if self.get_error(bv) == 0.0:
               return b
           winner = b
           loser = a

       newchromes = self.pop[loser][:]
       for x in range(TwentyFour.CHROMES):
           if random.random() < TwentyFour.REC_RATE:
               newchromes = newchromes[0:x] + \
                   self.pop[winner][x] + \
                   newchromes[x+1:]

           if random.random() < TwentyFour.MUT_RATE:
               newchromes = newchromes[0:x] + \
                   str(1-int(newchromes[x])) + \
                   newchromes[x+1:]

       self.pop[loser] = newchromes

       return a

   def run_up_to(self, num):
       for x in range(num):
           apop = self.run_trial()
           if self.get_error(self.compute(self.pop[apop])) == 0.0:
               print "trial " + str(x)
               print self.to_string(self.pop[apop])+"="+str(self.compute(self.pop[apop]))
               return
           if x > num - 10:
               print "trial " + str(x)
               print self.to_string(self.pop[apop])+"="+str(self.compute(self.pop[apop]))
       print "Failed to find answer in "+str(num)+" trials"

nums = [0]*4
for x in range(4):
   a = 0
   while a < 1 or a > 9:
       a = input("Enter a number: ")
       try:
           a * 2
       except:
           a = 0
   nums[x] = a

t4 = TwentyFour(nums)
t4.run_up_to(10000)

I wrote this sort of half-assedly. I'm wondering if there are any problems that it's unable to find a solution for that actually have a solution.


Last Edit: Oct 30, 2009 18:42:55 GMT by Eric

newBookmarkLockedFalling