text:
Polynomial Long Division
Implement polynomial long division, an algorithm that divides two polynomials and gets the quotient and remainder:
(12x^3 - 5x^2 + 3x - 1) / (x^2 - 5) = 12x - 5 R 63x - 26
In your programs, you will represent polynomials as an array, with the constant term on the tail. for example, x^5 - 3x^4 + 2x^2 - x + 1 will become [1, -3, 0, 2, -1, 1].
The long division function you are going to write will return two values: the quotient and the remainder. You do not need to handle numerical imprecisions and arithmetic errors. Do not use math library to do your job, however, you may make your function able to deal with symbolic values. Shortest code wins.
EXAMPLE: div([12, -5, 3, -1], [1, 0, -5]) == ([12, -5], [63, -26])

https://rosettacode.org/wiki/Polynomial_synthetic_division#Python

J, 94
f=:>@(0&{)
d=:0{[%~0{[:f]
D=:4 :'x((1}.([:f])-((#@]{.[)f)*d);([:>1{]),d)^:(>:((#f y)-(#x)))y'

eg.
(1 0 _5) D (12 _5 3 _1;'')
63 _26 | 12  _5

Explanation of some snippets, given that a: (12 -5 3 -1) and b: (1 0 -5)
length of a:
#a
4

make a and b same order by appending zeroes to b:
(#a) {. b
1 0 -5 0

divide higher powers (first elements) of a, b:
(0{a) % (0{b)
12

multiply b by that and subtract it from a:
a - 12*b
12 0 _60

repeat n times b = f(a,b):
a f^:n b

Two things. 1) do you win characters by taking dividend/divisor in the unusual order? 2) is that trailing `;''' in the dividend necessary? looks like something you should do from inside the actual program.

@J-B: 1) No, actually it could be shorter for the "usual" order; it's just the way I started thinking about it. 2) It's part of the array so I suppose it should be part of the input.

I can't seem to grasp what an additional empty array has to do with the input.

Python 2, 260 258 257 255 bytes
exec'''def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d@R(1,F+1)];r=[0@R(D)];a=[[0@R(F)]@R(D)]
@R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i@r[D-F:]]'''.replace('@',' for i in ')

This executes:
def d(p,q):
 R=range;D=len(p);F=len(q)-1;d=q[0];q=[q[i]/-d for i in R(1,F+1)];r=[0 for i in R(D)];a=[[0 for i in R(F)] for i in R(D)]
 for i in R(D):
  p[i]/=d;r[i]=sum(a[i])+p[i]
  for j in R(F):
   if i<D-F:a[i+j+1][F-j-1]=r[i]*q[j]
 return r[:D-F],[d*i for i in r[D-F:]]

Use like so:
>>>d([12., -5., 3., -1.],[1.,0.,-5.])
([12.0, -5.0], [63.0, -26.0])

Wow, first time I've seen an exec/replace actually be used to save characters.

@xnor I've done that one other time, but for more than one replacement.

Haskell, 126
For a start:
l s _ 0=s
l(x:s)(y:t)n=x/y:l(zipWith(-)s$map(*(x/y))t++repeat 0)(y:t)(n-1)
d s t=splitAt n$l s t n where n=length s-length t+1

Sample use:
*Main> d [12, -5, 3, -1] [1, 0, -5]
([12.0,-5.0],[63.0,-26.0])

Javascript with lambdas, 108
f=(a,b)=>{for(n=b.length;a.length>=n;a.shift())for(b.push(k=a[q=0]/b[0]);q<n;++q)a[q]-=k*b[q];b.splice(0,n)}

It replaces first argument by reminder and second by result.
Example of usage in Firefox:
f(x=[12,-5,3,-1], y=[1,0,-5]), console.log(x, y)
// Array [ 63, -26 ] Array [ 12, -5 ]

Sorry for the bug. Already fixed.

APL (Dyalog Unicode) 18.0, 63 bytes
{0≥d←1+⍺-⍥≢⍵:⍬⍺⋄q(r↓⍨⊥⍨0=⌽r←⍺-m+.×q←(d↑⍺)⌹d↑m←⍉{⍵,⍨⍺⍴0}∘⍵⍤0⍳d)}

Try it online!
The TIO link (which uses 17.1) has a polyfill for ⍥.
Well, it uses ⌹ to solve a system of equations, but technically it's not a library, so...
How it works
Illustration for the inputs x←12 ¯5 3 ¯1 and y←1 0 ¯5:

We know that, from the lengths of x and y, the quotient will have two terms.
Construct a matrix which, when matrix-multiplied with the quotient, will give the polynomial product of quotient with y:

 1  0
 0  1
¯5  0
 0 ¯5

Calculate the quotient q so that first two terms of x agree with those of y×q, using matrix division ⌹.
Calculate the remainder r using x - y×q, then remove leading zeros of r. (q is guaranteed to have no leading zeros.)

{ ⍝ x←dividend, y←divisor
  d←1+⍺-⍥≢⍵  ⍝ Degree of the quotient; 1 + length of x - length of y
  0≥d: ⍬⍺    ⍝ If degree is zero or lower: quotient is zero, remainder is x

  m←⍉{⍵,⍨⍺⍴0}∘⍵⍤0⍳d  ⍝ Construct the matrix
                 ⍳d  ⍝ 0..d-1
     {      }∘⍵⍤0    ⍝ For each number i, yielding a matrix row
      ⍵,⍨⍺⍴0         ⍝ Make i copies of 0, and append y
                     ⍝ (Implicitly right-pad with zeros for short rows)
    ⍉                ⍝ Transpose

  q←(d↑⍺)⌹d↑m  ⍝ Get the quotient
          d↑m  ⍝ Take first d rows of the matrix
    (d↑⍺)      ⍝ Take first d numbers of x
         ⌹     ⍝ Matrix divide aka. solve linear system of equations

  r←⍺-m+.×q  ⍝ Get the remainder

  q(r↓⍨⊥⍨0=⌽r)  ⍝ Remove leading zeros from r, and join with q
       ⊥⍨0=⌽    ⍝ Reverse r, test equal to zero, and count trailing ones (⊥⍨)
    r↓⍨         ⍝ Drop that many numbers from start of r
  q(         )  ⍝ Join with q
}


text:
Implement BCD Arithmetic
Write the shortest function you can that takes two binary-coded decimal integers and a character indicating an arithmetic operation to perform and return the result.
Input Specification
You will be passed two 32-bit bit patterns representing unsigned BCD integers.  In C or Java, for example, you would be passed an int (unsigned, if you prefer).  The third argument to your function will be a single character denoting what operation to perform.  If your language requires fixed return sizes, return a 32-bit result and ignore overflow.  Your return value should also be encoded as a BCD.
You should support +, -, *, /, and %.  For subtraction, the first argument is the minuend and the second argument is the subtrahend.  For division and modulo, the first argument is the quotient and the second is the divisor.
Example
bcd(0x00000127, 0x00000003, '+') => 0x00000130 // NOT 0x0000012A

Python - 47 chars
bcd=lambda*a:"0x%08d"%eval("%x%s%x"%(a*2)[::2])

tests
>>> print bcd(0x00000127, 0x00000003, '+')
0x00000130
>>> print bcd(0x00000127, 0x00000003, '*')
0x00000381
>>> print bcd(0x00000127, 0x00000003, '/')
0x00000042
>>> print bcd(0x00000127, 0x00000003, '-')
0x00000124

I guess the question says we have to return as a BCD? http://codepad.org/6SyEB7DJ

@Dogbert, perhaps, but it doesn't really make sense to me to talk about passing in / returning a BCD. BCD here is just painting "0x" in front of the decimal representation of the number, which is quite different from using BCD numbers in assembler

Windows PowerShell, 54 56 69
filter f($a,$b,$o){'0x'+("{0:x}$o{1:x}"-f+$a,+$b|iex)}

A bit cheating, I guess, but the output very well works as input again. I.e., PowerShell doesn't care whether it's a string or actual numeric literal there.
Test:
> f 0x127 0x3 +
0x130

History:

2011-02-11 10:35 (69) – First attempt.
2011-02-11 10:36 (56) – Going easy on the extra zeroes.
2011-02-11 10:41 (54) – filter is shorter.

JavaScript ES6, 61 bytes
(a,b,y)=>0|'0x'+~~eval([a,b].map(t=>+t.toString(16)).join(y))

source: Stack Exchange

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

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

sort: votes


text:
Print a Binary Tree
Inspired by a recent question on SO...
Write a function to print a binary tree in the following format:
   3
 /   \
1     5
 \   / \
  2 4   6

The output should consist of a line of nodes, followed by a line of / and \ characters indicating relationships, followed by a line of nodes, etc.
You can assume all nodes are representable as a single character.
Adjacent nodes on the lowest level should be separated by at least one space, nodes further up should be separated as appropriate.
Nodes with two children should be placed precisely in the middle of their direct children.
Relationship slashes should be halfway between the parent and the appropriate child (round whichever way you want).

Input:
The input will be provided as an argument to your function. I won't specify the exact structure of the tree, however it must be usable as an actual binary tree. No "trees are represented in my program as strings coincidentally looking like the expected output".
You may print to an output stream or return a string containing the output, your choice.
Points for shortest code, but I'd much prefer a fully working long solution than a 90%-working short one.

Update for the bounty:
For the bounty, I (Optimizer) am making slight changes:

Input can be from STDIN,ARGV or function argument.
Output needs to be on STDOUT (or console.log for JS)
You can assume that input is in a form of array, for ex. [1,2,3] or [1 2 3]

Update 2 - The binary tree should actually be a binary search tree. Since I did not mention this initially, I will allow users to treat the converting a normal array into a binary search tree array as a separate program and the final byte count will only be for the program to take in the array as argument and print it like a binary tree.

Should we use several relationship slashes were appropriate? Must we use the minimum number of slashes? Should one distinguish between having a single left child and a single right child? Would it be fine to have leading spaces in every output line?

What do we do if the tree isn't complete (2^n-1 nodes for some n)?  Some nodes (which ones?) have only one child.  But if we're allowed to have nodes with only one child, the degenerate tree is easy to make (1-2-3-4-5-6 down and to the right, say).

How you draw it for large numbers? For example 30000,1000,499999

Fortran 77 -- 1085 characters
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.))
      v=2**(m+1)-1
      do l=1,m
         n=2**(l-1)
         k=2**(m-l+2)-3
         w=(3+k)*2**(l-1)-k
         p=1+(v-w)/2
         if(l.ne.1)then
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else
               print g,' '
            endif
         enddo
         print*
      enddo
      end

The tree is represented in the input array t in the usual fashion, root at 1, root->left at 2, root->right at 3 root->left->left at 4...
The output should fit in a conventional terminal up to 5 levels deep.
I use exactly one slash between each pair of nodes, which looks pretty silly near the top once there are four or more levels. I allowed for up to three digit nodes.
Full program with comments and a launching scaffold:
      program tree

      parameter (l=8)          ! How many nodes to support
      dimension i(l)

c     Initialize the array to all empty nodes
      do j=1,l
         i(j)=-1
      end do
c     Fill in some values
      i(1)=3
      i(2)=1
      i(3)=5
      i(5)=2
      i(6)=4
      i(7)=7
c      i(14)=6
c      i(15)=8
c     Call the printing routine
      call q(l,i)

      stop
      end

c     Print an ASCII representation of the tree
c
c     u the length of the array containing the tree
c     t an integer array representing the tree.
c
c     The array contains only non-negative values, and empty nodes are
c     represented in the array with -1.
c
c     The printed representation uses three characters for every node,
c     and places the (back) slash equally between the two node-centers.
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.)) ! maximum depth of the tree
      v=2**(m+1)-1              ! width needed for printing the whole tree
                                ! Optimized from 3*2**m + 1*((2**m)-1) at
                                ! the bottom level
      do l=1,m
         n=2**(l-1)             ! number of nodes on this level
         k=2**(m-l+2)-3         ! internode spacing
         w=(3+k)*2**(l-1)-k     ! width needed for printing this row
                                ! Optimized from 3*2**l + k*((2**l)-1) at
                                ! the bottom level
         p=1+(v-w)/2            ! padding for this row
c     Print the connecting lines associated with the previous level
         if(l.ne.1)then         ! Write the connecting lines
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
c     Print the nodes on this level
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else
               print g,' '
            endif
         enddo
         print*
      enddo
      end

Output with input equivalent to the example:
$ ./a.out
         3
     /      \
     1       5
      \    /  \
       2   4   7

HELP why this language?

Because it is so poorly suited to golfing.

CJam, 100 99 bytes
q~_,2b,)2\#:Q1@{_2$<Q(S*:T*TQ2/:Q@ts[N+_0@{@1$' >{2$St2$_Q3*&2/^_4$>"\/"=t}*@)}/;U*o]o1:U$>\2*\}h];

Input must be a list of characters, without any ascii control characters. Empty nodes are denoted by a space. It also must be a perfect binary tree with exactly 2n-1 nodes.
Example:
['6 '3 '7 '1 '4 '  '9 '0 '2 '  '5 '  '  '8 ' ]

Or simply use strings:
"63714 902 5  8 "

Output:
                6
            /       \
        3               7
      /   \               \
    1       4               9
   / \       \             /
  0   2       5           8

Explanation
q~                        " Read input. ";
_,2b,                     " Get tree height. ";
)2\#:Q                    " Get (displayed) tree width and save it in Q. ";
1@                        " Push X=1 and rotate the input to top. ";
{                         " Do: ";
    _2$<                  " Get first X characters from the input. ";
    Q(S*:T                " T = (Q-1) spaces. ";
    *                     " Separate the X characters by T. ";
    TQ2/:Q@t              " Put the string in the middle of T, and divide Q by 2. ";
    s                     " Concatenate everything into a string.
                            This is the line of node labels. ";
    [
        N+                " Append a newline. ";
        _                 " Duplicate. ";
        0@                " Push a 0 and rotate the original string to top. ";
        {                 " For each character: ";
            @             " Rotate the duplicate to top. ";
            1$' >         " Test if the current character is greater than a space. ";
            {             " If true: ";
                2$St      " Set the current character in the duplicate to space. ";
                2$        " Copy the current position I (the number initialized with 0). ";
                _Q3*&2/^  " Calculate I ^ ((I & (3*Q))>>1),
                            the position of the relationship character. ";
                _4$>      " Test if it is greater than the current position. ";
                "\/"=     " Select the relationship character. ";
                t         " Change the character in the duplicate. ";
            }*
            @)            " Increment the current position. ";
        }/
                          " The last two items are the line of relationship characters
                            and the tree width. ";
        ;                 " Discard the tree width. ";
        U*                " If it is the first line, empty the line of
                            relationship characters. ";
        o                 " Output. ";
    ]o                    " Output the line of node labels. ";
    1:U                   " Mark it not the first line. ";
    $>                    " Remove the first X characters from the input. ";
    \2*\                  " Multiply X by 2. ";
}h                        " ...while the input is not empty. ";
];                        " Discard everything in the stack. ";

Conversion script
[[0LL]W]
[q~{_a_:i={'0+}*}%La2*f+
_,,]z$
1$a+
{
    {
        1$1=1$1=>:T
        {
            ~@0=2 3$1=t
            @1@ta\+
        }*
        T
    }g
}*
0=1=a
{
    {
        (M\+:M;
        La[' LL]aer~
    }%
    _[' LL]a-
}g
];
M0+`-3<']+

It accepts either characters or single digit numbers.
Examples (all are the same):
['6 '7 '9 '3 '1 '2 '8 '4 '0 '5]
[6 7 9 3 1 2 8 4 0 5]
"6793128405"

Output:
['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]

It's a straight-forward Cartesian tree construction.

You can just add two more bytes and make the input of conversion script as proper integers instead of characters :)

@Optimizer Edited to support both. I think characters makes more sense since it only support node names with a single character. There are much more characters than single digit numbers.

APL, 125 characters
{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)×¯1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}

Example:
{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)×¯1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}('1' ('2' ('3' ('4' ()()) ('5' ()())) ('6' ()('7' ()())))('8' ()('9' ('0' ()())())))

Tested here.

Is this the conversion script too ?

@Optimizer It takes the nested array input format, which can be probably used as binary search tree (but I'm not sure about the complexity). If I must use some more usual formats... maybe I'll do it later.

@Optimizer Now reading the question again, does "binary search tree array" means the array of a complete binary tree in depth order (or something else)? I didn't think it was anything specific. And searching this term didn't give anything useful.

http://en.wikipedia.org/wiki/Binary_tree#Arrays

@Optimizer Well, that was just what I meant. But I don't think it is usually called "binary search tree array", but only "a kind of array storage of binary trees". It probably need some clarification... And I'll probably fix this answer days later, maybe in another language...

Python 2, 411 bytes
import math
def g(a,o,d,l,b):
 if l<0:
    return
 c=2*b+1
 k=2*l+1
 o[k]=' '*b
 n=d-l
 p=1 if n==0 else 3*2**n-1
 o[k-1]=p/2*' '
 i=0
 for v in a[2**l-1:2**l*2-1]:
    v=' ' if v==None else v
    o[k]+=v+' '*c
    m=' ' if v==' ' else '/' if i%2==0 else '\\'
    o[k-1]+=m+max(1,b)*' ' if i%2==0 else m+p*' '
    i+=1

 g(a,o,d,l-1,c)
def f(a):
 d=int(math.log(len(a),2))
 o=['']*(d*2+2)
 g(a,o,d,d,0)
 print '\n'.join(o[1:])

Note: First indentation level is 1 space, second is one tab.
Call f with a list of one-character strings or None's, eg. f(['1',None,'3']). The list can't be empty.
This should obey the rules for the bounty.
Converter script:
Converts and array to the format used by the binary tree printer.
Example:
$ python conv.py [3,5,4,6,1,2]
['3', '1', '5', None, '2', '4', '6']

-
import sys

def insert(bt, i):
    if i < bt[0]:
        j = 0
    else:
        j = 1

    n = bt[1][j]
    if n == [None]:
        bt[1][j] = [i, [[None], [None]]]
    else:
        insert(bt[1][j], i)

def insert_empty(bt, i):
    if i == 0:
        return
    if bt == [None]:
        bt += [[[None], [None]]]

    insert_empty(bt[1][0], i - 1)
    insert_empty(bt[1][1], i - 1)

def get(l, level):
    if level == 0:
        if type(l) == list:
            return ([], l)
        else:
            return ([l], [])
    elif type(l) != list:
        return ([], [])

    res = []
    left = []

    for r, l in  [get(i, level - 1) for i in l]:
        res += r
        left += l

    return (res, left)

if __name__ == '__main__':
    l = eval(sys.argv[1])
    bt = [l[0], [[None], [None]]]
    map(lambda x: insert(bt, x), l[1:])

    depth = lambda l: 0 if type(l) != list else max(map(depth, l)) + 1
    d = (depth(bt) + 1) / 2

    insert_empty(bt, d - 1)

    flat = []
    left = bt
    i = 0
    while len(left) > 0:
        f, left = get(left, 1)
        flat += f

        i += 1

    for i in range(len(flat) - 1, -1, -1):
        if flat[i] == None:
            flat.pop()
        else:
            break

    flat = map(lambda x: None if x == None else str(x), flat)

    print flat

Examples:
To run these you should have the main file named bt.py and the converter file named conv.py.
$ python conv.py [3,5,4,6,1,2] | python -c 'import bt; bt.f(input())'
   3
  / \
 1   5
  \ / \
  2 4 6
$ python conv.py [5,4,3,7,9] | python -c 'import bt; bt.f(input())'
   5
  / \
 4   7
/     \
3     9
$ python conv.py [1,2,3,4,5,6] | python -c 'import bt; bt.f(input())'
                               1
                                       \
                                               2
                                                   \
                                                       3
                                                         \
                                                           4
                                                            \
                                                             5
                                                              \
                                                              6
$ python conv.py [6,5,4,3,2,1] | python -c 'import bt; bt.f(input())'
                                   6
                       /
               5
           /
       4
     /
   3
  /
 2
/
1

You are not actually creating the binary tree. Just printing the array as a binary tree. The output of ['1','2','3','4','5','6','7','8','9'] array is not what you showed. It should have 3 as a right child of 2 which is a right child of 1 which is a root element.

@Optimizer From the question: "The input will be provided as an argument to your function. I won't specify the exact structure of the tree, however it must be usable as an actual binary tree." I don't see a specific definition of the array format used.

The question originally is about printing a binary tree. Your outputs are not binary trees. Format of the array has nothing to do with it.

@Optimizer how are they not binary trees? From Wikipedia: a binary tree is a tree data structure in which each node has at most two children. Do any of the nodes have more than two children?

Ughh. I see now. I think there is a term misunderstanding here . Even in the initial examples, the output is of the format of binary search tree. And my bounty is also for a binary search tree only. Sorry for the confusion there.

I have updated the bounty rules. Though the final score will not increase, but a program to convert a normal array to an breadth first array representation of a binary search tree is also required now.

@Optimizer good enough now?

Yup. The trees look so nice now!

Ruby, 265 bytes
def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=2**(h-d)-1;c=2**d;if d>0;m=' '*(s+s/2)+'I'+' '*(s-s/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

The @proudhaskeller version, 269 bytes
def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=(z=2**(h-d))-1;c=2**d;if d>0;m=' '*(s+z/2)+'I'+' '*(s-z/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

Explaination
The verbose version:
def p(t)
  depth = Math.log(t.length, 2).floor
  i = -1
  j = []
  (0..depth).each do |d|
    s = 2 ** (depth-d)-1
    c = 2 ** d

    if d > 0
      m = ' '*(s+s/2) + '|' + ' '*(s-s/2)
      w = i
      1.upto(d) { m += ' ' + m.reverse }
      puts m.gsub(/\|/) { |o| t[w+=1] ? (w%2==0 ? '\\' : '/') : ' ' }
    end

    puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' '
  end
end

Example
n = nil
p([
  1, 2, 3, 4, 5,
  n, 7, 8, 9, 0,
  1, n, n, 4, 5,
  6, 7, 8, 9, 0,
  1, 2, 3, n, n,
  n, n, 8, 9, n,
  n
])

gives:
               1
          /         \
       2               3
    /     \               \
   4       5               7
 /   \   /   \           /   \
 8   9   0   1           4   5
/ \ / \ / \ / \         / \
6 7 8 9 0 1 2 3         8 9

(I haven't written the conversion script yet.)

your slashes aren't exactly in the middle

@proudhaskeller "round whichever way you want", I thought it looks cooler this way. You can replace s/2 with (s+1)/2 if you want.

No, the slashes in the first row aren't exactly in he middle, in this row this isn't a matter of rounding

@proudhaskeller If you replace s/2 with (s+1)/2 they are exactly in the middle, but I still prefer this way because it makes the leftmost and rightmost branches look round.

it is against the spec...

@proudhaskeller I fixed it for you :)

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

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


text:
Finding "sub-palindromes" 2: subsequences.
The same task as Finding "sub-palindromes" but instead of finding substrings you must find subsequences that are not substrings.
eg1:
input: "12131331"
output:
"11", "33", "111", "121", "131", "313", "333", "1111", "1331", "11311", "13331"
or
"11", "33", "111", "333", "1111", "11311", "13331"

eg2:
input: "3333"
output:
"33", "333"
or
(null)

Input is a string of printable ascii characters.
Output is a list of unique strings.
If a subsequence also appears as a substring it may be omitted.
Shortest code wins.

It may be omitted or it must be omitted? Header and details don't match.

@J B: may be omitted. Where is the mismatch?

@Eelvex "subsequences that are not substrings".  That part reads like substrings aren't allowed.

@J-B: Substrings are not allowed. What you may or may not omit is a subsequence that also appears as a substring. Take a look at the examples: "1331" is a subsequence "12 13 13 31 " but also a substring "1213 1331 " so you may omit it.

@Eelvex: look at it this way.  The example output includes "1331".  But "1331" is a substring.  Thus I don't understand why it's there, given that substrings are not allowed.

@J-B: Look at it this way: use sequence indexes instead of values. The sequence I'm referring to is "2367" while the sequence you are referring to is "4567". They are completely different but happen to have the same value so you may omit the sequence if it is easier to code it that way.

@J-B: When I say "subsequences that are not substrings" I mean the set of subsequences that does not include the subset of substrings. i.e. the relative complement of subsequences to substrings. I think the misunderstanding is that it might seem I mean the list of subsequences that is not common with the list of substrings.

@J-B: btw, you'are not allowed to print "3333" in the second example because there is no such subsequence; only a substring.

GolfScript, 39 characters
:^1/[""]\{`{1$\+}+%}/.&{..-1%=^@?0<&},`

Examples:
> "12131331"
["11" "333" "111" "13331" "13131" "1111" "11311"]

> "3333"
[]

Basic blocks of the code:
# Save input in variable
:^

# Build all possible subsequences of the input
1/[""]\{`{1$\+}+%}/

# Filter unique ones
.&

# Filter relevant palindromes
{.
  .-1%=   # check if palindrome
  ^@?0<   # check if sequence is no substring
  &       # and operation on both
},

# Format output
`

Haskell (119)
import Data.List
main=interact f
f a=show.nub.filter(\x->(not$isInfixOf a x)&&x==reverse x&&length x>1)$subsequences a

Isn't too difficult with a builtin subsequences and nub... :)

Golfscript (95)
);.{{(\a\:x;.{[x]\+}%+}:b;{.!{[$]}{b}if}:a;.a{..-1%=&},\{,}{(;}/{{,}{);}/}%{+}*-.&{`}%", "*}and

I haven't really tried to golf this further, it's just a combination of left overs.
The question is inconsistent. My program prints all palindromic subsequences that are not substrings. Hope this is OK.
Example 1:
echo "12131331" | ruby golfscript.rb subseq_not_substr.gs
"11", "111", "13331", "13131", "1111", "11311"

Example 2:
echo "3333" | ruby golfscript.rb subseq_not_substr.gs

Empty String Example:
echo "" | ruby golfscript.rb subseq_not_substr.gs

With uglier output formatting, eg [11 111 13331 13131 1111 11311], it could be made a bit shorter.

Any way of formatting the output list is ok. Make it shorter :)


text:
Modulo code golf
Write a function f(a,b) that returns a mod b given the constraints:

you can't use division in any way
f(a,b) is always positive, eg: f(-1,5) = 4
it performs reasonably well for values of ~10e50 for a and b

If division is disallowed, it WILL perform badly,because only repeated subtraction is left.

Subtraction is not so bad but you also have multiplication.

Can the second operand be negative as well?

@sepp2k: It's not a requirement so treat it as it suits you.

Haskell 36 35 (34? 33)
If I may call the function ? instead:
1234567890123456789012345678901234
a?b|a<0=(a+b)?b|a>b=(a-b)?b|0<1=a

Elseway:
f a b|a<0=f(a+b)b|a>b=f(a-b)b|0<1=a

Nice idea, but this does not meet the requirements as it does not work at all if a is negative (it will just return a unchanged).

@Sepp2k: Now it works.

Note that 0<1 is shorter than True

Could you try running this with input 10^50, 3? I'm pretty sure it wouldn't complete.

Perl, 62 bytes
Regex modulo
sub f{($a,$b)=@_;$_=1x$a;s/^(1{$b})+(1+)$/return length $2/e;}

Java Solution, 114 66 chars
Its now 66, thanks sepp2k!~
 int m(int x,int y){x=(x<0)?-(x*y-x):x;while(x>=y) x-=y;return x;}

This is 80 character if you remove the unnecessary whitespace. 73 if you also make the method non-static. 66 if you additionally make it package-private.

[:)] that was easy, thanks!.. I am so used to beautify the code oops!

I suggested an edit; discard it if you don't like it.

I dont know, If this is right place to ask this or not.. but I do not know how to strike off  (that must be easy.. idiot aman :P )

It's 64 by removing the whitespace at the start

And the whitespace after while(x>=y) is unnecessary

I know it has been 5.5 years, but you can golf it like this int m(int x,int y){for(x=x<0?-(x*y-x):x;x>=y;x-=y);return x;} (61 bytes)

Haskell (22)
Abuse of the rules, please don't downvote: Mathematically, the modulus may be arbitrary large, because all moduli are equivalent. Thus, you may also use this, it WILL always return a positive result:
1234567890123456789012
a?b|a<0=(a+b)?b|True=a

And it will also always satisfy the equation
a?b = c <-> n*b + c = a

For some integer n.

Ruby - 72 chars
f=->a,b{a==b&&0||a<b&&a+(a<0&&b||0)||(t=b;t<<=1until t>a;f[a-(t>>1),b])}

Uses recursion like a Binary Search to find the remainder.
Test
p f[106, 95]
p f[23, 2]
p f[-1, 5]
p f[20, 7]
p f[10**100, 3]
p f[4*10**200, 3123123]

11
1
4
6
1
823660

Brainfuck - 37 characters
,>,<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>.

Takes a and b as bytes from standard input. Outputs one byte. Does not meet criteria to work with arbitrary size numbers, but to do so in brainfuck would not be simple.

I'm torn.  The problem doesn't explicitely ask for arbitrary size integers, which would be a pain to implement in BF, that's for sure.  But you're not even close to performing "well" for e50, since you won't perform it at all.

The more I think about it, the more I think this is defensible. All you need to make it handle e50 is an implementation that works on arbitrarily large numbers. Those do exist. Then it is just a matter of defining efficiency. Since this performs a whole lot better than brainfuck's built in modulo operator, I say it passes that too.

I have no issue with the efficiency.  What got me started is that no BF implementation I know of would be able to run your code on anything close to e50.  The easy hurdle is the cell size, but implementations do exist that implement these as bignums.  The hard one is input.  I don't know of a single implementation that returns anything over 255, and can't conceive a reasonable one returning anything over 2^32.  You could always find one and read input over several operations, but your character count doesn't reflect that.  (publishing a new implementation for the the task is frowned upon)

Fair enough. I was assuming I had an implementation that allows an arbitrarily large bignum input. Failing to find (or be allowed to create) that, this submission probably does not meet the requirements. It definitely can't handle negative input anyways. But it is remarkably competitive in count for a BF program, even if it is not quite there.

Python 2, 35 bytes
f=lambda a,b:a if a<b else f(a-b,b)

Sadly, I can't use and/or short-circuiting here, so I have to do with one more byte.

This does not perform correctly for negative inputs.

@Quelklef It doesn't have to. It would have been nice to include negatives as well, since this is ½ trivial as of now, though.

I think I'm reading this differently than you. Either way, I guess you're right, since there's already an accepted answer

@Quelklef I read that comment as "you can treat negatives any way", which means that undefined behavior can occur as well.


text:
Power modulo golf.
Write a function f(a,b,c) that calculates a^b (mod c) in less than 10 seconds.

a, b < 10^100
c < 10000.

examples:
f(10^50, 10^50, 54123) = 46555
f(5^99, 10^99, 777) = 1

Inbuilt functions disallowed? (f=pow would work in Python).

Is division allowed in this one? What the input? Is it always positive?

He sets no more restrictions, so there should be no restrictions.

@Dogbert, @Juan: as FUZxxl said, there are no more restrictions; you can assume that the input is always positive if that helps you.

@Dogbert: I thought you meant pow(x,y) but now it's too late to take it back :)

dc 1 or 5 chars
In GNU dc, there is the operator |, doing exactly this. Quoted from the manual:

| Pops  three  values  and computes a modular exponentiation.  The first value popped is used as the reduction modulus; this  value must be a non-zero number, and should be an integer.  The second popped is used as the exponent; this value must be  a  non-negative  number,  and  any fractional part of this exponent will be ignored.  The third value popped is the base which gets exponentiated,  which should be an integer.  For small integers this is like the sequence Sm^Lm%, but, unlike ^, this command will  work with arbitrarily large exponents.

You may assign it to "function" as following:
[|]sf

(also 5 chars...) This assigns | to f. You may call it like lfx.

Python - 5 chars
f=pow

Test
>>> f(10**50, 10**50, 54123)
46555L
>>> f(5**99, 10**99, 777)
1L

On the one hand, it is implicit that build-in functions that exactly solve the problem should not be used; on the other hand, I learned a new option of pow.

Haskell, 65
Takes the liberty of taking the modulus only on set bits of binary b, but given the range constraints that won't be a problem.
f a b c|b==0=1|odd b=mod(a*f a(b-1)c)c|0<1=f(mod(a^2)c)(div b 2)c

Java 56 chars
My humble attempt with Java.
Object a(BigInteger...a){return a[0].modPow(a[1],a[2]);}

How to use :
a(new BigInteger("95"), new BigInteger("56"), new BigInteger("67"));

Haskell (54)
f a=g a a
g d a b c|b>0=g(mod(d*a)c)a(b-1)c|True=mod d c

This is my algorithm:

let d = a
while b > 0:

d <- (d*a)%c
b --

Return d%b

Not sure that algo can handle b=10^50 in less than 10 seconds.

Ruby, 15 bytes
->a,b,c{a**b%c}

Finishes in 0.114s for a=10, b=100, c=10000

Python 80 Characters
def f(a,b,c):
 x=1;y=a
 while b:
  if b%2:x=(x*y)%c
  y=(y*y)%c;b/=2
 return x%c

Nice solution but not "golfy" enough for an upvote.

PHP, 8 bytes
bcpowmod

You can assign the function name to a variable for 11 bytes:
$f=bcpowmod;

Note: bcpowmod requires libbcmath, which is built into PHP since version 4.0.4, but only enabled by default on Windows. On Linux you have to explicitly configure PHP with --enable-bcmath.


text:
Comparing powers.
Compare two numbers N1 = abc, N2 = def by constructing a function f(a,b,c,d,e,f) that:

returns 1 if N1 > N2
returns -1 if N1 < N2

Note: You are not required to return any value for any other relation between N1 and N2. e.g. when they are equal or when their relation is undefined (complex numbers).
other constrains:

all numbers are integers
a,b,c,d,e,f may be positive or negative but not zero.
|a|,|d| < 1000
|b|,|c|,|e|,|f| < 1010
running time less than few seconds

Examples:
f(100,100,100,50,100,100) = 1
f(-100,100,100,50,100,100) = 1
f(-100,99,100,50,100,100) = -1
f(100,-100,-100, -1, 3, 100) = 1
f(535, 10^9, 10^8, 443, 10^9, 10^9) = -1

This is code golf. Shortest code wins.

What about if they're equal, should it return 0? Or you assuming that there's no way that N1 will equal N2?

Can we get some sample input/outputs?

@Jonathan: I'm not specifying the "being equal" case on purpose. Do as you please. You may even assume that they are never equal.

@Dogbert: done.

|b|,|c|,|e|,|f| < 10^10 seems to contradict your last example

@belisarius: sorry ... fixed it.

@Eelvex. You should probably say that then. If there's an ambiguous case, then people are going to ask what you meant. And generally, giving requirements for a function which explicitly ignore the result of a valid set of inputs is not good. It may be fine for code golf, but even then, I'd suggest that it be explicitly stated that what the function returns in such cases is undefined.

@Jonathan-M: ok.

What should we do with, e.g. a=-1,b=2,c=-1?  Taking negative numbers to fractional powers isn't defined.

@Eelvex : exponentiation is not associative. Do you mean pow(a, pow(b, c)) < pow(d, pow(e, f)), or pow(pow(a, b), c) < pow(pow(d, e), f), or some combination of the two?

@roobs: The way it is written (abc) clearly implies pow(a, pow(b,c)).

@Keith: Fractional powers of negative integers give clear good old complex numbers. Since you can't directly compare complex numbers, you are not required to do anything. The problems states "return 1 if N1>N2; return -1 if N1<N2" so any other relation between N1, N2 is of no interest here. I'll update the question; thanks :)

@Eelvex, thanks for clarifying that, if only for me.

Could we maybe get some more testcases?

@Ventero: Sure; anything in particular?

@Eelvex: Not really, I'm just not entirely convinced yet my solution works, so any additional testcase would be great. ;)

@Eelvex, the specification for cases where the result isn't -1 or 1 is still vague. "You are not required to return any value" - does that mean I can raise an error / throw an exception? Or must I return a value, but I'm not constrained as to what that value is?

@Peter: Anything is ok. You should not expect input that gives anything else than strict, well defined inequality.

Mathematica, 110 chars
z[a_,b_,c_,d_,e_,f_]:=With[{g=Sign[a]^(b^c),h=Sign[d]^(e^f)},If[g!=h,g,g*Sign[Log[Abs[a]]b^c-Log[Abs[d]]e^f]]]

What kind of Mathematica do you use there and what magic incantation has to be used to actually get this to work? Putting the above into Mathematica 8 just yields »Syntax::bktwrn: "z(a_,b_,c_,d_,e_,f_)" represents multiplication; use "z[a_,b_,c_,d_,e_,f_]" to represent a function.« and »Syntax::sntxf: "z(a_" cannot be followed by ",b_,c_,d_,e_,f_):=sgn(ln(abs a)b^c-ln(abs d)e^f)".«

Fails the testcase 3,-3,3,-4,1,1, if I'm not completely mistaken (don't have Mathematica here, but Wolfram Alpha seems to agree).

Ok, got it to work now with z[a_,b_,c_,d_,e_,f_]:=Sign[Log[Abs[a]]b^c-Log[Abs[d]]e^f] which is considerably longer than what you have there, though. I probably am missing something here.

@Joey, I don't actually have Mathematica, so I was testing with the Wolfram Alpha interface. It appears that it's much more generous with what it accepts. Ah well - the priority is that @Ventero correctly points out a bug with the logic.

Will it "run in less than a few seconds" for z[535, 10^9, 10^8, 443, 10^9, 10^9]?

@Eelvex, yes - I timed it at 4 seconds using Wolfram Alpha to evaluate Sign[535]^((10^9)^(10^8))*Sign[Log[Abs[535]](10^9)^(10^8)-Log[Abs[443]](10^9)^(10^9)] and it's the expansion of logs to sufficient precision that's the potentially slow bit.

@Peter: Well, Wolfram Alpha runs on more than 10,000 cpus but OK :)

@Peter: I wish I could split the bounty but I can't; so, given that wolfram alpha reports errors when I try to evaluate your solution (eg. (-1)^(10^8)^(10^8)), I awarded it to Ventero.

Ruby 1.9, 280 227 189 171 characters
z=->a,b,c,d,e,f{l=->a{Math.log a}
u=->a,b{[a.abs,a][b&1]}
a=u[a,b=u[b,c]]
d=u[d,e=u[e,f]]
d*a<0?a<=>d :b*e<0?b<=>e :(l[l[a*q=a<=>0]/l[d*q]]<=>f*l[e*r=b<=>0]-c*l[b*r])*q*r}

I know this is a bit longer than the other solutions, but at least this approach should work without calculating abc, def, bc or ef.
Edit:

(279 -> 280) Fixed a bug when a**b**c < 0 and d = 1.
(280 -> 227) Removed an unnecessary check for a special case.
(227 -> 192) Removed some checks that aren't necessary with the given criteria (non-zero integers, no output necessary for complex values)
(192 -> 189) Due to all the other checks, I can safely calculate log(log(a)/log(d)) instead of log(log(a))-log(log(d)).
(189 -> 171) Simplified way to transform equivalent problems into one another.

Testcases:
z[100, 100, 100, 50, 100, 100] == 1
z[-100, 100, 100, 50, 100, 100] == 1
z[-100, 99, 100, 50, 100, 100] == -1
z[100, -100, -100, -1, 3, 100] == 1
z[535, 10**9, 10**8, 443, 10**9, 10**9] == -1
z[-1, -1, 1, 2, 2, 2] == -1
z[1, -5, -9, 2, -1, 2] == -1
z[1, -5, -9, 2, -1, 3] == 1
z[3, -3, 3, -4, 1, 1] == 1
z[-2, 1, 1, 1, 1, 1] == -1
z[1, 1, 1, -1, 1, 1] == 1
z[1, 1, 1, 2, 3, 1] == -1
z[1, 1, 1, 2, -3, 2] == -1
z[1, 1, 1, 2, -3, 1] == 1
z[-1, 1, 1, 1, 1, 1] == -1
z[2, 3, 1, 1, 1, 1] == 1
z[2, -3, 2, 1, 1, 1] == 1
z[2, -3, 1, 1, 1, 1] == -1

ShortScript, 89 bytes
{CP
$M^ η1 η2
$M^ ζ η3
↑Αζ
$M^ η4 η5
$M^ ζ η6
↔α>ζ↑Ζ1
↔α<ζ↑Ζ-1}

The implementation isn't exactly the described one, but it works.
This answer is non-competing, since ShortScript has been published after this challenge.

Python 2.6 (this doesn't actually work)
import cmath
g=cmath.log
f=lambda a,b,c,d,e,f:-1+2*((c*g(b)+g(g(a))-f*g(e)-g(g(d))).real>0)

today i learnt python has a complex log function. so, blindly double log both sides and look at the real component. works for 4 out of the 5 tests. not sure what's happening with the fourth one.
print f(100,100,100,50,100,100) == 1
print f(-100,100,100,50,100,100) == 1
print f(-100,99,100,50,100,100) == -1
print f(100,-100,-100, -1, 3, 100) == 1 # failure, sadness.
print f(535, 10^9, 10^8, 443, 10^9, 10^9) == -1

Well, it is that I messsed up the example that is wrong :/ Sorry ... fixing it...

my code still returns -1 for the fourth example wrong when a=100

Comparing just the real part is not correct.

yeah, that part was a stab in the dark. this is where i regret skipping that course in complex analysis

Python (99)
from math import*
from numpy import*
l=log
def f(a,b,c,d,e,f):return sign(l(a)*l(b)*c-l(d)*l(e)*f)

Fails on negatives.

Haskell, 44 characters
n True=1
n _=1-2
g a b c d e f=n$a^b^c>d^e^f

Runs under a second for all the test examples on my machine.

I have a supermachine from the future.

Also the machine code is highly optimized. Inspecting the compiled code, it does logarithms and other operations. The THC (Trinithis Haskell Compiler) is one smart compiler!!! Who said I had to use GHC or Hugs? In fact, I can provide real source code for my compiler which has a GHC dependency. It will output fast code for this source code even on /your/ machine. What's more, it will compile ANY Haskell program to the same degree of accuracy as the GHC (GHC is the backend).

@downvoters: I'll provide the whole source code this weekend (I won't be home for a while) for my compiler to prove to you that it runs quickly. Talking about language speed is nonsense, as it all boils down to the compiler/interpreter.

And I wasn't even talking about bullshit speed/efficiency. I was referring to how (BEFORE you edited the post and changed the function b to n) the type of function f was given by f :: (Ord a,       Num a,       Integral b2,       Integral (Bool -> t),       Integral b,       Integral b1) =>      a -> (Bool -> t) -> b -> a -> b1 -> b2 -> t Pretty strange stuff, huh?


text:
Crossword grid verification
Validate a proposed crossword grid.
Entries should be full programs that simply test a proposed grid
to determine if it meets a set of conditions for making crossword
solvers happy.
Input
The input will be the name of a file representing the crossword
grid. The input filename may be passed as an argument, on the
standard input, or by other conventional means other than
hardcoding.
Grid file format: The first line consists of two white-space
separated integer constants M and N. Following that line are M
lines each consisting of N characters (plus a new line) selected
from [#A-Z ]. These characters are interpreted such that '#'
indicates a blocked square, ' ' a open square in the puzzle
with no known contents and any letter an open square whose
containing that letter.
Output
The program should produce no output on valid grids and exit with
normal termination state. If the proposed grid fails, the program
should produce a diagnostic error message and exit with a
abnormal termination state (i.e. not 0 on unix) if this is
supported by your execution environment. The error message should
indicate both which condition for validity is violated and the
location of the offending square; you are free to chose the means
of conveying these facts.
Conditions for validity
Valid grids will have no answers (across or down) that are only 1
character long (extra credit for making the minimum length a
input parameter), and will exhibit the usual symmetry. The usual
symmetry means the crossword remains the same after (three
equivalent descriptions of the same operation):

reflection through it's own center
reflection both vertically and horizontally
180 degree rotation

Test input and expected output
Passes:
5   5
#  ##
#
  #
    #
##  #

Fails on short answer:
5   5
## ##
#
  #
    #
## ##

Fails on symmetry:
5   5
#  ##
#
  #
#   #
##  #

Aside
This is the second of several crossword related challenges. I
plan to use a consistent set of file-formats throughout and to
build up a respectable suite of crossword related utilities in
the process. For instance a subsequent puzzle will call for
printing a ASCII version of the crossword based on the input and
output of this puzzle.
Previous challenges in this series:

Crossword numbering

Does the symetry requirement also apply to the grid's known contents, or only to the structure (# or not #)?

Only to the structure of blocked and in-play squares.

Oh, this one already had a bounty. Bummer. Still, I think two answers are a bit few.

Center symmetry and 180°-rotation are the same thing - aren't they? But I don't see vertical, nor horizontal symmetry. But 90°-rotation.

Ruby - 215 207
t,*d=$<.map &:chop;n,d,e=t.size+1,(d*S=?#).gsub(/[^#]/,W=" "),->c,i{puts [c,i/n+1,i%n+1]*" ";exit 1}
0.upto(d.size-1){|i|d[i]==d[-i-1]||e[?R,i];d[i]==W&&(d[i-1]!=W&&d[i+1]!=W||d[i-n]!=W&&d[i+n]!=W)&&e[?L,i]}

Ungolfed:
h, *g = $<.map &:chop
w = h.size+1
g = (g*?#).gsub(/[^#]/," ")
error = ->c,i{ puts [c,i/w+1,i% w+1]*" "; exit 1 }
0.upto(size-1) { |i|
        error[?R, i] if g[i] != g[-i-1]
        error[?L,i] if g[i]==" " && (g[i-1]!=" " && g[i+1]!=" " || g[i-w]!=" " && g[i+w] != " ")
}

.
h, *g = $<.map &:chop

This basically removes the last char (line break) of each input line by calling the chop method on them, and returning an array of the results.
h takes the first element of this array and *g takes the rest. So we end up with the first line in h and the crossword grid lines in g.
g = (g*?#).gsub(/[^#]/," ")

g*?# joins (*) the array g with the "#" (?# is a character literal). This is the same as g.*("#"), or g.join("#"). Then every non # is replaced by a space.
For the symmetry check we just have to check if the char at every index is equals to the char at the opposite index in the string:
0.upto(g.size-1) { |i| if g[i] != g[g.size - i - 1]; error() }

In Ruby we can index strings from the end using negative indexes (starting from -1 instead of 0), so that g[-i-1] is the opposite of g[i] in the string. This saves a few chars:
0.upto(g.size-1) { |i| if g[i] != g[-i-1]; error() }

We can save a ; by using a conditional statement:
0.upto(g.size-1) { |i| error() if g[i] != g[-i-1] }

In the golfed version we can save a few more chars:
0.upto(g.size-1){|i|g[i]==g[-i-1]||error()}

In a previous version I used recursion for iterating over the string:
(f=->i{g[i]&&f[i+1]&&g[i]!=g[-i-1]&&error()})[0]

An out of bound access to g returns nil, so once g[i] returns nil, this stops the iteration.
Output format:
{ L | R } line-number column-number

L for length errors, and R for rotation error (so L 1 2 means length error at line 1, column 2)

Would you care to explain a little for those of us who don't speak ruby? I can see how you've removed any non-blacks from in-play squares, and how the answer length checking works (nice, BTW), but I'm not quite getting the symmetry check.

I see a problem here of how the width of the grid is determined - by taking the length of the 1st line. That is incorrect, it will only work on the example where that line is "5---5" (three spaces in the middle). If it was "5 5" it wont work!

Also i think there is a problem with "veritcal wrap-around", when going over the 1st row and looking one row down (+n) and one row up (-n) - the latter will look in the last row and may mistakenly pick-up space from there!

Well you are right for the width of the grid; I assumed that on the first line, the second number is always aligned to the end of the line.

Reference implementation
c99
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int isSymmetric(int m, int n, char g[m][n]){
  for (int i=0; i<m; ++i)
    for (int j=0; j<n; ++j)
      if ( (g[i][j]=='#') != (g[m-i-1][n-j-1]=='#') )
    return j*m+i;
  return -1;
}

int isLongEnough(int m, int n, char g[m][n], int min){
  /* Check the rows */
  for (int i=0; i<m; ++i) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int j=0; j<n; ++j) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == j-1) && (j-lb <= min+1) ) return lo*m+i;
    lb=j;
      } else {
    /* In-play square */
    lo=j;
      }
    }
  }

  /* Check the columns */
  for (int j=0; j<n; ++j) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int i=0; i<m; ++i) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == i-1) && (i-lb <= min+1) ) return lo*m+i;
    lb=i;
      } else {
    /* In-play square */
    lo=i;
      }
    }
  }

  /* Passed */
  return -1;
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;
  int min=1;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the minium
         answer length */
    if ( (min=atoi(argv[2]))<1 ) {
      fprintf(stderr,"%s: Minimum length '%s' too short. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Verify crossword grid.\n\t%s <grid file> [<minimum length>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0,e=-1;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

  readgrid(inf,m,n,grid);

  if ((e=isSymmetric(m,n,grid))>=0) {
    fprintf(stderr,"Symmetry violation at %d,%d.\n",e/m+1,e%m+1);
    return 4;
  } else if ((e=isLongEnough(m,n,grid,min))>=0) {
    fprintf(stderr,"Short answer at %d,%d.\n",e/m+1,e%m+1);
    return 8;
  }
  return 0;
}

C, 278 chars
char*f,g[999],*r=g;i,j,h,w;main(e){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(g+h*w,99,f);++h);
for(;j++<h;)for(i=0;i++<w;++r)if(e=*r==35^g[g+w*h-r-1]==35?83:
*r==35||i>1&r[-1]!=35|i<w&r[1]!=35&&j>1&r[-w]!=35|j<h&r[w]!=35?0:76)
exit(printf("%d%c%d\n",j,e,i));exit(0);}

As you might expect, the error messages have themselves been golfed. They take the following form:
11L8 - indicates a length error at row 11 column 8
4S10 - indicates a symmetry error at row 4 column 10

APL (115)
{∨/,k←⍵≠⌽⊖⍵:'⍉',(,k×⍳⍴k)~⊂2/0⋄×⍴d←(,⊃,/(g(⍉g←⍳⍴⍵))×{k↑1⌽1⊖0 1 0⍷¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵}¨⍵(⍉⍵))~⊂2/0:'∘',d}d↑↑{'#'≠⍞}¨⍳⊃d←⎕

If the grid is not symmetrical, it outputs ⍉ followed by the coordinates, i.e. for the example it gives ⍉ 2 5  4 1
If the grid has short answers, it outputs ∘ followed by the coordinates, i.e. for the example it gives ∘ 1 2  5 2
Explanation:

d↑↑{'#'≠⍞}¨⍳⊃d←⎕: read the first line as a list of numbers and store in d, then read as many lines as the first number, and reshape as a matrix of size d. 'Closed' squares are stored as 0 and 'open' squares as 1.
∨/,k←⍵≠⌽⊖⍵: store in k the places where the grid is asymmetrical. If there is such a place...
'⍉',(,k×⍳⍴k)~⊂2/0: output a ⍉ followed by the offending coordinates
⋄: otherwise...
~⊂2/0: remove the zero coordinates from the following list:
¨⍵(⍉⍵): for both the grid and its transpose...
¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵: surround the grid with  zeros (i.e. closed squares)
0 1 0⍷: see where it contains an 'open' square enclosed by two 'closed' squares (= too short)
k↑1⌽1⊖: remove the ring of extra zeros again
,⊃,/(g(⍉g←⍳⍴⍵))×: multiply by coordinates and transposed coordinates, and join together, to form a list of offending coordinates (and a lot of zeros which we remove).
×⍴d←: store the offending coordinates in d, and if there are any...
:'∘',d: output a ∘ followed by the coordinates.


text:
Square free Numbers
Given a number N, write the shortest complete program to find the number of square-free integers below N.
Sample Input
100000
Sample Output
60794

Constraints:

Should work for all positive N below 1,000,000
Should not take more than 10 secs.
Please do not use built in functions, please.

What do you mean with no builtin functions? If I use haskell, I might not even use + or * - they all are functions.

@fuzxxl No you can use them, but no functions that directly give you the answer to the question like in Mathematica.

Basically a copy of the following endless problem on anagol (that one has the limit fixed at 500): http://golf.shinh.org/p.rb?Square+free+integer.

@nabb Aha! I did not know about it. Anyways it is not against the spirit of analog.

J, 21 chars
+/(]=&#~.)@:q:"0>:i.N

Checks for each integer from 1 to N if any prime factor appears more than once.
eg:
+/(]=&#~.)@:q:"0>:i.10000
 6083
+/(]=&#~.)@:q:"0>:i.100000
 60794

Takes ~3secs for N=1,000,000 (@2GHz,1core)

I'm not sure if it existed before but as of J 6.02, there is the ~: verb known as NubSieve which returns a mask based on the input array where each index is 1 the first time it appears and 0 if it appears again. This allows for a solution using 18 bytes as [:+/*/@~:@q:@>:@i..

Python 2: 71 chars
i=n=input()
A=[1]*n
while~-i:A[i*i::i*i]=~-n/i/i*[0];i-=1
print~-sum(A)

Basically an optimization of Keith Randall's solution of zeroing out numbers that are multiples of squares. The main improvement is directly zeroing out the sublist A[i*i::i*i], which requires awkwardly calculating its length or else Python refuses to do the slice assignment.
Lots of ~- are used for -1. The ~-sum(A) corrects for 0 being falsely counted as a squarefree number.

Python, 84 characters
n=input()
R=range(n)
A=[1]*n
for i in R[2:]:
 for x in R[::i*i]:A[x]=0
print sum(A)

Java Solution
import java.io.*;
    public class Main{
            public static void main(String[] args)throws Exception {
              int N=Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
              int list[]=new int[N];
    for (int i=0;i<N;i++){
    list[i]=(i+1);
    }
    for (int i=1;i<N;i++){
    if (Math.sqrt(list[i])-Math.floor(Math.sqrt(list[i]))==0){
    for(int j=i;j<N;j+=(i+1)){
    list[j]=-1;
    }}}
    int c=0;
    for (int i=0;i<N;i++){
    if (list[i]!=-1){
    c++;
    }}System.out.println(c);}}

IDEONE  http://ideone.com/Yf467

Hope using sqrt is fine?

The question says complete program.

:(   that costed me a lot of characters :(

It's almost a crime to golf in Java. :)

Python - 105 bytes
s=input()
C=set()
for q in [k*k for k in range(2,s+1)]:
 i=1
 while q*i<=s:C.add(q*i);i+=1
print s-len(C)

APL (Dyalog Extended), 11 bytes
+/≡∘∪⍨⍤⍭¨⍤⍳

Try it online!
Bubbler's tacit form. (-4 bytes)
-1 byte from Adám.
APL (Dyalog Extended), 16 bytes
{+/{(⊢≡∪)⍭⍵}¨⍳⍵}

Try it online!
Same approach as the J answer, 100000 runs under 10 secs on tio, so it should be all good.
Explanation
{+/{(⊢≡∪)⍭⍵}¨⍳⍵}
   {(⊢≡∪)⍭⍵}     square-free checking function
   {     ⍭⍵}     prime factors of ⍵
    (⊢≡∪)        are the unique values equal to the originals?
                 function ends
            ¨⍳⍵  map function to range 1-n
 +/              sum the resulting boolean array

Tacit 12 bytes.

(⊢≡∪) → ≡∘∪⍨

Wolfram Language (Mathematica), 24 bytes
Count[√Range@#,_^_|1]&

Try it online!
SquareFreeQ is too long anyways.

Ruby - 119 114
I=gets.to_i
m=[]
(s=->i{(I>i*i)?s[i+1]+[i*i]:[]})[2].map{|s|(1..I).map{|x|s*x<I||break;m<<s*x}}
p ([*1...I]-m).size

Try using ((a=*1...I)-m).size in the last line.

C 144 Chars
#define m 1000001
x[m];
main(s,o,f){
for(o=2;o*o<m;o++)
for(f=s=o*o;f<m;f+=s)x[f]=1;
scanf("%d",&f);
for(s=0,o=1;o<f;o++)if(!x[o])s++;
printf("%d",s);
}

Instantaneous Solution on my crummy PC! :)

Java - 278 Characters
A golfed version of the Java answer already demonstrated here without changing the spirit of the answer, because the original poster's idea golfed could have saved 50%, which is huge compared to most other languages!
class T {public static void main(String[] a) {int n,i,j;double k;n=Integer.parseInt(a[0]);int l[]=new int[n];for(i=0;i<n;)l[i]=1+i++;for (i=1;i<n;i++) {k=Math.sqrt(l[i]);if(k==Math.floor(k))for (j=i;j<n;j+=i+1)l[j]=-1;}j=0;for(i=0;i<n;)if(l[i++]!=-1)j++;System.out.println(j);}}

Specifically, a few Java golfing tricks were used to optimize this:

Removed long variable names
Removed the use of a Reader in favor of using an argument (saves a huge amount of characters, including import, Exception handling, and casting the reader in general)
Removed extra brackets and parentheses using single-line actions for ifs and fors where applicable
Declare ints beforehand together to reduce calls to int
Declare a double and optimize square calculation
Extracted ++ where possible

This shows that the original ungolfed solution of 565 characters can be brought down to a very respectable <300 character answer even with a more structured language like Java.
Ungolfed
class T {
    public static void main(String[] a) {
        int n, i, j;
        double k;
        n = Integer.parseInt(a[0]);
        int l[] = new int[n];
        for (i = 0; i < n;)
            l[i] = 1 + i++;
        for (i = 1; i < n; i++) {
            k = Math.sqrt(l[i]);
            if (k == Math.floor(k))
                for (j = i; j < n; j += i + 1)
                    l[j] = -1;
        }
        j = 0;
        for (i = 0; i < n;)
            if (l[i++] != -1)
                j++;
        System.out.println(j);
    }
}

Can be 272 with some stray whitespace removed. I think you can use (int)k instead of Math.floor(k), bringing the total down to 265.

@DLosc I got a can't cast String to int when I did that. Would have if I could :(

Huh... even though k is a double? I don't really know Java, but that just seems odd to me.

@DLosc I'll check again tomorrow. Maybe I'm confused.

GNU coreutils, 44 bytes
seq $1|factor|sed '$d;/\( .*\)\1\b/d'|wc -l

This factors every number up to N, removes the last line (as we're only counting results strictly less than N), and removes any line with a repeated word.  Finally, we count the remaining lines.
The regular expression \( .*\)\1\b looks over-generous, but it takes advantage of what we know about the output of factor - the factors will be in ascending order, with exactly one space between each.
With N=1,000,000, this completes on my machine in about ¼ second.

Japt -x, 8 bytes
õ_=k)eZâ

Try it
õ_=k)eZâ     :Implicit input of integer U
õ            :Range [1,U]
 _           :Map each Z
  =          :  Reassign to Z
   k         :  Prime factors of Z
    )        :  End reassignment
     e       :  Test equality with
      Zâ     :  Z deduplicated
             :Implicit output of sum of resulting array

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


text:
Carmichael Numbers
Write a program to print Carmichael numbers. The challenge is to print the maximum number of them in less than 5 secs. The numbers should be in increasing order. Please do not use built in functions. Also please don't store the carmichael numbers in any form. To keep a common time measurement use Ideone. The program to print the maximum number of Carmichael number wins.
Sample Output
561
1105
1729
2465
2821
6601
8911
.
.
.

OEIS A002997

@JB: I for one usually accept the shortest answer only after a week or so. Also I doubt that this site will be that acceptance-heavy as SO.

10 seconds seems an awfully short time for this problem.  Unless you hardcode the answer...

Is multi-threading allowed?

I’m voting to close this question because online services aren't valid for fastest code due to connection and server differences.

@emanresuA This contradicts https://codegolf.meta.stackexchange.com/q/12707/46076, which says that they aren't a good choice for timing, but doesn't explicitly disallow them. (And I don't see any distinguishing factor between ideone and TIO)

@TheFifthMarshal Oh. Never mind then.

Python
This generates 1332 Carmichael numbers in under 5 seconds.  Remove the print to actually get ideone to run to completion.
N=180000

maxprime = 18*N+1
prime = [1]*maxprime
prime[0] = prime[1] = 0
for i in xrange(maxprime):
  if prime[i]:
    for j in xrange(2*i,maxprime,i):prime[j]=0

for i in xrange(N):
  a=6*i+1
  b=12*i+1
  c=18*i+1
  if prime[a] and prime[b] and prime[c]:print a*b*c

Note that you could make this a whole lot faster in C.

You are printing Carmichael numbers only of a particular type.

Indeed I am....

unGolf3D dear Java :) maxCount=1193221 (at my local) and 552721 (at ideone) in 4.8s
    public class Main{
    public static void main(String[] args){
          long start=System.currentTimeMillis();
          int N=1200000;
          int list[]=new int[N];
            for (int i=0;i<N;i++) {
                list[i]=(i+1);
            }
            for (int i=1;i<N;i++) {
                if (Math.sqrt(list[i])-Math.floor(Math.sqrt(list[i]))==0) {
                    for (int j=i;j<N;j+=(i+1)){
                        list[j]=-1;
                    }
                }
            }
        boolean Carmichael=false;
        int chemCount=0;
        int product=1;
          for(int i=561  ;(System.currentTimeMillis()-start)/1000.0<=5;i++){
              if(!isPrime(i)&&list[i-1]==i){
                  for(int div=2;div<Math.sqrt(i);div++){
                      if(i%div==0 && isPrime(div)){
                          if((i-1)%(div-1)==0){
                              Carmichael= true;
                              product*=div;
                              chemCount++;
                              if (product==i) break;
                              }
                          else{
                              Carmichael=false;
                              break;
                              }
                      }
                  }
                  if (Carmichael && chemCount>=3 && product==i)
                      System.out.println(i);
                  Carmichael=false;
                   chemCount=0;
                   product=1;
              }
          }
  }

        static boolean isPrime(long number){
            if (number==2)
                return true;
            if (number==1)
                return false;
            for (long i=2;i<=Math.sqrt(number);i++) {
                if (number%i==0)
                    return false;
            }
            return true;
        }
    }

My JVM gets this to 1193221 number in 5 sec... I am sure this is slower than any other scripting languages and algo!! :( ...
OTOH, http://www.ideone.com/clone/oNJin fails to create this big process.. calculates upto 552721 in 4.8 sec and breaks after that throwing http://en.wikipedia.org/wiki/SIGXCPU :)

High complexity involved, Less Time, and on top Java!!

Please mention the number of Carmichael number it generates, rather than the maximum Carmichael number you found.

Oops  that's only 49 :(... I thought that we need to quote the max "challenge is to print maximum of them in less than 5 secs"

C++
Machine i5-760 @ 2.8Ghz, only one core used
Numbers found in 5 seconds: 129
#define WIN32_MEAN_AND_LEAN
#include <windows.h>
#include <iostream>
using namespace std;

bool IsPrime (int v)
{
  bool
    is_prime = true;

  for (int i = 3, i2 = 9 ; i2 < v ; ++i, i2 += i + i + 1)
  {
    if (v % i == 0)
    {
      is_prime = false;
      break;
    }
  }

  return is_prime;
}

int Prime (int i, int &i2)
{
  static int
    primes [10000] = {2, 3, 5},
    primes2 [10000] = {4, 9, 25},
    num_primes = 3;

  while (i >= num_primes)
  {
    int
      v = primes [num_primes - 1];

    do
    {
      v += 2;
    } while (!IsPrime (v));

    primes [num_primes] = v;
    primes2 [num_primes] = v * v;
    ++num_primes;
  }

  i2 = primes2 [i];
  return primes [i];
}

bool IsCarmichael (int n)
{
   if (n < 2)
   {
      return false;
   }

   int
     k = n--,
     i2 = 4;

   for (int i = 1, p = 2 ; i2 <= k ; p = Prime (i++, i2))
   {
      if (k % p == 0)
      {
         k /= p;

         if (k % p == 0 || n % (p - 1) != 0)
         {
            return false;
         }

         i = 0;
      }
   }

   return --k != n && n % k == 0;
}

int main ()
{
  DWORD
    end = GetTickCount () + 5000;

  int
    count = 0,
    n = 561;

  while (GetTickCount () < end)
  {
    for (int i = 0 ; i < 1000 ; ++i)
    {
      if (IsCarmichael (n))
      {
        ++count;
        cout << n << endl;
      }
      ++n;
    }
  }

  cout << count << " Carmichael numbers found out of " << (n - 561) << " values tested." << endl;
}

Can you fix it to run on ideone.com? e.g replace DWORD with unsigned.

D Language, 139 numbers, 18900973 max
Implemented Korselt's criterion to extract Carmichael numbers, considering only odd numbers greater than 3 since an even number cannot satisfy the relation.
Code
import std.stdio, std.math;

bool isCarmichael(uint n) pure nothrow @nogc {
   auto maxValue = ceil(sqrt(float(n)));
   uint cn = n;

   for (uint i = 3; i < maxValue; i += 2) {
      if (cn % i == 0) {
         cn /= i;

         if (cn % i == 0)
            return false;

         if ((n-1) % (i-1))
            return false;
      }
   }

   if (cn > 1)
      return false;

   return true;
}

void main() {
   for (uint n = 3; ; n += 2) {
      if (isCarmichael(n))
         writeln(n);
   }
}

Output
561
1105
1729
2465
2821
6601
8911
10585
15841
29341
41041
46657
52633
62745
63973
75361
101101
115921
126217
162401
172081
188461
252601
278545
294409
314821
334153
340561
399001
410041
449065
488881
512461
530881
552721
656601
658801
670033
748657
825265
838201
852841
997633
1024651
1033669
1050985
1082809
1152271
1193221
1461241
1569457
1615681
1773289
1857241
1909001
2100901
2113921
2433601
2455921
2508013
2531845
2628073
2704801
3057601
3146221
3224065
3581761
3664585
3828001
4335241
4463641
4767841
4903921
4909177
5031181
5049001
5148001
5310721
5444489
5481451
5632705
5968873
6049681
6054985
6189121
6313681
6733693
6840001
6868261
7207201
7519441
7995169
8134561
8341201
8355841
8719309
8719921
8830801
8927101
9439201
9494101
9582145
9585541
9613297
9890881
10024561
10267951
10402561
10606681
10837321
10877581
11119105
11205601
11921001
11972017
12261061
12262321
12490201
12945745
13187665
13696033
13992265
14469841
14676481
14913991
15247621
15403285
15829633
15888313
16046641
16778881
17098369
17236801
17316001
17586361
17812081
18162001
18307381
18900973

The code runs on a single core, without parallelism. No luck making it work on IDEONE though; time is checked on my machine running the process with timeout 5s UNIX command.

Rust
Naive brute force. It can be optimized more.
Run it on Rust Playground!
extern crate rand;

fn gcd(a: i128, b: i128) -> i128 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn power(mut a: i128, mut b: i128, m: i128) -> i128 {
    let mut result = 1;
    a %= m;
    while b > 0 {
        if b % 2 != 0 {
            result = (result * a) % m;
        }
        b >>= 1;
        a = (a * a) % m;
    }
    result
}

fn is_prime_miller_rabin(n: i128) -> bool {
    if n < 2 {
        return false;
    }
    if n != 2 && n % 2 == 0 {
        return false;
    }
    let s = ((n - 1) as u128).trailing_zeros() as i128;
    let d = (n - 1) / 2i128.pow(s as u32);

    let witnesses: [i128; 12] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
    'next_witness: for &a in witnesses.iter().take_while(|&&x| x <= n - 1) {
        let mut x = power(a, d, n);
        if x == 1 || x == n - 1 {
            continue;
        }
        for _r in 1..s {
            x = power(x, 2, n);
            if x == n - 1 {
                continue 'next_witness;
            }
        }
        return false;
    }
    true
}

fn fermat_test(n: i128) -> bool {
    for a in 2..n {
        if gcd(a, n) == 1 {
            if power(a, n - 1, n) != 1 {
                return false;
            }
        }
    }
    true
}

fn is_carmichael(n: i128) -> bool {
    !is_prime_miller_rabin(n) && fermat_test(n)
}

fn main() {
    let start = 561;
    let end = 100000;  // Adjust end limit based on time constraint
    for n in start..end {
        if is_carmichael(n) {
            println!("{}", n);
        }
    }
}

Python 3, 1184 numbers
Somewhat simplified implementation of Richard Pinch's methods (Carmichael numbers up to 10^21, Carmichael numbers up to 10^16).
The idea is to enumerate all the Carmichael numbers less than \$N\$. We can prove that none of them will have prime factors \$>\sqrt{N}\$, so we split into two cases based on the size of the largest prime factor (specifically if it is larger or smaller than \$N^{0.3}\$).
We'll let \$n\$ be the number, and \$q\$ it's largest factor. If there is a factor greater than \$N^{0.3}\$, then since \$\frac{n}{q}\equiv1\mod{q-1}\$, enumerating all possible values of \$\frac{n}{q}\$ given \$q\$ is \$\mathcal{O}\left(N^{0.4}\right)\$. So enumerate \$q\$ from \$N^{0.3}\$ to \$N^{0.5}\$, and test with a Fermat test to base 2 and Korselt's criterion.
In the other case, we use a depth first search on products of prime factors, where we can limit the branching factor to \$N^{0.3}\$.
Try it on ideone!
import math
from collections import deque
import itertools
# from gmpy2 import powmod as pow

def main():
    x = find_carmichael(5_000_000_000)
    for idx, i in enumerate(sorted(x), 1):# + len(s)):
        print(idx, i)

def find_carmichael(X):
    if X = q: return False
        x = i
        f.append(i)
    if len(f) >= 2:
        n1 = P*q-1
        return all(n1%(p-1)==0 for p in f)

def dfs(X, primes, n=1, t=(), i=0, lcm=1):
    if math.gcd(n, lcm) > 1: return
    if lcm * n * len(primes) > X:
        for Q in range(pow(n, -1, lcm), X//n + 1, lcm):
            if math.gcd(n, Q) > 1: continue
            N = n*Q
            if pow(2, N, Q) == 2:
                if is_carmichael0(n, Q, t):
                    yield N
        return
    for i1 in range(i, len(primes)):
        p = primes[i1]
        n1 = n*p
        if n1 > X: break
        if len(t) >= 2 and (n-1)%(p-1) == 0 and n1%lcm == 1:
            yield n1
        yield from dfs(X, primes, n1, t+(p,), i1+1, math.lcm(lcm, p-1))

def is_carmichael0(n, Q, t):
    x = 0
    f = list(t)
    for i in factor(Q):
        if i == x: return False
        if i in t: return False
        x = i
        f.append(i)
    if len(f) >= 3:
        n1 = n*Q-1
        return all(n1%(p-1)==0 for p in f)

class LazyList:
    def __init__(self, I):
        self.I = I
        self.l = []
    def __getitem__(self, i):
        try:
            return self.l[i]
        except IndexError:
            self.l.extend(itertools.islice(self.I, i+1 - len(self.l)))
            return self.l[i]
    def range(self, a, b=None):
        if b is None:
            a, b = 0, a
        for i in self:
            if i = b: break
            yield i

def primes_():
    yield 2
    l = [3,5,7,11,13,17,19,23]
    yield from l
    p2s = deque([(p, p*p) for p in l[2:]])
    n = 23
    stuff = [(0, 3), (4, 5)]
    while True:
        p2, next_p2 = p2s.popleft()
        R = range(n+4, next_p2, 2)
        z = [[] for _ in R]
        for i, p in stuff:
            z[i].append(p)
        stuff.clear()
        stuff.append((p2-1, p2))
        for i, (l, n) in enumerate(zip(z, R)):
            # print(i, l, n)
            if l:
                for p in l:
                    i1 = i + p
                    if i1 >= len(R):
                        stuff.append((i1 - len(R) - 1, p))
                    else:
                        z[i1].append(p)
            else:
                yield n
                p2s.append((n, n*n))

primes = LazyList(primes_())

def factor(n):
    for p in primes:
        while n%p == 0:
            yield p
            n //= p
        if p*p > n:
            if n > 1: yield n
            return

if __name__ == '__main__': main()

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


text:
Physics golf: inclined shooting
An angry bird is shot at an angle \$β\$ to the horizontal at a speed \$u\$. The ground is steep, inclined at an angle \$α\$. Find the horizontal distance \$q\$ that the bird traveled before it hit the ground.

Make a function \$f(α, β, u)\$ that returns the length \$q\$: the horizontal distance that the bird traveled before it hit the ground.
Constraints and notes:

\$-90° < α < 90°\$.
\$0° < β < 180°\$.
\$α < β\$.
\$0 \le u < 10^9\$.
Assume acceleration due to gravity \$g = 10\$.
You may use radians instead of degrees for \$α\$, \$β\$.
Dimensions of \$u\$ are irrelevant as long as they are consistent with \$g\$ and \$q\$.
No air resistance or anything too fancy.

Shortest code wins.
See the Wikipedia article on projectile motion for some equations.
Samples:
f(0, 45, 10) = 10
f(0, 90, 100) = 0
f(26.565, 45, 10) = 5
f(26.565, 135, 10) = 15

As I saw some confusion about the formula, here it is for others to use it: q = ABS[1/5 u^2 Cos[β] Sec[α] Sin[β - α]]

Java
Works for radians only
double q(double a, double b, double u){
          return (Math.abs(((-Math.tan(a)+(Math.tan(b)))*(u*u)*(0.2*(Math.cos(b)*Math.cos(b))))));
      }

Golfed Version (Thanks to Peter)
double z=u*Math.cos(b);return(Math.tan(b)-Math.tan(a))*z*z/5;

Maths Used:
$$
q = ut\cos \beta \\
q\tan \alpha = ut\sin \beta - 0.5 \times 10 t^2 \\
- \tan \alpha + \tan \beta  = 5\frac q {u^2} \sec^2 \beta \\
q = \frac {(\tan \beta - \tan \alpha)u^2} {5\sec^2 \beta }
$$

There is something wrong with this... I just cant figure out correctly, can some1 help?

This formula is not correct. Please see comment at gnibbler's post

So yet, we dont have any perfect solution :)

updated the formula...  fire some testcases now please

You can save a few chars - Math.abs is unnecessary, -x+y is shorter as y-x, *0.2 is shorter as /5, and you have unnecessary brackets. OTOH you're missing the return type of the method.

Thanks for return type :)   Was just curious on getting the answer than golfing..I would let this be as it is.. for readability purpose!

@Aman: I can't test it right now but it seems correct. There are some test cases in the problem description that you may try.

The testcases given seems to work fine (with small difference in answer, perhaps because of radians and PIs)

@Aman, IMO it's much more readable as return (Math.tan(b)-Math.tan(a))*u*u*Math.cos(b)*Math.cos(b)/10; The golfed version would be double z=u*Math.cos(b);return(Math.tan(b)-Math.tan(a))*z*z/10; (two chars shorter...)

lol, Come On Peter, anyway Java would loose a golfing compeition, But I like your idea, I will edit my post!

@Aman, oops, that should be /5, not /10. I blame a lack of coffee ;) But I'm serious about finding it more readable with fewer parentheses: when they're nested five or six deep it takes effort to pair them up.

[:p] edited....

Haskell (37 35)
Based on Aman's solution:
q a b u=(tan a+tan b)*u*u*cos b^2/5

I think, this problem isn't real code-golf, as it is more implementing a formula than really doing some algorithm.

Maybe you are right, since the formula is already too short.

Would something like /5 or /5. work?

This formula is not correct. Please see comment at gnibbler's post.

Python3 - 65 chars
from math import*
f=lambda α,β,u:(tan(α)+tan(β))*u*u*.2*cos(β)**2

That's not quite correct. 1) f should always be positive and 2) for α > 0 it returns a larger value than for a=0, which is not possible.

Ah well, I copied FUZxxl's formula :/


text:
How many switches are ON
A class has N student and the class room has N switches (all turned OFF and numbered 1 to N). Each student has an enrollment number assigned from 1 to N. Each student serially (by number) toggles the switches that has a number which is divisible by his/her enrollment number.
Example: Student 1 will turn all the switches ON. Student 2 will turn all even switches OFF. Student N just toggles the Nth switch.
Write a function that takes N as input as returns number of ON switches.
sample I/O
Input: 10
Output:3

No upper bound for N is given, but greater the scope, better the code. Shortest and innovative function wins

I think this is way too easy. Essentially this comes down as: »How short can I make an invocation of a library function«.

Well yes its easy when the trick is out.. without the perfect square trick, we cant be sure how different people would approach this problem.

This is a fairly well-known problem, I guess. At least I stumbled over it at least two or three times by now, mostly in programming contest contexts. And if you have two ways of approaching the problem with vastly different lengths, then you can be sure everyone will jump at the shorter one as soon as the first one does it.

@Joey, Totally agreed..

why did you accept the longest answer? even if you don't understand the others, this is not fair

@proudhaskeller If you look at the timestamps, you will notice that the OP seems to have accepted the first answer before any others were posted.

@Joey my answer no longer uses any (named) library functions ;)

Python, 19 characters
f=lambda n:n**.5//1

Perfect squares are the only numbers with an odd number of divisors.
This used to be a 21-character answer:
f=lambda n:int(n**.5)

but since I originally wrote it in 2011, the floor-division // operator was introduced, which can replace the int call.
As a consequence, the answer is now returned as a floating-point number. (But f(10) == 3.0 is still a correct number of lockers!)

I verified that this does work.  However, I would love to know why this works.

It works because every divisor of a number matches up with a different divisor, so they always come in pairs, producing an even number of divisors. The sole exception is if the number is a perfect square, in which case the square root of the number "pairs" with itself, producing an odd number of divisors.

There's a lovely post at dailywtf.com about this problem.

@st0le: http://thedailywtf.com/Articles/Nerds,-Jocks,-and-Lockers.aspx

Why is this accepted when all other answers are shorter?

@J B : Yes all other answers are shorter than this, The answer was accepted after 5 votes and no other solution by that time. More importantly, this funda could not hv been better!

in reply to a suggested edit for removing the f=: I choose to keep it there because otherwise you just create a lambda but watch it immediately vanish into the aether, unable to be called. you can choose to believe in your heart that it’s a 17-character solution!

@PaulFisher untrue; the _ variable gets automatically set to the last evaluated expression. running the lambda definition will set _ to be that lambda, therefore callable with _(n).

While that works in an interactive console, like ipython, it is not generally true in the context of a regular Python program.

dc - 5 chars
[v]sf

Square root in dc is v. Using stdin/stdout takes 3 chars (?vp)

J, 9 chars
(Just for a simple example on J)
f=:[:<.%:

floor (<.) of square root (%:)

But the correct answer is the floor, not the ceiling.

@Peter: right, "<." is floor actually. :/ Thanks.

Why not <.@%:? It also never says it has to be a named function, so that brings you down to 5.

@ɐɔıʇǝɥʇuʎs, this is from a time where this was debated (i.e. if J had to use a named verb when the question asked for a function). I don't know what the consensus is now. Also, since OP accepted a 21-char long answer, there is little point in golfing this.

Haskell - 12
Some text so that my post is long enough.
f=floor.sqrt

i like this because of the elegant use of the composition operator :)

TI-BASIC, 3
int(√(Ans

Or in Stuck (invalid, since it's from 2015):
i/)

Or in QWERTY Reverse Polish Notation (valid, from 2009):
@r[

Not an interesting answer, but I think they win, since I can't find a language that has either one-character integer square root or implicitly reads from input and performs the calculation in two bytes.

APL (Dyalog Extended), 2 bytes
⌊√

Floor of root of the input.
Try it online!, Verify 50 test cases

GS2, 2 bytes
V-

The two instructions are parse number, and integer square root, in order.
The reason this works is that the only switches that are on are perfect squares.  Those are the only numbers with an odd number of divisors.

+1—I spent about an hour looking for the correct language and couldn't find it. However, this language was written after the challenge, so it's technically not valid.

Oh, sorry, didn't realize this challenge was so old.

05AB1E, 2 bytes
tï

Try it online or verify the first N test cases.
Explanation:
t   # Square-root the (implicit) input-integer
 ï  # Cast it to an integer (a.k.a. floors)
    # (after which the result is output implicitly)

Java (JDK), 18 bytes
(int)Math.sqrt(n);

Try it online!
Java (JDK), 133 bytes
boolean[]a=new boolean[n];
int c,i=c=0;
for(;++i<=n;)
for(int j=0;++j<= n;)
a[j-1]=j%i==0?!a[j-1]:a[j-1];
for(boolean b:a)
c=b?++c:c;

Try it online!

I'm not sure if answers are allowed to take input from a pre-existing variable, you may want to check the default input/outputs allowed

I assumed that "Functions may take input via function arguments" meant that, in java, it would translate into "Method arguments"

I think what most Java answers do here is use a lambda, like n->(int)Math.sqrt(n);. It's only three extra bytes in most cases.

That would make sense. I haven't messed around with lambda in java but will try to do it in further "golfings" :)

Moonscript 23
Pretty simple and self-explanatory
s=(n)->math.floor(n^.5)

Math++, 6 bytes
_sqrt?

(Filler Text Because 30-char minimum)

Wren, 23 bytes
Basically square-root and floor.
Fn.new{|x|x.sqrt.floor}

Try it online!

Perl 5 -p, 9 bytes
$_=0|sqrt

Try it online!