A programação competitiva é uma ótima maneira de dominar uma linguagem de programação específica. Mesmo que você não esteja interessado em competir em eventos mundiais, como o Facebook Hacker Cup, resolver problemas complexos de algoritmo usando nada além do básico de uma linguagem te expõe a aspectos que você normalmente não veria, como o quão eficiente certos métodos/operações são e como codar alternativas melhores. Esse é um passatempo legal de se ter, e como um bônus, você estará se tornando um solucionador de problemas melhor.

Por mais que, em uma competição real, codar em Swift seja uma grande desvantagem –  por ela ser relativamente lenta em comparação com outras linguagens e ter poucas estruturas de dados nativas, muitas plataformas online populares como LeetCode, HackerRank e Codefights suportam Swift e são uma ótima maneira para se tornar um melhor desenvolvedor iOS, especialmente porque problemas competitivos só aceitarão algoritmos muito rápidos como soluções possíveis. Se você nunca acessou uma dessas plataformas, recomendo dar uma olhada.

Neste artigo, veremos como usar o Swift para ler dados de entrada e darei algumas dicas para lidar com problemas competitivos na linguagem.

Leitura de entrada padrão com Swift

Na programação competitiva, o input do problema geralmente é inserido em um aplicativo de linha de comando, que por sua vez faz algum sentido daquilo e imprime o resultado desejado.
Plataformas como LeetCode e CodeFights processam automaticamente os dados de entrada e expõem um método vazio que deve retornar a solução do problema, mas outras plataformas como o HackerRank irão, às vezes, pedir para que você faça manualmente esse processo. Felizmente, isso não é tão complexo quanto parece.

Para simular um ambiente de programação competitiva, crie um projeto de Command Line Tool no Xcode:

Imagem1

Esteja ciente de que uma Command Line Tool não é um aplicativo Cocoa, então você não terá acesso a coisas como o UIKit! Os frameworks centrais como o Foundation são tudo o que você tem aqui.

No main.swift, digite e execute o seguinte código:

Neste ponto, o programa congelará. readLine() é um método da Biblioteca Padrão que lê de forma síncrona a entrada padrão e retorna uma String? uma vez que uma linha completa é encontrada ou nil se EOF for alcançado.
Se você digitar algo no console do Xcode, a execução do programa continuará e imprimirá o que você escreveu:

Imagem2

No entanto, um problema de programação competitiva provavelmente terá várias centenas de linhas de entrada. Você pode usar um loop while para fazer seu código continuar até que a entrada termine:

Imagem3

Isso é tudo que você precisa saber para começar. A partir daqui, sua habilidade com o Swift é a única variável.

Se você nunca fez isso antes, aqui vai um problema exemplo:

Exemplo de problema

Dado uma lista de inteiros, encontre a soma de seus elementos.

Formato de entrada

A primeira linha contém um inteiro, denotando o tamanho da lista.

A segunda linha contém n inteiros separados por espaços representando os elementos da lista.

Formato de saída

Imprima a soma dos elementos da lista como um único inteiro.

Amostra de entrada

Amostra de saída

Solução

Todo problema tem várias soluções possíveis. Nesse caso, podemos nos aproveitar do poder de reduce:

Dicas de Swift para Programação Competitiva

A beleza da programação competitiva é que apenas resolver o problema não é suficiente, seu programa deve resolvê-lo o mais rápido possível.
Há muito o que falar sobre a complexidade do tempo de execução, mas esta seção cobrirá apenas dicas de Swift que são úteis quando as coisas precisam ser rápidas.

Use operadores de Overflow

O Swift naturalmente protege você do overflow de números ao custo de um pouco de desempenho. Isso pode custar-lhe alguns nano-segundos valiosos, e alguns problemas podem até querer que você cause overflow. Felizmente, o Swift tem operadores aritméticos especiais que ignoram as verificações de overflow, tornando-os mais rápidos que os operadores normais:

Imprimir é devagar

O método print(_:) é muito lento e pode ser particularmente doloroso ao imprimir coisas como Arrays. Você pode ganhar algum desempenho se imprimir tudo de uma vez.

Alocar capacidades de lista antecipadamente

Os Arrays do Swift têm tamanhos dinâmicos, o que significa que a linguagem aloca automaticamente mais memória para ele à medida que aumenta de tamanho. Mesmo que isso seja muito rápido, você pode torná-lo ainda mais eficiente se conhecer o tamanho da lista antecipadamente usando o método:

Isso é útil se você tiver um problema em que a solução seja  uma lista com um tamanho específico.

Como alternativa, você pode usar o inicializador repeating:count: quando precisar de uma lista pré-preenchida:

Abuse de opcionais implicitamente desembrulhados

Enquanto o temido ! deve ser evitado em aplicações reais, segurança não é uma preocupação na programação competitiva. Como é garantido que as entradas serão sempre as mesmas, você pode ignorar completamente o overhead de desembrulhar tipos opcionais.

Use o inout

Usar argumentos inout pode ser muito útil para passar dados em funções recursivas, e eu pude confirmar que os argumentos inout são ainda mais rápidos de serem criados do que os normais ao passar tipos de valor que possuem tipos referências internas.

Subtraia Dates para medir desempenho – Rodrigo Carvalho

O código a seguir medirá quanto tempo leva para executar algo:

Isso pode ser útil quando você tem várias abordagens e não sabe qual delas é a mais rápida. Certifique-se de executar isso com as otimizações ativadas para medir corretamente trechos diferentes de código, pois a maioria dos truques do compilador do Swift exige isso.

Swift Algorithm Club

A maioria dos problemas de programação competitiva dependerá de uma estrutura de dados específica e, como o Swift infelizmente não tem suporte nativo para a maioria deles, isso significa que você terá que codificá-los.

Felizmente, o repositório swift-algorithm-club tem implementações Swift de praticamente tudo, tornando-o um ótimo lugar para aprender como codar estruturas de dados populares em Swift.

O que mais?

Independentemente se você está estudando para uma entrevista, querendo competir em eventos mundiais ou apenas tentando ser um desenvolvedor iOS melhor, resolver problemas de programação competitiva é uma maneira muito interessante de aumentar suas habilidades com o Swift. Eu pessoalmente me beneficiei muito com isso e adoraria saber o que você pensa a respeito.

Referências

Blog Swift Rocks
Big O Notation
Performant Arrays In Swift
Apple Docs: readLine()

Management of Rapiddo Marketplace’s iOS team, while still developing the app myself.

Posted by:Bruno Rocha

Management of Rapiddo Marketplace's iOS team, while still developing the app myself.

Deixe seu comentário