QR-коды ... и все такое джаз!

18

Это будет довольно сложная задача для игры в гольф.

Входные данные: к любому URL должен быть прикреплен протокол, например, http://codegolf.stackexchange.com (который будет нашим тестовым примером)

Вывод: сгенерированный QR-код, представляющий этот URL-адрес, который при сканировании интеллектуальным устройством приведет вас к этому URL-адресу в браузере смарт-устройства.

Правила для этого Code-Golf

  1. Как обычно, маленький код выигрывает.
  2. Нет внешних веб-ресурсов, библиотек или плагинов для генерации кода для вас. Ваш код должен рассчитать изображение QR-кода.
  3. Вывод может быть представлен изображением, сгенерированным HTML5 / CSS3, или даже с использованием соответствующих блоков Unicode, или, если ASCII вашей платформы имеет его, через символы ASCII, которые могут формировать QR-код (этот последний предназначен для Commodore 64 Basic, Amiga QBasic, Amstrad Basic и т. Д.), Но он должен генерировать вывод QR-кода, чтобы я мог сканировать код.
  4. За записями кода следует сопровождаемый сгенерированный вывод, либо снимок экрана вывода после выполнения вашего кода, либо ссылка, отображающая вывод (в зависимости от ситуации, которая лучше всего подходит)
  5. Вы должны проверить свой код по URL-адресу « http://codegolf.stackexchange.com » и сообщить о результатах в соответствии с правилами 3-4.
  6. Вы также должны протестировать свой код с выбранным URL-адресом и сообщить о результатах в соответствии с правилами 3-4.

Ссылки:

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/ для вдохновения ...;)

Уолли Уэст
источник
4
Бесконечная рекурсия по правилу 5.
user12205
@ace Хорошо замечено ... это было исправлено
WallyWest
1
После прочтения некоторой документации, я думаю, что «относительно сложным» является занижение.
Дэнни
Можем ли мы получить разъяснение относительно того, что означает «ваш код должен рассчитывать изображение QR-кода»? Я понимаю, что в представленном коде мы должны выполнить два основных пункта : 1) кодирование RS и 2) компоновка модуля .
Ник Т
Правило 3: так хорошо ли печатается ascii art из терминала, или оно должно идти в реальном файле изображения?

Ответы:

17

Python 3: 974 символа [примечание]

Далее бейте уродливой палкой, смотрите блокнот на GH-Gist . Python 3 имеет встроенную кодировку ASCII-85, которая помогает с молнии сосиски. Более продвинутые встроенные алгоритмы сжатия 3 (LZMA), похоже, плохо работают с такими мелочами.

Сжатие очень изменчиво при смене символов, было почти искушение написать что-то, что будет случайным образом пытаться использовать разные однобуквенные имена для переменных, чтобы минимизировать размер архива.

Python 2: 1420 1356 1085 1077 символов

введите описание изображения здесь

Я прочитал первый аргумент, переданный при вызове, который может быть строкой длиной до 106 символов. Выводом всегда является QR-код версии 5-L и маска 4, что означает, что он имеет размеры 37x37 модулей и может выдержать только ~ 5% урона.

Единственными зависимостями программы являются numpy(манипуляции с массивами) и matplotlib(только отображение); все кодирование Рида-Соломона, упаковка данных и расположение модулей обрабатываются в предоставленном коде . Что касается RS, я в основном ограбил функции Викиверситета ... для меня это все еще своего рода черный ящик. Узнал тонну о QR в любом случае.

Вот код, прежде чем я победил его уродливой палкой:

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

После:

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

(полагаясь на вкладку, чтобы считать 4/8 / любое количество пробелов> = 2., не уверен, насколько хорошо она будет копировать)

Поскольку это так долго, мы можем заархивировать его (видел, как кто-то делал это где-то еще, забыл, кто, хотя :(), чтобы сохранить еще несколько символов, в результате чего общее количество уменьшилось до 1085 1077, потому что pylabэто грязно:

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

введите описание изображения здесь

Если вы замените последнюю строку на следующую (она добавляет 62 символа), вы получите почти идеальный вывод, но другая все равно сканирует, и так далее.

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

Хороший QR-код

Ник Т
источник
Прекрасная работа! Жаль, что Python не лучший в решениях для игры в гольф, но это замечательное кодирование, @NickT!
WallyWest
Я мог бы, вероятно, сэкономить еще немного, если бы я потерял structвызов и некоторые ненужные нажатия, просто обрезая мою «главную строку» ...
Ник Т
К вашему сведению, второй уровень отступов может быть всего двумя пробелами. Я заметил, что вы используете четыре / Tab.
Бета-распад
1
@BetaDecay это всего лишь 1 вкладка (1 вкладка> 1 пробел в отношении отступа ... Я думаю, что SE ломает вкладки?)
Ник Т
@NickT да, это так.
2016 года