CNF – Conjunctive Normal Form (Dimacs format) Explained

This post is just to explain the CNF DIMACS file format to people new to SAT

Boolean Operators
V – OR
^ – AND
¬ – NOT/Negation

Variable – can assume only values either 1 (true/ON)  or 0 (false/OFF)
Clause   – is the disjunction of a number of variables (negations may also be present)
A CNF expression is made up of conjunction of one or more clauses.

Every Satisfiability problem can be expressed in CNF (conjunctive normal form).

File Format

At the begining of the file there can exist one or more comment line.

comment lines start with a ‘c’

Example:

c This is a comment
c This is another comment

The following lines are information about the expression itself so an example expression is used to help understanding.
(A v ¬B v C) ^ (B v D v E) ^ (D V F)

After comments if any comes the  Problem line starts with a ‘p’

p FORMAT VARIABLES CLAUSES

FORMAT is for programs to detect which format is to be expected. Which should always be ‘cnf’

VARIABLES is the count of number of unique variables in the expression

A,B,C,D,E,F

VARIABLES = 6

CLAUSES is the number of clauses in the expression

(A v ¬B v C) ^ (B v D v E) ^ (D V F)
1             1           1        = 3

results to
p cnf 6 3

This line is followed by the information in each clause

unique variables are enumerated from 1 to n

A,B,C,D,E,F
1,2,3,4,5,6

such that
1 represents A
2 represents B
3 represents C
etc…

a negation is represented as ‘-‘

e.g.

-1 represents ¬A

Each variable information is seprated by a blank space

so

(A v ¬B v C)  is represented by 1 -2 3

Add a 0 behind to indicate the end of the clause

so

(A v ¬B v C)  is represented by 1 -2 3 0

(B v D v E)   is represented by 2 4 5 0

(D V F)       is represented by 4 6 0

The final File will be

c This is a comment
c This is another comment
p cnf 6 3
1 -2 3 0
2 4 5 0
4 6 0

Some Considerations
If you are building a parser
-the final 0 is sometimes ommited.

If you are building a SAT solver
-CNF is used just to have a common way of expressing the file format your SAT solver could transform the expression in another format for a different strategy.

Further Readings
http://en.wikipedia.org/wiki/Conjunctive_normal_form
http://www.domagoj-babic.com/uploads/ResearchProjects/Spear/dimacs-cnf.pdf
http://classes.soe.ucsc.edu/cmps132/Winter05/hw/hw8sols.pdf

Get Command prompt to Full Screen in Windows 7

Ever faced the situation where you required to copy text from a Command Prompt and ended up copying the text manually just because you bump at the dialog in Fig:1 when you attempt Alt+enter ?

This System does not support full screen mode
Fig:1

Here is the solution:

Right Click My computer (Either on the Desktop or in the Windows Menu)

Manage My Computer
Fig:2

Click Manage as shown in Fig:2

Click Device Manager (which can be found in the Computer Management on the left of the window)

Disable Display Adapter
Fig:3

Expand Display Adapters and right click and disable your Display Adapter  as shown in Fig:3 and click yes

Open the Command Prompt and press Alt+Enter and it should go full Screen

Known Issues:

  • Do not run anything in Admin mode or you may not proceed. ( If you happen to do it Alt+F4 till u can use the system again)
  • Only CMDs opened after Disabling Display Adapter are allowed to go full screen.

Send an SMS over My GO account programmatically using Ruby (Outdated)

Introduction

A couple of days ago I have posted an explanation of how to send SMS messages over My Go Account using c#. I have decided to do the same but this time using Ruby. I will not go in detail of how to since the explanation can be found here

Requirements:

  • GO Mobile phone line
  • My Go account for the phone line (Free for every GO Mobile phone)

Tools Used:

Setup

After installing ruby always update your gems

You will need Mechanize gem.

gem install mechanize

Code

So the following Ruby Class in gomobile.rb has one method just to send an SMS.

  1. require 'rubygems'
  2. require 'mechanize'
  3. class Gomobile
  4. def sendSMS(mobile_number,password,recipient,message)
  5. agent = Mechanize.new
  6. page = agent.get 'https://www.go.com.mt/mygo/'
  7. form = page.form('my_go_login')
  8. form.msisdn = mobile_number
  9. form.password = password
  10. form.actionx = 'authenticatemain'
  11. page = agent.submit form
  12. content = agent.get page
  13. page = agent.get 'https://www.go.com.mt/mygo/main_right.jsp'
  14. form = page.form('smsform')
  15. form.phone_entries = recipient
  16. form.smsInput = message
  17. form.message_template = ''
  18. len = 420 - message.length
  19. num_of_smses = 1;
  20. if len > 279
  21. num_of_smses = 1
  22. elsif len > 147
  23. num_of_smses = 2
  24. elsif len > 11
  25. num_of_smses = 3
  26. elsif len > 0
  27. num_of_smses = 4
  28. else
  29. raise Exception.new("You have exceeded the limit of 420 Characters")
  30. end
  31. form.count = len.to_s+'+%28'+num_of_smses.to_s+'+SMS%29'
  32. form.pentries = recipient
  33. page = agent.submit form
  34. content = agent.get page
  35. end
  36. end

Using the Class

  1. load 'gomobile.rb'
  2. g = Gomobile.new
  3. g.sendSMS("YOUR_NUMBER", "PASSWORD", "NUMBER_TO", "ACTUAL MESSAGE")

Known Issues:

Indentation in Ruby is important, so make sure you have it right.

If it fails to run swap
agent = Mechanize.new
with
agent = WWW::Mechanize.new

 

Send an SMS over My GO account programmatically using c# ( Outdated)

Introduction

As the title says this post describes how to send SMS messages from GO mobile website www.go.com.mt/mygo/  programmatically with C#.  This is for educational purposes only and I’m not affiliated in any way to GO. Use the contents of this page  at your own risk.

Requirements:

  • GO Mobile phone line
  • My Go account for the phone line (Free for every GO Mobile phone)

Tools Used:

Sending an SMS manually

Browse www.go.com.mt/mygo/

Go mobile login
Fig:1

To send an SMS  a user first has to login with his mobile number and password as shown in Fig:1

Go Sms form
Fig:2

If the login is successful the user is given access to the  form in Fig:2 that takes recipients and a maximum of 420 characters in an SMS. When finished typing the desired SMS click send SMS button.

How to achieve the above programmatically?

To send an SMS there are needed two POSTs, one for Login and the other for the actual SMS to be sent. So a method for sending a POST over HTTPS was created.

  1. public static void httpsPost(String uri, String post_data, String referer,  CookieContainer cookieC){
  2. HttpWebRequest request = (HttpWebRequest)WebRequest.Create(uri);
  3. request.ProtocolVersion = HttpVersion.Version11;
  4. request.Method = "POST";
  5. request.ContentType = "application/x-www-form-urlencoded";
  6. request.UserAgent = "Mozilla/5.0 (Windows NT 6.1; rv:5.0) Gecko/20100101 Firefox/5.0";
  7. request.Accept = "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8";
  8. request.KeepAlive = true;
  9. request.ReadWriteTimeout = 300;
  10. request.Referer = referer;
  11. request.CookieContainer = cookieC;
  12. byte[] postBytes = Encoding.ASCII.GetBytes(post_data);
  13. request.ContentLength = postBytes.Length;
  14. Stream requestStream = request.GetRequestStream();
  15. requestStream.Write(postBytes, 0, postBytes.Length);
  16. requestStream.Close();
  17. HttpWebResponse response = (HttpWebResponse)request.GetResponse();
  18. }

Parameters:

Uri – is the url the POST is sent.

Post_data – is the actual data that post will carry

Referrer – is the previous url the post request originated.

cookieC –keeps the cookie the Web Server sends to the browser  to maintain the Session state. This is so that to keep the program logged to your My Go account between login and sending a SMS message.

To make sure the Web Server sends the same HTML code that it sends to the Web Browser, the UserAgent is spoofed to the same as the Web Browser used in this case FireFox 5.

Login Form

  1. <form name="my_go_login" method="post" action="./servlet/authorisation">
  2. <input name="msisdn" class="login-screen" type="textbox">
  3. <input name="password" class="login-screen" type="password">
  4. <input type=hidden name=actionx value="authenticatemain">
  5. <INPUT class="login-button" TYPE="image" src="./images/login_screen/submit_button.jpg">
  6. </form>

Note:  the HTML code was cleared from irrelevant tags for clarity. The tags removed include table for formatting and client side validation on the form data.

From the HTML code at https://www.go.com.mt/mygo/  we investigate the login form.

referrer – https://www.go.com.mt/mygo/

url – https://www.go.com.mt/mygo/ servlet/authorisation

msisdn – mobile number to login with

password – the password for the account

actionx – a hidden input which is always set to the value “authenticatemain”

Send SMS form

  1. <form name="smsform" action="./servlet/groupsms" method="post">
  2. recipients:
  3. <input type="text" name="phone_entries" id="phone_entries"/>
  4. message:
  5. <textarea name="smsInput"></textarea>
  6. <input type="hidden" name="pentries" values=""/>
  7. characters left:
  8. <input readonly name="count" value="420 (0 SMS)">
  9. <input class="transparent" type="button" value="send SMS" onClick="submitsmsform()">
  10. </form>

This form is POSTed to the server by AJAX which requires more time to figure out what is really going on.

  1. //identifies browser being used and then connects to servelet to retrieve data
  2. function TxRxXML(inputText)
  3. {
  4. if(inputText != "" && inputText != "," && inputText != " ")
  5. {
  6. //if IE
  7. if(window.ActiveXObject)
  8. {
  9. request = new ActiveXObject("Microsoft.XMLHTTP");
  10. }
  11. //if other browsers
  12. else if(window.XMLHttpRequest)
  13. {
  14. request = new XMLHttpRequest();
  15. }
  16. //event handler that fires when the state of the page changes
  17. request.onreadystatechange = processRequestChange;
  18. request.open("POST", "./servlet/ajaxwebsms?rand=-4974711596692347436", true );
  19. request.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded');
  20. request.send("phone_entries=" + inputText);
  21. }
  22. return false;
  23. }

Development becomes easier with the use of Temper Data which empowers the developer to pause and inspect requests and their content. With some manual SMSes testing the query string was figured out.

url – https://www.go.com.mt/mygo/servlet/groupsms

referrer – https://www.go.com.mt/mygo/main_right.jsp

phone_entries – target mobile number

smsInput – url encoded message

message_template= left blank (not needed unless using the sms template facility)

count – Just a string that holds the number of characters left and in how many SMSes the message need to be split.

int len = 420 – message.Length; (message length is prior url encoding)
if (len > 279) num_of_smses = 1;
else if (len > 147) num_of_smses = 2;
else if (len > 11) num_of_smses = 3;
else if (len > 0) num_of_smses = 4;
count=” + len.ToString() + “+%28″+num_of_smses.ToString()+”+SMS%29&

save_message– save or not the message on the account (on/off)

pentries– target mobile number

So to Login and Send an SMS we get the following:

  1. public static void sendSms(String mobile_Number, String password, String recipient, String message)
  2. {
  3. CookieContainer myCookie = new CookieContainer();
  4. /* login */
  5. String url     = "https://www.go.com.mt/mygo/servlet/authorisation";
  6. String referer = "http://www.go.com.mt/mygo/";
  7. // Create Login Query String
  8. String vars = msisdn="+mobile_Number+"&password="+password+"&actionx=authenticatemain";
  9. // Login
  10. httpsPost(url, vars, referer, myCookie);
  11. /* send sms*/
  12. url = "https://www.go.com.mt/mygo/servlet/groupsms";
  13. referer = "https://www.go.com.mt/mygo/main_right.jsp";
  14. // 420 is the maximum number of characters that can be sent at once
  15. int len = 420 - message.Length;
  16. // apply URL Encoding to the message
  17. message = HttpUtility.UrlEncode(message);
  18. // Calculate the number of SMSes to be sent
  19. int num_of_smses = 1;
  20. if (len > 279) num_of_smses = 1;
  21. else if (len > 147) num_of_smses = 2;
  22. else if (len > 11) num_of_smses = 3;
  23. else if (len > 0) num_of_smses = 4;
  24. else throw new Exception("You have exceeded the limit of 420 Characters");
  25. // Create SMS Query string
  26. vars = "phone_entries=" + recipient + "%2C&smsInput="+message+"&message_template=&count=" + len.ToString() +"+%28"+num_of_smses.ToString()+"+SMS%29&save_message=on&pentries=" + recipient + "%2C";
  27. // Send SMS
  28. httpsPost(url, vars, referer, myCookie);
  29. }

Parameters:

mobile_number – the mobile number representing the account

password – password for the account

recipient – the number of the target mobile phone to receive the SMS

message – the actual SMS message in plain text

To make sure the Web Server sends the same HTML code to the application the UserAgent is set to the same as the Browser used in this case FireFox 5.

Test it

  1. static void Main(string[] args)
  2. {
  3. sendSms("YOUR_NUMBER", "PASSWORD", "NUMBER_TO", "ACTUAL MESSAGE");
  4. }

The code was tested in Visual Studio 2010 in a Console Application the Target Framework was changed to .NET Framework 4 as shown in Fig:3 so as to be able to include the reference to System.Web shown in fig:4.

Change to .net Framework 4
Fig:3
Add System.web reference to visual studio 2010
Fig:4

Make sure the following name spaces are included

  1. using System.Text;
  2. using System.Net;
  3. using System.IO;

Final note

If multiple SMS are to be sent, one could separate login from sending SMS but keep in mind that the session times out after being idle for some time.

What is not included:

Error Handling.

Message Templates.

An explanation of how to send to multiple recipients. This is left for the reader to try out. (probably just separate the numbers with coma)

How to access and retrieve My Go phone book and how to add entries to it programmatically.

Between login and sending an SMS from the website a real web browser sends some GET/POST requests for autocomplete mobile numbers in the phonebook stored in the account. These are skipped entirely.

Does not cater beyond the 8 free daily SMSes that require confirmation from the user to charge the account for the SMS.