Fundo:
O MtDNA é uma parte do DNA humano que é transmitido de mãe para filho e raramente sofre mutação. Como isso é verdade para todos os seres humanos, é possível criar uma árvore enorme que visualize como todos os seres humanos se relacionam através de seus ancestrais maternos, desde a hipotética EVE. Toda mutação no MtDNA quando um filho nasce cria um novo sub-ramo a partir do seu ramo pai na árvore.
Saiba mais sobre o DNA mitocondrial (mtDNA) aqui: https://en.wikipedia.org/wiki/Mitochondrial_DNA
Objetivo:
Seu programa recebe uma lista de contagens de mutações nos galhos de árvores mtDNA e seu programa deve fornecer uma visualização em árvore
Exemplo de entrada e saída:
A entrada é uma tabela separada por ponto e vírgula de 3 colunas com uma linha para cada ramificação. Exemplo:
L0a'b'f'k;L0;14
L0a'b'f;L0a'b'f'k;23
L0;mtEVE;10
L0a'b;L0a'b'f;30
L0a;L0a'b;38
L0a1'4;L0a;39
L0a1;L0a1'4;40
L0a1a;L0a1;42
L0a1a NL;L0a1a;43
L0a1a1;L0a1a NL;44
L0a1a2;L0a1a NL;45
L0a1a3;L0a1a NL;44
L0a1 NL;L0a1;41
L0a1b;L0a1 NL;44
L0a1b NL;L0a1b;45
L0a1b1;L0a1b NL;46
L0a1b1a;L0a1b1;47
L0a1b1a1;L0a1b1a;48
L0a1b2;L0a1b NL;48
L0a1b2a;L0a1b2;50
L0a1c;L0a1 NL;45
L0a1d;L0a1 NL;44
L0a4;L0a1'4;55
L0a2;L0a;47
L0a2a;L0a2;49
L0a2a1;L0a2a;50
L0a2a1a;L0a2a1;51
L0a2a1a1;L0a2a1a;53
L0a2a1a2;L0a2a1a;53
L0a2a2;L0a2a;53
L0a2a2a;L0a2a2;54
L0a2b;L0a2;57
L0a2b1;L0a2b;58
L0a2c;L0a2;60
L0a2d;L0a2;49
L0a3;L0a;53
L0b;L0a'b;48
L0f;L0a'b'f;37
L0f1;L0f;61
L0f2;L0f;41
L0f2a;L0f2;46
L0f2a1;L0f2a;59
L0f2b;L0f2;63
L0k;L0a'b'f'k;39
L0k1;L0k;48
L0k2;L0k;54
L0d;L0;21
L0d1'2;L0d;25
L0d1;L0d1'2;30
L0d1 NL;L0d1;31
L0d1a;L0d1 NL;38
L0d1a1;L0d1a;41
L0d1c;L0d1 NL;39
L0d1c1;L0d1c;45
L0d1c1a;L0d1c1;46
L0d1c1b;L0d1c1;46
L0d1b;L0d1 NL;36
L0d1b1;L0d1b;40
L0d2;L0d1'2;31
L0d2a'b;L0d2;32
L0d2a;L0d2a'b;42
L0d2a1;L0d2a;43
L0d2b;L0d2a'b;46
L0d2c;L0d2;45
L0d3;L0d;39
Seu programa deve gerar uma visualização em árvore da esquerda para a direita, incluindo alguns números com base na entrada. Com base na entrada de exemplo, esta é uma saída válida:
0│ ┐ mtEVE [ 0][ 63]
10│ └♦♦♦♦♦♦♦♦♦┬────────────────┬─────────────────────────────────── L0 [ 10][ 63]
21│ │ └♦♦♦♦♦♦♦♦♦♦┬──────┬───────────────── L0d [ 11][ 46]
39│ │ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d3 [ 18][ 39]
25│ │ └♦♦♦┐ L0d1'2 [ 4][ 46]
30│ │ ├♦♦♦♦┬─────────────── L0d1 [ 5][ 46]
31│ │ │ └┬────┬┐ L0d1 NL [ 1][ 46]
36│ │ │ │ │└♦♦♦♦┬─── L0d1b [ 5][ 40]
40│ │ │ │ │ └♦♦♦ L0d1b1 [ 4][ 40]
38│ │ │ │ └♦♦♦♦♦♦┬── L0d1a [ 7][ 41]
41│ │ │ │ └♦♦ L0d1a1 [ 3][ 41]
39│ │ │ └♦♦♦♦♦♦♦┬────── L0d1c [ 8][ 46]
45│ │ │ └♦♦♦♦♦┬ L0d1c1 [ 6][ 46]
46│ │ │ ├ L0d1c1a [ 1][ 46]
46│ │ │ └ L0d1c1b [ 1][ 46]
31│ │ └♦♦♦♦♦┬┬───────────── L0d2 [ 6][ 46]
45│ │ │└♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d2c [ 14][ 45]
32│ │ └┬──┐ L0d2a'b [ 1][ 46]
42│ │ │ └♦♦♦♦♦♦♦♦♦┬ L0d2a [ 10][ 43]
43│ │ │ └ L0d2a1 [ 1][ 43]
46│ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d2b [ 14][ 46]
14│ └♦♦♦┬────────┐ L0a'b'f'k [ 4][ 63]
39│ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦┬─────┬──────── L0k [ 25][ 54]
48│ │ │ └♦♦♦♦♦♦♦♦ L0k1 [ 9][ 48]
54│ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0k2 [ 15][ 54]
23│ └♦♦♦♦♦♦♦♦┬──┐ L0a'b'f [ 9][ 63]
30│ │ └♦♦♦♦♦♦┬───────────┐ L0a'b [ 7][ 60]
48│ │ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0b [ 18][ 48]
38│ │ └♦♦♦♦♦♦♦┬────┬─┬────────────── L0a [ 8][ 60]
53│ │ │ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0a3 [ 15][ 53]
39│ │ │ └┬────┐ L0a1'4 [ 1][ 55]
40│ │ │ │ └┬────┬──── L0a1 [ 1][ 50]
42│ │ │ │ │ └♦┬── L0a1a [ 2][ 45]
43│ │ │ │ │ └┬┐ L0a1a NL [ 1][ 45]
44│ │ │ │ │ │├ L0a1a1 [ 1][ 44]
44│ │ │ │ │ │└ L0a1a3 [ 1][ 44]
45│ │ │ │ │ └♦ L0a1a2 [ 2][ 45]
41│ │ │ │ └┬────┬┐ L0a1 NL [ 1][ 50]
44│ │ │ │ │ │└♦♦ L0a1d [ 3][ 44]
45│ │ │ │ │ └♦♦♦ L0a1c [ 4][ 45]
44│ │ │ │ └♦♦┬───── L0a1b [ 3][ 50]
45│ │ │ │ └┬─┐ L0a1b NL [ 1][ 50]
46│ │ │ │ │ └┬─ L0a1b1 [ 1][ 48]
47│ │ │ │ │ └┬ L0a1b1a [ 1][ 48]
48│ │ │ │ │ └ L0a1b1a1 [ 1][ 48]
48│ │ │ │ └♦♦┬─ L0a1b2 [ 3][ 50]
50│ │ │ │ └♦ L0a1b2a [ 2][ 50]
55│ │ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0a4 [ 16][ 55]
47│ │ └♦♦♦♦♦♦♦♦┬─┬───┬────┬─ L0a2 [ 9][ 60]
49│ │ │ │ │ └♦ L0a2d [ 2][ 49]
49│ │ │ │ └♦┬┬─── L0a2a [ 2][ 54]
50│ │ │ │ │└┬── L0a2a1 [ 1][ 53]
51│ │ │ │ │ └┬─ L0a2a1a [ 1][ 53]
53│ │ │ │ │ ├♦ L0a2a1a1 [ 2][ 53]
53│ │ │ │ │ └♦ L0a2a1a2 [ 2][ 53]
53│ │ │ │ └♦♦♦┬ L0a2a2 [ 4][ 54]
54│ │ │ │ └ L0a2a2a [ 1][ 54]
57│ │ │ └♦♦♦♦♦♦♦♦♦┬ L0a2b [ 10][ 58]
58│ │ │ └ L0a2b1 [ 1][ 58]
60│ │ └♦♦♦♦♦♦♦♦♦♦♦♦ L0a2c [ 13][ 60]
37│ └♦♦♦♦♦♦♦♦♦♦♦♦♦┬─┬─────────────────────── L0f [ 14][ 63]
61│ │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0f1 [ 24][ 61]
41│ └♦♦♦┬───┬───────────────── L0f2 [ 4][ 63]
46│ │ └♦♦♦♦┬──────────── L0f2a [ 5][ 59]
59│ │ └♦♦♦♦♦♦♦♦♦♦♦♦ L0f2a1 [ 13][ 59]
63│ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0f2b [ 22][ 63]
Entrada: Detalhes
A tabela de entrada não está classificada em nenhuma ordem específica. Se reordenarmos aleatoriamente as linhas de entrada, a saída deve permanecer a mesma.
Cada linha na entrada representa um galho de árvore mtDNA ou um galho de árvore hipotético. A tabela de entrada pode ter qualquer número de linhas de comprimento.
Entrada: Detalhes - Coluna A (nome da filial):
A primeira coluna é o nome da ramificação real. O nome divide as linhas de entrada em 2 grupos de tipos de linhas que devem ser tratados de forma diferente (explicados posteriormente) um do outro:
- Tipo 1: o nome consiste em qualquer um
'
ou o sufixoNL
- Tipo 2: o nome não consiste em nenhum
'
ou no sufixoNL
.
O nome pode ter até 20 caracteres.
Entrada: Detalhes - Coluna B (nome do ramo pai):
A segunda coluna contém um ponteiro para o nome do ramo pai. Várias linhas (ramificações) podem compartilhar o mesmo pai. Sempre há exatamente 1 nome de filial pai distinto na tabela de entrada que aponta para um pai que não é representado entre as linhas de entrada; esse nome de filial pai é a raiz da árvore. No exemplo de entrada que é a terceira linha que aponta para a raiz: mtEVE
. Se a entrada tiver mais de uma raiz ou loops infinitos, é uma entrada inválida.
Entrada: Detalhes - Coluna C (número de mutações):
A terceira coluna é o número total de mutações que um ramo específico teve desde a raiz. O mtDNA humano não sofreu mutação mais de 100 vezes em uma única linha da hipotética raiz materna (ancestral humano / chimpanzé EVE), mas seu programa deve ser capaz de lidar com um número de 3 dígitos de mutações, até 999.
A partir da entrada, você pode calcular um número de ramificação de mutações exclusivas subtraindo o número de mutações do número de mutação pai.
Saída: Detalhes
Seu programa deve enviar 1 entre 3 mensagens de erro diferentes se a entrada for inválida de acordo com a descrição da entrada.
- Mensagem de erro 1, se a entrada tiver mais de uma raiz:
ERROR: Multiple roots
- Mensagem de erro 2, se os ponteiros pai de entrada fizerem um loop:
ERROR: Endless loop
- Mensagem de erro 3, qualquer outra coisa inválida sobre a entrada:
ERROR: Invalid input
Se a entrada não contiver erros, seu programa deverá gerar a árvore de acordo com as seguintes restrições: Cada linha consiste em 5 partes A, B, C, D e E:
- R: 5 caracteres, 3 caracteres alinhados à direita com número de mutações, um caractere de linha vertical:
|
e 1 espaço em branco - B: [máx. De mutações] caracteres árvore larga + 1 espaço em branco
- C: 20 caracteres, nome do ramo alinhado à esquerda
- D: 5 caracteres, 3 caracteres alinhados à direita, # de mutações únicas para o ramo encapsulado entre
[
e]
. (Mutações únicas serão explicadas abaixo). - E: 5 caracteres, número máximo de 3 caracteres alinhados à direita do total de mutações para este ramo e todos os ramos filhos encapsulados entre
[
e]
.
Um número de ramificação de mutações únicas é a diferença no número de mutações que o ramo atual possui do número de mutações que seu ramo pai possui. A primeira linha é a raiz e deve ser representada com 0
para # de mutações e # de mutações únicas.
Saída: Detalhes - ordem / classificação da linha
Se dois ou mais sub-ramos estão compartilhando o mesmo pai, os ramos são ordenados pelo número máximo de sub-ramos no total de mutações em ordem decrescente. Em nosso exemplo L0a1'4
, L0a3
e L0a2
compartilha o pai: L0a
.
Na visualização em árvore, a ordem de cima para baixo é o número máximo de sub-ramos do total de mutações entre parênteses: L0a3
(53), L0a1'4
(55), L0a2
(60).
Se dois ou mais sub-ramos compartilham o mesmo número máximo de mutações nos ramos-filhos, eles são alinhados verticalmente e ramificados de seus pais no mesmo local, a ordem das linhas entre esses sub-ramos é alfabética.
Saída: Detalhes - árvore (parte B)
A árvore deve ser desenhado com os caracteres ASCII a seguir: └
, ─
, ┬
, ┐
, ├
, │
,♦
A lógica da árvore é que todas as mutações devem ser representadas. Uma ramificação de uma ramificação pai: ┬
ou ┐
representa 1 mutação. Mutações exclusivas adicionais no mesmo ramo são representadas por: ♦
e devem ser alinhadas à esquerda e colocadas antes do primeiro sub-ramo.
Os sub-ramos são ramificados de seus pais ao longo do eixo xe a posição é determinada pelo número máximo de mutações entre todos os ramos filhos subsequentes.
Como sugerido anteriormente, a entrada possui 2 tipos diferentes de linhas de entrada. Digite 1 com qualquer caractere 'ou o sufixo NL no nome da ramificação, não deve preencher a linha horizontal à extrema direita de sua linha, mas terminar com um ┐
na última sub-ramificação. No exemplo, é aplicado aos seguintes ramos:
L0a'b'f'k;L0;14
L0a'b'f;L0a'b'f'k;23
L0a'b;L0a'b'f;30
L0a1'4;L0a;39
L0a1a NL;L0a1a;43
L0a1 NL;L0a1;41
L0a1b NL;L0a1b;45
L0d1'2;L0d;25
L0d1 NL;L0d1;31
L0d2a'b;L0d2;32
Espero que o exemplo de entrada e saída responda a perguntas adicionais sobre como a árvore deve ser desenhada, considere parte do desafio de descobrir a lógica.
Inspiração
Você pode experimentar minha versão javascript (sem golf) para obter inspiração: http://artificial.se/DNA/mtDNAmutationTree3.html (falta verificação de erro e são adicionadas algumas estatísticas que não fazem parte desse desafio em particular) .
Uma versão completa da mtDNA-tree [baseada em http://www.phylotree.org/ mtDNA tree Build 16 (19 de fevereiro de 2014)] pode ser encontrada aqui:
http://artificial.se/DNA/mtDNAfull.html
O arquivo de dados usado para a árvore completa:
http://artificial.se/DNA/mtDNA_full.txt
Este é um desafio do código-golfe.
fonte
L0d1
não deve ser colocado antesL0d2
, de acordo com a regra de classificação: "... ordem decrescente ..."L0a1'4
não é (55) mas (39),L0a2
não é (60) mas (47) ... Você poderia esclarecer isso?Respostas:
Python 3, 925 bytes
Sim, com menos de 1 KB! Provavelmente ainda há espaço para jogar golfe ...
fonte