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.

Pages: 1 2

7 Responses to “Three List Manipulation Exercises”

  1. 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

  2. V said

    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
    end
    
    
  3. Ilija said

    Solution 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))

    “`

  4. Ilija said

    Run the solution in scala here: http://ideone.com/1R7JMj

  5. Daniel said

    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:

    list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
    removeOddIntegers: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
    removeEveryNthElement (n=2): [0, 4, 8, 12, 16, 20]
    reverseHalves: [8, 4, 0, 20, 16, 12]
    
  6. Aquiles Peña said

    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);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: