7
\$\begingroup\$

One day, I saw the challenge to multiply two strings and I thought I might be able to do one better.

That challenge was fake. It was elementwise maximum. It was not real multiplication. So I set out to make something real. Real division between two strings.

I quickly realized that this would make an amazing challenge, as the algorithm was surprisingly complex and interesting to implement.

I then realized that it was actually easily reduced into a mere few operations. I'm still doing the challenge, though.

Enough with the backstory. Let's go.

Method

To divide two strings, do the following, where x is the first string and y the second:

  • If x does not contain y, return a space and a period concatenated to x.
    • For example, testx and blah would become .testx, with a space at the beginning.
  • Otherwise, return every occurrence of y in x, a period, then y divided by x with every occurrence of y removed, with all the periods removed.
    • For example, eestestst and est would become estest.est.

Challenge

Write a program or function that, given two strings via standard input, returns the first string divided by the second.

You may assume that both input strings will only contain letters between ASCII codepoints 33 and 45, and between codepoints 47 and 126 (yes, space and period are intended to be excluded), and that the operation does not require more than 10 layers of recursion.

You are not required to divide the empty string by itself.

Test cases

test, es => es. es
test, blah =>  .test
okayye, y => yy. y
testes, es => eses. es
battat, at => atat. at
see, es =>  .see
see, e => ee. e
same, same => same. 
aabb, ab => ab.ab 
eestestst, est => estest.est
aheahahe, aheah => aheah.aheah ah
-={}[];:"'!@#$%^&*()~`\|/.<>_+?, ^&*()~` => ^&*()~`. ^&*()~`
best,  => . 

Scoring

As this is , the submission with the least amount of bytes wins.

\$\endgroup\$
8
  • \$\begingroup\$ 1. Can we assume that the input strings only contain characters from a to z? 2. Why isn't the output of the first one es.tt? 3. Why is there a space after the periods in your testcases? \$\endgroup\$
    – Leaky Nun
    Jun 8, 2018 at 8:51
  • \$\begingroup\$ 1. No, besides the assumptions already listed. As for 2 and 3, note that the solution is recursive. test and es is es divided by tt, which is <space>.es as tt is not in es, and the period is removed. A similar thing happens for the other testcases with spaces. Note that the presence of a period after a period varies. \$\endgroup\$
    – LyricLy
    Jun 8, 2018 at 8:56
  • \$\begingroup\$ Then can you include testcases with characters other than a to z? What exactly are the characters that will appear? Can you phrase it in a positive instead of a negative? \$\endgroup\$
    – Leaky Nun
    Jun 8, 2018 at 8:58
  • \$\begingroup\$ Why is same. the output of same, same? \$\endgroup\$
    – Leaky Nun
    Jun 8, 2018 at 9:00
  • 2
    \$\begingroup\$ Your .testx string reads .textx instead. \$\endgroup\$
    – boboquack
    Jun 8, 2018 at 11:34

8 Answers 8

3
\$\begingroup\$

Python 2, 88 85 84 77 bytes

f=lambda x,y,d='.':y in x and y*x.count(y)+d+f(y,x.replace(y,''),'')or' '+d+x

Try it online!


Saved

  • -1 byte, thanks to LyricLy
  • -7 bytes, thanks to Dead Possum
\$\endgroup\$
4
  • \$\begingroup\$ 84 bytes by removing unneeded parentheses. \$\endgroup\$
    – LyricLy
    Jun 8, 2018 at 8:44
  • \$\begingroup\$ 77 bytes \$\endgroup\$ Jun 8, 2018 at 8:44
  • \$\begingroup\$ @DeadPossum wow clever, thanks ;) \$\endgroup\$
    – TFeld
    Jun 8, 2018 at 8:47
  • 1
    \$\begingroup\$ I'm not sure of an implementation yet, but perhaps you can use the fact that y*x.count(y) returns a falsy value to drop the y in x check? \$\endgroup\$
    – Mr. Xcoder
    Jun 8, 2018 at 8:50
2
\$\begingroup\$

Java (JDK 11), 146 bytes

String f(String x,String y){int c=x.replace(y," ").split(" ",-1).length-1;return c<1?" ."+x:y.repeat(c)+"."+f(y,x.replace(y,"")).replace(".","");}

Try it online using Java 10! This TIO emulates String::repeat of Java 11 by writing Kevin Cruijssen's implementation as a helper method with the same amount of bytes.

Explanations

String f(String x,String y){                     // 
  int c=x.replace(y," ").split(" ",-1).length-1; // Count the number of occurrences of y in x.
                                                 // replace(y," ") fixes the issue on special characters for the split hereafter
                                                 // .split(" ",-1) makes sure that there are trailing elements
  return c<1
    ?                                            // If there are no occurrence, return 
      " ."+x                                     // " ."+x
    :                                            // Else return 
        y.repeat(c)                              // y, c times
      + "."                                      // append a dot
      + f(y,x.replace(y,"")).replace(".","");    // y divided by x without y, and remove all dots
}

String.repeat(int) only exists since Java 11, hence the JDK 11 header. Alas and to my knowledge, there are currently no Java 11 online compiler / tester...

\$\endgroup\$
6
  • 1
    \$\begingroup\$ For anyone wondering: Prove it indeed works by replacing y.repeat(c) with new String(new char[c]).replace("\0",y). \$\endgroup\$ Jun 8, 2018 at 9:29
  • \$\begingroup\$ Thanks @KevinCruijssen I'll integrate that in my answer. I should have done that, actually... \$\endgroup\$ Jun 8, 2018 at 9:33
  • \$\begingroup\$ @KevinCruijssen Thank you, I've been doing this quickly on the side and didn't check better. My bad. The random ascii characters don't work probably because they contain special characters used in regex (implicitly used by split). I'll try to fix this. \$\endgroup\$ Jun 8, 2018 at 9:51
  • 1
    \$\begingroup\$ How about using x.replace(y," ").split(" ",-1)? \$\endgroup\$
    – Jakob
    Jun 8, 2018 at 18:06
  • 1
    \$\begingroup\$ Works like a charm! Thanks @Jakob, that's very imaginative! \$\endgroup\$ Jun 8, 2018 at 20:26
1
\$\begingroup\$

Python 2, 72 bytes

lambda f,s:(s*f.count(s)+'.'*(s in f))+s*(s in f)+(' .'+f)*(f.find(s)<0)
\$\endgroup\$
0
\$\begingroup\$

Proton, 75 bytes

f=(x,y)=>(u=x.count(y))?y*u+'.'+f(y,x.replace(y,'')).replace('.',''):' .'+x

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Physica,  81 75  67 bytes

f=>x;y;d='.':y∈x&&y*x.count[y]+d+f[y;Replace[x;y;''];'']||' '+d+x

Try it online!

Utilizes Dead Possum's golfs on TFeld's answer.

\$\endgroup\$
0
\$\begingroup\$

Retina, 105 bytes

¶.*$
$&¶.
/^(.*)¶.*\1/{*>|""L`(?<=(.*)¶.*)\1|\.$
(?<=(.*)¶.*)\1|\.$

)`(.*)¶(.*)
$2¶$1
.*¶(.*)¶(.*)
 $2$1

Try it online! Link includes test suite, but code normally takes y then x on separate lines. Explanation:

¶.*$
$&¶.

Append a newline and a . This expression is cumbersome in order to deal with an empty second input, where $ would otherwise match twice.

/^(.*)¶.*\1/{

Repeat while x contains y.

*>|""L`(?<=(.*)¶.*)\1|\.$

Output all of the matches of y in x, plus the . on the first pass.

(?<=(.*)¶.*)\1|\.$

And then delete them all.

)`(.*)¶(.*)
$2¶$1

Swap over x and y and repeat.

.*¶(.*)¶(.*)
 $2$1

Output the . if x never contained y, and y.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Babel Node), 90 bytes

Based on Olivier Grégoire Answer

(_,x)=>(l=_.match(RegExp(x,`g`)))?l.join``+`.`+f(x,_.replace(x,'')).split`.`.join``:` .`+_

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Stax, 28 bytes

Çûù=a┐µ¬▄↑ivܰ{⌐╨[£èvÇu┴▓<v~

Run and debug it

\$\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.