I had a similar programming problem a few years ago, where I wanted to generate a table where some cells would span several rows or columns, and it was hard to predict in advance how many rows/columns a cell would span.

The solution I adopted was first to generate the table in memory as a simple 2 dimensional array of hashes, Then once the data had been turned into a table, I had another function that compared and merged neighbouring identical cells. Finally the table was rendered in it's final form. I was rendering to HTML. From your problem description, it looks like you need to render to plain text, so Text::Table looks suitable.