Making Cryptarithm Solver - Improving It

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 5268 Views - Last Post: 24 May 2012 - 01:31 PM Rate Topic: -----

#1 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Making Cryptarithm Solver - Improving It

Posted 15 May 2012 - 11:31 AM

Hey, I've been trying to make a cryptarithm solver for a while now, and it works, but it's REALLY slow.
Currently, I have:
for s in range(1,10):
	for e in range(0,10):
		for n in range(0,10):
			for d in range(0,10):
				for m in range(1,10):
					for o in range(0,10):
						for r in range(0,10):
							for y in range(0,10):
								send = s*1000 + e*100 + n*10 + d
								more = m*1000 + o*100 + r*10 + e
								money = m*10000 + o*1000 + n*100 + e*10 + y
								if send + more == money:
									if s!=e and s!=n and s!=d and s!=m and s!=o and s!=r and s!=y and e!=n and e!=d and e!=m and e!=o and e!=r and e!=y and n!=d and n!=m and n!=o and n!=r and n!=y and d!=m and d!=o and d!=r and d!=y and m!=o and m!=r and m!=y and o!=r and o!=y and r!=y:
										print "  %1d%1d%1d%1d" & (s, e, n, d)
										print " +%1d%1d%1d%1d" & (m, o, r, e)
										print "------"
										print " %1d%1d%1d%1d%1d" % (m, o, n, e, y)



When I run in, I get an error:
TypeError: "unsupported operand type(s) for &: 'str' and 'tuple'"


I believe it has something to do with the formatting near the end, but they've never worked for me for some reason.

Now to what I've done... I have tried taking the 'if' statement:
if s!=e and s!=n and s!=d and s!=m and s!=o and s!=r and s!=y and e!=n and e!=d and e!=m and e!=o and e!=r and e!=y and n!=d and n!=m and n!=o and n!=r and n!=y and d!=m and d!=o and d!=r and d!=y and m!=o and m!=r and m!=y and o!=r and o!=y and r!=y:

and distributing the first section:
if s!=e and s!=n and s!=d and s!=m and s!=o and s!=r and s!=y

to the
 for s in range(1,10): 
to produce.
for s in range(1,10):
	if s!=e and s!=n and s!=d and s!=m and s!=o and s!=r and s!=y:
		
	for e in range(0,10):
		if e!=n and e!=d and e!=m and e!=o and e!=r and e!=y:
			
		for n in range(0,10):
			if n!=d and n!=m and n!=o and n!=r and n!=y:
				
			for d in range(0,10):
				if d!=m and d!=o and d!=r and d!=y:
				
				for m in range(1,10):
					if m!=o and m!=r and m!=y:
						
					for o in range(0,10):
						if o!=r and o!=y
						
						for r in range(0,10):
							if r!=y
							
							for y in range(0,10):
								send = s*1000 + e*100 + n*10 + d
								more = m*1000 + o*100 + r*10 + e
								money = m*10000 + o*1000 + n*100 + e*10 + y
								if send + more == money:
									print "  %1d%1d%1d%1d" & (s, e, n, d)
									print " +%1d%1d%1d%1d" & (m, o, r, e)
									print "------"
									print " %1d%1d%1d%1d%1d" % (m, o, n, e, y)

and I was just wondering, would that work if I was to expand and have the program check if the corresponding letter is equal or not equal to another while inside that letters loop? What would be the best course of action?

Is This A Good Question/Topic? 0
  • +

Replies To: Making Cryptarithm Solver - Improving It

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2091
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: Making Cryptarithm Solver - Improving It

Posted 15 May 2012 - 11:56 AM

Your error isn't on the line with the if, it's on the line after it:

print "  %1d%1d%1d%1d" & (s, e, n, d)


And as the error message indicates the problem is that the &-operator doesn't work with a string and a tuple as operands. You probably meant to use % there (same on the following lines).
Was This Post Helpful? 1
  • +
  • -

#3 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Making Cryptarithm Solver - Improving It

Posted 15 May 2012 - 12:18 PM

You mentioned that it runs really slowly, this is why:
for s in range(1,10):
	for e in range(0,10):
		for n in range(0,10):
			for d in range(0,10):
				for m in range(1,10):
					for o in range(0,10):
						for r in range(0,10):
							for y in range(0,10):



There are 8 loops. Each loop runs 9 - 10 times. According to my math (and someone correct me if it's wrong) you have 81,000,000 iterations. That means you do the following, 81 million times:
send = s*1000 + e*100 + n*10 + d
more = m*1000 + o*100 + r*10 + e
money = m*10000 + o*1000 + n*100 + e*10 + y


That's a lot of work, my friend.
Was This Post Helpful? 2
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,596
  • Joined: 16-October 07

Re: Making Cryptarithm Solver - Improving It

Posted 15 May 2012 - 01:06 PM

Look at all your exception cases...

Bail as early as you can:
for s in range(1,10):
	if s!=e:
		for e in range(0,10):
			for n in range(0,10):
				if s!=n and e!=n:
					for d in range(0,10):
						# you have enough to complete this calculation here
						send = s*1000 + e*100 + n*10 + d


Was This Post Helpful? 2
  • +
  • -

#5 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Re: Making Cryptarithm Solver - Improving It

Posted 15 May 2012 - 09:25 PM

Okay, put together everyone's ideas and got out this.

for s in range(1,10):
    if s!=e:
        for e in range(0,10):
            for n in range(0,10):
                if s!=n and e!=n:
                    for d in range(0,10):
                        send = s*1000 + e*100 + n*10 + d
                        for m in range(1,10):
                                if m!=o:
                                    for o in range(0,10):
                                        if o!=r and o!=e:
                                            for r in range(0,10):
                                                more = m*1000 + o*100 + r*10 + e

                                                print more, send
                                            
                                            if send + more == money:
	                                        if s!=e and s!=n and s!=d and s!=m and s!=o and s!=r and s!=y and e!=n and e!=d and e!=m and e!=o and e!=r and e!=y and n!=d and n!=m and n!=o and n!=r and n!=y and d!=m and d!=o and d!=r and d!=y and m!=o and m!=r and m!=y and o!=r and o!=y and r!=y:

	                                            print "  %1d%1d%1d%1d" & (s, e, n, d)
	                                            print " +%1d%1d%1d%1d" & (m, o, r, e)
	                                            print "------"
	                                            print " %1d%1d%1d%1d%1d" % (m, o, n, e, y)
                



Am I starting to get the right idea? I got the correct spacing on the edit, but it's not appearing correctly on the post. Also, I'm working on the first beginning part, so mind my horribly long 'if' statement for now.
Was This Post Helpful? 0
  • +
  • -

#6 alexr1090  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 44
  • View blog
  • Posts: 124
  • Joined: 08-May 11

Re: Making Cryptarithm Solver - Improving It

Posted 15 May 2012 - 10:53 PM

if you could get all those commands after the if statement into one line, it would be a good entry for the one-liner challenge
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,596
  • Joined: 16-October 07

Re: Making Cryptarithm Solver - Improving It

Posted 16 May 2012 - 06:11 AM

It looks like you're doing this:
for s in range(1,10):
	for e in range(0,10):
		if e not in [s]:
			for n in range(0,10):
				if n not in [s,e]:
			...



If so, then a one liner...
Spoiler

It's not a complete one liner, because at that point I get zero results. I was rather bummed. I looked over the logic.

Ultimately, I need this to be true: s*1000 + e*100 + n*10 + d + m*1000 + o*100 + r*10 + e = m*10000 + o*1000 + n*100 + e*10 + y

Which means, this must be true: s*1000 + e*91 + n*90 + d - m*9000 - o*900 - r*10 - y = 0

Just looking at that, if d!=y, then I don't think it can ever be true. Nor do I believe there is a set within the given range where it can be true, regardless of limits.

So, the shortest form of the given problem in python is pass.

This post has been edited by baavgai: 16 May 2012 - 06:14 AM

Was This Post Helpful? 1
  • +
  • -

#8 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Re: Making Cryptarithm Solver - Improving It

Posted 16 May 2012 - 10:57 AM

View Postbaavgai, on 16 May 2012 - 06:11 AM, said:

It looks like you're doing this:
for s in range(1,10):
	for e in range(0,10):
		if e not in [s]:
			for n in range(0,10):
				if n not in [s,e]:
			...



If so, then a one liner...
Spoiler

It's not a complete one liner, because at that point I get zero results. I was rather bummed. I looked over the logic.

Ultimately, I need this to be true: s*1000 + e*100 + n*10 + d + m*1000 + o*100 + r*10 + e = m*10000 + o*1000 + n*100 + e*10 + y

Which means, this must be true: s*1000 + e*91 + n*90 + d - m*9000 - o*900 - r*10 - y = 0

Just looking at that, if d!=y, then I don't think it can ever be true. Nor do I believe there is a set within the given range where it can be true, regardless of limits.

So, the shortest form of the given problem in python is pass.


Okay, I was just trying to follow what you showed me in your earlier post, where did I go wrong?

I guess you could solve for the first word at first using...
for s in range(1,10):
	    if s!=e:

and keep using that for all the letters in 'SEND'. Or am I thinking the wrong way?
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,596
  • Joined: 16-October 07

Re: Making Cryptarithm Solver - Improving It

Posted 16 May 2012 - 12:33 PM

My earlier post is wrong. It puts the check too soon.

You can get all valid s,e,n,d combos with this:
for s in range(1,10):
	for e in range(0,10):
		if s!=e:
			for n in range(0,10):
				if n not in [s,e]:
					for d in range(0,10):
						if d not in [s,e,n]:
							print (s,e,n,d)



Or, more concisely:
for s in range(1,10):
	for e in [ v for v in range(10) if v not in [s]]:
		for n in [ v for v in range(10) if v not in [s,e]]:
			for d in [ v for v in range(10) if v not in [s,e,n]]:
				print (s,e,n,d)


Was This Post Helpful? 1
  • +
  • -

#10 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Re: Making Cryptarithm Solver - Improving It

Posted 22 May 2012 - 10:36 AM

Sorry, it was my birthday this weekend and we went camping, anyways, may I ask what the "v" in your code means? Or is it something that I just didn't learn?

I was thinking of grabbing all the values using the first code you showed me above, and then checking using an if statement whether send + more = money.

Using your code, I made the second word as well.

for m in range(1,10): 
	for o in range(0,10): 
		if m!=o: 
			for r in range(0,10): 
				if r not in [m,o]: 
					for e in range(0,10): 
						if e not in [m,o,r]: 
							print (m,o,r,e)


Was This Post Helpful? 0
  • +
  • -

#11 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Re: Making Cryptarithm Solver - Improving It

Posted 22 May 2012 - 10:49 AM

Can't figure out how to edit posts, so I got this together.

for s in range(1,10):
	for e in range(0,10):
		if s!=e:
			for n in range(0,10):
				if n not in [s,e]:
					for d in range(0,10):
						if d not in [s,e,n]:
							print (s,e,n,d)
for m in range(1,10): 
	for o in range(0,10): 
		if m!=o: 
			for r in range(0,10): 
				if r not in [m,o]: 
					for e in range(0,10): 
						if e not in [m,o,r]: 
							print (m,o,r,e)
for m in range(1,10):
	for o in range(0,10):
		if m!=o:
			for n in range(0,10):
				if n not in [m,o]:
					for e in range(0,10):
						if e not in [m,o,n]:
							for y in range(0,10):
								if y not in [m,o,n,e]:
									print (m,o,n,e,y)
word1 = s,e,n,d
word2 = m,o,r,e
word3 = m,o,n,e,y

if word1 + word2 == word3:
    print word1
    print word2
    print word3

							



Currently I'm working on trying to get everything from declaring the word1, word2, etc. and down.
Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,596
  • Joined: 16-October 07

Re: Making Cryptarithm Solver - Improving It

Posted 22 May 2012 - 11:16 AM

The v is just a variable name. You can do this:
for i in range(5):
	if i!=2:
		print i



Or this:
for j in [ i for i in range(5) if i!=2 ]:
	print j



This output is the same. The construct is called a list comprehension. It's a very pythony thing to do.


Back to your work. Use defs! You have a brutal level of nesting. You can aleviate it with more functions.


def doSendMore(s,e,n,d,m,o,r):
	print (m,o,r,e)
	# more code here


def doSend(s,e,n,d):
	print (s,e,n,d)
	for m in range(1,10): 
		for o in range(0,10): 
			if m!=o: 
				for r in range(0,10): 
					if r not in [m,o]: 
						# you duped this
						# don't do that
						# for e in range(0,10): 
						#	if e not in [m,o,r]: 
						doSendMore(s,e,n,d,m,o,r)
								

def process():
	for s in range(1,10):
		for e in range(0,10):
			if s!=e:
				for n in range(0,10):
					if n not in [s,e]:
						for d in range(0,10):
							if d not in [s,e,n]:
								doSend(s,e,n,d)
							 

process()


Was This Post Helpful? 0
  • +
  • -

#13 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Re: Making Cryptarithm Solver - Improving It

Posted 22 May 2012 - 11:32 AM

Hmm, I don't quite understand those yet, maybe I should go and learn them. Though, this...
def process():
	for s in range(1,10):
		for e in range(0,10):
			if s!=e:
				for n in range(0,10):
					if n not in [s,e]:
						for d in range(0,10):
							if d not in [s,e,n]:
								def doSend(s,e,n,d)

def doSendMore(s,e,n,d,m,o,r):					
	print (m,o,r,e)
	
def doSend(s,e,n,d):
	print (s,e,n,d)
	for m in range(1,10): 
		for o in range(0,10): 
			if m!=o: 
				for r in range(0,10): 
					if r not in [m,o]:
						doSendMore(s,e,n,d,m,o,r)
							


I believe I understand this a bit and can probably try and keep going. Would I need another def to figure out if 'send + more = money'?
Was This Post Helpful? 0
  • +
  • -

#14 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Making Cryptarithm Solver - Improving It

Posted 22 May 2012 - 11:42 AM

On this tutorial, look at the section called "List Comprehensions".
Was This Post Helpful? 0
  • +
  • -

#15 Fultoa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 15-May 12

Re: Making Cryptarithm Solver - Improving It

Posted 24 May 2012 - 11:32 AM

Hmm, I wrote this up, but never used the 'defs'. This doesn't work and only outputs the values of send, more and money.
for s in range(1,10):
	for e in range(0,10):
		if s!=e:
			for n in range(0,10):
				if n not in [s,e]:
					for d in range(0,10):
						if d not in [s,e,n]:
							print (s,e,n,d)
for m in range(1,10): 
	for o in range(0,10): 
		if m!=o: 
			for r in range(0,10): 
				if r not in [m,o]: 
					for e in range(0,10): 
						if e not in [m,o,r]: 
							print (m,o,r,e)
for m in range(1,10):
	for o in range(0,10):
		if m!=o:
			for n in range(0,10):
				if n not in [m,o]:
					for e in range(0,10):
						if e not in [m,o,n]:
							for y in range(0,10):
								if y not in [m,o,n,e]:
									print (m,o,n,e,y)
send = s*1000 + e*100 + n*10 + d
more = m*1000 + o*100 + r*10 + e
money = m*10000 + o*1000 + n*100 + e*10 + y
if send + more == money:
	print "  %1d%1d%1d%1d" % (s, e, n, d)
	print " +%1d%1d%1d%1d" % (m, o, r, y)
	print "-------"
	print " %1d%1d%1d%1d%1d" % (m, o, n, e, y)

							


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2