38

I have following 2 div tags

<div class="one">
    +
   +++
    +
</div>

second div tag

<div class="two">
    + +   ++++  + ++  + + +
    + ++ +++ + +++ ++ + +++
    + ++ + + ++ + + + + ++ 
</div>

Now what I want to find if .one is exist in .two. Is it possible if yes how can we do it in javascript?

Update

I want to check the + pattern. I mean does

+ +++ +

exist in .two? The pattern has to be in that same order in .two.

@shub answer does not seem to be working. Here is JSFiddle of that answer.

Om3ga
  • 30,465
  • 43
  • 141
  • 221

13 Answers13

19

Part 1:

To see how the data would match, you may want to try turning this into letters, instead of pluses.

<div class="one">
    g
   tuv
    J
</div>

<div class="two">
    a b   cdef  g hi  j k l
    m no pqr s tuv wx y zAB
    C DE F G HI J K L M NO 
</div>

You'd have to do something like this:

Since: one.innerText = g \n tuv \n J

It would need to be turned into a regular expression like: /g|tuv|J/g

To see the cross matching, copy & paste the contents of class two into this site & delete the spacing before "a", "m" & "C": http://regexr.com/3eumc

Part 2

The problem is if "tuv" moves around in string 2, it wouldn't be locked with "g" above "u" above "J".

To fix that "g" above "u" above "J" problem, we'd have to think of this as a 2-dimensional dataset for a game board. That means turning the string into a matrix (array of arrays), where each letter plus each space gets dropped into an array slot. Like so:

var matrix = [
  // 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 = columns. Remember to add +10, +20!
    [a| |b| | | |c|d|e|f| | |g| |h|i| | |j| |k| |l], // row 0
    [m| |n|o| |p|q|r| |s| |t|u|v| |w|x| |y| |z|A|B], // row 1
    [C| |D|E| |F| |G| |H|I| |J| |K| |L| |M| |N|O]    // row 2
];

Now you can check to see if:

if ((matrix[0][13] === 'g') 
    && (matrix[1][12] === 't') && (matrix[1][13] === 'u') && (matrix[1][14] === 'v') 
    && (matrix[2][13] === 'J')) {
    /* SUCCESS when all 5 letters appear & "g" is above "u" & "u" is above "J".
    The entire cross can move left or right, but lines 1, 2 & 3 can't shift 
    independently of the other 3 lines. Otherwise it should fail.
    */
} else {
    // FAIL
}

Part 3...

I've solved this matrix search puzzle. See my jsFiddle at https://jsfiddle.net/briankueck/pern32vv/

Here is the core of how the code looks. Turn on the debugging switch at that jsFiddle link to see how it runs. :)

function getMatrix(cssSelector, canTrim) {
    // Built by, Clomp! @briankueck http://www.clomp.com
    var obj = $(cssSelector);
    if (obj) {
        var matrix = obj.text()

        /* Makes sure that we are selecting 3 lines, not 5 
         * as the example has a \n after <div ...>\n and before \n</div>
         */
        if (canTrim) {
            matrix = matrix.trim();
        }

        // Now split those 3 lines.
        matrix = matrix.split(/\n/);

        /* Trims each array in the matrix. Note: matrix[row] is a string, 
         * but we can treat a string as an array of characters.
         */
        if (canTrim) {
            // Trims each row, if desired.
            for (var row = 0; row < matrix.length; row++) {
                matrix[row] = matrix[row].trim();
            }
        } else {
            // Gets rid of spaces before matrix 1 in this demo.
            var maxLength = 0;
            var space = ' '; // You can also use a period here to see how it works.
            var tempMatrix = [];
            for (var row = 0; row < matrix.length; row++) {
                // This cuts the rows down (vertically) from 5 to 3.
                if (matrix[row].trim().length > 0) {
                    matrix[row] = matrix[row].replace(/\s/g, space);
                    matrix[row] = matrix[row].replace(/\t/g, space);
                    tempMatrix.push(matrix[row]);

                    if (matrix[row].length > maxLength) {
                        maxLength = matrix[row].length;
                    }
                }
            }

            /* This loops those 3 rows (horizontally) & slices the 1st character off 
             * each array if they are all identical & only contain spaces, which we are 
             * tracking with the period character '.' as dots.
             */
            var charactersToStrip = 0;
            for (var column = 0; column <= maxLength; column++) {
                for (var row = 0; row < tempMatrix.length; row++) {
                    if (tempMatrix[row][column] !== space) {
                        break;
                    } else if (row === (tempMatrix.length - 1)) {
                        charactersToStrip++;
                    }
                }
            }

            /* Strips characters, without removing the space before "g" 
             * and the space before "J".
             */
            for (var column = 0; column < charactersToStrip; column++) {
                for (var row = 0; row < tempMatrix.length; row++) {
                    tempMatrix[row] = tempMatrix[row].substring(1);
                }
            }
            matrix = tempMatrix;
        }
    }

    return matrix;
}

function matrixSearch(matrixOne, matrixTwo) {
    // Built by, Clomp! @briankueck http://www.clomp.com
    var space = ' '; // You can also use a period here to see how it works.

    // This is for " g". First we trim it, as we only want the "g" character.
    var searchChar = matrixOne[0].trim();

    // Next we find the lock position.
    var firstCharPosition = matrixTwo[0].indexOf(searchChar);

    var matchingRows = -1;
    if (firstCharPosition > -1) {

        // This should be 1 & not 0.
        var matchingCharInMatrixOne = matrixOne[0].indexOf(searchChar);

        // Now we can find the starting index of character 0 in each row of matrixTwo:
        var startIndex = firstCharPosition - matchingCharInMatrixOne;

        // This simultaneously scans rows 1, 2 & 3 in both matricies.
        var matchingRows = 0;
        for (var row = 0; row < matrixOne.length; row++) {
            /* We now know both the startIndex = 11 & the lock position = 12. 
             * So let's use them for "tuv" and " J".
             */
            var endIndex = startIndex + matrixOne[row].length;
            var i = -1;
            for (var column = startIndex; column < endIndex; column++) {
                i++;
                if (matrixOne[row][i] !== space) {
                    var matrixOneCharacter = matrixOne[row][i];
                    var matrixTwoCharacter = matrixTwo[row][column];
                    if (matrixOneCharacter !== matrixTwoCharacter) {
                        break;
                    } else if (column === (endIndex - 1)) {
                        // Found it!
                        matchingRows++;
                    }
                }
            }
        }
    }

    // Now we can find it:
    var isFoundInMatrixTwo = ((matchingRows > -1) 
        && (matchingRows === matrixTwo.length)) ? true : false;

    return isFoundInMatrixTwo;
}

var cssSelector1 = '.one';
var cssSelector2 = '.two';

var matrixOne = getMatrix(cssSelector1, false);
var matrixTwo = getMatrix(cssSelector2, true);

var isFound = matrixSearch(matrixOne, matrixTwo);
console.log('Is matrix 1 in matrix 2? ', isFound);

Enjoy!

Btw, Merry Christmas Stack Overflow community from Clomp!

Clomp
  • 3,168
  • 2
  • 23
  • 36
8

Well, we already have great answers here, but... here is one approach more. :)

Basically: filter input, get clean pattern/matrix (assumption is that there will be two spaces at the start - have to fix this!), test it against another pattern (actually - make HTML structure and arrays from both => compare them)

Visual representation of what's happening is there, too.

Code is attrocity, can and should be cleaned up (but it kinda works, lol):

spacer='-';

pattern=$('.one').text().replace(/ /g,spacer).split('\n');

patt=pattern.filter(function(val){
   if(val.indexOf('+')>=1) {
   
   
 return val;
   }
});
patt = patt.map(function(x){
   return x.slice(2);
});


var lgth = 0;
var longest;

for(var i=0; i < patt.length; i++){ // http://stackoverflow.com/questions/6521245/finding-longest-string-in-array 
    if(patt[i].length > lgth){
        var lgth = patt[i].length;
        longest = patt[i];
    }      
} 

 
//console.log(longest.length);
longest_sequence=longest.trim().length;

matrix=[];

for(j=0;j<patt.length;j++) {
//
if(patt[j]!=longest) {


cleaned=patt[j]+spacer.repeat(longest.length-patt[j].length);
cleaned=cleaned.substr(-longest_sequence);
}
else {
cleaned=longest.trim();
}
matrix.push(cleaned);
}
//console.log(matrix.join('\n'));


cells=[];
for(i=0;i<matrix.length;i++)  {


cells.push(matrix[i].split(''));
$('table.small').append('<tr>');
}

$( "table.small tr" ).each(function( index ) {
for(j=0;j<cells[index].length;j++) {
$(this).append('<td>'+cells[index][j]+'</td>');
 }
});



data=$('.two').text().replace(/ /g,spacer).split('\n');
data=data.filter(function(val){
   if(val.indexOf('+')>=1) {
   return val;
   }
});

data = data.map(function(x){
   return x.slice(2);
});

//console.log(data);
//console.log(data.join('\n'));

cells=[];
for(i=0;i<data.length;i++)  {


cells.push(data[i].split(''));
$('table.big').append('<tr>');
}

$( "table.big tr" ).each(function( index ) {
for(j=0;j<cells[index].length;j++) {
$(this).append('<td>'+cells[index][j]+'</td>');
 }
});

//comparing!!!
pattern_arr=[];
$("table.small tr").each(function() {
pattern_arr.push($(this).children().text().trim())
});
function arraysEqual(a1,a2) {
    /* WARNING: arrays must not contain {objects} or behavior may be undefined */
   // console.log(JSON.stringify(a1)+':'+JSON.stringify(a2));
   // console.log('________________________________________');
    return JSON.stringify(a1)==JSON.stringify(a2);
}

count=-1;
timer=setInterval(function(){ 
count++;
sliced_arr=[];
slices=[];
$( "table.big tr" ).each(function( index ) { 
$(this).children('td').removeClass('search');
sliced=$(this).children('td').slice( count,count+longest_sequence );
slices.push(sliced);
$(sliced).addClass('search');



sliced_arr.push($(sliced).text().trim());




if(arraysEqual(pattern_arr,sliced_arr)) {



//$(sliced).addClass('found').removeClass('search');

$.each( slices, function( key, value ) {
$(this).addClass('found').removeClass('search');
});
//$(slices).addClass('found').removeClass('search');

$('#status').text('Found!');





clearInterval(timer);
 }
 
for(i=0;i<sliced_arr.length;i++)
 if(sliced_arr[i]=="") {

  clearInterval(timer);

$('#status').text('Not found!');
 break;

 }



});
}, 1000);
.one, .two {
  font-size:22px;
}

table.big {
  border:1px solid #666;
padding:0;
  border-collapse:collapse;
}
table.big td {
  border:1px solid #666;
 
  padding:5px;
  margin:0;
}

table.small {
  border:1px solid red;
padding:0;
  border-collapse:collapse;
}
table.small td {
  border:1px solid red;
 
  padding:5px;
  margin:0;
}

.found {
  font-weight:bold;
  color:white;
  background:green;
}
.search {
  font-weight:bold;
  color:white;
  background:orange;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="one"><pre>
   +
  +++
   +
 </pre></div>
<table class="small">

</table>
<div class="two"><pre>
  + +   ++++  + ++  + + +
  + ++ +++ + +++ ++ + +++
  + ++ + + ++ + + + + ++ 
</pre></div>

<table class="big">

</table>
<div id="status">
</div>
sinisake
  • 11,240
  • 2
  • 19
  • 27
8

@2619's previous post shows interest for the Bliffoscope problem. Given that the text contents of div.one and div.two, in fixed-width font, ascii art style, are pictures pieced together from +, meaning an active pixel, and "" (space) inactive. The idea is to find in which position we could place div.one over div.two, so that the two patterns form more intersections. I'm only considering the intersection of the coordinates of the active pixels of two given images.

In this example, + is replaced by o to highlight the intersections of each match. A simplified version that uses canvas can be found here.

In the below SO snippet and in the JSFiddle demo, click the Next and Previous links, or press the arrow buttons of the keyboard, to navigate through the matches.

_main.best_positions() returns the number of intersections for every possible superposition, with any degree of tolerance for error, sorted by number of intersections (more matches first).

var PatternFinder;

PatternFinder = (function(win, doc, undefined) {
  'use strict';

  var _main = {

    selectors: {
      object_1_pattern: ".one",
      background_pattern: ".two",
      results: ".three",
      next_button: ".next",
      previous_button: ".previous",
      match_score: ".intersecting_coords",
      match_nr: ".match_nr",
    },
    cache: {
      object_text_string: '',
      context_text_string: ''
    },
    init: function() {

      _main.cache.object_text_string = $(_main.selectors.object_1_pattern).text();
      _main.cache.context_text_string = $(_main.selectors.background_pattern).text();

      // Parse our images from the text strings.
      _main.serialized_context = _main.serialize_map(_main.cache.context_text_string);
      _main.serialized_object = _main.serialize_map(_main.cache.object_text_string);

      // Find the position of the object with larger amount of intersecting coordinates
      _main.best_positions = _main.get_best_position(_main.serialized_context, _main.serialized_object);
      _main.current_result = _main.best_positions.length - 1;

      // Draw initial results
      _main.print_output(_main.current_result);

      // Handle user input
      $(_main.selectors.next_button).click(function() {
        _main.current_result -= 1;
        _main.print_output();
      });
      $(_main.selectors.previous_button).click(function() {
        _main.current_result += 1;
        _main.print_output();
      });
      // Keyboard: Arrow keys
      $(document).keydown(function(e) {
        switch (e.which) {
          case 37:
            { // left
              _main.current_result += 1;
              _main.print_output();
              break;
            }
          case 39:
            { // right
              _main.current_result -= 1;
              _main.print_output();
              break;
            }
          default:
            return;
        }
        e.preventDefault(); // prevent the default action (scroll / move caret)
      });
    },

    // Highlight an intersection.
    // Replace "+" by "o" in coords _x, _y.
    highlight_match: function(_x, _y, background) {
      var x = 0,
        y = 0,
        i = 0,
        output = "",
        c;
      for (i = 0; i < background.length; i += 1) {
        c = background[i];
        if (c == "+" && x == _x && y == _y) {
          output = output + "o";
        } else {
          output = output + c;
        }
        x += 1;
        if (c == "\n") {
          x = 0;
          y += 1;
        }
      }

      return output;
    },

    // Receive the translated serialized object,
    // and the original text string for the background.
    // Return the background text string, with the matches 
    // between it and serialized_object highlighted.
    merge_and_deserialize: function(serialized_object, background) {
      var i;
      for (i = serialized_object.length - 1; i >= 0; i--) {
        background = _main.highlight_match(serialized_object[i][0], serialized_object[i][1], background);
      }
      return background;
    },

    // Receive a text string like the one from the Stack Overflow ticket, 
    // return an array of coordinates of filled in pixels (+ or space).
    serialize_map: function(char_map) {
      var x = 0,
        y = 0,
        c,
        i,
        map = [];
      for (i = 0; i < char_map.length; i += 1) {
        c = char_map[i];
        if (c == "+") {
          map.push([x, y]);
        }
        x += 1;
        if (c == "\n") {
          x = 0;
          y += 1;
        }
      }
      return map;
    },

    // Find number of intersections between two images (that's where the magic happens).
    // Found here: https://gist.github.com/lovasoa/3361645
    array_intersect: function() {
      var a, d, b, e, h = [],
        l = [],
        f = {},
        g;
      g = arguments.length - 1;
      b = arguments[0].length;
      for (a = d = 0; a <= g; a += 1) {
        e = arguments[a].length, e < b && (d = a, b = e);
      }
      for (a = 0; a <= g; a += 1) {
        e = a === d ? 0 : a || d;
        b = arguments[e].length;
        for (l = 0; l < b; l += 1) {
          var k = arguments[e][l];
          f[k] === a - 1 ? a === g ? (h.push(k), f[k] = 0) : f[k] = a : 0 === a && (f[k] = 0);
        }
      }
      return h;
    },

    // Translate the coordinates of a serialized image.
    translate: function(coords, ix, iy) {
      return [coords[0] + ix, coords[1] + iy];
    },

    // Find in which position the object has more intersections with the background.
    get_best_position: function(context, object) {

      // Calculate image dimensions
      var context_width = context.sort(function(a, b) {
          return b[0] - a[0];
        })[0][0],
        context_height = context.sort(function(a, b) {
          return b[1] - a[1];
        })[0][1],
        object_width = object.sort(function(a, b) {
          return b[0] - a[0];
        })[0][0],
        object_height = object.sort(function(a, b) {
          return b[1] - a[1];
        })[0][1];
      // Swipe context, store amount of matches for each patch position.
      var similaritudes = [],
        cx, cy, intersection, translated_object;

      for (cx = -object_width; cx < context_width; cx += 1) {
        for (cy = -object_height; cy < context_height; cy += 1) {
          translated_object = object.map(function(coords) {
            return _main.translate(coords, cx, cy);
          });

          intersection = _main.array_intersect(context, translated_object);

          if (intersection.length > 0) {
            similaritudes.push({
              coords: [cx, cy],
              similaritudes: intersection.length
            });
          }

        }
      }
      // Return coords,
      // sorted by those for which number of matches was greater.
      return similaritudes.sort(function(a, b) {
        return a.similaritudes - b.similaritudes;
      });
    },

    print_output: function() {

      var positioned_object;

      // Get the coordinates of one of our matches.
      _main.current_result = Math.max(_main.current_result, 1);
      _main.current_result = Math.min(_main.current_result, _main.best_positions.length - 1);

      var score = _main.best_positions.slice(_main.current_result)[0].similaritudes;
      var best_position = _main.best_positions.slice(_main.current_result)[0].coords;

      // Translate our image patch to the position defined by _main.current_result.
      positioned_object = _main.serialized_object.map(function(coords) {
        return _main.translate(coords, best_position[0], best_position[1]);
      });

      // Produce merged images (background after replace).
      var final_image = _main.merge_and_deserialize(positioned_object, _main.cache.context_text_string);
      // Print image and information
      $(_main.selectors.results).text(final_image);
      $(_main.selectors.match_score).text(score);
      $(_main.selectors.match_nr).text(_main.best_positions.length - _main.current_result);
    }

  };

  // Expose methods
  _main.public_methods = {
    init: _main.init,
  };
  return _main.public_methods;

}(window, document));

PatternFinder.init();
.one,
.two {
  display: none;
}
.three {
  white-space: pre;
  font-family: "Lucida Console", Monaco, "Courier New", Courier, monospace;
  margin: 0 0 20px 0;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="one">
    +
   +++
    +
</div>
<div class="two">
    + +   ++++  + ++  + + +
    + ++ +++ + +++ ++ + +++
    + ++ + + ++ + + + + ++ 
</div>
<h3>Match: <span class="match_nr"></span></h3> 
<h5>Intersecting coordinates: <span class="intersecting_coords"></span></h5>
<div class="three"></div>
<nav>
<a class="previous" href="#">Previous</a>
<a class="next" href="#">Next</a>
</nav>
<p><sub>Click Next and Previous or use the keyboard arrows to see other possible matches.</sub></p>
Community
  • 1
  • 1
Ivan Chaer
  • 6,980
  • 1
  • 38
  • 48
3

The code snippet below finds all occurrences of the "one" pattern in the "two" div, as written in the markup. The results are reported in the console output (line index and position in line).

Credits :

  1. Clomp's comments helped me to understand that the question was about the markup pattern
  2. I borrowed getIndicesOf from this answer by Tim Down

function find() {
    var i, j, k;
    var txtOne = $('.one').text();
    var txtTwo = $('.two').text();
    var linesOne = txtOne.split("\n");
  
    // Get search patterns from "one"
    var patterns = getSearchPatterns(linesOne);

    // Get content lines from "two"
    var linesTwo = txtTwo.split("\n");
    while (linesTwo.length > 0 && !linesTwo[0]) {
        linesTwo.shift();
    }

    // Get all the positions of all patterns in all lines
    var searchResults = [];
    var patternInLines, positionsInLine;
    for (i = 0; i < patterns.length; i++) {
        patternInLines = [];
        for (j = 0; j < linesTwo.length; j++) {
            positionsInLine = getIndicesOf(patterns[i], linesTwo[j], true);
            patternInLines.push(positionsInLine);
        }
        searchResults.push(patternInLines);
    }

    // Get the occurrences of all patterns at the same position on consecutive lines
    var results = [];
    var firstPatternInLine, firstPatternPosition, patternInLine, found;
    var firstPattern = searchResults[0];
    for (j = 0; j < linesTwo.length - patterns.length; j++) {
        firstPatternInLine = firstPattern[j];
        for (k = 0; k < firstPatternInLine.length; k++) {
            firstPatternPosition = firstPatternInLine[k];
            found = true;
            for (i = 1; i < patterns.length; i++) {
                patternInLine = searchResults[i][j + i];
                if (patternInLine.indexOf(firstPatternPosition) < 0) {
                    found = false;
                    break;
                }
            }
            if (found) {
                results.push({
                    line: j,
                    position: firstPatternPosition
                })
            }
        }
    }

    // Display results
    for (i = 0; i < results.length; i++) {
        console.log(results[i]);
    }
    if (results.length < 1) {
        console.log("No occurrence found");
    }
}

// Trim the search lines to get the minimal search "block"
function getSearchPatterns(lines) {
    var items = [];
    var result = [];
    var i, txt, offset, item;
    var minOffset = 1000000;
    var maxLength = 0;
    for (i = 0; i < lines.length; i++) {
        txt = lines[i].trim();
        if (txt) {
            offset = lines[i].indexOf(txt);
            items.push({
                str: txt,
                offset: offset
            });
            minOffset = Math.min(offset, minOffset);
        }
    }
    for (i = 0; i < items.length; i++) {
        item = items[i];
        item.offset -= minOffset;
        maxLength = Math.max(item.offset + item.str.length, maxLength);
    }
    for (i = 0; i < items.length; i++) {
        item = items[i];
        result.push(paddRight(paddLeft(item.str, item.offset), maxLength));
    }
    return result;
}

function paddLeft(str, count) {
    var padding = "";
    for (var i = 0; i < count; i++) {
        padding += " ";
    }
    return padding + str;
}

function paddRight(str, length) {
    var result = str;
    while (result.length < length) {
        result += " ";
    }
    return result;
}

// Find all positions of search string in string
// By Tim Down at https://stackoverflow.com/a/3410557/1009922
function getIndicesOf(searchStr, str, caseSensitive) {
    var searchStrLen = searchStr.length;
    if (searchStrLen == 0) {
        return [];
    }
    var startIndex = 0, index, indices = [];
    if (!caseSensitive) {
        str = str.toLowerCase();
        searchStr = searchStr.toLowerCase();
    }
    while ((index = str.indexOf(searchStr, startIndex)) >= 0) {
        indices.push(index);
        startIndex = index + searchStrLen;
    }
    return indices;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="one">
     a
    bcd
     e
</div>
<div class="two">
    ++ + ++ ++++ + ++ + + + a 
    + +   ++++  a ++  + + +bcd
    + a  +++ + bcd ++ + +++ e 
    +bcd + + ++ e + + + ++ ++
    + e ++++++++++++++++++++++
</div>
<button onclick="find()">Test!</button>
Community
  • 1
  • 1
ConnorsFan
  • 70,558
  • 13
  • 122
  • 146
  • At first glance this code example appears to work... because all of the data uses "+" plus signs. If the data is turned into letters, then this code example won't match the vertical & horizontal pattern which the OP is asking for. It's attempting to select the horizontal pluses on either side of the middle "+++" & not the + above nor below that. – Clomp Dec 23 '16 at 22:46
  • 1
    @Clomp - I see what you mean. If you are right, the OP wants to match the pattern given in the markup, not in the rendered HTML (which answers the question asked by haltersweb in the comments). – ConnorsFan Dec 23 '16 at 23:00
  • If the data will contain identical data elements where each + occurs at then your code would work, but that's risky because we don't know if the data will be identical or different. The OP did mention: "The pattern has to be in that same order in .two". So I wrote an answer that would do that for different data. Either way, we're both trying to help him out. :) – Clomp Dec 24 '16 at 02:12
2

your jquery code will look something like this. You can play more with this logic

    jQuery().ready(function(){
var lines = $(".two").text().split("\n");
for(i=1;i<=lines[1].length;i++){
    if(lines[1][i]=='+' 
  && lines[2][i-1]!='undefined' && lines[1][i]==lines[2][i-1] 
  && lines[2][i]!='undefined' && lines[1][i]==lines[2][i] 
  && lines[2][i+1]!='undefined' && lines[1][i]==lines[2][i+1]
  && lines[3][i]!='undefined' && lines[1][i]==lines[3][i] 
  ){
  console.log('exists');
  }
}
});

Here is the fiddle:https://jsfiddle.net/ahmadasjad/12eqhs7L/5/

Ahmad Asjad
  • 825
  • 1
  • 8
  • 29
  • can you look at this https://jsfiddle.net/12eqhs7L/4/. When I change the `.one` pattern then it still works which it shouldn't. – Om3ga Dec 21 '16 at 21:53
  • my fiddle was just for that pettern, you can build a logic based on this. – Ahmad Asjad Dec 21 '16 at 22:00
  • And the thing you are looking it's also possible, first let you try, it you couldn't let me know. – Ahmad Asjad Dec 21 '16 at 22:03
  • Well the thing is that in `.two` the text is not displayed in that same pattern(in fiddle) I showed in question. That might be the reason? – Om3ga Dec 21 '16 at 22:08
  • check again earlier there're some error. there is one pattern available in .two as you can see by eye as well while matching. – Ahmad Asjad Dec 21 '16 at 22:18
  • https://jsfiddle.net/12eqhs7L/6/ I tried this but this does not seem to be what I want. Because the top `+` is first checked in line 1 which is true in several places. Let me know if you could help me in this further. – Om3ga Dec 21 '16 at 22:24
  • Moreover, the pattern in `.one` could be any other pattern. Not just this one. – Om3ga Dec 21 '16 at 22:31
  • My answer as if it's static content as it's right now is fine. But if you want to check dynamically like .one content exist in .two or not, you'll have to do following: take first line of .one and search it in .two, if found, search for second line in the line after that at same column, etc.... – Ahmad Asjad Dec 21 '16 at 22:32
  • That is exactly what I am doing in my solution which I put in my comment above. – Om3ga Dec 21 '16 at 22:35
2

There are quite interesting ideas in previous posts, I like to add functional approach which is more compact (it uses lodash). Main idea is to trim matching text and compare it with shifting window(cut) on the target text. On top of that function also returns position where match is found from the left. See working Fiddle:

function findText(text, search) {
  const width = maxWidth(search)-minTrim(search);
  const matcher = cut(search, minTrim(search),width).join('');
  return _.range(text[1].length) // create array of possible matches
            .map(col=>cut(text, col, width).join(''))
            .indexOf(matcher)+1; // and match with matcher
}

// Returns left padding size, e.g. 3 in the example
function minTrim(t) {
  return _.min(t.filter(s=>!!s).map(s=>s.length-_.trimStart(s).length))
}

// Returns window within $text at $start position with $width
function cut(text, start, width) {
  return text.map(s=>_.padEnd(s.substr(start,width),width))
}

// Returns maximum width of the line within text
function maxWidth(text) {
  return _.max(text.map(s=>s.length))
}

Function findText can be used like this:

const two=document.getElementsByClassName("two")[0].innerHTML.split('\n');
const one=document.getElementsByClassName("one")[0].innerHTML.split('\n');
alert((pos=findText(two,one)) ? `found at position ${pos}` : "not found");

Option 2 if string consist only of '+' and length is not more than 64 characters we can convert above function to bit mask matching. E.g. convert every string to the binary digit, then shift target string, applying search mask (e.g. window in the above example) and comparing numbers. See working fiddle:

function findTextBin(text,search) {
  const toBin=str=>str.split('')
          .reduce((res,c)=>res<<1|(c==='+'?1:0),0)
  let one=search.map(toBin)
  let mask=toBin(_.max(one).toString(2).split('').map(c=>'+').join(''))
  let two=text.map(toBin)
  let length=_.max(text.map(str=>str.length))
  for(let i=length; i; i--,two=two.map(num=>num>>1))
    if(two.every((num,row)=>(num&mask)===one[row]))
      return i-mask.toString(2).length;
  return false;
}
Max Vorobjev
  • 1,233
  • 6
  • 7
1

Just a suggestion, but you can hash the content to compare them. This code uses CryptoJS library to generate MD5 hash

<script src="http://crypto-js.googlecode.com/svn/tags/3.0.2/build/rollups/md5.js"></script>
<script>
    var div1 = CryptoJS.MD5( $('.one').text() );
    var div2 = CryptoJS.MD5( $('.two').text() );
    if(div1 === div2) {
        // your code here
   }
</script>
mrid
  • 5,782
  • 5
  • 28
  • 71
1
$('.one').diffString($('.two').html());
Pang
  • 9,564
  • 146
  • 81
  • 122
1

Assuming that the number of rows are same in both, the following solution keeps it simple to find the pattern.

Preconditions:

This solution needs the pattern, and the target to be formed as the follows:

var pattern = [
  ' + ',
  '+++',
  ' + '
];

var target = [
  '+ +   ++++  + ++  + + +',
  '+ ++ +++ + +++ ++ + +++',
  '+ ++ + + ++ + + + + ++ '
];

I think a simple javascript operation can do that -- reading the HTML row-by-row, and appending it to an array. If needed, I can provide that code as well.

How it works:

The code first decides the width of pattern, and then continues to find patterns of such width column-by-column in the target array. The loop stops when a pattern of lower width is detected, or a match is found.

The code:

// Our core function
function matches(target, pattern) {

  if (pattern.length > target.length) {
    return false;
  }

  var patternWidth = findPatternWidth(pattern);
  var startIndex = 0;
  var currentPattern = getNextPattern(target, startIndex, patternWidth);

  while (patternValid(currentPattern, patternWidth)) {
    if (identicalArrays(currentPattern, pattern)) {
      return true;
    }

    startIndex++;
    currentPattern = getNextPattern(target, startIndex, patternWidth);
  }

  return false;
}

// -*-*-*-*-*- HELPER FUNCTIONS -*-*-*-*-*-*

// Finds the width of the pattern we want to match
function findPatternWidth(pattern) {
  var maxWidth = 0;

  for (var i = 0; i < pattern.length; i++) {
    if (pattern[i].length > maxWidth) {
      maxWidth = pattern[i].length;
    }
  }

  return maxWidth;
}

// Finds the next suitable pattern, starting with an index, of a maximum width
function getNextPattern(target, startIndex, maxWidth) {
  var result = [];

  for (var i = 0; i < target.length; i++) {
    result.push(target[i].substr(startIndex, maxWidth));
  }

  return result;
}

// Checks if two non-nested arrays are identical
function identicalArrays(source, target) {
  if (source.length !== target.length) {
    return false;
  }

  for (var i = 0; i < source.length; i++) {
    if (source[i] !== target[i]) {
      return false;
    }
  }

  return true;
}

// Checks if a given pattern is of given width
function patternValid(pattern, maxWidth) {
  for (var i = 0; i < pattern.length; i++) {
    if (pattern[i].length < maxWidth) {
      return false;
    }
  }

  return true;
}

I believe that this approach can be extended to get rid of this assumption the number of rows are same in both.

31piy
  • 23,323
  • 6
  • 47
  • 67
1

To find the pattern in another string, the position of the pluses relative to each other is first found; then the pluses in the second string are checked if they are in the same relative positions.

The findCoordinates function finds the position of the pluses in the pattern relative to the first plus in the pattern string. For the pattern,

 +
+++
 +

the + in the top row is at (0,0). The first + in the second row is at (-1,1) since it is one row below and one place to the left of the first +. Similarly, the other pluses are at (0,1), (1,1), and (0,2) respectively.

The hasPattern function uses the relative coordinates to check if the pattern is present in the second string. For each + in the second string, it checks if there are other + characters at the corresponding positions to match the pattern. For the example pattern, the function would check if a character is a plus. If it is a +, then it checks the characters below to the left, directly below, below to the right, and two rows below. If those characters are also pluses, then the function returns true.

function findCoordinates(string) {
  var rows = string.split('\n');
  var coordinates = [];
  var first = null;

  for (var i = 0; i < rows.length; i++) {
    for (var j = 0; j < rows[i].length; j++) {
      if (rows[i][j] === '+') {
        if (first === null) {
          first = {x:j, y:i};
        }
        coordinates.push({x:j-first.x, y:i-first.y});
      }
    }
  }

  return coordinates;
}

function hasPattern(string, coordinates)
{
  var rows = string.split('\n');
  var matches = 0;
  var coordinate = null;

  for (var i = 0; i < rows.length; i++) {
    for (var j = 0; j < rows[i].length; j++) {
      if (rows[i][j] === '+') {
        matches = 0;
        for (var k = 0; k < coordinates.length; k++) {
          coordinate = coordinates[k];
          if (rows[i + coordinate.y] && rows[i + coordinate.y][j + coordinate.x] === '+') {
            matches++;
          }
        }
        if (matches === coordinates.length) {
          return true;
        }
      }
    }
  }
  return false;
}

var one = document.querySelector('.one');
var two = document.querySelector('.two');

console.log(hasPattern(two.textContent, findCoordinates(one.textContent)));
div {
  font-family: monospace;
  white-space: pre;
}
<div class="one">
    +
   +++
    +
</div>

<div class="two">
    + +   ++++  + ++  + + +
    + ++ +++ + +++ ++ + +++
    + ++ + + ++ + + + + ++ 
</div>
David
  • 383
  • 10
  • 18
0

This solution won't work if the number of lines of the test pattern and source pattern are different.

The idea is to create a string of sequential columns of the pattern. Then we can easily check if the pattern exists using indexOf

Example, a pattern like this:

1 2 3
+   +
  + 
+ + +

becomes "+ + +++ +"; // equivalent of ["+ +"," ++","+ +"].join("");

enter image description here Here is the fiddle https://jsfiddle.net/flyinggambit/vcav3c46/

function getVerticalPattern(pattern){
  // split the pattern in to an array, each item represents each line
  var pattern = pattern.split("\n"); 
  var numLines = pattern.length; // Find the number of lines

  // Find the longest string
  var longestString = 0;
  for(var i=0; i<pattern.length; ++i){
      longestString = pattern[i].length;
  }

  // Rearrange the pattern
  var newPattern = [];
  for (var i=0; i<longestString; i++){
      for (var j=0; j<numLines; j++){
          if(pattern[j] && pattern[j].length){ // sometimes the split was creating empty strings ""
            newPattern.push(pattern[j][i]);
          }
      }   
  }
  return newPattern.join("");
}

function findPattern(testPattern, srcPattern){
  return (getVerticalPattern(srcPattern)).indexOf(getVerticalPattern(testPattern));
}

var srcPattern = document.getElementsByClassName("two")[0].innerHTML;
var testPattern = document.getElementsByClassName("one")[0].innerHTML;
var result = findPattern(testPattern, srcPattern);

if(result !== -1){
  console.log("pattern found");
}else{
  console.log("pattern not found");
}
<pre class="one">
    +
   +++
    +
</pre>


<pre class="two">
    + +   ++++  + ++  + + +
    + ++ +++ + +++ ++ + +++
    + ++ + + ++ + + + + ++ 
</pre>

It was thrilling and fun to answer this question :)

Flying Gambit
  • 1,238
  • 1
  • 15
  • 32
0

This is quick and ugly, still some error checking and optimization left to be done... but enough to show the concept:

var pattern = [
  '+ + ',
  '+ ++',
  '+ ++'
];

var target = [
  '+ +   ++++  + ++  + + +',
  '+ ++ +++ + +++ ++ + +++',
  '+ ++ + + ++ + + + + ++ '
];

function getAllIndexes(arr, val) {
    var indexes = [], i = -1;
    while ((i = arr.indexOf(val, i+1)) != -1){
        indexes.push(i);
    }
    return indexes;
}

function checkNextRow(pattern, target, pRow, tRow) {
  var matchePos = target[i].indexOf(pattern[0]);
}


function test(pattern, target) {
  //get pattern hights for later
  var pH = pattern.length;
  var tH = target.length;

  //target should have equal or more rows
  if (tH < pH) return 'not found';

  //which is the lowest row of the target where top row of the pattern can be matched?
  tLastTop = tH - pH;


  //function to check row of pattern
  function checkRest(pRow, tRow, hPosMatch) {
    console.log('searching for '+pattern[pRow]+' in '+target[tRow]);
    var matchPos = target[tRow].indexOf(pattern[pRow], hPosMatch);

    console.log('search result>>>>'+matchPos);
    if (matchPos >= 0 && matchPos === hPosMatch) {
      if (pRow === pH-1) {
        console.log('last row of pattern matched');
        return true; //last row of pattern matched
      } else {
        console.log('calling checkRow from itself');
        return checkRest(pRow+1, tRow+1, hPosMatch);
      }
    } else {
      console.log('pattern not found in row, returning false',hPosMatch, matchPos);
      return false;
    }
  }

  //search for top row of pattern
  for (i = 0; i <= tLastTop; i++) {
    //get all accurance indexes of patern's first row
    var matches = getAllIndexes(target[i], pattern[0]);
    console.log("matches",matches);
    if (matches.length <= 0) continue;

    //try other rows for each accurance position
    for (h = 0; h <= matches.length; h++) {
      var hPosMatch = matches[h];
      console.log('calling checkRow from iterator');
      var result = checkRest(1,i+1,hPosMatch);
      if (result) return true;
    }
  }
  return false;


}

console.log(test(pattern, target));

I skipped loading DIV content into pattern/target vars as it seems trivial. Also I assumed spaces are also important for pattern, meaning '+ +' does not match '+++'

JSBin is here: http://jsbin.com/kayeyi/edit?js,console

Mirko Vukušić
  • 2,091
  • 1
  • 10
  • 14
0

To not overcomplicate things I made some assumptions on the inputs:

  1. Number of lines in inputs are equal
  2. Any empty line from inputs can be omitted
  3. Every non-empty line of inputs should contain whitespace characters at "missing" places
  4. The whitespace character in both inputs is the same and it's NOT a line break

Besides of collecting data from the DOM the solution goes through following steps:

  1. Both pattern and input are converted into arrays of strings, each string for a line. Arrays must have same length (assumption 1)
  2. For each pair of lines list of possible matches are collected - list of all indices in input string on which pattern string is included
  3. Result lists are flattened into single list and all indices are counted. Now for each possible index we have number of lines where match is successful
  4. Filter the result to leave only indices with maximum count

There is also a working fiddle of the solution

function indexOf(pattern, input){
 if(pattern.length !== input.length) throw 'Works only for same number of lines';
 var counts = [].concat(...input.map((s,i) => allMatches(pattern[i],s))).reduce((r,e) => (r[e] = (r[e] || 0) + 1, r), {}); //find all matches for all lines and flatten the result
  var stops = Object.keys(counts).filter(k => counts[k] === pattern.length); //get only those that span across all the lines
  return stops[0] || -1; //first found or -1 if empty
}
function allMatches(substr, str){
 var result = [], index = 0;
  while(~(index = str.indexOf(substr, index))) // ~(-1) is falsy
   result.push(index++);
  return result;
}
function readContent(element){
 return (element.value || element.textContent).split(/[\r\n]+/).filter(s => s.length); //get all non-empty lines
}
function showResult(pattern, input){
 var chars = Array(input[0].length).fill('\xa0'); // &nbsp;
 chars[indexOf(pattern, input)] = '^';
  document.querySelector('.result').textContent = chars.join('');
}
function updater(){
 showResult( readContent(document.querySelector('.one')),
       readContent(document.querySelector('.two'))
 );
}
document.querySelector('.one').addEventListener('input', updater);
document.querySelector('.two').addEventListener('input', updater);
updater();
.one, .two, .result{
  padding: 0;
  margin: 0;
  font-family: monospace;
  width: 100%;
  font-size: 1rem;
}
<textarea class="one" rows="4">
 + 
+++
 + 
</textarea>
<textarea class="two" rows="4">
+ +   ++++  + ++  + + +
+ ++ +++ + +++ ++ + +++
+ ++ + + ++ + + + + ++ 
</textarea>
<div class="result"></div>
Vasily Liaskovsky
  • 2,248
  • 1
  • 17
  • 32