text:
Find all unambiguous prefixes of a set of strings
For this challenge, you must implement Ruby's Abbrev module in as little code as possible.
Challenge

The input will be whatever your language has as an array (array, list, sequence, etc.) of strings. You may write a function, or you may accept comma-separated words on STDIN.
You must then calculate the set of unambiguous prefixes for those strings. This means you must return a hash (or map, object, etc.) of abbreviations to their original strings.

A "prefix" is a substring of the original string starting at the beginning of the string. For example, "pref" is an prefix of the word "prefix."
An unambiguous prefix is one that can only mean one word. For example, if your input is car,cat, then ca is not an unambiguous prefix because it could mean either "car" or "cat."
The exception to this rule is that a word is always a prefix of itself. For example, if you have input such as car,carpet, car:car must be in your output.

You can then return the hash/map/object/etc. from your function (or do the equivalent in your language), or print it out to STDOUT in key:value pairs in the form of f:foo,fo:foo,.... (The key-value pairs may also be separated by whitespace if it makes your code shorter.)

Test cases
Input  code,golf,going
Output c:code,co:code,cod:code,code:code,gol:golf,golf:golf,goi:going,goin:going,going:going

Input  pie
Output p:pie,pi:pie,pie:pie

Input  pie,pier,pierre
Output pie:pie,pier:pier,pierr:pierre,pierre:pierre

Input  a,dog
Output a:a,d:dog,do:dog,dog:dog

Rules

The input will not contain duplicate elements.
Your output may be in any order; you don't have to sort it.
You may not use a built-in Abbrev module/function/thing like Ruby's.
This is code-golf, so the shortest code in bytes will win!

Does stdout have to be exactly that format? Or can I do key:value\nkey:value\nkey:value... ?

Rather than redefining the word abbreviation you could just use prefix with its standard meaning. And I think unambiguous conveys the desired property of the keys more effectively than unique, for which my first intuition was that you wanted only one prefix per input word.

@PeterTaylor Good idea; edited.

May one print the same key multiple times (with the same value)?

APL (46)
(Yes, the APL charset does fit in a byte, with room to spare.)
{↑{∆/⍨2=⍴∆←(⊂⍵),∆/⍨⊃¨⍵∘⍷¨∆}¨∪⊃,/{↑∘⍵¨⍳⍴⍵}¨∆←⍵}

This is a function that takes a list of strings, and returns a 2-by-N matrix, where each row contains an unambigous prefix and the word it belongs to:
{↑{∆/⍨2=⍴∆←(⊂⍵),∆/⍨⊃¨⍵∘⍷¨∆}¨∪⊃,/{↑∘⍵¨⍳⍴⍵}¨∆←⍵}'code' 'golf' 'going'
 c      code
 co     code
 cod    code
 code   code
 gol    golf
 golf   golf
 goi    going
 goin   going
 going  going

Explanation:

∆←⍵: store the right argument in ∆.
{↑∘⍵¨⍳⍴⍵}¨∆: for each element of ∆, get the possible prefixes of that element:

⍳⍴⍵: get a list from 1 to the length of ⍵
↑∘⍵¨: for each of those numbers, get that many elements from ⍵.

∪⊃,/: concatenate the lists together and take the unique values.
{...}¨: for each of the unique prefixes:

∆/⍨⊃¨⍵∘⍷¨∆: select the words that start with that prefix
(⊂⍵),: also enclose the prefix, and concatenate
∆/⍨2=⍴∆←: only return the list if there are two elements (the prefix and one matching word)

↑: turn the list of tuples into a matrix

The link is broken now...

Python 2.7 - 146 141 bytes
l=raw_input().split(',')
for w in l:
 for a in range(len(w)):
    e=w[:a+1]
    if e==w or len(filter(lambda b:b.startswith(e),l))==1:print e+':'+w

Note that the indentation on lines 4 and 5 is not 4 spaces, that's a side effect of SE's markdown interpreter. That's a literal tab character, so only one byte.
This is not technically up to spec, but I'll change it if Doorknob clarifies. It uses newlines instead of commas to separate the output. For example:
$ python2 abbreviations.py <<< code,golf,golfing
c:code
co:code
cod:code
code:code
golf:golf
golfi:golfing
golfin:golfing
golfing:golfing

New: I was able to get rid of 5 characters by assigning the string that I'm checking to a variable e. This means that I only have to type e instead of w[:a] three times. It also means I save characters by doing e=w[:a+1] and changing ...range(1,len(w)+1) to range(len(w)).

Explanation:
l=raw_input().split(',') # Gets a line of input from stdin and splits it at every ',' to make a list
for w in l: # For each word in that list...

 for a in range(1,len(w)+1): # For each number a from 1 to the length of that word...

    if (w[:a]==w # w[:a] gets the string w up to the ath index. For example, 'aeiou'[:3] == 'aei'.
                 # We're testing every possible w[:a] to see if it's a unique abbreviation.
                 # However, a word is always its own abbreviation, so we hardcode that in by testing
                 # if w[:a] is the same as w.

or len(filter( # filter takes a function and an iterable as an argument, and returns a list of every
               # element of that iterable where that_function(that_element) returns a True-y value

lambda b:b.startswith(w[:a]),l) # We define an anonymous function that returns True for any string
                                # that begins with our current w[:a]. We filter for words that return
                                # True.

)==1): # If exactly one word returns True for this, it's a unique abbreviation!

     print w[:a]+':'+w # Print the abbreviation, a colon, and the full word.

You could use sum(b.startswith(e) for b in l) instead of len(filter(lambda b:b.startswith(e),l))

You can also shorten b.startswith(e) to b.find(e)==0 or b[:a+1]==e, and check <2 on the count instead of ==1.

Also do e=""\n for a in w:\n\te+=a instead of for a in range(len(w)):\n\te=w[:a+1] as it saves 10 chars

I've made an ungolphed version here for anyone that needs it  https://gist.github.com/stuaxo/c371b2d410191a575b763b74719856c8

J - 47 char
(,.~~.@,~[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>)

J sees strings as just vectors of characters, which means that when it tries to make a list of strings it actually ends up making a table of characters, so the ends get padded with spaces. J's solution to this is called the box, so this function takes as argument a boxed list of strings, so as to preserve length.
   'code';'golf';'going'
+----+----+-----+
|code|golf|going|
+----+----+-----+

Also, J lacks a hash type, so the closest it has to that is a two-column table of items, say boxed strings, for instance. If that is unacceptable and I have to default to the key-value form, I can reformat the output to this form in 67 characters total:
;@|.@,@((<&>',:'),."1,.~~.@,[:(#~1-1({.\e."_1]\.){:"1)@;(<,.<\)&.>)

Explanation by explosion:
(,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) NB. unambiguous prefixes
                                    (     )&.>  NB. for each string:
                                     <\         NB.   take all prefixes
                                       ,.<      NB.   pair each with string
        [:                         ;            NB. gather up "partial" hashes
          (#~1-                  )@             NB. remove those rows where:
               1({.\        ){."1               NB.   each key
                    e."_1                       NB.   is an element of
               1(        ]\.){."1               NB.   the rest of the keys
 ,.~                                            NB. hash each word to itself
       ,                                        NB. add these rows to hash
    ~.@                                         NB. remove duplicate rows

Examples:
   (,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) 'pie';'pier';'pierre'
+------+------+
|pie   |pie   |
+------+------+
|pier  |pier  |
+------+------+
|pierre|pierre|
+------+------+
|pierr |pierre|
+------+------+
   NB. 1-char words have to be made into lists with ,
   (,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) (,'a');'dog'
+---+---+
|a  |a  |
+---+---+
|dog|dog|
+---+---+
|d  |dog|
+---+---+
|do |dog|
+---+---+
   NB. "key:value," format, reversed order to save chars
   ;@|.@,@((<&>',:'),."1,.~~.@,[:(#~1-1({.\e."_1]\.){:"1)@;(<,.<\)&.>) 'code';'golf';'going'
goin:going,goi:going,gol:golf,cod:code,co:code,c:code,going:going,golf:golf,code:code,

Haskell 96 87
import Data.List
i=inits
f a=a>>= \x->[(y,x)|y<-i x,y/="",y`notElem`(a>>=i)\\i x||y==x]

Ungolfed version:
 import Data.List
 f a = concatMap (\x ->
     [(y, x) |
      y <- inits x,
      y /= "",
      y `notElem` concatMap inits a \\ inits x || y == x]
     ) a

Example:
> f ["pi","pier","pierre"]
[("pi","pi"),("pier","pier"),("pierr","pierre"),("pierre","pierre")]

I used the inits function, which finds all prefixes of a list/string. Does it count as cheating?

You can replace concatMap by (=<<), which is in the Prelude. Saves you 10 characters.

@Rhymoid Thank you. I removed concatMap but I can't save more than 9 characters.

Oh wait, you're right; Haskell considers >>=\  as a single lexeme. Sorry about that...

Python 3 (97)
c=','
S=c+input()
for w in S.split(c):
 e=w
 while e:e<w<w*S.count(c+e)or print(e+':'+w);e=e[:-1]

We iterate over prefixes of each word in the input, printing the corresponding prefix/word pair if it either appears exactly once or is to whole word. We take advantage of the short-circuiting behavior of or (and print being a function) to print only if one of these conditions is met.
The while loop repeatedly cuts off the last character to create shorter and shorter prefixes, terminating when the empty string remains. This is the only time we index or slice into anything.
We count the occurrences of the prefix e in the input by searching the original comma-separated input string S for substrings ','+e. We prepend a comma to the input string beaforehand. This addition causes an extra empty string element when we split, but this has no effect because it has no nonempty substrings.
To check for the case when the substring e is the whole word w, we compare them using the string comparison operator. This compares lexicographically, so shorter prefixes are smaller. The double comparison fails if either e==w or S.count(c+e)<2.
If printing outputs in the form e,w were allowed, I'd save a character by writing e+c+w instead.
Credit to undergroundmonorail from whose answer  I based my overall code structure.

(e<w)*S.count(c+e)>1 can be golfed to e<w<w*S.count(c+e) to save 2 characters.

@isaacg Thanks! I've added your optimization.

Perl, 93 77
With newlines and indentation for readability:
sub f{
    (map{
        $h{$x}=[($x=$`.$&,$_)x!$h{$x}]while/./g;
        $_,$_
    }@_),map@$_,values%h
}

A bit too late and too long, but I'm glad it's finally got below 100. Function returns a list which can be assigned to hash variable:
%h = f(qw/code golf going pie pier pierre/);
print "$_ $h{$_}\n" for sort keys %h;

and
perl prefix.pl
c code
co code
cod code
code code
goi going
goin going
going going
gol golf
golf golf
pie pie
pier pier
pierr pierre
pierre pierre

Actually, returned list is not filtered yet - hash construction is completed at the moment of its assignment i.e. outside function. IF it's not clean/fair enough, add 3 to count and put function contents into curly braces, prepending + - then function returns 'true' hash reference.

Ruby, 114
def f(l);h={};l.each{|w|w.size.times{|i|k=w[0..i];h[k]=h[k]&&0||w}};h.delete_if{|k,v|v==0};l.each{|w|h[w]=w};h end

Ungolfed:
def f(list)
  hash = {}
  list.each do |word|
    word.size.times do |i|
      key = word[0..i]
      h[key] = (hash[key] && 0) || word
    end
  end
  hash.delete_if{|key, value| v==0}
  list.each{|word| hash[word] = word}
  hash
end

k4 (70)
not particularly golfed; i'm sure it could be shorter
pretty similar to the J impl. above, i think -- basically just collects all the (proper) prefixes, removes the words from the prefixes again (to handle the "car"/"carpet" case), groups them into equivalence classes, picks the classes with only one element, reduces them from lists to strings, and adds in the map from strings to themselves.
f:{(x!x),*:'{(&1=#:'x)#x}{x@=y@:&~y in x}.,/'+{1_'(c#,x;(!c:#x)#\:x)}'x}

some test cases
note that in k/q, a string is list of characters, so a string containing only a single character needs to be marked as such using the unary , function; & m.m. w.r.t a list of strings containing only a single string
these use q's show function, which has built-in formatting for some data structures, to make the results more readable:
  .q.show f("code";"golf";"going")
"code" | "code"
"golf" | "golf"
"going"| "going"
,"c"   | "code"
"co"   | "code"
"cod"  | "code"
"gol"  | "golf"
"goi"  | "going"
"goin" | "going"
  .q.show f@,"pie"
"pie"| "pie"
,"p" | "pie"
"pi" | "pie"
  .q.show f("pie";"pier";"pierre")
"pie"   | "pie"
"pier"  | "pier"
"pierre"| "pierre"
"pierr" | "pierre"
  .q.show f(,"a";"dog")
,"a" | ,"a"
"dog"| "dog"
,"d" | "dog"
"do" | "dog"
  .q.show f("car";"carpet")
"car"   | "car"
"carpet"| "carpet"
"carp"  | "carpet"
"carpe" | "carpet"

JavaScript - 212
w=prompt(o=[]).split(",");w.map(function(k,l){for(i=0;++i<k.length;){p=k.slice(0,i);if(w.filter(function(r,t){return t!=l}).every(function(r){return r.indexOf(p)}))o.push(p+":"+k)}o.push(k+":"+k)});console.log(o)

Initial golf.
Input:
code,golf,going
Output:
["c:code", "co:code", "cod:code", "code:code", "gol:golf", "golf:golf", "goi:going", "goin:going", "going:going"]

Q: 44 Bytes
{x!p@'(?0,&:)'p in\:&1=#:'=,/p:`$(-1_)\'$x}

NOTES

Q language has an inner core named internally K4 (used in this answer and another previously answer to this question)
To test code, download interpreter (kx.com, free for non-commertial
use, support for Windows, Linux, Mac)

Interpreter admits two syntaxes:

verbose (more readable names, distinct names for moands and diads, more libraries, ...). Load source file with q extension, or interactive interpreter
compact (functional inner core, one letter operators, same letter for both uses monad/diad, ...). Load source file with k extension, or interactive interpreter in k mode (write \ at prompt). Code must be tested in this mode

The code defines a lambda (anonymous function). To give name to the function we need prefix name: (ex f:{..}), so requires 46 Bytes
TEST
(assumming named function: otherwise substitute f for the code)
f `code`golf`going

`code`golf`going!(`code`cod`co`c;`golf`gol;`going`goin`goi)

returns a dictionary (syntax keys!values). Keys are a list of symbols (`symb`symb..), and values a list of list of symbols. If we execute the sentente at the interactive interpreter, we have a more convenient presentation (each key and associate values at a different line)
code | `code`cod`co`c
golf | `golf`gol
going| `going`goin`goi

EXPLANATION
x is the implicit argument to the lambda
$x convert symbol list to string list
(-1_)\   iterates over each elem of the symbol list
(reads as for each string calculates prefixes (at eat iteration drops last char  of the string (-1_), until empty string)
$       transforms to a symbol list again (list of all prefixes)
p:       and assigns to p
,/       raze all (concatenates and creates a one-level structure)
=        classify -> for each unique prefix, associates the corresponding words
#:'      calculates length (number of words associated to each prefix)
1=       true if length=1 (unambiguous), false otherwise
&        where -> index of true elements
p in\:   determines for all prefix if they are in unambiguous prefix
(..)' applies (..) to each value at right (unambiguous prefix)
?0,&:  -> distinct 0 concatenated where (to cope words as prefix of itself)
p@       transform indexes to symbols
x!..     construct a dictionary with x (words) as keys, and .. as values
Read as:

Construct and returns a dictionary with the words as keys, and values
..
... values of indexes at distinct positions 0 (all word) and where
unambiguous prefix
... unambiguous calculated as prefixes that appear only at one word
(wordlist associates to each symbols has length one)
... lists resulting of classifying all unique symbols with corresponding
words
... prefixes calculated by repeating drop last char of each word

PHP 7.0, 67 bytes (postdates the challenge)
for(;a&$c=$s[++$k]??($s=$argv[++$i])[$k=+$t=!1];)echo$t.=$c,":$s,";

takes input from command line arguments; prints a trailing comma; run with -nr.
for newer PHP, add one byte: Replace &a with ""<.
for older PHP, use these 70 bytes:
PHP, 70 bytes
for(;a&$s=$argv[++$i];)for($k=+$t="";a&$c=$s[$k++];)echo$t.=$c,":$s,";

Brachylog, 23 bytes
∋Xa₀Y;?↔⟨∋a₀⟩ᶜ1∧Y;X|∋gj

Try it online!
Takes input as a list through the input variable, and generates a list of [key, value] pairs through the output variable. Any input string which is not a prefix of another input string will be generated as a prefix of itself twice, although the header on TIO hides this by using ᵘ to obtain the full list instead of ᶠ.
 X                         X
∋                          is an element of
                           the input variable
    Y                      and Y
  a₀                       is a prefix of
 X                         X.
             ᶜ             The number of ways in which
        ⟨∋  ⟩              an element can be selected from
     ;?↔⟨   ⟩              the input variable
    Y; ↔⟨ a₀⟩              such that it has Y as a prefix
              1            is equal to 1.
               ∧Y          Y is not necessarily 1,
                   |       and the output variable
                Y;X        is the list [Y, X].
                   |       If every choice from the first rule has been taken already,
                           the output variable is
                    ∋      an element of
                   |       the input variable
                     gj    paired with itself.

If duplicates in the output are not tolerated, add three bytes to wrap the whole thing in {}ᵘ, unless there's some shorter way to either exclude something form being a prefix of itself, or generate every necessary output pair without the extra rule ∋gj.

APL (Dyalog Classic), 38 bytes
thanks Erik the Outgolfer for reminding me to use a single-byte character encoding
{⊃,/⍵{b,¨⍨(⊂¨⍵~⊃,/a~⊂⍵)∪b←⊂⊂⍺}¨a←,\¨⍵}

Try it online!

Um... I don't see any one of the bad characters that you can't use with Adám's SBCS here... :P

without noticing, i've picked the wrong interpreter version again... thanks for halving my byte count :)

Perl 5 -a, 76 bytes
map{say"$, $a"if($,=substr$a,0,$_)eq$a||2>grep/^$,/,@F}1..length($a=$_)for@F

Try it online!

Groovy - 212 chars
Golfed:
c="collectEntries";f="findAll";def g={def h=[:].withDefault{[]};it.each{def w->w.size().times{ h[w[0..it]] << w}};(h."$f"{k,v->v.size()==1}."$c"{k,v->[k,v[0]]}).plus(h."$f"{k,v->v.contains(k)}."$c"{k,v->[k,k]})}

example output:
println g(["code","golf","going"])

[c:code, co:code, cod:code, code:code, gol:golf, golf:golf, goi:going, goin:going, going:going]

Ungolfed:
def g = { def list ->
    def hash = [:].withDefault{[]}
    list.each {
        def word -> word.size().times{ hash[word[0..it]] << word }
    }

    def map = hash.findAll{ k,v -> v.size() == 1 }.collectEntries{ k,v -> [k,v[0]] }
    map.plus(hash.findAll{ k,v -> v.contains(k) }.collectEntries{ k,v -> [k,k] }
    map
}

Python (127)
So I couldn't comment @undergroundmonorail, but I thought that taking a dictionary approach would be better? I'm sure with some list/dictionary comprehension it could be cut down tremendously too, but can't get it to work with popping from the dict.
i=raw_input().split(",")
d = {}
for x in i:
    for c in range(1,len(x)+1):
        if x[:c] in d:
            del d[x[:c]]
        else:
            d[x[:c]]=x
print d

The print will output the dictionary, unordered.
EDIT: Ahh I missed the car:car / car:carpet criteria. Maybe a length check?

Maybe I'm missing something, but this seems to alternately add and delete the prefix entry each time it is encountered, so wouldn't an ambiguous prefix appear if it occurs in 3 words?

JavaScript (Node.js), 88 bytes
L=>L.map(s=>[...s].map(c=>L.filter(t=>t>S&t<S+'~',S+=c)[1]&&s>S||(R[S]=s),S=''),R={})&&R

Try it online!

Zsh, 95 bytes
local -A m
for w;{m[$w]=$w;x=
for c (${(s::)w})x+=$c&&[ ${(M)@:#$x*} = $w ]&&m[$x]=$w
}
local m

Try it online!
The only way to "return" an associative array in Bash/Zsh is by declaring it without the local keyword and then accessing it in the parent scope. This would save one byte. However, I/O via variables is generally frowned upon, so we print the array definition instead.
local -A m                          # declare m as associative
                                    # "local" is shorter than "typeset"/"declare"
for w;{                             # for each word
    m[$w]=$w                        # the word is a prefix of itself
    x=                              # ensure x is empty
    for c (${(s::)w})               # for each character in the word
        x+=$c &&                    # append to x (building a prefix
          [ ${(M)@:#$x*} = $w ] &&  # if the only match is the word itself:
          m[$x]=$w                  # ... then x is a prefix of w
}
local m                             # print m

Ruby, 84 bytes
Just noticed there's already an existing Ruby solution, oh well. This basically improves on the old solution by picking prefixes in a smarter way (eliminating the need to add each word as a "prefix" at the end) and counting prefixes to check uniqueness before adding them to the hash, instead of overwriting the value with a dummy if there is a duplicate and then erasing the entry.
->w{h={};w.map{|e|(1..e.size).map{|i|w.count{|d|d[0,i]==e[0,i]}<2?h[e[0,i]]=e:0}};h}

Try it online!


text:
Write a program that can that can write a program, in the shortest code possible!
As stated, write a program that is capable to, in an automated manner, write more code and another program and execute that program from itself.
In short, you are asked to write a program that can write another self-standing program itself and enable it to execute in any function.
Do this in the shortest amount of code possible, with the one restriction being that it has to be written in one of these languages.
If you need even more specific details, read on:

You are asked to write a program that will (in an automated manner)
  write the lines of code needed for another program, and compile that
  program/execute it from the programmatic structure of the main program
  itself. The program is not executing the program, but is programmed to
  write code and then compile/get the OS to execute it while it's still
  running separately.

Does the program need to execute the compiled child?

I've closed this as Too Broad because it's basically saying "write some code that prints any other code." You're going to have to be a little more specific - for example, "write a program that compiles a program that will delete the original code, and then runs it" or something like that (bad example, but you get the idea). Once improvements have been made, I'll be happy to reopen this.

C: 41 38 characters
Pretty much the most trivial solution possible in C.
main(){system("gcc -xc -<<<'main;'");}

Seems like it doesn't matter if the generated program crashes (as long as it compiles), so I guess your inner program can be shortened to main; instead of main(){}

source: Stack Exchange

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

sort: votes


text:
Build a drug testing scheduler
In this problem on Puzzling.SE, I ask a question about determining the amounts of drug to use in a clinical test to minimize total drug usage and fulfill the requirements of the testing procedure.
The problem is as follows, for those of you who currently don't have access to the private beta:

A medical researcher is trying to test the effect of a certain drug on mice. He is supposed to collect data for all doses from 1 to 2N units, but only has the data collection resources for N tests. He has decided to only test dose amounts that are not multiples or factors of each other (for example, if he decided to use a dose of 15 units for a specific test, that would preclude tests for 1, 3, 5, 30, 45, etc. units). Moreover, because the drug is relatively expensive, he wants to use as little of the drug as he can manage to run these tests.
How can he arrange the dosage amounts so that he ends up using all N test packages, and the total units of dosage used in the tests are as low as possible?

The original problem states N = 25. Your task is to build a program than can answer this question for any number of tests up to N = 2500.
Your program will take a number N from 1 to 2500 as input, and return a set of N integers between 1 and 2N inclusive such that none of the N numbers are multiples of each other, each number from 1 to 2N is a factor or multiple of at least one of the numbers in the set, and the sum of all the numbers in the set is as low as you can manage.
Your program must return a valid result for each value of N to be valid.
Your program will be scored by the sum of all the returned numbers for each scenario from N = 1 to N = 2500. In the event of a tie, the shorter solution will win.

If N=15, then 2N=30 so he wouldn't be able to get 45, right? Or am I misunderstanding something?

45 is just there as an example of a multiple of 15. If it exceeds the bounds of the given N value, you don't have to take it into account.

Javascript 5,955,958,211
I'm not sure if it is the optimal solution.
I used a brute-force method.
function f(n) {
  var o=[];
  for(var i=n;i--;) o.push(2*n-i); //init array from n+1 to 2*n

  for(i=n;i>0;i--) { //bruteforce on number from n to 1
    var index=0;
    var nbFactor=0;
    for(j=0;j<n;j++) {
      if((o[j]/i)%1==0) {
        index=j;
        nbFactor++;
      }
    }
    if(nbFactor==1) { //if there is only 1 factor, replace it by the new number
      o[index]=i;
    }
  }
  return o.sort(function(a,b){return a-b;});
}

Golfed (130) :
function f(n){o=[];for(i=n;i++<2*n;)o.push(i);for(i=n;i;i--){for(d=c=j=0;j<n;j++)if((o[j]/i)%1==0)d=j,c++;if(c==1)o[d]=i}return o}

Here is the result found by my algorithm for 25 :

[8, 12, 14, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49]

Little piece of code to compute the score (takes approx. 200 seconds on Chrome) :
var result=0;
var t = Date.now();
for(var j=1;j<2501;j++) {
  result += f(j).reduce(function(r,e){return r+e;});
}
console.log("Score : " + result + "\nCompute time : " + ((Date.now()-t)/1000) + " seconds");

JavaScript - 5,955,958,211
A tiny bit of pre-processing to generate the factors of 1 ... 5000
var factors = [];

for( var i = 1; i <= 5000; i++ )
{
    factors[i] = [];
    for( var j = 1; j <= i; j++ )
    {
        if ( i % j == 0 )
            factors[i].push(j);
    }
}

The main function:
function find_min_doses( N, DEBUG )
{
    var output = [];
    var factorCount = [];
    for( var i = 1; i <= 2*N; i++ )
    {
        factorCount[i]=0;
        for( var j = 0; j < factors[i].length; j++ )
        {
            factorCount[factors[i][j]]++;
        }
    }
    var changed = false;
    do
    {
        if ( DEBUG && changed )
        {
            console.log( output.sort( function(a,b){ return a-b; } ).toString()
                         + " = "
                         + output.reduce( function(p,c){ return p+c; } )
                       );
        }
        changed = false;

        var count = 0;
        for( var i = 1; i <= 2*N; i++ )
        {
            if ( factorCount[i] == 1 )
            {
                if ( count < N )
                {
                    output[count++] = i;
                }
                else
                {
                    for( var j = 0; j < factors[i].length; j++ )
                        factorCount[factors[i][j]]--;
                }
            }
        }

        for( var i = 0; i < N; i++ )
        {
            var o = output[i];
            var f = factors[o];
            for( var j = 0; j < f.length; j++ )
            {
                var v = f[j];
                if ( factorCount[v] == 2 )
                {
                    output[i]=v;
                    for( var k = 0; k < f.length; k++ )
                    {
                        factorCount[f[k]]--;
                    }
                    changed = true;
                    break;
                }
            }
        }
    }
    while( changed );

    return output.reduce( function(p,c){ return p+c; } );
}

A test harness:
var total = 0;
var time = new Date();
for ( var i = 1; i <= 2500; i++ )
{
    total += find_min_doses( i );
}
console.log( "Score: " + total + "\nTime: " + ((new Date()-time)/1000) + " seconds." );

Output (Chrome)
Score: 5955958211
Time: 1.438 seconds.

Output (FireFox)
Score: 5955958211
Time: 66.107 seconds.

Prolog - 5,955,958,211 (?)
Its far too slow to run all 2500 test cases but it will find the optimal solution(s) in every case.
Golfed - 370 Characters
a([]).
a([_]).
a([H,N|T]):-H<N,a([N|T]).
s([],0).
s([H|T],S):-s(T,X),S is X+H.
e(_,[]).
e(V,[H|T]):-H mod V>0,e(V,T).
d([]).
d([H|T]):-e(H,T),d(T).
b(N,L):-T is 2*N,between(1,T,L).
l([H|T],M):-l(T,H,M).
l([],M,M).
l([H|T],C,M):-X is min(H,C),l(T,X,M).
m(R,M):-findall(T,s(R,T),L),l(L,M).
f(N):-length(R,N),maplist(b(N),R),a(R),d(R),m(R,M),s(R,M),write(R),nl,write(M),nl.

Ungolfed
ensure_sorted([]).                    % Ensures that the values of
ensure_sorted([_]).                   % a list are in ascending order.
ensure_sorted([Head,Next|Tail]):-
    Head<Next,
    ensure_sorted([Next|Tail]).

sum([Head|Tail],Total):-              % Calculate the sum of
    sum(Tail,Temp),                   % a list
    Total is Temp+Head.

ensure_not_divisor(_,[]).             % Ensure that the value
ensure_not_divisor(Val,[Head|Tail]):- % is not a divisor of
    Head mod Val > 0,                 % any numbers of the list.
    ensure_not_divisor(Val,Tail).

ensure_no_divisors([]).
ensure_no_divisors([Head|Tail]):-     % For each value of the list
    ensure_not_divisor(Head,Tail),    % ensure that it is not a divisor
    ensure_no_divisors(Tail).         % of the succeeding values.

btwn(N,List):-                        % Restrict the values to be
    Temp is 2*N,                      % between 1 and 2N
    between(1,Temp,List).

list_min([Head|Tail],Min):-           % Find the minimum value of
    list_min(Tail,Head,Min).          % the list.
list_min([],Min,Min).
list_min([Head|Tail],Current_Min,Min):-
    Temp is min(Head,Current_Min),
    list_min(Tail,Temp,Min).

min_sum(R,Min):-                      % For all the valid answers
    findall(Temp,sum(R,Temp),List),   % find the minimum sum.
    list_min(List,Min).

func(N):-
    length(R,N),                      % A list of N unknown values
    maplist(btwn(N),R),               % Restrict each value to integers 1..2N
    ensure_sorted(R),                 % Ensure the list is sorted.
    ensure_no_divisors(R),            % Ensure that each value is not a divisor of a higher value.
    min_sum(R,Min),                   % Find the minimum sum of all answers
    sum(R,Min),                       % Restrict the answer to have the minimum sum.
    write(R),nl,                      % Output the doses (and a newline).
    write(Min),nl.                    % Output the score (and a newline).

Python – 7,818,751,250
As a last-place reference answer, consider the following:
def f(n):
    return range(n+1, n*2+1)

For any N, choosing unit sizes from N+1 to 2N will ensure that no number is a multiple or factor of any other, simply by virtue of the fact that they're too close together. The smallest nontrivial multiple of N+1 is 2N+2, and the largest nontrivial factor of 2N is N, and no nontrivial multiple or factor of any number will fall between those two.
However, there will always be solutions that do much better than this – simply replacing 2N-2 with N-1 already will always yield a better solution.

I don't have a good solution yet, but I have a score computer and it computes 7,818,751,250 for your solution.

Oh. Did I miss it by a factor of 10? I'll correct that. Wolfram Alpha was putting the result into scientific notation, so I might have eyeballed the exponent wrong.

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


text:
Destroy Them With Lazers
Introduction
The arena is a flatland dotted with skyscrapers, which your enemies use for cover. You and your enemies shoot each other with lasers. All of you carry jet packs, allowing flight.
Which enemies can you hit with your laser, and which are hiding?
Problem
First, the size of an arena is given by an integer n on a single line. The following n lines contain n integers per line separated by a space. Each integer represents the height of the building at that location. Each building is a rectangular solid, 1 unit by 1 unit by height units.
Next, your location is given on a single line as three floating point numbers x, y, z.
Finally, the number of enemies are given by an integer m on a single line. The following m lines contain three floating point numbers per line separated by a space. These represent the  x, y, and z coordinates of an enemy. The coordinate system is defined as follows:

x is measured from left to right in the city input
y is measured from top to bottom
z is measured from the ground up

For each enemy, if an unobstructed line can be drawn from you to that enemy, output a positive integer. Otherwise, output a negative integer. Separate outputs with a new line.
Sample Input
Comments, denoted by '#', are present to help you quickly see what each line does. They will not be present in the actual input.
5              # Size of the map
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
4 4 4 4 4      # Buildings
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
2.5 0.0 4.0    # Your location
3              # Number of enemies
2.5 5.0 0.1    # Enemy location
2.5 5.0 5.0    # Enemy location
0.0 2.7 4.5    # Enemy location

Sample output
For the sample input above, we output the following:
-1
1
1

Assumptions

0 < n < 100
0 < m < 100
0 <= x <= n
0 <= y <= n
0 <= z < n
Players will not be located on or inside of a corner, edge, or side of a building
Your line of sight to an enemy will never be tangent to the corner, edge, or side of a building
A player is not an obstruction

Glad to see it out of the sandbox :)

If I can't destroy an enemy, may I join them?

@user80551 Sorry, I had to roll back your edit to the title because the mispelling was intentional. Google it.

@Rusher Oh , sorry, IDK that

Such a good question. Maybe not perfect for golfing but really good.

Related: https://www.youtube.com/watch?v=NKTpWi5itOM

This question appears to have a cumbersome IO format. Can you fix it/can I just take in a 2D array of numbers?

@StephenLeppik Sorry, that wouldn't be fair to those that already posted their answers under the current spec.

@StephenLeppik I hope that the downvote was based on the challenge as a whole, and not just the input format. When I posted this challenge three years ago, there was no guidance on what input formats made everyone happy, and so I created my own. In fact, I was one of the first ones to ask the community for their preferences. If I were to repost today, I would absolutely allow a more flexible input. Making input easier would affect the competitiveness of existing answers, so I'm not changing it.

Perl, 301 296 282
Edit 2: Actually, competition or not, there is no reason not to golf it a little further. Test it online.
Edit: Couple of parentheses gone, simpler regex to check for non-zero integer.
With newlines and indentation for readability:
sub i{<>=~/\S+/g}
@b=map[i],@r=0..<>-1;
print.1<=>(map{
    @a[1,0,2,4,3]=@a;
    @b=map{$i=$_;[map$b[$_][$i],@r]}@r;
    grep$a[3]
        &&($k=(($x=$_)-$a[0])/$a[3])**2<=$k
        &&pop[sort map@{$b[$_]}[$x-!!$x,$x],
                   ($_=$a[1]+$k*$a[4]),$_-/^\d+$/]
           >=$a[2]+$k*$a[5]
    ,@R=@r
}@a=map$_-shift@v,i,@u=@v=@$_),$/for([i])x<>

It requires 5.14 because of scalar (array reference) argument to pop.

Can you explain your solution a little bit? I haven't tested it and I haven't leant Perl, yet, so some comments would be nice.

@WorldSEnder, outline of the algorithm is as follows. Straight line PE connects two points in 3-D space, "Player" (X1Y1Z1) and "Enemy" (X2Y2Z2). Its projection on (XY) plane intersects some of the grid-lines i.e. integers x = const or y = const such as X1 < x < X2 or Y1 < y < Y2 (assuming here that e.g. X1 < X2, but it's not important). Coordinates x y of these intersections can easily be found, and therefore z coordinate of a point on PE line, too.

(continued) On the other hand, for any x y coordinates, we know height h of the building (rather, maximum height of up to 4 buildings which share x y point). Enemy can be shot if (and only if) h < z for all "intersection points" mentioned above. Implementation is some basic arithmetics, as well as several tricks with Perl for the purpose of golfing. Decyphering the details of how I did it a month ago will take some time now :-).

Argh, as I see there is a bug in the last (5th) revision: indices to the elements of @a array in grep expression should appear in the order 0,3,0,4,1,5,2 instead of 3,0,3,1,4,2,5 - sorry.

OK, better late than never, and to finish with this all, here is commented version.

Just revisiting this and noticed you beat the current winner, so I'm shifting accepted answer to you :)

Python 2.7 - 429 420 308 308 chars
I thought of this challenge more of as a math problem than a code golf problem, so don't be too harsh to me if I missed some obvious optimizations. Anyways, here is the code:
b=lambda:raw_input().split()
m=map
d=range(input())
h=[m(int,b())for _ in d]
x,y,z=m(float,b())
for e,f,g in[m(float,b())for _ in[1]*input()]:o=lambda x,y,u,v,i,j:i<=x+u/v*(j+1-y)<=i+1<[]>z+(g-z)/v*(j+1-y)<=max(h[i][j:j+2])if v else 0;print 1-2*any(o(x,y,e-x,f-y,j,i)+o(y,x,f-y,e-x,i,j)for j in d for i in d)

This should work for edge and corner cases (pun unintended) and is pretty solid. Ouput for the provided example:
-1
1
1

And here is a "short" explanation:
fast_read = lambda : raw_input().split() # define a helper
# m = map another helper
grid_range = range(input())
houses = [map(int, fast_read()) for _ in grid_range]
# 'map(int,...)' is a shorter version of '[int(a) for a in ...]'
pos_x,pos_y,pos_z = map(float, fast_read()) # read the player position
# the following loops through all enemy coordinates
for ene_x, ene_y, ene_z in [map(float,fast_read()) for _ in[1]*input()]:
    vec_z = ene_z - pos_z
    # is_hit macro uses vector math to detemine whether we hit a specific wall
    # wallhit -> 1
    # no wallhit -> 0
    is_hit = lambda pos_x, pos_y, vec_x, vec_y, co_x, co_y:\
        (co_x <= pos_x + vec_x/vec_y * (co_y + 1 - pos_y) <= co_x + 1 # check if hit_x is good
        < [] > # an effective and
        pos_z + (ene_z - pos_z)/vec_y * (co_y + 1 - pos_y) <= max(houses[co_x][co_y:co_y + 2]) # check if hit_z is good
        if vec_y else 0) # if vec_y is 0 we can't hit the wall parallel to y
    print (.5 - # can hit -> 0.5 - 0 = 0.5, hit -> 0.5 - 1 = -0.5
            any( # if we hit any wall
                # we swap x and y-coordinate because we read them "incorrect"
                is_hit(pos_x, pos_y, ene_x-pos_x, ene_y-pos_y, cur_y, cur_x) # check for hit in x-direction
                + # effective 'or'
                is_hit(pos_y, pos_x, ene_y-pos_y, ene_x-pos_x, cur_x, cur_y) # check for hit in y-direction
                    for cur_y in grid_range # loop y
                for cur_x in grid_range)) # loop x

I guess this is full of flaws. Btw I saved chars at nesting (first level is one space, second one tab, then one tab and a space...).
I hope after all this answer can point to the way to do it.

I just realized that the sample input was invalid because one of the enemies was located directly on the ground, which is technically the top of a zero height building, which I promised would not happen. Your submission passes the corrected test case, but it fails this one - http://ideone.com/8qn3sv . Can you check my test case? I might be missing something or maybe my coordinate system is unclear.

No, it's just that the vector is going right through the corners... now I know why you promised Assumption 6&7 :)

btw, I output a negative float but that can be fixed with 2 extra chars (print 1-2*... instead of print.5-...) So it's not that big of a difference I guess

You passed the few tests I came up with. Nice job! You should still go ahead and make it print integers to keep in line with the spec.

Accepting your answer until someone comes up with a better solution. I don't think they will. Very rarely does anyone revisit old solved challenges. You should golf more! It looks like you know your stuff. :)

Well, looks like someone came back and beat you (although I didn't notice for nearly a month). Still, thanks for answering!

C - 2468
Not golfed at all, but hopefully it's a starting point for more interesting implementations. The implementation of intersect is cribbed heavily from Adrian Boeing. His pseudo-code was incomplete, but his explanation of the math was invaluable. The basic idea is that you take a line from the player to the target and clip it against all the walls of each building, updating the length for each wall. The remaining length is the portion inside the building, so if it's zero, there was no intersection.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
    float x;
    float y;
    float z;
} vec3;

float
dot(vec3 a, vec3 b)
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

vec3
scale(float s, vec3 a)
{
    vec3 r;
    r.x = s * a.x;
    r.y = s * a.y;
    r.z = s * a.z;
    return r;
}

vec3
add(vec3 a, vec3 b)
{
    vec3 r;
    r.x = a.x + b.x;
    r.y = a.y + b.y;
    r.z = a.z + b.z;
    return r;
}

int
intersect(vec3 a, vec3 b, vec3 *normals, vec3 *points, int nnormals)
{
    vec3 ab = add(b, scale(-1, a));
    float tfirst = 0;
    float tlast = 1;
    int i;
    for(i = 0; i < nnormals; i++)
    {
        float d = dot(normals[i], points[i]);
        float denom = dot(normals[i], ab);
        float dist = d - dot(normals[i], a);
        float t = dist / denom;
        if(denom > 0 && t > tfirst)
        {
            tfirst = t;
        }
        else if(denom < 0 && t < tlast)
        {
            tlast = t;
        }
    }
    return tfirst < tlast ? 1 : 0;
}

const vec3 N = {0,-1,0};
const vec3 S = {0,1,0};
const vec3 W = {-1,0,0};
const vec3 E = {1,0,0};
const vec3 D = {0,0,-1};

int
main(void)
{
    vec3 normals[5];
    vec3 player;
    vec3 *targets;
    int i;
    int j;
    vec3 *buildings;
    vec3 *b;
    int nbuildings = 0;
    int n;
    int m;
    char line[300];
    normals[0] = N;
    normals[1] = S;
    normals[2] = W;
    normals[3] = E;
    normals[4] = D;
    fgets(line, 300, stdin);
    n = atoi(line);
    /*5 sides for each building*/
    buildings = calloc(n * n * 5, sizeof(*buildings));
    b = buildings;
    for(i = 0; i < n; i++)
    {
        char *z;
        fgets(line, 300, stdin);
        for(j = 0; j < n && (z = strtok(j ? NULL : line, " \n")) != NULL; j++)
        {
            vec3 bottom;
            vec3 top;
            if(z[0] == '0') continue;
            nbuildings++;
            bottom.x = j;
            bottom.y = i;
            bottom.z = 0;
            top.x = j + 1;
            top.y = i + 1;
            top.z = atoi(z);
            b[0] = top;
            b[1] = bottom;
            b[2] = top;
            b[3] = bottom;
            b[4] = top;
            b += 5;
        }
    }
    fgets(line, 300, stdin);
    player.x = atof(strtok(line, " "));
    player.y = atof(strtok(NULL, " "));
    player.z = atof(strtok(NULL, " \n"));
    fgets(line, 300, stdin);
    m = atoi(line);
    targets = calloc(m, sizeof(*targets));
    for(i = 0; i < m; i++)
    {
        int hit = 1;
        fgets(line, 300, stdin);
        targets[i].x = atof(strtok(line, " "));
        targets[i].y = atof(strtok(NULL, " "));
        targets[i].z = atof(strtok(NULL, " \n"));
        for(j = 0; j < nbuildings; j++)
        {
            b = &buildings[j * 5];
            if(intersect(player, targets[i], normals, b, 5) == 1)
            {
                hit = 0;
                break;
            }
        }
        printf("%d\n", hit ? 1 : -1);
    }
    free(buildings);
    free(targets);
    return 0;
}

Tried a few test cases and you passed all of them. Here is the ideone that anyone else can use to verify - http://ideone.com/MTXpzF


text:
Write a square-counting program
A well-known puzzle involves counting how many squares can be made using the points on a 3x3 grid:
.  .  .
.  .  .
.  .  .

The answer is 6 — four small squares, one large square, and one square formed from the top, left, bottom, and right pegs, with edges along the diagonals of the squares.
Your task is to build a program that counts the total number of squares that can be formed from a set of points.
Your program will take input in one of two formats (of your choosing):

An M by N grid  consisting of either . or . . represents a point on the grid that a square can be a corner of, and all spaces on the grid are exactly one unit apart horizontally or vertically.
A list of coordinate pairs representing points that a square can be on.

and return the number of distinct squares that can be formed using the points provided. Your program must return a correct solution for every possible input.

For example, take the input above but where the center square is missing:
...
. .
...

There are only two possible squares here (the big one and the diagonal one), so the program should return 2.

The shortest code to do this in any language wins.

I would upvote you, but your reputation is perfect. (6666) :-P

As long as I have that reputation, I'm the devil :(

Are we talking about squares or rectangles? You say the horizontal and vertical unit is both 1. But in your example, the dots are one unit apart vertically but 3 units apart horizontally. So how are those squares? Also could there be gaps in the input? If so, could you provide a more complex example?

The dots in the question are only spaced out more widely for aesthetic purposes. They should be only one character apart for purposes of the actual question.

What's the max possible value for M and N, and the max number of total points? And are we free to say how many points there are in any way we wish? (Either by taking an input at the beginning, or by stopping once some kind of EOF is reached.)

You can take inputs in the format of your choosing as long as it's one of the two types of format above, and your program should work efficiently for any M and N up to 300, but it should eventually work for any value of M and N at all.

What about M,N > INT_MAX (or similar)?

M and N up to 300 means storing a character array of 90000 points in the first type of input, or 90000 coordinate pairs in the second type. That's a reasonable limitation, but a data structure of that size would normally be hard coded. So when you say "eventually" do you mean "the algorithm shall be adaptable by tweaking the constants and types in the program for any value of M and N"?

@ace: The algorithm your program uses should theoretically be able to solve any bounded case, but for practical limitations' sake, you can assume that M and N will be less than INT_MAX.

@steveverrill That works, I suppose.

Can the squares be rotated at angles other than 45*? e.g: a square that looks more similar to a skewed diamond?

@Ourous like 4 knight's moves in chess forming a square for example. As far as I can tell, the existing answer considers those. It will make a massive difference on the larger sizes, where you could have gradients of 1 in 100 or less.

In the first example the answer should be 5, since the last option you describe is a Rhombus (aka diamond). Like wikipedia said   "a rhombus with right angles is a square" Therefor the last option shouldn't count right?

No, the whole point of the original riddle is that the rhombus is a square because the sides are at right angles to each other.

Python, 95
Takes a list of coordinates from stdin.
l=input();print(sum((c-d+b,d+c-a)in l and(a-d+b,b+c-a)in l for a,b in l for c,d in l)-len(l))/4

Explanation:

 For each pair of points (a,b) and (c,d), check if the square with additional points (c-d+b,d+c-a) and (a-d+b,b+c-a) is in the list.  This counts each square 4 times, and each point once (when (a,b) = (c,d)), so subtracting the number of points and dividing by 4 gives the number of squares.

Clever, concise.


text:
Stack the deck!
Alice and Bob like to play a card game, with a deck of cards numbered with consecutive nonnegative integers.
Alice has a very particular way of shuffling the deck, though. First, she takes the top card from the deck and puts it at the bottom of the deck. Then she removes the next card, and starts a pile with it. Then, again she cycles the top card to the bottom, and puts the new top card onto the pile. She repeats this process until she's emptied the deck, at which point the pile is the new deck.
  deck     |  pile
-----------+-----------
 3 1 4 0 2 |
 1 4 0 2 3 |
 4 0 2 3   |         1
 0 2 3 4   |         1
 2 3 4     |       0 1
 3 4 2     |       0 1
 4 2       |     3 0 1
 2 4       |     3 0 1
 4         |   2 3 0 1
           | 4 2 3 0 1
 4 2 3 0 1 |

Figure 1: Alice performs her shuffle on the 5-card deck "3, 1, 4, 0, 2". The backs of the cards are all facing left.
One day, Bob announces he's taking a week's vacation. Alice, having nobody to play the game with, enlists her friend Eve. Now, Eve is a shameless cheater, so when she sees Alice's peculiar shuffle, she realizes that she can stack the deck beforehand to her advantage!
When Eve gets home after the first day, she does some analysis on the game and figures out that her best odds are when the cards are in the order 0, 1, 2, 3, 4, 5, ... She didn't catch how many cards were in the deck, though, so she hatches a harebrained scheme to write some code on her arm that, when run, takes the size of the deck and displays the order Eve needs to put the cards in, so that when Alice shuffles the deck, the final deck is in the order 0, 1, 2, 3, ...
It doesn't really matter to Eve what language the code is in (she knows them all), or whether the code is a function taking an integer argument and returning an array, or a full program taking input via a command line argument or STDIN and writing the results to STDOUT. She does, however, need the code as short as possible, to minimize the chance of Alice seeing it and catching her.
Immoral as it might be, can you guys help Eve out?
Example inputs and outputs:
in  out
 1  0
 2  0 1
 5  2 4 0 3 1
10  2 9 4 8 0 7 3 6 1 5
52  6 51 25 50 12 49 24 48 1 47 23 46 11 45 22 44 5 43 21 42 10 41 20 40 2 39 19
    38 9 37 18 36 4 35 17 34 8 33 16 32 0 31 15 30 7 29 14 28 3 27 13 26

Lovely phrasing, I'll get cracking.

It's slightly confusing that your stacks are aligned at the top. And stating the order of the stack explicitly would also help clarify the question a bit.

The same goes for the deck.

Also: are you trying to trick us by having a sample of length 5? Without wishing to spoil: shuffle(shuffle(range(5))) == range(5)...

@Synthetica I guess it so happens that Alice's shuffle on a 5-card deck is an involution. I didn't really think about it when posting because it doesn't hold in general.

If we choose STDOUT, does the output have to be exactly as in the example or is an array OK?

Related question, although it's a bit of a subtle relationship. Taking k=2, solutions to Josephus' problem tell you the index of the 0 in the output to this problem; this is essentially the extended Josephus problem in disguise.

GolfScript, 15 14 13 bytes
])~,{\+)\+}/`

Try it online.
Example
$ golfscript alice.gs <<< 10
[2 9 4 8 0 7 3 6 1 5]

How it works
])    # Collect the stack into an array and pop. This leaves [] below the input string.
~     # Interpret the input string.
,     # For input “N”, push the array [ 0 … N-1 ] (the pile).
{     # For each card on the pile:
  \+  # Put the card on top of the deck.
  )   # Remove a card from the bottom of the deck.
  \+  # Put the card on top of the deck.
}/    #
`     # Convert the deck into a string.

You might use {}/ instead of the map operator to save a char.

Thanks! I wanted an array, so I used map. Force of habit...

]( as the first two chars effectively puts an empty array under the input, saving you a later []\ .

Thanks! It took me way too long to figure out why this wasn't working with the online interpreter. Forgot to clear the stack...

Julia, 83
u(n)=(a=[n-1:-1:0];l=Int[];[push!(l,shift!(push!(l,pop!(a)))) for i=1:length(a)];l)

The last element in the returned vector is the top of the deck.

Mathematica, 92 77 46 bytes
Expects the input in variable n:
l={};(l=RotateRight[{#-1}~Join~l])&/@Range@n;l

It's just literally playing the shuffle backwards, by moving over a card and then putting the bottom card on top.
EDIT: No need to keep track of the output stack, just iterate through the integers.

Python 2.7 - 57
d=[0]
for j in range(1,input()):d=[d.pop()]+[j]+d
print d

Nice and simple, just invert the shuffle. Fairly close to how Golfscript does it.

J (13 chars) and K (9)
As it turns out, it's a simple process to undo the shuffle, and APL-likes have the fold adverb / to help them out in making this as short as possible.
J takes 13 char with (_1|.,)/@i.@-, while K only needs 9: |(1!,)/!:. APL would be similarly terse.
Here's a step-by-step trace of the J version.
(_1|.,)/@i.@- 4                  NB. recall that J is right-associative
(_1|.,)/@i. - 4                  NB. u@v y  is  u v y
(_1|.,)/@i. _4                   NB. monad - is Negate
(_1|.,)/ i. _4                   NB. @
(_1|.,)/ 3 2 1 0                 NB. monad i. is Integers, negative arg reverses result
3 (_1|.,) 2 (_1|.,) 1 (_1|.,) 0  NB. u/ A,B,C  is  A u B u C
3 (_1|.,) 2 (_1|.,) _1 |. 1 , 0  NB. x (M f g) y  is  M f x g y
3 (_1|.,) 2 (_1|.,) _1 |. 1 0    NB. dyad , is Append
3 (_1|.,) 2 (_1|.,) 0 1          NB. dyad |. is Rotate
3 (_1|.,) _1 |. 2 , 0 1          NB. repeat ad nauseam
3 (_1|.,) _1 |. 2 0 1
3 (_1|.,) 1 2 0
_1 |. 3 , 1 2 0
_1 |. 3 1 2 0
0 3 1 2

You might notice that in the J, we reverse the array of integers first, but in the K we do it afterwards: this is because the K fold is more like a foldl, compared to the J's foldr.