Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Write a full program with a source code of 256 bytes or less that looks at an image of a flag and determines what country that flag is from. A zip file containing the 196 different flags in the challenge can be downloaded from here. Source: [Flagpedia]. These 196 flag images are the only inputs your program has to handle.

Your program will take no input. The flag image will be in the same directory as your program and named "f.png". Your program will open this file, identify it, and print the two letter abbreviation for that country. If you use a language that can't open files, it's also acceptable to run your program as ./program < f.png.

Each flag file is named the same as the expected output. All output above 2 letters will be ignored.

Here is a list of all the outputs/filenames:

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, 

Scoring

Here is a short python script that I will use to score each submission.

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

Your score is the total number of flags correctly identified. In case of a tie, the earlier submission wins.

Rules

  • For my testing convenience, any language with a freely available interpreter/compiler for Windows 10 or Ubuntu can be used.

  • Image processing libraries are allowed, but any builtins related to flags or countries are not allowed. (cough Mathematica cough)

  • Please provide the full command needed to run your program along with links to any necessary libraries.

  • Submissions may not interact with any file except "f.png".

  • I don't have any hard time-limit on submissions, but please keep it relatively quick. I don't want the scoring script to take hours.

share|improve this question
4  
The byte limit is really low. Just storing the 196 two-letters codes uncompressed requires 392 bytes – edc65 Mar 26 at 22:48
2  
@edc65 The point is that you're only going to get a small number of the flags. – isaacg Mar 26 at 23:14
1  
@edc65 I intentional picked a number that would make a perfect score of 196 basically impossible. It's more about compression of recognizing images then codegolf. – Dr Green Eggs and Iron Man Mar 26 at 23:18
    
Just double checking - can we only use the ./program < f.png option if the language has no way of reading files, or can we also use it even if the language can read files? (Apparently CJam can read from files, which I didn't know) – Sp3000 Mar 27 at 17:22
    
These 196 flag images are the only inputs your program has to handle then you say Your program will take no input. Does that mean that the one file f.png will be one of the those 196. So the program cannot reference those zipped files? Just f.png – Matt Mar 27 at 17:25
up vote 11 down vote accepted

CJam, 139 141

There's a lot of unprintables in the code, so here's the xxd hexdump:

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/=

This is exactly 256 bytes, with the program doing:

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

Run the program with the command

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

Thanks to @Dennis for help with getting this submission working.

share|improve this answer
    
I'm amazed anyone got this many. 139/196 = 70.9%.You scraped an A grade! – Level River St Mar 27 at 12:07
    
Could you make the binary dump an xxd -r-reversible one? Cygwin should have xxd – cat Mar 27 at 13:45
1  
@tac Had to poke around a bit, but I didn't realise Cygwin did have it - I just had to select it manually for installation. I'll update it when I next update the answer. – Sp3000 Mar 27 at 14:34
    
I tried using the same technique as for Morse code, but the best I've been able to get is 129 flags, and I haven't even checked whether that fits in the 256-byte limit. Well done for finding such a good hash. – Peter Taylor Apr 1 at 15:23

Python 2, Score = 68 89

This solution uses the hash of the flag image file to create an index into a list of the country abbreviations. If more than one flag hashed to an index, only the first abbreviation will be returned (so it will fail some of those tests with more than one country in a hash bucket). This algorithm does however guarantee one correct answer for every non-empty hash bucket.

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

This program is 247 characters.

A more readable version:

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]

Building the encoded string

To build the encoded string, I use a function to read in the flag files as strings, generate a hash from the string, and reduce the hash to a limited number of 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

to return a dictionary of countries that match each signature, then use some code to convert the dictionary into a lookup string:

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

I needed to experiment a bit with which values of buckets gives the best results.

share|improve this answer
    
Is this just taking the average color of the flag? – Ashwin Gupta Mar 27 at 5:27
    
@AshwinGupta, the program reads in the file then takes a hash of it. This large hash number is reduced to an index in a string list by using a modulo operator. – CarpetPython Mar 27 at 5:42
1  
Not sure if it'll help, but you can do print'...'[...:][:2]. Also, maybe a lookup table with >> and & for some basic compression? – Sp3000 Mar 27 at 5:57
    
@Sp3000, the double index idea looks interesting but I can't see where is would save any bytes here. I had not considered bit manipulation functions for compression, but that could offer an advantage. Hmmmm. – CarpetPython Mar 27 at 6:16
1  
Double indexing saves 3 bytes because you don't need to save to a variable i, but whether or not you can make use of those extra bytes is a different question :P – Sp3000 Mar 27 at 6:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.