LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#26 July 5 2010

GN90

Re: Quizz of the Day

Reverse a single connected linked list. Best optimized algo (performance first, then memory usage) wins.

so is this correct ?

struct node{ int data ; node * next }

node* reverse (node * list) {

           node *pt , *temp ;

           pt = list.next ;
           list.next = null ;
           while (pt != null){
                  temp = pt.next ;
                  pt.next = list ;
                  list = pt ;
                  pt = temp ;
           }
           return list ;
}

Last edited by GN90 (July 5 2010)

Offline

#27 July 6 2010

arithma

Re: Quizz of the Day

@GN90, you got it right.

The algorithm should be easier to think about in those terms that helped me while deriving the same algo, but in a recursive style:

void reverse_recursive( node * & rev, node * rest ){
	if(rest == 0) return;

	node * next = rest->next;
	rest->next = rev;
	rev = rest;
	reverse_recursive(rev, next);
}

Here's some code that I used to confirm your posted code and mine.
Your turn to question our abilities!


#include <iostream>
using namespace std;

struct node {
	int data;
	node * next;
};

node* reverse (node * list) {
	node *pt , *temp ;

	pt = list->next ;
	list->next = 0 ;
	while (pt != 0){
		temp = pt->next ;
		pt->next = list ;
		list = pt ;
		pt = temp ;
	}
	return list ;
}

void reverse_recursive( node * & rev, node * rest ){
	if(rest == 0) return;

	node * next = rest->next;
	rest->next = rev;
	rev = rest;
	reverse_recursive(rev, next);
}

void spit_list(node * p){
	while(p != 0) {
		cout << p->data << endl;
		p = p->next;
	}
}

void main(){
	node a = {1, 0};
	node b = {2, 0};
	node c = {3, 0};
	node d = {4, 0};

	a.next = &b;
	b.next = &c;
	c.next = &d;

	node * p = reverse(&a);
	spit_list(p);

	node * reverse = 0;
	reverse_recursive(reverse, p);
	spit_list(reverse);
}

Last edited by arithma (July 6 2010)

Offline

#28 July 6 2010

Ayman

Re: Quizz of the Day

Here is my entry in Java, not recursive but does the job, I should have posted it earlier yesterday

public void reverseList() 
{
    ListNode current = head;
    head = null;
    while (current != null) 
    {
        ListNode ptr = current;
        current = current.next;
        ptr.next = head;
        head = ptr;
    }
}

Same algo as GN90 actually :)

Last edited by Ayman (July 6 2010)

Offline

#29 July 6 2010

arithma

Re: Quizz of the Day

OK, here's one I haven't had the chance to solve yet (the problem is my original)

On christmas, our office has a secret santa event. Everyone's name is put into a bowl. Each employee comes in random order, and picks a name from the bowl (there is the unfortunate possibility of one picking their own name).

Looking at the (employee name - A, name of employee on card - B), there must be at least one loop (starting with a random employee, then going to the next employee based on the card the previous one chose).

A loop configuration is a list of the size of loops in ascending order.
An employee configuration is a list of numbers, giving each employee the number of the other employee on the car he chose.

For n employees, there are n! employee configurations.

Return, given n, the number of employee configurations for each loop configuration.

Example: n=1
{Loop Configurations, Corresponding employee configurations} = {(1), 1} -- there is only one loop possible, the employee to himself. There is only one employee configuration to begin with.

Example: n=2
{Loop, Configs} = {(2), 1}
{Loop, Configs} = {(1, 1), 1}
Either a loop of two employees, each being the santa of the other, or two loops, each employee being the santa of himself.
The sum of configs sums to 2! which is 2.

Example: n=3
{(3), 2}
{(2, 1), 3}
{(1, 1, 1), 1}
There are 3! employee configs in total. Each one being the santa of himself amounts to a single config. A loop going through all the employees has two possibilities (one in each direction (1, 2, 0) or (2, 0, 1) ). The rest of configurations belong to the middle case. Those configs are detailed below:
(0, 2, 1)
(2, 1, 0)
(1, 0, 2)

I haven't come down to an implementation yet, but the problem itself needs some understanding. I am working on my writing-a-problem skills, so please let me know where it needs clarification.

Offline

#30 July 6 2010

GN90

Re: Quizz of the Day

@ arithma : i didn't understand what should we do in the question you've posted

And here's my question: (its not a programing question cause I don't know what to post)

A drinks machine offers three selections - Tea, Coffee or Random
(Either tea or Coffee)but the machine has been wired up wrongly
so that each button does not give what it claims. If each drink
costs 50p, how much minimum money do you have to put into the
machine to find out which button gives which selection?

Offline

#31 July 6 2010

arithma

Re: Quizz of the Day

@GN90: The challenge itself is to figure out what the question is about, jokingly. I admit I failed to make it clear what the question is about.

I believe your question was asked and answered somewhere on this forum before. Something about entering a single coin and hitting random. The result determines what random is wired to. If it's coffee, then coffee button is tea, and tea button is random.

I think the question is more interesting if the wiring is done really randomly (with the possibility of a correct wiring).

Offline

#32 July 6 2010

GN90

Re: Quizz of the Day

arithma wrote:

@GN90: The challenge itself is to figure out what the question is about, jokingly. I admit I failed to make it clear what the question is about.

I believe your question was asked and answered somewhere on this forum before. Something about entering a single coin and hitting random. The result determines what random is wired to. If it's coffee, then coffee button is tea, and tea button is random.

I think the question is more interesting if the wiring is done really randomly (with the possibility of a correct wiring).

yeah , maybe it was asked.
and your answer is correct , sorry for this stupid question anyways

and it should be your turn now.

Offline

#33 July 6 2010

Joe

Re: Quizz of the Day

I think the question is more interesting if the wiring is done really randomly (with the possibility of a correct wiring).

Not really, since there is no way of solving this. If the wiring is done completely randomly, then there's no possibility of actually knowing. Think about it, the random button could (theoretically) give out Tea a million times straight. So technically there is no minimum amount of tries that guarantees a solution.

What would be impressive though is to modelize what I just wrote in a mathematical equation (or set of equations) that cannot be solved, thus proving that there is no way of finding a minimum value (Do I make sense to anyone ?)

Offline

#34 July 7 2010

arithma

Re: Quizz of the Day

To prove what you just said, the random button can return the same type of cup indefinitely, rendering any attempt to discover what the wiring is inept. Still, the truly random wiring is the more possible situation to face in real life.

I was thinking more about the problem being an optimization problem over the space of click sequence.
As in, what is the click sequence that will maximize your certainty (or minimize your uncertainty) about the wiring of the machine.

Machine has three Buttons: A, B, C; the types of drinks are A, B, R(random).

Think of this example sequence:

Click A. Returns A (we are calling the first drink it returns A to avoid unnecessary symmetry). 50% -> (A is wired to A) & 50% -> (A is wired to R)
Then Click B. case 1: Returns A: C is most definitely wired to B.
                    case 2: Returns B: All hell is loose probability wise.

I think the most suiting representation for the probabilities would be some kind of tree with assumptions and their probabilities as branches. We'd also have to represent the click sequences.
The difficulty is insane since we're modeling logic, and basing other logic on top of that.

Offline

#35 August 17 2010

arithma

Re: Quizz of the Day

I thought you guys should read a blog post inspired by this thread: http://mskafi.blogspot.com/2010/08/so-i … -suck.html

Offline

#36 August 19 2010

Ayman

Re: Quizz of the Day

Write a function to check if a number is Happy Number or not.

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers[1]).

e.g. 7 is happy, as the associated sequence is:

7^2 = 49
4^2 + 9^2 = 97
9^2 + 7^2 = 130
1^2 + 3^2 + 0^2 = 10
1^2 + 0^2 = 1

For more information you can refer to http://en.wikipedia.org/wiki/Happy_number Good luck :)

P.S. This is a classic exercise but I just thought of making this thread live again. :)

Last edited by Ayman (August 19 2010)

Offline

#37 August 19 2010

arithma

Re: Quizz of the Day

#include <iostream>
using namespace std;

typedef unsigned int uint;

uint next(uint n){
	uint sum = 0;

	while(n > 0){
		uint digit = n % 10;
		sum += digit * digit;
		n /= 10;
	}

	return sum;
}

void main(){
	uint slow, fast;
	cout << "Enter number: ";
	cin >> slow;
	fast = next(slow);

	while(slow != fast){
		slow = next(slow);
		fast = next(next(fast));

		cout << slow << "-" << fast << endl;
	}

	cout << "slow = " << slow << endl;
	if(slow == 1)
		cout << ":)\n";
	else
		cout << ":(\n";
}

The idea is simple. If you have a loop, two operations per step versus one operation per step will collide with each other.
This eliminates the need to store or memorize what happened before to compare against.

Offline

#38 August 19 2010

J4D

Re: Quizz of the Day

kteer belkon fadi !

Offline

#39 August 19 2010

Ayman

Re: Quizz of the Day

kteer belkon fadi !

Niyelna

Offline

#40 August 19 2010

xterm
Moderator

Re: Quizz of the Day

Here's a translation of arithma's implementation into F#

let f x =
    x.ToString().ToCharArray()
    |> Seq.map (fun c -> pown ((int c) - 48) 2)
    |> Seq.sum

let happy n next =
    let rec compare a b =
        match a = b with
        | true -> a
        | false -> compare (next a) (next (next b))
    compare n (next n)

Example: 4 numbers (true means happy) :

Code: [7;20;92;487] |> Seq.map (fun x -> happy x f = 1)

Output:  [true; false; false; true]


Example: Number of happy numbers between 1 and 1000

Code: [1 .. 1000] |> Seq.map (fun x -> happy x f) |> Seq.filter (fun x -> x = 1 ) |> Seq.sum

Output: 143

Last edited by xterm (August 19 2010)

Offline

#41 August 19 2010

Joudi416

Re: Quizz of the Day

arithma wrote:

The idea is simple. If you have a loop, two operations per step versus one operation per step will collide with each other.
This eliminates the need to store or memorize what happened before to compare against.

could this be used in C# too? or the only way is to save the sums in a list?

btw here's my C# version:

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication13
{
    class Program
    {
        static void Main(string[] args)
        {
            uint n, s = 0;
            bool b=false;
            Console.Write("Enter a positif number to find out it's mood:");
            n = uint.Parse(Console.ReadLine());
            List<uint> li=new List<uint>();
            while(n!=1 && b==false)
            {
                li.Add(n);
                while (n != 0)
                {
                    s += (n % 10) * (n % 10);
                    n /= 10;
                    if (li.Contains(n)) { b = true; }
                }
                n = s;
                s = 0;
            }
            if (b == true) Console.WriteLine("sad");
            else Console.WriteLine("happy");
            Console.ReadLine();      
        }
    }
}

Last edited by Joudi416 (August 19 2010)

Offline

#42 August 19 2010

arithma

Re: Quizz of the Day

Yeah you can certainly do that in C# as well, I'll post up a translation here before I sleep.

Ok, here we go, C# version.

        static uint next(uint n)
        {
            uint sum = 0;
            while (n > 0)
            {
                uint digit = n % 10;
                sum += digit * digit;
                n /= 10;
            }

            return sum;
        }

        static void Main(string[] args)
        {
            Console.Write("Enter number: ");
            uint n = uint.Parse(Console.ReadLine());
            uint slow = next(n);
            uint fast = next(next(n));

            while (slow != fast)
            {
                slow = next(slow);
                fast = next(next(fast));
                Console.WriteLine(slow + "-" + fast);
            }

            if (slow == 1)
                Console.WriteLine(":)");
            else
                Console.WriteLine(":(");
        }

Last edited by arithma (August 20 2010)

Offline

#43 August 20 2010

GN90

Re: Quizz of the Day

I have a question concerning Arithma's code, before i read your code, i thought of a solution similar to Joudi's.
I read your code and I understood it, but my question is why did you chose 2 operations versus 1 ? was it a random thing or not ?
because while trying changing the number of operations (3 vs 1 loops eternally, 4 vs 1 not , 5 vs 1 was looping , ...) when I've reached 8 operations vs 1, the number "fast" behaved like fast = fucntion(fast)  , it didn't change through all the loop.

......
while(slow != fast){
        slow = next(slow);
        fast = next(next(next(next(next(next(next(next(fast))))))));
.......

this how i modified it and like i said fast became as if it was a constant, tried it for about more than 100 numbers (ma 2afda bele ) and i always got results like that :

Enter a number: 6
36-89
45-89
41-89
17-89
50-89
25-89
29-89
85-89
89-89
slow = 89
:(

and many other similar results.
i don't think this is some coincidence, is it some arithmetic property ?
having that i removed the operation on "fast" numbers in the loop and replaced it in the first operation on "fast" (the one used to initialize fast) and i got this code at the end :

void main(){
    uint slow, fast;
    cout << "Enter number: ";
    cin >> slow;
    fast = next(next(next(next(next(next(next(next(next(slow)))))))));
    cout<<fast ;
    if(fast == 1)
        cout << "\n:)";
    else
        cout << "'n:("; 
}

and next() is the same as arithma defined it before.

it seems to be a right code but i don't know why

Last edited by GN90 (August 20 2010)

Offline

#44 August 20 2010

arithma

Re: Quizz of the Day

@GN90: You have my two thumbs up. Perfect questions.

In the case of next(next(n)), the distance will decrease always by 1 on each loop (distance to collide). However, as I'll show you in the code sample, next(next(next(n))) may always skip next(n).

This almost drove me crazy, but I got a test case that shows the danger of using next(next(next(n)))

#include <iostream>
using namespace std;

typedef unsigned int uint;

uint next(uint n){
    n++;

    return n % 4;
}

void main(){
    uint slow, fast;
    slow = 0;
    fast = next(slow);

    while(slow != fast){
        slow = next(slow);
        fast = next(next(next(fast)));

        cout << slow << "-" << fast << endl;
    }

    cout << "slow = " << slow << endl;
    if(slow == 1)
        cout << ":)\n";
    else
        cout << ":(\n";
}

The rationale behind this: next(n) versus next(next(n)) inside a cycle is the same as n versus next(n). However, the last form is used since we don't know we're already in the cycle yet. We don't know the size of the cycle either. So if we just fix slow and only advance fast, slow may stay out of the loop, and no collision may ever happen.

The following is a next function such that you may not necessarily start within the loop. (You may start at 1000, it will eventually loop inside the 0 to 3 sequence).

uint next(uint n){
	if(n > 4)
		return n / 2;

    n++;
    return n % 4;
}

Oh, btw, you owe me 2 hours

Last edited by arithma (August 20 2010)

Offline

#45 August 20 2010

arithma

Re: Quizz of the Day

Pasted up the C# code translation.

Offline

Board footer