La FÊe Verte
#toyprogrammingchallenge
Another Freebie...
This problem was asked by Facebook.
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is not allowed.
đ Dr. Freemo :jpf: đŗđą
@Absinthe Since the main complexity issue here becomes space complexity im going to tackle this as a space optimized solution. Sould also be pretty close to ideal on time complexity if i do it right too.
đ Dr. Freemo :jpf: đŗđą
@Absinthe My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
I also need to improve the display function as it does breadth first not depth first thus breaks the optimization right now.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
đ Dr. Freemo :jpf: đŗđą
@Absinthe My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
I also need to improve the display function as it does breadth first not depth first thus breaks the optimization right now.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
đ Dr. Freemo :jpf: đŗđą
@Absinthe My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
https://git.qoto.org/snippets/4
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
I also need to improve the display function as it does breadth first not depth first thus breaks the optimization right now.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
đ Dr. Freemo :jpf: đŗđą
@Absinthe My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
https://git.qoto.org/snippets/4
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
Incomplete paths can also be trimmed to further reduce the space. But since incomplete paths each add only a single leaf node to the tree, and might be useful for various use cases I decided to keep it.
đ Dr. Freemo :jpf: đŗđą
@Absinthe BTW i intentionally chose to list them not count them. I could probably optimize further if I counted only. In fact that would be trivial, so i think ill solve that too.
Kyle
Linear in time and space by taking advantage of the Fibonacci numbers.
function count = interpretations(string)
ambig = string(1:end-1) == '1' | (string(1:end-1) == '2' & string(2:end) <= '6');
ambig &= string(1:end-1) ~= '0' & string(2:end) ~= '0' & [string(3:end) '1'] ~= '0';
ambig = [false ambig false];
consec = find(ambig(1:end-1) & !ambig(2:end)) - find(!ambig(1:end-1) & ambig(2:end));
fibo = zeros(max(consec), 1);
fibo(1:2) = [2 3];
for i = 3:max(consec)
fibo(i) = fibo(i - 1) + fibo(i - 2); end;
count = prod(arrayfun(@(x)fibo(x), consec)); end;
đ Dr. Freemo :jpf: đŗđą
lol not efficient if **all** you need is the count, but it does work of course.
đ Dr. Freemo :jpf: đŗđą
@billstclair @Absinthe Time-complexity has nothing to do with raw-speed. If you do the brute force solution and actually list all solutions with a copy approach (the absolute simplest least efficient way) then your dealing with exponential space complexity. Good luck computing large datasets on even the beefiest of machines where a linear solution would attack it with ease.
đ Dr. Freemo :jpf: đŗđą
This is the best solution IMO for count-only (technically what the question asked).
Bobinas P4G is a social network. It runs on GNU social, version 2.0.1-beta0, available under the GNU Affero General Public License.
All Bobinas P4G content and data are available under the Creative Commons Attribution 3.0 license.