Dalam tantangan ini, Anda perlu menemukan piksel tertentu dalam sebuah foto (diambil dengan kamera asli).
Anda memberikan tupel (R, G, B) dan gambar, dan Anda harus mengembalikan titik (x, y) di dalam gambar yang cocok dengan warna RGB yang diberikan . Gambar mungkin memiliki banyak titik yang cocok dengan warna; Anda hanya perlu menemukan 1.
The Tantangan adalah bahwa Anda perlu untuk melakukannya saat membaca sebagai beberapa piksel mungkin . Skor Anda akan menjadi jumlah total piksel yang dibaca di semua kasus uji.
Jika diinginkan, Anda dapat membaca seluruh gambar menjadi array nilai RGB, selama Anda tidak melakukan pemrosesan pada piksel. Saya mengizinkan ini murni untuk tujuan efisiensi. Misalnya, dalam Python, list(Image.open("image_name+".jpg").convert("RGB").getdata())
tidak apa-apa.
Lokasi hardcoding tidak diperbolehkan. Algoritme Anda harus bekerja dengan baik untuk lebih dari sekedar test case yang tercantum di bawah ini. Anda tidak diizinkan untuk menyimpan data di antara kasus uji. Saya telah memilih nilai RGB yang jarang muncul ( <10
) pada gambar (dalam kasus yang membuat perbedaan untuk algoritma Anda). Jika Anda menggunakan keacakan dalam algoritme Anda, silakan tetapkan seed, sehingga skor Anda konstan.
Gambar dapat ditemukan di Github
Kasus uji:
image_name:
(r, g, b) [all possible answers]
barn:
(143,91,33) [(887,1096),(2226,1397),(2007,1402),(2161,1508),(1187,1702)]
(53,35,59) [(1999,1260)]
(20,24,27) [(1328,1087),(154,1271)]
(167,148,176) [(1748,1204)]
(137,50,7) [(596,1498)]
(116,95,94) [(1340,1123)]
(72,49,59) [(1344,857),(1345,858),(1380,926),(1405,974),(1480,1117)]
(211,163,175) [(1963,745)]
(30,20,0) [(1609,1462),(1133,1477),(1908,1632)]
(88,36,23) [(543,1494),(431,1575)]
daisy:
(21,57,91) [(1440,1935),(2832,2090),(2232,2130),(1877,2131),(1890,2132)]
(201,175,140) [(1537,1749),(2319,1757)]
(169,160,0) [(2124,759)]
(113,123,114) [(1012,994),(2134,1060),(1803,1183),(1119,1335)]
(225,226,231) [(3207,829),(3256,889),(3257,889),(1434,981),(2599,1118),(2656,1348),(2656,1351)]
(17,62,117) [(2514,3874),(2336,3885)]
(226,225,204) [(3209,812)]
(119,124,146) [(2151,974),(2194,1021),(2194,1022),(2202,1034),(2812,1500)]
(2,63,120) [(2165,3881),(2326,3882),(2330,3882),(2228,3887)]
(200,167,113) [(1453,1759)]
dandelion:
(55,2,46) [(667,825),(668,825)]
(95,37,33) [(1637,1721),(1625,1724),(1405,1753),(2026,2276),(2016,2298)]
(27,41,50) [(1267,126),(424,519),(2703,1323),(1804,3466)]
(58,92,129) [(2213,3274)]
(136,159,105) [(1300,2363),(2123,2645),(1429,3428),(1430,3432),(1417,3467),(1393,3490),(1958,3493)]
(152,174,63) [(2256,2556)]
(78,49,19) [(2128,2836)]
(217,178,205) [(2736,3531)]
(69,95,130) [(870,305),(493,460),(2777,1085),(2791,1292),(2634,3100)]
(150,171,174) [(2816,1201),(2724,2669),(1180,2706),(1470,3215),(1471,3215)]
gerbera:
(218,186,171) [(4282,1342)]
(180,153,40) [(4596,1634),(4369,1682),(4390,1708),(4367,1750)]
(201,179,119) [(4282,1876),(4479,1928)]
(116,112,149) [(5884,252),(4168,371),(4169,372),(4164,384),(5742,576)]
(222,176,65) [(4232,1548)]
(108,129,156) [(5341,3574),(5339,3595),(5302,3734)]
(125,99,48) [(4548,1825),(4136,1932),(5054,2013),(5058,2023),(5058,2035),(5055,2050),(5031,2073)]
(170,149,32) [(4461,1630),(4520,1640)]
(156,185,203) [(3809,108)]
(103,67,17) [(4844,1790)]
hot-air:
(48,21,36) [(1992,1029),(2005,1030),(2015,1034),(2018,1036)]
(104,65,36) [(3173,1890),(3163,1893)]
(169,89,62) [(4181,931),(4210,938),(4330,1046),(4171,1056),(3117,1814)]
(68,59,60) [(1872,220),(1874,220),(1878,220),(1696,225),(3785,429)]
(198,96,74) [(4352,1057)]
(136,43,53) [(1700,931)]
(82,42,32) [(4556,961),(4559,973),(4563,989),(4563,990),(4441,1004),(4387,1126),(4378,1128)]
(192,132,72) [(1399,900),(3105,1822),(3104,1824),(3105,1824),(3107,1826),(3107,1827),(3104,1839),(3119,1852)]
(146,21,63) [(1716,993)]
(125,64,36) [(4332,937)]
in-input:
(204,90,1) [(1526,1997),(1385,2145),(4780,2807),(4788,3414)]
(227,163,53) [(1467,1739),(2414,1925),(2441,2198),(134,2446)]
(196,179,135) [(3770,2740),(1110,3012),(3909,3216),(1409,3263),(571,3405)]
(208,59,27) [(1134,1980),(4518,2108),(4515,2142)]
(149,70,1) [(4499,1790),(2416,2042),(1338,2150),(3731,2408),(3722,2409),(4400,3618)]
(168,3,7) [(987,402),(951,432),(1790,1213),(1790,1214),(1848,1217),(4218,1840),(4344,1870),(1511,1898)]
(218,118,4) [(3857,1701),(1442,1980),(1411,2156),(25,2606)]
(127,153,4) [(3710,2813)]
(224,230,246) [(2086,160),(2761,222),(4482,1442)]
(213,127,66) [(4601,1860),(4515,2527),(4757,2863)]
klatschmohn:
(170,133,19) [(1202,2274),(1202,2275),(957,2493),(1034,2633),(3740,3389),(3740,3391),(3683,3439)]
(162,92,4) [(489,2854)]
(159,175,104) [(3095,2475),(3098,2481)]
(199,139,43) [(1956,3055)]
(171,169,170) [(3669,1487),(3674,1490),(3701,1507)]
(184,115,58) [(1958,2404)]
(228,169,5) [(1316,2336),(1317,2336)]
(179,165,43) [(3879,2380),(1842,2497),(1842,2498)]
(67,21,6) [(1959,2197),(2157,2317),(2158,2317),(2158,2318),(2116,2373)]
(213,100,106) [(1303,1816)]
tajinaste-rojo:
(243,56,99) [(1811,2876),(1668,4141),(2089,4518),(1981,4732),(1659,4778),(2221,5373),(1779,5598),(2210,5673),(2373,5860)]
(147,157,210) [(1835,1028),(1431,3358)]
(114,37,19) [(1792,3572),(1818,3592)]
(108,117,116) [(2772,4722),(1269,5672),(2512,5811),(2509,5830),(2186,5842),(2186,5846),(2190,5851),(2211,5884)]
(214,197,93) [(1653,4386)]
(163,102,101) [(2226,2832),(2213,3683),(1894,4091),(1875,4117)]
(192,192,164) [(2175,2962),(2206,3667),(2315,3858),(1561,3977),(3039,5037),(3201,5641)]
(92,118,45) [(1881,1704),(1983,1877),(2254,2126),(3753,5862),(3766,5883)]
(145,180,173) [(1826,1585)]
(181,124,105) [(1969,3892)]
turret-arch:
(116,70,36) [(384,648),(516,669)]
(121,115,119) [(2419,958)]
(183,222,237) [(172,601),(183,601),(110,611),(111,617)]
(237,136,82) [(2020,282),(676,383),(748,406),(854,482),(638,497),(647,661),(1069,838),(1809,895),(1823,911)]
(193,199,215) [(1567,919),(1793,1047)]
(33,30,25) [(1307,861),(309,885),(1995,895),(504,1232),(2417,1494)]
(17,23,39) [(1745,1033),(788,1090),(967,1250)]
(192,139,95) [(1445,1337)]
(176,125,98) [(1197,1030)]
(178,83,0) [(2378,1136)]
water-lilies:
(86,140,80) [(2322,2855),(4542,3005),(4540,3006),(4577,3019)]
(218,124,174) [(1910,2457)]
(191,77,50) [(2076,1588)]
(197,211,186) [(4402,1894)]
(236,199,181) [(2154,1836)]
(253,242,162) [(1653,1430)]
(114,111,92) [(1936,2499)]
(111,93,27) [(2301,2423),(2127,2592),(2137,2717),(2147,2717)]
(139,92,102) [(1284,2243),(1297,2258)]
(199,157,117) [(3096,993)]
sumber
Jawaban:
Python, skor: 14.035.624
Hal pertama yang pertama, inilah kodenya:
dan inilah gif yang menunjukkan bagaimana algoritma memeriksa piksel:
Jadi, inilah yang dilakukan kode ini: Variabel
heap
adalah antrian prioritas dari(x, y)
koordinat dalam gambar, diurutkan berdasarkan jarak Euclidean warna pada yang mengkoordinasikan dengan warna sasaran. Ini akan diinisialisasi dengan 10.200 poin yang didistribusikan secara merata di seluruh gambar.Dengan heap yang diinisialisasi, kita kemudian muncul dari titik dengan jarak minimum ke warna target. Jika warna pada titik itu memiliki jarak> 0, artinya, jika warna pada titik itu BUKAN warna target, kita tambahkan 8 titik di sekitarnya dari padanya
heap
. Untuk memastikan bahwa suatu titik tidak dianggap lebih dari satu kali, kami mempertahankan variabelvisited
, yang merupakan kumpulan dari semua poin yang telah diperiksa sejauh ini.Terkadang, alih-alih langsung mengambil titik dengan jarak warna minimum, kami akan secara acak memilih titik lain dari dekat bagian atas antrian. Ini tidak sepenuhnya diperlukan, tetapi dalam pengujian saya, ini mengurangi sekitar 1.000.000 piksel dari total skor. Setelah warna target ditemukan, kami cukup mengembalikan panjang
visited
set.Seperti @Karl Napf, saya mengabaikan kasus uji di mana warna yang ditentukan tidak ada dalam gambar. Anda dapat menemukan program driver untuk menjalankan semua kasus uji di repositori GitHub yang saya buat untuk jawaban ini.
Berikut adalah hasil dari setiap test case khusus:
sumber
Python, skor: 396.250.646
Ini adalah pencarian bagian empat rekursif. Terkadang ia menemukan nilai yang benar dalam beberapa persen, kadang-kadang lebih dari 75%. Berikut adalah hasil untuk semua testcases:
pixels_visited, percentage, (position) (RGB at position) = (RGB searched)
sumber