text:
Formatting a Lisp-like Syntax
Background
(Based on a true, heart-wrenching story)
In my time, I've played around with Lisp and similar languages often. I've written with them, ran them, interpreted them, designed them, and made machines write with them for me... And if there is one thing that bothers me, it's seeing Lisp that does not comply with my specific formatting style.
Unfortunately, some text editors (cough XCode cough) tend to strip my beautiful tabs and spaces whenever code is copied and pasted... Take this beautifully spaced Lisp-like syntax:
(A
    (B
        (C)
        (D))
    (E))

(Where ABCDE are arbitrary functions)
SOME text editors butcher this lovely code to the following end:
(A
(B
(C)
(D))
(E))

What a mess! That's not readable!
Help me out, here?
The Challenge
Your goal in this challenge is to take a series of functions separated by newlines in a format described below and return a more beautiful arrangement that highlights readability and elegance.
The Input
We define a function F of arity N arguments as a construct similar to the following:
(F (G1 ...) (G2 ...) (G3 ...) ... (GN ...))

where G1, G2, ..., GN are all functions in and of themselves. An arity 0 function A is simply (A), while an arity 2 function B is of the form (B (...) (...))
Your code should take input as a series of functions with a single newline before every function's leading parenthesis (except for the first function). The example above is valid input.
You may assume:

The parentheses are balanced.
A function will never have to be indented more than 250 times.
EVERY function is surrounded by parentheses: ()
A function's name will only contain printable ASCII characters.
A function's name will never contain parentheses or spaces.
There is an optional trailing newline on input.

The Output
Your code should output the same set of functions, where the only changes made are the additions of spaces or tabs before the leading parentheses of functions.
Output should comply with the following rules:

The first function (and later top-level functions) given should have no preceding spaces
An argument to a function's horizontal location is exactly one tab to the right of that function's horizontal location.
A tab is implementation-defined, but must be at least 3 spaces.
You may optionally print a maximum of two spaces after each line.

Rules

This is code-golf: the shortest code wins!
Standard Loopholes are disallowed.

Examples
Input:
(A
(B
(C)
(D))
(E))

Output:
(A
    (B
        (C)
        (D))
    (E))

Input:
(!@#$%^&*
(asdfghjklm
(this_string_is_particularly_long
(...))
(123456789)))
(THIS_IS_TOP_LEVEL_AGAIN
(HERE'S_AN_ARGUMENT))

Output:
(!@#$%^&*
    (asdfghjklm
        (this_string_is_particularly_long
            (...))
        (123456789)))
(THIS_IS_TOP_LEVEL_AGAIN
    (HERE'S_AN_ARGUMENT))

Input:

(-:0
(*:0
(%:0
(Arg:6)
(Write:0
(Read:0
(Arg:30))
(Write:0
(Const:-6)
(Arg:10))))
(%:0
(Const:9)
(/:0
(Const:-13)
(%:0
(Arg:14)
(Arg:0)))))
(WriteArg:22
(-:0
(Const:45)
(?:0
(Arg:3)
(Arg:22)
(Arg:0)))))

Output:
(-:0
    (*:0
        (%:0
            (Arg:6)
            (Write:0
                (Read:0
                    (Arg:30))
                (Write:0
                    (Const:-6)
                    (Arg:10))))
        (%:0
            (Const:9)
            (/:0
                (Const:-13)
                (%:0
                    (Arg:14)
                    (Arg:0)))))
    (WriteArg:22
        (-:0
            (Const:45)
            (?:0
                (Arg:3)
                (Arg:22)
                (Arg:0)))))

Congrats on making the Hot Network Questions list! :D

@AlexA. Hooray! My dreams have been realized. :D

What if there is no function name, like ()?

Does the indentation have to be >= 3 spaces, or is a tab acceptable?

@isaacg You can assume all functions are named in this case. And whatever your OS/language define to be a horizontal tab is fine. If you use spaces, there must be at least 3. I'll clarify that when I can get to a computer. Thanks!

I'm not sure how to combine A function's name will never contain parentheses or spaces. with A function's name is followed by a maximum of two trailing spaces.. Could you give an example? All test cases seem to contain only newlines, not spaces.

@Dennis I believe that second quote was intended as a "if it is helpful to your program to assume there are trailing spaces, you can have up to 2 of them." You can safely ignore it. I'll clarify in the morning. Thanks!

Can we assume that the indentation level will never go over some limit, e.g. 9999?

@kirbyfan64sos Sure, I've set it to 250 (to fit in one byte) in the question.

Pyth, 24 20 19 18 bytes
FN.z+*ZC9N~Z-1/N\)

Increments a counter for every line, counts total number of closing parentheses encountered so far, and subtracts it from the counter. Then we indent by counter tabs.

@Downvoter Care to explain?

I didn't downvote, but the *4 is a hardcoded and redundant preference. FN.z+*ZC9N~Z-1/N\) lets you use your editor's indent width and saves one byte.

I concur, a tab would be one character shorter. \<tab> or C9.

Common Lisp - 486 414 bytes (Rube Goldberg version)
(labels((p(x d)(or(when(listp x)(#2=princ #\()(p(car x)d)(incf d)(dolist(a(cdr x))(format t"~%~v{   ~}"d'(t))(p a d))(#2# #\)))(#2# x))))(let((i(make-string-input-stream(with-output-to-string(o)(#1=ignore-errors(do(b c)(())(if(member(setq c(read-char))'(#\( #\) #\  #\tab #\newline):test'char=)(progn(when b(prin1(coerce(reverse b)'string)o))(#2# c o)(setq b()))(push c b))))))))(#1#(do()(())(p(read i)0)(terpri)))))

Approach
Instead of doing like everybody else and count parentheses by hand, let's invoke the Lisp reader and do it The Right Way :-)

Read from input stream and write to a temporary output stream.
While doing so, aggregate characters different from (, ) or whitespace as strings.
The intermediate output is used to build a string, which contains syntactically well-formed Common-Lisp forms: nested lists of strings.
Using that string as an input stream, call the standard read function to build actual lists.
Call p on each of those lists, which recursively write them to the standard output with the requested format. In particular, strings are printed unquoted.

As a consequence of this approach:

There are less restrictions on the input format: you can read arbitrarly formatted inputs, not just "one function per line" (ugh).
Also, if the input is not well-formed, an error will be signaled.
Finally, the pretty-printing function is well decoupled from parsing:  you can easily switch to another way of pretty-printing S-expressions (and you should, if you value your vertical space).

Example
Reading from a file, using this wrapper:
(with-open-file (*standard-input* #P"path/to/example/file")
    ...)

Here is the result:
(!@#$%^&*
    (asdfghjklm
        (this_string_is_particularly_long
            (...))
        (123456789)))
(THIS_IS_TOP_LEVEL_AGAIN
    (HERE'S_AN_ARGUMENT))
(-:0
    (*:0
        (%:0
            (Arg:6)
            (Write:0
                (Read:0
                    (Arg:30))
                (Write:0
                    (Const:-6)
                    (Arg:10))))
        (%:0
            (Const:9)
            (/:0
                (Const:-13)
                (%:0
                    (Arg:14)
                    (Arg:0)))))
    (WriteArg:22
        (-:0
            (Const:45)
            (?:0
                (Arg:3)
                (Arg:22)
                (Arg:0)))))

(it seems that tabs are converted to spaces here)
Pretty-printed (golfed version)
Contrary to the safer original version we expect input to be valid.
(labels ((p (x d)
           (or
            (when (listp x)
              (princ #\()
              (p (car x) d)
              (incf d)
              (dolist (a (cdr x)) (format t "~%~v{  ~}" d '(t)) (p a d))
              (princ #\)))
            (princ x))))
  (let ((i
         (make-string-input-stream
          (with-output-to-string (o)
            (ignore-errors
             (do (b
                  c)
                 (nil)
               (if (member (setq c (read-char)) '(#\( #\) #\  #\tab #\newline)
                           :test 'char=)
                   (progn
                    (when b (prin1 (coerce (reverse b) 'string) o))
                    (princ c o)
                    (setq b nil))
                   (push c b))))))))
    (ignore-errors (do () (nil) (p (read i) 0) (terpri)))))

Retina, 89 83 bytes
s`.+
$0<tab>$0
s`(?<=<tab>.*).
<tab>
+ms`^((\()|(?<-2>\))|[^)])+^(?=\(.*^((?<-2><tab>)+))
$0$3
<tab>+$
<empty>

Where <tab> stands for an actual tab character (0x09) and <empty> stands for an empty line. After making those replacements, you can run the above code with the -s flag. However, I'm not counting that flag, because you could also just put each line in its own source file, in which case the 7 newlines would be replaced by 7 penalty bytes for the additional source files.
This is a full program, taking input on STDIN and printing the result to STDOUT.
Explanation
Every pair of lines defines a regex substitution. The basic idea is to make use of .NET's balancing groups to count the current depth up to a given (, and then insert that many tabs before that (.
s`.+
$0<tab>$0

First, we prepare the input. We can't really write back a conditional number of tabs, if we can't find them somewhere in the input string to capture them. So we start by duplicating the entire input, separated by a tab. Note that the s` just activates the single-line (or "dot-all") modifier, which ensures that the . also matches newlines.
s`(?<=<tab>.*).
<tab>

Now we turn every character after that tab into a tab as well. This gives us a sufficient amount of tabs at the end of the string, without modifying the original string so far.
+ms`^((\()|(?<-2>\))|[^)])+^(?=\(.*^((?<-2><tab>)+))
$0$3

This is the meat of the solution. The m and s activate multi-line mode (so that ^ matches the beginnings of lines) and single-line mode. The + tells Retina to keep repeating this substitution until the output stops changing (in this case, that means until the pattern no longer matches the string).
The pattern itself matches a prefix of the input up to an unprocessed ( (that is, a ( that doesn't have any tabs before it, but should). At the same time it determines the depth of the prefix with balancing groups, such that the height of stack 2 will correspond to the current depth, and therefore to number of tabs we need to append. That is this part:
((\()|(?<-2>\))|[^)])+

It either matches a (, pushing it onto the 2 stack, or it matches a ), popping the last capturing from the 2 stack, or it matches something else and leaves the stack untouched. Since the parentheses are guaranteed to be balanced we don't need to worry about trying to pop from an empty stack.
After we've gone through the string like this and found an unprocessed ( to stop at, the lookahead then skips ahead to the end of the string, and captures tabs into group 3 while popping from the 2 stack until its empty:
(?=\(.*^((?<-2><tab>)+))

By using a + in there, we ensure that the pattern only matches anything if at least one tab should be inserted into the match - this avoids an infinite loop when there are multiple root-level functions.
<tab>+$
<empty>

Lastly, we just get rid of those helper tabs at the end of the string to clean up the result.

This is very cool. Well done! It's always a pleasure to see Retina.

C: 95 94 characters
It's not very golfed yet, and from the question I'm unsure whether tabs are acceptable, which is what I use here.
i,j;main(c){for(;putchar(c=getchar()),c+1;i+=c==40,i-=c==41)if(c==10)for(j=i;j--;putchar(9));}

Ungolfed:
i,j;
main(c){
  for(
    ;
    putchar(c=getchar()),
    c+1;
    i+=c==40,
    i-=c==41
  )
    if(c==10)
      for(
        j=i;
        j--;
        putchar(9)
      );
}

Edit: Made it so that it quits on EOF.

Tabs are perfectly acceptable.

Could you use if(c<11) instead of if(c==10)?

Julia, 103 99 97 94 88 bytes
p->(i=j=0;for l=split(p,"\n") i+=1;println("\t"^abs(i-j-1)*l);j+=count(i->i=='\)',l)end)

This defines an unnamed function that accepts a string and prints the indented version. To call it, give it a name, e.g. f=p->.... Note that the input must be a valid Julia string, so dollar signs ($) must be escaped.
Ungolfed + explanation:
function f(p)
    # Set counters for the line number and the number of close parens
    i = j = 0

    # Loop over each line of the program
    for l in split(p, "\n")
        # Increment the line number
        i += 1

        # Print the program line with |i-j-1| tabs
        println("\t"^abs(i-j-1) * l)

        # Count the number of close parens on this line
        j += count(i -> i == '\)', l)
    end
end

Example, pretending each set of four spaces is a tab:
julia> f("(A
(B
(C)
(D))
(E))")

(A
    (B
        (C)
        (D))
    (E))

Any suggestions are more than welcome!

Haskell, 83 81
unlines.(scanl(\n s->drop(sum[1|')'<-s])$n++['\t'|'('<-s])"">>=zipWith(++)).lines

a very points free solution.

you can just drop h=.

Perl, 41
$_="\t"x($i-$j).$_;$i+=y/(/(/;$j+=y/)/)/

40 characters +1 for -p.
Run with:
cat input.txt | perl -pe'$_="\t"x($i-$j).$_;$i+=y/(/(/;$j+=y/)/)/'

Python 2 - 88 78 Bytes
Fairly straightforward (and not very short) solution:
l=0
for x in raw_input().split():g=x.count;d=l*'\t'+x;l+=g("(")-g(")");print d

A couple tips: 1) You can use '\t' instead of '   ' and save one byte; 2) no need to assign input.split() to a variable, since it's only used once (same for c, as well as d--just move the print statement); 3) operator precedence means parentheses around l*c aren't needed.  Also, it looks like f isn't used for anything--is that a relic of a previous version?

Also, if this is Python 2, you'll need to use raw_input instead of input (and don't forget the parentheses after it!).

CJam, 20 bytes
r{_')e=NU)@-:U9c*r}h

Try it online in the CJam interpreter.
How it works
r                    e# Read a whitespace-separated token R from STDIN.
{                 }h e# Do, while R is truthy:
  _')e=              e#   Push C, the number of right parentheses in R.
       NU            e#   Push a linefeed and U (initially 0).
         )@-         e#   Compute U + 1 - C.
            :U       e#   Save in U.
              9c*    e#   Push a string of U tabulators.
                 r   e#   Read a whitespace-separated token R from STDIN.


text:
Find the Fenceposts
Background
An atomic bomb has exploded near the fencepost factory!
Since fenceposts are essential for the survival of our civilization, we must rescue as many as possible.
We are sending radiation-resistant robots to search the area, and it is your task to program their artificial vision.
Input
Your input is a rectangular grid of the characters |-#, representing two kinds of fencepost parts and rubble, given as a newline-delimited string.
The fenceposts have been horribly maimed by the explosion, and some have even been fused together by the heat.
We define a candidate fencepost to be either a horizontal pattern that starts and ends in | and has one or more -s between them (like |-| or |---| but not ||), or a vertical pattern that starts and ends in - and has one or more |s between them (essentially a horizontal candidate fencepost rotated 90 degrees).
An actual fencepost is a candidate fencepost which does not share any of its parts with another candidate fencepost.
Output
Your output is the number of actual fenceposts in the input grid.
Example
Consider the input grid
|#|-|#|##
#||--|||#
###|#|--#
###-||--|
-#-|#-|#-
#---#-#-|
#-#-|#--|

There are 5 candidate fenceposts in this grid, but only 2 of them are actual fenceposts (shown in bold).
Thus the correct output is 2.
Rules
You can write either a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Additional Test cases
Input:
##--
||##
-#|-
|#|#

Output: 0 (0 candidate fenceposts)
Input:
-##|-##--
#|#-|#||-
--|-#|#||
##||||-##
||#|--|-|
-#|-#--|#
|####|#-#

Output: 0 (5 candidate fenceposts)
Input:
#|--|---|-|#
####|##--||-
-|-##||#|---
-#|#-|-#-|||
#|-##--###|-
---#-||-#-##
#|---|###|-#
-|---#-#|#|#
|#--|####-|-

Output: 4 (8 candidate fenceposts)
Input:
-|-||---##|#
---|######-#
####-##|#--|
|||##|#-||||
####-#-||-#|
---#--|#-#--
-|#-####-##-
#||-|-|-###|
|-##||-||-#-

Output: 5 (7 candidate fenceposts)
Input:
|#-|#|#-###|#-#
----#####|#----
|#--#-##-#|##-|
|#-|#-|--##||--
||#-#---##|||##
#|#-|||-#-#--||
--#|-||#|--|#|#
-#-|###||-#--#|
-#||-|#-##||##|
|--|-|||-##|-#|

Output: 4 (9 candidate fenceposts)
Input:
||-|-|-##-#-#-|#--#-
-##|-#|-#-##-|#|--|-
||#---###||-|#|##|-#
#||-#-#-|---|#||#|##
-#-###-##-|-#-|-#||#
##-#--#||-----||-|##
-|--#-#-#|---#-#|#-#
###|-|#-#|-|###|#-|#
#||#-#|--|-||#------
||##|-||#-|--#|#-#-#
|#-|-#-|-|--##-#|||#
-|#--#||##---##|-##-
#|-|-|-||-||#-#-|##-
|-#|##|-|#|#|--||#--

Output: 9 (30 candidate fenceposts)

So are the periods in the |--...--| pattern wildcards?  Does that mean horizontal fences have to have a t least 5 hyphens?  I'm a bit confused by the notation.

@BMac They are supposed to be an ellipsis, meaning that some hyphens are omitted. I agree that it's not the clearest notation. Let me think of something less ambiguous.

If we write a function, may it take one 2D-array argument as input, eg. [[-,|,-],[#,#,-],[-,-,|]]?

@blutorange No, in this challenge it needs to be a single string.

Ruby, 266 268 bytes
To get this started. Makes use of the fact that variables point to objects (a 1-char string for each element of the 2D array) to eliminate overlapping candidates.
Eg. if you execute  a="s";b=a, both a and b point to the same string. "test"=="test" returns true, but "test".equal?("test") returns false, because we have created two different String objects.
->d{c=->d,f,v,u{i=0
r=[]
d.map{|y|j=0
e=[]
y.map{|x|f[j]||=[]
f[j][i]=x
x==v ?e[1]?r<<e+[x]&&e=[x]:e[0]?e=[x]:e<<x :x==u&&e[0]?e<<x :e=[]
j+=1}
i+=1}
r}
y=c[d.split.map(&:chars),f=[],?|,?-]+c[f,[],?-,?|]
y.count{|x|y.all?{|q|x.equal?(q)||!(q+x).uniq!(&:object_id)}}}

Test cases on ideone.

you can use map instead of each

@w0lf thanks, applied. funny thing is, I should have known that...

Python3, 362 bytes:
E=enumerate
def P(b,c,X,Y,n,e):
 try:
  if(C:=b[(x:=c[-1][0]+X)][(y:=c[-1][1]+Y)])in[n,e]:
   K=c+[(x,y)]
   if C==n:yield from P(b,K,X,Y,n,e)
   elif len(c)>1:yield{*K}
 except:1
def f(b):c=[q for x,j in E(b)for y,k in E(j)for q in P(b,[(x,y)],*(k=='-',k!='-'),*['-','|'][::[1,-1][k=='-']])if k in['|','-']];return sum(all(not j&i for j in c if j!=i)for i in c)

Try it online!

Change the return statement to save 5 bytes: sum(all(j in[i,j-i]for j in c)for i in c)

341 bytes, if you optimize string usage in the second function: def f(b):c=[q for x,j in E(b)for y,k in E(j)for q in P(b,[(x,y)],*(k=='-',k!='-'),*['-|','|-'][k=='-'])if'#'!=k];return sum(all(j in[i,j-i]for j in c)for i in c)

Didn't try, but you could save more bytes on the comparisions, if they test for '|' instead of '-'. Vertical bar is higher up in the alphabet than Dash, so you can use '<' for comparisions.

source: Stack Exchange

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

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

sort: votes


text:
Return every N-th word of a string
Your goal is to write a program that, given a number N and a string as input, will return a string containing every Nth word of the original string, starting from the first word.
Sample inputs/outputs:
N = 2, str = "This is a sentence"

"This a"
--
N = 2, str = "The quick brown fox jumped over the lazy dog."

"The brown jumped the dog."
--
N = 7, str = "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa."

"Lorem elit. massa."

You're allowed to assume that the input will always contain at least N+1 words, and that words will always be delimited by the space character  .
This is code-golf, so the shortest answer in bytes wins.

The I/O seems to be underspecified. Are we supposed to read N = 2, str = "This is a sentence" from STDIN?

@Dennis I intentionally left it vague. Take input in whatever way you want; stdin, reading from a file, speech-to-text...

Should have posted first and asked questions later. This contest is already over...

This is a bit too easy IMO... This just becomes a fastest gun in the west contest.

Also, what the hell? Don't accept an answer within 20 minutes! A contest must run for at least a week to allow other submissions.

@orlp: I've undone it; I thought that I should change it if another shorter one comes along. This was my first attempt at a contest, prolly should've used the sandbox first.

What are the possible word separators?

@LuisMendo Space.

Pyth, 6
jd%Qcz

Splits on spaces, takes every Nth element, joins on spaces.
Try it online
Explanation
jd          : join on spaces
  %Q        : take every Qth character (Q will have read the input with N)
    cz      : chop the other input on whitespace

CJam, 7 bytes
q~S/%S*

Test it here. This reads a number and a string (in that order) from STDIN.
Explanation
q~      e# Read and eval input.
  S/    e# Split on spaces.
    %   e# Take every Nth element.
     S* e# Join the words back together with spaces.

Python, 35 characters
lambda n,s:' '.join(s.split()[::n])

It should be a string, not a list, as per the examples.

Whoops, that's right. Fixed.

KDB(Q), 26 bytes
{" "sv#[0N,y;" "vs x][;0]}

Explanation
             " "vs x         / cut x string by space
      #[0N,y;       ]        / cut list by y length
                     [;0]    / take first of each list
 " "sv                       / combine with space
{                        }   / lambda

Test
q){" "sv#[0N,y;" "vs x][;0]}["The quick brown fox jumped over the lazy dog.";2]
"The brown jumped the dog."

Julia, 38 bytes
(n,s)->join(split(s," ")[1:n:end]," ")

This creates an anonymous function that accepts an integer and string as input and returns the required output. To call it, give it a name, e.g. f=(n,s)->....
Ungolfed + explanation:
function f(n, s)
    # Split the string into words
    words = split(s, " ")

    # Get every nth word starting at 1
    every_nth = words[1:n:end]

    # Join into a single string separated with a space
    join(every_nth, " ")
end

Examples:
julia> f(2, "The quick brown fox jumped over the lazy dog.")
"The brown jumped the dog."

julia> f(2, "This is a sentence.")
"This a"

Jelly, 3 bytes (language postdates challenge?)
ḲmK

Ḳ splits the first input on spaces; m takes every nth element; then K joins on spaces again. m is missing a second argument, so it takes the second input by default.
Try it online!

12-basic, 42 bytes
?JOIN(INPUT$().SPLIT(" ")STEP INPUT()," ")

Try

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


text:
Build a poisoned wine testing scheduler
Recently at Puzzling.SE, there was a problem that I wrote about determining which two bottles out of a larger number are poisoned when the poison only activates if both components are drunk. It ended up being quite the ordeal, with most people managing to get it down to 18 or 19 prisoners using completely different algorithms.
The original problem statement is as follows:

You are the ruler of a medieval kingdom who loves throwing parties. The courtier who tried to poison one of your wine bottles last time was furious to learn that you managed to identify which bottle he had poisoned out of 1,000 with just ten prisoners.
This time he's a bit craftier. He's developed a composite poison P: a binary liquid that's only deadly when two individually harmless components mix; this is similar to how epoxy works. He's sent you another crate of 1,000 wine bottles. One bottle has component C_a and another one has component C_b. (P = C_a + C_b)
Anyone who drinks both components will die on the stroke of midnight on the night they drank the final component, regardless of when in the day they imbibed the liquid. Each poison component stays in the body until the second component activates, so if you drink one component one day and another component the next, you will die on midnight at the end of the second day.
You have two days before your next party. What is the minimum number of prisoners you need to use for testing in order to identify which two bottles are tainted, and what algorithm do you need to follow with that number of prisoners?

Bonus
Additionally, suppose that you had a fixed limit of 20 prisoners at your disposal, what's the maximum number of bottles you could theoretically test and come to an accurate conclusion about which bottles were affected?

Your task is to build a program to solve the bonus problem. Given n prisoners, your program will devise a testing schedule that will be able to detect the two poisoned bottles among m bottles, where m is as large as possible.
Your program will initially take as input the number N, the number of prisoners. It will then output:

M, the number of bottles you will attempt to test. These bottles will be labelled from 1 to M.

N lines, containing the labels of the bottles each prisoner will drink.

Your program will then take as input which prisoners died on the first day, with the prisoner on the first line being 1, the next line being 2, etc. Then, it will output:

N more lines, containing the labels of the bottles each prisoner will drink. Dead prisoners will have blank lines.

Your program will then take as input which prisoners died on the second day, and output two numbers, A and B, representing which two bottles your program thinks contains the poison.
An example input for two prisoners and four bottles might go as such, if bottles 1 and 3 are poisoned:
> 2      // INPUT: 2 prisoners
4        // OUTPUT: 4 bottles
1 2 3    // OUTPUT: prisoner 1 will drink 1, 2, 3
1 4      // OUTPUT: prisoner 2 will drink 1, 4
> 1      // INPUT: only the first prisoner died
         // OUTPUT: prisoner 1 is dead, he can't drink any more bottles
3        // OUTPUT: prisoner 2 drinks bottle 3
> 2      // INPUT: prisoner 2 died
1 3      // OUTPUT: therefore, the poisoned bottles are 1 and 3.

The above algorithm may not actually work in all
cases; it's just an example of input and output.

Your program's testing schedule must successfully determine each possible pair of poisoned bottles in order for it to be a valid submission.
Your program will be scored on the following criteria, in order:

The maximum number of bottles it can discern for the case N = 20.

The number of bottles for the case N = 21, and successively higher cases after that.

The length of code. (Shorter code wins.)

How will the input look if more than one prisoner dies on a single day? Neither of your examples covers that case, and the specification is ambiguous to me.

Is it a single line with a space-separated list of prisoners that died?

Does shorter code matter more than number of bottles? Is it productive to increase the length of the code to make it handle one more bottle, as i did in my recent edit?

Number of bottles takes priority. If you make your code longer and more complex to squeeze more bottles in, that is productive.

In the original problem there are only 2 days to solve the problem. Is that also the rule for the challenge? (it severly limits possible solutions, however an unlimited amount of days would be to easy)

The problem statement says, "You have two days before your next party."

Python 2.7.9 — 21 bottles
Assuming that ESultanik's speculation is right on what the input is when multiple prisoners die
r=raw_input;s=str;j=s.join;p=int(r());z=range;q=z(p);x=z(p+1)
print s(p+1)+"\n"+j("\n",(j(" ",(s(a) for a in x if a!=b)) for b in q))
v=r().split();d=[s(a) for a in q if s(a) not in v];d+=[p]if len(d)==1 else [];
print "\n"*p,;r();print j(" ",[s(a) for a in d])

Algorithm: every prisoner drinks from every bottle except their number (1st prisoner doesn't drink first bottle). If they don't die, their number bottle is poisoned. If only one prisoner survives, the extra bottle is poisoned.

Perl 5, 66 bottles
(72 bottles for 21 prisoners)
The prisoners are divided optimally into 2 groups. The bottles are grouped in sets.
Each prisoner of group 1 will drink from all sets except for one.
There will be 1 or 2 survivors. The 1 or 2 sets that weren't drank by them will continue to day 2.
On day 2 the remaining prisoners (including the survivors) drink from all remaining bottles except for one.
When 2 prisoners survive then the bottles they didn't drink are poisoned.
If only 1 prisoner remains then the bottle they all drank is also suspicious.
The code includes extra functionality to facilitate testing.
When the poisened bottles are added as additional parameters, then it won't ask for input about who died.
($p,$f,$l)=@ARGV;
$p=9if!$p;
$m=$p-(2*int($p/4))+1;
$n=$p-$m+2;
$b=$m*(($n+1)/2);
@M=(1..$m);
print"Prisoners: $p\nBottles: $b\n";
# building the sets of items
for$x(@M){
    $j=$k+1;$k+=($n+1)/2;
    $s=join",",($j..$k);
    $A[$x]=$s
}
# assigning the sets to the actors
for$x(@M){
    @T=();
    for$j(@M){if($x!=$j){push@T,split/,/,$A[$j]}}
    print"Prisoner $x drinks @T\n";
    $B[$x]=join",",@T
}
if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=split/ /;
    %h=map{($_,1)}@D;
    @S=grep{!$h{$_}}(@M)
}
else{
    # calculate who dies based on the parameters
    for$x(@M){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@S,$x}
    }
}
for(@D){print"Prisoner $_ dies\n"}

# calculate the remaining items
for(@S){push@R,split/,/,$A[$_]}@R=sort{$a<=>$b}grep{!$g{$_}++}@R;

# different set of actors if there were 1 or 2 sets remaining
if(@S>1){@S=($S[0],$m+1..$p,$S[1],0)}else{@S=($m+1..$p)};

$i=0;@B=@D=();
# assign an item to each actor
for$x(@S){
    @T=();
    for($j=0;$j<@R;$j++){
        if($i!=$j){push@T,$R[$j]}
    }$i++;
    print"Prisoner $x drinks @T\n"if$x>0;
    $B[$x]=join",",@T
}

if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=sort split/ /;
    if(@D<@S-1){push@D,0} # because the set that noone drinks isn't manually put in
    %h=map{($_,1)}@D;
    @L=grep{!$h{$_}}(@S);
}
else{
    # calculate who dies based on the parameters
    @D=();
    for$x(@S){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@L,$x}
    }
}

for(@D){print"Prisoner $_ dies\n"if$_>0}

# calculate the remaining items
for(@L){push@F,split/,/,$B[$_]}
map{$c{$_}++}@F;
for(keys%c){push(@Z,$_)if$c{$_}==1}
@R=sort{$a<=>$b}@Z;

print"Suspected bottles: @R"

Test
$ perl poisened_bottles.pl 20
Prisoners: 20
Bottles: 66
Prisoner 1 drinks 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 2 drinks 1 2 3 4 5 6 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 3 drinks 1 2 3 4 5 6 7 8 9 10 11 12 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 4 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 5 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 7 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 8 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 9 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 10 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 61 62 63 64 65 66
Prisoner 11 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
Who dies: 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 3 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 7 dies
Prisoner 8 dies
Prisoner 9 dies
Prisoner 10 dies
Prisoner 1 drinks 2 3 4 5 6 61 62 63 64 65 66
Prisoner 12 drinks 1 3 4 5 6 61 62 63 64 65 66
Prisoner 13 drinks 1 2 4 5 6 61 62 63 64 65 66
Prisoner 14 drinks 1 2 3 5 6 61 62 63 64 65 66
Prisoner 15 drinks 1 2 3 4 6 61 62 63 64 65 66
Prisoner 16 drinks 1 2 3 4 5 61 62 63 64 65 66
Prisoner 17 drinks 1 2 3 4 5 6 62 63 64 65 66
Prisoner 18 drinks 1 2 3 4 5 6 61 63 64 65 66
Prisoner 19 drinks 1 2 3 4 5 6 61 62 64 65 66
Prisoner 20 drinks 1 2 3 4 5 6 61 62 63 65 66
Prisoner 11 drinks 1 2 3 4 5 6 61 62 63 64 66
Who dies: 1 12 14 15 16 17 18 20 11
Prisoner 1 dies
Prisoner 11 dies
Prisoner 12 dies
Prisoner 14 dies
Prisoner 15 dies
Prisoner 16 dies
Prisoner 17 dies
Prisoner 18 dies
Prisoner 20 dies
Suspected bottles: 3 63

Test without manual input
$ perl poisened_bottles.pl 7 2 5
Prisoners: 7
Bottles: 12
Prisoner 1 drinks 3 4 5 6 7 8 9 10 11 12
Prisoner 2 drinks 1 2 5 6 7 8 9 10 11 12
Prisoner 3 drinks 1 2 3 4 7 8 9 10 11 12
Prisoner 4 drinks 1 2 3 4 5 6 9 10 11 12
Prisoner 5 drinks 1 2 3 4 5 6 7 8 11 12
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 1 drinks 2 5 6
Prisoner 7 drinks 1 5 6
Prisoner 3 drinks 1 2 6
Prisoner 1 dies
Suspected bottles: 2 5

As is tradition, I will post a last-place reference answer.
Python — 7 bottles
prisoners = int(raw_input())

bottles = 0
while (bottles * (bottles + 1) / 2 - 1) <= prisoners:
    bottles += 1

print bottles

pairs = []
for i in range(bottles):
    for j in range(i + 1, bottles):
        pairs += [str(i + 1) + " " + str(j + 1)]

for i in range(prisoners):
    if i < len(pairs):
        print pairs[i]
    else:
        print

dead_prisoner = raw_input()

for i in range(prisoners):
    print
raw_input() # discard the second day entirely

if dead_prisoner == "":
    print pairs[-1]
else:
    print pairs[int(dead_prisoner) - 1]

Make each prisoner drink one possible pair of bottles except for the pair of the last two. If any prisoner dies, the pair that that prisoner drank were the poisoned ones. Otherwise, it was the last two bottles that were poisoned.
For allotments of at least n(n-1)/2 - 1 prisoners, you can do up to n bottles. For n = 7, this lower limit is 20.
We only actually need one day for this solution to work. A two-day solution with a similar scope might get up to 20 bottles for N = 20, but it's too much work for a trivial answer.


text:
Finding Poly Nemo!
Oh no! Nemo, our small clown fish is lost in this ASCII ocean and his dad Marlin is trying to find him.
Your task is to get Marlin to Nemo safely. But beware, we have a feeding frenzy Bruce on the loose, so better avoid him at all costs!
Details
You are given a rectangular ASCII ocean grid containing only lowercase alphabets a-z. This ocean will have nemo, marlin and bruce inside it in the form of a continuous polyomino, always starting from the top most cell in the first column of polyomino. So for example, out of all possible tetrominos, the valid ones are listed in the below snippet

nemo

n
e
m
o

no
em

ne
om

nem
  o

  o
nem

n
e
mo

 o
 m
ne

ne
 m
 o

n
emo

ne
 mo

n
em
 o

 mo
ne

But forms like these are invalid and won't be present in the input:
omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Finally, your task is to find a path from the marlin polyomino tile to the nemo polyomino tile making sure that any cell in your path is not adjacent to the bruce polyomino tile. Your output should replace all alphabets which are not part of the marlin tile, nemo tile and the path connecting them both with a character from the printable ASCII range (including space) other than the lowercase a-z.
Example
If the input ocean is as following:
oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvtbsalyfrlyn
cicjrucejhiaeb
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

(with the 3 polyominos being:
...n..........
.mli..........
.ar...........
..............
....b.........
....ruce......
..............
.....n........
.....emo......
..............
..............
..............

)
Then a valid solution may look like:
...n..........
.mli..........
.ar...........
.u............
.n............
.i............
.z............
.wvjan........
.....emo......
..............
..............
..............

Below snippet contains a few more examples:

oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvthsalyfrlyn
cibrucejhiaebu
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

...n..........
.mli..........
.ar...........
.u............
qn............
c.............
b.............
ywvjan........
.....emo......
..............
..............
..............

----------------------------------------------

nemokjahskj
sdjsklakdjs
uqiceasdjnn
sbruakmarli

nemokjahskj
..........s
..........n
......marli

----------------------------------------------

Notes

The grid will always be a perfect rectangle and will contain only one polyomino tile of nemo, marlin and bruce.
Your path should not go through bruce or any of the 4 adjacent (up, down, left and right) cells of any cell in the bruce tile.
It is always guaranteed that there will be at least one valid path from marlin to nemo.
There is no requirement of a shortest path here, so go nuts!
Even though you don't have to find the shortest path, any cell in the path (path not including marlin or nemo) cannot be adjacent to more than two other cells in the path.
The path should not go through the marlin or nemo tiles, as it would then confuse the little fishes in choosing a direction.
As usual, you may write a program or function, taking input via STDIN (or closest equivalent), command-line argument or function parameter, and producing output via STDOUT (or closest equivalent), return value or function (out) parameter.
If multi-line input is not possible, then you may assume that the grid is joined by the | character instead of \n. You may also take the input as an array of grid rows.

This is code golf so the shortest entry in bytes wins.

Can the path go through marlin (or nemo)? would the above solution still be valid if the k above the l in marlin was visible? (making the path from the n in marlin to nemo)

@KSab I'd say no as it would then confuse marlin :)

Matlab 560
560 bytes when removing all unnecessary spaces, all semicolons and all comments. Could be golfed much more but I am to tired right now (maybe tomorrow...) Good night everyone.
PS: I assumed that the path must have a 4 neighbourhood ('+') connectedness.
function c(A)
Z = [0,1,0;1,1,1;0,1,0];
Br = q('bruce');
Bn = conv2(Br,ones(3),'s')>0;
Ne = q('nemo');
Ma = q('marlin');
%construct path marlin to nemo
U=Ma>0;M=A*Inf;
M(U)=0;
for k=1:2*sum(size(A))%upper bound for path length
    %expand
    V=imdilate(U,Z);
    V(Bn)=0;
    M(V-U==1)=k;
    U=V;
    %disp(M)
end
%go back from nemo to marlin
Pr=reshape(1:numel(A),size(A));
[i,j]=find(Ne);
m=M(i(1),j(1));%value
P=A*0;%path image
P(i(1),j(1))=1;
for k=m:-1:1
    %find neighbour of (i(1),j(1)) with value m-1
    U=imdilate(P,Z);
    F = M==k;
    G = F&U;
    mask = Pr == min(Pr(F & U));
    P(mask)=1;
end
A(~P & ~Ma & ~Ne)='.';
disp(A)

    function M = q(s)%find string in matrix, A ascii, M mask
        M = A*0;
        m=numel(s);
        N = M+1;%all neighbours
        for k=1:m;
            M(A==s(k) & N)=k;%only set the ones that were in the neighbourhood of last
            L=M==k;
            N=imdilate(L,Z);
        end
        for k=m:-1:2
            %set all that are not neighbour to next higher highest to zero
            L=M==k;
            N=imdilate(L,Z);
            M(M==k-1 & ~N)=0;
        end
    end

end

Calling function : (newlines not necessary)
c(['oxknvvolacycxg',
'xmliuzsxpdzkpw',
'warukpyhcldlgu',
'tucpzymenmoyhk',
'qnvtbsalyfrlyn',
'cicjrucejhiaeb',
'bzqfnfwqtrzqbp',
'ywvjanjdtzcoyh',
'xsjeyemojwtyhi',
'mcefvugvqabqtt',
'oihfadeihvzakk',
'pjuicqduvnwscv']);

Output:
...n..........
.mli..........
.ar...........
..c...........
..v...........
..c...........
..q...........
..vjan........
.....emo......
..............
..............
..............

How it works
Extracting names
The first part is extracting the names e.g. nemo, which is done by the function q(). The function first marks everything as 0, then the occurences first letter of the name as 1, then the second letter as 2 if there is a 1 in the neighbourhood, then the third and so on. After that there should in the case of nemo be only one 4. From that we go backwards until we found the 1 again and then delete all the other numbers that were greater that, so we get back a nice mask where the letters nemo are masked. We do this for all three names, and can then proceed to finding a path.
Finding the path
We start at Marlins positions and send a shockwave throu the hole 'image' step by step. In each step we increase the distance counter and mark the 'pixels' under the wavefront with the current distance. (As it is usually done with shortest path algorithms.) This wavefront obviously gets blocked by the area of Bruce, therefore it will flow around him. This step is repeated until an upper bound is reached. This (admittedly very loose) upper bound is now the circumference of the 'image' (the shortest paths will be way shorter in any case). In the test case it looks something like this:
 2 1 1  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  1  2  3  4  5  6  7  8  9 10 11
 2 1 1  _  _  _  5  6  7  8  9 10 11 12
 3 2 2  _  _  _  _  _  _  9 10 11 12 13
 4 3 3  _  _  _  _  _  _ 10 11 12 13 14
 5 4 4  _  _  _  _  _  _ 11 12 13 14 15
 6 5 5  6  7  8  9 10 11 12 13 14 15 16
 7 6 6  7  8  9 10 11 12 13 14 15 16 17
 8 7 7  8  9 10 11 12 13 14 15 16 17 18
 9 8 8  9 10 11 12 13 14 15 16 17 18 19
10 9 9 10 11 12 13 14 15 16 17 18 19 20

Now start at nemo pixels and decrease the distance counter in each step and add a neighbour with the next lower distance (according to that distance map we calculated earlier) to our path.

Python 2 - 658
Very very inefficient both in time and memory. The function to identify the patterns is the recursive function S, and the function to find the paths is the C, which is basically a horribly inefficient A* implementation.
G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
print'\n'.join(''.join(G[y][x]if(x,y)in N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))else'.'for x in R(X))for y in R(Y))

For testing use this (very slightly) less golfed one (which calculates the path once instead for every tile)
G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
s=N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))
print'\n'.join(''.join(G[y][x]if(x,y)in s else'.'for x in R(X))for y in R(Y))


text:
Generate a Pallette for an Image
This is a successor to my previous Code Golf challenge, which may be found here.
This time, you are trying to determine what the contents of colors.txt should be.
Your task is to take from the input the path to an image and a number of colours, and write to colors.txt a list of that many colors chosen for that image.
Remember, you are generating pallettes to go with this challenge.
As usual, you are going for lowest score, but in this case, your score is given by ceil(codeSize/(1+max(0,votes))), so upvotes will help you as well.
For one or more of the following images, you should test your generated pallettes (using one of the answers from this challenge to test them) and post the results for a variety of pallette sizes:

Apart from lifting the restriction that on the number of contiguous cells in the result, this seems to be asking for the same as Paint by Numbers.

So, do you think this should be deleted in that case?

Java
796 bytes
import java.awt.Color;import java.awt.image.*;import java.io.*;import java.util.*;import javax.imageio.*;public class P{public static void main(String[] a) throws Exception{Random R=new Random();Scanner in=new Scanner(System.in);PrintStream o=new PrintStream("colors.txt");List<Color> col=new ArrayList<Color>();BufferedImage i=ImageIO.read(new File(in.nextLine()));int h=i.getHeight(),w=i.getWidth(),k=in.nextInt(),x,y,z=0,r,g,b;while(col.size()<k&&z<k*k){x=R.nextInt(w);y=R.nextInt(h);Color c=new Color(i.getRGB(x, y));r=5*(c.getRed()/5);g=5*(c.getGreen()/5);b=5*(c.getBlue()/5);c=new Color(r,g,b);if(!col.contains(c)){col.add(c);}z++;}while(col.size()<k)col.add(new Color(R.nextInt(256),+R.nextInt(256),R.nextInt(256)));for(Color c:col)o.println(c.getRed()+" "+c.getGreen()+" "+c.getBlue());}}

Picks random colors from the image, with each component rounded to the nearest multiple of 5, such that no color is selected twice. If, after n2 selections, it has not yet found n distinct colors, it picks the rest entirely at random.
Some sample results:
The black spaceship in 10 colors:

In 25 colors:

In 50 colors:

In 200 colors:

The gold spaceship in 10 colors:

In 25 colors:

In 50 colors:

In 200 colors:

And, finally, the exploding globe in 10 colors:

In 25 colors:

In 50 colors:

And in 200 colors:


text:
Most concise way to fold tree structures
Background (F#)
Let there be trees:
type Tree<'T> = Node of 'T * Tree<'T> list

Now lets fold them nicely with a function called...
foldTree f:('a -> 'b -> 'c) -> g:('c -> 'b -> 'b) -> a:'b -> t:Tree<'a> -> 'c

...taking two functions f and g, an initial state a and of course a tree structure t. Similar to the well known function fold which operates on lists, this function should "merge" siblings with g and parents with their children with f resulting in an accumulated simple value.
Example (F#)
The tree...
//      1
//     / \
//    2   3
//   / \   \
//  4   5   6

let t = Node (1, [Node (2, [Node (4, []); Node (5, [])]); Node (3, [Node (6, [])])])

...passed to foldTree with the operators for addition and multiplication along with the initial state 1...
let result = foldTree (+) (*) 1 t
        // = (1 + ((2 + ((4 + a) * ((5 + a) * a))) * ((3 + ((6 + a) * a)) * a)))
        // = (1 + ((2 + ((4 + 1) * ((5 + 1) * 1))) * ((3 + ((6 + 1) * 1)) * 1)))

...should return the value 321 to result.
The Challenge
In any programming language, define the function foldTree in the most concise way you can come up with. Fewest number of characters wins.

I don't understand how folding is being generalized to trees. In what order do the mergings happens? Could you please give a worked example? Also, are our answers allowed to use imperative constructs?

@xnor each subtree is folded recursively; then the list of results is folded by a right-fold of g with starting value a, and combined with the node's value through f. Judging by the types.

Please some more examples?

@xnor, personally I'm most interested in functional approaches. However, I will not dismiss any answer using other programming paradigms.

@edc65, I extended the example a little bit. Hope that clears things up for you.

The title seems to conflict with the statement In any programming language...

That's correct. I changed it.

Haskell, 37 35:
data T a=a:*[T a]

(f%g)z(x:*t)=x`f`foldr(g.(f%g)z)z t

not counting the type definition. With it, 54 52 (shortened by using infix operator, similarly to the answer by proud haskeller, but in a different way).
Ungolfed:
data Tree a = Node a [Tree a]

foldTree :: (a -> b -> c) -> (c -> b -> b) -> b -> Tree a -> c
foldTree f g z (Node x t) = f x $ foldr (g . foldTree f g z) z t
                       -- = f x . foldr g z . map (foldTree f g z) $ t

--      1
--     / \
--    2   3
--   / \   \
--  4   5   6

t = Node 1 [Node 2 [Node 4 [], Node 5 []],
            Node 3 [Node 6 []]]

result = foldTree (+) (*) 1 t   -- ((+)%(*)) 1 t        {-
       = 1 + product [2 + product[ 4 + product[], 5 + product[]],
                      3 + product[ 6 + product[]]]
       = 1 + product [2 + 5*6, 3 + 7]
       = 321                                            -}

   -- product [a,b,c,...,n] = foldr (*) 1 [a,b,c,...,n]
   --     = a * (b * (c * ... (n * 1) ... ))

This is the redtree ("reduce tree") function from John Hughes paper, "Why Functional Programming Matters", where it is presented in a more verbose formulation.

Interesting... I'm looking at the paper right now, but I can't find this particular definition of foldtree in there. Are you referencing the version of the paper published in “Research Topics in Functional Programming” ed. D. Turner, Addison-Wesley, 1990, pp 17–42.?

Ok, that's basically the same three-liner he gave in the updated version of the paper.I found this shortcut with foldr while learning functional programming with Hughes' paper and was wondering why he didn't use it. Especially considering that his defintion of foldtree is a bit loose about types there. Turns out my finding wasn't that special after all :(

change that frowny to smiley and all will be okay! :) it's good that you discovered this yourself too. the paper was first written very long time ago, in 1984.

2 bytes to save: use an infix constructor instead of N, e.g. :# and  f x$... instead of f x(...).

interestingly, when i was thinking of my solution, I came up with that improvement too but I dropped it because the two improvements couldn't be used together. oh well.

although, I did not think of putting f in infix when using that improvement.

you had a great idea. I've remembered seeing somewhere that using infix operators is one of known golfing techniques for Haskell. you're correct, it's either this way, or your way. Using infix f brings no savings in char count, but it is cleaner looking than f x$.

F#, 70 61
let rec r f g a (Node(n,c))=f n<|List.foldBack(g<<r f g a)c a

Not going to win the contest, but I think you can't get less with F#

Haskell, 35
data T a=a:>[T a]
h(%)g a(e:>l)=e%foldr(g.h(%)g a)a l

the data type declaration is not counted.

Prolog, 85
Logic programming
b([],A,A). b([E|N],A,R):-b(N,A,T),c(E,A,Y),g(Y,T,R). c((C,S),A,R):-b(S,A,T),f(C,T,R).

Ungolfed
b([],A,A).
b([Element|Siblings],A,R):-
      b(Siblings,A,RSiblings),c(Element,A,RElement),
      g(RElement,RSiblings,R).

c((Parent,Children),A,R):-
      b(Children,A,RChildren),f(Parent,RChildren,R).

Functions f and g
f(A,B,R):-R is A+B.
g(A,B,R):-R is A*B.

Example
c((1,[(2,[(4,[]),(5,[])]),(3,[(6,[])])]),1,R).

Try it online
Edit: correction of error signaled by Will Ness, thanks for the feedback

Mathematica, 48
Head@#~#2~Fold[##3,#0[x,##2]~Table~{x,List@@#}]&

Example:
In[1]:= foldTree = Head@#~#2~Fold[##3,#0[x,##2]~Table~{x,List@@#}]&;

In[2]:= foldTree[1[2[4[], 5[]], 3[6[]]], Plus, Times, 1]

Out[2]= 321

JavaScript (ES6), 62
Javascript seems functional enough, function objects can be easily defined and passed as parameters.
Define a node as an object {v:value, c:list of children}, the example tree is:
t={v:1, c:[{v:2,c:[{v:4},{v:5}]},{v:3,c:[{v:6}]}]}

(here the c is optional. Making c a mandatory field with value [] if there are no children, the fold function can be 5 chars shorter)
and the fold function is:
F=(t,a,f,g)=>{
  var r=a
  t.c && t.c.forEach(t=>r=g(r,F(t,a,f,g)))
  return f(t.v,r)
}

Golfed (there is little to golf)
F=(t,a,f,g,r=a)=>(t.c&&t.c.map(t=>r=g(r,F(t,a,f,g))),f(t.v,r))

Test In Firefox

t={v:1, c:[{v:2,c:[{v:4},{v:5}]},{v:3,c:[{v:6}]}]}

F=(t,a,f,g,r=a)=>(t.c&&t.c.map(t=>r=g(r,F(t,a,f,g))),f(t.v,r))

document.write(F(t, 1, (a,b)=>a+b, (a,b)=>a*b))


text:
Find the longest musical substring
A musical string is any string that can be played on a piano keyboard.
For those of us who weren't forced to learn the piano as kids, here is what the keyboard looks like.

So the string feed a dead cabbage is a musical string because every single letter corresponds to one of these nots.
Your challenge is to write a program that takes a string as input from STDIN, and finds the longest musical substring. Then your program must print the substring, and it's length. Here are some sample inputs/outputs.

Input: "FEED ME! I'm hungry!"
Output: feed 4

Input: No no no, no musistrin!
Ouput: 0

Input: "A **bad** !!!fAd82342"
Output: abadfad 7

Input: "Good golfing!"
Output: dg 2

Rules

Your output may be upper or lower-case, but there must be no punctuation or spaces.

There will capitalization and punctuation in the input string, but this doesn't affect whether or not a substring is considered "musical" or not.

There must be a space between the musical substring, and the number.

Full programs only, no functions?

@AlexA yes, full program.

Can the output be mixed case?

@nderscore yes, it can be.

Pyth, 25 23 bytes
pdJef!-T<G7+k.:@Grz0)lJ

2 bytes saved thanks to @Jakube.
Demonstration. Test harness.
Explanation:

rz0: The input, in lowercase.
@Grz0: Strip any non-alphabetic characters.
.:@Grz0): Generate all substrings.
+k.:@Grz0): Add in the empty string.
f ... +k.:@Grz0): Filter over these strings.
-T<G7: Filter each string for non musical characters.
!-T<G7: Negate the result. This is True if and only if the string was musical.
f!-T<G7+k.:@Grz0): Filter out the musical strings.
ef!-T<G7+k.:@Grz0): Take the last such string. .: orders substrings by size, so this is also the longest musical substring.
Jef!-T<G7+k.:@Grz0): Assign the result to J.
pdJ: Print J, with d, space, as the ending character.
lJ: Then, print the length of J.

Ruby, 83 75 characters
Fairly self-explanatory.
puts"#{s=gets.gsub(/[^a-z]/i,'').split(/[^a-g]/i).max_by &:size} #{s.size}"

Takes advantage of the fact that Ruby can split strings on regex (.split(/[^a-g]/)).

Perl, 58
#!perl -p
$\=0;map{$i++;$\="$& $i"if/[a-g]{$i}/i}(s/\W//gr)x y!!!cd

Use:
$ perl ~/mus.pl <<<"FEED ME! I'm hungry!"
FEED 4

or
$ perl -pe'$\=0;map{$i++;$\="$& $i"if/[a-g]{$i}/i}(s/\W//gr)x y!!!cd' <<<"FEED ME! I'm hungry!"
FEED 4

Java, 268
class Z{public static void main(String[]a){String s=new java.util.Scanner(System.in).nextLine().toLowerCase().replaceAll("[^a-z]",""),t;for(int i=s.length();i-->0;)if(!(t=s.replaceFirst("^(.*)([a-g]{"+i+"})(.*)$","$2")).equals(s)){System.out.println(t+" "+i);break;}}}

Expanded:
class Z {
    public static void main(String[] a) {
        String s = new java.util.Scanner(System.in).nextLine().toLowerCase().replaceAll("[^a-z]", ""), t;
        for (int i = s.length(); i-- > 0;) {
            if (!(t = s.replaceFirst("^(.*)([a-f]{" + i + "})(.*)$", "$2")).equals(s)) {
                System.out.println(t + " " + i);
                break;
            }
        }
    }
}

R, 98 94 bytes
p=strsplit(gsub("[^a-z]","",readline(),T),"[^a-gA-G]+")[[1]];m=max(n<-nchar(p));cat(p[n==m],m)

Ungolfed + explanation:
# Read from STDIN and remove all non-alphabetic characters
r <- gsub("[^a-z]", "", readline(), ignore.case = TRUE)

# Split r into a vector of substrings on characters other than a-g
p <- strsplit(r, "[^a-g]+")[[1]]

# Get the number of characters in each substring
n <- nchar(p)

# Get the length of the longest substring
m <- max(n)

# Print the string and length
cat(p[n == m], m)

Suggestions are welcome!
Note: The output is now mixed-case, which is allowed per the OP's edit. This saved 4 bytes.

golflua, 84 85 84 bytes
B=I.r():g("%A",""):g("[^a-gA-G]"," ")M=0Q=""~@W B:gm("(%w+)")?#W>M M=#W Q=W$$w(Q,M)

I first force lowercase, then strip spaces non-letter characters, then remove all non-musical letters on the input (stdin). I then scan through each remaining word and compare its length before outputting the largest and length (stdout). There's probably a shorter way to do the loop, but at the moment this is what I've got.
An ungolfed Lua code would be
Line = io.read()                                  -- read stdin
NoSpaced = Line:gsub("%A","")                     -- strip non-letter chars
MusicalLetters = NoSpaced:gsub("[^a-gA-g]", " ")  -- remove non-musical letters
WordLen = 0, LongWord = ""                        -- helpers
for words in MusicalLetters:gmatch("(%w+)") do    -- scan for longest word
   if words:length() > WordLen then
      WordLen = words:length()
      LongWord = words
   end
end
print(LongWord, WordLen)                          -- output solution

Perl 5 (106)
use List::Util reduce;$_=lc<>;s/[^a-z]//g;$_=reduce{length$a>length$b?$a:$b}m/[a-g]+/g;print"$_ ",0+length


text:
Schedule a 4-way stop
A bunch of cars are lined up at a 4-way stop sign waiting to proceed.  Everyone is confused about who gets to go next, who is going which way, etc.  Clearly suboptimal.
Your job is to schedule the traffic at the stop sign in an optimal fashion.
You receive as input 4 strings of turn requests, one for each of the four cardinal directions.  Each request is either L for left, S for straight, or R for right.
LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

The first row is the lineup at the North entrance to the intersection.  The first car in line wishes to turn left (that is, exit East).  The subsequent rows are for the incoming East, South, and West entrances.  So the first car coming from the West wishes to exit South.
Traffic moves in a series of steps.  At each step, you must choose a subset of the cars at the head of their lines to proceed.  The cars chosen must not interfere with each other.  Two cars interfere if they exit the same direction or if they must cross each other's path (given standard right-hand driving rules).  So two opposite cars both wishing to go straight may go at the same step.  So may 4 cars all wishing to turn right.  Two opposite cars can both turn left simultaneously.
Your job is to schedule the intersection in a minimum series of steps.  For each step, output a line with the incoming cars' compass direction(s) listed.  For the example above, the minimal schedule is 14 steps.  One minimal schedule is:
N    [L from North]
E    [S from East]
E    [S from East]
E    [S from East]
NESW [L from North, R from East, L from South, R from West]
NE   [S from North]
EW   [R from East]
NESW [L from North, R from East, L from South, R from West]
W    [L from West]
EW   [L from East, L from West]
NESW [R from North, L from East, R from South, L from West]
NES  [L from North, R from East, L from West]
NS   [S from North, S from South]
SW   [R from South, L from West]

Your program should be able to handle 50 cars in each line in under 1 minute.  Input of the 4 strings and output of the schedule may be in any convenient manner for your language.
Shortest program wins.
A larger example:
RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

which requires a minimum of 38 rounds.  One possible solution:
E
EW
E
ESW
S
NS
ES
NESW
NSW
ESW
ES
NSW
NS
NS
NW
EW
NSW
NS
EW
NES
EW
NSW
NE
E
NE
EW
E
E
EW
EW
EW
W
ESW
NSW
NSW
NS
NSW
NEW

Can I install a roundabout instead?

How did you calculate the minimal schedule for the first example? I think this is a valid 13-step schedule: NSW, NSW, ESW, EW, EW, NES, NE, EW, NE, NEW, NS, ES, E

@ESultanik: your 4th step, EW, has East going straight, West turning left.  That is not an allowed configuration.

@Fatalize: I have a program which does it using dynamic programming.

Ah yeah, sorry about that. I had a bug in my program. I'll be posting an answer shortly…

Python, 1219 Bytes
I didn't spend very much time/effort trying to golf this, but I might improve it if other answers start popping up.  I use A* search with an admissible heuristic, guaranteeing optimality.  I am pretty sure (although I haven't bothered to confirm) that the heuristic is also consistent, meaning that it is O(dynamic programming).
The program reads in four lines from STDIN in the format you have specified, and prints the result to STDOUT, also in the format you specified.
from heapq import heappush,heappop
from itertools import combinations
N,E,S,W=range(4)
L="L"
R="R"
T="S"
d=[{L:E,R:W,T:S},{L:S,R:N,T:W},{L:W,R:E,T:N},{L:N,R:S,T:E}]
b=set([(N,S,W,E),(N,S,E,W),(S,N,W,E),(S,N,E,W),(E,W,N,E),(N,S,W,N),(S,N,E,S),(W,E,S,W)])
for x in list(b):b.add(x[2:]+x[:2])
def v(*a):return a[1]!=a[3] and a not in b
i=lambda:raw_input()+'\n'
i=map(lambda l:map(lambda e:("NESW"[l[0]],d[l[0]][e]), l[1]),enumerate((i()+i()+i()+i()).split()))
q=[]
heappush(q,(0,[],i))
while q:
    h,a,n=heappop(q)
    m=sum(map(bool,n))
    if m==0:
        print "\n".join(a)
        break
    for r in range(4,0,-1):
        f=False
        for c in combinations(range(4),r):
            l=True
            for i in c:
                if not n[i]:
                    l=False
                    break
            if not l:continue
            l=True
            for x,y in combinations(c,2):
                if not v(x,n[x][0][1],y,n[y][0][1]):
                    l = False
                    break
            if l==False:continue
            f=True
            e=list(n)
            for i in c:e[i]=e[i][1:]
            heappush(q,(m-r+min(map(len,e)),a+["".join([n[x][0][0] for x in c])],e))
        if f:break

Example usage:
$ time echo "RRLLSSRLSLLSSLRSLR\nRLSLRLSLSSRLRLRRLLSSRLR\nRLSLRLRRLSSLSLLRLSSL\nLLLRRRSSRSLRSSSSLLRRRR" | python 4way.py
NES
NEW
NSW
NS
NS
ESW
NS
NES
NEW
NS
NES
NSW
NS
NS
NSW
NW
NS
NS
NS
EW
ES
SW
EW
EW
SW
ES
EW
EW
EW
EW
E
EW
EW
EW
EW
EW
E
EW
echo   0.00s user 0.00s system 38% cpu 0.002 total
python 4way.py  0.02s user 0.01s system 90% cpu 0.030 total


text:
Selectively murder positive integers
Introduction
Arithmetic Gaol is a special facility that incarcerates positive integers. However, recently, the positive integers have been trying to escape. Therefore the wardens have decided to, um, eliminate some of the positive integers to send a message to the other integers. They have hired a software engineer to write a program to figure out which integers to eliminate for maximum effect.
Input Description
Input is given via STDIN, command line arguments, or a user input function (such as raw_input). You can't have it as a function argument or a preinitialized variable (e.g. this program expects input in a variable x).
The first line of input contains a single positive integer n where 8 >= n >= 3. Following that are n lines containing n characters from the set [1,2,3,4,5,6,7,8,9]. Here is an example input:
5
22332
46351
65455
24463
65652

Output Description
The wardens would like to eliminate numbers so that the following conditions are met:

In each row and column of the resulting grid, no number will appear twice;
No two eliminated numbers may be adjacent horizontally or vertically;
The surviving numbers must form an orthogonally contiguous group -- it will be possible to travel from any surviving number to any other surviving number moving only horizontally and vertically and never crossing any eliminated number.

Output the input (minus the first line), with the eliminated numbers replaced with #.
There may be more than one solution. If that is the case, you may output any solution.
There may also be no solution. If that is the case, output the string no answer.
Here is a possible output for the example input:
#2#3#
46351
6#4#5
24#63
#56#2

Example Inputs and Outputs
There are multiple outputs for each input, so these outputs are just examples.
Input:
5
46551
51565
32654
14423
43244

Output:
46#51
#156#
326#4
1#423
#324#

Input:
7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Output:
71#362#
#6815#3
5238#64
#7#62#8
154#382
3814756
#325#4#

Input:
8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Output:
21#34768
#5196287
683#21#4
9#24#853
#4865912
7#51#64#
89751326
436#8#7#

Input:
4
2222
2331
3112
1322

Output:
no answer

(Also known as Singles.)

This puzzle is excellent. Thank you.  Working on a solution

I like this puzzle, but it cannot be answered "as is" using JavaScript in a browser, as the only user input method prompt does not allow multi line input.

Ruby, 346 344 329 316 bytes, sl∞∞∞∞∞∞w
This is code-golf, not code-fast, so...
N=/!/=~G=$*[1..-1]*?!
M=N*N
g=->i{(!G[i]||G[i]<?*||i<0||A[i])&&break
A[i]=0
[1,N+1,-1,-1-N].map{|a|g[i+a]}}
f=->w,a{A=[];g[/\d/=~G=a];/#.{#{N}}?#/!~G&&/(\d)([^!]*|.{#{N}}.{#{O=N+1}}*)\1/!~G&&A.count(0)+w==M&&N.times.map{|m|puts G[m*(1+N),N]}&&exit
(w...M).map{|j|b=a+'';b[j]=?#
w<M&&f[w+1,b]}}
f[0,G]
$><<"no answer"

Use it like:
mad_gaksha@madlab ~/Applications/Tools $ ruby -W0 c50442.rb 3 323 312 231
#23
312
231

The flag -W0 is not necessary, but I suggest you either add it to disable warnings or redirect stderr...
Tell me if you had enough patience to run it on the examples for n=6,7,8
Changelog

each ⇨ map, thanks to @NotThatCharles
check for adjacent deletions and same digits by two regexps, similar to what @NotThatCharles suggested
optimized reading input a little
smaller & slower

a few incremental improvements in size: \d is shorter than [^#] in the penultimate line; M.times.to_a is longer than (0..M-1).to_a

@NotThatCharles Thanks for the tips! But M.times.to_a is 1 byte shorter than (0..M-1).to_a ;) (0...M).to_a works too and is of the same length.

...counting is hard

does it actually complete when n=8?

@NotthatCharles If you wait loooong enough, or use a super-fast PC, yes, it should. This is a code-golf without any restrictions as to speed, so I prioritized code-length...

Basically, it tries every combination of deleting numbers...

I bet you could also save space with keeping it one string instead of double-mapping it - /(\d).{#{N-1}}+\1/ finds dupes, and /#.{#{N-1}}+#/ finds adjacent #s

@NotthatCharles Yes, that made it shorter, thanks. But as I had been using a string without  line separators, detecting adjacent # horizontally was broken. So I had to add line separators and adjust many other parts of the program, so that it didn't save as much as it could have, but still a bit.

Ruby - 541..., 394
The basic algorithm is a recursive depth-first search of duplicates to affirmatively select, looking through row 1, then column 1, then row 2, etc, and checking that two neighbors are not killed and that the grid is connected (that's the break if clause in there, and the bit that comes before it).
K=(0...(N=gets.to_i)*N).to_a
J=gets(p).split*''
H=->m{K&[m+1,m-1,m+N,m-N]}
Q=->k{s=[k[j=0]]
(j=s.size
s.map{|x|(s+=H[x]&k).uniq!})while s[j]
break if(K-k).any?{|m|(H[m]-k)[0]}||k!=k&s
$><<K.map{|m|[k.index(m)?J[m]:?#,m%N>N-2?"
":p]}*''|exit if !g=((0...N*2).map{|x|(k.select{|m|m.divmod(N)[x/N]==x%N}.group_by{|m|J[m]}.find{|l,c|c[1]}||[])[1]}-[p]).min
g.map{|d|Q[k-g<<d]}}
Q[K]
puts"no answer"

Some neat tricks:
if w[1] is much shorter than if !w.one? and if you know there's at least one member, it's the same result.
Similarly, [0] is shorter than any? if there's no block, and s[j] is a cute shortcut for j<s.size (technically, it's more like j.abs<s.size)
And y%N+(y/N).i is much shorter than Complex(y%N,y/N)
Also, when there's two complicated conditionals to generate strings, it might be shorter to do [cond1?str1a:str1b,cond2?str2a:str2b]*'' than to add all the parens or #{}s in.
Ungolfing and explanation:
(This is from the 531 byte version.  I've made changes.  Most notably, I've since eliminated the call to product - just solve one digit per row/column at a time, and J is now just an array, indexed by integers. All coordinates are just integers.)
H calculates neighbors
def H m
  # m, like all indices, is a complex number
  #    where the real part is x and the imaginary is y
  # so neighbors are just +/-i and +/-1

  i='i'.to_c
  neighborhood = [m+1, m-1, m+i, m-i]

  # and let's just make sure to eliminate out-of-bounds cells
  K & neighborhood
end

N is the size of the grid
N = gets.to_i

K are the keys to the map (complex numbers)
# pretty self-explanatory
# a range of, e.g., if N=3, (0..8)
# mapped to (0+0i),(1+0i),(2+0i),(0+1i),(1+1i),(2+1i),...
K = (0..N**2-1).map{|y| (y%N) +(y/N).i }

J is the input map (jail)
# so J is [[0+0,"2"],[0+1i,"3"],....].to_h
J=K.zip($<.flat_map {|s|
  # take each input line, and...
  # remove the "\n" and then turn it into an array of chars
  s.chomp.chars
}).to_h

k are the non-killed keys
# starts as K

Q is the main recursive method
def Q k
  j=0 # j is the size of mass
  # the connected mass starts arbitrarily wherever k starts
  mass=[k[0]]
  while j < s.size # while s hasn't grown
    j = mass.size
    mass.each{|cell|
      # add all neighbors that are in k
      (mass+=H[cell] & k).uniq!
    }
  end
  # if mass != k, it's not all orthogonally connected
  is_all_connected = k!=k&mass

  # (K-k) are the killed cells
  two_neighbors_killed = (K-k).any?{|m|
    # if any neighbors of killed cells aren't in k,
    # it means it was killed, too
    (H[m]-k)[0]
  }
  # fail fast
  return if two_neighbors_killed || is_all_connected

  def u x
    x.group_by{|m|J[m]}.select{|l,c|c[1]}
  end

  rows_with_dupes = Array.new(N){|r|u[k.select{|m|m.imag==r}]}

  cols_with_dupes = Array.new(N){|r|u[k.select{|m|m.real==r}]}

  # dupes is an array of hashes
  # each hash represents one row or column.  E.g.,
  #   {
  #     "3"=>[(0+0i),(1+0i),(3+0i)],
  #     "2"=>[(2+0i),(4+0i)]
  #   }
  # means that the 0th, 1st and 3rd cells in row 0
  # all are "3", and 2nd and 4th are "2".
  # Any digits without a duplicate are rejected.
  # Any row/col without any dupes is removed here.
  dupes = (rows_with_dupes+cols_with_dupes-[{}])

  # we solve one row at a time
  first_row = dupes[0]

  if !first_row
    # no dupes => success!
    J.map{|m,v|k.member?(m)?v:?#}.each_slice(N){|s|puts s*''}
    exit
  else
    # the digit doesn't really matter
    t=first_row.values

    # cross-multiply all arrays in the row to get a
    # small search space. We choose one cell from each
    # digit grouping and drop the rest.
    t.inject(:product).map{ |*e|
      # Technically, we drop all cells, and add back the
      # chosen cells, but it's all the same.
      new_k = k-t.flatten+e.flatten

      # and then search that space, recursively
      Q[new_k]
    }
  end
end

The code is executed with:
# run with whole board
Q[K]

# if we get here, we didn't hit an exit, so we fail
puts"no answer"

Changelog
394 added @blutorange's suggestion below, and chopped out a lot more manipulation
408 revised output once more. Also use .min instead of .inject(:+) since I'm just taking one row anyway.
417 shorter output calculation
421 dropped complex numbers. Just use integers. Save a bundle
450 more input improvements
456 input improvements
462 incremental improvements - esp. find, not select
475 dropped u and squashed the row/col dupe builder
503 only solve one duplicate digit per row/column at a time.
530 use map &:pop instead of values
531 pull out the lambda that makes the dupes array
552 oops! missed a requirement
536 marginally improved population of dupes array (what was formerly d)
541 initial

Inside lambdas, break can be used instead of return, might save one more byte. I really lIke this one, lots of tricks and much faster.

@blutorange Thanks! Applied.  Still have a ways to go to hit 344, though.

A bit longer, yes, but otherwise it looks done well. One more thing I saw: In the second line, as the variable a is used only once, you could make that J=gets(p).split*''. Have you tried cli arguments, see my answer?

HTML + JavaScript (ES6) 459
Using an HTML textarea to get multiline input.
To test, run the snippet in Firefox.
Enlarge the textarea if you like, paste the input inside the textarea (beware: exact input, no extra spaces on any line), and tab away. The result is appended.
Method: a recursive Depth First Serarch. It finds non-optimal solutions for all the test cases in seconds (it's gode golf, but a valid answer should terminate for common test cases)

<textarea onchange="s=this.value,
  z=s[0],o=-~z,k=[],X='no answer',f='#',
  (R=(s,t,h={},r=[],d=0)=>(
    s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i])),
    [h[i][1]&&h[i].map(p=>r[d=p]=p)for(i in h)],
    d?r.some(p=>(
      (s[p+o]!=f&s[p-o]!=f&s[p-1]!=f&s[p+1]!=f)&&
      (
        g=[...s],g[p]=f,e=[...g],n=0,
        (F=p=>e[p]>0&&[1,-1,o,-o].map(d=>F(p+d),e[p]=--n))(p<o?p+o:p-o),
        t+n==0&&!k[g]&&(k[g]=1,R(g,t-1))
      )
    )):X=s.join('')
  ))([...s.slice(2)],z*z-1),this.value+=`

`+X"></textarea>

First try
Method: a Depth First Serarch, non-recursive, using a user stack.
The function could be easily transformed in a Breadth First Search, chaging l.pop to l.shift, so using a queue instead of a stack, but it's too slow and I'm not sure it can find an optimal solution anyway.

S=s=>{
  z=s[0],o=-~z,s=[...s.slice(2)];
  k=[];
  l=[[z*z,s]];

  for(d=1;d&&(t=l.pop());)
  {
    [t,s]=t,--t,

    s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i]),h={},r=[])

    d=0
    for(i in h)h[i][1]&&h[i].map(p=>r[d=p]=p)

    r.map(p=>
      (s[p+o]!='#'&s[p-o]!='#'&s[p-1]!='#'&s[p+1]!='#')&&
      (
        g=[...s],g[p]='#',
        f=[...g],n=0,
        (F=p=>f[p]>0&&[1,-1,o,-o].map(d=>F(p+d),f[p]=--n))(p<o?p+o:p-o),
        t+n||k[g]||(k[g]=l.push([t,g]))
      )
    )
  }
  return d?'no answer':s.join('')
}

// TEST
cases=[
 ['5\n22332\n46351\n65455\n24463\n65652','#2#3#\n46351\n6#4#5\n24#63\n#56#2']
,['5\n46551\n51565\n32654\n14423\n43244','46#51\n#156#\n326#4\n1#423\n#324#']
,['7\n7183625\n1681563\n5238564\n8786268\n1545382\n3814756\n5325345'
 ,'71#362#\n#6815#3\n5238#64\n#7#62#8\n154#382\n3814756\n#325#4#']
,['8\n21534768\n75196287\n68392184\n96244853\n44865912\n76516647\n89751326\n43698979'
 ,'21#34768\n#5196287\n683#21#4\n9#24#853\n#4865912\n7#51#64#\n89751326\n436#8#7#']
,['4\n2222\n2331\n3112\n1322','no answer']
]

  var out = ''
  var nt=0
  var exec =_=>{
    var t=cases[nt++];
    if (t) {
      var r = S(t[0]).replace(/#/g,'#');
      var k = t[1].replace(/#/g,'#');
      out += '
InputResultExpected
'+
      '
'+t[0]+'	'+r+'	'+k+'
';
      T.innerHTML = out + 'test ' + nt + ' done';
      setTimeout(exec, 100);
    }
    else
    {
      T.innerHTML = out;
    }
  }
  T.innerHTML = "...wait ..."
  setTimeout(exec, 100);
table {
  font-size: 12px;
}
td {
  font-family: monospace;
  white-space: pre;
  vertical-align: bottom;
  margin: 2x 4px;
}

b {
  color: #ccc;
}


text:
CodeGolf - Barry the messy developer #2

This is a follow-up of
  CodeGolf - Ignore the noise #1
  the only problem being that Barry has made things even worse for us. Lets see what happened

Update
I've added code to create random input and expected output because I'm not that good at explaining what I want, and I guess that sometimes words are more misleading than code (isn't that always?)
Description
Another method in Dumb Corp's API gives us the current price a provider is giving us for an item, the optimal price we would be making maximum sales with and the tendency of that price compared to previous prices as a string UP or DOWN. We need to decide if we should remove the item from the shop or wait.
Input
80,90,UP
150,100,DOWN
65,65,UP
1618,1618,DOWN
840,1200,DOWN
54,12,UP
30,1,UP

For a huge input sample demo with expected output, put the following code (js) in your browsers console and it should output valid random input for testing.
var output = "";
var result = "";

for(i=10;i--;){
  var currentPrice = Math.floor(Math.random() * 10000) + 1;
  var optimalPrice = Math.floor(Math.random() * 10000) + 1;
  var tendency = Math.round(Math.random())?"UP":"DOWN";
  var tresult = "WAIT\n";

  if((currentPrice > optimalPrice && tendency == "UP") ||
     (currentPrice < optimalPrice && tendency == "DOWN")){
       tresult = "STOP\n";
     }

  output +=currentPrice+","+optimalPrice+","+tendency+"\n";
  result +=tresult;
}
console.log(output);
console.log(result);

As always we will have a variable G as our input, however if your language makes it easier for you to simply read the input, that's also fine. The format is constant, and follow the format int,int,string
Desired Output
You're the brains of this operation, Barry should be doing this calculation on the server, but we can't count on him as you should know. You need to output WAIT if the tendency is towards the optimal price, or STOP if the tendency is towards loses.
In other words, with the 80,90,UP as input, we know that there is a product with current price of 80 and optimal price of 90 with a tendency to rise up, so we should WAIT. On the other hand, 840,1200,DOWN means the product price is going down and our optimal price is higher, so we should stop losses by outputting STOP.
If the two prices are identical, output WAIT regardless of the tendency.
Each product in a new line, single word per line:
WAIT
WAIT
WAIT
WAIT
STOP
STOP
STOP

Please, when possible, provide a way of verifying that your code is working since we can't all know just by looking at the syntax. As always, use as few characters as possible and remember that you're not competing against other languages necessarily, your competing against languages with similar syntax

Your test data isn't terribly useful without expected results.

@NotthatCharles: I'm pretty sure the block in the Desired Output section of the post is the expected result of the test data in the Input section.

I meant the "huge input sample"

I realice now that it wasn't really helpful, updated the code to provide expected output.

Does the program have to work for several lines of input or just for one at a time?

Please, several lines

Is there any reason why you prefer scoring in characters? The default around here is bytes (in an existing encoding of the participant's choice). With characters you just get people compressing their code by encoding it in Unicode characters and things like that. (Whatever your choice, don't change it for this challenge now, but you might want to keep it in mind for future challenges.)

To be fair, this is my third game and I wasn't aware of the difference between doing it in bytes or characters, although now that you mention it it makes total sense, sorry for that. Are all languages susceptible to being encoded to reduce character count?

CJam, 31 29 27 characters
"㫅㍸ꕆ敟鸢Ꝓ約䢫솓儓隆뻨"2G#b128b:c~

This is just an encoded version of the following code (in order to make use of the scoring by characters):
r{',/:~3<)(f*~<"STOP""WAIT"?Nr}h

Run all test cases here.
There might be a way to shorten this by encoding STOP and WAIT, but I'm quite happy with the rest.
Explanation
The code is surrounded by a loop which reads on line at a time, processes it, then pushes a newline, and reads the next line... The loop terminates once r returns an empty string (i.e. after all lines have been processed). That's this bit:
r{ ... Nr}h

As for processing each line, I'm making use of the fact that upper case letters are variables in CJam, so I can eval some of the input.
',/:~3<)(f*~<"STOP""WAIT"?
',/                        e# Split the input on commas.
   :~                      e# Eval each of the three resulting strings. The first two
                           e# will yield the prices, the third will dump a bunch of
                           e# values corresponding to the variables DNOPUW in the array.
     3<                    e# Truncate to three elements, so we only get the prices and
                           e# the values corresponding to U (0) and D (13).
       )(                  e# Slices off that variable value and decrement it, to get
                           e# something negative for UP and positive for DOWN.
         f*                e# Multiply both numbers by that value. So if we had UP then
                           e# both numbers will be negative now, otherwise they'll just
                           e# be scaled without affecting their relative size.
           ~<              e# Unwrap the array and check which element is larger.
             "STOP""WAIT"? e# Select the desired output string based on this boolean.

So the catch is that for UP we invert the relative sizes of the prices, so that we can cover all cases with a single inequality at the end.

I've requested clarification from the OP and he said the code should work for several lines of input. The shortest way to achieve this should be this: "㫅㍸ꕆ敟鸢Ꝓ約䢫솓儓隆뻨"2G#b128b:c~

@Dennis Ugh, scoring by characters... thanks.

Perl, 35
#!perl -pl
/,/;$_=$`-$'&&$`>$'^/D/?STOP:WAIT

Test me.

Perl, 77 73 bytes
while(<>){@p=split",";print($p[0]<$p[1]and$p[2]=~/D/?"STOP":"WAIT")."\n"}

Here's how it works:

while(<>) parses every line.
@p=split"," splits it by every comma. It's using the default Perl operator, $_ (which is where the line is stored.)
print (ternary) determines what to print.
$p[0]<$p[1]and$p[2]=~/D/ asks if the current price is less than the price we want, and it's going down (by checking for a D.)
(condition)?(if):(else) is the ternary operator.
If our condition earlier matched, it'll output STOP. Otherwise, it'll output WAIT.

I'm assuming there is no trailing newline on the input - a trailing newline produces an extra WAIT.
Thanks to Alex A. for helping me save 4 bytes!

Granted it's been quite a while since I've used Perl, but does it have to be and? Can you use & or something?

@AlexA. I'm not sure why, but && behaves strangely. I tried using it, and it said there was an "unmatched <>".

Huh. Weird. Oh well. Nice solution.

Can you do a single call to print and just do something like print((condition)?"STOP":"WAIT")."\n"?

@AlexA. Huh, did not know you could do that. Thanks!

Also, do you need the parentheses around the condition? If not, that'll save another 2.

@AlexA. Apparently not, so thanks!

One more: I think you can do say rather than print,which is 2 bytes shorter, plus it implicitly appends a newline, which renders the ."\n" and, if I'm not mistaken, the parentheses around the ternary, unnecessary.

@AlexA. It says that it doesn't know what say is. I have Perl v5.18.2, so is say only available in Perl 6+?

According to this, it was new in Perl v5.10. And it's in the documentation for 5.20.1...

You changes break the code. print($p[0]<$p[1]and$p[2]=~/D/?"STOP":"WAIT")."\n" is equivalent to (print(($p[0]<$p[1])and($p[2]=~/D/?"STOP":"WAIT")))."\n" so neither the condition nor the EOL adding work as intended: http://ideone.com/dNB3xd

say needs to be enabled by use v5.10 in the source or -E on the command line.

@nutki: I disagree with the logic grouping but I agree with the newline. This works as expected for me.

@AlexA., and and && are not the same. && takes precedence over ?:, but and not.

Do you really need to specify p[2] in $p[2]=~/D/ ? If you omit those 4 characters and the 2 characters for =~ i'm pretty sure the match will be performed against the whole string. If the two ints are guaranteed to be decimal (as the test data always provides) then the only place a D can ever appear is in the 3rd field, so you're safe matching against the whole string. And you would have 5 fewer characters

You should also be safe replacing "\n" with the file input separator, $/ , which must contain newline or you wouldn't be able to read the file. Should save you 2 more characters.

I think you can also change while(<>){...} to map{...}<> to save 2 more characters

C, 85
c;main(i,j){for(;scanf("%d,%d,%c%*s",&i,&j,&c)>0;)puts(i-j&&i>j^c<70?"STOP":"WAIT");}

Test me.

Ruby - 89 Chars
G.split.map{|a|b,c,d=a.split(?,);puts (b.to_i>=c.to_i)^(e=d[2])&&(b!=c||e)?'STOP':'WAIT'}

RubyFiddle
With help from to bluetorange!

Is this correct for the new equal test cases? I also tried something like this, but that failed for one of those test cases.

@Oebele didn't see that ... not sure whether they were added after my original but I've added the = now thanks :)

Wait - why did I myself do a complex workaround taking many bytes instead of adding = which I knew was also a possibility... Time to fix!

Does this account for case 1618,1618,DOWN ?

Perhaps I'm stupid, but I don't get this code. It seems to me that for each of the 3 comma-separated values of each line, it does something with the 1st, 2nd, and 4th character and prints WAIT or STOP? Using a.split.map{..} prints 3 WAIT or STOP for each input line. Did you mean to do sth. like b,c,d=a.split(?,)? Also, !b[3][2] is shorter than b[3]=='UP', but I think that it should be b[2]? Comparing strings with >= requires attention, as "9">="77" is true. The default input line separator is \n, so you could use split without arguments. ?\n is shorter than '\n'.

If I change the code like this, it works for all examples correctly for me: G.split.map{|a|b,c,d=a.split(?,);puts (b.to_i>=c.to_i)^(d[2])&&(b!=c||d[2])?'STOP':'WAIT'}

You're right - not sure how I got away with that. I've updated it now to reflect your changes, with an added shorten on assigning d[2] to a variable on the first reference of it.

Glad you like it ;) Btw, your score is 90 bytes/chars, not 91. Some editors add a final newline upon saving that isn't necessary. Here's a byte counter.

I've sorted that out on the latest edit - but I'll use that byte counter in future, always learning!

Python 3, 89 84 82 bytes
for l in G:a,b,c=l.split(',');print('WSATIOTP'[a==b or(int(a)<int(b))^(c<'U')::2])

Explanation:
for l in G:                                   #For every line in G:
           a,b,c=l.split(',');                #Split the line into three strings.
                              print()         #Print the contained expression.

'WSATIOTP'                                    #'WAIT' and 'STOP' interleaved.
          [                              ::2] #Select every other character.
                or                            #If either expression is true, pick 'WAIT'
           a==b
                  (             )^(     )     #Select 'WAIT' if exactly one is true.
                   int(a)<int(b)              #If first number < second number.
                                   c<'U'      #If c is 'DOWN'

Care to explain it?

@JuanCortés Added explanation.

Beautiful, I love it!

R, 95 108
R and strings, not really friends:)
eval(parse(t=sub("U","<",sub("D",">",gsub("(.*),(.*),(.).*","cat(if(\\1\\3=\\2)'WAIT\n'else'STOP\n')",G)))))

Input is the character vector G then changes each string into an if statement that is evaluated.
Edit Messed up my interpretation of the rules.  Fix cost a few characters.
> G=c(
+     '80,90,UP',
+     '150,100,DOWN',
+     '65,65,UP',
+     '1618,1618,DOWN',
+     '840,1200,DOWN',
+     '54,12,UP',
+     '30,1,UP'
+ )
> eval(parse(t=sub("U","<",sub("D",">",gsub("(.*),(.*),(.).*","cat(if(\\1\\3=\\2)'WAIT\n'else'STOP\n')",G)))))
WAIT
WAIT
WAIT
WAIT
STOP
STOP
STOP
>

Why do the last two return "wait"? They should give "stop".

@Oebele I misunderstood the rules.  It wasn't the clear for higher current prices descending.  Will fix soon

Matlab, 100 90 bytes
Not as small as I'd like - especially the conversion from boolean to the strings is very long. I tried to shave off a few bytes by switching to Octave, but apparently %c is not supported for textscan yet in Octave.
B=textscan(G,'%f,%f,%c%s\n');xor(B{1}>=B{2},B{3}==85);C(a)={'STOP'};C(~a)={'WAIT'};char(C)

Personally I think it is nice that this solution is the only one so far that does not use split :)
EDIT: originally solved the equals situation way too complex.

This is actually 92 bytes - you missed the a= bit before the xor function call. Though even then it doesn't actually produce the correct output.

Javascript ECMAScript 6, 112b
var O="";for(let E of G.split("\n"))[A,B,C]=E.split(","),O+=("U"<C||-1)*(A-B)>0?"STOP\n":"WAIT\n";console.log(O)

Only on ECMAScript 6 compatible browsers
Explanation
("U"<C||-1)*(A-B)>0?"STOP\n":"WAIT\n"

It makes use of the fact that if we ask if 0 is true it will return false, so we can say 1 for UP, -1 for DOWN. Then we multiply that by the difference of current price and optimal price to make both of them work for the greater than 0 part
If condition is met, return STOP, otherwise (including equal values) return WAIT
Needs further golfing

C- 91 Bytes
Because C has to be there somewhere
Now looks very similar to @nutki version although working out whether to output "STOP" or "WAIT" is diffferent.
Ungolfed-
main(i,j)
{
    char c[5];
    while(scanf("%i,%i,%s",&i,&j,c)+1)
        puts((j-i)*(*c-70)<0?"STOP":"WAIT");
}

Golfed-
 main(i,j){char c[5];while(scanf("%i,%i,%s",&i,&j,c)+1)puts((j-i)*(*c-70)<0?"STOP":"WAIT");}

The old one
Ungolfed-

int main()
{
    int i,j;
    char *c="";
    while(scanf("%i,%i,%s",&i,&j,c)+1)
    {
        if(i<j)
        {
            if(*c-68)
                printf("WAIT\n");
            else
                printf("STOP\n");
        }
        if(i>j)
        {
            if(*c-68)
                printf("STOP\n");
            else
                printf("WAIT\n");
        }
        if(i==j)
            printf("WAIT\n");
    }
    return 0;
}

Golfed

#define W printf("WAIT\n");
#define S printf("STOP\n");
int main(){int i,j;char *c="";while(scanf("%i,%i,%s",&i,&j,c)+1){if(i<j){if(*c-68)W else S}if(i>j){if(*c-68)S else W}if(i==j)W}return 0;}

I'll continue to try to cut it down

This code will just crash. You need char c[4] instead of char *c="" (which is also shorter).

@nutki , Actually, its just Undefined Behavior. A crash need not happen.

@CoolGuy, writing 5 bytes to a read only location of 1 byte. Is there a system in which this will not segfault?

@nutki - obviously my Windows PC as it worked on that!

@nutki , See? TheE's system did not throw a segfault. It is just undefined behavior. Might work on one system, but won't on the other. Anything can happen. But who cares? This is code golf so the program just needs to "work" :)  BTW, shouldn't it be char c[5] ( 1 space for the \0 at the end )?

@TheE , Nice. Much shorter! +1

Javascript (ES6), 82 80 79 bytes
Edit: -2 using @JuanCortés multiplication method
Edit: -1 using a trick to reduce the multiplication method
alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>(c-o)*~{P:-2}[t]>0?'STOP':'WAIT'))

Commented:
alert(                           // alert final output after replacement
    G.replace(/(.+),(.+),(.)+/g, // capture group for sections of each line
                                 // (.)+ captures only the last character
                                 // . doesn't match newlines, so this runs for each line
        (x,c,o,t)=>              // use a function to calculate each replacement string
            (c - o)              // calculate difference, negative for o>c
            *                    // multiply by
            ~{ P: -2 }[t]        // { P: -2 }[t] returns -2 for UP ('P') -2, else undefined
                                 // ~-2 => 1, ~undefined => -1
            > 0                  // if result > 0 (muplication of negatives or positives)
            ? 'STOP' : 'WAIT'    // return corresponding replacement string
    )
)

Snippet Demo:

function run(){
    G = input.value;
    /* start solution */
    alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>(c-o)*~{P:-2}[t]>0?'STOP':'WAIT'))
    /* end solution */
}
<textarea id="input" cols="25" rows="7">80,90,UP
150,100,DOWN
65,65,UP
1618,1618,DOWN
840,1200,DOWN
54,12,UP
30,1,UP</textarea><br />
<button id="run" onclick="run();">Run</button>

Revision History:
// 80
alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>(c-o)*(t>'N'||-1)>0?'STOP':'WAIT'))

// 82
alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>+c>o&t>'N'|+c<o&t<'P'?'STOP':'WAIT'))

Care to explain the logic? Looks awesome but I have no idea whats going on

@JuanCortés I've added a commented version :)

Cheers! That I do understand

Python 3 - 108 106 102 97B
for l in G:a,b,c=l.split(',');s=int(a)-int(b);d=c<'E';print(['WAIT','STOP'][(s<0)*d+(s>0)*(1-d)])

Work in progress...