19
\$\begingroup\$

Background

A matryoshka doll (or Russian nesting doll) is a set of dolls that fit inside of each other. I've accidentally mixed up my collection of matryoshka dolls and I don't remember which one goes inside which.

Objective

Given a list of unique strings, sort them into nested matryoshka dolls. Each string is an individual doll, and a matryoshka doll is a list of strings.

Rules

Let min(a,b) be the lexicographic min of strings a and b. Let a ⊂ b denote that a is a substring of b. Then,

  1. The list of matryoshka dolls must be sorted lexicographically
  2. String a can fit into string b if a ⊂ b
  3. If a ⊂ b and a ⊂ c, then a will go inside min(b,c)
  4. If both a ⊂ c and b ⊂ c, but a ⊄ b b ⊄ a, then only min(a,b) will go inside c
  5. If both a ⊂ c and b ⊂ c, and also a ⊂ b, then only b will go inside c. I.e., superstrings go before substrings so that the matryoshka isn't prematurely terminated.

Examples

In:
hahaha, hah, lol, lololol, bahaha, bah, haha, ah

Out:
bahaha, bah, ah
hahaha, haha, hah
lololol, lol

In:
aa, aaaa, a, aaaaaaaaaa

Out:
aaaaaaaaaa, aaaa, aa, a
\$\endgroup\$
13
  • 3
    \$\begingroup\$ First post here, please point out anything dumb / fixes needed. \$\endgroup\$
    – sujeet
    Jan 16, 2018 at 1:22
  • 2
    \$\begingroup\$ Welcome to PPCG! If you're not sure if the post is good enough, you can post it in the Sandbox first. \$\endgroup\$
    – DELETE_ME
    Jan 16, 2018 at 1:28
  • 2
    \$\begingroup\$ It's not mandatory, just keep it here. The community like it. \$\endgroup\$
    – DELETE_ME
    Jan 16, 2018 at 1:42
  • 2
    \$\begingroup\$ @sujeet in the future, try to post to the sandbox first. It's a place to get feedback about your challenges before you post them on the main site. Don't worry about it now, since this challenge seems fine as is, but it's something to consider for the future. \$\endgroup\$
    – Riker
    Jan 16, 2018 at 2:01
  • 3
    \$\begingroup\$ What should be the result of ab, ba, aba, bab? By rule 3, both ab and ba should go into aba, and by rule 4, ba cannot go into either aba or bab. \$\endgroup\$
    – Zgarb
    Jan 16, 2018 at 10:28

1 Answer 1

2
\$\begingroup\$

Python 2, 298 bytes

def f(x,E=enumerate):
 o=[]
 while any(x):
	for k,p in E(x):
	 e=0
	 if sum(i(p,j)for j in x)<1:
		for d,r in E(o):
		 if i(p,r[-1])*((r[-1]<e)or e==0):m,e=d,r[-1]
		if e:o[m]+=[p]
		else:o+=[[p]]
		x[k]=''
 print sorted(o)
i=lambda p,b:(b!=p)*any([p==b[j:j+len(p)]for j in range(len(b)-len(p)+1)])

Try it online!

-28 bytes with tips from @dylnan, bug find by @Dennis, and bug fix by @Mr.Xcoder

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 301 bytes. Just turned i into a lambda function and changed the variable name out to o. \$\endgroup\$
    – dylnan
    Jan 16, 2018 at 6:09
  • 1
    \$\begingroup\$ 297 bytes (E=enumerate) \$\endgroup\$
    – dylnan
    Jan 16, 2018 at 6:14
  • \$\begingroup\$ Functions have to be reusable, but the out variable never changes. Try it online! \$\endgroup\$
    – Dennis
    Jan 16, 2018 at 14:09
  • \$\begingroup\$ To fix that issue, 298 bytes. Also, out, 3-char variable name... Seriously :P? \$\endgroup\$
    – Mr. Xcoder
    Jan 16, 2018 at 15:43

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.