artificial intelligence, mathematics

Intermezzo Problem Solution(s)

Below there is a problem I invented a month or so ago. I published a link on Lesswrong and the solving began.

The first solution was 4 hexagons by LW user 9eB1. He later improved it by, quote:

 right triangle that’s half the area of the equilateral triangle. You can fit 4 in the square and two in the triangle, and the score is point six

Oscar Cunningham came with this, quote:

why not get a really good score by taking a completely gigantic shape that doesn’t cover anything

This is a clever but also somehow trivial solution, we have agreed.

So he came with thi:

OC

The thin red line is the uncovered area of the square, while the triangle can be tiled perfectly. The score is 0.57756.

Then I made I little promise, which has been broken already, that I will publish my solution on Monday, which is about two weeks ago by now.

The whole time, I was digitally evolving solutions on a computer. Just as I was not very far from Oscar’s solution he stroke again, with a much better one. More than twice as good as the previous one. This time he perfectly tiled the square and left some triangle uncovered. The score is 0.249..

This morning I almost decided to quit, when I saw something unusual on the screen. At first, I thought something wasn’t right. Then I realized what the damn computer is telling me.

The computer was evolving the following picture (visually rephrased by me for clearness).

house

The perfect score 0, albeit a bit trivial solution perhaps. Of course it is not necessary that you join the triangle and the square together. You can split the covering shape. Which computer did.

EDIT: 

The problem is with the Oscar’s last solution. When I put his algorithm into the machine, it showed an error in the form of a negative result.

Well, the algorithm is okay, but 1/7 and 1/4 can’t be. But 1/7 and 1/12 can be. But the result isn’t that good.

Advertisements
Standard

6 thoughts on “Intermezzo Problem Solution(s)

  1. Oscar Cunningham says:

    An interesting solution! I think that solutions of this kind only exist when the triangle and the square lie in the plane in a particular way (Although there’s always a super trival one piece solution). If the square was centred at (0,0) and the triangle at (100,50) then we would have no hope, because as soon as we did any reflection or rotation we would find that the two components of our tile would no longer be aligned to fit in both the square and the triangle.

    • I do require it from now on.

      You see, I’ve forget to require that the shape should cover at least something. Hence the first “trivial solution” Oscar gave. Which is arbitrarily good, depends only on how huge shape one choses.

      Some humans and some algorithms are very good at “going out of the box”, whenever possible. I love that, despite I have some adjustments to make afterward.

      • Oscar Cunningham says:

        I don’t think you should have to make the covering shape connected. Just make sure it only has one component in each tile!

  2. The current situation is as follows. The best solution is basically an algorithm, which first creates 1/4 by 1/7 by sqrt(1/4+1/49) triangle, then tiles perfectly the unit square with 56 of those triangles and then tiles the unit triangle with additional 24 said triangles. The current algorithm flips the covering shape but doesn’t do any rotation. It is like 1000 lines computer code. Some small area remains uncovered.

    The question is, how this algorithm can be improved, if that is possible at all. I don’t think, that some “non-algorithmic covering” is better.

    How to improve this algorithm, to have some even nicer end result, that is the problem. Nicer algorithm in the sense, that the uncovered area is relatively even smaller.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s