วันศุกร์ที่ 30 พฤษภาคม พ.ศ. 2551

Optimizing Treasurehunt's Question 1 (robot)

เมื่อพิจารณาดี ๆ แล้วพบว่าตาราง list สำหรับใช้คำนวณนั้น มีลักษณะสมมาตรบางส่วน เลยปรับปรุงให้ใช้หน่วยความจำในส่วนที่สมมาตรนั้นเพียงครึ่งเดียว ทำให้ลดการใช้หน่วยความจำได้พอสมควร และการคำนวณใน list ย่อย นั้นใช้เพียง list ก่อนหน้าเท่านั้น ดังนั้นพอคำนวณได้ list ปัจจุบันแล้ว ก็ลบ list ก่อนหน้าทิ้งได้ แต่ผมไม่อยากแก้โค้ดมาก เลยเอาแค่เปลี่ยนเป็น list ว่างพอ ผลคือ

a=2000
b=2000

if b>a:
a, b = b, a
d=[]
for i in range(a):
d[i:]=[[]]
if i>=b:
x = b
else:
x = i
for j in range(x+1):
if (i == 0) and (j == 0):
d[i][j:] = [0]
elif (i == 0) or (j == 0):
d[i][j:] = [1]
elif i == j:
d[i][j:] = [d[i][j-1]*2]
else:
d[i][j:] = [d[i][j-1] + d[i-1][j]]
if i>0:
d[i-1]=[]

print d[a-1][b-1]


ผลการรัน โดยใช้ time จับเวลา
415828425864924998634542842325676808706232957586556725463361909680781449739748170
786476583991009842613588566821101566552449812050519515271426829403308897930154848
139000401217874574325171349240478804805012554662232593418186105627855887297242750
191258293109799452562416018445296661723328582808673234975864811354576092306731674
226129026615041968499816993517068588780940662630054770440825519413455865220243087
597454080782838938422451159980693138755678460019308423353936671267937407109197183
261946634690754460222691463521097187455850580048349711806796515481309363032514472
631419167126959879296426641287728281408263950661584874428072352076560611103304329
056994774368533971570942013663930927771345889508878174490486498112868394435125871
368770117617083125252317200772612121394477978635381281677951466408518108004063757
181565789433577065739615351320655283808516684687687348436814782925229015434783262
936635458985024720378317210338353260437300968307371995465273889042991687076670199
592582593447226951517354719649532201876810233809966157181452417833096317816478439
040563226541144136090250318325435743209975329838676879857054480550574759550296644
05427578211111064192312240045083183062752759630345186798202023360000

real 0m6.381s
user 0m5.024s
sys 0m0.076s


ลองแก้ขนาดเป็น 4000x4000 คำตอบยาวมากไม่โพสต์แล้วกัน แต่จับเวลาได้

real	0m59.338s
user 0m27.342s
sys 0m0.148s


ทั้งหมดรันบนแล็ปท็อป AMD Turion64 2.2GHz (1 core), RAM 1GB

Google Treasure Hunt

เล่นมั่ง ๆ

ตอนแรกที่เห็นโจทย์ข้อแรก (robot) สมองกำลังมึน คิดไปมายิ่งปวดหัว เลยเลิกซะ แต่พอเห็นหลาย ๆ คนโพสต์บล็อก เชียร์ว่าไม่ยาก ๆ เอาวะลองดูใหม่ซักตั้ง

เข้าเว็บ http://treasurehunt.appspot.com/ ปุ๊บคราวนี้ได้ข้อ 3 (network) เลย ลองอันนี้ก่อนละกัน พบว่าง่ายมาก ๆ สำหรับคนที่เข้าใจเรื่อง routing table ของระบบเน็ตเวิร์คแบบ TCP/IP หลักการคือดูว่าจากต้นทางจะไปหาปลายทางต้องเดินผ่าน node ไหนบ้าง เช่นผมเริ่มจาก G ต้องไป A ก็ดูว่า ip ของ A คืออะไร แล้วดูในตารางว่า แถว G มี route ไปหา A ไหม ซึ่งดูได้จากคอลัมน์ของ routing 3 คอลัมน์แรก ถ้ามีก็ให้ไป ip นั้นเลย ถ้าไม่มี ให้ไป default route คือคอลัมน์สุดท้าย เช่นของผมไม่มีใน 3 คอลัมน์แรก ก็ให้ดู ip ในคอลัมน์สุดท้ายซึ่งบอกให้ไป ip หนึ่ง ดูในตารางพบว่าเป็นของ H ก็จดในกระดาษว่า GH แล้วก็ทำเช่นเดียวกันไปเรื่อย ๆ สุดท้ายก็พบว่าเส้นทางเดินคือ GHIJKCOLMBA ก็คือคำตอบที่ต้องส่งไป คำถามนี้ใช้เวลา 2-3 นาทีก็เสร็จ ถูกในครั้งแรกเลยด้วย

ย้อนมาทำข้อ 1 (robot) มีตารางขนาดใหญ่อันหนึ่ง หุ่นยนต์อยู่มุมบนซ้าย ปลายทางอยู่มุมล่างขวา ให้หาจำนวนเส้นทางที่หุ่นยนต์สามารถเดินจากมุมบนซ้ายมามุมล่างขวา โดยให้หุ่นยนต์เดินลง หรือเดินไปทางขวาเท่านั้น วิธีคิดน่าจะมี 2 แนวทางคือ ใช้คณิตศาสตร์ คือเรื่องความน่าจะเป็น กับโปรแกรมมิ่งเอาดื้อ ๆ ซึ่งผมเลือกเขียนโปรแกรม ง่ายกว่าสำหรับผม ก่อนอื่นก็หาแพตเทิร์นของมันให้ได้ก่อน โดยค่อย ๆ คิดโดยมองจากมุมล่างขวาซึ่งเป็นปลายทางว่า

ตารางขนาด 1x1 หุ่นยนต์อยู่ที่ตำแหน่งเดียวกับปลายทาง คำตอบ = 0
ตารางขนาด 1x2 คำตอบ = 1
ตารางขนาด 1xn คำตอบ = 1
ตารางขนาด nx1 คำตอบ = 1 เช่นกัน

ตารางขนาด 2x2 คำตอบ = 2
ตารางขนาด 2x3, 3x2 คำตอบ = 3
ตารางขนาด 3x3 คำตอบ = 6

ไล่ต่อไปอีกหน่อย ก็เริ่มจับทางได้ว่า จำนวนวิธีการเดินของตารางขนาด mxn ก็คือ จำนวนวิธีการเดินของตารางขนาด (m-1) x n + จำนวนวิธีการเดินของตารางขนาด m x (n-1)

เขียนให้สวย ๆ ก็ได้ว่า f(m,n) = f(m-1,n) + f(m,n-1) แบบนี้มัน recursive ชัด ๆ ว่าแล้วก็จับ python มาเขียนโค้ด ได้ว่า

def r(a,b):
if (a == 1) and (b == 1):
return 0
elif (a == 1) or (b == 1):
return 1
else:
return r(a-1,b)+r(a,b-1)

m, n = 4, 5
print r(m,n)


ลองค่า m และ n น้อย ๆ ดูแล้วถูกต้องดี อืมม ไม่เลว ๆ แต่พอใส่ค่าจริง ๆ ลงไป คือ 43, 49 ปรากฏว่าเงียบไปนานมาก ดูท่าไม่ดีละ ลองลดลงเหลือ 20, 20 ก็ยังนาน เฮ่ย ไม่ธรรมดาแฮะ แสดงว่าจำนวนทางเดินมันเยอะมาก ทำ recursive ไม่ไหวแล้ว เปลี่ยนมาเป็น array ละกัน

a=43
b=49

d=[]
for i in range(a):
d[i:]=[[]]
for j in range(b):
if (i == 0) and (j == 0):
d[i][j:] = [0]
elif (i == 0) or (j == 0):
d[i][j:] = [1]
else:
d[i][j:] = [d[i][j-1] + d[i-1][j]]

print d[a-1][b-1]


โชคดีที่ python ใช้เลขจำนวนเต็มขนาดใหญ่ได้ทันที เพราะคำตอบของมันคือ 85182187099351463190080550 ส่งคำตอบเข้าไป ผ่านฉลุย (ถ้าใช้โปรแกรมแรกคิด คงหลายวันเสร็จ)

คำถามข้อที่ 2 ให้ดาวน์โหลดไฟล์ .zip มาไฟล์หนึ่ง พร้อมโจทย์

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing stu and ending in .pdf
Sum of line 4 for all files with path or name containing zzz and ending in .js
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)


โอว แบบนี้ต้องเขียนโปรแกรมเท่านั้น และหนทางหาคำตอบที่ดีที่สุดคือ shell programming ครับพี่น้อง ไม่ยากเลย แต่ครั้งแรกตีโจทย์ผิด อ่านไม่ดีเอง คือคิดว่าชื่อแฟ้มมี stu และนามสกุล .pdf เท่านั้น ที่จริงแล้วในชื่อ path ก็ได้ รอบแรกผิดแค่ตรงนี้เอง

มีอีกจุดที่ต้องระวังคือ โจทย์ให้เอาบรรทัดที่ 4 มา แต่ถ้าจำนวนบรรทัดมีไม่ถึง ก็ไม่ต้องเพิ่มค่า sum ดีที่โจทย์เตือนไว้ เพราะไม่อย่างนั้น ถ้าใช้แค่ head + tail จะได้บรรทัดสุดท้ายมาเสมอ โดยอาจจะไม่ใช่บรรทัดที่ 4 ก็ได้ ผลคือได้ shell script หน้าตาอย่างนี้มา

ln1=4
st1="stu"
ext1=".pdf"

ln2=4
st2="zzz"
ext2=".js"

repeat(){
n=1
while [ ${n} -le ${1} ]; do
n=$(($n+1))
echo 0
done
}

s=0
for a in `find . | grep ${st1} | grep ${ext1}$`; do
s=$((`repeat ${ln1} | cat ${a} - | head -n ${ln1} | tail -n 1`+${s}))
done

t=0
for a in `find . | grep ${st2} | grep ${ext2}$`; do
t=$((`repeat ${ln2} | cat ${a} - | head -n ${ln2} | tail -n 1`+${t}))
done

echo "s= ${s}"
echo "t= ${t}"
echo "s*t= $((${s}*${t}))"


ซึ่งผมได้คำตอบคือ 2683982036 ส่งไปในครั้งที่สองก็ถูกต้องเรียบร้อยดี

รออาทิตย์หน้าจะมีคำถามใหม่มาอีก แต่ไม่รู้วันไหน เห็นว่าตอบถูกหมดเป็นคนแรกมีรางวัลให้ ทำอย่างไรจะได้เป็นคนแรกล่ะนี่ เอาน่าเผื่อมีรางวัลปลอบใจเป็น invite ให้ลองใช้ google app engine ก็คงจะดี

วันอังคารที่ 13 พฤษภาคม พ.ศ. 2551

Thai Font Tuning in Hardy 1

ใน Ubuntu Hardy (8.04) มีฟอนต์ไทยใหม่มาให้ใช้ 3 ตัว คือ Waree, Umpush และ Sawasdee โดยเฉพาะ Waree นั้นถูกกำหนดให้เป็นฟอนต์ปริยายแทน Loma แล้ว ดังนั้นเมื่อติดตั้งครั้งแรกจะเป็นหน้าตาฟอนต์แปลกไปไม่คุ้นตา ก็ด้วยเหตุนี้นี่เอง

ในตอนแรกนี้จะปรับแต่งฟอนต์เพียงเล็กน้อย โดยยังคงใช้ Waree เหมือนเดิม ก่อนอื่นมาดูก่อนว่าปัญหาที่เราจะพบคืออะไร

1-default

ดูกันใกล้ ๆ

1-default-1 1-default-2

นี่คือปัญหาที่เราจะพบเมื่อติดตั้ง Hardy สังเกตว่าตัวอักษรขนาดเล็ก หัวจะหายบ้าง รูตรงหัวตันบ้าง รูปทรงผิดเพี้ยนค่อนข้างมาก ส่วนตัวอักษรที่ใหญ่ขึ้นกลับมีปัญหาที่แปลกไปอีกแบบคือเส้นที่บาง ๆ จะหายไป สังเกตตรงประโยคตัวอย่าง

ปัญหานี้เกิดจาก โดยปกติแล้ว Hardy จะกำหนดให้ใช้ font hinting แบบ native คือเป็น hint ที่ฝังมากับฟอนต์เลย เช่นฟอนต์ Bitstream Vera ซึ่งจะแสดงได้สวยงาม คมชัดไม่เบลอในทุกขนาดตัวอักษร ส่วนฟอนต์ที่ไม่มี hint จะยังคงแสดงเบลอ ๆ เหมือนเดิม แต่ฟอนต์ Waree นั้นมี hint อยู่ด้วย แต่อย่างที่ทราบการดีว่าการทำ hint ให้สมบูรณ์นั้นยากมาก ฟอนต์ Waree จึงแสดงออกมาดีที่สุดได้แบบที่เห็น

ทางแก้แบบง่ายคือ ลดระดับของ hint ลงเหลือแค่ระดับ slight หรือ "นิดหน่อย" โดยเลือกเมนู "ระบบ" --> "ปรับแต่งพื้นโต๊ะ" --> "รูปโฉม" แล้วเลือกแท็บ "แบบอักษร" แล้วคลิกปุ่ม "รายละเอียด..." จากนั้นตั้งค่า Hinting เป็น "นิดหน่อย" ตามภาพ

2-font-render-details

ผลคือ

3-screen2

3-screen2-1 3-screen2-2

การตั้งระดับ Hint เป็น slight จะทำให้การเรนเดอร์ฟอนต์เน้นที่รูปทรงของฟอนต์มากกว่าความคมชัด ทำให้เห็นได้อย่างชัดเจนว่ารูปทรงของฟอนต์ถูกต้องสวยงาม แต่ก็มีความเบลอมากเช่นกัน และยังทำให้ฟอนต์ภาษาอังกฤษเบลอไปด้วย

สำหรับท่านที่พอใจกับการตั้งฟอนต์แบบนี้ก็หยุดได้เลยครับ แต่สำหรับผมแล้ว ผมต้องการมากกว่านั้น ผมอยากให้ตัวอักษรภาษาอังกฤษชัดเท่าที่มันจะชัดได้ ในขณะที่ภาษาไทยก็ไม่เพี้ยนถึงขั้นเส้นหาย หัวหาย

ทางออกคือ libfreetype ในปัจจุบันมี autohint ซึ่งเป็นวิธีการเรนเดอร์ฟอนต์โดยไม่ต้องพึ่ง hint ที่มาในตัวฟอนต์เอง แต่จะสร้าง hint อัตโนมัติ ซึ่งตัวหลัง ๆ นี่มันทำได้ดีมาก ๆ แต่เราจะใช้ autohint เฉพาะกับฟอนต์ที่เราต้องการ ในที่นี้คือฟอนต์ภาษาไทยเท่านั้น ฟอนต์ที่มี native hint ดี ๆ อย่าง Bitstream Vera เราจะไม่แตะ จะใช้ native hint เหมือนเดิม

ขั้นแรก สร้างแฟ้ม .fonts.conf ไว้ที่ home ของท่านเองโดยให้มีเนื้อหาดังนี้

<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
<match target="font">
<test name="family">
<string>Loma</string>
<string>Garuda</string>
<string>Norasi</string>
<string>Kinari</string>
<string>Purisa</string>
<string>TlwgMono</string>
<string>TlwgTypewriter</string>
<string>Waree</string>
<string>Umpush</string>
<string>Sawasdee</string>
</test>
<edit name="autohint" mode="assign"><bool>true</bool></edit>
</match>
</fontconfig>


จากนั้นให้ล็อกเอาท์ออกจากระบบ แล้วล็อกอินเข้ามาใหม่ แล้วตั้งค่าฟอนต์ให้เป็นตามภาพนี้

4-font-render-details-full

ผลลัพธ์สุดท้าย

5-screen3

5-screen3-1 5-screen3-2

จะเห็นว่าตัวอักษรภาษาอังกฤษมีความคมชัดเป็นปกติ ส่วนตัวไทยนั้นมีหัวหาง เส้นต่าง ๆ ครบถ้วน อ่านได้ชัดเจนดี มีเพี้ยนบ้างแต่น้อยมาก ๆ

เป็นอย่างไรครับ เห็นความงามของฟอนต์ Waree หรือยัง