Google Codejam Qualification Round 2014 / Mine

mine.adb

with Ada.Text_IO;
with Ada.Integer_Text_IO;

procedure Mine is
	package IO renames Ada.Text_IO;
	package IntIO renames Ada.Integer_Text_IO;

	type CellValue is ('*', '.', 'c');
	type Board is array (Natural range <>, Natural range <>) of CellValue;
	
	function CreateBoard (R, C: in Positive) return Board is
		result: Board(1 .. R, 1 .. C);
	begin
		for i in Positive range 1 .. R loop
			for j in Positive range 1 .. C loop
				result(i, j) := '*';
			end loop;
		end loop;
		result(1, 1) := 'c';
		return result;
	end CreateBoard;

	procedure DrawRect(b: in out Board;
		sr, er, sc, ec: in Positive;
		count: in Natural;
		v: in CellValue) is
		inner_count: Natural;
	begin
		inner_count := count;
		for i in Positive range sr .. er loop
			for j in Positive range sc .. ec loop
				if inner_count <= 0 then
					return;
				elsif i > 1 or j > 1 then
					b(i, j) := v;
				end if;
				inner_count := inner_count - 1;
			end loop;
		end loop;
		return;
	end DrawRect;

	procedure FindBoard(R, C: in Positive; M: in Natural) is
		mboard: Board(1 .. R, 1 .. C);
		empty: Natural;
	begin
		mboard := CreateBoard(R, C);
		empty := R*C - M;
		if M = 0 or R = 1 or C = 1 or empty = 1 then
			DrawRect(mboard, 1, R, 1, C, empty, '.');
			goto Possible;
		elsif empty = 2 or empty = 3 or empty = 5 or empty = 7 then
			goto Impossible;
		elsif R = 2 or C = 2 then
			if empty mod 2 = 1 then
				goto Impossible;
			elsif R = 2 then
				DrawRect(mboard, 1, 2, 1, empty/2, empty, '.');
			else
				DrawRect(mboard, 1, empty/2, 1, 2, empty, '.');
			end if;
			goto Possible;
		else
			if empty mod 2 = 0 then
				if empty > C*2 then
					DrawRect(mboard, 1, 2, 1, C, empty, '.');
					empty := empty - C*2;
				else
					DrawRect(mboard, 1, 2, 1, empty/2, empty, '.');
					goto Possible;
				end if;
			else
				if empty > C*2+3 then
					DrawRect(mboard, 1, 2, 1, C, empty, '.');
					empty := empty - C*2;
				else
					DrawRect(mboard, 1, 2, 1, (empty-3)/2, empty-3, '.');
					DrawRect(mboard, 3, 3, 1, 3, 3, '.');
					goto Possible;
				end if;
			end if;
			if empty > (R-2)*2 then
				DrawRect(mboard, 3, R, 1, 2, empty, '.');
				empty := empty - (R-2)*2;
			elsif empty mod 2 = 0 then
				DrawRect(mboard, 3, 2+(empty/2), 1, 2, empty, '.');
				goto Possible;
			else
				DrawRect(mboard, 3, 2+((empty-1)/2), 1, 2, empty, '.');
				mboard(3, 3) := '.';
				goto Possible;
			end if;
			DrawRect(mboard, 3, R, 3, C, empty, '.');
			goto Possible;
		end if;
<<Possible>>
		for i in Positive range 1 .. R loop
			for j in Positive range 1 .. C loop
				IO.Put(CellValue'Image(mboard(i, j))(2));
			end loop;
			IO.Put_Line("");
		end loop;
		return;
<<Impossible>>
		IO.Put_Line("Impossible");
		return;
	end FindBoard;

	T, R, C: Positive;
	M: Natural;
begin
	IntIO.Get(T);
	for Ti in Positive range 1 .. T loop
		IntIO.Get(R);
		IntIO.Get(C);
		IntIO.Get(M);
		IO.Put("Case #");
		IntIO.Put(Item=>Ti, Width=>0);
		IO.Put_Line(":");
		FindBoard(R, C, M);
	end loop;
end Mine;

mine.lua

#!/usr/bin/env lua

-- This code is unused because I did not want to use Lua early.

function split(s)
	local res = {}
	local i = 1
	for token in string.gmatch(s, '([0-9]+)') do
		res[i] = 0+token
		i = i+1
	end
	return res
end

function getTable(R, C)
	local res = {}
	for i = 1,R do
		res[i] = {}
		for j=1,C do
			res[i][j] = '*'
		end
	end
	return res
end

function printTable(R, C, res, flip)
	local str = ""
	if flip then
		for i=1,C do
			if i > 1 then str = str .. "\n" end
			for j=1,R do
				str = str .. res[j][i]
			end
		end
	else
		for j=1,R do
			if j > 1 then str = str .. "\n" end
			for i=1,C do
				str = str .. res[j][i]
			end
		end
	end
	return str
end

function solve(R, C, M, flip)
	if C > R then
		return solve(C, R, M, not flip)
	end
	-- Condition: C < R, M < R*C
	local empty = R*C - M
	local board = getTable(R, C)
	local parity = empty%2
	board[1][1] = 'c'
	if C == 1 then
		for i=2,empty do
			board[i][1] = '.'
		end
	elseif empty > 1 then -- empty == 1: always possible
		if empty < 4 then
			return "Impossible"
		elseif empty <= 7 and parity == 1 then
			return "Impossible"
		elseif C == 2 then
			if parity == 1 then
				return "Impossible"
			else
				board[1][2] = '.'
				for i=2,empty/2 do
					board[i][1] = '.'
					board[i][2] = '.'
				end
			end
		else
			empty = empty-2
			board[1][2] = '.'
			for i=2,R do
				if empty == 3 or empty == 0 then break end
				empty = empty-2
				board[i][1] = '.'
				board[i][2] = '.'
			end
			if empty <= 3 then
				for i=1,empty do
					board[i][3] = '.'
				end
			else
				for i=3,C do
					if empty <= 1 then break end
					empty = empty-2
					board[1][i] = '.'
					board[2][i] = '.'
				end
				for i=3,R do
					for j=3,C do
						if empty == 0 then break end
						empty = empty-1
						board[i][j] = '.'
					end
					if empty == 0 then break end
				end
			end
		end
	end
	return printTable(R, C, board, flip)
end

T = 0 + io.read()
for Ti=1,T do
	line = split(io.read())
	print(string.format("Case #%d:", Ti))
	print(solve(line[1], line[2], line[3], false))
end

mine.vb

Class Maze
	Shared Sub Main
		Dim T, N, R, C, M, E, LL as Integer
		Dim l() as String
		T = CInt(Console.ReadLine())
		For Ti As Integer = 1 To T
			l = Split(Console.ReadLine())
			R = CInt(l(0))
			C = CInt(l(1))
			M = CInt(l(2))
			E = R*C - M
			Console.WriteLine("Case #" & Ti & ":")
			If M = 0 Then
				For i As Integer = 1 To R
					For j As Integer = 1 To C
						If i = 1 and j = 1 Then
							Console.Write("c")
						Else
							Console.write(".")
						End If
					Next
					Console.Write(vbLf)
				Next
			ElseIf R = 1 or C = 1 or E = 1 Then
				For i As Integer = 1 To R
					For j As Integer = 1 To C
						If i = 1 and j = 1 Then
							Console.Write("c")
							E = E - 1
						ElseIf E > 0
							Console.Write(".")
							E = E - 1
						Else
							Console.Write("*")
						End If
					Next
					Console.Write(vbLf)
				Next
			ElseIf E = 2 Or E = 3 Or E = 5 Or E = 7 Then
				Console.WriteLine("Impossible")
			Elseif R = 2 Or C = 2 Then
				If E mod 2 = 1 Then
					Console.WriteLine("Impossible")
				Else
					For i As Integer = 1 To R
						For j As Integer = 1 To C
							If i = 1 and j = 1 Then
								Console.Write("c")
							ElseIf (R = 2 and j <= E/2) or (C = 2 and i <= E/2) Then
								Console.Write(".")
							Else
								Console.Write("*")
							End If
						Next
						Console.Write(vbLf)
					Next
				End If
			Else
				Dim map(R, C) As String
				For i As Integer = 0 To R-1
					For j As Integer = 0 To C-1
						map(i, j) = "*"
					Next
				Next
				map(0, 0) = "c"
				map(0, 1) = "."
				E = E-2
				For i As Integer = 1 To R-1
					If E = 3 or E = 0 Then
						Exit For
					End If
					E = E - 2
					map(i, 0) = "."
					map(i, 1) = "."
				Next
				If E <= 3 Then
					For i As Integer = 0 To E-1
						map(i, 2) = "."
					Next
				Else
					For i As Integer = 2 To C-1
						If E <= 1 Then
							Exit For
						End If
						E = E - 2
						map(0, i) = "."
						map(1, i) = "."
					Next
					For i As Integer = 2 To R-1
						For j As Integer = 2 To C-1
							If E = 0 Then
								Exit For
							End If
							E = E-1
							map(i, j) = "."
						Next
						If E = 0 Then
							Exit For
						End If
					Next
				End If
				
				For i As Integer = 0 To R-1
					For j As Integer = 0 To C-1
						Console.Write(map(i, j))
					Next
					Console.Write(vbLf)
				Next
			End If
		Next
	End Sub
End Class