Look and say sequence is the sequence of numbers generated from the previous number by reading off the digits of which the number consists.
So the first number is 1 then there is one "1". one 1 -> 11
Now use the number "11" and there are two 1s. two 1s -> 21
21: one 2 and one 1 -> 1211
1211: one 1, one 2 and two 1s -> 111221
111221: three 1s, two 2s and one 1 -> 312211
312211: one 3, one 1, two 2s and two 1 -> 13112221
13112221: one 1, one 3, two 1s, three 2s and one 1 -> 1113213211
----------------------------------------------------------------
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 ...
The Java programme code which reads off the given number can be written like
public static String LookAndSayUsingForLoop(final String number)
{
if (null == number || number.isEmpty())
{
return "";
}
int firstCharPosition = 0;
final StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < number.length(); i++)
{
if (number.charAt(firstCharPosition) != number.charAt(i))
{
//
// the char at the current position is not equal to the first char
// in the group of the equal chars so collect the chars
// from the first char position to just before the current position.
//
final String digitsFound = number.substring(firstCharPosition, i);
stringBuilder.append(digitsFound
.length())
.append(number
.charAt(firstCharPosition));
firstCharPosition = i; // set the new first char position
}
}
/* add the leftover */
stringBuilder.append(number
.substring(firstCharPosition,
number.length())
.length())
.append(number
.charAt(firstCharPosition));
return stringBuilder.toString();
}
System.out.println(LookAndSayUsingForLoop("1"));
Result: 11
System.out.println(LookAndSayUsingForLoop("11"));
Result: 21
System.out.println(LookAndSayUsingForLoop("21"));
Result: 1211
So to get the first ten elements,
String result1 = number;
System.out.print(result1 + " ");
for (int i = 1; i < howMany; i++)
{
result1 = LookAndSayUsingForLoop(result1);
System.out.print(result1 + " ");
}
It prints out.
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
It can be simpler if recursion is used. The LookAndSayUsingForLoop method can be re-written like
private static String lookAndSayV1(final String number, final int position)
{
if (number.length() == position)
{
// reached the end which means every digit in the number is
// equal to one another so just read off the entire number.
return String.valueOf(number.length()) + number.charAt(0);
}
final char firstChar = number.charAt(0);
return firstChar == number.charAt(position) ?
// the current char equals to the first one so keep checking
lookAndSayV1(number, position + 1) :
// otherwise, read off until just before the current position
// then check from the current position
// calling this function itself again.
String.valueOf(number
.substring(0, position)
.length()) +
firstChar +
lookAndSayV1(number
.substring(position), 0);
}
The result is exactly the same as the one using 'for' loop.
System.out.println(lookAndSayV1("1", 0));
Result: 11
System.out.println(lookAndSayV1("11", 0));
Result: 21
System.out.println(lookAndSayV1("21", 0));
Result: 1211
To get the first ten elements, another recursive method can be used.
public static String lookAndSay(final int howMany, final String number)
{
return 0 >= howMany ?
"" :
number + " " + lookAndSay(howMany - 1, lookAndSayV1(number, 0));
}
final String number = "1";
final String result = lookAndSay(10, number);
System.out.println(result);
Result:
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
The method lookAndSayV1() can be re-written using only one return statement and a few conditional operations.
private static String lookAndSayV2(final String number, final int position)
{
return number.length() == position ?
String.valueOf(number
.length()) +
number.charAt(0) :
(number.charAt(0) == number.charAt(position) ?
lookAndSayV2(number, position + 1) :
String.valueOf(number
.substring(0, position)
.length()) +
number.charAt(0) +
lookAndSayV2(number
.substring(position), 0));
}
This works the same as the lookAndSayV1() method. The code would be more readable with readOff() method.
private static String readOff(final String digits)
{
return String.valueOf(digits.length()) + digits.charAt(0);
}
private static String lookAndSayV3(final String number, final int position)
{
return number.length() == position ?
readOff(number) :
(number.charAt(0) == number.charAt(position) ?
lookAndSayV3(number, position + 1) :
readOff(number
.substring(0, position)) +
lookAndSayV3(number
.substring(position), 0));
}
public static String lookAndSay3(final int howMany, final String number)
{
return 0 >= howMany ? "" : number + " " + lookAndSay3(howMany - 1, lookAndSayV3(number, 0));
}
If the numbers should be stored in a List object, it can be done like
public static void lookAndSayUsingList(final String number, final int howMany, final List<String> resultList)
{
resultList.add(number);
if (resultList.size() < howMany)
{
lookAndSayUsingList(lookAndSayV3(number, 0), howMany, resultList);
}
}
final List<String> resultList = new ArrayList<String>();
lookAndSayUsingList(number, howMany, resultList);
System.out.println(resultList);
If you prefer having returned result,
private static List<String> lookAndSayUsingList2(final String number, final int howMany, final List<String> list)
{
list.add(number);
if (list.size() < howMany)
{
return lookAndSayUsingList2(lookAndSayV3(number, 0), howMany, list);
}
return Collections.unmodifiableList(new ArrayList<String>(list));
}
The last line which returns an unmodifiable list object should use a new ArrayList object instead of directly using list. Just making list unmodifiableList is not enough as the caller of this method can still modify the given parameter list
e.g.) Just have Collections.unmodifiableList(list); will result in
final List<String> resultList = new ArrayList<String>();
resultList.add(number);
final List<String> result = lookAndSayUsingList2(resultList, howMany);
// result.add("test"); // <- this does not work! runtime exception!
resultList.add("test"); // <- yet this does!!!
// Now the result has "test" at the end although it's unmodifiable List.
// It was modified using resultList.
If you don't want to pass a List object, create another method and use it with the lookAndSayUsingList2() method.
public static List<String> lookAndSayUsingList2(final String number, final int howMany)
{
final List<String> list = new ArrayList<String>();
return lookAndSayUsingList2(number, howMany, list);
}
System.out.println(lookAndSayUsingList2(number, howMany));
Finally, using a Function object.
public interface LookAndSayFunction
{
void apply(String number, int howMany);
}
final List<String> resultListFromFunctionObject = new ArrayList<String>();
new LookAndSayFunction() {
@Override
public void apply(final String number, final int howMany)
{
resultListFromFunctionObject.add(number);
if (resultListFromFunctionObject.size() < howMany)
{
apply(lookAndSayV3(number, 0), howMany);
}
}
}.apply(number, howMany);
System.out.println(resultListFromFunctionObject);
Don't want to get a mutable List object staying outside the function?
public interface Function1<T, R>
{
R apply(T input);
}
public interface Function2<T1, T2, R>
{
R apply(T1 input1, T2 input2);
}
final Function2<String, Integer, List<String>> anotherFunction =
new Function2<String, Integer, List<String>>() {
@Override
public List<String> apply(final String number, final Integer howMany)
{
return new Function<List<String>>() {
@Override
public List<String> apply()
{
final List<String> resultList = new ArrayList<String>();
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
resultList.add(number);
if (resultList.size() < howMany.intValue())
{
return apply(lookAndSayV3(number, 0));
}
return Collections.unmodifiableList(resultList);
}
}.apply(number);
}
}.apply();
}
};
System.out.println(anotherFunction.apply(number, howMany));
Or currying can be used.
final Function1<Integer, Function1<String, List<String>>> lookAndSayWithCurrying =
new Function1<Integer, Function1<String, List<String>>>() {
@Override
public Function1<String, List<String>> apply(final Integer howMany)
{
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
final List<String> resultList = new ArrayList<String>();
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
resultList.add(number);
if (resultList.size() < howMany.intValue())
{
return apply(lookAndSayV3(number, 0));
}
return Collections.unmodifiableList(resultList);
}
}.apply(number);
}
};
}
};
System.out.println(lookAndSayWithCurrying.apply(howMany)
.apply(number));
The function can be reused.
final Function1<String, List<String>> lookAndSayToGet10Elements = lookAndSayWithCurrying.apply(10);
System.out.println(lookAndSayToGet10Elements.apply(number));
System.out.println(lookAndSayToGet10Elements.apply(number));
Result:
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
final Function1<String, List<String>> lookAndSayToGet5Elements = lookAndSayWithCurrying.apply(5);
System.out.println(lookAndSayToGet5Elements.apply(number));
Result:
[1, 11, 21, 1211, 111221]
System.out.println(lookAndSayToGet5Elements.apply("111221"));
Result:
[111221, 312211, 13112221, 1113213211, 31131211131221]
System.out.println(lookAndSayToGet5Elements.apply("21"));
Result:
[21, 1211, 111221, 312211, 13112221]
System.out.println(lookAndSayToGet5Elements.apply("1"));
Result:
[1, 11, 21, 1211, 111221]
If you want to fix the number and get different numbers of elements as the results from the look and say function,
final Function1<String, Function1<Integer, List<String>>> lookAndSayWithCurryingAndNumberFixed =
new Function1<String, Function1<Integer, List<String>>>() {
@Override
public Function1<Integer, List<String>> apply(final String number)
{
return new Function1<Integer, List<String>>() {
@Override
public List<String> apply(final Integer howMany)
{
final List<String> resultList = new ArrayList<String>();
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
resultList.add(number);
if (resultList.size() < howMany.intValue())
{
return apply(lookAndSayV3(number, 0));
}
return Collections.unmodifiableList(resultList);
}
}.apply(number);
}
};
}
};
final Function1<Integer, List<String>> lookAndSayWithNumberFixed = lookAndSayWithCurryingAndNumberFixed.apply("1");
System.out.println(lookAndSayWithNumberFixed.apply(3));
System.out.println(lookAndSayWithNumberFixed.apply(5));
System.out.println(lookAndSayWithNumberFixed.apply(10));
Results:
[1, 11, 21]
[1, 11, 21, 1211, 111221]
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
Here are all the examples.
Results:
Using LookAndReadUsingForLoop:
String result1 = number;
System.out.print(result1 + " ");
for (int i = 1; i < howMany; i++)
{
result1 = LookAndSayUsingForLoop(result1);
System.out.print(result1 + " ");
}
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
--------------------------------------------------------------------------------
Using lookAndSayV1:
System.out.println(lookAndSay(howMany, number));
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
--------------------------------------------------------------------------------
Using lookAndSaV2:
System.out.println(lookAndSay2(howMany, number));
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
--------------------------------------------------------------------------------
Using lookAndSaV3:
System.out.println(lookAndSay3(howMany, number));
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
--------------------------------------------------------------------------------
Using lookAndSayUsingList:
final List<String> resultList = new ArrayList<String>();
lookAndSayUsingList(number, howMany, resultList);
System.out.println(resultList);
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
--------------------------------------------------------------------------------
Using lookAndSayUsingList2:
System.out.println(lookAndSayUsingList2(number, howMany, new ArrayList<String>()));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
--------------------------------------------------------------------------------
Using another lookAndSayUsingList2 (without passing List):
System.out.println(lookAndSayUsingList2(number, howMany))
--------------------------------------------------------------------------------
Using Function object:
final List<String> resultListFromFunctionObject = new ArrayList<String>();
new LookAndSayFunction() {
@Override
public void apply(final String number, final int howMany)
{
resultListFromFunctionObject.add(number);
if (resultListFromFunctionObject.size() < howMany)
{
apply(lookAndSayV3(number, 0), howMany);
}
}
}.apply(number, howMany);
System.out.println(resultListFromFunctionObject);
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
--------------------------------------------------------------------------------
Using Function object with returned List object:
final Function2<String, Integer, List<String>> anotherFunction = new Function2<String, Integer, List<String>>() {
@Override
public List<String> apply(final String number, final Integer howMany)
{
return new Function<List<String>>() {
@Override
public List<String> apply()
{
final List<String> resultList = new ArrayList<String>();
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
resultList.add(number);
if (resultList.size() < howMany.intValue())
{
return apply(lookAndSayV3(number, 0));
}
return Collections.unmodifiableList(resultList);
}
}.apply(number);
}
}.apply();
}
};
System.out.println(anotherFunction.apply(number, howMany));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
System.out.println(anotherFunction.apply(number, 5));
[1, 11, 21, 1211, 111221]
System.out.println(anotherFunction.apply(number, 7));
[1, 11, 21, 1211, 111221, 312211, 13112221]
--------------------------------------------------------------------------------
Using currying (number of elements fixed):
final Function1<Integer, Function1<String, List<String>>> lookAndSayWithCurrying =
new Function1<Integer, Function1<String, List<String>>>() {
@Override
public Function1<String, List<String>> apply(final Integer howMany)
{
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
final List<String> resultList = new ArrayList<String>();
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
resultList.add(number);
if (resultList.size() < howMany.intValue())
{
return apply(lookAndSayV3(number, 0));
}
return Collections.unmodifiableList(resultList);
}
}.apply(number);
}
};
}
};
lookAndSayWithCurrying.apply(howMany)
.apply(number);
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
final Function1<String, List<String>> lookAndSayToGet10Elements = lookAndSayWithCurrying.apply(10);
System.out.println(lookAndSayToGet10Elements.apply(number));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
System.out.println(lookAndSayToGet10Elements.apply(number));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
System.out.println(lookAndSayToGet10Elements.apply(number));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
final Function1<String, List<String>> lookAndSayToGet5Elements = lookAndSayWithCurrying.apply(5);
System.out.println(lookAndSayToGet5Elements.apply(number));
[1, 11, 21, 1211, 111221]
System.out.println(lookAndSayToGet5Elements.apply(number));
[1, 11, 21, 1211, 111221]
System.out.println(lookAndSayToGet5Elements.apply(number));
[1, 11, 21, 1211, 111221]
System.out.println(lookAndSayToGet5Elements.apply("111221"));
[111221, 312211, 13112221, 1113213211, 31131211131221]
System.out.println(lookAndSayToGet5Elements.apply("21"));
[21, 1211, 111221, 312211, 13112221]
System.out.println(lookAndSayToGet5Elements.apply("1"));
[1, 11, 21, 1211, 111221]
--------------------------------------------------------------------------------
Using currying (number fixed):
final Function1<String, Function1<Integer, List<String>>> lookAndSayWithCurryingAndNumberFixed =
new Function1<String, Function1<Integer, List<String>>>() {
@Override
public Function1<Integer, List<String>> apply(final String number)
{
return new Function1<Integer, List<String>>() {
@Override
public List<String> apply(final Integer howMany)
{
final List<String> resultList = new ArrayList<String>();
return new Function1<String, List<String>>() {
@Override
public List<String> apply(final String number)
{
resultList.add(number);
if (resultList.size() < howMany.intValue())
{
return apply(lookAndSayV3(number, 0));
}
return Collections.unmodifiableList(resultList);
}
}.apply(number);
}
};
}
};
final Function1<Integer, List<String>> lookAndSayWithNumberFixed = lookAndSayWithCurryingAndNumberFixed.apply("1");
System.out.println(lookAndSayWithNumberFixed.apply(howMany));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]
System.out.println(lookAndSayWithNumberFixed.apply(3));
[1, 11, 21]
System.out.println(lookAndSayWithNumberFixed.apply(5));
[1, 11, 21, 1211, 111221]
System.out.println(lookAndSayWithNumberFixed.apply(10));
[1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]