Tarefa
Você deve escrever um programa ou função no idioma de sua escolha, que conte com precisão o número de ciclos de terminal de um gráfico direcionado simples.
Esse tipo específico de gráfico direcionado é representado como uma matriz de n números inteiros, cada um com um valor aleatório escolhido independentemente entre 1 e n (ou 0 e n-1, se o seu idioma conta com 0). O gráfico pode ser visto como setas apontando de um índice (nó) para um índice que corresponda ao valor encontrado no índice inicial.
Sua função deve ser capaz de aceitar gráficos grandes, até n = 1024, ou qualquer tamanho inteiro menor.
Exemplo
Considere este gráfico para n = 10:
[9, 7, 8, 10, 2, 6, 3, 10, 6, 8]
O índice 1 contém um 9, então há uma seta do índice 1 para o índice 9. O índice 9 contém um 6, então há uma seta 9 -> 6. O índice 6 contém 6, que é um ciclo terminal, apontando de volta para si mesmo.
O Índice 2 contém um 7. O Índice 7 contém um 3. O Índice 3 contém um 8. O Índice 8 contém um 10. O Índice 10 contém um 8, portanto esse é um segundo ciclo terminal (8 -> 10 -> 8 -> 10, etc. )
Índice 4 -> 10, que entra no segundo ciclo do terminal. Da mesma forma, o índice 5 -> 2 -> 7 -> 3 -> 8, que também faz parte do segundo ciclo do terminal.
Nesse ponto, todos os índices (nós) foram verificados, todos os caminhos foram seguidos e dois ciclos terminais únicos foram identificados. Portanto, a função deve retornar 2 , pois esse é o número de ciclos de terminal neste gráfico direcionado.
Pontuação
Aponte para o menor código, mas verifique se ele conta os ciclos do terminal corretamente. O código mais curto após 1 semana vence.
Casos de teste
Aqui estão alguns casos de teste para verificar a correção do seu código. Se o seu idioma conta índices de matriz a partir de 0, é claro que você deve subtrair 1 do valor de cada elemento da matriz, para evitar um índice fora de limite.
n = 32, 5 ciclos:
[8, 28, 14, 8, 2, 1, 13, 15, 30, 17, 9, 8, 18, 19, 30, 3, 8, 25, 23, 12, 6, 7, 19, 24, 17, 7, 21, 20, 29, 15, 32, 32]
n = 32, 4 ciclos:
[20, 31, 3, 18, 18, 18, 8, 12, 25, 10, 10, 19, 3, 9, 18, 1, 13, 5, 18, 23, 20, 26, 16, 22, 4, 16, 19, 31, 21, 32, 15, 22]
n = 32, 3 ciclos:
[28, 13, 17, 14, 4, 31, 11, 4, 22, 6, 32, 1, 13, 15, 7, 19, 10, 28, 9, 22, 5, 26, 17, 8, 6, 13, 7, 10, 9, 30, 23, 25]
n = 32, 2 ciclos:
[25, 23, 22, 6, 24, 3, 1, 21, 6, 18, 20, 4, 8, 5, 16, 10, 15, 32, 26, 25, 27, 14, 13, 12, 9, 9, 29, 8, 13, 31, 32, 1]
n = 32, 1 ciclo:
[6, 21, 15, 14, 22, 12, 5, 32, 29, 3, 22, 23, 6, 16, 20, 2, 16, 25, 9, 22, 13, 2, 19, 20, 26, 19, 32, 3, 32, 19, 28, 16]
n = 32, 1 ciclo:
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, 6, 7]
n = 1024, 6 ciclos:
[239, 631, 200, 595, 178, 428, 582, 191, 230, 551, 223, 61, 564, 463, 568, 527, 143, 403, 154, 236, 928, 650, 14, 931, 236, 170, 910, 782, 861, 464, 378, 748, 468, 779, 440, 396, 467, 630, 451, 130, 694, 167, 594, 115, 671, 853, 612, 238, 464, 771, 825, 471, 167, 653, 561, 337, 585, 986, 79, 506, 192, 873, 184, 617, 4, 259, 4, 662, 623, 694, 859, 6, 346, 431, 181, 703, 823, 140, 635, 90, 559, 689, 118, 117, 130, 248, 931, 767, 840, 158, 696, 275, 610, 217, 989, 640, 363, 91, 129, 399, 105, 770, 870, 800, 429, 473, 119, 908, 481, 337, 504, 45, 1011, 684, 306, 126, 215, 729, 771, 5, 302, 992, 380, 824, 868, 205, 807, 917, 407, 759, 181, 640, 685, 795, 258, 180, 900, 20, 773, 546, 866, 564, 761, 632, 895, 968, 980, 651, 225, 676, 18, 685, 784, 208, 227, 3, 267, 852, 57, 487, 566, 633, 849, 309, 543, 145, 575, 811, 621, 560, 492, 24, 665, 66, 851, 168, 262, 259, 754, 481, 565, 768, 172, 1012, 241, 3, 370, 985, 389, 82, 779, 744, 829, 836, 249, 975, 909, 840, 226, 867, 499, 192, 909, 972, 735, 252, 785, 545, 486, 186, 1011, 89, 939, 649, 110, 119, 185, 836, 717, 545, 938, 621, 946, 94, 363, 721, 177, 747, 59, 819, 146, 283, 821, 547, 654, 941, 755, 18, 449, 367, 499, 944, 62, 553, 435, 344, 900, 25, 251, 920, 902, 99, 326, 98, 495, 385, 929, 865, 327, 725, 674, 33, 173, 429, 873, 558, 90, 460, 366, 543, 583, 954, 792, 213, 536, 670, 49, 738, 802, 1015, 23, 915, 119, 263, 307, 601, 474, 971, 826, 613, 446, 37, 145, 894, 901, 307, 906, 886, 990, 89, 798, 384, 487, 822, 354, 768, 902, 163, 179, 134, 920, 439, 619, 215, 94, 709, 744, 366, 543, 349, 347, 2, 438, 141, 486, 19, 998, 500, 857, 955, 932, 1, 587, 195, 646, 550, 887, 626, 400, 348, 154, 808, 678, 873, 186, 282, 168, 993, 722, 56, 345, 5, 226, 328, 22, 894, 658, 264, 13, 803, 791, 359, 217, 997, 168, 578, 952, 734, 964, 898, 659, 628, 980, 15, 31, 439, 13, 875, 687, 1004, 1023, 165, 642, 561, 897, 711, 124, 404, 346, 723, 774, 352, 784, 276, 395, 14, 443, 343, 153, 510, 590, 172, 215, 130, 106, 295, 906, 133, 758, 483, 898, 391, 760, 702, 972, 721, 611, 592, 1001, 724, 934, 59, 831, 171, 253, 869, 431, 538, 20, 648, 76, 351, 103, 33, 385, 852, 437, 470, 95, 434, 408, 430, 994, 366, 706, 809, 532, 161, 388, 668, 245, 965, 365, 913, 471, 927, 245, 256, 805, 540, 380, 995, 446, 657, 545, 573, 955, 499, 322, 949, 635, 401, 185, 421, 626, 534, 429, 930, 633, 563, 348, 626, 518, 682, 233, 775, 444, 42, 199, 57, 271, 683, 397, 883, 620, 768, 8, 331, 497, 19, 340, 900, 919, 497, 276, 78, 252, 164, 764, 927, 242, 270, 759, 824, 945, 886, 262, 59, 439, 217, 720, 519, 862, 626, 326, 339, 589, 16, 565, 947, 604, 144, 87, 520, 256, 240, 336, 685, 361, 998, 805, 678, 24, 980, 203, 818, 855, 85, 276, 822, 183, 266, 347, 8, 663, 620, 147, 189, 497, 128, 357, 855, 507, 275, 420, 755, 131, 469, 672, 926, 859, 156, 127, 986, 489, 803, 433, 622, 951, 83, 862, 108, 192, 167, 862, 242, 519, 574, 358, 549, 119, 630, 60, 925, 414, 479, 330, 927, 94, 767, 562, 919, 1011, 999, 908, 113, 932, 632, 403, 309, 838, 341, 179, 708, 847, 472, 907, 537, 516, 992, 944, 615, 778, 801, 413, 653, 690, 393, 452, 394, 596, 545, 591, 136, 109, 942, 546, 57, 626, 61, 587, 862, 829, 988, 965, 781, 849, 843, 815, 60, 928, 784, 388, 341, 491, 565, 83, 110, 164, 38, 1024, 859, 297, 520, 327, 733, 699, 631, 78, 178, 671, 895, 818, 637, 99, 425, 933, 248, 299, 333, 144, 323, 105, 849, 942, 767, 265, 72, 204, 547, 934, 916, 304, 919, 273, 396, 665, 452, 423, 471, 641, 675, 60, 388, 97, 963, 902, 321, 826, 476, 782, 723, 99, 735, 893, 565, 175, 141, 70, 918, 659, 935, 492, 751, 261, 362, 849, 593, 924, 590, 982, 876, 73, 993, 767, 441, 70, 875, 640, 567, 920, 321, 46, 938, 377, 905, 303, 736, 182, 626, 899, 512, 894, 744, 254, 984, 325, 694, 6, 367, 532, 432, 133, 938, 74, 967, 725, 87, 502, 946, 708, 122, 887, 256, 595, 169, 101, 828, 696, 897, 961, 376, 910, 82, 144, 967, 885, 89, 114, 215, 187, 38, 873, 125, 522, 884, 947, 962, 45, 585, 644, 476, 710, 839, 486, 634, 431, 475, 979, 877, 18, 226, 656, 573, 3, 29, 743, 508, 544, 252, 254, 388, 873, 70, 640, 918, 93, 508, 853, 609, 333, 378, 172, 875, 617, 167, 771, 375, 503, 221, 624, 67, 655, 465, 272, 278, 161, 840, 52, 1016, 909, 567, 544, 234, 339, 463, 621, 951, 962, 1019, 383, 523, 279, 780, 838, 984, 999, 29, 897, 564, 762, 753, 393, 205, 31, 150, 490, 156, 796, 586, 676, 773, 465, 489, 1024, 433, 214, 701, 480, 604, 280, 241, 563, 943, 911, 12, 400, 261, 883, 999, 207, 618, 141, 959, 767, 978, 461, 992, 982, 272, 143, 404, 645, 331, 348, 783, 698, 827, 82, 145, 536, 449, 852, 750, 789, 413, 913, 420, 14, 499, 285, 533, 223, 75, 591, 994, 884, 237, 63, 411, 563, 611, 801, 173, 759, 278, 318, 772, 1018, 48, 440, 333, 611, 834, 423, 583, 22, 716, 393, 794, 83, 83, 864, 859, 600, 525, 808, 569, 95, 952, 852, 567, 651, 2, 984, 906, 992, 747, 602, 143, 547, 1008, 940, 245, 633, 378, 193, 771, 965, 648, 437, 873, 591, 664, 271, 777, 274, 742, 68, 429, 825, 144, 55, 272, 279, 6, 400, 485, 66, 311, 663, 441, 23, 988, 726, 48, 624, 302, 617, 120, 653, 810, 641, 142]
fonte
Respostas:
GolfScript, 25 caracteres
A mesma abordagem da solução de Keith Randall , mas no GolfScript. Observe que o GolfScript possui matrizes com índice zero. Testador online .
fonte
Mathematica 69
Código
Este encontra o número de componentes do gráfico.
O primeiro caso de teste:
Análise
Faça uma lista de arestas direcionadas entre índices (usando o exemplo 1).
Graph
desenha um gráfico mostrando os componentes do gráfico.ImagePadding
eVertexLabels
são usados aqui para mostrar os índices.WeaklyConnectedComponents
retorna a lista de vértices para cada componente.Length
retorna o número de componentes.Tempo da lista de amostras com 1024 elementos:
Tempo: 0.002015 seg
Apenas por diversão, aqui está uma imagem do caso de teste final, representado graficamente. Omiti os rótulos dos vértices; existem muitos.
fonte
WeaklyConnectedComponents
é muito detalhado. Mas dá muito trabalho. (Nunca se deve subestimar J e linguagens semelhantes por concisão.) #Python,
132116 caracteresPara cada índice, seguimos arestas para n hops, o que garante que estamos em um ciclo terminal. Seguimos n mais saltos e encontramos o índice mínimo nesse ciclo. O número total de ciclos de terminal é apenas o número de mínimos diferentes que encontramos.
fonte
#define F for i in r
, em Python, C (++) - estilo ... :)Em Python:
fonte
if
condições.c=lambda l:0 if l==[] else c(l[:-1])+1 if l[-1]==len(l) else c([[x,l[-1]][x==len(l)] for x in l[:-1]])
é melhor: 102 bytes.J -
6153 charEste foi um doozy.
A
<@<:
transformar a lista em um gráfico de J, que se parece com uma lista de caixas, ea caixa no índicei
contém todos os nós que nói
se conecta. J indexa de zero, então usamos<:
para diminuir tudo um por um antes de encaixar<
.O
<~.@(],;@:{~)^:_&.>]
transforma cada nó em uma lista de todos os nós que podem ser alcançadas a partir dele. Ele<...&.>]
é responsável por fazer isso acontecer com cada nó e, na~.@(],;@:{~)^:_
verdade, vem de um J golfe dessa tarefa de 'nós alcançáveis' que fiz algumas semanas atrás.e.
executa uma tarefa interessante. Se o fechamento de "alcançabilidade" do gráfico (a versão do gráfico, de modo que se houver arestas direcionadas X → Y e Y → Z, adicionarmos a aresta X → Z.) Tiver N nós e arestas E,e.
nesse gráfico uma matriz booleana de N linhas e colunas E, com um True se o nó correspondente compartilhar um nó acessível com essa borda. Confuso, mas tenha paciência comigo.Em seguida, temos que encontrar o número de ciclos de terminal, ou seja, o número de grupos que compartilham Trues entre suas colunas. Queremos fazer uma espécie de tabela de multiplicação das linhas (
"1/~
) e usamos um tipo de produto interno como a multiplicação, aquela que ANDs em pares e depois ORs todos os resultados juntos (+./ .*
). A matriz resultante é uma tabela quadrada com um True em cada posição em que duas linhas compartilham pelo menos uma coluna entre elas.Agora tudo o que precisamos fazer é verificar quantos tipos diferentes de padrões de linha existem. Portanto, fazemos exatamente isso: agrupe linhas do mesmo tipo (
/.~
), relate o número em cada grupo (#
) e, em seguida, pegue o número de grupos (#@
).Uso em outros exemplos:
Infelizmente, o gabinete do elemento 1024 agora leva muito tempo para terminar. A versão anterior
<:@#@((#~0={.+/@:*"1])^:a:)@e.@(~.@(],;@:{~)^:_&.>~<)@:(<@<:)
(61 caracteres) levou um pouco mais de um segundo para fazer isso.fonte
Python (96)
Muito, muito, muito, muito com base na resposta do usuário2228078, pois funciona exatamente da mesma forma, mas é mais eficiente:
(Pergunta técnica: o golfe de outra pessoa deve ser um wiki da comunidade?)
fonte
Python
(89)(87)A idéia principal é começar em cada nó à vez e percorrer o caminho a partir dele, marcando cada nó que visitamos com um rótulo exclusivo para o nó em que começamos. Se alguma vez atingirmos um nó marcado, paramos de andar e verificamos se a marcação é a que corresponde ao nosso nó inicial. Se for, devemos ter percorrido um loop, então aumentamos a contagem de ciclos em um.
No código,
u
é o contador de ciclo,i
é o nó inicial,j
é o nó atual em que estamos andando. O rótulo correspondente ao nó iniciali
é seu complemento de bit~i
que é sempre negativo. Marcamos um nó apontando-o para esse valor, substituindo o que ele realmente apontou (tomando cuidado para caminhar até esse nó antes que ele seja esquecido).Sabemos que atingimos um nó marcado quando caminhamos para um "nó" de valor negativo imediatamente depois. Verificamos se esse valor negativo é o rótulo atual para ver se percorremos um ciclo. Como cada nó que andamos é efetivamente excluído, cada ciclo será percorrido apenas uma vez.
Ele salva caracteres para contar
i
manualmente com uma variável dummy loop e_
depois comofor i in range(len(G))
. As listas Python são indexadas em 0. Se eles fossem indexados em 1, poderíamos salvar dois caracteres escrevendoj=i=i+1
para teri
ej
ser 1 no primeiro loop e escreverj>0
no lugar dej>=0
.Editar:
Podemos salvar dois caracteres iterando
i
sobre os elementos da lista em vez dos índices, pois o nó que não é apontado por nenhuma borda não importa. Temos que repetirset(G)
Porém, para evitar a repetição de um nó inicial apontado por vários outros nós.fonte