• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Optimizing this "send more money" code

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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!

 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Bartender
Posts: 1845
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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" ?
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic