fork download
copy 
  1. #!/usr/bin/env python
  2. # coding=utf-8
  3. import math
  4. from copy import deepcopy
  5.  
  6. zrkadla = []
  7.  
  8. C = (42,0)
  9. H = 8
  10. def dist(poz1, poz2, smer):
  11.     if smer == 'h' or smer == 'd':
  12.         return abs(poz1[1] - poz2[1])
  13.     else:
  14.         return abs(poz1[0] - poz2[0])
  15.  
  16. def trafi(poz, smer, z):
  17.     if   smer == "h":
  18.         return poz[0] == z[0] and poz[1] < z[1]
  19.     elif smer == "d":
  20.         return poz[0] == z[0] and poz[1] > z[1]
  21.     elif smer == "p":
  22.         return poz[1] == z[1] and poz[0] < z[0]
  23.     else:
  24.         return poz[1] == z[1] and poz[0] > z[0]
  25.  
  26. def pretinaZrkadlo(poz, smer):
  27.     trafeneZrkadlo = -1
  28.     d = 0
  29.     for i in range(len(zrkadla)):
  30.         if trafi(poz, smer, zrkadla[i]):
  31.             tmp = dist(zrkadla[i],poz, smer)
  32.             if trafeneZrkadlo == -1 or tmp < d:
  33.                 trafeneZrkadlo = i
  34.                 d = dist(zrkadla[trafeneZrkadlo], poz, smer)
  35.     return trafeneZrkadlo
  36.  
  37. def trafiCiel(poz, smer):
  38.     return trafi(poz, smer, C)
  39.  
  40. def solveA(natocenie, z, smer, path, depth):
  41.     if natocenie[z][0]:
  42.         if natocenie[z][1] == "A":
  43.             path+='A'
  44.             if smer == "h":
  45.                 return solve(natocenie, zrkadla[z], "l", path, depth + 1)
  46.             elif smer == "d":
  47.                 return solve(natocenie, zrkadla[z], "p", path, depth + 1)
  48.             elif smer == "p":
  49.                 return solve(natocenie, zrkadla[z], "d", path, depth + 1)
  50.             else:
  51.                 return solve(natocenie, zrkadla[z], "h", path, depth + 1)
  52.     else:
  53.         natocenie[z][0] = True
  54.         natocenie[z][1] = 'A'
  55.         path+='A'
  56.         if smer == "h":
  57.             return solve(natocenie, zrkadla[z], "l", path, depth + 1)
  58.         elif smer == "d":
  59.             return solve(natocenie, zrkadla[z], "p", path, depth + 1)
  60.         elif smer == "p":
  61.             return solve(natocenie, zrkadla[z], "d", path, depth + 1)
  62.         else:
  63.             return solve(natocenie, zrkadla[z], "h", path, depth + 1)
  64.  
  65. def solveB(natocenie, z, smer, path, depth):
  66.     if natocenie[z][0]:
  67.         if natocenie[z][1] == "B":
  68.             path+='B'
  69.             if smer == "h":
  70.                 return solve(natocenie, zrkadla[z], "p", path, depth + 1)
  71.             elif smer == "d":
  72.                 return solve(natocenie, zrkadla[z], "l", path, depth + 1)
  73.             elif smer == "p":
  74.                 return solve(natocenie, zrkadla[z], "h", path, depth + 1)
  75.             else:
  76.                 return solve(natocenie, zrkadla[z], "d", path, depth + 1)
  77.     else:
  78.         natocenie[z][0] = True
  79.         natocenie[z][1] = 'B'
  80.         path+='B'
  81.         if smer == "h":
  82.             return solve(natocenie, zrkadla[z], "p", path, depth + 1)
  83.         elif smer == "d":
  84.             return solve(natocenie, zrkadla[z], "l", path, depth + 1)
  85.         elif smer == "p":
  86.             return solve(natocenie, zrkadla[z], "h", path, depth + 1)
  87.         else:
  88.             return solve(natocenie, zrkadla[z], "d", path, depth + 1)
  89.  
  90. def solve(natocenie, poz, smer, cesta, hlbka):
  91.     trafeneZ = pretinaZrkadlo(poz, smer)
  92.  
  93.     if trafiCiel(poz, smer):
  94.         if trafeneZ != -1:
  95.             if dist(poz, C, smer) < dist(poz, zrkadla[trafeneZ], smer):
  96.                 return cesta
  97.         else:
  98.             return cesta
  99.  
  100.     if hlbka < H and trafeneZ != -1:
  101.         A = solveA(deepcopy(natocenie), trafeneZ, smer, deepcopy(cesta), hlbka)
  102.         B = solveB(deepcopy(natocenie), trafeneZ, smer, deepcopy(cesta), hlbka)
  103.         if A == None: A = "X" * (H + 1)
  104.         if B == None: B = "X" * (H + 1)
  105.         if len(A) == len(B):
  106.             return min(A,B)
  107.         if len(A) < len(B):
  108.             return A
  109.         else:
  110.             return B
  111.     else:
  112.         return "X" * (H + 1)
  113.  
  114. if __name__ == "__main__":
  115.     f = open("P2-input.txt","r")
  116.     for line in f:
  117.         a = map(int, line.split())
  118.         if len(a) > 0:
  119.             zrkadla.append(a)
  120.     f.close()
  121.     natocenie = [[False, "A"] for i in range(len(zrkadla))]
  122.  
  123.     sol = "X"
  124.     while sol[0] == "X":
  125.         sol = solve(natocenie, [0,0], "h", "", 0)
  126.         H += 1
  127.  
  128.     print sol
  129.  
Success #stdin #stdout #stderr 0.02s 6160KB
comments (?)
stdin
copy 
-50 -49
-50 -46
-50 -29
-50 -20
-50 -2
-50 12
-49 -17
-49 15
-49 20
-48 -10
-48 4
-48 43
-47 -27
-47 -26
-47 7
-47 23
-46 31
-46 43
-45 -12
-45 -5
-45 29
-44 -23
-44 3
-43 -33
-43 -32
-43 -31
-43 7
-43 46
-42 -16
-42 8
-42 12
-42 23
-42 23
-42 36
-42 46
-41 -40
-41 11
-41 12
-40 -44
-40 -40
-40 -26
-40 28
-39 -24
-38 -39
-38 -1
-38 6
-37 -41
-37 -8
-37 9
-37 11
-36 -40
-36 -40
-36 -9
-36 -4
-36 8
-34 -40
-34 -35
-34 27
-33 -1
-32 -38
-32 -32
-32 3
-32 11
-31 -42
-31 -29
-31 -13
-30 24
-30 24
-30 28
-30 29
-29 -37
-29 -6
-29 -6
-28 -39
-28 -34
-28 -28
-28 9
-28 49
-27 -49
-27 -9
-27 -6
-27 26
-26 -38
-26 -29
-26 11
-26 32
-25 -1
-24 7
-24 31
-24 40
-23 -1
-23 10
-22 -22
-22 -16
-22 23
-20 -21
-20 23
-20 33
-20 37
-19 -38
-19 15
-19 42
-18 -34
-18 -34
-18 -6
-18 27
-18 45
-17 -42
-16 -38
-16 -31
-16 -30
-16 40
-15 -42
-15 26
-14 -26
-14 25
-14 46
-13 -35
-13 -30
-13 -8
-12 -35
-12 -25
-12 -11
-12 28
-12 42
-12 45
-10 2
-10 26
-9 1
-9 44
-9 48
-8 -24
-8 -7
-8 24
-7 -21
-7 -16
-7 16
-7 19
-7 36
-7 39
-6 -33
-6 -30
-6 37
-6 39
-5 6
-5 43
-4 -11
-3 -23
-3 29
-3 46
-2 -18
-1 -12
-1 -3
-1 12
-1 43
-1 44
-1 46
0 11
1 -23
1 -19
1 2
2 19
3 -16
4 -25
4 -20
4 -10
4 19
5 -36
5 21
5 24
6 -17
7 -6
8 -41
8 -37
8 -29
8 -27
8 -25
8 -24
8 -19
8 21
9 -31
9 5
10 -23
10 -19
10 50
11 -3
11 4
11 11
11 35
12 -45
12 -6
13 11
13 15
14 -35
14 28
15 -26
15 -22
15 20
15 29
15 39
16 -4
16 0
16 2
16 21
17 -29
17 10
17 31
18 -35
18 8
18 39
19 -22
19 -18
19 -9
21 8
22 -41
22 -36
22 -34
22 -7
22 25
23 -47
23 27
23 38
24 -41
24 9
25 -26
25 -19
25 -6
26 -42
26 35
27 -44
28 -43
28 -26
28 -6
28 18
28 34
28 46
29 -42
29 -37
29 11
29 17
29 37
30 -17
30 -16
30 12
30 48
31 22
32 -46
32 -23
32 -17
32 29
33 -42
33 4
33 39
34 -39
34 -11
34 40
35 13
35 24
35 40
35 42
35 50
36 -44
36 -16
37 -43
37 -35
37 8
37 13
37 22
37 23
37 33
37 41
38 -34
38 -33
38 -25
38 -24
38 25
38 28
38 34
39 -25
39 31
39 31
39 32
40 -30
40 -10
40 33
40 34
41 5
41 14
41 48
42 -15
42 -11
42 -2
42 8
42 15
43 -12
43 -1
43 17
43 37
44 -8
44 42
45 -39
45 -28
45 -24
45 -20
45 24
46 -50
46 -3
46 9
46 9
46 11
47 -28
47 -22
47 -3
47 0
48 -5
48 -1
48 6
49 -9
50 -47
50 -43
50 17
stdout
copy 
Standard output is empty
stderr
copy 
ERROR: /home/R12opY/prog.pl:129:0: Syntax error: Unexpected end of file
ERROR: Stream user_input:0:322 Syntax error: Unexpected end of file
https://ideone.com/bJ6FAl
language:
Prolog (swi 7.6.4)
created:
10 years 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!