QR-Codes ... und der ganze Jazz!

18

Dies wird eine relativ herausfordernde Code-Golf-Herausforderung sein.

Eingabe: Für jede URL muss das Protokoll angehängt sein, z. B. http://codegolf.stackexchange.com (dies ist unser Testfall).

Ausgabe: Ein generierter QR-Code, der diese URL darstellt. Wenn Sie von einem Smart-Gerät gescannt werden, gelangen Sie zu dieser URL im Browser des Smart-Geräts.

Regeln für diesen Code-Golf

  1. Wie immer gewinnt der kleinste Code.
  2. Keine externen Webressourcen, Bibliotheken oder Plugins, um den Code für Sie zu generieren. Ihr Code muss das QR-Code-Bild berechnen.
  3. Die Ausgabe kann durch ein Bild erfolgen, das mit HTML5 / CSS3 oder sogar mit geeigneten Unicode-Blöcken erstellt wurde, oder, falls ASCII auf Ihrer Plattform verfügbar ist, durch ASCII-Zeichen, die den QR-Code bilden können (letzteres richtet sich an Commodore 64 Basic). Amiga QBasic, Amstrad Basic usw.), aber es muss eine QR-Code-Ausgabe generiert werden, damit ich den Code scannen kann.
  4. Eingaben des Codes müssen mit der generierten Ausgabe gefolgt werden, entweder mit einem Screenshot der Ausgabe nach Ausführung Ihres Codes oder mit einem Link, der die Ausgabe anzeigt (je nachdem, was der Situation am besten entspricht).
  5. Sie müssen Ihren Code mit der URL " http://codegolf.stackexchange.com " testen und die Ausgabe gemäß den Regeln 3 bis 4 melden.
  6. Sie müssen Ihren Code auch mit einer URL Ihrer Wahl testen und die Ausgabe gemäß den Regeln 3 bis 4 melden.

Verweise:

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/ zur Inspiration ...;)

WallyWest
quelle
4
Endlose
@ace Gut gesehen ... dies wurde behoben
WallyWest
1
Nach dem Lesen einer Dokumentation halte ich "relativ herausfordernd" für eine Untertreibung.
Danny
Können wir klären, was "Ihr Code muss das QR-Code-Bild berechnen" bedeutet? Ich nehme es bedeuten , dass wir müssen die beiden wichtigsten Punkte tun in dem eingereichten Code : 1) RS kodiert , und 2) Modul - Layout .
Nick T
Regel 3: Wird ASCII-Kunst von einem Terminal aus gedruckt, oder muss sie in eine tatsächliche Bilddatei kopiert werden?

Antworten:

17

Python 3: 974 Zeichen [nb]

Weiter mit dem hässlichen Stock schlagen, siehe Notizbuch auf GH-Gist . Python 3 verfügt über eine integrierte ASCII-85-Codierung, die bei der komprimierten Ausgabe hilft. Die fortschrittlicheren integrierten Kompressionsalgorithmen (LZMA) von 3 scheinen mit so kleinen Dingen nicht gut zu funktionieren.

Das Zippen ist sehr unbeständig, wenn es darum geht, Zeichen zu ändern. Es war fast versucht, etwas zu schreiben, bei dem zufällig verschiedene Namen mit einem Buchstaben für Variablen gesucht wurden, um die Größe des Zippers zu minimieren.

Python 2: 1420 1356 1085 1077 Zeichen

Bildbeschreibung hier eingeben

Ich habe das erste beim Aufruf übergebene Argument gelesen, das eine Zeichenfolge mit bis zu 106 Zeichen sein kann. Die Ausgabe ist immer ein Version 5-L QR-Code und Maske 4, was bedeutet, dass die Module 37x37 groß sind und nur ~ 5% Schaden aushalten können.

Die einzigen Abhängigkeiten des Programms sind numpy(Array-Manipulationen) und matplotlib(nur Anzeige); Alle Reed-Solomon-Codierungen, Datenpakete und Modullayouts werden im bereitgestellten Code behandelt . Für RS habe ich im Grunde genommen die Wikiversity-Funktionen beraubt ... für mich ist es immer noch eine Art Black-Box. Auf jeden Fall eine Menge über QR gelernt.

Hier ist der Code, bevor ich ihn mit dem hässlichen Stock besiege:

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

Nach:

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

(unter Verwendung eines Tabulators als 4/8 / unabhängig von der Anzahl der Leerzeichen> = 2., nicht sicher, wie gut es kopiert)

Weil es so lange dauert, können wir es komprimieren (ich habe es woanders gemacht, habe aber vergessen, wen :(), um ein paar weitere Zeichen zu speichern, was die Gesamtsumme auf 1085 - 1077 reduziert, weil pylabes schmutzig ist:

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

Bildbeschreibung hier eingeben

Wenn Sie die letzte Zeile durch die folgende ersetzen (es werden 62 Zeichen hinzugefügt), erhalten Sie eine nahezu perfekte Ausgabe, aber die andere scannt immer noch.

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

Guter QR-Code

Nick T
quelle
Gut gemacht! Es ist schade, dass Python nicht die beste Lösung für das Golfen ist, aber das ist eine bemerkenswerte Codierung, @NickT!
WallyWest
Ich könnte wahrscheinlich mehr sparen, wenn ich den structAnruf verliere und ein unnötiges bisschen Druck ausübe, indem ich einfach meine 'Master-Saite' abschneide ...
Nick T
Zu Ihrer Information: Die zweite Einrückungsstufe kann nur zwei Leerzeichen umfassen. Mir ist aufgefallen, dass Sie vier / tab verwenden.
Beta Decay
1
@ BetaDecay es soll nur 1 Tab sein (1 Tab> 1 Leerzeichen, was Einrückung betrifft ... Ich denke, SE Tabs?)
Nick T
@ NickT ja, das tut es.
30.