QR Codes… et tout ce jazz!

18

Cela va être un défi de golf de code relativement difficile.

Entrée: Toute URL doit avoir le protocole attaché, par exemple http://codegolf.stackexchange.com (qui sera notre cas de test)

Sortie: un code QR généré qui représente cette URL, qui, lorsqu'il est analysé par un appareil intelligent, vous amènera à cette URL sur le navigateur de l'appareil intelligent.

Règles pour ce Code-Golf

  1. Comme d'habitude, le plus petit code gagne.
  2. Aucune ressource Web externe, bibliothèque ou plug-in pour générer le code pour vous. Votre code doit calculer l'image du code QR.
  3. La sortie peut être présentée par une image, générée par HTML5 / CSS3, ou même en utilisant des blocs Unicode appropriés, ou si l'ASCII de votre plate-forme en dispose, via des caractères ASCII qui peuvent former le code QR (cette dernière est dirigée vers Commodore 64 Basic, Utilisateurs Amiga QBasic, Amstrad Basic, etc.), mais il doit générer une sortie de code QR pour que je puisse scanner le code.
  4. Les entrées du code doivent être suivies de la sortie générée, soit par une capture d'écran de la sortie après l'exécution de votre code, soit par un lien montrant la sortie (selon la situation qui convient le mieux)
  5. Vous devez tester votre code avec l'URL " http://codegolf.stackexchange.com " et signaler la sortie conformément aux règles 3 à 4.
  6. Vous devez également tester votre code avec l'URL de votre choix et signaler la sortie conformément aux règles 3 à 4.

Les références:

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/ pour l'inspiration ...;)

WallyWest
la source
4
Récursion infinie à la règle 5.
user12205
@ace Bien repéré ... cela a été corrigé
WallyWest
1
Après avoir lu de la documentation, je pense que "relativement difficile" est un euphémisme.
Danny
Pouvons-nous obtenir une clarification sur ce que signifie "votre code doit calculer l'image du code QR"? Je suppose que cela signifie que nous devons faire les deux points principaux du code soumis : 1) l' encodage RS et 2) la disposition des modules .
Nick T
règle 3: est-ce que l'art ascii est imprimé à partir d'une amende terminale, ou doit-il aller dans un fichier image réel?

Réponses:

17

Python 3: 974 caractères [nb]

Battez encore plus avec le vilain bâton, voir le carnet sur GH-Gist . Python 3 a un encodage ASCII-85 intégré, qui aide avec le saus zippé. Les algorithmes de compression intégrés (LZMA) plus avancés de 3 ne semblent pas bien fonctionner avec de si petites choses.

La fermeture à glissière est très inconstante pour changer les caractères, elle était presque tentée d'écrire quelque chose qui essaierait au hasard différents noms à 1 lettre pour les variables afin de minimiser la taille zippée.

Python 2: 1420 1356 1085 1077 caractères

entrez la description de l'image ici

J'ai lu le premier argument passé lors de l'appel, qui peut être une chaîne de 106 caractères maximum. La sortie est toujours un code QR de version 5-L et un masque 4, ce qui signifie qu'il fait 37x37 modules de grande taille et ne peut gérer que 5% de dégâts.

Les seules dépendances du programme sont numpy(manipulations de tableaux) et matplotlib(affichage uniquement); tout l'encodage Reed-Solomon, l'emballage des données et la disposition des modules sont traités dans le code fourni . Pour RS, j'ai essentiellement volé les fonctions de Wikiversité ... c'est toujours une sorte de boîte noire pour moi. J'ai beaucoup appris sur QR dans tous les cas.

Voici le code avant de le battre avec le bâton laid:

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

Après:

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

(en s'appuyant sur un onglet pour compter comme 4/8 / quel que soit le nombre d'espaces> = 2., je ne sais pas dans quelle mesure il copiera)

Parce que c'est si long, nous pouvons le compresser (vu quelqu'un faire cela ailleurs, j'ai oublié qui cependant :() pour enregistrer quelques caractères supplémentaires, ce qui ramène le total à 1085 1077 parce que pylabc'est sale:

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

entrez la description de l'image ici

Si vous remplacez la dernière ligne par la suivante (elle ajoute 62 caractères), vous obtenez une sortie presque parfaite, mais l'autre scanne toujours, donc peu importe.

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

Bon code QR

Nick T
la source
Bon travail! C'est dommage que Python ne soit pas le meilleur des solutions de golf, mais c'est un codage remarquable, @NickT!
WallyWest
Je pourrais probablement économiser un peu plus si je perds l' structappel et un peu de poussée inutile en tronquant simplement ma 'chaîne principale' ...
Nick T
Pour info le deuxième niveau d'indentation peut être seulement deux espaces. J'ai remarqué que vous utilisez quatre / tab.
Beta Decay
1
@BetaDecay, il est censé n'être que 1 onglet (1 onglet> 1 espace en ce qui concerne l'indentation ... Je pense que SE brise les onglets?)
Nick T
@ NickT oui, c'est le cas.
Rɪᴋᴇʀ