text:
String to Binary
This is a code golf challenge. Just like the title says, write a program to covert a string of ascii characters into binary.
For example:
"Hello World!"
should turn into
1001000 1100101 1101100 1101100 1101111 100000 1010111 1101111 1110010 1101100 1100100 100001.
Note: I am particularly interested in a pyth implementation.

We had the reversed asked: http://codegolf.stackexchange.com/questions/35096/convert-a-string-of-binary-characters-to-the-ascii-equivalents

I noticed that. There's an anecdote for why I asked this question. I encouraged my friend to learn programming, and he took a java class last summer where each student had to pick a project. He told me he wanted to translate text to binary, which I then did (to his dismay) in python 3 in 1 line (a very long line). I find it incredible that his project idea can be distilled down to 8 bytes.

that's cool, thanks for sharing! I do like easier questions like this because it gives more people a chance to participate and generates lots of content in the form of answers.

Can I take input via a file (as specified at http://meta.codegolf.stackexchange.com/a/2452/30076)?

I would prefer that you take a string as input, but if you feel that you can provide an interesting and/or unique solution by using a file for input, please feel free to do so.

Are the spaces necessary?

Does it has to be ASCII? i.e., if a technology is not ASCII compatible, could the results reflect that?

Can we assume ASCII printable 32-127?  If so, can binary strings be 7 chars with left zero-padding?

Is it acceptable to output with a separator other than spaces (e.g. a newline)?

CJam, 8 bytes
l:i2fbS*

Easy-peasy:
l:i           "Read the input line and convert each character to its ASCII value";
   2fb        "Put 2 on stack and use that to convert each ASCII value to base 2";
      S*      "Join the binary numbers by space";

Try it here

Python 3, 41 bytes
print(*[bin(ord(x))[2:]for x in input()])

Like KSFT's answer, but I thought I'd point out that, in addition to raw_input -> input, Python 3 also has an advantage here due to the splat for print.

Pyth, 10 bytes
jdmjkjCd2z

Python mapping and explanation:
j           # join(                               "Join by space"
 d          #      d,                             "this space"
 m          #      Pmap(lambda d:                 "Map characters of input string"
  j         #                    join(            "Join by empty string"
   k        #                        k,           "this empty string"
    j       #                        join(        "This is not a join, but a base conversion"
     C      #                             Pchr(   "Convert the character to ASCII"
      d     #                                  d  "this character"
            #                                 ),
     2      #                             2       "Convert to base 2"
            #                            )
            #                        ),
  z         #           z)))                      "mapping over the input string"

Input is the string that needs to be converted without the quotes.
Try it here

Is asdfghjlkl also a valid pyth program? What does it do?

@flawr any harm in trying ? ;)

@flawr That compiles to the python Psum(d).append(Pfilter(lambda T:gte(head(join(Plen(k),Plen()))))), whee d=' ' and k=''. So no, it is not valid at all.

Thanks for the Pyth solution. I just started learning it today, but I think it will take some time getting used to. Any suggestions?

@ericmark26 look around your room or office, and smash everything that you can find into your keyboard and see if it interprets. Figure out what it does, and then repeat with the next object. When you run out, try different rotations.

@ericmark26 I think the best way to get used to Pyth is to take some simple Python programs, and translate them into Pyth.

MITS Altair 8800, 0 bytes
Input string is at memory address #0000H (allowed).  Output in binary via front panel I/O lights D7-D0.
Example, do RESET, then EXAMINE to see the first byte, followed by repeating EXAMINE NEXT to see the rest.
"H" = 01 001 000:

"e" = 01 100 101:

"l" = 01 101 100:

Try it online!
Non-competing, of course. :)

Python 3 - 43 bytes

print(*map("{:b}".format,input().encode()))

No quite the shortest, but an interesting approach IMO. It has the added advantage that if the number of significant bits varies, E.G. Hi!, padding with zeros is trivial (2 more bytes, as opposed to 9 for .zfill(8)):
print(*map("{:08b}".format,input().encode()))

Python - 52
print" ".join([bin(ord(i))[2:]for i in raw_input()])

I'll work on translating this into Pyth. Someone else did a Pyth answer already.
If you don't care about it being a full program or about I/O format and use Python 3, you can do it in 23 bytes like this:
[bin(ord(i))for i in x]

x is the input.
I know this doesn't count because the interpreter wasn't released before the challenge was posted, but here it is in KSFTgolf:
oan

Ruby, 34 28 24 bytes
$<.bytes{|c|$><<"%b "%c}

Takes input via STDIN. 6 bytes saved thanks for AShelly and another 4 thanks to britishtea.

trim by 6 with $<.each_byte{|c|$><<"%b "%c}

You can shave off some more characters by using String#bytes instead of String#each_byte. The block form is deprecated, but it still works :)

@britishtea Oh, nice. thank you!

PowerShell, 63 59 46 bytes
-13 bytes thanks to @mazzy
"$($args|% t*y|%{[Convert]::ToString(+$_,2)})"

Try it online!

? Try it online!

Forth (gforth), 45 bytes
: f 0 do dup i + c@ 2 base ! . decimal loop ;

Try it online!
Code Explanation
: f           \ start a new word definition
  0 do        \ start a loop from 0 to string length - 1
    dup i +   \ duplicate the address and add the loop index to get addr of current character
    c@        \ get the character at that address
    2 base !  \ set the base to binary
    .         \ print the ascii value (in binary)
    decimal   \ set the base back to decimal
  loop        \ end the loop
;             \ end the word definition

Java  - 148 Bytes
public class sToB{public static void main(String[] a){for(int i=0;i<a[0].length();i++){System.out.print(Integer.toString(a[0].charAt(i) ,2)+" ");}}}

Edited to include full file

I think OP wants a full program, not just a snippet. Plus, it can be golfed a lot more, methinks.

that is the full program, if you put that in a main class, it will run.
as for better golfing, probably but i could not spot how.

The full program includes the main class, too.

could be shorter using for(char c:a[0].toCharArray()){ or even for(byte b:a[0].getBytes()){ since the input is ascii, assuming a non-utf-16 machine locale

nice, I would never have thought of that. thank you.

You can get rid of the public and shorten the program name to a single char to win more bytes. Plus, (String[]a)is perfectly accepted by the compiler, earning you another byte.

I know it's been more than 2.5 year, but you can save 20 bytes like this: interface B{static void main(String[]a){for(Integer i=0;i<a[0].length();)System.out.print(i.toString(a[0].charAt(i++),2)+" ");}}

Scala - 59 - 55 Bytes
readLine().map(x=>print(x.toByte.toInt.toBinaryString))

Normally, one should use foreach and not map.

JavaScript ES6, 63 65 bytes
alert([for(c of prompt())c.charCodeAt().toString(2)].join(' '))

This is rather long, thanks to JavaScript's long function names. The Stack Snippet below is the rough ES5 equivalent, so it can be run in any browser. Thanks to edc65 for the golfing improvements.

alert(prompt().split('').map(function(e){return e.charCodeAt().toString(2)}).join(' '))

[for of] is slightly shorter than [...].map to enumerate charactes in strings: alert([for(c of prompt())c.charCodeAt().toString(2)].join(' '))

You can golf off two bytes by replacing .join(' ') with .join` ` . You can golf off a lot of bytes by using a function instead of prompt/alert

Matlab
This is an anonymous function
f=@(x) dec2bin(char(x))

usage is f('Hello World').
Alternatively, if x is defined as the string Hello World! in the workspace, then just dec2bin(char(x)) will work.

I'm not sure about how to score this because I'm not sure how I can get the input. Any comments?

Why char? I think you mean dec2bin(x)-'0'

Because I'm not that clever!

My point is: char(x), when x is already a string, does nothing. So you can remove it to save some space. On the other hand, the result of dec2bin is a string, and I think the output should be numbers

I understand, and you are right, of course. Matlab makes it easy to forget about data types sometimes.

J - 9
1":#:3&u:

No idea how to make this in a row without doubling the length of the code, I need J gurus to tell me :)
1":#:3&u:'Hello world!'
1001000
1100101
1101100
1101100
1101111
0100000
1110111
1101111
1110010
1101100
1100100
0100001

You can add ". to the beginning. It evaluates your result so it will be in one line and separated by spaces. Even shorter is to create base10 numbers with the base2 digits: 10#.#:3&u:.

Python 3.6, 39 bytes
print(*[f'{ord(c):b}'for c in input()])

Try it online!

x86-16 machine code, IBM PC DOS, 33 31 28 bytes
Binary:
00000000: d1ee ad8a c849 b308 ac92 b000 d0e2 1430  .....I.........0
00000010: cd29 4b75 f5b0 20cd 29e2 ebc3            .)Ku.. .)...

Listing:
D1 EE       SHR  SI, 1          ; point SI to DOS PSP (80H)
AD          LODSW               ; load input string length into AL, SI to 82H
8A C8       MOV  CL, AL         ; set up loop counter
49          DEC  CX             ; remove leading space/slash from char count
        LOOP_CHAR:
B3 08       MOV  BL, 8          ; loop 8 bits
AC          LODSB               ; load next char
92          XCHG AX, DX         ; use DX for bit shift
        LOOP_BIT:
B0 00       MOV  AL, 0          ; clear AL
D0 E2       SHL  DL, 1          ; high-order bit into CF
14 30       ADC  AL, '0'        ; AL = '0' + CF
CD 29       INT  29H            ; write AL to screen
4B          DEC  BX             ; decrement bit counter
75 F5       JNZ  LOOP_BIT       ; loop next bit
B0 20       MOV  AL, ' '        ; display a space
CD 29       INT  29H            ; write AL to screen
E2 EB       LOOP LOOP_CHAR      ; loop next char
C3          RET                 ; return to DOS

A standalone PC DOS executable COM file. Input is via command line, output to screen.

Ruby, 24 bytes
I was hoping to beat Martin Ender, but I only managed to tie him.
Takes input on STDIN; +1 bytes for -p flag.
gsub(/./){"%b "%$&.ord}

Try it online!

Python 3, 39 bytes
print(*[f'{ord(i):b}'for i in input()])

Try it online!
Slight improvement over the current leading Python answer

Vyxal S, 3 bytes
bƛṅ

Try it Online!
Explanation:
b    # Convert each letter to a list of bits
 ƛ   # In each list of bits:
  ṅ  #   Join elements
     # 'S' flag - join top of stack with spaces and output

Rust, 47 45 bytes
|s:&str|for i in s.bytes(){print!("{:b} ",i)}

Try it online!
A closure iterating over the string, converting each character to its ascii number, then printing out it's binary equivalent with :b
Turns out you don't need {} always to define a closure

Haskell, 65
m s=tail$do c<-s;' ':do j<-[6,5..0];show$mod(fromEnum c`div`2^j)2

heavy use of the list monad. it couldn't be converted to list comprehentions because the last statements weren't a return.

C++ - 119 bytes
Freeing memory? What's that?
#include<cstdio>
#include<cstdlib>
int main(int c,char**v){for(*v=new char[9];c=*(v[1]++);printf("%s ",itoa(c,*v,2)));}

(MSVC compiles the code with warning)

C version, shorter main(int c,char**v){char x[9];for(;c=*(v[1]++);printf("%s ",itoa(c,x,2)));}

Tcl, 52 bytes
proc B s {binary s $s B* b;regsub -all .{8} $b {& }}

Try it online!

Unfortunately the program version has more bytes due to the join: binary scan [join $argv] B* b;puts [regsub -all .{8} $b {& }]

Jelly, 3 bytes
OBK

Try it online!

APL (Dyalog), 12 bytes
10⊥2⊥⍣¯1⎕UCS

Try it online!
Thanks to Adám for help with this solution.

JavaScript ES6, 71 bytes
alert(prompt().split('').map(c=>c.charCodeAt(0).toString(2))).join(' ')

Welcome to PPCG! You need .split('') to split at the empty string; .split() turns "abc" into ["abc"].

Commodore VIC-20/C64/128 and TheC64Mini, 101 tokenized BASIC bytes
Here is the obfuscated listing using Commodore BASIC keyword abbreviations:
 0dEfnb(x)=sG(xaNb):inputa$:fOi=1tolen(a$):b=64:c$=mI(a$,i,1):fOj=0to6
 1?rI(str$(fnb(aS(c$))),1);:b=b/2:nEj:?" ";:nE

Here for explanation purposes is the non-obfuscated symbolic listing:
 0 def fn b(x)=sgn(x and b)
 1 input a$
 2 for i=1 to len(a$)
 3 let b=64
 4 let c$=mid$(a$,i,1)
 5 for j=0 to 6
 6 print right$(str$(fn b(asc(c$))),1);
 7 let b=b/2
 8 next j
 9 print " ";
10 next i

The function fn b declared on line zero accepts a numeric parameter of x which is ANDed with the value of b; SGN is then used to convert x and b to 1 or 0.
Line one accept a string input to the variable a$, and the loop starts (denoted with i) to the length of that input. b represents each bit from the 6th to 0th bit. c$ takes each character of the string at position i.
line 5 starts the loop to test each bit position; right$ is used in line 6 to remove a auto-formatting issue when Commodore BASIC displays a number, converting the output of fn b to a string; asc(c$) converts the current character to its ascii code as a decimal value.
Line 7 represents the next bit value. The loop j is ended before printing a space, then the last loop i is ended.

><>, 34 bytes
i\~48*o
?\:0(?;:2%:}-2,:0=
?\{nl1=

Try it online!

05AB1E, 4 bytes
Çbðý

Try it online.
Explanation:
Ç     # Convert the (implicit) input-string to a list of unicode values
 b    # Convert each integer to a binary string
  ðý  # Join by spaces (and output the result implicitly)

Could be just the first two bytes if a list output is allowed, or 3 bytes with » if a newline delimiter instead of space delimiter is allowed.

Perl 5, 21 bytes
printf'%b ',ord for@F

Try it online!

Gaia, 4 bytes
ċb¦ṡ

Pretty happy with this
How it works
ċ   Get a list of all the code points in the input string
b¦  Convert every number in that list to binary
ṡ   Joins the element of the list with spaces
Implicit Output

Try it Online!

Zsh --extendedglob, 30 bytes
<<<${1//(#m)?/$[[##2]#MATCH] }

Try it online!
//Replace every (#m) matched ? single character with its binary representation. [#2] leaves a 2# prefix on, [##2] strips it.

Zsh, 43 36 bytes
for c (${(s::)1})printf $[[##2]#c]\

Try it online!
Try it online!
Try it online!
for c (${(s::)1})                           # for character in string $1   (e.g. H)
                       $[       ]          # arithmetic evaluation
                       $[     #c]          # get character code           (e.g. 72)
                       $[[##2]#c]          # convert to base 2            (e.g. 1001000)
               printf  $[       ]\    # append space, print

If all binary strings need to be 8 characters long, +5 bytes:
for c (${(s::)1})printf %08d\  $[[##2]#c]

Try it online!

using printf for 43 bytes

Shakti, 8 3 bytes
In 2020.02.19:
10/2\`c?

Example:
 10/2\`c?"Hello World!"
1001000 1100101 1101100 1101100 1101111 100000 1010111 1101111 1110010 1101100 1100100 100001

Update: 3 bytes in 2020.02.23, via Arthur: 2\'

JavaScript (V8), 52 bytes
a=>[...a].map(p=>p.charCodeAt().toString(2)).join` `

Try it online!
Beats all existing JS answers.

brainfuck, 465 455 443 356 bytes
>>,[<+<+>>-]<[[-]>+++++++>+[>[-]>>[-]<<<<<<[>>>>+>+<<<<<-]>>>>[<<<<+>>>>-]<<[>>+>>+<<<<-]>>>>[<<<<+>>>>-]<<[>>[-]++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>[-]>[<<<+>>>-]<<<<-]>>[-]++<[>->+<[>]>[<+>-]<<[<]>-]<<[-]>>>>[<<<+<+>>>>-]<<<<<<[>>>+<<<-]>>>[[-]>>[-]-[<+>-----]<---[<<+<<+>>>>-]<<.[-]>]<<[>+>+<<-]>>-[<<+>>-]<]++++[>++++++++<-]>.<<<<[-]>[-]>[-],[<+<+>>-]<]

Try it online!

K (ngn/k), 12 6 bytes
{2\'x}

Try it online!
-6 bytes thanks to @coltim
Returns a 2D array.

I think this can be just 2\'

Cobra - 64
As a Lambda:
do(s='')=(for c as int in s get Convert.toString(c,2)).join(' ')

Postscript, 17 bytes (13 byte program + 4 character command line switch)
s { 2 7 string cvrs = } forall

Which is 31 bytes in tokenized form: (backticks denote literal characters, everything else is hexidecimal)
`s{2 7` 92A5 9230 `=}` 9249

Run using Ghostscript as:
gs -ss="Hello World!" string-to-binary.ps

JavaScript 78
alert(eval('""'+prompt().replace(/./g,"+' '+'$&'.charCodeAt().toString(2)")))

Ruby 38 Bytes
p gets.bytes.map{|i|i.to_s 2}.join ' '

.join ' ' can be shortened to *' '.

STATA 158
I used a different approach than most. Read in via the display _request() prompt (shortened to di _r(r)). Write the string to a file called b in text mode. Open b in binary mode and read each character as a byte and convert to binary. Technically the b file should be closed at the end, but it is a valid program and runs successfully without it.
di _r(r)
file open a using "b",w
file w a "$r"
file close a
file open a using "b",b r
file r a %1bu t
while r(eof)==0 {
loc q=t
inbase 2 `q'
file r a %1bu t
}

Golang - 68
I'm new to Go and I'm not sure on the rules for counting characters in this language on here either.
Imports (11 bytes):
import"fmt"

Function (55 bytes):
func c(s string){for _,r:=range s{fmt.Printf("%b ",r)}}

You can run it here.

You can golf this with import."fmt" and then just using Printf.

Erlang, 71 Bytes
f(S)->L=lists,L:droplast(L:flatten([integer_to_list(X,2)++" "||X<-S])).

If a trailing whitespace at the end is allowed then
55 Bytes
f(S)->lists:flatten([integer_to_list(X,2)++" "||X<-S]).

Never will C# win these kinds of questions but here's a try, completely without encoding. :)
C# - 84
Console.Write(String.Join(" ",Console.ReadLine().Select(x=>Convert.ToString(x,2))));

This could be made much shorter by using a lambda function, ie: x=>String.Join(" ",x.Select(y=>Convert.ToString(y,2))); However note that, due to using .Select(), both this shorter answer, and your original answer, need to include the 18 bytes for using System.Linq; unless you specify that it's using the Visual C# Interactive Compiler, which imports System.Linq by default

Here's the lambda function solution using Interactive Compiler, total of 55 bytes

Julia, 23 bytes
f(n)=[bin(a)for a in n]

q/kdb+, 18 bytes
Solution:
" "sv"01"0b vs'4h$

Example:
q)" "sv"01"0b vs'4h$"Hello World!"
"01001000 01100101 01101100 01101100 01101111 00100000 01010111 01101111 01110010 01101100 01100100 00100001"

Explanation:
Convert string to byte array, convert each byte to binary, index into the string "01" and then join strings together with whitespace " ":
" "sv"01"0b vs'4h$ / the solution
               4h$ / cast ($) to type byte (4h)
         0b vs'    / convert each (') byte to binary (0b vs)
     "01"          / (implicit) index into "01" (false;true)
" "sv              / join (sv) with " "

Shell utils, 102 bytes
I'm kind of ashamed of this.
xxd -b|sed -r "s/^.*: //;s/  .+$//;s/0*([01]+)/\1/g"|tr \n\r " "|sed -r "s/ +/ /g;s/ *1101 *1010 *$//"

Since I'm (possibly) running utilities from various archives across the Internet on Windows, I'll list the version information for each:
xxd V1.10 27oct98 by Juergen Weigert
GNU sed version 4.2.1
tr (GNU textutils) 2.0
Microsoft Windows [Version 10.0.15063]

PHP, 59 bytes
<?foreach(str_split($argv[1])as$a)echo decbin(ord($a)).' ';

Try it online!

Deorst, 8 bytes
vombkE]_

Try it online!
How it works
Example input: ab
vo       - Map ordinal;      STACK = [[97, 98]]
  mb     - Map binary;       STACK = [['1100001', '1100010']]
    k    - Turn off sort;    STACK = [['1100001', '1100010']]
     E]  - Flatten;          STACK = ['110001', '1100010']
       _ - Join with spaces; STACK = ['110001 1100010']

05AB1E, 10 bytes
SvyÇ2Bнð«?

S           //Split string
 v          //Loop on every character
  y         //Push current character to the stack
   Ç        //Get ASCII value of character
    2B      //Convert to base 2
      н     //Convert from 1-element array to string
       ð«   //Append space
         ?  //Print with no newline

Try it online!

Perl 6, 16 bytes
*.ords>>.base(2)

Try it online!
Converts the string to codepoints and then each to base 2.

Java 8, 112 bytes
Takes input as a command line argument
interface M{static void main(String[]a){a[0].chars().forEach(i->System.out.print(Long.toBinaryString(i)+" "));}}

Try it online!

I'm so tired right now that I forgot I already did this challenge and almost posted a duplicate.

Japt -S, 4 bytes
¬®c¤

Try it
¬®c¤     :Implicit input input of string U
¬        :Split
 ®       :Map
  c      :  Character code
   ¤     :  To binary string
         :Implicitly join with spaces and output

Or, if we can take input as an array of characters ...
Japt -mS, 2 bytes
c¤

Try it

Python 3, 39 bytes
for i in input():print(bin(ord(i))[2:])

Try it online!

Welcome to the site! While I'm sure it's a non-issue, the post asks for spaces, not newlines, between the binary chunks. I've commented on the question asking if newlines are acceptable for you. In addition, I've edited in a link to Try it online! so that others can verify that your solution works.

Elixir 47
for c<-:io.read(''),do: :io.fwrite('~.2B ',[c])

As function:
& for<<c<-&1>>,do: :io.fwrite('~.2B ',[c])

As function working on charlists (' delimited strings):
& for c<-&1,do: :io.fwrite('~.2B ',[c])

Erlang 41
[io:fwrite('~.2B ',[C])||C<-io:read("")].

How is this answer called?  Is it a complete program?  Is it a function? Is it something else?

Fixed to be full program.

Burlesque, 10 bytes
XX{**b2}mw

Try it online!
XX  # Break into characters
{
 ** # Convert to ascii val
 b2 # Convert to binary
}mw # Map and spaces between elements

PHP, 44 bytes
while($c=decbin(ord($argn[$i++])))echo"$c ";

Try it online!

Pip -s, 6 bytes
TB*A*a

Converts to ASCII/Unicode, then to binary. the -s flag joins lists on space.
Try it online!

Husk, 7 bytes
wm(ṁsḋc

Try it online!

05AB1E, 2 1 byte
b

Try it online! Beats all other answers. Takes input as a list of code points.

Rust, 40 bytes
|s|for c in s.bytes(){print!("{:b} ",c)}

Try it online!
An anonymous function that takes in an &str, iterates over bytes, and prints them as a binary string.

MUMPS, 77 76 bytes
r s,! f i=1:1:$l(s) s r=$a($e(s,i)) s b=" " f  s b=(r#2)_b,r=r\2 i r=0 w b q

Example
REPL > r s w ! f i=1:1:$l(s) s r=$a($e(s,i)) s b=" " f  s b=(r#2)_b,r=r\2 i r=0 w b q
Hello World!
1001000 1100101 1101100 1101100 1101111 100000 1010111 1101111 1110010 1101100 1100100 100001

Explanation

M is great at keeping things to one line.
We assign user input to variable s and write a newline (!).
For each character in our string, get the ASCII value with $ascii() and $extract() (intrinsic functions can be abbreviated).
b is meant to hold the binary value of our character, but we will quickly set it to be a space since we need that to separate the binary representation of each character.
Now we enter an unconditional loop (two spaces after declaring the for loop). We prefix b with out ascii value (r) modulo 2. You can do string operations on numbers in M.
We then reduce our ascii value by half, disregarding the remainder (\ is floor division)
We do this until our ascii value hits 0, at which point we write our binary value

Go, 116 bytes
package main
import(."fmt";"os";."io/ioutil")
func main(){b,_:=ReadAll(os.Stdin);for c:=range b{Printf("%b ",b[c])}}

Try it online!

Thunno 2 ṠB, 1 byte
ḃ

Attempt This Online!
Or, 4 bytes flagless:
Cḃðj

Attempt This Online!

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳


text:
Sum the powers to n
Directions
Write a program that, given an input integer n (n >= 0), outputs the smallest positive integer m where:

n = a[1]^b[1] + a[2]^b[2] + a[3]^b[3] + ... + a[k]^b[k]
a and b are finite sequences of the same length
all elements of a are less than m
all elements of b are less than m
all elements of a are different and integers a[x] >= 0
all elements of b are different and integers b[x] >= 0
a[x] and b[x] are not both 0 (since 0^0 is indeterminate)

This is code-golf, so fewest bytes wins.
Examples
In 0 -> Out 1
Possible Sum:

In 1 -> Out 2
Possible Sum: 1^0

In 2 -> Out 3
Possible Sum: 2^1

In 3 -> Out 3
Possible Sum: 2^1 + 1^0

In 6 -> Out 4
Possible Sum: 2^2 + 3^0 + 1^1

In 16 -> Out 5
Possible Sum: 2^4

In 17 -> Out 4
Possible Sum: 3^2 + 2^3

In 23 -> Out 6
Possible Sum: 5^1 + 3^0 + 2^4 + 1^3

In 24 -> Out 5
Possible Sum: 4^2 + 2^3

In 27 -> Out 4
Possible Sum: 3^3

In 330 -> Out 7
Possible Sum: 6^1 + 4^3 + 3^5 + 2^4 + 1^0

How are we supposed to make a sequence of unique, nonnegative integers that has a non-infinite sum?

Also, the first case doesn't make sense because a sum with 0 terms would suffice.

@feersum I don't quite understand your question. My solution to this is a brute force search of all combinations where m<2 then m<3 then m<4 etc. until I find a sum that equals n. Also, I thought about having the sum for 0 be no terms, but then what is the output? m > ?

My first comment was because the way it is written suggests an infinite sequence. For the second issue, I suggest that the minimum input is 1.

@feersum Alright, I will change the example case. And I will also try to notate a finite sequence somehow. Any ideas?

For finite sequences, you would usually do something like n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k].

Nice question. Just one quibble on the first test case: a and b are finite sequences of length 0, so there is no integer m which doesn't satisfy the constraints, and since there is no smallest integer the answer is not defined. Possible fixes would be to ask for the smallest natural number m (in which case you should change the expected answer there to 0) or for the smallest positive integer m.

GolfScript (59 chars)
~:T),{),.0{2$0-{2${{4$2$^}2*@3$\?4$+f~}%\;~}%+\;\;}:f~T&}?)

Online demo
This uses recursion to enumerate the values achieveable for a given m and searches for the first m which works. It's lightly inspired by xnor's answer but quite different in implementation.
Dissection
~:T                  # Evaluate input and store in T (for Target)
),{                  # Search [0 1 ... T] for the first m which matches a predicate
  ),.0               #   Push [0 ... m] to the stack twice and then 0
                     #   Stack holds: possibleAs possibleBs sum
  {                  #   Define the recursive function f
    2$0-{            #     Map over A in possibleAs (except 0)
      2${            #       Map over B in possibleBs (except 0)
        {4$2$^}2*    #         Duplicate respective possibles and remove selected values
        @3$\?4$+     #         Compute sum' = sum + A^B
        f            #         Recursive call gives an array [sums]
        ~            #         Push the sums to the stack individually
        }%           #       End map: this collects the sums into a combined array
      \;             #       Pop A, leaving just the combined [sums] inside the map
      ~              #       Repeat the trick: push to the stack individually
    }%               #     End map, collecting into a combined array
                     #     Stack now holds: possibleAs possibleBs sum [sums]
    +                #     Include the original sum in the array of reachable sums
    \;\;             #     Pop possibleAs and possibleBs
  }:f                #   End function definition
  ~                  #   Evaluate the function
  T&                 #   Test whether the sums contain T
}?                   # End search
)                    # Increment to get m

Python, 120
f=lambda n,A,B:n*all(f(n-a**b,A-{a},B-{b})for a in A for b in B)
g=lambda n,m=1,M={0}:f(n,M-{0},M)and g(n,m+1,M|{m})or m

The function f is an auxiliary function that checks whether n can not be expressed as a sum of powers with distinct bases from A and exponents from B. It uses a natural recursive strategy: n must be nonzero, and we try every possible choice of base and and exponent and they all need to fail. We removing them from the allowed lists and decrease n by the corresponding amount.
The function g is the main function. It searches for an m that works. M is the set of allowed values up to m-1. We remove 0 from the allowed exponents to stop 0**0 (which Python evaluates to 1) from being used. This doesn't hurt anything Because 0**x is a useless 0 for all other x.

You could probably change n and all() to n*all().

@grc Ah, you don't actually need the short circuiting because it bottoms out. Thanks for the improvement.

Python 2, 138 bytes
from itertools import*
S=lambda n,m=0,R=[]:m*any(n==sum(map(pow,*C))for k in R for C in product(*tee(permutations(R,k))))or S(n,m+1,R+[m])

(Thanks to @Jakube for all the tips)
I've never learnt so much about the itertools module as I have from this one question. The last case takes about a minute.
We start by searching from m = 1 and incrementing until we get a solution. To check for a solution we iterate over:

k = 0 to m-1, where k is the number of terms in the solution
All possible combination of terms (by zipping together two permutations of subsets of [0, 1, ... m-1] with size k), then summing and checking if we have n

Note that we iterate k up to m-1 — even though technically m terms are possible in total, there's always a solution with m-1 terms as 0^0 is not allowed and 0^b contributes nothing. This is actually important because 0^0 is treated as 1 by Python, which seems like a problem, but it turns out not to matter!
Here's why.
Suppose a solution found erroneously uses 0^0 as 1, e.g. 3^2 + 1^1 + 0^0 = 11. Since we only generate up to m-1 terms, there must be some j we are not using as a base (here j = 2). We can swap out the base 0 for j to get a valid solution, here 3^2 + 1^1 + 2^0 = 11.
Had we iterated up to all m terms, then we might have gotten incorrect solutions like m = 2 for n = 2, via 0^0 + 1^1 = 2.

Nice one. You can save 4 bytes by using imap though.
imap(pow,C,D) ... for C,D in

@Jakube I'm actually looking through the doc for itertools as we speak :P I already have another saving — tee.

Me too.
Also, my mistake. Why would someone suggest imap, when there is map?? -1 byte

The default parameter for tee is already n=2. Saves 2 bytes.

@Jakube Ahaha thanks. This is probably the first time I've ever used map with more than one iterable, and in fact this question's bring out a lot of firsts for me.

One last thing. If you go back to your any-construct, you can save 2 additional bytes: m*any(n==sum ...)or S(n,m+1)

@Jakube I can save another byte by passing in a list instead of having range(m), but I feel like that's now intruding on your solution...

I don't mind. You can use it if you want.

GolfScript (90 84 bytes)
[0.,.]](~:T),(+{:x;{:|2,{:c)|=x),^{c[1$x]=:A^x^:-;[|~-+@A-?+@A+@]}%}/+~}%.[]*T&}?)\;

Online demo
Dissection
[0.,.]             # Base case: [sum As Bs] is [0 [] []]
](~:T              # Collect it in an array of cases; fetch parameter, eval, store in T.
),(+               # Create array [1 2 ... T 0]. Putting 0 at the end means that it won't
                   # be reached except when T is 0, and nicely handles that special case.
{                  # Loop over the values from that array...
  :x;              #   ...assigning each in turn to x (and popping it from the stack)
  {                #   Stack holds array of [sum As Bs] cases; map them...

    :|             #     Store [sum As Bs] in |
    2,{:c          #     For c in [0 1]...
      )|=x),^      #       Get [0 1 ... x]^ either As or Bs, depending on c
      {            #       Map these legal new As or Bs respectively...
        c[1$x]=:A  #         Work out which of that value or x is the new A
        ^x^:-;     #         And the other one is the new B
        [          #         Begin gathering in an array
          |~       #           Push sum As Bs to the stack
          -+       #           Add - to Bs to get Bs'
          @A-?+    #           Rotate sum to top and add A^- to get sum'
          @A+      #           Rotate As to top and add A to get As'
          @        #           Final rotation to put elements in the right order
        ]          #         Gather in array [sum' As' Bs']
      }%           #       End map
    }/             #     End for
    +~             #     Push all the elements corresponding to x^B and A^x on to the stack
  }%               #   End map, collecting the untouched [sum As Bs] and all the new
                   #   [sum' As' Bs'] arrays into a new array of reached cases.
  .[]*T&           #   Flatten a copy of that array and filter to values equal to T.
                   #   This gives a truthy value iff we've found a way to make T.
}?                 # Loop until we get a truthy value, and push the corresponding x
)\;                # Increment to get the value of m and discard the array of cases

The most elegant trick is the handling of the special case for 0.

I am really happy that CJam is this time not soo much shorter than standard python=P

@flawr, this is GolfScript, not CJam. CJam can probably be quite a bit shorter because it has a built-in for Cartesian products. And it might be that xnor's idea of a recursive function gives shorter GolfScript, too.

Oh sorry, just confused them=)

Haskell, 143 130
import Data.List
p n=head$[1..]>>=(\m->[m|let x=permutations[0..m-1]>>=inits,a<-x,b<-x,sum(zipWith(\x y->x^y*signum(x+y))a b)==n])

Usage example: p 23 -> 6.
This is a simple brute force search. For every list [0..0], [0..1], [0..2] ... [0..∞] take all initial segments of the permutations (e.g. [0..2]: permutations: [012], [102], [210], [120], [201], [021], initial segments for 1st permutation: [0], [01], [012], 2nd: [1], [10], [102], etc.). For every combination of 2 of those lists calculate the sum of powers. Stop when first one equals n.

you should use >>= rather than concatMap. they are just the same but with the arguments flipped.

@proudhaskeller: Yes, thanks!

Python: 166 characters
from itertools import*;p=permutations
f=lambda n,r=[0]:any(n==sum(map(lambda x,y:(x+y>0)*x**y,a,b))for j in r for a,b in product(p(r,j),p(r,j)))*1or 1+f(n,r+[len(r)])

Explanation
The function f creates all possible integers, that can be expressed as sum of powers of of numbers in r. If starts with r = [0]. If any of those integers is equal to n, it returns the length of r, otherwise it call itself recursively with an extended r.
The computation of the all integers, that can be expressed as sum is done with two loops.
The first loop is the for j in r, which tells us the length of the expression (2^3 + 1^2 has length 2). The inner loop iterates over all combinations of permutations of r of length j. For each I calculate the sum of powers.

JavaScript (ES6) 219 224
Recursive function. Starting with m=1, I try all combinations of integer 1..m for bases and 0..m for exponents (0 base is useless given 0^0 == undefined).
If no solution found, increase m and try again.
Special case for input 0 (in my opinion that is an error in the specs anyway)
The C function recursively generates all combinations from an array of given length, so that
C(3, [1,2,3]) --> [[3,2,1], [3,1,2], [2,3,1], [2,1,3], [1,3,2], [1,2,3]]

The third level every is used to zip together the array a of bases and b of exponents (there is no zip function in JavaScript). Using every to stop early when there is a solution not using all elements in the two arrays.
F=(n,j=1,k=[],
  C=(l,a,o=[],P=(l,a,i=l)=>{
    for(l||o.push(a);i--;)
      e=[...a],P(l-1,e.concat(e.splice(i,1)))
  })=>P(l,a)||o
)=>n&&C(k.push(j++),k)[E='every'](a=>C(j,[0,...k])[E](b=>a[E](x=>t-=Math.pow(x,b.pop()),t=n)))
?F(n,j,k):j

Test In FireFox/FireBug console
;[0,1,2,3,6,16,17,23,24,27,330].map(x=>[x,F(x)])

Output

[[0, 1], [1, 2], [2, 3], [3, 3], [6, 4], [16, 5], [17, 4], [23, 6], [24, 5], [27, 4], [330, 7]]

source: Stack Exchange

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

sort: votes


text:
H Tree Directories
Programmers are often obsessed with drawing fractals. I think we need a new computer based medium.
The H tree is a fairly simple type of fractal made of horizontal and vertical lines. Here it is at it's tenth iteration (courtesy Wikipedia):

Now, imagine each of the lines in the image is a directory (folder) in a standard computer file system. All but the smallest lines intersect two lines smaller than themselves; these two smaller lines are subdirectories of the larger line. Thus the large horizontal line in the middle is the parent directory of the two largest vertical lines, which are in turn parents, grandparents, etc. of rest of the lines in the image.
Challenge
Write a program that takes in a positive integer N via stdin or the command line (or closest alternative) and creates a directory tree that mirrors the Nth iteration of the H tree fractal.
The first iteration (N = 1) is a single horizontal line. In each subsequent iteration a new set of vertical or horizontal lines is added to the ends of the current lines. So for N = 2 two vertical lines are added (making an H shape), for N = 3 four horizontal lines are added to that, etc.
The name of the root directory must always be tree. The names of the subdirectories must match the direction they are in with respect to their parent line, using right, left, up and down.
Since the root directory is always a horizontal line it will always have right and left subdirectories. But those two will have up and down subdirectories, and those will have right and left again, and so on.
The directories at the end of the limit of iterations should be empty.
Example
For N = 3 the directory tree should look like this:
tree
    right
        up
        down
    left
        up
        down

Additional Info

Ideally the tree directory will pop up in the same folder the source code is in, but it's alright if it goes to some working directory.
You may assume that there is no pre-existing tree directory in the place yours will be created.
You may assume that your program will always be run on the same common modern operating system (Mac/Windows/Linux). Basically don't worry about using a file separator that doesn't work in all OS's.

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

Do the subdirectories of tree always have to be left and right instead of up and down?

@KSFT Yes: "Since the root directory is always a horizontal line it will always have right and left subdirectories."

Ruby, 127 bytes
f=->n{n<2?['tree']:f[n-1].map{|p|%w{left right up down}[n%2*2,2].map{|d|p+?/+d}}.flatten}
system'mkdir "'+f[gets.to_i]*'" "'+?"

Tested on Windows. Takes input via STDIN.
f recursively generates a list of the required leaves of the tree, and then I just feed them to a single system call of mkdir.

Lua, 179
t=0+io.read()a={"left","right","up","down"}function h(d,v)if v~=t then os.execute("mkdir "..d)x=1 if v%2==1 then x=3 end for g=x,x+1 do h(d.."\\"..a[g],v+1)end end end h("tree",0)

Python - 194
from os import system as s
a="mkdir "
s(a+"tree")
def f(n):
 if n<j%2:return
 for i in(0,1):m=["up"if n%2 else"left","rdiogwhnt"[n%2::2]][i];s(a+m);s("cd "+m);f(n-1);s("cd..")
j=input()
f(j+j%2)

its slightly shorter to do from os import*;s=system

Two more things: you can also do ["left","up"][n%2] and you can drop the brackets around (0,1) to give for i in 0,1:

Python 2 + *nix coreutils, 212 189
Generates all the innermost paths and calls
mkdir -p
import os
n=int(raw_input())-1
for i in range(2**n):os.system("mkdir -p "+os.path.join('tree',*([['right','left'],['up','down']][b%2][int(j)]for b,j in enumerate('{:0{}b}'.format(i,n)))))

Crashes if input < 1

you can combine the first two lines: import os,itertools as t

@DenDenDo Removed itertools completely

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


text:
Cover a Region with Rectangles
Input
Your input in this challenge is a list of integer pairs. They represent the southwest corners of unit squares on the plane, and the list represents their union as a subset of the plane. For example, the list
[(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)]

represents the red-colored set in this picture:

Output
Yor output is a list of integer quadruples, representing rectangular subsets of the plane. More explicitly, a quadruple (x,y,w,h) reperents a rectangle of width w > 0 and height h > 0 whose southwest corner is at (x,y). The rectangles must form an exact covering of the input region, in the sense that each of the unit squares is a subset of some rectangle, each rectangle is a subset of the region, and two rectangles may overlap only at their borders. To forbid trivial solutions, the covering must not contain two rectangles that could be merged into a larger rectangle.
For example, the list
[(0,0,2,1),(0,1,3,1),(1,2,2,1)]

represents the legal covering

of the above region, whereas the covering given by
[(0,0,2,2),(2,1,1,1),(1,2,1,1),(2,2,1,1)]

is illegal, since the neighboring 1-by-1 squares could be merged:

Rules
You can give a full program or a function. The precise formatting of the input and output is not important, within reason. The shortest byte count wins, and standard loopholes are disallowed. You are encouraged to provide an explanation of your algorithm, and some example outputs.
Test Cases
A U-shaped region:
[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]

A large triangle:
[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]

A square with holes:
[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]

Disconnected regions:
[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(4,0),(4,1),(4,2),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(6,0),(6,1),(6,2),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,7),(9,8),(9,9),(10,0),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9)]

Verifier
Use this Python 2 program to verify your solution. It takes from STDIN a list of tuples (the input) and a list of quadruples (your output), separated by a comma.
I also wrote this Python 2 program to generate the pictures, and you can use it too. It takes from STDIN a list of either tuples or quadruples, and produces a file named out.png. It requires the PIL library. You can change the size of the grid cells and the width of the gird lines too, if you want.

Python: 196 193 182 character
def g(r):
 for p in r:
  for q in r:
   for h in 0,1:
    if p[h::2]==q[h::2]and p[1-h]+p[~h]==q[1-h]:p[~h]+=q[~h];r.remove(q);return g(r)
 return r
f=lambda P:g([x+[1,1]for x in P])

My first solution used the exact same algorithm as KSFT, therefore I experimented with other methods.
First I do some preprocessing, I convert all points into small 1x1 rectangles {x+(1,1)for x in P}. With these rectangles, I call the function g. g iterates over each combination of rectangles. If it finds 2 rectangles, that can be merged into a bigger one, it deletes both and append the new one. Afterwards it calls itself with the new set of rectangles.
Usage
f([[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]])

Results
Here are the visualization of the results. Note that they may be a bit different in the current version. The idea is though, that there is no kind of noticeable pattern.
A U-shaped region:

A large triangle

A square with holes:

Disconnected regions:

Just for fun: Pyth: 73 69 character
D!HFGHFZHV2I&q%2>GN%2>ZNqs%2>G-1N@Z-1N X-3NG@Z-3NR!-H]Z)))RH!m+d*2]1Q

Works only in the offline version. Bug in the online version is fixed now. Try it here: Pyth Compiler/Executor. Expects a list of lists, not a list of tuples.
edit: Used an idea from @edc65: Instead of deleting both rectangles and creating a new one, I manipulate one and only delete one. In the Python solution I could get ride of the sets and the tuple-list-tuple casts. -11 chars in Python / -4 chars in Pyth

Python3: Smiley faces are now valid code.

I might be wrong, but I think you can change 3-h to ~h?

Accepted for the Pyth version.

Python - 272 261 258 251 224
I think I can golf this more. I'm pretty sure this works, but I haven't finished testing it on all of the test cases yet. I finished testing it. It works for all of the test cases.
a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h

I'm working on adding images of the results.
Edit: Here are the results from the example and the test cases:

I'm trying to write this in Perl, but I can't figure out how to get multidimensional arrays from stdin without a huge number of characters. Does anyone have any suggestions?

Two things: (i[0]+w,i[1]+j)not in c to {(i[0]+w,i[1]+j)}-c and you can move w=h=1 to the c=set(a)-set(b) line

A few more: b+=[(j+i[0],k+i[1])] to b+=(j+i[0],k+i[1]), and you use range three times so it's shorter  to assign r=range

Also I'm not sure, but is it possible to do x,y=i then using x and y instead of i[0] and i[1]? That would save a lot of bytes.

Haven't tested this, but I think it works:
Instead of while not[j for j in r(h)if(x+w,y+j)not in c]:w+=1 use while all((x+w,y+j)in c for j in r(h)):w+=1.

@Sp3000/Jakube I've used all of your suggestions.

@KSFT Please test your code before you post it. I think there are 2 bugs right now.

@Jakube Yeah, I guess I should've done that... What are the bugs?

I spotted the ix in one of the last lines. And the line  while{(x,y+h)}-c:h+=1 is an infinite loop, not sure why though.

I think you need a not in the condition.

@Jakube Ah, you're right. I fixed it.

For the last few lines you can do b+=[(j+x,k+y)for j in r(w)for k in r(h)] then put the print on the same line. Also instead of if i in b:continue you can do if i not in b: then indent the lines following after the above suggestion. But yeah, probably fix up the bugs first.

@KSFT No, the not belongs to the first while loop, not the second one. And I still see that ix

Like this?

@Doorknob Why did you edit my post? Was there something wrong with what I wrote?

@KSFT The line I removed had nothing to do with the actual solution and was simply noise.

@Doorknob Okay...I didn't know that was against the rules.

Python 2, 139
The program accepts lists of ordered pairs surrounded by curly braces on standard input. E.g., {(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)}
s=input()
while s:x,y=min(s);w=h=0;exec"while(x+w,y)in s:w+=1\nwhile%s<=s:s-=%s;h+=1"%(("{(X,y+h)for X in range(x,x+w)}",)*2);print x,y,w,h

It's often irritating (not only in golf) that Python does not allow an assignment inside of a loop test. To work around this, I used string formatting operations.

That's impressive. The same algorithm as KSFT, 'only' 85 (!!!) chars  shorter.

Mathematica - 315 285 267 bytes
f=(r={};For[m=MemberQ;t=Table;s=Sort@#,s!={},For[{x,y,w,h}=#~Join~{1,1}&@@s;i=j=0,i<1||j<1,If[s~m~{x+w,y+a-1}~t~{a,h}==True~t~{h},w++,i++];If[s~m~{x+a-1,y+h}~t~{a,w}==True~t~{w},h++,j++]];s=s~Cases~_?(!m[Join@@t[{x+a,y+b}-1,{a,w},{b,h}],#]&);r~AppendTo~{x,y,w,h}];r)&

With some help from @MartinBüttner.
Ungolfed:
f = (
    rectangles = {};
    For[squares = Sort[#], squares != {},
        For[{x, y, w, h} = Join[squares[[1]], {1, 1}]; i = j = 0, i < 1 || j < 1,
            If[Table[MemberQ[squares, {x + w, y + a - 1}], {a, h}] == Table[True, {h}], w++, i++];
            If[Table[MemberQ[squares, {x + a - 1, y + h}], {a, w}] == Table[True, {w}], h++, j++];
        ];
        squares = Cases[squares, _ ? (!MemberQ[Join@@Table[{x + a - 1, y + b - 1}, {a, w}, {b, h}], #] &)];
        AppendTo[rectangles, {x, y, w, h}]
    ];
    rectangles
)&

Usage:
In: f @ {{0,0},{1,0},{0,1},{1,1},{2,1},{1,2},{2,2}}
Out: {{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

Test Cases
A U-shaped region

{{0, 0, 6, 2}, {0, 2, 2, 4}, {4, 2, 2, 4}}

A large triangle

{{0, 0, 6, 5}, {0, 5, 3, 3}, {0, 8, 2, 1}, {0, 9, 1, 1}, {3, 5, 2, 1}, {3, 6, 1, 1}, {6, 0, 3, 2}, {6, 2, 2, 1}, {6, 3, 1, 1}, {9, 0, 1, 1}}

A square with holes

{{0, 0, 6, 3}, {0, 3, 3, 6}, {1, 9, 9, 1}, {3, 4, 3, 2}, {3, 6, 2, 3}, {4, 3, 6, 1}, {5, 7, 5, 2}, {6, 1, 4, 2}, {6, 5, 4, 2}, {7, 0, 3, 1}, {7, 4, 3, 1}}

Disconnected regions

{{0, 0, 2, 5}, {0, 5, 1, 4}, {1, 6, 2, 4}, {2, 1, 1, 5}, {4, 0, 3, 3}, {4, 4, 3, 6}, {5, 3, 1, 1}, {8, 0, 3, 4}, {8, 4, 1, 6}, {9, 7, 2, 3}, {10, 4, 1, 3}}

JavaScript (ES6) 148 155 199
Edit2 Some more tuning
Edit Some golfing + rewrite using recursion. Did not expect such a reduction.
Now it's a little difficult to follow, but the algorithm is the same.
The algorithm is similar to @jakube answer.

Each point becomes a 1x1 square (preprocessing)
For each element, check if it can be merged with another
 Yes? First element grows, second element erased, start again at step 2
 Else, proceed to next element

F=l=>
  (l.map(x=>x.push(1,1)),R=f=>
    l.some(u=>
      (l=l.filter(t=>
        [0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))
      ),f)
    )?R():l
  )()

Test in snippet

F=l=>(l.map(x=>x.push(1,1)),R=f=>l.some(u=>(l=l.filter(t=>[0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))),f))?R():l)()

// Test
MyCanvas.width= 600;
MyCanvas.height = 220;
var ctx = MyCanvas.getContext("2d");
ctx.fillStyle="#f23";

Draw=(x,y,f,l)=>l.forEach(p=>ctx.fillRect(x+p[0]*f,y+p[1]*f,p[2]*f-1||f-1,p[3]*f-1||f-1));

test=[
[[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,0],[2,1],[3,0],[3,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[6,0],[6,1],[6,2],[6,3],[7,0],[7,1],[7,2],[8,0],[8,1],[9,0]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,7],[5,8],[5,9],[6,1],[6,2],[6,3],[6,5],[6,6],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,6],[1,7],[1,8],[1,9],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[4,0],[4,1],[4,2],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,4],[6,5],[6,6],[6,7],[6,8],[6,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,7],[9,8],[9,9],[10,0],[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9]]
]

Draw(0,0,10,test[0]),Draw(0,110,10,F(test[0]))
Draw(50,0,10,test[1]),Draw(50,110,10,F(test[1]))
Draw(130,0,10,test[2]),Draw(130,110,10,F(test[2]))
Draw(250,0,10,test[3]),Draw(250,110,10,F(test[3]))
Draw(370,0,10,test[4]),Draw(370,110,10,F(test[4]))
<canvas id=MyCanvas></canvas>

Haskell, 158
f[]=[]
f s@((x,y):_)=(x,y,w-x,h-y):f[r|r@(a,b)<-s,a<x||a>=w||b<y||b>=h]where w=[i|i<-[x..],notElem(i,y)s]!!0;h=[i|i<-[y..],not$all(\x->elem(x,i)s)[x..w-1]]!!0

test cases and images will be here shortly.
Algorithm:
Take the first square. Reach as far right without encountering a square not in the input. Then reach as far up as possible without having a square not on the input. We now have a rectangle without a missing square. Add it to the output, remove all of its squares from the input and call recursively.

You can save 1 byte by replacing not$all(\x->elem(x,i)s) with any(\x->notElem(x,i)s).

Mathematica, 153 151 144 136 133
Sort[{##,1,1}&@@@Input[]]//.{a___,r:{x_,y_,__},b___,{X_,Y_,W_,H_},c___}/;r=={x,Y,X-x,H}||r=={X,y,W,Y-y}:>{a,r+Sign@{0,0,X-x,Y-y},b,c}

Example:
Input:
{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 1}, {1, 2}, {2, 2}}

Output:
{{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

Input:
{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 7}, {5, 8}, {5, 9}, {6, 1}, {6, 2}, {6, 3}, {6, 5}, {6, 6}, {6, 7}, {6, 8}, {6, 9}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {8, 8}, {8, 9}, {9, 0}, {9, 1}, {9, 2}, {9, 3}, {9, 4}, {9, 5}, {9, 6}, {9, 7}, {9, 8}, {9, 9}}

Output:
{{0, 0, 3, 9}, {1, 9, 9, 1}, {3, 0, 3, 3}, {3, 4, 1, 5}, {4, 3, 1, 6}, {5, 3, 1, 3}, {5, 7, 1, 2}, {6, 1, 1, 3}, {6, 5, 1, 4}, {7, 0, 3, 9}}

Algorithm:
Cover the region with unit squares, then merge them.