Код-гольф - Реализация алгоритма выборки комбинаций
1,00
р.
Приём ответов завершён, всем спасибо за участие! Можете оставлять свои решения, но победители уже выбраны и пересчёта не будет.
Приветствую.
Задача: Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых будет равняться 10.
Подробнее: Диапазон чисел: 0 - 1000 включительно. Количество чисел во входящем массиве: 1 - 10 включительно. Уже выбранные числа могут использоваться неоднократно, но комбинации должны быть уникальны. --- Смена позиций не делает комбинацию уникальной, т. е. [1,9] и [9,1] не позволяются). --- При входных данных [5,5,2,3] можно сделать [5,5], [5,2,3]. Продолжительность конкурса: 14 дней. Обязательный формат метки ответа (для автоматического парсера в таблицу):
Определение победителя: Определяется по градации:
Реализация, состоящая из наименьшего количества символов. Реализация, получившая больше всего плюсов (общий рейтинг минус голоса против). Реализация, время первой редакции которой раньше.
Необходимо так же давать ссылку на один из онлайн-компиляторов с Вашим рабочим кодом. Тесты приветствуются. Настоятельно рекомендуется давать как конкурсную версию кода (минифицированную и/или с колдунствами), так и наглядное описание этого же кода. Всем интересно не только увидеть языковую магию, но и что-то почерпнуть для себя.
От одного участника допустимо несколько ответов, если они реализованы на разных языках. Но не более одного на язык
Все вопросы по деталям и/или разногласиям и/или трактовке условий, прошу обсуждать в комментариях к этому сообщению или в комнате чата по код-гольфу.
Итоги:
Стандартные 3 места + 1 за самое большое количество плюсов (общий рейтинг минус голоса против).
1 место: @PavelMayorov - Haskell, 42 символа. 2 место: @ArtemKonovalov - Scala, 69 символов. 3 место: @Mike - Perl, 78 символов.
Зрительские симпатии: @D-side (Ruby, 84) - 19 баллов.
Поздравления всем участникам, вы хорошо сражались. Особенно страсти накалились в самом конце, когда неожиданно было опубликовано решение обгоняющее лидера на 1 символ. Но судьба вернула всё обратно.
Хотелось бы отметить необычное для данного соревнования решение от пользователя @AlexanderGavrikov - 1437 символов! Это своеобразный рекорд, стоит отметить.
Таблица лидеров:
execute(581668) .cssload-container,.cssload-cube{width:97px height:97px transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative margin:23px 84px perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0 transform-origin:50% 100%}.cssload-half1{height:39px position:absolute animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px height:19px background:#ddd position:absolute}.cssload-s1{left:39px animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px transform-origin:50% 0}.cssload-s2{top:19px animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px top:19px transform-origin:100% 50% animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px top:39px transform-origin:0 50% animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1 transform:translateY(0) background:#ddd}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(-90deg) background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0 transform:rotateX(-179deg)}10%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1 background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0 transform:rotateX(-179deg)}20%,90%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0 transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1 transform:rotateX(0)}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(90deg) background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1 transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0 transform:rotateY(-179deg)}20%{opacity:1 background:#ddd transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg) opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0 transform:rotateY(179deg)}30%{opacity:1 transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg) background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1 transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}} .cssload-container,.cssload-cube{width:97px height:97px transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative margin:23px 84px perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0 transform-origin:50% 100%}.cssload-half1{height:39px position:absolute animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px height:19px background:#ddd position:absolute}.cssload-s1{left:39px animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px transform-origin:50% 0}.cssload-s2{top:19px animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px top:19px transform-origin:100% 50% animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px top:39px transform-origin:0 50% animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1 transform:translateY(0) background:#ddd}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(-90deg) background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0 transform:rotateX(-179deg)}10%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1 background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0 transform:rotateX(-179deg)}20%,90%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0 transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1 transform:rotateX(0)}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(90deg) background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1 transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0 transform:rotateY(-179deg)}20%{opacity:1 background:#ddd transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg) opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0 transform:rotateY(179deg)}30%{opacity:1 transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg) background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1 transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}} /* TODO: Fix it */ body { font-size: 1rem line-height: 1.5rem font-family: 'Open Sans', sans-serif background: #fff padding: 0 2rem } h1 { font-weight: 600 margin-bottom: 3rem text-align: center color: #212121 } #leadership { width: 100% margin: 1rem auto border-collapse: collapse box-shadow: 0 2px 7px rgba(0,0,0,0.2) background: #fafafa } #leadership td { padding: 1rem .5rem !important text-align: left font-weight: 500 transition: all .3s ease-in-out } #leadership tr:hover td{ background: #03a9f4 color: #fefefe } #leadership tr:hover td a { color: #fff } #leadership th { padding: 1.5rem .5rem !important color: #727272 text-align: left !important font-weight: 500 border-bottom: 1px solid #dcdcdc } #leadership a { text-decoration: none color: #212121 } #leadership a:hover { color: #03a9f4 } #leadership td:nth-of-type(1){ text-align: center color: #727272 font-size: .75rem } #leadership td:nth-of-type(2){ } #leadership td:nth-of-type(2) img { width: 34px border-radius: 50% } /* #leadership th:nth-of-type(1), #leadership th:nth-of-type(2){ border-bottom: none } */ #leadership th:nth-of-type(5), #leadership th:nth-of-type(6), #leadership th:nth-of-type(7), #leadership td:nth-of-type(5), #leadership td:nth-of-type(6), #leadership td:nth-of-type(7) { text-align: center !important }
Удачи всем!
Ответ
Ruby, 84 91
->a{(1..a.size).flat_map{|n|a.sort.combination(n).select{|c|c.reduce(:+)==10}.uniq}}
Первое решение, которое таки умещается в одну строку при просмотре с сайта!
Это литерал лямбды, который надо вызвать с массивом входных данных. Результатом будет массив из найденных комбинаций.
Ideone
В Ruby функция получения комбинаций элементов массива реализована прямо в классе Array, в стандартной библиотеке. Ой.
В остальном, решение максимально прямое и неплохо переводится на естественный язык:
(1..a.size) # Для диапазона от 1 до длины массива А .flat_map{ |n| # ...сконкатенировать для каждого N в нём следующее: a.sort # Из отсортированного массива А... .combination(n) # ...взять все комбинации длиной N элементов .select{ |c| # ...выбрав только те С из них, в которых: c.reduce(:+)==10} # Cвёртка С сложением равна 10. .uniq} # ...убрав повторения.
Поскольку порядок в комбинациях неважен, чтобы не получить дубликатов, массив можно отсортировать. Можно отсортировать и комбинации постфактум, но это медленнее и требует больше символов.
Приветствую.
Задача: Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых будет равняться 10.
Подробнее: Диапазон чисел: 0 - 1000 включительно. Количество чисел во входящем массиве: 1 - 10 включительно. Уже выбранные числа могут использоваться неоднократно, но комбинации должны быть уникальны. --- Смена позиций не делает комбинацию уникальной, т. е. [1,9] и [9,1] не позволяются). --- При входных данных [5,5,2,3] можно сделать [5,5], [5,2,3]. Продолжительность конкурса: 14 дней. Обязательный формат метки ответа (для автоматического парсера в таблицу):
Язык, КоличествоСимволов
Определение победителя: Определяется по градации:
Реализация, состоящая из наименьшего количества символов. Реализация, получившая больше всего плюсов (общий рейтинг минус голоса против). Реализация, время первой редакции которой раньше.
Необходимо так же давать ссылку на один из онлайн-компиляторов с Вашим рабочим кодом. Тесты приветствуются. Настоятельно рекомендуется давать как конкурсную версию кода (минифицированную и/или с колдунствами), так и наглядное описание этого же кода. Всем интересно не только увидеть языковую магию, но и что-то почерпнуть для себя.
От одного участника допустимо несколько ответов, если они реализованы на разных языках. Но не более одного на язык
Все вопросы по деталям и/или разногласиям и/или трактовке условий, прошу обсуждать в комментариях к этому сообщению или в комнате чата по код-гольфу.
Итоги:
Стандартные 3 места + 1 за самое большое количество плюсов (общий рейтинг минус голоса против).
1 место: @PavelMayorov - Haskell, 42 символа. 2 место: @ArtemKonovalov - Scala, 69 символов. 3 место: @Mike - Perl, 78 символов.
Зрительские симпатии: @D-side (Ruby, 84) - 19 баллов.
Поздравления всем участникам, вы хорошо сражались. Особенно страсти накалились в самом конце, когда неожиданно было опубликовано решение обгоняющее лидера на 1 символ. Но судьба вернула всё обратно.
Хотелось бы отметить необычное для данного соревнования решение от пользователя @AlexanderGavrikov - 1437 символов! Это своеобразный рекорд, стоит отметить.
Таблица лидеров:
execute(581668) .cssload-container,.cssload-cube{width:97px height:97px transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative margin:23px 84px perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0 transform-origin:50% 100%}.cssload-half1{height:39px position:absolute animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px height:19px background:#ddd position:absolute}.cssload-s1{left:39px animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px transform-origin:50% 0}.cssload-s2{top:19px animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px top:19px transform-origin:100% 50% animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px top:39px transform-origin:0 50% animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1 transform:translateY(0) background:#ddd}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(-90deg) background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0 transform:rotateX(-179deg)}10%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1 background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0 transform:rotateX(-179deg)}20%,90%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0 transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1 transform:rotateX(0)}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(90deg) background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1 transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0 transform:rotateY(-179deg)}20%{opacity:1 background:#ddd transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg) opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0 transform:rotateY(179deg)}30%{opacity:1 transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg) background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1 transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}} .cssload-container,.cssload-cube{width:97px height:97px transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative margin:23px 84px perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0 transform-origin:50% 100%}.cssload-half1{height:39px position:absolute animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px height:19px background:#ddd position:absolute}.cssload-s1{left:39px animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px transform-origin:50% 0}.cssload-s2{top:19px animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px top:19px transform-origin:100% 50% animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px top:39px transform-origin:0 50% animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1 transform:translateY(0) background:#ddd}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(-90deg) background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0 transform:rotateX(-179deg)}10%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1 background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0 transform:rotateX(-179deg)}20%,90%{opacity:1 transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0 transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1 transform:rotateX(0)}40%{transform:rotateX(0) background:#ddd}50%{transform:rotateX(90deg) background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1 transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0 transform:rotateY(-179deg)}20%{opacity:1 background:#ddd transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg) opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0 transform:rotateY(179deg)}30%{opacity:1 transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg) background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1 transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}} /* TODO: Fix it */ body { font-size: 1rem line-height: 1.5rem font-family: 'Open Sans', sans-serif background: #fff padding: 0 2rem } h1 { font-weight: 600 margin-bottom: 3rem text-align: center color: #212121 } #leadership { width: 100% margin: 1rem auto border-collapse: collapse box-shadow: 0 2px 7px rgba(0,0,0,0.2) background: #fafafa } #leadership td { padding: 1rem .5rem !important text-align: left font-weight: 500 transition: all .3s ease-in-out } #leadership tr:hover td{ background: #03a9f4 color: #fefefe } #leadership tr:hover td a { color: #fff } #leadership th { padding: 1.5rem .5rem !important color: #727272 text-align: left !important font-weight: 500 border-bottom: 1px solid #dcdcdc } #leadership a { text-decoration: none color: #212121 } #leadership a:hover { color: #03a9f4 } #leadership td:nth-of-type(1){ text-align: center color: #727272 font-size: .75rem } #leadership td:nth-of-type(2){ } #leadership td:nth-of-type(2) img { width: 34px border-radius: 50% } /* #leadership th:nth-of-type(1), #leadership th:nth-of-type(2){ border-bottom: none } */ #leadership th:nth-of-type(5), #leadership th:nth-of-type(6), #leadership th:nth-of-type(7), #leadership td:nth-of-type(5), #leadership td:nth-of-type(6), #leadership td:nth-of-type(7) { text-align: center !important }
Удачи всем!
Ответ
Ruby, 84 91
->a{(1..a.size).flat_map{|n|a.sort.combination(n).select{|c|c.reduce(:+)==10}.uniq}}
Первое решение, которое таки умещается в одну строку при просмотре с сайта!
Это литерал лямбды, который надо вызвать с массивом входных данных. Результатом будет массив из найденных комбинаций.
Ideone
В Ruby функция получения комбинаций элементов массива реализована прямо в классе Array, в стандартной библиотеке. Ой.
В остальном, решение максимально прямое и неплохо переводится на естественный язык:
(1..a.size) # Для диапазона от 1 до длины массива А .flat_map{ |n| # ...сконкатенировать для каждого N в нём следующее: a.sort # Из отсортированного массива А... .combination(n) # ...взять все комбинации длиной N элементов .select{ |c| # ...выбрав только те С из них, в которых: c.reduce(:+)==10} # Cвёртка С сложением равна 10. .uniq} # ...убрав повторения.
Поскольку порядок в комбинациях неважен, чтобы не получить дубликатов, массив можно отсортировать. Можно отсортировать и комбинации постфактум, но это медленнее и требует больше символов.
