text:
Sort by custom alphabet
The challenge is to make a program that sorts a list of words, only that the words need to be in the order of a random given alphabet.
Your program will accept a string of comma-separated words and a new alphabet.
Your program will output every word in the same way in the new sorted order.
Example:
Input:
home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy

Output:
cat,green,home,network,egg,oval

This is a code-golf, so the winner is the person with the shortest program.
This is my first challenge so any improvements to the question/challenge are appreciated.

I take from your example that the alphabet will be separated from the words by a space. Is that correct? 2. Will the words always be in lowercase?

@Dennis yes to both

That is a mistake. I will edit that.

+1 OK question (for a first try ;-)).  But I'm not seeing the relevance of the title - perhaps you can rename it to Sort by custom alphabet or something more creative?

@DigitalTrauma Yeah that might be better. I tried to play a little with the words. I aimed for a reference to ascii and utf-8 and the like to ask which it is. But that one failed. I'll change it to your suggestion which was better.

May we take the inputs in a form that is more appropriate to the language? E.g. two separate inputs; a character matrix with one word on each line, and a character vector of letters. A list of strings. Etc.

CJam, 26 19 17 bytes
rr:A;',/{Af#}$',*

Try it online.
Test case
$ cjam sort.cjam <<< 'home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy'
cat,green,home,network,egg,oval

How it works
rr                    " Read two whitespace-separated tokens from STDIN. ";
  :A;                 " Save the second token (the alphabet) in A.       ";
     ',/              " Split the remaining token at commas.             ";
        {Af#}$        " Sort by the chunks' characters' indexes in A.    ";
               ',*    " Join, separating by commas.                      ";

Well, since u also made used the same approach, mine doesn't really make any sense now.

@Optimizer: You beat me by eight seconds. If you undelete your answer, I'll roll mine back.

No, I think its a trivial and very obv change. I should have looked at your updates before posting my answer in the first place :)

Bash+coreutils, 37 bytes
tr ,$2 \\na-z<<<$1|sort|tr \\na-z ,$2

Output:
$ ./alphasort.sh home,oval,cat,egg,network,green bcdfghijklmnpqrstvwxyzaeiouy
cat,green,home,network,egg,oval, $

Nice way of dealing with the commas!

Pyth, 19 characters
j\,o_mx_zdNchczd\,

Test:
$ pyth -c "j\,o_mx_zdNchczd\," <<< 'home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy'
cat,green,home,network,egg,oval

Explanation:
                            Implicit: d=" "
                            Implicit: z=input()
j\,                         ",".join(
   o                                 order_by(lambda N:
    _                                                  rev(
     m                                                     map(lambda d:
      x_zd                                                              rev(z).index(d),
      N                                                                 N),
    chczd\,                                            z.split(" "[0].split(",")

Essentially, it sorts the chunks, with a key of the list of indexes of the characters in the string, then joins them on commas. The reversal businesses is shorter than spliting the string again.

18 bytes: j\,_omx_zdNchczd\,

@Dennis very clever, thank you.

R, 49 bytes
function(w,a,`[`=chartr)"a-z"[a,sort(a["a-z",w])]

Try it online!
Translates words from given alphabet to a-z, then sorts and then translates back.
Uses flexible I/O rules (vector of words and alphabet as string).

With strict I/O rules it goes up by a lot (R is not very good with strings):
R, 112 bytes
function(s,`/`=strsplit,t=el(s/" "))paste(chartr("a-z",t[2],sort(chartr(t[2],"a-z",el(t[1]/",")))),collapse=",")

Try it online!
Here we do the splitting of the input string inside the function.
First, we redefine / to be strsplit. It always returns a list, so we will need to extract the first element (which is shortest done by el). We split the words from the alphabet on   and then the words themselves on ,.
Then we do the same trick as in the main answer.
At the end we collapse the whole vector with , using paste.

With many strange function redefinitions:
R, 111 bytes
function(s,`?`=el,`[`=chartr,`/`=strsplit,t=?s/" ")paste("a-z"[t?2,sort((t?2)["a-z",?(t?1)/","])],collapse=",")

Try it online!
Here we also redefine [ to be chartr, so we cannot use [ to subscript t anymore, but we can use el for this purpose.
This leads us also to redefining ? to be el (after some trial and error with operator precedence). It is worth noting, that ? can act as binary and unary operator and has the lowest precedence of all.

K (ngn/k), 23 bytes
{","/x@<y?x:","\x}." "\

Try it online!
Takes input as outlined in question.

" "\ split input on the space, into the list of comma-delimited words and the (shuffled) alphabet
{...}. call the function with the list of words as the first arg (x) and the alphabet as the second arg (y)
x:","\x split the string of comma-delimited words into a list of the words themselves, updating the x variable
y?x look up the index of each character in each word in the shuffled alphabet
x@< grade the resulting list of lists of indices, and apply the sort order to the list of words
","/ join the individual words with commas

K (ngn/k), 8 bytes
{x@<y?x}

Try it online!
Assumes more lenient input/output format; a first arg x of a list of words, and a second arg y containing the shuffled alphabet. A list of strings is returned instead of a comma-delimited string.

Ruby, 53 50 bytes
a,b=$*
$><<a.split(?,).sort_by{|w|w.tr b,'a-z'}*?,

I'm using Ruby's tr to replace the custom alphabet with a-z before sorting. Input is via command-line argument.

You can shave off a byte if you use $><< to print to screen (you can remove the space then). You can shave off another two bytes by assigning $* to variables like so: a,b=$* and using #sort_by instead of #sort_by!.

@britishtea Thanks. I thought I would need *$* (which I had at first and which is the same length).

Clojure, 115 50 bytes
Oh, an edit five years later :D And actually in the past I out-golfed myself, now I used (map char(range 97 123)) to generate the a - z sequence but my original answer just re-uses the alphabet input via (sort %2). Well this new answer requires a more liberal input format, namely the first argument is a list of words.
#(map(fn[i](str(mapv(zipmap %2(sort %2))i)))%)

I had to re-discover that vectors don't sort neatly, but this can be avoided by casting them to strings. And not by using clojure.string/join or apply str, they sort just fine as string representations of the vector! Change the sort-by to map and you get:
(def f #(map(fn[i](str(mapv(zipmap %2(sort %2))i)))%))

(f ["home", "oval", "cat", "egg", "network", "green"] "bcdfghjklmnpqrstvwxzaeiouy")

("[\\f \\x \\j \\v]"
 "[\\x \\q \\u \\i]"
 "[\\b \\u \\p]"
 "[\\v \\e \\e]"
 "[\\k \\v \\p \\r \\x \\n \\h]"
 "[\\e \\n \\v \\v \\k]")

TIO
Original answer:
#(apply str(butlast(interleave(sort-by(fn[w](apply str(map(zipmap(sort %2)%2)w)))(re-seq #"[a-z]+"%))(repeat \,))))

Wow, this started of well with (sort-by(fn[w](mapv(zipmap(sort %2)%2)w))) but then I realized vec don't get sorted the same way as strings, and interleaving those commas takes significant amount of code as well.

05AB1E, 15 bytes
#`U',¡ΣXsSk}',ý

Try it online.
With less restricted I/O rules, this could have been 2 (or 3) bytes:

Σk: Try it online with character-list input;
ΣSk: Try it online with string-list input.

Explanation:
#            # Split the (implicit) input-string by spaces
 `           # Pop and push both strings separated to the stack
  U          # Pop the alphabet-string, and store it in variable `X`
   ',¡      '# Split the words-string on ","
      Σ      # Sort this list of words by:
       X     #  Push the alphabet-string `X`
        s    #  Swap so the current word is at the top of the stack again
         S   #  Convert it to a list of characters
          k  #  Get the index of each character in the alphabet-string
      }',ý  '# After the sort-by: join this list of words with "," delimiter
             # (after which this string is output implicitly as result)

Σ            # Sort the first (implicit) input-list of character-lists by:
 k           #  Index each character into the second (implicit) alphabet-string
             # (after which the sorted list of character-lists is output implicitly)

Technically, isn't 05AB1E newer than the challenge?

@pajonk It is, but since mid 2017 that doesn't matter anymore. Newer languages are allowed to answer challenges without adding a "non-competing".

thanks for the update, I somehow missed that.

JavaScript (E6) 102 119
Sort with a mapping function 'M' based on the alphabet in variable 'a'
With IO using popup (prompt + alert)
x=prompt().split(/[ ,]/),
a=x.pop(),
M=w=>[10+a.search(c)for(c of w)]+'',
alert(x.sort((a,b)=>M(a)>M(b)))

As a (testable) function with 1 string parameter, returning a string array (92)
F=x=>(
  M=w=>[10+a.search(c)for(c of w)],
  x=x.split(/[ ,]/),
  a=x.pop(),
  x.sort((a,b)=>M(a)>M(b))
)

Test In FireFox/FireBug console
F('home,oval,cat,egg,network,green zyxwvtsrqpnmlkjhgfdcbaeiou')

Output
["network", "home", "green", "cat", "egg", "oval"]

-4 if you replace your sort function with (M(a)>M(b))-(M(a)<M(b))

@DocMax very nice. It turns out that it's even simpler than that (http://stackoverflow.com/a/7232172/3640407)

If you reuse prompt for input and output and alias it you can avoid the split call by taking the inputs separately. I think that should save a few characters.

Also I'm only on my phone right now but why is M so complex? Wouldn't it work to use M=w=>[...a].indexOf(w)? I can't test it right now, unfortunately.

@IngoBürk w is a word, not a character. M replace each character in w with its position in a.

Ah, of course. Suddenly the 10 in there makes sense to me, too :) I don't know why I thought about characters..

Python, 131
w,a=input().split()
print(",".join(sorted(w.split(","),key=lambda s:"".join(["abcdefghijklmnopqrstuvwxyz"[a.find(c)]for c in s]))))

There should be plenty of room for improvement.

You don't have to use a key as the sort function - just use the list of a.find(c) directly.

Pip, 15 bytes
b@?^_SKa^',J:',

Takes the two inputs as command-line arguments. Try it online!
Explanation
b@?^_SKa^',J:',
       a         ; First command-line arg (list of words)
        ^',      ; Split on commas
     SK          ; Sort by the following key function:
   ^_            ;   Split the word into a list of letters
 @?              ;   Get the index of each letter in
b                ;   The second command-line arg (alphabet)
           J:',  ; Join the resulting list on commas

Japt, 12 bytes
¸Îq, nU¸Ì q,

Try it

Zsh, 24 bytes
tr $1 a-z|sort|tr a-z $1
Attempt This Online!
If we must use the OP's inane I/O format, 37 bytes:
tr $2, a-z\\n<<<$1|sort|tr a-z\\n $2,
Attempt This Online!
If a trailing comma is not allowed either, append |head -c-1 for +10 bytes.

Python 3, 50 bytes
With flexible input :
lambda w,a:sorted(w,key=lambda s:[*map(a.find,s)])

Try it online!
Python 3, 71 bytes
With strict input format :
lambda x:sorted(x[:-27].split(","),key=lambda s:[*map(x[-26:].find,s)])

Try it online!
Both can be shortened by 3 bytes in python 2 by removing [*   ] arround the map

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


text:
Stitch a picture
NOTE: This question is currently in the SANDBOX.  Please bear this in mind before adding new answers.

I have a large collection of fine art.  My toddler is learning to use scissors and glue; lately she has started playing with my art collection.  Fortunately she is really quite good with the scissors and cuts things up into perfect squares.  She then uses glue to randomly tile the cut-up squares back into a new piece of art.  For example, she reinterpreted my Mona Lisa (which wikipedia kindly hosts for me) as follows:

The following python script simulates what my toddler has done:
#!/usr/bin/python

import sys
import random
from PIL import Image

origname = sys.argv[1]

im = Image.open(origname)
width, height = im.size
width = (int(width + 99) / 100) * 100
height = (int(height + 99) / 100) * 100

im = im.crop((0, 0, width, height))

im2 = Image.new("RGB", (width, height), "black")

blocks = []
for x in range(width / 100):
    for y in range(height / 100):
        blocks.append(im.crop((x * 100, y * 100, (x + 1) * 100, (y + 1) * 100)))

random.shuffle(blocks)

for x in range(width / 100):
    for y in range(height / 100):
        im2.paste(blocks.pop().rotate(90 * random.randint(0,3)), (x * 100, y * 100))

im2.save("shuf" + origname)

Please excuse python skills - I'm still learning, but was happy to see how quick and easy it was to write this script.  Polite code-reviews will be graciously accepted ;-)
It does the following:

loads the image whose file name was given as a command-line parameter
pads that image with black pixels such that the width and height are exactly divisible by 100
divides the image into 100x100 pixel blocks
randomly shuffles the blocks
randomly rotates the blocks (by multiples of 90 degrees)
reassembles the randomly arranged blocks back into a new image with the same size attributes as the (padded) original
saves the new image using the original filename prefixed with shuf

Your task is to write a program that takes the output of this script, analyses the edges of each 100x100 block and reassembles them back to the original picture.
Input:

an image filename.  This may be passed at the commandline, via STDIN or even hard-coded, whichever is most convenient.

Output:

either output the a singular rearranged image to a differnent file, or display the singular rearranged output to the screen.

Input and output specs are intended to be lenient here, as filename-parsing is a non-goal of this code-golf question.
Other rules

The program must be able to correctly reassemble any random arrangement of the wikipedia Mona Lisa by the python script.  Hard-coding of block transformations of the example image above is strictly not allowed.

Because all 100x100 pixel blocks are randomly rotated, the output image may also be randomly rotated by a multiple of 90 degrees.

It is understood that for some degenerate cases (e.g. chequerboard of 100x100) blocks it is impossible to correctly rearrange the image.  In those cases it is acceptable to produce incorrect/undefined output.  However I think in general for photo images and almost all "famous" artworks, reassembly should be possible.  Works by Mark Rothko are a possible exception.

Common image manipulation libraries may be used (e.g. Python's PIL), but any APIs expressly designed for this purpose are strictly banned.

Standard “loopholes” which are no longer funny

Now my toddler got a hold of The Scream.  This is the result that needs to be fixed:

could we input/output the image through stdin/stdout? (like ./solution1 < input.jpeg > output.jpeg) And what about the image formats?

@JohannesKuhn Yes, thats fine.  Any common image format is fine.

So can I just brute force this?

Also how is the program supplied the original image?

@BetaDecay as the task is to obtain the original image, I don't think the original image is supplied

@edc65 How on earth do you know that the image is as it should be then?

I think its possible to reconstruct the image up to rotation, if the image is not a degenerate case

You can improve your Python code by removing all spaces, giving variables single-letter names, using exec with string replacement on the repetitive bits, and replacing (x + 1) * 100 with -~x*100. :-P

@xnor Ha ha funny ;-)

@Cameron Yes, this is a good point - I will edit in a note about rotation of final image

@BetaDecay wrt brute forcing.  You may only output a single fixed image.  Multiple output images are not acceptable.

@BetaDecay The point of the challenge is for your program to analyze the edges of blocks to find similarities and attempt to fit similar edges together to reassemble the original picture.  Hence the [tag:image-processing] tag.

It occurs to me that http://codegolf.stackexchange.com/questions/36967/put-together-cut-strips-of-paper-to-get-original-message is possibly related. IMO image vs text and 1d vs 2d matching alone are enough to set this one apart.  Of course its up to the community to decide if this is a duplicate or not.

You can do easily with brute force. Try every block arrangement (including rotations) and keep the one that minimize the total difference at borders. With monna lisa, 77!477 possibilites (good that 7 and 11 are primes). May I cross-post my (eventual) answer to http://codegolf.stackexchange.com/q/36747/21348?

@DigitalTrauma But actually your Python code looks good. I don't have any comments.

This task is impossible.  Sure you can try and minimize MSE on the edges and push it through greedy or the Hungarian algorithm, but its still fundamentally just a 'best guess' for the programmer's definition of 'best'.  For any algorithm, you can craft input that defeats it.  And images like this one http://www.robertnyman.com/images/0611/lightroom/grid-view-panels-hidden.png will, with 100x100 grids, defeat all attempts.

Furthermore, my naive approach works well enough ... except the MSE of the black padding pixel edges is 0 with each other!  It seems wrong to special-case black edges, and black edges can legitimately occur in-image.  Alas I think the contest is, fundamentally, flawed.

@Will You may assume that the unpadded original does not have black edges.

Well I can't get MSE to work on these edges.  Because the edges are not exact matches, and because I'm not trying to model the JPG DCT, I keep getting mismatches that are actually lower edge MSE than the real image.  Oh well.

@Will Perhaps the MSE is not the better way ...

Maybe you should turn this into a code-challenge and make the score the number of correctly aligned edges (code size being the tie breaker). And it would be huge help if you used a lossless image format.

This really sounds intresting/challenging but I think it might be too challenging. I tried for the mona lisa various distance metrics and calculated MSE for a lot of rotated/swapped tiles of the original mona lisa, and was always able to find configurations that had a lower global MSE than the original image. I am going to try some totally different approach now, but I think the idea is good to transform this into some "best out of 10 images" alignment contest like others suggested.

This exact problem is an active area of research, see eg http://www.cs.umanitoba.ca/~ywang/papers/crv13_jigsaw.pdf and https://github.com/typeinference/jigsaw-puzzle which has an implementation of that. State of the art is just 96% correct; the paper also explains how it calculates that score (hint hint)

Your toddler is very destructive. :P

Can we assume that the images are RGBA?

Actually, that doesn't matter. Never mind.

This is just edge-matching, right...? Or is there a component I missed?

source: Stack Exchange

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

sort: votes


text:
Find X in a partially sorted Array
Your job is to find the location (read index) of a given element X in an array gone through the following transformation process:

Take a fully sorted integer array of size N (N is known implicitly)
Take any random number of mutually exclusive even index pairs (as in that no index appears in more than 1 pair) from the array and swap the elements on those indexes.

A sample array can be like
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

formed by
// Take fully sorted integer array
[-1, 2, 3, 4, 5, 6, 70, 80, 90, 100]
// Take some even index pairs : (0, 4) and (6, 8)
// Swap the elements in these indexes. i.e., element at 4th index goes to 0th etc.
// Final array:
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

and a sample X to find in this array can be
-1

You should output the index of the element X in the final array (4 in the above example) or -1 if the element is not found in the array.
Rules

In built searching functions are prohibited.
You must write a method/function/program which takes input from STDIN/Command line arguments/Function arguments.
Input must be in <Array> <X> format. Example: [5, 2, 3, 4, 1, 6, 9, 8, 7, 10] 1
The input array may also contain duplicate integers. In such case, any one index can be the output. UPDATE : You may assume that total number of duplicates << (far less than) size of array. For the benefit of the question in general, duplicates are now prohibited to avoid playing a role in time complexity of the searching algorithm.
Output should be the index of the element X in the array or -1 if not present.

Scoring

Being a code-golf and a code-challenge, your score is calculated by <byte count of your program>*<coeff. of complexity>
Coefficient of Complexity is decided based on the worst case time complexity of your code (Big-O) using the mappings given below.
If your code needs to know the length of the array, it can calculate length using inbuilt methods and that won't be added to the time complexity of the searching part of the code.

Time Complexity      Coefficient
--------------------------------
O(1)                 0.25
O(log(n))            0.5
O(n)                 5
O(n*log(n))          8.5
O(n^2)               10
O(greater than n^2)  20

Minimum score wins!
Bonus

Multiply your final score by 0.5 if you can handle a case where the array has gone through the step 2 in the transformation process I times (instead of just 1), where I is passed as the third parameter in input.
Note that while going through step 2, I times, pairs in each step are mutually exclusive, but pairs in different steps can have common indexes.

JavaScript (E6) 97.5 (39*5*0.5)
(O(n), linear search, the array can be scrambled again and again)
The function accepts (and ignores) a third parameter
F=(a,x)=>a.map((e,i)=>e-x?0:j=i,j=-1)|j

or
F=(a,x)=>a.some((e,i)=>(j=i,e==x))?j:-1

or
F=(a,x)=>a.every((e,i)=>(j=i,e-x))?-1:j

Test in FireFox/FireBug console
F([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1, 2)

Output
4

Nicely played with coefficients and bonus!

Golfscript, 20 * 2.5 = 50
~{={0:-1}*0):0}+%;-1

Explanation:

~ - eval the input. It should be in the form [-1 0 3 2 4] 3.
{...}+% - prepend the last argument (needle) to {...}, then map the resulting function over the array
;-1 - discard the results of the mapping, and push -1 to the stack.

The real fun is what happens inside:

= - check if the needle matches the haystack element
{0:-1} - take the current value of the variable 0 and store it into the variable -1.
* - execute the function n times = execute if the previous is true.
0):0 - increment the current value of 0.

yep. In golfscript, numeric all literals are just variables initialised to some useful values.

Haskell, 51 * 2.5 = 127.5
a 0= -1;a x=x;f[]_= -1;f(h:t)n|h==n=0|1>0=a$1+f t n

ungolfed:
adjust 0 = -1
adjust x =  x

find []     _ = -1
find (x:xs) n | x == n    = 0
              | otherwise = adjust $ 1 + find xs n

Python 79.75 (319*0.5*0.5) 106.5 (213*0.5)
UPDATE: Since the time complexity is determined by worst case for any number of swaps, I have reduced my algorithm to work only for the case I=1, which results in O(log n) time.
The findX function is f, while g, and h are helpers.
The function uses the ordering of the odd indices to apply search to find where X should be. If X has been swapped then it uses a second binary to search to find where X has been swapped to, based on the value found at where X should have been. Since I use two binary searches in the worst case it is O(logN).
I find X by applying a binary search on the odd indices. If X is not found on the odd indices, I check the array at the even index where X should be if the array was ordered (call this value n1). If n1 equals X, I found the index. If n1 does not equal X I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n1). Call this new value n2. If n2 equals X, I found the index. Otherwise I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n2) ... etc.
The algorithm terminates when X is found or n1 is found a second time.
Essentially my algorithm traces the random swapping in reverse. That is, it will 'decode' the last swap, then 'decode' the second last swap, and so on until I decode the first swap. For each 'decode', I use a binary search ( O(logN) time ), plus an additional binary search to find the first index. The algorithm will 'decode' the simplest sequence of random swaps to get to the given state (e.g. the algorithm will not apply any decoding to an array that had the same swapping applied twice). Also, note that any sequence of swapping will be equivalent to a sequence of swapping of length less than or equal to N/2. Hence the complexity is at worst O(min(I, N/2) * logN) and the algorithm works for I swaps.
def f(l,X):
   m=len(l)
   i=g(l,X,0,m-m%2)
   return -1 if i>=m else i if l[i]==X else g(l,l[i],0,m-m%2)
def g(l,X,n,m):
   a=(n+m)//2
   a+=a%2-1
   return n if m<=n else g(l,X,a+1,m) if l[a]<X else g(l,X,n,a-1) if l[a]>X else a

     def h(l,F,X,s,m):
        i=g(l,F,0,m-m%2)
        return -1 if i==s or i>=m else i if l[i]==X else h(l,l[i],X,s,m)

Ex:
print f([-1, 2, 3, 4, 5, 6, 70, 80, 90, 100],-1)
print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1)
print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100], 5)
print f([-1, 2, 70, 4, 90, 6, 3, 80, 5, 100],-1)
Output:
0
4
0
0

"I will find the index of X after I iterations." -- Iiiii'm not sure about that. Can you elaborate on that part? Still, very nice.

My bad, it will be at most I+1 iterations. I'll edit my post.

Your algorithm fails for e.g. f([1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1],2), which is a transformed version of f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2],2). In fact, since an array consisting of an odd number of 1s followed by a 2 is guaranteed to contain no information in the odd indices, and the 2 may appear at any even index in the list, I've argued with @Optimizer above that sub-O(n) worst case performance is impossible. Otherwise, I had the same idea, hence props for a smooth implementation. ;)

@COTO that's an implementation issue - just plop an infinity at the end to handle the case of the element being looked up being at the end.

@JanDvorak: The element being looked up isn't at the end. It's somewhere unknown in the middle of the list. That's the problem.

@Cameron an off-by-one issue isn't what I meant here - I'm not sure why it should succeed finding the target at all.

@COTO I mean, the case of the element being looked up being the largest in the array.

@COTO oh. Gotcha. Once you know you might be missing a 2, you still don't know where in the list it is. Forbidding duplicates would solve that.

@JanDvorak: I know. But the input is the transformed list, where the largest element, so long as it's at an even position, may have been swapped with a random 1 somewhere in the list. Since all of the odd elements are 1, a binary search avails no information at all about its location. And yes, forbidding duplicates would solve it. :)

Still, it's a nice approach for when there are no duplicates in the input array, even if I believe it only works for a single round of swaps.

You're absolutely right about it only working for a single round of swaps. Two or more rounds of swaps allows all permutations of the even elements, meaning that (once again) the odd elements provide absolutely no information about the even elements in the worst case. Thus it is my contention that for I >= 2, it is impossible to beat O(n) worst case performance even with duplicates forbidden.

@COTO good catch. I didn't think of the the case of duplicate values, and yes that can only be done in O(N).

@Cameron +1 for putting up with me. ;)

@COTO are you sure two rounds of swaps are sufficient to generate every permutation? How do you generate larger cycles? Two rounds are definitely sufficient to randomise the lower half entirely (enough to force linear-time worst-case)by swapping all up, then all down, but then the permutation of the top half becomes entangled with the permutation of the bottom half (isomorphic cycle space, I believe).

@COTO no problem, but I am sure it works for more than one swap. I've added more example tests

I've also added, what I hope to be, a better description of why it works

@JanDvorak: Good observation. I admit my group theory is a bit rusty. Regardless, it does seem as though it would be remarkably difficult to search over the reachable set of permutations in sub-O(n), even with I = 2.

@Cameron: After pondering it for a while, I see your point on I log(n) complexity for unique elements (not sure where that ranks on the point scale). The swaps must ultimately create a cycle containing the search value, if it's present. Your implementation has at least one bug, however. Consider f([1, 8, 3, 10, 5, 4, 7, 6, 9, 2], 10) which is obtained from passing [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] through swaps (6, 8), (4, 8), (2, 8), (2, 10). Your routine incorrectly returns -1 in this case.

@COTO actually, it is possible to perform an arbitrary permutation using only two rounds of swapping. For each cycle in the cycle space, reverse first the whole cycle (from an arbitrary point), then the cycle without one element.

You should really remove your (provably impossible) claims about the behavior for I > 1 and alter the score appropriately. (cc @COTO - are you sure you want to upvote an answer with such impossible claims?)

Your actual score is 319/2 = 159.5 - that is, the worst so far rather than the best so far.

@COTO, in your example "which is obtained from passing [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] through swaps (6, 8), (4, 8), (2, 8), (2, 10)" - Are you taking those pairs in a single swap step ? If yes, you are violating the rule of mutually exclusive pairs, explained in the question

@Cameron - Why do you have a second 0.5 multiplier ? Can your algorithm solve for I > 1 swap steps ? If yes, I don't see a code where you read a third argument in your function f

@Optimizer: No, it's over I = 4 steps. Cameron's algorithm is intended to work for any I, hence it should work for the given sequence, which it doesn't.

@COTO [1, 8, 3, 10, 5, 4, 7, 6, 9, 2] is invalid input since you have swapped the odd indices, not the even indices

@Optimizer I have one 0.5 multiplier since it works in O(log n) time for I=1 swaps and I have a second 0.5 multiplier since it works for I>1. I was unsure whether to use the complexity when I=1 or take the worst case for any I

@Cameron Worst case for any I

@Optimizer Ok, I'll edit my score

JavaScript ES6, 95 (38*5*0.5)
Performs an O(n) search. Accepts bonus parameter but ignores it
f=(a,x)=>a.reduce((p,c,i)=>c-x?p:i,-1)

Shouldn't f([1, 2, 3], 42) return -1?

@Chiru Yeah missed that part working on it

@Chiru Fixed unfortunately with more bytes

+1 for both fixing it and still having the shortest ES6 solution as of now. Great job!

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


text:
Chotchkies Restaurant
Because there isn't enough xkcd on PPCG...

Challenge
The challenge is the same as above - given a menu and a total price, you need to find what the customer ordered.
The menu will be supplied as a text file in the format:
Name:Price
Name:Price

The path to the menu file and the total price should be supplied via argv or STDIN.
If you wish, the menu may be supplied via STDIN/argv (instead of newlines, separate each item by commas).
The output should be a list of values. If there are multiple answers, output all of them.
Example
Menu:
Burger:12.60
Pepsi:3.50
Lobster Thermidore:33.10
Ice Cream:23.00

Total Price: 68.70
The output is:
Burger
Lobster Thermidore
Ice Cream

Winning
The fastest code given an undisclosed problem wins. The speed will be taken five times and averaged.

Can the menu be directly input via STDIN/arguments ?

Limitation of a file makes a lot of programming languages impossible to use here.

What do you mean by fastest code ? Time wise ? Complexity wise ? If its time wise, then its completely unfair

Why unfair? I assume OP will run the undisclosed test case on their machine. However, it should be run multiple times for each submission to rule out noise. It also begs the question if there are limitations of the languages that can be used.

@IngoBürk If there are two answers, 1 in JS and 1 in C, JS one is bound to be slower what so ever.

(Given they use similar algorithms)

@Optimizer Won't that be the case in every fastest code challenge though?

Generally fastest code challenges have some common platform to test things out and the test cases are big enough to diminish the gaps enough.

@Optimizer I will try and make sure that the problem is big enough (100 items on the menu, say?) then.

I agree with the comments on speed both here and in the answer. You're going to need a huge menu, and even with 100 items parsing the menu might take longer than running the algorithm (depending on your disk and api.) I do think this would have (still would?) make an excellent codegolf.

@steveverrill Edited to make it code golf

@steveverrill: I guess you got me wrong. 100 items would take forever, since 2^100 is a huge number of possible combinations to test. I was trying to say that 2^50 is already huge, thus both approaches mentioned here might be intractable.

@Falko perhaps my statement was a little hasty. But to really need to search 2^100 possibilities, there would have to be 2^100 distinct totals, which means bills up to 2^100 cents. With a realistic bill value in the range 0 to 2^16 cents ($0 to $655.36) there would have to be multiple ways of reaching many of the totals, so you might get a lucky hit fairly quickly.

@steveverrill: Yeah, ok. You're have something like this in mind. But the OP says: "If there are multiple answers, output all of them." ;)

@Falko Oops, I missed that bit about outputting all of them! That could be a lot of text...

See Peter Taylor's comment above - code golf makes this a duplicate.

Python 2 - Naive implementation - 224
Well, let's start with "the most naive algorithm" as some kind of reference solution:
import itertools

path = input()
total = input()

with open(path) as f:
    menu = map(lambda l: l.split(':'), f.read().split('\n'))

names, prices = zip(*menu)
prices = map(float, prices)

for i in range(len(menu)):
    for comb in itertools.combinations(range(len(menu)), i):
        if sum(prices[c] for c in comb) == total:
            for i in comb:
                print names[i]

Input:
"data.txt"
68.70

Output:
Burger
Lobster Thermidore
Ice Cream

Complexity:
O(2^N * N)

--> exponential in the number of menu items N (of course)

Edit:
To reflect the new winning criterion I golfed it down quite a bit:
from itertools import*
S=str.split
f,t=S(input())
m=[S(l,':')for l in S(open(f).read(),'\n')]
R=range(len(m))
F=float
for i in R:
 for C in combinations(R,i):
  if sum(F(m[c][1])for c in C)==F(t):
   for j in C:print m[j][0]

The input format changed to data.txt 68.70 (both on one line separated with a whitespace).

I'm pretty sure the naive implementation is the only one anyone is going to have the stamina for.

@COTO: Agree. And if tested with a menu filled with 100 appetizers (!?) a complexity of O(2^N * N) vs. O(2^(N/2)) doesn't even matter. ;)

Sorry for being so indecisive, but to avoid this being marked as a dupe, I've changed it back to fastest code.


text:
Is the brick structure stable?
Let's represent a standard masonry brick as [__] (and ignore the fact that the top is open). When these bricks are stacked every other layer is offset by half a brick, as is usual in brick construction:
  [__][__][__][__]
[__][__][__][__]
  [__][__][__][__]
[__][__][__][__]

Thus each brick has at most six neighbors and it's impossible for two bricks to directly line up vertically.
The key point is that arrangements of these bricks are not mortared, but merely held together by gravity. So it is important that each brick in the structure is stable, otherwise the entire structure is unstable.
There are three ways an individual brick may be stable:

Any brick on the ground (the lowest line of bricks) is stable.
Any brick that has two bricks directly below it is stable:
  [__]   <- this brick is stable
[__][__] <- because these bricks hold it up

Any brick that has a brick both above and below it on the same side is stable:
  [__]  [__]
[__]      [__] <- these middle bricks are stable
  [__]  [__]      because the upper and lower bricks clamp them in

[__]          [__]
  [__]      [__]   <- these middle bricks are NOT stable
    [__]  [__]

From these rules we can see, for example, the arrangement
  [__][__][__][__]
[__][__][__][__]
  [__][__][__][__]
[__][__][__][__]

is unstable because the top right brick is unstable, which is all it takes.
A brick structure is only stable if all of its bricks are stable.
Challenge
Your task is to write a function that takes in a brick structure string and returns a truthy value if the structure is stable, and a falsy value if unstable. (truthy/falsy definition)
The input string may be arbitrarily large but it will always be a rectangular grid of characters, with spaces filling areas void of bricks. The character grid width will be divisible by 4 but the height may be odd or even.
The brick grid always extends above and to the right of the lower left brick position:
         .
         .
         .
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?

Depending on the structure, each BRK? either represents a brick ([__]) or empty space (4 spaces).
Notice that the half-brick cavities are filled with spaces to ensure that the character grid is rectangular.
Scoring
The shortest code in bytes wins.
Notes

If desired you may use . instead of space as the empty space character.
The empty string is considered stable.
If your language doesn't have functions you may use a named string variable as input and assign the result to another variable.
If your language doesn't have strings you may do whatever seems appropriate for input.

Test Cases
Various test cases, separated by empty lines. For clarity . is used instead of space for empty spaces.
Stable:
[__]

..[__]..
[__][__]

........[__]........
......[__][__]......
........[__]........

..[__][__]..
[__][__][__]
..[__][__]..
[__]....[__]

............[__]..
..[__][__][__][__]
[__][__][__][__]..
..[__][__][__][__]
[__][__][__][__]..

..[__]........[__]..
[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........

Unstable:
..[__]..
........

..[__]..
[__]....

..[__]..
....[__]

..[__][__]..
[__]....[__]
..[__][__]..
[__]....[__]

..[__][__][__][__]
[__][__][__][__]..
..[__][__][__][__]
[__][__][__][__]..

[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........

I'm pretty sure your definition of stability doesn't match the reality ;-)

@JanDvorak I know but who would want to golf a whole physics engine :P

........[__]....
......[__][__]..
....[__][__]....
..[__][__]......
[__][__]........
..[__].......... (you'll have to mentally stack those lines on top of each other. The point being that your rules allow structures whose centre of gravity is far offset from their point of contact with the ground. It should be possible to tighten them to avoid this, without needing a physics engine, if you felt like it.)

Yeah this challenge would be more fun if the bricks obeyed Newtonian mechanics!

Verisimilitude in the physics is a huge can of worms, however. One can come up with many simple cases where the stability depends on coefficient of friction and/or on the weight of the bricks on top.

"stable"…heh

80386 machine code, 98
The code:
60 8b f1 8b f9 b0 0a f2 ae 8b ef 2b ee b0 00 f2
ae 2b fe 83 ef 02 2b fd 72 41 03 f7 2b f5 33 c9
8a 7c 6e fc 8a 1c 6e b1 02 33 d2 8b c7 f7 f5 83
fa 02 75 03 b7 00 41 8a 66 fc 8a 06 3b fd 7d 02
33 c0 23 c3 0a c4 22 df 0b c3 f6 44 2e fe 01 74
04 d1 e8 73 06 2b f1 2b f9 73 c5 61 d1 d0 83 e0
01 c3

The code scans the ASCII art from the end to the beginning, jumping 2 characters at a time. This does twice the needed checks (it would be enough to jump 4 characters), but simplifies the logic.
Checking starts at the next-to-last row of characters (no need to check the last line). At each line, it starts 3 characters from the right (no need to check too far to the right). For each character, it checks 4 surrounding characters:
A...B
..X..
C...D

There is a bunch of logical conditions to check:

If A and C are brick characters, X is supported
If B and D are brick characters, X is supported
If C and D are brick characters, X is supported
If X is a brick character, it has to be supported; otherwise the structure is unstable

It's a lucky coincidence that all brick characters [_] have their LSB set; all other characters .\n have it clear. In addition, the 80386 instruction set has these handy "high" and "low" registers (ah, al, etc), which help parallelize the checks a bit. So all the checking amounts to some obscure bit fiddling.
I started from the following C code:
int check(const char* ptr)
{
    int width, result = 0, pos;

    width = strchr(ptr, '\n') - ptr + 1;
    pos = strlen(ptr) - 1 - width; // pos points to the B character
    ptr += pos - width;

    while (pos >= 0)
    {
        int a = ptr[-4];
        int c = ptr[-4 + 2 * width];
        int b = ptr[0];
        int d = ptr[0 + 2 * width];
        int ab = a << 8 | b;
        int cd = c << 8 | d;
        if (pos < width)
            ab = 0; // A and B don't exist; set them to 0
        int jump = 2; // distance to next brick
        if (pos % width == 2) // leftmost brick?
        {
            cd &= 0xff; // C doesn't exist; set it to 0
            ++jump;
        }
        int support_v = ab & cd;
        support_v = support_v | support_v >> 8; // data in LSB
        int support_h = cd & cd >> 8; // data in LSB
        int support = (support_v | support_h) & 1;
        if (!support & ptr[-2 + width])
            goto UNSTABLE;
        ptr -= jump;
        pos -= jump;
    }
    return 1;
UNSTABLE:
    return 0;
}

I translated the code to assembly language (it's mostly one-to-one), including a golfed implementation of strchr and strlen. The following source code is translated by MS Visual Studio to the machine code at the top of my post.
__declspec(naked) int __fastcall check(const char* ptr) // MS Visual Studio syntax
{
    _asm
    {
        pushad;

        // ecx = ptr
        mov esi, ecx; // esi = ptr
        mov edi, ecx
        mov al, 10;
        repne scasb;
        mov ebp, edi;
        sub ebp, esi; // ebp = width

        mov al, 0;
        repne scasb;
        sub edi, esi;
        sub edi, 2;
        sub edi, ebp; // edi = pos
        jc DONE;

        add esi, edi;
        sub esi, ebp;

        xor ecx, ecx; // ecx = jump

    LOOP1:
        mov bh, [esi - 4 + 2 * ebp]; // bh = C
        mov bl, [esi + 2 * ebp]; // bl = D
        // bx = CD
        mov cl, 2;
        xor edx, edx
        mov eax, edi
        div ebp;
        cmp edx, 2;
        jne LABEL2;
        mov bh, 0
        inc ecx;
    LABEL2:

        mov ah, [esi - 4]; // ah = A
        mov al, [esi]; // al = B
        // ax = AB
        cmp edi, ebp;
        jge LABEL3;
        xor eax, eax;
    LABEL3:

        and eax, ebx; // ax = support_v
        or al, ah; // al = support_v
        and bl, bh; // bl = support_h
        or eax, ebx; // eax = support
        test byte ptr[esi - 2 + ebp], 1;
        jz LABEL4; // not a brick character - nothing to check
        shr eax, 1; // shift the LSB into the carry flag
        jnc DONE;
    LABEL4:
        sub esi, ecx;
        sub edi, ecx;
        jnc LOOP1;

    DONE:
        // here, the result is in the carry flag; copy it to eax
        popad;
        rcl eax, 1;
        and eax, 1;
        ret;
    }
}

MATLAB - 119 bytes
Minified:
function c=S(B),f=@(m)conv2([(0&B(1,:))+46;B]+3,m,'valid');M=[2 0;-1 -1;0 2];c=isempty(B)||all(all(f(M)&f(fliplr(M))));

Expanded:
function c = isstable( B )

f = @(m) conv2( [(0&B(1,:))+46; B] + 3, m, 'valid' );
M = [2 0;-1 -1;0 2];
c = isempty( B ) || all(all( f( M ) & f(fliplr( M )) ));

Sample Usage:
S4 = [  '..[__][__]..'; ...
        '[__][__][__]'; ...
        '..[__][__]..'; ...
        '[__]....[__]'];

fprintf( 'S4: %d\n', isstable( S4 ) );

S4: 1

U4 = [  '..[__][__]..'; ...
        '[__]....[__]'; ...
        '..[__][__]..'; ...
        '[__]....[__]'];

fprintf( 'U4: %d\n', isstable( U4 ) );

U4: 0

Details
The routine appends a row of . to the top of the input matrix, then converts to a numeric matrix by adding 3 to the ASCII character codes. Given this conversion, a 2D convolution with the kernel
 2  0
-1 -1
 0  2

yields a matrix with 0 at locations where the character pattern
 . *
 _ _
 * .

is present, with * representing "any character". Because of the construction of the kernel, this is the only valid character pattern that will yield a 0.
An identical convolution is performed with the left-right flipped version of the kernel to detect
 * .
 _ _
 . *

An input is stable if either i) it is empty, or ii) no zeros appear in either convolution.
Two frustrations are

MATLAB's default convolution runs past the edges of the operand matrix, producing erroneous 0s in opposing corners for both convolutions, requiring ,'valid' (8 bytes) to be added to conv2 call to limit the output to the area where the convolution is valid.
Handling the empty string case adds 12 bytes.

JavaScript (E6) 131 261
F=a=>
  [...a].every((e,p)=>
    !(d={']':-3,'[':3}[e])
     |a[p-r]=='_'&(x=a[p+r]!=' ')
     |a[p-r+d]=='_'&(y=a[p+r+d]!=' ')
     |x&y
  ,r=a.search(/\n/)+1)

Test in FireFox/FireBug console
;['[__]', '  [__]  \n[__][__]', '        [__]        \n      [__][__]      \n        [__]        ',
 '  [__][__]  \n[__][__][__]\n  [__][__]  \n[__]    [__]',
 '            [__]  \n  [__][__][__][__]\n[__][__][__][__]  \n  [__][__][__][__]\n[__][__][__][__]  ',
 '  [__]        [__]  \n[__][__][__][__][__]\n  [__][__][__][__]  \n    [__][__][__]    \n      [__][__]      \n        [__]        ']
.forEach(x => console.log(x+'\n'+F(x)))

;['  [__]  \n        ', '  [__]  \n[__]    ' ,'  [__]  \n    [__]',
 '  [__][__]  \n[__]    [__]\n  [__][__]  \n[__]    [__]',
 '  [__][__][__][__]\n[__][__][__][__]  \n  [__][__][__][__]\n[__][__][__][__]  ',
 '[__][__][__][__][__]\n  [__][__][__][__]  \n    [__][__][__]    \n      [__][__]      \n        [__]        ']
.forEach(x => console.log(x+'\n'+F(x)))

Output
    [__]
true

  [__]
[__][__]
true

        [__]
      [__][__]
        [__]
true

  [__][__]
[__][__][__]
  [__][__]
[__]    [__]
true

            [__]
  [__][__][__][__]
[__][__][__][__]
  [__][__][__][__]
[__][__][__][__]
true

  [__]        [__]
[__][__][__][__][__]
  [__][__][__][__]
    [__][__][__]
      [__][__]
        [__]
true

  [__]
false

  [__]
[__]
false

  [__]
    [__]
false

  [__][__]
[__]    [__]
  [__][__]
[__]    [__]
false

  [__][__][__][__]
[__][__][__][__]
  [__][__][__][__]
[__][__][__][__]
false

[__][__][__][__][__]
  [__][__][__][__]
    [__][__][__]
      [__][__]
        [__]
false

Ungolfed
F=a=>(
  a=a.replace(/__/g,'').replace(/  /g,'.'),
  r=a.search(/\n/)+1,
  [...a].every((e,p)=>
    e < '0' ||
    (e ==']'
    ? // stable right side
     a[p-r]=='[' & a[p+r]!='.'
     |
     a[p-r-1]==']' & a[p+r-1]!='.'
     |
     a[p+r]!='.' & a[p+r-1] != '.'
    : // stable left side
     a[p-r]==']' & a[p+r]!='.'
     |
     a[p-r+1]=='[' & a[p+r+1]!='.'
     |
     a[p+r]!='.' & a[p+r+1] != '.'
    )
  )
)

What does [...a] do, if you don't mind my asking? I know ES6 allows ...arg as the last argument of a function to capture variadics, but I've never seen it used this way.

@COTO http://codegolf.stackexchange.com/a/37723/21348, use case 2 (it's very common, I use it in maybe 80% of my answers)

Sunofagun. Just like {:} in MATLAB. That's going to be very useful. Thanks. :)

Python 279
I think I am pretty bad in code golf challenges and maybe I use the wrong languages for that :D
But I love code that can be easily read :) Btw I would like to see a python code that uses less bytes!
def t(b):
    r=b.split()
    l=len(r[0])
    r=['.'*l]+r
    for i in range(len(r)-2,0,-1):
        r[i]+='...'
        for j in range(l):
            if(r[i][j]=='['):
                if(r[i+1][j]<>'_'or(r[i+1][j+3]<>'_'and r[i-1][j]<>'_'))and(r[i+1][j+3]<>'_'or r[i-1][j+3]<>'_'):
                    return False
    return True

Possible examples:
A = "..[__][__][__][__]\n\
[__][__][__][__]..\n\
..[__][__][__][__]\n\
[__][__][__][__].."
print t(A) #False

B = "..[__]........[__]..\n\
[__][__][__][__][__]\n\
..[__][__][__][__]..\n\
....[__][__][__]....\n\
......[__][__]......\n\
........[__]........"
print t(B) #True

I don't use the dots inside my code, actually your input can uses any char but not _ and  [

Generally instead of using <>, you would use !=.

@EthanBierlein wasn't sure but yes != is tge preferred way

JavaScript 2 (ES6) - 148 151 bytes
F=s=>s.split(/\n/).every((b,i,a)=>(r=1,b.replace(/]/g,(m,o)=>(T=z=>(a[i-1+(z&2)]||[])[o-z%2*3]=='_',r&=i>a.length-2?1:T(2)?T(3)|T(0):T(3)&T(1))),r))

Exepects a string of newline separated brick rows (note: if we could use a different separator character like "|" to separate rows this could be made 1 byte shorter).
Test in Firefox console with:
F('..[__]......\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // false
F('..[__][__]..\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // true

Python, 209
def s(b):
 c=b.split("\n");s="".join(c);l=len(c[0]);t=" "*l+s+"]]"*l;a=lambda x,y,z:t[x+l*y+z]=="]"
 return all([(a(i,1,1)&a(i,1,5))or(a(i,-1,1)&a(i,1,1))or(a(i,-1,5)&a(i,1,5))for i,x in enumerate(t)if x=="["])

Tests:
towers=(
"[__]",

"..[__]..\n"
"[__][__]",

"........[__]........\n"
"......[__][__]......\n"
"........[__]........",

"..[__][__]..\n"
"[__][__][__]\n"
"..[__][__]..\n"
"[__]....[__]",

"............[__]..\n"
"..[__][__][__][__]\n"
"[__][__][__][__]..\n"
"..[__][__][__][__]\n"
"[__][__][__][__]..",

"..[__]........[__]..\n"
"[__][__][__][__][__]\n"
"..[__][__][__][__]..\n"
"....[__][__][__]....\n"
"......[__][__]......\n"
"........[__]........",

"..[__]..\n"
"........",

"..[__]..\n"
"[__]....",

"..[__]..\n"
"....[__]",

"..[__][__]..\n"
"[__]....[__]\n"
"..[__][__]..\n"
"[__]....[__]",

"..[__][__][__][__]\n"
"[__][__][__][__]..\n"
"..[__][__][__][__]\n"
"[__][__][__][__]..",

"[__][__][__][__][__]\n"
"..[__][__][__][__]..\n"
"....[__][__][__]....\n"
"......[__][__]......\n"
"........[__]........",
)
[s(x) for x in towers]

Output:
[True, True, True, True, True, True, False, False, False, False, False, False]


text:
What are you waiting for? (A mahjong solver)
Idea thanks to @MartinBüttner from a discussion in chat
Mahjong is a tile game that is immensely popular in Asia. It is typically played with four players, and the goal of the game is to be the first person to complete a valid hand using the tiles. For this challenge, we will consider a simplified version of the game — PPCG mahjong.
In PPCG mahjong, there are three suits – m, p and s – and the tiles are numbered from 1 to 9. There are exactly four copies of each tile, and the tiles are denoted by its number followed by its suit (e.g. 3m, 9s).
A completed PPCG mahjong hand consists of four sets of three and a pair, for a total of 14 tiles.
A set of three can be either:

Three of the same tile (e.g. 4s 4s 4s, but not 4m 4p 4s), or
A sequence of three consecutive tiles in the same suit (e.g. 1s 2s 3s or 6p 7p 8p but not 3s 4m 5m or 3p 5p 7p). Sequences do not wrap (so 9m 1m 2m is invalid).

A pair is simply two identical tiles (e.g. 5s 5s).
The challenge
Your program will receive a space-separated hand of 13 tiles, with each tile appearing no more than four times. You may write either a full program or a function which takes in a string.
Your task is to find all possible 14th tiles ("waits") which, when added to the hand, would form a completed PPCG mahjong hand. The outputted tiles should be space-separated, but can be in any order. Leading or trailing whitespace is allowed.
Your program should run in a reasonable amount of time, no longer than a minute.
Examples
Input: 1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s
Output: 9s

Input: 1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p
Output:

Input: 1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s
Output: 1s

Input: 1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m
Output: 1m 2m 3m 4m 5m 6m 7m 8m 9m

Input: 1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s
Output: 1m 4m 6s 9s

In the first example, the 1m 4s 7p 3m all form existing triplets, leaving the lone 9s to form a pair.
In the second example, the 2s 3s and 7p 8p can only form sequences, and the remaining tiles can only form triplets. Hence no pair can be formed, and there is no output.
In the third example, the hand splits into 1m2m3m 2m3m4m 3m3m 1s1s 9s9s9s. Normally this would be a wait for 3m 1s, but as all four 3m have been used, the only available wait is 1s.
In the fourth example, all of the m tiles complete the hand. For example, for 1m, one could have 1m1m1m 1m2m3m 4m5m6m 7m8m9m 9m9m which is a completed hand.
Try to work out the rest of the fourth example and the fifth example :)
Scoring
This is code-golf, so the solution in the fewest bytes wins. Standard loopholes apply.

Thank you for actually doing Mahjong, rather than the (IMO annoying) solitaire using the tiles that westerners seem to think of whenever they hear the word "Mahjong".

@Quincunx Fun fact: This challenge came about because I wanted to do a challenge with an ASCII representation of Mahjong solitaire (which I might still do at some point...). I did call it "Mahjong solitaire" though. ;)

@Quincunx: I don't think it's their fault. It's game developers' fault for calling their "Mahjong solitaire" games "Mahjong" and nothing else.

What about seven pairs? thirteen orphans? you could do something even more complex with honors :) Do you think it's out-of-purpose if I create a codegolf that asks to calculate the shanten (minimal number of tiles needed before getting tenpai - ready to win) of a hand?

@VCourtois It's been a while, but I recall specifically excluding seven pairs, thirteen orphans, honours and already made calls so as to not overcomplicate the challenge for people new to the game. I think I considered making a shanten challenge later after that but never did in the end - if you'd like to post one I think it'd make a fine challenge.

Python, 312 281 bytes
def W(S):H=lambda C,n=0,t=1:sum([m<C[0]and H([c-s for c in C][:l]+C[l:],n+1,u)for m,s,l,u in(2,3,1,t),(t,2,1,4),(4-5*all(C[:3]),1,3,t)])|H(C[1:],n,t)if C[2:]and max(C)<5else n>4;T=[i+s for s in"mps"for i in"12345678900"];return" ".join(t for t in T if("1"<t)*H(map((S+t).count,T)))

W takes a string as input and returns a string as output.
The small number of tiles (27) makes it fast enough to test if each of them completes the hand.
The problem becomes to check if a hand is valid.
The function uses a simple backtracking algorithm that considers all possible choices of sets and checks if any of them adds up to a complete hand.
Hands are represented as tile histograms, i.e. a list of tile counts (for all the tiles, not only the ones present in the hand.) This makes it easy to both check if we have a certain number of a certain tile, and if we have a sequence of adjacent tiles (padding between tiles of different suits prevent multi-suit sequences.)

Ah, you beat me :P Anyway, it looks like you can use map in a couple of places, like: H(map((S+t).count,T))

@FryAmTheEggman Missed that. Thanks!

@Sp3000 It's Python 2. That's strange; it works fine for me on 2.7.8.

@Ell Works in 2.7.8 - 2.7.5 didn't like the 5else :P

JavaScript (E6) 306
F=h=>(
  R=(a,p,n=1)=>(a=[...a]).splice(p,n)&&a,
  K=(t,d=3)=>
    !t[0]
    |t.some(
      (v,p)=>
        v==t[p+1]&v==t[p+d-1]&&
        K(R(t,p,d))
      ||
        ~((r=t.indexOf((x=-~v[0])+v[1]))|(s=t.indexOf(-~x+v[1])))&&
        K(R(R(R(t,s),r),p))
    ),
  o=[],
  [for(s of'mps')for(i of'123456789')h.replace(t=i+s,s,'g')[34]
  &&K([t,...h.split(' ')].sort(),2)&&o.push(t)
  ],o
)

Explained
F=hand=>(
  Remove=(a,p,n=1)=>                // function to remove 1 or more element from an array, returning a new shorter array
    ((a=[...a]).splice(p,n), a),    // using array.splice on a new created array

  Check=(ckHand, dim)=>  // recursive function to check hand.
                         // removing pairs (at iteration 0) or sequence of three, if at last the hand remain empty then success
                         // parameter dim is 2 or 3 indicating how many equal elements are to be removed
    !ckHand[0]           // check if empty (element 0 does not exist)
    |ckHand.some(        // else traverse all array checking what can be removed
      (value, position)=>
        value == ckHand[position + 1]
        & value == ckHand[position + dim-1] &&   // look for 3 (or 2) equal elements
        Check(Remove(ckHand, position, dim), 3)   // if found, then remove elements and check again
      ||
        ~((r = ckHand.indexOf((x=-~value[0]) + value[1]))     // value[0] is number, value[1] is suit
        |(s = ckHand.indexOf(-~x + value[1]))) &&              // look for an ascending sequence in following elements (the array is sorted)
        Check(Remove(Remove(Remove(ckHand, s), r), position),3) // if sequence found, remove elements and check again
    ),
  output=[], // start with an empty solution list
  [ // using array comprehension to implement a double loop
    for(s of'mps')        // loop for all suits
    for(i of'123456789')  // loop for all numbers
    (
       tile=i+s, // current tile
       (hand.replace(tile,' ','g').length > 34)      // if tile is present 4 times in hand, the replaced length is 38-4 == 34
       && (                                       // else proceed with check
         ckHand = hand.split(' '),
         ckHand.push(tile),    // in ckHand (as an array) the hand to be checked, that is base hand + current tile
         ckHand.sort(),        // sorting the array simplfy the checks
         Check(ckHand, 2)      // start checks looking for a pair
       )
       &&
         output.push(tile)   // if check ok, add tile to the solution list
    )
  ],
  output // last expression in list is the function return value
)

Test in FireFox/FireBug console
;["1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s", "1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p",
 "1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s", "1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m",
 "1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s"].forEach(s=>console.log(s+' => '+F(s)))

Output
1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s => 9s
1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p =>
1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s => 1s
1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m => 1m,2m,3m,4m,5m,6m,7m,8m,9m
1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s => 1m,4m,6s,9s

JavaScript (Node.js), 241 bytes
s=>[...Array(i=27)].flatMap(_=>A([...s,k=--i%9+1+'mps'[i/9|0]])>/^(..)(.*\1){4}/.test(k+s)?k:[])
A=s=>s.some(t=>R(s,t,t,t)|t[1]<'z'&R(s,t,t[0]-1+t[1],t[0]-2+t[1]))|s[0]==s[1]&!s[2]
R=(s,p,q,r,z=0,k=s.filter(y=>y!=p||z++))=>p?z&&R(k,q,r):A(s)

Try it online!
Came from the more complex checker and made small changes

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


text:
Pixel-art, episode 1: display Super Mario
it's a-me!
Today's task is simple: write a program, or a function that displays the idle small Mario sprite, from Super Mario Bros, on NES, over a blue background.
Any kind of entry is valid as long as it displays those 12 * 16 pixels anywhere on the screen / window / browser.
(EDIT: the displayed image can be scaled up if your language can't do pixel art. You can also output ASCII art or HTML art, but using the right colors.)
Image (zoomed 400%):

You must use the following colors:

blue: #6B8CFF
red: #B13425
green/brown: #6A6B04
orange: #E39D25

Shortest program (in number of characters) wins!
Standard loopholes apply (especially, no network connexion allowed), but hardcoding and displaying an image file in your program is allowed. (entries using this trick will be rank separately)
Here we go!

Current Leaderboard
Shortest answer using code only:

Mathematica, 141. https://codegolf.stackexchange.com/a/39916/10732 (by Martin Büttner)
Bash, 158. https://codegolf.stackexchange.com/a/40002/10732 (by hpsMouse)
...

Shortest answer using some kind of hardcoded image:

HTML, 102b. https://codegolf.stackexchange.com/a/39923/10732 (by xem and NiettheDarkAbsol)
PHP, 131b. https://codegolf.stackexchange.com/a/39926/10732 (by NiettheDarkAbsol)
...

Also, creating a file is not allowed? It has to be displayed?

I don't see any pattern in that image. So it all comes down to the best compression one can use in a language.

@Optimizer Looks like RLE could work well.

Sorry for the mistakes, I fixed them and added a zoomed version of the image. @MartinBüttner you can create a file but your program must display it. And yeah, it's a basic compression challenge.

@Optimizer no pattern, but there's a lot of symmetry in the lower half on the image

@xem damn, no CJam then ;)

why, CJam is afraid of symmetry?

@xem no color output in CJam. Only text in one color

@Optimizer or an image ;)

Nitpicking: That's Mario, not Super Mario.

It's Mario Mario actually. But Super Mario is more popular :P

I would like to see someone do this in .NET

As a random added thing, the number of character changes required to convert from normal Red-outfit Mario to Fireball-launching White-outfit Mario. Haha :P

What a fun idea...Here's an idea for a sequel challenge: Take the Mario image (Any format) and turn it into an image of Luigi!

Can we make a piet program that looks like him?

Can output be to the terminal (i.e colorama in Python)?

sure, no prob...

Q. Regaring the category "code only"... does using a single HTML element only for the purpose of injecting JS output disqualify an entry in that category?

Q. Regarding HTML output... instead of line breaks to denote rows in the grid, is it within the rules to rely on the browser window being sized particularly so its contents wrap automatically to produce the same effect?

@bumpy yep, you're free to use a single HTML element and rely on resizing

@xem, you would not happen to have any copies of the original images, would you? The posted links are showing 410: Gone Errors

@TaylorScott thanks for the notification! fixed.

HTML/JS, 206 158 153 102

102
Trick used: save the compressed GIF file as an HTML file, and add  at the end
Thanks to this entry: https://codegolf.stackexchange.com/a/39926/10732 by @NiettheDarkAbsol
GIF87a  ¡ kŒÿã%jk±4%,       6„‡héj„Af-ÕdÎy\%    …R˜0”ŒÈJ³I©±²û“ú=ª$±p%i¸•¤

Demo: http://meuziere.free.fr/mario/gif.html

Older versions:
153
Trick used: save the compressed PNG file as an HTML file, and add  at the end
‰PNG

IHDR         _v”   PLTEjkkŒÿ±4%ã%ó’V   IIDAT×c[Êµj%C€ÍUŸ?|ìíœÿ02„ÿÿÊÐÊàÐÄÈÀ°ŠáÓë~†«ö3üZµž!jÚR‡P x( s6ïåÇ

158
Trick used: setting the trimmed dataURI of a compressed PNG as the SRC of an IMG tag and packing the whole thing in Unicode chars.

Execute that in your JS console:
document.write(unescape(escape('').replace(/uD./g,'')))

206
Unpacked (206b):

Demo

Tools used:

https://tinypng.com/
http://xem.github.io/miniURI/input.html
http://xem.github.io/obfuscatweet/

You don't need the tags. Just use the chrome's data uri and enter it in your url bar. 200 characters

Hm... I considered that dataURI isn't a valid "program". But you're right. All browsers allow dataURIs in the addressbar.

Now you're using a loophole yourself as the OP ;). You're offloading all work to the external/built-in compression of the GIF format. If that's cool we should all go hunting for obscure image formats with the best compression rate now, and I could have saved myself a lot of work writing my own compression. ;)

I edited the OP: there will be a ranking for hardcoded images and a ranking for ... not. ;)

@xem Well, your challenge, your call. But it seems a bit pointless if we're now just looking for the most compressed existing file format. ;)

Let's see that as a "side challenge". also, posting an image file is not valid: it has to be a program. HTML can't display much formats (bmp, png, gif, jpg, ...that's about it). And if another language than HTML can contain hardcoded images, I'm interested to see that. :)

Could you provide the HTML files Base64-encoded? Your external hosting seems to be down, and the in-answer text isn't copy-pasteable.

I provided a working url for the 102b file ;)

Does not display in MSIE 11.0.13

Yeah, saving an image file as HTML is a hack that IE doesn't understand (yet). But ... IE ... let's don't care about it :p

It appears the rawgit link is dead.

Mathematica, 412 292 252 212 163 148 143 141 characters
f=FromDigits[ToCharacterCode@#,2^16]~IntegerDigits~#2&;Image@Partition[f["넴╫賿橫ӣ鴥",256][[3#+1;;3#+3]]/256&/@"吀啐^A媾핮﻽溿뽫ﺩ埿⩕樨ꦪª⿼?ཐᐅ橕ꦪ喪"~f~4,12]

This uses caret notation ^A for the control character at code point 1. In Mathematica, I can actually embed the character literally, although that leads to all sorts of ugliness when copying things around. Anyway, the above is 2 characters shorter than my former version, and I got those to characters from using base-4 instead of base-5 to encode the colour palette indices. Right now I cannot be bothered to fix the explanation and screenshot below, so I'm leaving you here with the original base-5 version of my answer:

f=FromDigits[ToCharacterCode@#,2^16]~IntegerDigits~#2&;Image@Partition[f["넴╫賿橫ӣ鴥",256][[3#-2;;3#]]/256&/@"ᯱ曎㌟뱮䚻륏Σ襺ﺦ您汜豈塘ᙉ雬儥衰ꐰꃾ纔ㆯ쭴뫋澖ᕿ蓉"~f~5,12]

I'm encoding the pixels in Unicode characters (yay for counting by characters!).
Here is what it looks like in Mathematica:

Here's how it works:
First we define a function f that turns Unicode strings (passed in as the first argument #) into lists of integers. First we obtain the character codes. Those can be interpreted as digits of a base 65536 number. And then we convert that number to another base, passed in as the second argument #2.
Now let's do that for the longer Unicode string. ToCharacterCode yields this list:
{7153, 26318, 13087, 48238, 18107, 47439, 931, 35194, 62191, 65190, \
 24744, 57782, 27740, 35912, 22616, 5705, 38636, 20773, 34928, 42032, \
 41214, 32404, 12719, 52084, 47819, 28566, 5503, 33993}

Treating this as base 65536:
7933607912575313477287527915733176998797205587959732019781370103381...
4831246938139171755469819519515972565671101475553962564506286523593

And converting to base 5:
{2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
 2, 2, 2, 3, 3, 3, 4, 4, 3, 4, 2, 2, 2, 2, 3, 4, 3, 4, 4, 4, 3, 4, 4, \
 4, 2, 2, 3, 4, 3, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 4, 4, 4, 4, 3, 3, \
 3, 3, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 3, 3, 1, 3, 3, 3, \
 2, 2, 2, 2, 2, 3, 3, 3, 1, 3, 3, 1, 3, 3, 3, 2, 3, 3, 3, 3, 1, 1, 1, \
 1, 3, 3, 3, 3, 4, 4, 3, 1, 4, 1, 1, 4, 1, 3, 4, 4, 4, 4, 4, 1, 1, 1, \
 1, 1, 1, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 2, 2, 1, 1, 1, \
 2, 2, 1, 1, 1, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 3, \
 2, 2, 2, 2, 3, 3, 3, 3}

Those are the colour indices of the pixels, in order blue, red, green, orange. We use those to index into that list of numbers, which is the colour palette.
Now for the colour palette. That's "넴╫賿橫ӣ鴥". We use the above indices to select the correct string. Then we apply our function again, but using base 256. That yields a list of 12 integers:
{177, 52, 37, 107, 140, 255, 106, 107, 4, 227, 157, 37}

We use ;; range indexing to pull out the relevant slice for the current colour.
Lastly, we just use Partition to split this into rows of 12 and feed it to Image. Voilà!
Edit: With the Unicode packing the RLE was no longer worth it. Removing it saved 50 characters.
Edit: Of course, without RLE, there's also no need to go to base 16.
Edit: And while we're at it, why not Unicode-pack the colour palette, too? (I have a hunch that I can save a little bit more by make the entire colour palette also a single string and using Partition there too. I'll try that later.)
Edit: Yes, that did shave off another 5 bytes.

would you mind adding a screenshot of the result? (not that I don't trust your code, but curious about how it's displayed: in a window? a browser? else?)

@xem Will do. It's a REPL environment capable of graphical in- and output.

Not sure, but are you mirroring the lower portion of the image ?

@Optimizer No, I doubt I'd be able to do that in less characters than I'd be saving.

When I look in the Mathematica documentation I don't see any usage on tilde but it appears here that you're using it to feed the result of one function into another and then apply an additional argument to that second function (IntegerDigits)? Also, the color palette: looking at the image, it appears there are only four colors, but your color palette seems to include more than that: {177, 52, 37, 107, 140, 255, 106, 107, 4, 227, 157, 37}. Looking at the documentation for Image, it looks like it prints out grayscale unless additional options like ColorScale --> RGB is provided.

Man, the unicode encoding is just a joy to read. This is good.

@JavaNovice14085 The tilde is syntactic sugar to use infix notation. I.e. a~f~b is the same as f[a,b]. Precedence is  a bit tricky. It's left associative so a~f~b~g~c is g[f[a,b],c] and has lower precedence than @ (f@a is syntactic sugar for f[a]) but higher precedence than the Map and Apply short forms. The colour palette really is {{177, 52, 37}, {107, 140, 255}, {106, 107, 4}, {227, 157, 37}}, but I'm using an unrolled array and [[3#+1;;3#+3]] accesses a slice of three consecutive elements.

Java : 398 377
void s(){new java.awt.Frame(){public void paint(java.awt.Graphics g){int i=0,x,m[]={12226,44085194,467839834,0x5abea55a,0x5bbd5d50,0x5ffe9540,0x5ffe9540,0x5aee5d50,531408218,334277466,333492170,0xc02fc2},c[]={7048447,0xB13425,6974212,0xE39D25};for(setSize(99,99);i<192;g.setColor(new java.awt.Color(c[m[x]&3])),m[x]/=4,g.drawLine(x+40,60-i%16,x+40,60-i++%16))x=i/16;}}.show();}

Simply draws the sprite by unpacking an int for each column. Shown in a full program:
class P{
    public static void main(String[]a){
        new P().s();
    }

    void s(){
        new java.awt.Frame(){
            public void paint(java.awt.Graphics g){
                int i=0,x,m[]={12226,44085194,467839834,0x5abea55a,0x5bbd5d50,0x5ffe9540,
                               0x5ffe9540,0x5aee5d50,531408218,334277466,333492170,0xc02fc2},
                          c[]={7048447,0xB13425,6974212,0xE39D25};
                for(setSize(99,99);i<192;
                    g.setColor(new java.awt.Color(c[m[x]&3])),m[x]/=4,
                    g.drawLine(x+40,60-i%16,x+40,60-i++%16)
                )x=i/16;
            }
        }.show();
    }
}

Obligatory screenshot:

You can save 9 bytes by using an import java.awt.*.

x86 Machine Code, 102 bytes
How it works: The image is stored as a 2-bit image using a palette. Each row of the image is stored as 3 bytes, followed by one 1 byte of the color palette. This allows the data to be loaded as a single DWORD. The twelve pixels are output by masking off the lowest 2 bits of the value, writing them to video memory, and then right-shifting the entire value two bits. Once the pixels for the row have been outputted, the palette byte is written to the VGA palette. When the image is finished drawing, the program enters an infinite loop.
Assembly code to generate the binary:
org 100h
mov al,13h
int 10h
les ax,[bx]

mov si,image_data
draw:
add di,320-12
lodsd
xchg eax,ebx
mov cl,12
row:
mov ax,bx
and al,3
stosb
shr ebx,2
loop row
xchg ax,bx
mov dx,0x3c9
out dx,al
test al,al
jnz draw

image_data: db 21,0,85,0xb1/4, \
5,0,64,0x34/4,            \
165,190,87,0x25/4,        \
185,191,127,0x6b/4,       \
185,254,254,0x8c/4,       \
233,191,106,0xff/4,       \
213,255,95,0x6a/4,        \
165,168,85,0x6b/4,        \
169,40,106,0x4/4,         \
170,0,170,0xe3/4,         \
47,195,248,0x9d/4,        \
63,0,252,0x25/4,          \
15,0,240,111,             \
5,20,80,111,              \
169,85,106,111,           \
170,85,170

Base-64 encoded binary, save it as Mario.com to run it:
sBPNEMQHvigBgcc0AWatZpOxDInYJAOqZsHrAuL1k7rJA+6EwHXiwxUAVSwFAEANpb5XCbm/fxq5/v4j6b9qP9X/XxqlqFUaqShqAaoAqjgvw/gnPwD8CQ8A8G8FFFBvqVVqb6pVqg==
Sample output:

Octo/XO-Chip, 70 bytes
Octo is a high level assembly language that compiles down into bytecoded instructions for the CHIP-8 virtual machine. Octo provides some custom extensions called "XO-Chip" to the basic CHIP-8 bytecode, including the ability to draw 4-color bitmaps via overlaid bitplanes.
The compiled bytes are as follows:
0xA2 0x08 0xF3 0x01 0xD0 0x00 0x1F 0x00 0x3F 0xC0 0x39 0x00 0x51 0x00 0x58 0x80
0x21 0xE0 0x00 0x00 0x3F 0x00 0x7F 0xE0 0xFF 0xF0 0x36 0xC0 0x1F 0x80 0x3F 0xC0
0x39 0xC0 0x70 0xE0 0xF0 0xF0 0x00 0x00 0x00 0x00 0x3F 0x80 0x7F 0xE0 0x7F 0xF0
0x3F 0xE0 0x1F 0xC0 0x37 0x00 0x76 0xE0 0xF0 0xF0 0xE9 0x70 0xE0 0x70 0xC0 0x30
0x00 0x00 0x70 0xE0 0xF0 0xF0

Run it here in your browser: http://johnearnest.github.io/Octo/index.html?gist=33aa37d4717a425ccd4f
It is probably more illuminating to see the Octo assembly language which produces that bytecode:
: main
    i := mario
    plane 3
    sprite v0 v0 0

: mario
    0x1F 0x00 0x3F 0xC0 0x39 0x00 0x51 0x00
    0x58 0x80 0x21 0xE0 0x00 0x00 0x3F 0x00
    0x7F 0xE0 0xFF 0xF0 0x36 0xC0 0x1F 0x80
    0x3F 0xC0 0x39 0xC0 0x70 0xE0 0xF0 0xF0
    0x00 0x00 0x00 0x00 0x3F 0x80 0x7F 0xE0
    0x7F 0xF0 0x3F 0xE0 0x1F 0xC0 0x37 0x00
    0x76 0xE0 0xF0 0xF0 0xE9 0x70 0xE0 0x70
    0xC0 0x30 0x00 0x00 0x70 0xE0 0xF0 0xF0

The main program is three two-byte instructions. Set the memory index register i to the beginning of the data segment, select drawing plane 3 (3 is a bitmask; this indicates you wish to draw in 4 color mode with both bitplanes) and then draw a sprite at an x and y position given by register v0 (initialized to zero). The final 0 provides the size of the sprite, which in the SuperChip and XO-Chip instruction sets will draw a 16x16 sprite. In 4 color mode, a bitmap for the first plane is followed immediately by a bitmap for the second plane.
To see how the planes work, consider this modified program which scrolls one plane to the right after drawing mario:

: main
    i := mario
    plane 3
    sprite v0 v0 0
    plane 2
    scroll-right
    scroll-right
    scroll-right
    scroll-right

: mario
    0x1F 0x00 0x3F 0xC0 0x39 0x00 0x51 0x00
    0x58 0x80 0x21 0xE0 0x00 0x00 0x3F 0x00
    0x7F 0xE0 0xFF 0xF0 0x36 0xC0 0x1F 0x80
    0x3F 0xC0 0x39 0xC0 0x70 0xE0 0xF0 0xF0
    0x00 0x00 0x00 0x00 0x3F 0x80 0x7F 0xE0
    0x7F 0xF0 0x3F 0xE0 0x1F 0xC0 0x37 0x00
    0x76 0xE0 0xF0 0xF0 0xE9 0x70 0xE0 0x70
    0xC0 0x30 0x00 0x00 0x70 0xE0 0xF0 0xF0

If you enjoy this you might like one of my other solutions written with Octo. There's actually a game jam going on for the month of October based around this tool.

Bash + ImageMagick: 350 331 321 characters
(Palette shamelessly stolen from Martin Büttner's answer.)
p=(B13425 6B8CFF 6A6B04 E39D25)
for c in 21 0 85 5 0 64 165 190 87 1{85,91,27,85} 254{,} 233 191 106 213 255 95 165 168 85 169 40 106 170 0 170 47 195 248 63 0 252 15 0 240 5 20 80 169 85 106 170 85 170;{
for j in 0 2 4 6;{
d+=(-fill \#${p[c>>j&3]} -draw point\ $[i%12],$[i++/12])
}
}
convert -size 12x16 xc: "${d[@]}" x:

Sample output:

To inspect it easily add -scale 120 to convert's parameters to get a 10x scaled version:

s/185 191 127 185 254 254/1{85,91,27,85} 254{,}/; s/do/{/; s/done/}/

Doh. I even upvoted DigitalTrauma's related tip, but I keep forgetting that {..}. Thank you, @grawity.

GIF - 93 bytes
Hardcoding the image is apparently okay now, so... yay? :D
GIF87a  ¡ kŒÿã%jk±4%,       6„‡héj„Af-ÕdÎy\%    …R˜0”ŒÈJ³I©±²û“ú=ª$±p%i¸•¤  ;

As seen in Notepad++

As PHP - 131 bytes
<? header("Content-Type:image/gif");?>GIF87a  ¡ kŒÿã%jk±4%,       6„‡héj„Af-ÕdÎy\%  …R˜0”ŒÈJ³I©±²û“ú=ª$±p%i¸•¤  ;

can you please upload your gif somewhere (ctrlv.in for example)? I'd like to use it in my entry instead of PNG :)

@xem http://adamhaskell.net/img/mario.gif

@NiettheDarkAbsol I'm not sure how you counted the size of that, but I count 150 bytes. Regardless, scoring is by characters, and it seems to be 114 characters.

@MartinBüttner I'm using the windows-1252 character set, so things like ÿ are a single byte (0xff here) whereas they wouldn't be "normally". NP++ gives the length in characters and shows 93, and the file saved on my computer is also showing 93 bytes.

I see. I guess in that case your score for PHP would be 131 both in bytes and characters.

I think hardcoding is fine for kolmogorov complexity challenges, because they do require you to output a fixed image. I think the relevant loophole here is more like "using built-in functionality to do the work"... which in this case is the compression/decompression built into the browser rendering your compressed GIF.

I made a 102b html answer using this gif. thanks :D

PS: I also trimmed the last 2 bytes of the GIF. It seemed to work fine without them.

@NiettheDarkAbsol I just noticed that the OP explicitly lifted this loophole, so if you make an edit to the post I'll remove my downvote.

@MartinBüttner Edit made =3

Yup, the PHP snippet is fine for me (even if you could remove the last 2 bytes). But the raw gif snippet isn't a program.

@xem: If the browser is considered an "interpreter" for HTML/javascript/etc, and feeding it the raw gif snippet via the same mechanism results in the desired output... the difference becomes small

@MooingDuck indeed.

In two places it says that your GIF is actually 78 bytes long...

@BetaDecay Where does it say that?

Here, here and here.

@BetaDecay Have you considered that those counters expect text, not binary data? I provided the Notepad++ screenshot which clearly shows length : 93

Groovy 417 386
Fun as hell, but with a terrible char count. GroovyFX needed
m=[b:'6B8CFF',r:'B13425',g:'6A6B04',o:'E39D25'];groovyx.javafx.GroovyFX.start{stage(visible:!0){scene(width:60,height:80){flowPane{"3b5r4b2b9r1b2b3g2o1g1o3b1b1g1o1g3o1g3o1b1b1g1o2g3o1g3o1b2g4o4g1b3b7o2b2b2g1r3g4b1b3g1r2g1r3g1b4g4r4g2o1g1r1o2r1o1r1g2o3o6r3o2o8r2o2b3r2b3r2b1b3g4b3g1b4g4b4g".toList().collate 2 each{l->(l[0]as int).times{rectangle(width:5,height:5,fill:"#"+m[l[1]])}}}}}}

ungolfed:
m=[b:'6B8CFF',
   r:'B13425',
   g:'6A6B04',
   o:'E39D25']

s=5

groovyx.javafx.GroovyFX.start {bd->
  stage(visible: !0) {
    scene(width:s*12, height:s*16) {
      flowPane {
        "3b5r4b 2b9r1b 2b3g2o1g1o3b 1b1g1o1g3o1g3o1b 1b1g1o2g3o1g3o 1b2g4o4g1b 3b7o2b 2b2g1r3g4b 1b3g1r2g1r3g1b 4g4r4g 2o1g1r1o2r1o1r1g2o 3o6r3o 2o8r2o 2b3r2b3r2b 1b3g4b3g1b 4g4b4g"
          .replaceAll(" ", "")
          .toList()
          .collate(2)
          .each { l->
            t=l[0] as int
            cr=m[l[1]]
            t.times {
              rectangle(width:s, height:s, fill:"#"+cr)
            }
          }
      }
    }
  }
}

grep() instead of toList()

HTML/JS, 427 408 264 256 239 226 chars
Obfuscatweet, 271 270 264 256 239 226 chars
Using obfuscatweet, managed to shorten this down to < 250 :D
document.write(unescape(escape('').replace(/uD./g,'')))

Code below is what this consists of.
Trick used: converted image to base4 String of color tiles, converted this into a hexadecimal String. Index of the base 4 denotes color (0=blue, 1=RED, etc.) CSS with an inline p is used to because divs need content to expand (also p is shorter). Because CSS needs to begin with a letter, 'A' is prepended before the CSS tags.
Padding from the CSS gives pixels. None of this uses Unicode characters, which I'm not too familiar with anyways, though it'd probably go sub-300 in that case. The relative advantage to using the padding is that you can, as in this case, blow up the image to whatever size you want each pixel to be. I've used 9 pixels, but if you spend an extra character, you can get up to 99 pixels per represented pixel.

CSS, 127 119 118 114 100 13 0 chars
Switching from p to rp removes the need for display:inline, cost +1 char, -15! chars!
Removed all the colors and put it into an array in JS -87 chars. Then I just removed all the css
JS, 300 289 280 275 329 325 chars
c=["6B8CFF","B13425","6A6B04","E39D25"];a='0155000555540ABEC02EFEFC2EBFBF2BFEA803FFF00A6A002A69A8AA55AAF9D76FFD557FF5555F0541502A00A8AA00AA';with(document)for(i=0;i<96;write('
')){h=('000'+parseInt(a.slice(i,i+=6),16).toString(4)).slice(-12);for(j=0;j<12;write('<rp style="padding:1 8;background:#'+c[h[j++]]+'"></rp>'));}

I tried to cut as much as I could out of this plain JS processing a hex string, but given as it's my first try, this is how far I got using only what I know. The HTML writing has been shortened by a function that adds tags, and the classes use the base 4 value to determine the color to display.
Using additional shortening, replaced charAt with [] brackets, and removed the A0 class and set blue as default color for p, saving additional 10 characters. The additional cost to use rp tags is offset by a huge loss in CSS.
Additional offset from removing the while loop pad to just adding '000' for the use case and slicing -12 from it.
Added additional JS for colors, then put the padding in there. Noticed a bug with the padding that requires 2 extra characters to fix. Compacted a bunch of loops
HTML File, 430 429 419 399 366 342 chars
Demo

Nice! I'd advise you to remove all the line breaks in your code, and provide a link for a demo ( http://c99.nl ). As a bonus, you could pack your entry in Unicode chars using http://xem.github.io/obfuscatweet/. That will improve your score.

also, you can remove your  tags, place the

authors: Дима Анатольевич


text:
Javascript: Mini Space Invaders
I'm pretty new to code golfing, so I gave one of my first shots to a space invader clone called "Invas!on". It's a little less than 500 bytes, fully ASCII generated, and covers moving around and shooting at the aliens. There is also a little point system.
My specific question is about generating enemy patterns. I want to generate something like this:
...x.x.x.x.x.x...
..x.x.x.x.x.x.x..
...x.x.x.x.x.x...

...and so on.
Currently, I'm using this code:
for(b=[],j=2;j<136;j+=2)b.push(j),j==14&&(j=41)||j==55&&(j=80)||j==94&&(j=121)

It's just a loop that pushes enemy positions into an array b. Positions are every two spaces on a line, with a varying margin on both sides.
What is the shortest way to do this?

Although asking for golfing advice is on on-topic here, this seems a bit too broad for the scope of CodeGolf.SE. I don't know what the people at CodeReview.SE think about questions trying to shorten code, but in principle this sounds like it would be suitable over there.

@MartinBüttner: Won't they just kick it back here? CR.SE is about code improvement, not code reduction. Sending them golfed code is like serving up regurgitated meatballs to a master chef and asking "How can I make this better?"

Ok, thanks for the advice. I specified my question.

you could send it on http://www.reddit.com/r/tinycode/. There are good advices here.

Nope, @xem but http://codereview.stackexchange.com/

@DavidSkx - I updated the question to be a bit more interesting and challenging. Feel free to revert back if you don't like it.

@Optimizer I've rolled your edit back because I don't think we need to strengthen the impression that asking for golfing advice isn't welcome here. By completely changing it into a kolmogorov challenge, it does give that feeling. No offense intended, obviously.

@Geobits This basically is a kolmogorov challenge which asks for a shorter code to get the job done. Anyways, OP can rollback tomy rev if he likes it.

@Optimizer Yea, I don't rollback very often, this one just felt off to me. I agree it could go either way.

58 : -20 bytes(25%) from OP
for(b=[],j=2;j<136;j+=j==14||j==94?29:j==55?27:2)b.push(j)

This should do the same thing as your code, but without all the ugly parentheses and explicit assignments. Since all you're really doing is adding each time, all you have to do is check how much to add.
I should note that I have no idea where you got the numbers from in the original code. Since it doesn't seem to match the pattern you gave, I assume the pattern is just an example (and the actual lines are longer), or there's something going on in your other code (not shown here). Either way, I matched up my positions with yours.

For a fixed pattern like this, though, it  might be shorter to just encode it in a bitmap-style string or bitmasked integer. Doing it loop-style allows you to vary it a bit easier, but if your pattern is constant it's something to be aware of. For instance, your shown pattern has 51 positions, which are either "on" or "off". This means it needs 51 bits for a straight bitmask, which can fit in a single number:
000101010101010000010101010101010000010101010101000 = 0xAAA0AAA82AA8

So, if you can unpack that into an array efficiently, you may be able to score some more bytes. Unfortunately, I'm no Javascript whiz, so I couldn't get it shorter this way, leaving it at 61 bytes. Others may be able to improve upon this:
for(b=[],j=0,m=0xAAA0AAA82AA8;m>0;m>>>=1,j++)if(m&1)b.push(j)

So for this exact pattern, the first method is shorter (for me). If the pattern wasn't so evenly spaced (allowing simple additions), the second would most likely end up shorter.

You have to do m = m >>> 1, otherwise it is a signed integer, so m > 0 will fail. This can be made m>>>=1

@soktinpk Thanks for that :D

This is incredible, great work.

I'm getting a problem with for(b=[],j=0,m=0xAAA0AAA82AA8;m>0;m>>>=1,j++)if(m&1)b.push(j), it only registers an array of 13 elements, which seems to only account for the first two rows... What's happened to the third row?


text:
Verify Magic Square
A magic square is a square array of numbers with side n consisting of the distinct positive integers 1, 2, ..., n² arranged such that the sum of the n numbers in any horizontal, vertical, or main diagonal line is always the same number, which is known as the magic constant.
Your program must input, through std-in, a number specifying the length of the side of your square, then the numbers in the square. No numbers may be used more than once, no number greater than n² may be used, and all numbers must be greater than 0.  The program must determine whether that combination of numbers is a magic square.

CJam, 47 39 35 33 31 bytes
l~/{_1fb_,Y${\(_@=\}%:++\z}2*;=

Takes input like
4 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]

Outputs 1 if magic square, 0 otherwise.
How it works:
l~/                               "Evaluates the input and split the array into chunks"
                                  "of size N where N is the first integer";
   {                      }2*     "Run this code block 2 times";
    _1fb                          "Copy the 2D array and calculate sum of each row of copy";
        _,                        "Copy the array containing sum of each row and get"
                                  "its length. This is equal to N";
          Y${      }%             "Run this code block for each array of the original"
                                  "2D array that we copied from stack";
             \(_                  "Put the length number to top of stack, decrement and"
                                  "copy that";
                @=\               "Take the element at that index from each row and put"
                                  "N back behind at second position in stack";
                     :+           "Take sum of elements of the array. This is sum of"
                                  "one of the diagonals of the 2D array";
                       +          "Push diagonal sum to row sum array";
                        \z        "Bring original array to top and transpose columns";
                             ;    "At this point, the stack contain 3 arrays:"
                                  "  Array with sum of rows and main diagonal,"
                                  "  Array with sum of columns and secondary diagonal and"
                                  "  The original array. Pop the original array";
                              =   "Check if sum of rows + main diagonal array is equal to ";
                                  "sum of columns + secondary diagonal array";

This can be golfed further.
Try it online here

Python 2: 132 chars
n,l=input()
r=range
print r(1,n*n+1)==sorted(l)*len({sum(l[i::j][:n])for(i,j)in zip(r(n)+r(0,n*n,n)+[0,n-1],[n]*n+[1]*n+[n+1,n-1])})

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

The are two things to check:

The sums are the rows, columns, and diagonals are all equal
The elements are a permutation of [1,2,...,n*n].

The first is checked by taking sums of slices corresponding to these subsets. Each row, column, or diagonal is described by its starting value and its displacement. We take the list corresponding slice, truncate to n elements, and sum it. In Python's [start:end:step] notation, rows are [r*n::1], columns are [c::n] and the two diagonals are [0::n+1] and [n-1::n-1]. These are stored as a list of 2*n+2 pairs produced by zip.
We take the sets of sums and check that it has length 1. Also, we sort the input and check that it is the list [1,2,...,n*n]. Actually, we combine both into one check by multiplying sorted(l) by the length of the sum-sets, a check that always fails unless the sum-set has length 1.

I realized that you can encode a pair (i,j) more efficiently as a single number x, taking i=x%C and j=x/C for some large enough C. Might give that a shot later.

APL, 35
∧/2=/(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕)

Explanation
x←⎕⍴⍨,⍨⎕ prompts for input, shape it into a matrix, and assign to x
⌽ Reverses the matrix left-to-right
x(...) Create a array of matrices: x and x reverse
1 1∘⍉¨ For each of those matrices, take the diagonal
+/↑ form a 2×n matrix of the numbers on those diagonals and sum the rows
⍉x Transpose x
x, then concatenate with x to form a n×2n matrix
+⌿ and sum the columns
(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕) concatenate to form an array of the sums
2=/ check if consecutive pairs equal
∧/ and AND together all those results

APL 47 32
Using TwiNight's excellent solution and applying some more tweaking:
∧/2=/+⌿(1 1∘⍉∘⌽,1 1∘⍉,⍉,⊢)⎕⍴⍨,⍨⎕

Explanation:
This uses function trains, which were introduced in v14 of the Dyalog interpreter.
APL is executed from right to left, ⎕'s are inputs, so first the dimensions, then the vector of numbers.
⎕⍴⍨,⍨⎕ creates the matrix NxN
After that comes the function train which are basically just a sequence of functions (between brackets) applied to the right argument.
The functions are:
⊢ Returns just right argument (that is the matrix)
⍉ Transposes the right argument matrix
1 1∘⍉ Returns the diagonal
1 1∘⍉∘⌽ Returns the diagonal of the reversed (horizontally) matrix
All the results are concatenated with the function ","
At this point, the result is a matrix whose columns are then summed (+⌿). The values obtained this way are then checked to be the same with ∧/2=/
I'll leave my old solution here too:
{M←⍺ ⍺⍴⍵⋄d←M=⍉M⋄(⊃≡∪)((+/,+⌿)M),+/∘,¨d(⌽d)×¨⊂M}

takes dimension as left argument, vector of elements as right argument, for example:
4{M←⍺ ⍺⍴⍵⋄d←M=⍉M⋄(⊃≡∪)((+/,+⌿)M),+/∘,¨d(⌽d)×¨⊂M}16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1
1

Can be tried online here: www.tryapl.org

Mathematica 128  125
d = Diagonal; r = Reverse; i = Input[];
Length@Union[Tr /@ Join[p = Partition[i[[2]], i[[1]]],
t = Transpose@p, {d@p}, {d@t}, {d@r@p}, {d@r@t}]] == 1

Takes input such as
{4,{16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, 1}}

True

Surely there's a lot of whitespace that can be removed here

All of the white space can be removed. I left it there for readability. And I didn't count unnecessary white space.

You can do Input[r=Reverse] to save a byte. #&@@ is a byte shorter than [[1]]. You can probably in addition use infix notation for Partition for another byte. And Thread should work instead of Transpose. Alternatively, use this Unicode character as a post fix operator (Mathematica uses it for superscript T for transpose).

JavaScript (E6) 194
Using prompt to read input and display output.
Test in console with FireFox >31 (Array.fill is very new)
z=(p=prompt)(n=p()|0).split(' '),u=Array(2*n).fill(e=d=n*(n*n+1)/2),z.map((v,i)=>(r=i/n|0,u[r+n]-=v,u[c=i%n]-=v,d-=v*(r==c),e-=v*(r+c+1==n))),o=!(e|d|u.some(v=>v)),z.sort((a,b)=>a-b||(o=0)),p(o)

Less golfed
n = prompt()|0; // input side length
z = prompt().split(' '); // input list of space separeted numbers
e = d = n*(n*n+1)/2; // Calc sum for each row, column and diagonal
u = Array(2*n).fill(e), // Init check values for n rows and n columns

z.map( (v,i) => { // loop on number array
  r = i / n | 0; // row number
  c = i % n; // column number
  u[r+n] -= v; // subtract current value, if correct it will be 0 at loop end
  u[c] -= v;
  if (r==c) d -= v; // subtract if diagonal \
  if (r+c+1==n) e -=v; // subtract if diagonal /
}),
o=!(e|d|u.some(v=>v)); // true if values for rows, cols and diags are 0
z.sort((a,b)=>a-b||(o=0)); // use sort to verify if there are repeated values in input
alert(o);

GolfScript 67 (demo)
~]:q(/q(/zip+[q()/{(\;}%]+[q((/);(;{(\;}%]+{{+}*}%.&,2<q(2?,{)}%-!*

Pyth, 24 30 bytes
&q1l{sM++JcEQCJm.e@bkd_BJqSlQS

Try it online here.
&q1l{sM++JcEQCJm.e@bkd_BJqSlQSQ   Implicit: Q = evaluated 1st input (contents), E = evaluated 2nd input (side length)
                                  Trailing Q inferred
          cEQ                     Chop E into pieces or length Q
         J                        Store in J
                      _BJ         Pair J with itself with rows reversed
               m                  Map the original and it's reverse, as d, using:
                .e   d              Map each row in d, as b with index k, using:
                  @bk                 Get the kth element of b
                                  The result of this map is [[main diagonal], [antidiagonal]]
        +J                        Prepend rows from J
       +     CJ                   Prepend columns from J (transposed J)
     sM                           Sum each
    {                             Deduplicate
   l                              Length
 q1                               Is the above equal to 1?
&                                 Logic AND the above with...
                          SlQ     ... is the range [1-length(Q)]...
                         q        ... equal to...
                             SQ   ... sorted(Q)

Edit: fixed a bug, thanks to @KevinCruijssen for letting me know :o)

This outputs True for magic squares with numbers that are too big, or not all unique. I.e. 4 and [12,26,23,13,21,15,18,20,17,19,22,16,24,14,11,25] or 4 and [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] output both True. (Almost all existing answer have the same problem though, but since they are posted over 4 years ago I didn't bother to correct their mistakes in a comment.)

@KevinCruijssen Damn, I got so focused on verifying the sums that I forgot about the other requirements... I'm such a dope

LUA 186 Chars
s=io.read(1)v=io.read(2)d=0 r=0 for i=1,#s do t=0 for j = 1, #s do t=t+s[i][j]end d=d+s[i][i] r=r+s[i][#s-i+1]if t ~= v then o=true end end if d~=v and r~= v then o=true end print(not o)

05AB1E, 24 21 bytes
ôD©ø®Å\®Å/)O˜Ë²{¹nLQ*

Input format: 4\n[2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15]. Outputs 1/0 for truthy/falsey respectively.
Try it online or verify some more test cases.
Explanation:
ô      # Split the 2nd (implicit) input into parts of a size of the 1st (implicit) input
       #  i.e. [2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15] and 4
       #   → [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]]
 D     # Duplicate it
  ©    # And store it in the register (without popping)
ø      # Zip/transpose; swapping rows/columns
       #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]]
       #   → [[2,11,7,14],[16,5,9,4],[13,8,12,1],[3,10,6,15]]
®      # Push the matrix from the register again
 Å\    # Get the top-left to bottom-right main diagonal of it
       #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [2,5,12,15]
®      # Push the matrix from the register again
 Å/    # Get the top-right to bottom-left main diagonal of it
       #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [3,8,9,14]
)      # Wrap everything on the stack into a list
       #  → [[[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]],
       #     [[2,11,7,14],[16,5,9,4],[13,8,12,1],[3,10,6,15]],
       #     [2,5,12,15],
       #     [3,8,9,14]]
 O     # Take the sum of each inner list:
       #  → [[34,34,34,34],[34,34,34,34],34,34]
 ˜     # Flatten this list
       #  i.e. [[34,34,34,34],[34,34,34,34],34,34] → [34,34,34,34,34,34,34,34,34,34]
  Ë    # Check if all values are equal to each other
       #  i.e. [34,34,34,34,34,34,34,34,34,34] → 1 (truthy)
²      # Push the second input again
 {     # Sort it
       #  i.e. [2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15]
       #  → [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
  ¹n   # Push the first input again, and take its square
       #  i.e. 4 → 16
    L  # Create a list in the range [1, squared_input]
       #  i.e. 16 → [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
     Q # Check if the two lists are equal
       #  i.e. [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
       #   and [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] → 1 (truthy)
*      # Check if both checks are truthy by multiplying them with each other
       #  i.e. 1 and 1 → 1
       # (and output the result implicitly)

K (ngn/k), 36 33 bytes
-3 bytes from improvements by @ngn
{1=#?{+/x,'x@'!#x}'(|+:)\(x,x)#y}

Try it online!
May be non-qualifying, as this is a function taking two args; the length of the square, and a list of the square's values.

(x,x)#y build x-by-x matrix of the values from y
(|+:)\ build list of all rotations of the matrix
{...}' inner lambda, called on each rotation

x@'!#x get the main diagonal elements
x,'x zip them with the original values
+/ take the column-wise sum (the last column being the main diagonal)

1=#? is there only one distinct sum?

Husk, 27 bytes
&=O¹ḣ□³Λ=mΣ+mo►L∂Se↔C³¹S+TC

Try it online!
I don't know any other techniques to golf this further, but it would be really cool if I could get it any lower.
Explanation coming later.
Takes inputs as 2 command line args, since Husk does not have the feature of taking from STDIN.