# 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. Nov 27, 2019 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, 2019 at 1:36 • @xnor, do you have an example? Nov 27, 2019 at 1:36 • @PeterKagey Nope, I haven't checked whether it's possible. – xnor Nov 27, 2019 at 1:37 • On the "retraces steps" problem, [1,2,3,4,5,6] does interesting things. Nov 27, 2019 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)  Try it online! 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. Nov 28, 2019 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. Nov 28, 2019 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. Nov 28, 2019 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. Nov 28, 2019 at 22:52
• 1496 bytes with some very minor golfs (removed loads of spaces; changed some multi-byte variables to single-byte uppercase characters; changed the while True to while 1; etc.) You could paste both your function and this function I linked in text-compare.com for an easy comparison of the changes I did. I'm sure an actual Python golfer could reduce the byte-count drastically, but unfortunately I'm not too skilled in Python. Nice answer btw! Feb 26, 2020 at 7:39