I've completed most of problem set 4 and the find_best_shifts_rec function works, but it's majorly inefficient. It returns tuples, but if the string is over maybe 50 or so characters, it starts taking a lot of time. When I use print statements, it shows me that the string is being decoded properly (it even decoded the fable -- with a few minor mistakes) but I can't get it to return the tuples associated, since the amount of time it takes to do so seems to grow exponentially. I used recursion, but I also used a loop to go through shifts 0 -27 for my "simpler version of the problem" (i.e. one step up from the base case). I've put it away for a while and am moving on, but I thought I'd ask if there's anything obvious that I must be doing wrong that comes to mind.

Question

I've completed most of problem set 4 and the find_best_shifts_rec function works, but it's majorly inefficient.  It returns tuples, but if the string is over maybe 50 or so characters, it starts taking a lot of time.  When I use print statements, it shows me that the string is being decoded properly (it even decoded the fable -- with a few minor mistakes) but I can't get it to return the tuples associated, since the amount of time it takes to do so seems to grow exponentially.  I used recursion, but I also used a loop to go through shifts 0 -27 for my "simpler version of the problem" (i.e. one step up from the base case).  I've put it away for a while and am moving on, but I thought I'd ask if there's anything obvious that I must be doing wrong that comes to mind.

anonymous · Answer

You can fix the minor errors in the fable decode by only choosing the first 'word' of each valid decode, even if more than one word gets decoded. We'd have to see your code to address the other issues please post your code - using a code pasting site like: - http://dpaste.com - http://pastebin.com - https://gist.github.com/ - http://pastie.org - http://codepad.org - http://ideone.com - http://www.repl.it/ paste your code there and post the link here. select Python syntax highlighting when u paste.

anonymous · Answer

Thanks!  I figured out the problem causing the main issue I was having and will keep working on it, but the info on how to post code is really useful.  Much appreciated.