Three More List Manipulation Exercises

October 14, 2016

Once again, Scheme makes these exercises simple. Here’s a sample list:

(define xs '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))

We give two solutions to the first task; both use the (make-list n x) function from the Standard Prelude:

(define (task1a xs ns)
  (reverse (apply append (map make-list ns xs))))

(define (task1b xs ns)
  (reverse (mappend make-list ns xs)))

> (task1a '(a b c) '(1 2 3))
(c c c b b a)
> (task1b '(a b c) '(1 2 3))
(c c c b b a)
> (task1a '(d c b a) '(3 0 0 1))
(a d d d)
> (task1b '(d c b a) '(3 0 0 1))
(a d d d)

The second of those two functions uses mappend from the Standard Prelude, which is like map except that it uses append instead of cons. You should get familiar with functions like mappend, because code you write with them is more concise and easier to read, and because it makes you think of the patterns in your coding. We also have two versions of the second task:

(define (task2a xs)
  (let loop ((xs xs) (odds (list)) (evens (list)))
    (cond ((null? xs) (append (reverse odds) (reverse evens)))
          ((odd? (car xs)) (loop (cdr xs) (cons (car xs) odds) evens))
          (else (loop (cdr xs) odds (cons (car xs) evens))))))

(define (task2b xs) (append (filter odd? xs) (filter even? xs)))

> (task2a xs)
(1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20)
> (task2b xs)
(1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20)

Again, using a suitable function, like filter, makes the code clear and concise. There is no loss of efficiency in using filter, and no reason to prefer the version using a loop. Again, we have two versions of the third function:

(define (task3a xs n)
  (let ((len (length xs)))
    (list-ref xs (- len n 1))))

(define (task3b xs n) (list-ref (reverse xs) n))

> (task3a xs 5)
15
> (task3b xs 5)
15

To my mind, the second version is simpler because it doesn’t require the auxiliary variable len, or the arithmetic of computing the index. You can run the program at http://ideone.com/iYhPhH, where you will also see mappend and make-list.

Advertisements

Pages: 1 2

7 Responses to “Three More List Manipulation Exercises”

  1. Daniel said

    Here’s a solution in Java.

    public class LinkedList<T> {
      public static class Node<U> {
        U data;
        Node<U> next;
      }
      
      Node<T> head;
      
      // Adds a node to the front of a LinkedList.
      public void add(T value) {
        Node<T> node = new Node<>();
        node.data = value;
        node.next = head;
        head = node;
      }
      
      @Override
      public String toString() {
        StringBuffer output = new StringBuffer("[");
        for (Node<T> n = head; n != null; n = n.next) {
          if (n != head) output.append(", ");
          output.append(n.data);
        }
        output.append("]");
        return output.toString();
      }
      
      // Reverses a linked list in-place.
      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 static <U> LinkedList<U> repeats(
          LinkedList<U> list, LinkedList<Integer> counts) {
        LinkedList<U> output = new LinkedList<>();
        Node<U> current = list.head;
        Node<Integer> currentCount = counts.head;
        while (current != null && currentCount != null) {
          for (int i = 0; i < currentCount.data; ++i) {
            output.add(current.data);
          }
          current = current.next;
          currentCount = currentCount.next;
        }
        return output;
      }
      
      public static LinkedList<Integer> rearrange(LinkedList<Integer> list) {
        LinkedList<Integer> output = new LinkedList<Integer>();
        for (Node<Integer> n = list.head; n != null; n = n.next) {
          if (n.data % 2 != 0) output.add(n.data);
        }
        for (Node<Integer> n = list.head; n != null; n = n.next) {
          if (n.data % 2 == 0) output.add(n.data);
        }
        output.reverse();
        return output;
      }
      
      // n = 0 returns the last element.
      // Will throw an NPE if n is negative or too big (which is always the case for
      // an empty list).
      public T nthFromEnd(int n) {
        Node<T> nthFromEnd = null;
        int count = 0;
        for (Node<T> node = head; node != null; node = node.next) {
          if (nthFromEnd != null) nthFromEnd = nthFromEnd.next;
          if (count++ == n) nthFromEnd = head;
        }
        return nthFromEnd.data;
      }
      
      public static void main(String[] args) {
        int size = 10;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = size-1; i >= 0; --i) list.add(i);
        System.out.println("list:\n  " + list);
        LinkedList<Integer> counts = new LinkedList<>();
        for (int i = 0; i < size; ++i) counts.add(i % 2 == 0 ? 1 : 2);
        System.out.println("counts:\n  " + counts);
        System.out.println("repeats(list, counts):\n  " + repeats(list, counts));
        System.out.println("rearrange(list):\n  " + rearrange(list));
        int n = 3;
        System.out.println(
            String.format("list.nthFromEnd(%d):\n  ", n) + list.nthFromEnd(n));
      }
    
    }
    

    Output:

    list:
      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    counts:
      [2, 1, 2, 1, 2, 1, 2, 1, 2, 1]
    repeats(list, counts):
      [9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1, 0, 0]
    rearrange(list):
      [1, 3, 5, 7, 9, 0, 2, 4, 6, 8]
    list.nthFromEnd(3):
      6
    
  2. V said
    
    def task_1(a, b)
      a.zip(b).flat_map { |x, n| n.times.map { x } }.reverse
    end
    
    def task_2(list)
      list.partition(&:odd?).flatten
    end
    
    def task_3(list, n)
      list.reverse[n]
    end
    
    
  3. My solution in clojure:

    (defn t1 [l1 l2]
      (mapcat #(repeat %2 %1) (reverse l1) l2))
    
    (defn t2 [l]
      (flatten (conj (filter even? l) (filter odd? l))))
    
    (defn t3 [l n]
      (nth (reverse l) n ))
    

    Output:

    (t1 ‘(2 3 4 1) ‘(4 5 6 1)) => (1 1 1 1 4 4 4 4 4 3 3 3 3 3 3 2)

    (t2 ‘(1 2 3 4 5 6 7 8)) => (1 3 5 7 2 4 6 8)

    (t3 ‘(1 2 3 4 5 5 6 7) 3) => 5

  4. Daniel said

    @miguelpinia, it looks like we had different interpretations of task 1. I associated “reverse order” with the returned list. It looks like you associated “reverse order” with the input list.

    Here’s the Clojure version of my interpretation, based on your code.

    (defn t1 [l1 l2]
      (reverse (mapcat #(repeat %2 %1) l1 l2)))
    

    @V, are your functions intended to operate on Ruby Arrays? My interpretation of the problem was that ‘list’ refers to ‘linked list’ (based on the comment, “… practice with linked lists”), but after reading again I see that the tasks all say ‘list’, not ‘linked list’.

  5. V said

    @miguelpinia There are no build-in linked lists in Ruby, so my implementation is intended for Arrays. I thought for this simple exercise LinkedList, List or Array could be used interchangeably.

  6. matthew said

    @Daniel: It does mention “practice with linked lists” in the first line. Makes a nice exercise in pointer manipulation. Here’s C++ solutions to a couple of the previous set of exercises and the odd/even rearrangement problem:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
      Node(int n_, Node* next_) : n(n_), next(next_) {}
      int n; Node *next;
    };
    
    void removeodd(Node **p) {
      while(*p) {
        if ((*p)->n%2) {
          *p = (*p)->next;
        } else {
          p = &(*p)->next;
        }
      }
    }
    
    void swaphalves(Node **p) {
      if(!*p) return;
      int i, j; Node *q = *p, *r = *p;
      for (i = 1; q->next; i++, q = q->next);
      for (j = 1; j < i/2; j++, r = r->next);
      q->next = *p; *p = r->next; r->next = 0;
    }
    
    void split(Node **root) {
      Node **oend = root, *estart = 0, **eend = &estart;
      for (Node *p = *root; p; p = p->next) {
        if (p->n%2) {
          *oend = p; oend = &p->next;
        } else {
          *eend = p; eend = &p->next;
        }
      }
      *oend = estart; *eend = 0;
    }
    
    void show(Node *p) {
      printf("[ ");
      for ( ; p; p = p->next) {
        printf("%d ", p->n);
      }
      printf("]\n");
    }
    
    int main(int argc, char *argv[]) {
      Node *s = 0;
      for (int i = 1; i < argc; i++) {
        s = new Node(atoi(argv[argc-i]),s);
      }
      show(s);
      split(&s); show(s);
      swaphalves(&s); show(s);
      removeodd(&s); show(s);
    }
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: