Mercurial > louis > peeves

changeset 2:6bebf4b42ebc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Correctly format the stacks and lists exercices
author Louis Opter <kalessin@kalessin.fr>
date Mon, 01 Jul 2013 23:25:58 -0700
parents 8f77e48d3704
children 1f4c37678f69
files stacks_lists/fifo_from_two_lifos/fifo.c stacks_lists/fifo_from_two_lifos/question.rst stacks_lists/fifo_from_two_lifos/solution.c stacks_lists/pancakes/pancakes.py stacks_lists/pancakes/question.rst stacks_lists/pancakes/solution.py stacks_lists/remove_list_duplicates/question.rst stacks_lists/remove_list_duplicates/remove_duplicates.c stacks_lists/remove_list_duplicates/solution.c stacks_lists/remove_list_duplicates/solution.py
diffstat 10 files changed, 283 insertions(+), 252 deletions(-) [+]
line wrap: on
line diff
--- a/stacks_lists/fifo_from_two_lifos/fifo.c	Sun Jun 30 23:43:41 2013 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,117 +0,0 @@
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-struct lifo
-{
-    struct lifo *next;
-    int         value;
-};
-
-struct fifo
-{
-    struct lifo *head;
-    struct lifo *tail;
-};
-
-void
-push(struct lifo **head, struct lifo *e)
-{
-    assert(e);
-
-    e->next = *head;
-    *head = e;
-}
-
-struct lifo *
-pop(struct lifo **head)
-{
-    assert(head);
-
-    if (!*head)
-        return NULL;
-    struct lifo *e = *head;
-    *head = e->next;
-    return e;
-}
-
-void
-print(struct lifo *head)
-{
-    for (; head; head = head->next)
-        printf("%d ", head->value);
-    printf("\n");
-}
-
-
-void
-enqueue(struct fifo *queue, int value)
-{
-    struct lifo *new_head = calloc(1, sizeof(*new_head));
-    new_head->value = value;
-    push(&queue->head, new_head);
-
-    struct lifo *new_tail = calloc(1, sizeof(*new_head));
-    new_tail->value = value;
-    if (!queue->tail) {
-        push(&queue->tail, new_tail);
-        return;
-    }
-    struct lifo *reversed = NULL;
-    for (struct lifo *it = pop(&queue->tail); it; it = pop(&queue->tail))
-        push(&reversed, it);
-    push(&reversed, new_tail);
-    for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
-        push(&queue->tail, it);
-}
-
-int
-dequeue(struct fifo *queue)
-{
-    assert(queue->tail);
-    assert(queue->head);
-
-    struct lifo *e;
-
-    if (queue->head == queue->tail)  {
-        e = queue->tail;
-        queue->tail = NULL;
-        free(queue->head);
-        queue->head = NULL;
-    } else {
-        e = pop(&queue->tail);
-        struct lifo *reversed = NULL;
-        for (struct lifo *it = pop(&queue->head); it; it = pop(&queue->head))
-            push(&reversed, it);
-        free(pop(&reversed));
-        for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
-            push(&queue->head, it);
-    }
-
-    int ret = e->value;
-    free(e);
-    return ret;
-}
-
-
-int
-main(void)
-{
-    struct fifo queue = { .head = NULL, .tail = NULL };
-
-    for (int i = 0; i != 5; i++)
-        enqueue(&queue, i);
-
-    print(queue.head);
-    print(queue.tail);
-
-    printf("dequeue(&queue) = %d\n", dequeue(&queue));
-    printf("dequeue(&queue) = %d\n", dequeue(&queue));
-    printf("dequeue(&queue) = %d\n", dequeue(&queue));
-    enqueue(&queue, 42);
-    printf("dequeue(&queue) = %d\n", dequeue(&queue));
-    printf("dequeue(&queue) = %d\n", dequeue(&queue));
-    printf("dequeue(&queue) = %d\n", dequeue(&queue));
-
-    return EXIT_SUCCESS;
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/fifo_from_two_lifos/question.rst	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,6 @@
+FIFO From Two LIFOs
+===================
+
+Build a queue (i.e: a list where you queue new elements at the head and dequeue
+elements at the tail) from two stacks (i.e: a list where you push and pop at
+the head).
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/fifo_from_two_lifos/solution.c	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,117 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct lifo
+{
+    struct lifo *next;
+    int         value;
+};
+
+struct fifo
+{
+    struct lifo *head;
+    struct lifo *tail;
+};
+
+void
+push(struct lifo **head, struct lifo *e)
+{
+    assert(e);
+
+    e->next = *head;
+    *head = e;
+}
+
+struct lifo *
+pop(struct lifo **head)
+{
+    assert(head);
+
+    if (!*head)
+        return NULL;
+    struct lifo *e = *head;
+    *head = e->next;
+    return e;
+}
+
+void
+print(struct lifo *head)
+{
+    for (; head; head = head->next)
+        printf("%d ", head->value);
+    printf("\n");
+}
+
+
+void
+enqueue(struct fifo *queue, int value)
+{
+    struct lifo *new_head = calloc(1, sizeof(*new_head));
+    new_head->value = value;
+    push(&queue->head, new_head);
+
+    struct lifo *new_tail = calloc(1, sizeof(*new_head));
+    new_tail->value = value;
+    if (!queue->tail) {
+        push(&queue->tail, new_tail);
+        return;
+    }
+    struct lifo *reversed = NULL;
+    for (struct lifo *it = pop(&queue->tail); it; it = pop(&queue->tail))
+        push(&reversed, it);
+    push(&reversed, new_tail);
+    for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
+        push(&queue->tail, it);
+}
+
+int
+dequeue(struct fifo *queue)
+{
+    assert(queue->tail);
+    assert(queue->head);
+
+    struct lifo *e;
+
+    if (queue->head == queue->tail)  {
+        e = queue->tail;
+        queue->tail = NULL;
+        free(queue->head);
+        queue->head = NULL;
+    } else {
+        e = pop(&queue->tail);
+        struct lifo *reversed = NULL;
+        for (struct lifo *it = pop(&queue->head); it; it = pop(&queue->head))
+            push(&reversed, it);
+        free(pop(&reversed));
+        for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
+            push(&queue->head, it);
+    }
+
+    int ret = e->value;
+    free(e);
+    return ret;
+}
+
+
+int
+main(void)
+{
+    struct fifo queue = { .head = NULL, .tail = NULL };
+
+    for (int i = 0; i != 5; i++)
+        enqueue(&queue, i);
+
+    print(queue.head);
+    print(queue.tail);
+
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    enqueue(&queue, 42);
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+
+    return EXIT_SUCCESS;
+}
--- a/stacks_lists/pancakes/pancakes.py	Sun Jun 30 23:43:41 2013 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,62 +0,0 @@
-#!/usr/bin/env python
-
-
-def flip_pancakes(pancakes, index):
-    print(
-        "{0} → flip at {1} ({2}) (biggest_sorted={3}, biggest_unsorted={4}) → ".format(
-            pancakes, index, pancakes[index], pancakes[find_biggest_sorted(pancakes)], pancakes[find_biggest_unsorted(pancakes)]
-        ),
-        end=""
-    )
-    for i in range(int((index + 1) / 2)):
-        tmp = pancakes[index - i]
-        pancakes[index - i] = pancakes[i]
-        pancakes[i] = tmp
-    print("{0}".format(pancakes))
-
-
-def is_sorted(pancakes):
-    for i in range(1, len(pancakes)):
-        if pancakes[i - 1] > pancakes[i]:
-            return False
-    return True
-
-
-def find_biggest(pancakes):
-    biggest = pancakes[0]
-    biggest_idx = 0
-    for i in range(1, len(pancakes)):
-        if pancakes[i] > biggest:
-            biggest = pancakes[i]
-            biggest_idx = i
-    return biggest_idx
-
-
-def find_biggest_sorted(pancakes):
-    for i in reversed(range(1, len(pancakes))):
-        if i != find_biggest(pancakes[:i + 1]):
-            return i
-    return 0
-
-
-def find_biggest_unsorted(pancakes):
-    biggest = pancakes[0]
-    biggest_idx = 0
-    for i in range(1, find_biggest_sorted(pancakes) + 1):
-        if pancakes[i] > biggest:
-            biggest = pancakes[i]
-            biggest_idx = i
-    return biggest_idx
-
-
-def sort_pancakes(pancakes):
-    while not is_sorted(pancakes):
-        biggest_unsorted = find_biggest_unsorted(pancakes)
-        flip_pancakes(pancakes, biggest_unsorted)
-        biggest_sorted = find_biggest_sorted(pancakes)
-        flip_pancakes(pancakes, biggest_sorted)
-        biggest_unsorted = find_biggest_unsorted(pancakes)
-
-
-if __name__ == "__main__":
-    sort_pancakes([7, 5, 4, 8, 2, 1])
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/pancakes/question.rst	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,8 @@
+Pancakes Stack
+==============
+
+You have a stack of pancakes of different diameters. You can modify the stack
+by inserting a spatula between two pancakes and flip over the stack on top of
+the spatula.
+
+Sort the stack in increasing order (i.e: the biggest pancake at the bottom).
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/pancakes/solution.py	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,63 @@
+#!/usr/bin/env python
+
+# This probably could be simplified.
+
+def flip_pancakes(pancakes, index):
+    print(
+        "{0} → flip at {1} ({2}) (biggest_sorted={3}, biggest_unsorted={4}) → ".format(
+            pancakes, index, pancakes[index], pancakes[find_biggest_sorted(pancakes)], pancakes[find_biggest_unsorted(pancakes)]
+        ),
+        end=""
+    )
+    for i in range(int((index + 1) / 2)):
+        tmp = pancakes[index - i]
+        pancakes[index - i] = pancakes[i]
+        pancakes[i] = tmp
+    print("{0}".format(pancakes))
+
+
+def is_sorted(pancakes):
+    for i in range(1, len(pancakes)):
+        if pancakes[i - 1] > pancakes[i]:
+            return False
+    return True
+
+
+def find_biggest(pancakes):
+    biggest = pancakes[0]
+    biggest_idx = 0
+    for i in range(1, len(pancakes)):
+        if pancakes[i] > biggest:
+            biggest = pancakes[i]
+            biggest_idx = i
+    return biggest_idx
+
+
+def find_biggest_sorted(pancakes):
+    for i in reversed(range(1, len(pancakes))):
+        if i != find_biggest(pancakes[:i + 1]):
+            return i
+    return 0
+
+
+def find_biggest_unsorted(pancakes):
+    biggest = pancakes[0]
+    biggest_idx = 0
+    for i in range(1, find_biggest_sorted(pancakes) + 1):
+        if pancakes[i] > biggest:
+            biggest = pancakes[i]
+            biggest_idx = i
+    return biggest_idx
+
+
+def sort_pancakes(pancakes):
+    while not is_sorted(pancakes):
+        biggest_unsorted = find_biggest_unsorted(pancakes)
+        flip_pancakes(pancakes, biggest_unsorted)
+        biggest_sorted = find_biggest_sorted(pancakes)
+        flip_pancakes(pancakes, biggest_sorted)
+        biggest_unsorted = find_biggest_unsorted(pancakes)
+
+
+if __name__ == "__main__":
+    sort_pancakes([7, 5, 4, 8, 2, 1])
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/remove_list_duplicates/question.rst	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,11 @@
+Remove Duplicates From a List
+=============================
+
+Write a function that takes a list in input and remove duplicates elements from
+the list. The order of the elements in the list must not change.
+
+Twists
+------
+
+- Keep the last duplicated element instead of the last one.
+- What is the time complexity?
--- a/stacks_lists/remove_list_duplicates/remove_duplicates.c	Sun Jun 30 23:43:41 2013 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,73 +0,0 @@
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-struct list
-{
-    struct list *next;
-    struct list *prev;
-    int         value;
-};
-
-void
-print(struct list *head)
-{
-    for (; head; head = head->next)
-        printf("%d ", head->value);
-    printf("\n");
-};
-
-void
-insert(struct list **head, int value)
-{
-    struct list *node = malloc(sizeof(*node));
-    node->prev = NULL;
-    node->next = *head;
-    node->value = value;
-    if (*head)
-        (*head)->prev = node;
-    *head = node;
-}
-
-struct list *
-remove_node(struct list *node)
-{
-    assert(node);
-    node->prev->next = node->next;
-    if (node->next)
-        node->next->prev = node->prev;
-    struct list *next = node->next;
-    free(node);
-    return next;
-}
-
-void
-remove_duplicates(struct list *head)
-{
-    for (struct list *target = head; target; target = target->next) {
-        for (struct list *it = target->next; it;) {
-            if (it->value == target->value) {
-                it = remove_node(it);
-            } else {
-                it = it->next;
-            }
-        }
-    }
-}
-
-int
-main(void)
-{
-    struct list *head = NULL;
-
-    for (int i = 5; i != 0; i--)
-        insert(&head, i);
-    for (int i = 1; i <= 5; i++)
-        insert(&head, i);
-    
-    print(head);
-    remove_duplicates(head);
-    print(head);
-
-    return EXIT_SUCCESS;
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/remove_list_duplicates/solution.c	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,73 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct list
+{
+    struct list *next;
+    struct list *prev;
+    int         value;
+};
+
+void
+print(struct list *head)
+{
+    for (; head; head = head->next)
+        printf("%d ", head->value);
+    printf("\n");
+};
+
+void
+insert(struct list **head, int value)
+{
+    struct list *node = malloc(sizeof(*node));
+    node->prev = NULL;
+    node->next = *head;
+    node->value = value;
+    if (*head)
+        (*head)->prev = node;
+    *head = node;
+}
+
+struct list *
+remove_node(struct list *node)
+{
+    assert(node);
+    node->prev->next = node->next;
+    if (node->next)
+        node->next->prev = node->prev;
+    struct list *next = node->next;
+    free(node);
+    return next;
+}
+
+void
+remove_duplicates(struct list *head)
+{
+    for (struct list *target = head; target; target = target->next) {
+        for (struct list *it = target->next; it;) {
+            if (it->value == target->value) {
+                it = remove_node(it);
+            } else {
+                it = it->next;
+            }
+        }
+    }
+}
+
+int
+main(void)
+{
+    struct list *head = NULL;
+
+    for (int i = 5; i != 0; i--)
+        insert(&head, i);
+    for (int i = 1; i <= 5; i++)
+        insert(&head, i);
+    
+    print(head);
+    remove_duplicates(head);
+    print(head);
+
+    return EXIT_SUCCESS;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/remove_list_duplicates/solution.py	Mon Jul 01 23:25:58 2013 -0700
@@ -0,0 +1,5 @@
+#!/usr/bin/env python
+
+# Not bad, but it will change the order of the elements in the list:
+def remove_list_duplicates(l):
+    return list(set(l))