Three List Manipulation Exercises
October 11, 2016
Writing in Scheme makes tasks like this simple:
(define xs '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))
(define (task1 xs) (filter even? xs))
> (task1 xs)
(2 4 6 8 10 12 14 16 18 20)
(define (task2 n xs)
(let loop ((xs xs) (k 1) (zs (list)))
(if (null? xs) (reverse zs)
(if (= k n) (loop (cdr xs) 1 zs)
(loop (cdr xs) (+ k 1) (cons (car xs) zs))))))
> (task2 3 xs)
(1 2 4 5 7 8 10 11 13 14 16 17 19 20)
(define (task3 xs)
(call-with-values
(lambda () (split (quotient (length xs) 2) xs))
(lambda (front back) (append back front))))
> (task3 xs)
(11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10)
Task1 requires only RnRS Scheme, and task3 uses split from the Standard Prelude. There is no standard procedure for deleting every nth item from a list, either in RnRS or the Standard Prelude or SRFI 1 (that surprised me, SRFI 1 has a function for everything), so I had to write a loop. I can’t imagine writing these functions in C.
You can run the program at http://ideone.com/RyzlpB.
Solution in Common Lisp :
http://pastebin.com/exe9KLP3
I’ve read on pastebin that the free pastebin account is automatically deleted if not used for a certain period of time. So I now use another paste site. See:
http://paste.lisp.org/display/328394
Solution in Ruby
def drop_odds(list) list.reject(&:odd?) end def remove_every_nth_item(n, list) list.each_slice(n).map { |l| l.take(n-1) }.flatten end def reverse_two_halves(list) n = list.size / 2 [list.take(n), list.drop(n)].reverse.flatten endSolution in Scala
“`
val xs= 1 to 20 toList
def drop_odds(list:List[Int])=list.filter(_% 2==0)
def filter_nth(list:List[Int],n:Int)=list.zipWithIndex.filter { case (_, i) => (i + 1) % n != 0 }.map { _._1}
def reverse_two_halves(list:List[Int])=list.splitAt(list.length/2) match{case (left:List[Int],right:List[Int])=>right++left}
println(drop_odds(xs))
println(filter_nth(xs,3))
println(reverse_two_halves(xs))
“`
Run the solution in scala here: http://ideone.com/1R7JMj
Here’s a solution in Java. The removeOddIntegers is a static method because it only works on LinkedLists of integers (whereas the other methods for the problem are class methods that work on LinkedLists of arbitrary type).
public class LinkedList<T> { public static class Node<T> { T data; Node<T> next = null; } Node<T> head; // Adds an element to the front of a LinkedList. public void add(T element) { Node<T> node = new Node<T>(); node.data = element; node.next = head; head = node; } @Override public String toString() { StringBuffer output = new StringBuffer("["); Node<T> current = head; while (current != null) { if (current != head) output.append(", "); output.append(current.data); current = current.next; } output.append("]"); return output.toString(); } public static void removeOddIntegers(LinkedList<Integer> list) { Node<Integer> dummy = new Node<Integer>(); dummy.next = list.head; Node<Integer> current = dummy; while (current != null) { if (current.next != null && current.next.data % 2 != 0) { current.next = current.next.next; } else { current = current.next; } } list.head = dummy.next; } public void removeEveryNthElement(int n) { Node<T> dummy = new Node<T>(); dummy.next = head; Node<T> current = dummy; int i = 1; while (current != null) { if (current.next != null && i % n == 0) { current.next = current.next.next; } else { current = current.next; } ++i; } head = dummy.next; } public int size() { Node<T> current = head; int size = 0; while (current != null) { ++size; current = current.next; } return size; } // Reverses a linked list. public void reverse() { Node<T> current = head; head = null; while (current != null) { Node<T> next = current.next; current.next = head; head = current; current = next; } } public void reverseHalves() { int size = size(); if (size < 2) return; reverse(); Node<T> current = head; int i = 0; int midpointIdx = size / 2; if (size % 2 == 0) --midpointIdx; Node<T> midpoint = null; while (true) { if (i == midpointIdx) midpoint = current; if (i == size - 1) { current.next = head; head = midpoint.next; midpoint.next = null; break; } ++i; current = current.next; } } public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<Integer>(); for (int i = 20; i >= 0; --i) list.add(i); System.out.println("list: " + list); removeOddIntegers(list); System.out.println("removeOddIntegers: " + list); int n = 2; list.removeEveryNthElement(n); System.out.println(String.format("removeEveryNthElement (n=%d): ", n) + list); list.reverseHalves(); System.out.println("reverseHalves: " + list); } }Output:
solutions in PHP:
1) without odd integers
function pares($A) {
$l=sizeof($A);
foreach ($A as $a => $v) {
if($v % 20) {
unset($A[$a]);}
}
return print_r($A);
}
2) without Nth element
function elemento($A,$B) {
$n=0;
foreach ($A as $a => $v) {
if(($B-1)==$n) {
unset($A[$a]);
}
$n++;
}
return print_r($A);
}
3) reversed
function rev_halv($A) {
$l=sizeof($A);
if($l % 2==0) {
$m=$l/2;
$odd=false;
}
else {
$m=($l-1)/2;
$odd=true;
}
$ays=array_chunk($A, $m , true);
$m1=array_reverse($ays[0],true);
$m2=array_reverse($ays[1],true);
if($odd) {
$m3=array_reverse($ays[2],true);
$m=$m1+$m3+$m2;
}
else {
$m=$m1+$m2;
}
return print_r($m);
}