The Resistance puzzle discussion

Puzzles
#1

Feel free to send your feedback or ask for some help here!

1 Like
#2

I get 90% for my solution with a failure for the “long sequence, large dictionary” test, which is also the case (#4) that I fail in the dev section. This doesn’t make much sense to me since there really isn’t any way I can see for the dictionary size to make a difference in my code. The answer I get for dev test case #4 is 2075131904 (vs the expected 57330892800). Any clue to what I could be missing? What about “large dictionary” could cause a problem that doesn’t show up in “small dictionary”?

1 Like
#3

Bigger dictionary leads to increasing amount of the possible messages.
It’s hard to tell what’s wrong with your code without looking at it. I had the same problem when I wrongly processed the situation when I found several words on the one step.

#4

Yes, I know not being able to see the code means you can’t fix it for me but I’m just looking for any clues because I’m stumped. I initially didn’t catch how to handle multiple words with the same code correctly but that caused several other tests to fail, not just the very last “long code, large dictionary” (LCLD) test. That also made the result for the LCLD test way too small (by a factor of several hundred rather than ~27 as it is now).

In examining the LCLD test in the dev (#4) my code indicates that there are only two codes that represent 3 words (there are many that represent 2) and neither of those two code for 3 words appear in any messages (nor anywhere else in the code).

multicode #1: .--.-...---..-    [WLEOU, PTVMU, PTSOU]
multicode #2: ..---..-.--....   [IMXADI, ITGRZI, UZNMH]

I’ve made my own test case to ensure that the 3 and larger codes would work but more than 2 isn’t different than more 1 since I just have a count (actually the list of the words for debug/display purposes) which I multiply and then accumulate.

#5

Okay, adding more debug messages got me there. Some of the multiply-accumulate steps were overflowing int. Switching to long for those calculations does the trick. Probably should have switched to long as soon as I saw large totals (such as an expected answer of 57.3 billion).

1 Like
#6

This is the simplest task in the “Very hard” group. :sunny:

8 Likes
#7

Damn, implemented and reimplemented… still getting 127401984 instead of 57330892800.

Exactly a factor of 450!

Smaller tests would help, instead of having very small, then very big examples.

[solved] Forgot the damn multiplication (multiple words giving the same morse code)

4 Likes
#8

Does anyone have any more test cases? My code is failing a few tests during submission (including the test4 from the IDE) but it is very hard to pinpoint exactly what’s wrong because the first 3 tests in IDE are trivial.

During submission, my code fails:

  • Many possibilities, with small sequence and small dictionnary
  • Small sequence, large dictionary
  • Long sequence, large dictionary

but passes everything else, including

  • Dictionnary contains differents words for a same code
  • Long sequence, small dictionary

Thanks
dimaj

3 Likes
#9

Wow, this one was tough :slight_smile: I had to recode everything from scratch 3 or 4 times before getting a solution that passes the tests. My final solution is based on a network algorithm combined with memoization – given the complexity of the problem, I was very surprised that it was possible to find such a fast solution.

For the very hard problems, it would be very interesting to see the list of people who were successful, in which languages, and the code efficiency (for instance the validation time).

4 Likes
#10

I came up with a strange solution that passes all tests in the IDE (I do get the expected answer of 57 billions) yet only gets 63%!

I fail at:

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

But I pass things like:

  • No possible message
  • Small sequence, large dictionary
  • Long sequence, large dictionary

Things I tried:
everything to uppercase, word appearing multiple times in dictionnary

Any idea of what I should be careful of and what the IDE doesn’t test that the server does?

#11

Nevermind, I found out the issue. it was me being silly - I used the same variable name as a previous PHP reference which caused my index tree of valid words to lose the validity of the last word in the dictionnary whenever i reasigned something to that variable. Derp
100% now :slight_smile:

1 Like
#12

There is a small error in the default stub code in Python on this case.
ValueError: invalid literal for int() with base 10: ‘-.-’

It’s really no big deal, but wanted the dev team to know about that.

#13

Did you solved your problem?

My code fails test4 from the IDE (output is 16307453952) and the pair of test with large dictionary during submission.

Any clue will be helpful

#14

Finally I solved all the cases. My pillow was right: don’t try to solve anything when you are sleepy.

2 Likes
#16

This one was very easy. I’ve achieved 100% in less than 1h. But, strangely, I didn’t unlocked any achievement. Even with my first try, I only got 67%, and didn’t unlock the 50% achievement.

Edit: It’s ok, I now have both achievements. It just took half an hour to unlock.

#17

I had to rewrite my solution from scratch once because it was way too slow for the last test. I even wondered if the challenge was actually possible in JavaScript, given the solution (57330892800 !)

In the end my second algorithm took between 50 & 70ms :sunny:

2 Likes
#18

Started with a graph of letters/graph of words exponential approach using recursions and timed out on 1 word. Thought of a more direct recursion exponential way and got half the validation before starting to timeout. Figured out a polynomial dynamic programming approach and got all except the long sequences. Figured out an optimization (no need to check for words longer than the longest word) and got 100% in 100ms. Nice puzzle <3.

#19

I have succeeded with the 4 tests in the IDE but when submitting, i get only 80% and i fail on “one single message possible” and “long sequence, large dictionnary”.
I have no wat to know what’s wrong with them, is it a performance problem ? Wrong result ? How can we know ?

#20

Failing one single message possible sounds like you have a bug which might be hard to find since you’re passing 100% IDE. Failing the last test might be linked to that bug. Or it could be performance. I would check my timings on the last IDE test to see how close I am to the limit.

#21

The last step takes 500ms, what’s the limit, it’s not specified in the instructions ?