Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Challenging projects every programmer should try (2019)

austinhenley.com

Post reply on HN
Print view View original

311–320 of 346 posts

Re: Challenging projects every programmer should try (2019)

#311

Post by ryandrake »

tester756 wrote: post #213
p-e-w wrote: post #211

Earlier quoted context omitted.

Where in the world can you get a computer science degree without hearing about consensus algorithms?

Pretty much everywhere below country's top3, top5? I've got masters degree and I don't think anyone even mentioned word "paxos" or "raft" during my 5 years there. Fortunely internet is a thing and I could read something about this topic. I know graduates from various public schools and people who heard about paxos (let alone can implement it) are tiny %.

I have a Comp Eng degree from the 90s, been in the industry since then (~25 years), and I have never heard of Paxos. Even the top results from a Google search yields that Paxos is one of: 1. a blockchain company, or 2. a Greek island. More than halfway down the page there is mention of an algorithm of some kind. Probably not a good example of "baseline knowledge" for a software engineer.

Re: Challenging projects every programmer should try (2019)

#312

Post by MikeTheGreat »

darreninthenet wrote: post #135
MikeTheGreat wrote: post #120

Earlier quoted context omitted.

> an orchestra conductor doesn't need to play [...] any instrument! in order to make music Ok, this is clearly a side-topic AND at the risk of being pedantic: Is this actually true? Like, I can see how theoretically one could learn to sight-read music well enough to be able to direct an orchestra of individual musicians, then do enough ear-training to identify enough notes to keep tabs on everyone (especially if you'…

I guess it depends what you mean by "play an instrument" - almost all proficient conductors have proficiency in at least one orchestral instrument. There is at least one (so I'm speculating he's not the only one, but it is likely to be rare) proficient conductor (Leopold Stokowski) who had no real proficiency with any instrument but he did have some very rudimentary piano training... and then pretty much taught himse…

I was intrigued and looked into this. According to Wikipedia:

"He studied at the Royal College of Music, where he first enrolled in 1896 at the age of thirteen, making him one of the youngest students to do so. In his later life in the United States, Stokowski would perform six of the nine symphonies composed by his fellow organ student Ralph Vaughan Williams. Stokowski sang in the choir of the St Marylebone Parish Church, and later he became the assistant organist to Sir Walford Davies at The Temple Church. By age 16, Stokowski was elected to membership of the Royal College of Organists. In 1900, he formed the choir of St. Mary's Church, Charing Cross Road, where he trained the choirboys and played the organ. In 1902, he was appointed the organist and choir director of St. James's Church, Piccadilly. He also attended The Queen's College, Oxford, where he earned a Bachelor of Music degree in 1903" [1]

That sounds like a bit more than rudimentary piano training to me :)

[1] https://en.wikipedia.org/wiki/Leopold_Stokowski#Early_life

Re: Challenging projects every programmer should try (2019)

#313

Post by adamnemecek »

ThrowawayR2 wrote: post #127
adamnemecek wrote: post #9

I will also add a CAS, computer algebra system to the list.

I've never seen an explanation of Gröbner bases that's accessible enough to the average non-mathematician developer to make that practical. Any pointers?

"Modern Computer Algebra" by Joachim von zur Gathen, Jürgen Gerhard is decent.

Re: Challenging projects every programmer should try (2019)

#314

Post by _gabe_ »

gushogg-blake wrote: post #247

On the text editor one: > The biggest challenge is figuring out how to store the text document in memory. My first thought was to use an array, but that has horrible performance if the user inserts text anywhere other than the end of the document. I guess this is only an issue in low level languages, as I just used a JavaScript string and I don't think it's been a perf issue in 2+ years using my editor full time. Ple…

And here I was thinking the author must have been using a higher level language. I remembered reading this blog[0] where the author stated that the worst case scenario for an insertion at the beginning of a 2mb file only took 2ms on an old laptop while using an array as the data structure. I believe the author was using Zig here.

[0]: https://www.scattered-thoughts.net/writing/focus-text/

Re: Challenging projects every programmer should try (2019)

#315

Post by umvi »

MBCook wrote: post #36
umvi wrote: post #30

For a fun challenge, implement space invaders in Verilog (i.e. purely in hardware)

How would you suggest going about the display? Driving an LCD or generating an NTSC/PAL signal? Or maybe a giant array of LEDs? Is there a good tool to simulate Verilog so you can test without hardware?

When I did it, I drove VGA

Re: Challenging projects every programmer should try (2019)

#316

Post by tamrix »

bobsomers wrote: post #103
p-e-w wrote: post #24

While writing a text editor, a compiler, an operating system, or a raytracer might make you a better programmer, it won't make you a better software engineer. In fact, it might make you worse at software engineering, because it embodies the disastrous "Not Invented Here" doctrine. Hackers like to obsess about Big-O, data structures, HoTT, and other high-theory stuff, yet the following skills, essential for software e…

I don't understand why you think a search engine requires the use of "real engineering skills" like picking and choosing libraries and identifying which opportunities will yield fruitful optimization. Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. I'm more inclined to think that your comment is really more revealing about what…

How about the ultimate programming challenge. Make a project that makes real money.

Re: Challenging projects every programmer should try (2019)

#317

Post by datadeft »

p-e-w wrote: post #107
bobsomers wrote: post #103

Earlier quoted context omitted.

I don't understand why you think a search engine requires the use of "real engineering skills" like picking and choosing libraries and identifying which opportunities will yield fruitful optimization. Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. I'm more inclined to think that your comment is really more revealing about what…

> Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. In the linked article, these projects are all explicitly described as opportunities to learn about low-level stuff like how to efficiently store editable text. The difference with a web search engine is that nobody today can build such a thing completely from scratch, therefore…

I think searx was largely built by a single person.

https://github.com/searx/searx

Re: Challenging projects every programmer should try (2019)

#318

Post by whazor »

aardvark179 wrote: post #224
p-e-w wrote: post #62

Earlier quoted context omitted.

And the most challenging part is making a text editor that actually works well from a usability perspective. Which has almost nothing to do with data structures and optimization. I've used dozens of text editors. I have never once thought "man, that thing is slow". But I have thought "man, that thing is a bug-ridden, unintuitive piece of garbage" many, many times.

Try re-indenting a large xml file, or something else that will result in a very large number of small deletions and insertions throughout a file. Even on a modern computer the underlying data structures will make the difference between something near instantaneous and the user giving up in despair after a few minutes. A simple array does not cut it.

Formatting a file could be a single operation that creates a single array of lines. Normally the formatter is a separate program that actually gets the input as string and returns a new string as output. So the extra concatenation and splitting would not cost much extra.

The formatting is often difficult enough that it will need a separate data structure anyways.

Re: Challenging projects every programmer should try (2019)

#319

Post by crazygringo »

YetAnotherNick wrote: post #261
crazygringo wrote: post #250

Earlier quoted context omitted.

Assuming you get the TCP/IP stack for free, you still need to build fully-featured HTTPS and a "webscale" multi-server database for document storage from scratch. The crawler is easy and so is something like PageRank, but then building the sharded keyword text search engine itself that operates at webscale is a whole other project... The point is that it's too much work for a single person to build all the parts them…

Simple methods of search like exact matching are very fast using textbook algorithms. There are well known algorithm like suffix tree which could search in millions of documents in milliseconds.

That's not enough. It needs to be sharded and handle things like 10 search terms, each of which match a million documents and you're trying to find the intersection. Across shared results from 20 servers. Quickly.

That's not a textbook algorithm.

Re: Challenging projects every programmer should try (2019)

#320

Post by marginalia_nu »

crazygringo wrote: post #319
YetAnotherNick wrote: post #261

Earlier quoted context omitted.

Simple methods of search like exact matching are very fast using textbook algorithms. There are well known algorithm like suffix tree which could search in millions of documents in milliseconds.

That's not enough. It needs to be sharded and handle things like 10 search terms, each of which match a million documents and you're trying to find the intersection. Across shared results from 20 servers. Quickly. That's not a textbook algorithm.

Intersecting postingslists is a solved problem. You can do it in sublinear time with standard search engine algorithms.

The problem space is embarassingly parallel, so sharding is no problem. Although, realistically, you probably only need 1 server to cope with the load and storage needs. This isn't 2004. Servers are big and fast now, as long as you don't try to use cloud compute.

Post reply on HN