Rangoli antes e depois de colorido

Alfabeto Geométrico

O problema de hoje é simples, então não se assuste caso a solução não seja óbvia em um primeiro instante. Vamos construir o Alfabeto Geométrico (AG) passo-a-passo, assim como os subproblemas que devem ser solucionados para chegarmos na saída desejada.

Problema:

Dado um inteiro n, a tarefa consiste em criar um alfabeto geométrico de tamanho n.

Entrada:

  • Um inteiro n, tal que, 0 < n <= 26

Saída:

  • Um alfabeto geométrico
          N = 7 
------------g------------
----------g-f-g----------
--------g-f-e-f-g--------
------g-f-e-d-e-f-g------
----g-f-e-d-c-d-e-f-g----
--g-f-e-d-c-b-c-d-e-f-g--
g-f-e-d-c-b-a-b-c-d-e-f-g
--g-f-e-d-c-b-c-d-e-f-g--
----g-f-e-d-c-d-e-f-g----
------g-f-e-d-e-f-g------
--------g-f-e-f-g--------
----------g-f-g----------
------------g------------

                        N = 14
--------------------------n--------------------------
------------------------n-m-n------------------------
----------------------n-m-l-m-n----------------------
--------------------n-m-l-k-l-m-n--------------------
------------------n-m-l-k-j-k-l-m-n------------------
----------------n-m-l-k-j-i-j-k-l-m-n----------------
--------------n-m-l-k-j-i-h-i-j-k-l-m-n--------------
------------n-m-l-k-j-i-h-g-h-i-j-k-l-m-n------------
----------n-m-l-k-j-i-h-g-f-g-h-i-j-k-l-m-n----------
--------n-m-l-k-j-i-h-g-f-e-f-g-h-i-j-k-l-m-n--------
------n-m-l-k-j-i-h-g-f-e-d-e-f-g-h-i-j-k-l-m-n------
----n-m-l-k-j-i-h-g-f-e-d-c-d-e-f-g-h-i-j-k-l-m-n----
--n-m-l-k-j-i-h-g-f-e-d-c-b-c-d-e-f-g-h-i-j-k-l-m-n--
n-m-l-k-j-i-h-g-f-e-d-c-b-a-b-c-d-e-f-g-h-i-j-k-l-m-n
--n-m-l-k-j-i-h-g-f-e-d-c-b-c-d-e-f-g-h-i-j-k-l-m-n--
----n-m-l-k-j-i-h-g-f-e-d-c-d-e-f-g-h-i-j-k-l-m-n----
------n-m-l-k-j-i-h-g-f-e-d-e-f-g-h-i-j-k-l-m-n------
--------n-m-l-k-j-i-h-g-f-e-f-g-h-i-j-k-l-m-n--------
----------n-m-l-k-j-i-h-g-f-g-h-i-j-k-l-m-n----------
------------n-m-l-k-j-i-h-g-h-i-j-k-l-m-n------------
--------------n-m-l-k-j-i-h-i-j-k-l-m-n--------------
----------------n-m-l-k-j-i-j-k-l-m-n----------------
------------------n-m-l-k-j-k-l-m-n------------------
--------------------n-m-l-k-l-m-n--------------------
----------------------n-m-l-m-n----------------------
------------------------n-m-n------------------------
--------------------------n--------------------------

Casos de Testes

Dada a natureza do problema, podemos limitar nossos casos a 3 testes:

  • Valores de n menores do que 1 ou maior que 26, retornam erro;
  • n = 7 tem saída igual ao valor supracitado;
  • n = 14 […]

Antes de ler o resto, sugiro que você pare um pouco e pense sobre o problema. Use papel e caneta ou só a cabeça mesmo, mas tente enumerar as características do problema e os elementos que você julgue ser necessário para solução.


Solução

Antes de mais nada, é preciso dizer que existem diversas formas de se atacar o problema. Vou apresentar somente uma dentre essas.

De cara, a primeira coisa que conseguimos notar é que o valor de n está diretamente relacionado com a quantidade de letras do alfabeto que usaremos. Ou seja, para n=3, temos L = [‘a’, ‘b’, ‘c’]; n=7 temos L = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’].

Podemos então escrever nossa propria lista L = [‘a’, ‘b’,…,’z’] ou, em python, utilizar ascii_lowercase do módulo string para esse propósito.

import string

n = 7
letters = list(string.ascii_lowercase[:n])

print(letters)
>>> ['a', 'b', 'c', 'd', 'e', 'f', 'g']

Agora que sabemos a relação de n com as letras, qual outra informação nós conseguimos tirar disso? Vamos utilizar o primeiro exemplo como base, onde para n=7, temos na linha central do losango:

g-f-e-d-c-b-a-b-c-d-e-f-g

E que contém os itens:

[‘a’, ‘b’, ‘b’, ‘c’, ‘c’, ‘d’, ‘d’, ‘e’, ‘e’, ‘f’, ‘f’, ‘g’, ‘g’]

Vamos utilizar essa informação para gerar uma expressão que nos forneça a largura do AG de acordo com o valor de n. Podemos observar que todas as letras aparecem duas vezes, menos a primeira, então sabemos que parte da expressão deve conter ((2 * n)  – 1), que corresponde a quantidade de letras. Mas e os traços entre as letras? A quantidade de traços é sempre igual a quantidade de letras, menos um. Podemos então sintetizar nossa fórmula para o cáculo da largura como sendo:

width = (((n * 2) - 1) * 2) - 1

 


Screen Shot 2016-08-17 at 15.05.30

Figura 1 – Triângulo

Utilizando somente a parte superior do AG, podemos observar que existem n linhas, onde para cada i em linhas, usamos exatamente i letras distintas, e em ordem decrescente.

Podemos também observar que as letras estão sempre centralizadas e separadas por um hífen (“-“).

A segunda metade é igual a primeira metade, menos a última linha e na ordem inversa.

Transformando [‘g’, ‘f’, ‘g’] em “g-f-g”

O que nós queremos se traduz no ato de concatenar os elementos de um iterável com uma determinada string. Para isso, em python, podemos utilizar o método join de strings.

print( "-".join(['g', 'f', 'g']) )
&gt;&gt;&gt; "g-f-g"

Para criarmos uma função com comportamento igual a este join, basta que receba como entrada uma lista a_list e uma string text a ser concatenada com cada um dos elementos, menos o último.

def functional_join(a_list: list, text='') -> str:
    result = ""
    last_index = len(a_list) - 1

    for index, value in enumerate(a_list):
        result += value
        if index != last_index:
            result += text

    return result

Obs.:  Como o objetivo é didático, a função presume que os itens da lista de entrada também são strings. (use join!)
Obs.2: Se você quiser tentar criar sua própria solução, lembre-se que é importante testar se o resultado é válido para: listas vazias, listas com 1 elemento, listas de tamanho par e ímpar.


Centralizando strings em um espaço

Em python, centralizar uma string é tarefa bem fácil se utilizarmos o método format. Por exemplo, para a primeira linha da nossa AG:

print( "{:-^{width}}".format("g", width=width) )
>>> '------------g------------'

Como nosso objetivo não é só aprender sintaxe, vamos construir nossa solução para enteder a lógica!

Se considerarmos uma string como uma lista de caracteres, para centralizarmos um único caracter em uma determinada extensão (nosso width), basta acharmos o ponto central desta lista e atribuirmos a este índice o valor do caracter desejado e, a todos os outros, o hífen.

O mesmo raciocínio não pode ser aplicado em sua totalidade para uma solução genérica, capaz de centralizar n caracteres. Para descobrir em qual índice da nossa string de saída está o primeiro caracter da nossa entrada, também precisamos levar em consideração o tamanho da string a ser centralizada. Entendendo isso, escrever um solução se torna mais trivial.

from collections import deque

def center(text: str, width: int, fill='-') -> str:
    assert width >= len(text)

    queue = deque(text)
    text_start_i = int((width - len(text)) / 2)
    centered = []

    for i in range(width):
        if (i >= text_start_i) and queue:
            centered.append(queue.popleft())
        else:
            centered.append(fill)

    return functional_join(centered)

Nesta função utilizamos deque de collections, uma estrutura FIFO que atende bem ao nosso propósito.

Montando o AG

Agora que já sabemos centralizar as letras preenchendo os cantos com uma string e concatenar os elementos, basta entender a lógica dos níveis.

Screen Shot 2016-08-17 at 16.54.36

Figura 2: Primeiro quadrante

Screen Shot 2016-08-17 at 16.55.12

Figura 3: Segundo quadrante

Podemos observar no primeiro quadrante (metade esquerda do triângulo), que os elementos utilizados são resultado de uma iteração em ordem inversa sobre a lista original, com limite diretamente relacionado ao nível. Entendendo como montar as listas para ambas as partes, basta somá-las e aplicar as funções que vimos nas etapas anteriores.

 

 

Seguindo esse raciocínio, podemos escrever uma solução nesta linha:

def items_for_depth(a_list: list, depth: int) -> list:
    left = [a_list[l] for l in range(0, depth + 1)]
    right = [a_list[l] for l in reversed(range(0, depth))]

    return left + right

print(items_for_depth(letters, 5))
>>> ['g', 'f', 'e', 'd', 'c', 'b', 'c', 'd', 'e', 'f', 'g']

Obs.: Tendo em vista que essa função é chamada ((2*n) – 1) vezes, para tamanhos de n muito grandes (que não é nosso caso), o custo das operações de alocações e somas de listas pode pesar na performace da solução, podendo ser substituídas por expressões geradoras e uma operação de chain.


Agora basta juntar todas as partes, e temos a nossa solução para imprimir uma linha, dada a profundidade:

def print_line(depth):
    global width
    items = items_for_depth(letters, depth)

    line_content = functional_join(items, '-')
    print(center(line_content, width))

As linhas 5 e 6 podem ser substituídas pelas soluções já existentes na linguagem:

    line = '-'.join(items)
    print('{:-^{width}}'.format(line, width=width))

Tudo que precisamos fazer agora é chamar a função print_line na ordem correta e observar o output no console.

for depth in range(n):
    print_line(depth)

for depth in reversed(range(n-1)):
    print_line(depth)

Conclusão

Se você leu até aqui, espero que tenha gostado do desafio. Esse post ficou bem mais longo do que eu esperava e espero não ter ficado muito cansativo 😛
Ficou com alguma dúvida? Alguma parte poderia ser melhor explicada? Você implementou de uma outra forma ou em uma outra linguagem e gostaria de compartilhar? Deixe um comentário ou entre em contato direto comigo.

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s