Search in this blog

Saturday, December 5, 2015

Enable Shared Folders and Clipboard in Virtualized Linux using VirtualBox

I will assume you have installed a Linux distribution in VirtualBox, to enable the shared folders and clipboard you have to follow these steps:
1- Open a terminal
2- apt-get update
3- apt-get upgrade
4- apt-get install build-essential module-assistant
5- m-a prepare
6- in VirtualBox menu bar choose 'devices -> Install Guest Additions'
7- Go to the terminal and run 'mount /media/cdrom'
8- run 'sh /media/cdrom/VBoxLinuxAdditions.run' and follow the instructions.

Notes:
- If you get errors after step 6, reboot your Linux and continue in step 6.
- You may need root access to run some commands.

After these steps you should be able to share folders and clipboard, you may need to reboot after step 8.
Posted by at No comments:
Labels:

Sunday, October 25, 2015

Competitive Programming Resources

Competitive Programming / Programming Contest Resources for learning things

This list is going to be edited frequently when I find good resources to learn things.

Tools:
Graph drawing: http://mxwell.github.io/draw-graph/


Improving in CP


Dynamic Programming Optimization Problems:
http://codeforces.com/blog/entry/47932

Non Trivial DP tricks:
http://codeforces.com/blog/entry/47764

Slope Trick:
http://codeforces.com/blog/entry/47821

Floyd Warshall:
https://www.quora.com/Why-is-the-order-of-the-loops-in-Floyd-Warshall-algorithm-important-to-its-correctness/answer/Jayaprakash-Sundararaj

Manacher's Algorithm:
https://www.quora.com/What-is-Manachers-algorithm-How-can-we-use-it-to-find-all-palindromic-sub-strings-in-a-string

Meet in the middle:
http://qr.ae/R3GIji


Suffix Array - Linear time construction (DC3) explained:
http://qr.ae/R6EeWR

Fractional Cascading:
http://codeforces.com/blog/entry/21892
http://www.cs.uu.nl/docs/vakken/ga/slides5b.pdf (Page 43)


Bipartite Matching:
http://www.slideshare.net/KuoE0/acmicpc-bipartite-matching?next_slideshow=1


Algorithms and Data Structures Implementations:
https://sites.google.com/site/indy256/


Suffix Automaton
http://codeforces.com/blog/entry/20861

Binary Indexed Tree for Range Minimum Query
http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

Binary Indexed Tree for coefficients in functions:
http://apps.topcoder.com/forums/?module=Thread&threadID=756271


SQRT Decomposition


Combinatorics:

Trie

Sweep Line


SPOJ Must Solve problems

Centroid Decomposition


Competitive programming courses


Matching in general graph

Matrix Power


Matrix Power alternative using DP

Treap


Splay Tree

Segment Tree

2D Segment Tree

Persistent Segment Tree

Ordered Sets



Data Structures

Map Short Permutation (11, 12 items) to integer

Segmented Sieve


Dynamic Connectivity

Aho-Corasick

Find primes in some interval


Suffix Tree

Suffix Array


Sieve Methods


2-SAT


Graphs

FFT
http://codeforces.com/blog/entry/14744 
http://codeforces.com/blog/entry/20751
http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt

MO’s Algorithm

Game Theory

Manacher’s Algorithm

Minimum Diameter Spanning Tree

Dynamic Programming (DP)

DP with bitmasks

DP over integers

DP Optimizations



Heavy Light Decomposition
http://blog.anudeep2011.com/heavy-light-decomposition/

Ternary Search


Trie

Z-Algorithm


Nim Game
http://web.mit.edu/sp.268/www/nim.pdf


World Finals 2015 solutions

Andrew Stankevich Contests

Regional Contests with editorial

Training Advices

Saratov University Notebook


Complex Numbers in Geometry
https://uqu.edu.sa/files2/tiny_mce/plugins/filemanager/files/4041834/cnum_mr.pdf





Link-Cut Tree
http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
http://www.cs.cmu.edu/~avrim/451f12/lectures/lect1009-linkcut.txt

Burnside's lemma
http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html



Posted by at No comments:
Labels:

Sunday, October 4, 2015

The 2015 ACM-ICPC Caribbean Local Contests (Real contest) Solutions

The 2015 ACM-ICPC Caribbean Local Contests (Real contest) and Gran Premio de México & Centroamérica Fase III happened in 2015/10/26.

I will explain my way for solving all the problems here, if you don't understand something or have a question don't dude to ask.

If you have a different / better solution, share it with us.

THE POST IS NOT FINISHED, I WILL DO IT AS SOON AS I CAN.

I hope this can be useful for you.


The problems can be solved in COJ.
A. Naebbirac Phrases (Trivial)
B. Careful with Poison (Combinatorics)
C. Counting Figures (Ad-hoc, Sweep line?)
D. Dr. B - Tree II (DP)
E. Even Number of Divisors (Number theory, Binary Search)
F. Fast Traveler Game (Simulation)
G. Fear of the Dark (HLD, Segment Tree)
H. How Many Numbers (Backtracking)
I. List of Natural Numbers (Find the pattern)


A - Naebbicar Phares

Read two string S and T and count how many characters are different in S and T at same index, for example if S = "alex" and T = "alxs" answer is 2, is guaranteed that length of S is equal to length of T, the letters in black are the mismatches.

Here is my code.

B - Careful with Poison

First how to solve the problem without the square? Binomial Coefficient is you friend.

Let ways(N, K) = number of ways to choose K elements from a set of N.

This will ignore the square, we have to use the Inclusion Exclusion Principle to remove the invalid ways.

To do this, let represent the square as 9 points in the grid:

ABC
DEF
GHI

The points "C", "E" and "G" are exclusive, this means that if our path can pass only from one of these three points.

Let count(N, a, b) = the number of ways to get from point (0, 0) to point (N, N) passing the point located at (a, b), this can be broke in the number of ways to get from (0, 0) to (a, b) multiplied by the number of ways to get from (a, b) to (N, N).

Now to remove the invalid ways we can use the previous function and the result is = ways(N, N) - count(N, Cx, Cy) - count(N, Ex, Ey) - count(N, Gx, Gy).

Notice that N can be large and is an obvious overflow, we are required to compute the result modulo a prime number, this help us to use modular arithmetic to compute the answer, we can pre compute all the factorials between [0, MAX] MOD M and compute the binomial coefficient using the modular inverse.

Complexity is O(1) per query if you precomputed the modular inverse or O(log(N) ) computing it as required.

See the code for further details.

Here is my code.


C - Counting Figures

This problem can be solved detecting only the figures of 4, 6 and 8 sides.

A figure have 4 sides if is a completed rectangle:

XXXX
XXXX
XXXX

The X is a filled point.

A figure have 6 sides if filling a subrectangle in a corner makes a complete rectangle:

XXEE
XXEE
XXXX
XXXX

The E is an empty point.

A figure have 8 sides if require two corners to be filled as rectangles to build a complete rectangle or if requires to fill a rectangle starting in a side but not in a corner, see the examples:

XXEE
XXEE
XXXX
XXEE

Or

XXXX
XXEE
XXEE
XXXX

This is an easy to find solution but really tedious to code, i'm trying to get a better and shorter approach, my code is around 300 lines long.

THIS WILL BE UPDATED WITH A BETTER SOLUTION.

Here is not my code.




D - Dr. B - Tree II

Let ways(L, K) = number of ways to make a string of length L with exactly K mirror couples, Z is the number of different characters allowed being 10 in this case (all the digits from 0 to 9).

If L is odd that means we should place the middle character of the string and then solve the problem for a string of even length, we can place this in Z ways and only if K > 0 because always this character will be a mirror couple, example, X is the character to place.
...X...

If L is even we can split the string in two parts of length L/2 (left and right) and place exactly two characters, one in left part and one in the right one, in this way we can decide to place a mirror couple or not, for example.

X....X

In this case we are setting a mirror couple and there are Z ways to do it.

X....Y

in this case we are setting two character being not a mirror couple, there are Z*(Z-1) ways to do it, you can place every character at X and every character but X for Y.

Here is a pseudocode:

 ways(L, K)
 if (L == 0 && K == 0) ret 1
 if (L < 0 || K < 0 ) ret 0
 if (L is odd) ret Z*ways(L-1, K-1) 
 ret Z*ways(L-2, K-1) + Z*(Z-1)*ways(L-2, K)

The complexity is exponential but you can memoize the results using Dynamic Programming to get a complexity of O(L*K).

Don't forget to do all operation with modulo.

Here is my code.



E - Even Number of Divisors

We are given an interval [L, R] and we have to count how many numbers K in that interval have even number of divisors, for example, the next list contains the required information for the values in the interval [1, 6]:

K = 1 2 3 4 5 6
D = 1 2 2 3 2 4
C = n y y n y y

K is the value we want to know if should be counted.
D is the number of divisors of K.
C is "y" if have and even number of divisors (should be counted).

This is not an obvious task but we can invert the problem.

Let f(L, R) = the number of values K in the interval [L, R] where the number of divisors of K is odd.

If we can compute f efficiently, the answer would be (R - L + 1) - f(L, R), (R - L + 1) is the length of the interval.

How to compute this? The trick is that a number K has odd number of divisors if K is a perfect square (see this to believe), there is at most sqrt(N) perfect squares in the interval [1, N], so we can pre compute all perfect squares in this interval (where N is the maximum possible value) and store it in an array.

For answer a query f(L, R) = firstLower(R) - firstHigher(L) + 1

firstLower(N) = the index of the last element in the array strictly <= N
firstHigher(N) = the index of the first element in the array strictly >= N

Both can be computed using binary search.

The complexity is O(N*log(N) ) where N = sqrt(max possible number).

Here is my code.


F - Fast Traveler Game

This is a simulation problem, do what is required and you will get accepted your solution.

Here is my code.


G - Fear of the Dark

This is not an easy problem, you need to know about several non-trivial data structures:
Once you about all of them the problem may seem trivial but code it without mistakes is not easy.
I hope to have the time to explain it better later.

First you need to solve FLIPCOIN in order to prove you understand how to write the required Segment Tree for this problem.

Complexity is O(N * log(N) + Q * log(N) * log(N) ) where N is the number of nodes and Q the number of queries.

Here is my long and modulated code.

H - How Many Numbers

You are given two variables, O and E, you have to count how many distinct numbers can be formed using exactly O odd digits and E even digits, including negative numbers, O + E <= 18.

This is an easy problem solvable with backtracking because the constrains are small.

Is obvious that we can count only the positive numbers and multiply the result by 2.

There are two especial cases to handle here.
1.- The number can't have leading zeros.
2.- If O = 0 and E = 1 means that we need to count all even digits and the number of digits = 1, this means that we have to add 1 to the result for counting the zero, the result for this case is 9, 4 possible even digits positive and negative + the zero.


Understanding the 2 above cases makes easy to design a solution.

Suppose you have a case where O = 1 and E = 1, X and Y are both digits, we need to place them.

XY

The two possibilities are that X is and even digit and Y is an odd digit or X is and Odd digit and Y an even.

The first case is to place an odd digit at X position and an even digit for Y.
There are 5 odd digits for X (1,3,5,7,9) and 5 even digits for the Y position (0,2,4,6,8), so the total is 5*5.

The second case is to place an odd digit at X position and an even for Y.
There are 4 options for X (2,4,6,8) because the number can't start with zero and 5 options for Y, so the result is 4*5.

The answer is 5*5 + 4*5 for positive numbers, so muliply it by 2 to get the required result.

Now we need write a function for the general case.

f(first, odds, evens)
 if (odds == 0 && evens == 0) ret 1
 ans = 0
 if (odds != 0 ) ans += 5 * f(false, odds - 1, evens)
 if (evens != 0) ans += 5 - (first ? 1 : 0) * f(false, odds, evens-1)
 ret ans

This help us to find the answer for positive numbers, handle the case 1 0 outside this.

In this solution we are avoiding to create numbers with leading zeros but there is other way for do it, you can count all the numbers with leading zeros and subtract the numbers starting with zero, use what you prefer.

Be careful because the result doesn't fit in an Integer data type but a Long is enough.

The complexity is O(2^N) per case, where N = E+O

Here is my code.


I - List of Natural Numbers

We can notice that a number K will be added only in the K-th step, using this information we can generate using brute force how many times a number K is added to the list for some steps like 20 for example.

This is the result for the first 15 values.
2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8

There is no obvious pattern but we can use OEIS and paste this values as input, OEIS will try to find a sequence, fortunately there is a sequence =D.

 The number of times a value K is in the final list is:
  • 2 if K = 1 
  • phi(K) if K != 1
Phi is the Euler's totient function and can be computed in O( sqrt(N) ) which is acceptable for this problem, learn about it.

 Complexity is O( sqrt(N) ) per case.

Here is my code.




Posted by at No comments:
Labels:

Monday, July 13, 2015

MyBatis-Spring Summary for Production Applications

MyBatis is my favorite ORM, when I first tried to use it I got surprised because the configuration was a really easy task.

I use it in every app with a relational database, I combine it with Spring as a Dependency Injection framework.

Most of the configuration I will write is using Annotations, read more about MyBatis-Spring to get a better understanding.

The next beans are for the Spring XML file configuration:

    <!-- DataSource -->
    <bean id="dataSource"
          class="org.apache.tomcat.jdbc.pool.DataSource">
        <property name="driverClassName" value="org.postgresql.Driver" />
        <property name="url" value="jdbc:postgresql://localhost:5432/dbname" />
        <property name="username" value="user" />
        <property name="password" value="password" />
        <property name="maxWait" value="15" />
        <property name="removeAbandonedTimeout" value="15" />
        <property name="defaultAutoCommit" value="false" />
    </bean>

You should define a dataSource, I use Tomcat Connection Pool, you can use the one you prefer.

Define the sqlSessionFactory:

    <!-- MyBatis config -->
    <bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">
        <property name="dataSource" ref="dataSource" />
    </bean>

Defina a mapper bean (the one with the methods and sql queries):

    <!-- MyBatis mappers -->
    <bean id="comercioMapper" class="org.mybatis.spring.mapper.MapperFactoryBean">
        <property name="mapperInterface" value="com.alex.mapper.SampleMapper" />
        <property name="sqlSessionFactory" ref="sqlSessionFactory" />
    </bean>

Create the Interface for com.alex.SampleMapper:

package com.alex.mapper;

@Service
public interface SampleMapper {
 // the code later
}

Create a sample POJO:

public class Sample {
 private Integer id;
 private String name;
 private Integer age;
 // getters / setters
}

Assume you have a table like:

CREATE TABLE sample (
 id SERIAL NOT NULL PRIMARY KEY,
 name VARCHAR(50) NOT NULL,
 age INT NOT NULL
);

Declare methods to Add / Update / Delete:

    @Insert( "INSERT INTO sample (name, age) VALUES ( #{s.name), #{s.age) )" )
    @Options(useGeneratedKeys = true, keyProperty = "s.id")
    void add(@Param("s") Sample s);

    @Delete( "DELETE FROM sample WHERE id = #{s.id)" )
    void delete(@Param("s") Sample s);

    @Update( "UPDATE sample SET name = #{s.name}, age = #{s.age} WHERE id = #{s.id}" )
    void update(@Param("s") Sample s);

    @Select( "SELECT * FROM sample WHERE id = #{id}" )
    Sample find(@Param("id") Integer id);

The important part here is the "add" method which will try to insert a new row in a table with auto generated keys, if succeed, the generated key will be stored in the id field of the stored object.

This is really good, but what about is your the fields in your object have different names of the table in the database?

For example:

public class Sample {
 Integer id;
 String theName;
 Integer age;
}

You have to tell MyBatis for handling "theName" field as "name" column:

    @Select( "SELECT * FROM sample WHERE id = #{id}" )
    @Results({
        @Result(property = "theName", column = "name")
    })
    Sample find(@Param("id") Integer id);

What about reading complex objects?

public class Sample {
 Integer id;
 Data data,
}

public class Data {
 String name;
 Integer age;
}

Is the same, can you see it?

    @Select( "SELECT * FROM sample WHERE id = #{id}" )
    @Results({
        @Result(property = "data.name", column = "name"),
        @Result(property = "data.age", column = "age")
    })
    Sample find(@Param("id") Integer id);

Have you heard about TypeHandler? What about it?

The objects:

public class Sample {
 Integer id;
 Other other;
}

public class Other {
 Integer id;
}

The table:

CREATE TABLE sample (
 id INT NOT NULL PRIMARY KEY,
 other_id INT NOT NULL
)

The mapper:

    @Select( "SELECT * FROM sample WHERE id = #{id}" )
    @Results({
        @Result(
          property = "other.id", column = "other_id", typeHandler = OtherTypeHandler.class
        )
    })
    Sample find(@Param("id") Integer id);

Define the TypeHandler:

public class OtherTypeHandler extends BaseTypeHandler<Other> {
    @Override
    public Other getNullableResult(ResultSet rs, String colName) throws SQLException {
        Other other = new Other();
        other.setId(rs.getInt(colName));
        return other;
    }

    @Override
    public Other getNullableResult(ResultSet rs, int colNum) throws SQLException {
        Other other = new Other();
        other.setId(rs.getInt(colNum));
        return other;
    }

    @Override
    public Other getNullableResult(CallableStatement cs, int colNum) throws SQLException {
        Other other = new Other();
        other.setId(cs.getInt(colNum));
        return other;
    }

    @Override
    public void setNonNullParameter(PreparedStatement ps, int i, Other t, JdbcType jt) throws SQLException {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
}

These are all the things I had needed using MyBatis, in the moment I needed I invest some time to find them, I put it here for using them if I forget them and hoping can be useful for you and save your time.

See you in the next post.
Posted by at No comments:
Labels:

Sunday, July 12, 2015

Java Geocoding using Google Maps Api

Java Server-Side Geocoding

I was developing a web app including a map and some markers in it, I got a decent database having many human readable addresses like "1600 Amphitheatre Parkway, Mountain View, CA", in order to put a marker in the map for a human readable address you need coordinates, Geocoding is the process of for converting human readable address into geographic coordinates (latitude, longitude).

My app is developed in Java using Google Maps, Google has a API for geocoding (https://developers.google.com/maps/documentation/geocoding/), the problem is, the API works for JavaScript only, you can find lots of examples for using it this way.

Google has a web service which can give you geocodes in json or xml, try this link: http://maps.googleapis.com/maps/api/geocode/json?address=california&sensor=false

Here we are requesting the location of "california".

Now make in it works in Java is not a hard taks, you need to write the necessary objects for representing the json structure and some a method to do a GET request and parse the json result into the Java object.

I will use Apache Http Components for doing the request and Jackson JSON Processor for parsing the request.

First, declare the requiered objects for the geocoding API (all of them should have getters and setters, DONT FORGUET TO PUT IT).

public class GoogleGeoCode {
    private String status;
    private GoogleGeoResult [] results;
    private Boolean exclude_from_slo;
    private String error_message;
}
 
public class GoogleGeoResult   {
    private GoogleGeoAdressComponent [] address_components;
    private String formatted_address;
    private GoogleGeoGeometry geometry;
    private Boolean partial_match;
    private String place_id;
    private String [] types;
}  

public class GoogleGeoAdressComponent {
    private String long_name;
    private String short_name;
    private String [] types;
}
 
public class GoogleGeoGeometry {
    private GoogleGeoBounds bounds;
    private GoogleGeoLatLng location;
    private String location_type;
    private GoogleGeoBounds viewport;
}
  
public class GoogleGeoBounds   {
    private GoogleGeoLatLng northeast;
    private GoogleGeoLatLng southwest;
}
 
public class GoogleGeoLatLng {
    private String lat;
    private String lng;
} 

Before doing the next I hope you had read the documentation of Google for geocoding, if not, reading it would help you to understand some things.

Google allows you to do geocoding without having an API_KEY but in most cases having it would be better, if you will use the API_KEY you should do the request using SSL (https), if you sent the KEY over HTTP, google will reject the request, the method works for BOTH (http and https):

/**
 * Given an address asks google for geocode
 *
 * If ssl is true API_KEY should be a valid developer key (given by google)
 *
 * @param address the address to find
 * @param ssl defines if ssl should be used
 * @return the GoogleGeoCode found
 * @throws Exception in case of any error
 *
 */
public GoogleGeoCode getGeoCode(String address, boolean ssl) throws Exception {
    // build url
    StringBuilder url = new StringBuilder("http");
    if ( ssl ) {
        url.append("s");
    }
  
    url.append("://maps.googleapis.com/maps/api/geocode/json?");
  
    if ( ssl ) {
        url.append("key=");
        url.append(API_KEY);
        url.append("&");
    }
    url.append("sensor=false&address=");
    url.append( URLEncoder.encode(address) );
  
    // request url like: http://maps.googleapis.com/maps/api/geocode/json?address=" + URLEncoder.encode(address) + "&sensor=false"
    // do request
    try (CloseableHttpClient httpclient = HttpClients.createDefault();) {
        HttpGet request = new HttpGet(url.toString());

        // set common headers (may useless)
        request.setHeader("User-Agent", "Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Firefox/31.0 Iceweasel/31.6.0");
        request.setHeader("Host", "maps.googleapis.com");
        request.setHeader("Connection", "keep-alive");
        request.setHeader("Accept-Language", "en-US,en;q=0.5");
        request.setHeader("Accept", "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8");
        request.setHeader("Accept-Encoding", "gzip, deflate");

        try (CloseableHttpResponse response = httpclient.execute(request)) {
            HttpEntity entity = response.getEntity();

            // recover String response (for debug purposes)
            StringBuilder result = new StringBuilder();
            try (BufferedReader in = new BufferedReader(new InputStreamReader(entity.getContent()))) {
                String inputLine;
                while ((inputLine = in.readLine()) != null) {
                    result.append(inputLine);
                    result.append("\n");
                }
            }

            // parse result
            ObjectMapper mapper = new ObjectMapper();
            GoogleGeoCode geocode = mapper.readValue(result.toString(), GoogleGeoCode.class);

            if (!"OK".equals(geocode.getStatus())) {
                if (geocode.getError_message() != null) {
                    throw new Exception(geocode.getError_message());
                }
                throw new Exception("Can not find geocode for: " + address);
            }
            return geocode;
        }
    }
}


HttpComponents and Jackson Parser made the job easier.

You may notice some request returns most than 1 result, in this case, what about for keeping the better one?

I define the better one as the result with the most similar address to the one requested (google gives you a formatted address for every result),

I used a simple approach for measuring this, the Longest Common Subsequence, the next method will help you to filter the results into the best one, I used in my app and seems to work really well.

/**
 * Given an address and google geocode find the most probable location of
 * address, the measure uses the longest common subsequence algorithm and a
 * minimum requirement for similarity
 *
 * @param address the original address
 * @param geocode the google geocode results
 * @return the most probable location (lat, lng), null if no one matches
 */
public GoogleGeoLatLng getMostProbableLocation(String address, GoogleGeoCode geocode) {
    address = address.toLowerCase();
    int expected = address.length() / 2;
    int sz = geocode.getResults().length;
    int best = expected;
    GoogleGeoLatLng latlng = null;
    for (GoogleGeoResult result : geocode.getResults()) {
        GoogleGeoLatLng cur = result.getGeometry().getLocation();
        String formattedAddress = result.getFormatted_address().toLowerCase();
        int p = lcs(address, formattedAddress);

        if (p > best) {
            latlng = cur;
            best = p;
        }
    }
    return latlng;
}



And the LCS method:

/**
 * The longest common subsequence of s and t using dynamic programming
 *
 * @param s the first string
 * @param t the second string
 * @return the length of the longest common subsequence
 */
private int lcs(String s, String t) {
    int N = s.length();
    int M = t.length();
    int[][] ans = new int[N + 1][M + 1];
    for (int k = N - 1; k >= 0; k--) {
        for (int m = M - 1; m >= 0; m--) {
            if (s.charAt(k) == t.charAt(m)) {
                ans[k][m] = 1 + ans[k + 1][m + 1];
            } else {
                ans[k][m] = Math.max(ans[k + 1][m], ans[k][m + 1]);
            }
        }
    }
    return ans[0][0];
}


I packet them into a simple class:

/**
 * Utils for Google geocoding api
 * 
 * @author Alexis Hernandez
 */
public class GoogleGeoUtils {
 public GoogleGeoCode getGeoCode(String address, boolean ssl); 
 public GoogleGeoLatLng getMostProbableLocation(String address, GoogleGeoCode geocode);
 private int lcs(String s, String t);
}


I may attach the sources later.

IMPORTANT NOTE: I used HttpClient 4.5 (the current latest version) but some previous versions have issues requesting google apis using SSL.


After I wrote the code I found a library which appears to do the work: https://code.google.com/p/geocoder-java/

If you want to, give it a try, I didn't tested.


I hope it can be useful for you, thanks for reading and see you in the next post.

Posted by at No comments:
Labels:

Saturday, July 4, 2015

Adafruitt FONA MiniGSM C Library for Raspberry Pi and similars

Adafruit FONA MiniGSM is a great product, you can learn more here, they wrote a library for Arduino which is found here.

If you buy this product and use it on Arduino, you will have not problems but what about if you need to do some complex needing a Raspberry Pi (RPi) or similar computer? Adafruit provide you a post for connecting FONA to a RPi here but has nothing for programming something.

When I bought FONA (like a year ago) I was in this situation, I wrote a small library in C which supports the most basic operations like send command and check command reply, I wrote a function to send SMS which basically use the previous functions, if you need more functions is not hard to extend the library.

The library is written in C and tested in Linux, it should work with most Linux distributions and with most SIMXXX chips working with AT commands.

I put a Main function as an example for using this library.

Note: This assume you have connected FONA to the port "/dev/ttyUSB0", be sure to change it if is not the case.

/**
 * source: http://stackoverflow.com/a/6947758/3211175
 *
 * Author: Alexis Hernandez
 *
 * gcc adafruit_fona_rpi.c -o fona -std=c99
**/

#include <errno.h>
#include <termios.h>
#include <unistd.h>
#include <stdio.h>

#include <signal.h>
#include <fcntl.h>
#include <features.h>
#include <string.h>

#ifndef CRTSCTS
#  ifdef CNEW_RTSCTS
#    define CRTSCTS CNEW_RTSCTS
#  else
#    define CRTSCTS 0x80000000
#  endif /* CNEW_RTSCTS */
#endif /* !CRTSCTS */

int set_interface_attribs(int fd, int speed, int parity)    {
        struct termios tty;
        memset(&tty, 0, sizeof tty);
        if ( tcgetattr(fd, &tty) !=  0 )    {
                printf("error %d from tcgetattr\n", errno);
                return -1;
        }

        cfsetospeed (&tty, speed);
        cfsetispeed (&tty, speed);

        tty.c_cflag = (tty.c_cflag & ~CSIZE) | CS8;     // 8-bit chars
        // disable IGNBRK for mismatched speed tests; otherwise receive break
        // as \000 chars
        tty.c_iflag &= ~IGNBRK;         // disable break processing
        tty.c_lflag = 0;                // no signaling chars, no echo,
                                        // no canonical processing
        tty.c_oflag = 0;                // no remapping, no delays
        tty.c_cc[VMIN]  = 0;            // read doesn't block
        tty.c_cc[VTIME] = 5;            // 0.5 seconds read timeout

        tty.c_iflag &= ~(IXON | IXOFF | IXANY); // shut off xon/xoff ctrl

        tty.c_cflag |= (CLOCAL | CREAD);// ignore modem controls,
                                        // enable reading
        tty.c_cflag &= ~(PARENB | PARODD);      // shut off parity
        tty.c_cflag |= parity;
        tty.c_cflag &= ~CSTOPB;
        tty.c_cflag &= ~CRTSCTS;

        if ( tcsetattr(fd, TCSANOW, &tty) != 0 )    {
                printf("error %d from tcsetattr", errno);
                return -1;
        }
        return 0;
}

void set_blocking(int fd, int should_block)    {
        struct termios tty;
        memset (&tty, 0, sizeof tty);
        if ( tcgetattr(fd, &tty) != 0 )    {
                printf("error %d from tggetattr", errno);
                return;
        }

        tty.c_cc[VMIN]  = should_block ? 1 : 0;
        tty.c_cc[VTIME] = 5;            // 0.5 seconds read timeout

        if ( tcsetattr(fd, TCSANOW, &tty) != 0 )    {
                printf("error %d setting term attributes", errno);
        }
}


int fd;    // file descriptor for connection
char buf [100];    // buffer for the reply

// init connection
int startConnection(char *portname)    {

    fd = open(portname, O_RDWR | O_NOCTTY | O_SYNC);
    if (fd < 0)    {
        printf("error %d opening %s: %s", errno, portname, strerror (errno));
        return 0;
    }

    set_interface_attribs(fd, B115200, 0);  // set speed to 115,200 bps, 8n1 (no parity)
    set_blocking(fd, 0);                // set no blocking
   
    //
    send("AT");
    usleep(100000);
   
    // turn off Echo!j
    send("ATE0");
    usleep(100000);
   
    return    sendCheckReply("ATE0", "OK");
}

void endConnection()    {
    close(fd);
}


// send a command to the serial port, read the answer but do nothing
int send(char *cmd)    {
//    printf("send: %s\n", cmd);
   
    int cmd_len = strlen(cmd);
    write( fd, cmd, cmd_len );                // send cmd
    write( fd, "\n", 1 );

    usleep ( (cmd_len + 10 + 25) * 300 );        // sleep enough to transmit the cmd plus
                                        // receive 25:  approx 100 uS per char
                                       
    int read_len = read(fd, buf, sizeof buf);  // read up to 100 characters if ready to read
   
    /*
    // print result
    printf(" read: %d bytes\n", read_len);
    for (int i = 0; i < read_len; i++)    printf( " %c", buf[i] );
    printf("\n");
    for (int i = 0; i < read_len; i++)    printf( " %d", buf[i] );
    printf("\n");
    */
   
    return 1;
}


/**
 * send cmd and checks device's reply match exact message
 * cmd and reply should ends with "cr+lf"
**/
int sendCheckReply(char *cmd, char *reply)    {

//    printf("sendCheckReply: %s\n", cmd);
    int cmd_len = strlen(cmd);
    write( fd, cmd, cmd_len );                // send cmd
    write( fd, "\n", 1 );

    usleep ( (cmd_len + 10 + 25) * 300 );        // sleep enough to transmit the cmd plus
                                        // receive 25:  approx 100 uS per char
                                       
    int read_len = read(fd, buf, sizeof buf);  // read up to 100 characters if ready to read
    // should return some like "\r\nxx\r\n", then avoid first 2 and last 2 bytes
   
    // print result
    /*
    printf(" read: %d bytes\n", read_len);
    for (int i = 0; i < read_len; i++)    printf( " %c", buf[i] );
    printf("\n");
    for (int i = 0; i < read_len; i++)    printf( " %d", buf[i] );
    printf("\n");
    */
   
    // strcmp
    int reply_idx = 0;
    int reply_len = strlen(reply);
    int read_idx = 2;
    read_len -= 2;
   
    for (; reply_idx < reply_len && read_idx < read_len && reply[reply_idx] == buf[read_idx]; reply_idx++, read_idx++);
   
    return    reply_idx == reply_len && read_idx == read_len ? 1 : 0;
}



/**
 * send cmd and checks device's reply is a prefix of response
**/
int sendCheckReplyPrefix(char *cmd, char *reply, int extraSleep)    {

    printf("sendCheckReplyPrefix: %s\n", cmd);
    int cmd_len = strlen(cmd);
    write( fd, cmd, cmd_len );                // send cmd
    write( fd, "\n", 1 );

    usleep ( (cmd_len + 10 + 25) * 300 );        // sleep enough to transmit the cmd plus
                                        // receive 25:  approx 100 uS per char
              
    if    ( extraSleep )
        usleep(extraSleep);
                       
    int read_len = read(fd, buf, sizeof buf);  // read up to 100 characters if ready to read
    // should return some like "\r\nxx\r\n", then avoid first 2 and last 2 bytes
   
    // print result
    printf(" read: %d bytes\n", read_len);
    for (int i = 0; i < read_len; i++)    printf( " %c", buf[i] );
    printf("\n");
    for (int i = 0; i < read_len; i++)    printf( " %d", buf[i] );
    printf("\n");
   
    // strcmp
    int reply_idx = 0;
    int reply_len = strlen(reply);
    int read_idx = 2;
   
    for (; reply_idx < reply_len && read_idx < read_len && reply[reply_idx] == buf[read_idx]; reply_idx++, read_idx++);
   
    return    reply_idx == reply_len ? 1 : 0;
}


// send smmmsg to smsaddr
int sendSMS(char *smsaddr, char *smsmsg) {
    if ( !sendCheckReply("AT+CMGF=1", "OK") )    {
        printf("fail: AT+CMGF=1\n");
        return 0;
    }
   
    // build send command like = AT+CMGS="nnnn"
    char sendcmd[30] = "AT+CMGS=\"";
    strncpy( sendcmd+9, smsaddr, 30-9-2); // 9 bytes beginning, 2 bytes for close quote + null
    sendcmd[ strlen(sendcmd) ] = '\"';
   
    printf("trying to send: %s\n", sendcmd);
   
    if ( !sendCheckReplyPrefix( &sendcmd[0], "> ", 0 ) )    {
        printf("fail: AT+CMGS=num\n");
        return 0;
    }
   
    // build msg command, append new line + ctrl+z
    char msgcmd [200];
    int msglen = strlen(smsmsg);
    strncpy(msgcmd, smsmsg, msglen);
    msgcmd[msglen] = '\n';
    msgcmd[msglen + 1] = 0x1A;
   
    return    sendCheckReplyPrefix( msgcmd, "+CMGS", 1000000 * 3 );
}








// main
int main()    {

    char *portname = "/dev/ttyUSB0";
   
    int attemps = 10;
    while    ( attemps-- &&    !startConnection(portname) )    usleep(1000);
   
    if    ( attemps <= 0 )    {
        printf( "ERROR: Can not start connection\n" );
        return    0;
    }
   
    printf("Connection started!\n");
   
    char *num = "0123456789";
    char *msg = "message here";
   
    if    ( sendSMS(num, msg) )    {
        printf("SMS sent\n");
    }    else    {
        printf("SMS can not be send\n");
    }
   
   
    printf("end\n");
   
    endConnection();
    return    0;
}





I hope this can be useful for you, be sure to ask any question.

Thanks for reading and see you in next post.
Posted by at No comments:
Labels: , , ,
Subscribe to: Posts (Atom)