text:
Music: what's in this chord?
Input
The symbol of any triadic chord (see http://en.wikipedia.org/wiki/Chord_(music)#Triads).
Output
The notes constituting the given chord.
Examples
Input: AM
Output: A C# E
Input: C#m
Output: C# E G#
Input: Db+
Output: C# F A
Input: C0
Output: C D# F#
Bonuses
-50 if you can also deal with seventh chords
-150 for actually playing the sound of the chord
-150 for using printable characters to show how to play the chord on a piano; example for AM:
┌─┬─┬┬─┬─┬─┬─┬┬─┲┱─┬─┬─┲━┱┬─┲━┱─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ┃┃ │ │ ┃ ┃│ ┃ ┃ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ┃┃ │ │ ┃ ┃│ ┃ ┃ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ┃┃ │ │ ┃ ┃│ ┃ ┃ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┲┛┗┱┘ │ ┗┯┛└┲┛ ┃ └┬┘└┬┘└┬┘ │
│  │  │  │  │  ┃  ┃  │  │  ┃  ┃  │  │  │  │
└──┴──┴──┴──┴──┺━━┹──┴──┴──┺━━┹──┴──┴──┴──┘

-100 for using printable characters to show how to play the chord on a guitar; example for AM:
x   o   o   o   o   o
┌───┬───┬───┬───┬───┐
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   █   █   █   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │

(see https://en.wikipedia.org/wiki/Box-drawing_character)
Rules

The result must be a command-line program or script.
The input and output can be in any form, as long as it follows a music notation standard.
A guitar or piano representation is considered valid if and only if it contains the three (triadic) or four (seventh) required notes and nothing else. The same note can be present several times in the chord.
External libraries are not allowed, except for sound generation (in which case the #include, import... directives are not added to the character count).
This is code golf, the shortest code wins!

A little bit of music theory...
In modern Western tonal music, every octave is made of twelve successive notes, often noted:
A A# B C C# D D# E F F# G G#
Or:
La La# Si Do Do# Re Re# Mi Fa Fa# Sol Sol#
In this system, we consider that two successive notes (e.g. A and A#, or E and F) are separated by one semitone. Also, the notes are kind of "looping": what immediately follows G# is A.

A chord is constituted by a few (2, 3, 4, sometimes more) notes that "sound good together". For instance, triadic chords contain three different notes, and seventh chords contain four different notes.
Let's define the four triadic chords as:

Major triad: contains the root of the chord (in this question, the note given as input), the major third for the root (4 semitones higher than the root), and the perfect fifth for the root (7 semitones higher than the root); this can be symbolized 0-4-7
Minor triad, symbolized 0-3-7
Augmented triad, symbolized 0-4-8
Diminished triad, symbolized 0-3-6

So for example, if you want to make a C major triad, noted C, CM, Cmaj, you will need three noted:

0: the root, in this case a C
4: the minor third, 4 semitones higher than the root; that's an E
7: the perfect fifth, 7 semitones higher than the root: a G

This is what the 0-4-7, 0-3-7, 0-4-8 and 0-3-6 notations used above mean! For the seventh chords, use the following pattern:

That's it for today! Now, amaze me with amazing code... If you have any question, add some comments below.

Kind-of the inverse  of this older question.

Yes, I found it too when checking for duplicates... but even if both questions are about chords, the way to the solution is quite different!

It might be worth adding an explanation including the formulas for the chords in integer notation for non musicians. Integer notation refers to everything in semitones. Major chord (Example AM): 0,4,7. Minor chord (example C#m): 0,3,7. C diminished (Example Co, or as you call it C0) 0,3,6 (note that the correct representation is C Eb Gb, but for this challenge I guess we can assume both this and C D# F# are acceptable.) The formula for an augmented chord (Example Db+) is 0,4,8 and your example is wrong as it doesn't even contain a Db. As written it is a B+ which is equivalent to a D#+ or G+

Also, when you consider adding a seventh to all of these triads, there are a bewildering number of possibilities. Can we assume the challenge is limited to the dominant seventh? (formula 0,4,7,10) Example G B D F.

Finally, does the chord inversion on the piano have to be one with the root as the lowest note? I assume any valid inversion is acceptable on the guitar, as the "standard" inversion on the piano is often impossible on the guitar. Note that one of the most inversions for C7 on the guitar does not even contain a G: http://music.stackexchange.com/questions/12205/why-does-the-c7-chord-on-guitar-omit-the-g-note-5th-in-open-position.

Also, shortest code will result from use of the same chord shape for all guitar chords of the same type, barred. So Ab will be an A shape barred at the 11th fret. Is it Ok to put a number or do we have to draw 11 frets? All in all, it's a lot of things to think about. You may want to simplify the bonuses.

By the way, I do like the question :-)

@steveverrill: a lot of constructive comments... I am editing the question :)

@steveverrill: phew! I added some precisions and a bit of music theory. The result is terribly long, and I'm not sure it will be of much help for music newbies...

Hmm.. your augmented chord is still wrong. C# is enharmonic to Db, but Db+ is Db F A there's no D# or G in there. That's perhaps a little more theory than necessary, the formulas were the important part. If you really want to include all eight of the seventh chords listed in wikipedia you should specify the input.  I assume the ascii-art output of piano and guitar is flexible.

Oops indeed. Edited.

"The input and output can be in any form, as long as it follows a music notation standard." How much are we allowed to restrict it? Can we say only C# is accepted and neglect the equivalent Db, or vice versa? Can we use/require h in place of #? Do we have to support both of CM Cmaj or just one?

@algorithmshark: it means you can follow the standard(s) of your choice, as long as you remain consistent.

What do you think about including F# in the tonal scale?

I feel like I've learned more about music theory here than I've learned from lessons.

The coolest problem on this site !

You could also add a bonus for accepting a key, major/minor/augmented/diminished, and a figured bass to determine the chord.

Just an FYI, the guitar chord you have as AM is more like Bb...

BBC BASIC
Emulator at bbcbasic.co.uk
Rev 1, 340 - 150 keyboard - 150 playing = 40
Here's the latest version, in which I managed to include the following enhancements while lengthening by only a few more characters.
Input can be edited comfortably on the screen before pressing return (I was using GET$ before to get single keypresses, because BBC Basic does not let you access a single character from a string as if the string was an array. Now I use the rather bulky MID$ function to extract a string of one character from within the string.
Both sides of keyboard displayed as well as the full line between E and F.
To compensate for the characters added by the above, I rearranged the program to eliminate unnecessary print statements, and deleted some white space which at first sight looked like it couldnt be deleted. IN BBC Basic all built in functions are reserved words, and you can put a variable name right before them with no space in between. Variable names are not allowed to start with a reserved word. In order to make the program less confusing to read I changed all variables to lower case.
Although the presentation looks much better, the following program is actually  fully golfed already.  (See correction below.) Generally newlines and colons are interchangeable, except when an IF statement is used. In that case all statements on the same line (separated by colons) with be executed conditionally. Statements after the newline are not controlled by the IF and will always be executed.
Program rev 1 340 characters
  a$="C#D#EF#G#A#B0Mm+"
  INPUTx$
  r=INSTR(a$,LEFT$(x$,1))-1
  c=INSTR(a$,MID$(x$,2,1))
  IFc=2c=INSTR(a$,MID$(x$,3)):r=r+1
  t=(r+4-c MOD2)MOD12
  f=(r+c DIV2)MOD12
  v=1
  FORn=-1TO11
  c=1-(n<0ORn=4ORn=11)*5
  b$=MID$(a$,n+1,1)
  IFb$="#"c=11:b$=MID$(a$,n,1)+b$
  c$=MID$("   _______--|__",c,5)
  IFr=n ORt=n ORf=n c$=c$+b$:SOUNDv,-15,100+n*4,99:v=v+1
  PRINTc$
  NEXT

CORRECTION: RT Russell's BBC BASIC for Windows allows you to eliminate some newlines and colons, bringing the total down to 327, see below. Also it tokenises the keywords into single characters before saving, bringing it down to 279.
  a$="C#D#EF#G#A#B0Mm+"INPUTx$
  r=INSTR(a$,LEFT$(x$,1))-1c=INSTR(a$,MID$(x$,2,1))IFc=2c=INSTR(a$,MID$(x$,3))r=r+1
  t=(r+4-c MOD2)MOD12f=(r+c DIV2)MOD12v=1FORn=-1TO11c=1-(n<0ORn=4ORn=11)*5b$=MID$(a$,n+1,1)IFb$="#"c=11b$=MID$(a$,n,1)+b$
  c$=MID$("   _______--|__",c,5)IFr=n ORt=n ORf=n c$=c$+b$SOUNDv,-15,100+n*4,99v=v+1
  PRINTc$
  NEXT

Output rev 1

Rev 0, 337 - 150 keyboard - 150 playing = 37
A$="C#D#EF#G#A#B0Mm+":X$=GET$:R=INSTR(A$,X$)-1:X$=GET$:IF X$="#"R=R+1:X$=GET$
C=INSTR(A$,X$):T=(R+4-C MOD2)MOD12:F=(R+C DIV2)MOD12:V=1:PRINT"______"
FORN=0 TO 11
C=1-(N=4)*12:B$=MID$(A$,N+1,1): IF B$="#" C=7: B$=MID$(A$,N,1)+B$
PRINT MID$("    __---|________",C,6);:IF(R-N)*(T-N)*(F-N)=0 PRINT B$;:SOUND V,-15,100+N*4,99:V=V+1
PRINT
NEXT

This is a similar concept to my Arduino answer, but I always knew I could beat that byte count with BBC basic. Only recognises sharps, but considers B# invalid,you must put C. This could be fixed if it was really considered important.
I abandoned the idea of guitar and concentrated on improving the keyboard. It now runs from C to B, and I've added in the left side of the keyboard and the line between E and F. That costs 28 characters. The right hand side wouldn't be much more.
Here's some sample output, an A# diminished chord (which has a pretty freaky sound in this inversion) and a B major chord. Note that the input is not echoed to the screen. As per the Arduino answer, turn the screen anticlockwise to view.

Ungolfed version
A$="C#D#EF#G#A#B0Mm+"                              :REM Note names and chord type names fit very conveniently in the same string.
X$=GET$                                            :REM Get a character
R=INSTR(A$,X$)-1                                   :REM Root note = position of that char in A$. INSTR starts counting at 1, but we want 0, so subtract.
X$=GET$                                            :REM If the root note is natural, the next character will be the chord type. But...
IF X$="#"R=R+1:X$=GET$                             :REM If this char is # we need to increment the root, and get another char for chord type.
C=INSTR(A$,X$)                                     :REM C encodes for chord type
T=(R+4-C MOD2)MOD12                                :REM even C means major third, odd C means minor third
F=(R+C DIV2)MOD12                                  :REM "Mm" gives C=14,15 meaning C DIV2=7 (perfect fifth.) C=13,16 give diminished and augmented: 6,8.
V=1                                                :REM V is the sound channel number ("voice")
PRINT"______"                                      :REM left side of keyboard for cosmetic reasons
FORN=0 TO 11                                       :REM at the start of each iteration initialise C to 1, to point to the 4 spaces/2 underscores in the string below for drawing white notes.
  C=1-(N=4)*12                                     :REM if the note is E, add 12 so it points to the 6 underscores to draw the line between E and F.
  B$=MID$(A$,N+1,1)                                :REM load B$ with the name of the current note.
  IF B$="#" C=7: B$=MID$(A$,N,1)+B$                :REM if the character encountered is a sharp, update C to point the characters for drawing a sharp. Find the previous character in A$ and join it to the beginning of B$ to complete the note name.
  PRINT MID$("    __---|________",C,6);            :REM print the key (6 characters.)
  IF(R-N)*(T-N)*(F-N)=0 PRINT B$;:SOUND V,-15,100+N*4,99:V=V+1  :REM if N is equal to R,T or F, print the note name beside the key, play the note and increment the channel number for the next note.
  PRINT                                            :REM print a carriage return. It may be possible to golf this line out.
NEXT

How is the program supposed to be used from command line? (I installed BBC BASIC on my Ubuntu machine)

Wow, I didn't know there was a version of BBC basic for Ubuntu. I can't find one on the site I got my emulator from, and I don't use Ubuntu. Original BBC basic only had one program in memory at a time so you typed RUN. With the emulator I use you have to start the emulator environment then it runs within it. It has a text editor, then you click to run, then when the program terminates you can either type RUN to run the program again, or type individual Basic commands within the environment. You can produce a command-line executable with my emulator, but only if you buy the full version.

If you want to test the program, the best way I could help you is if you could find a Windows machine and download the exact version I'm using. Alternatively, if you could tell me where you got your Ubuntu version from I could have a little read of that.

BBC Basic runs on Linux too, they provide many distributions on their home page depending on the host OS. I just didn't manage to get the program running, neither from passing the code or pasting it in the prompt...

I just downloaded Napoleon Brandy Basic, and it is indeed, difficult to get started! You need save the code as text file called chords.nap, then type LOAD"chords.nap" at the command prompt. It adds line numbers to the code (more authentic to the original BBC Basic, would add a few more characters) Then you type RUN and the program crashes at the line with the SOUND statement in it, with the error message "Unsupported Basic V feature found." You could actually write a serious program with RT Russell's implementation if you really wanted to. But with Brandy basic I wouldn't even think about it.

In conclusion, This is the only one at bbcbasic.co.uk that might work with Linux AND sound: http://appdb.winehq.org/objectManager.php?sClass=version&iId=21754 But I just realised the point of Wine it's to make a Windows application run on Linux. And INKEY$ doesn't work, so GET$ may not work either (the new version does not use either.) It's a pity, because I know you like my post and I would like you to hear it. Here's the full link for the Windows version http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

Ok, I got it working with Wine. The program works pretty well, and the sounds are alright (event though the square signals are horrendous). Although the actual length in bytes is 337 (newlines count), this one definitely looks like a winner!

@MathieuRodic Your byte count of 337 for Rev0 is correct, the program I used to count didn't count the newlines. For Rev1 it was actually 348, not 337. But I have modified two lines and now it is down to 340 (I was trying to be too clever with the way I combined conditions, a simple OR and elimination of whitespace is shorter.) I found it's also possible to delete some newlines/colons but I added that as a note rather than claiming it in the title. I prefer to win with well presented code if possible. Thanks for going to the trouble of testing the program!

Something to try: Change INPUTx$ for READ x$, and add a line at the bottom: DATA CM,GM,Am,FM. Put the whole program inside a FOR loop, and add a line RUN at the end so it restarts itself. Now it plays a 4-chord turnaround continuously (the screen gets a little out of sync with the sound.) Adjust the 99 in the SOUND statement for the tempo desired.

As you can tell, I didn't try to golf this at all. I'm a music geek, and a pet peeve of mine is when people write things using the wrong enharmonics (e.g. saying that a C diminished chord is C D# F# instead of C Eb Gb), so I wrote this program that gets the enharmonics right. It does so by representing each note as the number of perfect fifths above F.
For what it's worth, if you want to distinguish enharmonics, any musical interval can be represented nicely in a computer program as a number of perfect fifths and a number of octaves. An augmented fourth, for example, is 6 perfect fifths and -3 octaves, and a diminished fifth is -6 perfect fifths and 4 octaves.
Haskell, 441 characters
import Data.List

notes = "FCGDAEB"

fromNum x = [notes !! (mod x 7)] ++ if x < 0 then replicate (-(div x 7)) 'b' else replicate (div x 7) '#'

toNum (x:xs) = y + 7 * if isPrefixOf "b" xs then -length xs else length xs
    where Just y = elemIndex x notes

chord xs = unwords . map (fromNum . \x -> toNum (init xs) + x) $ case last xs of 'A' -> [0,4,8]; 'M' -> [0,4,1]; 'm' -> [0,-3,1]; 'd' -> [0,-3,-6]

main = getLine >>= putStrLn . chord

Some example invocations:
jaspers:junk tswett$ ./chord
AM
A C# E
jaspers:junk tswett$ ./chord
C#m
C# E G#
jaspers:junk tswett$ ./chord
DbA
Db F A
jaspers:junk tswett$ ./chord
Cd
C Eb Gb
jaspers:junk tswett$ ./chord
A#M
A# C## E#
jaspers:junk tswett$ ./chord
Dbm
Db Fb Ab

Python3 - 315 char
First time in codegolf!
Only supports minor, major, diminished and augmented chords right now.
z=["C","C#","D","D#","E","F","F#","G","G#","A","A#","B"];y=[1,2,4,5,6]
def q(a):print(z[a%12])
a=input();k=(ord(a[0])+3)%7;j=k;m=4;s=0;f=7;
for i in y:
    if(k>=i):j+=1
if('#'in a):j+=1
if('b'in a):j-=1
if('m'in a or'0'in a):m=3
if('+'in a or"aug"in a):f=8
if('0'in a or"dim"in a):f=6;m=3
if('ma'in a):m=4
q(j);q(j+m);q(j+f);

Use 'C C# D D# E F F# G G# A A# B'.split(' ') instead of your literal array to save some bytes.

if('#'in a):j+=1 -> if'#'in a:j+=1 = 2 chars less for every statement. Also changing y to a range() expression saves something too. Welcome! (and remember that newlines also count ;))

@wch More bytes can be saved with 'C C# D D# E F F# G G# A A# B'.split() ;)

How did you count your score? I think you have to count new lines as one char each as well. By the way, since this answer works only in Python3, I'll edit your answer to explicitly state that. Also, instead of using y to store [1,2,4,5,6], why don't you just skip the y and replace line 4 with for i in[1,2,4,5,6]:? Anyway, welcome to codegolf and I hope you have fun here.

You can also save 3 more chars by indenting with only one space instead of four in line 5.

Arduino
Input/output is sent to / received from the Arduino via a COM port. A user can interact with this via a terminal, or the serial monitor in the Arduino IDE. As you may have guessed from my choice of platform, I am planning to include the actual playing of the chord (though I haven't done it yet.)
I have tackled the keyboard bonus successfully, and I have tried to tackle the guitar, with limited success.
The chord box comes in at 130 bytes, which is too long to be worth it. Therefore I have tried another way, just printing the fret numbers Tab style. Currently this is 81 bytes for a bonus of 81-100=-19. If this approach is deemed valid I can try and improve on it.
The chords used are all D-type shapes with the root on the 2nd string, fifth on the 3rd string, and third on the 1st and 4th strings. The 5th and 6th strings are not used and I mark this with X's on the right of the chord box (the left would be more usual, but examples marked on the right can be found.)
Because the program considers F to be the lowest note (for compatability with the keyboard while avoiding excessively high frets with this chord shape) the highest chord is an E (with root on the 17th fret.) See example output.
The keyboard is more successful in terms of golfing. It runs from F-E rather than C-B for the reasons described above. It must be viewed by turning the screen 90% anticlockwise, when you can clearly see the outlines of the black notes, and the demarcation between the white notes with ---. The line between B an C could be extended with some ____ for a few more bytes.
I will try playing the notes next. This will be interesting because, although I believe the Arduino Uno has 3 internal timers, only one note at a time can be played using the built in tone command. There is an external library function which uses all the hardware timers (which will mess up the serial, but it won't be needed at that stage anyway.) Alternatively I may try to produce the tones in softare.
If I am successful with that, I will golf it down but I don't think it will be the overall winner.
Ungolfed code
String p="F#G#A#BC#D#E -Mm+",y,d[]=
{"    ","---|"},n="\n";

void setup() {
  Serial.begin(9600);
  Serial.setTimeout(99999);
}

void loop(){
  char x[9]; int r,t,f,i,c=1;
  Serial.readBytesUntil(13,x,9);
  Serial.println(x);
  r=p.indexOf(x[0]);
  if (x[1]==35|x[1]==98){c=2;r+=x[1]==35?1:-1;}
  f=p.indexOf(x[c])/2;
  t=4-p.indexOf(x[c])%2;

  //chord box
  y=n;for(i=24;i--;)y+=d[1]+(i%4?"":" \n");
  y[89]=y[107]='X'; y[t*4-10]=y[t*4+52]=y[f*4+14]=y[28]='O';
  Serial.print("\t "+String(r+6)+y);

  f+=r;t+=r;

  //tab style
  Serial.println(String(t+1)+n+String(r+6)+n
  +String(f-2)+n+String(t+3)+"\nX\nX\n");

  f%=12;t%=12;

  //piano
  for(i=0;i<12;i++){
    c=0;
    y=String(p[i]);
    if(y=="#") {c=1;y=p[i-1]+y;}
    Serial.println(d[c]+"__"+((r-i&&t-i&&f-i)?"":y));
  }
}

Sample output
The lower the spacing between the lines of text, the better this looks. Therefore it looks great when I am actually editing the post, but horrible in the grey box after posting. Instead I've posted a screenshot of the Arduino serial monitor which is of intermediate line spacing (and hence display quality.)

Can't wait for the actual sound!

The notes for EM are correct (E G# B), but they aren't aligned correctly on your keyboard. It looks like you're on the right track though!

@CameronTinker Please tilt your screen 90 deg anticlockwise and look again. Note that the keyboard runs from F to E, not from C to B for the reasons described in my post. Choosing F as the internal "zero note" was a compromise for both guitar and keyboard output. There are 3 black notes on the left, 2 on the right and the output notes are correctly aligned. Extending the division between B and C would make it clearer, but would cost about 20 extra bytes. Crude it is, but I still think my keyboard is more readable than Pandubear's.

I don't know how I missed that! Sorry about that. I'm a pianist and my first inclination when I saw this was that the keyboard didn't look right ;).

@MathieuRodic I've got sounds out of the Arduino now, but they are so poor I'm not sure I'd call them a recognisable chord. I will have another try, but there are a few things happening with the Arduino that I don't understand. Anyway I just posted an answer in BBC Basic with keyboard and sound that's looking much better. So I will update this post later

Python 506(unicode as 1 char)-150(sound)-150(keyboard) = 206
For sound playing, it uses pygame.midi. Note that the pygame.midi.get_default_output_id() method don't work very well. So you may try changing the line o=Output(get_default_output_id()) to o=Output(1), o=Output(2), etc. Usually the correct value is between 0 and 5.
c=input()
s='C D EF G A B'.index(c[0])+{'#':1,'b':-1,'':0}[c[1:-1]]
m='0mM+'.index(c[-1])
t=s+3+m//2
R=[list(x)for x in['┌─'+'─┬─'*13+'─┐']+['│'+'  │'*14]*5+['└─'+'─┴─'*13+'─┘']]
i=3
for d in[3,6,3,3,6]*2:q=slice(i-1,i+2);R[0][q]='┬─┬';R[1][q]=R[2][q]=R[3][q]='│ │';R[4][q]='└┬┘';i+=d
X=[2]+[1,2,1,2,3,1,2,1,2,1,2,3]*2
from pygame.midi import*
init()
o=Output(get_default_output_id())
for s in[s,t,t+3+m%2]:R[[5,3][s%12 in[1,3,6,8,10]]][sum(X[:s+1])]='o';o.note_on(s+60,127,1)
for r in R:print(''.join(r))

Results
goooolf> python chords2.py
CM
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│ o│  │ o│  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
Cm
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││o│ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│ o│  │  │  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
Dm
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │ o│  │ o│  │ o│  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
D+
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │o││ ││o│ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │ o│  │  │  │  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
G+
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││o│ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │  │  │ o│  │ o│  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
Am
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │  │  │  │ o│  │ o│  │ o│  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
C#0
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │o││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │ o│  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
EbM
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││o│ │ │ ││ ││o│ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │  │  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

J - 82 char
Self-contained, reads from console input. If you need stdin, change the final 1 to a 3. Claiming no bonuses, and only covering the triads.
+/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1

Instead of a sharp note e.g. C# you must use the equivalent flat name Db. (Correcting for this would inflate the code by more than a bit.) The four types of chords are 0 for diminishing, m for minor, M for major, and + for augmented.
The logic is as follows: we use the last character to add an offset to the base 0-3-6, which selects the kind of third and fifth. Meanwhile, we use the note to find where in the scale to pull the notes from. The ;: both makes the note compatible with indexing into the scale at the start, and later (by &.) turns the pulled notes into a space separated string.
Example usage:
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
AM
A Ch E
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
Ab0
Ab B D
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
B+
B Eb G
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
Em
E G B

Does the suffix 'h' follow one of the "music notation standards"?

@MathieuRodic I suppose it's a grey area, so I bumped them all up to flats. No change in functionality. Don't know why I didn't do this earlier.

Javascript, 224 char
n=prompt();a="A0A#0B0C0C#0D0D#0E0F0F#0G0G#".split(0);x=1;r=a.indexOf(n[0]);n[1]=="#"&&(r++,x++);n[1]=="b"&&(r--,x++);s=r+4;l=r+7;(n[x]=="m"||n[x]==0)&&s++;s%=12;n[x]=="+"&&l++;n[x]==0&&l--;l%=12;alert(a[r]+" "+a[s]+" "+a[l])

This is my first code golf. I think it can be shorter, but I can't find any bytes to save.
Supports major, m for minor, 0 for diminished, + for augmented, or 37 more bytes for dim, aug.

n[m]==0 can be simply !n[m]. Same applies at another place. Total you can cut off 6 chars easily.

@GaurangTandon Since n is string, n[m]==0 will cast 0 to "0", so it equals to n[m]=="0". "0" == 0 is true, but !"0" is false.

I was just pointing out because I got the same output when I inputted AM. I might be wrong also.

Python (143 134 chars)
n,a='A A# B C C# D D# E F F# G G#'.split(),input();m,i=ord(a[-1])-42,n.index(a[:-1])
print(n[i],n[(i+4-m//2)%12],n[(i-4+(-m//2))%12])

My first golf challenge :), don't know if some more bytes can be shaved off.
The notation used here is * aug / + maj / , min / - dim
I deserve a bonus point for having the constant 42 in the code :P

You can gain a few bytes like this: n,q,a='A A# B C C# D D# E F F# G G#'.split(),[4,4,3,3],input();m,i=ord(a[-1])-42,n.index(a[:-1])

Scala 537 chars - 50
import java.util.Scanner
object C extends App{
val c=Map("M"->145,"m"->137,"+"->273,"0"->73,"7"->1169,"M7"->2193,"m7"->1161,"Mm7"->2185,"+7"->1297,"+M7"->2321,"07"->585,"7b5"->1097)
val n=List("A","A#","B","C","C#","D","D#","E","F","F#","G","G#")
val o=List("","Bb","Cb","B#","Db","","Eb","Fb","E#","Gb","","Ab")
val s=new Scanner(System.in).nextLine
val v=s indexWhere{c=>c!='#'&&c!='b'&&(c<'A'||c>'G')}
val (u,m)=s splitAt v
val x=n.indexOf(u)max o.indexOf(u)
val k=c(m)
for(i<-0 to 11)if((k&(1<<i))!=0)print(n((i+x)%12)+" ")
println}

Python 3: 257 - 150 = 107
Just 25 chars too long to beat the J solution! Oh well. There are some neat ideas here, I think.
I='AaBCcDdEFfGg'*2
Q='0123456789.,'*2
K="""-1#_2
-,#_0
-9#_.
____8
-6#_7
-4#_5
____3"""
r,*R,q=input()
r=I.find(r)+bool(R)
p=str.replace
for x in[0]+[8,4,7,3,6]['+Mm0'.find(q):][:2]:K=p(K,Q[x+r],I[x+r].upper())
for x in Q:K=p(K,x,' ')
print(p(K,' #','  '))

Input is like the examples, though you must use sharp names instead of flat names. (e.g. Gb must be F#)
Output is a single octave of a piano, seen from above and to the left, with note names superimposed. Should be just a tiny stretch of the imagination.
$ echo C#m | python3 chords.py
-  _
-G#_
-  _
____
-  _E
-C#_
____

Nice job! Although, I don't see the notes to play in the output? For CM, we should be able to read C E G...

Oh, I misinterpreted the question I suppose. Let's see if I can work that in...

Fixed! Too long... ):

Can't you replace bool(R) with R|0?

Nah, the point is that R is a list and bool(R) is 1 (true) if nonempty, and 0 (false) if empty. The | operator doesn't work with lists...

The output looks ugly...

@Ray to be fair, he was trying to beat the golf score of an answer in J. He gave the best shot at what he was trying to do and unfortunately he failed. If the downvote is yours, i don't think he deserves it. I am upvoting because his keyboard inspired mine.

Raku, 216 bytes
Shorter than my original Scala solution and spells pitches correctly to boot.
for $*IN.lines {m:P5/([A-G])(\#*)(b*)([Mm+0])/;my \r=4613502.comb[$0.ord-65]+7*($1.comb-$2.comb);put %(:M<0 4 1>,:m<0 -3 1>,"+",<0 4 8>,0,<0 -3 -6>){$3}.map({"FCGDAEB".comb[($/=r+$_)%7]~(<b #>)[$/>0]x abs($/div 7)})}

Try it online!

Haskell, 273 chars
n(s,a)="CCDDEFFGGAABB"!!(s+1-a):["b#"!!a|" b b  b b b "!!s/=' ']
t p=[(s,a)|s<-[11,10..0],a<-[0,1],n(s,a)==p]!!0
m(s,d)=n(mod s 12,d-3)
c q=[n(a,x),m(a+d,d),m(a+d+e,e)]where
 (a,x)=t$init q;f=lookup(last q).zip"0mM+";Just d=f[3,3,4,4];Just e=f[3,4,3,4]
main=print.c=<<getLine

Results
C0 ->["C","Eb","Gb"]   Cm ->["C","Eb","G"]    CM ->["C","E","G"]     C+ ->["C","E","G#"]
C#0->["C#","F","G"]    C#m->["C#","F","G#"]   C#M->["C#","F","Ab"]   C#+->["C#","F","A"]
D0 ->["D","F","Ab"]    Dm ->["D","F","A"]     DM ->["D","F#","A"]    D+ ->["D","F#","A#"]
D#0->["D#","Gb","A"]   D#m->["D#","Gb","A#"]  D#M->["D#","G","Bb"]   D#+->["D#","G","B"]
E0 ->["E","G","Bb"]    Em ->["E","G","B"]     EM ->["E","G#","B"]    E+ ->["E","G#","C"]
F0 ->["F","Ab","B"]    Fm ->["F","Ab","C"]    FM ->["F","A","C"]     F+ ->["F","A","C#"]
F#0->["F#","A","C"]    F#m->["F#","A","C#"]   F#M->["F#","A#","Db"]  F#+->["F#","A#","D"]
G0 ->["G","Bb","Db"]   Gm ->["G","Bb","D"]    GM ->["G","B","D"]     G+ ->["G","B","D#"]
G#0->["G#","B","D"]    G#m->["G#","B","D#"]   G#M->["G#","C","Eb"]   G#+->["G#","C","E"]
A0 ->["A","C","Eb"]    Am ->["A","C","E"]     AM ->["A","C#","F"]    A+ ->["A","C#","F"]
A#0->["A#","Db","F"]   A#m->["A#","Db","F"]   A#M->["A#","D","F"]    A#+->["A#","D","F#"]
B0 ->["B","D","F"]     Bm ->["B","D","F#"]    BM ->["B","D#","Gb"]   B+ ->["B","D#","G"]


text:
How many Sudoku puzzles exist?
This is not a Sudoku solver, nor a Sudoku checker.
Your challenge is to write a function or script that, given as input the "block" size of a 2D Sudoku puzzle (which is 3 for the classic 9x9 board, 4 for a 16x16 board, etc.) will compute an approximation of the number of distinct puzzles (solutions) that exist for that size.
For example, given input 3, your program should print an approximation, to the desired precision, of the number 6,670,903,752,021,072,936,960 which is the known number of distinct 9x9 Sudoku puzzles, or 5,472,730,538 when taking into account the various symmetries. Your solution should state whether symmetries are counted or ignored.
"Desired precision" is left undefined: your program might run for a given time and then output its result, or compute it up to a given number of significant digits, or even run forever, printing better and better approximations. The point is that it should be possible to make it compute the result to any required precision, in a finite time. (So "42" is not an acceptable answer.) Restricting the precision of your result to the available machine floats is acceptable.
No accessing online resources, no storing the source code in the file name, etc.

PS: I know this is a Hard Problem (NP-complete if I'm not mistaken.) But this question is only asking for an approximate, statistical solution. For example you can try random configurations that satisfy one (or better two) constraints, compute how many of those exist and then check how often you get a puzzle that satisfies all three constraints. This will work in a decent time for small sizes (certainly for size=3 and possibly 4) but the algorithm should be generic enough to work for any size.
The best algorithm wins.

PS2: I changed from code-golf to code-challenge to better reflect the difficulty of the problem and encourage smarter solutions, over dumb but well-golfed ones. But since apparently "best algorithm" is unclear, let me try to define it properly.
Given enough time and disregarding constant factors (including CPU and intepreter speed), or equivalently, considering their asymptotical behaviour, which solution would converge to the exact result the fastest?

Isn't this actually a really hard problem? Are you just asking for the shortest way to produce a function to produce the numbers {1, 1, 288, 6e21}, or to somehow extend this to n>3?

The exact solution is an incredibly hard problem, but an approximation can be computed with some random sampling and a few seconds of modern CPU time. Of course smarter solutions are welcome!

@Tobia this approach was used to find the approx number of rubik's cube positions requiring N moves to solve http://kociemba.org/cube.htm so it is possible to get an approximation this way. However, if I write a program which makes every row solved and then tests to see if the columns & squares are solved, it will have (9!)^9=1E50 possibilities to bruteforce, of which only 6E21 are hits (per the question.) It'll need 1.6E28 tries per hit on average. That's pretty slow. Now, if I could ensure both rows and cols are correct and check only squares, I'd be getting somewhere. Ah! I have an idea...

@steveverrill See? :-)

Isn't there an analytic solution?

@Newbrict if you read the wikipedia article referenced in the first comment, you will see that there is an analytic method for counting the symmetries, but not the solved grids (3x3 has been done on a computer in seconds, 4x3 took much longer, and 4x4 has not been done, though the answer has been found approximately.) There seems to be an analytic approximation, though. BTW, if you divide the larger number in the question by the number of symmetries, you do not get exactly the smaller symmetry-reduced number. This is because there are some symmetrical positions.

On hold? DAMN! I didn't see that coming! This is due to the change of  winning criterion, isn't it? I have something to post now (not quite an NxN solution, but a pretty good investigation.) Should have posted what I had yesterday, voting to reopen!

"The best algorithm wins. (Best approximation over asymptotic complexity.)".  So b=best_approximation; a=asymptotic_complexity; score=b/a ?

@steveverrill You can post it now, sorry for the trouble

@Tobia that was a lot of writing I just did! I hope it's clear. This is obviously a tough one. Easy to define the problem, hard to solve, and even harder to explain how you did it!

I think the definition of a winning algorithm might need some honing. As it is right now, defining it as "which solution would converge to the exact result the fastest" sounds like you're asking for the algorithm that simply produces the exact answer the fastest, which makes the approximation aspect of the problem pointless. Now I'm not great at designing scoring algorithms myself, but perhaps something like summing elapsedTime*abs(answer-guess)/answer for a couple predetermined elapsedTime values (lower score is better) could be a start. Powers or logarithms might need to be added.

C++
What i will present here is an algorithm, illustrated with an example for a 3x3 case. It could theoretically be extended to the NxN case, but that would need a much more powerful computer and/or some ingenious tweaks. I will mention some improvements as I go through.
Before going further, let's note the symmetries of the Sudoku grid, i.e. the transformations which lead to another grid in a trivial way. For block size 3, the symmetries are as follows:
Horizontal symmetry
**The N=3 sudoku is said to consist of 3 "bands" of 3 "rows" each**
permute the three bands: 3! permutations = 6
permute the rows in each band: 3 bands, 3! permutations each =(3!)^3=216

Vertical symmetry
**The N=3 sudoku is said to consist of 3 "stacks" of 3 "columns" each.**
the count is the same as for horizontal.

Note that horizontal and vertical reflections of the grid can be achieved by a combination of these, so they do not need to be counted.
There is one more spatial symmetry to be considered, which is transposing, which is a factor of 2. This gives the total spatial symmetry of
2*(N!*(N!)^N)^2 = 2*(6*216)^2=3359232 spatial symmetries for the case N=3.

Then there is another, very important symmetry, called relabelling.
Relabelling gives a further (N^2)!=9!=362880 symmetries for the case N=3. So the total
number of symmetries is 362880*3359232=1218998108160.

The total number of solutions cannot be found simply by multiplying the number of symmetry-unique solutions by this number, because there are a number (less than 1%) of automorphic solutions. That means that for these special solutions there is a symmetry operation that maps them to themselves, or multiple symmetry operations that map them to the same other solution.
To estimate the number of solutions, I approach the problem in 4 steps:
1.Fill an array r[362880][12]with all possible permutations of the numbers 0 to 8. (this is programming, and it is in C, so we are not going to use 1 to 9.) If you are astute you will notice that the second subscript is 12 not 9. This is because, while doing this, bearing in mind that we are going to consider this to be a "row" we also calculate three more integers r[9,10,11] == 1<<a | 1<<b | 1<<c where 9,10,11 refer to the first, second and third stack and a,b,c are the three numbers present in each stack for that row.
2.Fill an array b with all possible solutions of a band of 3 rows. To keep this reasonably small, only include those solutions where the top row is 012,345,678. I do this by brute force, by generating all possible middle rows and ANDing r[0][10,11,12] with r[i][10,11,12]. Any positive value means there are two identical numbers in the same square and the band is invalid. When there is a valid combination for the first two rows, I search the 3rd (bottom) row with the same technique.
I dimensioned the array as b[2000000][9] but the program only finds 1306368 solutions. I did not know how many there were, so I left the array dimension like that. This is actually only half the possible solutions for a single band (verified on wikipedia), because I only scan the 3rd row from the current value for i upwards. The remaining half of the solutions can be found trivially by exchanging the 2nd and 3rd rows.
The way the information is stored in array b is a little confusing at first. instead of using each integer to store the numbers 0..8 found in a given position, here each integer considers one of the numbers 0..8 and indicates in which columns it can be found. thus b[x][7]==100100001 would indicate that for solution x the number 7 is found in columns 0,5 and 8 (from right to left.) The reason for this representation is that we need to generate the rest of the possibilities for the band by relabelling, and this representation makes it convenient to do this.
The two steps above comprise the setup and take about a minute (possibly less if I removed the unnecessary data output. The two steps below are the actual search.)
3 Search randomly for solutions for the first two bands that do not clash (i.e. do not have the same number twice in a given column. We pick a random solution for band 1, assuming always permutation 0, and a random solution for band 2 with a random permutation. A result is normally found in less than 9999 tries (first stage hit rate in the thousands range) and takes a fraction of a second. By permutation, I mean that for the second band we take a solution from b[][] where the first row is always 012,345,678 and relabel it so that any possible sequence of numbers on the first row is possible.
4 When a hit is found in step 3, search for a solution for the third band which does not clash with the other two. We do not want to make just one try, otherwise the processing time for step 3 would be wasted. On the other hand we do not want to put an inordinate amount of effort into this.
Just for fun, last night I did it the dumbest way possible, but it was still interesting (because it nothing for ages, then found large numbers of solutions in bursts.) It took all night to get one datapoint, even with the little hack (!z) I did to abort the last k loop as soon as we know this is not a valid solution (which makes it run nearly 9 times faster.) It found 1186585 solutions for the complete grid
after searching all 362880 relabellings of all 1306368 canonical solutions for the last block, a total of 474054819840 possibilities. That's a hit rate of 1 in 400000 for the second stage. I will try again soon with a random search rather than a scan. It should give a reasonable answer in just a few million tries, which should take only a few seconds.
The overall answer should be (362880*(1306368*2))^3*hit rate=8.5E35*hit rate. By back calculating from the number in the question, I expect a hit rate of 1/1.2E14. What I've got so far with my single datapoint is 1/(400000*1000) which is out by a factor of about a million. This could be an anomaly of chance, an error in my program, or an error in my math. I won't know which it is until I run a few more tests.
I'll leave this here for tonight. The text is a bit scrappy, I will tidy it up soon and hopefully add some more results, and maybe a few words on how to make it faster and how to extend the concept to  N=4. I don't think I'll be making too many more changes to my program, though :-)
Ah.. the program:
#include "stdafx.h"
#define _CRT_RAND_S
#include <algorithm>
#include <time.h>

unsigned int n[] = { 0,1,2,3,4,5,6,7,8 }, r[362880][12], b[2000000][9],i,j,k,l,u,v,w,x,y,z;

int main () {

  //Run through all possible permutations of n[] and load them into r[][]
  i=0;
  do {
      r[i][9] = r[i][10] = r[i][11]=0;
      for (l = 0; l < 9; l++){
          r[i][l] = n[l];
          r[i][9 + l / 3] |= 1 << n[l];
      }
      if((i+1)%5040==0) printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
          ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
      i++;
  } while ( std::next_permutation(n,n+9) );

  //Initialise b[][]
  for (l = 0; l<2000000; l++) for (k = 0; k<9; k++) b[l][k]=0;
  //fill b[][] with all solutions of the first band, where row0 ={0,1,2,3,4,5,6,7,8} and row1<row2
  l=0;
  for (i = 0; i<362880; i++)
  if (!(r[0][9] & r[i][9] | r[0][10] & r[i][10] | r[0][11] & r[i][11])){printf("%d %d \n",i,l);
     for (j=i; j<362880;j++)
       if(!(r[0][9]&r[j][9] | r[0][10]&r[j][10] | r[0][11]&r[j][11] | r[j][9]&r[i][9] | r[j][10]&r[i][10] | r[j][11]&r[i][11] )){
           for (k = 0; k < 9; k++){
               b[l][r[0][k]]|=1<<k;
               b[l][r[i][k]]|=1<<k;
               b[l][r[j][k]]|=1<<k;
            }
            l++;
       }
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[j][0],r[j][1],r[j][2],r[j][3],r[j][4],r[j][5],r[j][6],r[j][7],r[j][8],r[j][9],r[j][10],r[j][11],r[j][9]+r[j][10]+r[j][11]);
//        printf("%d %d %o %o %o %o %o %o %o %o %o \n",i,l,b[l][0],b[l][1],b[l][2],b[l][3],b[l][4],b[l][5],b[l][6],b[l][7],b[l][8]);
  }

  // find a random solution for the first 2 bands
  l=0;
  do{
      rand_s(&u); u /= INT_MIN / -653184; //1st band selection
      rand_s(&v); v /= INT_MIN / -181440; //2nd band permutation
      rand_s(&w); w /= INT_MIN / -653184; //2nd band selection
      z = 0;
      for (k = 0; k < 9; k++) z |= b[u][k] & b[w][r[v][k]];
      l++;
  } while (z);
  printf("finished random after %d tries \n",l);
  printf("found solution with top band %d permutation 0, and middle band %d permutation %d \n",u,w,v);
  getchar();

  // scan all possibilities for the last band
  l=0;
  for (i = 0; i < 362880; i++) for (j = 0; j < 1306368; j++){
              z=0;
              for(k=0;(k<9)&&(!z);k++) z|= b[u][k] & b[j][r[i][k]] | b[j][r[i][k]] & b[w][r[v][k]];
              if (!z){ l++; printf("solution %d : i= %d j=%d",l,i,j); }
  }
  printf("finished bottom band scan at %d millisec \n", clock()); getchar();
}

source: Stack Exchange

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

sort: votes


text:
building circuit for divisibility by 3
A boolean circuit in TCS is basically a DAG consisting of And, Or, Not gates, and by  what is known is "functional completeness" they can compute all possible functions. eg this is the basic principle in an ALU.

Challenge: create a circuit to determine whether an 8-binary-digit number is divisible by 3 and somehow visualize your result (ie in some kind of picture)

The judging criteria for voters is based on whether the code to generate the circuit generalizes nicely to arbitrary size numbers, and whether the algorithmically-created visualization is compact/balanced but yet still human-readable (ie visualization by hand arrangement not allowed). ie the visualization is for n=8 only but the code will ideally work for all 'n'. winning entry is just top voted.
Somewhat similar question: Build a multiplying machine using NAND logic gates

Much better. However "generalize" and "aesthetic" are not objective. All questions must have an objective winning criterion. If you want to apply those characteristics, use popularity-contest. If you want shortest code, use code-golf. If you want to make a combination of the two, use code-challenge, but specify a formula. For example 1.25votes - 0.25length as this question does: http://codegolf.stackexchange.com/questions/23581/eiffel-tower-in-3d/23585#23585

ok made those chgs you ask for. thx for feedback.

Oghh, I guess compiled VHDL or Verilog after all its optimizations should give the shortest answer. I'll try it later.

A better winning criteria would be [tag:gate-golf]

@TheDoctor ??? what is gate-golf? that tag is nonexistent. note to participants: please state what language/visualization tool you are using. if anyone else wants to enter plz comment. otherwise will accept winner tonite. thx much to respondents so far this went "BTE" better than expected!

@vzn If there are to be more such challenges, I think gate-golf would be a great tag to use.  You should just be able to add the new tag to questions, then I think a moderator would have to approve/deny the new tag

This would probably be better split into two challenges: 1. the "gate-golf" part and 2. the visualization part.  They are quite distinct problems and I don't see any particular value added by having them clubbed into the same challenge.

DT maybe so for this site. the visualization makes it easier for voters to judge entrants, they can do so not nec on code alone. also it was intended as part of a larger project that involves easily visualizing circuit DAGs for more sophisticated analysis & other challenges that build on this one. re new challenges

Hmm wondering if I can use this: http://stackoverflow.com/questions/4085914/binary-divisibility-by-3.
Probably not :)

CC are you joking? yeah that post is marked as dup of another with solutions similar to some below. nice find!

The graph maintains 3 booleans at each level i.  They represent the fact that the high-order i bits of the number are equal to 0, 1, or 2 mod 3.  At each level we compute the next three bits based on the previous three bits and the next input bit.
Here's the python code that generated the graph.  Just change N to get a different number of bits, or K to get a different modulus.  Run the output of the python program through dot to generate the image.
N = 8
K = 3
v = ['0']*(K-1) + ['1']
ops = {}

ops['0'] = ['0']
ops['1'] = ['1']
v = ['0']*(K-1) + ['1']
for i in xrange(N):
  ops['bit%d'%i] = ['bit%d'%i]
  ops['not%d'%i] = ['not','bit%d'%i]
  for j in xrange(K):
    ops['a%d_%d'%(i,j)] = ['and','not%d'%i,v[(2*j)%K]]
    ops['b%d_%d'%(i,j)] = ['and','bit%d'%i,v[(2*j+1)%K]]
    ops['o%d_%d'%(i,j)] = ['or','a%d_%d'%(i,j),'b%d_%d'%(i,j)]
  v = ['o%d_%d'%(i,j) for j in xrange(K)]

for i in xrange(4):
  for n,op in ops.items():
    for j,a in enumerate(op[1:]):
      if ops[a][0]=='and' and ops[a][1]=='0': op[j+1]='0'
      if ops[a][0]=='and' and ops[a][2]=='0': op[j+1]='0'
      if ops[a][0]=='and' and ops[a][1]=='1': op[j+1]=ops[a][2]
      if ops[a][0]=='and' and ops[a][2]=='1': op[j+1]=ops[a][1]
      if ops[a][0]=='or' and ops[a][1]=='0': op[j+1]=ops[a][2]
      if ops[a][0]=='or' and ops[a][2]=='0': op[j+1]=ops[a][1]

for i in xrange(4):
  used = set(['o%d_0'%(N-1)])|set(a for n,op in ops.items() for a in op[1:])
  for n,op in ops.items():
    if n not in used: del ops[n]

print 'digraph {'
for n,op in ops.items():
  if op[0]=='and': print '%s [shape=invhouse]' % n
  if op[0]=='or': print '%s [shape=circle]' % n
  if op[0]=='not': print '%s [shape=invtriangle]' % n
  if op[0].startswith('bit'): print '%s [color=red]' % n
  print '%s [label=%s]' % (n,op[0])
  for a in op[1:]: print '%s -> %s' % (a,n)
print '}'

great! have used graphviz also... tiny quibble, there are unused ANDs/ORs in the diagram. also suggest maybe highlighting input bits in different color to show their locations

@vzn: Ok, fixed.

Depth:7 (logarithmic), 18x AND, 6x OR, 7x XOR, 31 gates (linear)
Let me calculate the digit sum in base four, modulo three:

circuit drawn in Logisim
Generalisation, formally (hopefully somewhat readable):
balance (l, h) = {
  is1: l & not h,
  is2: h & not l,
}

add (a, b) =
  let aa = balance (a.l, a.h)
      bb = balance (b.l, b.h)
  in  { l:(a.is2 & b.is2) | (a.is1 ^ b.is1),
        h:(a.is1 & b.is1) | (a.is2 ^ b.is2)}

pairs [] = []
pairs [a] = [{h:0, l:a}]
pairs [rest.., a, b] = [pairs(rest..).., {h:a, l:b}]

mod3 [p] = p
mod3 [rest.., p1, p2] = [add(p1, p2), rest..]

divisible3 number =
  let {l: l, h: h} = mod3 $ pairs number
  in  l == h

now in english:
While there are more than two bits in the number, take two lowest pairs of bits and sum them modulo 3, then append the result to the back of the number, then return if the last pair is zero modulo 3. If there is an odd number of bits in the number, add an extra zero bit to the top, then polish with constant value propagation.
Appending to the back instead of to the front ensures the addition tree is a balanced tree rather than a linked list. This, in turn, ensures logarithmic depth in the number of bits: five gates and three levels for pair cancellation, and an extra gate at the end.
Of course, if approximate planarity is desired, pass the top pair unmodified to the next layer instead of wrapping it to the front. This is easier said than implemented (even in pseudocode), however. If the number of bits in a number is a power of two (as is true in any modern computer system as of March 2014), no lone pairs will occur, however.
If the layouter preserves locality / performs route length minimisation, it should keep the circuit readable.
This Ruby code will generate a circuit diagram for any number of bits (even one). To print, open in Logisim and export as image:
require "nokogiri"

Port = Struct.new :x, :y, :out
Gate = Struct.new :x, :y, :name, :attrs
Wire = Struct.new :sx, :sy, :tx, :ty

puts "Please choose the number of bits: "
bits = gets.to_i

$ports = (1..bits).map {|x| Port.new 60*x, 40, false};
$wires = [];
$gates = [];

toMerge = $ports.reverse;

def balance a, b
y = [a.y, b.y].max
$wires.push Wire.new(a.x   , a.y , a.x   , y+20),
          Wire.new(a.x   , y+20, a.x   , y+40),
          Wire.new(a.x   , y+20, b.x-20, y+20),
          Wire.new(b.x-20, y+20, b.x-20, y+30),
          Wire.new(b.x   , b.y , b.x   , y+10),
          Wire.new(b.x   , y+10, b.x   , y+40),
          Wire.new(b.x   , y+10, a.x+20, y+10),
          Wire.new(a.x+20, y+10, a.x+20, y+30)
$gates.push Gate.new(a.x+10, y+70, "AND Gate", negate1: true),
          Gate.new(b.x-10, y+70, "AND Gate", negate0: true)
end

def sum (a, b, c, d)
y = [a.y, b.y, c.y, d.y].max
$wires.push Wire.new(a.x   , a.y , a.x   , y+40),
          Wire.new(a.x   , y+40, a.x   , y+50),
          Wire.new(a.x   , y+40, c.x-20, y+40),
          Wire.new(c.x-20, y+40, c.x-20, y+50),
          Wire.new(b.x   , b.y , b.x   , y+30),
          Wire.new(b.x   , y+30, b.x   , y+50),
          Wire.new(b.x   , y+30, d.x-20, y+30),
          Wire.new(d.x-20, y+30, d.x-20, y+50),
          Wire.new(c.x   , c.y , c.x   , y+20),
          Wire.new(c.x   , y+20, c.x   , y+50),
          Wire.new(c.x   , y+20, a.x+20, y+20),
          Wire.new(a.x+20, y+20, a.x+20, y+50),
          Wire.new(d.x   , d.y , d.x   , y+10),
          Wire.new(d.x   , y+10, d.x   , y+50),
          Wire.new(d.x   , y+10, b.x+20, y+10),
          Wire.new(b.x+20, y+10, b.x+20, y+50)
$gates.push Gate.new(a.x+10, y+90, "XOR Gate"),
          Gate.new(b.x+10, y+80, "AND Gate"),
          Gate.new(c.x-10, y+80, "AND Gate"),
          Gate.new(d.x-10, y+90, "XOR Gate")
$wires.push Wire.new(a.x+10, y+90, a.x+10, y+100),
          Wire.new(b.x+10, y+80, b.x+10, y+90 ),
          Wire.new(b.x+10, y+90, a.x+30, y+90 ),
          Wire.new(a.x+30, y+90, a.x+30, y+100),
          Wire.new(d.x-10, y+90, d.x-10, y+100),
          Wire.new(c.x-10, y+80, c.x-10, y+90 ),
          Wire.new(c.x-10, y+90, d.x-30, y+90 ),
          Wire.new(d.x-30, y+90, d.x-30, y+100)
$gates.push Gate.new(d.x-20, y+130, "OR Gate"),
          Gate.new(a.x+20, y+130, "OR Gate")
end

def sum3 (b, c, d)
y = [b.y, c.y, d.y].max
$wires.push Wire.new(b.x   , b.y , b.x   , y+20),
          Wire.new(b.x   , y+20, b.x   , y+30),
          Wire.new(b.x   , y+20, d.x-20, y+20),
          Wire.new(d.x-20, y+20, d.x-20, y+30),
          Wire.new(c.x   , c.y , c.x   , y+60),
          Wire.new(c.x   , y+60, b.x+30, y+60),
          Wire.new(b.x+30, y+60, b.x+30, y+70),
          Wire.new(d.x   , d.y , d.x   , y+10),
          Wire.new(d.x   , y+10, d.x   , y+30),
          Wire.new(d.x   , y+10, b.x+20, y+10),
          Wire.new(b.x+20, y+10, b.x+20, y+30),
          Wire.new(b.x+10, y+60, b.x+10, y+70)
$gates.push Gate.new(b.x+10, y+60 , "AND Gate"),
          Gate.new(d.x-10, y+70 , "XOR Gate"),
          Gate.new(b.x+20, y+100, "OR Gate" )
end

while toMerge.count > 2
puts "#{toMerge.count} left to merge"
nextToMerge = []
while toMerge.count > 3
 puts "merging four"
 d, c, b, a, *toMerge = toMerge
 balance a, b
 balance c, d
 sum *$gates[-4..-1]
 nextToMerge.push *$gates[-2..-1]
end
if toMerge.count == 3
 puts "merging three"
 c, b, a, *toMerge = toMerge
 balance b, c
 sum3 a, *$gates[-2..-1]
 nextToMerge.push *$gates[-2..-1]
end
nextToMerge.push *toMerge
toMerge = nextToMerge
puts "layer done"
end

if toMerge.count == 2
b, a = toMerge
x = (a.x + b.x)/2
x -= x % 10
y = [a.y, b.y].max
$wires.push Wire.new(a.x , a.y , a.x , y+10),
          Wire.new(a.x , y+10, x-10, y+10),
          Wire.new(x-10, y+10, x-10, y+20),
          Wire.new(b.x , b.y , b.x , y+10),
          Wire.new(b.x , y+10, x+10, y+10),
          Wire.new(x+10, y+10, x+10, y+20)
$gates.push Gate.new(x, y+70, "XNOR Gate")
toMerge = [$gates[-1]]
end

a = toMerge[0]
$wires.push Wire.new(a.x, a.y, a.x, a.y+10)
$ports.push Port.new(a.x, a.y+10, true)

def xy (x, y)
"(#{x},#{y})"
end
circ = Nokogiri::XML::Builder.new encoding: "UTF-8" do |xml|
xml.project version: "1.0" do
xml.lib name: "0", desc: "#Base"
xml.lib name: "1", desc: "#Wiring"
xml.lib name: "2", desc: "#Gates"
xml.options
xml.mappings
xml.toolbar do
  xml.tool lib:'0', name: "Poke Tool"
  xml.tool lib:'0', name: "Edit Tool"
end #toolbar
xml.main name: "main"
xml.circuit name: "main" do
  $wires.each do |wire|
    xml.wire from: xy(wire.sx, wire.sy), to: xy(wire.tx, wire.ty)
  end #each
  $gates.each do |gate|
    xml.comp lib: "2", name: gate.name, loc: xy(gate.x, gate.y) do
      xml.a name: "facing", val: "south"
      xml.a name: "size", val: "30"
      xml.a name: "inputs", val: "2"
      if gate.attrs
        gate.attrs.each do |name, value|
          xml.a name: name, val: value
        end #each
      end #if
    end #comp
  end #each
  $ports.each.with_index do |port, index|
    xml.comp lib: "1", name: "Pin", loc: xy(port.x, port.y) do
      xml.a name: "tristate", val: "false"
      xml.a name: "output",   val: port.out.to_s
      xml.a name: "facing",   val: port.out ? "north" : "south"
      xml.a name: "labelloc", val: port.out ? "south" : "north"
      xml.a name: "label",    val: port.out ? "out" : "B#{index}"
    end #port
  end #each
end #circuit
end #project
end #builder

File.open "divisibility3.circ", ?w do |file|
file << circ.to_xml
end

puts "done"

finally, when asked to create an output for 32 bits, my layouter generates this. Admittedly, it's not very compact for very wide inputs:

looks really great & best circuit/layout so far. what language is the code in? what layouter did you use if any? the layouter was requested to be an algorithm, and have to assume that algorithm was not used (hand layout) unless stated...

@vzn the layouter had to be implemented, too? I understood that restriction as meaning that we could draw the diagram manually, but readability must not depend on the way the diagram is drawn. TimWolla's circuit is definitely hand-generated. The pseudo-code is mostly based on Haskell with Javascripty objects added.

algorithmically created visualization was meant to mean basically algorithmic layouter but now admit that could be ambiguously interpreted. sorry for lack of crystal clarity. do you know of any automated layouter that can get nearly similar results to your hand layout?

Unfortunately, no. yEd has great layouters but it ignores orientation. I've never got familiar with dot nor I find its output exactly nice. I guess I could translate this pseudocode to Ruby (easy) and write my own specialised layouter (not too hard, but complex) that would export a logisim circuit (it's just an XML, and it's not even gzipped, so quite easy). Should I (I want to), and should I post that as a separate answer? Also, would that count as hand-designed?

All good answers, but this looks like the most elegant so far

@vzn Is my new layouter acceptable for you?

nice! alas automated circuit/graph layout is not as easy as it looks! asked for pkgs on [softwarerecs.se] awhile back but it got zapped :(

Depth:7 (logarithmic), 18x AND, 6x OR, 7x XOR Both gate count and depth neglect inverters(inverted inputs)(&output).

2×24 NOT, 2×10+5 AND, 2×2+5 OR, 2×2 NOR
This totally does not scale. Like not at all. Maybe I'll try to improve it.
I did test this for numbers up to 30 and it worked fine.
Those 2 big circuits are counting the number of active inputs:

The upper right one counts the number of bits with an even power (zero to 4)
The lower left one counts the number of bits with an odd power (zero to 4)

If the difference of those numbers is 0 or 3 the number is divisible by 3. The lower right circuit basically maps each valid combination (4,4, 4,1, 3,3, 3,0, 2, 2, 1, 1, 0, 0) into an or.
The little circle in the middle is an LED that is on if the number if divisible by 3 and off otherwise.

wow nice/fast! ... plz put a link to code or inline it ... also detail how you did the visualization ...?

@vzn The visualization was made with logisim. It was built my hand, but the general algorithm can easily be done with a program as well. It is partly explained in the answer.

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


text:
The Random Quine
Write a program that is capable of randomly generating itself.
It must do this based on the tokens used in its source code. If your program's source code is composed of 50 unique tokens and is 60 tokens long, then the program should output 60 tokens where each token is randomly chosen from one of the 50 unique tokens.
For example, this program would have a one in 50^60 chance to reproduce itself.
What is a token? That depends on the language. For example, identifiers (foo_bar), keywords (while), and numbers (42) would count as tokens in most languages. Whitespace would not count in most languages.
Additional rules:

Output may only contain tokens found in the programs source code, separated by the appropriate delimiter
Output must be the same length as the program's source code, counted by tokens
Only one programming language may be used
Source code must have at least 3 unique tokens
Exclude comments from the source code
Program should only have a one in U^L chance to reproduce itself

Scoring: The program that has the best chance to reproduce itself, wins.

@MathieuRodic: You're assuming that the program draws tokens without repetition.

@MathieuRodic: Let me rephrase. You're assuming the program randomly scrambles the multiset of its tokens, rather than drawing L tokens with repetition from the set of U tokens used in its source.

@user2357112: I see. My mistake was to consider this problem as a draw without replacement.

Rule #1 and #5 appear to be in contradiction to me.

Also rule #5 in conjunction with the scoring means that the highest possible score is if it has exactly U^L chance?

@Cruncher Fixed the contradiction. I edited earlier to simplify and ended up messing it up.

@Cruncher The highest possible score is by minimizing U^L.

Can you assume that built in random functions are TRNGs? Typical implementations have too small seeds to produce all outputs and thus might be unable to actually regenerate itself.

@CodesInChaos Sounds like a safe assumption to me.

@abligh No, how does that contradict? Minimize U^L. Or maximize 1/U^L.

@AustinHenley doh. Deleted that comment.

Does the randomness have to be uniform?

Python 2, 3^-3 = 0.037
exec abuse is quite handy for reducing the token count. Now updated to not read the source file!
exec '' """
s = '''{a}
s = {b}
s = s.format(a='"'*3, b="'"*3+s+"'"*3)
import random
tokens = ['exec', "''", s]
print random.choice(tokens), random.choice(tokens), random.choice(tokens),
{a}'''
s = s.format(a='"'*3, b="'"*3+s+"'"*3)
import random
tokens = ['exec', "''", s]
print random.choice(tokens), random.choice(tokens), random.choice(tokens),
"""

The extra '' between exec and the giant triple-quoted string is just to pad the token count to the required minimum of 3. It gets merged into the second string due to implicit string literal concatenation.
Original, opening-the-source-file version:
exec '''
# String literals are one token!
import random
import tokenize

with open(__file__) as f:
    tokens = [x[1] for x in tokenize.generate_tokens(f.readline)][:-1]

''' '''
# Splitting the string into two strings pads the token count to the minimum of 3.

print random.choice(tokens), random.choice(tokens), random.choice(tokens),
'''

Strictly speaking, the Python grammar places an ENDMARKER token at the end of the source file, and we can't produce a source file with ENDMARKERs randomly strewn about. We pretend it doesn't exist.

@Cruncher That is the probability. 3^-3 == 1/3^3

+1 for brilliant hack of the rules. The same idea implemented in J: ".]';(?3 3 3){]`".;~({:,],{:,],6#{:)'';(?3 3 3){]`".;~({:,],{:,],6#{:)'''''''.

Javascript, 102 tokens, 33 unique, 7.73×10-154
Note, this is a true quine. It doesn't read the file or use eval or Function.toString
meta = "meta = ; out = '' ; tokens = meta . split ( '\\u0020' ) ; tokens . push ( '\"' + meta + '\"' ) ; length = tokens . length ; tmp = length ; unique = { } ; while ( tmp -- ) unique [ tokens [ tmp ] ] = unique ; unique = Object . keys ( unique ) ; tmp = unique . length ; while ( length -- ) out += tokens [ ~~ ( Math . random ( ) * tmp ) ] + '\\u0020' ; console . log ( out )";
out = '';
tokens = meta.split('\u0020');
tokens.push('"' + meta + '"');
//console.log(tokens);
length = tokens.length;
tmp = length;
unique = { };
while(tmp--) unique[tokens[tmp]] = unique;
unique = Object.keys(unique);
//console.log(unique);
tmp = unique.length;
while(length--)
    out += unique[~~(Math.random() * tmp)] + '\u0020';
console.log(out)

Python: P(generating program in 1 trial) = 3.0317 * 10^-123
34 unique tokens, 80 total tokens. Note that there is a space at the end of each line.
import tokenize , random
tokens = [ x [ 1 ] for x in tokenize . generate_tokens ( open ( __file__ , 'r' ) . readline ) ] [ : -1 ]
s = ''
for x in tokens : s += random . choice ( list ( set ( tokens ) ) ) ; s += [ ' ' , '' ] [ s [ -1 ] == '\n' ]
print s

Sample output:
' ' random len set 'r' , for ( list , import ] ] tokens : random [ for '\n' import readline readline 'r' tokens [ len 'r' import '' choice '' '' for in ( readline ( = open readline , list 1 list s += for s 1 , '' : 1 += list len - __file__ ; open __file__ print . - ] 'r' for import [ print . ,

; . [ [ print print __file__ generate_tokens ] ; open ] , readline

Thanks to the other Python solution by user2357112 for reminding me to discard the last token and use __file__ which I was previously ignorant of.

J - 1 in 1117 = 1.978 x 10-18
;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''

J has a bunch of handy little tools for getting these kinds of jobs done.

First of all, any space separated string of numbers is one token. It means a one-dimensional array of those numbers. This is how J's lexer works. By the way, that's seventeen 11s, if anyone is curious.
(,,,{:,{:)'QUINE''' is a common quine trick in J, made to use as few tokens as possible: {: means Tail, so it appends the string to itself, and then adds two copies of the last character to the end of that. Since the last character is a single quote (J uses Pascal-style strings), the result is QUINE'QUINE'''.
;: is a tokenizer, and breaks up an input string as though it was J code, returning a list of boxes. The length of this result is 17.
~. takes all the unique elements of this array. The length of this result is 11.
? is called Roll. For each integer in its argument, it selects a random positive number greater than or equal to zero, less than that number. So here J will generate 17 numbers from 0 to 10 inclusive.
{ uses the random indices to select items out of our list of unique-tokens-in-boxes.
; opens all these boxes and runs the result together.

Some examples follow. The indented lines are the input prompts, and the lines flush with the left side are the interpreter's output.
   ;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''
~.~.(?;;:11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''(){11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){(;:;
   ;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''
{';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)''',?{:;:{:';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11{:{;(;:{:,~.

Postscript
This was a fun one
/cvx /cvx cvx /exec /exec cvx /dup /rand /mod /get /== /array /astore /realtime
/srand /repeat 6 17 54 17 /array cvx exec /astore cvx exec 54 /dup cvx /rand
cvx 17 /mod cvx /get cvx /== cvx 6 /array cvx exec /astore cvx exec cvx /realtime
cvx exec /srand cvx exec /repeat cvx exec

There are 17 unique tokens and 54 tokens total for approx 1 in 3.6e-67 chance.

Whitespace, 3^-205 3^-189 3^-181 3^-132 ~= 10^-63
This is a Whitespace program that, when seeded with random characters, has a 1 in 3^132 chance of reproducing itself (3 distinct tokens, repeated 132 times). It must be seeded with at least 132 random characters when run, (Whitespace has no built-in random or date function to seed with) e.g. some_whitespace_interpreter my_quine.ws <some_random_source >quine_output.ws.  The score would be improved if the program could be golfed any more, but this is my first "real" Whitespace program, so I'll just leave it with my meager amount of golfing.
Plain Whitespace code, or see it run: (to try it, click "edit", copy the stuff inside the <pre> tags; should be 132 characters with Unix-style EOL)

Code annotated with what command is what (not technically a quine, as it won't reproduce the comments):
stack push_number + 0 end
stack push_number + 1   0 0 1   end
heap        store stack push_number + 1 end
stack push_number + 1   0 0 0 0 0 end
heap        store stack push_number + 1 0 end
stack push_number + 1   0 1 0 end
heap        store stack push_number + 1 0 0 0 0 0 1 1   end
flow
make_label  loop_begin
stack push_number + 1   1   end
IO
read    character stack push_number + 1 1   end
heap        retrieve    stack push_number + 1   1   end
arithmetic   modulo     heap        retrieve    IO
print char stack push_number + 1    end
arithmetic   subtract   stack duplicate
 flow
jump_if_zero        end_prog
flow
jump_to
loop_begin
flow
make_label  end_prog
flow
end_program

If the seed just happens to be equivalent (the characters are taken mod 3 to be converted to the tokens) to this, it will succeed:
CCCCACCCBCCBABBCCCCBACCCBCCCCCABBCCCCBCACCCBCBCABBCCCCBCCCCCBBAACCBACCCBBABABCCCCBBABBBCCCBBABCBBBBBBACCCCCBABCCBCACABBAACABAACCAAAA
It's a pretty simple program, roughly equivalent to this Ruby program:
i = 131
while true
    print '\t \n'[STDIN.getc.ord % 3]
    i = i - 1
    break if i < 0
end

Perl, 27 tokens, P = 1.4779 x 10-34
@ARGV=$0;print$W[rand@W]for@W=split/(\W)/,readline

Last edit: use @ARGV=$0 instead of open*ARGV,$0 to save a token.

15 unique tokens
4 tokens appear 2 times (=, /, @, $)
1 token appears 4 times (W)

So I think that makes the probability (pow(2,2*4) * pow(4,4))/pow(27,27),
about 1.48E-34.
If the source code is in a file called ARGV, then you can use this 26 token solution with P =~ 2.193 x 10-31:
@ARGV=ARGV;print$ARGV[rand@ARGV]for@ARGV=split/(\W)/,readline

Actually, P = (4 * 2! + 4!) / 27!, which is around 1.7632684538487448 x 10^-26

Perl 6, \$1\$ in \$3^3\$ = \$0.037037...\$
(I know this isn't code-golf, but...)
q[say |roll <<~~"q[$_]".EVAL>>: 3]~~.EVAL

Try it online!
Much the same as the Python answer, where the first token is a string literal that is evaluated. The tokens are
q[say |roll <<~~"q[$_]".EVAL>>: 3]   String literal
~~                                   Smartmatch operator
.EVAL                                Function call

Explanation:
q[say |roll <<~~"q[$_]".EVAL>>: 3]         # Push as string literal
                                  ~~       # Smartmatch by setting $_ to the string literal
                                    .EVAL  # Eval the string
            <<~~"q[$_]".EVAL>>             # From the list of tokens
       roll                   : 3          # Pick 3 times with replacement
  say |                                    # Join and print

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


text:
Ration your integers and feed the people
It is wartime, and rationing is taking place in certain regions of your country. Your cities' region is one such region. The city chooses to give everyone the same amount, but in reality, larger people need more food. Chances are, a 200lb man is going to be eating more than that 7lb baby over there. The city, realizing that some people need more food, hires you, their best computer programmer, to solve the issue. They want you to write a program that will divvy up the food appropriately.
Being a smart programmer, you have developed a formula that gives an approximation of how much someone will eat based on their weight.
EAT = (WEIGHT - 1) / 20 + 1
For example, a 124 pound man will eat 7.125 units of food. Knowing that the food is served in packages of 1, and it would be irrational to cut them up, you can round the food units.
Each day, every person eats that many food units. If somebody goes for five days straight with less than that much food per day, they die of starvation.
You will receive population data in this form: Population*Weight, so if you receive 700*180, you know that their are 700 180lb men in the city. Your city has 100,000 units of food stored away.
For every day your city goes without anyone dying, you get one point. Whoever has the most points wins. Make sure you output how many days your city lasted before someone died.
Here is the input:
1000x90
2500x80
3000x150
2500x200
Edit: So, the rule "For every day your city goes without anyone dying, you get one point" was terribly abused. Rule change here: if anybody dies, then game over. No more counting.

I like it. Those who habitually eat too much (and therefore are obese) get to carry on eating too much. This is exactly the way bureaucracy works (especially with annual budgets.) +1.

If somebody goes for five days straight with less than that much food, they die of starvation. This means if somebody goes for 5 days straight with less than the portion of food that person needs for 1 day, then they die of starvation?

This is really neat. Just a few things: is the separator x or * or up to us? Any restrictions on the kind of input? Does it have to be from stdin or could it be a function argument? Does it have to be a \n delimited string or could it be an array of strings? What rounding should we use? And what's the output? Just the number of days? Or instructions on how to distribute food each day? Also some simple solved test cases might be useful...

It's generally a good idea to run challenges through the sandbox before posting to clarify such things.

You've told us what form the input will take, but not what we should output.

Also, if I feed each person the required amount every fifth day and don't feed them at all for the other 4 days no one will die, whereas if I'm 0.0001 unit below the required amount for 5 days in a row they die. Seems a bit unfair?

Thinking about it, isn't the solution actually quite trivial? To keep everyone alive for the first five days, I need to feed each person their required ration on day 5, which costs me 70550 units assuming "normal" rounding. The next 4 days no one will starve, but on day 10 I don't have another 70550 units to avoid someone dying. So 9 days is the maximum. Please correct me if I'm wrong.

@m.buettner I correct you in the form of my answer. ;)

@Doorknob I agree that "For every day your city goes without anyone dying, you get one point. Whoever has the most points wins." could be interpreted as you did it. But "Make sure you output how many days your city lasted before someone died." really seems to mean that the OP was getting at how long you can go without anyone dying at all. In any case that doesn't change that the solution is quite trivial and not subject to any interesting optimisation.

@m.buettner Okay, now I output how many days I lasted before someone died. The OP never mentioned anything about that affecting the score. :D

Rounding definitely needs to be defined.

Rounding eat up gives 70,000 units per day. Rounding down gives 66,500 units per day. Doesn't seem like one could make the bulk of the city survive for more than a few days

Aww, question got closed just as I wanted to post this answer:
bc / bash
It's a nice challenge, but I had the same idea as @m.buettner had and was going to post a comment along the lines of "you don't need a program for this, a mere calculator is enough". Then I realised, that there is a nice calculator in Unix: bc:
`scale=3;
define eat(w) { return (w - 1) / 20 + 1; }
needperfivedays = (1000*eat(90) + 2500*eat(80) + 3000*eat(150) + 2500*eat(200));
5 * (1 + 100000 / needperfivedays );`

Sad. This question has potential too. If only some more detail on how/when people die.

Ass. Happened again to me. Online Python version lasted 10 days. Could probably get more by tweaking the algorithm. Another question i could not answer at time. D:

All those who closed: pleas see the bottom of the post.

@joeelectricity please re-read my comments. Even with this last line there remain several things to clarify and in any case, this problem does seem to present any actual challenge which would inspire interesting (or even competing) answers. That's why I can only (again) suggest, you post this in the sandbox and try to refine the challenge with the help of the community.

Ruby, 100003 days/points (~274 years), 5 days before someone dies

For every day your city goes without anyone dying, you get one point.

I shall abuse this rule as much as possible!

Make sure you output how many days your city lasted before someone died.

Ok, I did. You didn't say anything about that affecting your score.
#input = STDIN.read
input = "1000x90
2500x80
3000x150
2500x200" # temporary debugging tool

food = 100000

input = input.split.map{|x| x.split('x').map &:to_i }
onlyPersonToFeedWeight = input.sort_by! {|a|
  a[1] # weight of person
}.first[1] # find the lightest weighing person
foodForOnePerson =  ((onlyPersonToFeedWeight - 1) / 20.0 + 1).ceil # EAT = (WEIGHT - 1) / 20 + 1

# you can see where this is going

daysNobodyDied = 0
daysSomeoneDied = 0

# first kill off all these overweight people
daysNobodyDied += 4
food -= foodForOnePerson
daysSomeoneDied += 1 # it's only all but one person in the city, don't worry

# I have a good feeling about this now
# ... I'm evil

loop {
  daysNobodyDied += 4
  food -= foodForOnePerson
  if food >= 0
    daysNobodyDied += 1
  else
    daysSomeoneDied += 1
    break
  end
}

puts "Survived for #{daysNobodyDied} days"
puts "There were #{daysSomeoneDied} days in which someone died"
puts "The first person died on day 5"

Output:
Survived for 100003 days
There were 2 days in which someone died
The first person died on day 5

I suggest you read the comments in the code first; they're quite amusing. ;) (Code is intentionally verbose.)
The strategy is simple:

On the first five days, only feed the lightest person (on the fifth day). Then everyone else dies so you don't have to worry about them.
Continue to starve this poor man with no friends or family by only feeding him once every five days until you run out of food.
The man will probably die before you run out of food since it will now last 274 years.

Does this make me evil or something?
Oh, and by the way, if he was lying down the whole time, he'd have a better than even chance that a bird would poop in his mouth. (Assuming the birds didn't starve.) Thanks for the... interesting fact, @Synthetica :-P

I thought the output was "...how many days your city lasted before someone died", not until everyone died.

@Geobits "For every day your city goes without anyone dying, you get one point."

I suppose the OP needs to clarify the point, since it can be interpreted both ways.

I think the obvious interpretation is at the point of the first death the game is over. You want city to be defined? day? dying? Fun interpretation. I feel that there are large quantities of protein which become available, so with males, females, and sufficient arrangement of deaths for consumption, there may be a way to get to 274 year (and longer) with population remaining. Another question, perhaps...

On mature reflection, your answer is growing on me. Upvoted even. Realised the question as it stands is not about any actual programming, but just coding a program correctly. So why not? Let me find my copy of Soylent Green and see if I can get some ideas...

BTW, is this guy doing anything beside just hanging around? https://www.wolframalpha.com/input/?i=100003%20days I didn't know the guys at Wolfram|Alpha red whatif-XKCD ;).

Following your argument you can put the score to infinity. The poster didn't specify that you should stop counting when the last one died. That's even more ridiculous and shows that it is a non-answer.

Please see my edit; I hadn't realized the loophole there ;). Under the new meanie rules, you only got 5 points.

Under this interpretation you have infinite days. Even after the last person dies, there's many days where no one dies.

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


text:
Solve a deterministic version of 2048 using the fewest bytes
Write a program that generates a winning sequence of moves to the deterministic variant of the game 2048. The sequence should be in the form of a string of numbers 0-3, with 0: up, 1: right, 2: down, 3: left.
For example, the string "1132" means right right left down. The winning program is the shortest source code that gets to 2048!
The rules to deterministic 2048:
The game is played on a 4x4 grid initially containing 1 tile, in the upper left-hand corner. Each move consists of the command "left", "right", "up" or "down". The command left slides all the tiles on the grid to the left, then combines and sums like tiles starting from the left. Likewise, the command right slides tiles to the right, then combines starting from the right.
Each tile can only participate in one combination per move.
After a move, a new 2 tile is created in the first column from the left with an available space, in the first available space from the top in that column.
For example, the sequence "right right left down" leads to the states
2___
____
____
____

2__2
____
____
____

2__4
____
____
____

24__
2___
____
____

2___
____
____
44__

The command right applied to the row _ 2 2 2 results in _ _ 2 4
The command right applied to the row 2 2 2 2 results in _ _ 4 4
This question inspired by http://jmfork.github.io/2048/

Challenges should be self-contained - what if that link dies?

This question appears to be off-topic because it is essentially a "link-only question."

$(".tile-container").addItem("
2048
");

I see the problem you have pointed out, and am fixing it. Should I delete this and repost when it's fixed, or just edit the post?

@user19700 If it's closed, it will be reopened once it's fixed.

I changed the description to be self-sufficient. If I create a script that verifies and animates sequences generated to the above spec, would it be off topic to link it?

@QuadmasterXLII you might clarify in your description the expected behaviour for 3 consecutive (identical) numbers

I added clarification. Thanks for the heads up!

Great! Close vote retracted. I still have an issue here: since it's deterministic, can't people just find the shortest output and then just output that?

@Doorknob: That would be a "not funny anymore" solution - something we shouldn't even have to explicitly state not to do

Python, 740 characters (665 characters compressed)
Code:
R=range
G=lambda:[[0]*4for _ in R(4)]
J=[(0,4,1),(2,-1,-1),(1,4,1)]
H=[0,-1,1]
def M(P,d):
 C=G();g,z=[(0,-1),(1,0),(0,1),(-1,0)][d];Q=H[g];W=H[z]
 while 1:
    N=[r[:]for r in P]
    for x in R(*J[g]):
     for y in R(*J[z]):
        s=N[y][x];q,w=y-W,x-Q;d=N[q][w];a,b,c=(((0,s,d),(1,0,s+d))[s==d],(0,0,s or d))[s<1 or d<1];
        if 2-a-(C[y][x]+C[q][w]>0):N[y][x]=b;N[q][w]=c;C[q][w]+=a
    if N==P:break
    P=N
 return N
def F(N):
 for x in R(4):
    for y in R(4):
     if N[y][x]==0:N[y][x]=2;return N
def Z(P,i):
 X=[d for d in R(4)if M(P,d)!=P]
 return i==0and(sum((256,c)[c>0] for v in P for c in v)+P[3][3]*10+P[3][2]*9,-1)or max((Z(F(M(P,d)),i-1)[0],d)for d in X)if X else(-1,-1)
B=G()
B[0][0]=2
h=''
while B[3][3]!=2048:_,X=Z(B,4);h+=`X`;B=F(M(B,X))
print h

(Mixes tabs with spaces for indentation to save a few bytes)
I must have sucked at golfing it because if I just compress the above code, base-64 encode it, and exec it, it's only 665 characters. The following is exactly equivalent to the above, no hard-coded solution or anything:
exec"""eJxVUl1vozAQfMa/wn2qnRjJcNzpDnf7QKS2qlRE+1IUy2oJkARdwl2hbT5+/a0NiXqSZXYH78zY
u0/QFe2qJrewKbaLqoi1lmYSLf909IU2LX1iETfkHjSTIhIBFywUfoALo8AhhtyBlhYMDKnqJX1g
mah4TOgMbhlXK3F01WOJxF06It8mRldGPcKdXhn1jJ+jIXS3bjY1DWLipaA7HRvrprNuMkM8m+wH
a5N7LEMlj1rwcAaPDvR6SPXB6L1Rb2IHB/9Z7P1HVSH6ZvTOqEIsRAmMoZ8eHTt3op9WnOseoDLW
KAIUuR12FbjwKjAK2ZslDf3CZ7NBYzobWK8lj0dZWKhRCko1/p5CQWxpCpDFi64ufhMvg5TQrn7/
6Fqauie8Yal9wC9XjeyNvtzS5dQSjVogz7Kh+o9sjv1oLF0OunKc1YmjOXXrAvBpTx4aJCvaivUf
W8bC7z9EyXV5LY2r/XR9cGFpw08+zfQ3g2sSyCEMzeSXbTce2RZ7xubshg0yXDSI44RhfDaSWxs5
rTd9zYbRIomdHJLgQVwQkjVcXpJhLJJB7AJCGf2MX0QOc5aIiKv1FF7zV5WAFUtEzjn52zXtO13/
AwRvylc=""".decode('base64').decode('zip')

Answer:
Takes ~47 seconds (17 seconds ungolfed) to find the 1111-move sequence:

2221230232213120120232222222221221203211012312310123123101223113322222123230210302321222323223212322101202323123322032132021233212312332023123312111123231223113312312322312232123222021221332111332221012222312222302232021233212312332023212222222123221202332023120312123223221232232222222122122323222222212212232222222221322233231222322200232122312232313132022322212312332121332312320212211332312323223212320232322322133223213212323202123123321231313332122232310112113322212323222220130231233211313332122232312312223232231231232312222220232212312220212232312232123222021221332111332221012222312222302232021233212312332023212222222123221202332023120312123223221322323223312230230323312232313133232223233212312323123323222332222222132221321320323233223232121323212232013221323233032021223320231233220322203132123202123321231233202131321221111231213232131210212312232332132103123130213133213232213321323212332332212222123323322202302333121220222323232113123323221223032131201123212133123131222323313133313300123231332011222221223232331313313112312113230231121232332122323232321312323213212232313212323211330231231012

With the following final board position and move:
   4    2   16    4
   2    8  128    8
   2    .    . 1024
   .    .    . 1024
Best move: s, with EV=25654

Trivia: the solution is 309 bytes gzipped and 418 bytes if gzipped and base64-encoded. Thus it would be a shorter program to just decode that and print it out, but that is no fun at all.
Explanation:
Here's a pastebin of the ungolfed version which prints out the board after each move, very fun to watch!
It's a very simple brute-force AI. It assigns an EV for each board position:
ev =   256 * number of spaces
     + sum_of_values
     + 10 * board_bottom_right
     +  9 * board_bottom_2nd_right

It does a depth-first search four moves ahead and picks the path that leads to the highest EV in four moves. The ev function encourages it to clean up the board and to keep the highest-valued pieces in the corner, which ends up being pretty optimal. It's enough to get it there!
If you modify the EV function to place a higher value on other board spots, something like:
1  1  1  1
1  1  1  1
1  1  9 10
1  9 10 11

That function gets it as far as:
   2    8    4    2
  16   32   64   16
  64  128  512 1024
   2  256 2048 8192

16k:
Eureka! With a 5-step lookahead instead of a 4, and the following weights:
1  1  4  4
1  1  4 10
1  1 14 16
1 16 18 20

It almost almost gets 32k, ending on:
   2  128    4     2
  64  256  512     4
   4  128 1024  4096
  16 2048 8192 16384

The sequence is here.
32k:
Yes ladies and gentlemen, we have hit the 32k mark. The EV function, instead of multiplying squares by a constant, raises each square to the following powers and adds them. x means the square isn't involved:
x x x 3
x x x 4
x x 5 6
x 6 7 8

It still sums all the values once and adds 256 for each empty square. Lookahead was 4 all the way up to 32k, and then it bumped up to 5, but it doesn't really seem to do much. End board:
   2  128    8     2
  64  256  512     4
   4  128 1024  2048
  16 4096 8192 32768

Pastebin of the 24,625-move sequence.

This solution is brilliant (I love your brute force + look-ahead DFS), epic explanation and your quest for ever higher powers of two is most excellent. +1!

Nice one! Using a heuristic with depth first possibly precludes you from reaching optimal solutions (shortest move sequence). Maybe you can incorporate an A* search :-)

tar -xzvf a.tar; python a