text:
Easily Typeable Words
This competition is over.
The winner is CJam with 22 characters, beating TwiNight's answer by one character. Congratulations Dennis!
An honorable mention goes to Falko, who went totally crazy with the free imports.
.

A while ago I wanted to know how I can out-type modern smartphones with my Nokia 3310, and while some answers were really good, I still can't keep up! Maybe I should take a different approach and simply not write any words that are awkward to type.
We'll call a piece of text easily typeable if no two consecutive letters are on the same button on the telephone keyboard, given the standard layout:

Your task
Your task is to write a program/function that accepts a string s from stdin/as a parameter and returns a truthy value if s is easily typeable and a falsy value otherwise. The input will only consist of lowercase letters and spaces and is guaranteed to be non-empty!
Scoring
This is codegolf, so lowest character-count wins.
Import statements will not be counted towards your final score, so if you've ever wanted to use std::set_symmetric_difference, liftM4, or itertools.combinations in your code, now is the time!
-3 if your source code is easily typeable, assuming everything that's not a letter is on button 0. After all, I might want to message your code to some friends!
Testcases
Here are a few testcases to check if your code is working as intended:
"x" -> True
"aardvark" -> False
"ardvark" -> True
"flonk" -> False

"im codegolfing all day long" -> False
"i indulge in minimizing bytecount" -> True

"havent heard from you in a long time" -> False
"your silence was of undue permanence" -> True

"how are  you" -> False
"how are you" -> True

Happy golfing!

Are two consecutive spaces bad?

@MartinBüttner yes! Should probably add a testcase for that.

But you don't need to wait between typing them and your finger is already where it belongs? :P

@MartinBüttner Haha wait, you don't? I don't actually own a 3310 anymore, but if I remember correctly the line break used to be on button 0 aswell :P

Hm, okay my memory isn't that clear any more either... your rules!

I have a nokia dumbphone, if I press space twice, I get a number 0.

Related question: devise a phone keyboard layout which maximises some score based on how easily typeable the most frequently occurring words are.

@jpcooper great idea! Will definitely ask that some time after this competition is over (unless you want to, of course)

@jpcooper like the two mentioned here? I've used 8pen and really like it, except that my phone glass heats up using it (from the contact, not from CPU activity) and the coefficient of friction makes it hard to use for long inputs. Using the s-pen on the Note 3 is so much easier :)

@Eben I hadn't actually heard of 8pen. Looks very interesting. I was in any case thinking of something that would fit on a standard number pad. I only have a "dumbphone" after all :)

my favorite dumbphone (which kinda was smart, it did internet) was my Blackberry Pearl. That beautiful 2 letter per key made it so super easy to type on!

CJam, 34 31 27 22 characters
1l{'h-_9/-D+3/X\:X^*}/

Try it online.
Example run
$ cjam <(echo "1l{'h-_9/-D+3/X\:X^*}/") <<< 'aardvark'; echo
0
$ cjam <(echo "1l{'h-_9/-D+3/X\:X^*}/") <<< 'ardvark'; echo
66000

How it works
1l                         " Push a R := 1 and read a line L from STDIN.                  ";
                           " Initialize X := 1. (implicit)                                ";
  {                  }/    " For each character C of L, do the following:                 ";
    'h-                    "     C -= 'h'                                                 ";
       _9/-D+3/            "     Y := (C - C / 9 + 13) / 3                                ";
               X\  ^*      "     R *= X ^ Y                                               ";
                 :X        "     X := Y                                                   ";
                           " Print R. (implicit)                                          ";

Background
The core of the code consists in applying a map F to each character C of the input string so that the images of symbols on the same key match. I found the a suitable map by observing the following:
The map T : C ↦ (C - 'h') + 13 transforms the string S := " abcdefghijklmnopqrstuvxyz" as follows:
[-59   6  7  8   9 10 11  12 13 14  15 16 17  18 19 20  21 22 23 24  25 26 27  28 29 30 31]

For the keys 0 to 6, it would suffice to divide T(C) by 3, but we have to apply some sort of correction to the characters in s, t, v, y and z.
The map D : C ↦ (C - 'h') / 9 transforms the string S into the following array:
[ -8   0  0  0   0  0  0   0  0  0   0  0  0   0  0  0   0  1  1  1   1  1  1   1  1  1  2]

This corrects the quotients of s, t, v, y and z, without affecting the others.
Finally, the map F : C ↦ (T(C) - D(C)) / 3 transforms the string S as follows:
[-17   2  2  2   3  3  3   4  4  4   5  5  5   6  6  6   7  7  7  7   8  8  8   9  9  9  9]

All that rests is to compare the consecutive characters somehow. For that purpose, we XOR F(C) with the image of the previous character – for the first, we XOR F(C) with 1 (default value of the variable X), which has no preimage – and multiply all the results.
The product will be falsy if and only if one of the factors is zero, i.e., if and only if two consecutive characters have the same image by F.

I think the byte (Not character) count for this one is 54

@Optimizer I think the [tag:code-golf] tag wiki says bytes

This answer no longer contains non-ASCII characters.

@professorfish The tag wiki is just the default. If the challenge specifies characters, it's characters.

Python 2 - 80, 68, 64, 61, 58, 50, 48, 45, 44 42
Even though it's getting a little ridiculous now, I'll keep on making use of free library imports, even the __builtin__ library:
from numpy import diff as D
from pprint import pprint as P
from __builtin__ import all as A
from __builtin__ import raw_input as I
from __builtin__ import bytearray as B

So only the following short line counts towards the code length:
P(A(D([(o-o/112-o/59)/3for o in B(I())])))

Credits to Markuz for the ideas regarding input()! These free-import challenges always introduce you to some lesser known libraries. ;)

Alternative using only the operator library (98, 83 79):
from operator import ne as n
K=[(ord(c)-1-(c>'p')-(c>'w'))/3for c in input()]
print all(map(n,K[1:],K[:-1]))

I'll stop here. But you could further golf this version using sys, pprint and other libraries...

Alternative without libraries (105):
s=input()
n=lambda c:(ord(c)-1-(c>'p')-(c>'w'))/3
print all([n(s[i])!=n(s[i+1])for i in range(len(s)-1)])

And once again we independently post the same solution in Ruby and Python. Looks like this time you're winning though. ;) ... Can't you also save 4 bytes, by assigning ord(c) to a variable (say o) and then subtracting c/112 and c/119 instead of the booleans?

@MartinBüttner: Yeah, once in a while Python can beat Ruby. Unfortunately I can't assign variables within lambda expressions that easily. With [(o-1-o/112-o/119)/3for o in map(ord,s)] I end up with 80 bytes again.

Ah I see. Sick new improvement though! :D

Very impressive. And you could still save 3 bytes with from sys import argv as s, using s[1] instead of input()

importing input from __builtin__ as well is actually even better :D saving yet another Byte.

Blatant rule abuse. I love it!

Using itertools.imap instead of map lets you remove a slice, and using bytearray(s) can replace a map(ord,s). Might want to use raw_input as you seem to be demanding quotes right now.

@Dennis I didn't restrict python's import statements on purpose :P

@YannVernier: bytearray is a good idea. But I'm not sure what you mean with imap.

If the argument iterables are of different length, map pads the shorter one with None but imap simply stops at the shortest; so map(n,K[1:],K[:-1]) can be reduced to imap(n,K[1:],K).

I just realized that the difference is quite moot; None won't match, so the result is the same.

I spent a couple minutes trying to figure out why you used from __builtin__ import whatever as W instead of W=whatever before going back and reading the question carefully :P

Ruby Regex (most popular flavours), 106 83 bytes
Because regex
^(?!.*(  |[abc]{2}|[def]{2}|[ghi]{2}|[jkl]{2}|[mno]{2}|[p-s]{2}|[tuv]{2}|[w-z]{2}))

I've just cut the middleman (Ruby) and made this a pure-regex solution. Works in a lot of flavours and only finds a match if the string does not contain two consecutive characters on the same button.

Can't you put that {2} outside the alternation, saving 22 bytes?

@NiettheDarkAbsol unfortunately not, because then it can pick different alternatives for the two repetitions.

Aah, of course. I knew there was a reason XD

Kudos for a readable, understandable, golfed solution!

Bash+coreutils, 49
tr a-z $[36#8g7e9m4ddqd6]7778888|grep -Pq '(.)\1'

Returns an exit code of 1 for TRUE and 0 for FALSE:
$ for s in "x" "aardvark" "ardvark" "flonk" "im codegolfing all day long" "i indulge in minimizing bytecount" "havent heard from you in a long time" "your silence was of undue permanence" "how are  you" "how are you"; do echo "./3310.sh <<< \"$s\" returns $(./3310.sh <<< "$s"; echo $?)"; done
./3310.sh <<< "x" returns 1
./3310.sh <<< "aardvark" returns 0
./3310.sh <<< "ardvark" returns 1
./3310.sh <<< "flonk" returns 0
./3310.sh <<< "im codegolfing all day long" returns 0
./3310.sh <<< "i indulge in minimizing bytecount" returns 1
./3310.sh <<< "havent heard from you in a long time" returns 0
./3310.sh <<< "your silence was of undue permanence" returns 1
./3310.sh <<< "how are  you" returns 0
./3310.sh <<< "how are you" returns 1
$

Very nice! This would be 46 characters in Perl: perl -pE'y/a-z/aaadddgggjjjmmmpppptttwwww/;$_=!/(.)\1/' <(echo "x") It prints 1 for true and nothing for false.

@chilemagic Go ahead and post the perl answer :).  Don't forget to add one to the score for using the -p command-line parameter (as per code-golf conventions).

I thought I could find a way to shorten aaadddgggjjjmmmpppptttwwww but I've given up.

@BenJackson I figured out a way.  We can actually use a string of any distinct characters - 11122233344455566667778888 will do.  By base 36 encoding the first 19 digits of this number, we can save 1 char!

APL(Dyalog), 24 23
~∨/2=/⌊¯13⌈.21-.31×⎕AV⍳⍞

∧/2≠/⌊¯13⌈.21-.31×⎕AV⍳⍞

Explanation
⍞: Takes string input from screen
⎕AV: This is the atomic vector which is bascially a string of all characters APL recognizes, which of course include all lowercase letters (index 18~43) and space (index 5)
⍳: IndexOf function. For many functions in APL that takes one or two scalar arguments, you can feed it an array in place of a scalar - APL will do the looping for you. So ⍳ returns a numeric array of indices.
.21-.31×: Times 0.31 and then subtract from 0.21. This is a little trick that maps letter on the same key (especially PQRS) to the same number (when rounded down to integers), except Z, which get mapped to its own group
¯13⌈: max with -13. This brings Z back to the group with WXY
⌊: Round down to integers
2≠/: Pairwise-≠. Returns a boolean array for each consecutive pair.
∧/: AND together all entries of the resulting array.

I was going to post something like this, but you beat me to it. Damn Z key! You can still shave 1 char off by saying ∧/2≠/ (all consecutive pairs are typed on different keys) instead of ~∨/2=/ (no consecutive pair is typed on the same key.) APL FTW!!!

Yes tkx. I was thinking "I should be able to shave off 1 char here why can't I do it OMGGGG!!!" But I got to go to class so I just post what I have. And, yes, DAMN Z KEY. Unfortunately I am on my phone so I can't edit it until later

And I made a conscious thought about De Morgan's Laws and still can't figure it out... How dumb

Good luck texting this to your friends. ;)

This looks very interesting. Is there any way to try this code without purchasing a Dyalog APL interpreter? The online interpreter I usually use doesn't seem to understand the dialect...

ngn/apl does not have the ⎕AV vector. It does have the ⎕UCS function, which gives the Unicode code point of every character, but you'd have to adjust the linear function .21-.31× because it gives different numbers. Then, apparently there's a bug with reading from ⍞ and returning a number (it returns undefined) so you might want to replace ⍞ with a literal string, eg. 'ardvark'

~∨/2=/ is ∄ x,y consecutive : x=y in that other inferior notation, while ∧/2≠/ is ∀ x,y consecutive : x≠y, so it comes from the negation of the universal quantifier, not De Morgan ;-) https://en.wikipedia.org/wiki/Universal_quantification#Negation

Isn't universal quantifier negation just an extension of De Morgan's Law to potentially infinite cases? I was doing finite test cases so I was thinking De Morgan.

@Tobia: Thanks, but ⎕AV is precisely what I was interested in. My approach is still a little clumsy compared to a simple linear function.

Perl - 44
This is basically a Perl adaptation of @DigitalTrauma's answer posted with his permission. Shaved off 2 characters thanks to @KyleStrand.
y/b-y/aadddgggjjjmmmpppptttzzz/;$_=!/(.)\1/

43 characters + 1 for -p flag. y/// is the same as tr///. It prints 1 for true and nothing for false. I can post a detailed explanation if requested.
Example run:
perl -pE'y/b-y/aadddgggjjjmmmpppptttzzz/;$_=!/(.)\1/' <(echo "x")

Perl - 81
$s=join"]{2}|[",qw(abc def ghi jkl mno p-s tuv w-z);say/^(?!.*(  |[$s]{2}))/?1:0

+1 for -n flag. It works by using join to create the regex (same one as Martin's), which shaves of a few bytes.
Example run:
perl -nE'$s=join"]{2}|[",qw(abc def ghi jkl mno p-s tuv w-z);say/^(?!.*(  |[$s]{2}))/?1:0' <(echo "your silence was of undue permanence")

Couldn't you shave off two characters from the Perl solution by letting a and z remain untransliterated? y/b-y/aadddgggjjjmmmpppptttzzz/;$_=!/(.)\1/ Also, this won't handle spaces, will it?

...oh, right, two spaces in a row is already two identical characters in a row. My bad.

@KyleStrand nice call on letting a and z remain the same. Updated answer!

JavaScript - 159 156 bytes
function g(s){p=n=-1;for(i=0;i!=s.length;i++){p=n;n=s.charCodeAt(i);n-=97;if(n>17)n--;if(n>23)n--;if(p==-1)continue;if(~~(p/3)==~~(n/3))return 0;}return 1;}

Returns 1 for truthy and 0 for falsy.
If only I could get rid of the keywords.

At least you can get rid of some whitespaces and if's :)
141 : function g(s){p=n=-1;for(i=0;i<s.length;i++){p=n;n=s.charCodeAt(i)-97;n>17&&n--;n>23&&n--;if(~p)continue;if(~(p/3)==~(n/3))return 0}return 1}

You use lots of interesting things in your answer that I haven't seen before. I usually write in C++ but I thought I'd give JS a shot as it's quicker to test online.

I only found this place today and thought I'd give it a shot. My next try will be superior :D

You can make your code a character shorter by replacing the != in the for loop by a <.

Yes that was in Optimizer's optimisations :) what's the etiquette on using people's suggestions in my answer? Now that there is another JavaScript entry that I can beat by accepting those modifications.

c, 74 bytes
main(c,d,r){for(;~(c=getchar());r*=d!=c/3,d=c/3)c-=--c/'p'*(c-'k')/7;c=r;}

Returns a non-zero exit status for TRUE and 0 for FALSE:
$ for s in "x" "aardvark" "ardvark" "flonk" "im codegolfing all day long" "i indulge in minimizing bytecount" "havent heard from you in a long time" "your silence was of undue permanence" "how are  you" "how are you"; do echo "./3310 <<< \"$s\" returns $(./3310 <<< "$s"; echo $?)"; done
./3310 <<< "x" returns 40
./3310 <<< "aardvark" returns 0
./3310 <<< "ardvark" returns 216
./3310 <<< "flonk" returns 0
./3310 <<< "im codegolfing all day long" returns 0
./3310 <<< "i indulge in minimizing bytecount" returns 72
./3310 <<< "havent heard from you in a long time" returns 0
./3310 <<< "your silence was of undue permanence" returns 232
./3310 <<< "how are  you" returns 0
./3310 <<< "how are you" returns 8
$

You can save 3 bytes by changing your while to for(;c=~getchar();d=c/3), and another byte by changing your first if to a ?: operator.

@Allbeert - Thanks.  The parenthesis around c=getchar() are required though because ~ has higher precedence than =.  Still, I'll take the other two bytes :)

For the last bit, does something like exit(d!=c/3); instead of if(d==c/3)exit(0); work?

@professorfish That would make the exit at that point unconditional, which I don't want

You can save one character with r*=d^c/3

@Alchymist I tried that but it doesn't work, I think because the result of the ^ can be greater than 1, and the *= happens for every character, so r overflows after a few characters giving an incorrect value.

Good point!  Overflow shouldn't matter per se but here you will keep multiplying by values with trailing zeros until you overflow to r=0.

Ruby 1.8, 89 83 81 78 bytes
p$*[0].chars.map{|c|c=c[0];(c-c/?p-c/?w-1)/3}.each_cons(2).map{|a,b|a!=b}.all?

Here is another submission. To my shame, it beats the regex. :(
This takes the string via command-line argument and prints a boolean.
As for the algorithm, I'm shifting down the letters after p by one and after z by two, and then I check that there are no collisions after integer division by 3.
PS: This is the first time, that using Ruby 1.8 shortened the code (due to the shorter way to get character codes).

Cobra - 80
def f(s)
    for c in s
        for x in 9,if' adgjmptw'[x]>c,break
        t,f=x,t<>x
    print f

JavaScript (ES6) 66 74
F=s=>[...s].every(c=>[...' adgjmptw'].map(x=>s+=c<x,w=s,s=0)|s!=w)

The inner loop find the group for each character. Conceptually is a 'reduce' but 'map' is shorter. The outer loop compare the group of consecutive chars and exits with false if they are equal.
Test In Firefox/Firebug console
;["x","aardvark","ardvark","flonk","im codegolfing all day long",
"i indulge in minimizing bytecount","havent heard from you in a long time",
"your silence was of undue permanence","how are  you","how are you"]
.forEach(x=>console.log(x + ' -> ' + F(x)))

Output
x -> true
aardvark -> false
ardvark -> true
flonk -> false
im codegolfing all day long -> false
i indulge in minimizing bytecount -> true
havent heard from you in a long time -> false
your silence was of undue permanence -> true
how are  you -> false
how are you -> true

You can do .some instead of every. Because even if it fails one time, the answer is falsy.

@Optimizer some and every are interchangeble, fiddling with the conditions. But here simply put some instead of every will not work, try it.

Hmm, you are right. I need to understand your logic first.

Please don't mind if I start using this [...s].every trick in my golfs :)

Perl, 83 bytes
$_=<>;chop;map{$_=ord;$_=($_-$_/112-$_/119-1)/3;die 0 if$l==$_;$l=$_}split//;die 1

Making heavy abuse of $_ in Perl.

As you can observe, is allowed to pass command-line parameters to the interpreter, just you have to count the extra parameters. (The bare minimum needed to access the code, -e in Perl, is free.) 71 characters alternative with command-line parameters: perl -nlaF -e 'map{$_=ord;$_=($_-$_/112-$_/119-1)/3;die 0 if$l==$_;$l=$_}@F;die 1'.

@manatwork you don't need the -l, but it looks good!

@chilemagic, I just tried to reproduce the original code's equivalent, so I added -l as replacement for chop. But of course, you are right.

Thanks @manatwork, I didn't even think to making use of the command line options for Perl.

Two tasks are tricky in Python; detecting chains, and assigning the groups. Both can be assisted using numpy, but it is not in the standard library.
Python 2 (only standard library) - 59 chars function
from itertools import imap as M
from __builtin__ import bytearray as A, all as E
from operator import ne as D, not_ as N
from re import S, sub as X, search as F

# 68
#def f(s):
# g=[(n-n/115-n/61)/3for n in A(s)]
# return E(M(D,g,g[1:]))

# 67 with regex via regex
#f=lambda s:N(F(X('(\S)(.)',r'|[\1-\2]{2}','  acdfgijlmopstvwz'),s))

# 59 slightly optimized ordinal classifier and regex sequence detector
f=lambda s:N(F(r'(.)\1',A((n-n/23-n/30)/3for n in A(s)),S))

# 69 using itertools.groupby
#from itertools import groupby as G
#from __builtin__ import sum as S, len as L
#f=lambda s:N(S(L(A(g))-1for _,g in G((n-n/115-n/61)/3for n in A(s))))

Python 2 (only standard library) - 53 chars stdin to exit value
Here I abuse the fact that issubclass(bool,int), so changing all() to any() gets me a valid exit value, shaving off the not() from the return value. The removal of function overhead made the regex versions fall behind in size.
from itertools import groupby as G, imap as M
from __builtin__ import bytearray as A, any as E
from __builtin__ import raw_input as I
from sys import exit as Q
from operator import eq as S

g=[(n-n/23-n/30)/3for n in A(I())]
Q(E(M(S,g,g[1:])))

J - 42 char
Function taking string on the right.
*/@(2~:/\(I.4 3 4 1,~5#3){~(u:97+i.26)&i.)

First we map the alphabet (u:97+i.26) into the numbers 0 through 25, all other characters (including spaces) going to 26 (i.). Then we map ({~) the first three elements map to the first key, the next three to the next key, and so on through the keys of the phone pad, making sure to map the space/other punctuation to a separate key at the end. (4 3 4 1,~5#3 is equal to 3 3 3 3 3 4 3 4 1 and I. turns that into a 27-item array where the first three are key 1, etc.) Then we check for pairwise inequality (2~:/\) and AND all the results together (*/).
   */@(2~:/\(I.4 3 4 1,~5#3){~(u:97+i.26)&i.) 'i indulge in minimizing bytecount'
1
   f =: */@(2~:/\(I.4 3 4 1,~5#3){~(u:97+i.26)&i.)
   f 'im codegolfing all day long'
0
   f '*/@(2~:/\(I.4 3 4 1,~5#3){~(u:97+i.26)&i.)'  NB. no -3 bonus :(
0

Racket, 119
(define(f t)(for*/and([s(map ~a'(abc def ghi jkl mno pqrs tuv wxyz))][i s][j s])(not(regexp-match(format"~a~a"i j)t))))

Ungolfed (combinatoric regexing):
(define(f t)
  (for*/and([s (map ~a '(abc def ghi jkl mno pqrs tuv wxyz))]
            [i s]
            [j s])
    (not (regexp-match (format "~a~a" i j) t))))

ES6, JavaScript 89 70 characters
I know its not a winner because when coming to handy operations like getting ASCII value of character, JS puts a lot of bloat (.charCodeAt()).
N=s=>[...s].every(c=>l-(l=(c.charCodeAt()-(c>"r")-(c>"y")-1)/3|0),l=1)

Run it in Web Console of latest Firefox.
Usage:
N("testing if this works")

The function returns either true or false.
EDIT: Golfed a lot using the [...x].every trick learned from @edc65 (Thanks!)
I will try to golf it more :)

JavaScript - 152
Not a winner but I gave it a shot. Beats @Lozzaaa by 4 bytes as of posting time :)
function m(a){c="abc-def-ghi-jkl-mno-pqrstuv-wxyz";j=a.split("");for(z in j)if(j[z]=Math.floor(c.indexOf(j[z])/4),0!=z&&j[z-1]==j[z])return 0;return 1};

Passes all the tests.
Takes advantage of JS's lack of typing to make a multi type array, and it takes advantage of indexOf returning -1 for space support.
Usage:
m("string here")

Assumes lowercase alphabetic characters and spaces only. Returns 1 for true, 0 for false.
Maybe if I knew ES6 I could try the second challenge...

"if only ... " - Did you see my answer ? :P

Yes I did. I don't know ES6 (yet), sadly. However, this was interesting to make.

Yeah, your solution using an interesting approach.

GML (Game Maker Language), 149
s=argument0p=n=-1for(i=0;i<string_length(s);i++){p=n;n=string_char_at(s,i)-97;x=n>17&&n--;x=n>23&&n--;if(!p)x=1if(!(p/3)=!(n/3))x=0}show_message(x)

Python 3 - 152 chars
Not the shortest I could go, but it'll do for now
k=['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz',' ']
x=input()
l=2>1
for i in range(len(x)-1):
 for j in k:
  if x[i+1] in j and x[i] in j:l=1>2
print(l)


text:
Tips for golfing in OCaml
Inspired from the assortment of other 'Tips for golfing in language xyz'. As usual, please only suggest tips that are specific to OCaml and not programming in general. One tip per answer please.

Use functions instead of match
let rec f=function[]->0|_::t->1+f t

is shorter than
let rec f x=match x with[]->0|_::t->1+f t

Never use begin […] end
This:
begin […] end

is always synonymous with this:
([…])

Define several variables or functions at once
Thanks to tuples, you can define several variables at once. And as functions are first-class citizens…:
let f,g=(fun x->x+1),fun x->2*x

You can’t, however, write:
let f,g=(fun x->x+1),fun x->2*f x

Error: Unbound value f

Unfortunately, you can’t avoid the issue by using rec:
let rec f,g=(fun x->x+1),fun x->2*f x

Error: Only variables are allowed as left-hand side of let rec

Exploit curryied functions
Functions in OCaml are curryied. It might be useful to exploit that fact sometimes.
let n y=f x y

can be written
let n=f x

If you need arithmetic operations, you can surround them with parentheses so they behave like standard, prefix functions. (+), (-), …
let n=(+)1;;
n 3;;

- : int = 4

downto
If you're not sure how to loop downwards, downto is usually the one to go for. Instead of:
for i=0 to 1000 do
Printf.printf"%d
"(1000-i)
done

You can do:
for i=1000 downto 0 do
Printf.printf"%d
"i
done

you could also do something like for i= -1000 to 0. Also, your syntax for these programs is missing the do done parts

print_string
Instead of the usual Printf.printf"", you can actually use the below (ONLY for strings, no formatting):
print_string"wassup"

Which is 1 byte shorter than:
Printf.printf"wassup"

Is this really worth a tip? It isn't normal to use Printf.printf for raw strings anyway

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:
Catenary Between Two Points (Hanging Chain)
This is one of several challenges left for the community by Calvin's Hobbies.
The curve that an idealised hanging rope or chain makes is a catenary.

Image by Bin im Garten, via Wikimedia Commons. Used under the CC-By-SA 3.0 licence.
Write a program that will draw a catenary, as an image, in quadrant 1 of the plane given two points (x1,y1), (x2,y2), and the "rope length" L. L will be greater than the distance between the two points.
You must also draw axes on the left and bottom sides of the image (400x400 px min) for scale. Only draw the quadrant from x and y in range 0 to 100. (You may assume the points are in range.)
Dots, or something similiar, should be drawn at the (x1,y1), (x2,y2) endpoints to distinguish them. The curve should only be drawn in the space between these points.

How precise do we have to be? Does the image have to be anti-aliased? How wide must/can the line be?

We also assume that the curve itself (not just the points) is in range, right? Or would we draw two arcs cut by the axis if it goes below that?

@Sparr The image does not have to be anti-aliased. The line must be at least 1px thick. The catenary should be as accurate as your language's floating point arithmetic can do.

@Geobits You may also assume the curve is in range.

I was going to do this until I realized that the math might be slightly more complex than my current pre-calculus. Maybe next year.

What should the horizontal force be?

@BetaDecay I don't know what that is. Lets say its 0.

@MartinBüttner I still don't understand it - I had thought that with the two points and the length of rope, there would only be one catenary that resulted. All I can say is that the horizontal force should be such that it draws the same kind of curves as this.

Just look up the Wikipedia article you linked to. The section on the mathematical description explains what the horizontal force is needed for.

@IngoBürk In the image you're referring to the centenaries clearly are not the same length. The question asks that the length of the curve between the points is L. If you let out the a=1/2 line in that image until it was the same length as the a=3 line, the curves would match up. The only catenary of the same length between those points is the up facing mirrored version.

@VonIlya It might be good to say that L will never be less than the distance between the endpoints.

Can we assume the given points will be distinct? (Specifically their x values)

@stokastic Yes.

Before I refine my answer, a couple of clarifications: 1.Can we assume the points will be given left to right (lower x value first) or can they be reversed? 2. I think I have misinterpreted the rules regarding the sizing. I have drawn my axes as 400x400 graphics units (which I have realised is only 200x200 pixels.) I will resize to 800x800 graphics units (400x400 pixels) and scale so that this corresponds to 100x100 mathematical units (x and y in range 0-100.)

@steveverrill 1. Yes. 2 Also Yes

@VonIlya 1. Is that yes we can assume the points will always be given left to right and not reversed?

@steveverrill Yes

Python + NumPy + Matplotlib, 1131
Just to get us started, here's an attempt that uses no knowledge of calculus or physics other than the fact that the catenary minimizes the energy of a chain. Hey, my algorithm may not be efficient, but at least it's not implemented efficiently either!
import math
import random
import numpy as np
import matplotlib.pyplot as plt
length, x0, y0, x1, y1 = input(), input(), input(), input(), input()
chain = np.array([[x0] + [length / 1000.]*1000, [y0] + [0.] * 1000])
def rotate(angle, x, y):
 return x * math.cos(angle) + y * math.sin(angle), -x * math.sin(angle) + y  * math.cos(angle)
def eval(chain, x1, y1):
 mysum = chain.cumsum(1)
 springpotential = 1000 * ((mysum[0][-1] - x1) ** 2 + (mysum[1][-1] - y1)  ** 2)
 potential = mysum.cumsum(1)[1][-1]
 return springpotential + potential
def jiggle(chain, x1, y1):
 for _ in xrange(100000):
  pre = eval(chain, x1, y1)
  angle = random.random() * 2 * math.pi
  index = random.randint(1,1000)
  chain[0][index], chain[1][index] = rotate(angle, chain[0][index], chain[1][index])
  if( pre < eval(chain, x1, y1)):
   chain[0][index], chain[1][index] = rotate(-angle, chain[0][index], chain[1][index])
jiggle(chain, x1, y1)
sum = chain.cumsum(1)
x1 = 2 * x1 - sum[0][-1]
y1 = 2 * y1 - sum[1][-1]
jiggle(chain, x1, y1)
sum = chain.cumsum(1)
plt.plot(sum[0][1:], sum[1][1:])
plt.show()

BBC Basic, 300 ASCII characters, tokenised filesize 260
  INPUTr,s,u,v,l:r*=8s*=8u*=8v*=8l*=8z=0REPEATz+=1E-3UNTILFNs(z)/z>=SQR(l^2-(v-s)^2)/(u-r)a=(u-r)/2/z
  p=(r+u-a*LN((l+v-s)/(l-v+s)))/2q=(v+s-l*FNc(z)/FNs(z))/2MOVE800,0DRAW0,0DRAW0,800CIRCLEu,v,8CIRCLEr,s,8FORx=r TOu
    DRAW x,a*FNc((x-p)/a)+q
  NEXT
  DEFFNs(t)=(EXP(t)-EXP(-t))/2
  DEFFNc(t)=(EXP(t)+EXP(-t))/2

Emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html
This has obviously been solved before, so the first thing I did was look what others have done.
The equation of a catenary centred at the origin is simply y=a*cosh(x/a). It becomes slightly more complicated if it is not centred at the origin.
Various sources say that if the length and endpoints are known the value for a must be determined numerically. There is an unspecified parameter h in the wikipedia article. So I found another site and basically followed the method here: http://www.math.niu.edu/~rusin/known-math/99_incoming/catenary
BBC Basic does not have sinh and cosh built in, so I defined two functions at the end of the program to calculate them using EXP
coordinates for lefthand point must be supplied before righthand point, OP confirmed this is OK. Length is given last. Values can be separated by commas or newlines.
Ungolfed code
  INPUT r,s,u,v,l

  REM convert input in range 0-100 to graphic coordinates in range 0-800
  r*=8 s*=8 u*=8 v*=8 l*=8

  REM solve for z numerically
  z=0
  REPEAT
    z+=1E-3
  UNTIL FNs(z)/z>=SQR(l^2-(v-s)^2)/(u-r)

  REM calculate the curve parameters
  a=(u-r)/2/z
  p=(r+u-a*LN((l+v-s)/(l-v+s)))/2
  q=(v+s-l*FNc(z)/FNs(z))/2

  REM draw axes, 800 graphics units long = 400 pixels long (2 graphics units per pixel)
  MOVE 800,0
  DRAW 0,0
  DRAW 0,800

  REM draw markers at end and beginning of curve (beginning last, so that cursor is in right place for next step)
  CIRCLE u,v,8
  CIRCLE r,s,8

  REM draw curve from beginning to end
  FORx=r TOu
    DRAW x,a*FNc((x-p)/a)+q
  NEXT

  REM definitions of sinh and cosh
  DEF FNs(t)=(EXP(t)-EXP(-t))/2
  DEF FNc(t)=(EXP(t)+EXP(-t))/2

Python 2.7 + matplotlib, 424
Run as
python thisscript.py [length] [x0] [y0] [x1] [y1]

If I can assume that x0 is always smaller than x1 character count reduces to 398
from numpy import *
from pylab import *
from scipy.optimize import *
import sys
c=cosh
l,p,q,u,w=map(float,sys.argv[1:])
if p>u:
 p,q,u,w=u,w,p,q
h=u-p
v=w-q
a=brentq(lambda a:(2.*h/a*sinh(0.5*a))**2-l**2-v**2,1e-20,600)
b=brentq(lambda b:c(a*(1.-b))-c(a*b)-a*v/h,-600/a,600/a)
r=linspace(p,u,100)
plot([p,u],[q,w],'ro')
plot(r,h/a*c(((r-p)/h-b)*a)-h/a*c(a*b)+q,'k-')
gca().set_xlim((0,100))
gca().set_ylim((0,100))
show()

The magic number 600 you see appearing in some places is due to the fact that cosh(x) and sinh(x) start overflowing around x=710 (so 600 to keep some margin)

 Basically I solve the problem in the frame where the catenary goes
 trough (0,0) and (x1-x0,(y1-y0)/(x1-x0)) and then remap to the original
 frame. This improves the numerical stability a lot.

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


text:
Restricted memory optimization
The edit (or Levenshtein) distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other. If the two strings have length n each, it is well known that this can be done in O(n^2) time by dynamic programming. The following Python code performs this calculation for two strings s1 and s2.
def edit_distance(s1, s2):
    l1 = len(s1)
    l2 = len(s2)

    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
      matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
      for sz in range(0,l1):
        if s1[sz] == s2[zz]:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
        else:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
    return matrix[l2][l1]

In this task you have to get as close are you can to computing the edit distance but with a severe memory restriction. Your code is allowed to define one array containing 1000 32-bit integers and this is to be the only temporary storage you use in your computation.  All variables and data structures are to be contained in this array. In particular, you would not be able to implement the algorithm above as for strings of length 1000 as it would require you to store at least 1,000,000 numbers. Where your language doesn't naturally have 32 bit integers (for example Python) you simply need to make sure you never store a number larger than 2^32-1 in the array.
You may read in the data using any standard library of your choice without worrying about the memory restrictions in that part. In order to make the competition fair for the main part of your code, you may only use operations that are functionally equivalent to those in the C programming language and cannot use any external libraries.
To be extra clear, the memory to store the input data or used by your language's interpreter, JVM etc. does not count towards your limit and you may not write anything to disk.  You must assume the input data is read-only when in memory so you can't reuse that to gain more working space.
What do I have to implement?
Your code should read in a file in the following format. It will have three lines. The first line is the true edit distance. The second is string 1 and the third is string 2.   I will test it with the sample data at https://bpaste.net/show/6905001d52e8 where the strings have length 10,000 but it shouldn't be specialised for this data. It should output the smallest edit distance it can find between the two strings.
You will also need to prove your edit distance actually comes from a valid set of edits. Your code should have a switch which turns it into a mode that may use more memory (as much as you like) and outputs the edit operations that give your edit distance.
Score
Your score will be the (optimal edit distance/divided by the edit distance you find) * 100.  To start things off, notice that you can get a score by just counting the number of mismatches between the two strings.
You can use any language you like which is freely available and easy to install in Linux.
Tie break
In the case of a tie-break, I will run your code on my Linux machine and the fastest code wins.

Would for(int i=0;i<=5;i++) be allowed because it's storing data in i?

@BetaDecay  Yes although to follow the rules more closely you would do something like { uint32_t foo[1000]; for (foo[0] = 0; foo[0] < 5; ++foo[0]) printf("%d ", foo[0]); }  This is assuming your array of 32 bit integers will be called foo.

What is the point of having the true edit distance in the file? Is the program actually supposed to read it? Or (what seems more sensible) is it just in there for you to see how successful the program was?

@feersum Exactly. It's just there so you can see what your score is easily.

https://bpaste.net/show/6905001d52e8 gives me a 404 page!

C++, Score 92.35
Estimation Algorithm: The algorithm finds the first place the two string differ, and then tries all possible N operation permutations (insert, delete, replace - characters that match are skipped without consuming an operation). It scores each possible set of operations based on how much farther that set of operations successfully matches the two strings, plus how much it causes the string lengths to converge. After determining the highest-scoring set of N operations, the first operation in the set is applied, the next mismatch is found, and the process repeats until the end of the string is reached.
The program tries all values of N from 1-10 and selects the level that gave the best results. N=10 is generally the best now that the scoring method takes the string length into consideration. Higher values of N would probably be even better, but take exponentially more time.
Memory Usage: Since the program is purely iterative, it needs very little memory. Only 19 variables are used to track the program state. These are set by #defines to act as global variables.
Usage: The program is used the same as feersum's: the first parameter is assumed to be the file, and any additional parameters indicate that the edits should be shown. The program always prints the estimated edit distance, and the score.
Verification Output: The verification output it formatted in three rows:
11011111100101100111100110100 110 0 0000   0 01101
R I          IR     R        D   D D    DDD D     D
01 1111110010 0001110001101000110101000011101011010

The top row is the target string, the middle is the operations, and the bottom is the string being edited. Spaces in the operation line indicate that the characters match. 'R' indicates that the edit string has it's character in that position replaced with the target string's character. 'I' indicates that the edit string has the target string's character inserted at that position. 'D' indicates that the edit string has it's character in that position deleted. The edit and target strings have spaces inserted when the other has a character inserted or deleted so they line up.
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <fstream>

int memory[1000];
#define first (*(const char **)&memory[0])
#define second (*(const char **)&memory[1])
#define block_ia memory[2]
#define block_ib memory[3]
#define block_n memory[4]
#define block_op memory[5]
#define block_o memory[6]
#define block_x memory[7]
#define n memory[8]
#define opmax memory[9]
#define best_op memory[10]
#define best_score memory[11]
#define score memory[12]
#define best_counter memory[13]
#define la memory[14]
#define lb memory[15]
#define best memory[16]
#define bestn memory[17]
#define total memory[18]

// verification variables
char printline1[0xffff]={};
char *p1=printline1;
char printline2[0xffff]={};
char *p2=printline2;
char printline3[0xffff]={};
char *p3=printline3;

// determine how many characters match after a set of operations
int block(){
    block_ia=0;
    block_ib=0;
    for ( block_x=0;block_x<block_n;block_x++){
        block_o = block_op%3;
        block_op /= 3;
        if ( block_o == 0 ){ // replace
            block_ia++;
            block_ib++;
        } else if ( block_o == 1 ){ // delete
            block_ib++;
        } else { // insert
            if ( first[block_ia] ){
                block_ia++;
            }
        }
        while ( first[block_ia] && first[block_ia]==second[block_ib] ){ // find next mismatch
            block_ia++;
            block_ib++;
        }
        if ( first[block_ia]==0 ){
            return block_x;
        }
    }
    return block_n;
}

// find the highest-scoring set of N operations for the current string position
void bestblock(){
    best_op=0;
    best_score=0;
    la = strlen(first);
    lb = strlen(second);
    block_n = n;
    for(best_counter=0;best_counter<opmax;best_counter++){
        block_op=best_counter;
        score = n-block();
        score += block_ia-abs((la-block_ia)-(lb-block_ib));
        if ( score > best_score ){
            best_score = score;
            best_op = best_counter;
        }
    }
}

// prepare edit confirmation record
void printedit(const char * a, const char * b, int o){
    o%=3;
    if ( o == 0 ){ // replace
        *p1 = *a;
        if ( *b ){
            *p2 = 'R';
            *p3 = *b;
            b++;
        } else {
            *p2 = 'I';
            *p3 = ' ';
        }
        a++;
    } else if ( o == 1 ){ // delete
        *p1 = ' ';
        *p2 = 'D';
        *p3 = *b;
        b++;
    } else { // insert
        *p1 = *a;
        *p2 = 'I';
        *p3 = ' ';
        a++;
    }
    p1++;
    p2++;
    p3++;
    while ( *a && *a==*b ){
        *p1 = *a;
        *p2 = ' ';
        *p3 = *b;
        p1++;
        p2++;
        p3++;
        a++;
        b++;
    }
}

int main(int argc, char * argv[]){

    if ( argc < 2 ){
        printf("No file name specified\n");
        return 0;
    }

    std::ifstream file(argv[1]);
    std::string line0,line1,line2;
    std::getline(file,line0);
    std::getline(file,line1);
    std::getline(file,line2);

    // begin estimating Levenshtein distance
    best = 0;
    bestn = 0;
    for ( n=1;n<=10;n++){ // n is the number of operations that can be in a test set
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            first++;
            second++;
        }
        total=0;
        while ( *first && *second ){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            total ++;
            first += block_ia;
            second += block_ib;
        }
        // when one string is exhausted, all following ops must be insert or delete
        while(*second){
            total++;
            second++;
        }
        while(*first){
            total++;
            first++;
        }
        if ( !best || total < best ){
            best = total;
            bestn = n;
        }
    }
    // done estimating Levenshtein distance

    // dump info to prove the edit distance actually comes from a valid set of edits
    if ( argc >= 3 ){
        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        n = bestn;
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            *p1 = *first;
            *p2 = ' ';
            *p3 = *second;
            p1++;
            p2++;
            p3++;
            first++;
            second++;
        }
        while ( *first && *second){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            printedit(first,second,best_op);
            first += block_ia;
            second += block_ib;
        }
        while(*second){
            *p1=' ';
            *p2='D';
            *p3=*second;
            p1++;
            p2++;
            p3++;
            second++;
        }
        while(*first){
            *p1=*first;
            *p2='I';
            *p3=' ';
            p1++;
            p2++;
            p3++;
            first++;
        }

        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        int ins=0;
        int del=0;
        int rep=0;
        while ( *p1 ){
            int a;
            for ( a=0;a<79&&p1[a];a++)
                printf("%c",p1[a]);
            printf("\n");
            p1+=a;
            for ( a=0;a<79&&p2[a];a++){
                ins += ( p2[a] == 'I' );
                del += ( p2[a] == 'D' );
                rep += ( p2[a] == 'R' );
                printf("%c",p2[a]);
            }
            printf("\n");
            p2+=a;
            for ( a=0;a<79&&p3[a];a++)
                printf("%c",p3[a]);
            printf("\n\n");
            p3+=a;
        }
        printf("Best N=%d\n",bestn);
        printf("Inserted = %d, Deleted = %d, Replaced=%d, Total = %d\nLength(line1)=%d, Length(Line2)+ins-del=%d\n",ins,del,rep,ins+del+rep,line1.length(),line2.length()+ins-del);
    }

    printf("%d, Score = %0.2f\n",best,2886*100.0/best);
    system("pause");
    return 0;
}

C++   75.0
The program is designed to work with arbitrary text strings. They can be of any different lengths as long as neither exceeds 13824 characters. It uses 1,897 16-bit integers, which is equivalent to 949 32-bit integers. At first I was writing it in C, but then realized there was no function for reading a line.
The first command-line argument should be a filename. If a second argument exists, a summary of the edits is printed. The first line in the file is ignored while the second and third are the strings.
The algorithm is a doubly blocked version of the usual algorithm. It performs basically the same number of operations, but is of course much less accurate, since if a common subsequence gets split over the edge of a block, much of the potential savings are lost.
#include <cstring>
#include <inttypes.h>
#include <iostream>
#include <fstream>

#define M 24
#define MAXLEN (M*M*M)
#define SETMIN(V, X) if( (X) < (V) ) { (V) = (X); }
#define MIN(X, Y) ( (X) < (Y) ? (X) : (Y) )

char A[MAXLEN+1], B[MAXLEN+1];
uint16_t d0[M+1][M+1], d1[M+1][M+1], d2[M+1][M+1];

int main(int argc, char**argv)
{

    if(argc < 2)
        return 1;

    std::ifstream fi(argv[1]);

    std::string Astr, Bstr;
    for(int i = 3; i--;)
        getline(fi, i?Bstr:Astr);
    if(!fi.good()) {
        printf("Error reading file");
        return 5;
    }
    if(Astr.length() > MAXLEN || Bstr.length() > MAXLEN) {
        printf("String too long");
        return 7;
    }

    strcpy(A, Astr.c_str());
    strcpy(B, Bstr.c_str());

    uint16_t lA = Astr.length(), lB = Bstr.length();
    if(!lA || !lB) {
        printf("%d\n", lA|lB);
        return 0;
    }
    uint16_t nbA2, nbB2, bA2, bB2, nbA1, nbB1, bA1, bB1, nbA0, nbB0, bA0, bB0; //block, number of blocks
    uint16_t iA2, iB2, iA1, iB1, jA2, jB2, jA1, jB1; //start, end indices of block

    nbA2 = MIN(M, lA);
    nbB2 = MIN(M, lB);
    for(bA2 = 0; bA2 <= nbA2; bA2++) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        for(bB2 = 0; bB2 <= nbB2; bB2++) {
            if(!(bA2|bB2)) {
                d2[0][0] = 0;
                continue;
            }
            iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
            d2[bA2][bB2] = ~0;
            if(bB2)
                SETMIN(d2[bA2][bB2], d2[bA2][bB2-1] + (jB2-iB2));
            if(bA2)
                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2] + (jA2-iA2));

            if(bA2 && bB2) {
                nbA1 = MIN(M, jA2-iA2);
                nbB1 = MIN(M, jB2-iB2);
                for(bA1 = 0; bA1 <= nbA1; bA1++) {
                    iA1 = iA2 + (jA2-iA2) * (bA1-1)/nbA1, jA1 = iA2 + (jA2-iA2) * bA1/nbA1;
                    for(bB1 = 0; bB1 <= nbB1; bB1++) {
                        if(!(bA1|bB1)) {
                            d1[0][0] = 0;
                            continue;
                        }
                        iB1 = iB2 + (jB2-iB2) * (bB1-1)/nbB1, jB1 = iB2 + (jB2-iB2) * bB1/nbB1;
                        d1[bA1][bB1] = ~0;
                        if(bB1)
                            SETMIN(d1[bA1][bB1], d1[bA1][bB1-1] + (jB1-iB1));
                        if(bA1)
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1] + (jA1-iA1));

                        if(bA1 && bB1) {
                            nbA0 = jA1-iA1;
                            nbB0 = jB1-iB1;
                            for(bA0 = 0; bA0 <= nbA0; bA0++) {
                                for(bB0 = 0; bB0 <= nbB0; bB0++) {
                                    if(!(bA0|bB0)) {
                                        d0[0][0] = 0;
                                        continue;
                                    }
                                    d0[bA0][bB0] = ~0;
                                    if(bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0][bB0-1] + 1);
                                    if(bA0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0] + 1);
                                    if(bA0 && bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0-1] + (A[iA1 + nbA0 - 1] != B[iB1 + nbB0 - 1]));
                                }
                            }
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1-1] + d0[nbA0][nbB0]);
                        }
                    }
                }

                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2-1] + d1[nbA1][nbB1]);
            }
        }
    }
    printf("%d\n", d2[nbA2][nbB2]);

    if(argc == 2)
        return 0;

    int changecost, total = 0;
    for(bA2 = nbA2, bB2 = nbB2; bA2||bB2; ) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
        if(bB2 && d2[bA2][bB2-1] + (jB2-iB2) == d2[bA2][bB2]) {
            total += changecost = (jB2-iB2);
            char tmp = B[jB2];
            B[jB2] = 0;
            printf("%d %d deleted {%s}\n", changecost, total, B + iB2);
            B[jB2] = tmp;
            --bB2;
        } else if(bA2 && d2[bA2-1][bB2] + (jA2-iA2) == d2[bA2][bB2]) {
            total += changecost = (jA2-iA2);
            char tmp = B[jA2];
            A[jA2] = 0;
            printf("%d %d inserted {%s}\n", changecost, total, A + iA2);
            A[jA2] = tmp;
            --bA2;
        } else {
            total += changecost = d2[bA2][bB2] - d2[bA2-1][bB2-1];
            char tmpa = A[jA2], tmpb = B[jB2];
            B[jB2] = A[jA2] = 0;
            printf("%d %d changed {%s} to {%s}\n", changecost, total, B + iB2, A + iA2);
            A[jA2] = tmpa, B[jB2] = tmpb;
            --bA2, --bB2;
        }
    }

    return 0;
}

Thank you for being the first answerer! What is your score?

@Lembik OK, I have calculated the score, assuming it is based only on the one example.

This is great. Do you think it's possible to get a much higher score?

Python, 100
I did manage to calculate the edit distance perfectly in the allotted memory limit. Sadly, this entry violates two rules of the challenge, in letter if not in spirit.
First, I have not actually stored my data in 1000 32-bit ints. For 10000-character strings, my program creates two 10000-element arrays that will only contain +1, 0, or -1. At 1.585 bits per ternary number, it would be possible to pack those 20000 trits into 31700 bits, leaving 300 bits as more than enough for my 7 remaining 16-bit integers.
Second, I have not implemented the required mode for showing edits. I have, alternately, implemented a mode that prints out the full edit matrix. It is absolutely possible to calculate the edit path from that matrix, but I don't have time right now to implement it.
#!/usr/bin/env python

import sys

# algorithm originally from
# https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows

print_rows = False
if len(sys.argv) > 2:
    print_rows = True

def LevenshteinDistance(s, t):
    # degenerate cases
    if s == t:
        return 0
    if len(s) == 0:
        return len(t)
    if len(t) == 0:
        return len(s)

    # create two work vectors of integer distance deltas

    # these lists will only ever contain +1, 0, or -1
    # so they COULD be packed into 1.585 bits each
    # 15850 bits per list, 31700 bits total, leaving 300 bits for all the other variables

    # d0 is the previous row
    # initialized to 0111111... which represents 0123456...
    d0 = [1 for i in range(len(t)+1)]
    d0[0] = 0
    if print_rows:
        row = ""
        for i in range(len(t)+1):
            row += str(i) + ", "
        print row

    # d1 is the row being calculated
    d1 = [0 for i in range(len(t)+1)]

    for i in range(len(s)-1):
        # cummulative values of cells north, west, and northwest of the current cell
        left = i+1
        upleft = i
        up = i+d0[0]
        if print_rows:
            row = str(left) + ", "
        for j in range(len(t)):
            left += d1[j]
            up += d0[j+1]
            upleft += d0[j]
            cost = 0 if (s[i] == t[j]) else 1
            d1[j + 1] = min(left + 1, up + 1, upleft + cost) - left
            if print_rows:
                row += str(left+d1[j+1]) + ", "

        if print_rows:
            print row

        for c in range(len(d0)):
            d0[c] = d1[c]

    return left+d1[j+1]

with open(sys.argv[1]) as f:
    lines = f.readlines()

perfect = lines[0]
string1 = lines[1]
string2 = lines[2]
distance = LevenshteinDistance(string1,string2)
print "edit distance: " + str(distance)
print "score: " + str(int(perfect)*100/distance) + "%"

example input:
2
101100
011010

example verbose output:
0, 1, 2, 3, 4, 5, 6,
1, 1, 1, 2, 3, 4, 5,
2, 1, 2, 2, 2, 3, 4,
3, 2, 1, 2, 3, 2, 3,
4, 3, 2, 1, 2, 3, 3,
5, 4, 3, 2, 1, 2, 3,
6, 5, 4, 3, 2, 2, 2,
edit distance: 2
score: 100%