I was somewhat busy over the weekend. My wife and I were going to make some cannoli but for simplicity we decided to bake some chocolate cornetto. We are planning on making cannoli next weekend.
Last week I was reading the web page from Microsoft Dynamics 365 Connected Store. It uses video cameras and IoT devices to capture non-PII (Personally Identifiable Information) from customers that can be used by the store to improve service and increase sales. I spend time reading different related articles and watching YouTube videos. I am impressed with the approach to the subject by Microsoft. Most companies try to incorporate PII data but that may have many implications for the store, customer and the ability to offer the system to customers in different parts of the world due to local laws. I can go on and on but that would take us out of the topic for this post.
About a year or two ago I stopped by a Walgreens Pharmacy that is a few 
blocks away from where I live. While walking by the refrigerated section I noted cameras inside the units looking outwards and electronic displays on the prices of items inside the refrigerator. At the time I thought they were testing something and did not give it more thought. Around that time I also read an article on Communications of the ACM that described the goals of having cameras and other IoT devices to help manage a retail environment. I could not find the article on the ACM website.
I did a search using Google on the internet and the articles “Walgreens Tests Digital Cooler Doors With Cameras to Target You With Ads” and “Walgreens Testing Custom Digital Ads For Shoppers” came up. The article was published about a year ago. In that time many other ideas have come up to make refrigerators, and in general the entire store, more productive and appealing to customers.
On a separate topic (also outside the main topic for this post) there have been news that some people including the government of China and the WHO (World Health Organization) have been complaining about quarantines and cancelling flights to and from affected countries (i.e., China). We can discuss the subject of quarantines as long as we like, but they are effective in stopping the transmission of communicable diseases. That said, there is no reason to think less about the people that are being quarantined. It could well be you or me. Once the issue is resolved all things should go back to normal.
What seems to be happening is that some governments due to the side effects (less business) do not want to impose quarantines or to share information about what have they found, even if it is just simple statistics. That is bad news.
OK, enough is enough; let’s get to the subject of this post. I received a message from HackerRank inviting me to solve the Cipher challenge. If interested please take a look at the description.
The challenge contains several examples. The last one seems to be somewhat mangled.
7 4 1110101001 cipher <<< plain[0]: 1 cipher[0]: 1 cipher <<< plain[1]: 0 cipher[0]: 1 ^ cipher[1]: 1 cipher <<< plain[2]: 0 cipher[1]: 1 ^ cipher[2]: 1 cipher <<< plain[3]: 1 cipher[2]: 1 ^ cipher[3]: 0 cipher <<< plain[4]: 0 cipher[3]: 0 ^ cipher[4]: 1 ^ plain[0]: 1 cipher <<< plain[5]: 1 cipher[4]: 1 ^ cipher[5]: 0 ^ plain[1]: 0 cipher <<< plain[6]: 1 cipher[5]: 0 ^ cipher[6]: 1 ^ plain[2]: 0 1001011 7 4 1110100110 cipher <<< plain[0]: 1 cipher[0]: 1 cipher <<< plain[1]: 0 cipher[0]: 1 ^ cipher[1]: 1 cipher <<< plain[2]: 0 cipher[1]: 1 ^ cipher[2]: 1 cipher <<< plain[3]: 1 cipher[2]: 1 ^ cipher[3]: 0 cipher <<< plain[4]: 0 cipher[3]: 0 ^ cipher[4]: 1 ^ plain[0]: 1 cipher <<< plain[5]: 1 cipher[4]: 1 ^ cipher[5]: 0 ^ plain[1]: 0 cipher <<< plain[6]: 0 cipher[5]: 0 ^ cipher[6]: 0 ^ plain[2]: 0 1001010 6 2 1110001 cipher <<< plain[0]: 1 cipher[0]: 1 cipher <<< plain[1]: 0 cipher[0]: 1 ^ cipher[1]: 1 cipher <<< plain[2]: 1 cipher[1]: 1 ^ cipher[2]: 1 ^ plain[0]: 1 cipher <<< plain[3]: 1 cipher[2]: 1 ^ cipher[3]: 0 ^ plain[1]: 0 cipher <<< plain[4]: 1 cipher[3]: 0 ^ cipher[4]: 0 ^ plain[2]: 1 cipher <<< plain[5]: 1 cipher[4]: 0 ^ cipher[5]: 0 ^ plain[3]: 1 101111 10 3 1110011011 cipher <<< plain[0]: 1 cipher[0]: 1 cipher <<< plain[1]: 0 cipher[0]: 1 ^ cipher[1]: 1 cipher <<< plain[2]: 0 cipher[1]: 1 ^ cipher[2]: 1 cipher <<< plain[3]: 0 cipher[2]: 1 ^ cipher[3]: 0 ^ plain[0]: 1 cipher <<< plain[4]: 0 cipher[3]: 0 ^ cipher[4]: 0 ^ plain[1]: 0 cipher <<< plain[5]: 1 cipher[4]: 0 ^ cipher[5]: 1 ^ plain[2]: 0 cipher <<< plain[6]: 0 cipher[5]: 1 ^ cipher[6]: 1 ^ plain[3]: 0 cipher <<< plain[7]: 1 cipher[6]: 1 ^ cipher[7]: 0 ^ plain[4]: 0 10000101
The screen capture from the console of the Visual Studio Code IDE shows four samples. I took them from the HackerRank web page. I added some additional output so we can better understand what is going on. When I submitted my solution I commented them out. The solution should only return the plain text for the associated cipher.
The last sample on the web site shows 0010000101 but my code shows 10000101. That said; my solution passed all test cases.
The diagram illustrates example #1. We are provided the cipher string (bottom string) and the number of times the plain text is shifted once right while the encryption process was taking place. Of course, we would not be able to see the plain text. What we know is the length of the plain text (n) and the number of times it was shifted and XORed (k).
The first digit in the cipher matches the first digit in the plain text. The next 
few digits (3 in our example) seem that they could follow the same decryption process. Finally we would have to think how to process the rest (n – k) of the n digits. Note that the last three digits in the cipher do not seem to contribute to the decryption process.
Note than after we copy the first digit from the plain text, we can generate the next digit by using an XOR between the previous digit and the current one in the cipher text.
The last n – k digits in the plain text can be generated by using the XOR operation for the previous digit, the current one and a plain text digit.
// **** open scanner ****
private static final Scanner scanner = new Scanner(System.in);
/**
* Test scaffolidng.
*/
public static void main(String[] args) throws IOException {
// **** open buffered writer ****
// BufferedWriter bufferedWriter = new BufferedWriter(new
// FileWriter(System.getenv("OUTPUT_PATH")));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** read next line and split ****
String[] nk = scanner.nextLine().split(" ");
// **** extract binary values for n and k ****
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
// **** read the next line ****
String s = scanner.nextLine();
// **** ****
String result = cipher(k, s);
// **** display result ****
bufferedWriter.write(result);
bufferedWriter.newLine();
// **** close buffered writer ****
bufferedWriter.close();
// **** close scanner ****
scanner.close();
}
As usual I copy the test scaffolding and go over it making sure I understand how the data is being provided and how the key function is being called.
Seems like the data is collected and the cipher() function is called with the number of times the plain text is shifted and XORed and the string holding the cipher text.
/**
* Complete the cipher function below. Parse the cipher from left to right.
*/
static String cipher(int k, String s) {
// **** compute number of bits in plain text ****
int n = s.length() - k + 1;
// **** array to hold cipher and plain text ****
int[] cipher = new int[n];
int[] plain = new int[n];
// **** process the first n characters in the string ****
for (int i = 0; i < n; i++) {
// **** populate the cipher element ****
cipher[i] = s.charAt(i) - '0';
// **** compute the value for the plain text element ****
if (i == 0) {
plain[i] = cipher[i];
// ???? ????
System.out.println("cipher <<< plain[0]: " + plain[i] + " cipher[0]: " + cipher[i]);
} else if (i < k) {
plain[i] = cipher[i - 1] ^ cipher[i];
// ???? ????
System.out.println("cipher <<< plain[" + i + "]: " + plain[i] + " cipher[" + (i - 1) + "]: " + cipher[i - 1]
+ " ^ cipher[" + i + "]: " + cipher[i]);
} else {
plain[i] = cipher[i - 1] ^ cipher[i] ^ plain[i - k];
// ???? ????
System.out.println("cipher <<< plain[" + i + "]: " + plain[i] + " cipher[" + (i - 1) + "]: " + cipher[i - 1]
+ " ^ cipher[" + i + "]: " + cipher[i] + " ^ plain[" + (i - k) + "]: " + plain[i - k]);
}
}
// **** populate string builder with contents of the plain text array ****
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(plain[i]);
}
// **** return string with the plain text ****
return sb.toString();
}
We start by getting the number of bits in the plain text. We declare two arrays. The first is to hold part of the cipher and the second the plain text. We then enter a loop to extract the plain text.
As we recall, the first entry in the cipher matches the first digit in the plain text.
The next digits in the plain text may be obtained by using the XOR operation between the previous and the current cipher values.
For the last k digits we use the same XOR operation but add the first digits from the plain text.
Once the loop is done and the plain text is in the array we use a string builder to populate it with the values in the plain text array. The string representation of the string builder is returned.
Most of the time that I spent on this problem was figuring out how to generate the last digits in the plain text.
Please note that this encryption is useless. Encryption can not be backed up by secrecy. There is no security in this encryption mechanism.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa