Reverse look and say

I am trying to implement a function that takes a string of digits as input and returns a list of inputs to the look_and_say() function that would have resulted in the given string. Essentially, I am looking for a reverse implementation of the look_and_say() process.

For example, given the input string "3754", the expected output should be ['77744444', <375 times 4> ], as these would be the inputs that would generate the string "3754" through the look_and_say() process.

The primary constraint of the problem is that each digit in the input string must have a length of 1, while the count of consecutive occurrences can vary in length. It is crucial to note that in the case of "3754", the desired output should not include "37" times "54" since "54" has a length of 2.

My current approach involves iterating over the input string and using a mutable list to store the results. Additionally, I utilize a memory HashMap to avoid duplicate entries. However, I have encountered an issue with the output, which didn't concatenate the "777" with the "444" with "3754" as input.

fun sayAndCount(
    string: String,
    counts: MutableList<String> = mutableListOf(),
    memory: HashMap<String, String> = HashMap(),
): List<String> {

    if (memory.containsKey(string)) {
       return listOf()
    }

    val times =  string.substring(0, string.lastIndex)
    val number = string.last()
    val count = number.toString().repeat(times.toInt())
    memory[string] = count

    if (string.length <= 3) {
        return listOf(count)
    }

    for (index in 2 until string.lastIndex) {
        counts.addAll(sayAndCount(string.substring(0, index), counts, memory))
        counts.addAll(sayAndCount(string.substring(index), counts, memory))
    }

    return counts.toList()
}

I would greatly appreciate it if someone could point me in the right direction.

The problem is in your for loop: it adds results for substrings, while you should only add solutions for the complete string.

Secondly, you should only make one recursive call -- consider the left partition as something you will not split in more partitions (as that would lead to duplicates); and only make the recursive call for the rest of the string.

So you should have an inner loop that iterates over the results coming from recursion, and then in that inner body you should prefix each of those results with the left-partition, so that you cover the whole string.

Finally, your memory map should have the list of solutions, not a single solution (string) like you did with memory[string] = count.

Here it is implemented in JavaScript:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const memo = new Map;

function solutions(s) {
    if (memo.has(s)) return memo.get(s);
    if (s.length < 2) return [];
    
    const results = [s.at(-1).repeat(+s.slice(0, -1))];
    // Choose size of left partition
    for (let i = 2; i < s.length - 1; i++) {
        const left = s[i-1].repeat(+s.slice(0, i-1)); 
        for (const right of solutions(s.slice(i))) {
             results.push(left + right);
        }
    }
    memo.set(s, results);
    return results;
}


// Example:
console.log(solutions("3754"));

<!-- end snippet -->

function reverse_look_and_say(s) {
    let result = [];
    for (let i = 0; i < s.length; i += 2) {
        let count = s[i];
        let digit = s[i+1];
        result.push(digit.repeat(parseInt(count)));
    }
    return result;
}

1. The function takes a string s as input, which represents the result of a look-and-say sequence.

2. The function initializes an empty array result to store the final result.

3. The function enters a for loop that iterates over the input string s in increments of 2.

4. In each iteration of the loop, the function extracts the count and digit from the input string by indexing s at positions i and i+1, respectively.

5. The function then appends the digit repeated count times to the result array using the push method and the repeat method.

6. Once the loop has finished iterating over the entire input string, the function returns the final result array.

This is relatively straightforward I don't understand the use of hashmaps here. If I'm not wrong this should answer your question

python
def convert(num):
    num_str = str(num)
    result = ''
    for i in range(len(num_str)):
        result += num_str[i] * (10**i)
    return int(result)

print(convert(3754))
# 77744444