text:
Solve Any Motion Physics Problem (Equations Supplied)
Physics Challenge
This program should be able to solve for ANY two of the following variables the user wants to solve.

s (displacement)
v (velocity)
u (initial velocity)
a (acceleration)
t (time)

At start the user must choose two variables they want to solve for and what variables they can supply. You are limited to using the following equations.
Equations Permitted

(http://en.wikipedia.org/wiki/Equations_of_motion)
The entrant with the least amount of code and posts the quickest will win.
Rules

This is code-golf. The shortest code wins.
Your program must terminate in reasonable time for all reasonable inputs.
You are allowed to transform the equations algebraically if need be
The program must be able to interpret a variable of which the user cannot supply (See Example 2)

Input Example
The program will start and ask which variable the user will like to calculate:
(s, v, u, a, t) - the user selects this via a char type or string.
It then supplies all values for the other unknowns and the program will solve for the variables.
Example 1:
*What would you like to calculate? (s, v, u, a, t)*
Input: a, u     // This could also be s,v s,u, s,a v,u (ANY COMBINATION)

*Enter value for s:*
Input: 7        // The input will always be random

*Enter value for v:*
Input: 5

// Repeat for others

//program calculates

Var a = answer
Var u = answer

Example 2:
*What would you like to calculate? (s, v, u, a, t)*
Input: a, t

*Enter value for u:*
Input: 5

*Enter value for s:*
Input: UNKNOWN

*Enter value for v:*
Input: 7

*The answers for a and t are 464 and 742*

Edit
I think everyone here is overcomplicating the question. It simply asks to solve any 2 variables from the list of (s, v, u, a, t) and solve them using the equations. As the programmer you must be able to allow values to be taken for the variables that are not being solved. I will clarify that the program must be able to solve for any variable supplied by the user on startup. I also removed the somewhat correct equation s=v/t because people are becoming confused by it.

How is the input received? What format is it in? You've said it's [code-golf], but then added that solving multiple variables will increase the chance of winning - I'd have thought that would take more code and actually reduce their chance of winning. Probably the best way to add an extra bonus without going against the tag you've used is to add a bounty and award it to the (first?) answer that meets the extended spec.

Adding to @Gareth's remarks: can you please provide some test cases? And I don't understand Rule 3.

@Gareth You're right. I changed the challenge to be more difficult. Input is received by any way you would like it to be BUT the program must be able to calculate any case. What do you mean by which format?

@Howard Provided tests cases and removed RUle 3

The line "and also s = v/t (a simple equation to find displacement)" is just plain wrong. It's dimensionally inconsistent and contradicts the other given equations.

it should be s=v*t

@Avi No it should not.

These are not test cases but incomplete examples.

No, s=vt is wrong. It's dimensionally ok, but still contradicts the other equations -- look at Eqns 2,3,5.

Voting to hold this question until a specification is given which would allow to judge competing answers according to code-golf criteria.

@Howard I think he takes 'simple formula' as formula when acceleration is 0 . So s=ut OR s=v*t as a=0.

You're now asking for the program to solve underdetermined systems of equations.

There are five variables (s,u,v,a,t), and one can choose (in 10 different ways) any two of them to be expressed in terms of the other three.  If the user identifies which two are to be "solved for" (say v1, v2 to be solved for in terms of v3, v4, v5), the program can then output two equations, giving v1 and v2 in terms of v3, v4, v5. If the user additionally provides one or more consistent values for any of the variables v3, v4, v5, then the two output equations can be correspondingly simplified. It looks like a doable problem to me, and the OP has already said it's code-golf.

@r.e.s., you correctly observe that any two can be solved for in terms of the other three. The question currently says "the user must choose more than two variables they want to solve for". Surely you must agree with me that it asks to solve an underdetermined system?

@PeterTaylor Correct, but currently both examples say "What would you like to calculate? (s, v, u, a, t) Input: a, u". It seems to me that the question needs to be clarified.

you still have a contradiction between how many variables to solve for, but it is getting closer.

Maple, 41 chars
s:=i->solve({v=u+a*t,s=(u+v)*t/2,op(i)}):

(Formulas used: #1 and #3.  These are sufficient to let Maple derive the rest.)
This defines a function s that takes in a set of initial conditions and solves the equations of motion for those initial values.  For example, the command:
> s({ u = 1, v = 2, t = 3 });

outputs:
                          {a = 1/3, s = 9/2, t = 3, u = 1, v = 2}

Notes:
You generally need to specify three initial values for a unique solution; if you don't provide enough, Maple will try to give you a partial solution:
> s({ u = 1, v = 2 });

                                        3 t
                          {a = 1/t, s = ---, t = t, u = 1, v = 2}
                                         2

(Yes, that's an ASCII art fraction there.  Even in text mode, Maple tries to typeset your math nicely.)
No solution is return for overspecified or otherwise unsolvable inputs; for example, s({ u = 1, v = 2, t = 0 }); outputs nothing.
If multiple solutions exist, Maple will generally try to return all of them:
> s({ u = 1, s = 0, a = -1 });

                          {a = -1, s = 0, t = 2, u = 1, v = -1},
                          {a = -1, s = 0, t = 0, u = 1, v = 1}

Sometimes, the output may contain RootOf() expressions, as in:
> s({ u = 10, s = 1, a = -1 });
                                                         2
                {a = -1, s = 1, t = RootOf(2 - 20 _Z + _Z , label = _L3), u = 10,
                                               2
                 v = 10 - RootOf(2 - 20 _Z + _Z , label = _L3)}

As far as Maple's concerned, this is a perfectly good solution, but if you want to turn it into something readable for us mere humans, use allvalues():
> allvalues(s({ u = 10, s = 1, a = -1 }));
                                            1/2                 1/2
                {a = -1, s = 1, t = 10 - 7 2   , u = 10, v = 7 2   },
                                            1/2                  1/2
                {a = -1, s = 1, t = 10 + 7 2   , u = 10, v = -7 2   }

Alternatively, you can specify the initial conditions as floating-point values, e.g. u = 10.0, which will cause Maple to return purely numerical solutions instead:
> s({ u = 10.0, s = 1, a = -1 });

                {a = -1., s = 1., t = 0.1005050634, u = 10., v = 9.899494937},
                {a = -1., s = 1., t = 19.89949494, u = 10., v = -9.899494937}

Finally, note that, since Maple is a computer algebra system, it allows you to specify arbitrary equations in the input.  For example, if we didn't care about the specific initial velocity, but only about the change in velocity, we could just specify e.g. v = u + 1 and get the partial solution:
> s({ v = u + 1 });

                {a = 1/t, s = t v - 1/2 t, t = t, u = v - 1, v = v}

We can even extend the physics model if we want, as in:
> s({ f = m * a, u = 0, f = 1, m = 10, t = 5 });

                {a = 1/10, f = 1, m = 10, s = 5/4, t = 5, u = 0, v = 1/2}

Nice. I especially like that equations 2, 4 and 5 are inferred from equations 1 and 3.

Golf-Basic 84, 58 characters
Executed from a TI-84 calculator
i`Cp`S,V,U,A,T@C=1d`U+AT@C=2d`UT+.5AT²@C=1d`"V="@C=2d`"S="

Sample Run
?1
?S=UNKNOWN
?V=UNKNOWN
?U=5
?A=4
?T=2
V=
              13

GTB, 43
`C,S,V,U,A,T@C=1$~"V="~U+AT#~"S="~UT+.5AT²&

Sample Runs
Solve for V
?1
?UNKNOWN
?UNKNOWN
?5
?4
?2
V=
          13

Solve for S
?2
?UNKNOWN
?UNKNOWN
?5
?4
?2
S=
          18

source: Stack Exchange

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

sort: votes


text:
Halt with 50% non-Halting
Create a program that halts exactly 50% of the time. Be original. Highest voted answer wins. By exactly I mean that on each run there is a 50% chance of it halting.

What do you mean by exactly 50% of the time? 50% is a proportion (no integral number is 50% of 3 times).

Removed tag code-challenge because it needs an objective winning criterion.

@Howard: I think he means that, when running your program the first time, it should halt, the second time it shouldn't, the third time, it should, ...

But then it is 100%, 50%, 66%, ...

@ProgramFOX That would be nowhere near exactly.

I mean that it should have an exactly 50% probability to halt on every run.

But then it won't be Halt, Don't Halt, Halt, Don't Halt because with a 50% prob you get runs.

If the program doesn't halt, does that mean it runs forever? It'll sure as hell halt when I turn the PC off. (Unless it is NSA code, then who knows...)

You really should clarify your question: “exact 50% probability to halt on every run” is contradictory with “halt, don't halt, halt, don't halt” — there's only a 1/16 chance of that particular sequence happening.

@Gilles I interpreted it to be out of a large number (say 1,000,000) of runs, half of them (exactly 500,000) should halt.

@Tyzoid This requirement is also incompatible with “an exact 50% probability to halt on every run”.

How many times should it halt if it's run three times?

Who keeps upvoting these poor questions?

If you flip a coin three times, it also won't land heads 1.5 times, but there is exactly 50% probability it will land on heads each time.

This is a fine question.  Only those who don't understand probability are confused by it.  The original title was perhaps a bit misleading, but no worse than the New York Times.

I found it perfectly clear.  Create a program that has a 50% chance of halting (or, equivalently a 50% chance of falling into an infinite loop), and you cannot know which will occur before every runtime.

There is no way to guarantee an exact 50% statistical probability even after doing 1 billion iterations. That's how randomness works.

Perl
fork || do {sleep(1) while(1)}

Each time you run this program, it halts and doesn't halt.

Schrodinger's halt

Python
import random
p=.3078458
while random.random()>=p:p/=2

Each time around the loop it breaks with exponentially decreasing probability.  The chance of never breaking is the product \$(1-p)(1-\frac{p}{2})(1-\frac{p}{4})...\$ which is \$\frac{1}{2}\$.  (Obligatory comment about floating point not being exact.)

+1 for maths. This would make a good "what is the behavior of this code" test problem.

Doesn't work. You can't add up the probabilities like that; the actual probability of halting is 1-3/47/815/16..., which works out to about 42%.

nice but the comment above is right: the probability of not halting is P(not halting on first)*P(not halting on second)P(not on third)... which tends to ~58%.  See here for exact: http://www.wolframalpha.com/input/?i=product+%281-1%2F2%5En%29%2C+n%3D2+to+infinity

start with p=0.3078458 to get 50.00002% :)

My bad.  Probability is hard.

JavaScript
Alternatives halting and not halting. (halts on first run, doesn't halt on second, ...)
var h = localStorage.halt;
while (h) localStorage.halt = false;
localStorage.halt = true;

@Jan Oops, sorry, fixed. (I'm answering from my phone right now so I can't test)

looks good now (I still like my answer better ;-) )

Doesn't work on ie8/ff3 (compatibility troll)

@Tyzoid who uses FF3 anyways? And it does work in IE8.

This doesn't fit the challenge anymore, because it is predictable.

Geometry Dash 2.2 Editor Glitch - 2 objects

Explanation:
The random trigger randomly toggles (disables) Group ID 1 or 2 with a 50% chance.
The purple pad is on reverse mode (meaning that if the cube touches it, the cube moves backward, which goes to the left forever and ever.).
Since the purple pad has Group ID 2, it has a 50% chance of being disabled, which means that the cube can pass through it to the end of the level, which will halt.
How to reproduce this:
Purple pad is on reverse mode and has Group ID 1.

Inside the random trigger.

Wow GD in code golf

@Jacob yes!! its a shame 2.2 still hasn't been released even though this leaked editor was usable, even in 2018

Well, with all of the leaks in the past week it looks like it might be out pretty soon. I wonder what possibilities there are for code-golf with all the new triggers

C
#include <unistd.h>
main() { while (getpid()&2); }

-1: Not Exactly 50%

It's exactly 50% on my operating system. It might not be on yours...

Random Brainfuck, 5 bytes
?[--]

Try it online!
Random BF extends BF's set of primitives with the ?, which generates a random byte and stores it in the current cell. That is, it generates an integer from 0-255. Given that there are an equal amount of odds and evens in that range, there is a 50% chance that the current cell is set to an even number after the first step.
The [--] endlessly decrements the current cell by two, as long as the current cell is not zero. Therefore, all even numbers will terminate. On the other hand, since parity is invariant mod 256, all odd numbers will loop forever, never quite reaching zero.

Lost, 2 bytes
%@

Try it online!
Although this is apparently a popcon, I figure the language itself is adequately interesting!
Lost is a fairly standard toroidal 2D language, with the caveat that the instruction pointer's initial position and direction are completely random. Additionally, in order to make it possible to write deterministic programs, there's a piece of global state called the safety which doesn't allow the program to halt by reaching @ until it's been turned off by %. So, this program has three cases:

50% of the time, the IP starts moving left or right. It eventually reaches both instructions, and the program halts.
25% of the time, the IP starts moving up or down on %. The safety is turned off, but it never reaches @, so the program does not halt.
25% of the time, the IP starts moving up or down on @. The safety is never turned off, so the program does not halt.

Simply brillant!

@gildux I'm pretty sure this is also the shortest program that can halt at all

INTERCAL, 59 bytes
DO %50 (1) NEXT
DO COME FROM COMING FROM
(1) PLEASE GIVE UP

Try it online!
COME FROM COMING FROM makes an endless loop, but there is a 50% chance to skip to the end of the program.

21 bytes if you use syntax error.

Ruby
n = 2*rand(1...49)+1; divisors = (1...100).select{|x|n % x == 0}.count until divisors == 2
print n

There are exactly 24 odd primes between 0..100, the largest being 97. This algorithm chooses a random odd number within the range and repeats until it finds a prime:
This particular implementation has two bugs:

an exclusive range is used, meaning that 99 is never tested, meaning there are only 48 possible values for n, of which 24 are primes.
while n was meant to be redrawn at each iteration, only the primality testing is executed in the loop. If at first it doesn't succeed, it will try again - but with the same number.

><>, 3 bytes
x;v

Try it online!
I... don't actually know ><>, but this should work on the same principle as the existing answers, just by "rerolling" vertical travel and looping if it goes left rather than down.

BASH
#!/bin/bash
set -e
sed -i 's/true\;/false\;/' $0
while false; do echo -n ''; done;
sed -i 's/false\;/true\;/' $0

Just a fun self-modifying script.
Note: the empty quoted string on echo -n '' are just for clarity. They can be removed without loss of functionality.

GolfScript
2rand{.}do

I know this isn't a code-golf challenge, but I golfed it anyway. :)

Alternatively, here's a GolfScript implementation of Keith Randall's solution:
2{2*.rand}do

In theory, this will have an exactly 1/4 + 1/8 + 1/16 + ... = 1/2 probability of halting.  In practice, though, it will always eventually run out of memory and halt, because the denominator keeps getting longer and longer.

I felt like golfing this one:
Befunge - 5 chars
?><
@

(I'm not sure whether this actually works as I don't have a befunge compiler on me)

I think ?v@ also works.

Poetic, 113 bytes
sometimes i,i think i get a choice
if its a thing i know i do affect,i bet i do win
i`m sorry if it breaks
o-h no

Try it online!

Somewhat obfuscated solution:
Haskell
import Control.Monad
import Control.Monad.Random         -- package MonadRandom
import Control.Monad.Trans.Maybe
import Data.Numbers.Primes          -- package primes

-- | Continue the computation with a given probability.
contWithProb :: (MonadRandom m, MonadPlus m) => Double -> m ()
contWithProb x = getRandomR (0, 1) >>= guard . (<= x)

loop :: MonadRandom m => MaybeT m ()
loop = contWithProb (pi^2/12) >> mapM_ (contWithProb . f) primes
  where
    f p = 1 - (fromIntegral p)^^(-2)

main = evalRandIO . runMaybeT $ loop

Python
The same solution expressed in Python:
import itertools as it
import random as rnd
from math import pi

# An infinite prime number generator
# Copied from http://stackoverflow.com/a/3796442/1333025
def primes():
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

def contWithProb(p):
    if rnd.random() >= p:
        raise Exception()

if __name__ == "__main__":
    rnd.seed()
    contWithProb(pi**2 / 12)
    for p in primes():
        contWithProb(1 - p**(-2))

Explanation

 This solution makes use of the fact that the infinite product \$\Pi(1-p^{-2})\$ converges to \$\frac{6}{\pi^2}\$. This is because \$\zeta(2)=\Pi(\frac{1}{1-p^{-2}})\$ converges to \$\frac{\pi^2}{6}\$.

><>, 4 bytes
x;
>

Try it online!

Oh, I did NOT see the existing ><> answer... whoops.

Pyt, 3 bytes
ɹ`ł

Try it online!
ɹ          get a random bit (0 or 1 with equal probability)
 `ł        loop while top of stack is truthy (1 is truthy; 0 is not)

I knew these answers would start flowing in once I revived it XD. Our golflangs and tarpits really didn't compare for these kinds of problems back then.

C
int main() {
    char i;
    while(i&1);
}

@JanDvorak Shhhhh, don't tell everyone!

This abuses undefined behavior that compilers already break to optimize the code. Therefore, for this to have any chances of working, you cannot optimize this code (not that this will work even then, because in main, the registers are initialized to 0 for security reasons).

><>, 5 bytes and a beautiful 2x2 square
x;
><

x sends the instruction pointer in a random direction; If it sends left or right the IP will hit ; and terminate. If it goes up or down the IP will get stuck in the infinite >< loop, being sent back and forth between the two.

it's not called <>< tho, it's called ><> lol (unless there's one called <>< I haven't heard of)

also you can save 1 byte by removing the < (because the pointer wraps around); it won't be a 2x2 square anymore but it'll be nicely golfed c:

Scala
object HaltOrNot extends App {
  val x = scala.util.Random.nextLong
  while (((scala.util.Random.nextLong & 0xFFFFFFFFFFFFFFFEL) ^ x) != 0) {}
}

If x is odd positive or even negative, this program will never halt.
If x is even positive or odd negative, this program will definitely halt... someday... after thousands of years...
(e.g., if your machine can test 100 Mio loops per second it will terminate after 2924 years in expectation)

TI-Basic
:Lbl 1:If round(rand):Pause:Goto 1

The syntax for round( is round(value,# of decimal places), and the second argument defaults to 9.

Python, 48
import random
a=random.randrange(2)
while a:pass

Perl
BEGIN {
    # Do the following block 50% of time.
    if (int rand 2) {
        # Create a function that doubles values.
        *double = sub {
            2 * shift;
        };
    }
}
double / 3 while 1; # Calculates double divided using /

Not code golf, so I could avoid unreadable code (because what it does is more important). It randomly declares a function during compilation phase. If it gets declared, double gets regular expression as an argument. If it doesn't get declared, double is a bareword, and Perl divides it by 3 endlessly. This abuses Perl's bareword parsing, in order to get parser parse the same code two different ways.

Java
import java.util.Random;

class Halt50 {
    public static void main(String[] args){
        if(new Random().nextInt(2)==0)for(;;);
    }
}

Java
import java.io.*;

public class HaltNoHalt {
    public static void main(String[] args) throws Exception {
        RandomAccessFile f = new RandomAccessFile("HaltNoHalt.java", "rw");
        f.seek(372);
        int b = f.read();
        f.seek(372);
        f.write(b ^ 1);
        Runtime.getRuntime().exec("javac HaltNoHalt.java");

        while ((args.length & 1) == 1);
    }
}

This self-modifies the code to toggle the == 1 to == 0 and back, every time it's run. Save the code with newlines only or the offset will be wrong.
The args.length is just to prevent compiler optimizations.

JavaScript (Node.js), 24 bytes
It was incorrect, but somehow correcting it removed 2 bytes, thanks Roman Czyborra for pointing out it was incorrect
And another -2 because I forgot how to JS
if(Date.now()%2)for(;;);

Date.now() returns the amount of milliseconds since the Unix time epoch, which has a 50% chance to be even at the moment of running the program.

Isn't this missing a final ||for(;;); to prevent 100% halting?

I was stupid and didn't think of differences the REPL introduces...

Can we please stop feeling stupid?

Alice, 5 bytes
2U$v@

Try it online!
2          Pushes the number 2 on the stack
 U         Pops 2, pushes a random number in the range [0,2) on the stack
  $        Pops the random number, if 0 skip the next instruction
   v       Now moves vertically forever
    @      Halt

Fortran (GFortran), 19 bytes
1 if(i>0)goto 1
end

Try it online!. Since the lazy programmer did not initialise i, it is a random 32 bit integer, populated from whatever bits were floating around in that memory space before.

Javascript
JS has these Object URL things, which are generated when you create a file. The hex is all meaningless nonsense, but not in this case! Therefore, something like this works:
var blob = URL.createObjectURL(new Blob([""]))
// The blob looks something like "blob:null/01234567-1234-1234-1234-0123456789ab" and is hex, which can be exploited, really, any character works!
while (TextEncoder && new TextEncoder().encode(blob)[10] > 56) {
// Forever!
}

Python, 19 bytes
while id(1)>>17&1:1

Run online
This gets the address of the constant 1 in memory, and gets the 17th bit from the right. It then loops forever if the bit is 1.
I can't use a later bit to save a byte, because those bits seem to be constant between runs. The last bits are always 0011110000.
Some debug code:
print(bin(id(1)))
print(bin(id(1)>>17))
print(id(1)>>17&1)

Exactly 50% of the time?
OBJ-C
- (void)applicationDidFinishLaunching:(NSNotification*)aNotification {
    BOOL haltedLastRun = [(NSNumber*)[[NSUserDefaults standardUserDefaults] objectForKey:@"halted"] boolValue];
    if (!haltedLastRun) {
        [[NSUserDefaults standardUserDefaults] setObject:[NSNumber numberWithBool:YES] forKey:@"halted"];
        [[NSApplication sharedApplication] terminate:nil];
    }
}

Haskell
Runs for two intervals, each one 1 second long (chosen because 1 second is the SI unit for time). Halts inside 50% of the intervals. So 50% of the running seconds it will not halt, the other 50% it will. Works in GHC only.
import Control.Concurrent (threadDelay)
main = threadDelay 1990000

Shell Script
this script will clobber .md5sum files in the current and child directories.
#!/bin/sh
echo *.md5sum|xargs -n1|head -n1|xargs test -e && exec rm *.md5sum
while ! find . -name '*.md5sum' -print0 |xargs -0r grep 00000000000000
do {
    find . -type f -print|sed -e 's!^\(.*\)$!md5sum "\1" > "\1".md5sum!e'
}
done

GTB
[@r;p;]

I know this isn't code-golf but I decided to golf it anyway.

C++
#include <fstream>
main () {
    int c;
    std::fstream fs;
    fs.open ("myfile.txt", std::fstream::in);
    fs>>c;
    fs.close ();
    fs.open ("myfile.txt", std::fstream::out);
    fs<<c+1;
    fs.close ();
    while (c%2);
    return 0;
}

Each run will halt iff the run before didn't.

Windows Command Script
This script will append code to itself which ultimately alternates 'x' on each run.
call :last
if %x%==1 (
    echo>>%0 set x=0
    exit /b 0
) else (
    echo>>%0 set x=1
)
:nohalt
goto :nohalt
:last
set x=1
[newline here]

Python 2, 54 bytes
import time;H=[time.time()%2]
for h in H:H+=[h]*int(h)

Try it online!
Halting behaviour is dependent on current time.

Math++
_($rand*2)+2>$
2>$
1

Pxem, filename: 7 bytes + content: 0 bytes = 7 bytes, depends on implementation.

Filename (escaped): \002.r.w.a
Content: empty.

How it works

\002.r: pushes one of 0 or 1.
.w ... .a: while empty || pop!=0; do ... ;done

Try it online!

Thue, 19 bytes
0::=00
10::=
::=
10

Try it online!
TIO's Thue interpreter doesn't seem to be working correctly.

Thunno, \$ 6 \log_{256}(96) \approx \$ 4.94 bytes
2RZw?[

Attempt This Online!
Explanation
2R      # range(2): push [0, 1]
  Zw    # Random element of ↑
    ?   # If ↑ == 1:
     [  #  Loop forever
        # (Else, exit)

C (GCC)
unsigned long long i,j,k;
r;

main()
{
    srand(time(0));

    i=k=1;
    while (k) {
        k = 0;
        for (j = 1; j <= i; ++j) {
            do {
                r = rand() % 4;
            } while (r == 3);

            k += !!r;
        }
        ++i;
    }
}

Try It Online!
It loops while k isn't 0. k is only 0 at the end of the loop if i number of calls to rand() are all divisible by 3. The chance of that equals
$$ \frac {1} {3^i} $$
and the sum of all inverse natural powers of 3 equals 0.5. Of course, i doesn't go from 1 to infinity, but from 1 to ULLONG_MAX. When i reaches ULLONG_MAX, the for loop will loop infinitely as j will always be less than or equal to i (assuming ULL_MAX + 1 is 0).
Since i doesn't quite loop from 1 to infinity, the code will loop slightly less than 50 % of the time, more specifically
$$ 50 \% - \frac {1} {3^{U+1} - 3^{U}} $$
where U is ULLONG_MAX.

there's also the problem with rand() % 3 not being uniformly distributed, which leads to the probability of it being 0 to slightly increase

@c-- True … I'll see what I can do about that.

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

authors: Александр Белецкий

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


text:
Helping the Farmer
Farmer Jack is very poor. He wants to light his whole farm but with minimum of cost. A lamp can illuminate its own cell as well as its eight neighbors . He has arranged the lamps in his field but he needs your help in finding out whether or not he has kept any extra lamps.
Extra lamps : Lamps which on removing from the farm will make no difference to the number of cells lit. Also, the lamps you will point will not be removed one by one, but they will be removed simultaneously.
Note: The only action you can perform is to remove some lamps. You can neither rearrange nor insert lamps. Your final target is to remove maximum number of lamps such that every cell which was lit before is still lit.
Help Farmer Jack in spotting the maximum number of useless lamps so that he can use them elsewhere.
Input
You will be given in the first line dimensions of the field M and N.Next M lines follow containing N characters each representing the field.
'1' represents cell where lamp is kept.
'0' represents an empty cell.
Output
You have to output an integer containing number of useless lamps.
Sample Input:
3 3
100
010
001

Sample Output:
2

Winner:
Since it is code golf, winner will be the one who will successfully complete the task in least number of characters

@PeterTaylor I have edited my post. Do you still have a confusion?

may we assume the input ends with a newline?

Yes sure, you can do that

This looks like homework.

Can you post a couple more complex examples? Is there a limit for the number of lamps?

Given the complexity of the problem, and the number of variables and parameters that need naming, I recommend that it be a code-challenge.  Also, you really ought to require that the program show which lights are useless (by their position or by showing which ones are indispensable).Finally, you ought to include more complex examples that we are expected to provide solutions to.  Otherwise, it will be very difficult to know for sure whether procedures do what they were intended to do.

On the other hand, there may be a much simpler way to identify useless lamps...

Are we guaranteed that the input lamps will light the whole farm?  I'm going to guess no...

@KeithRandall Your guess is right. The input lamps may or may not light the whole field

This is just minimum set cover with a strange encoding and a silly story.

@user2369284 if the farm is not fully lit, what should our output be?  A negative integer whose absolute value is the minimum number of additional lamps needed?

@Panzercrisis I would assume the farm can be partially lit. We are still required to provide the number of lamps that can be safely removed without switching off cells that were originally lit.

Mathematica 186 (greedy) and 224 (all combinations)
Greedy Solution
t=MorphologicalTransform;n@w_:=Flatten@w~Count~1
p_~w~q_:=n[p~t~Max]==n[q~t~Max]
g@m_:=Module[{l=m~Position~1,r,d=m},While[l!={},If[w[m,r=ReplacePart[d,#-> 0]&
[l[[1]]]],d=r];l=Rest@l];n@m-n@d]

This turns off superfluous lights one by one.
If the light coverage is not diminished when the light goes off, that light can be eliminated.
The greedy approach is very fast and can easily handle matrices of 15x15 and much larger (see below). It returns a single solutions, but it is unknown whether that is optimal or not.
Both approaches, in the golfed versions, return the number of unused lights.
Un-golfed approaches also display the grids, as below.
Before:

After:

Optimal Solutions using all combinations of lights (224 chars)
With thanks to @Clément.
Ungolfed version using all combinations of lights
fThe morphological transform function used in sameCoverageQ treats as lit (value = 1 instead of zero) the 3 x3 square in which each light resides.When a light is near the edge of the farm, only the squares (less than 9) within the borders of the farm are counted.There is no overcounting; a square lit by more than one lamp is simply lit.The program turns off each light and checks to see if the overall lighting coverage on the farm is reduced.If it is not, that light is eliminated.
nOnes[w_]:=Count[Flatten@w,1]
sameCoverageQ[m1_,m2_]:=nOnes[MorphologicalTransform[m1,Max]]==
  nOnes[MorphologicalTransform[m2,Max]]

(*draws a grid with light bulbs *)
h[m_]:=Grid[m/.{1-> Style[\[LightBulb],24],0-> ""},Frame-> All,ItemSize->{1,1.5}]

c[m1_]:=GatherBy[Cases[{nOnes[MorphologicalTransform[ReplacePart[Array[0&,Dimensions[m1]],
#/.{{j_Integer,k_}:> {j,k}-> 1}],Max]],#,Length@#}&/@(Rest@Subsets[Position[m1,1]]),
{nOnes[MorphologicalTransform[m1,Max]],_,_}],Last][[1,All,2]]

nOnes[matrix] counts the number of flagged cells. It is used to count the lights and also to count the lit cells
sameCoverageQ[mat1, mat2] tests whether the lit cells in mat1 equals the number of lit cells in mat2.MorphologicalTransform[[mat] takes a matrix of lights and returns a matrix` of the cells they light up.
c[m1] takes all combinations of lights from m1 and tests them for coverage.  Among those that have the maximum coverage, it selects those that have the fewest light bulbs.  Each of these is an optimal solution.

Example 1:
A 6x6 setup
(*all the lights *)
m=Array[RandomInteger[4]&,{6,6}]/.{2-> 0,3->0,4->0}
h[m]

All optimal solutions.
(*subsets of lights that provide full coverage *)
h/@(ReplacePart[Array[0&,Dimensions[m]],#/.{{j_Integer,k_}:> {j,k}-> 1}]&/@(c[m]))

Golfed version using all combinations of lights.
This version calculates the number of unused lights.  It does not display the grids.
c returns the number of unused lights.
n@w_:=Flatten@w~Count~1;t=MorphologicalTransform;
c@r_:=n@m-GatherBy[Cases[{n@t[ReplacePart[Array[0 &,Dimensions[r]],#
/.{{j_Integer,k_}:> {j,k}-> 1}],Max],#,Length@#}&/@(Rest@Subsets[r~Position~1]),
{n[r~t~Max],_,_}],Last][[1,1,3]]

n[matrix] counts the number of flagged cells. It is used to count the lights and also to count the lit cells
s[mat1, mat2] tests whether the lit cells in mat1 equals the number of lit cells in mat2.t[[mat] takes a matrix of lights and returns a matrix` of the cells they light up.
c[j] takes all combinations of lights from j and tests them for coverage.  Among those that have the maximum coverage, it selects those that have the fewest light bulbs.  Each of these is an optimal solution.
Example 2
m=Array[RandomInteger[4]&,{6,6}]/.{2-> 0,3->0,4->0};
m//Grid

Two lights can be saved while having the same lighting coverage.
    c[m]

2

I don't have Mathematica at hand so I can't test this code, but I think your algorithm is incorrect — unless I misunderstood your explanations. If my understanding is correct, it relies on a greedy strategy that is dependent on the order in which light are processed: for example, starting from the middle lamp in your 3*3 test case would remove it and leave the two side lamps. I don't expect that the particular ordering that you use in the implementation makes it correct, but I don't have a counter-example right now.

Your idea seems to be that it may be possible to have 2 superfluous lights, a, b, in the original setup, one of which is more superfluous than the other.  So, it may be that there is better economy achieved if one is removed (first).  I sense that this could not happen with 3 lights total, but it may indeed be possible with greater numbers of lights.  I originally solved the problem by testing all combinations of lights.  This is certainly optimal and thus ideal, but I found it impractical with a large set of lights.

@Clément I'm working on a solution that will test all possible combinations.  Will take a while...

It sure will ;) But that's to be expected: as it stands this problem is an instance of the minimum set cover — which is NP. Whether the additional assumptions (almost all covering sets, except the lateral ones, have the same cardinality) allow for an efficient implementation is an interesting problem though.

I strongly suspect the greedy solution is correct if you go sequentially by rows and columns, but I haven't proven it yet.

Neat work, +1! Something awesome to do here would be to run both algorithms on small randomly generated input sets, and check whether they always return equal results. If they do it won't prove that the greedy algorithm was correct, but if they don't then it will give us a counter-example.

Good idea. Perhaps when I have some free time...

Java 6 - 509 bytes
I made some assumptions about the limits and solved the problem as stated at this time.
import java.util.*;enum F{X;{Scanner s=new Scanner(System.in);int m=s.nextInt(),n=s.nextInt(),i=m,j,k=0,l=0,r=0,o,c,x[]=new int[30],y[]=x.clone();int[][]a=new
int[99][99],b;while(i-->0){String t=s.next();for(j=n;j-->0;)if(t.charAt(j)>48){x[l]=i;y[l++]=j;}}for(;k<l;++k)for(i=9;i-->0;)a[x[k]+i/3][y[k]+i%3]=1;for(k=1<<l;k-->0;){b=new
int[99][99];for(j=c=l;j-->0;)if((k&1<<j)>0)for(c--,i=9;i-->0;)b[x[j]+i/3][y[j]+i%3]=1;for(o=i=0;i++<m;)for(j=0;j++<n;)o|=a[i][j]^b[i][j];r=c-o*c>r?c:r;}System.out.println(r);}}

Run like this: java F <inputfile 2>/dev/null

Not exactly short, but fits in a disk sector :p I may try a different language later.

@aditsu How to make this work on windows?

@user2369284: I don't see how you can do 0011111100 with only 2 lamps.  You need to cover 8 cells with light, and each lamp can do at most 3.

@user2369284 perhaps java F <inputfile 2>nul, if that fails then java F <inputfile and ignore the exception. Also it won't run with java 7.

@aditsu I'm really sorry.That was a typo error. Your program works correctly.

@aditsu I'm not able to give an upvote unless you edit your post.So please make a minor edit so that I may upvote your answer.

Python, 309 chars
import sys
I=sys.stdin.readlines()[1:]
X=len(I[0])
L=[]
m=p=1
for c in''.join(I):m|=('\n'!=c)*p;L+=('1'==c)*[p<<X+1|p<<X|p<<X-1|p*2|p|p/2|p>>X-1|p>>X|p>>X+1];p*=2
O=lambda a:m&reduce(lambda x,y:x|y,a,0)
print len(L)-min(bin(i).count('1')for i in range(1<<len(L))if O(L)==O(x for j,x in enumerate(L)if i>>j&1))

Works using bitmasks.  L is a list of the lights, where each light is represented by an integer with (up to) 9 bits set for its light pattern.  Then we exhaustively search for subsets of this list whose bitwise-or is the same as the bitwise-or of the whole list.  The shortest subset is the winner.
m is a mask that prevents wraparound of the bits when shifting.

Please try to provide a program which runs correctly.Java/C++ are safe to any kind of indentation or spacing but Python is not.Obfuscating or shortening code is another thing but providing a program which does not run is another.

@user2369284 what are you talking about?! It works perfectly fine (with python 2)

@aditsu I have python 3.

@user2369284 well, the print syntax is different so it fails in python 3

Ruby, 303
[this was coded to answer a previous version of the question; read note below]
def b(f,m,n,r)b=[!1]*1e6;(n..n+m*n+m).each{|i|b[i-n-2,3]=b[i-1,3]=b[i+n,3]=[1]*3if f[i]};b[r*n+r+n+1,n];end
m,n=gets.split.map(&:to_i)
f=[!1]*n
m.times{(?0+gets).chars{|c|f<<(c==?1)if c>?*}}
f+=[!u=0]*n*n
f.size.times{|i|g=f.dup;g[i]?(g[i]=!1;u+=1if m.times{|r|break !1if b(f,m,n,r)!=b(g,m,n,r)}):0}
p u

Converting to arrays of Booleans and then comparing neighbourhoods for changes.
Limitation(?): Maximum farm field size is 1,000 x 1,000. Problem states "Farmer Jack is very poor" so I'm assuming his farm isn't larger.  ;-)  Limitation can be removed by adding 2 chars.
NOTE: Since I began coding this, it appears the question requirements changed. The following clarification was added "the lamps you will point will not be removed one by one, but they will be removed simultaneously".  The ambiguity of the original question allowed me to save some code by testing individual lamp removals.  Thus, my solution will not work for many test cases under the new requirements. If I have time, I will fix this. I may not. Please do not upvote this answer since other answers here may be fully compliant.

c++ - 477 bytes
#include <iostream>
using namespace std;int main(){
int c,i,j,m,n,p,q=0;cin>>m>>n;
int f[m*n],g[m*n],h[9]={0,-1,1,-m-1,-m,-m+1,m-1,m,m+1};
for(i=0;i<m*n;i++){f[i]=0;g[i]=0;do{c=getchar();f[i]=c-48;}while(c!='0'&&c!='1');}
for(i=0;i<m*n;i++)if(f[i])for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)g[i+h[j]]++;
for(i=0;i<m*n;i++)if(f[i]){p=0;for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)if(g[i+h[j]]<2)p++;if(p==0){for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)g[i+h[j]]--;q++;}}cout<<q<<endl;}

APL, 97 chars/bytes*
Assumes a ⎕IO←1 and ⎕ML←3 APL environment.
m←{s↑⊃∨/,v∘.⊖(v←⍳3)⌽¨⊂0⍪0⍪0,0,s⍴⍵}⋄n-⌊/+/¨t/⍨(⊂m f)≡¨m¨(⊂,f)\¨t←⊂[1](n⍴2)⊤⍳2*n←+/,f←⍎¨⊃{⍞}¨⍳↑s←⍎⍞

Ungolfed version:
s ← ⍎⍞                                         ⍝ read shape of field
f ← ⍎¨ ⊃ {⍞}¨ ⍳↑s                              ⍝ read original field (lamp layout)
n ← +/,f                                       ⍝ original number of lamps
c ← ⊂[1] (n⍴2) ⊤ ⍳2*n                          ⍝ all possible shutdown combinations
m ← {s↑ ⊃ ∨/ ,v ∘.⊖ (v←⍳3) ⌽¨ ⊂ 0⍪0⍪0,0, s⍴⍵}  ⍝ get lighted cells given a ravelled field
l ← m¨ (⊂,f) \¨ c                              ⍝ map of lighted cells for every combination
k ← c /⍨ (⊂ m f) ≡¨ l                          ⍝ list of successful combinations
u ← ⌊/ +/¨ k                                   ⍝ min lamps used by a successful comb.
⎕ ← n-u                                        ⍝ output number of useless lamps

⎕ ← s⍴ ⊃ (⊂,f) \¨ (u= +/¨ k) / k               ⍝ additional: print the layout with min lamps

I agree that more test cases would be better. Here's a random one:
Input:
5 5
10001
01100
00001
11001
00010

Output (useless lamps):
5

Layout with min lamps (not included in golfed version):
0 0 0 0 1
0 1 0 0 0
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

C++ 5.806 Bytes
This is not optimized for size yet. But since there are few contestants i will leave it at that for now.
FarmersField Header:

#pragma once

namespace FarmersLand
{

class FarmersField
{
private:
    unsigned _m_size, _n_size;
    int * _lamp, * _lumination;
    char * _buffer;
    void _illuminate(unsigned m, unsigned n);
    void _deluminate(unsigned m, unsigned n);
    void _removeLamp(unsigned m, unsigned n);
    void _setLamp(unsigned m, unsigned n);
    int _canRemoveLamp(unsigned m, unsigned n);
    int _coordsAreValid(unsigned m, unsigned n);
    int _getLuminationLevel(unsigned m, unsigned n);
    int * _allocIntArray(unsigned m, unsigned n);
    int _coordHelper(unsigned m, unsigned n);
public:
    FarmersField(char * input[]);
    FarmersField(const FarmersField & field);
    ~FarmersField(void);
    int RemoveLamps(void);
    char * Cstr(void);
};

}

FarmersField CPP:

#include "FarmersField.h"
#include <stdio.h>

namespace FarmersLand
{

void FarmersField::_illuminate(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        ++this -> _lumination[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_deluminate(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        --this -> _lumination[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_removeLamp(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        unsigned mi_start = (m == 0) ? 0 : m - 1;
        unsigned mi_end = m + 1;
        unsigned ni_start = (n == 0) ? 0 : n - 1;
        unsigned ni_end = n + 1;

        for(unsigned mi = mi_start; mi <= mi_end; ++mi)
        {
            for(unsigned ni = ni_start; ni <= ni_end; ++ni)
            {
                this -> _deluminate(mi, ni);
            }
        }
        --this -> _lamp[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_setLamp(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        unsigned mi_start = (m == 0) ? 0 : m - 1;
        unsigned mi_end = m + 1;
        unsigned ni_start = (n == 0) ? 0 : n - 1;
        unsigned ni_end = n + 1;

        for(unsigned mi = mi_start; mi <= mi_end; ++mi)
        {
            for(unsigned ni = ni_start; ni <= ni_end; ++ni)
            {
                this -> _illuminate(mi, ni);
            }
        }
        ++this -> _lamp[this -> _coordHelper(m,n)];
    }
}

int FarmersField::_canRemoveLamp(unsigned m, unsigned n)
{
    unsigned can = 1;
    unsigned mi_start = (m == 0) ? 0 : m - 1;
    unsigned mi_end =   (m == (this->_m_size - 1)) ? m : m + 1;
    unsigned ni_start = (n == 0) ? 0 : n - 1;
    unsigned ni_end =   (n == (this->_n_size - 1)) ? n : n + 1;

    for(unsigned mi = mi_start; mi <= mi_end; ++mi)
    {
        for(unsigned ni = ni_start; ni <= ni_end; ++ni)
        {
            if( 1 >= this -> _getLuminationLevel(mi, ni) )
            {
                can = 0;
            }
        }
    }
    return can;
}

int FarmersField::_coordsAreValid(unsigned m, unsigned n)
{
    return m < this -> _m_size && n < this -> _n_size;
}

int FarmersField::_getLuminationLevel(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        return this -> _lumination[this -> _coordHelper(m,n)];
    }
    else
    {
        return 0;
    }
}

int * FarmersField::_allocIntArray(unsigned m, unsigned n)
{
    int * a = new int[m * n];
    for(unsigned i = 0; i < m*n; ++i)
    {
        a[i] = 0;
    }
    return a;
}

int FarmersField::_coordHelper(unsigned m, unsigned n)
{
    return m * this -> _n_size + n;
}

int FarmersField::RemoveLamps(void)
{
    int r = 0;
    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if(this -> _canRemoveLamp(m,n))
            {
                ++r;
                this -> _removeLamp(m,n);
            }
        }
    }
    return r;
}

char * FarmersField::Cstr(void)
{
    unsigned size = this -> _m_size * this -> _n_size + _m_size ;
    unsigned target = 0;
    delete(this -> _buffer);
    this -> _buffer = new char[ size ];
    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            this -> _buffer[target++] =  (0 == this -> _lamp[this -> _coordHelper(m,n)])? '0' : '1';
        }
        this -> _buffer[target++] = '-';
    }
    this -> _buffer[size - 1 ] = 0;
    return this -> _buffer;
}

FarmersField::FarmersField(char * input[])
{
    sscanf_s(input[0], "%u %u", &this -> _m_size, &this -> _n_size);

    this -> _lamp = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _lumination = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _buffer = new char[1];

    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if('0' != input[m+1][n])
            {
                this -> _setLamp(m,n);
            }
        }
    }
}

FarmersField::FarmersField(const FarmersField & field)
{
    this -> _m_size = field._m_size;
    this -> _n_size = field._n_size;

    this -> _lamp = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _lumination = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _buffer = new char[1];

    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if(0 != field._lamp[this -> _coordHelper(m,n)])
            {
                this -> _setLamp(m,n);
            }
        }
    }

}

FarmersField::~FarmersField(void)
{
    delete(this -> _lamp);
    delete(this -> _lumination);
    delete(this -> _buffer);
}

}

And a set of tests to show that the code does what it was built to do:

#include "../../Utility/GTest/gtest.h"

#include "FarmersField.h"

TEST(FarmersField, Example1)
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "100", "010", "001"};
    FarmersField f(input);
    EXPECT_STREQ("100-010-001", f.Cstr());
    EXPECT_EQ(2, f.RemoveLamps());
    EXPECT_STREQ("000-010-000", f.Cstr());
}

TEST(FarmersField, Example2)
{
    using namespace FarmersLand;
    char * input[] = {"3 6", "100000", "010000", "001000"};
    FarmersField f(input);
    EXPECT_STREQ("100000-010000-001000", f.Cstr());
    EXPECT_EQ(1, f.RemoveLamps());
    EXPECT_STREQ("000000-010000-001000", f.Cstr());
 }

TEST(FarmersField, Example3)
{
    using namespace FarmersLand;
    char * input[] = {"6 3", "100", "010", "001", "000", "000", "000",};
    FarmersField f(input);
    EXPECT_STREQ("100-010-001-000-000-000", f.Cstr());
    EXPECT_EQ(1, f.RemoveLamps());
    EXPECT_STREQ("000-010-001-000-000-000", f.Cstr());
 }

TEST(FarmersField, Example4)
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "000", "000", "000",};
    FarmersField f(input);
    EXPECT_STREQ("000-000-000", f.Cstr());
    EXPECT_EQ(0, f.RemoveLamps());
    EXPECT_STREQ("000-000-000", f.Cstr());
 }

TEST(FarmersField, Example5)
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "111", "111", "111",};
    FarmersField f(input);
    EXPECT_STREQ("111-111-111", f.Cstr());
    EXPECT_EQ(8, f.RemoveLamps());
    EXPECT_STREQ("000-010-000", f.Cstr());
 }

TEST(FarmersField, Example6)
{
    using namespace FarmersLand;
    char * input[] = {"6 6", "100001", "001010", "001001", "001010", "110000", "100001",};
    FarmersField f(input);
    EXPECT_STREQ("100001-001010-001001-001010-110000-100001", f.Cstr());
    EXPECT_EQ(6, f.RemoveLamps());
    EXPECT_STREQ("100011-001010-000000-000010-010000-000001", f.Cstr());
 }

Please provide a testing utility which does use external libraries.

It is GTest: http://code.google.com/p/googletest/downloads/list

Perl 3420 bytes
Not a golf solution, but I found this problem interesting:
#!/usr/bin/perl
use strict;
use warnings;

{
   package Farm;
   use Data::Dumper;

   # models 8 nearest neighbors to position i,j forall i,j
   my $neighbors = [ [-1, -1],
                     [-1,  0],
                     [-1, +1],
                     [ 0, -1],
                     # current pos
                     [ 0,  1],
                     [+1, -1],
                     [+1,  0],
                     [+1, +1] ];

   sub new {
      my ($class, %attrs) = @_;
      bless \%attrs, $class;
   }

   sub field {
      my $self = shift;
      return $self->{field};
   }

   sub rows {
      my $self = shift;
      return $self->{rows};
   }

   sub cols {
      my $self = shift;
      return $self->{cols};
   }
   sub adjacents {
      my ($self, $i, $j) = @_;

      my @adjs;
   NEIGHBORS:
      for my $neighbor ( @$neighbors ) {
         my ($imod, $jmod) = ($neighbor->[0] + $i, $neighbor->[1] + $j);
         next NEIGHBORS
            if $imod >= $self->rows || $jmod >= $self->cols;

         # push neighbors
         push @adjs,
            $self->field->[$imod]->[$jmod];

      }

      return @adjs;
   }

   sub islit {
      my ($lamp) = @_;

      return defined $lamp && $lamp == 1;
   }

   sub can_remove_lamp {
      my ($self, $i, $j) = @_;

      return scalar grep { islit($_) } $self->adjacents($i, $j);
   }

   sub remove_lamp {
      my ($self, $i, $j) = @_;

      $self->field->[$i]->[$j] = 0;
   }

   sub remove_lamps {
      my ($self) = @_;

      my $removed = 0;
      for my $i ( 0 .. @{ $self->field } - 1) {
         for my $j ( 0 .. @{ $self->field->[$i] } - 1 ) {
            next unless islit( $self->field->[$i]->[$j] );

            if( $self->can_remove_lamp($i, $j) ) {
               $removed++;
               $self->remove_lamp($i, $j);
            }
         }
      }

      return $removed;
   }

   1;
}

{ # Tests
   use Data::Dumper;
   use Test::Deep;
   use Test::More;

   { # 3x3 field
      my $farm = Farm->new( rows  => 3,
                            cols  => 3,
                            field => [ [1,0,0],
                                       [0,1,0],
                                       [0,0,1]
                                     ]
      );

      is( 2,
          $farm->remove_lamps,
          'Removed 2 overlapping correctly'
      );

      is_deeply( $farm->field,
                 [ [0,0,0],
                   [0,0,0],
                   [0,0,1],
                 ],
                 'Field after removing lamps matches expected'
      );

   }

   { # 5x5 field
      my $farm = Farm->new( rows  => 5,
                            cols  => 5,
                            field => [ [0,0,0,0,0],
                                       [0,1,0,0,0],
                                       [0,0,1,0,0],
                                       [0,0,0,0,0],
                                       [0,0,0,0,0]
                                     ]
      );

      is( 1,
          $farm->remove_lamps,
          'Removed 1 overlapping lamp correctly'
      );

      is_deeply( $farm->field,
                 [ [0,0,0,0,0],
                   [0,0,0,0,0],
                   [0,0,1,0,0],
                   [0,0,0,0,0],
                   [0,0,0,0,0],
                 ],
                 'Field after removing lamps matches expected'
      );
   }
}

(I/O was taken out so I could show concrete tests)

Python - 305 bytes
import sys,itertools
w,h=map(int,input().split());w+=1
l=[i for i,c in enumerate(sys.stdin.read())if c=="1"]
f=lambda l:{i+j for i in l for j in(0,1,-1,w-1,w,w+1,1-w,-w,-w-1)if(i+j+1)%w}&set(range(w*h))
for n in range(1,len(l)):
 for c in itertools.combinations(l,n):
  if f(c)^f(l):print(len(l)-n);exit()


text:
Hide evil code - print files containing a given string anywhere in a directory tree
The point of this puzzle is to learn how a malicious code can be hidden and discovered in a program.
A person is asking the question:

Plz give me some code that how can I search a file may be in Present
  Directory or in its Sub-Directories.

(This is a variant of a real question I've seen posted on one site.)
To be more specific: The OP wants you to write a program that accepts a string and a directory. It will traverse all files in the directory and recursively all its subdirectories. For each file it will check if the file contains the string, and if it does, will print the name of the file. (The program can have additional features as long as they are relevant to the main goal, if you wish.) There are no requirements on the traversal order.
However, the main task of this puzzle is to hide into the program additional code that will make a fool of the person that asks for the program in the eyes of its users/colleagues/boss/etc. For example, print a humiliating text at some point, such as: The author of the program doesn't know how to program, should return his/her diploma and get fired. Be creative.
Rules:

The solution must not be harmful (except making fool of the OP, of course). It must not do any irreversible damage to end users (no stuff like rm -rf)! Such solutions will be disqualified.
The trolling stuff should be hidden so that the OP won't find it easily.
It shouldn't be obvious that you're trolling the OP. The code should look genuine.
The solution must come with a proper explanation how it trolls the OP so that everybody can learn something from your solution. The explanation should be hidden in a hidden-until-you-click text (spoilers). When judging, try to discover the trolling without looking at the explanation and vote for those that are difficult to discover.
Also try to hide the trolling from the OP if (s)he tries to run the code a few times. Perhaps start trolling only after a particular date, or under some conditions that a sloppy programmer won't test. Be creative and don't forget to explain the trick.
Don't just create a script using existing tools such as grep or find. Write the program from scratch. Better avoid libraries and prefer low-level calls - this will make the code more complex and gives you the opportunity to hide the evil stuff there.

This is a popularity-contest. Please judge according the above points.

How does "will make a fool of the person that asks for the program in the eyes of its users/colleagues/boss." and "should return his/her diploma and get fired." square with "The solution must not be harmful, must not do any damage to its users"?

I appreciate that you've put in more effort than most posters of "trolling" questions, but all questions on this site should have a clear specification and "how can I search a file may be in present directory" is nowhere near meeting that standard. (Whether any code-trolling question can meet that standard is a separate issue).

@PeterTaylor I tried to give a more specific assignment. If you have more specific suggestions, I'll appreciate them.

"Hide evil code" - evil implies harmful.

@emory the coder is not the user. Humiliating the coder in front of his fellow coders without effecting the clients is possible.

I'm voting to close this question as off-topic because it is [tag:underhanded].

I'm voting to close this question as off-topic because It's code trolling.

Here is my solution (in Perl):
#! /usr/bin/perl -w

use Cwd 'abs_path';

# Check the command line arguments
my $F = abs_path($0);
if ($#ARGV!=1) {
    print "Usage: ".$F." <dir> <expr>\n";
    exit(1);
}

# The first argument is the directory
my @u = (abs_path($ARGV[0]));
# Check for trailing slash
my $c = substr $u[0], -1, 0;

# Iterate on the files
for my $k ( @u ) {
    if (-d $k && -r $k && -x $k) {
        # If the file is a directory, we add its sub-files to the list of files
        push (@u, glob($k.($c eq "/" ? "*" : "/*")));
    } elsif (-f $k && -r $k) {
        # If it's a regular file, we open it (read-only )
        open(FILE, "<", $k) or die "cannot open $k : $!";
        # Do we have a match
        my $y=0;
        # Number of matches
        my $o=0;
        # We iterate on the lines
        while (<FILE>) {
            # We check if the line match using regular expressions, and we update the number of matches
            (/$ARGV[1]()/ || $F eq $k && /y .([F c-y])/) && (($c,$y,$o)=($c.$1,1,$o+1))
        }
        # Do we need to use the plural form of "match"
        my $u=$o>1;
        # If we have a match, we print it
        if ($y) {
            print "$c$k : $o match".($u?"es\n":"\n");
        }
        # Close the file (opened read-only )
        close(FILE) or die "cannot close $k : $!";
    }
}

The first argument of the program is the directory and the second argument is the string we are looking for. The program also show the number of matches in each file.
Here is how to search "VGA" in /etc:
$ ./mygrep.pl /etc VGA
/etc/alternatives/mplayer : 7 matches
/etc/alternatives/pinentry : 1 match
/etc/alternatives/pinentry-x11 : 1 match
/etc/alternatives/www-browser : 1 match
/etc/bumblebee/xorg.conf.nouveau : 2 matches
/etc/bumblebee/xorg.conf.nvidia : 2 matches
/etc/default/console-setup : 2 matches
/etc/htdig/english.0 : 1 match
/etc/X11/X : 6 matches
/etc/laptop-mode/conf.d/video-out.conf : 3 matches
$

And now, here is the trick :

 The program works exactly as advised as long as it doesn't encounter itself in the files. As soon as it encounters itself, it starts to prefix each file found with insanity.
 Let's copy some files in the current directory and try again :
 $ cp /etc/default/console-setup /etc/bumblebee/xorg.conf.nouveau /etc/bumblebee/xorg.conf.nvidia /etc/htdig/english.0 ./
$ ./mygrep.pl ./ VGA
/tmp/mygrep/console-setup : 2 matches
/tmp/mygrep/english.0 : 1 match
Fuck you /tmp/mygrep/mygrep.pl : 9 matches
Fuck you /tmp/mygrep/xorg.conf.nouveau : 2 matches
Fuck you /tmp/mygrep/xorg.conf.nvidia : 2 matches
$
 This is due to this code:
 $F eq $k && /y .([F c-y])/
 It tests if the current file is the running program, and if it is, it extract some part of the program with a regexp and affects it to $c with
 $c = $c.$1
 What is extracted by the regexp are the variable declarations (variables are named $F, @u, $c, $k, $y, $o, $u) and two spaces from the comments.
 I had to do that to keep it hidden, even if the program is relatively short.

Haha, this is epic.


text:
How long does it take to paint a stick?
(Based on this Math.SE problem, which also provides some graphics)
I have a stick which looks kinda like this:

I want it to look kinda like this:

I'm not an expert painter, however, so before I start such an ambitious DIY project, I want to make sure that I'm not in over my head.
Your program should tell me how  how many steps are involved in painting this stick.  Each step involves painting a continuous area with a solid color, which covers up previous layers of paint.  For the above example, I could paint the left half blue, the right half red, and then the two separate green areas for a total of 4 steps (the green is not continuously painted).

Here it is in ASCII:
------
bbb---
bbbrrr
bgbrrr
bgbrgr

There are a couple different ways to paint this stick and end up with the same result.  I'm only interested in the time estimate, however, which is four steps.
Goal
Your program should output the minimum number of steps needed to paint a stick with a given color scheme.  The paint scheme will be in the form of a string of characters, while output will be a number. This is code golf.  Shortest program wins.
Input
Your program will receive the coloring scheme for a stick in the form of a string of letters.  Each unique letter (case sensitive) represents a unique color.
YRYGR

grG

GyRyGyG

pbgbrgrp

hyghgy

Output
These numbers are the least number of steps needed to paint the sticks.
4

3

4

5

4

Explanations
This is how I arrived at the above numbers.  Your program does not need to output this:
 -----
 YYY--
 YRY--
 YRYG-
 YRYGR

 ---
 g--
 gr-
 grG

 -------
 GGGGGGG
 GyyyGGG
 GyRyGGG
 GyRyGyG

 --------
 pppppppp
 pbbbpppp
 pbbbrrrp
 pbgbrrrp
 pbgbrgrp

 ------
 -yyyyy
 -ygggy
 hygggy
 hyghgy

Edit: I'll add more test cases if they prove to be more difficult test cases.

This reminds me of http://stackoverflow.com/q/10364248/785745, which is similar, but in 2D.

Python 3, 60 59 bytes
p=lambda s:len(s)and-~min(sum(map(p,s.split(c)))for c in s)

Try it online!
Ungolfed:
def paint(stick):
    if not stick:
        return 0
    return 1 + min(
        sum(paint(part) for part in stick.split(c))
        for c in stick
    )

You- you beat GS?!

you can use ...and-~min(...) instead of ...and 1+min(...)to save 1 byte

GolfScript, 82 72 67 characters
.,n*{:c,,{[).2$1<*\c>+1$.,,{).2$<\3$<=},,.@>@@>]}%\;{~S)}%$0+0=}:S~

Reasonably fast for a GolfScript program, examples:
> hyghgy
4

> pbgbrgrp
5

The algorithm used works through the colors left-to-right recursively, according to the following statements:

Ignore all parts from the left which already have the required color. Overpainting them again will not provide a better answer.

If the complete stick already has the desired color, return 0 steps as result.

Otherwise, take the target color of the now leftmost part (i.e. the first not in the desired color).

Paint 1 part with the target color and recurse.
Paint 2 parts with this color and recurse.

...

Paint the whole remaining stick with this color and recurse.

Take the minimum of all those numbers and add 1 (for the current step). Return this as the optimal number of steps.

This algorithm works, because the leftmost part has to be painted at one time anyways, so why not do it immediately - in any possible fashion.
.,n*         # prepare the initial situation (target stick, unpainted stick)
             # used n instead of '-' for the unpainted parts, because it is shorter
{            # Define the operator S which does t c S -> n
             #   - t: the desired target colors
             #   - c: the stick as it is colored currently
             #   - n: minimum number of steps required to go from c to t
  :c         # Assign the current configuration to the variable c
  ,,{[       # Map the list [0 1 2 .. L-1]
             # We will build a list of all possible configurations if we paint
             # the stick with the 0th part's color (either 1 or 2 or 3 or ... parts)
    ).       # Increase the number, i.e. we paint 1, 2, 3, ... L parts, copy
    2$1<     # Take the first color of the target configuration
    *        # ...paint as many parts
    \c>+     # ...and keep the rest as with the current stick
    1$       # take the target configuration
             # Top of stack now e.g. reads
             #    h----- hyghgy (for i=0)
             #    hh---- hyghgy (for i=1)
             # Next, we strip the common leading characters from both strings:
    .,,      # Make list [0 1 2 ... L-1]
    {        # Filter {}, all the numbers for which the first j+1 parts are the same
      ).     # incr j
      2$<    # take leftmost j parts of stick A
      \3$<   # take leftmost j parts of stick B
      =      # are they equal?
    },,      # The length of the result is the number of common parts.
    .@>      # cut parts from A
    @@>      # cut parts from B
  ]}%
  \;         # Remove the target from the stack (not needed anymore)
             # We now have a list of possible paintings where 1, 2, ..., L parts were
             # painted from the left with the same color.
             # All configurations were reduced by the common parts (they won't be
             # painted over anyways)
  {~S)}%     # Call the method S recursively on the previously prepared configurations
  $0+0=      # $0= -> sort and take first, i.e. take the minimum, 0+ is a workaround
             # if the list was empty (i.e. the operator was called with a stick of length 0).
}:S
~            # Execute S

+1 for the "colour leftmost wrong" algorithm. However, it seems to be n! steps ;) (but maybe this is the real complexity, I dunno).

JavaScript: 187 Bytes
Assuming we're allowed to just have the input and output to a function (please)!
function p(w){var j,l,s=-1,i,m=i=w.length;if(m<2)return m;for(;i--;){l = 1;for(var k=-1;(j=k)!=m;){if((k=w.indexOf(w[i],++j))==-1)k=m;l+=p(w.substring(j,k));}if(s==-1||l<s)s=l;}return s;}

157 Bytes by doing further ugly optimization (Which is part of the point, and I found incredibly fun):
function p(w){var j,l,s=-1,i,m=i=w.length;if(m<2)return m;for(;i--;s<0|l<s?s=l:1)for(l=1,j=0;~j;)l+=p(w.substring(j,(j=w.indexOf(w[i],j))<0?m:j++));return s}

135 Bytes I realised that the length of the input is an upper bound and I don't need to handle trivial cases separately now.
function p(w){var j,l,s,i,m=s=i=w.length;for(;i--;l<s?s=l:1)for(l=1,j=0;~j;)l+=p(w.substring(j,~(j=w.indexOf(w[i],j))?j++:m));return s}

Test cases:
p("YRYGR")
4
p("grG")
3
p("GyRyGyG")
4
p("pbgbrgrp")
5
p("hyghgy")
4

Expanded version:
function paint(word) {
    var smallest = -1;
    if(word.length < 2) return word.length;
    for(var i = word.length; i-->0;) {
        var length = 1;
        for(var left, right = -1;(left = right) != m;) {
            if((right = word.indexOf(word[i],++left)) == -1) right = word.length;
            if(left != right) length += paint(word.substring(left , right));
        }
        if(smallest == -1 || length < smallest) smallest = l;
    }
    return smallest;
}

For every character of the input, calculate the length of the pattern if we paint that colour first. This is done by pretending we paint that colour and then making sub sections out of the bits that aren't that colour, and recursively calling the paint method on them. The shortest path is returned.
Example (YRYGR):
Initially, try R. This gives us the sub groups Y and YG. Y is trivially painted in one go.
For YG:
Try G, Y is trivial, length 2. Try Y, G is trivial, length 2. YG is therefore length 2.
Painting R first therefore gives us 1 + 1 + 2 = 4
Then try G. This gives us the sub groups YRY and R. R is trivial.
For YRY:
Try Y: R is trivial, length 2. Try R: Y and Y are the two groups, length 3.
YRY is length 2.
Painting G first gives 1 + 1 + 2 = 4
Then try Y. This gives the sub groups R and GR. R trivial, GR is length 2. Y is length 4
This implementation would then check R and Y again to reduce code length. The result for YRYGR is therefore 4.

I think your expanded version lost the var m somewhere.

Unfortunately, also your version does not give the correct result for input "abcacba".

@Hasturkun m was just shorthand for word.length :)
@Howard You're correct, I shall have to re-think this.

*waits 7 years*

CoffeeScript - 183 247 224 215 207
x=(s,c='')->return 0if !s[0]?;return x s[1..],c if s[0]is c;l=s.length;return x s[1...l],c if s[l-1]is c;i=s.lastIndexOf s[0];1+(x s[1...i],s[0])+x s[i+1..],c
y=(z)->z=z.split "";Math.min (x z),x z.reverse()

Demo on JSFiddle.net
Ungolfed version including debug code and comments:
paintSubstring = (substring, color = '####') ->
  console.log 'Substring and color', substring, color, substring[0]
  # no need to color here
  if !substring[0]?
    return 0
  # no need to recolor the first part
  if substring[0] is color
    return paintSubstring (substring[1..]), color
  l = substring.length
  # no need to recolor the last part
  if substring[l-1] is color
    return paintSubstring substring[0...l], color
  # cover as much as possible
  index = substring.lastIndexOf substring[0]
  part1 = substring[1...index]
  part2 = substring[index+1..]
  console.log 'Part 1:', part1
  console.log 'Part 2:', part2
  # color the rest of the first half
  p1 = paintSubstring part1, substring[0]
  # color the rest of the second half, note that the color did not change!
  p2 = paintSubstring part2, color
  # sum up the cost of the substick + this color action
  return p1+p2+1
paintSubstringX=(x)->Math.min (paintSubstring x.split("")), paintSubstring x.split("").reverse()
console.clear()
input = """YRYGR
grG
GyRyGyG
pbgbrgrp
aaaaaaaa
hyghgy""".split /\n/
for stick in input
  console.log paintSubstringX stick

Appears to return an incorrect result for hyghgy.  It  says 5 but it should be 4.  (however, it returns the correct result of 4 for hyghgyh).

@PhiNotPi God, this pushed me back over 60 characters :( Trying to reimplement this in another language, after taking a nap.

Python, 149 chars
D=lambda s:0 if s=='?'*len(s)else min(1+D(s[:i]+'?'*(j-i)+s[j:])for i in range(len(s))for j in range(i+1,len(s)+1)if set(s[i:j])-set('?')==set(s[i]))

I use ? to mark an area that may be any color.  D picks a contiguous region of the stick that contains only a single color (plus maybe some ?s), colors that region last, replaces that region with ?s, and recurses to find all the previous steps.
Exponential running time.  Just barely fast enough to do the examples in a reasonable time (a few minutes).  I bet with memoization it could be much faster.

Python 3 - 122
def r(s,a):c=s[0];z=c in a;return s[1:]and min([1+r(s[1:],a+c)]+[r(s[1:],a[:a.rfind(c)+1])]*z)or(1-z)
print(r(input(),''))

It seems to work, but I'm still not 100% sure that this method will always find the minimum number of steps.

Haskell, 118 86 characters
p""=0
p(a:s)=1+minimum(map(sum.map p.words)$sequence$map(a%)s)
a%b|a==b=b:" "|1<3=[b]

Test runs:
λ: p "YRYGR"
4

λ: p "grG"
3

λ: p "GyRyGyG"
4

λ: p "pbgbrgrp"
5

λ: p "hyghgy"
4

λ: p "abcacba"
4

This method isn't even all that inefficient!

Haskell, 143 chars
f s=g(r n ' ')0where{r=replicate;n=length s;g p l=minimum$n:[0|p==s]++[1+g(take i p++r(j-i)(s!!i)++drop j p)(l+1)|l<n,i<-[0..n-1],j<-[i+1..n]]}

This tries all possible rewritings up to the length of the string, and goes until it finds one that constructs the input pattern. Needless to say, exponential time (and then some).

A simple breadth first search. It doesn't put anything on the queue that's already been seen. It works in under a second for all of the examples but 'pbgbrgrp' which actually takes a full minute :(
Now that I have something that works I'll be working on finding something faster and shorter.
Python - 300 296
def f(c):
 k=len(c);q=['0'*99];m={};m[q[0]]=1
 while q:
  u=q.pop(0)
  for x in ['0'*j+h*i+'0'*(k-j-i) for h in set(c) for j in range(1+k) for i in range(1,1+k-j)]:
   n=''.join([r if r!='0' else l for l,r in zip(u,x)])
   if n == c:
     return m[u]
   if not n in m:
    m[n]=m[u]+1;q.append(n)

Can you please check the indentation? It seems to be broken.

@Howard fixed. I have no idea what I was thinking last night.

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


text:
Array Merge without Duplicates
I recently saw this Javascript code on StackOverflow for merging two arrays, and removing duplicates:
Array.prototype.unique = function() {
    var a = this.concat();
    for(var i=0; i<a.length; ++i) {
        for(var j=i+1; j<a.length; ++j) {
            if(a[i] === a[j])
                a.splice(j--, 1);
        }
    }
    return a;
};

var array1 = ["Vijendra","Singh"];
var array2 = ["Singh", "Shakya"];
var array3 = array1.concat(array2).unique();

While this code works, it is horribly inefficient (O(n^2)). Your challenge is to make an algorithm with less complexity.
The winning criteria is the solution with the least complexity, but ties will be broken by shortest length in characters.
Requirements:
Package all your code together in a function that meets the following requirements for "correctness:"

Input: Two arrays
Output: One array
Merges elements of both arrays together- Any element in either input array must be in the outputted array.
The outputted array should have no duplicates.
Order doesn't matter (unlike the original)
Any language counts
Don't use the standard library's array functions for detecting uniqueness or merging sets/arrays (although other things from the standard library is okay). Let me make the distinction that array concatenation is fine, but functions that already do all of the above are not.

How are we supposed to create or append to an array without using array functions?

@EmilVikström See my edit. I meant that you can't use array uniqueness functions. Sorry for being unclear.

If one of the arrays has duplicates in it, do we remove them as well? For example, should merging [1, 2, 2, 3] and [2, 3, 4] return [1, 2, 2, 3, 4] or [1, 2, 3, 4]?

@O-I The second output is the correct one. The outputted array should have no duplicates.

So, I'm guessing simply doing arr1 | arr2 in Ruby is against the rules?

@O-I Yes, that would make it too easy.

May I ask: Arrays of what?  Can we assume simply integers or strings, or do we also have to allow more complex things like multilevel objects?

@jawns317 Assume that the components of the arrays are primitives- integers, strings, floats, or bools.

Does using a function like Mathematica's DeleteDuplicates count as a uniqeness function?

@YvesKlett Yes. That kind of defeats the whole purpose of finding a more efficient algorithm.

It need to realize a merge sort with Worst-case performance ~ O(n log n). Boring.

Perl27 Characters
Simple Perl Hack
my @vals = ();
push @vals, @arr1, @arr2;
my %out;
map { $out{$_}++ } @vals;
my @unique = keys %out;

I'm sure someone could one-liner this.. and thus (Thanks Dom Hastings)
sub x{$_{$_}++for@_;keys%_}

"Don't use the standard library's array functions for detecting uniqueness (although other things form the standard library is okay)"

How I am violating that rule? I'm not using unique functions?

How does it work, then? Sorry, I can't read perl. If it reads the keys of a hash map - does that count as OK with that rule? I won't vote until convinced that it is.

It combines the arrays, loops over both and adds to a hash incrementing the value who's key is the current value in the array loop. Then it takes the keys of that hash, I have used this in some of my work..
So [1,1,2,3,4,4] becomes { 1 => 2, 2 => 1, 3 => 1, 4 => 2 }

@ZachLeighton you can shorten the code to 27 chars with sub x{$_{$_}++for@_;keys%_} (in case it comes down to a tie!) and use as: z((1,2,3,4),(2,3,4,5,6))

I saw your answer above.. very nicely done.

I've removed my answer, I didn't realise you'd already submitted a Perl solution. Please feel free to utilise this golfed version.

Sure I referenced you in the edit, thanks!

A bit late to the party: sub x{keys{map{$_,1}@_}} for 24. The original could also be improved by one by replacing $_{$_}++ with \$_{$_}.

JavaScript O(N) 131 124 116 92 (86?)
Golfed version:
function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}

Human readable golfed version:
function m(i,x) {
   h = {}
   n = []
   for (a = 2; a--; i=x)
      i.map(function(b){
        h[b] = h[b] || n.push(b)
      })
   return n
}

I could use concat like so and do it in 86 characters:
function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}

But I am not sure if it is still O(N) based on this JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping as the concat version is marginally faster with smaller arrays but slower with larger arrays (Chrome 31 OSX).
In practice do this (golf is full of bad practices):
function merge(a1, a2) {
   var hash = {};
   var arr = [];
   for (var i = 0; i < a1.length; i++) {
      if (hash[a1[i]] !== true) {
        hash[a1[i]] = true;
        arr[arr.length] = a1[i];
      }
   }
   for (var i = 0; i < a2.length; i++) {
      if (hash[a2[i]] !== true) {
        hash[a2[i]] = true;
        arr[arr.length] = a2[i];
      }
   }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));

I'm not great at computing complexity but I believe this is O(N). Would love if someone could clarify.
Edit: Here is a version that takes any number of arrays and merges them.
function merge() {
   var args = arguments;
   var hash = {};
   var arr = [];
   for (var i = 0; i < args.length; i++) {
      for (var j = 0; j < args[i].length; j++) {
        if (hash[args[i][j]] !== true) {
          arr[arr.length] = args[i][j];
          hash[args[i][j]] = true;
        }
      }
    }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));

This is almost exactly what I was gonna post in a couple of seconds :-( Yes, it is amortized linear time if hash tables are implemented with amortized constant time for insertion and searching (which is common in many languages, don't know specifically about JS).

@EmilVikström Thanks for that I believe JavaScript does but don't have proof on it. Apologies for having fast fingers, slowed yourself down with comments :P

This is a great approach. However, could you also provide a "code-golf" style solution in addition to your nicely formatted version? Seeing that multiple people have thought of this as the right approach, there's probably going to be a tie at O(N).

@cloudcoder2000 Ok, I wanted to print a full version as the code-golf version is likely to be less efficient in practice.

@GeorgeReith I'm not really sure what you meant by that... but what I meant by "code-golf" style is that you minify, simplify, and shorten your current O(N) solution.

@GeorgeReith You're second solution appears to be O(N^2).

@cloudcoder2000 It is no different from the first. The only complexity added is looping the argument list. Each array only gets looped once still. It just loops the arg list instead of explicitly stating each one. I get what you mean by code-golf I will post one, what I meant is I wanted a normal version as code-golf enforces bad practices which equal poorer performance at execution time.

@GeorgeReith Thanks for clarifying, and I look forward to seeing what you post. Also, when you have nested for loops, you're pretty much guaranteed to run in polynomial time.

@cloudcoder2000 Added golfed version. I'd love to get some clarification on that but I can't see how there is any difference between the first and second version. With two arrays it still executes a loop on the array once each time. The same code gets executed, just in the first I wrote two seperate loops here I have an outer loop that just runs the inner loop twice. Except with the bonus of supplying an unlimited number of arrays to merge.

@GeorgeReith With only two arrays as input, that is what happens. However, when calculating time complexity, you always look for the worst case scenario. Nested loops are multiplied, so the worst case is O(n^2). I'm not knowledgeable enough about it to explain to you (I don't want to say anything incorrect and give you the wrong idea) but you can look at this link for more info.

@cloudcoder2000 According to the requirements two arrays is the worst possible scenario, this is a controlled input scenario. Seems odd to me. Although I could remove args.length and replace it with 2 if you like... would actually save characters.

@GeorgeReith It is true that for your first function, the worst case is two inputs. However, when you say that the function "takes any number of arrays" then you imply that the input for the function can be multiple arrays- polynomial time. If you mean that your function is only meant for two arrays- linear time- as input, then please describe it accordingly.

@cloudcoder2000 Okay... I actually re-implemented my golfed version which is limited to two arrays (saved me some chars). Thanks for the info, I'm sure you're correct it just seems odd to me.

@cloudcoder2000 @GeorgeReith Looks like it would be O(N) to me even with variable inputs, but you need to be careful with your definition of N. It would be the number of elements contained in all input arrays, not how many input arrays there are.

Why do you have 1 + -- i instead of just i--?

@meiamsome there are two loops, and each one's worst case is independent from the other. So really, shouldn't it be O(N*M)? I'm not certain of this, so please clarify. Either way, it doesn't really matter, because @GeorgeReith provided another solution that is definitively O(N).

@cloudcoder2000 They are not fully independent so the worst case is not O(A*B) (Not using N because it's confusing). It would be that if every input array (every A) had the same amount of elements (B) as it is actually O(SUM(B) FOR ALL A), which can be rewritten as O(N) when defining N as the count of elements of all array inputs.

@cloudcoder2000  Consider m([1,1],[1,1,1,1]) and m([1,1],[1,1],[1,1]). Both would run in almost the same time. This can be extended to any amount of arguments/elements and you can see time is independent of the amount of arguments but dependant on how many elements in all the arrays. They would run at slightly different times due to how many loops are ran and thus how many times variables are altered, but such differences are negligible when using big-O notation assuming B >> A.

@meiamsome That's great to know - that's what my gut tells me, you're definitely better at expressing it than I. 1+--i because I moved the --i into my condition and it would ignore 0 otherwise because the condition gets called before the first iteration - Just squeezing out characters.

@GeorgeReith i-- would perform the loop with i being 1 and then 0 as well, no?

@meiamsome You're right... that's two less characters. I had a reason I couldn't use i-- in one of my earlier versions... I forgot that had changed. Thank you sir.

You should put the golfed version on top since that is the one that's actually 92 characters. Currently, the first code listed contains something like 250 characters.

@KyleKanos Done :)

function m(i,x){h={};i.concat(x).map(function(b){h[b]=1});return Object.keys(h)}

Python 2.7, 38 chars
F=lambda x,y:{c:1 for c in x+y}.keys()

Should be O(N) assuming a good hash function.
Wasi's 8 character set implementation is better, if you don't think it violates the rules.

Nice! Comprehensions in Python can be so elegant and powerful.

PHP, 69/42 68/41 chars
Including the function declaration is 68 characters:
function m($a,$b){return array_keys(array_flip($a)+array_flip($b));}

Not including the function declaration is 41 characters:
array_keys(array_flip($a)+array_flip($b))

One way in Ruby
To keep within the rules outlined above, I would use a similar strategy as the JavaScript solution and use a hash as an intermediary.
merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] ||= el } }.keys

Essentially, these are the steps I'm going through in the line above.

Define a variable merged_arr that will contain the result
Initialize an empty, unnamed hash as an intermediary to put unique elements in
Use Object#tap to populate the hash (referenced as hash in the tap block) and return it for subsequent method chaining
Concatenate arr1 and arr2 into a single, unprocessed array
For each element el in the concatenated array, put the value el in hash[el] if no value of hash[el] currently exists. The memoization here (hash[el] ||= el) is what ensures the uniqueness of elements.
Fetch the keys (or values, as they are the same) for the now populated hash

This should run in O(n) time. Please let me know if I've made any inaccurate statements or if I can improve the above answer either for efficiency or readability.
Possible improvements
Using memoization is probably unnecessary given that the keys to the hash are going to be unique and the values are irrelevant, so this is sufficient:
merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] = 1 } }.keys

I really love Object#tap, but we can accomplish the same result using Enumerable#reduce:
merged_arr = (arr1 + arr2).reduce({}) { |arr, val| arr[val] = 1; arr }.keys

You could even use Enumberable#map:
merged_arr = Hash[(arr1 + arr2).map { |val| [val, 1] }].keys

How I would do it in practice
Having said all that, if I were asked to merge two arrays arr1 and arr2 such that the result merged_arr has unique elements and could use any Ruby method at my disposal, I would simply use the set union operator which is intended for solving this exact problem:
merged_arr = arr1 | arr2

A quick peek at the source of Array#|, though, seems to confirm that using a hash as an intermediary seems to be the acceptable solution to performing a unique merge between 2 arrays.

"Don't use the standard library's array functions for detecting uniqueness (although other things form the standard library is okay)"

How am I violating that rule in the second example? Memoization is being performed on a hash. Is that not allowed either?

Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

A function that would take n arrays could be the following:
function m()
{
  var o={},a=arguments,c=a.length,i;
  while(c--){i=a[c].length;while(i--)o[a[c][i]] = true}
  return Object.keys(o);
}

Golfed, I think this should work ( 117 chars )
function m(){var o={},a=arguments,c=a.length,i;while(c--){i=a[c].length;while(i--)o[a[c][i]]=1}return Object.keys(o)}

Update
If you want to keep the original type, you could
function m()
{
  var o={},a=arguments,c=a.length,f=[],g=[];
  while(c--)g.concat(a[c])
  c = g.length
  while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}
  return f
}

or golfed 149:
function m(){var o={},a=arguments,c=a.length,f=[],g=[];while(c--)g.concat(a[c]);c= g.length;while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}return f}

This still can cast some doubts, if you want to distinguish 123 and '123', then this would not work..

Thanks for the answer. It is impressively short, however this only does half the problem. You also need to include in the solution the actual merging part (even if its the same as in the original example) and put it all together in one function. Also, could you provide "golfed" version in addition to this (as it is O(N))?

This casts all members into strings. e.g. m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7]) becomes ["1", "2", "3", "4", "5", "6", "7"]

Mathematica 10 Chars
Union[a,b]

Example:
a={1,2,3,4,5};
b={1,2,3,4,5,6};
Union[a,b]

{1, 2, 3, 4, 5, 6}

Mathematica2 43 Chars
Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}

I think this would go in the category of using standard library array methods.

Hi @cloudcoder2000. No need to call some specific library to use Union in Mathematica.

In my opinion, using a builtin function to do exactly what the question is asking to do is cheating.

ok ok .. the second code do not use Union.

I guess Tally[Join[a, b]][[;; , 1]] would also be cheating ;-)  BTW you could save chars by using single-letter variables.

@YvesKlett! Done!..

python,46
def A(a,b):print[i for i in b if i not in a]+a

Or, using set operation simply
python, 8
set(a+b)

Sorry it wasn't clear, using set operations is also cheating.

Your 1st code will have duplicates if there are duplicates in a or if there are duplicates in b and that element is not in a.

Fortran: 282 252 233 213
Golfed version:
function f(a,b,m,n) result(d);integer::m,n,a(m),b(n),c(m+n);integer,allocatable::d(:);j=m+1;c(1:m)=a(1:m);do i=1,n;if(.not.any(b(i)==c(1:m)))then;c(j)=b(i);j=j+1;endif;enddo;allocate(d(j-1));d=c(1:j-1);endfunction

Which not only looks infinitely better but will actually compile (too long a line in its golfed form) with the human-readable form:
function f(a,b,m,n) result(d)
  integer::m,n,a(m),b(n),c(m+n)
  integer,allocatable::d(:)
  j=m+1;c(1:m)=a(1:m)
  do i=1,n
     if(.not.any(b(i)==c(1:m)))then
        c(j)=b(i);j=j+1
     endif
  enddo
  allocate(d(j-1))
  d=c(1:j-1)
end function

This should be O(n) as I copy a into c and then check each b against all of c. The last step is to eliminate the garbage that c will contain since it is uninitialized.

Perl
23 bytes, if we only count the code block inside subroutine. Could be 21, if overwriting global values is allowed (it would remove my from the code). It returns elements in random order, because order doesn't matter. As for complexity, on average it's O(N) (depends on number of hash collisions, but they are rather rare - in worst case it can be O(N2) (but this shouldn't happen, because Perl can detect pathological hashes, and changes the hash function seed when it detects such behavior)).
use 5.010;
sub unique{
    my%a=map{$_,1}@_;keys%a
}
my @a1 = (1, 2, 3, 4);
my @a2 = (3, 4, 5, 6);
say join " ", unique @a1, @a2;

Output (also showing randomness):
/tmp $ perl unique.pl
2 3 4 6 1 5
/tmp $ perl unique.pl
5 4 6 2 1 3

Javascript 86
Golfed version:
function m(a,b){var h={};return a.concat(b).filter(function(v){return h[v]?0:h[v]=1})}

Readable version:
function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}

This ignores falsey values... m([1,0,0,0,0],[0,1,0]) returns [1].

Change h[v]=v to h[v]=1.

Well spotted @GeorgeReith! We went from 86 to 84 :)

It's still 86, I think you got confused because you removed 2 characters from the readable version not the golfed one.

JavaScript 60
I'm using ES6 generator.
The following is testable using Google's Traceur REPL.
m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}

APL (Dyalog Unicode), O(N), 28 bytes
Anonymous tacit infix function.
(⊢(/⍨)⍳∘≢=⍳⍨),

Try it online!
, concatenate the arguments; O(N)
(…) apply the following anonymous tacit function on that; O(1)
   ⍳⍨ indices selfie (indices of first occurrence of each element in the entire array); O(N)
  = compare element by element to; O(N):
   ⍳∘≢ indices of the length of the array; O(N)
 (/⍨) use that to filter; O(N):
  ⊢ the unmodified argument; O(1)
O(N + 1 + N + N + N + N + 1) = O(N)

If you're looking for a JavaScript-based implementation that relies on the underlying Objects behind the framework to be efficient, I would've just used Set. Usually in an implementation, the Set object inherently handles unique objects during insertion with some sort of binary search indexing. I know in Java it's a log(n) search, using binary search based on the fact that no set can contain a single object more than once.

While I have no idea if this is also true for Javascript, something as simple as the following snippet may suffice for an n*log(n) implementation:
JavaScript, 61 bytes
var s = new Set(a);      // Complexity O(a.length)
b.forEach(function(e) {  // Complexity O(b.length) * O(s.add())
  s.add(e);
});

Try it online!

If the above snippet uses a = [1,2,3] and b = [1,2,3,4,5,6] then s=[1,2,3,4,5,6].
If you know the complexity of the Set.add(Object) function in JavaScript let me know, the complexity of this is n + n * f(O) where f(O) is the complexity of s.add(O).


text:
Self-contained hello-world program
I want a program that outputs "hello world" on console on my x86_64 based Linux computer. Yes, a complete program, not something silly that needs an interpreter or a compiler to work.
You may:

use all glibc functionality
submit a static executable
submit a dynamic executable with dependencies if you outline them
compile an ELF file
dig into the ELF format and remove all unneeded stuff
be creative and work around the ELF format

Describe here how you create and execute the program.
The shortest program wins.

Similar: http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html

@PeterTaylor The page I immediately thought of when reading this. Thanks for digging it up before me.

@breadbox is a high-rep user on our site. I'm sure they'll nail this one. ;-)

Too bad you specified the platform :)

@marinus why is this a bad thing?

marinus may use any platform he likes to go below the 45 bytes from http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html

why not write your own platform? Thingy should fit into a bootsector :) 0x001d bytes: http://www.staerk.de/thorsten/How_to_program_your_own_OS plus two bytes boot sector signature

and sorry for calling this an OS, back in 2008 I was a bit ignorant

MS-DOS .COM - 21 bytes
From the comments:

marinus may use any platform he likes to go below the 45 bytes from muppetlabs.com/~breadbox/software/tiny/teensy.html – Thorsten Staerk

So now I had to. (So don't accept this answer because it's cheating.)
He made a mistake, because that allows me to do:
BITS 16
              org     0x100
              mov     ah,9
              mov     dx,hello
              int     0x21
              int     0x20
hello:        db      "hello world$"

Compile with:
nasm -f bin -o hello.com hello.asm

And then DOSBOX or something will run the resulting .com, which is 21 bytes in size.
No hacks are even needed because .com files have no structure.

no mistake... I had it in my mind somewhere... I used to write programs with debug.exe... nopret.com, 2 bytes

that was why 70,000 bytes are not possible as .com program... and .com is not part of any URL ;)

the rules don't say that it has to terminate.  You can remove the int 0x20.

at the very least, the int 0x20 can be a ret.

This is what you had in mind? Or you want any more hacky?
EDITED(2)
Assembler (NASM) { source: 155 bytes, compiled: 384 bytes }
Source code: helloworld.nasm
global _start
_start:
write:
 mov eax, 4
 mov ebx, 1
 mov ecx, h
 mov edx, 12
 int 0x80
exit:
 mov eax, 1
 mov ebx, 0
 int 0x80
h: db 'hello world', 10, 0

Compile
$ nasm helloworld.nasm -f elf64 -o helloworld.o
$ ld helloworld.o -s -o helloworld

Execution
$ ./helloworld
hello world

Size
$ ls -al helloworld.nasm helloworld
-rw-rw-r-- 1 user user 155 Jan  5 11:08 helloworld.nasm
-rwxrwxr-x 1 user user 384 Jan  5 11:09 helloworld

Platform:
$ uname -io
x86_64 GNU/Linux
$ nasm -v
NASM version 2.09.10 compiled on Oct 17 2011

use nasm as assembler and get it much smaller

ok, edited as EDITED(2)

Assembly - compiled: 76 bytes
This is a 32-bit executable, but taking advantage of backwards compatibility it will run on x86_64 systems too. At least it did on mine. It's based on breadbox's "tiny.asm" and it's hackier still so I wouldn't be that surprised if some Linuxes didn't want to touch it.
I tried it on Debian 7 in a VM, and it worked.
BITS 32
              org     0x00200000
              db      0x7F, "ELF"
hello:        db      "hello world", 10
              dw      2
              dw      3
              ; nasm insisted on aligning them properly so let's do it this way
exit:         dd      0x80cd4066 ; inc eax - int 0x80
              dd      start
              dd      phdr - $$
phdr:         dd      1
              dd      0
              dd      $$
              dw      1
              dw      0
              dd      filesize
              dd      filesize
start:        mov     ecx, hello ; B9 0400 0200 -> flag 1 set -> executable
              mov     edx, 12
              inc     eax
              shl     eax,2
              int     0x80
              xor     eax, eax
              jmp     exit
filesize      equ     $ - $$

It actually works:
~$ nasm -f bin -o hello hello.asm;chmod +x hello
~$ ./hello
hello world
~$ wc -c hello
76 hello
~$

It even neatly outputs a newline as I had a byte to spare in the ELF header.

Just tried it, works for me on an i7 running 64-bit Ubuntu 14.04 LTS.

No output on tio


text:
write an "operating system" that dims Num Lock
I want to write x86 assembler code that can be used to boot your computer from and dims NumLock. This means

you cannot rely on glibc or any other of these "comfi" libraries
you cannot rely on the Linux kernel
we will test your code by dumping it onto a virtual floppy and boot a VM from it
goal is to switch on and off NumLock so quickly that it appears dimmed
it's okay if everything fits into the bootloader and loops endlessly

Solution with most votes wins.

I know you think "dim numlock - that's easy" but it is not. So much has to happen to get that far, like scanning for devices and drivers for them. A PS2 keyboard might be easier but I digress. I could make a z80 output "Hello world!" via a UART easily though :P

wow good comment... I did dim NumLock once and thought I knew it was easy. But that was maybe specific to my DIN keyboard (DIN was the predecessor for PS/2 at least in Germany).

doesn't the BIOS give you an address where to write the NumLock? If not, how would you do it e.g. in the boot loader? Now I am curious to solve my own excercise :)

use port 60: http://stackoverflow.com/questions/3434827/assembly-keyboard-io-port

I haven't tested this (VirtualBox doesn't pass through its virtual keyboard LEDs onto the physical keyboard, and I'm not on a PC I can reboot currently). But I think it should probably work and is probably quite minimal.
There may be some additional setup that needs to be done on the keyboard controller for these commands to work. If so it would be essentially trivial to add to the code below...
[bits 16]
[org 0x7c00]
mov al, 0xed
out 0x60, al
mov al, 0x07
out 0x60, al
mov al, 0xed
out 0x60, al
mov al, 0x00
out 0x60, al
jmp $$
times 510 - ($ - $$) db 0
dw 0xaa55

Compile with nasm -f bin -o floppy.img numlock.asm.
Will give this a real test and tweak accordingly later (if someone else wants to try and/or tweak it feel free).

works on my laptop. My laptop's numlock goes on an off.  No external keyboard needed. Also scroll lock and caps lock. Good trick with times 510 - ...