En este desafío, debe encontrar un píxel específico dentro de una fotografía (tomada con una cámara real).
Se le pasa una tupla (R, G, B) y una imagen, y necesita devolver un punto (x, y) dentro de la imagen que coincida con el color RGB dado . La imagen puede tener múltiples puntos que coinciden con el color; solo necesitas encontrar 1.
El desafío es que debes hacerlo mientras lees la menor cantidad de píxeles posible . Su puntaje será el número total de píxeles leídos en todos los casos de prueba.
Si lo desea, puede leer la imagen completa en una matriz de valores RGB, siempre que no realice ningún procesamiento en los píxeles. Permito esto únicamente para fines de eficiencia. Por ejemplo, en Python, list(Image.open("image_name+".jpg").convert("RGB").getdata())
está bien.
No se permiten ubicaciones de codificación fija. Su algoritmo debería funcionar bien para algo más que los casos de prueba enumerados a continuación. No está permitido guardar datos entre casos de prueba. Elegí valores RGB que aparecen con poca frecuencia ( <10
) en la imagen (en caso de que eso marque la diferencia en su algoritmo). Si está utilizando aleatoriedad en su algoritmo, establezca una semilla para que su puntaje sea constante.
Las imágenes se pueden encontrar en Github
Casos de prueba:
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)]
fuente
Respuestas:
Python, puntaje: 14,035,624
Lo primero es lo primero, aquí está el código:
y aquí hay un gif que muestra cómo el algoritmo examina los píxeles:
Entonces, esto es lo que está haciendo este código: la variable
heap
es una cola prioritaria de(x, y)
coordenadas en la imagen, ordenada por la distancia euclidiana del color en esa coordenada al color objetivo. Se inicializa con 10.200 puntos que se distribuyen uniformemente en toda la imagen.Con el montón inicializado, sacamos el punto con la distancia mínima al color objetivo. Si el color en ese punto tiene una distancia> 0, es decir, si el color en ese punto NO es el color objetivo, agregamos los 8 puntos circundantes
heap
. Para garantizar que un punto dado no se considere más de una vez, mantenemos la variablevisited
, que es un conjunto de todos los puntos que se han examinado hasta ahora.Ocasionalmente, en lugar de tomar directamente el punto con la distancia mínima de color, elegiremos al azar algún otro punto cercano la parte superior de la cola. Esto no es estrictamente necesario, pero en mis pruebas, elimina aproximadamente 1,000,000 de píxeles del puntaje total. Una vez que se encuentra el color de destino, simplemente devolvemos la longitud del
visited
conjunto.Al igual que @Karl Napf, ignoré los casos de prueba en los que el color especificado no estaba presente en la imagen. Puede encontrar un programa de controlador para ejecutar todos los casos de prueba en el repositorio de GitHub que creé para esta respuesta.
Aquí están los resultados de cada caso de prueba específico:
fuente
Python, puntuación: 396,250,646
Es una búsqueda recursiva de cuatro secciones. A veces encuentra el valor correcto en un pequeño porcentaje, a veces más del 75%. Aquí están los resultados para todos los casos de prueba:
pixels_visited, percentage, (position) (RGB at position) = (RGB searched)
fuente