text:
Longest common substring in linear time
This challenge is about writing code to solve the following problem.
Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties.

The substring of A should also match some substring of B.
There should be no longer substring of A that satisfies the first property.

For example:
A = xxxappleyyyyyyy

B = zapplezzz

The substring apple with indices 4 8 (indexing from 1) would be a valid output.
Functionality
You can assume the input will be on standard in or in a file in the local directory, that is your choice. The file format will simply be two strings, separated by a new line. The answer should be a full program and not just a function.
I would eventually like to test your code on two substrings taken from the strings in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .
Score
This is code-golf with a twist. Your code must be run in O(n) time, where n is the total length of the input.
Languages and libraries
You can use any language which has a freely available compiler/interpreter/etc. for Linux. You should only use standard open source libraries not designed to solve this task. In case of dispute, I will count this as any library which either comes as standard with your language or one that you can install in a default ubuntu machine from a default repository.
Useful information
There are at least two ways to solve this problem in linear time. One is to first compute the suffix tree and the second is to first compute the suffix array and the LCP array.

Here is a full and (perhaps over-)detailed explanation of linear time suffix tree construction (it turns out some of the figures are messed up unfortunately). There is also a very nice SO answer about linear time suffix tree construction at https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english .  It includes a link to source code too.  Another detailed explanation can be found here, this time giving a full solution in C.
Section 2 of http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf gives a linear time suffix array construction algorithm and Appendix A has C++ source code.  This answer tells you how then to compute the longest common substring https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays .  Section 5 of https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf which also has an associated video lecture https://courses.csail.mit.edu/6.851/spring12/lectures/L16.html also explains the same algorithm starting at 1:16:00.

O(n) time
Are you sure it is possible?

@Capture_A_Lag Yes!  I know you can do it via a suffix tree or suffix array and maybe other ways too.

@Lembik Sorry, but these are very complex algorithms and it's not really fun to golve 100+ lines of code.

@FUZxxl I have updated the question with links to clear explanations with examples and useful source code. I hope that helps!

Not worth attempting. If you weren't worried about O(n) and planning to use huge strings to test, maybe then it would.

@mbomb007 I wasn't planning on testing with huge strings! I just meant the strings will be substrings of the huge strings I linked to. This was to provide example input to be helpful.

Still, O(n) is pretty discouraging.

@mbomb007 Surely not for 007 :) Would you be happy with n log n instead?  I have tried to add lots of detail for the algorithms but can add more if that would help.

The article at the second link you provide under "Useful information" says that "constructing [a suffix tree] requires O(N^2) time"

@KSFT This part sets out the time and space complexity .... "In fact, the reduction in the number of nodes is such that the time and space requirements for constructing a suffix tree are reduced from O(N2) to O(N). "

Wow...I cannot understand any of those explanations.

@KSFT The suffix tree ones or the suffix array ones? I can try to help if there is a particular point you are stuck on.

I'm pretty close to a Java solution that works without any of the suffix tree brain surgery. I have been running tests simple strings and sentences. The time complexity of the solution is bounded well below O(n^2) but space complexity is high due to String objects and data structures required. I need to know these details before posting the solution: 1. Are you open to a Java solution?
2. If so, what is your machine config and JVM heap size?

Java is fine. I have a standard ubuntu set up with 8GB  of RAM.

@Azee See Lembik's reply (you may not have got a notification because your answer was converted to a comment.)

The first example file seems to have a lot of mistakes. It's difficult to separate my misinterpretation of the algorithm from the mistakes in the document... For example, Figure 6.1 has 3 misplaced $.  Figure 6.2 has two extra $ and incorrect labelling of the top edge. Figure 6.4 is missing the final b on edge 2... and that's all the farther I've gotten so far.

@mellamokb Oh yes... Gusfield is a world expert but apparently not at drawing figures!

@Agawa001 I am not sure 100% sure what you mean. Say you have two strings of length 10^6 each. What is the longest your idea could possibly take?

I have just about completed a C# implementation (not golfed) that implements the suffix tree.  Still working out all the little bugs, which are fairly difficult to track down...  I'm still not quite grasping how to convert the suffix tree code into a code that finds longest common substring.

I'm not smart enough to write an O(n), but I did like the idea so wrote up a working solution. var a = "xxxappleyyyyyyy";
var b = "zapplezzz";
(a,b)=>{
var len = Math.min(b.length,a.length);
while(len > 0){
for(var i1 = 0; i1 < a.length - len; i1++){
for(var i2 = 0; i2 < b.length - len; i2++){
var str1 = a.substring(i1,i1+len);
var str2 = b.substring(i2,i2+len);
if(str1 === str2){
return {Index1: i1+1, Index2: i1 + len, String: str1};
}
}
}
len--
}
}

@Lembik You should just make the question [fastest-code], where the program with the best worst-case in big-oh notation wins. Then you'll at least get some answers, and in the even that someone can solve it in O(n), they'll win.

@mbomb007 It's a good idea. Not sure how to supply the test input though.

Done a simple program for the answer, but its O(N^2).

What alphabet will the input strings be drawn from? [a-z]? [a-zA-Z]? [a-zA-Z0-9]?

@Gareth [a-z] is ok.

This must be the question with the most deleted answers per valid answer...

@FlipTack: Agreed. I've protected it because it's attracting people who think "I can solve that" without reading the question, and my experience is that such questions tend end up needing protection eventually (additionally, the protection banner is, here, a clue that the question has obvious wrong answers).

Isn't this always worst case O(nlog(n))? I mean, judging by the amount of attention obviously not, but can someone explain to me why? I've read the full wiki page on suffix trees and it only solidified my confusion on the worst case performance of suffix trees being O(n)...

Python 2, 646 bytes
G=range;w=raw_input;z=L,m,h=[0]*3
s=w();t=len(s);s+='!%s#'%w();u=len(s);I=z*u
def f(s,n):
 def r(o):
	b=[[]for _ in s];c=[]
	for x in B[:N]:b[s[x+o]]+=x,
	map(c.extend,b);B[:N]=c
 M=N=n--~n/3;t=n%3%2;B=G(n+t);del B[::3];r(2);u=m=p=r(1)>r(0);N-=n/3
 for x in B*1:v=s[x:x+3];m+=u<v;u=v;B[x/3+x%3/2*N]=m
 A=1/M*z or f(B+z,M)+z;B=[x*3for x in A if x<N];J=I[r(0):n];C=G(n)
 for k in C:b=A[t]/N;a=i,j=A[t]%N*3-~b,B[p];q=p<N<(s[i:i-~b],J[i/3+b+N-b*N])>(s[j+t/M:j-~b],J[j/3+b*N]);C[k]=x=a[q];I[x]=k;p+=q;t+=1-q
 return C
S=f(map(ord,s)+z*40,u)
for i in G(u):
 h-=h>0;j=S[I[i]-1]
 while s[i+h]==s[j+h]:h+=1
 if(i<t)==(t<j)<=h>m:m=h;L=min(i,j)
print-~L,L+m

Try it online
This uses the skew algorithm described in "Simple Linear Work Suffix Array Construction" by Kärkkäinen and Sanders. The C++ implementation included in that paper already feels a little "golfy", but there is still plenty of room for making it shorter. For example, we can recurse until arriving at an array of length one, instead of short circuiting as in the paper, without violating the O(n) requirement.
For the LCP part, I followed "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications" by Kasai et al.
The program outputs 1 0 if the longest common substring is empty.
Here is some development code that includes an earlier version of the program that follows the C++ implementation a bit more closely, some slower approaches for comparison, and a simple test case generator:
from random import *

def brute(a,b):
    L=R=m=0

    for i in range(len(a)):
        for j in range(i+m+1,len(a)+1):
            if a[i:j] in b:
                m=j-i
                L,R=i,j

    return L+1,R

def suffix_array_slow(s):
    S=[]
    for i in range(len(s)):
        S+=[(s[i:],i)]
    S.sort()
    return [x[1] for x in S]

def slow1(a,b):
    # slow suffix array, slow lcp

    s=a+'!'+b
    S=suffix_array_slow(s)

    L=R=m=0

    for i in range(1,len(S)):
        x=S[i-1]
        y=S[i]
        p=s[x:]+'#'
        q=s[y:]+'$'
        h=0
        while p[h]==q[h]:
            h+=1
        if h>m and len(a)==sorted([x,y,len(a)])[1]:
            m=h
            L=min(x,y)
            R=L+h

    return L+1,R

def verify(a,b,L,R):
    if L<1 or R>len(a) or a[L-1:R] not in b:
        return 0
    LL,RR=brute(a,b)
    return R-L==RR-LL

def rand_string():
    if randint(0,1):
        n=randint(0,8)
    else:
        n=randint(0,24)
    a='zyxwvutsrq'[:randint(1,10)]
    s=''
    for _ in range(n):
        s+=choice(a)
    return s

def stress_test(f):
    numtrials=2000
    for trial in range(numtrials):
        a=rand_string()
        b=rand_string()
        L,R=f(a,b)
        if not verify(a,b,L,R):
            LL,RR=brute(a,b)
            print 'failed on',(a,b)
            print 'expected:',LL,RR
            print 'actual:',L,R
            return
    print 'ok'

def slow2(a,b):
    # slow suffix array, linear lcp

    s=a+'!'+b+'#'
    S=suffix_array_slow(s)

    I=S*1
    for i in range(len(S)):
        I[S[i]]=i

    L=R=m=h=0

    for i in range(len(S)):
        if I[i]:
            j=S[I[i]-1]
            while s[i+h]==s[j+h]:
                h+=1
            if h>m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h>0

    return L+1,R

def suffix_array(s,K):
    # skew algorithm

    n=len(s)
    s+=[0]*3
    n0=(n+2)/3
    n1=(n+1)/3
    n2=n/3
    n02=n0+n2
    adj=n0-n1

    def radix_pass(a,o,n=n02):
        c=[0]*(K+3)
        for x in a[:n]:
            c[s[x+o]+1]+=1
        for i in range(K+3):
            c[i]+=c[i-1]
        for x in a[:n]:
            j=s[x+o]
            a[c[j]]=x
            c[j]+=1

    A=[x for x in range(n+adj) if x%3]+[0]*3

    radix_pass(A,2)
    radix_pass(A,1)
    radix_pass(A,0)

    B=[0]*n02
    t=m=0

    for x in A[:n02]:
        u=s[x:x+3]
        m+=t<u
        t=u
        B[x/3+x%3/2*n0]=m

    A[:n02]=1/n02*[0]or suffix_array(B,m)
    I=A*1
    for i in range(n02):
        I[A[i]]=i+1

    B=[3*x for x in A if x<n0]
    radix_pass(B,0,n0)

    R=[]

    p=0
    t=adj
    while t<n02:
        x=A[t]
        b=x>=n0
        i=(x-b*n0)*3-~b
        j=B[p]
        if p==n0 or ((s[i:i+2],I[A[t]-n0+1])<(s[j:j+2],I[j/3+n0]) if b else (s[i],I[A[t]+n0])<(s[j],I[j/3])):R+=i,;t+=1
        else:R+=j,;p+=1

    return R+B[p:n0]

def solve(a,b):
    # linear

    s=a+'!'+b+'#'
    S=suffix_array(map(ord,s),128)

    I=S*1
    for i in range(len(S)):
        I[S[i]]=i

    L=R=m=h=0

    for i in range(len(S)):
        if I[i]:
            j=S[I[i]-1]
            while s[i+h]==s[j+h]:
                h+=1
            if h>m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h>0

    return L+1,R

stress_test(solve)

This looks very promising!

Correct me if I'm wrong, but isn't this actually 739 bytes? I copied into https://mothereff.in/byte-counter and deleted 2 spaces from lines 6-9, but I'm not sure if that's correct.

@PatrickRoberts Those are tabs.

Nice answer! You might want to have a look at GSACA a novel linear time SACA from 2016. Reference implementation is 246 lines full of comments (170 without comments) and seems very golfable. You'll find it on github.

We clearly need a version in Jelly now :)

I think that 0--n/3 can be n/3.

@TuukkaX Out of curiosity, do you remember if you were experiencing any specific emotions when you wrote that comment? Or, what was the mindset?

@MitchSchwartz I'm currently trying to stay on noPMO, so I can't feel emotions strongly right now (probably due to inbalanced brain chemicals). At the time of reading the code quickly, my syntax golfing motor spotted that, and I don't remember feeling any specific emotions. Did you think of the same thing or why the question? :) Now I'm curious.

@TuukkaX That's an interesting response that I wasn't expecting. Well, I'm not sure if I should be phrasing this in some special way, but the fact that your original comment wasn't actually correct played some part in why I decided to ask. :)

what is w and what to input in the python2 solution?
why still using python2 as it outdates now?

oh - understood ... you replaced "raw_input" by "w" ... then it is clear.
this is not clever:

whenever i "enter" a line i close and save the comment, but did not want to ....
as i was not able to put my question into comments, i wrote it here as "aswer", for which i don't need any stupid whatsoever points, but ...
as i now answered my question myself it is useless to be placed here. ... No way to delete it .... sorry for inconvenience

@Ing.JosefKlotzner Python 2 is shorter than Python 3. We don't care about being up-to-date here, we care about better scores. For this question ([tag:code-golf]), a shorter answer is better. Python 2 scores better much of the time. Also, newlines are not possible in comments.

I've edited in a TIO link and replaced the spaces with tabs so that the byte count is correct :)


text:
Word search puzzle generation
Given a list of strings, find the smallest square matrix that contains each of the initial strings. The strings may appear horizontally, vertically or diagonally and  forwards or backwards like in this question Word Search Puzzle.
Words should be placed in the square, with at least one word in each direction (horizontal, vertical and diagonal). Words should appear just one time.
So, the input is just a list of words. For example: CAT, TRAIN, CUBE, BICYCLE. One possible solution is:
B N * * * * *
* I * * C A T
* A C * * * *
* R * Y * * C
* T * * C * U
* * * * * L B
* * * * * * E

I replaced filling letters with asterisks just for clarity. The desired output should include random filling letters.

Must each word be found in only one position (like typical word searches)? For instance, the letter left of AC in your example would make another CAT if it's T.

It's not clear to me what exactly you mean by "Words should be placed randomly in all directions". Would an answer meet this criterion if, having laid the words out deterministically, it randomly selects one of the eight symmetries of the square? Or, at the other extreme, should the output be selected uniformly from all the possible smallest squares which contain the words? Or is the line drawn somewhere in between those extremes?

Yes, it should be found only in one position.

@PeterTaylor, I edited the question. I hope it's clear now.

Not really, no. I'm still not clear what the space from which an answer should randomly sample is, nor how much flexibility is allowed in weighting the elements of that space.

Why 3 reopen votes? This is still totally underspecified.

@PeterTaylor, I chose to remove the random part from the question, so one just have to place the words in any way and get the smallest possible matrix just with the constraints of directions and repetition.

Can one word appear totally within another? You mention random filling letters -- do they have to avoid accidentally repeating the words?

@xnor Yes, words could appear totally or partially within another because it doesn't contradict the rules. And yes, random filling letters should avoid accidentally repeat the words.

As of now, the question has inputs that can not be solved, but no mention is made of how you're supposed to deal with that. For example the set A B C D E F G H I J K L M N O P Q R S T U V W X Y Z has no solution.

letter sharing makes it quite difficult...

Is this supposed to be codegolf? The accepted answer hasn't been golfed at all

JavaScript (ES6), 595 628 680
Edit Some cleanup and merge:
- function P merged inside function R
- calc x and z in the same .map
- when solution found, set x to 0 to exit outer loop
- merged definiton and call of W
Edit2 more golfing, random fill shortened, outer loop revised ... see history for something more readable
Unlike the accepted answer, this should work for most inputs. Just avoid single letter words. If an output is found, it's optimal and using all 3 directions.
The constraint of avoiding repeating words is very hard.
I had to look for repeating word at each step adding word to the grid, and at each random fill character.
Main subfunctions:

P(w) true if palindrome word. A palindrom word will be found twice when checking for repeated words.
R(s) check repeating words on grid s
Q(s) fill the grid s with random characters - it's recursive and backtrack in case of repeating word - and can fail.
W() recursive, try to fill a grid of given size, if possibile.

The main function use W() to find an output grid, trying from a size of the longest word in input up to the sum of the length of all words.
F=l=>{
  for(z=Math.max(...l.map(w=>(w=w.length,x+=w,w),x=0));
      ++z<=x;
      (W=(k,s,m,w=l[k])=>w?s.some((a,p)=>!!a&&
            D.some((d,j,_,r=[...s],q=p-d)=>
              [...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
              &&R(r)&&W(k+1,r,m|1<<(j/2))
            )
          )
        :m>12&&Q(s)&&(console.log(''+s),z=x)
      )(0,[...Array(z*z-z)+99].map((c,i)=>i%z?1:'\n'))
    )
    D=[~z,-~z,1-z,z-1,z,-z,1,-1]
    ,R=u=>!l.some(w=>u.map((a,p)=>a==w[0]&&D.map(d=>n+=[...w].every(c=>u[q+=d]==c,q=p-d)),
      n=~([...w]+''==[...w].reverse()))&&n>0)
    ,Q=(u,p=u.indexOf(1),r=[...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'])=>
      ~p?r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1):1
    //,Q=u=>u.map((c,i,u)=>u[i]=c!=1?c:' ') // uncomment to avoid random fill
}

Ungolfed and explained (incomplete, sorry guys it's a lot of work)
F=l=>
{
  var x, z, s, q, D, R, Q, W;
  // length of longest word in z
  z = Math.max( ... l.map(w => w.length))
  // sum of all words length in x
  x = 0;
  l.forEach(w => x += w.length);

  for(; ++z <= x; ) // test square size from z to x
  {
    // grid in s[], each row of len z + 1 newline as separator, plus leading and trailing newline
    // given z==offset between rows, total length of s is z*(z-1)+1
    // gridsize: 2, z:3, s.length: 7
    // gridsize: 3, z:4, s.length: 13
    // ...
    // All empty, nonseparator cells, filled with 1, so
    // - valid cells have a truthy value (1 or string)
    // - invalid cells have falsy value ('\n' or undefined)
    s = Array(z*z-z+1).fill(1)
    s = s.map((v,i) => i % z != 0 ? 1 : '\n');

    // offset for 8 directions
    D = [z+1, -z-1, 1-z, z-1, z, -z, 1, -1]; // 4 diags, then 2 vertical, then 2 horizontal

    // Function to check repeating words
    R = u => // return true if no repetition
      ! l.some( w => // for each word (exit early when true)
      {
          n = -1 -([...w]+''==[...w].reverse()); // counter starts at -1 or -2 if palindrome word
          u.forEach( (a, p) => // for each cell if grid
          {
            if (a == [0]) // do check if cell == first letter of word, else next word
               D.forEach( d => // check all directions
                 n += // word counter
                   [...w].every( c => // for each char in word, exit early if not equal
                     u[q += d] == c, // if word char == cell, continue to next cell using current offset
                     q = p-d  // starting position for cell
                   )
               ) // end for each direction
          } ) // end for each cell
          return n > 0 // if n>0 the word was found more than once
      } ) // end for each word

    // Recursive function to fill empty space with random chars
    // each call add a single char
    Q =
    ( u,
      p = u.indexOf(1), // position of first remaining empty cell
      r = [...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'] // char array to be random shuffled
    ) => {
      if (~p) // proceed if p >= 0
        return r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1)
      else
        return 1; // when p < 0, no more empty cells, return 1 as true
    }
    // Main working function, recursive fill of grid
    W =
    ( k, // current word position in list
      s, // grid
      m, // bitmask with all directions used so far (8 H, 4V, 2 or 1 diag)
      w = l[k] // get current word
    ) => {
      var res = false
      if (w) { // if current word exists
        res = s.some((a,p)=>!!a&&
            D.some((d,j,_,r=[...s],q=p-d)=>
              [...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
              &&R(r)&&W(k+1,r,m|1<<(j/2))
            )
          )
      }
      else
      { // word list completed, check additional constraints
        if (m > 12 // m == 13, 14 or 15, means all directions used
            && Q(s) ) // try to fill with random, proceed if ok
        { // solution found !!
          console.log(''+s) // output grid
          z = x // z = x to stop outer loop
          res = x//return value non zero to stop recursion
        }
      }
      return res
    };
    W(0,s)
  }
}

Test in Firefox/FireBug console
F(['TRAIN', 'CUBE','BOX','BICYCLE'])
,T,C,B,O,X,B,H,
,H,R,U,H,L,I,H,
,Y,A,A,B,E,C,B,
,D,H,S,I,E,Y,I,
,H,E,R,L,N,C,T,
,G,S,T,Y,F,L,U,
,H,U,Y,F,O,E,H,

not filled
,T,C,B,O,X,B, ,
, ,R,U, , ,I, ,
, , ,A,B, ,C, ,
, , , ,I,E,Y, ,
, , , , ,N,C, ,
, , , , , ,L, ,
, , , , , ,E, ,

F(['TRAIN','ARTS','RAT', 'CUBE','BOX','BICYCLE','STORM','BRAIN','DEPTH','MOUTH','SLAB'])
,T,A,R,C,S,T,H,
,S,R,R,L,U,D,T,
,T,B,A,T,N,B,P,
,O,B,O,I,S,A,E,
,R,B,A,X,N,H,D,
,M,R,M,O,U,T,H,
,B,I,C,Y,C,L,E,

F(['AA','AB','AC','AD','AE','AF','AG'])
,A,U,B,C,
,T,A,E,Z,
,C,D,O,F,
,Q,C,G,A,

F(['AA','AB','AC','AD','AE','AF'])
output not filled - @nathan: now you can't add another Ax without repetitions. You'll need a bigger grid.
,A, ,C,
, ,A,F,
,D,E,B,

On your last test case, isn't it possible in a 3x3 grid?

@NathanMerrill no. More detail in the answer text

totally unreadable code :) but nice that is the downside of byte/point "award" don't be a human compiler

@firephil trying to add an explanation, it's not easy ...

C#
Here's a simple implementation with still work to be done.
There are very many combinations to get smallest size.
So just used simplest algorithm in could think of.
class Tile
{
    public char C;
    public int X, Y;
}

class Grid
{
    List<Tile> tiles;

    public Grid()
    {
        tiles = new List<Tile>();
    }
    public int MaxX()
    {
        return tiles.Max(x => x.X);
    }
    public int MaxY()
    {
        return tiles.Max(x => x.Y);
    }
    public void AddWords(List<string> list)
    {
        int n = list.Count;
        for (int i = 0; i < n; i++)
        {
            string s = list[i];
            if(i==0)
            {
                Vert(s, 0, 0);
            }
            else if(i==n-1)
            {
                int my = MaxY();
                Diag(s, 0, my+1);
            }
            else
            {
                Horiz(s, 0, i);
            }
        }

    }
    private void Vert(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x+i;
            t.Y = y;
            tiles.Add(t);
        }
    }
    private void Horiz(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x+i;
            t.Y = y;
            tiles.Add(t);
        }
    }
    private void Diag(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x++;
            t.Y = y++;
            tiles.Add(t);
        }
    }
    public void Print()
    {
        int mx = this.MaxX();
        int my = this.MaxY();
        int S = Math.Max(mx, my) + 1;
        char[,] grid = new char[S, S];
        Random r = new Random(DateTime.Now.Millisecond);
        //fill random chars
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                grid[i, j] = (char)(r.Next() % 26 + 'A');
            }
        }
        //fill words
        tiles.ForEach(t => grid[t.X, t.Y] = t.C);
        //print
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                Console.Write("{0} ", grid[i,j]);
            }
            Console.WriteLine();
        }
    }
}

class WordSearch
{
    public static void Generate(List<string>list)
    {
        list.Sort((x, y) =>
        { int s = 0; if (x.Length < y.Length)s = -1; else if (y.Length < x.Length)s = 1; return s; });
        list.Reverse();
        Grid g = new Grid();
        g.AddWords(list);
        g.Print();
    }

}

Test
class Program
{
    static void Main(string[] args)
    {
        string words = "CAT, TRAIN, CUBE, BICYCLE";
        string comma=",";
        List<string> w = words.Split(comma.ToArray()).ToList();
        List<string> t = new List<string>();
        foreach(string s in w)
        {
           t.Add(s.Trim());
        }
        WordSearch.Generate(t);

        Console.ReadKey();
    }
}

it works but its not optimal : sample string words = "CAT,DOG,HR,RUN,CMD";

Do you check if the random fill characters cause the repetition of a word in the grid?

-1 Tried it. Does not follow the specs at least one word in each direction (horizontal, vertical and diagonal). Running the test program, no horizontal word (3 vertical, 1 diag)

This question is code-golf, so you should post how many bytes in the title, and probably shorten your program a bunch. Thanks.

@edc65 It does one vertical,  one diagonal and all others horizontal. As I commented to get perfect solution will require enormous number of combinations to check as well as the specifications of the question.

Did you tried your own test code? Vertical: TRAIN, CUBE, BICYCLE. Diagonal: CAT. Horizontal: none.

source: Stack Exchange

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

sort: votes


text:
ASCII Ice Cream
Write a program or function that takes in a positive integer N, and prints or returns an N×N ASCII art string whose top half is a semicircle made of ('s and whose bottom half is a downward-pointing triangle made of V's, with spaces used as padding.
In other words, make an ASCII ice cream cone: (output for N = 17)
      (((((
    (((((((((
  (((((((((((((
  (((((((((((((
 (((((((((((((((
 (((((((((((((((
(((((((((((((((((
(((((((((((((((((
VVVVVVVVVVVVVVVVV
 VVVVVVVVVVVVVVV
  VVVVVVVVVVVVV
   VVVVVVVVVVV
    VVVVVVVVV
     VVVVVVV
      VVVVV
       VVV
        V

Examples
Here are the outputs for N = 1 to 5. Note that for odd N, the triangle always must be the larger half.
V

((
VV

(((
VVV
 V

 ((
((((
VVVV
 VV

 (((
(((((
VVVVV
 VVV
  V

Here's an N = 101 pastebin.
And here's an ungolfed Python 3 reference implementation:
N = int(input())
ic = [[' '] * N for _ in range(N)]
for y in range(N//2):
    for x in range(N):
        if (x - (N - 1) / 2)**2 + (y - (N - 1) / 2)**2 < (N / 2)**2:
            ic[y][x] = '('
for y in range(N//2, N):
    for x in range(y - N//2, N - (y - N//2)):
        ic[y][x] = 'V'
for line in ic:
    print(''.join(line))

Details

Take input from stdin, command line, or as function argument. Output to stdout or similar, or you may return the string if you write a function.
The cone portion should exactly match the reference implementation for all N.
The ice cream portion does not need to exactly match the reference implementation as long as it is clearly in the shape of a semicircle for all N. (This is so you don't have to worry about slight differences in the semicircle due to roundoff errors.)
There should not be any unnecessary leading spaces but there may be superfluous trailing spaces.
The output may optionally contain a trailing newline.
You may optionally use any 3 other distinct printable ASCII characters in place of (, V, and space.

Scoring
The shortest submission in bytes wins. Tiebreaker goes to the oldest submission.

Am I the only one who thought "IceCII ASCream" when I read the title?

@Sp3000 Jeez, I hope so...

CJam, 46 bytes
Try it online.
{:Z{Z{Z(2./:R-zYR<):P#YR-zP#+Z2./P#>SP?}/N}fY}

I believe this currently mimics the original specification exactly, which was required when I started producing this answer. There may be potential to save a few bytes by making the math less accurate to the original specification, but until I see a way to save more than one or two bytes doing so, I'll leave it as-is.
Explanation
{               "Begin block";
  :Z{             "For each y from 0 to input-1";
    Z{              "For each x from 0 to input-1";
      Z(2./:R         "Calculate the radius as (input-1)/2.0";
      -z              "Calculate the horizontal distance from the center";
      YR<):P          "Calculate the power to raise distances to: (y<radius)+1
                       (This results in Euclidean distance being calculated for
                        the ice cream and Manhattan distance being calculated
                        for the cone)";
      #               "Raise the horizontal distance to the determined power";
      YR-zP#          "Calculate the vertical distance from the center and
                       raise it to the determined power";
      +               "Add the horizontal and vertical distances";
      Z2./P#          "Calculate the solid distance threshold and raise it to
                       the determined power";
      >SP?            "If the solid threshold is exceeded, produce a space;
                       otherwise, produce the determined power digit
                       (This results in ice cream being represented by the
                        digit '2' and the cone by the digit '1')";
    }/              "End x loop";
    N               "Produce a new line";
  }fY             "End y loop";
}               "End block";

This appears to use 2's and 1's instead of ('s and V's ?

@MarkReed This is allowed. Last line in the details section.

inca2 129 123 121 111 107
This mostly uses the formulas from the python example, but using jot-dots and iotas instead of double-looping. The i function performs the circular test for the j function which invokes jot-dot upon it. And the k function performs the triangle test for the l function. The c function catenates the results of j and l and reshapes it to N×N.
edit: -6 combine 2 maps into 1.
edit: -2 remove useless ravels.
edit: nicer typescript.
edit: -10 apply repeated expression array-wise.
edit: -4 factor out repeated expression as a function.
edit: line-by-line commentary.
q:y-(n-1)%2
i:[((n%2)^2)>+/(qx y)^2
j:(~[y%2)i.(~y)
k:2*[x>[|qy
l:(@1+~]y%2)k.(~y)
c:y y#((jn<y),ly){' (V'

In more detail, the entry-point is the c function which takes one argument implicitly named y.
c:y y#((jn<y),ly){' (V'
         n<y            } assign y to 'n'
        jn<y            } call j(y)
              ly        } call l(y)
      ((    ),  )       } catenate the results
      (         ){' (V' } map 0 1 2 to ' ' '(' 'V'
  y y#                  } reshape to NxN

The j function receives the same input value as its y parameter.
j:(~[y%2)i.(~y)
     y%2         } y divided by 2
    [            } floor
   ~             } iota. this generates the row indices 0..y/2
            ~y   } iota y. this generates the column indices 0..y
  (     )i.(  )  } jot-dot with the function i

The jot-dot here does the double-loop. It calls the i function with every combination of elements from the left and right arrays (0..n/2 and 0..n). So the i function receives as x the y index of the table, and it receives as y the x index. The names got a little backwards here :).
i:[((n%2)^2)>+/(qx y)^2
     n%2                 } n divided by 2
    (n%2)^2              } squared
                 x y     } make a 2-element array (x,y)
                qx y     } call q on this array

where q does
q:y-(n-1)%2
     n-1    } n minus 1
         %2 } divided by 2
  y-        } y minus that

back to i
i:[((n%2)^2)>+/(qx y)^2
               (    )^2  } square the result from q(x,y)
             +/          } sum the two numbers
            >            } compare the left side (above) with the right (=> 0/1)
  [                      } floor

The floor should not be necessary. But apparently there's a bug in the interpreter.
The l function works similarly to the j function, using a jot-dot.
l:(@1+~]y%2)k.(~y)
        y%2         } y divided by 2
       ]            } ceiling
      ~             } iota 0..ceil(y/2)-1
    1+              } add 1 => 1..ceil(y/2)
   @                } reverse => ceil(y/2)..1
               ~y   } iota y  0..y-1
  (        )k.(  )  } jot-dot using k

The k function yields a boolean scaled by 2 so the values can be distinguished from the ice cream values later on, in the mapping.
k:2*[x>[|qy
     x       } k's left arg
         qy  } y-(n-1)%2
        |    } abs
       [     } floor
     x       } left-hand-side again
      >      } compare
    [        } floor (should be unnecessary)
  2*         } scale by 2

In action (piping through tr to remove tab chars which are the REPL's prompt):
josh@Z1 ~/inca
$ ./inca2 <icecream | tr -d '\t'

c1
V

c2
((
VV

c3
(((
VVV
 V

c4
 ((
((((
VVVV
 VV

c5
 (((
(((((
VVVVV
 VVV
  V

josh@Z1 ~/inca
$

Python 2, 193 192
Does not use strings, only math
N=input()
R=(N+1)/2;r=range(R)
s=lambda L,U:(10**U-10**L)/9
f=lambda N,m:s(0,N)+s(m,N-m)
g=lambda N,m:s(0,N)+s(m,N-m)*6
for i in r[1:]:print f(N,int(R-(2*R*i-i*i)**.5))
for i in r:print g(N,i)

s(L,U) returns a number of the form "U-digits with the rightmost L zeros and the rest ones"
f(N,m) returns an N-digit number with the inner section of 2 and an m-wide border of 1on each side
g(N,m) does the same, but using 7 for the 'colour' of the inner section since it matches the texture of the cone more closely
Output
N=8         N=9
11122111    112222211
12222221    122222221
22222222    222222222
22222222    222222222
77777777    777777777
17777771    177777771
11777711    117777711
11177111    111777111
            111171111

Very unique way to do it :)

If only we can see the ice cream too :P

Perl 6, 175
Pretty straightforward implementation without much golfing, just extraneous whitespace/punctuation elimination:
sub MAIN($d){my$r=($d/2).Int;for 1..$r ->$n
{my$y=$n-$r;my$h=sqrt($r*$r-$y*$y).Int;my$w=2*$h+$d%2;say
' 'x($r-$h)~'('x$w};for 1..($d-$r) ->$y {say ' 'x($y-1)~'V'x($d-2*$y+2)}}

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


text:
Construct a Ladder
Introduction
I want to build a ladder.
For this, I have scavenged from the junkyard two long boards with holes in them, and I want to place the steps into these holes.
However, the holes are not evenly placed, so the steps will be a little wonky, and I find it hard to estimate the amount of rod I need for them.
Your job is to do the calculations for me.
Input
Your input is two bit vectors, given as arrays of integers, which represent the two boards.
A 0 represents a segment of one aud (arbitrary unit of distance) without a hole, and a 1 represents a segment of one aud with a single hole.
The arrays may be of different lengths and contain a different number of 1s, but they will not be empty.
I will construct my ladder as follows.
First, I place the two boards exactly one aud apart, and align their left ends.
For each index i, I measure the distance between the ith hole of the first board with the ith hole of the second board, cut a piece of rod, and attach it between the two holes.
I stop once I run out of holes in one of the boards.
Output
Your output is the total amount of rod I'll need for the steps, measured in auds.
The output should be correct to at least six significant digits.
Example
Consider the inputs [0,1,1,0,1,1,1,1,0,0] and [1,0,0,1,1,1,0,0,1].
The resulting ladder looks like this:

The total length of the rod in this ladder is 7.06449510224598 auds.
Rules
You can write either a function or a full program.
The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
[0] [0] -> 0.0
[0] [1,0] -> 0.0
[1,0,0] [1,1,1,1,1] -> 1.0
[0,1,0,1] [1,0,0,1] -> 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] -> 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] -> 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] -> 20.38177416534678

For your own safety, I really don't recommend climbing any ladder that looks like that.

J, 20 bytes
4+/@:o.(<0 1)|:-/&I.

It uses the trick in MickyT's answer in R.
(<0 1)|: gives the diagonal of a matrix. For the explanations of the other parts, see FUZxxl's answer.

Neat. I admit defeat.

J, 22 characters
Not inspired by the answer of randomra. The I. part is equal as that is the immediately obvious way of finding the holes.
(4+/@:o.<.&#$-/@,:)&I.

I. y – all the indices of y repeated as often as the corresponding item of y. Incidentally, if y is a vector of booleans, I. y contains the indices at which y is 1. For instance, I. 1 0 0 1 1 1 0 0 1 yields 0 3 4 5 8.
x u&v y – the same as (v x) u (v y). Applied as x u&I. y, we get (I. x) u (I. y). Let's continue with the transformed input.
x <.&# y – the lesser of the lengths of x and y.
x -/@,: y – the difference of the items of x and y. If one vector is longer, it is padded with zeroes.
x $ y – y reshaped to the shape specified by x. Specifically, if x is a scalar, x elements are taken from y. In this usage, x (<.&# $ -/@,:) y makes sure that trailing holes are ignored.
4 o. y – the function %: 1 + *: y, that is, sqrt(1 + y²). Incidentally, this function maps from hole distance to length of rods.
+/ y – the sum of the elements of y.

Python, 85
lambda*A:sum(abs(x-y+1j)for x,y in zip(*[[i for i,x in enumerate(l)if x]for l in A]))

This turned out similar to Mac's solution. Convert the lists of 0's and 1's to ordered lists of the one-indices, and then sum the distance between respective elements.

Nicely done. Nice trick with the complex literal!

I'm a bit sad that this is one byte shorter than my other answer, which I think is a more creative solution.

J, 32 28 bytes
The verb I. returns the positions of 1s in a binary string which is a huge help.
   +/@,@(=/&(#\)*[:>:&.*:-/)&I.

   0 1 0 1 (+/@,@(=/&(#\)*[:>:&.*:-/)&I.) 1 0 0 1
2.41421

For a better J solution check FUZxxl's answer.

Haskell, 77 73 bytes
r x=[a|(a,1)<-zip[1..]x]
i#j=sum$zipWith(\n m->sqrt((n-m)**2+1))(r i)$r j

Usage: [0,1,0,1] # [1,0,0,1] which outputs 2.414213562373095
How it works: the function r returns a list of the positions of the holes of a board, e.g. r [0,1,0,1] -> [2,4]. # zips two of those lists and turns it into a list of distances between corresponding holes and finally sums it.

R, 67
Uses outer to do a difference for indexed holes.  Diag returns required differences.
Then sum the calculated distances
function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5)

Test run in R Fiddle.  I have wrapped it in a print to show the return complies with spec.
> print((function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5))(c(0,1,1,0,1,1,1,1,0,0),c(1,0,0,1,1,1,0,0,1)),digits=10)
[1] 7.064495102
> print((function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5))(c(1,1,1,1,1),c(0,0,1,1,0,1,0,0,1)),digits=10)
[1] 12.73343313
>

Nice one. a==1 can be a>0 or !!a.

CJam, 36 33 bytes
l~]{:L,{L=},}%z{,(},0\{~-_*)mq+}/

Very naive approach... it expects the input as CJam-style arrays on STDIN
[0 1 1 0 1 1 1 1 0 0] [1 0 0 1 1 1 0 0 1]

Here is a test harness for all the example inputs. The results in the input field are used before the actual code is called. You can remove them if you don't trust me. ;)
Explanation
l~]                               "Read and eval input, wrap in an array.";
   {        }%                    "Map this block onto both input arrays.";
    :L,                           "Store array in L, get its length N.";
       {L=},                      "In the range [0 .. N-1] get all elements where L is 1.";
                                  "At this point we've converted each array into a list of its
                                   non-zero indices.";
              z                   "Transpose the array, pairing up indices at the same position.";
               {,(},              "Filter the extraneous elements of the longer input.";
                    0\            "Put a 0 before the array.";
                      {        }/ "For each pair of holes...";
                       ~-         "Unwrap the pair, take the difference.";
                         _*)mq    "Square, increment, square root.";
                              +   "Add to the running total.";

Python, 105 102 100 bytes
i=lambda l:(i for i,h in enumerate(l)if h)
l=lambda*a:sum(((a-b)**2+1)**.5for a,b in zip(*map(i,a)))

Pretty basic, just converts the input lists to lists of hole indices, then computes distance between each pair of such indices.
Test case:
>>> print l([0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1])
7.06449510225

Credit to @FryAmTheEggman for a couple of byte-saving suggestions. Turns out this can be golfed further, as demonstrated in xnor's answer.

You can remove the spaces after enumerate(l) and the 0.5 (which could just be .5).

@FryAmTheEggman: absolutely right, thanks! Changed as suggested.

Found another thing using starred assignment: l=lambda*a:sum(((a-b)**2+1)**.5for a,b in zip(*map(i,a)))

@FryAmTheEggman: thanks again! Unfortunately it seems xnor's gone one better though - much the same, but with the first lambda rolled into the second as a list comprehension...

Python, 86
f=lambda a,b,i=1j:a>[]<b and a[0]*b[0]*abs(i)+f(a[a[:1]<=b:],b[b[:1]<=a:],i+a[0]-b[0])

A low-level and naive recursive solution without any list searching.
The input lists are a and b. If either is empty, return 0.
Otherwise, let x and y be their first elements (the code doesn't actually assign these because you can't do assignments in a lambda, but it will make explaining easier). If both are 1, i.e. their product is 1, then they contribute rod distance. We keep track of distance in the complex number i, so that distance is the absolute value. Actually, we compute it regardless, then multiply it by x*y.
Then, we recurse. The idea is to shift both lists one step, unless one list starts with a 0 and the other with a one, in which case we shift only the 0 list. That way, 1's are always consumed in pairs. We could check these conditions with x<y and y<x, but it's shorter to take advantage of list comparison as a[:1]<=b. Finally, we adjust the complex displacement between the current elements by x-y.

Since you're upset that this was 1 byte more than your other solution, I found a way to save a byte. Change a>[]<b to a>0<b. It works since both [] and 0 are falsy, so they're equivalent.

Also, what is a:?

@mbomb007. Did you do any testing? In python2: ([] > []) != ([] > 0), and in python3 it is an error (unorderable types).

@mbomb007. The a: is part of the slice [b[:1]<=a:].

Pyth, 30 bytes
s+0m^h^-hded2 .5CmfTm*hb@kblkQ

Try it online with the input [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].
Explanation:
I convert the lists into lists of indices [2, 3, 5, 6, 7, 8] and [1, 4, 5, 6, 9] and zip them together [(2,1), (3,4), (5,5), (6,6), (7,9)]. Then I subtract the values, square them, add 1 and sum over all square roots.
CmfTm*hb@kblkQ
 m           Q     map each list k in input() to the following list:
    m      lk         map each value b of [0, 1, 2, ..., len(k)-1] to the value:
     *hb@kb              (b + 1) * k[b]
  fT                  filter the list for positive values
C                  zip these two resulting lists

s+0m^h^-hded2 .5...
   m            ...  map each pair of values d to:
    ^h^-hded2 .5         ((d[0] - d[1])^2 + 1)^0.5
 +0                  insert 0 at the front of the list
s                    sum

Shame that sum doesn't work for empty lists.

Clip 3, 55 47 38
[cr+`j[v[w#)#mvw2B}}(c)c]sl`{%ky1%kx1`

For the list with the fewer holes, the program iterates through it, and connects each hole with the corresponding hole of the other list. The sizes are calculated and summed.
>java -jar Clip3.jar ladder.clip
{0,1,1,0,1,1,1,1,0,0}
{1,0,0,1,1,1,0,0,1}
7.064495102245980096000721459859050810337066650390625

Explanation
[c          .- Assign c to the lists, in order of size    -.
  r+`       .- The sum of...                              -.
   j[v[w    .- Join the lists with a function on v, w     -.
     #      .- Square root                                -.
      )     .- 1 plus                                     -.
       #    .- The square of                              -.
        mvw .- The distance between v and w               -.
       2
     B      .- (one-half, so #...B means square root)     -.
   }}(c)c   .- Apply joining function to the lists        -.
  ]sl`{     .- c is the (sorted by size) list of...       -.
    %ky1    .- Indices of y (the second input) which are 1-.
    %kx1    .- Indices of x (the first input) which are 1 -.
  `

If we are very liberal about the input format, we can reduce this to 36 bytes by removing each k. This requires the input to be a string of the control characters characters \0 and \1.

Python, 116 115 bytes
This is a recursive solution.
It became pretty annoying when I found that index() just throws an error when no value is found, but I made it work. Unfortunately, I cannot use a lambda. It also annoyed me that list.remove() doesn't return the list, but instead returns None.
def f(x,y,r=0):
    try:i,j=x.index(1),y.index(1)
    except:return r
    x.pop(i);y.pop(j);return f(x,y,r+((i-j)**2+1)**.5)

Run online here: http://repl.it/c5L/2

Even with tabs, that code is 116 bytes, not 112.

Ah, missed the newlines, thanks.

ECMAScript 6, 86 bytes
This originally started out using reduce (I wanted to see if it could be done in one loop as opposed to @edc65 answer).
f=(c,b,a=[0,...c],j)=>a.reduce((c,v,i)=>c+=v&&(j=b.indexOf(1,j)+1,v=i-j,j)?Math.sqrt(1+v*v):0)

But using @edc65 for map and &&t to return the value I was able to shorten it quite a bit.
f=(a,b,j,c=0)=>a.map((v,i)=>c+=v&&(j=b.indexOf(1,j)+1,v=i+1-j,j)&&Math.sqrt(1+v*v))&&c

f=(a,b,j,c=0)        //variables note the j can be undefined
=>a.map((v,i)=>      //loop through the first array
c+=                  //add
v&&                  //test to see if we have a hole
(j=b.indexOf(1,j)+1, //if so see if there is a whole on the other board
v=i+1-j,             //calculate index difference
j)                   //the last var gets evaluated so check to see if indexOf returned -1
&&Math.sqrt(1+v*v))  //calculate
&&c                  //return sum

I still have to find a single case when reduce beats map with an user managed accumulator.

@edc65 probably true, reduce makes more sense semantically, but other than that it is actually kind of awkward to use. Of course, since when did code golfers worry about semantics.

Java, 151
This just walks along a looking for ones, then walks along b when it finds one. If float accuracy is acceptable I could save a couple bytes, but I went with double to match the test output.
double d(int[]a,int[]b){double z=0;for(int x=-1,y=0,d=b.length;x++<a.length&y<d;z+=a[x]>0?Math.sqrt((y-x)*(y++-x)+1):0)for(;y<d&&b[y]<1;y++);return z;}

With whitespace:
double d(int[]a,int[]b){
    double z=0;
    for(int x=-1,y=0,d=b.length;
            x++<a.length&y<d;
            z+=a[x]>0?Math.sqrt((y-x)*(y++-x)+1):0)
        for(;y<d&&b[y]<1;y++);
    return z;
}

Six significant digits is enough accuracy, so it float gives you that, go for it.

@Zgarb The repeated additions on most inputs only give me 4-5 digits tops, so I'll stick to the more accurate version. Thanks for the clarification, though.

JavaScript (ES6) 108
The main point is the f function that maps the input 0..1 arrays in arrays of holes positions. Then the arrays are scanned computing a total rods length using the pythagorean theorem. The |0 near the end is needed to convert NaNs that can result when the driver array (the first) is longer than the second.
F=(a,b,f=a=>a.map(v=>++u*v,u=0).filter(x=>x))=>
  f(a,b=f(b)).map((v,i)=>t+=Math.sqrt((w=b[i]-v)*w+1|0),t=0)&&t

Test In Firefox / FireBug console
;[[[0],[0]]
 ,[[0],[1,0]]
 ,[[1,0,0],[1,1,1,1,1]]
 ,[[0,1,0,1],[1,0,0,1]]
 ,[[0,1,1,0,1,1,1,1,0,0],[1,0,0,1,1,1,0,0,1]]
 ,[[1,1,1,1,1],[0,0,1,1,0,1,0,0,1]]
 ,[[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0],[0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1]]]
.forEach(v=>console.log('['+v[0]+']','['+v[1]+']',F(...v)))

[0] [0] 0
[0] [1,0] 0
[1,0,0] [1,1,1,1,1] 1
[0,1,0,1] [1,0,0,1] 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0]   [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] 20.38177416534678

Octave, 60 59 42
@(a,b)trace(sqrt((find(a)'-find(b)).^2+1))

Perl 98
sub l{$r=0;@a=grep$a->[$_],0..$#$a;@b=grep$b->[$_],0..$#$b;$r+=sqrt 1+(shift(@a)-shift@b)**2 while@a&&@b;$r}

Readable:
sub l {
    $r = 0;
    @a = grep $a->[$_], 0 .. $#$a;
    @b = grep $b->[$_], 0 .. $#$b;
    $r += sqrt 1 + (shift(@a) - shift @b) ** 2 while @a && @b;
    $r
}

Testing:
use Test::More;
for (<DATA>) {
    my ($A, $B, $r) = /\[ ([0-9,]+) \] \s \[ ([0-9,]+) \] \s -> \s ([0-9.]+) /x;
    $a = [split /,/, $A];
    $b = [split /,/, $B];
    cmp_ok l(), '==', $r, "test $_";
}
done_testing($.);
__DATA__
[0] [0] -> 0.0
[0] [1,0] -> 0.0
[1,0,0] [1,1,1,1,1] -> 1.0
[0,1,0,1] [1,0,0,1] -> 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] -> 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] -> 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] -> 20.38177416534678

APL, 35 28 bytes
Uses a similar algorithm to the J solution, but APL has fewer builtins.
{+/4○⊃-/{⍵⍴¨⍨⌊/⍴¨⍵}⍵/¨⍳¨⍴¨⍵}

Example input:
      {+/4○⊃-/{⍵⍴¨⍨⌊/⍴¨⍵}⍵/¨⍳¨⍴¨⍵}(1 0 0 1)(0 1 0 1)
2.414213562


text:
HTML2JSON Converter
Edit
I have posted a 250 lines reference implementation for review at CR, discussing the major class of the code. Download the complete Visual Studio 2013, .NET 4.5 source code (10 kB) from my server.
Story
This is based on a real world puzzle.
A colleague had a very old program. It was announced to be discontinued by the company and then it was really discontinued in 2009. Now I should use that program as well, but it is full of bugs and I refused to use it. Instead I wanted to help my colleague and converted the content into a reusable format so we could import it to any other program.
The data is in a database, but the scheme is horrible because it creates new tables every now and then, so doing a SQL export was not feasible. The program also does not have an export functionality. But it has a reporting capability. Bad luck: reporting to Excel fails, because the output is larger than the 65.000 lines allowed by the only old excel format it supports. The only option left was reporting to HTML.
Task
Given

input is a HTML document
it seems to be created by Microsoft Active Report, which shouldn't really matter. But for the sake of equality, your code must not use any Active Report specific library to parse the HTML (if such a thing exists)
The reports is hierarchically structured in either 2 or 3 levels.
the HTML is horrible (IMHO), it consists of DIVs and SPANs only, each having a @style attribute specified. The left position of the style at a SPAN can be used to detect the indentation, which allows conclusions to get the number of levels.
there is always one SPAN which defines the key. The key is formatted in bold and ends with a colon (use whatever you want to detect it)
The key may be followed by another SPAN which defines the value. If the value is not present, it shall be considered as an empty string.
if a key reappears on the same level, that's the start of a new item

you

create a valid JSON file as output
the JSON needn't be pretty-printed, just valid
non-breaking spaces can be converted to normal spaces or be Unicode 00A0
remove the NOBR tags from the output
ignore any unneeded information like the page number (last SPAN in a DIV), HEAD and STYLE before the first DIV
use the key as the property name (remove the trailing colon and the spaces)
use the value as the property value
create an array property called Children for the items on the next level

As far as I can tell, the HTML is technically ok. All tags are closed etc. but it's not XHTML. You needn't do any error checking on it.
Side note: I don't need your code to solve a task or homework. I have already implemented a converter but to a different output format.
Rules
Code Golf. The shortest code wins. Hopefully the task is complex enough to make it hard for special golfing languages so that other languages have a chance as well.
Libraries are allowed. Loophole libraries specially crafted for this task shall be downvoted.
Answer with shortest code on 2015-03-14 gets accepted.
Sample
The code shall be able to process all kinds of reports the program produces, so do not hard code any keys or values. Here's an anonymized 2 page except of one of the reports.

        <title>
            ActiveReports Document
        </title><meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8" />

                <nobr>Requirement Name:</nobr>
                <nobr>Activate Golf</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Average</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Activate Golf</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Activate Golf Settings</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>Add Balls</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Low</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>High</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Download Golf Puzzles from Internet</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>Add Player</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Average</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Golf Upload Puzzles to Server</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>GLFD</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>High</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Page 1 of 115</nobr>

                <nobr>Requirement Name:</nobr>
                <nobr>Count dimples</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Low</nobr>
                <nobr>Status:</nobr>
                <nobr>Failed</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Low</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Add dimples</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Create divot</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Repair divot</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Modify divot</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>Use iron</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>High</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Go fairway</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Analyze trajectory</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Collect ball</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Exchange ball</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>你好</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>High</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Page 2 of 115</nobr>

Expected JSON Output (handcrafted, please correct me if I added a typo):
{
    "Children":
    [
        {
            "RequirementName": "Activate Golf",
            "Description": "",
            "Risk": "Average",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
                {
                    "TestName": "Activate Golf"
                },
                {
                    "TestName": "Activate Golf Settings"
                }
            ]
        },
        {
            "RequirementName": "Add Balls",
            "Description": "",
            "Risk": "Low",
            "Status": "In Progress",
            "PrioritätQA": "High",
            "Children":
            [
                {
                    "TestName": "Download Golf Puzzles from Internet"
                }
            ]
        },
        {
            "RequirementName": "Add Player",
            "Description": "",
            "Risk": "Average",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
                {
                    "TestName": "Golf Upload Puzzles to Server"
                }
            ]
        },
        {
            "RequirementName": "GLFD",
            "Description": "",
            "Risk": "High",
            "Status": "In Progress",
            "Priorität QA": "Average",
            "Children":
            [
            ]
        },
        {
            "RequirementName": "Count dimples",
            "Description": "",
            "Risk": "Low",
            "Status": "Failed",
            "PrioritätQA": "Low",
            "Children":
            [
                {
                    "TestName": "Add dimples"
                },
                {
                    "TestName": "Create divot"
                },
                {
                    "TestName": "Repair divot"
                },
                {
                    "TestName": "Modify divot"
                }
            ]
        },
        {
            "RequirementName": "Use iron",
            "Description": "",
            "Risk": "High",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
                {
                    "TestName": "Go fairway"
                },
                {
                    "TestName": "Analyze trajectory"
                },
                {
                    "TestName": "Collect ball"
                },
                {
                    "TestName": "Exchange ball"
                }
            ]
        },
        {
            "RequirementName": "你好",
            "Description": "",
            "Risk": "High",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
            ]
        }
    ]
}

You say shortest code wins (and tagged it [tag:code-golf]), but you also say "Highest voted answer on 2015-03-14 gets accepted", as if this were a [tag:popularity-contest].

@Scimonster: Indeed, that's a bug, because usually the shortest golf answers are also upvoted. Updated question.

Can you provide a reference implementation so we can make sure our code works correctly? And perhaps a larger sample of input data?

@FUZxxl: in the sandbox I was asked to make the sample data shorter... In addition, the input here is limited to 35000 chars, so I'd need to provide it for download somwhere else. At this time I only have the original data, which I cannot publish. How large do you want it to be? At the moment I also don't have a reference implementation, but I'll try to provide one if that's helpful. I wanted to solve the puzzle by myself anyway (even if not very golfed).

@ThomasW. I just want some different data so I don't make wrong assumptions about what the input looks like.

In the sample html what indication is there that the current top level child is ending and the next one (starting with "Requirement Name") is starting?

What happens when the text in any field is long enough that it overflows to the next line?

@JerryJeremiah: it starts over with the first key (here: "Requirement Name") at the same left position (here: 0.01388884in) again.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ : Thanks for asking. (Are you familiar with Active Reports?) In reality it will insert a BR tag, even in the middle of a word. But for the puzzle, you needn't consider this, because I export the HTML with very wide columns so that this does not happen.

@ThomasW.: No, the first time hearing the name, and I'm taken aback at the HTML mess it generates.

@FUZxxl: the reference implementation is available. See the top of the question.

VBScript 819 (if line endings count as 1)
VBScript is a Microsoft scripting language unrelated to VBA, VB.net or legacy VB6
For those of you that have never seen it:

http://en.wikipedia.org/wiki/VBScript
http://www.w3schools.com/Vbscript/default.asp

VBScript is NOT designed for golfing and I am not great at golfind anyway so the best I can do is 819.  If you see a way to make it shorter please comment.
To run this code use:
cscript //nologo //u html2json.vbs < html2json.html > html2json.json

This code does not indent the json properly but keeping the indent level would have made it even longer.  The other thing that differs from the example json is that this code doesn't produce empty Children arrays that aren't there in the html - I hope that's ok.  Here is the code:
Set W=WScript
Set S=W.Stdin
W.Echo"{"
Do
While InStr(a,":abs")<1
a=S.Readline
If a=""Then W.Echo"}]}":W.Quit
Wend
Do
If InStr(a,">Page&")<1Then
a=Replace(a," "," ")
Do
B=InStr(a,"&#")+2
If B<3Then Exit Do
C=InStr(B,a,";")
a=Left(a,B-3)&Chr(Mid(a,B,C-B))&Mid(a,C+1)
Loop
D=InStr(a,"<nobr>")+6
E=InStr(D,a,"</nobr>")
V=Mid(a,D,E-D)
F=InStr(a,"top:")+4
G=InStr(F,a,"in;")
T=Mid(a,F,G-F)
If T=U Then
W.Echo X&""""&K&""":"""&V&"""":X=","
K=""
Else
If K<>""Then W.Echo X&""""&K&""":""""":X=","
K=Left(V,Len(V)-1)
K=Replace(K," ","")
P=InStr(a,"left:")+5
Q=InStr(P,a,"in;")
L=Mid(a,P,Q-P)
If L>M Then W.Echo X&"""Children"":[":X=""Else If Abs(T-U)>.3And U>0Then W.Echo"}":X=","
If L<M Then W.Echo"]}":X=","
If Abs(T-U)>.3Then W.Echo X&"{":X=""
End If
End If
a=S.Readline
Loop While InStr(a,">Page ")<0
U=T
M=L
Loop

C# - 1716
Ok, this one was rather simple for me, but that might be the reason why it is not very short. I just golfed the reference implementation (including all parts, not only the part that is posted on Code Review):
namespace System{using Collections.Generic;using Globalization;using IO;using Linq;using ExCSS;using HtmlAgilityPack;using Newtonsoft.Json;class J:JsonConverter{Dictionary<string,string>P=new Dictionary<string,string>();List<J>C=new List<J>();decimal L;J V{get;set;}static void Main(string[]a){J j=new J();j.H(a[0]);File.WriteAllText(a[1],JsonConvert.SerializeObject(j,j));}public override void WriteJson(JsonWriter w,object o,JsonSerializer s){J j=(J)o;w.WriteStartObject();foreach(var p in j.P){w.WritePropertyName(p.Key);w.WriteValue(p.Value);}if(j.C.Count>0){w.WritePropertyName("Children");w.WriteStartArray();foreach(J c in j.C)s.Serialize(w,c);w.WriteEndArray();}w.WriteEndObject();}public override object ReadJson(JsonReader r,Type t,object o,JsonSerializer s){return o;}public override bool CanConvert(Type o){return o==typeof(J);}void H(string f){var h=new HtmlDocument();h.LoadHtml(File.ReadAllText(f));J v=this;foreach(var p in h.DocumentNode.Descendants().Where(x=>(x.Name=="div"&&x.Ancestors("div").Any()))){var k="";foreach(var s in p.Descendants().Where(x=>x.Name=="span")){var d=new Parser().Parse(".d{"+s.Attributes["style"].Value+"}").StyleRules[0].Declarations;var t=Net.WebUtility.HtmlDecode(s.Descendants("nobr").First().InnerText);if(!d.Any(a=>a.Name=="font-weight"&&a.Term+""=="bold")){A(ref v,k,t);k="";}else{A(ref v,k,"");k=t.Trim(':');foreach(var l in from a in d where a.Name=="left"select decimal.Parse(a.Term.ToString().Replace("in",""),new NumberFormatInfo{NumberDecimalSeparator="."})){while(v.L>l)v=v.V;if(l>v.L){J c=new J{L=l,V=v};v.C.Add(c);v=c;}}}}}}void A(ref J j,string k,string v){if(k=="")return;if(j.P.ContainsKey(k)){J s=new J{L=j.L,V=j.V};j.V.C.Add(s);j=s;}j.P.Add(k,v);}}}

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


text:
Fastest way to compute order of magnitude in x86 assembly
The task is simple: write assembly that computes the order of magnitude of an integer using as few clock cycles as possible.

Order of magnitude is defined as log10, not log2.
The range of valid input is 0 to 1012, inclusive. Behaviour for input outside that range is undefined.
Values should be rounded down to the nearest integer, with the exception that given input 0 the output should be 0. (You can consider this to be the best representation of negative infinity that's possible in unsigned integers).
Must be x86 assembly.
The integer must be a runtime value, not a static/inline integer. So we don't know what it is at compile time.
Assume that you have an integer loaded into a register already. (But include setting the value in the register in the answer for clarity).
Can't call any external libraries or functions.
Free to use any of the available instructions in the Intel docs.
No C.
Any of the ~7 Intel Core architectures are acceptable (listed on page 10). Ideally Nehalem (Intel Core i7).

The winning answer is one that uses the fewest clock cycles possible. That is, it can have the most operations per second. Approximate clock cycle summaries are here: http://www.agner.org/optimize/instruction_tables.pdf. Calculating clock cycles can happen after the answer is posted.

Are 'FYL2X' and other FPU instructions allowed?

@DigitalTrauma yes

Log10(0) is NaN.  What should the output be for input 0?

@FryAmTheEggman The winner is the one with the fewest clock cycles.

@DigitalTrauma Magnitude for Log10(0) should be 0.

Should the result be an integer?  If so, how should it be rounded?

@DigitalTrauma yes the result should be an integer. It should be as if you took a string and counted the number of characters (I don't know if that is a feasible solution or not). So order of magnitude for 1023 would be 3. For 9999, 3. For 10000, 4. For 5, 0. For 12, 1, etc.

So the input and output are both integers, yes ? But the input can be as great as 10^12, so it's too big for a 32 bit int. So do we assume 64 bit integer input ?

Is the winning criterion based on the maximum or average number of cycles? And if it's average, what is the distribution of inputs?

Should 999 be magnitude 2? For all the other examples the magnitude is number of digits - 1. Please clarify.

Which processor is targeted?  The linked document lists more than 20 different processes (AMD, Intel, others) and there is considerable variation in the latencies.

@DigitalTrauma Any of the ~7 Intel Core ones (listed on page 10). Ideally Nehalem (Intel Core i7).

7 cycles, constant time
Here's a solution based on my answer to this SO Question.
It uses BSR to count how many bits are needed to hold the number. It looks up how many decimal digits needed to represent the largest number that many bits can hold. Then it subtracts 1 if the actual number is less than the nearest power of 10 with that many digits.
    .intel_syntax noprefix
    .globl  main
main:
    mov rdi, 1000000000000              #;your value here
    bsr rax, rdi
    movzx   eax, BYTE PTR maxdigits[1+rax]
    cmp rdi, QWORD PTR powers[0+eax*8]
    sbb al, 0
    ret
maxdigits:
    .byte   0
    .byte   0
    .byte   0
    .byte   0
    .byte   1
    .byte   1
    .byte   1
    .byte   2
    .byte   2
    .byte   2
    .byte   3
    .byte   3
    .byte   3
    .byte   3
    .byte   4
    .byte   4
    .byte   4
    .byte   5
    .byte   5
    .byte   5
    .byte   6
    .byte   6
    .byte   6
    .byte   6
    .byte   7
    .byte   7
    .byte   7
    .byte   8
    .byte   8
    .byte   8
    .byte   9
    .byte   9
    .byte   9
    .byte   9
    .byte   10
    .byte   10
    .byte   10
    .byte   11
    .byte   11
    .byte   11
    .byte   12
powers:
    .quad   0
    .quad   10
    .quad   100
    .quad   1000
    .quad   10000
    .quad   100000
    .quad   1000000
    .quad   10000000
    .quad   100000000
    .quad   1000000000
    .quad   10000000000
    .quad   100000000000
    .quad   1000000000000

Compiles on GCC 4.6.3 for ubuntu and returns the value in the exit code.
I'm not confident interpreting that cycles table for any modern processor, but using @DigitalTrauma's method, on the Nehalim processor, I get 7?
ins        uOps Latency
---        -    -
BSR r,r  : 1    3
MOVZX r,m: 1    -
CMP m,r/i: 1    1
SBB r,r/i: 2    2

Oh - saw DigitalTrauma's after I started writing mine. Similar ideas. Using his counting methodology I think get 3,1,1,1=6 for BSR,MOV,CMP,SBB

Yep, I think yours beats mine.  Just goes to show a) I'm not an assembly programmer and b) assembly is best left alone by us mere mortals ;-)

The integer must be a runtime value, not a static/inline integer. So we don't know what it is at compile time.

right, and the next line says: "Assume that you have an integer loaded into a register already. (But include setting the value in the register in the answer for clarity)."   Which is what I have done.

replace the movzx eax with mov al.  The top 24 bits of eax will already be zero, so the zx is redundant (and it's expensive).

BTW, clang will generate your code now; here's a 64-bit version :
uint32_t ilog10(uint64_t v) {
uint32_t lz = 63 ^ __builtin_clzll(v);
constexpr char digits[64] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19};
uint32_t guess = digits[lz];
constexpr uint64_t powers[21] = {1ULL, 10ULL, 100ULL, 1000ULL, etc};
return guess - (v < powers[guess]);
}
See https://godbolt.org/g/55Bd5N

@peterferrie: movzx eax, byte mem is cheaper than mov al, mem on Intel CPUs.  mov al,mem is a micro-fused ALU+load instruction that merges into the old value (How exactly do partial registers on Haswell/Skylake perform? Writing AL seems to have a false dependency on RAX, and AH is inconsistent).  movzx is a pure load that zero-extends in the load port.  See Any way to move 2 bytes in 32-bit x86 using MOV without causing a mode switch or cpu stall? for a summary of movzx costs on recent CPUs.

In this case EAX already has to be ready (because it's an input to the addressing mode) so the false dependency doesn't hurt.  But the partial-register stall when the caller reads EAX on Nehalem or earlier does hurt.  And the merge uop will un-laminate from the load on SnB/IvB because of the indexed addressing mode.

Best case 8 cycles, Worst case 12 cycles
Since it is not clear in the question, I am basing this off the Ivy Bridge latencies.
The approach here is to use the bsr (bit scan reverse) instruction as a poor-man's log2().  The result is used as an index into a jump table which contains entries for bits 0 to 42.  I am assuming that given that operation on 64bit data is implicitly required, then use of the bsr instruction is OK.
In the best case inputs, the jumptable entry can map the bsr result directly to the magnitude. e.g. For inputs in the range 32-63, the bsr result will be 5, which is mapped to a magnitude of 1.  In this case, the instruction path is:
Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

In the worst case inputs, the bsr result will map to two possible magnitudes, so the jumptable entry does one additional cmp to check if the input is > 10n.  E.g. for inputs in the range 64-127, the bsr result will be 6.  The corresponding jumptable entry then checks if the input > 100 and sets the output magnitude accordingly.
In addition for the worst case path, we have an additional mov instruction to load a 64bit immediate value for use in the cmp, so the worst case instruction path is:
Instruction    Latency

bsrq                 3
jmp                  2
movabsq              1
cmpq                 1
ja                   2
movl                 1
jmp                  2

total               12

Here is the code:
    /* Input is loaded in %rdi */
    bsrq    %rdi, %rax
    jmp *jumptable(,%rax,8)
.m0:
    movl    $0, %ecx
    jmp .end
.m0_1:
    cmpq    $9, %rdi
    ja  .m1
    movl    $0, %ecx
    jmp .end
.m1:
    movl    $1, %ecx
    jmp .end
.m1_2:
    cmpq    $99, %rdi
    ja  .m2
    movl    $1, %ecx
    jmp .end
.m2:
    movl    $2, %ecx
    jmp .end
.m2_3:
    cmpq    $999, %rdi
    ja  .m3
    movl    $2, %ecx
    jmp .end
.m3:
    movl    $3, %ecx
    jmp .end
.m3_4:
    cmpq    $9999, %rdi
    ja  .m4
    movl    $3, %ecx
    jmp .end
.m4:
    movl    $4, %ecx
    jmp .end
.m4_5:
    cmpq    $99999, %rdi
    ja  .m5
    movl    $4, %ecx
    jmp .end
.m5:
    movl    $5, %ecx
    jmp .end
.m5_6:
    cmpq    $999999, %rdi
    ja  .m6
    movl    $5, %ecx
    jmp .end
.m6:
    movl    $6, %ecx
    jmp .end
.m6_7:
    cmpq    $9999999, %rdi
    ja  .m7
    movl    $6, %ecx
    jmp .end
.m7:
    movl    $7, %ecx
    jmp .end
.m7_8:
    cmpq    $99999999, %rdi
    ja  .m8
    movl    $7, %ecx
    jmp .end
.m8:
    movl    $8, %ecx
    jmp .end
.m8_9:
    cmpq    $999999999, %rdi
    ja  .m9
    movl    $8, %ecx
    jmp .end
.m9:
    movl    $9, %ecx
    jmp .end
.m9_10:
    movabsq $9999999999, %rax
    cmpq    %rax, %rdi
    ja  .m10
    movl    $9, %ecx
    jmp .end
.m10:
    movl    $10, %ecx
    jmp .end
.m10_11:
    movabsq $99999999999, %rax
    cmpq    %rax, %rdi
    ja  .m11
    movl    $10, %ecx
    jmp .end
.m11:
    movl    $11, %ecx
    jmp .end
.m11_12:
    movabsq $999999999999, %rax
    cmpq    %rax, %rdi
    ja  .m12
    movl    $11, %ecx
    jmp .end
.m12:
    movl    $12, %ecx
    jmp .end

jumptable:
    .quad   .m0
    .quad   .m0
    .quad   .m0
    .quad   .m0_1
    .quad   .m1
    .quad   .m1
    .quad   .m1_2
    .quad   .m2
    .quad   .m2
    .quad   .m2_3
    .quad   .m3
    .quad   .m3
    .quad   .m3
    .quad   .m3_4
    .quad   .m4
    .quad   .m4
    .quad   .m4_5
    .quad   .m5
    .quad   .m5
    .quad   .m5_6
    .quad   .m6
    .quad   .m6
    .quad   .m6
    .quad   .m6_7
    .quad   .m7
    .quad   .m7
    .quad   .m7_8
    .quad   .m8
    .quad   .m8
    .quad   .m8_9
    .quad   .m9
    .quad   .m9
    .quad   .m9
    .quad   .m9_10
    .quad   .m10
    .quad   .m10
    .quad   .m10_11
    .quad   .m11
    .quad   .m11
    .quad   .m11_12
    .quad   .m12
    .quad   .m12
    .quad   .m12

.end:
/* output is given in %ecx */

This was mostly generated from gcc assembler output for proof-of-concept C code I wrote.  Note the C code uses a computable goto to implement the jump table.  It also uses the __builtin_clzll() gcc builtin, which compiles to the bsr instruction (plus an xor).

I considered several solutions before arriving at this one:

FYL2X to calculate the natural log, then FMUL by the necessary constant.  This would presumably win this if it was an [tag:instruction:golf] contest.  But FYL2X has as latency of 90-106 for Ivy bridge.

Hard-coded binary search.  This may actually be competitive - I'll leave it to someone else to implement :).

Complete lookup table of results.  This I'm sure is theoretically fastest, but would require a 1TB lookup table - not practical yet - maybe in a few years if Moore's Law continues to hold.

If necessary I can calculate an average latency for all allowed input.

jmp and jcc don't have latency, only throughput costs.  Branch-prediction + speculative execution mean control dependencies aren't part of data dependency chains.


text:
Pure Sourcery - Shaping programs that output the digits 0 through 9
Here's a pixelated 5 by 7 font for the digits 0 through 9:
.███.
█...█
█...█
█...█
█...█
█...█
.███.

..█..
███..
..█..
..█..
..█..
..█..
█████

.███.
█...█
....█
...█.
..█..
.█...
█████

.███.
█...█
....█
..██.
....█
█...█
.███.

█..█.
█..█.
█..█.
█████
...█.
...█.
...█.

█████
█....
█....
.███.
....█
█...█
.███.

.███.
█...█
█....
████.
█...█
█...█
.███.

█████
....█
....█
...█.
...█.
..█..
..█..

.███.
█...█
█...█
.███.
█...█
█...█
.███.

.███.
█...█
█...█
.████
....█
█...█
.███.

(This font and this page will probably look better if you run this JavaScipt code in your browsers console or in the URL bar prefixed by javascript:: $('#question pre,.answer pre').css('line-height',1).)
Write two equal sized rectangular blocks of text, one to represent the empty spaces (.) in the font above, and one to represent the filled spaces (█).
When these two text blocks are arranged into the same 5×7 pattern as one of the digits above, then the resulting large text block should be a program that prints that digit to stdout. This should work for all 10 digits.
For example, if your . text block was
---
'''

and your █ text block was
ABC
123

then the program
---ABCABCABC---
'''123123123'''
ABC---------ABC
123'''''''''123
ABC---------ABC
123'''''''''123
ABC---------ABC
123'''''''''123
ABC---------ABC
123'''''''''123
ABC---------ABC
123'''''''''123
---ABCABCABC---
'''123123123'''

should output 0. Similarly, the program
------ABC------
''''''123''''''
ABCABCABC------
123123123''''''
------ABC------
''''''123''''''
------ABC------
''''''123''''''
------ABC------
''''''123''''''
------ABC------
''''''123''''''
ABCABCABCABCABC
123123123123123

should output 1, and so on up to the program for 9.
You can use this stack snippet to make the digit shaped programs:

<textarea id='empty' rows='8' cols='32' placeholder='empty space text block...'></textarea><textarea id='filled' rows='8' cols='32' placeholder='filled space text block...'></textarea>
Digit <input id='digit' type='text' value='0'> <button type='button' onclick='go()'>Generate</button>

<textarea id='output' rows='16' cols='64' placeholder='output...' style='background-color: #eee;' readonly></textarea>

Details

None of the 10 large text block programs should require input. Only output the single digit plus an optional trailing newline. Output to stdout or a similar alternative.
None of the programs may read or access their own source code. Treat this like a strict quine challenge.
The text blocks may not be identical and must have nonzero dimensions.
The text blocks may contain any characters except line terminators.
The 10 programs must be full-fledged programs written in the same language, they are not REPL snippets. You may optionally add a trailing newline to all of them or none of them.

Scoring
Your score is the area (width times height) of one of your text blocks. (They are the same size so there's no point in counting both blocks.) The area of the example is 3 by 2, for a score of 6.
The lowest score wins. In case of ties, the highest-voted answer wins.

On your code, you can improve it a lot. var t=parseInt(document.getElementById("digit").value[0]);if(isNaN(t))return void alert("Invalid digit."); can be written as var t=document.getElementById("digit").value[0]/1;if(t!=t)return void alert("Invalid digit.");, which is the same but shorter. There are a few more things you can improve in it, but it does look great!

@IsmaelMiguel TBH I put it through a JS minifier to get it on one line. It was never meant to be golfed.

Oh, dude... That is a bit lazy... In a golfing question, you post a non-golfed code... But hey, I get it and I'm just saying this. You don't have to follow what I said. But it's a good thing to do.

@IsmaelMiguel I posted ungolfed utility code, which arguably should be as readable as possible so bugs are easier to spot. But really, as long as it works, the code size of the stack snippet has literally zero bearing on the outcome of the challenge.

I know, and I get it. I was just trying to joke about it. Sadly, mission failed. But maybe next time.

text blocks may not be identical really? I want to see someone break this rule, by giving two identical codeblocks, which magically return different digits, when every number is exactly the same code ^^

This should be easy as pie with Marbellous. Sadly I don't know Marbellous :(

@Falco I know, I know :P I just need to cover my bases.

CJam, 20 18 14 13 12 * 1 = 12
Try it online: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Empty block
];BG*K+ :BD%

Solid block
];B9+33%:B4/

Explanation
I used a similar strategy to Sp3000's solution, such that each block performs a multiplication, an addition, and (possibly) a modulo operation on a variable and saves the value back. To find an optimal solution, I used good old brute force. I wrote a program that searches the space of all possible initial values (the initial values of CJam variables) and many millions of possible pairs of transformation functions such that the output for every digit form is unique. Then, I filtered the results for ones such that the final result for digit forms ending in an empty block, of which there are 8, can be mapped back to the correct result via another multiply, add, and modulo formula.
After a couple of days of CPU time of searching, the best result so far is down to a size of 12! This solution starts with a value of 11, the empty block transformation function is x * 16 + 20, the empty block result function is x % 13, the solid block transformation function is (x + 9) % 33, and the solid block result function is x / 4.

><> (Fish), 5 * 10 = 50
Empty block
   \   !9
4n;    n/
1n;\
       \
0n;n7\\\

Solid block
   \; n8/
     /!/!v
     \  ;6
3n;\ ! /nn
2n;n5<  8;

This code contains no logic or arithmetic only uses static redirections of ><>'s 2D instruction pointer (IP) with 'mirrors' (/ and \) and two 'arrows' (< and v). The only other flow-controller is the 'trampoline' (!) which jumps through the next character.
The IP starts from the top left corner heading East. After some redirections it reaches a number it is pushed onto the stack and printed out with n and the program terminates with ;.
The program flow
A block 'recognizes' the current state of the program from the fact that which point the IP came in and based on the state it decides which direction should it to let out the pointer (which block should be executed next) and in which exact position the pointer should left (which will be the new state). Of course the blocks don't do any logic all this behavior comes from the redirectors.

I was hoping for an answer like this. Pure magic.

CJam, 23 22 19 * 1 = 19
Empty block:
];G)B%:G"73860594"=

Solid block:
];GW*B+3*D%:G    7-

Try it online.
I'm trying to get lucky with mathematical coincidences and failing, so here's a slightly different approach to uniqueness mapping from Martin's solution.
Start with 16. Empty blocks add 1 and take modulo 11. Solid blocks multiply by -1, add 11, multiply by 3 then take modulo 13. This magically maps 03456789 (the digits which end on an empty block) to 41753026, which we use indexing to get right. 12 maps neatly to 89, which we can remedy by subtracting 7.

CJam, 28 27 x 1 = 27
Here is a start.
Empty block
U):U;

Solid block
];U):UW+:WF%"1302986_7_54"=

Test it here. I can't give you a permalink with the code, because the code is too long, so you'll have to copy it in manually from the snippet in the challenge.
The idea is to hash the shape as follows:

For each "pixel" increment a counter U.
For each black "pixel" add U to a running total W (which starts at -1). At the end, we take this modulo 15, which happens to give unique results, which use to index into a lookup string.

Zsh -F, 1 * 34 = 34
Empty block:
x+=0;X=5719060800034;(bye 2-x[2]);

Solid block:
x+=1;(bye X[1+0b$x%13]);
Outputs via exit code, which is the simplest way I could think of to get only the final block to output a value. bye exits with a status code, and () prevents the shell from actually exiting; it only sets the code, so the last value will be the exit code of the whole shell.
Each block also appends either 0 or 1 to a string x; If the last block is solid (only the case for 1 and 2), the output is 2 - (the second digit of x). If the last block is empty, then 0b$x converts x from binary, %13 takes it modulo thirteen, and then that is indexed into the string X which is initialised earlier, to choose the correct output code.
Attempt This Online:
0
1
2
3
4
5
6
7
8
9
Here's the code for 5:
x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);
x+=0;X=5719060800034;(bye 2-x[2]);x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);
x+=0;X=5719060800034;(bye 2-x[2]);x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);
x+=1;(bye X[1+0b$x%13]);          x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=1;(bye X[1+0b$x%13]);
x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=0;X=5719060800034;(bye 2-x[2]);
x+=0;X=5719060800034;(bye 2-x[2]);x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=1;(bye X[1+0b$x%13]);          x+=0;X=5719060800034;(bye 2-x[2]);
x+=1;(bye X[1+0b$x%13]);          x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=0;X=5719060800034;(bye 2-x[2]);x+=1;(bye X[1+0b$x%13]);

Each block, read left-to-right, constructs the string 00000011110111110001111100111010001, which is 519633361 in binary. This modulo 13 is 0, and then the 1+0'th character of X (5719060800034) is 5, so that's the exit code.

Nice answer! I think this explanation's good enough for 300 rep, although giving an example for 0 or another digit wouldn't hurt.

Python 3, 73 bytes
empty code:
a,b=id and(0,1)or(2*a+0,b+1);id=b>34and print(b'XH"V;G F@D'.index(a%91));

Try it online!
solid code:
a,b=id and(1,1)or(2*a+1,b+1);id=b>34and print(b'XH"V;G F@D'.index(a%91));

Try it online!
both code contains unprintable chars
How it works:

on the first occurence of either empty or solid: as id is a python built-in, it is evaluated as True so id and <first> or <second> will evaluate <first> which initialise a and b. Then id is set to 0
a is the binary representation of the code with 0 for empty and 1 for solid
b is the number of bloc executed.
when b is equal to 35 (last bloc) it prints the result.
print(b'XH"V;G F@D'.index(a%91)) prints the index of the char whose codepoint is equal to a%91 (which is the right result)

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