Anonymous user
Talk:ABC problem: Difference between revisions
→Greedy algorithm: added another test case with a different set of blocks. -- ~~~~
(→order of blocks: best/worst solution, order of blocks. -- ~~~~) |
(→Greedy algorithm: added another test case with a different set of blocks. -- ~~~~) |
||
Line 51:
The python iterative solution is greedy and not garanteed to find a solution. Example: if blocks are "AB", "AB", "AC" and "AC", it may fail to find a solution for the word "ABBA". This particular algorithm only works if each letter appears on only one type of blocks. Not finding a solution when there is one is a matter of correctness. Either the task should put further constraints on the blocks ("All blocks containing letter A are of the same letter combinations"), or such algorithms should clearly state the chance of failure ("This is a greedy algorithm that's fast but may fail to find an answer"). --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 20:12, 10 January 2014 (UTC)
:Excellent point and a good test case! I shall look into updating the example.--[[User:Jking|Jking]] ([[User talk:Jking|talk]]) 21:08, 10 January 2014 (UTC)
:: Yes, while all the programming examples correctly process the words given for the specified blocks (as of now), some programming examples don't find a solution for the '''abba''' situation. I think it'd be a good idea to add another set of blocks ('''AB AB AC AC''') with the word '''abba''' as a test case word. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 23:44, 11 January 2014 (UTC)
== order of blocks ==
| |||