18 ms·

More challenging projects every programmer should try

757 points by pavehawk2007 6y ago

mraza007 6y ago
Interesting projects. I might try ray tracing in python as I’m also exploring a-lot about CGI lately. Has anyone tried CGI if so how’s your experience has been so far
jameskilton 6y ago
I would also recommend, if someone is interested in games, to do Tetris. It's a simple concept that is trickier than expected once you have to figure out the details of how it all comes together.
- corytheboyd 6y ago
  > figure out the details of how it all comes together Damn, that was good.
- drivers99 6y ago
  I wrote a Tetris to learn Python and Pygame. There are correct ways (assuming you want to follow official rules, or parts of it) to do the field size, colors, choose pieces randomly, wall push off, rotations, scoring, etc. https://tetris.fandom.com/wiki/Tetris_Guideline https://tetris.fandom.com/wiki/Tetris_Guideline
- quesera 6y ago
  Nice job slipping that in -- it fits perfectly! And it brings back a fun memory: I wrote MacTetris[1] when I was in high school. This made the computer lab a whole lot more popular during free periods than it had been previously. Two interesting bugs that I recall: * Mathematically rotating pieces around an axis was a terrible idea, but it produced some entertaining artifacts (and made placement much harder!). I replaced the math by precomputed rotation maps for each piece, which was much better. My first pass at the maps introduced a displacement bug, so you could spin the pieces counterclockwise and they would walk in the negative X direction. * I got an angry bug report in the lunch room from a kid who had no reason to know my name. He was having a really great game, and then his score started decreasing with every piece. He felt like his record high score had been stolen from him, and he was upset! I asked "what was your score??". He said "I don't know, but by the time I noticed, it was over 30,000 but it was going DOWN!". Aha..[2] :) [1] I'm sure the statute of limitations has expired on my appropriation of copyrights and trademarks. [2] Back in the day, "int" meant "signed 16-bit integer", which is not the proper data type for a score counter.
- xyzelement 6y ago
  You're getting some great nostalgia responses to this. Here's mine. In highschool, I cranked out a version of tetris in Turbo Pascal that basically worked. Fast forward a few years, I am taking CS219 with Prof Stark (random that I remember the course number) who is hard-core and really tough since it's year 2000 and the class is full of kids who are taking CS cuz it's "the thing" but have no passion or talent for programing. Me, I love programming but I don't have it very much together attendance-wise so I accidentally miss the midterm. OOPS. And obviously there's a "zero make-up test" policy, but surprisingly the prof lets me do the part of it which is a take-home coding assignment, since you can't really benefit from prior knowledge of the questions. My lucky stars - the test is to make a rudimentary subset of - you guessed it - Tetris. Which I had "solved" for myself a year or two earlier. Apparently I was the only one in the class to nail the implementation.
  - phist_mcgee 6y ago
    1. No idea who Prof Stark or CS219 is. Maybe some context here would help. 2. I f a course is super hard, maybe the class isn't 'full' of people who are just doing it to 'be cool, maybe that is your judgement and does not affect reality. 3. Great that you solved Tetris beforehand, but is there a point here? Are you implying that high school you was smarter than university peers? Sorry, but your post seems a little elitist, even thought it's just an anecdote.
    - xyzelement 6y ago
      Holly crap! First, there's not really a point. The preface to the post is that we're sharing nostalgia, right? Second, the "cool" thing is I got lucky that a test that I nearly blew myself up on happened to be on a subject I had already thought about a lot. However your #2 is off-base. There was something like 400% the applicants to the CS program in my university in 1999 vs 1998 and I bet that was true across the board. It was because dot-com was the hot shit and CS became a lot of people's default. The CS department had a tough choice between lowering the bar and "turning away business." This is not a controversial thing.
      - 6y ago
- superbaconman 6y ago
  I wrote this for the xbox 360 back in college. I definitely learned some some skills and would also recommend.
- hertzrat 6y ago
  Speaking of games, I made a decent percent of one recently. It was 4 months of programming character controllers and an ability system, plus 3 weeks of content creation. It came together for a game jam submission (with permission to use the preexisting code). Having to learn everything needed to write this... it was unbelievably educational from a software design point of view If you enjoy horror or third person fantasy adventure games, give it a shot. If you do, please fill out the survey at the end so I can make it better for the next release https://hertzrat.itch.io/a-few-nights-room-and-board https://hertzrat.itch.io/a-few-nights-room-and-board
- tijsvd 6y ago
  Even more fun, make tetris on a microprocessor, play on terminal via serial port. I did this as a diversion during my master's thesis - multiplayer tetris with two microprocessors, communicating through the radio protocol that I was building.
bob1029 6y ago
The database project is quite the rabbit hole if you start chasing performance. I have learned some amazing things about just how fast a 3~4ghz CPU core actually is from this journey.
xwdv 6y ago
Being able to do challenging projects is a cold comfort when by far the most challenging project I’ve ever faced was trying to build something people would pay.
- mooreds 6y ago
  Ah, but that isn't a programming problem (or at least, usually not primarily a programming problem). It's a product and marketing problem.
  - deleted 6y ago
    [deleted]
  - username90 6y ago
    Being a good programmer helps though, technical challenging things tend to have much smaller and worse competition. Like, you probably wont make a lot of money making another 2d platformer no matter how well you code, they are so easy to make that there are millions of them out there already. However if you make a performant and bug free factorio or minecraft clone you will at least get a few thousand people try it and from there it would grow if it is fun.
  - preommr 6y ago
    Learning what problems to solve, how to allocate resources, how to deal with building things from end-to-end, etc. are programming problems.
- Avtomatk 6y ago
  I face the same problem, I think that programmers can be skilled in a lot of different tasks, but for large projects, our two hands and our brain are not enough, no matter how smart you are, you need co-founders, loneliness leads you to procrastinate eternally.
- yudlejoza 6y ago
  You're being downvoted despite being a realist, having integrity, and putting things in perspective. But I can tell you there is no shortage of oversellers in the programming community. A programmer who's really a sleazy salesman at heart would jump at figuring out a fizbuzz solution on their own for the first time in their life, and would proceed to mark it as the biggest achievement in the history of mankind, make a webservice out of it, shout at the top of their lungs on social media, and would start knocking on VC doors. (hint hint: many of them actually get away with something not too different).
ashleyn 6y ago
Write a toy compiler for a basic like language, you'll learn about what your languages are actually doing.
- azhenley 6y ago
  Author here. I agree! That was one of the projects from the original project list that I posted a year ago (https://web.eecs.utk.edu/~azh/blog/challengingprojects.html https://web.eecs.utk.edu/~azh/blog/challengingprojects.html). In fact, this summer I wrote a 3-part tutorial series on implementing a BASIC compiler: Let's make a Teeny Tiny compiler (https://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html https://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html)
  - hedora 6y ago
    Hey! Be more careful when you call things fictitious! My first program ran on a CHIP-8 machine (COSMAC VIP), though I didn’t realize I was targeting an interpreter and not machine code. Great series of articles!
- SilasX 6y ago
  Yes! nand2tetris.org has this. (Also available on Coursera.) You write a compiler for a Java-like language in several steps: a parser that organizes the raw code, then a compiler that emits the virtual machine code, then a translator between the virtual machine code and assembly (and then, between assembly and binary).
- mhh__ 6y ago
  I think, interestingly, that writing the middle of a compiler is actually the best learning as a programmer. Parsing (should be) easy, the backend is hard but well documented and trodden, but the semantic analysis and error handling is where the real murky water is (Especially when you start trying t optimize it, like adding caching or threading or deferred execution)
  - lou1306 6y ago
    I could not agree more. Also, most textbooks and resources on compilers always spend a lot of time on grammars, lexing and parsing. Finding good stuff about intermediate representations, optimization passes and static analysis is harder than it should.
henning 6y ago
As someone who has played with writing trading bots but never traded them with real money, some advice: if your results seem too good to be true, they probably are. Your trading bot may be doing unrealistic things or its results may not be reliable if the following are true: - You are trading in a market with low liquidity or one that is controlled by a small number of market participants. I'm not an expert but I think this would apply more to markets like penny stocks and less to big markets like forex for major currency pairs - You are not taking transaction costs into account or not doing so properly - Your bot makes a low number of trades, making the results close or equivalent to lucky coin flips - Your bot is simply making trades that cannot be executed, or may be doing simulated trades of something that is not actually tradable. This applies to a large number of research papers that assume you can just buy and trade the S&P 500 itself. You can trade ETFs that are tied to an index but an index is not a tradable instrument in of itself. Once you realize this, a lot of papers seem very weird - You are not modelling other aspects of the trading process realistically, such as assuming the bot has infinite funds to trade, allowing it to take unlimited losses and continue trading when in reality you'd be hit with a margin call and your trading would be stopped - Your code is committing any number of data snooping errors where the bot is asked to trade at time A (say the open of a trading session) but has access to future data (say the closing price of that day, future data that would not actually exist in a live environment) - Depending on what you believe about how market conditions change over time, your bot may have worked in the past but would not work if used today. I.e., the market may have adapted to whatever edge your bot may have discovered There are probably lots more pitfalls I don't even know about since I'm not an actual trader. I'm not discouraging anyone from playing around or trying things, of course. I think it's great fun, which is why I do it. Here's the good news: if you realize you don't actually have an edge and avoid risking your hard-earned money, you come out ahead of almost all people who ever trade.
- pjc50 6y ago
  I worked on a unique HFT system which was capable of starting the response packet before the incoming packet's final byte had arrived. Negative latency. If it mispredicted the future, it would simply scramble the trailer and cause the packet to fail UDP checksum. It didn't make money in the real world because the quality of decision that could be made at that speed wasn't good enough.
cghendrix 6y ago
These look fun!
0xbadcafebee 6y ago
> it is really simple to create the basic "database". You can start by using the dictionary data structure that comes with whatever programming language you're using and slap a web API on top of it. Better yet: do it in C. There's no "dictionary" object type so you have to make it yourself. You'll soon learn a whole bunch of fallacies about how those "dictionaries" actually work. After you spent a good deal of time doing that, you can switch to authentication/authorization, logging, storage, tracing, API management, resource quotas, and a raft of distributed computing issues. I recommend basing it on Consul, it has a better general model than etcd.
- CBLT 6y ago
  I'll second this suggestion. Most of my toy projects aren't in C, but every time I design software in C I learn something.
- SilasX 6y ago
  Relatedly, I loved microcorruption.com, a RE/CTF challenge where you have to find exploits at the assembly level to bypass a lock. Some of the problems have hashtables implemented in assembly that you have to work through with a debugger, and it forces you say e.g. "okay, that register is storing the number of bits needed to store the [log of the number of] hashtable elements, which is then masked over the hash function output to know what bucket it needs to look in".
- avl999 6y ago
  I disagree with the C advice. If you don't want to rely on higher level language primitives like Dictionaries and so on there is nothing stopping you from rolling out your own implementations of these data structures in a more sane language (Go, Python, Java, Clojure whatever, anything but C). The project is challenging enough without having to fight segfaults and undefined behaviors.
  - iainmerrick 6y ago
    Writing it in C is good advice if you want to learn C (or you already know C but want to understand it better). It’s bad advice if you don’t want to learn C. Why would you want to learn C? To better understand the machine at a fairly low level. I think there’s still a lot of value in that. I’ve found that programmers who never learned C often don’t fully understand how memory management works, for example (not that that necessarily makes them bad programmers!) Most other non-garbage-collected languages would do the trick, like Rust or C++. But C arguably still has special value in that it’s a lot simpler than either of those -- no higher-level constructs or abstractions to distract you. Maybe Zig will be able to take over that role.
mellosouls 6y ago
Related discussion from the original suggestions a year ago fwiw: https://news.ycombinator.com/item?id=21790779 https://news.ycombinator.com/item?id=21790779
the_cat_kittles 6y ago
another one related to stock trading, but perhaps more interesting- build a simulator for a sport. both baseball and darts lend themselves to markov models, and are simple enough to simulate in some detail. with darts, you can get very close to as accurate as possible. baseball has more weird complications because of the rules. but its fun to do, and to compare to old games to see how well your model does.
- person_of_color 6y ago
  have you made money?
eatonphil 6y ago
I'd also recommend writing an emulator for real or fake (e.g. CHIP-8) hardware. It seems complicated but the core loop gets pretty simple. It ends up giving you a much better view of both assembly and pointer semantics (useful for better understanding C).
- azhenley 6y ago
  That’s in my original list from last year!
  - eatonphil 6y ago
    Ah, good call. I missed the link that this was a follow up post.
4778468d 6y ago
>> automate testing on historical data over long periods of time I want to try this. Where can u get access to historical pricing data that includes pricing changes during the day, not just end of day prices?
simias 6y ago
I would add "build a toy regex engine" to the list. A couple of years ago I implemented a toy regex engine from scratch (building NFAs then turning them into DFAs). I thought it was an enlightening experience because it showed me that the core principles behind regular languages are fairly simple, although you could spend years optimizing and improving your implementation. How do you deal with unicode? How do you modify your implementation to know how many characters you can skip if you don't have a match in order to avoid testing every single position in a file? It demystified the concept of a regex engine for me while at the same time making me realize how impressive the advanced, ultra optimized engines we use and take for granted are.
- schoen 6y ago
  I really enjoyed taking Ullman's Automata course on Coursera. I found it was great for better appreciating topics like * searching * implementation of automata in electronic circuits * challenges of formal specifications for things like protocols and grammars, as well as for verifying their correctness; implementation strategies for applying these specifications * computability and complexity * programming language theory * history of computer science * LANGSEC arguments in addition to having an austere mathematical beauty.
  - theshank 6y ago
    Thank you for sharing this one. I was looking for a course like this! BTW this course is now offered on edx.
    - schoen 6y ago
      Oh, thanks for the update! It looks like the new version is at https://www.edx.org/course/automata-theory https://www.edx.org/course/automata-theory Definitely recommended if you like somewhat dry and mathematical stuff with deep relevance to many areas of computer science. :-)
  - psibi 6y ago
    Somehow I found the course very dry (as compared to other coursera course like Dan Grossman's PL course).
avl999 6y ago
Building a distributed key value store is a fun project and lets you learn tons of real world world stuff. It's a great excuse to get a survey on grokking the design decisions required to build a distributed system and it will truly help one understand why No SQL DBs scale easier than relational ones and the kind of tradeoffs they make to achieve that.
SoSoRoCoCo 6y ago
I wrote a raytracer in 1996, and then a year later used Intel's VTune to speed it up. Just removing unused "return" statements gave me 3x speed increase. Apparently Borland C/C++ wasn't very smart back then. A fun project I did after that was writing a AI frame language to do goal-stack problem solving, specifically with path finding. I connected it to the ray tracer and made movies of spheres having wars. (I used an unlicensed DivX encoder to stitch together thousands of GIFs.)
- thealig 6y ago
  That sounds fun. Do you have code for reference? Also I want to try out building a raytracer sometime as a hobby project, is it advisable to learn some 3d graphic concepts like WebGl and so?
  - carl_dr 6y ago
    Check Ray Tracing In One Weekend out : https://raytracing.github.io/books/RayTracingInOneWeekend.html https://raytracing.github.io/books/RayTracingInOneWeekend.ht... You can very quickly get something on the screen with it, although getting an intuition for how it works may take a little longer and some reading around the concepts it introduces. But it does let you focus on the maths rather than worrying about also learning how Web/OpenGL works too.
timvisee 6y ago
Fantastic list! By the way, adventofcode.com is currently ongoing. Though the challenges are easy compared to the projects in this list, I highly recommend it. It covers problems you might face in big projects. With these small puzzles it's easy to experiment. It prepares you for bigger things.
- macintux 6y ago
  For better or worse, adventofcode relies heavily on mathematical literacy that I suspect is neither all that common among developers nor all that important to most programming jobs. Plus there’s no good way within the context of the puzzles to find out what mathematical trick you need if you don’t already know; you need to go find a virtual water cooler. I may simply be biased because each year it reveals how little I know, but I much prefer interesting programming problems that don’t require me to go to Reddit, read other people’s description of what math is required, go learn the math involved, and then finally implement a solution.
  - davidcbc 6y ago
    There has only been 1 day this year that I think falls into this category (and only one or two last year as well). They are almost all algorithm based rather than math based.
  - windowojji 6y ago
    I'd hardly say it relies _heavily_ on obscure math tricks. Typically there's one or two days which require, perhaps, an undergraduate level of math which people would likely get in an intro class during a CS degree. Most of the problems are around searching a space for some solution or just simulating some state changes. Recent problems involved implementing a higher dimensional version of Conway's game of life[0], a simple arithmetic expression evaluator [1], or a simulator for a simple number game[2] e.g. The most recent one[3] involves solving a jigsaw puzzle by using a simple backtracking search (or any number of other methods). It's a bit complex, but not reliant on a particular math trick. The vast majority of the problems in advent of code shouldn't require any math tricks, though they're often complex and involved, particularly as the month goes on. [0] https://adventofcode.com/2020/day/17 https://adventofcode.com/2020/day/17 [1] https://adventofcode.com/2020/day/18 https://adventofcode.com/2020/day/18 [2] https://adventofcode.com/2020/day/15 https://adventofcode.com/2020/day/15 [3] https://adventofcode.com/2020/day/20 https://adventofcode.com/2020/day/20
xamuel 6y ago
Here's an open-ended programming project which, in a certain formal sense, spans the entire range of all difficulty levels: write an "intuitive ordinal notation" for as large of an ordinal number as you can. What is an "intuitive ordinal notation"? Definition: The set of intuitive ordinal notations is the smallest set P of computer programs with the following property. For every computer program p, if, when p is run, all of p's outputs are elements of P, then p is in P. So "End.", the program which immediately ends with no outputs, is vacuously in P (all of its outputs are in P, because it has no outputs). It notates the ordinal 0. Likewise, "Print(`End.')" is in P, because its sole output, "End.", is in P; it notates the ordinal 1. Likewise, "Print(`Print(End.')')" is in P, notating the ordinal 2. And so on. The above can be short-circuited: "Let X=`End'; While(True){Print(X); X=`Print(\`'+X+`\')'}". This program outputs "End.", "Print(`End.')", "Print(`Print(`End.')')", and so on forever, all of which are in P, so this program itself is in P. It notates omega, the smallest infinite ordinal. Here's a library of examples in Python, currently going up to a notation for the ordinal omega^omega: https://github.com/semitrivial/IONs https://github.com/semitrivial/IONs
- carapace 6y ago
  Oh that's cool.
  - xamuel 6y ago
    As an example to illustrate how this initially-simple-looking project spans the whole range of all possible difficulty levels: suppose you had a source-code for a superhuman flawless obedient honest AGI, call it HAL. From that source-code, you could derive a source code X for: "Print all the computer programs which HAL would list if HAL were commanded: 'Enumerate every computer program which you know to be an intuitive ordinal notation'". Since we're assuming HAL is obedient and honest, all of X's outputs will be intuitive ordinal notations, so X itself is an intuitive ordinal notation: you could say it notates "the ordinal of HAL". So this innocent-looking exercise in fact touches the most ambitious possible projects, even "Design a perfect superhuman AGI" :-)
- ianai 6y ago
  They’re not sequential though so write a program which offers a way to check whether an output is in the solution set and stores the input and always returns true.
acutesoftware 6y ago
Writing even an extremely simple game without using a game engine or dedicated game library is quite an eye opener. Make a small 2D platform game, and it covers so many areas (and it is a lot of fun!).
fspear 6y ago
I would add an emulator to the list.I've always struggled to figure out how these are built from scratch. A long time ago I wanted to code a neogeo emulator but gave up before I even started, I didn't have a clue where to begin. I am amazed at anyone that can code an emulator from scratch.
- tuankiet65 6y ago
  Their previous article mentioned it: https://web.eecs.utk.edu/~azh/blog/challengingprojects.html https://web.eecs.utk.edu/~azh/blog/challengingprojects.html.
- deleted 6y ago
  [deleted]
- sterlind 6y ago
  they're really simple, in their basic form and for simple ISAs! it mostly boils down to keeping a bunch of registers and a giant switch statement. Each case simply implements the opcode. You have an array of bytes for the memory, and some emulated devices (e.g. trigger a screen update when the framebuffer memory gets changed, or set the instruction pointer to a handler when a key gets pressed.) It gets hard when instructions need lots of decoding, or you have 3d graphics hardware to emulate, or if you have something like a BIOS, or if you want to JIT. I'm actually eyeing implementing a console on an FPGA as my holiday project, with something like Chisel.
  - schoen 6y ago
    It seems like a lot of the complexity may also come in when you have important circuits to emulate other than the CPU. In that case you'd have more to worry about in terms of timing, dataflow, and synchronization. And some platforms might conceivably have analog circuits that play an important role too, although I guess you might be able to abstract that out by trying to create a rough digital functional equivalent even if it isn't completely faithful to the behavior of the analog part.
    - 6y ago
userbinator 6y ago
IMHO a text-based browser isn't exactly in the "challenging" category, as it basically amounts to stripping all the HTML tags out and doing some very simple transformations (like replacing <br>'s with newlines.) Then again, one of the things I've been working on intermittently for the past few years is a graphical (CSS2+) browser, which is definitely in the challenging category. There are some other public efforts too: https://github.com/lexborisov/Modest https://github.com/lexborisov/Modest https://github.com/litehtml https://github.com/litehtml https://github.com/ArthurHub/HTML-Renderer https://github.com/ArthurHub/HTML-Renderer Along the same lines, some other challenging projects I recommend are to write decoders/renderers for existing formats like MP3, MP4, PDF, etc.
- Forge36 6y ago
  It looks straightforward until you hit a couple of edge cases. Examples: test <1 becomes test 1 Test< 2 becomes test 2 Test <a becomes test Test < b becomes test b (From memory) What about: Test <fakeTag>? Per tests i did, "test " was expected however "test <fakeTag>” was seen as the plaintext version suggesting there's a list of valid tags which is filtering the behavior.
  - userbinator 6y ago
    That's because '<' needs to be followed by [!/?a-zA-Z] to be recognised as a tag start. Otherwise it is a literal '<'. The full details are in here somewhere: https://www.w3.org/TR/2011/WD-html5-20110113/tokenization.html https://www.w3.org/TR/2011/WD-html5-20110113/tokenization.ht...
  - benibela 6y ago
    I have been stuck on such these edge cases for almost 15 years building my own HTML parser It is always working on all the HTML files I have, but then people make new HTML files with other issues.
- zerf 6y ago
  To this list I would add "Web Browser Engineering" [0] which is a textbook / browser engine that is currently being written by Dr. Pavel Panchekha at the University of Utah. The code for the book and browser is available on GitHub [1] and a more current bleeding edge draft is also published [2]. The book guides the reader in implementing a graphical web browser, starting with HTTP and HTML then moving on to the layout, the box model, CSS, browser chrome, forms, and scripts. [0] https://browser.engineering https://browser.engineering [1] https://github.com/pavpanchekha/emberfox https://github.com/pavpanchekha/emberfox [2] https://browser.engineering/draft/ https://browser.engineering/draft/
Waterluvian 6y ago
Writing a Game Boy emulator has been the most fulfilling and interesting programming project in my life. I love, most of all, how modular the project is. I can do an hour here or there and make meaningful progress. I'm really eager to discover other very large programming projects that break down into sensible bites so well.
- windowojji 6y ago
  I worked on a game boy emulator a while ago to learn C. I did pretty well and was able to run most games I came across just fine, but never got audio working...I just couldn't understand any of the stuff online about how it worked, and was unable to find any good resources that walked through how audio emulation in general worked, much less game boy's version.
- shhsshs 6y ago
  I had never considered an emulator to be anywhere inside of the realm of possible projects I could take on for fun. I just thought it would be too complex without having a ton of very specific knowledge. Your comment prompted me to go look up some other attempts, and I’m really glad I did. It seems much more approachable to me now. Thanks!
  - Waterluvian 6y ago
    Consider starting with a CHIP-8 emulator. It's a perfect size for starting out and touches on a lot of important concepts you'll apply to the next emulator.
tracyhenry 6y ago
A great compilation: https://github.com/danistefanovic/build-your-own-x https://github.com/danistefanovic/build-your-own-x
- 082349872349872 6y ago
  Building your own dogfood (if you use it daily, code a quick-and-dirty one) is a good way to learn that by holding the right end of the exponential, 80-20 solutions can easily be closer to 1-99+ in terms of manpower and code size. (the flip side of 80-20 is: "all systems are fault tolerant, it's just that in most of them, the human is the component which tolerates the faults") Of my IT daily drivers, I've done toy: - web browser / server - email client - document formatter - text editor - window manager - 3D / 2D graphic slicers/rasterizers w/ alphabetic fonts - shell - interpreters / compilers - operating system - VHDLish CPU - various data encodings (Hamming, MFM, etc.) - discrete transistor logic (when I was just starting to program, I discovered the home directory of a colleague of my father's contained many experiments of this kind, and reading his work taught me C)
deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
person_of_color 6y ago
How about designing your own virtual memory system
- tsjq 6y ago
  that's like Prof Frank Mueller level
rex64 6y ago
I recently went through the process of creating a ray tracer project from zero for learning purposes. It was a humbling and eye-opening experience. I've written an article[0] to explain my process in detail if you're interested. [0] https://alessandrocuzzocrea.com/how-i-made-a-ray-tracer/ https://alessandrocuzzocrea.com/how-i-made-a-ray-tracer/
jackschultz 6y ago
Instead of a stock trading bot, go for daily fantasy sports contests. It can cover pretty much all parts of programming. Web scraping to gather data, databases for storing it, ML for analyzing, front and backend web dev to show the daily information and adjust. And instead of having to deal with trading regulations, contests can be really small and easy to enter. There are daily contests for 5 cents an entry, and you can enter 150 optimized lineups from an uploaded csv for $7.50 a day. You can really learn a ton.
- nsomaru 6y ago
  Which services would you recommend which are developer friendly? Could you describe your approach? What type of information would you scrape?
rdescartes 6y ago
I would recommend choosing a long enough time (e.g. 3 months) to contribute an open source project you are using, especially you are not familiar to that domain. I learnt a lot from modern compiler stuffs by contribute to rust-analzyer.
kunalpowar1203 6y ago
Thanks for following up with this list after your previous one. I spent a great deal of my time (including some office time) on writing a Chip-8 emulator thanks to your previous list :D
forgotmypw17 6y ago
I would add a basic feature-complete website which works on every mainstream browser starting with Mosaic. It's much easier than it may seem, architecting it is interesting, and there is a lot of "last 10%" stuff which keeps it fun as long as you keep going. In the demystifying area, it demystified HTML and JS history for me, forced me to use with a minimal toolkit, and taught me how to build "modern" JS features in ways which will not break browsers which don't know how to do them or have them disabled.
fergie 6y ago
I would strongly recommend building something that you yourself think is cool, and not feeling that you have to conform to what other people tell you to do.
- purplecats 6y ago
  why not, that's only one direct step removed from thinking that conformity to popular beliefs is cool.
- watwut 6y ago
  Most people draw blank when they are trying to come up with project idea. They are programmers, not creative after all. Which is why lists like this help.
  - anonytrary 6y ago
    If you are trying to think of an idea, you're already doing it wrong. The best ideas are motivated by problems you encounter yourself, not by trying to think of ideas. This is the biggest mistake you see with 20-something founders. Best way to come up with ideas is to use existing solutions and realize how shitty they are. Pretty much every single company was formed this way. > They are programmers, not creative after all. Damn, this is a bold comment on HN. Since when does profession determine how creative you are? I've met "programmers" and "geeks" who are more creative than "artists". Your profession has little to do with your innate creativity -- it just determines how you are able to express that creativity. Unpopular opinion, but lists like this are stupid for people who are trying to build companies. You have to try things and be pissed off at the status quo to find real problems. Nobody is going to find real problems for you, in the same way that no quant school is going to reveal their hedge fund's trading strategy to you. Finding ideas in a list is the last advice I would give to anyone. If it's public, it's probably not a profitable idea.
    - T_O_T_O 6y ago
      For a beginning programmer, these could be good projects. For someone with a lot of experience, I mostly agree with your comment.
djeiasbsbo 6y ago
For some simpler projects, I can only recommend doing some digital signal processing. For example, an audio signal is just a list of values, so you can do things like: - Count the number of zero crossings - Find out where they are - Create any shape of wave by adding together multiple sine waves - Hard clip the signal - Stretch a signal and interpolate it with new samples - Invert and revert a signal For level 2, you can start processing "live": - Create a sine synthesizer - Create a small ring buffer of samples - Find out how to output that audio (system audio, soundcard) - Add MIDI support - Add polyphony support DSP gets hard once it has to be in real time and the latency has to be minimal. It's great exercise to mess around with it.
- jamil7 6y ago
  I came across this area recently while trying to build an iOS app that could reliably detect knocks or taps on the body of the phone, I was ultimately unsuccessful but I learned a lot about collecting and analysing microphone and gyroscope data. Also built some nice tooling for collecting live iOS sensor data and transmitting it to prometheus/grafana over mqtt.
  - djeiasbsbo 6y ago
    That sounds interesting. A cool project would be to inspect gyroscope data when the iOS keyboard is in use. Maybe it would be possible to create a keylogger based on it. I guess it would depend on how good the data is and which keyboard is being used. I know that this is possible on Android.
anonytrary 6y ago
This article is aimed towards students. It's great advice for students who are in college, know very little, and want to improve their CS skills. It's poor advice for someone who already has a STEM degree and wants to build something useful and profitable. If you already know how these things work, your time is better spent on the "edge of the circle": http://matt.might.net/articles/phd-school-in-pictures/ http://matt.might.net/articles/phd-school-in-pictures/ which applies to businesses and startups as well. If you're in the latter group -- you've already got the skills to build real shit. Don't waste your time on homework problems. Find a problem you have and build a solution for it. Don't listen to people who tell you to work on homework problems that have already been solved; it's a complete waste of your time if you already know the fundamentals. As for stock trading bots -- if you don't have a mathematics degree or equivalent (e.g. having incredible math skills), don't even bother. You won't be profitable, and you will learn nothing useful in the process, because you will approach the problem as a naive CS student would. Smarter people than you have made trading bots and have failed miserably. Without having an extremely strong foundation in mathematics, your trading bot will amount to nothing more than a futile exercise in gluing APIs together.
- imtringued 6y ago
  You should grow a second spike. I'm at the point where visual design skills are a greater bottleneck than my computer science skills. I can build purely functional CAD models but man, making them functional AND look good is the real challenge.
  - anonytrary 6y ago
    Agreed. Everyone should aim to have 3-4 spikes they are passionate about. For every spike you have, you become exponentially more of a domain expert at the problems that are at the intersection of those spikes.
    - PeterisP 6y ago
      Yes, proper senior expertise often looks like being a jack of all trades and a master of three or so.
trustfundbaby 6y ago
What do folks think about implementing a web crawler that you can send to a website and it indexes every internal url on the site. I remember sitting down to write one 100 years ago now, and finding it to be much trickier than I thought it would be.
- tsjq 6y ago
  that's interesting. grab only the URLs, not the content?
  - trustfundbaby 6y ago
    right, but of course to do that, you'd have to grab the content to parse it :)
KlimYadrintsev 6y ago
What is the main reason of trying this projects? To learn something new? To train existing skills? Or is it to benefit financially from those projects?
arendtio 6y ago
What I am really missing is some kind of real-time AI. A decade ago, I have coded some bot for an ego-shooter with RTS elements and have learnt so much from it (while having a lot of fun). It starts with basic things like waypoint systems vs. area awareness systems plus the relevant routing algorithms like A*, but goes on to organizing a group of players and finding good strategies. And all of that with a limited time budget and an changing environment around you. Last but not least, you want to emulate human behavior which is probably the hardest part as it includes changing you behavior according to your situation (don't run straight against a wall for 10 seconds) but also taking into account the weaknesses as e.g. humans can't aim perfectly. Granted, what I have done has a huge field of challenges, but even with a 2D engine I think you can learn a lot from the experience.
- drummersbrother 6y ago
  You may be interested in the game Screeps. From their website (name +.com): "It's an open-source game for programmers, wherein the core mechanic is programming your units' AI. You control your colony by writing JavaScript. "
  - joycian 6y ago
    I looked this up and it seems very cool. Do you (or anybody else) know any more of these games or environments that can be controlled by code?
deleted 6y ago
[deleted]
whatever_dude 6y ago
My own favorite is an equation parser. Before attempting to do so I thought it was implemented as a simple seek over the string, maybe a bunch of regex stuff. I guess it can be done that way, at the cost of growing complexity; but the proper solution (with a stack, etc) is so elegant (makeing it easy to add functions, operators, parenthesis, variables, etc) that it really makes one appreciate the value of good, thoughtful engineering.
known 6y ago
https://en.wikipedia.org/wiki/List_of_lists_of_lists https://en.wikipedia.org/wiki/List_of_lists_of_lists FTW
mjgs 6y ago
Awesome couple of articles.

757 points by pavehawk2007 6y ago

Interesting projects. I might try ray tracing in python as I’m also exploring a-lot about CGI lately. Has anyone tried CGI if so how’s your experience has been so far

jameskilton 6y ago

I would also recommend, if someone is interested in games, to do Tetris. It's a simple concept that is trickier than expected once you have to figure out the details of how it all comes together.

corytheboyd 6y ago
> figure out the details of how it all comes together Damn, that was good.
drivers99 6y ago
I wrote a Tetris to learn Python and Pygame. There are correct ways (assuming you want to follow official rules, or parts of it) to do the field size, colors, choose pieces randomly, wall push off, rotations, scoring, etc. https://tetris.fandom.com/wiki/Tetris_Guideline https://tetris.fandom.com/wiki/Tetris_Guideline
quesera 6y ago
Nice job slipping that in -- it fits perfectly! And it brings back a fun memory: I wrote MacTetris[1] when I was in high school. This made the computer lab a whole lot more popular during free periods than it had been previously. Two interesting bugs that I recall: * Mathematically rotating pieces around an axis was a terrible idea, but it produced some entertaining artifacts (and made placement much harder!). I replaced the math by precomputed rotation maps for each piece, which was much better. My first pass at the maps introduced a displacement bug, so you could spin the pieces counterclockwise and they would walk in the negative X direction. * I got an angry bug report in the lunch room from a kid who had no reason to know my name. He was having a really great game, and then his score started decreasing with every piece. He felt like his record high score had been stolen from him, and he was upset! I asked "what was your score??". He said "I don't know, but by the time I noticed, it was over 30,000 but it was going DOWN!". Aha..[2] :) [1] I'm sure the statute of limitations has expired on my appropriation of copyrights and trademarks. [2] Back in the day, "int" meant "signed 16-bit integer", which is not the proper data type for a score counter.
xyzelement 6y ago
You're getting some great nostalgia responses to this. Here's mine. In highschool, I cranked out a version of tetris in Turbo Pascal that basically worked. Fast forward a few years, I am taking CS219 with Prof Stark (random that I remember the course number) who is hard-core and really tough since it's year 2000 and the class is full of kids who are taking CS cuz it's "the thing" but have no passion or talent for programing. Me, I love programming but I don't have it very much together attendance-wise so I accidentally miss the midterm. OOPS. And obviously there's a "zero make-up test" policy, but surprisingly the prof lets me do the part of it which is a take-home coding assignment, since you can't really benefit from prior knowledge of the questions. My lucky stars - the test is to make a rudimentary subset of - you guessed it - Tetris. Which I had "solved" for myself a year or two earlier. Apparently I was the only one in the class to nail the implementation.
- phist_mcgee 6y ago
  1. No idea who Prof Stark or CS219 is. Maybe some context here would help. 2. I f a course is super hard, maybe the class isn't 'full' of people who are just doing it to 'be cool, maybe that is your judgement and does not affect reality. 3. Great that you solved Tetris beforehand, but is there a point here? Are you implying that high school you was smarter than university peers? Sorry, but your post seems a little elitist, even thought it's just an anecdote.
  - xyzelement 6y ago
    Holly crap! First, there's not really a point. The preface to the post is that we're sharing nostalgia, right? Second, the "cool" thing is I got lucky that a test that I nearly blew myself up on happened to be on a subject I had already thought about a lot. However your #2 is off-base. There was something like 400% the applicants to the CS program in my university in 1999 vs 1998 and I bet that was true across the board. It was because dot-com was the hot shit and CS became a lot of people's default. The CS department had a tough choice between lowering the bar and "turning away business." This is not a controversial thing.
    - 6y ago
superbaconman 6y ago
I wrote this for the xbox 360 back in college. I definitely learned some some skills and would also recommend.
hertzrat 6y ago
Speaking of games, I made a decent percent of one recently. It was 4 months of programming character controllers and an ability system, plus 3 weeks of content creation. It came together for a game jam submission (with permission to use the preexisting code). Having to learn everything needed to write this... it was unbelievably educational from a software design point of view If you enjoy horror or third person fantasy adventure games, give it a shot. If you do, please fill out the survey at the end so I can make it better for the next release https://hertzrat.itch.io/a-few-nights-room-and-board https://hertzrat.itch.io/a-few-nights-room-and-board
tijsvd 6y ago
Even more fun, make tetris on a microprocessor, play on terminal via serial port. I did this as a diversion during my master's thesis - multiplayer tetris with two microprocessors, communicating through the radio protocol that I was building.

bob1029 6y ago

The database project is quite the rabbit hole if you start chasing performance. I have learned some amazing things about just how fast a 3~4ghz CPU core actually is from this journey.

xwdv 6y ago

Being able to do challenging projects is a cold comfort when by far the most challenging project I’ve ever faced was trying to build something people would pay.

mooreds 6y ago
Ah, but that isn't a programming problem (or at least, usually not primarily a programming problem). It's a product and marketing problem.
- deleted 6y ago
  [deleted]
- username90 6y ago
  Being a good programmer helps though, technical challenging things tend to have much smaller and worse competition. Like, you probably wont make a lot of money making another 2d platformer no matter how well you code, they are so easy to make that there are millions of them out there already. However if you make a performant and bug free factorio or minecraft clone you will at least get a few thousand people try it and from there it would grow if it is fun.
- preommr 6y ago
  Learning what problems to solve, how to allocate resources, how to deal with building things from end-to-end, etc. are programming problems.
Avtomatk 6y ago
I face the same problem, I think that programmers can be skilled in a lot of different tasks, but for large projects, our two hands and our brain are not enough, no matter how smart you are, you need co-founders, loneliness leads you to procrastinate eternally.
yudlejoza 6y ago
You're being downvoted despite being a realist, having integrity, and putting things in perspective. But I can tell you there is no shortage of oversellers in the programming community. A programmer who's really a sleazy salesman at heart would jump at figuring out a fizbuzz solution on their own for the first time in their life, and would proceed to mark it as the biggest achievement in the history of mankind, make a webservice out of it, shout at the top of their lungs on social media, and would start knocking on VC doors. (hint hint: many of them actually get away with something not too different).

ashleyn 6y ago

Write a toy compiler for a basic like language, you'll learn about what your languages are actually doing.

azhenley 6y ago
Author here. I agree! That was one of the projects from the original project list that I posted a year ago (https://web.eecs.utk.edu/~azh/blog/challengingprojects.html https://web.eecs.utk.edu/~azh/blog/challengingprojects.html). In fact, this summer I wrote a 3-part tutorial series on implementing a BASIC compiler: Let's make a Teeny Tiny compiler (https://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html https://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html)
- hedora 6y ago
  Hey! Be more careful when you call things fictitious! My first program ran on a CHIP-8 machine (COSMAC VIP), though I didn’t realize I was targeting an interpreter and not machine code. Great series of articles!
SilasX 6y ago
Yes! nand2tetris.org has this. (Also available on Coursera.) You write a compiler for a Java-like language in several steps: a parser that organizes the raw code, then a compiler that emits the virtual machine code, then a translator between the virtual machine code and assembly (and then, between assembly and binary).
mhh__ 6y ago
I think, interestingly, that writing the middle of a compiler is actually the best learning as a programmer. Parsing (should be) easy, the backend is hard but well documented and trodden, but the semantic analysis and error handling is where the real murky water is (Especially when you start trying t optimize it, like adding caching or threading or deferred execution)
- lou1306 6y ago
  I could not agree more. Also, most textbooks and resources on compilers always spend a lot of time on grammars, lexing and parsing. Finding good stuff about intermediate representations, optimization passes and static analysis is harder than it should.

henning 6y ago

As someone who has played with writing trading bots but never traded them with real money, some advice: if your results seem too good to be true, they probably are. Your trading bot may be doing unrealistic things or its results may not be reliable if the following are true: - You are trading in a market with low liquidity or one that is controlled by a small number of market participants. I'm not an expert but I think this would apply more to markets like penny stocks and less to big markets like forex for major currency pairs - You are not taking transaction costs into account or not doing so properly - Your bot makes a low number of trades, making the results close or equivalent to lucky coin flips - Your bot is simply making trades that cannot be executed, or may be doing simulated trades of something that is not actually tradable. This applies to a large number of research papers that assume you can just buy and trade the S&P 500 itself. You can trade ETFs that are tied to an index but an index is not a tradable instrument in of itself. Once you realize this, a lot of papers seem very weird - You are not modelling other aspects of the trading process realistically, such as assuming the bot has infinite funds to trade, allowing it to take unlimited losses and continue trading when in reality you'd be hit with a margin call and your trading would be stopped - Your code is committing any number of data snooping errors where the bot is asked to trade at time A (say the open of a trading session) but has access to future data (say the closing price of that day, future data that would not actually exist in a live environment) - Depending on what you believe about how market conditions change over time, your bot may have worked in the past but would not work if used today. I.e., the market may have adapted to whatever edge your bot may have discovered There are probably lots more pitfalls I don't even know about since I'm not an actual trader. I'm not discouraging anyone from playing around or trying things, of course. I think it's great fun, which is why I do it. Here's the good news: if you realize you don't actually have an edge and avoid risking your hard-earned money, you come out ahead of almost all people who ever trade.

pjc50 6y ago
I worked on a unique HFT system which was capable of starting the response packet before the incoming packet's final byte had arrived. Negative latency. If it mispredicted the future, it would simply scramble the trailer and cause the packet to fail UDP checksum. It didn't make money in the real world because the quality of decision that could be made at that speed wasn't good enough.

cghendrix 6y ago

These look fun!

0xbadcafebee 6y ago

> it is really simple to create the basic "database". You can start by using the dictionary data structure that comes with whatever programming language you're using and slap a web API on top of it. Better yet: do it in C. There's no "dictionary" object type so you have to make it yourself. You'll soon learn a whole bunch of fallacies about how those "dictionaries" actually work. After you spent a good deal of time doing that, you can switch to authentication/authorization, logging, storage, tracing, API management, resource quotas, and a raft of distributed computing issues. I recommend basing it on Consul, it has a better general model than etcd.

CBLT 6y ago
I'll second this suggestion. Most of my toy projects aren't in C, but every time I design software in C I learn something.
SilasX 6y ago
Relatedly, I loved microcorruption.com, a RE/CTF challenge where you have to find exploits at the assembly level to bypass a lock. Some of the problems have hashtables implemented in assembly that you have to work through with a debugger, and it forces you say e.g. "okay, that register is storing the number of bits needed to store the [log of the number of] hashtable elements, which is then masked over the hash function output to know what bucket it needs to look in".
avl999 6y ago
I disagree with the C advice. If you don't want to rely on higher level language primitives like Dictionaries and so on there is nothing stopping you from rolling out your own implementations of these data structures in a more sane language (Go, Python, Java, Clojure whatever, anything but C). The project is challenging enough without having to fight segfaults and undefined behaviors.
- iainmerrick 6y ago
  Writing it in C is good advice if you want to learn C (or you already know C but want to understand it better). It’s bad advice if you don’t want to learn C. Why would you want to learn C? To better understand the machine at a fairly low level. I think there’s still a lot of value in that. I’ve found that programmers who never learned C often don’t fully understand how memory management works, for example (not that that necessarily makes them bad programmers!) Most other non-garbage-collected languages would do the trick, like Rust or C++. But C arguably still has special value in that it’s a lot simpler than either of those -- no higher-level constructs or abstractions to distract you. Maybe Zig will be able to take over that role.

mellosouls 6y ago

Related discussion from the original suggestions a year ago fwiw: https://news.ycombinator.com/item?id=21790779 https://news.ycombinator.com/item?id=21790779

the_cat_kittles 6y ago

another one related to stock trading, but perhaps more interesting- build a simulator for a sport. both baseball and darts lend themselves to markov models, and are simple enough to simulate in some detail. with darts, you can get very close to as accurate as possible. baseball has more weird complications because of the rules. but its fun to do, and to compare to old games to see how well your model does.

person_of_color 6y ago
have you made money?

eatonphil 6y ago

I'd also recommend writing an emulator for real or fake (e.g. CHIP-8) hardware. It seems complicated but the core loop gets pretty simple. It ends up giving you a much better view of both assembly and pointer semantics (useful for better understanding C).

azhenley 6y ago
That’s in my original list from last year!
- eatonphil 6y ago
  Ah, good call. I missed the link that this was a follow up post.

4778468d 6y ago

>> automate testing on historical data over long periods of time I want to try this. Where can u get access to historical pricing data that includes pricing changes during the day, not just end of day prices?

simias 6y ago

I would add "build a toy regex engine" to the list. A couple of years ago I implemented a toy regex engine from scratch (building NFAs then turning them into DFAs). I thought it was an enlightening experience because it showed me that the core principles behind regular languages are fairly simple, although you could spend years optimizing and improving your implementation. How do you deal with unicode? How do you modify your implementation to know how many characters you can skip if you don't have a match in order to avoid testing every single position in a file? It demystified the concept of a regex engine for me while at the same time making me realize how impressive the advanced, ultra optimized engines we use and take for granted are.

schoen 6y ago
I really enjoyed taking Ullman's Automata course on Coursera. I found it was great for better appreciating topics like * searching * implementation of automata in electronic circuits * challenges of formal specifications for things like protocols and grammars, as well as for verifying their correctness; implementation strategies for applying these specifications * computability and complexity * programming language theory * history of computer science * LANGSEC arguments in addition to having an austere mathematical beauty.
- theshank 6y ago
  Thank you for sharing this one. I was looking for a course like this! BTW this course is now offered on edx.
  - schoen 6y ago
    Oh, thanks for the update! It looks like the new version is at https://www.edx.org/course/automata-theory https://www.edx.org/course/automata-theory Definitely recommended if you like somewhat dry and mathematical stuff with deep relevance to many areas of computer science. :-)
- psibi 6y ago
  Somehow I found the course very dry (as compared to other coursera course like Dan Grossman's PL course).

avl999 6y ago

Building a distributed key value store is a fun project and lets you learn tons of real world world stuff. It's a great excuse to get a survey on grokking the design decisions required to build a distributed system and it will truly help one understand why No SQL DBs scale easier than relational ones and the kind of tradeoffs they make to achieve that.

SoSoRoCoCo 6y ago

I wrote a raytracer in 1996, and then a year later used Intel's VTune to speed it up. Just removing unused "return" statements gave me 3x speed increase. Apparently Borland C/C++ wasn't very smart back then. A fun project I did after that was writing a AI frame language to do goal-stack problem solving, specifically with path finding. I connected it to the ray tracer and made movies of spheres having wars. (I used an unlicensed DivX encoder to stitch together thousands of GIFs.)

thealig 6y ago
That sounds fun. Do you have code for reference? Also I want to try out building a raytracer sometime as a hobby project, is it advisable to learn some 3d graphic concepts like WebGl and so?
- carl_dr 6y ago
  Check Ray Tracing In One Weekend out : https://raytracing.github.io/books/RayTracingInOneWeekend.html https://raytracing.github.io/books/RayTracingInOneWeekend.ht... You can very quickly get something on the screen with it, although getting an intuition for how it works may take a little longer and some reading around the concepts it introduces. But it does let you focus on the maths rather than worrying about also learning how Web/OpenGL works too.

timvisee 6y ago

Fantastic list! By the way, adventofcode.com is currently ongoing. Though the challenges are easy compared to the projects in this list, I highly recommend it. It covers problems you might face in big projects. With these small puzzles it's easy to experiment. It prepares you for bigger things.

macintux 6y ago
For better or worse, adventofcode relies heavily on mathematical literacy that I suspect is neither all that common among developers nor all that important to most programming jobs. Plus there’s no good way within the context of the puzzles to find out what mathematical trick you need if you don’t already know; you need to go find a virtual water cooler. I may simply be biased because each year it reveals how little I know, but I much prefer interesting programming problems that don’t require me to go to Reddit, read other people’s description of what math is required, go learn the math involved, and then finally implement a solution.
- davidcbc 6y ago
  There has only been 1 day this year that I think falls into this category (and only one or two last year as well). They are almost all algorithm based rather than math based.
- windowojji 6y ago
  I'd hardly say it relies _heavily_ on obscure math tricks. Typically there's one or two days which require, perhaps, an undergraduate level of math which people would likely get in an intro class during a CS degree. Most of the problems are around searching a space for some solution or just simulating some state changes. Recent problems involved implementing a higher dimensional version of Conway's game of life[0], a simple arithmetic expression evaluator [1], or a simulator for a simple number game[2] e.g. The most recent one[3] involves solving a jigsaw puzzle by using a simple backtracking search (or any number of other methods). It's a bit complex, but not reliant on a particular math trick. The vast majority of the problems in advent of code shouldn't require any math tricks, though they're often complex and involved, particularly as the month goes on. [0] https://adventofcode.com/2020/day/17 https://adventofcode.com/2020/day/17 [1] https://adventofcode.com/2020/day/18 https://adventofcode.com/2020/day/18 [2] https://adventofcode.com/2020/day/15 https://adventofcode.com/2020/day/15 [3] https://adventofcode.com/2020/day/20 https://adventofcode.com/2020/day/20

xamuel 6y ago

Here's an open-ended programming project which, in a certain formal sense, spans the entire range of all difficulty levels: write an "intuitive ordinal notation" for as large of an ordinal number as you can. What is an "intuitive ordinal notation"? Definition: The set of intuitive ordinal notations is the smallest set P of computer programs with the following property. For every computer program p, if, when p is run, all of p's outputs are elements of P, then p is in P. So "End.", the program which immediately ends with no outputs, is vacuously in P (all of its outputs are in P, because it has no outputs). It notates the ordinal 0. Likewise, "Print(`End.')" is in P, because its sole output, "End.", is in P; it notates the ordinal 1. Likewise, "Print(`Print(End.')')" is in P, notating the ordinal 2. And so on. The above can be short-circuited: "Let X=`End'; While(True){Print(X); X=`Print(\`'+X+`\')'}". This program outputs "End.", "Print(`End.')", "Print(`Print(`End.')')", and so on forever, all of which are in P, so this program itself is in P. It notates omega, the smallest infinite ordinal. Here's a library of examples in Python, currently going up to a notation for the ordinal omega^omega: https://github.com/semitrivial/IONs https://github.com/semitrivial/IONs

carapace 6y ago
Oh that's cool.
- xamuel 6y ago
  As an example to illustrate how this initially-simple-looking project spans the whole range of all possible difficulty levels: suppose you had a source-code for a superhuman flawless obedient honest AGI, call it HAL. From that source-code, you could derive a source code X for: "Print all the computer programs which HAL would list if HAL were commanded: 'Enumerate every computer program which you know to be an intuitive ordinal notation'". Since we're assuming HAL is obedient and honest, all of X's outputs will be intuitive ordinal notations, so X itself is an intuitive ordinal notation: you could say it notates "the ordinal of HAL". So this innocent-looking exercise in fact touches the most ambitious possible projects, even "Design a perfect superhuman AGI" :-)
ianai 6y ago
They’re not sequential though so write a program which offers a way to check whether an output is in the solution set and stores the input and always returns true.

acutesoftware 6y ago

Writing even an extremely simple game without using a game engine or dedicated game library is quite an eye opener. Make a small 2D platform game, and it covers so many areas (and it is a lot of fun!).

fspear 6y ago

I would add an emulator to the list.I've always struggled to figure out how these are built from scratch. A long time ago I wanted to code a neogeo emulator but gave up before I even started, I didn't have a clue where to begin. I am amazed at anyone that can code an emulator from scratch.

tuankiet65 6y ago
Their previous article mentioned it: https://web.eecs.utk.edu/~azh/blog/challengingprojects.html https://web.eecs.utk.edu/~azh/blog/challengingprojects.html.
deleted 6y ago
[deleted]
sterlind 6y ago
they're really simple, in their basic form and for simple ISAs! it mostly boils down to keeping a bunch of registers and a giant switch statement. Each case simply implements the opcode. You have an array of bytes for the memory, and some emulated devices (e.g. trigger a screen update when the framebuffer memory gets changed, or set the instruction pointer to a handler when a key gets pressed.) It gets hard when instructions need lots of decoding, or you have 3d graphics hardware to emulate, or if you have something like a BIOS, or if you want to JIT. I'm actually eyeing implementing a console on an FPGA as my holiday project, with something like Chisel.
- schoen 6y ago
  It seems like a lot of the complexity may also come in when you have important circuits to emulate other than the CPU. In that case you'd have more to worry about in terms of timing, dataflow, and synchronization. And some platforms might conceivably have analog circuits that play an important role too, although I guess you might be able to abstract that out by trying to create a rough digital functional equivalent even if it isn't completely faithful to the behavior of the analog part.
  - 6y ago

userbinator 6y ago

IMHO a text-based browser isn't exactly in the "challenging" category, as it basically amounts to stripping all the HTML tags out and doing some very simple transformations (like replacing <br>'s with newlines.) Then again, one of the things I've been working on intermittently for the past few years is a graphical (CSS2+) browser, which is definitely in the challenging category. There are some other public efforts too: https://github.com/lexborisov/Modest https://github.com/lexborisov/Modest https://github.com/litehtml https://github.com/litehtml https://github.com/ArthurHub/HTML-Renderer https://github.com/ArthurHub/HTML-Renderer Along the same lines, some other challenging projects I recommend are to write decoders/renderers for existing formats like MP3, MP4, PDF, etc.

Forge36 6y ago
It looks straightforward until you hit a couple of edge cases. Examples: test <1 becomes test 1 Test< 2 becomes test 2 Test <a becomes test Test < b becomes test b (From memory) What about: Test <fakeTag>? Per tests i did, "test " was expected however "test <fakeTag>” was seen as the plaintext version suggesting there's a list of valid tags which is filtering the behavior.
- userbinator 6y ago
  That's because '<' needs to be followed by [!/?a-zA-Z] to be recognised as a tag start. Otherwise it is a literal '<'. The full details are in here somewhere: https://www.w3.org/TR/2011/WD-html5-20110113/tokenization.html https://www.w3.org/TR/2011/WD-html5-20110113/tokenization.ht...
- benibela 6y ago
  I have been stuck on such these edge cases for almost 15 years building my own HTML parser It is always working on all the HTML files I have, but then people make new HTML files with other issues.
zerf 6y ago
To this list I would add "Web Browser Engineering" [0] which is a textbook / browser engine that is currently being written by Dr. Pavel Panchekha at the University of Utah. The code for the book and browser is available on GitHub [1] and a more current bleeding edge draft is also published [2]. The book guides the reader in implementing a graphical web browser, starting with HTTP and HTML then moving on to the layout, the box model, CSS, browser chrome, forms, and scripts. [0] https://browser.engineering https://browser.engineering [1] https://github.com/pavpanchekha/emberfox https://github.com/pavpanchekha/emberfox [2] https://browser.engineering/draft/ https://browser.engineering/draft/

Waterluvian 6y ago

Writing a Game Boy emulator has been the most fulfilling and interesting programming project in my life. I love, most of all, how modular the project is. I can do an hour here or there and make meaningful progress. I'm really eager to discover other very large programming projects that break down into sensible bites so well.

windowojji 6y ago
I worked on a game boy emulator a while ago to learn C. I did pretty well and was able to run most games I came across just fine, but never got audio working...I just couldn't understand any of the stuff online about how it worked, and was unable to find any good resources that walked through how audio emulation in general worked, much less game boy's version.
shhsshs 6y ago
I had never considered an emulator to be anywhere inside of the realm of possible projects I could take on for fun. I just thought it would be too complex without having a ton of very specific knowledge. Your comment prompted me to go look up some other attempts, and I’m really glad I did. It seems much more approachable to me now. Thanks!
- Waterluvian 6y ago
  Consider starting with a CHIP-8 emulator. It's a perfect size for starting out and touches on a lot of important concepts you'll apply to the next emulator.

tracyhenry 6y ago

A great compilation: https://github.com/danistefanovic/build-your-own-x https://github.com/danistefanovic/build-your-own-x

082349872349872 6y ago
Building your own dogfood (if you use it daily, code a quick-and-dirty one) is a good way to learn that by holding the right end of the exponential, 80-20 solutions can easily be closer to 1-99+ in terms of manpower and code size. (the flip side of 80-20 is: "all systems are fault tolerant, it's just that in most of them, the human is the component which tolerates the faults") Of my IT daily drivers, I've done toy: - web browser / server - email client - document formatter - text editor - window manager - 3D / 2D graphic slicers/rasterizers w/ alphabetic fonts - shell - interpreters / compilers - operating system - VHDLish CPU - various data encodings (Hamming, MFM, etc.) - discrete transistor logic (when I was just starting to program, I discovered the home directory of a colleague of my father's contained many experiments of this kind, and reading his work taught me C)

deleted 6y ago

[deleted]

deleted 6y ago

[deleted]

person_of_color 6y ago

How about designing your own virtual memory system

tsjq 6y ago
that's like Prof Frank Mueller level

rex64 6y ago

I recently went through the process of creating a ray tracer project from zero for learning purposes. It was a humbling and eye-opening experience. I've written an article[0] to explain my process in detail if you're interested. [0] https://alessandrocuzzocrea.com/how-i-made-a-ray-tracer/ https://alessandrocuzzocrea.com/how-i-made-a-ray-tracer/

jackschultz 6y ago

Instead of a stock trading bot, go for daily fantasy sports contests. It can cover pretty much all parts of programming. Web scraping to gather data, databases for storing it, ML for analyzing, front and backend web dev to show the daily information and adjust. And instead of having to deal with trading regulations, contests can be really small and easy to enter. There are daily contests for 5 cents an entry, and you can enter 150 optimized lineups from an uploaded csv for $7.50 a day. You can really learn a ton.

nsomaru 6y ago
Which services would you recommend which are developer friendly? Could you describe your approach? What type of information would you scrape?

rdescartes 6y ago

I would recommend choosing a long enough time (e.g. 3 months) to contribute an open source project you are using, especially you are not familiar to that domain. I learnt a lot from modern compiler stuffs by contribute to rust-analzyer.

kunalpowar1203 6y ago

Thanks for following up with this list after your previous one. I spent a great deal of my time (including some office time) on writing a Chip-8 emulator thanks to your previous list :D

forgotmypw17 6y ago

I would add a basic feature-complete website which works on every mainstream browser starting with Mosaic. It's much easier than it may seem, architecting it is interesting, and there is a lot of "last 10%" stuff which keeps it fun as long as you keep going. In the demystifying area, it demystified HTML and JS history for me, forced me to use with a minimal toolkit, and taught me how to build "modern" JS features in ways which will not break browsers which don't know how to do them or have them disabled.

fergie 6y ago

I would strongly recommend building something that you yourself think is cool, and not feeling that you have to conform to what other people tell you to do.

purplecats 6y ago
why not, that's only one direct step removed from thinking that conformity to popular beliefs is cool.
watwut 6y ago
Most people draw blank when they are trying to come up with project idea. They are programmers, not creative after all. Which is why lists like this help.
- anonytrary 6y ago
  If you are trying to think of an idea, you're already doing it wrong. The best ideas are motivated by problems you encounter yourself, not by trying to think of ideas. This is the biggest mistake you see with 20-something founders. Best way to come up with ideas is to use existing solutions and realize how shitty they are. Pretty much every single company was formed this way. > They are programmers, not creative after all. Damn, this is a bold comment on HN. Since when does profession determine how creative you are? I've met "programmers" and "geeks" who are more creative than "artists". Your profession has little to do with your innate creativity -- it just determines how you are able to express that creativity. Unpopular opinion, but lists like this are stupid for people who are trying to build companies. You have to try things and be pissed off at the status quo to find real problems. Nobody is going to find real problems for you, in the same way that no quant school is going to reveal their hedge fund's trading strategy to you. Finding ideas in a list is the last advice I would give to anyone. If it's public, it's probably not a profitable idea.
  - T_O_T_O 6y ago
    For a beginning programmer, these could be good projects. For someone with a lot of experience, I mostly agree with your comment.

djeiasbsbo 6y ago

For some simpler projects, I can only recommend doing some digital signal processing. For example, an audio signal is just a list of values, so you can do things like: - Count the number of zero crossings - Find out where they are - Create any shape of wave by adding together multiple sine waves - Hard clip the signal - Stretch a signal and interpolate it with new samples - Invert and revert a signal For level 2, you can start processing "live": - Create a sine synthesizer - Create a small ring buffer of samples - Find out how to output that audio (system audio, soundcard) - Add MIDI support - Add polyphony support DSP gets hard once it has to be in real time and the latency has to be minimal. It's great exercise to mess around with it.

jamil7 6y ago
I came across this area recently while trying to build an iOS app that could reliably detect knocks or taps on the body of the phone, I was ultimately unsuccessful but I learned a lot about collecting and analysing microphone and gyroscope data. Also built some nice tooling for collecting live iOS sensor data and transmitting it to prometheus/grafana over mqtt.
- djeiasbsbo 6y ago
  That sounds interesting. A cool project would be to inspect gyroscope data when the iOS keyboard is in use. Maybe it would be possible to create a keylogger based on it. I guess it would depend on how good the data is and which keyboard is being used. I know that this is possible on Android.

anonytrary 6y ago

This article is aimed towards students. It's great advice for students who are in college, know very little, and want to improve their CS skills. It's poor advice for someone who already has a STEM degree and wants to build something useful and profitable. If you already know how these things work, your time is better spent on the "edge of the circle": http://matt.might.net/articles/phd-school-in-pictures/ http://matt.might.net/articles/phd-school-in-pictures/ which applies to businesses and startups as well. If you're in the latter group -- you've already got the skills to build real shit. Don't waste your time on homework problems. Find a problem you have and build a solution for it. Don't listen to people who tell you to work on homework problems that have already been solved; it's a complete waste of your time if you already know the fundamentals. As for stock trading bots -- if you don't have a mathematics degree or equivalent (e.g. having incredible math skills), don't even bother. You won't be profitable, and you will learn nothing useful in the process, because you will approach the problem as a naive CS student would. Smarter people than you have made trading bots and have failed miserably. Without having an extremely strong foundation in mathematics, your trading bot will amount to nothing more than a futile exercise in gluing APIs together.

imtringued 6y ago
You should grow a second spike. I'm at the point where visual design skills are a greater bottleneck than my computer science skills. I can build purely functional CAD models but man, making them functional AND look good is the real challenge.
- anonytrary 6y ago
  Agreed. Everyone should aim to have 3-4 spikes they are passionate about. For every spike you have, you become exponentially more of a domain expert at the problems that are at the intersection of those spikes.
  - PeterisP 6y ago
    Yes, proper senior expertise often looks like being a jack of all trades and a master of three or so.

trustfundbaby 6y ago

What do folks think about implementing a web crawler that you can send to a website and it indexes every internal url on the site. I remember sitting down to write one 100 years ago now, and finding it to be much trickier than I thought it would be.

tsjq 6y ago
that's interesting. grab only the URLs, not the content?
- trustfundbaby 6y ago
  right, but of course to do that, you'd have to grab the content to parse it :)

KlimYadrintsev 6y ago

What is the main reason of trying this projects? To learn something new? To train existing skills? Or is it to benefit financially from those projects?

arendtio 6y ago

What I am really missing is some kind of real-time AI. A decade ago, I have coded some bot for an ego-shooter with RTS elements and have learnt so much from it (while having a lot of fun). It starts with basic things like waypoint systems vs. area awareness systems plus the relevant routing algorithms like A*, but goes on to organizing a group of players and finding good strategies. And all of that with a limited time budget and an changing environment around you. Last but not least, you want to emulate human behavior which is probably the hardest part as it includes changing you behavior according to your situation (don't run straight against a wall for 10 seconds) but also taking into account the weaknesses as e.g. humans can't aim perfectly. Granted, what I have done has a huge field of challenges, but even with a 2D engine I think you can learn a lot from the experience.

drummersbrother 6y ago
You may be interested in the game Screeps. From their website (name +.com): "It's an open-source game for programmers, wherein the core mechanic is programming your units' AI. You control your colony by writing JavaScript. "
- joycian 6y ago
  I looked this up and it seems very cool. Do you (or anybody else) know any more of these games or environments that can be controlled by code?

deleted 6y ago

[deleted]

whatever_dude 6y ago

My own favorite is an equation parser. Before attempting to do so I thought it was implemented as a simple seek over the string, maybe a bunch of regex stuff. I guess it can be done that way, at the cost of growing complexity; but the proper solution (with a stack, etc) is so elegant (makeing it easy to add functions, operators, parenthesis, variables, etc) that it really makes one appreciate the value of good, thoughtful engineering.

known 6y ago

https://en.wikipedia.org/wiki/List_of_lists_of_lists https://en.wikipedia.org/wiki/List_of_lists_of_lists FTW

mjgs 6y ago

Awesome couple of articles.