Kode QR ... dan semua Jazz itu!

18

Ini akan menjadi tantangan kode-golf yang relatif menantang.

Input: URL apa pun, harus memiliki protokol yang dilampirkan, misalnya http://codegolf.stackexchange.com (yang akan menjadi uji coba kami)

Output: Kode QR yang dihasilkan yang mewakili URL ini, yang, ketika dipindai oleh perangkat pintar akan membawa Anda ke URL itu di peramban perangkat pintar tersebut.

Aturan untuk Golf-Kode ini

  1. Seperti biasa, kode terkecil menang.
  2. Tidak ada sumber daya web eksternal, pustaka atau plugin untuk menghasilkan kode untuk Anda. Kode Anda harus menghitung gambar kode QR.
  3. Output dapat disajikan oleh gambar, dihasilkan oleh HTML5 / CSS3, atau bahkan menggunakan blok Unicode yang sesuai, atau jika ASCII platform Anda memilikinya tersedia, melalui karakter ASCII yang dapat membentuk kode QR (yang terakhir ini diarahkan pada Commodore 64 Basic, Amiga QBasic, Amstrad Basic, dll pengguna), tetapi harus menghasilkan output kode QR sehingga saya dapat memindai kode.
  4. Entri kode harus diikuti dengan output yang dihasilkan, baik dengan cuplikan layar output setelah mengeksekusi kode Anda, atau dengan tautan yang menunjukkan output (mana yang paling sesuai dengan situasi)
  5. Anda harus menguji kode Anda dengan URL " http://codegolf.stackexchange.com ", dan melaporkan hasilnya sesuai dengan Aturan 3 hingga 4.
  6. Anda juga harus menguji kode Anda dengan URL pilihan Anda, dan melaporkan hasilnya sesuai dengan Aturan 3 hingga 4.

Referensi:

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/ untuk inspirasi ...;)

WallyWest
sumber
4
Rekursi tak terbatas pada aturan 5.
user12205
@ace Melihat dengan baik ... ini telah diperbaiki
WallyWest
1
Setelah membaca beberapa dokumentasi, saya pikir "relatif menantang" adalah pernyataan yang meremehkan.
Danny
Bisakah kita mendapatkan klarifikasi tentang apa arti "kode Anda harus menghitung gambar kode QR"? Saya mengartikannya bahwa kita harus melakukan dua poin utama dalam kode yang dikirimkan : 1) RS encoding , dan 2) tata letak modul .
Nick T
aturan 3: jadi apakah ascii art dicetak dari denda terminal, atau apakah harus masuk ke file gambar yang sebenarnya?

Jawaban:

17

Python 3: 974 karakter [nb]

Selanjutnya kocok dengan tongkat jelek, lihat notebook di GH-Gist . Python 3 memiliki pengkodean ASCII-85 bawaan, yang membantu dengan sosis zip. Algoritma kompresi bawaan (LZMA) 3 yang lebih canggih tampaknya tidak bekerja dengan baik dengan hal-hal kecil seperti itu.

Zip sangat berubah-ubah tentang mengubah karakter sekitar, hampir tergoda untuk menulis sesuatu yang secara acak akan mencoba nama 1 huruf berbeda untuk variabel untuk meminimalkan ukuran zip.

Python 2: 1420 1356 1085 1077 karakter

masukkan deskripsi gambar di sini

Saya membaca argumen pertama yang diloloskan ketika dipanggil, yang bisa berupa string hingga 106-ish karakter. Outputnya selalu berupa kode QR 5-L versi dan mask 4 yang berarti 37x37 modulnya besar dan hanya bisa menangani ~ 5% kerusakan.

Satu-satunya dependensi program adalah numpy(manipulasi array) dan matplotlib(hanya tampilan); semua pengodean, pengemasan data, dan tata letak modul Reed-Solomon ditangani dalam kode yang disediakan . Untuk RS, saya pada dasarnya merampok fungsi Wikiversity ... itu masih semacam kotak hitam bagi saya. Belajar banyak tentang QR dalam acara apa pun.

Inilah kode sebelum saya mengalahkannya dengan tongkat jelek:

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()

Setelah:

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()

(mengandalkan tab untuk menghitung 4/8 / berapapun jumlah spasi> = 2., tidak yakin seberapa baik ia akan menyalin)

Karena begitu lama, kita dapat meng-zip-nya (melihat seseorang melakukan ini di tempat lain, lupa siapa :() untuk menyimpan beberapa karakter lagi, sehingga totalnya turun menjadi 1085 1077 karena pylabkotor:

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='))

masukkan deskripsi gambar di sini

Jika Anda mengganti baris terakhir dengan yang berikut (ini menambahkan 62 karakter), Anda mendapatkan output yang hampir sempurna, tetapi yang lainnya masih memindai, jadi apa pun.

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

Kode QR yang bagus

Nick T
sumber
Kerja bagus! Sangat disayangkan bahwa Python bukan yang terbaik dalam solusi golf, tetapi ini adalah coding yang luar biasa, @NickT!
WallyWest
Saya mungkin bisa menghemat lebih banyak jika saya kehilangan structpanggilan dan beberapa dorongan yang tidak perlu dengan hanya memotong 'master string' saya ...
Nick T
FYI tingkat indentasi kedua bisa hanya dua ruang. Saya perhatikan Anda menggunakan empat / tab.
Beta Decay
1
@BetaDecay seharusnya hanya menjadi 1 tab (1 tab> 1 spasi sejauh indentasi yang bersangkutan ... Saya pikir SE merusak tab?)
Nick T
@NickT ya, itu benar.
Rɪᴋᴇʀ