Конкурсная задача от Intel

Предлагаю желающим попробовать себя в программировании решить следующую задачу (условие ниже). Выбор языка не ограничен.

Problem Description: Write a threaded code that finds an example of a prime array that has the maximum number of primes hidden within it for a given array size. The following three restrictions for constructing arrays and counting primes must be observed:
1. Multiple digit prime numbers can only be constructed by reading consecutive numbers from top to bottom (vertical) or left to right (horizontal and diagonal). In the 2×2 prime array example given above, this would disqualify 31, 37, and 97 from being counted in the total. The number 73 is counted since it is read diagonally from left to right.
2. Only the digits 1..9 are to be used.
3. The total number of instances of a given digit within an array can be no more than one greater than the number of times any other digit is included. For the 2×2 case, a digit cannot appear more than once. In a 3×3 case, the following example is not considered a legitimate instance since the ’1′ digit appears twice, which is two more times than ’8′ appears (zero times).
| 1 1 3 |
| 7 5 4 |
| 9 2 6 |
Besides finding one example with the maximum number of primes that can be found contained in the array, a count of the number of other array configurations that also have the same number of primes must be computed.
Input: Two numbers will be given on the command line of the application. These will correspond to the number of rows and columns, respectively, of the array to be constructed. The range of values for both row and column values will be 1 to 10, inclusive.
Output: Output will be to stdout and must include one example of an array of the given size that contains the maximum number of hidden primes, the number of primes found in the array, a list of the primes that can be found within the printed array, and the number of total array configurations that have this maximum number of primes.
Output Example (from input ’3 3′):
Example of the 3×3 case
8 2 3
4 5 7
6 1 9
20 primes are hidden in the array
{2 3 5 7 23 61 19 41 59 53 17 37 79 823 457 619 251 379 859 653 }
1 total array configurations share this maximum number of primes
Timing: The total time for execution of the application will be used for scoring. (For most accurate timing results, submission codes would include timing code to measure and print this time to stdout, otherwise an external stopwatch will be used.)

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

матрица 4×3, ответ совпадает с привиденным.
800 сек на ноутбуке core i5 2520M, 4 ядра
302.7 секунды на десктопе 3770 8 ядер
вечером выложу на гитхаб, буду в резюме показывать как ачивмент ))) заодно и послушаю отзывов от доу.

Здорово. Выложишь — кинь ссылку, помедитируем вместе :)

хочется красоту навести в коде, а то на доу гкода не уважают. Кстатит пробовал запускать для матрицы 4×4 на i7 в 8 потоков, и даже через 2а часа никакого ответа. Трейсы показали что перебор идет. Вы случайно не пробовали 4×4 ?

Для 4×4 нужно перебрать 5 триллионов матриц. Я запустил свою новую оптимизированную версию, но без подсчета простых чисел. Получилось вот что (Core i7-2630QM 2GHz, notebook):


Horizontal size: 4
Vertical size: 4
Execution time: 10399.6 sec.
Total number of matrices processed: 5884534656000; Skipped: 3269185920000

При этом подсчитаны матрицы, которые можно пропустить (Skipped) = правый нижний элемент четный или равен 5.

ЗЫ: Твой код получил, почсмотреть пока не было времени.

Я би дивився у бік реалізації методу гілок та меж. Більш менш очевидно, що в оптимальному розв’язку парні числа будуть сконцентровані ліворуч, непарні праворуч. Якщо, наприклад, у випадку 3×3 поставити у нижньому правому куті парну цифру, то ми відразу перекреслюємо шість можливостей сховати у матриці просте число.

Таким чином можна робити пошук у глибину, починаючи з правого нижнього кута з непарних чисел. На кожному кроці треба рахувати кількість зруйнованих потенційних схованок для простих чисел. Першим у переборі потрібно дивитися варіант, де це число найменше. Якщо число зруйнованих схованок перебільшило значення у оптимальному варіанті, то перебір в цій гілці можна припинити.

Якщо, наприклад, у випадку 3×3 поставити у нижньому правому куті парну цифру,

Цікава думка, насправді. Варто її сформулювати алгоритмічно...
Дякую!

Это для математиков. В математике ещё 100500 тонн подобного «счастья», только польза его масового изучения — сомнительна.

Давайте простой вопрос: сколько раз в работе вам пригодились знания о простых числах?

// Спойлер: в реальной жизни сходные задачи есть, когда в одно число или сущность входят несколько уникальных составляющих. Но программисты вместо простых чисел тупо используют структуры данных. Начиная от битовых полей и заканчивая ООП с инжекцией зависимостей.

Математика здесь лишь почва для оттачивания скилов оптимизации и распараллеливания вычислений. Ну и разминка для моска, немношко. Основное — оттачивание скилов

Но программисты вместо простых чисел тупо используют структуры данных.

До тех пор, пока не встает задача защиты данных. Там простые числа нужны вне зависимости, структура это или __int64

// Спойлер: тип double в определенном смысле тоже битовая структура данных, например. А в случае, если надо найти простое число порядка 100-200 бит длиной — это тоже будет структура.

Ещё раз — да, это знание полезно. Но оно полезно в единичных случаях. Защита данных — это системное программирование. Большинство сочтёт таких кодеров сочтёт законченными ботанами. Они могут не знать ни единого фреймворка из «маст хэв», и даже не владеть английским на минимальном уровне. Но при этом они САМИ авторы фреймворков, и зачастую никто кроме них в мире в той же самой области не разбирался.

К примеру, если ты хочешь сделать свою криптовалюту — то да, тебе нужна математика. Но почему-то криптовалюты очень долгое время не было. Хотя математика — была. А потом появились копии — и ничего, авторы уже не были такими уж математиками, и не решали задачки от Интела.

И совсем уж глупо — пытаться решить такую задачу на скорость. Ибо в реальной жизни цена бага может быть от миллиона и выше. Почему так: а его не скоро обнаружат, а когда найдут — он будет уже везде. И те кто найдут — не станут трепаться, а заэксплойтят его по полной.

И поверь, даже в простеньком геймдеве есть куда больше интересных задач, чем тупой анализ матриц. Особенно там, где приходится работать с поведенческими шаблонами людей, менять их восприятие мира.

Еще раз: оптимизация и распараллеливание вычислений. Вы утверждаете, что эти скилы не применимы в прикладном программировании?

Я утверждаю, что за этими словами стоит МНОГО РАЗНЫХ задач. Не бывает скилла «оптимизация». Равно как и распараллеливание вычислений — базируется на ЗНАНИИ ПРИРОДЫ этих вычислений, а не даётся каким-то отдельным фантастическим скиллом.

Если бы эти знания были отдельными — у меня было бы 2 кнопки: «оптимизировать» и «распараллелить». Осталось бы добавить третью «написать код блять» — и профит!

Конкретно по твоей задаче — я утверждаю, что прокачанный скилл будет неприменим к другим задачам с вероятностью >99,999% в течение ближайшего полугода. А потому — будет попросту ЗАБЫТ. Даже если предположить что он где-то полезен.

Кстати, это касается огромного пласта знаний, даваемых образовательными учреждениями: на словах всё красиво, пока не начать разбирать реальную полезность, применимость, и сохраняемость знаний. И мало кто из чиновников рискнёт это сделать — ведь вывод будет что мы добровольно выпиливаем детей из жизни, фактически заключая в клетку системы.

давая я угадаю, по специальности вы вообще ниразу не програмист и не айти. Вы пошли формошлепить потому что в этой отрасли легче было косить бабло и не нада было особо напрягаться. Рекурсии ? сложность алгоритмов ? — этого не нада, нада только знание фреймворков )))) впрочем я ничего не имею против таких подходов, сам встречаю на каждом шагу людей которые в чем то знают больше меня а в чем то я знаю больше их. но если вас не тянет заоптимизировать какой то алгоритм — то нада задумываться насколько времени вас хватит как девелопера, потому что это походе не то чем вам хочется заниматься и вы в этой отрасли только ради денег.

Не угадал. Ещё варианты?

Да чего тут гадать. Совершенно очевидно, что распараллеливанием задач ты никогда не занимался.

Совершенно очевидно
Как раз потому что занимался — и могу утверждать, что типовые задачи давно имеют типовые решения. А низкоуровневые — все задачи РАЗНЫЕ, и распараллеливание у них РАЗНОЕ. Потому что разные узкие места, разный ресурс в наличии, разные объёмы и разные требования.

Даже простая с виду задача оптимизации трафика в IP-канале через QoS — и та не имеет одинакового решения, а лишь принципы. И когда тебе она попадётся — вспомни о своей задачке с Интела, и попробуй хоть что-нибудь применить.

Уважаемый, я уже 8 лет разрабатываю SIP PBX (3CX Ltd). Собственноручно написал ядро и еще пятОк сервисОв. Поверь, я знаю что такое распараллеливание и оптимизация. И благодаря этой задаче освоил, например, OpenMP технологию. Что оказалось очень полезным в моей работе.

Не понимаю что вы хотите кому доказать? Если кроме вас аббревиатуру

SIP PBX (3CX Ltd)
знает еще 2-3 человека, то это действительно частная задача/технология/что это на самом деле.

Вы находитесь в узкоспециализированной нише, вас в этом никто не упрекает и не говорит что это плохо и не пытается упрекнуть в незнании других узких ниш.

Только вот вы по непонятным причинам выглянув из своей ниши в реальный мир пытаетесь указать как низко пали все остальные, кто не знает вашей узкоспециализированной задачи, за что и получаете недоброжелательные комменты и троллинг.

Чем я задеваю Ваше самолюбие, никак не могу понять? Где я указывал «как низко пали все остальные»? Вы как-то в моем тексте умудряетесь видеть то, что я даже и не подразумевал.

Я предложил людям, которые заинтересовались этой задачей порешать её и устроить маленькое соревнование. Между собой. Это задевает Ваше ЧСВ?
Нет, вы прибежали сюда рассказать мне какой я заносчивый. Причем, по непонятным мне причинам, Вы уверены, что именно Вы наблюдаете реальный мир, а я — нет. Странно, но Ваше право так считать. Но и Вы не откажите мне в праве считать, что я таки в реальном мире живу.

Я уже специально начинаю комменты со слов «уважаемый» и т.п., и это не сарказм. Я понимаю, что попытка отстоять свою точку зрения будет воспринята как «недоброжелательные комменты», стараюсь смягчать. И это не помогает. Что мне еще сделать?

PS: 3CX SIP PBX — это готовый коммерческий софтверный продукт такой. Подробнее найдете в гугле, если надо, не хочу, чтобы восприняли это как пиар.

Да бестолковая задачка. Давали бы уже что то реально полезное. Кусок алгоритма для будущей разработки чего то там....

Специально для Вас у меня есть задача.
Даны числа g, M, y = g^x mod M. Нужно найти x. Размерность M порядка 1024 бит, для начала. Это — очень практическая задача из криптографии. Когда решите — я расскажу где применить.

тому кто решит эту задачу вы будете не нужны)

Товарищ выше просил «что-то реально полезное». Вы беретесь утверждать, что предложенная мной задача не имеет пользы? А если имеет — о чем Вы так глубокомысленно пытались мне сказать?

О том что человеку, который сможет решить эту задачу ваша помощь будет не нужна. В ваши дебаты с товарищем выше — я не вмешиваюсь — я только касательно примера полезной задачи. Ничего глубокомысленного я не хотел сказать и не сказал.

А я помощь и не предлагал, если Вы не заметили. Я предложил задачу.

Когда решите — я расскажу где применить.
— я воспринял это как предложение будущей помощи, но холиварить на эту тему не намерен, я не филолог, наверное ошибся, извините.

Ну якщо не знати, як можна використати прості числа, то ви їх й не будете використовувати. У мене, наприклад, прості числа виникали у алгоритмі визначення сили руки у покері.

До речі, маю ще подякувати Вам за ще один момент: нарешті я зміг сформулювати відповідь на питання «навіщо розв*язувти подібні задачі, адже вони не зустрічаются в роботі».
Так от, відповідь така, що програмісту в роботі перш за все потрібен мозок. Інформацію можна нагугліть, а мозок — ні. А подібні задачі як раз «відточують думки», як співав О. Скрипка :)

Чтобы нагуглить — как раз и нужно аналитическое мышление. Пронаблюдай за разными людьм, как они гуглят. И убедись, что разным людям гугл возвращает разные результаты :)

Единственное, чем простые числа полезны — они простые. То есть могут быть ИЗВЛЕЧЕНЫ из числа после операции умножения и любого их количества.
Именно поэтому могу утверждать, что структуры данных выполняют в точности ту же роль: сохранение информации ВНУТРИ, при выполнении ВНЕШНИХ операций над переменной. Фактически, это ключевая задача программирования — агрегация и извлечение данных, и как сделать это с наименьшими затратами.

Посему, будет лишним ТРЕНИРОВАТЬ и занимать долговременную память под ШАБЛОНЫ работы с простыми числами — большинству это никогда не понадобится. Есть тысячи других задач, в которых тренировка достигается более эффектно и гарантированно. Здесь — огромная вероятность пойти ложными путями и сформировать ЛОЖНЫЕ навыки, напичкав память огрызками неправильных алгоритмов.

Я соглашусь, что такие задачи полезны в подростковом возрасте. Когда формируется сам навык аналитического мышления, и ПРИСПОСОБЛЕНИЕ памяти к тому факту, что свыше 99.9999% информации вокруг есть ложь или бесполезность, и нужно умение формировать шаблоны восприятия чтобы
— видеть крупицу истины в потоке [детектировать шаблон по неполным данным],
— предсказывать вероятность, и ДЕЙСТВОВАТЬ на основе неполных данных + шаблона.

Без этого навыка формируется суеверное мышление — по природе нейросети мозга положительная обратная связь формирует память, но отрицательная связь её не в силах разрушить. Вернее, может — но нужна ОЧЕНЬ СИЛЬНАЯ отрицательная связь, например угроза жизни.

Логика — формирует навык разрушения ошибочных данных, не давая им сформировать постоянную память. Равно как и навык формирования условно-положительной связи, когда шаблон «может быть» полезен. Но оптимальное время формирования этого навыка — 10-12 лет. Хотя я лично имею опыт обучения 72-летнего человека логике. Но опять же, шаблоны под это должны быть сформированы ещё в детстве.

Кстати, кто не в курсе — базовая логика формируется в 4-6 месячном возрасте через понимание формы и размера. Дети, лишённые возможности её постичь — в дальнейшем становятся нелогичными, и это не зависит от пола. В дальнейшем они обучаются только в стрессовых ситуациях, а вот типичное «логическое» обучение — уже сложно для них. Потому что память не схватывает жёсткие шаблоны, позволяя широкую вариабельность. Этот процесс раздельный для зрительной памяти, звуковой, и кинестетики. Потому мы можем иметь идеальную зрительную память, но не иметь звуковой. Я уже молчу про логику на звуковой памяти, и насколько она отлична от логики зрительной.

Да, у «простых» вещей — сложное объяснение.

Единственное, чем простые числа полезны — они простые.

Геніально!

То есть могут быть ИЗВЛЕЧЕНЫ из числа после операции умножения и любого их количества.

Наприклад, модуль хеш функції бажано вибирати простим числом. Тільки де тут множення?

Посему, будет лишним ТРЕНИРОВАТЬ и занимать долговременную память под ШАБЛОНЫ работы с простыми числами — большинству это никогда не понадобится.

Взагалі, чому ти причепився так до простих чисел? Якщо брати конкурсне завдання, то там поки що ми використовуєм тільки те, що прості числа, за винятком тих, що складаються з одної цифри, не можуть закінчуватися на парну цифру або п’ятірку. Інформацію про цей факт можна знайти у арифметиці Пупкіна з картинками для початкової школи. Ніхто глибше в теорію чисел ще не копав.

Якщо брати матрицю 3×4, то всі прості числа можна прорахувати хоч повним перебором усіх чисел від 2 до 9999, перевіряючи кожен дільник. Якщо це робити один раз перед початком алгоритма, то це практично ніяк не вплине на його швидкість. 1 ms vs 2h якщо брати найкращу реалізацію :)

З іншого боку, мозок й так зберігає дуже багато інформації, яка ніяк не пов’язана з програмуванням взагалі. Це основні ідеї англійського початку, як шукати точку G методом найшвидшого спуску, це проходження Mass Effect, це багато-багато іншого. Наприклад, ви володієте інформацією про розвиток мозку малюка, але не даєте жодних визначень (базова логіка) та доказів. Чим прості числа гірше?

откуда инфа про 2 часа ? у меня матрицу 3×4 считает за 2000 секунд в одном потоке. Все простые числа загруженны в массив bool. Пытался распараллелить перетасовки матриц — но не работает как нада, потому что под параллельные вычисления нада логику переделывать.

Я не дуже пильно стежу за дискусією. У будь якому разі 1ms vs 2000s чи навіть 1ms vs 10s різниця на декілька порядків.

Моя порада буде дивитися у бік OpenCL, якщо ви плануєте розпаралелити виконання. Має добре лягти. А потім обчислення можна буде перенести на GPU. Плюс досвід у оптимізації перебірних задач на GPU.

это этого года задачка?

а что есть уже этого года задачка ?

я хз)) Но уже как бы 3/4 года прошло)

Если мне склероз не изменяет — 2010. Но потом конкурс больше не проводился. Или был еще в 2011, не помню уже.

Вот описание моего алгоритма перебора матриц. Приветствуются любые улучшения и альтернативные варианты.

Predefines:
— Xs,Ys — matrix sizes
— S = Xs*Ys — number of cells in matrix
— Q = [S/9] — number of times each digit will appear in matrix, minimum
— R = S%9 — number of digits that appear Q+1 times in matrix

For example, Xs=4, Ys=3 => S=12, Q=1, R=3
Starting sequence will be:
1 1 2 2 3 3 4 5 6 7 8 9

R digits (3) {1,2,3} appears Q+1 times (2)

1. Generate ’spread’:
— select R digits, in example above it will be {1,2,3}
— fill an array spread[1..9] with counts that define the number of times corresponding digit will appear in matrix
for example above it will be {2,2,2,1,1,1,1,1,1}

2. Init placement matrix ’places’, 9 rows, R columns:
— row [1..9] of the matrix represents places of corresponding digit, counting empty cells
i.e., initially, the sequence array is empty: x x x x x x x x x x x x
suppose row [1] has {2,5} in it, it comes to x x 1 x x 1 x x x x x x
now, suppose row [2] has {1,3}, it comes to x 2 1×2 1 x x x x x x, as it skips from counting cells that are occupied with 1’s already

— array ’length’[1..9] is filled along, each element represent the number of free cells for that digit left after
previous digits has been filled in sequence, starting with ’1′
in our example it will be:
length[1]=12 — no digits are filled yet
length[2]=10 — we have two 1’s, so two places are taken already
length[3]=8 — two 1’s, two 2’s out of 12 places
. . .
length[8]=2
length[9]=1 — only one place left for last digit

3. Generate matrix according to placement matrix

4. To get next matrix, change placement matrix, selecting all possible combinations starting from last digit
Example:
length[9]=1, so skip it
length[8]=2, places[8]={0}, so take next place: places[8]={1}
build sequence: 1 1 2 2 3 3 4 5 6 7×8 => 1 1 2 2 3 3 4 5 6 7 9 8
no more moves for ’8′, so next step is ’7′
length[7]=3, two possible moves
reset places[8]=places[9]={0}
move 1 => places[7] = {1}, gives 1 1 2 2 3 3 4 5 6×7 x
since places of 8 and 9 are reset, it gives 1 1 2 2 3 3 4 5 6 8 7 9
now moving higher digits, skipping 9, places[8]=1 gives 1 1 2 2 3 3 4 5 6×7 8 => 1 1 2 2 3 3 4 5 6 9 7 8
move 2 => places[7] = {2}, gives 1 1 2 2 3 3 4 5 6 x x 7
—//— 1 1 2 2 3 3 4 5 6 8 9 7
—//— 1 1 2 2 3 3 4 5 6 9 8 7
no more moves for 7, go to 6... etc

5. After all combinations are built, take next selection of R digits
for example, {1,2,4} {1,2,5} {1,2,6} ... {7,8,9}

and go to step 1

6. Stop after last selection has been processed.

рекомендую убрать пока решение, потому что никто над своим не будет думать )

В отличие от Интела — я денег за победу не предлагаю :)) так что рассчитываю на голый интерес.

Повторить мой вариант в более удачном исполнении — это тоже интересно, я отнюдь не считаю, что выжал максимум. Тогда у меня не было достаточно времени поразмыслить.

К тому же я уверен, что можно придумать более быстрый алгоритм. Возможно мой как раз покажет как делать не надо :)

вы типа задаете вектор мышления показав свой алгоритм. Я во время написания переписывал все раза 3, на некоторые мысли натыкаешься во время трейсов. Например поиск простых чисел длинной в 1 символ можна делать только когда проверяшь строки матрицы (слева направо), для всех остальных этапов типа сверху в низ (столбцы) и слева-вверх по диагонали от проверки чисел длинной в 1 символ можна отказаться. Еще пример для матрицы
123
456
789
если проверяется матрица слева-вверх по диагонали и доходит до нижней строки, (1,42,753) то она включает последнюю диагональную строку 753 и потом проверку матрицы снизу-вправо (753,86,9 ) можна начинать не с 0го столбца а с первого так как 753 уже проверенна раньше. Ну и т.д., тоесть пока не начнешь трейсить многие моменты не видны.

Похоже, мне удалось написать рекурсивный алгоритм генерации перестановок повторяющихся цифр. Осталось на пустые места расставлять все возможные размещения неповторяющихся цифр — и скорость генерации возрастет в разы.

я же вчера тебе его показал на питоне ))))

Я не очень понял что там было на питоне.
У меня сейчас практически мгновенно генерятся штуки вида

12345×6xxxxx
1234×56xxxxx
123×456xxxxx
12×3456xxxxx
. . .
xxxx1xx23456
xxxxx1×23456
xxxxxx123456

Теперь думаю, как это можно использовать :)))

И вот еще только что закончил функцию типа F(X) -> Y, где X = 0 .. N!-1, Y — неупорядоченная комбинация неповторяющихся цифр от 1 до N. Для N=6 такой результат:

654321xxx
564321xxx
546321xxx
543621xxx
. . .
123645xxx
123465xxx
123456xxx

у меня для матрицы 3×4, уникальная последовательность типа 112233456789 перебирается до вида 987654332211 за 5 секунд. В 5 секунд входит еще и построение возможных простых чисел для каждого набора. Вообще все возможные комбинации матриц для 3×4 строятся гдето за 300 секунд. Но когда я подключаю проверку сформированных из матрицы чисел на простоту, то 5 секунд удлиняется до 30 секунд а то и до минуты. Я уже даже тупо делал массив bool длинной 9999 для всех простых и для каждого предлагаемого N проверял какое значение у bool[N], если оно true то N — это простое. Но даже в таком случае (когда не нада считать является ли каждое N простым) все равно проход по одной последовательности занимает 30 сек. А если еще и записывать найденные простые для матрицы во временный массив то 5 секунд превращаются в 45 секунд )))) пока не смог это побороть.

Блин, события в Украине совсем выбили меня из колеи. Попробую продолжить попозже. Пока чую, что есть потенциал ускорить в 3-5 раз. Но как-то не до того.

такая же ситуация, вместо работы в основном читаю новости о вторжении россии. сегодня наконец посмотрел чего у меня все так тормозит, нашел место где тормоза, сам осилить не смог создал тему на доу dou.ua/...ms/topic/10824

Делюсь промежуточным результатом: перебор всех матриц 4×3 без поиска и подсчета простых чисел сейчас занимает 82 секнды. На той же машине полный оригинальный вариант работает 905 секунд.

что за машина ? у меня на i5 2520 кажись 42 секунды занимает, правда я не помню — возвращается что то из функции или нет. Потому что если ничего не возвращается то компилятор попросту отсечет перебор.

Проц — i7, компилятор ничего у меня не отсекает. Есть еще пространство для оптимизации. Распараллелено на восемь ядер.

матрица 4×3, 4 ядра i5 2520m, 15 секунд на перебор всех вариантов в 4 потока. с подсчетом простых чисел гдето 700 секунд. Только я еще не реализовал как запоминать матрицу с максимумом, просто возвращаю максимально найденное количество простых. я отказался от рекурсий для заполнения матриц и использую только std::next_permutation. Если про него сразу знать то задача очень упрощается.

я вчера переписал одну часть через permutation, оказалось есть такая штука. Осталось мне только распараллелить вычисления, потому что в одно ядро считает около 2000 секунд.

Подписаться на комментарии