-5
\$\begingroup\$

Intro

When you search in google, it always shows you a result with a sample text from the found webpage.

For example if you search for "Madonna greatest vinyl", google will show you one line link, and below a short excerpt from that found webpage:

Madonna Greatest Hits Records, LPs, Vinyl and CDs
Madonna - Greatest Hits Volume 2, Madonna, Greatest Hits ... vinyl Is Fully Restored To As Near New Condition As Possible. Shipping & Multiple Order D..

Task

Imagine yourself you work for google and you have to write a program/function which takes in:

  • a string containing many words (the webpage content)
  • list of searched words (at least 3)

and returns the shortest excerpt of given string (webpage) containing all searched words.

Example

Given this webpage content:

This document describes Session Initiation Protocol (SIP), an application-layer
 control (signaling) protocol for creating, modifying, and terminating
 sessions with one or more participants. These sessions include 
 Internet telephone calls, multimedia distribution, and multimedia conferences.

and these searched words: 

calls, sessions, internet

the program should return: 

sessions include Internet telephone calls
, as this is the shortest substring containing all 3 searched words. Note that one more substring contains these 3 words, it is "sessions with one or more participants. These sessions include Internet telephone calls", but it is longer, so it was discarded.

Rules

  • If the string is empty, return empty string
  • If all searched words are not found in given string, return empty string
  • Search is ignoring letters case
  • At least 3 words need to be specified for searching
  • The returned string may contain the searched words in different order than specified

Challenge

Write the fastest code. It's for google, right? Remember that repeatable strings comparison is very expensive.

|improve this question
\$\endgroup\$
  • 1
    \$\begingroup\$ Google doesn't always show a sample. Next time please post to the sandbox first. \$\endgroup\$ – fəˈnɛtɪk Feb 23 '17 at 12:19
  • 1
    \$\begingroup\$ This looks like it could be a good challenge, but you need to be more specific about the task, e.g. by defining possible inputs and outputs. Will there always be one text and three search words? Are the search words arbitrary strings? What should be returned if not all search words are present in the text? \$\endgroup\$ – Laikoni Feb 23 '17 at 12:41
  • \$\begingroup\$ So... what's the winning criteria? \$\endgroup\$ – DJMcMayhem♦ Feb 23 '17 at 19:46
  • \$\begingroup\$ I could maybe require to do it in one loop, but that would be a hint. \$\endgroup\$ – Filip Stachowiak Feb 25 '17 at 13:57
1
\$\begingroup\$

05AB1E, 13 bytes

Œévyl²l#åPiyq

Explanation:

Ύ            # Get substrings sorted by shortest first
  vyl         # For each substring (in lowercase)...
     ²l#      # Split the searched text (in lowercase)on spaces
        åP    # Check if each word of the searched text is in the substring
          iyq # If so, print the substring and terminate the program

Try it online!

It will only work for one line of input.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ It's very inefficient. Do you know how many substrings will it be if there are n words? I guess n!. And generating all of them will be time-consuming. \$\endgroup\$ – Filip Stachowiak Feb 25 '17 at 13:19
  • \$\begingroup\$ @FilipStachowiak This is code-golf, right? Not fastest-code. I'm not entirely sure because there is no tag on your question for the winning criterion. \$\endgroup\$ – Okx Feb 25 '17 at 13:23
  • \$\begingroup\$ Actually I removed the code-golf tag when I understood its meaning. There are no special winning criteria for this task. I think it's interesting as-is. \$\endgroup\$ – Filip Stachowiak Feb 25 '17 at 13:56
  • \$\begingroup\$ @FilipStachowiak that's exactly why it's closed as unclear what you're asking. The rules of PPCG state that every challenge must have an objecting winning criterion. \$\endgroup\$ – Okx Feb 25 '17 at 14:07
  • \$\begingroup\$ Great! I'll figure sth out. \$\endgroup\$ – Filip Stachowiak Feb 25 '17 at 14:10

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