text:
Be there or be square!
Everybody has heard of the phrase "be there or be square". So I thought it was time for a challenge about it.
Input
You will take a full absolute directory address as text as input via STDIN or equivalent.
Output
If the directory address exists and is valid, your program will move itself to that folder on your computer. If not, it will output via STDOUT or equivalent the following square:
+-+
| |
+-+

Requirements

Standard loopholes are disallowed.
You may output a single trailing newline if unavoidable.
Your program must produce no output if it has been moved.
Your program must be able to run again wherever it has been moved to.

Assumptions

You may assume that the input is never empty.
You may assume the directory never has a filename appended to the end.
You may assume that the input directory is never the current one.
You may assume you have permissions to write and execute everywhere.

This is code-golf, so shortest answer in bytes wins.

Can we hardcode the filename?

Yes @bookowl you may

Does the path include the filename (c:\users\Joe\program.txt) or not (c:\users\Joe\ )? In the latter case, must the name of the created file be the same as the source?

@LuisMendo you will never get a file as input only a directory

@FinW Sadly, you still haven't answered my question: must the name of the created file be the same as the original file?

@luismendo there isn't a created file

@LuisMendo You're moving, not copying, so I'd assume so.

@FinW Not letting the filename be hardcoded makes it a bit more challenging i guess!

Bash + coreutils, 43 42 bytes
mv -t $1 $0 2> >(:)||echo -n '+-+
| |
+-+'

This avoids printing the trailing newline via the -n flag to echo.
I'm not quite sure what the OP means by allowing a trailing newline if it's "unavoidable".
If it's acceptable to include a trailing newline, change
echo -n '+-+

to
echo '+-+

and save 3 bytes, for 39 bytes total.

PowerShell, 59 62 61 60 bytes
$z=ls($d=$args)-di;('"+-+
| |
+-+"','mv b.ps1 "$d"')[$?]|iex

Try it online!
Explanation
PowerShell's Move-Item cmdlet (mv) renames a file as well, so giving it a directory that doesn't exist as the destination just renames the file to that last component instead (as long as the parent exists), so that was no good.
I could use Test-Path to determine that the destination exists and is a directory, but it's too long Test-Path $d -PathT C.
So instead I'm using Get-ChildItem (ls) with the (shortened) -Directory parameter, and checking $? to see if it was successful. The output if there is any is assigned to $z so that it isn't seen.
That's done in the form of an array with 2 elements, then indexing into the array with the boolean value of $?, which will get coalesced to 0 or 1, so the first array element is chosen if the destination directory doesn't exist, and second if it does.
The first array element is a string containing the box (quoted); newlines are allowed in strings, even when they're not heredocs. The second element is a string containing the move command.
The result of that array selection gets piped into Invoke-Expression (iex) to be executed. This is necessary because of I just leave the actual move command in the array, it gets executed no matter what (to populate the array), which defeats the purpose.

The only reason this doesn't work on TIO is because the script is called .code.tio.ps1, not b.ps1. This works. There seems to be some stray output to STDOUT though. Not sure what causes that.

Wow awesome! The stray output was from gci, my test directories didn't exhibit that because they contained no child items, so this exposed that flaw. It's fixed now by just assigning the output. Thanks @Dennis !

I think ls is a shorter abbreviation for gci

@wat duh, it sure is! I use ls all the time and then in golfing I tend to forget it. Thank you.

Nice. I think this is the first time I've seen $? used in golfing here.

Thanks @AdmBorkBork , My prospective solution on this challenge would have used $? but as far as I can tell it's impossible to convert from a number to a [char] in PowerShell without using alphanumerics.

Octave, 60 57 52 bytes
8 bytes saved thanks to @Stewie
if~movefile('f.m',input(''))disp("+-+\n| |\n+-+")end

This is a script that lives within a file called f.m. When run, it will prompt the user for the folder to move the file to. If the folder does not exist and the move operation fails, then movefile returns false (or 0) otherwise it returns true (or 1). If it's false, we display the string "+-+\n| |\n+-+".

http://codegolf.stackexchange.com/a/107780/31516

Batch, 80 bytes
@if not "%1"=="" move %0 %1\>nul 2>nul&&%1\%~nx0||(echo +-+&echo ^| ^|&echo +-+)

Batch doesn't like it if you move the batch file as it's running, so by invoking %1\%~nx0 (which is the new name of the batch file) Batch stops looking for the old batch file.

Bash + coreutils, 54 bytes
if [ -d $1 ];then mv $0 $1;else echo "+-+
| |
+-+";fi

Simple enough. It does a test to see if the first argument exists, if it exists the program moves itself into the argument, else prints the square.
Does not work on Windows, however it works on Bash on Ubuntu on Windows / WSL. Does not take a drive letter, however I think that has been clarified to be OK.
This account is owned by Mendeleev.

I think you need echo -n so that you don't print a trailing newline.

Python 3, 71 bytes
from shutil import*
try:move('f',input())
except:print("+-+\n| |\n+-+")

It must be in a file named f
Fairly simple. It tries to move itself to whatever directory is given to it on STDIN, and if an error occurs it prints the box.

C 137 bytes
#include<dirent.h> g(char *f,char *z){DIR* d=opendir(z);if(d){strcat(z,f);rename(f,z);}else{puts("+-+");puts("| |");puts("+-+");}}

Ungolfed version:
#include<dirent.h>
g(char *f,char *z)
{
  DIR* d=opendir(z);
  if(d)
  {
    strcat(z,f);
    rename(f,z);
  }
  else
  {
    puts("+-+");
    puts("| |");
    puts("+-+");
  }
}

f accepts the filename and z accepts the directory name. Destination string is a concatenation of z and f. rename() is used to move the file to the new location.
The main() would look like this:
int main(int argc, char *argv[])
{
    g(argv[0]+2,argv[1]); // 1st arg is the Destination string
    return 0;
},

Can definitely shortened somehow!

Ruby, 58+12 = 70 bytes
Uses flags -nrfileutils. Input is piped in from a file w/o newlines into STDIN.
FileUtils.mv$0,File.exist?($_)&&$_ rescue$><<"+-+
| |
+-+"

Minecraft ComputerCraft Lua, 74 bytes
if fs.isDir(...)then fs.move("f",... .."f")else print("+-+\n| |\n+-+")end

Filename is hard-coded as "f". This runs on an in-game computer and runs relative to that computer's directory structure. Uses CC Lua's builtin fs API.
Ungolfed:
local tArgs = { ... }      -- '...' is Lua's vararg syntax, similar to python's *args syntax
if fs.isDir(tArgs[1]) then -- Using '...' is like passing all args separately, extra args are usually ignored
    fs.move("file", tArgs[1] .. "file") -- '..' is Lua's string concatenation syntax
else
    print("+-+\n| |\n+-+") -- print the required output if the directory doesn't exist
end

APL (Dyalog Unicode), 41 bytes
{⎕NEXISTS⍵:'f'⎕NMOVE⍨⍵,'f'⋄3 3⍴'+-+| |'}⎕

Try it online!
filename is hardcoded as f, in the current working directory.


text:
Print 'em goats
Related
Goats are great. Everybody loves goats.
And they also, for some reason, are an excellent complex ascii art for many languages to have built-ins for. Because of this, I personally feel a catalogue to document just how easily a language can print goats is greatly needed.
The Challenge
Given an integer input via any means print that many Goats separated by Newlines.
Your Goat for reference is:
  ___.
 //  \\
((   ''
 \\__,
/6 (%)\,
(__/:";,;\--____----_
;; :';,:';`;,';,;';`,`_
  ;:,;;';';,;':,';';,-Y\
   ;,;,;';';,;':;';'; Z/
   / ;,';';,;';,;';;'
  / / |';/~~~~~\';;'
 ( K  | |      || |
  \_\ | |      || |
   \Z | |      || |
      L_|      LL_|
      LW/      LLW/

Your particular goat may have more whitespace around it, if required.
Example
Given 3 on input, Output:
  ___.
 //  \\
((   ''
 \\__,
/6 (%)\,
(__/:";,;\--____----_
;; :';,:';`;,';,;';`,`_
  ;:,;;';';,;':,';';,-Y\
   ;,;,;';';,;':;';'; Z/
   / ;,';';,;';,;';;'
  / / |';/~~~~~\';;'
 ( K  | |      || |
  \_\ | |      || |
   \Z | |      || |
      L_|      LL_|
      LW/      LLW/
  ___.
 //  \\
((   ''
 \\__,
/6 (%)\,
(__/:";,;\--____----_
;; :';,:';`;,';,;';`,`_
  ;:,;;';';,;':,';';,-Y\
   ;,;,;';';,;':;';'; Z/
   / ;,';';,;';,;';;'
  / / |';/~~~~~\';;'
 ( K  | |      || |
  \_\ | |      || |
   \Z | |      || |
      L_|      LL_|
      LW/      LLW/
  ___.
 //  \\
((   ''
 \\__,
/6 (%)\,
(__/:";,;\--____----_
;; :';,:';`;,';,;';`,`_
  ;:,;;';';,;':,';';,-Y\
   ;,;,;';';,;':;';'; Z/
   / ;,';';,;';,;';;'
  / / |';/~~~~~\';;'
 ( K  | |      || |
  \_\ | |      || |
   \Z | |      || |
      L_|      LL_|
      LW/      LLW/

The Rules

You must take an integer input where 0 < input < 256, and print that many goats.
Goats may vary in whitespace, as long as the shape of the goat is the same.
You must submit a full program.
This is a catalogue, so any language or language version newer than the challenge is acceptable. Like usual, creating a language that prints N goats in 0 bytes isn't incredibly creative. Also, as this is a catalogue, no answer will be accepted.
This is however code-golf, so shortest answer per language.
If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck-derivatives like Alphuck), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

The Catalogue
Shamelessly stolen from The Hello World Challenge
The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:
## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

/* Configuration */

var QUESTION_ID = 107765; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 58375; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '
' + c.body.replace(OVERRIDE_REG, '') + '
';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery(''+lang+'').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

Do we need a newline between each goat?

Goats must be sequential, and not distorted by previous goats. So yes.

I would like to vote as a dupe of the rickroll challenge

I downvoted because this challenge seems to be pandering to languages that have this exact goat art implemented as a built-in. And otherwise it's just copying a fixed string n times, where the string has too little structure to beat hardcoding or general-purpose compression for many languages.

Given some thought, this was a really bad idea for a challenge fueled by nothing else than the laughs. I've voted to Close it myself.

I find it kinda funny that both given answers aren't even matching OP's specified output.. Both answers use " (double quotes) instead of the 'specified' ' (single quotes). Also, every line in OP's 'specified' output is missing a space, although I'm assuming that's just a StackExchange formatting issue?

@ATaco At this moment, none of the answers has a positive score, so you can delete the question if you want to.

Closevoters: there is nothing unclear about this challenge. Downvote challenges that you dislike - don't close-vote them unless they actually have issues.

I close voted this myself, free me from my mistakes

Ruby (2.3), 312 bytes
Hey, at least I didn't use a built-in!
n=gets.to_i
puts "
  ___.
 //  \\\\
((   ''
 \\\\__,
/6 (%)\,
(__/:\";,;\--____----_
;; :';,:';`;,';,;';`,`_
  ;:,;;';';,;':,';';,-Y\\
   ;,;,;';';,;':;';'; Z/
   / ;,';';,;';,;';;'
  / / |';/~~~~~\\';;'
 ( K  | |      || |
  \\_\\ | |      || |
   \\Z | |      || |
      L_|      LL_|
      LW/      LLW/\n"*n

You can save a few bytes by making this a function that accepts a number as an argument Just sayin' ! Returning a string instead of printing would be shorter too, if allowed...

@LevelRiverSt The challenge requires only a full program

Jelly,  194  191 bytes
-3 replacing b24ị with ṃ (a since-developed atom)
“wɦLż8ßȧṛ Ỵ?þġÐ®ạSḍọsñL1⁶ƁṄṫȥẊ`m®Ø⁼ƒ⁺Ė6⁺oHpæİṇµ\ṅṁ⁷V⁶k¡i£}ḣọSƑṭ<ḃṚSØ:kŒxṘıquṂUnƭ⁾DEØẓ×ðH¦ḅċ5pðḳṅ⁶Ḅḍ€®85ɲPp¦Ø0B¥=ẊCƲ<7eØ7ƥ÷8¡ÆḅẎṣṂ(hþẓ]ƲƤȦE¶ƙCɼƭżÆµėṙṾḞ\&O ¬ṆñKmɠ’ṃ“ .¶/\(',6%):";-`YZ|~KLW_”Ṅ¡’

Try it online!
How?
The 24 distinct characters from which the goat is constructed are:
.¶/\(',6%):";-`YZ|~KLW_
where ¶ represents a line feed, and the first character is a space.
A goat may now be thought of as a 277 digit base 24 number, G, where each digit represents the 1-based and mod-24 index of a character in the above list.
The code forms G using base 250, transforms G to a base 24 representation as a list of digits and indexes into the character set. It then repeats an instruction to print the resulting character array and a line feed n-1 times.
a long string of bytes
  |
“...’ṃ“ .¶/\(',6%):";-`YZ|~KLW_”Ṅ¡’ - Main link: n
“...’                               - make G using base 250
      “ .¶/\(',6%):";-`YZ|~KLW_”    - the characters of a goat, ¶ being a line feed
     ṃ                              - base decompression (use the 24 characters as the base 24 digits)
                                  ’ - decrement n to give n-1
                                 ¡  - repeat the previous link n-1 times
                                Ṅ   - print the result and a line feed

The only slight complication is that Jelly's base 250 representation is 1-based and the indexing is modular, so when a zero digit is present it will be a 250 digit - the remedy is to reduce the next most significant digit by 1, and repeat if that becomes a zero. (This occasionally will make for shorter code, but not this time.)

JavaScript (ES6), 306 bytes
Some slightly compressed goats...

[..."abcdefghijklmnopqrs"].map((c,i)=>s=s.split(c).join(`
 jnk me|h--~~|omLqq
r__pr,; |rr';  \\`.substr(i*2,2)),s=`rl_.a//rss
((r ''assl,
/6 (%)s,
(l/:";nsfllff_
;; :q,:q\`;,qnq\`,\`_k;:n;b':,j,-Ysc;nnb':;j Z/c/ ;,bqnq;'k/ /oq/gg~sq;'a( Krhdks_soodcsZood
i_|iL_|
iW/iLW/
`)&&console.log(s.repeat(prompt()))

SOGL, 174 bytes
▼īj-ηī¤ķJφB╝║α$a3╬ο'Βw)woE;@ē¹█lα.⁶↓!mΙ;┌.}γ§⁹≡r³╝╚wΓδΘργ±:⁾▓√׀⅝╝█%čczgΧMθL`«UΓ║νZ█č└sΩ±⅛mΤCρ2o¦≠]ΖøΙΧ²`žB+9‰κ╚¦¤Ƨ¹≥ΗxƧWJ∞┐∑¹±YEōΟ№Χθ≥⁹~E∞θτ-‘*

vary simple (from the outside)
...‘   push that string decompressed
    *  multiply by input

I had to chop the goat up into pieces of strings that each when compressed is as small as possible, which then get each compressed and joined together. more info

Chopping up goats? D: that's mean :P

RProgN, 16 bytes
"goat " read m C

I assume this is the answer you've been waiting for...
Try it online!

Lua, 306 bytes
:rep()'s io.read() times.
print(([[  ___.
 //  \\
((   ''
 \\__,
/6 (%)\,
(__/:";,;\--____----_
;; :';,:';`;,';,;';`,`_
  ;:,;;';';,;':,';';,-Y\
   ;,;,;';';,;':;';'; Z/
   / ;,';';,;';,;';;'
  / / |';/~~~~~\';;'
 ( K  | |      || |
  \_\ | |      || |
   \Z | |      || |
      L_|      LL_|
      LW/      LLW/
]]):rep(io.read()))

source: Stack Exchange

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

sort: votes


text:
Split a grid into a grid
Introduction
There is a small village with nothing but a few houses and empty fields.
The local bureaucrats want to divide the village into lots so that each lot contains exactly one house, and the borders of the lots form a nice straight-line grid.
Your task is to determine whether this is possible.
The task
Your input is a rectangular 2D array of bits; 1 represents a house and 0 an empty field.
Its size will be at least 1×1, and it will contain at least one 1.
You can take the input in any reasonable format (nested list of integers, list of strings, multiline string etc).
Your program shall determine whether the array can be divided into grid cells using straight horizontal and vertical lines so that each grid cell contains exactly one 1.
The grid cells may have different sizes and shapes, although they will always be rectangular.
The lines must run from one edge of the array to the opposite edge.
For example, the following is a valid division of an array:
00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1

whereas the following division is not valid, since there are grid cells with no 1s or more than one 1:
00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1

If a valid division exists, you shall output a truthy value, and otherwise a falsy value.
Rules and scoring
You can write a full program or a function.
The lowest byte count wins.
Test cases
[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True

can [ [0,0,1,0,1] , [1,0,0,1,0] , [0,0,0,1,0] ] be divided into: 3X1, 2X1, 3X2, 2X1, 2X1 rectangles in this manner or not?
001|01
---+--
100|10
+--
000|10

@officialaimm No, that is not valid. The grid lines must run from one side of the array all the way to the other side.

Proposed test case: [[1, 0, 1], [0, 1, 0], [1, 0, 0]] That was the only 3x3 matrix my new approach was failing for.

@Dennis Thanks, added.

Pyth, 30 29 26 24 23 bytes
sm.Asmmq1ssbCkds./MC./M

Try it online.
I'm sure this will get shorter. This is O(2mn), where m and n are the width and height of the array, but completes the last two test cases in 45 seconds on my laptop on battery (i5-5200U with limited performance).
Outputs the number of solutions.
Explanation
Five-dimensional arrays are really fun to work with.</sarcasm> You are not supposed to understand how this works even with the explanation.
                    ./M    Find all partitions of each row. Now we have a list of rows,
                           each containing the ways to split the row, each containing
                           the parts of the split (3D).
                   C       Transpose. Now we have a list of ways to split the columns,
                           each containing the rows, each containing the parts of the
                           row (3D).
                ./M        Find all partitions of each row list. Now we have a list of
                           ways to split the columns, each containing the ways to split
                           the rows, each containing the bunch of rows, each containing
                           the rows in the bunch, each containing the parts of the row
                           (6D).
               s           Combine the ways to split rows & columns into one array (5D).
 m            d            Do the following for each way to split rows & columns (4D):
     m       k                 Do the following for each bunch of rows (3D):
            C                      Transpose the array. We now have a list of column
                                   groups, each containing the row parts (3D).
      m    b                       Do the following for each column group (2D):
          s                            Combine the row parts in the column group. We now
                                       have the list of cells in this row/column group
                                       (1D).
         s                             Sum the cells.
       q1                              Check if the sum is one.
                                   We now have the list of booleans that tell if each
                                   row/column group is valid (1D).
                               We now have the 2D list of booleans that tell if each
                               row/column group in each bunch of rows is valid. (2D)
    s                          Combine the 2D list of booleans to 1D.
  .A                           Check if all values are truthy; if the split is valid.
                           We now have the validity of each split.
s                          Sum the list to get the number of valid solutions.

Jelly, 22 bytes
ŒṖḅ1S€€=1Ȧ€
SŒṖ⁸ṁþÇ€FS

Try it online!

Haskell, 116 bytes
import Data.List
m(a:b)=[a:e|e<-m b]++[zipWith(+)a d:e|d:e<-m b];m e=[e]
d=(any$any$all$all(==1)).map(m.transpose).m

Try it online!

This does not compile. Please delete your answer until it is fixed. There is also a lot of golfing potential, eg. renaming mergerows to m.

I was planning to run out of competition due to the hard-to-beat Pyth brevity and thank thee @Laikoni for spotting I likely messed up my indentation braces.

This incorrectly gives False on [[1,0],[0,1],[1,0]]. The problem is that a greedy collapse can get in the way of a later better collapse.

Indeed, my  [[1,1],[1,0]] collapse falsely obstructs the [[1],[1],[1]] solution.  Let me sleep over this or ought i delete?

@RomanCzyborra I'd suggest deleting while you sleep over it.

Did that! Now better?

I think you can save a byte by swapping the two cases of m and doing m x=[x] on the second one. We have a consensus that anonymous functions don't need to be bound to a name, so you can drop the d= part. Also, you should put the verification snippet q in a separate code block; I think you have miscounted your bytes.

Thank you for the [x] indeed.  Dropping the d= would fail to compile though given that my module already depends on Data.List.transpose and its rowmerges helper m.  Byte count lazily comes from head -3|wc -c and thus counts a trailing newline and already disregards the  convenience test q.

I count 116 bytes.

i know, you chopped the trailing '\n'

Jelly, 20 bytes
ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS

This is still a brute-force solution, but it's quite a bit faster than my other answer – which cannot cope with the last two test cases on TIO – and handles all test cases in ~4 seconds.
Try it online!
How it works
ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS  Main link. Argument: M (matrix, array of rows)

ŒṖ                    Compute all partitions, i.e., all groupings of M's rows.
  S€€                 Map sum over all individual groupings, collapsing the grouped
                      rows into a single row.
        Ðf            Filter; keep only those partially collapsed matrices for
                      which the link to the left returns a truthy value.
       $                Group the two links to the left into a monadic chain.
     Ị                    Insignificant; map 0 and 1 to 1, greater integers to 0.
      Ȧ                   All; return 1 iff the matrix contains no zeroes.
          Z€          Zip/transpose all kept matrices,
            µ         Combine all links to the left into a monadic chain.
             ⁺€       Duplicate the chain and map it over the individual results
                      from the first call. We now have all possible combinations
                      of row and column groupings (represented by the corresponding
                      matrices of collapsed rows and columns) that do not have a
                      2 anywhere. However, they still may contain zeroes.
               Ȧ€€    Map the all atom over the matrices, returning 1 only for
                      matrices that consist entirely of ones.
                  FS  Flatten and sum, counting the number of valid divisions.

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


text:
Find a Glider Synthesis (Game of Life)
Challenge Summary
In summary, the challenge is to provide the glider synthesis for a Game of Life configuration, which is your input.
What does this mean?
Well, firstly, let me explain a few terms.
By Game of Life, I mean Conway's Game of Life. If you don't know what this is, you can read the Wikipedia article at https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life. It explains it pretty well.
If you don't know what a glider synthesis is, it's pretty much a bunch of gliders that will form a specific configuration after a certain number of steps. Read http://www.conwaylife.com/wiki/Glider_synthesis for more details.
Okay, what are the rules?

Standard Loopholes Apply
The glider synthesis must only consist of the standard 5-cell gliders, but they can start in any of their 4 states/colors.
The glider synthesis is allowed to create other things, as long as they do not share a neighbor with and are not a neighbor of any living cell within the desired outcome. Moving structures can be created as byproducts as well.
The desired outcome will be at most 10x10.
The desired outcome will be achievable with a glider synthesis.

Actual Specifics
Input will be given as a 2D array of truthy/falsy values, which indicates the desired outcome (the desired outcome will be reachable). The array will be at most 10 by 10 in size. The desired outcome will not necessarily be a stable configuration. Output will also be given in the same format, indicating a valid glider synthesis (as defined by the rules above) to produce this outcome (the output can be as large as necessary). The output doesn't have a size limit. It doesn't necessarily need to be the fastest or the smallest; as long as it's valid, it's fine.
Summary of Everything
You will be given input as a 10x10 or smaller 2D array of truthy/falsy values of some sort. This could be a 2D array of something, an array of strings, a multi-line string, etc. Your task is to find a configuration using only standard 5-cell diagonal gliders that will eventually result in this outcome, where other byproducts are permitted so long as they do not interact in any way with the desired outcome. Given this configuration, you are to output a 2D array of truthy/falsy values in some format.
Winning
This is a code-golf challenge, so the shortest program will win. Tiebreak is by earlier submission.
In terms of test cases, you can just put the program output into a GoL emulator and run it and see if you get the desired output eventually.
Tips/Ideas
I don't have many well developed ideas myself, but what you could try to do is find all possible reverses of a GoL scenario (i.e. find all configurations that could evolve to the current one), though that's going to take a lot of power quickly.

What makes you think that this is even possible?

Can the input be unreachable? What the max size of the array we are allowed to output (if any)?

@orlp Nothing is impossible...

@orlp Nothing. I'm not sure this is possible. However, brute-forcing will technically work, but it will take practically forever to get a solution.

@Sefa Edited answers into question. The input will always be possible, and the output has no limit.

@KritixiLithos Solve the halting problem. Go.

@mbomb007 It's possible if you have infinite time, which is probably what you'll need for this one too.

https://cgl.herokuapp.com/?rule=23/3&seed=bo$o$3o If you want, you can use this program to verify solutions. seed is formatted as standard RLE encoding for automaton files. For example, like the last 3 lines on this one: https://cgl.herokuapp.com/patterns/gosperglidergun Exclamation to terminate the seed is unnecessary in the query parameter though

Someone with more time on their hands than I have might find http://www.conwaylife.com/wiki/Category:Pattern_constructible_by_a_given_number_of_gliders useful.

a 10x10 array of black/white squares is not 100 test cases, it is 2^100 test cases which is a slightly larger number ;)

@Sparr Yeah... I just realized that too... I don't think my brain was working earlier.

We cant even reverse game of life, do you think this is possible?

@MatthewRoh Given enough time, it is possible, though it's probably NP-complete (which is why I said given enough time).

This is not possible, for all configurations at least: some GoL configurations have no predecessor. See garden of eden. And if you're given only gliders as a starting point, you're certainly even more limited. Finally, solving this for the configurations where it is possible is non trivial. A more feasible challenge would be to output the initial gliders to draw a still character string given as input on the grid.

@dim I realize now that the challenge is rather unfeasible challenge. And thanks for the link! But in this challenge, you can assume everything has a valid glider synthesis.

You would have to allow that programs don't need to terminate for this to be possible

@MilkyWay90 how so

@HyperNeutrino Conway's Game of Life has been proven to be Turing-Complete, hence unsolvable without infinite time (A Turing Machine needs infinite time to solve the halting problem for it, because the Busy Beaver function is uncomputable)

@MilkyWay90 I'm sorry, you're going to have to explain that in simpler terms. You just threw like three concepts that I only vaguely know that don't seem related to each other or the challenge in any way to me.

@HyperNeutrino Wait nevermind, I was wrong

This is definitely possible by creating multiple GOL simulations (not all at once) and stepping them all independently at the same rate, and simply brute forcing the initial conditons. However, are there any time requirements here?

@mypronounismonicareinstate there are none at all


text:
The Tax Historian
Introduction
There is a tax collector that has some trouble managing the taxes of his kingdom: the historical records have burnt down in a great fire.
He wants to find out how many possible pasts there could be in terms of where the current money was inherited from. Luckily, his kingdom is very simple.
The kingdom can be modelled by a 2D boolean matrix, where l represents someone who has inherited money, and O represents someone who has not. For example:
l O l l

O O O l

l O l O

O O O l

(It will always be a rectangle)
In the next generation, the kingdom is smaller (The wolves are strong!).
The next generation would look like this, superimposed on the previous generation (x is a placeholder for a descendent in the next generation)
l O l l
 x x x
O O O l
 x x x
l O l O
 x x x
O O O l

A descendent will look at the ancestors that are directly around them (So the top-left x will see {l, O, O, O}, called an Unaligned rectangular neighbourhood)
If only one ancestor has inherited money, the descendant will inherit money from them. If more than one ancestor has inherited money, they will squabble and the descendant will end up not inheriting money. If no one has inherited money, the descendant will not inherit any money.
(More than one descendant can inherit from one ancestor)
So, the next generation would look like:

 l l O

 l l O

 l l O

Challenge
Input
The current state of the generation, as an array of arrays of any two distinct values, where the inner arrays are all of the same length.
E.g., for the example above, it could be:
[
  [True, True, False],
  [True, True, False],
  [True, True, False]
]

Output
An integer representing the number of unique previous generations where the next generation is the input.
You can assume that the answer will always be less than 2^30 - 1. (or 1073741823).
The previous generation would be called a "preimage" and this challenge would be to count the preimages.
Scoring
This is a fastest-code challenge, so each submission will be tested on my computer, and the submission that takes the least time will be the winner.
Example Input and Output
(Where 1 is a descendent who inherited money, and 0 is a descendent who did not inherit money)
Input:
[[1, 0, 1],
 [0, 1, 0],
 [1, 0, 1]]

Output:
4

Input:
[[1, 0, 1, 0, 0, 1, 1, 1],
 [1, 0, 1, 0, 0, 0, 1, 0],
 [1, 1, 1, 0, 0, 0, 1, 0],
 [1, 0, 1, 0, 0, 0, 1, 0],
 [1, 0, 1, 0, 0, 1, 1, 1]]

Output:
254

Input:
[[1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
 [1, 1, 0, 0, 0, 0, 1, 1, 1, 0],
 [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0, 0, 1, 1, 0, 0]]

Output:
11567

"lOOlLOOOOLLlololoLOLOLOOLOLOLOLL" is all I saw when I first opened the page.

C++ using the BuDDy library
This seemed like a nice excuse to play with binary decision diagrams.
The kingdom is converted into a big boolean formula where we have to count the number of ways in which it can be satisfied. That can (sometimes) be done more efficiently than it sounds.
The kingdom must be given as a program constant as a flat array and explicitely given dimensions. (Nice input is left as an execise for the reader :-)
Here is the embarrassingly simple code:
#include <iostream>
#include <bdd.h>

// describe the kingdom here:

constexpr int ROWS = 4;
constexpr int COLS = 10;

constexpr int a[] = {
   1, 1, 0, 1, 0, 1, 0, 1, 1, 0,
   1, 1, 0, 0, 0, 0, 1, 1, 1, 0,
   1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
   0, 1, 0, 0, 0, 0, 1, 1, 0, 0,
};

// end of description

// check dimensions
static_assert(ROWS*COLS*sizeof(int)==sizeof(a),
          "ROWS*COLS must be the number of entries of a");

// dimensions of previous generation
constexpr int R1 = ROWS+1;
constexpr int C1 = COLS+1;

// condition that exactly one is true
bdd one(bdd a, bdd b, bdd c, bdd d){
  bdd q = a & !b & !c & !d;
  q |= !a & b & !c & !d;
  q |= !a & !b & c & !d;
  q |= !a & !b & !c & d;
  return q;
}

int main()
{
  bdd_init(1000000, 10000); // tuneable, but not too important
  bdd_setvarnum(R1*C1);
  bdd q { bddtrue };
  for(int j=COLS-1; j>=0; j--) // handle high vars first
    for (int i=ROWS-1; i>=0; i--){
      int x=i+R1*j;
      bdd p=one(bdd_ithvar(x), bdd_ithvar(x+1),
                bdd_ithvar(x+R1), bdd_ithvar(x+R1+1));
      if (!a[COLS*i+j])
        p = !p;
      q &= p;
    }
  std::cout << "There are " << bdd_satcount(q) << " preimages\n";
  bdd_done();
}

To compile with debian 8 (jessie), install libbdd-dev and do g++ -std=c++11 -o hist hist.cpp -lbdd. (Optimizing options make almost no difference because the real work is done in the library.)
Big examples can lead to messages about garbage collection. They could be suppressed, but I prefer to see them.
bdd_satcount returns a double, but that is good enough for the expected range of results. The same counting technique is possible with exact (big) integers.
The code is optimized for ROWS<COLS. If you have a lot more rows than columns, it might be a good idea to transpose the matrix.

2.39 seconds. This is half the time that I had! Marking this as accepted.

@Artyer: Would you care to post your longest-running hidden test case? As well as your solution, if you'd like.

@AndrewEpstein I've recently had a harddrive failure and lost both the code and the original test cases (There were hundreds of them, and they were max 300-wide, 10-high i think). Sorry.

Python 2.7
This is just a naïve first attempt. It's not particularly fast, but it is correct.
The first observation is that each cell is dependent on exactly four cells in the previous generation. We can represent those four cells as a 4-bit number (0-15). According to the rules, if exactly one neighboring cell in the previous generation is 1, then a given cell in the current generation will be 1, otherwise, it will be 0. Those correspond to the powers of two, namely, [1, 2, 4, 8]. When the four ancestors are represented as a 4-bit number, any other number will result in a 0 in the current generation. With this information, upon seeing a cell in the current generation, we can narrow down the possibilities of the neighborhood in the previous generation to one of four or one of twelve possibilities respectively.
I've chosen to represent the neighborhood as follows:
32
10

where 0 is the least-significant bit, and so on.
The second observation is that for two adjacent cells in the current generation, the two neighborhoods from the previous generation overlap:
32  32
10  10

or:
32
10

32
10

In the horizontal case, the 2 from the left neighborhood overlaps with the 3 from the right neighborhood, and similarly with the 0 on the left and the 1 on the right. In the vertical case, the 1 from the top neighborhood overlaps with the 3 from the bottom neighborhood, and similarly with the 0 on the top and the 2 on the bottom.
This overlap means that we can narrow down the possibilities for yet-unchosen neighborhoods based on what we've already chosen. The code works it's way from left to right, top to bottom, in a recursive depth-first search for possible preimages. The following diagram indicates which previous neighborhoods we have to consider when looking at the possible neighborhoods of a current cell:
f = free choice
h = only have to look at the neighborhood to the left
v = only have to look at the neighborhood to the top
b = have to look at both left and top neighborhoods

[f, h, h, h, h],
[v, b, b, b, b],
[v, b, b, b, b],
[v, b, b, b, b]

Here's the code:

def good_horizontal(left, right):
    if (left & 4) >> 2 != (right & 8) >> 3:
        return False
    if left & 1 != (right & 2) >> 1:
        return False
    return True

def good_vertical(bottom, top):
    if (bottom & 8) >> 3 != (top & 2) >> 1:
        return False
    if (bottom & 4) >> 2 != (top & 1):
        return False
    return True

ones = [1, 2, 4, 8]
zeros = [0, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]
h = {}
v = {}

for i in range(16):
    h[i] = [j for j in range(16) if good_horizontal(i, j)]
    v[i] = [j for j in range(16) if good_vertical(i, j)]

def solve(arr):
    height = len(arr)
    width = len(arr[0])

    if height == 1 and width == 1:
        if arr[0][0] == 1:
            return 4
        else:
            return 12
    return solve_helper(arr)

def solve_helper(arr, i=0, j=0, partial=None):
    height = len(arr)
    width = len(arr[0])

    if arr[i][j] == 1:
        poss = ones
    else:
        poss = zeros

    if i == height - 1 and j == width - 1:  # We made it to the end of this chain
        if height == 1:
            return sum([1 for p in poss if p in h[partial[-1][-1]]])
        else:
            return sum([1 for p in poss if partial[-2][-1] in v[p] and p in h[partial[-1][-1]]])

    if j == width - 1:
        new_i, new_j = i + 1, 0
    else:
        new_i, new_j = i, j + 1

    if i == 0:
        if j == 0:
            # first call
            return sum([solve_helper(arr, new_i, new_j, [[p]]) for p in poss])
        # still in the first row
        return sum([solve_helper(arr, new_i, new_j, [partial[0] + [p]]) for p in poss if p in h[partial[0][-1]]])
    if j == 0:  # starting a new row
        return sum([solve_helper(arr, new_i, new_j, [r for r in partial + [[p]]]) for p in poss if partial[i - 1][0] in v[p]])
    return sum([solve_helper(arr, new_i, new_j, [r for r in partial[:-1] + ([partial[-1] + [p]])]) for p in poss if p in h[partial[i][-1]] and partial[i - 1][j] in v[p]])

To run it:
test3 = [
    [1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 1, 1, 0, 0]
]

expected3 = 11567

assert(solve(test3) == expected3)

This is taking to long to do the hidden test cases, so I'm not scoring this submission. Try a different algorithm, as this on has too high of a time complexity (It's O(<something>^n) I think.)


text:
Total Derangement (Difficulty Level: Hard)
The problem: Write a function which, given a cycle length n and a number of cycles m, where 'm' is within [2, n-2], generates m random cycles, each of length n, and all of which are derangements of each other. Then n=7, for example, m could be 2, 3, 4, or 5. All possible sets of m cycles of length n that fit the criteria should have equal probability of occurring.
What is a cycle? Imagine you're hopping around a list. Each element in the list is a number corresponding to another position on the list. Start out at the first element, and update your position to be whatever index is at that element:
CycleThrough(list)
{
    pos = 0;
    while(true) { pos = list[pos]; }
}

If you can visit every element in the list and get back to the start using this method, it's a cycle. If you can't, it's not. Here are a few examples of cycles:
(0)
(1, 0)
(1, 2, 0)
(2, 0, 1)
(1, 2, 3, 0)
(1, 3, 0, 2)
(2, 4, 1, 0, 3)

Take the last cycle. It goes 0 -> 2 -> 1 -> 4 -> 3 -> 0. What isn't a cycle? Take (4, 0, 3, 2, 1)- this isn't a cycle because it goes 0 -> 4 -> 1 -> 0, and you won't hit 3 or 2. Or take (1, 1) - it goes 0 -> 1 -> 1 -> 1 -> 1... and it never gets back to 0, so it's not a cycle.
What does it mean for two cycles to be deranged? Lets say you have two cycles, cycle A and cycle B. If A[i] never equals B[i], they're derangements of each other. If you have more than two cycles, they're all derangements of each other if all pairs of cycles are derangements.
The fastest algorithm (in time complexity) wins.
Example outputs for n=5, m=3:
{{1, 4, 3, 0, 2}, {3, 0, 4, 2, 1}, {2, 3, 1, 4, 0}}
{{3, 0, 4, 2, 1}, {2, 4, 3, 1, 0}, {4, 3, 1, 0, 2}}
{{3, 0, 1, 4, 2}, {2, 4, 3, 1, 0}, {4, 3, 0, 2, 1}}
{{3, 4, 0, 1, 2}, {1, 2, 4, 0, 3}, {2, 3, 1, 4, 0}}
{{3, 4, 0, 1, 2}, {4, 0, 1, 2, 3}, {1, 2, 3, 4, 0}}
{{4, 2, 0, 1, 3}, {2, 3, 1, 4, 0}, {1, 4, 3, 0, 2}}
{{4, 3, 0, 2, 1}, {2, 4, 1, 0, 3}, {3, 2, 4, 1, 0}}
{{4, 0, 1, 2, 3}, {3, 2, 0, 4, 1}, {2, 4, 3, 1, 0}}
{{3, 0, 1, 4, 2}, {4, 2, 0, 1, 3}, {1, 3, 4, 2, 0}}
{{3, 2, 0, 4, 1}, {4, 0, 1, 2, 3}, {1, 4, 3, 0, 2}}

Example outputs for n = 4...12, m = n-2
{{2, 3, 1, 0}, {3, 2, 0, 1}}
{{4, 0, 1, 2, 3}, {1, 2, 3, 4, 0}, {2, 3, 4, 0, 1}}
{{4, 2, 5, 1, 3, 0}, {2, 5, 4, 0, 1, 3}, {3, 4, 1, 5, 0, 2}, {5, 3, 0, 4, 2, 1}}
{{6, 3, 5, 0, 1, 4, 2}, {1, 5, 4, 2, 6, 3, 0}, {5, 2, 3, 6, 0, 1, 4}, {4, 0, 6, 1, 5, 2, 3}, {3, 6, 1, 4, 2, 0, 5}}
{{7, 0, 3, 6, 1, 2, 4, 5}, {6, 2, 0, 7, 5, 1, 3, 4}, {1, 5, 4, 0, 7, 6, 2, 3}, {5, 3, 6, 4, 0, 7, 1, 2}, {4, 6, 7, 2, 3, 0, 5, 1}, {3, 7, 1, 5, 2, 4, 0, 6}}
{{2, 3, 6, 8, 0, 4, 1, 5, 7}, {8, 5, 0, 2, 1, 6, 7, 3, 4}, {3, 2, 4, 5, 7, 1, 8, 6, 0}, {4, 6, 5, 7, 8, 0, 3, 2, 1}, {1, 8, 7, 4, 6, 3, 2, 0, 5}, {7, 0, 3, 1, 5, 2, 4, 8, 6}, {5, 7, 1, 6, 3, 8, 0, 4, 2}}
{{1, 4, 5, 6, 2, 9, 8, 3, 0, 7}, {4, 2, 7, 1, 9, 3, 5, 0, 6, 8}, {9, 5, 0, 8, 3, 7, 1, 4, 2, 6}, {5, 7, 6, 0, 8, 2, 4, 9, 1, 3}, {7, 6, 8, 9, 5, 0, 3, 1, 4, 2}, {2, 8, 9, 7, 1, 6, 0, 5, 3, 4}, {8, 0, 3, 5, 6, 4, 9, 2, 7, 1}, {6, 3, 4, 2, 0, 1, 7, 8, 9, 5}}
{{3, 4, 1, 5, 8, 9, 0, 10, 6, 7, 2}, {1, 2, 6, 4, 10, 8, 5, 9, 7, 3, 0}, {10, 6, 3, 1, 9, 7, 8, 4, 0, 2, 5}, {8, 3, 0, 7, 2, 6, 10, 5, 9, 1, 4}, {9, 5, 7, 6, 0, 3, 2, 8, 4, 10, 1}, {2, 0, 9, 10, 7, 1, 4, 3, 5, 6, 8}, {6, 7, 5, 8, 3, 4, 1, 2, 10, 0, 9}, {4, 8, 10, 9, 6, 0, 7, 1, 2, 5, 3}, {5, 10, 4, 0, 1, 2, 9, 6, 3, 8, 7}}
{{6, 11, 4, 5, 3, 1, 8, 2, 9, 7, 0, 10}, {1, 4, 8, 9, 10, 11, 5, 3, 7, 6, 2, 0}, {7, 9, 10, 1, 11, 3, 2, 8, 6, 0, 4, 5}, {4, 2, 5, 0, 6, 7, 9, 11, 1, 10, 8, 3}, {10, 8, 7, 6, 5, 0, 4, 1, 3, 11, 9, 2}, {9, 3, 6, 8, 7, 10, 1, 0, 5, 2, 11, 4}, {8, 0, 9, 11, 1, 4, 7, 10, 2, 3, 5, 6}, {3, 6, 0, 10, 2, 9, 11, 5, 4, 8, 1, 7}, {2, 5, 11, 7, 8, 6, 10, 9, 0, 4, 3, 1}, {11, 7, 1, 2, 0, 8, 3, 4, 10, 5, 6, 9}}

Please either clarify what the ambiguity is that remains or remove the hold on my question. I believe I have corrected everything you asked, and aside from that I don't believe it violates the rules in any way.

Can you give an example with n=9, m=7? (If you can then there's a further ambiguity, which is what the distribution of the random cycles should be: I presume it's selecting a random set of valid derangements such that each set is selected with equal probability assuming a perfect random number generator, but that's not entirely clear; however, the task being actually possible is a much bigger problem).

An answer for n=9, m=7 is {{5, 3, 4, 2, 0, 7, 8, 6, 1}, {2, 0, 8, 6, 5, 3, 1, 4, 7}, {1, 4, 6, 7, 8, 2, 3, 0, 5}, {8, 6, 0, 4, 7, 1, 2, 5, 3}, {3, 7, 5, 1, 2, 0, 4, 8, 6}, {4, 5, 7, 8, 3, 6, 0, 1, 2}, {6, 8, 3, 5, 1, 4, 7, 2, 0}}

I cleared up ambiguity and stated that all the different ways of doing it with m cycles of length n should have the same probability of occurring

If you'd like I could share all the code I've produced so far working on this problem.

"The fastest algorithm (in time complexity) wins." There's two parameters here, m and n, so it's not clear how to compare tradeoffs between these. If you mean for m to be linear in n, that would resolve it.

The worst case time complexity will always be when m=n-2 (since that's the maximum value m can take on for the challenge). Different algorithms will be compared for that case.

If n is an odd number than m can be n-1 but that isn't covered in the challenge

http://chat.stackexchange.com/rooms/52408/cyclic-mutual-derangements

Is it fine to use built-in combinatorial functions?

Python 3, \$O((n - 1)!^{m - 1}nm)\$ expected time
This is a reference answer using a very straightforward and slow rejection sampling algorithm, for the sake of having at least one valid answer. It picks \$m\$ random cycles, checks whether they form a valid solution, and repeats from scratch until they do.
Since there exists at least one valid solution, there must exist at least \$(n - 1)!\$ valid solutions (by relabeling it), so the probability that \$m\$ random cycles happen to be a valid solution is at least \$\frac{(n - 1)!}{(n - 1)!^m}\$. So we expect at most \$(n - 1)^{m-1}\$ iterations of the loop, with each iteration taking \$O(nm)\$ time. (This is a pessimistic analysis that could be improved with a better lower bound on the number of solutions.)
import random

def f(n, m):
    while True:
        cycles = []
        for i in range(m):
            order = list(range(1, n))
            random.shuffle(order)
            cycle = [None] * n
            for a, b in zip([0] + order, order + [0]):
                cycle[a] = b
            cycles.append(cycle)

        if all(len({cycle[j] for cycle in cycles}) == m for j in range(n)):
            return cycles

Try it online!

Python3, ~O(n!):
import collections, copy, random
def cycles(n):
   q, q1 = collections.deque([([], [0 for _ in range(n)], 0, {}, {*range(n)}, collections.defaultdict(set))]), collections.deque()
   while q:
     result, a, s, d, ac, cache = q.popleft()
     if not ac:
        yield a, cache
        continue
     for i, x in enumerate(a):
       if (s or i) and (i not in d and s not in cache[i]):
          l, _cache = copy.deepcopy(a), copy.deepcopy(cache)
          _d = copy.deepcopy(d)
          l[i] = s
          _d[i] = s
          _cache[i].add(s)
          q.append((result, l, i, _d, ac - {s}, _cache))

def main(n, m):
   cycle, result, cache, seen = [*cycles(n)], [], {}, []
   while 1:
     if len(result) == m and result not in seen:
        yield result
        result, cache, seen = [], {}, seen + [result]
        continue
     c, _cache = random.choice(cycle)
     if all(not cache.get(j, set())&_cache[j] for j in _cache):
        result.append(c)
        cache = {j:cache.get(j, set())|_cache[j] for j in _cache}

Try it online!

This doesn’t work. next(main(5, 3)) hangs forever about 1 in 6 times. (Convenient that your TIO link only tests 5 times!) I think that’s due to a bug, but even with the bug fixed, a strategy like this can’t possibly work. For example, with n = 6, m = 4, there is no way to extend [1, 2, 3, 4, 5, 0], [2, 3, 5, 0, 1, 4], [3, 4, 1, 5, 0, 2] with a fourth cycle.

No. There do exist solutions for n = 6, m = 4—an example is listed in the challenge—and the challenge requires you to find them all with equal probability. You just can’t use your row-by-row strategy, since you might start with those dead-end rows. This is marked “difficulty level: hard” for a reason.

@AndersKaseorg I was under the impression that only one block of m cycles had to be produced for the solution to be valid (based on "Example outputs"), hence the use of a generator + next. Anyway, I will look deeper into this later.

I’m skeptical that this strategy or anything similar can satisfy the challenge’s requirement that “All possible sets of m cycles of length n that fit the criteria should have equal probability of occurring”; do you have any reason to believe that it does? Also, your $O(mn)$ claim is not even remotely plausible, given that you have at least three nested loops with lots of restart conditions, and you generate less than half an output per second at n = 6, m = 4.

Now this doesn’t have any randomness at all. The challenge asks for a single random block of m cycles, where all valid outputs occur with equal probability. And I don’t know what you’re measuring with $O(n^3)$, but it’s definitely wrong.

@AndersKaseorg Added a bit of explanation to a randomized version of my previous solution, although even Python's random module is pseudo-random, so who knows. I suppose it would be valid to simply produce all possible m cycles, and then choose one randomly, but I think that goes against the spirit of the question.

You still aren’t outputting a single random block of m cycles. There is no reason for main to be a generator; the challenge just asks you to output one random block of m cycles. (If the challenge asked for a uniformly random die roll, a solution would be def main(): return random.randrange(1, 7)—nothing else.) Putting that aside, your generator can still get stuck on the same dead-end rows I described earlier, and when it doesn’t get stuck, it still doesn’t satisfy the equal probability requirement. And it takes at least $O(n!)$ time to generate your cycle pool.

@AndersKaseorg Thanks for the clarification on O(n!), will take a look at the possibility of dead-end rows later.

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


text:
Negative Space Graphs
Task
You will be given a positive integer and you must output a "self-complementary graph" with that many nodes.  If you don't know what a self-complementary graph is the wikipedia article wont help you much so below are two explanations, a technical and a non-technical one.
Non-Technical
A graph is a set of nodes that are connected by lines.  Each pair of points can be connected by one line or none.  The "complement" of a graph is the result of taking a graph and connecting all the nodes that are not connected and disconnecting all the nodes that are.
A self-complementary graph is a graph whose complement can be rearranged into the shape of the original.  Below is an example of a self-complementary graph and a demonstration of how.
Here is a graph with 5 nodes:

We will highlight the all the places where connections could go with red dotted lines:

Now we will find the complement of the graph by swapping the red and black edges:

This does not look like the original graph but if we move the nodes around like so (each step swaps two nodes):

We get the original graph!  The graph and its complement are the same graph
Technical
A self-complementary graph is a graph that is isomorphic to its complement.
Specifications
You will receive an positive integer via whatever method suits you best.  And you will output a graph in whatever method you deem appropriate,  this includes but is not limited to Adjacency Matrix Form, Adjacency List Form, and of course pictures!  The outputted graph must be its own complement and have as many nodes as the integer input.  If no such graph exists you must output a falsy value.
This is code-golf and you should aim to minimize your byte count.
Test Cases
Below are pictures of possible outputs for several n
4

5

9

Do we have to handle negative inputs?

@xnor No.  I will fix the question to be congruent

What should be the output for 1? I believe the empty graph on 1 vertex is technically self-complementary.

@xnor All order-1 and order-0 graphs are self complementary.

Is the following a legitimate output format: a list of pairs of integers between 1 and the input, where each pair represents an edge connecting the corresponding vertices? For example, {{1,2},{2,3},{3,4}} if the input is 4? (And if so, also checking that the empty list {}, which is not falsy for me, suffices if the input is 0 or 1.)

@GregMartin If you deem that method appropriate it is.  I really care very little about how things are outputted and want the challenge to be about manipulating graphs.  {} should suffice for 0 and 1.

Before anyone gets the idea of basing an answer on GraphData@{"SelfComplementary",{#,1}}&, I believe that simply loads some examples for low n from Wolfram's database, so this won't work for arbitrarily large inputs.

There is an error in the graph for 8. Each vertex should have an average of 7/2=3.5 edges, but instead has only an average of 2.5 vertices. A solution is to draw in 4 edges forming a square. See my answer

@LevelRiverSt Ah I seem to have commented those out in my code.  Good catch, I will fix when I have the time.

Haskell, 72 bytes
f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+b+sum[b|odd n,a<2])4<2]

Try it online!
A belated improvement inspired by ideas from kops. Takes vertex 1 to the the special vertex in the \$n=1 \bmod 4\$ case, rather than vertex n.

Haskell, 77 bytes
f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

Try it online!
This uses an easy-to-compute explicit criterion to decide whether an edge (a,b) belongs in the graph. Instantiates this algorithm, with the permutation cycling among the values modulo 4
4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

We include edges whose two endpoint vertices add to 0 or 1 modulo 4. Note that cycling vertices as per this permutation adds 2 modulo 4 to the vertex sum on each each, and so swaps edges and non-edges. This gives a permutation of vertices that complements the edges.
If the graph has an extra node beyond a multiple of 4, it is put in a cycle alone. We include edges with it when then other vertex is even. Permuting the vertices flips the parity, and so the graph remains self-complementary.
If the number of vertices isn't 0 or 1 modulo 4, no self-complementary graph is possible because there's an odd number of edges in the complete graph
Overall, here are the conditions:

If the input n isn't 0 or 1 modulo 4, output an empty list
Otherwise if n is even, include all edges (a,b) with a<b and a+b equal to 0 or 1 modulo 4.
Otherwise if n is odd, do the same, but instead include edges of the form (a,n) when a is even.

The code combines the second and third cases by replacing the condition mod(a+b)4<2 with mod(a+a)4<2 when both odd n and b==n.

Brachylog 2, 24 bytes
{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

Try it online!
This is a function that returns a pair consisting of two adjacency lists: one for the graph, one for the complement graph. (In the Brachylog interpreter on TIO, you can ask it to evaluate a function, rather than a full program, via giving Z as a command line argument.) For example, the output for input 5 is:
[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Here's what that looks like as an image (showing the two graphs):

As is common in Prolog-based languages, the function supports more than one call pattern. Notably, if you try to use it as a generator, it will output all possible self-complementary graphs with the given number of vertices (although I didn't take any effort to make this case usable, and notably it'll output each of the graphs many times each).
Explanation
This is basically just a description of the problem, leaving the Prolog implementation to find the best method of solving it. (However, I doubt it will use an algorithm any better than brute force in this particular case, so it's likely fairly inefficient, and testing seems to confirm this, showing the performance getting much worse the larger the graph is.)
{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

Incidentally, I ended up having to spend a whole 6 bytes (¼ of the program, the characters (∨?<2)) dealing with the special cases of 0 and 1. Frustrating, but that's the nature of special cases.
The \\ᵐcdl? section is a little hard to understand, so here's a worked example. Its purpose is to check whether something is a graph and its complement, with corresponding edges in the graph and complement being in the same order within the lists. The graph/complement pair becomes the eventual output of the program. Here's an example case:
[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Transposing this gives us a list of pairs of corresponding edges between the graph and the complement:
[[[1,2],[2,5]],[[1,3],[2,3]],[[1,5],[2,4]],[[3,5],[3,4]],[[4,5],[1,4]]

Next, we transpose inside the list elements and flatten one level; that gives us a list of pairs of corresponding elements between the graph and the complement:
[[1,2],[2,5],[1,2],[3,3],[1,2],[5,4],[3,3],[5,4],[4,1],[5,4]]

Clearly, what we want here is for there to be no more than 1 pair starting from each element (thus proving that the elements of the graph and the complement are in 1-to-1 correspondence). We can almost verify that just by stating that the list has at exactly ? distinct elements (i.e. a number of distinct elements equal to the number of vertices). In this case, the test succeeds; the distinct elements are:
[[1,2],[2,5],[3,3],[5,4],[4,1]]

However, this leaves room for a potential problem; if a vertex is entirely disconnected in the original graph, its correspondence won't be mentioned, leaving room for a duplicate correspondence from some other vertex. If this is the case, the complement graph must have an edge between that vertex (without loss of generality, let's say it's 1), and every other vertex, and so the list of correspondences will contain [1,2], [1,3], …, [1, ?]. When ? is large, this will lead to more correspondences total than we'd have otherwise, so there's no problem. The only issue happens when ? is 3 or lower, in which case we only end up adding one extra correspondence (whilst removing one from 1 not appearing in the input); however, this is not a problem in practice, because there are 3 possible edges on a 3-element graph, which is an odd number (likewise, 1 possible edge on a 2-element graph is also an odd number), and thus the test will fail at the \ step (you can't transpose a ragged list, i.e. ones whose elements have different lengths).

The difference between z and \ is that z is cyclic zip, meaning that [[1,2,3],["a"]] will end up being [[1,"a"],[2,"a"],[3,"a"]] with z, whereas it will fail for \. \ right now only works on square matrices; future implementation will make it work like z, except not cyclically.

I'd actually figured the difference out myself, but only after I wrote the explanation. This particular solution depends on \ only working on rectangles (although it only takes 2 more bytes if you can't take advantage of that step).

BBC BASIC, 161 bytes
Tokenised filesize 140 bytes
Download interpreter at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html
I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

Ungolfed code
  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

Explanation
This uses the same algorithm as Xnor, but produces a diagrammatic output.
Where n is of the form 4x+2 or 4x+3 there is no solution as the number of edges is odd.
Where n is of the form 4x we arrange all the vertices in a circle and draw those edges where (a+b) mod 4is 2 or 3 (not 0 or 1 as in Xnor's case, for golfing reasons. This is therefore the complement of the solution given by Xnor.)
To see this in a more pictoral sense, we take every second vertex and draw the edges to the vertices 1 and 2 places away in anticlockwise direction. This defines n parallel directions, half of the total. Then we add in all the other edges parallel to these.
The complement can be found by adding 1 to both a and b in each edge specification, or pictorally by rotating the diagram by a 1/n turn.
Where n is of the form 4x+1 we add another vertex, which is linked to every second vertex of the 4x graph. If it was placed at the centre the symmetry of the diagram would be preserved, but I chose to place it outside the main circle of points for clarity.
Output
The following are the first few cases for 4x+1. the 4x cases can be seen by deleting the vertex at bottom right and its associated edges.

Haskell, 75 bytes
f n=[(a,b)|b<-[1..n],a<-[1..b-1],n#0,a#sum(b:[a|n#3,n==b])]
x#y=mod(x+y)4<2

Try it online!
This is a direct golf of @xnor's solution posted as a separate answer for the bounty
There are two 1 byte saves here, one by replacing last with sum since in the case where we are checking whether a is even via 2*a mod 4 < 2, b happens to be known to be 1 mod 4 so adding it as well (producing 2*a+b) is harmless.
The second is by creating the hammer of x#y=mod(x+y)4<2 and aggressively finding a bunch of nails to hit with it, which just barely comes out to 1 byte shorter.

Congrats! I've posted the bounty.

JavaScript (ES6), 191 bytes
f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

This function returns an adjacency list. It uses two algorithms, and differentiates between empty complementary graphs and non-outputs by returning 0 instead of [] when none exists. The first algorithm is based on Rado Graphs constructed using the BIT predicate, and creates valid 0-, 1-, 4- and 5-order complementary graphs. The other algorithm, found by our friends at mathematics, constructs a valid V+4 vertex complementary graph by applying a 4-path addition to a valid V vertex complementary graph.
It begins by validating the input to confirm the existence of a valid complementary graph (using n*~-n/4%1), and if that fails, returns 0. It then checks if n>5 and recurses to the n-4 case to construct a valid lower order solution, then applies the 4-addition to the returned adjacency list on the way back up the recursion chain. Lastly, if n>5 is not true, it iterates from 0 to n-1 for x and y, and checks if the (y>>x)&1 is true. If so, then those nodes are paired.
Here is a more readable format of the function, with ternary operators expanded to if-else statements and eval()s inlined:
// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

Demo

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a
<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))">