Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Based on Fibonacci + RU Comments solution in Uncategorized category for Stair Steps by pyhappy
# migrated from python 2.7
from collections import defaultdict
import random
"""
При создании алгоритма я построил дерево решений сначала на бумаге, и
обнаружил интересную закономерность: на одном вертикальном уровне
количество нулей (0 – значение при перешагивании через эту ступень) и
количество цифр (значение ступени, при наступании на ступень)
подчиняется закону Фибоначчи (подробнее см ф-ции zeros_tree ,
digits_tree ).
При переводе дерева решений в матрицу решений, понадобился коэффициент
трансформации количества нулей и цифр в одной колонке, как оказалось
он тоже подчинялся закону Фибоначчи, но немного по-иному (подробнее см
ф-ции zeros_coeff , digits_coeff ).
Итоговое количество нулей и цифр в колонке я вычислил, умножив эти
значения (подробнее см ф-ции zeros_number , digits_number ).
Таким образом стало известно количество нулей ( перешагиваний через
ступень ) и количество цифр (наступаний на ступень ) на каждом уровне
(колонке) матрицы решений, и тем самым (сложив эти два числа) –я
получил число строк (вариантов) в матрице. Количество столбцов – это
количество ступеней, на которых есть значения, те кроме верхней и
нижней площадок.
Теперь, когда размеры матрицы известны, можно начинать ее заполнение
справа налево. Я начал с последней колонки, заполнил ее нулями и
цифрами (значениями последней ступени) произвольным образом, но при
этом соблюдая их количество нулей и цифр, в соответствии со значениями
с ф-ций zeros_number , digits_number .
Заполнив последнюю колонку, я перешел на следующую колонку, те
предпоследнюю. На ней также известно количество нулей и цифр, однако,
принцип их распределения более сложный.
Сначала для данной (предпоследней) колонки я построил два словаря со
значениями всех ячеек справа нее в качестве ключа и количеством их в
качестве значения. Таким образом, я получил словари, в котором
указаны различные варианты строк справа и количество их встречания в
данной колонке.
Затем, зная количество нулей и цифр, которое должно быть в текущей
колонке, я модифицировал словари, чтобы в качестве Value его стало
количество нулей, или цифр которое должно быть в данной колонке при
данном наборе ячеек справа.
Затем пройдя в цикле по этой колонке я выставил требуемое количество
нулей и цифр в соответствии с набором ячеек справа.
Еще одно примечание, которое я использовал, что если у ячейки справа
стоит 0 (те на нее не наступали, а перешагнули), то, следовательно,
текущая ячейка должна быть со значением, т.к. по условию задачи нельзя
переступать через две ступени.
Остальные действия для других колонок (справа налево) выполняются по
тому же принципу, что и для предпоследней колонки.
Результат вычисляется как ряд в матрице решений, в котором сумма
элементов будет максимальна.
"""
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return (a)
# Getting number of zeros in tree with 'row' number
def zeros_tree(col):
return fib(col)
# Getting number of digits in tree with 'row' number
def digits_tree(col):
return fib(col+1)
# Getting coefficient for zeros number in matrix col number with total columns
def zeros_coeff(col,total):
return fib(total-col+1)
# Getting coefficient for digits number in matrix col number with total columns
def digits_coeff(col,total):
return fib(total-col+2)
# Getting real number of zeros in matrix column with total columns
def zeros_number(col,total):
return zeros_tree(col)*zeros_coeff(col,total)
# Getting real number of digits in matrix column with total columns
def digits_number(col,total):
return digits_tree(col)*digits_coeff(col,total)
# Getting number of rows in result matrix
def get_rows_number(max_column):
return zeros_tree(max_column)+ digits_tree(max_column)
def print_results(m,stair_values):
# Printing results
print("")
bestway = [int(bool(i)) for i in m]
text_bestway = text(bestway,stair_values)
print("")
print(("STAIR VALUES = %s" % stair_values ))
print(("BEST WAY = %s" % bestway))
print(("BEST ROW VALUES = %s" % m ))
print(("SUM OF BEST ROW = %s" % sum(m) ))
print("")
print(("TEXT DESCRIPTION: %s" %text_bestway))
# Getting text description of the way
def text(bool_list,values):
result=[]
for i,n in enumerate(bool_list):
if n : result.append("go to %s stair(%s)" % (i+1,values[i]))
else: result.append("jupm through %s stair(%s)" % (i+1,values[i]))
return "First "+ ", then ".join(result)
# Main function
def checkio(stair_values):
n=len(stair_values)
rows=get_rows_number(n)
# dict of pairs on the right side
dic_digits_pairs = defaultdict(int)
dic_zeros_pairs = defaultdict(int)
# Generating None matrix for tree results
m = [[None for j in range(n)] for i in range(rows)]
# Filing last column
digits = digits_number(n,n)
for j in range(rows):
if j < digits:
m[j][n-1] = stair_values[n-1]
else: m[j][n-1] = 0
# Filing other columns with zeros and digits
for i in range(n-2,-1,-1):
zeros_count = zeros_number (i+1,n)
digits_count = rows-zeros_count
dic_zeros_pairs.clear()
dic_digits_pairs.clear()
#collecting list of pairs on the right side
for j in range(rows):
pair = str(m[j][i+1:])
if m[j][i+1] !=0:
dic_zeros_pairs[pair] += 1
dic_digits_pairs[pair] += 1
else:
dic_digits_pairs[pair] += 1
#counting number of zeros for each pair
number_zeros_pairs = sum(dic_zeros_pairs.values())
for pair in dic_zeros_pairs:
dic_zeros_pairs[pair] *= zeros_count/float(number_zeros_pairs)
dic_digits_pairs[pair] -= dic_zeros_pairs[pair]
#counting number of digits for each pair
number_digits_pairs = sum(dic_digits_pairs.values())
for pair in dic_digits_pairs:
dic_digits_pairs[pair] *= digits_count/float(number_digits_pairs)
#filing zeros and digits in column
for j in range(rows):
pair = str(m[j][i+1:])
if m[j][i+1] !=0:
if pair in dic_zeros_pairs:
if dic_zeros_pairs[pair]>0:
dic_zeros_pairs[pair]-=1
m[j][i]=0
continue
else:
m[j][i]=stair_values[i]
dic_digits_pairs[pair]-=1
continue
#filing digits in column
elif pair in dic_digits_pairs:
if dic_digits_pairs[pair]>0:
dic_digits_pairs[pair]-=1
m[j][i]=stair_values[i]
sum_info = [sum(s) for s in m]
max_row_sum = max(sum_info)
max_row_id = sum_info.index(max_row_sum)
best_row_values = m[max_row_id]
# Uncomment this to print result in more comfortable view
#print_results(best_row_values,stair_values)
return sum(best_row_values)
if __name__ == '__main__':
assert checkio([5,6,-10,-7,4]) == 8, 'First'
assert checkio([-11, 69, 77, -51, 23, 67, 35, 27, -25, 95])==393, 'Second'
assert checkio([-21, -23, -69, -67, 1, 41, 97, 49, 27])==125, 'Third'
assert checkio([5,-3,-1,2]) == 6, 'Fifth'
print('All ok')
April 23, 2012
Comments:
