Does anyone want to solve an algorithmic problem for me?

Skip to first unread message

Ram Rachum

Jul 29, 2021, 12:54:19 PM7/29/21
to pyweb-il
Hi guys,

For my research, I'm designing a concurrency framework that I call Sharknado. I spent a month working on the design (document I wrote for myself, hard to read), and I spent the last 10 days working on the implementation. It's still work-in-progress.

There is one small part of the design which is an algorithmic problem that I don't know how to solve efficiently. I wrote a naive solution. Would anyone here be interested in writing an efficient solution? Or at least describing it? 

In two sentences: You're given a union of hyperrectangles of natural numbers in a given dimension. You need to find a canonical representation of it that lets you efficiently do actions such as addition, subtraction, union, intersection and containment.

This object I'm talking about is the IntCrowd class. There's some explanation about it under the IntCrowd section in the design doc. Here's the inefficient implementation and tests that I wrote.

Here are a few examples in 3-dimensional space:

# This contains just one point (1, 2, 3):
IntCrowd(3, ((1, 2, 3),))

# This contains three points: (1, 2, 3), (1, 2, 4),  (1, 2, 5):
IntCrowd(3, ((1, 2, (3, 6)),)) 

# This contains four points: (1, 1, 5), (1, 1, 6), (1, 2, 5), (1, 2, 6):
IntCrowd(3, ((1, (1, 3), (5, 7)),)) 

Is anyone interested in finding an efficient implementation?

Reply all
Reply to author
0 new messages