# [Pyth](https://github.com/isaacg1/pyth) (no built-in compression), score 4695.07
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
1. Write a custom backpropagation loop in C++.
2. Curse at how slow it is.
3. Learn Tensorflow.
4. Build a new desktop with a sick GPU using Black Friday deals.
5. Scour the literature for ways to compress neural networks, and do that.
6. 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](https://arxiv.org/abs/1412.6980) algorithm without batching. The parameters weighting the 1125 connections are quantized to a range of 111 possible values using a variant of [stochastic quantization](https://arxiv.org/abs/1708.01001) (the primary variation being that we set the gradient for quantized parameters to zero).
### The result
[![output][1]][1]
### The code
1020 bytes, encoded with `xxd` (decode with `xxd -r`). I used the [2016-01-22 version of Pyth](https://github.com/isaacg1/pyth/commit/8752181ac426d9d4e224891fbb4a8021051e33bb) that was current when this challenge was released. You can run the code directly in Pyth, but Pyth in [PyPy3](https://pypy.org/download.html) (`pypy3 pyth starry.pyth`) runs it nine times faster, in about 3 minutes. The output image is written to `o.png`.
00000000: 4b6a 4322 0bf9 084a 6143 7853 022b 4d7d KjC"...JaCxS.+M}
00000010: e23f 42f4 5c22 09df 7337 52d9 dcbf 9567 .?B.\"..s7R....g
00000020: d5be b388 1493 da66 5398 2579 a9fd eb34 .......fS.%y...4
00000030: 6472 5e97 0519 336d ab36 30cd 8a83 165c dr^...3m.60....\
00000040: 72f2 bc43 d8d4 951e 51c1 57ba 3f80 3a12 r..C....Q.W.?.:.
00000050: eb2e 1294 7361 a657 b575 a67b 1644 b31c ....sa.W.u.{.D..
00000060: 79dc 553c a78a 7e42 2d14 2d60 e2db 11e3 y.U<..~B-.-`....
00000070: fcb6 6fd8 4a44 db53 4662 1841 9536 4fd0 ..o.JD.SFb.A.6O.
00000080: cfe9 3cbd 98a2 b8b2 7034 3258 0ee4 a4e7 ..<.....p42X....
00000090: 5d27 4c24 839f 8070 1d8c 7f69 0c3c 177d ]'L$...p...i.<.}
000000a0: b678 a1d0 de97 e5d0 b008 9bb6 ae17 5172 .x............Qr
000000b0: 5e6b f4fd 9142 b2f2 a83c d594 5999 d424 ^k...B...<..Y..$
000000c0: 9d04 d45c 42aa ff6f 7869 24db c691 bab9 ...\B..oxi$.....
000000d0: b235 c26d 87b6 8a2e 5e78 980a 64b8 e3aa .5.m....^x..d...
000000e0: db46 143c feae 94fc 928e 1e58 da07 d441 .F.<.......X...A
000000f0: d926 459a e2b3 fc27 ddef cc1a c576 faee .&E....'.....v..
00000100: 0397 160c ba40 966d c0de 8e96 2a66 859a [email protected]....*f..
00000110: 82cb 2690 1633 27bb e3bd 41b6 597d d36e ..&..3'...A.Y}.n
00000120: 570b 1038 43b3 7387 ded8 ca58 a3c0 6f6c W..8C.s....X..ol
00000130: 447b 2565 c9e2 fff7 7064 bcba 36e4 9340 D{%e....pd..6..@
00000140: a16e 52b4 b4ed a721 fe9e 7693 d679 b8f3 .nR....!..v..y..
00000150: 3739 4b0a 4e1f 5a6e a5e1 f7e5 5c20 0942 79K.N.Zn....\ .B
00000160: 3d3c c000 962a 2106 7b79 9c95 44ea c120 =<...*!.{y..D..
00000170: 9310 2b7c beef 40ee 4ccc 5fb2 b4f9 a2b8 ..+|[email protected]._.....
00000180: 8fcb 3029 bb0b 7723 ab94 4ea7 ecf6 02b1 ..0)..w#..N.....
00000190: 3e95 bced b677 5888 172c b7e4 25c0 256e >....wX..,..%.%n
000001a0: 13d2 c837 f4f6 1b0f ed78 5c72 abca 1413 ...7.....x\r....
000001b0: c490 b628 7753 2cd3 5b68 df63 e08f 57f4 ...(wS,.[h.c..W.
000001c0: b172 da04 18dc 9c96 620e 342c bd23 f24b .r......b.4,.#.K
000001d0: 2c1c 95ec efba 5df4 8a18 433c 70a5 ac07 ,.....]...C<p...
000001e0: e082 97f2 3a09 d33e e002 2076 c764 15e4 ....:..>.. v.d..
000001f0: 5cfa 427e 40ea 89b7 9cd9 afda d121 6440 \.B~@........!d@
00000200: 1e54 2700 3e60 3b16 ea84 07cb b4b3 027c .T'.>`;........|
00000210: f3b8 0f54 d759 563c 7ef2 b4df 4deb 476f ...T.YV<~...M.Go
00000220: 3731 5839 9058 fa98 7a14 f511 6b55 4a90 71X9.X..z...kUJ.
00000230: d60f 2f65 4875 a618 4bac 3c5d b9b7 359d ../eHu..K.<]..5.
00000240: dee5 3c71 d13d 9129 dab3 4bed e89e 3127 ..<q.=.)..K...1'
00000250: 975c 22bf fd41 85a8 52a1 13de e1fb 6679 .\"..A..R.....fy
00000260: 55af 1431 ae2f 6230 ec4e 560e 90e9 939b U..1./b0.NV.....
00000270: a4ef 5b84 0cb3 8dd4 fab0 d5c0 23eb d687 ..[.........#...
00000280: 733d ac2c edad e8fb cce6 6960 6365 ac1d s=.,......i`ce..
00000290: 934e de39 d7b6 08ba a321 3c83 3104 892f .N.9.....!<.1../
000002a0: 1578 ff04 06c6 b4b0 579d e986 592a 691b .x......W...Y*i.
000002b0: 4f71 d60b 47f3 ab04 53d2 9586 9772 3150 Oq..G...S....r1P
000002c0: 5883 52bb 3079 1588 fd89 d767 f74b a73a X.R.0y.....g.K.:
000002d0: 8066 5de5 bafd 3d1b c862 d72d 2992 ddd5 .f]...=..b.-)...
000002e0: 1483 e090 dce0 1770 4146 2b60 fcc2 e526 .......pAF+`...&
000002f0: 5449 8807 750c 9148 f53c adf3 ce23 8328 TI..u..H.<...#.(
00000300: 39b2 1cd2 ac64 6432 74b0 3198 b072 d8b0 9....dd2t.1..r..
00000310: 9405 2bb4 7c95 d2da 7c9d f126 f693 3ef9 ..+.|...|..&..>.
00000320: 5169 5ab1 cefa 56b6 95c3 45b0 c6b9 4567 QiZ...V...E...Eg
00000330: 3caf 16a7 125f 4606 5100 99ec a354 0abc <...._F.Q....T..
00000340: eaaf 2797 5816 af89 b309 379a 4806 638c ..'.X.....7.H.c.
00000350: 0c78 b56a 763e f11f 67e2 a6cb 0008 a9d7 .x.jv>..g.......
00000360: 7443 03fd f809 ae7d 38c2 fe36 fdd3 8842 tC.....}8..6...B
00000370: bd6e f714 0426 550e f781 9d16 2e05 f884 .n...&U.........
00000380: bb6c dba6 d144 d69b a94f d3bf da27 5d70 .l...D...O...']p
00000390: a356 dfb0 2715 b5ba 28af 5f0b 85ff 8aff .V..'...(._.....
000003a0: f0a9 dd2c e1c0 b13a 8337 8f17 c5fc bf43 ...,...:.7.....C
000003b0: f306 30e1 eb15 4d4e 9400 07fd 0694 acac ..0...MN........
000003c0: 3acc 0431 2231 3131 2e77 6d6d 2b4a 4b73 :..1"111.wmm+JKs
000003d0: 4d3e 332e 574a 615a 6332 3536 685e 3863 M>3.WJaZc256h^8c
000003e0: 732a 4c2d 3535 2e29 4a5a 3333 3634 5b32 s*L-55.)JZ3364[2
000003f0: 3536 6b64 2933 3836 2033 3230 56kd)386 320
### How it works
KjC"…"111
C"…" convert the long binary string to an integer in base 256
j 111 list its base 111 digits
K assign to K
.wmm+JKsM>3.WJaZc256h^8cs*L-55.)JZ3364[256kd)386 320
m 320 map for d in [0, …, 319]:
m 386 map for k in [0, …, 385]
JK copy K to J
[256kd) initialize value to [256, k, d]
.WJ while J is nonempty, replace value with
*L Z map over value, multiplying by
.)J pop back of J
-55 subtract from 55
s sum
c 3364 divide by 3364
^8 exponentiate with base 8
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.
<!-- language: lang-python -->
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.
[![neuron activations][2]][2]
[1]: https://i.sstatic.net/pkRWC.png
[2]: https://i.sstatic.net/jfjCs.png