24
\$\begingroup\$

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:

    enter image description here

  • The following shapes are invalid:

    invalid1 invalid2 invalid3

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:

    touching

  • 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.
\$\endgroup\$
  • \$\begingroup\$ What about rotations of the same shape? Are they distinct? \$\endgroup\$ – Martin Ender Sep 30 '14 at 12:39
  • \$\begingroup\$ If I take a bite out of the side of the shape, is it ok to have a foreground (black) line one pixel wide? Or does it have to be 3 pixels wide, so the incoming and outgoing line don't touch? or is it Ok to have it 2 pixels wide, so the incoming and outgoing line touch, but don't overlap? \$\endgroup\$ – Level River St Sep 30 '14 at 12:49
  • \$\begingroup\$ Some more questions: 1. Can the border of the 109x109 image act as one boundary of the shape? 2. If the line thickness is up to me, can I just say it's 200 pixels, so that the shape is just white pixels on a black image? 3. Is the shape connected if its pixels only touch along a corner? 4. I'm not a big fan of the character limit. A lot of languages might use 3/4 of that just to set up the exact output specifications. \$\endgroup\$ – Martin Ender Sep 30 '14 at 12:52
  • 2
    \$\begingroup\$ Question, how'd you get 1009? \$\endgroup\$ – Claudiu Sep 30 '14 at 17:20
  • 1
    \$\begingroup\$ Which of these shapes are valid and holeless? i.imgur.com/FSV0nHz.png \$\endgroup\$ – Sparr Sep 30 '14 at 23:26
25
+100
\$\begingroup\$

Python + Pycairo, 2100 shapes

Let's start with the obvious.

Animation 1

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.

\$\endgroup\$
  • \$\begingroup\$ Very nice. Simple idea, well executed. Won't be the winning score, but sets a good bar for further entries. \$\endgroup\$ – Sparr Sep 30 '14 at 20:39
  • \$\begingroup\$ ... *2, as Rotations [...] count as unique. \$\endgroup\$ – edc65 Oct 2 '14 at 17:14
  • \$\begingroup\$ @edc65: Actually *4, since it's not symmetric. \$\endgroup\$ – justhalf Oct 4 '14 at 3:34
19
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ A: The answer remains "yes", although I see now it is a bit odd. B. I see your point now and have made an edit to clarify, sorry for the confusion. \$\endgroup\$ – jsh Oct 1 '14 at 11:02
  • \$\begingroup\$ C: That's not a problem. A pixel is now defined as the smallest unit of drawing used. \$\endgroup\$ – jsh Oct 1 '14 at 11:15
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Are you able to provide a CDF file so I can try this out? \$\endgroup\$ – jsh Sep 30 '14 at 15:44
  • 1
    \$\begingroup\$ @jsh Try this \$\endgroup\$ – Martin Ender Sep 30 '14 at 15:48
  • \$\begingroup\$ I think all solutions that depend on random numbers will require a brute-force to validate. I'm not sure if you're doing a pixel by pixel check, but you could try saving each output to monochromatic bitmap (small filesize) and comparing the hashes. I imagine that's as fast as you'll get for image comparisons. \$\endgroup\$ – stokastic Sep 30 '14 at 17:13
  • \$\begingroup\$ @stokastic I'm currently building a very naive hash (sum of all pixel coordinates), and then I'm checking the colliding bins in detail. The problem is, no matter how sophisticated an approach I use for collision checking, the generation method is so slow, that I won't even be able to solve more than a few 10k or 100k seeds in a reasonable amount of time. There are several ways to considerably speed up the algorithm though, I think, so I might look into that at some point. \$\endgroup\$ – Martin Ender Sep 30 '14 at 17:49
  • \$\begingroup\$ @MartinBüttner You probably tested it already (or mathematica doesn't support it), but a straight up file-hash might be quicker. Just a suggestion if you haven't tried that. \$\endgroup\$ – stokastic Sep 30 '14 at 18:13
1
\$\begingroup\$

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")
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you give the image for n=0? And also can you explain how you achieve 10^395? \$\endgroup\$ – justhalf Oct 4 '14 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.