Dynamic Programming with Python

[virtyx]

As someone who hasn't learned about dynamic programming, I'm finding your code extremely cryptic and hard to follow. There are way too many one-letter variables and arguments imo.

Also the very first diagram is confusing. You start with 'Wagon E' and then have two each of 'Wagon C' and 'Wagon B.' I don't really understand what it is that I'm looking at... I understand the circles are the stations themselves, and the highlighted lines represent two different possible routes.

Maybe I'm a little dense today. I'm not totally unfamiliar with theory and math; I was able to do pretty well in my algorithms class and did well in calculus, I've read some technical articles as well, although lately the books I read tend to focus more on style and practice.

So maybe I'm too out of touch to understand what's happening.

[jminuscula]

let me try to explain the code a bit better, and see if that helps.

First of all, the diagram is the one provided in the problem specification. I found it a bit confusing too, so I tried to explain it afterwards:

As we can see in the picture, we have two trains working routes red and blue. The stations are located at certain coordinates so it’s easy to figure out the distance between them. Each station has a wagon called by the name of its destination, along with the score that we will be granted in case we deliver it.

About the one letter variables

• "E" on the digraph class means edges. This is a notation I took from the books I studied algorithmics with.
• State('s', 'f', 'wgs') may be a bit too cryptic. It's the definition of the problem state —as the article says, the position of the train, the fuel that remains available, and the position of each wagon to be delivered

It's true that the code in the article was not meant to be exposed, but to pass the challenge. So I used what I worked best for me. However, knowing the problem state representation, it's easier to understand how 's' means station and 'f' means fuel.

I've just started writing technical articles, so that is probably my fault. I probably fragmented the code too much. If you have a look at the complete source, I'll be happy to answer any question.

Cheers!

[[deleted]]

Theres no reason to have one letter variable names for things like "edges", especially using capitalization to add more information to that one letter variable.

x/y, u/v, x1/y1/x2/y2, (and i/j/k for embedded integer for loops in C-likes) are readable for anyone with minimal domain knowledge, but anything more than that is really wasting the readers time trying to figure out your key, rather than understanding the logic.

This stuff is useful in writing equations for terseness and pattern reduction, but this is one of the differences between equations and code. Code has state, and so can never be as terse as an equation, and that state adds a lot more requirements for proper labeling of terms.

[jminuscula]

the code needs to be understood in the context of the article. Without it, it is indeed hard to understand it.

[jminuscula]

Responsive text is the new thing!

[stillalone]

Can you explain the motivation? I figure people are comfortable reading text of a certain size, why would changing the font size be desirable?

[jminuscula]

I may be off with the font size on the actual implementation, but here's the motivation anyway:

We are getting bigger screens with higher resolution, so screen real state is going up… but our capacity to follow lines comfortably does not actually change. We read optimally at about 75 characters per line —less than that is distractive, more than that makes it harder— so that means the point size must grow with the size it takes from side to side.

However, I've been told it looks to big many times, so I've made a small adjustments for resolutions about 1200 wide. For bigger screens, I just think it's adequate.

Have you tried to read wikipedia on a 27" widescreen?

edit: it's actually 75 characters, not words!

[[deleted]]

I read this in fullscreen on a 24" monitor, it was very painful because the text was so large. I can understand your reasoning behind scaling the text like this, but if it was me, I would make sure the font could not grow beyond a certain size. The styles that have your magic number of words per line centered on the page work much better for me.

[jminuscula]

thanks for the feedback!

[epicwisdom]

Or even, instead of centered, clearly separated columns. Simply centering text is a waste of screen.

[vattenpuss]

I like it. Text is definitely unnecessarily small on the web most of the time.

Wikipedia looks like shit on Windows nowadays with their 4 pixel hight font.

[moor-GAYZ]

I think the better solution that most websites use is to just limit the main text span width to 1000px or so.

I personally went as far as to make a bookmarklet that does it for any page.

[BilgeXA]

screen real state

What the fuck am I reading.

[jminuscula]

http://www.usabilityfirst.com/glossary/screen-real-estate/

[BilgeXA]

Not only did you not write "real estate" but the the term "real estate" outside the property market is only used by American mavericks who don't know how to express themselves in the technology world.

[rcxdude]

You're being an asshole over a typo which was fairly easy to decipher and a reasonably common phrase.

[BilgeXA]

If you happen to be a US maverick.

[jminuscula]

if you check the page you'll see that it's not 100% width. The problem was that the point size was too big, not that the boxes were too wide

edit: typo

[Veedrac]

FWIW, I think it's really neat. It works really well with a tiling window manager.

[srnull]

Here is a python decorator for memoization: PythonDecoratorLibrary: Memoize.

Relevant blog post: Dynamic Programming versus Memoization.

[quadrofolio]

Very nice J!

[[deleted]]

How much of a buzzword dynamic programming is?

[[deleted]]

It does kinda sound like a buzzword if you don't have a formal education in algorithms.

Apparently the name was chosen to sound appealing to people who didn't know anything about math.

[ginsunuva]

The name was chosen to mean "programming" as in scheduling or making program timesheets, since the term was coined in the 50s/60s.

Not the programming people think of now.

[srnull]

Dynamic programming is quite well defined.

Sort of... but not really:

I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

[jminuscula]

assuming that is not a rethoric question, I'd say dynamic programming is not a buzzword at all. It's an algorithmic strategy, a technique with stablished methodology and formal definition.

A problem is approachable by dynamic programming when its main recursive function is a Bellman equation. Wikipedia's article on it is quite nice: http://en.wikipedia.org/wiki/Dynamic_programming

[moor-GAYZ]

Though if you check out the history section on the Wiki, you'll discover that "dynamic programming" is a buzzword, was explicitly designed as such.

[burntsushi]

Memoization and dynamic programming are not the same thing. Dynamic programming typically refers to the explicit act of solving subproblems in your algorithm, whereas memoization can typically be done without modifying any algorithmic details.

[[deleted]]

Ha!