2013年9月27日 星期五

[ Google CT2004 ] RoundA : Problem C. Sorting

Problem: 
Alex and Bob are brothers and they both enjoy reading very much. They have widely different tastes on books so they keep their own books separately. However, their father thinks it is good to promote exchanges if they can put their books together. Thus he has bought an one-row bookshelf for them today and put all his sons' books on it in random order. He labeled each position of the bookshelf the owner of the corresponding book ('Alex' or 'Bob'). 

Unfortunately, Alex and Bob went outside and didn't know what their father did. When they were back, they came to realize the problem: they usually arranged their books in their own orders, but the books seem to be in a great mess on the bookshelf now. They have to sort them right now!! 

Each book has its own worth, which is represented by an integer. Books with odd values of worth belong to Alex and the books with even values of worth belong to Bob. Alex has a habit of sorting his books from the left to the right in an increasing order of worths, while Bob prefers to sort his books from the left to the right in a decreasing order of worths. 

At the same time, they do not want to change the positions of the labels, so that after they have finished sorting the books according their rules, each book's owner's name should match with the label in its position. 

Here comes the problem. A sequence of N values s0, s1, ..., sN-1 is given, which indicates the worths of the books from the left to the right on the bookshelf currently. Please help the brothers to find out the sequence of worths after sorting such that it satisfies the above description. 

Input: 
The first line of input contains a single integer T, the number of test cases. Each test case starts with a line containing an integer N, the number of books on the bookshelf. The next line contains N integers separated by spaces, representing s0, s1, ..., sN-1, which are the worths of the books. 

Output: 
For each test case, output one line containing "Case #X: ", followed by t0, t1, ..., tN-1 in order, and separated by spaces. X is the test case number (starting from 1) andt0, t1, ..., tN-1 forms the resulting sequence of worths of the books from the left to the right. 

Limits: 
1 ≤ T ≤ 30. 

Small dataset 
1 ≤ N ≤ 100 
-100 ≤ si ≤ 100 

Large dataset 
1 ≤ N ≤ 1000 
-1000 ≤ si ≤ 1000 

Sample: 
Input
2
5
5 2 4 3 1
7
-5 -12 87 2 88 20 11

Output 
Case #1: 1 4 2 3 5
Case #2: -5 88 11 20 2 -12 87

One Solution: 
問題的描述很長, 但其實是送分題 Orz... 簡單說就是給你一個數字串列, 單數使用 asc sorting order; 雙數使用 desc sorting order, 而單數與雙數在原先的數字串列位置需保留. 所以: 
原始數列: 5 2 4 3 1
排序數列: 1 4 2 3 5

上面紅色字是單數; 綠色是雙數. 經過排序後顏色的位置沒有變, 紅色由低到高排列; 綠色由高到低排列. 知道問題後代碼便是秒殺: 


  1. package cj2014;  
  2.   
  3. import java.util.Comparator;  
  4. import java.util.PriorityQueue;  
  5.   
  6. import flib.util.io.QSReader;  
  7. import flib.util.io.QSWriter;  
  8.   
  9. public class PC {  
  10.     /** 
  11.      * BD: https://code.google.com/codejam/contest/2924486/dashboard#s=p2 
  12.      * @param args 
  13.      */  
  14.     public static void main(String args[]) throws Exception  
  15.     {  
  16.         String fn="C-large-practice.in";  
  17.         QSReader qsr = new QSReader(String.format("data/2014/%s", fn));  
  18.         QSWriter qsw = new QSWriter(String.format("data/2014/%s.out", fn));  
  19.         qsr.open();       
  20.         Integer pc = Integer.valueOf(qsr.line());  
  21.         Comparator desCmp = new Comparator(){  
  22.             @Override  
  23.             public int compare(Integer o1, Integer o2) {  
  24.                 return o2.compareTo(o1);  
  25.             }  
  26.               
  27.         };  
  28.         Comparator ascCmp = new Comparator(){  
  29.             @Override  
  30.             public int compare(Integer o1, Integer o2) {  
  31.                 return o1.compareTo(o2);  
  32.             }  
  33.               
  34.         };  
  35.         System.out.printf("\t[Info] Total %d question...\n", pc);  
  36.         for(int i=1; i<=pc; i++)  
  37.         {  
  38.             int size = Integer.valueOf(qsr.line());  
  39.             System.out.printf("\t\tP%d has %d number...\n", i, size);  
  40.             String ns[] = qsr.line().split(" ");  
  41.             PriorityQueue alexPQ = new PriorityQueue(10, ascCmp);  
  42.             PriorityQueue bobPQ = new PriorityQueue(10, desCmp);  
  43.             StringBuffer strBuf = new StringBuffer();  
  44.             for(int j=0; j
  45.             {  
  46.                 int k = Integer.valueOf(ns[j]);  
  47.                 if(k%2==0) {  
  48.                     bobPQ.add(k);  
  49.                     ns[j]="e"// even  
  50.                 }  
  51.                 else {  
  52.                     alexPQ.add(k);  
  53.                     ns[j]="o"// odd  
  54.                 }  
  55.             }  
  56.             for(int j=0; j
  57.             {  
  58.                 if(ns[j].equals("e")) strBuf.append(String.format("%d ", bobPQ.poll()));  
  59.                 else strBuf.append(String.format("%d ", alexPQ.poll()));  
  60.             }  
  61.             qsw.line(String.format("Case #%d: %s", i, strBuf.toString().trim()));  
  62.         }  
  63.           
  64.         qsr.close();  
  65.         qsw.close();  
  66.     }  
  67. }  

2013年9月26日 星期四

[ Java 文章收集 ] Java SE 6.0 內建 Javascript 引擎測試

來源自 這裡 
Preface: 
Java SE 6.0 採納 JSR 223 建議,使得 Java 能夠與眾多 Script 語言協同運作,透過 Java 定義的標準 API,能夠讓 Script 直接存取和控制 Java 的物件,而Java 應用程式當中也能夠直接內嵌 Script 環境。Java SE 6 的 javax.script package 定義了 Script API,裡面共實作了六個介面和六個類別,如下: 
- 介面 
Bindings: A mapping of key/value pairs, all of whose keys are Strings.
Compilable: The optional interface implemented by ScriptEngines whose methods compile scripts to a form that can be executed repeatedly without recompilation.
Invocable: The optional interface implemented by ScriptEngines whose methods allow the invocation of procedures in scripts that have previously been executed.
ScriptContext: The interface whose implementing classes are used to connect Script Engines with objects, such as scoped Bindings, in hosting applications.
ScriptEngine: ScriptEngine is the fundamental interface whose methods must be fully functional in every implementation of this specification.
ScriptEngineFactory: ScriptEngineFactory is used to describe and instantiate ScriptEngines.

- 類別 
AbstractScriptEngine: Provides a standard implementation for several of the variants of the eval method.
CompiledScript: Extended by classes that store results of compilations.
ScriptEngineManager:
The ScriptEngineManager implements a discovery and instantiation mechanism for ScriptEngine classes and also maintains a collection of key/value pairs storing state shared by all engines created by the Manager.
SimpleBindings:A simple implementation of Bindings backed by a HashMap or some other specified Map.
SimpleScriptContext: Simple implementation of ScriptContext.

範例01:第一個 Hello World 程式 
  1. package test.scripts;  
  2.   
  3. import javax.script.ScriptEngine;  
  4. import javax.script.ScriptEngineManager;  
  5. import javax.script.ScriptException;  
  6.   
  7. public class JSDemo1 {  
  8.     public static void main(String args[])  
  9.     {  
  10.         ScriptEngineManager mgr = new ScriptEngineManager(); // 建立一個 Script 管理員  
  11.         ScriptEngine jsEngine = mgr.getEngineByName("JavaScript"); // 取得 Javascript 引擎  
  12.         try {  
  13.           jsEngine.eval("print('Hello, world!')"); // 透過 Javascript 引擎解譯 print('hello, world') 命令  
  14.         } catch (ScriptException ex) {  
  15.             ex.printStackTrace();  
  16.         }   
  17.     }  
  18. }  
範例02:列舉 Java 環境支援的 Script 引擎 
  1. package test.scripts;  
  2.   
  3. import java.util.List;  
  4.   
  5. import javax.script.ScriptEngineFactory;  
  6. import javax.script.ScriptEngineManager;  
  7.   
  8. public class JSDemo2 {  
  9.   
  10.     /** 
  11.      * BD: 範例02:列舉 Java 環境支援的 Script 引擎 
  12.      * @param args 
  13.      */  
  14.     public static void main(String[] args) {  
  15.         ScriptEngineManager mgr = new ScriptEngineManager();  
  16.         List factories = mgr.getEngineFactories();  
  17.         for (ScriptEngineFactory factory : factories) {  
  18.             System.out.println("ScriptEngineFactory Info");  
  19.   
  20.             String engName = factory.getEngineName(); // 引擎名稱  
  21.             String engVersion = factory.getEngineVersion(); // 引擎版本  
  22.             String langName = factory.getLanguageName(); // Script 語言  
  23.             String langVersion = factory.getLanguageVersion(); // 語言版本  
  24.   
  25.             System.out.printf("\tScript Engine: %s (%s)\n", engName, engVersion);  
  26.             List engNames = factory.getNames();  
  27.             for (String name : engNames) {  
  28.                 System.out.printf("\t\tEngine Alias: %s\n", name);  
  29.             }  
  30.   
  31.             System.out.printf("\tLanguage: %s (%s)\n", langName, langVersion);  
  32.         }  
  33.     }  
  34. }  
執行結果: 
ScriptEngineFactory Info
Script Engine: Mozilla Rhino (1.6 release 2)
Engine Alias: js
Engine Alias: rhino
Engine Alias: JavaScript
Engine Alias: javascript
Engine Alias: ECMAScript
Engine Alias: ecmascript
Language: ECMAScript (1.6)

範例03:搜尋指定的 Script 引擎 
  1. package test.scripts;  
  2.   
  3. import java.util.List;  
  4.   
  5. import javax.script.ScriptEngine;  
  6. import javax.script.ScriptEngineFactory;  
  7. import javax.script.ScriptEngineManager;  
  8.   
  9. public class JSDemo3 {  
  10.   
  11.     /** 
  12.      * BD: 範例03:搜尋指定的 Script 引擎 
  13.      * @param args 
  14.      */  
  15.     public static void main(String[] args) {  
  16.         ScriptEngineManager mgr = new ScriptEngineManager();  
  17.         List scriptFactories = mgr.getEngineFactories();  
  18.         for (ScriptEngineFactory factory : scriptFactories) {  
  19.             String langName = factory.getLanguageName();  
  20.             String langVersion = factory.getLanguageVersion();  
  21.             if (langName.startsWith("ECMAScript") && langVersion.startsWith("1.6")) { // 比對指定的與名稱和版本  
  22.                 ScriptEngine engine = factory.getScriptEngine();  
  23.                 System.out.printf("Engine:%s\n", engine);  
  24.                 break;  
  25.             }  
  26.         }  
  27.     }  
  28. }  
範例04:執行外部 javasript 檔案 
考慮有如下的 js 檔案: 
- hellp.js 
  1. var str="Hello world, welcome to the universe.";  
  2. var n=str.indexOf("welcome");  
  3. print(str+" "+n);  
接著你可以如下執行該 js 檔案: 
  1. package test.scripts;  
  2.   
  3. import java.io.FileInputStream;  
  4. import java.io.InputStream;  
  5. import java.io.InputStreamReader;  
  6. import java.io.Reader;  
  7.   
  8. import javax.script.ScriptEngine;  
  9. import javax.script.ScriptEngineManager;  
  10. import javax.script.ScriptException;  
  11.   
  12. public class JSDemo4 {  
  13.   
  14.     /** 
  15.      * BD: 範例04:執行外部 javasript 檔案 
  16.      * @param args 
  17.      */  
  18.     public static void main(String[] args) throws Exception {  
  19.         ScriptEngineManager engineMgr = new ScriptEngineManager();  
  20.         ScriptEngine engine = engineMgr.getEngineByName("ECMAScript");  
  21.         InputStream is = new FileInputStream("hello.js");  
  22.         try {  
  23.             Reader reader = new InputStreamReader(is);  
  24.             engine.eval(reader);  
  25.         } catch (ScriptException ex) {  
  26.             ex.printStackTrace();  
  27.         }  
  28.     }  
  29. }  
執行結果: 
Hello world, welcome to the universe. 13

範例05:透過 Invocable 介面喚起 Javascript 函數 
  1. package test.scripts;  
  2.   
  3. import javax.script.Invocable;  
  4. import javax.script.ScriptEngine;  
  5. import javax.script.ScriptEngineManager;  
  6. import javax.script.ScriptException;  
  7.   
  8. public class JSDemo5 {  
  9.   
  10.     /** 
  11.      * BD: 範例05:透過 Invocable 介面喚起 Javascript 函數 
  12.      * @param args 
  13.      */  
  14.     public static void main(String[] args) {  
  15.         ScriptEngineManager engineMgr = new ScriptEngineManager();  
  16.         ScriptEngine jsEngine = engineMgr.getEngineByName("ECMAScript");  
  17.         try {  
  18.             jsEngine.eval("function sayHello() {" +  
  19.                         "  println('Hello, world!');" +  
  20.                         "}");  
  21.             Invocable invocableEngine = (Invocable) jsEngine;  
  22.             invocableEngine.invokeFunction("sayHello");  
  23.         } catch (ScriptException ex) {  
  24.             ex.printStackTrace();  
  25.         } catch (NoSuchMethodException nsme){  
  26.             nsme.printStackTrace();  
  27.         }  
  28.     }  
  29. }  
執行結果: 
Hello, world!

範例06:Script 直接存取 Java 物件 
  1. package test.scripts;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5.   
  6. import javax.script.ScriptEngine;  
  7. import javax.script.ScriptEngineManager;  
  8. import javax.script.ScriptException;  
  9.   
  10. public class JSDemo6 {  
  11.     /** 
  12.      * BD: 範例06:Script 直接存取 Java 物件  
  13.      * @param args 
  14.      */  
  15.     public static void main(String args[]) {  
  16.         List namesList = new ArrayList();  
  17.         namesList.add("Jill");  
  18.         namesList.add("Bob");  
  19.         namesList.add("Laureen");  
  20.         namesList.add("Ed");  
  21.         ScriptEngineManager engineMgr = new ScriptEngineManager();  
  22.         ScriptEngine jsEngine = engineMgr.getEngineByName("ECMAScript");  
  23.         jsEngine.put("namesListKey", namesList); // 將 java 變數指定給 javascript 環境中的 nameListKey 變數  
  24.         System.out.println("Executing in script environment…");  
  25.         try {  
  26.             // 列印 Java 的 nameList 變數內容,並新增一個 Dana 字串資料到 List 尾端  
  27.             jsEngine.eval("var x;" + "var names = namesListKey.toArray();"  
  28.                     + "for(x in names) {" + "  println(names[x]);" + "}"  
  29.                     + "namesListKey.add(\"Dana\");");  
  30.         } catch (ScriptException ex) {  
  31.             ex.printStackTrace();  
  32.         }  
  33.         System.out.println("Executing in Java environment…");  
  34.         for (String name : namesList) {  
  35.             System.out.println(name);  
  36.         }  
  37.     }  
  38. }  
執行結果: 
Executing in script environment…
Jill
Bob
Laureen
Ed
Executing in Java environment…
Jill
Bob
Laureen
Ed
Dana

範例07:透過 Invocable 將參數值傳遞給 Javascript 中的函數 
  1. package test.scripts;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5.   
  6. import javax.script.Invocable;  
  7. import javax.script.ScriptEngine;  
  8. import javax.script.ScriptEngineManager;  
  9. import javax.script.ScriptException;  
  10.   
  11. public class JSDemo7 {  
  12.   
  13.     /** 
  14.      * BD: 範例07:透過 Invocable 將參數值傳遞給 Javascript 中的函數 
  15.      * @param args 
  16.      */  
  17.     public static void main(String[] args) {  
  18.         List namesList = new ArrayList();  
  19.         namesList.add("Jill");  
  20.         namesList.add("Bob");  
  21.         namesList.add("Laureen");  
  22.         namesList.add("Ed");  
  23.         ScriptEngineManager engineMgr = new ScriptEngineManager();  
  24.         ScriptEngine jsEngine = engineMgr.getEngineByName("ECMAScript");  
  25.         Invocable invocableEngine = (Invocable) jsEngine;  
  26.         try {  
  27.             System.out.printf("\t[Info] Execute in JS:\n");  
  28.             jsEngine.eval("function printNames1(namesList) {" + "  var x;"  
  29.                     + "  var names = namesList.toArray();"  
  30.                     + "  for(x in names) {" + "    println(names[x]);" + "  }"  
  31.                     + "}" + "function addName(namesList, name) {"  
  32.                     + "  namesList.add(name);" + "}");  
  33.             invocableEngine.invokeFunction("printNames1", namesList);  
  34.             invocableEngine.invokeFunction("addName", namesList, "Dana");  
  35.             System.out.printf("\t[Info] Execute in Java:\n");  
  36.             for(String name:namesList) System.out.println(name);  
  37.         } catch (ScriptException ex) {  
  38.             ex.printStackTrace();  
  39.         } catch (NoSuchMethodException ex) {  
  40.             ex.printStackTrace();  
  41.         }  
  42.     }  
  43. }  
執行結果: 
[Info] Execute in JS:
Jill
Bob
Laureen
Ed
[Info] Execute in Java:
Jill
Bob
Laureen
Ed
Dana

範例08:script 使用 Java 的 package 
  1. package test.scripts;  
  2.   
  3. import javax.script.ScriptEngine;  
  4. import javax.script.ScriptEngineManager;  
  5. import javax.script.ScriptException;  
  6.   
  7. public class JSDemo8 {  
  8.   
  9.     /** 
  10.      * BD: 範例08:script 使用 Java 的 package 
  11.      * @param args 
  12.      */  
  13.     public static void main(String[] args) {  
  14.         ScriptEngineManager engineMgr = new ScriptEngineManager();  
  15.         ScriptEngine jsEngine = engineMgr.getEngineByName("ECMAScript");  
  16.         try {  
  17.             jsEngine.eval("importPackage(javax.swing);" + "var optionPane = "  
  18.                     + "  JOptionPane.showMessageDialog(null, 'Hello, world!');");  
  19.         } catch (ScriptException ex) {  
  20.             ex.printStackTrace();  
  21.         }  
  22.     }  
  23. }  
Supplement: 
W3Schools.com > JavaScript tutorial 
jrunscript - command line script shell 
Wiki > Rhino (JavaScript engine)

[ Python 文章收集 ] Timing and Profiling in IPython

Source From  Here   Preface   Timing and profiling code is all sorts of useful, and it’s also just good ol’ fashioned fun ( and sometimes s...