Escada Perfeita - Desafio 2306 URI

README.md

Escada Perfeita

URI Online Judge | 2306

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de vários pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem rearranjadas no formato de “escada”. Para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha e outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Dada uma sequência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro N que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

main.py

from functools import reduce


def init():
    columns = _make_columns()
    total_cubes = reduce(_sum, columns)
    initial_value = _get_initial_value_of_ladder(1, total_cubes, columns)
    if initial_value:
        print('Deslocamentos nescessários: ', _calculate_the_amount_of_displacement(columns, 0, initial_value, 0))
    else:
        print(-1)


def _make_columns():
    amount_columns = int(input('Insira a quantidade de colunas: '))
    return _make_column(amount_columns, [])


def _make_column(remaining_columns, columns):
    if remaining_columns == 0:
        return columns
    column = int(input(f'Insira número de cubos da { _increase(len(columns)) }º coluna: '))
    return _make_column(_decrease(remaining_columns), _add(columns, column))


def _get_initial_value_of_ladder(initial_value, total_cubes, columns):
    number_of_cubes = _calculate_number_of_cubes_by_initial_value(initial_value, 0, columns)
    if number_of_cubes < total_cubes:
        return _get_initial_value_of_ladder(_increase(initial_value), total_cubes, columns)
    if number_of_cubes == total_cubes:
        return initial_value


def _calculate_number_of_cubes_by_initial_value(number_of_cubes, current_column, columns):
    if current_column < len(columns) - 1:
        return number_of_cubes + _sum_cubes_in_column(number_of_cubes, current_column, columns)
    return number_of_cubes


def _sum_cubes_in_column(number_of_cubes, current_column, columns):
    return _calculate_number_of_cubes_by_initial_value(_increase(number_of_cubes), _increase(current_column), columns)


def _sum_displacements(displacements, cubes, ideal_number_of_cubes):
    displacement = cubes - ideal_number_of_cubes
    if displacement > 0:
        return _sum(displacements, displacement)
    return displacements


def _calculate_the_amount_of_displacement(columns, index, ideal_value, displacements):
    if index == len(columns):
        return displacements
    cubes = columns[index]
    return _calculate_the_amount_of_displacement(
        columns,
        _increase(index),
        _increase(ideal_value),
        _sum_displacements(displacements, cubes, ideal_value)
    )


def _sum(x, y):
    return x + y


def _increase(value):
    return value + 1


def _decrease(value):
    return value - 1


def _add(columns, column):
    return columns + [column]


if __name__ == '__main__':
    init()