Search a list: Difference between revisions
No edit summary |
(Added Forth) |
||
| Line 714: | Line 714: | ||
4 |
4 |
||
=={{header|Forth}}== |
|||
{{works with|4tH|3.61.5}} |
|||
<lang forth>include lib/row.4th |
|||
create haystack |
|||
," Zig" ," Zag" ," Wally" ," Ronald" ," Bush" ," Krusty" ," Charlie" |
|||
," Bush" ," Boz" ," Zag" NULL , |
|||
does> |
|||
dup >r 1 string-key row 2>r type 2r> ." is " |
|||
if r> - ." at " . else r> drop drop ." not found" then cr |
|||
; |
|||
s" Washington" haystack s" Bush" haystack</lang> |
|||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
| Line 753: | Line 766: | ||
end program main |
end program main |
||
</lang> |
</lang> |
||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
<lang gap># First position is built-in |
<lang gap># First position is built-in |
||
Revision as of 12:04, 20 May 2012
You are encouraged to solve this task according to the task description, using any language you may know.
Find the index of a string (needle) in an indexable, ordered collection of strings (haystack). Raise an exception if the needle is missing. If there is more than one occurrence then return the smallest index to the needle.
As an extra task, return the largest index to a needle that has multiple occurrences in the haystack.
ACL2
<lang lisp>(defun index-of-r (e xs i)
(cond ((endp xs) nil)
((equal e (first xs)) i)
(t (index-of-r e (rest xs) (1+ i)))))
(defun index-of (e xs)
(index-of-r e xs 0))</lang>
ActionScript
Using the built-in Error class
<lang ActionScript>var list:Vector.<String> = Vector.<String>(["Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Boz", "Zag"]); function lowIndex(listToSearch:Vector.<String>, searchString:String):int { var index:int = listToSearch.indexOf(searchString); if(index == -1) throw new Error("String not found: " + searchString); return index; }
function highIndex(listToSearch:Vector.<String>, searchString:String):int { var index:int = listToSearch.lastIndexOf(searchString); if(index == -1) throw new Error("String not found: " + searchString); return index; }</lang>
Using a custom error
In StringNotFoundError.as: <lang ActionScript>package { public class StringNotFoundError extends Error { public function StringNotFoundError(message:String) { super(message); } } }</lang> In a separate file: <lang ActionScript>import StringNotFoundError; var list:Vector.<String> = Vector.<String>(["Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Boz", "Zag"]); function lowIndex(listToSearch:Vector.<String>, searchString:String):int { var index:int = listToSearch.indexOf(searchString); if(index == -1) throw new StringNotFoundError("String not found: " + searchString); return index; }
function highIndex(listToSearch:Vector.<String>, searchString:String):int { var index:int = listToSearch.lastIndexOf(searchString); if(index == -1) throw new StringNotFoundError("String not found: " + searchString); return index; } </lang>
Ada
<lang ada>with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Text_IO; use Ada.Text_IO;
procedure Test_List_Index is
Not_In : exception;
type List is array (Positive range <>) of Unbounded_String;
function Index (Haystack : List; Needle : String) return Positive is
begin
for Index in Haystack'Range loop
if Haystack (Index) = Needle then
return Index;
end if;
end loop;
raise Not_In;
end Index;
-- Functions to create lists
function "+" (X, Y : String) return List is
begin
return (1 => To_Unbounded_String (X), 2 => To_Unbounded_String (Y));
end "+";
function "+" (X : List; Y : String) return List is
begin
return X & (1 => To_Unbounded_String (Y));
end "+";
Haystack : List := "Zig"+"Zag"+"Wally"+"Ronald"+"Bush"+"Krusty"+"Charlie"+"Bush"+"Bozo";
procedure Check (Needle : String) is
begin
Put (Needle);
Put_Line ("at" & Positive'Image (Index (Haystack, Needle)));
exception
when Not_In => Put_Line (" is not in");
end Check;
begin
Check ("Washington");
Check ("Bush");
end Test_List_Index;</lang> Sample output:
Washington is not in Bushat 5
ALGOL 68
Using a FORMAT "value error" exception
<lang algol68> FORMAT hay stack := $c("Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo")$;
FILE needle exception; STRING ref needle;
associate(needle exception, ref needle);
PROC index = (FORMAT haystack, REF STRING needle)INT:(
INT out;
ref needle := needle;
getf(needle exception,(haystack, out));
out
);
test:(
[]STRING needles = ("Washington","Bush");
FOR i TO UPB needles DO
STRING needle := needles[i];
on value error(needle exception, (REF FILE f)BOOL: value error);
printf(($d" "gl$,index(hay stack, needle), needle));
end on value error;
value error:
printf(($g" "gl$,needle, "is not in haystack"));
end on value error: reset(needle exception)
OD
)</lang>
Output:
Washington is not in haystack 5 Bush
Using a manual FOR loop with no exception
<lang algol68> []STRING hay stack = ("Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo");
PROC index = ([]STRING hay stack, STRING needle)INT:(
INT index;
FOR i FROM LWB hay stack TO UPB hay stack DO
index := i;
IF hay stack[index] = needle THEN
found
FI
OD;
else:
LWB hay stack - 1
EXIT
found:
index
);
test:(
[]STRING needles = ("Washington","Bush");
FOR i TO UPB needles DO
STRING needle := needles[i];
INT result = index(hay stack, needle);
IF result >= LWB hay stack THEN
printf(($d" "gl$, result, needle))
ELSE
printf(($g" "gl$,needle, "is not in haystack"))
FI
OD
)</lang>
Output:
Washington is not in haystack 5 Bush
AutoHotkey
<lang AutoHotkey>haystack = Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo needle = bush, washington Loop, Parse, needle, `, {
If InStr(haystack, A_LoopField) MsgBox, % A_LoopField Else MsgBox % A_LoopField . " not in haystack"
}</lang>
AWK
If we use an awk array indexed with "the order" of the string, to check if the needle is in the haystack we must walk the whole array; if we use the string itself as index (in awk index for an array is indeed an hash), and put its "index" (order number in the list) as associated value, we can fastly check if the needle is in the haystack. But we can't fastly use its order number to get the string value at that position.
In the following implementation we can reach the strings by numeric index with the array haystack_byorder (so, e.g. haystack_byorder[4] gives Bush), and know the "position" of the needle (if it exists) using it as string index for the array haystack, as example does. (Beware: this method does not work when there are duplicates!)
<lang awk>#! /usr/bin/awk -f BEGIN {
# create the array, using the word as index...
words="Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo";
split(words, haystack_byorder, " ");
j=0;
for(idx in haystack_byorder) {
haystack[haystack_byorder[idx]] = j; j++;
}
# now check for needle (we know it is there, so no "else")...
if ( "Bush" in haystack ) {
print "Bush is at " haystack["Bush"];
}
# check for unexisting needle
if ( "Washington" in haystack ) {
print "impossible";
} else {
print "Washington is not here";
}
}</lang>
BASIC
<lang qbasic>DATA foo, bar, baz, quux, quuux, quuuux, bazola, ztesch, foo, bar, thud, grunt DATA foo, bar, bletch, foo, bar, fum, fred, jim, sheila, barney, flarp, zxc DATA spqr, wombat, shme, foo, bar, baz, bongo, spam, eggs, snork, foo, bar DATA zot, blarg, wibble, toto, titi, tata, tutu, pippo, pluto, paperino, aap DATA noot, mies, oogle, foogle, boogle, zork, gork, bork
DIM haystack(54) AS STRING DIM needle AS STRING, found AS INTEGER, L0 AS INTEGER
FOR L0 = 0 TO 54
READ haystack(L0)
NEXT
DO
INPUT "Word to search for? (Leave blank to exit) ", needle
IF needle <> "" THEN
FOR L0 = 0 TO UBOUND(haystack)
IF UCASE$(haystack(L0)) = UCASE$(needle) THEN
found = 1
PRINT "Found "; CHR$(34); needle; CHR$(34); " at index "; LTRIM$(STR$(L0))
END IF
NEXT
IF found < 1 THEN
PRINT CHR$(34); needle; CHR$(34); " not found"
END IF
ELSE
EXIT DO
END IF
LOOP</lang>
Sample output:
Word to search for? (Leave blank to exit) foo Found "foo" at index 0 Found "foo" at index 8 Found "foo" at index 12 Found "foo" at index 15 Found "foo" at index 27 Found "foo" at index 34 Word to search for? (Leave blank to exit) bar Found "bar" at index 1 Found "bar" at index 9 Found "bar" at index 13 Found "bar" at index 16 Found "bar" at index 28 Found "bar" at index 35 Word to search for? (Leave blank to exit) baz Found "baz" at index 2 Found "baz" at index 29 Word to search for? (Leave blank to exit)
C
<lang c>#include <stdio.h>
- include <string.h>
const char *haystack[] = {
"Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Boz", "Zag", NULL
};
int search_needle(const char *needle, const char **hs) {
int i = 0;
while( hs[i] != NULL ) {
if ( strcmp(hs[i], needle) == 0 ) return i;
i++;
}
return -1;
}
int search_last_needle(const char *needle, const char **hs) {
int i, last=0;
i = last = search_needle(needle, hs);
if ( last < 0 ) return -1;
while( hs[++i] != NULL ) {
if ( strcmp(needle, hs[i]) == 0 ) {
last = i;
}
}
return last;
}
int main() {
printf("Bush is at %d\n", search_needle("Bush", haystack));
if ( search_needle("Washington", haystack) == -1 )
printf("Washington is not in the haystack\n");
printf("First index for Zag: %d\n", search_needle("Zag", haystack));
printf("Last index for Zag: %d\n", search_last_needle("Zag", haystack));
return 0;
}</lang>
Output:
Bush is at 4 Washington is not in the haystack First index for Zag: 1 Last index for Zag: 9
C++
The following code shows three different ways to solve the task.
<lang cpp>#include <string>
- include <algorithm>
- include <iterator>
- include <cstddef>
- include <exception>
- include <iostream>
// an exception to throw (actually, throwing an exception in this case is generally considered bad style, but it's part of the task) class not_found: public std::exception { public:
not_found(std::string const& s): text(s + " not found") {}
char const* what() const throw() { return text.c_str(); }
~not_found() throw() {}
private:
std::string text;
};
// needle search function, C-style interface version using standard library std::size_t get_index(std::string* haystack, int haystack_size, std::string needle) {
std::size_t index = std::find(haystack, haystack+haystack_size, needle) - haystack; if (index == haystack_size) throw not_found(needle); else return index;
}
// needle search function, completely generic style, needs forward iterators // (works with any container, but inefficient if not random-access-iterator) template<typename FwdIter>
typename std::iterator_traits<FwdIter>::difference_type fwd_get_index(FwdIter first, FwdIter last, std::string needle)
{
FwdIter elem = std::find(first, last, needle); if (elem == last) throw not_found(needle); else return std::distance(first, elem);
}
// needle search function, implemented directly, needs only input iterator, works efficiently with all sequences template<typename InIter>
typename std::iterator_traits<InIter>::difference_type generic_get_index(InIter first, InIter last, std::string needle)
{
typename std::iterator_traits<InIter>::difference_type index = 0;
while (first != last && *first != needle)
{
++index;
++first;
}
if (first == last)
throw not_found(needle);
else
return index;
}
// ----------------------------------------------------------------------------------------------------------------------------------
// a sample haystack (content copied from Haskell example) std::string haystack[] = { "Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Bozo" };
// some useful helper functions template<typename T, std::size_t sz> T* begin(T (&array)[sz]) { return array; } template<typename T, std::size_t sz> T* end(T (&array)[sz]) { return array + sz; } template<typename T, std::size_t sz> std::size_t size(T (&array)[sz]) { return sz; }
// test function searching a given needle with each of the methods void test(std::string const& needle) {
std::cout << "-- C style interface --\n";
try
{
std::size_t index = get_index(haystack, size(haystack), needle);
std::cout << needle << " found at index " << index << "\n";
}
catch(std::exception& exc) // better catch standard exceptions as well; me might e.g. run out of memory
{
std::cout << exc.what() << "\n";
}
std::cout << "-- generic interface, first version --\n";
try
{
std::size_t index = fwd_get_index(begin(haystack), end(haystack), needle);
std::cout << needle << " found at index " << index << "\n";
}
catch(std::exception& exc) // better catch standard exceptions as well; me might e.g. run out of memory
{
std::cout << exc.what() << "\n";
}
std::cout << "-- generic interface, second version --\n";
try
{
std::size_t index = generic_get_index(begin(haystack), end(haystack), needle);
std::cout << needle << " found at index " << index << "\n";
}
catch(std::exception& exc) // better catch standard exceptions as well; me might e.g. run out of memory
{
std::cout << exc.what() << "\n";
}
}
int main() {
std::cout << "\n=== Word which only occurs once ===\n";
test("Wally");
std::cout << "\n=== Word occuring multiple times ===\n";
test("Bush");
std::cout << "\n=== Word not occuring at all ===\n";
test("Goofy");
}</lang>
Output (note that in C++, indices start at 0):
=== Word which only occurs once === -- C style interface -- Wally found at index 2 -- generic interface, first version -- Wally found at index 2 -- generic interface, second version -- Wally found at index 2 === Word occuring multiple times === -- C style interface -- Bush found at index 4 -- generic interface, first version -- Bush found at index 4 -- generic interface, second version -- Bush found at index 4 === Word not occuring at all === -- C style interface -- Goofy not found -- generic interface, first version -- Goofy not found -- generic interface, second version -- Goofy not found
C#
<lang csharp>using System; using System.Collections.Generic;
class Program {
static void Main(string[] args) {
List<string> haystack = new List<string>() { "Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Bozo" };
foreach (string needle in new string[] { "Washington", "Bush" }) {
int index = haystack.IndexOf(needle);
if (index < 0) Console.WriteLine("{0} is not in haystack",needle);
else Console.WriteLine("{0} {1}",index,needle);
}
}
}</lang>
Clojure
<lang clojure>(let [haystack ["Zig" "Zag" "Wally" "Ronald" "Bush" "Krusty" "Charlie" "Bush" "Bozo"]]
(let [idx (.indexOf haystack "Zig")]
(if (neg? idx)
(throw (Error. "item not found."))
idx)))</lang>
Extra credit: Since Clojure vectors implement java.util.List, you can switch .indexOf for .lastIndexOf to find the highest index of your value.
Common Lisp
<lang lisp>(let ((haystack '(Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo)))
(dolist (needle '(Washington Bush))
(let ((index (position needle haystack)))
(if index
(progn (print index) (princ needle))
(progn (print needle) (princ "is not in haystack"))))))</lang>
Output:
WASHINGTON is not in haystack 4 BUSH
D
<lang d>import std.algorithm, std.range, std.string;
auto firstIndex(R, T)(R hay, T needle) {
auto i = countUntil(hay, needle);
if (i == -1)
throw new Exception("No needle found in haystack");
return i;
}
auto lastIndex(R, T)(R hay, T needle) {
return walkLength(hay) - firstIndex(retro(hay), needle) - 1;
}
void main() {
auto h = split("Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo");
assert(firstIndex(h, "Bush") == 4);
assert(lastIndex(h, "Bush") == 7);
}</lang>
Delphi
<lang Delphi> program Needle;
{$APPTYPE CONSOLE}
uses
SysUtils, Classes;
var
list: TStringList; needle: string; ind: Integer;
begin
list := TStringList.Create;
try
list.Append('triangle');
list.Append('fork');
list.Append('limit');
list.Append('baby');
list.Append('needle');
list.Sort;
needle := 'needle';
ind := list.IndexOf(needle);
if ind < 0 then
raise Exception.Create('Needle not found')
else begin
Writeln(ind);
Writeln(list[ind]);
end;
Readln; finally list.Free; end;
end. </lang> Output:
3 needle
E
<lang e>def haystack := ["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"]
/** meet the 'raise an exception' requirement */ def find(needle) {
switch (haystack.indexOf1(needle)) {
match ==(-1) { throw("an exception") }
match index { return index }
}
}
println(find("Ronald")) # prints 3 println(find("McDonald")) # will throw</lang>
Erlang
Erlang lists can be accessed with the function lists:nth/2, which starts at 1 (first element). As such Erlang can be considered 1-indexed for this problem. Note that you could set the indexing to 0 by modifying the function call in pos/2. <lang erlang>-module(index). -export([main/0]).
main() ->
Haystack = ["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"],
Needles = ["Washington","Bush"],
lists:foreach(fun ?MODULE:print/1, [{N,pos(N, Haystack)} || N <- Needles]).
pos(Needle, Haystack) -> pos(Needle, Haystack, 1). pos(_, [], _) -> undefined; pos(Needle, [Needle|_], Pos) -> Pos; pos(Needle, [_|Haystack], Pos) -> pos(Needle, Haystack, Pos+1).
print({Needle, undefined}) -> io:format("~s is not in haystack.~n",[Needle]); print({Needle, Pos}) -> io:format("~s at position ~p.~n",[Needle,Pos]).</lang>
Output:
Washington is not in haystack. Bush at position 5.
Euphoria
The find_all function from the standard library's search.e does nearly all the needed work here.There may be other ways to do this using Euphoria's various sequence searching functions as part of the standard library (std/search.e) and/or built into the language. The procedure can be made into a function to search with other strings, take user input and give output of the searched haystack.
<lang euphoria> include std/search.e include std/console.e
--the string "needle" and example haystacks to test the procedure sequence searchStr1 = "needle" sequence haystack1 = { "needle", "needle", "noodle", "node", "need", "needle ", "needle" } sequence haystack2 = {"spoon", "fork", "hay", "knife", "needle", "barn", "etcetera", "more hay", "needle", "a cow", "farmer", "needle", "dirt"} sequence haystack3 = {"needle"} sequence haystack4 = {"no", "need le s", "in", "this", "haystack"} sequence haystack5 = {"knee", "needle", "dull", "needle"} sequence haystack6 = {}
--search procedure with console output procedure haystackSearch(sequence hStack)
sequence foundNeedles = find_all(searchStr1, hStack)
puts(1,"---------------------------------\r\n")
if object(foundNeedles) and length(foundNeedles) > 0 then
printf(1, "First needle found at index %d \r\n", foundNeedles[1])
if length(foundNeedles) > 1 then
printf(1, "Last needle found at index %d \r\n", foundNeedles[length(foundNeedles)] )
for i = 1 to length(foundNeedles) do
printf(1, "Needle #%d ", i)
printf(1, "was at index %d .\r\n", foundNeedles[i])
end for
else
puts(1, "There was only one needle found in this haystack. \r\n")
end if
else
puts(1, "Simulated exception - No needles found in this haystack.\r\n")
end if
end procedure
--runs the procedure on all haystacks haystackSearch(haystack1) haystackSearch(haystack2) haystackSearch(haystack3) haystackSearch(haystack4) haystackSearch(haystack5) haystackSearch(haystack6) --wait for user to press a key to exit any_key() </lang>
Output:
--------------------------------- First needle found at index 1 Last needle found at index 7 Needle #1 was at index 1 . Needle #2 was at index 2 . Needle #3 was at index 7 . --------------------------------- First needle found at index 5 Last needle found at index 12 Needle #1 was at index 5 . Needle #2 was at index 9 . Needle #3 was at index 12 . --------------------------------- First needle found at index 1 There was only one needle found in this haystack. --------------------------------- Simulated exception - No needles found in this haystack. --------------------------------- First needle found at index 2 Last needle found at index 4 Needle #1 was at index 2 . Needle #2 was at index 4 . --------------------------------- Simulated exception - No needles found in this haystack. Press Any Key to continue...
Factor
<lang factor>: find-index ( seq elt -- i )
'[ _ = ] find drop [ "Not found" throw ] unless* ; inline
- find-last-index ( seq elt -- i )
'[ _ = ] find-last drop [ "Not found" throw ] unless* ; inline</lang>
( scratchpad ) { "a" "b" "c" "d" "c" } "c" find-index .
2
( scratchpad ) { "a" "b" "c" "d" "c" } "c" find-last-index .
4
Forth
<lang forth>include lib/row.4th
create haystack
," Zig" ," Zag" ," Wally" ," Ronald" ," Bush" ," Krusty" ," Charlie" ," Bush" ," Boz" ," Zag" NULL ,
does>
dup >r 1 string-key row 2>r type 2r> ." is " if r> - ." at " . else r> drop drop ." not found" then cr
s" Washington" haystack s" Bush" haystack</lang>
Fortran
<lang fortran> program main
implicit none
character(len=7),dimension(10) :: haystack = [ & 'Zig ',& 'Zag ',& 'Wally ',& 'Ronald ',& 'Bush ',& 'Krusty ',& 'Charlie',& 'Bush ',& 'Boz ',& 'Zag ']
call find_needle('Charlie')
call find_needle('Bush')
contains
subroutine find_needle(needle) implicit none character(len=*),intent(in) :: needle integer :: i do i=1,size(haystack) if (needle==haystack(i)) then write(*,'(A,I4)') trim(needle)//' found at index:',i return end if end do write(*,'(A)') 'Error: '//trim(needle)//' not found.' end subroutine find_needle
end program main
</lang>
GAP
<lang gap># First position is built-in haystack := Eratosthenes(10000);; needle := 8999;; Position(haystack, needle);
- 1117
LastPosition := function(L, x)
local old, new;
old := 0;
new := 0;
while new <> fail do
new := Position(L, x, old);
if new <> fail then
old := new;
fi;
od;
return old;
end;
a := Shuffle(List([1 .. 100], x -> x mod 10));
- [ 0, 2, 4, 5, 3, 1, 0, 4, 8, 8, 2, 7, 6, 3, 3, 6, 4, 4, 3, 0, 7, 1, 8, 7, 2, 4, 7, 9, 4, 9, 4, 5, 9, 9, 6, 7, 8, 2, 3,
- 5, 1, 5, 4, 2, 0, 9, 6, 1, 1, 2, 2, 0, 5, 7, 6, 8, 8, 3, 1, 9, 5, 1, 9, 6, 8, 9, 2, 0, 6, 2, 1, 6, 1, 1, 2, 5, 3, 3,
- 0, 3, 5, 7, 5, 4, 6, 8, 0, 9, 8, 3, 7, 8, 0, 4, 9, 7, 0, 6, 5, 7 ]
Position(a, 0);
- 1
LastPosition(a, 0);
- 97</lang>
See also Eratosthenes and Shuffle functions in RosettaCode.
Groovy
<lang groovy> def haystack = ["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"] def needles = ["Washington","Bush","Wally"] needles.each { needle ->
def index = haystack.indexOf(needle)
def lastindex = haystack.lastIndexOf(needle)
if (index < 0) {
assert lastindex < 0
println needle + " is not in haystack"
} else {
println "First index: " + index + " " + needle
println "Last index: " + lastindex + " " + needle
}
} </lang> Output:
Washington is not in haystack First index: 4 Bush Last index: 7 Bush First index: 2 Wally Last index: 2 Wally
Go
<lang go> package main
import "fmt"
var haystack = []string{"Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty",
"Charlie", "Bush", "Bozo", "Zag", "mouse", "hat", "cup", "deodorant", "television", "soap", "methamphetamine", "severed cat heads", "foo", "bar", "baz", "quux", "quuux", "quuuux", "bazola", "ztesch", "foo", "bar", "thud", "grunt", "foo", "bar", "bletch", "foo", "bar", "fum", "fred", "jim", "sheila", "barney", "flarp", "zxc", "spqr", ";wombat", "shme", "foo", "bar", "baz", "bongo", "spam", "eggs", "snork", "foo", "bar", "zot", "blarg", "wibble", "toto", "titi", "tata", "tutu", "pippo", "pluto", "paperino", "aap", "noot", "mies", "oogle", "foogle", "boogle", "zork", "gork", "bork", "sodium", "phosphorous", "californium", "copernicium", "gold", "thallium", "carbon", "silver", "gold", "copper", "helium", "sulfur"}
func main() {
// first task
printSearchForward("soap")
printSearchForward("gold")
printSearchForward("fire")
// extra task
printSearchReverseMult("soap")
printSearchReverseMult("gold")
printSearchReverseMult("fire")
}
// First task solution uses panic as an exception-like mechanism, as requested // by the task. Note however, this is not idiomatic in Go and in fact // is considered bad practice. func printSearchForward(s string) {
fmt.Printf("Forward search: %s: ", s)
defer func() {
if x := recover(); x != nil {
if err, ok := x.(string); ok && err == "no match" {
fmt.Println(err)
return
}
panic(x)
}
}()
fmt.Println("smallest index =", searchForwardPanic(s))
}
func searchForwardPanic(s string) int {
for i, h := range haystack {
if h == s {
return i
}
}
panic("no match")
return -1
}
// Extra task, a quirky search for multiple occurrences. This is written // without panic, and shows more acceptable Go programming practice. func printSearchReverseMult(s string) {
fmt.Printf("Reverse search for multiples: %s: ", s)
if i := searchReverseMult(s); i > -1 {
fmt.Println("largest index =", i)
} else {
fmt.Println("no multiple occurrence")
}
}
func searchReverseMult(s string) int {
largest := -1
for i := len(haystack) - 1; i >= 0; i-- {
switch {
case haystack[i] != s:
case largest == -1:
largest = i
default:
return largest
}
}
return -1
}</lang> Output:
Forward search: soap: smallest index = 15 Forward search: gold: smallest index = 77 Forward search: fire: no match Reverse search for multiples: soap: no multiple occurrence Reverse search for multiples: gold: largest index = 81 Reverse search for multiples: fire: no multiple occurrence
Haskell
Libraries and data: <lang haskell>import Data.List
haystack=["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"] needles = ["Washington","Bush"]</lang> I use 'lambda' notation for readability.
- Find 'just' an index:
<lang haskell>*Main> map (\x -> (x,elemIndex x haystack)) needles [("Washington",Nothing),("Bush",Just 4)]</lang> Want to know if there are there more Bushes hiding in the haystack? <lang haskell>*Main> map (\x -> (x,elemIndices x haystack)) needles [("Washington",[]),("Bush",[4,7])]</lang> To be complete. Here is the 'point free' version of the task: <lang haskell>import Control.Monad import Control.Arrow
- Main> map (ap (,) (flip elemIndex haystack)) needles
[("Washington",Nothing),("Bush",Just 4)]</lang>
HicEst
<lang HicEst>CHARACTER haystack='Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo.' CHARACTER needle*10
DLG(TItle="Enter search string", Edit=needle)
n = EDIT(Text=haystack, Option=2, End, Count=needle) ! Option = word
IF( n == 0 ) THEN
WRITE(Messagebox="!") needle, "not found" ! bus not found
ELSE
first = EDIT(Text=needle, LeXicon=haystack) WRITE(ClipBoard) "First ", needle, "found in position ", first ! First bush found in position 5
last = EDIT(Text=haystack, End, Left=needle, Count=" ") + 1 WRITE(ClipBoard) "Last ", needle, "found in position ", last ! Last bush found in position 8
ENDIF</lang>
Icon and Unicon
<lang Icon> link lists
procedure main() haystack := ["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"] # the haystack every needle := !["Bush","Washington"] do { # the needles
if i := lindex(haystack,needle) then { # first occurrence
write("needle=",needle, " is at position ",i," in haystack.")
if i <:= last(lindex,[haystack,needle]) then # last occurrence
write("needle=",needle, " is at last position ",i," in haystack.")
}
else {
write("needle=",needle, " is not in haystack.")
runerr(500,needle) # throw an error
}
}
end
procedure last(p,arglist) #: return the last generation of p(arglist) or fail local i every i := p!arglist return \i end</lang>
Taken from the public domain Icon Programming Library's lindex in lists which generates list indices for x of any type <lang Icon>procedure lindex(lst, x) #: generate indices for items matching x
local i
every i := 1 to *lst do
if lst[i] === x then suspend i
end</lang>
Sample output:
needle=Bush is at position 5 in haystack. needle=Bush is at last position 8 in haystack. needle=Washington is not in haystack. Run-time error 500 File haystack.icn; Line 7 program malfunction offending value: "Washington" Traceback: main(list_1 = []) runerr(500,"Washington") from line 7 in haystack.icn
J
J has a general and optimized lookup function, i.
For example:
<lang j> Haystack =: ;:'Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo'
Needles =: ;:'Washington Bush' Haystack i. Needles NB. first positions
9 4
Haystack i: Needles NB. last positions
9 7</lang>
Note that the arguments to i. can be anything (ie either or both may be scalars, lists, multidimensional arrays, etc).
To format output similar to the other examples, one might write:
<lang j> Haystack ;:^:_1@(] ,. [ ((<'is not in haystack')"_)`(#@[ I.@:= ])`(8!:0@])} i.) Needles Washington is not in haystack Bush 4</lang>
Or broken up into components and defined as a verb/function for finding the last positions: <lang j> msg=: (<'is not in haystack')"_ NB. not found message
idxmissing=: #@[ I.@:= ] NB. indices of items not found fmtdata=: 8!:0@] NB. format atoms as boxed strings findLastIndex=: ;:inv@(] ,. [ msg`idxmissing`fmtdata} i:)
Haystack findLastIndex Needles NB. usage
Washington is not in haystack Bush 7</lang>
To elaborate a bit: Array-oriented languages (like J) consume the input and produce the output in toto.
That is, all the results are produced simultaneously; consequently, throwing an exception for any part of the input would prohibit producing any output at all.
And while it is both possible and simple to treat the input item by item, this is significantly slower and loses the great advantage of array processing.
Therefore these languages generally produce a special, but conforming, output for "bad" inputs (in this case, an index past the end of the list). Then the functions which consume these outputs may be left untouched (as the special outputs are already in their domain) or may be extended simply.
In this case, there is only one function which formats and prints the results, and its treatment of "good" and "bad" outputs is identical (it cannot distinguish the two). It is simply that the outputs of previous functions have been arranged such that the results are conformable.
Java
for Lists, they have an indexOf() method: <lang java>import java.util.List; import java.util.Arrays;
List<String> haystack = Arrays.asList("Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo");
for (String needle : new String[]{"Washington","Bush"}) {
int index = haystack.indexOf(needle);
if (index < 0)
System.out.println(needle + " is not in haystack");
else
System.out.println(index + " " + needle);
}</lang>
for arrays, you have to do it manually: <lang java>String[] haystack = {"Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"};
OUTERLOOP: for (String needle : new String[]{"Washington","Bush"}) {
for (int i = 0; i < haystack.length; i++)
if (needle.equals(haystack[i])) {
System.out.println(i + " " + needle);
continue OUTERLOOP;
}
System.out.println(needle + " is not in haystack");
}</lang>
Output:
Washington is not in haystack 4 Bush
JavaScript
<lang javascript>var haystack = ['Zig', 'Zag', 'Wally', 'Ronald', 'Bush', 'Krusty', 'Charlie', 'Bush', 'Bozo'] var needles = ['Bush', 'Washington']
for (var i in needles) {
var found = false;
for (var j in haystack) {
if (haystack[j] == needles[i]) {
found = true;
break;
}
}
if (found)
print(needles[i] + " appears at index " + j + " in the haystack");
else
throw needles[i] + " does not appear in the haystack"
}</lang>
The following
:
<lang javascript>for each (var needle in needles) {
var idx = haystack.indexOf(needle);
if (idx == -1)
throw needle + " does not appear in the haystack"
else
print(needle + " appears at index " + idx + " in the haystack");
}
// extra credit
for each (var elem in haystack) {
var first_idx = haystack.indexOf(elem);
var last_idx = haystack.lastIndexOf(elem);
if (last_idx > first_idx) {
print(elem + " last appears at index " + last_idx + " in the haystack");
break
}
}</lang>
K
<lang K> Haystack:("Zig";"Zag";"Wally";"Ronald";"Bush";"Krusty";"Charlie";"Bush";"Bozo")
Needles:("Washington";"Bush")
{:[y _in x;(y;x _bin y);(y;"Not Found")]}[Haystack]'Needles </lang>
Output: <lang K>(("Washington"
"Not Found")
("Bush"
4))</lang>
Additional: If more than one occurrence ("Bush"), also show position of the last occurrence. Here we use the dyadic verb _sm (string match) instead of _bin (binary search).
<lang K> Haystack2: Haystack,,"Bush"
Needles2:Needles,,"Zag"
{+(x;{:[#&x;,/?(*&x;*|&x);"Not found"]}'+x _sm/:y)}[Needles2;Haystack2]</lang>
Output:
<lang K>(("Washington"
"Not found")
("Bush"
4 9)
("Zag"
1))</lang>
Liberty BASIC
<lang lb>haystack$="apple orange pear cherry melon peach banana needle blueberry mango strawberry needle " haystack$=haystack$+"pineapple grape kiwi blackberry plum raspberry needle cranberry apricot"
idx=1 do until word$(haystack$,idx)="" idx=idx+1 loop total=idx-1
needle$="needle" 'index of first occurrence for i = 1 to total
if word$(haystack$,i)=needle$ then exit for
next print needle$;" first found at index ";i
'index of last occurrence for j = total to 1
if word$(haystack$,j)=needle$ then exit for
next print needle$;" last found at index ";j if i<>j then
print "Multiple instances of ";needle$ else print "Only one instance of ";needle$;" in list."
end if
'raise exception needle$="cauliflower" for k=1 to total
if word$(haystack$,k)=needle$ then exit for
next if k>total then
print needle$;" not found in list."
else
print needle$;" found at index ";k
end if
</lang>
Lisaac
<lang Lisaac>+ haystack : ARRAY[STRING]; haystack := "Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo".split; "Washington Bush".split.foreach { needle : STRING;
haystack.has(needle).if {
haystack.first_index_of(needle).print;
' '.print;
needle.print;
'\n'.print;
} else {
needle.print;
" is not in haystack\n".print;
};
};</lang>
Logo
<lang logo>to indexof :item :list
if empty? :list [(throw "NOTFOUND 0)] if equal? :item first :list [output 1] output 1 + indexof :item butfirst :list
end
to showindex :item :list
make "i catch "NOTFOUND [indexof :item :list] ifelse :i = 0 [(print :item [ not found in ] :list)] [(print :item [ found at position ] :i [ in ] :list)]
end
showindex "dog [My dog has fleas] ; dog found at position 2 in My dog has fleas showindex "cat [My dog has fleas] ; cat not found in My dog has fleas</lang>
Lua
<lang lua>list = {"mouse", "hat", "cup", "deodorant", "television", "soap", "methamphetamine", "severed cat heads"} --contents of my desk
item = io.read()
for i,v in ipairs(list)
if v == item then print(i) end
end</lang>
Mathematica
This examples shows you the first appearance, the last appearance, and all appearances (as a list): <lang Mathematica>haystack = {"Zig","Zag","Wally","Ronald","Bush","Zig","Zag","Krusty","Charlie","Bush","Bozo"}; needle = "Zag"; first = Position[haystack,needle,1]1,1 last = Position[haystack,needle,1]-1,1 all = Position[haystack,needle,1]All,1</lang> gives back: <lang Mathematica>2 7 {2,7}</lang>
MATLAB
Collections of strings are stored in cell arrays in MATLAB. The solution bellow will only work for a cell array of this construction:<lang MATLAB>stringCollection = {'string1','string2',...,'stringN'}</lang> It will not work for any other construction, for example:<lang MATLAB>stringCollection = {{'string1'},{'string2'},{...},{'stringN'}}</lang>
searchCollection.m: <lang MATLAB>function index = searchCollection(list,searchItem,firstLast)
%firstLast is a string containing either 'first' or 'last'. The 'first' %flag will cause searchCollection to return the index of the first %instance of the item being searched. 'last' will cause %searchCollection to return the index of the last instance of the item %being searched. indicies = cellfun(@(x)x==searchItem,list); index = find(indicies,1,firstLast); assert(~isempty(index),['The string searchItem does not exist in this collection of strings.']);
end</lang>
Sample Output: <lang MATLAB>>> list = {'a','b','c','d','e','c','f','c'}; >> searchCollection(list,'c','first')
ans =
3
>> searchCollection(list,'c','last')
ans =
8
>> searchCollection(list,'g','last') ??? Error using ==> searchCollection at 11 The string 'g' does not exist in this collection of strings.</lang>
MAXScript
<lang maxscript>haystack=#("Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo")
for needle in #("Washington","Bush") do (
index = findItem haystack needle
if index == 0 then
(
format "% is not in haystack\n" needle
)
else
(
format "% %\n" index needle
)
)</lang>
Output: <lang maxscript>Washington is not in haystack 5 Bush</lang>
Objective-C
<lang objc>NSArray *haystack = [NSArray arrayWithObjects:@"Zig",@"Zag",@"Wally",@"Ronald",@"Bush",@"Krusty",@"Charlie",@"Bush",@"Bozo",nil]; for (id needle in [NSArray arrayWithObjects:@"Washington",@"Bush",nil]) {
int index = [haystack indexOfObject:needle];
if (index == NSNotFound)
NSLog(@"%@ is not in haystack", needle);
else
NSLog(@"%i %@", index, needle);
}</lang>
<lang objc>NSArray *haystack = [NSArray arrayWithObjects:@"Zig",@"Zag",@"Wally",@"Ronald",@"Bush",@"Krusty",@"Charlie",@"Bush",@"Bozo",nil]; id needle; NSEnumerator *enm = [[NSArray arrayWithObjects:@"Washington",@"Bush",nil] objectEnumerator]; while ((needle = [enm nextObject]) != nil) {
int index = [haystack indexOfObject:needle];
if (index == NSNotFound)
NSLog(@"%@ is not in haystack", needle);
else
NSLog(@"%i %@", index, needle);
}</lang>
Objeck
<lang objeck> use Structure;
bundle Default {
class Test {
function : Main(args : String[]) ~ Nil {
haystack := ["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"];
values := CompareVector->New();
each(i : haystack) {
values->AddBack(haystack[i]->As(Compare));
};
needles := ["Washington", "Bush"];
each(i : needles) {
values->Has(needles[i]->As(Compare))->PrintLine();
};
}
}
} </lang>
OCaml
<lang ocaml># let find_index pred lst =
let rec loop n = function
[] -> raise Not_found
| x::xs -> if pred x then n
else loop (n+1) xs
in
loop 0 lst;;
val find_index : ('a -> bool) -> 'a list -> int = <fun>
- let haystack =
["Zig";"Zag";"Wally";"Ronald";"Bush";"Krusty";"Charlie";"Bush";"Bozo"];;
val haystack : string list =
["Zig"; "Zag"; "Wally"; "Ronald"; "Bush"; "Krusty"; "Charlie"; "Bush"; "Bozo"]
- List.iter (fun needle ->
try
Printf.printf "%i %s\n" (find_index ((=) needle) haystack) needle
with Not_found ->
Printf.printf "%s is not in haystack\n" needle)
["Washington"; "Bush"];;
Washington is not in haystack 4 Bush - : unit = ()</lang>
Oz
No such function exists for the built-in list type (the operation is quite inefficient, after all). A possible implementation: <lang oz>declare
%% Lazy list of indices of Y in Xs.
fun {Indices Y Xs}
for
X in Xs
I in 1;I+1
yield:Yield
do
if Y == X then {Yield I} end
end
end
fun {Index Y Xs}
case {Indices Y Xs} of X|_ then X
else raise index(elementNotFound Y) end
end
end
Haystack = ["Zig" "Zag" "Wally" "Ronald" "Bush" "Krusty" "Charlie" "Bush" "Bozo"]
in
{Show {Index "Bush" Haystack}}
{Show {List.last {Indices "Bush" Haystack}}}
{Show {Index "Washington" Haystack}} %% throws</lang>
PARI/GP
<lang parigp>find(v,n)={
my(i=setsearch(v,n));
if(i,
while(i>1, if(v[i-1]==n,i--))
,
error("Could not find")
);
i
};</lang>
Pascal
See Delphi
Perl
<lang perl>use List::Util qw(first);
my @haystack = qw(Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo);
foreach my $needle (qw(Washington Bush)) {
my $index = first { $haystack[$_] eq $needle } (0 .. $#haystack); # note that "eq" was used because we are comparing strings
# you would use "==" for numbers
if (defined $index) {
print "$index $needle\n";
} else {
print "$needle is not in haystack\n";
}
}</lang> Output:
Washington is not in haystack 4 Bush
You could install a non-standard module List::MoreUtils: <lang perl>use List::MoreUtils qw(first_index);
my @haystack = qw(Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo);
foreach my $needle (qw(Washington Bush)) {
my $index = first_index { $_ eq $needle } @haystack; # note that "eq" was used because we are comparing strings
# you would use "==" for numbers
if (defined $index) {
print "$index $needle\n";
} else {
print "$needle is not in haystack\n";
}
}</lang>
Alternatively, if you need to do this a lot, you could create a hash table mapping values to indices in the haystack: <lang perl>my @haystack = qw(Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo);
my %haystack_indices; @haystack_indices{ @haystack } = (0 .. $#haystack); # Caution: this finds the largest index, not the smallest
foreach my $needle (qw(Washington Bush)) {
my $index = $haystack_indices{$needle};
if (defined $index) {
print "$index $needle\n";
} else {
print "$needle is not in haystack\n";
}
}</lang> Output:
Washington is not in haystack 7 Bush
Perl 6
<lang perl6>sub find ($matcher, $container) {
for $container.kv -> $k, $v {
$v ~~ $matcher and return $k;
}
fail 'No values matched';
}
my Str @haystack = <Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo>;
for <Washingston Bush> -> $needle {
my $pos = find $needle, @haystack;
if defined $pos {
say "Found '$needle' at index $pos";
say 'Largest index: ', @haystack.end -
find { $needle eq $^x }, reverse @haystack;
}
else {
say "'$needle' not in haystack";
}
}</lang>
The ~~ operator does smart matching based on the type of the matcher; in the general case, you can pass any predicate you like to force the semantics one way or another.
PHP
<lang php>$haystack = array("Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo");
foreach (array("Washington","Bush") as $needle) {
$i = array_search($needle, $haystack); if ($i === FALSE) // note: 0 is also considered false in PHP, so you need to specifically check for FALSE echo "$needle is not in haystack\n"; else echo "$i $needle\n";
}</lang> Output:
Washington is not in haystack 4 Bush
PicoLisp
Note that in PicoLisp all indexes are one-based (the first element has the position '1') <lang PicoLisp>(de lastIndex (Item Lst)
(- (length Lst) (index Item (reverse Lst)) -1) )
(de findNeedle (Fun Sym Lst)
(prinl Sym " " (or (Fun Sym Lst) "not found")) )
(let Lst '(Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo)
(findNeedle index 'Washington Lst) (findNeedle index 'Bush Lst) (findNeedle lastIndex 'Bush Lst) )</lang>
Output:
Washington not found Bush 5 Bush 8
PL/I
<lang PL/I> search: procedure () returns (fixed binary);
declare haystack (0:9) character (200) varying static initial
('apple', 'banana', 'celery', 'dumpling', 'egg', 'flour',
'grape', 'pomegranate', 'raisin', 'sugar' );
declare needle character (200) varying;
declare i fixed binary;
declare missing_needle condition;
on condition(missing_needle) begin;
put skip list ('your string || needle ||
does not exist in the haystack.');
end;
put ('Please type a string');
get edit (needle) (L);
do i = lbound(haystack,1) to hbound(haystack,1);
if needle = haystack(i) then return (i);
end;
signal condition(missing_needle);
return (lbound(haystack,1)-1);
end search; </lang>
PowerBASIC
<lang powerbasic>FUNCTION PBMAIN () AS LONG
DIM haystack(54) AS STRING
ARRAY ASSIGN haystack() = "foo", "bar", "baz", "quux", "quuux", "quuuux", _
"bazola", "ztesch", "foo", "bar", "thud", "grunt", "foo", _
"bar", "bletch", "foo", "bar", "fum", "fred", "jim", _
"sheila", "barney", "flarp", "zxc", "spqr", ";wombat", "shme", _
"foo", "bar", "baz", "bongo", "spam", "eggs", "snork", "foo", _
"bar", "zot", "blarg", "wibble", "toto", "titi", "tata", _
"tutu", "pippo", "pluto", "paperino", "aap", "noot", "mies", _
"oogle", "foogle", "boogle", "zork", "gork", "bork"
DIM needle AS STRING, found AS LONG, lastFound AS LONG
DO
needle = INPUTBOX$("Word to search for? (Leave blank to exit)")
IF needle <> "" THEN
' collate ucase -> case insensitive
ARRAY SCAN haystack(), COLLATE UCASE, = needle, TO found
IF found > 0 THEN
lastFound = found
MSGBOX "Found """ & needle & """ at index " & TRIM$(STR$(found - 1))
IF found < UBOUND(haystack) THEN
DO
ARRAY SCAN haystack(lastFound), COLLATE UCASE, = needle, TO found
IF found > 0 THEN
MSGBOX "Another occurence of """ & needle & """ at index " & _
TRIM$(STR$(found + lastFound - 1))
lastFound = found + lastFound
ELSE
MSGBOX "No more occurences of """ & needle & """ found"
EXIT DO 'will exit inner DO, not outer
END IF
LOOP
END IF
ELSE
MSGBOX "No occurences of """ & needle & """ found"
END IF
ELSE
EXIT DO
END IF
LOOP
END FUNCTION</lang>
Prolog
Works with SWI-Prolog <lang Prolog>search_a_list(N1, N2) :- L = ["Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Boz", "Zag"],
write('List is :'), maplist(my_write, L), nl, nl,
( nth1(Ind1, L, N1) -> format('~s is in position ~w~n', [N1, Ind1]) ; format('~s is not present~n', [N1])), ( nth1(Ind2, L, N2) -> format('~s is in position ~w~n', [N2, Ind2]) ; format('~s is not present~n', [N2])), ( reverse_nth1(Ind3, L, N1) -> format('~s last position is ~w~n', [N1, Ind3]) ; format('~s is not present~n', [N1])).
reverse_nth1(Ind, L, N) :- reverse(L, RL), length(L, Len), nth1(Ind1, RL, N), Ind is Len - Ind1 + 1.
my_write(Name) :- writef(' %s', [Name]). </lang>
Output :
?- search_a_list("Zag", "Simpson").
List is : Zig Zag Wally Ronald Bush Krusty Charlie Bush Boz Zag
Zag is in position 2
Simpson is not present
Zag last position is 10
true.
PureBasic
<lang PureBasic>If OpenConsole() ; Open a simple console to interact with user
NewList Straws.s()
Define Straw$, target$="TBA"
Define found
Restore haystack ; Read in all the straws of the haystack.
Repeat
Read.s Straw$
If Straw$<>""
AddElement(Straws())
Straws()=UCase(Straw$)
Continue
Else
Break
EndIf
ForEver
While target$<>""
Print(#CRLF$+"Enter word to search for (leave blank to quit) :"): target$=Input()
ResetList(Straws()): found=#False
While NextElement(Straws())
If UCase(target$)=Straws()
found=#True
PrintN(target$+" found as index #"+Str(ListIndex(Straws())))
EndIf
Wend
If Not found
PrintN("Not found.")
EndIf
Wend
EndIf
DataSection
haystack: Data.s "Zig","Zag","Zig","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo",""
EndDataSection</lang>
Python
<lang python>haystack=["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"]
for needle in ("Washington","Bush"):
try: print haystack.index(needle), needle except ValueError, value_error: print needle,"is not in haystack"</lang>
Output:
Washington is not in haystack 4 Bush
Note that in Python, the index method of a list already raises an exception. The following shows the default information given when the exception is not captured in the program: <lang python>>>> haystack=["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"] >>> haystack.index('Bush') 4 >>> haystack.index('Washington') Traceback (most recent call last):
File "<pyshell#95>", line 1, in <module>
haystack.index('Washington')
ValueError: list.index(x): x not in list >>></lang>
There is no built-in method for returning the highest index of a repeated string in a Python list, tuple or array, (although strings have rindex). Instead we need to look for the index in the reversed list and adjust the result. <lang python>>>> def hi_index(needle, haystack): return len(haystack)-1 - haystack[::-1].index(needle)
>>> # Lets do some checks >>> for n in haystack: hi = hi_index(n, haystack) assert haystack[hi] == n, "Hi index is of needle" assert n not in haystack[hi+1:], "No higher index exists" if haystack.count(n) == 1: assert hi == haystack.index(n), "index == hi_index if needle occurs only once"
>>></lang>
R
<lang R>find.needle <- function(haystack, needle="needle", return.last.index.too=FALSE) {
indices <- which(haystack %in% needle)
if(length(indices)==0) stop("no needles in the haystack")
if(return.last.index.too) range(indices) else min(indices)
}</lang> Example usage: <lang R>haystack1 <- c("where", "is", "the", "needle", "I", "wonder") haystack2 <- c("no", "sewing", "equipment", "in", "here") haystack3 <- c("oodles", "of", "needles", "needles", "needles", "in", "here")
find.needle(haystack1) # 4 find.needle(haystack2) # error find.needle(haystack3) # 3 find.needle(haystack3, needle="needles", ret=TRUE) # 3 5</lang>
REBOL
<lang REBOL>REBOL [ Title: "List Indexing" Author: oofoe Date: 2009-12-06 URL: http://rosettacode.org/wiki/Index_in_a_list ]
locate: func [ "Find the index of a string (needle) in string collection (haystack)." haystack [series!] "List of values to search." needle [string!] "String to find in value list." /largest "Return the largest index if more than one needle." /local i ][ i: either largest [ find/reverse tail haystack needle][find haystack needle] either i [return index? i][ throw reform [needle "is not in haystack."] ] ]
- Note that REBOL uses 1-base lists instead of 0-based like most
- computer languages. Therefore, the index provided will be one
- higher than other results on this page.
haystack: parse "Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo" none
print "Search for first occurance:" foreach needle ["Washington" "Bush"] [ print catch [ reform [needle "=>" locate haystack needle] ] ]
print [crlf "Search for last occurance:"] foreach needle ["Washington" "Bush"] [ print catch [ reform [needle "=>" locate/largest haystack needle] ] ]</lang>
Output:
Search for first occurance: Washington is not in haystack. Bush => 5 Search for last occurance: Washington is not in haystack. Bush => 8
REXX
This REXX program searches a collection of string (haystack) that are
stored in a sequential REXX array.
No counter is kept of the number of
items, but they should be numbered consecutively and can't have any gaps.
The haystack items may have any character, including blanks. A null
value isn't allowed.
<lang rexx>
/*REXX program searches a collection of strings, version 1. */
hay.= /*initialize haystack collection. */ hay.1 ='sodium' hay.2 ='phosphorous' hay.3 ='califonium' hay.4 ='copernicium' hay.5 ='gold' hay.6 ='thallium' hay.7 ='carbon' hay.8 ='silver' hay.9 ='curium' hay.10='copper' hay.11='helium' hay.12='sulfur'
needle='gold' /*we'll be looking for the gold. */
found=0 /*assume needle isn't found (so far). */
do j=1 while hay.j\== /*keep looking in haystack until nul. */
if hay.j=needle then do /*we've found a needle in the haystack.*/
found=1 /*indicate that a needle was found.*/
leave /* and stop looking, of course.*/
end
end
if \found then say needle "wasn't found in the haystack!"
</lang>
This REXX program searches a collection of string (haystack) that are
stored in a REXX array (which may have gaps).
A safe counter is kept of the maximum (highest) index in the array,
this counter may be any sufficiently high number.
The array may be out of order (but not recommended!).
<lang rexx>
/*REXX program searches a collection of strings, version 2. */
hay.0=100 /*safely indicate the highest item num.*/ hay.1 ='sodium' hay.2 ='phosphorous' hay.3 ='califonium' hay.7 ='copernicium' hay.9 ='gold' hay.16='thallium' hay.27='carbon' hay.30='silver' hay.33='lead' hay.45='copper' hay.46='helium' hay.10='sulfur'
needle='gold' /*we'll be looking for the gold. */
found=0 /*assume needle isn't found (so far). */
do j=1 for hay.0 /*start looking in the haystack, item 1*/
if hay.j=needle then do /*we've found a needle in the haystack.*/
found=1 /*indicate that a needle was found.*/
leave /* and stop looking, of course.*/
end
end
if \found then say needle "wasn't found in the haystack!"
/*---incidentally, to find out the number of items: */
hayItems=0
do k=1 for hay.0 /*find the item AFTER the last item. */ if hay.k\== then hayItems=hayItems+1 /*bump the item counter.*/ end
</lang>
This REXX program searches a collection of string (haystack) that are
stored in a REXX array.
This form uses a type of array called a
sparse arrow (with non-numeric indexes).
One drawback of this approach
is that the items can't have leading/trailing/imbedded blanks, nor can
they have special characters.
Only letters, numerals, and a few special
characters are allowed: !, @, #, $, ?, and _.
This method (finding a needle in a haystack) is extremely fast as there
isn't any table lookup, the "finding" is done by REXX's own internal
method of variable lookup, and, for the most part, it based on a table
hashing algorithm.
This method pre-prends an underscore (underbar) to avoid collision with
any REXX variable names. Therefore, there shouldn't be any REXX variable
names (in this program) that have a leading underscore (_).
<lang rexx>
/*REXX program searches a collection of strings, version 3. */
hay.=0 /*initialize haystack collection. */ hay._sodium =1 hay._phosphorous =1 hay._califonium =1 hay._copernicium =1 hay._gold =1 hay._thallium =1 hay._carbon =1 hay._silver =1 hay._copper =1 hay._helium =1 hay._sulfur =1
needle='gold' /*we'll be looking for the gold. */
Xneedle='_'needle /*pre-pend an underscore (underbar). */
upper Xneedle /*uppercase (that's how REXX stores 'em*/
/*alternative version of the above 2: */
/* Xneedle=translate('_'needle) */
found=hay.Xneedle /*this is it, it's found or it ain't. */
if \found then say needle "wasn't found in the haystack!"
</lang>
This REXX program searches a collection of string (haystack) that are
stored in a sequential REXX array (as in version 2).
This version finds the LAST occurance of the needle.
<lang rexx>
/*REXX program searches a collection of strings, version 4. */
hay.0=100 /*safely indicate the highest item num.*/ hay.1 ='sodium' hay.2 ='phosphorous' hay.3 ='califonium' hay.7 ='copernicium' hay.9 ='gold' hay.16='thallium' hay.27='carbon' hay.30='silver' hay.31='gold' hay.45='copper' hay.46='helium' hay.10='sulfur'
needle='gold' /*we'll be looking for the gold. */
found=0 /*assume needle isn't found (so far). */
do j=1 for hay.0 /*start looking in the haystack, item 1*/ if hay.j=needle then found=1 /*we've found a needle in haystack.*/ end /*(above) will find last occurance.*/
if \found then say needle "wasn't found in the haystack!" </lang>
Ruby
<lang ruby>haystack = %w(Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo)
%w(Bush Washington).each do |needle|
if (i = haystack.index(needle))
print i, " ", needle, "\n"
else
raise "#{needle} is not in haystack\n"
end
end</lang> Output:
4 Bush search_a_list.rb:8:in `block in <main>': Washington is not in haystack (RuntimeError) from search_a_list.rb:4:in `each' from search_a_list.rb:4:in `<main>'
extra credit <lang ruby>haystack.each do |item|
last = haystack.rindex(item)
if last > haystack.index(item)
puts "#{item} last appears at index #{last}"
break
end
end</lang>
or,
<lang ruby>multi_item = haystack .each_with_index .group_by {|elem, idx| elem} .find {|key, val| val.length > 1}
- multi_item is => ["Bush", [["Bush", 4], ["Bush", 7]]]
puts "#{multi_item[0]} last appears at index #{multi_item[1][-1][1]}" unless multi_item.nil?</lang>
Run BASIC
<lang runbasic>haystack$ = ("Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo Bush ") needle$ = "Zag Wally Bush Chicken"
while word$(needle$,i+1," ") <> ""
i = i + 1 thisNeedle$ = word$(needle$,i," ") + " " j = instr(haystack$,thisNeedle$) k1 = 0 k = instr(haystack$,thisNeedle$,j+1) while k <> 0 k1 = k k = instr(haystack$,thisNeedle$,k+1) wend if j <> 0 then print thisNeedle$;" located at:";j; if k1 <> 0 then print " Last position located at:";k1; print else print thisNeedle$;" is not in the list" end if
wend</lang>Output:
Zag located at:5 Wally located at:9 Bush located at:22 Last position located at:52 Chicken is not in the list
Sather
<lang sather>class MAIN is
main is
haystack :ARRAY{STR} := |"Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Bozo"|;
needles :ARRAY{STR} := | "Washington", "Bush" |;
loop needle ::= needles.elt!;
index ::= haystack.index_of(needle); if index < 0 then #OUT + needle + " is not in the haystack\n"; else #OUT + index + " " + needle + "\n"; end;
end; end;
end; </lang>
Scala
The method indexOf, defined for all classes inheriting from, or having an implicit conversion to, Seq returns the index of the first element, or -1 if none exists. The method lastIndexOf does the same for the last element. Neither throws an exception, but that's easily done afterwards.
However, a simple implementation, not using those or similar methods might be written like this:
<lang scala>def findNeedles(needle: String, haystack: Seq[String]) = haystack.zipWithIndex.filter(_._1 == needle).map(_._2) def firstNeedle(needle: String, haystack: Seq[String]) = findNeedles(needle, haystack).head def lastNeedle(needle: String, haystack: Seq[String]) = findNeedles(needle, haystack).last</lang>
It does raise an exception if there's no needle.
Scheme
<lang scheme> (define haystack
'("Zig" "Zag" "Wally" "Ronald" "Bush" "Krusty" "Charlie" "Bush" "Bozo"))
(define index-of
(lambda (needle hackstack)
(let ((tail (member needle haystack)))
(if tail
(- (length haystack) (length tail))
(throw 'needle-missing)))))
(define last-index-of
(lambda (needle hackstack)
(let ((tail (member needle (reverse haystack))))
(if tail
(- (length tail) 1)
(throw 'needle-missing)))))
</lang>
(index-of "Bush" haystack) 4 (last-index-of "Bush" haystack) 7
Slate
<lang slate>define: #haystack -> ('Zig,Zag,Wally,Ronald,Bush,Krusty,Charlie,Bush,Bozo' splitWith: $,). {'Washington'. 'Bush'} do: [| :needle |
(haystack indexOf: needle)
ifNil: [inform: word ; ' is not in the haystack']
ifNotNilDo: [| :firstIndex lastIndex |
inform: word ; ' is in the haystack at index ' ; firstIndex printString.
lastIndex: (haystack lastIndexOf: word).
lastIndex isNotNil /\ (lastIndex > firstIndex) ifTrue:
[inform: 'last occurrence of ' ; word ; ' is at index ' ; lastIndex]]].</lang>
Smalltalk
Smalltalk indexes start at 1. <lang smalltalk>| haystack | haystack :=
'Zig,Zag,Wally,Ronald,Bush,Krusty,Charlie,Bush,Bozo' subStrings: $,.
{ 'Washington' . 'Bush' } do: [:i|
|t l|
t := (haystack indexOf: i).
(t = 0) ifTrue: [ ('%1 is not in the haystack' % { i }) displayNl ]
ifFalse: [ ('%1 is at index %2' % { i . t }) displayNl.
l := ( (haystack size) - (haystack reverse indexOf: i) + 1 ).
( t = l ) ifFalse: [
('last occurence of %1 is at index %2' %
{ i . l }) displayNl ]
]
].</lang>
Standard ML
<lang sml>fun find_index (pred, lst) = let
fun loop (n, []) = NONE
| loop (n, x::xs) = if pred x then SOME n
else loop (n+1, xs)
in
loop (0, lst)
end;
val haystack = ["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"];
app (fn needle =>
case find_index (fn x => x = needle, haystack) of
SOME i => print (Int.toString i ^ " " ^ needle ^ "\n")
| NONE => print (needle ^ " is not in haystack\n"))
["Washington", "Bush"];</lang>
Tcl
<lang tcl>set haystack {Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo} foreach needle {Bush Washington} {
if {[set idx [lsearch -exact $haystack $needle]] == -1} {
error "$needle does not appear in the haystack"
} else {
puts "$needle appears at index $idx in the haystack"
}
}</lang> extra credit: <lang tcl>set haystack {Zig Zag Wally Ronald Bush Krusty Charlie Bush Bozo} foreach needle {Bush Washington} {
set indices [lsearch -all -exact $haystack $needle]
if {[llength $indices] == 0} {
error "$needle does not appear in the haystack"
} else {
puts "$needle appears first at index [lindex $indices 0] and last at [lindex $indices end]"
}
}</lang>
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT SET haystack="Zig'Zag'Wally'Ronald'Bush'Krusty'Charlie'Bush'Bozo" PRINT "haystack=",haystack LOOP needle="Washington'Bush'Wally" SET table =QUOTES (needle) BUILD S_TABLE needle = table
IF (haystack.ct.needle) THEN BUILD R_TABLE needle = table SET position=FILTER_INDEX(haystack,needle,-) RELEASE R_TABLE needle PRINT "haystack contains ", needle, " on position(s): ",position ELSE PRINT "haystack not contains ",needle ENDIF
RELEASE S_TABLE needle ENDLOOP </lang> Output:
haystack=Zig'Zag'Wally'Ronald'Bush'Krusty'Charlie'Bush'Bozo haystack not contains Washington haystack contains Bush on position(s): 5'8 haystack contains Wally on position(s): 3
Ursala
The indices function takes a pair of any type, treats haystack
as a list, and returns the pair of indices giving the first and last
positions of needle in it, which are numbered from zero and may be
equal. If it's not present, an exception is thrown with a diagnostic
message of 'missing'. The search is expressed by ~|, the built in
distributing filter operator.
<lang Ursala>#import std
indices = ||<'missing'>!% ~&nSihzXB+ ~&lrmPE~|^|/~& num</lang> The explanation is somewhat longer than the program.
- The
^|operator takes a right operand consisting of a pair of functions , and returns a function that takes a pair to the result . - An expression of the form
h/f gwherehis a function taking a pair, is equivalent toh(f,g). - The
~&operator represents the identity function. - The expression
^|/~& numapplied to an argument therefore evaluates tonum - The
numfunction takes any list and transforms it to a list of pairs . - The left operand to the
^|operator, if any, is composed with the function constructed from the right. In this case, the left operand is~&lrmPE~| - The
~|operator takes a predicate as its left operand and returns a function that operates on a pair , where is expected to be a list. The resulting function is evaluated by pairing with each item of , applying the predicate to each pair, and making a list of the items of for which the predicate holds on the pair. - The predicate in this case is
~&lrmPE, which will be passed an input of the form for the -th item in terms of the notation above. - The expression
~&lrmPEhas a root operatorE, which tests for equality, a left operandl, which extracts the left side of its argument, and a right operand ofrmP, which is the reverse composition (P) of the right side extraction (r) operator, followed by a further right side extraction expressed more idiomatically asmwhen the argument in question represents some type of key-value pair. - The predicate therefore compares the left side of , which is , to the right of the right, which is
- The result from
~&lrmPE~|will be a list of pairs of the form , for indices at which appears in the list. - This result is passed to the function
~&nSihzXB, which consists of subexpressionsnSandihzXBthat operate sequentially. - The
nSsubexpression makes a list of the left sides of all items of a list of key-value pairs, in this case constructing a list of indices from the input, and passing it to the subexpressionihzXB. - The subexpression
ihzXBhas a left subexpressioni, a right subexpressionhzXand a rootB. - The
B(mnemonic for "both") operator causes the left subexpression to be applied to the argument as a test, and if the result is non-empty, returns the result of applying the right. - The left subexpression
irepresents the identity function, and tests whether the argument list is non-empty. - If the list is non-empty, the expression
hzXconstructs the pair (X) of the head (h) and the last item (z) of the list given in the argument. - The disjunction operator
||used in an expression of the form||u vwith functionsuandvconstructs a function that appliesvto the argument, returns that result if non-empty, but otherwise returns the the result of applyingvto the argument. - The expression
<'missing'>is a list of strings representing the diagnostic message to be returned in the event of an empty list (corresponding to the not being present). - The constant operator (
!) is used because the message is not data-dependent. - The exception throwing operator (
%) compels the result of its operand to be returned in a way that bypasses the usual flow of control.
test program: <lang Ursala>#cast %nW
test = indices/'bar' <'foo','bar','baz','bar'></lang> output:
(1,3)
Yorick
<lang yorick>haystack = ["Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Bozo"]; needles = ["Bush", "Washington"]; for(i = 1; i <= numberof(needles); i++) {
w = where(haystack == needles(i));
if(!numberof(w))
error, "Needle "+needles(i)+" not found";
write, format="Needle %s appears first at index %d\n", needles(i), w(1);
if(numberof(w) > 1)
write, format="Needle %s appears last at index %d\n", needles(i), w(0);
}</lang>
- Programming Tasks
- Text processing
- ACL2
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- Delphi
- E
- Erlang
- Euphoria
- Factor
- Forth
- Fortran
- GAP
- Groovy
- Go
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- K
- Liberty BASIC
- Lisaac
- Logo
- Lua
- Mathematica
- MATLAB
- MAXScript
- Objective-C
- Objeck
- OCaml
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PowerBASIC
- Prolog
- PureBasic
- Python
- R
- REBOL
- REXX
- Ruby
- Run BASIC
- Sather
- Scala
- Scheme
- Slate
- Smalltalk
- Standard ML
- Tcl
- TUSCRIPT
- Ursala
- Yorick