4 Replies - 817 Views - Last Post: 08 July 2021 - 12:56 PM Rate Topic: -----

#1 java_exp   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 20-June 21

Guess a word if number of character matches are given

Posted 20 June 2021 - 10:51 PM

You need to guess a word. You are provided with a list of Words with the number of character matches at the right position.

Example

input {{"MOXTE",3} , {"AXCDG",0},{"MOQRT",2},{"FOUSE",4},{"POWER",1}}

return "MOUSE"
Explanation:

MOXTE    MO##E    3 matches
AXCDG    #####    0 matches
MOQRT    MO###    2 matches
FOUSE    #OUSE    4 matches
POWER    #O###    1 match

Result:  MOUSE




I tried using brute force. Max heap is not working. Any leads?

Is This A Good Question/Topic? 0
  • +

Replies To: Guess a word if number of character matches are given

#2 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 16302
  • View blog
  • Posts: 64,852
  • Joined: 12-June 08

Re: Guess a word if number of character matches are given

Posted 20 June 2021 - 11:14 PM

What do you mean you 'tried using brute force'? In what way?
Was This Post Helpful? 0
  • +
  • -

#3 java_exp   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 20-June 21

Re: Guess a word if number of character matches are given

Posted 20 June 2021 - 11:21 PM

Comparing each and every word and letter and finding the best fit.
Was This Post Helpful? 0
  • +
  • -

#4 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 870
  • View blog
  • Posts: 6,679
  • Joined: 25-December 13

Re: Guess a word if number of character matches are given

Posted 21 June 2021 - 04:31 AM

Can you post the steps in your algorithm?
Was This Post Helpful? 0
  • +
  • -

#5 Piet Souris   User is offline

  • D.I.C Head

Reputation: 44
  • View blog
  • Posts: 201
  • Joined: 01-December 15

Re: Guess a word if number of character matches are given

Posted 08 July 2021 - 12:56 PM

There are 26 ^ 5 possible strings, which is quite large, although doable brute force.

A way to reduce that number considerably is to check all the given words that have one or more correct letters. For instance: the word "FOUSE" has 4 characters correct. Now, that means that the soliution can have an F in position 0, an O at position 1, et cetera. You could thus make a Map<position, Set<possible characters>>.
Then, correct this map for the words that have no correct letters. For instance, "AXCDG": we know that the solution does not have an A at position 0, et cetera.

We end up with this map:

0, [F, M, P]
1, [O]
2, [Q, U, W, X]
3, [E, R, S, T]
4, [E, R, T]

If we then take the cartesian product of the values, we end up with 144 possible solutions, and only MOUSE fits the bill.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1