26
\$\begingroup\$

The quaint hamlet of Кодгольф in the Russian far east has a problem: their population is low (below 66), and no new people have arrived for years. Moreover, after centuries of near-isolation, just about everybody is related to each other.

Mayor Стекобмен 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 Боб computer to consult the genealogy charts. They had just been updated to the brand-new ASCII format, and look like this:

ы┬К
 ю

And this:

 А┬д
 О┴п┬Щ 
    Ф   

And this:

  з┬Й
Л┬м┴п─┬Ф
Ы┴я┬А ш┬Я
   З   Е

And even this:

 ю┬────────Й
м┬Е    
 │     ш
 │
 │
 Щ

Here's how it works. Each person is a letter from the Russian alphabet. Males are capital letters (any of АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ), females are lowercase letters (any of абвгдеёжзийклмнопрстуфхцчшщъыьэюя).

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 Cyrillic character never occurs more than once.

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 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. Ignore any character not given an explicit function in the above description.

It's fine to use an encoding other than Unicode for input/output purposes, e.g. KOI8-R as long as it's known and standardised by someone other than yourself. Scoring is done per this answer. If your language handles Cyrillic natively, it's an advantage!

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.

ы┬К   
 ю    

FALSE (there's only one bachelor)

2.

   А┬д    
 ю┬О┴п┬Щ  
  Щ   ф   

FALSE (Щ and ф are cousins)

3.

  з┬Й     
Л┬м┴п─┬Ф  
Ы┴я┬А ш┬Я 
   З   Е  

FALSE (З, Е and Ы are all male)

4.

  з┬Й     
Л┬м┴п─┬Ф  
ё┴А┬я ш┬Я 
   З   Е  

TRUE (ё and Е can marry)

5.

             ю┬────────Й  
            м┬Е           
             │     ш      
             │            
             │            
             Щ            

TRUE (ш is not related to anybody)

6.

           д┬Ф                                
 ю┬────────Й┴─ё┬З                             
  │            │                              
  │            ш <this person smells bad      
  │                                           
  │                                           
  Щ <this person betrayed the Party!          

FALSE (Щ and ш are cousins)

7.

Щ 1234567890 quick brown foxes jumped over the lazy dog ш

TRUE (Щ and ш are unrelated)

8.

    з┬Й     
  Л┬м┴п─┬Ф  
й┬Ы┴я┬А ш┬Я 
 Э   З   ю  

TRUE (ю and З, and also ю and Э)

9.

 А┬д      ф┬Ж   
 м┴п┬Щ     ю┬Я  
    Ф       ц   

TRUE (ц and Ф)

NOTE: Here is an ASCII version of roughly the same challenge.

\$\endgroup\$
20
  • 2
    \$\begingroup\$ Hi KeizerHarm, welcome to the site! Thanks for the question, it looks fun. A question: For example 4, aren't ё and З barred from marriage due to the fact that ё is З's aunt? In other words, ё's parent Л is З's grandparent? Also, I take it that we are to assume that marriages are always heterosexual, and that divorce and remarrying of widows/widowers does not exist? Making those assumptions is fine by me, I just wanted to be sure. \$\endgroup\$
    – isaacg
    Nov 15, 2019 at 17:38
  • 1
    \$\begingroup\$ @isaacg Thanks. You're right about question 4; I missed that. I'll fix that right away, and then draw up another example with two possible marriages. And yes to all of those. I'll add that too. \$\endgroup\$
    – KeizerHarm
    Nov 15, 2019 at 17:39
  • 13
    \$\begingroup\$ I've read through this a couple of times but maybe I'm still missing something: I don't see what requiring the use of the Russian alphabet adds to this challenge. \$\endgroup\$
    – Shaggy
    Nov 15, 2019 at 23:41
  • 3
    \$\begingroup\$ @Shaggy Well, for one: were it in the Latin alphabet, to detect a person you could simply check a character against the range [a-zA-Z]. The Russian alphabet however is not on one continuous range, so either Ё&ё need to be treated separately or the entire string of allowed characters needs to be in there, and I wonder if you could even compress that. Plus this makes for a funnier story. \$\endgroup\$
    – KeizerHarm
    Nov 16, 2019 at 0:19
  • 11
    \$\begingroup\$ Welcome to CGCC! I like your idea, but I'll agree with Shaggy: the really interesting core of this challenge has to do with first decoding the input into a graph of familial relationships, and then making some deductions based on that graph. The Cyrillic requirement is just an annoying distraction from those tasks, especially in languages where unicode is a bit of a pain. Maybe as a separate challenge "Is this Cyrillic unicode letter a capital letter?" would be interesting to golf for some; but as it is, it really detracts from my interest in answering your question. Just sayin'! \$\endgroup\$
    – Chas Brown
    Nov 16, 2019 at 4:19

3 Answers 3

7
\$\begingroup\$

K (ngn/k), 230 203 200 196 bytes

{t:{x*\:x};n:#*x:4(+|0,)/x;p:&2!c:+/"╒ё╡Ё©ъъ"<\:a:,/x;|//(~h=\:h:4!c p)&t[~|/p=/:?,/2#'(p^p^)'g]&3<{&/'x+\:x}/(~=#p)*(#a;1)0|/t'?(+/'p=/:/:g:{?'x,/'x x}/(!#a)+(-e;e,:n;e;n*e:-1 1;())4^"┴┬─│"?a)^0}

the input and the k code must be encoded in koi8-r. test with (linux only):

git clone https://bitbucket.org/ngn/k
cd k/g
../k can-this-village-have-a-wedding.k

please make sure your editor handles koi8-r correctly. for instance, if using vim, you can type :e ++enc=koi8-r after opening the file or put set fencs=utf-8,koi8-r in your ~/.vimrc


k functions are written in { }, have an implicit argument x, and consist of ;-separated expressions.

the sequence of expressions is evaluated left-to-right but the code within each expression is right-to-left.

t:{x*\:x} helper function that creates a multiplication table (outer product) for a list x

x:4(+|0,)/x surrounds the input x with zeroes. literally: 4 times (4( )/) add zero(-es) on top (0,), reverse (|), and transpose (+).

n:#*x let n be the width of the input. literally: length (#) of the first (*)

a:,/x let a be the flattened input

c:+/"╒ё╡Ё©ъъ"<\:a for each character in a, count how many of "╒ё╡Ё©ъъ"are before it (in koi8-r). this will give odd numbers for russian letters and even for non-letters. also, the remainder mod 4 will indicate the sex - upper/lowercase.

p:&2!c take c mod 2 (2!) and make a list of the indices where (&) it's 1. "p" for "people".

the rest of the code will build three p×p matrices that represent conditions for marriage:

  • the couple must be >3 steps apart in the graph of relatives. a "step" is a relationship of parent-child or spouse or sibling.

    • 4^"┴┬─│"?a for each in a find its index among "┴┬─│" and fill in 4 if not found.

    • (-e;e,:n;e;n*e:-1 1;()) replace "┴" with (-1;1;-n), "┬" with (-1;1;n), "─" with (-1;1), "│" with (-n;n), and others with an empty list

    • (!#a)+ add 0 1 2.. thus creating lists of neighbours

    • g:{?'x,/'x x}/ transitive closure - extend (,/) each (') neighbour list (x) with the neighbour lists of its neighbours (x x) and unique it (?), until convergence ({ }/); assign to g for "graph"

    • +/'p=/:/:g for each of g's neighbour lists build a boolean mask for which people are in it. ignore non-people.

    • ?( )^0 remove scalar 0s (( )^0) as they are a by-product of empty neighbour lists, and make the rest unique (?). this gives us a list of families as boolean masks.

    • t' build a family matrix for each family

    • 0|/ boolean-or of all family matrices

    • (#a;1) replace 0s with "infinity" (the length of a is as good as infinity here) and keep 1s as they are - this is a graph of how closely related p are. we need to find the shortest paths in it.

    • (~=#p)* put 0s on the diagonal. literally: multiply (*) by the negation (~) of the unit matrix (=) of that size (#p)

    • {&/'x+\:+x}/ until convergence, try to improve dist(i,j) with dist(i,k)+dist(k,j) (similar to the floyd-warshall algorithm)

    • 3< more distant than first cousins

  • they must not be already married

    • t[~|/p=/:?,/2#'(p^p^)'g] check which p are among the first 2 (2#) of the intersection between people ((p^p^)) and each (') neighbour list in g, and make it a boolean table
  • they must be of opposite sexes

    • (~h=\:h:4!c p) remember that c mod 4 encodes gender information

finally, |//...&...&... and-s the three matrices and tests if there's a truthy element in the result

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Yes, we have our first entry! Would you mind unwrapping it for me? I'd love to see your approach. \$\endgroup\$
    – KeizerHarm
    Nov 18, 2019 at 8:00
  • \$\begingroup\$ Ah, thank you. Count me impressed! We'll see if someone else dares to complete this challenge... \$\endgroup\$
    – KeizerHarm
    Nov 18, 2019 at 13:52
5
\$\begingroup\$

Jelly, 160 159 bytes

Ø.UN,ƊAN,Ɗ+Ṫ¥+œị2,5yⱮ$ɼ=5,6⁼Ø.Ɗɗ¡ƬṪ¥ƒ⁸’1¦⁺œị®⁼5ƊпṖṪ+2¦œị®⁻.Ɗ¡ƬṪ¥ⱮØ+$“”¹?
Odȷ%⁴ỊḢịƊ€€H“¥©“©©‘;U¤œṣjƭƒ$€ƬṪ©=.ŒṪ+2¦œị®ɗⱮØ+f2,4ƊÐḟWÇ€Ẏ$Ƭḣ3ẎƲ€Œcf/ÐḟḢ€€ȧœị¥O>⁽¡FIFẸ

Try it online!

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\$
1
  • \$\begingroup\$ Holy moly...... \$\endgroup\$
    – Razetime
    Dec 30, 2020 at 11:32
1
\$\begingroup\$

Python3, 1001 bytes:

m='АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
f=m.lower()
def g(t,c,l,w,d,s=[],r=[],o=-1):
 k=0
 for q,(x,y) in [(0,[0,-1]),(1,[1,0]),(1,[-1,0])]:
   if q!=o and len(t[0])>(a:=c[0]+x)>=0 and len(t)>(b:=c[1]+y)>=0 and(a,b)not in r:
    if(h:=t[b][a])=='│'or h=='─':k=1;yield from g(t,(a,b),l,q,d,s,r+[(a,b)])
    elif h =='┴':k=1;yield from g(t,(a,b),h,q,d,s,r+[(a,b)],o=1)
    elif h=='┬':
     if q:d.append(s[-1])
     else:k=1;yield from g(t,(a,b),h,q,d,s,r+[(a,b)])
    elif h in m+f and l in'┬┴':k=1;yield from g(t,(a,b),h,q,d,s+[h],r+[(a,b)])
 if not k:yield s
def e(x,y):
 return not any((q:=set(a)&set(b)) and any(a.index(i)<3 for i in q) for a in x for b in y)
def a(t):
 b,p,z=[*filter(None, t.split('\n'))],{},[]
 for x,y in[(x,y)for x in range(len(b[0]))for y in range(len(b))if(l:=b[y][x])in m+f]:
   for s in g(b,(x,y),b[y][x],0,z,s=[b[y][x]],r=[(x,y)]):
    p[s[0]]=p.get(s[0],[])+[s]
 return any(a not in z and b not in z and len(set([a in m, b in m]))==2 and e(p[a],p[b]) for a in p for b in p)

The basic idea is to traverse the input graph, building paths between nodes (the genealogy for each node), marking which nodes are already married, and then checking if it is possible for any two resulting nodes to marry (not already married, male and female, not cousins, etc.)

Try it online!

\$\endgroup\$

Your Answer

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

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