Welcome again to my Code Jam analysis!

Today I am going to explain you Magic Trick (Problem A) from Qualification Round which took place in last Saturday. There is a link to description here.

So, this problem is quite simple, all you need to do is to calculate an intersection of two sets. If these sets are disjoint then you should output “Volunteer cheated!”.

If these sets have more than one common element then you should output “Bad magician!”. Otherwise, that is, if sets have exactly one common element then you should output that element.

I want to discuss implementation of solution this problem in different languages.

For example, Delphi has built-in type called Set and built-in operation * (multiplication star sign) to calculate intersection of two sets and your program could look like following

program MagicTrick;

{$APPTYPE CONSOLE}

{$R *.res}

uses

System.SysUtils;

var

f, g: TextFile;

answer: String;

T, a1, a2: Byte;

deck1, deck2: array[0..3, 0..3] of Byte;

procedure ReadData;

var

i, j: Byte;

begin

Readln(f, a1);

for i := 0 to 3 do begin

for j := 0 to 3 do

Read(f, deck1[i, j]);

Readln(f);

end;

Readln(f, a2);

for i := 0 to 3 do begin

for j := 0 to 3 do

Read(f, deck2[i, j]);

Readln(f);

end;

end;

type

TByteSet = Set Of Byte;

function len(s: TByteSet; out element: Byte): Byte;

var

i: Byte;

begin

Result := 0;

for i := 1 to 16 do

if i in s then begin

Inc( Result );

element := i;

end;

end;

procedure ProcessData;

var

i, e: Byte;

s1, s2, s: TByteSet;

begin

s1 := [];

s2 := [];

for i := 0 to 3 do

Include(s1, deck1[a1 – 1, i]);

for i := 0 to 3 do

Include(s2, deck2[a2 – 1, i]);

s := s1 * s2;

case len(s, e) of

1: answer := IntToStr(e);

0: answer := ‘Volunteer cheated!’;

else answer := ‘Bad magician!’;

end;

end;

procedure OutputVerdict(casenum: Word);

begin

writeln(g, ‘Case #’, casenum, ‘: ‘, answer);

end;

var

i: Word;

s, sout: String;

begin

try

s := ParamStr(1);

if (s = ”) then begin

s := ‘input.txt’;

sout := ‘output.txt’;

end else

sout := StringReplace(s, ExtractFileExt(s), ‘o.txt’, []);

AssignFile(f, s);

Reset(f);

AssignFile(g, sout);

Rewrite(g);

try

Readln(f, T);

for i := 1 to T do begin

ReadData;

ProcessData;

OutputVerdict(i);

end;

finally

CloseFile(f);

CloseFile(g);

end;

Readln;

except

on E: Exception do begin

Writeln(E.ClassName, ‘: ‘, E.Message);

readln;

end;

end;

end.

If you wanted to implement this on C++ then you would have to write more characters to calculate sets intersection like following

#include <iostream>

#include <fstream>

#include <string>

#include <algorithm>

#include <set>

#include <iterator>

using namespace std;

int a1, a2;

int deck1[4][4], deck2[4][4];

string solve() {

set<int> s1;

set<int> s2;

set<int> intersect;

for ( int i = 0; i < 4; i++)

s1.insert(deck1[a1 – 1][i]);

for ( int i = 0; i < 4; i++)

s2.insert(deck2[a2 – 1][i]);

set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::inserter(intersect,intersect.begin()));

switch (intersect.size()){

case 1:

return to_string(static_cast<long long>(*intersect.begin()));

break;

case 0:

return “Volunteer cheated!”;

break;

default:

return “Bad magician!”;

}

}

int main(int argc, char* argv[]) {

string inputFile = (argc > 1) ? argv[1] : “input.txt”;

string outputFile = (argc > 2) ? argv[2] : (argc > 1) ? (inputFile + “out.txt”) : “output.txt”;

ifstream in;

ofstream out;

in.open(inputFile);

out.open(outputFile);

int tests;

in >> tests;

for (int test = 1; test <= tests; ++test) {

out << “Case #” << test << “: “;

// Grab input

in >> a1;

for ( int i = 0; i < 4; i++ ) {

for ( int j = 0; j < 4; j++ ) {

in >> deck1[i][j];

}

}

in >> a2;

for ( int i = 0; i < 4; i++ ) {

for ( int j = 0; j < 4; j++ ) {

in >> deck2[i][j];

}

}

// Solve the problem and give feedback to the end user;

out << solve() << endl;

cerr << “: ” << test << endl;

}

in.close();

out.close();

cout << inputFile << ‘\n’ << outputFile << ‘\n’;

cin.get();

return 0;

}

As for me, it seems quite annoying that you have to write all of this stuff

set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::inserter(intersect,intersect.begin()));

to perform a simple set intersection operation. I used to put just some sign between two sets variable to get such result.

To perform a set intersection in Java you can call retainAll method on one set passing another set as argument, it will modify first source to contain intersection of both sets:

s1.retainAll(s2);

and the whole solution could look like following:

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.PrintWriter;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import java.util.logging.Level;

import java.util.logging.Logger;

public class pa {

private static int a1, a2;

private static int deck1[][], deck2[][];

public static void main(String[] args) {

String inputFile = (args.length > 0) ? args[0] : “input.txt”;

String outputFile = (args.length > 1) ? args[1] : (args.length > 0) ? (inputFile + “out.txt”) : “output.txt”;

try {

Scanner sc = new Scanner(new FileReader(inputFile));

PrintWriter pw = new PrintWriter(outputFile);

int n = sc.nextInt();

sc.nextLine();

for (int c=0; c<n; c++) {

Read(sc);

System.out.println(“Test case ” + (c+1) + “…”);

pw.print(“Case #” + (c+1) + “: “);

pw.print(solve());

pw.println();

}

pw.flush();

pw.close();

sc.close();

} catch (FileNotFoundException ex) {

Logger.getLogger(pa.class.getName()).log(Level.SEVERE, null, ex);

}

}

private static void Read(Scanner sc) {

a1 = sc.nextInt();

deck1 = new int[4][4];

deck2 = new int[4][4];

for ( int i = 0; i < 4; i++ ) {

for ( int j = 0; j < 4; j++ ) {

deck1[i][j] = sc.nextInt();

}

}

a2 = sc.nextInt();

for ( int i = 0; i < 4; i++ ) {

for ( int j = 0; j < 4; j++ ) {

deck2[i][j] = sc.nextInt();

}

}

}

private static String solve() {

Set<Integer> s1 = new HashSet<Integer>();

Set<Integer> s2 = new HashSet<Integer>();

for ( int i = 0; i < 4; i++)

s1.add(deck1[a1 – 1][i]);

for ( int i = 0; i < 4; i++)

s2.add(deck2[a2 – 1][i]);

s1.retainAll(s2);

switch (s1.size()) {

case 1:

return String.valueOf(s1.iterator().next());

case 0:

return “Volunteer cheated!”;

default:

return “Bad magician!”;

}

}

}

The language I enjoy the most is definitely Python. First, you can perform set intersection just using symbol “&”, it is pretty convenient and reminds Delphi usability. Second, the final code is incredibly short and elegant in comparison to any languages mentioned before in my post, just look at it:

import sys, copy;

a1, a2 = 0, 0

d1, d2 = [[]]*2

def solve():

s1 = set(d1[a1 – 1]);

s2 = set(d2[a2 – 1]);

s = s1 & s2

l = len(s)

return s.pop() if l == 1 else “Volunteer cheated!” if l == 0 else “Bad magician!”;

inputFile = sys.argv[1] if (len(sys.argv) > 1) else “input.txt”;

outputFile = sys.argv[2] if (len(sys.argv) > 2) else (inputFile + “out.txt”) if (len(sys.argv) > 1) else “output.txt”;

print inputFile, outputFile

file = open(outputFile, “w”)

with open(inputFile, ‘r’) as f:

t = int(f.readline())

print t

for i in range(1, t + 1):

file.write(“Case #” + str(i) + “: “)

a1 = int(f.readline())

print a1

d1 = [[0 for x in xrange(4)] for x in xrange(4)]

d2 = [[0 for x in xrange(4)] for x in xrange(4)]

for j in range(4):

d1[j] = map(int, f.readline().split())

print d1

a2 = int(f.readline())

print a2

for j in range(4):

d2[j] = map(int, f.readline().split())

print d2

file.write(str(solve()) + “\n”)

file.close()

Voila, the problem is solved in four languages. If we download test samples and pass it to our program and upload output files back to google site, it would say that “Judge’s response for last submission: Correct.”

Congratulations!

Hope you liked this post.