Прошёл для души конкурс “Системный администратор 2011” (и тест, и квест). Но статья не о том. Решил привести описание решения одной задачи (задача №7 из квеста – о численном треугольнике) из этого конкурса на powershell, не столько ради самой задачи (типовой алгоритм оптимизации транспортной задачи), сколько ради практики на powershell.

Суть задачи максимально проста. Есть текстовый файл следующего вида:

2
1 3
4 1 5
4 1 7 1

И необходимо найти путь от вершины до любой “точки” (числа) в нижнем ребре треугольника такой, чтобы сумма чисел, через которые этот путь пролегает, была максимальной. Двигаться при этом можно только строго вниз или вниз-вправо по диагонали.

В приведённом выше примере ответ будет – 17. маршрут от вершины: 2 + 3 + 5 + 7. Но в самой задаче (а не в примере) – 121 строка в файле, и руками уже точно не подберёшь оптимальный маршрут.

Решим задачу на powershell:

# решаем тест конкурса Системный администратор 2011
# http://www.sysadmin2011.ru/quest/show/7
# грузим наш численный треугольник, формируя необходимые массивы

$data = @( `
    (get-content tr.txt) `
    | %{ `
        ,@( `
            ($_ -split ' ') `
            | %{[int] $_} `
        ) `
    } `
);

# далее алгоритм будет классический. Анализировать будем по строкам, начиная с первой,
# формируя новый массив массивов results, начиная с нижней (самой длинной) строки.
# сначала соответствующей строке results присвоим просто последнюю строку data
# затем в предыдущую строку results копируем предыдущую строку data,
# после чего перебираем все элементы results в этой строке и прибавляем к нему
# либо соответствующий, либо следующий за ним элемент следующей строки results (по max).
# и так - до первой (0ой) строки. В её 1ом (0ом) элементе - и будет максимальная сумма

$results = $data;
for ($r = $results.count-2; $r -ge 0; $r--) {
    for ($i = 0; $i -lt $results[$r].count; $i++) {
        $results[$r][$i] += ($results[$r+1][$i], $results[$r+1][$i+1]) | sort -descending | select -first 1 ;
    };
};

$results[0][0];

Красиво, на мой взгляд, получилась загрузка исходного файла в массив. Убил некоторое время над неочевидной комбинацией операторов ,@(), которая позволила избежать конкатенации массивов, отражающих строки исходного файла, в один массив. Однако, при наличии конвейера в powershell решение с циклами кажется каким-то совершенно не родным. Есть идеи, как можно написать решение короче и оптимальнее?

Опробовал и ещё одно решение:

@(
    (get-content tr.txt) `
    | % { `
        ,@( `
            ($_ -split ' ') `
            | ? {$_ -ne ''} `
            | %{[int] $_} `
        ) `
    } `
) `
| % `
-process { `
    if ($_.count -gt 1) {
        $_[0] += $lastRow[0];
        for ($i = 1; $i -lt $_.count-1; $i++) {
            if ($lastRow[$i] -gt $lastRow[$i-1]) {
                $_[$i] += $lastRow[$i];
            } else {
                $_[$i] += $lastRow[$i-1];
            };
        };
        $_[$_.count-1] += $lastRow[$lastRow.count-1];
    };
    $lastRow = $_;
} `
-end { `
    $lastRow;
} `
| sort -descending | select -first 1;

Прелесть его в том, что оно уже не загружает весь массив сразу, а способно (гипотетически) обрабатывать существенно большие “треугольники” при меньшей потребности в памяти. По сути, хранятся в один момент времени в памяти только две строки. Ну и работает этот вариант ощутимо быстрее. Но с точки зрения читабельности, мне кажется, он проиграл предыдущему.

Условие выбора максимального элемента можно и заменить таким образом:

$_[$i] += $lastRow[($i-1)..$i] | sort -descending | select -first 1;

Или определить свой функцию select-max:

function select-max {
    param (
        [Parameter(
            Mandatory=$true,
            ValueFromPipeline=$true
        )]
        [int]$i
    )
    begin {
        [int]$max = $i;
    }
    process {
        if ($i -gt $max) {$max = $i};
    }
    end {
        $max;
    }
}

@(
    (get-content tr.txt) `
    | % { `
        ,@( `
            ($_ -split ' ') `
            | ? {$_ -ne ''} `
            | %{[int] $_} `
        ) `
    } `
) `
| % `
-process { `
    if ($_.count -gt 1) {
        $_[0] += $lastRow[0];
        for ($i = 1; $i -lt $_.count-1; $i++) {
            $_[$i] += ($lastRow[($i-1)..$i] | select-max);
        };
        $_[$_.count-1] += $lastRow[$lastRow.count-1];
    };
    $lastRow = $_;
} `
-end { `
    $lastRow;
} `
| select-max;

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

Коллеги, буду рад, если предложите другие решения этой задачи!

Опубликовать комментарий

XHTML: Вы можете использовать следующие HTML теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Tags Связь с комментариями статьи:
RSS комментарии
Обратная ссылка