Google Codejam Qualification Round 2014 / War

war.ll

%char = type i8
%int = type i32

@casef = internal constant [17 x %char] c"Case #%d: %d %d\0A\00"
@finf = internal constant [3 x %char] c"%f\00"
@dinf = internal constant [3 x %char] c"%d\00"
@doutf = internal constant [4 x %char] c"%d\0A\00"
@foutf = internal constant [4 x %char] c"%f\0A\00"

declare %int @printf(%char* noalias nocapture, ...)
declare %int @scanf(%char* noalias nocapture, ...)
declare i8* @calloc(i64, i64)

define void @readInt(%int* %ptr) {
	call %int (%char*, ...)* @scanf(%char* getelementptr ([3 x %char]* @dinf, %int 0, %int 0), %int* %ptr)
	ret void
}


define void @readFloat(float* %ptr) {
	call %int (%char*, ...)* @scanf(%char* getelementptr ([3 x %char]* @finf, %int 0, %int 0), float* %ptr)
	ret void
}

define void @printInt(%int %v) {
	call %int (%char*, ...)* @printf(%char* getelementptr ([4 x %char]* @doutf, %int 0, %int 0), %int %v)
	ret void
}

define void @printFloat(float %f) {
	%d = fpext float %f to double
	call %int (%char*, ...)* @printf(%char* getelementptr ([4 x %char]* @foutf, %int 0, %int 0), double %d)
	ret void
}

define float* @getArrPtr(i8* %arr, i64 %i) {
	%x = ptrtoint i8* %arr to i64
	%y = mul i64 %i, 8
	%z = add i64 %x, %y
	%w = inttoptr i64 %z to float*
	ret float* %w
}

define float @getValue(i8* %arr, %int %i) {
	%j = zext %int %i to i64
	%fp = call float* @getArrPtr(i8* %arr, i64 %j)
	%f = load float* %fp
	ret float %f
}

define %int @getOriginalScore(i8* %naomi, i8* %ken, %int %size) {
init:
	br label %loop.head
loop.head:
	%ni = phi %int [0, %init], [%ni.next, %loop.cond.other]
	%ki = phi %int [0, %init], [%ki.next, %loop.cond.other]
	%cond.h1 = icmp ugt %int %size, %ki
	%cond.h2 = icmp ugt %int %size, %ni
	%cond.h = and i1 %cond.h1, %cond.h2
	br i1 %cond.h, label %loop.body, label %loop.after
loop.body:
	%f.n = call float @getValue(i8* %naomi, %int %ni)
	%f.k = call float @getValue(i8* %ken, %int %ki)
	%comp.f = fcmp ogt float %f.n, %f.k
	br i1 %comp.f, label %loop.cond.other, label %loop.cond.nope
loop.cond.nope:
	%ni.next.inc = add %int %ni, 1
	br label %loop.cond.other
loop.cond.other:
	%ni.next = phi %int [%ni, %loop.body], [%ni.next.inc, %loop.cond.nope]
	%ki.next = add %int %ki, 1
	br label %loop.head
loop.after:
	%comp.v = icmp ult %int %ni, %ki
	br i1 %comp.v, label %exit.calc, label %exit.none
exit.calc:
	%result = sub %int %ki, %ni
	ret %int %result
exit.none:
	ret %int 0
}

define %int @getDeceitfulScore(i8* %naomi, i8* %ken, %int %size) {
init:
	br label %loop.main
loop.main:
	%result = phi %int [0, %init], [%result.next, %loop.gomain]
	%ks = phi %int [0, %init], [%ks.next, %loop.gomain]
	%i = phi %int [0, %init], [%i.next, %loop.gomain]
	%comp.loop = icmp ult %int %i, %size
	br i1 %comp.loop, label %loop.body, label %loop.after
loop.body:
	%naomi.v = call float @getValue(i8* %naomi, %int %i)
	%ken.v = call float @getValue(i8* %ken, %int %ks)
	%comp.main = fcmp olt float %naomi.v, %ken.v
	br i1 %comp.main, label %loop.gomain, label %loop.cond.bigger
loop.cond.bigger:
	%result.next.inc = add %int %result, 1
	%ks.next.inc = add %int %ks, 1
	br label %loop.gomain
loop.gomain:
	%result.next = phi %int [%result, %loop.body], [%result.next.inc, %loop.cond.bigger]
	%ks.next = phi %int [%ks, %loop.body], [%ks.next.inc, %loop.cond.bigger]
	%i.next = add %int %i, 1
	br label %loop.main
loop.after:
	ret %int %result
}

define void @sort(i8* %arr, %int %size) {
init:
	%comp.size1 = icmp ule %int %size, 1
	br i1 %comp.size1, label %exit, label %outer_loop
outer_loop:
	%i = phi %int [1, %init], [%i.next, %inner_loop.after]
	br label %inner_loop
inner_loop:
	%j = phi %int [%i, %outer_loop], [%j.next, %inner_loop_swap]
	%j.next = sub %int %j, 1
	%j.64 = zext %int %j to i64
	%j.next.64 = zext %int %j.next to i64
	%fj.a = call float* @getArrPtr(i8* %arr, i64 %j.64)
	%fj.b = call float* @getArrPtr(i8* %arr, i64 %j.next.64)
	%f.a = load float* %fj.a
	%f.b = load float* %fj.b
	%comp.f = fcmp olt float %f.b, %f.a
	br i1 %comp.f, label %inner_loop.after, label %inner_loop_swap
inner_loop_swap:
	store float %f.b, float* %fj.a
	store float %f.a, float* %fj.b
	%comp.j = icmp sgt %int %j.next, 0
	br i1 %comp.j, label %inner_loop, label %inner_loop.after
inner_loop.after:
	%i.next = add %int %i, 1
	%comp.i = icmp ult %int %i.next, %size
	br i1 %comp.i, label %outer_loop, label %outer_loop.after
outer_loop.after:
	br label %exit
exit:
	ret void
}

define %int @main() {
init:
	%T.mem = alloca %int
	%N.mem = alloca %int
	call void @readInt(%int* %T.mem)
	%T = load %int* %T.mem
	br label %tc_loop
tc_loop:
	%ti = phi %int [1, %init], [%ti.next, %read_loop.after]
	call void @readInt(%int* %N.mem)
	%N = load %int* %N.mem
	%N.64 = zext %int %N to i64
	%naomi = call i8* @calloc(i64 %N.64, i64 8)
	%ken = call i8* @calloc(i64 %N.64, i64 8)
	%naomi.addr = ptrtoint i8* %naomi to i64
	%ken.addr = ptrtoint i8* %naomi to i64
	br label %read_loop.1
	; Read two arrays
read_loop.1:
	%n.1 = phi %int [0, %tc_loop], [%n.1.next, %read_loop.1]
	%naomi.ri.64 = zext %int %n.1 to i64
	%naomi.fp = call float* @getArrPtr(i8* %naomi, i64 %naomi.ri.64)
	call void @readFloat(float* %naomi.fp)
	%n.1.next = add %int %n.1, 1
	%cond.n.1 = icmp ult %int %n.1.next, %N
	br i1 %cond.n.1, label %read_loop.1, label %read_loop.2
read_loop.2:
	%n.2 = phi %int [0, %read_loop.1], [%n.2.next, %read_loop.2]
	%ken.ri.64 = zext %int %n.2 to i64
	%ken.fp = call float* @getArrPtr(i8* %ken, i64 %ken.ri.64)
	call void @readFloat(float* %ken.fp)
	%n.2.next = add %int %n.2, 1
	%cond.n.2 = icmp ult %int %n.2.next, %N
	br i1 %cond.n.2, label %read_loop.2, label %read_loop.after
read_loop.after:
	; Compute results
	call void @sort(i8* %naomi, %int %N)
	call void @sort(i8* %ken, %int %N)
	%result.a = call %int @getOriginalScore(i8* %naomi, i8* %ken, %int %N)
	%result.b = call %int @getDeceitfulScore(i8* %naomi, i8* %ken, %int %N)
	; Print results
	call %int (%char*, ...)* @printf(%char* getelementptr ([17 x %char]* @casef, %int 0, %int 0), %int %ti, %int %result.b, %int %result.a)
	; Condition checking (outer loop)
	%ti.next = add %int %ti, 1
	%cond.t = icmp ule %int %ti.next, %T
	br i1 %cond.t, label %tc_loop, label %exit
exit:
	ret %int 0
}

war.sh

#!/usr/bin/env bash

read T
for (( ti=1; ti<=$T; ti++ ))
do
	read N
	read -a naomi
	read -a ken
	PIFS=$IFS
	IFS=$'\n'
	naomi=($(printf '%s\n' "${naomi[@]}" | sort))
	ken=($(printf '%s\n' "${ken[@]}" | sort))
	IFS=$PIFS
	# Compute original score
	fair=0
	ni=0
	ki=0
	while [ $N -gt $ki -a $N -gt $ni ]
	do
		cmp=$(echo ${naomi[$ni]}'>'${ken[$ki]} | bc -l)
		if [ $cmp -eq 1 ]
		then
			ki=$(($ki + 1))
		else
			ni=$(($ni + 1))
			ki=$(($ki + 1))
		fi
	done
	if [ $ni -lt $ki ]
	then
		fair=$(($ki - $ni))
	fi
	#Compute score when Naomi cheats
	nofair=0
	ks=0
	kl=$(($N-1))
	for (( i=0; i<$N; i++ ))
	do
		if [ $ks -eq $kl ]
		then
			# The last one
			cmp=$(echo ${naomi[$i]}'>'${ken[$kl]} | bc -l)
			if [ $cmp -eq 1 ]
			then
				nofair=$(($nofair + 1)) 
			fi
			break
		else
			cmp=$(echo ${naomi[$i]}'<'${ken[$ks]} | bc -l)
			if [ $cmp -eq 1 ]
			then
				# Make Ken throw the largest thing
				kl=$(($kl - 1))
			else
				# Make Ken throw the smallest thing
				nofair=$(($nofair + 1))
				ks=$(($ks + 1))
			fi
		fi
	done
	echo "Case #$ti: $nofair $fair"
done