Difficult tasks each programmer ought to strive

2023-12-25 21:25:24

Difficult tasks each programmer ought to strive – Austin Z. Henley

Austin Z. Henley

I work on software program.

12/11/2019

Replace 12/14/2019: This put up spurred a number of dialogue on Hacker News and Reddit. I collected a number of the instructed tasks and put them in an inventory on the finish of this put up.

Take a look at the sequel to this put up: More challenging projects every programmer should try.

Take a look at the second sequel too: Challenging algorithms and data structures every programmer should try.

I discuss to a number of college students {and professional} builders that always wish to begin a aspect mission, however aren’t positive what to construct. Under is a handful of software program tasks that taught me rather a lot. Actually, they’re nice since you may construct them a number of instances and be taught new issues every time. So every time I do not know what to construct or I wish to be taught a brand new programming language or framework, I begin with certainly one of these:

Textual content editor
2D recreation – Area Invaders
Compiler – Tiny BASIC
Mini working system
Spreadsheet (exhausting!)
Online game console emulator (exhausting!)

Textual content Editor

We use textual content editors on a regular basis, however are you aware the way it actually works? Ignoring all the fancy options that your favourite editor has, how would you implement a textbox that helps a movable textual content cursor and choosing, inserting, and deleting textual content? No, you may’t use the builtin textbox element out of your favourite GUI framework!

The most important problem is determining the way to retailer the textual content doc in reminiscence. My first thought was to make use of an array, however that has horrible efficiency if the person inserts textual content wherever apart from the top of the doc. Fortunately, there are some good information buildings to be taught to resolve this.

One other hurdle was studying how a textual content cursor behaves in widespread editors. For instance, if I press the up arrow key with the cursor in the midst of the doc, the place will the cursor transfer? Similar column? Not if that line is shorter. Preserve urgent up. The cursor will snap again to the unique column as soon as a line is lengthy sufficient. It seems that the cursor has a reminiscence for the column and tries to get again to it. It’s these particulars that I by no means observed till I attempted to implement it.

After implementing the fundamental editor, I problem you to implement two extra options: undo/redo and phrase wrapping. Implementing undo/redo in an environment friendly method was thoughts blowing to me! I first tried preserving an array of earlier states, then tried the Memento sample, earlier than lastly deciding on the Command sample. Phrase wrapping forces you to separate the visible features of a textual content line from the reminiscence features.

Issues to be taught:

Information buildings for storing the textual content: array, rope, gap buffer, piece table.
Conduct and implementation of the textual content cursor.
Design patterns for undo/redo: memento, command.
Abstractions to separate the visible and reminiscence features of the textual content.

Additional studying:

Textual content Editor: Information Constructions (web)
Design and Implementation of a Win32 Textual content Editor (web)
Information Constructions and Algorithms in Java (Amazon)

2D recreation – Area Invaders

Even the simplest video games require some distinctive information buildings and design patterns. The concept right here is to implement a well-defined recreation from begin to end with out getting slowed down on the opposite enjoyable stuff (e.g., recreation design and artwork). Additionally, it’s best should you use a barebones 2D graphics library (e.g., SDL, SFML, PyGame), not an enormous recreation engine that’ll disguise all the fascinating bits from you.

First, you will need to be taught to attract to the display. I had no thought how this labored. You’re truly clearing the display then drawing every portion of the display in speedy succession, many instances a second, to create the impact that objects are transferring.

Second, you will be taught all in regards to the recreation loop. A recreation is successfully looping between drawing, getting person enter, and processing the sport logic.

Third, you will discover ways to course of person enter. I by no means paid consideration to the subtlties of initially urgent, holding, and releasing keys or mouse buttons, not to mention dealing with issues like a double click on. And the way usually do you verify for person enter? If you’re continually checking then which means the remainder of the sport is frozen!

Fourth, you will discover ways to create and handle your entire recreation objects and their state. For instance, how do you generate a dynamic variety of enemies? The manufacturing facility sample helps rather a lot.

Fifth, you will discover ways to apply the sport’s logic. When do bullet positions get up to date? When do extra enemies come onscreen? How are you aware when an enemy is destroyed? When is the sport over? I had by no means used the modulo operator prior to creating video games however it’s littered throughout my video games’ code.

When you get the fundamental recreation working, add a title display menu, a recreation over display, ensure that the sport runs on the similar pace even on totally different computer systems, and discover the way to implement extra fascinating enemies with AI. Nonetheless not sufficient? Add shader results, sound, and on-line multiplayer!

Issues to be taught:

Drawing to the display.
Dealing with person enter.
Sport loop.
Creating and managing a dynamic variety of objects (e.g., factory pattern).
State machines for enemy AI.
Taking part in sound.
Utilizing shaders.
Networking for on-line options.

Additional studying:

Sport Programming Patterns (Amazon, web)
Information Constructions for Sport Programmers (Amazon)
Programming Sport AI by Instance (Amazon)
The 8 classes I realized from releasing 8 video video games (web)

Compiler – Tiny BASIC

Probably the most-eye opening tasks I’ve labored on are compilers. Even now, if I’ve a free Sunday afternoon to do some coding, chances are high it’s a compiler. It’s a nice feeling while you create one thing that allows others to create extra issues. By implementing one I needed to be taught a lot extra in regards to the intricacies of compilers that I usually would by no means take into consideration (e.g., when do expressions get implicitly kind transformed).

I counsel writing the compiler from scratch for a really small BASIC-like language (see Tiny BASIC) and compile to another language that you understand properly. For instance, you possibly can write a Tiny BASIC compiler in Python that outputs C# code. It does not need to output meeting or C! Avoiding these will allow you to give attention to the compiler itself.

The primary hurdle is determining the way to lex (or tokenize) the enter code. Then you’ll parse the code, that’s verify the construction of the enter and produce a tree illustration of the code. The recursive descent parsing method is gorgeous! Subsequent you’ll semantically verify the enter, guaranteeing the code is sensible and that the kind guidelines are being adopted. Lastly, you may generate output!

This mission has a ton of present assets that will help you, and a easy compiler will be accomplished in a couple of days. Do not let the jargon scare you. Plus the chances are countless to what you may add! After getting the fundamental compiler working, you may add a normal library (in PeayBASIC I added easy 2D graphics performance), optimization passes, and enhance the error messages. Lastly, you need to write some instance applications in your personal language to point out off to the world!

Issues to be taught:

Additional studying:

My tutorial: Let’s make a Teeny Tiny compiler (web)
Crafting Interpreters (Amazon, web)
Write an Interpreter in Go (Amazon)
Let’s Construct a Compiler (web)
PeayBASIC supply code (GitHub)

Mini Working System

Through the years I’ve discovered myself making use of basic ideas from working techniques to a wide range of domains, like video games and even predictive fashions of human conduct. In a classroom setting the algorithms and information buildings utilized by working techniques may appear summary or ineffective, however they are surely helpful. Implementing an working system additionally helped me perceive much more about what’s going on underneath the hood.

There’s a little bit of a studying curve and a few boundaries to get began since it’s depending on {hardware}. Nonetheless, by following a guide or tutorial then you need to be capable of get a bootable OS working that may run your personal applications. I extremely advocate my colleague’s free on-line guide, Making a RISC-V Operating System using Rust.

Issues to be taught:

Additional studying:

OSDev.org’s wiki of assets (web)
Making a RISC-V Working System utilizing Rust (web)
Working System Ideas (Amazon)

Nonetheless not troublesome sufficient for you? Strive these two tasks:

Spreadsheet

A spreadsheet utility, like Excel, combines a number of the challenges from a textual content editor with these of a compiler. You will need to discover ways to characterize the cell contents in reminiscence and implement an interpreter for the programming language used for equations.

Additional studying:

Directed acyclic graph (web)
Reactive programming paradigm (web)
Spreadsheet Implementation Expertise (Amazon)

Online game console emulator

Writing an emulator (or digital machine) for a online game console combines the challenges of writing a compiler, an working system, and a compiler all into one. It’s fairly rewarding to play an actual recreation made by another person together with your emulator!

Emulating an actual online game console means writing a digital machine that pretends to perform identical to the precise CPU and different {hardware} elements. This lets you run video games designed for the online game console together with your emulator.

I like to recommend beginning by emulating CHIP-8, which is an easy, fictitious console, earlier than transferring on to an actual online game console. The NES, SNES, Gameboy, and Gameboy Advance are all fairly possible to emulate, with a far quantity of documentation and open supply emulators already, although they every have their very own quirks to make issues fascinating (e.g., sure video games could depend on undocumented bugs/options of the precise {hardware}). There’s additionally the PICO-8, which has grow to be a really worthwhile “fantasy” console.

Additional studying:

Please let me know in case you have another mission concepts! Here’s a listing of ideas from Hacker News, Reddit, Twitter, and emails I acquired: