{"blocks":[{"type":"paragraph","data":{"text":"В этом выпуске рассмотрим классическую задачу, известную под названием «Золотая гора». На CheckiO её реализовали в этой задаче."}},{"type":"paragraph","data":{"text":"Представьте себе треугольник, составленный из чисел. Одно число расположено в вершине. Ниже размещено два числа, затем три, и так до нижней грани. Вы начинаете на вершине, и нужно спуститься к основанию треугольника. За каждый ход вы можете спуститься на один уровень и выбрать между двумя числами под текущей позицией. По ходу движения вы «собираете» и суммируете числа, которые проходите. Ваша цель — найти максимальную сумму, которую можно получить из различных маршрутов."}},{"type":"paragraph","data":{"text":"Рассмотрим различные методы решения."}},{"type":"header3","data":{"level":3,"text":"Рекурсия"}},{"type":"paragraph","data":{"text":"Первым делом в голову приходит мысль использовать рекурсию и просчитать все пути от вершины. Когда мы спускаемся на один уровень, то все доступные числа ниже образуют новый меньший треугольник, и можно запустить нашу функцию уже для нового подмножества и так пока не достигнем основания."}},{"type":"code","data":{"code":"def golden_pyramid(triangle, row=0, column=0, total=0):\r\n global count\r\n count += 1\r\n if row == len(triangle) - 1:\r\n return total + triangle[row][column]\r\n return max(golden_pyramid(triangle, row + 1, column, total + triangle[row][column]),\r\n golden_pyramid(triangle, row + 1, column + 1, total + triangle[row][column]))","language":"python lazy-code"}},{"type":"paragraph","data":{"text":"Как мы видим, на первом уровне мы запустим нашу функцию два раза, затем 4, 8, 16 раз и так далее. В итоге мы получим сложность алгоритма 2N и, например, для 100-уровневой пирамиды нам нужно будет уже где-то ≈1030 вызовов функции. Многовато."}},{"type":"image","data":{"file":{"id":5766,"url":"//media.tproger.ru/uploads/2015/05/golden-pyramid-recursive.png"},"alt":"","title":"","caption":"","stretched":false,"withBackground":false,"withBorder":false,"width":720,"height":339,"optimizedFile":{"original":"https://media.tproger.ru/uploads/2015/05/golden-pyramid-recursive.png","alt":"Золотая пирамида — задача про треугольник, составленный из чисел 1","dimensions":{"width":720,"height":339},"additionalSizes":{"srcSet":[{"url":"https://tproger.ru/signed_image/eww5MPRO2qfiCk6Cc1zxOtUuxMrOCBeGgNINAYSZKyY/rs:fill:720:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":720},{"url":"https://tproger.ru/signed_image/oLMwaUn3gX77zkh6EuUue3owir-VZD27BABpajlmLOg/rs:fill:1440:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":1440},{"url":"https://tproger.ru/signed_image/GLk7MhSWNq11fNEI25i29kb-fp72zWFqhO5ifq5e-54/rs:fill:686:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":686},{"url":"https://tproger.ru/signed_image/uUIjF3HuwWHKvceTLQEvNDyis824WkWaKZRg99uV938/rs:fill:1372:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":1372},{"url":"https://tproger.ru/signed_image/TcVNqTE1zb3P52RlySBLnFVfkLzJlU3AAPiK1htP5zo/rs:fill:636:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":636},{"url":"https://tproger.ru/signed_image/IzcUcsUDRjaLLiqsjcw8huBDD0nBaRUUME3g3JOu9uY/rs:fill:1272:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":1272},{"url":"https://tproger.ru/signed_image/-TPYPGWUhHSyaolvK5UnPHEF6McSNfTMszNxCU1W2Ik/rs:fill:466:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":466},{"url":"https://tproger.ru/signed_image/pHx9iN3uFDF4EjcpWw8GL-25v3swl3704MTyVFDehhU/rs:fill:932:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1yZWN1cnNpdmUucG5n","dpr":1,"width":932}],"sizes":[{"media":"(min-width: 1441px)","size":"720px"},{"media":"(min-width: 1281px)","size":"686px"},{"media":"(min-width: 1281px)","size":"720px"},{"media":"(min-width: 961px)","size":"720px"},{"media":"(min-width: 671px)","size":"636px"},{"media":"(min-width: 500px)","size":"466px"}]}}}},{"type":"header3","data":{"level":3,"text":"Динамическое программирование"}},{"type":"paragraph","data":{"text":"Что если попробовать использовать принцип динамического программирования и разбить нашу проблему на множество мелких подзадач, результаты которых мы затем аккумулируем. Попробуйте взглянуть на треугольник вверх ногами. А теперь на второй уровень (то есть предпоследний от основания). Для каждой ячейки мы можем решить, каким будет лучший выбор в наших маленьких трёхэлементных треугольничках. Выбираем лучший, суммируем с рассматриваемой ячейкой и записываем результат. Таким образом, мы получили наш треугольник, но на один уровень ниже. Повторяем данную операцию снова и снова. В результате нам нужно (N-1)+(N-2)+…2+1 операций и сложность алгоритма равна N2."}},{"type":"code","data":{"code":"def golden_pyramid_d(triangle):\r\n tr = [row[:] for row in triangle] # copy\r\n for i in range(len(tr) - 2, -1, -1):\r\n for j in range(i + 1):\r\n tr[i][j] += max(tr[i + 1][j], tr[i + 1][j + 1])\r\n return tr[0][0]","language":"python lazy-code"}},{"type":"image","data":{"file":{"id":5767,"url":"//media.tproger.ru/uploads/2015/05/golden-pyramid-dynamic.png"},"alt":"","title":"","caption":"","stretched":false,"withBackground":false,"withBorder":false,"width":720,"height":485,"optimizedFile":{"original":"https://media.tproger.ru/uploads/2015/05/golden-pyramid-dynamic.png","alt":"Золотая пирамида — задача про треугольник, составленный из чисел 2","dimensions":{"width":720,"height":485},"additionalSizes":{"srcSet":[{"url":"https://tproger.ru/signed_image/ICKEBtb9b_5vUMr9V5cwl-OIN-TcgaTE5x5m8pTcmPI/rs:fill:720:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":720},{"url":"https://tproger.ru/signed_image/q5VMh-S_vpnAraqqMp3c2cbe5zol0RhCAs0jbwdzYRs/rs:fill:1440:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":1440},{"url":"https://tproger.ru/signed_image/nJq7T7DjGyC7uKdEmPWlCrdLSc-50USCkOu70qcJUe0/rs:fill:686:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":686},{"url":"https://tproger.ru/signed_image/3UNUBsTrBQmkw1uKbU_LveYYT55WR2fKcQR_SeymvOU/rs:fill:1372:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":1372},{"url":"https://tproger.ru/signed_image/49MPfdzpjUKHCRsj3_ORI4dkDdcjLNBlCK9pS4OvD1I/rs:fill:636:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":636},{"url":"https://tproger.ru/signed_image/3OGaZVB2o3tRanMolxpYWnF0ffEbv7H4CsCZzVke1kg/rs:fill:1272:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":1272},{"url":"https://tproger.ru/signed_image/cVLPjAgKZojmiu3yUJeYMD-YKPt4xBpuRN3swJwxKgo/rs:fill:466:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":466},{"url":"https://tproger.ru/signed_image/JPxwa-Qo7CJlsbwG4i0BVG8R2KpmNcaQcplPmHLqw6g/rs:fill:932:0:true/cb:vimg_2/f:webp/aHR0cHM6Ly9tZWRpYS50cHJvZ2VyLnJ1L3VwbG9hZHMvMjAxNS8wNS9nb2xkZW4tcHlyYW1pZC1keW5hbWljLnBuZw=","dpr":1,"width":932}],"sizes":[{"media":"(min-width: 1441px)","size":"720px"},{"media":"(min-width: 1281px)","size":"686px"},{"media":"(min-width: 1281px)","size":"720px"},{"media":"(min-width: 961px)","size":"720px"},{"media":"(min-width: 671px)","size":"636px"},{"media":"(min-width: 500px)","size":"466px"}]}}}},{"type":"header3","data":{"level":3,"text":"Решения игроков CheckiO"}},{"type":"paragraph","data":{"text":"Пользователь gyahun_dash написал интересную реализацию описанного выше метода ДП в своем решении «DP». Он использовал reduce, чтобы проходить по парам строк, и map чтобы обработать каждую из них."}},{"type":"code","data":{"code":"from functools import reduce\r\n\r\ndef sum_triangle(top, left, right):\r\n return top + max(left, right)\r\n\r\ndef integrate(lowerline, upperline):\r\n return list(map(sum_triangle, upperline, lowerline, lowerline[1:]))\r\n\r\ndef count_gold(pyramid):\r\n return reduce(integrate, reversed(pyramid)).pop()","language":"python lazy-code"}},{"type":"paragraph","data":{"text":"Игрок evoynov использовал двоичные числа, чтобы перебрать все возможные маршруты, представленные как последовательность 1 и 0 в своем решении «Binaries». И это наглядный пример сложности алгоритма с рекурсией и перебором всех маршрутов."}},{"type":"code","data":{"code":"def count_gold(p):\r\n path = 1 << len(p) res = 0 while bin(path).count(\"1\") != len(p) + 1: s = ind = 0 for row in range(len(p)): ind += 1 if row > 0 and bin(path)[3:][row] == \"1\" else 0\r\n s += p[row][ind]\r\n res = max(res, s)\r\n path += 1\r\n return res","language":"python lazy-code"}},{"type":"paragraph","data":{"text":"И чтобы не было скучно, посмотрим на легкий мозгодробитель от пользователя nickie и его однострочник «Functional DP», который только формально состоит из двух строк. Конечно, это решение из категории «Творческих» («Creative»). Не думаю, что автор использует такое на боевом коде. А просто для так для веселья, почему бы и нет."}},{"type":"code","data":{"code":"ount_gold=lambda p:__import__(\"functools\").reduce(lambda D,r:[x+max(D[j],D[j+1])\r\nfor j,x in enumerate(r)],p[-2::-1],list(p[-1]))[0]","language":"python lazy-code"}},{"type":"paragraph","data":{"text":"Вот и всё на сегодня. Делитесь вашими идеями и мыслями."}},{"type":"separator","data":{"text":"***"}},{"type":"paragraph","data":{"text":"Спасибо CheckiO за интересную задачу."}},{"type":"paragraph","data":{"text":""}}]}

Ошибка в настройках сайта