EPavlova
BAN USERHello,
A little diversion from my suggestions above. The rules for Android locked patterns are :
Each pattern must connect at least four dots.
The dots in the pattern must all be distinct.
If the line segment connecting any two consecutive dots in the pattern, middle dot (between them) should be already in pattern.
Also it is allowed to have "knight" moves - for example two points on 0,0 and 2,1.
So what should be done : 1 Generate all variations of 4...9 of 9 points and cut all solutions that are not valid. We coudn't come to there following pattern rules.
Here below is Java code. Hope will help.
public class AndroidLockPattern {
private boolean used[] = new boolean[9];
private boolean isValid(int index, int last) {
if (used[index])
return false;
if(last == -1)
return true;
// knight moves
if((index + last)%2 == 1)
return true;
// indexes are from both side of the diagonals for example 0,0, and 8,8
int mid = (index +last)/2;
if ( mid == 4)
return used[4];
// adajcent cells on diagonal - for example 0,0 and 0,1
if ((index%3 != last%3) && (index/3 != last/3)) {
return true;
}
// all other adjacent cells (two cells in one row or two cells in one column)
return used[mid];
}
public void numberOfPatterns() {
int res =0;
for (int len = 4; len <= 9; len++) {
res += calcPatterns(-1,len);
for (int i = 0; i < 9; i++) {
used[i] = false;
}
}
System.out.println(res);
}
private int calcPatterns(int last,int len) {
if (len == 0) {
return 1;
}
else {
int sum = 0;
for (int i = 0; i < 9; i++) {
if (isValid(i, last))
{
used[i] = true;
sum += calcPatterns(i, len - 1);
used[i] = false;
}
}
return sum;
}
}
}
Hello,
First my initial tought was to traverse through the string and to find intersections but the problem clearly states that string is too long (a lot of time and memory consuption) and decided to restrict myself only to a solution taking into account entries.
I would like to propose the following solution with complexity O(mlogm) where m is the number of entries. Let's sketch the algorithm :
First I generate two points from each entry - start point and end point and sort all point by their string index (start or end index). Then I traverse point array and store in a set all tags which are part of the query tags and still have't finish (their end time has not been come) yet. In case I have ther is an intersection of all querry tags ( set.size() == tags.size()) then produce the result.
Here is some code I wrote :
private class Interval {
private int s;
private int e;
private int tag;
Interval(int s, int e, int tag) {
this.s = s;
this.e = e;
this.tag = tag;
}
public Interval(int s, int e) {
this.s = s;
this.e = e;
}
public String toString() {
return String.format("%d - %d",s,e);
}
}
public class StringQueries {
private class Entry implements Comparable<Entry>{
private int index;
private int type;
private int tag;
Entry(int s, int type, int tag) {
this.index = s;
this.type = type;
this.tag = tag;
}
public int compareTo(Entry e) {
if (index < e.index)
return -1;
if (index > e.index)
return 1;
return 0;
}
}
private List<Entry> col;
public StringQueries(List<Interval> ls) {
col = new ArrayList<Entry>();
for (int index = 0; index < ls.size(); index++) {
col.add(new Entry(ls.get(index).s,1,ls.get(index).tag));
col.add(new Entry(ls.get(index).e,2,ls.get(index).tag));
}
Collections.sort(col);
}
public List<Interval> query(Set<Integer> set) {
List<Interval> result = new ArrayList<>();
if (col.size() == 0)
return result;
Set<Integer> tempSet = new HashSet<>();
int start = col.get(0).index;
for (int index = 0; index < col.size(); index++) {
Entry current = col.get(index);
if(set.contains(current.tag)) {
if (current.type == 2) {
if(tempSet.size() == set.size())
result.add(new Interval(start, current.index));
tempSet.remove(current.tag);
} else if (current.type == 1) {
start = current.index;
tempSet.add(current.tag);
}
}
}
return result;
}
}
zr.roman , I see your point ( unfortunately my russian is not very good to answer). Why should we use delimiter to split string array? Coudn't we use byte length followed by string encoding for the dictionary? Then if some string repeat in the array we could encode string index in dictionary, not the whole string. Just ponderiong over it.
- EPavlova December 09, 2015Added some correction on code:
public class CPeekIterator {
CIterator it;
int peekVal ;
boolean hasNext;
public CPeekIterator(CIterator it) {
this.it = it;
hasNext = it.hasNext();
peekVal = it.next();
}
int next() {
int temp = peekVal;
peekVal = it.next();
return temp;
}
int peek() {
return peekVal;
}
boolean hasNext() {
boolean temp = hasNext;
hasNext = it.hasNext();
return temp;
}
}
If it is possible to augment all methods in CPeekIterator , CIterator could be wrapped in the follwowing way.
public class CPeekIterator {
CIterator it;
int peekVal ;
boolean hasNext;
public CPeekIterator(CIterator it) {
this.it = it;
hasNext = it.hasNext();
peekVal = it.next();
}
int next() {
int temp = peekVal;
peekVal = next;
return temp;
}
int peek() {
return peekVal;
}
boolean hasNext() {
int temp = hasNext;
hasNext = it.next();
return temp;
}
}
Repgeraldgloria02, Android test engineer at Achieve Internet
I am a personal trainer. I design programs and provide nutritional advice and coaching. I wanted to share my knowledge ...
Repjacksonbetty625, Accountant at 247quickbookshelp
My work is specialized help, regardless of whether on the telephone, face to face, or distantly, identified with PC frameworks ...
RepHenryMelvin, Korean Air Change Flight at AMD
Hello, everybody! My name is Henry,I am a picture-drawer.Art drawing & painting classes for adults, kids, teens.We have ...
This is round robin tournament algorithm. Here is my implementation :
- EPavlova January 06, 2016