fork download
copy 
  1. from pprint import pprint
  2.  
  3.  
  4. # Ищем в графе циклы длины 3
  5. def find_triangles():
  6.     cycles = []
  7.     for i in range(vert_count):
  8.         for j in range(i + 1, vert_count):
  9.             for k in range(j + 1, vert_count):
  10.                 if (j in graph[i] and
  11.                         k in graph[j] and
  12.                         i in graph[k]):
  13.                     if not colinear(i, j, k):  # Проверяем что треугольник не вырожден
  14.                         cycles.append((i, j, k))
  15.     return cycles
  16.  
  17.  
  18. def colinear(i, j, k):
  19.     res = False
  20.     for l in lines:
  21.         if i in l and j in l and k in l:
  22.             res = True
  23.     return res
  24.  
  25.  
  26. # Для каждой вершины список лежащих с ней на одной прямой вершин
  27. graph = [
  28.     [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15],
  29.     [0, 2, 4, 7, 8, 9, 10, 11, 14],
  30.     [0, 1, 3, 4, 6, 9, 12, 15],
  31.     [0, 2, 4, 5, 8, 9, 10, 13, 16],
  32.     [0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16],
  33.     [0, 3, 4, 6, 10, 13, 14, 15, 16],
  34.     [0, 2, 4, 5, 7, 9, 12, 15],
  35.     [0, 1, 4, 6, 8, 11, 14, 15, 16],
  36.     [0, 1, 3, 7, 9, 11, 14],
  37.     [0, 1, 2, 3, 4, 6, 8, 10, 12, 15],
  38.     [1, 3, 4, 5, 9, 13, 16],
  39.     [0, 1, 4, 7, 8, 12, 13, 14],
  40.     [0, 2, 4, 6, 9, 11, 13, 15],
  41.     [0, 3, 4, 5, 10, 11, 12, 16],
  42.     [0, 1, 5, 7, 8, 11, 15],
  43.     [0, 2, 4, 5, 6, 7, 9, 12, 14, 16],
  44.     [3, 4, 5, 7, 10, 13, 15]
  45. ]
  46.  
  47. # Списки лежащих на одной прямой вершин
  48. lines = [
  49.     [0, 1, 2],
  50.     [2, 3, 4],
  51.     [4, 5, 6],
  52.     [6, 7, 0],
  53.     [1, 8, 11, 14, 7],
  54.     [1, 9, 10, 4],
  55.     [7, 15, 16, 4],
  56.     [0, 8, 9, 3],
  57.     [0, 14, 15, 5],
  58.     [3, 10, 13, 16, 5],
  59.     [0, 11, 12, 13, 4],
  60.     [2, 9, 12, 15, 6]
  61. ]
  62.  
  63. vert_count = 17
  64.  
  65. cycles = find_triangles()
  66. print(f"Triangles: {len(cycles)}")
  67. pprint(cycles)
  68.  
  69. #                                            ↑ (2)                                                                        
  70. #                                           ↑↑↑                                                                           
  71. #                                          ↑ ↑ ↑                                                                          
  72. #                                         ↑  ↑  ↑                                                                         
  73. #                                        ↑   ↑   ↑                                                                        
  74. #                                       ↑    ↑    ↑                                                                       
  75. #                                      ↑     ↑                                                                            
  76. #                                     ↑      ↑                                                                            
  77. #                                    ↑       ↑      ↑                                                                     
  78. #                                   ↑        ↑       ↑                                                                    
  79. #                                            ↑        ↑                                                                   
  80. #                                            ↑         ↑                                                                  
  81. #                                            ↑          ↑                                                                 
  82. #                                ↑           ↑           ↑                                                                
  83. #                               ↑            ↑            ↑                                                               
  84. #                              ↑             ↑             ↑                                                              
  85. #                             ↑              ↑              ↑                                                             
  86. #                            ↑               ↑               ↑                                                            
  87. #                           ↑                ↑                                                                            
  88. #                          ↑                 ↑                                                                            
  89. #                         ↑                  ↑                 ↑                                                          
  90. #                        ↑                   ↑                  ↑                                                         
  91. #                  (1)  ↑↑↑                  ↑                  ↑↑   (3)                                                     
  92. #                        ↑  ↑                ↑               ↑   ↑↑                                                       
  93. #                        ↑     ↑             ↑            ↑↑     ↑ ↑                                                      
  94. #                     ↑  ↑        ↑          ↑          ↑        ↑  ↑                                                     
  95. #                    ↑   ↑           ↑       ↑       ↑           ↑   ↑                                                    
  96. #                   ↑    ↑             ↑     ↑    ↑              ↑    ↑                                                   
  97. #                  ↑     ↑                ↑  ↑ ↑↑                ↑     ↑                                                  
  98. #                 ↑      ↑              (9)  ↑                   ↑      ↑                                                 
  99. #                ↑       ↑                ↑  ↑  ↑                ↑                                                        
  100. #               ↑        ↑             ↑     ↑    ↑↑             ↑                                                        
  101. #              ↑         ↑          ↑↑       ↑       ↑           ↑                                                        
  102. #             ↑          ↑        ↑          ↑          ↑        ↑         ↑                                              
  103. #            ↑           ↑     ↑             ↑             ↑     ↑          ↑                                             
  104. #                        ↑  ↑                ↑               ↑↑  ↑           ↑                                            
  105. #                    (8) ↑↑                  ↑                  ↑↑ (10)       ↑                                           
  106. #          ↑           ↑ ↑                   ↑                   ↑ ↑           ↑                                          
  107. #         ↑         ↑    ↑                   ↑                   ↑    ↑         ↑                                         
  108. #        ↑       ↑       ↑                   ↑                   ↑      ↑↑       ↑                                        
  109. #       ↑     ↑↑         ↑                   ↑                   ↑         ↑      ↑                                       
  110. #      ↑    ↑            ↑                   ↑                   ↑            ↑    ↑                                      
  111. #     ↑  ↑               ↑                   ↑                   ↑               ↑                                        
  112. #    ↑↑                  ↑(11)               ↑ (12)              ↑ (13)            ↑↑                                     
  113. #(0) ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑  (4)                                  
  114. #     ↑ ↑↑               ↑                   ↑                   ↑               ↑  ↑                                     
  115. #      ↑   ↑             ↑                   ↑                   ↑            ↑↑   ↑                                      
  116. #       ↑     ↑          ↑                   ↑                   ↑         ↑↑     ↑                                       
  117. #        ↑       ↑       ↑                   ↑                   ↑       ↑       ↑                                        
  118. #                  ↑↑    ↑                   ↑                   ↑    ↑         ↑                                         
  119. #                     ↑  ↑                   ↑                   ↑ ↑           ↑                                          
  120. #          ↑             ↑   (14)            ↑                   ↑ (16)       ↑                                           
  121. #           ↑            ↑  ↑                ↑                ↑  ↑           ↑                                            
  122. #            ↑           ↑    ↑↑             ↑             ↑     ↑                                                        
  123. #             ↑          ↑       ↑           ↑          ↑        ↑                                                        
  124. #              ↑         ↑          ↑        ↑       ↑↑          ↑                                                        
  125. #               ↑        ↑             ↑     ↑     ↑             ↑        ↑                                               
  126. #                ↑       ↑               ↑↑  ↑  ↑                ↑       ↑                                                
  127. #                 ↑      ↑                  ↑↑  (15)             ↑      ↑                                                 
  128. #                  ↑     ↑                ↑↑ ↑ ↑                 ↑     ↑                                                  
  129. #                   ↑    ↑              ↑    ↑    ↑              ↑    ↑                                                   
  130. #                        ↑           ↑       ↑      ↑↑           ↑   ↑                                                    
  131. #                        ↑        ↑          ↑         ↑         ↑  ↑                                                     
  132. #                        ↑     ↑↑            ↑            ↑      ↑ ↑                                                      
  133. #                      ↑ ↑   ↑               ↑               ↑   ↑↑                                                       
  134. #                  (7)  ↑↑↑                  ↑                  ↑↑    (5)                                                    
  135. #                        ↑                   ↑                                                                            
  136. #                         ↑                  ↑                                                                            
  137. #                          ↑                 ↑                 ↑                                                          
  138. #                           ↑                ↑                ↑                                                           
  139. #                            ↑               ↑               ↑                                                            
  140. #                             ↑              ↑              ↑                                                             
  141. #                              ↑             ↑             ↑                                                              
  142. #                                            ↑            ↑                                                               
  143. #                                            ↑           ↑                                                                
  144. #                                ↑           ↑          ↑                                                                 
  145. #                                 ↑          ↑         ↑                                                                  
  146. #                                  ↑         ↑        ↑                                                                   
  147. #                                   ↑        ↑                                                                            
  148. #                                    ↑       ↑                                                                            
  149. #                                     ↑      ↑                                                                            
  150. #                                      ↑     ↑     ↑                                                                      
  151. #                                       ↑    ↑    ↑                                                                       
  152. #                                        ↑   ↑   ↑                                                                        
  153. #                                         ↑  ↑  ↑                                                                         
  154. #                                          ↑ ↑ ↑                                                                          
  155. #                                           ↑↑                                                                           
  156. #                                            ↑   (6)                                                                       
  157.  
Success #stdin #stdout 0.23s 19364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Triangles: 70
[(0, 1, 4),
 (0, 1, 7),
 (0, 1, 8),
 (0, 1, 9),
 (0, 1, 11),
 (0, 1, 14),
 (0, 2, 3),
 (0, 2, 4),
 (0, 2, 6),
 (0, 2, 9),
 (0, 2, 12),
 (0, 2, 15),
 (0, 3, 4),
 (0, 3, 5),
 (0, 3, 13),
 (0, 4, 5),
 (0, 4, 6),
 (0, 4, 7),
 (0, 4, 9),
 (0, 4, 15),
 (0, 5, 6),
 (0, 5, 13),
 (0, 6, 9),
 (0, 6, 12),
 (0, 6, 15),
 (0, 7, 8),
 (0, 7, 11),
 (0, 7, 14),
 (0, 7, 15),
 (0, 8, 11),
 (0, 8, 14),
 (0, 9, 12),
 (0, 9, 15),
 (0, 11, 14),
 (0, 12, 15),
 (1, 2, 4),
 (1, 2, 9),
 (1, 4, 7),
 (1, 4, 11),
 (1, 8, 9),
 (2, 3, 9),
 (2, 4, 6),
 (2, 4, 9),
 (2, 4, 12),
 (2, 4, 15),
 (3, 4, 5),
 (3, 4, 9),
 (3, 4, 10),
 (3, 4, 13),
 (3, 4, 16),
 (3, 9, 10),
 (4, 5, 10),
 (4, 5, 13),
 (4, 5, 15),
 (4, 5, 16),
 (4, 6, 7),
 (4, 6, 9),
 (4, 6, 12),
 (4, 6, 15),
 (4, 7, 11),
 (4, 9, 12),
 (4, 9, 15),
 (4, 10, 13),
 (4, 10, 16),
 (4, 12, 15),
 (4, 13, 16),
 (5, 6, 15),
 (5, 15, 16),
 (6, 7, 15),
 (7, 14, 15)]
https://ideone.com/g61dUS
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!