How many paths are there through an m x n matrix, M? Suppose we can only move up and to the right. From (0, 0) to, say, (100, 70) there are an incredible number of paths. What if we add the restriction that you are NOT allowed to pass through point (60, 50)?
Since the question above is from one of my homeworks, I won’t give a solution here! Instead, I want to talk about what I did to quickly and easily calculate solutions of this order or magnitude using DataJoy, the online Python and R editor.
DataJoy is brought to you by the team at ShareLaTeX, the fantastic online TeX platform that I have subscribed to for some months now. My new workflow is to have a DataJoy project open beside my ShareLaTeX project in my browser. Though I tend to prefer a Unix-style workflow with lots of shell interaction, this semester I’m a teaching fellow for CS50 and we’re using an online IDE. So for better or for worse, it’s a browser-based year.
One great advantage of this is that my work is backed up in the cloud and accessible most everywhere. This is great for my because me two Windows 7 machines are getting older and it’s nice to be able to hop onto a school workstation and get to work. I also don’t need to worry about keeping a clean, well-equipped, and updated Python + libraries installation(s) on my local machine. For instance, I don’t need to have numpy + scipy on my space-limited laptop.
To get an answer (not the correct one!) on the order of , I just need to create a Python script in my project that contains the following:
1 2 3 4 5 from scipy.special import comb comb(100, 70, exact=True) Out: 62757830663187746413533383430396L
Did I need that 32-digit long for my solution? No–understanding and showing the combinatorial concepts is more important. But it’s still fun with DataJoy to be able to get huge solutions like this very quickly and with no overhead on my computer.
UPDATE: now that the class is over, here’s a quick solution. We simply take the universe of total paths and subtract out the bad paths. A bad path is one which reaches the forbidden point (60, 50) and then, by the multiplication principle, can take some unique path on the 60 remaining steps (40 to the right, 20 up).