Making Sandwiches

Question

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 code-golf, so shortest answer wins!

Answer 1

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!

Answer 2

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.

Answer 3

Jelly, 5 bytes

Ḋ;wḣ@

Try it online!

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

Answer 4

J, ²² 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!

Answer 5

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*$/

Answer 6

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!

Answer 7

Perl 5 (-p), 15 bytes

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

Try it online!

Answer 8

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);
}

Answer 9

Perl 6, 16 bytes

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

Try it online!

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

Answer 10

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

Answer 11

Retina, 12 bytes

(.*?)\1*$
$1

Try it online!

Answer 12

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)

Answer 13

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!

Answer 14

Python 3, 46 bytes

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

Try it online!

Answer 15

Ruby -p, 18 bytes

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

Try it online!

Answer 16

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

Answer 17

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

Answer 18

Brachylog, 3 bytes

ġ≡ᵛ

Try it online!

ġ      Split the input into substrings of equal length
 ≡ᵛ    such that each substring is the output.

Answer 19

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

Answer 20

GolfScript, 10 bytes

..2*1>\?)<

Try it online!

Explanation

.          # Make a copy of the initial input
 .2*       # Make another copy that has a double length
    1>     # Trunctuate the copy to without the first item
      \    # Swap the copy to below
       ?   # Find the index of the input
        )  # Increment the index
         < # Slice the input so that the whole section emerges

Answer 21

Husk, 6 bytes

↑¹€tD¹

Try it online! Yet another port of xnor's answer.

Answer 22

Vyxal, 6 bytes

dḢ?ḟ›Ẏ

Try it Online!

Yet another port of xnor's answer

Answer 23

Charcoal, 10 bytes

…θ§⌕Ａ⁺θθθ¹

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

     ⁺θθ    Duplicate the input
   ⌕Ａ   θ   Find all indices of the input
  §      ¹  Skip the first index, which is always zero
…θ          Truncate the input to that length
            Implicitly print

Answer 24

Wren, 37 bytes

Basically a port.

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

Try it online!

Answer 25

R, 33 36 bytes

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

Try it online