fork download
copy 
  1. E=enumerate
  2. def f(b):
  3.  d={(x,y):v for x,r in E(b)for y,v in E(r)};p={i for i in d if d[i]*~-all(d.get((i[0]+X,i[1]+Y))for X in[-1,0,1]for Y in[-1,0,1]if X*Y)};q,t=[([],p)],[]
  4.  for r,p in q:
  5.   if not p:return len(r)
  6.   Q=[[M:=min(p)]];p-={M};S=[[M]]
  7.   for R in Q:
  8.    for a in[-1,0]:
  9.     if d.get(V:=(R[a][0],R[a][1]-a+~a))and(Z:=[[V]+R,R+[V]][a])not in S:Q+=Z,;S+=Z,
  10.   F,T=[[i]for i in S],{}
  11.   for R in F:
  12.    n=[(x+1,y)for x,y in R[-1]]
  13.    if all(d.get(N)for N in n):F+=R+[n],
  14.    else:T[e]=T.get(e:=sum(map(len,R)),[])+[R]
  15.   q+=[(r+[R],p-{j for k in R for j in k})for I in T for R in T[I]]
  16.  
  17. s = """
  18. [[1]] -> 1
  19. [[1,1]] -> 1
  20. [[1],[1]] -> 1
  21. [[1,0,1]] -> 2
  22. [[1,0],[0,0]] -> 1
  23. [[1,0],[0,1]] -> 2
  24. [[1,0],[1,1]] -> 2
  25. [[1,1,1],[1,0,1]] -> 3
  26. [[0,1,0],[1,1,1],[0,1,0]] -> 2
  27. [[1,1,1],[1,0,1],[1,1,1]] -> 4
  28. [[1,1,0],[1,1,1],[0,1,1]] -> 2
  29. [[1,0,1,0],[1,1,1,1],[1,0,1,0]] -> 3
  30. [[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,0]] -> 4
  31. [[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,1]] -> 5
  32. [[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,1,1,1]] -> 4
  33. [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]] -> 3
  34. [[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]] -> 4
  35. [[0,0,1,0,0],[0,1,1,1,0],[1,1,1,1,1],[0,1,1,1,0],[0,0,1,0,0]] -> 3
  36. [[1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 1, 0, 1, 1, 1], [0, 1, 1, 1, 0, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1, 0], [1, 1, 0, 1, 1, 1, 0, 1]] -> 7
  37. [[0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]] -> 2
  38. """
  39. for i in filter(None, s.split('\n')):
  40. 	a, b = map(eval, i.split(' -> '))
  41. 	assert f(a) == b
  42.  
  43. print('tests passed!')
Success #stdin #stdout 0.11s 14112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tests passed!
https://ideone.com/INjn92
language:
Python 3 (python  3.12)
created:
10 days 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!