Смятане на варианти - оптимизация на бройките ползван материал.

pix3l каза:
Баси, php-то имало енумерации вече... след 20+ години 😂
Увеличете...
Де и да работеха като в нормалните езици. Енумерация по подразбиране би трябвало да има числова стойност, като започват от 0.

PHP: 
enum LogLevel {
    case Debug;
   case Info;
}

var_dump(LogLevel::Debug < LogLevel::Info); // би трябвало да върне True но връща False
var_dump(LogLevel::Debug->value < LogLevel::Info->value); // дава warning и False, защото $value е недефинирано

// ----

enum LogLevel2 : int {
    case Debug = 0;
    case Info = 1;
}

var_dump(LogLevel2::Debug < LogLevel2::Info); // връща False, защото не може да вземе стойността
var_dump(LogLevel2::Debug->value < LogLevel2::Info->value); // най-накрая сработва и връща True

Леко е досадно честно казано.
 
Енумерациите си имат плюсовете, защото можеш да ги ползваш като тип. Ако създаваш константи, при тях не можеш да гарантираш типа, който може да искаш да зададеш на даден параметър или променлива. Типа ще ти остане примитивен и ще трябва да правиш допълнителни проверки, които можеш да оставиш на интерпретатора.

В Rust например енумерациите са доста мощни и полезни.
 
Онзи ден имплементирах най-наивния наглед работещ рекурсивен алгоритъм, за който писах на първата страница (вие що не го пробвахте :D :p); тръгнах да му добавям да помни и изрезките (в момента само печатам общата бройка накрая) ама не го подкарах бързо и го зарязах.

Предимството на рекурсивния алгоритъм е, че доста директно следва условието и може лесно да се провери за коректност по индукция (не съм го правил). Недостатъкът е, разбира се, че върви покъртително бавно, защото пробва абсолютно всяка възможност за всяка възможна тръба.
С образователна цел, ето питонска версия на псевдокода ми от по-горе (че php не съм писал от години, а и го нямам инсталиран :D):
Python: 
from math import inf

def alg(demand, supply, depth = 0):
    if not demand: return 0

    (wanted_len, wanted_count) = demand[0]

    options = []

    for i, (supply_len, supply_count) in enumerate(supply):
        if supply_len >= wanted_len:
            # copy them
            new_demand = demand[::]
            new_supply = supply[::]

            add_pipe(wanted_len, -1, new_demand)
            add_pipe(supply_len, -1, new_supply)

            if supply_len > wanted_len:
                add_pipe(supply_len - wanted_len, 1, new_supply)

            options.append(
                alg(new_demand, new_supply, depth + 1)
                + (1 if supply_count == inf else 0))

    return min(options)

def add_pipe(new_pipe_len, amount, to_pipes):
    if amount < -1 or amount > 1: raise Exception("Can add/remove no more than 1 at a time.")
    if new_pipe_len == 0: return

    for i, (pipe_len, pipe_count) in enumerate(to_pipes):
        if new_pipe_len == pipe_len: # perfect match!
            new_amount = pipe_count + amount
            if new_amount > 0:
                to_pipes[i] = (pipe_len, new_amount)
            elif new_amount == 0:
                to_pipes.pop(i)
            else:
                raise Exception(f"Impossible! Negative new_amount: {new_amount}")
            return
        if new_pipe_len > pipe_len:
            to_pipes.insert(i, (new_pipe_len, 1))
            return

    to_pipes.append((new_pipe_len, 1))

Код: 
demand = [(5,20),(4,10),(0.1,1)]
supply = [(6,inf)]
print(alg(demand,supply))
# print(alg([(5, 3), (1, 4)], [(6, inf)]))
# print(alg([(50, 3), (10, 2), (1, 1)], [(60, inf)]))
# print(alg([(1,3)], [(6, inf), ((1,3))]))

@Revelation, искаш ли да сравним резултатите? Генерирах малко тестове, прикачвам си тестовия файл: на всеки ред има списък с demand и накрая числото, което даде мойта реaлизация при supply от безброй тръби с дължина 10.
Дай да видим дали имаме някакви разлики върху някой от входовете?
Генерирах тестовете така:
Python: 
    for k in range(2,6):
        for _ in range(20):
            demand = []
            for length in random.sample(range(1, 10), k = k):
                demand.append((length, random.randrange(1,6)))
            demand.sort(reverse=True, key=lambda p: p[0])
            res = alg(demand, [(10, inf)])
            print(f"{demand} {res}")
 

Прикачени файлове

  • tests.txt
    tests.txt
    2.4 KB · Преглеждания: 3
Последно редактирано:
Всички резултати са еднакви https://onlinephp.io/c/73bdb

PHP: 
<?php

enum LogLevel: int
{
    case Debug = 0;
    case Info = 1;
}

class Logger
{
    private function __construct()
    {
    }

    public static function create(): Logger
    {
        return new Logger;
    }

    public function debug($msg = "", array $context = [], bool $prettyPrint = false): void
    {
        $this->log(LogLevel::Debug, $msg, $context, $prettyPrint);
    }

    public function info($msg = "", array $context = [], bool $prettyPrint = false): void
    {
        $this->log(LogLevel::Info, $msg, $context, $prettyPrint);
    }

    private function log(LogLevel $logLevel, $msg = "", array $context = [], bool $prettyPrint = false): void
    {
        if ($logLevel->value < LOG_LEVEL->value) return;

        $jsonFlags = $prettyPrint ? JSON_PRETTY_PRINT : JSON_ERROR_NONE;
        $context = !empty($context)
            ? json_encode($context, $jsonFlags)
            : null;

        printf("%s %s\n", $msg, $context);
    }
}

class PipeDemandInfo
{
    private int $quantity;
    private int $length;

    public function __construct(int $length, int $quantity)
    {
        if ($length <= 0) {
            throw new InvalidArgumentException("Length must be greater than zero.");
        }

        if ($quantity <= 0) {
            throw new InvalidArgumentException("Quantity must be greater than zero.");
        }

        $this->length = $length;
        $this->quantity = $quantity;
    }

    public function getQuantity(): int
    {
        return $this->quantity;
    }

    public function getLength(): int
    {
        return $this->length;
    }
}

class PipeDemandCalculator
{
    private int $usedPipes = 0;
    private int $defaultPipeLength;

    /** @var PipeDemandInfo[] */
    private array $pipesDemand = [];

    /** @var int[] */
    private array $leftovers = [];
    private Logger $logger;

    public function __construct(int $defaultPipeLength)
    {
        $this->defaultPipeLength = $defaultPipeLength;
        $this->logger = Logger::create();
    }

    public function getUsedPipes(): int
    {
        return $this->usedPipes;
    }

    public function displaySummary(): void
    {
        $this->logger->info("========= Summary =========");
        $this->logger->info(sprintf("> Pipe length: %dmm", $this->defaultPipeLength));
        $this->logger->info("> Demands:");
        foreach ($this->pipesDemand as $pipeDemandInfo) {
            $this->logger->info(sprintf("  * %d x %dmm", $pipeDemandInfo->getQuantity(), $pipeDemandInfo->getLength()));
        }

        $this->logger->info("> Result:");
        $this->logger->info(sprintf("  * Total pipes used: %d", $this->usedPipes));
        $this->logger->info(sprintf("  > Leftover cuts: %d", sizeof($this->leftovers)));
        foreach (array_count_values($this->leftovers) as $length => $quantity) {
            $this->logger->info(sprintf("    * %d x %dmm", $quantity, $length));
        }
    }

    public function addPipeDemand(int $quantity, int $length): void
    {
        if ($length > $this->defaultPipeLength) {
            throw new InvalidArgumentException(
                sprintf("\$length must be less than or equal to %d.", $this->defaultPipeLength)
            );
        }

        $this->pipesDemand[] = new PipeDemandInfo($length, $quantity);
    }

    public function calculate(): void
    {
        // always start with the longest pipes
        usort($this->pipesDemand, fn(PipeDemandInfo $a, PipeDemandInfo $b) => $b->getLength() - $a->getLength());

        foreach ($this->pipesDemand as $demandInfo) {
            $this->logger->debug("Demanded length", [$demandInfo->getLength()]);
            $this->calculateDemand($demandInfo);
        }
    }

    private function calculateDemand(PipeDemandInfo $pipeDemandInfo): void
    {
        for ($i = 0; $i < $pipeDemandInfo->getQuantity(); $i++) {
            $pipeLength = $this->findLeftoverPipe($pipeDemandInfo->getLength());
            if ($pipeLength === null) {
                $pipeLength = $this->defaultPipeLength;
                $this->usedPipes++;
            }

            $remainingLength = $pipeLength - $pipeDemandInfo->getLength();
            if ($remainingLength > 0) {
                $this->leftovers[] = $remainingLength;
            }
        }
    }

    private function findLeftoverPipe(int $requiredLength): ?int
    {
        // always start from the shortest
        sort($this->leftovers);

        $this->logger->debug(context: ['leftovers' => $this->leftovers]);

        $smallestDemandedPipe = $this->pipesDemand[sizeof($this->pipesDemand) - 1];

        $totalLeftovers = sizeof($this->leftovers);
        for ($i = 0; $i < $totalLeftovers; $i++) {
            $leftoverLength = $this->leftovers[$i];

            $logContext = ['leftover length' => $leftoverLength, 'required length' => $requiredLength];

            if ($leftoverLength < $requiredLength) {
                $this->logger->debug('Leftover length is smaller than the required. Skip to next...', $logContext);
                continue;
            }

            $remainingLength = $leftoverLength - $requiredLength;
            if ($remainingLength > 0 && $remainingLength < $smallestDemandedPipe->getLength() && $i < array_key_last($this->leftovers)) {
                $this->logger->debug(
                    'Cutting from this leftover pipe leaves a cut smaller than the smallest demanded pipe. Skip, if not last iteration.',
                    array_merge($logContext, ['smallest demanded length' => $smallestDemandedPipe->getLength()])
                );
                continue;
            }

            array_splice($this->leftovers, $i, 1);

            return $leftoverLength;
        }

        return null;
    }
}

const LOG_LEVEL = LogLevel::Info;

$file = file("./tests.txt", FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$logger = Logger::create();
$allResultsEqual = true;

foreach ($file as $row) {
    [$demand, $result] = explode(" ", $row);

    $calc = new PipeDemandCalculator(10);
    $decodedDemand = json_decode($demand);
    foreach ($decodedDemand as [$length, $quantity]) {
        $calc->addPipeDemand($quantity, $length);
    }
    $calc->calculate();

    $assertEqual = $calc->getUsedPipes() === (int)$result;
    if (!$assertEqual) {
        $allResultsEqual = false;
    }

    $logger->debug(context: ['demand' => $demand, 'equal' => $assertEqual]);
}

$logger->info(sprintf("All equal? %s", var_export($allResultsEqual, true)));

Пипнах малко твоя файл да го нагодя за по-лесно четене при мен.
[[8,3],[7,4]] 7
[[6,1],[5,1]] 2
[[6,4],[5,5]] 7
[[9,3],[7,3]] 6
[[6,5],[2,2]] 5
[[8,5],[4,2]] 6
[[8,2],[5,2]] 3
[[8,2],[1,2]] 2
[[9,2],[6,3]] 5
[[8,4],[5,2]] 5
[[9,2],[6,1]] 3
[[7,3],[3,3]] 3
[[7,3],[2,4]] 4
[[5,1],[2,5]] 2
[[8,4],[7,1]] 5
[[6,2],[3,1]] 2
[[8,5],[5,2]] 6
[[7,3],[6,2]] 5
[[3,2],[1,3]] 1
[[9,4],[7,4]] 8
[[9,2],[5,4],[4,4]] 6
[[6,3],[4,2],[3,4]] 4
[[3,2],[2,4],[1,1]] 2
[[9,5],[8,1],[5,1]] 7
[[9,5],[6,2],[3,2]] 7
[[6,1],[3,3],[2,2]] 2
[[5,3],[3,3],[2,4]] 4
[[8,4],[6,2],[3,4]] 7
[[5,2],[4,4],[3,3]] 4
[[8,4],[7,2],[4,5]] 9
[[3,1],[2,2],[1,4]] 2
[[7,1],[3,4],[2,4]] 3
[[4,1],[3,4],[1,2]] 2
[[7,1],[6,2],[4,4]] 4
[[7,1],[6,4],[5,1]] 6
[[5,1],[4,1],[3,4]] 3
[[8,2],[6,5],[5,4]] 9
[[8,3],[7,3],[6,5]] 11
[[8,4],[7,4],[3,4]] 8
[[6,1],[5,2],[3,1]] 2
[[9,1],[6,4],[3,2],[1,1]] 5
[[8,1],[3,2],[2,1],[1,2]] 2
[[9,2],[6,4],[5,5],[4,1]] 9
[[6,3],[3,1],[2,3],[1,4]] 4
[[8,3],[7,4],[4,3],[3,1]] 9
[[9,2],[8,1],[6,4],[5,1]] 8
[[9,2],[4,1],[3,3],[1,5]] 4
[[7,1],[5,4],[4,2],[1,5]] 4
[[9,5],[8,4],[7,4],[1,5]] 13
[[7,1],[6,4],[4,3],[2,4]] 6
[[7,1],[6,3],[4,3],[1,1]] 4
[[6,3],[4,5],[2,1],[1,3]] 5
[[9,2],[8,1],[5,5],[3,2]] 7
[[8,3],[6,1],[5,3],[1,3]] 6
[[9,5],[8,5],[7,2],[5,3]] 14
[[9,5],[6,2],[5,3],[4,3]] 9
[[9,5],[5,2],[3,4],[2,3]] 8
[[8,3],[7,4],[6,5],[3,1]] 12
[[7,2],[6,2],[5,2],[1,5]] 5
[[9,5],[7,1],[5,2],[3,5]] 9
[[9,3],[7,4],[5,3],[3,3],[1,3]] 9
[[7,3],[6,2],[5,3],[4,3],[3,2]] 7
[[8,5],[6,4],[5,3],[2,2],[1,3]] 11
[[8,1],[6,1],[4,2],[3,5],[2,2]] 5
[[9,4],[6,1],[5,4],[4,3],[2,3]] 9
[[9,5],[8,3],[7,2],[2,5],[1,1]] 10
[[9,4],[6,4],[5,4],[4,2],[3,5]] 11
[[9,1],[7,3],[6,4],[3,5],[1,3]] 8
[[8,3],[6,5],[5,3],[3,3],[2,1]] 10
[[9,2],[8,4],[7,1],[6,4],[3,4]] 11
[[7,1],[5,3],[3,3],[2,5],[1,4]] 5
[[6,4],[5,3],[4,1],[2,3],[1,4]] 6
[[9,1],[6,3],[5,2],[3,1],[2,4]] 5
[[8,5],[7,4],[4,4],[3,3],[2,5]] 11
[[8,3],[7,1],[5,1],[3,2],[1,5]] 5
[[8,3],[7,4],[5,3],[3,5],[1,2]] 9
[[6,2],[5,1],[4,2],[3,3],[2,5]] 5
[[9,4],[6,3],[5,5],[3,5],[2,4]] 11
[[9,3],[8,1],[7,2],[5,5],[1,2]] 9
[[9,5],[8,4],[7,3],[2,4],[1,4]] 12
 
Ето и опростения вариант на моя код, че в ООП варианта има доста ненужни неща

PHP: 
<?php

const PIPE_LENGTH_MM = 6000;

$demand = [
    [5000, 20],
    [1000, 4],
    [100, 1],
];

print_r(calculatePipes($demand));

function calculatePipes(array $demand): array|int
{
    if (empty($demand)) return 0;

    $usedPipes = 0;
    $leftovers = [];

    usort($demand, fn($a, $b) => $b[0] - $a[0]);

    [$smallestDemandedPipe,] = $demand[sizeof($demand) - 1];

    foreach ($demand as [$requiredLength, $quantity]) {
        for ($i = 0; $i < $quantity; $i++) {
            [$pipeLength, $isNew] = findPipe($requiredLength, $leftovers, $smallestDemandedPipe);

            $usedPipes += (int)$isNew;

            $remainingLength = $pipeLength - $requiredLength;
            if ($remainingLength > 0) {
                $leftovers[] = $remainingLength;
            }
        }
    }

    return ['used pipes' => $usedPipes, 'leftovers' => array_count_values($leftovers)];
}

function findPipe(int $requiredLength, array &$leftovers, int $smallestDemandedPipe): array
{
    sort($leftovers);

    $totalLeftovers = sizeof($leftovers);
    for ($i = 0; $i < $totalLeftovers; $i++) {
        $leftoverLength = $leftovers[$i];

        if ($leftoverLength < $requiredLength) {
            continue;
        }

        $remainingLength = $leftoverLength - $requiredLength;
        if ($remainingLength > 0 && $remainingLength < $smallestDemandedPipe && $i < array_key_last($leftovers)) {
            continue;
        }

        array_splice($leftovers, $i, 1);

        return [$leftoverLength, false];
    }

    return [PIPE_LENGTH_MM, true];
}
 
Revelation каза:
Енумерациите си имат плюсовете, защото можеш да ги ползваш като тип. Ако създаваш константи, при тях не можеш да гарантираш типа, който може да искаш да зададеш на даден параметър или променлива. Типа ще ти остане примитивен и ще трябва да правиш допълнителни проверки, които можеш да оставиш на интерпретатора.

В Rust например енумерациите са доста мощни и полезни.
Увеличете...
И според мен енумерациите са полезни, говоря за това:
PHP: 
<?php

LogLevel::Debug < LogLevel::Info
 
pix3l каза:
И според мен енумерациите са полезни, говоря за това:
PHP: 
<?php

LogLevel::Debug < LogLevel::Info
Увеличете...
Не съм те разбрал правилно. При такива нива е по-лесно с такива сравнения, иначе ще паднат големи проверки.

@anonimen да сравним сега скорости? :D
 
Revelation каза:
@anonimen да сравним сега скорости? :D
Увеличете...
A не не, мойто решение е експоненциално по броя на тръбите, абсурд :D Дори за входове с дължина на demand по 5 и повече отнема по повече от няколко секунди, затова тестовете са такива орязани/къси. Написах го, просто защото е най-лесното, в което мога да съм сигурен, че е вярно.
Твойто като гледам е кубично at worst, просто няма база за сравнение :D
Трябва да ти го прочета да видя как точно го правиш.

Иначе супер за коректността.
 
anonimen каза:
A не не, мойто решение е експоненциално по броя на тръбите, абсурд :D Дори за входове с дължина на demand по 5 и повече отнема по повече от няколко секунди, затова тестовете са такива орязани/къси. Написах го, просто защото е най-лесното, в което мога да съм сигурен, че е вярно.
Твойто като гледам е кубично at worst, просто няма база за сравнение :D
Трябва да ти го прочета да видя как точно го правиш.

Иначе супер за коректността.
Увеличете...
Да не говорим, че Питоня се слави с бавните си loop-ове хаха.

  1. Завъртам деманда, като започвам от най-дългите парчета
  2. Въртя из изрезките (сортирани във възходящ ред) и търся подходяща тръба, която събира изискания размер
  3. Ако текущата изрезка е по-малка от изисканата, пропускам и пробвам следващата докато намеря по-дълга
  4. Ако намеря изрезка по-дълга от изисканата, проверявам дали, ако отрежа от нея ще ми остане парче, което е по-голямо или равно на най-късата тръба, която се изисква от текущия деманд
  5. Ако и последната тръба от изрезките идва по-къса от последната изискана, то я взимам понеже знам, че поне събирам това, което се изисква в момента
  6. Махам изрезката от масива и я връщам
  7. Ако не намеря читава тръба от изрезките, то връщам нова
  8. Ако ми останат изрезки, пъхам в масива с изрезки
 
На стъпки 4/5:
Revelation каза:
Ако и последната тръба от изрезките идва по-къса от последната изискана, то я взимам понеже знам, че поне събирам това, което се изисква в момента
Увеличете...
A това защо работи? И по принцип, защо точно този избор тук (от коя изрезка да вземеш) е най-добрият:
PHP: 
$remainingLength = $leftoverLength - $requiredLength;
if ($remainingLength > 0 && $remainingLength < $smallestDemandedPipe && $i < array_key_last($leftovers)) {
    continue;
}

array_splice($leftovers, $i, 1);

return [$leftoverLength, false];

С алчен алгоритъм ми беше първата мисъл още в началото:
anonimen каза:
На всяка итерация гледаш най-дългата тръба от demandа, взимаш най-късата тръба от supply'я, която я побира, и режеш от нея.
Увеличете...
обаче това невинаги е най-добрият избор.
Ти си го адаптирал до
"за най-дългата тръба от demanda, взимаш най-късата тръба от supplyя, която я побира, но само ако това, което остане при изрязването, не може да се ползва по-натам."
Увеличете...
Но пак, защо това го прави най-добрия избор?

Сега като го гледам, почнах да се чудя дали не можеш във find_pipe с двоично търсене да свалиш сложността на иначе линейния цикъл до логаритмична. За целта ще трябва да махнеш sort'a преди него обаче, и да ползваш за leftovers вечно сортирана структура с ефективно добавяне/триене.
 
Хмм, я провери с този пример: две 4ки и четири 3ки при supply от тръби с дължина 10.
Оптималното решение е с две тръби: всяка я режеш на 4 + 3 + 3. Твоят алгоритъм обаче като го приложа, реже втората четворка от изрезката, останала след първата, т.е. реже от 6тицата.
И в сандбокса като го пуснах, на [[4,2],[3,4]] 3 изкара true, а на [[4,2],[3,4]] 2 - false.
Проблемът е в условието "$i < array_key_last($leftovers)", което киква в случая и не те оставя да вземеш нова тръба за втората 4ка. Пробвах да го махна, но тогава фейлват други тестове.
 
Всъщност май фундаменталния проблем тука е, че се опитва с "локално" знание да вземе "глобално" най-добър избор. Тоест, опитваш се да избереш изрезка на база единствено дължината на тръбата, която режеш, но не взимаш предвид останалите тръби, които ще трябва да изрежеш в последствие. Например:

В случая - имаш две 4ки, и на втората решаваш - използвайки локалното знание само за нейната дължина (4) и текущите изрезки (една 6ица), че е по-добре да я вземеш от шестицата. Тоест правиш алчен алгоритъм, което в тая задача не работи :(

Тъпото е, обаче, че единственият коректен алгоритъм (изглежда), който имаме, е твърде бавен, за да генерираме достатъчно много тестове :D
 
Тъкмо пишех, че за това имам съмнения, че ще има случаи, в които вероятно няма да работи и ти през това време даде такъв пример, хаха.

Честно казано, в последно време мозъка ми мисли само архитектурно на работа и малко ми забива мозъка с алгоритмични задачи.

В момента даже не мога да замисля друго решение, което би било бързо и коректно.
 
Тоест, @uphero ще трябва да се задоволиш или с бавен (рекурсивния, който дадох по-горе), или с неточен алгоритъм. C'est la vie :).
За второто, варианти бол - в статията в уикипедия има линкове с имплементации най-долу.

Както пишат тук https://stackoverflow.com/questions/23922557/algorithm-for-pipe-cutting-optimization, вариант е да вземеш алгоритъма на автора, който е "sometimes known as the first-fit decreasing algorithm"1. That algorithm is designed for speed, but does not always result in an optimal solution.
 
Интересно ми е твоето решение при по-голям деманд колко би се бавило. До няколко секунди си е все още търпимо. Ако стигаме минута и нагоре, тогава вече става грозно хаха.
 
Зависи колко са големи входовете на uphero.

Например при тръби по 10м, demand [(8, 4), (5, 1), (3, 1), (2, 5), (1, 5)], [(10, inf)] отнема феноменалните...
$ time python webtourist_pipes.py
6
python webtourist_pipes.py 4,75s user 0,01s system 99% cpu 4,762 total
Увеличете...
5 секунди :D

Не мога да преценя добре в кои случаи се бави много. Друг пример с подобна дължина минава веднага: [(8, 2), (7, 3), (6, 5), (4, 5), (2, 1)] (отново 5 вида тръби).
Или пък [(7, 2), (5, 3), (4, 3), (3, 5), (1, 5)] отнема... 125s :D
Някакво практично решение може да бъде да си подготви кеш с готови сметнати конфигурации, ако са малки входовете.
 
anonimen каза:
Зависи колко са големи входовете на uphero.

Например при тръби по 10м, demand [(8, 4), (5, 1), (3, 1), (2, 5), (1, 5)], [(10, inf)] отнема феноменалните...

5 секунди :D

Не мога да преценя добре в кои случаи се бави много. Друг пример с подобна дължина минава веднага: [(8, 2), (7, 3), (6, 5), (4, 5), (2, 1)] (отново 5 вида тръби).
Или пък [(7, 2), (5, 3), (4, 3), (3, 5), (1, 5)] отнема... 125s :D
Някакво практично решение може да бъде да си подготви кеш с готови сметнати конфигурации, ако са малки входовете.
Увеличете...
Вероятно в случаите, където имаш размери, които оставят голям брой изрезки, през които трябва да минеш рекурсивно. Но 125 секунди са си убийство.

Остави малко логове тук и там, и ще си покаже къде се бави.

Но твоя пример на питон много ме бъгва. Това с inf ме хвърля в тъча леко и някои части ми се струват странно написани. :D
 
Аа inf'инитито е голямо удобство :D
Позволява без излишна допълнителна логика да взимам по един и същи начин тръби от безкрайния и крайния supply (ако имам безброй тръби с дължина 6 и пет тръби с дължина 3, то и в двата случая правя `pipe_count - 1`, за да "взема" тръба от new_supply).

Демо https://ideone.com/4G4Nay

А иначе къде се бави е ясно - в ужасно многото на брой рекурсивни извиквания.
Например в [(8, 4), (5, 1), (3, 1), (2, 5), (1, 5)] (при supply с дължина 10), втората тръба 5 може да я вземе от нова или от изрезката на първата. Във всеки от двата случая третата петица има още 2 варианта, и докато стигнем до единицата получаваме гигантско дърво на възможности. Не знам дали някои от тях не могат да се орежат, но пак, това няма да промени експоненциалността на нарастването.

Прикачам файла с отпечатани рекурсивните извиквания (с аргументите си) за този пример. Редовете в него са 2.4 милиона, поради което и не можах да го пейстна в pastebin Освен това се оказа, че е в суров вид е 250МБ, та се наложи да го зипна. Нещо не успявам да го прикача. Да не би 4.5МБ да му е много на форума? Ето го в някакъв произволен сайт https://file.io/sP93PPaNEXVb изтича след 2 седмици. След това може да си го генерирате от сорса в по-горния линк.

Ако не ви се тегли, файлът изглежда така:

PHP: 
Making [(8, 4), (5, 1), (3, 1), (2, 5), (1, 5)] with [(10, inf)]
   Making [(8, 3), (5, 1), (3, 1), (2, 5), (1, 5)] with [(10, inf), (2, 1)]
      Making [(8, 2), (5, 1), (3, 1), (2, 5), (1, 5)] with [(10, inf), (2, 2)]
         Making [(8, 1), (5, 1), (3, 1), (2, 5), (1, 5)] with [(10, inf), (2, 3)]
            Making [(5, 1), (3, 1), (2, 5), (1, 5)] with [(10, inf), (2, 4)]
               Making [(3, 1), (2, 5), (1, 5)] with [(10, inf), (5, 1), (2, 4)]
                  Making [(2, 5), (1, 5)] with [(10, inf), (7, 1), (5, 1), (2, 4)]
                     Making [(2, 4), (1, 5)] with [(10, inf), (8, 1), (7, 1), (5, 1), (2, 4)]
                        Making [(2, 3), (1, 5)] with [(10, inf), (8, 2), (7, 1), (5, 1), (2, 4)]
                           Making [(2, 2), (1, 5)] with [(10, inf), (8, 3), (7, 1), (5, 1), (2, 4)]
                              Making [(2, 1), (1, 5)] with [(10, inf), (8, 4), (7, 1), (5, 1), (2, 4)]
                                 Making [(1, 5)] with [(10, inf), (8, 5), (7, 1), (5, 1), (2, 4)]
                                    Making [(1, 4)] with [(10, inf), (9, 1), (8, 5), (7, 1), (5, 1), (2, 4)]
                                       Making [(1, 3)] with [(10, inf), (9, 2), (8, 5), (7, 1), (5, 1), (2, 4)]
                                          Making [(1, 2)] with [(10, inf), (9, 3), (8, 5), (7, 1), (5, 1), (2, 4)]
                                             Making [(1, 1)] with [(10, inf), (9, 4), (8, 5), (7, 1), (5, 1), (2, 4)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                             Making [(1, 1)] with [(10, inf), (9, 2), (8, 6), (7, 1), (5, 1), (2, 4)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                             Making [(1, 1)] with [(10, inf), (9, 3), (8, 4), (7, 2), (5, 1), (2, 4)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                             Making [(1, 1)] with [(10, inf), (9, 3), (8, 5), (6, 1), (5, 1), (2, 4)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                             Making [(1, 1)] with [(10, inf), (9, 3), (8, 5), (7, 1), (4, 1), (2, 4)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                             Making [(1, 1)] with [(10, inf), (9, 3), (8, 5), (7, 1), (5, 1), (2, 3), (1, 1)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0, 0]
                                          Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                          Making [(1, 2)] with [(10, inf), (9, 1), (8, 6), (7, 1), (5, 1), (2, 4)]
                                             Making [(1, 1)] with [(10, inf), (9, 2), (8, 6), (7, 1), (5, 1), (2, 4)]
                                             Best option is 0 out of [1, 0, 0, 0, 0, 0]
                                             Making [(1, 1)] with [(10, inf), (8, 7), (7, 1), (5, 1), (2, 4)]
 
Трябва да си влезнал или регистриран, за да отговориш тук.

Back
Горе