text:
Kolmogorov complexity Chad Gadya
EDIT It is not clear how answers to the question of compressing a long text, without cumulative properties are relevant to golfing a short cumulative strong, any more than general Lempel Ziv techniques are relevant to code-golfing. Take note that the complexity of 99 bottles of beer is not O(Sqrt(n))
Knuth suggested  the notion of theoretical complexity of songs (Knuth, Donald E. "The complexity of songs." Communications of the ACM 27.4 (1984): 344-346.), noting that most cumulative songs are O(sqrt(n)).
Cumulative songs never showed up in PPCG. The challenge this time is Chad Gadya, a famous cumulative song in Aramaic and Hebrew, sung in cumulation of the seder. The lyrics can be found, e.g., here (blue text). (There are slight variations, so use this one, copied below).
To state the obvious, Chad Gadya belongs in the complexity class of the famous "Läuschen und Flöhchen" tale by the Grimm brothers, and some other more or less famous English songs, i.e., O(sqrt n).
The challenge is to write a program, in any programming language, that produces the song, each verse in its own line. The program takes no input, and cannot cheat by using, e.g., wget. A greater challenge is to make the solution so small that it can fit in a twitter message. (I bet no one here would be able to meet this challenge)
A short such program could be useful for twitter/sms holiday greetings. Please minimize the number of bytes (not characters). Output should be in UTF8.
Why is this interesting?

Knuth paper on the the complexity of cumulative songs
Song is very short; standard tricks would not help.
Space savings in Niqqud is an extra challenge.
Repetitions are not only due to the cumulative nature of the song.
The twitter objective seems impossible.
The song itself is quite short, much shorter than other songs that have been posted here. Compression of short text is more challenging than that of long text.

Output

חַד גַּדְיָא, חַד גַּדְיָא דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא שׁוּנְרָא, וְאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא כַלְבָּא, וְנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא חוּטְרָא, וְהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא נוּרָא, וְשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַיָּא, וְכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא תוֹרָא, וְשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַשּׁוֹחֵט, וְשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַלְאַךְ הַמָּוֶת, וְשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַקָּדוֹשׁ בָּרוּךְ הוּא, וְשָׁחַט לְמַלְאַךְ הַמָּוֶת, דְּשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא

If you find it hard to deal with Hebrew and Aramaic (tough luck...), try first getting your hands dirty with Läuschen und Flöhchen, and then proceed to the real challenge.
A related, but different question is that of "99 Bottles of Beer". If you care about complexity, you would notice that the theoretical complexity of bottles of beers is different from that of the two farthing kid.

You should include the full text of the song in your post. That said, I don't see why this isn't a dupe of this kgc question. The different character set shouldn't change the types of compression people use, and there doesn't seem to be substantial usable symmetry in the song not present in other challenges.

Relevant meta discussion about song text kolmogorov complexity challenges.

Leaving aside the issue of whether this adds anything new, it certainly needs some editing. "Briefly describe the challenge. Provide a short background for your challenge. Briefly answer the following questions for your readers." That's not a task for the answerers. And there's no reason to link to a Google redirection link which updates its search utility database.

Not every song is a duplicate of the rickroll. Where the song is short and the structure follows a strong pattern (here 'cumulative') golfing techniques other than straight text compression are applicable. See my meta post on work it harder, make it better (linked by Martin above.) Opinion is divided but the majority agreed with me. If we start closing questions like this, by the same logic we should close many ASCII art kolmogorov complexity questions, which would clearly be detrimental to the site. Voted to reopen, Did not upvote as I dislike Unicode challenges

@PeterTaylor: are the edits made sufficient in your opinion?

This reads like a long excuse (meaning, an answer to "Why is this on topic?") and a very brief description of the challenge. I think it needs more of the latter (and more prominently, viz first) and perhaps less of the former.

Please check that my edit matches your intent, and revert it otherwise.

I still think it's a duplicate. It may not be clear to you why the grammar-based techniques used in earlier song compression questions are equally applicable to this particular song, but it's perfectly clear to those of us who use them.

@msh210: Not sure what the edit did. It looks the same to me. Did you change the order of Niqqud letters?

I removed the dagesh form the gimel in "לְגַּדְיָא" n the line that starts "וַאֲתָא נוּרָא".

@PeterTaylor: Can you please clarify? Are you referring to context free grammars? Or is it the natural language own grammar? How can you systematically capture a natural language grammar? I tried checking out previous solutions Kolmogorov/Song like question, and I could not find any reusable techniques.

This link is in the first paragraph of the accepted answer to the question this was initially closed as a duplicate of. If it doesn't go into enough detail, read this paper.

@PeterTaylor: I am quite familiar with this paper and the theory of compressing grammars. Has it been said that the shortest grammar for a given string is linked in any precise manner with the shortest program that produces it? e.g., one solution here uses a search and replace trick.

Python 2, 633 603 589 584 bytes (384 chars)
Note: the file must begin with a 3-byte “UTF-8 BOM” (EF BB BF), which Stack Exchange does not seem to preserve.
v="נָשַׁךְ הִכָּה שָׂרַף כָבָה שָׁתָה".split()+["שָׁחַט"]*4
c=', '.join(["חַד גַּדְיָא"]*2)
b=" דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. "+c
print c+b
e='אָכְלָה לְגַדְיָא,'+b
for i,t in enumerate("שׁוּנְרָא|כַלְבָּא|חוּטְרָא|נוּרָא|מַיָּא|תוֹרָא|שׁוֹחֵט|מַלְאַךְ הַמָּוֶת|הַקָּדוֹשׁ בָּרוּךְ הוּא".split('|')):
 print'וַאֲתָא '+(t if i!=7else'הַשּׁ'+t[4:])+' וְ'+e
 e=v[i]+' לְ'+t+', דְּ'+e

Output:
חַד גַּדְיָא, חַד גַּדְיָא דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא שׁוּנְרָא וְאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא כַלְבָּא וְנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא חוּטְרָא וְהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא נוּרָא וְשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַיָּא וְכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא תוֹרָא וְשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַשּׁוֹחֵט וְשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַלְאַךְ הַמָּוֶת וְשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַקָּדוֹשׁ בָּרוּךְ הוּא וְשָׁחַט לְמַלְאַךְ הַמָּוֶת, דְּשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא

How it works:
I first create a list of all the nouns and verbs. It's in a string with a separator because that's a lot cheaper, byte-wise. I also have the ending piece in a variable.
The first part of the first line (חד גדיא, חד גדיא) is already contained at the end, so i just slice it and prepend.
Each of the next lines follows the same format, so i keep a running variable e (for end) of the part that gets copied, and just print the part that changes.
The line of השוחט needs to be special-cased.
Code shortened to use BOM by suggestion of Anders Kaseorg and msh210, and optimized with some tricks from msh210's answer.

You can’t leave off the encoding header, but you can replace it with a 3-byte “UTF-8 BOM” (EF BB BF).

Perl 5, 632 bytes
$g="חַד גַּדְיָא";$g.=", $g";$\="דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. $g";@a=split b,"שׁוּנְרָאbכַלְבָּאbחוּטְרָאbנוּרָאbמַיָּאbתוֹרָאbשׁוֹחֵטbמַלְאַךְ הַמָּוֶתbהַקָּדוֹשׁ בָּרוּךְ הוּאbגַדְיָא";@c{@a}=@a;$c{'שׁוֹחֵט'}="הַשּׁוֹחֵט";@d=qw/אָכְלָה נָשַׁךְ הִכָּה שָׂרַף כָבָה שָׁתָה/;push@d,('שָׁחַט')x3;print$g.$";for$i(0..8){$/="\nוַאֲתָא $c{$a[$i]}, וְ$d[$i] לְ$a[$i-1], ";$/.="דְּ$d[$i-$_] לְ$a[$i-$_-1], "for 1..$i;print$/}

Good job. Can the trick in this one help you?
"g=(["חד גדיא"]*2).join ", " k = "שונרא1אכלה1כלבא1נשך1חוטרא1הכה1נורא1שרף1מיא1כבה1תורא1שתה1השוחט1שחט1מלאך המוות1שחט1הקדוש ברוך הוא1שחט" base = " דזבן אבא בתרי זוזי. " + g old = "גדיא" puts g + base k.scan(/(\D+)\d(\D+)/){ puts "ואתא #{$1}, ו#{$2} ל#{old}," + base base = " ד#{$2} ל#{old}," + base old = $1.delete("ה") } (Credit goes to G. A.)

@YossiGil, dunno, I don't speak (or even recognize) that language.

GolfScript, 577 bytes
"חַד גַּדְיָא, חַד גַּדְיָא. ":d"דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. "d+"\n"+:c"גַדְיָא,שׁוּנְרָא,כַלְבָּא,חוּטְרָא,נוּרָא,מַיָּא,תוֹרָא,שׁוֹחֵט,מַלְאַךְ הַמָּוֶת,הַקָּדוֹשׁ בָּרוּךְ הוּא"","/:y;"אָכְלָה,נָשַׁךְ,הִכָּה,שָׂרַף,כָבָה,שָׁתָה,שָׁחַט,שָׁחַט,שָׁחַט"","/:x;9,{"וַאֲתָא "\.6="הַ"""if\.y\1+=\", וְ"\.x\=\" לְ"\.y\=\,-1%{", דְּ"\.x\=\" לְ"\.y\=\;}%". "c}%

Store the nouns and actions in variables by splitting strings.
Using a list of lists of increasing sizes, each in descending order - [[1],[2,1],[3,2,1]...] - print the first and subsequent lines of each stanza using those index values.

Python 2, 331 bytes
(This source contains non-printable bytes, so it is presented as a hexdump that can be decoded with xxd -r.)
00000000: efbb bf70 7269 6e74 2278 01ed 54b5 6145  ...print"x..T.aE
00000010: 310c ec33 85fb c08e 3f0b 7c66 6668 c2ec  1..3....?.|ffh..
00000020: 39a4 7572 3917 8630 932b 4ba6 23bf a74d  9.ur9..0.+K.#..M
00000030: b9d0 aad1 8ad8 bb42 0eb5 2d97 5ada 318f  .......B..-.Z.1.
00000040: 2c18 9456 4eb5 8189 3216 8646 4b18 ca62  ,..VN...2..FK..b
00000050: dd6a 99ab 1bac aee4 4cdb 461b 5a17 8bed  .j......L.F.Z...
00000060: 68f6 cc6b d1b6 70f8 025c 30c7 ba71 d7af  h..k..p..\0..q..
00000070: b5c0 fb46 0470 47eb a84b a8bb 187b 186b  ...F.pG..K...{.k
00000080: 467b 282b 09c2 b7f2 eea2 0529 c278 d623  F{(+.......).x.#
00000090: d450 84b5 8e1c 9275 2cd0 33ff 0512 9bbc  .P.....u,.3.....
000000a0: ad95 0453 0364 57ac e79c 3a41 d67f cd8b  ...S.dW...:A....
000000b0: 116f 0b7d 58eb 3eba 15b6 4d1d dfd4 2e32  .o.}X.>...M....2
000000c0: feb7 865c 72d0 b6a3 6fa3 8bba ecd9 468e  ...\r...o.....F.
000000d0: 92eb 339e 664f 3798 b84a 1e61 01dd c6f3  ..3.fO7..J.a....
000000e0: 8d6c 27db f71b 9f8d afa1 5d8b 25ff 2b1c  .l'.......].%.+.
000000f0: 3ad3 5618 5c30 af69 9177 9211 e5e5 94be  :.V.\0.i.w......
00000100: ee97 d323 4f27 87b1 5c72 085e 9773 dd3c  ...#O'..\r.^.s.<
00000110: 16d9 3ac9 956a 7f58 b2f9 fb5b 12ab ca10  ..:..j.X...[....
00000120: a0c4 61c2 3302 b9b8 5996 1e89 f9f9 e741  ..a.3...Y......A
00000130: 91bf e181 e407 720b 7329 ec60 222e 6465  ......r.s).`".de
00000140: 636f 6465 2827 7a69 7027 29              code('zip')

How can this hexdump be downloaded?

@YossiGil I think you copy and paste it into a file, for an example see http://www.linuxjournal.com/content/doing-reverse-hex-dump

@YossiGil Here’s a copy you can download, in case xxd is inconvenient: https://filebin.ca/2fNVeo4jr3aY/chad-gadya.py


text:
Driftsort an array
Driftsort is a simple way to "sort" an array. It works by "sliding" or "rotating" the elements over in the array until the array is sorted, or until the array fails to be sorted.
Let's walk through two examples. First, consider the array [10, 2, 3, 4, 7]. Since the array is not sorted, we rotate it once. (This can happen in either direction, so long as it remains the same direction.) Then, the array becomes:
[7, 10, 2, 3, 4]

This is not sorted, so we rotate again.
[4, 7, 10, 2, 3]

And again:
[3, 4, 7, 10, 2]

And a final time:
[2, 3, 4, 7, 10]

And it's sorted! So the array [10, 2, 3, 4, 7] is driftsortable. Here are all the rotations of the array, for clarity:
[10, 2, 3, 4, 7]
[7, 10, 2, 3, 4]
[4, 7, 10, 2, 3]
[3, 4, 7, 10, 2]
[2, 3, 4, 7, 10]

Consider now the array [5, 3, 9, 2, 6, 7]. Look at its rotations:
[5, 3, 9, 2, 6, 7]
[7, 5, 3, 9, 2, 6]
[6, 7, 5, 3, 9, 2]
[2, 6, 7, 5, 3, 9]
[9, 2, 6, 7, 5, 3]
[3, 9, 2, 6, 7, 5]

None of these arrays are sorted, so the array [5, 3, 9, 2, 6, 7] is not driftsortable.

Objective Given a nonempty array/list of integers as input to a program/function, implement driftsort on the input and output it, or output a falsey value (or an empty array/list) if it cannot be driftsorted. The integers are bound to your languages max/min, but this must be at least 255 for the max, and 0 for the min.
You may use built-in sorting methods, but not a built-in which solves the challenge.
This is a code-golf, so the shortest program in bytes.
Test cases
input => output
[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]

An easy way to check if a list is driftsortable is if sorted(l) is a contiguous sublist of l+l.

Just to clarify: If our language supports negative integers, they can occur in the input, yes?

@Dennis that is correct.

Shouldn't this be called shiftsort?

@FilipHaglund I thought about calling it that, but it may cause confusion with the shift operation that removes the first element of an array.

Jelly, 6 bytes
ṙỤċṢȧṢ

Try it online! or verify all test cases.
How it works
ṙỤċṢȧṢ  Main link. Argument: A (list)

 Ụ      Grade up; return the indices of A, sorted by their corresponding values.
ṛ       Rotate A by each index, yielding the list of all rotations.
   Ṣ    Yield A, sorted.
  ċ     Count the number of times sorted(A) appears in the rotations.
        This gives 0 if the list isn't driftsortable.
    ȧṢ  Logical AND with sorted(A); replaces a positive count with the sorted list.

Ahem, 19 bytes of UTF8.

Jelly has a custom code page that encodes each of the 256 characters it understands as single bytes. (It's 16 bytes with UTF-8 btw.)

@Dennis: you should copy/paste this in all your Jelly submissions to prevent us (ie, ones who didn't knew this before) from making the same comments ? ;)

Ruby, 33
->a{a.any?{a.sort==a.rotate!}&&a}

a.any? fires up to once for each element in the array, except it stops (and returns true) as soon as the array has been mutated into a sorted state. If this happens, we return the mutated array. Otherwise we return the false value that any? returns.

This is super clever, particularly the in-place rotate. Nice work!

Alas, my own Ruby answer has been bested. +1

Ah yes, the old "sort it until you can tell if it's able to be sorted" technique.

Python 2, 51 bytes
lambda l:sorted(l)*(map(cmp,l[-1:]+l,l).count(1)<3)

Doesn't bother rotating. Instead, sorts the list, then sees if the original is drift-sortable by checking if there's at most one decrease among consecutive elements of the cyclified list. The count is <3 because map pads the shorter list with None at the end, adding a fake decrease.

[1, 3, 2, 4] only has one decrease among consecutive elements but it's not drift-sortable.

@Neil Oh shoot.

@Neil I think this fixes it. Could you please take a look?

Aw we <3 you too

I can't say I'm expert at Python but that seems reasonable assuming the <3 is to avoid having to precisely rotate the list.

What does the cmp do in map?

@R.Kap Return 1 if positive 0 if 0 -1 if negative

What Python version are you using? I just tried using cmp and I get a NameError in Python 3.5.

@R.Kap cmp was removed from python 3, it works in python 2.

Right, this is Python 2 only, fixed.

Pyth, 9 bytes
*SQ}SQ.:+

Explanation:
           - Q = eval(input())
         + -    Q+Q
       .:  -   sublists(^)
   }       -  V in ^
    SQ     -   sorted(Q)
*SQ        - ^ * sorted(Q) (return sorted(Q) if ^ True)

Try it here!
Or use a test suite!

I think you mean substrings (sublists) for .:. Combinations would include non-contiguous elements.

Matlab, 61 47 41 bytes
Thanks @Suever for -6 bytes!
@(a)sort(a)+0*min(strfind([a,a],sort(a)))

If strfind([a,a],sort(a)) tries to find the sorted input vector as a 'substring' of the unsorted, that was appended to itself. If true, the input is driftsortable and we get a vector of length 2, if not we get a empty vector. min just transforms this to an number / empty vector. Adding the sorted vector to 0 just displays it, adding it to an empty vector throws an error.

Does the substring check handle [2, 3] not being a sublist of [12, 34]?

Yes, each integer array can also interpreted as string, where each number is treated as one character, no matter how big the number.

@flawr My interpretation is that strfind can work directly with numbers, not only with chars (even though that's not documented). If the numbers were being interpreted as chars they would be limited to 65535 (try for example +char(1e5))

@LuisMendo You are right, it even works with floating point numbers. Note that numers above 65535 will just be displayed as a space when considered as part of a string.

Julia, 71 66 52 bytes
x->(y=sort(x))∈[circshift(x,i)for i=1:endof(x)]&&y

This is an anonymous function that accepts an array and returns an array or a boolean. To call it, assign it to a variable.
For an input array x, we construct the set of all rotations of x and check whether the sorted version x is an element of that list. If it is, we return x sorted, otherwise we return false.
Saved 19 bytes thanks to Dennis!

JavaScript (ES6), 72 70 65 bytes
a=>a.map(y=>{c+=x>y;x=y},x=a.slice(c=-1))|c<1&&a.sort((a,b)=>a-b)

Returns 0 on failure. Previous 85 83 80-byte version avoided calling sort:
a=>a.map((y,i)=>{x>y&&(c++,j=i);x=y},x=a.slice(c=-1))|c<1&&a.splice(j).concat(a)

Edit: Saved 2 bytes by initialising c to -1 instead of 0. Saved 5 bytes by switching from reduce to map, sigh...

See the edit ;)

Call to sort for numbers is incorrect. Check on the sample [10, 2, 3, 4, 7].

This code also failes 3 tests: [1], [0, 0, 0, 0, 0, 0, 0] and [75, 230, 30, 42, 50].

@Qwertiy Sorry about the sort oversight, which caused the third test failure. The other two test failures were caused by me over-golfing; I've reverted to the previous version.

Pip, 15 + 1 = 17 16 bytes
Ugh, the other golfing languages are blowing this out of the water. However, since I've already written it...
L#gI$<gPBPOgYgy

Takes input as space-separated command-line arguments. Requires -p or another array-formatting flag to display the result legibly rather than concatenated. The false case outputs an empty string, which is visible by virtue of the trailing newline.
                 Implicit: g is array of cmdline args; y is empty string
L#g              Loop len(g) times:
         POg       Pop the first item from g
      gPB          Push it onto the back of g
    $<             Fold on < (true if g is now sorted)
   I        Yg     If true, yank g into y
              y  Autoprint y

05AB1E, 12 bytes
Code:
DgFÀÐ{Qi,}}0

Uses CP-1252 encoding. Try it online!.

Snowman 1.0.2, 27 bytes
((}#AsO|##aC,as|aLNdE`aR*))

This is a subroutine that takes input from and outputs to the current permavar.
Try it online!
((                       ))  subroutine
  }                          set our active variables b, e, and g:
                              .[a] *[b] .[c]
                              .[d]      *[e]    (* represents an active variable)
                              .[f] *[g] .[h]
   #                         store the input in variable b
    AsO                      sort in-place
       |                     swap b with g; now sorted input is in g
        ##                   store the input again in b and e
          aC                 concat; now the input doubled is in b and e is empty
            ,                swap e/g; now b has 2*input and e has sorted input
             as              split 2*input on sort(input) and store result in g
               |             bring the result up to b (we no longer care about g)
                aLNdE        take length and decrement; now we have 0 in b if the
                               array is not driftsortable and 1 if it is
                     `aR     repeat e (the sorted array) b times:
                               if b is 0 (nondriftsortable), returns [] (falsy)
                               otherwise (b=1), returns sorted array unchanged
                        *    put this back into the permavar

Javascript ES6, 48 45 43 chars
x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x

Test:
f=x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x
;`[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]`
.split`
`.map(t => t.replace(/^(.*) => (.*)$/, "f($1)+'' == $2")).every(eval)

I think you can save two bytes by using (x+[,x]) and a further byte by using ~ instead of 1+ in your condition.

@user6188402, yep, thank you.

MATL, 13 12 10 9 bytes
SGthyXfa*

The same idea as @flawr's answer where we hijack strfind (Xf) to find the sorted version of the input within the concatenation of two copies of the input.
Try it Online!
Explanation
        % Implicitly get input
S       % Sort the input
Gth     % Explicitly grab the input again and concatenate with itself
y       % Copy the sorted version from the bottom of the stack
Xf      % Look for the sorted version as a subset
a       % Gives a 1 if there were matches and 0 otherwise
*       % Multiply by the sorted array. Yields all zeros for no match and the
        % sorted array when a match was found
        % Implicitly display the stack contents

Can't you remove g? Or replace ng by a

@LuisMendo Can't replace with just an n because n could be > 1. a definitely works though. I figured there was a better way. Thanks!

Julia, 33 bytes
x->sum(diff([x;x]).<0)<3&&sort(x)

Try it online!
How it works
This concatenates the array x with itself and counts the number of pairs that are out of order, i.e. the number of contiguous subarrays [a, b] for which b - a < 0. If c is the number of unordered pairs of x itself and t is 1 if x's last element is larger than its first, sum will return 2c + t.
The array x is driftsortable iff (c, t) = (1, 0) (x has to be rotated to the smaller value of the only unordered pair), (c, t) = (0, 1) (x is sorted) or (c, t) = (0, 0) (x is sorted and all of its elements are equal), which is true iff 2c + t < 3.

Brachylog, 39 bytes
l:0re:?{[0:L],!L.|rh$(L,?h-1=:L:1&.}.o.

I really need to add an optional argument to $( - circular permute left to permute more than once... this would have been 13 bytes. This will wait after implementing a stable new transpiler in Prolog.
Explanation
l:0re                                     I = a number between 0 and the length of Input
     :?{[0:L],!L.|rh$(L,?h-1=:L:1&.}      All this mess is simply circular permutating the
                                          input I times
                                    .o.   Unify the Output with that circular permutation
                                          if it is sorted, else try another value of I

Ruby, 47 bytes
Recursive function. Returns nil if the input array cannot be driftsorted.
f=->a,i=0{a.sort==a ?a:a[i+=1]?f[a.rotate,i]:p}

CJam, 17 13 bytes
Thanks to Dennis for saving 4 bytes.
{_$\_+1$#)g*}

An unnamed block (function) which takes and returns a list.
Test suite.
Explanation
This essentially uses xnor's observation that the sorted list appears in twice the original list if its drift sortable:
_$   e# Duplicate input and sort.
\_+  e# Get other copy and append to itself.
1$   e# Copy sorted list.
#    e# Find first position of sorted list in twice the original,
     e# of -1 if it's not found.
)g   e# Increment and take signum to map to 0 or 1.
*    e# Repeat sorted array that many times to turn it into an empty
     e# array if the input was not drift sortable.

@Dennis oh, looks like we came up with that independently. Thanks though. :)

C++ 14, 242 chars
#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}}

If I can't leave output empty, 252 chars http://ideone.com/HAzJ5V
#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}cout<<'-';}

Ungolfed version http://ideone.com/Dsbs8W
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define b v.begin()

int main()
{
  vector <int> v;
  int x, n=0;

  for(;cin>>x;++n)
    v.push_back(x);

  for(x=n;x--;rotate(b,b+1,b+n))
    if(is_sorted(b,b+n))
    {
      for(x:v) cout<<x<<' ';
      return 0;
    }

  cout << '-';
}

PS: Based on @MichelfrancisBustillos's idea.

Java 7, 207 bytes
int[]D(int[]i){int x,z;z=x=-1;int[]d=new int[i.length];while(++x<i.length)if(i[x]>i[(x+1)%i.length])if(z<0)z=(x+1)%i.length;else return null;if(z<0)z=0;x=-1;while(++x<d.length)d[x]=i[z++%i.length];return d;}

Detailed try here
// driftsort in ascending-order
int[] D(int[]i)
{
    int x = -1,z = -1;
    int[] d = new int[i.length];

    while ((++x) < i.length)
    {
        if (i[x] > i[(x+1)%i.length])
        {
            if(z < 0) z = (x+1)%i.length;
            else return null; // not driftsortable
        }
    }

    if(z < 0) z = 0;
    x = -1;
    while ((++x) < d.length)
    {
        d[x] = i[(z++)%i.length];
    }

    return d;
}

Java 175
prints out the output as space separated values, or prints f for a falsey value.
void d(int[]a){String s;for(int v,w,x=-1,y,z=a.length;++x<z;){v=a[x];s=""+v;for(y=0;++y<z;v=w){w=a[(x+y)%z];if(v>w){s="f";break;}s+=" "+w;}if(y==z)break;}System.out.print(s);}

goes through all the combinations of the array of integers until it finds the valid sequence or runs out of combinations. the array isn't modified, but instead the driftsorted sequence is stored as a space delimited string.
a bit more readable:
void driftsort(int[]array){
    String str;
    for(int previous,current,x=-1,y,len=array.length;++x<len;){
        previous=array[x];
        s=""+previous;
        for(y=0;++y<len;previous=current){
            current=array[(y+x)%len];
            if(previous>current){
                str="false";
                break;
            }
            str+=" "+current;
        }
        if(y==len)break;
    }
    System.out.print(str);
}

try it online

C, 105 bytes
i,s;main(c,v)char**v;{c--;while(i++<c)if(atoi(v[i])>atoi(v[i%c+1]))c*=!s,s=i;while(--i)puts(v[s++%c+1]);}

This accepts the input integers as separate command-line arguments and prints the output list as one integer per line.
If the list isn't driftsortable, the program exits prematurely due to a floating point exception, so its empty output represents an empty list.
Verification
$ gcc -o driftsort driftsort.c 2>&-
$ ./driftsort 1 | cat
1
$ ./driftsort 5 0 5 | cat
0
5
5
$ ./driftsort 3 2 1 | cat
$ ./driftsort 0 9 3 | cat
$ ./driftsort 1 2 3 4 | cat
1
2
3
4
$ ./driftsort 4 1 2 3 | cat
1
2
3
4
$ ./driftsort 0 2 0 2 | cat
$ ./driftsort 5 3 9 2 6 7 | cat
$ ./driftsort 0 0 0 0 0 0 0 | cat
0
0
0
0
0
0
0
$ ./driftsort 75 230 30 42 50 | cat
30
42
50
75
230
$ ./driftsort 255 255 200 200 203 | cat
200
200
203
255
255

Ruby, 28
->a{(a*2*?,)[a.sort!*?,]&&a}

Returns either the sorted array, or nil (which is a falsy value) if the input is not drift-sortable.

Python, 53 bytes
s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))

If you want to test this head over to https://www.repl.it/languages/python3 and copy paste this:
s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))
print(N([1,2,3,4,5,0]))

How it works:

s is a variable storing the sorted python function which sorts lists
N is the main function
The input list sorted: s(x) is multiplied by whether or not the list is driftsortable str(s(x))[1:-1]in str(x+x) (thanks to @xnor)

This works because [1,2,3,4]*false results in an empty list []
and [1,2,3,4]*true results in [1,2,3,4]

In Python 2, you can shorten this to lambda x,s=sorted:(`s(x)`[1:-1]in`x+x`)*s(x) for 44 bytes.

Python, 83 bytes
def f(l):g=sorted(l);return g if any(l[x:]+l[:x]==g for x in range(len(l)))else 1>2

This got put to shame by the other python answers, but I might as well post it anyway. I really dislike the
range(len(l)))

part. Is there a faster way to iterate through the list?

It's not much, but l.append(l.pop(0))or g==l for _ in l saves a byte over the range-len approach. Using a lambda would save 14 additional bytes.

MATLAB/Octave,  118 bytes
function r(a)
i=0
while (~issorted(a) && i<length(a))
    a=a([2:end 1]),i=i+1
end
if issorted(a)
    a
else
    0
end

I think you can already save some bytes by writing everything on one line and using input(''). Also avoid unnecessary spaces and parenthesis! And you can again shed some bytes by first defining f=@issorted.

PowerShell v2+, 87 80 bytes
param($a)0..($a.length-1)|%{if($a[$_-1]-gt$a[$_]){$c--}};(0,($a|sort))[++$c-ge0]

Steps through the input list $a, checking each pairwise element (including the last and first) to see if there is more than one decreasing pair. If the particular pair is decreasing, we decrement $c. Outputs either the sorted list, or single element 0, based on the value of $c at the end. If more than one "bad" pair is present, then ++$c will still be negative, otherwise it will be at least 0, so the second element of the pseudo-ternary is chosen ($a|sort).
I see xnor did something similar, but I came up with this independently.

C++, 313 359 370 bytes
Huge shoutout to @Qwertiy for getting this working and teaching me some great golfing methods!

Golfed:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> v;int x,c=0,s=0,y;while(cin>>x)v.push_back(x);do if(rotate(v.begin(),v.begin()+1,v.end()),c++,is_sorted(v.begin(),v.end()))s=1;while(!s&c<=v.size());if(s)for(y=0;y<v.size();y++)cout<<v[y]<<" ";else cout<<"False";}

Ungolfed:
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  vector <int> v;
  int x, c=0, s=0, y;

  while(cin>>x)
    v.push_back(x);

  do
    if (
      rotate(v.begin(),v.begin()+1,v.end()),
      c++,
      is_sorted(v.begin(),v.end())
    ) s = 1;
  while(!s & c <= v.size());

  if (s)
    for(y=0; y<v.size(); y++)
      cout<<v[y]<<" ";
  else
    cout<<"False";
}

Golfing isn't just removing spaces. using namespace std; is 20 chars when std:: 6 times is 30. bool s = False; - why not =0? You can drop return 0;. Why are brackets here !s&&(c<=v.size())? Figure braces and no commas...

Wow, thanks! A Lot of stuff (like std:: and return 0;) has become habit from programming classes. I really need to start checking my programs better.

Also there is a set of bugs. Why do you read until zero and put that zero into data? Why do you output to size inclusive? Why True and False instead of true and false. http://ideone.com/kVTI25 - your version, http://ideone.com/y8s44A - fixed and prepared for golfing version.

Thank you again! Caping True and False is from Python. I didn't even know you could write ifs like that!

And much more shortened: http://ideone.com/Dsbs8W and golfed http://ideone.com/HAzJ5V (255 252 chars). Used C++14 for foreach loop.

@Qwertiy I yield, if you would like, I'll delete this answer so you can post it yourself, since it is more yours than mine at this point.

You don't need to delete anything.

Maybe you leave 313 chars revision? Or shorten it to 311 as you have extra linebreak ans space there?

Factor, 47 bytes
[ dup dup append [ natural-sort ] dip subseq? ]

join the sequence onto itself, then check if the sorted rendition of the original is a subsequence.

This sounds like a philosophical haiku: dup dup append \\ natural sort \\ dip subseq? Even fits the 4-4-3 pattern :)

@Akiiino :D point-free languages are so poetic.

Mathematica 55 50 61 58 bytes
With 3 bytes saved thanks to Martin Büttner.
My earlier attempts did not pass all of the test case. I needed to add Union to avoid repetitions in list that were input in order.
Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&

Tests
Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&/@
{{1},{5,0,5},{3,2,1},{0,9,3},{1,2,3,4},{4,1,2,3},{0,2,0,2},{5,3,9,2,6,7},
{0,0,0,0,0,0,0},{75,230,30,42,50},{255,255,200,200,203}}

{{1}, {0, 5, 5}, {}, {}, {1, 2, 3, 4}, {1, 2, 3, 4}, {}, {}, {0, 0, 0,
     0, 0, 0, 0}, {30, 42, 50, 75, 230}, {200, 200, 203, 255, 255}}

Explanation
Right rotate the input list from 1 to n times, where n is the length of the input list.  If the sorted input list is among the output rotated lists, return it; otherwise return an empty list.

@MartinBüttner, Your suggestion failed in some of the test cases, specifically, #s 3,4,7,8.

@DavidC Ah, damn, you're right, I mixed up the behaviour of @@ and /@ on empty lists. Join@@ should still be shorter than Flatten@ though.

C#, 125 117 bytes
int[]d(int[] m){int r=0;for(int i=0;i<m.Length-1;i++)if(m[i+1]<m[i])r++;if(r<2){Array.Sort(m);return m;}return null;}

ungolfed:
int[] driftsort(int[] m)
    {
        int r = 0;
        for (int i = 0; i < m.Length - 1; i++)
            if (m[i + 1] < m[i])
                r++;

        if (r < 2) { Array.Sort(m); return m; }
        return null;
    }

there is much to get smaller here, advice would be appreciated
thanks to Erik Konstantopoulos for -8

I'm no C# expert, but I think int[] driftsort turns to int[]driftsort for -1 byte.

@ErikKonstantopoulos You are correct.

Seems like you can replace the if()s with ?: ternaries, too

@cat I don't think the second if() can be replaced.

there must be a way to return a sorted array.

also the name is long for no reason. lol lemme fix dat

int[] m doesn't need a space, also, if you use C# 6, you can use a lambda and leave out the name and type: https://msdn.microsoft.com/en-us/library/bb397687.aspx

cat i tried but i couldnt get it to work...

Mathcad, TBD

In Mathcad, 0 (scalar) == false.
(Equivalent) byte count is TBD until counting method agreed.  Approx 52 bytes using a byte = operator / symbol keyboard equivalence.

PHP, 98 bytes
Outputs a 1 if driftsortable, else nothing
$a=$argv[1];$b=$a;sort($a);foreach($a as $v){echo($a===$b?1:'');array_unshift($b, array_pop($b));}

source: Stack Exchange

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

sort: votes


text:
Tips for golfing in PARI/GP
PARI/GP is a free computer algebra system. It is designed for (algebraic) number theory, not golfing, but that's part of the attraction. Unsurprisingly, it fares best at mathematical tasks; its support for string manipulation is primitive. (Having said that, advice for golfing non-mathematical tasks is also welcome.)
As usual, please post one tip per answer.
These tips should be at least somewhat specific to PARI/GP; advice which applies to 'most' languages belongs at Tips for golfing in <all languages>. Some general tips which don't need to be included:

Compress whitespace. (In GP all whitespace outside of strings is optional.)
Use single-character variables. (There are 50 choices, a-z and A-Z except I and O.)
Use < and > rather than <= and >= when possible.
Chain assignments. (a=b=c or a+=b*=c)

Use operators to replace commands (or longer operators!) when possible.
length(v) → #v (saves 5-7 bytes)
matsize(M)[2] → #M (saves 9-11 bytes)
matsize(M)[1] → #M~ (saves 8-10 bytes)
floor(x) → x\1 (saves 3-5 bytes)
round(x) → x\/1 (saves 2-4 bytes)*
shift(x,n) → x>>n or x<<n (saves 2-6 bytes)
sqr(x) → x^2 (saves 1-3 bytes)
deriv(x) → x' (saves 4-6 bytes)
mattranspose(M) → M~ (saves 11-13 bytes)
factorial(n) → n! (saves 8-10 bytes)
&& → & (saves 1 byte; note that this syntax is deprecated)
|| → | (saves 1 byte; only works in older versions)
* Prior to 2.8.1 (2016) the \/ operator did not work correctly on t_REAL numbers—update if you haven't!

x\/1: is that designed to be a round operator, or just some sort of magic?

@primo: Yes, it's a round operator. Not very well-known, though, so I thought I'd mention it. Of course round(x/6) to x/6 is an even bigger win...

In a string context (e.g. the arguments of print or Str), commas are unnecessary:
i=99
print(i" bottles of beer on the wall")

This is even true if one of the arguments is an assignment. The following is equivalent to the above:
print(i=99" bottles of beer on the wall")

Unassigned variables evaluate to their name in a string context:
for(i=1,2,print(i" bottl"e" of beer on the wall.");e=es)

produces:
1 bottle of beer on the wall.
2 bottles of beer on the wall.

In a multi-line context { ... }, the closing brace is unnecessary.
print({"this is line one
this is line two")

Documentation
In REPL:
?* - show all commands.
?<command> - show brief documentation for a command.
Online documentation:
http://pari.math.u-bordeaux.fr/dochtml/html.stable/

The refcard is also very helpful: https://pari.math.u-bordeaux.fr/pub/pari/manuals/2.13.0/refcard.pdf

Some replacements:

poldegree(f) -> #f'
subst(f,x,y) -> x=y;eval(f) if x is not used elsewhere
subst(f,x,0) -> f%x but its type is t_POL instead of t_INT
polcoeff(s+O(x^(n+1)),n) -> Pol(s+O(x^n*x))\x^n but its type is t_POL
polcoeff(s+O(x^(n+1)),n) -> Vec(s+O(x^n++))[n] if the constant term of s is nonzero
Vecrev(v)~ -> Colrev(v)
Pol(s+O(x^n)) -> s%x^n if s is a rational function (e.g., 1/(1-x)) and n > 0
(1-x^n)/(1-x) -> x^n\(x-1)
matrix(n,n,i,j,e) -> matrix(n,,i,j,e)
a[2..#a] / a[2..-1] -> a[^1]
a[1..-2] -> a[^#a]
if(cond0,a,if(cond1,b,c)) -> if(cond0,a,cond1,b,c)
ceil(x) -> -x\-1

Use set-builder notation to replace apply and select.
apply(x->thing1(x)&&thing2(x),select(condition,v)) → [thing1(x)&&thing2(x)|x<-v,condition(x)]
or
apply(x->thing1(x)&&thing2(x),v) → [thing1(x)&&thing2(x)|x<-v]
but if you're applying a named function, apply is better, since the arguments are implicit:
[functionName(x)|x<-v] → apply(functionName,v)

Use specialized loops.
GP provides (at least) the following loops: for, forcomposite, fordiv, forell, forpart, forprime, forstep, forsubgroup, forvec, prod, prodeuler, prodinf, sum, sumalt, sumdiv, sumdivmult, suminf, sumnum, sumnummonien, sumpos.
So don't write s=0;for(i=1,9,s+=f(i));s when you could write sum(i=1,9,f(i)), don't write for(n=1,20,f(prime(n))) when you could write forprime(p=2,71,f(p)), and certainly don't write apply(v->print(v),partitions(4)); instead of forpart(v=4,print(v)).
prodeuler can be useful as a product over the primes, but note that it returns a t_REAL rather than a t_INT, so rounding at the end may be necessary depending on the task.
sumdiv can be a real lifesaver compared to a simple loop over divisors.
forvec is a replacement for a whole collection of loops. You can replace (ungolfed)
{
for(i=0,9,
  for(j=i,99,
    for(k=i,200,
      f(i,j,k)
    )
  )
);
}

with
forvec(v=[[0,9], [0,99], [0,200]],
  call(f, v)
,
  1 \\ increasing sequences only
)

Know your built-ins
Like other computer algebra systems, PARI/GP also has a lot of built-ins for number theory, linear algebra, polynomials, and other branches of algebra.
The easy way to find a built-in is looking at the reference card.

Reference card for 2.15.1 (the newest version)
Reference card for 2.13.3 (the version on ATO)
Reference card for 2.11.1 (the version on TIO)

Many built-ins have a prefix to indicate the types they work on. For example:

Built-ins for matrices usually have the prefix mat
Built-ins for polynomials usually have the prefix pol
Built-ins for power series usually have the prefix ser

When you are looking for a built-in, you can type the prefix in the REPL, and press tab. The command-line completion will tell you what functions it has.
To see the help message of a built-in in the REPL, just type ? functionname. For a more detailed help message, sometimes with examples, type ?? functionname.

Avoid return when possible.
The final value in the function is returned, so don't write ...;return(x) but just ...;x.
If you must use return, note that the bare for return yields the PARI value gnil, which is falsy (coerced into a GP 0 or PARI gen_0 as needed), so you can usually write return rather than return(0).
And (almost?) needless to say, but if you have two values to choose from, much better to return if(condition,x,y) than if(condition,return(x));y.

Truthy and Falsy
There isn't a Boolean type in PARI/GP. Truthy and falsy are defined as the following:

Values that equal to 0 are falsy. This includes real number 0.0, complex number 0.0+0.0*I, polynomial 0*x, power series 0+O(x^3), modulo object Mod(0,3), and many others.
Vector and matrices that are empty or only contains falsy values are falsy. This includes nested falsy vectors like [0, [0, 0, [[]]]].
Everything else is truthy. In particular, lists, maps, strings, and Vecsmalls are always truthy even if they are empty or only contains falsy values.

The simplest way to convert a to the "default" truthy / falsy value (i.e., 1 / 0) is !!a.
When testing equality with ==, every falsy value is equal to 0. If you need to distinguish between different falsy values, use ===.
Use - to test equality
For a and b that can subtract, we can do:

if(a==b,c,d) => if(a-b,d,c)
a==b&&c => a-b||c if we only need the side effect of c.
a==b||c => a-b&&c if we only need the side effect of c.

Be careful when testing vector equality: only vectors that have the same length can subtract.
Any and All
There isn't built-in any or all function in PARI/GP.
When checking if a predicate is true for all or any integers in a range, we can just use sum or prod.
When checking if any item in a vector is truthy, we don't need a function: the vector itself is truthy if and only if any item in it is truthy.
When checking if all item in a vector is truthy, the following has the same length:
vecprod(a)
![!i|i<-a]

Initialize with truthy/falsy
When using functions like for, sum, prod, we usually initialize some variable to 0 and 1. If the previous expression returns the opposite truthy/falsy value, we can just use it. For example:
a=some_truthy_value;for(i=0,n,do_something())
=>
for(i=!a=some_truthy_value,n,do_something())

String replace
PARI/GP doesn't have a string replace built-in, but when you want to replace every occurrence of a in s by b, you can do strjoin(strsplit(s,a),b).
strjoin and strsplit are introduced in PARI/GP 2.13.0, so they are not supported on TIO.

Default parameters
In PARI/GP, function parameters default to 0. This can be useful when you need to initialize a variable to 0.
For example, instead of f(x)=i=0;..., you can write f(x,i)=....

Along those lines, if you don't return anything, gnil is returned automatically, and it functions like 0 in most contexts.

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

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


text:
Regex Golf: Verify a Sudoku Solution
Write a regex which matches any valid sudoku solution and doesn't match any invalid sudoku solution. The input is an unrolled version of the sudoku, i.e. there are no line delimiters. E.g. the following board:
7 2 5 8 9 3 4 6 1
8 4 1 6 5 7 3 9 2
3 9 6 1 4 2 7 5 8
4 7 3 5 1 6 8 2 9
1 6 8 4 2 9 5 3 7
9 5 2 3 7 8 1 4 6
2 3 4 7 6 1 9 8 5
6 8 7 9 3 5 2 1 4
5 1 9 2 8 4 6 7 3

would be given as:
725893461841657392396142758473516829168429537952378146234761985687935214519284673

The rules are probably common knowledge by now, but just in case... a sudoku board is valid if and only if:

Each row contains the digits from 1 to 9 exactly once.
Each column contains the digits from 1 to 9 exactly once.
Each of the nine 3x3 subgrids contains the digits from 1 to 9 exactly once.

Rules
Your answer should consist of a single regex, without any additional code (except, optionally, a list of regex modifiers required to make your solution work). You must not use features of your language's regex flavour that allow you to invoke code in the hosting language (e.g. Perl's e modifier).
You can use any regex flavour which existed before this challenge, but please specify the flavour.
Do not assume that the regex is anchored implicitly. E.g. if you're using Python, assume that your regex is used with re.search and not with re.match. Your regex does not need to match the entire string. It just needs to match at least one substring (which may be empty) for valid solutions and yield no matches for invalid solutions.
You may assume that the input will always be a string of 81 positive digits.
This is regex golf, so the shortest regex in bytes wins. If your language requires delimiters (usually /.../) to denote regular expressions, don't count the delimiters themselves. If your solution requires modifiers, add one byte per modifier.
Test Cases
Valid boards:
123456789456789123789123456231564897564897231897231564312645978645978312978312645
725893461841657392396142758473516829168429537952378146234761985687935214519284673
395412678824376591671589243156928437249735186738641925983164752412857369567293814
679543182158926473432817659567381294914265738283479561345792816896154327721638945
867539142324167859159482736275398614936241587481756923592873461743615298618924375
954217683861453729372968145516832497249675318783149256437581962695324871128796534
271459386435168927986273541518734269769821435342596178194387652657942813823615794
237541896186927345495386721743269158569178432812435679378652914924813567651794283
168279435459863271273415986821354769734692518596781342615947823387526194942138657
863459712415273869279168354526387941947615238138942576781596423354821697692734185
768593142423176859951428736184765923572389614639214587816942375295837461347651298
243561789819327456657489132374192865926845317581673294162758943735914628498236571
243156789519847326687392145361475892724918653895263471152684937436729518978531264
498236571735914628162758943581673294926845317374192865657489132819327456243561789
978531264436729518152684937895263471724918653361475892687392145519847326243156789
341572689257698143986413275862341957495726831173985426519234768734869512628157394

Invalid boards:
519284673725893461841657392396142758473516829168429537952378146234761985687935214
839541267182437659367158924715692843624973518573864192298316475941285736456729381
679543182158926473432817659567381294914256738283479561345792816896154327721638945
867539142324167859159482736275398684936241517481756923592873461743615298618924375
754219683861453729372968145516832497249675318983147256437581962695324871128796534
271459386435168927986273541518734269769828435342596178194387652657942813823615794
237541896186927345378652914743269158569178432812435679495386721924813567651794283
168759432459613278273165984821594763734982516596821347615437829387246195942378651
869887283619214453457338664548525781275424668379969727517385163319223917621449519
894158578962859187461322315913849812241742157275462973384219294849882291119423759
123456789456789123564897231231564897789123456897231564312645978645978312978312645
145278369256389147364197258478512693589623471697431582712845936823956714931764825
243561789829317456657489132374192865916845327581673294162758943735924618498236571
243156789529847316687392145361475892714928653895263471152684937436719528978531264
498236571735924618162758943581673294916845327374192865657489132829317456243561789
978531264436719528152684937895263471714928653361475892687392145529847316243156789
342571689257698143986413275861342957495726831173985426519234768734869512628157394
345678192627319458892451673468793521713524986951862347179246835534187269286935714
341572689257698143986413275862341957495726831173985426519234768734869512628517394

For further test cases, you can use this CJam script which takes a valid board as input and randomly shuffles it to give a new valid board (input format irrelevant as long as it contains only digits and optionally whitespace).
If your regex is compatible with the .NET flavour, you can test it online using Retina. A valid solution should print 0 for invalid boards and some positive integer for valid boards. To run all test cases at once, use this template and insert the regex on the second line. If you need regex modifiers, prepend a ` to the regex and put the standard modifier letters in front of it.

related http://codegolf.stackexchange.com/q/22443/15599

If only this were [code-bowling], lol.

Wait...If we are using Python, we can only use regular expressions, and nothing else? Also, how big is each board? Is there a specific size? If not, how should we extract each board out of the clump of digits under valid boards?

@R.Kap Regardless of which flavour you're using, you should submit only the regex (and possibly some modifiers), yes. Each input is exactly 81 digits and represents a full board. (Each line in the test cases is a separate board.)

I wrote a script to solve simple sudoku's in SQL. I am sure it can be rewritten for this question. However SQL doesn't have much REGEX. Does that disqualify the answer ? (Script would probably be a bit below 400 characters)

@t-clausen.dk I'm afraid this challenge is specifically for regex-only solutions. Have a look at the challenge linked to in the first comment by Level River St.

Ruby regex, 71 78 73 bytes
^(?!.*(?=(.))(.{9}+|(.(?!.{9}*$))+|(?>.(?!.{3}*$)|(.(?!.{27}*$)){7})+)\1)

I don't really know Ruby but apparently it doesn't complain about cascaded quantifiers.
Try it here.
.NET regex, 79 78 75 or 77 bytes
Because Martin thinks this is possible... But I guess he will just incorporate these changes too.
^(?!(.)+((.{9})+|(?>(.{9})+
|.)+|(?((...)*
)(?>(.{27})+
|.){7}|.)+)(?<=\1))

Requires a trailing newline in the input to work. I'm not sure whether I'm allowed to do this (probably not).
Try it here.
The 77 byte sane version:
^(?!(.)+((.{9})+|((?!(.{9})*$).)+|(?((...)*$)((?!(.{27})*$).){7}|.)+)(?<=\1))

Thanks Neil for pointing out the error in my previous version and golfing off 1 byte (for the (...)*).
Try it here.
PCRE, 77 78 bytes
^(?!.*(?=(.))((.{9})+|(.(?!(?3)*$))+|(?(?=.(...)*$)(.(?!(.{27})*$)){7}|.)+)\1)

Just for completeness.
Try it here.
Another version, also 78 bytes:
^(?!.*(?=(.))((.{9})+|(.(?!(?3)*$))+|(?>.(?!(...)*$)|(.(?!(.{27})*$)){7})+)\1)

Try it here.
Explanation
^(?!.*                    # Match a string that doesn't contain the pattern,
                          # at any position.
  (?=(.))                 # Capture the next character.
  (
    (.{9})+               # Any 9*n characters. The next character is in
                          # the same column as the captured one.
  |
    (.(?!(.{9})*$))+      # Any n characters not followed by a positions 9*m
                          # to the end. The next character is in the same row
                          # as the captured one.
  |
    (                     # Any n occasions of...
    ?(.(...)*$)           # If it is at a position 3*k+1 to the end:
      (.(?!(.{27})*$)){7} # Then count 7*m characters that are not followed
                          # by a position 27*j to the end,
    |
      .                   # Else count any character.
    )+                    # The next character is in the same block as the
                          # captured one.
  )
  \1                      # Fail if the next character is the captured character.
)

Wow nice job. I only got it to 83 in .NET and had to switch to PCRE for 78. I have no doubt you'll end up beating that as well. :)

@MartinBüttner Yep.

I thought my use of lookahead to beat @MartinBüttner by (at the time) 4 bytes was neat but you've taken that to the next level.

Sorry, but this doesn't detect whether the cells at (1, 2) and (2, 1) are the same, and similarly for all other cells in squares where the duplicate is below and to the left.

I think you can fix it by changing (.(?!(.{27})*$)){9} to (.{7}(?=(...){0,5}(.{27})*$)).

@Neil You meant (...){1,6}. Fixed. Thanks.

It's hard to understand your correction when the comment you're correcting has been deleted...

Sorry, undeleted them. (cc @Neil)

Trailing newline seems a bit dodgy. My solution takes the input as is. (That said, 78 in .NET is impressive enough. Like I said I couldn't get below 83 in .NET. The rest is from using Ruby.)

75 now though, making use of your (.)+ (I tried that ages ago, but it didn't help in my old approach at all, and then forgot to retry after changing the code). That said, it looks like my solution is quite different from yours, so it's not just a case of having two bytes off locally somewhere.

@MartinBüttner I don't think you can use backreferences in lookbehind in Ruby, at least not on Rubular. Or did you find a workaround for that?

@jimmy23013 No, like I said, I'm using a different approach, so I don't have any lookbehinds at all. (Or lookaheads, for that matter.)

But yeah, I'd prefer if you counted the 77-byte version. The challenge spec is pretty specific about the input containing only exactly 81 digits. (Of course, if no one manages to beat my solution, the bounty will go to the best answer anyway. :P)

@MartinBüttner I just realized that I can translate my second PCRE version into Ruby... I guess you could post your answer now...

Nice work, I'll write mine up later. :)

There you go. I wonder if you'd be able to shorten my solution further as well. :P

PCRE, 117 119 130 133 147 bytes
^(?!(.{27})*(...){0,2}(.{9})?.?.?(.).?.?(?=(?2)*$).{6,8}(?3)?\4.{0,17}(?1)*$|.*(.)(.{8}(?3)*|((?!(?3)*$)(|.(?7))))\5)

Should also work in Python, Java, etc. flavors. Now with recursion! And the "recursion" feature used non-recursively for "subroutines", which I totally forgot about until I had to use actual recursion.

Cool idea - avoid repeats instead of matching norepeats!

It's a shame you can't write .{27}*.

Bah, I'd golfed your 133 byte solution down to 121 bytes only to find that you'd rewritten it, but here it is anyway: ^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(.)((.{9})+|((?!(.{9})*$).)+)(<=\8))

@Neil What flavor is that? PCRE or others I know don't allow backreferences in a lookbehind.

@Neil (<=\8) doesn't look like valid syntax (it's missing a ?). Also, the only flavour I know that supports backreferences in lookbehinds is .NET.

@MartinBüttner I switched to lookahead and still saved a byte: ^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(?3)*$)(?2)?.{6,8}\4.{0,17}(?1)*$|.*(?=(.))((?1)+|(.(?!(?2)*$))+)\5)

What in the [expletive deleted] is this dark magic

.NET regex, 8339 bytes
Yes, I know my solution is very naive, since Martin told me he did it in like 130 bytes. In fact, the URL to try it online is so long that I couldn't find a URL shortener that would accept it.
(code removed, since it's so long nobody will read it here,
and it made the post take forever to load. Just use the "Try it online" link.)

The below link does not work in IE, but does work in Chrome and Firefox.
Try it online - All test cases at once, with the help of !`  at the beginning, not included in byte count.

Here's the Python script I used to generate it (code below):
R=range(0,9)
S=range(1,10)

o = ""

# validate rows
T = "(?=.{%s,%s}%s)"
for j in R:
    for i in S:
        o += T % (9*j,9*(j+1)-1, i)

# validate columns
# "(?=(.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s})%s)"
T = "(?=("+"|".join([".{%s}"]*9)+")%s)"
for j in R:
    for i in S:
        o += T % (j,j+9,j+18,j+27,j+36,j+45,j+54,j+63,j+72, i)

# validate boxes
# (?=.{0,2}1|.{9,11}1|.{18,20}1)(?=.{3,5}1|.{12,14}1|.{21,23}1)
# (?=.{27,29}1|.{36,38}1|.{45,47}1)
T = ".{%s,%s}%s"
for i in S:
    for x in (0,27,54):
        for y in (0,3,6):
            o += "(?="+"|".join(T % (x+y+z,x+y+z+2, i) for z in (0,9,18))+")"

o += ".{81}"

o = o.replace(".{0}","").replace(",80}",",}")
print(o)

I'm rooting for you

Know what's funny? The try it online link will crash IE because it's too long :P

@cat That's why IE's only real purpose is allowing the user to download Firefox (or Chromium).

@cat It doesn't crash IE11 on Windows 8.1 though, although the Regex does not get processed properly.

@cat Let me know if you find a URL shortener that will take it. I tried a few, but each said it wasn't a valid URL. :D Try copy/pasting the URL instead of clicking it.

@NateKerkhofs Guess they fixed this, then: https://support.microsoft.com/en-us/kb/208427

@cat It doesn't crash my IE 11 on Windows 7. It just truncates the URL.

@mbomb007 Well maybe you're just special. :P

Try to golf the generator some more.  Maybe you can generate this long regex in fewer characters than a hand-written golfed regex!!  That would be awesome.

@wberry I already did in another setting, but I think the readability is important, since my regex isn't as readable. The simplicity of the method I used makes it so that anyone can understand how it works. If you want to know, simple golfing would make it about 350, but I'm sure it could be shrunk closer to 200 bytes.

.NET regex, 121 bytes
^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(?=(.))((.{9})+|(.(?!(.{9})*$))+)\8)

Explanation:
^(?!                     Invert match (because we're excluding duplicates)
 (.{27})*                Skip 0, 3 or 6 rows
 (.{9})?                 Optionally skip another row
 (...){0,2}              Skip 0, 3 or 6 columns
 .?.?(.).?.?(?=(...)*$)  Choose any of the next three cells
 (.{9})?                 Optionally skip another row
 .{6,8}\4                Match any of the three cells below
 .{0,17}(.{27})*$        As long as they're from the same square
|                        OR
 .*(?=(.))(              Choose any cell
  (.{9})+                Skip at least one row
 |                       or
  (.                     Skip cells
   (?!(.{9})*$)          Without reaching the end of the row
  )+                     For at least one cell (i.e. the cell chosen above)
 )\8)                    Match the chosen cell to the next cell
)

Nice, your combination of rows and columns is pretty clever. That saves 4 bytes on my own solution. :)

PCRE, 3579 bytes
An absolutely terrible brute force solution. Negative lookbehinds ahoy!
I spent way too much time on this to abandon it, so here it is, for posterity's sake.
On the bright side, if Sudoku suddenly starts using a different set of 9 characters, this'll still work, I guess...
http://pastebin.com/raw/CwtviGkC
I don't know how to operate Retina, but you can also paste it into https://regex101.com or similar and it'll match.
Ruby code used to generate the regex:
# Calculate the block you're in
def block(x)
    x /= 3
    x + x%3 - x%9
end

81.times do |i|
    row, col = i.divmod(9)
    neg = []
    neg += (0...col).map {|e| 9*row + e + 1}
    neg += (0...row).map {|e| 9*e + col + 1}
    neg += (0...i).map {|e| e + 1 if block(e) == block(i)}.compact
    neg = neg.uniq.sort.map {|e| "\\#{e}"}
    if neg.size > 0
        print "(?!#{neg.join '|'})"
    end
    print "(.)"
end

Ruby flavour, 75 74 bytes
Thanks to jimmy23013 for saving 1 byte.
^(?!(.{9}*(.|(.)){,8}|.*(\g<2>.{8})*|.{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?)\3).

Test it here.
Now that it's finally beaten, I can share my own solution. :) I discovered an interesting (maybe new?) regex technique in the process (the (.|(.)){,8}\3 part), which would probably be unbeatable in cases where this can't be combined with other parts of the regex (as was the case in jimmy23013's answer).
Explanation
Like the other short answers I'm using a negative lookahead which searches for duplicates in rows, columns or blocks. The basic building block of the solution is this:
(.|(.))...\3

Note that the \3 is reused between three different alternatives (which all use group 3 for duplicate detection).
That group on the left (which is group 2, containing group 3) is used for any position that can contain the first half of a duplicate digit (within a group that must not contain duplicate digits). Then ... is something that gets us the the next position where such a digit might occur (if necessary) and \3 tries to find the second half of the duplicate via backreference. The reason this works is backtracking. When the engine first matches (.|(.)) it will simply use . every time and not capture anything. Now the \3 at the end fails. But now the engine will gradually try using (.) instead of . for individual matches. Ultimately, if there's a duplicate, it will find the combination where (.) was last used on the first digit of the duplicate (such that the capture isn't overwritten later), and then uses some more . to bridge the gap to the backreference. If there is a duplicate, backtracking will always find it.
Let's look at the three different parts where this is used:
.{9}*(.|(.)){,8}

This checks for duplicates in some row. First we skip to any row with .{9}*. Then we match up to 8 characters (i.e. anything in that row except the last digit) using the optional duplicate capture and try to find the \3 after it.
.*(\g<2>.{8})*

This looks for duplicates in some column. First, note that \g<2> is a subroutine call, so this is the same as:
.*((.|(.)).{8})*

where the two groups we've just inserted are still referred to as 2 and 3.
Here, the .* simply skips as far as necessary (it would be sufficient to match up to 8 characters here, but that costs more bytes). Then the outer group matches one complete row (which may wrap across two physical rows) at a time, optionally capturing the first character. The \3 will be looked for right after this, which ensures vertical alignment between the capture and the backreference.
Finally, checking the blocks:
.{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?

Again, the \g<2> is a subroutine call, so this is the same as:
.{27}?.{3}?((.|(.)){3}.{6}){,2}.?.?

To verify the blocks, note that since we've already checked all the rows and columns, we only need to check four of the 3x3 blocks. When we know that all rows and columns as well as these 3x3 blocks are correct:
XX.
XX.
...

Then we know that there can't possibly be duplicates in the remaining blocks. Hence I'm only checking these four blocks. Furthermore, note that we don't have to look for duplicates within the same row of a 3x3 block. It's enough to find the first half of the duplicate in one row and search for the second half in a row further down.
Now for the code itself, we first skip to the beginning of one of the four blocks with .{27}?.{3}? (optionally skip three rows, optionally skip three columns). Then we try to match up to two of the rows of the 3x3 block with the same trick we used for the rows earlier:
(.|(.)){3}.{6}

We allow but don't require capturing of any of the 3 cells in the current row of the 3x3 block and then skip to the next row with .{6}. Finally, we try to find a duplicate in either of the 3 cells of the row we end up on:
.?.?

And that's it.

74: ^(?!(.*((.|(.)).{8})*|.{9}*\g<3>{,8}|.{27}?.{3}?(\g<3>{3}.{6}){,2}.?.?)\4); 73: ^(?!(.*((.|(.)|\4()).{8})*|.{9}*\g<3>{9}|.{27}?.{3}?(\g<3>{3}.{6}){3})\5).

@jimmy23013 I was actually using the \4() trick in an earlier version for the 3x3 blocks, but ended up getting rid of it, because it was longer. :D

@jimmy23013 The 73 one doesn't check the last row though: 341572689257698143986413275862341957495726831173985426519234768734869512628517394

Javascript regex, 532 530 481 463 chars
Validate rows:
/^((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$/

Validate columns:
/^((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9}/

Validate square from its first char:
/(?=.?.?(.{9}){0,2}1)(?=.?.?(.{9}){0,2}2)(?=.?.?(.{9}){0,2}3)(?=.?.?(.{9}){0,2}4)(?=.?.?(.{9}){0,2}5)(?=.?.?(.{9}){0,2}6)(?=.?.?(.{9}){0,2}7)(?=.?.?(.{9}){0,2}8)(?=.?.?(.{9}){0,2}9)/

Set preview to start of the square:
/^(((?=)...){3}.{18})+$/

And the whole expression:
/^(?=((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$)(?=((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9})(((?=.?.?(.{9}){0,2}1)(?=.?.?(.{9}){0,2}2)(?=.?.?(.{9}){0,2}3)(?=.?.?(.{9}){0,2}4)(?=.?.?(.{9}){0,2}5)(?=.?.?(.{9}){0,2}6)(?=.?.?(.{9}){0,2}7)(?=.?.?(.{9}){0,2}8)(?=.?.?(.{9}){0,2}9)...){3}.{18})+$/

Matches the whole string.

Test in Javascript ES6:
r = /^(?=((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$)(?=((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9})(((?=.?.?(.{9}){0,2}1)(?=.?.?(.{9}){0,2}2)(?=.?.?(.{9}){0,2}3)(?=.?.?(.{9}){0,2}4)(?=.?.?(.{9}){0,2}5)(?=.?.?(.{9}){0,2}6)(?=.?.?(.{9}){0,2}7)(?=.?.?(.{9}){0,2}8)(?=.?.?(.{9}){0,2}9)...){3}.{18})+$/
;`123456789456789123789123456231564897564897231897231564312645978645978312978312645
725893461841657392396142758473516829168429537952378146234761985687935214519284673
395412678824376591671589243156928437249735186738641925983164752412857369567293814
679543182158926473432817659567381294914265738283479561345792816896154327721638945
867539142324167859159482736275398614936241587481756923592873461743615298618924375
954217683861453729372968145516832497249675318783149256437581962695324871128796534
271459386435168927986273541518734269769821435342596178194387652657942813823615794
237541896186927345495386721743269158569178432812435679378652914924813567651794283
168279435459863271273415986821354769734692518596781342615947823387526194942138657
863459712415273869279168354526387941947615238138942576781596423354821697692734185
768593142423176859951428736184765923572389614639214587816942375295837461347651298`
.split`
`.every(r.test.bind(r))
&&
`519284673725893461841657392396142758473516829168429537952378146234761985687935214
839541267182437659367158924715692843624973518573864192298316475941285736456729381
679543182158926473432817659567381294914256738283479561345792816896154327721638945
867539142324167859159482736275398684936241517481756923592873461743615298618924375
754219683861453729372968145516832497249675318983147256437581962695324871128796534
271459386435168927986273541518734269769828435342596178194387652657942813823615794
237541896186927345378652914743269158569178432812435679495386721924813567651794283
168759432459613278273165984821594763734982516596821347615437829387246195942378651
869887283619214453457338664548525781275424668379969727517385163319223917621449519
894158578962859187461322315913849812241742157275462973384219294849882291119423759
123456789456789123564897231231564897789123456897231564312645978645978312978312645
145278369256389147364197258478512693589623471697431582712845936823956714931764825`
.split`
`.every(s => !r.test(s))

I think columns should be much easier than rows, so I find it curious that your column regex is longer than your row one.

@PeterTaylor, they have the same structure, but for columns I have to skip 9 chars instead of 1, so . gets into (.{9}) with brackets because of the next {0,8}. Why do you think columns should be shorter?

@PeterTaylor, yep, columns would've been simplier if I guessed to check negation.

@SuperJedi224, why javascript? I expect this regex to be valid everywhere.

@Qwertiy While your regex should work in many flavors, it relies on lookaheads (not available in Lua or OCaml, for example). It is also an invalid basic or extended regular expression, which use an entirely different syntax. It is best to pick on flavor for the validity claim, even if the solution works in many others.


text:
Greek Conversion Golf
Introduction
You must create a function to convert Arabic numerals into Greek numerals. The input will be an integer less than 1000 and more than 0.
Algorithm

Split number into digits (e.g. 123 -> 1, 2, 3)
Take each digit, and change to character found in table below, for letter symbol or letter name, (e.g. 123 -> 1, 2, 3 -> ΡΚΓ or RhoKappaGamma).

Specifications

No built-in number-system conversion
Result must be capitalized as in example.
Input will be in base 10.

Test Cases
123 -> RhoKappaGamma or ΡΚΓ
8 -> Eta or Η
777 -> PsiOmicronZeta or ΨΟΖ
100 -> Rho or Ρ
606 -> ChiDiGamma or ΧϜ

Table
Α = 1 = Alpha = 913 UTF-8
Β = 2 = Beta = 914 UTF-8
Γ = 3 = Gamma = 915 UTF-8
Δ = 4 = Delta = 916 UTF-8
Ε = 5 = Epsilon = 917 UTF-8
Ϝ = 6 = DiGamma = 988 UTF-8
Ζ = 7 = Zeta = 918 UTF-8
Η = 8 = Eta = 919 UTF-8
Θ = 9 = Theta = 920 UTF-8

Ι = 10 = Iota = 921 UTF-8
Κ = 20 = Kappa = 922 UTF-8
Λ = 30 = Lambda = 923 UTF-8
Μ = 40 = Mu = 924 UTF-8
Ν = 50 = Nu = 925 UTF-8
Ξ = 60 = Xi = 926 UTF-8
Ο = 70 = Omicron = 927 UTF-8
Π = 80 = Pi = 928 UTF-8
Ϙ = 90 = Koppa = 984 UTF-8

Ρ = 100 = Rho = 929 UTF-8
Σ = 200 = Sigma = 931 UTF-8
Τ = 300 = Tau = 932 UTF-8
Υ = 400 = Upsilon = 933 UTF-8
Φ = 500 = Phi = 934 UTF-8
Χ = 600 = Chi = 935 UTF-8
Ψ = 700 = Psi = 936 UTF-8
Ω = 800 = Omega = 937 UTF-8
Ϡ = 900 = SamPi = 992 UTF-8

Does that include base 10 number conversion?

I might be misunderstanding, but shouldn't 123 be "PKΓ"

You may want to add test cases such as 700 and 803 (with zeroes as digits).

How does 123 start with Tau? Doesn't Tau mean 300, and therefore TauKappaGamma means 323?

what encodings are allowed for the greek letters? UTF 8? (please give codepoints.) Are codepages allowed, such as https://en.wikipedia.org/wiki/Code_page_737 ? it may be obsolete but greek letters are rendered with a single byte.

@LevelRiverSt Any encoding is fine, but codepoints are UTF-8.

The character codes don't check out for me. 930 appears to be ΢; 931 is Σ.

The char code skip is because, in the lower-case section of ISO-8859-7, the final sigma precedes the regular sigma; there is no uppercase final sigma, so there is no respective code point.

Jelly, 42 40 bytes
“#'nn(2jj33556;r”Or2/F+878Ọ
ṚĖ’ḅ9‘xṚQṚị¢

Try it online! or verify all test cases.

Pyth, 49 48 46 44 bytes
_s.b@+kNsYc3mC+913d-.iU25smXm17hT4Cd"KGO"17_

Try it here.
Still working on shortening the function to generate the alphabet... and yes, the generator is longer than hardcoding the alphabet by 4 characters, but not in bytes.
_s.b@+kNsYc3[...]_
                 _  get input (implicit) and reverse
            [...]   generate "ΑΒΓΔΕϜΖΗΘΙΚΛΜΝΞΟΠϘΡΣΤΥΦΧΨΩϠ" (see below)
          c3        split into 3 equal chunks
  .b                map over each input digit (as Y) and chunk (as N)...
     +kN            prepend empty string to N (to support digits of 0)
    @   sY          get the Yth element of the empty-string-plus-digits array
 s                  concatenate all the digits
_                   reverse again to put digits back in the right order

Here's how the alphabet-generating function works. Let's take all the codepoints and subtract 913 (the smallest value):
0 1 2 3 4 75 5 6 7 8 9 10 11 12 13 14 15 71 16 18 19 20 21 22 23 24 79

Now let's pull out the ones that don't fit the pattern:
0 1 2 3 4    5 6 7 8 9 10 11 12 13 14 15    16 18 19 20 21 22 23 24
          75                             71                         79

Okay, so the strategy is forming: generate the range 0 to 24 (we'll deal with the missing 17 later), and then insert 75, 71, and 79 at the correct locations.
How can we insert the outliers? Pyth has an .interleave function that takes ex. [1,2,3] and [4,5,6] and results in [1,4,2,5,3,6]. We're going to have to add some placeholders, though, since obviously the outliers are far apart. Let's represent the placeholder with X:
0 1 2 3  4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24
X X X X 75 X X X X X  X  X  X  X  X 71  X  X  X  X  X  X  X 79

Right, so the bottom outlier array starts with four Xs. Can we group the outliers to each be preceded by four Xs and see what remains?
0 1 2 3  4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24
[four X]75 X X X X X  X [  four X  ]71  X  X  X [  four X  ]79

Now we make another key observation: since 79 comes at the very end, there can be any number of Xs preceding it, and any number of Xs following it as well! This is because interleaving [1,2,3] and [4,5,6,7,8,9] results in [1,4,2,5,3,6,7,8,9]—note that the extra elements in the second array end up at the end, and since they're going to be removed anyway, we can safely allow that.
That means we can normalize this such that every outlier is preceding by four Xs and succeeded by 6:
0 1 2 3  4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24
[four X]75[   six X   ] [  four X  ]71[     six X      ] [four X]79[six X]

Great! Now we can simply take the array [75, 71, 79], insert four placeholder values before each element and six after, and then interleave it with the range 0..24.
But wait, what happened to 17? Remember, the top line in all of these examples has been missing 17. We can simply remove the 17 after interleaving; but this leaves another delightfully evil possibility open. You guessed it—the placeholder value we've been referring to as X will be 17. This allows us to remove both the extraneous 17 and all the placeholder values in one fell swoop.
Finally! Here's the code used to implement this:
mC+913d-.iU25smXm17hT4Cd"KGO"17
              m         "KGO"    for each char in the string "KGO"...
                      Cd         take its ASCII value ("KGO" -> 75,71,79)
                m17hT            generate an 11-element array filled with 17
               X     4           replace the 5th element with the ASCII value ^^
             s                   concatenate all of these together
        .iU25                    interleave with range(25)
       -                     17  remove all the 17s
m     d                          for each value in the resulting array...
  +913                           add 913 (to get the real character value)
 C                               convert to character

Julia, 138 bytes
f(x,d=digits(x))=reverse(join([d[i]>0?[["ΑΒΓΔΕϜΖΗΘ","ΙΚΛΜΝΞΟΠϘ","ΡΣΤΥΦΧΨΩϠ"][i]...][d[i]]:""for i=1:endof(d)]))

This is a function that accepts an integer and returns a string.
For each digit in the input in reversed order, we get the character corresponding to that digit from the appropriate string then combine the characters and reverse the result. For any digits that are 0, we simply use the empty string.

JavaScript (ES6), 120 115 bytes
n=>(s=n+"").replace(/./g,(d,i)=>d--?"ΑΒΓΔΕϜΖΗΘΙΚΛΜΝΞΟΠϘΡΣΤΥΦΧΨΩϠ"[d+9*(s.length+~i)]:"")

Byte count is using UTF-8. It's 88 characters long. Input is a number.
Test

var solution = n=>(s=n+"").replace(/./g,(d,i)=>d--?"ΑΒΓΔΕϜΖΗΘΙΚΛΜΝΞΟΠϘΡΣΤΥΦΧΨΩϠ"[d+9*(s.length+~i)]:"")
var testCases = [ 123, 8, 777, 100, 606, 700, 803 ];
document.write("<pre>"+testCases.map(c=>c+": "+solution(c)).join("\n"));

Retina, 57 bytes

11 bytes saved thanks to @Martin Büttner.

Simple transliterate with appropriate character ranges and 0 deletion on each digit.
T`d`_ΡΣ-ΩϠ`.(?=..)
T`d`_Ι-ΠϘ`.\B
T`d`_Α-ΕϜΖ-Θ

Try it online. (First line added to allow all testcases to run together.)

Martin also suggested this one for the same score:
T`d`_J-R`.(?=..)
T`d`_L`.\B
T`dL`_Α-ΕϜΖ-ΠϘΡΣ-ΩϠ

Here's 57 (and a slightly more convenient test framework that doesn't require modifying the actual code).

Different idea, also 57.

Python 3, 118 bytes
f=lambda n,i=3:i*"_"and f(n//10,i-1)+"   ΡΙΑΣΚΒΤΛΓΥΜΔΦΝΕΧΞϜΨΟΖΩΠΗϠϘΘ"[i-1::3][n%10].strip()

Nice work with switching the order of operands in i*"_"and to avoid the space. I wouldn't have found that.

Julia, 84 bytes
f(x,p=0)=x>0?f(x÷10,p+9)"$(x%10<1?"":"/0123z456789:;<=>v?ABCDEFG~"[p+x%10]+866)":""

Try it online!

JavaScript (ES6), 83 characters, 110 bytes
n=>`${1e3+n}`.replace(/./g,(d,i)=>i--&&d--?"ΡΣΤΥΦΧΨΩϠΙΚΛΜΝΞΟΠϘΑΒΓΔΕϜΖΗΘ"[d+9*i]:"")

Ah, I almost tried this approach but somehow I forgot that 0s are replaced with nothing and thought they would break it!

@user81655 The command-line interpreter I use adds a byte to the length for the newline character (unless the lambda is a block), but today I was using the browser console, which doesn't. Oops.

Perl 6, 102 bytes
{[~] <ΡΣΤΥΦΧΨΩϠ ΙΚΛΜΝΞΟΠϘ ΑΒΓΔΕϜΖΗΘ>>>.&{('',|$^b.comb)[$_/100*10**$++%*]}}

Try it online!

Ruby, 134 bytes
Basic lookup dealie using modulus. It probably can be optimized somewhere, but Ruby won't coerce strings into integers the way Javascript can, haha
->n{((0<d=n/100)?"ΡΣΤΥΦΧΨΩϠ"[d-1]:"")+((0<d=n%100/10)?"ΙΚΛΜΝΞΟΠϘ"[d-1]:"")+((0<n%=10)?"ΑΒΓΔΕϜΖΗΘ"[n-1]:"")}

Please see edit -- I changed the character for Koppa.

All right, it's fixed.


text:
m-nomial coefficient
While the binomial coefficient are the coefficients of \$(1+x)^n\$, m-nomial coefficients are the coefficients of \$(1+x+x^2+...+x^{m-1})^n\$.
For example, \$m(3,5,6)\$ is the coefficient of \$x^6\$ in the expansion of \$(1+x+x^2)^5\$.
Write a program/function that takes 3 numbers as input and outputs the corresponding m-nomial coefficient.
Details

Input can be taken via any reasonable method.
Everything out of range is \$0\$, for example \$m(2,0,-1) = m(2,5,6) = 0\$
The first argument will be positive.
The second argument will not be negative.
All three arguments will be integers.

Testcases
Inputs:
[1,0,0]
[2,5,6]
[3,5,6]
[4,5,-1]

Outputs:
1
0
45
0

Scoring
This is code-golf. Shortest solution in bytes wins.

It's strange that a negative exponent gives a result of zero, since it gives a nonzero power series.

Why is m(0,0,0)=1 ? Any m(0, x, y) should be based on a polynomial with NO terms (not even 1) so it's really out of range and should give 0 (I'd even count it as invalid input)

@TonHospel Sorry, thanks, edited.

Thematically related.

@MartinBüttner If you are counting "thematically related" as related, then all [tag:arithmetic] and [tag:regex-golf] are related.

@KennyLau Both challenges are motivated by the same combinatorial problem, which I think makes them quite closely related. If someone is interested in either of them, they might be interested in the other. Barring a [tag:multinomial] tag, the best way to let people find them, is to post them in a comment, such that they show up as Linked in the sidebar.

Jelly, 6 bytes
ṗ’S€ċ⁵

This is a full program that accepts m, n and the exponent as separate command line arguments.
Try it online!
How it works
The problem boils down to counting the number of ways we can express the exponent as an ordered sum of exactly n integers between 0 and m - 1 (both inclusive).
ṗ’S€ċ⁵  Main link. Arguments: m, n, k

ṗ       Cartesian product; yield the array of all lists of exactly n elements of
        [1, ..., m].
 ’      Decrement all integers in the resulting 2D list.
  S€    Compute the sum of each individual list.
     ⁵  Yield k.
    ċ   Count the number of times k appears in the list of sums.

Perl, 63 60 59 57 bytes
Includes +2 for -pa
Give input parameters on STDIN
mnomial.pl <<< "3 5 6"

#!/usr/bin/perl -pa
$_=/-/^($_--,1x$F[2])=~/^(1{0,$_}){$F[1]}$(??{++$;})/+$

As a perl programmer I just know that every problem is really a regex in disguise...
Explanation:
m(3,5,6) can be seen as the number of ways you can get 6 by adding 5 integers in the range [0..2]. You can write a regex matching such a partition using:
1 x 6 = /^(1{0,2}){5}$/

However once a single solution is found the regex stops. We need to fail the found solution to get the regex to backtrack to the next solution and count the failures. In perl this can be done by extending the regex at runtime with something that is sure to fail, e.g. by demanding that something comes after the end of the string:
 1 x 6 = /^(1{0,2}){5}$(??{++$n})/

$n will count the number of failed attempts
My solution is basically this with two modifications:

Output the counter in such a way that you get 0 instead of the empty string if there is no valid partition and the counter never gets incremented
If the third argument is negative it would work if negative string lengths existed, but 1 x -5 is the empty string and 0 can be written exactly one way as sum of zeros, so that would output 1 instead of 0. I xor with the result of /-/to change the 1 back to 0

Without the need to handle a negative third argument this 49 byte solution would be good enough (give one parameter of m(x,y,z) on each line of STDIN in order y \n z \n x \n):
#!/usr/bin/perl -pa
$_=(1x<>)=~/^(1{0,@{[<>-1]}}){@F}$(??{++$;})/+$

Pyth, 29 8 bytes
/sM^UQEE

Try it online!
Uses Dennis' Method.
If the input can be rearranged so that m(3,5,6) is fed in the order of 6,3,5 into the program, an extra byte can be cut off:
/sM^UEE

Try it online!
Original 29-byte approach
.N?|TY?|<Y0>Y*tNT0sm:NtT-YdN1

Test suite.
How it works:
Uses the recurrence formula m(k,n,r) = m(k,n-1,r) + m(k,n-1,r-1) + ... m(k,n-1,r-k+1).
.N?|TY?|<Y0>Y*tNT0sm:NtT-YdN1
.N                             def colon(N,T,Y):
  ?|TY                             if T or Y:
      ?|<Y0>Y*tNT                      if Y<0 or Y>(N-1)*T:
                 0                         return 0
                                       else:
                  sm:NtT-YdN               return sum([colon(N,T-1,Y-d) for d in range(N)])
                                   else:
                            1          return 1

Perl, 55 51 bytes
Includes +2 for -pa
Same basic idea as my other Perl answer, finding partitions of an integer but with a completely different implementation. This version is shorter, but only because I don't have to special case a negative third argument.This version is also totally boring...
Give input for m(x,y,z) on STDIN with a line for each argument in order z, x, y. E.g. to calculate m(3,5,6):
 mnomial.pl
 6
 3
 5
 ^D

mnomial.pl:
#!/usr/bin/perl -pa
$"=",";$_=grep"@F"==eval,glob"+{@{[0..<>-1]}}"x<>

Sage, 71 bytes
lambda a,b,c:(c>=0and(sum(x^i for i in range(a))^b).list()[c:]or[0])[0]

Verify all test cases online
The unnamed lambda function constructs the polynomial and returns the specified coefficient if c is not negative and less than or equal to the degree of the polynomial, else 0.

Python, 64 bytes
f=lambda m,n,k:(k==0)+sum(f(m,n-1,k-t)for t in range(m*(n>0<k)))

As far as code golf goes, this is fairly efficient. Test it on Ideone.

I don't know if we reached a consensus on whether True/False is OK for 1/0, but if so f=lambda m,n,k:n and sum(f(m,n-1,k-t)for t in range(m))or k==0 is shorter.

I tried something similar, but I used +(k==0) because I didn't think Booleans were valid output... I'll write a meta question later. This has come up rather frequently.

@xnor I finally remembered I was going to do this. Should Booleans be allowed where a number is required?

Julia, 50 45 bytes
f(m,n,k)=n>0?sum(t->f(m,n-1,k-t),0:m-1):0^k^2

Try it online!
If digits supported unary, the following approach would be 1 byte shorter.
g(m,n,k)=sum(t->k==sum(digits(t,m)),0:m^n-1)

JavaScript (ES6), 118 bytes
(m,n,k)=>[...Array(n)].reduce(a=>a.map(x=>t+=x,t=0),[...Array(m*n+1)].map((_,i)=>i%m?0:i?x=-x*(n+1-i/m)*m/i:x=1))[k]|0

Works by calculating (xm-1)n/(x-1)n. (xm-1)n is calculated by the binomial theorem and the result is then repeatedly divided by x-1.
Edit: Saved 24 bytes by using a different binomial calculation. Saved 4 bytes by switching to reduce (yay!).

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