QR Codes... and all that Jazz!

18

8

This is going to be relatively challenging code-golf challenge.

Input: Any URL, must have the protocol attached, e.g. http://codegolf.stackexchange.com (which will be our test case)

Output: A generated QR Code that represents this URL, which, when scanned by a smart device will take you to that URL on the smart device's browser.

Rules for this Code-Golf

  1. As usual, smallest code wins.
  2. No external web resources, libraries or plugins to generate the code for you. Your code must calculate the QR code image.
  3. Output can be presented by an image, generated by HTML5/CSS3, or even using appropriate Unicode blocks, or if your platform's ASCII has it available, through ASCII characters that can form the QR code (this last one is directed at Commodore 64 Basic, Amiga QBasic, Amstrad Basic, etc users), but it must generate a QR code output such that I can scan the code.
  4. Entries of the code must be followed with the generated output, either by a screen shot of the output after executing your code, or with a link showing the output (whichever suits the situation best)
  5. You are to test your code with the URL "http://codegolf.stackexchange.com", and report the output in accordance to Rules 3 to 4.
  6. You are to also test your code with a URL of your choice, and report the output in accordance to Rules 3 to 4.

References:

1) http://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders

2) http://www.pclviewer.com/rs2/calculator.html

3) http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

4) http://en.wikipedia.org/wiki/QR_code

5) http://www.qrstuff.com/ for inspiration... ;)

WallyWest

Posted 2014-02-03T23:30:30.330

Reputation: 6 949

Mathematica: 20B ;) #~BarcodeImage~"QR"& – hYPotenuser – 2016-03-05T12:07:20.063

@hYPotenuser This is almost the same as a previously deleted answer, deleted because it was a built-in function within the language. – WallyWest – 2016-03-05T12:18:41.940

4Infinite recursion at rule 5. – user12205 – 2014-02-04T00:50:16.557

@ace Well spotted... this has been fixed – WallyWest – 2014-02-04T05:17:54.183

1After reading some documentation, I think "relatively challenging" is an understatement. – Danny – 2014-02-04T17:24:46.143

Can we get a clarification as to what "your code must calculate the QR code image" means? I'm taking it to mean that we must do the two major points in the submitted code: 1) RS encoding, and 2) module layout. – Nick T – 2014-02-04T20:58:03.723

rule 3: so is ascii art printed from a terminal fine, or does it have to go into an actual image file? – None – 2014-05-26T16:52:20.177

also, which of the QR code specifications do we use? how much error correction? – None – 2014-05-26T18:05:36.287

@professorfish ASCII art... hmmm... If you can pull it off then by all means try it... Also the QR specification to be used is whatever works to your advantage... This is code golf, after all... – WallyWest – 2014-05-27T06:47:12.773

Answers

17

Python 3: 974 chars [nb]

Further beat with the ugly stick, see notebook on GH-Gist. Python 3 has built-in ASCII-85 encoding, which helps with the zipped saus. 3's more advanced built-in compression algorithms (LZMA) don't seem to work well with such small things.

Zipping is very fickle about changing characters around, was almost tempted to write something that would randomly try different 1-letter names for variables to minimize the zipped size.

Python 2: 1420 1356 1085 1077 characters

enter image description here

I read the first argument passed when called, which can be a string up to 106-ish characters long. The output is always a version 5-L QR code and mask 4 which means it's 37x37 modules large and can only handle ~5% damage.

The program's only dependencies are numpy (array manipulations) and matplotlib (display only); all Reed-Solomon encoding, data packing, and module layout is handled within the provided code. For RS, I basically robbed the Wikiversity functions...it's still kind of a black-box for me. Learned a ton about QR in any event.

Here's the code before I beat it with the ugly stick:

import sys
import numpy as np
import matplotlib.pyplot as plt
# version 5-L ! = 108 data code words (bytes), 106 after metadata/packing

### RS code stolen from https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#RS_generator_polynomial
gf_exp = [1] + [0] * 511
gf_log = [0] * 256
x = 1
for i in range(1,255):
    x <<= 1
    if x & 0x100:
        x ^= 0x11d
    gf_exp[i] = x
    gf_log[x] = i
for i in range(255,512):
    gf_exp[i] = gf_exp[i-255]

def gf_mul(x,y):
    if x==0 or y==0:
        return 0
    return gf_exp[gf_log[x] + gf_log[y]]

def main():
    s = sys.argv[1]

    version = 5
    mode = 4 # byte mode
    dim = 17 + 4 * version
    datamatrix = 0.5 * np.ones((dim, dim))
    nsym = 26

    # PACK
    msg = [mode * 16, len(s) * 16] + [ord(c) << 4 for c in s]
    for i in range(1, len(msg)):
        msg[i-1] += msg[i] // 256
        msg[i] = msg[i] % 256

    pad = [236, 17]
    msg = (msg + pad * 54)[:108]

    # MAGIC (encoding)
    gen = [1]
    for i in range(0, nsym):
        q = [1, gf_exp[i]]
        r = [0] * (len(gen)+len(q)-1)
        for j in range(0, len(q)):
            for i in range(0, len(gen)):
                r[i+j] ^= gf_mul(gen[i], q[j])
        gen = r
    msg_enc = [0] * (len(msg) + nsym)
    for i in range(0, len(msg)):
        msg_enc[i] = msg[i]
    for i in range(0, len(msg)):
        coef = msg_enc[i]
        if coef != 0:
            for j in range(0, len(gen)):
                msg_enc[i+j] ^= gf_mul(gen[j], coef)
    for i in range(0, len(msg)):
        msg_enc[i] = msg[i]


    # PATTERN
    # position marks
    for _ in range(3):
        datamatrix = np.rot90(datamatrix)
        for i in range(4):
            datamatrix[max(0, i-1):8-i, max(0, i-1):8-i] = i%2
    datamatrix = np.rot90(datamatrix.T)

    # alignment
    for i in range(3):
        datamatrix[28+i:33-i, 28+i:33-i] = (i+1)%2

    # timing
    for i in range(7, dim-7):
        datamatrix[i, 6] = datamatrix[6, i] = (i+1)%2

    # the "dark module"
    datamatrix[dim-8, 8] = 1

    # FORMAT INFO
    L4 = '110011000101111' # Low/Mask4
    ptr_ul = np.array([8, -1])
    steps_ul = [0, 1] * 8 + [-1, 0] * 7
    steps_ul[13] = 2 # hop over vertical timing
    steps_ul[18] = -2 # then horizontal

    ptr_x = np.array([dim, 8])
    steps_x = [-1, 0] * 7 + [15-dim, dim-16] + [0, 1] * 7

    for bit, step_ul, step_x in zip(L4, np.array(steps_ul).reshape(-1,2), np.array(steps_x).reshape(-1,2)):
        ptr_ul += step_ul
        ptr_x += step_x
        datamatrix[tuple(ptr_ul)] = int(bit)
        datamatrix[tuple(ptr_x)] = int(bit)

    # FILL
    dmask = datamatrix == 0.5

    cols = (dim-1)/2
    cursor = np.array([dim-1, dim]) # starting off the matrix
    up_col = [-1, 1, 0, -1] * dim
    down_col = [1, 1, 0, -1] * dim
    steps = ([0, -1] + up_col[2:] + [0, -1] + down_col[2:]) * (cols/2)
    steps = np.array(steps).reshape(-1, 2)
    steps = iter(steps)

    # bit-ify everything
    msg_enc = ''.join('{:08b}'.format(x) for x in msg_enc) + '0' * 7 # 7 0's are for padding
    for bit in msg_enc:
        collision = 'maybe'
        while collision:
            cursor += steps.next()
            # skip vertical timing
            if cursor[1] == 6:
                cursor[1] = 5
            collision = not dmask[tuple(cursor)]
        datamatrix[tuple(cursor)] = int(bit)

    # COOK
    mask4 = lambda i, j: (i//2 + j//3)%2 == 0
    for i in range(dim):
        for j in range(dim):
            if dmask[i, j]:
                datamatrix[i, j] = int(datamatrix[i, j]) ^ (1 if mask4(i, j) else 0)

    # THE PRESTIGE
    plt.figure(facecolor='white')
    plt.imshow(datamatrix, cmap=plt.cm.gray_r, interpolation='nearest')
    plt.axis('off')
    plt.show()

if __name__ == '__main__':
    main()

After:

import sys
from pylab import*
n=range
l=len
E=[1]+[0]*511
L=[0]*256
x=1
for i in n(1,255):
 x<<=1
 if x&256:x^=285
 E[i]=x;L[x]=i
for i in n(255,512):E[i]=E[i-255]
def f(x,y):
 if x*y==0:return 0
 return E[L[x]+L[y]]
m=sys.argv[1]
m=[ord(c)*16 for c in'\4'+chr(l(m))+m]
for i in n(1,l(m)):m[i-1]+=m[i]/256;m[i]=m[i]%256
m=(m+[236,17]*54)[:108]
g=[1]
for i in n(26):
 q=[1,E[i]]
 r=[0]*(l(g)+l(q)-1)
 for j in n(l(q)):
    for i in n(l(g)):r[i+j]^=f(g[i],q[j])
 g=r
e=[0]*134
for i in n(108):
 e[i]=m[i]
for i in n(108):
 c=e[i]
 if c: 
    for j in n(l(g)):e[i+j]^=f(g[j],c)
for i in n(108):e[i]=m[i]
m=.1*ones((37,)*2)
for _ in n(3):
 m=rot90(m)
 for i in n(4):m[max(0,i-1):8-i,max(0,i-1):8-i]=i%2
m=rot90(m.T)
for i in n(3):m[28+i:33-i,28+i:33-i]=(i+1)%2
for i in n(7,30):m[i,6]=m[6,i]=(i+1)%2
m[29,8]=1
a=array
t=tuple
g=int
r=lambda x:iter(a(x).reshape(-1,2))
p=a([8,-1])
s=[0,1]*8+[-1,0]*7
s[13]=2
s[18]=-2
P=a([37,8])
S=[-1,0]*7+[-22,21]+[0,1]*7
for b,q,Q in zip(bin(32170)[2:],r(s),r(S)):p+=q;P+=Q;m[t(p)]=g(b);m[t(P)]=g(b)
D=m==0.1
c=a([36,37])
s=r(([0,-1]+([-1,1,0,-1]*37)[2:]+[0,-1]+([1,1,0,-1]*37)[2:])*9)
for b in ''.join('{:08b}'.format(x) for x in e):
 k=3
 while k:
    c+=s.next()
    if c[1]==6:c[1]=5
    k=not D[t(c)]
 m[t(c)]=g(b)
a=n(37)
for i in a:
 for j in a:
    if D[i,j]:m[i,j]=g(m[i,j])^(j%3==0)
imshow(m,cmap=cm.gray_r);show()

(relying on a tab to count as 4/8/whatever number of spaces >= 2., not sure how well it will copy)

Because it's so long, we can zip it (saw someone do this somewhere else, forgot who though :( ) to save some more characters, bringing the total down to 1085 1077 because pylab is filthy:

import zlib,base64
exec zlib.decompress(base64.b64decode('eJxtU0tzmzAQvvSkX6FLaglkyiM2hHRvyS2HZNobo3QwwY6IBVjQFrfT/96V3KR4Wg5I+/6+3ZXSfWdGOhwHsjWdpv1xX26oclqPtGDKdleTPezrltxCEUm/CKW3iiJyB/YWr9ZkgohsO0MVVS1tWSTi1YrnhE4fP6KFqi2d3qNfPj1CnK0IvS2UhOn6rpgkqHkkxolVFPPceeBviRpJnuot3bJJHG1Sm807AoS5qcevpqUhoX9ut4VN6d8VRymJBuQUlGb3DUGjVHTmiVXci9bUVqyw4uLdwq+eDdszzbmv5TkJp801gkDSgKf8gCSu7cVJF5a6Bqb9Ik7WIkqxLZe8yKMwk2RnW3VGbW3BH1AtLDmJoF3/sPiO+3t24MuIEwetOUVYnY3Bb5bHuvPcFMpv5CNs2Q6TiUPRSAzegSG1yxoll2dkwsxmql+h/8dWgbW69lY5favazKvWs6qNFBX/J8/fChqCyOvaemAsSQX34pPzl5NzYktqMN14FWKbyZzhpW26LicWCmw9z7OlEucibs1FTN7Cg89nQBIbH2e+ypMEQ99uEpjyI46RM+dUJKEbslhb4Gsxc8MsVyKTuMIllMaURzLC+LXf1zhd1Y7EwL7Um6eSTrkaa8NKNvHA1MNz2ddsia+Ac9JDyYpM4ApxMuBoRCS9zC/QilNKyVBEiYTYnlhoGZN7648Ny9D/E7z6YUAci9g9PpshdRQ24iAeLI0fqmcbhczjKA15EedSGDZw/H3CqfU+HK7vfXjA1R1ZzyXs2IY74f6PQG5A44sKIlK5+muRpA6wYQwr2gfALBZEYwUvSV0V/832j4l7V6ehbCzAxSJoOgS4+JmH2ebXIkCLLkfslxv8ZH1quxIvkBD6/Vnta/pyWv3KhyFo62lk3Ml2P/FpAaxzd66c9gXabqQ3SKniuMT6dDlxKwE7k85WpMxn76zMX9Pe4BI00u1CY0NPF/7ImosEm8OJ0sNz951pUemyh0oHO9yJL4ZfOzX/DQ2mdSs='))

enter image description here

If you replace the last line with the following (it adds 62 chars), you get nearly-perfect output, but the other still scans, so whatever.

figure(facecolor='white');imshow(m,cmap=cm.gray_r,interpolation='nearest');axis('off');show()

Good QR code

Nick T

Posted 2014-02-03T23:30:30.330

Reputation: 3 197

@NickT yeah, it does. – Rɪᴋᴇʀ – 2016-03-30T22:35:56.827

Great job! It's a pity that Python isn't the best in golfing solutions, but this is remarkable coding, @NickT! – WallyWest – 2014-02-05T21:57:10.707

I could probably save some more if I lose the struct call and some unnecessary bit pushing by just truncating my 'master string'... – Nick T – 2014-02-13T03:50:24.567

There's a decent saving to be made (if it survives the compression) by replacing the implementation of gf_mul with a long multiplication. You can ditch the tables entirely; the multiplication is def f(x,y):\n r=0\n for _ in n(8):\n\tif y&1:r^=x\n\tx,y=x*2,y//2\n\tif x&256:x^=285\n return r and to get round the usage of gf_exp in the second loop of main you have to pull out an accumulator: E=1\nfor i in n(26):\n q=[1,E]\n E=f(E,2)\n ... I make it a saving of 75 bytes (5.6%) before compression. – Peter Taylor – 2019-03-13T15:28:57.770

In fact, the calculation of gen can also be golfed quite a lot: g=[1]+[0]*26\nE=1\nfor i in n(26):\n for j in n(26,0,-1):\n\tg[j]^=f(g[j-1],E)\n\tE=f(E,2) – Peter Taylor – 2019-03-13T16:41:47.943

FYI the second indentation level can be just two spaces. I've noticed that you use four/tab. – Beta Decay – 2014-10-21T06:45:59.847

1@BetaDecay it's supposed to just be 1 tab (1 tab > 1 space as far as indenting is concerned...I think SE breaks tabs?) – Nick T – 2014-10-21T07:13:39.343