text:
Print rotation-safe numbers
Background
You are working for some board-game manufacturer and need to produce wooden tiles with the numbers from 0 to n engraved on them for some game. However, without further ado, some tiles would become indistinguishable, e.g., 6 and 9. To avoid this, you have to equip numbers that can be confused with others (and only those) with a disambiguating dot, e.g., you would have tiles like 9. or 6089..
Unfortunately, you need to use some old, yet programmable wood-engraving device for this, whose interface is so broken that you have to encode every character of the program by hand in an unspeakably tedious process. Fortunately the device understands every existing programming language. Thus you are looking for the shortest program that prints such tiles.
Actual task
Write the shortest program that:

Takes a positive integer n as input. How the input is read is up to you.
Prints each of the numbers from 0 to n (0 and n included) exactly once in an order of your choice, separated by a single whitespace character (including newline). The numbers are to be printed without leading zeros.
Appends a dot (.) to every number that turns into another, valid number upon rotation by π (180 °), even if that number is larger than n. Your typeface’s 0 and 8 are rotation-symmetric and the 9 is a rotated 6. The 2 and 5 are distinct upon rotation; the 1 is not rotation-symmetric. Numbers with leading zeros are not valid.

Examples
Each of the following numbers has to be printed exactly this way:

2
4
5
6.
8
9.
16
60
66.
68.
69
906
909.
8088.
9806.
9886
9889.

Shouldn't the 60 be 60.?

@red-X "Numbers with leading zeros are not valid."

clarify "valid number", does it include only numbers from 0 to n? that is, does 6 need a dot if there's no 9 in the tileset? (thematically, it doesn't actually, and no board game or dice would put a dot on the 6 if 6 was the highest number)

I would specify "every known programming language" or similar condition, otherwise we may be tempted to define a new programming language in which only the empty program, which compiles to a solution of this exact problem, is valid.

@Sparr: I clarified (and I am pretty sure that there are board games, who did this, though I cannot specify one right now).

@rationalis: There is a standard loophole for this. (Also, this wouldn’t make sense thematically, as you have to teach that machine that language.) Either way, I added an existing.

@rationalis What generally happens is that only language versions existing prior to the posting of the challenge are eligible to be the winning program. Versions made after can still post for fun, but should specify in their post that they are not contending. So yes you can define such a language, but it'd be ineligible and most likely not well received due to being a standard loophole (as above).

Pyth - 34 38
VhQJ`N+J*\.&nJX_J`69`96&eN!-J"0689

I must give thanks to @Sp3000 for helping me remove 4 bytes. I originally had an additional check &@JK which made sure there was a 6 or 9 in the number, but after perusing the answers before posting, I read his answer and noticed that my identical translation and reversal already took care of that.
Also thanks to @isaacg for pointing out that strings are iterables, and you can use set operations on them. Also for making the current code ;)
Explanation:
                                    : (implicit) Q=eval(input())
VhQ                                 : for N in range(Q+1):
   J`N                              : J=str(N)
      +J*\.                         : J + "." * ...
           &nJX_J`69`96             : J!=translate(reversed(J),"69","96") and...
                       &eN          : N%10 and...
                          !-J"0689  : not(setwise_difference(J, "0689"))

I don't think you need to use lists of integers for K and J - just use strings instead. Switching K to 69 and J to N saves a few characters, as does inlining K in the resulting program. Shortest I could get under that technique was VhQJ``N+J*\.&nJX_J``69``96&eN!-J"0689, 34 characters. (Two backticks are really one.)

@isaacg Thanks for the tip! I think for some reason I forgot that making a string of numbers was really short in pyth by using `. Anyway, you can write a code block with backticks by escaping them with . For example: hell\o wo`rld`

In the explanation, you appear to have an extra _, before the \96`.

@isaacg Thanks, fixed

CJam, 46 44 43 42 bytes
l~),{_A%g1$s_6890s-!\_69s_W%erW%=!&&'.*N}/

I think there's some room for improvement.
Test it here.
Explanation
l~),{_A%g1$s_6890s-!\_69s_W%erW%=!&&'.*N}/
l~                                         "Read an eval input.";
  ),                                       "Get range from 0 to n.";
    {                                   }/ "For each...";
     _                                     "Get a copy of the integer.";
      A%g                                  "Ends with digit other than 0?";
         1$s_                              "Get another copy, convert to string, get a copy.";
             0689s-!                       "Contains rotation-safe digits?";
                    \                      "Swap with other copy.";
                     _                     "Get another copy.";
                      69s_W%er             "Swap 6 and 9.";
                              W%           "Reverse.";
                                =!         "Is different from original?";
                                  &&       "AND all three conditions.";
                                    '.*    "If true, push a period (else, an empty string).";
                                       N   "Push a newline.";

What does this return when the input is 8?  (I pasted the code in Input and then clicked on the Run button, but an error was called.)

@DavidCarraher put the code in "Code" and n in Input.

input 98, your program puts a dot next to 66, which is incorrect.

@Sparr You should wait for the OP to answer your question before saying an answer is invalid. His statement: "Each of the following numbers has to be printed exactly this way" seems to contradict your interpretation.

I like the beauty of CJam explanations.

How the f*ck did you learn Cjam? It looks like total gibberish.

@AlecTeal By reading the wiki and some trial and error. (As well as the occasional advice from other CJam users here on PPCG.)

You are amazing.

@FryAmTheEggman I actually posted this comment before asking OP for a clarification.

CJam, 46 45 43 42 bytes
ri){Is___69`96`erW%=!\6809`-!&IA%g&'.*N}fI

I think it can be golfed a little more.
Takes n from STDIN.
Try it online here

APL 66
∊' ',¨{a←⌽'0.....9.86'[⎕D⍳b←⍕⍵]⋄'.'∊a:b⋄('0'=⊃a)∨⍵=⍎a:b⋄b,'.'}¨0,⍳

Explanation:
¨0,⍳           applies the function to each number 0-n
a←⌽'0.....9.86'[⎕D⍳b←⍕⍵] inverts 6s and 9s, leaving 8s and 0s, and replacing other numbers with dots. Reverses vector after substitution.
'.'∊a          if there is a dot in the number....
('0'=⊃a)       .. or if the number starts with 0...
⍵=⍎a           or if the (inverted) number is the same as original
:b             then print the original number
b,'.'          else print a dot in the end
∊' ',¨        Finally to give the result in the asked format i add a single space after each result and join them all

Try it on tryapl.org
Note that in the online interpreter the ⍎ function doesn't work so i had to substitute it with 2⊃⎕VFI which does the same in this case, executes and returns the number, given a string.

Looks wrong: 60, 69, 90, and 96 must not have dots.

Thanks @ngn, I corrected it, I think it works correctly now.

Well done :) Instead of ⊃,/ or ,/ you can use an ∊ at the front.

Oh right! I don't usually work in ml1 so i forget about the ∊.

Perl 5, 53 bytes
say$_,"."x(!/[1-57]|0$/&&reverse!=y/96/69/r)for 0..<>

Online demo.
Uses the Perl 5.10+ say feature, so needs to be run with perl -M5.010 (or perl -E) to enable it.  (See this meta thread.)  Reads input from stdin, prints to stdout.

C#, 343 309 characters
Way too long, but anyway:
namespace System.Linq{class C{static void Main(){int n=int.Parse(Console.ReadLine());for(int i=0;i<=n;i++){var b=i+"";var c=b.Replace("6","9");Console.Write(b+(b.All(x=>x=='0'|x=='8'|x=='6'|x=='9')&!b.EndsWith("0")&!(b.Count(x=>x=='6')==b.Count(x=>x=='9')&new String(c.Reverse().ToArray())==c)?". ":" "));}}}}

How does it work? To add a period to the number, it must match the following requirements:

Consists only of 0, 8, 6 and 9.
Does not end with a zero.
Is not the same number when you rotate it:

If a number has an equal amount of 6s and 9s, and
if c = the number with all 6s replaces with 9s,
and reversed c == c,
then: the rotated number is the same as the number itself.

The numbers are separated by a space.
Code with indentation:
namespace System.Linq
{
    class C
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i <= n; i++)
            {
                var b = i + "";
                var c = b.Replace("6", "9");
                Console.Write(b +
                    (b.All(x => x == '0' | x == '8' | x == '6' | x == '9') &
                    !b.EndsWith("0") &
                    !(b.Count(x => x == '6') == b.Count(x => x == '9') &
                    new String(c.Reverse().ToArray()) == c) ? ". " : " "));
            }
        }
    }
}

My answer is longer ;)  I appear to be bowling on the golf course.

What about 8808? It doesn't have any 6s or 9s, but is 8088 when rotated.

@El'endiaStarman Thanks a lot! While fixing my submission, I actually saved characters :)

Python 2, 130 116 113 bytes
def f(n):S=`n`;n and f(n-1);print S+"."*all([n%10,set(S)<=set("0689"),(u""+S[::-1]).translate({54:57,57:54})!=S])

Defines a function f which prints the numbers to STDOUT, in ascending order.
This time I thought I'd take a leaf out of @feersum's book with .translate :)
Expanded:
def f(n):
 S=`n`
 n and f(n-1)                                      # Recurse if not 0
 print S+"."*all([n%10,                            # Not divisible by 10
                  set(S)<=set("0689"),             # Consists of 0689
                  (u""+S[::-1]).translate
                  ({54:57,57:54})!=S])             # When rotated is not itself

Previous solution:
def f(n):S=`n`;print S+"."*all([n%10,set(S)<=set("0689"),eval("S[::-1]"+".replace('%s','%s')"*3%tuple("6a96a9"))!=S]);n and f(n-1)

Thanks to @xnor for showing me the .replace trick some time ago.

You can use (u''+S[::-1]) instead of unicode(S[::-1]).  Also, if you swap the print and the recursive call, numbers will come out in increasing order.

@ngn Ah thanks, I didn't think u""+ would actually work

See I think this should be smaller, for example it's not your fault that print is rightfully print, not "p" say, but if you were to write "p=print" and not have count as bytes in your "official" submission it'd shorten it!

M (MUMPS) - 72 70
R n F i=0:1:n W !,i S r=$TR($RE(i),69,96) W:r=+r*r'=i*'$TR(i,0689) "."

Most built-in commands and functions in M have abbreviated versions. I've used the full names below.
READ n - Read a string from the keyboard and store it in n.
FOR i=0:1:n - Loop from zero to n, incrementing i by 1 each time. (The remainder of the line constitutes the body of the loop.)
WRITE !,i - Print a newline followed by the value of i.
SET r=$TRANSLATE($REVERSE(i),69,96)) - Reverse i, replace nines with sixes and sixes with nines, and store that in r.
WRITE:r=+r*r'=i*'$TRANSLATE(i,0689) "."

: - Denotes a postconditional expression, so the WRITE command is only executed if r=+r*r'=i*'$TRANSLATE(i,0689) evaluates to a truthy value.
r=+r - Check that r doesn't have a leading zero. The unary + operator converts a string to a number, which strips leading zeroes if there are any.
* - Multiplication operator. M has no order of operations; all binary operators are evaluated in the order they appear from left to right.
r'=i - Check that i isn't the same as it's flipped version r.
'$TRANSLATE(i,0689) - Remove all zeros, sixes, eights, and nines from i, and check that there's nothing left. (' is the logical negation operator.)
"." - Finally the argument to the WRITE command (a literal string).

Edit: Made it a little shorter by abusing the multiplication operator. Previous version:
R n F i=0:1:n W !,i S r=$TR($RE(i),69,96) I '$TR(i,0689),i'=r,r=+r W "."

APL, 53 characters
∊{⍵,'. '↓⍨∨/(3≡⊃i)(5∊i),⍵≡'9608x'[i←⌽'6908'⍳⍵]}∘⍕¨0,⍳
0,⍳N        numbers 0..N
{...}∘⍕¨    format each number as a string and do the thing in curly braces
                inside the braces ⍵ is the current string
'6908'⍳⍵    encode '6' as 1, '9' as 2, '0' as 3, '8' as 4, and all others as 5
⌽           reverse
'9608x'[A]  use each element of A as an index in '9608x':
                effectively: swap '9'←→'6', preserve '08', mask other digits
⍵≡          does it match the original string?
                this is the first boolean condition, two more to come
5∊i         did we have a digit other than '0689'?
3≡⊃i        is the first of i (that is, the last of ⍵) a '0' (encoded as 3)?
∨/          disjunction ("or") over the three conditions, returns 0 or 1
'. '↓⍨      drop 0 or 1 elements from the beginning of the string '. '
⍵,          prepend ⍵
∊           flatten the results to obtain a single output string

C# 205 209
C# doesn't have to be so long...
more or less, a port of my JavaScript answer
class P{static void Main(string[]a){for(int n=int.Parse(a[0]);n>=0;--n){string p="",u=n+p;int e=n%10;foreach(var d in u)p=(d<56?d!=54?d>48?e=0:0:9:120-d-d)+p;System.Console.WriteLine(e!=0&p!=u?u+".":u);}}}

Ungolfed
class P
{
    static void Main(string[] a)
    {
        for (int n = int.Parse(a[0]); n >= 0; --n)
        {
            string p = "", u = n + p;
            int e = n % 10;
            foreach (var d in u) p = (d < 56 ? d != 54 ? d > 48 ? e = 0 : 0 : 9 : 120 - d - d) + p;
            System.Console.WriteLine(e != 0 & p != u ? u + "." : u);
        }
    }
}

JavaScript (ES6) 101 104 106 109
A function with n as argument, output via console.log
Edit using %10 to test for leading 0
Edit 2 for reorganization, I don't need array comprehension after all
Edit 3 modified (again) the check for leading 0
F=n=>{
   for(;e=~n;console.log(e*l&&p-n?n+'.':n),--n)
     for(d of(p='')+n)p=(l=d<8?d-6?-d?e=0:0:9:24-d-d)+p
}

Ungolfed and easier to test
F=n=>
{
  o = '';
  for( ; ~n; --n) // loop on n decreasing to 0 (~n is 0 when n==-1)
  {
    e = ~n; // init to a nonzero value, zero will mark 'invalid digit'
    p = ''; // build rotated number in p
    for(d of '' + n)
    {
      // l is the current digit, on exit will be the first digit of p
      l = d < 8 ?
            d != 6 ?
              d != 0 ?
                e = 0 // invalid char found, no matter what
                : 0
              : 9 // 6 become 9
            : 24 - d - d; // calc 8 => 8, 9 => 6
      p = l + p;
    }
    // e==0 if invalid char, l==0 if leading 0
    o += ' ' + ( e * l && p-n ? n+'.' : n);
  }
  console.log(o);
}

F(100)

Output
100 99. 98. 97 96 95 94 93 92 91 90 89. 88 87 86. 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68. 67 66. 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9. 8 7 6. 5 4 3 2 1 0

Is there a name for the construction with the for loop within brackets []? I am looking for a documentation, because I only knew this from python so far.

I think you can save a lot on newlines here.

@britishtea newlines and indentation added for readability and not counted. It's a single line

@flawr https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Array_comprehensions

Ruby, 81
?0.upto(*$*){|x|puts x.reverse.tr('69','96')!=x&&x=~/^[0689]+$/&&/0$/!~x ?x+?.:x}

Input is taken from the command line.
Generates a list of Strings from 0 to n. It loops trough them and prints them. It appends a dot if all conditions are satisfied:

reversing the number and replacing the 6s with 9s doesn't yield the original
the number only consists of the digits 0, 6, 8 and 9
the number doesn't end with 0

sed, 467
Longer than C#...
I pretty much completed this when @edc65 pointed out that answers need to process numbers 0-n and not just n.  Adding the sed code to increment 0-n adds a LOT more code, as this task is ill-suited to arithmetic-less sed.
:l
/^[0689]*$/{
h
s/$/:/
:x
s/([0-9]):(.*)/:\2\1/
tx
s/://
y/69/96/
G
/^([0-9]+)\n\1/be
s/^[^0].*/&./
:e
s/.*\n//
}
p
s/\.//
s/[0-9]/<&/g
s/0//g;s/1/_/g;s/2/__/g;s/3/___/g;s/4/____/g;s/5/_____/g
s/6/______/g;s/7/_______/g;s/8/________/g;s/9/_________/g
:t
s/_</<__________/
tt
s/<//g
s/_//
:b
s/__________/</g
s/<([0-9]*)$/<0\1/
s/_________/9/;s/________/8/;s/_______/7/;s/______/6/
s/_____/5/;s/____/4/;s/___/3/;s/__/2/;s/_/1/
s/</_/g
tb
s/^$/0/
/^0$/by
bl
:y
c\
0
p

As per the OP, ordering doesn't matter, so we work downwards from n to 0.
Output:
$ sed -rnf rotproof.sed <<< 100 | grep "\."
99.
98.
89.
86.
68.
66.
9.
6.
$

bc, 158
After doing this purely in sed using all string and regex operations with no native arithmetic, I was curious to see how this would look the other way around, i.e. all arithmetic and logic operations and no string/regex:
for(i=read();i+1;r=0){p=1
for(x=i;x;x/=A){d=x%A
if(x==i&&!d)p=0
if(d==6||d==9)d=F-d else if(d%8)p=0
r=r*A+d}
if(r==i)p=0
print i--
if(p)print "."
print "\n"}

Output is sorted in descending order.
Output:
$ bc rotproof.bc <<< 100 | grep "\."
99.
98.
89.
86.
68.
66.
9.
6.
$

Bash + coreutils, 105
for((i=0;i<=$1;i++));{
[ ${i//[0689]/} ]||[ $i = `rev<<<$i|tr 69 96` ]||((!${i: -1}))||d=.
echo $i$d
d=
}

Test:
$ ./rotproof.sh 100 | grep "\."
6.
9.
66.
68.
86.
89.
98.
99.
$

Python - 152
for i in range(input()+1):print`i`+("."*all([j in"0689"for j in`i`])and`i`[-1]!="0"and`i`!=`i`.replace("9","x").replace("6","9").replace("x","6")[::-1])

+1. Looking good... If you want to learn some tricks for getting it shorter there is another answer in python 2 which uses translate instead of replace, and in the edit history it also has a way of combining those 3 replaces into 1 which might come in handy for future questions...

Nice progress! In addition to the above here's some more golfs: "."if a[i]else"" -> "."*a[i], int(raw_input()) -> input() (which is really just eval(raw_input()))

Some golfes: (1) In Python 2, you can replace str(i) with \i`. (2) You use a` only once, so why assign it to a variable.

I'll use your second suggestion, but I use str(i) several times. Which one can I replace with i?

Not i, but i with backticks, which is synonymous to repr(i). You can use it instead of str(i) everywhere, although if you have str(i) around that many times it might be shorter to assign it to a variable and use that in addition to using backticks. (i.e. x=\i`; (do stuff with x)`)

@Sp3000 Wow...wait...how did I not know that?

It's deprecated in Python 3 though, just as an additional note (hence the emphasise on Python 2)

Ah. That makes it so much shorter!

I think you can also lose the two brackets around "."*(all([j in"0689"for j ... .replace("x","6")[::-1])

AWK: 120
{a[a[6]=9]=6;a[8]=8;for(j=a[0]=0;j<=$0;++j){r="";for(i=j;i;i=int(i/10))r=r a[i%10];print(j~/[^0689]|0$/||j==r)?j:j"."}}

Read the n value from stdin.
Test:

C:\AWK>gawk -f revnum.awk|grep \.
100
^Z
6.
9.
66.
68.
86.
89.
98.
99.

Rebol - 195
for n 0 do input 1[b: copy a: form n d: c: 0 parse reverse a[any[m:"6"(change m"9"++ c)|"9"(change m"6"++ c)|"0"|"8"| skip(++ d)]]print rejoin [b either all[d = 0 c > 0 a != b a/1 != #"0"]"."{}]]

Ungolfed + some annotations:
for n 0 do input 1 [
    b: copy a: form n
    d: c: 0

    ; reverse number and rotate "6" & "9"
    ; and do some counts (c when "6" or "9" and d when != "0689")
    parse reverse a [
        any [
            m:
              "6" (change m "9" ++ c)
            | "9" (change m "6" ++ c)
            | "0"
            | "8"
            | skip (++ d)
        ]
    ]

    print rejoin [
        b either all [
            d = 0               ; only has 0689 digits
            c > 0               ; must have at least one "6" or "9"
            a != b              ; not same when reversed
            a/1 != #"0"         ; does not "end" with zero
        ]
        "." {}                  ; if ALL then print "." else blank {}
    ]
]

JavaScript - 168 129  119 113 111 108
F=n=>{for(;~n;n--){r='';for(c of""+n)r=(c-6?c-9?c:6:9)+r;console.log(r-n&&!/[1-57]/.test(r)&&n%10?n+".":n)}}

4 5 6. 8 9. 16 60 66. 68. 69 906 909. 6090 9806. 9886 9889.

Or readable version:
F=n=>{for(;~n;n--){
    r='';for(c of ""+n)r=(c-6?c-9?c:6:9)+r; // rotate
    console.log( // output, new-line is added
        // original number, and
        // append dot only if number is different than its rotated version and no un-rotatable digit is present and there is no zero at the end
        r-n && !/[1-57]/.test(r) && n%10
           ?n+".":n
    )}}

I am not very happy with the regex, any ideas?
Edit: Learned neat trick with ~ and for (... of ...) from @edc65

Edit2: Reorganized conditions

Edit3: applied suggestions by @edc65

Bad pupil :) i=n+"";for(c of i) => for(c of i=n+"") save 2 bytes

...and c==6?A:B => c!=6=>B:A => c-6?B:A

also, usually Regexp.test(String) can be used instead of String.match(Regexp), 1 byte shorter.

6 bytes is total, thanks :)
for(c of i=n+"") is quite logical when I see it, but I wouldn't think of it.
c-6?B:A God forbid I ever put this into production code

Idea about the regexp: you need to check for 1 invalid char, not 1 ore more, so '+' is not needed.If you fiddle with your console.log expression you can save 8 bytes ... but then I think your answer would be too short

@edc65 you're right about the regex (probably remnant of some earlier version); there was also one extra space -> 2 bytes in total. What do you have in mind with the console.log part? Modifying the inner expression r-i?: or replacing the console.log (I tried to build the whole string first and output everything at the end like this for(s='';...){... s+' '+n+(r-i?:)} s, but I ended up with exactly same length). And by too short you mean shorter than yours ;)

Have a look http://pastebin.com/LDQxFKgx

I was able to do the conditions, the rest is more or less your work. 102 if I could get away without correctly handling input (OP's requirement "How the input is read is up to you." gives a bit of freedom I'd say).

Got 1 more byte on the regex.

05AB1E, 38 37 30 29 bytes
ÝεÐSUT%ĀiŽR!XåPiÐ69Â‡RÊi'.«]»

Try it online.
Explanation:
Ý                # Inclusive 0-based range: [0, (implicit) input]
 ε               # Map each integer to:
  Ð              #  Triplicate the current integer
  SU             #  Convert it to a list of digits, and pop and store it in variable `X`
    T%Āi         #  If the current integer contains no trailing zeros
    ŽR!XåPi      #  And if the current integer only consists of the digits [0689]
    Ð69Â‡RÊi     #  And if the current integer is not the same when its 6s and 9s
                 #  are swapped and then the total is reversed
             '.« #   Concat a '.'
                 #  Implicit else: use the top of the stack (the duplicate current integer)
]                # Close all three ifs and the map
 »               # Join the resulting list by newlines (and output implicitly)

Additional explanation for some parts:
T%Āi       # Check if the integer contains no trailing zeros:
T          #  Push 10 (T is a builtin for 10)
 %         #  Modulo
  Ā        #  Trutified: 0 remains 0 (falsey), everything else becomes 1 (truthy)
           #   i.e. 12 % 10 → 2 → 1 (truthy)
           #   i.e. 68 % 10 → 8 → 1 (truthy)
           #   i.e. 70 % 10 → 0 → 0 (falsey) (70 remains as is)
           #   i.e. 609 % 10 → 9 → 1 (truthy)
           #   i.e. 808 % 10 → 8 → 1 (truthy)

ŽR!XåPi    # Check if the integer only consists of the digits 0, 6, 8 and/or 9:
ŽR!        #  Push 6890 (Ž is a builtin for 2-char compressed integers, where R! is 6890)
   X       #  Push variable `X` (the list of digits)
    å      #  Check for each of these digits if they're in "6890"
     P     #  Take the product of that list
           #   i.e. [1,2] → [0,0] → 0 (falsey) (12 remains as is)
           #   i.e. [6,8] → [1,1] → 1 (truthy)
           #   i.e. [6,0,9] → [1,1,1] → 1 (truthy)
           #   i.e. [8,0,8] → [1,1,1] → 1 (truthy)

Ð69Â‡RÊi   # Check if the integer with 6s and 9s swapped and then reversed isn't unchanged:
Ð          #  Triplicate the integer
 69        #  Push 69
   Â       #  Bifurcate (short for Duplicate & Reverse)
    ‡      #  Transliterate (in `a` replace all characters `b` with characters `c`)
     R     #  Reverse
      Ê    #  Check for inequality
           #   i.e. 68 → "68" → "98" → "89" → 68 != "89" → 1 (truthy) (68 becomes "68.")
           #   i.e. 609 → "609" → "906" → "609" → 609 != "609" → 0 (falsey) (609 remains as is)
           #   i.e. 808 → "808" → "808" → "808" → 808 != "808" → 0 (falsey) (808 remains as is)

Perl - 84
for(0..$ARGV[0]){s/6/x/g;s/9/6/g;s/x/9/g;printf"$_%s\n",$_=~/^[0689]+[689]$/?".":""}

Powershell, 111 102 bytes
param($s)$s+'.'*!($s-match'[1-57]|0$|'+-join$(switch -r($s[($s.Length-1)..0]){'0|8'{$_}'6'{9}'9'{6}}))

Explained test script:
$f = {

param($s)           # input string
$l=$s.Length        # length of the string
$c=$s[($l-1)..0]    # chars of the string in the reversed order
$d=switch -r($c){   # do switch with regex cases for each char
    '0|8'{$_}       # returns the current char if it equal to 8 or 0
    '6'{9}          # returns 9 if the current char is 6
    '9'{6}          # returns 6 if the current char is 9
}                   # returns array of new chars (contains 0,6,8,9 only)
$s+'.'*!(            # returns s. Add '.' if not...
    $s-match'[1-57]|0$|'+-join$d
                    # $s contains chars 1,2,3,4,5,7 or
                    # ends with 0 or
                    # equal to string of $d
)

}

@(
    ,('2'    ,'2'   )
    ,('4'    ,'4'   )
    ,('5'    ,'5'   )
    ,('6.'   ,'6'   )
    ,('7'    ,'7'   )
    ,('9.'   ,'9'   )
    ,('16'   ,'16'  )
    ,('60'   ,'60'  )
    ,('66.'  ,'66'  )
    ,('68.'  ,'68'  )
    ,('69'   ,'69'  )
    ,('906'  ,'906' )
    ,('909.' ,'909' )
    ,('8088.','8088')
    ,('9806.','9806')
    ,('9886' ,'9886')
    ,('9889.','9889')
) | % {
    $e,$s = $_
    $r = &$f $s
    "$($r-in$e): $r"
}

Output:
True: 2
True: 4
True: 5
True: 6.
True: 7
True: 9.
True: 16
True: 60
True: 66.
True: 68.
True: 69
True: 906
True: 909.
True: 8088.
True: 9806.
True: 9886
True: 9889.

Stax, 27 bytes
Ç▒≈♣▌╬"÷╜─B↓«âpø←╚S☼ì>♫è;&╛

Run and debug it
Unpacked, ungolfed, and commented, it looks like this.
0p      print 0 with no line break
F       for each [1 .. n] execute the rest of the program, where n is the input
  zP    print a newline
  q     peek and print the iterating variable without newline
  A%!C  modulo 10, and cancel iteration if zero (this cancels for multiples of 10)
  _$cc  convert iterating value to string and duplicate it twice on the stack
  7R6-$ construct the string "123457"
  |&C   if the character intersection is truthy, cancel the iteration
  r     reverse string
  69$:t map 6 and 9 characters to each other
  =C    if this rotated string is equal to the original, cancel iteration
        print "." with no newline
        (this comment precedes the instruction because it's an unterminated literal)
  ".

Run this one

authors: คูณยศ หน่อสกูล


text:
Solve the BattleBlock Theater Puzzle
The game BattleBlock Theater occasionally contains a puzzle which is a generalised version of Lights Out. You've got three adjacent blocks, each of which indicates a level between 1 and 4 inclusive with bars, e.g.:
|
||||
||

If you touch a block, then that block as well as any adjacent block will increment its level (wrapping back from 4 to 1). The puzzle is solved when all three blocks show the same level (it doesn't matter which level). Since, the order you touch the blocks in doesn't matter, we denote a solution by how often each block is touched. The optimal solution for the above input would be 201:
|    --> || --> |||     |||
||||     |      ||      |||
||       ||     ||  --> |||

The game very easily generalises any number of blocks, although for some numbers, not all configurations are solvable.
The Challenge
Given a sequence of block levels, return how often each block needs to be touched to solve the puzzle. E.g. the above example would be given as 142 and could yield 201 as a result. If there is no solution, return some consistent output of your choice, which is distinguishable from all potential solutions, e.g. -1 or an empty string.
You may write a function or program, take input via STDIN, command-line argument or function argument, in any convenient list or string format, and similarly output via a return value or by printing to STDOUT.
Your code should return correct results for all test cases within a minute on a reasonable machine. (This is not a completely strict limit, so if your solution takes a minute and ten seconds, that's fine, but if it takes 3 minutes, it isn't. A good algorithm will easily solve them in seconds.)
This is code golf, so the shortest answer (in bytes) wins.
Examples
Solutions are not unique, so you may get different results.
Input                          Output

1                              0
11                             00
12                             No solution
142                            201
434                            101
222                            000
4113                           0230
32444                          No solution
23432                          10301
421232                         212301
3442223221221422412334         0330130000130202221111
22231244334432131322442        No solution
111111111111111111111222       000000000000000000000030
111111111111111111111234       100100100100100100100133
412224131444114441432434       113013201011001101012133

As far as I know, there are exactly 4 solutions for each input where the number of blocks is 0 mod 3, or 1 mod 3, and there are 0 or 16 solutions where it is 2 mod 3.

Do you need to output an optimal solution?

@xnor No, you don't.

Do we have to print exactly one solution or can we also print all of them?

@Jakube Exactly one please. I should have added a bonus for all/the optimal solution, but I didn't think of that early enough, so any (one) solution it is.

Python 2, 115 bytes
n=input()
for F in range(4):
 t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n)
 if x<1:print t[:-1];break

This is the golfed version of the program I wrote while discussing the problem with Martin.
Input is a list via STDIN. Output is a list representing the last solution found if there is a solution, or zero if there isn't. For example:
>>>
[1, 4, 2]
[2, 1, 1]
>>>
[1, 2]
0
>>>
map(int,"3442223221221422412334")
[2, 3, 3, 2, 1, 3, 2, 0, 0, 2, 1, 3, 2, 2, 0, 0, 2, 2, 3, 1, 1, 3]

Pyth, 32 29 bytes
V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB

The obligatory port. Thanks to @Jakube for the 3 byte saving.
Input method is the same as above, try it online.

Explanation (long and full of logic!)
First, two basic observations:

Observation 1: It doesn't matter which order you touch the blocks

Observation 2: If you touch a block 4 times, it's equivalent to touching it once

In other words, if there is a solution then there is a solution where the number of touches is between 0 and 3 inclusive.
Since modulo 4 is so nice, let's do that with the blocks too. For the rest of this explanation, block level 0 is equivalent to block level 4.
Now let's denote a[k] to be the current level of block k and x[k] to be the number of times we touch block k in a solution. Also let n be the total number of blocks. As @Jakube has noted, a solution must satisfy:
  a[0]   + x[0] + x[1]
= a[1]   + x[0] + x[1] + x[2]
= a[2]          + x[1] + x[2] + x[3]
= a[3]                 + x[2] + x[3] + x[4]
...
= a[n-1]                                     ...  + x[n-2] + x[n-1] + x[n]
= a[n]                                       ...           + x[n-1] + x[n]
= C

where C is the final level all blocks end up on, between 0 and 3 inclusive (remember we're treating level 4 as level 0) and all equations above are really congruences modulo 4.
Now here's the fun part:

Observation 3: If a solution exists, a solution exists for any final block level 0 <= C <= 3.

There are three cases based on the number of blocks modulo 3. The explanation for each of them is the same — for any number of blocks, there exists a subset of blocks which, if you touch each of them once, increases all block levels by exactly 1.
0 mod 3 (touch every third block starting from the second):
    .X. / .X. / .X.

1 mod 3 (touch every third block starting from the first):
    X. / .X. / .X. / .X

2 mod 3 (touch every third block starting from either the first or second):
    X. / .X. / .X. / .X.
    .X. / .X. / .X. / .X

This explains why there are 4 solutions for 0 mod 3 and 1 mod 3, and usually 16 solutions for 2 mod 3. If you have a solution already, touching the blocks as above gives another solution which ends up at a higher block level (wrapping around).
So what does this mean? We can pick any final block level C we want! Let's pick C = 0, because this saves on bytes.
Now our equations become:
0 = a[0] + x[0] + x[1]
0 = a[1] + x[0] + x[1] + x[2]
0 = a[2] + x[1] + x[2] + x[3]
0 = a[3] + x[2] + x[3] + x[4]
...
0 = a[n-1] + x[n-2] + x[n-1] + x[n]
0 = a[n] + x[n-1] + x[n]

And rearrange:
x[1] = -a[0] - x[0]
x[2] = -a[1] - x[0] - x[1]
x[3] = -a[2] - x[1] - x[2]
x[4] = -a[3] - x[2] - x[3]
...
x[n] = a[n-1] - x[n-2] - x[n-1]
x[n] = a[n] - x[n-1]

So what we can see is, if we have x[0], then we can use all the equations except the last to find out every other x[k]. The last equation is an additional condition we must check.
This gives us an algorithm:

Try all values for x[0]
Use the above equations to work out all of the other x[k]
Check if the last condition is satisfied. If so, save the solution.

That gives the solution above.
So why do we sometimes get no solution for 2 mod 3? Let's take a look at these two patterns again:
X. / .X. / .X. / .X.
.X. / .X. / .X. / .X

Now consider the equations at those positions, i.e. for the first one:
0 = a[0] + x[0] + x[1]
0 = a[3] + x[2] + x[3] + x[4]
0 = a[6] + x[5] + x[6] + x[7]
0 = a[9] + x[8] + x[9] + x[10]

Add them up:
0 = (a[0] + a[3] + a[6] + a[9]) + (x[0] + x[1] + ... + x[9] + x[10])

For the second one:
0 = a[1] + x[0] + x[1] + x[2]
0 = a[4] + x[3] + x[4] + x[5]
0 = a[7] + x[6] + x[7] + x[8]
0 = a[10] + x[9] + x[10]

Add them up again:
0 = (a[1] + a[4] + a[7] + a[10]) + (x[0] + x[1] + ... + x[9] + x[10])

So if (a[1] + a[4] + a[7] + a[10]) and (a[0] + a[3] + a[6] + a[9]) are not equal, then we have no solution. But if they are equal, then we get 16 solutions. This was for the n = 11 case, but of course this generalises to any number that is 2 mod 3 — take the sum of every third element starting from the second, and compare to the sum of every third element starting from the first.
Now finally, is it possible to figure out what x[0] has to be instead of trying all of the possibilities? After all, since we restricted our target level C to be 0, there is only one x[0] which gives a solution in the 0 mod 3 or 1 mod 3 case (as 4 solutions / 4 final levels = 1 solution for a specific final level).
The answer is... yes! We can do this for 0 mod 3:
 .X..X
.X..X.

Which translates to:
0 = a[2] + x[1] + x[2] + x[3]   -> 0 = (a[2] + a[5]) + (x[1] + ... + x[5])
0 = a[5] + x[4] + x[5]          /

0 = a[1] + x[0] + x[1] + x[2]   -> 0 = (a[1] + a[4]) + (x[0] + x[1] + ... + x[5])
0 = a[4] + x[3] + x[4] + x[5]   /

Subtracting gives:
x[1] = (a[2] + a[5]) - (a[1] + a[4])

Similarly for 1 mod 3 we can do this pattern:
 .X..X.
X..X..X

Which gives:
x[0] = (a[2] + a[5]) - (a[0] + a[3] + a[6])

These of course generalise by extending the indices by increments of 3.
For 2 mod 3, since we have two subsets which cover every block, we can actually pick any x[0]. In fact, this is true for x[0], x[1], x[3], x[4], x[6], x[7], ... (basically any index not congruent to 2 mod 3, as they are not covered by either subset).
So we have a way of picking an x[0] instead of trying all possibilities...
... but the bad news is that this doesn't save on bytes (124 bytes):
def f(n):s=[];L=len(n);B=sum(n[~-L%3::3])-sum(n[-~L%3::3]);x=A=0;exec"s+=B%4,;A,B=B,-n[x]-A-B;x+=1;"*L*(L%3<2or B<1);print s

Clever.
You can save 1 char by using J instead of H and 2 chars, if you pop the last element PJ instead of slicing. <J_1.
V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB

@Jakube Ah thanks. When I read pop I thought it was like Python pop returning the last element while removing from the list. Now I see that isn't the case.

Pyth, 72 76 73 66 39 38 character
Ph+f!eTmu+G%+&H@G_3-@QH@QhH4UtQd^UT2]Y

edit 4: Realized, that the calculations Q[N]-Q[N+1]+solution[-3] and Q[-2]-Q[-1]+solution[-3] are ident. Therefore I overcalculate the solution by 1, and filter the solutions, where the last entry is 0. Then I pop the last entry. Luckily the special cases doesn't need an extra treatment with this approach. -27 character
edit 3: Applying some golfing tricks from FryAmTheEggman: -7 character
edit 2: Using filter, reduce and map: -3 character
edit 1:In my first version I didn't printed anything, if there was no solution. I don't think that's allowed, therefore +4 character.
Expects a list of integers as input [1,4,2] and outputs a valid solution [2,0,1] if there is one, otherwise an empty list [].
Explanation:
Let Q be the list of 5 levels and Y the list of the solution. The following equations have to hold:
  Q0 + Y0 + Y1
= Q1 + Y0 + Y1 + Y2
= Q2      + Y1 + Y2 + Y3
= Q3           + Y2 + Y3 + Y4
= Q4                + Y3 + Y4

Therefore if we use any Y0 and Y1, we can calculate Y2, Y3 and Y4 in the following way.
Y2 = (Q0 - Q1     ) mod 4
Y3 = (Q1 - Q2 + Y0) mod 4
Y4 = (Q2 - Q3 + Y1) mod 4

Than all levels exept the last one are equal (because we didn't used the equation = Q4                + Y3 + Y4. To check, if this last one is also equal to the other levels, we can simply check if (Q3 - Q4 + Y2) mod 4 == 0. Notice, that the left part would be the value Y5. If I calculate the 6th part of the solution, I can simply check, if it is zero.
In my approach I simply iterate over all possible starts ([0,0], to [3,3]), and calculate length(input)-1 more entries and filter all solutions that end with a zero.
mu+G%+&H@G_3-@QH@QhH4UtQd^UT2   generates all possible solutions

it's basically the following:
G = start value           //one of "^UT2", [0,0], [0,1], ..., [9,9]
                          //up to [3,3] would be enough but cost 1 char more
for H in range(len(Q)-1): //"UtQ"
   G+=[(H and G[-3])+(Q(H)-Q(H+1))%4] //"+G%+&H@G_3-@QH@QhH4"
   //H and G[-3] is 0, when H is empty, else G[-3]

then I filter these possible solutions for valid ones:
f!eT //only use solutions, which end in 0

to this list of solutions I append an empty list, so that it has at least one item in it
 +....]Y

and take the first solution h, pop the last element p and print it
 Ph

Notice, that this also works, if there is only one block. In my approach I get the starting position [0,0] and doesn't extend it. Since the last entry is 0, it prints the solution [0].
The second special case (2 blocks) isn't that special after all. Not sure, why I overcomplicated things earlier.

I think printing nothing is okay for no solution iff that's the only case where you print nothing. Might have to get @MartinBüttner to confirm though

?**lQ]0qhQeQ<lQ3h+f!%-+ePQ@T_3eQ4mu+G]%+&H@G_3-@QH@QhH4UttQd^UT2]Y is 66 bytes. The performance was hit a bit, but it still runs the largest test case in <1s for me. Ping me if you want explanations of some of the golfs; there isn't enough space in this comment ;) Hope you are enjoying using Pyth :D

+<list><int> has the same effect as +<list>]<int>, so you can remove the first ]. Also, very nice solution.

@isaacg Is the same true for ~? It didn't seem to be when I tried

@Sp3000 Just replace ~ with a - ~<list>]<int> is equivalent to a<list><int>. ~ is +=, while a is .append()

@isaacg Oh... the doc says Bitwise and or setwise and. Returns leading type. currently

@Sp3000 Oops - I must have forgotten to update that. Someday soon I'm going to do a full doc rewrite. I'll fix it.

Ruby, 320 313 chars
m=gets.chop.chars.map{|x|x.to_i-1}
a=m.map{0}
t=->n{m[n]+=1
m[n-1]+=1if n>0
m[n+1]+=1if n<m.size-1
m.map!{|x|x%4}
a[n]=(a[n]+1)%4}
t[0]until m[0]==1
(2...m.size).map{|n|t[n]until m[n-1]==1}
r=0
while m.uniq.size>1&&m[-1]!=1
(0...m.size).each_with_index{|n,i|([1,3,0][i%3]).times{t[n]}}
(r+=1)>5&&exit
end
$><<a*''

Can definitely be golfed more. Outputs nothing for unsolvable puzzles.
Ungolfed version:
#!/usr/bin/ruby

nums = gets.chomp.chars.map {|x| x.to_i-1 }
touches = nums.map {0}

# our goal: make all the numbers 1
# utility function
touch = ->n {
    nums[n] += 1
    nums[n-1] += 1 if n > 0
    nums[n+1] += 1 if n < (nums.length-1)
    nums.map! {|x| x % 4 }
    touches[n] = (touches[n] + 1) % 4
}

# first, start with the very first number
touch[0] until nums[0] == 1

# then, go from index 2 to the end to make the previous index right
(2...nums.length).each {|n|
    touch[n] until nums[n-1] == 1
}

iters = 0
if nums.uniq.length != 1
    # I have no idea why this works
    while nums[-1] != 1
        (0...nums.length).each_with_index {|n, i|
            ([1, 3, 0][i % 3]).times { touch[n] }
        }
        if (iters += 1) > 5
            puts -1
            exit
        end
    end
end

puts touches * ''

Okay, this one was fun. Here's the basic algorithm, with {n} representing n "touch"es on the number above the n, as demonstrated on one of the examples:
we want each number to be a 1
first make the first number a 1
3442223221221422412334
2}
1242223221221422412334
 {3} now keep "touch"ing until the number to the left is a 1
1131223221221422412334
  {2}
1113423221221422412334
   {2}
1111243221221422412334
... (repeat this procedure)
1111111111111111111110

I got stumped for a bit here. How can I turn the 111...1110 into a series of same numbers? So I compared my solution and the correct solution (note: the "touch" counts all are one greater than they should be because the input is 1-indexed, while the output is 0-indexed):
3033233103233301320210
0330130000130202221111

I noticed that each number was one away from the correct one mod 4, so I marked them with +s, -s, and =s:
3033233103233301320210 original program output
+-=+-=+-=+-=+-=+-=+-=+ amount to modify by (+1, -1, or 0 (=))
4334534404534602621511 result (the correct answer)

0330130000130202221111 (the original solution, digits equal to result mod 4)

That worked for a while, until I noticed that sometimes the final result was 111...11112 or 11...1113 as well! Fortunately, repeatedly applying the magical formula that makes no sense but works also sorted these out.
So, there you have it. A program that starts out making sense, but degrades into more and more ugly hackiness as it goes. Quite typical for a code golf solution, I think. :)

I love the last comment in your code :). You can save 2 chars by changing exit if (r+=1)>5 to (r+=1)>5&&exit. Also, the (code)while cond syntax is shorter than while cond \n code \n end.

Python 2, 294,289,285,281 273 bytes
n=input();l=len(n);s=[0]*l
for i in range(2,l):
 a=(n[i-2]-n[i-1])%4;s[i]+=a;n[i-1]+=a;n[i]+=a
 if i+1<l:n[i+1]+=a
 n=[a%4for a in n]
if l%3>1 and n!=[n[0]]*l:print"x"
else:
 for i in range(l%3,l-1,3):s[i]+=(n[l-1]-n[l-2])%4
 m=min(s);s=[(a-m)%4 for a in s];print s

DEMO
I'm sure this can be golfed further..
Here are the results from the test cases:
[1]
-> [0]

[1,1]
-> [0, 0]

[1,2]
-> x

[1,4,2]
-> [2, 0, 1]

[4,3,4]
-> [1, 0, 1]

[2,2,2]
-> [0, 0, 0]

[4,1,1,3]
-> [0, 2, 3, 0]

[3,2,4,4,4]
-> x

[2,3,4,3,2]
-> [0, 0, 3, 3, 1]

[4,2,1,2,3,2]
-> [2, 0, 2, 3, 3, 1]

[3,4,4,2,2,2,3,2,2,1,2,2,1,4,2,2,4,1,2,3,3,4]
-> [0, 3, 3, 0, 1, 3, 0, 0, 0, 0, 1, 3, 0, 2, 0, 2, 2, 2, 1, 1, 1, 1]

[2,2,2,3,1,2,4,4,3,3,4,4,3,2,1,3,1,3,2,2,4,4,2]
-> x

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2]
-> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0]

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4]
-> [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 3, 3]

[4,1,2,2,2,4,1,3,1,4,4,4,1,1,4,4,4,1,4,3,2,4,3,4]
-> [1, 0, 3, 0, 0, 3, 2, 3, 1, 0, 0, 1, 0, 3, 1, 1, 3, 1, 0, 0, 2, 1, 2, 3]

The algorithm first makes sure that the values of all blocks except the last block are the same (by iterating through and adding to the "touch counts" of all blocks except the first 2). Then, if the number of blocks allows for it ((num_of_blocks - 1) % 3 != 1), goes back and makes sure the values of the rest of the blocks match the last block. Prints x if there is no solution.

source: Stack Exchange

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

authors: انور الشراري

sort: votes


text:
Magnetic Sculptures
This is a loose continuation of my earlier challenge on constructing graphs.
Background
An eccentric artist has hired you to estimate the structural integrity of his sculptures. He creates his works of art by taking a bunch of cube-shaped magnets, and dropping them one by one into a huge pile. To better analyze his method, we use the following two-dimensional model. We start with an empty floor, and drop a magnet # at any integer coordinate, say 0:
       |
       v
       #
===============
       0

If another magnet is dropped at 0, it ends up on top of the previous one:
       |
       v
       #
       #
===============
       0

Now, let us drop one more magnet at 0, and then one at 1:
        |
       #v
       ##
       #
===============
       0

As seen above, a falling magnet sticks to the second magnet it passes (the first one merely slows it down). The second magnet need not be directly below the first one, and a magnet on both sides still counts as one magnet:
      #   #
      ##|##
      # v #
      ### #
      #   #
===============
       0

The artists wants you to calculate the maximal vertical gap in the final sculpture, that is, the maximum number of empty spaces between two magnets on the same column, or a magnet and the ground below it. In the above picture, this number would be 3 (on column 2).
Input
A list of integers, representing the coordinates where the artist drops his magnets, read from left to right. You may assume that the coordinates satisfy -1024 <= i < 1024 and that the length of the list is at most 1024, if that helps.
Output
The maximal vertical gap in the final sculpture. The empty sculpture has gap -1, and this case has to be included, since our sculptor is a dadaist.
Additional rules
You may give a function or a full program. The shortest byte count wins, and standard loopholes are disallowed. Code with explanations is preferred.
Test cases
[] -> -1
[0,2,1] -> 0
[0,0,0,0,0,1,-1] -> 3
[0,0,0,0,0,1,1,1,2] -> 4
[1,1,2,2,2,2,2,2,1] -> 2
[1,1,2,2,2,2,2,2,1,0,1,0] -> 2
[1,2,1,2,1,2,1,2,2,2,2,1,0] -> 3
[-1,-1,-1,1,1,1,0] -> 1
[-1,-1,-1,-1,2,2,1,1,2,2,2,1,0] -> 2
[-2,-2,-2,-1,-1,-1,0,0,0,1,1,1,2,2,2,3,3,4,4,5,5,5,6] -> 6

Dyalog APL, 73 70 characters
{y←⍬⋄⌈/¯1,,¯1-2-/0,x⊢⌸{y,←⌈/(1+y/⍨0=⍵),Y⊃⍨2⊃⍒Y←1 1,∪y/⍨1=⍵}¨|x-¯1↓¨,\x←⍵}
{y←⍬⋄¯1⌈⌈/,¯1-2-/¯1,⍵⊢⌸{y,←⌈/(1+y/⍨0=⍵),⊃1↓{⍵[⍒⍵]}∪y/⍨1=⍵}¨|⍵-¯1↓¨,\⍵}
First statement:
       y←⍬  initialize semi-global variable y with an empty vector
Second statement, from right to left:
         ⍵  the vector of x coordinates
       ,\⍵  concat-scan: all prefixes of ⍵ of length 1, 2, ..., ≢⍵
   ¯1↓¨,\⍵  drop the last element of each prefix, lengths are 0, 1, ..., (≢⍵)-1
|⍵-¯1↓¨,\⍵  for each x: magnitudes of differences between x and its predecessors
 {...}¨...  execute the code in parens for each item of the argument
         ⍵  is now a single vector of differences from those described above
       1=⍵  boolean mask, where are our neighbouring xs?
    y/⍨1=⍵  select the ys corresponding to our neighbouring xs
   ∪y/⍨1=⍵  unique ys
   {⍵[⍒⍵]}  sort descending
       ⊃1↓  first of one-drop, i.e. get the second element if it exists, otherwise 0
       0=⍵  which previous xs are the same as our x?
  1+y/⍨0=⍵  select the corresponding ys and add 1 to them
        ⌈/  maximum of all the ys described so far
       y,←  append to the semi-global y
            the result from {} will be identical to y
  ⍵⊢⌸{...}  a matrix of ys, grouped in rows by x (which is now in ⍵) and zero-padded
       ¯1,  prepend ¯1 to the left of each row
       2-/  differences between consecutive horizontal elements, result is a matrix
       ¯1-  negative one minus each element of the matrix
         ,  ravel the matrix (linearize it to a vector)
        ⌈/  maximum; if the vector is empty, return ¯1.8e308, a very small number
     ¯1⌈⌈/  greater of ¯1 and the ⌈/  to avoid the very small number

Note: This is 122 bytes long (challenge is in bytes), assuming UTF-8.

See https://codegolf.stackexchange.com/questions/42536/create-an-array-with-repeated-numbers/42571?noredirect=1#comment100808_42571

I'm quite sympathetic: I've often been dinged for using non-ASCII characters in my golf'd Haskell. Since then I've been quite mindful if the Q specifies count by characters or bytes.

@MtnViewMark Scoring by bytes doesn't mean scoring by UTF-8 bytes. Doing so for APL is punishing it for being too old to recognise ASCII as an important standard. APL's character set fits easily within a single-byte codepage and that codepage exists. So using that codepage as the encoding each character is a byte. On the other hand, if you use non-ASCII characters in Haskell, you'll have to use an encoding which contains both the ASCII and the non-ASCII characters - and that's usually UTF-8.

@ngn - having now read most of the meta posts on this, seems that things are, alas, still muddy. However, perhaps it would be best, when the challenge is scored in bytes, to score APL in bytes, but mention somewhere the encoding used.

@MtnViewMark I'd be happy to discuss any particular concerns you have.  I don't think there would be much value in mentioning the encoding here, as this pertains to all APL posts.

Haskell - 217 185 182 Bytes
import Data.List
r g n m|m==n=max(head(g m)+1)((reverse.(0:).nub.sort$g(m-1)++g(m+1))!!1):g m|1<3=g m
j x=(-1)-minimum(0:(map(foldl r(\_->[0])x)[-1024..1024]>>=(tail>>=zipWith(-))))

Usage:
j [1,2,1,2,1,2,1,2,2,2,2,1,0]

This function builds up another function that returns a list of magnet y-positions for a given x-position. With it, it calculates the gaps for all x-positions -1024 .. 1024 and takes the maximum (Edit: now I'm taking the minimum, because gaps are negative: the lower the number the larger the gap).

Clever approach! Hope you don't mind that I golf'd it down a bit.

@MtnViewMark: Not at all. I've found 3 further bytes to save: don't flip the -, go with negative numbers and take the minimum.

In my repo, you can find this code, 42997-Magnetic.hs which also includes a test harness for the test cases, and a visualizer that displays the sculptures.

Javascript, 201 193
F=P=>{m=[];for(p of P){s=2;c=m[p]=m[p]||[];for(i=1e4;~i&&s;i--){if((m[p-1]||[])[i]||(m[p+1]||[])[i])s--;if(c[i-1]) s=0}c[++i]=1}g=-1;m.map(c=>{ d=0;for(i in c){g=i-d>g?i-d:g;d=++i} });return g}

F([1,1,2,2,2,2,2,2,1]) === 2

Or readable version
F=P=>{
  m=[];  // magnet positions
  for(p of P){ // every dropped magnet
    s=2; // initial speed
    c=m[p]=m[p]||[]; // column where magnet is dropping
    for(i=1e4;~i&&s;i--){ // continue until at floor or zero speed
      if((m[p-1]||[])[i]||(m[p+1]||[])[i])s--;  // magnet on either side, decrease speed
      if(c[i-1]) s=0; // magnet is directly below
    }
    c[++i]=1;
  }
  g=-1; // maximum gap
  m.map(c=>{
          d=0;for(i in c){g=i-d>g?i-d:g;d=++i;}
       });
  return g;
};

Python 2.7, 327
from itertools import *
s=input()
if s:m=min(s);l=[[] for _ in range(max(s)-m+3)]
for t in s:
    i=t-m+1;r=l[i];c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:];j=len(c)-c.index(1)-1-len(r) if any(c) else 0;l[i]=r+[0]*j+[1]
print -1 if not s else max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

Before white space golfing, it looks like this:
from itertools import *
s=input()
if s:
    m=min(s)
    l=[[] for _ in range(max(s)-m+3)]
for t in s:
    i=t-m+1;r=l[i]
    c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:]
    j=len(c)-c.index(1)-1-len(r) if any(c) else 0
    l[i]=r+[0]*j+[1]
print -1 if not s else max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

Here's an explanation of the more complex lines, mostly for my own benefit.
l=[[] for _ in range(max(s)-m+3)]

This constructs an array of empty lists of length max(drops)-min(drops)+1 plus a placeholder on either side. I always want to write [ [ ] ]*K to construct an array of empty lists, but that makes K pointers to the same empty list.
c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:]

The function izip_longest from itertools is like zip, but infills the shorter list with None in order to zip the lists together. The slicing [::-1] reverses the list of 0's and 1's from the "or" comparison. The list is reversed in order to use the index method in the next line, which finds the first instance of an element. Since the last element of a nonempty column must be 1, this is the first element in the reversed list and is ignored via the slice [1:].
j=len(c)-c.index(1)-1-len(r) if any(c) else 0
l[i]=r+[0]*j+[1]

First calculate the difference between the length of column i and the position of the second 1 in the adjacent columns. If the difference is positive, add that many zeros to column i before adding a 1. Any nonpositive number times [0] is the empty list.
max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

The function groupby from itertools splits a list into subsequences of consecutive elements. This line finds the max of the lengths of all the subsequences of zeros in all of the columns. It's necessary to cast each subsequence q to a list, because groupby returns a generator (like all the itertools functions) which naturally doesn't support a len method.

Java - 281 bytes
Pretty straight forward.
First it constructs the sculpture in an array
Then it finds the greatest gap.

int a(int[]b){
        int[][]d=new int[9999][9999];
        int g,r,t,y=-1;
        for(int c:b){
            c+=5000;
            g=0;
            for(r=9998;r>=0;r--){
                if(r==0||d[c][r-1]==1){d[c][r]=1;break;}
                if((d[c-1][r]==1||d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}
            }
        }
        for(int[] k:d){
            t=0;
            for(int i:k){
                if(i==0)t++;
                else{if(t>y)y=t;t=0;}
            }
        }
        return y;
    }

small -
int a(int[]b){int[][]d=new int[9999][9999];int g,r,t,y=-1;for(int c:b){c+=5000;g=0;for(r=9998;r>=0;r--){if(r==0||d[c][r-1]==1){d[c][r]=1;break;}if((d[c-1][r]==1||d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}}}for(int[] k:d){t=0;for(int i:k){if(i==0)t++;else{if(t>y)y=t;t=0;}}}return y;}

You can save a byte by replacing the first || with |. Also, returning y instead of printing it saves 9 bytes.

@Ypnypn, Thanks! BTW, Your first statement seems to throw an ArrayIndexOutOfBounds exception (-1). (I don't have a lot of experience with bitwise operators)

It's been about 1.5 years, but you can golf it some more: (272 bytes): int a(int[]b){int z=9999,d[][]=new int[z][z],g,r,t,y=-1;for(int c:b){c+=z/2;g=0;for(r=z;--r>-2;){if(r==0||d[c][r-1]==1){d[c][r]=1;break;}if((d[c-1][r]==1|d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}}}for(int[]k:d){t=0;for(int i:k){if(i==0)t++;else{if(t>y)y=t;t=0;}}}return y;}. Summary of the changes: z=9999 has been added and used; int and int[][] field initialization has been merged into one; second || is replaced by |; for(r=9998;r>=0;r--) has been changed to for(r=z;--r>-2;)

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


text:
Unflatten an Array
This challenge was inspired by a question on Mathematica.SE.
Say you've got a nested list/array of some arbitrary structure (the lists at each level don't necessarily have the same length). For simplicity, we'll assume that the nodes are non-negative integers or empty arrays. As an example
[[[1, 3], 2], [1, 4], 12, [[0, [], 0], [5, [7]]]]

Sometimes it's more convenient to flatten that list to perform some manipulation of the nodes, e.g.
--> [1, 3, 2, 1, 4, 12, 0, 0, 5, 7]
--> [1, 1, 0, 1, 0, 0, 0, 0, 1, 1]

But in the end you actually want to preserve the original structure, so you want to turn this back into
--> [[[1, 1], 0], [1, 0], 0, [[0, [], 0], [1, [1]]]

Your task is to perform that last step.
Given a nested list of arbitrary non-negative integers, which represents the desired structure of the result, and a flat list of non-negative integers, which represent the desired values, reshape the flat list into the form of the structured list. You may assume that both lists contain the same number of integers.
As usual you don't have to deal with invalid input (e.g. the second list not being flat, the input being syntactically malformed, not having integers as nodes, etc.). You may modify the input arrays in your code.
You may write a function or program, taking input via STDIN, command-line argument or function argument, and you may return the result or print it to STDOUT. You may use any convenient list or string format to represent input and output (as long as the format is unambiguous and the input is not preprocessed). Also, the format of both inputs needs to be consistent (so you can't take one input as a string and the other as a list, for instance). You may take the input lists in either order, but please specify the exact input method in your answer.
One more restriction: you must not use regular expressions. This is an array manipulation challenge, not a string manipulation challenge.
This is code golf, so the shortest answer (in bytes) wins.
Test Cases
Structure                             Values                 Result
[[[1,3],2],[1,4],12,[[0,0],[5,[7]]]]  [1,1,0,1,0,0,0,0,1,1]  [[[1,1],0],[1,0],0,[[0,0],[1,[1]]]]
[[[0,0],0],[0,0],0,[[0,0],[0,[0]]]]   [1,1,0,1,0,0,0,0,1,1]  [[[1,1],0],[1,0],0,[[0,0],[1,[1]]]]
[]                                    []                     []
[[]]                                  []                     [[]]
[0,1,2,3]                             [5,1,0,5]              [5,1,0,5]
[[[[[0]]]]]                           [123]                  [[[[[123]]]]]
[0,[1,[]],[[]],[2,3],[]]              [1,6,1,8]              [1,[6,[]],[[]],[1,8],[]]

Is it allowed if the values in the Structure array get changed?

@ProgramFOX yes. "You may modify the input arrays in your code."

Ironically, one of the submissions here is in Mathematica.

@impinball That is mine, which I posted along with the question, in order to prevent anyone else from stealing the answer from the linked question (and in fact, it's merely a golfed down version of that answer).

@MartinBüttner Oh. Nice. It's actually one of the shorter answers, too.

CJam, 18 16 13 bytes
lA,sNerN%l~]z

Takes input via STDIN in the same format as the previous CJam answer:
[0 [11 []] [[]] [2 3] []]
[1 6 1 8]

and outputs the result string to STDOUT
[1 [6 []] [[]] [1 8] []]

I simply treat the first line as string, convert all digit characters to newlines, split on one or more occurrences of newlines, put the second line as an array on stack, wrap in an array and zip together the two arrays (rows). Printing is automatic and as the first row was treated as string, it retains its brackets.
Code expansion
lA,sNerN%l~]z
l                     "Read the first line of input. This is the nested array";
 A,s                  "Get array [0,1,2...9] and  convert it to string '012..9'";
    Ner               "Replace all occurrences of 0,1,2,..9 with new line";
       N%             "Split on one or more occurrences of new line";
         l~           "Read the second line as an array";
           ]          "Wrap both the splitted string and the second line array";
                      "in an array";
            z         "Transpose the array, there by placing the numbers from second";
                      "input array in the split holes of first input string";

Thanks to @user23013 for saving 3 bytes.
Try it online here

From the OP, "This is an array manipulation challenge, not a string manipulation challenge."

@atk: It is arguable since OP only explicitly disallow regular expression.

Short for /La-: %.

@user23013 Wow, never bothered to realize that % is for split too, and it splits across multiple occurrences too!

@atk Yes, since only regex were banned, I used this technique.

JavaScript, ES6, 44 bytes
f=(a,b,i=0)=>a.map(x=>x.map?f(x,b,i):b[i++])

This creates a function f which can be called like
f([0,[1,[]],[[]],[2,3],[]],[1,6,1,8])

i.e. the nested array and the values array as input arguments. The output of the function is the converted nested array.
This question is a very nice question for recursion, that is why the answer is a neat and sweet recursion function. I create a function f which converts the first argument using the map method. For each element, if the element is an array, it calls f again, otherwise, for integers, it gets the ith item and returns that, incrementing the value of i. The value of i is passed down in each recursive call, so as to maintain the order correct.
Array vs. Integer detection is yet again done using the map method. For an array variable, map is a valid function, while for integer variables, there is no property or function called map defined for the variable.
This works in a latest Firefox browser (due to ES6).

I know I should avoid comments like "+1" and "thanks", but damn this is one sweet ES6 function! I can look at this code line for hours :)

I se that there's 2 .map existed in the code. Is there any way to further shorten it? Anyway, nice code!

Whoa, when did ES add that lambda syntax?

@fluffy in ES6 ;)

@Derek朕會功夫 unfortunetely no. map is tied to the context, so the first map belongs to a while the next map belongs to each x in the iteration. There is no other shorter way to refer map either, nor to differentiate array from integers

JavaScript, ES6, 41 bytes
I was really impressed by Optimizer's answer, it was very cleverly done and I learned a lot. However on looking it over I found a way of shortening it slightly and fixing a small bug:
f=(a,b)=>a.map(x=>x.map?f(x,b):b.shift())

I took out the i variable and replaced it with a shift(). This makes it slightly shorter and fixes the problem with the fact that i is passed by value and not by reference, witch caused some numbers from the final array to repeat and some at the end not to be used.
Again, Optimizer's answer was really well thought out, better than I could have done, I just fixed it a little.

Nice golf! A bit sad that I did not catch that :P

Dyalog APL, 14 characters
This is a no-brainer: (∊a)←b.
Normally, ∊a means a flattened, but when it occurs on the left-hand side of an assignment, it does precisely what this problem is asking for.  To comply with the requirement of being a function, it needs a few extra squiggles: {a←⍺⋄(∊a)←⍵⋄a} (curly braces for lambda; ⍺ and ⍵ for left and right argument; ⋄ for statement separator).
Test on tryapl.org.  Note that in APL the empty numeric vector is denoted by ⍬ ("zilde").  One-element vectors are constructed with (,A) because (A) would mean a scalar.  In the output, this thing:
┌⊖┐
│0│
└~┘

represents an empty numeric vector.  The 0 in the centre shows the "prototypical element" which is not an element of the array.

Does that graphical representation not distinguish (,1) and (1) or why is the final bit just presented as [1|1] instead of [1|[1]]?

The graphical representation that tryapl uses (known as ]box on) doesn't distinguish between them.  There's another function in Dyalog (display from dfns.dws) that does make a distinction, but unfortunately tryapl restricts the loading of additional workspaces (i.e. libraries). :(

To see the result in square-bracketed form, try this: ∊{0=⍴⍴⍵:⍕⍵ ⋄ '['(∇¨⍵)']'}a.  Or this: ∊{0=⍴⍴⍵:⍕⍵ ⋄ '['(1↓,'|',[1.5]∇¨⍵)']'}a if you insist on the separator, |.

Oh, you can also use ]display a in tryapl.  It gives complete information about the structure.  Sorry, I didn't realize this at first.

Fair point.  I turned it into a function at the cost of 2 extra bytes.

Make it a tfn to save 2 bytes: a←⎕⋄(∊a)←⎕⋄a

Python 2, 50
f=lambda s,v:v.pop(0)if s<[]else[f(x,v)for x in s]

This was a very beautiful problem. As I kept working on it, I kept realizing that bits of my code were unnecessary, and the logic collapsed into a simple expression. Most of the golfing was in finding the right algorithm.
s is the structure and v is the flat list of list. The idea is to check whether s is an integer with s<[] (Python 2 treats numbers as smaller than lists). If it is, simply take and return the first element of v, removing it from v. Otherwise, recurse down onto the sublists of s.
The pop  is a piece of imperative magic in very functional-style code. Because all v point to the same instance, popping an element from one removes it from v in the whole execution tree, so each number in v is only used once. The list comprehension [f(x,v)for x in s] creates a call tree that is expanded depth-first and left-to-right, causing the elements of v to be slotted in the correct order.
I wrote this independently of grc's answer, but it turned out to the same up to moving a single [ (and variable names). The move saves a char due to spacing. The bracket move means handling the node case immediately in the function, rather than as part of the list comprehension, which I hadn't considered.
We can save a char for 49 if we stretch the input requirements to take the value from STDIN and the structure as a function argument. This lets us use map.
v=input()
g=lambda s:v.pop(0)if s<[]else map(g,s)

Ruby, 39
f=->a,b{a.map{|d|f[d,b]}rescue b.shift}

Recurses till the element in the list is an integer.
Since calling Integer.map gives an exception,
it goes to the rescue portion, which "pops/shift" the 1st element out of the 2nd list.
Regex soln... a bit longer:
f=->a,b{eval a.to_s.split(/\d+/).zip(b)*''}

Try it with some test cases

Just for reference, regex solutions aren't allowed. ;)

Python, 51
f=lambda a,b:[b.pop(0)if x<[]else f(x,b)for x in a]

Example:
>>> f([0,[1,[]],[[]],[2,3],[]], [1,6,1,8])
[1, [6, []], [[]], [1, 8], []]

Mathematica, 41 bytes
Function[,m[[i++]],Listable][i=1;m=#2;#]&

This is an unnamed function which takes the structure as the first argument and the list of values as the second argument (and returns a list).
This is a golfed version of the accepted answer on the question that inspired this challenge. I'm posting this myself, and will not accept this answer (should it actually remain the shortest, which I doubt). This is in order to prevent any one else from winning the challenge by basically copying the answer.
How it works:

We define a Listable pure function. Listable functions are automatically applied to the elements of a list argument (recursively) instead of the list itself, so calling f on the structured list will basically return a list of the same structure with each integer i replaced by f[i].
We store the value list in the global m and a counter in i.
Each time we call f (regardless of the argument) we return the next element of m.

CJam, 43 37 35 33 bytes
This one is a direct conversion of my JS answer. A bit long, most of which is taken up by type detection.
q~:B;{{_`La`&{F}{;BW):W=}?}%}:F~`

Takes the two input arrays on two lines of STDIN like
[[[1 3] 2] [1 4] 12 [] [[0 0] [5 [7]]]]
[1 1 0 1 0 0 0 0 1 1]

and outputs to STDOUT like
[[[1 1] 0] [1 0] 0 "" [[0 0] [1 [1]]]]

Try it online here

Haskell, 113 104 bytes (86 + 18 from datatype declaration)
data N=I Int|L[N]
L[]!v=(L[],v)
L(a:b)!v|(c,w)<-a!v,(L d,u)<-L b!w=(L$c:d,u)
_!(n:m)=(I n,m)
s#v=fst$s!v

Haskell does not have a built-in nested array datatype, so I had to roll my own. For this reason, the program contains only pattern matching and explicit structural recursion. The last test case reads
L[I 0,L[I 1,L[]],L[L[]],L[I 2,I 3],L[]]#[1,6,1,8]

and evaluates to
L[I 1,L[I 6,L[]],L[L[]],L[I 1,I 8],L[]]

Rebol - 87 66 60
f: func[a[block!]b][map-each n a[any[attempt[f n b]take b]]]

Ungolfed:
f: func [a [block!] b] [
    map-each n a [
        any [
            attempt [f n b]
            take b
        ]
    ]
]

Example:
>> f [0 [1 []] [[]] [2 3] []]   [1 6 1 8]
== [1 [6 []] [[]] [1 8] []]

C#, 225 + 13 = 239 185 + 35 = 220 172 + 35 = 207 bytes
Requires this:
using System;using o=System.Object;

Accepts object[]s as arguments.
o[]u(o[]a,o[]b){var c=a;int i=0;Action<o[],o[]>d=null;d=(e, f)=>{for(int j=0;j<e.Length;j++){if(e[j]is int){f[j]=b[i];i++;}else{d((o[])e[j],(o[])f[j]);}}};d(a,c);return c;}

Ungolfed code:
object[] Unflatten(object[] structure, object[] values)
{
    var c = structure;
    int i = 0;
    Action<object[], object[]> recursiveFunc = null;
    recursiveFunc = (e, f) =>
    {
        for (int j = 0; j < e.Length; j++)
        {
            if (e[j] is int)
            {
                f[j] = values[i]; i++;
            }
            else
            {
                recursiveFunc((object[])e[j], (object[])f[j]);
            }
        }
    };
    recursiveFunc(structure, c);
    return c;
}

You can shorten it a bit more by using using o=System.Object and replacing all instances of object with simply o. http://msdn.microsoft.com/en-us/library/sf0df423.aspx

@Kroltan Great tip, thanks!

Clone is shallow. If modification of the inputs is allowed, you don't need to clone at all. If it's not allowed, you need proper cloning.

@CodesInChaos I see. As modifying the input array is allowed, I removed the clone. Thanks!

Python 2, 64 bytes
def g(N,L):f=lambda N:L.pop(0)if`N`<":"else map(f,N);return f(N)

I heard you like lists in lists so I put functions in functions.
Edit: Looking at grc's answer now I realise that was completely unnecessary. Oh well...

SWI-Prolog 82
f([],A,[],A):-!.
f([H|T],A,[J|U],B):-(is_list(H),!,f(H,A,J,C);A=[J|C]),f(T,C,U,B).

Sample run:
?- f([[[1,3],2],[1,4],12,[[0,[],0],[5,[7]]]],[1,1,0,1,0,0,0,0,1,1],R,[]).
R = [[[1,1],0],[1,0],0,[[0,[],0],[1,[1]]]].

The last [] in the query is for checking for mismatched number of elements, which doesn't seem to be necessary in this question.

What makes the cuts (and, by extension, the expensive is_list) necessary?

@UnrelatedString: Feel free to edit the answer directly if you found them unnecessary to get the right answer. My Prolog was bad back then (I use library and cuts extensively) and even more rusty these days.

Jelly, 1 byte
ṁ

Try it online!
Jelly's mold builtin does this exactly. Takes input in reversed order (i.e. the flat list first)

Jelly, 7 bytes
ßḢ}ŒḊ?€

Try it online!
Non-builtin is still pretty short. Takes input in normal order (flat list second)
How it works
ßḢ}ŒḊ?€ - Main link. Takes l on the left and r on the right
      € - Over each element k in l:
     ?  -   If statement:
   ŒḊ   -   Condition: Depth. This yields 0 for integers and non-zero for lists
ß       -   Then: Recurse with k on the left and r on the right
 Ḣ}     -   Else: Pop and return the first element of r

Erlang, 116 93 Bytes
f(R,F)->put(n,F),[g(X)||X<-R].
g([H|T])->[g(H)|g(T)];g([])->[];g(E)->[H|T]=get(n),put(n,T),H.

Uses two impure functions f and g. f manipulates the process dictionary by setting n to the flat list and maps each element of the nested list to g(X). g then sets n to the tail of the flat list every time it encounters a non-list value and returns the head of the flat list.

Powershell: 115
the input array is $i, the mapping is $m, output is $o
$h={if($_.GetType().IsArray){if($_.c -eq 0){,@()}else{,@($_|%{.$h})}}else{$m[$c++]}};$i|%{$o=@();$c=0}{$o+=,(.$h)}

$h is a string containing the recursive function, and you can execute code contained in a string with .$h... And it would be 30 bytes shorter if powershell didn't insist on flattening single value arrays to scalars, and an array with a single null value to null
and a handy array structure viewer for verifying results
$j={if($_.GetType().IsArray){write-host '(' -n;($_|%{.$j});write-host ')' -n}else{write-host "$_" -n}};write-host '(' -n;$o|%{(.$j)}; write-host ')' -n;

edit: 149
save as unflatten.ps1:
$m=[array]$args[1];$h={if($_.GetType().IsArray){if($_.c -eq 0){,@()}else{,@($_|%{.$h})}}else{$m[$c++]}};$args[0]|%{$o=@();$c=0}{$o+=,(.$h)};echo $o;

edit: 136, inline output array creation and write-output
$m=[array]$args[1];$h={if($_.GetType().IsArray){if($_.c -eq 0){,@()}else{,@($_|%{.$h})}}else{$m[$c++]}};echo(,@($args[0]|%{$c=0}{.$h}))

call with .\unflatten.ps1 [input array] [mapping array]
the output is written to the pipeline- so run this first:
Function View-Array{
Param([Parameter(ValueFromPipeline=$True,ValueFromPipelinebyPropertyName=$True)]
      [array]$o)

    PROCESS{
    $j={if($_.GetType().IsArray){write-host '(' -n;($_|%{.$j});write-host ')' -n}else{write-host "$_" -n}};
    write-host '(' -n;$o|%{(.$j)}; write-host ')' -n;
    }
}

and run with
.\unflatten.ps1 [input array] [mapping array] | View-Array

C#, (40+123)=163 bytes OR (67+81)=148 bytes
C# suffers from its static typing and long namespaces here.
Array method
Using statements:
using o=System.Object;using System.Linq;

Code:
o[] u(o[] x,o[] y){int i=0;Func<o[],o[],o[]> f=null;f=(a,b)=>a.Select(e=>e is int?b[i++]:f((o[])e,b)).ToArray();return f(x,y);}

Stack method (uses the Stack structure instead of arrays)
Using statements:
using s=System.Collections.Generic.Stack<object>;using System.Linq;

Code:
System.Func<s,s,s>f=null;f=(a,b)=>new s(a.Select(e=>e is int?b.Pop():f((s)e,b)));

First attempts, first code golf here.

Perl 5, 49 bytes
First argument is the template structure, second is the values.
sub u{($t,$l)=@_;ref$t?[map{u$_,$l}@$t]:shift@$l}

Test Program
use Test::More;
use Test::Deep;

sub u{($t,$l)=@_;ref$t?[map{u$_,$l}@$t]:shift@$l}

cmp_deeply u([[[1,3],2],[1,4],12,[[0,0],[5,[7]]]],[1,1,0,1,0,0,0,0,1,1]),[[[1,1],0],[1,0],0,[[0,0],[1,[1]]]];
cmp_deeply u([[[0,0],0],[0,0],0,[[0,0],[0,[0]]]],[1,1,0,1,0,0,0,0,1,1]),[[[1,1],0],[1,0],0,[[0,0],[1,[1]]]];
cmp_deeply u([], []), [];
cmp_deeply u([[]], []), [[]];
cmp_deeply u([0,1,2,3], [5,1,0,5]), [5,1,0,5];
cmp_deeply u([[[[[0]]]]], [123]), [[[[[123]]]]];
cmp_deeply u([0,[1,[]],[[]],[2,3],[]], [1,6,1,8]), [1,[6,[]],[[]],[1,8],[]];
done_testing;

R, 6 bytes
relist

Try it online!
relist performs the exact operation described here; and has been included since R 2.6.0 (released Oct. 3, 2007).

Vyxal, 1 byte
•

Try it Online!
Same as Jelly

Appleseed, 136 bytes
(def M(q((S D)(if S(if(type?(head S)Int)(cons(head D)(M(tail S)(tail D)))(cons(M(head S)D)(M(tail S)(drop(length(flatten(head S)))D))))(

Defines a recursive function that takes two lists. Try it online!
Ungolfed/commented
; Define mold
(def mold
  ; as a function of two arguments, the nested list representing the structure
  ; and the flat list containing the data
  (lambda (shape data)
    ; If the shape list is nonempty:
    (if shape
      ; If its first element is an int:
      (if (type? (head shape) Int)
        ; Construct the result list from
        (cons
          ; the first element of the data list
          (head data)
          ; followed by a recursive call with all but the first element of both lists
          (mold (tail shape) (tail data)))
      ; Else, its first element is a list:
        ; Construct the result list from
        (cons
          ; a recursive call with the first element of the shape list
          (mold (head shape) data)
          ; followed by a recursive call with
          (mold
            ; all but the first element of the shape list
            (tail shape)
            ; and all but the first N elements of the data list, where N is the number
            ; of data elements used in unflattening the head of the shape list
            (drop (length (flatten (head shape))) data))))
    ; Else, the shape list is empty:
      ; Return the empty list
      nil)))

Japt, 10 bytes
Ë¶Ô?ßDÔ:Vv

Try it

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

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


text:
Bad News, Someone
In the Futurama episode The Prisoner of Benda members of the crew swap bodies with each other, with the catch that no pair of bodies can have their minds swapped more than once.
Challenge
Write a program or function that accepts a valid collection of mind-body swaps that have already occurred, and outputs a legal set of swaps that will return each mind to its original body. The identifiers for these mind-body collections must be strings which will not contain newlines. You may add up to two (distinctly named) people who have had no prior swaps to the input group. (Proof that you only need at most 2 additional bodies) However, you must add the minimum number of people required to solve the problem.
The input and output may take any clear form, however, no additional information can be stored in either. You may assume it is always valid. This is code golf, so the winner is the submission with the fewest bytes.
Examples
[('A','B'),('C','D')] -> [('A','C'),('B','D'),('A','D'),('B','C')]

['A','B'] -> ['C','D','A','C','B','D','A','D','B','C']

[('A','B'),('C','D'),('A','C'),('A','D')] -> [('B', 'E'), ('A', 'E'), ('C', 'B'), ('C', 'E')]

"A\nB\nC\nD\n" -> "A\nC\nB\nD\nA\nD\nB\nC\n"

The one from the show:
[("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Phillip","John"),("Hermes","Turanga")]

The show's solution, given below is invalid:
[("Clyde","Phillip"),("Ethan","John"),("Clyde","John"),("Ethan",Phillip"),("Clyde","Hubert"),("Ethan","Wash Bucket"),("Clyde","Leela"),("Ethan","Nikolai"),("Clyde","Hermes"),("Ethan","Bender"),("Clyde","Amy"),("Ethan","Hubert"),("Clyde","Wash Bucket")]

This is invalid because Ethan, and Clyde are unnecessary because of how little Fry Phillip, Zoidberg John and Hermes Hermes used the machine. A valid solution for this case is provided below:
[("Philip","Hubert"),("John","Wash Bucket"),("Philip","Turanga"),("John","Nikolai"),("Philip","Hermes"),("John","Bender"),("Philip","Amy"),("John","Hubert"),("Philip","Wash Bucket")]

Note that there are clearly many possible answers for any valid input. Any is valid.

Are there some names we can assume will not be used?

@feersum Nope, part of the challenge ;)

So if you were taking input as a string, you would need to handle quotation marks, commas, parentheses, and brackets in the names somehow?

@feersum You mean if you took the whole input as a string? Then yes, however, you can assume names won't have newlines between them. (editing this in now)

Your solution for the show's input doesn't work. Amy and Bender are swapped at the end. A correct solution would be [('Nikolai', 'Phillip'), ('Nikolai', 'Hubert'), ('Nikolai', 'Turanga'), ('Nikolai', 'Bender'), ('Phillip', 'Amy'), ('John', 'Wash Bucket'), ('Nikolai', 'John'), ('Phillip', 'Wash Bucket'), ('Hubert', 'John'), ('Bender', 'Hermes')]

@Jakube Sorry, it seems that I made a typo when entering in the situation for the show. I believe it is fixed now, and the solution is ok.

Python 3: 328 character (slow), 470 character (fast)
Probably a bit too long for a serious answer.
Slow and short code:
from itertools import*
def d(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 n=list(n)
 while 1:
  for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)):
   u=n[:];j=0
   for s in Q:d(u,s)
   for s in t:
    j+=1;d(u,s)
    if n==u:return t[:j]
  n+=[''.join(n)]

d(u,s) applies a swap s to u. In the main method f(Q), I first generate the list of all persons n using set operations and converting the result back to a list. The while 1-loop is of course not a infinity loop. In it, I try too solve the problem using the persons I have in n. If it is not successful, I add another person by combining all names n+=[''.join(n)]. Therefore the while 1-loop is executed at most 3 times (see proof in the question).
The solving of the problem is done bruteforce. I generate all swaps that are legal and try all permutations for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)). If each person is in it's own body, I return the sequence of swaps.
Usage:
print(f([('A','B'),('C','D')]))
print(f([('A','B')]))
print(f([('A','B'),('C','D'),('A','C'),('A','D')]))

The example from futurama takes way too long. There are 9 persons, so there are 36 possible swaps and 28 of them are legal. So there are 26! legal permutations.
Faster code
def w(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 while 1:
  n=list(n);u=n[:];l=len(n)
  for s in Q:w(u,s)
  for d in range((l*l-l)//2-len(Q)+1):r(n,u,Q,[],d)
  n+=[''.join(n)]
def r(n,u,Q,t,d):
 m=0;v=u[:];l=len(u)
 for i in range(l):
  if n[i]!=v[i]:m+=1;w(v,(n[i],v[i]))
 if m<1:print(t);exit()
 for i in range(l*l):
  s=n[i//l],n[i%l]
  if m<=d and i//l<i%l and not set([s,s[::-1]])&set(Q+t):v=u[:];w(v,s);r(n,v,Q,t+[s],d-1)

The function f(Q) has an iterative deepening approach. It first tries depth=0, then depth=1, until depth=(l*l-l)//2-len(Q), which is the maximal number of legal moves. Like the slower code it then adds another person and tries again.
The recursive function r(n,u,Q,t,d) tries to solve the current position u with d swaps. n is the solved position, Q the input moves and t the moves already done. It first calculates an lower bound of swaps m needed (by solving the state with legal and illegal swaps). If m == 0, all persons are in the correct body, so it prints the solution t. Otherwise it tries all possible swaps s, if m<d (pruning), d>1 (which is already included in m<d, i//l<i%l (don't allow swaps like ('A','A') or ('A','B') and ('B','A')) and not set([s,s[::-1]])&set(Q+t) (s hasn't been performed yet).
Usage:
f([("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Philip","John"),("Hermes","Turanga")])

It finds the optimal swaps for the futurama problem in about 17 seconds on my laptop using pypy and about 2 minutes without pypy. Notice that both algorithms outputs different solutions, when calling it with the same parameter. This is because of the hashing algorithm of a python-set. n stores the person each time in a different order. Therefore the algorithm may be faster or slower each run.
Edit: The original futurama test case was wrong, the corrected test case has an optimal solution of 9 instead of 10, and is therefore faster. 2 seconds with pypy, 7 seconds without.


text:
What year is it?
It is December 2014, and 2015 has almost started. However, it appears not everyone has realized this.

But the people of PPCG come to the rescue!
Input
Your program is given a grid like the one one the wall, where days that are in the month December look different from those in November and January. Each week starts with Sunday and ends with Saturday.
Days within the month are represented by a #. Days that fall outside the month are represented by a  (space, ASCII code 32). Each week is on a separate line. Lines are separated by a newline character (\n). Your program may require either the ommission or inclusion of a newline at the end of the input.
For example, this is the input for December 2009:
  #####
#######
#######
#######
#####

The calendar is always of the month December.
Task
Given the input, you must find the year associated with the calendar. Since there are multiple years for which a calendar matches, you must return the year (before 2015) that is the closest to 2015. (Excluding 2015 itself.)
Your program must produce the correct output for any year < 2015, excluding those which have a calendar layout for December that is equal to that of another year (before 2015) closer to 2015.
If the year is < 2014, you must also calculate the difference of the year to 2014. For example, for 2012 the difference is 2.
Output
Your program's output must be:

The text: Your calendar is for <year>. (Note: since this was originally spelled as “calender“, I’ll accept that spelling as well.)
Followed by a newline (\n or \r\n).
Followed by the text: It's almost 2015.
If the year is < 2014, this must be followed by the text: You're <difference> years behind. This must be on a separate line.
Followed by a newline (\n or \r\n).
Followed by the text: Go buy a new calendar!
Optionally followed by a newline (\n or \r\n).

Rules

You can choose whether you want to receive the calendar as a command-line argument (e.g. yourprogram.exe <calendar>) or prompt for user input.
You may assume your program won't receive invalid input. Invalid input includes calendar layout for which there exists no year.
The shortest code (in bytes, in any language) wins.
Any non-standard command-line arguments (arguments that aren't normally required to run a script) count towards the total character count.
What your program must not do:

Depend on any external resources.
Depend on having a specific file name.
Output anything other than the required output.
Take exceptionally long to run. If your program runs over a minute on an average home user's computer, it's invalid.

Your program must not be written in a programming language for which there did not exist a publicly available compiler / interpreter before this challenge was posted.

Examples
Input:
  #####
#######
#######
#######
#####

Output:
Your calendar is for 2009.
It's almost 2015.
You're 5 years behind.
Go buy a new calendar!

Input:
 ######
#######
#######
#######
####

Output:
Your calendar is for 2014.
It's almost 2015.
Go buy a new calendar!

Input:
      #
#######
#######
#######
#######
##

Output:
Your calendar is for 2012.
It's almost 2015.
You're 2 years behind.
Go buy a new calendar!

Phew. Managed to post it 6 seconds before 2014 was over in UTC (which is used by SE). Also, Happy new year everybody!

Say, hypothetically, that 2016 and 2009 have the same shape. Then which one is the closest? (i.e. do you mean closest by absolute distance, or closest but earlier than 2015?)

@SP3000 The latter. I've edited the post to clarify.

For the second test case, Dec 1 2014 was on a Monday but your calendar shows it start from a Sunday. Is this correct?

@Sp3000 That was an error. I've fixed it, thanks.

Is it really necessary to spell calendar two different ways in the output?

"You can choose whether you want to receive the fraction as a command-line argument (e.g. yourprogram.exe 2/5)"... What?

@feersum Both were errors. The second one is because I copied some of the rules from this question of mine. I'll fix them.

@feersum That looks like an old mistake that wasn't corrected in the examples yet. The text: Your calendar is for <year>. (Note: since this was originally spelled as “calender“, I’ll accept that spelling as well.)

@nyuszika7h I've already corrected those errors. I added the text you cite because the change would otherwise invalidate existing answers.

@user2428118 I know that's why you added it. But the examples still said "calender" in a few places.

adding kolmorogov-complexity tag because over half the bytes in the best entries are dedicated to representing the static strings.

CJam, 126 bytes
"Your calendar is for "2e3q'##"DE9AB6C"=~+".
It's almost "2015_(".
You're 5 years behind"9@5$-:TtTg*".
Go buy a new calendar!"

Python 3, 178 bytes
s=input();i=42157313>>s.index("#")*4&15;print("Your calendar is for %d.\nIt's almost 2015.\n%sGo buy a new calendar!"%(2014-i,(i>0)*("You're %d year%s behind.\n"%(i,"s"*(i>1)))))

A simple lookup table based on the location of the first #.
Expanded:
s=input()
i=42157313>>s.index("#")*4&15
print("Your calendar is for %d.\nIt's almost 2015.\n%sGo buy a new calendar!"\
    %(2014-i,(i>0)*("You're %d year%s behind.\n"%(i,"s"*(i>1)))))

Perl - 187
$ARGV[0]=~/^( *)/;my@a=(7,8,3..5,0,6);my$b=($a[length$1]+2006);print"Your calendar is for $b.\nIt's almost 2015.\n".($b<2014?"You're ".2014-$b." years behind.\nGo buy a new calendar!":"")

"." and "-" have the same operator precedence, so you need parenthesis around "2014-$b".

The output for at least 2014 is incorrect.

@nutki Aah, I thought I fixed that already.

Perl 5: 137 143
#!perl -p
$_="Your calendar is for ".(2014-($%=w834506&s/#/?/r)).".
It's almost 2015.
".("You're $% years behind.
")x!!$%."Go buy a new calendar!"

Previous approach:
#!perl -p
/#/;$_="Your calendar is for ".(2014-($b=1558279/9**"@-"%9)).".
It's almost 2015.
".("You're $b years behind.
")x!!$b."Go buy a new calendar!"

Calendar on standard input (only the first line is significant of course)
perl 2014.pl <<<" ######"

C#, 384, 363 325 Bytes
C# Time, please tell me if i missed out on one of the rules etc.
string a(string s){var l=s.IndexOf('#');var x=(DayOfWeek)Enum.Parse(typeof(DayOfWeek),""+l);l=1;for(;;){var y=DateTime.Now.Year-l;var t=(new DateTime(y,12,1).DayOfWeek==x)?"Your calendar is for "+y+"\nIt's almost 2015\n"+((y < 2014)?"You're "+--l+"years behind\n":"")+"Go buy a new calendar":null;if(t!=null){return t;}l++;}}

Input
" ######"
"#######"
"#######"
"#######"
"#####  "

Output
"Your calendar is for 2014
 It's almost 2015
 Go buy a new calendar

Input 2
"  #####"
"#######"
"#######"
"#######"
"#####  "

Output 2
"Your calendar is for 2009
 It's almost 2015
 You're 5 years behind
 Go buy a new calendar"

Edit: Updated, managed to remove some bytes

The punctuation is missing from your output.

C# 235
minified:
class P{static void Main(string[] a){var y=new[]{1,0,5,4,3,8,2}[a[0].IndexOf('#')];var z=2014-y;System.Console.Write("Your calendar is for "+z+"\nIt's almost 2015.\n"+(z>0?"You're "+z+" years behind.":"")+"\nGo buy a new calendar!");}}

Ungolfed
class P
{
    static void Main(string[] a)
    {
        var y = new[]{1,0,5,4,3,8,2}[a[0].IndexOf('#')];
        var z = 2014-y;
        System.Console.Write("Your calendar is for "+z+"\nIt's almost 2015.\n"+(z>0 ? "You're "+z+" years behind.":"")+"\nGo buy a new calendar!");
    }
}

Well, the language is verbose :)

Your class and Main don't have to be public. Also, you can easily rename Program to P. That should save you some characters :)

20 characters indeed, thanks :)

You can save a few characters by changing how y is computed, if you index a string you can save the syntax required to describe the array (i.e. var y = "1054382"[index]-48 (0 is ASCII 48)). y can also be inlined into the z calculation for further savings.

Java, 243 bytes
It's a verbose language :-)
class A{public static void main(String[]s){int y=2005+new int[]{8,9,4,5,0,6,7}[s[0].indexOf("#")],d=2014-y;System.out.print("Your calendar is for "+y+".\nIt's almost 2015.\n"+(d>0?"You're "+d+" years behind.\n":"")+"Go buy a new calendar!");}}

Unminified
class A {
    public static void main(String[] s) {
        int y = 2005 + new int[]{8,9,4,5,0,6,7}[s[0].indexOf("#")],
            d = 2014 - y;
        System.out.print("Your calendar is for " + y + ".\nIt's almost 2015.\n"
            + (d > 0 ? "You're " + d + " years behind.\n" : "") + "Go buy a new calendar!");
    }
}

PHP, 215 181 bytes
Lookup table, 181 bytes
Due to short array syntax, only works on PHP 5.4+:
function a($i){$y=2005+[8,9,4,5,0,6,7][strpos($i,'#')];$f=2014-$y;echo "Your calendar is for $y.\nIt's almost 2015.\n".($f?"You're $f years behind.\n":'')."Go buy a new calendar!";}

Unminified
function a($input) {
    $year = 2005 + [8,9,4,5,0,6,7][strpos($input, '#')];
    $difference = 2014 - $year;
    echo "Your calendar is for $year.\nIt's almost 2015.\n" . ($difference ? "You're $difference years behind.\n" : '') . "Go buy a new calendar!";
}

Original, 215 bytes
Works with most (if not all) versions of PHP 5:
<?function a($c){$y=2015;$f=-1;do{$f++;$d=strtotime(--$y."-12-1");}while(date(w,$d)!=strpos($c,'#'));echo"Your calendar is for $y.\nIt's almost 2015.\n".($f?"You're $f years behind.\n":'')."Go buy a new calendar!";}

Unminified
<?php

function a($input) {
    $year = 2015;
    $difference = -1;
    do {
        $difference++;
        $date = strtotime(--$year . "-12-1");
    } while (date('w', $date) != strpos($input, '#'));
    echo "Your calendar is for $year.\nIt's almost 2015.\n" . ($difference ? "You're $difference years behind.\n" : '') . "Go buy a new calendar!";
}

CoffeeScript, 211 177 bytes
Similar to my PHP answer, but CoffeeScript doesn't have do-while loops nor does it have a short ternary operator:
a=(i)->y=2015;f=-1;loop(f++;d=new Date y--+"-12-01";break if d.getDay()==i.indexOf '#');"Your calendar is for "+y+".\nIt's almost 2015.\n"+(if f then"You're "+f+" years behind.\n"else'')+'Go buy a new calendar!'

Unminifed
a = (i)->
    y = 2015
    f = -1
    loop
        f++
        d = new Date y-- + "-12-01"
        break if d.getDay() == i.indexOf '#'
    "Your calendar is for " + y + ".\nIt's almost 2015.\n" + (if f then "You're " + f + " years behind.\n" else '') + 'Go buy a new calendar!'

Shortened by using a lookup table:
a=(i)->y=[8,9,4,5,0,6,7][i.indexOf '#']+2005;f=2014-y;"Your calendar is for "+y+".\nIt's almost 2015.\n"+(if f then"You're "+f+" years behind.\n"else'')+'Go buy a new calendar!'

JavaScript (ES6), 199 170 bytes
I'm not used to writing ES6 yet so any tips would be appreciated:
Lookup table, 170 bytes
a=(i)=>{y=[8,9,4,5,0,6,7][i.search('#')]+2005,f=2014-y;return`Your calendar is for ${y}.\nIt's almost 2015.\n${f?`You're ${f} years behind.\n`:''}Go buy a new calendar!`}

Original, 199 bytes
a=i=>{y=2015,f=-1;do{f++;d=new Date(`${y--}-12-01`)}while(d.getDay()!=i.search('#'))return`Your calendar is for ${y}.\nIt's almost 2015.\n${f?`You're ${f} years behind.\n`:''}Go buy a new calendar!`}

Unminified
a = i => {
    y = 2015;
    f = -1;
    do {
        f++;
        d = new Date(`${y--}-12-01`);
    } while (d.getDay() != i.search('#'));
    return `Your calendar is for ${y}.\nIt's almost 2015.\n${f ? `You're ${f} years behind.\n` : ''}Go buy a new calendar!`;
}

JavaScript (ES5), 212 182 bytes
I've also included my original version below
Lookup array, 182 bytes
function a(i){y=[8,9,4,5,0,6,7][i.indexOf('#')]+2005,f=2014-y;return"Your calendar is for "+y+".\nIt's almost 2015.\n"+(f?"You're "+f+" years behind.\n":'')+"Go buy a new calendar!"}

Unminified
function a(i) {
    y = [8,9,4,5,0,6,7][i.indexOf('#')] + 2005;
    f = 2014 - y;
    return "Your calendar is for " + y + ".\nIt's almost 2015.\n" + (f ? "You're " + f + " years behind.\n" : '') + "Go buy a new calendar!";
}

Original, 212 bytes
function a(i){y=2015,f=-1;do{f++;d=new Date(y--+"-12-01")}while(d.getDay()!=i.indexOf('#'));return"Your calendar is for "+y+".\nIt's almost 2015.\n"+(f?"You're "+f+" years behind.\n":'')+"Go buy a new calendar!"}

Unminified
function a(i) {
    y = 2015;
    f = -1;
    do {
        f++;
        d = new Date(y-- + "-12-01");
    } while (d.getDay() != i.indexOf('#'));
    return "Your calendar is for "+y+".\nIt's almost 2015.\n" + (f ? "You're "+f+" years behind.\n" : '') + "Go buy a new calendar!";
}

Ruby, 174
def a(i)y=2005+[8,9,4,5,0,6,7][i.index('#')];d=2014-y;puts"Your calendar is for #{y}.\nIt's almost 2015.\n"+(d>0?"You're #{d} years behind.\n":'')+"Go buy a new calendar!"end

PHP, 145 bytes
two linebreaks behind the closing tag because PHP will ignore the first one
Your calendar is for <?=2014-$y=_1054382[1+strspn($argv[1]," ")],".
It´s almost 2015.",$y?"
You're $y years behind.":""?>

Go buy a new calendar!

takes input from command line argument;
requires PHP 5.6 (released 18th Dec 2014) or later for indexing the string literal.

SmileBASIC, 159 bytes
DEF C C
Y=VAL("2834501"[INSTR(C,"#")])?"Your calender is for ";2014-Y;".
?"It's almost 2015.
IF Y THEN?"You're ";Y;" years behind.
?"Go buy a new calendar!
END

C# (Visual C# Interactive Compiler), 178 175 172 bytes
s=>{int p=2014,a=p-"1054382"[s.IndexOf("#")]+48;Write($"Your calendar is for {a}.\nIt's almost 2015.{(p-a>0?$"\nYou're {p-a} years behind.":"")}\nGo buy a new calendar!");}

Try it online!