LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 01-14-2012, 05:36 AM   #1
Calin956
LQ Newbie
 
Registered: Jan 2012
Posts: 3

Rep: Reputation: Disabled
help with an algorithm


you have a number and 5 operations
1) add one to a digit ... 3 points
2) decrese one from a digit ... 2 points
3) interchange 2 digits ... 7 points
4)add a digit... 10 points
5) delet a digit... 12 points
and you have to make the given number a palindrom with a total of minimal points
for example if the number is 234 , decrese 4 by 2 and you get 232 and 4 points
 
Old 01-14-2012, 06:52 AM   #2
ButterflyMelissa
Senior Member
 
Registered: Nov 2007
Location: Somewhere on my hard drive...
Distribution: Manjaro
Posts: 2,766
Blog Entries: 23

Rep: Reputation: 411Reputation: 411Reputation: 411Reputation: 411Reputation: 411
...ehrm..is this a school assignment? If so, sorry, kid. We dont do someone else's homework...

If not, expand a little. What programm language would you use? What is it for? More info...of course, if it's NOT an assignment...

Thor
 
Old 01-14-2012, 06:57 AM   #3
Snark1994
Senior Member
 
Registered: Sep 2010
Distribution: Debian
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 346Reputation: 346Reputation: 346Reputation: 346
While agreeing with Thor, even if it were a homework I would feel happy to point you at a Breadth First Search, which is what you probably want to be implementing
 
Old 01-14-2012, 07:46 AM   #4
Calin956
LQ Newbie
 
Registered: Jan 2012
Posts: 3

Original Poster
Rep: Reputation: Disabled
yeah, actually it's an example of a problem i might be geting at my exams and i've been trying but can't pull it trough...
it doesn't matter what language, but mously he asks us to work in C#

Last edited by Calin956; 01-14-2012 at 07:49 AM.
 
Old 01-15-2012, 04:37 AM   #5
Snark1994
Senior Member
 
Registered: Sep 2010
Distribution: Debian
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 346Reputation: 346Reputation: 346Reputation: 346
Right - next time say so in your question, 'cos it helps people know what level of support they're working on

Do you have any code that you've written to attempt the problem? Have you tried implementing the BFS I linked you to? (there's informal pseudocode on the wikipedia article I linked you to, but I'm almost certain there's better pseudocode on the web, or I can explain it if you get stuck.)
 
Old 01-15-2012, 07:13 AM   #6
Calin956
LQ Newbie
 
Registered: Jan 2012
Posts: 3

Original Poster
Rep: Reputation: Disabled
i can't quite imagine how to use BFS here, but thank's for trying to help me, i'll magenage i think
 
Old 01-15-2012, 07:27 AM   #7
Snark1994
Senior Member
 
Registered: Sep 2010
Distribution: Debian
Posts: 1,632
Blog Entries: 3

Rep: Reputation: 346Reputation: 346Reputation: 346Reputation: 346
Ahaha, okay. I'll explain anyway, to see if that makes it clearer...

Quote:
1) Subtract 1 from a digit = 2 points
2) Add 1 to a digit = 3 points
3) Interchange 2 digits = 7 points
4) Add a digit = 10 points
5) Delete a digit = 12 points

The goal is a palindrome using the minimum number of points.
Our queue of numbers to investigate starts out with out first number (234). We remove it from the queue, and then find all the numbers we can create from it using rule 1 (134, 224, 233) and all the numbers from rule 2 (334, ...). Our queue now looks like this:

Code:
 queue = [ (134,2) , (224,2) , (233,2) , (334,3) , ... , (24,12) , (23,13) ]
where each entry is a pair of (number, point cost to get to number), and the list is sorted by point cost. We now remove the first element from the list (ie. the one with lowest cost), check if it's a palindrome, and if not then repeat the step of adding all the possible numbers we can create from this new element. Remember to sort the list afterwards. Keep on removing the first element from the list and checking and adding until you find an element which is a palindrome.

Having written that, it does become obvious that you're going to get a really big queue really quickly. In that case, it might be better to use a depth limited search if space becomes an issue.

Of course, if you have an alternative approach which you also have problems with then do post back and we'll try to help you

Hope this helps,
 
1 members found this post helpful.
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Bounce Algorithm revof11 Programming 3 05-08-2007 08:50 AM
token bucket algorithm vs Leaky bucket algorithm xeon123 Linux - Networking 2 03-26-2007 04:57 AM
DSA Algorithm example James_dean Programming 1 03-09-2006 11:12 AM
about watershed algorithm caicaicherry Programming 4 09-22-2005 03:36 AM
assistance with an algorithm mandrake_linux Programming 3 07-27-2001 04:03 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 09:45 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration