text:
Fast Trig Calculation
Fast Trigonometry Calculations
Your task is to create a program which can calculate the sine, cosine and tangent of an angle in degrees.
Rules

No built-in trigonometry functions (not even secant, cosecant and cotangent if your language has them).
You may use lookup tables, but their total size must not exceed 3000 members (for all of the three operations put together). Please make it read the tables from a file (e.g. trig.lookup) so they don't confuse the code.
No network access.
You must correctly round your output as explained below. Don't use floor or ceiling.
You may use any method to calculate the values, for example continued fractions, as long as it is correct to 7 significant figures.
Your code must be able to time itself. Exclude the file I/O operations from your time - so just time the function(s) that do(es) the trig and any rounding.
I must be able to run your code. Please post a link to a freely available compiler/interpreter and give the instructions needed to compile/run the code (e.g. what options to pass to GCC).
Standard loopholes apply.

Input Format

Read from a file called trig.in unless your language doesn't support file I/O.
Angles are between 0 and 360 inclusive.
Input will consist of angles to ten significant figures in decimal digits, separated by new lines. For example:

90.00000000
  74.54390000
  175.5000000

Output Format

For each angle supplied, you must output its sine, cosine and tangent to 7 significant figures, separated by spaces, on a single line. Use "scientific notation", e.g. 1.745329E-5 for tan 0.001 or 1.000000E+0 for sin 90.
Denote infinity or NaN by n, for example the output for 90.00000000 should be 1.000000 0.000000 n.
If the input is three angles separated by newlines, your output should consist of three lines, each containing the sine, cosine and tangent.
You may not output anything else.
Output to a file called trig.out unless your language does not support file I/O.

Scoring

fastest-code. The challenge is to write a program which computes these three values as quickly as possible. Fastest time wins.
Everyone will receive the same test input of many angles.
Times will be recorded on my machine.
Your score is the average of three runs on the same input (you can't save anything in between runs obviously).
Compiling time not included. This challenge is more about the method used than the language. (If someone could point me to how I would exclude compilation time for languages such as Java, I'd be very grateful)
My machine is an Ubuntu 14.04 install. The processor's stats are on Pastebin (obtained by running cat /proc/cpuinfo).
I will edit your time into your answer when I've tested it.

Does the output have to be on a single line? It looks so pretty when it's formated with an enter key... Also, is there a specific date at which a winner is picked?

@Ephraim what do you mean by formatted with an enter key? no, there isn't a specific date. I really need to test all these solutions, but I haven't made the test input yet ;(

@professorfish - see the output in my answer. Every sin, cos and tan is on a new line. Do I need to change it to output the answers onto a single line?

@Ephraim The output format really doesn't matter (this isn't code-golf) as long as it outputs the sin cos and tan for every angle and they are separate

Does the output have to be rounded to 7 significant figures? or can it just be correct to that level?

@Ourous it has to be rounded

If you didn't have to significant figures precision requirements, I would use Bhaskara’s approximation for the Sine http://scholarworks.umt.edu/cgi/viewcontent.cgi?article=1313&context=tme — an incredible feat for the 7th century! The maximum error is −0.001631765 (downwards) and 0.0013436967 (upwards).

I can't use scientific notation and have output of 1.000000 0.000000 n at the same time. Also why are you so picky about how NaN is output?

Are we supposed to time only the trig calculations, or include the io in the timing?

Fortran 90
I employ the CORDIC method with a pre-tabulated array of 60 arctan values (see Wiki article for details on why that's necessary).
This code requires a file, trig.in, with all the values on newlines to be stored in the same folder as the Fortran executable. Compiling this is,
gfortran -O3 -o file file.f90

where file is whatever filename you give it (probably SinCosTan.f90 would be easiest, though it's not necessary to match program name and file name). If you have the Intel compiler, I'd recommend using
ifort -O3 -xHost -o file file.f90

as the -xHost (which doesn't exist for gfortran) provides higher level optimizations available to your processor.
My test runs were giving me about 10 microseconds per calculation when testing 1000 random angles using gfortran 4.4 (4.7 or 4.8 is available in the Ubuntu repos) and around 9.5 microseconds using ifort 12.1. Testing only 10 random angles will result in an indeterminable time using Fortran routines, as the timing routine is accurate to the millisecond and simple math says it should take 0.100 milliseconds to run all 10 numbers.

EDIT Apparently I was timing IO which (a) made the timing longer than necessary and (b) is contrary to bullet #6. I've updated the code to reflect this. I've also discovered that using a kind=8 integer with the intrinsic subroutine system_clock gives microsecond accuracy.
With this updated code, I am now computing each set of values of the trigonometric functions in about 0.3 microseconds (the significant digits in the end vary run-to-run, but it's consistently hovering near 0.31 us), a significant reduction from the previous iteration that timed IO.

program SinCosTan
   implicit none
   integer, parameter :: real64 = selected_real_kind(15,307)
   real(real64), parameter :: PI  = 3.1415926535897932384626433832795028842
   real(real64), parameter :: TAU = 6.2831853071795864769252867665590057684
   real(real64), parameter :: half = 0.500000000000000000000_real64
   real(real64), allocatable :: trigs(:,:), angles(:)
   real(real64) :: time(2), times, b
   character(len=12) :: tout
   integer :: i,j,ierr,amax
   integer(kind=8) :: cnt(2)

   open(unit=10,file='trig.out',status='replace')
   open(unit=12,file='CodeGolf/trig.in',status='old')
! check to see how many angles there are
   i=0
   do
      read(12,*,iostat=ierr) b
      if(ierr/=0) exit
      i=i+1
   enddo !-
   print '(a,i0,a)',"There are ",i," angles"
   amax = i

! allocate array
   allocate(trigs(3,amax),angles(amax))

! rewind the file then read the angles into the array
   rewind(12)
   do i=1,amax
      read(12,*) angles(i)
   enddo !- i

! compute trig functions & time it
   times = 0.0_real64
   call system_clock(cnt(1)) ! <-- system_clock with an 8-bit INT can time to us
   do i=1,amax
      call CORDIC(angles(i), trigs(:,i), 40)
   enddo !- i
   call system_clock(cnt(2))
   times = times + (cnt(2) - cnt(1))

! write the angles to the file
   do i=1,amax
      do j=1,3
         if(trigs(j,i) > 1d100) then
            write(tout,'(a1)') 'n'
         elseif(abs(trigs(j,i)) > 1.0) then
            write(tout,'(f10.6)') trigs(j,i)
         elseif(abs(trigs(j,i)) < 0.1) then
            write(tout,'(f10.8)') trigs(j,i)
         else
            write(tout,'(f9.7)') trigs(j,i)
         endif
         write(10,'(a)',advance='no') tout
      enddo !- j
      write(10,*)" "
   enddo !- i

   print *,"computation took",times/real(i,real64),"us per angle"
   close(10); close(12)
 contains
   !> @brief compute sine/cosine/tangent
   subroutine CORDIC(a,t,n)
     real(real64), intent(in) :: a
     real(real64), intent(inout) :: t(3)
     integer, intent(in) :: n
! local variables
     real(real64), parameter :: deg2rad = 1.745329252e-2
     real(real64), parameter :: angles(60) = &
       [ 7.8539816339744830962e-01_real64, 4.6364760900080611621e-01_real64, &
         2.4497866312686415417e-01_real64, 1.2435499454676143503e-01_real64, &
         6.2418809995957348474e-02_real64, 3.1239833430268276254e-02_real64, &
         1.5623728620476830803e-02_real64, 7.8123410601011112965e-03_real64, &
         3.9062301319669718276e-03_real64, 1.9531225164788186851e-03_real64, &
         9.7656218955931943040e-04_real64, 4.8828121119489827547e-04_real64, &
         2.4414062014936176402e-04_real64, 1.2207031189367020424e-04_real64, &
         6.1035156174208775022e-05_real64, 3.0517578115526096862e-05_real64, &
         1.5258789061315762107e-05_real64, 7.6293945311019702634e-06_real64, &
         3.8146972656064962829e-06_real64, 1.9073486328101870354e-06_real64, &
         9.5367431640596087942e-07_real64, 4.7683715820308885993e-07_real64, &
         2.3841857910155798249e-07_real64, 1.1920928955078068531e-07_real64, &
         5.9604644775390554414e-08_real64, 2.9802322387695303677e-08_real64, &
         1.4901161193847655147e-08_real64, 7.4505805969238279871e-09_real64, &
         3.7252902984619140453e-09_real64, 1.8626451492309570291e-09_real64, &
         9.3132257461547851536e-10_real64, 4.6566128730773925778e-10_real64, &
         2.3283064365386962890e-10_real64, 1.1641532182693481445e-10_real64, &
         5.8207660913467407226e-11_real64, 2.9103830456733703613e-11_real64, &
         1.4551915228366851807e-11_real64, 7.2759576141834259033e-12_real64, &
         3.6379788070917129517e-12_real64, 1.8189894035458564758e-12_real64, &
         9.0949470177292823792e-13_real64, 4.5474735088646411896e-13_real64, &
         2.2737367544323205948e-13_real64, 1.1368683772161602974e-13_real64, &
         5.6843418860808014870e-14_real64, 2.8421709430404007435e-14_real64, &
         1.4210854715202003717e-14_real64, 7.1054273576010018587e-15_real64, &
         3.5527136788005009294e-15_real64, 1.7763568394002504647e-15_real64, &
         8.8817841970012523234e-16_real64, 4.4408920985006261617e-16_real64, &
         2.2204460492503130808e-16_real64, 1.1102230246251565404e-16_real64, &
         5.5511151231257827021e-17_real64, 2.7755575615628913511e-17_real64, &
         1.3877787807814456755e-17_real64, 6.9388939039072283776e-18_real64, &
         3.4694469519536141888e-18_real64, 1.7347234759768070944e-18_real64]
     real(real64), parameter :: kvalues(33) = &
       [ 0.70710678118654752440e+00_real64, 0.63245553203367586640e+00_real64, &
         0.61357199107789634961e+00_real64, 0.60883391251775242102e+00_real64, &
         0.60764825625616820093e+00_real64, 0.60735177014129595905e+00_real64, &
         0.60727764409352599905e+00_real64, 0.60725911229889273006e+00_real64, &
         0.60725447933256232972e+00_real64, 0.60725332108987516334e+00_real64, &
         0.60725303152913433540e+00_real64, 0.60725295913894481363e+00_real64, &
         0.60725294104139716351e+00_real64, 0.60725293651701023413e+00_real64, &
         0.60725293538591350073e+00_real64, 0.60725293510313931731e+00_real64, &
         0.60725293503244577146e+00_real64, 0.60725293501477238499e+00_real64, &
         0.60725293501035403837e+00_real64, 0.60725293500924945172e+00_real64, &
         0.60725293500897330506e+00_real64, 0.60725293500890426839e+00_real64, &
         0.60725293500888700922e+00_real64, 0.60725293500888269443e+00_real64, &
         0.60725293500888161574e+00_real64, 0.60725293500888134606e+00_real64, &
         0.60725293500888127864e+00_real64, 0.60725293500888126179e+00_real64, &
         0.60725293500888125757e+00_real64, 0.60725293500888125652e+00_real64, &
         0.60725293500888125626e+00_real64, 0.60725293500888125619e+00_real64, &
         0.60725293500888125617e+00_real64 ]
    real(real64) :: beta, c, c2, factor, poweroftwo, s
    real(real64) :: s2, sigma, sign_factor, theta, angle
    integer :: j

! scale to radians
    beta = a*deg2rad
! ensure angle is shifted to appropriate range
    call angleShift(beta, -PI, theta)
! check for signs
    if( theta < -half*PI) then
       theta = theta + PI
       sign_factor = -1.0_real64
    else if( half*PI < theta) then
       theta = theta - PI
       sign_factor = -1.0_real64
    else
       sign_factor = +1.0_real64
    endif

! set up some initializations...
    c = 1.0_real64
    s = 0.0_real64
    poweroftwo = 1.0_real64
    angle = angles(1)

! run for 30 iterations (should be good enough, need testing)
    do j=1,n
       sigma = merge(-1.0_real64, +1.0_real64, theta <  0.0_real64)
       factor = sigma*poweroftwo

       c2 = c - factor*s
       s2 = factor*c + s
       c = c2
       s = s2
! update remaining angle
       theta = theta - sigma*angle

       poweroftwo = poweroftwo*0.5_real64
       if(j+1 > 60) then
          angle = angle * 0.5_real64
       else
          angle = angles(j+1)
       endif
    enddo !- j

    if(n > 0) then
       c = c*Kvalues(min(n,33))
       s = s*Kvalues(min(n,33))
    endif
    c = c*sign_factor
    s = s*sign_factor

    t = [s, c, s/c]
   end subroutine CORDIC

   subroutine angleShift(alpha, beta, gamma)
     real(real64), intent(in) :: alpha, beta
     real(real64), intent(out) :: gamma
     if(alpha < beta) then
        gamma = beta - mod(beta - alpha, TAU) + TAU
     else
        gamma = beta + mod(alpha - beta, TAU)
     endif
   end subroutine angleShift

end program SinCosTan

Finally, someone used CORDIC :D

I think that "-march=native" is the gfortran flag corresponding to ifort "-xHost". Also, I believe Intel has -O3 set to a more aggressive mode than gfortran, so you could try gfortran with "-O3 -fno-protect-parens -fstack-arrays" to see if it helps.

Also, you are timing the IO part as well, since you do read inside the loop. The rules specifically say you should not time IO. Fixing this gave quite the speedup on my computer: 0.37 microseconds per value, vs. 6.94 for your posted code. Also, the posted code does not compile, there's a trailing comma on line 100. There is also an error on line 23: trigs(i) should be just trigs. This makes the posted code segfault.

Improved version here: http://pastebin.com/freiHTfx

Update re: compiler options: -march and -fno-protect-parens did nothing, but -fstack-arrays shaved off another 0.1 microseconds per value. "ifort -O3 -xHost" is, remarkably, almost 2x slower than "gfortran -O3 -fstack-arrays": 0.55 vs. 0.27

@semi-extrinsic: Thanks for the catches. I was formatting some things between my copy & the one posted here and must have missed some things.

Strangely, my gfortran does not accept -fstack-arrays as an acceptable compiler flag (I have 4.4 natively, but do have a 4.8 installed now; it works on neither).

That's strange. I have 4.8.2, and compiling with "gfortran -O3 -march=native -fstack-arrays file.f90" works perfectly.

@KyleKanos How does the timing compare with the native Fortran functions if you do this for say, 10^6 random angles? You said it was indeterminate, but I'm curious, and maybe doing a lot more iterations would give better results.

Python 2.7.x or Java (Take your pick)
A free Python interpreter can be downloaded from here.
A free Java interpreter can be downloaded from here.
The program can take input both from a file named trig.in located in the same directory as the program file. Input is separated by newlines.
I originally did this in python because - well, I love python. But, since I wanna try to win as well, I rewrote it in java afterwards...
Python Version: I got about 21µs per run on my computer. I got about 32µs when running it on IDEone.
Java version: I get about 0.4µs per run on my computer, and 1.8µs on IDEone.
Computer specs:

Windows 8.1 update 1 64-bit with intel core i7-3632QM - 2.2GHz)

Test:

Time per run" is the cumulative time it takes to calculate the sin, cos, and tan all of the input angles.
The test input used for both is as follows:

90.00000000
74.54390000
175.5000000
3600000.000

About The Code:
The premise for this program was to estimate sin and cos using their Taylor polynomials with 14 terms, which was what I calculated was necessary to have an error estimate of less than 1e-8. However I found it was faster to calculate sin than cos, so decided to instead calculate cos by using cos=sqrt(1-sin^2)

Python Version:
import math
import timeit
import sys
import os
from functools import partial

#Global Variabls
pi2 = 6.28318530718
piover2 = 1.57079632679

#Global Lists
factorialList = [1.0,
                 -6.0,
                 120.0,
                 -5040.0,
                 362880.0,
                 -39916800.0,
                 6227020800.0,
                 -1307674368000.0,
                 355687428096000.0,
                 -121645100408832000.0,
                 51090942171709440000.0,
                 -25852016738884976640000.0,
                 15511210043330985984000000.0,
                 -10888869450418352160768000000.0,
                 8841761993739701954543616000000.0]

#simplifies angles and converts them to radians
def torad(x):
    rev = float(x)/360.0
    if (rev>1) or (rev<0):
        return (rev - math.floor(rev))*pi2
    return rev*pi2

def sinyield(x):
    squared = x*x
    for n in factorialList:
        yield x/n
        x*=squared

def tanfastdivide(sin, cos):
    if (cos == 0):
        return "infinity"
    return sin/cos

#start calculating sin cos and tan
def calcyield(outList):
    for angle in outList[0]:
        angle = torad(angle)
        sin = round(math.fsum(sinyield(angle)), 7)
        cos=math.copysign(math.sqrt(1-(sin*sin)),(piover2-angle))
        yield sin
        yield cos
        yield tanfastdivide(sin, cos) #tan

def calculations(IOList):
    calcyieldgen = calcyield(IOList)
    for angle in IOList[0]:
        IOList[1].append(next(calcyieldgen))
        IOList[2].append(next(calcyieldgen))
        IOList[3].append(next(calcyieldgen))
    return IOList

#Begin input from file
def ImportFile():
    try:
        infile = open("trig.in", "r")
    except:
        infile = sys.stdin
    inList = [[], [], [], []]

    #take input from file
    for line in infile:
        inList[0].extend([float(line)])
    return inList

#Begin output to file
def OutputResults(outList):
    try:
        outfile = open("trig.out", "w")
        PrintOutput(outList, outfile)
    except:
        print 'Failed to write to file. Printing to stdout instead...'
    finally:
        PrintOutput(outList, sys.stdout)

def PrintOutput(outList, outfile):
    #outList[0][i] holds original angles
    #outList[1][i] holds sin values
    #outList[2][i] holds cos values
    #outList[3][i] holds tan values
    outfile.write('-----------------------------------------------------\n')
    outfile.write('                    TRIG RESULTS                     \n')
    outfile.write('-----------------------------------------------------\n')
    for i in range(len(outList[0])):
        if (i):
            outfile.write('\n')
        outfile.write("For angle: ")
        outfile.write(str(outList[0][i]))
        outfile.write('\n    ')
        outfile.write("Sin: ")
        outfile.write(str('%.7E' % float(outList[1][i])))
        outfile.write('\n    ')
        outfile.write("Cos: ")
        outfile.write(str('%.7E' % float(outList[2][i])))
        outfile.write('\n    ')
        outfile.write("Tan: ")
        outfile.write(str('%.7E' % float(outList[3][i])))

#Run the Program first
inList = ImportFile()
OutputResults(calculations(inList))

#Begin Runtime estimation
def timeTest(IOList):
    for output in calcyield(IOList):
        pass
def baselined(inList):
    for x in inList:
        pass

totime = timeit.Timer(partial(timeTest, inList))
baseline = timeit.Timer(partial(baselined, inList))
print '\n-----------------------------------------------------'
print '                    TIME RESULTS:                    '
print '-----------------------------------------------------'
OverheadwithCalcTime =  min(totime.repeat(repeat=10, number=10000))
Overhead = min(baseline.repeat(repeat=1, number=10000))
estimatedCalcTime = (OverheadwithCalcTime - Overhead)
estimatedTimePerAngle = estimatedCalcTime/len(inList)
estimatedTimePerCalc = estimatedTimePerAngle/3
print ' Estimated CalcTime+Overhead:.....', '%.10f' % (OverheadwithCalcTime*100), 'µsec'
print ' Estimated Overhead Time:..........', '%.10f' % (Overhead*100), 'µsec'
print ''
print ' Estimated CalcTime/Run:..........', '%.10f' % (estimatedCalcTime*100), 'µsec'
print ' Estimated CalcTime/Angle:.........', '%.10f' % (estimatedTimePerAngle*100), 'µsec'
print ' Estimated CalcTime/Cacluation:....', '%.10f' % (estimatedTimePerCalc*100), 'µsec'
print '-----------------------------------------------------'
print "                   COOL, IT WORKED!                  "
print '-----------------------------------------------------'

Java Version:
import java.io.FileNotFoundException;
import java.io.File;
import java.io.PrintStream;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Scanner;
import java.lang.Math;

class Trig {
   /**
    *Global Variables
    **/
    static final double pi2 = 6.28318530718;
    public long totalTime = 0L;
    static final double piover2 = 1.57079632679;
    static final double plusinfty = Double.POSITIVE_INFINITY;
    static final double minusinfty = Double.NEGATIVE_INFINITY;
    static final double factoriallist[] =
                             new double[]{
                         -6.0,120.0,-5040.0,362880.0,-39916800.0,
                         6227020800.0,-1307674368000.0,355687428096000.0,
                        -121645100408832000.0,51090942171709440000.0,
                        -25852016738884976640000.0,
                         15511210043330985984000000.0,
                        -10888869450418352160768000000.0,
                         8841761993739701954543616000000.0
                         };
//Begin Program
    public static void main(String[] args) {
        Trig mytrig = new Trig();
        double[] input = mytrig.getInput();
        double[][] output = mytrig.calculate(input);
        mytrig.OutputResults(output);
        Trig testIt = new Trig();
        testIt.timeIt(input);
    }

//Begin Timing
    public void timeIt(double[] input) {
        double overhead = 0L;
        totalTime = 0L;

        for (int i = 0; i < 1000001; i++) {
            calculate(input);
            if (i == 0) {
                overhead = totalTime;
                totalTime = 0L;
            }
        }
        double averageTime = ((Double.valueOf(totalTime-overhead))/1000000.0);
        double perAngleTime = averageTime/input.length;
        double perOpperationTime = perAngleTime/3;
        NumberFormat formatter = new DecimalFormat("0000.0000");
        System.out.println("\n-----------------------------------------------------");
        System.out.println("                    TIME RESULTS:                    ");
        System.out.println("-----------------------------------------------------");
        System.out.println("Average Total  Runtime:.......... " + formatter.format(averageTime) + " nsec");
        System.out.println("                                = " + formatter.format(averageTime/1000) + " usec\n");
        System.out.println("Average Runtime Per Angle:....... " + formatter.format(perAngleTime) + " nsec");
        System.out.println("                                = " + formatter.format(perAngleTime/1000) + " usec\n");
        System.out.println("Average Runtime Per Opperation:.. " + formatter.format(perOpperationTime) + " nsec");
        System.out.println("                                = " + formatter.format(perOpperationTime/1000) + " usec");
    }

//Begin Input
    double[] getInput() {
        Scanner in;
        ArrayList<Double> input = new ArrayList<Double>();
        try {
            in = new Scanner(new File("trig.in"));
        } catch (FileNotFoundException e) {
            new FileNotFoundException("Failed to read from file. Reading from stdin instead...").printStackTrace();
            in= new Scanner(System.in);
        }
        while (in.hasNextLine()) {
            Double toadd = Double.parseDouble(in.nextLine());
            input.add(toadd);
        }
        in.close();
        double[] returnable = new double[input.size()];
        for(int i = 0; i < input.size(); i++) {returnable[i] = input.get(i);}
        return returnable;
    }

//Begin OutputStream Choice
    void OutputResults(double[][] outList) {
        PrintStream out;
        try {
            out = new PrintStream("trig.out");
            PrintOutput(outList, out);
            PrintOutput(outList, System.out);
        } catch (FileNotFoundException e) {
            new FileNotFoundException("Failed to write to file. Printing to stdout instead...").printStackTrace();
            PrintOutput(outList, System.out);
        }
    }

//Begin Output
    static void PrintOutput(double[][] outList, PrintStream out) {
        /**
         *outList[0][i] holds original angles
         *outList[1][i] holds sin values
         *outList[2][i] holds cos values
         *outList[3][i] holds tan values
         */
        NumberFormat formatter = new DecimalFormat("0.0000000E0");
        out.println("-----------------------------------------------------");
        out.println("                    TRIG RESULTS                     ");
        out.println("-----------------------------------------------------");
        for (int i=0; i<outList[0].length; i++) {
            out.println("For Angle: " + outList[0][i]);

            out.println("      sin: " + formatter.format(outList[1][i]));
            out.println("      cos: " + formatter.format(outList[2][i]));
            if (Double.valueOf(outList[3][i]).isInfinite() || Double.valueOf(outList[3][i]).isNaN()) {
                out.println("      tan: " + outList[3][i]);
            }
            else out.println("      tan: " + formatter.format(outList[3][i]));
        }
        if (out != System.out) out.close();
    }

//Begin Calculations
    double[][] calculate(double[] IOList) {
        double[][] outList = new double[4][IOList.length];
        double sin;
        double cos;
        double tan;
        double rads;
        int i = 0;
        long calctime = 0L;
        long startTime;
        long endTime;
        for (double input : IOList) {
            startTime = System.nanoTime();
            rads = toRad(input);
            sin=sin(rads);
            cos = ((piover2-rads)>=0) ? Math.sqrt((1.0-(sin*sin))) : -Math.sqrt((1.0-(sin*sin)));
            tan = (cos!=0.0d) ? sin/cos : ((sin>0) ? plusinfty : minusinfty);
            endTime = System.nanoTime();
            calctime = calctime + endTime - startTime;
            outList[0][i] = input;
            outList[1][i] = sin;
            outList[2][i] = cos;
            outList[3][i] = tan;
            i++;
        }
        totalTime = totalTime + calctime;
        return outList;
    }

//Convert Degrees to Radians
    double toRad(double deg) {
        double rev = deg/360.0;
        return (rev>1 || rev<0) ? Math.abs(rev - ((int)rev))*pi2 : rev*pi2;
    }

//Get sin
    double sin(double angle) {
        double sqr = angle*angle;
        double value = angle;
        for (double fct : factoriallist) {
            value += ((angle*=sqr)/fct);
        }
        return ((long)((value + Math.copySign(0.0000000005d, value))*10000000.0))/10000000.0;
    }
}

Your cosines are wrong for 180<x<360, and the program fails completely on 270.

@Ourous - I modified it, so it should work now in both languages.

You cos calculation is overkill, I'd just do sin(x+90degrees)

@Skizz - In my program, I use the word sin as both a function, and a variable. I thought it would be faster not to have to pass something to thesin() a second time, but I'll compare the two to see if that is really the case. Was your impression that copySign() function is slower that adding things up such as in my sin() function?

Ah, I see you're doing sin and cos at the same time. My comment would only really be valid if you were doing sin or cos.

Cobra
class Trig
    const mod as float = 0.0174532925199433f #0.0174532925199432957692369076848861271344287188854172f
    var time as System.Diagnostics.Stopwatch = System.Diagnostics.Stopwatch()
    var file as String[] = File.readAllLines('trig.in')
    var sin_out as float[] = float[](1)
    var cos_out as float[] = float[](1)
    var tan_out as float[] = float[](1)
    def main
        .compute(@[1f])
        .time.reset
        input = float[](.file.length)
        for num, line in .file.numbered, input[num] = float.parse(line)
        .compute(input)
        for num in .file.length, .file[num] = (.sin_out[num].toString('0.000000E+0') + ' ' + .cos_out[num].toString('0.000000E+0') + ' ' + .tan_out[num].toString('0.000000E+0'))
        File.writeAllLines('trig.out', .file)
        print .time.elapsed
    def compute(list as float[])
        .sin_out = float[](list.length)
        .cos_out = float[](list.length)
        .tan_out = float[](list.length)
        .time.start
        for index in list.length
            degrees as float = list[index]
            #add `degrees %= 360` for numbers greater than 360
            rad as float = sin as float = degrees * .mod
            two as float = rad * rad
            sin -= (rad *= two) / 6
            sin += (rad *= two) / 120
            sin -= (rad *= two) / 5040
            sin += (rad *= two) / 362880
            sin -= (rad *= two) / 39916800
            sin += (rad *= two) / 6227020800
            sin -= (rad *= two) / 1307674368000
            sin += (rad *= two) / 355687428096000
            sin -= (rad *= two) / 121645100408832000
            sin += (rad *= two) / 51090942171709440000f
            sin -= (rad *= two) / 25852016738884976640000f
            sin += (rad *= two) / 15511210043330985984000000f
            sin -= (rad *= two) / 10888869450418352160768000000f
            sin += (rad *= two) / 8841761993739701954543616000000f
            cos as float = (1 - (sin * sin)).sqrt * ((degrees - 180).abs - 90).sign
            if cos.isNaN, cos = 0
            .tan_out[index] = Math.round((sin / cos) * 10000000) / 10000000
            .sin_out[index] = Math.round(sin * 10000000) / 10000000
            .cos_out[index] = Math.round(cos * 10000000) / 10000000
        .time.stop

Compile it with cobra filename -turbo
Tests: AMD FX6300 @5.1GHz

The 360 * 10000 test used by the C answer runs in 365ms (vs 190ms)
The 4-entry test used by the Python and Java answers runs in 0.32µs (vs 30µs, 3µs)
The 1000 random angle test used by the Fortran answer runs at 100ns per angle (vs 10µs)

So apart from giving the wrong answer and being too slow, it's fine? :)

@Lembik It's now fixed.

do you realize you basically just wrote the same program in a different snake?

Octave (or Matlab) & C
A bit of a complicated build process, but kind of a novel approach and the results were encouraging.
The approach is to generate approximating quadratic polynomials for each degree. So degree = [0, 1), degree = [1, 2), ..., degree = [359, 360) will each have a different polynomial.
Octave - building part
Octave is publicly available - Google download octave.
This determines the best fit quadratic polynomial for every degree.
Save as build-fast-trig.m:
format long;
for d = 0:359
    x = (d-1):0.1:(d+1);
    y = sin(x / 360 * 2 * pi);
    polyfit(x, y, 2)
endfor

C - building part
This converts doubles in text format to native binary format on your system.
Save as build-fast-trig.c:
#include <stdio.h>

int main()
{
    double d[3];

    while (scanf("%lf %lf %lf", d, d + 1, d + 2) == 3)
        fwrite(d, sizeof(double), 3, stdout);

    return 0;
}

Compile:
gcc -o build-fast-trig build-fast-trig.c

Generating the coefficients file
Run:
octave build-fast-trig.m | grep '^ ' | ./build-fast-trig > qcoeffs.dat

Now we have qcoeffs.dat as the data file to use for the actual program.
C - fast-trig part
Save as fast-trig.c:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

#define INPUT    "qcoeffs.dat"

#define DEGREES    360

typedef struct {double a, b, c;} QCOEFFS;

double normalize(double d)
{
    if (d < 0.0)
        d += ceil(d / -(double)DEGREES) * (double)DEGREES;

    if (d >= (double)DEGREES)
        d -= floor(d / (double)DEGREES) * (double)DEGREES;

    return d;
}

int main()
{
    FILE *f;
    time_t tm;
    double d;
    QCOEFFS qc[DEGREES];

    if (!(f = fopen(INPUT, "rb")) || fread(qc, sizeof(QCOEFFS), DEGREES, f) < DEGREES)
    {
        fprintf(stderr, "Problem with %s - aborting.", INPUT);
        return EXIT_FAILURE;
    }
    fclose(f);

    tm = -clock();

    while (scanf("%lf", &d) > 0)
    {
        int i;
        double e, f;

        /* sin */
        d = normalize(d);
        i = (int)d;
        e = (qc[i].a * d + qc[i].b) * d + qc[i].c;

        /* cos */
        d = normalize((double)DEGREES / 4.0 - d);
        i = (int)d;
        f = (qc[i].a * d + qc[i].b) * d + qc[i].c;

        /* tan = sin / cos */

        /* output - format closest to specs, AFAICT */
        if (d != 0.0 && d != 180.0)
            printf("%.6e %.6e %.6e\n", e, f, e / f);
        else
            printf("%.6e %.6e n\n", e, f);
    }

    tm += clock();

    fprintf(stderr, "time: %.3fs\n", (double)tm/(double)CLOCKS_PER_SEC);

    return EXIT_SUCCESS;
}

Compile:
gcc -o fast-trig fast-trig.c -lm

Run:
./fast-trig < trig.in > trig.out

It will read from trig.in, save to trig.out and print to console the elapsed time with millisecond precision.
Depending on the testing methods used it may fail on certain input, e.g.:
$ ./fast-trig
0
-6.194924e-19 1.000000e+00 -6.194924e-19

The correct output should be 0.000000e+00 1.000000e+00 0.000000e+00. If the results are validated using strings, the input will fail, if they are validated using absolute error, e.g. fabs(actual - result) < 1e-06, the input will pass.
The maximum absolute error for sin and cos was ≤ 3e-07. For tan, because the result isn't limited to ± 1 and you can divide a relatively large number by a relatively small number, the absolute error could be larger. From -1 ≤ tan(x) ≤ +1, the maximum absolute error was ≤ 4e-07. For tan(x) > 1 and tan(x) < -1, the maximum relative error, e.g. fabs((actual - result) / actual) was usually < 1e-06 until you get in the area of (90 ± 5) or (270 ± 5) degrees, then the error gets worse.
In testing, the average time per single input was (1.053 ± 0.007) µs, which on my machine was about 0.070 µs faster than native sin and cos, tan being defined the same way.

C
Here's my attempt. It works like this:
Build a table of all values of sin(x) from 0 to 450 degrees. Equivalently this is all values of cos(x) from -90 to 360 degrees. With 2926 elements, there is enough space for a value every 1/6.5 degrees. The program unit is therefore 1/6.5 degrees, and there are 585 units in a quarter turn.
Convert input degrees into program units (multiply by 6.5==110.1 binary.) Find the nearest values for sin and cos from the table. then convert the remaining part of the input (dx) into radians.
apply the formula sin(x+dx) == sin x +(d(sin x)/dx)*dx. note that (d(sin x)/dx)==cos x, but only if we use radians.
unfortunately that isn't accurate enough on its own, so another term is required, based on the next derivative d2(sin x)/dx2 == -sin x. This needs to be multiplied by dx*dx/2 (not sure where the factor of 2 comes from, but it works.)
Follow the analogous procedure for cos x, then calculate tan x == sin x / cos x.
Code
There are about 17 floating point operations in here. That can be improved somewhat. The program contains table-building and test output using the native trig functions, but the algorithm does not. I will add timing and edit to comply with I/O requirements later (hopefully this weekend.) It matches the native function output except for very small values of sin x and cos x, which should be improvable to better than the native function output with some tweaking.
<#include <math.h>                                                 //only for table building and testing
int a;
double t[2926],                                                    //a table for sin x from 0 to 360+90=450deg every 1/6.5 degrees
x,                                                                 //input
s,c,                                                               //first guess sin and cos (from table)
sn,cs,                                                             //output sin and cos
pi1170=3.1415926535897932384626433832795/1170,                     // there are 1170 units of 1/6.5 degrees in a half circle
pi180=3.1415926535897932384626433832795/180;                       // pi/180 only used for testing

main(){
  for (a=0;a<=2925;a++)t[a]=sin(a*pi1170);                         //build table.

  scanf("%lf",&x);                                                 //input
  printf("%le %le %le\n",sin(x*pi180),cos(x*pi180),tan(x*pi180));  //native output for testing purposes

  x*=6.5;                                                          //convert from deg to program units. 6.5=110.1 in binary, a fairly round number.
  a=x+0.5;                                                         //a=round(x) add 0.5 to round, not truncate. Assigning to int, this is probably faster than the round function.
  x=(x-a)*pi1170;                                                  //(x-a)=dx in program units. Divide to get radians.

  s=t[a];                                                          //get sin(a) from table
  c=t[a+585];                                                      //cos(a)=sin(a+90degrees)=sin(a+585units)
  sn=s+c*x-s*x*x/2;                                                //sin(x+dx)=sin(x)+cos(dx)-sin(dx^2/2)
  cs=c-s*x-c*x*x/2;                                                //cos(x+dx)=cos(x)-sin(dx)-cos(dx^2/2)
  printf("%le %le %le\n",sn,cs,sn/cs);                             //print sin,cos and tan=sin/cos
}


text:
"KNOT" or "NOT"?
Write a program that processes an ASCII art representation of a tangled string and decides whether or not it can be untangled into a simple loop. The tangle is represented using the characters - and | to represent horizontal and vertical segments, and + to represent corners. Places where the string passes over itself are represented as follows:
            |                           |
         -------                     ---|---
            |                           |
(Horizontal segment on top)   (Vertical segment on top)

The ends of the string are connected together; there are no loose ends.
If your program decides that the string cannot be untangled into a simple loop, it should output the word KNOT. Otherwise, it should output the word NOT.
This is a code-golf challenge, so the shortest valid answer (measured in bytes of source code) will win.
Limits
The ASCII input will consist of up to 25 lines of 80 characters. You may assume that all the lines are padded with spaces to the same length.
Examples
Input:
+-------+    +-------+
|       |    |       |
|   +---|----+   +-------+
|   |   |        |   |   |
+-------|------------|---+
    |   |        |   |
    +---+        +---+

Output:
KNOT

Input:
+----------+
|          |
|    +--------------+
|    |     |        |
|    |   +-|----+   |
|    |   | |    |   |
|    +-----+    |   |
|        |      |   |
|        +------|---+
|               |
+---------------+

Output:
NOT

References

http://en.wikipedia.org/wiki/Knot_theory
http://en.wikipedia.org/wiki/Reidemeister_move
http://en.wikipedia.org/wiki/Unknotting_problem

+1 Great question.  Tempted to put a bounty on this one to encourage folks to jump into that knot theory.

Can we assume it's a knot (possibly the unknot) or can it be a link of >1 connected components?

@msh210 Yes, you can assume it's a single knot :-)

Python 3, 457 316 306 bytes
E=enumerate
V={'+'}
Q=[[(-j,i,k)for i,u in E(open(0))for j,v in E(u)for k in[{v}&V,'join'][u[j:j+2]=='|-']]]
while Q:
 a,b,c,d,*e=A=tuple(x//2for y,x in sorted((y,x)for x,y in E(Q.pop())));e or exit('NOT')
 if{A}-V:V|={A};Q+=[[c,d,a,b]+e,A,A[2:]+A[:2]][a<c<b<d:][c<a<d<b:]
 if b==d:Q=[[a,c]+e]
exit('KNOT')

Huh?
The program first converts the knot to a rectangular diagram, which has the following restrictions:

No two vertical or horizontal segments lie on the same line.
No vertical segment crosses over a horizontal segment.

For example, the first test case is converted to the following rectangular diagram:
+-----------+
|           |
|           | +-------+
|           | |       |
| +-------+ | |       |
| |       | | |       |
| |     +---+ |       |
| |     | |   |       |
| |     | +---+       |
| |     |             |
| |     |       +-------+
| |     |       |     | |
+-----+ |       |     | |
  |   | |       |     | |
  | +---+       |     | |
  | | |         |     | |
  | | +-------------+ | |
  | |           |   | | |
  | |           | +---+ |
  | |           | | |   |
  | |           | | +---+
  | |           | |
  +-+           | |
                | |
                +-+

which we uniquely represent by the sequence of y coordinates of the vertical segments, from right to left:
(5,10, 1,9, 8,10, 9,12, 5,12, 1,4, 0,3, 2,4, 3,7, 6,8, 7,11, 2,11, 0,6)

It then searches for simplifications of the rectangular diagram as described in Ivan Dynnikov, “Arc-presentations of links. Monotonic simplification”, 2004.  Dynnikov proved that from any rectangular diagram of the unknot, there is a sequence of simplifying moves that ends at the trivial diagram.  Briefly, the allowed moves include:

Cyclically permuting the vertical (or horizontal) segments;
Swapping consecutive vertical (or horizontal) segments under certain configuration constraints.
Replacing three adjacent vertices that lie in the very corner of the diagram with one vertex.

See the paper for pictures.  This is not an obvious theorem; it does not hold if, say, Reidemeister moves that do not increase the number of crossings are used instead.  But for the particular kinds of simplifications above, it turns out to be true.
(We simplify the implementation by only permuting vertical segments, but also allowing the entire knot to be transposed to interchange horizontal with vertical.)
Demo
$ python3 knot.py <<EOF
+-------+    +-------+
|       |    |       |
|   +---|----+   +-------+
|   |   |        |   |   |
+-------|------------|---+
    |   |        |   |
    +---+        +---+
EOF
KNOT
$ python3 knot.py <<EOF
+----------+
|          |
|    +--------------+
|    |     |        |
|    |   +-|----+   |
|    |   | |    |   |
|    +-----+    |   |
|        |      |   |
|        +------|---+
|               |
+---------------+
EOF
NOT
$ python3 knot.py <<EOF  # the Culprit
        +-----+
        |     |
+-----------+ |
|       |   | |
|   +-+ | +---|-+
|   | | | | | | |
| +-|-------+ | |
| | | | | |   | |
+-|-+ | | +---+ |
  |   | |       |
  +---|---------+
      | |
      +-+
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot
    +-----+
    |     |
  +-|---------+
  | |     |   |
  | | +-+ |   |
  | | | | |   |
+-|-|---|-|-+ |
| | | | | | | |
| | | +---|---+
| | |   | | |
+-------+ | |
  | |     | |
  | +-------+
  |       |
  +-------+
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot plus trefoil
    +-----+ +-----+
    |     | |     |
  +-|---------+   |
  | |     | | |   |
  | | +-+ | +---+ |
  | | | | |   | | |
+-|-|---|-|-+ +---+
| | | | | | |   |
| | | +---|-----+
| | |   | | |
+-------+ | |
  | |     | |
  | +-------+
  |       |
  +-------+
EOF
KNOT
$ python3 knot.py <<EOF  # Thistlethwaite unknot
      +---------+
      |         |
    +---+ +---------+
    | | | |     |   |
    | +-------+ |   |
    |   | |   | |   |
    |   | | +---+   |
    |   | | | |     |
    |   | +-------+ |
    |   |   | |   | |
    |   +-------+ | |
    |       | | | | |
+-----------+ | | | |
|   |         | | | |
| +-----------+ | | |
| | |           | | |
| | +-------------+ |
| |             |   |
| |             +-----+
| |                 | |
| |                 +---+
| |                   | |
+---------------------+ |
  |                     |
  +---------------------+
EOF
NOT
$ python3 knot.py <<EOF  # (−3,5,7)-pretzel knot
      +-------------+
      |             |
    +-|-----+       |
    | |     |       |
  +-|-+   +-------+ |
  | |     | |     | |
+-|-+   +---+   +---+
| |     | |     | |
| |   +---+   +---+
| |   | |     | |
| | +---+   +---+
| | | |     | |
| +---+   +---+
|   |     | |
|   |   +---+
|   |   | |
|   | +---+
|   | | |
|   +---+
|     |
+-----+
EOF
KNOT
$ python3 knot.py <<EOF  # Gordian unknot
+-------------+                 +-------------+
|             |                 |             |
| +---------+ |                 | +---------+ |
| |         | |                 | |         | |
| | +-------------+         +-------------+ | |
| | |       | |   |         |   | |       | | |
| | | +---------+ |         | +---------+ | | |
| | | |     | | | |         | | | |     | | | |
| +-------+ | +-------+ +-------+ | +-------+ |
|   | |   | |   | |   | |   | |   | |   | |   |
+-------+ | +-------+ | | +-------+ | +-------+
    | | | |     | | | | | | | |     | | | |
    | +-------+ | | | | | | | | +-------+ |
    |   | |   | | | | | | | | | |   | |   |
    +-------+ | | | | | | | | | | +-------+
        | | | | | | | | | | | | | | | |
        | +-----+ | | | | | | +-----+ |
        |   | |   | | | | | |   | |   |
        +---------+ | | | | +---------+
            | |     | | | |     | |
          +---------+ | | +---------+
          | | |       | |       | | |
          | | +-----------------+ | |
          | |         | |         | |
          | +---------------------+ |
          |           | |           |
          +-----------+ +-----------+
EOF
NOT

Wow, this is excellent.

Could you post an ungolfed version of your code?

Also, what's the time complexity of your program?

@JorgePerez I don’t have a separate ungolfed version; the best way to understand the program is to read Dynnikov’s paper that I linked. The complexity is something horribly exponential; as far as I know, whether a polynomial time algorithm exists is still an open problem.

source: Stack Exchange

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

sort: votes


text:
Solving a "Ubongo"-puzzle
Some time ago I came across a game called Ubongo. The player got four shapes and has to put them together in a way, that the shapes form the shape of the board. One example is this:

Note that the shapes can be turned or rotated.
Your goal is to write a programm that takes the board and the 4 shapes as parameter (command line or user input, handle it your way) and prints the solution (a graphical solution or a human-readable solution).
Example (same as above):
Input (board size, board information (0 for nothing, 1 for board field), 4x shape size and shape information (same as board information)):
>myprogram
5 5
11000
11000
11101
11111
00111
2 4
10
10
11
10
1 2
1
1
2 3
01
11
01
2 3
01
11
11

Output:
12000
12000
11304
13344
00344

(0 stands for nothing, 1 for the first shape given in the input, 2 for the second shape etc.)
Note that the choice of input and output is completely free, it should just be easy to understand.
The winner will be crowned two weeks from when the question was posted. The winner will be the person with the least code length.
EDIT :
You can assume that there is a solution to the given board and pieces. If there is no solution, your program does not have to work (but it would be nice if it prints an error message). For those, who need more tests, I found solutions to several puzzles with several boards and pieces here.

Can we assume that the input is guaranteed to be solvable?

@m.buettner Updated the challenge to code-golf only. But I still would like to add a bonus for esoteric programming languages. Any ideas for that? Also, the input should be solveable, because in the game you assume that too.

Can I take the input in array format? The example would be [5,5],[[1,1,0,0,0],[1,1,0,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,1,1,1]], [[[2,4],[1,0],[1,0],[1,1],[1,0]],[[1,2],[1],[1]],[[2,3],[0,1],[1,1],[0,1]],[[2,3],[0,1],[1,1],[1,1]]]

@Sirac If you want to add a bonus for esoteric programming languages, you'll need to change the tag to code-challenge. But I personally like this as a plain code golf. The terse esoteric languages are favoured here anyway.

Somewhat related.

More test cases please?

@TheRare As I said, the input format can be any way you like, but it should be understandable. Your format is no problem. Also, I found more test cases: http://www.kosmos.de/_files_media/mediathek/downloads/spieleloesungen/1160/ubongo_das_duell_1.pdf
http://www.kosmos.de/_files_media/mediathek/downloads/spieleloesungen/1160/ubongo_das_duell_2.pdf
http://www.kosmos.de/_files_media/mediathek/downloads/spieleloesungen/1160/ubongo_das_duell_3.pdf . I hope I could help you.

GolfScript, 210 characters
n%{(~\;/(\[]:f*}5*;].,,]zip{~{.!+`\1`/*n*~]}+%}%(:b{,:^1,*}%]({^,{[^1,*:e.@<\]`{\*^<}+1$%:a;b,:h,{[[e]h*.@<\]a*h<}/}%{.zip{.-1%.zip}3*}%.&`{{[[f*1$f*]zip{~+}%b f*]zip{~*}%^/}%~}+@%{1$f*0-.@f*@0={=}+,=},\;}/0=n*

This is a first attempt using GolfScript. Input must be given on STDIN in the same format as the example in the question. The output format results from an implementation error (using ascii values instead of numerics) but I left it in this form because it is short and looks nice.
☺☻
☺☻
☺☺♥ ♦
☺♥♥♦♦
  ♥♦♦

There might be some places where it can be golfed further. Maybe I can post an updated version tomorrow.

That output is sweet.

Python 2.x - 679 543 443 417 406 383 372 361 bytes
I'm actually pretty sad about this one. I am sure I missed something obvious. I'll be looking at this again later. Starting to feel good about this one.
543 - Edit 1: Discarding efficiency in favor of code length.
443 - Edit 2: Made the algorithm a lot simpler, fixed it (it couldn't handle flips) and
              removed ungolfed code because it wasn't relevant anymore.
417 - Edit 3: Rotate was only being used once anymore. Inlined it. Something else too.
406 - Edit 4: Made it accept only four shapes, as the spec says. Also reduced efficiency again.
383 - Edit 5: Ultimate abuse of exec. Shorter code and longer execution time!
372 - Edit 6: Every recursion now makes a copy of the current board, which is removed if
              the pieces don't fit. No more master board and no more emptying placed pieces.
361 - Edit 7: Removed unnecessary stuff. Also added the byte counts to changelog.

(q,g),O,s=input()
O=[x*6for x in sum(O,[])]
A='z,k=s[i];'+('z,k=z[::-1],zip(*k[::-1]);r=r or c(i+1,z,k,O);'*4+'k=map(reversed,k);')*2
def c(i,(w,h),p,o,r=0):
 for x in range(g*q):O=o[:];f=1;I=0;exec"P=x+I/w*q+I%w;exec('f=0','O[P]=i')[g*q>P>=0and O[P]>4]*p[I/w][I%w];I+=1;"*w*h;exec(i<4*f)*A;r=O*(i*f>3)or r
 return r
i=r=0;exec A+'print`r[i:i+q]`[1::3];i+=q;'*g

It takes the input in an array format. Example:
In:  [5,5],[[1,1,0,0,0],[1,1,0,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,0]]],[[1,2],[[1],[1]]],[[2,3],[[0,1],[1,1],[0,1]]],[[2,3],[[0,1],[1,1],[1,1]]]]
Out: 12000
     12000
     11304
     13344
     00344

In:  [6,5],[[0,1,1,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0],[0,1,1,1,1,0],[0,0,1,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,1]]],[[3,3],[[1,1,0],[0,1,1],[0,1,1]]],[[3,3],[[0,0,1],[1,1,1],[1,0,0]]],[[2,4],[[0,1],[1,1],[0,1],[0,1]]]]
Out: 033110
     223110
     223310
     022410
     004444 (thanks, edc65)

Quick explanation, if you can't read it. The function checks every possible position for a piece. Whenever the piece fits, it recursively checks that all other pieces fit too. When all pieces fit, the board is filled (pieces are placed on the board when checking) and it can be outputted straight away.

Nice code. And totally unfathomable to me.

Thanks! I'm just abusing exec to build loops by multiplying pieces of code,

Javascript (E6) 316 350 392 487 537 590
Board size limited to 6x6 to save runtime. With the same character count the limit could be 9x9. Any number of pieces
    F=(d,b,h)=>{R=s=>[...s].reverse(),Q=(n,i,k)=>{h[n]&&[t=h[n][1],t[0].map((c,i)=>t.map(r=>r[i]))].map(e=>[e,R(e),e.map(R),R(e).map(R)].map(s=>{for(i=36;i--;)k=b.map(x=>[...x]),s.some((u,q)=>!(w=b[~~(i/6)+q])||u.some((v,p)=>(c=i%6+p,v&&!(v=w[c]!=1)&&!(w[c]=n+2)||v)))||Q(n+1),b=k}))||console.log(b.join('\n'))},Q(0)}

History
316 - Slooower! The board is copied again for each recursive call. (Ab)using slower functions chosen for shorter names. The main loop on board rows and colums coalesced into one for. Also put a limit for board size up to 6x6 (not for short code, but for acceptable runtime)
350 - Golfed using more array traversing function and less loops
392 - Algorithm not changed: try to place a piece, if ok try next, recursive, but
use arrays only and not strings and use a single global board and not copy it during recursion (so it must be able to put a piece AND to remove it)
...
Ungolfed a bit
F = (d,b,h)=>{
  R = s => [...s].reverse(), // ... instead of slice that is faster
  Q = (n,i,k) => // Recursive function, fake param i to avoid vars
  {
    h[n] && // If there is still a piece to place, try to place it
    [t=h[n][1], t[0].map((c,i) => t.map(r => r[i]))]
      .map(e => // for e in :piece, transposed piece
        [e, R(e), e.map(R), R(e).map(R)]
        .map(s =>
          { // for s in : base piece, reversed, mirrored, diagonal
            for(i = 36; i--;) // 6x6: could be higher but slows down
              k = b.map(x=>[...x]), // save copy of board (again ... instead of slice)
              s.some( (u,q) => // traverse with 'some' to exit early if invalid position
                !(w=b[~~(i/6)+q])
                || u.some((v,p) => (c=i%6+p, v && !(v=w[c]!=1) && !(w[c]=n+2)||v))
              ) || Q(n+1), // if piece place, recurse
              b=k // recover the board from the copy
          }
      )) // if no more pieces, output result
    || console.log(b.join('\n' /** ,Q=_=>0 **/)) // remove comment to stop at first solution found
  },
  Q(0) // First call
}

Usage
Test in javascript console (Firefox)
Input parameters as array.
Time to finish is 50 sec on my PC, so Firefox will complain...
F(
[5,5],
[[1,1,0,0,0],[1,1,0,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,1,1,1]],
[
 [[2,4],[[1,0],[1,0],[1,1],[1,0]]],
 [[1,2],[[1],[1]]],
 [[2,3],[[0,1],[1,1],[0,1]]],
 [[2,3],[[0,1],[1,1],[1,1]]]
])

Another test case:
F(
 [6,5],
 [[0,1,1,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0],[0,1,1,1,1,0],[0,0,1,1,1,1]],
 [
  [[2,4],[[1,0],[1,0],[1,1],[1,1]]],
  [[3,3],[[1,1,0],[0,1,1],[0,1,1]]],
  [[3,3],[[0,0,1],[1,1,1],[1,0,0]]],
  [[2,4],[[0,1],[1,1],[0,1],[0,1]]]
 ]
)

Output / 2+2 solutions found, firefox console skip repeated console output
0,2,2,2,2,0
3,3,4,2,2,0
3,3,4,4,4,0
0,3,3,5,4,0
0,0,5,5,5,5

0,4,4,2,2,0
3,3,4,2,2,0
3,3,4,4,2,0
0,3,3,5,2,0
0,0,5,5,5,5

Thanks for the additional test case. Also, that code creeps me out.

@TheRare de nada.
The pseudo code is simple: try to put a shape, the board change, try next ... (like yours)
Thinking about a different implementation though

You passed me! Guess I have some work to do. ;)

Aaaand you won.

@TheRare Don't give up! I feel there is room for improvement using single dimension arrays (every two loops become one).

You know, I tried that, but flattening the array was painful. ,,, Actually, I just remembered an awesome way to do it.

Thanks for the reminder. It didn't help too much by itself, but I got other ideas while implementing 1D-array. Mainly, abusing exec even more. Cheers!

350? I'm impressed. Have a +1 for the hard work.

authors: Вера Андреева

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


text:
Fastest player for Dots and Boxes
The challenge is to write a solver for the classic pencil and paper game Dots and Boxes .  Your code should take two integers m and n as input which specifies the size of the board.

Starting with an empty grid of dots, players take turns, adding a
  single horizontal or vertical line between two unjoined adjacent dots.
  A player who completes the fourth side of a 1×1 box earns one point
  and takes another turn. (The points are typically recorded by placing
  in the box an identifying mark of the player, such as an initial). The
  game ends when no more lines can be placed. The winner of the game is
  the player with the most points.

You can assume that either n = m or n = m - 1 and m is at least 2.
The challenge is to solve the largest possible Dots and Boxes game in under a minute. The size of a game is simply n*m.   The output of your code should be win , draw or lose which should be the result for the first player assuming both players play optimally.
Your code must be compilable/runnable on ubuntu using easily installable and free tools.  Please report your score as the largest area you can solve on your computer in 1 minute together with the time.  I will then test the code on my computer and make a rank ordered table of entries.
In the case of a tie-break, the winner will be the fastest code on the largest size board it can solve in under a minute.

It would be better if the code outputted not just win or lose but the actual score as well. This makes for a sanity check of correctness.

Do we have to use minimax?

@qwr Can you let me know what other option you had in mind?

Wait, there's a predictable winner in this game based solely on grid size?

@Charles Yes if both players play optimally.

Some discussion on representations in the chatroom.

If I place a line which completes two boxes, do I get one extra turn or two?

@PeterTaylor I think you get two points but only one extra turn.

Please clarify the meaning of "size of a game". What is the size of the board pictured above? Is it 2x2, (measured in boxes), or 3x3 (measured in dots)?

@Kevin Apologies I was inconsistent. It is 2x2. Please let me know if any inconsistencies remain.

C99 - 3x3 board in 0.084s
2020 edit/disclaimer: See comments section. It looks like there may have been errors in the original code. Proceed to the remainder of this answer with some skepticism until it is fixed.
Edit: I refactored my code and did some deeper analysis on the results.
Further Edits: Added pruning by symmetries. This makes 4 algorithm configurations: with or without symmetries X with or without alpha-beta pruning
Furthest Edits: Added memoization using a hash table, finally achieving the impossible: solving a 3x3 board!
Primary features:

straightforward implementation of minimax with alpha-beta pruning
very little memory management (maintains dll of valid moves; O(1) updates per branch in the tree search)
second file with pruning by symmetries. Still achieves O(1) updates per branch (technically O(S) where S is the number of symmetries. This is 7 for square boards and 3 for non-square boards)
third and fourth files add memoization. You have control over the hashtable's size (#define HASHTABLE_BITWIDTH). When this size is greater than or equal to the number of walls, it guarantees no collisions and O(1) updates. Smaller hashtables will have more collisions and be slightly slower.
compile with -DDEBUG for printouts

Potential improvements:

fix small memory leak fixed in first edit
alpha/beta pruning added in 2nd edit
prune symmetries added in 3rd edit (note that symmetries are not handled by memoization, so that remains a separate optimization.)
memoization added in 4th edit
currently memoization uses an indicator bit for each wall. A 3x4 board has 31 walls, so this method couldn't handle 4x4 boards regardless of time constraints. the improvement would be to emulate X-bit integers, where X is at least as large as the number of walls.

Code
Due to lack of organization, the number of files has grown out of hand. All code has been moved to this Github Repository. In the memoization edit, I added a makefile and testing script.
Results

Notes on Complexity
Brute-force approaches to dots and boxes blow up in complexity very quickly.
Consider a board with R rows and C columns. There are R*C squares, R*(C+1) vertical walls, and C*(R+1) horizontal walls. That is a total of W = 2*R*C + R + C.
Because Lembik asked us to solve the game with minimax, we need to traverse to the leaves of the game tree. Let's ignore pruning for now, because what matters is orders of magnitude.
There are W options for the first move. For each of those, the next player can play any of the W-1 remaining walls, etc.. That gives us a search-space of SS = W * (W-1) * (W-2) * ... * 1, or SS = W!. Factorials are huge, but that's only the beginning. SS is the number of leaf nodes in the search space. More relevant to our analysis is the total number of decisions which had to be made (i.e. the number of branches B in the tree). The first layer of branches has W options. For each of those, the next level has W-1, etc.
B = W + W*(W-1) + W*(W-1)*(W-2) + ... + W!

B = SUM W!/(W-k)!
  k=0..W-1

Let's look at some small table sizes:
Board Size  Walls  Leaves (SS)      Branches (B)
---------------------------------------------------
1x1         04     24               64
1x2         07     5040             13699
2x2         12     479001600        1302061344
2x3         17     355687428096000  966858672404689

These numbers are getting ridiculous. At least they explain why the brute-force code seems to hang forever on a 2x3 board. The search-space of a 2x3 board is 742560 times larger than 2x2. If 2x2 takes 20 seconds to complete, a conservative extrapolation predicts over 100 days of execution time for 2x3. Clearly we need to prune.
Pruning Analysis
I started by adding very simple pruning using the alpha-beta algorithm. Basically, it stops searching if an ideal opponent would never give it its current opportunities. "Hey look - I win by a lot if my opponent lets me get every square!", thought no AI, ever.
edit I have also added pruning based on symmetrical boards. I don't use a memoization approach, just in case someday I add memoization and want to keep that analysis separate. Instead, it works like this: most lines have a "symmetric pair" somewhere else on the grid. There are up to 7 symmetries (horizontal, vertical, 180 rotation, 90 rotation, 270 rotation, diagonal, and the other diagonal). All 7 apply to square boards, but the last 4 don't apply to non-square boards. Each wall has a pointer to it's "pair" for each of these symmetries. If, going into a turn, the board is horizontally symmetric, then only one of each horizontal pair needs to be played.
edit edit Memoization! Each wall gets a unique id, which I conveniently set to be an indicator bit; the nth wall has the id 1 << n. The hash of a board, then, is just the OR of all walls played. This is updated at each branch in O(1) time. The size of the hashtable is set in a #define. All tests were run with size 2^12, because why not? When there are more walls than bits indexing the hashtable (12 bits in this case), the least significant 12 are masked and used as the index. Collisions are handled with a linked list at each hashtable index. The following chart is my quick-and-dirty analysis of how hashtable size affects performance. On a computer with infinite RAM, we would always set the table's size to the number of walls. A 3x4 board would have a hashtable 2^31 long. Alas we don't have that luxury.

Ok, back to pruning.. By stopping the search high in the tree, we can save a lot of time by not going down to leaves. The 'Pruning Factor' is the fraction of all-possible-branches which we had to visit. Brute-force has a pruning factor of 1. The smaller it is, the better.

23s seems conspicuously slow for a fast language like C. Are you brute forcing?

Brute force with a small amount of pruning from alpha beta. I agree that 23s is suspicious, but I don't see any reason in my code that it would be inconsistent.. In other words, its a mystery

How does your input work? It seems like you take 2 numbers as input but it's unclear what they do.

input is formatted as specified by the question. two space-separated integers rows columns specifying the size of the board

What do you get for the score in the 2x2 game? If you can get your code to output the optimal score that would be great.

@Lembik the code now does that and much more (specifically, it outputs statistics about the complexity of the current board. turns out 2x3 is, in fact, huge)

This is great. I suppose one way to handle symmetry and memoization together is to use rotation/reflection invariant representations of the board when you memoize?

Currently in the works is a version where each wall knows which other walls are symmetric pairs. I think this way I can still manage O(1) at each branch.

A really dumb question but when I run it with input "2 2" it says draw . But 2 by 2 is a win for the first player by 2 points.

@Lembik good news is I fixed the scoring error; 2x2 gives the correct output. Bad news is I am without internet and posting it will need to wait until tomorrow. It's quick though if you want to fix your local copy - in add_wall and remove_wall, adding two booleans needs to be casted as adding two ints.

@rangu did you have any luck?

@Lembik post is updated. Pruning symmetries is not a magical force to make it run faster.

Great. So only memoization to go! :) How much difference do you think that would make?

I Want to find a way to do memoization in O(1) also. Seems unlikely. I expect it won't add significant enough gains to reach 3x3. But that expectation may be wrong, so I gotta try :)

I get this warning. dotsnboxes_symmetries.h:138:58: warning: unused parameter ‘board’ [-Wunused-parameter]

Ignore it.. I gave all the symmetry functions the same type signature. That one happens to not depend on board size

..for the record, I hereby change my prediction that memoization won't have a big impact. It would reduce search from factorial to exponential branch space. the log plots would become straight lines. It could be enough to reach 3x3

In that case I am very excited! I look forward to seeing the result.

@Lembik I don't think there is anything left to do. I'm done with this crazy project!

I think your answer deserves a special place.  I looked it up and 3 by 3 is the largest problem size that has ever been solved before and your code is almost instant for it. If you can solve 3 by 4 or 4 by 4 you could add the result to the wiki page and be famous :)

See http://littlegolem.net/jsp/forum/topic2.jsp?forum=110&topic=90 for example (note that 4 x 4 there corresponds to 3 x 3 in your code).

I was exploring state of the art and stumbled across this. I downloaded and ran the code and it appears to be incorrect: it gives incorrect scores and different answers when width and height are switched. I'm curious if OP or anyone else has any comment on the correctness, since 3x3 board in 0.084s would be ground breaking!

OP here. This was written over a weekend a long time ago and, if I'm being honest, pretty sloppily. C has never been my language of choice. The kind of testing I did back then was to ensure that it gave the same answer for small boards whether brute-forcing or doing all the fancy speed-ups. And IIRC Lembik verified correctness of opening moves. But honestly if there's a bug somewhere I can't say I'm too surprised. In any case, I'm happy to consult or answer more questions if you're interested in picking up the proverbial torch.

@wrongu The first thing I want to say is that I am picking up the proverbial torch and reading through your code was a fantastic learning experience and way to start. I took away a lot of great ideas from you. I think an edit should be made to the post indicating that it may not be correct. solver_ab_sym_memo outputs a score of 0 on a 2x2 for instance, when it should be a score of 2, so who knows if there are some critical bugs

@jeremye thanks for looking into this. I might have time to fix things myself in a few weeks (might be fun to port to python too).

Python - 2x2 in 29s
Cross-posting from puzzles. Not especially optimized, but may make a useful starting point for other entrants.
from collections import defaultdict

VERTICAL, HORIZONTAL = 0, 1

#represents a single line segment that can be drawn on the board.
class Line(object):
    def __init__(self, x, y, orientation):
        self.x = x
        self.y = y
        self.orientation = orientation
    def __hash__(self):
        return hash((self.x, self.y, self.orientation))
    def __eq__(self, other):
        if not isinstance(other, Line): return False
        return self.x == other.x and self.y == other.y and self.orientation == other.orientation
    def __repr__(self):
        return "Line({}, {}, {})".format(self.x, self.y, "HORIZONTAL" if self.orientation == HORIZONTAL else "VERTICAL")

class State(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.whose_turn = 0
        self.scores = {0:0, 1:0}
        self.lines = set()
    def copy(self):
        ret = State(self.width, self.height)
        ret.whose_turn = self.whose_turn
        ret.scores = self.scores.copy()
        ret.lines = self.lines.copy()
        return ret
    #iterate through all lines that can be placed on a blank board.
    def iter_all_lines(self):
        #horizontal lines
        for x in range(self.width):
            for y in range(self.height+1):
                yield Line(x, y, HORIZONTAL)
        #vertical lines
        for x in range(self.width+1):
            for y in range(self.height):
                yield Line(x, y, VERTICAL)
    #iterate through all lines that can be placed on this board,
    #that haven't already been placed.
    def iter_available_lines(self):
        for line in self.iter_all_lines():
            if line not in self.lines:
                yield line

    #returns the number of points that would be earned by a player placing the line.
    def value(self, line):
        assert line not in self.lines
        all_placed = lambda seq: all(l in self.lines for l in seq)
        if line.orientation == HORIZONTAL:
            #lines composing the box above the line
            lines_above = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   VERTICAL),   #left
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            #lines composing the box below the line
            lines_below = [
                Line(line.x,   line.y-1, HORIZONTAL), #bottom
                Line(line.x,   line.y-1, VERTICAL),   #left
                Line(line.x+1, line.y-1, VERTICAL),   #right
            ]
            return all_placed(lines_above) + all_placed(lines_below)
        else:
            #lines composing the box to the left of the line
            lines_left = [
                Line(line.x-1, line.y+1, HORIZONTAL), #top
                Line(line.x-1, line.y,   HORIZONTAL), #bottom
                Line(line.x-1, line.y,   VERTICAL),   #left
            ]
            #lines composing the box to the right of the line
            lines_right = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   HORIZONTAL), #bottom
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            return all_placed(lines_left) + all_placed(lines_right)

    def is_game_over(self):
        #the game is over when no more moves can be made.
        return len(list(self.iter_available_lines())) == 0

    #iterates through all possible moves the current player could make.
    #Because scoring a point lets a player go again, a move can consist of a collection of multiple lines.
    def possible_moves(self):
        for line in self.iter_available_lines():
            if self.value(line) > 0:
                #this line would give us an extra turn.
                #so we create a hypothetical future state with this line already placed, and see what other moves can be made.
                future = self.copy()
                future.lines.add(line)
                if future.is_game_over():
                    yield [line]
                else:
                    for future_move in future.possible_moves():
                        yield [line] + future_move
            else:
                yield [line]

    def make_move(self, move):
        for line in move:
            self.scores[self.whose_turn] += self.value(line)
            self.lines.add(line)
        self.whose_turn = 1 - self.whose_turn

    def tuple(self):
        return (tuple(self.lines), tuple(self.scores.items()), self.whose_turn)
    def __hash__(self):
        return hash(self.tuple())
    def __eq__(self, other):
        if not isinstance(other, State): return False
        return self.tuple() == other.tuple()

#function decorator which memorizes previously calculated values.
def memoized(fn):
    answers = {}
    def mem_fn(*args):
        if args not in answers:
            answers[args] = fn(*args)
        return answers[args]
    return mem_fn

#finds the best possible move for the current player.
#returns a (move, value) tuple.
@memoized
def get_best_move(state):
    cur_player = state.whose_turn
    next_player = 1 - state.whose_turn
    if state.is_game_over():
        return (None, state.scores[cur_player] - state.scores[next_player])
    best_move = None
    best_score = float("inf")
    #choose the move that gives our opponent the lowest score
    for move in state.possible_moves():
        future = state.copy()
        future.make_move(move)
        _, score = get_best_move(future)
        if score < best_score:
            best_move = move
            best_score = score
    return [best_move, -best_score]

n = 2
m = 2
s = State(n,m)
best_move, relative_value = get_best_move(s)
if relative_value > 0:
    print("win")
elif relative_value == 0:
    print("draw")
else:
    print("lose")

Can be sped up to 18 seconds using pypy.

Javascript - 1x2 board in 20ms
Online demo available here (warning - very slow if larger than 1x2 with full search depth):
https://dl.dropboxusercontent.com/u/141246873/minimax/index.html
Was developed for the original win criteria (code golf) and not for speed.
Tested in google chrome v35 on windows 7.
//first row is a horizontal edges and second is vertical
var gameEdges = [
    [false, false],
    [false, false, false],
    [false, false]
]

//track all possible moves and score outcome
var moves = []

function minimax(edges, isPlayersTurn, prevScore, depth) {

    if (depth <= 0) {
        return [prevScore, 0, 0];
    }
    else {

        var pointValue = 1;
        if (!isPlayersTurn)
            pointValue = -1;

        var moves = [];

        //get all possible moves and scores
        for (var i in edges) {
            for (var j in edges[i]) {
                //if edge is available then its a possible move
                if (!edges[i][j]) {

                    //if it would result in game over, add it to the scores array, otherwise, try the next move
                    //clone the array
                    var newEdges = [];
                    for (var k in edges)
                        newEdges.push(edges[k].slice(0));
                    //update state
                    newEdges[i][j] = true;
                    //if closing this edge would result in a complete square, get another move and get a point
                    //square could be formed above, below, right or left and could get two squares at the same time

                    var currentScore = prevScore;
                    //vertical edge
                    if (i % 2 !== 0) {//i === 1
                        if (newEdges[i] && newEdges[i][j - 1] && newEdges[i - 1] && newEdges[i - 1][j - 1] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j - 1])
                            currentScore += pointValue;
                        if (newEdges[i] && newEdges[i][parseInt(j) + 1] && newEdges[i - 1] && newEdges[i - 1][j] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j])
                            currentScore += pointValue;
                    } else {//horizontal
                        if (newEdges[i - 2] && newEdges[i - 2][j] && newEdges[i - 1][j] && newEdges[i - 1][parseInt(j) + 1])
                            currentScore += pointValue;
                        if (newEdges[parseInt(i) + 2] && newEdges[parseInt(i) + 2][j] && newEdges[parseInt(i) + 1][j] && newEdges[parseInt(i) + 1][parseInt(j) + 1])
                            currentScore += pointValue;
                    }

                    //leaf case - if all edges are taken then there are no more moves to evaluate
                    if (newEdges.every(function (arr) { return arr.every(Boolean) })) {
                        moves.push([currentScore, i, j]);
                        console.log("reached end case with possible score of " + currentScore);
                    }
                    else {
                        if ((isPlayersTurn && currentScore > prevScore) || (!isPlayersTurn && currentScore < prevScore)) {
                            //gained a point so get another turn
                            var newMove = minimax(newEdges, isPlayersTurn, currentScore, depth - 1);

                            moves.push([newMove[0], i, j]);
                        } else {
                            //didnt gain a point - opponents turn
                            var newMove = minimax(newEdges, !isPlayersTurn, currentScore, depth - 1);

                            moves.push([newMove[0], i, j]);
                        }
                    }

                }

            }

        }//end for each move

        var bestMove = moves[0];
        if (isPlayersTurn) {
            for (var i in moves) {
                if (moves[i][0] > bestMove[0])
                    bestMove = moves[i];
            }
        }
        else {
            for (var i in moves) {
                if (moves[i][0] < bestMove[0])
                    bestMove = moves[i];
            }
        }
        return bestMove;
    }
}

var player1Turn = true;
var squares = [[0,0],[0,0]]//change to "A" or "B" if square won by any of the players
var lastMove = null;

function output(text) {
    document.getElementById("content").innerHTML += text;
}

function clear() {
    document.getElementById("content").innerHTML = "";
}

function render() {
    var width = 3;
    if (document.getElementById('txtWidth').value)
        width = parseInt(document.getElementById('txtWidth').value);
    if (width < 2)
        width = 2;

    clear();
    //need to highlight the last move taken and show who has won each square
    for (var i in gameEdges) {
        for (var j in gameEdges[i]) {
            if (i % 2 === 0) {
                if(j === "0")
                    output("*");
                if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
                    output(" <b>-</b> ");
                else if (gameEdges[i][j])
                    output(" - ");
                else
                    output("   ");
                output("*");
            }
            else {
                if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
                    output("<b>|</b>");
                else if (gameEdges[i][j])
                    output("|");
                else
                    output(" ");

                if (j <= width - 2) {
                    if (squares[Math.floor(i / 2)][j] === 0)
                        output("    ");
                    else
                        output(" " + squares[Math.floor(i / 2)][j] + " ");
                }
            }
        }
        output("<br />");

    }
}

function nextMove(playFullGame) {
    var startTime = new Date().getTime();
    if (!gameEdges.every(function (arr) { return arr.every(Boolean) })) {

        var depth = 100;
        if (document.getElementById('txtDepth').value)
            depth = parseInt(document.getElementById('txtDepth').value);

        if (depth < 1)
            depth = 1;

        var move = minimax(gameEdges, true, 0, depth);
        gameEdges[move[1]][move[2]] = true;
        lastMove = move;

        //if a square was taken, need to update squares and whose turn it is

        var i = move[1];
        var j = move[2];
        var wonSquare = false;
        if (i % 2 !== 0) {//i === 1
            if (gameEdges[i] && gameEdges[i][j - 1] && gameEdges[i - 1] && gameEdges[i - 1][j - 1] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j - 1]) {
                squares[Math.floor(i / 2)][j - 1] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
            if (gameEdges[i] && gameEdges[i][parseInt(j) + 1] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j]) {
                squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
        } else {//horizontal
            if (gameEdges[i - 2] && gameEdges[i - 2][j] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[i - 1] && gameEdges[i - 1][parseInt(j) + 1]) {
                squares[Math.floor((i - 1) / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
            if (gameEdges[i + 2] && gameEdges[parseInt(i) + 2][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][parseInt(j) + 1]) {
                squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
        }

        //didnt win a square so its the next players turn
        if (!wonSquare)
            player1Turn = !player1Turn;

        render();

        if (playFullGame) {
            nextMove(playFullGame);
        }
    }

    var endTime = new Date().getTime();
    var executionTime = endTime - startTime;
    document.getElementById("executionTime").innerHTML = 'Execution time: ' + executionTime;
}

function initGame() {

    var width = 3;
    var height = 2;

    if (document.getElementById('txtWidth').value)
        width = document.getElementById('txtWidth').value;
    if (document.getElementById('txtHeight').value)
        height = document.getElementById('txtHeight').value;

    if (width < 2)
        width = 2;
    if (height < 2)
        height = 2;

    var depth = 100;
    if (document.getElementById('txtDepth').value)
        depth = parseInt(document.getElementById('txtDepth').value);

    if (depth < 1)
        depth = 1;

    if (width > 2 && height > 2 && !document.getElementById('txtDepth').value)
        alert("Warning. Your system may become unresponsive. A smaller grid or search depth is highly recommended.");

    gameEdges = [];
    for (var i = 0; i < height; i++) {
        if (i == 0) {
            gameEdges.push([]);
            for (var j = 0; j < (width - 1) ; j++) {
                gameEdges[i].push(false);
            }
        }
        else {
            gameEdges.push([]);
            for (var j = 0; j < width; j++) {
                gameEdges[(i * 2) - 1].push(false);
            }
            gameEdges.push([]);
            for (var j = 0; j < (width - 1) ; j++) {
                gameEdges[i*2].push(false);
            }
        }
    }

    player1Turn = true;

    squares = [];
    for (var i = 0; i < (height - 1) ; i++) {
        squares.push([]);
        for (var j = 0; j < (width - 1); j++) {
            squares[i].push(0);
        }
    }

    lastMove = null;

    render();
}

document.addEventListener('DOMContentLoaded', initGame, false);

The demo is really great!  The 3 x 3 is really interesting as the winner changes back and forth as you increase the search depth.  Can I check, does your minimax ever stop half way through a turn?  What I mean is if someone gets a square, does it always extend to the end of their turn?

2x2 is 3 dots by 3. Are you sure your code can solve that exactly in 20ms?

"if someone gets a square, does it always extend to the end of their turn?" - If the player gets a square, it still moves to the next turn but that next turn is for the same player i.e. they get an extra turn for completing a square. "2x2 is 3 dots by 3" - Whoops. In that case my score is 1x1.

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