Bei dieser Herausforderung müssen Sie ein bestimmtes Pixel in einem Foto finden (aufgenommen mit einer echten Kamera).
Sie erhalten ein (R, G, B) -Tupel und ein Bild und müssen einen Punkt (x, y) innerhalb des Bildes zurückgeben, der der angegebenen RGB-Farbe entspricht . Das Bild kann mehrere Punkte haben, die mit der Farbe übereinstimmen. Sie müssen nur 1 finden.
Die Herausforderung besteht darin, dass Sie dies tun müssen, während Sie so wenig Pixel wie möglich lesen . Ihre Punktzahl ist die Gesamtzahl der Pixel, die in allen Testfällen gelesen wurden.
Wenn Sie möchten, können Sie das gesamte Bild in eine Reihe von RGB-Werten einlesen, solange Sie keine Verarbeitung der Pixel vornehmen. Ich erlaube dies nur aus Effizienzgründen. In Python list(Image.open("image_name+".jpg").convert("RGB").getdata())
ist das beispielsweise in Ordnung.
Hardcoding-Speicherorte sind nicht zulässig. Ihr Algorithmus sollte für mehr als nur die unten aufgeführten Testfälle gut funktionieren. Sie dürfen keine Daten zwischen Testfällen speichern. Ich habe RGB-Werte ausgewählt, die selten ( <10
) im Bild erscheinen (falls dies einen Unterschied für Ihren Algorithmus darstellt). Wenn Sie in Ihrem Algorithmus Zufälligkeit verwenden, setzen Sie bitte einen Startwert, damit Ihre Punktzahl konstant ist.
Bilder finden Sie auf Github
Testfälle:
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)]
quelle
Antworten:
Python, Kerbe: 14,035,624
Das erste ist das erste, hier ist der Code:
Und hier ist ein GIF, das zeigt, wie der Algorithmus Pixel untersucht:
Also, hier ist was dieser Code tut: Die Variable
heap
ist eine Prioritätswarteschlange von(x, y)
Koordinaten im Bild, sortiert nach dem euklidischen Abstand der Farbe an dieser Koordinate zur Zielfarbe. Es wird mit 10.200 Punkten initialisiert, die gleichmäßig über das gesamte Bild verteilt sind.Wenn der Heap initialisiert ist, entfernen wir den Punkt mit dem minimalen Abstand zur Zielfarbe. Wenn die Farbe an diesem Punkt einen Abstand> 0 hat, dh wenn die Farbe an diesem Punkt NICHT die Zielfarbe ist, addieren wir die 8 umgebenden Punkte von dieser zu
heap
. Um sicherzustellen, dass ein bestimmter Punkt nicht mehr als einmal berücksichtigt wird, pflegen wir die Variablevisited
, die eine Menge aller bisher untersuchten Punkte ist.Anstatt den Punkt mit dem minimalen Farbabstand direkt zu nehmen, wählen wir gelegentlich zufällig einen anderen Punkt in der Nähe des oberen Bereichs der Warteschlange aus. Dies ist nicht unbedingt erforderlich, aber in meinen Tests werden ungefähr 1.000.000 Pixel von der Gesamtpunktzahl entfernt. Sobald die Zielfarbe gefunden ist, geben wir einfach die Länge des
visited
Sets zurück.Wie bei Karl Napf habe ich die Testfälle ignoriert, in denen die angegebene Farbe nicht im Bild vorhanden war. Im GitHub-Repository, das ich für diese Antwort erstellt habe, finden Sie ein Treiberprogramm, mit dem Sie alle Testfälle ausführen können .
Hier sind die Ergebnisse der einzelnen Testfälle:
quelle
Python, Kerbe: 396.250.646
Es ist eine rekursive Suche nach vier Abschnitten. Manchmal findet es den richtigen Wert in wenigen Prozent, manchmal über 75%. Hier sind die Ergebnisse für alle Testfälle:
pixels_visited, percentage, (position) (RGB at position) = (RGB searched)
quelle