In some cases, often in physics, you have to sum graphs. Your challenge is to write, in a language of your choice, a program or function that takes multiple graphs as images, calculates all possible sums, and outputs the result.

Graphs

The graphs are images that contain a white (rgb(255, 255, 255)) background with a non-white pixel in each column. Examples:

example graph example graph example graph

The values of the script are represented as the Y positions of the colored pixels. The value at a certain X coordinate is equal to the Y position of the uppermost colored pixel in that column, with coordinates starting from 0 at the bottom left. There may or may not be additional colored pixels below those pixels for aesthetical reasons.

Task

Your task is to write, in a language of your choice, a program or function that takes multiple graphs as images, calculates all the possible 2^n - 1 sums, and outputs the result.

A sum of graphs is a graph where each column's value is equal to the sum of the values of the corresponding column in each of the input graphs.

The graphs will come in multiple colors. The result image must contain all possible sums of the graphs as other graphs, including the original graphs but excluding the zero sum.

The color of each sum is determined by the average of the colors of the graphs included, for example, graphs of colors rgb(255, 0, 255) and rgb(0, 255, 255) would produce a graph of rgb(128, 128, 255) (may also be rounded down).

The resulting image should be as high as required to fit all graphs. This means you may have to output an image larger than any of the inputs.

The order in which the resulting graphs are drawn to the resulting image does not matter, i.e. if result graphs overlap, you may choose which one is on top, but it has to be one of the graphs, not a combination of their colors.

You may assume that the input images are of equal width, that all columns of the images have at least one non-white pixel, and that the heights of the images (including output) are below 4096 pixels.

Example

Input A:

example graph a

Input B:

example graph b

Example output:

example graph sum

(In case someone is interested, I copy-pasted the data for these from random companies' stock charts. That was the first way I found to get realistic data as CSV.)

Rules

  • You may choose any bitmap image input file format.
  • You may choose any bitmap image output file format, which doesn't have to match the input.
  • You may use image processing libraries, however any functions to complete this task directly are banned.
  • Standard loopholes apply.
  • This is , so shortest code in bytes wins.

Graph generator script

Here is a Python 2 script that generates graphs. Input is given in lines, with the three first lines as the RGB color and the rest as data, terminated by EOF.

import PIL.Image as image
import sys

if len(sys.argv) < 2:
    sys.stderr.write("Usage: graphgen.py <outfile> [infile]")
    exit(1)
outfile = sys.argv[1]
if len(sys.argv) > 2:
    try:
        stream = open(sys.argv[2], "r")
        data = stream.read()
        stream.close()
    except IOError as err:
        if err.errno == 2:
            sys.stderr.write("File \"{0}\" not found".format(sys.argv[2]))
        else:
            sys.stderr.write("IO error {0}: {1}".format(err.errno, err.strerror))
        exit(1)
else:
    data = sys.stdin.read()

try:
    items = map(int, data.strip().split("\n"))
    red, green, blue = items[:3]
    items = items[3:]
    highest = max(items)
except (ValueError, TypeError, IndexError):
    sys.stderr.write("Invalid value(s) in input")

img = image.new("RGB", (len(items), highest + 1), (255, 255, 255))

prev = items[0]
img.putpixel((0, highest - items[0]), (red, green, blue))
for x, item in enumerate(items[1:]):
    img.putpixel((x + 1, highest - item), (red, green, blue))
    if item < prev:
        for i in range(item + 1, prev):
            img.putpixel((x, highest - i), (red, green, blue))
    else:
        for i in range(prev + 1, item):
            img.putpixel((x + 1, highest - i), (red, green, blue))
    prev = item

img.save(outfile, "png")
  • @MartinBüttner I'm currently making one for two graphs. I'm doing it by hand (no reference impl yet), so I don't know if I have the patience for 3. Also, the three I gave can't be summed since they are of different widths. – Pietu1998 Mar 13 '15 at 21:02
  • So if there are n input graphs, there will be 2^n - 1 lines in the output image? – Peter Taylor Mar 13 '15 at 21:06
  • @PeterTaylor Yes. – Pietu1998 Mar 13 '15 at 21:07
  • I take it the output doesn't actually need to contain any vertical lines? Only the top-most pixel in each column? – Martin Ender Mar 13 '15 at 22:25
  • @MartinBüttner That is correct, since that data can still be parsed as a graph as defined in the first section. – Pietu1998 Mar 13 '15 at 22:26
up vote 3 down vote accepted

MATLAB, 405

Call via: f('http://i.stack.imgur.com/ffCzR.png','http://i.stack.imgur.com/zHldg.png')

function f(varargin)
for k=1:nargin
i=im2double(imread(varargin{k}))
V(k,:)=size(i,1)-cellfun(@(V)find(any(V~=1,3),1),num2cell(i,[1,3]))
C(k,:)=i(find(any(i(:,1,:)~=1,3),1),1,:)
end
s=2^nargin-1
G=dec2bin(1:s)-'0'
C=bsxfun(@rdivide,G*C,sum(G,2))
V=G*V
m=max(V(:))
r=ones(m+1,size(V,2))
g=r
b=r
for i=1:s
M=bsxfun(@eq,(m:-1:0).',V(i,:))
r(M)=C(i,1)
g(M)=C(i,2)
b(M)=C(i,3)
end
imwrite(cat(3,r,g,b),'S.png')

Python, 422

Call from commandline python plotsum im1.png im2.png im3.png

import sys
from numpy import*
from scipy import misc as m
R=m.imread
r=range
a=array
N=sys.args[1:]
L=len(N)
P=[map(argmin,R(n,1).T)for n in N]               #converts image to list of heights, counting from the top
C=a([R(N[i])[P[i][0],0,:]for i in r(L)])         #finds and stores the colour
P=a([len(R(N[i]))-a(P[i])for i in r(L)])         #flips the numbers, measures actual heights from bottom
w=len(P[0])
h=max(sum(P,0))+1                                    #compute dimensions
G=ones((h,w,3))*255                                  #and make a white grid
for i in r(1,2**L):
 z=where(a(list(bin(i)[2:].zfill(L)))=='1');y=sum(P[z],0)    #sum the graphs
 for x in r(w):G[y[x],x,:]=average(C[z],0)                   #average the colours
m.imsave('S.png',G[::-1])                            #flip image vertically and save

Example output
enter image description here
Another example
enter image description here

That was a tricky one, high-level array operations and using arrays as indices helps a lot here. I dont expect to see solutions under 1000 bytes except in Mathematica and Matlab

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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