Esse é um dos vários desafios que a Calvin's Hobbies deixou para a comunidade .
Pegue um arquivo "descrevendo a árvore genealógica" com linhas do formulário:
[ID] [mother ID] [father ID] [gender] [full name]
como esta que descreve a primeira árvore genealógica em http://en.wikipedia.org/wiki/Cousin :
1 ? ? M Adam
2 ? ? F Agatha
3 ? ? M Bill
4 2 1 F Betty
5 2 1 M Charles
6 ? ? F Corinda
7 3 4 M David
8 6 5 F Emma
Escreva um programa ou função que inclua o nome do arquivo e dois IDs e mostre como essas pessoas estão relacionadas ao sangue em termos mais simples, usando os nomes comuns em inglês para as relações. A entrada pode ser via STDIN, ARGV ou argumentos de função, mas a saída deve ser para STDOUT.
Notas
- IDs são números inteiros positivos.
?
é usado quando a paternidade não é conhecida.- Suponha que o gráfico esteja conectado e não possua ciclos.
- Você não pode presumir que os pais de cada pessoa estejam listados antes dessa pessoa (para que o ID dos pais de uma pessoa possa ser maior que o seu próprio ID).
- Suponha que todos sejam homens ou mulheres e todos tenham exatamente uma mãe e exatamente um pai (do gênero correto), embora possam ser desconhecidos.
- Suponha que os nomes sejam únicos.
- Os nomes podem ter espaços neles.
Relações de sangue
As seguintes definições de relações R determinar se a pessoa Um é o R ou pessoa B . Se duas variantes de R são listados, o primeiro é para fêmea Um e o segundo para o sexo masculino Uma . Tudo isso precisa ser implementado. Se várias definições corresponderem, a anterior deve ser usada. Os termos entre parênteses são de gênero neutro, que não precisam ser implementados, mas serão reutilizados em outras definições. Nas definições envolvendo N e M , assuma N> 1 e M> 0 .
- filha / filho: A lista B como pai ou mãe.
- mãe / pai (pai): B lista A como pai ou mãe.
- irmã / irmão (A): A e B listam a mesma mãe e pai.
- meia-irmã / meio-irmão (irmão): A e B listam a mesma mãe ou o mesmo pai.
- sobrinha / sobrinho: A lista de um pai que é o irmão de B .
- tia / tio: B é sobrinha ou sobrinho de A.
- neta / neto (neto): A lista um pai que lista B como pai.
- avó / avô (avô): B é o neto de A.
- grande-sobrinha / sobrinho-neto: Um é o neto de C que é o irmão de B .
- tia-avó / tio-avô: B é sobrinha-sobrinha ou sobrinho -avó de A.
- bisneta / filho (1º bisneto): A é um neto de C que lista B como pai ou mãe.
- bisavó / pai (1º bisavô): B é o 1º bisneto de A.
- Neta neta / filho (neta neto): A é um (N-1) neto de C que lista B como pai ou mãe.
- Enésimo bisavó / pai (Enésimo bisavô): B é o nono bisneto de A.
- Nth grande-sobrinha / sobrinho: Uma é a (N-1) th grande-neto de C que é o irmão de B .
- Nth tia-avó / tio: B é um 's Nth sobrinha-neta de Nth sobrinho-neto.
- primo: Um é o neto de C que é o avô de B .
- Primo Nth: Uma é a (N-1) th neto de C que é a (N-1) th avós de B .
- primo, vezes M removido: Um é o neto de C que é a avó Mth de B ou A é o neto Mth de C que é a avó de B .
- Primo enésimo, M vezes removido: A é o quinto bisneto de C e é o quinto bisavô de B , onde
N = min(P,Q) + 1
eM = |P-Q|
.
Para Nth
, gravação 2nd
, 3rd
, 4th
, 5th
etc.
Para M times
, gravação once
, twice
, thrice
, 4 times
, 5 times
etc.
Exemplos
Suponha que o seguinte arquivo seja usado (você não precisa lidar com vários espaços, mas eu os adicionei para legibilidade):
1 ? ? F Agatha
2 ? ? M Adam
3 ? ? F Betty
4 1 2 M Bertrand
5 1 2 F Charlotte
6 ? ? M Carl
7 ? ? F Daisy
8 3 4 M David
9 5 6 F Emma
10 ? ? M Edward
11 ? ? F Freya
12 7 8 M Fred
13 9 10 F Grace
14 ? ? M Gerald
15 ? ? F Hillary
16 11 12 M Herbert
17 13 14 F Jane
18 ? ? M James
19 15 16 F Kate
20 17 18 M Larry
21 ? 18 F Mary
Em seguida, os IDs de entrada devem ser mapeados para as saídas da seguinte maneira:
1 2 --> Agatha is not a blood relative to Adam.
8 3 --> David is the son of Betty.
9 13 --> Emma is the mother of Grace.
4 5 --> Bertrand is the brother of Charlotte.
9 4 --> Emma is the niece of Bertrand.
5 8 --> Charlotte is the aunt of David.
16 7 --> Herbert is the grandson of Daisy.
1 9 --> Agatha is the grandmother Emma.
12 5 --> Fred is the great-nephew of Charlotte.
4 13 --> Bertrand is the great-uncle of Grace.
16 3 --> Herbert is the great-grandson of Betty.
6 17 --> Carl is the great-grandfather of Jane.
19 2 --> Kate is the 3rd great-granddaughter of Adam.
1 17 --> Agatha is the 2nd great-grandmother of Jane.
20 4 --> Larry is the 3rd great-nephew of Bertrand.
5 16 --> Charlotte is the 2nd great-aunt of Herbert.
8 9 --> David is the cousin of Emma.
19 20 --> Kate is the 4th cousin of Larry.
16 9 --> Herbert is the cousin, twice removed, of Emma.
12 17 --> Fred is the 2nd cousin, once removed, of Jane.
21 20 --> Mary is the half-sister of Larry.
Eu os escrevi à mão, então, deixe-me saber se você encontrar algum erro.
Outro conjunto de dados de teste (fornecidos por Scott Leadley, quaisquer erros são meus e não de Martin).
Árvore genealógica Ptolomeu
A imagem é ilustrativa; os dados abaixo são provenientes do artigo da Wikipedia " Dinastia ptolemaica ".
1 ? ? F Berenice I of Egypt
2 ? ? M Ptolemy I Soter
41 1 2 F Arsinoe II of Egypt
3 1 2 M Ptolemy II Philadelphus
4 ? ? F Arsinoe I of Egypt
5 ? ? M Philip
6 4 3 M Ptolemy III Euergetes
7 1 5 F Magas of Cyrene
8 7 ? F Berenice II
9 8 6 M Ptolemy IV Philopator
10 8 6 F Arsinoe III of Egypt
11 10 9 M Ptolemy V Epiphanes
12 ? ? F Cleopatra I of Egypt
13 12 11 M Ptolemy VI Philometor
14 12 11 F Cleopatra II
15 12 11 M Ptolemy VIII Physcon
19 ? ? F Eirene
16 14 13 M Ptolemy VII Neos Philopator
17 14 13 F Cleopatra III
18 14 15 M Ptolemy Memphites
20 19 15 M Ptolemy Apion
21 17 15 F Cleopatra IV
22 17 15 M Ptolemy IX Lathyros
23 17 15 F Cleopatra Selene I
24 17 15 M Ptolemy X Alexander I
25 23 22 F Berenice III of Egypt
26 23 24 M Ptolemy XI Alexander II
27 21 22 M Ptolemy XII Auletes
28 25 24 F Cleopatra V of Egypt
29 28 27 F Cleopatra VI of Egypt
30 28 27 F Berenice IV of Egypt
31 28 27 M Ptolemy XIII Theos Philopator
32 28 27 F Cleopatra VII Thea Philopator
33 28 27 M Ptolemy XIV
34 28 27 F Arsinoe IV of Egypt
35 ? ? M Julius Caesar
37 32 35 M Ptolemy XV Caesarion
36 ? ? M Mark Anthony
38 32 36 M Alexander Helios
39 32 36 M Ptolemy XVI Philadelphus
40 32 36 F Cleopatra Selene II
fonte
Ruby -
189212901247Executar como
ruby relation.rb ID1 ID2 relationship_file
.Versão ungolfed -
52513416 (mesma árvore de chamadas, apenas dobramos bastante o código)Passa no seguinte conjunto de testes:
fonte
Javascript, 2292
Tenho certeza de que ele pode ser jogado muito mais longe, tudo o que fiz foi colocar uma versão não destruída em um minificador.
Você pode executar a versão não-gasta aqui no jsFiddle . Aqui está a saída para os dados de exemplo:
fonte
Python 3: 1183
O nome do arquivo e os IDs das pessoas a serem descritas são lidos a partir da entrada padrão em uma única linha.
A parte superior do código são definições de função. O script começa na metade do caminho e primeiro trabalha no processamento da entrada (analisando o arquivo e depois atribuindo filhos aos pais em uma segunda passagem).
Depois que os dados são configurados, chamamos a
A
função uma vez para iniciar uma pesquisa recursiva. O resultado define o relacionamento.O restante do código é dedicado a descrever esse relacionamento em inglês. Irmãos e primos são complicados (e usam longas filas), o resto é bem direto.
Exemplo de execução (a segunda linha é minha entrada):
Função e chave de nome variável:
f
: O nome do arquivo do qual os dados da família são lidos.a
: O ID da pessoa que está relacionando o nome.b
: O ID da pessoa com quem o relacionamento é definido.t
: A própria árvore genealógica, como um mapeamento de dicionário de um id para uma cinco-tupla do id da mãe, do pai, sexo, nome e uma lista de filhos.g
: Um valor booleano que reflete o gênero da pessoaa
. ÉTrue
se eles são homens.u
: O número de gerações desdeb
o ancestral comum dea
eb
(ou 0 seb
fora
o ancestral).d
: O número de gerações desdea
o ancestral comum dea
eb
(ou 0 sea
forb
o ancestral).D(i)
: Procure recursivamente os descendentes de pessoai
por pessoaa
. Retornar a profundidadea
foi encontrada em, ou Nenhum, se não foi encontrado.A(i)
: Pesquisa recursivamentei
ei
descendentes, mas se ele não for encontrado recursivamente, procure tambémi
os ancestrais (e seus descendentes). Retorna uma tupla de 2, cujos valores sãou
ed
descritos acima. Se um relacionamento for encontrado pelos dois pais,u+d
é preferível aquele com o menor número de etapas geracionais ( ). Se a pessoaa
não tiver nenhuma relação de sangue com elai
,A(i)
retornaráNone
.P(r)
: Imprime a sequência de resultadosr
entre colchetes pelos nomes das pessoasa
eb
.O(n)
: Retorna uma sequência ordinal para o número fornecidon
. Apenas suporta1 < n < 21
.G(n)
: Retorna uma string de prefixo equivalente an-1
"greats" (por exemplo,"2nd great-"
para n = 2`). Retornará uma string vazia para n <= 1.GG(n)
: Retorna uma string de prefixo com "Nésimo ótimo" e "grand", conforme apropriado porn
gerações. Retornará uma string vazia para n <= 1.Peguei alguns atalhos no nome do código mais curto que poderiam ser revisados para obter um desempenho melhor (ou um pouco mais correto) em genealogias grandes. A
A
função não faz nenhuma tentativa para evitar recursões nas árvores filho que já foram pesquisadas, o que a torna mais lenta do que o necessário (embora provavelmente ainda seja rápida o suficiente para famílias de tamanho razoável). AO
função não lidar corretamente com ordinais superior a 20 (que é um pouco complicado para obter todos11th
,21st
e101st
bem, mas em uma das minhas versões preliminares eu fiz isso em cerca de 25 bytes adicionais). A menos que você esteja lidando com famílias muito antigas e famosas (por exemplo, algumas das famílias reais da Europa), não tenho certeza se confiaria na precisão de uma genealogia que voltou tão longe assim.Por outro lado, eu também pulei alguns lugares onde poderia economizar alguns bytes. Por exemplo, eu poderia economizar 3 bytes renomeando
GG
para um único nome de caractere, mas basear o nomegreat-grand
parecia mais valioso para mim.Acredito que todo o espaço em branco no código é necessário, mas é possível que alguns possam ser ignorados e eu apenas os perdi (eu continuava encontrando espaços dispersos nas listas de argumentos enquanto digitava esta resposta, mas acho que ' já os peguei todos agora).
Como minha correspondência recursiva requer uma regra relativamente simples para a qual os relacionamentos preferem se houver mais de um, não dou exatamente os resultados solicitados em alguns casos obscuros que envolvem incesto entre gerações. Por exemplo, se a pessoa
a
éb
tio e avô, meu código prefere o relacionamento com o avô, apesar da pergunta dizendo que o relacionamento com o tio deve ter maior precedência.Aqui está um exemplo de conjunto de dados que expõe o problema:
Suspeito que, para a maioria dos programas, os relacionamentos entre Bob e Claire ou entre Bob e Danielle causem problemas. Eles chamarão o primeiro par de meio-irmãos em vez de pai / filha ou descreverão o último par como avô / neta, em vez de tio / sobrinha. Meu código faz o último e não vejo nenhuma maneira razoável de alterá-lo para obter os resultados solicitados sem também errar o primeiro par.
fonte
Uma suíte de teste. Coloque-o em t / relação.t e execute "prove" ou "perl t / relação.t". Atualmente, assume que o arquivo do programa é "relationship.rb".
É um wiki da comunidade, então fique à vontade para adicionar testes. Se você mudar, acho que um carimbo de data / hora (ou alguma outra bandeira óbvia) estaria em ordem. Lista de Desejos:
fonte