Extreme Challenge! PHP sorting algorithm.

phpBB3 and MOD challenges setup by the staff to test and challenge your phpBB3 coding skills.

Extreme Challenge! PHP sorting algorithm.

Postby geoffreak » 31 Jul 2007, 19:44

Here is the challenge.
Figure out an algorithm that will sort a list of directories like so:
before wrote:directory/file.htm
file.htm
directory/another/file.htm
another.htm
directory/another.htm
a_really_long_filename_for_some_odd_reason.htm

after wrote:directory/another/file.htm
directory/another.htm
directory/file.htm
a_really_long_filename_for_some_odd_reason.htm
another.htm
file.htm


See how the folders are listed first even though it isn't alphabetically so?
I have been personally unable to do this despite around 10-15 hours of work.
I will continue to try but I want to see if the best minds out there can accomplish what I have not.

Remember, the names are all strings! ;)
Earthlings, we have been watching you for years, and now we know your primitive language, so listen: All your base are belong to us.
Anime Bite - Your future #1 source for all things anime and manga!My Blog
User avatar
geoffreak    
Supporter
Supporter
 
Posts: 663
Joined: 17 Mar 2007, 21:52
Location: The Internets
Favorite Team: phpBB
Gender: Male
phpBB Knowledge: 9


Re: Extreme Challenge! PHP sorting algorithm.

Postby eviL3 » 01 Aug 2007, 09:15

Hi,

just spent ages on this (over an hour for sure), that was a pain :D

Code: Select all
<?php

// http://startrekguide.com/forum/f74-phpbb3-coding-challenges/t3229-extreme-challenge!-php-sorting-algorithm.html

class geoff_extreme_algo
{
   var $output = array();
   
   function geoff_extreme_algo($list)
   {
      $_list = $this->_to_assoc_array($list);
      $_list = $this->_sort($_list);
      $_list = $this->_to_list($_list);
      
      $this->output = $_list;
   }
   
   function _to_assoc_array($list)
   {
      $output = $_dirs = array();
      
      foreach ($list as $file)
      {
         if (strpos($file, '/') !== false)
         {
            $_dir = substr($file, 0, strpos($file, '/'));
            $_file = substr($file, strpos($file, '/') + 1);
            
            $_dirs[$_dir][] = $_file;
         }
         else
         {
            $output[] = $file;
         }
      }
      
      foreach ($_dirs as $dir => $files)
      {
         $output[$dir] = $this->_to_assoc_array($files);
      }
      
      return $output;
   }
   
   function _sort($list)
   {
      $_list = array();
      
      asort($list);
      
      foreach ($list as $key => $item)
      {
         if (!is_array($item))
         {
            continue;
         }
         
         $_list[$key] = $this->_sort($item);
      }
      
      foreach ($list as $key => $item)
      {
         if (is_array($item))
         {
            continue;
         }
         
         $_list[] = $item;
      }
      
      return $_list;
   }
   
   function _to_list($list, $parent = false)
   {
      $_list = array();
      
      foreach ($list as $key => $item)
      {
         if (is_array($item))
         {
            $key = ($parent ? $parent . '/' : '') . $key;
            $_list = array_merge($_list, $this->_to_list($item, $key));
         }
         else
         {
            $_list[] = ($parent ? $parent . '/' : '') . $item;
         }
      }
      
      return $_list;
   }
}

$list = array(
   'directory/file.htm',
   'file.htm',
   'directory/another/file.htm',
   'another.htm',
   'directory/another.htm',
   'a_really_long_filename_for_some_odd_reason.htm',
);

$xtrm = new geoff_extreme_algo($list);

echo '<pre>' . print_r($xtrm->output, true) . '</pre>';

?>
Image
User avatar
eviL3    
MOD Author
MOD Author
 
Posts: 1002
Joined: 05 Nov 2006, 08:14
Location: Cooking in the MODs kitchen
Gender: Male

Re: Extreme Challenge! PHP sorting algorithm.

Postby geoffreak » 01 Aug 2007, 11:21

:shock:
You figured it out?!
Very nice!

I'll test and see if it works! :blink:
Earthlings, we have been watching you for years, and now we know your primitive language, so listen: All your base are belong to us.
Anime Bite - Your future #1 source for all things anime and manga!My Blog
User avatar
geoffreak    
Supporter
Supporter
 
Posts: 663
Joined: 17 Mar 2007, 21:52
Location: The Internets
Favorite Team: phpBB
Gender: Male
phpBB Knowledge: 9

Re: Extreme Challenge! PHP sorting algorithm.

Postby geoffreak » 01 Aug 2007, 11:27

Very close but there is still a few glitches :good:
Look what happens when I add an element to list:
Code: Select all
$list = array(
   
'directory/file.htm',
   
'file.htm',
   
'directory/another/file.htm',
   
'another.htm',
   
'directory/another.htm',
   
'a_really_long_filename_for_some_odd_reason.htm',
   
'directory/z/abe.xml',
);  

Array
(
[0] => directory/z/abe.xml
[1] => directory/another/file.htm
[2] => directory/another.htm
[3] => directory/file.htm
[4] => a_really_long_filename_for_some_odd_reason.htm
[5] => another.htm
[6] => file.htm
)
Earthlings, we have been watching you for years, and now we know your primitive language, so listen: All your base are belong to us.
Anime Bite - Your future #1 source for all things anime and manga!My Blog
User avatar
geoffreak    
Supporter
Supporter
 
Posts: 663
Joined: 17 Mar 2007, 21:52
Location: The Internets
Favorite Team: phpBB
Gender: Male
phpBB Knowledge: 9

Re: Extreme Challenge! PHP sorting algorithm.

Postby drathbun » 12 Sep 2007, 12:11

What is the exact requirement here? Are you simply trying to create a list where any directory appears first, followed by file names? Or should the directories be sorted in a "hierarchical" fashion too?

For example, how would this list be sorted when it's done?
Code: Select all
folder_a/folder_b/folder_c/file_a
folder_a/folder_b/folder_c/folder_d/file_a
folder_a/folder_b/file_a
folder_a/folder_c/file_a
folder_a/file_a
file_a
file_b
file_c
meh
User avatar
drathbun
STG Development
STG Development
 
Posts: 45
Joined: 10 Sep 2007, 11:11
Gender: Male

Re: Extreme Challenge! PHP sorting algorithm.

Postby eviL3 » 18 Sep 2007, 14:26

Yes drathbun, that's how it's supposed to look. Lord le Brand suggest using the usort() function :D
Image
User avatar
eviL3    
MOD Author
MOD Author
 
Posts: 1002
Joined: 05 Nov 2006, 08:14
Location: Cooking in the MODs kitchen
Gender: Male

Re: Extreme Challenge! PHP sorting algorithm.

Postby Mighty Gorgon » 18 Sep 2007, 16:59

Yes, maybe this comment may help.

http://php.net/manual/en/function.usort.php#39385
Luca
User avatar
Mighty Gorgon    
Style Author
Style Author
 
Posts: 20
Joined: 04 Jul 2007, 16:50
Location: Italy
Favorite Team: Juventus
Gender: Male


Return to phpBB3 Challenges at phpBB Academy

Who is online

Users browsing this forum: No registered users and 2 guests