381–390 of 507 posts
One reason I am amazed is because it's a dynamic programming solution to a highly formalized, abstract problem. I consider it as a kryptonite to my inner, formalism enthusiast functional programming fanboy persona.
There's something fundamentally appealing about Genetic Algorithms to me. Even though they don't apply everywhere, and even though "hill climbing with random restart" can be just as effective in many cases, there's just something awe inspiring about the idea of mimicking evolution. I also really like other related "nature inspired algorithms"[1] like Ant Colony Optimization, Particle Swarm Optimization, etc. [1]: htt…
While our algorithms might mimick evolution poorly, there's something raw about it. And it's not totally forgotten in research: https://blog.openai.com/evolution-strategies/
I stumped upon Differential Evolution which I implemented here https://github.com/peheje/nim_genetic/tree/master/Differenti...
It's fun to see how easy it is to define a new problem for it to solve.
Would like to apply it to create NN or Trees for classifications or the like.
Earlier quoted context omitted.
Nitpick: this only works if the player played exactly three moves (in the version of Tic Tac Toe I know you can play for up to 5 moves). Generalizing to 4 moves is fairly simple, to 5 moves less so; you can test all '3 from 5' combinations, which is only 10 possibilities, but I doubt the code to do this is easy to read and understand after the fact.
I'd disagree here; I still think it's quite elegant. For example, in python, it would look something like from itertools import combinations magic_square = [2,7,6, 9,5,1, 4,3,8] def did_user_win(moves): # Convert moves to magic square values magic_values = [magic_square[move] for move in moves] # Check if any sum of three moves equals 15 for three_values in combinations(magic_values,3): if sum(three_values) == 15: re…
Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
Unfortunately, as you suggest, the complexity of arbitrary precision multiplication kicks in and performance suffers.
Earlier quoted context omitted.
What I like about Dijkstra's algorithm is not that you can calculate the shortest path between two nodes, but that you can calculate the shortest path from one node to every other node, and do it one pass in O(n) time. I'm not sure it's at all obvious that it should be possible to do that.
>do it one pass in O(n) time Mind you, the “n” here is not the number of nodes! More precisely, Dijkstra’s algorithm runs in O(E + V * log V) time (if the priority queue is implemented with a heap), where E is the number of edges and V is the number of nodes. In the general case, E = O(V^2) (i.e. fully connected graph), so Dijkstra’s algorithm can calculate the shortest path to V nodes in O(V^2) time. It sounds less…
If there are negative edge-weights and cycles may occur, there is no shortest path between some nodes. You can keep going through a cycle whose total weight is negative getting "shorter" and "shorter".
It's like a race where one shortcut takes you back in time and leaves you where you started. You can use it to finish the race as far back in time before you started as you want.
Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
int32 zzzz (4 characters)
uint32 zzzz (4 characters)
int64 zzzzzzzzz (9 characters)
uint64 zzzzzzzzz (9 characters)
1-( 36123/123115) = 70% overflow int32
1-( 39774/123115) = 68% overflow uint32
1-(117909/123115) = 4.2% overflow int64
1-(118533/123115) = 3.7% overflow uint64Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...
A cool thing about binary search is you can also use it in real life. It's great for troubleshooting.