text:
Naïve Markov Chain Word Generation
There are many ways to generate random words. You can take random syllables from a set, you can use n-tuples, probably neural networks (what can't they do?), alternating between consonants and vowels, etc. The method this challenge is based off of is by far the worst. It uses a Markov chain to generate random words. If you are familiar Markov chains, you probably know why this method is so terrible.
If you want to read about Markov chains, click here.
Your program will take an input one or more words and generate a single random word, through the method of a weighted Markov chain. Since that probably makes sense to no one but me, here is an explanation through the use of a picture of the Markov chain with the input of abba:

(All edge weights are the same for all pictures) Your program will output the path through a Markov chain based on the input text. As you can see, there is a 1/2 chance it will output a, 1/8 chance of aba, 1/16 chance of abba, 1/32 chance of ababa, etc.
Here are some other example Markov chains:
yabba dabba doo

wolfram

supercalifragilisticexpialidocious

If you want more examples, use this. (I worked way too hard on it)
Details of challenge:

Input can be taken as a list of strings, or as a space, comma, or newline separated string
You may assume that all the words will be entirely lowercase with no punctuation (ASCII 97-122)
You may write either a program or a function
To test, you could probably input the examples and see if all inputs line up with the Markov chains

This is code-golf, so your program is scored in bytes.
Let me know if any part of this is unclear, and I will try to make it make more sense.

It probably makes sense to quite a fre people, because Chatgoat and Marky are both weighted Markov chatbots IIRC.

I don't understand the relationship between the input and those Markov chains. It sometimes appear to be impossible to  produce the input word by using one path in the given chain (e.g. "yabba dabba doo". No self loop for b so you cannot produce a double b. Moreover once you reach a b it doesn't seem possible to return to the start to produce the other words). I believe you must clarify what the requirements are...

@Bakuriu the error on the yabba dabba doo is an accident. I will fix it as soon as possible. As to the not being able to get back to start, you only generate one word from a given set of words. Does that clarify it?

Pyth, 38 32 bytes
VQJK1FZacN1k XKH]Z=KZ;WJ=JO@HJpJ

Thanks to FryAmTheEggman for 5 bytes!
To be honest I started writing Python answer when I noticed somebody posted a very similiar one so I decided to challenge myself with something new so I rewrote my answer (which was basically Pietu's answer) in Pyth.
Input is an array of strings ["Mary" , "had" , "a" , "little"]

Nice first post, welcome to PPCG :) Some golf tips: F is only ever useful when the variable V would use gets overridden when you don't want it to, so you can change the first Fd to V and replace d with N elsewhere. [) around one element is the same as ]. Instead of adding to a list you can use append (a) to save the casting. More in general, I think you can probably make this shorter by taking a more functional approach. I'm also not sure what the +kJ is for, adding the empty string to a string should be a noop?

Thanks! I would love to take more functional approach sadly I am not well versed in functional stuff (lambda expressions are probably my closest experience). Thanks for the bytes by the way!

Python 2, 138 133 bytes
from random import*
M={}
for w in input():
 P=p=1
 for k in list(w)+[""]:M[p]=M.get(p,[])+[k];p=k
while P:P=choice(M[P]);k+=P
print k

Takes in an array of string such as ["yabba", "dabba", "doo"].
Example outputs with that input:
do
ya
dabbbbbbbaba
do
ya
yaba
da
dabba
yabbababbababbbbababa
do

I also want to highlight this result.
stidoupilioustialilisusupexpexpexpicexperagilidoupexpexpilicalidousupexpiocagililidocercagidoustilililisupialis

Ruby, 112 107 101 99
Input is stdin, newline-seperated strings.
QPaysTaxes helped a lot with golfing it down!
M={}
while gets
k=''
$_.each_char{|c|M[k]||=[];M[k]<<c;k=c}
end
k=''
print k=M[k].sample while M[k]

I'd appreciate credit :D (Something like "thanks to QPaysTaxes for golfing help" or the like seems common around here)

Matlab, 160 bytes
Takes input as a cell array of strings, like {'string1','string2','string3'}.
s=input('');n=[];l=96;for i=1:numel(s);n=[n 96 double(s{i}) 123];end
while(l(end)<123);p=n(find(n==l(end))+1);l=[l p(randsample(nnz(p),1))];end
char(l(2:end-1))

This reads the words, and converts them to a vector of ASCII values, with a 96 to mark the start of a word, and a 123 to represent the end of a word. To construct a random word, start with a 96. The search for all the integers that follow 96 in the vector, and take a random sample from those to pick the next letter. Repeat this, looking for all the integers that follow the current one, until 123 is reached, which signals the end of the word. Convert it back to letters, and display.
The input {'yabba','dabba','doo'} produces results like da. Here are the results of ten runs: yabababbbababa,da,doo,doooooo,ya,da,doooo,ya,do,yaba.


text:
Longest word using a single row of the qwerty keyboard
The three rows of the qwerty keyboard are qwertyuiop, asdfghjkl and zxcvbnm. Your task is to find the longest word that can be typed using only one row of the keyboard, from a given list of words.
Sample input 1
artist
home
gas
writer
geology
marine
twerp

Output
writer

(Of the given words, only gas, writer and twerp can be written using a single row, and writer is the longest)
The words may not be actual words (so don't assume the third row to be invalid). However, you can assume that there will always be exactly one answer (no more, no less).
Sample input 2
wrhuji
bxnzmmx
gllwssjjd
vnccbb
lrkjhgfdsa
tttttt

Output
bxnzmmx

Additional punctuation and whitespaces can be provided in input (as per language requirements). However, no extra output should be given. Input and output are in lower case. Shortest code wins.

@MartinBüttner I would really like to see how this could be solved with Retina.  Do you think it is easily done?

Are the input words always in lowercase?

@nimi Yes, they are.

@ghosts_in_the_code You should state that in the challenge for clarity

@JerryJeremiah it's doable but finding the largest of them will likely dominate the code and make it uncompetitive. I'll add an answer later today.

So no newlines/ANSI color codes/other non-suppressible output?

I wonder if the shortest way of handling the "row checking" is not to just list out all the keystrokes.  If a language has built-in separation of vowels and consonants, that might be an advantage.  Nearly half of the top row is every vowel except A; the next row contains A and S and all consonants from D through L.  The bottom row is almost entirely pairs if you treat X and Z as next to each other in a list of consonants).

Relevant xkcd: https://what-if.xkcd.com/75/

@JerryJeremiah There you go.

@MartinBüttner  thanks so much.  I am just facinated by retina but not competent enough to solve these problems myself.

@MartinBüttner Can you please see my sandoboxed post here? It has not received enough attention and I'm not confident of actually posting it.

Python 2, 84 bytes
lambda l:max(l,key=lambda w:(-len({"asdfghjklzxcvbnm".find(c)/9for c in w}),len(w)))

Finds the max of the input, comparing by fewer keyboard rows spanned, then in increasing length. The keyboard row value is extracted by "asdfghjklzxcvbnm".find(c)/9, which takes the middle row to 0, the bottom row to 1, and the top row, which is excluded, to -1, since find gives -1 for missing values.
Other attempts:
lambda l:max((-len({"asdfghjklzxcvbnm".find(c)/9for c in w}),len(w),w)for w in l)[2]
lambda l:max(l,key=lambda w:len(w)-1./len({"asdfghjklzxcvbnm".find(c)/9for c in w}))
lambda l:max([w for w in l if len({"asdfghjklzxcvbnm".find(c)/9for c in w})<2],key=len)

1 / character more for Python 3 ;)

I didn't know the grammar allowed for no whitespace between 9 and for...

This is by far my favorite answer.

@jogloran, so long as the characther is not an E or e, you can pretty much always remove whitespace between a number and a variable name/keyword

@wnnmaw That's no longer true for newer versions of Python, e.g. 4if 0else 2 is valid in 2.7.11 and 3.5.1 (and probably has been valid for a few versions prior)

@Sp3000 I was browsing my older answers and found this, 4if 0else2 doesn't work in 2.5, 2.6 (and naturally not in 2.4 either as the syntax didn't exist there. Neither does it work in Python3s <3.3

Japt, 32 30 bytes
;Uf_¬£DbXu)f10Ãä¥ eÃn@Yl -XlÃg

Test it online! Input is an array of strings.
How it works
;Uf_  ¬ £  DbXu)f10Ã ä¥  eÃ n@  Yl -XlÃ g
;UfZ{Zq mX{DbXu)f10} ä== e} nXY{Yl -Xl} g

         // Implicit: U = input array of strings
;        // Reset variables A-L to various values.
         // D is set to the string "QWERTYUIOP\nASDFGHJKL\nZXCVBNM".
UfZ{   } // Take U and filter to only the items Z that return truthily to this function:
Zq       //  Split Z into chars, then
mX{    } //  map each char X by this function:
DbXu)    //   Return D.indexOf(X.toUpperCase()),
f10      //   floored to a multiple of 10.
         //  This maps each char to 0 for the top row, 10 for the middle, 20 for the bottom.
q ä==    //  Split the resulting string into chars and check each pair for equality.
e        //  Check that every item in the result is truthy. This returns true if all chars
         //  are on the same row; false otherwise.
         // Now we have only the words that are entirely on one row.
nXY{   } // Sort by passing each two args X and Y into this function:
Yl -Xl   //  Return Y.length - X.length. Sorts the longest to the front.
g        // Get the first item in the resulting array. Implicitly output.

Woah, did you just outgolf Dennis?

This is going to be hard to beat

Do you have "QWERTYUIOP\nASDFGHJKL\nZXCVBNM"a a predefined literal? Well played :-)

I can't seem to find where it is stated that D is set to QWERTYUIOP\nASDFGHJKL\nZXCVBNM, even the page you refer to seems to state Variables <...> D 13

@sukhmel A ; at the beginning of the program resets variables A-L to various values. D is set to the keyboard string. You can find more info here.

I was going to say that changing your language to have a built-in that trivializes the question is probably cheating, but it looks like it's had that since 0e43c90 on Jan 11th...

Python 2.5+ and 3, 93 bytes
Had to test how many strokes for this approach; this uses the fact that a.strip(b) results in empty string if a solely consists of characters that occur in b.
The function takes list of strings and returns a string.
lambda a:max(a,key=lambda x:(~all(map(x.strip,['qwertyuiop','asdfghjkl','zxcvbnm'])),len(x)))

Welcome to PPCG, nice first post :)

Why is the key variable there? I think you can remove it.

@CatsAreFluffy no, that is not possible. the key argument of max function is keyword-only.

Ack, I forgot about kwargs.

Retina, 73 bytes
G`^([eio-rtuwy]+|[adfghjkls]+|[bcmnvxz]+)$
1!`(.)+(?!\D+(?<-1>.)+(?(1)!))

Try it online!
Conclusion: Retina needs a sorting stage.
Explanation
G`^([eio-rtuwy]+|[adfghjkls]+|[bcmnvxz]+)$

This is a grep stage: it only keeps lines which are matched by the regex. I.e. those which are formed exclusively from one of those character classes.
1!`(.)+(?!\D+(?<-1>.)+(?(1)!))

Now we just need to find the largest of the remaining strings. We do this by matching all words which are at least as long than all the words after them. The 1 is a new addition to Retina (released two days ago), which limits this match stage to considering only the first such match. And ! instructs Retina to print the match (instead of counting it).

This is cool! I'll have to look at balanced groups sometime. Although they seem to be hard to understand. I've tried this (and it looks like it works), but I wanted to wait for your answer to see what kind of thing will you create.

@daavko Sorry for the self-promotion, but have you read my Stack Overflow post on balancing groups? I'm being told it's a good introduction. The concept itself really isn't that complicated, especially if you don't use the (?<a-b>...) syntax which is rarely needed in code golf.

I don't think I've seen that post. Most likely because I don't browse Stack Overflow often. Thanks for the link, I'll bookmark it and read it.

Probably off topic for a comment, but pretty much 100% of my knowledge of balancing groups comes from having read your post. I think you can self-promote it any time, it's a great help :) Anyway more on topic, would sort stage work something like O-1`.* to get the line with the longest input? Maybe it should work like transliteration and have more than one backtick separated region, a regex to split on and one to count? Actually maybe this also belongs in chat...  ¯_(ツ)_/¯

Never would have thought of o-r, awesome.

Are the parentheses in the first line needed?

Java, 154 142 or 142 130 bytes
Because, ya know, Java.
C#, for comparison.
146 bytes if input has to be a single string with values separated by \n:
s->java.util.Arrays.stream(s.split("\n")).filter(g->g.matches("[wetyuio-r]*|[asdfghjkl]*|[zxcvbnm]*")).max((a,b)->a.length()-b.length()).get()

134 bytes if I can assume input as String[] instead:
s->java.util.Arrays.stream(s).filter(g->g.matches("[wetyuio-r]*|[asdfghjkl]*|[zxcvbnm]*")).max((a,b)->a.length()-b.length()).get()

Slightly ungolfed:
UnaryOperator<String> longestQwertyStr = s ->
        java.util.Arrays.stream(s.split("\n")) // Split string input over `\n` and convert to Stream<String>
                .filter(g->g.matches("[wetyuio-r]*|[asdfghjkl]*|[zxcvbnm]*")) // Filter to Strings that only use characters from a single row
                .max((a,b)->a.length()-b.length()) // Find the max by comparing String length
                .get(); // Convert from Optional<String> to String and implicit return single statement lambda

Second lambda is a Function<String[],String>.

My updated version now even beats the shorter lambda as a full program :)

@SBI Curse Java's long method invocations! (All in good fun)

Being a Java developer myself, it's nice to see a verbose language that manages to be concise at the same time :)

If we're going to make an input assumption, lets make the one that helps us the most, input comes in as a List:l->l.stream().filter(g->g.matches("[wertyuio-r]*|[asdfghjkl]*|[zxcvbnm]*")).max((a,b)->a.length()-b.length()).get() (116 chars)

@Andreas As per my recent meta discussion, if a lambda takes a List, you have to include import java.util.*; in the byte count, meaning taking a list is -16 bytes by taking a List but +19 to import the List. HOWEVER, you did catch there using max instead of reduce for a gain of -7 bytes.

We have to score the imports!? That is a deathblow for java ever to score well. I trimmed a couple chars around the regex, too: [wetyuio-r]*|[asdfghjkl]*|[zxcvbnm]*

@Andreas Java will never score well. ^()$ need to be in the regex to assert that we match the whole string, but yes, you managed to save another character (that I miscounted as not saving anything earlier)! Thank you!

String::matches already matches the whole string. You're thinking of String::find

@Andreas I have been illuminated. Sorry for not believing your (or at least testing my assumption).

Python 3, 98
Saved 5 bytes thanks to Kevin.
Saved 3 bytes thanks to PM 2Ring.
Saved 3 bytes thanks to Antti Haapala.
Brute forcing it at the moment. I filter the words down to only those contained by a single row, and then sort for max string length.
lambda a:max(a,key=lambda x:(any(map(set(x).__le__,['qwertyuiop','asdfghjkl','zxcvbnm'])),len(x)))

Test cases:
assert f(['asdf', 'qwe', 'qaz']) == 'asdf'
assert f('''artist
home
gas
writer
geology
marine
twerp'''.splitlines()) == 'writer'
assert f('''wrhuji
bxnzmmx
gllwssjjd
vnccbb
lrkjhgfdsa
tttttt'''.splitlines()) == 'bxnzmmx'

Jelly, 40 34 bytes
p“£vẈ¬ḣ“£AS°GƤg“£ḷḳƤ²ƤȤḤ»f/€fµL€Mị

Try it online!
How it works
p“£vẈ¬ḣ“£AS°GƤg“£ḷḳƤ²ƤȤḤ»f/€fµL€Mị

 “£vẈ¬ḣ“£AS°GƤg“£ḷḳƤ²ƤȤḤ»           Use dictionary compression to yield
                                    ['quipo twyer', 'adj flash jg', 'bcmnz xv'].
p                                   Cartesian product; for all pairs of an input
                                    string and one of the rows.
                         f/€        Reduce each pair by filter, keeping only the
                                    letters in the input string that are on that
                                    particular keyboard row.
                            f       Filter the results, keeping only filtered words
                                    that occur in the input.
                             µ      Begin a new chain.
                              L€    Get the length of each kept word.
                                M   Get the index corr. to the greatest length.
                                 ị  Retrieve the word at that index.

Why don't you use the QWERTY builtin Øq? Did it not exist when this answer was posted?

PowerShell v2+, 72 bytes
($args-match"^([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)$"|sort Length)[-1]

Takes input via command-line arguments as $args, then uses the -match operator with a regex to select only the words that are exclusively made up of one keyboard row. We pipe those results into Sort-Object that sorts by the property Length. We can do this since strings in PowerShell are all of the System.String type, which includes .Length as a sortable property. This sorts the strings into ascending order by length, so we take the last one with [-1], leave it on the pipeline, and output is implicit.
Example
PS C:\Tools\Scripts\golfing> .\longest-word-qwerty-keyboard.ps1 asdf qwe zxc typewriter halls establishment
typewriter

Pyth, 45 35 bytes
Thanks to @FryAmThe Eggman for saving me some bytes!
elDf}k-LTc."`z:I¿Ç  Ì(T4²ª$8·"\`Q

Try it here!
Takes input as a list of words.
Explanation

elDf}k-LTc."..."\`Q   # Q = list of all input words

   f              Q   # Filter input with T as lambda variable
         c."..."\`    # List of all keyboard rows
      -LT             # Remove all letters of the current input row from the current input
                      # word. Results in a list of 3 string with one being empty if
                      # the word can be typed with one row
    }k                # Check if the list contains an emtpy string
elD                   # order result list by length and take the last

Ruby, 88 82 69
If I'm not allowed to take a list of strings and must take a multiline string, add +12 to the score and add .split('\n') right before the .grep call.
Thanks CatsAreFluffy for teaching me about stabby lambdas in Ruby, and further optimizations from manatwork
->x{x.grep(/^([o-rwetyui]+|[asdfghjkl]+|[zxcvbnm]+)$/).max_by &:size}

No, you add .split('\n') before the .select, right? And why no stabby lambdas?

I didn't know about the stabby lambda until just now, when you mentioned it. Thanks!

Can you add a space between the -88- and 82?

No need to assign it to a variable, anonymous functions are allowed; if the only thing to do inside .select's code block is to match it against a regular expression, .grep is more suitable; no need to put parenthesis around the last method's parameters in a call chain; .length has a shorter alias, .size: ->x{x.grep(/^([o-rwetyui]+|[asdfghjkl]+|[zxcvbnm]+)$/).max_by &:size}

C#, 141 / 112 / (120 bytes)
Contender for worst golfing language, for obvious reasons. Uses "my" locale with qwertz instead of qwerty but works fine otherwise.
Full program without where:
static void Main(string[]a){Console.WriteLine(a.OrderBy(x=>x.Length).Last(x=>Regex.IsMatch(x,"^([qwertzuiop]+|[asdfghjkl]+|[yxcvbnm]+)$")));}

Only output without Where:
Console.WriteLine(a.OrderBy(x=>x.Length).Last(x=>Regex.IsMatch(x,"^([qwertzuiop]+|[asdfghjkl]+|[yxcvbnm]+)$")));

Only output (original):
Console.WriteLine(a.Where(x=>Regex.IsMatch(x,"^([qwertzuiop]+|[asdfghjkl]+|[yxcvbnm]+)$")).OrderBy(x=>x.Length).Last());

The challenge says you have to use querty and since you are hardcoding this anyway, I don't see any reason to change that. Also you can use a function (maybe even a lambda) instead of a full program to save some bytes. This is always allowed unless explicitly forbidden in the challenge.

Being proud of my layout :P, it's not like I have a chance at winning anyway using C#. Edited in a version that's only the output.

Added another alternative, using only Last with a predicate instead of using where. This shaves off another 8 bytes.

awk , 92 84 81 bytes
(/^([wetyuio-r]+|[asdfghjkl]+|[zxcvbnm]+)$/)&&length>length(a){a=$0}END{print a}

saved 3 bytes thanks to @Wolfgang suggestion

You can subtract a byte by using [wetyuio-r] instead, and also two more by doing /^(expr|expr|expr)$/ instead of `/^expr$|^expr$|^expr$/

@Wolfgang: thanks for the tip. I tried already the 2nd one and on my awk it gave me the longest word instead of the right one... I'll try again. I agree with the first one though, saves 1 byte

@Wolfgang: hmm, does work this time (I may have fumbled the parenthesis on my own test, friday). I edit your tips in, thanks.

Are you sure the parenthesis around the regular expression are necessary? gawk and mawk are happy without them.

@manatwork: the inner ones are necessary, the outer one I prefer to have them to ensure the logic and evaluation order. .. maybe at the "cost" of 2 chars

bash, 105 bytes
And various other utilities, of course.
egrep -x '[wetyuio-r]+|[asdfghjkl]+|[zxcvbnm]+'|awk '{print length($0)"\t"$0;}'|sort -n|cut -f2|tail -n1

The awk code can be written shorter as $0=length"\t"$0.

MATL, 54 bytes
[]y"@Y:nh]2$SP"@Y:!t'asdfghjkl'mw'zxcvbnm'myy+~hhAa?@.

This works with current version (14.0.0) of the language/compiler.
Input format is (first example)
{'artist' 'home' 'gas' 'writer' 'geology' 'marine' 'twerp'}

or (second example)
{'wrhuji' 'bxnzmmx' 'gllwssjjd' 'vnccbb' 'lrkjhgfdsa' 'tttttt'}

Try it online!
Explanation
[]               % push empty array. Will be used for concatenation
y                % take input array implicitly at bottom of stack, and copy onto top
"                % for each string
  @Y:            %   push current string
  nh             %   get its length. Concatenate with array of previous lengths
]                % end for each
2$S              % sort the original copy of input array by increasing string length
P                % flip: sort by decreasing length
"                % for each string in decreasing order of length
  @Y:!           %   push that string as a column char vector
  t'asdfghjkl'm  %   duplicate. Tru for chars in 2nd row of keyboard
  w'zxcvbnm'm    %   swap. True for chars in 3rd row of keyboard
  yy+~           %   duplicate top two arrays, sum, negate: true for chars in 1st row
  hh             %   concatenate horizontally twice
  Aa             %   true if any column has all true values
  ?              %   if that's the case
    @            %     push string
    .            %     break for each loop
                 %   end if implicitly
                 % end for each
                 % display implicitly

Perl, 81 bytes

$a=$1 if/^([wetyuio-r]+|[asdfghjkl]+|[zxcvbnm]+)$/&&1<<y///c>$a=~y///c;END{say$a}

Symbol to letter count pretty high.

Groovy, 65 characters
{it.grep(~/[o-rwetyui]+|[asdfghjkl]+|[zxcvbnm]+/).max{it.size()}}

Sample run:
groovy:000> ({it.grep(~/[o-rwetyui]+|[asdfghjkl]+|[zxcvbnm]+/).max{it.size()}})(['wrhuji', 'bxnzmmx', 'gllwssjjd', 'vnccbb', 'lrkjhgfdsa', 'tttttt'])
===> bxnzmmx

Note that the regular expression used by .grep() not requires anchoring, allowing to spare the grouping too:
groovy:000> ['ab', 'ac', 'bc', 'abc', 'aca', 'bbc'].grep ~/[ac]+|b+/
===> [ac, aca]

K (ngn/k), 56 bytes
{x@*&|/&/''~^($`qwertyuiop`asdfghjkl`zxcvbnm)?\:x@:>#'x}

Try it online!

x@:>#'x sort the input (a list of strings) by their lengths, descending, updating x with the result
($`qwertyuiop`asdfghjkl`zxcvbnm) generate a list of strings representing which letters are present on each row of a qwerty keyboard
~^(...)?\:x check whether or not each letter of each input word is present or not in each keyboard line
&/'' determine if all letters of each input word are present in the same keyboard line or not
|/ check that there is at least one keyboard line containing all the letters of each input word
x@*& return the longest word in the input where the above criteria are met

Japt -h, 18 bytes
;k_£D·bøXuÃä¦ dÃñÊ

Try it
;k_£D·bøXuÃä¦ dÃñÊ     :Implicit input of array
 k                     :Remove elements that return true
  _                    :When passed through the following function
   £                   :  Map each character X
;   D                  :    "QWERTYUIOP\nASDFGHJKL\nZXCVBNM"
     ·                 :    Split on newlines
      b                :    Index of first element that
       ø               :      Contains
        Xu             :      Uppercase X
          Ã            :  End map
           ä           :  Consecutive pairs of characters
            ¦          :  Reduced by checking for inequality
              e        :  Any true?
               Ã       :End filter
                ñ      :Sort by
                 Ê     :  Length
                       :Implicit output of last element

Perl 5 -l, 75 bytes
map$a[y///c]=$_,grep/^([weo-rtyui]+|[asdfghjkl]+|[zxcvbnm]+)$/,<>;say pop@a

Try it online!

source: Stack Exchange

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

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

sort: votes


text:
Replace alias to form phrases
Inspired by the C-directive #define.
Challenge
Given one phrase with some alias, and one array with each alias text. Output the initial phrase replacing each alias with its respective text.
An alias is defined by one sharp # followed by its index in the array (the index may start at zero or one). Alias can contains another alias inside its text, and you must resolve all them (maybe recursively). You can assume the alias will never run into an infinite-loop. Alias won't have leading zeroes (#02 is not alias at index 2, it is alias at index 0 followed by the text 2).
You can assume the array will not pass 20 items in length.
You can write a program, or a function or even a #define-it would be nice :)
You can also use another input-method that fits better for your language.
Example
phrase: "#0 & #3"
array: [
    "Programming #1",
    "Puzzles",
    "Code",
    "#2 Golf"
]
output: "Programming Puzzles & Code Golf"

Step by step:
0> "#0 & #3"
1> "Programming #1 & #2 Golf"
2> "Programming Puzzles & Code Golf"

Since this is code-golf, shortest answer in bytes wins!
Another samples
phrase: "#0!"
array: [
    "We are #1",
    "#2",
    "#3",
    "#4 !",
    "graduating"
]
output: "We are graduating !!"

phrase: "##0#1#0#21#3#4"
array: [
    "a",
    "m",
    "z",
    "n",
    "g"
]
output: "#amaz1ng"

phrase: "##1#23"
array: [
    "WEIRD",
    "0 C",
    "AS"
]
output: "WEIRD CAS3"

phrase: "#1#7#6y#4#7#10s#7b#11#0#0#11r#7#0h#6#5#2#5#9#4."
array: [
    "t",
    "#12#3",
    "#11ga#3",
    "#0#10v#11",
    "#0h#10#8g",
    "#7#8",
    "a#8",
    " ",
    "n",
    "o",
    "i",
    "e",
    "P#9s#10"
]
output: "Positive anything is better than negative nothing."

The examples above used Array with index starting at zero.

If we use the 1-indexing option, do we not have to worry about the leading 0 thing becase #0 shouldn't appear? Or is #01 valid but not an alias (i.e. it just gets left in as is)?

@FryAmTheEggman. In that case you should just ignore #01

Easy with python for 0-9, mind blown trying to minimize 0-19 :D

There is a surprising amount of complexity hidden in what seems to be a simple problem.  Great question!

JavaScript (ES6) 58
Recursive function
f=(s,h,r=s.replace(/#(1?\d)/g,(_,x)=>h[x]))=>r==s?r:f(r,h)

Test

f=(s,h,r=s.replace(/#(1?\d)/g,(_,x)=>h[x]))=>r==s?r:f(r,h)

// Version without default parameters, same length but using a global
// f=(s,h)=>(r=s.replace(/#(1?\d)/g,(_,x)=>h[x]))==s?r:f(r,h)

console.log=x=>O.textContent+=x+'\n'

;[
  ['##1#23',['WEIRD','0 C','AS']],
  ["#0!",["We are #1","#2","#3","#4 !","graduating"]],
  ["##0#1#0#21#3#4",["a","m","z","n","g"]],
  ["##0#1#0#21#13#4",["a","m","z","","g","","","","","","","","","n"]],
  ["#1#7#6y#4#7#10s#7b#11#0#0#11r#7#0h#6#5#2#5#9#4.",
    ["t","#12#3","#11ga#3","#0#10v#11","#0h#10#8g","#7#8","a#8"," ","n","o","i","e","P#9s#10"]
  ],
  ["#0 & #3",["Programming #1","Puzzles","Code","#2 Golf"]]
].forEach(t=>{
  var a=t[0],b=t[1]
  console.log(a+' ['+b+']\n -> '+f(a,b))
})

I've added another test case with alias' index greater than 9.

Julia, 112 107 66 bytes
f(s,x)=(r=replace(s,r"#1?\d",m->x[1+parse(m[2:end])]))==s?s:f(r,x)

This is a recursive function that accepts a string an an array and returns a string. It uses 0-based indexing.
We begin by constructing a string r as the input string s with all matches of the regular expression #1?\d replaced with the element of x corresponding to 1 + the integer parsed out of the match. If this is equal to s, we return s, otherwise we recurse, passing r as the string.

Mathematica, 74 bytes
FixedPoint[#~StringReplace~a&,a=0;a=Reverse["#"<>ToString@a++->#&/@#2];#]&

Not too complicated. Most of it is just dedicated to creating the indices.

@WashingtonGuedes Fixed.

C, 269 232
#define f(p,a,l)char*n,o[999],i=0,c,x;for(strcpy(o,p);o[i];)o[i]==35&isdigit(o[i+1])?c=o[i+1]-48,c=isdigit(o[i+2])&c?10*c+o[i+2]-48:c,n=a[c<l?c:c/10],x=strlen(n),memmove(o+i+x,o+i+2+c/10,strlen(o+i)),i=!memmove(o+i,n,x):++i;puts(o);

As requested, a single #define solving the problem!  C macros can't be recursive, so the problem had to be solved iteratively.  The macro takes 3 arguments; the phrase p, the array a, and the length of the array l.  I only stripped whitespace from my ungolfed solution; I know there are a few more characters I can save, but I don't think it will get me below 200.  This will definitely not be a competitive solution.  Solution is fully golfed.  Ungolfed solution in the form of a function below:
f(char*p,char**a,int l){
  char o[999]={0},i=0;
  strcpy(o,p);
  while(o[i]){
    if(o[i]=='#'&&isdigit(o[i+1])){
      int c = o[i+1]-'0';
      if(isdigit(o[i+2])&&c)
        c=10*c+o[i+2]-'0';
      if(c>=l)
        c/=10;
      char *n=a[c];
      memmove(o+i+strlen(n),o+i+2+c/10,strlen(o+i));
      memmove(o+i,n,strlen(n));
      i=0;
    }else{
      i++;
    }
  }
  puts(o);
}

And test code:
void test(char *phrase, char **array, int length) {
  f(phrase, array, length);
}

main() {
  const char *t1[] = {
    "Programming #1","Puzzles","Code","#2 Golf"
  };
  test("#0 & #3", t1, 4);

  const char *t2[] = {
    "We are #1","#2","#3","#4 !","graduating"
  };
  test("#0!", t2, 5);

  const char *t3[] = {
    "a","m","z", "n","g"
  };
  test("##0#1#0#21#3#4", t3, 5);

  const char *t4[] = {
    "WEIRD","0 C","AS"
  };
  test("##1#23", t4, 3);

  const char *t5[] = {
    "t","#12#3","#11ga#3","#0#10v#11","#0h#10#8g","#7#8","a#8"," ","n","o","i","e","P#9s#10"
  };
  test("#1#7#6y#4#7#10s#7b#11#0#0#11r#7#0h#6#5#2#5#9#4.", t5, 13);
}

EDIT: Worked some golfing magic.  It's as about as short and unreadable as I think it can get.

Man, nice one!!! ... I would upvote it again if I could ;)

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


text:
Reverse an N-Dimensional array
Details
Write a function or program that, given an array (or list), containing only integers, returns or output an array with all sub-elements reversed. That is, reverse all elements of the deepest array, then the second deepest, etc. The dimensions need not be specified, but the function or program must work for jagged arrays in your programming language's native format.

Examples
This:
[[1,2], [3,4]]

Would become this:
[[4,3], [2,1]]

This:
[[[ 1, 2, 3], [ 4, 5, 6], [ 7, 8, 9]],
 [[10,11,12], [13,14,15], [16,17,18]],
 [[19,20,21], [22,23,24], [25,26,27]],
 [[28,29,30], [31,32,33], [34,35,36]],
 [[37,38,39], [40,41,42], [43,44,45]],
 [[46,47,48], [49,50,51], [52,53,54]]]

Would become this:
[[[54,53,52], [51,50,49], [48,47,46]],
 [[45,44,43], [42,41,40], [39,38,37]],
 [[36,35,34], [33,32,31], [30,29,28]],
 [[27,26,25], [24,23,22], [21,20,19]],
 [[18,17,16], [15,14,13], [12,11,10]],
 [[ 9, 8, 7], [ 6, 5, 4], [ 3, 2, 1]]]

This:
[[[1,2]],
 [[3,4], [5]],
 [[6,7,8], [9], [10,11]],
 [[[12,13], [14,15]], [16], [17,18,19,20]],
 [21]]

Would become this:
[[21],
 [[20,19,18,17], [16], [[15,14], [13,12]]],
 [[11,10], [9], [8,7,6]],
 [[5], [4,3]],
 [[2,1]]]

Bonus
This will hopefully encourage answers in some object-oriented programming languages...
-50% Bytecount If your program can take as input an array (or list) with its member's of various types (these can be in the form of objects) and successfully reverse all arrays.
This:
[["Foo",["Bar",1]],
  2,
 ["Baz"],
 [[["Qux"],3],3.14]]

Would become this:
[[3.14,[3,["Qux"]]],
 ["Baz"],
  2,
 [[1,"Bar"],"Foo"]]

In your bonus example, you treat strings as atoms. I would argue that they are sub-array, and thus should be reversed too. This is in fact what my APL solution does when fed normal strings, as APL does not have a string datatype, only character datatypes. Strings are therefore one-dimensional character arrays. If you want strings to remain in normal order, you just have to make them objects with a display form.

@Nᴮᶻ Do you believe that the -50% Bytecount is too generous? I may do something along the lines of -30% Bytecount for various data types, and something like -10% Bytecount for reversing Strings, -15% Bytecount for reversing an integer type (123 -> 321) and -15% Bytecount for reversing a floating type (3.14 -> 41.3).

I generally dislike bonuses. Reversing integers and floats is ... interesting.

Leave it for now, but next time, you may want to use the sandbox to figure out such things.

About bonuses...

For the bonus, what should happen for string input? Reverse? Don't reverse? Your choice?

@MrPublic If everything should be reversed i could write this Perl program: perl -p0e '$_=reverse;y/][/[]/'

I am making the decision to leave the question as-is, with only the current bonus. I will not add reversing strings, integers, or floats. I will admit, I should have asked about these in the Sandbox. Due to the number of answers already, the question will not be changed and left as-is.

Pyth, 11 - 50% = 5.5 bytes
L?+IbY_yMbb

Try it online: Demonstration or Test Suite.
This defines a function y. The additional 3 bytes <newline>yQ simply call the function with the input list and therefore doesn't need to be counted towards the bytes total.
Explanation:
L?+IbY_yMbb
L             define a function y(b), that returns:
 ?+IbY           if b + [] == b (test if b is a list):
      _yMb           recursively call y on all elements in b, then reverse the list
          b      else: b

Dyalog APL, 14 - 50% = 7 bytes
{∇¨⍣(×|≡⍵)⌽⍵}

⌽⍵ reverse argument
⍣(×|≡⍵) if the argument is not an atom (sign of the [absolute] depth)...
∇¨ ... apply the function to each element (of the reversed argument).
If ⎕ML←3 (IBM style), which is the case on systems that migrated from APL2, one byte can be saved by removing |.
Try APL online.
For curiosity, the proposed int and float reversing:
{∇¨⍣(×≡⍵){0::⌽⍵⋄⍎⌽⍕⍵}⍵}

The inner function:
0::⌽⍵ if any error occurs, just return the revesed argument
⍎⌽⍕ make into string, reverse, make into number

Prolog, 40 - 50% = 20 bytes
a(X,Y):-reverse(X,Z),maplist(a,Z,Y);X=Y.

This recursively calls predicate a/2 with maplist/3, for each member of the list, until reverse/2 fails (i.e. last element wasn't a list).

Python 2, 40 - 50% = 20
f=lambda x:map(f,x)[::-1]if"">x>[]else x

Only some minor modifications needed from the basic way to do it are needed to get the bonus. Uses the fact that all lists are less than the empty string, and all numbers are less than the empty list.
All test cases

Just a note that the version without the bonus is f=lambda x:map(f,x)[::-1]if x>[]else x.

Emacs Lisp, 46 bytes * 0.5 = 23
(defun g(x)(if(atom x)x(mapcar'g(reverse x))))

Usage example: (g '((1 2) 3 (four 5))) -> ((5 four) 3 (2 1))
Classic recursive approach: if the argument isn't a list, take it unchanged, if it's a list, map the function over the reverse of the list.

Mathematica, 34/2=17 bytes
Quiet[Reverse//@#]/.Reverse->(#&)&

Or just Reverse//@#& if you want a ton of errors and Reverses everywhere.

Clojure 43/2=21.5 bytes
(defn f[x](if(coll? x)(reverse(map f x))x))

Brachylog, 5 - 50% = 2.5 bytes
ċ↔↰ᵐ|

Try it online!
         The input
ċ        which is a list
 ↔       reversed
   ᵐ     with each element
  ↰      passed through this same predicate
    |    is the output. If the input isn't a list,
         it is the output.

Since ↔ can also reverse strings and integers, we have to explicitly fail non-lists with ċ.

Wolfram Language (Mathematica), 23 22 21 bytes
-50% bonus
#0/@Reverse@*List@@#&

Try it online!
Only works on nested Lists of atoms. Reverse a list, then reverse its elements. @@ and /@ are no-ops on atoms.

JavaScript ES6, 42 - 50% = 21 bytes
My score is perfect in so many ways. Implements a function r which recursively applies itself to the members of its input.
r=a=>Array.isArray(a)?a.reverse().map(r):a

If we assume no object has the property pop, then this becomes (31 - 50% = 15.5), thanks to dev-null:
r=a=>a.pop?a.reverse().map(r):a

Or, if we assume the object has a sane reverse property, we could do that as well (35 - 50% = 17.5):
r=a=>a[R="reverse"]?a[R]().map(r):a

I guess you could safely check for an array like this: a.pop?a.reverse().map(r):a. Assuming there is no need to handle void 0 and custom objects.

Lua, 111 99 * .5 = 55.5 49.5 bytes
function r(a)local t={}for i,v in next,a do t[#a+1-i]=type(v)=="table"and r(v)or v end return t end

Good bit of recursion

CJam, 20 bytes * 50% = 10
{_`0='[={W%{F}%}&}:F

Defines the named block F which can be applied to an array on top of the stack (or anything else, in which case it's a no-op).
Test it here.

Clojure, 38 bytes
(and a bonus I guess, but Clojure is a dynamic language so it comes for free)
(fn f[x](if(seq? x)(map f(into()x))x))

This is a good start but didn't employ these optimizations:

Define an anonymous function with fn instead of a named one with defn. But we still need a "scoped" name f for recursion
Take input as a list instead of vector, then we can use seq? instead of coll?
Use (into () ...) instead of reverse
Reverse x before mapping, we don't need as many spaces then

Clojure, 40 38 -50% = 19 bytes
(fn r[s](if(coll? s)(map r(rseq s))s))

Try it online!
A translation of the JavaScript answer. Matched the score with the best Clojure answer ;)

Haskell + free, 8.5 bytes (17 bytes -50% bonus)
In order to represent a ragged list in Haskell we use a free monad of lists.  We use the free library to get these free monads.
hoistFree reverse

Try it online!
Explanation
hoistFree takes a natural transformation from some functor \$F\$ to another functor \$G\$ and makes a natural transformation from \$\mathrm{Free}(F)\$ to \$\mathrm{Free}(G)\$.  Here the natural transformation is reverse, from lists to lists.
Because hoistFree must work with any natural transformation we know it must apply reverse exactly once to every sublist.  For example imagine we had a natural transformation:
newtype Reversed f a
  = Reversed (f a)

reverse' :: [a] -> Reversed [] a
reverse' =
  Reversed . reverse

This is functionally identical to reverse but the types prove it must be applied exactly once to every list.

Ruby, 32 - 50% = 16 bytes
Recursive function. Using rescue to catch the NoMethodError that triggers when trying to reverse a number or map a string turns out to be 2 bytes shorter than checking if the input is an array via a==[*a].
f=->a{a.reverse.map(&f)rescue a}

Try it online!

Julia 1.0, 27 -50% = 13.5
!x=x
!x::Array=reverse(.!x)

Try it online!


text:
Hilbert-Curvify a Matrix
Inspired by this question
Another way to unroll a 2D image into a 1D string is to use an Hilbert Curve.
There are many version of this curve, depending on the number of iterations used while computing it. Below follow example of Hilbert Curves from first order to fifth order.

The way of computing this curve is the following. First we define the first order Hilbert Curve as the one shown in figure (the one for n = 1), so that it fits in a 1x1 square. We than make four copies of this curve, spacing them in a 4x4 square, so that they all present the "concavity" towards the left side. We then flip the two leftmost order 1 curves, so that the top one concavity faces toward the top, while the bottom's faces the bottom. We finally connect the the corners of the adjacent Hilbert Curves. If wanting to obtain a (n+1)-order Curve, we just need to repeat the process with four n-order Curves. We can see a visualisation of the process here (I will also add an image detailing the process soon)
Your task in this challenge is to unroll a matrix of integers along the lowest order Hilbert Curve for that matrix.
For simplicity's sake, we will have the curve starting from the top left corner of the matrix.
You can receive the input either as a list of list of integers, where each
sub-list represents a row of the matrix.
You can assume that the input will be a square matrix (n*n).
For example:
Input:
[[ 1, 2,]
 [ 3, 4 ]]

Output:
[ 1, 2, 4, 3 ]

Since we are using the first order Hilbert Curve shown in figure
Input:
[[ 1, 2, 3, 4,    ]
 [ 5, 6, 7, 8,    ]
 [ 9, 10, 11, 12, ]
 [ 13, 14, 15, 16 ]]

Output:
[ 1, 5, 6, 2, 3, 4, 8, 7, 11, 12, 16, 15, 14, 10, 9, 13 ]

Using the second order Hilbert Curve
As usual, standard loopholes are not permitted.
This is code-golf, so the shortest answer in byte wins.

Related.

@StewieGriffin sure, I'm on it

@StewieGriffin I've added a brief summary, I'll do a more thorough job in the next hour or so, after finishing lessons

The matrix needs to not only be a square one, it also needs n to be a power of 2.

APL (Dyalog Unicode), 41 bytesSBCS
Saved 30 bytes (!) by consulting the wisdom of the APL Orchard, especially @ngn and @Sherlock9.

{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵}

Try it online!
Explanation as follows:
{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵} ⍝ Recursive function - takes input as an
                                          ⍝ n*n square matrix
 0::⍵                                     ⍝ Our base case - this is an error guard
                                          ⍝ If there's any error, catch it and
                                          ⍝ return the function's input
                                      ≢⍵  ⍝ Find the number of rows in the input
                                2 ¯2÷⍨    ⍝ Divide the above by 2 and negative 2,
                                          ⍝ resulting in a 2-element vector
                            ∘.,⍨          ⍝ Outer product - take the above vector and
                                          ⍝ apply concatenation (,) with each element
                                          ⍝ against all elements in the vector. Since
                                          ⍝ we have a 2-element vector, this results in
                                          ⍝ a 2-by-2 matrix, e.g.
                                          ⍝ [[(2,2),(2,¯2)],[(¯2,2),(¯2,¯2)]]
                        ↑∘⍵¨              ⍝ For each element in the matrix, we apply
                                          ⍝ "take" against our original input matrix.
                                          ⍝ Take, given a negative number, will take
                                          ⍝ elements from the end of a particular rank.
                                          ⍝ With our argument above, this means that we end
                                          ⍝ up with our original original input matrix
                                          ⍝ split by quadrant into a 2-by-2 matrix.
                                          ⍝ It is also worth noting that take expects
                                          ⍝ an integer argument, so for matrices whose
                                          ⍝ rowcount divided by two results in a decimal
                                          ⍝ (i.e., 1-by-1 matrices), we throw an error
                                          ⍝ which is caught by the guard above, returning
                                          ⍝ the original input.
                       ⌽                  ⍝ Flip the above matrix about the vertical axis.
                   ⊢∘⍉\                   ⍝ Apply a "monadic transpose scan". More details
                                          ⍝ on how this works below, but for our purposes
                                          ⍝ this applies transpose to each of the two
                                          ⍝ sub-matrices on the right half.
                ⌽@1                       ⍝ Swap the two upper sub-matrices. Given our
                                          ⍝ flip for the overall matrix above, this returns
                                          ⍝ the two upper quadrants to their original
                                          ⍝ positions.
               ,                          ⍝ Ravel: flatten the 2-by-2 matrix into a
                                          ⍝ 4-element vector
         ⌽∘⊖¨@4                           ⍝ Take the last element of the list (the lower
                                          ⍝ right quadrant originally) and flip it
                                          ⍝ along the vertical and horizontal axes. Given
                                          ⍝ the transposition above, this has the final
                                          ⍝ effect of transposition along the antidiagonal.
       ∇¨                                 ⍝ For each element in the above vector, recurse.
      ∊                                   ⍝ Recursively flatten the results into a single
                                          ⍝ vector.

More details on "monadic transpose scan".
Dyalog documentation on error guards.

MATL, 86 85 bytes
This solution is based upon Jonas Lundgren's File Exchange entry which utilizes complex numbers to generate the Hilbert curve. These complex numbers are then converted to index values to retrieve the elements of the matrix that fall along the curve.
nZl2/1XLJQXH1J-XI0,1L:"XJJZj1j*XKKH-JI-JH+IK-,4$h2/]XJJ1L*XJJH+J1)-XHGHXjHYj3$)1$Xd1$

Try it online!
Explanation
%--- Define some numbers to be used throughout ---%
n                   % Retrieve the number of elements in the input matrix
Zl2/                % Compute the order of the curve (log2(numel(i))/2)
1XL                 % Store the order in the 1L clipboard
JQ XH               % Store 1 + j in H clipboard
1J- XI              % Store 1 - j in I clipboard
0                   % Place 0 onto the stack

%--- Compute the hilbert curve ---%
1L:"                % For k = 1:order
    XJ                   % Store the top of the stack (z) in J clipboard
    JZj                  % Compute the conjugate of z (stored in J)
    1j*                  % Multiply by j to get conj(z) * j
    XK                   % Store result in K clipboard
    KH- JI- JH+ IK- 4$h  % Horizontal concatenation of K-H, J-I, J+H, and I-K
    2/                   % Divide entire array by 2
]                   % End for loop
XJ                  % Store z in J clipboard

%----- Convert complex decimal values to complex integer indices ----%
J1L*                % Multiply z by the order
XJ                  % Store result in clipboard J
JH+                 % Add 1 + j to H
J1)-                % Subtract the first element of z
XH                  % Store integer complex numbers in H

%--- Retrieve the elements from the input along the curve ---%
G HXj HYj 3$)       % Index into input using real/imag components input(real, imag)
                    % This will yield an numel(real) x numel(imag) matrix where
            % the diagonal values are the values we want
1$Xd                % Extract the diagonals using diag with one input
1$                   % Display only the top element on the stack

@DonMuesli I'm working on a better way to handle this. It's definitely far from elegant! Thanks for the pointers. Updated!

I haven't looked into this specific challenge. Sometimes clipboards can't be avoided

Python 3, 327 289 275 271 239 234 bytes
This is a solution I modified from my answer for another Hilbert curve question here. Any golfing tips are appreciated.
Edit: Changed how g is incremented and decremented. Now using eval() and str.translate. No longer using l=len(s).
def h(s):
 t=[s[0][0]];x=y=g=0;b="A"
 for j in range(len(bin(len(s)))-3):b=b.translate({65:"-BF+AFA+FB-",66:"+AF-BFB-FA+"})
 for c in b:g+=(c<"-")-(c=="-");a=c>"B";x,y=[[x,y],[[x+1-g%4,y],[x,y+g%4-2]][g%2]][a];t+=[s[x][y]]*a
 return t

Ungolfed:
# the following function is implemented in the code with b=b.translate

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def matrix_to_hilbert(mat):
    length = len(mat)       # this returns the number of rows in the matrix
    if length < 2:
        return mat
    it = len(bin(length)) - 3
    hil = hilbert(it)
    output = [mat[0][0]]    # a list that starts with the first element of the matrix
    x = 0
    y = 0
    heading = 0
    for char in hil:        # navigating the Hilbert curve
        if char == "-": heading += -1
        elif char == "+": heading += 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output.append(mat[x][y])
    return output

Mathcad, 302 bytes
The Mathcad program below is based on the @Sherlock9 Python program.  It differs by curvifying rectangular matrices by ignoring those parts of the Hilbert Curve that lie outside of the matrix bounds.  Note that as Mathcad has relatively poor string handling, I've mapped the Lindenmayer symbols to integers in the Hilbert function.

Mathcad works through a 2D interface that allows the user to place (and freely mix) mathematical expressions, plots, text, inputs and outputs.   I've equated a byte to the minimum user keyboard equivalent operation to create a symbol (for example, the definition operator (:=) is entered by simply typing :.

Uiua, 36 bytes
⊏⍏∩♭⍥(⊂∶¯+¬×2⧻♭.⇌.≡⊂⊃⍉+∶⧻♭.)ₙ2⧻,↯1⇡1

Try it online!
Constructs the path on the matrix directly, and uses it to index into the matrix.
⊏⍏∩♭⍥(⊂∶¯+¬×2⧻♭.⇌.≡⊂⊃⍉+∶⧻♭.)ₙ2⧻,↯1⇡1    input: matrix M of size 2^n*2^n
↯1⇡1    the initial Hilbert matrix [[0]]
ₙ2⧻,    log 2 of the length of M (= n)
⍥(...)   repeatedly construct the Hilbert matrix by calling the inner function n times...
  ∶⧻♭.   put the number of elements in the current matrix under itself
  ⊃⍉+   construct the top two submatrices: 1) transpose 2) add to each element
  ≡⊂     join horizontally
  ⇌.     create a copy and reverse its rows
  ¯+¬×2⧻♭.  a bunch of arithmetic to get the bottom two submatrices
  ⊂∶      join vertically in reverse
∩♭    flatten the Hilbert matrix and M
⊏⍏    put the elements of M in the increasing order in the Hilbert matrix

Uiua, 41 bytes
⊡⍉∧(≡⊂∶⍜⊢-≡⇌,-1×2∶≡⊂∶⇌⍜⊢+,,⇌)↯2⇡1ⁿ∶2⇡ₙ2⧻.

Try it online!
Constructs the list of coordinates and indexes into the original matrix using ⊡ "pick".

Wolfram - 233
Based on representation as Lindenmayer system:
f[m_]:=m[[Sequence@@Reverse[#+1]]]&/@DeleteDuplicates@AnglePath[Pi/2,List@@StringReplace[Last@SubstitutionSystem[{"A"->"-BF+AFA+FB-","B"->"+AF-BFB-FA+"},"A",Round@Sqrt@Length@m],{"A"|"B"->"","-"->{0,-Pi/2},"+"->{0,Pi/2},"F"->{1,0}}]]

Could you post some screenshots of it working, for users who don't have Mathematica?

Is "Wolfram" different than Mathematica? If not, it should be called Mathematica.

@WizardOfMenlo Here it is working online

@swish I think you need to change the permission of the Web app, it seems to be blocked

@mbomb007 Wolfram is the name of the language, Mathematica is like an IDE.

@WizardOfMenlo I don't think so, I can access it from new private window without signing in.

@swish, weird, from my laptop it doesn't seem to make me access, I've tested it with my desktop version and it works, +1

@swish But everyone else posts it as "Mathematica". That's even what Martin called it on the showcase your language challenge.

@mbomb007 I guess it's just a habit to call it like Mathematica. But it should be called Wolfram starting of November 2013, check this article

What's a representaion? Is it like a representation?

##& is equivalent to Sequence

Ruby, 224 221 216 bytes
This answer is based on my Python answer.
->s{t=[s[0][0]];x=y=g=0;b=?A;(s.size.bit_length-1).times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};b.each_char{|c|g+=c==?-?-1:c==?+?1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t<<s[x][y])if c==?F};t}

Ungolfing:
def hilbert(mat)
  result = mat[0][0]
  x = 0
  y = 0
  heading = 0
  b = "A"
  (mat.size.bit_length-1).times do each |j| # Hilbert curve using a Lindenmayer system
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  b.each_char do |char| # navigating the matrix
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
      result << s[x][y]
    end
  return result
  end

CJam, 60
Lq~:A,2mL{:B1f^0B1B2B3f^]:+}*1+{AT=U=\2md'U^_~)@2*-':@+~;}%p

Try it online
Explanation:
I'm building the fractal as a series of movement directions: 0=right, 1=down, 2=left, 3=up.
L          push an empty array (level 0 fractal)
q~:A       read the input, evaluate and store in A
,2mL       get the length (number of rows) and calculate the logarithm in base 2
            (to get the desired level)
{…}*       repeat <level> times
  :B       store the previous-level fractal in B
  1f^      XOR it with 1 (top-left part)
  0        (move right)
  B        copy the fractal (top right part)
  1        (move down)
  B        copy the fractal (bottom right part)
  2        (move left)
  B3f^     copy the fractal and XOR it with 3 (bottom left part)
  ]:+      put everything in an array and concatenate the parts
1+         add a dummy move (needed for the last step)
{…}%       apply to each direction in the array
  AT=U=    push A[T][U] (T and U are initially 0)
  \2md     bring the direction to the top and get the quotient and remainder mod 2
  'U^      XOR the 'U' character with the remainder,
            to get the variable we want to modify
  _~)      make a copy of it, then evaluate it and increment
  @2*-     bring the quotient to the top, multiply by 2 and subtract
  ':@+     concatenate ':' with the variable name
  ~;       evaluate (this updates the variable) and pop the result
p          pretty-print the resulting array


text:
Creating a falling ball map
Introduction
For the ones who never heard of this game before. You are playing a ball which needs to survive as long as possible. This is done by moving to the left or right, going to the holes. Since the map moves upwards, you need to go downwards to survive longer. If you search for images, you probably know which game I mean.
The Task
Given a positive integer n, output a falling ball map of n layers. Between the layers, there are 4 newlines. The width of the layer is made up of 25 underscore characters, with one hole of length 5. That means that the total width is equal to 30. This is randomly shifted after each layer. An example of a valid layer is:
_______________     __________

The hole can also be at the edges, as if the layer is like a cylinder:
  _________________________

Note that there are 2 leading spaces and 3 trailing spaces. Making a single hole of width 5.
Test cases
For n=4, this is a valid output:
_______________     __________

______     ___________________

_______________________     __

  _________________________

Note: the holes must be uniformly distributed. Trailing and/or leading newlines are allowed.
This is code-golf, so the submission with the least amount of bytes wins!

@DonMuesli Haha, that can happen to anyone :p

Pyth, 19 bytes
VQ.>+*\_25*d5O30*b4

Try it here!
Explanation

VQ.>+*\_25*d5O30*b4  # Q = input

VQ                   # Repeat Q times
     *\_25           # 25 underscores
          *d5        # 5 spaces
    +                # concat the underscores and spaces
  .>         O25     # rotate this string 0-29 times
                *b4  # print the seperating newlines

Ruby, 74 71 59
Thanks to Alex A. for reminding me that being basically one line means I can use the stabby lambda
f=->n{n.times{puts (('_'*25+' '*5)*2)[rand(30),30]+"\n"*5}}

puts adds a newline to the end (while Ruby's print doesn't), so it's been updated to 5 newlines.

All hail the times function for saving me 3 bytes over the for loop :D

57 bytes: ->n{n.times{puts (('_'*25+' '*5)*2)[rand(30),30]+"\n"*5}} Try here

You don't need to assign the lambda as part of the submission since we don't require functions to be named.

But then how am I supposed to call the function?

You can do (->n{n.times{puts (('_'*25+' '*5)*2)[rand(30),30]+"\n"*5}})[input] or just specify that you need to assign it in order to call it. This is quite common on the site.

Pyth, 19 bytes
VQ.>r"5 25_"9O30*4b

Try it here
Thanks to FryAmTheEggman for catching a bug.

@AandN FryAmTheEggman is right, I have changed it to be randomly shifted by 0-29 characters instead of 0-25.

Julia, 72 bytes
n->join([join(circshift(["_"^25*" "^5...],rand(1:30)))"\n"^5 for i=1:n])

This is an anonymous function that accepts an integer and returns a string. To call it, assign it to a variable.
We construct a string of 25 underscores followed by 5 spaces, then splat that into an array of characters. We circularly shift it a random number of times (between 1 and 30), join it back into a string, and tack on 5 newlines. This process is repeated n times, where n is the input. The resulting array is joined and returned.
Try it here

PowerShell 65 Bytes
0..$args[0]|%{-join("_"*25+" "*5)[($r=Random 25)..($r-29)];,""*5}

Run a loop for n iterations. Get a random number and make a underscore string with 5 spaces at the end. Index into the the string as an array to pull starting from a random location. Negative indexing wraps from the end. Join that back up again and append 5 newlines.
Edit: I don't know why I thought I needed the parameter for -Maximum as it's positional. Thanks to TimmyD I shaved some bytes and forgot to get input so that drove me back up to 65.

@TimmyD I would be surprised if anyone still had 1.0. It was only available as a download and was not shipped with any OS. 2.0 should be considered the norm.

@TimmyD I do agree with that point just not where PowerShell 1.0 is concerned. If anyone is on this site using using that it would surprise me. If I used a 3.0 or higher feature I would highlight that for sure.

MATL, 23 bytes
:"95l25X"5Z"h30YrYS10ct

Try it online!
Explanation
:"           % take input n implicitly. Repeat loop n times
  95l25X"    %   row vector with number 95 ('_') repeated 25 times
  5Z"        %   row vector of 5 blank spaces
  h          %   concatenate vertically
  30Yr       %   random number uniformly distributed on [1,2,...,30]
  YS         %   circularly shift
  10c        %   newline character. Includes another newline when printed
  t          %   duplicate
             % implicitly end loop and display stack contents

Java, 177 140 bytes
-1 byte to Blue moving the i++
-2 bytes to me leaving meaningless whitespace in the original
-34 bytes to Blue for realizing I didn't need the char[] at all
Because, ya know, Java.
n->{String s="";for(;n-->0;){int r=(int)(Math.random()*30);for(int i=0;i<30;){s+=i>r&i<r+6|r>24&i++<=r%25?" ":"_";}s+="\n\n\n\n";}return s;}

Slightly ungolfed:
Function<Integer, String> fallingBall = n -> {
    String s = "";
    for (;n-->0;) {
        int r = (int)(Math.random()*30);
        for (int i=0; i<30; i++) {
            s += i>r&i<r+6|r>24&i<=r%25?" ":"_";
        }
        s += "\n\n\n\n";
    }
    return s;
}

Since Java doesn't have a String 'rotate', I had to take a different approach. I generated a random int 0-29 that represents the start index of the hole (OBO because > is shorter than >=). Each individual character is then decided by the logic
l[index] = (index>random && index<random+6) || (random>24 && index<=random%25) ? ' ' : '_';

This handles the "wrapping" nature of the whole.

By putting the i++ the last place i is used, you can save a byte.

Smart. Hacky, but smart. Smarter still is me somehow leaving meaningless whitespace at the beginning of my snippet (s = ""). Both are fixed now.

You can also save a bunch more by getting rid of the char array, change the char literals to string literals, and use s+= in the inside for loop. I just tested it

Btw great answer

That's what I get for focusing on one way to do it. -34(!) bytes.

SpecBAS - 93 bytes
1 a$="_"*25+" "*5: INPUT n: FOR i=1 TO n: r=1+INT(RND*30): ?a$(r TO)+a$( TO r-1)''''': NEXT i

Makes a string of 25 underscores + 5 spaces, picks a random start point and splices the string at that position and tacks the start of string to end.
The apostrophe forces a newline, so 1 at end of string and 4 empty lines.

Python, 119 103 bytes
import random
s='_'*20+' '*5
def f(n,a=random.randint(0,25)):[print(s[a:]+s[:a]+3*'\n')for _ in' '*n]

Your latest update doesn't work because you've put the random in a default argument, so the function will always output the same row n times

Python 3.5 - 109 113 bytes (+4 for printing out 4 new lines between each result):
def g(a,j='_'*25+' '*5):
 for l in range(a):import random;n=random.randrange(len(j)+1);print(j[-n:]+j[:-n]+'\r'*4)

Ungolfed Form:
# j is the starting string with the 25 underscores and then 5 spaces at the end
def g(a,j='_'*25+' '*5):
    import random #Import the random module
    for l in range(a): # Do the following as many times as provided by the user
        n=random.randrange(len(j)+1) Get a random number in the range 0-29
        print(j[-n:]+j[:-n]+'\r'*4) #Shift the string characters right "n" times and print out the results with 4 new lines in between

Basically what is going on is that a string 'j', consisting of 25 underscore followed by 5 spaces, is given as an argument to the function "g". Then, the random module is imported, and, as many times as specified by the user, a random number is chosen in the range 0 => 29, and the string, "j", is shifted right that many times. The result is then printed out after each iteration, with 4 new lines in between each result.

Does this also print the newlines in between?

@AandN Now it does. :)

You actually need to print 4 newlines :p. So changing '\r' to '\r'*4 should probably work. Also, I think you can change range(a+1) to range(a).

@AandN Actually,  using range(a) actually prints out a-1 number of lines, so range(a+1) is the best way to print out the exact number of lines the user provides. Also, it now prints 4 new lines in between each result.

Hmmm, that is weird, because I tested this with g(5) and it prints 6 strings instead of five, so changing a+1 to a would probably fix that.

@AandN Actually, I just tested it right now, and you're right! I actually  forgot that, even though it starts from 0 and goes up to 9, that's still 10 numbers. Therefore, I have now corrected by golfed code. It should work perfectly now. :)

That saves 2 bytes :). It's a very nice answer!

@AandN Thanks! I really appreciate that!


text:
Roman Numeral Line Segments
Write a program or function that accepts an integer in the range 1..3999 as input and returns the number of line segments required to express that integer in standard Roman numerals (so you would use XL but not VM). Examples:
   1 -> 1
   4 -> 3
   5 -> 2
   9 -> 3
  10 -> 2
  40 -> 4
  50 -> 2
  90 -> 3
 100 -> 1
 400 -> 3
 500 -> 2
 900 -> 5
1000 -> 4

Roman number conversion builtins are permitted, but you can solve the problem without them by repeatedly subtracting the largest remaining number from the above list. Example: 1234 = 4 + 1 + 1 + 2 + 2 + 2 + 3 = 15.
This is code-golf, so the shortest program wins.

Why is 10 two line segments instead of four? When writing X, you'd typically only write two lines, but doesn't the intersection of the lines make it four segments?

@AlexA. The definition of line segment is usually something like: "The set of points following the shortest path between two points". There doesn't seem to be any reason to cut X based on this, you only need two sets of end points to define it. (Assuming Romans primarily wrote on euclidean geometries, I guess)

@FryAmTheEggman Hm okay. Good to know, thanks.

Pyth, 92 76 70 bytes
KsMc."/9hæ²z³Þ§ªW×Oû[Tnè,O¤"\/WQ=Q-Q=Nef!>TQ%2K aY@KhxKN;sY

Try it here!
Thanks to @FryAmTheEggman for some string packing suggestions which saved me some bytes!
I am still wondering if there is a mathematical way of encoding this list. Will try to figure something out.
Explanation
This uses the given algorithm. K contains the given list with the numbers and the corrosponding number of line segments in alternation. This list gets constructed by splitting a packed string, which gets decoded to 0/0/1/1/4/3/5/2/9/3/10/2/40/4/50/2/90/3/100/1/400/3/500/2/900/5/1000/4, on / and mapping each element to an integer.

KsMc."..."\/WQ=Q-Q=Nef!>TQ%2K aY@KhxKN;sY    # Q = input

   c."..."\/                                 # split the string on /
KsM                                          # map every number to int and assign to K
            WQ                               # while Q != 0
                     f    %2K                # only take every 2nd element of K and filter with T
                      !>TQ                   # T <= Q
                  =Ne                        # Take the last element of that and assign that to N
              =Q-Q                           # Q = Q - N
                                   xKN       # index of the first occurence of N in K
                                  h          # increment that index because we want the line segments
                              aA@K           # get the line segment from that index and append that to Y
                                      ;sY    # end the loop and print the sum of all line segments in Y

C, 148 129 chars
d,x,n[]={1000,900,500,400,100,90,50,40,10,9,5,4,1,4,5,2,3,1,3,2,4,2,3,2,3,1};f(c){while(d+=(c/n[x])*n[x+13],c%=n[x++]);return d;}

My first code-golf :^). Since the question states I can use a function, I have changed main to a function to trim some chars (most importantly: pass c as parameter rather scanf)
unpacked
d,x,n[]={1000,900,500,400,100,90,50,40,10,9,5,4,1,4,5,2,3,1,3,2,4,2,3,2,3,1};
f(c){
  while(d+=(c/n[x])*n[x+13],
        c%=n[x++]);
  return d;
}

Mathematica, 80 72 bytes
Tr[Characters[#~IntegerString~"Roman"]/.{"I"|"C"->1,"M"->4,_String->2}]&

Anonymous function that just converts numbers to Roman numerals, replaces each character with its number of segments, and takes the total.

Retina, 128 bytes
.+
$*
1{1000}
t'
1{900}
td
1{500}
d
1{400}
t
1{100}
'
1{90}
t
1{50}
d
1{40}
t'
1{10}
d
1{9}
t
1{5}
d
1{4}
t
1
'
t
d'
d
''
'+
$.0
Simple replacing until there's nothing left to replace. Then the apostrophes are counted and that's our number of line segments.
If input and output in unary are allowed, it's 115 bytes (although who would want to type 1234 ones?).
Try it online!
Try it online! (unary IO)

Python 3, 95 bytes
def f(a,b=0):
 for e in'᝴ᔝ஺ॣəȟĮô>9 ':e=ord(e);d=e//6;b+=a//d*(e%6);a%=d
 return b

The Unicode string consists of the code points:
6004 5405 3002 2403 601 543 302 244 62 57 32 27 7

If you turn that string into a byte literal you can omit e=ord(e);

I don’t think that works in my case. I need a Unicode string :( i.e. I’m looping over the codepoints in that string, not over the bytes.

Oh, I see. Do you mind providing a hex dump of the string? It isn't displayed properly on my phone.

JavaScript (ES6), 79 bytes
n=>"0123323453"[[,a,b,c,d]=1e4+n+'',d]-(-"0246424683"[c]-"0123323455"[b])+a*4

The strings represent the number of line segments for the units, tens and hundreds digits. (Thousands is simply four times the thousands digit.) This method seems to be shorter than other options such as the algorithm suggested in the question.
Edit: Saved 2 bytes thanks to @user81655.

This is a cool algorithm. Rearranging the casts can save 2 bytes as well: n=>"0123323453"[[,a,b,c,d]=1e4+n+'',d]-(-"0246424683"[c]-"0123323455"[b])+a*4

@user81655 Oh, that's nice: simply changing the +s to -s allows me to remove the leading +, but then the grouping saves another byte.

Java, 152 bytes
Because, ya know, Java.
n->{int c=0;int[]r={999,4,899,5,499,2,399,3,99,1,89,3,49,2,39,4,9,2,8,3,4,2,3,3,0,1};for(int i=0;i<26;i+=2)while(n>r[i]){n-=r[i]+1;c+=r[i+1];}return c;}

Simple literal implementation of the given algorithm. Array packs the transform information: even indexes are one less than the roman numeral and odd indexes are the count for that numeral.
This is a lambda that takes and returns an int/Integer. This includes IntUnaryOperator or UnaryOperator<Integer>.


text:
Crack the Cipher
Write a program or function that will break ciphers, using as few bytes as possible.
Task
Given an encrypted message and a dictionary as input, output the decrypted message. The messages will be encrypted using a one-to-one character mapping, i.e. two characters can't both map to one, and vice versa. The message will only include words from the dictionary.
Input
Take as input an encrypted message and a dictionary of words. The input can be taken in any form you like, however the preferred input is the message as a string and the dictionary as either a new-line deliminated string, an array or the file path of a file containing one word per line.
Output
Output the decrypted message in any format you like (although human-readable is preferred). The output must only contain words from the message.
Examples
These examples assume that the dictionary given is an English dictionary, such as the one included in Linux:
TLW EYQMA HJUIP BUN VYKZWR UDWJ TLW FCXS RUG FCOT IWWAWPR HYT TLWP PUTQMWR TLCT TLQO OWPTWPMW PWWRWR CRRQTQUPCF IUJRO TU HW WCOQFS BQNWR OU TLW BUN COAWR TLW RUG TU GWT CPUTLWJ OWPTWPMW, CPR ILWP TLW RUG JWBYOWR TLW BUN MJWCTWR UPW QPOTWCR
the quick brown fox jumped over the lazy dog last weekend but then noticed that this sentence needed additional words to be easily fixed so the fox asked the dog to get another sentence and when the dog refused the fox created one instead

VMXIBKGVW GVCG RH HLNVGRNVH XIVZGVW YB IVKOZXRMT LMV OVGGVI YB ZMLGSVI GSRH GVCG GVHGH BLF GL VMHFIV BLF XZM IVKOZXV HLNV LI ZOO LU GSV OVGGVIH RM GSV GVCG DRGS IVKOZXVNVMG OVGGVIH
encrypted text is sometimes created by replacing one letter by another this text tests you to ensure you can replace some or all of the letters in the text with replacement letters

Related

Related.

This is not a duplicate; that one has a hard-coded dictionary, this one uses an external dictionary.


text:
Distinct subsets that sum to a given number
Write a function that gets as an input a sorted array of positive numbers A, and an additional number n. The Task is to print out all distinct subsets of A, that sum to n.
Example:
Input:
A = [1,2,2,4,4]
n = 9

Output:
[1,2,2,4]
[1,4,4]

Bonus:
-50% if your code doesn't store duplicate subset (the same subset but in different order) intern. The function will not store more than one duplicate subset in memory at a time.
Shortest code in bytes wins.

Are duplicates allowed in the output?

What do you mean by "store"? Will input numbers always be positive integers?

store for example would be: to iterate over all subsets and store in a big array all feasible subsets and then remove all redundant ones.

If duplicates are stored, can they be produced in the output? Or do they need to be removed before displaying?

No only the distinct subsets should be displayed.

If a duplicate is generated, checked for uniqueness and then discarded, does that qualify for the bonus? The duplicate needs to be temporarily stored somehow. Perhaps the bonus rule could be more precise saying at most one duplicate can be present at any time?

yes that is what i meant. i will add it.

Bonuses are generally discouraged in [tag:code-golf]. I suggest that you decide on a single version of the challenge (bonus either required or not).

Pyth, 6
@yE./Q

Try it online
We get all of the subsets of the given list with yE, and then ./Q gets all of the integer partitions (lists of integers that add up to it) of the other input. @ Finds the intersection of the two sets.

Julia, 89 82 72 bytes
f(x,n)=partitions(n)∩foldl(vcat,[collect(combinations(x,i))for i=1:n])

This is a function that accepts an array and an integer and returns an array of arrays. It uses the same approach as FryAmTheEggman's clever Pyth answer and doesn't qualify for the bonus.
We get all combinations of the elements of x of size i for i in 1 to n, and take the intersection of this with the integer partitions of n. The resulting array is the set of combinations which are also partitions of n, i.e. those that sum to n.

Pyth, 9 - 50% = 4.5 bytes
f!.-TQ./E

Try it online: Demonstration
Got a little bit inspired by Fry.
Explanation:
f!.-TQ./E   implicit: Q = input list
      ./E   read a number from input and compute a list of partitions
f           filter for partitions T, which satisfy:
  .-TQ         remove the numbers in Q one by one from T
 !             check if the resulting list is empty
               (and therefore the partition is a subset of Q)

It seems a bit odd to claim the bonus when the integer partitions contain all of the subsets of the list that sum to the input, but I think that's the rather unclear bonus' fault...

JavaScript (ES6) 115
Using an hash table to store results, no duplicate is ever stored. But I doubt that this is what OP means for the bonus, so I will not claim it.
(A,n)=>[...Array(1<(x=A.filter((v,i)=>1<
[...Array(1< ( // build the current subset in x using bit mask
         // meanwhile, check if the elemnt sum is == n
    t = n,
    x = A.filter( (v,i) => 1<[...Array(1<(x=A.filter((v,i)=>1<<i&m&&(t-=v,1),t=n),t||++s[x]),s={})&&Object.keys(s)

function go() {
  var a = A.value.match(/\d+/g)
  var n = +N.value
  O.textContent = f(a,n).join('\n')
}

go()
Array A <input id=A value='1 2 2 4 4'>

Value n <input id=N value=9>

<button onclick='go()'>Go</button>

Perl 6, 50 bytes - 50% = 25
{@^a.combinations.unique(as=>~*).grep: *.sum==$^n}
Ungolfed
sub d (@a,$n) {
    @a.combinations.unique(as => ~*).grep: *.sum == $n
}

Perl 6 has a built in combinations operator (as well as one for permutations!). Both of these return a lazy list.
unique by itself would not return unique combinations, because technically they are not unique (they are equivalent) so we tell unique to compare them as strings (~$var coerces $var to a string, and * means Whatever)
Then we grep for Whatever.sum is equal to n; Result of last evaluated expression is returned by default
Lastly, if I don't define a signature, I can use $^var to refer to a passed variable. Alphabetical (Positional) order matters with these, as $^a is passed in before $^b;

You can shave a couple bytes by using some routines instead of some of the methods, {grep *.sum==$^n,unique as=>~*,@^a.combinations}

Haskell, 54 * 1.0 76 bytes * 0.5 = 38
import Data.List
f n=foldl(\r e->r++[e|notElem e r,sum e==n])[].subsequences

Usage example: f 9 [1,2,2,4,4] -> [[1,2,2,4],[1,4,4]].
Brute force: check every subsequences, keep it if it has the right sum and has not been seen before. subsequences build the list of subsequences lazily, i.e. one after the other, so at most one new element is kept in memory together with all unique elements so far.
For reference the previous version with the built-in function to remove duplicates, which requires to build the whole list of subsequences in memory. 54 bytes, no bonus.
import Data.List
x#n=nub[y|y<-subsequences x,sum y==n]

MATL, 26 * 0.5 = 13
x{}FTinZ^!"0$G@)s=?2MVJX(u

Works with current version (14.0.0) of the language/compiler.
EDIT (June 10, 2016): The link below replaces J by JQ to adapt to recent changes in the language
Try it online!
Explanation
All possible subsets are tested to see if the sum is correct. For each subset, if the sum condition is satisfied the subset is stored in a (cell) array. Immediately after that, duplicates are removed (the only possible duplicate at this point is the newly added array, and in that case it is removed). So this gets the bonus.
x        % take number input implicitly. Delete (gets copied into clipboard G)
{}       % push empty cell array. Will be grown with the found subsets
FT       % push array [false, true]
in       % take array input. Push its length
Z^!      % Cartesian power. 2D array in which each column indicates (via
         % logical indexing) which elements of the input array form a
         % subset. This covers all possible subsets.
"        % for each column
  0$G    %   push the two inputs: number, then array
  @)     %   apply logical index to extract the current subset
  s      %   compute its sum
  =      %   are they equal?
  ?      %   if so
    2M   %     push the subset again
    V    %     convert numbers to string. Needed to test for uniqueness
    JX(  %     append that to the cell array that stores the subsets
    u    %     remove duplicates (the only possible duplicate is the
         %     newly appended subset)
         %   end if implicitly
         % end for each implicitly
         % display implicitly

Pyth, 8 bytes
{fqsTQyE

No bonus.
{ f         Unique elements of filter lambda T:
    q                     equals
      s T                        sum of T
      Q       First input
    y E    over all subsets of second input

Try it here.

Ruby, 73 bytes
->x,n{(1..n).flat_map{|i|x.combination(i).select{|c|eval(c*?+)==n}.uniq}}

This is a lambda function that accepts an array and an integer and returns an array of arrays. To call it, assign it to a variable, say f, and do f.call(x, n).
For each i from 1 to n, we get all combinations of size i of the elements of x, select those combinations c such that c sums to n, and take the unique elements.
Try it here

Brachylog, 39 bytes
:1fd.,{,.[L:N]hs?{_,0 .|b:2&I,?h+I=.}N}

Called with a list containing the list of numbers first and the value of the sum second.

05AB1E, 8 bytes
Uses CP-1252 encoding. Code:
æÙvyO²Q—

Try it online!

PHP, 162 - 50% = 81 bytes
function c($a,$n){$o=[];for(;++$i<pow(2,count($a));){$s=[];foreach($a as$x=>$e)if($i&pow(2,$x))$s[]=$e;if(array_sum($s)==$n&&!in_array($s,$o))$o[]=$s;}return$o;}

Without a powerset built in this was kind of a pain.
for(;++$i<pow(2,count($a));)                    #generate integers
foreach($a as$x=>$e)if($i&pow(2,$x))$s[]=$e;    #use integers to generate subsets
if(array_sum($s)==$n&&!in_array($s,$o))$o[]=$s; #conditionally add suset to output

the rest is just necessary initialisation and output

Jolf, 9 bytes, noncompeting
I had to do some bugfixes, ergo, invalid :( Try it here anyhow!
ψmψxd=uHj
 mψx      unique powerset of input array
ψ   d     filtered according to a function
     =uH   that tests if the sum of the member
        j  is the input number.

Test like
[1,2,2,4,4]

9

Oracle SQL 11.2, 199 bytes
SELECT DISTINCT s FROM(SELECT SYS_CONNECT_BY_PATH(TRUNC(i),'+')s FROM(SELECT''||COLUMN_VALUE+ROWNUM/100 i FROM XMLTABLE((:a)))START WITH i>0 CONNECT BY i>PRIOR i),XMLTABLE(s)WHERE''||column_value=:n;

Inputs are :
:a the array of positive numbers, formated like "1","2","3","3"
:n the target number
Un-golfed :
SELECT DISTINCT s
FROM  (
        SELECT SYS_CONNECT_BY_PATH(TRUNC(i),'+')s
        FROM   (
                 SELECT ''||COLUMN_VALUE+ROWNUM/100 i
                 FROM   XMLTABLE((:a))
               )
        START WITH i>0 CONNECT BY i>PRIOR i
      ), XMLTABLE(s)
WHERE ''||column_value=:n;

Mathematica, 33 bytes
Cases[{}⋃Subsets@#,s_/;Tr@s==#2]&

Mathematica, 57 bytes (-50%) = 28.5 bytes
Cases[Fold[Append@@@Thread@{##}⋃#&,{{}},#],s_/;Tr@s==#2]&

J, 28 bytes
~.@((=+/@>)#])]<@#~2#:@i.@^#

Generates the power set and filters it before removing duplicates.
Usage
Since J does not support ragged arrays, each subset is output within a box.
   f =: ~.@((=+/@>)#])]<@#~2#:@i.@^#
   9 f 1 2 2 4 4
┌─────┬───────┐
│1 4 4│1 2 2 4│
└─────┴───────┘

Explanation
~.@((=+/@>)#])]<@#~2#:@i.@^#  Input: n on LHS, A on RHS
                           #  Get the size of A
                   2      ^   Get 2^len(A)
                       i.@    Get the range [0, 1, ..., 2^len(A)-1]
                    #:@       Convert each to binary to get the masks for each subset
                 #~           Copy using each mask from A
               <@             Box each subset
      +/@>                    Unbox each and reduce using addition
     =                        Check which sums are equal to n, 1 if true else 0
            ]                 Get the list of boxed subsets
           #                  Copy only those whose sums are equal to n
~.@                           Remove duplicates and return


text:
Solve the Secretary Problem
The Secretary Problem is a famous problem described as thus:

You need a new secretary
You have N applicants that you can interview one at a time
You are able to score each applicant after the interview.  Your scoring system will never give two applicants the same score
After you interview an applicant, you must give an immediate "yes" or "no"
You want the applicant with the highest score

The solution is to interview the first floor(N/e) applicants, and then accept the first applicant that has a higher score than all of the previous applicants.   If none of the applicants are higher, then return the last applicant.  Interestingly enough, this gives the top applicant 1/e percent of the time.  e refers to Euler's number.  To get the value of e, you can use a builtin, log, or hardcode it to at least 5 decimal points.
Input:
An non-empty array of unique non-negative integers no more than 2^31-1.
Output:
An integer representing the chosen candidate.  To be clear the algorithm is:

Find the maximum element in the first floor(N/e) elements of the array.
Iterate through the remaining elements, and return the first element that is higher than the maximum found on step 1.
If none of the elements are higher, than return the last element.

For example, say your array was [2,7,4,3,9,20], so N = 6 and floor(N/e) = 2.  The first 2 elements of the array is [2,7].  The max of [2,7] is 7.  The remaining elements are [4,3,9,20].  The first element that is greater than 7 is 9, so we return 9.
Test Cases:
[0]         => 0
[100]       => 100
[100, 45]   => 100
[0, 1]      => 0
[45, 100]   => 45
[1, 4, 5]   => 4
[1, 5, 4]   => 5
[5, 4, 1]   => 1
[5, 1, 4]   => 4
[4, 1, 5]   => 5
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
=> 98
[10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30]
=> 30

Your solution must be O(n), where n is the length of the array.  If your language has a builtin that finds the maximum of an array, you can assume that the function takes O(n) (and hopefully it does).
Standard loopholes apply, and this is a code-golf, so the make the shortest answer in your favorite language!

What e should be used?

@voidpigeon I presume it's https://en.wikipedia.org/wiki/E_(mathematical_constant)

Ah, now I understand how the algorithm works. I thought your second paragraph meant that you never interview the candidates after floor(n/e) at all.

Is there a required minimum precision for e?

@Mego if your language has a builtin for e or log, you can use that, or you can define your own using 5 decimal points.

I asked specifically because in some languages, it's shorter to define a variable with 5 decimal points of precision than it is to actually use the builtin e (e.g. Python, where e=2.71828 is shorter than import math;math.E)

@Mego edited my comment.  You are free to define your own to 5 decimal points if you wish.

You should edit that into the challenge. Additionally, is there a restriction on what range of values is possible for the input?

You should add the test case [0, 1]. My current revision is failing that one. (Stupid 0.)

@Dennis mine too, since that means the first stage doesn't occur.

Note:  1/e percent of the time. would be really bad. It's a probabilty of 1/e, that is roughly 37% of times

It's still the maximum percentage :)

Jelly, 13 bytes
L:Øe³ḣȯ-Ṁ<i1ị

Definitely an O(n) algorithm, hopefully an O(n) implementation. Try it online!
How it works
L:Øe³ḣȯ-Ṁ<i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         <     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).

CJam, 20 Bytes
q~___,1me/i<:e>f>1#=

Works similarly to Dennis's suggestion.
q~___                     Read array, duplicate three times
      ,                   Consume one to find the length
       1me/i              Push e then divide and take floor
            <             Take that many elements from the list
             :e>          Find maximum (Thanks to Dennis)
                f>        Label array elements larger than this as 1
                  1#      Find the first one (won't be in set of elements we've looked in)
                    =     Take that element from the final copy of the array. -1 gives us the last element as required

$W= doesn't run in linear time.

Urgh, you're right. Is there any better way of finding the maximum in CJam that you know of that does?

:e> (reduce by maximum)

MATL, 27 25 23 bytes
tttn1Ze/:)-1hX>>T0(f1))

Uses the same approach as A. Simmons' CJam answer.
Try it online!

Java, 128 118 bytes
a->{int c=(int)(a.length/Math.E),i=0,m=-1,t=0;for(;i<a.length;i++){t=a[i];if(i<c)m=t>m?t:m;if(t>m)return t;}return t;}

Indented:
static Function<Integer[], Integer> secretary2 = a -> {
    int c = (int) (a.length/Math.E),     // c = floor(N/E)
        i = 0, m = -1, t = 0;            // declare vars early to save bytes
    for (;i<a.length;i++) {              // for each element of input
        t = a[i];                        // cache element to save bytes
        if (i<c)                         // if before c
            m = t>m ? t : m;             // m = max(m, element)
        if (t>m)                         // if element > m
            return t;                    // return: we've found our best
    }                                    // if never found a good element
    return t;                            // return the last element
};

JavaScript (ES6) 64
(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

Less golfed
(
 a,
 l=a.length/Math.E, // limit for stage 1
 x // init at undefined
)=>(
  a.every(v => --l > 0 // checking for >0 no need to floor
          ? x>v?1:x=v // stage 1, find max in x, always return truthy
          : (z=v)<x ) // stage 2, set z to current value and exit early if z>x
  , z // at last z has the last seen value
)

Test

f=(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

console.log=x=>O.textContent+=x+'\n'

;[
 [0], [100], [0,1], [1,2,3],
 [100, 45],
 [45, 100],
 [1, 4, 5],
 [1, 5, 4],
 [5, 4, 1],
 [5, 1, 4],
 [4, 1, 5],
 [10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30],
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
].forEach(t=>{
  var r=f(t)
  console.log(r+' : '+t)
})

Ruby, 64 bytes
->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}

@Doorknob It loops through the first floor(N/e) elements once to find the maximum, then loops through the rest of the list in the worst case comparing each element to the maximum. There is only one comparison per element in both parts.

Ah, that's right. I misread and thought you were finding the max in each iteration.

In fact, I think it's still O(n) if you just do a.find in the second step, although obviously it's a lot less efficient.

You can use (0...c) for a range that excludes c.

@histocrat Yes, it should be O(2n) which is O(n)

@histocrat Thanks! For some reason I was thinking that c was a floating point number and not an integer.

PARI/GP, 70 bytes
This may have trouble on older versions of gp when given a singleton, but it works at least from revision 18487.
v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]

JavaScript (ES6), 79 bytes
a=>(m=Math.max(...a.splice(0,a.length/Math.E)),a.slice(a.findIndex(x=>x>m))[0])

Works because findIndex returns -1 on failure, but a.slice(-1)[0] returns the last element of the array as desired.

Python 2, 87 bytes
a=input()
t=int(len(a)/2.71828)
m=max(a[:t]+[-1])
for x in a[t:]:
 if x>m:break
print x

The user enters the array as a list, with square brackets and commas. Python 2's input() command is convenient here.
Whether or not we terminate the process early, we hire the last person who got interviewed.

Perl 6, 43 bytes
I think this is O(n)
{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}

Python 3.5; 110 bytes:
def Interview(h):k=max(h[0:int(len(h)/2.71828)-1]);n=max(h[int(len(h)/2.71828)-1:len(h)-1]);return max([k, n])

Basically, what the above does is that it firstly takes an array provided, "h" as long as it includes more than 5 items (for now...), finds the maximum value in the first (length of array (len(h))/ Euler's number (to 5 decimal places)) items of that array, and then returns that value as "k". Furthermore, "n" is the maximum value in the rest of the array. Finally, the value returned from the function is the maximum value in an array containing both "k" and "n".
Note: The max() function of Python is O(n) complexity.
Below is a more readable, non-code-golf version of the above code that has a random, unique 10-item array provided, to confirm that it works:
import random, math

def Interview():
    k = max(h[0:int(len(h)/math.e)-1])
    n = max(h[int(len(h)/math.e)-1:len(h)-1])
    return max([k, n])

h = random.sample(range((2*31)-1), 10)

print(Interview(h))

Welcome to PPCG!  You can comma separate your imports.  Also, you don't need to generate the array yourself, so you can remove that portion of the code (simply have the array as a parameter to the function)

@NathanMerrill Yeah, I was thinking of doing that, but then I thought that you wouldn't really like it, but now that I know that really does not matter, I will edit my answer. Also, thanks for the tip about comma separating my imports. I had totally forgotten about that!

Other tips: You have lots of unneeded whitespace (after commas, between equals signs.  You don't need a print statement at the end either.

@NathanMerrill Thanks for the tips! I will keep those in mind as I do more code-golfing! :)