Bring out the inner llama of a sentence

Question

Your objective is to take input like

Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good.

and create an array of the indexes of the string where the letters that make up the word "Llama" appear (one of each in order). For example, let me show the letters pointed at with carets to show the indexes:

Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good.
                                            ^                      ^        ^                            ^        ^

So the array would look like:

[44, 67, 76, 105, 114]

(If your application uses a indexing that's not 0-based, the numbers will look different. That's fine.)

If the text has no llama, then the array should be empty, nil, null, or undefined.

Any code language is accepted. This is a code-golf contest, so the least characters win!

Answer 1

Perl, 52 bytes

The solution is provided as function that takes the string as argument and returns a list of positions.

• One-based positions, case-sensitive search, without newlines: 52 bytes

  sub l{pop=~/(l).*?(l).*?(a).*?(m).*?(a)/;@+[1..$#+]}
  

  The case-sensitive search returns an empty array in the example of the question, because after matching the first three letters the lowercase letter m is missing in the input text.

• Support of newlines: + 1 byte = 53 bytes

  sub l{pop=~/(l).*?(l).*?(a).*?(m).*?(a)/s;@+[1..$#+]}
  

  The text can now span several lines.

• Case-insensitive search: + 1 byte = 54 bytes

  sub l{pop=~/(l).*?(l).*?(a).*?(m).*?(a)/si;@+[1..$#+]}
  

  Now the example in the question reports a list of index positions, they are one-based numbers:

  [45 68 77 106 115]
  

• Zero-based positions: + 9 bytes = 63 bytes

  sub l{pop=~/(l).*?(l).*?(a).*?(m).*?(a)/si;map{$_-1}@+[1..$#+]}
  

  Result for the example in the question:

  [44 67 76 105 114]
  

Ungolfed:

The latter variant includes more or less the other variants.

sub l {
    # pop() gets the last argument 
    pop() =~ /(l).*?(l).*?(a).*?(m).*?(a)/si;
    # the letters inbetween are matched against ".*?",
    # the non-greedy variant of ".*". Thus ".*?"
    # matches only as few as possible characters.
    # The modifier /i controls the case-sensitivity
    # and means ignore case. Without the case matters.
    # Modifier /s treats the string as single line,
    # even if it contains newlines.
    map { $_-1 }   # subtract 1 for zero-based positions
        @+[1..$#+]
    # Array @+ contains the end-positions of the last
    # submatches, and of the whole match in the first position.
    # Therefore the first value is sliced away.
    # @+ is available since Perl 5.6.
}

# test
my @result = l(<<"END_STR");
Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good.
END_STR
print "[@result]\n";

Answer 2

sed, 299+1

Yes, sed can find a llama. No, sed can't do math. This is the longest answer so far, at 299+1 characters, because I had to teach sed to count.

This answer requires a sed with extended regular expressions (sed -E or sed -r). I used OpenBSD sed(1). Input is one string per line. (Therefore, the string may not contain a newline.) Output is a line of numbers, or nothing.

Usage (+1 character for -r):

$ echo 'All arms on all shoulders may ache.' | sed -rf llama.sed
1 2 12 26 30 

Source code (299 characters):

s/%/z/g
s/(.*)[Aa]/\1%/
s/(.*)[Mm](.*%)/\1%\2/
s/(.*)[Aa]((.*%){2})/\1%\2/
s/(.*)[Ll]((.*%){3})/\1%\2/
s/(.*)[Ll]((.*%){4})/\1%\2/
/(.*%){5}/!d
s/[^%]/z/g
:w
s/(z*)%/\10 z\1/
s/z*$//
s/z0/1/
s/z1/2/
s/z2/3/
s/z3/4/
s/z4/5/
s/z5/6/
s/z6/7/
s/z7/8/
s/z8/9/
s/([0-9]z*)z9/z\10/g
s/(z*)z9/1\10/
/[%z]/bw

The program first replaces the llama with five %. (All % in this program are literal.) The first command s/%/z/g changes any % to z in the input line. The next five commands find the llama, so All arms on all shoulders may ache. becomes A%% arms on %ll shoulders %ay %che. Because each .* is greedy, I always finds the llama on the right: llama llama would become llama %%%%%. If I can't get five %, then /(.*%){5}/!d deletes the input line and skips the next commands.

s/[^%]/z/g changes every character but % to z. Then I enter a loop. s/(z*)%/\10 z\1/ changes the first % to 0, copies zero or more z from left to right, and adds one more z to right. This is so the number of z will equal the index. For example, zz%zzz%... becomes zz0 zzzzzzzz%... because the first % was at index 2, and the next % is at index 8. s/z*$// removes extra z from the end of the string.

The next eleven commands count z by removing each z and counting up from 0. It counts like zzz0, zz1, z2, 3. Also, 1zzzz9 becomes z1zzz0 (later 23), or zzzz9 becomes 1zzz0 (later 13). This loop continues until there are no more % or z.

Answer 3

CJam - 33

lel"llama"{1$#)_T+:T\@>}/;]___|=*

It gets the 1-based indexes (2 more bytes for 0-based)

Explanation:

l reads a line from the input (replace with q for whole input)
el converts to lowercase
"llama"{...}/ executes the block for each "llama" letter
1$ copies the current string
# finds the index of the letter
)_ increments and duplicates
T+:T adds T (initially 0), updates T and leaves it on the stack
\@ swaps items around, now we have current-T, index, string
> slices the string starting at the index
; pops the remaining string
] gathers the indexes in an array
At this point we have all the 1-based indexes; iff any letter was not found, the array will have duplicates.
___ makes 3 more copies of the array
| (with 2 array copies) removes duplicates
= compares, resulting in 0 if there were duplicates or 1 if not
* multiplies the array 0 or 1 times accordingly

Answer 4

Fortran - 154 148

Fortran sucks at golfing, but just to prove that parsing strings can be done in a math-based language, I did it:

function f result(r);integer::r(5),j=1;do i=1,len(s);if(s(i:i)==a(j:j).or.s(i:i)==b(j:j)) then;r(j)=i;j=j+1;endif;enddo;if(any(r==0))r=0;endfunction

I saved a few characters by eliminating the not-required f at the end of endfunction and used if(any(r==0)) instead of if(.not.all(r>0)).

This requires:

1. s to be the string with text
2. a to be the lower-case test (i.e., llama)
3. b to be the upper-case test (i.e., LLAMA)

The full, un-golfed program is

program find_llama
   character(len=123) :: s = "Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good."
   character(len=5) :: a="llama",b="LLAMA"

   print *,f()
 contains
   function f result(r)
     integer::r(5),j=1
     do i=1,len(s)
        if(s(i:i)==a(j:j).or.s(i:i)==b(j:j)) then
           r(j)=i
           j=j+1
        endif
     enddo
     if(any(r==0)) r=0
   end function
end program find_llama

Answer 5

Ruby, 56 65 63

Edit: +9 characters so that it is case-insensitive.

Defines a function (lambda, technically) f.

f=->s{i=0;'LLAMA'.chars.map{|c|i=s.upcase.index(c,i+1)||break}}

Returns nil if there is no llama. If it has to be [] (empty array), then just add ||[] before the last } for a total of 4 extra characters.

Readable version:

innerLlama = -> str{
    index = 0;
    str.downcase!
    arr = 'llama'.each_char.map{|char|
        index = str.index(char, index + 1)
        break unless index
    }
    # uncomment this line for empty array on failure
    #arr || []
}

Answer 6

C# - 119

Takes string, outputs array. Null if no llama in string.

int[]a(string s){var i=0;var o="llama".Select((x,y)=>i=s.IndexOf(x,y>0?i+1:0));return o.All(x=>x>=0)?o.ToArray():null;}

Answer 7

C - 53

Compile with:

gcc -D L=\"llama\" -D W=\"Lie\ is\ good.\ \ I\ just\ ate\ a\ bunch\ of\ pies\ early\ this\ morning.\ \ Actually,\ it\ was\ closer\ to\ the\ afternoon.\ \ Mornings\ are\ good.\"

I tested this compile command with cygwin's gcc. Other environments might handle spaces, and other special characters differently.

The 0-based result is stored into array r. Its contents are undefined if there is no llama in the string.

• Case-sensitive (53)

  i,m,r[5];main(){for(;W[i];i++)W[i]==L[m]?r[m++]=i:i;}

• Case-insensitive (58)

  i,m,r[5];main(){for(;W[i];i++)(W[i]|96)==L[m]?r[m++]=i:i;}

Answer 8

Python, 100

I am the worst golfer ever. :P

Thanks to @xnor for shaving off 6 bytes.

g,n,o='llama',0,[]
for i in s:
 if g:exec("o+=[n];g=g[1:];"*(i.lower()==g[0])+"n+=1")
o*=len(o)>4

o contains the array after.

EDIT: Fixed.

EDIT 2: len(g) to g, o==5 to o>4 as per @xnor's suggestions.

EDIT 3: @WolframH fixed it.

Answer 9

JavaScript (ECMAScript 6) - 68 Characters

(/((((.*l).*l).*a).*m).*a/.exec(s)||[]).map(x=>x.length-1).reverse()

Assumes that the string to test is in the variable s. If you want to turn it into a function then prepend f=s=> (for an additional 5 characters).

Outputs:

[]

Case Insensitive - 69 Characters

(/((((.*l).*l).*a).*m).*a/i.exec(s)||[]).map(x=>x.length-1).reverse()

Outputs:

[68, 80, 93, 105, 114]

Case Insensitive & First Match - 74 Characters

(/((((.*?l).*?l).*?a).*?m).*?a/i.exec(s)||[]).map(x=>x.length-1).reverse()

Outputs:

[44, 67, 76, 105, 114]

Answer 10

Python 71

Assumes input in s. Output in o.

F=s.lower().find
o=F('l'),
for c in'lama':o+=F(c,o[-1]+1),
o*=min(o)>=0

Edit: Changed from lists to tuples to save 2 bytes.

Answer 11

Python 100

import re
x=input()
print[re.search(r"l.*?(l).*?(a).*?(m).*?(a)",x,re.I).start(i) for i in range(5)]

Sample:

in  = Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good.
out = [44, 67, 76, 105, 114]
in[out] = ['l', 'l', 'a', 'M', 'a']

Answer 12

Haskell, 111

import Data.Char
l i(a:as)t@(b:bs)|a==b=i:l(i+1)as bs|True=l(i+1)as t
l _ _ _=[]
r s=l 0(map toUpper s)"LLAMA"

Ungolfed:

import Data.Char

llama :: Int -> String -> String -> [Int]
llama i (a:as) t@(b:bs)
  | a==b      = i : llama (i+1) as bs
  | otherwise = llama (i+1) as t
llama _ _ _ = []

runme :: String -> [Int]
runme s = llama 0 (map toUpper s) "LLAMA"

Example:

*Main> r "Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good."
[44,67,76,105,114]

Answer 13

Matlab, 61 96

Searches the string and replaces everything up to each match with gibberish before searching for next character. Will leave s undefined if an the word does not occur.

t='llama';for q=1:5;s(q)=min(regexpi(z,t(q))),z(1:s(q))=0;end

Note that the charcount could be reduced if case sensitivity is allowed.

Previous versions

 try;t='llama';for q=1:length(t);s(q)=find(lower(z)==t(q),1);z(1:s(q))=ones(1,s(q));end;catch;end

Searches the string and replaces everything up to each match with gibberish before searching for next character. Error handling (try-catch-end) could maybe be dropped, then the program would crash (but s would be undefined as required) if llama not found.

Implementation:

>> z='Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good.';
>> try;t='llama';for q=1:length(t);s(q)=find(lower(z)==t(q),1);z(1:s(q))=ones(1,s(q));end;catch;end
>> s
s =

    45    68    77   106   115

Without error handling:

t='llama';for q=1:length(t);s(q)=find(lower(z)==t(q),1);z(1:s(q))=ones(1,s(q));end

Answer 14

Language Java

 final int[] wordIndexInSentence(String sentence, String word)
  {
    final int[] returnArr = new int[word.length()];
    int fromIndex = 0;
    word = word.toUpperCase();
    sentence = sentence.toUpperCase();
    for (int i = 0; i < word.length(); i++)
    {
      final char c = word.charAt(i);
      returnArr[i] = sentence.indexOf(c, fromIndex);
      fromIndex = returnArr[i] > 0 ? returnArr[i] + 1 : fromIndex;
    }
    return returnArr;
  }

Answer 15

Rebol, 97

f: func[s][a: copy[]foreach n"llama"[if none? s: find s n[return[]]append a index? s s: next s]a]

Usage example in Rebol console:

>> f "Pie is good.  I just ate a bunch of pies early this morning.  Actually, it was closer to the afternoon.  Mornings are good." 
== [45 68 77 106 115]

>> f "nearly llami"       
== []

>> f "Llama"
== [1 2 3 4 5]

>> f reverse "llama"
== []

Rebol uses 1-based indexing. Returns empty list [] if no llama sequence found (case insensitive).

Ungolfed:

f: func [s] [
    a: copy []
    foreach n "llama" [
        if none? s: find s n [return []]
        append a index? s
        s: next s
    ]
    a
]

Answer 16

Python (70)

r=[];c=-1
for x in'llama':c=s.lower().find(x,c+1);r+=[c]
r*=1-(-1in r)

We search of each character in 'llama' in turn, starting after the location of the previously-found character. If no character is found, c becomes the default value of -1, in which case the last line turns r into the empty list.

Edit: Found out that str.find(s,...) can be invoked as s.find(...), saving 4 characters.

Answer 17

OpenEuphoria, 147128

I have two examples. First, the shortest:

object t=and_bits(gets(0),#DF),L="LLAMA",i=0,X={}for j=1 to 5 do 
i=find(L[j],t,i+1)X&=i 
end for 
if find(0,X) then X={} end if?X

I can get it down to 126 characters if I use "or" instead of "and" like the C version does up above. However, this also matches the string ''!-! as llama. Uncommon, but still a possible error.

object t=or_bits(gets(0),96),L="llama",i=0,X={}for j=1 to 5 do 
i=find(L[j],t,i+1)X&=i 
end for 
if find(0,X) then X={} end if?X

And then the version using regular expressions:

include std/regex.e
include std/sequence.e
include std/utils.e
object X=regex:find(new("(?i)(l).*?(l).*?(a).*?(m).*?(a)"),gets(0))
? iff(atom(X),{},vslice(X[2..6],2))

Both take input from STDIN and post to STDOUT.

EDIT: Shorter regex example:

include std/regex.e
include std/sequence.e
object X=regex:find(new("(?i)(l).*?(l).*?(a).*?(m).*?(a)"),gets(0))
if atom(X)then?{}else?vslice(X[2..6],2)end if

Answer 18

Powershell - 121 85

I'm still practicing with Powershell, expect this could be improved

$s contains the string, result is in array $a

Original version

$a=@();$w="llama";$n=$c=0;foreach ($i in $s.tochararray()) {if ($i -eq $w[$n]) {$a+=$c;$n+=1} $c+=1};$a*=$a.length -gt 4

Ungolfed

$a=@()
$w="llama"
$n=$c=0
foreach ($i in $s.tochararray()) {
 if ($i -eq $w[$n]) {
  $a+=$c
  $n+=1
 } $c+=1
}
$a*=$a.length -gt 4

New version, with massive thanks to @goric

$a=@();$n=$c=0;[char[]]$s|%{if($_-eq"llama"[$n]){$a+=$c;$n++}$c++};$a*=$a.length-gt4

Answer 19

Jelly, 16 bytes

ŒlẹⱮ“ṫɠ»Ż>ƇḢ¥@\Ḋ

Try it online!

How it works

ŒlẹⱮ“ṫɠ»Ż>ƇḢ¥@\Ḋ - Main link. Takes a string on the left
Œl               - Lowercase
    “ṫɠ»         - Compressed string: "llama"
   Ɱ             - For each character in "llama":
  ẹ              -   Find the indexes of that character in the input
        Ż        - Prepend 0
            ¥    - Last 2 links as a dyad f(x, y):
         >Ƈ      -   Keep elements of x greater than y
           Ḣ     -   Take the first element
             @\  - Reduce the list by the f(y, x)
               Ḋ - Dequeue

Answer 20

PHP

no PHP answer yet? I think a language heavily string-oriented can beat at least a math-based one

function x($s){$i=$j=0;$r=str_split('llama');$s=strtolower($s);while($i<strlen($s)){if($s[$i]==$r[$j]){$r[$j]=$i;$j++;if($j>4)return$r;}$i++;}return[];}
  

152 against fortran 154, job done :P

ungolfed

function x($s){
    $i=$j=0;$r=str_split('llama');
    $s=strtolower($s);
    while($i<strlen($s)){
        if ($s[$i]==$r[$j]){
            $r[$j]=$i;
            $j++;
            if($j>4)
                return $r;
        }
        $i++;
    }
    return[];
}

if the caller always passes a lowercase string, it lowers to 137

Answer 21

JavaScript, 122 115

function(s,b){z=[];for(i=0;i<5;i++){z.push(b=s.toLowerCase().indexOf("llama"[i],++b))};return z.indexOf(-1)<0?z:[]}

Defines a function that takes a string as its only argument (second arg is a cheap var) and returns either an empty array or a 5-element array.

Drops to 108 if I take the input on a single char variable (s) and leave the output in another (b):

var b=((z="llama".split('').map(function(a){return (b=s.toLowerCase().indexOf(a,++b))})).indexOf(-1)<0?z:[])

Edit: Swapped out map for for loop.

Answer 22

APL, 47

+\↑⊃{a s←⍵⋄~⍺∊s:⍬⍬⋄a,←n←s⍳⍺⋄a(n↓s)}/'amall',⊂⍬⍞

Not the shortest code, but quite warped, in an APL way.

Explanation

'amall',⊂⍬⍞ Make an array of 6 elements: the letters 'amall' and a subarray of 2 elements, themselves subarrays: the empty array and a line of characters read from input.

{...}/... Reduce (right-fold) the 6-element array using the provided function.

a s←⍵ Decompose the right argument into the array of indices and the remaining substring (initially the empty array and the full string.)

~⍺∊s:⍬⍬ If the substring does not contain the next letter ⍺ stop the computation and return the empty array.

a,←n←s⍳⍺ Otherwise, find its position, call it n, and append it to the array of indices.

a(n↓s) Make and return an array of 2 elements: the extended array of indices and the remaining substring.

+\↑⊃... Unpack the output of the folding, take the first element (the array of indices) and scan it with addition, to turn relative offsets into absolute ones.

Examples

      +\↑⊃{a s←⍵⋄~⍺∊s:⍬⍬⋄a,←n←s⍳⍺⋄a(n↓s)}/'amall',⊂⍬⍞
All cats meow aloud.
2 3 6 10 15

 

      +\↑⊃{a s←⍵⋄~⍺∊s:⍬⍬⋄a,←n←s⍳⍺⋄a(n↓s)}/'amall',⊂⍬⍞
Some cats purr instead.
 

Answer 23

Julia, 76

Another regex example using Julia language.

f(s)=(m=match(r"(?i)(l).*?(l).*?(a).*?(m).*?(a)",s);m==nothing?m:m.offsets)

Answer 24

ARM Thumb-2 machine code, 42 bytes

Machine code (little endian hexdump):

2500 a208 f812 3b01 b15b 5d44 b144 3501
42a3 d003 f084 0420 42a3 d1f6 c120 e7f1
2100 4770 6c6c 6d61 0061

Commented assembly:

        .syntax unified
        .arch armv6t2
        .thumb
        .globl llama
        .thumb_func
        // Input:
        //    r0: null terminated string
        //    r1: output uint32_t array, must be 4 byte aligned
        // Output:
        //    if it matches, the ONE-INDEXED offsets are stored in r1
        //    otherwise, r1 is set to NULL. (Elements are still
        //    modified).
llama:
        // index
        movs    r5, #0
        // lookup table
        adr     r2, .LLAMA
        // loop through "llama"
.Llama:
        // Read byte from llama string, increment
        ldrb    r3, [r2], #1
        // end at null terminator
        cbz     r3, .LlAmA
.LLama:
        // r4 = str[r5]
        ldrb    r4, [r0, r5]
        // if we reach the null terminator, we don't have a match.
        cbz     r4, .LlaMa
        // increment r5 (this is what makes it one indexed)
        adds    r5, #1
        // check for a direct match
        cmp     r3, r4
        beq     .LLAma
        // flip the case by xoring 1<<5
        eor     r4, r4, #0b00100000
        // test the case when flipped
        cmp     r3, r4
        bne     .LLama
.LLAma:
        // *r1++ = index
        stm     r1!, {r5}
        // loop indefinitely (trip condition is the first cbz)
        b       .Llama
.LlaMa:
        // If we don't have a match, set r1 to NULL.
        movs    r1, #0
.LlAmA:
        // Otherwise, return.
        bx      lr
.LLAMA:
        .asciz  "llama"