Праздничный биатлон

    Programmers' dayС днем программиста, коллеги!

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

    Алгоритмы. Задача №1, разминочная


    Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка.

    Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4.
    Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.

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

    Алгоритмы. Задача №2, посложнее


    Руководство финансовой пирамиды решило присвоить числовой рейтинг каждому из участников пирамиды. Если участник до сих пор никого не привел в пирамиду, то его рейтинг равняется 1. Если у участника уже есть подчиненные участники, то его рейтинг равняется 1 + сумма рейтингов его прямых подчиненных.
    Задача: найти сумму рейтингов всех участников финансовой пирамиды.

    Исходные данные подаются в виде массива из n строк, где каждая строка содержит n символов. Каждый символ — либо '0', либо '1'.
    j-й символ i-й строки указывает на то, является ли участник под номером j прямым подчиненным участника i.
    j-й символ j-й строки всегда равен '0'. Дерево участников никогда не имеет циклов. Каждый участник всегда является прямым подчиненным максимум одного другого участника. У дерева участников всегда только один корневой участник.

    Пример исходных данных:

    "0110"
    "0000"
    "0001"
    "0000"

    Корневым элементом в данном случае является участник 0. У него двое подчиненных: участники 1 и 2. У 1 подчиненных нет, у 2 есть подчиненный участник 3.
    Рейтинг 3-го: 1.
    Рейтинг 1-го: 1.
    Рейтинг 2-го: 1 + 1 = 2.
    Рейтинг 0-го: 1 + 1 + 2 = 4.

    Результатом работы кода должна являться сумма рейтингов всех участников, в данном случае это: 1 + 1 + 2 + 4 = 8.

    SQL. Задача №1, попроще


    Дано: две (ненормализированные) таблицы:
    Categories(Id, Name)
    Books(Id, CategoryId, Name)

    В будущем вы, конечно же, хотите добавить третью таблицу-связку Book_Category, но пока что в таблице Books может существовать несколько записей с одинаковым значением поля Name, но разными CategoryId.

    Задача: написать запрос, который выбирает все книги, которые есть в категории с Id = 1, но которых нет в категории с Id = 2.
    Небольшое уточнение: СУБД, которую вы используете, не знает, что такое подзапросы :)

    SQL. Задача №2, посложнее


    Есть таблица Players(Id, Name, Score), где Score — количество очков игрока. Чем больше очков, тем выше место игрока в зачетной таблице.
    Задача: написать запрос, который выбирает игроков, занимающих (делящих) 3-е место.

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

    Пример данных:

    Players

    Как видно, 1-2 место делят Stepan и Svetlana, а 3-4 — Vladimir и Valentin, которых и должен вернуть запрос.

    Скрипт для создания таблицы и тестовых данных можно скачать.

    Напоследок


    Те, у кого нет аккаунта, могут слать решения мне на почту: dmitrii.shevchenko@gmail.com. Инвайтов не обещаю (нет их у меня), а вот в комментарии самые интересные решения выложу.

    Надеюсь, вам понравится :)
    Метки:
    Поделиться публикацией
    Комментарии 83
    • +1
      Спасибо, действительно понравилось! Только вот задачку с игроками не смог решить(
      • +1
        Мне кажется что 2я SQL задача неправильно поставлена:
        так как Stepan и Svetlana делят 1е место, Vladimir и Valentin 2е, а Ivan 3е.
        Если я не прав тогда, объясните мне что надо выводить если у 3х игроков будет 10, например.
        • +1
          Обычно в турнирах по, например, шахматам, используют именно подход, описанный мной в условии. И да, это реализоваь сложнее, чем выбор игроков с третим максимальным количеством очков.
          • +1
            Если у троих будет 10, то они делят с первого по третье место. Соответственно, для выборки по третьему месту нужно выводить всех троих.
            • +1
              Да несложная задача, решу на MySQL:
              select Name from `test` where score=(SELECT score FROM `test` ORDER BY Score desc limit 3,1)
              • +1
                Да уж. Задача «посложнее» на поверку оказалась попроще :) А я-то спросонья, когда ее придумывал, написал решение, заджоинив таблицу саму на себя.
                Кстати, такое же решение прислал мне на почту Алексей Масленников:

                SELECT * FROM `players` WHERE Score = (SELECT Score FROM `players` ORDER BY  Score DESC LIMIT 2,1)
                • +2
                  Хабрачитатель Konstantin Snegov прислал такое решение, но в синтаксисе T-SQL:

                  SELECT  TOP 1 WITH TIES 
                          p.*
                  FROM    #players AS p
                  WHERE   score IN (
                  SELECT  TOP 3
                          score
                  FROM    #players AS p
                  GROUP BY    score
                  ORDER BY    Score DESC )
                  ORDER BY Score ASC
          • +1
            Как-то так можно…
            with scores as(
                   select 1 id, 'Ivan' name, 8 score from dual union all
                   select 2,    'Stepan',   10       from dual union all
                   select 3,    'Irina',     3       from dual union all
                   select 4,    'Vasily',    7       from dual union all
                   select 5,    'Vladimir',  9       from dual union all
                   select 6,    'Svetlana', 10       from dual union all
                   select 7,    'Valentin',  9       from dual union all
                   select 8,    'Bla',       0       from dual 
                 )
            select name
                 , score
                 , dense_rank() over(order by score desc) as PLACE
            from scores
            order by score desc


            Stepan   10	1
            Svetlana 10	1
            Valentin  9	2
            Vladimir  9	2
            Ivan      8	3
            Vasily    7	4
            Irina     3	5
            Bla       0	6

            • +1
              промахнулся, предназначалось для #namespace.
            • +1
              Это решает чуть-чуть другую задачу. Я ответил по этому поводу предыдущему комментатору.
              • +1
                ага, вон как. Понял.
                • +1
                  Тогда вот так (если опять с условием задачи не протупил):

                  select *
                  from (
                    select name, score
                           -- минимальное место в группе (по очкам)
                         , min(place) keep(dense_rank first order by PLACE) over(partition by score) min_place
                         -- максимальное место в группе (по очкам)
                         , max(place) keep(dense_rank last order by PLACE) over(partition by score) max_place
                    from (
                      select name
                           , score
                           -- пронумеровываем результаты 
                           , row_number() over(order by score desc) as PLACE
                      from scores
                    )
                  )
                  -- желаемое место между минимальным и максимальным в группе
                  where 3 between min_place and max_place
              • +1
                Почему тогда уж сразу и не написать
                HAVING (dense_rank() over(order by score desc)) = 3
                ?
                Увы, сейчас доступа к какой-нибудь базе нет :)
              • +3
                А число разве не является своим подчислом? Равно как любое множество является своим подмножеством.

                Если делать так, как у вас (не является), то вот решение первой задачи.

                import Data.List
                 
                dividedBy :: Int -> String -> Bool
                dividedBy _ [] = False
                dividedBy n b = case read b of
                0 -> False
                -> n `mod` x == 0 && n /= x
                 
                dividers :: Int -> Int
                dividers n = length . filter (dividedBy n). subsequences . show $ n
                • +1
                  круто, а я и забыл про subsequences. Можно было всё сократить ещё на две строчки
                  • +1
                    Да, бывает, чего уж там. :)
                  • +1
                    Может быть, так и правда было бы логичнее. В любом случае, на решение задачи это не сильно влияет :)
                    Поздравляю с первым решением! А что это, простите, за язык такой?
                    • 0
                      Haskell.

                      Для полной работоспособности следует добавить функцию main:

                      main = putStrLn. show. dividers $ 101
                      • 0
                        > А что это, простите, за язык такой?

                        Позор, не узнать Haskell. :P
                        • +2
                          Вместо едкостей лучше бы решение на Lisp предоставили, — я помню, вы за этот язык можете кого угодно съесть.
                          • +1
                            (Надо чаще читать почту)

                            > я помню, вы за этот язык можете кого угодно съесть.

                            Нет, я не фанатик, просто считаю его (Common Lisp, в остальных новомодных лиспах вроде Clojure есть пара новых идей, но вырезаны почти все хорошие старые) лучшим языком для большинства задач. :] Есть никого не планирую.

                            > Вместо едкостей лучше бы решение на Lisp предоставили

                            Слишком поздно открыл топик о много прочитал готовых решений. Теперь всё что приходит в голову — построчные их переводы.

                            Впрочем, кое-что продемонстрировать можно.

                            Например, компайлер-макросы, позволяющие определять для своих функций способы оптимизации их вызова. Здесь примитивный вариант, но идея, думаю, ясна: sprunge.us/igBi?cl

                            Как нетрудно убедиться в SBCL с помощью DISASSEMBLE, последние две строчки при включённых оптимизациях заменяются на результат (в маш. коде для subseqs и t1 будет список и число соответственно). sprunge.us/ZPUR

                            Если же передать аргументом не константу или выключить оптимизации, то будет вызываться функция. sprunge.us/HeeY
                            • 0
                              Что ж, спасибо, интересно.
                      • 0
                        Решение второй задачи:

                        import Data.List
                         
                        treeData = [
                        "0110",
                        "0000",
                        "0001",
                        "0000"
                        ]
                         
                        employeeSubs = elemIndices '1'
                        employees = map employeeSubs treeData
                         
                        calcEmpl d n = foldr (\x -> (+) (calcEmpl d x)) 1 (!! n)
                        calcAll = map (calcEmpl employees) [0..(length employees) - 1]


                        Вызов calcAll выводит рейтинг для участников по порядку:

                        [4, 1, 2, 1]
                        • 0
                          Кстати, в задании ошибка, если у меня все правильно. У третьего должен быть рейтинг 2.
                          • 0
                            Забыл результат:

                            main = putStrLn. show. sum $ calcAll

                            (Печатает 8).
                          • +1
                            Неверно, попробуйте на 1919 — ваша программа выдает 5, хотя на самом деле ответ 2.
                            PS. Такая ошибка тут у многих
                            • +2
                              Хм, возможно, я не совсем ясно написал условие. Но в данном случае ответ действительно 4 (или 5, в зависимости от того, учитывается ли делимость на само себя), т.к. 1919 нацело делится на 1, 1, 19 и 19.
                              А условии специально приведен пример, где показывается, что каждый из повторяющихся множителей считается.
                              • 0
                                А, я пропустил этот момент :) Тогда ок
                                • +1
                                  Стыдно признавать, но таки вы правы — программа ошибочна! Правда, в другом. :) Если посмотреть, что выдает функция subsequences на число 1919, увидим нелицеприятное:

                                  ["",«1»,«9»,«19»,«1»,«11»,«91»,«191»,«9»,«19»,«99»,«199»,«19»,«119»,«919»,«1919»]

                                  Поясню справкой по функции:

                                  The subsequences function returns the list of all subsequences of the argument.

                                  subsequences «abc» == ["",«a»,«b»,«ab»,«c»,«ac»,«bc»,«abc»]


                                  То есть имеем лишнюю «19», которая вместе с 1, 19, 1, 19 составляет 5 элементов. Если добавить еще число как подчисло себя, то получится 6.

                                  Пока думаю, как это исправить. :)
                                  • +1
                                    А я как раз думал почему же 19 3 раза получилось в вашем примере (я заменял вывод длины списка на вывод самого списка) :)
                                    • +1
                                      Но все равно, автор топика говорит что по условию нужно считать повторки. Хотя subsequences все равно придется заменить.

                                      Кстати, я тоже искал такую функцию для перебора всех подстрок в питоновском itertools, и там её не оказалось :(
                            • +4
                              решение первой в лоб. Тормозное, но надеюсь не слишком длинное

                              subsets [] = [[]]
                              subsets (x:xs) = subsets xs ++ (map (x:) (subsets xs))

                              calculate :: Int -> [Int]
                              calculate n = (filter ((==0).mod n).map head.group.sort.map read.tail.init.subsets.show) n

                              main = (print.length.calculate) 1938

                              Кстати, у вас ошибка:
                              Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 13 и 38.

                              на самом деле 1,3,19,38.
                              • +2
                                Чуть чуть упростил, получился однострочничек. Причём только в виде комбинаций функций.

                                dividers = length.((.(filter (/=0).map read.tail.init.subsequences.show)) =<< filter.((0 ==).).mod)

                                Использовать
                                import Data.List
                                import Control.Monad.Instances
                                dividers = length.((.(filter (/=0).map read.tail.init.subsequences.show)) =<< filter.((0 ==).).mod)
                                main = print.dividers $ 1938


                                btw, язык — хаскель
                                • 0
                                  Я плохо понимаю этот ваш последний вариант. Он на число 1919 выдает 5, — и это, вроде бы, правильный результат, если учитывается число как подчисло самого себя. Если не учитывать, то должно быть 4. Не пойму, как сделано у вас среди этого мозголомного однострочника. :)

                                  Кстати, функция subsequences нам подложила свинью. См. мой прошлый комментарий. :)

                                  Первый ваш вариант выдает 2 на 1919, что неверно.

                                  В общем, если ваш второй вариант работает как надо (даже несмотря на свинью с subsequences), то в этом вы победили. :)
                                  • +1
                                    Неа, мой варинат не верен. Только сейчас понял.
                                    Дело в том, что subsequences не подходит для разбиения. Поскольку он строит множество всех подмножеств а нужно считать только включения.
                                    то есть в подчислах 1938 нет числа 13, которе даст subsequences.

                                    из-за этого в примере с 1919 число 19 вылезает 3 раза (первая еденица даст два числа, последняя давт ещё одно 19). такие дела.
                                    • +1
                                      В итоге пришлось сделать перебором вручную. Хотя явно менее красивый вариант
                                      dividers n = let d = (length.show) n
                                                   in length [ subNumer | a<-[1..d], b<-[0..a-1], a-b/=d, let subNumer = div (mod n (10^a)) (10^b), subNumer /= 0, mod n subNumer == 0]
                                      • +1
                                        Да, тут, конечно, красоты особо нет. Зато есть list comprehensions, что любопытно.
                                    • +1
                                      import Control.Applicative
                                      import Control.Monad.Instances
                                      import Data.List
                                      
                                      solve = length.tail.((filter.((==0).).mod)<*>(filter (>0).map (read .('0':)).(>>= tails).inits.show))
                                      
                                      main = readLn >>= print . solve
                                      
                                      
                                  • +4
                                    В условии первой задачи очепятка, не 13, а 19.
                                    Решение в лоб (C#, LinqPad):
                                    var n = 1938;
                                    var s = n.ToString();
                                    var l = s.Length;
                                    Enumerable.Range(0, l)
                                    .SelectMany(x => Enumerable.Range(1, l - x).Select(i => int.Parse(s.Substring(x, i))))
                                    .Where(i => i != n && n%i == 0)
                                    .Dump();
                                    • +2
                                      Будет деление на ноль для чисел вроде 101. Исправленный вариант:
                                      var n = 1938;
                                      var s = n.ToString();
                                      var l = s.Length;
                                      Enumerable.Range(0, l)
                                      .SelectMany(x => Enumerable.Range(1, l - x).Select(i => int.Parse(s.Substring(x, i))))
                                      .Where(i => i != 0 && i != n && n % i == 0)
                                      .Count();
                                      
                                    • +2
                                      Вторая задача в лоб, C#, LinqPad

                                      var src = new[] { «0110», «0000», «0001», «0000» };
                                      Func<int, int> getRating = null;
                                      getRating = index => src[index].OfType().Select((c, i) => c == '1'? getRating(i): 0).Sum() + 1;
                                      src.Select((s, i) => getRating(i)).Sum().Dump();
                                      • +3
                                        Парсер съел 'OfType<Char>()', fixed:

                                        var src = new[] { "0110", "0000", "0001", "0000" };
                                        Func<int, int> getRating = null;
                                        getRating = index => src[index].OfType<Char>().Select((c, i) => c == '1' ? getRating(i) : 0).Sum() + 1;
                                        src.Select((s, i) => getRating(i)).Sum().Dump();
                                        • +1
                                          Да, все правильно :) Интересный подход с Linq'ом.
                                      • +8
                                        1 задание:
                                        как я вижу никто не использует регулярные выражения для решения этой задачи, хе-хе, получайте:

                                        #!/usr/bin/env perl
                                        use common::sense;
                                        use re 'eval';

                                        my $n = 1938;
                                        my @to_check;

                                        for (1..length($n)-1) {
                                        $n =~ /.{$_}(?{ push @to_check,$& })(*FAIL)/;
                                        }

                                        say scalar grep { $n % $_ == 0 } @to_check;


                                        смысл всего вышенаписанного на Великом Языке Программирования Perl:
                                        в цикле for строка бьётся на субстроки регулярным выражением, причём, благодаря тому что нужное количество символов принудительно НЕ СОВПАДАЕТ, перебор идёт по несколько нужных символов не друг за другом, а со смещением в один символ
                                        и в конце каждое полученное значение проверяется на основном числе и выводиться количество делителей на которые число делится без остатка
                                        • 0
                                          забыл добавить проверку деления на 0:
                                          последнюю строчку надо заменить на
                                          say scalar grep { $n % $_ == 0 } grep $_ != 0,@to_check;
                                        • +3
                                          4 задание:
                                          select distinct a.id,a.name,a.score
                                          from players a
                                          left join (select distinct score from players) b on (a.score<b.score)
                                          group by a.id,a.name,a.score
                                          having count(b.score)=2
                                          order by a.score desc;
                                          • +2
                                            если одинаковый результат у N игроков считать за N мест, то даже проще:
                                            select distinct a.id,a.name,a.score
                                            from players a
                                            left join players b on (a.score<b.score)
                                            group by a.id,a.name,a.score
                                            having count(b.score)=2
                                            order by a.score desc;
                                            • +1
                                              Это неплохо, но не работает, если у трех участников Score равен 10. Тогда они делят места с 1 по 3, а ваш запрос ничего не возвращает.
                                              • +1
                                                Можно посчитать для каждого участника наивысшее место (число результатов, больше чем у него + 1) и низшее место (число результатов «перед ним» + число результатов, равных его). На третье место попадают все, у кого число 3 между двумя этими значениями.

                                                select a.id, a.name
                                                from @players a
                                                cross join @players b
                                                group by a.id, a.name
                                                having 3 between
                                                sum(case when (b.Score > a.Score) then 1 else 0 end) + 1
                                                -- минимальное место
                                                and (sum(case when (b.Score > a.Score) then 1 else 0 end) +
                                                sum(case when (b.Score = a.Score) then 1 else 0 end))
                                                -- максимальное место
                                          • +2
                                            Кстати, задача №3

                                            select a.Id, a.CategoryId, a.Name from Books a
                                            left join Books b on b.Id = a.Id and b.CategoryId = 2
                                            where a.CategoryId = 1 and b.Id is null
                                            • 0
                                              Верно :)
                                              Кстати, в ту же минуту, что вы написали комментарий, на почту пришло такое же решение от хабрачитателя Alexey Syschikov.
                                              • +1
                                                По-моему, так проще:
                                                select name from books where categoryId = 1
                                                minus
                                                select name from books where categoryId = 2;
                                                
                                                • +1
                                                  Это синтаксис Oracle? Да, так, конечно, удобнее :)
                                                  • 0
                                                    Да, с MySQL не часто приходится работать, поэтому не знал, что там нет «minus».
                                            • +2
                                              Задачка №1 на python:
                                              n = 1938
                                              s = str(n)
                                              r = set()
                                              for a in range(len(s)):
                                                  for b in range(len(s)-a):
                                                      num = int(s[a:a+b+1])
                                                      if not n % num:
                                                          r.add(num)
                                              print len® - 1
                                              • +4
                                                Только хотел написать на питоне. У тебя, кстати, деление на нуль не отлавливается.

                                                Задача #1.
                                                Вот в две строки ответ:
                                                n = "1938"
                                                print len([i for i in range(len(n)-1) for j in range(len(n)-i) if int(n[j:j+i+1]) and int(n)%int(n[j:j+i+1])==0])
                                                

                                                Знаю что некрасиво, но я не мастер в извращениях.
                                                • +1
                                                  Ваше решение работает :)

                                                  Между прочим, в редакцию поступило письмо от Виктора, начинающего пайтониста:

                                                  В программировании я новичок, могут быть ляпы, писал решение первой задачи на Python 2.7:

                                                  l = [str(1938)[i] for i in range(len(str(1938)))]
                                                  res = 0
                                                  
                                                  def sr():
                                                    m = ''
                                                    for n in range(len©):
                                                      m += c[n]
                                                    if m != '': return int(m)
                                                    else: return 0.1
                                                  
                                                  for j in range(len(l)):
                                                    for i in range(len(l)):
                                                      c = l[i:j+1]
                                                      if l != c and 1938%sr() == 0: res += 1
                                                  
                                                  print res

                                                  Был бы очень признателен, если бы Вы указали узкие места и ошибки в коде. Пытаюсь научиться программировать, начал с Python.

                                                  Помогите Виктору :)
                                                  • 0
                                                    От новичка — новичку:
                                                    habrahabr.ru/post/204476/
                                                    Это насчёт всех range(len(x)) и прочих узкостей. К примеру:
                                                    >>for n in range(len©):
                                                    >>> m += c[n]

                                                    Меняется на
                                                    for n in c:
                                                    m += n

                                                    И ещё — константы всегда легче вывести в отдельную переменную.

                                                    >>> for char in str(1984):
                                                    … print char

                                                    1
                                                    9
                                                    8
                                                    4

                                                    Внезапно, строка — это список символов, и нет нужды делать [str(1938)[i] for i in range(len(str(1938)))] ;-) Зачем создавать массив, если строка — это сам по себе массив символов?

                                                    Нет проверки на деление на ноль, печалька =(

                                                    Это не всё, думаю, но углубиться не хватит времени =(
                                                  • +1
                                                    У меня получилось на 5 символов меньше :-D
                                                    a = '1938'
                                                    print len([1 for k in range(len(a)) for l in range(k+1,len(a)+1) if int(a[k:l]) if int(a)%int(a[k:l])==0])-1
                                                    
                                                • +3
                                                  Второй алгоритм на APL с циклом (неизящный):
                                                  image

                                                  И его вывод:
                                                  image
                                                  • 0
                                                    Ой-ё… Ну и язык, — чтобы запостить его пример, нужно скрншотить… Да, вы молодец. :)
                                                    • 0
                                                      Спасибо. Проблема в том, что текстом спецзнаки отображаются совсем уж коряво, например:
                                                      ↑(,¨↓mat[i;])/¨⊂sum

                                                      поэтому приходится скриншотить.
                                                • +1
                                                  Было бы совсем хорошо, если бы добавить к каждому заданию набор тестов.
                                                  • +1
                                                    Я тут что, первый рубист?
                                                    number = 1938.to_s
                                                    unpack_string = ""
                                                    number.length.times do |num|
                                                      unpack_string += "@#{num}aa*" unless num+1 == number.length
                                                      unpack_string += "@0a#{num}" unless num < 2
                                                    end
                                                    p (number.unpack(unpack_string) - ["0"]).find_all{|element|number.to_i%element.to_i==0}.count
                                                    
                                                    • +2
                                                      Оригинальное решение 2-й SQL'ной задачи предложил хабрачитатель Юрий!

                                                      SELECT GROUP_CONCAT(a.Name)
                                                      FROM players AS a
                                                      INNER JOIN players AS b
                                                        ON a.Score = b.Score
                                                      GROUP BY a.Score, b.Name
                                                      ORDER BY a.Score DESC
                                                      LIMIT 2,1;

                                                      Если кто-нибудь захочет выслать ему инвайт, напишите мне личное сообщение.
                                                      • +1
                                                        Довольно оригинальное решение! Только как быть, если кроме имени надо будет вернуть другую информацию по игрокам?
                                                        • +1
                                                          Использовать еще одно отличное решение, предложенное хабрачитателем по имени Григорий Косьян :)

                                                          SELECT sg.name
                                                          FROM Players sg
                                                          INNER JOIN Players gr2
                                                            ON (sg.score <= gr2.score)
                                                          LEFT JOIN Players gr1
                                                            ON (sg.score < gr1.score)
                                                          GROUP BY sg.name
                                                          HAVING COUNT(DISTINCT gr1.name) < 3
                                                            AND 3 <= COUNT(DISTINCT gr2.name);
                                                      • +1
                                                        В рамках ненормального программирования хабрачитатель Кирилл Зорин прислал решение первой алогритмической задачи на PL/SQL:

                                                        with
                                                         t as (select 1938 as num from dual),
                                                         tt as (select level lev, num from t connect by level <= length(to_char(num)))
                                                        select
                                                         count(
                                                          case when mod(t1.num, substr(to_char(t1.num), t1.lev, length(to_char(t1.num)) - t1.lev + 1 - t2.lev + 1)) = 0
                                                           then 1 end)
                                                        from
                                                         tt t1,
                                                         tt t2
                                                        where
                                                         t2.lev <= length(to_char(t1.num)) - t1.lev + 1
                                                         and substr(to_char(t1.num), t2.lev, length(to_char(t1.num)) - t1.lev + 1-t2.lev+1)!= t1.num


                                                        * This source code was highlighted with Source Code Highlighter.
                                                        • 0
                                                          «T-SQL и не такое может!», — как бы отвечает хабрачитатель с ником Dr.Marazm.

                                                          declare @num as int, @i as int = 1, @j as int = 1
                                                          set @num = 1938
                                                          drop table #t
                                                          create table #t (a int)

                                                          while @i <= len(@num) begin
                                                            set @j = 1
                                                            while @j <= len(@num) begin
                                                              insert into #t (a)
                                                              select substring(cast(@num as varchar),@i,@j) a
                                                              set @j = @j + 1
                                                            end
                                                            set @i = @i + 1
                                                          end

                                                          select distinct *, @num % a from #t where @num % a = 0 and @num <> a


                                                          * This source code was highlighted with Source Code Highlighter.
                                                          • +1
                                                            Наконец-то у меня есть учётка на Хабре и теперь я могу написать, что в моём решении нет никакого PL/SQL :)
                                                        • +1
                                                          MYSQL 2: SELECT group_concat(id, SEPARATOR ",") FROM players GROUP BY score ORDER BY score LIMIT 2,1

                                                          В случае с id, если нам нужны именно id игроков.
                                                          • +3
                                                            Алгоритмы. Задача №2, посложнее
                                                            Решение на javascript, не такое интересное, но работает во всех браузерах…
                                                            var data = [
                                                            "0110",
                                                            "0000",
                                                            "0001",
                                                            "0000"
                                                            ];
                                                            
                                                            function calc(row){
                                                              var res = 0;
                                                              return !!row.replace(/1/g, function(m, i){ 
                                                                res += calc(data[i]);
                                                              }) + res;
                                                            }
                                                            
                                                            for (var i = 0, row, result = 0; row = data[i++];)
                                                              result += calc(row);
                                                            
                                                            alert(result); // вывод результата, выдаст 8
                                                            


                                                            А вот если заюзить Array.prototype.reduce из ES5, то получается весьма интересно :) (работает в IE9, Chrome, Firefox, Opera)
                                                            var data = [
                                                            "0110",
                                                            "0000",
                                                            "0001",
                                                            "0000"
                                                            ];
                                                            
                                                            alert(data.reduce(function calc(res, row){
                                                              return !!row.replace(/1/g, function(m, i){ 
                                                                res = calc(res, data[i]);
                                                              }) + res;
                                                            }, 0));  // выдаст 8
                                                            

                                                            • +1
                                                              запутанное решение первой на PHP

                                                              function solve1($n)
                                                              {
                                                              $r = 0;
                                                              for ($i = $j = 0, $l = strlen($n); $i < $l; $i += ($j *= (++$j < $l — $i)) == 0)
                                                              if ($j+1 < $l && substr($n, $i, $j+1)) $r += (($n % substr($n, $i, $j+1))==0);
                                                              return $r;
                                                              }
                                                              • +1
                                                                Алгоритмы. Задача №1, разминочная
                                                                Решение на javascript. В целом, классическое решение, если опустить автоматическое приведение к типам.
                                                                  var num = String(1938);
                                                                  var result = -1;
                                                                
                                                                  for (var e = num.length; e; e--)
                                                                    for (var s = 0; s < e; s++)
                                                                      result += num % num.substring(s, e) == 0;
                                                                  
                                                                  alert(result);
                                                                
                                                                • +1
                                                                  1-я задача, рекурсивное решение.

                                                                  <code class="python">n = 1938
                                                                  r = lambda x, y: r(0, x) + r(x[1:], 0) if x else int(n % int(y) == 0 if int(y) else 0) + r(0, y[:-1]) if y else 0
                                                                  print r(str(n), 0) - 1</code>
                                                                  • +1
                                                                    Поправил подсветку и немного сократил код.
                                                                    n = 1938
                                                                    r = lambda x, y: x and r(0, x) + r(x[:-1], 0) or y and (not n % (int(y) or .1)) + r(0, y[1:]) or 0
                                                                    print r(str(n), 0) - 1
                                                                    
                                                                  • 0
                                                                    моя версия на php)
                                                                    $num = 1938;
                                                                    for($j=1; $j < strlen($num); $j++){
                                                                    for($i=0; $i < strlen($num); $i++){
                                                                    $array[] = substr($num,$i,$j);
                                                                    }
                                                                    }
                                                                    $array = array_unique($array);
                                                                    $count = 0;
                                                                    foreach ($array as $value){
                                                                    if(($num % $value) == 0){
                                                                    $count++;
                                                                    }
                                                                    }
                                                                    echo $count;
                                                                    • 0
                                                                      Более-менее стандартное, зато структурированное решение на C++ прислал хабрачитатель Евгений Дворянкин:
                                                                      #include <iostream>
                                                                      
                                                                      int GetRating(std::string *Data, int index)
                                                                      {
                                                                          int rate = 1;
                                                                          for (int i =0; i<Data[index].size(); i++)
                                                                              if(Data[index][i] == '1')
                                                                                  rate+=GetRating(Data, i);
                                                                      
                                                                          return rate;
                                                                      }
                                                                      
                                                                      void main()
                                                                      {
                                                                          std::string srcData[]={"0110", "0000", "0001", "0000"};
                                                                          int rate=0;
                                                                          for(int i=0; i < (sizeof(srcData)/sizeof(srcData[0])) ; i++)
                                                                              if(srcData[i]=="0000")
                                                                                  rate++;
                                                                              else
                                                                                  rate+=GetRating(srcData,i);
                                                                          std::cout << rate;
                                                                      }
                                                                      • 0
                                                                        А вот и рекурсивное решение на лиспе. Если точнее, на Racket.

                                                                        (define (calc tbl)
                                                                          (define (rating str)
                                                                            (apply + 1
                                                                                   (map (λ (x) (rating (list-ref tbl (car x))))
                                                                                        (regexp-match-positions* "1" str))))
                                                                          (apply + (map rating tbl)))
                                                                        

                                                                        Вызывать так:
                                                                        (calc '("0110" "0000" "0001" "0000"))
                                                                        • 0
                                                                          Решение юзера hidoba (он сейчас без интернета) на Wolfram Mathematica:


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