Códigos QR ... e todo esse Jazz!

18

Este será um desafio relativamente desafiador ao código-golfe.

Entrada: Qualquer URL, deve ter o protocolo anexado, por exemplo, http://codegolf.stackexchange.com (que será nosso caso de teste)

Saída: um código QR gerado que representa esse URL que, quando verificado por um dispositivo inteligente, leva você a esse URL no navegador do dispositivo inteligente.

Regras para este Código-Golfe

  1. Como sempre, o menor código vence.
  2. Não há recursos externos da web, bibliotecas ou plugins para gerar o código para você. Seu código deve calcular a imagem do código QR.
  3. A saída pode ser apresentada por uma imagem, gerada por HTML5 / CSS3, ou mesmo usando blocos Unicode apropriados, ou se o ASCII da sua plataforma estiver disponível, através de caracteres ASCII que podem formar o código QR (este último é direcionado ao Commodore 64 Basic, Usuários Amiga QBasic, Amstrad Basic, etc), mas deve gerar uma saída de código QR para que eu possa digitalizar o código.
  4. As entradas do código devem ser seguidas com a saída gerada, por uma captura de tela da saída após a execução do código ou por um link que mostre a saída (o que melhor se adequar à situação)
  5. Você deve testar seu código com o URL " http://codegolf.stackexchange.com " e relatar a saída de acordo com as Regras 3 a 4.
  6. Você também deve testar seu código com um URL de sua escolha e relatar a saída de acordo com as Regras 3 a 4.

Referências:

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/ para inspiração ...;)

WallyWest
fonte
4
Recursão infinita na regra 5.
user12205 04/04
@ace Bem visto ... isso foi corrigido
Wally West
1
Depois de ler alguma documentação, acho que "relativamente desafiador" é um eufemismo.
Danny
Podemos obter um esclarecimento sobre o que significa "seu código deve calcular a imagem do código QR"? Estou entendendo que devemos fazer os dois pontos principais no código enviado : 1) codificação RS e 2) layout do módulo .
Nick T
regra 3: assim, a arte ascii é impressa a partir de um terminal, ou precisa ser inserida em um arquivo de imagem real?

Respostas:

17

Caracteres do Python 3: 974 [nb]

Para bater ainda mais com o bastão feio, veja o caderno no GH-Gist . O Python 3 possui codificação ASCII-85 embutida, que ajuda com o molho compactado. Os algoritmos de compressão incorporados (LZMA) mais avançados da 3 parecem não funcionar bem com coisas tão pequenas.

O zíper é muito inconstante quanto à mudança de caracteres, quase tentava escrever algo que tentasse aleatoriamente nomes diferentes de uma letra para variáveis ​​para minimizar o tamanho do zíper.

Python 2: 1420 1356 1085 1077 caracteres

insira a descrição da imagem aqui

Eu li o primeiro argumento passado quando chamado, que pode ser uma cadeia de caracteres com até 106 caracteres. A saída é sempre um código QR da versão 5-L e uma máscara 4, o que significa que possui 37x37 módulos grandes e pode suportar apenas ~ 5% de dano.

As únicas dependências do programa são numpy(manipulações de matriz) e matplotlib(somente exibição); toda a codificação Reed-Solomon, empacotamento de dados e layout do módulo são manipulados dentro do código fornecido . Para o RS, basicamente roubei as funções da Wikiversidade ... ainda é uma espécie de caixa preta para mim. De qualquer forma, aprendi muito sobre o QR.

Aqui está o código antes de eu vencê-lo com o bastão feio:

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

Depois de:

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

(contando com uma guia para contar como 4/8 / qualquer número de espaços> = 2., não tenho certeza de quão bem ele será copiado)

Por ser tão longo, podemos compactá-lo (vi alguém fazer isso em outro lugar, esqueceu quem :() para salvar mais alguns personagens, diminuindo o total para 1085 1077, porque pylabé imundo:

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

insira a descrição da imagem aqui

Se você substituir a última linha pela seguinte (ela adiciona 62 caracteres), obtém uma saída quase perfeita, mas a outra ainda digitaliza, o que for.

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

Good QR code

Nick T
fonte
Bom trabalho! É uma pena que o Python não seja o melhor em soluções de golfe, mas essa é uma codificação notável, @NickT!
5304 WallyWest
Eu provavelmente poderia salvar um pouco mais se eu perder a structchamada e alguns pouco desnecessária empurrando por apenas truncar o meu 'string mestre' ...
Nick T
Para sua informação, o segundo nível de indentação pode ter apenas dois espaços. Notei que você usa quatro / tab.
Beta Decay
1
@BetaDecay que é suposto ser apenas um guia (1 tab> 1 espaço, tanto quanto o recuo está em causa ... Eu acho SE breaks guias?)
Nick T
@ NickT sim, faz.
Rɪᴋᴇʀ