Haha. Reminds me of a lab where we had to program a 6502 to play some sort of game, rendered on an oscilloscope. My genius friend stayed up all night writing code that rendered the snake by dynamically writing code, rather than the obvious approach of reading the “snake” coordinates and rendering those to the screen.

Our snake code ran at something obscene like 1,000 Hz. So much faster than anyone else’s. The professor couldn’t understand how we did it, so gave a low mark.

>The professor couldn’t understand how we did it, so gave a low mark.

That was genuinely upsetting to read.

In High School 2004 I made a license plate detection system for our IT class project. It was not perfect, granted, but was able to locate license plates in a photograph pretty reliably and do OCR on them.

Teacher was like, nah, that's not possible, and clearly hadn't even read it. Gave me an A just to stop me complaining, still not understanding the project.

My Fortran professor gave me a low mark because I used a lookup table for octal to binary conversion, instead of using division and modulo.

In a teaching lab in 1995, I had to make a digital thermometer using a mcu. I wrote code that dynamically read the voltage drop on the sensor and calculated the temperature. It was fast enough and easy to calibrate. The code was small and easy to understand.

I didn’t pass because the point of the assignment was to use lookup tables, even though that was a more complex approach in this case :(

"It was fast enough and easy to calibrate."

Are you sure about easy to calibrate 8) Did your solution have the same level of accuracy across the range as the MCU would provide?

Bizarrely, you sometimes have to follow the standards because that is what everyone does. I can't think of an example now but there will and have been cases in engineering where the wrong answer is the right one because that is what is done. I know of mensuration devices that "model" some curves with a linear approximation and paper over the errors with cough error estimates and/or keeping within the nearly linear range. That too is fine if everyone understands what is going on.

Accuracy is a funny old thing.

However, I like your approach and it shows you probably understand the principles involved. Ideally, if you are going to be a smart arse like that, then submit two solutions - the proscribed one and your clever one.

You mention a MCU but not what sort of sensor ...

Curious as to what you mean by "dynamically writing code"

Like meta programming, creating a string to define a query and then executing the string. In the case above, you dynamically create the program you need to solve the problem and then execute it. This is different than "solving the problem". You are writing a program to "write the program to solve the problem".

Doesn't sound like this kind of complicated string eval would be able to do 1000Hz but then again I also have no clue where you could possibly need that for a snake game. On an oscilloscope you'd need to produce vector lines to move from/to right?

More likely, I would wager that they were just overwriting the instructions to draw with new instructions that just inline everything so it didn't need to fetch out to anything.

Yes. This.

This is a slightly simpler (because of unicity) version of bucket sort or counting sort.

I remember seeing a (gag) variation of counting sort that just provided each element as an argument to `sleep`.

Yup, sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

That’s more like heapsort, because the OS will use a heap to implement a priority queue that contains times for when the next process needs to be scheduled.

Brilliant!

Although if it took a long time to enumerate the list of elements…

Pass them in as milliseconds or nanoseconds?

The "set of random unique numbers between x and y" part stands out so strongly that I would be shocked if the whole point wasn't to encourage a non-comparative sort.

> but sort of relevant

Hahahahaha :D

> I won the contest by setting to 0 a y-x register range of memory and then inserting each number into the range based on the number itself ("27" into register 27, "18" into register 18, etc.). Then I printed out all non-zero numbers in the range.

That's really smart. The others were just angry because they couldn't think outside of the box. Nice work!

That's not silly, that's the right way to solve that problem, unless y - x is large enough that you'd benefit from using one bit per number instead of one word. Well, usually calling qsort() would be fast enough, and less code.

That brings up memories! I did the same thing. We had to sort a million integers in the range 0-1000 (exclusive range). I did a counting sort, and beat every other solution handily.

In my case, though, the teacher disqualified my solution since the resulting lists didn't contain the same fixnums as the one i sorted, which I argued was stupid.

In the end I implemented a merge sort with some tricks and won anyway.

The same fixnums!? Fixnums are distinct from bignums in that they're small enough to fit in a machine word and therefore don't need to be objects allocated in the heap... Was this an odd implementation wherein fixnums were put into the heap anyway?

Nope. This was in PLT scheme. Fixnums were eq? to other fixnums, meaning they satisfied the most basic equality.

Arguing was futile. When we started benchmarking very large lists, the counting sort was the only one that did it in reasonable time. Despite being disqualified.

It's not silly. That's basically the "counting sort" and it definitely has uses.

The observation that "random numbers can be sorted in linear time" is actually often useful in algorithm design. A typical application is storing a sorted list of hash values.

Basically pigeon hole or bucket sorting https://en.wikipedia.org/wiki/Pigeonhole_sort which, as another commenter mentioned, are types of non-comparison sorting so you can get near linear times

I think the mainstream sorting algorithms tend to cater towards "mainstream" ordering which tends to be somewhat sorted versus purely random. An example is https://en.wikipedia.org/wiki/Timsort

I have also heard about it as radix sort : http://www.codercorner.com/RadixSortRevisited.htm

This is not the same as radix sort but you're right that radix is a non-comparative sorting algorithm just like the one the parent commenter described.

So, you implemented bucket sort?

Isn’t this usually taught right before sort algorithms? It’s a simple lead-in to the topic and is great for reasoning about memory overhead.

Sounds like an index sort. Your number space must have been fairly dense for this to work.

I like this! Could this be a digital implementation of the analog Spaghetti Sort? [https://en.wikipedia.org/wiki/Spaghetti_sort]

That's just the right solution if you know x and y (or even just x?) ahead of time isn't it?

And don't you mean "27" into register 27-x, do. 18 etc.?

Or even neither!

Much faster to find upper and lower bounds and essentially construct a hash table than to manually sort a whole list of non-trivial length.

Is it really? Building the hash can be made in linear time but iterating the values in order, especially when there might be gaps in the interval? Could be messy

The overhead of hashing in a hash table makes it worse than sorting algorithms without hashing.

ha, I did exactly the same thing!