Talk:ABC problem: Difference between revisions
→order of blocks
m (→Definition please: added an article.) |
|||
| (11 intermediate revisions by 5 users 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)
Line 90 ⟶ 92:
::Yeah they're a pretty common toy. They look something like [http://career-city.com/resumeimages/block-letter-font-8.jpg this]. Letters on opposite sides and the other four sides are blank (or maybe they have pictures carved/printed on them instead). --[[User:Mwn3d|Mwn3d]] ([[User talk:Mwn3d|talk]]) 21:01, 5 June 2014 (UTC)
:::
<
__________________
/\ \
Line 125 ⟶ 127:
\ / /
\/_________________/
</
== Alternative Common Lisp version ==
I think this is a little bit more consice (at least it is definitely shorter). I'm not sure about adding it in addition to the old one / instead?
<code>
(defun word-possible-p (word alphabet)
(labels ((%usablep (b) (find (char-upcase (char word 0)) b)))
(or (zerop (length word))
(iter
(for candidate :in (remove-if-not #'%usablep alphabet))
(when (word-possible-p
(subseq word 1) (remove candidate alphabet :count 1))
(return t))))))
</code>
[[User:Wvxvw|Wvxvw]] ([[User talk:Wvxvw|talk]]) 13:37, 5 April 2015 (UTC)
== C and Perl versions ==
In the C recursive version, if I've understood this correctly, once a character has been
matched successfully by
''if (b[i][0] != c && b[i][1] != c) continue;''
there is no need to keep matching it, therefore, I would put
''break;''
at the end of the ''for'' block in ''can_make_words''.
Similarly with the Perl recursive version, perhaps
''last;''
at the end of the ''for'' block in ''_can_make_word''.
For example, if we test the 2nd set from the Perl version where the blocks are US TZ AO QA and the word is "auto", without and with the ''break''/''last'', the former returns true, the latter
false.
I believe false is the correct answer, i.e. auto can't be made from US TZ AO QA in the order
the letters appear.
: It's supposed to be a ''set'' of blocks, which means there's no specific order among them. So "auto" can be made by "Q[A] [U]S [T]Z A[O]". --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 18:57, 18 May 2015 (UTC)
:: I'm quite wrong, its not the order of the letters. The matches made are the first but not necessarily the best. Perldoc for keys function states "Hash entries are returned in an apparently random order", so depending on the order the hash keys are returned from %blocks I sometimes see the candidates as AO,SU,TZ then no more candidates, and sometimes as AQ,SU,TZ,AO. --[[User:Buggerit|Buggerit]] ([[User talk:Buggerit|talk]]) 10:13, 19 May 2015 (UTC)
::: I still don't see how that happens. The use of <code>local</code> can be confusing, but it appears to be correct, and all the test cases work. Do you have a counterexample where it failes? --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 20:32, 19 May 2015 (UTC)
| |||