Saturday, March 14, 2009

Small quiz solutions in 12 languages

Last week I posted a short programming quiz in my Thai development community at narisa.com and asked members to come up with solutions in many languages as possible. We finally got 12 solutions implemented in C, C#, Clojure, Erlang, Groovy, Haskell, Java, PHP, Python, Ruby, Scala, Visual Basic with LINQ. Some languages have more than one implementations.

The quiz is about parsing and sorting an input text file. There are records; one per line. Each record has many fields delimited by a pipe symbol '|'. The first field is a record number. We want to sort all the records by this number and display the sorted result one record per line. Each line will display the record number followed by sorted fields. (The original problem didn't have number sort and first column exclusion constraints)

For example, an input.txt file:
13|hello|world|bangkok
4|1monkey|ant|dog|cow|cat
2|pink|yellow|red|magenta
1|earth|sun|jupiter|pluto


The expected result:
1 earth jupiter pluto sun
2 magenta pink red yellow
4 1monkey ant cat cow dog
13 bangkok hello world


Notice that the record number 13 is after record number 4. So we need to compare the number by value, not by string literal. Each record has to exclude the field number and sort the rest alphabetically.

Here are solutions. Your truly provided 2 solutions in Ruby and Scala. You will see that Thai development community is quite vibrant from a variety of language choices. Look like Groovy is among the most popular one. You will see that scripting languages are good for this kind of problem in terms of compactness and declarative style. Read the original post in Thai here.

C (gcc) by iWat
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct record
{
int number;

int num_fields;
char **fields;

char *buffer;
};

static int record_number_comparator(struct record *first, struct record *second)
{
return first->number - second->number;
}

static void bubble_sort(void **ar_p_struct, int count, int (*comparator)(void *, void *))
{
int i;
int j;

for (i = 0; i < count - 1; ++i)
{
for (j = 0; j < count - 1 - i; ++j)
{
if (comparator(ar_p_struct[j+1], ar_p_struct[j]) < 0) {
void *p_tmp;

p_tmp = ar_p_struct[j];
ar_p_struct[j] = ar_p_struct[j + 1];
ar_p_struct[j + 1] = p_tmp;
}
}
}
}

static void print_record(struct record *my_record)
{
int i;

for (i = 0; i < my_record->num_fields; ++i)
{
printf("%s ", my_record->fields[i]);
}

printf("\n");
}

static void parse_records(FILE *fp, struct record ***p_ar_p_records, int *p_num_records)
{
char buffer[256];

*p_num_records = 0;
*p_ar_p_records = NULL;

while (fgets(buffer, 256, fp) != NULL)
{
struct record *current_record = malloc(sizeof(struct record));

current_record->num_fields = 0;
current_record->fields = malloc(10 * sizeof(char *));
current_record->buffer = strdup(buffer);

char *start = current_record->buffer;
char *pointer = start;

while(1)
{
if (*pointer == '|' || *pointer == '\0')
{
current_record->fields[current_record->num_fields] = start;

start = pointer + 1;

if (current_record->num_fields == 0)
current_record->number = atoi(current_record->fields[0]);

++current_record->num_fields;

if (*pointer == '\0')
{
if (*(pointer - 1) == '\n')
*(pointer - 1) = '\0';
break;
}

*pointer = '\0';
}

++pointer;
}

++(*p_num_records);
*p_ar_p_records = (struct record **) realloc(*p_ar_p_records, sizeof(struct record *) * (*p_num_records));
(*p_ar_p_records)[(*p_num_records) - 1] = current_record;
}
}

int main(int argc, char **argv)
{
int i;
int num_records;
struct record **ar_p_records;

FILE *fp;

if (argc != 2)
{
printf("Usage: %s <input file>\n", argv[0]);
return 1;
}

fp = fopen(argv[1], "r");

if (fp == NULL)
{
printf("error reading file: %s\n", argv[1]);
return 2;
}

parse_records(fp, &ar_p_records, &num_records);

printf("===== parse result\n");

for (i = 0; i < num_records; ++i)
{
print_record(ar_p_records[i]);
}

bubble_sort((void **) ar_p_records, num_records, (int(*)(void *, void *)) record_number_comparator);

printf("\n===== sort result\n");

for (i = 0; i < num_records; ++i)
{
bubble_sort(
(void **) (ar_p_records[i]->fields + 1),
ar_p_records[i]->num_fields - 1,
(int(*)(void *, void *)) strcmp);
print_record(ar_p_records[i]);
}


fclose(fp);
}


C# with LINQ by bleak
using System;
using System.Linq;

class FunCode
{
static void Main(string[] args)
{
string[] records = System.IO.File.ReadAllLines("input.txt");
var rs = from r in records
let fields = r.Split('|')
orderby int.Parse(fields[0])
select string.Concat(fields[0], " ", string.Join(" ", fields.Skip(1).OrderBy(x => x).ToArray()));
foreach (var r in rs)
Console.WriteLine(r);
}
}


Clojure by pphetra
(defn outer-sort [xs]
(sort-by #(first %) xs))

(defn inner-sort [xs]
(let [fst (first xs)
rst (sort (rest xs))]
(cons fst rst)))

(defn solve [xs]
(outer-sort (map inner-sort xs)))

(defn read-file [file-name]
(let [raw-lines (seq (.split (slurp file-name) "\n"))
lines (map #(seq (.split % "\\|")) raw-lines)]
lines))

(defn pretty-print [xs]
(doseq [line xs]
(do (doseq [word line]
(print word ""))
(print "\n"))))

;; ตัวอย่างการใช้
(pretty-print (solve (read-file "input.txt")))


Coldfusion by iporsut
<cfset recordset = QueryNew("id, list" , "Integer, VarChar")>
<cfset count = 1 />
<cfloop file="#Expandpath('/')#input.txt" index="line">
<cfscript>
line = listChangeDelims(line,",","|");
id = listfirst(line);
list = listsort(listrest(line) , "text", "asc");
list = listChangeDelims(list," ",",");

QueryAddRow(recordset,1);
QuerySetCell(recordset,"id",id,count);
QuerySetCell(recordset,"list",list,count);

count++;
</cfscript>
</cfloop>

<cfquery dbtype="query" name="qSortedRecord">
select id,list
from recordset
order by id asc
</cfquery>

<cfoutput query="qSortedRecord">
#qSortedRecord.id# #qSortedRecord.list# <br />
</cfoutput>


Erlang by pphetra
-module(s1).
-export([solve/1]).

-import(lists, [sort/2,sort/1]).
-import(string, [tokens/2, to_integer/1]).

% เขาว่า read แบบ binary จะ performance ดีกว่า
readfile(FileName) ->
{ok, Binary} = file:read_file(FileName),
tokens(erlang:binary_to_list(Binary), "\n").

% แต่ละ line ที่ได้มาให้ split tokens ด้วย
parse(FileName) ->
[ tokens(Line, "|") || Line <- readfile(FileName)].

% sort โดยใช้ Head Element และแปลงเป็น integer ก่อน sort
outer_sort(List) ->
sort(fun ([H1|_], [H2|_]) -> to_integer(H1) =< to_integer(H2) end, List).

solve(FileName) ->
outer_sort([ [H | sort(T)] || [H|T] <- parse(FileName)]).

1> c(s1).
{ok,s1}
2> s1:solve('input.txt').


Groovy #1 by cblue
def result=[:]
new File('input.txt').eachLine {
def line = it.tokenize('|')
result[line[0] as int] = line[1..-1].sort()
}
result.sort{ e1, e2 -> e1.key - e2.key }.each { k, v ->
println "$k ${v.join(' ')}"
}


Groovy #2 by cblue
def result = new File('input.txt').readLines().collect {
def line = it.tokenize('|')
[line.head() as int] + line.tail().sort()
}
result.sort { o1, o2 -> o1[0] <=> o2[0] }.each {
println it.join(' ')
}


Groovy #3 by xcaleber

new File("input.txt").readLines()*.tokenize("|").sort{one, another -> one[0] <=> another[0]}.each{ println "${it[0]} ${it[1..-1].sort().join(' ')}" }


Haskell #1 by iporsut
import List

compareFirst::[[Char]]->[[Char]]->Ordering
compareFirst a b | (read (head a)::Int) >= (read (head b)::Int) = GT
| otherwise = LT

transformPipeToSpace::[Char]->[Char]
transformPipeToSpace a = map transform a
where
transform b | b == '|' = ' '
| otherwise = b
inputToWords::[Char]->[[[Char]]]
inputToWords input = map words (map transformPipeToSpace (lines input))


wordsToOutput::[[[Char]]]->[Char]
wordsToOutput word = foldl (++) "" (map unwordsNewline word)
where
unwordsNewline w = (unwords w)++['\n']

sortRecords::[Char]->[[[Char]]]
sortRecords input = map sortWords (sortBy compareFirst (inputToWords input))
where
sortWords (x:xs) = x:(sort xs)
main = do
input <- readFile "input.txt"
putStrLn (wordsToOutput (sortRecords input))


Haskell #2 by pphetra
import List

split delim s
| [] <- rest = [token]
| otherwise = token : split (delim) (tail rest)
where (token,rest) = span (/= delim) s

compareFirst a b | (read (head a)::Int) >= (read (head b)::Int) = GT
| otherwise = LT

splitAndSort s = head xs : sort (tail xs)
where xs = split '|' s

main = do
input <- readFile "s1.txt"
putStrLn $ (unlines . map unwords . sortBy compareFirst . map splitAndSort . lines) input


Java #1 by comx
package javaapplication1;

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws Exception {
Reader r = new FileReader("c:/input.txt");
BufferedReader br = new BufferedReader(r);
SortedSet lineItemHolder = new TreeSet();
while (true) {
String line = br.readLine();
if (line == null) {
break;
}
lineItemHolder.add(new LineItem(line));
}
print(lineItemHolder);
}

public static void print(Collection items) {
for (Object object : items) {
System.out.println(object);
}
}
}


Java #2 by panther
import java.io.*;
import java.util.*;

class FooSort
{
public static void main(String[] args)throws Exception
{
BufferedReader br = new BufferedReader( new FileReader("c:/input.txt") );
Map<Integer, List<String>> tm = new TreeMap<Integer, List<String>>();

while( true ){

String line = br.readLine();

if( line == null ){
break;
}

String[] record = line.split("[|]");
List<String> list = Arrays.asList( record );

Collections.sort( list );

tm.put( Integer.parseInt( list.get( 0 ) ) , list );
}

Iterator<Map.Entry<Integer, List<String>>> it =
((Set<Map.Entry<Integer, List<String>>>)tm.entrySet()).iterator();

while( it.hasNext() ){
renderlist( it.next().getValue() );
}
}

public static void renderlist( List<String> list ){

Iterator<String> it = list.iterator();

while( it.hasNext() ){
System.out.print( it.next() + " " );
}

System.out.println();
}
}


PHP by Rux
<?php
$lines = file('input.txt');

foreach($lines as $line){
$key = substr($line, 0, strpos($line, '|'));
$ds[$key] = explode('|', $line);
}

ksort($ds);

foreach($ds as $rw){
sort($rw);
echo implode("&nbsp;", $rw);
echo "<br />";
}
?>


Ruby by your truely
lines = IO.readlines('input.txt').map do |line|
items = line.chomp.split('|')
[items.shift] + items.sort
end
lines.sort { |one, another| one[0].to_i <=> another[0].to_i }.each do |line|
puts line.join(' ')
end


Ruby with UNIX commands by pphetra
ruby -F'\|' -nlae 'puts $F[1..-1].sort().unshift($F[0]).join(" ")' input.txt | sort -nk 1

Scala by your truly
import scala.io.Source
import scala.util.Sorting

def show_sort(fileName: String) = {
def sort_record(line: String) = {
val fields = List.fromString(line.replace("\n", ""), '|')
fields.head :: fields.tail.sort((a,b) => (a compareTo b) < 0)
}
val tuples = Source.fromFile(fileName).getLines.map(sort_record).collect
val sort_tuples = Sorting.stableSort(tuples, (a:List[String], b:List[String]) => a.head.toInt < b.head.toInt)
sort_tuples.map(tuple => println(tuple.mkString("", " ", "")))
}
show_sort("input.txt")


VisualBasic.NET with LINQ by tuckclub
Module Module1

Sub Main()
Dim records = System.IO.File.ReadAllLines("input.txt")
Dim rs = From r In records _
Let ia = r.Split("|") _
Let ca = (From c In ia.Skip(1) Order By c) _
Order By ia(0) _
Select ia.Take(1).Union(ca).ToArray
For Each r In rs
Console.WriteLine(String.Join(" ", r))
Next
Console.ReadKey()
End Sub

End Module