4
\$\begingroup\$

Introduction

Don't worry - no knowledge in mathematics is needed. It is possible to just skip the motivation part, but I think it is nice if a puzzle has a background story. Since the title contains the number I there will be more puzzles of this kind, if you like them. Feedback is highly appreciated. I hope you have fun with this puzzle! :)

Sandbox-Answer


Motivation

Many processes in the real life can be modelled with differential equations. A differential equation is an equation contain some differential expression, e.g.

x'(t) = λx(t)

This is a ordinary (= 1D) differential equation (ODE). And the solution to this is simply x(t) = x₀e^{λt} for any x₀∈ℝ. This ODE can be used as model for population growth (rabbits multiplying exponentially) or radiation decay. In both cases x̧₀ is the initial population / initial amount of material.

Now not everything in the world of physics can be modelled with ODEs. Since we live in a multidimensional world there should be differential equations with more than just one component, right?
These equations are named partial differential equations (PDE).

For example flow fields can (in some cases) be modelled using the Stokes Equation:

-Δv + ∇p = f in Ω
     ∇∘v = 0 in Ω

where v is the velocity and p is the pressure of the flow. And Ω⊂ℝ² is just the geometry on which the equation is solved - e.g. a tube.

Now if you want to solve these equations there is a method called Finite Element Method. And this method requires a grid of your geometry. In most cases these grids contain quadrilaterals or triangles.

For this code-golf we will use a very simple grid:

(0,1)                     (1,1)
  x-----x-----x-----x-----x
  |     |     |     |     |
  |  1  |  2  |  3  |  4  |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |  5  |  6  |  7  |  8  |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |  9  | 10  | 11  | 12  |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  | 13  | 14  | 15  | 16  |
  |     |     |     |     |
  x-----x-----x-----x-----x
(0,0)                     (1,0)

This 2D-grid consists of 5x5 points in (2D) unit cube [0,1]×[0,1]⊂ℝ². Therefore we have 16 cells. The four Cartesian coordinates and the numbers in the cells are not part of the grid. They are just to explain the Input/Output.

There is a connection between the grid-size and the accuracy of the solution - the finer the grid the higher the accuracy. (Actually that is not always true.) But a finer grid also has a draw-back: The finer the grid the higher the computation cost (RAM and CPU). So you only want to refine your grid at some locations. This idea is called adaptive refinement and is usually based on the behaviour of the solution - e.g. thinking about the flow problem above: refine that part of the grid, where the solution is turbulent, don't refine if the solution is boring.

Task

The task is to implement this adaptive refinement in a general way. Since we don't solve any PDE in this code-golf the criteria to refine grid cells is based on a circle disk. This circle disk is simply defined by the midpoint p=[p0,p1]∈[0,1]² and the radius r ∈ [0,1].

Every cell intersecting with that disk (including boundaries - see Example 1) will be refined.

The output is the 5x5 grid above with the refined cells.

Asked Questions

What is the purpose of 'x'?

'x' represents nodes/vertices, '-' and '|' edges.

Refinement of a cell means, that you split one cell into 4:

  x-----x       x--x--x
  |     |       |  |  |
  |     |   >   x--x--x
  |     |       |  |  |
  x-----x       x--x--x

Examples

Input: p=[0,0] r=0.5
Output:
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x--x--x-----x-----x-----x
  |  |  |     |     |     |
  x--x--x     |     |     |
  |  |  |     |     |     |
  x--x--x--x--x-----x-----x
  |  |  |  |  |     |     |
  x--x--x--x--x     |     |
  |  |  |  |  |     |     |
  x--x--x--x--x--x--x-----x
  |  |  |  |  |  |  |     |
  x--x--x--x--x--x--x     |
  |  |  |  |  |  |  |     |
  x--x--x--x--x--x--x-----x

The midpoint is located in (0,0) with radius 0.5.

Cell 13: Completely inside the cell.
Cell 9 : Intersects, since lower left corner has coords (0,0.25).  
Cell 14: Intersects, since lower left corner has coords (0.25,0). 
Cell 5 : Intersects, since lower left corner has the coordinates (0, 0.5). 
Cell 15: Intersects, since lower left corner has the coordinates (0.5, 0). 
Cell 10: Intersects, since lower left corner has the coordinates (0.25, 0.25).
The distance from (0,0) to that corner is √(0.25²+0.25²) < 0.36 < 0.5.

Cell 11:  Does not intersect, since the closest point is the lower left
corner with coordinate (0.5,0.25), so the distance is 
√(0.5² + 0.25²) > √(0.5²) = 0.5


Input: p=[0.5,0.5] r=0.1
Output:
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x--x--x--x--x-----x
  |     |  |  |  |  |     |
  |     x--x--|--x--x     |
  |     |  |  |  |  |     |
  x-----x--x--x--x--x-----x
  |     |  |  |  |  |     |
  |     x--x--x--x--x     |
  |     |  |  |  |  |     |
  x-----x--x--x--x--x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x

The midpoint is located in (0.5,0.5) with radius 0.1. 
Therefore the circle is completely inside the union of cells 6,7,10 and 11.
It does not touch any 'outer' boundaries of these four cells.
So the only refined cells are these four. 


Input: p=[0.35,0.9] r=0.05
Output:
  x-----x--x--x-----x-----x
  |     |  |  |     |     |
  |     x--x--x     |     |
  |     |  |  |     |     |
  x-----x--x--x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x

Cell 2: Intersecting with the circle.
Cell 1: Not refined, since the right edge has x-coordinate 0.25 < 0.35-0.05 = 0.3.
Cell 3: Not refined, since the left edge has x-coordinate 0.5 > 0.35+0.05 = 0.4.
Cell 6: Not refined, since the top edge has y-coordinate 0.75 < 0.9 - 0.05 = 0.85. 

Rules

Since this is my first puzzle / golf help is appreciated.

  • : Smallest byte size wins.
  • Trailing / Leading whitespaces are allowed.
  • The Cartesian coordinates are not part of the grid, and should not be seen in the output.
  • Only allowed chars are '-', '|', 'x' and ' '
  • Input: All three numbers will be floats. It does not matter if your input is a tuple (p0,p1) and a number r, or three numbers, or one array - just be reasonable.
\$\endgroup\$
  • 2
    \$\begingroup\$ What does the circle have to do with the adaptivity? Do we always use a 5x5 grid? where do we use x-es and where don't we use them? Also I think the whole motivation part could be omitted, as it does not help understand the the challenge itself. \$\endgroup\$ – flawr Jul 10 '17 at 15:37
  • \$\begingroup\$ @flawr 1) "The task is to implement this adaptive refinement in a general way". With other words to implement the general concept of refining this grid in a specific region. For this golf it is a simple circle. Usually in numerics this region would depend on the solution. // 2) Yes only this grid, I will edit the question about what each char stands for. 3) Yes, it could be omitted. But I don't like that, in the same way I wouldn't have read Lord of the Rings on only one page. \$\endgroup\$ – P. Siehr Jul 10 '17 at 16:48
  • \$\begingroup\$ @flawr : I am really sorry. There has been a mistake in the examples, it is corrected and should be clear now. \$\endgroup\$ – P. Siehr Jul 10 '17 at 17:21
  • \$\begingroup\$ I think following needs clarification: What does "cell touching the circle" mean? Do one (or more?) corner points have to be within the circle? Or is it about the center? Or is it enough if one edge of a cell gets crossed? Please include the exact specs to that in the challenge. Then I think it should be good to go. \$\endgroup\$ – flawr Jul 10 '17 at 20:29
  • \$\begingroup\$ @flawr Changed "touching" to "intersecting". So if there is any common point of (cell + cell boundary) and (circle disk + circle) the cell will be refined. I added explanations to the output examples. Thanks for your remark. \$\endgroup\$ – P. Siehr Jul 10 '17 at 22:00
3
\$\begingroup\$

Charcoal, 107 105 106 bytes

F²«x⁵↷²x³↷»F³«C⁰±⁴C⁶¦⁰»F⁴«A⁻×⁴IθιεF⁴«A⁻×⁴Iηκ먪›⁺X⎇›ε¹⁻ε¹∧‹ε⁰ε²X⎇›δ¹⁻δ¹∧‹δ⁰δ²X×⁴I沫J⁺³×⁶ι⁻²×⁴κP|x|xP-x--x

Try it online! Link is to verbose version of code, not that it helps. Edit: Saved 2 bytes by handling the reversed sense of the Y-axis in a different way, but added a byte to handle a clarification in the question. Explanation:

F²«x⁵↷²x³↷»

Prints a cell. It does this by printing an x, then printing 5 (which expands to ----- because the default cursor direction is right), then it rotates downwards, prints another x, prints 3 (which now expands to three |s downwards), then rotates left. Doing all that twice completes the cell.

F³«C⁰±⁴C⁶¦⁰»

There are four cells horizontally and vertically, so the cell needs to be copied horizontally and vertically three times. The vertical copy is done upwards to simplify the calculation below.

F⁴«A⁻×⁴IθιεF⁴«A⁻×⁴Iηκδ

The 16 cells are now looped over using a four by four nested loop. The coordinates of the midpoint are multiplied by 4, scaling them from 0 to 4, which corresponds to our loop indices which are subtracted, so the resulting variables are now relative to the cell's bottom left corner.

¿¬›⁺X⎇›ε¹⁻ε¹∧‹ε⁰ε²X⎇›δ¹⁻δ¹∧‹δ⁰δ²X×⁴I沫

The variables are now compared to the range 0 to 1 that represents the relative quadrupled cell coordinates. If they lie outside this range it means that the midpoint lies outside the cell, so the distance to the range is squared and the sum of the squares compared to the square of the quadrupled radius. If it is not greater, then the cell needs to be refined.

J⁺³×⁶ι⁻²×⁴κP|x|xP-x--x

The cursor is moved to the centre of the cell to be refined. The string x|x is printed vertically (both up and down), while the string x--x is printed horizontally (both left and right). (The middle xs overlap.)

\$\endgroup\$
  • \$\begingroup\$ Although, there's not a huge difference, You are drawing '+' instead of 'x' at the inner vertices. \$\endgroup\$ – officialaimm Jul 10 '17 at 16:26
  • \$\begingroup\$ I am sorry, but I made a mistake in the examples, see the "Asked Questions" part :/ \$\endgroup\$ – P. Siehr Jul 10 '17 at 17:27
  • \$\begingroup\$ @officialaimm What a silly oversight. Fortunately the fix is just to change the + at the end to x. \$\endgroup\$ – Neil Jul 10 '17 at 18:35
  • \$\begingroup\$ @P.Siehr I have updated the code and it should now match the updated examples. \$\endgroup\$ – Neil Jul 10 '17 at 18:46
  • \$\begingroup\$ Great, but sadly the question is still on hold. I think everything is clear now. \$\endgroup\$ – P. Siehr Jul 10 '17 at 20:12

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.