text:
So obviously, P = NP
SAT is the problem of determining whether a boolean expression can be made true. For example, (A) can be made true by setting A=TRUE, but (A && !A) can never be true. This problem is known to be NP-complete. See Boolean Satisfiability.
Your task is to write a program for SAT that executes in polynomial time, but may not solve all cases.
For some examples, the reason it is not really polynomial could be because:

There is an edge case that is not obvious but has a poor runtime
The algorithm actually fails to solve the problem in some unexpected case
Some feature of the programming language you are using actually has a longer runtime than you would reasonably expect it to have
Your code actually does something totally different from what it looks like it's doing

You may use any programming language (or combination of languages) you wish. You do not need to provide a formal proof of your algorithm's complexity, but you should at least provide an explanation.
The primary criteria for judging should be how convincing the code is.
This is a popularity contest, so the highest rated answer in a week wins.

This question hits more than one closure criterion. Too broad: a problem which solves any problem in P meets the criteria. Too subjective and/or unclear: "appears to execute in polynomial time" is open to all kinds of interpretations.

Would it be better if we restrict problem choices to well-known NP problems, and remove the twist? I think appears to execute in polynomial time is what gives people flexibility for the popularity contest.

It would be better if you restrict the problem domain, otherwise you invoke the cloud of uncertainty around what is "well-known". Why not pick a single NP-hard problem and focus on that? That has the advantage of leaving other such problems open to future questions along the same line. Several narrow questions can provide far more ongoing delight and entertainment to the site than one broad one.

Fair enough. I'll edit shortly.

Can't add comments yet... Eric Lippert's "solution" is of course a sleight of hand. The C# language requires the compiler to do all the work. So given a 3SAT problem, you can ask the C# compiler to solve it, which will take exponential time. With that done, the C# compiler generates a program that solves one instance of 3SAT in linear time. Now since the solution of any instance of any NP complete problem is either YES or NO, that's not really much of an achievement.

@gnasher729: I got the C# compiler to solve a SAT problem; I consider that to be a reasonably interesting achievement.

It would be fun if someone accidentally solves SAT in polynomial time here.

please tag this code trolling

@Turion: S/He'd be recruited to the Laundry.

fyi further inquiry there are P vs NP tags on cs.se & tcs.se. see also how not to solve P=?NP cs.se and math monster/many P vs NP refs/stackexchange questions

@Turion decades of Research, millions in rewards and prizes and all the women and fame one could have - but the real motivation for solving P=NP will end up being this PCG challenge.

Not thinking about the problem can sometimes make it easier.

@TimSeguine ...why?

Warhing: Do not do this in PHP. Everything is true if the PHP gods want it to be.

@NothingsImpossible: Women? Really?

I'm voting to close this question as off-topic because underhanded challenges are no longer welcome on this site. http://meta.codegolf.stackexchange.com/a/8326/20469

C#

Your task is to write a program for SAT that appears to execute in polynomial time.

"Appears" is unnecessary. I can write a program that really does execute in polynomial time to solve SAT problems. This is quite straightforward in fact.

MEGA BONUS: If you write a SAT-solver that actually executes in polynomial time, you get a million dollars! But please use a spoiler tag anyway, so others can wonder about it.

Awesome. Please send me the million bucks. Seriously, I have a program right here that will solve SAT with polynomial runtime.
Let me start by stating that I'm going to solve a variation on the SAT problem. I'm going to demonstrate how to write a program that exhibits the unique solution of any 3-SAT problem.  The valuation of each Boolean variable has to be unique for my solver to work.
We begin by declaring a few simple helper methods and types:
class MainClass
{
    class T { }
    class F { }
    delegate void DT(T t);
    delegate void DF(F f);
    static void M(string name, DT dt)
    {
        System.Console.WriteLine(name + ": true");
        dt(new T());
    }
    static void M(string name, DF df)
    {
        System.Console.WriteLine(name + ": false");
        df(new F());
    }
    static T Or(T a1, T a2, T a3) { return new T(); }
    static T Or(T a1, T a2, F a3) { return new T(); }
    static T Or(T a1, F a2, T a3) { return new T(); }
    static T Or(T a1, F a2, F a3) { return new T(); }
    static T Or(F a1, T a2, T a3) { return new T(); }
    static T Or(F a1, T a2, F a3) { return new T(); }
    static T Or(F a1, F a2, T a3) { return new T(); }
    static F Or(F a1, F a2, F a3) { return new F(); }
    static T And(T a1, T a2) { return new T(); }
    static F And(T a1, F a2) { return new F(); }
    static F And(F a1, T a2) { return new F(); }
    static F And(F a1, F a2) { return new F(); }
    static F Not(T a) { return new F(); }
    static T Not(F a) { return new T(); }
    static void MustBeT(T t) { }

Now let's pick a 3-SAT problem to solve. Let's say
(!x3) &
(!x1) &
(x1 | x2 | x1) &
(x2 | x3 | x2)

Let's parenthesize that a bit more.
(!x3) & (
    (!x1) & (
        (x1 | x2 | x1) &
        (x2 | x3 | x2)))

We encode that like this:
static void Main()
{
    M("x1", x1 => M("x2", x2 => M("x3", x3 => MustBeT(
      And(
        Not(x3),
        And(
          Not(x1),
          And(
            Or(x1, x2, x1),
            Or(x2, x3, x2))))))));
}

And sure enough when we run the program, we get a solution to 3-SAT in polynomial time. In fact the runtime is linear in the size of the problem!
x1: false
x2: true
x3: false

 You said polynomial runtime. You said nothing about polynomial compile time. This program forces the C# compiler to try all possible type combinations for x1, x2 and x3, and choose the unique one that exhibits no type errors. The compiler does all the work, so the runtime doesn't have to.  I first exhibited this interesting techinque on my blog in 2007: http://blogs.msdn.com/b/ericlippert/archive/2007/03/28/lambda-expressions-vs-anonymous-methods-part-five.aspx Note that of course this example shows that overload resolution in C# is at least NP-HARD. Whether it is NP-HARD or actually undecidable depends on certain subtle details in how type convertibility works in the presence of generic contravariance, but that's a subject for another day.

You'll have to contact the clay mathematics institute for your million bucks. But I am not sure they will be satisfied.

This is absolutely amazing. Good job.

I think it's worth mentioning that this approach specifically solves 3-SAT, and can at best be generalized to solve K-SAT, for some finite K. However, afaict you cannot generalize this approach to solve general SAT, at least in a staticly typed language like C#.

@EricLippert: Actually, by nesting Or clauses (since Or(x,y,z) == Or(x,Or(y,z))), you can make the clauses arbitrarily long. Therefore, it is possible to solve SAT problems directly using the current framework.

@mneonneo: Arbitrarily long is not infinitely long. I could nest the clauses 1,000,000 times, but that would not allow me to solve 1,000,001-SAT, without writing a new program and recompiling. If I don't know the size of the input beforehand, this is not feasable.

Of course any SAT problem can be transformed into an equivalent 3-SAT problem, so this restriction is merely an inconvenience. The more vexing issue with my "solution" is that it requires that the problem have a unique solution. If there is no solution or more than one solution then the compiler gives an error.

@JonathanPullano I believe everything above 1,000,000 can be considered an edge case and unexpected input, according to 1. and 2. in the question.

@Petr: I agree with you. I just to inform the readers and perhaps encourage someone to try something new.

@EricLippert the uniqueness requirement is ok. You can always reduce SAT to Unique-SAT (SAT but assuming the inputs have 0 or 1 assignments) using a polynomial time randomized reduction. Keywords: Isolation Lemma, Valiant-Vazirani theorem.

Amazing write up: http://andysresearch.blogspot.com.ar/2007/06/paths-to-discovery-valiant-vazirani.html

@JonathanPullano: Nesting Ors gives you a way to encode arbitrary SAT problems in a manner consistent with the helper types already defined (this is distinct from converting SAT->3SAT because you encode the boolean logic directly). Plus, SAT isn't defined in terms of infinite-length clauses (that would make the problems infinitely long), but rather in terms of clauses that can be of arbitrary length.

@DiegodeEstrada: I did not know that -- thanks for the note!

@EricLippert: AFAIK the compiler errors should tell you if the problem is satisfiable or not (i.e. whether the invocations are ambiguous or unsatisfiable). Too bad it won't produce anything executable...

@nneonneo: That's correct.

@mneonneo: Encoding SAT problems is a fine approach, though that encoding not explicitly written in this code, and the challenge is to write a program that solves SAT (The solution is still valid as per Petr's comment). I was not referring to infinite length clauses though. To solve a SAT problem directly with this method with a finite but arbitrarily long number of clauses would require an infinite amount of code. This is because even though each individual input is finite, it can be arbitrarily high, and so there are an infinite number of cases for the code to check.

@JonathanPullano: I'm not following your train of thought here.  Take your finite SAT problem. There's allegedly a polynomial algorithm to turn that into a "unique 3-SAT" problem. That will have a finite number n of variables and a finite number m of AND clauses, each clause having no more than three variables. Encode the variables by introducing n nested lambdas as I show, and encode the AND clauses with m nested calls to And. Run the compiler -- that's the non-polynomial step -- and then run the executable to get the answer.

@JonathanPullano: The contents of Main() constitute an encoding of the problem into C# code. Encoding is distinct from transformation; in the former case, you are simply translating the problem from mathematical terminology into a particular sequence of characters understood by the compiler, and in the latter you are creating a problem instance of a different problem which equivalently solves the original problem instance.

@EricLippert: My point actually is that you don't need to turn your SAT problem into a 3SAT problem because you can just nest Or clauses to get arbitrarily long boolean clauses.

Eric: I completely agree with you that transforming the problem to 3SAT is a valid answer. It might be nice to see that transformation explicitly, but even without that the answer is valid as per Petr's logic. mneonneo suggests that you can also encode arbitrarily long clauses to solve general SAT directly, however unless I am misunderstanding how he does this, I think you could only solve an instance of K-SAT this way, but not general SAT, because in the general case you would need to list out an infinite number of cases in code. This is getting a bit off-topic though guys :)

Nit: UNIQUE-3SAT, the problem you are solving here, is not NP-complete. It is co-NP-complete, and it is widely thought (though not proven) that co-NP != NP. So, technically, this answer does not solve a known NP-complete problem.

@JonathanPullano: Why would you need to list out an infinite number of cases? For example, we can encode (x v y v z v w) as Or(Or(x,y,z),x,w), without having to create a 4-argument version of the Or function.

@nneonneo: I am learning all kinds of new things today, thanks!

@nneonneo: Thanks, I now follow what you are saying. I suppose an ideal answer would take in some input and then generate the source code above via your encoding, but that is really just a technicality.

Nitpicking: The code above isn't really the program, it is the input. The program that is solving 3-SAT is the C# compiler. The solution is the compiled program - it already contains the solution, you don't even have to run it. The run time of the compiled program is irreverent - the complexity is of the run time is inside the compiler. All of this isn't very important, but I wouldn't give you a million dollars. Thanks for this answer and for the interesting discussion is created!

@Kobi even if he did solve P=NP, I don't think many people here would have the means/will to give him a million dollars. I, for starters, surely wouldn't.

I really love this solution. Reminds me of a C++ technique I read about once, called template metaprogramming. I think programmers often forget how powerful their compilers are.

"Seriously, I have a program right here that will solve SAT with polynomial runtime." - me too, but unfortunately it does not fit in this comment box.

@Kobi: Yes, that's the joke.

@CompuChip: Indeed. We see here that semantic analysis of C# is at least NP-HARD. C++ metaprogramming is even harder; it's Turing-complete and therefore not decidable. The Haskell type system also has this property.

This program runs in O(1) actually. There is no input. If I made a program that outputted x1: false\nx2: true\nx3: false it would be equivalent to this program. And take much less time to compile as well.

@ArlaudPierre: The reference to a million dollar prize is: http://www.claymath.org/millenium-problems/p-vs-np-problem  the Clay institute has a bounty of $1M each for a collection of unsolved important problems.

@EricLippert I know, but you're not the Clay institute :-)

@CompuChip, From now on you will be known as Fermat.

This particular instance of 3SAT is also an instance of 2SAT.

I don't think this program solves any SAT problem, since the problem is not taken as its input. What it does is simply printing out the answer of a specific instance of the SAT problem.

@hpsMouse: I've given you a recipe for making a program that solves any SAT problem you care to name. The example I gave is an illustration of how to do so. Making a program that takes as its input SAT problems, produces a C# program that encodes it, compiles it and runs it, is left as an exercise; I figured that was so straightforward as to not need doing explicitly.

I just wanted to point out that you could actually use dynamic code compilation in C# to take the problem as input :)

@EricLippert: Yes, but any program that takes a SAT problem as input and compiles it no longer has polynomial runtime :(

C# can do type-level programming? This puts C++ templates and Haskell multi-parameter typeclasses into shame

@SHiNKiROU: Not really. C++ templates are known to be Turing-complete, as is I believe the Haskell type system. The C# type system is generally considered to have less representational power than either C++ or Haskell.

I've signed up here only to upvote this answer.

Hmm, the "MEGA BONUS" on the question was removed...

@JonathanPullano the "clay" mathematics institute?

Multi-language (1 byte)
The following program, valid in many languages, mostly functional and esoteric, will give the correct answer for a large number of SAT problems and has constant complexity (!!!):
0

Amazingly, the next program will give the correct answer for all remaining problems, and has the same complexity. So you just need to pick the right program, and you'll have the correct answer in all cases!
1

This is amazing. I had myself a good laugh.

Absolutely f****** brilliant!

Hmm. It's easy now. All I need to do is write a program that will pick the right program!

Precisely ! :-)

Just so people don't get the wrong impression: A meaningful problem, in the world of complexity theory, is a question with an infinite amount of instances. Here we have two programs that solve every instance of every problem, but solve only the (infinitely small portion of) problems that have constant result. I actually had an exercise question "Is 'does the decimal representation of pi have 100 consecutive zeroes' decidable?" The answer was "yes" since one of the above programs does solve it.

@shiona I agree on the first statement. But not on the second :) Since every problem (instance) can be formulated in terms of a yes/no question (and in particular every NP problem in terms of a SAT one), the two programs will solve any problem, once appropriately formulated :)

@Mau A wikipedia definition, and the one I was taught: "A decision problem is any arbitrary yes-or-no question on an infinite set of inputs."

@shiona I am not aware of any methods of determining whether or not a specific digit sequence exists in pi that do not involve calculations of some number of digits of pi, so is the decidability of a problem not based on the decidability of its result? While the result of the decision problem is constant (as pi does not change), any process to determine the result will only terminate if the result is "yes", which I thought would make the problem only partially decidable.

@JAB There is no method to solve the problem, so in a way I think you are on the right track. Now that you brought up partial (semi-)decidability, I think I will have to read it up some more before continuing.

Reminiscent of http://xkcd.com/221/.

I don't get it. :/

No longer funny

@shiona (I realize this comment is very late) Your comments don't make sense to me, as they are related to decidability, which this thread has nothing to do with. In fact, algorithms that don't decide the problem are explicitly acceptable. The pi-thing is decidable because if there is a longest finite number of consecutive 0s in pi (call that k), then compare our input number n to k and output "yes" iff n <= k, otherwise no. If there isn't a longest sequence, output "yes" for any input n. We just don't know which algorithm is correct, but that has nothing to do with decidability.

@shiona Also "problems that have constant result" makes no sense, as languages are defined as sets, and any object is either in any given set or it isn't, so every answer to every decidability problem is always constant.

JavaScript
By using iterated non-determinism, SAT can be solved in polynomial time!
function isSatisfiable(bools, expr) {
    function verify() {
        var values = {};
        for(var i = 0; i < bools.length; i++) {
            values[bools[i]] = nonDeterministicValue();
        }
        with(values) {
            return eval(expr);
        }
    }
    function nonDeterministicValue() {
        return Math.random() < 0.5 ? !0 : !1;
    }

    for(var i = 0; i < 1000; i++) {
        if(verify(bools, expr)) return true;
    }
    return false;
}

Example usage:
isSatisfiable(["a", "b"], "a && !a || b && !b") //returns 'false'

This algorithm just checks given boolean formula a thousand times with random inputs. Almost always works for small inputs, but is less reliable when more variables are introduced.

By the way, I'm proud that I had the opportunity to utilize two of the most underused features of JavaScript right next to each other: eval and with.

This is actually a well established testing method. Haskell's QuickCheck library started all the fun, I believe. It has since been reimplmented in many languages.

I think it should be noted that, this program is less likely to return the correct answer, the bigger the sat expression. The 1000 in the for loop should somehow scale with the input size(some polynomial non-O(1) scaling).

@Cruncher To be more precise, the larger the number of variables, the less likely it is to return the correct answer. (e.g. a very long expression with a single variable will almost always return the correct answer)

@PeterOlson well of course. I was stating it as loosely as possible. A longer SAT expression is more likely to contain more variables

Randomness is not the same thing as nondeterministic. Both of them have precise definitions and they don't overlap.

@Tim: A program which is deterministic on its input may be fed random input, is that what you're getting at?  But a random (not pseudo-random) number generator is non-deterministic, and a program whose output depends on an entropy source other than its input is also non-deterministic (wrt its input).

@BenVoigt no I am getting at: The colloquial use of the word "nondeterministic" is different than its use in complexity theory. This program is obviously making a play on the fact that SAT is in NP (nondeterministic polynomial time), but then proceeds to branching randomly. But a non deterministic program (in the sense of a nondeterministic Turing machine) will always accept if any of the reachable branches accepts.

@Tim: Hmm.  But nondeterministic also has a strong definition (stochastic) in other technical fields.  If I needed a formal technical term for your NTM it would be list-valued or vector-valued computation.  So sorry, you're trying to impose the definition from another field, when the word was used correctly in context.  The technical meaning of non-deterministic is multi-valued (and many of those values are quite precise).  I guess a complexity theorist would say the meaning is non-deterministic?

@BenVoigt since the question is based on a complexity theoretic claim, I think it is more than reasonable to expect the term to be used in that sense in an answer. No I would just call it ambiguous, just like the question it is posted as an answer to.

@TimSeguine I admit that my use of the word "nondeterministic" in this context is dubious at best, just like the claim that SAT can be solved in polynomial time. I know it's not correct, it's just part of the game of deception.

You had (and took) the opportunity to use the two worst features of Javascript: eval and with.

@PaulDraper and then call them underused! I had a nice laugh!

Mathematica + Quantum Computing
You may not know that Mathematica comes with quantum computer aboard
Needs["Quantum`Computing`"];

Quantum Adiabatic Commputing encodes a problem to be solved in a Hamiltonian (energy operator) in such way that its state of minimum energy ("ground state") represents the solution. Therefore adiabatic evolution of a quantum system to the ground state of the Hamiltonian and subsequent measurement gives the solution to the problem.
We define a subhamiltonian that corresponds to || parts of the expression, with appropriate combination of Pauli operators for variables and its negation

Where for expression like this
expr = (! x3) && (! x1) && (x1 || x2 || x1) && (x2 || x3 || x2);

the argument should look like
{{{1, x3}}, {{1, x1}}, {{0, x1}, {0, x2}, {0, x1}}, {{0, x2}, {0, x3}, {0, x2}}}

Here is the code to construct such argument from bool expression:
arg = expr /. {And -> List, Or -> List, x_Symbol :> {0, x},
    Not[x_Symbol] :> {1, x}};
If[Depth[arg] == 3, arg = {arg}];
arg = If[Depth[#] == 2, {#}, #] & /@ arg

Now we construct a full Hamiltonian, summing up the subhamiltonians (the summation corresponds to && parts of the expression)
H = h /@ arg /. List -> Plus;

And look for the lowest energy state
QuantumEigensystemForm[H, -1]

If we got an eigenvalue of zero, then the eigenvector is the solution
expr /. {x1 -> False, x2 -> True, x3 -> False}
> True

Unfortunately the official site for the "Quantum Computing" add-on is not active and I can't find a place to download it, I just still had it installed on my computer. The Add-on also have a documented solution to the SAT problem, on which I based my code.

I have no idea how this answer works. +1

"adiabatic evolution of a quantum system to the ground state", how that happens?

@XiaogeSu "Naturally".

@swish OK. Now consider a Hydrogen atom, in 1st excited state. If there is no vacuum fluctuation, then base on Schoedinger equation it will stay in 1st excited state. I cannot see how it goes to ground state.

@XiaogeSu Evolution determined by the Hamiltonian, and naturally it evolves to the lowest energy. So knowing the spectrum, we can assume that the system will end up in the ground state.

@SCOTTAARONSON did you have a momentary lapse of your ethics?

@XiaogeSu in order to go to the ground state, one also needs to have an interaction with the environment  that deexcitates the higher states, you're right. The idea here is that this interaction is very small, "adiabatic".

fyi adiabatic QM computing has a lot of similarities to classical simulated annealing. now implemented by Dwave. its similar to a "cooling" temperature/energy system that "finds/settles" in local minima.

see also Dwave & the inception of the QM computing dream for more bkg/details on the world-leading implementation of QM computing

FWIW, I think you got this package from here - http://homepage.cem.itesm.mx/lgomez/quantum/index.htm

How does this work, given NP is not known to be in BQP? Even with (theoretically) a quantum computer, how does this give a polynomial time solution to 3-SAT?

Three approaches here, all involve a reduction of SAT into its 2D geometric lingua franca: nonogram logic puzzles. Cells in the logic puzzle correspond to SAT variables, constraints to clauses.
For a full explanation (and to please review my code for bugs!) I've already posted some insight to patterns within the nonogram solution space. See https://codereview.stackexchange.com/questions/43770/nonogram-puzzle-solution-space . Enumerating >4 billion puzzle solutions and encoding them to fit in a truth table shows fractal patterns -- self-similarity and especially self-affinity. This affine-redundancy demonstrates structure within the problem, exploitable to reduce the computational resources necessary to generate solutions. It also shows a need for chaotic feedback within any successful algorithm. There is explanatory power in the phase transition behavior where "easy" instances are those that lie along the coarse structure, while "hard" instances require further iteration into fine detail, quite hidden from normal heuristics. If you'd like to zoom into the corner of this infinite image (all <=4x4 puzzle instances encoded) see http://re-curse.github.io/visualizing-intractability/nonograms_zoom/nonograms.html
Method 1. Extrapolate the nonogram solution space shadow using chaotic maps and machine learning (think fitting functions similar to those that generate the Mandelbrot Set).

Here is a visual proof of induction. If you can scan these four images left to right and think you have a good idea to generate the missing 5th... 6th... etc. images, then I have just programmed you as my NP oracle for the decision problem of nonogram solution existence. Please step forth to claim your prize as the world's most powerful supercomputer. I'll feed you jolts of electricity every now and then while the world thanks you for your computational contributions.
Method 2. Use Fourier Transforms on the boolean image version of inputs. FFTs provide global information about frequency and position within an instance. While the magnitude portion should be similar between the input pair, their phase information is completely different -- containing directionalized information about a solution projection along a specific axis. If you're clever enough you might reconstruct the phase image of the solution via some special superposition of the input phase images. Then inverse transform the phase and common magnitude back to the time domain of the solution.
What could this method explain? There are many permutations of the boolean images with flexible padding between contiguous runs. This allows a mapping between input -> solution taking care of multiplicity while still retaining FFTs' property of bidirectional, unique mappings between time domain <-> (frequency, phase). It also means there's no such thing as "no solution." What it would say is that in a continuous case, there are greyscale solutions that you're not considering when looking at the bilevel image of traditional nonogram puzzle solving.
Why wouldn't you do it? It's a horrible way to actually compute, as FFTs in today's floating-point world would be highly inaccurate with large instances. Precision is a huge problem, and reconstructing images from quantized magnitude and phase images usually creates very approximate solutions, although maybe not visually for human eye thresholds. It's also very hard to come up with this superpositioning business, as the type of function actually doing it is currently unknown. Would it be a simple averaging scheme? Probably not, and there's no specific search method to find it except intuition.
Method 3. Find a cellular automata rule (out of a possible ~4 billion rule tables for von Neumann 2-state rules) that solves a symmetric version of the nonogram puzzle. You use a direct embedding of the problem into cells, shown here.

This is probably the most elegant method, in terms of simplicity and good effects for the future of computing. The existence of this rule isn't proven, but I have a hunch it exists. Here's why:
Nonograms require lots of chaotic feedback in the algorithm to be solved exactly. This is established by the brute force code linked to on Code Review. CA is just about the most capable language to program chaotic feedback.
It looks right, visually. The rule would evolve through an embedding, propogate information horizontally and vertically, interfere, then stabilize to a solution that conserved the number of set cells. This propogation route follows the path (backwards) that you normally think of when projecting a physical object's shadow into the original configuration. Nonograms derives from a special case of discrete tomography, so imagine sitting concurrently in two kitty-cornered CT scanners.. this is how the X-rays would propogate to generate the medical images. Of course, there are boundary issues -- the edges of the CA universe cannot keep propogating information beyond the limits, unless you allow a toroidal universe. This also casts the puzzle as a periodic boundary value problem.
It explains multiple solutions as transient states in a continuously oscillating effect between swapping outputs as inputs, and vis versa. It explains instances that have no solution as original configurations that don't conserve the number of set cells. Depending on the actual outcome of finding such a rule, it may even approximate unsolvable instances with a close solution where the cell states are conserved.

+1 for leaving me saying "why didn't I think of that?" :P

You are Stephen Wolfram and I claim my five pounds!

This answer really deserves more credit, as it's the best attempt to make a convincing program. Good show.

C++
Here is a solution that is guaranteed to run in polynomial time: it runs in O(n^k) where n is the number of booleans and k is a constant of your choice.

 It is heuristically correct, which I believe is CS-speak for "it gives the correct answer most of the time, with a bit of luck" (and, in this case, an appropriately large value of k - edit it actually occurred to me that for any fixed n you can set k such that n^k > 2^n - is that cheating?).

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <cmath>
#include <vector>

using std::cout;
using std::endl;
typedef std::vector<bool> zork;

// INPUT HERE:

const int n = 3; // Number of bits
const int k = 4; // Runtime order O(n^k)

bool input_expression(const zork& x)
{
  return
  (!x[2]) && (
    (!x[0]) && (
      (x[0] || x[1] || x[0]) &&
      (x[1] || x[2] || x[1])));
}

// MAGIC HAPPENS BELOW:

 void whatever_you_do(const zork& minefield)
;void always_bring_a_towel(int value, zork* minefield);

int main()
{
  const int forty_two = (int)pow(2, n) + 1;
  int edition = (int)pow(n, k);
  srand(time(6["times7"]));

  zork dont_panic(n);
  while(--edition)
  {
    int sperm_whale = rand() % forty_two;
    always_bring_a_towel(sperm_whale, &dont_panic);

    if(input_expression(dont_panic))
    {
      cout << "Satisfiable: " << endl;
      whatever_you_do(dont_panic);
      return 0;
    }
  }

  cout << "Not satisfiable?" << endl;
  return 0;
}
void always_bring_a_towel(int value, zork* minefield)
{
  for(int j = 0; j < n; ++j, value >>= 1)
  {
    (*minefield)[j] = (value & 1);
  }
}

void whatever_you_do(const zork& minefield)
{
  for(int j = 0; j < n; ++j)
  {
    cout << (char)('A' + j) << " = " << minefield[j] << endl;
  }
}

Good answer. I would put the explanation in a spoiler tag so people can stare at it and scratch their head a bit.

Thanks for the suggestion @JonathanPullano, I've added a spoiler tag and obfuscated the code a bit.

By the way, I only just found out about bitfield, maybe I would have preferred that over std::vector.

+1 for the creative obfuscation and hitchhiker's references

Yes of course that's cheating, if k depends on n it's not much of a constant :-)

@RemcoGerlich k doesn't depend on n - you can set it to whatever you want. If you choose k "large" the algorithm just is more likely to get the answer right ;) The observation was that if you choose it to be of the order 2^n then average run time is O(2^(n-1)) (I think) but with a proper uniform random generator the answer will be found with probability 1.

@RemcoGerlich and of course it's cheating - if you have a real polynomial-order algorithm that is guaranteed to find the correct answer then please publish it!

ruby/gnuplot 3d surface
(ooh stiff competition!) ... anyway ... is a picture worth a thousand words? these are 3 separate surface plots made in gnuplot of the SAT transition point. the (x,y) axes are clause & variable count and the z height is total # of recursive calls in the solver. code written in ruby. it samples 10x10 points at 100 samples each. it demonstrates/uses basic principles of statistics and is a Monte Carlo simulation.
its basically a davis putnam algorithm running on random instances generated in DIMACS format. this is the type of exercise that ideally would be done in CS classes around the world so students could learn the basics but is almost not taught specifically at all... maybe some reason why there are so many bogus P?=NP proofs? there is not even a good wikipedia article describing the transition point phenomenon (any takers?) which is a very prominent topic in statistical physics & is key also in CS.[a][b] there are many papers in CS on the transition point however very few seem to show surface plots! (instead typically showing 2d slices.)
the exponential increase in runtime is clearly evident in 1st plot. the saddle running through the middle of 1st plot is the transition point. the 2nd and 3rd plots show the % satisfiable transition.
[a] phase transition behavior in CS ppt Toby Walsh
[b] empirical probability of k-SAT satisfiability tcs.se
[c] great moments in empirical/experimental math/(T)CS/SAT, TMachine blog

 P=?NP QED!

#!/usr/bin/ruby1.8

def makeformula(clauses)
    (1..clauses).map \
    {
            vars2 = $vars.dup
            (1..3).map { vars2.delete_at(rand(vars2.size)) * [-1, 1][rand(2)] }.sort_by { |x| x.abs }
    }

end

def solve(vars, formula, assign)

    $counter += 1
    vars2 = []
    formula.each { |x| vars2 |= x.map { |y| y.abs } }
    vars &= vars2

    return [false] if (vars.empty?)
    v = vars.shift
    [v, -v].each \
    {
            |v2|
            f2 = formula.map { |x| x.dup }
            f2.delete_if \
            {
                    |x|
                    x.delete(-v2)
                    return [false] if (x.empty?)
                    x.member?(v2)
            }
            return [true, assign + [v2]] if (f2.empty?)
            soln = solve(vars.dup, f2, assign + [v2])
            return soln if (soln[0])
    }
    return [false]
end

def solve2(formula)
    $counter = 0
    soln = solve($vars.dup, formula, [])
    return [$counter, {false => 0, true => 1}[soln[0]]]
end

c1 = 10
c2 = 100
nlo, nhi = [3, 10]
mlo, mhi = [1, 50]
c1.times \
{
    |n|
    c1.times \
    {
            |m|
            p1 = nlo + n.to_f / c1 * (nhi - nlo)
            p2 = mlo + m.to_f / c1 * (mhi - mlo)
            $vars = (1..p1.to_i).to_a
            z1 = 0
            z2 = 0
            c2.times \
            {
                    f = makeformula(p2.to_i)
                    x = solve2(f.dup)
                    z1 += x[0]
                    z2 += x[1]
            }
#           p([p1, p2, z1.to_f / c2, z2.to_f / c2]) # raw
#           p(z1.to_f / c2)                         # fig1
#           p(0.5 - (z2.to_f / c2 - 0.5).abs)       # fig2
            p(z2.to_f / c2)                         # fig3
    }
    puts
}

I'm glad you contributed this answer. In any successful proof of P versus NP (either way) it's one of many requirements for predictive power. Thanks for pointing out its importance. :)

more musings on P vs NP, many top/ collected refs, etc


text:
Tips for golfing in Julia
What general tips do you have for golfing in Julia? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Julia (e.g. "remove comments" is not an answer).

NOTE: The below are correct as of Julia 1.4.1
A few tricks to save a few characters

Overload operators with frequently used binary functions. For example, if you need to do a lot of integer divisions, and no need for inverse division, use \ =div, and you can then type a\b instead of div(a,b). Note the space - this is necessary to avoid it parsing as a "=" operator. Also note that, if overloaded at REPL prompt level, use (\)=Base.(\) or \ =Base. \ to reset it. NOTE: some functions have existing UTF-8 operators pre-defined, such as ÷ for div, as noted by Alex A.
Use ^ with strings for conditional output. That is, rather than a>0?"Hi":"", use "Hi"^(a>0) to save one byte, or for boolean a, use "Hi"^a to save three bytes.
(sometimes) Store small fixed-size vectors as separate variables. For instance, rather than a=split("Hi there"," "), you may be able to avoid a[1] and a[2] by using a,b=split("Hi there"," "), which can be referenced as a and b, saving three bytes for each use, at the cost of just two extra characters at assignment. Obviously, do not do this if you can work with vector operations.
Don't use isempty for Arrays, Tuples, or Strings - instead, use ==[] for arrays and ==() for tuples; similarly, for the negative, use !=[] and !=(). For strings, use =="" for empty, but use >"" for not-empty, as "" is lexicographically before any other string and it saves one byte.
Use the right short-circuit boolean operator in place of "if". It might be a bit less Julia-specific, but it is worth bearing in mind. x<=1&&"Hi" can be written as x>1||"Hi", saving a character (so long as the return of the boolean isn't important).
Don't use contains to check presence of character in string - if you're restricted to the basic ASCII, use in('^',s) rather than contains(s,"^"). If you can use other characters, you can save a bit more with '^'∈s, but note that ∈ is 3 bytes in UTF-8.
Looking for minimum/maximum values in an array? Don't use minimum or maximum - rather than using minimum(x) or maximum(x), use min(x...) or max(x...), to shave one character off your code. Alternatively, if you know all elements of x will be non-negative, use minabs(x) or maxabs(x)
Where possible and permitted by the challenge, use an actual newline instead of \n - note that this will make your code harder to read, and may mean that you need to provide an "ungolfed" version to make it possible for people to actually understand it.
Put options after the regex string - if you want to have a regex string in multiline mode, for example, don't type r"(?m)match^ this", type r"match^ this"m, saving three characters.
Where possible, use array concatenation instead of push!, unshift!, append!, or prepend! - for normal arrays, this can be done easily. For arrays of type Any with array elements, you will need the type Any, as in Any[[1,2]]. At one stage, curly braces could be used as an alternate notation ({[1,2]}), but this has been discontinued.
Don't use collect to convert a string into a char array - instead of collect(A), use [A...], which will do the same thing and save 4 bytes.
Need a number converted to a string? Use "$(s[i])" or dec(s[i]) for expressions or multi-character variables, and "$i" for single-character variables.
Use union or ∪ instead of unique - union(s) will do the same thing as unique(s), and save a byte in the process. If you can use non-ASCII characters, then ∪(s) will do the same thing, and ∪ only costs 3 bytes instead of the 5 bytes in union. In some circumstances, for single-character variables, you can save another byte using s∪s (thanks, MarcMush, for s∪s).
Use array indexing to get the size of an array or string - when you use end within array indexing, it automatically gets converted to the length of the array/string. This can be handy when you want to collect the length while doing certain operations. For example, if you need the length of A and the middle value, you might write A[(k=end)÷2]. This can also work in multiple dimensions, and for index iterators - A[(k=1:end;)] will give you an iterator for k=1:length(A), which can be handy when you also want to use A. Note that the assignment must occur in brackets, with a semicolon (such as (k=end;)) if no operation is done outside the brackets. (thanks to MarcMush for identifying a workaround for keywords in array indexing)

Outdated tricks that worked at some point, but no longer do:

 Access first element of Array with [] - for arrays, the expression A[] is equivalent to A[1]. Note that this does not work for Strings if you wish to get the first character, or for Tuples. - A[] no longer works.

 Reverse 1-D arrays using flipud - reverse(x) is one byte longer than flipud(x) and will perform the same operation, so the latter is better. - flipud is no longer in Base.

 Use ?: instead of && or || for conditional assignment - that is, if you want to perform an assignment only on some condition, you can save one byte by writing cond?A=B:1 rather than cond&&(A=B), or cond?1:A=B rather than cond||(A=B). Note that the 1, here, is a dummy value. - the ?: notation now requires spaces around ? and :.

Oh how I would love that first trick in Python.

You can split on spaces using simply split("Hi there") since the pattern argument defaults to a space.

@AlexA. - I know, but it's not the point of the tip, and the tip applies equally well either way.

Point 12 has changed in 0.5.

@Oxinabox - I'm not surprised, I'm pretty sure a few of them are outdated by now. I originally wrote most of the tips for 0.3, I think.

?: seems to be less useful in recent versions of Julia, as both need to be surrounded by spaces, adding 4 useless bytes.

@ETHproductions - yeah, there have been some changes that undoubtedly cause issues with some of the tips. I'll eventually update the tips to suit current behaviour.

I think 13 and 14 no longer work.

@HenriqueFerrolho - thanks, I'll revisit the list soon (hopefully by this weekend) to figure out which ones are now outdated, as well as whether there are any notable new tricks.

I know it took some time, but I've updated the list to separate out the deprecated tips, which are now listed as spoilers at the end. I will attempt to update with new tips, soon.

@MarcMush - thank you, I've made some edits based on your feedback. I'll have to revisit with more tips, soon.

Redefine operators to define functions
Redefining operators can save a lot of bytes in parentheses and commas.
Recursive unary operators
For a unary example, compare the following recursive implementations of the Fibonacci sequence:
F(n)=n>1?F(n-1)+F(n-2):n # 24 bytes
!n=n>1?!~-n+!(n-2):n     # 20 bytes
!n=n>1?!~-n+!~-~-n:n     # 20 bytes

Try it online!
The redefined operator retains its initial precedence.
Note that we could not simply swap out ! in favor of ~, since ~ is already defined for integers, while ! is only defined for Booleans.
Binary operators
Even without recursion, redefining an operator is shorter than defining a binary function. Compare the following definitions of a simple divisibility test.
f(x,y)=x==0?y==0:y%x==0 # 23 bytes
(x,y)->x==0?y==0:y%x==0 # 23 bytes
x->y->x==0?y==0:y%x==0  # 22 bytes
x\y=x==0?y==0:y%x==0    # 20 bytes

Try it online!
Recursive binary operators
The following illustrates how to redefine a binary operator to compute the Ackermann function:
A(m,n)=m>0?A(m-1,n<1||A(m,n-1)):n+1    # 35 bytes
^ =(m,n)->m>0?(m-1)^(n<1||m^~-n):n+1   # 36 bytes
| =(m,n)->m>0?m-1|(n<1||m|~-n):n+1     # 34 bytes
m\n=m>0?~-m\(n<1||m\~-n):n+1           # 28 bytes

Try it online!
Note that ^ is even longer than using a regular identifier, since its precedence is too high.
As mentioned before
m|n=m>0?m-1|(n<1||m|~-n):n+1           # 28 bytes

would not work for integer arguments, since | is already defined in this case. The definition for integers can be changed with
m::Int|n::Int=m>0?m-1|(n<1||m|~-n):n+1 # 38 bytes

but that's prohibitively long. However, it does work if we pass a float as left argument and an integer as right argument.

Don't be too easily seduced by factor(n) The tempting base library function factor(n) has a fatal flaw: it returns the factorization of your integer in an unordered Dict type. Thus, it requires costly collect(keys()) and collect(values()) and potentially also a cat and a sort to get the data you wanted out of it. In many cases, it may be cheaper to just factor by trial division. Sad, but true.
Use map map is a great alternative to looping. Be aware of the difference between map and map! and exploit the in-place functionality of the latter when you can.
Use mapreduce mapreduce extends the functionality of map even further and can be a significant byte-saver.
Anonymous functions are great! ..especially when passed to the aforementioned map functions.
Cumulative array functions cumprod, cumsum, the flavorful cummin and the other similarly named functions enable cumulative operations along a specified dimension of an n-dimensional array. (Or *un*specified if the array is 1-d)
Short notation for Any When you want to select all of a particular dimension of a multi-dimensional array (or Dict), e.g. A[Any,2], you can save bytes by using A[:,2]
Use the single-line notation for functions Instead of function f(x) begin ... end you can often simplify to f(x)=(...)
Use the ternary operator It can be a space-saver for single-expression If-Then-Else constructions. Caveats: While possible in some other languages, you cannot omit the portion after the colon in Julia. Also, the operator is expression-level in Julia, so you cannot use it for conditional execution of whole blocks of code.
if x<10 then true else false end vs
x<10?true:false

How on Earth is "use the ternary operator" somewhat specific to Julia? It's relevant to every language which has it.

It's relevant that it has it. Many languages also have map, anonymous or pure functions, some kind of shorthand for any/all, cumulative functions, etc. If we were to reduce every tips thread to only the features absolutely unique to that language, there would be very little tips content.

There are probably almost as many languages which don't have comments as there are languages which don't have the ternary operator.

Gosh, only all the functional ones for starters, where everything returns a value so a ternary op would be redundant. If you must have specific examples: Go, Haskell, Scala, Lua, VB, Prolog, PL/SQL...even Python didn't for many versions. Of the near-dozen languages whose tips threads mention their ternary operator is there some reason you only chose to come be provincial in mine?

I haven't seen the others.

Well, hey, at least you're an equal-opportunity curmudgeon. ヘ(￣ー￣ヘ)

let us continue this discussion in chat

Might I suggest adjusting tip 3? mapreduce is longer than either mapfoldl or mapfoldr, and can have varying behaviour depending on implementation. mapfoldl and mapfoldr are left- and right-associative (respectively) consistently, and thus are a better choice. This also applies more generally to reduce (use foldl or foldr).

factor is gone for the standard library

Iterate over functions
This is also possible in other languages, but usually longer than the straightforward method. However, Julia's ability to redefine its unary and binary operators make it quite golfy.
For example, to generate the addition, subtraction, multiplication and division table for the natural numbers from 1 to 10, one could use
[x|y for x=1:10,y=1:10,| =(+,-,*,÷)]

which redefines the binary operator | as +, -, * and ÷, then computes x|y for each operation and x and y in the desired ranges.
This works for unary operators as well. For example, to compute complex numbers 1+2i, 3-4i, -5+6i and -7-8i, their negatives, their complex conjugates and their multiplicative inverses, one could use
[~x for~=(+,-,conj,inv),x=(1+2im,3-4im,-5+6im,-7-8im)]

which redefines the unary operator ~ as +, -, conj and inv, then computes ~x for all desired complex numbers.
Examples in actual contests

Female and Male Sequences (binary)
Case Permutation (unary)

1. Use @b_str to store lists
returning an array of UInt8s (ranging 0-127 in ascii)
for example

[99,100] -- 8 characters
b"cd" -- 5 characters

and using Unicode characters:

b"" -- 4 characters, 7 bytes
[240,159,144,162] -- way more

2. Avoid loops, use .|> or @.
Very often, .|> or broadcasting is shorter:

r=1:n;@.print(r*n^r)
1:n.|>i->print(i*n^i)
@.print((1:n)n^(1:n))
print.((1:n).*n.^(1:n))
[print(i*n^i) for i=1:n]
for i=1:n print(i*n^i)end

3. Choose the right function to override

depending on the number of arguments it can take without parenthesis (useful for recursive functions)

- can take 1 or 2 arguments Try it online!
~ can kinda take 1 or 2 arguments Try it online!
+ can take 1 or more arguments Try it online!
* can take 2 or more arguments Try it online!

depending on their operator precedence

> and < are useful, with a lower precedence than + Example with <
~ has a very low precedence, lower than <, =>, &&... Example
^ has the highest precedence, battling with unary operators (-x^-y == -(x^(-y)))
* has the precedence of an unary operator when the * is omitted (2x^2abs(y)a == 2*(x^(2*abs(y)*a)))

some quirky operators

~ is the only operator that can be placed directly before a = (for example ~=length)

> (and >, ==...) can be splat without parenthesis, ~ also but not in the function definition Try it online!

+ (and *, ++) interprets a+b+c as +(a,b,c) rather than (a+b)+c

< (and >, ==...) has a short-circuiting behaviour Try it online!

4. Some common substitions:

codeunits(s) => [s...], Int[s...], for i=s, [s...].-'\0' Try it online!
sum(a[i]*b[i] for i=1:9) => sum(a.*b) or a'*b Try it online!

r=1:n;@.println(r*n^r) seems to work too, it also beats the other solutions.

Don't type return f(x)=x+4 is identical to but shorter than f(x)=return x+4.  Julia always returns the result of the last statement.
Use = instead of in.  [x for x in 1:4] is 3 characters longer than, but equivalent to [x for x=1:4]

Keywords can sometimes immediately follow constants without the need for a space or semicolon. For example:
n->(for i=1:n n-=1end;n)

Note the lack of a space between 1 and end. This is also true for end occurring after a close paren, i.e. )end.
Perform integer division using ÷ rather than div() or overloading an operator. Note that ÷ is worth 2 bytes in UTF-8.
Use vec() or A[:] (for some array A) rather than reshape() whenever possible.
Create functions rather than full programs when allowed in the challenge rules. It's shorter to define a function which accepts input rather than defining variables by reading from stdin. For example:
n->(n^2-1)
n=read(STDIN,Int);n^2-1

Variables can be incremented inside the argument to a function. For example, the following is my answer to the Find the Next 1-Sparse Binary Number challenge:
n->(while contains(bin(n+=1),"11")end;n)

This is shorter than incrementing n inside of the loop.

Use Broadcasting function calls.
Introduced in Julia 0.5.
It is like map, but uses less characters,
and does broadcasting behavour over it's args -- which means you can write less lambda's to deal with things.
Rather than:

map(f,x) -- 8 characters.
f.(x) -- 5 characters

Better still:

map(a->g(a,y),x) -- 16 characters
g.(x,[y]) -- 9 characters

source: Stack Exchange

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

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

sort: votes


text:
St. Patrick's Day Challenge!
Seeing as its St. Patrick's day, I thought I would have a little challenge
Your task is to write a program draws a clover in any way possible. Each leaf has to be symmetrical, and the user has to input the number of leaves that they want on the clover. It then must be drawn. This has to be generated. You cannot just load an image or have ASCII art saved as a variable. However using modules like turtle to generate (and draw is included under generate) are fine.
You can use any language. This is a code-golf so the shortest answer wins.
Begin! Happy St Patrick's Day!
Just for reference, here is an example of a 3 leaf clover
Just for DavidCarraher

Also, you might want to specify a shamrock instead of a clover!

Mathematica - 106 bytes
c=RegionPlot[x^2+y^2<Abs@Sin[#x~ArcTan~y/2]||x>0&&y^2<.001,{x,-1,1},{y,-1,1},Frame->0>1,PlotStyle->Green]&

Ungolfed version:
c[leaves_] := (
    angle = ArcTan[x,y];
    RegionPlot[
        x^2 + y^2 < Abs[Sin[leaves*angle/2]]
        || x > 0 && y^2 < .001
      , {x,-1,1}
      , {y,-1,1}
      , Frame -> False, PlotStyle -> Green
    ]);

Here are the outputs for c[3] through c[6].

At the cost of another 7 bytes you can improve the colour (using PlotStyle->Darker@Green or PlotStyle->Hue[.3,1,.7] instead), and for another 15 bytes you can remove some of the sampling artifacts (using an additional option ,PlotPoints->90), giving a total of 128 bytes for these beauties:

The braces and commes in those pictures are not produced by c, but just by how I output them to fit them all in one row.
Lastly, here is an attempt at somewhat neater shading. I didn't even bother golfing this down further, the option names are just too long. I'm not even sure I'm too pleased with the result, but I thought I'd post it anyway. This is 188 bytes as it stands:
c=RegionPlot[x^2+y^2<Abs@Sin[(l=#)x~(a=ArcTan)~y/2]||x>0&&y^2<.001,{x,-1,1},{y,-1,1},Frame->0>1,PlotPoints->90,ColorFunction->(Hue[.3,1,.5+.2Sin[.5l#~a~#2]^8]&),ColorFunctionScaling->0>1]&

Your Abs[] has no closing bracket

let's see a 3d version too?

@MichaelStern tempting :) ... but maybe some other time... I just spent my entire free time for today on another answer ^^

C (145 126)
float d=2/--r,x,y=-1;for(;y<=1;y+=d,puts(""))for(x=-1;x<=1;x+=d)putchar(x*x+y*y<fabs(sin(l*atan2(x,y)))||fabs(x)<d&y>0?35:32);

Draws a clove in ASCII art; the function is passed the number of desired leaves and the resolution in characters. See example here: http://ideone.com/YDGN4H
Note that the result is much nicer when the horizontal resolution is doubled, at the cost of a slightly more verbose code (see http://ideone.com/RYaLz4).
Full version:
#include <math.h>
#include <stdio.h>

void clover(float l, float r)
{
    float d = 2.f / --r;
    float x, y=-1.f;
    for (; y<=1.f; y+=d){
        for (x=-1.f; x<=1.; x+=d){
            printf((x*x + y*y < fabs(sin(l * atan2(x,y))) | (fabs(x) < d & y > 0)) ? "#" : " ");
        }
        printf("\n");
    }
}

int main(int argc, char* argv[])
{
    clove(4.f, 48.f);
    return 0;
}

Best use of variables names l and r!

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


text:
Display the explosion of a star in ASCII-art
The goal is to animate a star exploding in ASCII art, starting from a single star character * to a supernovae and finally to the space void.
Rules :

You have to display only 80 characters per line on 24 lines (this is
the default terminal size on Linux)
Only these 95 printable characters from ASCII are allowed
Steps:

The initial star must be * and centred horizontally and vertically
The star has to grow to show that it explodes
At the end the screen must be empty (the star has disappeared)

Length of the code or languages are irrelevant
Votes will decide of the most creative and beautiful results. Have you ever seen an exploding star? Let's see how you imagine this.

I've added an answer using Python as an example, but you're encouraged to create something different or better.
You have one week to participate, the winner will be chosen on 2014-04-01.
Samples of output (with some frames only):
# start

                                        *

# during explosion

                                    ****#****
                                 ***#@##*#@#****
                               *@**@@@*##**#*#**#*
                              **@@*#**#@*#@****#***
                              ****@*@***#****@**@@*
                             *******@***@@***#****#*
                              *#***#*##@****##@@@**
                              **#@###****@*********
                               *****@**@*@*****@**
                                 ************@**
                                    ****#****

# star is expanding

                                        *
                               ********* **@******
                           ****   **#**@ #**#*#   ****
                         ***  **  **##** *@@*@*  **  ***
                       **  *  @@   *@*#* ***@*   *#  *  **
                     *** #  *  *#  *@#** ***@*  **  @  * *@*
                    ** *  * ** *@  ****@ @****  ** #* *  * **
                   ** * @* * ** *@  #### *#**  ** ** * @* * **
                  *# * # ** * #* *  **** ****  @ ** * ** * * #*
                 ** * *# * @ * #  @  @*@ *#*  *  @ # # * @* * **
                 *# * * * * # * @* * **# *#* * ** * * * * * # **
                 ** # * * @ * * # * # ** @* * * * * * # @ @ * **
                *# * * * * * * * * # * * * * * * @ @ * * * * * **
                 *# * @ * @ * @ * * * ** *@ * * # * * * * * @ @*
                 *# # @ * * # * *@ * *** @#@ @ ** * @ @ * * # **
                 *# * ** * * * @  @  **@ ***  *  @ * * * @* * #*
                  ** * * ** * #@ *  #*** **##  * #* * #@ * * @*
                   *# * *@ * @@ *#  **** @***  ** ** * #* * #*
                    *# *  * *@ **  @**@* *@#**  ** ** *  * @*
                     *#* @  *  @@  **##* ****@  **  #  * @**
                       **  @  #*   @*@#* @*@*#   @#  *  **
                         *#*  @*  @#*@*# **#*@#  **  ***
                           ****   *##**# #***@*   @***
                               ****@**@* *****@***

# star is disappearing

               *  -  -  --  --   ------- -------   --  --  -  -  *
             ** -  -  -  --  --   ------ ------   --  --  -  -  - **
            * -- - -- -- --  --   ------ ------   --  -- -- -- - -- *
          ** - -  - -- -- --  --  ------ ------  --  -- -- -- -  - - **
         *  - - -- - -- -  -  --   ----- -----   --  -  - -- - -- - -  *
        ** - - - -- - -- -  -  --  ----- -----  --  -  - -- - -- - - - **
        * - - - -  - - -  - -- --  ----- -----  -- -- -  - - -  - - - - *
       * - - - -  - - - -- - -- --  ---- ----  -- -- - -- - - -  - - - - *
      * -- - - - - - - - -- - -- -  ---- ----  - -- - -- - - - - - - - -- *
      * - - - - - - - -- - - - -  -  --- ---  -  - - - - -- - - - - - - - *
      * - - - - - - - - - - - - -- - --- --- - -- - - - - - - - - - - - - *
      * - - - - - - - - - - - - - - - -- -- - - - - - - - - - - - - - - - *
     * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *
      * - - - - - - - - - - - - - - - -- -- - - - - - - - - - - - - - - - *
      * - - - - - - - - - - - - -- - --- --- - -- - - - - - - - - - - - - *
      * - - - - - - - -- - - - -  -  --- ---  -  - - - - -- - - - - - - - *
      * -- - - - - - - - -- - -- -  ---- ----  - -- - -- - - - - - - - -- *
       * - - - -  - - - -- - -- --  ---- ----  -- -- - -- - - -  - - - - *
        * - - - -  - - -  - -- --  ----- -----  -- -- -  - - -  - - - - *
        ** - - - -- - -- -  -  --  ----- -----  --  -  - -- - -- - - - **
         *  - - -- - -- -  -  --   ----- -----   --  -  - -- - -- - -  *
          ** - -  - -- -- --  --  ------ ------  --  -- -- -- -  - - **
            * -- - -- -- --  --   ------ ------   --  -- -- -- - -- *
             ** -  -  -  --  --   ------ ------   --  --  -  -  - **

# the star is gone

(there is nothing)

Animated example of output:

If you want some inspiration, you can look at an explosion from Captain Blood, a game from 1988.

There isn't really a spec here to determine whether an answer is "correct" or not.

I'm removing the word correct from the question. The most popular answer will be declared as the winner.

Whether the word is in the question or not, all questions should have a clear spec against which answers can be measured.

Is "display something which look like the output examples, but feel free to be creative and artistic" enough? I can add more rules (time, number of frames, sizes, etc.) but I'm pretty sure it will make it less interesting.

Please explain if the rules are not clear enough and how I can improve them.

If I could see a way to improve them, I would have suggested it; the only thing which has occurred to me so far is to provide detailed references to the evolution of a supernova against which to judge the submissions. But while it's easy to find a graph of the magnitude evolution, I can't find much about the diameter evolution. The best I've found so far is some Hubble images.

C + curses

I haven't made much of an effort to tidy up the source code. Basically it calculates an expanding shock wave, with a solid background added to the first few frames to give a sort of flash effect. [[EDIT: The explosion looked a bit odd appearing from a single asterisk, so I added a few frames of expansion at the beginning of the animation.]]
Random particles are superimposed on top of this, with positions determined according to a basic perspective calculation to give it a slightly 3D feel. (Well that was the idea, anyway.)
#include <curses.h>
#include <stdlib.h>
#include <math.h>

#define NUM_FRAMES 150
#define NUM_BLOBS 800
#define PERSPECTIVE 50.0

typedef struct {
  double x,y,z;
} spaceblob;

double prng() {
  static long long s=1;
  s = s * 1488248101 + 981577151;
  return ((s % 65536) - 32768) / 32768.0;
}

int main() {
  char *frames[NUM_FRAMES], *p;
  int i,j,x,y,z,v,rows,cols,ith,i0;
  int maxx,minx,maxy,miny,delay=1E6;
  double bx,by,bz,br,r,th,t;
  spaceblob *blobs;

  /* Initialize ncurses and get window dimensions */
  initscr();
  getmaxyx(stdscr,rows,cols);
  minx = -cols / 2;
  maxx = cols+minx-1;
  miny = -rows / 2;
  maxy = rows+miny-1;

  /* Generate random blob coordinates */
  blobs = malloc(NUM_BLOBS * sizeof(spaceblob));
  for (i=0; i<NUM_BLOBS; i++) {
    bx = prng();
    by = prng();
    bz = prng();
    br = sqrt(bx*bx + by*by + bz*bz);
    blobs[i].x = (bx / br) * (1.3 + 0.2 * prng());
    blobs[i].y = (0.5 * by / br) * (1.3 + 0.2 * prng());;
    blobs[i].z = (bz / br) * (1.3 + 0.2 * prng());;
  }

  /* Generate animation frames */
  for (i=0; i<NUM_FRAMES; i++) {
    t = (1. * i) / NUM_FRAMES;
    p = frames[i] = malloc(cols * rows + 1);
    for (y=miny; y<=maxy; y++) {
      for (x=minx; x<=maxx; x++) {

        /* Show a single '*' in first frame */
        if (i==0) {
          *p++ = (x==0 && y==0) ? '*' : ' ';
          continue;
        }

        /* Show expanding star in next 7 frames */
        if (i<8) {
          r = sqrt(x*x + 4*y*y);
          *p++ = (r < i*2) ? '@' : ' ';
          continue;
        }

        /* Otherwise show blast wave */
        r = sqrt(x*x + 4*y*y) * (0.5 + (prng()/3.0)*cos(16.*atan2(y*2.+0.01,x+0.01))*.3);
        ith = 32 + th * 32. * M_1_PI;
        v = i - r - 7;
        if (v<0) *p++ = (i<19)?"%@W#H=+~-:."[i-8]:' '; /* initial flash */
        else if (v<20) *p++ = " .:!HIOMW#%$&@08O=+-"[v];
        else *p++=' ';
      }
    }

    /* Add blobs with perspective effect */
    if (i>6) {
      i0 = i-6;
      for (j=0; j<NUM_BLOBS; j++) {
        bx = blobs[j].x * i0;
        by = blobs[j].y * i0;
        bz = blobs[j].z * i0;
        if (bz<5-PERSPECTIVE || bz>PERSPECTIVE) continue;
        x = cols / 2 + bx * PERSPECTIVE / (bz+PERSPECTIVE);
        y = rows / 2 + by * PERSPECTIVE / (bz+PERSPECTIVE);
        if (x>=0 && x<cols && y>=0 && y<rows)
          frames[i][x+y*cols] = (bz>40) ? '.' : (bz>-20) ? 'o' : '@';
      }
    }

    /* Terminate the text string for this frame */
    *p = '\0';
  }

  /* Now play back the frames in sequence */
  curs_set(0); /* hide text cursor (supposedly) */
  for (i=0; i<NUM_FRAMES; i++) {
    erase();
    mvaddstr(0,0,frames[i]);
    refresh();
    usleep(delay);
    delay=33333; /* Change to 30fps after first frame */
  }
  curs_set(1); /* unhide cursor */
  endwin(); /* Exit ncurses */
  return 0;
}

That's nice! Can you please explain how you captured the terminal images? I think you should reduce the part when you're typing, if you haven't added it for teasing the viewer.

@n.1 You're right -- it was dragging on a bit. I use IShowU to capture the screen, and export the frames from QuickTime to ImageMagick to create an animated GIF, and then use Gifsicle to optimise the GIF animation. It's a bit of a palaver, really. Let me know if you've found a better method.

Javascript
Thought it was worth a shot in JS.  Suggest saving and running; very very slow if you paste in console.
var boomboom = (function() {
    //Clear any existing page
    document.getElementsByTagName("body")[0].innerHTML="";

    var space=document.createElement("div");
    var iterator=0;
    var stars = 50;
    var timer=100;

    //Set container
    space.setAttribute("id","space");
    space.setAttribute("style","width:1000px;height:600px;margin:auto;border:solid 1px #000;position:relative;overflow:hidden;background:#000;color:#fff");
    document.getElementsByTagName("body")[0].appendChild(space);

    //Set interval and draw...
    var interval = setInterval(function(){ drawStars(iterator,stars); }, timer);
    drawStars(iterator, stars);

    function drawStars(r,c) {
        clearInterval(interval);

        //a container for this set of stars
        var starContainer=document.createElement("div");

        //don't draw more if there are too many, it's got to go
        if(iterator < 1000) {
            for(var i = 0; i < c; i++) {
                var x,y;

                if(iterator < 100) {
                    x=500 + r * Math.cos(2 * Math.PI * i / c) * 0.7;
                    y=300 + r * Math.sin(2 * Math.PI * i / c) * 0.7;
                }

                //add some randomness for the boom boom
                if(iterator > 100) {
                    x=500 + r * Math.cos(2 * Math.PI * i / c) * 0.7*Math.random();
                    y=300 + r * Math.sin(2 * Math.PI * i / c) * 0.7*Math.random();
                }

                //Make a star
                var star=document.createElement("div");
                star.setAttribute("class","star");

                //Exploding stars are red, I hope
                var color = iterator < 100 ? "color:#fff" : "color:rgb("+parseInt(255*Math.random())+",0,0)";
                star.setAttribute("style","position:absolute; left:"+ x +"px;top:"+ y +"px;"+color);

                //Change the star character as boom boom gets bigger
                if(iterator <= 200) {
                    star.innerText="*";
                }
                else if(iterator >=200 & iterator <= 400) {
                    star.innerText="O";
                }
                else  {
                    star.innerText="-";
                }
                //Add the star to its container
                starContainer.appendChild(star);
            }
        }
        //draw the container
        space.appendChild(starContainer);

        //increment the iterator.  It's an iterator because we're using intervals and it's late.
        iterator+=5;

        //remove stars when we get too many
        if(iterator > 200) {
            space.removeChild(space.firstChild);
        }
        if(iterator < 1500) { //do it all again
            timer = timer > 10 ? timer-10 : timer;
            interval=setInterval(function(){ drawStars(iterator,stars); }, timer);
        }

        //make sure it's actually empty
        else {
            space.innerHTML="";
        }
    }
}());

Edits
In JSBin: http://jsbin.com/worofeqi/5/watch?js,output
Oddly runs much more smoothly when done from local file system than in JSBin.  Honestly not sure why; may look at that this evening.

Can you please place it on jsfiddle, jsbin or another website where we can see easily? When adding the question I only thought about displaying the result in a terminal but I won't update the rules now that you've added your answer, I should have added this rule before.

Answer updated (note the (very odd) caveat)

Python
#!/usr/bin/python

import sys, math, time, random

def distance(x, y):
    # ((y - y_center) * 2) -> correct ratio for a true circle
    return math.ceil(math.sqrt(((x - 40) ** 2) + (((y - 12) * 2) ** 2)))

def star(radiuses):
    for r in radiuses:
        #~ clear screen: http://stackoverflow.com/a/2084521/2257664
        print chr(27) + "[2J"

        # width
        for y in range(24):
            # height
            for x in range(80):
                d = distance(x, y)

                #~ border
                if (d == r):
                    sys.stdout.write('*')
                #~ inside the star
                elif (d < r):
                    if (r > 35):
                        sys.stdout.write(' ')
                    elif (r > 25) and ((d % 2) != 0):
                        sys.stdout.write('-')
                    elif (r > 15) and ((d % 2) == 0):
                        sys.stdout.write(' ')
                    else :
                        sys.stdout.write(random.choice('****#@'))
                #~ space outside the star
                else:
                    sys.stdout.write(' ')
            print
        time.sleep(0.1)

star(range(0, 12) + range(10, 0, -1) + range(0, 50))

Example output (using less steps and without clearing the screen).
Excerpts of the output are also displayed in the question.


text:
compare string without conditional operator
Compare if three string variables with the same content, return true if they are or false if they are not without using conditional operators and bitwise operators.
e.g. in C# without && || ?:
return  (string1==string2)==(string1==string3)==true;

PS: initial idea came from these question

Popularity contests shouldn't get the [tag:code-challenge] tag. I've removed that tag.

How about just... if(string1==string2)return string2==string3;return false

Many thanks @ProgramFOX, I'm new to PCG

Also, I think it's a good idea to ban bitwise operators. true & true is actually the same as true && true.

@mniip, I think your code is valid, just less interesting :)  Anyway, I'm not 100% sure if this question can raise any interesting answers at all. But I'm keen to find out and hence the question..

Trivial variant on Determine if Strings are equal

@PeterTaylor: It's not a duplicate, because that question doesn't allow the == operator and similar, but this question doesn't allow operators like conditional operators and bitwise operators such as &&.

@ProgramFOX, && isn't a bitwise operator; few of the 63 answers to that question can't be trivially adapted to this one.

@PeterTaylor: I know && is not a bitwise operator. I actually meant to give && as an example to "conditional operators". Unfortunately, I can't edit it anymore.

@ProgramFOX, it's a Boolean operator. The only operator which I can find anyone describing as a conditional operator is ?:.

GolfScript
1$=:a;=a+2="true""false"if

This program assumes three strings on the stack.
Test online
How it works:

1$ copies the second element on the stack (the second string) to the top of the stack.
=:a; returns 1 if the two top elements (the second and the third string) are equal; otherwise, 0. Then, it stores this result in the variable a and it pops it from the stack. Now only the first and the second string remain on the stack.
= checks whether the first and the second string are equal.
a+ puts the value of a on the stack and calculates the sum of a and the result of the previous comparison.
2="true""false"if puts "true" on the stack if the sum of the comparison results is equal to 2: in this case, both comparisons returned true. If the sum is 1 or 0 then it puts "false" on the stack. This value is now the only one on the stack, and at the and of a program, GolfScript always outputs the values on the stack.

[Edit]
Thanks to Peter Taylor for pointing out that variables are not necessary:
1$=@@=+2="true""false"if

You don't need a variable. @@ will push the top item on the stack down two. (And since idiomatic GolfScript is golfed, I prefer my answer to the question which I claim this one duplicates. Just change ( to a suitable comparison).

@PeterTaylor: Thank you, I have updated my answer.

Perl
The function CompareStrings takes any number of strings and returns the strings true or false:

true is returned if there are one or more strings and all strings are equal.
false is returned if there is no string or at least two different strings.

sub CompareStrings (@) {
    my %hash = map { $_ => 1 } @_;
    return ('false', 'true')[not scalar(keys %hash) - 1];
}

The strings are put as keys in a hash. If there is at least one string and all strings are equal, then the hash has one key exactly. Otherwise there are zero or two or more keys. After 1 is subtracted the operator not maps the cases to the empty string and 1 that are used to select the result string (the empty string becomes 0).
sub CompareStrings (@) {
    my %hash = map { $_ => 1 } @_;
    return ('false', 'true')[not scalar(keys %hash) - 1];
}

Complete script with test cases:
#!/usr/bin/env perl
use strict;
$^W=1;

sub CompareStrings (@) {
    # several variants to initialize the hash, whose keys are the strings:
    # my %hash; @hash{@_} = (1) x @_;
    # my %hash; $hash{$_} = 1 for @_;
    my %hash = map { $_ => 1 } @_;
    return ('false', 'true')[not scalar(keys %hash) - 1];
}

# Testing

$\ = "\n";
print CompareStrings qw[];                  # false
print CompareStrings qw[foobar];            # true
print CompareStrings qw[hello hello];       # true
print CompareStrings qw[Hello World];       # false
print CompareStrings qw[abc abc abc];       # true
print CompareStrings qw[abc abc def];       # false
print CompareStrings qw[abc def ghi];       # false
print CompareStrings qw[a a a a a a a a];   # true
print CompareStrings qw]a a a a oops a a];  # false

__END__


text:
Calculate practical numbers
Definition
A positive integer n is a practical number (OEIS sequence A005153) iff all smaller positive integers can be represented as sums of distinct divisors of n.
For example, 18 is a practical number: its divisors are 1, 2, 3, 6, 9, and 18, and the other positive integers smaller than 18 can be formed as follows:
 4 = 1 + 3          5 = 2 + 3           7 = 1 + 6
 8 = 2 + 6          10 = 1 + 9         11 = 2 + 9
12 = 3 + 9 = 1 + 2 + 9 = 1 + 2 + 3 + 6
13 = 1 + 3 + 9      14 = 2 + 3 + 9      15 = 6 + 9
16 = 1 + 6 + 9      17 = 2 + 6 + 9

But 14 is not a practical number: its divisors are 1, 2, 7, and 14, and there's no subset of these which adds to 4, 5, 6, 11, 12, or 13.
Challenge
Write a program, function, or verb which takes as input a positive integer x and either returns or prints the xth practical number, indexed from 1 for consistency with OEIS. Your code must be sufficiently efficient that it can handle inputs up to 250000 in less than two minutes on a reasonable desktop computer. (NB my reference implementation in Java manages 250000 in less than 0.5 seconds, and my reference implementation in Python manages it in 12 seconds).
Test cases
Input        Expected output
1            1
8            18
1000         6500
250000       2764000
1000000      12214770
3000000      39258256

(IMHO) this can be even move interesting if the fastest code (per language?) wins

@SargeBorsch So you'll see tables of 250K entries all over the answers

@belisarius good point. but I think such cheating can be easily banned. Or the problem may require correct answers for any number, but then there would be difficulties when doing it in a language with no big integers in the standard library... :/

I have one algorithmic optimization in mind, but with current rules I'm too lazy to implement it :P

@SargeBorsch, if you don't want to golf your code feel free to upload it to something like gist.github.com and drop a link in a comment here or in chat. FWIW I prefer code golf with generous performance constraints to fastest code for two reasons: firstly, the length of the code is more objectively measurable; secondly, it introduces an element of tradeoff: which speed optimisations can be left out in order to shorten the code without ruining the performance?

J (99 chars)
f=:3 :0
'n c'=.0 1
while.c<y do.
'p e'=.__ q:n=.n+2
c=.c+*/(}.p)<:}:1+*/\(<:p^e+1)%<:p
end.
n+n=0
)

Since the problem statement asks for a "program, function or verb", someone had to make a J submission. J people will notice I didn't really golf (!) or optimize this. Like the other entries, I used Stewart's theorem, mentioned at the OEIS link, to test whether each even number is practical or not.
I don't have ready access to a "reasonable desktop computer" with J installed. On my six year old netbook f 250000 computes in 120.6 seconds, which is not quite under two minutes, but presumably on any slightly more reasonable computer this finishes in time.

Mathematica, 126 121 chars
Thanks to belisarius.
Using the formula on wikipedia.
f=(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&

Examples:
f[1]

1

f[8]

18

f[250000]

2764000

It took 70s to compute f[250000] on my computer.

I think you can get better performance at the expense of one char by bypassing odd integers

In reducing the code from the OEIS submission, you slowed down the execution 10-fold.  Just wondering, "why do you think your code runs so much slower than the OEIS example?"

@belisarius Your suggestion cuts the time in half, as expected.

The same in 119 chars: (i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&

Haskell - 329
s 1=[]
s n=p:(s$div n p)where d=dropWhile((/=0).mod n)[2..ceiling$sqrt$fromIntegral n];p=if null d then n else head d
u=foldr(\v l@((n,c):q)->if v==n then(n,c+1):q else(v,1):l)[(0,1)]
i z=(z<2)||(head w==2)&&(and$zipWith(\(n,_)p->n-1<=p)(tail n)$scanl1(*)$map(\(n,c)->(n*n^c-1)`div`(n-1))n)where w=s z;n=u w
f=((filter i[0..])!!)

Examples:
> f 1
1
> f 13
32
> f 1000
6500

Here's a small testing suite (prepend to the above):
import Data.Time.Clock
import System.IO

test x = do
    start <- getCurrentTime
    putStr $ (show x) ++ " -> " ++ (show $ f x)
    finish <- getCurrentTime
    putStrLn $ " [" ++ (show $ diffUTCTime finish start) ++ "]"

main = do
    hSetBuffering stdout NoBuffering
    mapM_ test [1, 8, 1000, 250000, 1000000, 3000000]

Test results after being compiled with ghc -O3:
1 -> 1 [0.000071s]
8 -> 18 [0.000047s]
1000 -> 6500 [0.010045s]
250000 -> 2764000 [29.084049s]
1000000 -> 12214770 [201.374324s]
3000000 -> 39258256 [986.885397s]

When I try this in ghci it complains parse error on input \='`. Do I need to use some flag or other?

@PeterTaylor You cannot paste function definitions into ghci like that. Simplest you can do is save it to asdf.hs and run ghci asdf.hs, then from there you would be able to access f

@PeterTaylor ghc --make -O3 [filename]. You could also load it in ghci with :l [filename] but given the time constraints compiled is probably best. :)

@JonathanVanMatre as seen in the above comment, ghci loads files specified in its arguments

Ah, ok. In the meantime I've got it running with your test framework and ghc. Your computer's faster than mine, but it's still soundly inside the performance criterion on my computer at 98 seconds.

Haha, jinx @mniip! Anyway, I got 250k in 22s with this in my system. ETA: Yeah, I know you can use arguments but since Peter was trying to paste it in I was suggesting the closest analogue to that.

Javascript, 306 307 282B
function y(r){for(n=r-1,k=1;n;k++)if(p=[],e=[],c=0,P=s=1,!((x=k)%2|1==x)){while(x>1){for(f=x,j=2;j<=Math.sqrt(f);j++)if(f%j==0){f=j;break}f!=p[c-1]?(p.push(f),e.push(2),c++):e[c-1]++,x/=f}for(i=0;c>i;i++){if(p[i]>P+1){s=0;break}P*=(Math.pow(p[i],e[i])-1)/(p[i]-1)}s&&n--}return k-1}

250k in approx. 6s on my laptop.
Commented un-golfed code: http://jsfiddle.net/82xb9/3/ now with better sigma-testing and a better if condition (thank you comments)
Pre-edit versions: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/

The question does ask for a function or program (JS doesn't have verbs), so rather than not counting the first line you should wrap the second line in a function declaration and replace the final k--; with return k-1. Although that increases your byte count slightly, you can save a few with things like replacing p[i]>=P+2 with p[i]>P+1 (and probably by removing the internal function call and using a break instead).

I think "testing sigma" part can be re-written for both size and speed: http://jsfiddle.net/3DTSa/ . Though this JS solution is very fast as it is.


text:
A golfed golfing game
You have to make a golf game with the following specification :-

The field is 10 X 10 characters without spaces.

Free ground is represented by .

A hole generated at random(not at 0,0) is shown by O (its alphabet and not zero).

The ball starts at 0,0 represented by X.

You can hit the ball with input d 4 (meaning direction to the bottom with magnitude of 4 characters after the ball more like vectors in physics).
Example:
X.........
..........
..........
..........
..........
..........
..........
..........
..........
.........O
score : 0
b 4

But, since you are not so good at golfing therefore the force you think is applied is often only close to the actual force that is applied !(if x the offset in force then -2 < X < +2)

you should have to tell the real force applied and display the ball moved to that real force like this :-
lets say the ball actually moved by 3.

..........
..........
..........
X.........
..........
..........
..........
..........
..........
.........O
score : 1
applied force : 4
real force    : 3

The four directions are U (up), D (down), l (left), r (right) and magnitude of force should be between 0 and 10 (excluding both 0 and 10).

The ball should not bounce off the edges, if the force reaches that much then the the ball stops at the last point at the boundary.
r 9

..........
..........
..........
.........X
..........
..........
..........
..........
..........
.........O
score : 2
applied force : 9
real force    : 11

In the end when the game is finished you have to display Par in <n> shots! (where n is score)

Coding:

You have to design a working program showing the exact output.
post the code in golfed and ungolfed versions.
also post a successful test run (images if possible).
No use of functions or languages excessively specialized to this task (I don't know if they really exist!)

Winner:
Winner will be chosen 1 week from now.
Winner is the submission with least characters.
And, most important thing
Best of luck :)

I would like to see the reasons of up-votes(because I don't know why I got up-votes and how will I keep it up) or down-votes(Obviously to improve).Also, please don't answer my question if it has down-votes.

@the downvoter Please explain the reason of your down-vote!

"you are not so good at golfing" seems like an understatement if I can aim to hit the ball (e.g. D 1) and not move it at all (X=-1). Most of the spec is intelligible, but you haven't said what to do if a) the intended stroke would place the ball out of bounds; b) the intended stroke wouldn't, but with X taken into account it would.

This is woefully underspecified. Physics challenges are tough. The obvious loophole here has nothing to do with physics, though: you haven't required that the force applied must be randomized, and you have explicitly requested that the force not be displayed. Consequently, instead of an elementary physics simulation you are likely to get the golfiest approach to displaying the output field with one character replaced by an O.

@PeterTaylor I made some edits please reconsider my question(from point 6), if there's anything else I would like to know

I think you've misunderstood the purpose of my comment. I wasn't the downvoter explaining the reason: just someone commenting on an incomplete spec. FWIW I think you've plugged the hole.

I agree, much better now!

If the calculated force is negative what do we do? I.e I aim to hit 1, I get a -2 accuracy additor and get -1. The ball goes backwards?

@LegoStormtroopr "magnitude of force should be between 0 and 10 (excluding both 0 and 10)" bounds the force offset.

@LegoStormtroopr yes! that is also part of this game

@JonathanVanMatre thought 0 was ok for applied force since 0<input<10 and -2<x<2 results in 0<=applied force<=10 and our field is 10 spaces long. Of course you need to be lucky if you need to go 10 spaces as you can only input 9.

@TheConstructor While it is admittedly still a little unclear in the question text itself, OP added the 0 < actual force < 10 in response to Peter noting above that negative or zero force was possible. Thus, it is safe to assume that the 0 < af <10 constraint is to be applied after the desired force has been offset by the -2<variance<2 offset. i.e. final force should always be between 1 and 9 inclusive.

K, 319 305 308
{b:(10*!-_-(100)%10)_@[100#".";0,1?100;:;"XO"];c:0 0;e:s:-1;while["O"in,/b;e@b;e"Score : ",$s+:1;h:"SI"$" "\:0:0;h[1]:1|*(w:h 1)+1?-2+!5;b:.[;;:;]/[b;(c;d:9&((`r`d`l`u!({(0,x)+};{(x,0)+};{(0,-x)+};{(-x,0)+}))[h 0]h 1)c);".X"];c:d;e"Applied force : ",$w;e"Real force    : ",$h 1];e"Par in ",($1+s)," shots!";}

Could definitely golf this more. Incrementing/decrementing the indices is what kills me and could probably be done much simpler.
(Slightly) more readable than the one liner:
golf:{[]
    b:(10*!-_-(100)%10)_@[100#".";0,1?100;:;"XO"];
    c:0 0;e:s:-1;
    while["O"in,/b;
        e@b;
        e"Score : ",$s+:1;
        h:"SI"$" "\:0:0;
        h[1]:1|*(w:h 1)+1?-2+!5;
        b:.[;;:;]/[b;(c;d:9&((`r`d`l`u!({(0,x)+};{(x,0)+};{(0,-x)+};{(-x,0)+}))[h 0]h 1)c);".X"];
        c:d;
        e"Applied force : ",$w;
        e"Real force    : ",$h 1];
    e"Par in ",($1+s)," shots!";
    }

.
k)golf[]
X.........
..........
..........
..........
.......O..
..........
..........
..........
..........
..........
Score : 0
d 4
Applied force : 4
Real force    : 4
..........
..........
..........
..........
X......O..
..........
..........
..........
..........
..........
Score : 1
r 7
Applied force : 7
Real force    : 5
..........
..........
..........
..........
.....X.O..
..........
..........
..........
..........
..........
Score : 2
r 2
Applied force : 2
Real force    : 1
..........
..........
..........
..........
......XO..
..........
..........
..........
..........
..........
Score : 3
r 1
Applied force : 1
Real force    : 1
Par in 4 shots!

Won't change the current outcome, but the colons for the two force lines should be aligned. Congrats!

@Jonathan - made the change for an extra 3 chars.

Scala, 605
Golfed:
import scala.util.Random;object G extends App{var b,h=(0,0);while(b==h)h =(Random.nextInt(10),Random.nextInt(10));var s=0;def f{for(y<- 0 to 9){for(x<- 0 to 9)print(if(b==(x,y))"X"else if(h==(x,y))"O"else ".");println};println("score : "+s)};f;while(b!=h){val i=readLine.split(" ");val x=i(1).toInt.ensuring(a=>a>0&&a<10)-1+Random.nextInt(3);b=i(0).toLowerCase match{case "d"=>(b._1,b._2+x) case "u"=>(b._1,b._2-x) case "r"=>(b._1+x,b._2) case "l"=>(b._1-x,b._2)};b=(b._1.min(9).max(0),b._2.min(9).max(0));s+=1;f;println("applied force : "+i(1));println("real force : "+x)};println("Par in "+s+" shots!")}

Just a straight-forwardly implemented ice-breaker. Input is read line-by-line from stdin and power lower then 1 or higher then 9 will result in an AssertionError to comply with the specs.
I am pretty sure there are shorter programs, but let's see how far we get ;-)
Ungolfed:
import scala.util.Random

object Golf extends App {
  var b, h = (0, 0)
  while (b == h) h = (Random.nextInt(10), Random.nextInt(10))
  var s = 0

  def field {
    for (y <- 0 to 9) {
      for (x <- 0 to 9)
        print(if (b ==(x, y)) "X" else if (h ==(x, y)) "O" else ".")
      println
    }
    println("score : " + s)
  }
  field
  while (b != h) {
    val i = readLine.split(" ")
    val x = i(1).toInt.ensuring(a => a > 0 && a < 10) - 1 + Random.nextInt(3)
    b = i(0).toLowerCase match {
      case "d" => (b._1, b._2 + x)
      case "u" => (b._1, b._2 - x)
      case "r" => (b._1 + x, b._2)
      case "l" => (b._1 - x, b._2)
    }
    b = (b._1.min(9).max(0), b._2.min(9).max(0))
    s += 1
    field
    println("applied force : " + i(1))
    println("real force : " + x)
  }
  println("Par in " + s + " shots!")
}

Random example run:

X......O..
..........
..........
..........
..........
..........
..........
..........
..........
..........
score : 0

r 8
.......OX.
..........
..........
..........
..........
..........
..........
..........
..........
..........
score : 1
applied force : 8
real force : 8

l 1
.......OX.
..........
..........
..........
..........
..........
..........
..........
..........
..........
score : 2
applied force : 1
real force : 0

l 1
.......X..
..........
..........
..........
..........
..........
..........
..........
..........
..........
score : 3
applied force : 1
real force : 1
Par in 3 shots!

Sorry for the delay in choosing the answer!

@MukulKumar no problem. still I am a bit surprised I got the accepted answer :D

OH MY GOD!!! WHAT DID I DO I thought this is popularity-contest ......sorry pal.

Julia, 427
This is pretty straightforward on the whole. Julia isn't really designed to deal with I/O very heavily, as she's intended for large-scale scientific computation. But for our limited purposes here, she obliges by accepting some STDIO and playing a little game of golf with us.
Edit: charged myself two additional characters because I had omitted the spaces after the colon for applied force and real force.
a=fill(".",10,10)
x,y,s,b,c=1,1,0,iceil(10rand()),iceil(10rand())
a[x,y],a[b,c]="X","O"
while(x,y)!=(b,c)
print(a)
m=readline(STDIN)
d,f=m[1],m[2]
o=(d in"Ul"?-1:d in "Dr"?1:0)
g=clamp(round((f-48)+4rand()-2),1,9)*o
a[x,y]="."
x,y=(d in "UD"?clamp(x+g,1,10):x),(d in "lr"?clamp(y+g,1,10):y)
a[x,y]="X"
s+=1
print("score : ",s,"\napplied force : ",f,"\nreal force    : ",abs(g),"\n")
end
print(a,"\nPar in ",s," shots!")

Here's a sample game, in which the final putt becomes an increasingly trying situation for our golfer.
(Note that occasionally our Ints get converted to Floats on the fly...ah, the vagaries of dynamic typing.)
X . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . O . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
STDIN> r5
score : 1
applied force : 5
real force    : 7.0
. . . . . . . X . .
. . . . . . . . . .
. . . . . . . . . .
. . . . O . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
STDIN> D3
score : 2
applied force : 3
real force    : 2.0
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . X . .
. . . . O . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
STDIN> l3
score : 3
applied force : 3
real force    : 3.0
. . . . . . . . . .
. . . . . . . . . .
. . . . X . . . . .
. . . . O . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
STDIN> D1
score : 4
applied force : 1
real force    : 2.0
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . O . . . . .
. . . . X . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
STDIN> U1
score : 5
applied force : 1
real force    : 2.0
. . . . . . . . . .
. . . . . . . . . .
. . . . X . . . . .
. . . . O . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
STDIN> D1
score : 6
applied force : 1
real force    : 1
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . X . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Par in 6 shots!

PHP - 563
<?php
$b=[0,0];do{$h=[rand(0,9),rand(0, 9)];}while(!($h[0]|$h[1]));
$s=0;function o(){global$b,$h,$s;for($y=0;$y<10;$y++){for($x=0;$x<10;$x++){$p=[$y,$x];if($p==$b)echo'X';elseif($p==$h)echo'O';else echo '.';}echo "\n";}echo "score : $s
";}o();while($h!=$b){list($d,$p)=explode(' ',fread(STDIN,9));$P=max(1,min(9,$p+rand(-2,2)));switch($d){case'u':$b[0]-=$P;break;case'd':$b[0]+=$P;break;case'l':$b[1]-=$P;break;case'r':$b[1]+=$P;break;}$b=[max(0,min(9,$b[0])),max(0,min(9,$b[1]))];$s++;o();echo "applied force : ${p}real force    : $P
";}echo "Par in $s shots!";

X.........
......O...
..........
..........
..........
..........
..........
..........
..........
..........
score : 0
d 1
..........
X.....O...
..........
..........
..........
..........
..........
..........
..........
..........
score : 1
applied force : 1
real force    : 1
r 5
..........
......X...
..........
..........
..........
..........
..........
..........
..........
..........
score : 2
applied force : 5
real force    : 6
Par in 2 shots!

Ungolfed:
<?php
$ball = [0,0];
do {
    $hole = [ rand(0,9), rand(0, 9) ];
}while(!($hole[0]|$hole[1]));
$score = 0;
function out() {
    global $ball, $hole, $score;
    for($y=0;$y<10;$y++) {
        for($x=0;$x<10;$x++) {
            $p=[$y,$x];
            if($p==$ball)echo'X';
            elseif($p==$hole)echo'O';
            else echo '.';
        }
        echo "\n";
    }
    echo "score : $score
";
}
out();
while($hole!=$ball) {
    list($direction, $power) = explode(' ',fread(STDIN,10));
    $rPower=$power+rand(-2,2);
    switch($direction) {
        case 'u':$ball[0]-=$rPower;break;
        case 'd':$ball[0]+=$rPower;break;
        case 'l':$ball[1]-=$rPower;break;
        case 'r':$ball[1]+=$rPower;break;
    }
    $ball[0]=max(0,min(9,$ball[0]));
    $ball[1]=max(0,min(9,$ball[1]));
    $score++;
    out();
    echo "applied force : ${power}real force    : $rPower
";
}
echo "Par in $score shots!";

You may not have me beat for shortest code, but par in 2 shots! It took me (whispers) 6.

-100 for using global :D