Talk:ABC problem

Solution?

Had fun with this one last night after playing with my daughter. Should I include a solution? --Jking (talk) 14:46, 8 January 2014 (UTC)

You probably need to have a solution at hand to write a good task. If you've got it, why not add it as the first example? (I do) --Paddy3118 (talk) 20:34, 8 January 2014 (UTC)

Added.--Jking (talk) 03:46, 9 January 2014 (UTC)

Examples OK?

It appears to me that, given the set of blocks on the page, the result of a test on "BOOK" should be true?

Also it is possible to make a zero-length word with whatever letters you have. In which case shouldn't the results of can_make_word "" be True? --Tikkanz (talk) 19:42, 8 January 2014 (UTC)

I think you can spell the empty string with zero blocks. So the first test should return true. The reasoning is similar to the Python function all([]) returning True. Another clue comes from the Python iterative solution, that has needed a special case for the empty string. Often in algorithms if you have a special case it needs a special justification.-bearophile (talk)

Hi Bearophile, I think you are premature in your changes. The recursive Python solution has no such special case handling and returns False. I will revert your task change pending further discussion... (P.S. did you read my comments below on the null case)? --Paddy3118 (talk) 13:50, 9 January 2014 (UTC)

Hi, you need one B and two O's but the only blocks with either a B or an O are the two blocks BO and OB - you can't spell three letters with two blocks! --Paddy3118 (talk) 20:30, 8 January 2014 (UTC)

(The difficult null case). I take it as you cannot spell the null string with blocks as no block has a face without any characters. --Paddy3118 (talk) 20:37, 8 January 2014 (UTC)

OK, I was/am confused then about what the rules for using a block are? If a block is chosen, can only one of letters on the block can be used in the word? If so perhaps the following should be added as an additional constraint. "Only one letter can be used from each block chosen".

I guess that is a logical way to explain the null string generating "False", but using no blocks from the collection can also be thought of as "using the given set of blocks". Maybe better specification is required for this case too? --Tikkanz (talk)

can_make_word("") == False

Currently the original task creator set the answer for a null string as being False. Various people think that it could and should be True. There are three ways I think of dealing with this:

1. Keep the original False.
2. Switch to True.
3. Remove the need for the null string case from the examples and silently allow either True or False for this case.

It would be good to hear from the original task creator on this issue as well from other interested parties. --Paddy3118 (talk) 18:44, 9 January 2014 (UTC)

Well the question is, "Can you make this word given this collection of blocks?" The answer doesn't make sense without valid input and there are numerous ways to handle it in different languages. I chose the "false" value arbitrarily since it could be readily interpreted as, "no, I cannot spell any words if you don't give me one to spell." The case for "true" is equally valid. If it would help avoid bike-shedding over the issue I'd opt for removing the case altogether.--Jking (talk) 20:20, 9 January 2014 (UTC)

An empty string is a word without letters, which is not the same as "not giving you a word". If you are going to choose arbitrarily between two interpretations anyway, choose the one that's simpler. We want to use a subset of the blocks to spell out a word, using an empty subset (i.e. no blocks) is the way to spell a word with no letters, so "true" is a more natural answer. What you want is better expressed as "using a nonempty set of blocks to spell a word", which is different and more (and unnecessarily) restrictive. Choosing "true" or "false" are not equally valid if you define the task clearly. --Ledrug (talk) 20:49, 9 January 2014 (UTC)

I'm aware of the case for "true" and had considered it before choosing "false" for a moment. It was simply the first test case I wrote. I chose "false" and moved on and haven't given it this much thought (though I think I might've wondered what is a word with no letters?). I honestly don't see either choice being essential to the spirit of the task and would happily accept "true" if that makes more sense to more people.--Jking (talk) 21:14, 9 January 2014 (UTC)

So far, it seems that a choice of item 3 would upset everyone equally ;-)

I would be inclined to swap to item 3. Any nay-sayers? --Paddy3118 (talk) 09:52, 10 January 2014 (UTC)

I agree with Jking that the handling of a null is pretty meaningless in terms of this task (I don't imagine that spelling "" comes up much when using these blocks!), so I support choosing item 3. --Tikkanz (talk) 11:12, 10 January 2014 (UTC)

Not a set of blocks

The block (F S) appears twice so I changed the description to use the word collection rather than a set of blocks. I have also added a specific example "CONFUSED" that will fail if their is only one (F S) block available. --Paddy3118 (talk) 20:49, 8 January 2014 (UTC)

Why not change one of the toy blocks to a   (S F)?   That is the case for   (B O). -- Gerard Schildberger (talk) 01:42, 9 January 2014 (UTC)

There could be duplicate blocks. I didn't mean "set" in the mathematical sense which would be confusing. Collection seems appropriate. --Jking (talk) 02:55, 9 January 2014 (UTC)

Greedy algorithm

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"). --Ledrug (talk) 20:12, 10 January 2014 (UTC)

Excellent point and a good test case! I shall look into updating the example.--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. -- Gerard Schildberger (talk) 23:44, 11 January 2014 (UTC)

order of blocks

PL/I has a problem:
blocks = 'US TZ AO QA'
word = 'Auto' cannot be spelt when taking AO for the A of AUTO. Therefore I created version 2 earlier for REXX and now for PL/I (which are the two languages I know rather well). I cannot say how other languages' solutions behave.--Walterpachl (talk) 19:58, 11 January 2014 (UTC)

Using your blocks I get:

BLOCKS: US TZ AO QA

Can we spell    'AuTO'? True Using: A from 'QA', U from 'US', T from 'TZ', O from 'AO'

--Paddy3118 (talk) 20:55, 11 January 2014 (UTC)

Thanks! Fine :-) --Walterpachl (talk) 21:08, 11 January 2014 (UTC)

I assume tha the programs should work for any set of blocks and any word --Walterpachl (talk) 21:24, 11 January 2014 (UTC)

Yes, indeed.   I hope the author will drop this task back into draft status and add the word   abba   (with the AB AB AC AC pool of blocks, in that order). -- Gerard Schildberger (talk) 22:09, 11 January 2014 (UTC)

I think the order of blocks should not be relevant. Think of Scrabble. --Walterpachl (talk) 23:10, 11 January 2014 (UTC)

For a greedy algorithm, the order of blanks may be important.   That is, in another order than shown (i.e., AC AC AB AB), it most likely would find a solution.   (This was an error in my first attempt at programming a solution in REXX which turned out to be a greedy algorithm and it didn't find a solution for the   abba   or   auto   problem as stated above).   The above block order (AB AB AC AC) is the "worst" order to be in, as a greedy algorithm would find a letter on the first block that contained the letter, and "remove" that block from further consideration.   The game of Scrabble (R) doesn't have multiple letters on a tile. -- Gerard Schildberger (talk) 23:35, 11 January 2014 (UTC)

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? --Walterpachl (talk) 12:31, 12 January 2014 (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). -- Gerard Schildberger (talk) 00:54, 13 January 2014 (UTC)

Definition please

Am I to understand that these are 2-sided "blocks"? I certainly never had anything like that as a child...