Order two numerical lists: Difference between revisions
Lhogho |
|||
Line 780: | Line 780: | ||
return 0 |
return 0 |
||
}</lang> |
}</lang> |
||
=={{header|TUSCRIPT}}== |
|||
<lang tuscript> |
|||
$$ MODE TUSCRIPT |
|||
MODE DATA |
|||
$$ numlists=* |
|||
1'2'1'3'2 |
|||
1'2'0'4'4'0'0'0 |
|||
1'2'3'4'5 |
|||
1'2'1'5'2'2 |
|||
1'2'1'6 |
|||
1'2'1'6'2 |
|||
1'2'4 |
|||
1'2'4 |
|||
1'2 |
|||
1'2'4 |
|||
$$ MODE TUSCRIPT |
|||
list1="1'2'5'6'7" |
|||
LOOP n,list2=numlists |
|||
text=CONCAT (" ",list1," < ",list2) |
|||
IF (list1<list2) THEN |
|||
PRINT " true: ",text |
|||
ELSE |
|||
PRINT "false: ",text |
|||
ENDIF |
|||
list1=VALUE(list2) |
|||
ENDLOOP |
|||
</lang> |
|||
Output: |
|||
<pre style='height:30ex;overflow:scroll'> |
|||
false: 1'2'5'6'7 < 1'2'1'3'2 |
|||
false: 1'2'1'3'2 < 1'2'0'4'4'0'0'0 |
|||
true: 1'2'0'4'4'0'0'0 < 1'2'3'4'5 |
|||
false: 1'2'3'4'5 < 1'2'1'5'2'2 |
|||
true: 1'2'1'5'2'2 < 1'2'1'6 |
|||
true: 1'2'1'6 < 1'2'1'6'2 |
|||
true: 1'2'1'6'2 < 1'2'4 |
|||
false: 1'2'4 < 1'2'4 |
|||
false: 1'2'4 < 1'2 |
|||
true: 1'2 < 1'2'4 |
|||
</pre> |
Revision as of 19:56, 12 October 2012
You are encouraged to solve this task according to the task description, using any language you may know.
Write function that orders two lists or arrays filled with numbers.
The function should accept two lists as arguments and return true
if the first list should be ordered before the second, and false
otherwise.
The order is determined by lexicographic order: Comparing the first element of each list. If the first elements are equal, then the second elements should be compared, and so on, until one of the list has no more elements. If the first list runs out of elements the result is true
. if the second list or both run out of elements the result is false
.
ACL2
The built-in lexorder does this.
ACL2 !>(lexorder '(1 2 3) '(1 2 3 4)) T ACL2 !>(lexorder '(1 2 4) '(1 2 3)) NIL
Ada
This is already implemented in the built-in comparison operators for arrays of types that have a direct ordering. This also includes arrays of user defined types, using the type definition order from smallest to largest. Demonstrated in the program below: <lang Ada> with Ada.Text_IO; use Ada.Text_IO; procedure Order is
type IntArray is array (Positive range <>) of Integer; List1 : IntArray := (1, 2, 3, 4, 5); List2 : IntArray := (1, 2, 1, 5, 2, 2); List3 : IntArray := (1, 2, 1, 5, 2); List4 : IntArray := (1, 2, 1, 5, 2);
type Animal is (Rat, Cat, Elephant); type AnimalArray is array (Positive range <>) of Animal; List5 : AnimalArray := (Cat, Elephant, Rat, Cat); List6 : AnimalArray := (Cat, Elephant, Rat); List7 : AnimalArray := (Cat, Cat, Elephant);
begin
Put_Line (Boolean'Image (List1 > List2)); -- True Put_Line (Boolean'Image (List2 > List3)); -- True Put_Line (Boolean'Image (List3 > List4)); -- False, equal Put_Line (Boolean'Image (List5 > List6)); -- True Put_Line (Boolean'Image (List6 > List7)); -- True
end Order; </lang> Output:
TRUE TRUE FALSE TRUE TRUE
AutoHotkey
The function is overkill as we can just compare the list's ObjMaxIndex() <lang AHK>List1 := [1,2,1,3,2] List2 := [1,2,0,4,4,0,0,0] MsgBox % order(List1, List2)
order(L1, L2){ return L1.MaxIndex() < L2.MaxIndex() }</lang>
Bracmat
When evaluating a sum or a product, Bracmat creates an expression with a canonical order, which happens to be compatible with the order defined in this task. In a pattern, only a sum or product on the left hand side (lhs) of the match (:
) operator is evaluated. In the solution below we match a composition of the two function arguments into a sum of two terms with itself. If the match expression succeeds, the lhs must already have been in canonical order before evaluation, which means that the first argument is smaller than the second argument. In that case the function outputs FALSE. Notice that if the arguments are the same, evaluation of the sum produces the product of one of the terms and a factor two. This complicates the pattern a bit.
<lang bracmat>( 1 2 3 4 5:?List1
& 1 2 1 5 2 2:?List2
& 1 2 1 5 2:?List3
& 1 2 1 5 2:?List4
& Cat Elephant Rat Cat:?List5
& Cat Elephant Rat:?List6
& Cat Cat Elephant:?List7
& ( gt
= first second . !arg:(?first,?second) & out $ ( (.!first)+(.!second) : ((.!first)+(.!second)|2*(.!first)) & FALSE | TRUE ) )
& gt$(!List1,!List2) & gt$(!List2,!List3) & gt$(!List3,!List4) & gt$(!List4,!List5) & gt$(!List5,!List6) & gt$(!List6,!List7) );</lang> Output:
TRUE TRUE FALSE FALSE TRUE TRUE
C
<lang c>int list_cmp(int *a, int la, int *b, int lb)
{
int i, l = la;
if (l > lb) l = lb;
for (i = 0; i < l; i++) {
if (a[i] == b[i]) continue;
return (a[i] > b[i]) ? 1 : -1;
}
if (la == lb) return 0;
return la > lb ? 1 : -1;
}</lang>
This funciton returns one of three states, not a boolean. One can define boolean comparisons, such as list_less_or_eq
, based on it:<lang c>#define list_less_or_eq(a,b,c,d) (list_cmp(a,b,c,d) != 1)</lang>
C++
The built-in comparison operators already do this: <lang cpp>#include <iostream>
- include <vector>
int main() {
std::vector<int> a; a.push_back(1); a.push_back(2); a.push_back(1); a.push_back(3); a.push_back(2); std::vector<int> b; b.push_back(1); b.push_back(2); b.push_back(0); b.push_back(4); b.push_back(4); b.push_back(0); b.push_back(0); b.push_back(0);
std::cout << std::boolalpha << (a < b) << std::endl; // prints "false" return 0;
}</lang>
clojure
<lang clojure> (defn lex? [a b]
(compare a b))
</lang>
Common Lisp
<lang Lisp>(defun list< (a b)
(cond ((not b) nil) ((not a) t) ((= (first a) (first b)) (list< (rest a) (rest b))) (t (< (first a) (first b)))))</lang>
Alternate version
<lang Lisp>(defun list< (a b)
(let ((x (find-if-not #'zerop (mapcar #'- a b)))) (if x (minusp x) (< (length a) (length b)))))</lang>
D
The built-in comparison operators already do this: <lang d>void main() {
assert([1,2,1,3,2] >= [1,2,0,4,4,0,0,0]);
}</lang>
Ela
<lang ela>[] <. _ = true _ <. [] = false (x::xs) <. (y::ys) | x == y = xs <. ys
| else = x < y
[1,2,1,3,2] <. [1,2,0,4,4,0,0,0]</lang>
Factor
All sequences respond to words in the math.order vocabulary.
IN: scratchpad { 2 3 } { 2 5 } before? . t
Go
<lang go>package main
import "fmt"
// If your numbers happen to be in the range of Unicode code points (0 to 0x10ffff), this function // satisfies the task: func lessRune(a, b []rune) bool {
return string(a) < string(b) // see also bytes.Compare
}
// Otherwise, the following function satisfies the task for all integer // and floating point types, by changing the type definition appropriately. type numericType int
func lessNT(a, b []numericType) bool {
l := len(a) if len(b) < l { l = len(b) } for i := 0; i < l; i++ { if a[i] != b[i] { return a[i] < b[i] } } return l < len(b)
}
var testCases = [][][]numericType{
{{0}, {}}, {{}, {}}, {{}, {0}},
{{-1}, {0}}, {{0}, {0}}, {{0}, {-1}},
{{0}, {0, -1}}, {{0}, {0, 0}}, {{0}, {0, 1}}, {{0, -1}, {0}}, {{0, 0}, {0}}, {{0, 0}, {1}},
}
func main() {
// demonstrate the general function for _, tc := range testCases { fmt.Printf("order %6s before %6s : %t\n", fmt.Sprintf("%v", tc[0]), fmt.Sprintf("%v", tc[1]), lessNT(tc[0], tc[1])) } fmt.Println()
// demonstrate that the byte specific function gives identical results // by offsetting test data to a printable range of characters. for _, tc := range testCases { a := toByte(tc[0]) b := toByte(tc[1]) fmt.Printf("order %6q before %6q : %t\n", string(a), string(b), lessByte(a, b)) }
}
func toByte(a []numericType) []byte {
b := make([]byte, len(a)) for i, n := range a { b[i] = 'b' + byte(n) } return b
}</lang> Output:
order [0] before [] : false order [] before [] : false order [] before [0] : true order [-1] before [0] : true order [0] before [0] : false order [0] before [-1] : false order [0] before [0 -1] : true order [0] before [0 0] : true order [0] before [0 1] : true order [0 -1] before [0] : false order [0 0] before [0] : false order [0 0] before [1] : true order "b" before "" : false order "" before "" : false order "" before "b" : true order "a" before "b" : true order "b" before "b" : false order "b" before "a" : false order "b" before "ba" : true order "b" before "bb" : true order "b" before "bc" : true order "ba" before "b" : false order "bb" before "b" : false order "bb" before "c" : true
Groovy
Solution: <lang groovy>class CList extends ArrayList implements Comparable {
CList() { } CList(Collection c) { super(c) } int compareTo(Object that) { assert that instanceof List def n = [this.size(), that.size()].min() def comp = [this[0..<n], that[0..<n]].transpose().find { it[0] != it[1] } comp ? comp[0] <=> comp[1] : this.size() <=> that.size() }
}</lang>
Test: <lang groovy>CList a, b; (a, b) = [[], []]; assert ! (a < b) b = [1] as CList; assert (a < b) a = [1] as CList; assert ! (a < b) b = [2] as CList; assert (a < b) a = [2, -1, 0] as CList; assert ! (a < b) b = [2, -1] as CList; assert ! (a < b) b = [2, -1, 0] as CList; assert ! (a < b) b = [2, -1, 0, -17] as CList; assert (a < b) a = [2, 8, 0] as CList; assert ! (a < b)</lang>
Haskell
The built-in comparison operators already do this: <lang haskell>Prelude> [1,2,1,3,2] < [1,2,0,4,4,0,0,0] False</lang>
Icon and Unicon
List_llt is written in the style of all Icon/Unicon relational operators returning its right argument if successful and signaling failure otherwise.
<lang Icon>procedure main()
write( if list_llt([1,2,1,3,2],[1,2,0,4,4,0,0,0]) then "true" else "false" )
end
procedure list_llt(L1,L2) #: returns L2 if L1 lexically lt L2 or fails
every i := 1 to min(*L1,*L2) do
if L1[i] << L2[i] then return L2 else if L1[i] >> L2[i] then fail
if *L1 < *L2 then return L2 end</lang>
J
This is not a built-in in J.
<lang j>before=: -.@(-: /:~)@,&<~</lang>
Example use:
<lang j> (,0) before 0
before
0
before ,0
1
(,_1) before ,0
1
(,0) before ,0
0
(,0) before ,_1
0
(,0) before 0 _1
1
(,0) before 0 0
1
(,0) before 0 1
1
0 _1 before ,0
0
0 0 before ,0
0
0 0 before ,1
1
(,'b') before
0
before
0
before ,'b'
1
(,'a') before ,'b'
1
(,'b') before ,'b'
0
(,'b') before ,'a'
0
(,'b') before 'ba'
1
(,'b') before 'bb'
1
(,'b') before 'bc'
1
'ba' before ,'b'
0
'bb' before ,'b'
0
'bb' before ,'c'
1</lang>
Java
There are a few methods here. The method named "ordered" which works on arrays is a translation of Common Lisp. The other two are loose translations of Tcl (some tweaks were needed to get the length checks to work out) and are probably better options. <lang java5>import java.util.Arrays; import java.util.List;
public class ListOrder{ public static boolean ordered(double[] first, double[] second){ if(first.length == 0) return true; if(second.length == 0) return false; if(first[0] == second[0]) return ordered(Arrays.copyOfRange(first, 1, first.length), Arrays.copyOfRange(second, 1, second.length)); return first[0] < second[0]; }
public static <T extends Comparable<? super T>> boolean ordered(List<T> first, List<T> second){ int i = 0; for(; i < first.size() && i < second.size();i++){ int cmp = first.get(i).compareTo(second.get(i)); if(cmp == 0) continue; if(cmp < 0) return true; return false; } return i == first.size(); }
public static boolean ordered2(double[] first, double[] second){ int i = 0; for(; i < first.length && i < second.length;i++){ if(first[i] == second[i]) continue; if(first[i] < second[i]) return true; return false; } return i == first.length; } }</lang>
Joy
<lang Joy> DEFINE order == [equal] [false] [[[[size] dip size <=] [[<=] mapr2 true [and] fold]] [i] map i and] ifte. </lang>
Using it:
[1 2] [1 2 3] order. # true [1 2] [1 3] order. # true [1 2] [1 2] order. # false [1 3] [1 2] order. # false [1 2 3] [1 2] order. # false
LabVIEW
This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.
Lhogho
Uses standard '=' notation
<lang logo>print [1 2] = [1 2] print [1 2] = [1 2 3] print [1 3] = [1 2] print [1 2 3] = [1 2]
make "list1 [1 2 3 4 5 6] make "list2 [1 2 3 4 5 7] print :list1 = :list2</lang>
output: <lang logo>true false false false false</lang>
Mathematica
<lang Mathematica>order[L1_, L2_] := Length [L1] < Length [L2]</lang>
Example use: List1 = {1, 2, 1, 3, 2}; List2 = {1, 2, 0, 4, 4, 0, 0, 0}; order[List1, List2] ->True
Mercury
For a particular numerical type, you can get away with
<lang Mercury>:- pred lt(list(int)::in, list(int)::in) is semidet. lt([], [_|_]). lt([H1|T1], [H2|T2]) :- H1 =< H2, T1 `lt` T2.</lang>
For a list of any numerical type, one way would be to use a typeclass:
<lang Mercury>:- pred lt(list(T)::in, list(T)::in) is semidet <= comparable(T). lt([], [_|_]). lt([H1|T1], [H2|T2]) :- H1 =< H2, T1 `lt` T2.</lang>
... which you would have to create:
<lang Mercury>:- module comparable.
- - interface.
- - import_module int, float, integer, list.
- - typeclass comparable(T) where [
pred '<'(T::in, T::in) is semidet, pred '=<'(T::in, T::in) is semidet
].
- - instance comparable(int).
- - instance comparable(float).
- - instance comparable(integer).
- - instance comparable(list(T)) <= comparable(T).
- - implementation.
- - instance comparable(int) where [
pred('<'/2) is int.(<), pred('=<'/2) is int.(=<)
]. % likewise for float and integer...
- - instance comparable(list(T)) <= comparable(T) where [
pred('<'/2) is lt, % the 'lt' above. pred('=<'/2) is lte % 'lt' with: lte([], []).
].
% pred lt % pred lte</lang>
Which would be used in this way - note the typeclass and the comparison operator.
<lang Mercury>:- pred test(list(T), list(T), io, io) <= comparable(T).
- - mode test(in, in, di, uo) is det.
test(A, B) -->
io.write(A), io.write_string(" < "), io.write(B), io.write_string(" : "), io.write_string(S), io.nl, { A < B -> S = "yes" ; S = "no" }.</lang>
OCaml
The built-in comparison operators already do this: <lang ocaml># [1;2;1;3;2] < [1;2;0;4;4;0;0;0];; - : bool = false</lang>
But we could write it explicitly this way:
<lang ocaml>let rec ordered_lists = function
| x1::tl1, x2::tl2 -> (match compare x1 x2 with | 0 -> ordered_lists (tl1, tl2) | 1 -> false | _ -> true) | [], _ -> true | _ -> false</lang>
Here is a small script to test this function:
<lang ocaml>(* copy-paste the code of ordered_lists here *)
let make_num_list p n =
let rec aux acc = if Random.int p = 0 then acc else aux (Random.int n :: acc) in aux []
let print_num_list lst =
List.iter (Printf.printf " %d") lst; print_newline()
let () =
Random.self_init(); let lst1 = make_num_list 8 5 in let lst2 = make_num_list 8 5 in print_num_list lst1; print_num_list lst2; Printf.printf "ordered: %B\n" (ordered_lists (lst1, lst2))</lang>
Sample execution:
$ ocaml ordered_lists.ml 1 2 1 3 2 1 2 0 4 4 0 0 0 ordered: false
Also notice that the function ordered_lists
will work with anything the function Pervasives.compare
is able to compare (most OCaml types and structures made from the base types). In the prototype of this function below 'a list
means a list of anything:
<lang ocaml>val ordered_lists : 'a list * 'a list -> bool</lang>
PARI/GP
<lang parigp>lex(u,v)<1</lang>
Perl
<lang Perl>#!/usr/bin/perl -w use strict ;
sub orderlists {
my $firstlist = shift ; my $secondlist = shift ; my $first = shift @{$firstlist } if @{$firstlist} ; my $second ;
- keep stripping elements from the first list as long as there are any
- or until the second list is used up!
while ( @{$firstlist} ) { if ( @{$secondlist} ) { #second list is not used up yet!
$second = shift @{$secondlist} ; if ( $first < $second ) { return 1 ; } if ( $first > $second ) { return 0 ; }
} else { #second list used up, defined to return false
return 0 ;
} $first = shift @{$firstlist} ; } return 0 ; #in all remaining cases return false
}
my @firstnumbers = ( 43 , 33 , 2 ) ; my @secondnumbers = ( 45 ) ; if ( orderlists( \@firstnumbers , \@secondnumbers ) ) {
print "The first list comes before the second list!\n" ;
} else {
print "The first list does not come before the second list!\n" ;
} </lang>
Perl 6
This is already a built-in comparison operator. <lang perl6>my @a = <1 2 4>; my @b = <1 2 4>; say @a," before ",@b," = ", @a before @b;
@a = <1 2 4>; @b = <1 2>; say @a," before ",@b," = ", @a before @b;
@a = <1 2>; @b = <1 2 4>; say @a," before ",@b," = ", @a before @b;
for 1..10 {
my @a = (^100).roll((2..3).pick); my @b = @a.map: { Bool.pick ?? $_ !! (^100).roll((0..2).pick) } say @a," before ",@b," = ", @a before @b;
}</lang>
- Output:
1 2 4 before 1 2 4 = False 1 2 4 before 1 2 = False 1 2 before 1 2 4 = True 63 52 before 0 52 = False 17 75 24 before 31 75 24 = True 43 32 before 43 32 = False 73 84 before 2 84 = False 73 92 before 40 24 46 = False 16 24 before 41 24 = True 9 12 22 before 9 12 32 67 = True 81 23 before 81 23 = False 55 53 1 before 55 62 83 = True 20 40 51 before 20 17 78 34 = False
PicoLisp
The built-in comparison functions already do this (not only for lists of numbers, but for any arbitrary data type). <lang PicoLisp>: (> (1 2 0 4 4 0 0 0) (1 2 1 3 2)) -> NIL</lang>
Pike
<lang Pike>int(0..1) order_array(array a, array b) {
if (!sizeof(a)) return true; if (!sizeof(b)) return false; if (a[0] == b[0]) return order_array(a[1..], b[1..]); return a[0] < b[0];
}</lang>
Pikes Array.sort_array()
function can sort an array of arrays using the <
operator, but it will sort longer arrays before shorter ones. Therefore the above function is still needed if the intent is to use the comparison for a sort operation.
If the numbers are in 32bit signed integer range, the following works too: <lang Pike>(string)a < (string)b;</lang>
PureBasic
<lang purebasic>DataSection
Array_1: Data.i 5 ;element count Data.i 1, 2, 3, 4, 5 ;element data Array_2: Data.i 6 Data.i 1, 2, 1, 5, 2, 2 Array_3: Data.i 5 Data.i 1, 2, 1, 5, 2 Array_4: Data.i 5 Data.i 1, 2, 1, 5, 2 Array_5: Data.i 4 Data.i 1, 2, 1, 6 Array_6: Data.i 5 Data.i 1, 2, 1, 6, 2
EndDataSection
- False = 0
- True = 1
- helper subrountine to initialize a dataset, *dataPtr points to the elementcount followed by the element data
Procedure initArrayData(Array a(1), *dataPtr)
Protected elementCount = PeekI(*dataPtr) Dim a(elementCount - 1) For i = 0 To elementCount - 1 *dataPtr + SizeOf(Integer) a(i) = PeekI(*dataPtr) Next
EndProcedure
- helper subroutine that returns 'True' or 'False' for a boolean input
Procedure.s booleanText(b)
If b: ProcedureReturn "True": EndIf ProcedureReturn "False"
EndProcedure
Procedure order(Array a(1), Array b(1))
Protected len_a = ArraySize(a()), len_b = ArraySize(b()), elementIndex
While elementIndex <= len_a And elementIndex <= len_b And a(elementIndex) = b(elementIndex) elementIndex + 1 Wend If (elementIndex > len_a And elementIndex <= len_b) Or (elementIndex <= len_b And a(elementIndex) <= b(elementIndex)) ProcedureReturn #True EndIf
EndProcedure
Dim A_1(0): initArrayData(A_1(), ?Array_1) Dim A_2(0): initArrayData(A_2(), ?Array_2) Dim A_3(0): initArrayData(A_3(), ?Array_3) Dim A_4(0): initArrayData(A_4(), ?Array_4) Dim A_5(0): initArrayData(A_5(), ?Array_5) Dim A_6(0): initArrayData(A_6(), ?Array_6)
If OpenConsole()
PrintN(booleanText(order(A_1(), A_2()))) ;False PrintN(booleanText(order(A_2(), A_3()))) ;False PrintN(booleanText(order(A_3(), A_4()))) ;False PrintN(booleanText(order(A_4(), A_5()))) ;True PrintN(booleanText(order(A_5(), A_6()))) ;True Print(#crlf$ + #crlf$ + "Press ENTER to exit"): Input() CloseConsole()
EndIf
</lang>
Sample output:
False False False True True
Python
The built-in comparison operators already do this: <lang python>>>> [1,2,1,3,2] < [1,2,0,4,4,0,0,0] False</lang>
Rascal
The built-in comparison operator already does this: <lang rascal>rascal>[2,1,3] < [5,2,1,3] bool: true</lang>
Ruby
The built-in <=>
operator already does this:
<lang ruby>>> ([1,2,1,3,2] <=> [1,2,0,4,4,0,0,0]) < 0
=> false</lang>
Standard ML
<lang sml>- List.collate Int.compare ([1,2,1,3,2], [1,2,0,4,4,0,0,0]) = LESS; val it = false : bool</lang>
Tcl
<lang tcl>proc numlist< {A B} {
foreach a $A b $B { if {$a<$b} { return 1 } elseif {$a>$b} { return 0 } } return 0
}</lang>
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT MODE DATA $$ numlists=* 1'2'1'3'2 1'2'0'4'4'0'0'0 1'2'3'4'5 1'2'1'5'2'2 1'2'1'6 1'2'1'6'2 1'2'4 1'2'4 1'2 1'2'4 $$ MODE TUSCRIPT list1="1'2'5'6'7" LOOP n,list2=numlists text=CONCAT (" ",list1," < ",list2) IF (list1<list2) THEN PRINT " true: ",text ELSE PRINT "false: ",text ENDIF list1=VALUE(list2) ENDLOOP </lang> Output:
false: 1'2'5'6'7 < 1'2'1'3'2 false: 1'2'1'3'2 < 1'2'0'4'4'0'0'0 true: 1'2'0'4'4'0'0'0 < 1'2'3'4'5 false: 1'2'3'4'5 < 1'2'1'5'2'2 true: 1'2'1'5'2'2 < 1'2'1'6 true: 1'2'1'6 < 1'2'1'6'2 true: 1'2'1'6'2 < 1'2'4 false: 1'2'4 < 1'2'4 false: 1'2'4 < 1'2 true: 1'2 < 1'2'4