# How predictable is popular music?

The McGill Billboard Project annotates various audio features of songs from a random sample of the Billboard charts. I scraped this data to produce the following file of chord progressions:

chords.txt

Write the shortest code that outputs the above file (or its contents).

Edit: Here's a quick description of the notation to get you started:

• N denotes no chord.

• A:min denotes the A minor triad chord.

• C#:sus4(b7,9) and other spicy chords are completely described here.

• That's .... a really long list. Does the output have to be in order? – Jo King Jan 24 '20 at 4:47
• Could you include a brief description of the chord format? Understanding what C#:sus4(b7,9) exactly means may help to compress it. – Arnauld Jan 24 '20 at 7:42
• @RGS You can do that. As per the rules described in this meta post, your score would be your_code_size + 802213 + 1. – Arnauld Jan 24 '20 at 8:05
• @HymnsForDisco - Yes, compression/decompression libraries are allowed, but presumably, the best compressions will leverage insights from music theory. – Dustin G. Mixon Jan 24 '20 at 9:53
• @DustinG.Mixon I'm hugely interested, being a musician, but quite discouraged by the 125000+ lines of data, I have a work too :D is there a version with songs titles just for info? Another interesting part would be the relative aspect of notes, as the same progression can be transposed, but that's another matter, the way notes are written make this a bit difficult – Kaddath Jan 24 '20 at 10:14

# Java (JDK), 295709 47044 (gzipped file) + 943 (code) + 1 (file) + 67 (imports) = 48055 bytes

Examining the file manually (with some help from notepad++), I found that there were 976 unique entries in the file, formed of 36 unique characters (plus newlines):

#(),/123456789:ABCDEFGNXabdghijmnsu

I then looked for common patterns, and created a dictionary as follows (key = value):

:maj = ¬
:min = 
\r\nA = "
\r\nB = £
\r\nC = $\r\nD = % \r\nE = ^ \r\nF = & \r\nG = * \r\nN = _ \r\nX = - :sus = + :hdim = = :dim = [ (9) = } (#9) = ] :7 = { :5 = ~ :aug = ; #11 = @ b7 = ' maj7 = < b13 = > :11 = ? (11) = \ b:9 = Z ¬^¬ = H ¬%¬ = I ¬$¬ = J
¬"¬ = K
£b¬ = L
¬*¬ = M
b¬"b = O
¬&¬ = P
b¬^b = Q
+4(', = R
¬£ = S
+4(') = T
%b¬ = U
££ = V
7%7 = W
7" = Y
"b{] = c
*7 = e
:13^b = f
7$= k % = l ^ = o " = p b7^ = q b{% = r cc = t oo = v &#~ = w __ = x YY = y &#¬ = z I then find-and-replace using those items in order: ()->{String s = "A LONG STRING THAT I CAN'T PASTE HERE - SEE TIO LINK"; String[] d=new String[]{"&#¬","z","YY","y","__","x","&#~","w","oo","v","cc","t","b{%","r","b7^","q","\"","p","^","o","%","l","7$","k",":13^b","f","*7","e","\"b{]","c","7\"","Y","7%7","W","££","V","%b¬","U","+4(')","T","¬£","S","+4(',","R","b¬^b","Q","¬&¬","P","b¬\"b","O","¬*¬","M","£b¬","L","¬\"¬","K","¬$¬","J","¬%¬","I","¬^¬","H","b:9","Z","(11)","\\",":11","?","b13",">","maj7","<","b7","'","#11","@",":aug",";",":5","~",":7","{","(#9)","]","(9)","}",":dim","[",":hdim","=",":sus","+","\r\nX","-","\r\nN","_","\r\nG","*","\r\nF","&","\r\nE","^","\r\nD","%","\r\nC","$","\r\nB","£","\r\nA","\"",":min","",":maj","¬"};
for (int i=0;i<d.length;i+=2){s=s.replace(d[i+1],d[i]);}return s;}

TIO (sort of).

EDIT

Using the GZIPped version of the string in a file "f" (size 45708 bytes), the code can then be as follows:

• FYI - If you zip your string, it's only 47,044 bytes, so I think this would beat my answer. – Dustin G. Mixon Feb 11 '20 at 15:41

# Python 3, 969 + 36208 (size of data file) = 37177 bytes

A mix of encoding and traditional compression. I store each of the roots (the "letters") and index into an array to find them, then, if it's not N, X or the empty string (which don't have a "chord type" (combination of the quality and other stuff tacked on the end) and are immediately followed by a newline), I use the next byte to index a table of the "chord types".

The data file (named "b") is available on my GitHub.

import base64,zlib,io
while 1:

Edit: I decided not to be lazy after all and go Google correct music terms.

• It doesn't seem to work: IndexError: index out of range with the provided file – G B Feb 12 '20 at 10:53
• @GB I use the error out at the end to exit the loop – famous1622 Feb 12 '20 at 14:32
• Ok, so I assume the output file is smaller than expected because of CR/LF. I can't verify the original because I have no access to dropbox from behind a company proxy. – G B Feb 12 '20 at 14:35
• @GB yeah, it should be because of the CR/LF, is the end Cb:maj(9) repeated and a final N? – famous1622 Feb 12 '20 at 14:37

# Python 3, 23 + 802213 (size of file we want to reproduce) + 1

This function takes as argument the file we want to reproduce and then prints it xD

• Just to be clear, the purpose of my comment was actually to dissuade you from doing so. :-) – Arnauld Jan 24 '20 at 8:27
• @Arnauld it is just a basic benchmark while you guys are trying to figure out the best encodings :) – RGS Jan 24 '20 at 8:29
• Worst Golf Score Ever :P – Kaddath Jan 24 '20 at 9:10
• @Kaddath Just look up some Lenguage/Unary answers, those score a lot worse. ;) This ~62 trillion bytes answer of mine is actually rather short for Lenguage. Usually it's more like this 5.71728886e+3431 bytes answer, haha. ;p – Kevin Cruijssen Jan 24 '20 at 13:56
• I don't think this counts as a serious contender. – Grimmy Jan 24 '20 at 18:03

# MATLAB, 55935 = 10 + 55924 + 1

Compress the text file as a 55924-byte zip file c and then run the code

unzip('c')

We add a byte to the score to account for the extra file.

## Python 3: 93943 = 91,752 + 1990 + 1

This is my messy attempt at a compression. Sadly still worse than simply zipping the file though XD.

The information density of the file is not as great as it seems and there were several observable redundancies. Because of that I have doubts that there is a reasonable way to predict the data. I am prepared to be wrong though :-). The code by itself is not golfed that much, since the main portion of the cost is the size of the compressed files. The decompressor is only 1990 bytes long. The compression itself is done by Two separate huffman trees, implied ":" between them and two one-bit streams that act as a guides. Also there are few simple substitutions in place.

1. First huffman tree codes the first letter
2. Second huffman tree codes the portion that follows the ":"
3. First bit file (a) codes whether the line before the ":" consists of 0-1 or 2 characters
4. Second bit file (u) codes whether the second character before : is "b" or "#"

Lastly, all the files are compressed via zip since on my work computer we don't have anything else. Might try other compressors later on. zip-input This archive has to be in programs working directory.

The code itself is tied tightly to the file. It does not cover full format specifications listed by the author of the question. (Also, I have hard-coded the input file size into the decoder - after I missed the proper termination one times too many.) There is definitely a room for improvements - for example few more substitutions tied to the numbers in brackets.

There might be a missing trailing newline in the output, that I somehow keep missing while trying to debug.

Huffman tree generator:

import heapq as h
import numpy as np
from bitarray import bitarray

class List:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.leftSon = None
self.rightSon = None

def __lt__(self, other):
return self.freq < other.freq

def check(self,arr,  prefix):
if self.char is not None:
arr.append((self.char, prefix))
else:
self.leftSon.check(arr, prefix + "0")
self.rightSon.check(arr, prefix + "1")

def encode(self):
if self.char is None:
toRet = "0"
toRet += self.leftSon.encode()
toRet += self.rightSon.encode()
else:
toRet = "1" + np.binary_repr(ord(self.char), 8)

class HuffmanTree:
def __init__(self, inputList):
a = []
for x in inputList:
h.heappush(a, List(x[0], x[1]))
while len(a) > 1:
first = h.heappop(a)
second = h.heappop(a)
new = List(None, first.freq + second.freq)
new.leftSon = first
new.rightSon = second
h.heappush(a, new)
self.root = a[0]
self.encodeArray = []
self.root.check(self.encodeArray, "")
encodeDict = {}
for x in self.encodeArray:
encodeDict[x[0]] = x[1]
self.encodeDict = encodeDict
print(self.encodeArray)

def encodeSelf(self):
x = bitarray()
for b in bits:
if b == "0":
x.append(0b0)
else:
x.append(0b1)
return x

The code to generate the support files:

import huffman
from bitarray import bitarray

a = ""
with open("chords.txt") as chr:

def getCounts(l):
counts = {}
for x in l:
if x in counts.keys():
counts[x] += 1
else:
counts[x] = 1
res = []
for x in counts.keys():
res.append((x, counts[x]))
return res

def stringToBits(string):
ret = bitarray()
for x in string:
if x =="0":
ret.append(0b0)
else:
ret.append(0b1)
return ret

lines = a.split("\n")
firstPart = []
secondPart = []
for i in lines:
a = i.split(":")
firstPart.append(a[0])
if len(a) > 1:
secondPart.append(a[1] + "\n")

###First part
Afile = ""
huffFile = ""
sharpFile = ""

firstPartChars = ""
fChar = []
sChar = []
for x in firstPart:
firstPartChars += x
if len(x) == 0:
fChar.append("\n")
Afile += "0"
else:
fChar.append(x[0])
if len(x) == 1:
Afile += "0"
if len(x) == 2:
Afile += "1"
sChar.append(x[1])

print([x for x in set(fChar)])
print([x for x in set(sChar)])

fCharCount = getCounts(fChar)
sCharCount = getCounts(sChar)
firstHuff = huffman.HuffmanTree(fCharCount)
for char in fChar:
code = firstHuff.encodeDict[char]
huffFile += code

for char in sChar:
if char == "b":
sharpFile += "0"
elif char == "#":
sharpFile += "1"
else:
raise Exception("error in sharp file")

#######
#####Second part
sPartFile = ""
subs = {}
subs["maj"] = "~"
subs["min"] = "&"
subs["sus"] = "^"
subs["aug"] = "%"
subs["dim"] = "$" subs["hdi"] = "@" spPart = [] secSubPart = "" for x in secondPart: c = x.replace("maj", "~").replace("min", "&").replace("sus", "^").replace("aug", "%")\ .replace("dim", "$").replace("hdim", "@")
spPart.append(c)
secSubPart += c
secPartCounts = getCounts(secSubPart)
secondHuff = huffman.HuffmanTree(secPartCounts)
for x in secSubPart:
sPartFile += secondHuff.encodeDict[x]

aBits = stringToBits(Afile)
huffBits = stringToBits(huffFile)
sharpBits = stringToBits(sharpFile)
sPartBits = stringToBits(sPartFile)
print("test")
with open("a", "wb") as t:
aBits.tofile(t)
with open("h", "wb") as t:
huffBits.tofile(t)
with open("u", "wb") as t:
sharpBits.tofile(t)
with open("f", "wb") as t:
sPartBits.tofile(t)

with open("i", "wb") as t:
a = firstHuff.encodeSelf()
a.tofile(t)
with open("j", "wb") as t:
b = secondHuff.encodeSelf()
b.tofile(t)

Finally the code itself:

from bitarray import bitarray as b
import zipfile
with zipfile.ZipFile("h.zip", 'r') as z:
z.extractall(".")

class N:
def __init__(s):
s.c = None
s.l = None
s.r = None
def i(s):
return s.l == None
def d(s, r):
if s.i():
return s.c
else:
if r.b() == 0:
return s.l.d(r)
else:
return s.r.d(r)
class R:
def __init__(s, bits):
s.d = bits
s.i = 0

def b(s):
t = s.d[s.i]
s.i += 1
return t

def B(s):
toRet = s.d[s.i:s.i + 8]
s.i += 8

def rn(r):
if r.b() == 1:
n = N()
n.c = r.B().tostring()
else:
left = rn(r)
right = rn(r)
n = N()
n.l = left
n.r = right
return n

def bff(i):
with open(i, "rb") as f:
c = b()
c.fromfile(f)
return c

c = bff(a)
r = R(c)
n = rn(r)
return n

fp = R(bff("h"))
sp = R(bff("f"))
af = R(bff("a"))
bp = R(bff("u"))

ft = ""
test = open("test", "w")
i=0
while i < 125784:
i += 1
tp = ""
n = "\n"
s = "#"
b = "b"
t = fh.d(fp)
spr = True
if af.b() == 0:
if t == n:
tp += t
spr = False
elif t == "N" or t == "X":
tp += t + n
spr = False
else:
tp += t + ":"
else:
tp += t
if bp.b() == 1:
tp += s + ":"
else:
tp += b + ":"
if spr:
x = sh.d(sp)
while x != n:
tp += x
x = sh.d(sp)

tp += x
tp = tp.replace("~", "maj").replace("&", "min").replace("^", "sus")\
.replace("%", "aug").replace("\$", "dim").replace("@", "hdim")
ft += tp
print(ft)

# bash, 802213 + 5 + 1 = 802219 bytes

cat<b

With a file named b containing the contents of chords.txt.