__str__ Function

[JJHT7439]

Alright, I have a problem with a program that I am trying to write.

The purpose of the program is to solve 1 specific algorithm. That algorithm is send + more = money. The program is supposed to find the value of each letter and return them to you.

I think that I have all of the code working internally, as in the program appears to solve the algorithm correctly. The problem is that I can not get the code to display the solution correctly. I attached my code but if you look at the __str__ function in config you'll notice that it returns the environment for the config. But when you actually run the code it only displays the value of the last changed letter in the environment.

For example, if you run the solve function and wait for it to solve the algorithm, it will only tell you that {y=2} Which it does. But it is leaving out all of the other letters. I thought it was that my environment was not population the .rest part but it is because if you look in my code, if you keep doing self.env.rest.rest.rest etc... it will keep printing out the rest of the letters. I think that it has to be a problem with how I am using the __str__ function in either the config or nonEmptyEnv classes.

If you have any questions, just ask. Also if you try to run the program it will take a minute.

CODE:

""" Purpose of the program is to decrypt the value of the letters in the equation
 Send + More = Money. Each letter having a unique single digit value.
 Does this using a tree and checking through different configurations of values
 for each letter until the goal is found"""


# Empty Enviroment class
class EmptyEnv():
    __slots__ = ()

# Non empty enviroment class
class NonEmptyEnv(object):
    __slots__ = ('letter','digit','rest')

    def __init__(self,letter,digit,rest):
        self.letter = letter
        self.digit = digit
        self.rest = rest
        

    def __str__(self):
        result = self.letter + "=" + str(self.digit)
        if EmptyEnv:
            return result
        else:
            return result + ',' + str(self.rest)

class Config(object):
    __slots__ = ('env','letters','pos','unused')

    def __init__(self,env,letters,pos,unused):
        self.env = env
        self.letters = letters
        self.pos = pos
        self.unused = unused

    def __str__(self):
        return '{' + str(self.env) + '}'

    # ** This is commented because using this method does display all of the
    # values, but It's not pretty and it shouldn't need to be that long
        #return "{" + str(self.env) + str(self.env.rest) + str(self.env.rest.rest) + "}"

def mkEmptyEnv():
    return EmptyEnv()

# Function that solves, Initial config for Solve function is:
    # (E,('s','e','n',...,'y'), 0, (0,1,2,3,...,9))
def solve(config):
    """solve: Config -> Config or FAILURE"""
    if isGoal(config):
        print(config)
    else:
        childern = sucessor(config)
        for child in childern:
            solution = solve(child)
            if solution != False:
                return solution
        return False

# Looks up the value of a letter in an enviroment
def lookUp(letter,env):
    if env.letter == letter:
        return env.digit
    else:
        return lookUp(letter,env.rest)

''' Checks if the configutation is the goal, if the config position is
not equal to the length of the letters then it does not check the math '''
def isGoal(config):
    if config.pos == len(config.letters):
        '''s,e,n,d,m,o,r,y = lookUp('s',config.env),lookUp('e',config.env),
        lookUp('n',config.env),lookUp('d',config.env),lookUp('m',config.env),
        lookUp('o',config.env),lookUp('r',config.env),lookUp('y',config.env)'''
        s = lookUp('s',config.env)
        e = lookUp('e',config.env)
        n = lookUp('n',config.env)
        d = lookUp('d',config.env)
        m = lookUp('m',config.env)
        o = lookUp('o',config.env)
        r = lookUp('r',config.env)
        y = lookUp('y',config.env)
        return s>0 and m>0 and 1000*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e == 10000*m + 1000*o + 100*n + 10*e + y
    else:
        return False
    
''' Creates a list of succesor configs from the current config. '''
def sucessor(config):
    if config.pos >= len(config.letters):
        return []
    else:
        result = []
        letter = config.letters[config.pos]
        for i in range(len(config.unused)):
            d = config.unused[i]
            newDigit = config.unused[:i] + config.unused[i+1:]
            result.append(Config(NonEmptyEnv(letter,d,config.env),config.letters,config.pos+1,newDigit))
        return result

Example Output:

>>> E = EmptyEnv
>>> c = Config(E, ('s','e','n','d','m','o','r','y'),0,(0,1,2,3,4,5,6,7,8,9))
>>> solve(c)
{y=2}

[Gribouillis]

Here is a working __str__ function

class NonEmptyEnv(object):
    __slots__ = ('letter','digit','rest')

    def __init__(self,letter,digit,rest):
        self.letter = letter
        self.digit = digit
        self.rest = rest
        

    def __str__(self):
        result = self.letter + "=" + str(self.digit)
        if isinstance(self.rest, NonEmptyEnv):
            result += ',' + str(self.rest)
        return result

Otherwise, your solution is overly complicated. You are using NonEmptyEnv instances as stack elements and you traverse the stack recursively for each lookup. It looks like a lisp program. Did you consider storing intermediary states in a list or a tuple or a dict or a collections.deque object ? For example you could have [('n', 6),('e',5),('s',9)] as an intermediary state.

Another interesting tool for this problem is the function itertools.combinations() . For example

>>> from itertools import combinations
>>> combi = combinations(list(range(10)), 8)
>>> for i in range(15):
...  print next(combi)
... 
(0, 1, 2, 3, 4, 5, 6, 7)
(0, 1, 2, 3, 4, 5, 6, 8)
(0, 1, 2, 3, 4, 5, 6, 9)
(0, 1, 2, 3, 4, 5, 7, 8)
(0, 1, 2, 3, 4, 5, 7, 9)
(0, 1, 2, 3, 4, 5, 8, 9)
(0, 1, 2, 3, 4, 6, 7, 8)
(0, 1, 2, 3, 4, 6, 7, 9)
(0, 1, 2, 3, 4, 6, 8, 9)
(0, 1, 2, 3, 4, 7, 8, 9)
(0, 1, 2, 3, 5, 6, 7, 8)
(0, 1, 2, 3, 5, 6, 7, 9)
(0, 1, 2, 3, 5, 6, 8, 9)
(0, 1, 2, 3, 5, 7, 8, 9)
(0, 1, 2, 3, 6, 7, 8, 9)

Finally, there are probably better approaches than brute force for this problem, so you should think a little more about the algorithm.

[richieking]

hhhmmmmm

Slash12.. I think your algo. is too long to solve this case. Refactor i thing is needed.
:)

[JJHT7439]

Alright, the reason that I'm using brute force is because I'm in a data structures class and this is the way that the teacher wants it done. I know that there are better methods, but I just need it to work for now.

Second, I tried your Str function in the first post and for some reason it returns duplicates of the letter configurations.

EX: When you run it it will display
{y=2,r=8,o=0,m=1,d=7,n=6,e=5,s=9r=8,o=0,m=1,d=7,n=6,e=5,s=9o=0,m=1,d=7,n=6,e=5,s=9}

And I'm not too experienced with python so I'm not sure what the other things you talked about do. Sorry.

[Gribouillis]

Alright, the reason that I'm using brute force is because I'm in a data structures class and this is the way that the teacher wants it done. I know that there are better methods, but I just need it to work for now.

Second, I tried your Str function in the first post and for some reason it returns duplicates of the letter configurations.

EX: When you run it it will display
{y=2,r=8,o=0,m=1,d=7,n=6,e=5,s=9r=8,o=0,m=1,d=7,n=6,e=5,s=9o=0,m=1,d=7,n=6,e=5,s=9}

And I'm not too experienced with python so I'm not sure what the other things you talked about do. Sorry.

I did not have the same problem with the __str__ function. You probably changed something else to the code.

To illustrate what I wrote above, I modified your code by eliminating the Env classes

# python 2 or 3
""" Purpose of the program is to decrypt the value of the letters in the equation
 Send + More = Money. Each letter having a unique single digit value.
 Does this using a tree and checking through different configurations of values
 for each letter until the goal is found"""


class Config(object):
    letters = ('s', 'm', 'e','n','d','o','r','y')
    math = (1000, 1000-10000, 100+1-10, 10-100, 1, 100-1000, 10, -1)
    __slots__ = ('values', 'pos','unused')

    def __init__(self, values, pos, unused):
        self.values = values
        self.pos = pos
        self.unused = unused

    def solve(self):
        """Return a solution Config or None if no solution"""
        if self.isGoal():
            return self
        else:
            for child in self.successor():
                solution = child.solve()
                if solution:
                    return solution

    def isGoal(self):
        ''' Checks if the configutation is the goal, if the config position is
        not equal to the length of the letters then it does not check the math '''
        if self.pos == len(self.letters):
            checksum = 0
            for i, val in enumerate(self.values):
                checksum += val * self.math[i]
            return self.values[0] > 0 and self.values[1] > 0 and checksum == 0
        else:
            return False
    
    def successor(self):
        ''' Creates a list of succesor configs from the current config. '''
        result = []
        if self.pos < len(self.letters):
            for i in range(len(self.unused)):
                d = self.unused[i]
                newDigit = self.unused[:i] + self.unused[i+1:]
                result.append( Config(self.values + (d,), self.pos + 1, newDigit) )
        return result
    
    def display(self):
        for i in range(self.pos):
            print("{x} = {v}".format(x = self.letters[i], v = self.values[i]))
    
if __name__ == "__main__":
    c = Config((), 0, (0,1,2,3,4,5,6,7,8,9))
    sol = c.solve()
    if sol:
        sol.display()
    else:
        print("No solution found")

""" my output --->
s = 9
m = 1
e = 5
n = 6
d = 7
o = 0
r = 8
y = 2
"""

Notice that most of your functions take a config argument, and they are better implemented as methods in the class Config.

[Gribouillis]

And here is a much shorter solution using itertools

# python 2 or 3
# solve SEND + MORE = MONEY by brute force
import itertools as itt

letters = ('s', 'm', 'e','n','d','o','r','y')
coefs = (1000, 1000-10000, 100+1-10, 10-100, 1, 100-1000, 10, -1)

def solve():
    for t in itt.combinations(range(10), len(letters)):
        for v in itt.permutations(t):
            if v[0] > 0 and v[1] > 0 and sum(v[i] * coefs[i] for i in range(len(coefs))) == 0:
                print(list(zip(letters, v)))
                return

if __name__ == "__main__":     
    solve()

""" my output -->
[('s', 9), ('m', 1), ('e', 5), ('n', 6), ('d', 7), ('o', 0), ('r', 8), ('y', 2)]
"""

[LuckyX2]

Here's how I did it, my empty environment is different though. My empty environment has a .name but it's initialized as None. so I just iterate through the environment, building the lists until None is reached and then I return the string without the extra comma at the end.

class EmptyEnv(object):
    __slots__ = ('name')
    
    def __init__(self):
        self.name = None

class NonEmptyEnv(object):
    __slots__ = ('name','value','rest')
    
    def __init__(self, name, value, rest):
        self.name = name
        self.value = value
        self.rest = rest

    def __str__(self):
        letterLst = []
        valueLst = []
        curLetter = self.name
        curValue = self.value
        envString = ""
        while curLetter != None:
            letterLst.append(curLetter)
            valueLst.append(curValue) #error here
            curLetter = self.rest.name
            curValue = self.rest.value
        for i in letterLst:
            envString+str(i)+"="+str(valueLst[i])+","
        return envString[0:-1]

But when I run it I get nothing, I debugged and the error was showing at "valueLst.append(curValue)"

[LuckyX2]

Well I just tried yours modified ever so slightly to fit my use of None for the EmptyEnv and it worked.

Using the test case:

E = NonEmptyEnv('e', 2, NonEmptyEnv('s', 1, EmptyEnv()))
print(E)

I get the output:

e=2,s=1,

Here's my version of yours:

class EmptyEnv(object):
    __slots__ = ('name')
    
    def __init__(self):
        self.name = None
        
    def __str__(self):
        return ""
 
class NonEmptyEnv(object):
    __slots__ = ('name','value','rest')
    
    def __init__(self, name, value, rest):
        self.name = name
        self.value = value
        self.rest = rest
        
    def __str__(self):
        result = self.name + "=" + str(self.value)
        if self.name == None:
            return result
        else:
            return result + ',' + str(self.rest)

[LuckyX2]

So I took that last bit of code I posted and combined it with yours. Now it works.

""" Purpose of the program is to decrypt the value of the letters in the equation
 Send + More = Money. Each letter having a unique single digit value.
 Does this using a tree and checking through different configurations of values
 for each letter until the goal is found"""


# Empty Enviroment class
class EmptyEnv(object):
    __slots__ = ('letter')
    
    def __init__(self):
        self.letter = None
        
    def __str__(self):
        return ""

# Non empty enviroment class
class NonEmptyEnv(object):
    __slots__ = ('letter','digit','rest')

    def __init__(self,letter,digit,rest):
        self.letter = letter
        self.digit = digit
        self.rest = rest
        

    def __str__(self):
        result = self.letter + "=" + str(self.digit)
        if self.letter == None:
            return result
        else:
            return result + ',' + str(self.rest)

class Config(object):
    __slots__ = ('env','letters','pos','unused')

    def __init__(self,env,letters,pos,unused):
        self.env = env
        self.letters = letters
        self.pos = pos
        self.unused = unused

    def __str__(self):
        return '{' + str(self.env) + '}'

    # ** This is commented because using this method does display all of the
    # values, but It's not pretty and it shouldn't need to be that long
        #return "{" + str(self.env) + str(self.env.rest) + str(self.env.rest.rest) + "}"

def mkEmptyEnv():
    return EmptyEnv()

# Function that solves, Initial config for Solve function is:
    # (E,('s','e','n',...,'y'), 0, (0,1,2,3,...,9))
def solve(config):
    """solve: Config -> Config or FAILURE"""
    if isGoal(config):
        print(config)
    else:
        childern = sucessor(config)
        for child in childern:
            solution = solve(child)
            if solution != False:
                return solution
        return False

# Looks up the value of a letter in an enviroment
def lookUp(letter,env):
    if env.letter == letter:
        return env.digit
    else:
        return lookUp(letter,env.rest)

''' Checks if the configutation is the goal, if the config position is
not equal to the length of the letters then it does not check the math '''
def isGoal(config):
    if config.pos == len(config.letters):
        '''s,e,n,d,m,o,r,y = lookUp('s',config.env),lookUp('e',config.env),
        lookUp('n',config.env),lookUp('d',config.env),lookUp('m',config.env),
        lookUp('o',config.env),lookUp('r',config.env),lookUp('y',config.env)'''
        s = lookUp('s',config.env)
        e = lookUp('e',config.env)
        n = lookUp('n',config.env)
        d = lookUp('d',config.env)
        m = lookUp('m',config.env)
        o = lookUp('o',config.env)
        r = lookUp('r',config.env)
        y = lookUp('y',config.env)
        return s>0 and m>0 and 1000*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e == 10000*m + 1000*o + 100*n + 10*e + y
    else:
        return False
    
''' Creates a list of succesor configs from the current config. '''
def sucessor(config):
    if config.pos >= len(config.letters):
        return []
    else:
        result = []
        letter = config.letters[config.pos]
        for i in range(len(config.unused)):
            d = config.unused[i]
            newDigit = config.unused[:i] + config.unused[i+1:]
            result.append(Config(NonEmptyEnv(letter,d,config.env),config.letters,config.pos+1,newDigit))
        return result

Using this test case:

E = EmptyEnv()
c = Config(E, ('s','e','n','d','m','o','r','y'),0,(0,1,2,3,4,5,6,7,8,9))
solve(c)

I get the result:

{y=2,r=8,o=0,m=1,d=7,n=6,e=5,s=9,}

That additional comma at the end is annoying but shouldn't cause any point reductions in your grading I'd imagine.

[JJHT7439]

I did not have the same problem with the __str__ function. You probably changed something else to the code.

Snip

Strange, I didn't think I changed anything in the code but I retried it on my previous version of the program and it worked fine, not sure what happened there. Thanks for your help.

[Ampj]

class Config(object):
letters = ('s', 'm', 'e','n','d','o','r','y')
math = (1000, 1000-10000, 100+1-10, 10-100, 1, 100-1000, 10, -1)
__slots__ = ('values', 'pos','unused')

Where did you get those values for math? I understand the rest but not how you got those coefficients for the letters. Thanks!

[Gribouillis]

Where did you get those values for math? I understand the rest but not how you got those coefficients for the letters. Thanks!

Because

SEND = 1000*s + 100*e + 10*n + 1*d
MORE = 1000*m + 100*o + 10*r +1*e
MONEY = 10000*m + 1000*o + 100*n + 10*e + 1*y

so the equation SEND + MORE = MONEY is equivalent to

0 == (1000-10000)*m + 1000*s + (100+1-10)*e + (100-1000)*o + (10-100)*n + 10*r + 1*d -1*y

[TrustyTony]

Little logic, even partial, included works also miracles for speed, even when generating all permutations:

letters = ('s', 'm', 'e','n','d','o','r','y')
coefs = (1000, 1000-10000, 100+1-10, 10-100, 1, 100-1000, 10, -1)

def sendmoremoney():
# python 2 or 3
# solve SEND + MORE = MONEY by brute force with little logic
    for t in itertools.combinations(range(10), len(letters)):
        for v in itertools.permutations(t):
            # fifth number must be 1, fourth numbers must add to at least 9 (10 with carry), last digit sum (d+e) modulo 10 is y
            if v[1] == 1 and v[0]+v[1] >= 8 and ((v[4]+v[2]) % 10 == v[-1]) and sum(v[i] * coefs[i] for i in range(len(coefs))) == 0:
                return (list(zip(letters, v)))