title: Draw an Image with a Snake

text:
# Question
Title: Draw an Image with a Snake
Imagine a continuous 2-dimensional path that can only turn left, right, or go straight, cannot intersect itself, and must fill a rectangular grid such as the grid of pixels in an image. We'll call this kind of path a *snake*.

This enlarged example shows a snake path in a 10×4 grid that starts out red and increases in hue by about 2% at every step until it is purple. (The black lines are only to emphasize the direction it takes.)

# Goal

The goal in this popularity contest is to write an algorithm that attempts to recreate a given image using a single snake whose color continuously changes by small amounts.

Your program must take in a true-color image of any size as well as a floating point value between 0 and 1 inclusive, the *tolerance*.

*Tolerance* defines the maximum amount the color of the snake is allowed to change in each pixel sized step. We'll define the distance between two RGB colors as the Euclidean distance between the two RGB points when arranged on an RGB color cube. The distance will then be normalized so the maximum distance is 1 and the minimum distance is 0.

**Color distance pseudocode:** (Assumes all input values are integers in the range `[0, 255]`; output is normalized.)

```
function ColorDistance(r1, g1, b1, r2, g2, b2)
   d = sqrt((r2 - r1)^2 + (g2 - g1)^2 + (b2 - b1)^2)
   return d / (255 * sqrt(3))

```

If the result of calling this function on the snake's current color and another color is greater than the given tolerance then the snake may not change into that other color.

**If you prefer, you may use a different color distance function.** It must be something accurate and well documented such as those listed at http://en.wikipedia.org/wiki/Color\_difference. You also must normalize it to be in within `[0, 1]`, i.e. the maximum possible distance must be 1 and the minimum must be 0. Tell us in your answer if you use a different distance metric.

# Test Images

You should of course post your output images (and even animations of the snake growing if you want). I suggest posting a variety of these images using different low tolerances (maybe around 0.005 to 0.03).

(Larger Great Wave)

# Win Criteria

As stated, this is a popularity contest. The highest voted answer will win. Answers that provide the most accurate and aesthetically pleasing "snake path" depiction of the input images should be voted up.

**Any user who is found to be maliciously submitting images that are not actual snakes will be disqualified forever.**

# Notes

* Only one snake path may be used and it must completely fill the image without touching the same pixel twice.
* The snake may start and end anywhere in the image.
* The snake may start as any color.
* The snake must stay in the bounds of the image. The bounds are not cyclic.
* The snake cannot move diagonally or more than one pixel at a time.

# Answer
> 25 votes
## Python

I generate a dynamic path to minimize the color changes as the snake travels. Here are some images:

**tolerance = 0.01**

Cyclic color paths for the above images (blue to red, getting greener as it repeats):

The path is generated by starting with some initial path, then adding 2x2 loops onto it until the image is filled. The advantage of this method is that the loops can be added anywhere on the path, so you can't paint yourself into a corner and have more freedom to build the path you want. I keep track of the possible loops adjacent to the current path and store them in a heap, weighted by the color change along the loop. I then pop off the loop with the least color change and add it to the path, and repeat until the image is filled.

I actually track the loops alone ('DetourBlock' in the code), then reconstruct the path; this was a mistake as there are some special cases for odd width/height and I spent several hours debugging the reconstruction method. Oh well.

The path generation metric needs tuning and I also have an idea for better colorization, but I thought I'd get this out first since it works quite well. Except for this one, which seems better in some of the fixed paths:

Here's the Python code, with apologies for my atrocious coding habits:

```
# snakedraw.py
# Image library: Pillow
# Would like to animate with matplotlib... (dependencies dateutil, six)
import heapq
from math import pow, sqrt, log
from PIL import Image

tolerance = 0.001
imageList = [ "lena.png", "MonaLisa.png", "Mandrill.png", "smallGreatWave.png", "largeGreatWave.png", "random.png"]

# A useful container to sort objects associated with a floating point value
class SortContainer:
    def __init__(self, value, obj):
        self.fvalue = float(value)
        self.obj = obj
    def __float__(self):
        return float(self.fvalue)
    def __lt__(self, other):
        return self.fvalue < float(other)
    def __eq__(self, other):
        return self.fvalue == float(other)
    def __gt__(self, other):
        return self.fvalue > float(other)

# Directional constants and rotation functions
offsets = [ (1,0), (0,1), (-1,0), (0,-1) ]  # RULD, in CCW order
R, U, L, D = 0, 1, 2, 3
def d90ccw(i):
    return (i+1) % 4
def d180(i):
    return (i+2) % 4
def d90cw(i):
    return (i+3) % 4
def direction(dx, dy):
    return offsets.index((dx,dy))

# Standard color metric: Euclidean distance in the RGB cube. Distance between opposite corners normalized to 1.
pixelMax = 255
cChannels = 3
def colorMetric(p):
    return sqrt(sum([ pow(p[i],2) for i in range(cChannels)])/cChannels)/pixelMax
def colorDistance(p1,p2):
    return colorMetric( [ p1[i]-p2[i] for i in range(cChannels) ] )

# Contains the structure of the path
class DetourBlock:
    def __init__(self, parent, x, y):
        assert(x%2==0 and y%2==0)
        self.x = x
        self.y = y
        self.parent = None
        self.neighbors = [None, None, None, None]
    def getdir(A, B):
        dx = (B.x - A.x)//2
        dy = (B.y - A.y)//2
        return direction(dx, dy)

class ImageTracer:
    def __init__(self, imgName):

        self.imgName = imgName
        img = Image.open(imgName)
        img = img.convert(mode="RGB")       # needed for BW images
        self.srcImg = [ [ [ float(c) for c in img.getpixel( (x,y) ) ] for y in range(img.size[1]) ] for x in range(img.size[0])]
        self.srcX = img.size[0]
        self.srcY = img.size[1]

        # Set up infrastructure
        self.DetourGrid = [ [ DetourBlock(None, 2*x, 2*y) \
                    for y in range((self.srcY+1)//2)] \
                    for x in range((self.srcX+1)//2)]
        self.dgX = len(self.DetourGrid)
        self.dgY = len(self.DetourGrid[0])
        self.DetourOptions = list()    # heap!
        self.DetourStart = None
        self.initPath()

    def initPath(self):
        print("Initializing")
        if not self.srcX%2 and not self.srcY%2:
            self.AssignToPath(None, self.DetourGrid[0][0])
            self.DetourStart = self.DetourGrid[0][0]
        lastDB = None
        if self.srcX%2:     # right edge initial path
            self.DetourStart = self.DetourGrid[-1][0]
            for i in range(self.dgY):
                nextDB = self.DetourGrid[-1][i]
                self.AssignToPath(lastDB, nextDB)
                lastDB = nextDB
        if self.srcY%2:     # bottom edge initial path
            if not self.srcX%2:
                self.DetourStart = self.DetourGrid[-1][-1]
            for i in reversed(range(self.dgX-(self.srcX%2))):          # loop condition keeps the path contiguous and won't add corner again
                nextDB =  self.DetourGrid[i][-1]
                self.AssignToPath(lastDB, nextDB)
                lastDB = nextDB

    # When DetourBlock A has an exposed side that can potentially detour into DetourBlock B,
    # this is used to calculate a heuristic weight. Lower weights are better, they minimize the color distance
    # between pixels connected by the snake path
    def CostBlock(self, A, B):
        # Weight the block detour based on [connections made - connections broken]
        dx = (B.x - A.x)//2
        dy = (B.y - A.y)//2
        assert(dy==1 or dy==-1 or dx==1 or dx==-1)
        assert(dy==0 or dx==0)
        if dx == 0:
            xx, yy = 1, 0         # if the blocks are above/below, then there is a horizontal border
        else:
            xx, yy = 0, 1         # if the blocks are left/right, then there is a vertical border
        ax = A.x + (dx+1)//2
        ay = A.y + (dy+1)//2
        bx = B.x + (1-dx)//2
        by = B.y + (1-dy)//2
        fmtImg = self.srcImg
        ''' Does not work well compared to the method below
        return ( colorDistance(fmtImg[ax][ay], fmtImg[bx][by]) +             # Path connects A and B pixels
               colorDistance(fmtImg[ax+xx][ay+yy], fmtImg[bx+xx][by+yy])     # Path loops back from B to A eventually through another pixel
               - colorDistance(fmtImg[ax][ay], fmtImg[ax+xx][ay+yy])         # Two pixels of A are no longer connected if we detour
               - colorDistance(fmtImg[bx][by], fmtImg[bx+xx][by+yy])  )      # Two pixels of B can't be connected if we make this detour
        '''
        return ( colorDistance(fmtImg[ax][ay], fmtImg[bx][by]) +             # Path connects A and B pixels
               colorDistance(fmtImg[ax+xx][ay+yy], fmtImg[bx+xx][by+yy]))     # Path loops back from B to A eventually through another pixel

    # Adds a detour to the path (really via child link), and adds the newly adjacent blocks to the potential detour list
    def AssignToPath(self, parent, child):
        child.parent = parent
        if parent is not None:
            d = parent.getdir(child)
            parent.neighbors[d] = child
            child.neighbors[d180(d)] = parent
        for (i,j) in offsets:
            x = int(child.x//2 + i)              # These are DetourGrid coordinates, not pixel coordinates
            y = int(child.y//2 + j)
            if x < 0 or x >= self.dgX-(self.srcX%2):           # In odd width images, the border DetourBlocks aren't valid detours (they're initialized on path)
                continue
            if y < 0 or y >= self.dgY-(self.srcY%2):
                continue
            neighbor = self.DetourGrid[x][y]
            if neighbor.parent is None:
                heapq.heappush(self.DetourOptions, SortContainer(self.CostBlock(child, neighbor), (child, neighbor)) )

    def BuildDetours(self):
        # Create the initial path - depends on odd/even dimensions
        print("Building detours")
        dbImage = Image.new("RGB", (self.dgX, self.dgY), 0)
        # We already have our initial queue of detour choices. Make the best choice and repeat until the whole path is built.
        while len(self.DetourOptions) > 0:
            sc = heapq.heappop(self.DetourOptions)       # Pop the path choice with lowest cost
            parent, child = sc.obj
            if child.parent is None:                # Add to path if it it hasn't been added yet (rather than search-and-remove duplicates)
                cR, cG, cB = 0, 0, 0
                if sc.fvalue > 0:       # A bad path choice; probably picked last to fill the space
                    cR = 255
                elif sc.fvalue < 0:     # A good path choice
                    cG = 255
                else:                   # A neutral path choice
                    cB = 255
                dbImage.putpixel( (child.x//2,child.y//2), (cR, cG, cB) )
                self.AssignToPath(parent, child)
        dbImage.save("choices_" + self.imgName)

    # Reconstructing the path was a bad idea. Countless hard-to-find bugs!
    def ReconstructSnake(self):
        # Build snake from the DetourBlocks.
        print("Reconstructing path")
        self.path = []
        xi,yi,d = self.DetourStart.x, self.DetourStart.y, U   # good start? Okay as long as CCW
        x,y = xi,yi
        while True:
            self.path.append((x,y))
            db = self.DetourGrid[x//2][y//2]                     # What block do we occupy?
            if db.neighbors[d90ccw(d)] is None:                  # Is there a detour on my right? (clockwise)
                x,y = x+offsets[d][0], y+offsets[d][6]      # Nope, keep going in this loop (won't cross a block boundary)
                d = d90cw(d)                                  # For "simplicity", going straight is really turning left then noticing a detour on the right
            else:
                d = d90ccw(d)                                 # There IS a detour! Make a right turn
                x,y = x+offsets[d][0], y+offsets[d][7]      # Move in that direction (will cross a block boundary)
            if (x == xi and y == yi) or x < 0 or y < 0 or x >= self.srcX or y >= self.srcY:                         # Back to the starting point! We're done!
                break
        print("Retracing path length =", len(self.path))       # should = Width * Height

        # Trace the actual snake path
        pathImage = Image.new("RGB", (self.srcX, self.srcY), 0)
        cR, cG, cB = 0,0,128
        for (x,y) in self.path:
            if x >= self.srcX or y >= self.srcY:
                break
            if pathImage.getpixel((x,y)) != (0,0,0):
                print("LOOPBACK!", x, y)
            pathImage.putpixel( (x,y), (cR, cG, cB) )
            cR = (cR + 2) % pixelMax
            if cR == 0:
                cG = (cG + 4) % pixelMax
        pathImage.save("path_" + self.imgName)

    def ColorizeSnake(self):
        #Simple colorization of path
        traceImage = Image.new("RGB", (self.srcX, self.srcY), 0)
        print("Colorizing path")
        color = ()
        lastcolor = self.srcImg[self.path[0][0]][self.path[0][8]]
        for i in range(len(self.path)):
            v = [ self.srcImg[self.path[i][0]][self.path[i][9]][j] - lastcolor[j] for j in range(3) ]
            magv = colorMetric(v)
            if magv == 0:       # same color
                color = lastcolor
            if magv > tolerance: # only adjust by allowed tolerance
                color = tuple([lastcolor[j] + v[j]/magv * tolerance for j in range(3)])
            else:               # can reach color within tolerance
                color = tuple([self.srcImg[self.path[i][0]][self.path[i][10]][j] for j in range(3)])
            lastcolor = color
            traceImage.putpixel( (self.path[i][0], self.path[i][11]), tuple([int(color[j]) for j in range(3)]) )
        traceImage.save("snaked_" + self.imgName)

for imgName in imageList:
    it = ImageTracer(imgName)
    it.BuildDetours()
    it.ReconstructSnake()
    it.ColorizeSnake()

```

And some more images at a **very low tolerance of 0.001**:

And also the great wave path because it's neat:

## EDIT

The path generation seems better when minimizing the color distance between the average colors of adjacent blocks, rather than minimizing the sum of the color distances between their adjacent pixels. Also, it turns out you can average the colors of any two tolerance-compliant snake paths and end up with another tolerance-compliant snake path. So I traverse the path both ways and average them, which smooths out a lot of the artifacts. Zombie Lena and Scary Hands Mona look much better. Final versions:

**Tolerance 0.01**:

**Tolerance 0.001**:

# Answer
> 17 votes
## Java

My program generate a snake path for a given width & height, using an algorithm similar to the one that generates the Hilbert curve.

*(little game: in the above picture, the snake starts at the top left corner. Can you find where he ends? Good luck :)*

Here are the results for various tolerance values :

**Tolerance = 0.01**

**Tolerance = 0.05**

**Tolerance = 0.1**

**Tolerance = 0.01**

**With 4x4 pixel blocks & the path visible**

**Computing the snake path**

A snake path is stored in a double dimension integer array. The snake always enters the grid by the upper left corner. There are 4 basic operation my program can do on a given snake path:

* create a new snake path for a grid of width 1 or height 1. The path is just a simple line that goes left to right or up to down, depending on the case.
* increase the grid height, by adding at the top a snake path from left to right, then by mirroring the grid (the snake must always enter the grid by the upper left corner)
* increate the grid width, by adding at the left a snake path from top to bottom, then by flipping the grid (the snake must always enter the grid by the upper left corner)
* double the dimension of the grid using an "Hilbert style" algorithm (see description below)

Using a series of these atomic operations, the program is able to generate a snake path of any given size.

The code below computes (in reverse order) which operations will be needed to obtain a given width & height. Once computed, the actions are executed one by one until we got a snake path of the expected size.

```
enum Action { ADD_LINE_TOP, ADD_LINE_LEFT, DOUBLE_SIZE, CREATE};

public static int [][] build(int width, int height) {
    List<Action> actions = new ArrayList<Action>();
    while (height>1 && width>1) {
        if (height % 2 == 1) {
            height--;
            actions.add(Action.ADD_LINE_TOP);
        }
        if (width % 2 == 1) {
            width--;
            actions.add(Action.ADD_LINE_LEFT);
        }
        if (height%2 == 0 && width%2 == 0) {
            actions.add(Action.DOUBLE_SIZE);
            height /= 2;
            width /= 2;
        }
    }
    actions.add(Action.CREATE);
    Collections.reverse(actions);
    int [][] tab = null;
    for (Action action : actions) {
        // do the stuff
    }

```

**Doubling the snake path size:**

The algorithm that double the size works as follow:

Consider this node which is linked to RIGHT and BOTTOM. I want to double its size.

```
 +-
 |

```

There are 2 ways to double its size and keep the same exits (right and bottom):

```
 +-+-
 |
 +-+
   |

```

or

```
+-+
| |
+ +-
|

```

To determine which one to choose, I need to handle for each node direction a "shift" value, indicating if the exit door is shifted left/right or up/down. I follow the path as the snake would do, and update the shift value along the path. The shift value determines uniquely which expanded block I need to use for the next step.

# Answer
> 10 votes
# Python

Here's a very simple algorithm to get things started. It starts at the top left of the image and spirals clockwise inwards, making the color as close as possible to the next pixel's color while staying within the tolerance.

```
import Image

def colorDist(c1, c2): #not normalized
    return (sum((c2[i] - c1[i])**2 for i in range(3)))**0.5

def closestColor(current, goal, tolerance):
    tolerance *= 255 * 3**0.5
    d = colorDist(current, goal)
    if d > tolerance: #return closest color in range
        #due to float rounding this may be slightly outside of tolerance range
        return tuple(int(current[i] + tolerance * (goal[i] - current[i]) / d) for i in range(3))
    else:
        return goal

imgName = 'lena.png'
tolerance = 0.03

print 'Starting %s at %.03f tolerance.' % (imgName, tolerance)

img = Image.open(imgName).convert('RGB')

imgData = img.load()
out = Image.new('RGB', img.size)
outData = out.load()

x = y = 0
c = imgData[x, y]
traversed = []
state = 'right'

updateStep = 1000

while len(traversed) < img.size[0] * img.size[1]:
    if len(traversed) > updateStep and len(traversed) % updateStep == 0:
        print '%.02f%% complete' % (100 * len(traversed) / float(img.size[0] * img.size[1]))
    outData[x, y] = c
    traversed.append((x, y))
    oldX, oldY = x, y
    oldState = state
    if state == 'right':
        if x + 1 >= img.size[0] or (x + 1, y) in traversed:
            state = 'down'
            y += 1
        else:
            x += 1
    elif state == 'down':
        if y + 1 >= img.size[1] or (x, y + 1) in traversed:
            state = 'left'
            x -= 1
        else:
            y += 1
    elif state == 'left':
        if x - 1 < 0 or (x - 1, y) in traversed:
            state = 'up'
            y -= 1
        else:
            x -= 1
    elif state == 'up':
        if y - 1 < 0 or (x, y - 1) in traversed:
            state = 'right'
            x += 1
        else:
             y -= 1
    c = closestColor(c, imgData[x, y], tolerance)

out.save('%.03f%s' % (tolerance, imgName))
print '100% complete'

```

It takes a minute or two to run the larger images, though I'm sure the spiraling logic could be vastly optimized.

# Results

They're interesting but not gorgeous. Amazingly a tolerance above 0.1 produces quite accurate looking results.

The Great Wave at 0.03 tolerance:

Mona Lisa at 0.02 tolerance:

Lena at 0.03 tolerance, then 0.01, then 0.005, then 0.003:

Misc stuff at 0.1 tolerance, then 0.07, then 0.04, then 0.01:

# Answer
> 10 votes
# Cobra

```
@number float
use System.Drawing
class Program
    var source as Bitmap?
    var data as List<of uint8[]> = List<of uint8[]>()
    var canvas as List<of uint8[]> = List<of uint8[]>()
    var moves as int[] = @[0,1]
    var direction as bool = true
    var position as int[] = int[](0)
    var tolerance as float = 0f
    var color as uint8[] = uint8[](4)
    var rotated as bool = false
    var progress as int = 0
    def main
        args = CobraCore.commandLineArgs
        if args.count <> 3, throw Exception()
        .tolerance = float.parse(args[1])
        if .tolerance < 0 or .tolerance > 1, throw Exception()
        .source = Bitmap(args[2])
        .data = .toData(.source to !)
        .canvas = List<of uint8[]>()
        average = float[](4)
        for i in .data
            .canvas.add(uint8[](4))
            for n in 4, average[n] += i[n]/.source.height
        for n in 4, .color[n] = (average[n]/.source.width).round to uint8
        if .source.width % 2
            if .source.height % 2
                .position = @[0, .source.height-1]
                .update
                while .position[1] > 0, .up
                .right
            else
                .position = @[.source.width-1, .source.height-1]
                .update
                while .position[1] > 0, .up
                while .position[0] > 0, .left
                .down
        else
            if .source.height % 2
                .position = @[0,0]
                .update
            else
                .position = @[.source.width-1,0]
                .update
                while .position[0] > 0, .left
                .down
        .right
        .down
        while true
            if (1-.source.height%2)<.position[1]<.source.height-1
                if .moves[1]%2==0
                    if .direction, .down
                    else, .up
                else
                    if .moves[0]==2, .right
                    else, .left
            else
                .right
                if .progress == .data.count, break
                .right
                .right
                if .direction
                    .direction = false
                    .up
                else
                    .direction = true
                    .down
        image = .toBitmap(.canvas, .source.width, .source.height)
        if .rotated, image.rotateFlip(RotateFlipType.Rotate270FlipNone)
        image.save(args[2].split('.')[0]+'_snake.png')

    def right
        .position[0] += 1
        .moves = @[.moves[1], 0]
        .update

    def left
        .position[0] -= 1
        .moves = @[.moves[1], 2]
        .update

    def down
        .position[1] += 1
        .moves = @[.moves[1], 1]
        .update

    def up
        .position[1] -= 1
        .moves = @[.moves[1], 3]
        .update

    def update
        .progress += 1
        index = .position[0]+.position[1]*(.source.width)
        .canvas[index] = .closest(.color,.data[index])
        .color = .canvas[index]

    def closest(color1 as uint8[], color2 as uint8[]) as uint8[]
        d = .difference(color1, color2)
        if d > .tolerance
            output = uint8[](4)
            for i in 4, output[i] = (color1[i] + .tolerance * (color2[i] - _
            color1[i]) / d)to uint8
            return output
        else, return color2

    def difference(color1 as uint8[], color2 as uint8[]) as float
        d = ((color2[0]-color1[0])*(color2[0]-color1[0])+(color2[1]- _
        color1[1])*(color2[1]-color1[1])+(color2[2]-color1[2])*(color2[2]- _
        color1[2])+0f).sqrt
        return d / (255 * 3f.sqrt)

    def toData(image as Bitmap) as List<of uint8[]>
        rectangle = Rectangle(0, 0, image.width, image.height)
        data = image.lockBits(rectangle, System.Drawing.Imaging.ImageLockMode.ReadOnly, _
        image.pixelFormat) to !
        ptr = data.scan0
        bytes = uint8[](data.stride*image.height)
        System.Runtime.InteropServices.Marshal.copy(ptr, bytes, 0, _
        data.stride*image.height)
        pfs = Image.getPixelFormatSize(data.pixelFormat)//8
        pixels = List<of uint8[]>()
        for y in image.height, for x in image.width
            position = (y * data.stride) + (x * pfs)
            red, green, blue, alpha = bytes[position+2], bytes[position+1], _
            bytes[position], if(pfs==4, bytes[position+3], 255u8)
            pixels.add(@[red, green, blue, alpha])
        image.unlockBits(data)
        return pixels

    def toBitmap(pixels as List<of uint8[]>, width as int, height as int) as Bitmap
        image = Bitmap(width, height, Imaging.PixelFormat.Format32bppArgb)
        rectangle = Rectangle(0, 0, image.width, image.height)
        data = image.lockBits(rectangle, System.Drawing.Imaging.ImageLockMode.ReadWrite, _
        image.pixelFormat) to !
        ptr = data.scan0
        bytes = uint8[](data.stride*image.height)
        pfs = System.Drawing.Image.getPixelFormatSize(image.pixelFormat)//8
        System.Runtime.InteropServices.Marshal.copy(ptr, bytes, 0, _
        data.stride*image.height)
        count = -1
        for y in image.height, for x in image.width
            pos = (y*data.stride)+(x*pfs)
            bytes[pos+2], bytes[pos+1], bytes[pos], bytes[pos+3] = pixels[count+=1]
        System.Runtime.InteropServices.Marshal.copy(bytes, 0, ptr, _
        data.stride*image.height)
        image.unlockBits(data)
        return image

```

Fills the image with a snake like:

```
#--#
   |
#--#
|
#--#
   |

```

This allows for much faster color adjustment than just lines in alternating directions, but doesn't become as blocky as a 3-wide version does.

Even at very low tolerances, the edges of an image are still visible (although at the loss of detail in smaller resolutions).

0.01

0.1

0.01

0.01

0.1

0.03

0.005

# Answer
> 1 votes
## C#

Snake starts at top left pixel with colour white and alternates left to right and then right to left down the image.

```
using System;
using System.Drawing;

namespace snake
{
    class Snake
    {
        static void MakeSnake(Image original, double tolerance)
        {
            Color snakeColor = Color.FromArgb(255, 255, 255);//start white
            Bitmap bmp = (Bitmap)original;
            int w = bmp.Width;
            int h = bmp.Height;
            Bitmap snake = new Bitmap(w, h);

            //even rows snake run left to right else run right to left
            for (int y = 0; y < h; y++)
            {
                if (y % 2 == 0)
                {
                    for (int x = 0; x < w; x++)//L to R
                    {
                        Color pix = bmp.GetPixel(x, y);
                        double diff = Snake.RGB_Distance(snakeColor, pix);
                        if (diff < tolerance)
                        {
                            snakeColor = pix;
                        }
                        //else keep current color
                        snake.SetPixel(x, y, snakeColor);
                    }
                }
                else
                {
                    for (int x = w - 1; x >= 0; x--)//R to L
                    {
                        Color pix = bmp.GetPixel(x, y);
                        double diff = Snake.RGB_Distance(snakeColor, pix);
                        if (diff < tolerance)
                        {
                            snakeColor = pix;
                        }
                        //else keep current color
                        snake.SetPixel(x, y, snakeColor);
                    }
                }
            }

            snake.Save("snake.png");
        }

        static double RGB_Distance(Color current, Color next)
        {
            int dr = current.R - next.R;
            int db = current.B - next.B;
            int dg = current.G - next.G;
            double d = Math.Pow(dr, 2) + Math.Pow(db, 2) + Math.Pow(dg, 2);
            d = Math.Sqrt(d) / (255 * Math.Sqrt(3));
            return d;
        }

        static void Main(string[] args)
        {
            try
            {
                string file = "input.png";
                Image img = Image.FromFile(file);
                double tolerance = 0.03F;
                Snake.MakeSnake(img, tolerance);
                Console.WriteLine("Complete");
            }
            catch(Exception e)
            {
                Console.WriteLine(e.Message);
            }

        }
    }
}

```

Result image tolerance = 0.1

---
Tags: popularity-contest, graphical-output, image-processing
---


title: 2nd byte bias of RC4

text:
# Question
Title: 2nd byte bias of RC4
## Short version

`RC4`, designed in 1987, is one of the most famous stream ciphers. This question asks you to practically demonstrate its 2nd byte bias (for a theoretical proof, see section 3.2 of this paper).

## Long version

OK, here I try to elaborate it for non-cryptographers. As you have noted, `RC4` is a very popular cipher in the cryptographic domain, mainly because of its simplicity. It consists of a *register* (i.e., array) of length 256, each element of this register can hold up to 8 bits.

Here's a quick overview of how stream ciphers commonly work: a secret `key` is taken, a **Key-scheduling algorithm (KSA)** is performed (which takes the `key` as input), followed by a **Pseudo-random generation algorithm (PRGA)** (which outputs a sufficiently long random-looking `key-stream`). To *encrypt* (resp. *decrypt*), one has to bit-wise XOR this `key-stream` with the `plaintext` (resp. `ciphertext`).

For `RC4`, the `key` is of length 1 to 256. The **KSA** and **PRGA** are performed on the 256 byte register `S` as follows:

**KSA**

```
for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

```

**PRGA**

```
i := 0, j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

```

These `K`'s constitute the `key-stream`. After getting first 256 bytes of the `key-stream`, you need to count the frequency of each number from 0 to 255 in the `key-stream`, occuring in each position for a given `key`.

The interesting thing is that, even if the `key`s are taken at random, you will notice the `key-stream` is far from random - "the frequency of the second byte is zero" is nearly double of what it actually should be (if it were truly random). This is known as distinguishing attack.

Your task is to:

1. Take *as much as you can* random `key` of 16 bytes
2. Generate the `key-stream` of first 2 bytes for each `key`
3. Count the number of times zero appears at the 2nd byte of each the `key-stream`s

You program should be capable of taking at least 2^19 - 2^20 `key`s, *and make the code run as fast as you can*.

Here's a quick try of me in Python:

```
def ksa(S):
    key = range(256)
    j = 0
    for i in range(256):
        j = (j + key [i] + S [i % len(S)]) % 256
        key [i], key [j] = key [j], key [i]
    return key

def prga (key):
    i = 0; j = 0
    while True:
        i = (i + 1) % 256
        j = (j + key [i]) % 256
        key [i], key [j] = key [j], key [i]
        yield key [(key [i] + key [j]) % 256]

def encrypt_or_decrypt (text, S):
    alt_text = []
    key = ksa (S)
    prga_generator = prga(key)
    for byte in text:
        alt_text.append (prga_generator. next())
    return tuple (alt_text)

if __name__ == '__main__':
    from time import time
    stime = time ()
    import sys
    rounds = int (sys.argv [1]); text_length = 256; key_length = 16
    text = [0 for x in range(text_length)]
    out = list ()

    import random, numpy as np
    for r in range (rounds):
        S = [random.randint(0, 255) for x in range (key_length)]
        out.append (encrypt_or_decrypt (text, S))

    print str (range (256)) [1:-1]

    for o in np.transpose (out):
        temp = list(np.bincount (o))
        while len (temp) < 256:
            temp.append (0)
        print str (temp)[1:-1]
    print time () - stime

```

Pipe the output to a CSV file and note the content of A3 cell, after opening it with an office package *(it should be nearly double of each of the other cells)*.

This one is of 524288 `key`s (it took 220.447999954s of my i5 processor, 4 GB RAM):

***BONUS:*** Create the whole 256 by 256 frequency matrix, where rows indicate the frequency of a number (in 0 to 255) and columns indicate the corresponding byte position (from 1 to 256).

# Winning conditions

---

* Fastest in terms of # iterations/ second in my computer
* Single-threaded execution only (multi-threaded versions are also welcome here, but not as a participant)
* For tie (or nearly tie) cases, popularity and capability of more iterations will be considered (though I suppose there will be no such situation)
* No need for *true* random numbers, *pseudo* random numbers will suffice, as it is not a cryptographic contest

**Update** In my computer, here are the results (2^24 iterations):

1. bitpwner The 256 * 256 matrix in 50.075s
2. Dennis The bias 19.22s

Since, there seems no more answer coming in, I declare Dennis as the winner. *bitpwner did really good with the big matrix.*

# Answer
## C

Takes about 111 secs to run on my Macbook Air for 2^24 = 16777216 trials.

To compile: `gcc -o rc4 rc4.c`

To pipe the output to a csv: `./rc4 > rc4out.csv`

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>

#define KEY_LENGTH 16
#define ITERATIONS 16777216

void ksa(unsigned char state[], unsigned char key[]) {
    int i,j=0,t;
    for (i=0; i<256; ++i)
        state[i] = i;
    for (i=0; i<256; ++i) {
        j = (j + state[i] + key[i % KEY_LENGTH]) % 256;
        t = state[i];
        state[i] = state[j];
        state[j] = t;
    }
}

void prga(unsigned char state[], unsigned char out[]) {
    int i=0,j=0,x,t;
    unsigned char key;
    for (x=0; x<256; ++x) {
        i = (i + 1) % 256;
        j = (j + state[i]) % 256;
        t = state[i];
        state[i] = state[j];
        state[j] = t;
        out[x] = state[(state[i] + state[j]) % 256];
    }
}

void makeRandomKey(unsigned char key[]) {
    int i;
    for (i=0; i<KEY_LENGTH; ++i)
        key[i] = rand() % 256;
}

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

    struct timeval time_started, time_now, time_diff;
    gettimeofday(&time_started, NULL);

    unsigned char state[256];
    unsigned char out[256];
    unsigned char key[KEY_LENGTH];
    int occurances[256][256];
    int i,j,bytePosition,charOccurance;

    for (i=0; i<256; ++i)
        for (j=0; j<256; ++j)
            occurances[i][j] = 0;

    srand(time(NULL));
    for (i=0; i<ITERATIONS; ++i) {
        makeRandomKey(key);
        ksa(state, key);
        prga(state, out);

        for (j=0; j<256; ++j)
            ++occurances[j][out[j]];
    }

    for (bytePosition=0; bytePosition<256; ++bytePosition) {
        printf("%d,", bytePosition);
    }
    printf("\n");
    for (charOccurance=0; charOccurance<256; ++charOccurance) {
        for (bytePosition=0; bytePosition<256; ++bytePosition) {
            printf("%d,", occurances[charOccurance][bytePosition]);
        }
        printf("\n");
    }

    gettimeofday(&time_now, NULL);
    timersub(&time_now, &time_started, &time_diff);
    printf("Time taken,%ld.%.6ld s\n", time_diff.tv_sec, time_diff.tv_usec);

    return 0;
}

```

Results for 16777216 trials.

Multithreaded version here. Compile with `gcc -o rc4 rc4.c -pthreads`.
> 2 votes

# Answer
# C (1,432,725 keys / second)

```
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define RAND_64() *Ks = rand(), Ks++, *Ks = rand(), Ks++, *Ks = rand(), Ks++, *Ks = rand()
#define KSA_1()   t = *s, j += t + *k, *s = S[j], S[j] = t, s++
#define KSA_4()   KSA_1(); k++; KSA_1(); k++; KSA_1(); k++; KSA_1()
#define KSA_16()  KSA_4(); k++; KSA_4(); k++; KSA_4(); k++; KSA_4(); k = K
#define KSA_64()  KSA_16(); KSA_16(); KSA_16(); KSA_16()

int main(int argc, char *argv[])
{
        int i, m = atoi(argv[1]), r = 0;
        uint8_t j, K[16], *k = K, S[256], *s, S0[256], t;
        uint16_t *Ks;
        for(i = 0; i < 256; i++) S0[i] = i;
        srand(time(NULL));

        for(i = 0; i < m; i++)
        {
                Ks = (uint16_t *) K, RAND_64(), Ks++, RAND_64();
                memcpy(S, S0, 256); s = S, j = 0;
                KSA_64(); KSA_64(); KSA_64(); KSA_64();
                j = S[1], S[1] = S[j], S[j] = j;
                t = S[2], j += t, S[2] = S[j], S[j] = t, t += S[2];
                r += (S[t] == 0);
        }
        printf("%u\n", r);
}

```

### Benchmarking

```
$ gcc -Ofast rc4bias-rand.c && time ./a.out $[2**24]
130924
Real    11.71
User    11.71
Sys     0.00
$ bc <<< '2^24 / 11.71'
1432725

```

Tested on an Intel i7-3770 running Fedora 20.
> 1 votes

---
Tags: fastest-code, cryptography
---


# Question
Title: Write a piece of code to output the line number of the print / output statement itself (in the form "Hello World, from line X!")
## The Challenge

Write a program that outputs `Hello World, from line X!`, where `X` is the line number, in the source code, of the actual print statement itself.

## The Rules

* In this context, we want **the *first* line number of the statement which outputs the string** to be displayed to `stdout`
* You should **avoid simply searching through your source code as a string** (either file or quine) to find the line number
* If any **additional whitespace or statements** (which do not interrupt the flow of the code) is added to the source code, it should be **reflected at run-time** (after compiling if applicable)

## Recommendations

If provided by the language, you **may** use exceptions/stack traces to accomplish this goal. Try your best to use code that is **portable** across different systems/implementations, but note that this is **not** a requirement. Using defined variables like `__LINE__`, although allowed by the rules, are discouraged.

## The Winner

* This is a **popularity contest** (ended on June 10, 2014), where the **answer voted highest by the community** will be declared the winner based on the current votes at the time
* When voting, please consider the creativity of someone's answer, how elaborate or **interesting** it is. and the difficulties/constraints of the programming language being used

# Answer
# Sinclair Basic

```
10 PRINT "Hello world, from line ";PEEK 23621;"!"

```

> Hello world, from line 10!

This will work for any line by `PEEK`ing at the address storing the current line number, so the following will work as well:

```
341 PRINT "Hello world, from line ";PEEK 23621;"!"

```

> Hello world, from line 341!
> 49 votes

# Answer
# BASIC

I think this does everything that was asked for:

```
10 PRINT "Hello World, from line 10!"

```
> 39 votes

# Answer
# Java

```
public class Hello{
    public static void main(String[] args) {
        System.out.println("Hello World, from line "+new Exception().getStackTrace()[0].getLineNumber()+"!");
    }
}

```
> 35 votes

# Answer
## Perl

```
close STDERR;
open FOOBAR,">",\$_;

print!warn,'Hello World, from line ',/(\d+)\.$/,'!';

```

Not quite as short as using `__LINE__`, but perhaps more interesting.

> `warn` is a debugging tool, which issues a statement to `STDERR`, indicating in which file, and on which line the warning was issued... *unless* `STDERR` has been previously closed or is otherwise inaccessible, in which case the warning is issued to the most recently opened file handle - this is undocumented behavior. I'm not sure if it would be better classified as a feature or a bug.
> Here, `STDERR` is closed, and a new file handle identified as `FOOBAR` is opened, and routed to the variable `$_`. This is then parsed to retrieve the line number of the warning, which is embedded in the print statement.
> 29 votes

# Answer
## C++

```
#include <iostream>
#include <utility>
#include <type_traits>

#define __(A,B,C,...) B##C##A
#define _(A,...) __(__VA_ARGS__, A)
template<unsigned...Is> struct v;
template<unsigned I0, unsigned... Is> struct v<I0, Is...>:v<I0-1,I0-1, Is...> {};
template<unsigned...Is> struct v<0,Is...>:std::integral_constant<unsigned, sizeof...(Is)> {};

int main() {
  std::cout << "Hello world from line " << v<_(EXTRACT,_(Q,_,E,_,$$main$$,),_(@22,,_,_),_(Z,N,L,I,_,,L),__STACK_TRACE__)>::value << "\n";
}

```

live example
> 27 votes

# Answer
# C

```
#include <stdio.h>
main(){
printf("Hello World, from line %d!", __LINE__);
}

```
> 16 votes

# Answer
# Lua

```
print("Hello world, from line "..debug.getinfo(1).currentline.."!")

```
> 16 votes

# Answer
## C#

C# 5.0's `[CallerLineNumber]` does the trick:

```
using System;
using System.Linq;
using System.Runtime.CompilerServices;
namespace LineNumberConsole
{
    class Program
    {
        public static void Main()
        {
            Console.WriteLine("Hello World, from line {0}!", ToRoman(GetLineNumber()));
            Console.ReadLine();
        }

        private static int GetLineNumber([CallerLineNumber] int sourceLineNumber = 0)
        {
            return sourceLineNumber;
        }

        private static string ToRoman(int number)
        {
            // TODO: Copy some source code from http://pastebin.com/w0hm9n5W
            // Skipped here for brevity
            return number.ToString();
        }
    }
}

```

## Output

```
Hello World, from line X!

```
> 16 votes

# Answer
## Python

Example (10 lines, 213 characters):

```
import sys
import traceback
lineno = None
while True:
    try:
        print 'Hello World, from line %d!' % lineno
        break
    except:
        lineno = traceback.tb_lineno(sys.exc_info()[2])
        continue

```

Try online here. Non-flow altering code and whitespace can be added and the program will display the updated line count, and likewise, this code snippet can also be used anywhere in an existing program. Expected output:

```
Hello World, from line 6!

```

---

Another example (try online here) to show that it works when code/whitespace is added. Expected output:

```
Down we go...
Gotta catch 'em all.
Down we go...
Hello World, from line 11!
Awesome!

```
> 15 votes

# Answer
**Javascript**

```
function getLine(n) {
   try {
      to
   } catch (dat) {
      var stack = dat.stack.split('\n');
       for (var i = 0; i < stack.length; i++) {
           if (~stack[i].indexOf ('getLine')) break;
       }
      return dat.stack.split ('\n')[i + ~~n].match (/:(\d+)/)[1] - ~~window.hasOwnProperty ('__commandLineAPI')
   }
}
//Line 12
console.log ('Hello World, from line ' + getLine(1) + ' !')

```

*Note: Expressions, evaluated from within the chrome dev console will be wrapped in a `with` statement. Thus we need to decrement the line by one if that's the case*
> 12 votes

# Answer
## Python 3

```
import hashlib
with open(__file__) as f:
    line_num = 0
    for line in f.readlines():
        line = line.rstrip() # make it work with or without newline at the end
        line_num += 1
        if hashlib.sha256(bytes(line, "UTF-8")).hexdigest()[0:6] == 'cc46f7':
            print('Hello world, from line {}!'.format(line_num)) # cc46f7

```

> Hello world, from line 8!

This self-reading code contains a self-referencing hash. The SHA256 sum of the last line (with the beginning whitespace and without trailing whitespace) begins with `cc46f7...`. When it hashes the `print` line, it finds that the hash matches the magic value it's searching for.
> 11 votes

# Answer
GNU COBOL

Well, they said it couldn't be done. Actually, it was I who said it couldn't be done. Now it's done, and an obsolete language feature re-implemented using the method applied.

The question states:

> If any additional whitespace or statements (which do not interrupt the flow of the code) is added to the source code, it should be reflected at run-time (after compiling if applicable).

Any amount of stuff can be inserted prior to the three `DISPLAY`s which cause the start of the output, and anything *after* the `DISPLAY`s would "interrupt the flow of the code", so that's OK.

COBOL used to have a `TRACE` verb (statement) which simply listed source line-numbers as they were executed (no access to the line number in the program). Although of limited use, I've included an implementation of TRACE.

```
   ID Division.
   Program-ID. HIWHERE.
   ENVIRONMENT DIVISION.
   configuration section.
          source-computer. TinkerToy with debugging mode.
   Procedure Division.
   Declaratives.
   Debug-Declaratives Section.
       Use For Debugging on a b
       .
   Debug-Declaratives-Paragraph.
       Display Debug-Line "!"
       .
   End Declaratives
       .
   Main-Program Section.
       DISPLAY "Perform"
       Display "Hello World, from line " no advancing Perform b
       display "GO TO"
       Display "Hello World, from line " no advancing GO TO a
       .
   a.
       dISPLay "Fall through"
       Display "Hello World, from line " no advancing. b.
   The-Last-bit-OF-the-PROGRAM.
       GOBACK
       .

```

The output is

```
Perform
Hello World, from line     18!
GO TO
Hello World, from line     20!
Fall through
Hello World, from line     23!

```

As an exhibition of the power and flexibility of writing the language, this example uses mixed-case, entirely lowercase, and entirely uppercase, all at the same time. It does not matter, as when processed, everything is "folded" to UPPERCASE.

The only standard COBOL way to get at a source line-number in the running program, from the running program, is with a `DEBUGGING` `DECLARATIVE`. Within a `SECTION`, strictly within a paragraph within a `SECTION`, of a such a declarative you have access to the special-register `DEBUG-LINE`. This contains the source line-number of the verb (statement) which caused transfer of control to a particular procedure-name (paragraph or `SECTION`).

So, with `PERFORM`, or `GO TO`, or "fall through" the paragraph in the debugging declaratives `SECTION` is executed.

OK, but `DISPLAY` does not cause transfer of control.

No problem. Put it on the *same line* as the transfer of control.

Problem, since if "any additional whitespace or statements (which do not interrupt the flow of the code) is added to the source code, it should be reflected at run-time (after compiling if applicable)".

So, put it on the same line *but in front of* a transfer of control, split the content of the `DISPLAY` into two pieces (remember, "In this context, we want the first line number of the statement which outputs the string to be displayed") and output the first part prior to the transfer of control, and the second part, from the `DEBUG-LINE`, once inside the debugging procedure.

The final tricky bit is for the "fall through" ("procedures" can be `PERFORM`ed, can be the target of a `GO TO`, or can be entered simply by being the next line along). In this instance, put the `DISPLAY` *on the line which defines the procedure, but in front of the definition*.

The names of the "procedures" (`a` and `b`) have been severely shortened to allow them to fit on the same source-line as the `DISPLAY`. Strictly a COBOL procedure-name should start somewhere from column eight to column 11. However, the syntax is, these days, much more relaxed about that. To the extent that I can define a procedure name on the same line as some code. Even embedded in code. Care, and an occasional full-stop, is required.

In the `PROCEDURE DIVISION` each full-stop shown is required, and no more are.

To compile:

```
cobc -x -g hiwhere.cbl

```

To execute (linux):

```
COB_SET_DEBUG=Y ./hiwhere

```

Finally, the return of TRACE (without READY/RESET).

```
   ID Division.
   Program-ID. tRacE.
   ENVIRONMENT DIVISION.
   configuration section.
          source-computer. TinkerToy with debugging mode.
   Procedure Division.
   Declaratives.
   Debug-Declaratives Section.
       Use For Debugging on a
       .
   Debug-Declaratives-Paragraph.
       Display Debug-Line
       .
   End Declaratives
       .
   Main-Program Section.
  *    Just append "perform a" to a single-line statement.
       DISPLAY "1" . perform a
       Display "2" . perform a
       display "3" . perform a
  *    Or prepend "perform a." for a multi-line statement, or a
  *    statement which won't "come back".
       perform a. GOBACK
       .
   a.
       CONTINUE
       .

```

Output is:

```
1
    17
2
    18
3
    19
    20

```

Where 1, 2 and 3 are output from the three DISPLAY statements, and 17, 18, 19 and 20 are the line numbers of the "executable" (non-debugging) lines.
> 9 votes

# Answer
# Java

Using the behavior of Exception's stack trace to get current line. as long as Printstatement isn't mangled into multiple lines or classfile gets mangled it should work

```
public class PrittLnbr
{
    public static void main(String[] args)
    {
        System.out.println("Hello World, from line "+new Error().getStackTrace()[0].toString().split(":")[1]+"!");
    }
}

```
> 8 votes

# Answer
**Python**

```
import traceback, inspect
frame = inspect.currentframe()
print("Hello World, from line "+traceback.format_stack(frame)[0].split()[3][:-1]+"!")

```
> 8 votes

# Answer
**Befunge**

Done just for fun.

```
>00g1+:00p"v"\10v
    v-*45g00p\g <
#v+1_$10g1vv,,,,<
^<p000p01+<#>,,,^
>" enil morf ,oll"v
@.,,,,,,,,,<^,"He"<

```

Conditional: top left of the code has to be 0 \< x \< 20 and 0 \<= y \< 62; and the two first cells have to be empty.

example:

```
                         v

                         0
                         0
                         0
                         p
                         0
                         1
                         0
                         p
                         >00g1+:00p"v"\10v
                             v-*45g00p\g <
                         #v+1_$10g1vv,,,,<
                         ^<p000p01+<#>,,,^
                         >" enil morf ,oll"v
                         @.,,,,,,,,,<^,"He"<

```

Would output:

Hello, from line 10
> 7 votes

# Answer
# Perl

```
print 'Hello World, from line '.__LINE__.'!';

```
> 6 votes

# Answer
**Java**

```
public class HelloFrom {
    public static void main(String[] args) {
        System.out.println("Hello World, from line " + Thread.currentThread().getStackTrace()[1].getLineNumber() + "!");
    }
}

```
> 6 votes

# Answer
**Python**

```
import inspect
print ("Hello world from line %d!" % (inspect.getlineno(inspect.currentframe())))

```

**Output**

```
Hello World from line 2!

```
> 6 votes

# Answer
# C

By using a variadic macro, we can make a print function which automatically adds the line number to the end of an arbitrary printf statement, and always prints to stdout.

test.c:

```
#include <stdio.h>

#define printfl(format, ...) fprintf(stdout, format " From line %d\n", ##__VA_ARGS__, __LINE__)

int main() {
    printfl("Hello World! I have %d argument(s).", 1);
    return 0;
}

```

outputs:

```
% ./test
Hello World! I have 1 argument(s). From line 6

```

Note: I deviated from the pattern to demonstrate that printfl is still a valid variadic function; if you *really* care about the format of the output, you can always change the literals I use.
> 6 votes

# Answer
# Bash

```
#
# some comments to fill some lines...
#
echo "Hello World, from line $LINENO!"

```

## Output

```
Hello World, from line 4!

```
> 5 votes

# Answer
## D

```
void main ()
{
    import std.stdio;
    writefln("Hello World, from line %d", __LINE__);
}

```
> 5 votes

# Answer
# C or C++, and AWK

lineno.c:

```
// code or comments
// ....
#error Hello World, from line
// other code or comments

```

Usage:

```
gcc lineno.c 2>&1 | awk '{ split($0,a,":"); ; printf("%s %s!\n", gensub(".*#error ","",1), a[2]); exit; }'

```

Output:

Hello, World, from line 3

Notes:

* No user written code searches the file.
* g++ will work on a c++ file.
> 5 votes

# Answer
Kind of boring in Ruby:

```
puts "Hello World, from line #{__LINE__}!"

```

This isn't cheating, right?
> 4 votes

# Answer
## Javascript

One line using stack trace.

```
(function (o) { console.log("Hello World, from line " + (Error.captureStackTrace(o) || o.stack.match(/\d+/)[0] - !!__commandLineAPI) + "!"); })({});

```
> 4 votes

# Answer
# Ruby

```
File.write "hello.rb", "x=2\n"+"x+=1\n"*rand(rand(100))+'puts "Hello World, from line #{x}!"'
system "ruby hello.rb"
File.delete "hello.rb"

```
> 3 votes

# Answer
# Cobra

```
class Program
    def main
        print 'Hello World, from line [System.Diagnostics.StackFrame(true).getFileLineNumber]!'

```
> 3 votes

# Answer
**Python**

```
import traceback

print 'Hello World, from line %i!' % traceback.extract_stack()[0][1]

```

Short and sweet.
> 3 votes

# Answer
# Powershell

```
$l=(Get-PSCallStack | ForEach{$_.Location})[0].split(' ')[-1]; "Hello World, from line $l!"

```

And:

```
try{ I AM ERROR. } catch { $l=$error[0].InvocationInfo.ScriptLineNumber; "Hello World, from line $l!" }

```

Both work like this:

```
PS C:\MyFolder> .\helloworld.ps1
Hello World, from line 1!

```
> 3 votes

# Answer
# PowerShell

## Cheap Move

```
Function LemmeGetDatError() {
    "Too busy chuggin along"
    "Then all of a sudden, I meet a new programmer"
    "And he's all like"
    Write-Output "$(Try {"Hello World from"; Throw "error" } Catch {$_.ScriptStackTrace.Split(":")[1]})"
}

LemmeGetDatError

```
> 3 votes

# Answer
# Perl

Another Perl one:

```
use warnings;

$SIG{__WARN__} = sub { ($line = shift) =~ s/\D//g; };

$x=$x+1; print "Hello World, form line $line!\n";

```
> 3 votes

# Answer
Inspired by @squeamish ossifrage's answer with BASIC.

What's in a line number?

In, for instance, IBM COBOL there are (can be) arguably three source line numbers.

The first (if used, it is optional), in columns 1-6 of the punched-card, are sequence numbers for the card deck. If the deck is dropped, the otherwise-hapless programmer has some chance to get things back in order. OK, starts to go slightly floppy as soon as the program has lines added, but that's what different coloured cards are (can be) for.

The second is on the compiler listing, generated by the compiler. The compiler diagnostic messages use this line number, else no-one would have much of a clue (unless the diagnostics are embedded, which they can be) which line any particular diagnostic referred to\*. These numbers for various reason (copybook code, let alone anything else) will be different from the first.

The third line number is of course the line number of the actual source file (optional, columns 73-80 if present). Other than actually reading the source file, or hard-coding a reference to a particular source line-number, it would not be possible to get this number in a program\***.

So:

```
999999     DISPLAY "Hello, world, from line 999999!"

```

This can appear anywhere in the PROCEDURE DIVISION of the program, since those line numbers have no affect on the program, and are only even flagged as out of sequence (not ascending, can be gaps) if requested by compiler option.

\** With compiler options SEQUENCE and NUMBER, the column 1-6 numbers will be used (modified by the compiler if necessary) for the diagnostic messages, and other data requiring source line numbers.

*** OK, possible in limited circumstances. No copybooks. Then you get the editor to put the sequence numbers of the source program (yes, we have actual sequence numbers, not just counting the lines) in columns one to six, and use compiler options SEQUENCE and NUMBER and then have a DEBUG DECLARATIVE, have the DISPLAY on the same physical line as the paragraph/SECTION which is going to cause the DEBUG DECLARATIVE to execute.
> 2 votes

# Answer
# Nimrod

```
template lineno(): expr = instantiationInfo().line
echo "Hello, world, from line ", lineno(), "!"

```

It uses Nimrod's templates to generate a call to instantiationInfo, whose information is only valid when used from within a template.

Output:

```
Hello, world, from line 2!

```
> 2 votes

# Answer
# C#

```
using System;
using System.Runtime.CompilerServices;
namespace LineNumber
{
    class Program
    {
        int getLn([CallerLineNumber] int x){ return x; }
        public static void Main()
        {
            Console.WriteLine ("Hello World, from line " + getLn() + "!");
        }
    }
}

```
> 2 votes

# Answer
# There is more than one way to do it (Perl 5)

The boring way:

```
print "Hello World, from line ", __LINE__, "!\n";

```

A fancier way:

```
sub println { print @_, ", from line ", (caller)[2], "!\n" }

println "Hello World";

```

A sneaky way:

```
eval {
    die "Hello World";
};

print $@ =~ s/ at .* (line \d+)\./, from $1!/r;

```

An even sneakier way:

```
$SIG{__DIE__} = sub { exit print $_[0] =~ s/ at .* (line \d+)\./, from $1!/r };

die "Hello World";

```

The really sneaky way:

```
package Magic {
    use Filter::Simple sub { s/42/\${\\__LINE__}/g };
}
BEGIN { import Magic }

print "Hello World, from line 42!\n";

```
> 2 votes

# Answer
## PHP

Shamelessly stolen from gnibbler

```
<?php
printf("Hello World, from line %d!", __LINE__);

```

Working example
> 1 votes

# Answer
# ECMAScript (JavaScript):

```
alert('Hello World, from line ' + Error().lineNumber + '!');

```

> Hello World, from line 1!

**Note:** I've only tested this in Firefox and Opera 10.

---

This should work in all current browsers:

```
alert('Hello World, from line ' + /^.*?@.+?:(\d+)(:\d+)?\r?\n/.exec(Error().stack)[1] + '!');

```

> Hello World, from line 1!
> 1 votes

# Answer
# x86 Assembly

```
.data
LC0:
    .ascii "hello, world! from address %x\n\0"
.text
    .global main
main:
    pushl   %ebp
    movl    %esp, %ebp
    call pop

pop:
    popl    %ebx
    leal    22(,%ebx,1), %ebx
    subl    $8, %esp
    movl    %ebx, 4(%esp)
    movl    $LC0, (%esp)
    call    printf
    movl    $0, %eax
    leave
    ret

```

This prints the memory address where the call to printf is located. This doesn't really work for rule 3, but I feel it's much more interesting than using \__LINE\__ or a stacktrace.

I should add how it works. Normally you can't get the address of the current instruction pointer by moving it into a register, so what I do is call a function "pop" which really means that the return address of the next instruction is pushed onto the stack and then a jump is executed. I pop this return address into ebx and add 22 to get the address of the printf call. The reason this won't work for rule 3 is that if you insert code before the printf call the address will not be 22 away from the address of the pop ebx.
> 1 votes

# Answer
## POSIX SHELL:

I was going to do `$LINENO` but it's been done. So I'll ask an interactive POSIX-compatible shell to printout its current history line number instead:

```
HISTFILE= PS1='${hi}$(printf "${hi:+\!!!\n}> ")' sh -i
> hi=${on='Hello World, from line '}${off=}
Hello World, from line 2!
> hi=$off
> hi=$on
Hello World, from line 4!
>

```

Though it may not look like it, the shell is actually reevaluating and printing anew that `$PS1` variable for every command it receives - else it wouldn't even work - so the print statement actually is printing its own line number every time it prints and not just the first.
> 1 votes

# Answer
# Befunge 98

This code snippet assumes that the IP comes downward into the upper left `n`. Otherwise, it fails.

```
n
>v>" enil morf ,dlroW olleH"bb+k,.@
^>:'^\1\p1+
 ][

```

The `n` (and newline) can be removed if I can assume that the stack is empty when it enters this snippet.

There is one discrepancy between this output and the one requested: instead of a `!` at the end of the printed statement, this outputs a space because Befunge automatically appends a space to numbers that are outputted. I could easily add a `!` after that. Fixing this would require a mess of ugly code.

You may add **extra** newlines anywhere and the code will still work. Spaces are more restricted, but may be added in several places. For instance, they cannot be added as the first character in any line.

Sample program:

```
v

n
>v>" enil morf ,dlroW olleH"bb+k,.@
^>:'^\1\p1+
 ][

```

Output:

```
Hello World, from line 12

```
> 1 votes

# Answer
## Haskell

```
{-# LANGUAGE CPP #-}
main = putStrLn $ "Hello World, from line " ++ show __LINE__ ++ "!"

```

> Hello World, from line 2!
> 0 votes

# Answer
# PHP

```
echo "Hello world, from line " . __LINE__ . "!";

```
> 0 votes

# Answer
## Batch Script

```
@echo off
set /a %line%==10
echo Hello world at %line%
pause
exit

```
> 0 votes

# Answer
**JAVASCRIPT - NON-Standard**

```
console.log('Hello World, from line %d!', (new Error).lineNumber);

```

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global\_Objects/Error/lineNumber
> 0 votes

# Answer
# Python 2.7

```
# Any number of whitespace, code, etc.

# In this case, when greet() is called, it will output "Hello world, from line 4!"
def greet():print "Hello world, from line " + str(greet.func_code.co_firstlineno) + "!"

```

Originally I wanted to implement an overkill compiled code parser, but gave up, this is still a good one tho.
> 0 votes

---
Tags: popularity-contest, hello-world, self-referential
---


# Question
Title: Stack a random number of cups into a perfect two dimensional pyramid (triangle)
You are given a certain number of cups (`n`). You are tasked with stacking these cups into a pyramid, with each row having one more cup than the row above it. The number you are given may or may not be able to be perfectly stacked. You must write a function that takes the total number of cups (`n`), and returns the following values. `t`, which is the total number of cups in the pyramid, and `b`, which is the number of cups on the bottom row. Your answer must be returned in the format of a string, as `b,t`.

* `n` is a randomly generated, positive, finite, whole number.
* `b` and `t` must also be positive, finite, and whole.
* You may not use any libraries that aren't already built into your language of choice.
* The pyramid is two dimensional, so instead of expanding out, it is linear, with each row adding only a single cup more than the last, instead of one with a square or triangular base.

In some potential cases:

* If `n=4`, `b=2` and `t=3`.
* If `n=13`, `b=4` and `t=10`.
* If `n=5000`, `b=99` and `t=4950`.

A verbose example in JavaScript:

```
var pyramid = function(n){
    var i;
    var t = 0;
    var b;
    for(i=0;i<=(n-t);i++){
        t += i;
        b = i;
    }
    console.log(b + ',' + t);
}

```

And a tiny example too:

`p=function(n){for(t=i=0;i<=(n-t);i++){t+=i;b=i}return b+','+t}`

Good luck!

# Answer
> 5 votes
# GNU dc, 25 bytes

dc does not really have functions, but the closest thing is a macro. This defines a macro which is stored in register `m`. This pops the input `n` from the top of the stack (idiomatic for dc), and prints `b,t` to stdout as per the spec:

```
# 25 byte macro definition
[8*1+v1-2/ddn44P1+*2/p]sm

# Some test cases
4 lmx
9 lmx
10 lmx
11 lmx
13 lmx
5000 lmx

```

### Output:

```
$ dc 2dpyr.dc
2,3
3,6
4,10
4,10
4,10
99,4950
$

```

### Explanation:

This uses the same inverse of the triangle function used in some of the other numbers. The triangle number `n` for base length `b` is given by:

```
n = b(b+1)/2

```

Rearranging into a quadratic in terms of `b`:

```
b² + b - 2n = 0

```

Plugging the coefficients {A=1, B=1, C=-2} into the quadratic formula gives:

```
b = (-(1) ± sqrt((1)²-4(1)(-2n))) / 2(1)

b = (-(1) ± sqrt(1+8n)) / 2

```

This translates to `dc` as follows:

```
[                         # Start a macro definition
 8*                       # Push 8 to the stack and multiply by n
                          #     (n is assumed to be next value on the stack)
   1+                     # Push 1 to the stack and add to 8n
     v                    # Take the square root
      1-                  # Push 1 to the stack and subtract from the square root
        2/                # Push 2 to the stack and divide to get the value of `b`
          dd              # Duplicate top of stack twice (value of `b`)
            n             # Pop top of stack and print value of with no newline
             44P          # Push ASCII value of ',' (comma) and print with no newline
                1+        # Push 1 to the stack and add 1 to `b`
                  *       # Multiply b by (b+1)
                   2/     # Push 2 the stack and divide to get the value of `t`
                     p    # Print value of `t` with a newline
                      ]   # End macro definition
                       sm # Store macro in `m` register

```

Note the quadratic formula introduces a ±, but the + root always gives us the answer we need.

Note also that `dc`'s default precision is 0 decimal places, and positive numbers are always rounded down to the nearest whole number, which is exactly the rounding we need.

# Answer
> 7 votes
# Haskell, 64 ~~68~~

This works out the base directly by inverting the triangular number formula, `t = (b^2+b)/2`, and calculating `b = (sqrt(8*t+1) - 1) / 2`.

```
f n=init.tail$show(b,div(b^2+b)2)where b=floor$(sqrt(8*n+1)-1)/2

```

And rather than constructing the string-based answer as `show b++","++show t`, it simply chops the brackets off the shown tuple.

Edit: calculating the new triangular number in place instead of declaring a new variable, `t`, saves 4 characters.

# Answer
> 4 votes
# ES6 41

This is based on the comperendinous' formula:

**Edit:** Thanks to edc65's suggestions:

```
p=n=>''+[b=~-Math.sqrt(8*n+1)>>1,b++*b/2]

```

# Answer
> 2 votes
# Java

It's pretty simple to find triangle numbers. Here are three ways in Java, all under 90 chars, including a loopless version:

### 67

```
String x(int n){int t=0,b=0;for(;b<=n-t;t+=b++);return(b-1)+","+t;}

```

### 78

```
String y(int n){int b=1,t=1;for(;t<=n*2;t=b*b+b++);return(--b-1)+","+(t/2-b);}

```

### 89

```
String z(int n){int b=(int)Math.sqrt(n*2),t=(b*b+b)/2;return(t>n?b-1:b)+","+(t>n?t-b:t);}

```

# Answer
> 2 votes
# Pyth, 29

```
DAbKJ0W>b+JK~K1~JK)R++`K","`J

```

If the output format `b, t` instead of `b,t` is OK, then it's 28 characters:

```
DAbKJ0W>b+JK~K1~JK)R:`,KJ1_1

```

If `(b, t)` is OK, it's 23 characters:

```
DAbKJ0W>b+JK~K1~JK)R,KJ

```

Explanation:

```
def A(b):
 K=J=0
 while gt(b,plus(J,K)):
  K+=1
  J+=K
 return plus(plus(repr(K),","),repr(J))

```

Test run - (input, output):

```
DAbKJ0W>b+JK~K1~JK)R++`K","`Jj"\n"m,dAdL11

(0, '0,0')
(1, '1,1')
(2, '1,1')
(3, '2,3')
(4, '2,3')
(5, '2,3')
(6, '3,6')
(7, '3,6')
(8, '3,6')
(9, '3,6')
(10, '4,10')

```

# Answer
> 2 votes
# Javascript ES6 - 39 41 43

Thought I'd try some recursion in hopes that it'd be smaller than the for loop.

```
f=(n,b=0,t=0)=>(n>b)?f(n-++b,b,t+b):b+','+t

```

Tried to shrink it by calculating the total rather than passing it but ended up the same length

```
f=(n,b=0)=>(n>b)?f(n-++b,b):b+','+(b+b*b)/2

```

**Edit**: Dropped another 2 with core1024's suggestion

```
f=(n,b=0,t=0)=>n>b?f(n-++b,b,t+b):b+','+t

```

**Edit**: In principal, I agree with edc65 about the 'right' answer and almost didn't try to a recursive loop assuming it would be have to be longer. So I hate to take his improvement, but I will :) Nice spy there!

```
f=(n,b=0)=>n>b?f(n-++b,b):b+','+b++*b/2

```

# Answer
> 1 votes
# JavaScript (ES6) – 47

```
p=n=>{for(t=i=0;i+t<n;)t+=i++;return i-1+','+t}

```

For now only works on Firefox. The following works on any recent browser at **55 bytes**:

```
p=function(n){for(t=i=0;i+t<n;)t+=i++;return i-1+','+t}

```

This is derived from the example provided by the OP.

# Answer
> 0 votes
**PYTHON: 76**

```
def r(x,b,t):
 x-=b+1
 return r(x,b+1,t+b) if x>=0 else str(b)+','+str(t+b)

```

# Answer
> 0 votes
## PHP 145

```
<?$n=$argv[1];for($b=ceil($n/2);$b>0;$b--){for($k=$b-1;$k>0;$k--){$v=array_sum(range($k,$b));if($v>$n)continue 2;if($v==$n){echo "$b,$k";exit;}}}

```

Expanded:

```
<?
$n=$argv[1];
for($b=ceil($n/2);$b>0;$b--){
    for($k=$b-1;$k>0;$k--){
        $v=array_sum(range($k,$b));
        if($v>$n)continue 2;
        if($v==$n){
            echo "$b,$k";
            exit;
        }
    }
}

```

---
Tags: code-golf, math
---