Paint Starry Night, objectively, in 1kB of code
Mathematica, score 14125.71333
"a.png"~Export~ConstantImage[{28,34,41}/95,{386,320}]
Saves this image:
to a.png.
Pyth (no built-in compression), score 4695.07 4656.03 4444.82
Pyth’s only image-related functionality is a builtin to write a matrix of RGB triples as an image file. So the crazy idea here is to train a small deep neural network on the (x, y) ↦ (r, g, b) function representing the image, and run it on the coordinates of each pixel.
The plan
- Write a custom backpropagation loop in C++.
- Curse at how slow it is.
- Learn Tensorflow.
- Build a new desktop with a sick GPU using Black Friday deals.
- Scour the literature for ways to compress neural networks, and do that.
- Scour the literature for ways to avoid overfitting neural networks, and do the opposite of that.
The current network is built from 45 sigmoid neurons, with each neuron connected to the x, y inputs and to every previous neuron, and the last three neurons interpreted as r, g, b. It’s trained using the Adam algorithm without batching. The parameters weighting the 1125 connections are quantized to a range of 93 possible values (except the constant terms, which have 932 possible values) using a variant of stochastic quantization, the primary variation being that we set the gradient for quantized parameters to zero.
The result
The code
1023 bytes, encoded with xxd (decode with xxd -r). I used the 2016-01-22 version of Pyth that was current when this challenge was released. You can run the code directly in Pyth, but Pyth in PyPy3 (pypy3 pyth starry.pyth) runs it nine times faster, in about 3 minutes. The output image is written to o.png.
00000000: 4b6a 4322 05d4 7bb1 06f8 6149 da66 28e3 KjC"..{...aI.f(.
00000010: 8d17 92de a833 9b70 f937 9fc6 a74e 544d .....3.p.7...NTM
00000020: 1388 e4e5 1d7e 9432 fe38 1313 3c34 0c54 .....~.2.8..<4.T
00000030: 89fe 553b 83a3 84bb 08c8 09fe 72be 3597 ..U;........r.5.
00000040: b799 34f8 8809 4868 feb8 acde 2e69 34e6 ..4...Hh.....i4.
00000050: 1c1a c49a 27f0 f06a 3b27 0564 178a 1718 ....'..j;'.d....
00000060: 1440 e658 e06a c46d aa81 ac3f c4b7 8262 [email protected]...?...b
00000070: 398a 39e3 c9b7 6f71 e2ab 37e0 7566 9997 9.9...oq..7.uf..
00000080: 54eb eb95 0076 0adf 103c f34c 0b4e e528 T....v...<.L.N.(
00000090: a2df 6b4a 7a02 011a 10a9 2cf0 2edc 9f6f ..kJz.....,....o
000000a0: 33f3 5c96 9e83 fadb a2fa 80fc 5179 3906 3.\.........Qy9.
000000b0: 9596 4960 8997 7225 edb1 9db5 435e fdd8 ..I`..r%....C^..
000000c0: 08a6 112f 32de c1a5 3db8 160f b729 649a .../2...=....)d.
000000d0: 51fa 08e8 dcfa 11e0 b763 61e6 02b3 5dbb Q........ca...].
000000e0: 6e64 be69 3939 b5b2 d196 5b85 7991 bda5 nd.i99....[.y...
000000f0: 087a f3c0 6b76 b1d0 bb29 f7a4 29a3 e21a .z..kv...)..)...
00000100: 3b1b 97ae 1d1b 1e0f f3c7 9759 2458 c2db ;..........Y$X..
00000110: 386f 5fbb a166 9f27 2910 a1b5 cfcc d8db 8o_..f.').......
00000120: afaf bdb4 573d efb1 399b e160 6acf e14b ....W=..9..`j..K
00000130: 4c6b 957a 245a 6f87 63c7 737d 6218 6ab2 Lk.z$Zo.c.s}b.j.
00000140: e388 a0b3 2007 1ddf b55c 7266 4333 f3a2 .... ....\rfC3..
00000150: d58f d80b a3a6 c6c1 d474 58f3 274b 6d32 .........tX.'Km2
00000160: 9d72 b674 7cc4 fdf6 6b86 fb45 1219 cc5c .r.t|...k..E...\
00000170: 7244 396d 1411 d734 a796 ff54 cf1f 119d rD9m...4...T....
00000180: 91af 5eab 9aad 4300 1dae d42e 13f8 62a1 ..^...C.......b.
00000190: a894 ab0b 9cb1 5ee2 bb63 1fff 3721 2328 ......^..c..7!#(
000001a0: 7609 34f5 fcfe f486 46e9 dfa8 9885 4dac v.4.....F.....M.
000001b0: f464 3666 e8b9 cd82 1159 8434 95e8 5901 .d6f.....Y.4..Y.
000001c0: f0f5 426c ef53 6c7e ad28 60f6 8dd8 edaa ..Bl.Sl~.(`.....
000001d0: 8784 a966 81b6 dc3a e0ea d5bf 7f15 683e ...f...:......h>
000001e0: 93f2 23ae 0845 c218 6bdc f47c 08e8 41c2 ..#..E..k..|..A.
000001f0: 950e f309 d1de 0b64 5868 924e 933e 7ab8 .......dXh.N.>z.
00000200: dab7 8efb b53a 5413 c64b 48e6 fc4d 26fe .....:T..KH..M&.
00000210: 594a 7d6b 2dd0 914e 6947 afa7 614d b605 YJ}k-..NiG..aM..
00000220: 8737 554e 31bc b21c 3673 76bf fb98 94f8 .7UN1...6sv.....
00000230: 1a7d 0030 3035 2ce6 c302 f6c2 5434 5f74 .}.005,.....T4_t
00000240: c692 349a a33e b327 425c 22e8 8735 37e1 ..4..>.'B\"..57.
00000250: 942a 2170 ef10 ff42 b629 e572 cd0f ca4f .*!p...B.).r...O
00000260: 5d52 247d 3e62 6d9a d71a 8b01 4826 d54b ]R$}>bm.....H&.K
00000270: f26f fe8e d33d efb5 30a8 54fb d50a 8f44 .o...=..0.T....D
00000280: a3ac 170a b9a0 e436 50d5 0589 6fda 674a .......6P...o.gJ
00000290: 26fb 5cf6 27ef 714e fe74 64fa d487 afea &.\.'.qN.td.....
000002a0: 09f7 e1f1 21b6 38eb 54cd c736 2afa d031 ....!.8.T..6*..1
000002b0: 853c 8890 8cc0 7fab 5f15 91d5 de6e 460f .<......_....nF.
000002c0: 4b95 6a4d 02e4 7824 1bbe ae36 5e6c 0acd K.jM..x$...6^l..
000002d0: 0603 b86c f9fd a299 480f 4123 627e 951f ...l....H.A#b~..
000002e0: a678 3510 912c 26a6 2efc f943 af96 53cd .x5..,&....C..S.
000002f0: 3f6c 435c cbae 832f 316c e90e 01e7 8fd6 ?lC\.../1l......
00000300: 3e6d d7b4 fffb cd4a 69c7 5f23 2fe7 bf52 >m.....Ji._#/..R
00000310: 3632 3990 17ed 045a b543 8b79 8231 bc9b 629....Z.C.y.1..
00000320: 4452 0f10 b342 3e41 6e70 187c 9cb2 7eb5 DR...B>Anp.|..~.
00000330: cdff 5c22 9e34 618f b372 8acf 4172 a220 ..\".4a..r..Ar.
00000340: 0136 3eff 2702 dc5d b946 076d e5fd 6045 .6>.'..].F.m..`E
00000350: 8465 661a 1c6e b6c8 595f 6091 daf2 103b .ef..n..Y_`....;
00000360: 23ab 343a 2e47 95cf 4218 7bf5 8a46 0a69 #.4:.G..B.{..F.i
00000370: dabb 4b8d 7f9b b0c1 23b1 c917 839c 358c ..K.....#.....5.
00000380: b33c de51 e41c e84d 12bf 8379 f4c5 65fa .<.Q...M...y..e.
00000390: 0b65 7fe7 e1a0 fb0e 30f4 a7d2 b323 3400 .e......0....#4.
000003a0: 15e8 8a48 5d42 9a70 3979 7bba abf5 4b80 ...H]B.p9y{...K.
000003b0: b239 4ceb d301 89f8 9f4d 5ce6 8caa 2a74 .9L......M\...*t
000003c0: ca1b 9d3f f934 0622 3933 2e77 6d6d 2b4a ...?.4."93.wmm+J
000003d0: 4b73 4d3e 332e 574a 615a 6332 3536 685e KsM>3.WJaZc256h^
000003e0: 3463 732a 4c2d 3436 2e29 4a5a 3138 3739 4cs*L-46.)JZ1879
000003f0: 5b32 3739 6b33 6429 3338 3620 3332 30 [279k3d)386 320
How it works
KjC"…"93
C"…" convert the long binary string to an integer in base 256
j 93 list its base 93 digits
K assign to K
.wmm+JKsM>3.WJaZc256h^4cs*L-46.)JZ1879[279k3d)386 320
m 320 map for d in [0, …, 319]:
m 386 map for k in [0, …, 385]
JK copy K to J
[279k3d) initialize value to [3*93, k, 3, d]
.WJ while J is nonempty, replace value with
*L Z map over value, multiplying by
.)J pop back of J
-46 subtract from 46
s sum
c 1879 divide by 1879
^4 exponentiate with base 4
h add 1
c256 256 divided by that
aZ append to value
>3 last three elements of the final value
sM floor to integers
.w write that matrix of RGB triples as image o.png
Training
During my final training run, I used a much slower quantization schedule and did some interactive fiddling with that and the learning rate, but the code I used was roughly as follows.
from __future__ import division, print_function
import sys
import numpy as np
import tensorflow as tf
NEURONS, SCALE_BASE, SCALE_DIV, BASE, MID = 48, 8, 3364, 111, 55
def idx(n):
return n * (n - 1) // 2 - 3
WEIGHTS = idx(NEURONS)
SCALE = SCALE_DIV / np.log(SCALE_BASE)
W_MIN, W_MAX = -MID, BASE - 1 - MID
sess = tf.Session()
with open('ORIGINAL.png', 'rb') as f:
img = sess.run(tf.image.decode_image(f.read(), channels=3))
y_grid, x_grid = np.mgrid[0:img.shape[0], 0:img.shape[1]]
x = tf.constant(x_grid.reshape([-1]).astype(np.float32))
y = tf.constant(y_grid.reshape([-1]).astype(np.float32))
color_ = tf.constant(img.reshape([-1, 3]).astype(np.float32))
w_real = tf.Variable(
np.random.uniform(-16, 16, [WEIGHTS]).astype(np.float32),
constraint=lambda w: tf.clip_by_value(w, W_MIN, W_MAX))
quantization = tf.placeholder(tf.float32, shape=[])
w_int = tf.round(w_real)
qrate = 1 / (tf.abs(w_real - w_int) + 1e-6)
qscale = 0
for _ in range(16):
v = tf.exp(-qscale * qrate)
qscale -= ((1 - quantization) * WEIGHTS - tf.reduce_sum(v)) / \
tf.tensordot(qrate, v, 1)
unquantized = tf.distributions.Bernoulli(
probs=tf.exp(-qscale * qrate), dtype=tf.bool).sample()
num_unquantized = tf.reduce_sum(tf.cast(unquantized, tf.int64))
w = tf.where(unquantized, w_real, w_int)
a = tf.stack([tf.ones_like(x) * 256, x, y], 1)
for n in range(3, NEURONS):
a = tf.concat([a, 256 * tf.sigmoid(
tf.einsum('in,n->i;', a, w[idx(n):idx(n + 1)]) / SCALE)[:, None]], 1)
color = a[:, -3:]
err = tf.reduce_sum(tf.square((color - 0.5 - color_) / 255))
train_step = tf.train.AdamOptimizer(0.01).minimize(err, var_list=[w_real])
sess.run(tf.global_variables_initializer())
count = 0
quantization_val = 0
best_err = float("inf")
while True:
num_unquantized_val, err_val, w_val, _ = sess.run(
[num_unquantized, err, w, train_step],
{quantization: quantization_val})
if num_unquantized_val == 0 and err_val < best_err:
print(end='\r\x1b[K', file=sys.stderr)
sys.stderr.flush()
print(
'weights', list(w_val.astype(np.int64)),
'count', count, 'err', err_val)
best_err = err_val
count += 1
print(
'\r\x1b[Kcount', count, 'err', err_val,
'unquantized', num_unquantized_val, end='', file=sys.stderr)
sys.stderr.flush()
quantization_val = (1 - 1e-4) * quantization_val + 1e-4
Visualization
This picture shows the activations of all 45 neurons as a function of the x, y coordinates. Click to enlarge.
Java, 7399.80678201
This reminded me of a project I had in my numerical computations class a few semesters back, which was to draw a silhouette of Mount Everest using polynomial interpolation. That was done in MATLAB, but I'm not very fond of MATLAB, so I decided to work in Java. The basic idea behind it is that I chose "smart" points (read here as "random") for the polynomial interpolation. With the few bytes I had left, I created a way for the stars to be drawn, which happens before the drawing of the mountain. It may be possible to condense the code and add another polynomial for the bottom to help better the score.
Edit: I've made added and changed some of the polynomials and added all of the stars. My previous score was a 9807.7168935, so as you can see it is a very big improvement. Unfortunately the code took a hit in its readability because I had to squeeze out the last few bytes to get all of the stars, and give them groups.
import java.awt.image.*;
public class Y{public static void main(String[]a)throws Exception{
int w=386;int[]s={5819,18,5530,9,8644,7,11041,16,21698,14,22354,40/**/,4326,4,29222,14,40262,9,56360,8,59484,12,65748,24};
double[][]p={{-1},{88},{85,0.284,-0.0064,2.028e-5},{128,0.18},{180,0.674,-0.00473,6.65e-6},{240,-0.181},{272,-0.1167},{273,0.075},{3270,-95.57,0.7},{854,-9.83,0.0381}};
int[]c={-12561790,-11439717,-10981487,-11836288,-9600372,-13088667,-13287091,-13354436,-14275540,-14736605};
int o=p.length;BufferedImage b=new BufferedImage(w,320,1);
int i=0;for(;i<o;i++)
{if(i==o-2)for(int j=0;j<s.length;j+=2)for(int l=0;l<w*320;l++)if((l%w-s[j]%w)*(l%w-s[j]%w)+(l/w-s[j]/w)*(l/w-s[j]/w)<s[j+1]*s[j+1])
b.setRGB(l%w, l/w,j<s.length/2+1?j==10?-5788556:-8944525:-7036782);
for(int l=0;l<w*320;l++){int m=0;for(int y=0;y<p[i].length;y++)m+=Math.pow(l%w,y)*p[i][y];if(l/w>m)b.setRGB(l%w,l/w,c[i]);}
}
javax.imageio.ImageIO.write(b,"png",new java.io.File("o.png"));
}
}
9807.7168935 points:
7399.80678201 points:
