A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

**GN90**

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)*

**arithma**

@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)*

**Ayman**

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)*

**arithma**

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.

**GN90**

@ 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?

**arithma**

@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).

**GN90**

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.

**Joe**

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 ?)

**arithma**

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.

**arithma**

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

**Ayman**

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)*

**arithma**

```
#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.

**J4D**

*kteer belkon fadi ! *

**Ayman**

kteer belkon fadi !

Niyelna

**xterm****Moderator**

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)*

**Joudi416**

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)*

**arithma**

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)*

**GN90**

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)*

**arithma**

@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)*

**arithma**

Pasted up the C# code translation.