Bersenang-senang dengan bendera!

20

Tulis program lengkap dengan kode sumber 256 byte atau kurang yang terlihat pada gambar bendera dan tentukan dari negara mana bendera itu berasal. File zip yang berisi 196 bendera berbeda dalam tantangan dapat diunduh dari sini . Sumber: [ Flagpedia ]. 196 gambar bendera ini adalah satu-satunya input yang harus ditangani oleh program Anda.

Program Anda tidak akan menerima input. Gambar bendera akan berada di direktori yang sama dengan program Anda dan dinamai "f.png". Program Anda akan membuka file ini, mengidentifikasinya, dan mencetak singkatan dua huruf untuk negara itu . Jika Anda menggunakan bahasa yang tidak dapat membuka file, Anda juga dapat menjalankan program sebagai ./program < f.png.

Setiap file flag dinamai sama dengan output yang diharapkan. Semua output di atas 2 huruf akan diabaikan.

Berikut adalah daftar semua output / nama file:

ad, ae, af, ag, al, am, ao, ar, at, au, az, ba, bb, bd, be, bf, bg, bh, bi, bj,
bn, bo, br, bs, bt, bw, by, bz, ca, cd, cf, cg, ch, ci, cl, cm, cn, co, cr, cu,
cv, cy, cz, de, dj, dk, dm, do, dz, ec, ee, eg, eh, er, es, et, fi, fj, fm, fr,
ga, gb, gd, ge, gh, gm, gn, gq, gr, gt, gw, gy, hn, hr, ht, hu, id, ie, il, in,
iq, ir, is, it, jm, jo, jp, ke, kg, kh, ki, km, kn, kp, kr, ks, kw, kz, la, lb,
lc, li, lk, lr, ls, lt, lu, lv, ly, ma, mc, md, me, mg, mh, mk, ml, mm, mn, mr,
mt, mu, mv, mw, mx, my, mz, na, ne, ng, ni, nl, no, np, nr, nz, om, pa, pe, pg,
ph, pk, pl, pt, pw, py, qa, ro, rs, ru, rw, sa, sb, sc, sd, se, sg, si, sk, sl,
sm, sn, so, sr, st, sv, sy, sz, td, tg, th, tj, tl, tm, tn, to, tr, tt, tv, tw,
tz, ua, ug, us, uy, uz, va, vc, ve, vn, vu, ws, ye, za, zm, zw, 

Mencetak gol

Berikut ini adalah skrip python pendek yang akan saya gunakan untuk menilai setiap pengiriman.

import os
import subprocess
import random

botlist = []
with open("bots.txt") as bots:
    for line in bots:
        line = line.split(", ")
        if len(line) >= 2:
            botLine = line + [0]
            botlist.append(botLine)

files = os.listdir(os.getcwd() + "/flags")
random.shuffle(files)

def test(bot_command):
    score = 0
    for filename in files:
        command = "COPY flags\\{} f.png".format(filename)
        os.system(command)

        print bot_command

        result = subprocess.check_output(bot_command, shell = True)
        if result[:2] == filename[:2]:
            score += 1

    return score

for i in range(len(botlist)):
    command = botlist[i][1]
    botlist[i][2] = test(command)

with open("output.txt", "w+") as output:
    for bot in botlist:
        output.write("{} got a score of {}.".format(bot[0], bot[2]))

os.system("del f.png")

Skor Anda adalah jumlah total bendera yang diidentifikasi dengan benar. Dalam hal seri, pengajuan sebelumnya menang.

Aturan

  • Untuk kenyamanan pengujian saya, bahasa apa pun dengan juru bahasa / kompiler yang tersedia secara bebas untuk Windows 10 atau Ubuntu dapat digunakan.

  • Pustaka pemrosesan gambar diizinkan, tetapi bawaan apa pun yang terkait dengan bendera atau negara tidak diizinkan. ( Batuk Mathematica batuk )

  • Harap berikan perintah lengkap yang diperlukan untuk menjalankan program Anda bersama dengan tautan ke perpustakaan yang diperlukan.

  • Kiriman tidak boleh berinteraksi dengan file apa pun kecuali "f.png".

  • Saya tidak memiliki batas waktu pengajuan yang sulit, tapi tolong tetap relatif cepat. Saya tidak ingin skrip penilaian membutuhkan waktu berjam-jam.

DJMcMayhem
sumber
4
Batas byte sangat rendah. Hanya menyimpan 196 kode dua huruf yang tidak terkompresi membutuhkan 392 byte
edc65
2
@ edc65 Intinya adalah Anda hanya akan mendapatkan sejumlah kecil bendera.
isaacg
1
@ edc65 Saya sengaja memilih nomor yang akan membuat skor sempurna pada dasarnya mustahil. Ini lebih tentang kompresi mengenali gambar daripada codegolf.
DJMcMayhem
Cukup periksa ulang - bisakah kita hanya menggunakan ./program < f.pngopsi jika bahasa tidak memiliki cara membaca file, atau bisakah kita juga menggunakannya bahkan jika bahasa dapat membaca file? (Rupanya CJam dapat membaca dari file, yang saya tidak tahu)
Sp3000
196 gambar bendera ini adalah satu-satunya input yang harus ditangani oleh program Anda, maka Anda mengatakan bahwa program Anda tidak akan mengambil input . Apakah itu berarti bahwa satu file f.png akan menjadi salah satu dari 196 itu. Jadi program tidak dapat merujuk file zip tersebut? Just f.png
Matt

Jawaban:

11

CJam, 139 141

Ada banyak unsintables dalam kode, jadi inilah xxdhexdump:

00000000: 7132 3925 3162 226d cec5 9635 b14b 69ee  q29%1b"m...5.Ki.
00000010: d9d0 66e8 97b8 e88d 2366 7857 9595 1c73  ..f.....#fxW...s
00000020: 9324 11b2 ddb8 7a3f 19ed bd37 07c0 cb86  .$....z?...7....
00000030: 394e b34a ecf0 8c9b f300 a216 2e2e 594a  9N.J..........YJ
00000040: 9a6b 3b2f 250a 9a25 783b 0e49 3e9c 6ab9  .k;/%..%x;.I>.j.
00000050: 8d6d d729 42d0 85f3 657b 7d86 af48 c6cb  .m.)B...e{}..H..
00000060: f7ff 980f b81c dd5e e8cb 4e34 d8ec edca  .......^..N4....
00000070: 6646 1b4d 7605 8937 ed58 2302 1cc1 ebfd  fF.Mv..7.X#.....
00000080: 16d3 b53e 3e2c d879 fe33 feef dd65 d49f  ...>>,.y.3...e..
00000090: 5d73 7ced 92e6 9526 c186 00bf d2a8 ffaa  ]s|....&........
000000a0: 65a0 3001 f42a 94d7 592f ebe7 8bdf 97a7  e.0..*..Y/......
000000b0: 0681 8ee1 9e0e 424b f6a1 4c50 1c8a 8de5  ......BK..LP....
000000c0: 481a 388c 6eaa 0c43 e1db 69df 567b 323f  H.8.n..C..i.V{2?
000000d0: 2573 c4ce b348 6fff 37e0 55b4 7c9a 7e7d  %s...Ho.7.U.|.~}
000000e0: 73a4 ef74 2b99 b765 2a2d d99f 986a 355c  s..t+..e*-...j5\
000000f0: db22 3236 3362 3236 6227 6166 2b32 2f3d  ."263b26b'af+2/=

Ini persis 256 byte, dengan program ini melakukan:

q29%                          Read input and keep every 29th char
    1b                        Sum code points
      "..."                   Push long string
           263b               Convert long string to base 263
               26b            Convert result to base 26
                  'af+        Add 'a to each element in the resulting array
                      2/      Split into chunks of length 2
                        =     Index sum cyclically to extract output

Jalankan program dengan perintah

java -Dfile.encoding=ISO-8859-1 -jar cjam-0.6.5.jar flags.cjam < f.png

Terima kasih kepada @Dennis untuk bantuan agar kiriman ini berfungsi.

Sp3000
sumber
Saya kagum ada yang mendapat sebanyak ini. 139/196 = 70,9%. Kamu mendapat nilai A!
Level River St
Bisakah Anda membuat binary dump menjadi xxd -r-reversibel? Cygwin seharusnyaxxd
kucing
1
@tac Harus melihat sedikit, tapi saya tidak menyadari Cygwin memang memilikinya - Saya hanya harus memilihnya secara manual untuk instalasi. Saya akan memperbarui ketika saya berikutnya memperbarui jawabannya.
Sp3000
Saya mencoba menggunakan teknik yang sama dengan kode Morse , tetapi yang terbaik yang bisa saya dapatkan adalah 129 flag, dan saya bahkan belum memeriksa apakah cocok dengan batas 256-byte. Dilakukan dengan baik untuk menemukan hash yang baik.
Peter Taylor
12

Python 2, Skor = 68 89

Solusi ini menggunakan hash dari file gambar bendera untuk membuat indeks ke daftar singkatan negara. Jika lebih dari satu bendera di-hash ke indeks, hanya singkatan pertama yang akan dikembalikan (sehingga akan gagal beberapa tes dengan lebih dari satu negara dalam ember hash). Namun algoritma ini menjamin satu jawaban yang benar untuk setiap ember hash yang tidak kosong.

i=hash(open('f.png').read())%99*2
print'kgmviruasefridusvakpsmbtgrpwcdsdauninrsyalsg--game--espyscmtyebhgqom--kh--inhudjbw--ltroilbicv--jonaugke--svhtbg--simcknbnpelcplgncmmacimytnttlytgcflirsvemhtzuyqaerbfbepa--uzaenearcl--jmbbphkzrwieet'[i:i+2]

Program ini adalah 247 karakter.

Versi yang lebih mudah dibaca:

encoded = 'kgmviruasefridusvakpsmbtgrpwcdsdauninrsyalsg--game--espyscmtyebhgqom--kh--inhudjbw--ltroilbicv--jonaugke--svhtbg--simcknbnpelcplgncmmacimytnttlytgcflirsvemhtzuyqaerbfbepa--uzaenearcl--jmbbphkzrwieet'
index = hash(open('f.png').read())%99 * 2
print encoded[index : index+2]

Membangun string yang disandikan

Untuk membangun string yang disandikan, saya menggunakan fungsi untuk membaca file flag sebagai string, menghasilkan hash dari string, dan mengurangi hash ke sejumlah hash buckets:

def encode(buckets):
    lookup = {}
    for fn in os.listdir('flags'):
        name = fn[:2]
        signature = hash(open('flags/'+fn).read()) % buckets
        lookup[signature] = lookup.get(signature, '')+name
    return lookup

untuk mengembalikan kamus negara yang cocok dengan setiap tanda tangan, lalu gunakan beberapa kode untuk mengonversi kamus menjadi string pencarian:

encoded = ''.join(lookup.get(v, '--')[:2] for v in range(buckets))

Saya perlu bereksperimen sedikit dengan nilai buckets memberikan hasil terbaik.

Ksatria Logika
sumber
Apakah ini hanya mengambil warna rata-rata dari bendera?
Ashwin Gupta
@AshwinGupta, program membaca dalam file kemudian mengambil hash. Nomor hash besar ini direduksi menjadi indeks dalam daftar string dengan menggunakan operator modulo.
Logic Knight
1
Tidak yakin apakah itu akan membantu, tetapi Anda dapat melakukannya print'...'[...:][:2]. Juga, mungkin tabel pencarian dengan >>dan &untuk beberapa kompresi dasar?
Sp3000
@ Sp3000, ide indeks ganda terlihat menarik tetapi saya tidak bisa melihat di mana akan menghemat byte di sini. Saya tidak mempertimbangkan fungsi manipulasi bit untuk kompresi, tetapi itu bisa menawarkan keuntungan. Hmmmm.
Logic Knight
1
Pengindeksan ganda menghemat 3 byte karena Anda tidak perlu menyimpan ke suatu variabel i, tetapi apakah Anda dapat menggunakan byte tambahan itu atau tidak adalah pertanyaan yang berbeda: P
Sp3000