2 Replies - 1334 Views - Last Post: 20 November 2018 - 09:14 AM Rate Topic: -----

#1 DK3250   User is online

  • Pythonian
  • member icon

Reputation: 489
  • View blog
  • Posts: 1,533
  • Joined: 27-December 13

Christmas Challenge no. 2: Find Close Triplets in 6-Dimensional Space

Post icon  Posted 17 November 2018 - 11:50 PM

Find Close Triplets in 6-Dimensional Space

Suppose you manufacture an item with two properties, we call them ‘x’ and ‘y’.
The manufacturing process is a little unstable, so both properties vary randomly in the interval 0 to 1. All items (in this interval) are good; however, we use the items in triplets.
Within a triplet it is important that the properties are close to one another.
This corresponds to placing all items in a scatter plot (2D-space) and finding triplets within a circle of a given diameter.

Now for the challenge we imagine items with 6 properties, all random in the 0 to 1 interval.
Suppose you have 100 such items. With a distance of 0.5 in 6D space as the maximum distance between any two items in a triplet; write a program that find the maximum number of triplets.

I have made such a program. I cannot, however, prove that the triplets found is the maximum number. In theory, another combination of items may lead to even more triplets.

To be able to compare results, I suggest this python backbone code:
import random
random.seed('seed')


class Item():
    def __init__(self):
        self.data = [random.random() for _ in range(6)]


items = []
for _ in range(100):
    items.append(Item())


‘items’ can also be a dictionary, - up to you.


The competition rules are the same as for the Pi challenge.
Most importantly: It's a friendly competition.

Next week I'll issue a third challenge.
It will be a very different one where all can participate no matter the programming experience level.

Is This A Good Question/Topic? 1
  • +

Replies To: Christmas Challenge no. 2: Find Close Triplets in 6-Dimensional Space

#2 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14581
  • View blog
  • Posts: 58,445
  • Joined: 12-June 08

Re: Christmas Challenge no. 2: Find Close Triplets in 6-Dimensional Space

Posted 20 November 2018 - 08:35 AM

Refresh me again.. it's early... what's a triplet in this scenario?

I get an object with properties x and y.
Values of x and y are 0 to 1 float/decimal.
There's a collection of objects max 100.

Is this looking to find the number of grouped-three objects with in .5 of each other?
Was This Post Helpful? 0
  • +
  • -

#3 DK3250   User is online

  • Pythonian
  • member icon

Reputation: 489
  • View blog
  • Posts: 1,533
  • Joined: 27-December 13

Re: Christmas Challenge no. 2: Find Close Triplets in 6-Dimensional Space

Posted 20 November 2018 - 09:14 AM

Sorry for not being clear.

A triplet is a group of three items (or products as I name them in the text).

In a 2D scatterplot you can imagine placing a small circle such that it covers (minimum) three items.
You take those three into first triplet and continue with the rest.
The challenge is to get as many triplets as possible.

If we move to 3D, it is easy to visualize how items that are close in 2D can become separated in 3D.
The same happens as we add more properties and move to higher dimensions.

Also space grows, in 2D the length of the diagonal is sqrt(2), in 3D it is sqrt(3) and in 6D it is sqrt(6).

We now have 6 properties.
The maximum distance in 6D space for any two items in a triplet is 0.5 'unit length'.
How do we find the maximum number of triplets?

This challenge builds on a real-life situation.
I once worked with building accelerometers (for measurements of vibrations). Inside those are three piezoelectrical crystals, they produce a small voltage upon pressure. The important thing was that those three crystals had to have similar properties. The actual voltage/N was not so important, but all three should give (almost) the same value.
Each crystal actually had 6 properties (voltage output upon pressure in x, y and z direction and three more). The job was to find as many close triplets as possible in batches of around 100 crystals.
Now, this job is turned into a Christmas Challenge...
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1