text:
Enumerate all palindromic numbers (in decimal) between 0 and n
Given a non-negative integer n, enumerate all palindromic numbers (in decimal) between 0 and n (inclusive range). A palindromic number remains the same when its digits are reversed.
The first palindromic numbers (in base 10) are given here:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101,
  111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242,
  252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383,
  393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, ...

This is a code golf with the prize going to fewest characters. The palindromic numbers should be output one per line to stdout. The program should read n from the commandline or stdin.

Between 1 and n (as per title) or 0 and n (as per body)? And which of the bounds does "between" include?

@wok: You still haven't answered if it's inclusive or exclusive range?  Is n part of the range to include?

@mellamokb Inclusive range.

Golfscript, 15 chars
~),{.`-1%~=},n*

You may save a char comparing strings instead of numbers '~),{`.-1%=},n*'.

@Howard, if you want to post that yourself I'll upvote it.

That would feel like plain copying ;-)

Perl 5.10, 29 (or 39) characters
say for grep$_==reverse,0..<>

Needs the say feature enabled. 29 chars if you consider that to be free,  otherwise 39 to add use 5.010;. Argument on STDIN.
Perl, 35 characters
#!perl -l
print for grep $_==reverse,0..<>

using the old perlgolf convention that #!perl is not counted but any flags following it are.
Perl, 36 characters
print$_,$/for grep $_==reverse,0..<>

If none of the others qualify.

Would you be so kind to explain what does $/ do?

@Gurzo $/ is the input record separator, which defaults to newline. It's just a little shorter than literal "\n".

Using map is shorter: map{say if$_==reverse}0..<>

@jho evil. Submit it :)

If you use -E in lieu of -e, you get say for free.

Befunge 320 313 303 characters
(including significant newlines and whitespace)
 &:#v_v#  #                  :-1<
v91:<         v          <
0     >0.@    >\25**\1-:#^_v
pv   p09+1g09<^_           >$+     v
:>:25*%\25*/:| ^:p18:+1g18\<
 :          > >90g 1-:90p  | >  ^
>|           $^     <      >-|  ^  #<
 @           > 0 81p^        >:.25*,^
            ^                      <

I wonder if I could make this smaller by rerouting the paths...
Edit: redid the top part to avoid an extra line.

Perl 5.10 - 27 characters
map{say if$_==reverse}0..<>
Reads the argument from stdin.

Ruby 1.9, 39 characters
puts (?0..gets).select{|i|i==i.reverse}

Input (must not be terminated with a newline) via stdin. Example invocation:
echo -n 500 | ruby1.9 palinenum.rb

40 characters for a version which uses commandline args:
puts (?0..$*[0]).select{|i|i==i.reverse}

Rohit proposed saving 3 characters in each of these by using p instead of puts.

Using your code I got the following output, which seems to be wrong(I am using ruby 1.9.2p0 (2010-08-18) [i386-mingw32])
`irb(main):023:0> p (?0..gets).select{|i|i==i.reverse}
1
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "11", "22", "33", "44", "55", "66", "77", "88", "
99"]
=> ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "11", "22", "33", "44", "55", "66", "77", "88"
, "99"]
`
The code below works for me
p ('0'..gets[0..-2]).select{|i|i==i.reverse}
Could you explain your code.

@PeterTaylor @Rohit p and puts are not equivalent, in fact using p breaks the output, as puts writes every element on a newline, if called with an array, whereas p simply calls .to_s.

J, 20 characters
(#~(-:|.)@":"0)>:i.n

I can read it!:) Nice

btw, to meet a requirement output numbers one per line you should add ,"0.

@defhlt ,. works as well

Python, 57 51 chars
for i in range(input()):
 if`i`==`i`[::-1]:print i

Usage:
echo 500 | python palindromic.py

Shorter: for i in range(input()):if\i`==`i`[::-1]:print i`

If using the interactive interpreter is legit, then you can avoid the print and just do if`i`==`i`[::-1]:i (I say this because the Scala solution depends on this).

The range should be inclusive.
And i think you can change you byte count to 50 (linebreaks are shorter on linux).

Perl > 5.10 : 25 characters
map$_==reverse&&say,0..<>

APL (25 17)
↑t/⍨t≡∘⌽¨t←⍕¨0,⍳⎕

Javascript 122 108 107 chars...
I'm sure this can be golfed more - I'm new to this!
n=prompt(o=[]);for(i=0;i<=n;i++)if(i+''==(i+'').split("").reverse().join(""))o.push(i);alert(o.join("\n"));

or
n=prompt(o=[]);i=-1;while(i++<n)if(i+''==(i+'').split("").reverse().join(""))o.push(i);alert(o.join("\n"));

Well, for starters the vars are unneeded, you can just make things global. Also prompt() doesn't strictly need parameters.

However, you can use parameters to prompt() to save one semicolon: n=prompt(o=[]);.

Also you still have a var i=0 that can have the var removed in your for.

Something's wrong with your code.  It prints out every number between 0 and n-1, not just the palindromes, in both FF and Chrome...  Aha found it.  You need parentheses: (i+'').split... otherwise you are reversing '' only :)  BTW you can easily test your code with jsfiddle, for example: http://jsfiddle.net/rU5Vh/

Also if I read the question right, it's inclusive of 0 and n.  So that should really be i<=n rather than i<n in the for.

You can save a few more chars by moving i=0 declaration outside and switching for to a while loop: while(i++<n).

hmm mellamokb thanks for all the tips. :) I had the brackets before .split before but must have stupidly removed them to try and save chars without noticing. That while(i++<n) won't that a) remove 0 from the numbers and b) not get to i==n.

I set i=-1 and it works with the while loop. Why does while(i++<n) also match true when i+1=n?

The trick is that i++<n compares i<n before adding 1 to i.  Thus, it runs all the way to i=n.  If you wanted to stop at i=n-1, you would use ++i<n instead.

alert(o.join(" ")) needs to be alert(o.join("\n")) according to the specs. Add 1 to your character count when you fix this.

@mellamokb In JS, a for loop should never require more characters than its equivalent while loop. Instead of i=-1;while(i++<n) you can use for(i=-1;i++<n;) to save a character.

I think using console.log() does not violate the rules, but reduces the code to 84 characters: for(i=0,n=prompt();i<=n;i++)if(i==(i+'').split('').reverse().join(''))console.log(i).

You could make this even shorter by using for(i=0;++i<=n;) instead of for(i=0;i<=n;i++).

Haskell 66 characters
main=do n<-readLn;mapM_ putStrLn[s|s<-map show[0..n],s==reverse s]

Misspelled the language name...

Fixed (filler chars)

Perl - 43 chars
for$i(0..<>){if($i==reverse$i){print$i,$/}}

This is my first attempt at code golf, so I'm pretty sure a Perl pro could golf it down.

Mathematica 61
Column@Select[0~Range~Input[],#==Reverse@#&@IntegerDigits@#&]

Brachylog
With the I/O format stated in the question, 8 bytes
≥ℕA↔A≜ẉ⊥

Try it online!
With modern PPCG I/O rules, 4 bytes
≥ℕ.↔

Try it online!
This is a function that generates all the outputs, not a full program like the previous example, and so doesn't comply with the spec as written, but I thought I'd show how the program would look like if the question had been written to modern I/O standards (which permit the use of functions, and output via generators).
Explanation
≥ℕ.↔
 ℕ    Generate natural numbers
≥     less than or equal to the input
  .   but output only the ones
   ↔  that would produce the same output if reversed

For the full program version, we create a temporary variable A to hold the output, explicitly labelize it (this is done implicitly for the main predicate of a program), and use the well-known ẉ⊥ technique for outputting a generator's elements to standard output.

When did modern PPCG I/O rules allow you to use a generator as submission?

@LeakyNun: I made the proposal on 30 Nov 2016, but the consensus is that they were already legal at that point (just not documented). We have an explicit rule allowing them now; through most of 2016, they weren't explicitly allowed and they weren't explicitly banned either.

Oh, well, I see.

PHP, 64 58 bytes
for($i=0;$i<=$argv[1];print$i==strrev($i)?$i.'\n':'',$i++)

Changed $_GET['n'] to $argv[1] for command line input.

PHP, 59 55 53 chars
for($i=0;$i++<$argv[1];)if($i==strrev($i))echo"$i\n";

Usage
php palindromic.php 500

Edit : thanks Thomas

you can remove the {s around the for loop and remove the space in echo "$i\n" to get echo"$i\n". That'll save you a few chars. Also, if you want to be cheeky you can change \n for   and save a char.

Scala 59
(0 to readInt)filter(x=>""+x==(""+x).reverse)mkString("\n")

I don't know any Scala, but does that really print on stdout? I would've guessed it's an expression returning a string.

In the interactive scala REPL, yes. You may test it here http://www.simplyscala.com/ but have to replace readInt with a concrete number, online.

C, 98 characters
n,i,j,t;main(){for(scanf("%d",&n);i<=n;i-j?1:printf("%d ",i),i++)for(t=i,j=0;t;t/=10)j=j*10+t%10;}

k (23 chars)
{i@&{&/i=|i:$x}'i:!1+x}

Befunge, 97 (grid size 37x4=148)
#v&#:< ,*25-$#1._.@
:>:::01-\0v >-!#^_$1-
*\25*/:!#v_::1>\#* #*25*#\/#$:_$\25*%
   `-10:\<+_v#

Have a better Befunge answer to this question. This is Befunge-93 specifically; I could probably make it even more compact with Befunge-98. I'll include that in a future edit.
Since you can't operate on strings in Befunge, the best I could do was compute the digit-reverse of each number (which I'm surprised I was able to manage without p and g) and compare it to the original number. The digit-reverse takes up most of the code (basically the entire third and fourth lines).
Note that the program, as it stands now, prints the numbers backwards from the input down to 0. If this is a big deal, let me know. (The challenge only says to enumerate them, not specifically in increasing order.)

+1. Lines can be closed by \n alone, so it's 94 bytes long. I don't think your "grid size" has any particular relevance.

05AB1E, 5 bytes
ƒNÂQ–

Explanation:
ƒ      # For N in range(0, input() + 1)
 N     #   Push N
  Â    #   Bifurcate (pushes N and N[::-1])
   Q   #   Check for equality
    –  #   If true, pop and print N

Uses CP-1252 encoding. Try it online!.

LʒÂQ is 4, non-competing still though..

@MagicOctopusUrn That doesn't work, as it uses the range $1-n$, not $0-n$. Also, it outputs a list, not numbers on separate lines.

Jelly, 5 bytes
ŻŒḂƇY

Try it online!

Unfortunately, this doesn't join the output list on newlines. I hope it doesn't cost any extra bytes to fix this.

@Lyxal Unsurprisingly, it does. Stupid older challenges and their crappy I/O formats

Perl 5, 24 bytes
map$_-reverse||say,0..<>

Try it online!

Python
n=raw_input('')
for a in range(0,int(n)+1):
    r=str(a)
    if str(a)==r[::-1]:
        print r

Hmm...232 characters is not really very competitive. Perhaps you could reduce the variable names to one character and delete the spaces between the variables and operators?

Good job. Some good tips for golfing Python can be found in this question: http://codegolf.stackexchange.com/questions/54/tips-for-golfing-in-python

You can get rid of n --just replace int(n) by int(raw_input())-- and you can change str(a) to r in the if statement

@Omar that can be golfed even more. int(raw_input()) can be just input(), the 0, in the range is unnecessary, and you can use a map to map str over the range instead of using r. Also, the print statement can be on the same line as the if statement, and indentation can be a single space. This saves a whole 38 bytes. Try it online!

Groovy, 83
System.in.eachLine{(0..it.toInteger()).each{if("$it"=="$it".reverse())println(it)}}

Q (33)
{if[x="I"$(|:) -3!x;:x]} each til

Probably a neater way to do this but anyway, sample usage (you enter n+1 to get to n):
q){if[x="I"$(|:) -3!x;:x]} each til  10
0 1 2 3 4 5 6 7 8 9

Suggestion by tmartin, gets it down to 29:
({$[x="I"$(|:) -3!x;x;]}')(!)

Same usage.

Q (34 chars)
Pass n rather than n+1 as an argument for this Q solution.
{i(&)({all i=(|)i:($)x}')i:(!)1+x}

Q,32
{a(&)a~'((|:)')a:((-3!)')(!)1+x}

Python, 106 characters
import sys as a
print(type(a.argv[1]))
for x in range(int(a.argv[1])+1):
 x=str(x)
 if x==x[::-1]:print(x)

usage:
python a.py 500

82 bytes

C# (217 214 191 chars)
Golfed version:
using System;using System.Linq;class P{static void Main(){int n=int.Parse(Console.ReadLine());do{var t=(n+"").ToArray();Array.Reverse(t);Console.Write(n+""==new string(t)?n+"\n":"");}while(n-->0);Console.ReadLine();}}

Readable:
using System;
using System.Linq;
class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        do
        {
            var t = (n + "").ToArray();
            Array.Reverse(t);
            Console.Write(n + "" == new string(t) ? n + "\n" : "");
        } while (n-->0);

        Console.ReadLine();
    }
}

This prints out palindromes in descending order making use of the n-->0 operator. (as n goes to 0).
*Edited version replaces do...while with while, saving 3 chars, but now you must input with n+1.
using System;using System.Linq;class P{static void Main(){int n=int.Parse(Console.ReadLine());while(n-->0){var t=(n+"").ToArray();Array.Reverse(t);Console.Write(n+""==new string(t)?n+"\n":"");}Console.ReadLine();}}

*edited: found a better way to reverse string without converting to array:
using System;using System.Linq;class P{static void Main(){int n=int.Parse(Console.ReadLine());while(n-->0)Console.Write(n+""==string.Join("",(""+n).Reverse())?n+"\n":"");Console.ReadLine();}}

Readable:
using System;
using System.Linq;
class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        while (n-->0)
            Console.Write(n + "" == string.Join("", ("" + n).Reverse()) ? n + "\n" : "");
        Console.ReadLine();
    }
}

PHP 53
Can 53 be any lower? Four different options:
for($i=$argv[1];$i-->0;)echo$i==strrev($i)?"$i\n":"";
for($i=$argv[1];$i-->0;)if($i==strrev($i))echo"$i\n";
while(($i=$argv[1]--)>0)echo$i==strrev($i)?"$i\n":"";
while(($i=$argv[1]--)>0)if($i==strrev($i))echo"$i\n";

If you want to get funky...
PHP 47
while(($i=$argv[1]--)>0)if($i==strrev($i))`$i`;

You have to ignore the error text. The palindrome numbers are still output to the command line, however.

Burlesque, 13
rz{J<-==}f[p^

Burlesque has some useful commands for golfing, in this case <- reverses anything you put before it.
          rz             creates a range from 0 to input
            {            start of filtering (discards any element not returning 1) the created range
              J <- ==    duplicates element, reverses duplicate, compare
            }f[          end filtering, now we're left with a block of palindromic integer which
            p^           takes care of, and outputs the numbers as desired.

Try it here The linked example has 1000 as input, change it to see more or fewer palindromic numbers.

How does your script accept the input? In your example it seems to be part of the script itself.

@har-wradim Burlesque takes input the same way as Golfscript does. Meaning that input is placed on the stack before the program code.  [input][code]. In my program above input can be any positive number (the linked example has 1000 for input), which will be followed by the code rz{J<-==}f[p^  You can change the 1000 to 10 000 or  100 000 and the code will run all the palindromic number up until the input value.

GolfScript is expected to push what comes from stdin on top of the stack by default. If this behavior is absent from the Burlesque specifications than your solution seems to violate one of the requirements.

@har-wradim As does Burlesque. I linked to the online shell for ease of access, but feel free to download and compile the Burlesque source code to check the different ways it can read input.

@har-wradim wait, it's because I put [Input n] in my explenation, isn't it? Solved!

Burlesque doesn't really specify how input is provided to the program, that's up to the implementation to decide. The recommendation in the 'specification' is to push STDIN as a string to the stack.

Pyth, 11
VhQIq`N_`NN

Example:
$ pyth -c 'VhQIq`N_`NN' <<< 200
0
1
2
3
4
5
6
7
8
9
11
22
33
44
55
66
77
88
99
101
111
121
131
141
151
161
171
181
191

C++, 145 143
#include<iostream>
int i,j,n,r;int main(){std::cin>>n;for(;i<=n;i++){j=i;while(j!=0){r=r*10;r=r+j%10;j=j/10;}if(i==r)std::cout<<i<<' ';r=0;}}

Alternative [143 too]:
#include<stdio.h>
int i,j,n,r;int main(){scanf("%d",&n);for(;i<=n;i++){j=i;while(j!=0){r=r*10;r=r+j%10;j=j/10;}if(i==r)printf("%d ", i);r=0;}}

Python (54)
print filter(lambda i:`i`==`i`[::-1],range(input()+1))

Added print staement

Gogh, 17 bytes
This answer is non-competing, as the language was created after the challenge was posted.
G{÷÷sR=¦?}m0%{Ƥ}m

Usage:
$ ./gogh i 'G{÷÷sR=¦?}m0%{Ƥ}m' <input>

Explanation
        “ Implicit input.                                      ”
G       “ Push an inclusive list.                              ”
{       “ Open a code block.                                   ”
 ÷÷     “ Push two copies of the TOS.                          ”
 sR=    “ Check if the integer is palindromic.                 ”
 ¦?     “ If n is palindromic, yield n. If not, yield 0.       ”
}m      “ Close the code block and map it to the TOS.          ”
0%      “ Remove non-palindromic integers (denoted by zeroes). ”
{       “ Open a code block.                                   ”
 Ƥ      “ Print.                                               ”
}m      “ Close the code block and map it to the TOS.          ”
        “ Implicit output.                                     ”

Zsh, 34 33 bytes
eval \>{0..$1}';ls `ls|rev`;rm *'

Try it online!

{0..$1} - repeat the string with this part substituted with the numbers from 0 to the input
evaluate that

> - create the file with that number
ls - list all the files in the current directory
|rev - reverse that
ls `ls|rev` - print the intersection of the files in the current directory and the output of ls|rev (i.e. filter palindromes)
rm * - remove all files

Husk, 6 bytes
#S=↔Θḣ

Try it online!
'Enumerates' palindromic numbers (so, outputs how many there are).  To list all of them, use fS=↔Θḣ for the same number of bytes.
#        # number of elements that
 S=      # are equal to themselves after
   ↔     # reversing their digits,
    Θḣ   # among 0 followed by 1..input.

Vyxal, j, 5 3 bytes
'Ḃ=

Try it Online!
Pretty simple answer really.
Explained
'Ḃ=
'     # Filter by:
 Ḇ=   #     Bifuricate the argument passed and check if the two results are equal
      # The `j` flag joins on newlines

Stax, 6 bytes
ô°hånⁿ

Run and debug it
-1 byte from Weijun Zhou's answer.

Javascript (ES6), 84 81 74 bytes
u=(n,c=n+1)=>c?u(n,--c).concat(`${c}`.split``.reverse().join``==c?c:[]):[]
u is function.
There's got to be a better way to golf the loop. Php is annoying but at least it has builtins...
Rewrote the whole thing, recursive now. Is there something else for array.concat that pushes nothing?
Why did I have a random argument that did nothing?

When answering with a function, you don't have to assign it to a variable.

@xigoi I think I do, because I need to push to result if necessary. Unless I try a recursive function... Back in 15 mins.

Thunno 2, 4 bytes
ĖæḲ=

Try it online!
Explanation
ĖæḲ=  # Implicit input
Ė     # Push [0..input]
 æ    # Filter by:
  Ḳ   #  Bifurcate it
   =  #  Are they equal?
      # Implicit output

Raku, 29 27 bytes
.flip-$_||.say for 0..slurp

Try it online!

T-SQL, 72
DECLARE @@ INT=X,@ INT=0#:IF @=REVERSE(@)PRINT @ SET @+=1IF @<=@@ GOTO #

Replace "X" with the input number.  This code runs in SQL Server 2008 R2.

Pyke, 6 bytes
S#`D_q

Explanation:
S      - range(1, input()+1)
 #     - filter where True
  `D_q -  str(num) == str(num)[::-1]

Try it here!

Visual Basic for Applications, 66 bytes
Callable from the immediate window.
Sub u(b)
For i=0To b
If StrReverse(i)=i Then Debug.?i
Next
End Sub

Stax, 7 characters
çi/i∩≈f

Run and debug online!
Explanation
Uses the unpacked version to explain.
^rfcEcr=
^r          [0..n]
  f         Print each element that matches the predicate on individual line
   cE       Array of decimal digits
     cr=    Equals its reverse

Javascript, 98 bytes
n=>new Array(n+1).fill().map((a,b)=>b).filter(a=>[...''+a].reverse().join``==''+a&&(a<=n)).join` `

PowerShell, 67 bytes
0..$args[0]|%{$x=[string]$_;if($x-eq(-join$x[-1..-$x.length])){$x}}

Try it online!

Haskell, 45 bytes
f n=filter(\x->show x==(reverse.show)x)[0..n]

Try it online!
Input is an Int, output is a [Int]


text:
Count the number of times a function runs
This is a teaser a friend of mine sent. It seems straightforward, but I can't seem to get my head around it, probably due to my lack of sleep.

You have 16 bits available.
Compose a function, and find a way to know when the function has run approximately one million times.
You MAY NOT use any additional memory space other than the 16 bits given.
Recursion may be used for efficiency, but, again, you MAY NOT use
memory definition inside the recursion frames: only the 16 bits.

What is the 16 bits?  16 bits of function definition in machine language?  16 bits of memory storage, but the function can be as large as necessary?  What is this function supposed to do?  Stop when it has been run one million times?  Display a message when it has been run one million times?  Is this function being randomly called by another program and you have to track, or is this function being run one million times in a row at the same time?  Can you describe in pseudo-code how this function works/is used in this process?

Superbly underspecified.

I understand: store the number of invocations (or whatever you like) in 16 bits. But should be clarified.

Bearing in mind that a standard PRNG, which all the approachs so far are using, probably has at least 48 bits of internal state, that approach fails point 3.

@Peter Mine doesn't use random numbers...

@Gareth: But 1st: you're about 5% away, and 2nd: you're forced to call your function 16 times in sequence. You can't count incoming emails, for example, this way.

@Peter: I don't think that my solution depends on a PRNG with 48 bits internal state. The only number which really doesn't fit into a short is the number of tests, to test my code. The PRNG only needs to produce shorts. However, a PRNG with 16 bits of state, is of course, together with 16 bits for a counter, 32 bit.

@user unknown, you're only asking the PRNG for 16 bits at a time, but I bet it uses more than that internally because otherwise its cycle would be so short that it would be seriously deficient. In fact, since it's Scala you're using Java's PRNG, which is documented to have 48 bits of internal state.

Not deficient for this task.

@user unknown I am inaccurate, yes - but the question does say approximately and changing the loop comparison to use 62500 like everyone else fixes that problem. Yes, I am forced to do a contrived thing like calling a function 16 times in a row, but the whole question is contrived - it is a puzzle after all.

See 2.: You have to compose a function, and count, how often it is called. You're composing a function, and count another functions invocations (which isn't composed - it's just a name).

@Peter Taylor:  Yeah, I had similar reservations about the random number generator.  However, because the problem does not specify hardward requirements other than memory, I'd use a CPU with a built-in random number generator.  I.E. It loads register 1 with x, register 2 with y, and then runs the random number generator instruction to load register 1 with a random number between x and y.  This would carry the same weight as an addition, and if we can't add, what can we do?  ;)

@user unknown That's not the way I read 2. It says 'find a way to know when the function has run 1 million times'. I do that. It's not very useful because the million times are all in succession, but that was not in the restrictions.

no love for this question :(

One-million in binary is equal to 11110100001001000000 (20 bits).  Thus, we cannot implement a simple counter for this.
Instead, the max number we can represent with 16 bits is 1111111111111111 = 65,535.  Since the answer requires that we only need to approximate 1 million function runs, we could add one to the counter approximately once every 16 function runs, and know that the function has run about 1 million times when the counter reaches 1000000/16 = 62500.
Below is the pseudocode of a potential solution, assuming that counter is a positive integer stored in 16 bits.  Also, this assumes that calls such as random(1,16) do not count towards memory as long as they are not stored in a variable.  Last, the random(x,y) function should give a random integer between x and y inclusive.
counter = 0;

function amIAttaBoutaMillionYet(){
    if(random(1,16)==16 && counter<62501){
        counter++;
    }
    if(counter==62500){
        return true;
    }
    return false;
}

UPDATE
Fixed function so that it won't show true after about 2 million+, 3 million+, etc.   function runs.  (thanks trinithis!)

This suffers from overflow if called too much, as numbits(counter) <= 16. Add a guard against incrementing counter if counter is greater than some number (say counter > 62500).

@trinithis:  Thanks, I missed that!

Beaten to it by Briguy37. :-(
Just call the function code 16 times for each tick of the counter.
def function()
{
    do stuff here...
}
while(loop<65535)
{
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    loop+=1
}

+1 for finding a different rule to break. (You're breaking rule 2 as specified, because you're executing the function 1m times rather than finding out when it's been called 1m times).

@Garet:  You could make the function private and then turn the while loop into a public controller function that runs the function 16 times, increments the counter, and then returns if the function has run about 1 million times.  You could even make it know when the function has run exactly 1 million times if you synchronized the controller method.  Admittedly, then the function can never have a single run, which doesn't break any rules, but it doesn't feel right either :)

Sorry Gareth...that's twice now I've typed your name wrong...doh!

You could make it so that for every external call of function A, A is called another 999,999 times internally. Therefore, you are guaranteed that that last internal call is the millionth call.
var internal = false;
function A() {
    if (internal)
        return;

    internal = true;

    A();
    A();
    // ...999999 times...
    A();
    A(); // This last call is guaranteed to be the millionth call

    internal = false;
}

A();

The obvious approach is self-modifying code. Something along the lines of (and bearing in mind that I scarcely ever touch C, consider this to be pseudocode and don't try compiling it)
uint16 counter = 0;

void fun() {
    byte x = 0;
    if (x == 15) counter++;
    (*fun)=(x+1)&15;
    if (counter == 62500 && x == 0) sprint("Jackpot!");
}

It is, of course, cheating, but so is every possible approach, because the problem taken literally violates basic principles of information theory. And there may be a small offset needed when overwriting the initial value of x: depends on your processor and compiler. (No, I'm not going to dig out my notes on ARM assembler just for this).

If you've got an additional variable x, aren't you breaking the 'only 16 bits' rule?

@Gareth, observe the text It is, of course, cheating. It is mathematically impossible to solve this problem without breaking that rule; therefore the purpose of the puzzle must be to find inventive ways of breaking it.

Fair point, I missed that bit.

Primary answer:
Does not use crazy macro expansion. Uses recursion and two 8 bit variables. The code works by recursing enough such that the first call to foo generates enough calls where the function is called approximately 1 million times.
//unsigned long count = 0;
//unsigned long numTimesTrue = 0;

#define SET_HIGH(x) (x |= (unsigned char)(1 << 7))
#define MASK_HIGH(x) (x & (unsigned char)~(1 << 7))
#define TEST_HIGH(x) (x & (unsigned char)(1 << 7))

int foo (unsigned char n = 0) {
    static unsigned char i;
    //++count;
    if (n == 0) {
        SET_HIGH(n);
    }
    if (MASK_HIGH(i) >= 20) {
        return 0;
    }
    for (i = n; MASK_HIGH(i) < 20; ++i) {
        n = i;
        foo(MASK_HIGH(i) + 1);
        i = n;
    }
    //if (TEST_HIGH(i) != 0) ++numTimesTrue;
    return TEST_HIGH(i) != 0;
}

int main () {
    int r1 = foo(); // 1, count == 1048576
    int r2 = foo(); // 0, count == 1048577
    int r3 = foo(); // 0, count == 1048578
    //assert(numTimesTrue == 1);
    return 0;
}

Secondary answer:
This returns true only once and only when the function has been run approximately 1 million times. I'm talking liberty in the usage of the word approximate in that the integers are unbounded. (1 is approximately 1,000,000 with respect to 100!!!!!! (you have to figure out which are factorials and which are exclamation points).)
int foo () {
    static int hasRun = 0;
    if (!hasRun) {
        hasRun = 1;
    }
    return !hasRun;
}

Well, similar to Briguy37. I divided the 16 bits to two 8 bits vars. low byte is incremented on every call and reset when it reaches 250. On reset of low byte increment hi. When hi reaches 4000 (1000000/250 = 4000), we have 1 million calls
    byte hi=0
    byte lo=0

    function oneMillionCallFunction()
        lo++
        if lo==250 then
            hi++
            lo=0
        if hi==4000 then
            return true
        return false

hi will never reach 4000 (this requires 12 bits and lo's 250 requires 8: 8+12=20)

ohh.. i should not code after drinking.. :P

In fact, keeping two 8-bit numbers and incrementing the high-bit one every time the low-bit one overflows is exactly the same as keeping one 16-bit number.

to implement Briguy's solution in D
import std.random;
bool foo(){
    static ushort count = 0;//16 bits
    if(uniform(0,16)==0)count++;//increment once in approx every 16 calls
    if(count==62500)return true;//we're close enough
    return false;
}

This scala-code contains the test, to see how much we are away:
val r = util.Random

def resetAndTest () {

var x = 0 : Short

def mioFun (n: Int) = {
  if (r.nextInt (30518) < 1000)
    x = (x + 1).toShort
  if (x < 0) {
    println ("n calls " + n )
    true }
  else false
}

(1 to 1010000).find (mioFun)

}

typical results:
scala> (1 to 10).foreach (_ => resetAndTest)
n calls 1001214
n calls 1000340
n calls  993883
n calls 1005774
n calls 1001670
n calls  997401
n calls 1009786
n calls  992853
n calls 1002313
n calls 1002992

I just had a strange idea - but it works. This python version works without any counter. The one-millionth call returns 1 any other the value 0.
def fun():
    global f
    try:
      f
    except NameError:
      def fun_int():
        yield 0
        yield 0
        ...
        yield 0
        yield 1
        while 1:
          yield 0
      f = fun_int()
    return f.__next__()

print(fun())
print(fun())
...
print(fun())
print(fun())

Unfortunately the generator reference f takes some bits - so please use a python implementation which does it in 16 bits or less.

Since Peter Taylor points out that using a PRNG may violate the 16-bit limit, what about using the system time? Would that also violate the limit?
In PHP:
$counter = 0;
function maybeOneMillion() {
  global $counter;
  $time = gettimeofday();
  if ($time['usec'] % 100 == 0) {
    $counter++;
    if ($counter == 10000) return true;
  }
  return false;
}

Python
Likely also bending the rules:
x = 0
def f():
    global x
    if x < 20:
        x = x + 1
        f()
        f()
        x = x - 1

Arguably could do with just 5 bits, and would probably be shorter in C. Stretches rule (3) perhaps a bit.

Protip: f.x No need for globals here.

C
it's actually 6 bit.
(Does rand() == 12679 count...?)
void func(void)
{
    static struct {
        unsigned short int count : 6;
    } S = {42};
    if (rand() == 12679)
        S.count--;
    if (!S.count)
        puts("1 MILLION REACHED");
}

C
This answer changes the name of the process, and more precisely uses the first character of the name as an additional 8-bits counter.
#include <stdio.h>

int main(int argc, char* argv[])
{
unsigned short cpt=0;

argv[0][0]=0;
while(argv[0][0]!=20)
    {
    cpt++;

    /* the function printf is called 1.0000.000 times */
    printf("ok\n");

    if (cpt==50000)
        {
        cpt=0;
        argv[0][0]++;
        }
    }

}

source: Stack Exchange

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

sort: votes


text:
Detect loops in a linked list
This comes from one of my favorite interview questions, though apparently it is now a fairly well-known puzzle. I have no way of knowing, but if you have already heard the answer it would be polite to let others try instead.
Task:
Write a function that takes as input a singly-linked list and returns true if it loops back on itself, and false if it terminates somewhere.
Here's some example code in C as a starting point so you can see what I mean, but feel free to write your answer in whatever language you like:
struct node
{
    void *value;
    struct node *next;
};

int has_loops(struct node *first)
{
    /* write your own loop detection here */
}

Hints:
There is a way to make this function run in O(n) time with a constant amount of extra memory. Good on you if you figure it out, but any working answer deserves some upvotes in my book.

You can make this more general (and applicable to languages which don't have pointers and references) if you rephrase it in terms of a function f:int->int. Given f and x0, let F(x) = if x=0 then 0 else f(x). Is there an int n such that f^n(x0) = 0?

That should, of course, read F^n(x0) = 0

@Peter: Yes, that's about equivalent, although the way you describe f suggests that it is a total function when it isn't. For example, it isn't correct to call f on any value that isn't of the form f^k(x0) for some k. Think about it like a monad if you want to apply it more generally, not as a function whose domain is integers.

I was aiming at a puzzle which is applicable to as many languages as possible and intelligible to people who aren't advanced Haskell hackers. And bearing in mind C's weak type system, f is a total function.

I suppose if you want to instantly segfault, you can treat f as a total function :)

This could be nicely asked as a logic question to a person:
You and your friend are in a maze and suspect you have been traveling in a circle, how can you confirm your suspensions? What if you have no items and are completely naked. The second would be analogous to having no memory in a system.
The first could be solved using bread crumbs or what not, however you could tell the person the loop may be 100km, do you have enough bread?

With no winning criterion whatsoever this does not seem to belong here at all.

C, non-golfed
The idea is to have to pointers p1 and p2 that traverse the list. p2 moves twice as fast as p1. If p2 reaches p1 at some point then there is a loop. Here is the C code (not tested, though).
struct node
{
  void *value;
  struct node *next;
};

int has_loops(struct node *p)
{
  struct node *p1 = p, *p2 = p->next;
  if (!p2) return 0;

  while (p1 != p2) {
    // p1 goes one step
    p1 = p1->next;
    if (!p1) return 0;

    // p2 goes two steps
    p2 = p2->next;
    if (!p2) return 0;
    p2 = p2->next;
    if (!p2) return 0;
  }

  return 1;
}

The line if (!p1) return 0 could be replaced by assert p1 if you really want to check for bugs in your compiler.

PT: Sure. I will leave it like this for symmetry. Could also make a #define ADVANCE(p) if (!(p = p->next)) return 0

Ada
The "Floyd's Cycle-Finding Algorithm" is the best solution. It's also called "The Tortoise and the Hare Algorithm".
linked_lists.ads:
generic
   type Element_Type is private;
package Linked_Lists is

   type Node is private;
   type List is private;

   function Has_Loops (L : List) return Boolean;

private

   type List is access Node;
   type Node is record
      Value   : Element_Type;
      Next    : List;
   end record;

end Linked_Lists;

linked_lists.adb:
package body Linked_Lists is

   function Has_Loops (L : List) return Boolean is
      Slow_Iterator : List := L;
      Fast_Iterator : List := null;
   begin
      -- if list has a second element, set fast iterator start point
      if L.Next /= null then
         Fast_Iterator := L.Next;
      end if;

      while Fast_Iterator /= null loop

         -- move slow iterator one step
         -- guaranteed to be /= null, since it is behind fast iterator
         Slow_Iterator := Slow_Iterator.Next;

         -- move fast iterator one step
         -- guaranteed to be valid, since while catches null
         Fast_Iterator := Fast_Iterator.Next;
         -- move fast iterator another step
         -- null check necessary
         if Fast_Iterator /= null then
            Fast_Iterator := Fast_Iterator.Next;
         end if;

         -- if fast iterator arrived at slow iterator -> loop detected
         if Fast_Iterator = Slow_Iterator then
            return True;
         end if;

      end loop;

      -- fast iterator arrived end, no loop present.
      return False;
   end Has_Loops;

end Linked_Lists;

here is the implementation of the Brent algorithm:
package body Linked_Lists is

   function Has_Loops (L : List) return Boolean is
      Turtle : List     := L;
      Rabbit : List     := L;
      Steps  : Natural  := 0;
      Limit  : Positive := 2;
   begin

      -- is rabbit at end?
      while Rabbit /= null loop

         -- increment rabbit
         Rabbit := Rabbit.Next;
         -- increment step counter
         Steps := Steps + 1;

         -- did rabbit meet turtle?
         if Turtle = Rabbit then
            -- LOOP!
            return True;
         end if;

         -- is it time to move turtle?
         if Steps = Limit then
            Steps := 0;
            Limit := Limit * 2;
            -- teleport the turtle
            Turtle := Rabbit;
         end if;

      end loop;

      -- rabbit has reached the end
      return False;
   end Has_Loops;

end Linked_Lists;

It's provably not the best solution, actually.

What do you mean, Peter?

well, it is O(n) time and O(1) space, seems optimal for me

Apparently, Brent's cycle detection algorithm is faster.

@Clueless, Gareth's comment is precisely what I meant. It's like A* vs Dijkstra: asymptotically they're the same but you can prove that A* will never do more work than Dijkstra and that it will sometimes do less.

I don't think the two situations are really comparable. A* gives average-case asymptotic speedup for many problems, whereas since Floyd's algorithm is already within a constant factor of optimal there's not much you can do to improve it.

added implementation of brent's algorithm

Since the solution is already in the open, I think it's fair to step in now with Brent's algorithm, which is the one I'm familiar with from integer factorisation.
#define bool int
#define false 0
#define true 1

bool has_loops(struct node *first) {
    if (!first) return false;

    struct node *a = first, *b = first;
    int step = 1;

    while (true) {
        for (int i = 0; i < step; i++) {
            b = b->next;
            if (!b) return false;
            if (a == b) return true;
        }

        a = a->next;
        if ((step << 1) > 0) step <<= 1;
    }
}

Haskell
Naive algorithm:
import Data.Set (Set)
import qualified Data.Set as Set

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

hasLoop :: [Node a] -> Bool
hasLoop = hasLoop' Set.empty

hasLoop' :: Set Id => [Node a] -> Bool
hasLoop' set xs = case ns of
  [] -> False
  x:xs' -> let
    ident = getId x
    set' = Set.insert ident set
    in if Set.member ident set
      then True
      else hasLoop' set' xs'

Floyd's Cycle-Finding Algorithm:
import Control.Monad (join)
import Control.Monad.Instances ()
import Data.Function (on)
import Data.Maybe (listToMaybe)

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

next :: [a] -> Maybe [a]
next [] = Nothing
next (_:xs) = Just xs

nexts :: [a] -> [a] -> (Maybe [a], Maybe [a])
nexts xs ys = (next xs, next $ next ys)

hasLoop :: [Node a] -> Bool
hasLoop = uncurry hasLoops' . join nexts

hasLoop' :: Maybe [Node a] -> Maybe [Node a] -> Bool
hasLoop' (Just xs) (Just ys)
  | on (==) (getId . listToMaybe) xs ys = True
  | otherwise = uncurry hasLoop' $ nexts xs ys
hasLoop' _ Nothing = False
hasLoop' Nothing _ = False -- not needed, but there for case completeness

D
This is a solution I thought of myself. It runs in O(n) and uses O(1) memory.
What I'm doing is simply iterating through the list and reversing all the pointers. If the list contains a cycle, you'll eventually end up at the beginning of the list and otherwise you end up at the end, which is somewhere else if your list is longer than 1. Now you've determined the result you can restore the list by simply reversing the pointers again.
Here is my code and a test:
import std.stdio;

// The list structure.
struct node(T)
{
    T data;
    node!T * next;

    this(T data) {this.data = data; next = null;}
}

bool hasLoop(T)(node!T * first)
{
    // List shorter than two nodes has no loops.
    if(!first || !first.next)
    {
        return false;
    }

    // Keep iterating through the list, while reversing the pointers.
    node!T * previous = null,
             current = first;
    while(current)
    {
        auto next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    // If the last node was the beginning of the list, there was a cycle.
    // Otherwise, there are none.
    bool result = previous == first;

    // Do the reversal again to restore the list to its original state.
    current = previous;
    previous = null;
    while(current)
    {
        auto next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    // Done!
    return result;
}

// Test
unittest
{
    // Build a list.
    int[] elems = [1,2,3,4,5,6,7,8,42];

    auto list = new node!int(elems[0]);
    auto curr = list;
    foreach(x; elems[1..$])
    {
        curr.next = new node!int(x);
        curr = curr.next;
    }

    // Outcomment the line below to test for a non-cycle list.
    curr.next = list.next.next.next;

    // Do cycle check.
    writeln(hasLoop(list) ? "yes" : "no");

    // Confirm the list is still correct.
    curr = list;
    for(int i = 0; i < elems.length; ++i, curr = curr.next)
    {
        assert(curr.data == elems[i]);
    }
}

If you iterate through the list once to reverse the pointers, and then once more to put them back the way they were originally, isn't that O(2n)?

@Gareth, O-notation ignores constant factors.

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


text:
Maximize order of operations
Here's a problem to which I don't know the answer. Suppose you have an ordered list of integers with an operator in between each consecutive pair. Let's restrict ourselves to three operations that are closed over the integers, namely addition, multiplication and subtraction. Is there a good way to find the order we should perform the operations such that the expression evaluates to the maximum value?
For example, given the input 5 * 5 - 3 + 8 * -2 the correct order is to first perform the addition leading to 5 * 5 - 11 * -2, then perform the last multiplication leading to 5 * 5 - -22, then perform the subtraction leading to 5 * 27, then perform the final multiplication giving 135, which is maximal.
The question is: does there exist a reasonably efficient way to find this answer? I can see some tricks that might help a little, but I can also see some roadblocks.
Here's a program in python that computes the solution in the dumb recursive O(2^n) fashion. It might be helpful to check answers.
def find_max(x):
    if len(x) == 1:
        return x[0]
    y = [find_max(contract(x, i)) for i in xrange(len(x)//2)]
    return max(y)

def contract(x, i):
    return x[:2*i] + [do_op(*x[2*i:2*i + 3])] + x[2*i + 3:]

def do_op(left, op, right):
    return {"+": left + right, "-": left - right, "*": left * right}[op]

init = [int(x) if i%2 == 0 else x for i,x in enumerate(raw_input().split())]
print find_max(init)

Usage: python findmax.py < in.txt where in.txt contains a sequence like 4 * -3 + 6 - 2 * 10.
Is there a significantly faster way?

You could use dynamic programming to get some improvement. But does this belong here or on StackOverflow?

I'd say it belongs here as it's a programming puzzle.

From the FAQ: `All questions on this site, whether a programming puzzle or a code golf, should have …
An objective primary winning criterion, so that it is possible to indisputably decide which entry should win.`

Your example is bad. After performing the addition (1st step), you should have 5 * 5 + 5 * -2.

@trinithis: I think Clueless had in mind 5 * 5 - (3 + 8) * -2 for the first addition step.

Haha, whoops. You're right.

Maybe the challenge should be "best asymptotic complexity".  I posted an O(n³) solution; maybe someone else can do better.

Haskell, O(n3)
import Data.Array

data Op = Plus | Minus | Times

exampleTerms :: [Integer]
exampleTerms = [5, 5, 3, 8, -2]

exampleOps :: [Op]
exampleOps = [Times, Minus, Plus, Times]

main = print $ maximalOrder exampleTerms exampleOps

type MinMax = (Integer, Integer)

-- Given an operator and minimal/maximal values for left- and right-hand sides,
-- compute the minimal/maximal value of the expressions joined together with this operator.
combine :: Op -> MinMax -> MinMax -> MinMax
combine Plus  (lmin, lmax) (rmin, rmax) = (lmin + rmin, lmax + rmax)
combine Minus (lmin, lmax) (rmin, rmax) = (lmin - rmax, lmax - rmin)
combine Times (lmin, lmax) (rmin, rmax) = (minimum ps, maximum ps)
    where ps = [lmin * rmin, lmin * rmax, lmax * rmin, lmax * rmax]

maximalOrder :: [Integer] -> [Op] -> Integer

maximalOrder []    _                 = error "maximalOrder: No terms"
maximalOrder terms ops
    | length terms /= length ops + 1 = error "maximalOrder: Mismatched terms/ops lists."

maximalOrder terms ops = snd $ minMax 0 (termCount - 1) where
    termCount :: Int
    termCount = length terms

    termsA :: Array Int Integer
    termsA = array (0, termCount-1) $ zip [0..] terms

    opsA :: Array Int Op
    opsA = array (0, termCount-2) $ zip [0..] ops

    dp :: Array (Int, Int) MinMax
    dp = array ((0,0), (termCount-1,termCount-1))
         [((start, end), minMax start end)
             | start <- [0..termCount-1], end <- [start..termCount-1]]

    minMax :: Int -> Int -> MinMax
    minMax start end
        | start == end =
            let x = termsA ! start
            in (x,x)
        | otherwise =
            let xs = [combine (opsA ! i) (dp ! (start,i)) (dp ! (i+1,end)) | i <- [start..end-1]]
            in (minimum (map fst xs), maximum (map snd xs))

This computes the minimal and maximal values of every substring in the expression, by going through each intervening operator and finding the minimal/maximal result of treating that operator as the root of the expression.  It collects these results into the overall minimal and maximal values for this substring.
This algorithm runs in O(n3) time and uses O(n2) space.  Finding the minimal/maximal value of an expression string, once its substrings have been visited, takes O(len), where len is the length of the substring.  The minimal/maximal value of every substring needs to be computed:
1..5
1..4 2..5
1..3 2..4 3..5
1..2 2..3 3..4 4..5
1..1 2..2 3..3 4..4 5..5

In this case, it takes 5*1 + 4*2 + 3*3 + 2*4 + 1*5.  In general, the number of operations grows in a cubic fashion.
At the heart of the algorithm is the combine function, which takes an operator and the minimal/maximal values of each of its operands, and produces the minimal/maximal results.
To maximize the result:

If adding two numbers, maximize both arguments.
If subtracting two numbers, maximize the left argument and minimize the right argument.
If multiplying two numbers, try the following:

Maximize both arguments.  This gives us the maximal result when multiplying two positive numbers.
Minimize both arguments.  This gives us the maximal result when multiplying two negative numbers, since a negative times a negative equals a positive.
Minimize the left argument and maximize the right argument, or vice versa.  We'd rather multiply two positives or two negatives and get a positive result, but if we have to multiply a positive and a negative and get a negative result, we want it to be as close to zero as possible.  To do so, we minimize the positive number and maximize the negative number.

This is a very clever optimization, I like it.


text:
Descending Sort using Standard Ascending Sort Function
Taking an array of records. For example
[
name: 'eventA', timestamp: '2011-08-27 15:34:00',
name: 'eventB', timestamp: '2011-08-28 13:31:00',
name: 'eventC', timestamp: '2011-08-29 10:34:00',
name: 'eventD', timestamp: '2011-08-30 16:36:00',
]

How can I sort these by timestamp in a descending using a standard natural ascending sort algorithm built into most languages. E.g.
E.g
C#: collection.Sort(record => record.timestamp)
Python: sort(collection, lambda record: record.timetstamp)
You can not use the sortByDescending methods, of course most languages have them (or a flag to sort fn for descending)
Somehow have to transform the record.timestamp so that it sorts descending
Solution 1:
Parse the date into a Date object provided by most languages and get time in milliseconds/seconds since 1970. Minus the amount from 0 to get the negated value and sort by this.
Extra points for no expensive date conversions

reverse . sort

-1 There's no challenge or puzzle here at all.

Maybe we should introduce a "rosetta stone" tag, and have the goal be to solve the problem in a variety of languages.

C++: std::sort(array.rbegin(), array.rend())

Haskell
sortByDescending cmp = sortBy (flip cmp)

Example:
import Data.List
import Data.Function
import Data.Maybe
import Data.Time.LocalTime
import Data.Time.Parse      -- requires module strptime

data Record = Record {
    name      :: String,
    timestamp :: LocalTime
} deriving Show

sortByDescending cmp = sortBy (flip cmp)

sortByTimestampDescending :: [Record] -> [Record]
sortByTimestampDescending = sortByDescending (compare `on` timestamp)

parseExample :: (String, String) -> Record
parseExample (n,t) = Record n (fst $ fromJust $ strptime "%Y-%m-%d %H:%M:%S" t)

examples :: [Record]
examples = map parseExample
    [("eventA", "2011-08-27 15:34:00")
    ,("eventB", "2011-08-28 13:31:00")
    ,("eventC", "2011-08-29 10:34:00")
    ,("eventD", "2011-08-30 16:36:00")]

main = mapM_ print $ sortByTimestampDescending examples

Output:
Record {name = "eventD", timestamp = 2011-08-30 16:36:00}
Record {name = "eventC", timestamp = 2011-08-29 10:34:00}
Record {name = "eventB", timestamp = 2011-08-28 13:31:00}
Record {name = "eventA", timestamp = 2011-08-27 15:34:00}

D
retro(sort!"a.timestamp<b.timestamp"(array));

or
retro(schwartzSort!"a.timestamp"(array));

(you need to import std.algorithm and std.range)
though honestly reversing an array without a build-in function is simple as it is
int i=0,j=arr.length;while(i<--j)swap(arr[i++],arr[j]);

or without a swap function:
int i=0,j=arr.length;while(i<--j){auto tmp=arr[i];arr[i++]=arr[j];arr[j]=tmp;}

Scala:
val src = """name: 'eventA', timestamp: '2011-08-27 15:34:00', name: 'eventB', timestamp: '2011-08-28 13:31:00', name: 'eventC', timestamp: '2011-08-29 10:34:00', name: 'eventD', timestamp: '2011-08-30 16:36:00'"""

class NT (name: String, val n: String, time: String, val ts: String)
val nts = src.split ("[,:] ").sliding (4, 4).map (l =>
    new NT (l(0), l(1), l(2), l(3))).toList
nts.sortWith ((a, b) => a.ts < b.ts).reverse.foreach (k =>
    println (k.ts + " " + k.n))

Result:
'2011-08-30 16:36:00' 'eventD'
'2011-08-29 10:34:00' 'eventC'
'2011-08-28 13:31:00' 'eventB'
'2011-08-27 15:34:00' 'eventA'


text:
Arithmetic Golf: Reach 2011
This is an ai-player challenge. Your goal is to reach the number 2011 as quickly as possible, or to get as close to it as you can.
Rules:

A "hole" consists of a rectangular grid of digits (0-9).
Your total starts at 0.
You may start at any digit on the grid. This is your first "stroke."
For each subsequent stroke, you may move to any immediately adjacent digit (up, left, down, right). However, you may not move to a digit that you have used before.
With each stroke, you will use your current total and the digit at your current position as operands (the total is always the first operand), and apply one of the four basic arithmetic operations (+ - * /). The result will become your new total.
If your total becomes 2011, your score for the course is the number of strokes.
If you have no more valid moves, your score is your current number of strokes + your total's distance from 2011.
You may also choose at any time to stop, and your score will be your current number of strokes + your total's distance from 2011.

Input:

You will read in a file containing data for each "hole." Alternatively, you may accept the input through stdin or an equivalent.
Each hole will consist of H rows of W digits, for a grid of size WxH. H and W may vary per hole.
The holes will be separated by a single blank line.
In the spirit of golf, the competition will consist of 18 holes, but your program should be able to handle any number of them.

Output:

For each hole, your program should output the position of the starting digit. The position should be given as (row, col) where the top-left is (0, 0).
For each stroke, your program should output the chosen operation, the current digit, and the resulting total.
At the end of each hole, whether you reach 2011 or not, your program should output your number of strokes and your score for the hole (usually the same as the number of strokes).
For testing purposes, you may also find it helpful to output your path on each board indicating which digits were used. However, you will not be required to provide this output for the competition.

Notes:

For any given hole, your program should always start at the same position and choose the same route (i.e., no random choices). The starting position does not need to be the same for every hole.
The total is not limited to the integers. That is, if you divide 4023 by 2, your total would become 2011.5, and you would still be .5 away from the goal.
Your program should run in a "reasonable" amount of time.
For purposes of verifiability, your program should be runnable on an online interpreter such as ideone.com.
The winner is the program that has the lowest overall score for the entire course. If there is a tie, the tying programs will play a new course, hole-for-hole, with the lowest scorers advancing until there is only one winner. If there is still a tie after the tiebreaker course, the program submitted first will win.

Deadline:

The current deadline for this competition is September 10, 2011. This deadline may be extended, depending on interest.

Sample input:
14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

Sample output:
Start: (3, 7)
+4=4
*9=36
*9=324
*6=1944
+9=1953
+8=1961
+8=1969
+9=1978
+6=1984
+8=1992
+8=2000
+8=2008
+4=2012
-1=2011
Strokes: 14
Score: 14

14932875921047
6043....014654
563..65.108239
90..208.187569
94.76198569386
...97356029523

Sample output (compact):
Start: (3, 7)
+4=4 *9=36 *9=324 *6=1944 +9=1953 +8=1961 +8=1969 +9=1978 +6=1984 +8=1992 +8=2000 +8=2008 +4=2012 -1=2011
Strokes: 14   Score: 14

Sample input:
0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

Sample output:
Start: (4, 7)
+3=3
*6=18
*5=90
+7=97
*5=485
*4=1940
+7=1947
+8=1955
+9=1964
+8=1972
+6=1978
+7=1985
+3=1988
+4=1992
+5=1997
+5=2002
+5=2007
+3=2010
+1=2011
Strokes: 19
Score: 19

0346092836
.986249812
..68086343
..09828197
.61248..55
.02574.681
...504.124
20.....313

Sample input:
9876
5432
1098
7654
3210

Sample output:
Start: (2, 2)
+9=9
*8=72
*4=288
*5=1440
+6=1446
+7=1453
+3=1456
+2=1458
+1=1459
Strokes: 9
Score: 561

9876
5432
10..
....
....

Sample input:
39857205
74493859
02175092
54239112
39209358
34568905

Sample output:
Start: (0, 0)
+3=3
*7=21
*4=84
*4=336
-1=335
*2=670
/3=(670/3)
*9=2010
+1=2011

.9857205
...93859
02.75092
54....12
39209358
34568905

Results
Unfortunately, there were only two contestants, but I'll post the results.
#1 - Howard (1881)
#2 - Gareth (5442)

The first half of the course consisted of roughly "normal" holes, generated mostly randomly. The second half was more challenging, as the holes contained more "sand traps" (sections deliberately filled with low numbers, especially 0s).
**Howard**
01) 5 - 5
02) 5 - 5
03) 6 - 6
04) 6 - 7
05) 6 - 7
06) 6 - 6
07) 5 - 5
08) 5 - 5
09) 6 - 6
10) 9 - 10
11) 5 - 8
12) 8 - 8
13) 6 - 7
14) 8 - 9
15) 7 - 12
16) 20 - 1665
17) 29 - 66
18) 30 - 44
Front 9) 52
Back  9) 1829
Full 18) 1881

**Gareth**
01) 9 - 10
02) 33 - 173
03) 8 - 8
04) 11 - 16
05) 7 - 84
06) 17 - 17
07) 9 - 10
08) 8 - 8
09) 15 - 15
10) 16 - 16
11) 12 - 32
12) 18 - 164
13) 34 - 335
14) 10 - 10
15) 26 - 447
16) 78 - 78
17) 1 - 2010
18) 1 - 2009
Front 9) 341
Back  9) 5101
Full 18) 5442

The course used can be found on pastebin.
@Howard: I ran your program with the lower number of paths due to limits on ideone. If your full version gives significantly different results, let me know the scores and the relative running time of the program.

Is the new total always   , or can it be   ?

@J B Always   . I'll update the description to make it clearer.

'Your program should run in a "reasonable" amount of time.' Should this not be properly specified? It seems you just want to prevent the brute-force solution, but there are other algorithms that also take quite a long time. Is 10 minutes per hole on a normal dual-core ok? An hour? The whole time from finishing the program till 09-10-2011 for the entire course, when running on a state-of-the-art mainframe? — And as for the non-randomness, is this just for being repeatable? Certainly, we may use a pseudo-random generator with a fixed seed? Or do you really want no Monte-Carlo?

@leftaroundabout I'm not sure how to properly specify what "reasonable" is without a standard environment. I suppose that since I'll be testing these on ideone, it should run to completion there, which I think means a maximum of 15 seconds per hole. Also, the non-randomness is indeed just for verifiability. You may use a PRNG with a fixed seed, since that should result in the same output every time.

@migimaru With larger number of paths it is 39 strokes less with a runtime of 150s for the complete course. Still hole 16 smashes my arithmetic golfer.

Java - The Why-Not-Try-It-The-Easy-Way-Approach
Here is my first submission for this problem. I don't know if it qualifies for ai-player because it is more "artifical clumsiness". Maybe I can do better but I think it is hard to beat it on most grids.
The program just takes paths and operations calculated by a very complicated and clever algorithm (no, it's not random ;-) It will give you the same result every time) and compares all of them to find the best one.
Input must be given on STDIN. You can see the examples running here (note: number of paths reduced).
The output for above holes is
Start: (4, 0)
+9=9
*4=36
*8=288
*7=2016
-6=2010
Strokes: 5
Score: 6

Start: (3, 3)
+9=9
*8=72
*4=288
*7=2016
-5=2011
Strokes: 5
Score: 5

Start: (0, 2)
+7=7
*8=56
*4=224
-0=224
*9=2016
-5=2011
Strokes: 6
Score: 6

Start: (2, 3)
+7=7
*9=63
*4=252
*8=2016
-5=2011
Strokes: 5
Score: 5

The program itself is given below (it makes use of lots of static declarations - don't try this at home).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class Main {

    // DEBUG=true displays progress
    private static final boolean DEBUG = false;

    // Number of paths to try
    private static final int PATHS = 10000000;

    // Saves the number grid
    static int[][] grid;

    // start position
    static int startx;
    static int starty;

    // used digits and operations
    static int[] ns = new int[1024];
    static int[] ops = new int[1024];

    // current best score and output for this score
    static double bestScore;
    static String best;

    // a random number generator
    static Random random;

    public static void main(String[] args) throws IOException {
        BufferedReader cons = new BufferedReader(new InputStreamReader(System.in));

        String[] conLines = new String[1024];
        int numLines = 0;

        while (true) {
            String line = cons.readLine();
            if (line == null || line.isEmpty()) {
                // already some lines found
                if (numLines > 0) {
                    // prepare grid and run algorithm
                    prepareGrid(conLines, numLines);
                    findBest();
                    System.out.println(best);
                }
                numLines = 0;
            } else {
                conLines[numLines++] = line;
            }
            if (line == null)
                break;
        }
    }

    private static void findBest() {
        random = new Random(1);
        bestScore = 9999e99;
        for (int k = 0; k < PATHS; k++) {
            int sx = startx = random.nextInt(grid.length);
            int sy = starty = random.nextInt(grid[0].length);
            doStep(0, 1, 0, sx, sy);
        }
    }

    private static void doStep(int num, int den, int steps, int sx, int sy) {
        // consume the digit at the current position
        ns[steps] = grid[sx][sy];
        grid[sx][sy] = -1;

        // choose random operation and apply to total=num/den
        ops[steps] = num == 0 || ns[steps] == 0 ? random.nextInt(2) : random.nextInt(4);
        if (ops[steps] == 0) {
            num -= den * ns[steps];
        } else if (ops[steps] == 1) {
            num += den * ns[steps];
        } else if (ops[steps] == 2) {
            den *= ns[steps];
            int g = gcd(num, den);
            if (g > 1) {
                num /= g;
                den /= g;
            }
        } else if (ops[steps] == 3) {
            num *= ns[steps];
            int g = gcd(num, den);
            if (g > 1) {
                num /= g;
                den /= g;
            }
        }

        // calculate score for path up to now and save it if best
        double score = steps + 1 + Math.abs(2011 - num / (double) den);
        if (score < bestScore) {
            bestScore = score;
            best = String.format("Start: (%d, %d)\n", starty, startx);
            int nn = 0;
            int dn = 1;
            for (int k = 0; k <= steps; k++) {
                if (ops[k] == 0) {
                    nn -= dn * ns[k];
                } else if (ops[k] == 1) {
                    nn += dn * ns[k];
                } else if (ops[k] == 2) {
                    dn *= ns[k];
                    int g = gcd(nn, dn);
                    if (g > 1) {
                        nn /= g;
                        dn /= g;
                    }
                } else if (ops[k] == 3) {
                    nn *= ns[k];
                    int g = gcd(nn, dn);
                    if (g > 1) {
                        nn /= g;
                        dn /= g;
                    }
                }
                best += String.format(dn == 1 ? "%c%d=%d\n" : "%c%d=%d/%d\n", "-+/*".charAt(ops[k]), ns[k], nn, dn);
            }
            best += String.format("Strokes: %d\n", steps + 1);
            best += dn == 1 ? String.format("Score: %d\n", (int) (score + 0.05)) : String.format("Score: %f\n", score);
            if (DEBUG) {
                System.out.println(best);
                printGrid(grid);
                System.out.println();
            }
        }

        if (steps + 2 < bestScore) {
            // choose any direction and go on
            int dir = random.nextInt(4);
            int nx = sx;
            int ny = sy;
            int b = 0;
            while (b < 4) {
                if (dir == 0 && sx > 0 && grid[sx - 1][sy] >= 0) {
                    nx = sx - 1;
                    break;
                } else if (dir == 1 && sx < grid.length - 1 && grid[sx + 1][sy] >= 0) {
                    nx = sx + 1;
                    break;
                } else if (dir == 2 && sy > 0 && grid[sx][sy - 1] >= 0) {
                    ny = sy - 1;
                    break;
                } else if (dir == 3 && sy < grid[0].length - 1 && grid[sx][sy + 1] >= 0) {
                    ny = sy + 1;
                    break;
                }
                b++;
                dir++;
            }

            // if further step possible
            if (b < 4) {
                doStep(num, den, steps + 1, nx, ny);
            }
        }

        // put back the digit
        grid[sx][sy] = ns[steps];
    }

    // helper function calculating gcd
    private static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    // helper function reading the grid from an array of strings
    private static void prepareGrid(String[] data, int numLines) {
        grid = new int[data[0].length()][numLines];
        for (int y = 0; y < numLines; y++) {
            for (int x = 0; x < data[y].length(); x++) {
                grid[x][y] = (int) (data[y].charAt(x) - '0');
            }
        }
    }

    // helper function printing the grid
    private static void printGrid(int[][] grid) {
        for (int y = 0; y < grid[0].length; y++) {
            for (int x = 0; x < grid.length; x++) {
                System.out.print(grid[x][y] < 0 ? '.' : (char) ('0' + grid[x][y]));
            }
            System.out.println();
        }
    }
}

Edit: Just did a small performance optimization. We don't need to follow a path anymore if it's length already exceeds the best score found so far.

Scala
object Main
{
    def main(args:Array[String])
    {
        var input=io.Source.stdin.getLines.toArray

        while(!input.isEmpty)
        {
            var hole=input.takeWhile(_!="").map(_.map(x=>Integer.parseInt(x.toString)).toArray).toArray
            input=input.dropWhile(_!="")
            if(!input.isEmpty)
                input=input.tail

            var (height,width)=(hole.size,hole.head.size)
            var bestscore=10000000
            var bestrunoutput=""
            var currentval=0
            var output=""
            var exit=false
            var c:Array[Array[Int]]=Array(Array(0))
            var(steps,xnow,ynow)=(0,0,0)

            def getNeighbours(x:Int,y:Int,c:Array[Array[Int]]):Array[(Int,Int,Int)]=
                (for(a<- -1 to 1;b<- -1 to 1;if(Math.abs(a)!=Math.abs(b) && x+b>=0 && x+b<width && y+a>=0 && y+a<height)) yield (c(y+a)(x+b),x+b,y+a)).toArray.sortBy(_._1).reverse

            for(y<-0 until height;x<-0 until width)
            {
                c=hole.map(_.clone)
                exit=false
                steps=0
                xnow=x
                ynow=y

                currentval=c(ynow)(xnow)
                output="Start: ("+y+","+x+")\n+"+currentval+"="+currentval+"\n"
                while(!exit)
                {
                    var neighbours=getNeighbours(xnow,ynow,c)
                    while(neighbours.size>0 && (neighbours.head._1*currentval>2011 || neighbours.head._1<2))
                        neighbours=neighbours.drop(1)
                    if(neighbours.size==0)
                    {
                        neighbours=getNeighbours(xnow,ynow,c)
                        while(neighbours.size>0 && (neighbours.head._1+currentval>2011 || neighbours.head._1==0))
                            neighbours=neighbours.drop(1)
                        if(neighbours.size==0)
                        {
                            exit=true
                        }
                        else
                        {
                            currentval+=neighbours.head._1
                            c(ynow)(xnow)=0
                            output+="+"+neighbours.head._1+"="+currentval+"\n"
                        }
                    }
                    else
                    {
                        currentval*=neighbours.head._1
                        c(ynow)(xnow)=0
                        output+="*"+neighbours.head._1+"="+currentval+"\n"
                    }
                    if(!exit)
                    {
                        xnow=neighbours.head._2
                        ynow=neighbours.head._3
                    }
                    steps+=1
                }
                output+="Strokes: "+steps+"\nScore: "+(steps+2011-currentval)+"\n"

                if(steps+2011-currentval<bestscore)
                {
                    bestscore=steps+2011-currentval
                    bestrunoutput=output
                }
            }

            println(bestrunoutput)
        }
        println
    }
}

I've tidied it up a little, fixed the bug that let the same number be used more than once for addition, and I've met the requirement (which I didn't spot before) to take multiple holes as input.
The algorithm is fairly simple:
For every possible start point:
    Find the highest value neighbour and try multiplying it
    If it's too high
        Try the next highest neighbour
        If there are no more neighbours
            Find the highest value neighbour and try adding it
            If it's too high
                Try the next highest neighbour
                If there are no more neighbours
                    End this attempt and calculate the score
Print out the attempt with the best score

Running in ideone.com:
Input
14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

9876
5432
1098
7654
3210

39857205
74493859
02175092
54239112
39209358
34568905

Output
Start: (0,3)
+3=3
*9=27
*4=108
*3=324
*6=1944
+5=1949
+9=1958
+9=1967
+4=1971
+8=1979
+8=1987
+9=1996
+7=2003
+6=2009
+2=2011
Strokes: 15
Score: 15

Start: (6,6)
+7=7
*5=35
*4=140
*7=980
+8=988
+9=997
+8=1005
*2=2010
+1=2011
Strokes: 9
Score: 9

Start: (4,0)
+3=3
*7=21
*6=126
*5=630
+9=639
*3=1917
+7=1924
+8=1932
+9=1941
+5=1946
+4=1950
Strokes: 11
Score: 72

Start: (4,5)
+3=3
*9=27
*8=216
*9=1944
+9=1953
+5=1958
+7=1965
+9=1974
+5=1979
+8=1987
+9=1996
+4=2000
+7=2007
+3=2010
Strokes: 14
Score: 15

Looks like mine'll have to be content being weekend golf player compared to Howard's Tiger Woods. :-)


text:
Unique Sudoku Finder
Challenge:
Given a Sudoku board on standard input, find the minimum number of numbers added to make the board unique.
Specifics/Rules:

The input is formatted as follows (all whitespace is significant)
516|827|943
278|394|615
349|615|872
---+---+---
98 |4 2|156
465|189|237
12 |5 6|489
---+---+---
892|743|561
634|951|728
751|268|394

The output is formatted with one number per line, formatted like (x,y):z - x and y start from one at the top left and increase down and right; z is the number to be added.

In this case these would all be valid outputs: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3, and (5,6):7, as any one of these would allow the board to be solved.

If a unique/solved Sudoku board is entered, the program should not print anything, even a newline.
The program should run in less than an hour for any board (I suggest testing using a fully blank board, or a board with one random number on it...).

Scoring:

Take your total (golfed) code size in characters, including all whitespace...

Bonuses:
1/2 code size:  If the program prints a single exclamation point and stops upon having a board with no solutions entered.
1/2 code size:  If the program prints two exclamation points and stops upon having a board with an internal contradiction entered (two numbers the same on the same row/column/square).

Boring and probably difficult :(

Boo. 'Not print anything, not even a newline' rules out GolfScript.

a sudoku solver that never needs to backtrack/guess for a full solution is needed for this, (and each time a "guess" is needed output it)

I don't see the reason to downvote this. Much effort was made to show a pretty puzzle; it is very clear, and properly stated. It's too big for my taste, but that's too subjective for a reason to downvote, isn't it?

Brachylog, 245 bytes /2 = 122.5
@n:1a:"-"x:7fF:3a$\:3a@3:4a,Fc~bCh[0:0:0]gO,Co~c[V:O:T]h:F:6f:10ao:ba(h:11a;!);"!!"w!
h"-".|:"|"x:2f.
e(~m["0123456789":.]`;0<.<=9)
:ha#d.
:@3az:ca:5a.
:3a.
hs.:=a,?t:9ac:=fl1
:Im:8f:[[I]]z:ca.
:Jm:J.
:ha.
lg:?c.
b:+a[X:Y],?h:Y:Xr:"(~d,~d):~d
"w

(Note that you have to use the version of the language as of this commit. This code would need some slight changes for it to work properly in the following versions of Brachylog)
This prints "!!" if the given board has internal contradictions (This takes a few seconds in that case however on TIO, so be patient).
I'm not sure I understand the first bonus correctly so I'm not addressing it.
This is obviously non-competing since the language is much more recent than the challenge, however since there are no other answers I'm not sure this matters a whole lot…
Explanation

Main predicate:
@n                Split the input on line breaks
:1a:"-"x          Transform into a list of lists, each sublist contains a line's values
:7fF              Transform so that cells are [Value:X:Y]
:3a               All values on lines must be different
$\:3a             All values on columns must be different (by transposition)
@3:4a,            All 3*3 block values must be different
Fc~bCh[0:0:0]gO,  Append a fake cell [0:0:0]
Co~c[V:O:T]       Sort the board, the blank cells V will be those before O ([0:0:0])
h:F:6f            Find all subsets of blank cells with specific values for which
                      the board has only one solution
:10ao             Sort the subsets by lengths
:ba               Discard the lengths
(
  h:11a             Print the first subset = an answer
;                 Or (board is already fully determined)
  !                 Terminate
)
;                 Or (Some values don't respect the constraints)
"!!"w!            Print "!!" and terminate

Predicate 1: Remove all "|" on lines, transform the ---+---+--- into - to remove them after
h"-".    If the first char is "-", then Output is "-"
|        Or
:"|"x    Remove all occurences of "|" from the input
:2f.     Output is the result of all outputs of predicate 2 on the filtered string

Predicate 2: Convert one char to an integer, or if blank to a variable between 1 and 9.
e                      Take a char of the input string
(
  ~m["0123456789":.]     Output is the index of the char in "0123456789"
  `                      Discard the choice point caused by the ;
;                      Or
  0<.<=9                 Output is an integer between 1 and 9
)

Predicate 3: Impose that all values of the input list of cells must be distinct
:ha    Retrieve the head of each cell (i.e. the value) in the input
#d.    Apply a constraint of distinctness to those values

Predicate 4: Apply the distinctness constraint to values in 3*3 blocks
:@3a            Split 3 lines of the board in 3 parts
    z           Zip them together
     :ca:5a.    Concatenate each element of the zip, apply predicate 5 to that

Predicate 5:
:3a.    Apply predicate 3 to each element of the input

Predicate 6: Assign values satisfying the constraints to a subset of the blank cells, then with those values there is only one solution to the board.
hs.       Output is a subset of the blank cells
:=a,      Assign values to those cells
?t:9ac    Concatenate the values of all cells of the board
:=f       Find all solved boards
l1        There is only 1 such solved board

Predicate 7: Transforms the board such that each cell is now [V:X:Y] instead of only V (the value).
:Im       Take the Ith line of the board
:8f       Transform all elements of the line using predicate 8
:[[I]]z   Zip the result with [I]
:ca.      Concatenate each element of the zip

Predicate 8: Transforms a line such that each cell is now [V:X].
:Jm    Take the Jth element of the line
:J.    Output is [That element:J]

Predicate 9: Retrieve the values of cells
:ha.   Take the head of each element of the input

Predicate 10: Append the length of a subset at the beginning of it
lg     Put the length of the input in a list
:?c.   Concatenate it with the input

Predicate 11: Print one cell
b:+a[X:Y],        Increment coordinates by 1 to get X and Y
?h:Y:Xr:          Build the list [X:Y:Value]
"(~d,~d):~d\n"w   Format that list as "('X','Y'):'Value'\n" to STDOUT

Can’t you just expand this into a Prolog answer? Then it’d be competing! (You could post it separately.) I’m not sure how direct the mapping between Brachylog and Prolog is.

@Lynn Yes I could, I could even just post the Prolog code that gets generated by Brachylog's transpiler (which would be highly ungolfed obviously). I won't do it though because I'm pretty sure the challenge's poster will never come back to accept an answer anyway :p


text:
A Mere Bagatelle
The challenge
Given a bagatelle board like the one below:
|                    |
|    /\            / |
|      \            /|
|  \      \ /\    \  |
|   \   /       \    |
|\     /   /  \      |
|   \            / \ |
|    \               |
|  \    / \ /\    \  |
|\     /   /  \     /|
|                /   |
|    /\         /  / |
|              /     |
|\     /   /  /      |
|                    |
----------------------

your task is to turn a list of 'throws' into a score.
The board will always be 20 characters (plus 2 edges) wide, but of variable height. Each 'throw' is a number representing where the ball falls into the board, starting at 0 for the far left up to 19 for the far right. Each ball will fall straight down unless it encounters a / or a \. Encountering a / shifts the ball one column to the left, and a \ shifts the ball one column to the right. After being shifted, the ball continues straight down as before. The score for a throw is dependant on where the ball hits the bottom of the board.
The scores for each finishing position are as follows:
|                    |
----------------------
 01234567899876543210

and are the same for all boards. The first and last rows will always be empty. The ball is guaranteed to reach the bottom regardless of where it is dropped from, so there will be no boards where it can get trapped by \/,\| or |/ combinations.
Input
Input will be on STDIN, and will consist of the board followed by a blank line followed by a space separated list of numbers representing the throws.
Output
Ouput should be the total score for the given game.
A couple of examples
Input
|                    |
| \                  |
|  \                 |
|   \                |
|    \               |
|     \              |
|      \             |
|       \            |
|        \           |
|         \          |
|          \         |
|           \        |
|            \       |
|             \      |
|              \     |
|               \    |
|                \   |
|                 \  |
|                    |
|                    |
----------------------

1 4 2 19 0 2 4 3 17 13 16

Output
9

Input
|                    |
| \                / |
|  \              /  |
|   \            /   |
|    \          /    |
|     \        /     |
|      \      /      |
|       \    /       |
|        \  /        |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
----------------------

15 10 3 8 18 19 0 6 7 10

Output
72

Input
|                    |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
|                    |
----------------------

1 4 18 17 14 2 0 19 15

Output
18

Test scripts
I've used some test scripts written by Joey and Ventero (I hope they don't mind...) to create some tests for this task:-

Bash
PowerShell

Usage: ./test [your program and its arguments]
This is codegolf - shortest solution wins.

You could have my generating script for them as well :-). I eventually wanted to make that public but as long as it still needs tweaking for many tasks I didn't want to do that.

@Joey A generating script would be a useful tool to have available.

Both sets of test should be fixed now.

GolfScript, 60 59 chars
n/{},)\);{1>:x,,{.x=31%4%(+}%}%[10,.-1%+]+0@[~]{2${=}/+}/\;

I was so tempted to write a solution which works by redefining the symbols /, \, and space, but it's actually quite expensive (especially once you can no longer use the original \).
31%4%( is nicked from Keith Randall's solution and maps the ASCII codes for space, /, and \ to 0, -1, 1 respectively. (See edit history).

Surprisingly long for GolfScript. :-) How did you get it to work with the test script though? All I got was errors when I tried ./test ruby golfscript.rb peter.gs? I threw some tests at it as piped input instead.

./test-bagatelle.sh \which golfscript.rb` bagatelle2.gs`

Python 2, 147 132 130 chars

import sys
s=0
l=list(sys.stdin)
for t in l[-1].split():
 p=int(t)+1
 for r in l[:-3]:p-=" /".find(r[p])
 s+=min(p-1,20-p)
print s

Did you run it against the test script? ;-)

No, just against the examples in the question. I'll try the test script. [...] I see that it gives wrong results now. It used to work earlier, I'll search for that bug.

Ohh, it's because i thought it to be clever to use a triangle wave instead of the range and reversal I used earlier (and Keith still uses). This doesn't work because I need the 9 twice, though. Hmm - I'll see whether I can find a trick around that, my triangle wave is a mess anyway (can't even remember why there are brackets around the twenty, and the first ten is meant to be a nine).

Okay, fixed now. Next time I test my stuff a little more ;)

No problem, I often manage to break my answers with excessive shrinking.

Maybe s+=min(p,19-p)?

for r in l[:-3]:p-=" /".find(r[p]) should save a few chars

Thank you two. Especially gnibbler's trick is truly awesome - but it cannot hurt to know a shorter tri function, too ;)

@gnibbler That's a genius trick.

19-p+1 == 20-p

Python, 165 159 chars
import sys
A=list(sys.stdin)
C=range(10)
C+=C[::-1]
for L in A[-4::-1]:C=[C[i+ord(L[i+1])%31%4-1]for i in range(20)]
print sum(C[int(x)]for x in A[-1].split())

It starts with a row of scores and works its way from the bottom up, computing what the scores would be for balls starting at each row.

list(sys.stdin) instead of readlines()

Ruby, 123 117 115 107 99 98 97
*b,_,_,n=*$<
p eval n.split.map{|k|i=k.to_i+1
b.map{|l|i-='\ /'.index(l[i])-1}
[i-1,20-i].min}*?+

Why use rescue? Can't you chop off two lines from b in the initial assignment?

@migimaru: Indeed. But I have to chop off three lines, not two.

Right. I meant two more lines. Sorry.

you can use i-='\ /'... instead to save one more char


text:
Regex validating regex
Build a regex that will accept a regex string as input and check if it's valid. Basically, your regex should be able to validate itself. (Any invalid regex should not be validated, so you can't use .*. ;))
Your flavor must be fully supported by well known implementations (Perl, sed, grep, gawk, etc), and it must fully support what those implementations support. [Don't worry about the lawyer speak; I'm just trying to remove any possible loopholes for the smart***es.]

I'd code-golf it, but I'm worried it'll give an edge to those who know and use non-feature-rich flavors. Or are my worries unfounded?

not possible, the arbitrary nesting brackets make a regex a context free grammar, (replacing it with a polish notation also needs a stack)

@ratchet Augh, you might be right.

some extensions on the regular languages exist that may allow matching the brackets but I don't know how to do it

It's bound to be possible with Perl regexes.

@ratchet freak is correct; regular expressions are a context-free grammar, so a regular expression cannot accurately capture context-sensitive features of the language -- eg, balancing arbitrarily nested parentheses, etc.

@BrianVandenberg regular expressions implemented in modern languages are pretty much all non-regular ... as soon as you add backreferences, you can match non-regular languages. Moreover, both Perl/PCRE and .NET are powerful enough to match correct nesting.

I've voted to close this question as it has no winning criteria, making it impossible to objectively identify a winner, and thus off-topic.

Ruby
I tried to match the actual syntax of Ruby's regex flavor as much as possible, but there are a few quirks: it accepts a few lookbehinds that are actually invalid (like (?<=(?<!))), and it recognizes empty character ranges like D-A. The latter could be fixed for ASCII, but the regex is long enough as it is.
\A(?<main>
    (?!
        \{(\d+)?,(\d+)?\} # do not match lone counted repetition
    )
    (?:
        [^()\[\]\\*+?|<'] | # anything but metacharacters
        (?<cclass>
            \[ \^? (?: # character class
                (?: # character class
                    [^\[\]\\-] | # anything but square brackets,  backslashes or dashes
                    \g<esc> |
                    \[ : \^? (?: # POSIX char-class
                        alnum | alpha | word | blank | cntrl | x?digit | graph | lower | print | punct | space | upper
                    ) : \] |
                    - (?!
                        \\[dwhsDWHS]
                    ) # range / dash not succeeded by a character class
                )+ |
                \g<cclass> # more than one bracket as delimiter
            ) \]
        ) |
        (?<esc>
            \\[^cuxkg] | # any escaped character
            \\x \h\h? | # hex escape
            \\u \h{4} | # Unicode escape
            \\c . # control escape
        ) |
        \\[kg] (?:
            < \w[^>]* (?: > | \Z) |
            ' \w[^']* (?: ' | \Z)
        )? | # named backrefs
        (?<! (?<! \\) \\[kg]) [<'] | # don't match < or ' if preceded by \k or \g
        \| (?! \g<rep> ) | # alternation
        \( (?: # group
            (?:
                \?
                (?:
                    [>:=!] | # atomic / non-capturing / lookahead
                    (?<namedg>
                        < [_a-zA-Z][^>]* > |
                        ' [_a-zA-Z][^']* ' # named group
                    ) |
                    [xmi-]+: # regex options
                )
            )?
            \g<main>*
        ) \) |
        \(\?<[!=] (?<lbpat>
            (?! \{(\d+)?,(\d+)?\} )
            [^()\[\]\\*+?] |
            \g<esc>  (?<! \\[zZ]) |
            \g<cclass> |
            \( (?: # group
                (?:
                    \?: |
                    \? \g<namedg> |
                    \? <[!=]
                )?
                \g<lbpat>*
            ) \) |
            \(\?\# [^)]* \)
        )* \)
        |
        \(\? [xmi-]+ \) # option group
        (?! \g<rep> )
        |
        \(\?\# [^)]*+ \) # comment
        (?! \g<rep> )
    )+
    (?<rep>
        (?:
            [*+?] | # repetition
            \{(\d+)?,(\d+)?\} # counted repetition
        )
        [+?]? # with a possessive/lazy modifier
    )?
)*\Z

Unreadable version:
\A(?<main>(?!\{(\d+)?,(\d+)?\})(?:[^()\[\]\\*+?|<']|(?<cclass>\[\^?(?:(?:[^\[\]\\-]|\g<esc>|\[:\^?(?:alnum|alpha|word|blank|cntrl|x?digit|graph|lower|print|punct|space|upper):\]|-(?!\\[dwhsDWHS]))+|\g<cclass>)\])|(?<esc>\\[^cuxkg]|\\x\h\h?|\\u\h{4}|\\c.)|\\[kg](?:<\w[^>]*(?:>|\Z)|'\w[^']*(?:'|\Z))?|(?<!(?<!\\)\\[kg])[<']|\|(?!\g<rep>)|\((?:(?:\?(?:[>:=!]|(?<namedg><[_a-zA-Z][^>]*>|'[_a-zA-Z][^']*')|[xmi-]+:))?\g<main>*)\)|\(\?<[!=](?<lbpat>(?!\{(\d+)?,(\d+)?\})[^()\[\]\\*+?]|\g<esc>(?<!\\[zZ])|\g<cclass>|\((?:(?:\?:|\?\g<namedg>|\?<[!=])?\g<lbpat>*)\)|\(\?#[^)]*\))*\)|\(\?[xmi-]+\)(?!\g<rep>)|\(\?#[^)]*+\)(?!\g<rep>))+(?<rep>(?:[*+?]|\{(\d+)?,(\d+)?\})[+?]?)?)*\Z

Aren't they both the unreadable version?

@Kibbee The first one is reasonably readable if you know regex well.

How does this ensure that there are no invalid numeric backreferences?

I guess it doesn't. Then again, it's not the only limitation it has (see above). Some things could be fixed, but the regex would become ridiculously long.


text:
Optimal Othello/Reversi Move
This is a code-golf challenge: Given a specific board in the game of Othello (Reversi), find a move for Black that will capture the maximum number of White pieces.
(Obviously, this may not be the true "optimal" play for Black, but to keep things simple we are only interested in finding the move that will capture the most pieces.)
If you are unfamiliar with the rules of Othello (Reversi), you may refer to: http://en.wikipedia.org/wiki/Reversi

Input will be provided as a file, or through stdin (your choice).
You may assume that the board will be a standard 8x8 size.
Black pieces will be indicated by b and White pieces will be indicated by w. Empty spaces will be indicated by .
The input may not necessarily be a valid board reachable by the rules of the game. Regardless, you must still find the optimal move following the rules of the game.
Your program must output the move by Black that will capture the most White pieces. If there is a tie, you may choose to output any (or all) of the moves. If there is no valid move, your program must indicate so by outputting x.
Your output can be provided as a coordinate, such as (3,4), or in algebraic notation, such as b5. When submitting your answer, please clearly indicate your output format and specify where your coordinate system starts from.

Sample input:
........
..b.....
...b....
...wwww.
...wb...
........
........
........

Sample output in (row,col) format, with (0,0) in the top-left corner:
(5,3)

Sample input:
........
......w.
.wwwwww.
.wwwwww.
.wwwwww.
.wwwwww.
.b....b.
........

Sample output in algebraic notation, with a1 in the bottom-left corner:
b7

Sample input:
........
........
..bbbb..
..bwwb..
..bwwb..
..bbbb..
........
........

Sample output:
x

This is code golf, so the shortest solution will be accepted.

Python, 184 chars
import os,re
M=os.read(0,99)
s=0
t='x'
for p in range(72):
 c=sum(len(re.match(r'\.w+b|',M[p::d]).group()[2:])for d in(-10,-9,-8,-1,1,8,9,10))
 if c>s:s=c;t='(%d,%d)'%(p/9,p%9)
print t

Coordinates are given as (y,x) with (0,0) in the upper left.
$ ./othello.py < othello1
(5,3)
$ ./othello.py < othello2
(1,1)
$ ./othello.py < othello3
x