13
\$\begingroup\$

Introduction

Bob runs a deli. His deli serves sandwiches to its customers. However, it is a bit unusual. At Bob's deli, instead of telling Bob what they want, customers show Bob an ASCII art drawing of their sandwich. Bob must find the pattern in their sandwich so he knows what ingredients to prepare. However, Bob does not like picking out patterns. He wants you to write a program to help him do that.

Challenge

You must write a function which, given the filling of a sandwich, will output a list of ingredients for Bob to prepare. You must find the pattern of ingredients in the filling, then output that pattern.

  • Input will be a string. It will never be empty, and it will only contain printable ASCII characters (characters 32 to 255). If your language has no method of input, input can be taken in the form of command line arguments or stored in a variable.
  • Output must be a string. If your language has no method of output (or you are running a function, not a full program) you may output through return code or through a variable.

Example I/O

  • Input: |&|&|&|&
    Output: |&
  • Input: :&|:&|:&|
    Output: :&|
  • Input: ((&|((&|((&|((&|
    Output: ((&|

Rules

This is , so shortest answer wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ @JoKing - The challenge has been modified. Now contestants must simply find the pattern in a string. \$\endgroup\$ – sugarfi Nov 6 at 22:56
  • 2
    \$\begingroup\$ Will the input always be a string repeated multiple times? \$\endgroup\$ – xnor Nov 6 at 23:45
  • 2
    \$\begingroup\$ @xnor - yes, you can assume that. \$\endgroup\$ – sugarfi Nov 7 at 0:42
  • 9
    \$\begingroup\$ Is |&|& a valid answer for the first example input? \$\endgroup\$ – Greg Martin Nov 7 at 6:50
  • 9
    \$\begingroup\$ Bob makes a special deli where he reads patterns, but hates reading patterns. Bob is an excellent metaphor, for what I'm not sure. \$\endgroup\$ – Redwolf Programs Nov 7 at 13:32

22 Answers 22

24
\$\begingroup\$

Python, 28 bytes

lambda s:s[:(s+s).find(s,1)]

Try it online!

The length of the output is the first nonzero position starting from which s can be found in the doubled s+s.

For example:

s   = abcabcabc

s+s = abcabcabcabcabcabc
         abcabcabc
         ^
         s starting at position 3 (zero-indexed)

46 bytes

f=lambda s,p='':p*(s+p==p+s)or f(s[1:],p+s[0])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This is very clever \$\endgroup\$ – Cruncher Nov 11 at 14:33
7
\$\begingroup\$

05AB1E, 3 bytes

η¢Ï

Try it online!

η     # prefixes of the input
 ¢    # count the number of occurences of each one within the input
  Ï   # filter the input, keeping only indices where the above is 1

Prefixes that stop short of the last repetition of the pattern can be found multiple times in the input, offset by a pattern-length. Thus, this ends up keeping only the last repetition of the pattern.

\$\endgroup\$
6
\$\begingroup\$

Jelly, 5 bytes

Ḋ;wḣ@

Try it online!

A slightly modified version of xnor's answer. Method: Given S, concatenates Swithout the first character with S, then finds the index of S in this new string, then takes the head.

\$\endgroup\$
4
\$\begingroup\$

J, 22 15 bytes

{.~1+]i.~#$&><\

Try it online!

No regex solution:

{.~                      NB. take from the input this many chars:
    1 +                  NB. 1 plus...
          i.~            NB. the first index of...
        ]                NB. the input in this list:
                    <\   NB. every prefix of the input...
                $&>      NB. cyclically repeated to...
              #          NB. the size of the input.

I could shave off two more bytes using a xnor's wholly different approach, but for the sake of variety I'll leave my original as the answer:

{.~1{]I.@E.,~

Try it online!

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 25 bytes

s=>/(.+?)\1*$/.exec(s)[1]

Try it online!

Regular expression

   +-------> 1st (and only) capturing group: 1 or more character(s), non greedily
   |   +---> reference to the capturing group, repeated 0 to N times
  _|_  | +-> end of string
 /   \/ \|
/(.+?)\1*$/
\$\endgroup\$
  • \$\begingroup\$ Find any characters, followed by that match repeated 0 or more times. Execute that regex on the input and return the first capture group? \$\endgroup\$ – Pureferret Nov 8 at 10:12
  • \$\begingroup\$ @Pureferret The regular expression will match 1 or more characters (except newlines) in a non-eager way, and will match that captured group of characters at least 0 times until the end of the string. The anonymous function will return the value in the key 1 in the resulting array from the exec method of the regular expression. This works because if .+? matches any number of characters, and (.+?)\1* ensures that whatever is left is exactly the same as the capturing group or nothing at all ($). Check regex101.com/r/r1iXY6/1 for a much better explanation. \$\endgroup\$ – Ismael Miguel Nov 8 at 12:24
  • \$\begingroup\$ @IsmaelMiguel is that not what I said (just less clearly)? \$\endgroup\$ – Pureferret Nov 8 at 12:33
  • \$\begingroup\$ @Pureferret And more accurate. Which is the problem with my explanation :/ But Arnauld added a good explanation. \$\endgroup\$ – Ismael Miguel Nov 8 at 12:43
3
\$\begingroup\$

Icon, 50 bytes

procedure f(s)
return s[1:1+find(s,s[2:0]||s)]
end

Try it online!

An Icon port of xnor's Python solution. Don't forget to upvote his answer!

\$\endgroup\$
3
\$\begingroup\$

Perl 5 (-p), 15 bytes

s/(.+?)\1*$/$1/

Try it online!

\$\endgroup\$
3
\$\begingroup\$

C (clang), 72 bytes

f(char*s){int n=1,p=1;while(s[p]|p%n)s[p]^s[p%n]?p=++n:++p;puts(s+p-n);}

Try it online!

Explanation:

The algorithm is a simple brute force search, checking whether the entire string is a repetition of a pattern of length n=1,2,3,…. The non-golfed implementation could be as follows:

void f(char* s)
{
    // try pattern length=1,2,3…
    for (int n = 1; ; n++)  
    {
        // loop over the string (until null terminator) to see if
        // it's a repetition of the pattern
        int p = n;
        for (; s[p]; p++)  
        {
            if (s[p] != s[p%n])
            {
                // not a repeating pattern
                break;
            }
        }

        if (!s[p]) {
            // we've reached the end of the string, so it seems to be
            // a repeating pattern… but it's not a valid solution
            // if the pattern is cut off in the middle ("cutoff case"):
            // e.g. abc-abc-abc-ab
            if (p % n == 0)
            {
                // print and return: we can simply output the *last*
                // occurrence of the pattern, because it is followed 
                // by the null terminator
                puts(s + p - n);
                return;
            }
        }
    }
}

The golfed version is doing this in a single loop:

f(char* s)
{
    int n=1,p=1;
    while (s[p]|p%n)
        // more verbosely, s[p] || (p%n != 0)
        // - Loop while we haven't reached the null terminator.
        // - If we have, keep going if p is not a multiple of n
        //   (i.e. in the cutoff case).
    {
        s[p]^s[p%n]?p=++n:++p;
            // more verbosely,
            // if (s[p] != s[p%n]) { n++; p = n; } else { p++; }
            // - If the pattern is not repeating, increment the pattern
            //   length n and start over. This also applies in the cutoff
            //   case; in that case s[p] is the null terminator.
            // - Otherwise increment p and continue checking the string.
    }
    puts(s+p-n);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 69 using for statement and n,p default to int \$\endgroup\$ – AZTECCO Nov 7 at 13:42
2
\$\begingroup\$

Perl 6, 16 bytes

{m/(.+?))>$0+$/}

Try it online!

Standard regex solution, finding a non-greedy match that repeats for the whole string

\$\endgroup\$
2
\$\begingroup\$

Jelly, 6 bytes

sJEƇḢḢ

A monadic Link accepting a list of characters which yields a list of characters.

Try it online!

How?

sJEƇḢḢ - Link: list of characters, S
 J     - range of length (S) = [1,2,3,...,length(s)]
s      - (S) split into chunks (of each of these sizes)
   Ƈ   - filter keep those for which:
  E    -   all equal?
    Ḣ  - head
     Ḣ - head
\$\endgroup\$
2
\$\begingroup\$

Retina, 12 bytes

(.*?)\1*$
$1

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

η.ΔKõQ

Try it online or verify all test cases.

Or alternatively:

«¦sk>£

Try it online or verify all test cases.

Explanation:

η       # Get the prefixes of the (implicit) input-string
 .Δ     # Get the first prefix which is truthy for:
   K    #  Remove all occurrences of this substring in the (implicit) input-string
    õQ  #  And check if what remains is an empty string
        # (after which the found prefix is output implicitly as result)

«       # Append the (implicit) input-string with itself
 ¦      # Remove the first character
  sk    # Get the (0-based) index of the input-string in the earlier created string
    >   # Increase this by 1 to make it a 1-based index
     £  # And only leave that amount of leading characters from the (implicit) input-string
        # (after which this is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Red, 51 bytes

func[s][copy/part t: append copy s s find next t s]

Try it online!

A Red port of xnor's Python solution. Don't forget to upvote his answer!

Using parse:

Red, 71 bytes

func[s][n: 0 until[n: n + 1 parse s[copy t n skip any t]]copy/part s n]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 46 bytes

lambda s:re.match(r"(.+?)\1*$",s)[1]
import re

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Since the challenge has been changed, this answer is no longer valid. \$\endgroup\$ – sugarfi Nov 6 at 22:56
  • 1
    \$\begingroup\$ @sugarfi its okey, i updated my answer :) \$\endgroup\$ – Delta Nov 6 at 23:17
1
\$\begingroup\$

Ruby -p, 18 bytes

~/(.+?)\1*$/
$_=$1

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt, 7 bytes

¯ÒU²ÅbU

Try it

¯ÒU²ÅbU     :Implicit input of string U
¯           :Slice to 0-based index
 Ò          :  Bitwise increment
  U²        :    Duplicate U
    Å       :    Slice off the first character
     bU     :    First index of U

Alternative/Original

Since posted by Aztecco.

ã æ@¶îX

Try it

ã æ@¶îX     :Implicit input of string U
ã           :Substrings
  æ         :First element that returns true
   @        :When passed through the following function as X
    ¶       :  Test U for equality with
     îX     :  X repeated to length of U
\$\endgroup\$
  • \$\begingroup\$ Seen your answer just after posting mine! \$\endgroup\$ – AZTECCO Nov 7 at 16:44
  • \$\begingroup\$ @AZTECCO, I'll update with my alternative 7 byte solution momentarily and you can have this one. \$\endgroup\$ – Shaggy Nov 7 at 18:57
  • \$\begingroup\$ @AZTECCO, updated. \$\endgroup\$ – Shaggy Nov 7 at 19:12
  • \$\begingroup\$ Ok then I undelete mine, thank you @Shaggy \$\endgroup\$ – AZTECCO Nov 7 at 21:12
1
\$\begingroup\$

Japt, 7 bytes

ã f@¥îX

Try it

U.ã(). // all substrings
f( // filtered by..
function(X, Y, Z) { return U == U.î(X) }) // item repeated till input.length == input
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 3 bytes

ġ≡ᵛ

Try it online!

ġ      Split the input into substrings of equal length
 ≡ᵛ    such that each substring is the output.
\$\endgroup\$
1
\$\begingroup\$

SimpleTemplate 0.62, 184 bytes

Yeah ... This is a very long one ...

It highlights the weaknesses of that specific version (check below for version 0.72).

{@setI 0}{@setC""}{@setA argv.0}{@do}{@setO"{@setc A.",I,"}"}{@callimplode intoO O}{@evalO}{@setC C,c}{@callimplode intoC C}{@incI}{@callstr_replace intoR C,"",A}{@untilR is""}{@echoC}

This is a huge mess, here's the ungolfed one:

{@set index 0}
{@set chars ""}
{@set arg argv.0}

{@do}
    {@set code "{@set char arg.", index, "}"}
    {@call implode into code code}
    {@eval code}
    {@set chars chars, char}
    {@call implode into chars chars}

    {@inc by 1 index}
    {@call str_replace into result chars, "", arg}
{@until result is equal to ""}

{@echo chars}

Yes, those 5 lines inside the {@do} only do 2 things:

  1. Get the character at the position of the index value.
  2. Add the character into the variable chars, as a string.

You can test the golfed and ungolfed versions on http://sandbox.onlinephpfunctions.com/code/7f2065a193d2bd0920cc3a4523e4b0ebf7a72644



Version 0.72, 112 bytes

This non-competitive version uses new features I've developed today, to allow me to do more with the language.

First, here's the code:

{@setX}{@setC""}{@do}{@setC"#{C}#{argv.0.[X]}"}{@incX}{@callstr_replace intoR C,"",argv.0}{@untilR is""}{@echoC}

It looks like a mess! Lets clear it up:

{@set index 0}
{@set chars ""}

{@do}
    {@set chars "#{chars}#{argv.0.[index]}"} {@// NEW IN 0.72}
    {@inc by 1 index}
    {@call str_replace into result chars, "", argv.0}
{@until result is equal to ""}

{@echo chars}

Most of this has been explained in other answers, so, I will focus on this line: {@set chars "#{chars}#{argv.0.[index]}"}.

This showcases 2 new features in the language and a bugfix:

  • Now you can get a value from an array based on the value of a variable
  • Now there's string interpolation, where "#{chars}" will interpret the chars variable and the result is a single string. Before, you would have to do {@set chars chars, value2, ...}, which makes an array instead of a string.
  • Previously, you could only access 1 member of an array/string. Currently, you can access as many deep in as you want. This meant that {@echo argv.0.0} would need to be written as {@set arg argv.0}{@echo arg.0}.

The line {@set chars "#{chars}#{argv.0.[index]}"} replaces the previously mentioned lines inside the {@do}.

You can try this on http://sandbox.onlinephpfunctions.com/code/e2ab3d10c8224ee475cf4d4ca94fef7896ae2764

\$\endgroup\$
  • 1
    \$\begingroup\$ Non-competing isn't a thing anymore. Unless you added the new features specifically for this challenge, in which case the solution is invalid. \$\endgroup\$ – Shaggy Nov 7 at 23:36
  • \$\begingroup\$ @Shaggy Got any meta links for that? If you do, once presented, I will delete the answer. And no, I added those for all challenges in the future. This was more for me to "test the waters". So many challenges were impossible (like this one) without those changes. \$\endgroup\$ – Ismael Miguel Nov 7 at 23:53
  • \$\begingroup\$ The way in which @Shaggy is claiming this might be invalid is by violating this standard loophole, however adding new general features after a challenge is OK. See here for the meta post abolishing non-competingness. \$\endgroup\$ – pppery Nov 8 at 1:38
  • \$\begingroup\$ @pppery None of those apply. This language has been used at least 15 times by me, on other challenges, over the last 2 years. The features I've added are for my language aren't made so I could use it in this specific challenge, but features I've been wanting to implement for a very long time. I just used this challenge to test them out, and decided to post the test as an answer. Previously, this type of challenge would have been almost impossible. I could change my {@set chars "#{chars}#{argv.0.[index]}"} line into something extremelly convoluted, that wouldn't be worth the time [...] \$\endgroup\$ – Ismael Miguel Nov 8 at 9:12
  • \$\begingroup\$ [...] spent on the challenge, when there were answers that are 3-10 bytes long and do it well. To make that line work previously, I would have to do it in 3x the length, at least. It isn't something specific for this challenge, but for future usage of the language. To write that single line, I would have to write {@call implode into code "{@set char argv.0.", index, "}"}{@eval code}{@call implode into chars chars, char}, or similar. just to be able to do this type of challenge. \$\endgroup\$ – Ismael Miguel Nov 8 at 9:23
0
\$\begingroup\$

Charcoal, 10 bytes

…θ§⌕A⁺θθθ¹

Try it online! Link is to verbose version of code. Adaptation of @xnor's answer. Explanation:

     ⁺θθ    Duplicate the input
   ⌕A   θ   Find all indices of the input
  §      ¹  Skip the first index, which is always zero
…θ          Truncate the input to that length
            Implicitly print
\$\endgroup\$
0
\$\begingroup\$

Wren, 37 bytes

Basically a port.

Fn.new{|a|a[0..(a+a).indexOf(a,1)-1]}

Try it online!

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

R, 33 36 bytes

sub("(.+?)\\1*$","\\1",scan(,""))

Try it online

\$\endgroup\$

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.