38
\$\begingroup\$

Garland Words

A garland word is a word which can be strung together like a garland, because it ends with the same letters it starts with. These groups of letters can even overlap!

For example, underground is a garland word of order 3, because it starts and end with the same 3 characters, und. This means it could be strung together like undergroundergrounderground....

alfalfa is a garland word, too! It's of order 4. It starts and ends with alfa. It can be strung together like so: alfalfalfalfa.

A process which I call garlandifying is where once you determine the order n of a garland word, you take the original word and add the segment required to have it loop as a garland n times. So, since onion is an order 2 garland word, you would take onion, chop off the first 2 letters to get ion and add that to the end 2 times to get onionionion.

Objective

Make a program or function which takes input from standard input or a function argument and prints out or returns the word, garlandified.

All words will be lowercase, and the highest possible order for a word is length(word) - 1.

Example I/O

"onion"       --> "onionionion"
"jackhammer"  --> "jackhammer"
"abracadabra" --> "abracadabracadabracadabracadabracadabra"
""            --> ""
"zvioz"       --> "zviozvioz"
"alfalfa"     --> "alfalfalfalfalfalfa"
"aaaa"        --> "aaaaaaa"

This is , so least number of bytes wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ Any N-letter word starts with the same N letters that it ends with. What is the maximum order that should be considered? \$\endgroup\$ – feersum Jul 15 '15 at 14:20
  • \$\begingroup\$ @feersum The maximum order is the word's length - 1. Added that to the main post. \$\endgroup\$ – Kade Jul 15 '15 at 14:22
  • \$\begingroup\$ Do I have to print out just the garland? or can I perhaps print it and an exception? \$\endgroup\$ – DeadChex Jul 15 '15 at 15:33
  • \$\begingroup\$ @DeadChex There should be no exceptions. \$\endgroup\$ – Kade Jul 15 '15 at 15:34
  • 1
    \$\begingroup\$ @LuisMendo It should work for arbitrarily long words. \$\endgroup\$ – Kade Jul 16 '15 at 11:34

17 Answers 17

12
\$\begingroup\$

Pyth, 19 18 bytes

+z*>Kf!xz>zT1zl>zK

Try it online: Demonstration or Test harness

Explanations:

+z*>Kf!xz>zT1zl>zK   implicit: z = input string
     f      1        find the first number T >= 1, which satisfies:
         >zT            all but the first T chars of z
       xz               index of ^ in z
      !                 == 0
    K                store in K
                     the order is length(z) - K
   >K        z       the last K chars
  *                  repeated
              l>zK   len(all but the last K chars) times
+z                   insert z at the beginning
\$\endgroup\$
14
\$\begingroup\$

Python, 60 bytes

f=lambda s,i=1:s.find(s[i:])and f(s,i+1)or(len(s)-i)*s[:i]+s

Was hoping for better, but oh well. s.find works neatly here in place of not s.startswith.

\$\endgroup\$
12
\$\begingroup\$

Retina, 58 bytes

.+
$0#$0
(.*)(.+)#.*\1$
$0#$1#$2-
+`\w#(\w*)-
#$1-$1
#.*-
<empty line>

Each line should go to its own file but you can run the code as one file with the -s flag.

The four substitution pairs do the followings:

  • Duplicate word so we can search for overlaps too.
  • Append the word split up at order number of characters.
  • Append the last part order times.
  • Keep the original word and the lastly appended part and drop everything else.

The string states for the example onion:

onion
onion#onion
onion#onion#on#ion-
onion#onion##ion-ionion
onionionion
\$\endgroup\$
10
\$\begingroup\$

Haskell, 64 bytes

g s=[b>>a|(a,b)<-map(`splitAt`s)[1..],and$zipWith(==)s b]!!0++s

Tests:

λ: g "onion"       == "onionionion"
True
λ: g "jackhammer"  == "jackhammer"
True
λ: g "abracadabra" == "abracadabracadabracadabracadabracadabra"
True
λ: g ""            == ""
True
λ: g "zvioz"       == "zviozvioz"
True
λ: g "alfalfa"     == "alfalfalfalfalfalfa"
True
λ: g "aaaa"        == "aaaaaaa"
True
\$\endgroup\$
10
\$\begingroup\$

Java, 160 157 bytes

static void g(String s){int i=s.length(),o;for(String p=s;i-->0;)if(s.endsWith(s.substring(0,i))){for(o=i;o-->0;)p+=s.substring(i);System.out.print(p);i=0;}}

Input/Output:

 g("abracadabra"); --> "abracadabracadabracadabracadabracadabra"

Spaced and tabbed for readability:

static void g(String s){
int i=s.length(),o;
for(String p=s;i-->0;)
    if(s.endsWith(s.substring(0,i))){
        for(o=i;o-->0;)
            p+=s.substring(i);
        System.out.print(p);
        i=0;
    }
}

Suggestions welcome.

\$\endgroup\$
  • \$\begingroup\$ As a note to my self, the String ops can be moved into the for loop to save a byte or two on semicolons \$\endgroup\$ – DeadChex Jul 16 '15 at 5:16
  • \$\begingroup\$ why not do i=0; ? \$\endgroup\$ – overactor Jul 16 '15 at 6:14
  • \$\begingroup\$ @overactor where? The reason I use the length is because I want the full String and then I want to move towards none of it, with substring I don't think I can avoid using it in this method and will take the byte penalty for it \$\endgroup\$ – DeadChex Jul 16 '15 at 10:04
  • 2
    \$\begingroup\$ I meant to break out of the outer for loop. \$\endgroup\$ – overactor Jul 16 '15 at 10:06
8
\$\begingroup\$

Sed: 87 84 characters

(83 characters code + 1 character command line option.)

h
s/(.*)./& \1/
T
s/(.+) \1.*/ \1 \1/
t
g
q
:
s/^([^ ]+)(.*)[^ ]$/\1 \1\2/
t
s/ //g

Sample run:

bash-4.3$ sed -r 'h;s/(.*)./& \1/;T;s/(.+) \1.*/ \1 \1/;t;g;q;:;s/^([^ ]+)(.*)[^ ]$/\1 \1\2/;t;s/ //g' <<< 'underground'
undergroundergroundergrounderground
\$\endgroup\$
  • \$\begingroup\$ Automatic upvote of sed answer ;-). Follow this tip to drop 2 chars from your label definition and branch \$\endgroup\$ – Digital Trauma Jul 15 '15 at 17:50
  • \$\begingroup\$ Tried, but I am afraid that advice is only for cases when you not have label-less jumps to the end of code. [A bit later…] Ok, thinking again, why I tried to process multiple input lines at once? \$\endgroup\$ – manatwork Jul 15 '15 at 17:57
7
\$\begingroup\$

CJam, 24 23 bytes

q_:Q,{~)Q>Q\#!},W>~_Q>*

q_:Q                       e# Read the input, take a copy and store it in Q too
    ,{        },           e# Take the length of the input and filter [0 .. len - 1] array
      ~)                   e# Same as number * -1
        Q>                 e# Take last number characters. Call this string S
          Q\#!             e# See if Q starts with S. After the filter, we will only have
                           e# those numbers from [0 .. len - 1] array which are valid orders
                W>~        e# Take the last order number, if exists.
                   _Q>*    e# Garlandify the input order times.

Just to start it with something..

Try it online here

\$\endgroup\$
5
\$\begingroup\$

Matlab: 97 89 82 bytes

Function that uses a regular expression with lookbehind and a capture group:

function t=f(s)
n=sum(regexp(s,'(.*$)(?<=^\1.+)'))-1;t=[s(repmat(1:n,1,end-n)) s];

That sum is needed to handle the empty-string input (convert [] into 0).

Examples:

> f('onion'), f('jackhammer'), f('abracadabra'), f(''), f('zvioz'), f('alfalfa'), f('aaaa')
ans =
onionionion
ans =
jackhammer
ans =
abracadabracadabracadabracadabracadabra
ans =
   Empty string: 1-by-0
ans =
zviozvioz
ans =
alfalfalfalfalfalfa
ans =
aaaaaaa
\$\endgroup\$
4
\$\begingroup\$

REGXY, 53 49 bytes

Uses REGXY, a regex substitution based language

//$'#/
/.(.+)#\1\K/#/
a/(#).(.*#)|#.*/$'$1$2/
//a

Overview: A number of regular expressions are applied. An example run would look like:

onion (input)
onion#onion (line 1 regex)
onion#on#ion (line 2 regex - find the repeated section and separate with #)
onionion#n#ion (line 3 regex - the length of the middle token is the garland order, remove a character and append the third token onto the original string on the left)
onionionion##ion (line 4 regex is a pointer to line 3 - repeat the previous again)
onionionion##ion (line 4 regex is a pointer to line 3 - strip everything after and including the #)

Detailed explanation The following is a line by line breakdown of the regexes:

//$'#/

This is a regex substitution which matches the first empty string (i.e. the start of the string) and replaces it with everything to the right of the match ($') followed by a hash. For example, it will turn onion into onion#onion.

/.(.+)#\1\K/#/

This line finds the section which overlaps by looking for a group of characters immediate preceding the # ((.+)) which are the same on the other side of the # (\1). The \K just means 'forget that I matched anything', meaning it will not actually be replaced in the substitution. This effectively, this means we just add a # to the position after the overlap has been found, turning onion#onion into onion#on#ion.

a/(#).(.*#)|#.*/$'$1$2/

The initial 'a' is just a label for the regex. After this, we find the first # followed by a single character (.) and capture everything after this until the next # (.*#). We replace this with everything to the right of the match, i.e. the last token ($'), followed by a # ($1), followed by the second token less a character (we treat this as a counter, decreasing it each iteration). In the case of onion#on#ion, the two tokens we backreference on are shown in brackets, and the section the entire regex matches is between the pipes: onion|(#)o(n#)|ion. We then replace the bits we match (between the pipes) with $' (everything to the right of the match, i.e. 'ion'), then $1 (the #), then $2 (n#), meaning we end up with onion|(ion)(#)(n#)|ion (brackets show the three tokens in the replacement string).

If the regex fails to match in the first alternation (everything before the pipe), we must have decreased our counter to zero, meaning there are no characters inside the second token. Instead, we look at the second part of the pattern, #.*. This simply replaces everything after the first # with $'$1$2. Since there are no backreferences created by this alternation, and there is nothing to the right of the match (.* matches until the end of the string), we terminate the match and return the result.

//a

This is just a pointer to the previous line, ensuring we continue to execute the regex substitution until it fails to match any more.

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

jq 1.5: 91 characters

(87 characters code + 4 characters command line option.)

.+. as$t|[range(1;length)|select($t[:.]==$t[-.:])]|(max//0)as$i|[range($i)|$t[$i:]]|add

Sample run:

bash-4.3$ jq -R -r -f judy.jq <<< 'underground'
undergroundergroundergrounderground
\$\endgroup\$
3
\$\begingroup\$

rs, 51 48 bytes

(.+)/\1 \1
(.+)(.+) .+\1$/\1(\2)^^((^^\1_))
 .*/

TAKE THAT, RETINA AND SED!!!!! ;)

Cut off 3 bytes thanks to @randomra.

Live demo and test cases.

Note that the jackhammer test case is not there. There's a bug in the handling of spaces in the web interface that causes it to print incorrect output. The offline version of rs handles it correctly.

51-byte version:

(.+)/\1 \1
^(.+)(.+) (.+)\1$/\1(\2)^^((^^\1_))
 .*/

Live demo and test cases for original.

\$\endgroup\$
  • \$\begingroup\$ @randomra Updated. Thanks! \$\endgroup\$ – kirbyfan64sos Jul 16 '15 at 22:14
2
\$\begingroup\$

JavaScript (ES6), 95 bytes

f=s=>{for(e=i=s.length;i&&e;)s+=s.slice(--i).repeat(!(e=!s.endsWith(s.slice(0,i)))*i);return s}

Demo

Firefox only for now:

f = s => {
  for (e = i = s.length; i && e;) s += s.slice(--i).repeat(!(e = !s.endsWith(s.slice(0, i))) * i);
  return s
}

console.log = x => X.innerHTML += x + '\n';

console.log(f('onion'));
console.log(f('jackhammer'));
console.log(f('abracadabra'));
console.log(f(''));
console.log(f('zvioz'));
console.log(f('alfalfa'));
console.log(f('aaaa'));
<pre id=X></pre>

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

JavaScript (ES6), 82 bytes

g=(s,i=t=s.length)=>s.endsWith(c=s.slice(0,--i))?c+s.slice(i-t).repeat(i+1):g(s,i)

[Deleted my original answer, because I've now learned ES6 and was interested in finding a recursive solution to this challenge]

Example

g=(s,i=t=s.length)=>s.endsWith(c=s.slice(0,--i))?c+s.slice(i-t).repeat(i+1):g(s,i)

console.log(g('onion'));
console.log(g('jackhammer'));
console.log(g('abracadabra'));
console.log(g(''));
console.log(g('zvioz'));
console.log(g('alfalfa'));
console.log(g('aaaa'));

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

CoffeeScript + ES6, 77 bytes

Same approach as my JavaScript answer.

f=(s,e=i=s.length)->s+=s[i..].repeat !(e=!s.endsWith s[...i])*i while--i&&e;s
\$\endgroup\$
0
\$\begingroup\$

C

#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {
    char *str   = NULL;
    char *p     = NULL;
    int len     = 0 ;
    int i       = 0;
    int j       = 0;
    int k       = 0;
    int loop    = 0;

    if (argc == 1 )
        return 0;

    str = argv[1];
    len = strlen(str);

    if (len %2) {
        loop = len/2 + 1;
    }
    else {
        loop = len/2;
    }


    p = &str[len/2];
    for (i = 0; i < loop ; i++) {
        if (str[k] == *(p++)) {
            k++;
        }
        else
            k = 0;
    }

    printf("k = %d\n", k);
    printf("%s", str);
    p = &str[k];
    for (j =0; j < k ; j++) {
        printf("%s", p);
    }
    return 0;
}

Golfed: 195 bytes - GCC

main(int c,char**a){
char *s=a[1],*p;int i=0,j=0,k=0,z,l=strlen(a[1]);
z=l%2?-~(l/2):l/2;p=&s[l/2];
for(;i<z;i++)k=s[k]==*(p++)?-~k:0;
printf("k=%d\n",k);puts(s);p= &s[k];
for(;j<k;j++)puts(p);}
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! This question is code golf, so I suggest that you "golf" your code by removing unnecessary whitespace, etc., and then include the byte count of your code in the title of your post along with the language. \$\endgroup\$ – lirtosiast Jul 15 '15 at 23:08
  • 1
    \$\begingroup\$ Got it. Thank you for the direction. I will keep it in mind next time. \$\endgroup\$ – Alam Jul 16 '15 at 3:51
  • \$\begingroup\$ It's not too late to "golf" it. If you click on the "edit" button underneath your answer, you could still remove the unnecessary whitespace and add a byte count. \$\endgroup\$ – DJMcMayhem Jul 17 '15 at 19:47
  • \$\begingroup\$ Isn't int implicit in (sufficiently old versions of) C? \$\endgroup\$ – Angew Jul 18 '15 at 11:56
0
\$\begingroup\$

Groovy 75 57 55 bytes

f={w->x=w;w.find{x-=it;!w.indexOf(x)};w+(w-x)*x.size()}

Amazing how coming back to something the day after can help

Ungolfed:

f = {w ->

//Set x equal to w
    x=w

//Loop through the characters of w until we return true
    w.find {

//set x equal to x minus the first instance of the current character, i.e.     the word minus the first character
        x-=it

//Returns the index of the first occurance of the string of chars x, when this is 0 (false) we want to return true, so negate it
        !w.indexOf(x)
    }

//When we've escaped the loop, if we've found a match return the word plus the word minus the match multiplied by the lengh of the match.
    w+(w-x)*x.size()     
}
\$\endgroup\$
-1
\$\begingroup\$

In case somebody needs the code in JS to test it. Note: I traversed the string from end to increase efficiency:

"use strict";

var garlandify = function(inputString){
    var stringLength = inputString.length;  
    var savedString = inputString;

    for( var i=1; i<stringLength; i++ ){
         var endIndex = Math.abs(i) * -1;       
         if( inputString.startsWith( inputString.substr(endIndex) ) ){
              for( var j=1; j<=i; j++){
                  savedString += inputString.substr(i, stringLength );
              }
              console.log(savedString);         
         }  
    }
};

garlandify("onion");
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to the Programming Puzzles & Code Golf stack exchange! You don't need to worry about efficiency at all for code-golf, just the length of your program. So the slow, inefficient version may well be the best here (it can make a refreshing change from "real work"!). So remove the unnecessary whitespace, and use single-letter variable names - then read Tips for golfing in JavaScript. I think there's much you can do to golf this - but we do like to see the ungolfed, commented version if your algorithm is clever. Have fun! \$\endgroup\$ – Toby Speight Jul 16 '15 at 18:06

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.