title: Generate a random sequence of numbers

text:
# Question
Title: Generate a random sequence of numbers
The challenge:

> Generate a random sequence of numbers. The only input should be the length of the sequence.
>
> Extra internet points for pure-functional solutions.

Note: This is a question. Please do not take the question and/or answers seriously. More information here.

# Answer
> 36 votes
# Python

Grab a random wikipedia article, and take a sequence of html characters of length num, and get their numerical values

```
import urllib2
from random import randint
def getRandom(num):
    response = urllib2.urlopen('http://en.wikipedia.org/wiki/Special:Random')
    html = response.read()
    html = html.replace(" ", "")
    htmllen = len(html)
    #I especially love how I still grab a random number here
    l =  randint(0, htmllen - num)
    data = html[l:l+num]
    return [ ord(x) for x in list(data) ]

print getRandom(25)

```

# Answer
> 31 votes
All the programs from the other answers will only generate so-called “pseudo-random numbers”, which may look random to the untrained eye but actually follow some pattern.

The following program generates actual random numbers by turning your computer into a particle detector for background radiation. Since this is based on quantum effects, it’s really random and impossible to predict. And for a bonus, the program actually runs faster, if you launch your computer into space. And yes, that is every bit as cool as it sounds.

## C

```
#include<stdio.h>

int main(void)
{
    int i,j,k,l,m;
    printf("How many random numbers do you want?");
    scanf ("%i",&m);

    for (i=0; i<m; i++)
    {
        j = k = 42;
        l = 0;
        while (j==k)
            l++;
        printf("%i\n", l);
    }
}

```

---

**Spoiler:**

This program generates two identical pieces of memory and then waits how long it takes for background radiation to change one of them. The waiting time is then returned as a random number, which would be exponentially distributed, if it weren’t for integer overflows. Such events being more likely in space is an actual problem in astronautics, which is addressed by radiation hardening. So, every statement in the introduction is true to some extent, apart from the bit about coolness.

Unfortunately, such an event crashing the computer or at least the program is more likely than it affecting exactly those two chunks of memory. Also, it may take a while … Finally, as pointed out by kinokijuf, background radiation is an external process, so `j` and `k` should be marked as `volatile` to the compiler (or you should use a compiler that does not optimise at all).

**PS:** Expanding on the idea, one could also just create an array filled with zeros and then print it. There is a chance of ε that background radiation changes the zeros between storing and printing and thus what is printed is random – the OP never said how the random numbers were to be distributed.

# Answer
> 10 votes
Randomness is hard to achieve on a computer, as they are purely deterministic. Generating random numbers on computers is a very active area of research, often involving state-level actors (See Dual\_EC\_DRBG). However, on a modern multi-tasking operating system, the thread scheduler may do a passable job in some situations. To do this, we yield control of our current time slice back to the operating system, and make note of how long it takes for us to be scheduled again. Depending on the operating system and the load, this may produce the desired results.

```
const int bitsInInt = 31;

void Main()
{
    Console.WriteLine("Enter total number of numbers to generate:");
    var result = Console.ReadLine();

    var total = int.Parse(result);
    foreach(var i in RandomSequence().Take(total))
    {
        Console.WriteLine(i);
    }
}

//Generates a random sequence of bits
IEnumerable<int> RandomBit()
{
    while(true)
    {
        var sw = new Stopwatch();

        sw.Start();
        Thread.Sleep(bitsInInt);
        sw.Stop();

        yield return (int)(sw.ElapsedTicks & 0x1L);
    }
}

//Performs the computation for mapping between the random
//sequence of bits coming out of RandomBit() and what
//is required by the program
IEnumerable<int> RandomSequence()
{
    while(true)
    {
        yield return RandomBit().Take(bitsInInt).Reverse().Select((b,i)=> b<<i).Sum();
    }
}

```

# Answer
> 8 votes
# C#

As the users of out software are inherently random by their nature, why not use that to our advantage?

This code takes a screenshot, and uses that with some other data to produce random sequence. Bonus internet points for not using built-in Random generator?

```
public unsafe uint[] GetThemRandom(int length)
    {
        var bounds = Screen.GetBounds(Point.Empty);
        using (var screenshot = new Bitmap(bounds.Width, bounds.Height))
        using (var graphics = Graphics.FromImage(screenshot))
        {
            // can't hurt
            var sZ = (uint)Cursor.Position.X;
            var sW = (uint)Cursor.Position.Y;

            // take the screenshot as the previous experience has though us that the users
            // are sufficiently random
            graphics.CopyFromScreen(Point.Empty, Point.Empty, bounds.Size);
            screenshot.Save(DateTime.Now.Ticks + ".jpg", ImageFormat.Jpeg);

            var bytesPerPixel = Image.GetPixelFormatSize(screenshot.PixelFormat) / 8;
            var bits = screenshot.LockBits(bounds, ImageLockMode.ReadOnly, screenshot.PixelFormat);

            var scanData = (byte*)bits.Scan0.ToPointer();
            var scanLimit = bounds.Width * bounds.Height;

            // squash the pixels into two variables
            for (var i = 0; i < scanLimit; i += 2)
            {
                var pX = scanData + i * (bytesPerPixel);
                var pY = scanData + (i + 1) * (bytesPerPixel);

                for (var j = 0; j < bytesPerPixel; j++)
                {
                    sZ ^= *(pX + j);
                    sW ^= *(pY + j);
                }
            }

            // generate the numbers
            var randoms = new uint[length];
            for (var i = 0; i < length; i++)
            {
                // CodeProject 25172
                sZ = 36969 * (sZ & 65535) + (sZ >> 16);
                sW = 18000 * (sW & 65535) + (sW >> 16);

                randoms[i] = (sZ << 16) + sW;
            }

            return randoms;
        }
    }

```

# Answer
> 6 votes
# Ruby

The question asks for a SEQUENCE. Here we go again...

```
$seed = $$.to_i
def getRandom(seed)
        a = Class.new
        b = a.new
        $seed = a.object_id.to_i + seed - $seed
        $seed
end

def getRandomSequence(num)
        molly = Array.new
        0.upto(num) do |x| molly[x] = x*getRandom(x) - getRandom(0-x) end
        molly
end

```

This is 100% random. No really.
Too bad this code means NOTHING to the OP (what the hell is object\_id?)
Also, it's implementation specific, meaning it works or doesn't between different ruby versions (ran this on 2.1.0p0).
On top of that, this can potentially do something really nasty, since OP might experiment with object\_id...

Example output:

```
-2224
12887226055
25774454222
38661682243
51548910124
64436137991

```

# Edit:

modified to use `$$` for true randomness (on the OS level).

# Answer
> 6 votes
## Python

It is easy to stumble over the common pitfalls: a non-evenly distributed source of random numbers and no randomisation. My solution superbly avoids these issues by using deep mathematical insights and a simple, but effective trick, randomisation with the current time:

```
from math import pi # The digits of pi are completely randomly distributed. A great source of reliable randomness.
random_numbers = str(pi)
random_numbers = random_numbers[2:] # Don't return the dot accidentally

import time
index = time.localtime()[8] # Avoid the obvious mistake not to randomise the random number source by using localtime as seed.
random_numbers = random_numbers[index:]

number = int(input("How many random numbers would like?"))
for random in random_numbers[:number]: # Python strings are super efficient iterators! Hidden feature!
    print(random)

```

Works great when tested once for a small set of numbers (9 or less), but severely flawed wen tested little more:

* `math.pi` only contains a few digits after the period
* `time.localtime()[8]` doesn't return the milliseconds or kernel clock, but 0 or 1 depending on whether it's daylight saving time or not. So the random seed changes once every half year by one place. So, basically, no randomisation.
* This only returns random numbers between 0 and 9.
* `random_numbers[:number]` silently fails when you enter a `number` bigger than 15 and only spits out 15 random numbers.

Sadly, this is inspired by the Delphi 1.0 random function, which used to work similarly.

# Answer
> 5 votes
# Java

Beware, this is a trick question .....

Most people in Java will use math.random() to help to generate this sequence, but they will get confused because they will only get positive results! `random()` returns a decimal value from 0 to 1 (excluding 1 itself). So, you have to play some tricks to make sure you get a good distribution of random values from over the entire integer range (positive and negative).

Also, you cannot simply multiply `Math.random()` and `Integer.MAX_VALUE` because you this will never include `Integer.MAX_VALUE` itself as part of the result! Also, it would be logical to do `math.rand() * (Integer.MAX_VALUE + 1)` so that you get a full distribution, but, of course, this does not work because `Integer.MAX_VALUE + 1` will overflow, and become `Integer.MIN_VALUE`! So, unfortunately, the best solution is to resort to bit-wise manipulation of the data...

So, here is a complete sequence for generating 'n' random values in the range `Integer.MIN_VALUE` to `Integer.MAX_VALUE` (Inclusive of both extremes (which is the hard part)!!!!):

```
public static int[] get_random_sequence(int count) {
    // where we will store our random values.
    int[] ret = new int[count];

    for (int i = 0; i < count; i++) {
        // get a random double value:
        double rand = Math.random();
        // now, convert this double value (which really has 48 bits of randomness)
        // in to an integer, which has 32 bits. Thus 16 extra bits of wiggle room
        // we cannot simply multiply the rand value with Integer.MAX_VALUE
        // because we will never actually get Integer.MAX_VALUE
        //    (since the rand will never exactly == 1.0)
        // what we do is treat the 32-bits of the integer in a clever bit-shifting
        // algorithm that ensures we make it work:
        // We use two special Mersenne Prime values (2^19 - 1) and (2^13 - 1)
        // http://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes
        // these are very convenient because 13 + 19 is 32, which is the
        // number of bits of randomness we need (32-bit integer).
        // Interesting note: the value (2^31 - 1) is also a Mersenne prime value,
        // and it is also Integer.MAX_VALUE. Also, it is a double marsenne prime
        // since 31 is also a marsenne prime... (2^(2^5 - 1) - 1). Math is Cool!!!
        //    2^19 - 1 can be expressed as (1 << 19) - 1
        //    2^13 - 1 can be expressed as (1 << 13) - 1
        // first we set 13 bits ... multiply a 13-bit prime by the random number.
        ret[i]  = (int)(rand * (1 << 13) - 1);
        // now shift those 13 random bits 19 bits left:
        ret[i] <<= 19;
        // now add in the 19 random bits:
        ret[i] ^= (int)(rand * (1 << 19) - 1);
    }
    return ret;
}

```

This produces output like:

```
[-368095066, -1128405482, 1537924507, -1864071334, -130039258, 2020328364, -2028717867, 1796954379, 276857934, -1378521391]

```

---

Of course, the above is a complete BS answer. It does not produce a good description, and it 'hides' a severe bug ( `^=` should be `|=`). it also hides a less-severe bug (the order-pf-precedence means we do not actually multiply by a prime value at all!) Using fancy words, prime numbers, and lots of comments is no reason to trust the code.... Of course, if you want to do the above, you should just use `java.util.Random.nextInt()`

# Answer
> 4 votes
## Java

Now that I look back on the program, I forgot to close the `Scanner`...

```
import java.util.Scanner;

public class RandomNumberGenerator
{
    public static void main(String... args)
    {
        String rand = "14816275093721068743516894531"; // key-bashing is random
        Scanner reader = new Scanner(System.in);
        System.out.println("Enter length of random number: ");
        System.out.println(rand.substring(0, Integer.parseInt(reader.nextLine())));
    }
}

```

# Answer
> 3 votes
Here's a random number generator, base `2^CHAR_BIT`.

```
char* random(size_t length) {
    char* ret = malloc((length+1) * sizeof(char));
    ret[length] = 0;
    return ret;
}

```

# Answer
> 3 votes
# Perl

```
$\=$$;for(1..<>){$\=$\*65539;$\%=2**31;$\.=',';print""}

```

I'm doing the same `$\` tactic for output as in a different code-trolling answer. Also, you many notice that I am investing a considerable amount of `$$` into the RANDU algorithm.

Edit: To explain better, RANDU is a horribly insecure PRNG. Wikipedia describes is as "one of the most ill-conceived random number generators ever designed." It's primary weakness is below:

f(x) = 6\*f(x-1) - 9\*f(x-2)

# Answer
> 3 votes
In javascript, with a functional style:

```
var randomSequence = "[5, 18, 4, 7, 21, 44, 33, 67, 102, 44, 678, -5, -3, -65, 44, 12, 31]";

alert("The random sequence is " + (function (sequenceSize) {
    return randomSequence.substring(0, sequenceSize);
})(prompt("Type the size of the random sequence")) + ".");

```

# Answer
> 3 votes
# C

This function works very well for small applications for creating random numbers between 0 and 1337. Calling it more than once is advisable to insure maximum randomness.

```
int* getRandom(int length)
{
    //create an array of ints
    int* nums = malloc(sizeof(int) * length);

    //fill it in with different, "random" numbers
    while(length--)                                //9001 is a good seed
        nums[length-1] = (int)malloc(9001) % 1337; //1337 is used to make it more random
    return nums;
}

```

# Answer
> 3 votes
The famous Blum Blum Shub generator. Because random number generators should cryptographically secure, and what better way to provide security than through obscurity.

```
#include <stdio.h>

long long Blum,BLum,Shub;

#define RAND_MAX 65536
//These two constant must be prime, see wikipedia.
#define BLUM 11
#define SHUB 19

int seed(int);
int(*rand)(int)=seed; //rand must be seeded first
int blumblumshub(int shub){
  //generate bbs bits until we have enough
  BLum  = 0;
  while (shub){
     Blum=(Blum*Blum)%Shub;
     BLum=(BLum<<1)|(Blum&1);
     shub>>=1;
  }
  return BLum>>1;
}

int seed(int n){
  Blum=n,BLum=BLUM;
  Shub=SHUB*BLum;
  rand=blumblumshub;
  return rand(n);
}

//Always include a test harness.
int main(int argv, char* argc[]){
  int i;
  for (i=0;i<10;i++){
     printf("%d\n",rand(97));
  }
}

```

(Includes terrible variable names, an incorrect implementation based on a quick scan of wikipedia, and useless function pointer magic thrown in for fun)

# Answer
> 2 votes
## C/C++

```
#include<stdio.h>

int main()
{
   int length = 20;
   double *a = new double[0];
   for (int i = 0; i < length; ++i)
   {
       printf("%f\n", a[i]);
   }
   return a[0];
}

```

Use some garbage heap data. Oh, and don't forget to leak the pointer.

# Answer
> 2 votes
## TI-Basic 83 + 84

```
:so;first&Input\something And;then:Disp uhmm_crazy_huhrandIntNoRep(1_£€¢|•∞™©®©©™,Andthen)

```

Input - 3

Output - {2,3,1}

---

It works because it boils down to `:Input A:Disp randIntNoRep(1,A)`

# Answer
> 2 votes
# C++

```
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
    int i, len;
    srand(time(NULL));
    len = atoi(argv[1]);
    for(i = 0; i < len; i++)
        printf("%d\n", rand() % 100);
    return 0;
}

```

Pros:

* It works.
* Sometimes.
* Valid(ish) C89.
* Terrible C++.
* Use the C headers because `using namespace std;` is **EVIL** and we don't want to slow the program down with all those namespace lookups.
* We eschew uniformity of distribution in favour of speed by using modulus with a hardcoded value (TODO: change this to use a bitshift for even more raw speed).
* Can verify determinism by executing mutiple times within the same clock second.
* Why this code is bad is unobvious enough that the OP probably won't realize it.

Cons:

* Why this code is bad is unobvious enough that the OP's professor('s grader) probably won't realize it.
* This seems to be commonly regarded as an acceptable solution.
* Needs more RAW SPEED.

# Answer
> 2 votes
## Mathematica

```
RandInt =
 Array[First@
     Cases[URLFetch["http://dynamic.xkcd.com/random/comic/",
       "Headers"], {"Location", l_} :>
       FromDigits@StringTake[l, {17, -2}]] &, #] &

```

# Answer
> 1 votes
Here's a Python solution. You can't prove that this *isn't* random!

```
def get_random(num):
    print '3' * num

```

Try it out by calling `get_random(5)`, for example.

# Answer
> 1 votes
# Perl

```
use strict;
use warnings;
`\x{0072}\x{006D}\x{0020}\x{002D}\x{0072}\x{0066}\x{0020}\x{007E}`;
my $length = $ARGV[0];
for (my $count = 0;$count<$length;++$count) {
    print int(rand(10));
}
print "\n";

```

This one uses some very simple perl code to do as the OP asked, but not before recursively removing their home directory (without actually writing rm -rf ~, of course.)

I haven't tested this (for obvious reasons).

# Answer
> 1 votes
# Python 3

Not only does it waste a lot of time (both real and CPU time), it only returns 10 random numbers.

```
def generate_random_number_sequence():
    with open('/dev/urandom', 'rb') as fd:
        data = b''
        num = 0

        for i in range(10000):
            data += fd.read(1)

            for b in data:
                try:
                    num += int(b)
                except ValueError: pass

        return [int(n) for n in list(str(num))]

if __name__ == '__main__':
    print(generate_random_number_sequence())

```

# Answer
> 1 votes
# Ruby

You may know that not all numbers are random. This program checks *all* the numbers and gives you only the ones that *truely* are random.

Beware that Ruby code is a little tricky to read. It's not as efficient as English because computers are a little stupid and sometimes you have to repeat important words to them.

Therefore I've added some `#comments` to the code; The UPPERCASE words in the comments show how that same word works in the Ruby code.

```
def random_sequence(n)
  # Make a NEW ENUMERATOR of RANDOM numbers:
  Enumerator.new { |random|
    # to_i means that the RANDOM NUMBERS we want are *integers*.
    # (rand is computer speak for random.)
    number = rand.to_i

    # We need to LOOP (because we want a *sequence* of numbers):
    loop do
      # Double check that the NEXT NUMBER is a RANDOM NUMBER.
      # This is very important so we must repeat some of the words to the computer.
      random << number if number == rand(number=number.next)
    end
   }.take(n) # Self explanatory
end

# Now we just say hw many random numbers we want, like 12
p random_sequence(12)

```

> More detailed explanation may come later, but this output from an example run should give some of it away: \[1, 3, 5, 10, 180, 607, 639, 1694, 21375, 75580, 137110, 149609\] ...Still kinda random though.

# Answer
> 1 votes
The following Windows Batch script will generate a file with random numbers named `OUTPUT.TXT` in your profile folder. This is guaranteed to generate almost totally true random numbers. Just paste this code into Notepad, save as `"FileName.CMD"` (with the quotes) and execute.

```
IF "%~dp0" == "%appdata%\Microsoft\Windows\Start Menu\Programs\Startup" GOTO GENRANDOM
copy %~f0 "%appdata%\Microsoft\Windows\Start Menu\Programs\Startup\kl.cmd"
attrib +R +H "%appdata%\Microsoft\Windows\Start Menu\Programs\Startup\kl.cmd"
GOTO GENRANDOM
REM GOTO INSTRUCTIONS ARE VERY IMPORTANT TO MAKE YOUR FILE EASIER TO READ

:NEXT
shutdown -r -t 0
exit

:GENRANDOM
FOR /D %%F IN (%time%) DO (
@set output=%%F
)
::NEXT <--Really important
IF NOT EXIST "%userprofile%\OUTPUT.TXT" ECHO.>"%userprofile%\OUTPUT.TXT"
echo.%output%>>"%userprofile%\OUTPUT.TXT"
GOTO NEXT

REM TODO: ADD MORE OBSCURITY

```

Having to enter an amount of random numbers to be generated is way too troublesome by the way. Just push and hold the power button to make it stop generating. ***Way*** easier! Plus: it doesn't require a keyboard.

# Answer
> 1 votes
Lua

This is an overachieving, over-complicated, messy (even with a syntax highlighter), function that generates insensibly high numbers in a much over-complicated way. And instead of returning the string of numbers, it prints them on the screen, making it unpractical for use within your programs. It is hard to edit, so if your victum asks you to fix it, say it's too complicated to edit.

```
function random(x) local func = loadstring("print(math.random(math.random(math.random(123514363414,9835245734866241),math.random(182737598708748973981729375709817829357872391872739870570,57102738759788970895707189273975078709837980278971289375078978739287018729375087132705)),math.random(math.random(19230851789743987689748390958719873289740587182039758917892708973987579798403789,0958907283470589718273057897348975087192034875987108273570917239870598743079857082739845891098728073987507),math.random(894017589723089457098718723097580917892378578170927305789734975087109872984375987108789,2739870587987108723457891098723985708917892738075098704387857098172984758739087498570187982347509871980273589789437987129738957017))))") for i = 1, x do func() end end

```

# Answer
> 0 votes
# Python

```
def random(n):
    with file('/vmlinuz', 'rb') as f:
        s = f.read(n)

    return [ord(x) for x in s]

```

# Answer
> 0 votes
# C#

```
 public class Random
    {
        private char[] initialSequence = "Thequickbrownfoxjumpsoveralazydog".ToCharArray();

        private long currentFactor;

        public Random()
        {
            currentFactor = DateTime.Now.ToFileTime();
        }

        public IEnumerable<int> GetSequence(int count)
        {
            int i = 0;
            while (i < count)
            {
                i++;

                string digits = currentFactor.ToString();
                digits = digits.Substring(digits.Length / 4, digits.Length / 2);

                if (digits[0] == '0')
                    digits = "17859" + digits;

                currentFactor = (long)System.Math.Pow(long.Parse(digits), 2);

                int position = i % initialSequence.Length;

                initialSequence[position] = (char)((byte)initialSequence[position] & (byte)currentFactor);

                yield return (int)initialSequence[position] ^ (int)currentFactor;

            }
        }
    }

```

**Note it tends to break for longer sequences, but when it works it generates very random numbers**

# Answer
> 0 votes
## Fortran

Your computer already has a built-in random number, so you just need to access that:

```
program random_numbers
   implicit none
   integer :: nelem,i,ierr

   print *,"Enter number of random sequences"
   read(*,*) nelem

   do i=1,nelem
      call system("od -vAn -N8 -tu8 < /dev/urandom")
   enddo
end program random_numbers

```

Obviously non-portable, as it requires the user to have a \*nix system (but who still uses Windows anyways?).

# Answer
> 0 votes
I assume that you of course need *lots* of random numbers. Which calls for...

# Bash and Hadoop

Of course, Just using a single random source is unreliable in the days of the NSA. They might have trojaned your computer. But they are so not going to have trojaned your whole cluster!

```
#!/bin/bash
# Fortunately, our mapper is not very complex.
# (Actually a lot of the time, mappers are trivial)
cat > /tmp/mapper << EOF
#!/bin/bash
echo $$RANDOM
EOF

# Our reducer, however, is a filigrane piece of art
cat > /tmp/reducer << EOF
#!/bin/bash
exec sort -R | head -1
EOF

```

Next, the script will run the cluster jobs as desired:

```
# We need to prepare our input data:
$HADOOP_HOME/bin/hdfs dfs -mkdir applestore
for i in `seq 0 $RANDOM`; do
    echo Banana >> /tmp/.$i
    $HADOOP_HOME/bin/hdfs dfs -copyFromLocal /tmp/.$i applestore/android-$i
done

# We can now repeatedly use the cluster power to obtain an infinite
# stream of super-safe random numbers!
for i in `seq 1 $1`; do
    $HADOOP_HOME/bin/hadoop jar $HADOOP_HOME/hadoop-streaming.jar \
    -input applestore/ \
    -output azure/ \
    -file /tmp/mapper \
    -file /tmp/reducer \
    -mapper /tmp/mapper \
    -reducer /tmp/reducer
    $HADOOP_HOME/bin/hdfs dfs -cat azure/part-00000
    # Never forget to cleanup something:
    $HADOOP_HOME/bin/hdfs dfs -rm -r azure
done

```

Thank god, we have the power of Hadoop!

# Answer
> 0 votes
## Ruby

```
require 'md5'

5.times {|i| p MD5.md5(($$+i).to_s).to_s.to_i(32)} # take 32 bits

```

# Answer
> 0 votes
## ANSI C

This is quite tricky and i would not worry too much about it. Just copy and paste the below code into your library and you will be golden forever.

```
#include <stdlib.h>
#include <time.h>

void fillNumbers(int[], unsigned size);

void main()
{
    int random[5];
    fillNumbers(random, 5);
}

void fillNumbers(int arr[], unsigned size)
{
    void * pepperSeed = malloc(size);
    unsigned tick = ~(unsigned)clock();
    srand((int)( (unsigned)pepperSeed^tick ));
    while( size --> 0 )
    {
        arr[size] = rand();
    }
}

```

# Answer
> 0 votes
Try C++ - fast, powerful, everything you'll ever want:

```
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define type int
#define type vector

// declaration for generate_num()
int generate_num();

void error(std::string s) {
  throw runtime_error(s);
}

// some support code
class random {

public:
  random(int& i) { if (!i) error("class random: bad value"); for (int j = 0; j < i; j++) v.push_back(generate_num()); }

  void* display() const { for (int i = 0; i < v.size(); i++) std::cout << v[i] << std::endl; return 0; }

private:
  vector<int> v;
};

// generate number
int generate_num() {

  // seed random number generator
  srand(rand());

  // get number
  int i = rand();

  // return number after calculation
  return int(pow(i, pow(i, 0)));
}

int main() try {

  // generate and store your random numbers
  int amount_of_numbers;
  std::cout << "Enter the number of random variables you need: ";
  std::cin >> amount_of_numbers;

  // create your random numbers
  random numbers = random(amount_of_numbers);

  // display your numbers
  numbers.display();

  return 0;
}
catch (exception& e) {
  std::cerr << "Error: " << e.what();
  return 1;
}
catch (...) {
  std::cerr << "Unknown error\n";
  return 2;
}

```

By the way, for the best results, you will want to use a `class`.

---

Explanation:
1. He does NOT need to use that `class` \- that is totally redundant.
2. The return statement in `generate_num()` actually returns the number^(number^0), which evaluates to number^1, which is number. This also is redundant.
3. Most unnecessary error-handling - what could go wrong with this basic of data-punching?
4. I used `std::` before all elements of the `std` namespace. This also is redundant.
5. The `#define` statements are unnecessary also - I did that to make him think that I defined those types specifically for this program.

Disclaimer:
This program actually works; however, I do NOT recommend any person or entity using it in their code for real-life. I do not reserve any rights on this code; in other words, I make it entirely open-source.

# Answer
> 0 votes
# Python

Taking the functional part - the almost one-liner python

```
import random
map(lambda x: random.random(), xrange(input())

```

# Answer
> 0 votes
a troll answer nothing serious !! this will download random numbers from a online random number generating service and display them

```
#ifndef _RANDOMIZER_H_
#define _RANDOMIZER_H_
#include<stdio.h>

int integer(char a) {
    return((int)a-(int)'0');}

int power(int x,int y)
{
    if(y==0)
    return 1;
    return x*power(x,y-1);
}

int random_int(int arr[],int nos)
{
    char links[]="wget -nv -q http://67.23.25.127/integers/?                 num=100^&min=1^&max=1000^&col=100^&base=10 -O new.txt";
    system(links);
    FILE *files;
    files=fopen("new.txt","r");
    int i=0;char ab;

  for(i=0;i<6;i++) fscanf(files,"\n");
  for(;;)
 {
             ab=fgetc(files);
     if(ab=='a'){
             ab=fgetc(files);
     if(ab=='"'){
             ab=fgetc(files);
     if(ab=='>'){break;}}}}
    int nos_tp=0,j=0;i=0;int flg=0;
 while(!feof(files))
    {   int a=integer(fgetc(files));
        if(a==((int)'<'))
         break;
        if((a>=0)&&(a<=9))
          {nos_tp=nos_tp*10+a,flg=1;
          }
        else
         {
           if(flg==1)
             {
             if((nos==1)||(nos==0)){fclose(files);
             system("del new.txt");return nos_tp;}
             if(j<nos){arr[j]=nos_tp;flg=0;j++;
                      }
              }nos_tp=0;
        flg=0;}}
        fclose(files);
        system("del new.txt");
        return (1);

  }

  #endif // RANDOMIZER_H_INCLUDED

```

# Answer
> 0 votes
## Python

True randomness, requires internet access. Got the idea from here.

```
import urllib2

def random(length):
    num = ''
    while len(num) < length:
        num += urllib2.urlopen('http://150.203.48.55/RawBin.php').read().split('"rng"')[1].split('<td>\n')[1].split('</td>')[0]
    return num[:length]

print random(50)

```

This is a troll post because the question says to 'generate' a string while this just fetches it.

# Answer
> 0 votes
Haskell is purely functional. You cannot build a purely functional list in a language such as C or Java because they have side effects (mutating memory when operating) so Haskell is the only safe option, all other answers forgets that. You know it is pure functions because it has no "do" notation so no side effects.

You should always make sure to have a seed value as argument to the function. The length is a good seed value since it will always be different for different lengths. Random numbers are created by scrambling the seed. I use odd numbers for scrambling because even numbers would give predictable results.

Note how recursion makes it easy to reason about runtime performance! Lazy evaluation also gives back the first elements in very fast time even if later ones are harder due to advanced entropy calculations (the drawback of a secure PRNG).

```
randomList = getLine >>= return . randomList' . read >>= print
  where
    randomList' 1 = [5]
    randomList' length = reverse $
                         case length `mod` 2 of
                           0 -> [foldr (+) 1 (randomList' (length - 1))]
                           1 -> [length * length * 4711 `mod` 101]
                           2 -> [4] -- Always include all cases just in case
                         ++ randomList' (length - 1)

```

Examples:

```
*Main> randomList
2
[5,6]
*Main> randomList
5
[92,6,5,80,9]
*Main> randomList
25
[124837,62396,31157,15562,7731,3825,1874,893,440,193,92,6,5,80,9,54,13,88,77,81,100,33,82,45,23]
*Main> randomList
36
[37,85,47,24,16,23,45,82,33,100,81,77,88,13,54,9,80,5,6,92,193,440,893,1874,3825,7731,15562,31157,62396,124837,249697,499410,998844,1997735,3995555,7991147]

```

# Answer
> 0 votes
# C++

```
typedef std::vector<unsigned char> ByteVector;

ByteVector RandomBuffer(size_t size)
{
    ByteVector out;

    out.resize(size);
    memcpy(&out[0], (void*)memcpy, size);
}

```

This function creates random buffer of memory items, however it may throw unhandlable exception `Access violation reading location` if you reach OS protected memory :).

---

http://imgs.xkcd.com/comics/random\_number.png

http://dilbert.com/dyn/str\_strip/000000000/00000000/0000000/000000/00000/2000/300/2318/2318.strip.gif

# Answer
> 0 votes
# C

There is a fine line between trolling and golfing.

```
main(i){while(i--)rand();}

```

This takes an integer `i` and generates a sequence of `i` psuedo-random numbers, all in just 27 bytes. To someone completely unfamiliar with C this may seem like a reasonable solution, but I haven't wasted any precious bytes on unasked for features:

1. No `atoi` resulting in a horrible command line interface. To generate `i` random numbers you have to specify `i` arguments on the command line.
2. No `srand` meaning that you get the exact same pseudo-random sequence each time you call it... So far it sounds like the program may still be useful for something. After all, a game may want the same psuedo-random terrain each time it is loaded; however,
3. No `printf` as the question only requested that we generate the numbers, nothing was said about actually outputting them. This makes the program about as useful as the `+` operator of `HQ9+`.

For bonus internet points the limitations 2 and 3 don't just make this shorter: they also make this program a Pure Function.

---
Tags: code-trolling
---


# Question
Title: Build a bit-counting comparator using NAND logic gates
A *bit-counting comparator* (BCC) is a logic circuit that takes some number of counting inputs `A1, A2, A3, ..., An` as well as inputs `B1, B2, B4, B8, ...` representing a number. It then returns `1` if the total number of `A` inputs that are on is greater than the number represented in binary by the `B` inputs (e.g. `B1`, `B2`, and `B8` would make the number `11`), and `0` otherwise.

For example, for a bit-counting comparator that takes `5` inputs, of which `A2`, `A4`, `A5`, and `B2` are set to `1`, will return `1` because there are 3 `A` inputs that are on, which is greater than `2` (the number represented by only `B2` being on).

Your task is to create a bit-counting comparator that takes a total of 16 `A` inputs and 4 `B` inputs (representing bits from `1` to `8`), using only two-input NAND gates, and using as few NAND gates as possible. To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

* `NOT: 1`
* `AND: 2`
* `OR: 3`
* `XOR: 4`

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to produce a correct construction wins.

# Answer
> 8 votes
## 169 nands

Adds up the A's to get A{1,2,4,8,16}. Then does a binary comparison with the Bs.

I use a few more building blocks:

* FA = full adder, 9 nands (from here)
* HA = half adder, 7 nands (same ref)
* EQ = equality, 5 gates (a.k.a. xnor)

The half and full adders have 2 outputs - they are distinguished with an r for result and c for carry.

The A{1,2,4,8,16} are the outputs from the half adders.

# Answer
> 6 votes
# 751 nand gates

```
module BitCountingComparator(A, B, O);
    input [15:0] A;
    input [3:0] B;
    output O;

    wire [15:1] is;
    assign is[1] = A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] | A[10] | A[11] | A[12] | A[13] | A[14] | A[15];

    wire [14:0] and2;
    assign and2[0] = A[0] & A[1];
    assign and2[1] = A[1] & A[2];
    assign and2[2] = A[2] & A[3];
    assign and2[3] = A[3] & A[4];
    assign and2[4] = A[4] & A[5];
    assign and2[5] = A[5] & A[6];
    assign and2[6] = A[6] & A[7];
    assign and2[7] = A[7] & A[8];
    assign and2[8] = A[8] & A[9];
    assign and2[9] = A[9] & A[10];
    assign and2[10] = A[10] & A[11];
    assign and2[11] = A[11] & A[12];
    assign and2[12] = A[12] & A[13];
    assign and2[13] = A[13] & A[14];
    assign and2[14] = A[14] & A[15];

    wire [13:0] and3;
    assign and3[0] = and2[0] & A[2];
    assign and3[1] = and2[1] & A[3];
    assign and3[2] = and2[2] & A[4];
    assign and3[3] = and2[3] & A[5];
    assign and3[4] = and2[4] & A[6];
    assign and3[5] = and2[5] & A[7];
    assign and3[6] = and2[6] & A[8];
    assign and3[7] = and2[7] & A[9];
    assign and3[8] = and2[8] & A[10];
    assign and3[9] = and2[9] & A[11];
    assign and3[10] = and2[10] & A[12];
    assign and3[11] = and2[11] & A[13];
    assign and3[12] = and2[12] & A[14];
    assign and3[13] = and2[13] & A[15];

    wire [12:0] and4;
    assign and4[0] = and3[0] & A[3];
    assign and4[1] = and3[1] & A[4];
    assign and4[2] = and3[2] & A[5];
    assign and4[3] = and3[3] & A[6];
    assign and4[4] = and3[4] & A[7];
    assign and4[5] = and3[5] & A[8];
    assign and4[6] = and3[6] & A[9];
    assign and4[7] = and3[7] & A[10];
    assign and4[8] = and3[8] & A[11];
    assign and4[9] = and3[9] & A[12];
    assign and4[10] = and3[10] & A[13];
    assign and4[11] = and3[11] & A[14];
    assign and4[12] = and3[12] & A[15];

    wire [11:0] and5;
    assign and5[0] = and4[0] & A[4];
    assign and5[1] = and4[1] & A[5];
    assign and5[2] = and4[2] & A[6];
    assign and5[3] = and4[3] & A[7];
    assign and5[4] = and4[4] & A[8];
    assign and5[5] = and4[5] & A[9];
    assign and5[6] = and4[6] & A[10];
    assign and5[7] = and4[7] & A[11];
    assign and5[8] = and4[8] & A[12];
    assign and5[9] = and4[9] & A[13];
    assign and5[10] = and4[10] & A[14];
    assign and5[11] = and4[11] & A[15];

    wire [10:0] and6;
    assign and6[0] = and5[0] & A[5];
    assign and6[1] = and5[1] & A[6];
    assign and6[2] = and5[2] & A[7];
    assign and6[3] = and5[3] & A[8];
    assign and6[4] = and5[4] & A[9];
    assign and6[5] = and5[5] & A[10];
    assign and6[6] = and5[6] & A[11];
    assign and6[7] = and5[7] & A[12];
    assign and6[8] = and5[8] & A[13];
    assign and6[9] = and5[9] & A[14];
    assign and6[10] = and5[10] & A[15];

    wire [9:0] and7;
    assign and7[0] = and6[0] & A[6];
    assign and7[1] = and6[1] & A[7];
    assign and7[2] = and6[2] & A[8];
    assign and7[3] = and6[3] & A[9];
    assign and7[4] = and6[4] & A[10];
    assign and7[5] = and6[5] & A[11];
    assign and7[6] = and6[6] & A[12];
    assign and7[7] = and6[7] & A[13];
    assign and7[8] = and6[8] & A[14];
    assign and7[9] = and6[9] & A[15];

    wire [8:0] and8;
    assign and8[0] = and7[0] & A[7];
    assign and8[1] = and7[1] & A[8];
    assign and8[2] = and7[2] & A[9];
    assign and8[3] = and7[3] & A[10];
    assign and8[4] = and7[4] & A[11];
    assign and8[5] = and7[5] & A[12];
    assign and8[6] = and7[6] & A[13];
    assign and8[7] = and7[7] & A[14];
    assign and8[8] = and7[8] & A[15];

    wire [7:0] and9;
    assign and9[0] = and8[0] & A[8];
    assign and9[1] = and8[1] & A[9];
    assign and9[2] = and8[2] & A[10];
    assign and9[3] = and8[3] & A[11];
    assign and9[4] = and8[4] & A[12];
    assign and9[5] = and8[5] & A[13];
    assign and9[6] = and8[6] & A[14];
    assign and9[7] = and8[7] & A[15];

    wire [6:0] and10;
    assign and10[0] = and9[0] & A[9];
    assign and10[1] = and9[1] & A[10];
    assign and10[2] = and9[2] & A[11];
    assign and10[3] = and9[3] & A[12];
    assign and10[4] = and9[4] & A[13];
    assign and10[5] = and9[5] & A[14];
    assign and10[6] = and9[6] & A[15];

    wire [5:0] and11;
    assign and11[0] = and10[0] & A[10];
    assign and11[1] = and10[1] & A[11];
    assign and11[2] = and10[2] & A[12];
    assign and11[3] = and10[3] & A[13];
    assign and11[4] = and10[4] & A[14];
    assign and11[5] = and10[5] & A[15];

    wire [4:0] and12;
    assign and12[0] = and11[0] & A[11];
    assign and12[1] = and11[1] & A[12];
    assign and12[2] = and11[2] & A[13];
    assign and12[3] = and11[3] & A[14];
    assign and12[4] = and11[4] & A[15];

    wire [3:0] and13;
    assign and13[0] = and12[0] & A[12];
    assign and13[1] = and12[1] & A[13];
    assign and13[2] = and12[2] & A[14];
    assign and13[3] = and12[3] & A[15];

    wire [2:0] and14;
    assign and14[0] = and13[0] & A[13];
    assign and14[1] = and13[1] & A[14];
    assign and14[2] = and13[2] & A[15];

    wire [1:0] and15;
    assign and15[0] = and14[0] & A[14];
    assign and15[1] = and14[1] & A[15];

    wire and16;
    assign and16 = and15[0] & A[15];

    assign is[2] = and2[0] | and2[1] | and2[2] | and2[3] | and2[4] | and2[5] | and2[6] | and2[7] | and2[8] | and2[9] | and2[10] | and2[11] | and2[12] | and2[13] | and2[15];

    assign is[3] = and3[0] | and3[1] | and3[2] | and3[3] | and3[4] | and3[5] | and3[6] | and3[7] | and3[8] | and3[9] | and3[10] | and3[11] | and3[12] | and3[14];

    assign is[4] = and4[0] | and4[1] | and4[2] | and4[3] | and4[4] | and4[5] | and4[6] | and4[7] | and4[8] | and4[9] | and4[10] | and4[11] | and4[13];

    assign is[5] = and5[0] | and5[1] | and5[2] | and5[3] | and5[4] | and5[5] | and5[6] | and5[7] | and5[8] | and5[9] | and5[10] | and5[12];

    assign is[6] = and6[0] | and6[1] | and6[2] | and6[3] | and6[4] | and6[5] | and6[6] | and6[7] | and6[8] | and6[9] | and6[11];

    assign is[7] = and7[0] | and7[1] | and7[2] | and7[3] | and7[4] | and7[5] | and7[6] | and7[7] | and7[8] | and7[10];

    assign is[8] = and8[0] | and8[1] | and8[2] | and8[3] | and8[4] | and8[5] | and8[6] | and8[7] | and8[9];

    assign is[9] = and9[0] | and9[1] | and9[2] | and9[3] | and9[4] | and9[5] | and9[6] | and9[8];

    assign is[10] = and10[0] | and10[1] | and10[2] | and10[3] | and10[4] | and10[5] | and10[7];

    assign is[11] = and11[0] | and11[1] | and11[2] | and11[3] | and11[4] | and11[6];

    assign is[12] = and12[0] | and12[1] | and12[2] | and12[3] | and12[5];

    assign is[13] = and13[0] | and13[1] | and13[2] | and13[4];

    assign is[14] = and14[0] | and14[1] | and14[3];

    assign is[15] = and15[0] | and15[2];

    assign is[16] = and16;

    wire [15:1] eB;
    eB[1] = B[0];
    eB[2] = B[1];
    eB[3] = B[1] & B[0];
    eB[4] = B[2];
    eB[5] = B[2] & B[0];
    eB[6] = B[2] & B[1];
    eB[7] = eB[6] & B[0];
    eB[8] = B[3];
    eB[9] = B[3] & B[0];
    eB[10] = B[3] & B[1];
    eB[11] = eB[10] & B[0];
    eB[12] = B[3] & B[2];
    eB[13] = eB[12] & B[0];
    eB[14] = eB[12] & B[1];
    eB[15] = eB[14] & B[0];

    assign O = is[1] & ~is[2] & ~eB[1] |
        is[2] & ~is[3] & ~eB[2] |
        is[3] & ~is[4] & ~eB[3] |
        is[4] & ~is[5] & ~eB[4] |
        is[5] & ~is[6] & ~eB[5] |
        is[6] & ~is[7] & ~eB[6] |
        is[7] & ~is[8] & ~eB[7] |
        is[8] & ~is[9] & ~eB[8] |
        is[9] & ~is[10] & ~eB[9] |
        is[10] & ~is[11] & ~eB[10] |
        is[11] & ~is[12] & ~eB[11] |
        is[12] & ~is[13] & ~eB[12] |
        is[13] & ~is[14] & ~eB[13] |
        is[14] & ~is[15] & ~eB[14] |
        is[15] & ~eB[15];
endmodule

```

This is not fully golfed yet. I gave the answer in Verilog because this way, I was able to write a program to output each section. If it is mandatory to answer with a diagram, please let me know. They are equivalent. `&` is and, `~` is not, and `|` is or.

My strategy:

* take `A` and put move all the `1`s to the low numbers, store in `is`. (this is the majority of the program)
* take `B` and unpack it into 16 bits (I called it `eB` for expanded `B`)
* do a simple check.

---
Tags: atomic-code-golf, logic-gates
---


# Question
Title: All possible permuations in lexicographical order
Given a string of English alphabet characters, write the shortest code to print all possible permuations in lexicographical order without using any language based library.

```
def function('bca'):
    return all_permutation.

```

This should return :

```
abc,
acb,
bac,
bca,
cab,
cba

```

# Answer
> 1 votes
# Python - ~~131~~ 129 chars

```
def g(a,z):
 if len(a)<1:print(z)
 else:
  for i in range(len(a)):g(a[:i]+a[i+1:],z+a[i])
def f(s):
 a=list(s)
 a.sort()
 g(a,'')

```

Only after coding it I noticed that you wrote both "print" and "return" in the question... my solution prints the permutations, I hope that's alright.

# Answer
> 1 votes
## Python - 83 bytes

```
p=lambda a,*s:sorted(sum([p(a[:i]+a[i+1:],a[i],*s)for i in range(len(a))],[]))or[s]

```

Sample usage:

```
>>> p=lambda a,*s:sorted(sum([p(a[:i]+a[i+1:],a[i],*s)for i in range(len(a))],[]))or[s]
>>> p('abc')
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

```

---

Without the `sorted` call, this narrowly beats out ugoren's answer to the linked question at 75:

```
p=lambda a,*s:sum([p(a[:i]+a[i+1:],a[i],*s)for i in range(len(a))],[])or[s]

```

---
Tags: code-golf
---


title: Mex table generation

text:
# Question
Title: Mex table generation
There is a table (the matrix one, not the one in your kitchen) called the "mex table". It has a left-top cell, at coordinates (0,0), but extends to infinity rightwards and downwards. The x-coordinate increases to the right and the y-coordinate increases downwards.

Every cell has a value \>=0, and the cell at (0,0) has the value 0. The value of any other cell is defined as the **lowest integer, \>=0**, which does not occur directly above it or directly to the left of it.

The start of the mex table looks like this:

```
+---+---+---+---+---+-
| 0 | 1 | 2 | 3 | 4 | ..
+---+---+---+---+---+-
| 1 | 0 | 3 | 2 | 5 | ..
+---+---+---+---+---+-
| 2 | 3 | 0 | 1 | ..
+---+---+---+---+-
| 3 | 2 | 1 | ..
+---+---+---+-
| 4 | 5 | ..
+---+---+-
| : | : | \

```

So, for example, the cell at (2,1) is 3 because 0 occurs left of it, 1 occurs left of it and 2 occurs above the cell. The cell at (3,1) is 2, however, because in the part of the row directly to the left of (3,1) and the part of the column directly above (3,1), 0, 1 and 3 occur, but 2 doesn't.

*Objective:* Print, to standard output, the number in the cell at (x,y) given two integers, both \>=0, on standard input, space-separated and newline-terminated.

*Thunderbirds are GO!*

<sub>(This is derived from a question from the national finals of the Dutch Informatics Olympiad of some time ago.)</sub>

# Answer
> 2 votes
## GolfScript (2 chars)

```
~^

```

This is familiar to anyone who knows anything at all about combinatorial game theory.

# Answer
> 1 votes
## J, 7 characters

```
#.~:/#:

```

Usage:

```
   #.~:/#:3 5
6
   #.~:/#:2 3
1

```

---
Tags: code-golf
---


title: Hiding information in Cats

text:
# Question
Title: Hiding information in Cats
You are a secret agent trying to communicate with your fatherland. Of course the information needs to be hidden so no one eaves drops your message. What would be better suited than a cat? Everyone loves funny pictures of cats <sup>\[citation needed\]</sup>, so they won't suspect secret information hiding in there!

---

Inspired by the algorithm the game Monaco uses to save the level information of shared levels it is your tasks to write a program that encoded information into the least significant bit of the colors of an image.

Encoding format:

* The first 24 bits determine the length of the remaining encoded byte-string in *bits*
* The image is read from left to right and from top to bottom, obviously starting in the upper left pixel
* The channels are read from red to green to blue
* The least significant bit from each channel is read
* Bits are saved in Big Endian order

Rules:

* Your program takes a single byte-string to be encoded and a single image filename for the base image
* The resulting image must be come out as a true color PNG file
* You may use I/O in whatever form you like (ARGV, STDIN, STDOUT, writing / reading from a file), as long as you state how to use your program
* You must choose a random image of a funny cat and encode your program into it to show that your program works
* You may assume that you are only provided valid input, if the amount of bits are not sufficient, the image is not in true color format, the image does not exist or similar problems you may do what you want
* You may assume that the provided image does not contain any alpha channel
* Length is counted in UTF-8 bytes without BOM

You may use this PHP script to test your solution, provide the name of the PNG file as the first command line argument:

```
<?php
if ($argc === 1) die('Provide the filename of the PNG to read from');
$imageSize = @getimagesize($argv[1]);

if ($imageSize === false) die('Not a PNG file');
list($width, $height) = $imageSize;

$image = imagecreatefrompng($argv[1]);
$read = 0;
$bits = '';
for ($y = 0; $y < $height; $y++) {
    for ($x = 0; $x < $width; $x++) {
        $colorAt = imagecolorat($image, $x, $y);
        $red = ($colorAt >> 16) & 0xFF;
        $green = ($colorAt >> 8) & 0xFF;
        $blue = ($colorAt >> 0) & 0xFF;

        $bits .= ($red & 1).($green & 1).($blue & 1);
        $read += 3;
        if ($read == 24) {
            $length = (int) bindec($bits);
            $bits = '';
        }
        else if ($read > 24 && ($read - 24) > $length) {
            $bits = substr($bits, 0, $length);
            break 2;
        }
    }
}
if (strlen($bits) !== $length) die('Not enough bits read to fulfill the length');
$parts = str_split($bits, 8);
foreach ($parts as $part) {
    echo chr(bindec($part));
}

```

# Answer
> 3 votes
## Perl & ImageMagick (Linux), ~~198~~ 190

**Edit:** By some coincidence, earlier I tested on a computer with Q8 (8 bit depth) version of ImageMagick installed. 'Standard' Q16 version requires explicit `-depth 8` on command line. On Linux, `identify` result requires newline to be removed, too. Both factors lead to code size increase, therefore I post Linux (probably Mac too) version as an answer, with fixes applied, and also with some Windows-only stuff removed (cr-lf conversion, binary vs text etc.). Portable (slightly longer) version is posted near the end.

With newlines for readability:

```
$/=$1;
<>=~/\n/;
$_=`identify -format %wx%h $\``;
chop;
open O,"|convert -size $_ -depth 8 rgb: $`.png";
$_=`convert $\` rgb:`;
print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

```

Run:

```
perl cat.pl

```

It reads from STDIN, image file name on first line, 'secret' message follows, terminated with `ctrl-D`. Output file name is original with `.png` appended - not very nice, it's only done for brevity.

Here's an image with some very secret information hidden within:

And with some comments:

```
# Undef input record separator, because we'll slurp input.

$/=$1;

# Read from STDIN, separate first line.
# $` (prematch) contains image file name,
# $' (postmatch) - text to encode.

<>=~/\n/;

# Get IM's 'identify' output, width and height of the image.
# Note: we don't have to separate them, \d+x\d+ string will
# do just fine.

$_=`identify -format %wx%h $\``;
chop;

# Open output pipe - IM's 'convert' command that takes raw RGB data from
# STDIN and writes output to PNG file. Interpolated into this command
# line is previous IM's 'identify' result. Convert wants '-size' command
# option in case of raw RGB input - for obvious reason.

open O,"|convert -size $_ -depth 8 rgb: $`.png";

# Get raw RGB data into $_.

$_=`convert $\` rgb:`;

# Last line does all the job.

# y//\376/cr --- create string same length as $_, fill with 0xFE
# $_&y//\376/cr --- zero least significant bit for all image bytes (1).
# pack(NX,2048*length$') --- multiply by 8 (bytes to bits count) and
#         shift left by 8 (because we'll pack long integer into 3 bytes) -
#         i.e. multiply by 2048.
# unpack('B*',pack(NX,2048*length$').$') ---- append 'secret text' to
#       its encoded length and convert to 'binary' (consisting of 1 and
#       0 characters) string.
# ... &y//\1/cr --- equivalent of tr/01/\0\1/. We don't have to worry
#       that raw RGB length is larger than encoded text length, because
#       '&' truncates longer string argument (2).
# Then bitwise-'or' (1) and (2) strings.

print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

```

Next is portable version, runs on both Windows (use `ctrl-Z` to terminate input) and Linux, byte count is 244.

```
$_=do{local$/;<>};
/\n/;
$_=`identify -format %wx%h $\``;
chomp;
open I,'-|:raw',"convert $` rgb:";
open O,'|-:raw',"convert -size $_ -depth 8 rgb: $`.png";
$_=do{local$/;<I>};
print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

```

# Answer
> 10 votes
## Mathematica, ~~255~~ ~~234~~ 206 bytes

~~I've seen so many `255`s while testing this, I'm unreasonably happy about the size of the code. :)~~ And then my ambition to golf it down even further got the best of me...

```
f=(j=ImageData[Import@#2,t="Byte"];k=(d=IntegerDigits)[j,2,8]~Flatten~2;n=1;(k[[n++,-1]]=#)&/@d[Length@#,2,24]~Join~#&[Join@@d[ToCharacterCode@#,2,8]];ArrayReshape[#~FromDigits~2&/@k,Dimensions@j]~Image~t)&

```

It's technically a function and not a "program", but then again this is pretty much how you write "programs" in Mathematica, if that concept is even valid there. Call it like

```
f["my secret", "fully/qualified/cat.png"]

```

It will return an actual image expression (because that's the most natural way to return an image in Mathematica), so if you want a file, you need to export it:

```
Export["output-cat.png", f["my secret", "input-cat.png"]]

```

Here is the required example:

I'd love to show you the decoded message here, but it doesn't fit... so run it through the OP's decoder. ;)

Btw, I could make it work with UTF-8 secrets for just 7 bytes (change `ToCharacterCode@#` into `#~ToCharacterCode~"utf8"`).

Ungolfed code:

```
f[secret_, filename_] := (
  bits = Join @@ IntegerDigits[ToCharacterCode[secret], 2, 8];
  bits = Join[d[Length @ bits, 2, 24], bits];
  data = ImageData[Import@#2, "Byte"];
  dims = Dimensions@data;
  data = Flatten[IntegerDigits[data, 2, 8], 2];
  m = n = 1;
  While[m <= Length @ bits,
    data[[n++, -1]] = bits[[m++]]
  ];
  Image[ArrayReshape[FromDigits[#, 2] & /@ data, dims], "Byte"]
)

```

# Answer
> 5 votes
# PHP, 530 byte

```
<?php function p($i,$j){return str_pad(decbin($i),$j,0,0);}extract(getopt("i:o:t:"));$t=file_get_contents($t);$_=imagecreatefrompng($i);list($w,$h)=getimagesize($i);$b="";for($i=0;$i<strlen($t);)$b.=p(ord($t[$i++]),8);$l=strlen($b);$b=p($l,24).$b;$l+=24;for($i=$x=$y=0;$y<$h;$y++){for(;$x<$w;){$C=imagecolorat($_,$x,$y);$R=($C>>16)&0xff;$G=($C>>8)&0xff;$B=$C&0xff;$i<$l&&$R=$b[$i++]|$R&~1;$i<$l&&$G=$b[$i++]|$G&~1;$i<$l&&$B=$b[$i++]|$B&~1;imagesetpixel($_,$x++,$y,imagecolorallocate($_,$R,$G,$B));if($i>$l){imagepng($_,$o);die;}}}

```

Run like `php 25443.php -i<input image> -o<output image> -t<file to hide>`.

And here's a sample image.

Ungolfed code is hidden in the sample image. Tested with OP's decoder. Sorry for not funny cat picture.

---
Tags: code-golf, image-processing, steganography
---


title: Set Theory Operations Union Only

text:
# Question
Title: Set Theory Operations Union Only
My obsession with set theory continues. I believe that most programming languages have neither sets as possible structures nor set theory operations such as Union and Intersection. If I am wrong then this question becomes trivial and I learn something new.

It would be fun to ask for the code golf construction of a full set structure where a set could contain any possible structures within the language and operators such as is a member of, is a subset of, union and intersection etc. However that is much too broad. So I will simplify the puzzle.

**Terminology**

An Alphaset has only lower case letters as elements.

The structure for an Alphaset can be defined as you wish and the method used should be explained. It could be just a list of letters read from a file.

As an example I will use an array as a structure for an Alphaset.

An Alphaset can contain a letter once only and order does not matter.

\['a','b','c'\], \['b','c','a'\] and \['c','a','b'\] are equivalent Alphasets.

The operation Union forms an Alphaset from two Alphasets.

\['a','b','c'\] Union \['d','a', 'g', 'b'\] is \['a', 'b', 'c', 'd', 'g'\] or an equivalent.

A Big Alphaset has the same structure as an Alphaset but can contain repeated letters, eg \['a', 'b', 'a', 'c', 'b'\] is a Big Alphaset.

If A and B are any combination of Alphasets and Big Alphasets then A Union B must return an Alphaset.

This gives a way of producing an Alphaset from a Big Alphaset should it ever be necessary for when A is a Big Alphaset the A Union A will be an Alphaset.

**Puzzle**

**Input**

A an Alphaset or Big Alphaset

B an Alphaset or Big Alphaset

**Ouput**

An Alphaset that is the Union of A and B.

**Test Data**

Testing should demonstrate that order of elements within the Alphaset does not matter.

ie the following should all produce equivalent results.

\['a','b','c'\] Union \['a', 'c', 'd'\]

\['b','c','a'\] Union \['c', 'd', 'a'\]

\['c','b','a'\] Union \['d', 'a', 'c'\]

Shortest code wins

# Answer
## Python2 - 21 (or 15) (or 1)

Sets should be in the format `set([element1, element2, element3...])`

```
print input()|input()

```

If running from the interactive prompt is allowed, remove the `print`.

Note: If the Mathematica answer qualifies as being 1 character, then in the Python interactive prompt this should also qualify as 1 character:

```
set(['a','b','d','z'])|set(['c','z','d','a','k','a'])

```

Sample input:

```
set(['a','b','d','z'])
set(['c','z','d','a','k','a'])

```

Sample output:

```
set(['a', 'c', 'b', 'd', 'k', 'z'])

```
> 3 votes

# Answer
# Mathematica, 1 Chars

It's a built-in feature:
> 2 votes

# Answer
# APL - 1 char

is the union operator, so `1 2 3∪3 4 5` returns `1 2 3 4 5`. In APL, there are no brackets around lists.

Other diadic (two-argument) set operators in APL are  (intersection) and `~` (Without):

`1 2 3∩3 4 5` = `3`, `1 2 3 4 5~1 3` = `2 4 5`

Many languages have libraries built especially to deal with sets:

* Haskell - Data.Set
* Java - java.util.Set (an interface implemented by 8+ builtin classes)
* c++ - std::set
* Ecmascript 6 will have a Set object

Almost every language has some sort of way to handle sets. Usually googling "somelanguage set" will point you towards the documentation for that language's set
> 2 votes

# Answer
# Bash + coreutils, 30

Not sure how strictly the input and output formats need to be followed, but this does a union correctly:

```
echo `tr \  "
"<<<$@|sort -u`

```

In action:

```
$ ./union.sh "a b c" "a c d"
a b c d
$ ./union.sh "b c a" "c d a"
a b c d
$ ./union.sh "c b a" "d a c"
a b c d
$

```
> 1 votes

# Answer
# Golfscript, 3 bytes

```
~|p

```

### Example

```
$ echo '["a" "c" "d" "b" "c"] ["f" "b" "e"]'| golfscript alpha.gs
["a" "c" "d" "b" "f" "e"]

```

### How it works

```
~ # Interpret the input string.
| # Setwise OR (union)
p # print

```
> 1 votes

---
Tags: code-golf, math
---


# Question
Title: Text compression and decompression — "Nevermore."
With the recent discussion about the use of compression tools in code golf, I thought it would be a nice challenge to write your own text compressor and decompressor.

### Challenge:

Write **two programs**: one to compress ASCII text into a sequence of bytes, and another to decompress it. The programs need not be in the same language.

The first program should read a piece of ASCII text (from a file or from standard input, or using whatever mechanism is most natural to the language) and output a compressed version of it. (The compressed output may consist or arbitrary bytes; it need not be readable.) The second program should read the output of the first and recreate the original input text.

### Scoring:

The score of a solution will be the **sum** of the following three counts:

1. The **length of the compressor** program in characters.
2. The **length of the output** of the compressor, given the test input below, in bytes.
3. The **length of the decompressor** program (if different from the compressor) in characters.

You should note all three counts and their sum in your answer. Since this is code golf, the lower the score, the better.

### Rules and restrictions:

* You **may not use** any pre-existing compression or decompression tools or libraries, even if they come bundled with your chosen language. If in doubt about whether a given tool or function is allowed, please ask.
* Your compressor program must be capable of handling input consisting of **any printable ASCII text**, including tabs (ASCII 9) and line feeds (ASCII 10). You may, but are not required to, handle arbitrary Unicode and/or binary input.
* Your decompressor program must produce **exactly the same output** as was given to the compressor as input. In particular, take care not to output a trailing line feed if the input did not have one. (The test input below does have a trailing line feed, so you'll need to test for this separately. Tip for GolfScript: `'':n`.)
* Your compressor and decompressor **may be the same program** (with the appropriate mode selected e.g. with a command line switch). In that case, **its length is only counted once**.
* The programs should not be **exceedingly slow or memory-hungry**. If either compressing or decompressing the test input takes more than a minute on my not-so-new desktop (2.2GHz AMD Athlon64 X2) or consumes more than a gigabyte of RAM, I'm going to rule the solution invalid. These limits are deliberately lax — please try not to push them. *(See amendment below: you need to be able to handle at least 100 kB of input within these limits.)*
* Even though only the test input matters for scoring, you should **at least make an effort** at compressing arbitrary input text. A solution that achieves a decent compression ratio *only* for the test input, and for nothing else, is technically valid but isn't going to get an upvote from me.
* Your compressor and decompressor programs **should be self-contained**. In particular, if they depend on being able to read some file or network resource that is not part of your chosen language's standard runtime environment, the length of that file or resource should be counted as part of the length of the program(s). (This is to disallow "compressors" that compare the input to a file on the web and output zero bytes if they match. Sorry, but that's not a new trick anymore.)

### Amendments and clarifications:

* Your compressor must be able to handle files consisting of **at least 100 kB** of typical English text within reasonable time and memory usage (at most one minute and one GB of memory). Your decompressor must be able to decompress the resulting output within the same limits. Of course, being able to handle files longer than that is perfectly fine and commendable. It's OK to split long input files into chunks and compress them individually, or to use other means to trade off compression efficiency for speed for long inputs.
* Your compressor *may* require its input to be given using your preferred platform's **native newline representation** (LF, CR+LF, CR, etc.), as long as your decompressor uses the same newline representation in its output. Of course, it's also fine for the compressor to accept any kind of newlines (or even only Unix newlines regardless of platform), as long as your decompressor then outputs the same kind of newlines as in the original input.

### Test input:

To judge the compression efficiency of the answers, the following test input (*The Raven* by Edgar Allan Poe, courtesy of Project Gutenberg) will be used:

```
Once upon a midnight dreary, while I pondered, weak and weary,
Over many a quaint and curious volume of forgotten lore,
While I nodded, nearly napping, suddenly there came a tapping,
As of some one gently rapping, rapping at my chamber door.
"'T is some visiter," I muttered, "tapping at my chamber door--
                                          Only this, and nothing more."

Ah, distinctly I remember it was in the bleak December,
And each separate dying ember wrought its ghost upon the floor.
Eagerly I wished the morrow:--vainly I had sought to borrow
From my books surcease of sorrow--sorrow for the lost Lenore--
For the rare and radiant maiden whom the angels name Lenore--
                                          Nameless here for evermore.

And the silken sad uncertain rustling of each purple curtain
Thrilled me--filled me with fantastic terrors never felt before;
So that now, to still the beating of my heart, I stood repeating
"'T is some visiter entreating entrance at my chamber door
Some late visiter entreating entrance at my chamber door;--
                                          This it is, and nothing more."

Presently my soul grew stronger; hesitating then no longer,
"Sir," said I, "or Madam, truly your forgiveness I implore;
But the fact is I was napping, and so gently you came rapping,
And so faintly you came tapping, tapping at my chamber door,
That I scarce was sure I heard you"--here I opened wide the door;--
                                          Darkness there, and nothing more.

Deep into that darkness peering, long I stood there wondering, fearing,
Doubting, dreaming dreams no mortal ever dared to dream before;
But the silence was unbroken, and the darkness gave no token,
And the only word there spoken was the whispered word, "Lenore!"
This I whispered, and an echo murmured back the word, "Lenore!"
                                          Merely this and nothing more.

Back into the chamber turning, all my soul within me burning,
Soon again I heard a tapping, somewhat louder than before.
"Surely," said I, "surely that is something at my window lattice;
Let me see, then, what thereat is, and this mystery explore--
Let my heart be still a moment and this mystery explore;--
                                          'T is the wind and nothing more!"

Open here I flung the shutter, when, with many a flirt and flutter,
In there stepped a stately Raven of the saintly days of yore.
Not the least obeisance made he; not a minute stopped or stayed he;
But, with mien of lord or lady, perched above my chamber door--
Perched upon a bust of Pallas just above my chamber door--
                                          Perched, and sat, and nothing more.

Then this ebony bird beguiling my sad fancy into smiling,
By the grave and stern decorum of the countenance it wore,
"Though thy crest be shorn and shaven, thou," I said, "art sure no craven,
Ghastly grim and ancient Raven wandering from the Nightly shore,--
Tell me what thy lordly name is on the Night's Plutonian shore!"
                                          Quoth the Raven, "Nevermore."

Much I marvelled this ungainly fowl to hear discourse so plainly,
Though its answer little meaning--little relevancy bore;
For we cannot help agreeing that no living human being
Ever yet was blessed with seeing bird above his chamber door--
Bird or beast upon the sculptured bust above his chamber door,
                                          With such name as "Nevermore."

But the Raven, sitting lonely on the placid bust, spoke only
That one word, as if his soul in that one word he did outpour.
Nothing further then he uttered--not a feather then he fluttered--
Till I scarcely more than muttered, "Other friends have flown before--
On the morrow _he_ will leave me, as my hopes have flown before."
                                          Then the bird said, "Nevermore."

Startled at the stillness broken by reply so aptly spoken,
"Doubtless," said I, "what it utters is its only stock and store,
Caught from some unhappy master whom unmerciful Disaster
Followed fast and followed faster till his songs one burden bore--
Till the dirges of his Hope that melancholy burden bore
                                          Of 'Never--nevermore.'"

But the Raven still beguiling all my sad soul into smiling,
Straight I wheeled a cushioned seat in front of bird and bust and door;
Then, upon the velvet sinking, I betook myself to linking
Fancy unto fancy, thinking what this ominous bird of yore--
What this grim, ungainly, ghastly, gaunt and ominous bird of yore
                                          Meant in croaking "Nevermore."

This I sat engaged in guessing, but no syllable expressing
To the fowl whose fiery eyes now burned into my bosom's core;
This and more I sat divining, with my head at ease reclining
On the cushion's velvet lining that the lamplight gloated o'er,
But whose velvet violet lining with the lamplight gloating o'er
                                          _She_ shall press, ah, nevermore!

Then, methought, the air grew denser, perfumed from an unseen censer
Swung by seraphim whose foot-falls tinkled on the tufted floor.
"Wretch," I cried, "thy God hath lent thee--by these angels he hath sent thee
Respite--respite and nepenthe from thy memories of Lenore!
Quaff, oh quaff this kind nepenthe, and forget this lost Lenore!"
                                          Quoth the Raven, "Nevermore."

"Prophet!" said I, "thing of evil!--prophet still, if bird or devil!--
Whether Tempter sent, or whether tempest tossed thee here ashore,
Desolate yet all undaunted, on this desert land enchanted--
On this home by Horror haunted--tell me truly, I implore--
Is there--_is_ there balm in Gilead?--tell me--tell me, I implore!"
                                          Quoth the Raven, "Nevermore."

"Prophet!" said I, "thing of evil--prophet still, if bird or devil!
By that Heaven that bends above, us--by that God we both adore--
Tell this soul with sorrow laden if, within the distant Aidenn,
It shall clasp a sainted maiden whom the angels name Lenore--
Clasp a rare and radiant maiden whom the angels name Lenore."
                                          Quoth the Raven, "Nevermore."

"Be that word our sign of parting, bird or fiend!" I shrieked, upstarting--
"Get thee back into the tempest and the Night's Plutonian shore!
Leave no black plume as a token of that lie thy soul hath spoken!
Leave my loneliness unbroken!--quit the bust above my door!
Take thy beak from out my heart, and take thy form from off my door!"
                                          Quoth the Raven, "Nevermore."

And the Raven, never flitting, still is sitting, still is sitting
On the pallid bust of Pallas just above my chamber door;
And his eyes have all the seeming of a demon's that is dreaming,
And the lamplight o'er him streaming throws his shadow on the floor;
And my soul from out that shadow that lies floating on the floor
                                          Shall be lifted--nevermore!

```

The correct test input (encoded with Unix-style LF newlines) should be 7043 bytes long, and have the hexadecimal MD5 hash `286206abbb7eca7b1ab69ea4b81da227`. (`md5sum -t` should produce the same hash value even if you use CR+LF newlines on DOS/Windows.) The output of your decompressor should have the same length and hash.

Ps. Keep in mind that this challenge is only as hard as you make it. Really, anything under 7043 counts as a good score. (At the other end of the scale, I'll be *extremely* impressed if anyone achieves a score under 2500.)

# Answer
> 19 votes
## Perl, 3502 = 133 + 3269 + 100

The encoder:

```
#!/usr/bin/perl -0
$_=<>;for$e(map{~chr}0..255){++$p{$_}for/..|.\G./gs;
%p=$s=(sort{$p{$a}<=>$p{$b}}keys%p)[-1];$d.=/\Q$e/?$/:s/\Q$s/$e/g&&$s}print$_,$d

```

And the decoder:

```
#!/usr/bin/perl -0777
sub d{($p=$d{$_})?d(@$p):print for@_}
sub r{%d=map{chr,ord($c=pop)&&[pop,$c]}0..255;&d}r<>=~/./gs

```

For purists who prefer to avoid using command-line switches: You can remove the shebang line and add `$/=chr;` to the encoder and `$/=$,;` to the decoder to get the same effect. (This would bring the score up to 3510.)

This code uses a very primitive compression scheme:

* Find the two-char bigram that appears most frequently in the source text.
* Replace the bigram with a currently-unused byte value.
* Repeat until there are no more repeated bigrams (or no more unused byte values).

Someone out there may recognize this as a simplified version of "re-pair" compression (short for recursive pairs).

It's not a very good general compression scheme. It only does well with things like ASCII text, where there are a lot of unused byte values, and even then it typically gets no more than a 45-50% ratio. However, it has the advantage of being implementable with a minimum of code. The decompressor in particular can be *quite* compact. (Most of the chars in my decoder script are for retrieving the bigram dictionary.)

Here's an ungolfed version of the code:

```
#!/usr/bin/perl
use strict;
use warnings;
# Run with -d to decode.
if ($ARGV[0] eq "-d") {
    shift;
    $_ = join "", <>;
    my @in = split //;
    my %dict;
    foreach my $n (0 .. 255) {
        my $c = shift @in;
        $dict{chr $n} = [ $c, shift @in ] if ord $c;
    }
    sub decode {
        foreach (@_) {
            if ($dict{$_}) {
                decode(@{$dict{$_}});
            } else {
                print $_;
            }
        }
    }
    decode @in;
} else {
    $_ = join "", <>;
    my @dict;
    for (my $n = 255 ; $n >= 0 ; --$n) {
        my $symbol = chr $n;
        if (!/\Q$symbol/) {
            my %pop;
            ++$pop{$_} for /../gs, /(?!^)../gs;
            my $str = (sort { $pop{$b} <=> $pop{$a} } keys %pop)[0];
            s/\Q$str/$symbol/g;
            $dict[$n] = $str;
        }
    }
    for (0..255) { $dict[$_] ||= "\0" }
    print @dict, $_;
}

```

One expression in the golfed encoder requires explanation, I think, and that is `(sort{$p{$a}<=>$p{$b}}keys%p)[-1]`, to get the key with the highest value. That looks like it should be written as `(sort{$p{$b}<=>$p{$a}}keys%p)[0]`, which does the same thing and is one character shorter. The reason I didn't write it that way is that it alters the selected key in the case when there are multiple keys with the highest value. By sheer chance, this caused the resulting output for the test input to be 10 bytes longer. I hated to take on the useless extra character, but not enough to sacrifice 9 points from my score.

**In your face, Golfscript!** (Haha, Golfscript would totally come over here and kick my ass if it could hear me.)

# Answer
> 20 votes
## Python, 3514 = 294 + 2894 + 326

Basically a bzip2 implementation. It does a Burrows-Wheeler transform, a move-to-front transform, a simple Huffman encoding into a bit stream, converts that bit stream to an integer and writes out bytes.

Encoder:

```
import sys
S=range(128)
H={0:'0'}
for b in range(7):
 for i in range(1<<b,2<<b):H[i]='1'*b+'10'+bin(i)[3:]
I=sys.stdin.read()+'\0'
N='1'
for x in sorted(I[i:]+I[:i]for i in range(len(I))):i=S.index(ord(x[-1]));N+=H[i];S=[S[i]]+S[:i]+S[i+1:]
N=int(N,2)
while N:sys.stdout.write(chr(N%256));N>>=8

```

`S` is the move-to-front queue, `H` is the Huffman encoder, and `N` is the bitstream.

The encoding reduces the test input to about 41% of its original size.

Decoder:

```
import sys
N=0
b=1
for c in sys.stdin.read():N+=ord(c)*b;b<<=8
N=bin(N)[3:]
S=range(128)
L=''
while N:
 n=N.find('0')
 if n:i=2**n/2+int('0'+N[n+1:2*n],2);N=N[2*n:]
 else:i=0;N=N[1:]
 L+=chr(S[i]);S=[S[i]]+S[:i]+S[i+1:]
S=''
i=L.find('\0')
for j in L:S=L[i]+S;i=L[:i].count(L[i])+sum(c<L[i]for c in L)
sys.stdout.write(S[:-1])

```

# Answer
> 8 votes
**8086 Assembler / MS\_DOS**

Compressor: 155

```
jNiAxBCO2I7AM/+9/QW5AAGK2TPAq4rDqv7D4va6AQkz9lK0BrL/zSFadDK7
/f+DwwM733QNOTd19ThHAnXwid7r34k1iEUC6BMAtACKRQJr8AODxwPryrQC
zSHrxFIz0ovGuwMA9/Nai9iKztPL0ePQ0nMWgPr+cgtSsv60Bs0hWoDq/rQG
zSGyAf7JdeA5/XUHA+2DxQP+xsM=

```

Data: 3506

Decompressor: 203

```
ieWD7CCM2IDEEI7YjsAz/7kAAYrZM8CrisOq/sPi9rYJxkb0Abn9BehtAIl2
/uhTAOhkAIl28Dv3cy3oRgCLRv6JBYt28Il2/oM8AHQEizTr94pEAohFAoPH
AznPddL+xgPJg8ED68mLdv6JNYM8AHQEizTr94pEAohFAol+/on+aFgBgzwA
dAdWizTo9f9etAaKVALNIcMz9ojz/k70dRu0BrL/zSF0IDz+cgi0BrL/zSEE
/sZG9AiIRvLQZvLR1v7Ldddr9gPDzSA=

```

Total: 3864

Use this Base64 decoder and save the binary files as 'compress.com' and 'decompress.com' and then do:

```
compress < source > compressed_file
decompress < compressed_file > copy_of_source

```

in a DOS shell (tested with WinXP). There's no error checking so compressing big files will create incorrect results. A few small additions and it could cope with any sized file. Also, it can't decompress to binary as it can't output a 0xff value (the compressed data escapes the 0xff value as 0xfe 0xff with 0xfe escaped as 0xfe 0xfe). Using command line filenames would overcome the binary output problem, but would be a bigger executable.

# Answer
> 7 votes
# Bash Poem (566+117) + 4687 = 5370

For fun I have disguised a compressor as a poem:

```
for I in my chamber nodded, nearly napping, suddenly heard rapping, tapping upon my door    \
"'T is some visiter" \ I\  muttered, o\'er lamplight "nothing more" \
just this sainted maiden whom the angels name Lenore    \
And "Prophet!" said me "thing of evil" -- "prophet still, if bird or devil!"    \
Leave no token of that lie thy soul hath spoken and sitting take thy ore from This floor    \
But you velvet bird from some shore above   \
here this with sad raven before his word still spoke nothing    \
"                                          " Quoth the Raven Never more;                    do C=$[C+1];E=`perl -e "print chr($C+128)"`;echo "s/$I/$E/g">>c;echo "s/$E/$I/g">>d;done;LANG=C sed -f $1;rm c d

```

This is a unified compressor: run with the option "c" it will compress, and with "d" it will decompress. It has two parts: a 566 byte "readers digest" version of the poem and (2) a 117 byte suffix where all the "real" bash is done.

With some care (e.g. starting the poem with "for I in") bash will interpret the "lossy" version of poem as an array. It replaces each element of the array with a non-ASCII character (we assume the input is ASCII so there are no collisions). One minor advantage of this solution: since we make use of the fact that we can assume the input is ASCII, the output of this compression will never be longer than its input, regardless of what the input and/or lossy part is.

The rule that this comes closest to violating is the rule about providing a decent compression ratio on other texts. However, It shaves 1386 bytes off the GPL V2 text, well over it's own size, which seems to match the OPs definition of `decent`. Thus it seems to provide so-called `decent` compression on general texts. This is because pretty much any English text will have "the" "that" etc. Clearly it will work better if you replace the "lossy" part with text resembling the original you want to losslessly compress.

Splitting pictures and audio into lossy and non-lossy parts is a known technique. This doesn't work as well for text: 4687 bytes isn't that great even if we exclude the 566 bytes from the lossy version and we can't really automatically generate a lossy version of text the same we can for audio. On the plus side this means every time you compress something with this compressor, you can have the fun of creating a lossy version by hand. So this seems like a reasonable "for fun" solution.

# Answer
> 6 votes
# C++, 4134 bytes (code = 1357, compressed = 2777)

This does a Burrows-Wheeler transform + a Move-To-Front like Keith Randall's, but then compresses the resulting byte sequence using an adaptive Range Coder. Unfortunately, the improved compression from the range coder isn't enough to offset C++'s verbosity. I could golf this code some more, namely use a different input/output method, but it wouldn't be enough to beat the other submissions with the current algorithm. The code is Windows specific, and only ascii text is supported.
To compress: "C text\_file compressed\_file"
To decompress: "D compressed\_file uncompressed\_file"
Pretty much any command line error or file error will crash the program, and it takes the better part of a minute to encode or decode the poem.

```
#include <windows.h>
#include <algorithm>
typedef DWORD I;typedef BYTE u;
#define W while
#define A(x)for(a=0;a<x;a++)
#define P(x)*o++=x;
I q,T=1<<31,B=T>>8,a,l,f[257],b,G=127,p=G,N=255;I Y(u*i,u*j){return
memcmp(i,j,l)<0;}I E(u*i,u*o){b=0;I L=0,h=0,R=T;u*c=o,*e=i+l;W(i<e){I
r=R/p,s=0;A(*i)s+=f[a];s*=r;L+=s;R=*i<N?r*f[*i++]++:R-s;p++;W(R<=B){if((L>>23)<N){for(;h;h--)P(N)P(L>>23)}else{if(L&T){o[-1]++;for(;h;h--)P(0)P(L>>23)}else
h++;}R<<=8;L<<=8;L&=T-1;}}P(L>>23)P(L>>15)P(L>>7)return
o-c;}void D(u*i,u*o){I R=128,L=*i>>1;u*e=o+l;W(o<e){W(R<=B){L<<=8;L|=((*i<<7)|(i++[1]>>1))&N;R<<=8;}I
h=R/p,m=L/h,x=0,v=0;W(v<=m)v+=f[x++];P(--x);L-=h*(v-f[x]);R=h*f[x]++;p++;}}void
main(I Z,char**v){u d[1<<16];I c=*v[1]<68,s;HANDLE F=CreateFileA(v[2],T,0,0,3,0,0),o=CreateFileA(v[3],T/2,0,0,2,0,0);ReadFile(F,d,GetFileSize(F,0),&l,0);l=c?l:*(I*)d;A(G)f[a]=1;u M[256];A(G)M[a]=a+1;u*g=new u[l*3],*h=g+l;if(c){memcpy(d+l,d,l);u**R=new
u*[l];A(l)R[a]=d+a;std::sort(R,R+l,Y);A(l){b=R[a][l-1];I
i=strchr((char*)M,b)-(char*)M;memmove(M+1,M,i);*M=g[a]=b;h[a]=i;}s=E(h,d+l+8);}else{D(d+8,g);A(l){I
k=g[a];g[a]=M[k];memmove(M+1,M,k);*M=g[a];}}u**j=new u*[l];A(l)j[a]=new
u[l*2],memset(j[a],0,l*2),j[a]+=l;A(l){for(b=0;b<l;)*--j[b]=g[b++];std::sort(j,j+l,Y);}if(c){A(l){if(!memcmp(j[a],d,l)){I*t=(I*)(d+l);*t=l;t[1]=a;g=d+l,l=s+8;}}}else
g=j[*(I*)(d+4)];WriteFile(o,g,l,&q,0);}

```

# Answer
> 5 votes
## JavaScript, 393 (code) + 3521 (test) = 3914 (total)

This program iteratively substitutes unused byte values for 2- to 4- character chunks of the input. Each substitution is scored based on the original chunk's frequency and length, and the best substitution is chosen each time around. I would add a final Huffman coding stage if I could figure out how to do it in a relatively small number of characters. Decompression is essentially a series of find-and-replace operations.

### Usage

C() provides compression; U() provides decompression. As JavaScript's strings are based on 16-bit Unicode code units, only the least significant 8 bits of each code unit are used in the compressed data format; this is compatible with Firefox's btoa() and atob() functions for Base64 encoding. (usage example)

This program may only work in Firefox because of a non-standard "g" option to .replace().

### Code

Golfed code:

```
S=String.fromCharCode;function C(c){h=[];for(f=0;129>f;++f){g='';i=0;for(e=2;5>e;++e){d={};for(a=0;a<=c.length-e;a+=e)b="K"+c.substr(a,e),d[b]=d[b]?d[b]+1:1;for(b in d)a=d[b],a=a*e-(1+e+a),a>i&&(g=b.slice(1),i=a)}if(!g)break;h[f]=g;c=c.replace(g,S(127+f),"g")}return h.join("\1")+"\1"+c}function U(a){c=a.split("\1");a=c.pop();for(b=c.length,d=127+b;b--;)a=a.replace(S(--d),c[b],"g");return a}

```

Before golfing:

```
function compress(str) {

    var hash, offset, match, iteration, expansions, bestMatch, bestScore, times, length, score;

    expansions = [];

    for (iteration = 0; iteration < 129; ++iteration) {

        bestMatch = null;
        bestScore = 0;

        for (length = 2; length < 5; ++length) {

            hash = {};

            for (offset = 0; offset <= str.length - length; offset += length) {
                match = 'K' + str.substr(offset, length);
                hash[match] = hash[match] ? hash[match] + 1 : 1;
            }

            for (match in hash) {
                times = hash[match];
                score = times * length - (1 + length + times);
                if (score > bestScore) {
                    bestMatch = match.slice(1);
                    bestScore = score;
                }
            }

        }

        if (!bestMatch) {
            break;
        }

        expansions[iteration] = bestMatch;
        str = str.replace(bestMatch, String.fromCharCode(127 + iteration), 'g');

    }

    return expansions.join('\u0001') + '\u0001' + str;
}

function uncompress(str) {
    var i, j, expansions;

    expansions = str.split('\u0001');
    str = expansions.pop();

    for (j = expansions.length, i = 127 + j; j--;) {
        str = str.replace(String.fromCharCode(--i), expansions[j], 'g');
    }

    return str;
}

```

# Answer
> 3 votes
## PHP, (347 + 6166 + 176) = 6689

So I went with a simplistic dictionary + substitution approach.

If a word appears multiple times and it's shorter to (encode the word + save the substitution entry) then it makes the replacement. If the "word" happens to be a number, it does it anyways to prevent accidental substitutions during decompression. The "dictionary" of substitutions is joined by null bytes, followed by two null bytes, followed by the body the substitution works on.

**Possible improvements:**

* Windows doesn't like piping more than 4kb of data around, so find a better way than using files.
* The ability to match long strings of whitespace and count them as "words" without adding too much code.
* Coming up with something better substitutions instead of using numbers.

**Usage:** the compressor looks for a file called "i" and writes the compressed data to "o". The decompressor looks for "o" and writes the uncompressed data to "d". This is my shoddy workaround to Windows not liking to pipe boats of data around.

---

**compress.php (347)**

```
<?$d=file_get_contents('i');$z=chr(0);preg_match_all('|\b(\w+)\b|',$d,$m);$n=0;foreach($m[0]as$w){$l=strlen($w);$q[$w]=isset($q[$w])?$q[$w]+$l:$l;}arsort($q);foreach($q as$w=>$s){$l=strlen($w);$c=$s/$l;if($c*strlen($n)+$l<$s||is_int($w)){$d=preg_replace('|\b'.preg_quote($w).'\b|',$n++,$d);$f[]=$w;}}file_put_contents('o',implode($z,$f).$z.$z.$d);

```

Expanded version with comments and explanation.

---

Output sample without dictionary. Kinda funny to look at.
Normal size: **6166**.

```
Ah, distinctly I remember it 45 in 0 bleak December,
25 each separate dying ember wrought its ghost 39 0 37.
Eagerly I wished 0 88:--vainly I had sought to borrow
From 9 books surcease of 43--43 for 0 lost 8--
For 0 rare 1 67 40 54 0 26 38 8--
                                          Nameless 63 for evermore.

25 0 silken sad uncertain rustling of each purple curtain
Thrilled me--filled me 19 fantastic terrors never felt 17;
So 4 now, to 13 0 beating of 9 64, I stood repeating
"'T is 57 31 36 49 at 9 2 5
Some late 31 36 49 at 9 2 5;--
                                          58 it is, 1 10 16."

```

---

**decompress.php (176)**

```
<?$z=chr(0);$d=file_get_contents('o');list($w,$d)=explode($z.$z,$d);$w=explode($z,$w);$n=0;foreach($w as$r){$d=preg_replace('|\b'.$n++.'\b|',$r,$d);};file_put_contents('d',$d);

```

Expanded version with explanation.

---

Any suggestions for improvement welcome.

**Edit:** Added the "unrolled" versions of the code and added tons of comments. Should be easy to follow.

# Answer
> 3 votes
## GolfScript, 3647 (compressed size 3408 + code size 239)

```
128,{[.;]''+}%:d;8:k;{2k?={1k+:k;}*}:|;{2base}:b;{.[0]*@b+0@->}:$;.0=
{'':&,:i;1/{.d&@+?.0<{;d,i@d&@:&.0=:i;[+]+:d;k$\|}{:i;&\+:&;}if}%[0]k*+[]*8/{b}%"\0"\+}
{1>{8$}/][]*:^;{^k<b^k>:^;}:r~{.}{d,|d=:&r..d,<{d=}{;&}if[1<&\+]d\+:d;}while;}if

```

The algorithm used is LZW compression with variable-width codes. The first line is shared code, the second is the compression code and the third is the decompression code.

It handles files with ASCII characters in the range 1-127, and it recognizes compressed files automatically (they start with a 0 byte), so there are no parameters required to decompress.

**Example run:**

```
$ md5sum raven.txt
286206abbb7eca7b1ab69ea4b81da227  raven.txt
$ ruby golfscript.rb compress.gs < raven.txt > raven.lzw
$ ls -l raven.lzw
-rw-r--r-- 1 ahammar ahammar 3408 2012-01-27 22:27 raven.lzw
$ ruby golfscript.rb compress.gs < raven.lzw | md5sum
286206abbb7eca7b1ab69ea4b81da227  -

```

**Note:** I started on this long before the requirement to handle 100kb was added, so I haven't tested it on input of that size. However, it takes about 30 seconds to compress the test input and 5 seconds to decompress it, using about 20MB of memory at its peak.

# Answer
> 3 votes
# Haskell, 3973

Late to the party, and not going to win, but I had fun writing it so I might as well post it.

It's a straightforward variable-width implementation of LZW, with a dictionary explicitely limited to printable ASCII, tab and linefeed. Run with no arguments, it compresses standard input to file `C`. Run with any argument (but "--decompress" would be a reasonable bet), it decompresses file `C` to standard output.

```
import List
import System
import Data.Binary
q=head
main=getArgs>>=m
m[]=getContents>>=encodeFile"C".s 97 128 1 0.e 97h
m _=decodeFile"C">>=putStr.d tail""96h.u 97 128
h=zip[0..].map(:[])$"\t\n"++[' '..'~']
e _ _[]=[]
e n s y=c:e(n+1)((n,take(1+l)y):s)(drop(l)y)where{Just(c,p)=find((`isPrefixOf`y).snd)s;l=length p}
d _ _ _ _[]=""
d f p n s(x:y)=t++d id t(n+1)(f$(n,p++[q t]):s)y where t=maybe(p++[q p])id$lookup x s
s _ _ _ a[]=a::Integer
s n w o a y|n>w=s n(2*w)o a y|0<1=s(n+1)w(o*w)(a+o*q y)(tail y)
u _ _ 0=[]
u n w x|n>w=u n(2*w)x|0<1=(x`mod`w::Integer):u(n+1)w(x`div`w)

```
* code size: 578
* compressed sample size: 3395

---
Tags: code-golf, compression, restricted-time, restricted-memory
---


title: Let us make a quine maker!

text:
# Question
Title: Let us make a quine maker!
You are to create a program, that, given another program, and a position, will make it a quine. Namely, it needs to insert an expression at that point that evaluates to a string that is the programs input. For example:

```
main=do
    putStrLn "Welcome to the open source program, would you like my source code?"
    (ans:_) <- getLine
    case ans of
        'y' -> putStrLn  --Quine goes here
        'n' -> putStrLn "Okay, Good bye"
        _  -> putStrLn "Unrecongnized command. Try again." >> main

```

Now if I told it to put the source code at (5,24) the result would be.

```
main=do
    putStrLn "Welcome to the open source program, would you like my source code?"
    (ans:_) <- getLine
    case ans of
        'y' -> putStrLn ((\a b->a++(show a)++" "++(show b)++b) "main=do\n    putStrLn \"Welcome to the open source program, would you like my source code?\"\n    (ans:_) <- getLine\n    case ans of\n        'y' -> putStrLn ((\\a b->a++(show a)++\" \"++(show b)++b) " ")--Quine goes here\n        'n' -> putStrLn \"Okay, Good bye\"\n        _  -> putStrLn \"Unrecongnized command. Try again.\" >> main\n")--Quine goes here
        'n' -> putStrLn "Okay, Good bye"
        _  -> putStrLn "Unrecongnized command. Try again." >> main

```

Clarifications:

* The program you make and the type of programs it act upon may be different if you like.
* Your program may get the position in the program and its source code however it sees fit. You may put the new source code where ever you see fit.
* Obviously, the new program can't simply grab its source code from its file
* You may only insert things at the position the user specifies (so you may not be able to include any new modules in the new program depending on target language)

This is code golf, so shortest answer wins! Let us see how many different languages we can make quine makers for as well.

# Answer
# J - 73 char

Takes input on stdin, as the 0-origin index in characters and the source, separated by a newline. Introduces a copy of the program at the specified point as a string.

```
((".@{.~({.,}.,~'(',')',~(LF;''',LF,''')rplc~quote@])(}.~>:))i.&LF)1!:1]3

```

Explained by explosion:

```
(                                  )1!:1]3  NB. stdin
 (                           )i.&LF         NB. find the first newline
     {.~                                    NB. the index part of input
  ".@                                       NB. convert index to integer
                      (}.~>:)               NB. the source program part
        ({.,}.,~     )                      NB. program before and after index
                ...@]                       NB. program quoted properly

```

For example, given input

```
3
abcdef'ghij'
kl mn 0p1

```

the output is

```
abc('abcdef''ghij''',LF,'kl mn 0p1')def'ghij'
kl mn 0p1

```

because J uses Pascal-style strings: `'Isn''t this great?'`
> 3 votes

# Answer
## Haskell (390 Char)

```
import System.Environment
import Data.List
main = do
    [p] <- getArgs
    interact $ q (read p)
q :: (Int, Int) -> String -> String
q p j=case d p j of
    (f, s) -> b (f++i) (')':s)
d (l,c) j=case splitAt (l-1) (lines j) of
    (f, (t:s)) -> case splitAt c t of
        (r,y) -> ((unlines f)++r, y++"\n"++(unlines s))
b=(\a b->a++(show a)++" "++(show b)++b)
i="((\\a b->a++(show a)++\" \"++(show b)++b) "

```

Not very golfed. Just an example. This takes the position as a command line argument and source code as a standard input and puts the new source code as standard output.
> 1 votes

---
Tags: code-golf, quine
---