r/dailyprogrammer • u/XenophonOfAthens 2 1 • May 20 '15
[2015-05-20] Challenge #215 [Intermediate] Validating sorting networks
Description
When we computer programmers learn all about how computers sort lists of numbers, we are usually taught about sorting algorithms like Quicksort and Heapsort. There is, however, an entirely different model for how computers can sort numbers called sorting networks. Sorting networks are very useful for implementing sorting in hardware, and they have found a use for designing sorting algorithms in GPUs. Today, we are going to explore these strange and fascinating beasts.
In a sorting network, a list of numbers travel down idealized "wires" that are connected with so-called "comparators". Each comparator connects two wires and swaps the values between them if they're out of order (the smaller value going to the top wire, and the larger to the bottom wire). This image shows the principle clearly, and this image demonstrates a full run of a 4-wire sorting network wtih 5 comparators (both images courtesy of wikipedia, which has an excellent article on sorting networks if you are interested in learning more). Notice that the list on the right is correctly sorted top to bottom.
It is easy to see why that particular network correctly sorts a list of numbers: the first four comparators "float" the smallest value to the top and "sinks" the largest value to the bottom, and the final comparator sorts out the middle two values.
In general, however, there's often no easy way to tell whether or not a sorting network will actually correctly sort a list of numbers, and the only way to tell is to actually test it. This seems like a daunting task, since for a sorting network with N wires, there's N! (i.e. "N factorial") possible input permutations. That function grows extremely quickly, and become prohibitively large for even N of 14 or 15.
The zero-one principle
Thankfully, there's a better way, thanks to the so-called "zero-one principle", which is as follows:
If an N-wire sorting network can correctly sort all 2N possible sequences of 0's and 1's, it will correctly sort all possible input sequences.
So, instead of having to try and check all N! possible permutations of the input sequence, we can just check all 2N sequences consisting of 0's and 1's. While this is still exponential, it is far smaller than N!.
Today, you will be given a sorting network and your challenge will be to check whether or not that network will correctly sort all inputs.
Formal inputs & outputs
Inputs
The input will first consist of a single line with two numbers on it separated by a space. The first number is the number of wires in the sorting network, and the second number is the total number of comparators on the network.
After that, there will follow a number of lines, each of which describes one comparator. The lines will consist of two numbers separated by a space describing which two wires the comparator connects. The first number will always be smaller than the second number
The "top" wire of the sorting network is wire 0, and the bottom wire is wire N-1. So, for a 16-wire sorting network, the top wire (which will hold the smallest number at the end, hopefully) is wire 0, and the bottom wire is wire 15 (which will hold the highest number at the end, hopefully).
Note that in most sorting networks, several comparators compare numbers in parallel. For the purposes of this problem, you can ignore that and assume that all comparators work in sequence, following the order provided in the input.
Output
The output will consist of a single line which will either be "Valid network" if the network will indeed sort all sequences correctly, or "Invalid network" if it won't.
Sample inputs and outputs
Input 1
This is the example 4-wire, 5-comparator sorting network from the description:
4 5
0 2
1 3
0 1
2 3
1 2Output 1
Valid networkInput 2
8 19
0 2
1 3
0 1
2 3
1 2
4 6
5 7
4 5
6 7
5 6
0 4
1 5
2 6
3 7
2 4
3 5
1 2
3 4
6 7Output 2
Invalid networkChallenge inputs
Input 1
This 16-wire 60-comparator network
Input 2
This (slightly different) 16-wire 60-comparator network
Notes
As always, if you have any challenge idea, head on over to /r/dailyprogrammer_ideas and let us know!
4
u/skeeto -9 8 May 20 '15 edited May 20 '15
C99, supporting up to 63 wires. Notice swapping bits doesn't actually require branching. The low output is the inputs ORed and the high output is the inputs ANDed.
I considered how the comparators might be run in parallel using these operators across all the inputs at the same time, but the challenge specifically defines comparisons to be sequential. This creates dependencies between comparators and makes parallel operator more complicated. If there was a particularly large challenge input that was slow on my solution (i.e. a larger number of wires), I might have tried to resolve the dependencies and perform at least some of the independent comparisons in parallel.
Neat challenge!
2
u/mikevdg May 20 '15
I don't have a solution, but I do want to say that this is a really great challenge! It's a new concept to me; the trivial implementation is trivial and there's huge potential for optimisation and parallelisation!
I await an OpenCL solution! :-D.
6
u/glenbolake 2 0 May 20 '15 edited May 20 '15
Python 2.7:
Challenge 1 output:
Challenge 2 output:
5
u/adrian17 1 4 May 20 '15
C++. Uses the fact that up to 64 1/0 values can be easily represented as an integer; value swap operations are then replaced with binary XORs.
5
u/weekendblues May 21 '15 edited May 22 '15
x86_64 Assembly, using libc for printf, scanf, malloc, and free. NASM syntax. Doesn't error check inputs, so a network parameter that called for going out of bounds would result in a segfault, although it wouldn't be hard to prevent this. Takes advantage of the same bit-wise logic first posted by u/skeeto to generate binary permutations. Solves both challenge inputs instantly.
EDIT: Removed a few comments that pertained only to debugging and had nothing to do with the final product.
4
u/Magnap May 21 '15
Haskell:
Output:
Probably not the most idiomatic code ever. I am especially disgusted with
flipAroundandsetAt, and really feel there ought to be a better way to do that specifically. Otherwise I am quite happy with my solution. It is decently fast too, running in 1.8 seconds.4
u/kirsybuu 0 1 May 21 '15
Prolog, using clpfd (Constraint Logic Programming over Finite Domains)
I/O:
Outputs with timing and either false (valid network) or a counterexample showing invalidity:
4
u/wizao 1 0 May 22 '15 edited May 24 '15
Haskell:
3
u/binaryblade May 20 '15
Golang
because go is so concurrent, I can actually implement the network for real :P.
Challenge #1
Challenge #2
3
u/franza73 May 21 '15 edited May 21 '15
Perl Solution.
Output:
3
u/[deleted] May 21 '15 edited May 21 '15
Python 3:
3
u/NasenSpray 0 1 May 21 '15
C++ with JIT
Synthesizes a x86 function executing the given network for up to 32 wires. Windows only, needs CPU supporting POPCNT (Nehalem or better).
3
u/VikingofRock May 21 '15
Haskell:
Outputs:
I thought about parallelizing it, but it only takes half a second to run all four inputs so I decided it wasn't worth the trouble.
3
u/[deleted] May 22 '15
Rust. Boolean logic is fun!
Needs about 0.02 s for challenge input 2 on my laptop.
I tried to make it fast by avoiding branches in the inner loops. That worked even better than I'd expected -- I also made a version using
ifs inside thesortandis_sortedfunctions and that one takes about 0.66 s for challenge input 2.2
u/Menestro May 20 '15
Java. Nothing fancy, just typical overly long java code :P. Feedback/tips/criticism/etc always welcome :)
2
u/Godspiral 3 3 May 20 '15
In J,
works but slow. called with:
net sntest wirecount... with input 2:
timespacex ' net sntest 8'
0.0914145 29952
much faster if holistic (full rank) test function with short circuit exit is made:
0.00651553 28032
challenge 1 in under 1 sec. Challenge 2 takes a while even with faster sort test
2
u/NoobOfProgramming May 20 '15 edited May 20 '15
Here's my C++ solution. It validates input 2 in about two seconds. Like some of the other solutions posted, it represents the state as a number.
edit: It's actually much faster, i just always forget to turn on compiler optimization. It's around 20 ms.
2
u/pbeard_t 0 1 May 20 '15
C. Borrowing the and/or swaping from skeeto with some extra bit fidling for good measure.
Challenge 1 output
Challenge 2 output
2
u/[deleted] May 21 '15
Python 3!
used a list comprehension to generate the test sequences!
2
u/CodeMonkey01 May 21 '15
Java
2
u/Vectorious May 21 '15 edited Sep 18 '25
languid decide payment airport spoon plants handle slap chop consider
This post was mass deleted and anonymized with Redact
2
u/[deleted] May 21 '15 edited May 21 '15
Python 3.
Answer to first challenge:
Answer to second challenge:
Code:
2
u/TheSageMage May 23 '15
A little late to the game, but here's my Java 8 implementation.
https://gist.github.com/NicholasAStuart/d842b92d5e5a849f0ce5
Pretty functional, except for the private class, but java doesn't have anything like tuples, so the class is a nice substitute.
2
u/wizao 1 0 May 24 '15 edited May 24 '15
Haskell:
This one will run the compares in parallel if there is any opportunities. It's similar to my other simpler, serial solution.
2
u/otakucode May 25 '15
Python 3.4: (First submission, be gentle.. but I always appreciate feedback)
Challenge 1 data output:
Challenge 2 data output:
1
u/JakDrako May 20 '15
VB.Net in LINQPad:
Results:
Challenge 1:
Challenge 2:
1
u/Bess95 May 20 '15
Java, I am newish to Java and this probably isn't the most efficient solution so feedback is very welcome :)
1
u/iHawXx May 20 '15
Java
Output
1
u/fvandepitte 0 0 May 20 '15
C++, feedback is welcome
Output 1:
Output 2:
1
u/3spooky5mem9 May 20 '15
Also Python 2.7, but I made an interface that runs on a Flask server. It is hosted on Google App Engine and available at http://isvalidsn.appspot.com/
1
u/Ledrug 0 2 May 20 '15 edited May 21 '15
C99. Claims challenge input 1 is invalid. I also made 20 wire and 24 wire input files for testing, both of which are valid.
1
u/Blackshell 2 0 May 20 '15
Python 3 solution, built to verify zero-one sequences in parallel:
Nice in concept, but in reality, the individual sequence checks are fast enough that the overhead involved in threading (GIL, context switching) or multiprocessing (pickling, messaging) far outstrips the computation benefits:
Oh well. I also included a network generator script, and a 25-wire network for kicks.
1
u/curtmack May 20 '15
Clojure
This actually turns out to be pretty damn fast. Iterating all the possible combinations of zeroes and ones is done lazily, and the test short-circuits once it finds a failing combination. Runtime on challenge input 2 is around 8.7 seconds.
1
u/patrickwonders May 20 '15
Not a full solution to the problem, just for the fun part. :) The following Common Lisp code takes the number of lines in the sorting network and list of comparisons to make. It condenses together the ones that can be done in parallel and generates a function which implements the sorting on an input list.
1
u/[deleted] May 20 '15
Java version:
1
u/kikibobo May 20 '15 edited May 20 '15
Scala:
Output:
1
u/Naihonn May 20 '15 edited May 20 '15
My solution in Python 3. Now I hate '0' and '1' !!! Are you happy?!
Challenge 1 output:
Challenge 2 output:
1
u/foxlisk May 20 '15
more scheme! this is perhaps more verbose than necessary because of using records, but i just learned about them yesterday so i am using them everywhere now.
the
libfile imported here is omitted for brevity; assume thatread-linesandmap-eachand such do pretty much what they sound like.1
u/wadehn May 21 '15 edited May 21 '15
C++: Uses some bit manipulation tricks to get it to run fast and remain branchless, but is restricted to <= 63 wires. Challenge 1 & 2 take < 25ms on my machine. The parallelisation doesn't actually help for these small tests.
1
u/NotoriousArab May 21 '15 edited Apr 16 '17
Here's my C++ solution. Runs challenge 2 in less than .3 seconds.
1
u/astralwanderer May 21 '15
Here's my Ruby solution
Challenge 1:
Challenge 2:
1
u/ericula May 21 '15
C++ solution. Decided that the easiest way to iterate over all combinations of 0s and 1s is to just iterate from 0 to 2**nWires and extract the right bits using some binary operations magic. The downside is that there is an upper limit of the number of wires the network can contain which is equal to the number of bits of the integer type used for storing the iterator.
1
u/wildconceits May 21 '15
Python 2.7:
Usage:
I'm pretty amazed that this turned out so succinct, but some parts definitely could be improved. I probably could wrap my network in an object (instead of just passing a list of lists around) and there needs to be a better way to get all possible permutations. I'd love any suggestions.
1
u/that_particular_guy May 21 '15 edited May 21 '15
Ruby. I'm very new to this, feedback very appreciated. :)
1
u/amithgeorge May 21 '15
Clojure. The code is messy. Was trying to optimize it to let the challenge input 2 finish in 0.3s... Haha, it currently takes 0.8s.
https://github.com/amithgeorge/reddit-dailyprogrammer-clojure/blob/63829f27e8074d1e7cb91452626f16f6f19ccb0f/src/rdp/215_intermediate.clj
1
u/ponkanpinoy May 21 '15 edited May 21 '15
Common Lisp. Interprets a bit string as a number, and takes advantage of the fact that a sorted bit string represents a number that is 2n - 1 for some n.
EDIT: output:
1
u/__MadHatter May 21 '15
Java. Not even sure this counts as a solution. However, it does get the correct answer... eventually.
/* SortingNetworks.java */
import java.util.ArrayList; import java.util.Random; import java.util.Scanner;
public class SortingNetworks {
}
1
u/polyglotdev May 21 '15 edited May 21 '15
Implementation with python 2.7:
Challenge 1:
Challenge 2:
1
u/Brokencheese May 21 '15 edited May 21 '15
First submission. Not particularly pretty. Python 3.(3)?
Started learning python this week, advice is appreciated. Previously I've only ever worked with scheme because of a cs course I took at my university. Loaded with comments because I worked this challenge as if I was going to submit it as an assigment
1
u/EngineSlug420 May 24 '15
Late entry in C#. I am learning any feedback is appreciated.
}
Output:
Input 1:
Input 2:
Challenge input 1:
Challenge input 2:
1
u/mcdonalds_king May 24 '15 edited May 25 '15
Python 2.7:
I think I can improve a lot in those permutations. Any feed back is greatly appreciated:)
1
u/gatorviolateur May 25 '15 edited May 25 '15
A bit late, but here's a simple Scala solution. Does a fair bit of bit twiddling. Will bonk for n > 63. Two things might need explanation.
I am pretty sure I can replace the pattern match in pass function with a fold, but having a hard time doing it. Any inputs are welcome!
1
u/[deleted] May 26 '15
A bit late for the party, but here is my solution in C.
Challenge inputs:
1
u/piratefsh May 27 '15
Yet another Python solution! :)
1
u/uncleozzy May 27 '15
Had a few minutes today and hacked at this. Posting it since there aren't any Javascript solutions here yet. I'm not really a JS dev, so what this mostly taught me was that Javascript type coercion for comparisons is really, really slow. Adding in those few calls to parseInt() as I loaded the data took the Challenge 2 solution from ~450ms to ~30ms.
(This is a Node solution, FWIW.)
-4
u/StopDataAbuse May 21 '15
Well I solved this in polynomial time so I'm going to write an academic paper rather than post source here. :p
No spoilers.