Retrieving a key from a dictionary using its value

Is there a way?

Can I find the dictionary's key if I know the value?

(If so, I'm sure it's simple, and I apologize in advance for asking.)


(filler for getting my edited post, updated/posted)
(again, filler for getting my edited post, updated/posted)


It only goes one way:

key (input) ---> value (output)

but-so, all you got to do, is to add a reversed key-value pair to the dictionary:

an example

HK edited, version 2: (let me know if it still got errors)

<game name="example_game">

  <attr name="start" type="script">
    invoke (month_object.month_script_attribute)
  </attr>

</game>

<object name="month_object">

  <attr name="month_script_attribute" type="script">
    show menu ("choose selection method", month_object.month_scriptdictionary_attribute, false) {
      invoke (ScriptDictionaryItem (month_object.month_scriptdictionary_attribute, result))
    }
  </attr>

  <month_scriptdictionary_attribute type="scriptdictionary">

    <item key="string_to_integer">
      show menu ("Month?", month_object.month_stringlist_attribute, false) {
        player.month_string_attribute = result
        player.month_integer_attribute = ToInt (StringDictionaryItem (month_object.month_stringdictionary_attribute, result))
      }
    </item>

    <item key="integer_to_string">
      msg ("Month? (1 to 12)")
      get input {
        if (IsInt (result)) {
          integer_variable = ToInt (result)
          if (integer_variable > 0 and integer_variable < 13) {
            player.month_integer_attribute = integer_variable
            player.month_string_attribute = StringDictionaryItem (month_object.month_stringdictionary_attribute, integer_variable)
          } else {
            invoke (ScriptDictionaryItem (month_object.month_scriptdictionary_attribute, "integer_to_string"))
          }
        } else {
          invoke (ScriptDictionaryItem (month_object.month_scriptdictionary_attribute, "integer_to_string"))
        }
      }
    </item>

  </month_scriptdictionary_attribute>

  <attr name="month_stringlist_attribute" type="stringlist">

    <value>january</value>
    <value>february</value>
    <value>march</value>
    <value>april</value>
    <value>may</value>
    <value>june</value>
    <value>july</value>
    <value>august</value>
    <value>september</value>
    <value>october</value>
    <value>november</value>
    <value>december</value>

  </attr>

  <month_stringdictionary_attribute" type="stringdictionary">

    <!--
    'string to integer (important: the 'integer' returned output is still a string value, so you'll have to convert it, via 'ToInt (RETURNED_OUTPUT)', into integers if you want/need them as integers, my code example does/shows this for you)' items
    -->

    <item>
      <key>january</key>
      <value>1</value>
    </item>

    <item>
      <key>february</key>
      <value>2</value>
    </item>

    <item>
      <key>march</key>
      <value>3</value>
    </item>

    <item>
      <key>april</key>
      <value>4</value>
    </item>

    <item>
      <key>may</key>
      <value>5</value>
    </item>

    <item>
      <key>june</key>
      <value>6</value>
    </item>

    <item>
      <key>july</key>
      <value>7</value>
    </item>

    <item>
      <key>august</key>
      <value>8</value>
    </item>

    <item>
      <key>september</key>
      <value>9</value>
    </item>

    <item>
      <key>october</key>
      <value>10</value>
    </item>

    <item>
      <key>november</key>
      <value>11</value>
    </item>

    <item>
      <key>december</key>
      <value>12</value>
    </item>

    <!--
    'integer to string' items
    -->

    <item>
      <key>1</key>
      <value>january</value>
    </item>

    <item>
      <key>2</key>
      <value>february</value>
    </item>

    <item>
      <key>3</key>
      <value>march</value>
    </item>

    <item>
      <key>4</key>
      <value>april</value>
    </item>

    <item>
      <key>5</key>
      <value>may</value>
    </item>

    <item>
      <key>6</key>
      <value>june</value>
    </item>

    <item>
      <key>7</key>
      <value>july</value>
    </item>

    <item>
      <key>8</key>
      <value>august</value>
    </item>

    <item>
      <key>9</key>
      <value>september</value>
    </item>

    <item>
      <key>10</key>
      <value>october</value>
    </item>

    <item>
      <key>11</key>
      <value>november</value>
    </item>

    <item>
      <key>12</key>
      <value>december</value>
    </item>

  </month_stringdictionary_attribute>

</object>

a more fancy/cool application (Pixie's genius/credit) is to use this for handling magic/damage types for various magic/elemental types (weak: x2 or x1.5 damage: fire vs water, strong: x0.5 damage: fire vs fire, immunity: x0 damage: fire vs fire, reflection: fire vs fire, absorption:fire vs fire), if interested I can craft the code and explain it


<function name="FindKey" parameters="dict, value">
  foreach (key, dict) {
    if (DictionaryItem(dict, key) = value) {
      return (key)
    }
  }
</function>

Not too efficient, but it works.


awesome... never thought (nor be able to realize how) to make it into a (dynamic) Script/Function... really cool code, thank you, mrangel!


Saw this and thought "Wow, you can do that?"

show menu ("choose selection method", month_object.month_scriptdictionary_attribute, false) {
  do (month_object, "month_scriptdictionary_attribute", result)
}

Tried it. Nope; do definitely doesn't work with a scriptdictionary and a key. Thought that would be an odd thing to be omitted from the manual.
Would be nice if it could; but then it's not hard to make a function that does that. I was just surprised to see someone apparently doing in one line what I'd taken a fair amount of time polishing.


mrangel,

I thought of doing that with foreach...

Right now I've just got two dictionaries. (I thought that would be easier on the game than running a foreach loop.)


Here's how I use ShowMenu with Script Dictionary to run the script:

<!--Saved by Quest 5.7.6404.15496-->
<asl version="550">
  <include ref="English.aslx" />
  <include ref="Core.aslx" />
  <game name="show menu script">
    <gameid>8a565181-e882-4c68-8253-69e84fcce2ed</gameid>
    <version>1.0</version>
    <firstpublished>2017</firstpublished>
    <scriptDic type="scriptdictionary">
      <item key="one">
        JS.alert ("You chose scriptDic one.")
      </item>
      <item key="two">
        msg ("You ran scriptDic two.")
      </item>
    </scriptDic>
  </game>
  <object name="room">
    <inherit name="editor_room" />
    <enter type="script">
    </enter>
    <description>Enter {command:TEST}</description>
    <object name="player">
      <inherit name="editor_object" />
      <inherit name="editor_player" />
    </object>
  </object>
  <command name="test">
    <pattern>test</pattern>
    <script>
      ShowMenu ("Dictionary choices: ", game.scriptDic, true) {
        invoke (ScriptDictionaryItem(game.scriptDic, result))
      }
    </script>
  </command>
</asl>

For a string dictionary, I just msg (result)


Returning a string:

firsttime {
  game.stringDic = NewStringDictionary()
  i = 0
  while (i<4) {
    i = i + 1
    a = ToWords(i)
    dictionary add (game.stringDic, "You chose "+a+".", a)
  }
}
ShowMenu ("Dictionary choices: ", game.stringDic, true) {
  msg (result)
}

@ mrangel:

it can be done, I just need to check-on/fix some of the code syntax (since it's having errors, doh!)

(will edit my previous post with the code, so try it again, and hopefully it'll be syntax-error/error free now, lol)

for all Attribute Types except Dictionaries (not sure if String/Object Dictionaries work or not), you can use the 'attr' syntax, but not with dictionaries (not sure if String/Object Dictionaries work or not), I keep forgetting about it, as I like using the 'attr' syntax, lol. I changed all of the dictionaries to the non-attr syntax, just to be safe.

the 'show menu' should take the 'keys' of a dictionary for it's menu choices, just like as if it were a list, at least I think it does for string dictionaries, but maybe not for Object/Script dictionaries.

I used 'invoke' instead of 'do', as with do's syntax/signature, it does seem like it can't work with script dictionaries, only scripts.

usually using 'do' is better as you can concatenate with it and it works with most Attribute Types, though 'invoke' is quick/easy for scripts and script dictionaries (need to use the 'ScriptDictionaryItem' to get a returned script for 'invoke' to use), though both 'invoke' and 'do' can be passed arguments/parameters, as well:

http://docs.textadventures.co.uk/quest/scripts/do.html
http://docs.textadventures.co.uk/quest/scripts/invoke.html

let me know if there's still errors with using my code, as it's likely just some stupid typos or syntax errors... it does work... it can be done... just need to get my code correct, lol.


HK

Look - >

http://textadventures.co.uk/forum/quest/topic/tt4jutugqkgljdcdbrcm_a/retrieving-a-key-from-a-dictionary-using-its-value#7a5b2241-0628-491d-82b0-d6afb3cd6ebd

http://textadventures.co.uk/forum/quest/topic/tt4jutugqkgljdcdbrcm_a/retrieving-a-key-from-a-dictionary-using-its-value#c970d81a-20ba-4fbd-b74c-ee90f6060cb3


Sorry, I shouldn't have said anything.


You can do this, too:

game.scriptDictTemp = NewScriptDictionary()
functOne => {
  msg ("This is function one!")
}
dictionary add (game.scriptDictTemp, "one", functOne)
functTwo => {
  msg ("This is function two!")
}
dictionary add (game.scriptDictTemp, "two", functTwo)
create ("dictObjTemp")
ShowMenu ("Dictionary choices: ", game.scriptDictTemp, true) {
  dictObjTemp.thisScript = ScriptDictionaryItem(game.scriptDictTemp, result)
  do (dictObjTemp, "thisScript")
  destroy ("dictObjTemp")
}

EDIT

I don't know what I had messed up, but this works:

x = FindKey(game.stringDic, "four")
msg ("The key is "+x)
ShowMenu ("Dictionary choices: ", game.stringDic, true) {
  msg (result)
}
  <function name="FindKey" parameters="dict, value" type="string">
    foreach (key, dict) {
      if (StringDictionaryItem(dict, key) = value) {
        return (key)
      }
    }
  </function>
    <start type="script"><![CDATA[
      game.stringDic = NewStringDictionary()
      i = 0
      while (i<4) {
        i = i + 1
        a = ToWords(i)
        dictionary add (game.stringDic, "You chose "+a, a)
      }
    ]]></start>

Why sorry, mrangel?

I'm having all kinds of fun with this stuff!

...and I'm fairly certain that HK is, as well.

...and I like your function better than having a reversed dictionary.

A foreach can't have that much more effect on Quest's resources than retrieving a value from a dictionary; can it?


in terms of speed (likely not actual significant difference however), having dictionaries (with reversed items), is better: no/few operations vs operations involved with using the 'findkey' method

in terms of memory/resources, the 'findkey' method is better, as you don't have to have 'quantity of dictionaries x2:reversed items'

in terms of human (time/effort/typing), using the 'findkey' is superior, as you don't have to have 'quantity of dictionaries x2:reversed items'


thus, using 'findkey' method is better, and it's actually very efficient (iterating through lists/arrays is very fast in terms of computer hardware, as all device's memory is a list/array), especially in terms of human involvement, saves so much time/effort/typing!


I would suggest returning null or throwing an error if nothing is found. It is going to happen at some point, and will be easier to debug if you have it handle it itself.

<function name="FindKey" parameters="dict, value">
  foreach (key, dict) {
    if (DictionaryItem(dict, key) = value) {
      return (key)
    }
  }
  return(null)
</function>

<function name="FindKey" parameters="dict, value">
  foreach (key, dict) {
    if (DictionaryItem(dict, key) = value) {
      return (key)
    }
  }
  error("Value not found in dictionary: " + value)
</function>

in terms of speed (likely not actual significant difference however), having dictionaries (with reversed items), is better

Incorrect. Looking up the key iterates over (on average) half the dictionary. Building the reverse dictionary has to iterate over the whole thing. If you change the dictionary more often than you have to do a reverse lookup, it's faster to scan it each time. Benchmarking on Perl says a lookup function is faster for cases where you have less than √2 lookups per change. This roughly matches up with what I'd expect.

In Quest, not sure where the dividing line would be. I suspect it would be higher, because iterating over a dictionary gives you the keys in the same order they were added. Unless there's some really neat black magic going on, I suspect this means the dictionary add and remove functions will be really, really slow.

(Not slow enough to make a difference in a real game, but comparatively slower than my benchmarks would imply)


So, DictionaryItem basically performs a foreach of its own, but returns out of the script when it finds a match?


Also, check this out:

DictFun.aslx

http://textadventures.co.uk/games/view/j5w1ex6puksylzddbdihwq/dictfun

I was having WAY too much fun with dictionaries.

(I have to improve my dictionary-pimping skills so I can go back to the poker hand thing. (I just now realized mrangel had two dictionaries going on, and that's why my stuff wasn't working. (KV sighs and shrugs.) I'm old.)


Most of the stuff is more easily accomplished using a single list (I've seen it with my own eyes, using the same values), but this was a good learning experience for me.

Speaking of that:

Thanks, mrangel, HK, and Pixie, and everyone else, for teaching me what I know at this point!!!

You all are awesome!


So, DictionaryItem basically performs a foreach of its own, but returns out of the script when it finds a match?

There's a few ways it could be implemented. The way Perl does it is to store elements by hash of the key, and a list of key-value pairs within each hash bucket; in which case the efficiency of adding or retrieving an element is O(log n). But that method has the disadvantage that foreach retrieves the elements in (what looks like) a random order. It's a compromise between memory, speed, and convenience.

If the dictionary is stored internally as a list of key-value pairs, then dictionary add would have to scan over the whole dictionary to make sure the value doesn't exist, so retrieval and insertion are both O(n). So if your dictionary isn't premade, building the initial reverse dictionary would be O(n^2); while looping over the list checking keys manually will be O(n log n) I think.
Sorry, had a stressful day, laptop died, I'm not thinking so clearly. So could be completely wrong about everything.


I would guess Quest dictionaries use C# dictionaries under the hood, which use hash tables according to here.


thanks for the info mrangel, and for correcting me, as I'm still trying to understand this type of stuff, sighs, so the information and explanation by you is greatly helpful/appreciated, and again, my apologizes for assuming/stating incorrect things in my post(s).


retrieval and insertion are both O(n). So if your dictionary isn't premade, building the initial reverse dictionary would be O(n^2); while looping over the list checking keys manually will be O(n log n) I think.

That's where I get lost.

Guess:

O is the function?

(n) the amount of time it takes to perform the function?

(n^2) there are two loops (or iterations) in the function?

(n log n) uh... huh huh huh...


EDIT:

Does this lead me astray at any point?

If not, I think I get it.


I cheated when I made my last two dictionaries, by the way.

I made a list, then I wrote a function in the start script that turned that list into a string dictionary.

Then, I saved the game, opened the save with Notepad++, and copied the the dictionary, pasting it into the actual game.

Then, I changed the start script so it made a reverse dictionary, saved, copied and pasted that dictionary into the game.

(It took me longer to type that explanation than it did to make the dictionaries. Hehehe.)


the 'O' just means the format of the equation/formula, called 'Big O notation'

the rest is the formula/equation, depending on the speed and quantity of the operations

usually any coefficients are insignificant, so they're ignored (not shown in the Big O notation)

https://en.wikipedia.org/wiki/Big_O_notation

https://en.wikipedia.org/wiki/Analysis_of_algorithms

I'm still trying to learn algorithm analysis...


@ KV:

that looks like a good link for an intro to this type of stuff.


Log in to post a reply.

Support

Forums