Easy problem to fix: the provided starting code has a function decodeMorse(), but shouldn't it be named decode_morse()?

Hey Zwyx! I finally got back to it, and figured it out. My program dissasembles the deck as it decodes it, and a successful decoding turns the deck into an empty list. Since Python passes lists by reference this change persists into the caller's scope. So, in the last set of tests with a randomized deck my code succeeds but empties out the deck, and then the tests call your control decode() with an empty list. I changed my decode() function to operate on a copy of the deck and everything worked; all tests passed.

Two (not mutually exclusive) possibilities for closing this hole: (1) specify that user functions not change their arguments; or (2) change tests so that they call user functions with a copy of the deck. The second is easy enough; just pass "deck[:]" instead of "deck".

Thanks for the challenge, and for the help debugging the problem!

Got it, thanks. It'll take at least a few days to get to it, though. I have some other commitments that need attention.

Yeah, that puzzles me too --- that other people have completed the Python version of the kata.

It's been years since I've used GPG and have lost track of my private keys. Maybe on some archive media somewhere. But I've also forgotten the passphrase!

So, apropos the kata, here's my email, encoded in a deck, if you'd like to send the program that way:

AC 2C 3C 4C 5C 6C 7C 8C 9C TC 3H 6D KH
QS TH KS JD 3D 6H 2S 7S 2H AH 8S 2D 3S
QD TS QC 8H 4S 9D 8D JH AD 9H 7H 5D TD
5H KD KC AS 4H 6S 4D 5S 7D QH JC JS 9S

OK, I just looked at it again. I think there is a problem with the randomized-deck tests. Here's a test that my code failed today:

QC 9S 8H QH 3C 6D 2D 5S 3S AC TC 7H 8C
5D 8D 4D 8S KC JD 5C QS JH QD 6S KH 7S
KD JC AD 3D TS TH 7D 9H 4S 6C 4H 9D 4C
5H KS 9C JS 2H AH 2S 3H 6H 2C 7C TD AS

'ZNSZZCXGCBGXTAAUVHSTLHVHBGXYNODYUJWTLEQASRHAMVI' should equal None

However, my local tests suggest it should not be None. Here's output from a test where my program encodes the message to a deck, then decodes the deck back to a message. The round-trip succeeds:

ZNSZZCXGCBGXTAAUVHSTLHVHBGXYNODYUJWTLEQASRHAMVI
['QC', '9S', '8H', 'QH', '3C', '6D', '2D', '5S', '3S', 'AC', 'TC', '7H', '8C',
'5D', '8D', '4D', '8S', 'KC', 'JD', '5C', 'QS', 'JH', 'QD', '6S', 'KH', '7S',
'KD', 'JC', 'AD', '3D', 'TS', 'TH', '7D', '9H', '4S', '6C', '4H', '9D', '4C',
'5H', 'KS', '9C', 'JS', '2H', 'AH', '2S', '3H', '6H', '2C', '7C', 'TD', 'AS']
=> 'ZNSZZCXGCBGXTAAUVHSTLHVHBGXYNODYUJWTLEQASRHAMVI'

Here's a test where I start with the deck as given in the test, and decode it to a message:

['QC', '9S', '8H', 'QH', '3C', '6D', '2D', '5S', '3S', 'AC', 'TC', '7H', '8C',
'5D', '8D', '4D', '8S', 'KC', 'JD', '5C', 'QS', 'JH', 'QD', '6S', 'KH', '7S',
'KD', 'JC', 'AD', '3D', 'TS', 'TH', '7D', '9H', '4S', '6C', '4H', '9D', '4C',
'5H', 'KS', '9C', 'JS', '2H', 'AH', '2S', '3H', '6H', '2C', '7C', 'TD', 'AS']
=> 'ZNSZZCXGCBGXTAAUVHSTLHVHBGXYNODYUJWTLEQASRHAMVI'

Again, everything is as it should be.

Did someone else translate the kata into Python? Perhaps they could be encouraged to have a look.

No, I went on to try the Bernoulli Numbers kata and spent a couple of days optimizing code and reading up on Bernoulli numbers. :-)

I was hoping you'd be able to find the bug. Might it be that the Python tests still expect "10" instead of "T" for ranks of ten?

I'll have another look.

Trying to go through all permutations of the cards is probably the problem. The number of permutations is HUGE -- about 18 orders of magnitude larger than the estimated number of atoms making up the earth (about 10^50, see https://www.fnal.gov/pub/science/inquiring/questions/atoms.html). The crux of the kata is figuring out how to compute the permutation without brute-force enumeration (and then going the other way, figuring out where a given permutation would be in a sorted list of all possible permutations). Try working on small problems to develop intuition -- say, if you had a deck that had just 4 cards (A, B, C, and D), the possibilities are:

A B C D

A B D C

A C B D

A C D B

A D B C

A D C B

... 3 more 6-line blocks

Note that this 6-line "A" block has sub blocks -- a 2-line "B" subblock, a 2-line "C" subblock, and a 2-line "D" subblock.

Where would "B A C D" come -- in which 6-line block? Apply that thinking recursively. Within the "B" block, where would "A C D" come?

Hopefully this will help get you started. And as a hint, div (//) and mod (%) are your friends!

Regarding lists the kata states: "(An adjacency list) is sorted in
order A0 to A5 ...", but this is not adhered to in the test cases.
This sorting is not necessary and the specification can be dropped.

It is not specified whether graphs can have disconnected components,
and as a special case of that, whether isolated vertices are allowed.
It is also not specified what find_all_paths should do if there
are no paths (because the start and end are in disconnected
components), though it's pretty obvious it should be an empty list.

If a kata specifies that graph edges have weights, then those weights
should be used. A simple way to do this would have "find_all_paths"
output a list of (path, total_path_weight) pairs, and perhaps specify
that the list's primary sort key be total_path_weight.

It should be specified that "find_all_paths" should only return paths
in which no node is repeated. Otherwise, in an undirected graph, if
there is a path from A to B, there are infinitely many paths from A
to B: (A-B, A-B-A-B, A-B-A-B-A-B, etc.)

The instructions define a cycle as a "loop" but does not define
"loop". I suggest dropping this definition entirely, as it does
not come into play in the kata but is likely to be confusing --
students expect that information in instructions is going to
be relevant to understanding or solving the problem. If a
student is interested in learning more about graphs, a simple
web search will return plenty of information. If you wish to
actively encourage students to learn more, just include the
statement "This kata just scratches the surface of
what graphs are and what is possible with them. If
you are interested in learning more about graphs,
check out $A_GOOD_INTRODUCTORY_URL".

The sort order for the returned result of "find_all_paths"
should be specified exactly, rather than with a single
example and hint.

The information stored in a Graph object is unnecessary, and can even
conflict with what one of the methods might receive -- a user of the
class can easily initialize a Graph object with one graph, then call
one of the conversion methods with a completely different graph.
Consider instead a Graph init method that would detect the type of its
argument, then convert it to whatever internal representation the author
wants to use. The class would then have methods "as_dict", "as_matrix",
and "as_list", which would return the indicated representation after
converting from the internal representation. This structure is simpler
yet still forces the author to write at least five conversion methods.
The class could also have a method "vertices" which returns a list of
all vertices found in the graph. The class skeleton would look like:

class Graph():
def init(self, graph):
""" Detect the representation of the graph argument, and
convert to an internal representation and store it.
"""
pass

  def vertices(self):
      """ Return a list of all vertices, in alphabetical order.
      """
  pass
  
  def as_matrix(self):
      """ Return the graph as an adjacency matrix.
      """
      pass

  def as_list(self):
      """ Return the graph as an adjacency list.
      """
      pass

  def as_dict(self):
      """ Return the graph as a adjacency dict.
      """
      pass

  def find_all_paths(self, graph, start_vertex, end_vertex):
      """ Return a list of all (path, total_weight) pairs, where
          path is a list of nodes from start_vertex to end_vertex
          with no vertices repeated, and total_weight is
          the sum of all the edge weights in the path.
      """
      pass

Hope this helps.

Difficult, but definitely learned a lot doing this one. Not sure the effort unrolling loops and list comprehensions in order to squeeze out the last milliseconds of efficiency was time well spent, though.

I was a little surprised too. I reflected that you were probably right that camel case wouldn't start with upper case, but decided to check to be sure.

Views vary as to whether PascalCase is a form of camel case. For example, the Wikipedia article "Camel case" states "Some programming styles prefer camel case with the first letter capitalised, others not." Simple fix is to state in the problem that initial letters will never be uppercase.

Problem does not specify what to do with something like "theABCs", nor what to do if the first letter is a capital.