# HG changeset patch # User Louis Opter # Date 1372746358 25200 # Node ID 6bebf4b42ebca693366d3685cc0410f7f1659f3e # Parent 8f77e48d3704b08b4be9d2657325751b4c64ff01 Correctly format the stacks and lists exercices diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/fifo_from_two_lifos/fifo.c --- 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 -#include -#include - -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; -} diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/fifo_from_two_lifos/question.rst --- /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). diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/fifo_from_two_lifos/solution.c --- /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 +#include +#include + +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; +} diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/pancakes/pancakes.py --- 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]) diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/pancakes/question.rst --- /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). diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/pancakes/solution.py --- /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]) diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/remove_list_duplicates/question.rst --- /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? diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/remove_list_duplicates/remove_duplicates.c --- 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 -#include -#include - -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; -} diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/remove_list_duplicates/solution.c --- /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 +#include +#include + +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; +} diff -r 8f77e48d3704 -r 6bebf4b42ebc stacks_lists/remove_list_duplicates/solution.py --- /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))