16
\$\begingroup\$

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 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 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:

A graph showing the lines above, with important points labeled A through H

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)"]
\$\endgroup\$
10
  • \$\begingroup\$ Sandbox \$\endgroup\$ Jan 2 at 10:11
  • \$\begingroup\$ Can I specify some order in which intersections are added, and then use the indices of the points? Can I define two objects in each step and append their intersections, without all intersections being added by default? \$\endgroup\$ Jan 2 at 10:43
  • 1
    \$\begingroup\$ Can I assume the only integer in the input is 1, and other integers have to be represented by repeated addition? \$\endgroup\$ Jan 2 at 10:45
  • \$\begingroup\$ @CommandMaster That can "represent any closed form number exactly and unambiguously", go ahead. As for the order, I'm going to say no: the output has to explicitly list the points used in each construction. And, I'm not sure I understand what you mean by defining two objects in each step and their intersections? \$\endgroup\$ Jan 2 at 16:18
  • \$\begingroup\$ The second question was only relevant had the answer to first one has been yes - I asked if, when using the index, I can assume only intersections I specifically create are created. It isn't relevant if you have the explicitly list the points, because then obviously you'd just want all intersections. \$\endgroup\$ Jan 2 at 16:38

2 Answers 2

11
\$\begingroup\$

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:

Animation for (sqrt(2), 3)

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)
\$\endgroup\$
2
  • \$\begingroup\$ (1/2) It's not pretty but you can cut down on some of the repeated code using exec: ATO! Maybe \$\endgroup\$
    – Dingus
    Jan 9 at 23:15
  • \$\begingroup\$ (2/2) you could take it further and eliminate another def and return by embedding the first f-string within the second? (I couldn't manage to, don't really speak Python.) \$\endgroup\$
    – Dingus
    Jan 9 at 23:16
7
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Could you explain your input and output formats please? \$\endgroup\$ Jan 3 at 6:38
  • \$\begingroup\$ -4 by replacing P with a function that pads with zeros. \$\endgroup\$
    – emanresu A
    Jan 7 at 10:08
  • \$\begingroup\$ In fact, -24 by moving the circle/square bit to the end. \$\endgroup\$
    – emanresu A
    Jan 7 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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