text:
Nether Portal Detection
The video game Minecraft is all about placing and removing different types of blocks in the 3D integer lattice that makes up the virtual world. Each lattice point can contain exactly one block or be empty (an "air" block officially). In this challenge, we will only be concerned with one vertical 2D plane of the 3D world, and one type of block: obsidian.
When obsidian forms the outline of an empty rectangle in a vertical plane, a nether portal can be created. The empty rectangle may be any size from 2 units wide by 3 units high to 22 units wide by 22 units high. The corners of the rectangle do not need to be bordered in obsidian, just the sides.
For example, suppose X is obsidian and . is emptiness: (The numbers are just for identification purposes and are also empty.)
...................................
..XXXX....XXXX....XXXXXXXXX........
..X..X...X....X..X.........X..XXXX.
..X.1X...X.2..X..X...3...X.X..X....
..X..X...X....XXXX.........X..X.6X.
..XXXX....XXXX...XXXXXXXXXXX..X..X.
.............X.4.X....X.5.X...XXXX.
.............X...X....X...X........
..............XXX......XXX.........
...................................

This grid contains 3 valid portals:

Portal 1 is 2 by 3 units, totally empty, and bordered in obsidian. Therefore it's valid.
Portal 2 is 4 by 3, totally empty, and bordered in obsidian. Therefore it's valid.
Portal 3 isn't totally empty. Therefore it's invalid.
Portal 4 is 3 by 3, totally empty, and bordered in obsidian. Therefore it's valid.
Portal 5 is 3 by 2 units, which is too small. Therefore it's invalid.
Portal 6 is missing a part of the border. Therefore it's invalid.

Challenge
Write a program or function that takes in these string representations of grids of obsidian and emptiness, and prints or returns the number of valid nether portals present.

Input can be from stdin or file or function argument.
You may assume the input is always well formed - i.e. a perfectly rectangular grid of text, at least 1 character wide and tall, only containing X and .. You may optionally assume there is a trailing newline after the last row.
If desired, you may use any two distinct printable ASCII characters in place of X and ..
Obsidian may be on the borders of the grid. Anything beyond the borders is considered empty.

Example input - the output should be 4:
................................................................
...................................XXXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX....XXXXXXXXX........X.......................X....
..X..X...X....X..X.........X..XXXX.X.......................X....
..X..X...X....X..X.......X.X..X....X.......................X....
..X..X...X....XXXX.........X..X..X..XXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX...XXXXXXXXXXX..X..X.X......................X..XXX
.............X...X....X...X...XXXX.X......................X..X..
.............X...X....X...X........X......................X..X..
..............XXX......XXX........XXXXXXXXXXXXXXXXXXXXXXXX...X..
..................................XX.........................XXX

Scoring
The submission with the fewest bytes wins.

Can I use another ASCII character in place of the newlines?

@Zgarb No, I still want the input to look like a grid.

When did nether portals' size change from static 2x3 to the optional larger sizes?

@Sparr SInce 1.7.2 (see the update history). I'm not sure if they can do this in the console editions.

Definitely +1 because Minecraft.

I see 6 valid portals in the example, how do you get to 4? Example

Perl, 81 86
Using more than one regexp.
#!perl -p0
$_=map{/.
/;$n="@-"-++$.;/(?=X{$.}..{$n}(X\.{$.}X.{$n}){3,22}.X{$.})/gs}($_)x21

The regexp for a specific width of a portal is much simpler than a generic one: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m} where m is the width of the portal and n is total width - 1 - m. The regexp must be put in a zero width forward assertion (?=...) because the matches may overlap. Then I iterate 21 times over this regexp setting $n and $.. "@-" evaluates to start position of the last match (/.\n/) which happen to be total width - 1. $. is used as the other variable as it is initialized to 1 when used with -p0.

You can save a byte if you use a different character than . for empty cells (so you don't have to escape it).

Regex (.NET flavour), 182 181 145 132 126 114 104 100 98 97 96 bytes
2D ASCII art pattern recognition? Sounds like a job for regex! (It doesn't.)
I know this is going to kick loose endless discussions again about whether regex submissions are valid programs or not, but I doubt this will beat APL or CJam anyway, so I don't see any harm. (That being said, they do pass our die-hard test for "What is a programming language?".)
This takes input as the string to be matched, and the result is the number of matches found. It uses _ in place of ., because I'd have to escape the latter. It also requires a trailing newline.
(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)

You can test it live at RegexHero or RegexStorm). The matches will be the top obsidian rows of the portals. If you can find a test case where it fails, please let me know!
What is this sorcery?
The following explanation assumes a basic understanding of .NET's balancing groups. The gist is that captures are stacks in .NET regex - every new capture for the same name is pushes onto the stack, but there's also syntax to pop captures from those stacks again, as well as syntax to pop captures from one stack and push captures onto another at the same time. For a more complete picture, you can have a look at my answer on Stack Overflow which should cover all the details.
The basic idea is to match a pattern like:
 X{n}..{m}
X_{n}X.{m} |
X_{n}X.{m} |  3 to 22 times
X_{n}X.{m} |
 X{n}..{m}

Where n is between 2 and 22 (inclusive). The tricky thing is getting all the ns and all the ms to be the same. Since the actual characters won't be the same, we can't just use a backreference.
Note that the regex has to embedded newlines, which I'll write as \n in the following.
(                     # Open capturing group 1. This will contain the top of a portal, which
                      # I can reuse later to match the bottom (being of the same length).
  X                   # Match a single X.
  (X){1,21}           # Match 1 to 21 X's, and push each separately on the <2> stack. Let's
                      # Call the number of X's captured N-1 (so N is the inner width of the
                      # portal).
)                     # End of group 1. This now contains N X's.
(?=                   # Start a lookahead. The purpose of this lookahead is to capture a
                      # string of N underscores in group 2, so I can easily use this to match
                      # the inside rows of the portal later on. I can be sure that such a
                      # string can always be found for a valid portal (since it cannot have 0
                      # inner height).
  \D+                 # Skip past a bunch of non-digits - i.e. *any* of the vaild characters
                      # of the input (_, X, \n). This to make sure I search for my N
                      # underscores anywhere in the remainder of the input.
  (                   # Open capturing group 3. This will contain a portal row.
    (?>               # This is an atomic group. Once the engine hass successfully matched the
                      # contents of this group, it will not go back into the group and try to
                      # backtrack other possible matches for the subpattern.
      (?<-2>_)+       # Match underscores while popping from the <2> stack. This will match as
                      # many underscores as possible (but not more than N-1).
    )                 # End of the atomic group. There are two possible reasons for the
                      # subpattern stopping to match: either the <2> stack is empty, and we've
                      # matched N-1 underscores; or we've run out of underscores, in which
                      # case we don't know how many underscores we matched (which is not
                      # good).
    _                 # We simply try to match one more underscore. This ensures that we
                      # stopped because the <2> stack was empty and that group 3 will contain
                      # exactly N underscores.
  )                   # End of group 3.
)                     # End of the lookahead. We've got what we want in group 2 now, but the
                      # regex engine's "cursor" is still at the end of the portal's top.
(?=                   # Start another lookahead. This ensures that there's actually a valid
                      # portal beneath the top. In theory, this doesn't need to be a
                      # lookahead - I could just match the entire portal (including the lines
                      # it covers). But matches cannot overlap, so if there were multiple
                      # portals next to each other, this wouldn't return all of them. By
                      # putting the remainder of the check in a lookahead the actual matches
                      # won't overlap (because the top cannot be shared by two portals).
  .                   # Match either _ or X. This is the character above the portal side.

  (                   # This group (4) is where the real magic happens. It's purpose is to to
                      # count the length of the rest of the current line. Then find a portal
                      # row in the next line, and ensure that it's the same distance from the
                      # end of the line. Rinse and repeat. The tricky thing is that this is a
                      # single loop which matches both inner portal rows, as well as the
                      # bottom, while making sure that the bottom pattern comes last.

    (?!\7)            # We didn't have a group 7 yet... group 7 is further down the pattern.
                      # It will capture an empty string once the bottom row has been matched.
                      # While the bottom row has not been matched, and nothing has been
                      # captured, the backreference will fail, so the negative lookahead will
                      # pass. But once we have found the bottom row, the backreference will
                      # always match (since it's just an empty string) and so the lookahead
                      # will fail. This means, we cannot repeat group 4 any more after the
                      # bottom has been matched.
    (.)*              # Match all characters until the end of the line, and push each onto
                      # stack <5>.
    \n                # Match a newline to go to the next line.
    .*                # Match as many characters as necessary to search for the next portal
                      # row. This conditions afterwards will ensure that this backtracks to
                      # the right position (if one exists).
    (                 # This group (6) will match either an inner portal row, or the bottom
                      # of the portal.
      X\3X            # Match X, then N underscores, then X - a valid inner portal row.
    |                 # OR
      ()              # Capture an empty string into group 7 to prevent matching further rows.
      \1.             # Use the captured top to match the bottom and another character.
    )
    (?=               # This lookahead makes sure that the row was found at the same
                      # horizontal position as the top, by checking that the remaining line
                      # is the same length.
      (?<-5>.)*       # Match characters while popping from the <5> stack.
      (?(5)!)\n       # Make sure we've hit end of the line, *and* the <5> stack is empty.
    )
  ){4,23}             # Repeat this 4 to 23 times, to ensure an admissible portal height.
                      # Note that this is one more than the allowed inner height, to account
                      # for the bottom row.
  \7                  # Now in the above repetition there is nothing requiring that we have
                      # actually matched any bottom row - it just ensured we didn't continue
                      # if we had found one. This backreference takes care of that. If no
                      # bottom row was found, nothing was captured into group 7 and this
                      # backreference fails. Otherwise, this backreference contains an empty
                      # string which always matches.
)

C#, 185 bytes
Here is a full C# function, just to make this a valid entry. It's time I wrote a command-line "interpreter" for .NET regular expressions...
static int f(string p){return System.Text.RegularExpressions.Regex.Matches(p,@"(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)").Count;}

Hmm, not sure how I feel about a pure regex answer. Matching the tops isn't the same as printing the number. It would of course be fine to use regex in a program and print the number of matches. Still, as you say, it will probably be beaten, so I'm too concerned either.

You can use ^ (or any unused character) for (?!).

@user23013 Oh, good point, thank you.

118 bytes.

@user23013 I got 114 with just using unnamed group, but not combining the line checks into one.

I think I'll not post it as an answer... as I can't seem to golf it anymore.

(X(X){1,21})(?=\D+((?>(?<-2>_)+)_)) still works, and removes a byte.

@user23013 oh right, thank you!

Typo and I don't have enough rep to edit, nor anything remotely helpful to add so I'll leave it here: every new capture for the same name is pushes onto the stack (should be pushed). Kudos, by the way, this is brilliant.

Python, 219 bytes
def f(s):s=s.split();L=len;R=range;return L([r for r in R(L(s))for a in R(L(s[0]))for w in R(2,23)for h in R(3,min(L(s)+~r,23))if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

Better than Java, but boy the quintuple nested loops hurt. The for/in might be slightly compressible using %s substitution, but it wouldn't save much.
Expanded:
def f(s):
  s=s.split()
  L=len
  R=range
  return L([r for r in R(L(s))
              for a in R(L(s[0]))
              for w in R(2,23)
              for h in R(3,min(L(s)+~r,23))
              if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*
                 all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

My instinct is to try the itertools nested loop generation sorcery.

Java, 304 bytes
This is a lot longer than a regular expression. It simply iterates over every possible square in the input. If it is a valid portal, it increments a counter by 1. It then returns the counter. This can probably be golfed much further. Any suggestions are welcome.
int a(String...a){a=a[0].split("\n");int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();for(;c<j;c++)for(d=0;d<i;d++)for(e=c+2;++e<j&e<c+24;)a:for(f=d+3;++f<i&f<d+24;){for(g=c;g<=e;g++)for(h=d;h<=f;h++){if(g==c|g==e&&h==d|h==f)continue;if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)continue a;}b++;}return b;}

Indented:
int a(String...a){
    a=a[0].split("\n");
    int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
    for(;c<j;c++)
        for(d=0;d<i;d++)
            for(e=c+2;++e<j&e<c+24;)
                a:for(f=d+3;++f<i&f<d+24;){
                    for(g=c;g<=e;g++)
                        for(h=d;h<=f;h++){
                            if(g==c|g==e&&h==d|h==f)
                                continue;
                            if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                continue a;
                        }
                    b++;
                }
    return b;
}

Full program:
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;

public class B {

    public static void main(String[] args) throws FileNotFoundException {
        String blocks = new BufferedReader(new FileReader(args[0])).lines().reduce((a,b)->a+"\n"+b).get();
        System.out.println(new B().a(blocks));
    }

    int a(String...a){
        a=a[0].split("\n");
        int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
        for(;c<j;c++)
            for(d=0;d<i;d++)
                for(e=c+2;++e<j&e<c+24;)
                    a:for(f=d+3;++f<i&f<d+24;){
                        for(g=c;g<=e;g++)
                            for(h=d;h<=f;h++){
                                if(g==c|g==e&&h==d|h==f)
                                    continue;
                                if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                    continue a;
                            }
                        b++;
                    }
        return b;
    }

}


text:
Your Language in a Box
Now with BONUS for run-time placement.
Write a program to fill a text box with the identifiers used in your program while keeping your program
small. With all the identifiers you have used (excluding those you created) in
your program, fill a 12x6 box with as many as you can. You get extra points for
identifiers that cross over (crossword style), but they can't join end to end.
Output
Your program should print (to stdout) a 12x6 character box with your packed identifiers and a # border. The
box should have columns labeled with letter A-L and the rows 1-6 (spaced like the example below). Then print a
line for each identifier used. Each line will have the location of the first
letter, the identifier itself, and the score. The score is equal to the number
of letters in the identifier with a possible '+bonus' added. The identifier gets
a 5 point bonus for each letter shared with a crossing identifier. The final
line reports 'TOTAL: ' and the sum of the identifier scores. An example output
for a possible Python program would look like this:
   ABCDEFGHIJKL
  ##############
1 #  pinsert   #
2 #  o         #
3 #  print     #
4 #    not     #
5 #            #
6 #import      #
  ##############
C1 pop 3+5
D1 insert 6
C3 print 5+10
E3 in 2+10
E4 not 3+5
A6 import 6
TOTAL: 55

Notes:

Identifiers can be unattached (like import above).
You cannot join pop and print inline with poprint.
The string in inside insert cannot be used. Joining words must be orthogonal.
Identifiers can be placed next to each other (like pop and insert above).

Your answer should include your program output with your source code and a title
consisting of the language name and your score.
Score
Your score for the challenge will the the puzzle score squared divided by the
size of your source code (in bytes). Eg: The puzzle above with a 300 byte
program would score 55*55/300 = 10.08. Highest score wins.
Rules

You can use any identifier in your program that is not defined by you.
Keywords, class names, method names, library names, and built-in function names are examples of eligible identifiers.
EDITED: You may only use standard libraries that are included with the minimum language release. Extended language packages and the use of external libraries (are now) forbidden. The huge range of libraries with extensive lists of identifiers would unbalance this challenge. If you are unsure of how this works with your language, please leave a question in the comments.
Identifiers must consist of [a-zA-Z_] characters only and have at least 2
characters.
You may only use each identifier once in the puzzle.
Identifiers can only be used left to right or downwards.

Dynamic Bonus!
If your code determines where to place identifiers at run time, the shared letter bonus will be 20 instead of 5. You may list which identifiers will used, but your code must decide where in the box to place them. Your code must also calculate and print the score list. If your placements depend on the ordering of the identifier list, hard-coded pairings, or other non-dynamic placement short-cuts, you are not eligible for the Dynamic Bonus.
In the example output above, the puzzle score for a run-time placement program would become 145. Then if the code was 800 bytes, the score would be 145*145/800 = 26.28.
The Dynamic Bonus is designed to reward clever algorithms instead of static hard-coded solution strings, and compensate for the larger resulting source code size.
EDITS:

Changed libraries used to only those in the minimum language release.
Added the dynamic bonus option.

Just to be clear, greater score is better, right?

Correct. Jam as many unique identifiers into the box while keeping your program as small as possible -> best score.

Does this challenge actually involve programming?

Perhaps I should make this more clear. You must write and execute a program that outputs the text requirement. The text in the output depends on the identifiers used in the program you write.

FYI, some libraries involving SIMD or Shader defines all combinations of xyzw / rgba / stpq :)

@KennyTM I realise now that free libraries may be abused. I have changed the question to allow only standard libraries. I apologise to any who have done work that is now prohibited.

Is it right that builtin methods count as well, since you've used list.pop and list.insert?

@grc: Yes. Identifiers such as builtin methods can be used in the puzzle if used in your program. They are identifiers from the standard language (and obviously not created by you) so are allowed.

Can words be placed in sequence (ex. popprint)?

@Doorknob: Yes. Words can be touching, end to end, or otherwise.

Lets say my language has keywords: ab, cd, ef, abc, def. Can I score for all of them (for a total of 12 points) with a row abcdef?

@nutki: no. You may not embed words in other words or connect them in a line. Words may only be connected orthogonally. There are however many possible sharing letters (I count 4) in your example which would score well.

Do you have to use the keywords actively? (I mean you could write a do-loop with nothing in it just so you can use the keyword)

The identifiers used must be used correctly for your language. They must be executed or at least be able to be executed (you can't just list the keywords you want to use). It is not required that the code does anything useful.

STATA, 387^2 / 677 = 221.2
I got lazy and just wanted to output something that works before trying to get it with optimal score. I'll probably update it later as I fit more words in, and I'm open to suggestions from anyone that uses STATA (which doesn't seem very popular on CodeGolf). STATA is really good about having a lot of two letter commands/parameters. Also, usually most can be shortened to save characters/fit better (i.e. display can be display, displa, displ, disp, dis, or di). Also, the capture means that it suppresses output and error messages. So the entire while loop has 0 output.
cap infile using a,us(b)
cap while _rc>0{
ls
cap ge c=1 if 0<1
so c
egen d=rownonmiss(c),str
regres c d
notes
clist,noh no
li,compress
dec c,g(f)
do a
}
gl e=";;;ABCDEFGHIJKL ;;############## 1;#rownonmissdo# 2;#e;hd;o;notes# 3;#geii;hif_rc;# 4;#r;ls;clist;;# 5;#egen;ailu;;;# 6;#slcompress;;# ;;############## A1;rownonmiss;10+30 K1;do;2+5 H2;notes;5+20 A3;ge;2+5 G3;if;2+5 I3;_rc;3+15 C4;ls;2+10 F4;clist;5+20 A5;egen;4+20 C6;compress;8+20 A1;regres;6+15 C1;while;5+15 F1;noh;3+5 H1;infile;6+25 I1;so;2+10 J1;str;3+15 K1;dec;3+15 D2;dis;3+5 I3;_s;2+10 F4;cap;3+10 G4;li;2+5 B5;gl;2+5 D5;no;2+10 I5;us;2+5 TOTAL:;387"
token $e
forv x=1/34{
dis subinstr(``x'',";"," ",.)_s(0)
}

generates
   ABCDEFGHIJKL
  ##############
1 #rownonmissdo#
2 #e hd o notes#
3 #geii hif_rc #
4 #r ls clist  #
5 #egen ailu   #
6 #slcompress  #
  ##############
A1 rownonmiss 10+30
K1 do 2+5
H2 notes 5+20
A3 ge 2+5
G3 if 2+5
I3 _rc 3+15
C4 ls 2+10
F4 clist 5+20
A5 egen 4+20
C6 compress 8+20
A1 regres 6+15
C1 while 5+15
F1 noh 3+5
H1 infile 6+25
I1 so 2+10
J1 str 3+15
K1 dec 3+15
D2 dis 3+5
I3 _s 2+10
F4 cap 3+10
G4 li 2+5
B5 gl 2+5
D5 no 2+10
I5 us 2+5
TOTAL: 387

This answer looks valid. Currently the leader.

Python, 1342 / 349 = 50.02
If I have understood the rules correctly, this should be a valid submission.
from sys import *
stdout.write("""   ABCDEFGHIJKL
  ##############
1 #from   f  i #
2 #  r   not t #
3 #      write #
4 #  s   import#
5 #  y   False #
6 #  stdout    #
  ##############
A1 from 4+5
C1 or 2+5
H1 format 6+25
K1 iter 4+10
G2 not 3+5
G3 write 5+10
C4 sys 3+5
G4 import 6+10
G5 False 5+5
C6 stdout 6+10
TOTAL 134
""".format(not False or iter([])))

You can really just keep incrementing your score by adding more identifiers: the size of the program increases linearly (by approx. twice the identifier length), while the score increases approximately by the square of the identifier length. Then the challenge becomes more how to cram most keywords into the square instead of how to write a short program to do it.

Your answer looks valid. I had planned to motivate programmers to write a dynamic solver with some level of introspection, but I expect this embed-the-answer-in-a-string approach will be easier. Sigh.

Your point that the challenge is more puzzle than programming is well taken. I have added a bonus for answers that use run-time placement in their programs. The string printing style is still valid, but I hope to see more programming solutions that make use of the bonus. Thanks for your answer and insights +1.

Maybe I'm just missing something, but why stdout.write rather than print, and what's with the format(not False or iter([])) at the end?  You could also easily add as "is" next to the "sys" and a "for" below "from"...

@aquavitae You can only use identifiers that are used in your program in valid syntax, so Frxstrem is including the identifiers that will be used in the puzzle. The program does not have to make sense or be efficient.

Ah, sorry, apparently I didn't read the problem properly. In that case you could change the format to read iter([i for i in [not False is sys]])

Perl, 7282 / 639 = 829.4
Oh well, this is not valid, missed that I have to have the identifiers in my code.
#!perl -l
use B::Keywords'@Symbols','@Barewords';
use List::Util shuffle;
srand 45502;
@b=@a=shuffle map{push@{+length},$_;$_}grep/^[a-z]{2,}$/,@Symbols,@Barewords;
$z=$"x12 .$/;$z x=6;
$s=length,$z=~s/ {$s}/$_/&&($_=0)for@a;
$_=$z;$"='|';
sub f{join'',/(.)(?=@_.*(\n))/sg}$_=f".{12}(.)"x5;
s/@a/$v=length$&;$tot+=$v*21;$r.=(map{m!.!;map{$&.$_}1..7}A..L)[@-]." $& $v+".($v*20)."\n";uc$&/ge;
$_=f".{6}(.)"x11;
s/@b/$v=length$&;$b=$&=~y!A-Z!!;$tot+=$v+$b*20;$c=lc$&;$r.=(map{m!.!;map{$_.$&}A..M}1..6)[@-]." $c $v+".($b*20)."\n";uc$&/ige;
$_=$z;
s/
/#
/mg;
s/^/++$l.' #'/mge;
print'   ',A..L,'
  ','#'x14,'
',$_,'  ','#'x14,"
${r}TOTAL: $tot"

This requires a perl reflection module (B::Keywords). Can be installed on ubuntu with sudo apt-get install libb-keywords-perl. With the seed given in the code above it generates the 728 answer:
   ABCDEFGHIJKL
  ##############
1 #dumplogforqr#
2 #lcfirstbreak#
3 #socketshmctl#
4 #requiregiven#
5 #lengthgmtime#
6 #getserventdo#
  ##############
B1 uc 2+40
C2 fc 2+40
F3 tr 2+40
G1 gt 2+40
I1 or 2+40
J1 recv 4+80
L4 ne 2+40
A1 dump 4+20
E1 log 3+20
H1 for 3+40
K1 qr 2+0
A2 lcfirst 7+60
H2 break 5+40
A3 socket 6+40
G3 shmctl 6+20
A4 require 7+20
H4 given 5+40
A5 length 6+0
G5 gmtime 6+20
A6 getservent 10+0
K6 do 2+0
TOTAL: 728

Note that different versions of perl may have different RNG and different keyword list, but it should be easy to find a seed with a comparable result.

You have spotted one of the problems - identifiers must occur at least once in your code. There is another problem. You should not use libraries that are not provided in the basic language package. This is a necessary rule to stop the use of libraries that would provide unfair advantages in this challenge. I hope you can change your approach and create a good Perl answer for the challenge.

source: Stack Exchange

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

sort: votes


text:
insertspacesbetweenwords
In this challenge, your input is a string of lower-case letters like this:
insertspacesbetweenwords

and a dictionary like the that from my other challenge. You may assume that the dictionary file contains only lower-case letters and line-feed characters. Furthermore, the last character in the dictionary file is a line-feed character and the entries are sorted alphabetically.
Write a function that given these two strings, returns a single string containing all possible ways to insert spaces between some of the characters in the input string, such that the words created are all in the dictionary. Each possibility shall be terminated with a line-feed character. Some lines of the output for the example are:
insert spaces between words
insert space s between words
insert spaces between word s
insert space s between word s
insert spaces be tween words

The order of the output lines doesn't matter.
This is codegolf, the usual scoring rules apply, standard loopholes are verboten.

Are trailing spaces acceptable?

I still don't get the input format. Is it the string of letters and then each word in the dictionary? If so, how do we know when the input is done?

@KSFT Your input is two strings. One string contains the dictionary, the other contains the word-string where you shall insert spaces.

@Zgarb No. The question says “all possible ways to insert spaces between some of the characters in the input string;” trailing spaces are not between characters of the input string.

Is the word s in your dictionary, but not other letters of the alphabet?

@feersum The example output is just a selection of the lines of the output for insertspacesbetweenwords. The actual output is much longer.

s isn't a word I would expect to find in the dictionary, so it's still unclear to me whether s is a dictionary word, or if letters may be left over if they can't be included in any of the words.

@feersum In this particular example I used a dictionary where all single characters a re part of the dictionary. All words formed by inserting spaces between them must be in the dictionary as mentioned in the challenge.

Can the input string be empty?

@Zgarb You may assume that it isn't.

@britishtea Please read the post, it says exactly how the dictionary string is formatted. It's one word per line, all lower-case characters, with a single line-feed character terminating each line.

Haskell, 113 107 105 88 87 86 bytes
Works for empty inputs too (but gives an empty string as output).
s!d=unlines[w|w<-map concat$mapM(\c->[[c],[' ',c]])s,all(`elem`lines d).words$w,w>"!"]

Defines an infix binary function !. Call it like this:
"abababbaab" ! "ab\nba\na\nbab\n"

Result:
"ab ab ab ba ab\nab a bab ba ab\na bab ab ba ab\na ba bab ba ab\n"

Explanation
The idea is to split the left input string s into words by inserting spaces in all possible ways, and keep those that consist of words of the dictionary d. A leading space is checked by comparing to the string "!".
s!d=                           -- Define the string s!d by
 unlines                       -- joining with line-breaks
  [w|w<-                       -- the strings w obtained by
    map concat$                -- concatenating each list of strings
    mapM(\c->[[c],[' ',c]])s,  -- obtained by replacing each letter 'c' of s by
                               -- either "c" or " c",
   all(`elem`lines d).         -- such that only lines of d
    words$w,                   -- occur as words in w, and
   w>"!"]                      -- w is lexicographically larger than "!",
                               -- which here means that w does not begin with a space.

Python 3, 88
f=lambda x,w,s=[]:[x or print(*s)]+[x.find(y)or f(x[len(y):],w,s+[y])for y in w.split()]

String to split is x, the dictionary string is w.
The idea is to repeatedly check which strings y of the dictionary are a prefix for the current string x. The expression x.find(y) evaluates to the Falsey 0 only if x starts with y (substrings not present give -1), so the short-circuiting of or makes the function recurse down only when the prefixes matches. The prefix is chopped off with x[len(y):] and the list of subwords is updated in s.
When the whole string x has been consumed, we print the subwords s, automatically joined by spaces.

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


text:
Find Privileged Substrings
Privileged Strings
The set of privileged strings is defined recursively as follows.

All strings of length 0 or 1 are privileged.
A string s of length at least 2 is privileged, if there exists a shorter privileged string t that occurs in s exactly twice, once as a prefix and once as a suffix. Overlapping occurrences are counted as distinct.

For example, the strings aa, aaa and aba are privileged, but ab and aab are not.
Input
An alphanumeric string.
Output
All privileged substrings of the input string, each exactly once, in any order. The output can be given in your language's native array format (or closest equivalent), or printed one substring per line.
Fun fact
The number of strings in the output is always exactly length(s) + 1 (source).
Rules
Both functions and full programs are permitted. The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
These are sorted first by length and then alphabetically, but any order is acceptable.
"" -> [""]
"a" -> ["","a"]
"abc" -> ["","a","b","c"]
"abcaaabccaba" -> ["","a","b","c","aa","cc","aaa","aba","abca","abcca","bccab","bcaaab","caaabc"]
"1010010110101010001101" -> ["","0","1","00","11","000","010","101","0110","1001","01010","10001","10101","010010","101101","0101010","1010101","01011010","10100101","1010001101","1101010100011","00101101010100","011010101000110"]
"CapsAndDigits111" -> ["","1","A","C","D","a","d","g","i","n","p","s","t","11","111","igi","sAndDigits"]

Leaderboard
Here's a by-language leaderboard, courtesy of Martin Büttner.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
# Ruby, <s>104</s> <s>101</s> 96 bytes

function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45497;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*((?:[^,\s]|\s+[^-,\s])*)/
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	AuthorLanguageSize

Winners by Language

LanguageUserScore

{{PLACE}}	{{NAME}}{{LANGUAGE}}{{SIZE}}Link

{{LANGUAGE}}{{NAME}}{{SIZE}}Link

Can the output be space-separated or does it have to be separated by newlines? (if printing)

@Sp3000 It has to be either newlines, or however your language prints an array of strings.

So you're asking us to check your privileged strings?

why such a long definition? Couldn't you have equivalently written "a priveliged string is a string that begins and ends with the same symbol, said symbol not occuring anywhere else in the string"? =)

@Mints97 The shorter string t may not be a single symbol. For example, aaa is a privileged string, since it has aa as a prefix and suffix, and it occurs only twice. I added it as an example.

oh, my bad. Sorry. Didn't realize the difference.

.NET Regex, 31 bytes
(?=(((?<=(\3\2|)).+?(?<=\3))*))

The strings are captured in \1 in each match.
Explaination
(?=                             # Lookahead. This makes it possible to catch overlapped
                                #   strings in \1.
    (                           # The captured group \1 for result.
        (                       # Match 0 or more occurrences.
            (?<=(\3\2|))        # Set \3 to the string from last \3 to the current position,
                                #   or an empty string for the first time.
            .+?(?<=\3)          # Match a shortest nonempty string so that the whole string
                                #   from the beginning to the current position ends with \3.
        )*
    )
)

CJam, 33 45 39 38 bytes
l_,,\f>{(0{:U2$>2$2$#):T<+UT+T}g;\;N}%

Let's say it is printed without a trailing newline. So the trailing newline means an empty substring...
Explaination
l              " Read one line. ";
_,,            " Get an array of 0 to array length-1. ";
\f>            " Get all nonempty suffixes. ";
{              " For each suffix: ";
    (          " Extract the first character. Say the first character X and the rest Y. ";
    0          " Push U = 0. ";
    {          " Do: ";
        :U     " Set variable U. ";
        2$>    " Z = Y with first U characters removed. ";
        2$2$#  " Find X in Y, or return -1 if not found. ";
        ):T    " Increment and save it in T. ";
        <+     " Append the first T characters of Z to X. ";
        UT+    " U += T. ";
        T      " Push T. ";
    }g         " ...while T is nonzero. ";
    ;\;        " Discard U and Y. ";
    N          " Append a newline. ";
}%

Python 2, 179 173 164 bytes
exec"f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n%s);g=lambda s:filter(f,{''}|{s[i:j+1]for i%sfor j%s})"%((" in range(len(s))",)*3)

Pretty bulky currently — I wonder if it's possible to combine the check and the substring generation somehow...
The lambda f is basically an is_privileged() function, combining the three conditions into one comparison (substring is privileged, appears twice, is suffix and prefix).
Expanded:
f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n in range(len(s)))
g=lambda s:filter(f,{''}|{s[i:j+1]for i in range(len(s))for j in range(len(s))})

Python 3, 131 129 bytes
f=lambda s,p={''}:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)or list(p)

This recursively finds privileged substrings, starting with the shortest ones and adding them to a set. The set is then used in determining whether longer substrings are privileged.
Unfortunately, it is a one-use-only function. Here's a corresponding full program (145 bytes):
p={''}
f=lambda s:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)
f(input())
print(list(p))

Python, 152 147 126 116 bytes
def n(s):
 w='';t=[w]
 for a in s:w+=a;t+=[w[w.rfind(w[-max(len(q)for q in t if w.endswith(q)):],0,-1):]]
 return t

As demonstrated in the linked paper, there is a unique privileged suffix for every prefix of a string. That suffix is of the form p·u·p where p is the longest previously found privileged substring which is a suffix of the prefix. (The search is the argument to max, which actually finds the length of p because it was easier to do max than longest.) Once p is found, the suffix itself is formed by searching for the second last occurrence of p in the prefix, using rfind constrained to not use the last character. We know that will work, because p is a previously found suffix. (A more rigorous proof of the algorithm can be derived from the paper.)
I'm pretty sure that this could be implemented in linear time using a suffix tree, instead of the quadratic cubic algorithm used above, but the above program is certainly fast enough in all the test cases, and handles a string of 2000 as in a little less than a second on my (not superpowered) laptop.

Ruby, 87
I do feel like there's a recursive regex solution here somewhere, but I'm not very good at those, so here's a very slow and long recursive function.
f=->s{s[/./]?(o=f[$']|f[s.chop];o.any?{|t|s[/^#{t}/]&&s[/.#{t}/]&&!$'[0]}&&o<<s;o):[s]}

Algorithm is roughly the same as grc's, made slower (but shorter) by not special-casing single characters. A single-character string can be considered privileged due to having the empty string as a prefix, a suffix, and nowhere else.
The other interesting trick here is the use of $', a magic variable inherited from Perl that takes the value of the string after the most recent regular expression match. This gives me a short way of chopping the first character off of a string, although I gain almost all of those characters by having to set it up with s[/./] instead of s[0]. I use it again to check that the second substring match occurs at the end of the string.

J, 92 bytes
Takes a couple seconds on the longest input.
p checks if a string is privileged (with recursion), s checks every substring using p.
   p=.1:`(+./@:(($:@>@{.*((2=+/)*1={:)@{.@=)@(<\))~i.@#)@.(1<#)
   s=.3 :'~.a:,,(<@#~p)\.\y'

Tests:
   s 'CapsAndDigits111'
┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬───┬─┬──────────┬─┬──┬───┐
││C│a│p│s│A│n│d│D│i│g│igi│t│sAndDigits│1│11│111│
└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴───┴─┴──────────┴─┴──┴───┘

   input =. '';'a';'ab';'abc';'abcaaabccaba';'1010010110101010001101';'CapsAndDigits111'

   s each input
┌──┬────┬──────┬────────┬─────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────────────────...
│┌┐│┌┬─┐│┌┬─┬─┐│┌┬─┬─┬─┐│┌┬─┬─┬─┬────┬──┬───┬──────┬──────┬──┬─────┬─────┬───┐│┌┬─┬─┬───┬───┬──┬────┬──────┬────────┬──┬────┬──────┬────────┬─────┬─────┬───────┬───────┬──────────────┬───┬─────┬─────────────┬───────────────┬──────────┐│┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬...
││││││a││││a│b││││a│b│c││││a│b│c│abca│aa│aaa│bcaaab│caaabc│cc│abcca│bccab│aba││││1│0│101│010│00│1001│010010│10100101│11│0110│101101│01011010│10101│01010│1010101│0101010│00101101010100│000│10001│1101010100011│011010101000110│1010001101││││C│a│p│s│A│n│d│D│i│...
│└┘│└┴─┘│└┴─┴─┘│└┴─┴─┴─┘│└┴─┴─┴─┴────┴──┴───┴──────┴──────┴──┴─────┴─────┴───┘│└┴─┴─┴───┴───┴──┴────┴──────┴────────┴──┴────┴──────┴────────┴─────┴─────┴───────┴───────┴──────────────┴───┴─────┴─────────────┴───────────────┴──────────┘│└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴...
└──┴────┴──────┴────────┴─────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────────────────...

   #@s each input NB. number of strings in outputs
┌─┬─┬─┬─┬──┬──┬──┐
│1│2│3│4│13│23│17│
└─┴─┴─┴─┴──┴──┴──┘

   # each input NB. input lengths
┌─┬─┬─┬─┬──┬──┬──┐
│0│1│2│3│12│22│16│
└─┴─┴─┴─┴──┴──┴──┘

JavaScript (ES6) 195
The P function recursively verifies that a string is privileged.
The F function tries every substring contained into the given string. Found strings are stored as keys of a hashtable to avoid duplicates.
At last, the keys are returned as output.
F=a=>{
  P=(s,l=s.length,r=l<2,j=1)=>{
    for(;!r&&j<l;j++)s.indexOf(x=s.slice(0,j),1)+j-l||(r=P(x));
      return r
  };
  for(o={'':l=i=0};a[i+l]||a[i=0,++l];)
    if(P(p=a.slice(i++,i+l)))
      o[p]=0;
  return[a for(a in o)]
}


text:
Navigate text with arrow keys
Background
Most (halfway decent) text editors allow you to navigate text using the arrow keys.  Up and down allow you to navigate lines, while left and right move across a line but also wrap around.  Furthermore, if the line is shorter than your cursor's X position, the cursor appears at the end of the line but returns to the same X position if you keep moving up or down.  Perhaps the following visual explanation will help:
Examples Of Motion
A simple sample of text could look like this.  The cursor will be inserted between two characters in this text, or at an end.
-----
---
------

let's put the cursor here:

X-----
---
------

move down (v):

-----
X---
------

move left (<):

-----X
---
------

v

-----
---X
------

v (notice how the X position of the cursor has been maintained)

-----
---
-----X-

^

-----
---X
------

>  (more line wrapping)

-----
---
X------

<

-----
---X
------

^ (the X-position from earlier is no longer maintained due to the left-right motion)

---X--
---
------

The Challenge
Given several lines of ASCII test, find the shortest path from the start location to the end location.  The start location is represented by ^ and the end location is represented by $, and there will only be one of each.  These aren't considered part of the text and don't contribute to that line's "length."
The input will consist of several non-blank lines of text.  Output will be a series of ^v<> characters that show one of the shortest paths.  You may optionally assume an additional newline at the end of each, but that is not included as part of the navigable text.
You can write a program or named function.  The winner will be the shortest submission, measured in bytes.
Example I/O
^Squares
are
fun$ny

vv<v  (which is better than the naive vv>>>)

Squares
^are
funny$

<vv

Alp$habet^
Song

v<^

Mary had a little lamb,
His fleece was white as snow,
And$ everywhere that ^Mary went,
The lamb was sure to go.

^^>>>>v>>>

$^degenerate case

(no output)

"The cursor will be inserted between two characters in this text, or at the end" -- proceeds to put the cursor at the beginning in the first example

There are two ends of every line.  Edited to "an end."

Vim allows arrows.   I have a real vi on my AIX box that does not ( I have added map statements to my startup file). "halfway decent"... yep

The first example's output could also be v<vv, right? Or would that end after the last character on that line?

@mbomb007 It would end after the last character of the line.

CJam, 139 bytes
Well this took many hours to come to something that feels done. It feels like the time it takes to aggressively optimize CJam code is something larger than O(n) with respect to the size of the code...
You can try it online, but for any input for which the best path is at least 6 operations or so, you should probably try it offline with a faster interpreter.
Squished:
q_'$-_'^-:T;'^#\'^-'$#W{)2$5Y$5b+{:D[L"_T<W%_N#)_@>N+N#X-Ue>+-"_"W%-U"--2'<t2'>t'++'(')]=~0e>T,e<D3/1$T<N\+W%N#X?:X;}/2$-}g5b{" ^v<>"=}%]W=

Expanded and commented:
q               "Read the input";
_'$-            "Remove the end marker";
_'^-:T;         "Remove the start marker and save the text";
'^#             "With only the end marker removed, locate the start marker";
\'^-'$#         "With only the start marker removed, locate the end marker";
W               "Initialize the path number to -1";
{               "Do...";
  )               "Increment the path number";
  2$              "Initialize the cursor position to that of the start marker";
  5Y$5b+          "Convert the path number to base 5, then add a leading 5
                   (the leading 5 will act to initialize the column memory)";
  {:D             "For each digit in the path digit string:";
    [               "Begin cases:";
      L               "0: Do nothing";
      "_T<W%_N#)_@>N+N#X-Ue>+-"
"REFS: [   1   ][  2  ][ 3 ]45
                       1: [1] Calculate the distance to the end of the previous
                              line (0 if no such line)
                          [2] Calculate the length of the previous line (0 if
                              no such line)
                          [3] Calculate the distance to move backwards in the
                              previous line as the maximum of the length of the
                              previous line minus the column memory and 0
                          [4] Calculate the total distance to move as the sum
                              of [1] and [3]
                          [5] Subtract [4] from the cursor position";
      _"W%-U"-        "2: Start with a base of the logic of case 1, but with a
                          few operations adjusted.";
      -2'<t2'>t       "   [1] Calculate the distance to the *start* of the
                              *next* line (0 if no such line)
                          [2] Calculate the length of the *next* line (0 if no
                              such line)
                          [3] Calculate the distance to move *forwards* in the
                              *next* line as the *minimum* of the length of the
                              *next line* and *the column memory*
                          [4] Calculate the total distance to move as the sum
                              of [1] and [3]";
      '++             "   [5] *Add* [4] *to* the cursor position";
      '(              "3: Decrement the cursor position";
      ')              "4: Increment the cursor position";
    ]=~             "Execute the case corresponding to the path digit mod 5";
    0e>T,e<         "Clamp the cursor position to [0, text length]";
    D3/             "Check if the path digit is not 0, 1, or 2...";
    1$T<N\+W%N#     "Calculate the current column";
    X?:X;           "If the above check succeeded, update the column memory";
  }/              "End for each";
  2$-             "Subtract the end marker position from the cursor position";
}g              "... While the above subtraction is nonzero";
5b              "Convert the path number to base 5";
{" ^v<>"=}%     "Map each digit in the path string to its operation symbol";
]W=             "Clean up";

Overall, this is a pretty straightforward solution. It "executes" the digits of the base-5 representation of a path number that is incremented every iteration, starting with 0, until a path works. The digits 1-4 map to the operations up, down, left, and right, and 0 does nothing. The first iteration using a path of just 0 catches the degenerate case. All other paths that contain a 0 are never selected because they're just versions of already-tested paths with added no-ops.
The state is modeled in as minimalistic of a way as possible: the text with start and end markers removed, the cursor position in the text, and the "column memory." Newlines are mostly treated like any other character, so there's no concept of a row, and the cursor position is just an index. This makes moving left and right dead simple, which are just implemented as decrement and increment (with clamping to the size of the text). Moving up and down is a bit trickier, but still manageable.
Code reuse was a pretty vital optimization tactic. Examples of this include:

Writing the code for moving up in a way such that it's smaller to generate the code for moving down at runtime than to write its own code. This is done by copying the code for moving up and removing/replacing a few characters.
Updating the "column memory" is done conditionally based on the path digit divided by 3 instead of it being coded into the logic of the operation. This also allows initialization of the column memory by adding a dummy 5 operation to the start of the path string, which also just so happens to use the 0 no-op logic due to circular array indexing and there being only 5 defined operations.

Overall, I'm very happy with how this came out. This is definitely the most work I've put into a code golf answer to date (for something that fits into a tweet!?). The run time is pretty abysmal, though. CJam isn't exactly the fastest language to begin with and this algorithm has a complexity of something like O(m*5n), where m is the size of the input and n is the size of the output. Good thing speed doesn't count!

Nice :) I feel a bit guilty for indirectly making you spend so much time on this :p

Python 2: 446
Q=input().split('\n');
def g(c):l=[l for l in Q if c in l][0];return Q.index(l),l.index(c)
a,b=g('^');c,d=g('$');Q=map(len,Q);Q[a]-=1;Q[c]-=1
if a==c:d-=b<d;b-=d<b
t=-1
while Q:
 l=[];T=t=t+1;x,y,z=a,b,b
 while T:l+=[T%5]*(T%5>0);T/=5
 for T in l:A=":x+=T+T-3;y=min(Q[x],z)";B="x<len(Q)-1";exec"if "+["","x"+A,B+A,"y:y=z=y-1\nelif x:x-=1;y=z=Q[x]","y<Q[x]:y=z=y+1\nelif "+B+":x+=1;y=z=0"][T]
 if(x,y)==(c,d):print''.join(' ^v<>'[x]for x in l);Q=0

Straightforward solution. I'm performing a breadth-first search. t iterates over all different paths. I convert t into base 5, but only use the entries, which are nonzero. 1 is up, 2 is down, 3 is left  and 4 is right.
I keep the current position of the cursor in 3 variables x, y and z. x is the line, y the column position, and z the 'hidden' column position, if you go up or down and the line is too short. Lots of ifs decide, how the variable change during a move.
Preprocessing is really lengthy, the first 4 lines perform only this task.
The long testcase takes a really long time. The algorithm has a complexity of O(N*5^N), where N is the length of the shortest solution.
Usage: Input the lines as a single string (lines seperated by \n) like "Alp$habet^\nSong"

CJam - 274
No answer yet? Ok, here's one :)
qN/_{0:V;{_'^={[UVV]:B;;}{'$={[UV]:E;}{V):V;}?}?}/U):U;}/"^$"f-:,:A;{:X0=[X0=(_A=X2=_@e<\]X?}:U;{:X0=A,(=X[X0=)_A=X2=_@e<\]?}:D;{:X1=[X~;(_]{X0=[X0=(_A=_]X?}?}:L;{:X1=X0=A=={X0=A,(=X[X0=)0_]?}[X~;)_]?}:R;[[BM]]{_{0=2<E=},_{0=1=o0}{;[{"U^DvL<R>"2/\f{[~@1/~@\+@@~\]}~}/]1}?}g;

Try it at http://cjam.aditsu.net/ ... except for the Mary example or something of that size, you'll probably want the java interpreter.

WTF? 274 !!!!!!

@Optimizer hahaha, well, I wasted enough time on it, go ahead and golf it more if you want :p


text:
Convert human readable time interval to date components
Challenge
Write the shortest program that converts a human readable time interval to date components of the form:
{±YEARS|±MONTHS|±DAYS|±HOURS|±MINUTES|±SECONDS}

Sample cases
Each test case is two lines, input followed by output:
1 year 2 months 3 seconds
{1|2|0|0|0|3}

-2 day 5 year 8months
{5|8|-2|0|0|0}

3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds
{17|0|3|0|-5|1}

Rules

You can not use strtotime or any built-in function that does the whole job.
Shortest code wins (bytes)
You can print your output to stdout or a file, the result can also be returned by a function, it's up to you
The token can be in singular or plural form.
The components may be in a random order
There may be no white space between the number and the token
Sign is optional when the time interval is positive (input and output)
If a component appears more than once the values should be added
Each component has its own sign
The components should be handled separately (e.g. 80 minutes remains as 80 in the output)
The input is guaranteed to be lower case

Happy Golfing!

I like this challenge but I'm having a hard time coming up with anything that isn't long and messy in languages which are ill-suited for code golf. :/

Does output format matter?

Sign is optional when the time interval is positive Does that mean that input may contain + signs?

CJam, 60 bytes
After being stuck in the 60's for a long time, I finally managed to squeeze this down to 60 bytes. Good enough! Ship it!
Try it online
Squished:
'{0a6*q[{_A,s'-+#)!{"ytdhic"#:I){]'0+iA/I_3$=@+t[}*}*}/'|*'}

Expanded and commented:
'{              "Add '{' to output";
0a6*            "Initialize time to a list of 6 zeros";
q               "Read the input";
[               "Open an empty numeric character buffer";
{               "For each character in the input:";
  _               "Append the character to the numeric character buffer";
  A,s'-+#)!       "Check if the character is not part of a number";
  {               "If so:";
    "ytdhic"#:I     "Remove the character from the numeric character buffer and
                     convert it to the corresponding time unit index, or -1 if
                     not recognized
                     (Time units are recognized by a character in their name
                     that does not appear before the recognition character
                     in any other name)";
    ){              "Repeat (time unit index + 1) times:";
      ]'0+iA/         "Close the numeric character buffer and parse it as an
                       integer (empty buffer is parsed as 0)";
      I_3$=@+t        "Add the integer to the value of the indexed time unit";
      [               "Open an empty numeric character buffer";
    }*              "End repeat
                     (This is used like an if statement, taking advantage of
                     the fact that iterations after the first have no effect)";
  }*              "End if";
}/              "End for";
'|*             "Insert a '|' between each time unit value (implicitly added to
                 output)";
'}              "Add '}' to output";

I initially started using a token-based approach, but that got pretty firmly stuck at... 61 bytes. Sigh. So I totally changed gears and switched to this character-based approach, which is much more interesting anyways.
My parsing method works by adding any valid numeric characters reached (0-9 and -) to a buffer and parsing the buffer as an integer when a certain character from one of the time unit names is reached. Those characters are y, t, d, h, i, and c, which all satisfy the conditions that they appear in a time unit name and don't appear before the recognition character in any other time unit name. In other words, when one of these time unit recognition characters is reached, the numeric buffer will be filled with the last number seen if this actually signals a time unit, or the numeric buffer will be empty if this just appears in, but shouldn't signal, some other time unit. In either case, the numeric buffer is parsed as an integer, or 0 if it was empty, and this is added to the corresponding time unit value. Thus recognition characters appearing in other time units after their recognition character have no effect.
Other crazy hacks include:

Abusing loops so numeric characters are left on the stack (which acts as the numeric character buffer) "for free."
Repeating a block zero or multiple times instead of conditionally because the loop is more compact than an if statement, and iterations after the first have no effect.

For anyone curious about my token-based solution that got stuck at 61 bytes, I'll post it here as well. I never got around to expanding or commenting it, though.
CJam, 61 bytes
'{0a6*q'm-'{,64/~m*{:X/XS**}/S%2/{~0="yodhis"#_3$=@i+t}/'|*'}

+1 This definitely deservers more upvotes.

@Forlan07 Thanks for the support. :) But I was a bit late to answer, so it's not unexpected. The process of producing this answer was satisfying enough anyways.

Perl: 61 characters
Thanks to @nutki.
s/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge

Sample run:
bash-4.3$ perl -pe 's/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge' <<< '1 year 2 months 3 seconds'
{1|2|0|0|0|3}

bash-4.3$ perl -pe 's/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge' <<< '-2 day 5 year 8months'
{5|8|-2|0|0|0}

bash-4.3$ perl -pe 's/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge' <<< '3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds'
{17|0|3|0|-5|1}

My poor efforts: 78 77 characters
s/([+-]?\d+) *(..)/$a{$2}+=$1/ge;$_="{ye|mo|da|ho|mi|se}";s/\w./$a{$&}||0/ge

Some improvements I could find: s/(-?\d+) *(..)/$$2+=$1/ge;$_="{ye|mo|da|ho|mi|se}";s/\w./${$&}+0/ge

Another 4 chars: s/-?\d+ *(m.|.)/$$1+=$&/ge;$_="{y|mo|d|h|mi|s}";s/\w+/${$&}+0/ge

Wow. Great tricks, @nutki.

Also found in other solutions, (m.|.) -> m?(.) saves extra 4.

Doh. That was about to try out now. So it works. :)

Python 2, 99 bytes
import re
f=lambda I:"{%s}"%"|".join(`sum(map(int,re.findall("(-?\d+) *m?"+t,I)))`for t in"yodhis")

This is a lambda function which takes in a string and simply uses a regex to extract the necessary numbers.
Thanks to Martin for pointing out that \s* could just be <space>*. It's easy to forget that regexes match spaces literally...

Ruby, 119 106 86 85 84 bytes
One byte saved thanks to Sp3000.
->i{?{+"yodhis".chars.map{|w|s=0;i.scan(/-?\d+(?= *m?#{w})/){|n|s+=n.to_i};s}*?|+?}}

This is an unnamed function, which takes the input as a string, and returns the result (also as a string). You can test it by assigning it to f, say, and calling it like
f["3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds"]

JavaScript 100 105 112
Edit Adding template strings (first implemented dec 2014, so valid for this challenge) - at time I was not aware of them
Edit Eureka, at last I got the meaning of m? in all the other answers!
s=>s.replace(/(-?\d+) *m?(.)/g,(a,b,c)=>o['yodhis'.search(c)]-=-b,o=[0,0,0,0,0,0])&&`{${o.join`|`}}`

Test

F=
s=>s.replace(/(-?\d+) *m?(.)/g,(a,b,c)=>o['yodhis'.search(c)]-=-b,o=[0,0,0,0,0,0])&&`{${o.join`|`}}`

;['1 year 2 months 3 seconds','-2 day 5 year 8months'
,'3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds']
.forEach(i=>console.log(i,F(i)))

R, 197 bytes
I realize this isn't a competitive entry at all, I mostly just wanted to come up with a solution in R. Any help shortening this is of course welcome.
function(x){s="{";for(c in strsplit("yodhis","")[[1]])s=paste0(s,ifelse(c=="y","","|"),sum(as.numeric(gsub("[^0-9-]","",str_extract_all(x,perl(paste0("(-?\\d+) *m?",c)))[[1]]))));s=paste0(s,"}");s}

Like Martin's answer, this is an unnamed function. To call it, assign it to f and pass a string.
This is pretty hideous, so let's take a look at an un-golfed version.
function(x) {
    s <- "{"
    for (c in strsplit("yodhis", "")[[1]]) {
        matches <- str_extract_all(x, perl(paste0("(-?\\d+) *m?", c)))[[1]]
        nums <- gsub("[^0-9-]", "", matches)
        y <- sum(as.numeric(nums))
        s <- paste0(s, ifelse(c == "y", "", "|"), y)
    }
    s <- paste0(s, "}")
    return(s)
}

Based on the structure alone it's easy to see what's going on, even if you aren't too familiar with R. I'll elaborate on some of the stranger looking aspects.
paste0() is how R combines strings with no separator.
The str_extract_all() function comes from Hadley Wickham's stringr package. R's handling of regular expressions in the base package leaves much to be desired, which is where stringr comes in. This function returns a list of regular expression matches in the input string. Notice how the regex is surrounded in a function perl()--this is just saying that the regex is Perl-style, not R-style.
gsub() does a find-and-replace using a regex for each element of the input vector. Here we're telling it to replace everything that isn't a number or minus sign with an empty string.
And there you have it. Further explanation will be gladly provided upon request.

I don’t think outsourcing string extraction to an external package is a good idea. Isn’t it a loophole when an external community-supported library is used? Even if it is OK, why did you not include library(stringr) in your source?

Cobra - 165
def f(s='')
    l=int[](6)
    for i in 6,for n in RegularExpressions.Regex.matches(s,'(-?\\d+) *m?['yodhis'[i]]'),l[i]+=int.parse('[n.groups[1]]')
    print'{[l.join('|')]}'

C++14, 234 229 bytes
Edit: cut down 5 bytes by using old style declaration instead of auto.
I know the winner has already been chosen, and that this would be the longest submission so far, but I just had to post a C++ solution, because I bet nobody expected one at all :)
To be honest, I'm pretty much happy with how short it turned out to be (by C++ measurements, of course), and I'm sure it can't get any shorter that this (with just one remark, see below). It is also quite a nice collection of features new to C++11/14.
No third-party libraries here, only standard library is used.
The solution is in a form of lambda function:
[](auto&s){sregex_iterator e;auto r="{"s;for(auto&t:{"y","mo","d","h","mi","s"}){int a=0;regex g("-?\\d+ *"s+t);decltype(e)i(begin(s),end(s),g);for_each(i,e,[&](auto&b){a+=stoi(b.str());});r+=to_string(a)+"|";}r.back()='}';s=r;};

Ungolfed:
[](auto&s)
{
    sregex_iterator e;
    auto r="{"s;
    for(auto&t:{"y","mo","d","h","mi","s"})
    {
        int a=0;
        regex g("-?\\d+\\s*"s+t);
        decltype(e)i(begin(s),end(s),g);
        for_each(i,e,[&](auto&b)
        {
            a+=stoi(b.str());
        });
        r+=to_string(a)+"|";
    }
    r.back()='}';
    s=r;
}

For some reason, I had to write
regex g("-?\\d+\\s*"s+t);
decltype(e)i(begin(s),end(s),g);

instead of just
decltype(e)i(begin(s),end(s),regex("-?\\d+\\s*"s+t));

because the iterator would only return one match if I pass in a temporary object. This doesn't seem right to me, so I wonder if there's a problem with GCC's regex implementation.
Full test file (compiled with GCC 4.9.2 with -std=c++14):
#include <iostream>
#include <string>
#include <regex>

using namespace std;

int main()
{
    string arr[] = {"1 year 2 months 3 seconds",
                    "-2 day 5 year 8months",
                    "3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds"};
    for_each(begin(arr), end(arr), [](auto&s){sregex_iterator e;auto r="{"s;for(auto&t:{"y","mo","d","h","mi","s"}){int a=0;auto g=regex("-?\\d+ *"s+t);decltype(e)i(begin(s),end(s),g);for_each(i,e,[&](auto&b){a+=stoi(b.str());});r+=to_string(a)+"|";}r.back()='}';s=r;});
    for(auto &s : arr) {cout << s << endl;}
}

Output:
{1|2|0|0|0|3}
{5|8|-2|0|0|0}
{17|0|3|0|-5|1}

PHP, 141 bytes
preg_match_all("#(.?\d+)\s*m?(.)#",$argv[1],$m);$r=[0,0,0,0,0,0];foreach($m[1]as$i=>$n)$r[strpos(yodhis,$m[2][$i])]+=$n;echo json_encode($r);

takes input from first command line argument; uses [,] for output instead of {|}. Run with -r.
breakdown
preg_match_all("#(.?\d+)\s*m?(.)#",$argv[1],$m);    # find intervals.
# (The initial dot will match the sign, the space before the number or a first digit.)
$r=[0,0,0,0,0,0];                   # init result
foreach($m[1]as$i=>$n)              # loop through matches
    $r[strpos(yodhis,$m[2][$i])]+=$n;   # map token to result index, increase value
echo json_encode($r);               # print result: "[1,2,3,4,5,6]"


text:
Factorize it! ...badly
A curious kid uses a program which can factorize a number or an expression into the following form: p1^e1 * p2^e2 * ... * pn^en . Exponents equal to 1 are omitted e.g. 360 = 2^3 * 3^2 * 5
The kid types this output into the program as new input but they don't understand the ^ sign so sometimes they skip one or more of those concatenating the corresponding prime-base and exponent. E.g. (360 =) 2^3 * 3^2 * 5 => 2^3 * 32 * 5 (= 1280)
Because of these mistakes she might get a different factorization which they can input again (with skipping 0 or more ^'s). They repeat the process until the factorization doesn't change anymore (maybe there are no more ^'s or they copied the output correctly).
You should write a program or function which given an integer n (n>1) outputs all the possible numbers in increasing order whose factorization could be the one the kid ended up with (including n). E.g. for input 16 the possible final factorizations are (16 =) 2^4, (24 =) 2^3 * 3, (23*3 =) 3 * 23
Input details:

input is a single integer bigger than 1
no input will be given which generates output number greater than 2^31-1
no input will be given which generates more than 1000 output numbers

Output details:

a list of integers in a convenient form for your language

Examples:
Input => Output
11    => 11
16    => 16 24 69
360   => 140 360 770 1035 1219 1280 2875 3680
605   => 560 605 840 2415
2048  => 211 2048
58564 => 230 456 1311 2508 9975 12768 13794 20748 58564 114114 322102

This is code-golf so shortest program wins.

Don't we already have Factorize It ?

@Optimizer This is quite different.

The last number for 360 should be 3680: 2^33^25 => 23325 = 3680

@blutorange Thanks, edited.

CJam - 66
ria{_{:XmF{1=1>},La\{a1$\f++}/La-{XI{~#}%:*/I{si}%:**}fI}%|}1e3*$p

Try it at http://cjam.aditsu.net/
Explanation:
ria                       read token, convert to integer and wrap in array
{…}1e3*                   repeat 1000 times
    _                     duplicate array
    {…}%                  transform each array item (number) using the block
        :X                store the number in X
        mF                factorize with exponents
        {1=1>},           keep only the factors with exponent > 1
        La\{a1$\f++}/     get all the subsets (*)
        La-               remove the empty subset
        {…}fI             for I = each subset of prime factors with exponent > 1
            XI{~#}%:*/    divide X by all the factors in I
            I{si}%:**     multiply with the primes from I
                          concatenated with their exponents
    |                     add the new numbers to the array, removing duplicates
$                         sort
p                         print the final array

(*) Thanks Martin

cjam code from the cjam god

Any amount of ^'s could be removed in one step. So for 58564 = 2^2 * 11^4 it should be able to generate 2508 = 22 * 114.

@randomra you should add an example for this kind of thing

@randomra should be better now

Great! Added the example. Sorry for skipping it.

Ruby, 219
To get this started:
s=->(x){A=[];def k(x)A<<x
y=Prime.prime_division x;n=0..y.size-1
n.each{|i|n.to_a.combination(i+1).each{|c|c.each{|z|v=y.dup
v[z][1]>1?v[z]=[v[z].join.to_i,1]:next
k v.inject(1){|s,b|s*b[0]**b[1]}}}}end;k x;A.uniq.sort}

Creates a function s returning an Array of numbers.
https://ideone.com/iOMGny
Use it like this:
#usage

#load from the standard library
require"prime"

#read from stdin and print to stdout
p s.call $<.read.to_i

So much fun writing this all of this on a mobile phone...

Pyth, 46 45 44
Su{smmu*/N^T/PdTv+`T`/PdTkdyft/PdT{PdGU^T3]Q

Try it here.
Fixed the multiple ^ bug. For instance:
Input:  58564
Output: [230, 456, 1311, 2508, 9975, 12768, 13794, 20748, 58564, 114114, 322102]

Note that this code relies on a couple of bugfixes to the official compiler that were pushed after the question was asked. However, it does not use any new language features.

What do you get for 58564?

[230, 456, 1311, 58564, 322102], which is wrong.

@aditsu Fixed the issue.

As Pyth isn't rigorously documented (based on my findings) it is difficult to distinguish between bug fixes and new features so I decided not to choose this entry as the winning answer.

@randomra I understand your decision not to accept this answer. However, I'd just like to mention what the bugfix was: Using a reduce (u) inside another reduce was impossible. I changed a 2 to a 3 in the appropriate location so that reduce would take 3 inputs instead of 2. That's all.

Perl, 193 bytes
sub R{my($k,$v,@z)=@_;map{$k**$v*$_,$v>1?($k.$v)*$_:()}@z?R(@z):1}
@q=(0+<>);
while($x=pop@q){
my%f;@r=sort{$a<=>$b}@r,$x;
for(2..$x){$x/=$_,$f{$_}++while$x%$_<1}
$_~~@r||push@q,$_ for R%f
}
print"@r"

Newlines are just added for readability.
The for loop factorises the next number ($x) into a hash (%f) of primes and powers. The recursive function (R) uses this hash to generate all the numbers that could be attained by removing ^ signs. These numbers are added to a queue (@q), and the process is repeated by the outer while loop. Each number from the queue is also kept in a unique, sorted array (@r) for printing.

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