# Question
Title: Determining the rotation of square given a list of points
In this challenge, you will be given a list of points. **These points lie on the perimeter of an imaginary square**. Your goal is to:

1. If possible, print out the rotation of the square, which will be a value from \[0, 90) where 0 represents a square with lines vertical and horizontal. The rotation is to be given in degrees counted counter-clockwise.
2. If the rotation of the square is ambiguous (such as only being given 2 points), print out "Unknown"
3. If creating a square given the points is impossible, print out "Impossible"

The points you are given are guaranteed to be unique, and are in no particular order. You can use any format you wish to input the list, but for my examples, my points will be in the format `x,y`, and space separated. The numbers are floating-point numbers, and you can assume they are within a range that your language can handle. Your output should be accurate to at least 3 decimal places, and assume your language handles floating point numbers with perfect accuracy.

Here are some test cases (I have made most of these using whole numbers for easy visualizing, but your program should handle floating points):

Unknown:

```
0,0
0,0 1,0
0,0 1,0 0,1
0,0 1,0 0,1 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2

```

Impossible:

```
0,0 1,0 2,0 3,1 4,2
0,0 1,0 2,0 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2
2,0 0,1 2,2 0,3
0,0 2,1 0,2 2,2 -1,1

```

Possible (if not designated, should return 0):

```
0,0 1,0 2,0
0,0 0.3,0.3 0.6,0.6  (should return 45)
0,0 0.1,0.2 0.2,0.4  (should return appx 63.435 (the real value is arctan(2)))
0,0 0,1 2,1 2,2
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3

```

I may have missed some interesting test cases. If so, please comment to add them.

This is code-golf, so the shortest-code wins!

# Answer
> 6 votes
# Rev 1: Ruby, 354 bytes

**further golfing thanks to blutorange.**

```
->a{t=s=Math::PI/18E4
d=r=c=0
a=a.map{|e|e-a[0]}
0.upto(36E4){|i|b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose
m,n=b
if n.min>=f=0
l=[m.max-x=m.min,n.max].max
a.each_index{|j|f+=((l-w=n[j])*(x+l-v=m[j])*(x-v)*w)**2}
(1E-9>q=f/l**8)&&(c>0&&(i-d)%9E4%89E3>1E3?c=9E9:0;c+=1;d=i)
q<t&&(r=i)&&t=q;end}
c<101&&a[1]?c<1?'impossible':r%9E4/1.0E3:'unknown'}

```

# Ruby, 392 bytes

```
->(a){
s=Math::PI/18E4
t=1
d=r=c=0
a=a.map{|e|e-a[0]}
(0..36E4).each{|i|
b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose
m=b[0]
n=b[1]
x=m.min
if n.min>=0
l=[m.max-x,n.max].max
f=0
a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}
q=f/l**8
if q<1E-9
c>0&&(i-d)%9E4%89E3>1E3?(c=9E9):0
c+=1
d=i
end
if q<t
r=i
t=q
end
end
}
c>100||a.size<2?'unknown':c<1? 'impossible':r%9E4/1.0E3
}

```

The algorithm is as follows:

-Pick an arbitrary point (the first one) and move that to the origin (subtract the coordinates of this point from all points in the list.)

-Try all rotations of the square about the origin in 0.001 degree increments, through 360 degrees.

-For a given rotation, if all points are above the y axis, draw the smallest possible square around all the points, incorporating the lowest and leftmost point.

-Check if all points are on the edge. This is done with a soft calculation that takes each point, finds the squared distances from all edges, and multiplies them together. This gives a good fit rather than a yes/no answer. It is interpreted that a solution is found if this product divided by sidelength^8 is less than 1E-9. In practice this is less than a degree of tolerance.

-The best fit is taken mod 90 degrees and reported as the correct angle.

Currently the code returns a value of ambiguous if over 100 solutions are found (at 0.001 degree resolution. That's 0.1 degrees of tolerance.)

**first fully working function, in test program**

I left the resolution at 1/10th of the required resolution to make the speed reasonable. There is an error of 0.01 degress on the very last test case.

```
g=->(a){
 s=Math::PI/18000
 t=1
 d=r=-1
 c=0
 a=a.map{|e| e-a[0]}

 (0..36000).each{|i|
    b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose

    m=b[0]
    n=b[1]
    x=m.min

    if n.min>=0

       l=[m.max-x,n.max].max
       f=0
       a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}
       q=f/l**8

       if q<1E-9

         j=(i-d)%9000
         c>0&&j>100&&j<8900?(c=9E9):0
         c+=1
         d=i
       end

       if q<t
         r=i
         t=q
       end

     end
  }

 print "t=",t,"   r=",r,"     c=",c,"    d=",d,"\n"
 p c>100||a.size<2?'unknown':c<1? 'impossible':r%9000/100.0
}

#ambiguous
#g.call([Complex(0,0)])
#g.call([Complex(0,0),Complex(1,0)])
#g.call([Complex(0,0),Complex(1,0),Complex(0,1)])
#g.call([Complex(0,0),Complex(1,0),Complex(0,1),Complex(1,1)])
#g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2)])

#impossible
#g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(3,1),Complex(4,2)])
#g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(1,1)])
#g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2),Complex(2,2)])
#g.call([Complex(2,0),Complex(0,1),Complex(2,2),Complex(0,3)])
#g.call([Complex(0,0),Complex(2,1),Complex(0,2),Complex(2,2),Complex(-1,1)])

#possible
g.call([Complex(0,0),Complex(1,0),Complex(2,0)])
g.call([Complex(0,0),Complex(0.3,0.3),Complex(0.6,0.6)]) #(should return 45)
g.call([Complex(0,0),Complex(0.1,0.2),Complex(0.2,0.4)]) #(should return appx 63.435 (the real value is arctan(2)))
g.call([Complex(0,0),Complex(0,1),Complex(2,1),Complex(2,2)])
g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,4),Complex(2,0),Complex(2,4),Complex(4,1),Complex(4,3)])

```

**golfed version, resolution compliant with spec, takes about a minute per call, in test program.**

There's still a pesky error of 0.001 degrees on the last test case. Increasing resolution further would probably eliminate it.

```
g=->(a){                                                            #take an array of complex numbers as input
  s=Math::PI/18E4                                                   #step size PI/180000
  t=1                                                               #best fit found so far
  d=r=c=0                                                           #angles of (d) last valid result, (r) best fit; c= hit counter
  a=a.map{|e|e-a[0]}                                                #move shape so that first point coincides with origin
  (0..36E4).each{|i|                                                #0..360000
    b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose             #rotate each element by dividing by unit vector of angle i*s, convert to array...
    m=b[0]                                                          #...transpose array [[x1,y1]..[xn,yn]] to [[x1..xn],[y1..yn]]...
    n=b[1]                                                          #...and assign to variables m and n
    x=m.min                                                         #find leftmost point
    if n.min>=0                                                     #if all points are above x axis
       l=[m.max-x,n.max].max                                        #find the sidelength of smallest square in which they will fit
       f=0                                                          #f= accumulator for errors. For each point
       a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}   #...add to f the product of the squared distances from each side of the smallest square containing all points
       q=f/l**8                                                     #q= f normalized with respect to the sidelength.
       if q<1E-9                                                    #consider a hit if <1E-9
         c>0&&(i-d)%9E4%89E3>1E3?(c=9E9):0                          #if at least one point is already found, and the difference between this hit and the last exceeds+/-1 deg (mod 90), set c to a high value
         c+=1                                                       #increment hit count by 1 (this catches infinitely varible cases)
         d=i                                                        #store the current hit in d
       end
       if q<t                                                       #if current fit is better than previous one
        r=i                                                         #store the new angle
        t=q                                                         #and revise t to the new best fit.
       end
    end
  }
  c>100||a.size<2?'unknown':c<1? 'impossible':r%9E4/1.0E3           #calculate and return value, taking special care of case where single point given.
}
#ambiguous
puts g.call([Complex(0,0)])
puts g.call([Complex(0,0),Complex(1,0)])
puts g.call([Complex(0,0),Complex(1,0),Complex(0,1)])
puts g.call([Complex(0,0),Complex(1,0),Complex(0,1),Complex(1,1)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2)])

#impossible
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(3,1),Complex(4,2)])
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(1,1)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2),Complex(2,2)])
puts g.call([Complex(2,0),Complex(0,1),Complex(2,2),Complex(0,3)])
puts g.call([Complex(0,0),Complex(2,1),Complex(0,2),Complex(2,2),Complex(-1,1)])

#possible
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0)])
puts g.call([Complex(0,0),Complex(0.3,0.3),Complex(0.6,0.6)]) #(should return 45)
puts g.call([Complex(0,0),Complex(0.1,0.2),Complex(0.2,0.4)]) #(should return appx 63.435 (the real value is arctan(2)))
puts g.call([Complex(0,0),Complex(0,1),Complex(2,1),Complex(2,2)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,4),Complex(2,0),Complex(2,4),Complex(4,1),Complex(4,3)])

```

Note that for about 30% more code this algorithm could be adapted to work fast: it is obvious that in cases with a finite number of solutions, one of the edges lies flat along a a cube, so all we really have to try is those angles that correspond to each pair of vertices. It would also be necessary to do a bit of wiggling to check there aren't there aren't infinitely many solutions.

# Answer
> 6 votes
# Perl

Hello, here is my humble soution. Test cases are put in **DATA** stream at the bottom of the file. The algorithm has grown by a try-error approach.
I admit that it is a broadly heuristic approach, but it is really fast: it resolves all the cases *instantly*.
I am aware there will be some bugs, but up to now it gives correct replies to all the test cases.
I am also aware that the *shortest* code wins, but I am sure this is among the shortest in the *fastest* meaning of the term.

Here is the algorithm

1. examine dots and for each segment between two dots record slope, length, x-intercept, y-intercept
2. find straight lines (i.e. three dots or two adjacent segments) and distinct possible slopes (say them rotations). Keep track of the longest segment available in each line.
3. find all the distances between a segment and a third point (this should be used to point 4). Keep track of minimum non-zero distance.
4. for any four dots (rougly a rectangle) find inner dots

Show solutions:

A. Say "Impossible" if there are one or more inner dots.

B. One Line:

* In case of most of dots in a single line without inner dots, say "Possible"
* In case of dots too close to line, say "Impossible"

C. Two lines:
* Say "Possible" when there is only one possible rotation
* Say "Impossible" when there are more than one rotation

D. No lines: find rotation that fits its 90° rotate segment
* Say "Possible" if only one fits or as many as dots fit.
* Say "Impossible" if more than one fits and not as many as dots
* Say "Unknown" if as many as rotation fit.

Here is the code (all known bugs are resolved)

```
#!/usr/bin/perl
use strict ;
use warnings ;
my $PI = 4*atan2( 1, 1 ) ;
my $EPS = 0.000001 ;
while ( <DATA> ) {
    if ( /^\s*#/ ) { print ; next } # print comments
    chomp ;
    my @dot = split /\s+/ ;
    my $n = scalar @dot || next ; # skip empty lines

    # too few dots
    if ( $n < 3 ) {
        print "@dot : Unknown.\n" ;
        next
    }

    my %slop = () ; # segment --> its slope
    my %leng = () ; # segment --> its length
    my %x0   = () ; # segment --> its line's x-intercept
    my %y0   = () ; # segment --> its line's y-intercept
    my %side = () ; # slope   --> list of segments (with duplicates)

    # 1. examine dots
    for my $p (@dot) {
        my ($px,$py) = split /,/, $p ;
        for my $q (@dot) {
            next if $p eq $q ;
            next if defined ( $slop{ "$q $p" } ) ;
            my $segment_name = "$p $q" ;
            my ($qx,$qy) = split /,/, $q ;
            my $dx = $px - $qx ;
            my $dy = $py - $qy ;
            my $slope = "inf" ; $slope = $dy / $dx if abs($dx) > 0 ;
            my $sd = $dx*$dx+$dy*$dy ;
            my $x0 = ( $slope eq 'inf' ? $px : "nan" ) ;
            my $y0 = ( abs($slope) > 0 ? $px : "nan" ) ;
            $x0 = $qx - $qy / $slope if abs($slope) > 0 ;
            $y0 = $qy - $qx * $slope if $slope ne "inf" ;
            push @{ $side{ $slope } }, $segment_name ;
            $slop{ $segment_name } = $slope ;
            $leng{ $segment_name } = sqrt( $sd ) ;
            $x0{ $segment_name } = $x0 ;
            $y0{ $segment_name } = $y0 ;
        }
    }

    # 2. find straight lines and distinct possible slopes (rotation)
    my %line = () ;     # slope --> segment name
    my %rotation = () ; # slope --> slope itself
    my $a_rotation ;
    for my $slope ( keys %side ) {
        my %distinct = () ;
        for my $segment_name ( @{ $side{ $slope } } ) {
            $distinct{ $segment_name } = $slope ;
            my $rot = $slope eq 'inf' ? '0' : abs( $slope < 0 ? 1/$slope : $slope ) ;
            $rotation{ $rot } = $rot ;
            $a_rotation = $rot ;
        }
        for my $a_segm ( keys %distinct ) {
            for my $b_segm ( keys %distinct ) {
                next if $a_segm eq $b_segm ;
                # the two segment has to be adjacent
                my ($a1,$a2) = split / /, $a_segm;
                my ($b1,$b2) = split / /, $b_segm;
                next unless $a1 eq $b1 || $a1 eq $b2 || $a2 eq $b1 || $a2 eq $b2 ;
                # the two segment has to have same intercepts
                my $x0a = $x0{ $a_segm } ;
                my $x0b = $x0{ $b_segm } ;
                my $y0a = $y0{ $a_segm } ;
                my $y0b = $y0{ $b_segm } ;
                next unless $x0a eq $x0b && $y0a eq $y0b ;
                # keep the longest segment
                my $a_len = 0 ;
                $a_len = $leng{ $line{ $slope } } if defined( $line{ $slope } ) && defined( $leng{ $line{ $slope } } ) ;
                for my $segm ("$a1 $b1", "$a1 $b2", "$a2 $b1", "$a2 $b2",
                              "$b1 $a1", "$b2 $a1", "$b1 $a2", "$b2 $a2" ) {
                    next unless defined ( $leng{ $segm } ) ;
                    if ( $a_len < $leng{ $segm } ) {
                        $a_len = $leng{ $segm } ;
                        $line{ $slope } = $segm ;
                    }
                }
            }
        }
    }

    # 3. find distance between a segment and a third point
    my %distance = () ;            # segment-point --> distance
    my %distance_mani = () ;       # distance --> array of segment-point
    my %min_distance = () ;        # segment --> min distance to other dots
    for my $segment_name ( keys %slop ) {
        my $a = $slop{ $segment_name } ;
        my $b = -1 ;
        my $c = $y0{ $segment_name } ;
        my $z = $x0{ $segment_name } ;
        for my $p (@dot) {
            next if $segment_name =~ /$p/ ; # skip dots that are in the segment
            my ($px,$py) = split /,/, $p ;
            my $d = 0 ;
            if ( $a ne 'inf' ) {
                my $num = ($b * $py) + ($a * $px) + $c ;
                my $den = sqrt( $a*$a + $b*$b ) ;
                $d = abs( $num ) / $den ;
            }
            else {
                $d = abs( $px - $z );
            }
            $distance{ "$segment_name $p" } = $d ;
            push @{ $distance_mani{ $d } }, "$segment_name $p" ;
            if ( $d > 0 ) {
                $min_distance{ $segment_name } = $d if !defined ( $min_distance{ $segment_name } ) or $d < $min_distance{ $segment_name }
            }
        }
    }

    # 4. find inner dots: pick 4 dots to form a well shaped pseudo-rectangle
    #    and check for any other dot that is too close to all the 4 sides.
    my $fail = 0 ;
    RECTANGLE:
    for my $a ( @dot ) {
        for my $b ( @dot ) {
            next if $a eq $b ;
            my ($ax,$ay) = split /,/, $a ;
            my ($bx,$by) = split /,/, $b ;
            next if $ax > $bx || $ay > $by ;
            for my $c ( @dot ) {
                next if $c eq $a or $c eq $b ;
                my ($cx,$cy) = split /,/, $c ;
                next if $bx < $cx || $by > $cy ;
                for my $d ( @dot ) {
                    next if $d eq $a or $d eq $b or $d eq $c ;
                    my ($dx,$dy) = split /,/, $d ;
                    next if $cx < $dx || $cy < $dy  ;
                    next if $dx > $ax || $dy < $ay  ;
                    for my $e ( @dot ) {
                        next if $e eq $a or $e eq $b or $e eq $c or $e eq $d ;

                        my $abe = $distance{ "$a $b $e" } || $distance{ "$b $a $e" } || next ;
                        my $bce = $distance{ "$b $c $e" } || $distance{ "$c $b $e" } || next ;
                        my $cde = $distance{ "$c $d $e" } || $distance{ "$d $c $e" } || next ;
                        my $dae = $distance{ "$d $a $e" } || $distance{ "$a $d $e" } || next ;

                        my $abd = $distance{ "$a $b $d" } || $distance{ "$b $a $d" } || next ;
                        my $abc = $distance{ "$a $b $c" } || $distance{ "$b $a $c" } || next ;
                        my $bca = $distance{ "$b $c $a" } || $distance{ "$c $b $a" } || next ;
                        my $bcd = $distance{ "$b $c $d" } || $distance{ "$c $b $d" } || next ;
                        my $cdb = $distance{ "$c $d $b" } || $distance{ "$d $c $b" } || next ;
                        my $cda = $distance{ "$c $d $a" } || $distance{ "$d $c $a" } || next ;
                        my $dac = $distance{ "$d $a $c" } || $distance{ "$a $d $c" } || next ;
                        my $dab = $distance{ "$d $a $b" } || $distance{ "$a $d $b" } || next ;

                        if ( $abd > $abe && $abc > $abe &&
                             $bca > $bce && $bcd > $bce &&
                             $cdb > $cde && $cda > $cde &&
                             $dac > $dae && $dab > $dae) {
                            ## print "     $a $b $c $d --> $e\n";
                            $fail ++ ;
                            last RECTANGLE ;
                        }
                    }
                }
            }
        }
    }
    if ( $fail ) {
        print "@dot : Impossible.\n" ;
        next # DATA
    }

    my $m = scalar keys %rotation ; # how many distinct slopes
    my $r = scalar keys %line ; # how many lines i.e. >3 dots in a straight line

    print "@dot : " ;
    # most of dots lie in single line without inner dots
    if ( $r == 1 ) {
        $a_rotation = (keys %line)[0] ;
        my $a_segment = $line{ $a_rotation } ;
        my $a_dist = $min_distance{ $a_segment } || 0 ;
        if ( $a_dist && $a_dist < $leng{ $a_segment } ) {
            print "Impossible.\n"  ;
        }
        else {
            print "Possible. --> " . sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" ;
        }
        next # DATA
    }
    # two lines
    if ( $r == 2 ) {
        print "Impossible.\n" if $m > 1 ;
        print "Possible. --> " .
            sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" if $m == 1 ;  # never?
        next ; # DATA
    }
    # no lines
    if ( $r == 0 ) {
        # match between segment rotation and other side
        my $count = 0 ;
        my $numeros = 0 ;
        for my $slope ( keys %rotation ) {
            my $rot = $slope eq '0' ? 'inf' : -1/$slope ;
            if ( exists $side{ $rot } ) {
                $count++ ;
                my $u = scalar @{ $side{ $rot } } ;
                if ( $numeros < $u ) {
                    $numeros = $u ;
                    $a_rotation = $slope ;
                }
            }
        }
        print "Possible. --> " .
            sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" if $count < 2 or $count == $n ;
        print "Unknown.\n"    if $count == $m ;
        print "Impossible.\n"    if $count > 2 && $count != $n && $count != $m;
        next # DATA
    }
    # there are lines
    print "lines $r " ;
    my $shorter = 0 ;
    my $longer = 0 ;
    for my $slope ( keys %line ) {
        for my $dis ( keys %distance_mani ) {
            $shorter++ ;
            $longer++ ;
        }
    }
    print "ACK! WHAT IS THIS CASE! n=$n, m=$m, r=$r\n" ;
    1 ;
}

1;

__DATA__
# Unknown:

0,0
0,0 1,0
0,0 1,0 0,1
0,0 1,0 0,1 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2

# Impossible:

0,0 1,0 2,0 3,1 4,2
0,0 1,0 2,0 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2
2,0 0,1 2,2 0,3
0,0 2,1 0,2 2,2 -1,1

# Possible (if not designated, should return 0):

0,0 1,0 2,0 1,2
0,0 1,0 2,0 0.5,2.1

0,0 1,0 2,0
0,0 1,0 2,0 1,2
0,0 0.3,0.3 0.6,0.6
0,0 0.1,0.2 0.2,0.4
0,0 0,1 2,1 2,2
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3

```

And here is its ouptut

```
# Unknown:
0,0 : Unknown.
0,0 1,0 : Unknown.
0,0 1,0 0,1 : Unknown.
0,0 1,0 0,1 1,1 : Unknown.
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 : Unknown.
# Impossible:
0,0 1,0 2,0 3,1 4,2 : Impossible.
0,0 1,0 2,0 1,1 : Impossible.
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2 : Impossible.
2,0 0,1 2,2 0,3 : Impossible.
0,0 2,1 0,2 2,2 -1,1 : Impossible.
# Possible (if not designated, should return 0):
0,0 1,0 2,0 1,2 : Possible. --> 0.000 deg
0,0 1,0 2,0 0.5,2.1 : Possible. --> 0.000 deg
0,0 1,0 2,0 : Possible. --> 0.000 deg
0,0 1,0 2,0 1,2 : Possible. --> 0.000 deg
0,0 0.3,0.3 0.6,0.6 : Possible. --> 45.000 deg
0,0 0.1,0.2 0.2,0.4 : Possible. --> 63.435 deg
0,0 0,1 2,1 2,2 : Possible. --> 0.000 deg
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3 : Possible. --> 0.000 deg

```

Regards.

Matteo.

---
Tags: code-golf, geometry
---


title: Play a Song for Me

text:
# Question
Title: Play a Song for Me
## Challenge

Given guitar tablature you must output the song represented by the tab. This may be to the speakers of your computer or to an audio file (.wav, .mp3, .midi, .aiff, etc.). There will also be a second input for timing.

The tabs may be input via a file or straight to STDIN. The tab will be in ASCII form.

## Spec

All tabs are for 6 six string guitars with standard E tuning: E2 (82.41 Hz), A2 (110.00 Hz), D3 (146.83 Hz), G3 (196.00 Hz), B3 (246.94 Hz), E4 (329.63 Hz).

The only techniques (besides normal picking) you have to cater for are:

* Bending (this will always be a half tone bend)
* Hammering on
* Pulling off
* Sliding up/down

Since you cannot synthesise the sound of a muted string, treat `x` as a `-`.

When bending, output the full transition from unbent to string to bent to unbent again.

The second input will be the time that each symbol on the tab represents in seconds. For example:

For input:

```
e|---
B|---
G|---
D|---
A|---
E|---

```

With timing `0.5`, because there are `3` columns of symbols (but no notes), the outputted audio file is (`3*0.5=1.5`) `1.5` seconds of silence.

## Example tabs

### 1 - The Weight (Jack White, Jimmy Page + The Edge edition)

```
e|----3-----3---3----2---------3--------------------|
B|----3-----3---3----3--1-1----3--------------------|
G|----0-----0---0----2--0-0----0--------------------|
D|----0-----0---2-------2-2----0--------------------|
A|----2-----0---2-------3-3----2--------------------|
E|----3-----2---x----2--x-x----3--------------------|

```

### 2 - Smells Like Teen Spirit

```
e|--------------|---------------|-------------|-------------|
B|--------------|---------------|-------------|-------------|
G|-----8h10-----|-8-8b----6--5--|-6--5--------|-------------|
D|-10--------6--|---------------|-------8-6-8-|-8b----6--5--|
A|--------------|---------------|-------------|-------------|
E|--------------|---------------|-------------|-------------|

```

### 3 - Star Spangled Banner

```
e|---0-------2-5---9-7-5-----------9-7-5-4-2-4-5------|
B|-----2---2-------------2-4-5---5---------------5-2--|
G|-------2-------------------------------------------2|
D|----------------------------------------------------|
A|----------------------------------------------------|
E|----------------------------------------------------|

```

# Answer
> 7 votes
# MATLAB

This is sort of unfinished. I used a quick and dirty method to make the audio as easily as possible. The method I used made it difficult to implement the bending/hammering (I also had never heard those words in this context before).

Having said all of that, this script will read in a text file called "inputs.txt" containing the ascii-tab as required and play the song.

```
%timing
t=0.25;  %of course, this line could be 't=input('timing: ');
        %if you make t a wonky value such that t*8192 is not an integer, some
        %stuff will fail
%frequencies and extra variables to allow some laziness later
e = 329.63;eN = 1;
B = 246.94;BN = 2;
G = 196.00;GN = 3;
D = 146.83;DN = 4;
A = 110.00;AN = 5;
E = 82.41;EN = 6;
%this will store the song in a more computer friendly way
song = zeros(1,6);
%function to get frequency from v=frequency and f=fret
w=@(v,f)v*(2^(f/12));
%get input and start the big loop
file = fopen('input.txt');
line = fgetl(file);
while ischar(line)
    %the first character of the line will give us the the line frequency
    lfreqv = eval(line(1));         %frequency
    lfreqN = eval([line(1),'N']);   %horizontal index of frequency
    %start the small loop over each line
    for k = 3:(numel(line))-1
        if (strcmp(line(k),'-'))||(strcmp(line(k),'|'))||(strcmp(line(k),'h'))||(strcmp(line(k),'b'))
            song(k-2,lfreqN) = 0;
        else
            song(k-2,lfreqN) = w(lfreqv,double(line(k)));
        end
    end
    line = fgetl(file);
end
fclose(file);
%this will hold the song
tune = [];
vols = zeros(1,6);
playf = zeros(1,6);
for songIndex = 1:size(song,1)
    ctune = [];
    for k=1:6
        if song(songIndex,k) == 0
            vols(k) = 2*vols(k)/4;
        else
            vols(k) = 1;
            playf(k) = song(songIndex,k);
        end
        ctune(k,1:t*8192)=vols(k)*sin(0.5*pi*playf(k)*(1:(t*8192))/8192);
    end
    tune = [tune ctune];
end
soundsc(sum(tune));

```

Here is a link to the sound of the first test input.

Here is a link to the sound of the third test input. (Star Spangled Banner or Ice Cream Truck?)

The second test input sounded pretty bad to me, but that may be because it uses a lot of `b`s and `h`s which the script ignores.

As you can hear, the output is not quite the same quality as the original. It sort of sounds like there's a metronome playing in the background. I think these tunes have character.

# Answer
> 6 votes
# Python 3

I had to try this one.

This converts a tab to a midi file as played by a piano. I have no idea how to do a string bending on a piano, so it can't do that, but hammer-on's and pull-off's are straightforward.

I generated the test files like so: `$ python3 tab.py The-weight.txt 0.14` where `0.14` is the length of a single note in seconds.

```
from midiutil.MidiFile3 import MIDIFile
import sys

# Read the relevant lines of the file
lines = []
if len(sys.argv) > 1:
    filename = sys.argv[1]
    try:
        beats_per_minute = 60 / float(sys.argv[2])
    except:
        beats_per_minute = 756
else:
    filename = 'mattys-tune.txt'
    beats_per_minute = 756
with open(filename) as f:
    for line in f:
        if len(line) > 3 and (line[1] == '|' or line[2] == '|'):
            line = line.replace('\n', '')
            lines.append(line)
assert len(lines) % 6 == 0

# Initialize the MIDIFile object (with 1 track)
time = 0
duration = 10
volume = 100
song = MIDIFile(1)
song.addTrackName(0, time, "pianized_guitar_tab.")
song.addTempo(0, time, beats_per_minute)

# The root-pitches of the guitar
guitar = list(reversed([52, 57, 62, 67, 71, 76])) # Assume EADGBe tuning
def add_note(string, fret):
    song.addNote(0, string, guitar[string] + fret, time, duration, volume)

# Process the entire tab
for current in range(0, len(lines), 6):  # The current base string
    for i in range(len(lines[current])): # The position in the current string
        time += 1
        for s in range(6):               # The number of the string
            c = lines[current + s][i]
            try: next_char = lines[current + s][i + 1]
            except: next_char = ''
            if c in '-x\\/bhp':
                # Ignore these characters for now
                continue
            elif c.isdigit():
                # Special case for fret 10 and higher
                if next_char.isdigit():
                    c += next_char
                    lines[current + s] = lines[current + s][:i+1] + '-' + lines[current + s][i+2:]
                # It's a note, play it!
                add_note(s, int(c))
            else:
                # Awww
                time -= 1
                break

# And write it to disk.
def save():
    binfile = open('song.mid', 'wb')
    song.writeFile(binfile)
    binfile.close()
    print('Done')
try:
    save()
except:
    print('Error writing to song.mid, try again.')
    input()
    try:
        save()
    except:
        print('Failed!')

```

The code is on github too, https://github.com/Mattias1/ascii-tab, where I also uploaded the result of the examples provided by the OP. I also tried it on some of my own tabs. It's quite weird to hear a piano play it, but it's not bad.

## Examples:

I added some direct links, but not sure how long they stay, so I'll keep the old download links as well.

1. The weight, or play
2. Smells like teen spirit, or play
3. Star sprangled banner, or play
4. Matty's tune, or play
5. dm tune, or play

And the tab from Matty's tune (my favourite) below:

```
    Am/C        Am            F          G             Am/C        Am
e |------------------------|----------------0-------|------------------------|
B |-1--------1--1--------1-|-1--------1--3-----3----|-1--------1--1--------1-|
G |-2-----2-----2-----2----|-2-----2--------------0-|-2-----2-----2-----2----|
D |----2-----------2-------|----2-------------------|----2-----------2-------|
A |-3-----2-----0----------|-------0--------0--2----|-3-----------0----------|
E |-------------------3----|-1-----------3----------|------------------------|

    F        G               Am/C        Am           F           G
e |------------------------|------------------------|----------------0-------|
B |-1--------3-------------|-1--------1--1--------1-|-1--------1--3-----3----|
G |----------4-------------|-2-----2-----2-----2----|-2-----2--------------0-|
D |-------3--5-------------|----2-----------2-------|----2-------------------|
A |----3-----5--------0--2-|-3-----2-----0----------|-------0--------0--2----|
E |-1--------3-----3-------|-------------------3----|-1-----------3----------|

    Am/C        Am           F        G
e |------------------------|------------------------|
B |-1--------1--1--------1-|-1----------3-----------|
G |-2-----2-----2-----2----|------------4-----------|
D |----2-----------2-------|-------3---5------------|
A |-3-----------0----------|----3------5------------|
E |------------------------|-1--------3-------------|

```

# Answer
> 4 votes
# JavaScript

**Note: Uses Web Development Audio Kit; This is way out of IE's League; Tested in Google Chrome**

You can put the tabs in the textarea. IE you could put Matty's tune from Matty's post in the textarea (with the letters over the notes) and it will still parse correctly.

Click to Run Program

JavaScript:

```
context = new AudioContext;
gainNode = context.createGain();
gainNode.connect(context.destination);

gain= 2;

function getValue(i) {
    return document.getElementById(i).value;
}

function addValue(i, d) {
    document.getElementById(i).value += d;
}

function setValue(i, d) {
    document.getElementById(i).value = d;
}

document.getElementById("tada").onclick = updateLines;

function updateLines(){
    var e=getValue("ta").replace(/[^-0-9\n]/g,'').replace("\n\n","\n").split("\n");
    for(var l=0;l<e.length;l+=6){
        try{
        addValue("littleE",e[l]);
        addValue("B",e[l+1]);
        addValue("G",e[l+2]);
        addValue("D",e[l+3]);
        addValue("A",e[l+4]);
        addValue("E",e[l+5]);
        }catch(err){}
    }
    updateDash();
}

document.getElementById("littleE").oninput = updateDash;
document.getElementById("B").oninput = updateDash;
document.getElementById("G").oninput = updateDash;
document.getElementById("D").oninput = updateDash;
document.getElementById("A").oninput = updateDash;
document.getElementById("E").oninput = updateDash;

function updateDash() {
    max = 10;
    findDashMax("littleE");
    findDashMax("B");
    findDashMax("G");
    findDashMax("D");
    findDashMax("A");
    findDashMax("E");
    applyMax();
    i = "littleE";
    dash = new Array();
    for (var l = 0; l < getValue(i).length; l++) {
        if (getValue(i).charCodeAt(l) == 45) {
            dash[l] = true;
        } else {
            dash[l] = false;
        }
    }
    /*applyDash("B");
    applyDash("G");
    applyDash("D");
    applyDash("A");
    applyDash("E");*/
}

function findDashMax(i) {
    if (getValue(i).length > max) {
        max = getValue(i).length;
    }
}

function applyMax() {
    if (max < 50) {
        document.getElementById("stepe").size = 50;
        document.getElementById("littleE").size = 50;
        document.getElementById("B").size = 50;
        document.getElementById("G").size = 50;
        document.getElementById("D").size = 50;
        document.getElementById("A").size = 50;
        document.getElementById("E").size = 50;
    } else {
        document.getElementById("stepe").size = max + 1;
        document.getElementById("littleE").size = max + 1;
        document.getElementById("B").size = max + 1;
        document.getElementById("G").size = max + 1;
        document.getElementById("D").size = max + 1;
        document.getElementById("A").size = max + 1;
        document.getElementById("E").size = max + 1;
    }
}

function applyDash(i) {
    var old = getValue(i);
    setValue(i, "");
    for (var l = 0; l < old.length || dash[l] == true; l++) {
        if (dash[l] == true) {
            addValue(i, "-");
        } else {
            if (old.charCodeAt(l) != 45) {
                addValue(i, old.charAt(l));
            }
        }
    }
}
document.getElementById("next").onclick = begin;

function addDash(i) {
    while (getValue(i).length < max) {
        addValue(i, "-");
    }
}

function begin() {
    setValue("littleE",getValue("littleE").replace(/[^-0-9]/g,''));
    setValue("B",getValue("B").replace(/[^-0-9]/g,''));
    setValue("G",getValue("G").replace(/[^-0-9]/g,''));
    setValue("D",getValue("D").replace(/[^-0-9]/g,''));
    setValue("A",getValue("A").replace(/[^-0-9]/g,''));
    setValue("E",getValue("E").replace(/[^-0-9]/g,''));
    addDash("littleE");
    addDash("B");
    addDash("G");
    addDash("D");
    addDash("A");
    addDash("E");
    setValue("next", "Stop");
    //playing = true;
    findLength();
    document.getElementById("next").onclick = function () {
        clearInterval(playingID);
        oscillator["littleE"].stop(0);
        oscillator["B"].stop(0);
        oscillator["G"].stop(0);
        oscillator["D"].stop(0);
        oscillator["A"].stop(0);
        oscillator["E"].stop(0);
        setValue("next", "Play");
        document.getElementById("next").onclick = begin;
    }
    step = -1;
    playingID = setInterval(function () {
        step++;
        setValue("stepe", "");
        for (var l = 0; l < step; l++) {
            addValue("stepe", " ");
        }
        addValue("stepe", "V");
        if (lg[step]) {
            oscillator["littleE"].stop(0);
            oscillator["B"].stop(0);
            oscillator["G"].stop(0);
            oscillator["D"].stop(0);
            oscillator["A"].stop(0);
            oscillator["E"].stop(0);
        }
        qw=0
        doSound("littleE");
        doSound("B");
        doSound("G");
        doSound("D");
        doSound("A");
        doSound("E");

    }, getValue("s") * 1000);
}

function doSound(i) {
    switch (getValue(i).charAt(step)) {
        case ("-"):
        case ("x"):
        case (""):
        case (" "):
            break;
        default:
            qw++;
            makeSound(fretToHz(getHz(i), getValue(i).charAt(step)), i);

    }
    checkTop();
}

function checkTop(){
    switch(qw){
        case 0:
            break;
        case 1:
            gain=2;
            break;
        case 2:
            gain=1;
            break;
        case 3:
            gain=.5;
            break;
        default:
            gain=.3;
            break;
    }
}

function getHz(i) {
    switch (i) {
        case "littleE":
            return 329.63;
        case "B":
            return 246.94;
        case "G":
            return 196;
        case "D":
            return 146.83;
        case "A":
            return 110;
        case "E":
            return 82.41;
    }
}

function fretToHz(v, f) {
    return v * (Math.pow(2, (f / 12)));
}

/*function getTime() {
    var u = 1;
    while (lg[step + u] == false) {
        u++;
    }
    return u;
}*/

function findLength() {
    lg = new Array();
    for (var h = 0; h < getValue("littleE").length; h++) {
        lg[h] = false;
        fl(h, "littleE");
        fl(h, "B");
        fl(h, "G");
        fl(h, "D");
        fl(h, "A");
        fl(h, "E");
    }
    console.table(lg);
}

function fl(h, i) {
    var l = getValue(i).charAt(h);
    switch (l) {
        case "-":
        case "|":
            break;
        default:
            lg[h] = true;
    }
}

oscillator = new Array();

function makeSound(hz, i) {
    console.log("playing " + hz + " Hz" + i);
    oscillator[i] = context.createOscillator();
    oscillator[i].connect(gainNode);
    oscillator[i].frequency.value = hz;
    oscillator[i].start(0);
}

soundInit("littleE");
soundInit("B");
soundInit("G");
soundInit("D");
soundInit("A");
soundInit("E");

function soundInit(i) {
    makeSound(440, i);
    oscillator[i].stop(0);
}
setInterval(function () {
    gainNode.gain.value = .5 * getValue("v") * gain;
    document.getElementById("q").innerHTML = "Volume:" + Math.round(getValue("v") * 100) + "%";
}, 100);

```

Can you Identify this song?

# Answer
> 2 votes
# Java

This program converts a tablature to 16-bit WAV format.

Firstly, I wrote a whole bunch of tablature parsing code. I'm not sure if my parsing is entirely correct, but I think it's okay. Also, it could use more validation for data.

After that, I made the code to generate the audio. Each string is generated separately. The program keeps track of the current frequency, amplitude and phase. It then generates 10 overtones for the frequency with made-up relative amplitudes, and adds them up. Finally, the strings are combined and the result is normalized. The result is saved as WAV audio, which I chose for its ultra-simple format (no libraries used).

It "supports" hammering (`h`) and pulling (`p`) by ignoring them since I really didn't have the time to make them sound too different. The result sounds a bit like a guitar, though (spent some hours spectrum analyzing my guitar in Audacity).

Also, it supports bending (`b`), releasing (`r`) and sliding (`/` and `\`, interchangeable). `x` is implemented as muting the string.

You can try tweaking the constants in the start of the code. Especially lowering `silenceRate` often leads to better quality.

## Example results

## The code

I want to warn any Java beginners: do *not* try to learn anything from this code, it's terribly written. Also, it was written quickly and in 2 sessions and it was not meant to be used ever again so it has no comments. (Might add some later :P)

```
import java.io.*;
import java.util.*;

public class TablatureSong {

    public static final int sampleRate = 44100;

    public static final double silenceRate = .4;

    public static final int harmonies = 10;
    public static final double harmonyMultiplier = 0.3;

    public static final double bendDuration = 0.25;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Output file:");
        String outfile = in.nextLine();
        System.out.println("Enter tablature:");
        Tab tab = parseTablature(in);
        System.out.println("Enter tempo:");
        int tempo = in.nextInt();
        in.close();

        int samples = (int) (60.0 / tempo * tab.length * sampleRate);
        double[][] strings = new double[6][];
        for (int i = 0; i < 6; i++) {
            System.out.printf("Generating string %d/6...\n", i + 1);
            strings[i] = generateString(tab.actions.get(i), tempo, samples);
        }

        System.out.println("Combining...");
        double[] combined = new double[samples];
        for (int i = 0; i < samples; i++)
            for (int j = 0; j < 6; j++)
                combined[i] += strings[j][i];

        System.out.println("Normalizing...");
        double max = 0;
        for (int i = 0; i < combined.length; i++)
            max = Math.max(max, combined[i]);
        for (int i = 0; i < combined.length; i++)
            combined[i] = Math.min(1, combined[i] / max);

        System.out.println("Writing file...");
        writeWaveFile(combined, outfile);
        System.out.println("Done");
    }

    private static double[] generateString(List<Action> actions, int tempo, int samples) {
        double[] harmonyPowers = new double[harmonies];
        for (int harmony = 0; harmony < harmonyPowers.length; harmony++) {
            if (Integer.toBinaryString(harmony).replaceAll("[^1]", "").length() == 1)
                harmonyPowers[harmony] = 2 * Math.pow(harmonyMultiplier, harmony);
            else
                harmonyPowers[harmony] = Math.pow(harmonyMultiplier, harmony);
        }
        double actualSilenceRate = Math.pow(silenceRate, 1.0 / sampleRate);

        double[] data = new double[samples];

        double phase = 0.0, amplitude = 0.0;
        double slidePos = 0.0, slideLength = 0.0;
        double startFreq = 0.0, endFreq = 0.0, thisFreq = 440.0;
        double bendModifier = 0.0;
        Iterator<Action> iterator = actions.iterator();
        Action next = iterator.hasNext() ? iterator.next() : new Action(Action.Type.NONE, Integer.MAX_VALUE);

        for (int sample = 0; sample < samples; sample++) {
            while (sample >= toSamples(next.startTime, tempo)) {
                switch (next.type) {
                case NONE:
                    break;
                case NOTE:
                    amplitude = 1.0;
                    startFreq = endFreq = thisFreq = next.value;
                    bendModifier = 0.0;
                    slidePos = 0.0;
                    slideLength = 0;
                    break;
                case BEND:
                    startFreq = addHalfSteps(thisFreq, bendModifier);
                    bendModifier = next.value;
                    slidePos = 0.0;
                    slideLength = toSamples(bendDuration);
                    endFreq = addHalfSteps(thisFreq, bendModifier);
                    break;
                case SLIDE:
                    slidePos = 0.0;
                    slideLength = toSamples(next.endTime - next.startTime, tempo);
                    startFreq = thisFreq;
                    endFreq = thisFreq = next.value;
                    break;
                case MUTE:
                    amplitude = 0.0;
                    break;
                }
                next = iterator.hasNext() ? iterator.next() : new Action(Action.Type.NONE, Integer.MAX_VALUE);
            }

            double currentFreq;
            if (slidePos >= slideLength || slideLength == 0)
                currentFreq = endFreq;
            else
                currentFreq = startFreq + (endFreq - startFreq) * (slidePos / slideLength);

            data[sample] = 0.0;
            for (int harmony = 1; harmony <= harmonyPowers.length; harmony++) {
                double phaseVolume = Math.sin(2 * Math.PI * phase * harmony);
                data[sample] += phaseVolume * harmonyPowers[harmony - 1];
            }

            data[sample] *= amplitude;
            amplitude *= actualSilenceRate;
            phase += currentFreq / sampleRate;
            slidePos++;
        }
        return data;
    }

    private static int toSamples(double seconds) {
        return (int) (sampleRate * seconds);
    }

    private static int toSamples(double beats, int tempo) {
        return (int) (sampleRate * beats * 60.0 / tempo);
    }

    private static void writeWaveFile(double[] data, String outfile) {
        try (OutputStream out = new FileOutputStream(new File(outfile))) {
            out.write(new byte[] { 0x52, 0x49, 0x46, 0x46 }); // Header: "RIFF"
            write32Bit(out, 44 + 2 * data.length, false); // Total size
            out.write(new byte[] { 0x57, 0x41, 0x56, 0x45 }); // Header: "WAVE"
            out.write(new byte[] { 0x66, 0x6d, 0x74, 0x20 }); // Header: "fmt "
            write32Bit(out, 16, false); // Subchunk1Size: 16
            write16Bit(out, 1, false); // Format: 1 (PCM)
            write16Bit(out, 1, false); // Channels: 1
            write32Bit(out, 44100, false); // Sample rate: 44100
            write32Bit(out, 44100 * 1 * 2, false); // Sample rate * channels *
                                                    // bytes per sample
            write16Bit(out, 1 * 2, false); // Channels * bytes per sample
            write16Bit(out, 16, false); // Bits per sample
            out.write(new byte[] { 0x64, 0x61, 0x74, 0x61 }); // Header: "data"
            write32Bit(out, 2 * data.length, false); // Data size
            for (int i = 0; i < data.length; i++) {
                write16Bit(out, (int) (data[i] * Short.MAX_VALUE), false); // Data
            }
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static void write16Bit(OutputStream stream, int val, boolean bigEndian) throws IOException {
        int a = (val & 0xFF00) >> 8;
        int b = val & 0xFF;
        if (bigEndian) {
            stream.write(a);
            stream.write(b);
        } else {
            stream.write(b);
            stream.write(a);
        }
    }

    private static void write32Bit(OutputStream stream, int val, boolean bigEndian) throws IOException {
        int a = (val & 0xFF000000) >> 24;
        int b = (val & 0xFF0000) >> 16;
        int c = (val & 0xFF00) >> 8;
        int d = val & 0xFF;
        if (bigEndian) {
            stream.write(a);
            stream.write(b);
            stream.write(c);
            stream.write(d);
        } else {
            stream.write(d);
            stream.write(c);
            stream.write(b);
            stream.write(a);
        }
    }

    private static double[] strings = new double[] { 82.41, 110.00, 146.83, 196.00, 246.94, 329.63 };

    private static Tab parseTablature(Scanner in) {
        String[] lines = new String[6];
        List<List<Action>> result = new ArrayList<>();
        int longest = 0;
        for (int i = 0; i < 6; i++) {
            lines[i] = in.nextLine().trim().substring(2);
            longest = Math.max(longest, lines[i].length());
        }
        int skipped = 0;
        for (int i = 0; i < 6; i++) {
            StringIterator iterator = new StringIterator(lines[i]);
            List<Action> actions = new ArrayList<Action>();
            while (iterator.index() < longest) {
                if (iterator.get() < '0' || iterator.get() > '9') {
                    switch (iterator.get()) {
                    case 'b':
                        actions.add(new Action(Action.Type.BEND, 1, iterator.index(), iterator.index()));
                        iterator.next();
                        break;
                    case 'r':
                        actions.add(new Action(Action.Type.BEND, 0, iterator.index(), iterator.index()));
                        iterator.next();
                        break;
                    case '/':
                    case '\\':
                        int startTime = iterator.index();
                        iterator.findNumber();
                        int endTime = iterator.index();
                        int endFret = iterator.readNumber();
                        actions.add(new Action(Action.Type.SLIDE, addHalfSteps(strings[5 - i], endFret), startTime,
                                endTime));
                        break;
                    case 'x':
                        actions.add(new Action(Action.Type.MUTE, iterator.index()));
                        iterator.next();
                        break;
                    case '|':
                        iterator.skip(1);
                        iterator.next();
                        break;
                    case 'h':
                    case 'p':
                    case '-':
                        iterator.next();
                        break;
                    default:
                        throw new RuntimeException(String.format("Unrecognized character: '%c'", iterator.get()));
                    }
                } else {
                    StringBuilder number = new StringBuilder();
                    int startIndex = iterator.index();
                    while (iterator.get() >= '0' && iterator.get() <= '9') {
                        number.append(iterator.get());
                        iterator.next();
                    }
                    int fret = Integer.parseInt(number.toString());
                    double freq = addHalfSteps(strings[5 - i], fret);
                    actions.add(new Action(Action.Type.NOTE, freq, startIndex, startIndex));
                }
            }
            result.add(actions);
            skipped = iterator.skipped();
        }
        return new Tab(result, longest - skipped);
    }

    private static double addHalfSteps(double freq, double halfSteps) {
        return freq * Math.pow(2, halfSteps / 12.0);
    }

}

class StringIterator {
    private String string;
    private int index, skipped;

    public StringIterator(String string) {
        this.string = string;
        index = 0;
        skipped = 0;
    }

    public boolean hasNext() {
        return index < string.length() - 1;
    }

    public void next() {
        index++;
    }

    public void skip(int length) {
        skipped += length;
    }

    public char get() {
        if (index < string.length())
            return string.charAt(index);
        return '-';
    }

    public int index() {
        return index - skipped;
    }

    public int skipped() {
        return skipped;
    }

    public boolean findNumber() {
        while (hasNext() && (get() < '0' || get() > '9'))
            next();
        return get() >= '0' && get() <= '9';
    }

    public int readNumber() {
        StringBuilder number = new StringBuilder();
        while (get() >= '0' && get() <= '9') {
            number.append(get());
            next();
        }
        return Integer.parseInt(number.toString());
    }
}

class Action {
    public static enum Type {
        NONE, NOTE, BEND, SLIDE, MUTE;
    }

    public Type type;
    public double value;
    public int startTime, endTime;

    public Action(Type type, int time) {
        this(type, time, time);
    }

    public Action(Type type, int startTime, int endTime) {
        this(type, 0, startTime, endTime);
    }

    public Action(Type type, double value, int startTime, int endTime) {
        this.type = type;
        this.value = value;
        this.startTime = startTime;
        this.endTime = endTime;
    }
}

class Tab {
    public List<List<Action>> actions;
    public int length;

    public Tab(List<List<Action>> actions, int length) {
        this.actions = actions;
        this.length = length;
    }
}

```

---
Tags: popularity-contest, audio
---


title: A Chrestomathy of Obscurity

text:
# Question
Title: A Chrestomathy of Obscurity
You should complete four tasks in a language which:

* must return no results\* when searched for on this (codegolf.se) website, for example ToffeeScript;
* must have a page listed at Esolang, Rosetta Code or Wikipedia;
* be a distinct language, rather than a distinct version (e.g. python 2.1 would be valid iff python satisfied the first two criteria).

\*The exception being this hit for ToffeeScript.

The four tasks you should complete are:

1) Write a tweetable (\<140 characters) description/promotion of your chosen language.

2) Print "Hello World! This is written in `<programming language name>`."

3) Print all the odd numbers in a user specified range. (e.g. a stdin of `20 25` should return `21 23 25`).

4) Write a program which you feel best demonstrates an interesting feature of your chosen language.

Scoring:

* This is a popularity contest
* Bonus of 10 points if listed in two of the above directories, 25 if in all three.
* Score is the summation of votes received at midnight UTC on July 1 2015, plus the bonuses.

Clarifications:

* Task 1) can be a tweetable program but plain text is also acceptable.
* Many languages do not have an existing interpreter; solutions to these are fine, but will be taken in good faith.
* The second criterion for language choice forbids pages whose creation dates after this post. If, for a given language, X, a solution to a problem exists on Rosetta Code but it does not have a distinct page of its own somewhere, it is still acceptable.

# Answer
# BlooP

Bonus: 10

There are pages for BlooP on Esolangs and Wikipedia. A PPCG search for BlooP returns no results. If you're feeling particularly loopy, you can try it out on repl.it.

---

### Task 1: The Tweet

> BlooP: Nothing but bounded loops. ;) #programming #goodtimes

This uses standard Twitter styling including hashtags and emoticons. This would appeal to any Twitter user.\*

---

### Task 2: The Hello World

```
DEFINE PROCEDURE ''GREETING'' [N]:
BLOCK 0: BEGIN
  PRINT['Hello World! This is written in BlooP.']
BLOCK 0: END.

GREETING[0];

```

As you can see, this is a prime golfing language.\*

---

### Task 3: The Odd Numbers

```
DEFINE PROCEDURE ''IS-ODD'' [N]:
BLOCK 0: BEGIN
  OUTPUT <= 0;
  CELL(0) <= 2;
  LOOP AT MOST N+1 TIMES:
  BLOCK 1: BEGIN
    IF N+1 = CELL(0), THEN:
    BLOCK 2: BEGIN
      OUTPUT <= 1;
      ABORT LOOP 1;
    BLOCK 2: END;
    CELL(0) <= CELL(0) + 2
  BLOCK 1: END;
BLOCK 0: END.

DEFINE PROCEDURE ''ODDS-IN-RANGE'' [A,B]:
BLOCK 0: BEGIN
  CELL(0) = A;
  LOOP AT MOST B TIMES:
  BLOCK 1: BEGIN
    IF CELL(0) > B, THEN:
    ABORT LOOP 1;
    IF IS-ODD[CELL(0)] = 1, THEN:
    PRINT[CELL(0)];
    CELL(0) <= CELL(0) + 1;
  BLOCK 1: END;
BLOCK 0: END.

ODDS-IN-RANGE[20,25];

```

The only available operators in BlooP are assignment (`<=`), addition, multiplication, greater than, less than, and equals. Because of its painfully verbose syntax, it's actually pretty easy to tell what's going on even without a deep understanding of the language.

---

### Task 4: The Interesting

Note: My snippet for this task is subject to change should I come up with something more interesting.

```
DEFINE PROCEDURE ''MINUS'' [M,N]:
BLOCK 0: BEGIN
  IF M < N, THEN:
  QUIT BLOCK 0;
  LOOP AT MOST M + 1 TIMES:
  BLOCK 1: BEGIN
    IF OUTPUT + N = M, THEN:
    ABORT LOOP 1;
    OUTPUT <= OUTPUT + 1;
  BLOCK 1: END;
BLOCK 0: END.

DEFINE PROCEDURE ''FIB''[N]:
BLOCK 0: BEGIN
  IF N < 1, THEN:
  QUIT BLOCK 0;
  OUTPUT <= 1;
  IF N < 3, THEN:
  QUIT BLOCK 0;
  OUTPUT <= FIB[MINUS[N,1]] + FIB[MINUS[N,2]];
BLOCK 0: END.

FIB[10];

```

Behold, the Fibonacci numbers.

---

\*May not be true
> 7 votes

# Answer
# Mond*

* * Searching for 'Mond' gives one result (this answer notwithstanding), but it's a false positive and doesn't actually mention the language.
* Rosetta Code page. This was actually created after the challenge was posted, however a solution to the QuickSort task has existed since September 2014.
* Although mond looks very similar to JavaScript (indeed, it's quite easy to write Mond/JS polyglots), it is not a subset, superset, or re-implementation. It is its own distinct language.

Try it in your browser

***Full disclosure****: I'm involved with the development and design process of Mond to a degree and have personally implemented several major language features including user-defined operators which are demonstrated in tasks 3 & 4.*

### Task #1

The pipeline operator (`|>`) is syntax sugar that transforms the function call on the right-hand side to a function call with the value on the left-hand side inserted as the first argument. `foo |> bar()` is the same as `bar( foo )`.

```
"Simple, elegant scripting language implemented in C# for .NET/Mono" |> printLn();

```

### Task #2

```
"Hello World! This is written in Mond." |> printLn();

```

### Task #3

The code for this task assumes several things:

1. The range of numbers will be entered on a single line
2. The upper and lower bounds will be separated by a single space
3. The numbers given are integers in base-10 and contain only the chars `0-9`

Try it here

```
// parse a string to a number
fun toNumber( str ) {
    var n = 0, pow = str.length();

    for( var i = 0; i < str.length(); ++i )
        n += ( str.charCodeAt( i ) - 48 ) * ( 10 ** --pow );

    return n;
}

fun map( arr, fn ) {
    var ret = [ ];

    foreach( var item in arr )
        fn( item ) |> ret.add();

    return ret;
}

// user-defined operator to create an upper-bound inclusive range a-la Ruby
// (i.e. 1 .. 5 produces [ 1, 2, 3, 4, 5 ])
seq( .. )( start, end ) {
    for( var i = start; i <= end; ++i )
        yield i;
}

// read a line from STDIN, trim leading and trailing whitespace,
// split the string to an array, map the array to parse all strings to numbers.
var nums = readLn().trim().split( " " ) |> map( toNumber );

// nums[0] .. nums[1] makes use of the user-defined operator declared on line 22.
// nums[0] is the lower bound, nums[0] is the upper bound.
foreach( var n in nums[0] .. nums[1] ) {
    if( n % 2 != 0 ) printLn( n );
}

```

### Task #4

This task demonstrates user-defined operators, which allow the programmer to define any arbitrary operator (so long as it doesn't already exist) just like a function, and use it as they would any other operator. They come in unary and binary flavours.

Try it here.

```
// forward function compositing user-defined operator.
// the function on the right-hand side is called with
// the result of the function on the left-hand side.
fun( >>> )( fn1, fn2 ) {
    return fun( ...args ) {
        return fn1( ...args ) |> fn2();
    };
}

// the mythical "goes down to" operator of legend.
// a lazy sequence that returns all numbers starting from 'hi'
// down to (and including) 'lo'
seq( --> )( hi, lo ) {
    for( var i = hi; i >= lo; --i )
        yield i;
}

seq map( iterable, callback ) {
    foreach( var item in iterable )
        yield item |> callback();
}

// doubles the value of n
fun double( n ) -> n *  2;

// squares the value of n (** is the power operator, a-la Python or Ruby)
fun square( n ) -> n ** 2;

// gets the sequence for 10 down to 0, passes it into
// map, which maps it through the composited function of
// double and square, which first doubles the given value
// then squares it.
var nums = ( 10 --> 0 ) |> map( double >>> square );

foreach( var n in nums )
    printLn( n );

```
> 5 votes

# Answer
# jq

None of the 14 results on codegolf.se is about the language. (`jq` (and uppercase variants) seems to be frequent statement in Pyth.)

There is jq category on Rosetta Code.

You can try it online but some of examples below need latest version 1.5.

## Task 1: The Tweet

> jq is like sed for JSON; you can use it to process structured data with the same ease that sed, awk, grep and friends let you play with text

(Shamelessly twittified the first paragraph from its site.)

## Task 2: The Hello World

```
bash-4.3$ jq -n -r '"Hello World! This is written in jq."'
Hello World! This is written in jq.

```

## Task 3: The Odd Numbers

```
bash-4.3$ jq -R 'split(" ") | range(.[0] | tonumber; .[1] | tonumber + 1) | select(. % 2 == 1)' <<< '20 25'
21
23
25

```

## Task 4: The Interesting

The ~/.mozilla/firefox/\*.default/extensions.json file containing information about the installed Firefox extensions has 0 newlines in 171 Kb on JSON data, which makes it somehow difficult to read.

Pretty print the JSON data:

```
bash-4.3$ jq '' ~/.mozilla/firefox/*.default/extensions.json

```

Doh. 8000++ lines are too long, so pass it to pager, but keep the highlighting:

```
bash-4.3$ jq -C '' ~/.mozilla/firefox/*.default/extensions.json | less -r

```

Ouch. How many extensions are there anyway?

```
bash-4.3$ jq '.addons | length' ~/.mozilla/firefox/*.default/extensions.json
58

```

Ok, but some of them are disabled. How many exactly?

```
bash-4.3$ jq '[.addons[] | select(.active | not)] | length' ~/.mozilla/firefox/*.default/extensions.json
7

```

Some of them are quite abandoned and not work with current Firefox anymore:

```
bash-4.3$ jq -r '.addons[] | [.defaultLocale.name, (.targetApplications[] | select(.id == "{ec8030f7-c20a-464f-9b0e-13a3a9e97384}"))] | select(.[1].maxVersion | gsub("[^\\d.]"; "") | tonumber < 38.0) | .[0]' ~/.mozilla/firefox/*.default/extensions.json
Unity Desktop Integration
Unity Websites integration
Ubuntu Firefox Modifications

```

(This later is not true. For some reason extensions.json contains other version ranges than the extensions' install.rdf. But that is not jq's fault anyway.)
> 5 votes

# Answer
# ooc

Yeah, I'm about a month late. So what???

## Task 1

> ooc is a programming language that compiles down to C99 that has an elegant syntax, and supports both high- and low-level development.

135 bytes! That was close!

Also, fake bonus points for ooc's insanely cool ASCII-art logo:

```
           +(NNhBBhss+'                  ~+'(sNBND=~.
           -(=NDhNN+=+=' .   .  .    . .+='+~DNND+=.
           .+-DBDDh+(D-<'      .....  -<+ (=~DNh+<(
            '+<NNNB=~=z-(<-<<(+('-'~<<=- .+'sBNh~+
             (~=NNND+=DB~(-.    . .    ...(=BNB+s--      ALL YOUR
             .=-=DBDz-'~. .   ..'. .... '  '~s<<szh<.
               <(~'. .  .  ..sD='-~'-'-DDs.. . .~sD(     CODEBASE
            . ~+'  '  .-(-..sBNB~(~~+=hNNNz'<<z='-z(
           . .=. -DDz<~s~  'BNNN=~+<shNNNND(sNNNh~(+    ARE BELONG
            .=<.(NNNNDDs. (hhs+=s=hNDNNBNBBs<BNND<<=.
            .'-'~sNNs((- .''. ' -~NNDz+((~---~sB<'''.     TO US!
                '=(++(-..  . ...-~+B~'....'.''-+(     .
                -=z<<'.. .'-...'-~hz~-'.''''-~-<=
                 .~+~s~  ~z<~'-'--hN=~((~'---(~~z~
                   (+<-.'+=''''~(+=Bz--~(((=+s+~(s
  IT'S OVER      . '+-..~<----~-+(sBNh+zBNNBNh+<z'
                   .<-'--''(<~=B=hDDD=<<<++=++<=.
  9000 BUGS!     .. s~..'h=++ss=D<<~+B(<(+<=Nz=+
                    +'.''+NNDN(+z(((sB<((s+hNh<+
                   .= -~(~(zDNz+z+zhNDz=szhhBz++.       MADNESS?
                   '+. ss<'~=NBNBBDzBzhshDD=+<<-
                   -= . +s~-(+==hhDBNBDDs==hz+<     THIS! IS! LLAMA!
                 '(<-  . '~~(<+<=+<sz=+sshzs(..
                .+<.    '('-~(((((<++(<<((= .
                 .--.. ....'.'.'.'..''..'-..

```

## Task 2

```
"Hello, world!" println()

```

## Task 3

```
import text/StringTokenizer
import structs/ArrayList
input := stdin readLine() split(' ', false)
(begin, end) := (input[0] toInt(), input[1] toInt())
for (i in begin..end+1) {
    if (i % 2 != 0) { "%d " printf(i) }
}
println()

```

Pretty straightforward implementation. Also, this showcases an interesting aspect of ooc: method calls use spaces as delimiters, not dots. For instance, notice `stdin readLine() split(' ', false)` above. In most languages, that would be written as `stdin.readLine().split(' ', false)`, but ooc reserves that for call chaining (scroll down to the code example).

## Task 3

This showcases my favorite ooc feature: type matching. It's like pattern matching. In an OO language. Awesome.

```
import structs/ArrayList
import math/Random

Animal: abstract class {
    makeNoise: abstract func
}

Sheep: class extends Animal {
    init: func
    makeNoise: func {
        "Baaaaaaa!" println()
    }
}

Wolf: class extends Animal {
    init: func
    makeNoise: func {
        "Hooooowl!" println()
    }
}

animals := [Sheep new(), Sheep new(), Sheep new()] as ArrayList<Animal>
badNumber := Random randRange(0, 3)
animals[badNumber] = Wolf new()
animal: Animal

"Enter a number between 0 (inclusive) and 3 (exclusive)" println()
inputNumberString := stdin readLine()
for (chr in inputNumberString) {
    if (!(chr.digit?())) {
        "NUMBER, not CHARACTER! Can't you read!?" println()
        exit(1)
    }
}
inputNumber := inputNumberString toInt()
try {
    animal = animals[inputNumber]
} catch (e: OutOfBoundsException) {
    "I said a number between one and three, you idiot!" println()
    exit(1)
}
"Animal noise:" println()
animal makeNoise()
match (animal) {
    case sheep: Sheep => { "It's a stupid, annoying sheep!" println() }
    case wolf: Wolf => { "AHH! A WOLF! You got eaten. :/ R.I.P." println() }
}

```
> 4 votes

---
Tags: popularity-contest, multiple-holes
---


title: Incremental Game Time Format

text:
# Question
Title: Incremental Game Time Format
## Incremental Game Time Format

### Goal

Incremental games often have a countdown timer expressing the days, hours, minutes and seconds until a task is complete. Depending on the space available, they can be formatted as:

```
2d 13h
23h 59m 48s
14m
3h 0m 0s

```

The goal of this code golf is to write a function or program that performs this formatting.

### Inputs

* The total number of seconds.
* The maximum number of segments to output.

### Output

* Segments include:
    + **0w** weeks
    + **0d** days
    + **0h** hours
    + **0m** minutes
    + **0s** seconds
* Each segment is separated by a single space.
* Displayed segments must be contiguous. For example, you will not show hours and seconds without showing minutes, even if there are zero minutes.
* Single-digit values do not have leading zeros, though a value of zero must be shown as `0`.
* Values are rounded down.
* The first segment displayed is the first non-zero value.

### Test Cases

```
seconds  segments  output
     0      1      0s
   123      1      2m
   123      2      2m 3s
   123      3      2m 3s
 82815      3      23h 0m 15s
307891      2      3d 13h
307891      4      3d 13h 31m 31s
604800      1      1w
604800      6      1w 0d 0h 0m 0s

```

### Winning

The lowest byte-count solution in one week will win "acceptance".

### Edits

* Clarified which segment is first, as shown in examples.
* Added test case 4 as per request.

# Answer
# CJam (snapshot), ~~41~~ 38 bytes

```
q~"<<^X^G"{imd\}%W%"wdhms":s.+_{0=}#><S*

```

The above uses caret notation, since two of the characters are unprintable.

*Thanks to @Sp3000 for golfing off 2 bytes.*

### Testing

The latest stable release (0.6.5) has a bug that can cause `{}#` to return Integers instead of Longs. Quite paradoxically, this can be circumvented by casting to integer (`i`).

To run this with code with the online interpreter, click this permalink or copy the code from this paste.

Alternatively, you can download and build the latest snapshot by executing the following commands:

```
hg clone http://hg.code.sf.net/p/cjam/code cjam-code
cd cjam-code/
ant

```

You can create the CJam file like this:

```
base64 -d > game-time.cjam <<< cX4iPDwYByJ7aW1kXH0lVyUid2RobXMiOnMuK197MD19Iz48Uyo=

```

### How it works

```
q~        e# Read an evaluate the input.
"<<^X^G"  e# Push the string corresponding to the array [60 60 24 7
{         e# For each character:
  i       e#   Replace it by its code point.
  md      e#   Push divisor and residue of the division by that code point.
  \       e#   Swap their order.
}%
W%        e# Reverse the resulting array.
"wdhms":s e# Push ["w" "d" "h" "m" "s"].
.+        e# Perform vectorized concatenation.
_         e# Push a copy.
{0=}#     e# Find the index of the first pair with positive integer.
>         e# Remove the preceding pairs.
<         e# Truncate to the number of pairs specified in the input.
S*        e# Join, separating by spaces.

```
> 7 votes

# Answer
# Java, ~~197~~ 191 bytes

```
String p(int s,int m){String a[]={s%60+"s",(s/=60)%60+"m",(s/=60)%24+"h",(s/=24)%7+"d",(s/7)+"w"},b="",z="";for(s=5;s>0&&a[--s].charAt(0)=='0';);for(;s>=0&&--m>=0;z=" ")b+=z+a[s--];return b;}

```

I just noticed that Java supports declaration like `String a[]`. This allowed me to pull the declaration of `b` and `z` into the same line, which saved me from writing `String` again.
> 6 votes

# Answer
# C, 134 127 110 104 103 bytes

New Version:

```
a,e=5;f(n,x){for(;e;n%=a)a=(int[]){1,60,3600,86400,604800}[--e],x>e?printf("%u%c ",n/a,"smhdw"[e]):0;}

```

Previous Version:

```
#define p(a) x>--e?printf("%u%c ",n/a,"smhdw"[e]):0;n%=a;
e=5;f(n,x){p(604800)p(86400)p(3600)p(60)p(1)}

```
> 5 votes

# Answer
# Pyth, ~~39~~ 43 bytes

```
jd_>vz+V?u?GeGPG+m%~/QddCM"<<"Q)Q]0"smhdw

```

edit: +4 chars, because I forgot the `0s` test case.

This includes 2 unprintable chars. Get the actual code and try it online: Demonstration

### Explanation:

```
                                         z = 1st input line (segments, as string)
                                         Q = 2nd input line (time, as int)
                         "<<.."          string with 4 chars
                       CM                convert to ASCCI-values => [60,60,24,7]
                m                        map each d of ^ to:
                   /Qd                     Q / d
                  ~                        update Q, but use the old value for
                 %  Q d                    Q mod d
                                         this gives [sec, min, hour, day]
               +               Q         add Q (week)
        u                       )        apply the following expression to G,
                                         starting with G = [s,m,h,d,w], until
                                         G stops changing:
         ? eG                              if eG != 0:
          G                                  update G with G (stop changing)
                                           else:
             PG                              update G with G[-1]
                                         this gets rid of trailing zeros
      +V                         "smhdw  vectorized add with "smhdw"
   >vz                                   only use the last eval(z) items
  _                                      reverse order
jd                                       join by spaces and print

```
> 4 votes

# Answer
## Python 2.7 - ~~181~~ ~~178~~ 174 bytes

My first attempt to golf something.

```
def I(s,M):
 z=[0]*5;j=0
 for i in [604800,86400,3600,60,1]:z[j],s=s/i,s%i;j+=1
 l=[z.index(n)for n in z if n][0]
 return" ".join([str(i)+n for n,i in zip('wdhms',z)][l:l+M])

```
> 3 votes

# Answer
# Julia, 158 bytes

I'm sure this could be shorter with a more clever approach, but this is what I have for now.

```
(s,g)->(j=0;p=cell(5,1);for i=[604800,86400,3600,60,1] p[j+=1],s=s÷i,s%i end;z=findfirst(p);z>0?join([string(p[i],"wdhms"[i])for i=z:min(z+g-1,5)]," "):"0s")

```

This creates an unnamed function that accepts two integers as input and returns a string. To call it, give it a name, e.g. `f=(s,g)->...`.

Ungolfed + explanation:

```
function f(s, g)
    # Initialize an array and an index
    p = cell(5, 1)
    j = 0

    # Loop over the number of seconds in a week, day, hour,
    # minute, and second
    for i in [604800, 86400, 3600, 60, 1]
        # Set the jth element in p to be the quotient and s
        # to be the remainder of i into s
        p[j+=1], s = s ÷ i, s % i
    end

    # Get the index of the first nonzero value in p
    z = findfirst(p)

    if z > 0
        # We start the string at the first nonzero value
        # and continue until we hit the desired number of
        # units (z+g-1) or the maximum number of units (5),
        # whichever comes first. The appropriate unit is
        # appended to each value and the values are then
        # joined with a space.
        join([string(p[i], "wdhms"[i]) for i in z:min(z+g-1,5)], " ")
    else
        # If there are no nonzero values in p, we just
        # have 0 seconds
        "0s"
    end
end

```

Examples:

```
julia> f(82815, 6)
"23h 0m 15s"

julia> f(604800, 4)
"1w 0d 0h 0m"

```
> 2 votes

# Answer
# rs, 367 bytes

```
^(\d+)/(_)^^(\1)
(_*) (\d)/\1!\2
_{60}/#
#{60}/@
@{24}/:
:{7}/;
(_+)/(^^\1)s
(#+)/(^^\1)m
(@+)/(^^\1)h
(:+)/(^^\1)d
(;+)/(^^\1)w
([a-z])/\1
w ((\d+[^\dd])|!)/w 0d \1
d ((\d+[^\dh])|!)/d 0h \1
h ((\d+[^\dm])|!)/h 0m \1
(m|^) ?!/\1 0s!
!(\d+)/!(_)^^(\1)
#
+#(\d+)([a-z]) ?(.*)!(_*)/\1\2 #\3!\4@
#/
(@+)/ (_)^^((^^\1))
!(_+) \1(_*)/!\2
_+ _+/
+\d+[a-z] ?!_/!
 *!/
^$/0s

```

Live demo and all test cases.

Messy, messy, messy...

Takes about 3-7 seconds to execute the test cases on Chrome for Android. Do *not* use debug mode, which can freeze your browser in this case because of all the output that would be printed.
> 1 votes

# Answer
## Scala, 147 bytes

```
def p(s:Int,i:Int)=List(s/604800+"w",s/86400%7+"d",s/3600%24+"h",s/60%60+"m",s%60+"s").dropWhile(k=>k.head=='0'&&k.tail!="s").take(i).mkString(" ")

```
> 1 votes

# Answer
## C#, 239 237 170 164 bytes

This is no where near as compact as other solutions, but I can't pose this challenge without having a stab at it myself.

This latest iteration was inspired by ESC's answer.

Indented for clarity:

```
string G(int s,int n){
    int[]x={s%60,(s/=60)%60,(s/=60)%24,(s/=24)%7,s/7};
    for(s=5;x[--s]==0&s>0;);
    var o="";
    while(n-->0&s>=0)
        o+=" "+x[s]+"smhdw"[s--];
    return o.Trim();
}

```
> 0 votes

---
Tags: code-golf, date
---


# Question
Title: Shortest Longest Common Subsequence Code
Your task to to solve the SLCSC problem, which consists in finding the shortest possible code to solve the Longest Common Subsequence problem.

A valid solution to the LCS problem for two or more strings **S1, … Sn** is any string **T** of maximal length such that the characters of **T** appear in all **Si**, in the same order as in **T**.

Note that **T** does not have to be a sub*string* of **Si**.

### Example

The strings `axbycz` and `xaybzc` have 8 common subsequences of length 3:

```
abc abz ayc ayz xbc xbz xyc xyz

```

Any of these would be a valid solution for the LCS problem.

### Details

Write a program or a function that solves the LCS problem, as explained above, abiding the following rules:

* The input will consist of two or more strings containing only lowercase letters.

You may read those strings as an array of strings or a single string with a delimiter of your choice.
* Your code must output any single one of the possible solutions to the problem, optionally followed by a linefeed or surrounded by quotes.
* You may assume that the strings are shorter than 1000 characters and that there are at most 20 strings.

Within these limits, your code should work as expected *in theory* (given unlimited time and memory).
* Your code must complete the combined test cases of the next section in under an hour on my machine (Intel Core i7-3770, 16 GiB RAM).

**Approaches that simply iterate over all possible subsequences will not comply with the time limit.**
* Using built-ins that trivialize this task, such as `LongestCommonSequence`, is not allowed.

Standard rules apply.

### Test cases

```
a
ab

```

Output: `a`

---

```
aaaaxbbbb
bbbbxcccc
ccccxaaaa

```

Output: `x`

---

```
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl

```

Output: `hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrl` or any other common subsequence of the same length

---

```
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg

```

Output: `icsvllvjnlktywuar` or any other common subsequence of the same length

---

```
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr

```

Output: `krkk` or any other common subsequence of the same length

---

```
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja

```

Output: `code` or any other common subsequence of the same length

---

```
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt

```

Output: `golf` or any other common subsequence of the same length

---

```
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp

```

Output: the empty string

# Answer
# CJam, 31

```
q~L{_:&\f{_2$f#:).>j+}{,}$W>s}j

```

Try it online

9 bytes golfed thanks to Dennis!

**Explanation:**

This algorithm tries every possible character for the first position of the subsequence, replaces each string with the substring after the first occurrence of that character, and then calls itself recursively (with memoization).

```
q~          read and evaluate the input (taken as an array)
L{…}j       execute block with recursive memoization and no starting values
  _         duplicate the array of strings
  :&\       intersect the strings as character sets and move before the array
             these are all the possible characters for the sequence
  f{…}      for each character and the array
    _2$     duplicate the array and the character
    f#      find the character position in each string
    :)      increment the positions (to skip the character)
    .>      slice each string starting at the corresponding position
    j       call the j block recursively
    +       concatenate the starting character with the result
  {,}$      sort resulting strings (one for each character) by length
  W>        keep only the last element, if any
  s         convert (from 0/1-string array) to string

```
> 4 votes

# Answer
# Python - ~~665~~ 644

Indentation levels:

```
1: space
2: tab
3: tab + space
4: 2 tabs
5: 2 tabs + space

```

The code defines a function `o`, which takes a list of strings as arguments and returns one of the LCS's for the strings.

```
def o(t):
 t=[[y for y in x if y in reduce(lambda x,y:x.intersection(y),t,set(t[0]))]for x in t];l=map(len,t);C=[0]*reduce(lambda x,y:x*-~y,l,1);y=lambda z:[x-1for x in z];m=len(t);e=enumerate
 def g(h):
    r,x=0,1
    for k,j in e(h):r+=-~j*x;x*=-~l[k]
    return r
 def f(h):
    i=len(h)
    if i==m:
     b=g(h);c=t[0][h[0]]
     for k,j in e(h):
         if t[k][j]!=c:break
     else:C[b]=1+C[g(y(h))];return
     r=0
     for k,_ in e(h):a=h[:];a[k]-=1;r=max(r,C[g(a)])
     C[b]=r;return
    for j,_ in e(t[i]):f(h+[j])
 def p(h):
    if min(h)==-1:return''
    v=C[g(h)]
    for k,_ in e(h):
        a=h[:];a[k]-=1
        if v==C[g(a)]:return p(a)
    return p(y(h))+t[0][h[0]]
 f([]);return p(y(l))

```

Test code:

```
tests = [
"""
a
ab
""",
"""
aaaaxbbbb
bbbbxcccc
ccccxaaaa
""",
"""
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
""",
"""
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
""",
"""
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
""",
"""
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
""",
"""
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
""",
"""
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
"""
]

for s in tests:
 print o(s.strip().split())

```

Time it takes to run the tests on my computer:

```
$ time python 52808-shortest-longest-common-subsequence-code-golfed.py
a
x
hecbpyhogntqtpcqgkxchpsieuhbncvhuqndbjqmclchqyfhtdvgoysuhrrl
icsvllvanlktywuar
krkk
code
golf

        9.03 real         8.99 user         0.03 sys

```
> 5 votes

# Answer
# Pyth, ~~59~~ ~~58~~ ~~55~~ 35 bytes

```
L&@Fb?+yPMbeeb@FeMbeolNmyXJbdP@bdlb

```

Cut a whopping 20 bytes thanks to @isaacg!

55 byte version:

```
DCHR?k!&.AH@FH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

```

Cut off 3 bytes by changing `.U@bZ` to `@F` (the fold operator).

58 byte version:

```
DCHR?k!&.AH.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

```

Cut off a byte by changing the format of a boolean conditional.

59 byte version:

```
DCHR?k|!.AH!.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

```

This was hard! Python kept segfaulting! Pretty sure it was some kind of bug, but I couldn't get a minimal test case. Oh well.

I based the algorithm off of this one. Which is fine, except that that one is designed for only two strings. I had to tweak it a bit to make it work on more. Then, the last test case was taking too long, so I had to add an additional check to exit the recursion if there are no more common characters.

It's pretty slow, but *should* take less than an hour (hopefully). I'm testing on my Core i3 with 6 GB of RAM, so your 16-GB Core i7 should blow through this. :)

I also took advantage of Pyth's auto-memoizing functions to make it a bit faster.

**EDIT**: @Dennis said it passes!

To test it, add the following line:

```
CQ

```

and give it a list of strings via standard input (e.g. `['a', 'ab']`).

## Explanation for the 35 byte version:

WIP.

## Explanation for the 55 byte version:

```
DCH                                                        define a function C that takes a list of strings H
   R                                                       return the following expression
    ?                                                      if
      !&.AH@FH                                             there are no more common letters OR all the strings are empty
     k                                                     return the empty string
              ?          ql{medH1                          else if the last character of every string is equal
               +Cm<1dHeeH                                  return the result of adding the last character to recursion with every item without its last character
                                 h.MlZ.eC++<Hk]<1b>HhkH    otherwise, return the largest result of recursing len(H) times, each time with one element's last character cut off

```
> 4 votes

# Answer
# C, ~~618~~ 564 bytes

```
d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y=n-1,z,i,t,m=0,w=1;for(;y;)x[y--]=999;for(;y<N;y++){for(i=0;i<n&&s[i]==R[y][i];i++);if(i/n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)t&=!!*j[i];y&=j[i]-s[i]>x[i]?z=0,1:0;}t&=!y;I:if(t){if(z)for(i=0;i<n;i++)x[i]=j[i]-s[i];d++,t+=L(j,n),d--,m=t>m?a=c,t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

```

And here it is unraveled, for "readability":

```
d,M,N,A[9999][2];
char*(R[9999][20]),b[1000];
L(char**s,n){
    char*j[20],c,a=0;
    int x[n],y=n-1,z,i,t,m=0,w=1;
    for(;y;)
        x[y--]=999;
    for(;y<N;y++){
        for(i=0;i<n&&s[i]==R[y][i];i++);
        if(i/n){
            a=A[y][0];
            m=A[y][1];
            w=0;
            if(m+d<M||!a)
                goto J;
            else{
                c=a;
                goto K;
            }
        }
    }
    for(c=97;w&&c<'{';c++){
        K:
        t=1,
        y=1,
        z=1;
        for(i=0;i<n;j[i++]++){
            for(j[i]=s[i];*j[i]-c;j[i]++)
                t&=!!*j[i];
            y&=j[i]-s[i]>x[i]?z=0,1:0;
        }
        t&=!y;
        I:
        if(t){
            if(z)
                for(i=0;i<n;i++)
                    x[i]=j[i]-s[i];
            d++,
            t+=L(j,n),
            d--,
            m=t>m?a=c,t:m;
        }
    }
    if(w){
        for(y=0;y<n;y++)R[N][y]=s[y];
        A[N][0]=a;
        A[N++][1]=m;
    }
    J:
    if(d+m>=M)
        M=d+m,b[d]=a;
    if(!d)
        N=0,M=0,puts(b);
    return m;
}

```

Ladies and gentlemen, I've made a horrible mistake. It *used* to be prettier... And goto-less... At least now it is **fast**.

We define a recursive function `L` that takes as input an array `s` of arrays of characters and the number `n` of strings. The function outputs the resulting string to stdout, and incidentally returns the size in characters of that string.

### The Approach

Though the code is convoluted, the strategy here is not all too complex. We start with a rather naive recursive algorithm, which I will describe with pseudocode:

```
Function L (array of strings s, number of strings n), returns length:

Create array of strings j of size n;

For each character c in "a-z",
    For each integer i less than n,
         Set the i'th string of j to the i'th string of s, starting at the first appearance of c in s[i]. (e.g. j[i][0] == c)
         If c does not occur in the i'th string of s, continue on to the next c.
    end For

    new_length := L( j, n ) + 1; // (C) t = new_length
    if new_length > best_length
        best_character := c; // (C) a = best_character
        best_length := new_length; // (C) m = best_length
    end if
end For

// (C) d = current_depth_in_recursion_tree
if best_length + current_depth_in_recursion_tree >= best_found
     prepend best_character to output_string // (C) b = output_string
     // (C) M = best_found, which represents the longest common substring found at any given point in the execution.
     best_found = best_length + current_depth;
end if

if current_depth_in_recursion_tree == 0
    reset all variables, print output_string
end if

return best_length

```

Now, this algorithm on its own is pretty atrocious (but can be fit in around ~230 bytes, I've found). This is not how one gets speedy results. This algorithm scales incredibly poorly with string length. This algorithm *does*, however, scale fairly well with larger numbers of strings. The last test case would be solved virtually instantly, since no strings in `s` have any characters `c` in common. There were two main tricks I've implemented above that resulted in an incredible speed increase:

* At every call to `L`, check if we've been given this same input before. Since in practice information is passed around via pointers to the same set of strings, we don't *actually* have to compare strings, just locations, which is great. If we find that we've gotten this information before, there's no need to run through the calculations (most of the time, but getting output makes this a bit more complicated) and we can get away with just returning the length. If we do *not* find a match, save this set of input/output to compare to future calls. In the C code, the second `for` loop attempts to find matches to the input. Known input pointers are saved in `R`, and the corresponding length and character output values are stored in `A`. This plan had a drastic effect on runtime, especially with longer strings.
* Every time we find the locations of `c` in `s`, there's a chance we know right off the bat that what we've found isn't optimal. If every location of `c` appears *after* some known location of another letter, we **automatically know** that this `c` does not lead to an optimal substring, because you can fit one more letter in it. This means that for a small cost, we can potentially remove several hundred calls to `L` for large strings. In the above C code, `y` is a flag set if we automatically know that this character leads to a suboptimal string, and `z` is a flag set if we find a character that has exclusively earlier appearances than any other known character. The current earliest appearances of characters are stored in `x`. The current implementation of this idea is a bit messy, but nearly doubled performance in many instances.

With these two ideas, what didn't finish in an hour now took about 0.015 seconds.

There are probably plenty more little tricks that can speed up performance, but at this point I started worrying about my ability to golf everything. I'm still not content with the golf, so I'll likely come back to this later!

### Timings

Here's some testing code, which I invite you to try online:

```
#include "stdio.h"
#include "time.h"

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int main(int argc, char** argv) {
    /* Our test case */
    char* test7[] = {
        "nqrualgoedlf",
        "jgqorzglfnpa",
        "fgttvnogldfx",
        "pgostsulyfug",
        "sgnhoyjlnfvr",
        "wdttgkolfkbt"
    };

    printf("Test 7:\n\t");
    clock_t start = clock();

    /* The call to L */
    int size = L(test7, SIZE_ARRAY(test7));

    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("\tSize: %d\n", size);
    printf("\tElapsed time: %lf s\n", dt);

    return 0;
}

```

I ran the OP's test cases on a laptop equipped with a 1.7 GHz Intel Core i7 chip, with an optimization setting of `-Ofast`. The simulation reported a peak of 712KB required. Here's an example run of each test case, with timings:

```
Test 1:
    a
    Size: 1
    Elapsed time: 0.000020 s
Test 2:
    x
    Size: 1
    Elapsed time: 0.000017 s
Test 3:
    hecbpyhogntqppcqgkxchpsieuhbmcbhuqdjbrqmclchqyfhtdvdoysuhrrl
    Size: 60
    Elapsed time: 0.054547 s
Test 4:
    ihicvaoodsnktkrar
    Size: 17
    Elapsed time: 0.007459 s
Test 5:
    krkk
    Size: 4
    Elapsed time: 0.000051 s
Test 6:
    code
    Size: 4
    Elapsed time: 0.000045 s
Test 7:
    golf
    Size: 4
    Elapsed time: 0.000040 s
Test 8:

    Size: 0
    Elapsed time: 0.000029 s

Total time: 0.062293 s

```

In golfing, I hit performance rather significantly, and since people seemed to like the brute speed (0.013624 s to complete all test cases combined) of my previous 618-byte solution, I'll leave it here for reference:

```
d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y,z,i,t,m=0,w=1;for(y=0;y<n;y++)x[y]=999;for(y=0;y<N;y++){for(i=0;i<n;i++)if(s[i]!=R[y][i])break;if(i==n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)if(!*j[i]){t=0;goto I;}if(j[i]-s[i]>x[i])z=0;if(j[i]-s[i]<x[i])y=0;}if(y){t=0;}I:if(t){if(z){for(i=0;i<n;i++){x[i]=j[i]-s[i];}}d++,t+=L(j,n),d--,m=t>m?(a=c),t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

```

The algorithm itself is unchanged, but the new code relies on divisions and some trickier bitwise operations that end up slowing the whole thing down.
> 4 votes

# Answer
# Python 2, 285

Code:

```
import re
def f(s,a,b):
  if b==[]:return s+f('',[],a)
  if a==[]:return s+max([f(b[0][i],[b[0][i+1:]],b[1:]) for i in range(len(b[0]))],key=len) if b[0]!='' else ''
  return max([f(s,a+[b[0][i.start()+1:]],b[1:]) for i in re.finditer(s[-1],b[0])],key=len) if ~b[0].find(s[-1]) else ''

```

Usage:

```
print f('',[],['axbycz','xaybzc'])

```

Explanation:

This is a recursive function. `s` is the character we are looking for. `a` contains list of strings sliced after `s`. `b` contains list of strings untouced yet. `f` returns the longest common string.

The first condition checks if we finished to go through all the strings. if so, it means `s` is common character, and it returns `s` and looking for more common characters.

The second condition checks if we don't start to go through any string, meaning we don't even have a character (`a==[]` is equivalent to `s==''`). if so we check each character of the first string in `b`.

The last line moves the first string in `b` to `a`, by finding each occurrence of `s` in this string.

On the first call, `s` should be empty string. `a` should be empty list and `b` should contains all the strings.
> 1 votes

---
Tags: code-golf, string, subsequence
---