4 ms·
If you’re looking for a more practical algorithm: this problem can be formulated as a shortest path problem on the graph whose vertices are (n, fret, finger, st
by anderskaseorg 7y ago
If you’re looking for a more practical algorithm: this problem can be formulated as a shortest path problem on the graph whose vertices are (n, fret, finger, string) tuples. A simple dynamic programming solution is to fill out a distance table whose entry distance[n, fret, finger, string] is the optimal cost of the prefix of the melody ending at note n, which can be computed as 0 if n = 1, or in terms of the entries for note n − 1 if n ≥ 2.
- deleted 7y ago[deleted]
- texasbigdata 7y agoHow did you learn this. Math undergrad? Comp sci? Something else?
- ves 7y agoYou would definitely cover some graph and dynamic programming algorithms in a good introductory algorithms course.
- wwright 7y agoThis is one of the only huge benefits of formal CS education — those basic algorithm and discrete math courses make some problems trivial.
- charlus 7y agoThis example is directly mentioned in MIT Introduction to Algorithms, I would recommend it - https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-22-dp-iv-guitar-fingering-tetris-super-mario-bros/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...
- dgellow 7y agoCheck out Coursera's algorithms specialization: https://www.coursera.org/specializations/algorithms https://www.coursera.org/specializations/algorithms
- senshu 7y agoI agree with that and I definitely will try. As explained in the first comment, one of the motivations for the project was to learn constraint programming. The tablature generator could be a nice example to compare different paradigms and algorithms.