Enclose 1009 pixels

Question

Output is a shape that encloses 1009 pixels.

• The shape must take the form of a single, closed, non-intersecting loop.

Input is a positive non-zero integer.

• Each input must yield output that is unique — that is, each output must be unique from those generated using a lower input.

Victory is decided by the largest input limit:

• Your submission's input limit is regarded as 1 less than the lowest input that gives non-unique or otherwise invalid output.
• For instance, if valid and unique output is produced for an input of 1, 2 or 3 but not 4, your input limit is 3.

There is a 1009 byte limit on source code. If there is a draw the entry with the fewest bytes wins.

---

Restrictions and clarifications:

• A shape's maximum size is 109 by 109 pixels. Size includes the line used to draw the shape.
• A line is constant width.
• The enclosed space must be entirely enclosed by the line - you can't use the boundary of the image file.
• The enclosed 1009 pixels refers only to enclosed space. It does not include the line.
• Output is an image.
• There are no further graphical restrictions - e.g. on colour, line thickness etc.
• An output's uniqueness refers only to the enclosed space. Changes to the line or other graphical changes are irrelevant if the enclosed space is not unique.
• A translation of shape isn't unique. Rotations, reflections and any other transformations count as unique.
• Output must be reproducible — the same input will always give the same output
• There needn't be a relation between outputs, consecutive or otherwise.
• Outside of a submission's 'input limit' there is no defined output.
• No other input or fetching of external data is permitted.
• A line must be continuous — i.e. pixels must touch (touching a corner counts).
• A pixel is the smallest unit of 'drawing' used by your method of drawing, and won't necessarily correspond to a screen pixel.

---

Examples:

• Here is an example of a valid shape:

  

• The following shapes are invalid:

  

EDIT: Line touching:

• Enclosed space must be continuous which is defined as pixels touching. Touching corners counts.

• A line cannot enclose any space on its outer side. This image posted by @Sparr illustrates this point - only the first shape on each row are valid:

  

• The outer sides of a line may touch, but not in a way that encloses space.

• Touching lines may not overlap - e.g. two touching 1 pixel thick lines would have a combined thickness of 2px, never 1px.

Answer 1

Python + Pycairo, 2¹⁰⁰ shapes

Let's start with the obvious.

from cairo import *
from sys import argv

n = int(argv[1]) - 1

s = ImageSurface(FORMAT_ARGB32, 109, 109); c = Context(s)
c.set_antialias(ANTIALIAS_NONE); c.set_line_width(1); c.translate(54, 54)
def pixel(x, y): c.rectangle(x, y, 1, 1); c.fill()

W, H, R = 100, 10, 9
X1, Y1 = -W / 2 - 1, -H / 2 - 1
X2, Y2 = X1 + W + 1, Y1 + H + 1

pixel(X2 - 1, Y1)
c.move_to(X1, Y1 + 1); c.line_to(X1, Y2 + 1)
c.move_to(X2 + 1, Y1); c.line_to(X2 + 1, Y1 + R + 1);
c.move_to(X2, Y1 + R + 1); c.line_to(X2, Y2 + 1)
c.stroke()

for i in xrange(W):
    offset = (n >> i) & 1
    for y in Y1, Y2: pixel(X1 + i, y + offset)

s.write_to_png("o.png")

Takes the number on the command line and writes o.png.

Answer 2

BBC Basic, score 10^288 (minus 1 if zero not counted)

Download interepreter at http://sourceforge.net/projects/napoleonbrandy/ (not my usual BBC basic interpreter, that one doesn't support long enough strings.)

To encode a lot of information, you need a lot of perimeter. That means a thin shape. I start with a vertical bar of 49 pixels at the left, and add ten tentacles of 96 pixels to it. Each tentacle can encode 96 bits in a similar manner to @ell's solution, a total of 960 bits.

As BBC Basic cannot handle numbers that large, a number of up to 288 decimal digits is input as a string, and each set of 3 decimal digits is converted to a 10-bit binary number. Each bit is then used to wiggle one of the tentacles up by one pixel if it is a 1 (but not if it is a 0.) The program can handle up to 288/3=96 such sets of 3 digits

    1MODE1:VDU19,0,7;0;19,15,0;0;               :REM select an appropriate screen mode and change to black drawing on white background
   10INPUT a$
   20a$=STRING$(288-LEN(a$)," ")+a$             :REM pad input up to 288 characters with leading spaces
   50RECTANGLE0,0,8,200                         :REM draw a rectangle at the left, enclosing 49 pixels
   60FOR n=0 TO 95
   70  b=VAL(MID$(a$,n*3+1,3))                  :REM extract 3 characters from a$ and convert to number
   80  FOR m=0 TO 9                             :REM plot the ten tentacles
   90    PLOT71,n*4+8,m*20+8+(b/2^m AND 1)*4    :REM plot (absolute coordinates) a background colour pixel for tentacle m at horizontal distance n
  100    POINT BY 0,-4                          :REM offsetting vertically by 1 pixel according to the relevant bit of b
  110    POINT BY 4,4
  120    POINT BY -4,4                          :REM then plot foreground colour pixels (relative coordinates) above, below and to the right.
  130  NEXT
  140NEXT

Output

A typical output for a 288-digit number. Note that 999 is 1111100111 in binary. You can see how the sets of 9 digits cause the tentacles to undulate.

Technicalities

A.The answer to Martin's point 3 "is the shape connected if its pixel's touch only along a corner?" was "yes" so I understand my answer complies. Nevertheless, if you alternate (for example) 999's and 000's in every row, it looks very busy.

B. If we view this as a rectangle with bites taken out of the side, you can see that I allowed three pixels between each pair of adjacent tentacles, to ensure that the black line round the outside never touches itself. There is no specific rule on this (I hope my reason for asking is clearer in the light of my answer.) If the line is allowed to touch itself on the OUTSIDE of the shape, I could move the tentacles together and use less pixels for the vertical bar (and so make the tentacles a bit longer.) It would, however become very confusing to determine by eye whether a pixel was inside or outside the shape, so I think my interpretation that the outside of the black line should never touch itself is best.

C. BBC basic in this screen mode treats a 2x2 square of screen pixels as a single pixel. I've left this as it is, because it helps viewing if the shape is not too tiny. Each one of these BBC basic pixels is considered as a box of 4x4 logical units. From the start, the developers of BBC basic had the foresight to realise that one day screen resolutions would increase, so they made the logical resolution higher than the physical resolution.

Answer 3

Mathematica, 496 bytes, Score: large-ish (>1157)

The lower bound I've got there is ridiculously low, but I haven't found a better way than brute force to check yet.

SeedRandom@Input[];
g = 0 &~Array~{109, 109};
g[[2, 2]] = 1;
h = {{2, 2}};
For[n = 1, n < 1009,
  c = RandomChoice@h;
  d = RandomChoice[m = {{1, 0}, {0, 1}}];
  If[FreeQ[e = c + d, 1 | 109] && 
    Count[g[[2 ;; e[[1]], 2 ;; e[[2]]]], 0, 2] == 1,
   ++n;
   h~AppendTo~e;
   g[[## & @@ e]] = 1
   ];
  ];
(
    c = #;
    If[e = c + #; g[[## & @@ e]] < 1,
       g[[## & @@ e]] = 2
       ] & /@ Join @@ {m, -m}) & /@ h;
ArrayPlot[g, ImageSize -> 109, PixelConstrained -> True, 
 Frame -> 0 > 1]

I haven't golfed this yet, because there was no need to. I'll do that once someone proves they are actually tying with me.

The algorithm is basically doing a flood-fill from the top-left corner of the 109x109 image (offset by one pixel to allow for the line) and when I've flooded 1009 cells, I stop and mark the border. You said colours are up to us, so the background is white, the line is black and the interior is grey (I can remove the gray for a handful of characters if necessary).

The flood fill is quite constrained, but that ensures that I don't have to worry about about holes. Relaxing these constraints will probably dramatically increase my (yet unknown) score.

I'll try to put some lower bounds on the score now.

Answer 4

Python 2, Score > 10^395

It is extremely slow, and I haven't actually managed to get any result other than n=0, but if you want to test it lower SIZE (the number of pixels) and BOUND the maximum side length of the bounding square and you should be able to get plenty of results. It was very difficult to try and calculate how many it would produce; I am fairly confident that the lower bound I give is accurate, but I suspect the actual count to be significantly larger, and I may try to improve on it later.

import sys
import pygame
sys.setrecursionlimit(1100)

def low(s):
    return min(sum(e[1] for e in s[:i+1]) for i in range(len(s)))
def high(s):
    return max(sum(e[1] for e in s[:i+1])+s[i][0] for i in range(len(s)))

BOUND = 109
SIZE = 1009

def gen(n,t=0):
    if n <= (BOUND-t)*BOUND:
        for i in range(1,min(n,BOUND)):
            for r in gen(n-i,t+1):
                a,b=r[0]
                for x in range(max(1-a,high(r)-low(r)-BOUND),i):
                    yield [(i,0),(a,x)]+r[1:]
        yield [(n,0)]

def create(n):
    g=gen(SIZE)
    for i in range(n+1):shape=g.next()
    s=pygame.Surface((BOUND+2,BOUND+2))
    l=low(shape);x=0
    for y,(t,o) in enumerate(shape):
        x+=o;pygame.draw.line(s,(255,255,255),(x-l+1,y+1),(x-l+t,y+1))
    out=[]
    for x in range(BOUND+2):
        for y in range(BOUND+2):
            if all((0,0,0)==s.get_at((x+dx,y+dy))for dx,dy in[(-1,0),(1,0),(0,-1),(0,1)]if 0<=x+dx<BOUND+2 and 0<=y+dy<BOUND+2):
                out.append((x,y))
    for x,y in out:
        s.set_at((x,y),(255,255,255))
    pygame.image.save(s,"image.png")