# Circular robot instructions

This challenge is based on Project Euler problem 208. Also related to my Math Stack Exchange question, Non-self-intersecting "Robot Walks".

You have a robot that moves in arcs which are $$\1/n$/extract_tex] of a circle, with each step turning toward the left or to the right. The robot takes in an array of instructions of the form $$\(a_1, a_2, \dots, a_{2m})\$$ with $$\a_k \in \mathbb N_0\$$. The robot follows these instructions by taking $$\a_1\$$ steps to the right, followed by $$\a_2\$$ steps to the left, followed by $$\a_3\$$ steps to the right, continuing in this alternating fashion until completing the final instruction by taking $$\a_{2m}\$$ steps to the left. If the robot is in the same position (and same orientation) that it began in, then it terminates, otherwise, it starts the sequence of moves over. The goal of this challenge is to write a program that takes in an integer $$\n \geq 2\$$ and a list of instructions $$\(a_1, a_2, \dots, a_{2m})\$$ and computes how many self-intersections the robot's path contains. # Example For example, with $$\n = 5\$$, these are the following walks for [1,2], [1,3], [1,4], [2,3], [2,4], and [3,4] respectively: The number of intersections are 0, 5, 10, 0, 5, and 0 respectively. ### Play Want to try it out for yourself? You can use the left/right arrow keys on your computer via this web app forked from Github user cemulate. Change the step size by modifying the n=6 parameter in the URL. Change the initial walk by modifying the w=5,3 parameter in the URL, or remove the initial walk by removing the &w=5,3 parameter altogether. # Test data  n | instructions | output ----+---------------+-------- 3 | [3,0] | 0 3 | [3,1] | 3 3 | [3,3] | 1 3 | [3,2,3,1] | 2 6 | [1,1] | 0 6 | [5,1] | 3 6 | [5,2] | 1 6 | [5,3] | 3 6 | [5,4] | 6 6 | [1,1,1,5] | 3 6 | [1,2,3,4] | 0 6 | [1,2,3,4,5,6] | 8 7 | [2,3,1,3,1,1] | 14 7 | [3,1,4,1] | 56 19 | [1,2] | 0  Note: You can assume that the instructions will not cause the robot to retrace it's track (as in $$\n = 6\$$ and [1,4,2,3] or $$\n = 7\$$ and [2,3,1,3].) That is, the robot may intersect its path tangentially or transverally, but it will not retrace a step. You can also assume that there will be a finite number of intersections (e.g., [5,5] will never be an instruction for $$\n = 6\$$). # Challenge Your program must take two parameters • A positive integer, n, the reciprocal of which gives the step size, and • An even-length array of nonnegative integers, a, the instruction for the robot. Your program must output a single integer, which counts the number of times that the robot intersects its path, tangentially (as in $$\n=6\$$ with [5,3]) or transverally (as in $$\n=5\$$ with [1,3]). This is a challenge, so the shortest code wins. • @Arnauld, thanks for the comment. I mentioned this briefly at the end of the "test data" section, but I added it to the "challenge" section now too. Please suggest more clarifying edits if you see anything unclear. – Peter Kagey Nov 27 '19 at 1:32 • If the robot goes over the same point 3 or more times, how do we count that for self-intersections? – xnor Nov 27 '19 at 1:36 • @xnor, do you have an example? – Peter Kagey Nov 27 '19 at 1:36 • @PeterKagey Nope, I haven't checked whether it's possible. – xnor Nov 27 '19 at 1:37 • On the "retraces steps" problem, [1,2,3,4,5,6] does interesting things. – Draco18s no longer trusts SE Nov 27 '19 at 21:31 ## 1 Answer # Python 3.8 (pre-release), 1533 bytes def w(n,ll,ans): global p,q from math import sin,cos,pi,atan2 def y(s,e,f,a,b): x,y=f(s),f(e) g=lambda a,b,x:0<=(x-a)%2<=b-a while e-s>1e-15: m=(s+e)/2 z=f(m) if x*z<=0: e,y=m,z else: s,x=m,z return (g(a,b,s)or g(a,b,e))and[s]or[] from fractions import Fraction as R s,v,d=(0,0,R(1,2)),[],1 while True: for l in ll: b=s[2]+R(1,2)*d c=s+(R(2,n)*l,d,(s[0]-cos(b*pi),s[1]-sin(b*pi)),b,b-R(2,n)*l*d) if l: v.append(c) s=(c[5][0]+cos(c[7]*pi),c[5][1]+sin(c[7]*pi),(c[7]-R(1,2)*d)%R(2)) d=-d if s[2]==R(1,2): break e,l=enumerate,len(v) q=lambda x:all(abs(i)<1e-7 for i in x) p=[] h=lambda i,p:any(all(q([j-k]) for j,k in zip(i,a))for a in p) def z(u): global p,q for i in u: if not h(i,p): p.append(i) if all(abs(i)<1e-6 for i in s[:2])and l>1: [z([c[:2]]) for c in v if c[3]==R(2)] x_=[t_ for n,c in e(v) for m,d in e(v) if (n-m)%l not in [0,1,l-1] and len(t_:=[(f,t) for f,g in [(c,d),(d,c)]if not q(x:=[f[5][i]-g[5][i]for i in[0,1]])and (a:=x[0])**2+(b:=x[1])**2<=4+1e-14 and(t:=sum((y((r:=[1,-1][b<0]*2/pi*atan2((1-(u:=a/(a*a+b*b)**.5)*u)**.5,u-1))-i,r+j,lambda t:(a+cos(pi*t))**2+(b+sin(pi*t))**2-1,*sorted(f[6:]))for i,j in[(1,0),(0,1)]),[]))])==2] [z([i for i in x[1] if h(i,x[0])])for x in[[[(f[5][0]+cos(i*pi),f[5][1]+sin(i*pi))for i in t]for f,t in t_]for t_ in x_]] print(len(p),sep='',end='') if len(p)!=ans: print(min((abs(i[0]-j[0])+abs(i[1]-j[1]),n,m) for n,i in e(p) for m,j in e(p) if n!=m)) else: print('') else: print(0)  Try it online! ## Python 2 (PyPy), 1580 bytes n,ll=map(eval,input().split(' ')) from math import sin,cos,pi,atan2 #and let's implement the bisection def y(s,e,f,a,b):#solve f=0 within (s,e) if x in (a,b) x,y=f(s),f(e) g=lambda a,b,x:0<=(x-a)%2<=b-a while e-s>1e-15:# or g(a,b,s)!=g(a,b,e): m=(s+e)/2 z=f(m) if x*z<=0: e,y=m,z else: s,x=m,z c,d=g(a,b,s),g(a,b,e) #c,d #True,True [s] #True,False [s] #False,True [s] #False,False [] return (c or d)and[s]or[] from fractions import Fraction as R #the start point s=(0,0,R(1,2)) #now let's compute the arcs #we need to store x0,y0,angle,length,direction,center,start angle,end angle #arcs array v=[] d=1#the direction, 1 for clockwize while True: for l in ll: b=s[2]+R(1,2)*d#start angle c=s+(R(2,n)*l,d,(s[0]-cos(b*pi),s[1]-sin(b*pi)),b,b-R(2,n)*l*d)#the arc if l: v.append(c) s=(c[5][0]+cos(c[7]*pi),c[5][1]+sin(c[7]*pi),(c[7]-R(1,2)*d)%R(2)) d=-d if s[2]==R(1,2): break e,l=enumerate,len(v) q=lambda x:abs(x)<1e-7 p=[]#array of intersection points #like in array h=lambda i,p:any(all(q(j-k) for j,k in zip(i,a))for a in p) def z(u):#add points if not in array global p,q #print(p,u) for i in u: if not h(i,p): p.append(i) if all(abs(i)<1e-6 for i in s[:2])and l>1: #returned to the same point for n,c in e(v): if c[3]==R(2):z([c[:2]]) for m,d in e(v): if (n-m)%l not in [0,1,l-1]: #compute the intersection x=[] for f,g in [(c,d),(d,c)]: a,b=[f[5][i]-g[5][i]for i in[0,1]] if q(a)and q(b): break if a*a+b*b>4+1e-14: break u=a/(a*a+b*b)**.5 #the angle from a to b r=[1,-1][b<0]*2/pi*atan2((1-u*u)**.5,u-1) t=sum( (y(r-i,r+j,lambda t:(a+cos(pi*t))**2+(b+sin(pi*t))**2-1,\ *sorted(f[6:]))for i,j in[(1,0),(0,1)]),[]) #that's it if not t: break x.append([(f[5][0]+cos(i*pi),f[5][1]+sin(i*pi))for i in t]) else: #intersection points z([i for i in x[1] if h(i,x[0])]) print(len(p)) else: #infinite, return 0 print(0)  Runs in all test cases. # Python 3.8 + sympy, ungolfed, # covering almost all test cases (except 7 and 19 -- sympy can't simplify some expressions) at least to know what you have to bear. Major improvement in comparison with previous version is that: 1) It simply holds array of intersection points, 2) Any arc end counts as intersection if arc length $$\=2\pi\$$ unless arc array length is $$\1\$$ Still need to be rewritten into precise $$\i^{\frac{2\pi}{n}}\$$ arithmetic from sympy import * R=Rational angle=R(0) class Arc: def __init__(self,x0,y0,angle,length,direction): #','.join('self.%s'%i for i in 'x0,y0,angle,length'.split(',')) (self.x0, self.y0, self.angle, self.length, self.dir)=x0,y0,angle,length,direction self.start=(angle+pi/R(2)*direction)#%(R(2)*pi) self.end_=self.start-self.length*self.dir self.center=(x0-cos(self.start),y0-sin(self.start)) def i(self,a0): #t=symbols('t') #param_form=(self.center[0]+cos(self.start+t), # self.center[1]+sin(self.start+t)) #z=solveset((a.center[0]-param_form[0])**2+ # (a.center[1]-param_form[1])**2-1,t) #return z #to (a + cos(t))^2 + (b + sin(t))^2 = 1 a,b=[self.center[i]-a0.center[i] for i in [0,1]] try: d={frozenset([-cos(3*pi/7) - sin(pi/14), -2*sin(3*pi/7)]):False, frozenset([cos(3*pi/7) + sin(pi/14), 2*sin(3*pi/7)]):False} if (frozenset([a,b]) in d and d[frozenset([a,b])]) or \ (frozenset([a,b]) not in d and a**R(2)+b**R(2)>R(4)): return set() if a**R(2)+b**R(2)==R(4): #https://www.wolframalpha.com/input/?i=%28a%2Bcos%28t%29%29%5E2%2B%28b%2Bsin%28t%29%29%5E2%3D1+and+a%5E2%2Bb%5E2%3D4 #s=R(-1,2)*sqrt(R(4)-a**R(2)) #c=R(-1,2)*a if (a==R(2)): return set([pi]) return set([(R(-1) if b<R(0) else R(1))*R(2)*\ atan2(sqrt(R(4)-a**R(2)),a-R(2))]) except Exception: print((a,b)) raise #https://www.wolframalpha.com/input/?i=%28a%2Bcos%28t%29%29%5E2%2B%28b%2Bsin%28t%29%29%5E2%3D1 if a!=R(0) and a!=R(2) and ((z0:=b**R(2)+a**R(2)-R(2)*a)==0 or\ abs(float(z0))<1e-6): s=R(2)*(R(-1) if b<R(0) else R(1))*atan2(sqrt(-(a-R(2))*a),(a-R(2))) return set([s]) if not ((z0:=b**R(2)+a**R(2)-R(2)*a)==0 or\ abs(float(z0))<1e-6): s=sqrt(-a**R(4)-2*a**R(2)*b**R(2)+4*a**R(2)-b**R(4)+R(4)*b**R(2)) r=set() for sg in [R(-1),R(1)]: d=a**R(3)-2*a**R(2)+sg*b*s+a*b**R(2)-R(2)*b**R(2) if d!=0 or abs(float(d))>=1e-6: r.add(R(2)*atan2((sg*s-R(2)*b),z0)) return r #thank you so much for such interesting coding challenge if a==R(0) and b==R(0): return set() print((a,b)) raise Exception('') def end(self): return (self.center[0]+cos(self.start-self.length*self.dir), self.center[1]+sin(self.start-self.length*self.dir), (self.end_-pi/R(2)*self.dir)%(R(2)*pi)) from PIL import Image,ImageDraw d=300 x0,y0=d//2,d//2 r,r0=20,2 n,l=7 , [2,3,1,3,1,1]#5,[3,4] s=(r''' 3 | [3,0] | 0 3 | [3,1] | 3 3 | [3,3] | 1 3 | [3,2,3,1] | 2 6 | [1,1] | 0 6 | [5,1] | 3 6 | [5,2] | 1 6 | [5,3] | 3 6 | [5,4] | 6 6 | [1,1,1,5] | 3 6 | [1,2,3,4] | 0 6 | [1,2,3,4,5,6] | 8 7 | -[2,3,1,3,1,1] | 14 7 | -[3,1,4,1] | 56 19 | -[1,2] | 0''' r'''5 | -[0,1,1,3,4,1,2,1,1,4,1,2,1,3] | 2 ''' ) def add_point(point): global points,count if not any(all(abs(float(j-k))<1e-6 \ for j,k in zip(i,point)) for i in points): points.append(point) count+=1 import re for n,l,ans in\ re.findall(r'\s*(\d+)\s*\|\s*\[(.*?)$\s*\|\s*(\d+)',s):
#[(5,'0,1,1,3,4,1,2,1,1,4,1,2,1,3',2)]:
#[('7', '2,3,1,3,1,1', '14')]:
#    [('6', '1, 1', '0')]:
#    [(6,'1,1,1,5',3)]:
print(n,l,end='')
n=int(n)
l=[int(i.strip()) for i in l.split(',')]
fn='196399/%d_%s.png'%(n,'_'.join(map(str,l)))
start=(0,0,pi/R(2))
dir_=1
a_array=[]
for count in range(30):
for l_ in l:
a=Arc(*start,pi/R(n)*R(2*l_),dir_*2-1)
a_array.append(a)
start=[simplify(i) for i in a.end()]
#print(start,a.center,a.start,a.end_)
dir_^=1
if (abs(float(start[0]))<1e-3) and \
(abs(float(start[1]))<1e-3) and start[2]%(R(2)*pi)==pi/R(2):
break
##        else:
##            continue
##        break
a_array=[a for a in a_array if a.length!=0]
print(' ',len(a_array),end='')
count=0
points=[]
if len(a_array)==1:
print(' ans=%s, count=%d'%(ans,count))
continue
for n,a in enumerate(a_array):
if a.length==R(2)*pi:
for m,b in enumerate(a_array):
if (n-m)%len(a_array) not in [0,1,len(a_array)-1]:
#print('.',sep='',end='')
try:
i_=[list(a.i(b)),list(b.i(a))]
p_=list(list(0<=((-R(d_)*(i-st))%(R(2)*pi))<=l_ for i in s) \
for s,l_,st,d_ in \
zip(
(i_),
[a.length,b.length],
[a.start,b.start],
[a.dir,b.dir]
))
if all(any(i) for i in p_):
for t,angle in zip(p_[0],i_[0]):
if t:break
point=tuple(i+f(angle) for i,f in zip(a.center,[cos,sin]))
#print('\n',(n,m),sep='')
except Exception:
print(i_,[a.length,b.length],[a.start,b.start])
raise
#assert count//2==int(ans)
print(' ans=%s, count=%d'%(ans,count))
#break
continue
xy=[sum(map(f,a_array))/len(a_array) for f in \
[(lambda i:lambda a:a.center[i])(i) for i in [0,1]]]
image = Image.new('RGB',(d,d),'white')
draw = ImageDraw.Draw(image)
point=lambda x,y:draw.ellipse((x0-r0+x,y0-r0-y,x0+r0+x,y0+r0-y),'blue','blue')
for a in a_array:
start=[a.x0,a.y0,a.angle]
dir_=a.dir
point(*[int((i-xy_)*R(r)) for i,xy_ in zip(start[:2],xy)])
c=[int((i-xy_)*R(r)) for i,xy_ in zip(a.center,xy)]
draw.arc((c[0]-r+x0,-c[1]-r+y0,c[0]+r+x0,-c[1]+r+y0),
*([int(-a.start*180/pi),int(-a.end_*180/pi)][::dir_]),
0x3a2af6)
#image.save(fn,'PNG')
#break
#image.show()
a=a_array
f=lambda n,m:(a[n].i(a[m]),a[n].start,a[n].length,a[n].dir)
g=lambda a,b:list(list((0,((-R(d_)*(i-st))%(R(2)*pi)),l_) for i in s) \
for s,l_,st,d_ in \
zip(
(i_),
[a.length,b.length],
[a.start,b.start],
[a.dir,b.dir]
))


Output:

3 3,0  0 loops made  1 ans=0, count=0
3 3,1  2 loops made  6 ans=3, count=3
3 3,3  0 loops made  2 ans=1, count=1
3 3,2,3,1  0 loops made  4 ans=2, count=2
6 1,1  29 loops made  60 ans=0, count=0
6 5,1  2 loops made  6 ans=3, count=3
6 5,2  1 loops made  4 ans=1, count=1
6 5,3  2 loops made  6 ans=3, count=3
6 5,4  5 loops made  12 ans=6, count=6
6 1,1,1,5  2 loops made  12 ans=3, count=3
6 1,2,3,4  2 loops made  12 ans=0, count=0
6 1,2,3,4,5,6  1 loops made  12 ans=8, count=8


But it can generate such things although it was not in the task.

• 50% of test cases is not good enough. All answers have to solve the problem fully, and to be a serious competitor, one must at least attempt to golf it. – HyperNeutrino Nov 28 '19 at 14:14
• I don't know what is wrong with intersection being end points, I already count intersections with <= (line 124). I already invested more than 7 hours into it and it's not enough, it needs to be re-worked to exact calculations without sympy, although after embedding wolframalpha solution of $(a+\cos(t))^2+(b+\sin(t))^2=1$ along with corner cases I did not want to continue with it at all, hard-coding the formulas (as one will eventually do if does not prefer a numerical method) is mandatory part of the task, it's boring. See my point? Golfing will be after de-sympy-fying. – Alexey Burdin Nov 28 '19 at 14:28
• That's fair. The golfing part is less significant; getting rid of most of the spaces is fine for a first attempt. Draft answers are usually discouraged (I'm not sure if they're disallowed, but very uncommon at least) though, outside of proof of feasibility for problems that have questionable solvability. – HyperNeutrino Nov 28 '19 at 14:38
• For what it's worth, I really appreciate this submission as a proof of concept—I voted it up. Even if you don't complete it, I think this can be a valuable resource for other people attempting the challenge. – Peter Kagey Nov 28 '19 at 22:52
• I'm very impressed by this solution and the effort that went into it. I've put a bounty on this question that I'll be able to award to you in 24 hours – Peter Kagey Nov 30 '19 at 1:24