Bardzo ciekawe zadanie ostatnio dostałem do zrobienia w PHP. Jestem ciekawy jak podeszlibyście do zbudowania takiego algorytmu.

A więc tak:

Zadanie

Dane należy rozbić na 4 kolumny tabeli:
- zachowując porządek alfabetyczny grup,
- nie rozrywając grup na 2 lub więcej kolumn
- jedna grupa musi w całości mieścić się w jednej kolumnie
- wstawiając między grupami jedną linię pustą (po ostatniej kategorii w kolumnie nie trzeba wstawiać pustej linii)

Problem
Kategorie w grupach trzeba rozbić na 4 kolumny, tak aby te kolumny były jak najbardziej zrównoważone pod względem ilości znajdujących się w nich kategorii (i odstępów między nimi), czyli dążymy do tego aby kolumny były jak najkrótsze. Rozwiązanie w postaci skryptu php zawierającego formularz z polem textarea, do którego będzie można wkleić dane wejściowe i po wysłaniu formularza otrzyma się wynik zadania.



Przykładowe dane wejściowe:


Ma wyświetlić tabelę jak tutaj http://dado.smarthost.pl/test/index.php (przyklad)


Moje (nie idealne) rozwiązanie:

[PHP] pobierz, plaintext 
<?php
 
/**
* Klasa sortująca kategorie produktów do tabeli n - kolumnowej
*/
class Category
{
	/**
	* @var array
	*
	* Parametry do generowania tabeli
	*/
	protected $param = array();
 
	/**
	* Konstruktor
	*/
	public function __construct()
	{
		$this->param = array(
			'table_columns' => 4
		);
	}
 
	/**
	* Getter
	*
	* @return val/array/bool
	*/
	public function get_param($val)
	{
		// dostęp do parametrów klasy
		if( ! isset($val)) return false;
		if( isset($this->param[$val])) return $this->param[$val];
		return false;
	}
 
	/**
	* Spłaszczenie tablicy wejściowej tablicy asocjacyjnej to tablicy jednowymiarowej
	*
	* @param array $array
	* @param integer $cool
	*
	* @return array
	*/
	protected function merge_group($cool)
	{
		if(is_array($this->param['render_data']) && count($this->param['render_data']) > 0 && is_numeric($cool))
		{
			$group_category_array = array();
			foreach($this->param['render_data'] as $row)
			{
				if($row['cool'] == $cool)
				{
					$group_category_array = array_merge($group_category_array, array_merge($row['category'], array(' ')));
				}
			}
			$this->param['column_max'][] = count($group_category_array);
 
			return $group_category_array;
		}
		else
		{
			return FALSE;
		}
	}
 
	/**
	* Praca na danych, wstępna obróbka
	*
	* @param	string $raw_data
	*/
	private function _data_prepare()
	{
		if( ! isset($this->param['raw_data']) || empty($this->param['raw_data']))
		{
			return false;
		}
 
		$this->param['data_group_arr'] = explode("\n\r", trim($this->param['raw_data'])); // kategorie pogrupowane według nazwy => arr
		$this->param['data_arr'] = explode("\r\n", trim($this->param['raw_data'])); // wszystkie kategorie w tablicy 2D
		$this->param['count_rows'] = round(count($this->param['data_arr']) / $this->param['table_columns']); // wskaźnik końca danych w jednej  kolumnie
	}
 
	/**
	* Podział grup produktów na kolumny
	*
	* @reutrn array
	*/
	protected function _render_data()
	{
		$this->_data_prepare(TRUE); // przytowanie danych
 
		if( ! isset($this->param['data_group_arr']) || ! is_array($this->param['data_group_arr'])) return false;
 
		$i = (int) 0; // elementy w kolumnie
		$cool = (int) 1; // iterator kolumn
 
		for($tc = 0; $tc <= count( $this->param['data_group_arr'] ); $tc++)
		{
 
			if( isset( $this->param['data_group_arr'][$tc]))
			{
		  		$row = $this->param['data_group_arr'][$tc]; // element do zmiennej lokalnej
				$category = explode("\r\n", trim($row)); // kategorie w grupie => array
				$count_category = count($category); // obliczenie elementów w kolumnie
 
				// bolicznie elementów w kolejnej grupie
				if(isset($this->param['data_group_arr'][$tc+1]))
				{
					$count_category_next = count(explode("\r\n", trim($this->param['data_group_arr'][$tc+1])));
				}
				else
				{
					$count_category_next = 0;
				}
 
				// sumowanie całej kolumny kategorii
				$i += $count_category;
 
				// generowanie danych do tabeli
				$this->param['render_data'][] = array(
					'category' =>  $category,
					'count' => $count_category,
					'cool' => $cool
				);
 
				// sprawdzanie czy suma kategorii nie przekracza 1/4 sumy wszytkich pól + sume kategorii grupy następnej
				if(($i + $count_category_next) >= $this->param['count_rows'])
				{
					$i = (int) 0; // zerowanie całości po przekroczeiu wskaźnika
					$cool++; // nowa kolumna
				}
			}
		}
		return TRUE;
	}
}
 
/**
* Zwracanie sforamtowanych danych dla widoku
*/
class Category_Data extends Category
{
 
	/**
	* Pobranie danych po obróbce, zwraca tablice w 4 głównych elementach
	*
	* @return array
	*/
	public function get_final_data($raw_data)
	{
 
		$column = array();
		$this->param['raw_data'] = trim(strip_tags(htmlspecialchars($raw_data))) ; // filtrowanie superglobalnej
 
		if($this->_render_data() === TRUE)
		{
			for($i=1; $i<=($this->param['table_columns'] ); $i++)
			{
				$column['col_' . $i] = $this->merge_group($i);
			}
			return $column;
		}
		else
		{
			return false;
		}
	}
}
 
 
 
/**
* Mini kontroler na potrzeby zadania
*/
class Controller
{
 
	/**
	* @var string
	*
	* akcja kontrolera
	*/
	private $action;
 
	/**
	* @var array
	*
	* Przechowywanie widoku
	*/
	private $template = array();
 
	/**
	* Inicjuje zmienne w tablicy widoku, filtruje zmienną globalną
	* twoży nazwę publicznej metody kontrolera i jeśli istnieje wywołuje ją
	*/
 	public function __construct()
	{
		// elementy widoku
		$this->template['head'] = '<!DOCTYPE HTML>
			<html>
				<meta charset="utf-8">
    			<meta http-equiv="X-UA-Compatible" content="IE=edge">
    			<meta name="viewport" content="width=device-width, initial-scale=1">
				<title>Kategorie Produktów</title>
				<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.2/css/bootstrap.min.css">
				<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.2/css/bootstrap-theme.min.css">
				</head>
				<body style="padding:2em;"><div class="container"><div class="row">
			<h1>Zadanie: Kategorie Produktów</h1>
		</div>';
		$this->template['footer'] = '</div></body></html>';
		$this->template['back'] = '<br /><a href="index.php" class="btn btn-primary" role="button">Powrót</a>';
		// elementy widoku - koniec
 
		if( ! isset($_GET['action']) || empty($_GET['action'])) $_GET['action'] = 'index'; //  predefiniowanie
		$this->action = trim(strip_tags( htmlspecialchars($_GET['action']))) . '_action'; // Filtrowanie
 
		if( is_callable(array($this, $this->action)))
		{
	 		return call_user_func(array($this, $this->action)); // Call Action
		}
		else
		{
			return $this->notfound_action(); // HTTP 404
		}
	}
 
 
	/**
	* Wynik zadania
	*
	* @return string
	*/
	public function render_action()
	{
		// Pobieranie wyniku zadania
		$category = new Category_Data;
		$data = $category->get_final_data($_POST['raw_data']); // pobieranie danych
 
		// Widok
		echo $this->template['head'];
		if($data !== FALSE)
		{
			$table_columns = $category->get_param('table_columns'); // pobieranie liczby kolumn
			$count_rows =  max($category->get_param('column_max')) - 2; // pobieranie maksymalnej liczby wierszy w kolumnie;
 
	  		$this->template['table'] = '<table class="table table-bordered">' ;
			for( $i=0; $i<=$count_rows; $i++ )
			{
				$this->template['table'] .= '<tr>';
				for($col=1; $col<=$table_columns; $col++)
				{
					$this->template['table'] .= (isset( $data['col_' . $col][$i]) ? '<td>'.$data['col_' . $col][$i].'</td>':'<td></td>');
				}
				$this->template['table'] .= '</tr>';
			}
			$this->template['table'] .= '</table>';
			echo $this->template['table'];
		}
		else
		{
			echo '<div class="alert alert-danger" role="alert"><b>Błąd!</b> Brak danych.</div>';
		}
		echo $this->template['back'] . $this->template['footer'];
	}
 
	/**
	* Akcja domyślna
	*
	* @return string
	*/
	public function index_action()
	{
		// Widok
		echo $this->template['head'] .
		'<div class="row">
			<div class="col-md-12">
				<form method="post" action="index.php?action=render" class="form-horizontal">
					<div class="form-group">
					    <label>Dane wejściowe</label>
					    <textarea name="raw_data" class="form-control" rows="23"></textarea><br />
						 <button type="submit" class="btn btn-primary">Wyślij</button>
					</div>
				</form>
			</div>
		</div>' . $this->template['footer'];
	}
 
 
	/**
	* HTTP 404
	*
	* @return string
	*/
	public function notfound_action()
	{
		header('HTTP/1.0 404 Not Found');
		echo $this->template['head'] .
			'<div class="alert alert-danger" role="alert"><h1>404 Not Found</h1></div>' .
			$this->template['back'] .
		$this->template['footer'];
	}
 
}
 
$Controller = new Controller; // Uruchomienie zadania
?>
 
[PHP] pobierz, plaintext