<p>This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up.</p>

<p>Anyway, the game is as such: my friend John has a sequence of letters that are mapped to a sequence of numbers (the letters are unique but the numbers are not necessarily unique). John now hides the letters from the sequence and sends me only the numbers in the same order as the sequence. My job is to guess the letters of this sequence. The only information available to me is a database that contains all letters of the alphabet and a rough numerical mapping.</p>

<p>So, for example, John computes the following:</p>

<p>(a : 5, b : 10, c : 1, e : 15, f : 4)</p>

<p>Then john sends me (5, 10, 1, 15, 4). I now have to guess which letters those numbers belong to. As I said above, I have some rough estimate of what number each letter in my database should be mapped to.</p>

<p>This problem is not hard with this domain. The Hungarian algorithm for lowest cost assignment would work fine. However, what about arbitrarily large string sizes? Suppose I have a gigantic database of strings (ranging from a few letters all the way to 20 letters) to number mappings. The database is ordered lexographically. John chooses a subset of this database, changes the numbers of each entry a certain amount (different for all) and then asks me to guess that sequence.</p>

<p>Any leads?</p>

CC BY-SA 3.0
2016-02-09T02:12:09.403Z
1. I don't understand the last paragraph.  Can you edit?  Previously you talked about sequences but now you're talking about strings.  Is the database a database of strings, or a database of strings to number mappings?  What *is* a string-to-number mapping?  What is an entry in the database?  Are there numbers in the database?  What does it mean to change each number a certain amount -- can you be more precise?  What sequence are you supposed to guess?  I'm so lost.  Can you try to formalize that problem more carefully?  2. It's not clear how the Hungarian algorithm solves the initial problem.
D.W.
CC BY-SA 3.0
2016-02-15T18:23:15.860Z
This doesn't seem to have anything to do with linear algebra.  Deobfuscated, the question seems to ask: fix a dictionary $\{a_i \mid i \in I\}$, given a set $\{f(a_i)+\delta_i \mid i \in J\}$ of salted hashes, reconstruct $J$.  In other words, find out which words in the dictionary appear as passwords in a hashed password file.
András Salamon
<ds.algorithms><co.combinatorics>
Matching of points in two discrete linear sequences with potentially missing points
wyas
# Matching of points in two discrete linear sequences with potentially missing points

(Asked by: username_0 on 2016-02-07)

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up.

Anyway, the game is as such: my friend John has a sequence of letters that are mapped to a sequence of numbers (the letters are unique but the numbers are not necessarily unique). John now hides the letters from the sequence and sends me only the numbers in the same order as the sequence. My job is to guess the letters of this sequence. The only information available to me is a database that contains all letters of the alphabet and a rough numerical mapping.

So, for example, John computes the following:

(a : 5, b : 10, c : 1, e : 15, f : 4)

Then john sends me (5, 10, 1, 15, 4). I now have to guess which letters those numbers belong to. As I said above, I have some rough estimate of what number each letter in my database should be mapped to.

This problem is not hard with this domain. The Hungarian algorithm for lowest cost assignment would work fine. However, what about arbitrarily large string sizes? Suppose I have a gigantic database of strings (ranging from a few letters all the way to 20 letters) to number mappings. The database is ordered lexographically. John chooses a subset of this database, changes the numbers of each entry a certain amount (different for all) and then asks me to guess that sequence.

Any leads?

**Tags:** ds.algorithms, co.combinatorics

> **Comments:**
> **username_1**: 1. I don't understand the last paragraph.  Can you edit?  Previously you talked about sequences but now you're talking about strings.  Is the database a database of strings, or a database of strings to number mappings?  What *is* a string-to-number mapping?  What is an entry in the database?  Are there numbers in the database?  What does it mean to change each number a certain amount -- can you be more precise?  What sequence are you supposed to guess?  I'm so lost.  Can you try to formalize that problem more carefully?  2. It's not clear how the Hungarian algorithm solves the initial problem.  
> **username_2**: This doesn't seem to have anything to do with linear algebra.  Deobfuscated, the question seems to ask: fix a dictionary $\{a_i \mid i \in I\}$, given a set $\{f(a_i)+\delta_i \mid i \in J\}$ of salted hashes, reconstruct $J$.  In other words, find out which words in the dictionary appear as passwords in a hashed password file.  

---

## 0 answers

