Question

What is the most interesting algorithm you know?

Answer 1

Can you define what you mean by interesting?

Answer 2

No :(

Answer 3

Ok then the most interesting algorithm I know is one that I wrote. ;)

Answer 4

\begin{array}l\color{#FF0000}{\text{Nice}}\text{ }\color{#FF7F00}{\text{what}}\text{ }\color{#FFE600}{\text{does}}\text{ }\color{#00FF00}{\text{it}}\text{ }\color{#0000FF}{\text{do?}}\text{ }\color{#6600FF}{\text{When}}\text{ }\color{#8B00FF}{\text{did}}\text{ }\color{#FF0000}{\text{you}}\text{ }\color{#FF7F00}{\text{write}}\text{ }\color{#FFE600}{\text{it?}}\end{array}

Answer 5

Which one lol.

Answer 6

\begin{array}l\color{#FF0000}{\text{Y}}\color{#FF0000}{\text{ }}\color{#FF7F00}{\text{o}}\color{#FF7F00}{\text{ }}\color{#FFE600}{\text{u}}\color{#FFE600}{\text{ }}\color{#00FF00}{\text{r}}\color{#00FF00}{\text{ }}\color{#0000FF}{\text{ }}\color{#0000FF}{\text{ }}\color{#0000FF}{\text{a}}\color{#0000FF}{\text{ }}\color{#6600FF}{\text{l}}\color{#6600FF}{\text{ }}\color{#8B00FF}{\text{g}}\color{#8B00FF}{\text{ }}\color{#FF0000}{\text{o}}\color{#FF0000}{\text{ }}\color{#FF7F00}{\text{r}}\color{#FF7F00}{\text{ }}\color{#FFE600}{\text{i}}\color{#FFE600}{\text{ }}\color{#00FF00}{\text{t}}\color{#00FF00}{\text{ }}\color{#0000FF}{\text{h}}\color{#0000FF}{\text{ }}\color{#6600FF}{\text{m}}\color{#6600FF}{\text{ }}\color{#8B00FF}{\text{ }}\color{#8B00FF}{\text{ }}\color{#FF0000}{\text{:}}\color{#FF0000}{\text{ }}\color{#FF7F00}{\text{-}}\color{#FF7F00}{\text{ }}\color{#FFE600}{\text{D}}\color{#FFE600}{\text{ }}\end{array}

Answer 7

Yeah which one? lol

Answer 8

\begin{array}l\color{#FF0000}{\text{Y}}\color{#FF7F00}{\text{o}}\color{#FFE600}{\text{u}}\color{#00FF00}{\text{r}}\color{#0000FF}{\text{ }}\color{#0000FF}{\text{f}}\color{#6600FF}{\text{a}}\color{#8B00FF}{\text{v}}\color{#FF0000}{\text{o}}\color{#FF7F00}{\text{r}}\color{#FFE600}{\text{i}}\color{#00FF00}{\text{t}}\color{#0000FF}{\text{e}}\color{#6600FF}{\text{ }}\color{#6600FF}{\text{o}}\color{#8B00FF}{\text{n}}\color{#FF0000}{\text{e}}\color{#FF7F00}{\text{!}}\end{array}

Answer 9

They are all interesting to me.

Answer 10

\begin{array}l\color{#FF0000}{\text{The}}\text{ }\color{#FF7F00}{\text{only}}\text{ }\color{#FFE600}{\text{algorithm}}\text{ }\color{#00FF00}{\text{I've}}\text{ }\color{#0000FF}{\text{ever}}\text{ }\color{#6600FF}{\text{written}}\text{ }\color{#8B00FF}{\text{is}}\text{ }\color{#FF0000}{\text{this}}\text{ }\color{#FF7F00}{\text{one}}\text{ }\color{#FFE600}{\text{I'm}}\text{ }\color{#00FF00}{\text{using}}\text{ }\color{#0000FF}{\text{to}}\text{ }\color{#6600FF}{\text{color}}\text{ }\color{#8B00FF}{\text{my}}\text{ }\color{#FF0000}{\text{words}}\text{ }\color{#FF7F00}{\text{:(}}\end{array}

Answer 11

Okay, in 1980 I designed and coded a game that was subsequently ripped off by a major arcade game producer. I was writing it one a Vic-20. It was a side-scroller with a vehicle that could jump. I had to come up with an algorithm that kept all of the sprites in sync while on the ground, but followed each other like a train when jumping. Later I added an algorithm to add a somewhat similar effect while it was on the ground to simulate bumpy terrain.

Answer 12

compared to my text-coloring algorithm, that's much cooler. Is that major arcade game producer still in business today?

Answer 13

yes

Answer 14

the algorithm was actually really simple, but I was 12 at the time so I thought it was pretty genius.

Answer 15

when I was 12, I didn't even know what an algorithm was :-P

Answer 16

lol - neither did I.

Answer 17

More recently, on my first foray into Java, I wrote one that put the appropriate appendix to a number (1st, 2nd, 3rd, 4th, etc.). Before the haters start flaming me, I know that is really easy, trivial, and NO BIG DEAL, but since it was not a requirement of the assignment and I was the only one in the class that even thought to do it, I was pretty proud of myself.

Answer 18

so if I type in "42" it appends "nd" to the end?

Answer 19

hmm... let's try doing it in C!

Answer 20

Yes.

Answer 21

The trick is doing the check during your parse routine.

Answer 22

http://ideone.com/aJRon

So in C, this will be a parsing loop that will include a step checking the last character in the string

Answer 23

Yes.

Answer 24

i'm not too good with parsing though :(

Answer 25

I don't know enough C to help you there.

Answer 26

Right; although C syntax is very similar to Java, string handling in both languages is very very different anyway :(

Answer 27

Yeah I figured. Seems that way with most languages that are direct derivatives of each other.

Answer 28

that appendix algorithm isn't so trivial in C :(

Answer 29

Well it didn't seem trivial when I first came up with it, but looking back it really wasn't that hard, but isn't that always the way it is?

Answer 30

http://ideone.com/FIUgO so that's it in C++. Time to try it in C :-D

Answer 31

I think you can actually do it without parsing. It just happened that the numbers that I wanted to append were parsed strings. Let me look at my old code and see what I can come up with.

Answer 32

This is an interesting exercise in C :)

Answer 33

What you have looks about right. Does it work?

Answer 34

it seems to work

Answer 35

Yup.

Answer 36

So now see if you can do it without parsing.

Answer 37

Using int variables.

Answer 38

Should be able to do it with math. I'm trying to figure out the formula now.

Answer 39

lol

Answer 40

What's so funny. I wait. I know. I'm a geek. Tell me something I don't already know.

Answer 41

I think we might be able to use the bitwise operations and stuff to do it... or maybe the modulo operator.

Answer 42

mod 10!

Answer 43

http://ideone.com/IuM5n there we go

Answer 44

Yeah that's what I was thinking.

If Number % 10 = 1 then sNumber = Number + "st"

and so forth.

Answer 45

Yep did you test?

Answer 46

I don't like '11st' or '12nd' or '13rd' though... how do we fix those cases?

Answer 47

Yes I believe i have a check in there for those numbers.

Answer 48

http://ideone.com/0enJt fixed

Answer 49

Yep. Exactly.

Answer 50

I think the C version is easy to do now :-D

Answer 51

See. Told you it was trivial. ;)

Answer 52

hmm.... but my code won't do it properly if you give it something like 111 or 112 or 113 :(

Answer 53

Actually my java version is all on one line except for the check.

resultsArea.append(horRule + yearCount + (yearCount == 1 ? "st" : (yearCount == 2 ? "nd" : (yearCount == 3 ? "rd" : "th"))) + " year\n");

Answer 54

because you are only checking 11-13.

Answer 55

right.... how do I fix it?

Answer 56

Mod 100

Answer 57

but it will break if I give it a bigger number like 1111 or 1112 :-D

Answer 58

hmm. good point.

Answer 59

See I didn't even have to think that far because we were dealing with a program where all of my parsed numbers were < 100

Answer 60

so in order for me to make it work for arbitrary numbers, I must use strings?

Answer 61

No shouldn't. I know this is calculable.

Answer 62

http://ideone.com/G1Ydb so the string version is now working correctly.

Answer 63

Nice. That's one solution. I still think it's calculable. But I'm going to have to ponder it when I'm in math mode. I've been in writing mode all morning.

Answer 64

I shall ask this one in the Math section :-D I'm sure someone will answer it

Answer 65

I'm going to try to figure it out, but post your solution on ideone when you have it.

Answer 66

No I think mod 100 will work. Show me how it breaks.

Answer 67

http://ideone.com/lYxkE

Answer 68

you're right... it works!

Answer 69

112 mod 100 = 12
1112 mod 100 = 12
11112 mod 100 = 12
ad infinitum

Answer 70

Yea!

Answer 71

Who says you can't learn anything from trivial things?

Answer 72

See no that we know this if we EVER encounter a similar situation we will already be a step toward the solution.

Answer 73

This is why I believe there is no such thing as a 'stupid question'

Answer 74

nice conversation guys! most interesting algorithm? Hmmm I think my favorite one will be written in 2012 by myself :)

Answer 75

Yeah this was one of the more enlightening conversations that I've had lately. It's nice that i was able to walk away with something from it. I nominated agdgdgdgwngo "Best Question Asker" at the OS party because he always asks good questions. Okay well not always (what is a computer?).

Answer 76

I've thinking of asking a question like this for a couple of days, i'm more interested in interesting data structures though =)

some algorithms i've found interesting are

A*
Bellman-Ford
max flow
min cost max flow

they have quite a few uses

Answer 77

A* is interesting because it's relatively old algorithm (first described in 1968, but a simpler form of it was proposed by Dijkstra in 1959), but very long lived - it's still the gold standard for path finding. Pretty much any video game uses A* or a variant of it for AI pathfinding to this day!

Answer 78

i read only beginning but java is more similar to c++ than c :P thats why its hard to play with strings in c