Moving Beyond Brute Force — Part 1
This post is a peek into how I tackle complex problems. There are plenty of blogs out there that discuss solutions, but I don’t see many that peel back the curtain on how programmers begin problems of this nature. I am writing not as a programmer who has completed a task, but I am journaling in real-time to display a slightly different perspective.
The problem I am attempting to solve is from ProjectEuler.net:
My gut reaction when seeing this problem is that I need to somehow keep track of three variables; row, column, and value. Dictionaries work well at handling two pieces of data that are related, but what can handle more, an object! This raises a problem that seems attainable. I need to import the .txt file containing all of the numbers, iterate through each value in that file, and create an object for each number with the appropriate information included. I see some potential problems with this approach, but enough planning already, it’s time to give this a shot. I have a trajectory and I am sure that I will adjust this plan soon.
Python is new to me, so I did a quick google-search to wrap my head around the syntax for python classes. I am coming from a Ruby world and so far I notice the def __init__ method is equivalent to def initialize in Ruby. It’s amazing how similar Python and Ruby really are.
After a few minutes of tinkering, I built a program that successfully codes each value in the matrix using a row + column format.
When I run my test, I get an organized set of data that matches the example matrix. I did consider building an array of arrays, but I just don’t like the ideas of getting lost in index numbers. Objects seem cleaner, so I thought I would share that decision.
Now I need to solve the main problem of comparing various routes through the matrix. Before I begin solving any problem, I like to lay out the big hurdles that I see. The first hurdle is that moving to the smallest value at each decision will not give a valid result. In the example, moving from 422 to 121 is the correct option but 111 is a relatively smaller adjacent value. This means that I’m going to have to compare solutions as a whole, not individual decisions. This is a hurdle, because the number of different possible solutions in an 80 by 80 matrix will not compute in a reasonable amount of time.
Comparing large sets will increase processing time, so I need to consider what parameters I could implement to decrease the total processing time for this program.
To recap, I have a set of random objects that are labeled as ‘v##’. v12 represents the value at row one, column two. I have also created a random route generator that returns a list of valid coordinates from the top-left of my matrix to the bottom-right. I am at the point where I need to use my list to generate a total sum. From here, I can begin to compare the total sum of each value from my route. I’m at a stopping point and I plan to finish this project up next week.
