What's the most challenging algorithm you've ever faced
-
Hmmmm, Of course there are faster ways. I would recommend getting your polygon algorithms working first and then move towards optimization. Obviously writing single pixels one at a time will be low performance. Writing sizeof(int) would be faster and SIMD instructions even faster. Same goes for whatever array you are using to store your polygon points. 'sparse' std::bitset would be lowest memory usage but slow as molasses. std::bitset would be low memory but a little bit faster. A huge array of quadword zeros and ones read with SIMD... fast and fat Pick your poison.
I can't use the STL because it's pretty much non-existent on the arduino for anything non-trivial. Part of the reason is due to supporting 8 bit processors and all the constraints that usually come with them. The STL doesn't play well with 8kB of RAM. It's not that it won't work, it's just not really great for that, and if you only have 256kB of nvs program space to work with. Because of that I've had to hand roll things like std::is_same<> :doh: I can't do anything that specifically targets SIMD, because although some of the processors I target do support those instructions, there is no unified way to target it other than to cajole the C++ compiler into generating the right machine code. Frankly, I don't even know what SIMD looks like on, say a 32-bit Tensilica chip but I know it supports it in some form. Same with ARM Cortex CPUs. I'm currently using run lengths so that I draw horizontal scanlines at a time. That cuts down device traffic (often SPI bus traffic), since I can almost always fill a rectangle with a color in less instructions than writing each individual pixel. - horizontal and vertical lines are technically filled rectangles. =) Other than that though, it's still pixel by pixel. What really gets me though, is having to examine each point in the draw destination. I've limited the search by getting a bounding rectangle for the polygon, but all it does is sort the points so it won't deal with "inside out" polygons. I don't rightly care, because that's almost never what you want anyway, and if you did you could just fill the screen before drawing it or something. I can add support for it fairly easily but it seems a waste of time. I'm not worried about scanning the path segments in terms of time or space as I expect paths to be very small in practice. Like less than 30 or so points. You can do more of course, but it's on you because I make you pass in a buffer to use anyway. What I'm concerned about is the brute force check of each pixel in the draw destination to see if it falls within the polygon. That seems ... inelegant to say the least. I got it working less than 10 minutes after you pointed me to it. =)
Real programmers use butterflies
-
Although today it would be quite trivial to do, I reckon that a graphical game of Reversi on a RadioShack TRS80 with only 4K of RAM was my most challenging ever. The computer was pretty much unbeatable on the 'hard' setting.
So old that I did my first coding in octal via switches on a DEC PDP 8
+1 for bringing a game into this instead of code. :laugh:
Real programmers use butterflies
-
I can't use the STL because it's pretty much non-existent on the arduino for anything non-trivial. Part of the reason is due to supporting 8 bit processors and all the constraints that usually come with them. The STL doesn't play well with 8kB of RAM. It's not that it won't work, it's just not really great for that, and if you only have 256kB of nvs program space to work with. Because of that I've had to hand roll things like std::is_same<> :doh: I can't do anything that specifically targets SIMD, because although some of the processors I target do support those instructions, there is no unified way to target it other than to cajole the C++ compiler into generating the right machine code. Frankly, I don't even know what SIMD looks like on, say a 32-bit Tensilica chip but I know it supports it in some form. Same with ARM Cortex CPUs. I'm currently using run lengths so that I draw horizontal scanlines at a time. That cuts down device traffic (often SPI bus traffic), since I can almost always fill a rectangle with a color in less instructions than writing each individual pixel. - horizontal and vertical lines are technically filled rectangles. =) Other than that though, it's still pixel by pixel. What really gets me though, is having to examine each point in the draw destination. I've limited the search by getting a bounding rectangle for the polygon, but all it does is sort the points so it won't deal with "inside out" polygons. I don't rightly care, because that's almost never what you want anyway, and if you did you could just fill the screen before drawing it or something. I can add support for it fairly easily but it seems a waste of time. I'm not worried about scanning the path segments in terms of time or space as I expect paths to be very small in practice. Like less than 30 or so points. You can do more of course, but it's on you because I make you pass in a buffer to use anyway. What I'm concerned about is the brute force check of each pixel in the draw destination to see if it falls within the polygon. That seems ... inelegant to say the least. I got it working less than 10 minutes after you pointed me to it. =)
Real programmers use butterflies
honey the codewitch wrote:
I got it working less than 10 minutes after you pointed me to it. =)
Congratulations. Now you see why I said the geometry was exceedingly simple. :) Geometry has become my new hobby over the last few years. I want you to know something personal. I've been a member here on codeproject for over 18 years. I never make any wild physics/math claims (except one a few months ago). Over a year ago I predicted that the core of gas giants are diffuse and contain multiple closed-packed spheres[^]. I posted a brief mention about it over on Ycombinator[^]. Last month they found that indeed the core of Saturn spans 60% of it's diameter[^]. I am just playing around with n-spheres (14-248) dimensional geometries. That news gives me some confidence that at least some of what I am modeling might be correct. I wish that I could get more people interested in geometry, I am seeing some interesting things. Best Wishes, -David Delaune
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
Not exactly an algorithm but certainly the most challenging I had to do was read data from a LIDAR, at almost 100MB/s (that is mega byte per second), while doing 3D object detection using a third generation embedded core i5 (can not remember if it was a 13W or 17W CPU) with only 1GB of RAM and without dropping any packets/frames/information. The LIDAR required a dedicated gigabit Ethernet connection to the motherboard. Even a switch in the connection would mean packets were dropped. And that CPU struggled to keep up with the data rate let alone do 3D object detection. I'm so glad that implementing path finding and object collision on top of that was not my job :) Best regards
-
honey the codewitch wrote:
I got it working less than 10 minutes after you pointed me to it. =)
Congratulations. Now you see why I said the geometry was exceedingly simple. :) Geometry has become my new hobby over the last few years. I want you to know something personal. I've been a member here on codeproject for over 18 years. I never make any wild physics/math claims (except one a few months ago). Over a year ago I predicted that the core of gas giants are diffuse and contain multiple closed-packed spheres[^]. I posted a brief mention about it over on Ycombinator[^]. Last month they found that indeed the core of Saturn spans 60% of it's diameter[^]. I am just playing around with n-spheres (14-248) dimensional geometries. That news gives me some confidence that at least some of what I am modeling might be correct. I wish that I could get more people interested in geometry, I am seeing some interesting things. Best Wishes, -David Delaune
Randor wrote:
I wish that I could get more people interested in geometry, I am seeing some interesting things
When I went over the high wall back in early 2017 I saw some things - the kinds of things you only see if you're crazy, because apparently I am. Well, the most profound thing I ever saw - in my life - heck, if I live 6 lifetimes I will never see anything so beautiful - is the organic yet fractalish nature of reality itself, in motion. It was infinite - folding back in on itself impossibly - the entire thing like a giant clockwork rose blooming, but exceptionally more beautiful. So yeah, I can appreciate some geometry. :-D
Real programmers use butterflies
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
-
Randor wrote:
I wish that I could get more people interested in geometry, I am seeing some interesting things
When I went over the high wall back in early 2017 I saw some things - the kinds of things you only see if you're crazy, because apparently I am. Well, the most profound thing I ever saw - in my life - heck, if I live 6 lifetimes I will never see anything so beautiful - is the organic yet fractalish nature of reality itself, in motion. It was infinite - folding back in on itself impossibly - the entire thing like a giant clockwork rose blooming, but exceptionally more beautiful. So yeah, I can appreciate some geometry. :-D
Real programmers use butterflies
-
Well, Anyway, now I am looking forward to your next Lounge post explaining how you were mistaken and that your most challenging algorithm was actually easy as pi. Best Wishes, -David Delaune
I'll edit my original, crediting you with my epiphany. Thank you again.
Real programmers use butterflies
-
Can't narrow it down to one. But when I encounter them, it has the following 2 characteristics: 1) I can't remember writing it (but there's unfortunately evidence that I did) 2) It can't be discerned how it works, or ever worked.
There's no *laughing so I don't cry* emoji for this relatable content so I improvised as best I could.
Real programmers use butterflies
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
-
Something bounded by two points. :-\
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
-
Given these truths: o Time is money. o Money is the root of all evil. o Girls cost time and money. We obtain
time = money
_____
money = V evilgirls = time x money
girls = money x money
_____ _____
girls = V evil x V evilgirls = evil
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.Greg Utas wrote:
Given these truths: o Time is money. o Money is the root of all evil. o Girls cost time and money.
Time is worth far more than money ( money can't ( always ) buy me time ) "_The love of_" money is the root of all evil. ( Actually, I'd say power(?) domination(??) ) Proposition 3 I won't touch.
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
find a way to compress 1 inch letters and symbols to fit on a small 2 inch tall screen with only 16K flash memory to work with
