• Post Reply Bookmark Topic Watch Topic
  • New Topic

Optimizing this "send more money" code  RSS feed

 
Trevor Whitaker
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all, I wasn't sure how I would go about making this code more optimal as in less actions are made to find the result or even making the code smaller. Any help is appreciated!

 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
well yes there are more optimizations, but do you need them?

any way, there are a lot of keys to this problem where you could optimize, but again, why?

it looks like you have covered all possibilities and should be fine.

-steve
 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would be very tempted to see if the generation of possibilites can be done recursively -- and generated in a way, that checks for duplicates as part of the process. It will likely not be faster, but at least it won't have the ridiculous number of nested "for" loops, and nested "if" conditions.... Okay, and the other reason would be just to see if it can be done that way...

Henry
 
Stefan Evans
Bartender
Posts: 1836
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This algorithm goes through every single possibility for every single substitution, and checks for consistency at the lowest level.
The main way to optimise this is to not descend into a nested loop until you have to.
You can quite easily eliminate huge branches of this search tree by doing checks earlier.

Ask your self at each level of looping "is it worth continuing" ?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12542
48
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan Evans wrote:Ask your self at each level of looping "is it worth continuing" ?

Good point...you could move much of the tests on lines 27-32 up into the first line of the respective for loops...I think...something like:


I'm not saying that this is better or easier to understand, but it would save some iterations.
 
Paul Clapham
Sheriff
Posts: 22521
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When I wrote my general-purpose alphametic solver, I started at the top right and worked from top to bottom and from left to right. I also used backtracking -- which means that when I got to a place where there wasn't any valid value for the cell I was trying to fill in, I went back to the previous cell and tried the next value.

So the logic would go something like this:

Try D = 0. Is that okay? Yes.

Try E = 0. Is that okay? No, try E = 1. Is that okay? Yes.

Try Y = 0. Is that okay? No, try Y = 1. Is that okay? (We're always going to have E = Y or else D + E <> Y plus carry so let's skip ahead...) Y = 9 isn't okay, so let's backtrack to E.

Try E = 2. Is that okay? Yes.

(All values of E are going to result in no valid values of Y as long as D = 0, so let's skip ahead...) E = 9 isn't okay, so let's backtrack to D.

Try D = 1. Is that okay? Yes.

And so it goes on, until either you get to the point where you have filled in valid values for all of the cells, or you've backtracked right off the very first cell.

This of course is completely different than the original posted code, but it would run a lot faster.
 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is my first cut at a recursive solution...



It is not very efficient, as it is done with strings. If I get into the mood later, I may take a crack at converting it to use arrays.... or not, I may get lazy.

Henry
 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Same solution, using an int array instead of a string...



Not sure which version is better -- mostly because it added another loop (which was hidden in the string operation previously).

Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!