Last active
May 25, 2025 03:30
-
-
Save sachinlala/c240715a998a23f2686a640128145fc0 to your computer and use it in GitHub Desktop.
Look and say
This file contains hidden or 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
| /** | |
| About the sequence: each row represents the previous row, by counting consequtive digits. | |
| Problem statement: given an input index, generate the row for that index | |
| Logic: | |
| 1. base case: start with [1], at index 0 | |
| 2. for each subsequent index: | |
| 1. take the previous sequence | |
| 2. count consecutive identical digits | |
| 3. output count followed by the digit | |
| 4. repeat for all groups | |
| Optimization: | |
| 1. load the sequence at class level, at bootup | |
| 2. generate upto a reasonable index, for the initial load | |
| Important note: | |
| Beyond a point, the sequence has billions of digits, hence we will need to stream the data to a storage and look-up from there. | |
| */ | |
| import java.util.Map; | |
| import java.util.List; | |
| import java.util.HashMap; | |
| import java.util.ArrayList; | |
| public class LookAndSay { | |
| static Map<Integer, List<Integer>> map = new HashMap<>(); | |
| static { | |
| // initial load | |
| constructMap(55); | |
| } | |
| public static String lookAndSay(final int requiredIndex) { | |
| List<Integer> list = map.get(requiredIndex); | |
| if (list == null || list.size() == 0) { | |
| constructMap(requiredIndex); | |
| list = map.get(requiredIndex); | |
| } | |
| final StringBuilder sb = new StringBuilder(); | |
| for (final int value: list) { | |
| sb.append(value); | |
| } | |
| return sb.toString(); | |
| } | |
| private static void constructMap(final int requiredIndex) { | |
| final List<Integer> list = new ArrayList<>(); | |
| list.add(1); | |
| map.put(0, list); | |
| for (int i=1; i <= requiredIndex; i++) { | |
| final List<Integer> previousList = map.get(i-1); | |
| int counter = 1; | |
| int previousEntry = previousList.get(0); | |
| final List<Integer> currentRow = new ArrayList<>(); | |
| for (final int value: previousList.subList(1, previousList.size())) { | |
| // count the value till it the same | |
| if (previousEntry == value) { | |
| counter++; | |
| } else { | |
| currentRow.add(counter); | |
| currentRow.add(previousEntry); | |
| previousEntry = value; | |
| counter = 1; | |
| } | |
| } | |
| currentRow.add(counter); | |
| currentRow.add(previousEntry); | |
| if (currentRow.size() > 0) { | |
| map.put(i, currentRow); | |
| } | |
| } | |
| } | |
| public static void main(String[] args) { | |
| final String[] expectedSequenceForTest = { | |
| "1", | |
| "11", | |
| "21", | |
| "1211", | |
| "111221", | |
| "312211", | |
| "13112221", | |
| "1113213211", | |
| "31131211131221", | |
| "13211311123113112211" | |
| }; | |
| final int totalTests = expectedSequenceForTest.length; | |
| int passedTests = 0; | |
| for (int i = 0; i < expectedSequenceForTest.length; i++) { | |
| final String result = lookAndSay(i); | |
| final boolean passed = result.equals(expectedSequenceForTest[i]); | |
| if (passed) { | |
| passedTests++; | |
| System.out.println("✓ Test #" + i + " PASSED: " + result); | |
| } else { | |
| System.out.println("✗ Test #" + i + " FAILED:"); | |
| System.out.println(" Expected: " + expectedSequenceForTest[i]); | |
| System.out.println(" Got: " + result); | |
| } | |
| } | |
| System.out.println("\n=== Test Summary ==="); | |
| System.out.println("Tests passed: " + passedTests + "/" + totalTests); | |
| if (passedTests == totalTests) { | |
| System.out.println("🎉 ALL TESTS PASSED! Implementation is correct."); | |
| } else { | |
| System.out.println("❌ Some tests failed. Check implementation."); | |
| System.exit(1); | |
| } | |
| showGrowthStats(55); | |
| // can add more tests here for higher indexes, within index=55 | |
| } | |
| public static void showGrowthStats(int maxIndex) { | |
| System.out.println("\n=== Look and Say Sequence Growth ==="); | |
| for (int i = 0; i <= maxIndex; i += 5) { | |
| try { | |
| final String sequence = lookAndSay(i); | |
| System.out.printf("Index %2d: Length %,8d%n", i, sequence.length()); | |
| } catch (final Exception e) { | |
| System.out.println("Index " + i + ": ERROR - " + e.getMessage()); | |
| break; | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment