Sunday, 26 July 2015

Panda and XOR problem at hackerearth with commentary

Log | Problem Solving >

Problem: Panda and XOR

URI for problem

https://www.hackerearth.com/tracks/pledge-2015-easy/panda-and-xor

Problem Statement (copied as it is, formatted)

Presently he has gone mad and he won’t stop performing XOR operation on various numbers.

Given an array of N numbers, for each subset of the array Little Panda
performs MAXOR operation for the subset. MAXOR operation means that he finds XOR of all elements in that subset (if the subset is [1,2,3]
then MAXOR is 1^2^3=0) .
Little Panda is now exhausted and wants to do something else. Little Panda wants to pick any two subsets the MAXOR of whose are same.
Little Panda needs to find the number of selections that he can make.
He is very very weak in programming so he wants the answer from you.

Since the output can be very large output it modulo 1000000007.

Input Format
The first line contains N i.e. the length of the array.
N lines follow, each containing a non-negative integer.

Output Format
Output Little Panda’s Query in a single line.

Constraints
1 <= N <= 100000
0 <= A[i] <= 100
where A[i] denotes the value of array element

Sample Input
3 1 2 3
Sample Output
3

Explanation

Little Panda can pick the subsets:
1. {1,3} and {2} whose MAXOR is 2.
2. {1,2} and {3} whose MAXOR is 3.
3. {2,3} and {1} whose MAXOR is 1.

Time Limit: 1 sec(s) for each input file. Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded if any testcase passes.
Allowed languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA,
JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP,
PYTHON, RUBY, R, RUST, SCALA

Problem Author: Akash Agrawall Problem
Tester: Deepankar Anil Kumar

Few problems with problem statement

There are a few problems with this problem statement:

• Input Format says that ‘N lines follow’, that’s not the case in the sample input.
• nothing to worry though;
• Empty sub-sets are not allowed; not mentioned.

Anyway, moving on to the solving problem.

I do not know how to solve this problem. No clue at all.

Well, then I moved to editorial. Poorly written editorial. I understand that a hacker mindset is behind all this, but clarity is elusive to the point that it might be an alien concept to the author at that time. Still maybe. Hackers don’t learn to code clearer until they stop hacking and think for a moment.

So, I am going to learn from the editorial and the given link and solve the problem myself, but first.

I found this code presented as the code that was used to solve the problem.

/*******************
Akash Agrawall
***********************/

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<functional>
#include<numeric>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define INF INT_MAX
#define ALL(x) x.begin(),x.end()
#define LET(x,a) __typeof(a) x(a)
#define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define EACH(it,v) IFOR(it,v.begin(),v.end())
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define fill(x,v) memset(x,v,sizeof(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define si(n) scanf("%d",&n)
#define pi(n) printf("%d ",n)
#define pd(n) printf("%lf ",n);
#define pdl(n) printf("%lf\n",n);
#define pin(n) printf("%d\n",n)
#define pln(n) printf("%lld\n",n)
#define pl(n) printf("%lld ",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
#define ll long long int
#define F first
#define S second
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;}
ll arr[100006],flagit[134],flg[134];
inline ll checkit(ll calc)
{
if(calc>=mod)
calc%=mod;
return calc;
}
inline ll chck(ll calc)
{
while(calc<0)
calc+=mod;
calc%=mod;
return calc;
}
int main()
{
ll n,calc,calc1,i,j,sz,c1,c2,ans=0;
sl(n);
rep(i,n)
{
sl(arr[i]);
}
rep(i,135)
flagit[i]=0;
rep(i,n)
{
rep(j,135)
flg[j]=0;
rep(j,129)
{
if(flagit[j]!=0)
{
calc=j^arr[i];
//printf("i=%d j=%d calc=%d\n",i,j,calc);
flg[calc]+=flagit[j];
flg[calc]=checkit(flg[calc]);
}
}
rep(j,129)
{
//printf("i=%d calc=%d calc1=%d\n",i,calc,calc1);
flagit[j]+=flg[j];
flagit[j]=checkit(flagit[j]);
}
flagit[arr[i]]++;
flagit[arr[i]]=checkit(flagit[arr[i]]);
}
c2=modpow(2,mod-2,mod);
//pln(c2);
rep(i,129)
{
//printf("i=%d flagit=%d\n",i,flagit[i]);
calc=flagit[i];
c1=calc*(calc-1);
c1=chck(c1);
c1=c1*c2;
c1=checkit(c1);
ans+=c1;
ans=checkit(ans);
}
pln(ans);
return 0;
}

Now, this code is hideous as shit. Poorly named macro to unused code. Hmm, I ought to clear the mess.

So I did clear the mess.

This is code looks like after a half hour clean up.

#include<iostream>
using namespace std;

#define MOD (int)(1e9 + 7)

long long int modpow(long long int a, long long int n, long long int temp)
{
long long int res = 1, y = a;
while (n > 0) {
if (n & 1){
res = (res*y) % temp;
}
y = (y*y) % temp;
n /= 2;
}
return res % temp;
}

long long int arr[100006], flagit[134], flg[134];

inline long long int chck(long long int calc)
{
while (calc < 0)
calc += MOD;
calc %= MOD;
return calc;
}

int main()
{
long long int n, calc, calc1, i, j, c1, c2, ans = 0;
scanf("%lld", &n);
for (i = 0; i < n; i++)
{
scanf("%lld", &arr[i]);
}
for (i = 0; i < 135; i++)
flagit[i] = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < 135; j++)
flg[j] = 0;
for (j = 0; j < 129; j++)
{
if (flagit[j] != 0)
{
calc = j^arr[i];
flg[calc] += flagit[j];
flg[calc] = flg[calc] % MOD;
}
}
for (j = 0; j < 129; j++)
{
flagit[j] += flg[j];
flagit[j] = flagit[j] % MOD;
}
flagit[arr[i]]++;
flagit[arr[i]] = flagit[arr[i]] % MOD;
}
c2 = modpow(2, MOD - 2, MOD);
for (i = 0; i < 129; i++)
{
calc = flagit[i];
c1 = calc*(calc - 1);
c1 = chck(c1);
c1 = c1*c2;
c1 = c1 % MOD;
ans += c1;
ans %= MOD;
}
printf("%lld\n", ans);
return 0;
}

Looks almost half the lines now.

These many include directives deleted.

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<functional>
#include<numeric>

That’s just too many.

There are other things that I have deleted like unused macros etc.

I can refactor more. Wait I’ll show you the refactored code. No tests though.

[This is a live post. Timestamp: 11:22 July 27, 2015]

Okay, at 11:51 AM, after half an hour of refactoring and making sure that code works, here’s my submission.

Refactored code

#include<iostream>
using namespace std;

#define MOD (int)(1e9 + 7)

long long int CalculateC2(long long int a, long long int n, long long int temp)
{
long long int res = 1, y = a;
while (n > 0) {
if (n & 1){
res = (res*y) % temp;
}
y = (y*y) % temp;
n /= 2;
}
return res % temp;
}

long long int arr[100006], flagit[134], flg[134];

inline long long int Sanitize(long long int calc)
{
while (calc < 0)
calc += MOD;
calc %= MOD;
return calc;
}

long long int GetInputs(){
long long int numberOfInputs, i;

scanf("%lld", &numberOfInputs);
for (i = 0; i < numberOfInputs; i++)
{
scanf("%lld", &arr[i]);
}
return numberOfInputs;
}

void SetArrayToZero(long long int arr[], long long int count)
{
long long int i = 0;
for (i = 0; i < count; i++) {
arr[i] = 0;
}
}

long long int CalculateC1(long long int index, long long int c2)
{
long long int c1 = Sanitize(flagit[index] * (flagit[index] - 1));
return (c1*c2) % MOD;
}

long long int CalculateNumberOfSetsWithEqualXOR(void)
{
long long int i = 0, ans = 0, c2 = CalculateC2(2, MOD - 2, MOD);

for (i = 0; i < 129; i++)
{
ans = (ans + CalculateC1(i, c2)) % MOD;
}
return ans;
}

void ProcessInput(long long int i)
{
long long int j = 0, calc = 0;

SetArrayToZero(flg, 135);
for (j = 0; j < 129; j++)
{
if (flagit[j] != 0)
{
calc = j^arr[i];
flg[calc] += flagit[j];
flg[calc] = flg[calc] % MOD;
}
}
for (j = 0; j < 129; j++)
{
flagit[j] += flg[j];
flagit[j] = flagit[j] % MOD;
}
flagit[arr[i]]++;
flagit[arr[i]] = flagit[arr[i]] % MOD;
}

void ProcessAllInputs(long long int numberOfInputs)
{
long long int i = 0;
for (i = 0; i < numberOfInputs; i++)
{
ProcessInput(i);
}
}

long long int CalculateNumberOfMatchingXORSets(){
long long int numberOfInputs = GetInputs();
SetArrayToZero(flagit, 135);
ProcessAllInputs(numberOfInputs);
return CalculateNumberOfSetsWithEqualXOR();
}

int main()
{
long long int numberOfMatchingXORSets = CalculateNumberOfMatchingXORSets();
printf("%lld\n", numberOfMatchingXORSets);
return 0;
}

Notice that I have created a ton of functions and broke the code in little pieces. I have not renamed much variables or functions. I’ll tell you why? It was really a bad piece of code.

When you write code, other should be able to read and understand the problem that you are trying to solve. Disclaimer: I have been guilty of writing unreadable code. I strive to clean the code as much as possible these days,

Anyway, still do not understand the code or problem or solution. Going to read up on it.

11:55 AM.

Come to think about it, this code is C code. Hmm. Also, I am going to rename the long long int to HugeInt via define directive.

Let me check if it works.

Yes it does! It’s C code.

So this was another thing that was wrong; but this time with the given code.

Now, I want to convert this code to C#.

So here’s the C# code.

C#

using System;

namespace HackerEarthProblemSolving
{
class PandaAndXorSolution
{
long MOD =  (long)(1e9 + 7);
long [] arr = new long[100006];
long [] flagit = new long[134];
long [] flg = new long[134];

long CalculateC2(long a, long n, long temp)
{
long res = 1, y = a;
while (n > 0) {
if (n % 2 == 1){
res = (res*y) % temp;
}
y = (y*y) % temp;
n /= 2;
}
return res % temp;
}

long Sanitize(long calc)
{
while (calc < 0)
calc += MOD;
calc %= MOD;
return calc;
}

long GetInputs(){

for (long i = 0; i < numberOfInputs; i++)
{
}
return numberOfInputs;
}

void SetArrayToZero(long [] arr)
{
for (long i = 0; i < arr.Length; i++)
arr[i] = 0;
}

long CalculateC1(long index, long c2)
{
long c1 = Sanitize(flagit[index] * (flagit[index] - 1));
return (c1*c2) % MOD;
}

long CalculateNumberOfSetsWithEqualXOR()
{
long i = 0, ans = 0, c2 = CalculateC2(2, MOD - 2, MOD);

for (i = 0; i < 129; i++)
{
ans = (ans + CalculateC1(i, c2)) % MOD;
}
return ans;
}

void ProcessInput(long i)
{
SetArrayToZero(flg);
for (long j = 0; j < 129; j++)
{
if (flagit[j] != 0)
{
long calc = j^arr[i];
flg[calc] += flagit[j];
flg[calc] = flg[calc] % MOD;
}
}
for (long j = 0; j < 129; j++)
{
flagit[j] += flg[j];
flagit[j] = flagit[j] % MOD;
}
flagit[arr[i]]++;
flagit[arr[i]] = flagit[arr[i]] % MOD;
}

void ProcessAllInputs(long numberOfInputs)
{
for (long i = 0; i < numberOfInputs; i++)
{
ProcessInput(i);
}
}

long CalculateNumberOfMatchingXORSets(){
long numberOfInputs = GetInputs();
SetArrayToZero(flagit);
ProcessAllInputs(numberOfInputs);
return CalculateNumberOfSetsWithEqualXOR();
}

public long Solve()
{
return CalculateNumberOfMatchingXORSets();
}

}
class PandaAndXorRunner
{
static void Main(){
PandaAndXorSolution paxs = new PandaAndXorSolution();
Console.WriteLine(paxs.Solve());
}
}
}

So, C# is done.

[Next Day - 7:40 AM 7/28/2015]

Today I am going to solve the problem on my own in C# first. I am going to use the logic provided in the editorial.

Logic provided in Editorial

freq[]={0} //initially

for i = 1 to n //Traversing the array:
temp[] = {0}

for j = 0 to 127
//Finding the values which are computed as MAXOR of some subset:
if freq[j] not equal to 0:
//Means this value is computed as MAXOR of some subset
//Now arr[i] can also be XORed with it
temp[j^arr[i]]+=freq[j]

for j = 0 to 127
freq[j]+=temp[j]

freq[arr[i]] += 1

Let’s see how it comes out.

I have understood problem:

So, for those who haven’t got the problem or who are new to the
problem, the problem boils down to two statements.

1) Find the XOR of every element in every subset for a given set; except null and set itself.

example: For a given set {1, 2, 3}: Calculate XOR of {1}, {1, 2}, {1,
3}, {2}, {2, 3}, {3}. {1} = 1; {2} = 2; {3} = 3; {1, 2} = 3; {2, 3} =
1; {1, 3} = 2;

2) Then find the number of ways you can pick two such subsets that their XOR values are equal.

example:
(continuing from above)
Now, pick two subsets:
{1} and {2, 3} = 1 way to pick.
{2} and {1, 3} = 1 way to pick.
{3} and {1, 2} = 1 way to pick.

Total ways: 3. And that’s the answer.

I’ll try to solve the problem myself next month. This problem is reflection of the reason why I hate online code submission platforms.

Simple program >

How to scan an integer from standard input and print if the number is even or odd?

C

#include <stdio.h>

int main()
{
int number = 0;
if(scanf("%i", &number)==1){
printf("%s", number%2 ? "Odd" : "Even");
}
return 0;
}

C#

using System;
class MyClass {
static void Main(string[] args) {
var output = i % 2 == 0 ? "Even" : "Odd";
Console.WriteLine(output);
}
}

C

#include <stdio.h>
#define ODD "Odd"
#define EVEN "Even"

int main()
{
int numberOfInputs = -1;
int currentInput = -1;
if(scanf("%i", &numberOfInputs)==1){
while(numberOfInputs-- != 0){
if(scanf("%i", &currentInput)==1){
printf("%s\n", currentInput % 2 ? ODD : EVEN);
}
}
}
return 0;
}

C#

using System;

class MyClass {
static string ODD = "Odd";
static string EVEN = "Even";

static void Main(string[] args) {
for(int i = 0; i < count; ++i){
PrintEvenOrOdd(num);
}
}
static void PrintEvenOrOdd(int num){
var output = num % 2 == 0 ? EVEN : ODD;
Console.WriteLine(output);
}
}

Simple program >

How to scan for an integer from standard input and print the same?

C

#include <stdio.h>

int main()
{
int number = 0;
if(scanf("%i", &number)==1){
printf("%i", number);
}
return 0;
}

C#

using System;
class MyClass {
static void Main(string[] args) {
Console.WriteLine(i);
}
}

That’s all!

Saturday, 25 July 2015

Check if a given integer is Even or Odd

Simple programs >

Check if a given integer is Even or Odd

There is nothing much to it. In computer programming, ‘%’ holds a very good value of providing remainder.

2 % 2 is 0
3 % 2 is 1
7 % 2 is 1
7 % 3 is 1
7 % 4 is 3
7 % 5 is 2
7 % 6 is 1
7 % 7 is 0

Well, that’s the logic. This logic is generally applicable on integer values only.

For example it doesn’t make any sense to divide a real number with other number to find remainder, since real number has digits after decimal.

10.10 % 2 might actually be an error

Right now I am guessing, we will come to know soon.

So let’s see the code.

C

int isEven ( number )
{
return number % 2 == 0;
}

That’s pretty much it.

Logic here is that:
1. given a number, when we divide it by 2, if it divides it completely i.e. remainder is zero, then it is even number.
2. else, the remainder will be one and thus an odd number.

Let’s look at some tests.

void test_manual_isEven ( )
{
printf("\n444 is : %s.", isEven(444) == 1 ? "even" : "odd");

printf("\n445 is : %s.", isEven(445) == 1 ? "even" : "odd");
}

void test_auto_isEven ( )
{
int number = 444;

if ( 1 == isEven(number) )
printf("\nTest #1 passed. %d is even.", number);

if ( 0 == isEven(number+1))
printf("\nTest #2 passed. %d is odd.", number+1);
}

The fact that isEven function checks for remainder equal to 0 for even numbers but we are checking for 1 as the isEven function return value for even number might be confusing you.

So, even_number divided by 2 = remainder is 0.
We return from isEven function 1 due to conditional check.
If remainder is equal to 0, then return true value, which happens to be 1 by default in C.
If remainder is equal to 1, then return false value, which happens to be 0 by default in C.

Online code.

JavaScript

var isEven = function ( number )
{
return parseInt(number) % 2 === 0 ? 1 : 0;
}

Well, that’s all you need to write a isEven function in JavaScript. However, notice that I am converting input number to integer specifically by calling parseInt function.

var number = 10;
isEven(number);
1
isEven(number+1);
0

0 signifies false, 1 signifies true. It’s like asking computer, is number 10 even?

If I do not use parseInt, then any real number can be sent and the result always will be 0. Check for your self.

python

>>> def isEven (number):
return int(number) % 2 == 0;

>>> isEven(19)
False
>>> isEven(20)
True

There is nothing much to discuss here. We are casting number to integer so that at least the non decimal part can be tested for evenality.

Fair warning: This is bad code. isEven(19.19) returns False because casting to integer makes it equivalent to isEven(19). Bad bad coding.

ruby

Since the logic is same, I will concentrate on the fact that the way to convert another number to integer in ruby is via .to_i.

This is by the way, my first ever function in ruby language.

irb(main):013:0> def isEven ( number )
irb(main):014:1>     return number.to_i % 2 == 0;
irb(main):015:1* end
=> :isEven
irb(main):016:0> isEven(18)
=> true
irb(main):017:0> isEven(19)
=> false
irb(main):018:0> isEven(19.19)
=> false
irb(main):019:0> isEven(192.19)
=> true
irb(main):020:0>

Ruby-cherry popped!!!

C#

C# is an (allegedly) object oriented language. [Note: I call languages like C#, Java, C++: POO. Yes! Poo. Pseudo Object Oriented languages.]

We need classes and a lot of boiler plate to get things done. If you look at the isEven function though, it is not different at all. It is similar to C, different from Ruby and Python and JavaScript.

using System;

public class Test
{
public static void Main()
{
Test t = new Test();

Console.WriteLine("isEven(10) : {0}, isEven(11) : {1}.", t.isEven(10), t.isEven(11));
}

bool isEven(int number)
{
return number % 2 == 0;
}

}

Code here.

F#

Though I have tried to learn F# (fruitlessly) before, this is actually my first function in F# too.

open System

let isEven x = (x % 2) = (0)

printfn "%b" (isEven 19)
printfn "%b" (isEven 20)

= symbol in F# simply means == in C# or ===in JavaScript.
printfn prints a new line at the end.

Code.

More ways to calculate evenality.

I hid from you a few more ways to find if a given number is even or odd.

Divide multiply logic.

Logic #1

Divide the given number by 2 and then multiply by 2 and check if
resultant number is equal to the given number.
If equal: Even number.
If not equal: Odd number.

10 / 2 is 5. 5 * 2 is 10.
10 is equal to 10.

11 / 2 is 5. 5 * 2 is 10.
10 is not equal to 11.

This logic will work in C, C#, Java kind of languages, but not in
python, JavaScript type of language that convert numbers to real
numbers as soon as they get chance. Of course you can use parseInt and
related functions, but we are already doing that in other logic.

Now we move towards another logic.

0th bit check.

Logic #2

Check if the zero-th bit of the given number is one or not.

number & 1 == 1 will return true for odd numbers and false for even
numbers.

say we use only first nibble.

4 is 0100.
The zero-th bit is 0. (right hand side)

3 is 0011.
0th bit is 1.

2 is 0010. (0th bit is 0) 1 is 0001. (0th bit is 1)

Well that was all about even and odd numbers.

Log > Rant >

I have always thought that I kill computers.

Well, no. There are other people too. One such is Zed A. Shaw and he says so here: I Can Kill Any Computer.

I do not want to go into my killing computers or how software makes me suicidal almost every time. Don’t have enough time left on Earth.

Every Mac I’ve owned has tanked in the first week and needed repairs
or replacing. Hard drives freeze up.

And then he continues:

It happens so often friends don’t believe me. There’s no way anyone
has those problems. I do. All the time.

Well good sir, I believe you!

JavaScript #21 - Variable hoisting in JavaScript

JavaScript > 1000 things about JavaScript >

JavaScript #21 - Example of variable hoisting in JavaScript.

function f(){
for(var i = 0; i < 10; i++){
var x;
x += i;
console.log(x);
}
}

is exactly same to following function as far as JavaScript parser is concerned:

function g(){
var i;
var x;
for(i = 0; i < 10; i++){
x += i;
console.log(x);
}
}

So put your variable declarations on top of the function.

function h(){
var i;
var x;
for(i = 0, x  = 0; i < 10; i++){
x += i;
console.log(x);
}
}

JavaScript >

I came accross a

Martin Rinehart’s comment that explains JavaScript succinctly.

There he says:

In JavaScript you can create, modify and delete objects.

Modifying objects includes creating, modifying and deleting properties.

Modifying properties includes changing their names and their values.

Values include data and code.

Done. This is the best comment ever on JavaScript or on a programming paradigm. Hats Off Sir, Hats Off!