Talk:ABC problem: Difference between revisions
→order of blocks
m (→Definition please: changed "picture" to use bold.) |
|||
| (One intermediate revision by one other user not shown) | |||
Line 80:
::::::: Scrabble: true but the order to arrange the letters is of no importance. And can you point me to a definition of greedy algorithm? The Wikipedia article I saw does not exactly describe what your first attempt did, does it? --[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 12:31, 12 January 2014 (UTC)
:::::::: A greedy algorithm is one that uses the quickest/simplest/shortest answer for each step, even though that may cause the overall procedure to fail. In this case, that refers to picking the first block that has the letter sought. Doing that removes the other letter on the block from availability and may result in returning "unable to make this word", when in fact a different choice of block for the chosen letter might allow the word to be made. Thus a comprehensive solution can say "yes" as soon as it finds any answer, but really has to try all combinations of the possible blocks for each letter before it can say "no". The algorithm used by the ZX-81 and Commodore BASIC solutions has this problem... --[[User:Markjreed|Markjreed]] ([[User talk:Markjreed|talk]]) 01:45, 18 May 2022 (UTC)
:::::::: I was referring to the order of the blocks (and the manner in which they are chosen, and then marked for non-participation for later choices). I'm not sure what you mean by arranging the letters. The whole point is to arrange the letters [here and ''Scrabble'' (R)] to spell words. As for what you saw on Wiki, I can only surmise what WIKI ''exactly'' describes; I think the Wiki article pretty much describes the methodology of the initial attempt of the what the REXX version 1 program did (albeit the original REXX version 1 algorithm didn't go deep enough to find a solution for some other later examples talked about, which made it an ineffective and an incorrect algorithm). There are other definitions of ''greedy algorithm'', but I don't to spend time and effort to see if those definitions apply to the initial REXX version 1 attempt, one reason is the initial REXX version 1 program is defunct. The initial REXX attempt could spell '''bbaa''' but not '''abba'''. The current REXX version 1 can (using the pool of blocks: '''AC AC AB AB''' in any order). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 00:54, 13 January 2014 (UTC)
| |||