text:
Create and write to a file
Challenge
Create a new file and write the string Hello World to it.
Restrictions

Your challenge must write to a file on disk, in the file system.
The file may not be a log file generated during normal operation of the interpreter.
The file must contain only the string Hello World. It is allowed to contain a trailing newline or minimal whitespace. No other content.
No command-line flags/pipes (etc) allowed, except when necessary to run the program. (e.g. perl -p)

Notes

This is code-golf, so shortest program in bytes wins.
Follow the spirit, not the letter, of the rules.

Is trailing newline okay?

@Winny yes, it is ok

Is a filename part of the contents of a file?

Could I also write to a magnetic tape, or must it be a disk? If so, are you including 3.5" and 5.25" disks? Or do you mean a "hard disk" or solid state disk?

@ShaunBebbers Those are acceptable too

Pyth, 14 bytes
.w"Hello World

Outputs to a file called o.txt.

Python 2, 32 bytes
print>>open(*"ww"),"Hello World"

Yes, this is valid python.

Woah. Explanation?

@DrGreenEggsandIronMan it looks like the main trick is how * can split an iterable into individual arguments in a function, so open(*"ww") becomes open("w","w").

@ValueInk Actually the main trick is the use of the extended print statement which is rarely seen in the wild.

That is indeed a cool trick, but if it weren't for your *"ww" trick you'd've tied with the other Python answer here, which uses open(...).write(...) instead for the same byte count

Oops, I didn't even realise that.

Haskell, 25 bytes
writeFile"o""Hello World"

zsh, 17 bytes
<<<Hello\ World>x

Outputs to a file called x.

Can you interpreted the > as a pipe?

What about >Hello\ World

Vyxal 2.5.3, 32 bytes
kh→@|;@+open(*"ww").write(VAR_)#

Vyxal can't really do anything with external files, which would normally render this challenge impossible. However, in Vyxal 2.5.3 and prior, there was an ACE exploit allowing for arbitrary Python execution. Yep, I found another one.

The ACE:
Vyxal is a transpiled language, so every Vyxal command is translated to some Python code, and then all of the translated commands are executed. Previously, I found that you could escape a string to insert any Python commands you wanted into the transpiled code. It turns out that you can do something similar with function names.
When defining a function in Vyxal, the resulting python looks something like this:
def FN_func(parameter_stack, arity=None):
    ...setup stuff...
    ...commands...
    ...finishing stuff...
    return stack

When calling a function in Vyxal, the resulting Python code looks something like this:
stack += FN_func(stack)

The thing is, when parsing the name of a function, the strategy was to just read characters until reaching a :, |, or ;, which are the delimiters of different parts of the function declaration/call. This meant that you could put any characters you wanted into the name, and it would attempt to transpile it the same way.
In this case, I used a + in the function name when I called it. That results in this transpiled code:
stack += FN_+open(*"ww").write(VAR_)#(stack)

This code will error when ran, because it tries to add together a function and the None that is returned from the open command. However, even though it errors, the open command still runs, meaning that we have executed arbitrary Python. If you wanted to write longer sections of Python code, you could replace the + with ([]) and add a newline after it.

The program:
In this program, the payload (the arbitrary Python code) is the following:
open(*"ww").write(VAR_)

The basis of this code is the open().write() command, which creates a file named w if it doesn't exist, then writes the contents of VAR_ to it.
The VAR_ variable is set at the beginning of the Vyxal program with kh→. This pushes the builtin Hello World and saves it to the nameless variable. All variable names are prepended with VAR_ internally, so the variable VAR_ is created and contains Hello World, which is written to the newly created file. Even though this has the overhead of the ACE setup, it ends up being shorter than the Python solutions due to the builtin.
This ACE has not been fixed in the repo, but it had a patch applied server-side for the online interpreter. It was also fixed in the rewrite and subsequent 2.6 release. If you want to try out this program for yourself, you can download the 2.5.3 version here.

Vim, 15 + 2 == 17 bytes
iHello World<esc>ZZ

+2 bytes for launching this with vim f instead of vim. Additionally, this version works to:
iHello World<C-o>ZZ

If launching vim like this is not allowed, there is also:
Vim, 18 bytes
iHello World<esc>:w f<cr>

Side note: this is a polyglot. The same thing works in V, except that it is one byte shorter (since the <cr> at the end is implicit.)

What's the  f<cr> at the end for?

@Zwei 'f' is the name of the file, and the <cr> (which is a mnemonic for "enter", a single byte) is necessary to run the command. Commands that start with a colon are like a mini shell inside of vim, and the command :w is the command for writing to a file.

Should <esc> not be counted as 5 bytes and <cr> as 4, since they have to be fully typed in?

@BartvanNierop No, <esc> is just notation for "The escape key", which is 0x1B, and <cr> is notation for "The Carriage Return key" which is 0x0B

That's if you actually start vim and type it. As far as I'm aware, when you're writing the source code in vimscript, you have to type them out.

Well first off, there is a precedent to score vim with keystrokes == bytes, but second off, there are several ways to write this in vim "code" without using the vim-key notation. For example, if you use <C-v> to insert a literal escape character and a literal carriage return, then you can assign all of these strokes to a macro, and run it that way. You could also do it in vimscript with normal 'iHello World^[:w f^M which is how vim displays it, not how you enter it. ^[ and ^M are both one byte.

And so I learn something new (about vim) every day. =] Thanks for the thorough explanation.

Ruby, 26 bytes
Writes to file f.
open(?f,?w)<<"Hello World"

Batch, 19 bytes
@echo Hello World>o

Not sure if it counts as wrong, but it outputs "Hello World" and a newline to the file, rather than simply "Hello World"

What is the '@' good for?

@PEAR It prevents the command from being echoed to STDOUT.

@brianush1 It doesn't count as wrong, apparently.

Batch, 18 bytes
echo Hello World>f

I think you need an @, or re-title this as (console).

The @ is not necessary.

Try saving it in a batch file and run it as such (not directly type the command). You will then see that you need the @, because the command is otherwise printed too. That means you have two options: 1) Delete this answer because it will be a dupe 2) Relabel as (console).

PowerShell, 15 bytes
"Hello World">o

> redirects the string to a file called o in the current directory.

Node.js, 42 bytes
require("fs").writeFile('o','Hello World')

i don't think this needs explanation
Node.js REPL, 31 bytes
fs.writeFile('o','Hello World')

for some reason in repl you dont need to include fs

I don't think this works. In order for it to work, you'd need require("fs").writeFile("o","Hello World"). Otherwise, fs is not included.

@CᴏɴᴏʀO'Bʀɪᴇɴ huh ok. works in REPL for some reason

I beat you with 1 byte :P

C, 44 bytes
main(){fputs("Hello World",fopen("o","w"));}

This will segfault on some systems without #include <stdio.h>

@StevenPenny As long as there's a system/compiler where it's guaranteed not to segfault, that's fine. Answers generally don't have to be portable.

@StevenPenny And now it has.

Dyalog APL, 19 bytes
⎕NPUT⍨'Hello World'

Creates a file with the name and contents "Hello World".

Bash, 18 bytes
echo Hello World>a

K, 20 Bytes
    `:f 0:,"Hello World"
    `:f

Confirmation;
    mmm@chromozorz:~/q$ cat f.txt
    Hello World

Since nobody said it yet, welcome to Programming Puzzles & Code Golf.

Much appreciated!

OK. I also think that you have extra leading spaces though. I will edit the spaces out if you want (I don't know if they are intentionally placed, but I think it was unintentional.)

R, 38 36 35 bytes
sink(" ");cat("Hello World");sink()

I like how the created file has no name ! It's just .txt anything, in fact !
-2 bytes thanks to @PEAR remark !
-1 bytes thanks to @BartvanNierop !
This code will produce a file with no name.

Is the '.txt' really necessary? File endings are just for the user. A single character might me enough.

I don't know R, but could you not shave off another byte, as by @PEAR's suggestion, by simply naming the file "a"?

C#, 93 77 76 bytes
using System.IO;namespace N{class C{static void M(){File.WriteAllText("f", "Hello World");}}}
class C{static void Main(){System.IO.File.WriteAllText("f", "Hello World");}}
class C{static void Main(){System.IO.File.WriteAllText("f","Hello World");}}

See it work, with an exception for unauthorized file access.
Changelog
Rev2

Removed unnecessary namespace
Changed function name to Main (because otherwise it won't be detected as main function)
Removed using directive (thanks Jean Lourenço)

Rev3

Removed space that sneaked in.

C# (without boilerplate), 47 bytes
void M(){File.WriteAllText("f","Hello World");}

You can save some bytes by removing the using and appending it directly to the method: System.IO.File.WriteAllText[...]

@JeanLourenço Thanks. I had that originally and then changed it for reasons unknown.

Clojure, 23 bytes
#(spit"x""Hello World")

Anonymous function which creates file called x and writes Hello World there.

ed, 19 characters
i
Hello World
.
w o

Sample run:
bash-4.3$ ed <<< $'i\nHello World\n.\nw o'
12

bash-4.3$ cat o
Hello World

MATL, 15 bytes
'Hello World'Z#

This creates a file called inout and writes the string to it.

C#, 118 112 98 bytes

Golfed
void M(){var f=new FileInfo("_");var s=f.CreateText();s.Write("Hello World");s.Flush();s.Close();}

Ungolfed
public void M() {
    var f = new FileInfo( "_" );
    var s = f.CreateText();

    s.Write( "Hello World" );
    s.Flush();
    s.Close();
}

Full explicit code
using System.IO;

namespace N {
    class C {
        public void M() {
            // A file name is required
            FileInfo f = new FileInfo( "_" );

            // Obtain the Stream to later write on it
            StreamWriter s = f.CreateText();

            // Write 'Hello World' to the Stream
            s.Write( "Hello World" );

            // Flush it to the file
            s.Flush();

            // Close the Stream, for security and integrity reasons.
            s.Close();
        }
    }
}

Releases

v1.2 - -14 bytes - Changed to vars. Shoutout to Jean Lourenço.
v1.1 -  -6 bytes - Simplified names.
v1.0 - 118 bytes - Initial solution.

I'll leave a version down below that only uses the Console to write on th file. Just because I can.

C# Console Version, 39 bytes

Golfed
void M(){Console.Write("Hello World");}

Ungolfed
public void M() {
    Console.Write("Hello World");
}

Full code
using System;

namespace N {
    class C {
        public void M() {
            // Write 'Hello World' to the output handler
            Console.Write("Hello World");
        }
    }
}

Usage
<Exe. file name>.exe > FileToOutput.txt

Releases

v1.0 - 39 bytes - Initial solution.

You can use 'var' instead of FileInfo and StreamWriter to save some bytes

Right! Completely forgot the vars thing... Thanks @JeanLourenço

Nim, 28 26 bytes
"o".writeFile"Hello World"

Yes, Nim has a function in the system module for opening a file, writing a string to it, then closing it again.

Julia, 47 bytes
f=open("o","w");write(f,"Hello World");close(f)

I tried using writedlm, but it didn't work out.

C, 37 bytes
main(){system("echo Hello World>o");}

Perl 6,  27  23 bytes
'o'.IO.spurt: 'Hello World'
spurt 'o','Hello World'

eacal, 26 bytes
write a string Hello World

This writes a string Hello World to file a, creating it if not present. Basically:
write <fileName> <exec>

and
string <params to convert to string>

Run the program as:
λ node eacal.js writeFile

J, 21 bytes
'Hello World'1!:3<'o'

This writes to a file o in the current directory, or, if not called from a file, in your j64-804 file. 1!:3 is the write foreign, and <'o' is the boxed filename (filenames need to be boxed). The LHS is the string to write.

Java
public class H
{
    public static void main(String[] a)
        throws IOException
    {
        FileWriter o = new FileWriter("x");
        o.write("Hello World");
        o.close();
    }
}

Simple I/O with no exception handling.
Corrected
Corrected the original code to write the correct string (Hello World).

Your answer would have been shorter if you had actually wrote the correct string..

@SeanBean: Huh, force of habit, I guess, that I wrote Hello, world. I corrected the code.

@DavidRTribble You can change public class H to class H and IOException to Exception. This will save you 9 bytes. Also, you should include the import java.io.*;

Python, 34 bytes
open("h","w").write("Hello World")

Outputs to a file called h.

APLX, 15 bytes
'Hello World'⍈1

Creates an APL component file containing just one component; the desired string. It can be read back with:
      'Hello World'⍇1
Hello World

Gema, 28 characters
\A=@write{o;Hello World}@end

Sample run:
bash-4.3$ gema '\A=@write{o;Hello World}@end'

bash-4.3$ cat o
Hello World

Java 7, 100 95 bytes
void f()throws Exception{java.io.Writer p=new java.io.PrintWriter("x");p.print("Hello World");}

Or if you want to close the writer after using it (101 bytes):
void f()throws Exception{try(java.io.Writer p=new java.io.PrintWriter("x")){p.print("Hello World");}}

Ungolfed:
class Main{
  static void f() throws Exception{
    try(java.io.Writer p = new java.io.PrintWriter("x")){
      p.print("Hello World");
    }
  }

  public static void main(String[] a){
    try{
      f();
    } catch(Exception ex){
    }
  }
}

Usage:
java -jar Main.jar

Java is my favorite language but jesus christ it's hilarious how bad a golfing language it is haha

@AlanTuning Indeed. xD I work with Java at work, and it's fun to code-golf in Java. You will NEVER be able to win a code-golf challenge here using Java, but it's still fun to write the Java code as short as possible.

well, you can just void f()throws Exception{new java.io.PrintWriter("x").print("Hello World");}

java.io.Writer p=new java.io.PrintWriter saves you some more characters.

@cliffroot Hmm, I tried that initially, but it didn't seem to write anything to disk. Will try again tomorrow, currently I don't have an IDE and file I/O doesn't work in ideone.

@Kevin Cruijssen, it seems like if you do not close the stream the write operation is not guaranteed to take place anyway.

Racket, 43 bytes
(display"Hello World"(open-output-file"f"))

JavaScript, 89 bytes
This code was tested in Chrome.  In other browsers, the element must be in the document for the click method to work.
a=document.createElement("a");a.href="data:text/plain,Hello World";a.download=1;a.click()

HTML, 83 bytes
This code was tested in Chrome.  It relies on the image failing to load, then it clicks itself, triggering the anchor tag which is a download link.

Awk, 29 27 characters
BEGIN{print"Hello World">1}

(No, not another output redirection. Just Awk's syntax is similar.)
Thanks to:

Pedro Maimere for suggesting to use integer for file name (-2 characters)

Sample run:
bash-4.3$ awk 'BEGIN{print"Hello World">1}'

bash-4.3$ cat 1
Hello World

Substituting "o" for a lone number like 1 saves 2 bytes.

Thank you, @PedroMaimere.

Tcl, 28 bytes
puts [open T w] Hello\ World

JavaScript (SpiderMonkey), 48 37 30 29 bytes
open`data:text/t,Hello World`

Try it online!

R, 20 bytes
write("Hello World")

This creates a file named "data" in the current directory and write "Hello World" in it.

Welcome to Code Golf! Nice first answer!

@Fmbalbuena thanks!

Php, 38 bytes
file_put_contents('a', 'Hello World');

You can save 15 bytes by calling the execution operator. \echo Hello\ World > a``

Heh heh that's not really PHP anymore.

36 bytes: fputs(fopen('a','c'),'Hello World');

@AlexHowansky You can do fputs(fopen(a,c),'Hello World'); and save 4 bytes.

PHP, 34 bytes
fputs(fopen(7,'c'),'Hello World');

@Lukabot I reverted your edit because it should have been a comment, and it is completely different enough to be its own answer (the same language can be used multiple times if the approach is different)

Mathematica, 27 bytes
".txt"~Export~"Hello World"

Like in the answer using R... isn't a single character enough for the file name?

@PEAR Mathematica can't infer the file format without a file extension.

Oh, ok... maybe something shorter encoded in the same way?... .c for example?

Perl, 20 bytes
`echo Hello World>o`

Perl will execute anything in backticks (`) as a system command.

ListSharp, 37 bytes
OUTP="Hello World" HERE[<here>+"\\a"]

simply writes Hello World to a file called "a"(not even a text file) in the script execution environment,

PHP, 27 bytes
exec('echo Hello World>o');

PHP, 20 bytes
`echo Hello World>o`

Bash script, 20 18 bytes
echo Hello World>o

Save this as a file write.sh and run it: `bash o.sh

Why did you repost a deleted answer?

Surely the quotes are unnecessary?

You can save a byte by escaping the space instead of using quotes: Hello\ World

@MTCoster, why? help echo says: “Display the ARGs, separated by a single space character and followed by a newline, on the standard output.”

@manatwork You're absolutely right, I was unaware of this!

@Dennis It was downvoted due to rules being written incorrectly. The rules are now fixed and I wanted to repost that answer without the downvotes.

That's not a good reason. After the rules have been clarified, people can just retract their downvotes. Duplicate answers are automatically flagged for moderator attention. Also, your edit makes your answer identical to this one.

AutoIT, 43 40 bytes
FileWrite(FileOpen("a",1),"Hello World")

Explanation
FileOpen takes two parameters and returns the handle of the file. Mode must be 1 for writing (appending) text.

FileOpen ( "filename" [, mode = 0] )

FileWrite takes two parameters, a handle and the text to write

FileWrite ( "filehandle/filename", "text/data" )

If a file does not exist, AutoIT will create it. Note that in my example it will not have any file extension associated (filename: a), but can still be opened with any text editor.
AutoIT is a Windows only scripting language.
Script-Example.com has an online AutoIT compiler that can verify the solution.

C#, 50 bytes
s=>System.IO.File.WriteAllText("f","Hello World");

An anonymous function that takes in an unused argument and outputs the file.
Alternatively and cheating slightly this one:
s=>System.IO.File.WriteAllText("f",s);

That takes in a string and works assuming the string contains the text: Hello World, for 38 bytes.

Common Lisp, 69 bytes
Lauded for being incredibly expressive, it's not the best golfing language...
(with-open-file (f "f" :direction :output) (format f "Hello, world"))

See it work, with permission denied.

Groovy, 28 characters
new File("o")<<"Hello World"

Sample run:
bash-4.3$ groovy -e 'new File("o")<<"Hello World"'

bash-4.3$ cat o
Hello World

Sed, 20 characters
(19 characters code + 1 character dummy input.)
s/^/Hello World/
wo

Seems the side effect of also displaying the string to STDOUT after the file was created is not prohibited.
Requires dummy input to work as per Are languages like sed exempt from “no input” rules?
Sample run:
bash-4.3$ sed $'s/^/Hello World/;wo' <<< ''
Hello World

bash-4.3$ cat o
Hello World

QBasic, 39 bytes
OPEN"f"FOR OUTPUT AS#1
?#1,"Hello World

Opens a file named f (creating it if it doesn't exist, wiping it if it does) and gives it the file handle #1. Then prints (?) to file #1 the string Hello World (with a trailing newline).

Jelly, 25 bytes
“ṠȷŀƤoĊịSAĊhJİⱮa¤XPṢḞɦ»ŒV

Try it online!
Executes the Python code open(*'aw').write('Hello World').

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


text:
Integer goes back and forth through time
Input:
An integer.
Output:

First convert the integer to it's equivalent Roman Numeral.
Then convert each capital letter of that Roman Numeral to their ASCII/UNICODE decimal value.
And output the sum of those.

Example:
1991 -> MCMXCI -> 77+67+77+88+67+73 -> 449
^ input                                ^ output

Roman Numerals:

Here is a perhaps useful Roman Numeral Converter.
Challenge rules:

Standard Roman Numeral rules are applied, so no alternative forms like IIII or VIIII instead of IV and IX.*
The Macron lines above the Roman Numerals past 1,000 are ¯ (UNICODE nr. 175). So one line counts as +175 and two as +350.
You are allowed to use any kind of input and output type, as long as it represents the integers.
The test cases will be in the range of 1 - 2,147,483,647.

* Roman Numeral rules (quote from Wikipedia):

Numbers are formed by combining symbols and adding the values, so II is two (two ones) and XIII is thirteen (a ten and three ones). Because each numeral has a fixed value rather than representing multiples of ten, one hundred and so on, according to position, there is no need for "place keeping" zeros, as in numbers like 207 or 1066; those numbers are written as CCVII (two hundreds, a five and two ones) and MLXVI (a thousand, a fifty, a ten, a five and a one).
Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX), subtractive notation is often used as follows:

I placed before V or X indicates one less, so four is IV (one less than five) and nine is IX (one less than ten)
X placed before L or C indicates ten less, so forty is XL (ten less than fifty) and ninety is XC (ten less than a hundred)
C placed before D or M indicates a hundred less, so four hundred is CD (a hundred less than five hundred) and nine hundred is CM (a hundred less than a thousand)
  For example, MCMIV is one thousand nine hundred and four, 1904 (M is a thousand, CM is nine hundred and IV is four).

Some examples of the modern use of Roman numerals include:
  1954 as MCMLIV; 1990 as MCMXC; 2014 as MMXIV
SOURCE

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:
100          ->   67
1            ->   73
4            ->   159
22           ->   322
5000         ->   261
2016         ->   401
1000000000   ->   427
1991         ->   449
9999         ->   800
1111111111   ->   2344
2147483647   ->   5362

Related

@martin 9999 -> M(X)CMXCIX -> 77+263+67+77+88+67+73+88 -> 800 and 2147483647 -> ((MMCXLV)MMCDLXXX)MMMDCXLVII -> 427+427+417+438+426+436 + 252+252+242+243+251+263+263+263 + 77+77+77+68+67+88+76+86+73+73 -> 5362. So I've corrected the second, but the 9999 was correct.

9999. Google says either or.

The test case 2222222222 isn't in the given range. Also I agree with 5362.

@Neil Ah oops, you're completely right. I'll change it to something else.

@martin I'm a bit confused about the I with a macron. M is 1000, so what is (I)? In the link you gave for 9999 it seems to also be 1000..

@KevinCruijssen depending on where you look, 9000->IX+ macron - see here

The title kinda sounds like a Stack Overflow C question.

Is the word "fourth" in the title a pun?  If not, it should be "forth".

Mathematica, 181 173 166 151 bytes
Golfed
(q=Select[ToCharacterCode@#,64<#<99&]&/@StringSplit[RomanNumeral[#],"_"];p=PadLeft;l=Length;Total[p[q,4]+p[{350,350*Mod[l@q,2],175,0}[[-l@q;;]],4],2])&

Ungolfed
(
q = Select[
     ToCharacterCode@#,
     64<#<99&
    ]&/@StringSplit[RomanNumeral@#,"_"];
p=PadLeft;
l=Length;
Total[
   p[q,4]+
   p[{350,350*Mod[l@q,2],175,0}[[-l@q;;]],4]
   ,2]
)&

Mathematica's RomanNumeral implementation gives (IX)CMXCIX for 9999, and so the program returns 971 for that number.
As written, a roman numeral of the type ((...))(...)... returns a nested list of the ASCII codes for the roman numerals of length 4, ((...))... returns a list of length 3, (...)... returns a list of length 2, and ... returns a list of length 1.  The final line converts those rules into the appropriate number of macrons for each section of the list, adds those macrons in, and then sums the entire nested list to return the output.

Welcome to PPCG!

@betseg Thank you!  This was a fun first problem.

Python 3, 281 278 273 269 bytes
My first attempt at codegolf, here we go. Tried to do it without looking at the linked question, so it's probably terrible :)
def f(n):d=len(str(n))-1;l=10**d;return 0if n<1else(n<l*4and[73,88,67,77,263,242,252,438,417,427][d]+f(n-l))or(l<=n//9and[161,155,144,340,505,494,690,855,844][d]+f(n-9*l))or(n<l*5and[159,164,135,338,514,485,688,864,835][d]+f(n-4*l))or[86,76,68][d%3]+(d//3*175)+f(n-5*l)

8 bytes smaller, thanks to Gábor Fekete
Ungolfed:
def f(n):
d = len(str(n)) - 1 # number of digits minus one
l = 10 ** d         # largest power of 10 that is not larger than parameter
if n == 0:
    return 0
elif n < 4 * l: # starts with X, C, M, ...
    return [
        ord('I'),
        ord('X'),
        ord('C'),
        ord('M'),
        ord('X') + 175,
        ord('C') + 175,
        ord('M') + 175,
        ord('X') + 350,
        ord('C') + 350,
        ord('M') + 350
    ][d] + f(n - l)
elif n // 9 * 10 >= 10 * l: # starts with IX, XC, ...
    return [
        ord('I') + ord('X'),
        ord('X') + ord('C'),
        ord('C') + ord('M'),
        ord('M') + ord('X') + 175,
        ord('X') + ord('C') + 350,
        ord('C') + ord('M') + 350,
        ord('M') + ord('X') + 525,
        ord('X') + ord('C') + 700,
        ord('C') + ord('M') + 700
    ][d] + f(n - 9*l)
elif n < 5 * l: # starts with IV, XL, CD, ...
    return [
        ord('I') + ord('V'),
        ord('X') + ord('L'),
        ord('C') + ord('D'),
        ord('M') + ord('V') + 175,
        ord('X') + ord('L') + 350,
        ord('C') + ord('D') + 350,
        ord('M') + ord('V') + 525,
        ord('X') + ord('L') + 700,
        ord('C') + ord('D') + 700
    ][d] + f(n - 4 * l)
else: # starts with V, L, D, ...
    return [
        ord('V'),
        ord('L'),
        ord('D'),
        ord('V') + 175,
        ord('L') + 175,
        ord('D') + 175,
        ord('V') + 350,
        ord('L') + 350,
        ord('D') + 350
    ][d] + f(n - 5 * l)

You can golf some bytes by replacing return 0 if n==0 else with return 0if n<1else

Your golfed version has calls to f in it when the function's name is g.

Change n//9*10>=10*l to n//9>=l to save some more.

Fixed function name, I changed it to check if I golfed it correctly and forgot to change it back.

Mathematica, 198 bytes
Tr[Tr@Flatten[ToCharacterCode/@#]+Length@#*Tr@#2&@@#&/@Partition[Join[SplitBy[Select[Characters@#/."\&"->1,MemberQ[Join["A"~CharacterRange~"Z",{1}],#]&],LetterQ]/. 1->175,{{0}}],2]]&@RomanNumeral@#&

Unfortunately, the builtin doesn't help here much, though I'm sure this can be golfed far more.
Note: Evaluates 9999 -> 971 as per here.

Ruby, 188 bytes
An adaptation based on my old Ruby answer for Roman numeral conversion. Try it online!
f=->x,i=0{k=0;(x<t=1e3)?"CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1".gsub(/(\D+)(\d+)/){v=$2.to_i;s=x/v;x%=v;($1*s).bytes.map{|c|k+=c==73&&i>0?77+175*~-i:c+175*i}}:k=f[x/t,i+1]+f[x%t,i];k}

Batch, 373 bytes
@echo off
set/an=%1,t=0,p=1
call:l 73 159 86 161
call:l 88 164 76 155
call:l 67 135 68 144
call:l 77 338 261 340
call:l 263 514 251 505
call:l 242 485 243 494
call:l 252 688 436 690
call:l 438 864 426 855
call:l 417 835 418 844
call:l 427 0 0 0
echo %t%
exit/b
:l
set/ad=n/p%%10,p*=10,c=d+7^>^>4,d-=9*c,t+=%4*c,c=d+3^>^>3,d-=5*c,t+=%3*c+%2*(d^>^>2)+%1*(d^&3)

Works by translating each digit of the number according to a lookup table for the values 1, 4, 5 and 9. Uses M(V), M(X), (M(V)) and (M(X)). If you prefer (IV), (IX), ((IV)) and ((IX)) then use call:l 77 509 261 511 and call:l 252 859 436 861 respectively.

R, 115 bytes
So... I'm posting my solution because I find the question pretty interesting. I did my best with R's capacities to deal with roman numbers without packages :  you can only input numbers between 1 and 3899, as the as.roman's documentation explains.
That's why I cheated a bit by giving range between 1 to 11 14 in the for loop : it's the lenght of as.roman(3899)'s output (MMMDCCCXCIX).
In fact, according to this website, the longest roman number is MMDCCCLXXXVIII (14 characters), which corresponds to 2888.
Furthermore, you can't compute the length of the output of this function.
a=scan();v=0;for(i in 1:14){v=c(v,as.numeric(charToRaw(substring(as.character(as.roman(a)),1:14,1:14)[i])))};sum(v)

If anyone sees a solution to deal with the above problems, please feel free to comment.

I don't understand why it thinks 3900 is ambiguous -- isn't that just MMMCM? I can get why it didn't do 4000 and up, though, since overline isn't the only convention for large numbers.

05AB1E, 31 bytes
RƵêS£í.XÇεNĀi73¬Ć:Ny73Q-Ƶм*+]˜O

Try it online or verify all test cases.
Explanation:
05AB1E does have a builtin to convert from/to Roman numbers. Unfortunately, \$M=1000\$ is the highest supported Roman digit, so it would convert something like 9999 to MMMMMMMMMCMXCIX. Because of this we'll split the input into parts at the 1000 separators, and convert each part separately. This results in the following code:
R                       # Reverse the (implicit) input-integer
 Ƶê                     # Push compressed integer 334
   S                    # Convert it to a list of digits: [3,3,4]
    £                   # Split the reversed input into parts of that size
     í                  # Reverse each individual part back
      .X                # Convert it from an integer to a Roman number string
        Ç               # Convert each string to a list of codepoint integer
         ε              # Map over each list of codepoints:
          NĀi           #  If the (0-based) map-index is NOT 0:
             73         #   Push 73
               ¬        #   Push its first digit (without popping): 7
                Ć       #   Append its own head: 77
                 :      #   Replace all 73 with 77 (replaces all "I" with "M")
              y         #   Push the list of codepoints again
               73Q      #   Check for each if it's equal to 73 ("I")
             N    -     #   Subtract those checks from the (0-based) map-index
                   Ƶм*  #   Multiply each by the compressed integer 175
                      + #   Add those to the list of codepoints (with 73 as 77)
         ]˜             # After the if-statement and map: flatten the list
           O            # And sum this list of integers
                        # (after which it is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ƶм is 175.

JavaScript (ES6), 183 bytes
f=(n,a=0)=>n<4e3?[256077,230544,128068,102535,25667,23195,12876,10404,2648,2465,1366,1183,329].map((e,i)=>(d=e>>8,c=n/d|0,n-=c*d,r+=c*(e%256+a*-~(i&1))),r=0)|r:f(n/1e3,a+175)+f(n%1e3)

Note: not only prefers (IV) to M(V), but also prefers (VI) to (V)M; in fact it will only use M at the very start of the number.

Python, 263 bytes
def g(m):x=0;r=[73,86,88,76,67,68,77,261,263,251,242,243,252,436,438,426,417,418,427,0,0];return sum([b%5%4*r[i+(i*1)]+((b==9)*(r[i+(i*1)]+r[(i+1)*2]))+((b==4)*(r[i+(i*1)]+r[i+1+(i*1)]))+((b in [5,6,7,8])*r[i+1+(i*1)])for i,b in enumerate(map(int,str(m)[::-1]))])

Welcome to PPCG, nice first answer!

Python 3, 315 bytes
def p(n=int(input()),r=range):return sum([f*g for f,g in zip([abs(((n-4)%5)-1)]+[t for T in zip([((n+10**g)//(10**g*5))%2for g in r(10)],[(n%(10**g*5))//(10**g*4)+max((n%(10**g*5)%(10**g*4)+10**(g-1))//(10**g),0)for g in r(1,10)])for t in T],[73,86,88,76,67,68,77,261,263,251,242,243,252,436,438,426,417,418,427])])

Ungolfed version:
def p(n=int(input()),r=range):
    return sum([f*g for f,g in zip(
        [abs(((n-4)%5)-1)]+
        [t for T in zip(
            [((n+10**g)//(10**g*5))%2for g in r(10)],
            [(n%(10**g*5))//(10**g*4)+max((n%(10**g*5)%(10**g*4)+10**(g-1))//(10**g),0)for g in r(1,10)]
        )for t in T],
        [73,86,88,76,67,68,77,261,263,251,242,243,252,436,438,426,417,418,427])])

Explanation:
This version uses a different approach, it counts occurrences of roman numerals in the number.
[abs(((n-4)%5)-1)] is the number of Is in the roman numeral.
[((n+10**g)//(10**g*5))%2for g in r(10)] is the number of V,L,D,(V),(L),(D),((V)),((L)),((D))s in the number.
[(n%(10**g*5))//(10**g*4)+max((n%(10**g*5)%(10**g*4)+10**(g-1))//(10**g),0)for g in r(1,10)] is the number of the X,C,M,(X),(C),(M),((X)),((C)),((M))s in the number.
It then multiplies the occurrences with the value of the character and returns the sum of it.

I don't know if I understood the challenge correctly but I leave here a first contribution.
First I did a good research on Roman numerals on this site in Spanish and this other very interesting site in English
And then I dedicated myself to preparing the following code:

get_ascii_sum = functools.partial(lambda f, n: sum([ord(c) for c in f(n)]), lambda n: functools.reduce(lambda r, vg: (r[0] + vg[1] * vg[2], r[1] - vg[1] * vg[2]), zip((lambda v, s: (v, [s[i] * ((n + 10 ** i) // (10 ** i * 5)) % 2 for i in range(len(s))], [((n % (10 ** i * 5)) // (10 ** i * 4)) + max(((n % (10 ** i * 5) % (10 ** i * 4)) + 10 ** (i - 1)) // (10 ** i), 0) for i in range(1, len(s))]))(values, symbols)), (0, num)))

Hi, welcome to CGCC! What programming language is your code? Based on the syntax I think it's Python? Could you perhaps add a header to your answer with the programming language, as well as the byte-count, similar as other answers? And if it is indeed Python, you can remove a lot of your spaces to save bytes. :) Tips for golfing in 'all languages' might be interesting to read through. (And if it is indeed Python, there is also a separated tips page for that.)

source: Stack Exchange

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

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

sort: votes


text:
Generate Linus Sequence
Definition
From the description on OEIS A006345:

To find a(n), consider either a 1 or a 2. For each, find the longest repeated suffix, that is, for each of a(n)=1,2, find the longest sequence s with the property that the sequence a(1),...,a(n) ends with ss. Use the digit that results in the shorter such suffix. a(1) = 1.

Worked-out Example
a(1)=1.
If a(2)=1, we will have the sequence 1 1 where the longest doubled substring from the end is 1. If a(2)=2 instead, then it would be the empty substring. Therefore a(2)=2.
When n=6, we choose between 1 2 1 1 2 1 and 1 2 1 1 2 2. In the first choice, 1 2 1 is doubled consecutively from the end. In the second choice, it is 2 instead. Therefore, a(6)=2.
When n=9, we choose between 1 2 1 1 2 2 1 2 1  and 1 2 1 1 2 2 1 2 2. In the first choice, the longest doubled consecutive substring is 2 1, while in the second choice 1 2 2 is doubled consecutively at the end. Therefore a(9)=1.
Task
Given n, return a(n).
Specs

n will be positive.
You can use 0-indexed instead of 1-indexed. In that case, please state so in your answer. Also, in that case, n can be 0 also.

Testcases
The testcases are 1-indexed. However, you can use 0-indexed.
n  a(n)
1  1
2  2
3  1
4  1
5  2
6  2
7  1
8  2
9  1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1

References

WolframMathWorld
Obligatory OEIS A006345

In the test case of n=9, the first choice 1 2 1 1 2 2 1 2 1 has the doubled substring 2 1 at the end.

Note that the linked OEIS page has a golfed Perl solution of ~43 bytes.

Haskell, 146 140 137 133 118 bytes
s!l|take l s==take l(drop l s)=l|1<2=s!(l-1)
g[w,x]|w<x=1|1<2=2
a 1=1
a n=g$(\s x->(x:s)!n)(a<$>[n-1,n-2..1])<$>[1,2]

Do you really need (\x->(\s->...? Otherwise you could write (\x s->....

That helps to save a few

Welcome to PPCG!

Instead of using the sane upper bound div ..., you can use the shorter n. The extra comparisons will all return false and not change the result.

ooh nice, I guess I assumed take would crash if given too large a value

Python, 137 bytes
def a(n,s=[0],r=lambda l:max([0]+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))):
 for _ in[0]*n:s+=[r(s+[0])>r(s+[1])]
 return-~s[n]

This solution is using 0-based indexing.

Jelly, 25 24 22 20 bytes
2 bytes thanks to Dennis.
2;€µḣJf;`€$ṪLµÞḢ
Ç¡Ḣ

Try it online!
A port of my answer in Pyth.
Ç¡Ḣ   Main chain

 ¡    Repeat for (input) times:
Ç         the helper chain
  Ḣ   Then take the first element

2;€µḣJf;`€$ṪLµÞḢ  Helper chain, argument: z

2;€               append z to 1 and 2, creating two possibilities
   µ         µÞ   sort the possibilities by the following:
    ḣJ                generate all prefixes from shortest to longest
       ;`€            append the prefixes to themselves
      f   $           intersect with the original set of prefixes
           Ṫ          take the last prefix in the intersection
            L         find its length
                 Ḣ   take the first (minimum)

Mathematica, 84 bytes
a@n_:=a@n=First@MinimalBy[{1,2},Array[a,n-1]~Append~#/.{___,b___,b___}:>Length@{b}&]

Jelly, 30 29 28 27 24 bytes
;€¬;\€Z;/f;`€$ṪḢ;
1Ç¡o2Ḣ

Try it online! or verify all test cases.

MATL, 34 bytes
vXKi:"2:"K@h'(.+)\1$'XXgn]>QhXK]0)

Try it online! or verify all test cases.
Explanation
v             % Concatenate stack vertically: produces empty array
XK            % Copy to clipboard K. This clipboard holds the current sequence
i:            % Take input n. Generate vector [1 2 ... n]
"             % For each k in [1 2 ... n]
  2:          %   Push [1 2]. These are the possible digits for extending the sequence
  "           %     For each j in [1 2]
    K         %       Push contents of clipboard K (current sequence)
    @         %       Push j (1 or 2)
    h         %       Concatenate horizontally: gives a possible extension of sequence
    '(.+)\1$' %       String to be used as regex pattern: maximal-length repeated suffix
    XX        %       Regex match
    gn        %       Convert to vector and push its length: gives length of match
  ]           %    End. We now have the suffix lengths of the two possible extensions
  >           %    Push 1 if extension with "1" has longer suffix than with "2"; else 0
  Q           %    Add 1: gives 2 if extension with "1" produced a longer suffix, or 1
              %    otherwise. This is the digit to be appended to the sequence
  h           %    Concatenate horizontally
  XK          %    Update clipboard with extended sequence, for the next iteration
]             % End
0)            % Get last entry (1-based modular indexing). Implicitly display

Python 2, 94 bytes
import re
s='1'
exec"s+=`3-int(re.search(r'(.*)(.)\\1$',s).groups()[1])`;"*input()
print s[-1]

Uses 0-based indexing. Test it on Ideone.

Pyth, 46 29 bytes
Took some inspiration from @Leaky Nun's excellent Pyth answer. Tried to see if there was a shorter way using strings. Still 3 bytes short!
huh.melM+kf!x>blTT._bm+dGS2Qk

You can try it out here.

Using reduce instead of explicit for-loop saves you 4 bytes

Pyth, 26 bytes
huh.mleq#.<T/lT2._b+RGS2QY

Test suite.
Explanation
When n = 6, we choose between 1 2 1 1 2 1 and 1 2 1 1 2 2.
We generate these two possibilities, and then look at their suffixes.
For the first one, the suffixes are: 1, 2 1, 1 2 1, 1 1 2 1, 2 1 1 2 1, 1 2 1 1 2 1.
We filter for doubled suffixes by checking if they are the same after rotating them for their length divided by 2 (it turns out that this check is not perfect, because it confirms 1 and 2 also).
We take the last doubled suffix and then take its length.
We then choose the possibility that corresponds to a minimum length generated above.
Then we proceed to the next value of n.
For the purpose of this program, it was golfier to generate the reversed array instead.
huh.mleq#.<T/lT2._b+RGS2QY
 u                      QY   repeat Q (input) times,
                             start with Y (empty array),
                             storing the temporary result in G:
                   +RGS2         prepend 1 and 2 to G,
                                 creating two possibilities
   .m             b              find the one that
                                 makes the following minimal:
                ._                   generate all prefixes
       q#                            filter for prefixes as T
                                     that equals:
         .<T/lT2                         T left-rotated
                                         by its length halved
      e                              take the last one
     l                               generate its length
  h                              take the first minimal one
h                                take the first one from the generated
                                 array and implicitly print it out

Perl, 40 bytes
$a.=/(.*)(.)\1$/^$2for($a)x$_;$_=$a%5+1

The code is 39 bytes long and requires the -p switch (+1 byte).
The loop is inspired by the Perl solution on the relevant OEIS page, although I did come up independently with the regular expression.
Test it on Ideone.

You have outgolfed OEIS, specifically, Ton Hospel/Phil Carmody...

Not really comparable since the OEIS script takes no input and prints the whole sequence.

Retina, 51 42 bytes
9 bytes thanks to Martin Ender.
.+
$*x
+`((.*)(^|2|(?<3>1))\2)x
$1$#3
!`.$

Try it online!
A port of this answer.

JavaScript (ES6), 84
Index base 0
n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

Less golfed
n=>{
  r = d => (s+d).match(/(.*)\1$/)[0].length;
  c = '1';
  for(s = c; n--; s += c)
    c = r(1) > r(2) ? 2 : 1;
  return c;
}

Test

F=
n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

for(n=0;n<20;n++)console.log(n,F(n))

Husk, 20 bytes
!¡λ◄(L←SnmDṫ:⁰)ḣ2);1

Try it online! or Verify first 20 values
Same algorithm as Leaky Nun's answers.

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


text:
Compounding english
A compound word is a word that contains 2 or more words in it.  We can do better than that, though.  We need you to create 1 (nonsensical) word that contains every word.
However, we want this word to be as short as possible.  We can use overlapping letters to achieve this.
For example, if your word list was ["cat", "atom", "a"], you would want to return "catom".
Input/Output
Your program will need to take a list of words as input, and return a compound word as output.
The word list you will be using is the top 10000 words in English, according to Google  (If this list turns out to be too easy, I may change it to a longer one).   For reference, simply appending each word gives you a score of 65888.
Your score is the number of letters in your final word, lower is better.  Tie breaker goes to the first poster.

Related. Related.

Is there any limit as to how long the program can run?

@Loovjo no, but if it ends up that bruteforcing is fast enough to run, then I'll change the word list to make it longer.

@muddyfish correct, edited.

So, for instance, the input list ["hello","ok","kid"] should return hellokid?

I hope we're not expected to put the compounded word directly in our answer...

@R.Kap yes, that string is valid, but any string that contains the three words is valid (e.g. kidokhello )

@PatrickRoberts If it fits in your answer, props to you :)  A pastebin/gist link would be great, but isn't required.

For consistency, you should include the actual length of all the words concatenated together if overlapping letters were not deleted. The length is 65888.

Hmm, who knows a good asymmetric travelling salesman heuristic?

I assume that there is no wrapping? A word cannot start at the end of the compound word and finish at its beginning?

Does the code need to be deterministic (PRNG with consistent seed)?

No wrapping, and yes to deterministic.

Relevant Youtube video: Portmantout

Given the size of the other programs compared to my PowerShell one, kinda wishing that code length was a factor in scoring, especially now that an optimal length word has been found. ;-)

I personally think credit should go to the first one who found the optimal solution, not just somebody who can golf their solution. :)

@NathanMerrill Oh, no doubt. I'm just tooting my own horn for giggles.

Is the optimal solution 28272(Mentioned in bounty) or 38272(In title of accepted answer) chars?

C++, final word length: 38272
(optimised version took about 20 minutes)
#include <iostream>
#include <string>
#include <vector>

std::size_t calcOverlap(const std::string &a, const std::string &b, std::size_t limit, std::size_t minimal) {
    std::size_t la = a.size();
    for(std::size_t p = std::min(std::min(la, b.size()), limit + 1); -- p > minimal; ) {
        if(a.compare(la - p, p, b, 0, p) == 0) {
            return p;
        }
    }
    return 0;
}

int main() {
    std::vector<std::string> words;

    // Load all words from input
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
    }

    std::cerr
        << "Input word count: " << words.size() << std::endl;

    // Remove all fully subsumed words

    for(auto p = words.begin(); p != words.end(); ) {
        bool subsumed = false;
        for(auto i = words.begin(); i != words.end(); ++ i) {
            if(i == p) {
                continue;
            }
            if(i->find(*p) != std::string::npos) {
                subsumed = true;
                break;
            }
        }
        if(subsumed) {
            p = words.erase(p);
        } else {
            ++ p;
        }
    }

    std::cerr
        << "After subsuming checks: " << words.size()
        << std::endl;

    // Sort words longest-to-shortest (not necessary but doesn't hurt. Makes finding maxlen a tiny bit easier)
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t maxlen = words.front().size();

    // Repeatedly combine most-compatible words until there is only one left
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 1) {
        auto bestA = words.begin();
        auto bestB = -- words.end();
        std::size_t bestOverlap = 0;
        for(auto p = ++ words.begin(), e = words.end(); p != e; ++ p) {
            if(p->size() - 1 <= bestOverlap) {
                continue;
            }
            for(auto q = words.begin(); q != p; ++ q) {
                std::size_t overlap = calcOverlap(*p, *q, bestPossible, bestOverlap);
                if(overlap > bestOverlap) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        std::string newStr = std::move(*bestA);
        newStr.append(*bestB, bestOverlap, std::string::npos);

        if(bestA == -- words.end()) {
            words.pop_back();
            *bestB = std::move(words.back());
            words.pop_back();
        } else {
            *bestB = std::move(words.back());
            words.pop_back();
            *bestA = std::move(words.back());
            words.pop_back();
        }

        // Remove any words which are now in the result
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos) {
                std::cerr << "Now subsumes: " << *p << std::endl;
                p = words.erase(p);
            } else {
                ++ p;
            }
        }

        std::cerr
            << "Words remaining: " << (words.size() + 1)
            << " Latest combination: (" << bestOverlap << ") " << newStr
            << std::endl;

        words.push_back(std::move(newStr));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

    std::string result = words.front();

    std::cout
        << result
        << std::endl;
    std::cerr
        << "Word size: " << result.size()
        << std::endl;
    return 0;
}

Verification bash one-liner:
cat commonwords.txt | while read p; do grep "$p" merged.txt >/dev/null || echo "Not found: $p"; done

It also produced some pretty cool in-progress words. Here are some of my favourites:

polyesterday (synthetic nostalgia)
afghanistanbul (something [insert politician you dislike] would say)
togethernet (the friendly internet)
elephantom (a large ghost)
thundergroundwaterproof (as in "I don't know why they felt the need to make it thundergroundwaterproof, but it's making me nervous")

And:

codescribingo (maybe an upcoming challenge on this site?)

The final output is on pastebin here: http://pastebin.com/j3qYb65b

An observation which might be useful to others looking to get the optimal solution: the problem can be reduced to a non-euclidean, asymmetric travelling salesman problem: define a matrix where element i, j = max_word_length - overlap(word[i], word[j]) (where overlap checks the overlap from the right of the first argument to the left of the second). Solving this (good luck!) then cutting the resulting loop at the highest cost (lowest overlap) will give an ordered list of words which can be merged to give an optimal solution.

Impressive. Is this checking every word in the current list against every other, each time through? I was considering this but assumed I'd need to just check a random sample to make it run in a reasonable time.

I wonder if it'd be possible to "cache" the distances between pairs in a way that you don't have to re-check them with each other every time, and only have to check them against the new megaword? At any rate, this is incredible and I wonder if it's completely optimal or not.

@ValueInk yes caching would be a big performance boost. An earlier version had that, but it adds a lot of complexity, so when I adapted some logic I had to re-write the lot. Instead I chose to drop caching. Also no, this isn't completely optimal. It's a greedy algorithm so it can't judge trade-offs, and it's unable to choose between "equally good" options. See my TSP comment for the (NP-Hard) optimal solution.

@trichoplax yup, that's what it's doing. Running time is O(n^3), which isn't so bad for this sample size. With caching it could be reduced to O(n^2). The inner check is also very parallel-isable, so even for larger samples it could run in reasonable time with threading / distributed computation. Also this gets a big speed boost from knowing the range of possible overlap widths for each step, which cut the runtime by a factor of 10.

This might not be as hard as general TSP, because we have the funny constraint that overlap(a, b) ≥ min{overlap(a, d), overlap(c, d), overlap(c, b)} for all a, b, c, d.

C++11, 38272 letters, proven optimal
This algorithm is guaranteed to provide a lower bound on the solution. In this case, it is able to achieve the lower bound and output an optimal 38272 letter solution. (This matches the solution found by Dave’s greedy algorithm. I was surprised and a little disappointed to discover that it’s optimal, but, there we are.)
It works by solving the minimum-cost flow problem on the network built as follows.

First, any words contained in other words are redundant; discard them.
For every word w, draw two nodes w_0 and w_1, where w_0 is a source with capacity 1 and w_1 is a sink with capacity 1.
For every (strict) prefix or suffix a of any word, draw a node a.
For every suffix a of w, draw an arc from w_0 to a with capacity 1 and cost 0.
For every prefix a of w, draw an arc from a to w_1 with capacity 1 and cost length(w) − length(a).

Any string of length n that contains every word can be converted into a flow on this network with cost at most n. Therefore, the minimum cost flow on this network is a lower bound on the length of the shortest such string.
If we’re lucky—and in this case we are—then after we redirect the flow coming into w_1 back out of w_0, we will find an optimal flow that has just one connected component and that passes through the node for the empty string. If so, it will contain an Eulerian circuit starting and ending there. Such an Eulerian circuit can be read back out as a string of optimal length.
If we weren’t lucky, add some extra arcs between the empty string and the shortest strings in the other connected components in order to ensure that an Eulerian circuit exists. The string would no longer necessarily be optimal in that case.
I use the LEMON library for its min-cost flow and Eulerian circuit algorithms. (This was my first time using this library, and I was impressed—I will definitely use it again for future graph algorithm needs.) LEMON comes with four different minimum-cost flow algorithms; you can try them here with --net, --cost, --cap, and --cycle (default).
The program runs in 0.5 seconds, producing this output string.
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <lemon/core.h>
#include <lemon/connectivity.h>
#include <lemon/euler.h>
#include <lemon/maps.h>
#include <lemon/list_graph.h>
#include <lemon/network_simplex.h>
#include <lemon/cost_scaling.h>
#include <lemon/capacity_scaling.h>
#include <lemon/cycle_canceling.h>

using namespace std;

typedef lemon::ListDigraph G;

struct Word {
    G::Node suffix, prefix;
    G::Node tour_node;
};

struct Edge {
    unordered_map<string, Word>::iterator w;
    G::Arc arc;
};

struct Affix {
    vector<Edge> suffix, prefix;
    G::Node node;
    G::Node tour_node;
};

template<class MCF>
bool solve(const G &net, const G::ArcMap<int> &lowerMap, const G::ArcMap<int> &upperMap, const G::ArcMap<int> &costMap, const G::NodeMap<int> &supplyMap, int &totalCost, G::ArcMap<int> &flowMap)
{
    MCF mcf(net);
    if (mcf.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap).supplyMap(supplyMap).run() != mcf.OPTIMAL)
        return false;
    totalCost = mcf.totalCost();
    mcf.flowMap(flowMap);
    return true;
}

int main(int argc, char **argv)
{
    clog << "Reading dictionary from stdin" << endl;
    unordered_map<string, Affix> affixes;
    unordered_map<string, Word> words;
    unordered_set<string> subwords;
    G net, tour;
    G::ArcMap<int> lowerMap(net), upperMap(net), costMap(net);
    G::NodeMap<int> supplyMap(net);
    string new_word;
    while (getline(cin, new_word)) {
        if (subwords.find(new_word) != subwords.end())
            continue;
        for (auto i = new_word.begin(); i != new_word.end(); ++i) {
            for (auto j = new_word.end(); j != i; --j) {
                string s(i, j);
                words.erase(s);
                subwords.insert(s);
            }
        }
        words.emplace(new_word, Word());
    }
    for (auto w = words.begin(); w != words.end(); ++w) {
        w->second.suffix = net.addNode();
        supplyMap.set(w->second.suffix, 1);
        w->second.prefix = net.addNode();
        supplyMap.set(w->second.prefix, -1);
        for (auto i = w->first.begin(); ; ++i) {
            affixes.emplace(string(w->first.begin(), i), Affix()).first->second.prefix.push_back(Edge {w});
            affixes.emplace(string(i, w->first.end()), Affix()).first->second.suffix.push_back(Edge {w});
            if (i == w->first.end())
                break;
        }
        w->second.tour_node = tour.addNode();
    }
    for (auto a = affixes.begin(); a != affixes.end();) {
        if (a->second.suffix.empty() || a->second.prefix.empty() ||
            (a->second.suffix.size() == 1 && a->second.prefix.size() == 1 &&
             a->second.suffix.begin()->w == a->second.prefix.begin()->w)) {
            affixes.erase(a++);
        } else {
            a->second.node = net.addNode();
            supplyMap.set(a->second.node, 0);
            for (auto &e : a->second.suffix) {
                e.arc = net.addArc(e.w->second.suffix, a->second.node);
                lowerMap.set(e.arc, 0);
                upperMap.set(e.arc, 1);
                costMap.set(e.arc, 0);
            }
            for (auto &e : a->second.prefix) {
                e.arc = net.addArc(a->second.node, e.w->second.prefix);
                lowerMap.set(e.arc, 0);
                upperMap.set(e.arc, 1);
                costMap.set(e.arc, e.w->first.length() - a->first.length());
            }
            a->second.tour_node = lemon::INVALID;
            ++a;
        }
    }

    clog << "Read " << words.size() << " words and found " << affixes.size() << " affixes; ";
    clog << "created network with " << countNodes(net) << " nodes and " << countArcs(net) << " arcs" << endl;

    int totalCost;
    G::ArcMap<int> flowMap(net);
    bool solved;
    if (argc > 1 && string(argv[1]) == "--net") {
        clog << "Using network simplex algorithm" << endl;
        solved = solve<lemon::NetworkSimplex<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if (argc > 1 && string(argv[1]) == "--cost") {
        clog << "Using cost scaling algorithm" << endl;
        solved = solve<lemon::CostScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if (argc > 1 && string(argv[1]) == "--cap") {
        clog << "Using capacity scaling algorithm" << endl;
        solved = solve<lemon::CapacityScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if ((argc > 1 && string(argv[1]) == "--cycle") || true) {
        clog << "Using cycle canceling algorithm" << endl;
        solved = solve<lemon::CycleCanceling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    }

    if (!solved) {
        clog << "error: no solution found" << endl;
        return 1;
    }
    clog << "Lower bound: " << totalCost << endl;

    G::ArcMap<string> arcLabel(tour);
    G::Node empty = tour.addNode();
    affixes.find("")->second.tour_node = empty;
    for (auto &a : affixes) {
        for (auto &e : a.second.suffix) {
            if (flowMap[e.arc]) {
                if (a.second.tour_node == lemon::INVALID)
                    a.second.tour_node = tour.addNode();
                arcLabel.set(tour.addArc(e.w->second.tour_node, a.second.tour_node), "");
            }
        }
        for (auto &e : a.second.prefix) {
            if (flowMap[e.arc]) {
                if (a.second.tour_node == lemon::INVALID)
                    a.second.tour_node = tour.addNode();
                arcLabel.set(tour.addArc(a.second.tour_node, e.w->second.tour_node), e.w->first.substr(a.first.length()));
            }
        }
    }

    clog << "Created tour graph with " << countNodes(tour) << " nodes and " << countArcs(tour) << " arcs" << endl;

    G::NodeMap<int> compMap(tour);
    int components = lemon::stronglyConnectedComponents(tour, compMap);
    if (components != 1) {
        vector<unordered_map<string, Affix>::iterator> breaks(components, affixes.end());
        for (auto a = affixes.begin(); a != affixes.end(); ++a) {
            if (a->second.tour_node == lemon::INVALID)
                continue;
            int c = compMap[a->second.tour_node];
            if (c == compMap[empty])
                continue;
            auto &b = breaks[compMap[a->second.tour_node]];
            if (b == affixes.end() || b->first.length() > a->first.length())
                b = a;
        }
        int offset = 0;
        for (auto &b : breaks) {
            if (b != affixes.end()) {
                arcLabel.set(tour.addArc(empty, b->second.tour_node), b->first);
                arcLabel.set(tour.addArc(b->second.tour_node, empty), "");
                offset += b->first.length();
            }
        }
        clog << "warning: Found " << components << " components; solution may be suboptimal by up to " << offset << " letters" << endl;
    }

    if (!lemon::eulerian(tour)) {
        clog << "error: failed to make tour graph Eulerian" << endl;
        return 1;
    }

    for (lemon::DiEulerIt<G> e(tour, empty); e != lemon::INVALID; ++e)
        cout << arcLabel[e];
    cout << endl;

    return 0;
}

While I can't claim to understand how min flow works, if this really is optimal, well done!

Sorry to disappoint :P I hadn't thought of a flow network; that's pretty elegant. Took me a while to understand how you were linking the words together in your network before I finally realised "For every (strict) prefix or suffix a of any word, draw a node a" meant that the nodes "a" can be shared between multiple words.

Also your solution is about 2,000 times faster than mine!

Maybe help this guy (http://www.cs.cmu.edu/~tom7/portmantout/) out with his attempt at a similar thing?

@OliverDaugherty-Long Done! (For real this time.) The best previously known bounds were 520732 ≤ optimal length ≤ 537136, and I believe I have improved both bounds to 536186.

Java 8, ~5 Minutes, Length of 39,279
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;

public class Words {

    public static void main(String[] args) throws Throwable {
        File file = new File("words.txt");
        List<String> wordsList = new ArrayList<>();
        BufferedReader reader = new BufferedReader(new FileReader(file));
        String line;
        while ((line = reader.readLine()) != null) {
            wordsList.add(line);
        }
        reader.close();

        Set<String> words = new HashSet<>();

        System.out.println("Finished I/O");

        for (int i = 0; i < wordsList.size(); i++) { //Step 1: remove any words that occur in other words
            boolean in = false;
            for (int j = 0; j < wordsList.size(); j++) {
                if (i != j && wordsList.get(j).contains(wordsList.get(i))) {
                    in = true;
                    break;
                }
            }
            if (!in) {
                words.add(wordsList.get(i));
            }
        }

        System.out.println("Removed direct containers");

        List<String> working = words.stream().sorted((c, b) -> Integer.compare(c.length(), b.length())).collect(Collectors.toList()); //Sort by length, shortest first
        StringBuilder result = new StringBuilder();
        result.append(working.get(0));
        while (!working.isEmpty()) {
            Optional<String> target = working.stream().sorted((c, b) -> Integer.compare(firstLastCommonality(result.toString(), b), firstLastCommonality(result.toString(), c))).findFirst(); //Find the string that has the greatest in common with the end of 'result'
            if(target.isPresent()) { //It really should be present, but just in case
                String s = target.get();
                working.remove(s);
                int commonality = firstLastCommonality(result.toString(), s);
                s = s.substring(commonality);
                result.append(s);
            }
        }

        System.out.println("Finished algorithm");

        String r = result.toString();
        System.out.println("The string: \n" + r);
        System.out.println("Length: \n" + r.length());
        System.out.println("Verified: \n" + !wordsList.stream().filter(s -> !r.contains(s)).findFirst().isPresent());
    }

    private static int firstLastCommonality(String a, String b) {
        int count = 0;
        int len = b.length();
        while (!a.endsWith(b) && !b.equals("")) {
            b = cutLastChar(b);
            count++;
        }
        return len - count;
    }

    private static String cutLastChar(String string) {
        if (string.length() - 1 < 0) {
            return string;
        } else {
            return string.substring(0, string.length() - 1);
        }
    }

}

Input:

a file called 'words.txt' in the working directory, in the exact same format as the file in the main post

Output:
Finished I/O
Removed direct containers
Finished algorithm
The string:
[Moved to pastebin](http://pastebin.com/iygyR3zL)
Length:
39279
Verified:
true

FGITW, and in Java no less. You sir have my vote.

Nice! You got rid of 26,609 characters.

@R.Kap go figure! I didn't even think to calculate that... There must be a smarter algorithm though, this is just the first thing that came to mind...

Python 2, 39254 characters
Takes 1-2 minutes to run on my machine, works by taking the longest word and then always adding the word to the result string that has the most strings in common. (Before that all words that are substrings of other words are removed to prevent unnecessary adding to the string.)
Update: Tried to look in both directions, but that doesn't do any better. (maybe it's using words that can be used better later?)
Link to the word on pastebin.
first 100 chars:
telecommunicationsawayneillegallynnbabyenbcjrxltdxmlbsrcwvtxxxboxespnycdsriconsentencessexyrsslipodc

Code:
import re
import urllib

def suffix_dist(w1,w2):
    for i in range(min(map(len,[w1,w2])))[::-1]:
        if w1[-i:]==w2[:i]:
            return i
    return 0

url="https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt"
s=urllib.urlopen(url).read()
words=s.split()
words.sort(key=len,reverse=True)

## remove words that are substrings of other words anyway
for i in range(len(words))[::-1]:
    if any(words[i] in w for w in words[:i]):
        words.pop(i)

print len(words)

words.sort(key=len)
w1=words.pop(-1)
result=w1
while words:
    ## get the word with longest shared suffix/prefix
    w2=max(words,key=lambda x:suffix_dist(w1,x))
    print w2
    words.pop(words.index(w2))
    if w2 in result:
        break
    result+=w2[suffix_dist(w1,w2):]
    w1=w2

print result[:100]
print len(result)
print "Test:", all(w in result for w in s.split())

Welp, I've been beaten by 25 characters... +1 for that

Nice work! I had a similar idea but you already had an answer up. My version starts with a small word instead of a big word, plus some other pruning that causes it to drastically lose out on the time factor, taking up to 3x the amount of time to run.

Ruby, 39222 characters
Uses a similar approach to @KarlKastor in his Python answer, but the starting string is one of the smallest words instead of the largest. Another optimization (I don't know how much it helps) is that in between each addition, it prunes any words that may have already been included in the string due to overlapping words.
Runs in a little over 4 minutes on my machine, not counting the web request to retrieve the list of words, but not quite 4:20.
The word on Pastebin.
require 'net/http'

puts "Obtaining word list..."
data = Net::HTTP.get(URI'https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt')
puts "Word list obtained!"

puts "Starting calculation..."
time = Time.now

words = data.split.sort_by(&:size)
words.reject!{|w| words.find{|x| w!=x && x.include?(w)}}

string = words.shift

def merge_dist(prefix, suffix)
    [prefix.size,suffix.size].min.downto(0).find{|i| prefix.end_with?(suffix[0,i])}
end

while words.length > 0
    suffix = words.max_by{|w| merge_dist string, w}
    string += suffix[merge_dist(string, suffix)..-1]
    words.reject!{|w| string.include? w}
end

delta = Time.now - time

puts "Calculation completed in #{delta} seconds!"
puts "Word is #{string.size} chars long."

open("word.txt", 'w') << string

puts "Word saved to word.txt"

PowerShell v2+, 46152 characters
param([System.Collections.ArrayList]$n)$n=$n|sort length -des;while($n){$x=$n.Count;$o+=$n[0];0..$x|%{if($o.IndexOf($n[$_])-ge0){$n.RemoveAt($_)}}}$o

Takes the input as a list, casts it into an ArrayList (so we can manipulate it). We sort it by length in -descending order. Then, while we still have words in our input array, do a loop. Each iteration, set helper $x to be equal to how many we have left, tack on the next item in the list to our output $o, and then trawl through everything still in our list. If the .IndexOf is not equal to -1 (i.e., the word was found somewhere in $o), we remove that word from our list of remaining words. Finally, at the end, output $o.
I don't have access to a Pastebin or similar, so here's the beginning and end of the word for temporary --  telecommunicationscharacterizationresponsibilitiessublimedirectory...fcmxvtwvfxwujmjsuhjjrxjdbkdxqc. Which I guess has shaved about 20,000 characters off of the input, so not that bad, I suppose.
I'm working on refinements.

PHP 46612 characters
This is just a start. I hope to improve it. All I've done so far is remove any word that is a sub-string of another word. I'm working on 3 copies of the array, but the memory doesn't seem to be an issue.
<?php
set_time_limit(3000);

$words=file('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt');
$words = array_map('trim', $words);

usort($words, function ($a, $b)
{
    if (strlen($a) == strlen($b) ){
        return 0;
    }
    return ( strlen($a) < strlen($b) )? -1 : 1;
});

$final_array=$words;
$comparison_array=$words;

  foreach($words as $key => $word){
    echo $word."<br>\n";
      foreach($comparison_array as $nestedKey => $nestedWord){
          if (strlen($nestedWord) <= strlen($word)) {
            unset($comparison_array[$nestedKey]);
            continue;
          }
          if( strpos($nestedWord,$word) !== FALSE ){
              unset($final_array[$key]);
              $restart=true;
              break;
          }
      }
  }

sort($final_array);
$compound='';
$compound = implode($final_array);
echo $compound;
echo "  <br><br>\n\n". strlen($compound);


text:
Number of cycles of a permutation
Consider a permutation of the integers 1, ..., n, such as this one for n = 6:
[5,2,4,3,6,1]

If you view the permutation as a mapping from [1,2,3,4,5,6] to [5,2,4,3,6,1], the permutation can be decomponsed into disjoint cycles. A cycle is a subset of elements that map to each other. For example, 1 gets mapped to 5, which gets mapped to 6, which gets mapped back to 1. So one cycle is [1,5,6]. The other cycles are [2] and [3,4]. Thus the number of cycles for this permutation is 3.
In general, the cycles of a permutation are unique (up to order), and the number of cycles for a permutation of size n varies from 1 to n.
The challenge
Given a non-empty permutation, output its number of cycles.
Input is an array formed by the n integers 1, 2, ..., n, where n > 0. Each integer occurs exactly once. The order in which they appear defines the permutation, as in the example above.
Instead of an array you can use a list, a string with a separator between the numbers, a separate input for each number, or anything that's reasonable.
For a permutation of size n, instead of the 1-based set of integers 1, ..., n you can consistently use the 0-based set 0, ..., n-1. If so, please indicate it in your answer.
The code should work for n up to 20 in a reasonable time, say less than one minute.
Code golf. All builtins allowed.
Test cases
This assumes 1-based, array input.
 [1] -> 1
 [3,2,1] -> 2
 [2,3,4,5,1] -> 1
 [5,2,4,3,6,1] -> 3
 [8,6,4,5,2,1,7,3] -> 2
 [4,5,11,12,7,1,3,9,10,6,8,2] -> 1
 [4,2,5,11,12,7,1,3,9,10,6,8] -> 5
 [5,8,6,18,16,9,14,10,11,12,4,20,15,19,2,17,1,13,7,3] -> 3
 [14,5,17,15,10,18,1,3,4,13,11,16,2,12,9,7,20,6,19,8] -> 7

Related
This related challenge asks for the actual cycles of the permutation, not the number of them. Requiring only the number of cycles can lead to shorter algorithms that sidestep generating the actual cycles.

Nevermind my question, it is stated in the question 0-based input is allowed.

@orlp That was quick! I didn't even get to see your question

Can we take a mapping of indexes to values as input?

@Copper I think yes, if the domain of the mapping is the set 1, ..., n in that order. Can you clarify how can a mapping be an input? Is it a data structure?

@LuisMendo Yes, it's a data structure, like a Python dict. I want to have {1: 2, 2: 1} as an input instead of [2, 1].

@Copper Ok, I think it's quite reasonable

J, 4 bytes
#@C.

This assumes that the permutation is 0-based. It uses the builtin C. which given a list representing a direct permutation outputs a list of cycles. Then # composed @ on that returns the number of cycles in that list.
Try it here.

That's cheating! :)

I should have banned builtins :-D

Builtins are love. Builtins are life. I do agree it would be more fun with builtins being banned. Feel free to change the rule right now before too many answer.

@miles Nah, I'll leave it as it is. Good job!

JavaScript, 99 98 bytes
This solution assumes the array and its values are zero-indexed (e.g. [2, 1, 0]).
f=a=>{h={},i=c=0;while(i<a.length){s=i;while(!h[i]){h[i]=1;i=a[i]}c++;i=s;while(h[++i]);}return c}

Explanation
// assumes the array is valid and zero-indexed
var findCycles = (array) => {
    var hash = {};  // remembers visited nodes
    var index = 0;  // current node
    var count = 0;  // number of cycles
    var start;      // starting node of cycle

    // loop until all nodes visited
    while(index < array.length) {
        start = index;  // cache starting node

        // loop until found previously visited node
        while(!hash[index]) {
            hash[index] = 1;    // mark node as visited
            index = array[index];   // get next node
        }
        count++;    // increment number of cycles

        index = start + 1;  // assume next node is right after

        // loop until found unvisited node
        while(hash[index]) {
            index++;    // get next node
        }
    }

    return count;   // return number of cycles
};

Welcome to PPCG! Nice first answer! This is also one of the best, if not the best, first answer I have seen in my experience! Keep up the good work!

Wow thank you so much!  I actually had to look up how to do the lambdas in JavaScript.  I'm not that familiar with the ES6 stuff yet.

Python, 77 69 67 bytes
f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))

(not p[i-1]) can be done as 0**p[i-1]

Mathematica, 45 bytes
Length@ConnectedComponents@Thread[Sort@#->#]&

It generates a graph and counts its connected components.

Mathematica, 37 28 27 bytes
#~PermutationCycles~Length&

Thanks @alephalpha for saving 9 bytes, and @miles for 1 more byte.

PermutationCycles[#,Length]&

Oh that's neat. I didn't know PermutationCycles could take a second argument to alter the head of its output. You can also use infix notation to save another byte #~PermutationCycles~Length&.

Also regarding your original solution, #& is a fair bit shorter than Identity. ;)

Python, 64 bytes
l=input()
for _ in l:l=[min(x,l[x])for x in l]
print len(set(l))

This golfed code happens to be idiomatic and readable. Uses 0-indexing.
Each value looks at what it points to and what the pointed value points to, and points to the smaller of the two. After enough repetitions, each element points to the smallest element of its cycle. The number of distinct elements pointed to is then the number of cycles.
It suffices to do n iterations. Alternatively, we could iterate until the list no longer changes. This strategy gave me a recursive function of the same length, 64 bytes:
f=lambda l,p=0:len(set(l*(l==p)))or f([min(x,l[x])for x in l],l)

Reducing was 65 bytes
lambda l:len(set(reduce(lambda l,_:[min(x,l[x])for x in l],l,l)))

The set(_) conversions can be shortened to {*_} in Python 3.5, saving 2 bytes.

Jelly, 12 10 9 bytes
ị³$ÐĿ«/QL

Saved 1 byte thanks to @Dennis.
This uses 1-based permutations. It works by applying the permutation repeatedly until it reaches a previous permutation while also keeping its previous values. By keeping track of the changes, it will create the orbit for every value along the columns of that table. Then, by finding either the minimum or maximum of each column, a label for that cycle can be created. Then deduplicate that list of labels and get the length of it which will be the number of disjoint cycles.
Try it here.
Explanation
ị³$ÐĿ«/QL  Input: permutation p
  $        Chain (ị³) as a monad
 ³           The input p
ị            For each value x, get the value at index x in p
   ÐĿ      Invoke it on p initially, and repeat it on its next value until it returns
           to a previous value and keep track of the results
           This will create a table where each column is the orbit of each value
     «/    Get the minimum value along each column of that table
       Q   Deduplicate
        L  Get the length and return

Very nice approach!

ị³$ÐĿ«/QL should work.

@Dennis Wow, that is a neat trick! Since each cycle is disjoint, taking either the max/min and using it as a label will be enough to deduplicate+length for the result.

Haskell, 111 bytes
l!i|l!!i<0=l|1<2=(take i l++[-1]++drop(i+1)l)!(l!!i)
f(x:y)|x>=0=0|1<2=1+f y
c l|l==[-1|x<-l]=0|1<2=1+c(l!f l)

Uses 0-based indexing

Damn, you better have a good programming font :) 1l!i|iIi!!1ll1|

@orlp and it's 111 bytes! :O

Pyth, 9 bytes
l{mS.u@QN

Uses 0-based indexes.
Try it online.
How it works
  m         map for d in input:
    .u        cumulative fixed-point: starting at N=d, repeatedly replace N with
      @QN       input[N]
              until a duplicate is found, and return all intermediate results
   S          sort
 {          deduplicate
l           length

JavaScript (ES6), 49 bytes
a=>a.reduce(g=(c,e,i)=>e<i?g(c,a[e],i):c+=e==i,0)

Uses zero-based indexing. Explanation: reduce is used to invoke the inner function g on each element of the array. c is the count of cycles, e is the array element, i is the array index. If the element is less than the index, then it's a potential cycle - the element is used to index into the array to find the next element in the cycle recursively. If we started out or end up with the original index then this is a new cycle and we increment the cycle count. If at any point we find a value larger than the index then we'll count that cycle later.

When I ran your code on the array [2,1,0,3,4,5], it crashed with this message "Maximum call stack size exceeded".

@kamoroso94 Sorry about that, a typo had crept in. Should be fixed now.

C, 90 bytes
Call f() with a mutable int array, 1 based indexing. The second parameter is the size of the array. The function returns the number of cycles.
i,j,c;f(a,n)int*a;{for(c=i=0;i<n;++i)for(j=0,c+=!!a[i];a[i];a[i]=0,i=j-1)j=a[i];return c;}

Try it on ideone.
The algorithm:
For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.

GAP, 30 bytes
Straightforward, the second argument to Cycles gives the set on which the permutation should act:
l->Size(Cycles(PermList(l),l))


text:
Lead Your Turtle by a String
Write a program or function that takes in a nonempty single-line string of printable ascii characters excluding space:
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

You may assume the input is valid.
Based on the input, draw a new string arranged on a textual grid of spaces and newlines following turtle graphics-esque rules where the turtle always occupies one grid space and can only face the cardinal directions.
Print the first character in the input string to the text grid. The turtle starts here facing right. Iterate over the rest of the characters in the input string (only stopping if the turtle gets stuck), repeating this process:

If the 4 grid spaces directly neighboring the turtle are all filled (i.e. none of them is a space), stop iterating. The turtle is stuck and the grid is as  complete as it can be.
Look at the current character in the input compared to the previous character:

If the current character is lexically before the previous, rotate the turtle a quarter turn left.
If the current character is lexically after the previous, rotate the turtle a quarter turn right.
If the current character equals the previous, don't rotate the turtle.

If the grid space the turtle is now facing is not empty (i.e. not a space), repeatedly rotate the turtle a quarter turn left until she is facing an empty grid space.
Move the turtle one grid step forward in the direction she's facing and print the current character on the grid in the turtle's new location.

Print or return the resulting text grid string with no extraneous rows or columns of whitespace. Lines may have trailing spaces up to the rightmost column with a non-space, but not beyond. A single trailing newline is optionally allowed.
The shortest code in bytes wins.
Example
Here are all the steps of the input spattuuxze. The ^V<> characters show the direction the turtle is facing, they are not part of the input or output.
s>
^
p
s
<ap
  s
^
t
ap
 s
^
t
t
ap
 s
tu>
t
ap
 s
tuu>
t
ap
 s
tuu
t x
apV
 s
tuu
<zx
ap
 s
At this point the turtle is stuck so the e never gets printed and the final output is:
tuu
tzx
ap
 s

Following is a similar but invalid output since it has an unnecessary leading column of whitespace:
 tuu
 tzx
 ap
  s

Test Cases
spattuuxze

tuu
tzx
ap
 s

spattuuxxze

tuu
t x
apx
 sze

1111111

1111111

ABCDEFGHIJKLMNOP

PEFG
ODAH
NCBI
MLKJ

`_^]\[ZYXWVUTSR

 ^_RS
\]`UT
[ZWV
 YX

Woo!

W
o
o!

woo!

!o
 o
 w

Wheeee

W
heeee

banana

  a
 an
an
b

Turtle

T
ure
 tl

turTle

  e
tTl
ur

(Do tell me right away if any of these seem wrong.)

You weren't kidding.

I think you should add the test case PONMLKJIHGFEDCBA, since the result is not just a square and contrasts with ABCDEFGHIJKLMNOP to highlight the asymmetry in the rules.

Groovy (357 Bytes)
No external turtle libs were used and no turtles were harmed.
R={s->s[0]?[0,-1*s[0]]:[s[1],0]}
L={s->s[0]?[0,s[0]]:[-1*s[1],0]}
def y(s){l=s.length()*2;z(new String[l][l],[l/4,l/4],s,null,[0,1])}
def z(g,l,w,p,h){if(w.length() && !g[(int)(l[0]+h[0])][(int)(l[1]+h[1])]){c=w.getAt(0);w=w.substring(1);if(p && p<c){h=R(h)}else if(p>c){h=L(h)};g[(int)l[0]+h[0]][(int)l[1]+h[1]]=c;z(g,[l[0]+h[0],l[1]+h[1]],w,c,h)}else{g}}

Try it here:
https://groovyconsole.appspot.com/edit/5115774872059904

Previous Attempts
Groovy (397 Bytes)
rotR={s->s[0]!=0?[0,-1*s[0]]:[s[1],0]}
rotL={s->s[0]!=0?[0,s[0]]:[-1*s[1],0]}
def y(s){z(new String[s.length()][s.length()],[s.length()/2,s.length()/2],s,null,[0,1])}
def z(g,l,w,p,h){if(w.length() && !g[(int)(l[0]+h[0])][(int)(l[1]+h[1])]){c=w.getAt(0);w=w.substring(1);if(p && p<c){h=rotR(h)}else if(p > c){h=rotL(h)};g[(int)l[0]+h[0]][(int)l[1]+h[1]]=c;z(g,[l[0]+h[0],l[1]+h[1]],w,c,h)}else{g}}

https://groovyconsole.appspot.com/script/5179465747398656

Answers must be complete and valid. Please delete your answer or finish it. Also, 30 minutes isn't very long. I've spent hours on answers before.

Java, 408 406 bytes
String f(String I){int l=I.length(),x=l,y=x,z=x,t=y,Z=x,T=y,d=1,i=1,a;char[][]g=new char[l*2][l*2];int[]D={-1,0,1,0};for(char c,p=g[x][y]=I.charAt(0);i<l;p=c){c=I.charAt(i++);d=((c<p?d-1:c>p?d+1:d)+4)%4;for(a=0;g[x+D[d]][y+D[3-d]]>0&&a++<4;)d=(d+3)%4;if(a>3)break;g[x+=D[d]][y+=D[3-d]]=c;z=z<x?z:x;Z=Z>x?Z:x;t=t<y?t:y;T=T>y?T:y;}for(I="";z<=Z;z++,I+="\n")for(a=t;a<=T;a++)I+=g[z][a]<1?32:g[z][a];return I;}

The function gets the the input as String and returns the outcome as a String.
Internally it uses a 2D char array to store the letters and keeps the min and max columns and rows used in order to return the sub-array that was used.
So, in the outcome String there are no leading columns of white-spaces but there are trailing white-spaces up to the rightmost column with a non-space character. A newline is added at the end.
Any suggestions to golf it more are welcome :-)

You might be able to do a smaller byte count using a char[] as input.
((c<p?d-1:c>p?d+1:d)+4)%4
Also, + 4 % 4 = 0, correct me if I'm wrong there but removing that +4 should not change your code.

@carusocomputing It is true that char[] as input would save many bytes but I am not sure if this is permitted by the question. The question mentions an "input string". Also the +4 is required because d which is the direction has to be bounded between 0 and 4. % is the remainder in java and it can be negative which is not desired. Thanks for the suggestions :-)

Ah... Good catch, fallacy on my end being that the inputs offered by OP covered all scenarios... "LNOPFg1#" breaks it without the +4. Sorry, even reading that code took me a minute.

Python3, 419 414 bytes
Z=input();l=r=c=M=R=C=N=len(Z);t=(r*2)+1;A=[0]*t;J=range
for i in J(t):A[i]=[" "]*t
A[r][c]=Z[0];i=1;Q=[1,0,-1,0];d=q=0
while i<l:
 if Z[i]<Z[i-1]:d+=3
 elif Z[i]>Z[i-1]:d+=1
 while A[r+Q[(d-1)%4]][c+Q[d%4]]!=" "and q<4:d+=3;q+=1
 if q>3:break
 r+=Q[(d-1)%4];c+=Q[d%4];R=min(R,r);C=min(C,c);M=max(M,r);N=max(N,c);A[r][c]=Z[i];i+=1;q=0
for i in J(R,M+1):
 for j in J(C,N+1):print(A[i][j],end="")
 print()


text:
King of the Torus!
King of the Torus!
Your job is to conquer the torus, but wait, there are multiple other players banded together in teams facing you! You will need to use your wit's to conquer the torus.
There are three teams: red, blue and green. Teams are self-assigned arbitrarily. If the teams are even you may join the team of your choice, otherwise you must join the smallest team(s). The map is a torus presented as a square of length 640  by 640.  Lets take a look at a sample map
OOOOOOOOOOOOOOOOOOOOOOOOOOO
RRRRRRRRRRRRRRRRRRRRRRRRRRR
OOOOOOOOOOOOOOOOOOOOOOOOOOO
GGGGGOOOOOOOOBBBBBBBBBBBBBB
GGGGGGGGGGGGGGGGGGGGGOOOOOG
OOOOOOOOOOOOOOOOOOOOOOOOOGG
RRRRRRRRRRRRRRRRRRRRRRRRRRR
OOOOOOOOOOOOOOOOOOOOOOOOOOO

as you can see, the red team has built a wall to safely conquer the territory between the two walls. Blue, and green will have to fight it out. This scaled down version of the map is representative of the larger one.
Red would likely win this battle as they would finish the game (once the board is filled or a large number of turns have passed) with the most territory
Now each bot has a location (known only to you). You can only move to an adjacent square if it is owned by your team. At the start of your game, you start on a single square of your teams color. Your goal is to expand this splotch by conquering other land. At any turn you can choose to move to any adjacent color of your own territory or you may alternatively choose to attack an adjacent territory. If the attacked square is unowned it will be captured.
Java API
You will override the Bot class to return a single number (0-3) for attempted moves and 4-7 for an attempted attack. Your bot's should only take 10 milliseconds to move, but the rule will not be formally enforced unless it becomes a problem. Problematic, malicous, or otherwise obnoxious bots are clearly not in the spirit of this competition and will be disqualified with an immediate low quality flag.
Otherwise bots acting in good faith, but otherwise buggy will be given time as needed for bug repairs.
Method summary
public abstract class Bot{
public final int team;// 0 = red 1 = green 2 = blue
public Bot(int inTeam){team=inTeam}//be sure to call super(inTeam);
public int move(){};//you will override this
}

Methods available

Color Bot.getColor(int x,int y){}//returns a Color object with rgb values where the r g or b value of the team owning it will be 100.
getX(); returns the X position of your bot
getY(); returns the y position of your bot
Bot.getMap();//returns the array representing the map. I.e Bot.getMap[i][j] returns a color with r g b values representing each teams stake in that spot.
//only one r g b value will be greater than 0 as only one team can hold a spot
Do not abuse the map access. Giving direct access (as opposed to a copy) is to speed up access to the map. Abusing it will result in disqualification!

A wrapper program may be made available as long as it still allows the program to run smoothly.
How to play:
Step one: Post your bot here as an answer and ensure it follows the specs.
Step Two Head over to this gitHub repository fork it and add your bot's file in as well as add these two lines after '//init bots' Bot.run. Be sure to choose the team with the least members if applicable.
  bots.add(new UniqueBotNameHere(team=choiceOfTeam,x=getRandom(0,map.length),y=getRandom(0,map[0].length)));
    map[x][y].colors[team]=255;

Step Three: Make a pull request. I will accept your pull request and your bot will automagically be added to the tournament.
Step Four: Download the source files and copy them into the proper package. Run the build and enjoy watching the bots

Good luck and don't let your team down! Team's will be made even by my sample bots. I may also move around teams to ensure equal members.

Interesting trivia
Modifying the Half Hearted flood filling sample bot, gives an interesting map generator.

related

Waller
He builds a wall, but he can't make the other team pay for it! He makes a nice low level bot to help debug your submissions.
public class Trump extends Bot{
int moves;
int direction;
    public Trump(int team, int inX, int inY) {
        super(team, inX, inY);
direction = Bot.getRandom(0, 4);
    }

    @Override
    public int move() {
int ret = direction;
switch(++moves%4){
    case 0:
        ret = direction+4;
        break;
    case 1:
        ret = direction;
        break;
    case 2:
        ret = direction + 1;
        break;
    case 3:
        ret = direction +3;
}
return ret;
    }

}

Half Hearted Flood Filler
Another low level bot. He tries to flood fill the map, but he only puts in 50% effort! I will enter another more competitve bot, but this guy is just to demonstrate one possible approach.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package toroidal.domination;

import java.awt.Color;
import java.util.Stack;

/**
 *
 * @author rohan
 */
public class HalfHeartedFloodFillBot extends Bot{
    public static class Node{
        public final int x,y;
        public Node(int x, int y){
            this.x=x;this.y=y;
        }
    }
private Stack<Integer> nodes = new Stack<>();
    public HalfHeartedFloodFillBot(int team, int inX, int inY) {
        super(team, inX, inY);
    }

    @Override
    public int move() {
        int x,y;

        for(int i = 0;i<4;i++){
    if(isEmpty(Bot.getColorAtSpot(x=getX()+(int) Math.cos(i*Math.PI/2),y= getY()+(int) Math.sin(i*Math.PI/2)))){
        nodes.add((i+2)%4);
        return i+4;
    }
}
        //no empty spots found try to backtrack or just do stuff!
return nodes.isEmpty()?Bot.getRandom(0,2)==0?Bot.getRandom(0, 2)==0?0:1:Bot.getRandom(0, 2)==0?2:3:nodes.pop();
    }
    boolean isEmpty(Color c){
        int r = c.getRed();
        int g = c.getGreen();
        int b = c.getBlue();
        return r == 0 && b == 0&& g == 0;
    }
}

SpiralBot
This bot will go until he hits something that is not neutral, then will turn left, making a spiral in the free space.
public class SpiralBot extends Bot{
    int d;

        public SpiralBot (int team, int inX, int inY) {
            super(team, inX, inY);
        d = 0;
        }

    int dx(int move){
        return (int) Math.cos(move * Math.PI / 2);
    }
    int dy(int move){
        return (int) Math.sin(move * Math.PI / 2);
    }

        @Override
        public int move() {
        int x = getX();
        int y = getY();
        Color[]c = new Color[4];
        for(int i = 0;i<4;i++)
            c[i] = Bot.getColor(x+dx(i), y+dy(i));
        if(c[d].equals(Color.black))
            return d;
        if(c[(d+1)%4].equals(Color.black))
            return d = (d+1)%4;
        if(c[(d+3)%4].equals(Color.black))
            return d = (d+3)%4;
        return d + 2;
    }

}

I have no account on GitHub, so if someone could push this for me that would be good. Thank you.

d i s not defined

@rohan fixed in an edit. I had an old version of the code.

Still seems to not work, as the issue is that you must attack a square before moving to it.