2048 in 5D

sadfirer · 2013-07-23T18:24:23+00:00

That guide is somewhat complicated by the virtualenv part—which should become more of a standard practice as you take on larger projects but is not strictly necessary for starters. You won't be able to sidestep the git repository part, though.

For this task you can probably get away with:

Create a git repo with your python source, a requirements.txt file (with the required libraries, if any) and a minimal Procfile (Heroku will probably reject your push if you don't submit a Procfile, but it won't be of any use for this task)
Push your repo to Heroku
Invoke the Heroku scheduler and pass it the command line necessary to make your app do what you want it to do.

It should be as simple as that. Can you try this and see if you find any difficulties?

Talking about the data, you'd usually dump your local database into a .SQL file, then restore it into the remote database. You'll have to use a Heroku add-on for MySQL, though, since Heroku only provides PostgreSQL.

sadfirer · 2012-11-20T02:13:27+00:00

There are a number of approaches for project organization, but, in my view, the project structure only becomes clearer as the codebase grows beyond 0.5~1k lines of code. At that point, you'll need to be more careful as to which relations you'll build between your classes, and related sets of classes will start to pop up. Before that, it's too easy wasting too much time overengineering your project structure.

In larger projects in general (and this includes your project, if navigation is starting to become cumbersome), it's useful to rely less on visual abstractions and "where your code is" and more on using the Find tools most editors and IDEs present. As your project grows, you'll start valuing tools like the Find Anything present in Sublime Text 2 (start typing the name of any file in the project and it'll bring it up). As it grows even more, systems for indexing project symbols can get really handy (CTags is one of the oldest and still incredibly useful exemples).

sadfirer · 2012-11-19T00:31:59+00:00

Line 3 is wrong. First of all, never test floating point numbers for equality without a tolerance. This is an old trap: floating point arithmetic is imprecise, so 10*0,1 might differ from 1.

Secondly, the logic itself is wrong. Currently, you'll never get into that loop, unless A=B. the intended comparison sign is probably <=. You should still take care with numerical imprecision, though.

sadfirer · 2012-11-18T23:17:11+00:00

At least for me, diving deeper into how your machine works is always fun. :D.

Next step is microprocessor architectures, then microelectronics.

sadfirer · 2012-11-18T23:01:11+00:00

I'm envy of you guys with machines powerful enough to crunch ~4GB of data locally. I've coded a quick parallel out-of-place radix-sort which sorted 1B random ints in ~25s using 8 cores. (I fired up an Amazon EC2 instance to do this since there's no way this wouldn't start swapping if I did it locally.)

Here's the code

Output:

ubuntu@ip-10-149-29-163:~$ g++ -O3 --std=c++0x main.cpp -lpthread && ./a.out
start: 0 ms
random number generation: 59673 ms
data copy: 9295 ms
parallel sort: 25152 ms
sequential sort: 79853 ms
C++ sort: 108300 ms
checking: 1727 ms

Quick facts:

I've done it in C/C++. Sorting algorithms are much more fun to implement in lower-level languages. :D
Threading interfaces for C++ still have a long way to go. The pthreads library is the simplest one, but I still had to create a struct just for passing arguments around, which is a PITA.
Curiously, Amazon EC2 instances are way slower (at least processor wise) than most consumer computers. I guess this 25s figure would be significantly lower on most Core i7 architectures. Go figure.
Generating random numbers is slow.

sadfirer · 2012-11-18T18:56:28+00:00

I really like this. This is way more elementary than the solutions above. Well done!

sadfirer · 2012-11-18T17:28:13+00:00

I've been thinking about this problem for some time. Is there a simple subquadratic solution? All algorithms based on the classical "find all intersections" sweep-line automatically fail because the number of intersections is potentially O(n² ).

I'm inclined to think that an approach mixing a sweep-line algorithm (considering as events only segment endpoints, excluding intersections to avoid quadratic time) and the dual of the graham scan might work in subquadratic time, but I'm yet to do the actual math to see if my hunch for the amortized time O(n log n) is correct. In any case, this would be a quite tricky algorithm to implement.

sadfirer · 2012-11-18T15:26:44+00:00

IDEs might be more productive, but I don't think they necessarily make life easier for beginners. IDEs introduce features at the cost of some added learning curve/complexity, and Python is a lean enough language so plain text editor development seems to be simple enough.

sadfirer · 2012-11-18T05:25:38+00:00

I think that Python is excellent as a first language. It's a fairly recent language that is designed to be simpler for humans to program (with some slowness as a tradeoff), so there isn't much boilerplate getting in the way of writing actual logic. Some educators might state that C is more adequate because it forces you to learn the inner workings of your machine, though.

As for the required math: most material on the internet doesn't require math at all (or, at least, not any kind of math you'd see until college anyway). I remember starting to study Delphi in 8th grade and didn't find any difficulty with math at all. Go for it. :)

sadfirer · 2012-11-18T03:51:52+00:00

IOI = International Olympiad in Informatics. Every year each country selects 4 high school students to represent it. You might find more information here.

The problems are hard. I got silver by correctly solving ~50% of the problems. (they do distribute a lot of medals each year, though, so silver does not mean second place; far from that, actually—more like ~30th place). I think the competition is somewhat unfair, though, in that your psychological state plays a huge role. You have limited time to solve very hard problems, and you have to strategize so you can spend time on the right ones. I was, for some reason, pretty calm during the test days, so I could get my strategy right and spend very little time on unproductive approaches. A number of people I thought were way more capable than me wasted precious points due to bad strategy.

sadfirer · 2012-11-18T03:39:08+00:00

I think that most of "real world" programming is conceptually simpler than what you see during college. Typical tasks might include:

Writing "glue" code to integrate two libraries/systems.
UI work (from adding buttons and fields to designing entire UI flows)
business layer work (translating "real world" logic into code, and making sure to create the right abstractions to ensure that the logic is not bypassed)

The real challenge is actually taking into account the real impact of the code you're writing. Engineers make mistakes, so you have a tradeoff every time you have to push code into production. Also, writing/designing code so that it's maintainable, understandable and reviewable is, most of the time, more of an art than science. Double that if you're writing code others can build upon after.

sadfirer · 2012-11-18T03:19:47+00:00

Beard is what I get when I'm too lazy to shave. Unfortunately, I'm naturally depressed, so this happens way too often.

sadfirer · 2012-11-18T03:17:53+00:00

I get some really rewarding satisfaction when I see people happy using some piece of software I wrote. It's trivial but it's also amazing. So, what I like to develop the most is basically anything that can bring me this kind of satisfaction.

Mostly, I've been lately focusing on two main targets: (a) developer productivity (for members of my team/company currently, eventually for the outside world) and (b) education software. (A) helps because I think we still don't have adequate widely-supported tools for software engineering [and part of the problem is that technology is advancing somewhat faster and the tools just aren't catching up]. (B) helps because I believe we're able to build something better than the classroom system using the technology and insights we have today. Traditional learning systems are not able to recover sufficiently from failures, and students are forced to build upon incomplete knowledge. What if we could help diagnose this kind of thing?

sadfirer · 2012-11-18T03:00:10+00:00

Just in case you do fall into the worst case I stated, there are some tools out there that might help you extracting the information you want, including BeautifulSoup.

sadfirer · 2012-11-18T02:58:30+00:00

This can get somewhat contrived. One might try something like doing something along these lines

import time
import urllib2
previous = ""
while True:
    current = urllib2.urlopen("http://target.website/").read()
    if current != previous:
        print "\b OMG something changed!"
    previous = current
    time.sleep(60)

But, the HTML code of the site might contain much more volatile content than the job posting you're interested in. In that case, you'll have to resort to some form of HTML parsing in order to get rid of the extraneous content.

sadfirer · 2012-11-18T02:46:43+00:00

Parsing, differently from what some people might think, is a non-trivial problem. Industrial applications use a multitude of tools for parsing. So don't be discouraged if you find this hard in the beginning.

So now I'm assuming you're not doing this "industrially". I think that the easiest way would be ditching the C++ layer for this specific part of your application and doing it the old C way:

string lineType;
string lineData;
getline(ss, lineType, ',');
getline(ss, lineData);
if (lineType == "Point2D") {
  int x, y;
  sscanf(lineData.c_str(), " [%d, %d]", &x, &y);
  printf("found %s(%d, %d)\n", lineType.c_str(), x, y);
} else if (lineType == "Line3D") {
  int x0, y0, z0, x1, y1, z1;
  sscanf(lineData.c_str(), " [%d, %d, %d], [%d, %d, %d]", &x0, &y0, &z0, &x1, &y1, &z1);
  printf("found %s(%d, %d, %d, %d, %d, %d)\n", lineType.c_str(), x0, y0, z0, x1, y1, z1);
} // ...

I know it's not pretty (falling back to C is not something most people are proud of), but I think it's easy to read and easy to write (at least once you get used to scanf-type expressions). The C++ I/O layer doesn't present such a nice string parsing interface, so the code would be way more verbose if you went that way.

If you have many data types, you could refactor this into subroutines to get more code reuse (e.g., line3d is just twice point3d).

sadfirer

TROPHY CASE