text:
Implement superoptimizer for addition
The task is to write code that can find small logical formulae for sums of bits.
The overall challenge is for your code to find the smallest possible propositional logical formula to check if the sum of y binary 0/1 variables equals some value x.  Let us call the variables x1, x2, x3, x4 etc.  Your expression should be equivalent to the sum. That is, the logical formula should be true if and only if the sum equals x.
Here is a naive way to do it to start with.  Say y=15 and x = 5. Pick all 3003 different ways of choosing 5 variables and for each make a new clause with the AND of those variables AND the AND of the negation of the remaining variables. You end up with 3003 clauses each of length exactly 15 for a total cost of 45054.
Your answer should take be a logical expression of that sort that can just be pasted into python, say, so I can test it.  If two people get the same size expression, the code that runs the fastest wins.
You ARE allowed to introduce new variables into your solution.  So in this case your logical formula consists of the y binary variables, x and some new variables.  The whole formula would be satisfiable if and only if the sum of the y variables equals x.
As a starting exercise some people may want to start with y=5 variables adding to x=2.  The naive method will then give a cost of 50.
The code should take two values y and x as inputs and output the formula and its size as the output.  The cost of a solution is just the raw count of variables in its output.  So (a or b) and (!a or c)  counts as 4.    The only allowed operators are and, or and not.
Update It turns out there is a clever method for solving this problem when  x =1, at least in theory .

This is off-topic. As you said: this question is about optimizing a logical expression. It's not a programming challenge/puzzle in any way.

@shiona The challenge is to think of a clever way to do it that runs quickly enough.  Maybe I should rephrase to make this clearer.  I think of it like a challenge to write  a superoptimizer.

Please define more precisely the "size".  Your description implies NOT isn't counted.  Or just raw variable negation doesn't count?  Each binary AND/OR counts as one?

Is this a golf or a challenge or what ? (It's an interesting problem area so I'd like to see the question's short-comings fixed - it would be a shame if it got closed.)

@PaulR It's meant to be a programming challenge (not a challenge to write the shortest code).  I have hopefully added a better tag.

Can you confirm exactly which operators are allowed in the final expression ? Would is just be AND/OR/NOT ? How about XOR ? NAND/NOR ? Arithmetic operators such as +/- ?

@PaulR Thanks for asking and sorry it wasn't clear before. Just AND/OR/NOT .

Yeah. 4 close votes and everything that prevents me from closing this question is an open bounty.

@JohannesKuhn Is there anything I can do to improve the question?

So for the example with y=5 and x=2, the output would be a logical expression that holds when exactly 2 of the y_i's are true, and the goal is to express this with as few {and,or,not}s as possible. Is this correct?

@Firefly  Yes. Well you can have as many nots as you like. I am just counting the number of occurrences of variables in the score.  The logical expression (not y[0] and y[1] ) or (y[0] and not y[1]) would give  a score of 4, for example, if it were actually correct for something.

How will introducing new variables work with the score? Say I want to let z[0] = y[0] and y[1], how do you want this indicated?

@Kaya The new variables would have to be in the logical formula and so are counted the same way as all the other variables. See my latest edit to the question or http://www.cs.cmu.edu/~wklieber/papers/2007_efficient-cnf-encoding-for-selecting-1.pdf for some concrete examples of how to introduce new variables.

Can you include an example including the result and how it's scored in your question? You haven't specified anything about how new variables are counted. If someone says z[0] = (y[0] or y[0]) and not y[1] with a result of z[0] or not z[0] or z[0], how is the scoring calculation done? Is it 3 because only the variables in the result expression count? Is it 9 because recursively expanding the zs gives a total 9 ys? Is it 7, since that's the count of variables that appear anywhere? Is it 6 because anything on the left side of an assignment equal sign doesn't count? Is it something else?

@Olathe The logical formula output can't have an equals sign in it, it is just a logical formula that is satisfiable if and only if the sum of the binary  y variables equals x.  Did I misunderstand you?

@Lembik thanks for the pdf link, I believe I understand now. If I desire to have the variable z[0] represent y[0] or y[1] then I would just need to introduce a clause that looks like (y[0] or y[1]) or not z[0] (or any equivalent statement using the 3 operators allowed).

@Kaya That is my understanding too. Now the problem is how to search for the minimal representation :)

@Lembik, I haven't done these kinds of problems before and Kaya's statement clears up what's going on.

@Olathe  Great and thanks to Kaya.

Python, 644
A simple recursive equation generator.  S generates an equation that is satisfied iff the list of vars adds up to total.
There are some obvious improvements to be done.  For instance, there are a lot of common subexpressions that appear in the 15/5 output.
def S(vars, total):
    # base case
    if total == 0:
        return "(" + " and ".join("not " + x for x in vars) + ")"
    if total == len(vars):
        return "(" + " and ".join(vars) + ")"

    # recursive case
    n = len(vars)/2
    clauses = []
    for s in xrange(total+1):
        if s > n or total-s > len(vars)-n: continue
        a = S(vars[:n], s)
        b = S(vars[n:], total-s)
        clauses += ["(" + a + " and " + b + ")"]
    return "(" + " or ".join(clauses) + ")"

def T(n, total):
    e = S(["x[%d]"%i for i in xrange(n)], total)
    print "equation", e
    print "score", e.count("[")

    # test it
    for i in xrange(2**n):
        x = [i/2**k%2 for k in xrange(n)]
        if eval(e) != (sum(x) == total):
            print "wrong", x

T(2, 1)
T(5, 2)
T(15, 5)

Generates:
equation (((not x[0]) and (x[1])) or ((x[0]) and (not x[1])))
score 4
equation (((not x[0] and not x[1]) and (((not x[2]) and (x[3] and x[4])) or ((x[2]) and (((not x[3]) and (x[4])) or ((x[3]) and (not x[4])))))) or ((((not x[0]) and (x[1])) or ((x[0]) and (not x[1]))) and (((not x[2]) and (((not x[3]) and (x[4])) or ((x[3]) and (not x[4])))) or ((x[2]) and (not x[3] and not x[4])))) or ((x[0] and x[1]) and (not x[2] and not x[3] and not x[4])))
score 27
equation (((not x[0] and not x[1] and not x[2] and not x[3] and not x[4] and not x[5] and not x[6]) and (((((not x[7] and not x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (not x[9] and not x[10]))) and (x[11] and x[12] and x[13] and x[14])) or ((((not x[7] and not x[8]) and (x[9] and x[10])) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((x[7] and x[8]) and (not x[9] and not x[10]))) and (((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (x[13] and x[14])) or ((x[11] and x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))))) or ((((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (x[9] and x[10])) or ((x[7] and x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10]))))) and (((not x[11] and not x[12]) and (x[13] and x[14])) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((x[11] and x[12]) and (not x[13] and not x[14])))) or ((x[7] and x[8] and x[9] and x[10]) and (((not x[11] and not x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (not x[13] and not x[14])))))) or ((((not x[0] and not x[1] and not x[2]) and (((not x[3] and not x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (not x[5] and not x[6])))) or ((((not x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2])))) or ((x[0]) and (not x[1] and not x[2]))) and (not x[3] and not x[4] and not x[5] and not x[6]))) and (((not x[7] and not x[8] and not x[9] and not x[10]) and (x[11] and x[12] and x[13] and x[14])) or ((((not x[7] and not x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (not x[9] and not x[10]))) and (((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (x[13] and x[14])) or ((x[11] and x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))))) or ((((not x[7] and not x[8]) and (x[9] and x[10])) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((x[7] and x[8]) and (not x[9] and not x[10]))) and (((not x[11] and not x[12]) and (x[13] and x[14])) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((x[11] and x[12]) and (not x[13] and not x[14])))) or ((((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (x[9] and x[10])) or ((x[7] and x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10]))))) and (((not x[11] and not x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (not x[13] and not x[14])))) or ((x[7] and x[8] and x[9] and x[10]) and (not x[11] and not x[12] and not x[13] and not x[14])))) or ((((not x[0] and not x[1] and not x[2]) and (((not x[3] and not x[4]) and (x[5] and x[6])) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((x[3] and x[4]) and (not x[5] and not x[6])))) or ((((not x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2])))) or ((x[0]) and (not x[1] and not x[2]))) and (((not x[3] and not x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (not x[5] and not x[6])))) or ((((not x[0]) and (x[1] and x[2])) or ((x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2]))))) and (not x[3] and not x[4] and not x[5] and not x[6]))) and (((not x[7] and not x[8] and not x[9] and not x[10]) and (((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (x[13] and x[14])) or ((x[11] and x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))))) or ((((not x[7] and not x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (not x[9] and not x[10]))) and (((not x[11] and not x[12]) and (x[13] and x[14])) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((x[11] and x[12]) and (not x[13] and not x[14])))) or ((((not x[7] and not x[8]) and (x[9] and x[10])) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((x[7] and x[8]) and (not x[9] and not x[10]))) and (((not x[11] and not x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (not x[13] and not x[14])))) or ((((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (x[9] and x[10])) or ((x[7] and x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10]))))) and (not x[11] and not x[12] and not x[13] and not x[14])))) or ((((not x[0] and not x[1] and not x[2]) and (((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (x[5] and x[6])) or ((x[3] and x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))))) or ((((not x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2])))) or ((x[0]) and (not x[1] and not x[2]))) and (((not x[3] and not x[4]) and (x[5] and x[6])) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((x[3] and x[4]) and (not x[5] and not x[6])))) or ((((not x[0]) and (x[1] and x[2])) or ((x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2]))))) and (((not x[3] and not x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (not x[5] and not x[6])))) or ((x[0] and x[1] and x[2]) and (not x[3] and not x[4] and not x[5] and not x[6]))) and (((not x[7] and not x[8] and not x[9] and not x[10]) and (((not x[11] and not x[12]) and (x[13] and x[14])) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((x[11] and x[12]) and (not x[13] and not x[14])))) or ((((not x[7] and not x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (not x[9] and not x[10]))) and (((not x[11] and not x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (not x[13] and not x[14])))) or ((((not x[7] and not x[8]) and (x[9] and x[10])) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((x[7] and x[8]) and (not x[9] and not x[10]))) and (not x[11] and not x[12] and not x[13] and not x[14])))) or ((((not x[0] and not x[1] and not x[2]) and (x[3] and x[4] and x[5] and x[6])) or ((((not x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2])))) or ((x[0]) and (not x[1] and not x[2]))) and (((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (x[5] and x[6])) or ((x[3] and x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))))) or ((((not x[0]) and (x[1] and x[2])) or ((x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2]))))) and (((not x[3] and not x[4]) and (x[5] and x[6])) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((x[3] and x[4]) and (not x[5] and not x[6])))) or ((x[0] and x[1] and x[2]) and (((not x[3] and not x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (not x[5] and not x[6]))))) and (((not x[7] and not x[8] and not x[9] and not x[10]) and (((not x[11] and not x[12]) and (((not x[13]) and (x[14])) or ((x[13]) and (not x[14])))) or ((((not x[11]) and (x[12])) or ((x[11]) and (not x[12]))) and (not x[13] and not x[14])))) or ((((not x[7] and not x[8]) and (((not x[9]) and (x[10])) or ((x[9]) and (not x[10])))) or ((((not x[7]) and (x[8])) or ((x[7]) and (not x[8]))) and (not x[9] and not x[10]))) and (not x[11] and not x[12] and not x[13] and not x[14])))) or ((((((not x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2])))) or ((x[0]) and (not x[1] and not x[2]))) and (x[3] and x[4] and x[5] and x[6])) or ((((not x[0]) and (x[1] and x[2])) or ((x[0]) and (((not x[1]) and (x[2])) or ((x[1]) and (not x[2]))))) and (((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (x[5] and x[6])) or ((x[3] and x[4]) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))))) or ((x[0] and x[1] and x[2]) and (((not x[3] and not x[4]) and (x[5] and x[6])) or ((((not x[3]) and (x[4])) or ((x[3]) and (not x[4]))) and (((not x[5]) and (x[6])) or ((x[5]) and (not x[6])))) or ((x[3] and x[4]) and (not x[5] and not x[6]))))) and (not x[7] and not x[8] and not x[9] and not x[10] and not x[11] and not x[12] and not x[13] and not x[14])))
score 644

This is very nice. How much smaller do you think the solutions could be?

@Lembik: haven't really thought about it.  You'd have to define new variables for common subexpressions.  For instance, not x[0] and not x[1] and not x[2] appears 5 times in the 15/5 expression.

I would have made this a comment, but I don't have a reputation. I wanted to comment that the results of Kwon & Klieber (known as the "Commander" encoding) for k=1 have been generalised for k>=2 by Frisch et al. "SAT Encodings of the At-Most-k Constraint." What you're asking about is a special case of the AM-k constraint, with an additional clause to guarantee At-Least-k, which is trivial, just a disjunction of the all variables to the AM-k constraint. Frisch is a leading researcher in constraint modelling, so I would feel comfortable suggesting that [(2k+2 C k+1) + (2k+2 C k-1)] * n/2 is the best bound known on the number of clauses required, and k*n/2 for the number of new variables to be introduced. The details are in the quoted paper, along with the instructions of how this encoding to built. It's fairly simple to write a program to generate this formula, and I think such a solution would be competitive with any other solutions you'll likely find for now. HTH.

Thank you. It would be interesting to see if this is still the best for my cost measurement for small problem sizes where some exhaustive super optimization might be possible.  Hopefully someone here will try this out.

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


text:
Make a colorful table
For this challenge, you must accept input as a comma-separated list (columns) of a run (rows) of the first letters of any of the colors red, orange, yellow, green, blue, or purple, and output (to stdout) the HTML for a table of those colors.
This is fairly hard to understand, so I'll just give a simple example.
Input:
rgb,gbr,grb

Output (with example screenshot):

Note that the HTML you output need not be valid; it just has to work. By "work", I mean that your output will be pasted into a .html file and viewed in the latest (currently, 9/28/13) Chrome (v 29.0.1547.76). The squares must be 50 pixels width and height. You may have whatever padding between them as you want (Chrome automatically uses 1 pixel of padding, even when you specify padding: 0px, so I can't control that).
Input will always be valid (letters will be one of roygbp), but the rows are not guaranteed to have equal amounts of squares in them. For example, roygbp,ooo is valid and should output

This is code-golf, shortest code wins.

Table layouts >:(

@minitech They're not layouts :P and anything goes in code golf :D

Perl: 153 126 124 116 114 characters
s!\w!''!ge;s!,!
!g;$_="
$_"

Sample run:
bash-4.1$ perl -p table.pl <<< 'rgb,oyp'

Sample output:
bash-4.1$ perl -p table.pl <<< 'yrryyryyryyyrrr,ryyyryryryyyryy,ryryryryryyyrry,yrryyryyrrryryy'

Razor Leaf, 136
table for r in prompt().split(",")
    tr for x in r
        td bgcolor:"##{"rf00of90yff0g070b00fp707".match(x+"(...)")[1]}"width:"50"height:"50"

Razor Leaf. The indentation is tabs, by the way.
You might have some trouble running this in a browser, so try Node.js and define global.prompt to return a fixed output. :)
var fs = require("fs");
var razorleaf = require("razorleaf");

global.prompt = function() {
    return "rgb,byp";
};

console.log(razorleaf.compile(fs.readFileSync("test.leaf", "utf-8"))());

Using other people’s tricks is 126, but that’s no good.
table cellpadding:"26"for r in prompt().split(",")
    tr for x in r
        td bgcolor:"##{"rf00rof90oyff0yg070gb00fbp707".split(x)[1]}"

ooh, interesting language! I'm going to look in to that :D

Mathematica 148 139
d_~f~n_:=Export[n,Grid@ToExpression@Characters@d/.{r->Red,o->Orange,y->Yellow,g->Green,
b->Blue,p->Purple}/.{x_RGBColor:>Graphics@{x,Rectangle[]}}]

f, defined above, is a simple function that takes the color strings as input and outputs an HTML file.
Usage
f[{"rgb","gbr","grb"}, "ColorfulTable.html"]

The HTML code that is output to file "ColorfulTable.html":
< ?xml version="1.0" encoding="UTF-8"?>
< ! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0//EN"
"HTMLFiles/xhtml-math11-f.dtd" >
< ! --Created by Wolfram Mathematica 9.0 : www.wolfram.com-- >

< title > Untitled
< /title >
< link href = "HTMLFiles/ColorfulTable.css" rel = "stylesheet" type = "text/css"/ >

                Created with  Wolfram  Mathematica  9.0

HTML rendering in Chrome

Hmm... this is stretching the rules a lot... input is very different from specified and it outputs to a file, not stdout. I'm afraid that this breaks too many rules, but very creative :D (oh, and btw I count 171 chars)

too bad. In principal, I ought to be able to input the HTML as a string, leaving it in standard output. But I haven't figured out how to do it yet. The byte count seems to be correct. I used the automatic-counter from Wolfram's One-Liner Competition.  The spaces are by and large optional. And :> is a single character in Mathematica.

lettercount.com says 147 for the current code? Missed to update it ?

-> and :> are single characters in Mathematica. And  is included only for readability.

JavaScript, 203 146
for(h='
',p=prompt(),i=0;c=p[i++];)
h+=","==c?"
":'';
alert(h)

Credit to @C5H8NNaO4 for the single loop & cellpadding ideas. I'm using a split string to find the right color. (the line breaks were added for readability)
Input:
rgb,bgroyp

Output:

Here's the JSFiddle
Does anyone know how to use unicode characters in JSFiddle? I could shave a few more characters off, but some characters wouldn't paste in correctly.

Nice improvement, especially the colorfinding =)

wait did you just copy mine,replaced the color object and moved 2 vars inside the for ? =P +1 anyway

GolfScript, 154 144 119
'

'\{:^44='
'{""}if}%

Online test
With credit to @bendytree for introducing the no-close-tags trend which allowed me to cut 25 chars.

Python 3 (158)
print('
',*['
'+''.join(''%dict(r=3840,o=3984,y=4080,g=96,b=15,p=1799)[c]for c in r)for r in input().split(',')])

Cool things:

This uses the * operator to pass multiple arguments to print, saving 6  characters compared to ''.join.
The colors are stored in decimal, then rendered as hex in the HTML. I found this to be much shorter than using string literals directly.

Javascript, 199 183 173 171 167 164 159 158 154
h="
";p=prompt();for(i=0;c=p[i++];)h+=","==c?"
":'';alert(h)

just realized i don't need an opening
 tag
stupid me, i of course do not need to split the input string to access single chars
... as well as i of course do not need to initialise c
inlined the lookup object
you can actually leave out the px for width and height
changed width and height to cellpadding 26px
replaced
 with

removed the ' around 26 at the cellpadding and from the bgcolor

Changin the for to a for .. in loop would save only one character, so i keep the for
Example Output for roygbp,ooo

ECMAScript 6: 148 characters
alert('
'+prompt().replace(/./g,x=>x==','?'
':''))

(Just to exercise the fat arrow syntax.)

Could you name your language ECMAScript 6? As the latest firefox is currently the only browser supporting it, it would avoid confusion

Ok. And thanks for the information. (Sadly I had no time to test in other browsers. But one thing is sure: in Firefox is available since version 22, not only the latest. ;))

=) Thanks, ( I would love seeing chrome supporting ES6 soon). Well yeah :P "latest" is the wrong word here, I'm not using firefox and am not up to date with their versions. So i think "the newer firefox browsers" would have been more appropriate. Nice use of the regex engine to create the complete table! +1

PHP, 182 164 163 characters
Example input:
<?php $x = 'roygbp,ooo'; ?>

Update 1; if you silence (or just ignore) E_NOTICE you can remove the quotes around strings that start with letters, shaving off another 18 characters
Update 2; trimmed 1 character!
<?php echo'

';$a=[r=>f00,g=>'080',b=>blue,o=>fa0,p=>'808',y=>ff0];foreach(str_split($x)as$b){echo$b==','?'
':"";}?>

You could change b=>'00f' to b=>blue to save 1 character, and remove cellpadding=50 to save 15.

@Doorknob Nice catch, but removing the cellpadding would make the boxes 2px x 2px; wouldn't that be cheating out of the assignment specification?

Ruby, 221 187
I am presenting my own solution first, as always:
$><<'
'+gets.chop.split(?,).map{|r|'
'+r.chars.map{|t|"	"}*''+'
'}*''+'
'

That can be reduced to 187 with some simple tricks: $><<'
'+gets.chop.split(?,).map{|r|'
'+r.chars.map{|t|"	"}*''+'
'}*''+'
'.

PHP, 277 characters
<?foreach(split(",",fgets(STDIN))as$r){?>
<?foreach(str_split($r)as$c)echo"

"?>
<?}?>

Input:
rgb,bgr,gbr

Output:

Hmmm... the stylesheet is killing me here. I don't have time now, but I'll come back to have a look at this later.
And yes, I'm deliberately not using tables for layout. ;-)

Python 2.7 (176)
I=raw_input().split(",")
h="
"
c=dict(r=3840,o=3984,y=4080,g=96,b=15,p=1799)
for r in I:
 h+="
"
 for x in r:h+=""%c[x]
print h

I pinched the use of dict and the insertion of Hex values from @Lambda Fairy
And for good measure, here is a jsfiddle with an example output

source: Stack Exchange

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

sort: votes


text:
string length comparer
this program has to take two strings and compare their length, then tell you which one is longer (string-a or string-b) and by how much
rules:

no using .length or other built-in length checking methods (duh!)
no using addition or subtraction, this includes improvised addition/subtraction, in case you find some sort of weird improvisation.
no > / < (greater then/less then) inside if / if-else statements (you can use them in loops though), this obviously includes >= etc. and no cheating (bool = a > b;if(bool))
emphasis is on short rather then efficient code
oh yeah almost forgot... good luck!

Is it code-golf? If so, tag it. If not, define the winning criteria.

@ugoren sorry not sure where to draw the line, i want shortest within the criteria, is that challenge or golf?

What is the format of the string ? Does it have some special terminator (e.g. C-style NUL) ?

what should it say if they are both the same size? anything or blank?

@lalalalalalalambda you could do blank, its a technical loophole if i didnt specify it.

why the -1 guys?

@PaulR if i dont specify, you can do whatever you want, as long as it fits the rules.

-1s are probably because your question is very unclear; you don't specify what format the strings are in, how to call the program, what the output should be, etc.

To Doorknob's comment I would add that questions of the form "Do a task that would normally be insanely trivial but with your hands cuffed behind your back" might make for amusing television, but in the context of programming challenges they largely come down to arguing that a particular language feature doesn't technically break the arbitrary restriction.

@PeterTaylor true, i didnt really think about that.

"no > / < (greater then/less then) inside if / if-else"  while(a>b){ do_something(); break;} is equivalent to an if...

@MrZander "and no cheating", obviously a run-once loop is not allowed.

@PeterTaylor: To be fair, doing things with your hands cuffed behind your back is the reason I mostly golf in sed :P

No addition and subtraction, and no reproducing it? You can’t reasonably expect a number.

@minitech thats what code puzzles are all about...

@tryingToGetProgrammingStraight: Code puzzles still have to be possible. Every single answer here involves addition, by the way.

@minitech it can involve addition, and subtraction, just not in order to determine which is longer - you can still use it in a printf or whatever, see answer from @C5H8NNaO4 (my favorite here).

It’s your statement that “improvised addition/subtraction is not allowed” that makes this question really… open to debate. The top sed solution improvises addition and subtraction by doing it in unary. It’s still improvised, but it’s in a different base. How far do you have to “improvise” before it’s not against the rules?

@minitech: Actually, my sed solution only subtracts (in unary, as I'm removing pairs of letters on each side), though technically only string substitutions are used. It's might be an abuse of the rules (eg. since output wasn't specified, using unary "a" and "b", the remains of the string), but so are most of the other answers.

@Hasturkun: But you’re adding a negative number. Gosh. (See, I just don’t know where it’s supposed to end…)

Relevant

SED, 45 (43 + 2 for the -n flag)
s/./a/g
h
n
s/./b/g
G
:a
s/b\(.*\)a/\1/
ta

Expects input as two separate lines, outputs the difference in unary, using "a" or "b" to indicate the longer string. run with sed -n.

Tcl 8.6, 90
lmap c [split $a {}] d [split $b {}] {puts [expr {{}eq$d?{A}:{}eq$c?{B}:[continue]}];exit}

If you run Tcl 8.5, use foreach instead lmap.
This shows a nice feature of Tcl's foreach/lmap: It can walk over several lists at once.

Perl, 87 78 - tells which is longer and by how much
alternative:

72 - tells which is longer and by how much, no special message if equal

Perl script expecting 2 strings as command line arguments. Tells which one is longer and by how much. This one I tried to make it readable and not short.
#!/usr/bin/perl
use warnings;
use strict;

my ($x,$y)=@ARGV;
$x=$x=~s/.//g;
$y=$y=~s/.//g;
my @z=($x..$y);
my @w=($y..$x);
if (@z) {
    if ($#z) { print "2nd longer than 1st by $#z" }
    else { print "Equal length" }
}
else {
    print "1st longer than 2nd by $#w"
}

Same code as a one liner, counting 78 characters (output now prints "a3" if a > b by 3 characters, "0" if equal):
perl -E'($x,$y)=@ARGV;$_=s/.//g for$x,$y;@z=$x..$y;@w=$y..$x;say@z?$#z?"b$#z":0:"a$#w"'

Finally, since OP clarified that when they are equal it is not really important what it will print, we can save 6 more characters:
perl -E'($x,$y)=@ARGV;$_=s/.//g for$x,$y;@z=$x..$y;@w=$y..$x;say@z?"b$#z":"a$#w"'

You don't need to count the perl -e (or -E), or the single-quotes around the program, so yes, your score is currently 78.

J 17
Since there is no output specification: the length difference is outputted at the location of the shortest string
    longest =: *&.^/"1@(=&' ')@,:
    'foobar' longest 'abc'
0 3 NB. Means abc is shorter by 3 chars.

Javascript 96 92
x=prompt;i=c=0;for(p=x();c=p[i=-~i];);q=x();for(j=0;c=q[i=~-i,j=-~j];);alert(0<i&&p+i||q+-i)

Note 0<i&& contains no if statement but a logical operator, which is not forbidden.
Input
  asd,asdfg
Output
  asdfg2
Means asdfg is 2 characters longer.

this is a fair loophole, and you program is cute.

Could you explain how this works? c=p[i=-~i] would just be 1 wouldn't it?

@tristin I'm on mobile, but i'll try: ~ is the bitwise NOT operator and flips all bits. 0001 becomes 1110. So ~0 === -1 and - -1 === 1 -> ~1 === -2 and - -2 === 2 and so forth. I hope this was understandable :)

@tryingToGetProgrammingStraight Thanks :)

Ruby, 66 52 (shows only which one is longer)
f=->{gets.gsub(/./,?1)}
a=f[]
b=f[]
puts'sab'[a<=>b]

Prints s for same, a for string a, and b for string b.
Ruby, 184 173 146 143 139 140 (also shows how much longer it is)
f=->{gets.gsub(/./,?1)}
a=f[]
b=f[]
d=->e{Math.log10(e.to_i).floor.next.to_s}
puts(a==b ? ?s:(c=a.sub(b,''))!=a ? ?a+d[c]:?b+d[b.sub(a,'')])

Sample run:
c:\a\ruby>stringcmp
testing123
testing
a3

c:\a\ruby>stringcmp
codegolf.SE
code golf . stack exchange
b15

c:\a\ruby>stringcmp
test
test
s

c:\a\ruby>

second example contains +'s

@lalalalalalalambda For string concatenation, not addition.

OK, I removed mine thinking concatenation would also count as addition, requiring strings to be joined via adding/removing elements to an array... just nit-picking though because mine is so darn long :P I don't think there is any hard n fast rule about it

@Doorknob This + is not string concatenation: Math.log10(e.to_i)+1 (second version, third line). You can use integer's .next or .succ though.

@daniero Whoops, missed that. Fixed (only +1 char)

Bringing up the rear as always with the verbose language. :)
Java - 278
import java.util.*;class b{public static void main(String[]a){Stack z=new Stack(),y=new Stack();for(String q:a[0].split(""))z.push(q);for(String q:a[1].split(""))y.push(q);while(!z.empty()&&!y.empty()){z.pop();y.pop();}System.out.print(y.empty()?"1-"+z.size():"2-"+y.size());}}

With line breaks and tabs
import java.util.*;
class a{
    public static void main(String[]a){
        Stack z=new Stack(),y=new Stack();
        for(String q:a[0].split(""))z.push(q);
        for(String q:a[1].split(""))y.push(q);
        while(!z.empty()&&!y.empty()){
            z.pop();
            y.pop();
        }
        System.out.print(y.empty()?"1-"+z.size():"2-"+y.size());
    }
}

Mathematica 40
f = #~Count~0 & /@ PadLeft[Characters /@ {##}] &

Output is similar to the J version.
Example Usage:
f["looooong", "short"]

{0, 3}

f["short", "thisstringisveryverylong"]

{19, 0}

f["equal", "equal"]

{0, 0}

PHP (44)
-r'list(,$a,$b)=$argv;echo strcmp($a^$a,$b^$b);'

The -r argument and single quotes are not counted in the score.
string-a and string-b are accepted as command-line arguments.
The magnitude of the decimal number printed is the difference in length.
The sign indicates which string is longer. A positive number means string-a is longer. A negative number means string-b is longer. Zero means the strings are the same length.

PHP 5.4 (96)
Here, strcmp is avoided in favor of other string functions that are not so cheap.
-r'list(,$a,$b)=$argv;echo@strtr(explode(${"\3"^$c=trim(($a^=$a).b^($b^=$b).a)},$$c,2)[1],"\0",$c);'

Scoring and input format remain the same.
The difference in length is printed in unary.
The symbol a  is used if string-a is longer; b is used if string-b is longer.
Nothing is printed if the strings are the same length (except in the commented version, which omits the error suppression operator @ and thus may report PHP notices and warnings).

Commented code:
<?php

list(, $a, $b) = $argv;

// Replace all bytes in both $a and $b with null bytes
// (Anything XORed with itself is zero.)
$a ^= $a;
$b ^= $b;

// PHP's bitwise XOR truncates its output to the shorter string's length,
// so only the marker ('a' or 'b') appended to the shorter string will
// remain after the null bytes in common are trimmed off. If $a is shorter,
// 'b' remains; likewise, if $b is shorter, 'a' remains.
$longer = trim($a . 'b' ^ $b . 'a'); // $c in the golfed code

// Flip bits 0 and 1 to switch 'a' to 'b' (or 'b' to 'a')
// ('a' === chr(0b1100001); 'b' === chr(0b1100010); "\3" === chr(0b11))
$shorter = "\3" ^ $longer;

// Remove the shorter string from the longer string
// $$shorter refers to $a if $shorter === 'a' or $b if $shorter === 'b'.
// $$longer works the same way.
$difference = explode($$shorter, $$longer, 2)[1];

echo strtr($difference, "\0", $longer);

JavaScript (prompt for input) - 128
I golfed it 2 more characters.
p=prompt,f=alert,i='lastIndexOf'
a=p().replace(/./g,'.')
b=p().replace(/./g,'.')
j=a[i](b),k=b[i](a)
~j&&f('a '+j)
~k&&f('b '+k)

"this program has to take two strings"

You supply two strings a and b to a function F. Do you want command line style?

its not a stand-alone program, it doesnt matter how you get the strings, prompting or inputs or whatever is fine, it just has to be stand-alone.

Python - 291 261 244 223 220 210 206
I got 206
import sys,itertools
q=sys.argv
h=[]
i=0
for k,g in itertools.groupby(map(lambda f,b:2 if f is None else 1 if b is None else 0,q[1],q[2])):h.append(list(g))
for i,a in enumerate(h[1],1):0
print q[h[1][0]],i

Sample Run
C:\pjs\codegolf>python last.py bananas apples
bananas 1
C:\pjs\codegolf>python last.py bananas hazlenuts
hazlenuts 2

Lots of room for golfing still. e.g. single-line blocks can go immediately after the colon on the previous line, like this: "if u:print [sys.argv[1],str(u)]". You can omit all of the indentation whitespace this way.

thanks @breadbox, I pinched this for mine, too. was trying break if e to no avail, so if e:break saved me another 12 :)

You can replace pass with 0 (or any other 1-character-Expression). Also, space after , and space before [ is unnecessary. (On the other hand, you don't even need the brackets in the print statements.) Oh, and the calls to list should be unnecessary (untested). I'll stop now :-)

@WolframH I changed a little, but thank you about replace pass by 0

well done Doug and thanks to @WolframH, this CG thing is really educational!

Bending the rules some...
JavaScript (92)
p=prompt
~function f(a,b) {
   a && !b && alert(0)
  !a &&  b && alert(1)

  f(a.slice(1), b.slice(1))
}(p(),p())

(Minified: p=prompt;~function f(a,b){a&&!b&&alert(0);!a&&b&&alert(1);f(a.slice(1),b.slice(1))}(p(),p()))
Takes two strings via prompts.  Alerts the difference in unary (as with Hasturkun's solution), using 0s if the first string is longer and 1s if the second string is longer.  Outputs each digit in a separate alert (ow), and terminates eventually when the call stack runs out (owww).
If we ignore the rule about no addition or subtraction, we could easily have the number be a nice (base 10) number whose sign denotes which string is longer:
p=prompt
alert(function f(a,b,n) {
  return a || b? f(a.slice(1), b.slice(1), n - !a + !b)
       :         n
}(p(),p(),0))

This version doesn't even wait for the call-stack to overflow!

Perl, 69 characters
sub l{l(map{substr$_,1}@_)if$_[0]&&$_[1];say pop()?2:1;die}l(<>,<>)

The gist is, recurse until one string is empty, then print the other. Run with perl -e CODE 2> /dev/null

Python 3: 125 91 90
Finally beat the JavaScript solutions :)
Prints both which is longer, and by how much.
Current (90 and Python 3):
I=input
q=a,b=I(),I()
while a+b:s=q[b!=""];a=a[1:];b=b[1:];i=a and b and-1or-~i
print(s,i)

Example output:
rees@Rees-Ubuntu:~/Python/CodeGolf$ python3 StringComparer.py
hi <- input one
hello <- input two
hello 3 <- output

Old (125 and Python 2):
r=raw_input
q=a,b=r(),r()
while a and b:a=a[1:];b=b[1:]
s=(q[0],q[1])[a==""]
i=0
while a or b:a=a[1:];b=b[1:];i=-~i
print s,i

Python, 708, 570, 566, 462, 492, 481, 480, 475, 363, 357, 354, 346, 343, 341, 340, 327, 315 (with whitespace)
My first CG, be gentle:
import sys
c=[1,2]
a=o=[]
l=d=e=v=0
s=sys.argv
r=range(0,99)
a=[zip(list(s[x]),r[1:]) for x in c]
a.insert(0,0)
for x in c:
    for p in a[x]:
        try:
            v=a[x==2 and 1 or 2][p[1]]
        except:
            l=s[x]
            o.append(1)
            e=1
    if e:break
o=zip(o,r)
print[l,o.pop()[1]]

Sample run:
me@home:~$ python diff.py bananas apples
['bananas', 1]
me@home:~$ python diff.py bananas hazlenuts
['hazlenuts', 2]

C, 230 200 193 characters
EDIT: Shortened it from 230 to 193 characters.
My first golf attempt. Maybe not a hole-in-one, but it works. Not being allowed to use strlen for this forces it to be fairly verbose in C. Maybe it can be shortened a bit?
a,b,w,i,l;
int main(int c,char **v){
    for(;a<256||b<256;i++){
        if(!v[1][i])a|=256;
        if(!v[2][i])b|=256;
        if(!(a&256))a++;
        if(!(b&256))b++;
    }
    a&=255;b&=255;
    w=a>b?0:1;
    l=w?b-a:a-b;
    printf("%s %i\n",v[w+1],l);
}

Or the uglier version:
a,b,w,i,l;int main(int c,char **v){for(;a<256||b<256;i++){if(!v[1][i])a|=256;if(!v[2][i])b|=256;if(!(a&256))a++;if(!(b&256))b++;}a&=255;b&=255;w=a>b?0:1;l=w?b-a:a-b;printf("%s %i\n",v[w+1],l);}

Example output:
N:\>golf.exe everything works
everything 5

it has to tell you how much it is longer by not how long the longer one is.

Some tips: int in variable declarations is optional. No need for parentheses around a<256. if(!x)y -> x||y. i is initialized by default.

Whoops, it outputs the difference now instead. Thanks for the tips ugoren. I knew "i" was initialized too, but I'm just so used to trying to write clear code! Like I said, my first golf. :)

Powershell 140
(assumes a max difference of 999)
$c=@(compare($args[0]-split'.')($args[1]-split'.'))
$n=[collections.stack]@(999..1)
$c|%{$n.pop()}
if($c){$args[$c[0].sideindicator-eq'=>']}

Outputs nothing if the string lengths are equal. If the string lengths are not equal, the longer string is displayed; the last number is the difference.

C (gcc), 89 bytes
i;c;q;j;f(a,b)char*a,*b;{for(i=j=c=0;a[i]||b[j];a[i]&&++i,b[j]&&++j)a[i]&&b[j]?:++c;a=c;}

Try it online! I think this has room for improvement, but I'm not sure where. Abuses undefined behaviour, but it it Works On TIO™. Simply starts increment c when one of a[i] or b[j] is the null byte (the end of the string); i and j are incremented until they hit this null byte.

87 bytes

Clojure - 206
(defn is-longer [first second first-left second-left]
  (defn remaining [current count]
    (if (empty? current)
      (/ (Math/log count) (Math/log 2))
      (remaining (rest current) (bit-shift-left count 1))))
  (cond
   (empty? first-left) [2 (remaining second-left 1)]
   (empty? second-left) [1 (remaining first-left 1)]
   :else (is-longer first second (rest first-left) (rest second-left))))

Or minified:
(defn y [a b al bl] (defn x [u t] (if (empty? u) (/ (Math/log t) (Math/log 2)) (x (rest u) (bit-shift-left t 1)))) (cond (empty? al) [2 (x bl 1)] (empty? bl) [1 (x al 1)] :else (y a b (rest al) (rest bl))))

Or in prettierific:
Returns:
  [1|2 count]
Getting around not using + was a fun challenge.

Python, 194

import sys,itertools as T
A=sys.argv
B=[]
N,i=None,0
for k,g in T.groupby(map(lambda f,b:[[0,1][b is N],2][f is N],A[1],A[2])):B.append(list(g))
for i,j in enumerate(B[1],1):0
print A[B[1][0]],i

R - 120/114
Shows difference:
a=strsplit(scan(what='c'),"")
c=0
for(i in 1:2){for(y in a[[i]]){if(i-1)c=c+1 else c=c-1}}
d=abs(c)
cat(a[[(c==d)+1]],d)

Shows just the longer:
a=strsplit(scan(what='c'),"")
c=0
for(i in 1:2){for(y in a[[i]]){if(i-1)c=c+1 else c=c-1}}
cat(a[[(c==abs(c))+1]])

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


text:
Simulate the Monty Hall Problem
I've never been able to wrap my head around the Monty Hall problem. Here's the premise:

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Run 10,000 simulations. Output the win percentage of switching. For example:
> 66.66733%

The host knows where the car is, so he never opens a door with the car behind it

As the challenge stands, it's hard to argue that it's not perfectly legal to just have 10,000 runs of the random-number generator and adds up which ones land below 0.6666. You might say that it's not really simulating the Monty Hall problem. But if it produces the exact same output, then what's really missing?

An interesting historical perspective (on the problem, not the golfing): Which Door Has the Cadillac?.

The challenge is still a little ambiguous with regards to what assumptions we're allowed to make. For example, some of the answers are probably saving a significant amount of code by assuming the car will be behind the same door every time or the player picks the same door every time.

I took first trying 50 cycles each way in real life and then getting him to code such a simulation himself to convince a friend that switching is the right thing to do.

@dmckee I started coding a simulation of it way back in grade 11 when I learned Visual Basic. I was trying to convince my dad about this problem, and as programming it I started optimizing pieces of code you REALLY start to realise that this is in fact true. Coding this yourself is the best way to convince yourself of this problem.

Also, you can never get a result of 66.66733% with exactly 10,000 simulations. :P

Enumerating all the possibilities is at least as illuminating as generating them randomly...

I had trouble with the Monty Hall problem. The point is indeed that Monty Hall only selects doors which do not hide a car. I got the reasoning once I made the same reasoning with 100 doors, 1 car. You choose a door. 1% of the cases you’re right, 99% wrong. If you’re wrong (99%), then Monty opens the 98 doors, the 99 always hide the car; switching is always right. If you’re right (1%), Monty opens 98 doors at random. Not switching is always right. So, in 99% of the cases, switching is right; in 1% not switching is right. You should probably switch.

JavaScript 52
for(i=s=0;i++<1e4;)s+=Math.random()<2/3;alert(s/100)

Doors are 1:[0,1/3), 2:[1/3,2/3), 3:[2/3, 1)
Assume the prize is always in door 3. If the guest picks doors 1 or 2, which is range [0,2/3), and they switch, they've won the prize.

Looks like CoffeeScript allows us to shave off a single character: i=s=0;s+=Math.random()<2/3while i++<1e4;alert s/100

J: 17 15
100%~+/2>?1e4$3

It picks a random door—let's label these 0, 1, or 2 where 2 is the door with the car—and computes the benefit of switching based on this logic:

If the player picked door 0, the host will open door 1. Switching will earn the player a new car (1).
If the player picked door 1, the host will open door 0. Switching will earn the player a new car (1).
If the player picked door 2, the winning door, the host will open either door 0 or door 1. Either way, if the player switches, he or she will find a goat (0).

It then computes the result as the sum of the previous array, divided by 100.
I'm pretty shaky with J so I'm sure this could be improved further.

R 115 100
The pseudo-simulation answer is 23 characters long:
sum(runif(1e4)>1/3)/100

but here is an actual simulation:
D=1:3
S=function(x)x[sample(length(x),1)]
sum(replicate(1e4,{
C=S(D)
P=S(D)
H=S(D[-c(C,P)])
F=D[-c(P,H)]
C==F
}))/100

D are the possible doors
S is a function to randomly select one item from a vector
C is the the door with the car (random among D)
P is the the door picked by the player (random among D)
H is the door picked by the host (random among D minus C and P)
F is the final door picked by the player (deterministic: D minus P and H)
success is measured by C==F.

returns: [1] 66.731
Edit
I can save a few characters by not assigning to variables and assuming without loss of generality that C==1:
D=1:3;S=function(x)x[sample(length(x),1)];sum(replicate(1e4,{P=S(D);1==D[-c(P,S(D[-c(1,P)]))]}))/100

Perl, 98 89 83 75 72 71 characters
Here's a serious answer that actually runs the simulation:
sub c{($==rand 2)-"@_"?$=:&c}$n+=$%==c c($%=rand 3)for 1..1e4;say$n/100

In each loop iteration, the player's initial choice is always door #2. First  the door with the car is stored in $%, then a different door is selected for Monty Hall to expose. If the remaining door is equal to $%, the round is won.
(Perl puncutation variables $% and $= are used because they do integer truncation for free.)

Powershell - 168 131 125 115
Golfed code:
nal g Random;1..1e4|%{$C=g 3;$P=g 3;$T+=$C-eq(0..2|?{$_-ne$P-and$_-ne(0..2|?{$_-ne$P-and$_-ne$C}|g)})};"$($T/100)%"

Changes from Original:
  Trimmed 53 characters off the original script with some modifications.

Removed spaces and parenthesis where PowerShell is forgiving of it.
Used a ForEach-Object loop, via the % alias, instead of while.
Used number ranges (e.g.: 0..2) instead of explicitly defined arrays.
Removed write from the last command - turns out I don't need it after all.
Flipped the expression for the host's choice around to use the shorter pipelining syntax.
Replaced 10000 with 1e4.
Took Joey's suggestion and omitted Get- from Get-Random. (Note: This modification significantly bloats the run time. On my system it jumped from about 20 seconds to nearly a half-hour per run!)
Used Rynant's trick of doing $T+=... instead of if(...){$T++}.

Some notes:
This script is intended to be as concise as possible, while also being as thorough a simulation of the Monty Hall scenario as possible. It makes no assumptions as to where the car will be, or which door the player will choose first. Assumptions are not even made for which specific door the host will choose in any given scenario. The only remaining assumptions are those which are actually stated in the Monty Hall problem:

The host will choose a door that the player did not pick first, which does not contain the car.

If the player picked the door with the car first, that means there are two possible choices for the host.

The player's final choice will be neither his initial choice nor the host's choice.

Ungolfed, with comments:
# Setup a single-character alias for Random, to save characters later.
# Note: Script will run a lot (about 500 times) faster if you use Get-Random here.
# Seriously, as it currently is, this script will take about a half-hour or more to run.
# With Get-Random, it'll take less than a minute.
nal g Random;

# Run a Monty Hall simulation for each number from 1 to 10,000 (1e4).
1..1e4|%{

    # Set car location ($C) and player's first pick ($P) to random picks from a pool of 3.
    # Used in this way, Random chooses from 0..2.
    $C=g 3;$P=g 3;

    # Increment win total ($T) if the car is behind the door the player finally chooses.
    # (Player's final choice represented by nested script.)
    $T+=$C-eq(

        # Filter the doors (0..2) to determine player's final choice.
        0..2|?{

            # Player's final choice will be neither their original choice, nor the host's pick.
            # (Host's pick represented by nested script.)
            $_-ne$P-and$_-ne(

                # Filter the doors to determine host's pick.
                0..2|?{

                    # Host picks from door(s) which do not contain the car and were not originally picked by the player.
                    $_-ne$P-and$_-ne$C

                # Send filtered doors to Random for host's pick.
                }|g
            )
        }
    )
};

# After all simulations are complete, output overall win percentage.
"$($T/100)%"

# Variable & alias cleanup. Not included in golfed script.
rv C,P,T;ri alias:g

I've run this script several times and it consistently outputs results very near to two-thirds probability. Some samples:
(As above)

67.02%

(Using Get-Random as the alias definition, instead of just Random)

66.92%
67.71%
66.6%
66.88%
66.68%
66.16%
66.96%
66.7%
65.96%
66.87%

Ruby 48 40 38
My code doesn't make any assumptions about which door the prize will always be behind or which door the player will always open.  Instead, I focused on what causes the player to lose.  As per the Wikipedia article:

[...] 2/3 of the time, the initial choice of the player is a door hiding a goat. When that is the case, the host is forced to open the other goat door [...] "Switching" only fails to give the car when the player picks the "right" door (the door hiding the car) to begin with.

So to simulate this (instead of using fixed values), I modeled it as so:

the show randomly picks 1 of the 3 doors to hide the prize behind
the player then randomly picks 1 of the 3 doors as his first choice
the player always switches, so if his first choice was the same as the show's choice, he loses

The code v1:
w=0;10000.times{w+=rand(3)==rand(3)?0:1};p w/1e2

The code v3 (thanks to steenslag and Iszi!):
p (1..1e4).count{rand(3)!=rand(3)}/1e2

Some sample return values:

66.44
66.98
66.33
67.2
65.7

p (1..10000).count{rand(3)!=rand(3)}/1e2 saves some chars.

@steenslag Ah, indeed it does!  Thank you! =)

Does Ruby not allow shortcutting powers of 10? E.g: 1e4 for 10000?

@Iszi It does, but scientific notation yields a float, so it can't always be substituted.  However, it is a viable substitution in v2, saving 2 more chars!

Mathematica 42
Count[RandomReal[1,10^4],x_/;x>1/3]/100// N

66.79

Python 2: 72 66 64
from random import*
i=10000
exec"i-=randint(0,2)&1;"*i
print.01*i

Example output: 66.49

You can save a few characters by using exec"i-=randint(0,2)&1;"*i instead of the for loop.

@WolframH Thanks, I'll update it now.

Also, use print.01*i instead of print i/100..

Nice solution but you're missing a semicolon.

Very true. Updating now...

PowerShell, 90
$i=0
1..10000|%{$g=random 3;$n=0..2-ne$g;$g=($n,2)[!!($n-eq2)]|random;$i+=$g-eq2}
$i/10000

Commented:
# Winning door is always #2

$i=0

# Run simulation 1,000 times
1..10000|%{

# Guess a random door
$g=random 3

# Get the doors Not guessed
$n=0..2-ne$g

# Of the doors not guessed, if either is the
# winning door, switch to that door.
# Else, switch to a random door.
$g=($n,2)[!!($n-eq2)]|random

# Increment $i if
$i+=$g-eq2}

# Result
$i/10000

This does not output a winning percentage in the format specified in the question. Also, save a couple characters by using 1e4 instead of 10000.

C, 101 95
float c,s,t,i;main(){for(;i<1e5;i++,c=rand()%3,s=rand()%3)i>5e4&c!=s?t++:t;printf("%f",t/5e4);}

That's for the actual simulation. For some cheaty rule-bending code, it's only 71 65 59:
p,i;main(){for(;i<1e5;rand()%5>1?i++:p++)printf("%f",p/1e5);}

I didn't do srand() because the rules didn't say I had to. Also, the cheaty version prints out about 30,000 extra numbers because it saves a character. I'm probably missing quite a few tricks, but I did the best I could.

Global variables are guaranteed to be zero on startup. Move your variable declarations out of main and you can drop the =0 initializations.

PHP 140
But i think that this is not working right. Any tip?
I'm getting values from 49 to 50.
$v=0;//victorys
for($i=0;$i<1e4;$i++){
    //while the selection of the host ($r) equals the player selection or the car
    //h=removed by host, p=player, c=car
    while(in_array($h=rand(1,3),[$p=rand(1,3),$c=rand(1,3)])){}
    ($p!=$c)?$v+=1:0; //if the player changes the selection
}
echo ($v/1e4)*100;

"If the player changes the selection"?

Sorry my English is not good. I mean, first i do a While trying to get aceptable values. Because the "host" can't remove a door containing the car OR the door that you choose. Then i have $p (players choice) and $c (where the car is). The OP said that you must take the percentage of winning when you switch, so i only count the result as a "victory" when $p!=$c (you switch your choice to the other door and you win).

Game Maker Language, 19 (51 w/ loop)
show_message(200/3)

It outputs 66.67! This is the correct probability ;)

The serious-mode code, 51 characters:
repeat(10000)p+=(random(1)<2/3);show_message(p/100)

Make sure to compile with treat all uninitialized variables as 0.

The oldest code, 59 characters:
for(i=0;i<10000;i+=1)p+=(random(1)<2/3);show_message(p/100)

Again, make sure to compile with treat all uninitialized variables as 0.
The output was 66.23

Fish - 46 43
This is using the same assumptions that Tristin made:
aa*v>1-:?v$aa*,n;
v*a<$v+1$x! <
>a*0^<  $<

The down direction on x represents you initially picking the correct door, left and right are the cases that you picked a different door, and up is nothing, and will roll again.
Originally, I initialized 10000 with "dd"*, but "dd" had to all be on the same line, and I wasted some whitespace. By snaking aa*a*a* I was able to remove a column, and ultimately 3 characters. There's a little bit of whitespace left that I haven't been able to get rid of, I think this is pretty good though!


text:
math with bitwise operators
objective
write a program that can perform addition, subtraction, multiplication, and division, using only bit-wise operators, by bit-wise operators i mean the equivalent of JavaScript &, |, ^, ~, << ,>> ,>>>. (AND, OR, XOR, NOT, and SHIFTs)
rules

you can use other operators, just not for the actual operation/output. (i.e. loop-indentation is ok).
it need not actually take input, just be technically functional. (i.e. functions that take arguments).
any output is OK, you can even return a object with the sum, difference, etc.
you need not return floats for division ints are ok as well, you can round anyway you like.
as short as you can.

It's really unclear what the program is supposed to look like. Are you asking for a library of four functions that can take and return arbitrary ints (barring division by zero)?

@breadbox its up to you, if you can make one function (i dont think this is practical) then knock yourself out. it has to be able to perform simple arithmetic on 32-bit integers. i hope my edit clarifies it a bit.

Do the function headers count against us, or only the function bodies?

@JanDvorak i think they should count against, just like variables and their declarations.

Lambda expression ftw. Too bad if your language don't have them.

@JohannesKuhn i dont see how that has anything to do with this challenge.

function a(x,y) {return x+y} vs a=(x,y)=>x+y

@JohannesKuhn i dont see any x+y....

lambda expressions are shorter, so they are better for [tag:code-golf]

JavaScript, 124 119
a=(x,y)=>y?a(x^y,(x&y)<<1):x
s=(x,y)=>a(x,a(1,~y))
m=(x,y)=>x?a(y,m(s(x,1),y)):0
d=(x,y)=>(x=s(x,y))>>31?0:a(1,d(x,y))

Addition and Subtraction work for any signed numbers, multiplication and division only for unsigned (this hasn't been specified).
The input is assumed to be 32 bit.
I've been very strict and not even used comparison operators, except testing for equality with zero. It could probably be written a bit shorter otherwise.

javascript... 1.6?

@JanDvorak … whatever works in Firefox

@tryingToGetProgrammingStraight Here's a testcase: http://jsfiddle.net/MM66r/

+1 i like the way its all built on a

A quick one character win: ~a(-1,y) is equivalent to a(1,~y).

I definitely have to take some time reading through your answers  here. I'm pretty sure i can learn a whole lot of it!

@C5H8NNaO4 code golf is awesome!!!

@JanDvorak ECMAScript 6 in fact. The `=>' notation is arrow function syntax.

You can save four bytes on your addition function, simply by letting it go one more iteration: a=(x,y)=>y?a(x^y,(x&y)<<1):x

@primo Oh, right. Nice catch.

C, 313 characters
s(a,b){return a&b?s(a^b,(a&b)<<1):a^b;}
d(a,b){return s(s(a,~b),1);}
P(a,b,c){return b?P(a<<1,b>>1,b&1?s(c,a):c):c;}
p(a,b){return b<0?d(0,P(a,d(0,b),0)):P(a,b,0);}
q(a,b,c,z){long v=b=(z=b<0)?d(0,b):b,w=1;for(a=a<0?z^=1,d(0,a):a;a>=v;v<<=1)w<<=1;
for(c=0;b<=a;v<=a?a=d(a,v),c=s(c,w):0)v>>=1,w>>=1;return z?s(~c,1):c;}

The four functions are s = sum, d = difference, p = product, and q = quotient. P is an internal helper function used by p, and is not part of the API. (Note that despite q's definition, it should be invoked with only two parameters.)
Please note that p and q do not work by iterative addition/subtraction, but actually do the bitwise computation. (Otherwise q could be significantly shorter.) Thus their running time is a respectable O(log N).
All four functions accept the full range of positive and negative integers as inputs. Dividing by zero will produce an infinite loop, since there's no portable way to raise the appropriate exception.
Special note for C standards lawyers: The code assumes that sizeof(long) is strictly greater than sizeof(int), which is true more often these days than it used to be. If longs and ints are the same size, however, and the implementation sign-extends on right-shift (as most do), then q's valid input range is decreased such that the absolute value of the second argument cannot have its highest (non-sign) bit set. (Since dividing by such values can only be equal to zero or one, this isn't too much of a restriction in practice.)


text:
Build a solver for the monks and buns problem
An old Chinese poem goes:

一百饅頭一百僧，
  大僧三個更無爭，
  小僧三人分一個，
  大小和尚得幾丁？

When translated into English, this math problem reads:

100 buns and 100 monks,
  Big monks eat 3 buns with no shortage,
  Little monks share one bun among three,
  Big and little monks, how many are there?

Once again, like in the cow and chicken problem, there is no simple calculation you can perform. You need the power of systems of equations.
Your task is to build a program that takes the following inputs, all positive integers:

b, the number of buns.
m, the number of monks.
bl, the number of buns a big monk can eat.
ms, the number of small monks who share one bun.

and output l and s, the number of big monks and small monks respectively. ("L" stands for "large").
Again, this problem has various states of solvability, but this time around, only output something if there is a unique solution in the nonnegative integers.
The shortest code to do all of the above in any language wins.

The problem input of the poem is 100 100 3 3, and the solution is 25 75.

This is just Build a solver for the cow and chicken problem with two inputs constrained to 1.

And one of the inputs turned into a reciprocal, I suppose.

R: 81 characters
i=scan();p=combn(0:i[2],2);cat(p[,p[1,]+p[2,]==i[2]&i[3]*p[1,]+p[2,]/i[4]==i[1]])

A brute force solver which takes all possible combinations of non-negative integers and subset the one corresponding to criteria.

F#: 125 characters
printf"%O"(Console.ReadLine().Split()|>Seq.map Int32.Parse|>Seq.toArray|>fun[|b;m;x;y|]->((m-b*y)/(1-x*y),m-(m-b*y)/(1-x*y)))

This is my first attempt at code golf (here anyway), so I'm sure this could be improved. It simply reads the input, parses it, then does a little number crunching to get the correct results.
The result will be formatted like this:
(25, 75)


text:
Build the blancmange function
The blancmange function is used as an example in basic calculus of a function that is continuous everywhere, but differentiable nowhere. It achieves this effect by using  the sums of ever-diminishing triangle-wave functions.
Your task is to build a program that takes a binary fractional number in the interval [0, 1] and returns the exact height of the blancmange curve at that position. Both fractions can be represented using the notation of your choice, but if you are using a nonstandard one (e.g. not IEEE floating-point or an integer with a fixed radix point), you must explain it in your solution, and your notation must support an accuracy of at least 2-52.

wait... 'exact', or 'accuracy of at least 2^-52'?

The function must take inputs with accuracy up to 2^-52 (and round them to a binary fraction), but must return the exact output for the rounded input (binary fractions have exact representations in blancmange).

I don't get what you mean by binary fraction. Is 3/5 a binary fraction? Or it is when I write it 11/101? Or denominator must be a power of 2? Or what?

Ruby, 53 characters
f=->x{x>0?f[2*x=x<0.5?x:1-x]/2+x: 0}
$><<f[gets.to_f]

expanded:
f = lambda do |x|
  if i>0
    x = 1 - x unless x < 0.5
    return x + f[2*x] / 2
  else
    return 0
  end
end

print f[gets.to_f]

The input is a decimal value, assumed to be in the range 0..1 . The output is a decimal value. The platform native double precision numeric type is used, and is assumed to be at least 53 bits of mantissa. Since every floating point value in a binary fraction, this algorithm will always terminate after at most 53 (with the default precision) steps.

Save one char: f=->x{x>0?f[2*x=x<0.5?x:1-x]/2+x: 0}

Mathematica 92 chars
This uses exact arithmetic (fractions).
b@n_:=FoldList[#+{1,#2}/2^n&,{0,0},
Total/@ (2 Reverse[IntegerDigits[#,2,n]&/@Range[0,2^n-1]]-1)]

{{{0, 0}, {1/2, 1/2}, {1, 0}}, {{0, 0}, {1/4, 1/2}, {1/2, 1/2}, {3/4,
     1/2}, {1, 0}}, {{0, 0}, {1/8, 3/8}, {1/4, 1/2}, {3/8, 5/8}, {1/2,
     1/2}, {5/8, 5/8}, {3/4, 1/2}, {7/8, 3/8}, {1, 0}}, {{0, 0}, {1/16,
     1/4}, {1/8, 3/8}, {3/16, 1/2}, {1/4, 1/2}, {5/16, 5/8}, {3/8, 5/
     8}, {7/16, 5/8}, {1/2, 1/2}, {9/16, 5/8}, {5/8, 5/8}, {11/16, 5/
     8}, {3/4, 1/2}, {13/16, 1/2}, {7/8, 3/8}, {15/16, 1/4}, {1, 0}}}

Source: Borut Levart [http : // demonstrations.wolfram.com/TakagiCurve/ ]

Mathcad, 73 "bytes"
The Mathcad worksheet shown here defines the triangle function s(x) and the blancmange function (blanc(x) - but deemed to be just b(x) for golfing purposes).  It also presents two variants, one specialized for rational numbers with power of two divisors, and one specialized for number of iterations of the summation.   The worksheet also presents plots of the various blancmange functions and tables of their results.
The blancmange function works in both numeric (IEEE floating point) and symbolic (arbitrary arithmetic) modes.

Mathcad uses a virtual 2D worksheet on which the user places text or executable expressions (eg, formula or programs).   Mathcad saves its worksheets in an XML format, which means that even a small program can be many hundreds or thousands of text characters long.  For the purposes of code golfing, I take a Mathcad "byte" to mean the number of distinct symbols that the user must enter to create a program.
For example, to evaluate an expression, the user types "="; Mathcad will place an evaluation operator on the worksheet, which gives the appearance of an "=" sign bounded by two black box symbols (known as placeholders).  Writing an expression in the left hand placeholder will cause Mathcad to evaluate the expression and put the result in the right hand placeholder.   If the expression is a simple variable, "a" say, that contains a value, then from an user perspective this would count as 2 byte program "a" and "=".  Raising one number to the power of another comprises entering the exponent operator (^) and then entering the two numbers in the appropriate placeholders. So, 3^4 would be a 3 byte program.

Not sure if this counts, but this Pari GP implementation works for any x. 53 bytes
s(x)=abs(x-round(x));
bm(x)=sum(i=0,50,s(2^i*x)/2^i);

You should include a byte count with your answer.

The bytecount is the number of characters?

For this answer yes

JavaScript (ES6), 35 bytes
B=x=>x%1?B(2*x%1)/2+(x<1/2?x:1-x):0

A straightforward implementation of this recursive formula.


text:
Unholy Grail Layout (Reverse Holy Grail Layout)
The Holy Grail Layout in CSS, is a full height, 3 column layout which consists of a fluid central column, and two side columns with fixed widths.
Your Task is Simple!
Reverse it, make a fixed width central column, and two fluid width columns to the sides. The point is for them to take All available space both vertically and horizontally. So if one adds elements above, or elements below (assume 100% width), your solution should shrink to accommodate. Same goes with elements on the sides. Your layout should fill 100% of its container's space.
Restrictions

HTML and CSS only (no JavaScript)
IE8+ support mandatory
Must work in all major browsers (it is, after all, a layout!)
HTML and CSS must both be valid.
No tables, it's supposed to be a layout, not an abomination.

Winner

Code with fewest characters wins, excess spaces and newlines do not count, don't be afraid to be readable! (I'm running the solution through a minifier)

Good luck!

The specification is a bit vague, but on the assumption that it can be tightened up, how would you pick a winner between two solutions? All questions on this site should have an objective primary winning criterion.

Well, with the lack of a better criterion, I'd say it would be shortest code possible. I'll edit it as soon as I get to a PC.

How about providing a list of browsers to support, then score by the following?  [code size] / [number of actually supported browsers]

I think the current attempt at an answer validates my comment that the specification is a bit vague. Can you give a precise definition of what counts as a "column"?

@PeterTaylor As always: Proof by example. I don't know yet if this is counter productive or not.

I will update the criteria when I get to a PC later today.

Edited to make clear (tell me if you still need more information). Sorry for those whose solutions were invalidated. (My first puzzle on this site :D)

Simple

L

R

C

Who said that it needs to be valid html?
Who said that I need a doctype?

display:table-cell is compatible ie8+ (as seen in caniuse)
<!DOCTYPE html>

  <title>a</title>

a
z
e

This is html/css valid, tried here : https://validator.w3.org/nu/#textarea
That's why there is head/title stuff.
But you can ommit html/body, according to the specs.
The issue I see is when you want to put something above/below, you have to make them display: table-row, and probably specify a height.

Why the downvotes ? Based on (not so clear) requirements, this answer is quite acceptable

Guaranteed to work in all browsers - old and new:

    a
    b
    c

CSS:
table, tr{
    width: 100%;
}
.f{
    width:100px;
}

Here's a fiddle: http://jsfiddle.net/8QWBX/1/
Note: if you want to make it shorter (but fail HTML standards) you may remove the tr tag and its styling. This will save 12 characters the way I see it.

Table for layout? I feel ill.


text:
Build an evaluator for nontrivial resistance diagrams
There is already a problem on here about calculating the total resistance of a resistor diagram. However, that problem deals only with series-parallel diagrams, which are trivially reducible. Here I present the question that includes nontrivial bridges and the like, and uses a slightly more convenient representation.
Your task is to build a program that, given a graph where each edge has a value representing the resistance of a resistor between the vertices of that edge, will calculate the resistance between two specified vertices.
Your program will take input in two parts:

The resistor graph. This can be in one of two forms, depending on which one is more convenient:

An N-by-N adjacency matrix, where N is the number of points in the resistor graph. The mth entry of the nth row is the resistance of the resistor between points m and n, in ohms. (The mth entry of the nth row and the nth entry of the mth row will always be equal.) The way this adjacency matrix is represented in data is your choice.
A number N, denoting the number of vertices in the graph, followed by a list of entries, each entry containing three numbers: p1, p2, and r, which are the numbers of the two points and the resistance of the resistor placed between those points. There will never be more than one resistor connecting two points. Again, the way this list is represented in data is your choice.

Two numbers v1 and v2, representing the vertices between which the resistance is to be calculated.

All resistors will have a resistance of a positive integer of ohms. A value of 0 will refer to a resistor-less wire (i.e. zero resistance), and a value of -1 or infinity (you can choose which one to accept) will refer to the absence of a wire (i.e. infinite resistance).
Your program will return R, the resistance between v1 and v2 in ohms, as a floating-point number (to at least four significant digits). If the resistance is infinite, return either -1 or your language's representation of infinity.
Your solution must not make use of any libraries that are specifically built for solving linear equations or calculating the resistance of a resistor diagram.
Since any winning criteria I could come up with will take too long to judge properly (except for "first submitted code that actually works", but that one is unacceptable for obvious reasons), this will also be code golf. The shortest code in any language that can do the above will win. However, if you have an idea for a different winning criterion, I would be glad to hear it.

Example inputs
1. Series diagram
The following matrix:
-1  2 -1 -1
 2 -1  3 -1
-1  3 -1  4
-1 -1  4 -1

is a diagram representing resistors of 2 ohms, 3 ohms, and 4 ohms, put in series in that order. An input of 1 3 as the vertices would return 5.0, and an input of 1 4 would return 9.0.
2. Parallel diagram
The following matrix:
-1  0  0  0 -1
 0 -1 -1 -1  2
 0 -1 -1 -1  3
 0 -1 -1 -1  4
-1  2  3  4 -1

is a diagram representing resistors of 2 ohms, 3 ohms, and 4 ohms, put in parallel in that order. An input of 1 5 as the vertices would return 0.9230769230769231.
3. Infinite-resistance diagram
The following matrix:
-1  2 -1 -1
 2 -1 -1 -1
-1 -1 -1  4
-1 -1  4 -1

is a diagram representing two disconnected graphs of resistors. The input 1 2 would return 2.0, but the input 1 4 would return -1 or infinity, as there is no path between the vertices.
4. Zero-resistance diagram
The following matrix:
-1  0  0  0 -1
 0 -1 -1 -1  2
 0 -1 -1 -1  0
 0 -1 -1 -1  4
-1  2  0  4 -1

is a diagram representing resistors of 2 ohms and 4 ohms, and a plain wire, put in parallel. An input of 1 5 as the vertices would return 0.0, as there is a wire with zero resistance running from point 1 to point 5 via point 3.
5. Bridge
The following matrix:
-1  2  1 -1
 2 -1  3  5
 1  3 -1  4
-1  5  4 -1

represents the smallest diagram of resistors that cannot be represented as a series-parallel diagram for a specific set of points, namely 1 and 4. An input of 1 4 has a result of 2.9.
6. Cube
The following matrix:
-1  1  1 -1  1 -1 -1 -1
 1 -1 -1  1 -1  1 -1 -1
 1 -1 -1  1 -1 -1  1 -1
-1  1  1 -1 -1 -1 -1  1
 1 -1 -1 -1 -1  1  1 -1
-1  1 -1 -1  1 -1 -1  1
-1 -1  1 -1  1 -1 -1  1
-1 -1 -1  1 -1  1  1 -1

is a diagram representing a cube of one-ohm resistors. According to Wikipedia, the input 1 8 will return 0.8333333333333333.

Can we require actual infinities in the input matrix rather than negative ones?

If you can do that, yes.

J, 50 characters
(3 :'0 a}1 b}y+1e_5*c=:+/(-/~y)%r+1e_4')^:_[0
%a{c

Assumes the input is already stored in a set of global variables as:

r is a 2D matrix of single-precision numbers
a, b are 0-based indices of the two nodes

Usage:
r=:   _ 2 _ _
r=:r,.2 _ 3 _
r=:r,._ 3 _ 4
r=:r,._ _ 4 _

a=:0
b=:3

(3 :'0 a}1 b}y+1e_4*c=:+/(-/~y)%r+1e_3')^:_<./r
%a{c

Explanation:

(3 :'...')^:_=/r - Repeat the explicit verb passed as a string until it converges (infinite power), starting with the scalar zero. It becomes a 1D array after the first iteration.

r+1e_4 - Add 100 μΩ parasitic resistance to each pair of resistor leads. We don't like wires. Lower values increase precision, but also limit the time step. If there are no wires, parasitic resistance is not needed.
(-/~y)% - Create the table of self-differences of the node voltage list (the table of voltage differences) (The table of self-differences of a scalar is a scalar zero). Divide this by the resistances. You get a list of resistor currents.
c=:+/ - Compute the sum of each column - the current flowing into each node - and tuck that away into a global variable.
y+1e_5* - Multiply that by the time step and add that to the node voltage of each node. The time step (divided by the parasitic capacitance of each node) must be lower than the lowest resistance, otherwise the simulation will not converge. Lower value = slower convergence. Without wires, we can increase this value to 1/2 and save three chars (and also speed up the convergence immensely). With wires, this won't converge at 1/2 Ω.
0 a}1 b} - Pin the probe voltages to 0 volts and 1 volt respectively.

%a{c - Take the current flowing into the ground, and return its inverse.

The answers it gives are usually off by a few digits, but I guess we'll count that as a margin of error in the measurements :D

Very elegant solution you have here (or at least very short). I wonder why the other problem has answers that are so long.

@JoeZ. The measurement error is caused by the parasitic resistance on each wire. You can lower that, but then it will take much longer to simulate (or not support bare wires)

Well, the fact that parasitic resistance makes the algorithm possible with bare wires seems like a very interesting property to have (wires have parasitic resistance in real life as well).

@JoeZ. Indeed. But, real life's time step of 5.4x10^-44 seconds is unbearably slow here :-)

@JoeZ., the other problem has one answer in Python (natural disadvantage with respect to J in vector arithmetic) and one in APL, which solves exactly rather than by simulation. Also both parse stdin rather than assuming that the data is already neatly parsed. (Given that you ask for a "program" rather than a function, statement, or expression, my understanding would be that this solution doesn't qualify).

I see. Well, that might account for it. (I do allow for the data to be neatly parsed already, by the way. I try to focus on the actual algorithmic bits rather than having half the code being spent on input processing.)


text:
Build a Mastermind engine
For reference to the game of Mastermind: Solving Mastermind in 6 or less moves
In the version of Mastermind used in this problem, the operating string is a 4-digit number, from 0000 to 9999, represented as either numbers from 0 to 9999 or strings of consecutive digits "0000" to "9999" in input.
Your task is to build a function that will take two numbers/strings secret and guess as input, and return two numbers A and B, the number of red and white pegs respectively.
The shortest code in any language to do this wins.

I think this spec would be improved by not having people go read the actual specification of the game in another challenge.

J: 40 26 29 22
=,&(+/)(~:#[)e.&~.~:#]

change: don't laminate, but work truly dyadically, eliminating need for explicit ranks ("1), lamination(,:) and between (/)
change: don't count duplicate characters twice
change: Strings are more efficient as they don't need parsing

This verb takes a left and right argument a string from '0000' to '9999'.
It takes care of doubles and excludes exact matches from checking correct numbers but wrong place.
Test cases:
NB. Give the beast a name
mm=: =,&(+/)(~:#[)e.&~.~:#]
NB. make 6 by 4 arrays of the inputs
secret =: (, ;. _2) '1254 1234 5441 5441 5441 5441 '
guess  =: (, ;. _2) '1342 1111 1234 4531 4441 5441 '

NB. Apply the verb on each pair of secret/guess
'1111' mm '1231'
2 0

NB. A whole bunch of test cases with formatting and printing of the inputs:
secret ([,' ',(":@mm),' ',])"1 guess

NB. output:
1254 1 2 1342
1234 1 0 1111
5441 0 2 1234
5441 1 2 4531
5441 3 0 4441
5441 4 0 5441

A little bit of explanation, reading from right to left:
NB.   ExactMatch: checks where digits correspond:
ExactMatch =: =

NB.   GoodDigitWrongPlace: Copies non-matched numbers from both arguments (left and right
NB.   pairs of parentheses, and checks them for same elements(e.), after eliminating
NB.   doubles in both (&~.)
GoodDigitWrongPlace =: (~: # [) (e.&~.) (~: # ])

NB.   Piecing the conditions together, after summing the booleans:
mm =: ExactMatch ,&(+/) GoodDigitWrongPlace

I think the result of "5441" and "1234" should be 0,2 rather than 0,3. The duplicate 4's should only be counted once. Save for "5441","4531"

Thanks, you are entirely right. Adds 3 characters ~.@

K, 41 36
{+/'(b;(in).(?x;y)@\:(!#x)@&~b:x=y)}

.
k)c1:("1254";"1234";"5441";"5441";"5441";"5441")
k)c2:("1342";"1111";"1234";"4531";"4441";"5441")
k){+/'(b;(in).(?x;y)@\:(!#x)@&~b:x=y)}'[c1;c2]
1 2
1 0
0 2
1 2
3 0
4 0

Ruby 2.0, 71 characters
f=->s,g{[x=(0..3).count{|n|s[n]==g[n]},g.chars.count{|e|s.sub!e,''}-x]}

This function actually modifies the first parameter, which is obviously a bit dodgy.  Would be easy enough to fix if it's actually against the rules.
I'm sure there's something sneaky you could do with String#count but I couldn't think of a nice way to handle duplicates.
Example usage:
p f['1254', '1342'] #=> [1, 2]
p f['1234', '1111'] #=> [1, 0]
p f['5441', '1234'] #=> [0, 2]
p f['5441', '4531'] #=> [1, 2]
p f['5441', '4441'] #=> [3, 0]
p f['5441', '5441'] #=> [4, 0]

Modifying the parameters is fine (they're being passed by value, not by reference).

@JoeZ. Why is this the accepted answer, when there are at least three other answers that are shorter?

It was just one of the first to be posted.  I'm sure he'll update it next time he checks :>

@chron: Yup.

GolfScript, 50 characters
{[[\].zip{1/~=},,\{$}/{1$?.)!!{)>0}*)},,\;1$-]}:M;

A similar solution to chron's answer written in GolfScript. Input must be provided as two strings on the stack, the result will be the array [A B].
Examples:
"1254" "1342" M p    # => [1 2]
"1234" "1111" M p    # => [1 0]
"5441" "1234" M p    # => [0 2]
"5441" "4531" M p    # => [1 2]
"5441" "4441" M p    # => [3 0]
"5441" "5441" M p    # => [4 0]

GolfScript (48 chars)
{[\]:&zip{1/~=},,.~)10,{{''+-,~5+}+&%.~>=+}/}:E;

E here stands for eval. I take a similar approach to Knuth's definition of the number of white pegs by calculating sum_{i=0}^{9} min(count(secret, i), count(guess, i)).
Online demo

MATL, 17 bytes
=s,4Y2@G!=s]Xlsy-

Try it online (Tested multiple inputs with this)
Explanation:
(For white pegs, Knuth's definition as mentioned by Peter Taylor is used: sum_{i=0}^{9} min(count(secret, i), count(guess, i)))
=         % check which digits are equal
s         % sum of 1s is the number of red pegs
,         % do twice
  4Y2     % predefined literal: '0':'9'
  @G      % get the next input
  !=      % broadcast equality check
  s       % sum to get the count of each digit in the input
]         % end
Xl        % elementwise minimum
s         % sum
y-        % subtract the number of red pegs
          % (implicit) convert to string and display

Python - 93
I'm pretty sure this is right. But a few example input/outputs in the question would help.
def m(S,G):
 R = [(s,g) for s,g in zip(S,G) if s!=g];S,G=zip(*R);W=set(S)&set(G);return 4-len(R),len(W)

And calling it gives:
print m('1234','1231')
>>> (3, 0)
print m('1234','1230')
>>> (3, 0)
print m('1234','1243')
>>> (2, 2)
print m('1234','4312')
>>> (0, 4)
print m("0123","0131")
>>> (2, 1)
print m("0123","0132")
>>> (2, 2)
print m("0123","0123")
>>> (4, 0)
print m("0123","4131")
>>> (1, 1)

The use of set makes me suspect that it will give a wrong answer for m("0011", "1100") (should be (0,4)).

@PeterTaylor Probably, but the rules seemed really poorly defined. But I'll change my anaswer if its wrong.

Knuth himself says that the rule for the number of white pegs "is somewhat difficult to state precisely and unambiguously, and the manufacturers have not succeeded in doing so on the directions they furnish with the game".

Here's a first draft in PowerShell: 168 characters.
function Test-Mastermind{param([char[]]$s,[char[]]$g)
4-($p=0..3|?{$s[$_]-ne$g[$_]}).Count
($p|%{$i=$_;$p|?{$s[$i]-eq$g[$_]-and0-ne$s[$i]}|%{($s[$i]=$g[$_]=0)}}).Count}

For the sake of illumination:
function Test-Mastermind {
    param([char[]]$s,[char[]]$g)
    4 - ($p = 0..3|?{ $s[$_] -ne $g[$_] }).count # count same  characters
    ( $p | % { $i = $_                           # ForEach $i in $p (char in secret)
        $p | ? {                                 # ForEach $_ in $p (char in guess)
            $s[$i] -eq $g[$_] -and 0 -ne $s[$i]  # If they match and aren't 0
         } | % { ($s[$i]=$g[$_]=0) }             # 0 them out, output something we can count
    } ).Count
}

Zeroes are allowed, so "0" shouldn't be the padding character.

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


text:
I'd like a homework pizza with everything on it, but no loops
So there was a "please do my homework question" on StackOverflow that lead to an idea. As everyone knows loops are quite expensive, in some places they can get as high as $12.99 an iterations, so to save money there shouldn't be any loops.
So, lets do the homework, but in the least intuitive way.

Write a program that decides, among competing candidate pizzas, which is the
  best deal, in the sense of the smallest cost per unit area. Pizzas come in three shapes:
  round, square, and oval (elliptical). The area of an oval is pi*ab/4, where:
   a and b are the longer and shorter dimensions of the oval.

The rest of the specifications are in the linked PDF, which I can add in if needed. The input and output should conform to the assignment.
As per breadboxes suggestion the I/O has changed a bit to be more golfy.

Your program must accept input for each pizza (lower case is a literal, uppercase is an argument):

In all of the below: C is the cost for that pizza in drachma (a float), and all units of length are in attoparsecs (~3cm).
C s L - a square pizza, with a size length L
C r D - a round pizza, with diameter D
C o L S - an oval pizza, with long side L and short side R, all ovals have an area of pi*L*S/4 (for some reason).
An empty string denotes that there are no more pizzas.

For each pizza, print out the area in attoparsecs, a literal @ and the cost in Drachma per square attoparsecs (just numbers, units not required).
After the user indicates there are no more pizzas, print the index of cheapest pizza (starting at 1).
Pi may be approximated to 3.1415

An example run would be (> indicates input, < is output, but these don't need to be printed to screen):
> 13.59 r 14.2
< 158.37 @ 0.086
> 14.04 s 12.3
< 151.29 @ 0.093
> 12.39 o 14.1 8.3
< 91.92 @ 0.135
>
< 1

Spaces are optional in output, but the @ symbol must be in the output of the pizza
However, you can't use any traditional loops. Recursion, gotos or list comprehension are all fine, but any thing that is syntactically a loop like a for, while or do ... while are all strictly forbidden.
Shortest code wins.

Do we want to adhere strictly to the lab's I/O? I suspect that those strings are going to wind up being the majority of everyone's character counts. It would be more to the spirit of codegolf if the I/O boilerplate could be downplayed. (Minimized, not in the codegolf sense of reduced to an absolute minimum, but in the sense of de-emphasized.) Either way, though, it would really improve the description if a complete sample session was included.

@breadbox I've changed the rules and I/O a little to make it more golfy. Thanks for the suggestion.

Does Ruby's Array#each (and other languages' equivalent constructs) count as a traditional loop, or as array comprehension? What about Ruby's while modifier that is technically a loop but it's written after the statement?

@JanDvorak I'm not well versed with ruby, but Array#each sounds in the spirit of the challenge, however while seems like it is not as it sounds like a do...while. Even if not its a token that sounds loop-ish.

I assume Java's for(Type elem:collection) counts as array comprehension?

Can we use 22/7 as the approximation?

@JanDvorak for looks like a loop so, no - not allowed. 22/7 it was good enough for Archimedes, so sure why not.

"all ovals have an area of piLS/4 (for some reason)" You'll notice that if L == S then this formula is pi * (2r)^2 / 4 which is pi * r^2. Essentially, this is just a generalization of the formula for the area of a circle. It's generally expressed as pi * a * b, where a and b are the semimajor and semiminor axes (i.e., half of L and S).

@user202729 I didn't think of that, since nobody pointed it out in the comments, and I didn't think of it while reading (replying to chat)

HTML/JavaScript, 160 bytes
(linebreaks/indentation only added here do prevent scrolling)
<input onchange='window.n++||(n=1,L=1e9);s=this.value.split(" ");d=s[2];
        a=[5.5/7*d*(s[3]||d),d*d][1*(s[1]=="s")];c=s[0]/a;alert(a!=a?m:a+"@"+c);
        L<c||(L=c,m=n)'>

The input is a text box (press Enter to submit); the output is an alert box.
A few caveats (or cheats, if you will):

Pi/4 is 5.5/7
in some cases, it assumes that the pizzas have non-zero areas
it's not possible to enter the same pizza twice in a row (because that won't trigger a change event)
note that defocusing the input also counts as "enter"
assumes that at least one pizza costs less than a billion Drachmas per square attoparsecs
no fault tolerance for the input whatsoever
you could argue that it's not qualified because it uses the browser's event loop

+1 - The code doesn't say for, while or loop. Using the browser seems like a legit abuse of the rules.

EDIT: Should note that I wrote this in response to prompting in the original stackoverflow question's comments.  So it attempts to exactly follow the homework assignment (which was supposed to be done in Python and produce specified output).  As such, it does not follow the updated golf-like rules.
So its absolutely not the shortest (repeats a lot of code), but it doesn't do any loops and it does some stupid things
def pizza(list,n):
    n = n + 1
    print 'Pizza Number ' + str(n) + ':'
    shape = raw_input('Pizza shape (round, square, oval):')
    if shape == 'oval':
        longer = float(raw_input('Pizza longer dimension:'))
        shorter = float(raw_input('Pizza shorter dimension:'))
        price = float(raw_input('Pizza price:'))
        area = (3.1415 * longer * shorter)/4
        print 'Pizza area is %.2f square inches' % area
        cost = price/area
        print 'Cost per square inch is $%.2f' % cost
        listing = '%d (OVAL %.2f x %.2f)' % (n,longer,shorter)
    elif shape == 'square':
        side = float(raw_input('Pizza side length:'))
        price = float(raw_input('Pizza price:'))
        area = side**2
        print 'Pizza area is %.2f square inches' % area
        cost = price/area
        print 'Cost per square inch is $%.2f' % cost
        listing = '%d (SQUARE %.2f x %.2f)' % (n,side,side)
    else:
        shape = 'round'
        diameter = float(raw_input('Pizza diameter:'))
        price = float(raw_input('Pizza price:'))
        area = 3.1415 * (diameter / 2)**2
        print 'Pizza area is %.2f square inches' % area
        cost = price/area
        print 'Cost per square inch is $%.3f' % cost
        listing = '%d (ROUND %.2f)' % (n,diameter)
    list[listing]=cost
    another = raw_input('Enter Another? (Y/N):')
    if another == 'Y':
        pizza(list,n)
        return list
    else:
        return list
dict=pizza({},0)
print 'The best deal is pizza number ' + min(dict, key=dict.get)

-Validates shape entry by assuming you want round if you enter anything else.
-Uses 3.1415 to avoid importing a library
-Assumes you are done if you enter anything besides 'Y'
-Every pizza is stored as a unique dictionary key.
Other than the things I intentionally did in a stupid way or to avoid a traditional loop, I'm open to any criticisms as I am not an accomplished python programmer.

I think doing things in intentionally stupid ways is part of the fun of being a golfer!

Well, I submitted my solution to the course's professor so we will see what he says.  Although I now notice that the course was being taught in Python 3 so I don't think my program will work as expected (I know there's some changes with input/raw_input).

Python - 251
Definitely not the shortest, but a good indication of whats required.
def p():
 i = raw_input().split(' ')
 if['']==i:return
 f=float;C=f(i.pop(0));S=i.pop(0);P=3.1416;a=f(i[0])
 if's'==S:A=a**2
 elif'r'==S:A=P*(a/2)**2
 elif'o'==S:A=P*a*f(i[1])/4
 c=C/A;print A,'@',c
 return[c,p()]
P=p()[:-1];print P,P.index(min(P))+1

Python 167 bytes
def p():
 try:return[eval("{2}*dict(s={2},r={2}*.7854,o={3}*.7854)['{1}']/{0}".format(*(raw_input()+' 1').split()))]+p()
 except:return[]
v=p()
print v.index(max(v))+1

Using the constant 0.7854 to approximate π/4.
Sample usage:
$ more in.dat
13.59 r 14.2
14.04 s 12.3
12.39 o 14.1 8.3

$ python homework-pizza.py < in.dat
1

Ruby, 128 132 141 characters
b,j,i=1/0.0,1
$<.map{|s|j+=1
c,s,x,y=[*z=s.split,0].map &:to_f
b,i=c,j if b>c
p"#{a={?s=>x*x,?r=>x*x*=0.7854,?o=>x*y}[z[1]]}@#{c/a}"}
p"#{i}"

Borrowed 0.7854 from Primo. It's more precise than 3.1415/4 anyways.
User indicates there are no more pizzas by closing the STDIN stream. Yes, CTRL+D works in the jRuby interactive console. Yes, you have to restart the console to reopen the stream.

Cool facts about Ruby:
Destructuring assignment: you can assign an array to a list of variables. If you try to pass a non-array, it will be converted to an array first. In case of non-array-likes, that's a single-element array containing that element. If the array is too short, extra variables are set to nil. If the array is too long, some elements are discarded. Here we assign nil to i for scoping reasons only.
Ruby's selling points are iterators and methods with callbacks in general. To be enumerable, all you have to do is to implement each and inherit the right methods. This challenge forbids traditional loops, but it allows array comprehensions. STDIN is an input stream, and as such it is enumerable. As a bonus, input stream comprehension sets the globals $_ (last line) and $. (line number) for us. Line 3 demonstrates the pretzel colon operator which constructs a block for the iterator.
Some find modifiers (do_something until it_is_done) confusing. I like them. Be careful that the order of evaluation (and of side-effects) is reversed, however. String interpolation - if overdone (like here) - can get messy at times (like here), and syntax highlighters can choke on nested interpolation (or give up completely, like here). Literal dereference. Just write a literal, and read from it immediately. Any decent language can do that (I owe an apology to PHP 5.3 at this point).
Of course, subexpression caching. As soon as an expression is long enough long or occurs frequently enough, stuff its value into a variable. Ruby's assignment has a low priority from the right, but high priority from the left. Thus, a*b=c*d assigns c*d to b. Also, carefully rearranging computation can let us alias variables. While normally a horrible thing, it can save characters when golfing because it lets one (ab)use the compound assignment operators. Unfortunately, it only works with operators.

Maybe it's just me, but I can't get this to run at all. 1.8.7, 1.9.3 and 2.0.0 all report undefined method \split' for nil. Changing line 2 to $<.map{|s|z=s.splitresults innil can't be coerced into Float, once again, in all three versions. Also, for what it's worth, the proper stream termination character on a windows machine seems to be ^Z` (at very least, PHP, Perl, Python and Ruby all seem to like it).

@primo I was testing in JRuby IRB Console [1.7.3 (1.9.3)]. Maybe it only works in IRB? CTRL+Z doesn't work for me in the jRuby console.

same nil to float coercion error in jruby: http://i.stack.imgur.com/UVwZz.png

@primo confirmed. Will debug.

@primo fixed. That's what I get for not testing every change.

A few more issues, unfortunately... 1) Ruby1.9.3 and Ruby2.0.0 both still require |s|z=s.split to run at all. 2) Ruby1.9.3 and Ruby2.0.0 do not report the best value, but rather the pizza with the lowest cost. 3) jRuby will always report 1 (this can be easily confirmed by adding a p$. to the loop comprehension).

@primo #2 is a misunderstanding of the rules. This can be fixed easily. As for #1 and #3 - can I claim jRuby IRB the platform? It works perfectly there.

I don't mean to rag on this, I think it's a very good solution, just not quite functional. A small modification makes a valid 1.9.3, and 2.0.0 solution (130 bytes): http://ideone.com/shS0nf You could claim a jRuby platform, but $. always coming back as 1 isn't very helpful.

@primo oh well. Fixed #1 and #2, but #3 got very expensive.