programming task!

Discussion of programming on Linux, including shell scripting, perl, python, c/c++, mono, java. Whatever tickles your fancy.

programming task!

Postby lambda » Fri Mar 02, 2007 1:38 am

here's a task for you. i had to write a program for someone to do this, and thought i'd see how you'd solve it.

you have a file in this format:

Code: Select all

root: admin1, admin2
postmaster: root
news: admin
admin: mani
admin1: zahra@server5, mani
admin2: admin1, manager@server5
mani: mani@server5

you want to flatten the aliases, and output a file like this:

Code: Select all

root: zahra@server5, mani@server5, manager@server5
postmaster: zahra@server5, mani@server5, manager@server5
news: mani@server5
admin: mani@server5
admin1: zahra@server5, mani@server5
admin2: zahra@server5, mani@server5, manager@server5
mani: mani@server5

you may write your code in any language.

you must also catch cycles. if you see something like this:

Code: Select all

root: postmaster
postmaster: admin
admin: root

you can assume that the file is "bad" and stop.
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Re:

Postby LinuxFreaK » Sat Mar 03, 2007 10:46 am

Dear PLUCian's,
Salam,

For those this problem is for can use below command as reference.

# man sed

Best Regards.
Farrukh Ahmed
LinuxFreaK
Site Admin
 
Posts: 5132
Joined: Fri May 02, 2003 10:24 am
ICQ: 82075802
Website: http://www.linuxpakistan.net/wiki/index.php?pagename=LinuxFreak
WLM: f4fahmed@hotmail.com
Yahoo Messenger: f4fahmed@yahoo.com
AOL: linuxpakistan@aol.com
Location: Karachi

Postby lambda » Sat Mar 03, 2007 2:36 pm

that's not going to help you one bit.
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Re:

Postby LinuxFreaK » Sat Mar 03, 2007 3:50 pm

Dear lambda,
Salam,

lambda wrote:that's not going to help you one bit.


But this will help for sure :)

# man awk

Best Regards.
Farrukh Ahmed
LinuxFreaK
Site Admin
 
Posts: 5132
Joined: Fri May 02, 2003 10:24 am
ICQ: 82075802
Website: http://www.linuxpakistan.net/wiki/index.php?pagename=LinuxFreak
WLM: f4fahmed@hotmail.com
Yahoo Messenger: f4fahmed@yahoo.com
AOL: linuxpakistan@aol.com
Location: Karachi

Re:

Postby LinuxFreaK » Sun Mar 04, 2007 12:34 am

Dear lambda,
Salam,

# cat file.txt | sed 's/@server5//' | awk -F '[ ,:]+' -v serv=server5 '{ a = $1 ; i = 1 ; r = ""; while ( $++i ) r = r $i "@" serv ", " ; sub(/, $/, "", r) ; print a ": " r }'

Where file.txt contain

Code: Select all

root: admin1, admin2
postmaster: root
news: admin
admin: mani
admin1: zahra@server5, mani
admin2: admin1, manager@server5
mani: mani@server5


Best Regards.
Farrukh Ahmed
LinuxFreaK
Site Admin
 
Posts: 5132
Joined: Fri May 02, 2003 10:24 am
ICQ: 82075802
Website: http://www.linuxpakistan.net/wiki/index.php?pagename=LinuxFreak
WLM: f4fahmed@hotmail.com
Yahoo Messenger: f4fahmed@yahoo.com
AOL: linuxpakistan@aol.com
Location: Karachi

Postby lambda » Sun Mar 04, 2007 2:31 am

this will need more programming than that! your code rewrites

Code: Select all

root: admin1, admin2
to

Code: Select all

root: admin1@server5, admin2@server5
that is incorrect.

try again!
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Re:

Postby LinuxFreaK » Sun Mar 04, 2007 5:53 pm

Dear lambda,
Salam,

That was just an idea.

Best Regards.
Farrukh Ahmed
LinuxFreaK
Site Admin
 
Posts: 5132
Joined: Fri May 02, 2003 10:24 am
ICQ: 82075802
Website: http://www.linuxpakistan.net/wiki/index.php?pagename=LinuxFreak
WLM: f4fahmed@hotmail.com
Yahoo Messenger: f4fahmed@yahoo.com
AOL: linuxpakistan@aol.com
Location: Karachi

nice

Postby s7r1k3r » Mon Mar 05, 2007 1:40 am

hmm, have to admit, Farrukh you've got some shell tools usage skills.
a10n3 s7r1k3r
s7r1k3r
Battalion Quarter Master Havaldaar
 
Posts: 221
Joined: Wed Aug 07, 2002 3:02 pm
Location: Rawalpindi

Re: nice

Postby LinuxFreaK » Mon Mar 05, 2007 9:09 am

Dear s7r1k3r,
Salam,

s7r1k3r wrote:hmm, have to admit, Farrukh you've got some shell tools usage skills.


Thanks

Best Regards.
Farrukh Ahmed
LinuxFreaK
Site Admin
 
Posts: 5132
Joined: Fri May 02, 2003 10:24 am
ICQ: 82075802
Website: http://www.linuxpakistan.net/wiki/index.php?pagename=LinuxFreak
WLM: f4fahmed@hotmail.com
Yahoo Messenger: f4fahmed@yahoo.com
AOL: linuxpakistan@aol.com
Location: Karachi

Re:

Postby LinuxFreaK » Mon Mar 05, 2007 9:11 am

Dear lambda,
Salam,

This is the solution of your programming task.

Code: Select all

#!/usr/bin/env perl

use strict;
use warnings;
use diagnostics;

#my $host = '@server5';

# type
#    set = hash of int;
#    relation = hash of set

# function join_relation: relation x relation ---> relation
sub join_relation
{
   my ($r, $s) = @_;
   my %t;
   while (my ($a, $b) = each %$r) {
      foreach my $c (keys %$b) {
         foreach my $d (keys %{$$s{$c}}) {
            ${$t{$a}}{$d} = 1;
         }
      }
   }
   return \%t;
}

# predicate subset_relation: relation x relation ---> bool
sub subset_relation
{
   my ($r, $s) = @_;
   while (my ($a, $b) = each %$r) {
      unless (subset_set($b, $$s{$a})) {
         return 0;
      }
   }
   return 1;
}

# predicate subset_set: set x set ---> bool
sub subset_set
{
   my ($m, $n) = @_;
   foreach my $a (keys %$m) {
      unless (defined $$n{$a}) {
         return 0;
      }
   }
   return 1;
}

# predicate equal_relation: relation x relation ---> bool
sub equal_relation
{
   my ($r, $s) = @_;
   return subset_relation($r, $s) && subset_relation($s, $r);
}

# union_relation: relation^* ---> relation
sub union_relation
{
   my $t;

   while (my $r = shift) {
      while (my ($a, $b) = each %$r) {
         foreach my $c (keys %$b) {
            ${$$t{$a}}{$c} = 1;
         }
      }
   }

   return $t;
}

# function transitive_closure: relation ---> relation
sub transitive_closure
{
   my ($r) = @_;
   my $s;
   my $run;

   do {
      $s = union_relation($r, join_relation($r, $r));
      $run = !equal_relation($s, $r);
      $r = $s;
   } while ($run);

   return $r;
}

# prune: relation ---> relation
sub prune
{
   my ($r) = @_;
   my $s;

   while (my ($a, $b) = each %$r) {
      foreach my $c (keys %$b) {
         unless (defined $$r{$c}) {
            ${$$s{$a}}{$c} = 1;
         }
      }
   }
   return $s;
}

# uniq: list ---> list
sub uniq
{
   my @list = @_;
   my %hash;

   foreach my $key (@list) {
      $hash{$key} = 1;
   }

   @list = keys %hash;
   return @list;
}

# extend: list ---> list
sub extend
{
   my @list = @_;
   my @newlist;
   foreach my $addr (@list) {
      if ($addr !~ /@/) {
#         push @newlist, "$addr$host";
         push @newlist, "$addr";
      } else {
         push @newlist, $addr;
      }
   }
   return uniq(@newlist);
}

my @lhs;
my $relation;

while (my $line = <>) {
   chomp $line;
   my @target = split /\s*[:,]\s*/, $line;
   my $key = $target[0];
   unless (defined $$relation{$key}) {
      push @lhs, $key;
   }
   shift @target;
   foreach my $target (@target) {
      ${$$relation{$key}}{$target} = 1;
   }
}

my $trans_closure = transitive_closure($relation);
$relation = prune($trans_closure);
foreach my $key (@lhs) {
   printf "%s: %s\n", $key, join(", ", sort uniq(extend(keys %{$$relation{$key}})));
}


Best Regards.
Farrukh Ahmed
LinuxFreaK
Site Admin
 
Posts: 5132
Joined: Fri May 02, 2003 10:24 am
ICQ: 82075802
Website: http://www.linuxpakistan.net/wiki/index.php?pagename=LinuxFreak
WLM: f4fahmed@hotmail.com
Yahoo Messenger: f4fahmed@yahoo.com
AOL: linuxpakistan@aol.com
Location: Karachi

Postby lambda » Fri Mar 16, 2007 11:59 pm

i'm saddened by the lack of response here. will no one else post a solution?

i'll make it easy -- just post the code to do flatten the aliases. ignore the cycle detection requirement.
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Postby masud » Sat Mar 24, 2007 11:49 pm

Sorry I'm late. Seen the post two days ago.

http://securitycoders.com/sp/alias.c
--SP--
masud
Havaldaar
 
Posts: 108
Joined: Thu Aug 05, 2004 12:15 am
Website: http://fedoraproject.org/wiki/MasoodMehmood
WLM: silentplayer@internet-criminals.com
Yahoo Messenger: xlx_silentplayer_xlx
Location: Fremont, CA

Postby lambda » Sun Mar 25, 2007 1:28 am

i would never have expected to see that done in c. by the way, your app doesn't like it if i give it a nonexistent file.

here's my code: qalias.
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Postby masud » Sun Mar 25, 2007 2:03 am

lambda wrote:i would never have expected to see that done in c.


then start expecting now.
--SP--
masud
Havaldaar
 
Posts: 108
Joined: Thu Aug 05, 2004 12:15 am
Website: http://fedoraproject.org/wiki/MasoodMehmood
WLM: silentplayer@internet-criminals.com
Yahoo Messenger: xlx_silentplayer_xlx
Location: Fremont, CA

Postby lambda » Sun Mar 25, 2007 2:45 am

as much as i loathe c++, i have to acknowledge that stl really makes things this sort of stuff easier for programmers. for example, you could use a map, and lists, and replace all your linked list foo.
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore


Return to “%s” Programming

Who is online

Users browsing this forum: No registered users and 1 guest

cron