• Post Reply Bookmark Topic Watch Topic
  • New Topic

Algorithm For Partitioning Spaces Java  RSS feed

 
Greg Savidge
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

up vote 0 down vote favorite


I am working on trying to implement a full text justification program in Java. I have the basics of it down but am stuck on the partitioning of spaces to pad the lines out to the desired length.

Lets say for example I have a line with 4 words that are:

The cat jumped over.

I want the line to be 25 characters in length and currently I have 20 characters, including spaces.

In other words I am going to need to add 5 additional spaces to the end on each word excluding the last.

I then divide 5 extra spaces to be added by the 3 positions to add it to and get the number 1.6666 repeating or 1 and 2/3 spaces per word. In reality though I can only use a whole number of spaces and I would like to distribute them as evenly as possible such as:

The _ _ _ cat _ _ _ jumped _ _ over. (where underscores are spaces).

My question is how could I implement a block of code that could allow me to partition the spaces between the words.

My only thought would be to create three counters that incrementally increase until there sums are equal to the number of spaces needed, but I am new to programming and am thinking there must be a simpler approach.

Thanks for reading.

Greg
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

The ironic thing is, I think you have worked out 90% of the problem, having given such a clear description of the problem. If only everybody else posted questions so easy to understand.

What about division? Using the rules of integer division and integer remainder, which you can read about in the Java Language Specification (beware: it might not be easy to read), you can probably work out that you need (1+1) for the first two words and (1) after the third.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Greg Savidge wrote:My only thought would be to create three counters that incrementally increase until there sums are equal to the number of spaces needed, but I am new to programming and am thinking there must be a simpler approach.

Well, when I tried this (quite a while ago) the best results seemed to come when I used a random distribution.

Basically, you know how many "gaps" there are going to be, and you've already worked out that each gap needs to be at least space/gaps long (where both are ints).

You also know that remainingSpace == space - (gaps * minimumGapSize). If that value is 0, your job is done; otherwise you want to distribute that remaining space randomly, but evenly, among your gaps (ie, add 1 to some and 0 to others).

I'll leave you work out how to do that

Winston
 
Greg Savidge
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks very much for the responses. I found the randomization of the space padding to be particularly helpful in my code. Ended up making one array that just held the words and another array that held the spaces. Then I just added to the array with spaces looping over the representation of the gaps as indexes in the array, randomly inserting spaces, until the necessary spaces where obtained. To get the sentence back out I just alternated between the words array and the spaces array until they were empty.

Thanks again.

Greg
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You didn’t add spaces / (words - 1) after every word and the remaining spaces % (words - 1) randomly one each after words?
 
Greg Savidge
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:You didn’t add spaces / (words - 1) after every word and the remaining spaces % (words - 1) randomly one each after words?


ended up looking like this in my code:

int gaps = (longLine.length-1);

int spaceRemainingCounter = charactersNeeded;

while (spaceRemainingCounter !=0)
{
      for (int i = 0; i < gaps; i++)
      {
           if (spaceRemainingCounter==0) break;
           int random = (int) (Math.random()*2);
           if (random !=0);
           else
           {
                String currentIndex = spaceArray.get(i);
                currentIndex +=" ";
                spaceArray.set(i, currentIndex);
                spaceRemainingCounter--;
                }
           }
}

String assemble="";
for (in j=0; j<longLine.length-1; j++)
{
     assemble+= longLine[J] + spaceArray.get(j);
}

assemble += longLine[longLine.length-1];

basically it kept adding spaces to an array that had the same indexing that another array had that was used to split the words into, randomly but sequentially over and over until there where no more spaces needed to be added and then I assembled the spaces and the words back together again. I should mention I initially filled my spaceArray with one space in each index to begin with.

My program has a ton of limitations, such as no indentations at the beginning of the sentence but it works for very simple cases for full line justification.

Again thanks for everyones help!
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Afraid I am not impressed. Sorry.

You have two tests for whether you have no spaces remaining. I think you can (probably should) get rid of one of those tests.
Are you sure that the 50/50 test will distribute the spaces evenly along the line?
Why use * 2 with Math.random? It would be simpler to use if (Math.random() < 0.5)...
Don't use a semicolon after if, least of all when it is followed by else; that is confusing code. In that case where you have 50/50 probabilities you can simply miss out the else, but otherwise you should alter the test in the if so as not to have an else block.
You are probably not after performance at present, but using += on Strings can cause slow performance. As a general rule of thumb, you should put the Strings into a StringBuilder and append " ".

I shall have to point you to the code button, which will obviate all those &nbsp;s you had to write.

 
Greg Savidge
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


What is the saying? You can impress most of the people most of the time, some of the people some of the time, but not all of the people all of the time. lol

Seriously though thanks for the feedback I will take the stylistic and coding advice for my next program. And thanks for the code button, I would get tired of writing html entity tags over and over again!
 
Greg Savidge
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And following up on the posting of code as in the presentation within this forum, what do you think is the best approach?
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Greg Savidge wrote: . . . thanks . . . thanks . . .
You're welcome

Not quite sure I understand the question about presentation. Sorry.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Greg Savidge wrote:And following up on the posting of code as in the presentation within this forum, what do you think is the best approach?

1. Read the UseCodeTags (←click) page thoroughly.
2. Read the DontWriteLongLines page.
3. Read the Java Coding Conventions document.

ie, Lots of reading.

Winston
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote: . . .
3. Read the Java Coding Conventions document.
. . .
So that is what the question meant!

I disagree with that document about indentation. I prefer having {} lined up vertically, but (in my opinion) the really serious mistake in that document is they say it doesn't matter whether you use tabs or spaces.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:I disagree with that document about indentation. I prefer having {} lined up vertically, but (in my opinion) the really serious mistake in that document is they say it doesn't matter whether you use tabs or spaces.

Totally agree about the latter, but with a few exceptions disagree on the first (it makes code look 'bloated' to me). Which just goes to show...

Winston
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is why I said prefer for the first part and serious mistake about the second. People who get used to {
    this sort of indentation
}
find it easy to read. But you can get all sorts of poor formatting on some platforms, here included, if you mix spaces and tabs.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!