2
\$\begingroup\$

Dr. Trump is the head psychiatrist at a mental hospital, which is populated by murdering psychopaths. If 2 psychopaths are left together, they will end up brutally injuring or even killing each other, so Dr. Trump needs to build walls to separate these psychopaths, but owing to the limited amount of funds he has left, he has to minimise the number of walls he builds. Walls of a room can either be horizontal or vertical in nature and of any length.

Help Dr. Trump minimise the number of walls he builds to separate all the psychopaths in a 2*n psych ward.

Also, do keep in mind that the shortest code wins.

Input

The first 2 lines contains the position of psychopaths (denoted by '#') and empty spaces (denoted by '-').

Output

An integer which is equal to the minimum number of walls to build to separate all the psychopaths from each other.

Input Constraints

1 <= n <= 1000000

Sample Test Cases

Test Case 1

Sample Input

##########
##########

Sample Output

10

Test Case 2

Sample Input

#-#-#
-#-#-

Sample Output

3

Test Case 3

Sample Input

#-----
------

Sample Output

0
\$\endgroup\$
11
  • \$\begingroup\$ do you mean minimise the number of walls? \$\endgroup\$ Jun 1, 2017 at 0:39
  • 1
    \$\begingroup\$ The first part says minimise rooms, so you might want to edit that. btw maybe put spaces in Dr. Ake. \$\endgroup\$ Jun 1, 2017 at 0:42
  • 4
    \$\begingroup\$ I'd like this challenge a lot better if the doctor had a different last name. There's absolutely no need to bring politics into it. \$\endgroup\$
    – Dennis
    Jun 1, 2017 at 3:14
  • 1
    \$\begingroup\$ This is borderline "Unclear what you're asking" because there are assumptions which aren't spelt out in the question. CalculatorFeline's comment illustrates one of them: there's no explanation of where the walls can be built. Another would be that the walls can cross each other for free (which would make much more sense if the question were about drawing lines rather than building walls: it already stretches common sense that the cost of a wall is independent of its length, and I can't find any rationalisation of that which allows + not to count as three walls). \$\endgroup\$ Jun 1, 2017 at 6:23
  • 1
    \$\begingroup\$ @Dennis- Here's the deal. Everything need not be what it seems. Just because it says Dr. Trump need not imply that I am referring to the President of the United States. At this day and age, If I use any name, there will be at least one person in the world that will get offended by it, that need not mean that we stop our daily lives to think of ways to appease other people, because, quite frankly, I don't see the point of judging a programming challenge by the names attached to it. \$\endgroup\$ Jun 1, 2017 at 9:26

1 Answer 1

6
\$\begingroup\$

Python, 270 228 166 156 bytes

a=input();b=input();m=lambda s:[c=="#"for c in s];f=m(a);g=m(b);s=p=0
for i in range(len(a)):q=2*f[i]+g[i];r=p&q;s+=r!=0;p=r or p|q
print(s+(any(f)&any(g)))

PEP8-ified:

a = input()
b = input()
m = lambda s: [c == "#"for c in s]
f = m(a)
g = m(b)
s = p = 0
for i in range(len(a)):
    q = 2*f[i]+g[i]
    r = p & q
    s += r != 0
    p = r or p | q
print(s+(any(f) & any(g)))

Try it online!

This is my first time here, be gentle please ;)

There is always a horizontal wall in the middle, except when prisoners are only on one side -- the addition in print() takes this into account. Strategy here is to break horizontal bar into sections such that there is no more than one prisoner on each side, for each section.

The for loop uses an int, p, to hold two bit flags, indicating whether the current top/bottom section already contains a psychopath. We & this with the flags from the new gridsquare to check whether we are going to overflow, and need to place a wall; if so, we increment s. We also use p&q to decide how to update the state: if we overflow, we hold onto just the overflowed prisoner (p&q). Otherwise, we | the new prisoners onto our current prisoner state. Using and and or as a ternary operator again here.

There are some helper functions at the top, as well as throwaway variable names for values used more than once.

Edit: It seems like this got simpler as it got shorter. It used to use all kinds of wacky behaviour

\$\endgroup\$
6
  • \$\begingroup\$ Nice answer, welcome to the site! I think you could do a,b=input() and have the input given with a comma between. I'm not sure if that's an allowed format though. \$\endgroup\$
    – DJMcMayhem
    Jun 1, 2017 at 4:54
  • \$\begingroup\$ Thank you Wheat Wizard! Those are all useful. I had the spaces there because my editor didn't highlight the and when it was next to the number, guess it was lexing it wrong. \$\endgroup\$
    – Luke Wren
    Jun 1, 2017 at 5:10
  • \$\begingroup\$ Thats a common parser problem, SE does it with its syntax highlighting as well. Here is a version with my suggestions added I noticed that you could also do s=p=0 to save some bytes. \$\endgroup\$
    – Wheat Wizard
    Jun 1, 2017 at 5:17
  • 1
    \$\begingroup\$ A bit more convoluted but the second r!=0 can be replaced with just r. If r is false it will short the and and return zero either way, if r is non-zero it will return r or(p|q) either way. \$\endgroup\$
    – Wheat Wizard
    Jun 1, 2017 at 5:58
  • \$\begingroup\$ I get the logic, but can you show the running code here ? \$\endgroup\$ Jun 1, 2017 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.