title: H Tree Directories

text:
# Question
Title: 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.

# Answer
# 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`.
> 5 votes

# Answer
# 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)

```
> 3 votes

# Answer
# 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)

```
> 2 votes

# Answer
## 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
> 2 votes

---
Tags: code-golf, fractal, file-system
---


title: Sum the powers to n

text:
# Question
Title: 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 , 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

```

# Answer
## 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

```
> 2 votes

# Answer
# 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`.
> 6 votes

# Answer
# 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`.
> 4 votes

# Answer
## 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`.
> 4 votes

# Answer
# 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.
> 4 votes

# Answer
# 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.
> 2 votes

# Answer
# 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\]\]
> 2 votes

---
Tags: code-golf, number, arithmetic
---


title: Billy Lost his Pen

text:
# Question
Title: Billy Lost his Pen
tl;dr \[True\] Billy got a Stack Overflow pen from Tim Post. Billy was stupid enough to *use* the pen, knowing that he was not worthy. Billy's friend took the pen apart, so Billy put the pen in a drawer at his house, hoping he would eventually fix it. A year later, Billy can only find half of the pen's pieces, and not the main part that has the words "Stack Overflow" on it. \[EndTrue\] \[Fake\] Billy looked at his home security camera and saw that a burglar had come in his house while he was sleeping and taken his pen. Billy vows revenge! Why can't he just ask for another Stack Overflow pen? Because this is the last one in existence. \[EndFake\] Err, technically this whole thing is fake because my name isn't Billy.

Help Billy find the scumbag that stole his pen so he can ultimately deal mortal damage to him and get the other half of his pen back! You will use a World object that has the following methods:

```
objectsAtPosition(lon: Number, lat: Number)

```

This returns an array of strings. One string for every object at the specified longitude (lon) and latitude (lat). The possible strings are:

`SUP` \- Super User Pen

`SFP` \- Server Fault Pen

`SOP` \- Stack Overflow Pen

`BD` \- Bad Dog

`GD` \- Good Dog

`G` \- Giygas

```
destroyObjectAt(lon: Number, lat: Number, i)

```

This destroys the object at the specified longitude, latitude, and index. For example, if at a specified longitude (lon) and latitude (lat) there are two or more objects, destroy the nth object in the array depending on what the index (i) is. You will destroy every Giygas and every Bad Dog.

```
giveTreatToObjectAt(lon: Number, lat: Number, i)

```

This gives a treat to the object at the specified longitude (lon), latitude (lat), and index. For example, if at a specified longitude (lon) and latitude (lat) there are two or more objects, give a treat to the nth object in the array depending on what the index (i) is. You will give all good dogs a treat.

```
collectObjectAt(lon: Number, lat: Number, i)

```

This collects the object at the specified longitude (lon) and latitude (lat), and index. For example, if at a specified longitude (lon) and latitude (lat) there are two or more objects, collect the nth object in the array depending on what the index (i) is. You will collect Billy's Stack Overflow pen and nothing else or else you die. Keep in mind that there is only *Billy's* Stack Overflow pen left in existence.

You will index through every longitude and latitude value (look below) and treat every object found as they should be treated.

Longitude and latitude rage from 0-10. Iterate incrementing by 1. Treat lon and lat as integers if you'd like. Use whatever-based indexing the language you're coding this in uses. This is , so shortest bytes in code wins.

Every item is an array. Here's an example of what the Array would be like. It's a 2D Array, 10x10. Longitude brings you right and latitude brings you down. So longitude with 5 and latitude with 4 would select this:

```
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['*Example*'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']

```

or

```
0→[item]1→[item]2→[item]3→[item]4→[item]5→[item]0↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]1↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]2↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]3↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item][*item*]←4[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]

```

In case you don't see it, it will select the item "*Example*" in the first one and the item "*item*" in the second one. I'm not sure how the human brain works, use your browser's search on page feature if you still don't see it.

PS:

If you don't know what a Giygas is, just know that you have to destroy it... or pray for your life by it (which ultimately destroys it anyway).

# Answer
> 2 votes
# C# - 272 bytes

I couldn't find too many tricks to do here outside of some for-loop shenanigans. I was hoping to use some Linq, but the index parts of the API made it difficult to make that work concisely.

```
class A{static void Main(string[] a){
for(int x=101,y,c;x-->0;)
for(y=101;y-->(c=0);)
foreach(string s in World.objectAtPosition(x,y)){
if(s=="SOP")World.collectObjectAt(x,y,c);
if(s=="BD"||s=="G")World.destroyObjectAt(x,y,c);
if(s=="GD")World.giveTreatToObjectAt(x,y,c);
c++;}}}

```

Here's my test code:

```
using System.Linq;
class A
{
    static void Main(string[] a)
    {
        for (int d = 0; d < 100; d++)
        {
        World.populate();

        for(int x=101,y,c;x-->0;)
        for(y=101;y-->(c=0);)
        foreach(string s in World.objectAtPosition(x,y))
        {
            if(s=="SOP")World.collectObjectAt(x,y,c);
            if(s=="BD"||s=="G")World.destroyObjectAt(x,y,c);
            if(s=="GD")World.giveTreatToObjectAt(x,y,c);
            c++;
        }

        World.verify();
        }
    }

    static class World
    {
        private static System.Collections.Generic.List<Item>[,] m_Map =
            new System.Collections.Generic.List<Item>[maxRange+1, maxRange+1];

        private static System.Random random = new System.Random();

        private const int maxRange = 100;
        private const int dogCount = 20;

        private class Item
        {
            public string id;
            public bool handled;

            public Item(string id)
            {
                this.id = id;
                this.handled = false;
            }
        }

        public static void populate()
        {
            for (int lat = 0; lat <= maxRange; lat++)
                for (int lon = 0; lon <= maxRange; lon++)
                    m_Map[lat, lon] = new System.Collections.Generic.List<Item>();
            addRandom("SUP");
            addRandom("SFP");
            addRandom("SOP");
            addRandom("G");
            for (int c = 0; c < dogCount; c++)
            {
                addRandom("BD");
                addRandom("GD");
            }
        }

        public static void verify()
        {
            for (int lat = 0; lat <= maxRange; lat++)
            {
                for (int lon = 0; lon <= maxRange; lon++)
                {
                    for (int index = 0; index < m_Map[lat, lon].Count; index++)
                    {
                        Item item = m_Map[lat, lon][index];
                        if (!item.handled && item.id != "SUP" && item.id != "SFP")
                        {
                            throw new System.Exception(string.Format("Didn't handle '{0}' at '{1},{2}:{3}'.",
                                item.id, lat, lon, index));
                        }
                    }
                }
            }
        }

        private static int randomCoord()
        {
            return random.Next(maxRange + 1);
        }

        private static void addRandom(string item)
        {
            int lat = randomCoord();
            int lon = randomCoord();
            m_Map[lat, lon].Add(new Item(item));
        }

        public static string[] objectAtPosition(int lat, int lon)
        {
            return m_Map[lat, lon].Select(item => item.id).ToArray();
        }

        public static void destroyObjectAt(int lat, int lon, int index)
        {
            Item item = m_Map[lat, lon][index];
            if (item.id == "G" || item.id == "BD")
                item.handled = true;
            else
                throw new System.InvalidOperationException(string.Format("Tried to destroy '{0}' at '{1},{2}-{3}'",
                    item.id, lat, lon, index));
        }

        public static void giveTreatToObjectAt(int lat, int lon, int index)
        {
            Item item = m_Map[lat, lon][index];
            if (item.id == "GD")
                item.handled = true;
            else
                throw new System.InvalidOperationException(string.Format("Tried to giveTreatTo '{0}' at '{1},{2}-{3}'",
                    item.id, lat, lon, index));
        }

        public static void collectObjectAt(int lat, int lon, int index)
        {
            Item item = m_Map[lat, lon][index];
            if (item.id == "SOP")
                item.handled = true;
            else
                throw new System.InvalidOperationException(string.Format("Tried to collect '{0}' at '{1},{2}-{3}'. You die.",
                    item.id, lat, lon, index));
        }
    }
}

```

---
Tags: code-golf
---


title: Double Factorial

text:
# Question
Title: Double Factorial
# Challenge

The objective is simple, in the shortest amount of bytes, write a function or program that takes a number and prints its double factorial.

The input must be taken from stdin or a function argument, and it must print the resulting double factorial to stdout.

Inbuilts are disallowed

# Answer
# Haskell 21

```
p n=product[n,n-2..1]

```
> 3 votes

# Answer
# CJam, ~~13~~ 12 bytes

```
ri,:)1~%1+:*

```

Expanded code:

```
ri            "Read the input as a string and convert it to integer";
  ,           "Create an array of 0 to input integers - 1";
   :)         "Increment each element in the array";
     1~       "Put 1 and do bitwise not to get -2";
       %      "Take every other integer starting from end";
        1+    "Add 1 to the array to account for result of 0 being 1";
          :*  "Reduce product to get double factorial";

```

At the end of the code, anything on stack is automatically printed to STDOUT in CJam.

Try it online here
> 3 votes

# Answer
# JavaScript, ES6, ~~38~~ 36 bytes

Wow this is huge!

```
f=a=>alert((g=n=>n>1?n*g(n-2):1)(a))
```

```
<input id=D /><button onclick="f(+D.value)">Run</button>
```

Of course I am just counting JS code. HTML is just for stack snippet demo.

Run it in latest Firefox browser.
> 2 votes

# Answer
# Matlab 16

```
@(n)prod(n:-2:1)

```

It is pretty sraight forward.
> 2 votes

# Answer
## r, 30

```
f=function(n)prod(seq(n,1,-2))

```
> 1 votes

# Answer
# Pyth: 11 character

```
u*GhH%2_UQ1

```

`Q` is the input value. `UQ` creates the list `[0, 1, 2, ..., Q-1]`, `_` inverts it, and `%2` removes every other element `[Q-1, Q-3, Q-5, ..., (1 or 0)]`. `u*GhH...1` reduces the list by multiplying the list elements (increased by 1) to `1`.

Try it here: Pyth Compiler/Executor
> 1 votes

---
Tags: code-golf, number, arithmetic
---


# Question
Title: All those duplicate questions deserve duplicate code to show them off
All those questions that are duplicates... Ignored and marginalized by society. It is just not... right. We have to do something. There surely must be love for them too.

They feel appreciated if a piece of code outputs a link to a duplicate question. But the duplicate questions are not so easily impressed. They are swept out off their feet only when the code when duplicated outputs a link to another duplicate question. The more the code can be duplicated and still output these links, the more the questions feel more loved.

Your task is to bring love and appreciation to these Stack Exchange pariahs.

---

Create a piece of code that when duplicated `k` times outputs a link to a duplicate question. `k` represents all the numbers in range `[1, N]`.

**Edit** I made code size matter because I realized you can write a program that can output as many links as you wanted.

# Rules:

**Language:**

* any language created prior to the post of this challenge is accepted. You may use a language already used in another answer.
* you may **not** use external resources (a database etc.)
* any encoding and any characters are allowed (including white spaces, new lines, non-ASCII). ~~Encoding is UTF-8.~~
* ~~code size does not matter~~. Size is measured in bytes.
* all duplications must be in the same language

**Code duplication:**

* ***clarification:*** the code must not duplicate itself. Simply put duplicating here means creating another code by copy-pasting the original one at the end of the last one obtained. Each will result in a new code that is run independently from the others.
* all the characters in the original code must be copy-pasted (including trailing new line (if any)). Each time the code pasted must be appended at the end.
* the code must create valid output when duplicated `1 (no duplication), 2, 3, 4, 5... N times`.
* It cannot skip a number (e.g. a code that creates valid output only when duplicated `1, 2, 3, 5, 6 times` will be considered only for `1, 2, 3` so `N = 3`)
* each time exactly one link must be output-ed.
* example (for what duplication means, not for valid output)

(python3) Original code (k = 1):

```
try:
  i
except NameError:
  i = 100
else:
  i = 200

if i == 100:
  print("stackoverflow.com/questions/" + str(i),end="")
else:
  print(i)

```

> k = 1 outputs stackoverflow.com/questions/100
> k = 2 outputs stackoverflow.com/questions/100200
> k = 3 outputs stackoverflow.com/questions/100200200

**Duplicate questions links (valid output):**

* Non-deleted questions from Programming Puzzles & Code Golf and Stack Overflow that were closed as duplicate prior to the time of the posting of this post are considered for this challenge.
* Helpful query to search for duplicate questions:

> is:question duplicate:yes

duplicates on PPCG and duplicates on SO

A valid link output for this question is any of these the two base links

```
stackoverflow.com/questions/1066589
stackoverflow.com/q/1066589
                    ^~~~~~^
                    this is referred as the link number in following paragraphs

```

to which you may add the prefix(es) `www.` and/or `http://`. You may also add a trailing `/`

Please note that after that you must not add anything (like the question title), even if that link results in a redirect to the question.

* You may not use a URL shortner service.
* You may not link to an answer or to another part of the page.
* The questions don't have to be duplicates of the same original or related in any way (`don't have to` means they can be if you want).
* For each time (for each `k`) a different question must be linked (two different links to the same question count as the same question)

**Multiple Submissions**

* You may post multiple answers with the same or different languages. Different posts can output the same link.

# Scoring

* Each link gives **1 point**.
* **Egoistic bonus**: **+0.5 points** for each link to your own question.
* **Forgive me bonus**: **+0.5 point** for each link to a question you voted to close (for whatever reason).
* **Judge Jury Executioner bonus**: **+0.5 point** for each link to your own question that you yourself voted to close (for whatever reason).
* **now what bonus**: **+0.5 points** for each link to a question closed as a duplicate to a question that has no answers.
* **train of thought bonus**: **+1 point** for each link to a question closed as a duplicate to another duplicate question (regardless of the length of the train)
* **dead end bonus**: **+1 point** for each link to a question closed as a duplicate of a question that was closed for a reason other than duplicate. (locked questions that exists because they have historical significance also don't count for this bonus).
* **George Santayana bonus**: **+1 point** for each link closed as a duplicate of a question by the same user.
* **You can't live without me bonus**: **+1.5 points** for each link whose number is prime.
* **Queen of the prom bonus**: **+2 points** for a link to a question of a user with all the questions (on the site of the linked question: PPCG or SO) closed as duplicates (at least 3, including the linked one). This bonus cannot be awarded more than once per user (even if you link to all 3 questions of this user, you are awarded the bonus only once, but you can be awarded this bonus again for a link to a question of another user or the same user but on the other site).
* All bonuses are cumulative. (this for instance has the effect that the *Judge Jury Executioner bonus* will always come with the *egoistic* and *forgive me* bonuses).
* **You don't love me enough penalty**:
    + `not_enough_penalty = 0.6` for `N = 2` (just 2 links)
    + `not_enough_penalty = 0.8` for `N = 3` (just 3 links)
    + `not_enough_penalty = 1` for `N >= 4` (4 or more links)

# **Winning Criteria**:

* `LinkPoints = 1 + bonuses` for each link
* **Points** = Sum(LinkPoints) * not\_enough\_penalty
* Votes = number of votes (upvotes - downvotes). Can be negative.
* ~~**Score** = 5 * Points + Votes~~
* **Size** = number of bytes of original code (k = 1).
* **Score** = (256-Size) / 32 * Points + Votes
Score is rounded to two decimals.
* **The winner** is the answer with the highest score. In the case of a tie the answer with the most votes wins.
* The winner will be awarded **two weeks** from the posting time of this question. If this question has intense activity at that time I will extend this.

# Post format

* Please specify the language, N - the number of duplication achieved, CodeSize and Points.
* Post the original piece of code.
* For each k in \[1..N\] post the link output-ed, the bonuses awarded and LinkPoints.
* Please add description where the way the code works is not obvious (for each k if needed) or if the language is not well-known.
* Express the formulas for Points and Score (without Votes, as they will be considered at the end of the challenge).

# Answer
> 2 votes
# C++, 212 bytes, 6 links, 10.31 points

```
#ifndef X
#define Y(N)s##N
#define X(N)Y(N)
#include<cstdio>
int i,j,k[]={2366,117,3818,3450,1047,2933},main;struct S{~S(){j+=k[i++];}};struct G{~G(){printf("stackoverflow.com/q/%d",j);}}g;
#endif
S X(__LINE__);

```

---

This code relies on the order of destructor to make it work (which seems to be well defined in this case), mainly because the preprocessor allows us to put a "prologue code" before the duplications, but not "epilogue code" because we don't know where does it end. But destructors run in reverse order, so we could put the final code (the print part) at the start as well.

The `k` array records the differences of successive link numbers. For now I just take links from the oldest pages. "6 links" seems to give the maximum score.

---

Resulting links:

1. https://stackoverflow.com/q/2366
2. https://stackoverflow.com/q/2483
3. https://stackoverflow.com/q/6301 (is prime +1.5)
4. https://stackoverflow.com/q/9751
5. https://stackoverflow.com/q/10798
6. https://stackoverflow.com/q/13731

Total score: (256 - 212)/32 × 7.5 = 10.31

# Answer
> 1 votes
## JavaScript (NodeJS) - 236 characters, including trailing newline

```
l=root.l||1;f=require('fs');t=(f.readFileSync(__filename)+'').split('\n');d="ge3oe gk05n gj341 gg8ah gfnar ga9i3 g602y g5mwi g2b9i fu75d g4lu0 4v1".split(' ');if(++l==t.length)console.log('https://stackoverflow.com/q/'+parseInt(d[l-2],36))

```

It uses a hardcoded list of question IDs, encoded in base 36. It reads its own source code, and only prints if it's on the last line of the file.

It results in a total of 12 questions, most closed by me:

Link points: 18.

**Score:** 11.25

# Answer
> 1 votes
# Tcl, 155 bytes, 15 links, 55.23 points

```
[proc f args {puts stackoverflow.com/q/[lindex {2366 2483 6301 9751 10798 13731 14599 16064 16233 16550 16704 18584 20146 22708 25376} [llength $args]]}]f

```

There is a trailing space.

Links:

1. https://stackoverflow.com/q/2366
2. https://stackoverflow.com/q/2483
3. https://stackoverflow.com/q/6301 (prime +1.5)
4. https://stackoverflow.com/q/9751
5. https://stackoverflow.com/q/10798
6. https://stackoverflow.com/q/13731
7. https://stackoverflow.com/q/14599 (target **deleted**; I think it should also qualify a bonus...)
8. https://stackoverflow.com/q/16064 (target not constructive +1)
9. https://stackoverflow.com/q/16233
10. https://stackoverflow.com/q/16550
11. https://stackoverflow.com/q/16704
12. https://stackoverflow.com/q/18584
13. https://stackoverflow.com/q/20146
14. https://stackoverflow.com/q/22708
15. https://stackoverflow.com/q/25376

Score = (256 - 155) / 32 * 17.5 = 55.23

The score can probably be improved by using another set of questions with more bonuses.

# Answer
> 0 votes
## STATA - 252 characters (including trailing newline) N = the number of duplicates on stackoverflow.com

Ignore the trailing space. I didn't know how to adjust this properly. Someone help me format this reasonably.

First this code tries to increment a counter variable. If that fails, it generates a new local variable and sets it equal to 2. Then it decrements it and creates a new variable to keep track of whether or not the page has the phrase " as duplicate by `<`a" in it. Until a line contains that phrase, the following is run:

Create a local variable to hold the url (using the counter as the question number). Copy the file to the local file a and replace it. Filter a (and move to b the result) by replacing "\>" with "\>\n" and replace b if necessary. Then read in b, clearing current data (i.e. dropping the d variable) with a string variable representing each line. If the phrase appears in any line, d becomes at least 1, thus ending the loop.

The last line displays the url and continues onto the next line because of the /// comment.

Thus, when k\>1, the last line of the first part becomes

`cap di`u' ///
cap loc \`c'++`

which is equivalent to:

`cap di`u' cap loc \`c'++`

which would throw a syntax error if the capture (cap) command were not used to capture the return code and prevent execution of the line, thus not printing the url unless it is the last of the k copies of the code.

```
cap loc \`c'++
if _rc>0{
loc c=2
}
loc \`c'--
g d=0
while d<1{
loc u="http://stackoverflow.com/q/\`c'"
copy \`u' "a",replace
filef "a""b",f(>)t(>\n)r
infix str l 1-9999 using "b",clear
egen d=max(strpos(l," as duplicate by `<a"))
loc \`c'++
}
cap di\`u' ///

```

Possible better approach (explanation coming soon):

```
cap so d
if _rc>0{
loc c=9761
}
loc f="http://stackoverflow.com/"
loc u="`f'search?page=`c'&tab=newest&q=duplicate%3ayes"
infix str l 1-9999 using `u',clear
g d="`f'q/"+regexs(1) if regexm(l,f="/questions([0-9]+)")
loc `c'--
cap l d in 1

```

---
Tags: code-challenge, source-layout
---


title: Cover a Region with Rectangles

text:
# Question
Title: 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.

# Answer
> 12 votes
# 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

# Answer
> 13 votes
# 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?

# Answer
> 8 votes
# 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.

# Answer
> 5 votes
# 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}}

```

# Answer
> 4 votes
# 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.

1. Each point becomes a 1x1 square (preprocessing)
2. 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>
```

# Answer
> 4 votes
# 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.

# Answer
> 3 votes
# 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.

---
Tags: code-golf, geometry, grid
---