15
\$\begingroup\$

This is the exact same question I asked earlier, but without the annoying Cyrillic factor which many found superfluous. I hope this is a better puzzle!


The quaint hamlet of North Codetown in the Scottish far north has a problem: their population is low (below 52), and no new people have arrived for years. Moreover, after centuries of near-isolation in their secluded valley without much economic opportunity, just about everybody is related to each other.

Mayor Montgomery has a solution that should keep the morale high: organise a wedding. However, the question is, are there two bachelors in the town that aren't at least cousins of each other?

The mayor fired up his state-of-the-art Microsoft Bob computer to consult the genealogy charts. They had just been updated to the brand-new ASCII format, and look like this:

b┬K
 l

And this:

 A┬d
 O┴p┬Z 
    q   

And this:

  e┬N
L┬m┴p─┬F
B┴y┬A z┬Y
   f   E

And even this:

 i┬────────N
m┬E    
 │     Z
 │
 │
 z

Here's how it works. Each person is a letter from the Latin alphabet. Males are capital letters (any of ABCDEFGHIJKLMNOPQRSTUVWXYZ), females are lowercase letters (any of abcdefghijklmnopqrstuvwxyz).

A '┬' between two people means they are married. Right below that is either another person - their child - or a '┴', meaning that this couple has two children; located to the left and right of the symbol.

Moreover, to the right and left of '┬' and '┴' there can be any number of '─' characters, to extend the lines, as it were. Similarly, there can be any number of '│' characters above a '┴' or below a '┬'.

Lastly, a character without any defined symbol above them is considered a new arrival to the village, and by definition unrelated to anybody.

Also be aware that this is a very conservative village. Nobody marries more than once, and every marriage is heterosexual. Furthermore, assume everybody in the graph is alive, and no two people share the same name: e.g., the same character never occurs more than once (except in comments).

The two bachelors should be of the opposite gender, and they should not be first cousins or any more closely related. First cousins once removed is okay. In other words: they should not share a parent, or a grandparent, or have one's grandparent be another's parent.

Challenge

Make the shortest possible program (by byte count) with as input either a string (containing newline characters), or a string array, or a rectangular two-dimensional string or char array (no higher or wider than 100 characters), containing the family tree of the town. Assume the input is a valid family tree, consisting of nothing but ASCII printable characters and the mentioned line/forking characters. Ignore any character not given an explicit function in the above description.

Return a boolean value of true or false (or a bit/int of 1 or 0, or any consistent truthy/falsey value used by the language of your choice) to indicate whether there can be a wedding given the family tree.

Examples

1.

b┬K   
 i    

FALSE (there's only one bachelor)

2.

   A┬d    
 i┬O┴p┬Z  
  z   F   

FALSE (z and F are cousins)

3.

  e┬N     
L┬m┴p─┬F  
B┴y┬A W┬y 
   E   T  

FALSE (B, E and T are all male)

4.

  e┬N     
L┬m┴p─┬F  
q┴A┬y w┬R 
   U   E  

TRUE (q and E can marry)

5.

             i┬────────N  
            m┬E           
             │     w      
             │            
             │            
             W            

TRUE (w is not related to anybody)

6.

           d┬F                                
 a┬────────N┴─e┬E                             
  │            │                              
  │            w                              
  │                                           
  │                                           
  V                                           

FALSE (V and w are cousins)

7.

Ww

TRUE (W and w are unrelated)

8.

fw

FALSE (f and w are of the same gender)

9.

    e┬N     
  L┬m┴p─┬F  
n┬B┴y┬A w┬Y 
 C   E   i  

TRUE (i and E, and also i and C)

10.

 A┬d      f┬H   
 m┴P┬z     i┬Y  
    F       u   

TRUE (F and u)

NOTE: You are free to substitute the control characters with ASCII characters if it makes your program simpler. In that case switch out │ with | (vertical bar), ─ with - (hyphen), ┬ with + and ┴ with =.

Example:

           d+F                                
 a+--------N=-e+E                             
  |            |                              
  |            w                              
  |                                           
  |                                           
  V                                           
\$\endgroup\$
  • 3
    \$\begingroup\$ this person smells bad those look like a bunch of unrelated persons. Maybe make the comments Cyrillic, now that the persons are latin? x) \$\endgroup\$ – Grimmy Nov 18 at 13:27
  • 2
    \$\begingroup\$ I'd recommend to remove comments entirely to simplify the challenge some more. \$\endgroup\$ – Arnauld Nov 18 at 13:37
  • 3
    \$\begingroup\$ if cyrillic is "annoying", aren't graphics drawing characters so too? \$\endgroup\$ – ngn Nov 18 at 14:03
  • 3
    \$\begingroup\$ You only seem to have 4 control characters, , , and . You could make this entirely ASCII by either converting the two T's to +, (or simply allow any two non-alphabetical chars to be used determined by the submitters if you want to keep them as two separate symbols), |, and -. \$\endgroup\$ – Veskah Nov 18 at 14:21
  • 3
    \$\begingroup\$ @Veskah Okay. I think the latter is a solution that works best while keeping the original challenge intact. + for ┬ and = for ┴ should work. \$\endgroup\$ – KeizerHarm Nov 18 at 14:29
4
\$\begingroup\$

Jelly, 155 153 bytes

Ø.UAƭN,Ɗ⁺+Ṫ¥+œị⁾+|yⱮ$ɼ=⁾|=⁼Ø.Ɗɗ¡ƬṪ¥ƒ⁸’1¦⁺œị®⁼”|ƊпṖṪ+2¦œị®⁻1Ɗ¡ƬṪ¥ⱮØ+$“”¹?
o@e¥€€ØẠ“-=“==”;U¤œṣjƭƒ$€ƬṪ©=1ŒṪ+2¦œị®ɗⱮØ+f⁾-+ƊÐḟWÇ€Ẏ$Ƭḣ3ẎƲ€Œcf/ÐḟḢ€€ȧœị¥>”ZIFẸ

Try it online!

Minor modification of my Cyrillic version.

A monadic link that takes a list of Jelly strings and returns 1 for true and 0 for false. I’m sure this could be golfed more. Full explanation to follow.

\$\endgroup\$
12
\$\begingroup\$

Python 2, 399 393 390 388 385 bytes

def f(s):
 V=S(''.join(s))-S(' |+-^');P={v:[]for v in V}
 for j,r in E(s):
	for i,c in E(r):
	 if'+'==c:
		p,q=a=h(r,i);A=a+P[p][:2]+P[q][:2];V-=S(a);v=j;b='|'
		while'z'<b:v+=1;b=s[v][i]
		if'^'==b:w,x=h(s[v],i);P[w]=P[x]=A
		else:P[b]=A
 return 1-all((b>'Z')==(c>'Z')or S(P[b])&S(P[c])for b in V for c in V)
h=lambda r,i:[x.strip('-')[0]for x in r[i-1::-1],r[i+1:]]
E=enumerate;S=set

Try it online!

2 bytes thx to Jitse; 3 bytes thanks to isaacg.

Jeez! I think I could golf this a bit more; but at least I got it under 400 bytes :).

The input s is a list of strings. The encoding is A-Z for males, a-z for females, + to indicate a marriage, ^ for when a marriage produces 2 children (instead of =, 'cause I liked the look better :) ). Then - for horizontal extensions, | for vertical extensions.

Output is 1 for truthy, 0 for falsey.

V is the set of all villagers, initially; then as we scan, we will remove from V those who are already married. So at the end, V will be the set of un-mated villagers.

P is a dictionary with keys for all villagers v. P[v] will be the list of those parents of v, followed those grandparents of v, who are also villagers. Note that then P[v][:2] are the parents of v (assuming they are villagers).

h is a helper function to skip over any horizontal extensions (runs of -). Useful both for extracting a pair of parent villagers as well as dual children.

\$\endgroup\$
  • \$\begingroup\$ Very nice answer! You can save 2 more bytes by renaming set. \$\endgroup\$ – Jitse Nov 19 at 9:08
  • \$\begingroup\$ I've not looked too closely, but you could also almost certainly save a whole bunch of bytes by only indenting each of your blocks by one space. Sure, it makes your code unreadable, but we don't care about readability here. \$\endgroup\$ – ymbirtt Nov 19 at 10:02
  • \$\begingroup\$ @ymbirtt :In python2 (soon to be dead!) both spaces and tab characters are semantic white space, with space taking precedence. So I think you are mistaking those tab characters for 8 spaces. \$\endgroup\$ – Chas Brown Nov 19 at 10:21
  • \$\begingroup\$ @ChasBrown I am indeed! Sorry about the mixup \$\endgroup\$ – ymbirtt Nov 19 at 10:22
  • \$\begingroup\$ You can save 3 bytes by prepending a= to the line starting p,q, then replacing [p,q] with a, and replacing {p,q} with S(a). \$\endgroup\$ – isaacg Nov 19 at 19:30

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.