3

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

1
  • 1
    @KromStern замечание верное ) Ну вот, как-то исправил.
    – Nick Volynkin
    4 мая 2016 в 8:00

7 ответов 7

9

Haskell, 25 символов

g s l=forM [1..l]$const s
g s l=forM [1..l] (\x->s) -- альтернативный вариант

Здесь параметр s - строка-алфавит, l - требуемая длина.

Для работы нужен модуль Control.Monad

Функция forM рекурсивно проходит по Traversable структуре и применяет функцию, возвращающую монаду, к каждому элементу, после чего "собирает" внутри монады структуру, состоящую из результатов функции.

Структура тут - список. Монада - тоже список (монада-список отвечает за перебор всех вариантов).

Таким образом, происходит следующее:

  1. Берется список индексов от 1 до l (l - требуемая длина пароля)

  2. Каждому индексу сопоставляется набор вариантов (он задан как const s - то есть номер индекса игнорируется и набор вариантов будет s независимо от индекса)

  3. Варианты каждого индекса комбинируются в порядке исходного списка - и получается список всех возможный строк длины l

6

119 символов

IEnumerable<string>F(char[]s,int l){return--l<0?new string[]{""}:from r in F(s,l)join c in s on 0 equals 0 select r+c;}
IEnumerable<string> F(char[] s, int l)
{
  return --l < 0
    ? new string[] { "" }
    : from r in F(s, l) join c in s on 0 equals 0 select r + c;
}

Чтобы можно было задавать задержку:

IEnumerable<string> F(char[] s, int l, int t)
{
  foreach (var r in F(s, l))
  {
    Thread.Sleep(t);
    yield return r;
  }
}

Проверка:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ruSO_519441___Перебор
{
  class Program
  {
    IEnumerable<string> F(char[] s, int l)
    {
      return --l < 0
        ? new string[] { "" }
        : from r in F(s, l) join c in s on 0 equals 0 select r + c;
    }

    static void Main(string[] args)
    {
      int i = 0;

      foreach (var s in (new Program()).F("01234567".ToCharArray(), 4))
        if (Convert.ToInt32(s, 8) != i++)
          throw new Exception();

      Console.WriteLine(i);
      Console.ReadKey();
    }
  }
}
6
  • @May_be, ответ дополнен.
    – Qwertiy
    2 мая 2016 в 20:17
  • @May_be, дополнил.
    – Qwertiy
    2 мая 2016 в 20:21
  • 1
    IEnumerable<string>F(char[]s,int l)=>--l<0?new[]{""}:F(s,l).SelectMany(_=>s,(a,b)=>a+b);
    – user181245
    2 мая 2016 в 23:11
  • @PetSerAl: почему не отдельным ответом?
    – VladD
    2 мая 2016 в 23:16
  • @VladD Я просто немного улучшил, а не придумал с нуля.
    – user181245
    2 мая 2016 в 23:17
5

Javascript ES6, 113 символов

(s,l)=>eval(`${t="for(q of s)".repeat(l,l=[]).replace(/q/g,(q,i)=>q+i)}l.push(${t.match(/q\d+/g).join('+')})`)&&l

PS: Раз уж появился F#, пусть и JS будет :)

3

Haskell, 42 символа

g s 0=[""];g s l=do{x<-g s$l-1;y<-s;[y:x]}

Развернутый вариант, для понимания:

gen :: [Char] -> Int -> [String]
gen chars 0 = return ""
gen chars len = do
  x <- gen chars (len-1)
  y <- chars
  return $ y:x

main = print $ gen ['a', 'b', 'c'] 3
3

71 82 92 символа

Версия на F#:

let rec p (l:char seq)=function
|0->seq{yield[]}
|k->seq{for s in p l (k-1) do for c in l->c::s}

Это, конечно, не C#, но тоже .NET, так что можно использовать с программами на C#.

Тестовый код:

[<EntryPoint>]
let main argv = 
    p ['a'; 'b'; 'c'] 4
       |> Seq.map (fun arr -> new string(arr |> List.toArray))
       |> Seq.iter (printfn "%A")
    0

Развёрнутое состояние:

let rec combinations allowed = function
    | 0 -> seq { yield [] }
    | k -> seq { for s in combinations allowed (k-1) do for c in allowed -> c::s }

Типовыводитель рулит, укоротил:

let rec p l=function
|0->seq{yield[]}
|k->seq{for s in p l (k-1)do for c in l->c::s}

По совету @PetSerAl, можно уложить в одну строку:

let rec p l=function 0->seq{yield[]}|k->seq{for s in p l (k-1)do for c in l->c::s}

Можно сэкономить ещё пару символов, если перейти к спискам:

let rec p l=function 0->[[]]|k->[for s in p l (k-1)do for c in l->c::s]
7
  • seq{yield[]} -> Seq.empty. Также символ | перед первым вариантом не является обязательным.
    – user181245
    2 мая 2016 в 23:55
  • @PetSerAl: Хм, вроде ж Seq.empty возвращает пустую последовательность, а мне нужна одноэлементная, состоящая из [].
    – VladD
    3 мая 2016 в 9:16
  • Да, чего-то я сглупил. Хотя, вроде проверял, работало. Значит, что-то не то проверял.
    – user181245
    3 мая 2016 в 12:39
  • @PetSerAl: И у меня без стартового | не скомпилировалось. Выдаёт error FS0010: Unexpected keyword 'let' or 'use' in binding. Expected incomplete structured construct at or before this point or other token. на последующем let main ...
    – VladD
    3 мая 2016 в 12:41
  • 1
    Я пишу такую команду в FSI: let rec p l=function 0->seq{yield[]}|k->seq{for s in p l (k-1)do for c in l->c::s} in p [1..3] 3;; — и он её прожёвывает.
    – user181245
    3 мая 2016 в 12:48
2

Ruby, 45 символов

->a, n{a.repeated_permutation(n).map(&:join)}

Функция (лямбда/проц), принимает массив символов и число, возвращает последовательность (перечислитель, генератор, Enumerator) перестановок его элементов с повторениями.

Но есть беда: он не ленивый (из-за .map(&:join)) и на сколько-нибудь больших входных данных он сожрёт всю память и упадёт. Но требований к этому не ставилось :)

Починить этот досадный недостаток можно всего за $9.99 +5 символов:

->a, n{a.repeated_permutation(n).lazy.map(&:join)}

                        вот так ^^^^^
2

38 символов

do.call(paste0,expand.grid(rep(s,l)))

где s-массив символов которые можно использовать, l-длина

Пример :

s=list(letters[1:3])
l=2
do.call(paste0,expand.grid(rep(s,l)))
[1] "aa" "ba" "ca" "ab" "bb" "cb" "ac" "bc" "cc"

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.