6
\$\begingroup\$

It's really frustrating when I'm working and I have a ton of windows open that are completely or partially hidden behind other windows. To make things worse, I'm still using two 1024x768 monitors.

Your task is to take a list of coordinates that designate the area, in pixels, on a screen, that a list of windows occupy and output a truthy value if, for a 2 monitor set-up with 1024x768 resolution, all the following conditions are met:

  • None of the windows would overlap,
  • None of the windows would be partly off screen
  • None of the windows would straddle a boundary between the two monitors (so the order in which you visualize monitors 1 and 2 is irrelevant)

And a falsey value if any of these criteria are not met.

You may assume that all windows are rectangular, and that no coordinates are negative in the input, which is in a file, in stdin, or in a list of tuples, is in the following format:

monitor-number left-x bottom-y right-x top-y
monitor-number left-x bottom-y right-x top-y
monitor-number left-x bottom-y right-x top-y

Where each line contains the ID of the monitor (which can either be in [1, 2] or [0, 1] depending on which is easier for your language), and the dimensions of a window.

For example, the following input will result in a truthy output because none of the windows overlap:

1 10 10 100 200
1 210 300 600 600
2 10 10 100 200

The following input will result in a falsey value because lines 1 and 3 result in an overlap:

1 10 10 50 50
2 5 5 600 200
1 20 20 80 80

The following input will result in a falsey value because it would partially off-screen on one of the monitors:

1 1000 400 1400 300 

This is so the shortest solution wins.

\$\endgroup\$
  • \$\begingroup\$ Can I also take input as a list of tuples which is passed to my function? \$\endgroup\$ – ThreeFx Jun 18 '17 at 20:39
  • \$\begingroup\$ @ThreeFx sure, let me update my post. \$\endgroup\$ – Govind Parmar Jun 18 '17 at 20:39
  • \$\begingroup\$ I suppose we are assuming that the monitor with minimum ID has its right edge aligned exactly with the left edge of the other? (My 1 and 2 are in fact the other way around :)) \$\endgroup\$ – Jonathan Allan Jun 18 '17 at 21:38
  • \$\begingroup\$ @JonathanAllan Sure, but either way, the criteria for truthy output is that it can't partially be on either monitor \$\endgroup\$ – Govind Parmar Jun 18 '17 at 21:39
  • \$\begingroup\$ wait - if they straddle that should yield a falsey value, even if they are not off screen? \$\endgroup\$ – Jonathan Allan Jun 18 '17 at 21:41
4
\$\begingroup\$

Jelly, 33 bytes

<⁽¡ð,769FẠ
Ḋs2Zr/€p/;€Ḣµ€ẎµQL⁼LȧÇ

A monadic link taking a list of lists of the window-data and returning 0 if any windows exceed their monitor's space or overlap, or 1 otherwise.

Uses 1-indexed monitor IDs; 1,1 to 1024,768 inclusive are considered on-screen.

Try it online! (Too slow for the first two test cases! Typical golf :))

How?

The reason this is so slow is because it creates all the pixels for all the windows, each with its monitor ID and checks for overlap using de-duplication (which is implemented using lists not sets). It also checks each pixel is on-screen rather than checking just the input corners. All in all very inefficient...

Test-case 1 succeeded (1) locally in only eleven minutes! Test-case 2 succeeded (0) in less.

<⁽¡ð,769FẠ - Link 1 check pixels are on-screen: list of lists, each being [x,y,ID]
 ⁽¡ð       - literal base-250 integer = 1025
    ,769   - pair with literal 769
<          - less than (vectorises) -> [[x<1025, y<769, ID],...]
        F  - flatten into a single list
         Ạ - all truthy?

Ḋs2Zr/€p/;€Ḣµ€ẎµQL⁼LȧÇ - Main link: list of lists, each being [ID,Lx,By,Rx,Ty]
            µ€         - for €ach window:
Ḋ                      -   dequeue -> [Lx,By,Rx,Ty]
 s2                    -   split into twos -> [[Lx,By],[Rx,Ty]]
   Z                   -   transpose -> [[Lx,Rx],[By,Ty]]
     /€                -   reduce €ach with:
    r                  -     inclusive range -> [[Lx,...,Rx],[By,...,Ty]]
        /              -   reduce with:
       p               -     Cartesian product -> all pixels, [[Lx,By],[Lx,By+1],...[Lx,Ty],[Lx+1,By],... ...[Rx,Ty]]
           Ḣ           -   head -> ID
         ;€            -   concatenate each pixel with the monitor ID
              Ẏ        - tighten -> one list of all window's [x,y,ID] values
               µ       - monadic chain separation, call that w
                Q      - deduplicate (unique [x,y,ID] values)
                 L     - length
                   L   - length of w
                  ⁼    - equal?
                     Ç - call last link (1) as a monad (all on-screen?)
                    ȧ  - logical and
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ That is... equal parts horrific and amazing. I love the solution of generating each pixel and testing, but it also makes me cringe inwardly. \$\endgroup\$ – Sebastian Lenartowicz Jun 18 '17 at 23:13
  • 1
    \$\begingroup\$ Yep, welcome to the golf course :p \$\endgroup\$ – Jonathan Allan Jun 18 '17 at 23:13
2
\$\begingroup\$

Haskell, 103 88 bytes

f l=[]==[a|z@(m,a,b,c,d)<-l,y@(n,e,f,g,h)<-l,y/=z&&m==n&&e<c&&(b<h||f<d)||1024<c||768<d]

Forgot the bounds checking initially.

Takes input as a list of 5-tuples representing the windows.

How does it work?

We pair all windows with each other and then look at all pairs (a, b) with a /= b. Since the relation is symmetric, we only have to check whether the right end of the first and left end of the second window overlap. If they do, then for them to overlap one's lower has to be higher than the other one's top or vice versa. Lastly, we do bounds checking.

If any of the conditions are true, the list will contain more than one element, so all there is left to do is to check whether the list is empty.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You use the variable name d twice, so it fails for example for f [(2,10,10,200,2000)]. Just rename the variables inside the 5-tuple y and adjust the conditions. \$\endgroup\$ – nimi Jun 18 '17 at 22:47
  • \$\begingroup\$ @nimi Whoops, how did I not see that? Thanks, it should be fixed now! \$\endgroup\$ – ThreeFx Jun 18 '17 at 22:49
  • \$\begingroup\$ Hmm, the first test case returns False: f [(1,10,10,100,200),(1,210,300,600,600),(2,10,10,100,200)]. \$\endgroup\$ – nimi Jun 18 '17 at 22:55
  • \$\begingroup\$ @nimi I'll fix that in the morning then, it's late here. If you want to correct it, feel free to! \$\endgroup\$ – ThreeFx Jun 18 '17 at 23:02
  • \$\begingroup\$ null is better style than []== and just as long (or short) \$\endgroup\$ – Bergi Jun 19 '17 at 3:19
1
\$\begingroup\$

JavaScript (ES6), 100 bytes

a=>!a.some(([m,l,b,r,t],i)=>l<0|b<0|r>1024|t>768|a.some(([n,k,c,s,u],j)=>i!=j&m==n&l<s&b<u&r>k&t>c))

Takes input as an array of arrays. Assumes window coordinates are monitor-relative. I could save 8 bytes by assuming windows never overlap to the left of the monitor but 100 is a nice round number ;-)

| improve this answer | |
\$\endgroup\$

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.