13
\$\begingroup\$

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\$ 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: All 5-robot walks.

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.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Kagey Nov 27 at 1:32
  • \$\begingroup\$ If the robot goes over the same point 3 or more times, how do we count that for self-intersections? \$\endgroup\$ – xnor Nov 27 at 1:36
  • \$\begingroup\$ @xnor, do you have an example? \$\endgroup\$ – Peter Kagey Nov 27 at 1:36
  • \$\begingroup\$ @PeterKagey Nope, I haven't checked whether it's possible. \$\endgroup\$ – xnor Nov 27 at 1:37
  • 2
    \$\begingroup\$ On the "retraces steps" problem, [1,2,3,4,5,6] does interesting things. \$\endgroup\$ – Draco18s Nov 27 at 21:31
4
+100
\$\begingroup\$

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
    print(' ',count,'loops made',end='')
    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:
            add_point((a.x0,a.y0))
        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]))
                        add_point(point)
                        #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.

\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – HyperNeutrino Nov 28 at 14:14
  • \$\begingroup\$ 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. \$\endgroup\$ – Alexey Burdin Nov 28 at 14:28
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – HyperNeutrino Nov 28 at 14:38
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Kagey Nov 28 at 22:52
  • \$\begingroup\$ 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 \$\endgroup\$ – Peter Kagey Nov 30 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.