Extreme Challenge! PHP sorting algorithm.

[geoffreak]

Here is the challenge.
Figure out an algorithm that will sort a list of directories like so:

directory/file.htm
file.htm
directory/another/file.htm
another.htm
directory/another.htm
a_really_long_filename_for_some_odd_reason.htm

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!

[eviL3 Igor]

Hi,

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

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>';

?>

[geoffreak]

You figured it out?!
Very nice!

I'll test and see if it works!

[geoffreak]

Very close but there is still a few glitches
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
)

[drathbun]

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

[eviL3 Igor]

Yes drathbun, that's how it's supposed to look. Lord le Brand suggest using the usort() function

[Mighty Gorgon Luca]

Yes, maybe this comment may help.

http://php.net/manual/en/function.usort.php#39385