Puzzle 8-12-08 (Spoiler)

bearophile bearophileHUGS at lycos.com
Tue Aug 12 14:42:29 PDT 2008


Wyverex Wrote:

> 1)First is simple..
> What's the  "condition" so that the following code
> snippet  prints both HelloWorld !

I have no idea yet. Condition can be a function that prints things by itself, but that's cheating.


> 2)Next little data structure knowledge need
> You are provided with two stacks, and pop() and push() functions for 
> them. You have to implement queue i.e. enqueue() and dequeue() using the 
> available operations.

import std.stdio: putr = writefln, format;

class Stack(T) {
    T[] data;
    void push(T el) { this.data ~= el; }
    T pop() {
        T aux = this.data[$-1];
        this.data.length = this.data.length - 1;
        return aux;
    }
    string toString() {
        return format("Stack(%s)", this.data);
    }
    int length() {
        return this.data.length;
    }
    void length(int n) {
        this.data.length = n;
    }
    void reverse() {
        if (this.data.length)
            this.data.reverse;
    }
}

class Queue(T) {
    // Modified from Cookbook Recipe 68436
    Stack!(T) back, forward;
    this() {
        back = new typeof(back);
        forward = new typeof(forward);
    }
    T dequeue() {
        if (this.forward.length)
            return this.forward.pop();
        else {
            this.back.reverse();
            auto aux = this.forward;
            this.forward = this.back;
            this.back = aux;
            return this.forward.pop();
        }
    }
    void enqueue(T el) { this.back.push(el); }
}

import std.stdio: put = writef, putr = writefln;

// a bit of testing
void main() {
    int n = 8;
    int m = 2;

    auto q = new Queue!(int);
    for (int i; i < n; i++) {
        q.enqueue(i);
        putr("enqueue: ", i);
    }
    putr();
    for (int i; i < n; i++)
        putr("dequeue: ", q.dequeue());

    for (int i; i < m; i++) {
        for (int j; j < 2; j++) {
            q.enqueue(j);
            putr("enqueue: ", j);
        }
        putr();
        for (int j; j < 2; j++)
            putr("dequeue: ", q.dequeue());
    }
    putr();
    for (int i; i < m; i++) {
         for (int j; j < 12; j++) {
            q.enqueue(j);
            putr("enqueue: ", j);
        }
        putr();
        for (int j; j < 12; j++)
            putr("dequeue: ", q.dequeue());
    }
}


> 3) little string manipulation
> How do you reverse the words in a string?
> "My name is Amit Agarwal"
> to
> "Agarwal Amit is name My"
> **try without using the library!

Python:

# not using string functions, nor slices
from array import array

def reverse(s, start, stop):
    n = stop - start + 1
    for i in xrange(n // 2):
        s[start + i], s[stop - i] = s[stop - i], s[start + i]

s = array("c", " My name  is Amit Agarwal 2")

reverse(s, 0, len(s)-1)
start = -1
for pos, c in enumerate(s):
    if c in " \t\n\r":
        if start != -1:
            reverse(s, start, pos-1)
            start = -1
    else:
        if start == -1:
            start = pos

print s
(using slices and string methods it's simpler)


D:

import std.stdio: putr = writefln;

void reverse(T)(T[] s, int start, int stop) {
    int n = stop - start + 1;
    for (int i; i < n/2; i++) {
        // swap
        T aux = s[start + i];
        s[start + i] = s[stop - i];
        s[stop - i] = aux;
    }
}

void main() {
    string s = " My name  is Amit Agarwal 0".dup;

    s.reverse;
    int start = -1;
    foreach (pos, c; s)
        if (c==' ' || c=='\t' || c=='\n' || c=='\r') {
            if (start != -1) {
                reverse(s, start, pos-1);
                start = -1;
            }
        } else
            if (start == -1)
                start = pos;

    putr('"', s, '"');
}

(One bug found translating from Python to D: those brackets are necessary!)

Most languages have a page with puzzles meant to be solved with that language, so I suggest you to create a Wiki page with such problems, plus the solutions shown by people too under a spoiler link.

Bye,
bearophile


More information about the Digitalmars-d-learn mailing list