text:
Photomosaics or: How Many Programmers Does it Take to Replace a Light Bulb?
I've compiled a mosaic of 2025 headshots from the avatars of the top Stack Overflow users.
(Click the image to view it full-size.)

Your task is to write an algorithm that will create an accurate photomosaic of another image using the 48×48 pixel avatars from this 45×45 grid of them.
Test Images
Here are the test images. The first is, of course, a light bulb!
(They are not full-sized here. Click an image to view it at full-size. Half-sized versions are available for The Kiss, A Sunday Afternoon..., Steve Jobs, and the spheres.)

Thanks to Wikipedia for all but the raytraced spheres.
At full-size these images all have dimensions divisible by 48. The larger ones had to be JPEGs so they could be compressed enough to upload.
Scoring
This is a popularity contest. The submission with mosaics that most accurately depict the original images should be voted up. I will accept the highest voted answer in a week or two.
Rules

Your photomosaics must be entirely composed of unaltered 48×48 pixel avatars taken from the mosaic above, arranged in a grid.
You may reuse an avatar in a mosaic. (Indeed for the larger test images you'll have to.)
Show your output, but keep in mind that the test images are very large, and StackExchange only allows posting of images up to 2MB. So compress your images or host them somewhere else and put smaller versions here.
To be confirmed the winner you must provide PNG versions of your light bulb or spheres mosaics. This is so I can validate them (see below) to ensure you are not adding extra colors to the avatars to make the mosaics look better.

Validator
This Python script can be used to check whether a completed mosaic really uses unaltered avatars. Just set toValidate and allTiles. It is unlikely to work for JPEGs or other lossy formats since it compares things exactly, pixel-for-pixel.
from PIL import Image, ImageChops

toValidate = 'test.png' #test.png is the mosaic to validate
allTiles = 'avatars.png' #avatars.png is the grid of 2025 48x48 avatars

def equal(img1, img2):
    return ImageChops.difference(img1, img2).getbbox() is None

def getTiles(mosaic, (w, h)):
    tiles = {}
    for i in range(mosaic.size[0] / w):
        for j in range(mosaic.size[1] / h):
            x, y = i * w, j * h
            tiles[(i, j)] = mosaic.crop((x, y, x + w, y + h))
    return tiles

def validateMosaic(mosaic, allTiles, tileSize):
    w, h = tileSize
    if mosaic.size[0] % w != 0 or mosaic.size[1] % h != 0:
        print 'Tiles do not fit mosaic.'
    elif allTiles.size[0] % w != 0 or allTiles.size[1] % h != 0:
        print 'Tiles do not fit allTiles.'
    else:
        pool = getTiles(allTiles, tileSize)
        tiles = getTiles(mosaic, tileSize)
        matches = lambda tile: equal(tiles[pos], tile)
        success = True
        for pos in tiles:
            if not any(map(matches, pool.values())):
                print 'Tile in row %s, column %s was not found in allTiles.' % (pos[1] + 1, pos[0] + 1)
                success = False
        if success:
            print 'Mosaic is valid.'
            return
    print 'MOSAIC IS INVALID!'

validateMosaic(Image.open(toValidate).convert('RGB'), Image.open(allTiles).convert('RGB'), (48, 48))

Good luck everyone! I cant wait to see the results.
Note: I know photomosaic algorithms are easy to find online, but they aren't yet on this site. I'm really hoping we see something more interesting than the usual "average each tile and each grid space and match them up" algorithm.

Isn't this essentially a duplicate of the previous one? Compute the color of each one, downscale the target to 2025px and apply the existing algorithm?

possible duplicate of American Gothic in the palette of Mona Lisa: Rearrange the pixels

@JanDvorak It's similar but I think not enough to be a duplicate. The algorithm you mentioned is one way to get a result. There are much more sophisticated solutions though.

K then... reverting (still too similar for me to upvote). Let's see what the answer bring...

My cat is missing from the avatars :-(

@JanDvorak The fact that the current answer is repeating avatars is enough to make me think this question is different. The pixel rearranging challenge could not reuse pixels, if I read it correctly.

@trlkly didn't notice you could reuse avatars; is it specified explicitly somewhere I didn't notice, or just allowed because unspecified?

But, once you specify a metric, all you need to do is to implement it and then grep the state space. Not a very interesting challenge, I'd say, unless someone comes up with a global metric.

@JanDvorak Not really a global metric but my new version reduces reuse of the same tile within a pre-defined radius.

You may wish to change "to make a light bulb" to "to replace a light bulb".

@JanDvorak The questions are similar but as trlkly says, this allows multiple avatars. Also you can take the "shape" of the tiles into account since you're arranging pictures not single pixels. Besides, if creating a program that applies a metric to an image is the defining point of these problems then http://codegolf.stackexchange.com/questions/33172/american-gothic-in-the-palette-of-mona-lisa-rearrange-the-pixels was already a duplicate of http://codegolf.stackexchange.com/questions/21041/cubify-this-a-lesson-in-grayscale-er-color-er-whatever.

Did you choose only headshot avatars in that image?

@nneonneo Yep. I wanted recognizable shots of real people.

The answers will eventually show how different this question is from the suggested duplicates. Not only can the shape of the avatars can be used to give a better fit than just treating each avatar as an average colour (as Calvin's Hobbies points out), but also the avatar with the closest fit based on average colour may not give the best colour fit for the finished image. A more accurate approach would treat it as a collection of "subpixels" rather than a single averaged superpixel. This question has the potential to gather some interesting solutions with a variety of different approaches.

It is worth noting that Photomosaic® is a registered trademark of Runaway Technology. http://www.photomosaic.com/

Java, average distance
package photomosaic;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import javax.imageio.ImageIO;

public class MainClass {

    static final String FILE_IMAGE = "45148_sunday.jpg";
    static final String FILE_AVATARS = "25745_avatars.png";
    static final String FILE_RESULT = "mosaic.png";

    static final int BLOCKSIZE = 48;

    static final int SCALING = 4;

    static final int RADIUS = 3;

    public static void main(String[] args) throws IOException {
        BufferedImage imageAvatars = ImageIO.read(new File(FILE_AVATARS));
        int[] avatars = deBlock(imageAvatars, BLOCKSIZE);

        BufferedImage image = ImageIO.read(new File(FILE_IMAGE));
        int[] data = deBlock(image, BLOCKSIZE);

        // perform the mosaic search on a downscaled version
        int[] avatarsScaled = scaleDown(avatars, BLOCKSIZE, SCALING);
        int[] dataScaled = scaleDown(data, BLOCKSIZE, SCALING);
        int[] bests = mosaicize(dataScaled, avatarsScaled, (BLOCKSIZE / SCALING) * (BLOCKSIZE / SCALING), image.getWidth() / BLOCKSIZE);

        // rebuild the image from the mosaic tiles
        reBuild(bests, data, avatars, BLOCKSIZE);

        reBlock(image, data, BLOCKSIZE);
        ImageIO.write(image, "png", new File(FILE_RESULT));
    }

    // a simple downscale function using simple averaging
    private static int[] scaleDown(int[] data, int size, int scale) {
        int newsize = size / scale;
        int newpixels = newsize * newsize;
        int[] result = new int[data.length / scale / scale];
        for (int r = 0; r < result.length; r += newpixels) {
            for (int y = 0; y < newsize; y++) {
                for (int x = 0; x < newsize; x++) {
                    int avgR = 0;
                    int avgG = 0;
                    int avgB = 0;
                    for (int sy = 0; sy < scale; sy++) {
                        for (int sx = 0; sx < scale; sx++) {
                            int dt = data[r * scale * scale + (y * scale + sy) * size + (x * scale + sx)];
                            avgR += (dt & 0xFF0000) >> 16;
                            avgG += (dt & 0xFF00) >> 8;
                            avgB += (dt & 0xFF) >> 0;
                        }
                    }
                    avgR /= scale * scale;
                    avgG /= scale * scale;
                    avgB /= scale * scale;
                    result[r + y * newsize + x] = 0xFF000000 + (avgR << 16) + (avgG << 8) + (avgB << 0);
                }
            }
        }
        return result;
    }

    // the mosaicize algorithm: take the avatar with least pixel-wise distance
    private static int[] mosaicize(int[] data, int[] avatars, int pixels, int tilesPerLine) {
        int tiles = data.length / pixels;

        // use random order for tile search
        List<Integer> ts = new ArrayList<Integer>();
        for (int t = 0; t < tiles; t++) {
            ts.add(t);
        }
        Collections.shuffle(ts);

        // result array
        int[] bests = new int[tiles];
        Arrays.fill(bests, -1);

        // make list of offsets to be ignored
        List<Integer> ignores = new ArrayList<Integer>();
        for (int sy = -RADIUS; sy <= RADIUS; sy++) {
            for (int sx = -RADIUS; sx <= RADIUS; sx++) {
                if (sx * sx + sy * sy <= RADIUS * RADIUS) {
                    ignores.add(sy * tilesPerLine + sx);
                }
            }
        }

        for (int t : ts) {
            int b = t * pixels;
            int bestsum = Integer.MAX_VALUE;
            for (int at = 0; at < avatars.length / pixels; at++) {
                int a = at * pixels;
                int sum = 0;
                for (int i = 0; i < pixels; i++) {
                    int r1 = (avatars[a + i] & 0xFF0000) >> 16;
                    int g1 = (avatars[a + i] & 0xFF00) >> 8;
                    int b1 = (avatars[a + i] & 0xFF) >> 0;

                    int r2 = (data[b + i] & 0xFF0000) >> 16;
                    int g2 = (data[b + i] & 0xFF00) >> 8;
                    int b2 = (data[b + i] & 0xFF) >> 0;

                    int dr = (r1 - r2) * 30;
                    int dg = (g1 - g2) * 59;
                    int db = (b1 - b2) * 11;

                    sum += Math.sqrt(dr * dr + dg * dg + db * db);
                }
                if (sum < bestsum) {
                    boolean ignore = false;
                    for (int io : ignores) {
                        if (t + io >= 0 && t + io < bests.length && bests[t + io] == at) {
                            ignore = true;
                            break;
                        }
                    }
                    if (!ignore) {
                        bestsum = sum;
                        bests[t] = at;
                    }
                }
            }
        }
        return bests;
    }

    // build image from avatar tiles
    private static void reBuild(int[] bests, int[] data, int[] avatars, int size) {
        for (int r = 0; r < bests.length; r++) {
            System.arraycopy(avatars, bests[r] * size * size, data, r * size * size, size * size);
        }
    }

    // splits the image into blocks and concatenates all the blocks
    private static int[] deBlock(BufferedImage image, int size) {
        int[] result = new int[image.getWidth() * image.getHeight()];
        int r = 0;
        for (int fy = 0; fy < image.getHeight(); fy += size) {
            for (int fx = 0; fx < image.getWidth(); fx += size) {
                for (int l = 0; l < size; l++) {
                    image.getRGB(fx, fy + l, size, 1, result, r * size * size + l * size, size);
                }
                r++;
            }
        }
        return result;
    }

    // unsplits the block version into the original image format
    private static void reBlock(BufferedImage image, int[] data, int size) {
        int r = 0;
        for (int fy = 0; fy < image.getHeight(); fy += size) {
            for (int fx = 0; fx < image.getWidth(); fx += size) {
                for (int l = 0; l < size; l++) {
                    image.setRGB(fx, fy + l, size, 1, data, r * size * size + l * size, size);
                }
                r++;
            }
        }
    }
}

The algorithm performs a search through all avatar tiles for each grid space separately.
Due to the small sizes I didn't implement any sophisticated data structurs or search algorithms but simply brute-force the whole space.
This code does not do any modifications to the tiles (e.g. no adaption to destination colors).
Results
Click for full-size image.

Effect of radius
Using radius you can reduce the repetitiveness of the tiles in the result. Setting radius=0 there is no effect. E.g. radius=3 supresses the same tile within a radius of 3 tiles.

radius=0

radius=3
Effect of scaling factor
Using the scaling factor we can determine how the matching tile is searched. scaling=1 means searching for a pixel-perfect match while scaling=48 does a average-tile search.

scaling=48

scaling=16

scaling=4

scaling=1

Wow. The radius factor really improves the results. Those same-avatar blotches were not good.

Not sure if it's me, but Pictureshack seems to have atrocious bandwidth compared to Imgur

@NickT Probably, but Imgur compresses everything to at most 1MB (http://imgur.com/faq#size). :(

Hmm, is it only me or the Mathematica answer by David is far better than this top-voted answer?

Too bad all those photos are gone. Can you reupload to imgur by any chance?

Mathematica, with control for granularity
This uses the 48 x 48 pixel photos, as required.  By default, it will swap those pixels for a corresponding 48x48 pixel square from the image to be approximated.
However, the size of the destination squares  can be set to be smaller than 48 x 48, allowing for greater fidelity to detail.  (see the examples below).
Preprocessing the palette
collage is the image containing the photos to serve as the palette.
picsColorsis a list of individual photos paired with their mean red, mean green, and mean blue values.
 targetColorToPhoto[]` takes the average color of the target swath and finds the photo from the palette that best matches it.
parts=Flatten[ImagePartition[collage,48],1];
picsColors={#,c=Mean[Flatten[ImageData[#],1]]}&/@parts;
nf=Nearest[picsColors[[All,2]]];

targetColorToPhoto[p_]:=Cases[picsColors,{pic_,nf[p,1][[1]]}:>pic][[1]]

Example
Let's find the photo that best matches RGBColor[0.640, 0.134, 0.249]:

photoMosaic
photoMosaic[rawPic_, targetSwathSize_: 48] :=
 Module[{targetPic, data, dims, tiles, tileReplacements, gallery},
  targetPic = Image[data = ImageData[rawPic] /. {r_, g_, b_, _} :> {r, g, b}];
  dims = Dimensions[data];
  tiles = ImagePartition[targetPic, targetSwathSize];
  tileReplacements = targetColorToPhoto /@ (Mean[Flatten[ImageData[#], 1]] & /@Flatten[tiles, 1]);
  gallery = ArrayReshape[tileReplacements, {dims[[1]]/targetSwathSize,dims[[2]]/targetSwathSize}];
  ImageAssemble[gallery]]

`photoMosaic takes as input the raw picture we will make a photo mosaic of.
targetPic will remove a fourth parameter (of PNGs and some JPGs), leaving only R, G, B.
dims are the dimensions of targetPic.
tiles are the little squares that together comprise the target picture.
targetSwathSize is the granularity parameter; it defaults at 48 (x48).
tileReplacements are the photos that match each tile, in proper order.
gallery is the set of tile-replacements (photos) with the proper dimensionality (i.e. the number of rows and columns that match the tiles).
ImageAssembly joins up the mosaic into a continuous output image.

Examples
This replaces each 12x12 square from the image, Sunday, with a corresponding 48 x 48 pixel photograph that best matches it for average color.
photoMosaic[sunday, 12]

Sunday (detail)

photoMosaic[lightbulb, 6]

photoMosaic[stevejobs, 24]

Detail, stevejobs.

photoMosaic[kiss, 24]

Detail of the Kiss:

photoMosaic[spheres, 24]

I like the idea of granularity. It gives more realism to the smaller images.

JS
Same as in previous golf: http://jsfiddle.net/eithe/J7jEk/ :D
(this time called with unique: false, {pixel_2: {width: 48, height: 48}, pixel_1: {width: 48, height: 48}}) (don't treat palette to use one pixel once, palette pixels are 48x48 swatches, shape pixels are 48x48 swatches).
Currently it searches through the avatars list to find the nearest matching by weight of selected algorithm, however it doesn't perform any color uniformity matching (something I need to take a look at.

Unfortunately I'm not able to play around with larger images, because my RAM runs out :D If possible I'd appreciate smaller output images. If using 1/2 of image size provided, here's Sunday Afternoon:

I've just added half-size images that are still divisible by 48 pixels.

GLSL
The difference between this challenge and the one at American Gothic in the palette of Mona Lisa: Rearrange the pixels interested me, because the mosaic tiles can be re-used, whereas the pixels couldn't. This means that it is possible to easily parallelize the algorithm, so I decided to attempt a massively parallel version. By "massively" I mean using the 1344 shader cores on my desktop's GTX670 all simultaneously, via GLSL.
Method
The actual tile-matching is simple: I calculate the RGB distance between each pixel in a target area and the mosaic tile area, and choose the tile with the lowest difference (weighted by brightness values). The tile index is written out in the red and green color attributes of the fragment, then after all the fragments have been rendered I read the values back out of the framebuffer and build the output image from those indices. The actual implementation is quite a hack; instead of creating an FBO I just opened a window and rendered into it, but GLFW can't open windows at arbitrarily small resolutions, so I create the window bigger than required, then draw a small rectangle that is the correct size so that it has one fragment per tile that maps to the source image. The entire MSVC2013 solution is available at https://bitbucket.org/Gibgezr/mosaicmaker
It requires GLFW/FreeImage/GLEW/GLM to compile, and OpenGL 3.3 or better drivers/video card to run.
Fragment Shader Source
#version 330 core

uniform sampler2D sourceTexture;
uniform sampler2D mosaicTexture;

in vec2 v_texcoord;

out vec4 out_Color;

void main(void)
{
    ivec2 sourceSize = textureSize(sourceTexture, 0);
    ivec2 mosaicSize = textureSize(mosaicTexture, 0);

    float num_pixels = mosaicSize.x/45.f;
    vec4 myTexel;
    float difference = 0.f;

    //initialize smallest difference to a large value
    float smallest_difference = 255.0f*255.0f*255.0f;
    int closest_x = 0, closest_y = 0;

    vec2 pixel_size_src = vec2( 1.0f/sourceSize.x, 1.0f/sourceSize.y);
    vec2 pixel_size_mosaic = vec2( 1.0f/mosaicSize.x , 1.0f/mosaicSize.y);

    vec2 incoming_texcoord;
    //adjust incoming uv to bottom corner of the tile space
    incoming_texcoord.x =  v_texcoord.x - 1.0f/(sourceSize.x / num_pixels * 2.0f);
    incoming_texcoord.y =  v_texcoord.y - 1.0f/(sourceSize.y / num_pixels * 2.0f);

    vec2 texcoord_mosaic;
    vec2 pixelcoord_src, pixelcoord_mosaic;
    vec4 pixel_src, pixel_mosaic;

    //loop over all of the mosaic tiles
    for(int i = 0; i < 45; ++i)
    {
        for(int j = 0; j < 45; ++j)
        {
            difference = 0.f;
            texcoord_mosaic = vec2(j * pixel_size_mosaic.x * num_pixels, i * pixel_size_mosaic.y * num_pixels);

            //loop over all of the pixels in the images, adding to the difference
            for(int y = 0; y < num_pixels; ++y)
            {
                for(int x = 0; x < num_pixels; ++x)
                {
                    pixelcoord_src = vec2(incoming_texcoord.x + x * pixel_size_src.x, incoming_texcoord.y + y * pixel_size_src.y);
                    pixelcoord_mosaic = vec2(texcoord_mosaic.x + x * pixel_size_mosaic.x, texcoord_mosaic.y + y * pixel_size_mosaic.y);
                    pixel_src = texture(sourceTexture, pixelcoord_src);
                    pixel_mosaic = texture(mosaicTexture, pixelcoord_mosaic);

                    pixel_src *= 255.0f;
                    pixel_mosaic *= 255.0f;

                    difference += (pixel_src.x - pixel_mosaic.x) * (pixel_src.x - pixel_mosaic.x) * 0.5f+
                        (pixel_src.y - pixel_mosaic.y) * (pixel_src.y - pixel_mosaic.y) +
                        (pixel_src.z - pixel_mosaic.z) * (pixel_src.z - pixel_mosaic.z) * 0.17f;
                }

            }

            if(difference < smallest_difference)
            {
                smallest_difference = difference;
                closest_x = j;
                closest_y = i;
            }
        }
    }

    myTexel.x = float(closest_x)/255.f;
    myTexel.y = float(closest_y)/255.f;
    myTexel.z = 0.f;
    myTexel.w = 0.f;

    out_Color = myTexel;
}

Results
The images render almost instantly, so the parallelization was a success. The downside is that I can't make the individual fragments rely on the output of any other fragments, so there is no way to get the significant quality increase you can get by not picking the same tile twice within a certain range. So, fast results, but limited quality due to massive repetitions of tiles. All in all, it was fun.
https://i.stack.imgur.com/MO7NU.jpg for full-size versions.

Python
Here goes for the first Python solution, using a mean approach. We can evolve from here. The rest of the images are here.

from PIL import Image
import numpy as np

def calcmean(b):
    meansum = 0
    for k in range(len(b)):
        meansum = meansum + (k+1)*b[k]
    return meansum/sum(b)

def gettiles(imageh,w,h):
    k = 0
    tiles = {}
    for x in range(0,imageh.size[0],w):
        for y in range(0,imageh.size[1],h):
            a=imageh.crop((x, y, x + w, y + h))
            b=a.resize([1,1], Image.ANTIALIAS)
            tiles[k] = [a,x,y,calcmean(b.histogram()[0:256]) \
                             ,calcmean(b.histogram()[256:256*2]) \
                             ,calcmean(b.histogram()[256*2:256*3])]
            k = k + 1
    return tiles

w = 48
h = 48

srch = Image.open('25745_avatars.png').convert('RGB')
files = ['21104_spheres.png', '45148_sunday.jpg', '47824_steve.jpg', '61555_kiss.jpg', '77388_lightbulb.png']
for f in range(len(files)):
    desh = Image.open(files[f]).convert('RGB')

    srctiles = gettiles(srch,w,h)
    destiles = gettiles(desh,w,h)

    #build proximity matrix
    pm = np.zeros((len(destiles),len(srctiles)))
    for d in range(len(destiles)):
        for s in range(len(srctiles)):
            pm[d,s] = (srctiles[s][3]-destiles[d][3])**2 + \
                      (srctiles[s][4]-destiles[d][4])**2 + \
                      (srctiles[s][5]-destiles[d][5])**2

    for k in range(len(destiles)):
        j = list(pm[k,:]).index(min(pm[k,:]))
        desh.paste(srctiles[j][0], (destiles[k][1], destiles[k][2]))

    desh.save(files[f].replace('.','_m'+'.'))

Yet Another Python Solution - Average Based (RGB vs Lab*)
Results (There are some slightly differences)
Bulb - RGB
full view

Bulb - Lab
full view

Steve - RGB
full view

Steve - Lab
full view

Spheres - RGB
full view

Spheres - Lab
full view

Sunday - RGB
full view

Sunday - Lab
full view

Kiss - RGB
full view

Kiss - Lab
full view

Code
requires python-colormath for Lab
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from PIL import Image
from colormath.color_objects import LabColor,sRGBColor
from colormath.color_conversions import convert_color
from colormath.color_diff import delta_e_cie1976

def build_photomosaic_ils(mosaic_im,target_im,block_width,block_height,colordiff,new_filename):

    mosaic_width=mosaic_im.size[0]              #dimensions of the target image
    mosaic_height=mosaic_im.size[1]

    target_width=target_im.size[0]              #dimensions of the target image
    target_height=target_im.size[1]

    target_grid_width,target_grid_height=get_grid_dimensions(target_width,target_height,block_width,block_height)       #dimensions of the target grid
    mosaic_grid_width,mosaic_grid_height=get_grid_dimensions(mosaic_width,mosaic_height,block_width,block_height)       #dimensions of the mosaic grid

    target_nboxes=target_grid_width*target_grid_height
    mosaic_nboxes=mosaic_grid_width*mosaic_grid_height

    print "Computing the average color of each photo in the mosaic..."
    mosaic_color_averages=compute_block_avg(mosaic_im,block_width,block_height)
    print "Computing the average color of each block in the target photo ..."
    target_color_averages=compute_block_avg(target_im,block_width,block_height)

    print "Computing photomosaic ..."
    photomosaic=[0]*target_nboxes
    for n in xrange(target_nboxes):
        print "%.2f " % (n/float(target_nboxes)*100)+"%"
        for z in xrange(mosaic_nboxes):
            current_diff=colordiff(target_color_averages[n],mosaic_color_averages[photomosaic[n]])
            candidate_diff=colordiff(target_color_averages[n],mosaic_color_averages[z])

            if(candidate_diff<current_diff):
                photomosaic[n]=z

    print "Building final image ..."
    build_final_solution(photomosaic,mosaic_im,target_nboxes,target_im,target_grid_width,block_height,block_width,new_filename)

def build_initial_solution(target_nboxes,mosaic_nboxes):
    candidate=[0]*target_nboxes

    for n in xrange(target_nboxes):
        candidate[n]=random.randint(0,mosaic_nboxes-1)

    return candidate

def build_final_solution(best,mosaic_im,target_nboxes,target_im,target_grid_width,block_height,block_width,new_filename):

    for n in xrange(target_nboxes):

        i=(n%target_grid_width)*block_width             #i,j -> upper left point of the target image
        j=(n/target_grid_width)*block_height

        box = (i,j,i+block_width,j+block_height)

        #get the best photo from the mosaic
        best_photo_im=get_block(mosaic_im,best[n],block_width,block_height)

        #paste the best photo found back into the image
        target_im.paste(best_photo_im,box)

    target_im.save(new_filename);

#get dimensions of the image grid
def get_grid_dimensions(im_width,im_height,block_width,block_height):
    grid_width=im_width/block_width     #dimensions of the target image grid
    grid_height=im_height/block_height
    return grid_width,grid_height

#compute the fitness of given candidate solution
def fitness(candidate,mosaic_color_averages,mosaic_nboxes,target_color_averages,target_nboxes):
    error=0.0
    for i in xrange(target_nboxes):
        error+=colordiff_rgb(mosaic_color_averages[candidate[i]],target_color_averages[i])
    return error

#get a list of color averages, i.e, the average color of each block in the given image
def compute_block_avg(im,block_height,block_width):

    width=im.size[0]
    height=im.size[1]

    grid_width_dim=width/block_width                    #dimension of the grid
    grid_height_dim=height/block_height

    nblocks=grid_width_dim*grid_height_dim              #number of blocks

    avg_colors=[]
    for i in xrange(nblocks):
        avg_colors+=[avg_color(get_block(im,i,block_width,block_height))]
    return avg_colors

#returns the average RGB color of a given image
def avg_color(im):
    avg_r=avg_g=avg_b=0.0
    pixels=im.getdata()
    size=len(pixels)
    for p in pixels:
        avg_r+=p[0]/float(size)
        avg_g+=p[1]/float(size)
        avg_b+=p[2]/float(size)

    return (avg_r,avg_g,avg_b)

#get the nth block of the image
def get_block(im,n,block_width,block_height):

    width=im.size[0]

    grid_width_dim=width/block_width                        #dimension of the grid

    i=(n%grid_width_dim)*block_width                        #i,j -> upper left point of the target block
    j=(n/grid_width_dim)*block_height

    box = (i,j,i+block_width,j+block_height)
    block_im = im.crop(box)
    return block_im

#calculate color difference of two pixels in the RGB space
#less is better
def colordiff_rgb(pixel1,pixel2):

    delta_red=pixel1[0]-pixel2[0]
    delta_green=pixel1[1]-pixel2[1]
    delta_blue=pixel1[2]-pixel2[2]

    fit=delta_red**2+delta_green**2+delta_blue**2
    return fit

#http://python-colormath.readthedocs.org/en/latest/index.html
#calculate color difference of two pixels in the L*ab space
#less is better
def colordiff_lab(pixel1,pixel2):

    #convert rgb values to L*ab values
    rgb_pixel_1=sRGBColor(pixel1[0],pixel1[1],pixel1[2],True)
    lab_1= convert_color(rgb_pixel_1, LabColor)

    rgb_pixel_2=sRGBColor(pixel2[0],pixel2[1],pixel2[2],True)
    lab_2= convert_color(rgb_pixel_2, LabColor)

    #calculate delta e
    delta_e = delta_e_cie1976(lab_1, lab_2)
    return delta_e

if __name__ == '__main__':
    mosaic="images/25745_avatars.png"
    targets=["images/lightbulb.png","images/steve.jpg","images/sunday.jpg","images/spheres.png","images/kiss.jpg"]
    target=targets[0]
    mosaic_im=Image.open(mosaic)
    target_im=Image.open(target)
    new_filename=target.split(".")[0]+"_photomosaic.png"
    colordiff=colordiff_rgb

    build_photomosaic_ils(mosaic_im,target_im,48,48,colordiff,new_filename)

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

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


text:
List the combinations of elements in a set
Given a set of n elements, the challenge is to write a function who lists all the combinations of k elements of in this set.
Example
Set: [1, 7, 4]
Input: 2
Output: [1,7], [1,4], [7,4]

Example
Set: ["Charlie", "Alice", "Daniel", "Bob"]
Input: 2
Output ["Daniel", "Bob"], ["Charlie", "Alice"], ["Alice", "Daniel"], ["Charlie", "Daniel"], ["Alice", "Bob"], ["Charlie",  "Bob"]

Rules (Edited)

The order of the output is of your choice.
The input may be any type of data. But the output should be the same type as the input. If the input is a list of integers, the output should be a list of integers as well. If the input is a string (array of characters), the output should be a string as well.
The code should work with any number of input variables.
You can use any programming language.
The answer should be able to use anything (string, int, double...) as input and output as well.
Any built-in functions that is related to combinations and permutations are forbidden.
Shortest code wins (in terms of bytes).
Tiebreaker: votes.
Duration: 1 week.

P.S. Be careful about the extreme inputs such as negative numbers, 0, etc.

How should input and output be done? (STDIN, function args, etc)

Although http://codegolf.stackexchange.com/questions/6380/generating-combinations-without-recursion does have an additional restriction, its answers could be copied unchanged and would still be hard to beat.

To avoid some of the loopholes used in this question, prohibit some builtin functions (combinations(), permutations(), etc.).

@PeterTaylor I've edited some rules. Thanks to Ypypn and golfer9338, now, this is a completely different question, I suppose.

By The input may be any type of data. do you mean any type of iterable data or an iterable filled with any type of data? e.g. is combos('ab', 1) -> ['a', 'b'] valid?

What should the output be if the input is negative?

I don't see how this question is a duplicate of "Generating combinations without recursion" when almost every answer so far uses recursion.

The removal of a restriction is not a significant change. Also, using existing answers to determine what is or is not a duplicate is not a good idea, because you would be unable to identify duplicates until they were already answered. Sometimes you just have to use your head.

I like recursion for question as this so for me it is ok reopen ...

Would powerset builtins count as combination builtins? The answer feels like "yes", but I'm not sure...

Haskell - 57 46 bytes
Bring it on, golfscripters.
0%_=[[]]
n%(x:y)=map(x:)((n-1)%y)++n%y
_%_=[]

Use case (same function works polymorphicaly):

2%[1,2,3,4] ➔ [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
3%"cheat" ➔ ["che","cha","cht","cea","cet","cat","hea","het","hat","eat"]
2%["Charlie", "Alice", "Daniel", "Bob"] ➔
[["Charlie","Alice"],["Charlie","Daniel"],["Charlie","Bob"],["Alice","Daniel"],["Alice","Bob"],["Daniel","Bob"]]

Thanks Mark, I didn't even consider making it infix.

Incidentally, what does "bring it on" mean in your dialect? In mine it implies a challenge, but that doesn't make sense in context because your final version is still longer than my initial version in the question this duplicates.

Python (72)
f=lambda S,k:S and[T+S[:1]for T in f(S[1:],k-1)]+f(S[1:],k)or[[]]*(k==0)

The function f takes a list S and number k and returns a list of all sublists of length k of S. Rather than listing all subsets and then filtering by size, I only get the subsets of the needed size at each step.
I'd like to get S.pop() to work in order to combine getting S[:1] with passing S[1:] later, but it seems to consume the list too much.
To preempt the objection any such Python solution breaks the rule that "The code should work in any number of input variables" because of recursion limits, I'll note that the Stackless Python implementation has no recursion limits (though I haven't actually tested this code with it).
Demonstration:
S = [1, 2, 6, 8]
for i in range(-1,6):print(i, f(S,i))

#Output:
-1 []
0 [[]]
1 [[1], [2], [6], [8]]
2 [[2, 1], [6, 1], [8, 1], [6, 2], [8, 2], [8, 6]]
3 [[6, 2, 1], [8, 2, 1], [8, 6, 1], [8, 6, 2]]
4 [[8, 6, 2, 1]]
5 []

Mathematica 10, 70 chars
Just a translation of the Haskell answer.
_~f~_={};_~f~0={{}};{x_,y___}~f~n_:=Join[Append@x/@f[{y},n-1],{y}~f~n]

Usage:

In[1]:= f[{1, 7, 4}, 2]
Out[1]= {{7, 1}, {4, 1}, {4, 7}}

Charcoal, 23 bytes
ＥΦＥＸ²Ｌθ⮌↨ι²⁼ΣιηΦ…θＬι§ιμ

Try it online! Link is to verbose version of code. Explanation:
    ²                   Literal 2
   Ｘ                    Raised to power
     Ｌ                  Length of
      θ                 Input array
  Ｅ                     Mapped over implicit range
         ι              Current index
        ↨               Converted to base
          ²             Literal 2
       ⮌                Reversed
 Φ                      Filtered on
            Σ           Digital sum of
             ι          Current base 2 value
           ⁼            Equal to
              η         Input `k`
Ｅ                       Mapped to
                 θ      Input array
                …       Chopped to length
                  Ｌ     Length of
                   ι    Current base 2 value
               Φ        Filtered on
                     ι  Current base 2 value
                    §   Indexed by
                      μ Current index

Haskell + Data.List, 44 bytes
0%_=[[]]
n%y=do{a:b<-tails y;(a:)<$>(n-1)%b}

Try it online!

The 46 byte answer is pretty hard to beat but if you have tails from Data.List you can do 44 bytes.

Python - 129
s is a list, k is the size of the combinations to produce.
def c(s, k):
    if k < 0: return []
    if len(s) == k: return [s]
    return list(map(lambda x: [s[0]]+x, c(s[1:], k-1))) + c(s[1:], k)

Python, 102
p=lambda s:p(s[1:])+[x+[s[0]]for x in p(s[1:])]if s else[s];c=lambda s,k:[x for x in p(s)if len(x)==k]

Call c to run:

c([5, 6, 7], 2) => [[6, 7], [5, 7], [5, 6]]

It gets all the permutations of the list s and filters the ones with length k.

Pyth, 28
DcGHR?+m+]'HdctGtHcGtHH*]Y!G

This is (heavily) based on the Haskell answer.
Explanation:
DcGH                           def c(G,H):
    R                          return
     ?                         Python's short circuiting _ if _ else _
       m+]'Hd                  map to [head(H)]+d
             ctGtH             c(G-1,tail(H))
       m+]'HdctGtH             map [head(H)]+d for d in c(tail(G),tail(H))
      +m+]'HdctGtHcGtH         (the above) + c(G,tail(H))
     ?                H        (the above) if H else (the below)
                       *]Y!G   [[]]*(not G)

Note: While the most recent version of Pyth, 1.0.9, was released tonight, and is therefore ineligible for this challenge, the same code works fine in 1.0.8.

APL(NARS), 80 chars, 160 bytes
{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

test and how to use it:
  f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
  o←⎕fmt
  o 5 f 1 2 3 4
┌0─┐
│ 0│
└~─┘
  o 4 f 1 2 3 4
┌1─────────┐
│┌4───────┐│
││ 1 2 3 4││
│└~───────┘2
└∊─────────┘
  o 3 f 1 2 3 4
┌4──────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 1 2 3│ │ 1 2 4│ │ 1 3 4│ │ 2 3 4││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊──────────────────────────────────┘
  o 2 f 1 2 3 4
┌6────────────────────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 1 2│ │ 1 3│ │ 1 4│ │ 2 3│ │ 2 4│ │ 3 4││
│└~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘2
└∊────────────────────────────────────────┘
  o 1 f 1 2 3 4
┌4──────────────────┐
│┌1─┐ ┌1─┐ ┌1─┐ ┌1─┐│
││ 1│ │ 2│ │ 3│ │ 4││
│└~─┘ └~─┘ └~─┘ └~─┘2
└∊──────────────────┘
  o 0 f 1 2 3 4
┌0─┐
│ 0│
└~─┘
  o ¯1 f 1 2 3 4
┌0─┐
│ 0│
└~─┘
  o 3 f (0 0)(1 2)(3 ¯4)(4 ¯5)
┌4────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌3────────────────────┐ ┌3────────────────────┐ ┌3─────────────────────┐ ┌3─────────────────────┐│
││┌2───┐ ┌2───┐ ┌2────┐│ │┌2───┐ ┌2───┐ ┌2────┐│ │┌2───┐ ┌2────┐ ┌2────┐│ │┌2───┐ ┌2────┐ ┌2────┐││
│││ 0 0│ │ 1 2│ │ 3 ¯4││ ││ 0 0│ │ 1 2│ │ 4 ¯5││ ││ 0 0│ │ 3 ¯4│ │ 4 ¯5││ ││ 1 2│ │ 3 ¯4│ │ 4 ¯5│││
││└~───┘ └~───┘ └~────┘2 │└~───┘ └~───┘ └~────┘2 │└~───┘ └~────┘ └~────┘2 │└~───┘ └~────┘ └~────┘2│
│└∊────────────────────┘ └∊────────────────────┘ └∊─────────────────────┘ └∊─────────────────────┘3
└∊────────────────────────────────────────────────────────────────────────────────────────────────┘
  o 4 f (0 0)(1 2)(3 ¯4)(4 ¯5)
┌1──────────────────────────────┐
│┌4────────────────────────────┐│
││┌2───┐ ┌2───┐ ┌2────┐ ┌2────┐││
│││ 0 0│ │ 1 2│ │ 3 ¯4│ │ 4 ¯5│││
││└~───┘ └~───┘ └~────┘ └~────┘2│
│└∊────────────────────────────┘3
└∊──────────────────────────────┘
  o 1 f (0 0)(1 2)(3 ¯4)(4 ¯5)
┌4────────────────────────────────────┐
│┌1─────┐ ┌1─────┐ ┌1──────┐ ┌1──────┐│
││┌2───┐│ │┌2───┐│ │┌2────┐│ │┌2────┐││
│││ 0 0││ ││ 1 2││ ││ 3 ¯4││ ││ 4 ¯5│││
││└~───┘2 │└~───┘2 │└~────┘2 │└~────┘2│
│└∊─────┘ └∊─────┘ └∊──────┘ └∊──────┘3
└∊────────────────────────────────────┘
  o 2 f ('Charli')('Alice')('Daniel')('Bob')
┌6──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌2─────────────────┐ ┌2──────────────────┐ ┌2───────────────┐ ┌2─────────────────┐ ┌2──────────────┐ ┌2───────────────┐│
││┌6──────┐ ┌5─────┐│ │┌6──────┐ ┌6──────┐│ │┌6──────┐ ┌3───┐│ │┌5─────┐ ┌6──────┐│ │┌5─────┐ ┌3───┐│ │┌6──────┐ ┌3───┐││
│││ Charli│ │ Alice││ ││ Charli│ │ Daniel││ ││ Charli│ │ Bob││ ││ Alice│ │ Daniel││ ││ Alice│ │ Bob││ ││ Daniel│ │ Bob│││
││└───────┘ └──────┘2 │└───────┘ └───────┘2 │└───────┘ └────┘2 │└──────┘ └───────┘2 │└──────┘ └────┘2 │└───────┘ └────┘2│
│└∊─────────────────┘ └∊──────────────────┘ └∊───────────────┘ └∊─────────────────┘ └∊──────────────┘ └∊───────────────┘3
└∊──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
  o ¯2 f ('Charli')('Alice')('Daniel')('Bob')
┌0─┐
│ 0│
└~─┘

the output seems ok... but bug are possible...
In practice it return void set as Zilde if input alpha out of range; if alpha is 1 it return the elements all one in its set (is it right?);
This below it seems a couple of char less but 2x slower above:
f←{(⍺>≢⍵)∨⍺≤0:⍬⋄1=⍺:,¨⍵⋄{w[⍵]}¨k/⍨{∧/</¨¯1↓{⍵,¨1⌽⍵}⍵}¨k←,⍳⍺⍴≢w←⍵}

05AB1E, 14 13 bytes
goLε¹ybRÏ}ʒgQ

Inspired by @Neil's Charcoal answer, so make sure to upvote him!
Try it online or verify a few more test cases.
If builtins were allowed this could have been 2 bytes:
.Æ

Try it online or verify a few more test cases.
Explanation:
g              # Get the length of the first (implicit) input-list
 o             # Take 2 to the power this length
  L            # Create a list in the range [1, 2**length]
   ε           # Map each integer `y` to:
    ¹          #  Push the first input-list again
     ybR       #  Convert integer `y` to binary, and reverse it
        Ï      #  And only keep values at truthy indices of `y` (so where the bit is a 1)
         }ʒ    # After the map: filter the list of lists by:
           g   #  Where the length of the inner list
            Q  #  Is equal to the (implicit) input-integer
               # (then the result is output implicitly)

.Æ             # Get all `b`-element combinations in list `a`,
               # where `b` is the first (implicit) input-integer,
               # and `a` is the second (implicit) input-list
               # (then the result is output implicitly)

JS - 117 188
(a,b,c=[])=>((d=(e,f,g=[])=>f*e?g.push(e)+d(e-1,f-1,g)+g.pop
()+d(e-1,f,g):f||c.push(g.map(b=>a[b-1])))(a.length,b),c)

(<source code>)(['Bob','Sally','Jonah'], 2)
     [['Jonah','Sally']['Jonah','Bob']['Sally','Bob']]

Array method madness
combination = (arr, k) =>
    Array
        .apply(0, { length: Math.pow(k+1, arr.length) })
        .map(Number.call, Number)
        .map(a => a
              .toString(arr.length)
              .split('')
              .sort()
              .filter((a, b, c) => c.indexOf(a) == b)
              .join(''))
        .filter((a, b, c) => a.length == k && c.indexOf(a) == b)
        .map(x => x.split('').map(y => arr[+y]))

C# (Visual C# Interactive Compiler), 141 bytes
l=>l.Any()?A(l.Skip(1)).Select(x=>l.Take(1).Union(x)).Union(A(l.Skip(1))):new object[][]{new object[]{}};B=(n,l)=>A(l).Where(x=>x.Count()==n)

Sadly, Tio/Mono doesn't seem to support generic type T declaration, so I'm forced to lose a few bytes with the object type instead.
//returns a list of all the subsets of a list
A=l=>l.Any()?A(l.Skip(1)).Select(x=>l.Take(1).Union(x)).Union(A(l.Skip(1))):new object[][]{new object[]{}};

//return the subsets of the required size
B=(n,l)=>A(l).Where(x=>x.Count()==n);

Try it online!

source: Stack Exchange

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

sort: votes


text:
Make a Number Expression
Few years ago, an esoteric programming language named 아희(Aheui) was created. Well, actually you don't need to know about this language or Korean characters.
Aheui uses stacks and a queue, but this time we use one stack and ignore other stacks and queue. You can push a number between 2 and 9 into a stack. You can do arithmetic operations by popping two numbers and pushing result. And you can duplicate a top number.
So, when I need a big number in Aheui, making a number was not an easy work. Push, push, multiply, duplicate, push, multiply, push, add…. It takes too much time and sometimes waste of bytes. I need a shortest expressions.
Summary
Your task is to write a function or a program which takes a number n (0 <= n <= 1000000) and returns concatenation of tokens.
Tokens are basically a postfix notation. Tokens are consisted of

Number between 2 and 9, which means "push number into stack"
+, -, /, *, which means "pop two numbers from stack, do arithmetic operation, push the result into stack". All calculations are in integer.
>, which means "duplicate a top number"

Tokens will be concatenated with empty string, so 5 5 + will be 55+.
After calculations, n must be on the top of the stack.
Sample input and output
INPUT = 0
OUTPUT = 22-
(or 33-, 44-, whatever)

INPUT = 1
OUTPUT = 22/
(or 32-, 33/, whatever)

INPUT = 5
OUTPUT = 5
(We don't need calculations, just push)

INPUT = 64
OUTPUT = 88*
(or 8>*)

INPUT = 1337
OUTPUT = 75*2+>*48*-
(This may not be a shortest solution)

Scoring
This is a list of test cases. Test cases are seperated by a new line character. You may write a test script which converts those bunch of numbers to string of tokens, or you can do it by your hand.
Let

S = size of complete function or program
O = length of converted strings
I = size of test cases (In this case, I = 526)

Then your score will be S * (O / I). Sizes are in bytes.
S includes function declarations, #includes, imports, whatever. Test script is not counted.
Scoring example
Let S is 150.
Sample Test cases
0
1
5
64
1337

Sample Output
22-22/588*75*2+>*48*-

In this case, I = 9, and O = 21. So your score is 150 * (21 / 9) = 350.
Rules

Standard "loopholes" are forbidden.
Lowest score wins.
If there is a tie, smaller code size wins.
Winner will be selected after three weeks (2014-08-04).

I wrote a validator in Node.js. Put input.txt and output.txt in same directory, and run node validator.js.
And I found two-year-old similar question. But scoring is different (this question includes code size in score), and this question can't use 1. So I hope it's not a duplicate.

Clarification needed. 1.The requested number must be on top of stack? What if the stack is not empty after popping the result? 2.Division is integer or floating point?

@edc65 1. Yes. It must be on the top of the stack. 2. Integer, floor. 53/ = 1, not 2.

Javascript, Score = 1663.46768
function X($){S=Math.sqrt;function J(A){return A.join("")}function M(A,B){return A.length<B.length?A:B}function D(q){var w="",e,r,t,y;for(e=9;e>1;e--){r=~~(q/e);t=r*e-q;if(t==0)y=J([G(r),e,"*"]);else y=J([G(r),e,"*",G(-t),"+"]);if(w=="")w=y;w=M(w,y)}return w}function Q(a){var s=~~S(a),d=a-s*s,f=J([G(s),">*",G(d),"+"]),g;s=Math.ceil(S(a));d=s*s-a;g=J([G(s),">*",G(d),"-"]);return M(f,g)}function G(z){var x,c,v,b,n,m;if(z==0)return"22-";if(z==1)return"22/";if(z>1&&z<10)return""+z;if(z>9&&z<19){x=~~(z/2);c=z-x;return J([x,c,"+"])}for(v=9;v>1;v--){b=~~(z/v);if(b>1&&b<10&&b*v==z)return J([v,b,"*"])}n=S(z);if(~~n==n)return J([G(n),">*"]);return M(D(z),Q(z))}return G($)}

This is my attempt for my question, and this is output. Code size is 671, and output size is 1304. Score is 1663.46768 (rounded up to 5 decimal places).

If you can transform your functions (or some of them) to functional form, meaning that you can transform them such that a function like function F(a){return <lots of code>} becomes possible, you can use the ECMAscript 6 syntax F=(a)=><lots of code>. Furthermore, you have if(z==0)return"22-";if(z==1)return"22/";. I think you can compress that to if(z<2)return["22-","22/"][z];. (If z can be negative, add a &&z>=0.)

+1 Great job! Golfed a little more and rewrited for EcmaScript 6 your code size is 406. X=$=>(S=Math.sqrt,M=(A,B)=>A.length<B.length?A:B,D=(q,w="",e,r,t,y)=>{for(e=9;e>1;e--)r=~~(q/e),t=q-r*e,y=t?G(r)+e+"*"+G(t)+"+":G(r)+e+"*",w=M(w||y,y);return w}, Q=(a,s=~~S(a))=>M(G(s)+">*"+G(a-s*s)+"+",G(++s)+">*"+G(s*s-a)+"-"), G=(z,v,b)=>{if(z<18)return z<2?"22"+"-/"[z]:z<10?z:"8"+(z-8)+"+";for(v=9;v>1;v--)if((b=~~(z/v))>1&b<10&b*v==z)return""+v+b+"*";return ~~(v=S(z))-v?M(D(z),Q(z)):G(v)+">*"},G($))

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


text:
Simulate Rule 110
Rule 110 is a cellular automaton with some interesting properties.
Your goal is to simulate a rule 110 in as few characters as possible.
For those who don't know, rule 110 is simulated line by line in a grid. Each square in a line of the grid looks at the squares above, above-left and above-right to determine what cell it should be.
current pattern  111 110 101 100 011 010 001 000
new cell          0   1   1   0   1   1   1   0

Input: numbers from 0 to 39 representing top row nth input square, in any reasonable format (comma-separated string, list, function arguments). To accommodate 1-indexed languages, numbers may also be 1-indexed and so range from 1 to 40.
Example input:
38,39

Output: A 40 x 40 grid representing the automata running including the first row. You should leave 0 as blank and 1 as any visible printing character. Trailing spaces are allowed, as long as the actual grid can reasonably be distinguished. The bottom of the grid may have a newline but there should not be blank lines between grid lines.
Example output:
                                  XX
                                 XXX
                                XX X
                               XXXXX
                              XX   X
                             XXX  XX
                            XX X XXX
                           XXXXXXX X
                          XX     XXX
                         XXX    XX X
                        XX X   XXXXX
                       XXXXX  XX   X
                      XX   X XXX  XX
                     XXX  XXXX X XXX

etc.
Note: A similar question about 1D cellular automata has already been asked, but I hope that, by using only one rule, shorter answers can be written.

Do the patterns wrap around (i.e. does the left-most cell check the right-most cell in the line above it)?

If it's singular, then it's a cellular automaton.

Do we have to take input as a comma-delimited string or (if we write a function) can we take a list of numbers as input? (At least one answer does the latter.)

The answers may be fractionally shorter than Simulate any 1D cellular automaton because the rule is hard-coded rather than having to be parsed from the input, but other than that the answers are going to be the same. If it were a different rule then there would be potential for savings, but how on Earth would special-casing a Turing-powerful rule save anything over a general implementation?

@PeterTaylor I was thinking along the lines of some clever bithack. In addiction the input method and generation time is different. Lastly the current answers are much more than fractionally shorter (which doesn't really mean anything)

@Ventero They do not in this version.

How do we handle edges?

@xnor Treat them as 0

if you start at 1 and going to fill 40x40 whats the input for?

@Sylwester I'm sorry, I don't quite understand what you're asking. Can you clarify?

@qwr I cannot se the correlation between the input 38,39 and the 14 lines output starting with 3 (xx).

You should probably specify that the space character can't be used for a 1.

Rule #110: Mathematica has a built-in for all problems?

Come on, someone do Husk!

Are 1-based indexing allowed, is a leading 0/space allowed?

@EvanCarroll: Here you go :D

@BMO this is an old question, but since nowadays consensus is to allow flexible input formats, I'll modify the question to allow it

CJam - 47
S40*l',/{i'!t}/{N40,S3$S++f{>3<2b137Yb='!^}}39*

It uses ! for "1" cells.
Try it at http://cjam.aditsu.net/
Explanation:
S40* makes a string (array) of 40 spaces
l',/ reads a line and splits by comma
{…}/ executes the block for each item (the numbers in string form)
- i'!t converts the number to integer and sets the item at that position in the previous string (initially 40 spaces) to '!'
At this point we have obtained the first line.
{…}39* executes the block 39 times
- N adds a newline
- 40, makes the array [0 1 … 39]
- S3$S++ copies the previous line (position 3 on the stack) and pads it with a space on each side
- f{…} executes the block for {each number from 0 to 39} and {the padded line}
-- >3< takes a slice of 3 items from the padded line starting at the current number
-- 2b converts from base 2; the items we sliced are not base-2 digits, but characters get converted to their ASCII values and ' ' mod 8 is 0 and '!' mod 8 is 1
-- 137Yb converts 137 to base 2 (Y = 2), obtaining [1 0 0 0 1 0 0 1], which is 110 reversed and negated (on 8 bits)
-- ='!^ gets the corresponding base-2 digit (the array wraps around so the index is taken mod 8) and xor's it with the '!' character, resulting in '!' for 0 and ' ' for 1

Ruby, 113 characters
c=[0]*41
eval"[#{gets}].map{|i|c[i]=1}"+'
c=(0..39).map{|x|putc" X"[u=c[x]]
110[4*c[x-1]+2*u+c[x+1]]}<<0;puts'*40

Takes input on stdin. To use a different rule, simply replace the 110 in the last line with whatever rule you want to try.
Example:
$ ruby 110.rb <<< 38,39
                                      XX
                                     XXX
                                    XX X
                                   XXXXX
                                  XX   X
                                 XXX  XX
                                XX X XXX
                               XXXXXXX X
                              XX     XXX
                             XXX    XX X
                            XX X   XXXXX
                           XXXXX  XX   X
                          XX   X XXX  XX
                         XXX  XXXX X XXX
                        XX X XX  XXXXX X
                       XXXXXXXX XX   XXX
                      XX      XXXX  XX X
                     XXX     XX  X XXXXX
                    XX X    XXX XXXX   X
                   XXXXX   XX XXX  X  XX
                  XX   X  XXXXX X XX XXX
                 XXX  XX XX   XXXXXXXX X
                XX X XXXXXX  XX      XXX
               XXXXXXX    X XXX     XX X
              XX     X   XXXX X    XXXXX
             XXX    XX  XX  XXX   XX   X
            XX X   XXX XXX XX X  XXX  XX
           XXXXX  XX XXX XXXXXX XX X XXX
          XX   X XXXXX XXX    XXXXXXXX X
         XXX  XXXX   XXX X   XX      XXX
        XX X XX  X  XX XXX  XXX     XX X
       XXXXXXXX XX XXXXX X XX X    XXXXX
      XX      XXXXXX   XXXXXXXX   XX   X
     XXX     XX    X  XX      X  XXX  XX
    XX X    XXX   XX XXX     XX XX X XXX
   XXXXX   XX X  XXXXX X    XXXXXXXXXX X
  XX   X  XXXXX XX   XXX   XX        XXX
 XXX  XX XX   XXXX  XX X  XXX       XX X
XX X XXXXXX  XX  X XXXXX XX X      XXXXX
XXXXXX    X XXX XXXX   XXXXXX     XX   X

Python - 141
i=input()
o=range(40)
l=''.join(' X'[c in i]for c in o)
for r in o:print l;l=''.join('X '[l[c-1:c+2]in('XXX','   ','X  ','','  ')]for c in o)

Run as e.g. python 110.py <<< 38,39

['X',' '] could be changed to 'X ' to save 5 characters.

My favourite fruit is now an o=range()

Mathematica, 122 bytes
f[a_]:=Riffle[CellularAutomaton[110,Array[If[MemberQ[ToExpression["{"<>a<>"}"],#-1],1,0]&,40],39]/.0->" "/.1->"X","
"]<>""

Yes, you might view this as abusing this loophole, but a) that loophole is quite disputed, b) a Cellular Automaton question needs a Mathematica answer (especially one about Rule 110) and c) Ventero's Ruby answer is shorter anyway, so I don't think any harm is done.
Most of the characters are used for input parsing and output formatting. The actual automaton is simulated using
CellularAutomaton[110,initialGrid,39]

This uses periodic boundary conditions (so the grid wraps around).

q, 67 62 58 bytes
Assumes no wrap-around:
{40{not(2 sv'flip 1 0 -1 xprev\:x)in 0 4 7}\@[40#0b;x;~:]}

Old version
{40{not(flip(prev;::;next)@\:x)in 3 cut 111100000b}\@[40#0b;x;not]}
{40{not(flip 1 0 -1 xprev\:x)in 3 3#111100000b}\@[40#0b;x;~:]}

Python, 186
def r(s,m=range(40)):
 s=[int(i in s)for i in m]
 for g in m:print''.join([' X'[i]for i in s]);s=[int(not''.join(map(str,s[i-1:i+2]if i else s[:2]))in'111 100 000 00'.split())for i in m]

Decent but probably not optimal.
You didn't specify how input is gotten so I just made a function.
Use example:

r([38,39])

Output:
                                      XX
                                     XXX
                                    XX X
                                   XXXXX
                                  XX   X
                                 XXX  XX
                                XX X XXX
                               XXXXXXX X
                              XX     XXX
                             XXX    XX X
                            XX X   XXXXX
                           XXXXX  XX   X
                          XX   X XXX  XX
                         XXX  XXXX X XXX
                        XX X XX  XXXXX X
                       XXXXXXXX XX   XXX
                      XX      XXXX  XX X
                     XXX     XX  X XXXXX
                    XX X    XXX XXXX   X
                   XXXXX   XX XXX  X  XX
                  XX   X  XXXXX X XX XXX
                 XXX  XX XX   XXXXXXXX X
                XX X XXXXXX  XX      XXX
               XXXXXXX    X XXX     XX X
              XX     X   XXXX X    XXXXX
             XXX    XX  XX  XXX   XX   X
            XX X   XXX XXX XX X  XXX  XX
           XXXXX  XX XXX XXXXXX XX X XXX
          XX   X XXXXX XXX    XXXXXXXX X
         XXX  XXXX   XXX X   XX      XXX
        XX X XX  X  XX XXX  XXX     XX X
       XXXXXXXX XX XXXXX X XX X    XXXXX
      XX      XXXXXX   XXXXXXXX   XX   X
     XXX     XX    X  XX      X  XXX  XX
    XX X    XXX   XX XXX     XX XX X XXX
   XXXXX   XX X  XXXXX X    XXXXXXXXXX X
  XX   X  XXXXX XX   XXX   XX        XXX
 XXX  XX XX   XXXX  XX X  XXX       XX X
XX X XXXXXX  XX  X XXXXX XX X      XXXXX
XXXXXX    X XXX XXXX   XXXXXX     XX   X

I did specify input: in your case you would have to use input() and format the input as specified in the original post.

Mathematica, 113 chars
Another Mathematica answer using CellularAutomaton.
Print@@" "["X"][[#]]&/@CellularAutomaton[110,SparseArray[#+1->1&/@ImportString[InputString[],"CSV"][[1]],40],39];

Interesting, how does " "["X"][[#]]& work?

@m.buettner " "["X"][[1]] is "X". " "["X"][[0]] returns the head of " "["X"], namely " ".

Oh, I see. So that's just generally saving a character for lists. That's really clever. I guess you could add it to http://codegolf.stackexchange.com/questions/12900/tips-for-golfing-in-mathematica

Lua - 351
Not the ideal language for golfing.
s,n,t,u=arg[1],{},table.remove,table.insert
for i=1,40 do u(n,i,'.') end
for i in s:gmatch("%d+")do u(n,i,'x');t(n)end
function a(b) c="";for i=1,40 do c=c..b[i] end;print(c);return c end
for i=1,40 do z= n[40]..a(n)..n[1];for k=2,41 do y=string.sub(z,k-1,k+1);if y=="xxx"or y=="x.." or y=="..." then u(n,k-1,'.')else u(n,k-1,'x')end;t(n)end end

do u(n,i,'x') that’s intentional, isn’t it?

C - 178
This code depends on the fact that each row in a matrix is stored in contiguous memory. Also, it does not print the first row, but it prints the next 40 ones, since the rules only specified a 40x40 grid.
Indented for readability only, the byte count only includes necessary code.
a[41][42],i,j,*t;
main(){
    while(scanf("%d,",&j)>0)
        a[i][j]=1;
    for(;i<40;i++,puts(""))
        for(j=0;++j<40;)
            t=&a[i][j],
            putchar((*(t+42)=1&(110>>(*(t+1)?1:0)+(*t?2:0)+(*(t-1)?4:0)))?88:32);
}

Haskell, 175 170 169 136 127 124 bytes
−9 bytes thanks to @bmo

t(a:b:r:_)=mod(b+r+b*r+a*b*r)2
w%a=take 40.map w.iterate a
d l=t%tail$0:l++[0]
f l=map(" #"!!)%d$(fromEnum.(`elem`l))%succ$0

Try it online!

Microsoft Excel, 21 19 characters
(Not sure how to score this actually. I know this takes 39*40 or 1560 formulas, but they all depend on the first one.)
As a bonus, this works in LibreOffice Calc too.
The formula
=(B1<>C1)+C1*(B1>A1
To get the 40x40:

Insert the formula at cell B2. (Don't forget the = sign!)
Drag the cells to Column AO.
Drag these cells to Row 40.

Extra niceties:

Conditionally format cells to Good when value is TRUE
Set cell widths to 0.3" or something.

Explanation

The input is the first row. A value that can be converted to TRUE, such as 1 is TRUE. A blank cell or anything else is a FALSE.
Column A is just a buffer to make edge cases easier to deal with.
This is easier to see if you do the conditional formatting stuff.
The formula is really just a hacky way of saying (B XOR C) + (BCA')

Of course, the implication here is that Excel is Turing Complete without VBA.

I believe you can shorten the second part to (B1>A1)

@JoKing Indeed. Good spot.

Python 3, 126 bytes (as function)
def r(n,r):
 for d in range(r):print("".join(" o"[n>>i&1]for i in range(40)));n=sum((110>>(n>>i&7)&1)<<i+1 for i in range(40))

142 bytes with stdin
n,r=map(int,input().split())
for d in range(r):print("".join(" o"[n>>i&1]for i in range(40)));n=sum((110>>(n>>i&7)&1)<<i+1 for i in range(40))

188, my first attempt and favourite
import itertools as t;print("\n".join(map(lambda n:"".join(" o"[n>>i&1]for i in range(n.bit_length())),t.accumulate(range(1,40),lambda n,d:sum((110>>(n>>i&7)&1)<<i+1 for i in range(d))))))

Welcome to Code Golf, and nice answer!

If you change 110 to 90 , you get Sierpiński triangles for free :D
And 30 gets you an adequate pseudo random number generator.

@ROGUH and from an initial state of 0b11, 120 grows with width in proportion to the square-root of time (and is the n=2 member of an infinite sequence of rules growing with Θ(ⁿ√t), which admits some interesting analysis with bitwise operators and generating functions :-)

Haskell, 135 131 130 bytes
-1 byte thanks to Ørjan Johansen (rearranging take 40)
Completely different approach to FrownyFrog's answer but about the same length:
(a?b)r=mod(b+r+b*r+a*b*r)2
r x=0:(zipWith3(?)x=<<tail$tail x++[0])
f y=take 40$map(" o"!!)<$>iterate r[sum[1|elem i y]|i<-[0..40]]

Uses \$1\$-indexing and has a leading space on each line, try it online!
Explanation
We're going to work with length-\$41\$ lists with values \$\texttt{0}\$, \$\texttt{1}\$, so let's start with the correct array:
f y=                               [sum[1|elem i y]|i<-[0..40]]

Next we're going to iterate the rule \$40\$ times:
    take 40$              iterate r

And finally map each \$\texttt{0}\$ and \$\texttt{1}\$ to some fancy character:
            map(" o"!!)<$>

The function r which applies the \$\texttt{110}\$-rule is pretty simple: Using zipWith3 and some padding we can outsource the actual decision for the next cell to (?):
r x=0:(zipWith3(?)x=<<tail$tail x++[0])

The (?) operator is the most interesting part of the solution: Previously I used a Boolean rule generated with a Karnaugh map, but turns out there is an even more concise way:
(a?b)r=mod(b+r+b*r+a*b*r)2

Save a byte by putting take 40$ before map(" o"!!)<$> .

Husk, 31 28 bytes
Hah, Husk is beating Jelly!
†!¨↑¨↑40¡ȯẊȯ!ḋ118ḋėΘ`:0M#ŀ40

Try it online!
Explanation & Ungolfed
Before adding an explanation, let me ungolf this a bit.. Let's first remove the various compositions, add explicit parentheses and uncompress the ¨↑¨ string. Also let's replace 40 with 4 for a more readable explanation:
†!"t "↑4¡(Ẋ(!ḋ118ḋė)Θ`:0)M#ŀ4  -- example input: [3]
                           ŀ4  -- lower range of 4: [0,1,2,3]
                         M     -- map over left argument
                          #    -- | count in list
                               -- : [0,0,0,1]
        ¡(              )      -- iterate the following indefinitely (example with [0,1,1,1])
                     `:0       -- | append 0: [0,1,1,1,0]
                    Θ          -- | prepend 0: [0,0,1,1,1,0]
          Ẋ(       )           -- | map over adjacent triples (example with  1 1 0
                  ė            -- | | create list: [1,1,0]
                 ḋ             -- | | convert from base-2: 6
                               -- | | convert 118 to base-2: [1,1,1,0,1,1,0]
                               -- | | 1-based index: 1
                               -- | : [1,1,0,1]
                               -- : [[0,0,0,1],[0,0,1,1],[0,1,1,1],[1,1,0,1],[1,1,1,1],[1,0,0,1],...]
      ↑4                       -- take 4: [[0,0,0,1],[0,0,1,1],[0,1,1,1],[1,1,0,1]]
†                              -- deep map the following (example with [1,1,0,1])
 !"t "                         -- | use each element to index into "t ": "tt t"
                               -- : ["   t","  tt"," ttt","tt t"]

Java, 321 characters
Input passed as argument from command line, for example java R 38,39
I have never written more obfuscated java code :-)
class R{public static void main(String[]a) {
Integer s=40;boolean[]n,o=new boolean[s];
for(String x:a[0].split(","))o[s.valueOf(x)]=s>0;
for(Object b:o){n=o.clone();
for(int j=0;j<s;j++){
boolean l=j>1&&o[j-1],r=o[j],c=j+1<s&&o[j+1];
n[j]=!(l&c&r|l&!c&!r|!(l|c|r));
System.out.print((r?"X":" ")+(j>s-2?"\n":""));
}o=n;}}}

Update:
Correct output example here (with 40 lines not 50):
New output below (removed previous one for brevity):
                                      xx
                                     xxx
                                    xx x
                                   xxxxx
                                  xx   x
                                 xxx  xx
                                xx x xxx
                               xxxxxxx x
                              xx     xxx
                             xxx    xx x
                            xx x   xxxxx
                           xxxxx  xx   x
                          xx   x xxx  xx
                         xxx  xxxx x xxx
                        xx x xx  xxxxx x
                       xxxxxxxx xx   xxx
                      xx      xxxx  xx x
                     xxx     xx  x xxxxx
                    xx x    xxx xxxx   x
                   xxxxx   xx xxx  x  xx
                  xx   x  xxxxx x xx xxx
                 xxx  xx xx   xxxxxxxx x
                xx x xxxxxx  xx      xxx
               xxxxxxx    x xxx     xx x
              xx     x   xxxx x    xxxxx
             xxx    xx  xx  xxx   xx   x
            xx x   xxx xxx xx x  xxx  xx
           xxxxx  xx xxx xxxxxx xx x xxx
          xx   x xxxxx xxx    xxxxxxxx x
         xxx  xxxx   xxx x   xx      xxx
        xx x xx  x  xx xxx  xxx     xx x
       xxxxxxxx xx xxxxx x xx x    xxxxx
      xx      xxxxxx   xxxxxxxx   xx   x
     xxx     xx    x  xx      x  xxx  xx
    xx x    xxx   xx xxx     xx xx x xxx
   xxxxx   xx x  xxxxx x    xxxxxxxxxx x
  xx   x  xxxxx xx   xxx   xx        xxx
 xxx  xx xx   xxxx  xx x  xxx       xx x
xx x xxxxxx  xx  x xxxxx xx x      xxxxx
xxxxxx    x xxx xxxx   xxxxxx     xx   x

Doing another puzzle I learned something interesting about nesting statements in for loops in php, and suddenly they are far more complex than I originally thought. When I get time I reckon I can beat this score considerably. For now though it remains unchanged at a non-competitive 408.

My php version 408 characters:
This was a great puzzle. I also spent ages playing with the inputs as these are fascinating things it must be said. Anyway, here is my PHP version (which is nowhere near as good as some of the answers posted but is complete. In 0th position only take above and above right, in 39th position only take above and above left, ie no wrapping. So here is my version:
<?php $a='38,39';$b='';$d=explode(',',$a);for($i=0;$i<40;++$i){$c=' ';
foreach($d as $k=>$v){if($v == $i){$c='x';}}$b.=$c;}echo $b."\n";
for($x=1;$x<41;++$x){$o='';for($i=1;$i<41;++$i){if(($i>1)AND(substr($b,$i-2,1)=='x')){
$l=1;}else{$l=0;}if((substr($b,$i-1,1))=='x'){$v=1;}else{$v=0;}if((substr($b,$i,1))=='x'){
$r=1;}else{$r=0;}if((($l+$v+$r)==2)OR(($v+$r)==1)){$o.='x';}else{$o.=' ';}}
echo $o."\n";$b=$o;}?>

You can see it and run it here: http://codepad.org/3905T8i8
Input is a input string at the start as $a='38, 39';
Output is as follows:
xx removed as was too long originally - had 50 lines, not 40 xx

Hope you like it!!!
PS I had to add a few line breaks to the code so you could see all of it and not have it stretch accross the page with a scroll bar.

Your output has 50 lines

Ah, that was because I was playing with it after I finished and seeing what happened. Altering the rules slightly has such interesting affects. Anyway have changed it to 40 now and sorry for missing that.

You may want to change the output too :p

Corrected the output and added new codepad link with correct value. Thank you again.

Remove the space between “as $k” in the foreach, “as$k” is valid php code

Stax, 24 bytesCP437
╦♥µ╤u{£┬íQ<;▀ΦΣ╢╕╚äZ↕áû↑

Run and debug online!
Uses the codepoint 1 in CP437 for "1" cells.
Excellent case to show the power of this language.
Explanation
Uses the unpacked version (29 bytes) to explain.
0]40X*,1&xDQ0]|S3B{:b^374:B@m
0]40X*                           Prepare a tape with 40 cells
      ,1&                        Assign 1 to the cells specified by the input
         xD                      Repeat the rest of the program 40 times
           Q                     Output current tape
            0]|S                 Prepend and append a 0 cell to it
                3B               All runs of length 3
                  {         m    Map each run with block
                   :b            Convert from binary
                     ^           Increment (call this value `n`)
                      374:B      The binary representation of 374
                                 [1,0,1,1,1,0,1,1,0]
                                 which is `01101110` reversed and prepended a 1
                           @     Element at 0-based index `n`

K (ngn/k), 44 36 bytes
{"X "39{(2\145)@2/'3':1,x,1}\^x?!40}

Try it online!
{ } function with argument x
!40 list of ints from 0 to 39
x? find their indices in x, use 0N (the "integer null") for not found
^ which of them are nulls? this gives us the input, negated
39{ }\ apply 39 times, collecting intermediate results in a list
1,x,1 surround the list with 1s (negated 0s)
3': triples of consecutive items
2/' binary decode each
@ use as indices in ...
2\145 binary encode 145 (negated bits of 110)
"X " finally, use the 40x40 matrix as indices in the string "X " (the @ here is implicit)

Pip, 54 bytes
x:Y0X40RAgoL40{Fi,40x@i:01110110@FB(y@>i@<3)Y0.xPxR0s}

Pip is turing complete?!
(Jokes aside, this was a fun pip answer.)
Explanation
x:Y0X40RAgoL40{Fi,40x@i:01110110@FB(y@>i@<3)Y0.xPxR0s}
x:Y0X40RAgo                                             Assign 40 spaces to x and replace the input indices with 1
                                                        The same value is also yanked to y.
           L40{                                      }  Repeat 40 times
               Fi,40                                    Loop variable i through range 1-40
                    x@i:                                Assign character at index i to:
                        01110110@                       a number in 01110110 at index:
                                 FB(y@>i@<3)            a 3 letter substring of y starting at i, converted to binary.
                                            Y0.x        Yank(assign value) of 0 concantenated with x to y
                                                PxR0s   Print x with zeros replaced with spaces

Try it online!

Jelly, 22 bytes
ṬµØ0jḄ3Ƥị236B¤µ39Ð¡Yo⁶

Try it online!
Took some inspiration from Erik's answer.

JavaScript, 242, 202 bytes

// redable version
((...l)=>{
  k=Array(40).fill(' ');l.map(x=>k[x]='X')

  for(i=0;i++<40;){
    console.log(k.join``);
    k=k.map((x,i)=> i==0|| (i==k.length) || ["   ","XXX","X. "].includes(k.at(i-1)+k.at(i)+k.at(i+1)) ? ' ':'X')
  }
})(38,39)

Minified:
((...l)=>{k=Array(40).fill(' ');l.map(x=>k[x]='X');for(i=0;i++<40;){console.log(k.join``);k=k.map((x,i)=>i==0||(i==k.length)||["   ","XXX","X. "].includes(k.at(i-1)+k.at(i)+k.at(i+1))?' ':'X')}})(38,39)

Python, 150 bytes
import sys
I=''.join(' X'[str(A)in sys.argv]for A in range(40))
for _ in I:print(I);I=''.join('X '[(' '+I+' ')[A:A+3]in'XXX.X   ']for A in range(100))

Example: python rule110.py 39
Old solution with hardcoded initial universe:
I=' '*99+'X'
for _ in I:print(I);I=''.join('X '[(' '+I+' ')[A:A+3]in'XXX.X   ']for A in range(100))

The rule became a bit complicated.
Based on another answer, I check only the rules that result in a dead cell because there's only 3 rules that can be compressed into a small substring check.
The cell at the next I[i] dies if I[i:i+3] is any of XXX X  , or   (3 spaces). Since I[i:i+3] is a string, we can check if it's a substring of 111 or 1000.
More concisely, I[i] = ' ' if I[i:i+3] is a substring of 111SEP1000, where SEP is anything besides X and  .

Nice solution! Since _ is already a space, you can change (' '+I+' ') to (_+I+_) for 95 bytes

...except, it looks like the challenge requires you to handle multiple input numbers, not just the 38, 39 case—that was just given as an example.

You're right. I've got to handle input, which will likely push me over 99 bytes.

The argv handling could be golf'd more, but it's late. 150 is a nice multiple of 50 anyway ha

Jelly, 29 bytes
‘;41ṬṖŻ;0Ḅe“¢£¤¦©‘Ɗ3ƤƊ39Ð¡Yo⁶

Try it online!

Perl 5 -a, 99 bytes
$_=$"x40;for$b(@F){substr$_,$b,1,1}for$b(1..40){say;s,(?<=(.)).(?=(.)),"$1$&$2"=~/111|  $/?$":1,ge}

Try it online!

Rust, 370 bytes
fn a(f:&[u8]){let mut g=[0;40];for e in f{g[*e as usize]=1;};p(&g);for _ in 0..39{let mut n=[0;40];for e in 0..40{let m=match e{0=>r(g[0]*2+g[1]),39=>r(g[38]*4+g[39]*2),_=>r(g[e-1]*4+g[e]*2+g[e+1])};n[e]=m;}g=n;p(&g);}}fn p(g:&[u8]){println!("{}",g.iter().map(|x|format!("{}",x)).collect::<String>().replace("0"," "));}fn r(b:u8)->u8{match b{0|4|7=>0,1|2|3|5|6=>1,_=>2}}

Try it online!
A probably very naive implementation. Input is a slice of u8 representing the starting 1s. Prints rule 110, with 1 as its character.
Ungolfed:
fn r110(filled: &[u8]) {
    let mut grid = [0; 40];
    for e in filled { grid[*e as usize] = 1; }

    println!(
            "{}",
            grid
            .iter()
            .map(|x| format!("{}",x))
            .collect::<String>()
            .replace("0", " "));

    for _iteration in 0..39 {
        let mut next_grid = [0; 40];
        for element in 0..40 {
            let next = match element {
                0 => {
                    rule(grid[0]*2 + grid[1])
                }
                39 => {
                    rule(grid[38]*4 + grid[39]*2)
                }
                _ => {
                    rule(grid[element-1]*4 + grid[element]*2 + grid[element+1])
                }
            };
            next_grid[element] = next;
        }
        grid = next_grid;
        println!(
            "{}",
            grid
            .iter()
            .map(|x| format!("{}",x))
            .collect::<String>()
            .replace("0", " "));
    }
}

fn rule(bits: u8) -> u8 {
// current pattern  111 110 101 100 011 010 001 000
// new cell          0   1   1   0   1   1   1   0
    match bits {
        0 | 4 | 7 => 0,
        1 | 2 | 3 | 5 | 6 => 1,
        _ => 2
    }
}
```


text:
Checking periodic table words
Given a sequence of letters, write a program to construct it using symbols on the periodic table. For example, given the input bacon, the program should output:
BaCoN
BAcON
BaCON

Note that capitalization is important. Standard loopholes apply. If a word can't be formed, any error message may be printed.
Edit: All possible ways to make the sequence must be output.

I like the question, but I'd suggest expanding it a bit more to avoid cheap tactics.

I read that challenge before posting mine; I believe that they use different algorithms. This one talks about permutations of symbols and the other can be solved with a pretty unsophisticated algorithm. In general, I think they have different intents.

@ɐɔıʇǝɥʇuʎs How would you suggest expanding the challenge?

I've edited the question to hopefully further distinguish it from the earlier one.


text:
Shortest expression for {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}
Given list of integers {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}.
For those who interested these numbers are used in weekday calculation.
Weekday = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, where m[n] - expression I'm searching, d - day of month, y - year - (month <= 2).
Construct expression consisting of arithmetic, logic and bitwise operators, which will output for positive integer n integer m so that m % 7 equals n-th number in the list.
Branches, ternary operators, table lookups and pointers are not allowed.
Score:
1 - for | & ^ ~ >> << operators
1.1 - for + - < > <= >= == != ! && || operators
1.2 - for * operator
1.4 - for / % operators
Answer with lowest score wins.
Personally I have found:

 (41*n)>>4+((n+61)>>4)<<2 with score 6.4.
 I thought this will be hard to find so provided own expression to start with.

I guess array dereferencing (and the kin) isn't allowed either?

Oh, yes of course, I have edited the question.

The question would be greatly improved by some motivation. Where do those numbers come from?

table lookups Interesting phrasing I suppose...

Why not count the %7 in the score? Maybe there's another solution not using %. Is zero positive, negative, both or nothing?

@ThomasW. %7 needs to be calculated in every case.

Yes, with the rest of the formula you have given in your updated question, this is clear now. Thanks.

@m.buettner Thank you for comment. It's my first question, I thought that own example will be good. Next time I won't steal fun)

What language is the expression supposed to be in? From the examples, I'm assuming C or some C-like language with similar operator syntax (such as C++ or Java), but it would be nice if you could include this information in the challenge (and tag it with the appropriate language tag).

I want to be it in C. However any language is ok if used operators which are in C language.

2 2.2
I love arbitrary precision arithmetic.
0x4126030156610>>(n<<2)

Or, if you don't like hex,
1146104239711760>>(n<<2)

Test:
print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]

Could you perhaps make a lookup table with 4*n instead, and save 0.2 points by writing it as n<<2?

@xnor Absolutely! Just to to switch from octal to hexadecimal. Just as sec.

Cool. I'm pretty convinced nothing can do better because it would require using only one operation, and they all seem to have too much structure mod 7. My best candidate of integer floor division const/n runs into a contradiction with n=4 and n=8.

@xnor Another close one is const%n which could satisfy everything except n=1,2 and 3.

I was gonna do the same thing, but you beat me to it...

No way to beat this I think) Btw, how small expression with 32-bit integers is possible?

@user2992539 I don't know what's optimal under your precise rules, but check out Mike Keith's solution here: http://www.merlyn.demon.co.uk/zel-like.htm#Keith

Rechoosen as accepted because first one with smallest score.

2.0
(127004 >> i) ^ 60233

or (score 2.2) :
(i * 3246) ^ 130159

All found with brute force :-)

Since this has the same score as isaacg's answer, but doesn't uses 64-bit integers, I'm choosing this as accepted answer. Thank you for answer!

@user2992539 While it's nice that this answer uses 32-bit integers, you didn't specify this criterion in your challenge, which makes isaacg's answer perfectly valid. Therefore, the two answers tie and I think it's only fair to accept the first one that got this score. (Kudos to Super Chafouin, though, +1!)

@m.buettner I have to agree with you. Next time, I will be more careful with description and answer selection.

For others to learn, could you elaborate on how you did the brute force calculation?

@Thomas I just made a double for loop, testing all the values p, q for the formula (p >> i) ^ q, then went to take a coffee, and 10 mn after came to read the results.

@SuperChafouin: ok, thanks. So you already had a clear pattern in mind and didn't brute force all operators as well.

35.3
I suspect this may be the least efficient method to create the list:
1.7801122128869781e+003 * n -
1.7215267321373362e+003 * n ^ 2 +
8.3107487075415247e+002 * n ^ 3 -
2.0576746235987866e+002 * n ^ 4 +
1.7702949291688071e+001 * n ^ 5 +
3.7551387326116981e+000 * n ^ 6 -
1.3296432299817251e+000 * n ^ 7 +
1.8138635864087030e-001 * n ^ 8 -
1.3366764519057219e-002 * n ^ 9 +
5.2402527302299116e-004 * n ^ 10 -
8.5946393615396631e-006 * n ^ 11 -
7.0418841304671321e+002

I just calculated the polynomial regression. I'm tempted to see what other terrible method could be attempted.
Notably, I could save 3.3 points if the result was rounded. At this point, I don't think that matters.

3.2
Zero based solution:
7 & (37383146136 >> (i*3))

One based solution:
7 & (299065169088 >> (i*3))

I initially thought that the %7 operation would be counted as well and % being an expensive operation here, I tried to solve it without it.
I came to a result of 3.2 like this:
// Construction of the number
// Use 3 bits per entry and shift to correct place
long c = 0;
int[] nums = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
for (int i = nums.Length - 1; i >= 0; i--)
{
    c <<= 3;
    c += nums[i];
}
// c = 37383146136

// Actual challenge
for (int i = 0; i < 13; i++)
{
    Console.Write("{0} ",7 & 37383146136 >> i*3);
}

I'd be interested in optimizations using this approach (without %). Thanks.

This is cool, maybe this will help me some day) How do you think, maybe I should create separate question for whole formula minimization?

How about (0426415305230 >> (i*3)) & 7? You can see the output digits in reverse order.

@CJDennis: I think there are no octal numbers in C#.

I thought it was just C? I can't see any other reference to C#.

Python (3)
Since there are quite a few of these questions these days, I decided to make a program to automatically solve them in 3 (or 2) tokens. Here's the result for this challenge:
G:\Users\Synthetica\Anaconda\python.exe "C:/Users/Synthetica/PycharmProjects/PCCG/Atomic golfer.py"
Input sequence: 0 3 2 5 0 3 5 1 4 6 2 4
f = lambda n: (72997619651120 >> (n << 2)) & 15
f = lambda n: (0x426415305230L >> (n << 2)) & 15
f = lambda n: (0b10000100110010000010101001100000101001000110000 >> (n << 2)) & 15

Process finished with exit code 0

Proof that this works:
f = lambda n: (72997619651120 >> (n << 2)) & 15

for i in range(12):
   print i, f(i)

0 0
1 3
2 2
3 5
4 0
5 3
6 5
7 1
8 4
9 6
10 2
11 4

How does your solver consider the cost of operands?

@ThomasW. It doesn't, it'll always use a right shift, possibly a left shift (if the values aren't 1 bit) and an &.

authors: Дмитрий Абросимов


text:
Find a route between two Wikipedia articles
Introduction
Recently, I was skyping with a bunch of friends and we got bored and had nothing to do, so we "invented" a "game" (some people in the comments pointed out that this game is playable online and very popular, so we definetely didn't invent it, although I hadn't seen it before). The reason I put the word "game" in quotation marks is because it's not an actual computer game, but it's played on Wikipedia.
It's really easy to play: Someone chooses some Wikipedia article as the goal. Let's assume Code Golf for this example. All the players then have to start from a random article (by pressing Random Article in the sidebar or going to this URL) and have to get to the "goal" as quick as possible using only linked articles of the article you are currently at. Rules include:

The search function is not allowed (obviously)
You may only click links in the article's main text (specifically all text inside <div id="bodyContent">)
If your random page or any other page you encounter has no valid links (dead links, loops, etc) or no links at all you may roll again.

The challenge
Here's where you come in: unfortunately I'm pretty bad at this game, but I'm also a dirty cheater. So I want you to implement this bot for me. I'm also a programmer, so naturally my hard disk is full of stuff like code, libraries and such and I only have   a few bytes of memory to spare. Therefore this challenge is Code Golf, the answer with the least bytes wins.
Implementation Details:

Of course you don't have to implement an intelligent bot that knows connections between topics and automatically detects the optimal route. Brute forcing is more than enough for the purpose of this challenge
In the actual game, time counts. Your program shouldn't take longer than 1 hour to find the article (this is to avoid loopholes like random searchers that will "eventually" find the goal)
If no path to the goal can be found (e.g. dead links or a loop) you can choose what to do from the list below:

Quit (score remains the same)
Get another random article and try again and do nothing on loops (score -= 10)
Get another random article on a dead link or a loop (detect loops automatically) (score -= 50)
(By "score" I mean your byte count here)

Another 20 bonus bytes will be subtracted if you "trace" the route, so you print the title of every individual page you visit.
Standard network libraries may be used (to avoid loopholes like "I crafted my own network library which crawls wikipedia articles")

The only thing network-related your program should do is send a HTTP request to download a wikipedia page

If your program finds the page, it should quit, but somehow signalize that it finished (printing the character "f" or the title of the page is enough)
Standard loopholes are to be avoided

Have fun golfing!
(This is my first question here, so please point out obvious loopholes and caveats in the comments before exploiting them - thanks :D)

Welcome to PPCG! Unfortunately (in my experience) people prefer exploiting loopholes instead of pointing them out, even if you ask them nicely not to. If you want some feedback before posting your challenge on main, you can post it in the sandbox (see Featured on Meta in the sidebar).

For a fun way to play this online with other people: http://thewikigame.com/ :)

Interesting enough for a challenge, but not enough reason for me to flood a site with requests.

Thanks @m.buettner, I'll remember that when posting the next time.

@Doorknob lol, this game is obviously much more popular than I imagined ;)

@manatwork I'm fairly certain Wikipedia has sufficient bandwith to handle "attacks" like this

Not exactly a loophole but I would look out for people complaining that this is just a graph search question that doesn't bring many new ideas to the table. I however think its fine, this site needs more questions. (Though you definitely didn't invent this "game" :P.)

@Calvin'sHobbies Well it adds a little spice by bringing in the network factor and such in my opinion. I'm glad you like it though. Yeah, I definitely didn't invent it :D I added an annotation about that in the text.

@HackerCow Your question is quite interesting, you should post your questions in the sandbox before.

@HackerCow I like this question, just a few little things. You described what to do if you cant find the page. But what will happen if you reach the page? and should there be output displaying what pages were visited to achieve the destination page?

@TeunPronk When the page is reached, the program should quit, but somehow signal that it's done (e.g. printing a message). By score I mean the character count. So the actual character count gets reduced by the corresponding number. Good point with the output, I'll add a few things to the implementation details I guess ;)

This is basically http://codegolf.stackexchange.com/q/18665/194 + http://codegolf.stackexchange.com/q/26031/194

This could have been good as a koth challenge taking the average number of hops out of 50 runs with each bot. Would give more incentive to build a more intelligent bot.

Why is brute forcing okay but the script needs to do this in under an hour? Seems contradictory. Brute forcing will, almost by definition, cause the script to take a while, especially when we're looking for one Wikipedia article out of millions.

@eric_lagergren - on the contrary I'd expect that most articles would be resolved within a few page jumps - even brute force this could be as little as a few seconds to minutes.

@NPSF3000 I suppose. I mean, I could open like 30 threads and try each until one finds the correct url, but that seems like an easy way to get banned from Wikipedia for hammering their servers...

@eric_lagergren to be fair the OP should have created a duplicate of wikipedia (the data is freely available) and hosted it themselves.

@NPSF3000 Mhmm. The issue I'm currently running into is that finding a page like /wiki/United_states is millions of times easier than /wiki/Code_golf, simply because the former is referenced much more than the latter.

@eric_langergren That's easy 'USA -> Personal Computer -> Application Software -> Web Application -> Perl -> Code Golf'  Now, as you state linking from a random page to USA is going to be pretty easy in most cases.

@eric_lagergren like I wrote, I mainly set this rule to avoid trolls. It's not really that much of a hard limit (2 or 3 hours are okay too), it's just to make sure someone doesn't write a program that takes tens of thousands of years to finish.

@HackerCow ahhh gotcha.

Python 373 -> 303
It reads the Wikipedia destination from input() (user input) and should be in the format of /wiki/dest. So, something like /wiki/Code_golf or /wiki/United_States. It also uses one space for the indents and http://enwp.org instead of Wikipedia's full URL to save bytes.

-50 because if it finds a broken URL it gets a new random URL.
-20 because it prints the title of each URL visited (could change title -> URL, but title is cleaner and actually makes my source larger).

It hangs every once and a while, and I can't figure out why. Perhaps because of Wikipedia rate limits?
I found the Boston Red Sox Wikipedia page in 9 minutes 20 seconds, and the United States page in under 10 seconds, so it shouldn't take too long to find Code Golf...
from mechanize import*;from lxml.html import*;from random import*;a=Browser();a.set_handle_robots(0);i='http://enwp.org/Special:Random';t=input();d={};k=a.open
def f(o):
 if o!=i:d[o]=o
 if o in d:f(i)
 try:v=fromstring(k(o).read()).xpath('//div[@id="content"]//a/@href')
 except:f(i)
 print a.title()
 if t in v:k(t);print 'f';exit()
 else:f(choice(v)) if v else f(i)
f(i)

I don't know a lot of python, but this looks nice

Does it detect loops though? If it doesn't, that's 10 bonus points instead of 50

@HackerCow yeah it won't visit the same url twice except for the /wiki/Special:Random url. Consequently, after visiting many urls it'll eat up your entire RAM.

I'll just say this: from ... import*.

I might be mistaken, but are you even using mechanize?

if t in v:a.open(t);print'f';exit()

@TheRare oh yeah I had that but when I did that my script kept doing weird things like hanging a Lot more often so I abandoned t :/ it was very strange -- I'll try it again though

It should have no effect on the performance, so I guess you just were unlucky.

@DevanLoper oh shoot, misread your comment. Yes, I am. Originally I was using import mechanize as m and the assigning m.Browser() to a so when I call a.open() I'm in effect calling mechanize.Browser().open() now I'm just importing all of mechanize and get to skip the ... as m part.

@TheRare you're probably right. there's no real reason for it to affect my script like you said.  thanks! I'll edit my post tomorrow when I'm not replying from my phone

You can also use 1 space indents. Oh, else:f(choice(v))if v else f(i). And if I'm not mistaken, except:v=l(a.open(i).read()).xpath(r) -> except:f(i)