The Resistance puzzle discussion

Indeed it seems possible, and the exponential count of re-arrangements is where this puzzle earns its seat in the Very Hard ranks. Care needs to be taken in order to avoid recalculating expensive operations.

~34 ms in Python3 for the last test case. struggled a lot until i discovered identical sequences could be different wordsā€¦ simple recursion with memoization.

Well, it took me three months and fifteen submits. It got to around 120ms for the last test case in C++ (my solution turned out to be somehow similar to Agadeā€™s).

Throughout the three months, Iā€™ve read through this entire thread multiple times. There were, of course, some discouraging posts up there amidst the ones that were actually helpful.

This puzzle wasnā€™t entirely easy for me but Iā€™m happy that it wasnā€™t easy - the process to get to the end was exhilarating.

If youā€™re stuck, persist; and if you havenā€™t started the puzzle already, do start and try it out. :slight_smile:

8 Likes

Is there anyone that can help with some hints on how to solve this. I am new to coding and trying to solve this in Haskell. I have been banging my head against the wall trying to get past the fourth test (LSLD).

any chance you could help with how you solved it?

Thereā€™s a few posts in this thread with hints. The big one that got me to 100% was saving the outcome at each stop, so if I found myself in the same position again I wouldnā€™t have to re-parse the path. I left a post in April '16 explaining it.

Does the rust compiler is enable with optimisation ? Because I get a 2200ms for the ā€œSĆ©quence longue, grand dictionnaireā€ with debug mode on my laptop and I get a 53ms with release mode (enable optimisation when compiling). I also use the same code ported in Kotlin and it succeed on all the tests.

No release mode for puzzles.

1 Like

Ok thankā€™s for the answer :grin:

In the core of the problem, there is a really simple mathematical solution :slight_smile:

I fail at:

  • Simple Test
  • Dictionnary contains differents words for a same code
  • Many possibilities, with small sequence and small dictionnary
  • Long sequence, small dictionary

does anyone have an idea on the problem with these test cases.
Iā€™m really stuck and canā€™t figure out the issue

what tests are you failing? IDE tests or validators (when you submit)?

As for hints, test names seem like relatively good directions to me.

By default, you can suppose that there is no problem with test cases of puzzles solved by thousands of other developers.

the 4 test cases iā€™m failing are the validator (after submit; all the ide test are passed). lol iā€™m sure that the test cases are correct i just canā€™t figure out whatā€™ going on. for the ā€œsimple testā€ all that says is that its simple
for the ā€œdictionnary contains more words for same codeā€ i tested the same situation with the 4th test on the ide.
for the ā€œmany possibilities with small sequenceā€ i tested my code with 2 examples given in the posts (look for ā€˜EEEā€™) one of them was
ā€¦
2
E
EEE
for a result of 19

my problem is that iā€™m not able to think about any case that makes my program fails

so i finally fixed the issue.
i had a bug not reading the last word in the input dictionary word.
fixed that and got 100%.
Thank you _CG_Thibaud for your help.

1 Like

Could you explain why 19 please ? ( and not 2) :sweat:
for this :
ā€¦
2
E
EEE

1 Like

The codingame markdown editor (now?) formats any sequence of dots with more than three dots into ā€¦

So ..... will become ā€¦ unless you quote it as code.

I know this is a sad answer, took me some time to realize it as well ;).

Here are two test cases that helped me:

.
2
E
EEE

Answer is 1. Looks super basic but I was passing the 4 IDE tests and failing that.

....----
4
E
EE
T
TT

Answer is 25. With three dots instead of 4 it should be 15.

Good luck!

2 Likes

:sob: lol thanks a lot !

Iā€™m really ashamed to write this, but if it can help someone who was able to make the same stupid mistake, it will serve me as a penance.
Working in JAVA, I wrote code with a clear idea what to do and procedure returning number of possible phrases for a line of morse code, that was recursively called was of the type Integer. It should be enough :slight_smile: or so I thought, before forgetting about it.
So I passed first 3 cases without problems, but #4 didnā€™t gave me expected value.
Tumbling code up and down, I could not find what was wrong, as it is usually when it is something stupid like that.
As soon as the type was changed into long, I got things straight.
It took me almost a day (with watching some games on TV) to figure it out.:frowning_face:

1 Like

Hi,
Can someone please explain what the goal is?
I say this because I have a working algorithm that checks the encoded message against the powerset of the list containing the morse code encoding of all the words in the dictionary. I assumed this was the goal since the ā€œ-.-ā€ test gives as an only possible answer the K ("-.-") and not A (".-") but the ā€œHELLOWORLDā€ test has an expected answer of 2, one for each combo [HELL+OWORLD, HELLO+WORLD]. So I assumed that the goal was to check for combinations that resulted in the whole encoded message being produced by said combinations, thus making just A not a valid answer for ā€œ-.-ā€ since a T ("-") would be missing.

That said, since I check through the powerset of the encoded versions of the words in the dictionary, it is not possible to ā€œskipā€ a certain combination yet the answers produced are not the expected answers.

P.S. It times out on large big, Iā€™ll optimize later, it fails the ā€œone possibleā€, ā€œno possibleā€ and ā€œmany possibleā€ tests
P.S.2. I get the encoded versions using a function I wrote for uni, which gets the code from a flattened binary tree, I checked, it works.

Thanks for the help.

Thanx for your test but i canā€™t undertand how it works. I am using Java and I pass the first 5 test when you submit, but Iā€™m afraid I havenā€™t understood something.
How do you get 19 solutions for this?
ā€¦
2
E
EEE

I only see 2.
E (3 times until the end)
EEE.(1 time)

I would apreciate an explanation or a list to know what 19 are.

And again, thanks for the tests