Last active
October 21, 2015 23:01
-
-
Save h2rashee/5b1928284fab5f14f4ec to your computer and use it in GitHub Desktop.
Given a sentence and a screen specification, find out how many duplications are possible without word breaks
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Given a text with N words (a_1 ... a_N), and a very large textual screen of | |
width C chars and height L lines (C & L may be much larger than N). | |
How many times would the text fully fit on the screen if words cannot be broken? | |
Text = "this is an example" | |
C = 15 | |
L = 5 | |
textOnScreen(text, c, l) = 3 | |
this is an | |
example this is | |
an example this | |
is an example | |
this is an | |
*/ | |
import java.util.*; | |
class TextDuplicator | |
{ | |
public static void main(String[] args) { | |
Scanner sc = new Scanner(System.in); | |
int charLim = sc.nextInt(); | |
int lines = sc.nextInt(); | |
StringBuilder text = new StringBuilder(); | |
while(sc.hasNext()) { | |
text.append(sc.next()); | |
text.append(" "); | |
} | |
text.deleteCharAt(text.length() - 1); | |
System.out.println(textOnScreen(text.toString(), charLim, lines)); | |
} | |
public static int textOnScreen(String text, int charLimit, int lines) { | |
text = text.trim(); | |
ArrayList<String> list = new ArrayList<String>(); | |
int start = 0; | |
for(int i = 0; i < text.length(); i++) { | |
// Add the word when we see a space | |
if(text.charAt(i) == ' ') { | |
list.add(text.substring(start, i)); | |
// Set start as the character after space | |
// ASSUMPTION: No consecutive whitespace | |
start = i+1; | |
} | |
} | |
// Add the final word to the list | |
list.add(text.substring(start, text.length())); | |
String[] words = new String[list.size()]; | |
words = list.toArray(words); | |
int count = 0; | |
int curWord = 0; | |
// We assume text wrapping where spaces between lines are discarded | |
for(int i = 0; i < lines; i++) { | |
int curLineLen = 0; | |
while(words[curWord].length() + curLineLen <= charLimit) { | |
// Add the word since we can | |
curLineLen += words[curWord].length(); | |
curWord++; | |
// If we have reached the end of the text | |
if(curWord == words.length) { | |
// Start again and mark that we added it more than once | |
curWord = 0; | |
count++; | |
} | |
// Account for the space after it | |
curLineLen++; | |
} | |
} | |
return count; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment