text:
DNA Encode a String
Challenge
You must write an encoder (and a separate decoder) which takes a string as input and outputs the string encoded in the style of a strand of DNA.
DNA
DNA is made up of four types of nucleotide:

Adenine (A)
Thymine (T)
Cytosine (C)
Guanine (G)

Adenine and thymine pair up together to make AT or TA. Similarly, cytosine and guanine pair up together to make CG or GC.
Let's call these pairs units. This means that your encoded string is only allowed to contain the four units AT, TA, CG and GC.
This means that:
ATTAGACG

Would be invalid because it contains the unit GA, which is impossible.
Similarly,
TAGCGCCGATA

Is invalid because the final A does not have a thymine to pair up with.
Example
You must encode the following example text and use its encoded length as part of your score:

I have a friend who's an artist and has sometimes taken a view which I don't agree with very well. He'll hold up a flower and say "look how beautiful it is," and I'll agree. Then he says "I as an artist can see how beautiful this is but you as a scientist take this all apart and it becomes a dull thing," and I think that he's kind of nutty. First of all, the beauty that he sees is available to other people and to me too, I believe. Although I may not be quite as refined aesthetically as he is ... I can appreciate the beauty of a flower. At the same time, I see much more about the flower than he sees. I could imagine the cells in there, the complicated actions inside, which also have a beauty. I mean it's not just beauty at this dimension, at one centimeter; there's also beauty at smaller dimensions, the inner structure, also the processes. The fact that the colors in the flower evolved in order to attract insects to pollinate it is interesting; it means that insects can see the color. It adds a question: does this aesthetic sense also exist in the lower forms? Why is it aesthetic? All kinds of interesting questions which the science knowledge only adds to the excitement, the mystery and the awe of a flower. It only adds. I don't understand how it subtracts.

Bounty
If you answer this challenge in the language DNA#, I will offer a 100 to 200 rep bounty.
Rules
Your encoder and decoder programs must work for any string supplied. Therefore, your encoder must produce a genuine encoding and your decoder should not simply hardcode the example text.
You must support all printable ASCII characters:
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

If you can support more characters, that is acceptable.
Scoring
Your score is how long in characters (not units) the encoded version of the above text plus the length in bytes of your decoder and your encoder.
Winning
The program with the lowest score wins.

Why is the encoder not included in the byte-count?

@LeakyNun I don't know, I guess I didn't think about both of them. It's been included now

Any valid program in Brainfuck is an equivalent valid program in DNA#.

@LeakyNun I know but I still want to see it in DNA#

Are only alpha numeric, dot, space coma and quote valid or any printable ascii character allowed in the input?

If you're including the encoder in the score then you should remove the tag [tag:kolmogorov-complexity]

@PeterTaylor Oh, okay

What's the maximum input length?

@Mast There isn't a maximum  As long as your program will handle

any source for DNA# interpreter? the linked one on esolang seems to be broken for me

@Aaron Not that I know of, but I'll have a look around

@βετѧΛєҫαγ: This challenge gives me an idea for another DNA-related one (namely, restriction mapping)! Unmodified, it would probably be too complicated for a classical code golf task, however.

May the encoder and the decoder have some code in common? Or are they supposed to be separate standalone modules?

@Arnauld They have to be completely standalone

I'm working on a simple python interpreter for DNA#, although I've decided to make one small alteration to the language.. where's the best place to post the script?

@Aaron Anywhere really. Github, Pastebin...

Pyth, 5152 + 21 + 23 = 5196 bytes
Encoder
sm@c4s_B"ATCG"djC.ZQ4

Try it here
Decoder
.ZCimxc4s_B"ATCG"dcQ2 4

Try it here (Input too long to link, put output of first in quotes in the input box)
Compresses the input and converts it from base 256 into an integer. Then converts into a sequence of base 4 numbers and chooses from ['AT', 'CG', 'GC', 'TA']

@βετѧΛєҫαγ I'm not sure why I didn't originally

@LuisMendo added some form of explanation

Thanks. The part "Compresses the input" was what I was missing

Without compressing the score would be about twice as big

DNA# : 10216 + 852 + 384 = 11452 bytes
This is not exactly tested, as I haven't gotten a hold of a working interpreter... There are probably mistakes
I use a simple brute force approach so far where each character is read in, then broken up into 2 bit blocks with AT = 00; TA = 01; CG = 10; GC = 11. The sample text is 1277 ASCII characters, and it takes 4 codes (2 bits) to encode each 8 bit char: 1277 * 4 * 2 = 10216 bytes
 Encoder
852 bytes - line form
GCGCGCTAATATATTAATTAATTAATTAATTAATTAATTAATTATACGCGCGATATTAATATGCATGCCGCGGCTACGATATGCCGCGATATATTAATTAATTAATTAATTAATTAATTAATTATACGCGCGATTAATATATTAATTAATTAATTAATTAATTAATTAATTAATTATACGCGCGATTAATTAATTAATGCATGCGCTAATATATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATATATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATGCATGCATCGGCCGGCTAATATATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATCGATATATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATGCATGCATCGGCCGGCTAATATATTAATTAATTAATTAATATATCGATCGATCGATCGATGCATGCATCGGCCGATATGCATATATGCATATGCATGCATGCATCGGCTAATTAATATTAATATGCATGCCGCGCGATATGCCGCGTACGATGCCGCGATGCATGCTATAATATATATCGCGATATATATGCTAATCGGCCGATTAATTAATTAATTAATGCCGATATATCGCGATATTAATATGCATGCCGCGATATGCTAATCGGCCGATATGCTAATCGGCCGGCCGATGCATGCGCCGATGCATGCGCGCGCCG

224 bytes - symbol form:
,[>++++++++*=X>:=<<X[/=<X>++++++++*=X+>+++++++++*=X+++<<[>+++++++++++++++++++>-------------------<<-][>----------------->+++++++++++++++++<<-][>++++>----<<-]>.>.<<<-[+>:=<<X/=<X*=<X<<-=>>X>>[-]++++</=>X>:=<<X>[-]>[-]]<<]<<,]

and with variable names and some messy comments...
DNA# dna encoder

a = input              //get first char
[                      //for each char
    b = 64             //divisor to get first 2 bits
    c = a              //initialize as a
    [                  //while c != 0
        c /= b
        d = 65         //first print char
        e = 84         //second print char
        c              //select c
        [              //if c > 0 (3,2,1)
            d + 19
            e - 19
            c - 1
        ]
        [              //if c > 1 (3,2)
            d - 17
            e + 17
            c - 1
        ]
        [              //if c > 2 (3)
            d + 4
            e - 4
            c - 1
        ]              //c is now 0 (hopefully)
        print d
        print e
        b - 1
        [              //if b is not 1 (last 2 bits)
            b + 1      //reset b
            c = a      //trash top 2 bits (modulus algorithm)
            c /= b
            c *= b
            a -= c
            c = 0      //reset c
            c + 4
            b /= c     //b >> 2
            c = a      //copy a again for next 2 bits
            d = 0      //get a 0 value so we don't loop
        ]
        c              //select c (0 if done with char: exit loop and get next char)
    ]
    a = input          //get next char
]
Decoder
384 bytes - line form
GCGCGCGCGCTAATATATATATTAATTAATTAATTAGCTAATATATTAATTAATTAATTAATTAATTAATTAATTAATTATACGCGCGATTAATTAATTAATGCATGCATGCTATAATATATATATATCGCGGCTAATATATTAATGCATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAGCCGGCTAATATATTAATGCATCGATCGATCGATCGATCGATCGGCCGGCTAATATATTAATGCATTAATTAATTAATTAGCCGATTAATTAATTAATTAATATTACGATGCCGCGATGCGCGCGCGCATATATATATCGGCCGATGCGCATATGCGCCG

99 bytes - symbol form
,,[>>++++[>+++++++++*=X+++<<<-=>>>X[>+<+++++++++++++++++++][>+<------][>+<++++]++++>*=<X<,,>>-]<.<]

var names...
DNA# dna decoder

,
,                  /* read second char into a*/
[                  /* for each set of 4 pairs */
    c = 4          /* loop iterator */
    [
        a - 84     /* if pair was AT (65,84): don't increment b */
        [
            b + 1
            a + 19 /* if pair was TA (84,65): increment b once */
        ]
        [
            b + 1
            a - 6  /* if pair was CG (67,71): increment b twice */
        ]
        [
            b + 1
            a + 4  /* if pair was GC (71,67): increment b three times */
        ]
        a = 4
        b *= a     /* shift b up 2 bits */
        a,,        /* get next char (skip one) */
        c - 1      /* decrement loop iterator: exit loop on 0 */
    ]
    b
    print          /* output b in ASCII */
    a              /* select a (next char) */
]                  /* end if next char is 0 (null terminated string) */
If anyone finds a mistake or is able to run the web interpreter feel free to tell me how wrong I am :P

I'll start work on making an interpreter tomorrow

I'm going to give you the bounty, but could you do this in line form instead of symbol form? I feel it'd be more in the spirit of the challenge :)

@βετѧΛєҫαγ haha yah, sure.. I used symbol form to develop as it was more readable (if you could call it that) and somewhat brainfu*k compatible.

Python 2, 10216 5152 + 72 98 + 122 110 139 = 10410 10398 5389
Encoder:
import zlib
lambda s:''.join('ACGTTGCA'[ord(c)>>b&3::4]for c in zlib.compress(s)for b in(0,2,4,6))

Decoder:
import zlib
lambda s:zlib.decompress(''.join(chr(int(''.join([str('ACGT'.index(s[i+j]))for j in(6,4,2,0)]),4))for i in xrange(0,len(s),8)))

Wow, that encoder and that decoder is so short

@βετѧΛєҫαγ Even shorter once I'd fixed the byte count and golfed some more bytes off!

@βετѧΛєҫαγ ...although I've since figured out compression, as evidenced by getting the same score for my DNA as everyone else.

JavaScript (ES6), 10216 8520 + 85 129 + 97 147 = 10398 8796
Encoder:
s=>s.replace(/..?.?/g,b=>"9876543210".replace(/./g,b=>'ACGT'[b=r>>b*2&3]+'TGCA'[b],r=0,[...b].map(c=>r=r*96+127-c.charCodeAt())))

Decoder:
s=>s.replace(/../g,c=>'ACGT'.search(c[0])).replace(/.{10}/g,b=>String.fromCharCode(...[9216,96,1].map(n=>parseInt(b,4)/n%96^127).filter(n=>n^127)))

Works by packing up to three printable ASCII characters into 20 nucleotides, thus saving 16.6% on average. The characters are mapped from 95 to 1 to shorten the decoder, as it can then use ^127 to floor the division and restore the character code. Excess nucleotides get decoded into 127 which needs to be skipped. The encoder could be 1 byte shorter and the decoder 7 bytes shorter in Firefox 30-57 (note that these are incompatible with the above):
s=>s.replace(/..?.?/g,b=>"9876543210".replace(/./g,b=>'ACGT'[b=r>>b*2&3]+'TGCA'[b],r=0,[...b].map(c=>r=r*96+c.charCodeAt()-31)))

s=>s.replace(/../g,c=>'ACGT'.search(c[0])).replace(/.{10}/g,b=>String.fromCharCode(...(for(n of[9216,96,1])if(n=parseInt(b,4)/n%96|0)n+31)))

Javascript (ES6), 6138 6038 bytes
These functions will encode and decode any printable ASCII characters as required by the challenge rules. They are however using a static Huffman code which is optimized for the example text. They should work pretty well on any other English text, as long as there aren't too many capital letters, digits or miscellaneous symbols. But they will perform poorly on a random input.
Edit: saved 94 bytes by rethinking the decoder logic and including all hints provided by Neil
Encoder (305 281 bytes)
s=>(n=0,C={},` e|ahinost|cdlr|.Ibfmuwy|',gpv|"k|;?ATqx|FHW|j|:`.split`|`.map((g,i)=>([...g].map(c=>C[c]=('00'+(n++).toString(2)).slice(-i-3)),n*=2)),s=s.replace(/./g,c=>C[c]||(524160|c.charCodeAt()).toString(2)),s.length&1&&(s+=0),s.replace(/../g,c=>'ATCG'[c=+`0b${c}`]+'TAGC'[c]))

Decoder (391 315 bytes)
s=>(n=N=0,C={},` e|ahinost|cdlr|.Ibfmuwy|',gpv|"k|;?ATqx|FHW|j|:`.split`|`.map((g,i)=>([...g].map(c=>(C[j=i+3]=(C[j]||{}))[n++]=c),n*=2)),s=s.replace(/../g,c=>''+((x='ATCG'.search(c[0]))>>1)+(x&1)),eval(`for(r='';N<s.length-1;){for(i=j=0;!(f=C[j]&&C[j][i])&&j++<19;i+=+s[N++]+i);r+=f||String.fromCharCode(i&127)}`))

DNA sequence (5442 bytes)
Below is the DNA sequence which is generated for the example text.
GCTATAATATCGCGCGTAGCGCATATCGATTAATATTACGGCGCCGTATACGATCGGCGCTAGCATTAGCTAATCGGCATTAGCCGATCGTAATATCGATGCCGATTAATGCATGCTAATGCTAATGCTAATATTAATTAGCCGGCCGATTATATAATCGTAATTAATGCATTAGCATATTACGCGTACGGCCGATATGCATCGATCGCGTAATGCGCCGGCATCGGCCGATTAATATTAGCGCATTACGATGCGCTAATATGCCGCGTATATACGCGGCATCGCGATGCTATAATTATAGCCGATTAGCGCGCATTATAATATTAATGCGCTATACGTAATCGTAATTAGCTAATGCTATAATCGCGATGCGCCGATTAGCATGCGCTACGATGCCGCGATGCCGATGCATTACGCGATATGCGCGCGCTAATGCGCCGATGCATTACGATATATCGGCATTACGATCGGCCGATGCCGTAGCGCTACGATTAATATTACGGCGCCGATCGATGCCGCGATGCCGTAATATCGATGCGCTAGCATTAATCGCGTAGCTACGATGCGCCGCGGCATTAATTAATTAGCGCTACGATTATACGATGCCGCGATTACGGCATTATAATGCCGTACGCGTACGGCTAGCGCCGTAGCATATATTACGCGCGATATGCTAATGCGCCGTAGCGCCGCGATATCGATGCGCTAGCATTACGCGGCGCCGATGCATTACGATATATCGTAGCCGCGGCATCGTAATGCCGCGATATGCGCGCTACGCGCGTATAGCATATCGCGTAATTAATCGCGTAGCTAGCATCGATGCGCCGCGGCTATAATATCGTAATCGATTAATTAGCATATCGTACGTACGCGTACGCGTACGCGATTATACGTAATTAGCATTAATCGTAATCGATTATACGATGCCGCGATTACGGCATTATAATGCCGTACGCGTACGGCTAGCGCCGTAGCATATATCGCGTATATACGCGTAATATGCTAATCGATGCTACGGCCGTACGCGATTAGCTAGCATTAGCATCGATTAATCGTAATATCGATATCGTACGGCATGCATTATAGCCGCGTACGCGTACGCGATTATAATCGTAGCGCTACGTAATTATAATCGCGGCTAATCGATTAATGCATTACGATATATCGTAGCCGGCTAATGCATGCTAATATTAATTAGCCGGCCGATTACGCGCGATTACGGCATTACGGCTAATTAGCATATTACGTAATATCGATATCGGCGCGCATGCCGATGCATATATCGCGTATATACGTAGCGCGCTATAGCCGTAGCGCCGCGATATCGATGCGCTAGCATTACGCGCGATCGCGTATATACGTAGCGCGCCGGCATTATAATCGCGCGTATAATATTATAATGCGCCGATCGTAATTAGCGCTACGGCATGCGCTAGCATTAATTACGGCCGATTAGCGCCGTACGCGCGCGGCCGGCGCTAATATTAGCGCGCCGATGCTACGTACGTACGCGATTAATTACGGCCGATTAATGCATTACGATGCGCATCGATCGCGTATAATCGATGCTACGATCGCGTAGCATGCTATAGCTACGATCGCGTATATAATCGCGATATCGCGTAATTAATCGTAATGCATCGATTACGCGTAATATCGTAGCGCATTAATTACGGCATATCGTACGGCTACGATATCGATCGCGCGATATTAATTATAATCGCGTAGCATCGATGCGCTACGTACGATGCGCTAGCCGATATCGATTAATTAGCCGGCCGATCGCGCGATATTAGCATATTAATTATATAATTAATTAGCCGTAATTACGCGCGATGCTACGATGCCGATTACGATGCGCGCATATGCCGCGATATGCGCGCTATACGATCGCGTATACGATGCCGTAGCGCTAATCGCGATGCTATAATTAGCATATCGTAGCTACGATTAGCCGATCGCGATTACGGCATTAATTAGCGCGCATGCCGTATACGCGCGATCGATTAATCGTAATTACGTAATGCCGGCCGGCATGCCGTACGGCCGATTAATATGCATGCTAATCGCGTACGCGTACGCGGCATCGTACGATGCATTAGCTACGATTAATCGTAATATCGCGTAATATGCTAATCGATGCTAATGCTAATGCTAATATTACGCGCGATCGGCATCGATGCCGATTAATGCGCTAGCGCCGGCGCATCGTACGGCATGCATCGTATAATTAATTATAATCGCGTAATTACGGCATTATAATGCCGTACGCGGCCGGCATTAATTACGGCCGATTAATATTACGGCGCCGATCGATGCCGCGATGCCGTAGCTAATATTAGCGCCGCGCGCGATTATAATCGCGTAATTAATCGCGTAGCATATTAATTATAATGCTAGCATATTAGCGCATCGATGCTATAATTAATCGTAATCGATGCCGATGCCGTACGGCATCGCGATGCCGATCGATGCATCGTAATATCGTACGGCTAATTAGCATGCTAATATCGCGTATAATCGATGCTAGCGCATTAATTAGCTAATTAGCATCGATCGCGTATATAATTAGCATATCGCGTAATTAATCGTAATGCATGCCGCGATATGCTATAATTATACGCGATGCCGTAGCATTATAGCATATGCTAGCATATCGTAGCCGCGTACGTAGCATCGATCGCGTATAATCGATCGGCATTAGCATTACGATCGTAATATGCATGCCGATCGCGTATAATGCCGTAATGCGCCGTAATTATAATCGCGTAATTATACGCGATGCCGATGCGCTAGCCGATTACGCGGCATCGTATAATTACGGCCGATTAATCGGCTATAATGCTAATATGCGCATCGATTACGTAGCCGTATACGCGGCCGTAGCGCATCGATGCCGCGTATATACGCGGCATCGCGATTAATGCATTAATGCATATATTATATAATGCGCCGATTAATATCGATATGCTACGATCGCGTAGCATGCTATAGCTAGCCGCGATATGCTATAATTAGCATATTATAATTAGCATATGCTATATAGCCGATCGTAATATGCGCATTATAATATGCGCGCGCGCTAGCATGCATGCTAATATGCTACGATCGCGTAGCATGCTATAGCTACGATTAATCGCGATTATAATCGCGGCTAATCGATCGGCCGGCTAGCATATTATAGCCGTATACGCGATTAGCGCGCATCGATTAATCGCGATTAATATGCCGTAATTATACGATCGGCGCTAATGCTAGCATATTACGCGATGCCGTAGCGCGCATATATCGCGTATAATGCCGTAATGCGCCGATCGTAATATCGTACGATCGTACGATATTACGGCATTATAATGCCGTACGCGGCCGGCATATCGTATAATATCGTAGCCGATTAATGCATTACGATATGCCGTAATTATAGCTACGGCCGATATCGGCGCATCGGCTAATATGCGCATGCGCCGTAATTATAATCGCGTAATATGCATGCCGGCCGTAGCATCGATCGTACGCGGCATGCGCATGCTACGCGCGGCCGTAGCATCGTAGCGCATCGATTAATGCATTAATGCATATATCGCGTATAATCGATGCGCTAGCCGTACGATCGGCATTACGTACGTAATGCATGCCGCGATATGCGCGCTACGCGCGTAATTACGGCCGCGTATACGCGCGATTATAATCGCGCGTATAATATCGCGTATAATCGATCGGCTAATTACGATCGATGCATGCATCGATTACGTAGCATTATAATCGCGTAATTACGGCGCCGATCGATGCCGCGATGCCGTAATATTAGCGCCGTAATTACGATGCGCCGATTACGGCCGATTACGTAGCATTAATTACGTACGGCCGTAGCATCGATCGCGCGATATATCGTATATATATACGTATAATCGGCTATAATATTACGTAGCCGTAATGCTACGCGCGCGTAATTATATAATATATGCGCTAGCATTACGATGCATATGCATGCCGCGTATAATTAATATGCTATAATATTACGCGTAATATGCATGCGCTAATTAGCATCGTACGTACGCGTACGTAGCGCGCTATAGCGCCGATATATGCTATAATATGCCGATATCGCGATGCGCATCGATCGCGTATATAATCGCGATATGCATGCGCATCGTACGGCTATATAATCGATCGGCATCGATGCCGATCGTAATCGTAATTATAATCGCGTAATTATACGCGATGCATTAATTACGTAGCTAATATTACGCGGCTAATATTAATCGGCGCTAGCCGTAATATCGATATGCGCGCCGTAGCATCGTACGTACGCGTACGCGATTAGCGCGCGCGCGCCGATTATAGCCGATATGCATCGATCGCGTATATACGCGTAATATCGATTACGTACGCGTATAATGCTAATGCTATACGATTAATCGTATAGCCGTAATCGATTAATGCATTAATGCATATATATGCGCGCGCTATACGCGTACGCGATATGCATGCCGATCGCGTATAATCGATGCATTAATTAGCTAATTAGCATCGATGCTAGCCGATGCATGCGCATTAATGCGCGCCGTAATTAGCGCGCGCATCGGCGCTACGATTACGCGTAATATGCTATAATATTAATATGCATGCTAATCGCGTACGCGTACGCGGCTAGCGCCGTAATTAGCGCCGCGGCATTACGATATTAGCGCTACGGCATGCGCTAGCCGTAATTAATTACGGCCGATTACGTAGCCGCGATGCCGTAATGCATGCTAATGCATGCGCGCCGCGATTAGCGCGCATGCCGTAATGCATGCTAATGCTAATATGCGCATCGATGCCGCGTATATACGCGGCATCGCGATCGCGTATAATCGATCGTACGGCATGCATTATAGCCGGCATTAATTAGCGCTACGGCGCATTAGCTATACGATATGCTAGCGCGCTAATTAATTAATATGCGCCGATGCCGGCATATCGTATAGCCGGCGCATCGATCGCGCGATATTATAATCGCGTAATATTAGCGCGCCGGCTACGTACGCGCGATGCGCATATTATAGCCGCGGCGCATCGATCGCGTATAATCGATGCCGATGCCGGCCGTACGCGATGCCGTAGCCGGCATATCGATGCGCTAGCATTATAATCGCGTAATATCGTAGCTAATTAATTAATTACGGCCGATTAATATTACGGCGCCGATCGATGCCGCGATGCCGTAGCTAATATTACGCGGCTAATATCGATTAGCGCATTAGCTACGATTAATCGGCGCTAGCCGTAGCTAATATTACGCGCGATCGGCGCATATGCGCGCCGATCGCGATTAGCATCGGCGCTAGCATGCCGTACGTACGCGTAATTAGCCGGCCGATTATACGATGCCGCGATATGCTATAATATCGTAGCCGTAGCTACGCGCGGCATCGCGTATACGCGCGCGTAGCTAAT

Demo
The snippet below includes some demonstration code.

let e =
s=>(n=0,C={},` e|ahinost|cdlr|.Ibfmuwy|',gpv|"k|;?ATqx|FHW|j|:`.split`|`.map((g,i)=>([...g].map(c=>C[c]=('00'+(n++).toString(2)).slice(-i-3)),n*=2)),s=s.replace(/./g,c=>C[c]||(524160|c.charCodeAt()).toString(2)),s.length&1&&(s+=0),s.replace(/../g,c=>'ATCG'[c=+`0b${c}`]+'TAGC'[c]))

let d =
s=>(n=N=0,C={},` e|ahinost|cdlr|.Ibfmuwy|',gpv|"k|;?ATqx|FHW|j|:`.split`|`.map((g,i)=>([...g].map(c=>(C[j=i+3]=(C[j]||{}))[n++]=c),n*=2)),s=s.replace(/../g,c=>''+((x='ATCG'.search(c[0]))>>1)+(x&1)),eval(`for(r='';N<s.length-1;){for(i=j=0;!(f=C[j]&&C[j][i])&&j++<19;i+=+s[N++]+i);r+=f||String.fromCharCode(i&127)}`))

function encode() {
  var txt, dna;

  if(txt = document.getElementsByTagName('textarea')[0].value) {
    dna = e(txt);
    document.getElementsByTagName('textarea')[0].value = '';
    document.getElementsByTagName('textarea')[1].value = dna;
    document.getElementsByTagName('div')[0].innerHTML = 'DNA length: ' + dna.length + ' (' + (dna.length / txt.length).toFixed(2) + ' nucleotides per character)';
  }
}

function decode() {
  var txt, dna;

  if(dna = document.getElementsByTagName('textarea')[1].value) {
    txt = d(dna);
    document.getElementsByTagName('textarea')[0].value = txt;
    document.getElementsByTagName('textarea')[1].value = '';
    document.getElementsByTagName('div')[0].innerHTML = 'Text length: ' + txt.length;
  }
}
textarea {font-size:10px;font-family:Arial;width:400px;height:70px}
<textarea>I have a friend who's an artist and has sometimes taken a view which I don't agree with very well. He'll hold up a flower and say "look how beautiful it is," and I'll agree. Then he says "I as an artist can see how beautiful this is but you as a scientist take this all apart and it becomes a dull thing," and I think that he's kind of nutty. First of all, the beauty that he sees is available to other people and to me too, I believe. Although I may not be quite as refined aesthetically as he is ... I can appreciate the beauty of a flower. At the same time, I see much more about the flower than he sees. I could imagine the cells in there, the complicated actions inside, which also have a beauty. I mean it's not just beauty at this dimension, at one centimeter; there's also beauty at smaller dimensions, the inner structure, also the processes. The fact that the colors in the flower evolved in order to attract insects to pollinate it is interesting; it means that insects can see the color. It adds a question: does this aesthetic sense also exist in the lower forms? Why is it aesthetic? All kinds of interesting questions which the science knowledge only adds to the excitement, the mystery and the awe of a flower. It only adds. I don't understand how it subtracts.</textarea><br>
<button onclick="encode()">Text -> DNA</button><button onclick="decode()">DNA -> Text</button><br><textarea></textarea><div></div>

match...map...join is the same as replace, no?

+\0b${c}`is shorter thanparseInt(c,2), although 'ATCG'[c=+`0b${c}`]+'TAGC'[c]` might be shorter still.

'ATCG'.search(c[0]) is shorter than 'ATTACGGC'.indexOf(c)/2. Also I think S.indexOf(c,n)==n would work instead of substr.

Oh, one final thing I overlooked: c.charCodeAt() suffices without the 0.

One, um, post-final thing: use \`s for your encoding string, saves having to quote the "` character.

@Neil - Thanks! I've also rewritten the decoder to get rid of Object.keys(), substr(), parseInt(), indexOf()', etc.

The [...s].map(...).join\`might also be better as areplace`, but I didn't count it to check.

Python 3, 15324 + 122 + 211 = 15657 bytes
This is a very wasteful method which converts each character to a three digit number and, for each of those three digits, assigns it a two unit code.
Encoder, 122 bytes
u='AAAATTTCCGTTTTAAAGGCATCGTCGCGGTAGCAGCGCC'
o=''
for i in o.join("%03d"%ord(i)for i in input()):o+=u[int(i)::10]
print(o)

See the encoded version of the example text here
Decoder, 211 bytes
u=['ATAT','ATTA','ATCG','ATGC','TATA','TACG','TAGC','CGCG','CGGC','GCGC']
l=input()
I=u.index
s=''
for j in[l[i:i+12]for i in range(0,len(l),12)]:s+=chr(int(str(I(j[:4]))+str(I(j[4:8]))+str(I(j[-4:]))))
print(s)

Ruby, 97 + 96 + 5152 = 5345 bytes
Encoder program requires the flags -nrzlib.
Zlib::Deflate.deflate($_).bytes{|b|('%04s'%b.to_s(4)).chars{|c|$><<"ATTACGGC"[2*c.to_i,2]}}

Decoder program requires the flags -przlib.
gsub(/../){"ATTACGGC".index($&)/2}
gsub(/..../){$&.to_i(4).chr}
$_=Zlib::Inflate.inflate$_

Node.js (5.6.0), 5104 + 125 + 122 = 5351
I was originally working in JavaScript, but Node.js provides compression much more easily. Thanks Neil for helping trim out 5 bytes on the encoder!
Encoder (125 bytes):
s=>[...require('zlib').deflateRawSync(s)].map(a=>('000'+a.toString(4)).slice(-4).replace(/./g,b=>'ATCG'[b]+'TAGC'[b])).join``

Decoder (122 bytes):
s=>require('zlib').inflateRawSync(Buffer(s.replace(/../g,a=>'ATCG'.search(a[0])).match(/..../g).map(a=>parseInt(a,4))))+''

DNA Sequence (5104 bytes):
TATATATATATATAATGCATCGTACGATGCCGGCTACGGCATGCATATATATGCATGCGCGCTAATTATATATACGATCGATCGGCCGTAGCATGCATATCGTAGCGCATCGATATATTACGTAGCTAGCATATGCCGCGATATCGTATAGCCGCGATCGCGGCCGTAATATGCGCGCTAATATCGGCATGCTACGATCGATGCATGCCGGCATTAATTACGCGTATACGTATAGCTAATTAATTATAATCGCGCGATTAGCCGGCGCGCGCTAGCGCTAATTAGCGCCGCGTATATAGCCGATCGTATACGTAATCGGCATTAATATCGATCGTAGCATCGGCTATACGGCTAATCGATGCGCCGTATAATTAATTATAATGCCGGCCGATATGCATGCATATTATACGGCCGCGCGTATAATGCATCGATTAGCCGTACGCGTAATTAGCTATACGTAATCGTACGTAGCCGCGTATACGTAATATATCGCGTAATTATAATCGATCGGCTACGCGCGGCGCCGATATGCTAGCATCGATCGTAATATGCTAATCGTATACGTATATACGTACGCGATCGGCATGCATGCATCGCGGCTATACGTACGGCCGATATGCATTAGCATATCGTAGCTAATCGATGCGCCGGCGCATATCGATCGATGCGCTAATATGCCGATTAATGCCGTAGCTATACGCGATCGTATAATGCGCGCATCGATGCATGCCGTAATTACGCGGCTACGATTACGCGTACGATGCTATAGCTACGCGTAATTAATTAGCTAGCATCGGCCGATTACGGCCGCGGCTACGTAGCATGCTAATCGCGTAATTATAGCGCCGGCGCATGCTAGCATGCTAATCGCGATGCTAATTAATCGTAATTACGCGCGCGCGTAATCGGCCGCGATGCCGCGTATAATTACGTAATGCCGTATAGCTAATCGATGCCGCGTACGCGGCGCTACGATGCCGCGATATCGCGTACGATCGTAGCTAGCATATTAATATTATAGCCGGCCGCGTAGCATGCATCGCGATTATATACGCGCGGCGCATGCTATAATTAATTAATGCTAATTAATCGCGATGCCGCGCGGCCGATTACGCGCGTAGCCGTATACGTAGCATCGGCGCATCGGCCGCGTAGCTATAATGCGCCGGCTAATCGGCTACGGCATATTAATGCCGCGATCGATCGTACGGCGCTATAATGCCGGCCGCGTAGCCGCGTATAATTAATGCCGATTAATCGCGGCGCTATATAATATATTATAGCGCGCATTATATAGCGCCGATGCTAGCGCTATACGGCGCTACGTAATTATAATATTATATAGCATGCTAGCCGCGATTATAGCATCGATGCTAATGCTACGCGCGCGTACGCGGCTACGATTAATTAGCTAATCGATATATGCTACGATTATATACGGCCGTAATTACGCGCGTAGCCGCGTAATGCCGTAGCATATCGTACGATATATTATACGGCGCTAATTACGCGATCGCGCGATTACGATCGTAGCATTAGCCGTAATTAATATATTATAGCATTAGCATTACGCGATCGCGGCATCGCGCGTAATGCTATAGCATCGCGGCTATAGCCGTAGCTATATAATGCATGCCGGCGCTAGCTAGCGCATATATTACGGCATATGCATTAGCGCATGCCGATATGCTACGATATCGGCTAGCCGATCGTATACGCGATCGGCCGCGTATAATCGCGCGGCGCTACGTATAGCTACGCGCGTAATTATAGCGCCGGCATTACGCGATATATGCCGTAGCATGCCGGCCGCGATTAGCCGCGTAATATATATTACGCGTAGCTAGCTAATTACGGCTACGGCTATAGCCGGCCGATTATAATTAATATTACGGCCGCGGCTATAGCATATATATGCGCATGCATTACGATTATATAGCATGCATATATCGATATCGTAATCGATTATAATATTATACGATCGCGCGATTACGATTATATACGTATAGCATATTAGCTACGTATAGCATTATAGCATATATGCTAGCTAGCCGGCTAATTAATATATGCCGCGATATATATGCGCATTAGCATGCCGATCGCGTAGCGCATCGATTAGCATATCGGCATGCGCGCCGTAATGCTAATGCTATATAATCGCGCGGCGCGCCGGCCGGCGCCGGCATATGCATATATATGCCGGCATGCATGCCGATTATATAGCGCGCCGCGTATATAGCCGCGATGCCGGCATTAGCATCGGCATCGCGGCTAGCGCATCGATCGTACGTACGTATAATTAGCATATCGCGCGCGGCATGCCGCGATTACGTAGCTAGCATTAATATATATCGATTAGCGCATGCTAATATATGCCGATATATATATTATAGCCGATCGGCGCATTATAGCCGATTAATTAATCGCGATTACGTACGGCATTATATACGTATACGCGCGTATAGCGCATATATTAATATCGATATGCGCGCATTATATATAGCCGATTACGTAATGCCGGCGCCGCGATGCATTAATCGATGCTAATATATTATACGTAATATCGGCTACGCGTATAGCATATATTACGCGATTACGATCGGCGCGCGCGCATGCTAGCATATCGATGCGCGCCGTAGCCGATCGCGCGGCATTAGCATGCGCTATAATCGATATATATTAGCCGATCGTATACGGCTACGCGCGTAATGCATTAGCCGTAGCATGCCGATTATAGCATATCGCGGCGCATATCGCGGCTACGGCATTAATCGATTATAATCGATGCATTAGCGCCGTAATGCCGATCGATTAGCATCGCGGCTATACGATCGGCTATAGCATTAATATATATTATACGCGGCATATATTAGCGCATTAGCTACGTAATATGCGCCGATTATACGGCCGGCATGCGCTACGGCATATTAGCCGCGTAATCGTACGCGATATTACGCGCGTAATGCCGTAGCGCATCGGCATATATCGCGATGCTACGTAATGCATGCATGCTAATCGATGCCGCGATCGATGCGCTAGCATCGTATAATATCGGCTAATCGTATACGTATATATAGCGCGCTATACGTAATGCCGGCTATATACGGCCGGCGCATGCGCATATGCATCGGCTAATTACGCGATCGTACGATCGATATATGCTACGGCGCGCATATCGGCTAGCCGCGCGCGGCCGGCTAATGCCGCGCGATATCGGCGCTATACGGCCGTACGATGCCGCGCGATATCGATGCTATAATTACGCGTAATCGATATGCGCTAGCGCCGATCGTATAGCTACGTAGCGCATTACGGCATGCTACGCGGCATGCATTAATCGGCCGATCGGCGCCGTAGCTACGATATCGTACGGCGCCGGCGCATTAGCTAGCGCGCGCGCCGCGGCATGCTATAATATTACGTACGCGTACGTAATATTAGCATGCATTAATTAGCCGGCATTATAGCTACGCGTACGCGATGCATTATACGTAGCGCTAGCATCGCGCGCGCGTATATAATGCCGCGTATACGATTAGCTATAGCCGGCCGCGCGGCTAGCATGCCGATCGATGCTAATCGGCCGTAATTACGATATTATATATATATATAGCTAGCGCATGCCGTACGGCCGTACGGCATATATTAATTAATTATAGCGCTAGCTACGATTATAGCTATATAGCTACGTAATCGCGGCATCGTAATCGGCGCTAGCCGCGATGCTAGCCGATCGCGGCCGGCCGCGTAATATGCCGGCGCCGTAATGCCGATCGTATATACGGCATCGCGGCCGCGATGCATGCCGATATCGTACGCGATATCGCGGCTATAGCCGATATCGTATACGCGTAATGCGCATGCTACGATATGCCGCGCGTATATAGCCGATCGGCCGCGTAATATTATAATCGGCATGCATATGCGCCGCGCGTACGGCGCTAATATCGCGCGATTAATTAATATATATTAGCATCGCGATGCGCATTATAATGCTACGCGGCGCCGGCGCCGATCGTATATAATGCCGGCCGCGATATATTAGCTATACGCGCGCGCGGCGCGCTACGCGTATAGCGCGCATATCGATATTAGCATGCTAATCGTAGCATGCATATCGTATACGCGCGATGCGCCGCGATGCATCGGCGCGCGCATGCCGGCGCGCGCCGCGCGGCATTATACGTAATCGTAGCGCGCGCCGATATGCTAATTAGCGCCGCGTAGCATGCTACGGCCGCGGCCGGCCGGCGCGCCGCGGCGCATATCGCGGCATCGCGGCTAATATCGCGATGCCGCGCGGCGCCGATCGTAGCTAGCTAGCGCGCATCGATATATATGCGCGCATGCCGCGTAGCTAGCGCATCGTAATTATAGCATCGCGCGCGGCATCGCGGCGCGCGCTAATTACGTAGCGCTACGCGATTACGCGATTAATGCGCGCCGGCATCGGCATTAGCGCATGCATTATATATATACGCGCGTACGGCGCTACGATATCGCGGCTATAATATGCTAGCGCCGCGATATATCGGCGCATCGTAATATGCGCTAATATATTAGCGCTAATATGCATCGGCATCGATCGGCTACGTATAATATGCGCGCGCATATATCGATATTAGCCGCGTACGTATACGTACGTATATAATGCTAATGCGCATTATAGCCGATTACGTACGATATGCGCGCATTAATCGTATATAGCTATACGATCGCGGCTATACGATATGCTAGCCGTATAGCGCTAGCATATATTAATATCGGCATATGCTAGCGCCGGCCGCGGCTATATACGGCATGCGCGCTACGGCGCTACGCGCGGCGCGCCGTATAATTATACGCGTAGCCGGCGCATATATCGGCCGTAGCCGGCATATGCGCATCGGCGCTAGCTATAGCTAATGCGCTAGCTACGTATACGTAGCCGTAATGCGCCGATGCGCATTAGCATGCTAGCCGCGCGTATACGTACGTATACGATCGCGCGGCGCTATACGCGGCGCCGTACGATGCGCGCCGATATGCATATCGATATATCGGCATGCGCTATACGTAGCATGCATGCATGCTATACGTACGATGCGCGCGCGCGCATATATTA

I think 'ATCG'[d]+'TAGC'[d] saves you some bytes.

@Neil I knew there must be some way to trim that part down, but I couldn't figure out how. Thank you!

Python 2, 12770 + 204 + 271 = 13245
Encoder:
from itertools import*
D=[''.join(p)for p in permutations('AT TA CG GC'.split())]
e=lambda x:''.join('AT'+D[c-32]if c<56else'TA'+D[c-56]if c<80else'CG'+D[c-80]if c<104else'GC'+D[c-104]for c in map(ord,x))

Decoder:
from itertools import*
D=[''.join(p)for p in permutations('AT TA CG GC'.split())]
n=D.index
d=lambda x:''.join(chr(n(c[2:])+32)if'AT'==c[:2]else chr(n(c[2:])+56)if'TA'==c[:2]else chr(n(c[2:])+80)if'CG'==c[:2]else chr(n(c[2:])+104)for c in map(''.join,zip(*[iter(x)]*10)))

Every character is encoded to a 10-character (5 unit) string, with the first unit indicating what quarter of the printable character string it belongs to, and the last four indicating what character in that quarter is represented.
Try it here.

PHP, 5106 + 297 + 161 = 5564
encoder
$t=str_replace("=","",base64_encode((gzdeflate($_GET["e"]))));$c="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";$e=["AT","TA","CG","GC"];$n="";foreach(str_split($t)as$b){$p=str_pad(base_convert(strpos($c,$b),10,4),3,"0",STR_PAD_LEFT);$n.=$e[$p[0]].$e[$p[1]].$e[$p[2]];}echo $n;

decoder
$e=["AT"=>0,"TA"=>1,"CG"=>2,"GC"=>3];$a=str_split(strtr($_GET["d"],$e),3);$o="";foreach($a as $v)$o.=$c[base_convert($v,4,10)];echo gzinflate(base64_decode($o));


text:
The Final Number
Challenge

Write a program that takes an array of 4 integers (which represents a sequence of numbers generated by a certain algorithm)  and returns the next integer that would follow.
We will only be using simple addition, subtraction, multiplication and division algorithms with a constant (i.e non-variable) variation.
For division we will use the floor integer values: 133/4 = 33 and 33/4 = 8
You can assume that there will always be one single valid return value
Test cases
[14,24,34,44] should return 54 (addition Algorithm)
[105,45,-15,-75] should return -135 (subtraction algorithm)
[5,25,125,625] should return 3125 (multiplicative algorithm)
[256,64,16,4] should return 1 (division algorithm)
General rules

This is code-golf, so the shortest answer in bytes wins the challenge.
Standard loopholes are forbidden

This is a simplified version of What comes next? and borderline duplicate.

I suggest you avoid the term "variance" here, as it's misleading

Please exactly specify the formlas.

You should add a test case with integer division. [261,65,16,4] => 1 for example.

@LuisMendo I agree - what is the correct way to explain it?

Maybe "variation"? Or perhaps say "increment/ratio". For division it's not exactly a ratio because of the flooring, but I guess I'd go with that

In the future, I recommend you to post in Sandbox before going live so that you can receive other people's comments beforehand.

You should really add some tests cases for integer division. Almost all replies fail to give correct result for [261,65,16,4], [4,2,1,0], or [2,1,0,0]

I'd just replace variation with right operand. That works for all binary operators.

I disagree with the duplicate vote(s). Finding the algorithm is simpler in the sense that there's only one operation to consider, but at the same time, it's harder because integer division has to be accounted for. I don't think there's porting an answer from the other challenge would be substantially easier than writing one from scratch.

You should probably specify non-negative integers, as when a division series is negative there are two interpretations. For example -81/4 is either 21 r 3 or -20 r -1.

^ (maybe obviously) that should read -21 r 3

@LegionMammal978 -1 and 0, presumably. As in +0?

Would be nice if the edge cases were added to the post so people can try them out before posting anything.

Is int a,int b,int c,int d a valid parameter-list instead of int[]a, considering the list is always 4 long in the question? Or is int[] mandatory when your language supports it?

I feel like you could do this really easily in Mathematica...

05AB1E, 18 16 18 bytes
D¥¬QPi`+s-ë`r/s\*î

Explanation
D                   # duplicate
 ¥                  # delta's
  ¬Q                # compare first delta to the other deltas
    P               # product (1 if all deltas are equal, otherwise 0)
     i              # if 1 (we're dealing with addition or subtraction)
      `+s-          # add the difference between the elements to the last element
          ë         # else (we're dealing with multiplication or division)
           `r/      # divide the 2nd element by the 1st
              s\*   # multiply with the 4th element
                 î  # round up

Try it online!

The output is wrong with [4,2,1,0] ...

@Damien: Thanks for letting me know. I fixed it and it even saved me a couple of bytes :)

Great. Now it validates all my test cases.

Try edge case for divide by four: [-325, -82, -21, -6]

...actually I guess the question should either be just for non-negative integers or should specify which convention is to be used.

It's OK see my comment on the question

@JonathanAllan: True. Lets wait for clarification from OP. Nice catch on the edge case!

Javascript (ES6),  44   42  44 bytes (fixed)
(a,b,c,d)=>a-b+d-c?d/(a<b?a/b:a/b|0)|0:d+c-b

Saved 2 bytes, following IsmaelMiguel's advice.
Fixed version for [2,1,0,0] and [1,0,0,0] as suggested by edc65
30 bytes version
For the record, my first attempt was 32 30 bytes but was lacking floor() support for the division. It also fails for special cases such as [2,1,0,0] and [1,0,0,0].
(a,b,c,d)=>c-2*b+a?d*c/b:d+c-b

Demo

var f =
(a,b,c,d)=>a-b+d-c?d/(a<b?a/b:a/b|0)|0:d+c-b

var test = [
  [ 14, 24, 34, 44 ],     // should return 54 (addition Algorithm)
  [ 105, 45, -15, -75 ],  // should return -135 (subtraction algorithm)
  [ 5, 25, 125, 625 ],    // should return 3125 (multiplicative algorithm)
  [ 256, 64, 16, 4 ],     // should return 1 (division algorithm)
  [ 260, 65, 16, 4 ],     // should return 1 (division algorithm with floor())
  [ 2, 1, 0, 0 ],         // should return 0 (special case of division algorithm)
  [ 1, 0, 0, 0 ]          // should return 0 (special case of division algorithm)
];

test.forEach(l => console.log('[' + l.join`, `+ '] => ' + f(...l)));

Wow, I didn't know that js has pattern matching.

@LeakyNun - Destructuring assignment was indeed introduced in ES6. Note that you can't do [a,b]=> for function parameters. The parentheses are required.

Nice, but you should handle integer division: [260, 65, 16, 4] => 0.9846153846153847. It should give 1

@Damien - Ah well... I knew someone would notice. ;-) That's fixed.

What about [2,1,0,0] ? Should give 0. I think it's the only counter example for b*2==c+a <=> addition/substraction algorithm

Why do you use destructive assignment? You could do (a,b,c,d)=>c-2*b+a?d/(a<b?a/b:a/b|0):d+c-b and inform that you need to do f.apply(null, [ 14, 24, 34, 44 ]); or pass each value individually to the function (f(14, 24, 34, 44);). This saves 2 bytes. And is standard practice in Javascript (specially in polyfills and with any of the methods on Array).

@Damien - You're right, and [1,0,0,0] is also a problem. Not sure if I can easily fix these special cases.

@IsmaelMiguel - Since it is not explicitly forbidden, I suppose I can do that indeed. Thanks!

[1,0,0,0] is a problem for me too :(

(a,b,c,d)=>a-b+d-c?d/(a<b?a/b:a/b|0):d+c-b, same byte count, works for 2,1,0,0

(a,b,c,d)=>a-b+d-c?d/(a<b?a/b:a/b|0)|0:d+c-b works even for 1,0,0,0

Brachylog, 37 33 27 bytes
b:[E]cL,?:Iz{:+a|:*a|:/a}Lt

Try it online! or verify all test cases.
Saved 10 bytes thanks to @LeakyNun.
Explanation
Input = [A:B:C:D]

b:[E]cL,     L = [B:C:D:E]
?:Iz         Create the list [[B:I]:[C:I]:[D:I]:[E:I]]
{            Either…
    :+a          Sum all couples of that list
|            or…
    :*a          Multiply all couples of that list
|            or…
    :/a          Integer divide all couples of that list
}L          The result is L
t           Output is the last element of L

As LeakyNun pointed out, we don't need the subtraction case because I can be any integer.

wow, brachylog(& prolog) are awesome

Addition and subtraction is the same

29 bytes

27 bytes

Haskell, 65 bytes
f l@[a,b,c,d]|[a,b..d]==l=d+b-a|z<-b+0^b=div(d*b)$a-mod(max b a)z

Python 2, 40 bytes
lambda(a,b,c,d):[d+c-b,d*c/b][c-2*b+a>0]

It's literally the JS answer ported into Python (thanks @LeakyNun!). My previous approach was ridiculously long, but here it is:
Python 2, 169 166 bytes
The second and third levels are a raw tab and a raw tab plus a space, respectively, which plays really badly with Markdown, so the tabs have been replaced by 2 spaces.
x=input()
q='%d%s%d'
for i in range(max(x)):
 for o in'+-*/':
  a=1
  for e,n in zip(x,x[1:]):
   try:1/(eval(q%(e,o,i))==n)
   except:a=0
  if a:print eval(q%(x[-1],o,i))

Pretty simple; tries every constant and operator it thinks could be the constant, then if the constant/operator combination works for every element in the list (using a try/except pair to avoid ZeroDivisionErrors), it prints the result for the last element in the list.
I'm sure there's a better method here, this is the naive method.

You'd better just port the js answer into Python

Breaks for [1,0,0,0] which should output 0

TSQL, 55 bytes
This script is trying adding and subtraction in the same check, then it tries to multiply, if that fails, it must be division.
DECLARE
@1 INT=6561,
@2 INT=729,
@3 INT=81,
@  INT=9

PRINT IIF(@2-@1=@-@3,@*2-@3,IIF(@1*@2=@3,@*@1,sqrt(@)))

Fiddle

C#, 63 bytes
int f(int[]x)=>2*x[1]-x[0]==x[2]?x[3]+x[1]-x[0]:x[3]*x[1]/x[0];

Checks whether the difference between the first and second element is the same as the difference between the second and third element. If so, it does addition/subtraction, otherwise it does multiplication/division.

GameMaker Language, 70 bytes
a=argument0;If a[3]+a[1]=a[2]*2return a[4]*2-a[3]return a[4]*a[4]/a[3]

R, 68 74
Array: 68 bytes
function(x)if(x[2]-x[1]==x[3]-x[2])x[4]+x[2]-x[1]else x[4]%/%(x[1]%/%x[2])

> (function(x)if(x[2]-x[1]==x[3]-x[2])x[4]+x[2]-x[1]else x[4]*x[2]/x[1])(c(14,24,34,44))
[1] 54

4 inputs: 45 bytes
function(a,b,c,d)if(b-a==c-b)d+b-a else d*b/a

Bonus solution with log, exp, var, 71 bytes
if(var(v<-diff(x<-scan(,1)))==0)x[4]+v[1]else x[4]*exp(diff(log(x)))[1]

update: integer division

Isn't this taking four variables rather than an array? If not you can get rid of the parentheses around b-a to save a byte though (and I note that your example calls are adding spaces back in).

@JonathanAllan You are right. It does not take an array.  The byte count has been updated. The parenthesis are needed due to else, but we can save a byte by adding a space instead. The calls don't need the additional spaces.

Yep, that's why I said you could save 1 byte rather than 2

Note, it does not currently handle the integer division requirement fully, e.g. 261,65,16,4 returns 0.9961686 rather than 1 (of course there should be a test case for this in the question).

@JonathanAllan function(x)if(x[2]-x[1]==x[3]-x[2])x[4]+x[2]-x[1]else x[4]%/%(x[1]%/%x[2])

JavaScript, 73 bytes
(a,b,c,d)=>(x=b-a,c-b==x&&d-c==x)?d+x:(x=b/a,b*x|0==c&&c*x|0==d)?d*x|0:-1

Tests:
console.log(s.apply(null,[14,24,34,44]), 54);
console.log(s.apply(null,[105,45,-15,-75]), -135);
console.log(s.apply(null,[5,25,125,625]), 3125);
console.log(s.apply(null,[256,64,16,4]), 1);

console.log(s.apply(null,[2,1,0,0]),0);
console.log(s.apply(null,[1,0,0,0]),0);
console.log(s.apply(null,[-325,-82,-21,-6]),-1);

console.log(s.apply(null,[-1,-1,-1,-1]),-1);
console.log(s.apply(null,[0,0,0,0]),0);

Works for them all.

Wasn't sure about the etiquette here. I know there's already another JS answer, but it doesn't address the edge cases. Mine is longer, but handles all those. Let me know if I didn't do this right.

There's nothing wrong with posting an answer in the same language as another answer, especially if your answer is correct and the other one is not. I don't know if you have enough rep to do so, but you might also want to comment on that answer to let them know which edge cases they are missing.

I actually took the edge cases from that other post, but they haven't solved the issue. ;P

TI-Basic, 37 bytes
Works on any TI-83/84 calculator
Input L1                     gets input into an array
L1(4)²/L1(3                  calculate the fifth number in a geometric series
If not(sum(ΔList(ΔList(L1    if ΔList(ΔList(L1)) yields an array of all zeroes
L1(4)2-L1(3                  calculate the fifth number in an arithmetic series
                             Ans is implicitly returned

Python 2, 75 66 65 61 bytes

lambda(a,b,c,d):d*2-c if d-c==b-a else d*b/a or b and d/(a/b)

Much longer than my previous 38 byte entry which did not cater for the division series correctly (just as most others didn't).
Test cases and more edge cases are on ideone
Note: integer division for a negative here is defined as having a remainder with the same sign as the divisor, so -81/4 would be -21 with a remainder of 3 and -81/-4 would be 20 with a remainder of -1.

negative number divided by negative number is positive... -81/-4 != -21

@DestructibleWatermelon Indeed it is. I have edited that and added the test case [325,-82,20,-5].

Java, 125 123 bytes
Golfed:
int m(int[]a){int r=(a[1]>a[0])?a[1]/a[0]:a[0]/a[1];return(a[0]-a[1]==a[1]-a[2])?a[3]-a[0]+a[1]:(a[0]<a[1])?a[3]*r:a[3]/r;}

Ungolfed:
int m(int[] a)
{
    int r = (a[1] > a[0]) ? a[1] / a[0] : a[0] / a[1];
    return (a[0] - a[1] == a[1] - a[2]) ? a[3] - a[0] + a[1] : (a[0] < a[1]) ? a[3] * r : a[3] / r;
}

This code surely has some issues since it doesn't handle division by zero and such things. It also won't work of course if there are more (or less) than 4 integers in the input array a. Which makes it beyond stupid, but I had fun :)
Try it out: https://ideone.com/nELH5I

Jelly, 14 bytes
ṪḤ_ṪµṪ²:ṪµIE$?

Try it online!
ṪḤ_ṪµṪ²:ṪµIE$?  Main Link =
             ?  If
          IE$   [condition]
          I     The differences between consecutive elements
           E    Is equal
ṪḤ_Ṫ            [then]
Ṫ               The last element
 Ḥ              Doubled
  _             Minus
   Ṫ            The last element (second-last of original list)
    µṪ²:Ṫµ      [else]
     Ṫ          The last element
      ²         Squared
       :        Divided by
        Ṫ       The last element (second-last of original list)

Pyth, 18 Bytes
?-+vzJEyQ/^E2J-yEJ

Accepts input as a newline-separated list of values.
Try it online!
Explanation:
?                         If
 -                          the following are not equal:
  +vzJE                      the sum of first and third values (and call the third value J)
       yQ                    and the second value * 2;
                            (i.e. if it is not an additive or subtractive formula)
          ^E2             Then: square the fourth value
         /   J              and divide by the third
?                         Else:
               yE           double the fourth value
              -  J          and subtract the third

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Look-and-say sequence: roman numerals edition
Challenge description
We've had a few challenges involving the Look-and-say sequence. Quick reminder:

The sequence starts with 1,
Subsequent terms of this sequence are generated by enumerating each group of repeating digits in the previous term,

So the first few terms are:
1        "one"
11       "one one" (we look at the previous term)
21       "two ones"
1211     "one two, one one"
111221   "one one, one two, two ones"
312211   "three ones, two twos, one one"

Now let's do the same thing, but use Roman Numerals instead. We start with I and follow the same rules (we apply the digit-counting rule to characters instead, so we read IVX as one one, one five, one ten instead of one four, one ten or some other way):
I           "one"
II          "one one"
III         "two ones" = "II" + "I"
IIII        "three ones" = "III" + "I"
IVI         "four ones" = "IV" + "I"
IIIVII      "one one, one five, one one"
IIIIIVIII   "three ones, one five, two ones" = ("III" + "I") + ("I" + "V") + ("II" + "I")

Given a positive integer N, either:

Output first N numerals of this sequence (any reasonable separator is fine, as well as ["I", "II", "III", ...]
Output Nth term of this sequence (it may be 0-indexed).

Remember to make your code as short as possible, since this is a code-golf challenge!
EDIT: I believe that there is always one standard/preferred way of expressing integers as roman numerals, (like 95 -> XCV instead of VC). Couple of Roman numeral converters I found online corroborate my opinion. If in doubt, use an online converter, as listing all the possible edge-cases and specific rules of writing Roman numerals is not the point of this challenge.
EDIT2: @PeterTaylor and @GregMartin pointed out that only numbers less or equal to 5 appear in the sequence, so you don't have to worry about the ambiguity of Roman numerals (numbers 1 - 8 are I, II, III, IV, V, VI, VII, and VIII)

There isn't a unique Roman numeral expression for each integer. Which numbers might it be necessary to express, and which expressions of those numbers are valid?

What do you mean by "there isn't a unique Roman numeral expression for each integer"? Like 4 / IV / IIII ? Or 95 / XCV / VC ? There might not always be a unique way to express an integer, but I'm pretty sure there's always a preferred (standard) one - correct me if I'm wrong.

how far do we have to go with our roman numberals?

Yes, both of those cases. In the second case, I think it's very much a matter of opinion which is preferable.

@Maltysen I think the number of equal digits that can appear in succession is limited to 7.

@shooqie I agree with you on this one, but you might just want to solidify the rules for roman numerals in OP.

@Maltysen: Like, this is something that bothers me the most about this site. Make a challenge a tiny bit more complicated and you get questions like what counts as X? or what about the edge-case #98752314?

@shooqie if these details weren't clarified, how would you compare answers? If there are certain edge cases left up to interpretation the actual scores become meaningless because they might make a bigger difference than any golfing tricks you could come up with.

@MartinEnder: Well, I did my best at clearing up the confusion about the Roman numerals, but I feel like I shouldn't have to say how to write them - we've had challenges with Roman numerals before and there didn't seem to be any confusion whatsoever.

I don't understand the output format - are we converting to roman numerals, grouping by character type, counting the length of each group and turning the whole thing into roman numerals again?

@muddyfish: Yeah, pretty much.

I think one can mathematically prove that numbers greater than 8 never appear in the sequence starting at I. If so, then programs need only consider Is and Vs.

@GregMartin, it's possible to prove the stronger statement that no run-length greater than 5 appears in the sequence whose first generation is I.

1k rep! Congrats :)

@GregMartin: Well, that certainly makes things easier.

Surprisingly roman numerals are in fact a decimal notation where a number is split into powers of 10. So 999 = 900+90+9 = CM + XC + IX = CMXCIX and not IM (This is the modern standard form. The romans themselves were not completely consistent). But as noted this is not needed here.

Perl, 49 bytes
Includes +1 for -p
Run with the 0-based index on STDIN, e.g.
ecce.pl <<< 14

ecce.pl:
#!/usr/bin/perl -p
s,(.)\1*,$&/$1%182 .$1,eg for($_=/$/)x$`;y;19;IV

Magic formulas are so magic.
Normally I would use ($_=//)x$' to make the loop control one byte shorter, but scoring on this site gives that a handicap of 2 so it ends up 1 byte longer. On older perls you can drop the space before for. Some versions of perl force you to add a final ; to close the transliteration. But what is given above is the code that works on my system.
Explanation
Working backwards from solution to code:
The string transformations we need:
I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

Each replacement ends with the repeated character. I will get a sequence of the same characters using regex /(.)\1*/, so this can be done by appending $1. The part before the -> is in $&. With that I still need:
I     -> I
II    -> II
III   -> III
IIII  -> IV
IIIII -> V

V     -> I
VV    -> II

Write I as 1 and V as 9:
1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

9     -> 1
99    -> 11

By dividing the part before -> by the repeated digit this becomes:
1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

1     -> 1
11    -> 11

So now the original repeated V is not an exception anymore. So I want an expression that makes this happen:
1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

And this can be done by a simple modulo 182:
1     % 182 = 1
11    % 182 = 11
111   % 182 = 111
1111  % 182 = 19
11111 % 182 = 9

(this even gets IIIIII to VI right though it isn't needed here)
All that is left is initializing the working variable to 1 for index 0, repeat this transformation in a loop and at the end replace 1 by I and 9 by V
1, 9 and 182 is the only parameter combination for which this simple formula works.

This is genius! :)

Mathematica, 113 90 83 bytes
Thanks to Martin Ender for suggestions that reduced the length by over 25%!
Showing off the high-level commands in Mathematica.
Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&

A pure function, taking an argument N and outputting the Nth element of this (0-indexed) sequence, as a list of characters. Spread out a bit:
Nest[
  Flatten[
    Characters @ {RomanNumeral@#,#2}& @@@
      Reverse @@@ Tally /@ Split@ #
    ]& ,
  {"I"}, #]&

The outer Nest iterates the middle four-line function, starting on {"I"}, N times. Line 4 splits the character list of the input Roman numeral into runs of like characters, counts each run with Tally, and puts the counts before the characters they're counting. Line 3 renders the counts as Roman numerals, then splits those Roman numerals up into lists of characters. The Flatten command reduces the whole list-of-lists to a one-dimensional list.
Here's the initial version:
Nest[
  "" <> Flatten[{RomanNumeral@#[[1]], #[[2]]} & /@
    (Reverse@#[[1]] & /@
      Tally /@
        Split@Characters@#)] &,
  "I", #] &

Grrr Mathematica ;)

If you use @@@ instead of /@ you can use # and #2 instead of #[[1]] and #[[2]]. Also, lists of characters are acceptable string types, so you can work with those and avoid using Characters@.

@MartinEnder Aha, I knew there must have been a @@@-like shortcut! As for lists of characters being acceptable string types (which I agree would shorten the code): is there a post on this site you can point me to that describes the community standard(s)?

http://meta.codegolf.stackexchange.com/a/2216/8478

A few more savings: Characters threads automatically so you can use @, Reverse@#& is of course the same as plain Reverse, in which case you also don't need those parentheses. And prefix notation (in the case of Flatten) doesn't save anything if you need to add parentheses to make it work. Combining all of those: Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&

CJam (33 30 bytes)
"I"{e`{(4md1$^'I*\'V*@}%e_}ri*

Online demo
Key to the correctness of the implementation is the following theorem:
If the first generation is I, no run length is ever greater than five
Lemma: if the first generation is I, no string ever contains VVV. Proof is by contradiction. Suppose that there is a first index n for which the nth generation contains VVV. If that VVV breaks down as (a)V VV then the conversion  from the previous generation is bad: it should have been (a+5)V. So it must be VV V(d), and the previous generation contained VVVVV, contradicting the choice of n.
Now, suppose there is a first index m for which the mth generation contains ...IIIIII.... Note that there can be no digits other than I and V in the string, because no previous generation has had a run of nine Is or nine Vs. At most four of the Is come from a run of Is in the previous string, so the corresponding section of the previous string must be ...IIIVV... giving ... IIII IIV .... Since the VV in generation m-1 doesn't come from VVVVV (see lemma), the second V must be a run-length of digit I, so in generation m-1 we have ...IIIVVI.... And since we want the initial Is to give IIII and not IVI or VI, it is preceded either by the start of the string or by a V.
If we have (...V)?IIIVVI... in generation m-1, what do we have in generation m-2? We've already observed that the VV of gen. m-1 must be parsed as (a)V V(I).
Suppose we take a=2: (...V)?I IIV VI... Actually it must be ...VI IIV VI..., although that leading V might be part of IV; so in the previous generation we have either (...V)? IIII VV IIIII... or (...V)? IIIII VV IIIII. Either way we run into trouble with VVIIIII: the second V must be a run-length, but then ...VI IIII... requires a following (run-length, digit) pair with the same digit.
So it must be a=1: (...V)?II IV VI.... Since generation m is the first with a run of six Is, that must be (...V)? II IV VI..., so that generation m-2 is (...V)? I V IIIII.... ...VIVIIIII... is impossible: however we choose to interpret the second V we end up with two consecutive (run-length, digit) pairs with the same digit.
Therefore generation m-2 must be ^IVIIIII..., parsed as ^IV IIII I(V)... or ^IV III II(V).... These give respectively generation m-3 as ^V III V ... or ^V II VV....
But if we look at the start of the strings beginning with the first one that starts with V, we get a cycle:
    VI IV I...
    IV III IV ...
    II IV IVI ...
    IIII IV II IV ...

and so no generation ever starts with either VIIIV or VIIVV. We must conclude that there is no such m.
Dissection
"I"          e# Initial generation
{            e# Loop...
  e`         e#   Run-length encode
  {          e#   Foreach [run-length char] pair...
    (        e#     Extract the run-length r
    4md1$^   e#     Get the number of Vs and the number of Is
             e#     The number of Vs is r/4 ; the number of Is is (r%4)^(r/4)
    'I*\'V*@ e#     Repeat strings the appropriate number of times and reorder
  }%
  e_         e#  Flatten to a simple string
}ri*         e# ... n times, where n is taken from stdin

Python 3, 195 bytes
There's a lot of bytes wasted on the roman numerals, so there's likely some golfing to be done there.
Thanks to @El'endiaStarman, @Sherlock9 and @Shooqie
import re
def f(x,r=""):
 for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*a
 return r
s="I"
for i in[0]*int(input()):print(s);s=re.sub(r'(.)\1*',lambda m:f(len(m.group()))+m.group()[0],s)

Ideone it!

You can omit square brackets: for v,i in(5,"V"),(4,"IV"),(1,"I")

@shooqie I had no idea that you could do that :D

for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*a saves a byte.

@βετѧΛєҫαγ: Also, you're not seem to be using i (as in for i in range(...)). I tried dabbling with exec but this escaped 1 in the 'sub' method seems to be messing up the code, I haven't been able to find a workaround.

@shooqie I shortened it a bit by getting rid of range

Hi, next time you might want to cross-out the previous byte-counts when improvements are made. I.e. Python 3, 314 210 202 200 199 196 bytes. A.f.a.i.k. it's kinda standard to do so here on PPCG.

@KevinCruijssen Nah, there isn't a standard on PPCG, and I prefer to keep it neater

R, 110 107 Bytes
as.roman combined with rle makes this easy. Scoping abuse and built in cat behavior of <<- saves a few bytes.
x="I"
replicate(scan(),{r=rle(strsplit(x,"")[[1]])
x<<-paste(rbind(paste(as.roman(r$l)),r$v),collapse="")})

Takes in N from console. Outputs first 2 to N terms of sequence (which I believe is within spec...)
 [1] "II"
 [2] "III"
 [3] "IIII"
 [4] "IVI"
 [5] "IIIVII"
 [6] "IIIIIVIII"
 [7] "VIIVIIII"
 [8] "IVIIIIVIVI"
 [9] "IIIVIVIIVIIIVII"
[10] "IIIIIVIIIVIIIIVIIIIIVIII"
[11] "VIIVIIIIIVIVIIVVIIVIIII"
[12] "IVIIIIVVIIVIIIVIIIIIVIIIIVIVI"
[13] "IIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"
[14] "IIIIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"
[15] "VIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"
[16] "IVIIIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"
[17] "IIIVIVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"
[18] "IIIIIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"
[19] "VIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"
[20] "IVIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"
[21] "IIIVIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"
[22] "IIIIIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIIVIVIIVIIIIIVVIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"
[23] "VIIVIIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVVIIVIIIVIIIIVVIIIVIIIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"
[24] "IVIIIIVVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIIVIIIIVIIIIIVIVIIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"
[25] "IIIVIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIVIIVVIIVIIIVIIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"

Perl 6, 62 bytes
{("I",{S:g/(.)$0*/{[$/.chars-1]~$0}/}...*)[$_]}

Anonymous function that accepts a zero-based index.
Makes use of the fact that roman numbers higher than 5 aren't needed, because the only groups of repeating digits that can occur, are:
I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

(try it online)

JavaScript (ES6), 107
Recursive function returning the Nth term 0 based
f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

Test

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

function update() {
  O.textContent=f(I.value)
}

update()
<input id=I value=25 type=number oninput='update()'>

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Can you beat the British Intelligence? (Nonogram Solver)
It is time to embark on a perilous quest to defeat the British Intelligence. The aim of this challenge is to write the shortest code that will solve a Nonogram.
What is a Nonogram?

The rules are simple.
  You have a grid of squares, which must be either filled in black or left blank. Beside each row of the grid are listed the lengths of the runs of black squares on that row. Above each column are listed the lengths of the runs of black squares in that column. Your aim is to find all black squares. In this puzzle type, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups.
   [1][2]

So the solution to the above Nonogram would be:

Implementation Details
You can chose to represent the Nonogram however you would like and take it as an input in whatever way you deem fit for your language. Same goes for output. The aim of this challenge is to literally just get the job done; if you can solve the nonogram with whatever output your program gives, that is valid. One caveat is you can't use an online solver :)
This problem is very algorithmically challenging (np-complete) in that there is no completely efficient solution to it and as such, you won't be penalized for not being able to solve larger ones, although your answer will be heavily rewarded if it is able to handle big cases (see bonus). As a benchmark, my solution works for up to roughly 25x25 within 5-10 seconds. To allow for flexibility amongst different languages, solutions that take less than 5 mins for a 25x25 nonogram are good enough.
You may assume a puzzle in always a square NxN nonogram.
You can use this online nonogram puzzle maker to test your solutions.
Scoring
You are, of course, free to use any language you want and since this is code golf, the entries will be sorted in the order: accuracy -> length of code -> speed. However, don't be discouraged by code golfing languages, answers in all languages that show attempts at golfing in an interesting way will be upvoted!
Bonus
I actually learnt about Nonograms from a cryptographic Christmas card released by the British Intelligence here. The first part was basically a massive 25x25 Nonogram. If your solution is able to solve this, you will get kudos :)
To make your life easier in terms of data entry, I have provided how I represented the data for this specific puzzle for your free use. The first 25 lines are the row clues, followed by a '-' separator line, followed by 25 lines of the col clues, followed by a '#' separator line, and then a representation of the grid with the square clues filled in.
7 3 1 1 7
1 1 2 2 1 1
1 3 1 3 1 1 3 1
1 3 1 1 6 1 3 1
1 3 1 5 2 1 3 1
1 1 2 1 1
7 1 1 1 1 1 7
3 3
1 2 3 1 1 3 1 1 2
1 1 3 2 1 1
4 1 4 2 1 2
1 1 1 1 1 4 1 3
2 1 1 1 2 5
3 2 2 6 3 1
1 9 1 1 2 1
2 1 2 2 3 1
3 1 1 1 1 5 1
1 2 2 5
7 1 2 1 1 1 3
1 1 2 1 2 2 1
1 3 1 4 5 1
1 3 1 3 10 2
1 3 1 1 6 6
1 1 2 1 1 2
7 2 1 2 5
-
7 2 1 1 7
1 1 2 2 1 1
1 3 1 3 1 3 1 3 1
1 3 1 1 5 1 3 1
1 3 1 1 4 1 3 1
1 1 1 2 1 1
7 1 1 1 1 1 7
1 1 3
2 1 2 1 8 2 1
2 2 1 2 1 1 1 2
1 7 3 2 1
1 2 3 1 1 1 1 1
4 1 1 2 6
3 3 1 1 1 3 1
1 2 5 2 2
2 2 1 1 1 1 1 2 1
1 3 3 2 1 8 1
6 2 1
7 1 4 1 1 3
1 1 1 1 4
1 3 1 3 7 1
1 3 1 1 1 2 1 1 4
1 3 1 4 3 3
1 1 2 2 2 6 1
7 1 3 2 1 1
#
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

And here is a slightly different version for your convenience; a comma separated tuple (row, col) where each element is list of lists.
([[7, 3, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 1, 3, 1],
  [1, 3, 1, 1, 6, 1, 3, 1],
  [1, 3, 1, 5, 2, 1, 3, 1],
  [1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [3, 3],
  [1, 2, 3, 1, 1, 3, 1, 1, 2],
  [1, 1, 3, 2, 1, 1],
  [4, 1, 4, 2, 1, 2],
  [1, 1, 1, 1, 1, 4, 1, 3],
  [2, 1, 1, 1, 2, 5],
  [3, 2, 2, 6, 3, 1],
  [1, 9, 1, 1, 2, 1],
  [2, 1, 2, 2, 3, 1],
  [3, 1, 1, 1, 1, 5, 1],
  [1, 2, 2, 5],
  [7, 1, 2, 1, 1, 1, 3],
  [1, 1, 2, 1, 2, 2, 1],
  [1, 3, 1, 4, 5, 1],
  [1, 3, 1, 3, 10, 2],
  [1, 3, 1, 1, 6, 6],
  [1, 1, 2, 1, 1, 2],
  [7, 2, 1, 2, 5]],
 [[7, 2, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 3, 1, 3, 1],
  [1, 3, 1, 1, 5, 1, 3, 1],
  [1, 3, 1, 1, 4, 1, 3, 1],
  [1, 1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [1, 1, 3],
  [2, 1, 2, 1, 8, 2, 1],
  [2, 2, 1, 2, 1, 1, 1, 2],
  [1, 7, 3, 2, 1],
  [1, 2, 3, 1, 1, 1, 1, 1],
  [4, 1, 1, 2, 6],
  [3, 3, 1, 1, 1, 3, 1],
  [1, 2, 5, 2, 2],
  [2, 2, 1, 1, 1, 1, 1, 2, 1],
  [1, 3, 3, 2, 1, 8, 1],
  [6, 2, 1],
  [7, 1, 4, 1, 1, 3],
  [1, 1, 1, 1, 4],
  [1, 3, 1, 3, 7, 1],
  [1, 3, 1, 1, 1, 2, 1, 1, 4],
  [1, 3, 1, 4, 3, 3],
  [1, 1, 2, 2, 2, 6, 1],
  [7, 1, 3, 2, 1, 1]])

Sadly my website is down but it used to have a reasonably fast Nonogram solver; 5-10 minutes sounds excessive.

Related

@Neil Grand! What language did you write it in? I was generous with the time because I didn't want to restrict users of certain slower languages. My solver works in under 10 seconds last I checked.

The way you worded it confused me into thinking your solver takes 10 minutes. Anyway, my solver was written in Java, but it probably wasn't as fast as 10 seconds (then again it would update the screen to show its thinking, which probably slowed it down).

Can we safely assume that the grid is always a NxN square? And BTW, thanks for putting the right name on a puzzle I've seen my wife playing with some times ago. :-) (Color Cross on Facebook)

@Arnauld Yes you can assume it is an NxN square :)

Can we assume that there is only one solution?

@Damien If there is more than one solution, your code should find any one of them. Is there a specific advantage to being able to assume there is only one solution?

I'm not sure yet. But I find it easier when the solution is unique

@Damien Go for it then :)

Is it a "nonogram" or "monogram?" You use monogram twice in the impl details section...

@SocraticPhoenix It's nonogram; damned autocorrect. Will fix it now.

http://codegolf.stackexchange.com/q/30081/21348 Related

Are there going to be empty rows?

@mbomb007 Read the bonus section. The British intelligence released a Nonogram as part 1 of a series of cryptographic challenges last christmas (possibly for employment purposes). As far as I know, no one actually managed to finish all of the challenges.

2 question: do we need to be able to handle unsolvable onces? /// Can I create a random answer, check if it work, if not repeat? (eg bogsort?) ^^

@dwana Your solution probably has to be deterministic.

@dwana You don't need to worry about unsolvable cases. As for the random answer, on a 25x25 nonogram, you have 2^625 possible configurations. In context, that's more than twice the number of atoms in the known universe (i.e. if you used each atom in the universe as a bit, you still wouldn't have enough space to store the possibilities). In terms of time, if it took you a nano second (generous) to check the validity of each configuration, it would take 7 lifetimes of the universe for the code to finish running :)

Ty for clarifying unsolvables cases. (+ i have a magical PC the validates an answer in ~ 2.1546362E-186 seconds)

@dwana Unfortunately for you, it will still take ~4.5E124 years to complete.

Is there a bug in my code or does the Christmas Puzzle have no solution? My backtrace cannot even solve the first 8 rows (returns "no solution" after about half a million iterations).

@Titus It definitely has a solution, although my data entry may have been shoddy. You can check against the original link in the bonus section of the question to validate the data.

No, the port is correct. Must be a bug somewhere. Need a smaller puzzle to test; the tiny one is always correct.

@Titus Try the 10x10s generated by the website linked in the text

I´m done. Can I get a /10 bonus for not using a golfing language? ;-)

Your CSV has no square hints. Here´s some JS to generate them:
s=[].fill([].fill(0,0,25),0,25);s[3][3]=s[3][4]=s3[3][12]=s3[3][13]=s3[3][21]=s[8][6]=s[8][7]=s[8][10]=s[8][14]=s[8][15]=s[8][18]=s[16][6]=s[16][11]=s[16][16]=s[16][20]=s[21][3]=s[21][4]=s[21][9]=s[21][10]=s[21][15]=s[21][20]=s[21][21]=1;

@gowrath Your tuple of lists which you say is (row, col) is actually (col, row). You should swap it around if you want it to match your other data format.

Additional Potential Point of Interest: The smallest unsolvable case is [1,1],[1,1]

Brachylog, 70 69 bytes
[R:C]hlL~l:L:1f=.:3aR,.z:3aC,
tL,?he##ElL,E:2a
.<2,_1<
@b:4f:la
e.h1,

This takes a list of two lists (first the rows indicators, then the column ones). Each indicator is itself a list (for situtions like [3,1] on one row).
This version takes about 3 minutes to solve the 5 by 5 example of the challenge.
Way more efficient version, 91 bytes
[R:C]hlL~l:L:1f:Cz:3az:Rz:3a=.:4aR,.z:4aC,
tL,?he##ElL,E:2a
.<2,_1<
:+a#=,?h
@b:5f:la
e.h1,

Try it online!
This one is not complete brute force: the only difference is that this one imposes constraints on the values of cells such that the number of 1s in each row and column matches the numbers given as indicators in the input. The only brute force part is then in finding the one grid with those constraints for which the "blocks" of 1s match what is given as indication.
This one takes about 0.05 seconds on the 5 by 5 example of the challenge. This is still way too slow for the bonus case, as I have no idea how to express the blocks of ones separated by one or more zeroes in terms of constraints.
Explanation
I will explain below the 93 bytes version. The only difference between the two is the call to predicate 3 which doesn't exist in the 70 bytes version, and the numbering of the predicates (since there is one less).

Main predicate:
[R:C]     Input = [R, C]
hlL       The length of R is L
~l        Create a list of length L
:L:1f     Each element of that list is a sublist of length L with cells 0 or 1 (Pred 1)
          %%% Part unique to the 93 bytes version
:Cz       Zip the rows of the list of lists with C
:3a       The sum of 1s in each row is equal to the sum of the indicators (Pred 3)
z         Transpose
:Rz       Zip the columns of the list of lists with R
:3a       The sum of 1s in each column is equal to the sum of the indicators (Pred 3)
          %%%
=.        Assign values to the cells of the list of lists which satisfy the constraints
:4aR,     The blocks of 1s must match the indicators on rows
.z        Transpose
:4aC,     The blocks of 1s must match the indicators on columns

Predicate 1: Forces the rows to have a specific length, and that each cell is 0 or 1.
tL,       L is the length given as second element of the input
?he       Take an element from the list
##ElL,    That element E is itself a list of length L
E:2a      The elements of E are 0s and 1s (Pred 2)

Predicate 2: Constrain a variable to be either 0 or 1
.<2,      Input = Output < 2
_1<       Output > -1

Predicate 3: The sum of 1s in a list must be equal to the sum of indicators (e.g. if the indicator is [3:1] then the list must have sum 4)
:+a       Sum the elements of the list and sum the indicator
#=,       Both sums must be equal
?h        Output is the list

Predicate 4: Check that blocks of 1s match the indicator
@b        Split the list in blocks of the same value
:5f       Find all blocks of 1s (Pred 5)
:la       The list of lengths of the blocks results in the indicator (given as output)

Predicate 5: True for blocks of 1s, false otherwise
e.        Output is an element of the input
  h1,     Its first value is 1

Feels like the perfect tool for the job. Looking forward to the explanation.

@Fatalize This is fantastic, I was waiting for someone to use a prolog-esque language to do this. Have you tried it with the 25x25 case? I entered the data for you already

@gowrath I will run this on my computer this afternoon, we'll see what happens.

@Fatalize Seems to time out but I may be doing it wrong. I wouldn't completely rely on my data entry skills either :D

@gowrath It times out on TIO, but I will run it on the offline interpreter directly on my computer.

@gowrath The second version still hasn't solved the big case after a few hours. The big problem is that I have no idea how to express the idea of blocks of 1 separated by at least one zero with constraints.

@Fatalize I could try and help out but your code is elvish to me :D. I'm a humble C/Python programmer.

You can add efficiency by summing a row's clues and adding x-1 where x is the number of clues for that row. If that number equals the width of the board, then the solution of that row is known independently of the other rows/columns. Do the same for columns. See the 4th row from the bottom of the bonus challenge.

To make this a lot more efficient, try the CLP(FD) constraint automaton/3. All it takes is to build a finite state machine that accepts the suitable number of consecutive ones and zeros between states.

@mat Well, I can do my method on paper. :)

@mat I will look into adding this to Brachylog, this seems like a useful constraint predicate to have.

Haskell, 242 230 201 199 177 163 160 149 131 bytes
import Data.Lists
m=map
a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b]
g=m$list[0]id.m sum.wordsBy(<1)

Finally under 200 bytes, credit to @Bergi. Huge thanks to @nimi for helping almost halving the size.
Wow. Almost at half size now, partly because of me but mainly because of @nimi.
The magic function is (#). It finds all solutions of a given nonogram.
This is able to solve all cases, but may be super slow, since it's complexity is about O(2^(len a * len b)). A quick benchmark revealed 86GB allocated for a 5x5 nonogram.
Fun fact: It works for all nonograms, not only square ones.

How it works:

a#b: Given lists of lists of integers which represent the number of squares, generate all grids (map(chunk$length b).mapM id$a>>b>>[[0,1]]) and filter the results to keep only the valid ones.
g: Given a potential nonogram it sums the runs of 1's horizontally.

You mean O(2^(len a * len b)), not O((len a * len b)^2).

@AndersKaseorg Right. Keep the million I accidentally implied there. :D

Another few bytes: m(chunk$l b) and replicate(l$a>>b)

@ThreeFx 86GB :O... Btw could you briefly explain how to compile this? I only just started learning haskell and this is giving errors with ghc. Wanna test it out :)

@gowrath What errors are you getting? You need to install the Haskell Platform which is the de facto standard distribution since it comes with many useful packages.

@ThreeFx Nvm I figured it out (y). This is a fantastic solution! Can you make it feasibly work for the 25x25?

@gowrath Not in that size, you'd need wayy more optimization.

import Data.Lists is enough, because it re-exports both Data.List and Data.List.Split.

@nimi Wow that is huge. Thanks!

@nimi [0,1]<$a>>b doesn't work...

Let us continue this discussion in chat.

@ThreeFx: Did you see my latest suggestions on chat?

@nimi Yes I did but unfortunately didn't have time. I'll look at it this evening (EST).

Pyth, 91 72 71 bytes
D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb

A program that takes input of a list of the form [size, [horizontal clues], [vertical clues]] where each clue is a list of integers (empty clues are the empty list, []), and prints every solution, newline separated, in the form of a binary grid where 1 is shaded and 0 is unshaded.
This is a brute force, so is roughly O(2^n^2). It starts taking a very long time for larger puzzles, but will solve any arbritrary size given sufficient time.
Try it online
How it works
The program generates every possible layout by taking the repeated Cartesian product of [0, 1] with a length equal to size^2. This is then split into chunks, giving a list for each horizontal line. Each line is run-length encoded, filtered by the presence of 1 and flattened, leaving the clue for that line. This is then checked against the input. The above process is repeated for the transpose of the chunks, checking the vertical lines. If there is a hit, each chunk is concatenated, and the concatenated chunks are joined on newlines and implicitly printed, with a trailing newline.
D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb  Program. Input: Q
                            hQ                                           Q[0], size
                           ^  2                                          Square
                        ,01                                              [0, 1]
                       ^                                                 Cartesian product
                      V                                     )            For N in the Cartesian product:
                                 cNhQ                                    Split N into Q[0] chunks
                               =T                                        Assign that to T
                                     =Y1                                 Y=1
                                        VhQ                              For H in range [0, Q[0]-1]:
D:GHd                                                                     def :(G, H, d)
                   rH8                                                     Run-length-encode(H)
               f.)T                                                        Filter by presence of 1 in character part
            .nC                                                            Transpose and flatten, giving the clue
       @@QdG                                                               Q[d][G], the relevant input clue
     Rq                                                                    Return clue==input clue
                                               :H@TH1                     :(H, T, 1)
                                                     :H@CTH2              :(H, transpose(T), 2)
                                           =*Y*                           Y=Y*product of above two
                                                             IY           If Y:
                                                                 mjkdT     Conacatenate each element of T
                                                               jb          Join on newlines
                                                                      b    Add a newline and implicitly print

Thanks to @Pietu1998 for some tips

This may be the longest Pyth program I've ever seen

=ZhZ is equal to =hZ, and FN is equal to V.

@TheBikingViking What exactly do you mean given sufficient time? I'm fairly sure this wouldn't solve a 25x25 by now if you had started it from the conception of the universe.

@gowrath I'm also fairly sure of that! I am new to Pyth, and after the length of time this took me, I don't even want to consider trying to implement a better algorithm

Javascript (ES6), 401 386 333 bytes
This is an early attempt. It's not very efficient but I was curious to test a solution using regular expressions on the binary representation of the rows and columns.
For example, it will translate the clue [3,1] into the following regular expression:
/^0*1{3}0+1{1}0*$/

Right now, this version is not taking square clues into account. I will probably add this later.
Code
(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

Output
The solution is displayed in binary format. Such as:
00110
01110
11100
11101
00001

Test
This is a simple test on the example grid.

let f =
(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

console.log(f(
  [[2],[3],[4],[2],[2]],
  [[2],[3],[3],[3,1],[1]]
));

nice idea. kills my browsers on the christmas puzzle, though.

Haskell, 109 bytes
Disclaimer: this is derived from @ThreeFx's answer. I helped him to golf down his answer but he seems to have lost interest to include my last substantial improvements, so I post them as new answer.
import Data.List
n=mapM id
a#b=[x|x<-n$(n$" #"<$a)<$b,g x==a,g(transpose x)==b]
g=map$max[0].map length.words

Usage example: [[2],[3],[3],[3,1],[1]] # [[2],[3],[4],[2],[2]] -> [["  ## "," ### ","###  ","### #","    #"]].
Brute force. Try all combinations of  and #, split int chunks of #, count the lengths and compare to the input.

PHP, 751 833 (720) 753 724 726 710 691 680 682 bytes
I was eager to build a specialised sequence increment and try my cartesian generator once more;
but dropped the cartesian in favour of backtracking to solve the large puzzle faster.
$p=[];foreach($r as$y=>$h){for($d=[2-($n=count($h)+1)+$u=-array_sum($h)+$w=count($r)]+array_fill($i=0,$n,1),$d[$n-1]=0;$i<1;$d[0]+=$u-array_sum($d)){$o=$x=0;foreach($d as$i=>$v)for($x+=$v,$k=$h[$i];$k--;)$o+=1<<$x++;if(($s[$y]|$o)==$o){$p[$y][]=$o;$q[$y]++;}for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);if(++$i<$n)for($d[$i]++;$i--;)$d[$i]=1;}}
function s($i,$m){global$c,$w,$p;for(;!$k&&$i[$m]--;$k=$k&$m<$w-1?s($i,$m+1):$k){for($k=1,$x=$w;$k&&$x--;){$h=$c[$x];for($v=$n=$z=$y=0;$k&&$y<=$m;$y++)$n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];if($k&$v)$k=$n<=$h[$z];}}return$k?is_array($k)?$k:$i:0;}
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));

expects hints in arrays $r for row hints, $c for column hints and $s for square hints.
throws invalid argument supplied for foreach if it finds no solution.
to get the correct byte count, use a physical \n and remove the other two line breaks.

description
1) from row hints
generate possible rows that satisfy the square hints
and remember their counts for each row index.
2) backtrack over the row combinations:
If the combination satisfies the column hints,
      seek deeper or return successful combination,
else try next possibility for this row
3) print solution

The last golfing had severe impact on the performance;
but I removed profiling assignments for the final benchmarks.
Replace $n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];
with if(($p[$y][$i[$y]]>>$x&1)-$v){$k=($v=!$v)||$n==$h[$z++];$n=1;}else$n++;
to undo the last golfing step.
examples
For the small example (17 to 21 around 12 8 7 6.7 5.3 ms), use
$r=[[2],[3],[3],[3,1],[1]];$c=[[2],[3],[4],[2],[2]];$s=[0,0,0,0,0];

for the christmas puzzle:

killed my small home server with the old solution
killed the browser with test outputs
now solved in 50 37.8 45.5 around 36 seconds

put data from question to a file christmas.nonogram and use this code to import:
$t=r;foreach(file('christmas.nonogram')as$h)if('-'==$h=trim($h))$t=c;elseif('#'==$h){$t=s;$f=count($h).b;}else
{$v=explode(' ',$h);if(s==$t)for($h=$v,$v=0,$b=1;count($h);$b*=2)$v+=$b*array_shift($h);${$t}[]=$v;}

breakdown
$p=[];  // must init $p to array or `$p[$y][]=$o;` will fail
foreach($r as$y=>$h)
{
    // walk $d through all combinations of $n=`hint count+1` numbers that sum up to $u=`width-hint sum`
    // (possible `0` hints for $h) - first and last number can be 0, all others are >0
    for(
        $d=[2-
            ($n=count($h)+1)+               // count(0 hint)=count(1 hint)+1
            $u=-array_sum($h)+$w=count($r)  // sum(0 hint) = width-sum(1 hint)
        ]                           // index 0 to max value $u-$n+2
        +array_fill($i=0,$n,1)      // other indexes to 1
        ,$d[$n-1]=0;                // last index to 0
                                    // --> first combination (little endian)
        $i<1;   // $i:0 before loop; -1 after increment; >=$n after the last combination
        $d[0]+=$u-array_sum($d) // (see below)
    )
    {
        // A: create row (binary value) from 1-hints $h and 0-hints $d
        $o=$x=0;
        foreach($d as$i=>$v)
            for($x+=$v,$k=$h[$i];$k--;)
                $o+=1<<$x++;
        // B: if $o satisfies the square hints
        if(($s[$y]|$o)==$o)
        {
            $p[$y][]=$o;    // add to possible combinations
            $q[$y]++;       // increase possibility counter
        }
        // C: increase $d
            // find lowest index with a value>min
                // this loop doesn´t need to go to the last index:
                // if all previous values are min, there is nothing left to increase
        for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);
        if(++$i<$n)             // index one up; increase $d if possible
            for($d[$i]++        // increase this value
            ;$i--;)$d[$i]=1;    // reset everything below to 1
            // adjust $d[0] to have the correct sum (loop post condition)
    }
}

// search solution: with backtracking on the row combinations ...
function s($i,$m)
{
    global $c,$w,$p;
    for(;
        !$k // solution not yet found
        &&$i[$m]    // if $i[$m]==0, the previous iteration was the last one on this row: no solution
            --;     // decrease possibility index for row $m
        $k=$k&$m<$w-1? s($i,$m+1) : $k      // if ok, seek deeper while last row not reached ($m<$w-1)
    )
    {
        // test if the field so far satisfies the column hints: loop $x through columns
        for($k=1,$x=$w;$k&&$x--;)   // ok while $k is true
        {
            $h=$c[$x];
            // test column hints on the current combination: loop $y through rows up to $m
            for($v=$n=$z=   // $v=temporary value, $n=temporary hint, $z=hint index
                $y=0;$k&&$y<=$m;$y++)
                // if value has not changed, increase $n. if not, reset $n to 1
                // (or 0 for $k=false; in that case $n is irrelevant)
                $n=$n*
                    // $f=false (int 0) when value has changed, true (1) if not
                    ($f=($p[$y][$i[$y]]>>$x&1)==$v)
                    +$k=$f?:    // ok if value has NOT changed, else
                        ($v=!$v)        // invert value. ok if value was 0
                        || $n==$h[$z    // value was 1: ok if temp hint equals current sub-hint
                        ++]             // next sub-hint
                ;
            // if there is a possibly incomplete hint ($v==1)
            // the incomplete hint ($n) must be <= the next sub-hint ($c[x][$z])
            // if $n was <$h[$z] in the last row, the previous column hints would not have matched
            if($k&$v)$k=$n<=$h[$z];
        }
        // ok: seek deeper (loop post condition)
        // not ok: try next possibility (loop pre condition)
    }
    return$k?is_array($k)?$k:$i:0;  // return solution if solved, 0 if not
}

// print solution
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));

The large example kills my small home server (500 - Internal Server Error). The combinations are ready after 15 secons, but the cartesian product has 1.823E+61 members. (The 7th and 22nd row only have one solution btw.) Algorithm must be improved.

I think this could be sped up if you used recursive backtracking. Nevertheless, great work!

@gowrath: backtracking gives a bit and even saves bytes ... integer with bit arithmetics give about 50% speed but increases the size (have to find out yet how much it exactly costs) ... I´m still on it.

@gowrath: I chased my bug down; it was in the increment (where else?): $d has to be in correct order for foreach