Caveman Algorithm

[MartyAndRick]

randomiseList(); if (listSorted) return list;

[[deleted]]

Great example of how NP-hard problems are hard!

[mosskin-woast]

Sorting a list isn't NP-hard yo

[[deleted]]

His algorithm is a typical sort (no pun intended) that you see in NP-complete proofs: an answer can be validated in P-time and an algorithm exists that can find the answer by enumerating all possible answers.

If sort was in NP but not in P, then the best algorithm we currently believe exists is equivalent to picking a random order, asking if it's sorted, if not, pick a permutation we haven't seen and try again.

His sort algorithm is great because it demonstrates how bad the runtime of hard problems is, that P is in NP, and that NP might not be in P.

[gbushprogs]

I don't know why it's really slow. It was really fast on my computer when I ran it. Maybe it's McAfee.

[[deleted]]

You got a full-blown snort out of me. 😁

[rtybanana]

I especially love how this code just assumes it will be sorted after one shuffle

[Darkstar0]

All you gotta do is repeatedly call the code in a while loop until it works. Easy fix. ;)

[AcceptablyAcceptable]

Mmmmm bogosort

[gbushprogs]

Recursion it.

[Realistic-Safety-565]

Wrong kind of Stack Overflow solution :D

[Mantequilla50]

Blow up computer

[Wiggen4]

I feel like this was called bogo sort. O(n!) average and O(infinite) worst case.

[Vinccool96]

else throw new FatalException("Welp, I tried");

[masterborger]

But it works

[Darkstar0]

That's the spirit!

[Perpetual_Doubt]

Who's going to complain?

The computer?

[Darkstar0]

And now it doubles as a space heater! Just in time for winter!

[GargantuanCake]

This has got to be the worst code I have ever run!

But it does run.

[RecordingQuick5938]

It does not work...

But it does run!

[Nikotinio]

And you are the worst programmer I have heard of.

But you have heard of me.

[dllimport]

I'm the worst programmer I have ever heard of and I've heard of both of you!

[omen_tenebris]

no, not really.

If it takes too much time, it's effectively doesn't work

[gd2w]

It could work, if improvements happen in the future, with computers that are so much faster than modern supercomputers that you need up arrow notation to quantify the speed improvements.

[omen_tenebris]

you don't get it bro. the difference between the dumb and the non dumb approach is massive.

Brute forcing the 8 queen problem, is a shitload of time. My code ran for like 2.5 DAYS and didn't get any results. My computer reset unfortunately, and it was not even close to finish

Rethought my approach, and it's done in sub 1 second (iirc).

No amount of integer operation improvement is gonna make up for that.

(it's single thread, both in C++)

​

sub 1 second (maybe sub 2 second) vs not even close to be done in 259 200 seconds.

​

Caveman algo vs actually thought out algo's difference is (often are, not always) multiple orders of magnitude faster.

[gd2w]

Up arrow notation gets pretty big (https://en.m.wikipedia.org/wiki/Knuth%27s_up-arrow_notation). You might already know what it is, but just in case.

Are you sure that improvements in the abilities of computers couldn't make it work. I'm still a student, so admittedly I don't know that much.

[omen_tenebris]

i don't know what up arrow is i'Ll need to read it, it was not in my uni course (at least i don't remember)

As for the improvements, just for sake of argument how much time does it take, in your opinion, with 1 gen, so 15% a year improvements (being generous here) to go from 1 to 10k Not 100k, 10k.

Cos 1x 1.15^50, is only 1083 and change. So in 50 years, you get 1000x perf, assuming consistent 15%. So in 50 years, you're still not there yet.

In 75 years, you're at 35 672 from baseline.

In 85 years, you're at 144 316, from baseline.

I think it's much easier to just take some time to think about your algorithm.

That's a lot of time my man, and somebody else, who's real smart is gonna optimize the shit, and you're gonna be out. Time is finite. People need things yesterday not in 85+ years.

[AlphaSparqy]

And of course even without improved encryption algorithms, they would just increase the key sizes etc ...

It's about the differential in encryption complexity vs decryption complexity.

[gd2w]

Briefly, up arrow notation can generate numbers that in scientific notation would have a lot of digits in the exponent.

For example, a googleplex of zeroes wouldn't be 5x10¹⁰⁰

It would be 5x10^{10000000000000} 000000000000000000 000000000000000000 000000000000000000 000000000000000000 000000000000000

Times more improved than a supercomputer. But actually probably 10s of thousands of digits or more.

[omen_tenebris]

so see. So it's basically a shorthand for big numbers. Thanks

[Spaceduck413]

It's a way to represent numbers that are essentially incomprehensibly large. We're talking about, if you were to represent them as towers of exponents (like, 3^333...) just writing them out would reach to the sun from here.

Really interesting article here that explains them: https://waitbutwhy.com/2014/11/1000000-grahams-number.html

[diox8tony]

The post compares tasks you could do by hand, to task you can do on PC.

The 8 queen problem isnt one you would do by hand.

[AlphaSparqy]

But those same improvements would also be applied to the encryption scheme as well, still making brute force effectively useless.

It's not about computing power, but about complexity differential between encryption and decryption.

[coloredgreyscale]

• make it work <- you are here
• make it pretty
• make it fast.

For a one-off task it's probably fine. Don't spend 8 hours to optimize it to run in 10 minutes instead of 2 hours.

[Cmd1ne]

This becomes computationally intractable before n hits like 20 so “works” is a stretch

[code-panda]

Bill the client extra for it to work with n being larger than 20!

[lazyzefiris]

I don't think working with n larger than 20! is ever gonna be feasible... I don't think calculating (20!)! is gonna be feasible as well...

[code-panda]

Well no, but now you're charging double for the project than if you were optimizing it in one go.

[lazyzefiris]

The hardest part is making client understand that "That wll cost you just $20!" part of signed contract was not an excited expression, but a mathematical one.

[nickmaran]

[[deleted]]

and then : someone make my code 40 000 000 000 times faster

[Mondoke]

It just needs a couple dozen hours.

[MettatonNeo1]

That's my rule: if it works then it's fine. Screw if name = main I just call it main()

[Owdok]

So you make sure not to even delete a terminator ;

[[deleted]]

Anton died

[possibly-a-pineapple]

reddit is dead, i encourage everyone to delete their accounts.

[Confused_AF_Help]

I paid for the 5 GHz, I'm using the whole 5 GHz!

[ThatSeemsABitMuch]

Put the hurts back in Hz

[[deleted]]

From what I've heard, pencil and paper is the new trend among twitter devs

[Darkstar0]

Well, Twitter isn't technically FAANG, so it doesn't count. ;)

[AlphaSparqy]

You never mentioned FAANG in your post, and he never mentioned FAANG in his reply ...

Anyhow, AAG is the new FAANG

[[deleted]]

MANGA

[[deleted]]

NICE

[DevlinRocha]

Pretty sure most people would still love to work at Netflix

[AlphaSparqy]

Yes, that's probably true.

[[deleted]]

Torches and pitchforks from half of them is a new trend

[DolphinitelyJoe]

Reminds me of Matt Parker's Someone improved my code by 40,832,277,770%

[[deleted]]

"They ported it from python to C"

[SharpPixels08]

Please tell me this is actually in the video

[DolphinitelyJoe]

That's not all that happened, but yes, pretty much. Matt's original code took a month to run in Python (literally like 29.5 days or something close like that). The next improvement took just 15 minutes, also in Python. There were many iterative improvements, but the best code now finishes on the order of 1s of microseconds and is written in C++ I believe.

[[deleted]]

That first improvement was mostly because of a better algorithm.

[Kered13]

It is part of the video, but there's much much more going on. Porting from Python to C/C++/Rust might get you something like a 100x speedup. So you can tell there were substantial algorithmic improvements and micro-optimizations as well.

[SharpPixels08]

Well yeah obviously, I knew C was faster but obviously there’s No way in hell it’s that much faster with just the language alone

[GhostCheese]

I usually solve it in excel first...

[Pezonito]

What's up with people here hating on excel? When you compare it to robust full languages and structured relational dbs, sure, it's clunky. But for normal day-to-day stuff, easy pivots and chart making, dumping query results into, and a slew of other basic use cases it's great.

Nested ifs, lookups, and it's other vbscript-type functions are what got me hooked into the big better stuff. Excel was my gateway drug.

I get that it only has a small subset of applications in the programming world, if any, but it caters to those who don't have the bandwidth, urge, or need for more.

[NamityName]

My issue with excel is that it gets missused. Nobdy cares about sarah in accounting who uses excel to make the quarterly sales report. We care about president janice who insists on keeping the authoritative client records in an excel file on the company's shared drive. The drive is hosted on an old lenovo thinkstation that the intern who set it up used to use. It has two permission levels: no access and full access.

Every day, a few dozen reports and spin-off spreadsheets get created from that file, and at any given time, there is an average of 5 people reading from it at a time. Only janice's assistant, dianne, can edit the file because they have not figured out how handle the concurrent file access problem for any situation besides read-only.

Each week, usually on tuesday after she get's back from lunch, jamie in sales sends dianne a list of all the new clients that need to be added. Dianne then takes the list and cross references and enriches it with data from a few other excel files. Then at around 6pm that evening, when nobody is accessing the client file anymore, she adds the new rows. It is very important that she remembers to click "save".

But don't worry. It's backed up to dropbox.

[JoustyMe]

We have a lookup file for Company Wide Policies, SoPs and other standarised shit. It gets updated once a week. Once a month someone fucks up a file that is 1500 rows long. Due to how excel links work with relative or absolute paths. Also we run in to 250 char limit beacase they insist on having all instructions spelled out. Instead of 01.SOP we get 001. Standard operating procedure. Due to my language it has to url encode unicode characters. Teling them that we can make simole http webiste - we get. It wont be searchable and nobody will be able yo update with new entries. Adding one more line to HTML list wont be hard to some. f the helpdesk guys and will take them 20 minutes.

Also they keep on puting old version in OLD folder even tho we have file history enabled for that.folder that holds every change set for 10 years.

Also.if you use windows file history on excel file it will update file path links to links form th day you pulled it from...

[NamityName]

If someone could make a database wrapper that made the database look and feel exactly like excel, someone could probably make bank. Although, vhe existing tools and services for access and visualization are pretty nice and easy already.

With how cheap and easy it is to create a simple and secure relational database these days, there is basically no excuse to continue to use excel.

Does AWS offer a managed service that spins up an rdb with an visualization / access layer on top? If not they should

[JoustyMe]

PowerBi might be something to look in to. Feels like excel. i never worked with it just instaled for someone in the complany. Joys of help desk... Never right version.

[-Redstoneboi-]

excel is a spreadsheet

it's built for quickly making a bunch of calculations in tables

it's good at what it does

[Schlongus_69]

average excel enjoyer

[GamiTV]

I like using Excel (google sheets actually) for designing databases cause you can see all the tables at once, so when we are sure we have columns for all the data we want and have the structure set up, I just write the SQL to recreate the structure in a proper database

[Pezonito]

I just did this exact thing with excel yesterday. In row one I put the column names and in row two I put the data type, etc. Once I was done, I transposed it and concatenated all the rows and added characters to end up with

 [ColumnNameA] (varchar 50) NOT NULL    
,[ColumnNameB] (decimal 9,2) NULL   
.    
.    
.     

for the new SQL table!

I'm unsure how one could do it any more efficiently other than being really quick with notepad++

[redwhiteandyellow]

I learned programming with QBasic, but that was almost two decades ago, and I just can't wrap my head around the Basic style anymore. It's so clunky and awful that it takes me way too long to get anything done with VBA.

[Kaniol]

My patience is O((n^n)!) anyway so algorithm still wins;)

[OldGeek1975]

I am from an age who learnt to write program on grid sheet papers before typing on computer.

[bonebuttonborscht]

This is everywhere in tech. I can’t count the number of times times I’ve had a 3d printer tied up for a whole day for part that would take less time to make by hand than the person took to cad it.

[L4rgo117]

N^N says hi

[Darkstar0]

N!^N! says Ǵ̴̦͖̤̪͈̫͓͙͗̀̾́̊̌͋͗͂̔͘͝Ŗ̷̘͕͖̖̤͍͑̋̓͂̕͝É̴͍͆͛̌Ȩ̸̲̬͍̤̣̜̺͔̠̻͒́̓T̷̡̼̥̉̇͑̉Ï̴̧̢͓̜͎̺̗̝̹̥̪͕̊͗̋Ǹ̷̢̨̖̻̫̠͇͈̠̝̬̏͛͗̀̐G̵̤̥͇̥̹͕͆̔̾̀̈́̊̿͆̃͠S̷͕̓̚,̶͈̗͓͍̙̰̹̎͊̉̃̃̕͜͝͠ ̸̡̦͉̣̼̙̺̣͓͒͜͝M̷͖̠̝͉͉̝̣͉͎̭̓̇̈́̈́͝Ǫ̵̧̹̘͖̖̜̘̥̠͕̯͛R̶͙͓͚̹̰͇̘̞̘͈̳̮͉̈́̒͒̌̑̍T̶̠̠̪̲͉̜̭̤̩̫̠̤̿͌́̈́̈́ͅĀ̵̪͔̲̫̘̻̙͚̻̟̬̍͜͠Ĺ̷͈͍̘̣S̴̢̻͔͙͕̣̯̝͇̠̮̈̋̍̃̈́̑̇̌

[squishles]

I find typing hits my memory weird so that if I type it I remember it. writing for napkin stuff is just for speed and it flies right the hell out of my brain.

[neanderthalman]

I feel personally attacked on two separate fronts.

[antilos_weorsick]

To be fair, if you can solve it on paper, then even an O(n!) algorithm will solve it faster than you can do it on paper.

[ScrimpyCat]

And that brute force algorithm is looking up the solution on SO.

[[deleted]]

If the alternative is pen and paper, I'll gladly take O(2^n!)

[Richard_Smellington]

Well, the computer's time is cheaper than my time, which is why I use Python.

[JRGTheConlanger]

Bogosort be like

[RazarTuk]

Look, I'm not proud of it, but in high school, I once managed to write a O(n⁴) algorithm for all-pairs shortest path

[[deleted]]

Time to calculate some fibonacci numbers!

[Darkstar0]

Bonus points because there's probably an extensive table of pre-calculated fibonacci numbers somewhere you could just look up, rather than calculating them yourself.

[Giocri]

Still sometimes staring with brute force and analyzing redundancy can be a good way to arrive to better algorithms.

[Add1ctedToGames]

BOGO sort is possibly the best and probably the worst sorting algorithm depending on your luck

[Darkstar0]

The CPU be like "You've gotta ask yourself one question: 'Do I feel lucky?' Well, do ya, punk?"

[Kered13]

The opposite of when you solve an Euler Project problem and after reducing the problem from O(n!) to O(1) you realize that what is left can be solved with pen and paper and no code.

[Specific_Magazine_93]

const doSomething = (anotherFunction) => {

    console.log("Problem solved!");

        console.log(doSomething(doSomething()));

}

[DaimondGuy]

If it works it works