4 ms·

I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never

I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions. The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far your tweets were from 280 chars and where you divided them (e.g., dividing after a full stop is better than after a comma, which is better than between two works, which is way better than midword). With a reasonable cost function, this really seems a textbook dynamic programming example (possibly much more credible than the entering-a-treasure-cave-with-a-rucksack story).

viraptor 6y ago
> no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far your tweets were from 280 chars That immediately brings Tex box badness to my mind. And the related line wrapping algorithm: http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf
- gridspy 6y ago
  Yes, dynamic programming is how I implemented line wrapping for (the help text in) SingStar PS3 also. Good spotting BTW, the line wrapping algorithm (where each tweet is a "line") is a perfect match for the post you are responding to. When doing programming competitions, you're often trying to figure out what standard algorithm is similar to the problem and how you need to tweak it to match.
- giomasce 6y ago
  Yes, I was more or less inspired by TeX's algorithm.
- 72deluxe 6y ago
  Thanks, an interesting paper. I wrote a word-wrapping algorithm once so this will be a good read to see how bad mine was.
deleted 6y ago
[deleted]
dominotw 6y ago
standard 'text justification' dp problem ? Eric's mit video on this : https://www.youtube.com/watch?v=ENyox7kNKeY https://www.youtube.com/watch?v=ENyox7kNKeY leetcode https://leetcode.com/problems/text-justification/ https://leetcode.com/problems/text-justification/
- tzs 6y ago
  (Apologies to people on mobile for the following...) One of the things I miss about Usenet was that nearly everyone read it with a fixed with font so that if you choose your phrasing well so as to make your text come out naturally perfectly justified, it would come out that way for them too. English has so many synonyms and near-synonyms for every word, and so much flexibility in the ordering of words that you can write like this in near real time. You get to the end of a line, find that you're just a little long or short, and you backtrack just a couple words or so most of the time and you can usually find a way that works. In this paragraph, for instance, I was one too long in the first line, but contracting "you are" down to "you're" fixed it. I was short in that last sentence, but inserting "down" fixed it. Perfect justification by inserting extra space is for amateurs. Now we've got all fancy and use variable width fonts and automatic wrapping and posting isn't quite as fun anymore. Give it a try. Use an editor with a fixed font to compose your next post and try to get it to come out perfectly justified without having to insert extra spaces. When you paste it into HN that will get lost, but the composing can be a fun little English puzzle.
  - raphlinus 6y ago
    I read at one point that the typesetters at the New Yorker would work with the copy editors to fix cases of bad justification (huge word space, awkward hyphen). It's rare to see that kind of care, but automatic algorithms are getting better. On topic to the original post, I implemented Knuth-style line breaking in the Android text stack (working with Anish Athalye who was an intern at the time and did the first prototype). There were a bunch of nicely tuned implementations of advanced data structures and algorithms in there.
  - gshubert17 6y ago
chubot 6y ago
Here's a thread on the same article that ended up being largely about dynamic programming :) https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actually https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actu... I still say it is a bad interview question, but there were lots of interesting examples I learned about. - GCC splitting IA-64 instructions - Trellis quantization in lossy video encoding - Knuth-Plass line breaking algorithm (mentioned here too) - Some algorithms I knew about, but which can be considered dynamic programming (I'm not sure how interesting this is): A* search, Dijikstra's shortest path, Myers common subsequence algorithm, transitive closure algorithm I would say the GCC one is most interesting because there's a link to the actual code and comments by the developer. https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia64/ia64.c#L9089 https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia6...
- giomasce 6y ago
  I tried to read the comment, but don't quite understand: what is the problem GCC is trying to solve there?
  - chubot 6y ago
    Sorry I don't have the full context. It seems like some kind of pattern matching over instructions to put them in bundles. I think it could be one of those cases where if you had a more obvious representation you wouldn't need a clever algorithm, but there is probably some other reason (good or not) that instructions are represented that way
  - nwallin 6y ago
    CPUs have some number of individual units that do different things. You'll have a few ALUs that can do stuff like adding, subtracting, xor, and, etc. You'll have some number of units that do floating point math. You'll have a shift unit to do bitshifts. In ye olden days, the CPU would only do one thing at a time, while the rest of the CPU sat idle. x86-64 (and most other architectures) can use multiple units at the same time using what's called a superscalar architecture. There's a hardware unit that figures out what units are in use and what instruction just arrived, and can either send the instruction to ALU0 if it's unused, or ALU1 if ALU0 is in use, etc. But this hardware unit that does scheduling is complex, it takes up space that could be used by other stuff. IA64 aka Itanium, not to be confused with x86-64, is a VLIW (very long instruction word) architecture. The underlying assumption is that the compiler knows in advance what operations it's already emitted, and what operations are coming next, and the compiler can be considerably more complex than the hardware scheduler does. So a VLIW instruction isn't just "add eax,ebx" like x86, it's more like "ALU0: add r12,r48; ALU1: add r93,r42; SHIFT: r60,12; MEM: load r17,r32". (Itanium had 128 registers) The compiler had to do a bunch of stuff that modern CPUs do in hardware. I think it even had to deconflict instructions; like the compiler had to know that an addition takes 3 clock cycles or whatever, so if you used ALU0 on cycle 123772 and then tried to use ALU0 again on 123774 something bad would happen, but don't quote me on that. So at some point the compiler is going to have a DAG of operations that need to get run in a block, and it needs to bundle up those individual operations into bundles of (I think) 4. Sounds dynamic programmy to me. At least I think that's what's going on. It turns out that most code is pretty branchy, which means many lines of code will have multiple entry points. This invalidates the assumption that the compiler knows what operation it just executed. So in practice, VLIW architectures aren't able to achieve their theoretical performance, and superscalar architectures are better.

viraptor 6y ago

> no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far your tweets were from 280 chars That immediately brings Tex box badness to my mind. And the related line wrapping algorithm: http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf

gridspy 6y ago
Yes, dynamic programming is how I implemented line wrapping for (the help text in) SingStar PS3 also. Good spotting BTW, the line wrapping algorithm (where each tweet is a "line") is a perfect match for the post you are responding to. When doing programming competitions, you're often trying to figure out what standard algorithm is similar to the problem and how you need to tweak it to match.
giomasce 6y ago
Yes, I was more or less inspired by TeX's algorithm.
72deluxe 6y ago
Thanks, an interesting paper. I wrote a word-wrapping algorithm once so this will be a good read to see how bad mine was.

deleted 6y ago

[deleted]

dominotw 6y ago

standard 'text justification' dp problem ? Eric's mit video on this : https://www.youtube.com/watch?v=ENyox7kNKeY https://www.youtube.com/watch?v=ENyox7kNKeY leetcode https://leetcode.com/problems/text-justification/ https://leetcode.com/problems/text-justification/

tzs 6y ago
(Apologies to people on mobile for the following...) One of the things I miss about Usenet was that nearly everyone read it with a fixed with font so that if you choose your phrasing well so as to make your text come out naturally perfectly justified, it would come out that way for them too. English has so many synonyms and near-synonyms for every word, and so much flexibility in the ordering of words that you can write like this in near real time. You get to the end of a line, find that you're just a little long or short, and you backtrack just a couple words or so most of the time and you can usually find a way that works. In this paragraph, for instance, I was one too long in the first line, but contracting "you are" down to "you're" fixed it. I was short in that last sentence, but inserting "down" fixed it. Perfect justification by inserting extra space is for amateurs. Now we've got all fancy and use variable width fonts and automatic wrapping and posting isn't quite as fun anymore. Give it a try. Use an editor with a fixed font to compose your next post and try to get it to come out perfectly justified without having to insert extra spaces. When you paste it into HN that will get lost, but the composing can be a fun little English puzzle.
- raphlinus 6y ago
  I read at one point that the typesetters at the New Yorker would work with the copy editors to fix cases of bad justification (huge word space, awkward hyphen). It's rare to see that kind of care, but automatic algorithms are getting better. On topic to the original post, I implemented Knuth-style line breaking in the Android text stack (working with Anish Athalye who was an intern at the time and did the first prototype). There were a bunch of nicely tuned implementations of advanced data structures and algorithms in there.
- gshubert17 6y ago

chubot 6y ago

Here's a thread on the same article that ended up being largely about dynamic programming :) https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actually https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actu... I still say it is a bad interview question, but there were lots of interesting examples I learned about. - GCC splitting IA-64 instructions - Trellis quantization in lossy video encoding - Knuth-Plass line breaking algorithm (mentioned here too) - Some algorithms I knew about, but which can be considered dynamic programming (I'm not sure how interesting this is): A* search, Dijikstra's shortest path, Myers common subsequence algorithm, transitive closure algorithm I would say the GCC one is most interesting because there's a link to the actual code and comments by the developer. https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia64/ia64.c#L9089 https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia6...

giomasce 6y ago
I tried to read the comment, but don't quite understand: what is the problem GCC is trying to solve there?
- chubot 6y ago
  Sorry I don't have the full context. It seems like some kind of pattern matching over instructions to put them in bundles. I think it could be one of those cases where if you had a more obvious representation you wouldn't need a clever algorithm, but there is probably some other reason (good or not) that instructions are represented that way
- nwallin 6y ago
  CPUs have some number of individual units that do different things. You'll have a few ALUs that can do stuff like adding, subtracting, xor, and, etc. You'll have some number of units that do floating point math. You'll have a shift unit to do bitshifts. In ye olden days, the CPU would only do one thing at a time, while the rest of the CPU sat idle. x86-64 (and most other architectures) can use multiple units at the same time using what's called a superscalar architecture. There's a hardware unit that figures out what units are in use and what instruction just arrived, and can either send the instruction to ALU0 if it's unused, or ALU1 if ALU0 is in use, etc. But this hardware unit that does scheduling is complex, it takes up space that could be used by other stuff. IA64 aka Itanium, not to be confused with x86-64, is a VLIW (very long instruction word) architecture. The underlying assumption is that the compiler knows in advance what operations it's already emitted, and what operations are coming next, and the compiler can be considerably more complex than the hardware scheduler does. So a VLIW instruction isn't just "add eax,ebx" like x86, it's more like "ALU0: add r12,r48; ALU1: add r93,r42; SHIFT: r60,12; MEM: load r17,r32". (Itanium had 128 registers) The compiler had to do a bunch of stuff that modern CPUs do in hardware. I think it even had to deconflict instructions; like the compiler had to know that an addition takes 3 clock cycles or whatever, so if you used ALU0 on cycle 123772 and then tried to use ALU0 again on 123774 something bad would happen, but don't quote me on that. So at some point the compiler is going to have a DAG of operations that need to get run in a block, and it needs to bundle up those individual operations into bundles of (I think) 4. Sounds dynamic programmy to me. At least I think that's what's going on. It turns out that most code is pretty branchy, which means many lines of code will have multiple entry points. This invalidates the assumption that the compiler knows what operation it just executed. So in practice, VLIW architectures aren't able to achieve their theoretical performance, and superscalar architectures are better.