text:
Ambiguous Roman Numeral Magic Squares
The king of Ancient Rome is having difficulties determining if a magic square is valid or not, because the magic square he is checking does not include any separators between the numbers. He has hired a software engineer to help him determine if a magic square is valid or not.
Input Description
Input comes in on STDIN or command line arguments. You cannot have the input pre-initialised in a variable (e.g. "this program expects the input in a variable x"). Input is in the following format:
<top>,<middle>,<bottom>

Each of <top>, <middle>, and <bottom> is a string that will only ever contain the uppercase characters I, V, and X. It will not contain spaces or any other characters. Each string represents three Roman numerals, thus resulting in a 3x3 matrix of numbers. However, these Roman numerals may (but not necessarily) be ambiguous. Allow me to illustrate this with an example. Consider the following example row of three Roman numerals, with no spaces between each number:
IVIIIIX

Because there are no spaces between the letters, there are two possibilites to the numbers here:

1, 8, 9 (I VIII IX)
4, 3, 9 (IV III IX)

When you consider that all three rows of the matrix can be ambigious, there is the potential for there to be many different 3x3 matrixes from a single input.
Note that sequences such as 1, 7, 1, 9 (I VII I IX) are not possible because each row will always represent three Roman numerals. Also note that the Roman numerals must be valid, so sequences such as 1, 7, 8 (I VII IIX) are also not possible.
Output Description
Output:

An integer A, where A is the number of unique 3x3 matrixes that can be formed from the ambigious input, and:
A truthy value if any of the unique 3x3 matrixes form a magic square, or:
A falsy value if none of the unique 3x3 matrixes form a magic square.

The truthy and falsy values must be consistent. They are seperated by a comma.
Some explanation is required on what is counted as unique. As long as a matrix does not have exactly the same numbers in exactly the same positions as a previously found matrix, it is counted as unique. This means that reflections, etc. of previously found matrixes are counted as unique.
Example Inputs and Outputs
In these examples, I use true as my truthy value and false as my falsy value.
Input: VIIIIVI,IIIVVII,IVIXII
Output: 24,true
(The magic triangle is 8-1-6, 3-5-7, 4-9-2.)
Input: IIIXVIII,IVIII,VIIII
Output: 210,false
Extras

You are not allowed to use inbuilt Roman Numeral conversion functions if your chosen language has one.

"king of Ancient Rome" ... Emperor?

@DigitalTrauma It's set in an alternate universe where Ancient Rome had a king, magic squares, and software engineers. Or something like that...

Also, you should use an interpunct (·) instead of a comma (http://en.wikipedia.org/wiki/Interpunct#Latin)

I have "24, true" for the first, but "210, false" for the second example. I'll investigate.

@coredump The reason for the difference in answers is due to a bug in my reference program I used to generate the sample inputs and outputs. I'll fix the original post in accordance.

What is the range of roman numerals that needs to be considered?

@MickyT All roman numerals that can be created with the characters I, V, and X. So from 1 (I) to to 39 (XXXIX).

@DigitalTrauma Rome had kings until about 509BC.

Perl, 219 237
Line breaks added for clarity.
#!perl -p
%x=(I,1,IV,4,V,5,IX,9,X,10);
$a="(X{0,3}(?:V?I{1,3}|I?V|IX)|X{1,3})"x3;
m*^$a,$a,$a$(?{
  @z=map"$$_",0..9;
  $r|=!grep$x-$_,map{$x=eval s/./ $z[$&]/gr=~s/IX|IV|\S/+$x{$&}/gr}123,456,789,147,258,369,159,357;
  ++$-
})^*;
$_="$-,$r"

Test me.

Prolog - 686
:-lib(util),lib(sd). r(S,R):-string_list(S,L),g(L,R). g(L,[N1,N2,N3]):-append(L1,X,L),append(L2,L3,X),n(L1,N1),n(L2,N2),n(L3,N3). n([73,86],4). n([73,88],9). n([73,73,73],3). n([73,73],2). n([73],1). n([86],5). n([86|N],D):-n(N,E),E<4,D is E+5. n([88|N],D):-n(N,E),D is E+10. n([88],10). m(M,[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3]):-split_string(M,",","",[X,Y,Z]),r(X,[X1,X2,X3]),r(Y,[Y1,Y2,Y3]),r(Z,[Z1,Z2,Z3]). a(L):-alldifferent(L),L=[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3],l(X1,X2,X3,T),l(Y1,Y2,Y3,T),l(Z1,Z2,Z3,T),l(X1,Y1,Z1,T),l(X2,Y2,Z2,T),l(X3,Y3,Z3,T). l(A,B,C,T):-T is A+B+C. p:-read_line(S),findall(L,m(S,L),A),length(A,C),findall(L,(member(L,A),a(L)),B),(B=[_|_]->R=true;R=false),writeln((C,R)).

Ungolfed
% I : 73
% V : 86
% X : 88
:-lib(util).
:-lib(sd).
r(S,R) :- string_list(S,L), g(L,R).
g(L,[N1,N2,N3]):-
    append(L1,X,L),
    append(L2,L3,X),
    n(L1,N1),n(L2,N2),n(L3,N3).
n([73,86],4).
n([73,88],9).
n([73,73,73],3).
n([73,73],2).
n([73],1).
n([86],5).
n([86|N],D):-n(N,E),E<4,D is E+5.
n([88|N],D):-n(N,E), D is E+10.
n([88],10).
m(M,[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3]) :-
    split_string(M,",","",[X,Y,Z]),
    r(X,[X1,X2,X3]),
    r(Y,[Y1,Y2,Y3]),
    r(Z,[Z1,Z2,Z3]).
a(L) :-
    alldifferent(L),
    L=[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3],
    l(X1,X2,X3,T),
    l(Y1,Y2,Y3,T),
    l(Z1,Z2,Z3,T),
    l(X1,Y1,Z1,T),
    l(X2,Y2,Z2,T),
    l(X3,Y3,Z3,T).
l(A,B,C,T):-T is A+B+C.
p :- read_line(S),
     findall(L,m(S,L),A),
     length(A,C),
     findall(L,(member(L,A),a(L)),B),
     (B=[_|_]->R=true;R=false),
     writeln((C,R)).

Of course, p could also be defined as:
p :- read_line(S),
     findall(L,m(S,L),A),
     length(A,C),
     findall(L,(member(L,A),a(L)),B),
     writeln(C),
     B=[_|_].

In that case, the environment would say 'Yes' or 'No' after writing the number of squares.
Example
Using eclipse.
[eclipse 105]: p.
 VIIIIVI,IIIVVII,IVIXII
24, true

[eclipse 106]: p.
 IIIXVIII,IVIII,VIIII
210, false

Example results for the second one are pasted here.

Haskell, 451 429 423 bytes
import Data.List
(#)=splitAt
(%)=map
w=length
r"X"=10
r('X':a)=10+r a
r a=case elemIndex a["I","II","III","IV","V","VI","VII","VIII","IX"]of Just i->i+1;_->0
s l=[r%[a,b,c]|x<-[2..w l],y<-[1..x],let(d,c)=x#l;(a,b)=y#d,r a*r b*r c>0]
e[a,b,c]=a==b&&a==c
p[l,m,n]=[1|a<-l,b<-m,c<-n,e$sum%[a,b,c],e$sum%(transpose[a,b,c])]
f i=(show$product$w%(s%i))++","++(show$0<(w$p$s%i))
q ','='\n'
q a=a
i=getLine>>=putStrLn.f.lines.map q

Usage:
*Main> i                           -- repl prompt, call i
VIIIIVI,IIIVVII,IVIXII             -- input via STDIN
24,True                            -- output
*Main> i
IIIXVIII,IVIII,VIIII
210,False

About 70 bytes just to get the input and output format right.
The function r converts a roman number (given as a string) to an integer (if it's not a valid roman number 0 is returned). s splits a string of roman digits into 3 substring and keeps those triples with valid roman numbers and converts them via r to integers . e checks if all integers of a three element list are equal. p takes three strings of roman digits, splits them via s into lists of integers, combines one integer of each list to triples and keeps those with equal sums in all directions. f calculates the number of valid matrices and checks if p returns the empty list (no valid solution) or not (valid solution exists). The main function i reads the input from STDIN, converts it to a list of strings (q helps by replacing , with \n) and calls p.

Python, 442 chars
R=range
L=len
S=sum
N={}
for i in R(40):
 r="";j=i
 while j>9:r+="X";j-=10
 if j>8:r+="IX";j-=9
 if j>4:r+="V";j-=5
 if j>3:r+="IV";j-=4
 N[r+"III"[:j]]=i
a,b,c=map(lambda x:sum([[Z]*all(Z)for i in R(L(x))for j in R(L(x))for Z in[map(N.get,(x[:i],x[i:j],x[j:]))]],[]),raw_input().split(","))
print L(a)*L(b)*L(c),any(S(x)==S(y)==S(z)==S(q[::3])==S(q[1::3])==S(q[2::3])==S(q[::4])==S(q[2:-1:2])for x in a for y in b for z in c for q in[x+y+z])

The code first builds N which is a mapping from roman numeral string to its value for all possible numbers we might need.  Splits each line into three in every possible way and checks which of the resulting triples all have mappings in N.  The final any sees if any combination is a magic square.

R, 489 474 464
This got a lot bigger than I wanted, but I suspect I can golf it down a bit.
It uses a brute force method, by calculating all the possible Roman Numeral combinations and their corresponding digits.
Once that is done it compares the input to the Roman Numeral list and gets the possible digits.
From there it goes through each matrix of numbers and test for the magic square, finally outputting the result.
s=strsplit;e=expand.grid;P=paste0;d=do.call;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[n];p=d(P,e(r,r,r));n=d(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=F;N=nrow(C);for(n in 1:N){T=matrix(strtoi(unlist(C[n,])),nr=3);E=E||length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1};P(N,',',any(E))

Test Run.  It waits for input once pasted into the RGui.
> e=expand.grid;l=length;s=strsplit;P=paste0;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[-40];p=do.call(P,e(r,r,r));n=do.call(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=c();N=nrow(C);for(n in 1:N){T=matrix(as.integer(unlist(C[n,])),nr=3);E=c(E,length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1)};paste(N,',',any(E))
VIIIIVI,IIIVVII,IVIXII
[1] "24 , TRUE"
> e=expand.grid;l=length;s=strsplit;P=paste0;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[-40];p=do.call(P,e(r,r,r));n=do.call(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=c();N=nrow(C);for(n in 1:N){T=matrix(as.integer(unlist(C[n,])),nr=3);E=c(E,length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1)};paste(N,',',any(E))
IIIXVIII,IVIII,VIIII
[1] "210 , FALSE"
>


text:
Tetris Tangrams
Introduction
Tangrams are a classic puzzle involving arranging/fitting blocks into various shapes.  From the Chinese 七巧板 - literally meaning "seven boards of skill".  Let's take this idea and use the seven Tetrominos pieces to fill a grid.
Challenge
Write a function or program that takes an array of grid coordinates as input, and outputs a completed 10 by 20 grid filled with Tetris pieces except in the specified coordinates.
Optimize your score by attempting to keep the distribution of pieces uniform.
Criteria
Use this pastebin of coordinates to accomplish your task.  There are five sets of coordinates.  Feel free to modify the format in which the coordinates are written, but not the values.
Data set #2 cannot be solved - in this case, simply output the grid with input cells filled in (i.e., X's where the holes are).
Input
Grid coordinates represent 'holes' in the grid.  These are cells which cannot contain any part of a Tetromino.
Grid coordinates:
(0,0), (1,0), (2,0), ... (9,0)
(0,1), (1,1), (2,1), ... (9,1)
.
.
.
(0,19), (1,19), (2,19), ... (9,19)

Use your programming language's array style of choice to input the coordinates.

Represent holes in the grid with an X or other printable ASCII.

Output
Using a standard Tetris grid size of 10 cells wide by 20 cells tall, print a solution grid if and only if the grid can be filled completely and perfectly using Tetromino pieces.
Pieces constructed with letters I, O, L, J, T, Z, S as follows:
I
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

Example
Output solution example with no input coordinates:
ZZIIIILLLI
JZZTTTLLLI
JJJSTLOOLI
SZZSSLOOLI
SSZZSLLJJI
TSOOSLLJII
TTOOSSLJII
TZOOSSLZII
ZZOOSSZZII
ZJJJJSZLLI
TTTJJOOILI
ITZJJOOILI
IZZTTTLIII
IZOOTZLIII
IJOOZZLLII
LJJJZSSTII
LLLTSSTTTI
LLLTTSSZJI
OOLTSSZZJI
OOIIIIZJJI

With distribution as follows:
I
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

11   6     8     6      6     7      6

Notes
Coordinates represent a single X and Y position on the grid.  The grid is 0 based, meaning coordinate (0,0) should either be the top left or the bottom left cell, author's choice.
Bricks can:

be selected at author's discretion.
be rotated as author sees fit.
be placed on the grid anywhere at author's discretion (aka: no Tetris gravity)

Bricks cannot:

be placed outside the bounds of the grid.
overlap an existing brick or hole in the grid.
be a non-standard Tetris tetromino piece.

Scoring
Your score is in the format:
( 1000 - [bytes in code] ) * ( M / 10 + 1 )
Where M is a multiplier for the distribution of pieces used in your solution sets.
Highest score by the Ides of March wins.
To calculate M, add the lowest individual tetromino distribution value for each set and then take the average rounded down to calculate M.
For example:
Set 1: 5
Set 2: 4
Set 3: 5
Set 4: 6
Set 5: 3

6 + 4 + 5 + 4 + 4 = 21 / 5 = 4.6
So you would use 4 as your M value.
Note: If a set has no solution, do not factor that set into calculating M, since it would have no tetromino distribution.

Improving questions after they are posted is generally difficult, because if the changes are substantial they will invalidate work of people who have already started working on the problem (or worse, even posted the result). I would recommend posting challenge ideas in the sandbox. That is the place to ask for feedback and polish the spec before it goes on main. That being said, after a quick skim, I didn't see any glaring problems with your challenge.

@MartinBüttner Duly noted, thanks for the feedback.

Ides of March = 15 of March. I had to look that up.

I've made some small changes to front-load the task description, because otherwise it's impossible to understand what we're being asked to do on the first read-through. I think it would be an improvement if you stated which of the input cases can't be solved, so that they function as test cases in addition to a scoring dataset.

@PeterTaylor Fair enough, I've added which solution set cannot be solved.  Thanks for the feedback.

Are there any standard algorithms for solving this kind of problem?

Python 3, 819 bytes, M=0, Score=181
This is a brute force DFS program. It builds a numpy array, and inserts all the inputted holes. It then takes the leftmost unfilled tile on the highest row that has one, and places a tetromino. Recursively, we now do it again - when we can't either we found a solution, or we backtrack and try another piece at the first opportunity.
This has an M of 0, since it tries to use pieces in a determined order, and almost always finds a solution without the last one in the list. I tried using a randomly ordered list each cycle to make a more even distribution, but I only got an M of 2, which wasn't worth the bytes required to import random.shuffle.
I can't comment the below code, since in my golfing I've long forgotten what much of it does. The general idea:

Import numpy and itertools product, with 1-letter names
Rename some builtins to be 1-letter functions, and define a lambda to save bytes
Build the array of possible tetrominos as numpy nd-arrays, all rotations included
In the recursive function:

Get the position of the unfilled tile desired, and cycle through the pieces list
For each piece, cycle through translations of it (moving it up and down)
If something doesn't work (piece goes off the board, hits another piece, hits a hole, etc.), try the next translation or the next entire piece
If it works, great. Try it, then recursively call the function.
If that path didn't work, it will return 'a', so we just try again. If it did work, it returns the board, and we pass it up the line.

Finally, the program. We build the 10x20 board as a numpy array of 1's.
The input is of the form (x1, y1);(x2,y2);... We put a 9 for each hole in it, then get the result of running the function on it.
The print statement then displays either the successful result or the empty, original board line by line, substituting the appropriate letters or symbols for the numbers.

import numpy as n
from itertools import product as e
m,s=range,len
p=[n.rot90(a,k)for a,r in[([[2,2]]*2,1),([[3]*3,[1,3,1]],4),([[0]*4],2),([[1,1,6],[6]*3],4),([[7,1,1],[7]*3],4),([[4,4,1],[1,4,4]],2),([[1,5,5],[5,5,1]],2)]for k in m(r)]
o=lambda a:e(m(s(a)),m(s(a[0])))
def t(l,d=0):
	g=list(zip(*n.where(l==1)))[0]
	for a in p:
		for u,v in o(a):
			w,x=l.copy(),0
			for r,c in o(a):
				if a[r,c]!=1:
					i,j=g[0]+r-u,g[1]+c-v
					if any([i<0,i>19,j<0,j>9])or l[i,j]!=1:
						x=1
						break
					w[i,j]=a[r,c]
			if x==0:
				if len(w[w==1]):
					f=t(w,d+1)
					if type(f)==str:continue
					return f
				return w
	return'a'
b=n.ones((20,10))
b[list(zip(*[eval(k)[::-1]for k in input().split(';')]))]=9
a=t(b)
for r in(a,b)[type(a)==str]:
	print(''.join(map(dict(zip([0,2,3,4,5,6,7,9,1],'IOTZSLJX-')).get,r)))

Try it online!
Sample test:
In: (1,1);(8,1);(4,4);(5,8);(4,11);(5,15);(1,18);(8,18)
Out:
IIIIOOOOLL
TXOOOOOOXL
TTOOOOOOTL
TOOIOOOOTT
TOOIXOOTTI
TTTITOOTTI
TTTITTTTII
OOTTTTTTII
OOTTTXOOII
TTTTOOOOII
TTTTOOOOII
TTTTXTOOII
ITTTTTTTII
ITTTTTTTII
IITTTLLTTI
IITOOXLTTI
IITOOTLTTI
IITTLTTTTI
IXTLLTJTXI
ILLLLLJJJI

Oh my - this is amazing.  Thanks for the wonderful write up, and nice work!

source: Stack Exchange

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

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

sort: votes


text:
Build a Twitter-quine
A short while, ago, @daniel_ernston sent the following challenge to @StackCodeGolf on Twitter:

@StackCodeGolf Your task is to build a program that uses the API of your choice to tweet its own source code. Shortest code wins, of course.

What about reading the source code and other quine cheats?

All permissible. I want to see how short you can get it, and I have a suspicion it may not be possible if I don't open those up.

If you can come up with a solution that doesn't use that cheat, though, then by all means I'll give you an honourable mention (and maybe even a bounty).

Hm, won't this depend quite heavily on the chosen user name and credentials? (Both whether it fits in the tweet and the actual score.)

The challenge was written to be novel, not completely fair. However, I suppose you could create a throwaway account.

I don't have a twitter account and while I could create one, I have to give them my phone number to get an api key, maybe someone could post api keys from a throwaway account for everyone to use. This would also make the challenge fairer  since they would be the same length.

JavaScript, 38 characters
window.open("http://tinyurl.com/erjk34");

Here is the tweet, in all its glory: https://twitter.com/kevinaworkman/status/575425948562014209
And here is my previous entry at 95 characters:
function q() {
window.open("https://twitter.com/intent/tweet?text="+encodeURIComponent(q+";{q();}"));
};{q();}

And if that's not cheating...
HTML, 22 characters
http://tinyurl.com/erjk35

It this what was meant by tweeting or was it referring to the REST API https://dev.twitter.com/rest/public?

@Maltysen It sends a tweet, so I'm counting it as fair game. It might be cheating, but hey, OP said that cheating was allowed! :p

Okay then, +1 for loopholes.

I specifically said "the API of your choice", so this is okay. However, in order to count for this challenge, you will need to actually use your code to make a Twitter post, then link to it here.

@JoeZ Done and done, and cheated even more.

I don't know much about Processing, but with vanilla JS you can remove the semicolon and window. because functions are automatically executed on the window object. You can also safely remove the https: protocol, leaving //tinyurl.... You'll have to regenerate the url, though.

@hsl processing.js comes with the benefit of running without boilerplate, so I'll keep the semicolon instead. Good call with the // though.

Well, uh, the TinyURL should post the tweet entirely by itself, without requiring you to press the "Tweet" button...

...although I understand that may not be possible for security reasons.

@JoeZ. I went into this knowing that it was probably cheating- especially my last update, haha. I just figured it would be fun to try, especially since you didn't have any answers after 3 days!

This does not actually tweet its entire source code; the link shortener's expansion of the shortened link is also source code.

For instance, this isn't considered a real quine: cat a, where a is just a text file containing the text cat a. (In that case, both the command and the file's contents are source code of the program, so the program needs to separately output the command and the contents of the file)

@AJMansfield That doesn't make any sense. Are you saying you have to export the code for System.out.println() if you print your quine to the console? Also, see the above "cheating is okay" rule, where your example of reading from a file would be acceptable. But more to the point: this was supposed to be ridiculous, so just have fun with it.

@KevinWorkman No, because the implementation of System.out.println is part of the corpus of library code, not application code written for the purpose of the hypothetical quine. I am assuming, of course, that you did in fact create the link shortener redirection you are using - if that link was an existing link shortening that you found and are reusing, that would be a perfectly valid zeroth-order quine.

@AJMansfield Eh, I think you're splitting hairs. The Windows machine I'm running on is also closed-source. Does that mean any quine that runs on it is invalid? I'm not saying my quine is valid, but I don't think I agree with your reasoning. Besides that, the OP specifically said that cheating was allowed and that you could do stuff like read from files, which is usually not "allowed" in quines. Either way, I'm sticking with my "this was supposed to be ridiculous" defense! :p

Also, you're saying that it would be fine if I "found" the shortened link, but not if I created it? That doesn't make much sense either. So if I had a partner who created the link for me, this would be okay? Again, I'm not saying this is the most honest or fair quine ever, but I don't agree with your logic here.

@KevinWorkman I have created a question on meta with regards to this: http://meta.codegolf.stackexchange.com/q/4877/7981

Let us continue this discussion in chat.

I am very sure you can take out window. Also, use a better/golfier URL shortener.

Python 2, 118 bytes
import webbrowser,urllib
webbrowser.open("https://twitter.com/intent/tweet?text="+urllib.quote(open(__file__).read()))

(Can't) Try it online! (Run locally)
¯\_(ツ)_/¯

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


text:
Writing code for three tasks
When you run your program first, it should print an integer sequence.  The
second run should print the 'Mary had a little lamb' song. The third run should
produce an ASCII image file.
Scoring
Your score will be the sum of your bytes of code and any file content at the
start of each of the 3 runs. Lowest score wins.
For example, myprog is 1500 bytes and does not change its size, but writes a 4
bytes file each run so it knows what to do on the next run. The score would be
1500 + (1500+4) + (1500+4) = 4508.
Output
The first output is this sequence of 133 integers, separated by single spaces:
0 89 98 179 188 197 269 278 287 296 359 368 377 386 395 449 458 467 476 485
494 539 548 557 566 575 584 593 629 638 647 656 665 674 683 692 719 728
737 746 755 764 773 782 791 809 818 827 836 845 854 863 872 881 890 908
917 926 935 944 953 962 971 980 1079 1088 1097 1169 1178 1187 1196 1259
1268 1277 1286 1295 1349 1358 1367 1376 1385 1394 1439 1448 1457 1466 1475
1484 1493 1529 1538 1547 1556 1565 1574 1583 1592 1619 1628 1637 1646 1655
1664 1673 1682 1691 1709 1718 1727 1736 1745 1754 1763 1772 1781 1790 1808
1817 1826 1835 1844 1853 1862 1871 1880 1907 1916 1925 1934 1943 1952 1961
1970

The second output is this text exactly (including capitals, punctuation, and
white space - the inconsistent punctuation is intentional):
Mary had a little lamb,
Little lamb, little lamb,
Mary had a little lamb,
Its fleece was white as snow

And everywhere that Mary went,
Mary went, Mary went,
Everywhere that Mary went
The lamb was sure to go

It followed her to school one day
School one day, school one day
It followed her to school one day
Which was against the rules.

It made the children laugh and play,
Laugh and play, laugh and play,
It made the children laugh and play
To see a lamb at school

The third output is this image in PPM ASCII(P3) format left in a file called
blue.ppm. This is the image in PNG format:

The PPM file should look something like this:
P3 50 50 255
255 255 255 255 255 255 255 255 255 255 255 255 ...
...
255 255 255

There is a copy of the full PPM file here.
Example run (on Linux)
# ls
myprog
# interpreter myprog
0 89 98 179 188 197 269 278 287 296 359 ...
# interpreter myprog
Mary had a little lamb,
Little ...
# interpreter myprog
# ls
blue.ppm
myprog
# cat blue.ppm
P3 50 50 255
255 255 255 255 255 ...

Rules

Your code may modify itself.
Running the program a fourth time is undefined behaviour.
You may write to a file in the current directory, but the size of this file
will add to your score at the start of each run. The final PPM file is
excluded from this.
The first two outputs are to stdout (or similar). The last output is written
to a file, with nothing sent to stdout.
The first two outputs may optionally have a trailing white space character (e.g. space or line feed).
You may not use compression or image libraries. You may use your own
compression or image functions but this code must be included in your program.
The standard loopholes are prohibited.

Great problem ! Learnt quite a few new things while solving it.

Does the PPM file need to have 256 color steps or should it just be able to generate the same image?

Does the image output file has to be exactly like the one mentioned in the question or can there be differences in whitespaces ? This is vital to my answer as I have taken special care that the newlines are inserted at the right place every time.

@Oberon and  Anmol Singh Jaggi, the PPM must be in P3 format and show the exact same picture as the PNG when viewed. The bit depth, internal white space is up to you, but it must be a valid file.

Python (897 + 814 + 386 = 2097)
Simple self-modifying answer. I'll have to refine the second run later.
def p(x):print x,
map(p,[0]+filter(lambda x:sum(map(int,`x`))==17,range(1971)))
#l="ittle lamb,";M="Mary ";w=M+"went";e="verywhere that "+w;s="chool one day";I="It followed her to s"+s+"\n";j="augh and play";i="It made the children l"+j;print M+"had a l"+l+"\nL"+l+" l"+l+"\n"+M+"had a l"+l+"\nIts fleece was white as snow\n\n"+"And e"+e+",\n"+w+", "+w+",\nE"+e+"\nThe lamb was sure to go\n\n"+I+"S"+s+", s"+s+"\n"+I+"Which was against the rules.\n\n"+i+",\nL"+j+", l"+j+",\n"+i+"\nTo see a lamb at school"
#print>>file("blue.ppm","w"),"P3 50 50 255"+' '.join(" %i"%(255-255*any(a<y<b and x==c or y==d and e<x<f for a,b,c,d,e,f in[(2,48,2,47,2,37),(9,48,36,9,27,37),(9,41,28,40,9,29),(0,41,10,1,9,49),(0,37,48,36,14,49),(2,37,15,3,2,16)]))*2+" 255"for x in range(50)for y in range(50))
import sys;x=file(sys.argv[0],"r+");y='#'.join(x.read().split('#')[1:]);x.seek(0);x.truncate();x.write(y)

Additionally, if run for the fourth time, it safely degrades to a NOP:
'.join(x.read().split('#')[1:]);x.seek(0);x.truncate();x.write(y)

That is going to be hard to beat. I was wondering when some sneaky self-modifying code would appear ;-)

Ruby, 1356 1268 * 3 = 3804 bytes
if File.file?(?b)
s='P3
50 50
255
'
d=e=0
[153,44,6,1,42,1,6,1,42,1,6,1,42,1,6,1,42,1,6,1,42,1,6,1,42,1,4,40,5,1,4,1,1,1,36,1,5,1,4,1,1,1,36,1,5,1,4,1,1,1,36,1,5,1,4,1,1,1,36,1,5,1,4,1,1,34,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,34,1,3,1,5,1,4,1,8,31,5,1,4,1,8,1,25,1,9,1,4,1,8,1,25,1,9,1,4,1,8,1,25,1,9,1,4,1,8,1,25,1,9,1,4,1,8,1,25,1,9,1,4,1,8,1,25,1,9,1,4,1,8,1,25,1,9,1,4,1,8,37,4,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,1,34,1,14,36,63].map{|n|n.times{s+=[" 255 255 255"," 0 0 255"][d];s+=$/if (e+=1)%50==0};d=1-d}
File.write 'blue.ppm',s
elsif File.file?(?a)
puts [["","Mary had a ","little lamb",?,,?,,"Its fleece was white as snow"],["And ","everywhere that ","Mary went",?,,'',"The lamb was sure to go"],["","It followed her to ","school one day",'','',"Which was against the rules."],["","It made the children ","laugh and play",?,,'',"To see a lamb at school"]].map{|a,b,c,d,e,f|[a+b+c+d,c.capitalize+', '+c+d,b.capitalize+c+e,f]*$/}*"

"
`touch b`
else
1971.times{|i|$><<"#{i} "if i.to_s.chars.map(&:to_i).reduce(:+)%17<1}
`touch a`
end

To keep track of the invocation, I'm creating an empty file a on the first run and an empty file b on the second run.

The first program uses a certain property of the numbers.
The second program uses a bunch of reusable parts of the verses, but that currently only saves 100 bytes over naively printing the entire thing.
The third program currently uses just a simple run-length encoding. I'll look into actually encoding the path of the line later.

Nice solution, especially the numbers (which is more of a math problem). You could save a few bytes if you replace i.to_s.chars.map(&:to_i).reduce(:+) with (j=i.to_s).sum-48*j.size

@blutorange Oh, that's neat. :) I still want to revisit the image generation. I'll work your suggestion into it when I do.

You only need to keep a part of your source file for the 2nd and 3rd runs but maybe it's not that much gain as the biggest part is part 3 currently. With run-length coding the run-length coded rows you could improve part 3 a lot.

Python 3, 1027 + 1028 + 1029 = 3084
0 or print('0 '+' '.join(str(i)for i in range(1971)if sum(map(int,str(i)))==17))
1 or print("""+$,
L$, l$,
+$,
Its fleece was white as snow

And e(@,
@, @,
E(@
The!was sure to go

#&
S&, s&
#&
Which was against the rules.

%l/,
L/, l/,
%l/
To see a!at school""".translate({43:'Mary had a l',36:'ittle lamb',40:'verywhere that ',64:'Mary went',35:'It followed her to s',38:'chool one day',47:'augh and play',37:'It made the children ',33:' lamb '}))
q=[153,44]+[e-63for e in b'E@i@E@i@E@i@E@i@E@i@E@i@CgD@C@@@c@D@C@@@c@D@C@@@c@D@C@@@c@D@C@@aB@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@a@B@D@C@G^D@C@G@X@H@C@G@X@H@C@G@X@H@C@G@X@H@C@G@X@H@C@G@X@H@C@G@X@H@C@GdC@a@M@a@M@a@M@a@M@a@M@a@M@a@M@a@M@a@M@a@M@a@Mc~?']
1 or open("blue.ppm","w").write("P3\n50 50\n255\n"+' '.join(q[r*2]*'255 255 255 '+q[r*2+1]*'0 0 255 'for r in range(140)).strip())
f=open(__file__);l=f.read();f.close();open(__file__,"w").write(l.replace("0 or","0 and",1).replace("1 or","0 or",1))

Uses OEIS A166370 for the numbers, some hand-written compression for Mary's Lamb and ASCII bytes to store the amounts of numbers in the PPM.
(Ab)uses Python's feature to only evaluate the second value for logical operators if the result is not known yet (short-circuiting): 1 or code and 0 and code do not evaluate code. Then uses some replacements to change the 0 or enabling code execution to a 0 and and the next 1 or to 0 or.
The 3rd execution kills the second replace, as there are no more 1 or's. The 4th execution kills the first replace, after which the code does basically nothing.

C++, 1204 * 3 = 3612 bytes
Compiler used - GCC 4.9.2 with -std=c++14 flag
#include<bits/stdc++.h>
int i,j,c;
using namespace std;int main(){fstream f("F"),g("G");if(!f){while(i<=1970){j=i,c=0;while(j)c+=j%10,j/=10;if(c==17||i==0)cout<<i<<" ";i++;}ofstream f("F");}else if(f&&!g){cout<<R"(Mary had a little lamb,
Little lamb, little lamb,
Mary had a little lamb,
Its fleece was white as snow

And everywhere that Mary went,
Mary went, Mary went,
Everywhere that Mary went
The lamb was sure to go

It followed her to school one day
School one day, school one day
It followed her to school one day
Which was against the rules.

It made the children laugh and play,
Laugh and play, laugh and play,
It made the children laugh and play
To see a lamb at school)";ofstream g("G");}else{ofstream F("blue.ppm");F<<"P3 50 50 ";vector<int> L={1,2,4,10,13,16,19,25,28,43,76,103,109,127,190,460};vector<string> R={"1","?","43","10","6","161=","1","14","39","10","4","1514121<","1","151412","33","10","12","1315141;","1","13151417","30","10","1","1514171","7",":1814171","36","01","1","41","11",";191","35","01","1",">"},C={"255","0"};string r;i=j=0;while(i<R.size()){stringstream S(R[i]);S>>c;while(c--)r+=R[i+1];i+=2;}i=0;while(i<r.size()){c=L[r[i]-48];while(c--){F<<C[j]<<" ";}j=1-j;i++;}}}

Explanation -:
#include<bits/stdc++.h>
using namespace std;

int main()
{
    fstream f( "F" ), g( "G" ); // Creating empty files so that the program can decide when to run which task

    /**************************** TASK 1 ****************************/

    if ( !f ) // Print all the numbers within the range whose sum of digits is 17
    {
        for ( int i = 0; i <= 1970; i++ )
        {
            int j = i, c = 0;
            while ( j )
            {
                c += j % 10, j /= 10;
            }
            if ( c == 17 || i == 0 )
            {
                cout << i << " ";
            }
        }
        ofstream f( "F" );
    }

    /**************************** TASK 2 ****************************/

    else if ( f && !g )  // Print the second task as it is using raw literals
    {
        cout << R"(Mary had a little lamb,
Little lamb, little lamb,
Mary had a little lamb,
Its fleece was white as snow

And everywhere that Mary went,
Mary went, Mary went,
Everywhere that Mary went
The lamb was sure to go

It followed her to school one day
School one day, school one day
It followed her to school one day
Which was against the rules.

It made the children laugh and play,
Laugh and play, laugh and play,
It made the children laugh and play
To see a lamb at school)";

        ofstream g( "G" );
    }

    /**************************** TASK 3 ****************************/

    else // Third task using Run-Length encoding
    {
        ofstream F( "blue.ppm" );
        F << "P3 50 50 ";

        /*
        L = set of all the lengths found during run-length encoding.
        R = vector containing the run-length encoding of "255" and "0" alternatingly.
                {1,"?") means 1 times print '255'/'0' "x" number of times where x = L[ASCII(?)-48] = L[15] = 469
        C = vector containing the two strings to be printed alternatingly.
        */

        vector<int> L = {1, 2, 4, 10, 13, 16, 19, 25, 28, 43, 76, 103, 109, 127, 190, 460};
        vector<string> R = {"1", "?", "43", "10", "6", "161=", "1", "14", "39", "10", "4", "1514121<", "1", "151412", "33", "10", "12", "1315141;", "1", "13151417", "30", "10", "1", "1514171", "7", ":1814171", "36", "01", "1", "41", "11", ";191", "35", "01", "1", ">"};
        vector<string> C = {"255", "0"};
        string r; // Contains the normal/expanded version of R
        i = j = 0;

        while ( i < R.size() ) // Expanding "R" into normal form and putting it into "r"
        {
            stringstream S( R[i] );
            S >> c; // Convert R[i] to its integer representation and put it in "c" with the help of stringstream.
            while ( c-- )
            {
                r += R[i + 1];
            }
            i += 2;
        }

        i = 0;
        while ( i < r.size() )
        {
            c = L[r[i] - 48];  // "c" is the number of times the current character has to be printed consecutively.
            while ( c-- )
            {
                F << C[j] << " ";
            }
            j = 1 - j; // Alternate "255" and "0"
            i++;
        }
    }
}

PHP (1552*3)+2 = 4658
There is A LOT of golfing that can be made.
The code writes 1 byte into another file called z, to check the status.
Here is the code:
<?$Y=base64_decode;$Z=gzdecode;$r=file_put_contents;switch(include z){case 2:$M=Mary;$l=lamb;$L=ittle;$H="$M had a l$L $l,";echo"$H
L$L $l, l$L $l,
$H
Its fleece was white as snow
";$W="$M went";$H="verywhere that $W";echo"
And e$H,
$W, $W,
E$H
The $l was sure to go
";$S=chool;$O="$S one day";$I="
It followed her to s$O";echo"$I
S$O, s$O$I
Which was against the rules.";$L="augh and play";$I="
It made the children l$L";echo"$I,
L$L, l$L,$I
To see a $l at s$S";$r(z,3);break;case 3:$r($Z($Y("H4sIAAAAAAAAA+3ay63CMBSE4X2qSAkRKH3QfzXAmkf8mBOfiX9dRXcBfIJ47Ewwj/uyb+u+Lbd9fx+r4gACAgICApoO2l5/Jf+X0icCfT4gG7ka0DSQQMdPOopB9bv5BpqeG6D2F8tjQK6AImJAroAiYkCugCJiQK6AemKQ51bWF+oaxe6Rk2DhAQUKjIIEIU9Xg8gTkBIiT0BKKG+e8nXMcVBRDFr3oyQIq4ADVLW1JNnfbEYkafYcJR+oatZLtrebEfluPVAAVDNKkn3yZoQfazhAvXkaW4WNTvQkEIUcSAlRyIGUEIUcSApRyIGUEIUcSAlRyIGUEIUcSAlRyH+/w/H7qudDXUHMf+nhpq4NGlM28196KOFtx5iy6XPpyTdiyaEhZdPg3p0S3gaN+baOAnVViAKV6bz4QxSoTOflAhAF6v95yfdVTT7otOEPCSNQ+Sgl/1jc9RhAhrOfux8HyG/2Gy6xE0J+v+AyXGInhAxnv98SOyFkOPspWA6Q3+w3XGInhChYQBGQ4ez3W2InhAxnPwXLAfKb/RfYvQqH8o0aENBJ0BPXPoC/PXEAAA==")),'blue.ppm');$r(z,1);break;default:echo$Z($Y("H4sIAAAAAAAAAxXSuQHAMAwCwFUYIehF+y8WXCWWaDj7gw4ncA+Uv7eIOcQKIf/fIPuQI+QuUj5fo+pQLdQsagclz67QeegSuhc9g95Gy/NLTBwmhanF9GCmMVsYeXeB5WFD2FxsDbYbO4XdxMr7I/QdREGxUA5UDXVBk9AGJGfuw33CcXExuGxcFa4TN4FbuvIHfq/091p/rk26N+nipN7R1RnuznB5htsz9GbuzzQA0wJMEzBtwNRbWIFlBpYdWIZgWYJlCpbe1hhsa7DNwbYH2yBsi7BNwtaLGIVjFY5ZOHbhGIZjGY5pOLbh6OWswzUPl+8+DcS1ENdEXBtxjcS1kku+sJ0oQ1GWokxF2YoyFmUtylzG4HsbDt/n3NG5C+cunbty7tq5G7738/3WJLxlVAIAAA=="));$r(z,2);}

I know that this is a VERY horrible code and I can try to golf the list.
But hey, I can't find a pattern on those :/

I can see that you have compressed the image in the last line, and minimised the size of the lamb song on the other lines, but I can't see where the integer sequence is. I need some guidance.

@CarpetPython More compression. It's the last part.

Thanks. If your are looking for the pattern in the integer sequence, some of the other answers may give you some clues. eg: the digits of the numbers have an interesting property.

@CarpetPython I'm not a copy-cat. But I did took a look at the other answers, but still couldn't find the pattern.

Ruby, 691+612+225 = 1528 bytes
Another self modifying answer, this time in ruby. I just bumped into this yesterday and the compressing of the poem caught my eye. I was only able to save 92 bytes off the raw text thought.
puts (0..1970).select{|i|eval(i.to_s.gsub /\B/,'+')%17<1}*' '
File.write $0,%@
m='lamb:little 0,:Mary :2had a 1:2went:laugh and play:It made the children 5:It followed her to 10: was : that :11 one day:school:everywhere:3
1 1
3
Its fleece8white as snow

And 1294,
4, 4,
1294
The 08sure to go

7
10, 10
7
Which8against the rules.

6,
5, 5,
6
To see a 0 at 11'
12.downto(0){|i|m.gsub! i.to_s,m.split(':')[i]}
puts m.split(':')[13].gsub /^./,&:upcase
File.write $0,%!a=[1]
s=[16,13]
File.write 'blue.ppm',(' P3
50 50 '+[460,a*43,[19,127]*6,13,a*39,[s,4,109]*4,s,4,a*33,10,s,[103,10,s]*12,25,a*30,s,25,[76,28,13,25]*7,a*36,13,[103,43]*11,a*35,190].flatten.map{|i|('255 '*i)+'0 0 '}*' ')[1..-6]!@

Each run of the program rewrites the program for the next run. I didn't figure out the special property of the numbers until looking over the other answers. And did take same inspiration Martin's answer but I didn't use the suggestion from blutorange because I couldn't figure out why it worked.
There is probably a few more bytes to scavenge from the poem but not much. It is basically just subbing in common sequences and is using the order of the sequence as the part to replace.
For the final part I length encoded all of the 255 bytes into an array and glued them together with the zeros. And then I encoded the repeating sequences in that array.

JavaScript + HTML, 3909 bytes
This is a HTML/JavaScript application that uses page reload to rerun files. I goofed on parsing the PPM. If you know how to read PPM files, please let me know. Stack Exchange doesn't allow local-storage. So you will have to run the JSFiddle.
Again, I know I bombed the ppm file.
But in the end:
JavaScript: 1,232 bytes * 3 = 3696
HTML: 71 bytes * 3 = 213
Total: 3909
JSFiddle

var mary = '
\
Mary had a little lamb,
\
Little lamb, little lamb,
\
Mary had a little lamb,
\
Its fleece was white as snow
\

\
And everywhere that Mary went,
\
Mary went, Mary went,
\
Everywhere that Mary went
\
The lamb was sure to go
\

\
It followed her to school one day
\
School one day, school one day
\
It followed her to school one day
\
Which was against the rules.
\

\
It made the children laugh and play,
\
Laugh and play, laugh and play,
\
It made the children laugh and play
\
To see a lamb at school\
';
var img = ''

function run() {
  var step = localStorage.getItem("step");
  step++;
  localStorage.setItem("step", step);
  $('#step').text(step);
  var r = $('#results')
  switch (step) {
    case 1:
      for (var i = 0; i < 133; i++) {
        r.append(i + 1 + ' ');
      }
      break;
    case 2:
      r.html(mary);
      break;
    case 3:
      r.html(img);
      localStorage.setItem("step", 0);
      break;
    default:
      localStorage.setItem("step", 0);
      break;
  }
}
run();

Step:

Hi @Neoaptt and welcome to PPCG. You might need to read the question carefully to make sure your answer meets the requirements. Your integer sequence does not match the required sequence, and the image is not written to a file in PPM format. The point of the question is to challenge you to store the three outputs in a compressed way inside your program, by exploiting patterns. Also not that downloading files from the network is one of the 'standard loopholes' prohibited in the question.

You can read up on these loopholes at http://meta.codegolf.stackexchange.com/questions/1061/standard-loopholes-which-are-no-longer-funny.


text:
Find the maximum of ax+b
You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.
Your program or function must run in expected (to the randomness if your code involves that, not the input) O(nlogn) time where n is the total input length (sum or maximum of the lengths of both lists).
This is code-golf. Shortest code wins.
Example
[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]

Output:
[11 12 14 16 20]

Explanation:
11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0

Note about the complexity:
If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.
That means, if your program can be tested to be in O(nlogn), possibly with edge case exceptions because of the implementation of your language, but cannot be seen logically in your own code, we'll say it is O(nlogn).

It looks to me like the expected results should be [11 12 12 15 4]. ???

@BobJarvis It's the maximum of ax+b for the corresponding x, but for all (a,b) in the list. Changed to make the example less misleading.

total input length = length of (a,b) pairs plus length of array of x ?

@Optimizer Right.

Why is it clear that it is even possible in O(n log(n))? Can you provide a reference algorithm?

And how do we have to expect the numbers to be distributed?

@flawr Find the part of the convex hull of the points (a,b), from the topmost to rightmost point, and do binary search on the slope (or find the maximum for unimodal function) for each x.

@flawr You can assume each number is in a basic integer type. The "expected complexity" is for the randomness in your program, and it cannot depend on the input distribution.

Can we assume that X is sorted on input?

@KeithRandall No.

@user23013 The asympotic runtime of many algorithms depends on assumptions on the input distributions, thats why I am asking.

@flawr It's basically just the worst-case complexity allowing the randomized quicksort (and things likely).

@user23013 Then please change that in the question, because you wrote the expected complexity should be O(n log(n)) =)

@flawr What I get from this page is that "average-case complexity" is usually for the average input, and "expected complexity" is for the randomness. If I misstood that, I'm not sure what term to use then.

Well, seeing the history, that line is just edited to the Wikipedia page recently. Edited and tried to not mention that. And I'm a bit confused...

You want expected complexity.  Expected over the random choices of the algorithm, not over any input distribution.

@KeithRandall Rollbacked the edit...

Pyth - 99 98 bytes
This is pretty much a direct translation of @KeithRandall's Python answer. It can definitely be golfed a lot more. I will be posting an explanation soon.
K[_1Z;FNShQAkdNW&>K2>+*k@K_3d+*@K_2@K_3eK=K<K_3)~K[c-eKd-k@K_2kd;FNSeQW&>K2>N@K2=K>K3)aY+*hKN@K1;Y

Takes two comma delimited lists, separated by commas through stdin.
Try it here
K                  K=
 [  )              A List containing
  _1               Negative 1
  Z                Zero
FN                 For N in
 ShQ               Sorted first input
Akd                Double assign k and d
 N                 To N
 W                 While
  &                Logical And
   >K2             K>2
   >               Greater Than
    +*k@K_3d       K[-3]*k+d
    +              Plus
     *@K_2@K_3     K[-2]*K[-3]
     eK            K[-1]
  =K               K=
   <K_3            K[:-3]
  )                Close while loop
 ~K                K+=
  [      )         List constructor
   c               Float division
    -              Minus
     eK            K[-1]
     d             d
    -              Minus
     k             k
     @K_2          K[-2]
   k               k
   d               d
 ;                 End list and for loop
FN                 For N in
  SeQ              Sorted second input
  W                While loop
   &               Logical and
    >K2            K[2:]
    >              Greater than
     N             N
     @K2           K[2]
   =K              K=
   >K3             K[3:]
  )                Close while loop
  aY               Y.append - Y is empty list
   +               Plus
    *hKN           (K+1)*N
    @K1            K[1]
;                  Close out everything
Y                  Print Y

Python, 214 bytes
S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b>H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x>H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R

Computes the convex hull by iterating through the input a,b in increasing a order.  The convex hull is recorded in H using the format -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn where xi is the x coordinate of the intersection of a{i-1},b{i-1} and ai,bi.
Then I iterate though the input xs in sorted order, truncating the convex hull to keep up as I go.
Everything is linear except for the sorts which are O(n lgn).
Run it like:
>>> print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}

@user23013: fixed

@KeithRandall In the last step, you search in H linearly for each x in X, don't you?. Isn't it possible that we have O(n^2) complexity when both lists have the same length?

@coredump: I search H linearly for each x, but because I do the xs in order I remember where the last search stopped and start the next search there.  So the inner while loop can execute at most O(n) times across all x (even though it might execute O(n) times for any individual x).

@coredump: Note that the same thing happens for the inner while loop in the first for loop.

@KeithRandall I missed that, thanks. Clever!

That's a really nice trick!

Haskell, 204 271 bytes
Edit: golfed much further by updating the convex hull as a list (but with the same complexity as the ungolfed version), using "split (x+1)" instead of "splitLookup x", and removing all qualified function calls like Predule.foldl.
This creates a function f which expects the list of (a,b) pairs and a list of x values.
I guess it will be blown away length-wise by anything in the APL family using the same ideas, but here it goes:
import Data.Map
r=fromListWith max
[]%v=[(0,v)]
i@((p,u):j)%v|p>v#u=j%v|0<1=(v#u,v):i
(a,b)#(c,d)=1+div(b-d)(c-a)
o i x=(\(a,b)->a*x+b)$snd$findMax$fst$split(x+1)$r$foldl'(%)[]$r$zip(fmap fst i)i
f=fmap.o

Sample usage:
[1 of 1] Compiling Main             ( linear-min.hs, interpreted )
Ok, modules loaded: Main.
λ> f [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] [1..5]
[11,12,14,16,20]
λ> f [(1,20), (2,12), (3,11), (4,8)] [1..5]
[21,22,23,24,28]

It works in O(n log n) time; see below for analysis.
Edit: Here's an ungolfed version with the big-O analysis and a description of how it all works:
import Prelude hiding (null, empty)
import Data.Map hiding (map, foldl)

-- Just for clarity:
type X = Int
type Y = Int
type Line = (Int,Int)
type Hull = Data.Map.Map X Line
slope (a,b) = a

{-- Take a list of pairs (a,b) representing lines a*x + b and sort by
    ascending slope, dropping any lines which are parallel to but below
    another line.

    This composition is O(n log n); n for traversing the input and
    the output, log n per item for dictionary inserts during construction.
    The input and output are both lists of length <= n.
--}
sort :: [Line] -> [Line]
sort = toList . fromListWith max

{-- For lines ax+b, a'x+b' with a < a', find the first value of x
    at which a'x + b' exceeds ax + b. --}
breakEven :: Line -> Line -> X
breakEven p@(a,b) q@(a',b') = if slope p < slope q
                                 then 1 + ((b - b') `div` (a' - a))
                                 else error "unexpected ordering"

{-- Update the convex hull with a line whose slope is greater
    than any other lines in the hull.  Drop line segments
    from the hull until the new line intersects the final segment.
    split is used to find the portion of the convex hull
    to the right of some x value; it has complexity O(log n).
    insert is also O(log n), so one invocation of this
    function has an O(log n) cost.

    updateHull is recursive, but see analysis for hull to
    account for all updateHull calls during one execution.
--}
updateHull :: Line -> Hull -> Hull
updateHull line hull
    | null hull = singleton 0 line
    | slope line <= slope lastLine = error "Hull must be updated with lines of increasing slope"
    | hull == hull' = insert x line hull
    | otherwise = updateHull line hull''
    where (lastBkpt, lastLine) = findMax hull
          x = breakEven lastLine line
          hull' = fst $ x `split` hull
          hull'' = fst $ lastBkpt `split` hull

{-- Build the convex hull by adding lines one at a time,
    ordered by increasing slope.

    Each call to updateHull has an immediate cost of O(log n),
    and either adds or removes a segment from the hull. No
    segment is added more than once, so the total cost is
    O(n log n).
--}
hull :: [Line] -> Hull
hull = foldl (flip updateHull) empty . sort

{-- Find the highest line for the given x value by looking up the nearest
    (breakpoint, line) pair with breakpoint <= x.  This uses the neat
    function splitLookup which looks up a key k in a dictionary and returns
    a triple of:
        - The subdictionary with keys < k.
        - Just v if (k -> v) is in the dictionary, or Nothing otherwise
        - The subdictionary with keys > k.

    O(log n) for dictionary lookup.
--}
valueOn :: Hull -> X -> Y
valueOn boundary x = a*x + b
    where (a,b) = case splitLookup x boundary of
                    (_  , Just ab, _) -> ab
                    (lhs,       _, _) -> snd $ findMax lhs

{-- Solve the problem!

    O(n log n) since it maps an O(log n) function over a list of size O(n).
    Computation of the function to map is also O(n log n) due to the use
    of hull.
--}
solve :: [Line] -> [X] -> [Y]
solve lines = map (valueOn $ hull lines)

-- Test case from the original problem
test = [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] :: [Line]
verify = solve test [1..5] == [11,12,14,16,20]

-- Test case from comment
test' = [(1,20),(2,12),(3,11),(4,8)] :: [Line]
verify' = solve test' [1..5] == [21,22,23,24,28]

Common Lisp - 648 692
With an actual binary search.
(use-package :optima)(defun z(l e)(labels((i(n m)(/(-(cadr m)(cadr n))(-(car n)(car m))))(m(l)(match l((list* a b c r)(if(<(i a b)(i b c))(list* a(m(list* b c r)))(m(list* a c r))))(_ l)))(f(x &aux(x(cdr x)))`(+(*,(car x)x),(cadr x)))(g(s e)(let*((q(- e s))(h(+ s(floor q 2)))d)(if(> q 1)(let((v(g s h))(d(pop l)))`(if(< x,(car d)),v,(g(1+ h)e)))(cond((not(car (setq d (pop l))))(f d))((> q 0)`(if(< x,(car d)),(f d),(f(pop l))))(t(f d)))))))(setq l(loop for(a b)on(m(remove-duplicates(#3=stable-sort(#3# l'< :key'cadr)'< :key'car):key 'car)) by #'cdr collect`(,(when b(i a b)),(car a),(cadr a))))`(mapcar(eval(lambda(x),(g 0(1-(length l)))))',e)))

(z '((2 8) (4 0) (2 1) (1 10) (3 3) (0 4)) '(1 2 3 4 5))
=> (11 12 14 16 20)

Explanation
Let n be the length of (a,b) and k the length of points.

sort (a,b) by a, then b - O(n.ln(n))
remove entries for duplicate a (parallel lines), retaining only the parallel line with the maximum b, which is always greater than the other (we prevent  divisions by zero when computing intersections) - O(n)
compress the result - O(n) : when we have consecutives elements (a0,b0) (a1,b1) (a2,b2) in the sorted list, such that the intersection point of (a0,b0) and (a1,b1) is greater than the one of (a1,b1) and (a2,b2), then (a1,b1) can safely be ignored.
build a list of (x a b) elements, where x is the value up-to-which line ax+b is maximal for x (this list is sorted by x thanks to previous steps) - O(n)
given that list, build a lambda that perform an interval check for its input and computes the maximum value - the binary tree is built in O(n) (see https://stackoverflow.com/a/4309901/124319). The binary search that will be applied has O(ln(n)) complexity. With the example input, we build the following function (that function is then compiled):
(LAMBDA (X)
  (IF (< X 4)
      (IF (< X 2)
          (IF (< X -6)
              (+ (* 0 X) 4)
              (+ (* 1 X) 10))
          (+ (* 2 X) 8))
      (+ (* 4 X) 0)))

apply that function for all elements - O(k.ln(n))

Resulting complexity: O((n+k)(ln n))) in a worst-case scenario.
We can't provide a complexity estimate for the total number of inputs (n+k), because k and n are independant.
For example, if n is asymptotically negligeable w.r.t. k, then the total complexity would be O(k).
But if we suppose that k=O(n), then the resulting complexity is O(n.ln(n)).
Other examples
(z '((1 10) (1 8) (1 7)) '(1 2 3 4 5))
=> (11 12 13 14 15)

And if we move backquotes to see what is being computed, we can see that we don't even need to make any comparison (once the first list is preprocessed):
(MAPCAR (LAMBDA (X) (+ (* 1 X) 10)) '(1 2 3 4 5))

Here is another example (taken from a comment):
(z '((1 20) (2 12) (3 11) (4 8)) '(1 2 3 4 5))
=> (21 22 23 24 28)

The effective function:
(MAPCAR
  (LAMBDA (X)
    (IF (< X 4)
        (+ (* 1 X) 20)
        (+ (* 4 X) 8)))
  '(1 2 3 4 5))

O(n log n + k) is of course in O((n+k) log (n+k)).

Which interpreter are you using? Ideone gives (LIST* A B C R) should be a lambda expression.

@user23013 Sorry, I forgot to (use-package :optima)  (editing...)

@user23013 I'am afraid I can't make Ideone load an external library. For testing, please download SBCL (or maybe another, though I only tested on SBCL) and install quicklisp. Then, you can (ql:quickload :optima) to download and install optima. Finally, the code I provided should be evaluable.

It returned (MAPCAR (EVAL (LAMBDA (X) ... which evaluates to the answer. Did you left some debug code there?

@user23013 I moved the backquote in order to quote (mapcar(lambda ...)), (and we could call eval on that). Granted, this is not strictly equivalent, but I thought it would not be interesting, and slightly confusing, to explain this :-)

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

authors: Bob Jarvis - Слава Україні


text:
Digit sum of powers in bases
You should write a program or function which outputs or returns the sum of the digits in base b representation of the first n natural power of a in ascending order.
Example for a = 2, b = 3  and n = 4
The base10 numbers are 2^0, 2^1, 2^2 and 2^3.
Their base3 representations are 1, 2, 11, 22.
The digit sums are 1, 2, 2, 4.
The sorted digit sums are 1, 2, 2, 4 which is the result.

Input

3 integers a > 1, b > 1  andn > 0

Output

A list of integers

Examples
Input => Output
2 5 10 => 1 2 4 4 4 4 4 4 8 8
3 2 20 => 1 2 2 3 4 5 6 6 6 8 9 10 11 11 13 14 14 14 15 17
5 6 1 => 1
6 6 11 => 1 1 1 1 1 1 1 1 1 1 1
6 8 20 => 1 6 6 8 8 8 13 13 15 20 22 22 22 27 29 34 34 34 36 41
8 2 10 => 1 1 1 1 1 1 1 1 1 1
15 17 18 => 1 15 17 31 31 33 49 49 63 65 81 95 95 95 95 113 127 129

This is code-golf so shortest code wins.

Can I take a,b,n separated by newlines as input to my program?

@FryAmTheEggman Any reasonable input format is fine.

Pyth, 11
Smsj^vzdQvw

Note that this requires the inputs separated by newlines in the order a,b,n.
Try it online here
Pyth has built-ins that do each step for us. We map over each value from 0 to n-1, raising a to that power. Then we use j to convert each of these numbers to base b. We sum the resulting lists, and the final list of numbers is Sorted.
The input is read in the order z, Q then w. z and w have to be evaled in order to be used as numbers.

CJam, 13 bytes
q~,f#\fb::+$p

I think this can be improved, but lets get this started.
The input is in the following order : b a n
Example input:
3 2 4

Output:
[1 2 2 4]

Code expansion:
q~             "Read the input and parse it. Now we have on stack, b a and n"
  ,            "Get an array from 0 to n-1";
   f#          "Get all the powers of a present in the array, i.e. 0 to n-1";
     \         "Swap the array of a^i and bring the base on top";
      fb       "For each number in the array, convert it into its base representation array";
        ::+    "Calculate the sum of each of the sub arrays in the bigger array";
           $p  "Sort and print the sum of digits of base representation of n powers of a";

Try it online here

The browser version runs out of precision for the "15 17 18" test case.

@JohnE Did you input in the correct order? i.e. 17 15 18

Ah, you're right- does work as expected with that input format. My apologies.

JavaScript (ES6) 170 175 196 98 100
Edit New version, handles bigger numbers using digits array. Score almost doubled :-(
Multiplying digit by digit is more difficult, summing the digits is simpler.
F=(a,b,n)=>
  (t=>{
    for(r=t;--n;r[n]=s)
      for(k=1,y=t,z=a;z;z=z/b|0)
        t=[...t.map(v=>(v=c+(k?w*~~y[i++]+v:w*v),s+=d=v%b,c=v/b|0,d),
           w=z%b,s=c=0,i=--k),c]
  })([1])||r.sort((a,b)=>a-b)

Less golfed
F=(a, b, n) =>
{
  var r=[1]; // power 0 in position 0

  for(w=[]; w.push(a%b),a=a/b|0; ); // a in base b

  for(t = [1]; --n; )
  {
    // calc next power, meanwhile compute digits sum
    y=[...t]
    k=1
    w.map(w=>
      (t=[...t.map(v=>(
        v = c + (k?w*~~y[i++]+v:w*v),
        d = v % b, // current digit
        s += d, // digits sum
        c = (v-d)/b, // carry
        d)
       ,s=c=0,i=--k),c]
      )
    );
    r[n] = s // store sum in result array (positions n-1..1)
  }
  return r.sort((a,b)=>a-b) // sort result in numeric order
}

My first attempt using doubles, fails for big numbers.
JS doubles have 52 mantissa bits when for instance 15^14 needs 55 bits.
F=(a,b,n,r=[1])=>(x=>{for(;--n;r[n]=s)for(t=x*=a,s=0;t;t=(t-d)/b)s+=d=t%b})(1)
||r.sort((a,b)=>a-b)

Less golfed
F=(a, b, n) =>
{
  var r=[1]; // power 0 in position 0
  for(x = 1; --n; )
  {
    x *= a; // calc next power starting at 1
    for(t = x, s = 0; t; t = (t-d) / b) // loop to find digits
    {
      d = t % b;
      s += d;
    }
    r[n] = s // store sum in result array (positions n-1..1)
  }
  return r.sort((a,b)=>a-b) // sort result in numeric order
}

Test In Firefox/FireBug console
;[[2,5,10],[3,2,20],[5,6,1],[6,6,11],[6,8,20],[8,2,10],[15,17,18]]
.forEach(t=>console.log(...t,F(...t)))

2 5 10 [1, 2, 4, 4, 4, 4, 4, 4, 8, 8]
3 2 20 [1, 2, 2, 3, 4, 5, 6, 6, 6, 8, 9, 10, 11, 11, 13, 14, 14, 14, 15, 17]
5 6 1 [1]
6 6 11 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
6 8 20 [1, 6, 6, 8, 8, 8, 13, 13, 15, 20, 22, 22, 22, 27, 29, 34, 34, 34, 36, 41]
8 2 10 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
15 17 18 [1, 15, 17, 31, 31, 33, 49, 49, 63, 65, 81, 95, 95, 95, 95, 113, 127, 129]

Your last test case seems to be wrong...

I don't know JS, but probably can't handle big (15^17) integers.

@randomra maybe, but 15^17 is not so big

right, 15^17 is so big indeed, 63 bits. With double the limit is 52 (near 15^13)

A purely mathematical equation on the Cartesian Plane, written in LaTeX: Unknown size, incomplete
Demonstrated here:
https://www.desmos.com/calculator/svpkyarzxh
a, b, and n are adjustable inputs.
To avoid spaghetti code, it's split into two functions, although it could be condensed.
f\left(x\right)=\floor \left(x-\left(b-1\right)\sum _{i=1}^{\log _bx}\floor \left(xb^{-i}\right)\right)
y=f\left(a^{\floor \left(x\right)}\right)\left\{0<x\le n\right\}

I'm not sure how to put the values in an adjustable list or sort the list without using an actual programming language. However, the fact that this equation allows you to put it on a programmable graphing calculator and figure out the rest from there. I know it can be done in TI-BASIC, but I'm too busy to put an example here.

Mathematica, 43 41 bytes
Sort[Tr/@IntegerDigits[#^Range@#3/#,#2]]&

Very straightforward and apart from the slight abuse of Tr very readable. This is an unnamed function which is called with the three parameters in order.
Example outputs:
f=Sort[Tr/@IntegerDigits[#^Range@#3/#,#2]]&
f[2, 5, 10]
(* {1, 2, 4, 4, 4, 4, 4, 4, 8, 8} *)
f[3, 2, 20]
(* {1, 2, 2, 3, 4, 5, 6, 6, 6, 8, 9, 10, 11, 11, 13, 14, 14, 14, 15, 17} *)
f[5, 6, 1]
(* {1} *)
f[6, 6, 11]
(* {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} *)
f[6, 8, 20]
(* {1, 6, 6, 8, 8, 8, 13, 13, 15, 20, 22, 22, 22, 27, 29, 34, 34, 34, 36, 41} *)
f[8, 2, 10]
(* {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} *)
f[15, 17, 18]
(* {1, 15, 17, 31, 31, 33, 49, 49, 63, 65, 81, 95, 95, 95, 95, 113, 127, 129} *)

Two bytes saved thanks to alephalpha.

Martin can you post some example output? I trust Mathematica more than OP

Sort[Tr/@IntegerDigits[#^Range@#3/#,#2]]&

@alephalpha Ah, neat :)

@edc65 Added all the example outputs.

J - 19
/:~+/"1#.inv`(^i.)/

Takes numbers in that order: b a c
Usage example (x stands for extended precision):
   /:~+/"1#.inv`(^i.)/ 5 2 10
1 2 4 4 4 4 4 4 8 8
   /:~+/"1#.inv`(^i.)/ 17 15x 18
1 15 17 31 31 33 49 49 63 65 81 95 95 95 95 113 127 129

APL (Dyalog Unicode), 29 24 bytes
{(⊂∘⍋⌷⊢)+⌿⍵(⊥⍣¯1)∊*∘⍳/⍺}

-5 bytes from Jo King.
Takes inputs as a n function b.
Try it online!
{(⊂∘⍋⌷⊢)+⌿(⊃⌽⍵)(⊥⍣¯1)(⊃⍵)*⍳⍺}

Takes inputs as n function a b
Thanks to Jo King for helping me fix this answer.
Try it online!
Explanation
{(⊂∘⍋⌷⊢)+⌿(⊃⌽⍵)(⊥⍣¯1)(⊃⍵)*⍳⍺} ⍺ → n, ⍵ → [a,b]
                          ⍳⍺  range (1..n)
                     (⊃⍵)*    a to the power of the range
          (⊃⌽⍵)               take b from reverse of ⍵
               (⊥⍣¯1)         inverse encode(decode) using b till it reaches zero
        +⌿                    reduce with addition along non-leading axis
                              i.e: sum the columns
 (⊂∘⍋⌷⊢)                      tacit fn:
    ⍋                         Get indices for ascending order
     ⌷                        Get elements at those indices
      ⊢                       From the right arg
  ⊂                           Enclose it

Haskell, 79 bytes
import Data.Digits
import Data.List
f a b n=sort$map(sum.digits b.(a^))[0..n-1]

Usage: f 6 8 20, output: [1,6,6,8,8,8,13,13,15,20,22,22,22,27,29,34,34,34,36,41]
This is a typical Haskell function: straight forward, same as ungolfed version but the imports ruin the golf score: for every element e of the list from 0 to n-1 calculate a^e, convert to a list of base b digits and sum it. Sort the resulting list.

Jelly, 7 bytes
Ḷ*@b⁵§Ṣ

Try it online!
Takes input as 3 command line arguments, \$n\$, \$a\$ then \$b\$.
How it works
Ḷ*@b⁵§Ṣ - Main link. n on the left, a on the right and b as the 3rd argument
Ḷ       - Range [0, 1, ..., n-1]
 *@     - Take a to the power of each [1, a, ..., a^(n-1)]
    ⁵   - Yield b
   b    - Convert each power to base b
     §  - Take the digit sums of each
      Ṣ - Sort the digit sums

Husk, 13 bytes
OmoΣB²`z^R¹⁴ŀ

Try it online!
Explanation
OmoΣB²`z^R¹⁴ŀ
            ŀ range from 0..n-1
         R¹⁴  a replicated n times
      `z^     zip both with power
 moΣB²        convert each power to base n, and sum digits
O             Sort in ascending order


text:
Count Maximal Fence Arrangements
Background
I want to build a fence.
For that, I have collected a bunch of poles, and stuck them to the ground.
I have also collected lots of boards that I'll nail to the poles to make the actual fence.
I tend to get carried away when building stuff, and most likely I'll just keep nailing the boards to the poles until there's no more place to put them.
I want you to enumerate the possible fences that I can end up with.
Input
Your input is a list of two-dimensional integer coordinates representing the positions of the poles, in any convenient format.
You can assume that it contains no duplicates, but you cannot assume anything about its order.
The boards are represented by straight lines between the poles, and for simplicity, we only consider horizontal and vertical boards.
Two poles can be joined by a board if there are no other poles or boards between them, meaning that the boards cannot cross each other.
An arrangement of poles and boards is maximal if no new boards can be added to it (equivalently, there is either a pole or a board between any two horizontally or vertically aligned poles).
Output
Your output is the number of maximal arrangements that can be constructed using the poles.
Example
Consider the input list
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]

Viewed from the top, the corresponding arrangement of poles looks something like this:
  o
 o o
o    o
 o o
  o

There are exactly three maximal arrangements that can be constructed using these poles:
  o        o        o
 o-o      o|o      o-o
o----o   o||| o   o| | o
 o-o      o|o      o-o
  o        o        o

Thus the correct output is 3.
Rules
You can write either a function or a full program.
The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8

The example seems to have (-2,0) twice. Should one of those be (2,0)?

@isaacg Actually, it should be (0,-2), good catch. Changing now.

Mathematica, 301 bytes
(t~SetAttributes~Orderless;u=Subsets;c=Complement;l=Select;f=FreeQ;Count[s=List@@@l[t@@@u[Sort@l[Sort/@#~u~{2},!f[#-#2&@@#,0]&]//.{a___,{x_,y_},{x_,z_},b___,{y_,z_},c___}:>{a,{x,y},b,{y,z},c}],f[#,t[{{a_,b_},{a_,c_}},{{d_,e_},{f_,e_}},___]/;d<a<f&&b<e<c]&],l_/;f[s,k_List/;k~c~l!={}&&l~c~k=={},{1}]])&

This is an unnamed function which takes the coordinates as a nested List and returns an integer. That is, you can either give it a name and call it, or just append
@ {{3, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}

With indentation:
(
  t~SetAttributes~Orderless;
  u = Subsets;
  c = Complement;
  l = Select;
  f = FreeQ;
  Count[
    s = List @@@ l[
      t @@@ u[
        Sort @ l[
          Sort /@ #~u~{2},
          !f[# - #2 & @@ #, 0] &
        ] //. {a___, {x_, y_}, {x_, z_}, b___, {y_, z_}, c___} :>
              {a, {x, y}, b, {y, z}, c}
      ],
      f[
        #,
        t[{{a_, b_}, {a_, c_}}, {{d_, e_}, {f_, e_}}, ___]
          /; d < a < f && b < e < c
      ] &
    ],
    l_ /; f[
      s,
      k_List /; k~c~l != {} && l~c~k == {},
      {1}
    ]
  ]
) &

I can't even begin to express how naive this implementation is... it definitely couldn't be more brute force...

Get all (unordered) pairs of poles.
Sort each pair and all pairs into a canonical order.
Discard pairs which don't share one coordinate (i.e. which aren't connectible by an orthogonal line).
Discard pairs can be formed from two shorter pairs (so that o--o--o yields only two fences instead of three).
Get all subsets of those pairs - i.e. all possible combinations of fences.
Filter out combinations which have fences crossing each other.
Count the number of resulting fence sets for which no strict superset can be found in the list.

Surprisingly it does solve all the test cases virtually immediately.
A really neat trick I discovered for this is the use of Orderless to cut down on the number of patterns I have to match. Essentially, when I want to ditch fence sets with crossing fences, I need to find a pair of vertical and horizontal fence and check the condition on them. But I don't know what order they'll appear in. Since list patterns are normally order dependent, this would result in two really long patterns. So instead I replace with surrounding list with a function t with t @@@ - which isn't defined so it is held as it is. But that function is Orderless, so I can just check a single order in the pattern, and Mathematica will check it against all permutations. Afterwards, I put the lists back in place with List @@@.
I wish there was a built-in that is a) Orderless, b) not Listable and c) not defined for 0 arguments or list arguments. Then I could replace t by that. But there doesn't seem to be such an operator.

When you're thinking if Mathematica does it right or fast enough, the answer is "yes".

Well, that's about as naive as my reference implementation. :P

Haskell, 318 bytes
import Data.List
s=subsequences
k[(_,a,b),(_,c,d)]|a==c=f(\w->(1,a,w))b d|1<2=f(\w->(2,w,b))a c
f t u v=[t x|x<-[min u v+1..max u v-1]]
q l=nub[x|x<-map(k=<<)$s[a|a@[(_,n,m),(_,o,p)]<-s l,n==o||m==p],x++l==nubBy(\(_,a,b)(_,c,d)->a==c&&b==d)(x++l)]
m=q.map(\(a,b)->(0,a,b))
p l=sum[1|x<-m l,all(\y->y==x||x\\y/=[])$m l]

Usage: p [(1,0),(0,1),(-1,0),(0,-1)]. Output: 2
How it works:

create all sublists of the input list and keep those with two elements and with either equal x or equal y coordinates. This is a list of all pairs of poles where a fence can be build in between.
create all sublists of it
add boards for every list
remove lists where a x-y coordinate appears twice (boards and poles)
remove duplicate lists (boards only) to handle multiple empty lists, because of directly adjacent poles (e.g. (1,0) and (1,1))
keep those which are not a strict sublist of another list
count remaining lists


text:
Fractal Points on a Line
Sometimes, when I'm really bored (really bored), I like to draw a line segment and draw points on it.
First, I draw a line segment of a certain size, which is 2^N for some value of N.  The line will be represented by a series of . characters.
................

Then, I plot a point at the left end.  Points will be represented by X characters.
X...............

Then, I follow a pattern.  Starting at the most recently plotted point (which I'll call A), I advance to the next plotted point (B) on the line (wrapping around as necessary).  Then, I advance to the next plotted point on the line (C).  Then, I plot a new point half-way in between this third point (C) and the next already plotted point (D).
Whenever you wrap around the line, the "middle" is determined in wrapping manner.  The newly plotted point is always to the right of C.
Let's say that the following line was my current line.  Here is how I would plot the next two points.  For this example, I'll label each important point with a letter.
X...A...X.X...X.
    ^

X...A...B.X...X.
        ^

X...A...B.C...X.
          ^

X...A...B.C...D.
            ^

X...X...X.X.A.X.
            ^

X...X...X.X.A.B.
              ^

C...X...X.X.A.B.
^

C...D...X.X.A.B.
  ^

X.A.X...X.X.X.X.
  ^

Returning to the previous example, the next point will be plotted in the middle of the line.
X.......X.......

This is perhaps a little bit of a special case: advancing to the next point simply leaves you where you started.  The only useful halfway point is the "cyclic" halfway point (the halfway point on the line), as opposed plotting a point on top of itself.
Below is the series of points that I would plot on the line from here to the end.
X.......X.......
X.......X...X...
X.......X.X.X...
X...X...X.X.X...
X...X...X.XXX...
X.X.X...X.XXX...
X.X.X...XXXXX...

There is no longer any room to plot the next point, as it would have to be wedged between two adjacent points, so I have reached the maximum depth for the given value of N = 4.  The last line in the above list is "complete."
The Challenge
The goal is to write the shortest program/named function that will print/return the completed line for a given value of N.  The above shows N = 4.
Input
Input will be a single non-negative integer N.  The length of the generated line will then be 2^N.
Output
Output will be the completed line of length 2^N, formed by . and X characters.  A trailing newline doesn't matter.
Example I/O
0
X

1
XX

2
X.XX

3
X.X.XXX.

4
X.X.X...XXXXX...

5
X.X.X...X...X...X.XXX.XXX.......

Python 2, 137
n=input()
l=[0]*2**n;i=0
while~i%2:i=i/2%2**n;l[i]=1;i=sum([k for k,v in enumerate(l*4)if(k>i)*v][1:3])
print''.join(['.X'[x]for x in l])

Quite straightforward.
Pyth, 49
More or less a translation. Main difference is that I don't use a list representing the line, I use a string.
J*\.^2QW!%Z2K%/Z2lJ=JXJK\X=Zs<tf&q\X@JT>TKU*4J2)J

Try it online.
                         Q=input(); Z=0 #implicit
J*\.^2Q                  J = "."*(2^Q)
W!%Z2                    while !(Z%2):
  K%/Z2lJ                  K=(Z/2)%(len(J))
  =JXJK\X                  change J, the point at index K is changed to a "X"
       f          U*4J     filter all elements T in [0, 1, 2, ..., 4*len(J)-1]:
        &q\X@JT>TK           where J[T]=='X' and T>K
     <t               2    only us the second and third element
  =Zs                      and store the sum to Z
)J                       end while and print J

Clip, 95
[z?zF#2(z*2*:(#2(z'.'X]'X]]n[Fa[b[q[j[r?=rirFrsrb'X]b]][t[u+*<ut*Blb/+tu2]]g+2jqg+3jq]#qa]%b'X}

CJam, 55 53 51 50 bytes
2ri#:N'.*0aN{):U+__Nf++$_U#))>2<1bNe|2/N%|}*{'Xt}/

Something to start with.
Try it online here

GolfScript (61 bytes)
~2\?,[]0{.@|$4*.@?2+1$>2<.+~<!4$,*++.2/\1&!}do;`{&!'X.'1/=}+%

The number of loop iterations required seems to be A061419, but the do-loop is shorter than calculating that. A divmod would save a char inside the do loop. The part which feels most wasteful is the output conversion, but I don't see how to improve it.

Java, 209 207 195 191 bytes
I'm surprised I was able to get it this short. There is probably still room for improvement. As usual, suggestions will be appreciated :)
This returns a char[]. Call using a(n).
char[]a;int b,c,d,e=2;char[]a(int f){java.util.Arrays.fill(a=new char[b=1<<f],'.');for(a[0]=88;d+1<e;c=(d+e)/2,a[c%b]=88)e=b(d=b(b(c)));return a;}int b(int f){for(;;)if(a[++f%b]>87)return f;}

Indented:
char[] a;
int b, c, d, e = 2;

char[] a(int f){
    java.util.Arrays.fill(
            a = new char[
                    b = 1 << f
                    ]
            , '.'
    );
    for(
            a[0] = 88;
            d + 1 < e;
                c = (d + e) / 2,
                a[c % b] = 88
        )
        e = b(
                d = b(
                        b(c)
                )
        );
    return a;
}

int b(int f){
    for (;;)
        if (a[++f % b] > 87)
            return f;
}

12 bytes thanks to Peter :)
4 bytes thanks to TNT ;)

(c%b+b)%b? Are you expecting c to be negative?

c=0 and d=0 can be shortened to just c and d. int types defined at the class level are automatically initialized to 0.

Mathematica, 110 102 112 108
a=Array["."&,n=2^Input[]];a[[Mod[Round@{n/2,n}//.{x_,y_,z___}/;y-x>1:>{z,x+n,(x+y)/2+n,y+n},n]+1]]="X";""<>a

Haskell, 182 bytes
(a:b)%(c:d)|a<c=a:b%(c:d)|1<2=c:(a:b)%d
f i=putStr$map(!(0:g[0,n..]))[0..n-1]where n=2^i;e!l|e`elem`l='X'|1<2='.';g(_:_:c:d:r)|m==c=[]|1<2=mod m n:g((d:r)%[m,m+n..])where m=div(c+d)2

Usage: f 5. Output: X.X.X...X...X...X.XXX.XXX........
Unfortunately Haskell doesn’t have a merge function in the standard libraries, so I have to provide my own (-> %). Fortunately I have to merge only infinite lists, so I don’t have to cover the base cases, i.e. empty lists. It still costs 40 bytes.
How it works: instead of setting the Xs directly in an array, I keep a list of positions where they are. Furthermore I do not wrap around at 2^N but keep on increasing the positions towards infinity (e.g. for N=2 with an X at the front, the position list looks like [0,4,8,12,16,20,…]). I take the 3rd and 4th element (c and d), calculate the new position (c+d)/2, keep it for the output list, merge the old position list from position 4 (the d) on with a new one starting with (c+d)/2 and recur. I stop when (c+d)/2 equals c. Finally I add a 0 to the output list and print Xs at the given positions and . elsewhere.
step by step example, N=2

step  position list       (c+d)/2  output     lists to merge (pos. list for next round)
                                   list       old list from d on / new list from (c+d)/2

  #1  [0,4,8,12,16,…]       10     [10]          [12,16,20,24,…] / [10,14,18,22,…]
  #2  [10,12,14,16,18,…]    15     [10,15]       [16,18,20,22,…] / [15,19,23,27,…]
  #3  [15,16,18,19,20,…]    18

stop here, because c equals (c+d)/2

add 0 to the output list: [0,10,15]
take all elements modulo 2^N: [0,2,3]
print X at position 0, 2 and 3