[Donanza]

jjl, on 23 April 2012 - 09:10 PM, said:

Quote

Here is my solution:

Your using a string on line #10

I meant help with the palindrome didn't want to take part!
Anyway i found the palindrome now

[MrCoder777]

I can do this by using linked lists. Is that allowed?

[ishkabible]

how do you plan to on using a linked list without pointers?

[Skydiver]

Linked list without pointers... Old school style. Or at least my father tells me that they used to do linked lists like this with arrays. But unfortunately it uses arrays which will disqualify it for this challenge:

Spoiler

struct List
{
    struct Node
    {
        char data;
        int next;    // Contains the index of the next Node. 0 means end of list.
    } arr[MAX_SIZE];

    int freeList;

    List()
    {
        // Node 0 is also used to store the head index.
        arr[0].next = 0;

        // Set up the free list
        for(int i = 1; i < MAX_SIZE - 1; i++)
            arr[i].next = i + 1;
        arr[MAX_SIZE - 1].next = 0;
        freeList = 1;
        
    }

    bool Append(char ch)
    {
        if (freeList == 0)
            return false; // no more room

        int current = 0;
        while (arr[current].next != 0)
            current = arr[current].next;
        arr[current].next = freeList;
        current = freeList;
        freeList = arr[freeList].next;
        arr[current].data = ch;
        arr[current].next = 0;        
    }
};

This post has been edited by jimblumberg: 25 August 2012 - 01:54 AM
Reason for edit:: Added spoiler tags

[ishkabible]

so basically it uses its own allocator with a fixed amount of memory. wouldn't pointers still be slightly more efficient because you wouldn't have to waste the cycles adding the index and the base pointer? just a conjecture, maybe it wouldn't work.

[Skydiver]

I think it really depends on the machine and how the compiler generates the code, but in general, I think the pointer will win out by having one less operation.

Anyway, thanks to jimblumberg for moving the code into spoiler tags. When I originally posted the code, I deliberately did not put the code in spoiler tags because I was thinking that by implementing Append(), rather than an InsertAtFront(), I was avoiding any hint of trying to solve the challenge listed here. An insert at front would then let you get the reversed string by traversing the list from head to tail and get the string in reverse order. With append, I now realize that you can recursively traverse the list and display the contents in reverse order. But still, this is a no-go since it uses an array.

This post has been edited by Skydiver: 25 August 2012 - 03:28 PM

[jjl]

I guess I'll try a linked list solution. The rules say you can't use "pointers", I'm not sure if that includes references or not, but here's my linked list solution using temporary references and polymorphism

Spoiler

#include <iostream>
#include <exception>

using namespace std;

template<typename T> struct basic_node {
   virtual T const &get_item() const = 0;
   virtual basic_node<T> const &get_next() const = 0;
};

template<typename T> struct node : public basic_node<T> {
   node(T item, basic_node<T> const &next) : item(item), next(next) {}
   T const &get_item() const { return item; }
   basic_node<T> const &get_next() const { return next; }
private:
   T item;
   basic_node<T> const &next;
};

template<typename T> struct empty_node : public basic_node<T> {
   struct empty_node_exception : public std::exception {};
   T const &get_item() const { throw empty_node_exception(); }
   basic_node<T> const &get_next () const { throw empty_node_exception(); }
};

void reverse_string(basic_node<char> const &str) {
   try {
      reverse_string(str.get_next());
   } catch(empty_node<char>::empty_node_exception &) {}
   std::cout<<str.get_item();
}
int main(int argc, char *argv[]) {
   reverse_string(node<char>('a', node<char>('b', node<char>('c', empty_node<char>()))));
   return 0;
}

This post has been edited by jjl: 27 August 2012 - 10:36 PM
Reason for edit:: Added spoiler tags

[uzumakinaruto]

Spoiler

void main()    
{
clrscr();
char*s=new char[20];
cout<<"enter string"<<endl;
gets(s);
int l=strlen(s);

for(int i=l-1;i>=0;i--)
{
cout<<s[i];
}
getch();
}

This post has been edited by ishkabible: 26 November 2012 - 11:39 AM

[ishkabible]

post code in code tags in spoiler tags please. not separate.

[graycode]

i use array for this in C.
but i don't know if this code runs. But hope this helps.
and please inform me if it won't run.

Spoiler

void main(){
   int row,col;

   char string[100]={NULL};
   scanf("%s",&string[NULL]);

  for(row=100;row>=0;row--){
    if(string[row]!=NULL){
       printf("%c",string[row]);
}
}

}

This post has been edited by GunnerInc: 27 November 2012 - 08:01 PM
Reason for edit:: Added spoiler tags

[uzumakinaruto]

ive used swapping

Spoiler

void main()
{
clrscr();
char*s=new char[20];
cout<<"enter string"<<endl;
gets(s);
int l=strlen(s);
int j=0;
char temp;
int k=l;
for(int i=0;i<=l;i++)
{
if(k>j)
{
temp=s[j];
s[j]=s[k];
s[k]=temp;
}
j++;
k--;
}
for(int a=0;a<=l;a++)
cout<<s[a];
getch();
}

please let me know if m wrong smwhere

[aresh]

Yes, it is wrong. You have to reverse it, not sort it. And everywhere you run your loop from i = 0 to i = l. That is wrong, since you can only access the array upto l-1. So, that is another problem.

EDIT : My bad, I read it wrong.

This post has been edited by aresh: 28 November 2012 - 12:56 AM

[uzumakinaruto]

but it does reverse the string.

[uzumakinaruto]

aresh, on 28 November 2012 - 12:41 AM, said:

Yes, it is wrong. You have to reverse it, not sort it.

ok so reversing code isnt basically done by swapping which i just did?

[aresh]

My bad, I read it wrong and thought you were doing bubble sort. Still, the error I mentioned is there. Also,

Quote

How would you reverse a string without using, pointers, arrays, or c-strings.

But, you have not followed these rules.