Construct this point

Question

Given a constructible point \$(x, y) \in \mathbb R^2\$, output the steps required to construct \$(x, y)\$

Constructing a point

Consider the following "construction" of a point \$(\alpha, \beta)\$ in the Cartesian plane:

Begin with the points \$(0, 0)\$ and \$(1, 0)\$. Then, more points can be added by performing a finite number of the following steps:

• Draw the unique infinitely long line between two existing points \$(x, y)\$ and \$(x', y')\$

• Draw the unique circle centered on an existing point \$(x, y)\$ that passes through a distinct existing point \$(x', y')\$

• Add a point \$(x, y)\$ where any two lines or circles intersect

For example, if we draw the line connecting \$(0, 0)\$ and \$(1, 0)\$, then the circle centered on \$(1, 0)\$ with radius \$1\$ (passes through \$(0, 0)\$), we can construct the point \$(2, 0)\$ where the circle and line intersect. Now, if we draw the circles centered on \$(0, 0)\$ and \$(2, 0)\$ that pass through \$(2, 0)\$ and \$(0, 0)\$ respectively, we construct the point \$(1, \sqrt 3)\$, and so on.

If both \$x\$ and \$y\$ are constructible numbers (i.e. there exists some closed form expression of \$x\$ and \$y\$ involving only integers, the 4 basic arithmetic operations and square roots), then \$(x, y)\$ can be constructed in a finite number of these steps.

---

This is a code-golf challenge, where you are provided, in exact form, two constructible numbers, \$x\$ and \$y\$, and should output the steps to construct the point \$(x, y)\$, beginning from the initial set of points \$S = \{(0, 0), (1, 0)\}\$.

As both \$x\$ and \$y\$ are constructible, they can be expressed as a finite combination of addition, multiplication, division, subtraction and square roots of integers - termed here as "closed form numbers". You may take input in any form that exactly represents any closed form number. This could be as an exact symbolic number (if your language has these), a string unambiguously representing the composition of the 5 operations (e.g. 7*sqrt(2)-sqrt(3), 7*s2-s3 or even sub(times(7, sqrt(2)), sqrt(3))), and so on. You may not input as floating point values. Note that the format you choose should be unambiguous for all possible inputs.

In short, you may choose any input format - not limited to strings - so long as that input format can represent any closed form number exactly and unambiguously. Additionally, be mindful of this standard loophole about encoding extra information into the input format - this is fairly loose, but try not to use formats that contain more information than just the 5 standard operations.

As output, you should produce some list of operations that, if followed, add the point \$(x, y)\$ to the set of constructed points \$S\$. By default, we will assume that all new points after each step are automatically added to \$S\$, and so you only need to output two possible instructions at each step:

• Draw a circle centered at a point \$(a, b)\$ going through a point \$(c, d)\$
• Draw a line through the points \$(a, b)\$ and \$(c, d)\$

This can be in any format that clearly includes both points necessary for each instruction, and which instruction is used. At the most basic, the options of [0, a, b, c, d] and [1, a, b, c, d] for circle and line respectively are completely fine. In short, you must be able to unambiguously distinguish each instruction from the next, the circle instruction from the line, and the two points \$(a, b)\$ and \$(c, d)\$. However, the values of \$a, b, c, d\$ must be exact constructible numbers.

Note that you may output any finite valid list of steps, not just the shortest.

This is a code-golf challenge, so the shortest code in each language wins

---

Worked example

Take the point \$H = (\sqrt 3, \sqrt 3)\$. This can be constructed in 8 steps, with the first point in the circle instruction being the center:

Line: (0, 0), (1, 0)
Circle: (1, 0), (0, 0)
Circle: (2, 0), (0, 0)
Circle: (0, 0), (2, 0)
Circle: (4, 0), (2, 0)
Line: (1, 0), (1, √3)
Line: (1, √3), (3, √3)
Line: (0, 0), (1, 1)

The construction lines from this can be seen as:

This can be extended with 5 more lines to construct the more complicated point \$(\sqrt 3, \sqrt 2)\$:

Line: (2, 0), (1, 1)
Line: (1, -√3), (3, -√3)
Line: (0, 0), (1, -1)
Line: (2-√2, √2), (√2, √2)
Line: (√3, √3), (√3, -√3)

Test cases

To be completed

Here, we use C (a, b), (x, y) to represent a circle with center \$(a, b)\$ and L (a, b), (x, y) a line that passes through the two points.

(x, y) -> Steps
(0, 0) -> []
(6, 0) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (4, 0), (2, 0)"]
(1, √3) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (0, 0), (2, 0)", "C (2, 0), (0, 0)"]
(1, 1) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (0, 0), (2, 0)", "C (4, 0), (2, 0)", "L (1, 0), (1, √3)"]
(-1/2, √2) -> ["L (0, 0), (1, 0)", "C (0, 0), (1, 0)", "C (-1, 0), (0, 0)", "L (-1/2, √3/2), (-1/2, -√3/2)", "C (1, 0), (0, 0)", "C (0, 0), (2, 0)", "C (2, 0), (0, 0)", "L (1, 0), (1, √3)", "L (0, 0), (1, 1)", "L (0, 0), (1, -1)", "L (√2, √2), (-√2, √2)"]
(1+√3+√2/2, 0) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (0, 0), (2, 0)", "L (1, √3), (1, 0)", "C (4, 0), (2, 0)", "L (1, √3), (3, √3)", "L (0, 0), (1, 1)", "L (2, 0), (1, 1)", "L (1, -√3), (3, -√3)", "L (√2, √2), (2, 0)", "L (2-√2, √2), (0, 0)", "C (1, 0), (1, 1+√2)", "L ((1+√2)/√2, 1/√2), ((1+√2)/√2, -1/√2)", "C ((1+√2)/√2, 0), ((1+√2)/2, √3))"]
(√2+√3, √5) -> ["L (0, 0), (1, 0)", "C (1, 0), (0, 0)", "C (2, 0), (0, 0)", "C (0, 0), (2, 0)", "L (1, √3), (1, 0)", "L (0, 0), (1, 1)", "L (0, 0), (1, -1)", "L (√2, √2), (√2, -√2)", "C (4, 0), (2, 0)", "L (1, √3), (3, √3)", "C (0, 0), (√2, √3)", "C (0, 0), (1, 0)", "C (√2, 0), (√2, √3)", "L (0, 1), (0, -1)", "C (0, √5), (0, 0)", "L (0, √5), (√5, √5)", "C (√2+√3, 0), (0, 0)", "L (√2+√3, 0), (√2+√3, √2+√3)"]

Answer 1

Python, 511 bytes

l=[(1,0,0,1,0)]
z,o='01'
def a(b,c):e=f'da{b}{c}2';v='dtm%s%ss32';l.extend([(0,b,0,c,0),(0,c,0,b,0),(1,e,v%(b,c),e,v%(c,b)),(0,e,0,0,0)]);return'a'+b+c
def m(b,c):l.append((0,0,0,c,0));return a(b,'m0'+c)
def t(b,c):l.append((1,0,p(b),p(c),p(m(b,o))));return't'+b+c
def d(b,c):l.append((1,0,1,p(b),p(m(o,c))));return'd'+b+c
def s(b):v=d(m(b,o),a(o,o));l.append((0,0,v,0,'m01'));return's'+b
def p(b):a(a(b,b),z);l.extend((a,c,b,e,d) for a,b,c,d,e in l[:]);return b
m(o,o)
def e(b,c):p(eval(b));p(eval(c));return l

Attempt This Online!

If we can assume the user evaluated the functions (so we don't have to call eval), we can just do e=lambda a,b:l.

The function is e, it takes as input the two coordinates. a is addition, m subtraction, t multiplication, d division, and s square root. o has to be used in place of 1, and z in place of 0.

Returns a list of objects to create, specifying coordinates in prefix notation, with single digits (so a32 = 5).

Here's how it works for \$(\sqrt2, 3)\$, for example:

The animation code:

import math
import matplotlib.pyplot as plt
from matplotlib import animation
from matplotlib.patches import Circle

def calc(s: str):
    if type(s) is int:
        return s, ''
    if s[0].isdigit():
        return int(s[0]), s[1:]
    v1, rem = calc(s[1:])
    if s[0] == 's':
        return v1**.5, rem
    v2, rem = calc(rem)
    return (v1+v2 if s[0]=='a' else v1-v2 if s[0]=='m' else v1*v2 if s[0]=='t' else v1/v2 if s[0]=='d' else None), rem

var = plt.subplots()
fig : plt.Subplot = var[0]
ax : plt.Axes = var[1]

artists = []

points = set()

dat = e('s(a(o,o))','s(a(o,a(o,o)))')
print(len(dat))
ax.axis('equal')
ax.plot(2**.5, 3**.5, 'bo')
objects = set()
for a, b, c, d, e in dat:
    b, c, d, e = (calc(x)[0] for x in (b, c, d, e))
    if (a,b,c,d,e) in objects:
        continue
    objects.add((a,b,c,d,e))
    if (b, c) not in points:
        artists.append(ax.plot(b, c, 'ro')[0])
        points.add((b, c))
    if (d, e) not in points:
        artists.append(ax.plot(d, e, 'ro')[0])
        points.add((d, e))
    if a == 1 and (b,c) != (d,e):
        artists.append(ax.axline((b,c),(d,e)))
    else:
        artists.append(ax.add_patch(Circle((b,c), math.hypot(b-d, c-e), fill=False)))

def update(frame):
    for i, art in enumerate(artists):
        art.set_visible(i < frame)


ani = animation.FuncAnimation(fig=fig, func=update, frames=len(artists)+20, interval=100)
plt.interactive(True)
plt.show(block=True)

Answer 2

JavaScript (Node.js), 366 bytes

P=(a,b=0,c=0,d=0,e=0)=>console.log(a,b,c,d,e)
L=x=>P(0,x)|P(x)|P(y=x+'/2',z=x+'/2*s3')|P(y,z,0,0,1)|P(x,z+'*2',x,0,1)
S=(b,a)=>`(${P(0,0,1,0,1),P(0,0,b)|P(b)|P(b+'/2',b+'/2*s3',a),b}-${a})`
D=(a,b)=>S(1,`(1-${P(a,0,S(a,b))|L(a)|L(1)|P(1,0,1,z=`(${a}/${b})`),z})`)
s=a=>P(S(0,1),0,a)|P(a,0,-1)|P(z=`(${a}-1)/2`,y=`(${a}+1)/2*s3`,z,-1+y,1)|P(z,0,a)|P(0,0,0,z='s'+a)||z

Try it online!

-24 from emanresu A

0 a b c d mean circle (a,b) through (c,d)

1 a b c d mean line through (a,b) and (c,d)

Should be quite golfable

• L provides line \$x=x_0\$, assuming \$x_0 \neq 0\$
• S subtracts two values
• D divides two values while creating point with given coords
• s gives square root

Notes

• Need confirm
• Some free points may sometimes give good: To draw \$x=0\$, a sequence Line((0,0),(1,0)), Circle((a,b),(0,0)), Line((2a,0),(a,b)), Line((0,2b)-(0,0)) should be shorter than always based on existing points, but that'd be complex-expressed
• Since taking a sequence of operations also "can represent any closed form number exactly and unambiguously", I assume it be a subset of +-*/sqrt