14
\$\begingroup\$

Given an input of a list of words and their abbreviations, output the pattern by which the abbreviations can be formed.

Let us take the example input of

potato ptao
puzzle pzze

as an example (that is, the abbreviation for potato is ptao, and the abbreviation for puzzle is pzze).

Consider all possible ways to obtain ptao from potato. One possible way is to take the first, third, fourth, and sixth letters, which we will refer to as 1346. But since t and o appear multiple times in the word, there are multiple other possible ways to generate ptao from potato: 1546, 1342, and 1542.

Similarly, note that pzze can be generated from puzzle with any of 1336, 1346, 1436, 1446. The only pattern that these two abbreviations have in common is 1346; therefore, that must be the output for this input. If multiple possible patterns are possible, you may output any, some, or all of them (at least one).

You may assume that:

  • Input words and abbreviations contain only lowercase letter.

  • There is at least one word/abbreviation pair in the input.

  • It is possible for every abbreviation to be formed from its corresponding word.

  • There will always be at least one pattern that forms every abbreviation.

  • The maximum length of each word is 9 characters.

Input may be taken as any of the following:

  • 2-dimensional array/list/array of tuples/etc. [[word, abbr], [word, abbr], ...]

  • flat 1-dimensional array/list [word, abbr, word, abbr, ...]

  • single string, delimited by any single character that is not a lowercase letter "word abbr word abbr"

  • hash/associative array/etc. {word => abbr, word => abbr, ...}

In any of these input options, you are also permitted to swap the order of word/abbr (please fully describe the input format in your post).

Output may be given as a single number, a string delimited by non-digits, or an array/list/tuple/etc. of numbers.

Since this is , the shortest code in bytes will win.

Test cases (remember that you only need to output ≥1 results if multiple patterns work):

In                                Out
--------------------------------------------------------
potato ptao puzzle pzze         | 1346
aabbcc abc fddeef def           | 246
prgrmming prgmg puzzles pzzlz   | 14353
aaaaa a bbbb b ccc c dd d e e   | 1
aaaaa a bbbb b ccc c            | 1, 2, 3
abcxyz zbcyax                   | 623514
abcxyz acbbacbcbacbbac          | 132213232132213
potato ptao                     | 1346, 1546, 1342, 1542
a aaaaa                         | 11111
\$\endgroup\$
  • \$\begingroup\$ Just to make sure I understand, the abbreviation process can reorder letters? \$\endgroup\$ – xnor Mar 4 '16 at 1:05
  • \$\begingroup\$ @xnor Correct, as seen in several of the test cases. \$\endgroup\$ – Doorknob Mar 4 '16 at 1:12
  • \$\begingroup\$ Can the 2D array have the other orientation? Each column, not each row, would contain a pair of word/abbrev \$\endgroup\$ – Luis Mendo Mar 4 '16 at 1:22
  • \$\begingroup\$ @DonMuesli No, it cannot. \$\endgroup\$ – Doorknob Mar 4 '16 at 1:33
  • \$\begingroup\$ Can we use zero-indexing, so print 0235 instead of 1346? \$\endgroup\$ – Denker Mar 4 '16 at 8:22
3
\$\begingroup\$

Pyth, 19 bytes

mhh@Fd.TmmxkmbhdedQ

Try it here!

Takes a list in the following format:

[["word","abbr"],["word","abbr"],...]

Alternative 17 bytes solution which outputs the result as list of zero-based indices which are wrapped in an 1-element list:

m@Fd.TmmxkmbhdedQ

Explanation

Example: [["potato", "ptao"],["puzzle", "pzze"]]

First we map every char in the abbrevation to a list of the indices of all occurences in the word which yields

[[[0], [2, 4], [3], [1, 5]], [[0], [2, 3], [2, 3], [5]]]

Then we transpose this list which gives us

[[[0], [0]], [[2, 4], [2, 3]], [[3], [2, 3]], [[1, 5], [5]]]

So the indices of each char of each abbrevation are together in one list.

Then we just have to find one common index in all of those lists which yields:

[[0], [2], [3], [5]]

This is the output of my alternative 17 byte solution above. This then gets transformed into [1,3,4,6].

Code breakdown

mhh@Fd.TmmxkmbhdedQ   # Q = input

m                 Q   # map input with d
        m       ed    # map each abbrevation with k
            mbhd      # map word to char list
         mxk          # map each abbrevation char to a list of indices
      .T              # Transpose
    Fd                # Fold every element
   @                  # and filter on presence
 hh                   # Take first element of the result und and increment it
\$\endgroup\$
  • \$\begingroup\$ Couldn't you also delete the dm right before the @? \$\endgroup\$ – Doorknob Mar 4 '16 at 13:11
  • \$\begingroup\$ @Doorknob I can. Thanks for spotting that! \$\endgroup\$ – Denker Mar 4 '16 at 14:07
3
\$\begingroup\$

MATL, 29 bytes

!"@Y:!=2#fX:wX:h]N$v1XQtv4#X>

Input is a 2D array in the following format:

{'potato' 'ptao'; 'puzzle' 'pzze'}

Try it online! (the linked code includes some modifications owing to changes in the language since this answer was posted)

!       % take input. Transpose
"       % for each column
  @Y:   %   push column. Unpack the two strings and push them onto the stack
  !     %   transpose second string
  =     %   matrix with all pairwise matchings of characters in word and abbreviation
  2#f   %   find row and col indices of those matchings
  X:    %   transform into column vector
  wX:   %   swap, transform into column vector
  h     %   concat into a two-col matrix
]       % end for
N$v     % concatenate all matrices containing the indices
1       % push 1
XQ      % build matrix adding 1 for each (row,col) index
tv      % concat vertically with itself, so that it has at least two rows.
        % This forces the following function to work on each col.
4#X>    % arg max of each col: position that produces a match in all pairs.
        % If there are several maximizers in each col this gives the first

The code required some involved (and lengthy!) tricks to

  • Prevent the orientation of vectors produced by find (f) from changing depending on input shape. These are statements X:wX:: force both outputs to be column vectors.
  • Counteract the "work along first non-singleton dimension" default behaviour of the min (X>) function. These are statements tv: concat a copy of itself to assure at least two rows);
\$\endgroup\$
2
\$\begingroup\$

Perl, 46 45 42 bytes

Includes +1 for -p

Give input as sequential words on STDIN, e.g.

perl -p abbrev.pl
prgrmming
prgmg
puzzles
pzzlz

Terminate STDIN with ^D or ^Z or whatever is needed on your system

abbrev.pl:

s#.#${${--$_.$.%2}.=$&}||=-$_#eg;$_ x=eof

Explanation

Consider this input (conceptual layout, not the real way to input for this program):

potatoes     ptao
puzzle       pzze

The program build strings representing the vertical columns of the full strings indexed on a column id

id1    pp     -> 1
id2    ou     -> 2
id3    tz     -> 3
id4    az     -> 4
...

etc. It also does the same for the abbreviations, but using a different id

ID1    pp     -> 1
ID2    tz     -> 3
ID3    az     -> 4
ID4    oe     -> 6

The words are implicitely processed one by one by using the -p option. The columns strings are constructed using repeated concatenations while each word is walked using s#.# ...code.. #eg, so each column needs a repeatable id. I use minus the column number followed by the line number modulo 2. The column number can be constructed using --$_ which starts out as the current word which due to the use of only a-z is guaranteed to evaluate as 0 in a numeric context. So I get -1, -2, -3, .... I'd really would have liked to use 1, 2, 3, ..., but using $_++ would trigger perl magic string increment instead of a normal numeric counter. I do want to use $_ and not some other variable because any other variable I would have to initialize to zero in every loop which takes too many bytes.

The line number modulo 2 is to make sure the ids for the full word and the ids for the abbreviation don't clash. Notice that I cannot use the full word and the abbreviation on one string to have a column number going over the combined string because the full words don't all have the same length, so the abbeviated word columns wouldn't line up. I also can't put the abbreviated word first (they all have the same length) because I need the count of the first column of the full words to be 1.

I abuse the perl global name space through a non strict reference to construct the column strings as:

${--$_.$.%2}.=$&

Next I map each column string to the first column number that string ever appears in (the mapping already indicated above) by again abusing the perl global namespace (but notice that the names cannot clash so the globals don't interfere with each other):

${${--$_.$.%2}.=$&} ||= -$_

I have to negate $_ because like I explained above I count the columns as -1, -2, -3, .... The ||= make sure only the first appearance of a given column gets a new column number, otherwise the previous column number is preserved and returned as value. This will happen in particular for every abbreviated word since the specification guarantees that there is a column in the full words that will have appeared beforehand. So in the very last abbreviated word each letter will be replaced by the column number in the full word that corresponds with the column for all abbreviated words. So the result of the very last substitution is the final result that is wanted. So print if and only if we are at the end of the input:

$_ x=eof

The column index assignment will also create entries for incomplete columns because the column is not completely constructed yet or some words are shorter and don't reach the full column length. This is not a problem since the columns needed in every abbreviated word are guaranteed to have a corrsponding column from the full words which has the maximum possible length (the number of currently seen pairs) so these extra entries never cause false matches.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 74 bytes

import Data.List
foldl1 intersect.map(\(w,a)->mapM(`elemIndices`(' ':w))a)

Input format is a list of pairs of strings, e.g.:

*Main > foldl1 intersect.map(\(w,a)->mapM(`elemIndices`(' ':w))a)  $ [("potato","ptao"),("puzzle","pzze")]
[[1,3,4,6]]

How it works: mapM (same as sequence . map) first turns every pair (w,a) into a list of lists of indices of the letters in the abbreviation (' ': fixes Haskell's native 0-based index to 1-based), e.g. ("potato", "ptao") -> [[1],[3,5],[4],[2,6]] and then into a list of all combinations thereof where the element at position i is drawn from the ith sublist, e.g. [[1,3,4,2],[1,3,4,6],[1,5,4,2],[1,5,4,6]]. foldl1 intersect finds the intersection of all such lists of lists.

\$\endgroup\$
0
\$\begingroup\$

ES6, 92 bytes

(w,a)=>[...a[0]].map((_,i)=>[...w[0]].reduce((r,_,j)=>w.some((s,k)=>s[j]!=a[k][i])?r:++j,0))

Accepts input as an array of words and an array of abbreviations. Returns an array of 1-based indices (which costs me 2 bytes dammit). In the case of multiple solutions, the highest indices are returned.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 210 bytes

Not an impressive answer seing the topscores here, but this is truly some of the craziest list comprehension I've ever done with Python. The approach is quite straigthforward.

 def r(p):
    z=[[[1+t[0]for t in i[0]if l==t[1]]for l in i[1]]for i in[[list(enumerate(w[0])),w[1]]for w in p]]
    return[list(set.intersection(set(e),*[set(i[z[0].index(e)])for i in z[1:]]))[0]for e in z[0]]

The function expects input always as a string 2-D array like: [[word, abbr],...] and returns a list of integers.

Ps: A detailed explanation coming soon

Ps2: Further golfing suggestions are welcomed!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.