More challenging projects every programmer should try • Hacker News Board

Re: More challenging projects every programmer should try

#51

Post by schoen » Mon, Dec 21, 2020, 1:24 AM UTC

simias wrote: post #27

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 mod…

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.

Re: More challenging projects every programmer should try

#52

Post by sterlind » Mon, Dec 21, 2020, 1:26 AM UTC

fspear wrote: post #42

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.

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.

Re: More challenging projects every programmer should try

#53

Post by schoen » Mon, Dec 21, 2020, 1:29 AM UTC

fspear wrote: post #42

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.

My friend who works on the MAME project told me that it's a very friendly platform for adding new emulators (whether you want to add an emulation of a game, a device, a platform, or whatever) because it provides a good structure to work with and a lot of tools to describe recurring patterns in electronics and systems. That might be a good middle ground to start with -- trying to add support in MAME for some device that's not presently emulated there. (Apparently the MAME project really appreciates such contributions, since they think of themselves as pursuing mainly a historical preservation and documentation mission, and would always like to see more devices covered.)

Although that's not "from scratch" because it would still be using their libraries and plumbing, it could be "from scratch" in the sense that you might take an environment with 0% support for emulating a certain device or system and build it up to having 100% support. So it seems like a nice way to start.

Re: More challenging projects every programmer should try

#54

Post by Waterluvian » Mon, Dec 21, 2020, 1:30 AM UTC

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.

Re: More challenging projects every programmer should try

#55

Post by altitudinous » Mon, Dec 21, 2020, 1:30 AM UTC

xwdv wrote: post #5

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.

I completely agree. Writing apps for the app store is the perfect example. I started out coding well coded apps that didn't make money, and as time has progressed my apps have lower code quality but I make more money. I focus less on code quality now and think more about marketing and appeal.

Re: More challenging projects every programmer should try

#56

Post by schoen » Mon, Dec 21, 2020, 1:31 AM UTC

sterlind wrote: post #52

fspear wrote: post #42

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.

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 inst…

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.

Re: More challenging projects every programmer should try

#57

Post by userbinator » Mon, Dec 21, 2020, 1:34 AM UTC

Forge36 wrote: post #45

userbinator wrote: post #43

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 '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: h…

It looks straightforward until you hit a couple of edge cases. Examples: test Test Test Test (From memory) What about: Test ? Per tests i did, "test " was expected however "test ” was seen as the plaintext version suggesting there's a list of valid tags which is filtering the behavior.

That's because 'The full details are in here somewhere: https://www.w3.org/TR/2011/WD-html5-20110113/tokenization.ht...

Re: More challenging projects every programmer should try

#58

Post by sumeno » Mon, Dec 21, 2020, 1:34 AM UTC

macintux wrote: post #44

timvisee wrote: post #30

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.

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…

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.

Re: More challenging projects every programmer should try

#59

Post by FartyMcFarter » Mon, Dec 21, 2020, 1:34 AM UTC

iainmerrick wrote: post #41

avl999 wrote: post #34

Earlier quoted context omitted.

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.

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 t…

> Most other non-garbage-collected languages would do the trick, like Rust or C++

Only as long as you avoid any fancy libraries that do a lot of the work for you.

Granted you can use fancy libraries in C too...

Re: More challenging projects every programmer should try

#60

Post by windowojji » Mon, Dec 21, 2020, 1:34 AM UTC

macintux wrote: post #44

timvisee wrote: post #30

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.

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'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

[1] https://adventofcode.com/2020/day/18

[2] https://adventofcode.com/2020/day/15

[3] https://adventofcode.com/2020/day/20