text:
Goldbach's conjecture
Write a program that prompts the user for an even integer greater than 2.
Given Goldbach’s conjecture that every even integer greater than 2 can
be expressed as the sum of two primes, print out two prime numbers which, when
added together, provide the requested even number.
Edit: the program only has to print A PAIR of primes, not all.
For example:
4 : 2 + 2
6: 3 + 3
8: 3 + 5
10: 5 + 5 or 3 + 7

"only has to print a pair of primes" Does that mean we are allowed to print more pairs?

I suppose if it shortens the length of your code, but it should be organized

APL, 34 or 44 bytes
The first version is 34 symbol long and is restricted to characters from the original single-byte APL charsets, such as the one still supported in Dyalog APL:
↑c/⍨n=+/¨c←,∘.,⍨v/⍨~v∊v∘.×v←1↓⍳n←⎕

Explanation:
                               n←⎕   ⍝ ask for a number, store as n
                          v←1↓⍳n     ⍝ generate all integers from 2 to n
                      v∘.×v          ⍝ compute the product table of any two such integers
                v/⍨~v∊               ⍝ select those that don't appear in the product table
         c←,∘.,⍨                     ⍝ generate all possible pairs of these primes
    n=+/¨c                           ⍝ check which pairs have a sum equal to n
↑c/⍨                                 ⍝ take the first that does

The second version is only 22 symbol long, because it exploits the π function to check for prime numbers, but that's only available in NARS2000 which uses Unicode, so the byte count is 44 in UCS-2:
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1

Explanation:
                   ⎕    ⍝ ask for a number N
                  ⍳ -1  ⍝ generate all naturals from 1 to N-1
             (⍪,⌽)      ⍝ arrange it into a table of all pairs of naturals with sum N
     {∧/0π⍵}            ⍝ check which pairs are made of all primes
2⍴(⌿⍨       )           ⍝ return the first pair that does

Examples
(⎕: is the prompt asking for a number)
      2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
      4
2 2
      2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
      6
3 3
      2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
      8
3 5
      2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
      124
11 113

Would ¯2π⍳2πn work as a prime generator?

@Oberon what does the π operator do exactly?

Dyadic π switches with ⍺: ¯2πx calculates the xth prime, ¯1πx is the first prime less than x, 0πx tests x for primality, 1πx is the first prime greater than x, 2πx is the number of primes less than x, 10πx is the number of divisors of x, 11πx is the sum of all divisors of x, 12πx and 13πx are the Möbius and totient function, respectively. Last but not least, the monadic πx returns the prime factorization of x.

@Oberon that's specific to NARS2000, isn't it? Seems to be an interesting interpreter. I'll try it out and revise my answer.

@Tobia It is? Sorry then. I saw it referenced somewhere, but they never mentioned NARS2000. Good to know.

@Oberon that's a really nice addition. I should add that to my keyboard layout.

2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1 has 22 characters, but 41 bytes (UTF-8). According to the blurb on the code-golf tag, the scoring criterion is byte-count.

@r.e.s. @Tobia as soon the code became NARS2000 specific (using π), it would need to be in UCS-2 (i.e. exactly 2 bytes per character) as this is the only available encoding for NARS2000. Other APLs at least have an option of staying within 256 characters. Dyalog APL currently has three symbols that force non-256 char encoding; ⍠⍤⌸, but as long as one doesn't use those, 1 byte/char is justified.

@Adám Agreed. Fixed.

Python 2, 75 71 bytes
n=input();k=m=1;p={0}
while{n-k,k}-p:m*=k*k;k+=1;p|={m%k*k}
print n-k,k

Test it on Ideone.
How it works
We use a corollary of Wilson's theorem:

At all times, the variable m is equal to the square of the factorial of k - 1; k starts at value 1 and m at value 0!² = 1. The set p will consist of 0 and all prime numbers up to the current value of k.
In each iteration, we first check if both n - k and k belong to p, which is true if and only if the set difference of {n-k, k} and p is empty. If it is, the condition is falsy and the loop continues.
Note that k > 0, and {n - k, k} will satisfy the condition for some positive value of n - k (assuming that Goldbach's conjecture is true), so the 0 in p won't lead to false positives.
In the loop, we update k and m. The new value of m is m × k² = (k - 1)!² × k² = k!², and the new value of k is k + 1, so m = (k - 1)!² still holds before and after the update.
Then, we perform set union to add the value of m % k × k to p. By the corollary of Wilson's theorem, this will add 1 × k = k if k is prime and 0 × k = 0 if not.
When the loop ends, we print the last values of n - k and k, which will be primes with sum n.

How on earth does that prime generating algorithm work?

@LeakyNun I've added an explanation.

Oh... that is genius.

Ruby 2.0 (65)
require'prime'
n=gets.to_i
Prime.find{|i|p [i,n-i]if(n-i).prime?}

PHP - 73 bytes
<?for(;@($n%--$$n?:$o=&$argv[1]>$$n=++$n)||${++$b}^${--$o};);echo"$b+$o";

Input is taken as a command line argument.
Sample usage:
$ php goldbach.php 7098
19+7079

GolfScript 41 33  32
~(,2>.-1%]zip{{.,2>\{\%!}+,},!}?

Accepts command line argument e.g.
echo "14" | ruby golfscript.rb goldbach.gs
-> [2 12]

Finds all relevant partitions of the input number with:
(,2>.-1%]zip  #If only zip were a one-character command!  It is so often useful.

and then finds the first partition where no numbers are NOT prime with:
{np,!}? #For each partition, filter down to elements that are not prime, and only accept if there are no such results (since [] is falsey).

where the composite-checking block np is:
{.,2>\{\%!}+,}

this block filters down to all numbers that evenly divide a given number.  If there are no such numbers (so the number is prime), the result is [], which is falsey in GolfScript.

R, 170 112 83 characters
a=scan();b=2:a;p=b[rowSums(!outer(b,b,`%%`))<2];q=p[(a-p)%in%p][1];cat(a,":",q,a-q)

Indented:
a=scan() #Take user input as a numeric
b=2:a
p=b[rowSums(!outer(b,b,`%%`))<2] #Find all primes from 2 to user input
q=p[(a-p)%in%p][1] #Check which a-p also belong to p and takes the first one
cat(a,":",q,a-q)

Usage:
> a=scan();b=2:a;p=b[rowSums(!outer(b,b,`%%`))<2];q=p[(a-p)%in%p][1];cat(a,":",q,a-q)
1: 72
2:
Read 1 item
72 : 5 67

Old solution at 112 characters, for posterity
a=scan();b=2:a;p=b[rowSums(!outer(b,b,`%%`))<2];w=which(outer(p,p,`+`)==a,T);cat(a,":",p[w[1,1]],p[w[1,2]])

Indented:
a=scan()
b=2:a
p=b[rowSums(!outer(b,b,`%%`))<2]
w=which(outer(p,p,`+`)==a,T) #Find the index of valid combinations
cat(a,":",p[w[1,1]],p[w[1,2]]) #Prints the first valid combination

This is both crazy and genial!!

perl 6:  69
$/=get;for grep &is-prime,^$/ {exit say $_,$_-$/ if ($/-$_).is-prime}

JavaScript (ES6) (Regex), 105
a=/^(xx+?)(?!(xx+)\2+$)x*(?=\1$)(?!(xx+)\3+$)/.exec("x".repeat(prompt()));alert(a[1].length+"+"+a[0].length)

Now you have a regex that tests the Goldbach conjecture, which has low requirement on special features (basic back-reference support, positive and negative look-ahead).
This uses String.prototype.repeat(), which is part of EcmaScript 6th edition proposal. Currently, this code only works on Firefox.
I really need a better language that has terse command when working with regex...

Python - 107
Basically an improvement on the second part of nutria's answer
(I ran this on 2.7 but I think it should also work for 3.x)
p=lambda x:all(x%i!=0 for i in range(2,x))
n=input()
for i in range(2,n-1):
    if p(i)&p(n-i): print i,n-i

Are the newlines, and spaces after : mandatory?

The tab could be reduced to a space, and the space before the print could be removed (shaves off 4 bytes).

Sage, 60
Similar in score and feel to r.e.s.'s solution, but I think it's different enough to post.
i=n=input()
while not{i,n-i}<set(primes(n)):i-=1
print i,n-i

Scala, 286 192 172 148 chars
Not the fastest but it works. Call g(10) to obtain the list of goldbach pairs for 10.
def g(n:Int)={def p(n:Int,f:Int=2):Boolean=f>n/2||n%f!=0&&p(n,f+1)
s"$n : "+(for(i<-2 to n/2;j=n-i if p(i)&&p(j))yield s"$i + $j").mkString(" or ")}

Conversion to C++ is straightforward.

newLISP - 169 148 chars
(define(p n)(=(length(factor n))1))
(define(g n)(when(even? n)(for(i 3 n 2)
(and(p i)(p(- n i))(println n {: } i { }(- n i))))))
(g(int(read-line)))

includes the code to run it. The results are over-generous...
72: 5 67
72: 11 61
72: 13 59
72: 19 53
72: 29 43
72: 31 41
72: 41 31
72: 43 29
72: 53 19
72: 59 13
72: 61 11
72: 67 5

C - 139 129 characters
a,b;i(x,y){return x>y?x%y?i(x,y+1):0:x>1;}main(){scanf("%i",&a);for(b=a/2;b-->1;)i(b,2)&&i(a-
b,2)&&printf("%i:%i+%i\n",a,b,a-b);}

You can shave 8 characters by removing the int declarations in your function i.  You can save another 2 characters by removing the if and adding in another double ampersand: i(b,2)&&i(a-b,2)&&printf(...)

Thanks! Didn't think of that &&. (I'll never get used to argument type silencing...)

I love your use of the nested ternary.

Sage, 65 62
n=input()
i=0
p=is_prime
while p(i)*p(n-i)==0:i+=1
print i,n-i

With the above in file goldbach.sage, execute it with Sage running in a terminal:
sage: %runfile goldbach.sage

Thanks to @boothby for the p=is_prime idea.

You can get this down to 62 by setting p=is_prime.

Mathematica 56
This returns all of the solutions for the input integer.
Select[Tuples[Prime@Range@PrimePi[n = Input[]], 2], Tr@# == n &]

For example, when 1298 is input…

{{7, 1291}, {19, 1279}, {61, 1237}, {67, 1231}, {97, 1201}, {127,
    1171}, {181, 1117}, {211, 1087}, {229, 1069}, {277, 1021}, {307,
    991}, {331, 967}, {379, 919}, {421, 877}, {439, 859}, {487,
    811}, {541, 757}, {547, 751}, {571, 727}, {607, 691}, {691,
    607}, {727, 571}, {751, 547}, {757, 541}, {811, 487}, {859,
    439}, {877, 421}, {919, 379}, {967, 331}, {991, 307}, {1021,
    277}, {1069, 229}, {1087, 211}, {1117, 181}, {1171, 127}, {1201,
    97}, {1231, 67}, {1237, 61}, {1279, 19}, {1291, 7}}

As written, it returns each solution twice.
Union[Sort/@ %]

{{7, 1291}, {19, 1279}, {61, 1237}, {67, 1231}, {97, 1201}, {127,
    1171}, {181, 1117}, {211, 1087}, {229, 1069}, {277, 1021}, {307,
    991}, {331, 967}, {379, 919}, {421, 877}, {439, 859}, {487,
    811}, {541, 757}, {547, 751}, {571, 727}, {607, 691}}

Input 2, ask an oracle if it halts, prove/disprove the twin primes conjecture, win

With this MSE solution we can do it in 47 bytes: Cases[{1,1}~FrobeniusSolve~Input[],{__?PrimeQ}] or even in 42 bytes as a function: Cases[{1,1}~FrobeniusSolve~#,{__?PrimeQ}]&.

Haskell, 97C
g n=head[(a,b)|let q=p n,a<-q,b<-q,a+b==n]
p n=filter c[2..n]
c p=null[x|x<-[2..p-1],p`mod`x==0]

Explanation:

g is the "goldbach" function. Calling g n gives you the pair of primes that add up to n.
p is a function that generates a list of primes less than n.
c is the prime checker function used to define p.

Example runs:
*Main> g 4
(2,2)
*Main> g 6
(3,3)
*Main> g 8
(3,5)
*Main> g 10
(3,7)
*Main> g 12
(5,7)
*Main> map g [4,6..100]
[(2,2),(3,3),(3,5),(3,7),(5,7),(3,11),(3,13),(5,13),(3,17),(3,19),(5,19),(3,23),(5,23),(7,23),(3,29),(3,31),(5,31),(7,31),(3,37),(5,37),(3,41),(3,43),(5,43),(3,47),(5,47),(7,47),(3,53),(5,53),(7,53),(3,59),(3,61),(5,61),(7,61),(3,67),(5,67),(3,71),(3,73),(5,73),(7,73),(3,79),(5,79),(3,83),(5,83),(7,83),(3,89),(5,89),(7,89),(19,79),(3,97)]

Julia, 50 49 bytes
~=primes;n=ARGS[]|>int
(n-~n)∩~n|>extrema|>show

Try it online!
If a function were acceptable, the code could be shortened to 32 bytes:
~=primes
!n=(n-~n)∩~n|>extrema

How it works
~=primes creates an alias for the built-in primes function which returns a list of all prime numbers up to its argument. n=ARGS[]|>int parses the first command-line argument as saves it in n.
To find a suitable pair of primes, we first compute the aforementioned prime range with ~n. Then, n-~n yields all differences of these primes and n.
By intersecting (∩) the result with the prime range itself, we make sure that the remaining primes p are such that n - p is also a prime.
Finally, extrema takes the lowest and highest prime in the intersection, so their sum must be n.

Python 3 - 150 143 characters
Old version (150 characters):
p=lambda n:0 in[n % i for i in range(2,n)]
n=int(input())
[print('%d+%d'%(a, b))for b in range(2,n)for a in range(2,n)if not(a+b!=n or p(a) or p(b))]

New version (thanks to ProgramFOX):
p=lambda n:0 in[n%i for i in range(2,n)]
n=int(input())
[print('%d+%d'%(a,b))for b in range(2,n)for a in range(2,n)if not((a+b!=n)|p(a)|p(b))]

It prints every combination, for example:
4
2+2
10 7+3 5+5 3+7

| can safely be used with boolean type, so (a+b!=n)|p(a)|p(b)

Even shorter by using: print([(a,b)for b in range(2,n)for a in range(2,n)if not((a+b!=n)|p(a)|p(b))]) (prints a list of tuples, whose sum is n). Saves 8 bytes.

Also using r=range(2,n) and referencing r saves a few more.

JavaScript, 139 137 136
a=prompt();function b(n){for(i=2;i<n;i++)if(n%i<1)return;return 1}for(c=2,r=1;c<a&&r;c++)if(b(c)&&b(a-c))alert(a+": "+c+" + "+(a-c)),r=0

I think you can shave off 2 more chars by return; instead of return 0;

Julia, 62 Chars (85 with prompt)
julia> g(n)=collect(filter((x)->sum(x)==n,combinations(primes(n),2)))
g (generic function with 1 method)

julia> g(88)
4-element Array{Array{Int64,1},1}:
 [5,83]
 [17,71]
 [29,59]
 [41,47]

This doesn't prompt the user (as required), does it?

No, didn't notice that.  It would add many characters right now julia.  g(int(readline(STDIN)))

GTB, 31
For your TI-84 Calculator
`A:.5A→B@%;A,4)4$~B+1,B-1#~B,B&

No prime built-ins.
Example runs
?4
               2
               2
?6
               3
               3
?8
               3
               5
?10
               5
               5

q [116 chars]
y where all each{{2=count where 0=(x mod)each til x+1}each x}each y:{a where x=sum each a:a cross a:til x}"I"$read0 0

No inbuilt function to find prime number.
Input
72

Output
5  67
11 61
13 59
19 53
29 43
31 41
41 31
43 29
53 19
59 13
61 11
67 5

J - 35 32 char
"Prompt the user" is the bane of every J golfer. There go all my hard-earned characters!
p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1

Explained:

".1!:1]1 - Read in a string (1!:1) from input (file handle 1) and convert it to a number (".).
p:i.n=: - Assign this number to the variable n, and then take the first n primes.
+/~ - Make an addition table, n wide and n high.
i.&n, - Turn the table into a single list, and then find the index of the first occurrence of n, which exists if Goldbach's conjecture is true.
p:(n,n)#: - Retrieve the row and column from the index, and take the corresponding primes.

Usage:
   p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
666
5 661
   p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
1024
3 1021

Had the prompt not been a requirement, here's a 25 character verb:
(,~p:@#:]i.~&,+/~@:p:@i.)

Python - 206
A little late to the party but I am practicing my golfing skills.
I actually coded this before I found this question! So mine doesn't include the beautiful lambda that the other Python solutions use.
import math
def p(n):
    if n%2==0&n>2:return False
    for i in range(3,n):
        if n%i==0:return False
    return True
X=int(input())
for i in range(2,X):
    if p(i)&p(X-i):print i,X-i;break

Jelly, 8 bytes (non-competing)
_ÆRfÆR.ị

Try it online! or verify all test cases.
How it works
_ÆRfÆR.ị  Main link. Argument: n (integer)

 ÆR       Prime range; yield all primes in [1, ..., n].
_         Subtract all primes from n.
   fÆR    Filter; intersect the list of differences with the prime range.
      .ị  At-index 0.5; yield the last and first element.

Python3 version of this one -110 bytes
p=lambda x:all(x%i!=0 for i in range(2,x))
n=int(input())
for i in range(2,n-1):
 if p(i)&p(n-i): print(i,n-i)

and a super golfed version:
exec(bytes('㵰慬扭慤砠愺汬砨椥㴡‰潦⁲湩爠湡敧㈨砬⤩渊椽瑮椨灮瑵⤨਩潦⁲湩爠湡敧㈨測ㄭ㨩 晩瀠椨☩⡰⵮⥩›牰湩⡴Ⱪ⵮⥩','u16')[2:])

Welcome to Code Golf! Nice first answer.

This program does not run and it is unclear what your actual code is. Also, neither of the two programs you wrote match the bytecount you specified. Please fix your answer and properly format the code.

@Makonede i fixed the issues you found.

Your code still doesn't work, and the bytecount is still wrong. Also, like I asked, please properly format your code.

@Makonede sorry i've been testing this on my computers Python interpreter and getting the byte count from a file i store the code in on my computer.

p is still not defined. you need to add the definition of p to this program.

@Razetime thanks for noticing when i was making the answer it didn't show the first line.

ok, now that it is working, you should remove the input prompt since this is code golf. Your other supergolfed version is 199 bytes.

Both of these now take input from a predefined variable (n), which is not an allowed input method. What Razetime was suggestion was to delete the useless phrase "Enter an even number: ", not to delete the entire line and turn the code into a snippet.

Batch - 266
@echo off&setLocal enableDelayedExpansion&for /L %%a in (2,1,%1)do (set/aa=%%a-1&set c=&for /L %%b in (2,1,!a!)do set/ab=%%a%%%%b&if !b!==0 set c=1
if !c! NEQ 1 set l=!l!%%a,)&for %%c in (!l!)do for %%d in (!l!)do set/ad=%%c+%%d&if !d!==%1 set o=%%c + %%d
echo !o!

Set out neatly -
@echo off
setLocal enableDelayedExpansion
for /L %%a in (2,1,%1) do (
    set /a a=%%a-1
    set c=
    for /L %%b in (2,1,!a!) do (
        set /a b=%%a%%%%b
        if !b!==0 set c=1
    )
    if !c! NEQ 1 set l=!l!%%a,
)
for %%c in (!l!) do for %%d in (!l!) do (
    set /a d=%%c+%%d
    if !d!==%1 set o=%%c + %%d
)
echo !o!

SQL, 295 284
In postgresql:
create function c(c int) returns table (n int, m int) as $$
with recursive i(n) as
(select 2 union all select n+1 from i where n<c),
p as (select * from i a where not exists
(select * from i b where a.n!=b.n and mod(a.n,b.n)=0))
select * from p a, p b where a.n+b.n=c
$$ language sql;

Should be able to do it in half the space though, if it weren't for things like "no left outer join in recursion", "no subquery in recursion"...
Here's the output:
postgres=# select c(10);
   c
-------
 (3,7)
 (5,5)
 (7,3)
(3 rows)

postgres=# select c(88);
   c
---------
 (5,83)
 (17,71)
 (29,59)
 (41,47)
 (47,41)
 (59,29)
 (71,17)
 (83,5)
(8 rows)

Oracle SQL 11.2, 202 bytes
WITH v(x,y,s)AS(SELECT LEVEL,LEVEL,0 FROM DUAL CONNECT BY LEVEL<=:1 UNION ALL SELECT x,y-1,s+SIGN(MOD(x,y))FROM v WHERE y>1),p AS(SELECT x FROM v WHERE x-s=2)SELECT a.x,b.x FROM p a,p b WHERE:1=a.x+b.x;

Un-golfed
WITH v(x,y,s) AS
(
  SELECT LEVEL,LEVEL,0 FROM DUAL CONNECT BY LEVEL<=:1
  UNION ALL
  SELECT x,y-1,s+SIGN(MOD(x,y))FROM v WHERE y>1
)
,p AS (SELECT x FROM v WHERE x-s=2)
SELECT a.x,b.x
FROM p a,p b
WHERE :1=a.x+b.x;

Python 3, 107 bytes
b=lambda x:all(x%y for y in range(2,x))
g=lambda x,i=2:((i,x-i)if b(i)&b(x-i)else g(x,i+1))if(i<x)else 0

b(x) is a primality test for x, and g(x) recurses through numbers to find two primes that fit.

Perl 5, 58 bytes
57, plus 1 for -nE
/^(11+?)(?!(11+)\2+$)1*(?=\1$)(?!(11+)\3+$)/;say for$1,$&

Input and output are in unary. Example:
$ perl -nE'/^(11+?)(?!(11+)\2+$)1*(?=\1$)(?!(11+)\3+$)/;say for$1,$&'
1111111111
111
1111111

Hat-tip.

05AB1E, 12 bytes
ÅP©-ʒ®så}Á2£

Try it online!

Thunno 2, 7 bytes
œP2ṚæS:

Try it online!
Prints all possible pairs. If you only want one, add the h flag.
Explanation
œP2ṚæS:  # Implicit input
œP       # Filter [1..input] for primes
   Ṛ     # Combinations with replacement
  2      # with a length of two
    æS:  # Filter by sum equals input
         # Implicit output

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


text:
Six degrees of web separation
Six degrees of separation is the theory that everyone and everything is six or fewer steps away, by way of introduction, from any other person in the world.
Your challenge here is to write a program which crawls to find out what is exactly 6 links away but connected back to the starting URL through a series of links.
For example if your program is given a starting url of http://vimeo.com it would then potentially (this is a made up example) crawl to:

http://www.abc.com links to ->
http://www.widgets.com links to ->
http://www.gadgets.net links to ->
http://www.techcrunch.com links to ->
https://twitter.com/techcrunch links to ->
http://www.youtube.com/user/techcrunch (finish as we are now 6 links away from the starting URL.)

Rules:

You can choose your own starting URL.
Any programming language can be used.
You most obey sites robots.txt files and not crawl any areas sites disallow.
Each step must be a new URL from the one you are currently on.
URLS should only be visited once per crawl.
You must output the starting URL and each link followed in sequence.

Winner:

This is a popularity contest so the solution with the most up-votes wins.

If anyone thinks this would be better as some other type of competition other than code golf, please comment.

Determining whether two sites are on the same domain or not is hard. Browsers have long lists of special cases to deal with it. In order to make this a fair contest, I think you should provide a spec for whether two FQDNs should be considered to be from the same domain or not for the purposes of this question.

@BenPaton You may want to use the sandbox, especially if you are unsure about your puzzle.

Does example.co.uk count as the same domain as example2.co.uk. If not, can you specify why?

Hello I would say example and example2 count as two distinct domains in this as the strings are different in the names.

Jan's question is just a specific case of my point. I'm voting to put this question on hold for the time being so that people don't waste time writing answers which might be invalidated when the spec is clarified.

@PeterTaylor I have added a distinct domains rules clarification section. Does this cover everything?

No. You say that subdomains don't count as new domains, but you don't say why example.co.uk and example2.co.uk aren't considered as subdomains of co.uk.

@PeterTaylor I though that would be obvious? Otherwise I would have asked for 6 distinct top level domains away from the starting URL which would be really hard to find examples of.

@BenPaton, some TLDs allow registration of yourdomain.tld (these include the com, org, net, and some CCTLDs; I suspect that mil and gov are also in this category, but that might be debatable); others have their own second level domains and allow registration of third level domains (e.g. the uk CCTLD). And IIRC it's not even that simple. See also http://publicsuffix.org/list/

"most up-votes wins" is [tag:popularity-contest].

what about google.com.br vs bing.com.br vs registro.br?

google.com.br vs bing.com.br vs registro.br - these are all distinct. google.com.br -> google.com wouldn't count though

@BenPaton This is a nice idea but really needs to be ironed out a bit more. There seems to be a lot of ambiguity about the rule for distinct domains, and even parsing a robots.txt file is non-trivial.

I am surprised there has been so many questions around what constitutes a different domain. To me it seems quite simple. If I'm on bing.com a link to cnn.com is clearly a move a different domain where as another part of bing wouldn't be. Perhaps all the extra rules to clarify this only serve to confuse?

Your "rules to clarify" completely miss the point. Anyone who would attempt this question understands the difference between a domain and the path component of a URL. The part which needs clarification is how to deal with the real world messiness of the part which ICANN administrates: that is, the desired "are these subdomains of the same domain?" equivalence relationship on FQDNs.

You're thinking at the wrong level of abstraction: you say that "If I'm on bing.com ... another part of bing wouldn't be [a different domain]": but you need to think in terms of FQDNs at the level of characters, which is all a computer sees, not at the level of "As a human, I know whether or not this FQDN is part of Bing", and you need to consider the world of CCTLDs with registries whose policies have changed over time.

@PeterTaylor can you provide an example URL where if your code parsed it you wouldn't know whether to classify it as sufficiently different to one you had already examined?

foo.hanoi.vn vs bar.hanoi.vn: it's not clear from http://www.vnnic.vn/en/domain/cctld-vn?lang=en whether hanoi.vn falls under case m, although appearing in the banner image is suggestive . foo.blogspot.com.ss vs bar.blogspot.com.ss vs quux.com.ss. (Do you know South Sudan's registration policy?) How about the new Chinese language gTLD?

With foo.hanoi.vn vs bar.hanoi.vn, these would be distinct as this is similar to foo/bar.co.uk. foo.blogspot.com.ss vs bar.blogspot.com.ss would not be distinct as they are both blogspot. Chinese language domains I don't see would work any differently to .com It just needs to be distinct.中文网

Ben, with your definition of a "domain" this challenge is impossible. You say that google.com and google.com.br are to be considered the same domain. That subdomains to twitter.com are not considered new domains, but subdomains to hanoi.vn are. Not only are you having wildly varying depth levels of a "subdomain" but you also consider domains on different TLDs to be the same. Did you even know that there is no standardised technical definition of a "subdomain"? ALL domain names are considered subdomains to . as far as the DNS specification goes.

Ok I have simplified the question to try and get away from what constitutes a distinct domain. Can this be taken off hold now?

Java, 8623 bytes
It isn't perfect. It has some issues connecting to some URLs and fails to parse the robots.txt properly. However, it's a start.
package info.varden.codegolf.sixdegreeslink;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URI;
import java.net.URISyntaxException;
import java.net.URL;
import java.net.URLConnection;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    private static HashMap<String, String> entities = new HashMap<>();
    private static HashMap<String, ArrayList<String>> robotstxts = new HashMap<>();

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        String init = "";
        for (String s : args) {
            init += s + "%20";
        }
        init = init.substring(0, init.length() - 3);
        try {
            System.out.println("Resolving entites (step 1 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLlat1.ent"));
            System.out.println("Resolving entites (step 2 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLsymbol.ent"));
            System.out.println("Resolving entites (step 3 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLspecial.ent"));
            System.out.println(entities.size() + " entites resolved.\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println("Starting search from: " + init + "\n");
        IterationInfo initInfo = new IterationInfo();
        IterationInfo info = initInfo;
        try {
            initInfo.scanLink = init;
            initInfo.links.add(init);
            initInfo.domains.add(getDomain(init));
            info = getSixStepsRecursive(initInfo);
        } catch (URISyntaxException e) {
            e.printStackTrace();
        }

        long diffTime = System.currentTimeMillis() - startTime;
        long second = (diffTime / 1000) % 60;
        long minute = (diffTime / (1000 * 60)) % 60;
        long hour = (diffTime / (1000 * 60 * 60)) % 24;
        diffTime = diffTime % 1000;

        String time = String.format("%02d:%02d:%02d.%d", hour, minute, second, diffTime);
        System.out.println("\nCompleted in " + time);
        System.out.println("\nRESULTS:");
        if (info.success) {
            for (int i = 0; i < info.links.size(); i++) {
                System.out.println(info.links.get(i));
            }
        } else {
            System.out.println("Can't find six degrees step separation!");
        }
    }

    private static IterationInfo getSixStepsRecursive(IterationInfo info) {
        IterationInfo returnInfo = info;
        String[] urls = new String[0];
        try {
            String content = downloadString(info.scanLink);
            content = content.replace("\t", " ").replace("\r", " ").replace("\n", " ");
            while (content.contains("  ")) content = content.replace("  ", " ");
            urls = content.split("\\Q<a href=\"\\E");
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        for (int i = 1; i < urls.length; i++) {
            try {
                if (info.iteration == 6) {
                    returnInfo.success = true;
                    return returnInfo;
                }
                returnInfo = info;
                urls[i] = stripHTMLEntities(urls[i].split("\"")[0]);
                if (urls[i].startsWith("//"))
                    urls[i] = "http:" + urls[i];
                if (!urls[i].startsWith("http://") && !urls[i].startsWith("https://")) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Relative or non-HTTP link (" + urls[i] + ")");
                    continue;
                }
                if (!canGetRobotsTxt(urls[i])) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Blocked by robots.txt (" + urls[i] + ")");
                    continue;
                }
                if (returnInfo.links.contains(urls[i])) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Exact link already passed (" + urls[i] + ")");
                    continue;
                }
                if (returnInfo.domains.contains(getDomain(urls[i]))) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Domain already passed (" + getDomain(urls[i]) + ") (" + urls[i] + ")");
                    continue;
                }

                System.out.println("Iter " + info.iteration + " - URL valid: Distict domain (" + getDomain(urls[i]) + ") (" + urls[i] + ")");
                returnInfo.links.add(urls[i]);
                returnInfo.domains.add(getDomain(urls[i]));
                returnInfo.iteration = info.iteration + 1;
                returnInfo.scanLink = urls[i];

                returnInfo = getSixStepsRecursive(returnInfo);
                if (returnInfo.success) {
                    return returnInfo;
                }
            } catch (Exception ex) {
            }
        }
        return returnInfo;

    }

    private static boolean canGetRobotsTxt(String url) {
        try {
            URI cur = new URI(url);
            if (!robotstxts.containsKey(cur.getHost())) {
                String rtxt = downloadString("http://" + cur.getHost() + "/robots.txt");
                String[] lines = rtxt.split("\n");
                ArrayList<String> ar = new ArrayList<>();
                for (String line : lines) {
                    if (line.endsWith("\r"))
                        line = line.substring(0, line.length() - 1);
                    if (line.toLowerCase().startsWith("disallow: ")) {
                        line = line.substring(10);
                        ar.add(line);
                    } else if (line.toLowerCase().startsWith("allow: ")) {
                        line = line.substring(7);
                        ar.remove(line);
                    }
                }
                robotstxts.put(cur.getHost(), ar);
            }
            ArrayList<String> a = robotstxts.get(cur.getHost());
            for (String s : a) {
                String[] sw = s.split("\\Q*\\E");
                String s2 = "^i";
                for (String s3 : sw) {
                    s2 += "\\Q" + s3 + "\\E(.+)";
                }
                s2 = s2.substring(0, s2.length() - 4);
                Pattern p = Pattern.compile(s2);
                Matcher m = p.matcher(cur.getPath());
                if (m.find()) {
                    return false;
                }
            }
            return true;
        } catch (Exception e) {
            return true;
        }
    }

    private static HashMap<String, String> getEntitiesFromEnt(String url) throws Exception {
        HashMap<String, String> e = new HashMap<>();
        String ent = downloadString(url);
        while (ent.contains("  ")) ent = ent.replace("  ", " ");
        String[] lines = ent.split("\n");
        for (String line : lines) {
            if (line.startsWith("<!ENTITY")) {
                String[] f = line.split(" ");
                e.put("&" + f[1] + ";", f[3].substring(1, f[3].length() - 1));
            }
        }
        return e;
    }

    private static String downloadString(String url) throws Exception {
        URL cur = new URL(url);
        URLConnection conn = cur.openConnection();
        conn.setRequestProperty("User-Agent", "URLConnection/1.7 (Any system) VardenCG/3.0");
        BufferedReader in = new BufferedReader(new InputStreamReader(conn.getInputStream()));
        String content = "", line;
        while ((line = in.readLine()) != null) content += line + "\n";
        in.close();
        return content;
    }

    private static String stripHTMLEntities(String html) {
        for (Entry<String, String> e : entities.entrySet())
            html = html.replace(e.getKey(), e.getValue());
        Pattern ep = Pattern.compile("&#(\\d+);");
        Matcher m = ep.matcher(html);
        while (m.find()) {
            if (!m.group(1).equals("38"))
                html = html.replace("&#" + m.group(1) + ";", String.valueOf((char)Integer.parseInt(m.group(1))));
        }
        Pattern ep1 = Pattern.compile("&(x|X)([\\da-fA-F]+);");
        Matcher m2 = ep1.matcher(html);
        while (m2.find()) {
            if (!m.group(1).equals("26")) {
                html = html.replace("&x" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
                html = html.replace("&X" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
            }
        }
        html = html.replace("&", "\0").replace("&x26;", "\0").replace("&X26;", "\0").replace("\0", "&");
        return html;
    }

    private static String getDomain(String url) throws URISyntaxException {
        URI uri = new URI(url);
        String host = uri.getHost().toLowerCase();
        String[] subDomainTree = host.split("\\.");
        String[] commonSLs = {"ac", "co", "com", "gov", "ltd", "me", "net", "org"};
        boolean isCommonSL = false;
        try {
            String secondLevel = subDomainTree[subDomainTree.length - 2];
            for (String sl : commonSLs) {
                if (sl.equals(secondLevel)) {
                    isCommonSL = true;
                }
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            return host;
        }
        try {
            if (isCommonSL) {
                return subDomainTree[subDomainTree.length - 3] + "." +
                        subDomainTree[subDomainTree.length - 2] + "." +
                        subDomainTree[subDomainTree.length - 1];
            } else {
                return subDomainTree[subDomainTree.length - 2] + "." +
                        subDomainTree[subDomainTree.length - 1];
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            return subDomainTree[subDomainTree.length - 2] + "." +
                    subDomainTree[subDomainTree.length - 1];
        }
    }

    private static class IterationInfo {
        public ArrayList<String> domains = new ArrayList<>();
        public ArrayList<String> links = new ArrayList<>();
        public String scanLink = "";
        public int iteration = 1;
        public boolean success = false;
    }

}

Parameter used: http://codegolf.stackexchange.com/
Output: http://pastebin.no/34cd (Had to post on other site because it was too big for codegolf)
There's a lot of stuff going on here.
First of all, I have to parse HTML entities like &em &39; and &x2F. The named entities have to be translated, I do that by downloading the definitions from W3C.
I also need to figure out the host of the URL, taking into account common second level domains like co, edu etc. (.co.uk, .edu.uk, ...)
Then I need to parse robots.txt.
I don't have time to write more now, but oh well, there's my contribution.
-- bilde2910

Thanks for having a go at this challenge your code and output certainly seem valid. Well done! I'm always pleased to see someone take some time on a challenge i set. Thanks :)

@BenPaton Thank you! Just trying my best to help out. It's not perfect, but it works to a certain degree. For some reason my 700 lines of "URL failed: Banned by robots.txt" didn't make it in. Oh well.

source: Stack Exchange

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

sort: votes


text:
Golf with a bowling ball: hello world with high complexity yet short code
In this challenge, you must write a Hello World program that is both short and complex.  We measure complexity by Cyclomatic McCabe complexity, and length by the number of bytes (not characters).
Score = complexity / bytes
For example, if the cyclomatic complexity is 5 and you use 100 bytes, your score is 5/100=0.05.  If the cyclomatic complexity is 25 and you use 200 bytes, your score is 25/200=0.125.
The program shall take no input.  The program must output exactly the ASCII-encoded string:
Hello, world!
in this exact case.  This string may or may not be followed by a single newline (LF, ASCII 10).  No other text shall be output.

Is this really code bowling? Seems like golf, with an added element.

@Iszi bowling is more appropriate than golf in this case because big score wins.

@hildred Highest score wins, but the code has to be fairly short to keep a score high. Though the scoring may not be golf-like, the nature of the challenge most closely matches code golf.

@Iszi, I'm not sure whether it's really bowling, but it's certainly not golf because the scoring depends on a factor other than the length of the code.

@PeterTaylor I understand there's a factor other than length of code, but length of code is a strong enough factor in this that I think it really does fit. I'm pretty sure we've had other modified code golf challenges like this before, and I can't think of another tag that fits well enough - unless you just want to genericize it to code bowling.

@Iszi: see the tag wiki for [tag:code-golf].

Ack, I meant "genericize it to code challenge" not bowling. And it looks like the Wiki supports that.

C# - 1/3
string x = null;
Console.WriteLine(x??x??x??...??x??"Hello, world!");

Score calculation:
lim(x→x/(x*3+53))
x→∞

If you feel the need to wrap this all in a class with a Main method... it doesn't change the score.

Yes, I thought of doing something similar in GolfScript with {}/.

Since x is always initialized to null, the score here should probably be one (every time the program is executed, one path - and exactly the same path - is taken).

@primo The OP didn't specify that each path must be reachable, which would an entirely new challenge, since it would require randomization.

@KendallFrey Or, that your program follow each branch at some point.

@primo And that requires randomization, unless I'm missing something.

for(i=0;13<i;i++){case 0: ... case 1: ...}. I don't see why randomization of any kind would be necessary.

"every time the program is executed, one path - and exactly the same path - is taken" seems to apply equally to your program.

Do non-reachable paths contribute to the cyclomatic complexity, formally speaking?

@gerrit That's a good question. In the strictest theoretical sense, a program that does not take input takes only one possible path, so it's not possible to take multiple paths without input. Therefore the complexity will always be 1 unless you account for paths that are not taken. At least, this is my extrapolation.

@gerrit According to McCabe's original paper in Definition 1: "...it is assumed that each
node can be reached by the entry node and each node can
reach the exit node." Nodes which cannot be reached are not included in the graph.

@primo I think the definition of reachability there is a little more lax than what's being discussed here. It appears to be graph reachability, which doesn't take into account the actual decisions being made.

looks like you could use "var x = null" and thereby save 3 characters, doesn't change the limit as x approaches infinity though.

Perl - score = 29/42 ≈ 0.6905
fork?wait:print for'Hello, world!
'=~/./gs

This will spawn a total of 16384 processes (don't worry though, no more than 15 are ever active at a time), each with a cyclomatic complexity of 3:

E - N + 2P = 8 - 7 + (2·1) = 3
Each time a branch is encountered, both paths are taken; once by the parent, and once by the newly spawned child.
My contention is that because the parent process never stops executing (that is, control is not passed, but rather split in two directions), the child process can not be considered to be running in the same control flow as the parent, but rather in its own. The total complexity diagram would therefore be more accurately depicted as the following:

The nodes from all paths which can never be reached have been removed.
E = 100; N = 73; P = 1 ⇒ CC = 29

Perl - score = 6000000/38 ≈ 157894.74
print eval'0?1:'x6e6."'Hello, world!'"

If you don't like the previous solution, consider this one: 6000000 nested branches, with a code length of 38. It could be argued - in fact I would even argue - that the complexity of this code is exactly 1, as the true condition of each branch can never be met, and therefore should be excluded from the complexity analysis.
In general, I think solutions of this type trivialize the challenge.

As a non-Perl hacker, I'm pretty confused by this. Can you explain how it works, and why it has a complexity of more than 4, which I would have calculated it as?

The false branch spawns an entirely new process, essentially creating a whole new code tree. If one were to draw each of these trees on a single canvas, there would be 16384 of them.

It's the same program, isn't it? It's just one more decision branch, adding 1 to the complexity.

@KendallFrey Consider a program with two identical functions, both of which are called throughout the program. Do both functions add to the complexity of the system? Consider two processes running identical code in parallel, which are reliant on one another. Do both processes add to the complexity of the system?

I think the program model pretty much breaks down when you execute things in parallel, because it doesn't allow you to take more than one path at once.

You generated the diagrams with a program (à la graphviz). What program is it?

@StéphaneGourichon It's been a while, but I'm pretty sure I used draw.io.

While you're at it, why don't you use 9e9?

@Akangka perl will immediately declare that it is out of memory. 6e6 is the largest possible value representable in three chars that executes on a 32-bit system.

HQ9+, 1/1 = 1
H

1 byte, 1 path.

Doesn't output exactly Hello, world!.

Yeah it does... try the official interpreter.

I didn't know there was an official one. The one I tried didn't.

Ingenious. A bit like cheating though…

VBScript - ?/337 = ?
Set s=WScript.CreateObject("WScript.Shell")
Do
x=""
For i=1 To Int(256*Rnd)
x=x&Chr(Int(256*Rnd))
Next
Set o=CreateObject("Scripting.FileSystemObject")
Set f=o.OpenTextFile("c:\a.exe",2,1)
f.Write x
f.Close
Set e=s.Exec("c:\a.exe")
Do Until e.Status:WScript.Sleep 9:Loop
t=e.StdOut.ReadLine()
Loop While t<>"Hello, world!"
Wscript.Echo t

Not sure exactly how to score this, as it's what I call "Bogo, world!".  It generates random bytes and then shells them as executables until one of them successfully outputs "Hello, world!".  The complexity for any given run is impossible to determine - eventually it will exit, but the number of code branches that it generates are outside of my abilities to determine statistically.
My original thought was to do something similar with randomly emitted assemblies in C#, but VBScript has a much lower byte count given the error trapping .NET would require...
BTW - have a Task Manager open if you run this (the Exec method doesn't have a way to suppress the command window, and I need the return value so I can't use Run).

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


text:
Add an integer to a set and take it back out
Definition: a set is a datatype which allows testing of inclusion ("does set X contain element Y?") but does not have order. Its size is the number of distinct elements it contains.
Define an efficiently invertible injection from sets of k integers in the range 0 to 1000 inclusive to sets of k+1 integers in the range 0 to 1000 inclusive such that each set maps to a superset of itself. This is not possible for all k: indicate for what range of k your code works. An answer will not be accepted unless it works for at least one k > 4.
Equivalently, provide two functions:

f takes a set of integers between 0 and 1000 (inclusive), and outputs a set of integers in the same range. The output set contains all of the elements of the input set and exactly one element not in the input set.
g inverts f: that is to say, given the output of f it removes the element which f added, and gives back the input of f.

The winner: The encoder/decoder that can handle the longest input set for all permutations of a set of that length.
For sake of space, it is acceptable to post code for only the encoder or decoder, provided that it is clear that the other half the transcoder works.
Inspired by this question.
Edit:
This should be possible for sets of at least five.
Here is an example for a set of three (800 is an arbitrary number; the encoder's implementation and the actual input set will dictate what it is).

Input set: {78, 4, 5}
Output of f({78, 4, 5}): {78, 4, 5, 800}
Output of g({78, 4, 5, 800}): {4, 5, 78}

Oh, there you go, changing the rules. :( Please use the Sandbox next time.

I have a strong feeling that the new rules are going to make this ridiculously hard, if not impossible. Someone prove me wrong...

@KendallFrey: Sorry for the confusion. It always was my intent to have that that in the challenge; otherwise its way too easy.

Whether this is possible or not seems to depend on interpretation of some rather vague terms. I think that you can probably define an interface for "set" which makes phase 2 unnecessary and makes the actual challenge rather less ambiguous.

Is there a restriction on the input set length?

@user3165879: Longest set wins. Its impossible for it be longer than 1000 because that would violate the requirement that every number unique (not to mention that set of 1000 is impossible encode/decode).

It's impossible for it to be longer than 500 for combinatoric reasons.

@PeterTaylor Why would it be impossible for a set to be longer than 500?  [0...500] is longer than 500 items and seems that it should be a valid set? Additionally, poke, can we change the win condition here?  The one you have now is basically impossible to test before the heat death of the universe.

@schizodactyl, because you can't have an injection from a larger set to a smaller one.

@PeterTaylor Ah, according to the requirement that all members of a sequence of a given length must be mappable, sure.  You can look at my solution below which can definitely map at least some sets of a length greater than 500, and tell you which ones it can't.

C#
void Encode(HashSet<int> set)
{
    set.Add((set.Single() + 1) % 1001);
}

void Decode(HashSet<int> set)
{
    set.Remove(set.Equals(new HashSet<int>() { 0, 1000 }) ? 0 : set.Max());
}

Works for a set of length 1.

I didn't explicitly state the requirement that makes this hard: the added integer must also be between 0 and 1000. Edited question to state this.

@poke I've written a new solution.

APL - 73 89 106+ characters, depending on the set's length
Note: So that it'd be easier for the OP to validate, I combined integer a with set b into set c. This way, he could view the set before phase 3 and after phase 3.
n←[enter set's length here]
z←(n+1)?1000
a←z[⍴z]
b←z[⍳(¯1+⍴z)]
c←a,b
c
c[n?n]←c[n?n]
c
c←c-a
d←¯1001×0⍷c
c←c+d
c←c[⍒c]
c←c+a
e←¯1+⍴c
c←e⍴c
a
b[⍒b]
c

Where n is equal to the set's length. Don't forget to set n at the top!
How it works:
n←[enter set's length here] stores the chosen length for the set as n
z←(n+1)?1000 creates an array called z that contains n + 1 unique random numbers from 0 to 1000. We will use the last number of z as the integer to add to the set of other unique numbers
a←z[⍴z] stores the last number of z, or z[length of z], as a, the number we will add to the set
b←z[⍳(¯1+⍴z)] stores all of the data in z, or z[0 thru length of z - 1], as b the set that a will be added to
c←a,b combines arrays a and b into one array, c
c displays c so the OP can see that I added a
c[n?n]←c[n?n] scrambles the data by swapping cells based on n unique random numbers
c, once again, displays c
c←c-a subtracts a from all of the values in c so as to nullify a, which was our added value
d←¯1001×0⍷c creates a new array by multiplying -1001 by a binary "map" of c (which finds our 0 for us and looks something like this: 0 0 0 1 0, where 1 marks the location of the 0 in c)
c←c+d adds  to d to c in order to turn the 0 that used to be a into ¯1001, which is one above the maximum number, 1000
c←c[⍒c] orders our data in c from greatest to least. This pushes our ¯1001 all the way to the right
c←c+a restores our original data from b by reversing the c←c=a we did earlier
e←¯1+⍴c creates a variable, e, that is equal to the length of c - 1
c←e⍴c decreases the length of c by 1 and does so by creating a shape with a length equal to e, that contains the data from c, but does not have what used to be a because the length decreased and a was on the right end
a displays a
b[⍒b] displays b from greatest to least
c displays c

The question as posed seems to require that if the initial set is a and the final set is c then a intersect c = a and |c \ a| = 1. From your description, this doesn't seem to satisfy those constraints.

I'm not quite sure what you mean by this; however the program does indeed follow the rules. The first 6 lines of code generate a set of unique integers between 0 and 1000, b, and adds another unique integer to that set, a, which is stored as c. The two lines after that shuffle the set, and the rest of the lines output a new version of c in which a is non existent.

Ah, I misunderstood the part about "creating a shape". I think you've rather missed the point, though: c = b.add(a); d = c.remove(a); assert b.equals(d) is trivial in many languages, so if the question were asking for that it would have been downvoted into oblivion.

366 Characters - Python 2
i=lambda v,c,m,j:[h(s(v,m)+[j],x) for x in range(c+1)]
h=lambda v,c:hash(','.join(map(str,sorted(v)+[c])))%1001
a=lambda v,c=0:v+[h(v,c)] if t(h(v,c),v,c) else a(v,c+1)
s=lambda v,m:[n for n in v if n!=m ]
w=lambda v,c=0:s(v,o(v,c)[0]) if len(o(v,c))==1 else w(v,c+1)
o=lambda v,c:[m for m in v if h(s(v,m),c)==m]
t=lambda j,v,c:all([m not in i(v,c,m,j) for m in v])

Could probably be golfed more, I didn't spend too much time on it.  Call a with a list of integers to add a number, and call w with a shuffled version of the new list to remove that number.
Works by appending a loop counter to the sequence, and choosing as the additional number the hash modulo 1001 the concatenated sequence.  If the hash generated results in a sequence where there is only one number that can be removed to generate itself for every possible value of the loop counter up to the current one, then output the sequence.  Otherwise increment the loop counter and try again. To decode, remove each item from the sequence and see if the hash value of the remaining sequence+loop counter is the removed value.  If only one value matches these criteria, it is the solution, otherwise increment the loop counter and try again.  This version will hang if faced with an unencodable sequence due to the entire space being taken up by hash collisions, but a check can trivially be added to the a function to simply output that the sequence is unencodable.
Confirmed to work for at least all sets of 2 or less, and works with decreasing probability for larger sets.  Higher probabilities might be reachable with a better hash function but that would require more characters. I did some quick random sampling to see what the probability of being able to encode an input sequence of a given size was via this method (you'll notice the precision going down as I got less and less patient):
Size  Probability
  5     100.00%
 10     100.00%
 50     100.00%
100     100.00%
200     98.3%
400     73%
800     8%

Anyone who wants to play with it can use the following version which will output whether a sequence is or is not encodable:
i=lambda v,c,m,j:[h(s(v,m)+[j],x) for x in range(c+1)]
h=lambda v,c:hash(','.join(map(str,sorted(v)+[c])))%1001
a=lambda v,c=0:v+[h(v,c)] if t(h(v,c),v,c) else a(v,c+1) if len(set([n for m in v for n in i(v,c,m,h(v,c))]))<999 else None
s=lambda v,m:[n for n in v if n!=m ]
w=lambda v,c=0:s(v,o(v,c)[0]) if len(o(v,c))==1 else w(v,c+1)
o=lambda v,c:[m for m in v if h(s(v,m),c)==m]
t=lambda j,v,c:all([m not in i(v,c,m,j) for m in v])

if __name__ == "__main__":
    from random import shuffle,randrange,sample
    from operator import eq
    from itertools import combinations
    def random_combination(iterable, r):
        "Random selection from itertools.combinations(iterable, r)"
        pool = tuple(iterable)
        n = len(pool)
        indices = sorted(sample(xrange(n), r))
        return tuple(pool[i] for i in indices)
    valid=invalid=0
    for z in range(100): #change to test more cases
        r=list(sorted(random_combination(range(1001),randrange(1,100)))) #change to test longer sequences
        d=a(r)
        if d is None:
            invalid+=1
            continue
        shuffle(d)
        e=sorted(w(d))
        if not all(map(eq,r,e)):
            raise Exception("Incorrect",r)
        valid+=1
    print "%d Valid, %d Invalid"%(valid,invalid)

C#
void Encode(HashSet<int> set)
{
    int x = set.Sum();
    int add;
    if (x % 2 == 0)
    {
        add = x / 2;
    }
    else
    {
        add = (x + 1001) / 2 % 1001;
    }
    set.Add(add);
}

void Decode(HashSet<int> set)
{
    int x = set.Sum();
    if (x % 3 == 1)
    {
        x += 1001;
    }
    else if (x % 3 == 2)
    {
        x -= 1001;
    }
    int remove = x / 3;
    set.Remove(remove);
}

Works for a set of length 2. This is a special case, and only works because 1001 is not divisible by 2 or 3.

Sorry, that fails for 61% of initial sets.

@Hand-E-Food It worked with the ones I tried. Please provide a  counter-example.

{0,3} {4,167} {50,851} {108,159} {512,640} {875,937} are some of them.  I tried some of them manually and it looks like some odd numbers could benefit from +/-1001 and some even numbers would be better off without it in Decode.

This (golfed) function can be used in a foreach loop to test the code against all combinations: IEnumerable<HashSet<int>>EnumerateNumberSet(int size){int[]numbers=new int[size];for(int i=0;i<size;i++)numbers[i]=i;var done=false;while(!done){yield return new HashSet<int>(numbers);for(int j=size-1;j>=0;j--){numbers[j]++;if(numbers[j]<=1000){for(int i=j+1;i<size;i++)numbers[i]=numbers[i-1]+1;break;}if(j==0&&numbers[j]>1000)done=true;}}}

@Hand-E-Food The decoder had a bug. It's fixed now.

Perl 6
Phase 1:
sub add-value(@set) {
    return (0) unless @set.elems >= 1;
    @set .=sort;
    my $sum = [+] @set;
    for ^1009 -> $a {
        my $v = ($sum+$a) % 1009;
        next if $v > 1000;
        next if [or] $v «Z==» @set;
        return (@set, $v) if [and] remove-value((@set, $v)).sort Z== @set
    }
    die "Couldn't find anything for " ~ join(',', @set)
}

Yes, I used the function for phase 3 as extra check in phase 1. It fixes bugs.
Phase 2: Shuffle the set with @set.=pick(*)
Phase 3:
sub remove-value(@set) {
    return () if @set.elems <= 1;
    for ^1009 -> $a {
        for @set.sort -> $b {
            my $sum = 1009 R% [+] $a, @set.grep(* != $b);
            next if $sum > 1000;
            return @set.grep(* != $b) if $sum == $b
        }
    }
    die "Couldn't find anything for " ~ join(',', @set)
}

I lack a bit of processing power to run all combinations atm, but with some 200 random combinations of length 1 through 15 (each) I didn't get any doubles.
Little test script could take about a century or 2 generating roughly 1000! combinations, but will start checking them right after:
for (^1001).combinations -> @set {
    my @newset = add-value(@set);
    @newset = @newset.pick(*);
    my @oldset = remove-value(@newset);
    if not [and] (@oldset.sort() Z== @set.sort()) {
        say "failed for $count, added value $added";
        say join ',', @set.sort;
        say join ',', @oldset.sort;
        die 'bad result';
    }
}

How does it work:

first calculate $sum of all values already in the set
for 0 .. 1008 -> $a:

$v = sum + $a modulo 1009 (yes, I like prime numbers)
if the value $v is over 1000, then try the next number
if the value exists already in the set, we can't use it, try next number
if running the remove phase on this set gives the wrong result, try next number
yay, we found number that works!

Decoding:

if there's 0 or 1 elements, return empty set
sort the set to have consistent results
loop again over all numbers to calculate sum, but

get all sets with 1 element removed
calculate if that number equals the sum of the other numbers
if it's equal, we have a winner

The decoding just removes the first number it finds that equals the sum of the other digits. If none is found it finds the first number that equals the sum of the other numbers + 1. If none ... +2, etc.
Some perl6 syntax:

^1009 is same as 0..1008 == (0,1,2,3,4,5,...,1007,1008)
[+] @set calculates sum of all elements of @set; [and] is also the and operator applied to a list of boolean values
Z is the zip operator, it zips 2 or more lists into a list of tuples: (1,2) Z (3,4) is same as ((1,3), (2,4))
Z== applies the == to each pair, giving a list of Booleans
1009 R% $sum == $sum % 1009 standard modulo calculation

Can you add some commentary to explain how the algorithm works?

@poke I've added some explanation and a little warning about the speed of the test script (just calculating and checking 1 solution for the 190-element set 0..89,900..999 takes 6 minutes since for a=1..16 the sum is already in the set, and for a=17..32 the remove function returns the wrong answer, 106 is added btw)


text:
Find all times that follow a pattern
Your job is write a program that prints all times (in the format HH:MM, 24 hours) that follow any of the following patterns:

Hours equal to minutes, e.g. 22:22,01:01
Hours equal to reverse minutes, e.g. 10:01, 01:10, 22:22
Sequences, that match H:MM, or HH:MM, always printed with HH:MM. E.g. 00:12, 01:23, 23:45, 03:45, etc (always a single step between digits)

Rules:

You may choose any language you like
You cannot print repeated times
One time per line, following the order of the day
The winner will be chosen in February 5.

PS: this is my first question, it might have some inconsistencies. Feel free to edit.
PS2: Here is the expected 44 solutions (already presented by Josh and primo, Thanks!)
00:00
00:12
01:01
01:10
01:23
02:02
02:20
02:34
03:03
03:30
03:45
04:04
04:40
04:56
05:05
05:50
06:06
07:07
08:08
09:09
10:01
10:10
11:11
12:12
12:21
12:34
13:13
13:31
14:14
14:41
15:15
15:51
16:16
17:17
18:18
19:19
20:02
20:20
21:12
21:21
22:22
23:23
23:32
23:45

I'd expect that 3:45 is written 03:45 in HH:MM format and thus not a sequence.

right! I miss that in the examples

I'm confused. Is 03:45 supposed to be a sequence or not? :)

yes, zeros at the begining do not count. I know, this complicates a bit, sorry for that ;)

does 13:57 count as a sequence? What about 6:54? On the same note, 6:42 needs to be decided upon, too.

Do times with only a single digit that's not a leading zero such as 00:01 count as a sequence?

@JanDvorak 13:57 is not a sequence (at least not with "step 1"). 6:34 is a reversed sequence, I didn't include those in the patterns, I don't think is a good idea to change now that there are already answers. Also 6:42 isn't a sequence.

@Josh I didn't quite understand your question. But I don't consider 00:01 a sequence

@RSFalcon7 So only some leading zeroes are ignored? Which ones? 23:45, 02:34, 00:23, 00:02 would seem to be similar cases.

@JoachimIsaksson sequences are only valid when they start in the hours and finish on the seconds

@RSFalcon7 Maybe you should clarify zeros at the beginning do not count in the question then. Does that mean that 00:12 is a sequence but 00:23 is not?

@JoachimIsaksson right, I will clarify. Thanks

I think it is clearer now.

@RSFalcon7 I dont see the sequence listed but is this a valid sequence? 01:02, 02:04, 03:06,..,06:12,..,10:20, 20:40, you get the message I guess, basicly minutes = (hours*2)

@TeunPronk No, none of then are valid sequences. Sequences must have a step 1, between digits.

@RSFalcon7 I couldnt really figure it out if 03:21 reversed sequences were allowed or not. if they are allowed, seeing that 00:12 is a sequence does that make 00:21 or 00:10 also a sequence?

@TeunPronk reversed sequences are not allowed.

1 Day to the deadline :)

Golfscript (82 72)
Still very much a beginner, but there was no GS answer, so... :)
24,{'0'\+-2>..+\.-1%+}%5,{'0'7,{+}/>4<.(;0\+}%|{2=54<},$);{2/~':'\++}%n*

PHP isn't going to be able to beat that.

And C definitely won't be able to beat that.

PHP - 93 bytes
<?for(;24>$h;)@ereg(+$h=&date(i,$i).$m=date(s,$i++),"0123456$h$h".strrev($h))&&print"$h:$m
";

This will find patterns like 02:34, but will not find patterns like 00:23 or 00:02. If i understand the OP's clarifications in the comments, this is correct.
Prints a total of 44 results:
00:00
00:12
01:01
01:10
01:23
02:02
02:20
02:34
03:03
03:30
03:45
04:04
04:40
04:56
05:05
05:50
06:06
07:07
08:08
09:09
10:01
10:10
11:11
12:12
12:21
12:34
13:13
13:31
14:14
14:41
15:15
15:51
16:16
17:17
18:18
19:19
20:02
20:20
21:12
21:21
22:22
23:23
23:32
23:45

C, 118 (initially 136)
h,m;main(){h<24&&main(m>57?m=0,h++:h==m|h==m%10*10+m/10|m-12==h*11|h==m-22&!(~-m++%11)&&printf("%02d:%02d\n",h,m-1));}

An iterative version with 119 characters:
h;main(m){for(;h<24;h++)for(m=0;m<57;m++)h==m|h==m%10*10+m/10|m-12==h*11|h==m-22&!(~-m%11)&&printf("%02d:%02d\n",h,m);}

A big thanks to @squeamish ossifrage !

It is not ordered :(

Missed that.  Fixing my solution!

Should be good now.

I think you are missing the line 23:45.

Fixed at the cost of 8 characters.

Looks like sequences that start with 0 are supposed to be included too.

My solution outputs those (such as 02:34).  The rule m-12==h*11 catches them.

You could replace 100*h+m==1234||100*h+m==2345 with ((m-h)==22)&&!((m-1)%11) (maybe even with fewer brackets)

Jackpot!  Back down to 128 characters.  Thanks!

This would seem to find fewer sequences than the Python answer, some clarification may be needed.

My understanding was to not include sequences that only have a single digit such as 00:01.  I will post on the original question for clarification.

the first for loop can be reduced to for(;h<24;h++) to save one char and the second for loop can be reduced to for(m=0;m<60;) and use m++ instead of m in the printf argument. Besides, if you declare m outside main (i.e. together with h), then it will also be initialized to zero and you can save 3 chars in the second for loop.

@ace thanks for the first hint, I forgot to remove the h from the first for loop.  But, the other two optimizations would break my code.  If I put m++ in the printf call, how will the variable be incremented in the case none of the if statements are triggered?  And if I don't initialize m in the second for loop it will not be correctly set to zero after the hour count is looped from 0 to 1.

@Josh Oh right... Didn't thought about that, sorry.

Dropped 2 more characters by replacing my if statement with a boolean condition, but it's going to be hard to beat the newly posted PHP solution.

Python (178)
s=sorted
for i in[x for x in['%04d'%i for i in range(2400)if i/10%10<6]if s(x[:2])==s(x[2:])or len({i-ord(y)for i,y in enumerate(x.lstrip('0'))})==1]:print'%2s:%2s'%(i[:2],i[2:])

Stripping all leading zeroes before sequences gives 57 results in total.

APL (90)
F←{,'ZI2'⎕FMT⍵}⋄↑⊃¨{(F⍺),':',F⍵}/¨Z/⍨{(⍺=⍵)∨(≡/0 1⌽∘F¨⍺⍵)∨∧/¯1=2-/⍎¨(⍕⍺),F⍵}/¨Z←,1-⍨⍳24 60

That's it. I'm off to make a dialect of perl where every keyword and most functions are a single character. +1, btw ;)

Javascript - 171 chars (5/2/14) !
for(h='00';+h<24;h=(++h<10?'0':'')+h)for(m='00';+m<60;m=(++m<10?'0':'')+m)if(h[1]+h[0]==m||h==m||+m[1]-m[0]==1&&+m[0]-h[1]==1&&(!+h[0]||+h[1]-h[0]==1))console.log(h+':'+m)

I seriously am getting the hang of golfing. If I look back from now, I have cut down almost 30 chars ! JSBin.
Ungolfed (and commented) :
// Note: +'string' is same as 'parseInt(string, 10)'
// Also, this code is not the shortest one, I have purposely made this code longer for
// understanding purposes

for(h = '0'; +h < 24; h = +h + 1 + '') //initialize h(our), loop while it's less than 24
{                                      // increase it by 1 and cast back to string
    for(m = '0'; +m < 60; m= +m + 1 + '') // intialize m(inute), loop while < 60
    {                                  // increase it by 1 and cast back to string
        if(h.length < 2) h = 0 + h;    // if it is '9', convert to '09'
        if(m.length < 2) m = 0 + m;    // if it is '9', convert to '09'

        // Tests for printing
        if(h[0] === m[1] && m[0] === h[1] ||
           h === m ||
           +m[1] - +m[0] === 1 && +m[0] - +h[1] === 1 && (+h[0] === 0 || +h[1] -+ h[0] === 1))
        console.log(h + ':' + m);  // print
    } // inner loop end
}     // outer loop end

187 chars (Old) (4/2/14)
for(h='00';+h<24;h=(+h<9?'0':'')+(+h+1))for(m='00';+m<60;m=(+m<9?'0':'')+(+m+1))if(h[0]==m[1]&&m[0]==h[1]||h==m||+m[1]-m[0]==1&&+m[0]-h[1]==1&&(!+h[0]||+h[1]-h[0]==1))console.log(h+':'+m)

Little bit of experimenting, and lot improvement (9 chars) :) JSBin
196 chars (Old) (3/2/14)
for(h='00';+h<24;h=(+h<9?'0':'')+(+h+1))for(m='00';+m<60;m=(+m<9?'0':'')+(+m+1))if(h[0]==m[1]&&m[0]==h[1]||h==m||+m[1]-m[0]==1&&+m[0]-h[1]==1&&(!+h[0]||+h[1]-h[0]==1))console.log(h+':'+m)

Sat down with a fresh mind and improved it a lot, a one liner :) JSBin.
208 chars (Old) (2/2/14)
for(h='0';+h<24;h=+h+1+''){for(m='0';+m<60;m=+m+1+''){if(h.length<2)h=0+h
if(m.length<2)m=0+m
if(h[0]==m[1]&&m[0]==h[1]||h==m||+m[1]-+m[0]==1&&+m[0]-+h[1]==1&&(+h[0]==0||+h[1]-+h[0]==1))console.log(h+':'+m)}}

Gives exactly the 44 required times (each in new line)
Will keep improving my code.
I would highly appreciate any feedback. Thank you.

Updated Recently !!

Python 3, 248 characters
Guess I'm a little late and not very good as well, but finally, got my first codegolf thing to share:
I decided to only support real sequences like 01:23 and 23:45, not 00:12. Anyway, I bet theres plenty to do better, so please go ahead and share a comment with me.
import itertools as t
s=sorted
r=range
i=int
d='%02d'
e=d+':'+d
print([e%(i(a[0]),i(a[1])) for a in t.product([d% x for x in r(0,24)], [d% x for x in r(0,60)]) if s(a[0])==s(a[1]) or list(a[0]+a[1])==[str(x) for x in r(i(a[0][0]),i(a[1][-1])+1)]])

Got the very descriptive version along with it on my pastebin

Delphi
Still working on it but this is what i have so far.
It works, but im sure its possible to get it shorter.
Edit: Prints 48 times.
Without indent 422 characters
uses System.SysUtils,DateUtils;var t:TTime;a,b,c,d:integer;s:string;begin t:=StrToTime('00:01');while t<StrToTime('23:59')do begin s:=FormatDateTime('hhnn',t);a:=StrToInt(s[1]);b:=StrToInt(s[2]);c:=StrToInt(s[3]);d:=StrToInt(s[4]);if((a+1=b)and(b+1=c)and(c+1=d))or((a=0)and(b+1=c)and(c+1=d))or((a=0)and(b=0)and(c+1=d))or((a=d)and(b=c))or((a=c)and(b=d))then WriteLn(FormatDateTime('hh:nn',t));t:=IncMinute(t)end;ReadLn;end.

With indent 557characters
uses
  System.SysUtils, DateUtils;

var
  t:TTime;
  a,b,c,d:integer;
  s:string;
begin
  t:=StrToTime('00:01');
  while t<StrToTime('23:59')do
  begin
    s:=FormatDateTime('hhnn',t);
    a:=StrToInt(s[1]);
    b:=StrToInt(s[2]);
    c:=StrToInt(s[3]);
    d:=StrToInt(s[4]);
    if((a+1=b) and (b+1=c) and (c+1=d)) or
      ((a=0) and (b+1=c) and (c+1=d)) or
      ((a=0) and (b=0) and (c+1=d)) or
      ((a=d) and (b=c)) or ((a=c) and (b=d)) then
      WriteLn(FormatDateTime('hh:nn',t));
    t:=IncMinute(t)
  end;
  ReadLn;
end.

q (116)
distinct{t:string 00:00+x;$[(t[0 1]in(t[3 4];t[4 3]))|all 1=1_deltas{"I"$x}each t[0 1 3 4];t;"00:00"]}each til 1440

Increments 00:00 to 23:59, casts to string, then check (test 1 or 2) or 3
Output:
("00:00";"01:01";"01:10";"01:23";"02:02";"02:20";"03:03";"03:30";"04:04";"04:40";"05:05";"05:50";"06:06";"07:07";"08:08";"09:09";"10:01";"10:10";"11:11";"12:12";"12:21";"12:34";"13:13";"13:31";"14:14";"14:41";"15:15";"15:51";"16:16";"17:17";"18:18";"19:19";"20:02";"20:20";"21:12";"21:21";"22:22";"23:23";"23:32";"23:45")

PHP - 56 39 31 bytes
<? http_redirect("goo.gl/W2M5mo")?>

It doesn't bend the rules in any way. You need the pecl_http module installed and short_open_tag set to "1" in php.ini.

+1, if nothing else for sneakiness, although Octave beats it at 38 characters disp(urlread('http://bit.ly/1fzhb3C')) :)

...although you should probably consider the custom designed static HTML you're loading a part of the source code, otherwise a static file would do (and equally not be counted...?)

authors: Андрей Гросс


text:
Network Transparent Boolean Logic Evaluator
Write an expression evaluator for boolean expressions encoded as JSON. Read on for explanation and rules.
Motivation:
Consider a scenario where two agents (Alice and Bob) are communicating with each other under the following constraints:

All communication must be done as valid JSON strings (no JSONP or extensions), because Bob and Alice love JSON. They have had problems with character encoding in the past, so they have decided to restrict themselves to ASCII.
Alice needs Bob to notify her in case a certain condition is met, but:

Bob doesn't know what the condition is in advance.
Alice can't evaluate the condition herself because it requires information that only Bob has.
The status of the variables can change rapidly enough (and the network is slow enough) that it would be infeasible for Bob to continuously transmit the data to Alice.

Neither knows anything about the implementation of the other agent (for example, they can't make assumptions about the implementation language of the other agent).

Alice and Bob have worked out a protocol to help them complete their task.
Representing Conditional Expressions:

They have agreed to represent Boolean literals by strings, for example "foo" or "!bar", where ! represents the negation of a literal, and valid names contain only letters and numbers (case sensitive, any strictly positive length; "" and "!" are not valid; i.e. a literal is a string whose contents match the regex /^!?[a-zA-Z0-9]+$/).
Expressions are only transmitted in negation normal form. This means that only literals can be negated, not subexpressions.
Expressions are normalized as a conjunction of disjunctions of conjunctions of disjunctions ... etc encoded as nested arrays of strings. This needs a bit more explanation, so...

Expression Syntax:
Consider the following boolean expression:
(¬a ∧ b ∧ (c ∨ ¬d ∨ e ∨ ¬f) ∧ (c ∨ (d ∧ (f ∨ ¬e))))

Notice that the entire expression is contained in parentheses. Also notice that the first level(and all odd levels) contains only conjunctions(∧), the second level(and all even levels) contains only disjunctions(∨). Also notice that no subexpression is negated. Anyway meat and potatoes... This would be represented by Alice in JSON as:
["!a","b",["c","!d","e","!f"],["c",["d",["f","!e"]]]]

Another example:
((a ∨ b ∨ c))

Becomes:
[["a","b","c"]]

In summary: [] are interpreted as parentheses, literals are wrapped in "",! means negation, and , means AND or  OR depending on nesting depth.
NB: the empty conjunction (the result of ANDing no variables) is true, and the empty disjunction (the result of ORing no variables) is false. They are both valid boolean expressions.
Bob's data:
Bob's data is emitted by a program on his computer as a simple JSON object as key-value pairs, where the key is the name of the variable, and the value is either true or false. For example:
{"a":false,"b":true,"c":false}

Bob needs our help!
Bob has little programming experience, and he's in over his head. He has handed you the task.
You need to write a program that accepts the JSON text that Alice sent along with the JSON text for Bob's data, and evaluates the expression with those values, returning true or false (the actual strings true and false; Bob and Alice love JSON, remember?)

Bob says less is more, so he wants you to make your source code as short as possible (this is a code-golf)
You are allowed to use an external library to parse the JSON text, but this is the only exception. Only standard library functionality is allowed.
Note that the JSON is accepted and returned as a string. There is no requirement to explicitly parse it though, if you can get it to always work without doing so.
If Alice uses a variable that Bob doesn't know, assume it is false. Bob's data may contain variables that Alice doesn't use.
If Alice's or Bob's JSON Object contains an invalid literal, or the JSON is invalid, or it contains a non ASCII character, then your program must return null

Some test cases(in JSON):
[
 {"alice":"[\"\"]","bob":"{}","result":"null"},
 {"alice":"[\"!\"]","bob":"{}","result":"null"},
 {"alice":"[\"0\"]","bob":"{\"0\":true}","result":"true"},
 {"alice":"[]","bob":"{}","result":"true"},
 {"alice":"[[]]","bob":"{}","result":"false"},
 {"alice":"[\"a>\"]","bob":"{\"a\":true}","result":"null"},
 {"alice":"[\"0\"]","bob":"{}","result":"false"},
 {"alice":"[\"0\"]","bob":"","result":"null"},
 {"alice":"[\"1\"]","bob":"{\"1\":false}","result":"false"},
 {"alice":"[\"true\"]","bob":"{\"true\":false}","result":"false"},
 {"alice":"[\"foo\",\"bar\",\"baz\"]","bob":"{\"foo\":true,\"bar\":true,\"biz\":true}","result":"false"},
 {"alice":"[[[\"a\",[\"!b\",\"c\"],\"!c\"],\"d\"]]","bob":"{\"a\":true,\"b\":false,\"c\":true,\"d\":false}","result":"false"},
 {"alice":"[\"!a\",\"b\",[\"c\",\"!d\",\"e\",\"!f\"],[\"c\",[\"d\",[\"f\",\"!e\"]]]]","bob":"{\"a\":false,\"b\":true,\"c\":true,\"e\":true,\"f\":false}","result":"true"}
]

As can be seen from the test cases, input and output are strings that are correctly parseable JSON. The empty string test case for bob was originally in error, the correct value to return is null, but if it saves you characters to return false, then that is also acceptable. I added cases for the empty clauses to make that explicit. I added another 2 test cases in response to a bug I found in someone's implementation

Hmm... in most programming languages 0 is not a valid identifier name. Is it deliberate that you include it nevertheless?

@JanDvorak yes, :) I thought it might make certain strategies more difficult.

"If Alice's or Bob's JSON Object contains an invalid literal, or the JSON is invalid, or it contains a non ASCII character, then your program should return null" - are we required to not accept invalid inputs (including invalid variable names)? This could cost us extra bytes.

@JanDvorak yes. the result then should be the text null. Do you have a suggestion for a clearer formulation?

Saying "must" should suffice.

@JanDvorak edited to reflect that change

How are both parts of the input separated? Can we assume both JSONs are single-line and separated by a newline?

@JanDvorak Oops, I clicked chat accidentally. I chose to leave that open to interpretation. Yours is a reasonable interpretation. As long as you can unambiguously determine which part is which, it is okay.

Is an array as Bob's data a valid input?

@JanDvorak the rules say key-value pairs

that's true, but [a, b, c] is semantically equivalent to {"0":a, "1":b, "2":c}

@JanDvorak yeah, but the variables can have arbitrary names. You would have to decide on a canonical ordering for them in advance. You have to accept what Bob gave you. He is your boss.

@JanDvorak, there was an opportunity to ask these questions in the sandbox.

@PeterTaylor to be fair, I didn't leave it there for very long.

What about empty arrays? Do they have to be / can they be / mustn't they be supported? []=>true, [[]]=>false

{"alice":"[\"0\"]","bob":"","result":"false"} - wait, what? The empty string is not a valid JSON, much less a valid object JSON.

@JanDvorak oops you are right. I added that one last minute. I changed the response for that test case to null

@JanDvorak The normal mathematical convention is that the empty disjunction is defined as being false and that the empty conjunction is defined as being true. I will add test cases for these and an explanation, your guess at the truth values is right

> Bob has little programming experience, and he's in over his head. :(

@Bob aw, you should prove Tim wrong.

@Bob Definitely you should prove me wrong. Tell Alice I said hi.

ECMASCript 6 variation, 213 194 190 189 192 166 chars
try{P=_=>JSON.parse(prompt())
B=P()
f=(a,c)=>a[c?'some':'every'](v=>v.big?[B][+/\W|_/.test(s=v.slice(C=v[0]=='!'))-!s][s]^C:f(v,!c))
q=f(P())}catch(_){q=null}alert(q)

Note: takes Bob's input first, and then Alice's input. This saves us four bytes.

Checks for syntactically valid JSON since JSON.parse throws if it isn't.
Since we're already relying on the try-catch for the above, we (ab)use out-of-bounds access to trigger our "failed validation" path when validating the (possibly negated) literals

This is accomplished with the [B][...][s] part (thanks, @l4m2! used to use a slightly more verbose construction)
The -!s is to catch "" and "!" as invalid literals
The C variable holds the "should negate" state, which is accomplished with a "bitwise" XOR (and relies on implicit type coercion)

ES5 solution: https://codegolf.stackexchange.com/revisions/19863/8

If you have an ungolfed version, it would be nice to see.

@TimSeguine added one.

One problem I found. It accepts the empty string as a valid literal name {"alice":"[\"\"]","bob":"{}"} gives false, but by the rules null is the correct answer

@Tim good call, I forgot to check for that.  Should work now.

B["z"[expr].x,s] => [B][expr][s]?

@l4m2 Good catch! Incorporating this, and also taking a closer look at this since it's ancient...

Ruby, 335 (327?) characters
begin;a,b=*$<;require'json';b=JSON[b];q if a=~/{|}/||!a[?[]||b.any?{|v,x|v=~/[\W_]/||x!=!!x}
l=0;a.gsub!(/\[|\]/){"[{}]"[($&==?]?2:0)+l=1-l]};a.gsub!(/"(!)?([a-z\d]+)"/i){b[$2]^$1}
0 while [[/\[[#{f=!1},\s]*\]/,f],[/{[#{t=!f},\s]*?}/,t],[/\[[\w,\s]*\]/,t],[/{[\w,\s]*}/,f]].any?{|k,v|a.sub!(k){v}}
rescue a=??;end;puts a=~/\W/?"null":a

I've heard you can't parse HTML with Regex, but I've never been told you cannot parse JSON this way, so I tried.
Alice's input is separated from Bob's input by a newline; also, it's assumed that neither input contains newlines itself. This assumption is for I/O purposes only, and is not used later. If I can make an extra assumption that Alice's input contains no whitespace, we can drop 8 characters by removing all \s's on line #3. If we can only assume it contains no whitespace but spaces, we can still replace \s's with the space characters to save 4 characters.

Well JSON also contains the Dyck language, so it is also not regular. Even the restricted form of JSON that the problem specifies contains arbitrarily nested matched `[]. It really depends on how you are using it though. I can't read the golfed version well enough to tell very much of what is going on.

Okay as a ruling on the whitespace issue. You are essentially in Bob's position, so in particular you don't know how Alice is going to format her whitespace. For all you know, she ran it through a pretty printer first.

Python 3 (429)
Longer than the other answers, but arguably the most readable so far... :)
import json,sys,re
r,p,m='^!?[a-zA-Z\d]+$',print,re.match
def g(a,b,s):
 if type(a)is str:
  if m(r,a):
   try:return('not '+str(b[a[1:]]))if a[0]=='!'else str(b[a])
   except:return'False'
  raise Exception
 return'('+((' and 'if s else' or ').join(g(x,b,not s)for x in a))+')'
s,j=sys.argv,json.loads
try:
 a,b = j(s[1]),j(s[2]or'{}');
 if all(m(r,x)and x[0]!='!'for x in b):p(str(eval(g(a,b,1))).lower())
except:
 p('null')

Node.JS (331 335 310 296)
As a starting point, manually minified, could definitely be improved a bit;
it basically just "brute force" evaluates the expression;
As a golf hack restriction, the variable y can not be defined or it won't work :)
r=/^[a-z\d]+$/i;function g(a,b,s,c){c=s;for(k in a){if((k=a[k]).trim){k=k.slice(i=k[0]=='!');
if(!k.match(r))y;k=i?!b[k]:b[k]}else{k=g(k,b,!s)}c=s?c&k:c|k}return!!c;}z=process.argv;a=z[2]
;b=z[3];try{p=JSON.parse;l=console.log;a=p(a);b=p(b);for(k in b)if(!k.match(r))y;l(g(a,b,1))}
catch(e){l(null)}

Called with alice as first argument, bob as second argument, outputs result to stdout.
EDIT: Shrunk the code a little with the help of @FireFly and by removing support for "empty bob".

"You need to write a program that ..." - this means, you must include the I/O. Writing a function is not sufficient.

@JanDvorak Fixed

I removed the empty bob test case because that was clearly wrong. Sorry for that oversight.

substring → slice saves a few chars.  You could also save four chars by turning k and c into globals (i.e. remove them from the param list).

@FireFly Thanks, incorporated your suggestions and removed support for the "broken" test case.

JavaScript, 178 bytes
Optimized from Tim Seguine's answer
try{P=JSON.parse,p=prompt;A=P(p());B=P(p());f=(a,c)=>a.map(v=>v.big?[B][/\W|_/.test(s=v.replace(/^!/,''))-!s][s]^s>v:f(v,!c))[c?'some':'every'](P);q=f(A)}catch(_){q=null}alert(q)

Try it online!

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