HW8 Clarifying exponential.txt

_ginevra_ (620 points)
0 8 15
asked Dec 5, 2020 in HW8 required by _ginevra_ (620 points)
Looking at the test exponential.txt it has occurred to me that in cases in which the clues are all the same I don't exactly understand what type of order should be followed by Nikita to produce '"secret". In this case are there different "secrets" lists that are the permutations of the set of secrets or is there in fact an order that must be followed? Can anyone clarify this?

*below is exponential.txt

# cities: ROME MILAN
# clues:  la la la la la la la la la la la
# start:  ROME


2 Answers

Best answer
Dario_loi (1710 points)
0 3 10
answered Dec 6, 2020 by Dario_loi (1,710 points)
selected Dec 7, 2020 by _ginevra_

You can get a more clear idea of what is going on if you look into the test's corresponding .JSON instruction

this is the code to run the test contained in the test01.py file:

    def test_random_expo4(self):
        filename = "exponential.txt"
        clues = ' '.join(['la']*4)
        start = 'ROME'
        TT = [ 'tic', 'tac', 'toc' ]
        BB = [ 'bing', 'bong', 'bang' ]
        expected = { (f"{t1} {b2} {t3} {b4}", 'ROME') for t1 in TT for b2 in BB for t3 in TT for b4 in BB }
        return self.do_test(filename, start, clues, expected)

if you plug that expression into a python interpreter, you see that expected is muuuch bigger than 9, that is because, whenever you get a clue, in this case la, and there are multiple routes that you can take for that clue, (in this case, la brings you three times from rome to milan, and three times from milan to rome), you must explore all possible paths that clue will lead to, so, for each of the 'romes' at the start, you end up three times in milan, nine times back to rome, twenty-seven times back to milan again, and so on and so forth, and then, when you are finished, you must step all the way back and take the second rome's path.

the test's name is exponential.txt 'cause the expected output should follow this formula (correct me if I am wrong):

n = number of cities (in this case 3)

c = number of clues

expected out = n^c

Which coincidentially also seems to correspond to all the possible permutations of the secrets (tic toc tac, bing bong bang)

Nicholas Tiveron (1670 points)
2 5 8
commented Dec 6, 2020 by Nicholas Tiveron (1,670 points)
edited Dec 6, 2020 by Nicholas Tiveron
Actually, my only doubt was if it continued or not after the first secret (and I assumed not but apparently I was wrong) and now that I'm looking at the code in the test, which I missed before, it seems that it does since there are 81 total combinations of secrets (which, if I interpreted it correctly, also means that your formula should work, even though I don't know why they changed the number of clues from 11 in the file to 4 in the test). What I don't get is why the first secret would be: ('toc bong tic bing', 'ROME') since 'toc' and 'bong' are not the first clues you encounter.
Dario_loi (1710 points)
0 3 10
commented Dec 6, 2020 by Dario_loi (1,710 points)
if you look closely to the output of expected, you see that the data structure is a Set

sets are (despite what some people might tell you) an unordered data structure, therefore every entry gets mixed up randomly, or more often, for optimization reasons, ordered in an increasing fashion, that is why the order in which the clues appear in the expected file doesen't match your actual order.

but don't worry, since they are unordered, your program's output order also won't matter.

Also they haven't changed the number of clues, they just did multiple tests with the same kind of pattern, since they probably realized it's really scalable, i'd be looking forward to test_random_expo10 as the one that gives our programs the most trouble.
Nicholas Tiveron (1670 points)
2 5 8
answered Dec 6, 2020 by Nicholas Tiveron (1,670 points)
In the instructions it's explained that: "From the same city, the same clue can lead to multiple alternative cities. So the paths to explore could be multiple and the secrets more than one." and also that "there may be different instructions that even starting from the same city AND having the same clue, lead to different cities and/or produce different secrets".  

From these assumptions and basing my logic on the secrets constructed in the file "esempio.txt" , the secrets in this case would be (note that I only split them into multiple lines for readability):

('tic bing',  'MILAN'), ('tic bong',  'MILAN'), ('tic bang',  'MILAN'),

('toc bing',  'MILAN'), ('toc bong',  'MILAN'), ('toc bang',  'MILAN'),

('tac bing',  'MILAN'), ('tac bong',  'MILAN'), ('tac bang',  'MILAN')

For a total of 9 secrets (= 3 (different secrets) ^2 (cities)), hence the filename "exponential". Additionally, by following the order of the secrets, this should be the only output possible (so, even in this case, there shouldn't be other possible orders). Hope this was clear.

Of course, I could be wrong, so if anyone else could add by confirming/debunking this I would be grateful.
_ginevra_ (620 points)
0 8 15
commented Dec 6, 2020 by _ginevra_ (620 points)
Yes I understand what you are saying but in fact in this case you not only have the same clues at the same city but also the same destination also noting that the clues are always the same. This is why it gets confusing. Also according to the description of the HW a secret is complete when there is no corresponding city for the next clue, so in this case I would assume the secrets to be of this length

Tic bing toc bong tac bang

So in fact all the possible secrets would be permutations of the Rome secrets in indexes 0,2,4 and permutations of the Milan secrets in indexes 1,3,5. So another example according to this logic would be

Toc bin tic bong tac bang

At least this is the argument that I arrived to from my understanding of the hw. It would be convenient if any forum moderator could reply to settle this matter thank you.