News
Day 16 Comments: re and DP ;-) and a note on next week
Written on 16.12.2022 22:17 by Sven Rahmann
Good evening,
I just wanted to say that today's problem (already part 1) is not so easy. As you may read in the description, you have to figure out a path from your position ('AA') to every valve that can release pressure in open them in an optimal order. Usually part 1 can be brute-forced, but in my input, there were already 15 valves, so naively running all 15! = 1.3 * 1012 permutations is out of the question (at least in pure Python). It may work within a day or so with a reasonably efficient compiled C program. So the challenge is not only to write some good here, but also to come up with a better idea.
You could apply a technique called branch-and-bound: Clearly, some permutations already start so badly that they will never have a chance of beating another already known solution. Then all permutations which share such a bad prefix do not have to be evaluated. This can cut off a large fraction of the search space if you already know a good solution. It is not trivial to implement correctly, though.
Another approach will be discussed in class on Tuesday: dynamic programming (DP). This is also not trivial to get correct on the first attempt, but it also plays nicely with part 2 of today's problem. Of course, we will not discuss this particular problem in class, but other applications of DP. From bioinformatics, you should be familiar with edit distance (or alignment score) computation using DP: optimally solving a large problem by putting together optimal solutions of smaller subproblems, without repeatedly solving the same subproblem more than once.
Another useful module to use today (and on some previous days) is 're' for regular expressions to parse the input file. Unfortunately, regular expressions form their own little language, and there is a learning curve. However, once you know how to write patterns and how to extract the relevant information, parsing the input file becomes much simpler than splitting and piecing everything together. So we will also discuss regular expressions (also regexes, re_s) on Tuesday.
Classes next week
Unfortunately, we lack information about heating in the ZBI building next week. At the moment, we assume that the PC pool will be operational and due to the amount of PCs in the room, it will also be warm. Therefore, the tutorials will probably(!) be on campus. However, if you cannot or do not want to come, no problem: You can always use the alternative channels and/or if there is high demand, we can also offer a video tutorial
Have a nice weekend!