
9 votes

Understanding DeepMind’s sorting algorithm
5 votes 
JavaScript physics engine for the absolute beginner
1 vote 
Making bracket pair colorization 10k times faster in VSCode
7 votes 
AltF4 #47  Calculating and optimizing recipe solutions in Factorio
4 votes 
Multimodal Neurons in Artificial Neural Networks
3 votes 
I was wrong. CRDTs are the future
9 votes 
Hoare’s Rebuttal and Bubble Sort’s Comeback
6 votes 
Humble Book Bundle: Software Development by O'Reilly
8 votes 
SVTAV1, an opensource AV1 video encoder and decoder developed by Intel and Netflix
11 votes 
O(n^2), again, now in Windows Management Instrumentation
10 votes 
Programming Challenge: Convert between units
Hi everyone! It's been a long time since last programming challenge list, and here's a nice one I've encountered. If you search for something like 7km to AU, you'll get your answer. But how is it...
Hi everyone! It's been a long time since last programming challenge ^{list}, and here's a nice one I've encountered.
If you search for something like 7km to AU, you'll get your answer. But how is it done? I don't think they hardcoded all 23 units of distance and every conversion factor between them.
If you were programming a conversion system  how would you do it?
First of all, you have input in format that you can specify, for example something like this:
meter kilometer 1000 mile kilometer 1.609344 second minute 60 ...
Then you should be able answer queries. For example
7 mile meter
should convert 7 miles to meters, which is11265.41
.Can you design an algorithm that will convert any unit into any other unit?
Edit: Some conversion rates I extracted from wikipedia:
ångström 0.1nm astronomical unit 149597870700m attometre 0.000000000000000001m barleycorn 8.4m bohr 0.00846 cable length (imperial) 185.3184m cable length 185.2m cable length (US) 219.456m chain (Gunters) 20.11684m cubit 0.5m ell 1.143m fathom 1.8288m femtometre 0.00000000000001m fermi 0.00000000000001m finger 0.022225m finger (cloth) 0.1143m foot (Benoit) 0.304799735m foot (Cape) (H) 0.314858m foot (Clarke's) (H) 0.3047972654m foot (Indian) (H) 0.304799514m foot,metric 0.31622776602m foot,metric (long) 0.3m foot,metric (short) 0.30m foot (International) 0.3048m foot (Sear's) (H) 0.30479947m foot (US Survey) 0.304800610 french 0.0003m furlong 201.168m hand 0.1016m inch 0.0254m league 4828m lightday 25902068371200m lighthour 107925284880m lightminute 17987547480 lightsecond 299792458m lightyear 31557600lightsecond line 0.002116m link (Gunter's) 0.2011684m link (Ramsden's; Engineer's) 0.3048m metre 1m m 1metre km 1000m mickey 0.000127 micrometre 0.000001 mil; thou 0.0000254 mil 10km mile (geographical) 6082foot (International) quarter 0.2286m rod 5.0292m rope 6.096m shaku 0.303 0303m span (H) 0.2286m stick (H) 0.0508m toise 1.949 0363m twip 1.76310 yard 0.9144m
17 votes 
Genetic Algorithms
Introduction to Genetic Algorithms Genetic algorithms can be used to solve problems that are difficult, or impossible to solve with traditional algorithms. Much like neural networks, they provide...
Introduction to Genetic Algorithms
Genetic algorithms can be used to solve problems that are difficult, or impossible to solve with traditional algorithms. Much like neural networks, they provide goodenough solution in short amount of time, but rarely find the best one. While they're not as popular as neural networks nor as widely used, they still have their place, as we can use them to solve complicated problems very fast, without expensive training rigs and with no knowledge of math.
Genetic algorithms can be used for variety of tasks, for example for determining the best radio antenna shape, aerodynamic shapes of cars and planes, wind mill shapes, or various queing problems. We'll use it to print "Hello, World!".
How does it work?
Genetic algorithm works in three steps.
 Generate random solutions
 Test how good they are
 Pick the best ones, breed and mutate them, go to step 2
It works just like evolution in nature. First, we generate randomised solutions to our problem (in this case: random strings of letters).
Then, we test each solution and give it points, where better solutions gain more points. In our problem, we would give one point for each correct letter in the string.
Afterwards, we pick the best solutions and breed it together (just combine the strings). It's not bad idea to mutate (or randomize) the string a bit.
We collect the offsprings, and repeat the process until we find good enough solution.
Generate random solutions
First of all, we need to decide in which form we will encode our solutions. In this case, it will be simply string. If we wanted to build race cars, we would encode each solution (each car) as array of numbers, where first number would be size of the first wheel, the second number would be size of the second wheel, etc. If we wanted to build animals that try to find food, fight and survive, we would choose a decision tree (something like this).
So let's start and make few solutions, or entities. One hundred should be enough.
from random import randint goal = "Hello, World!" allowed_characters = list("qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM ,!") def get_random_entity(n, string_length): entities = [] for _ in range(0, n): entity = "" for _ in range(0, string_length): entity += allowed_characters[randint(0, len(allowed_characters)1)] entities.append(entity) return entities print(get_random_entity(100, 13))
Test how good they are
This is called a "fitness function". Fitness function determines how good a solution is, be it a car (travel distance), animal (food gathered), or a string (number of correct letters).
The most simple function we can use right now will simply count correct letters. If we wanted, we could make something like Levenshtein distance instead.
def get_fitness(entity): points = 0 for i in range(0, len(entity)): if goal[i] == entity[i]: points += 1 return points
Crossover and mutation
Now it's time to select the best ones and throw away the less fortunate entities. Let's order entities by their fitness.
Crossover is a process, when we take two entities (strings) and breed them to create new one. For example, we could just give the offspring one part from one parent and another part from second parent.
There are many ways how to do this, and I encourage you to try multiple approaches when you will be doing something like this.
P: AAAABBBBCCCC P: DDDDEEEFGGGG F1: AAAABBBFGGGG
Or we can just choose at random which letter will go from which parent, which works the best here. After we have the offsprint (
F1
), we should mutate it. What if we were unfortunate, andH
(which we need for ourHello, World!
) was not in any of the 100 entities? So we take the string and for each character of the string, there is a small chance to mutate it  change it at random.F1: ADDDEBEFGCGG F1`: ADHDEBEFGCGG
And it's done. Now kill certain part of old population. I don't know which percentage is best, but I usually kill about 90% of old population. The 90% that we killed will be replaced by new offsprings.
There is just one more thing: which entities do we select for crossover? It isn't bad idea  and it generally works just fine  to just give better entities higher chance to breed.
def get_offspring(first_parent, second_parent, mutation_chance): new_entity = "" for i in range(0, len(first_parent)): if randint(0, 100) < mutation_chance: new_entity += allowed_characters[randint(0, len(allowed_characters)1)] else: if randint(0, 1) == 0: new_entity += first_parent[i] else: new_entity += second_parent[i] return new_entity
When we add everything together, we get this output:
Generation 1, best score: 2 ::: QxZPjoptHfNgX Generation 2, best score: 3 ::: XeNlTOQuAZjuZ Generation 3, best score: 4 ::: weolTSQuoZjuK Generation 4, best score: 5 ::: weTgnC uobNdJ Generation 5, best score: 6 ::: weTvny uobldb Generation 6, best score: 6 ::: HellSy mYbZdC Generation 7, best score: 7 ::: selOoXBWoAKn! Generation 8, best score: 8 ::: HeTloSoWYZlh! Generation 9, best score: 8 ::: sellpX WobKd! Generation 10, best score: 9 ::: welloq WobSdb Generation 11, best score: 9 ::: selloc WoZjd! Generation 12, best score: 10 ::: wellxX WoVld! Generation 13, best score: 10 ::: welltX World! Generation 14, best score: 10 ::: welltX World! Generation 15, best score: 10 ::: welltX World! Generation 16, best score: 11 ::: zellov Wobld! Generation 17, best score: 11 ::: Hellty World! Generation 18, best score: 11 ::: welloX World! Generation 19, best score: 11 ::: welloX World! Generation 20, best score: 11 ::: welloX World! Generation 21, best score: 12 ::: welloX World! Generation 22, best score: 12 ::: Helloy World! Generation 23, best score: 12 ::: Helloy World! Generation 24, best score: 12 ::: Helloy World! Generation 25, best score: 12 ::: Helloy World! Generation 26, best score: 12 ::: Helloy World! Generation 27, best score: 12 ::: Helloy World! Generation 28, best score: 12 ::: Helloy World! Generation 29, best score: 12 ::: Helloy World! Generation 30, best score: 12 ::: Helloy World! Generation 31, best score: 12 ::: Helloy World! Generation 32, best score: 12 ::: Helloy World! Generation 33, best score: 12 ::: Helloy World! Generation 34, best score: 13 ::: Helloy World! Generation 35, best score: 13 ::: Hello, World!
As we can see, we find pretty good solution very fast, but it takes very long to find perfect solution. The complete code is here.
Maintaining diversity
When we solve difficult problems, it starts to be increasingly important to maintain diversity. When all your entities are basically the same (which happened in this example), it's difficult to find other solutions than those that are almost the same as the currently best one. There might be a much better solution, but we didn't find it, because all solutions that are different to currently best one are discarded. Solving this is the real challenge of genetic algorithms. One of the ideas is to boost diverse solutions in fitness function. So for every solution, we compute distance to the current best solutions and add bonus points for distance from it.
20 votes 
Coding Challenge  Design network communication protocol
Previous challenges It's time for another coding challenge! This challenge isn't mine, it's this challenge (year 5, season 3, challenge 3) by ČVUT FIKS. The task is to design a network...
It's time for another coding challenge!
This challenge isn't mine, it's this challenge (year 5, season 3, challenge 3) by ČVUT FIKS.
The task is to design a network communication protocol. You're sending large amount of bits over the network. The problem is that network is not perfect and the message sometimes arrives corrupted. Design a network protocol, that will guarantee that the decoded message will be exactly same as the message that was encoded.
MESSAGE => (encoding) => message corrupted => (decoding) => MESSAGE
Corruption
Transmitting the message might corrupt it and introduce errors. Each error in a message (there might be more than one error in a single message) will flip all following bits of the message.
Example:
011101 => 011010
(

is place where an error occured).There might be more than one error in a message, but there are some rules:

Minimum distance between two errors in a single message is
k

Number of bits between two errors is always odd number
According to these rules, describe a communication protocol, that will encode a message, and later decode message with errors.
Bonus

Guarantee your protocol will work always  even when errors are as common as possible

Try to make the protocol as short as possible.
8 votes 

I made a video to showcase / explain my free space pathfinding algorithm.
8 votes 
Programming Challenge  Find path from city A to city B with least traffic controls inbetween.
Previous challenges Hi, it's been very long time from last Programming Challenge, and I'd like to revive the tradition. The point of programming challenge is to create your own solution, and if...
Hi, it's been very long time from last Programming Challenge, and I'd like to revive the tradition.
The point of programming challenge is to create your own solution, and if you're bored, even program it in your favourite programming language. Today's challenge isn't mine. It was created by ČVUT FIKS (year 5, season 2, challenge #4).
You need to transport plans for your quantum computer through Totalitatia. The problem is, that Totalitatia's government would love to have the plans. And they know you're going to transport the computer through the country. You'll receive number
N
, which denotes number of cities on the map. Then, you'll getM
paths, each going from one city to another. Each path hask
traffic controls. They're not that much effective, but the less of them you have to pass, the better. Find path from cityA
to cityB
, so the maximum number of traffic controls between any two cities is minimal. CityA
is always the first one (0
) and cityB
is always the last one (N1
).Input format:
N M A1 B1 K1 A2 B2 K2 ...
On the first two lines, you'll get numbers N (number of cities) and M (number of paths). Than, on next
M
lines, you'll get definition of a path. The definition looks like1 2 6
, where1
is id of first city and2
is id of second city (delimited by a space). You can go from city 1 to city 2, or from city 2 to city 1. The third number (6
) is number of traffic controls.Output format:
Single number, which denotes maximum number of traffic controls encountered on one path.
Hint: This means, that path that goes via roads with numbers of traffic controls
4 4 4
is better than path via roads with numbers of traffic controls1 5 1
. First example would have output4
, the second one would have output5
.Example:
IN:
4 5 0 1 3 0 2 2 1 2 1 1 3 4 2 3 5
OUT:
4
Solution: The optimal path is either
0 2 1 3
or0 1 3
.Bonus
 Describe time complexity of your algorithm.
 If multiple optimal paths exist, find the shortest one.
 Does your algorithm work without changing the core logic, if the source city and the target city is not known beforehand (it changes on each input)?
 Do you use special collection to speed up minimum value search?
Hints
13 votes 
Xmas rush : a nice programming challenge going on right now. Only 7 days left!
6 votes 
Programming Challenge  It's raining!
Hi everyone, it's been 12 days since last programming challenge. So here's another one. The task is to make an algorithm that'll count how long would it take to fill system of lakes with water....
Hi everyone, it's been 12 days since last programming challenge. So here's another one. The task is to make an algorithm that'll count how long would it take to fill system of lakes with water.
It's raining in the forest. The forest is full of lakes, which are close to each other. Every lake is below the previous one (so 1st lake is higher than 2nd lake, which is higher than 3rd lake). Lakes are empty at the beginning, and they're filling at rate of 1l/h. Once a lake is full, all water that'd normally fall into the lake will flow to the next lake.
For example, you have lakes A, B, and C. Lake A can hold 1 l of water, lake B can hold 3 l of water and lake C can hold 5 l of water. How long would it take to fill all the lakes?
After one hour, the lakes would be:A (1/1), B (1/3), C(1/5)
. After two hours, the lakes would be:A(1/1), B(3/3), C(2/5)
(because this hour, B received 2l/h  1l/h from the rain and 1l/h from lake A). After three hours, the lakes would be:A(1/1), B(3/3), C(5/5)
. So the answer is3
. Please note, that the answer can be any rational number. For example if lake C could hold only 4l instead of 5, the answer would be2.66666...
.Hour 0:
\ / (A) \ / \ / \ / (B) \ / \ / \ /     (C)
Hour 1:
\============/ (A) \ / \ / \============/ (B) \ / \ / \ /   ======= (C)
Hour 2:
============== \============/  (A)  \================/ \==============/ \============/ (B) \ / \ / \ / ======= ======= (C)
Hour 3:
============== \============/  (A)  ======== \================/  \==============/  \============/  (B)  \===========/ \=========/ \=======/ ======= ======= (C)
Good luck everyone! Tell me if you need clarification or a hint. I already have a solution, but it sometimes doesn't work, so I'm really interested in seeing yours :)
21 votes 
Wave Function Collapse
7 votes 
The Foundations of Algorithmic Bias
8 votes 
Idle musings about the Pollard Rho method of factoring integers
5 votes 
Introduction to A*
10 votes 
Programming Challenge: Two Wizards algorithm challenge
I'm running out of ideas, if you have any, please make your own programming challenge. This challenge is about designing algorithm to solve this problem. Let's have game field of size x, y (like...
I'm running out of ideas, if you have any, please make your own programming challenge.
This challenge is about designing algorithm to solve this problem.
Let's have game field of size x, y (like in chess). There are two wizards, that are standing at
[ 0, 0 ]
and are teleporting themselves using spells. The goal is to not be the one who teleports them outside of the map. Each spell teleports wizard by at least +1 tile. Given map size and collection of spells, who wins (they do not make any mistakes)?Here are few examples:
Example 1
x:4,y:5
Spells:
{ 0, 2 }
Output:
false
Description: Wizard A starts, teleporting both of them to 0, 2. Wizard B teleports them to 0, 4. Wizard A has to teleport them to 0,6, which overflows from the map, so he loses the game. Because starting wizard (wizard A) loses, output is
false
.Example 2
x:4,y:4
Spells:
{ 1,1 }
Output:
true
Example 3
x:4,y:5
Spells:
{ 1,1 },{ 3,2 },{ 1,4 },{ 0,2 },{ 6,5 },{ 3,1 }
Output:
true
Example 4
x:400,y:400
Spells:
{9,2},{15,1},{1,4},{7,20},{3,100},{6,4},{9,0},{7,0},{8,3},{8,44}
Ouput:
true
Good luck! I'll comment here my solution in about a day.
Note: This challenge comes from fiks, programming competition by Czech college ČVUT (CTU).
15 votes 
Shor, I'll Do It  A Simple Explanation of the Algorithm Quantum Computers would use to crack RSA
4 votes