May 30, 2008 at 11:21 · Filed under Public
เมื่อพิจารณาดี ๆ แล้วพบว่าตาราง 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
ลองแก้ขนาดเป็น 4000×4000 คำตอบยาวมากไม่โพสต์แล้วกัน แต่จับเวลาได้
real 0m59.338s
user 0m27.342s
sys 0m0.148s
ทั้งหมดรันบนแล็ปท็อป AMD Turion64 2.2GHz (1 core), RAM 1GB
May 29, 2008 at 23:29 · Filed under Public
เล่นมั่ง ๆ
ตอนแรกที่เห็นโจทย์ข้อแรก (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 แนวทางคือ ใช้คณิตศาสตร์ คือเรื่องความน่าจะเป็น กับโปรแกรมมิ่งเอาดื้อ ๆ ซึ่งผมเลือกเขียนโปรแกรม ง่ายกว่าสำหรับผม ก่อนอื่นก็หาแพตเทิร์นของมันให้ได้ก่อน โดยค่อย ๆ คิดโดยมองจากมุมล่างขวาซึ่งเป็นปลายทางว่า
ตารางขนาด 1×1 หุ่นยนต์อยู่ที่ตำแหน่งเดียวกับปลายทาง คำตอบ = 0
ตารางขนาด 1×2 คำตอบ = 1
ตารางขนาด 1xn คำตอบ = 1
ตารางขนาด nx1 คำตอบ = 1 เช่นกัน
ตารางขนาด 2×2 คำตอบ = 2
ตารางขนาด 2×3, 3×2 คำตอบ = 3
ตารางขนาด 3×3 คำตอบ = 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 ก็คงจะดี
May 12, 2008 at 17:57 · Filed under Public, Ubuntu, ลินุกซ์
ใน Ubuntu Hardy (8.04) มีฟอนต์ไทยใหม่มาให้ใช้ 3 ตัว คือ Waree, Umpush และ Sawasdee โดยเฉพาะ Waree นั้นถูกกำหนดให้เป็นฟอนต์ปริยายแทน Loma แล้ว ดังนั้นเมื่อติดตั้งครั้งแรกจะเป็นหน้าตาฟอนต์แปลกไปไม่คุ้นตา ก็ด้วยเหตุนี้นี่เอง
ในตอนแรกนี้จะปรับแต่งฟอนต์เพียงเล็กน้อย โดยยังคงใช้ Waree เหมือนเดิม ก่อนอื่นมาดูก่อนว่าปัญหาที่เราจะพบคืออะไร
ดูกันใกล้ ๆ
นี่คือปัญหาที่เราจะพบเมื่อติดตั้ง Hardy สังเกตว่าตัวอักษรขนาดเล็ก หัวจะหายบ้าง รูตรงหัวตันบ้าง รูปทรงผิดเพี้ยนค่อนข้างมาก ส่วนตัวอักษรที่ใหญ่ขึ้นกลับมีปัญหาที่แปลกไปอีกแบบคือเส้นที่บาง ๆ จะหายไป สังเกตตรงประโยคตัวอย่าง
ปัญหานี้เกิดจาก โดยปกติแล้ว Hardy จะกำหนดให้ใช้ font hinting แบบ native คือเป็น hint ที่ฝังมากับฟอนต์เลย เช่นฟอนต์ Bitstream Vera ซึ่งจะแสดงได้สวยงาม คมชัดไม่เบลอในทุกขนาดตัวอักษร ส่วนฟอนต์ที่ไม่มี hint จะยังคงแสดงเบลอ ๆ เหมือนเดิม แต่ฟอนต์ Waree นั้นมี hint อยู่ด้วย แต่อย่างที่ทราบการดีว่าการทำ hint ให้สมบูรณ์นั้นยากมาก ฟอนต์ Waree จึงแสดงออกมาดีที่สุดได้แบบที่เห็น
ทางแก้แบบง่ายคือ ลดระดับของ hint ลงเหลือแค่ระดับ slight หรือ “นิดหน่อย” โดยเลือกเมนู “ระบบ” –> “ปรับแต่งพื้นโต๊ะ” –> “รูปโฉม” แล้วเลือกแท็บ “แบบอักษร” แล้วคลิกปุ่ม “รายละเอียด…” จากนั้นตั้งค่า Hinting เป็น “นิดหน่อย” ตามภาพ
ผลคือ
การตั้งระดับ 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>
จากนั้นให้ล็อกเอาท์ออกจากระบบ แล้วล็อกอินเข้ามาใหม่ แล้วตั้งค่าฟอนต์ให้เป็นตามภาพนี้
ผลลัพธ์สุดท้าย
จะเห็นว่าตัวอักษรภาษาอังกฤษมีความคมชัดเป็นปกติ ส่วนตัวไทยนั้นมีหัวหาง เส้นต่าง ๆ ครบถ้วน อ่านได้ชัดเจนดี มีเพี้ยนบ้างแต่น้อยมาก ๆ
เป็นอย่างไรครับ เห็นความงามของฟอนต์ Waree หรือยัง
April 26, 2008 at 00:22 · Filed under Public, Ubuntu, ลินุกซ์, โอเพนซอร์ส
เมื่อวาน Ubuntu 8.04 Hardy Heron ออกอย่างเป็นทางการช่วงเย็น ๆ ในประเทศไทย ซึ่งอันที่จริง ผมก็ได้เอามาติดตั้งใช้งานจริง ตั้งแต่ออกเบต้าแล้ว และอัพเกรดมาเรื่อย ๆ
มีสิ่งที่คาดหวังไว้จำนวนหนึ่งกับ Hardy แต่ยังพบว่ายังไม่พร้อม อันเนื่องจาก Ubuntu กำหนดการออกรุ่นไว้ตามเวลาเป๊ะ ๆ ต่างจาก Debian ที่ออกเมื่อพร้อม จึงเป็นเรื่องปกติที่ Ubuntu รุ่น release อาจจะไม่ได้ทำงานได้ตามที่คาดหวังเสมอไป จึงขอเอาประสบการณ์ที่พบมาเล่าให้ฟัง
- Firefox รุ่นนี้ตั้งธงว่าจะใช้ Firefox 3.0 แต่ก็มีความล่าช้าที่โครงการ Mozilla เองซึ่งในที่สุดแล้วก็เสร็จไม่ทันแน่แล้ว ล่าสุด Firefox 3.0 กำหนดออกประมาณ มิ.ย. 51 ใน Hardy ตั้งใจจะใส่รุ่น 3.0pre แต่ก็ไม่ทัน ดังนั้นรุ่นที่ติดตั้งไปพร้อม Hardy คือ 3.0b5 ซึ่ง บอกตามตรงว่ายังไม่เสถียรพอ ใช้งานปกติ ยังมี crash ให้เห็นเป็นพัก ๆ วันละ 3-5 ครั้ง บางวันต้องถอยไปใช้ firefox-2 แทน แต่ก็อึดอัดกับข้อจำกัดบางอย่าง
ทางออกทาง Hardy จะอัพเกรด Firefox ให้เรื่อย ๆ จนกระทั่งเป็น 3.0 ตัวเต็ม และอัพเกรด minor release ไปเรื่อย ๆ แต่นั่นก็ใช้เวลา อย่างเร็วก็รอรุ่น 3.0pre ซึ่งคงดีกว่านี้พอสมควร แต่ถ้าไม่ไหวจริง ๆ ก็ให้ติดตั้ง firefox-2 ใช้งานไปก่อนได้ ซึ่งเสถียรดีมาก ๆ
- Network Manager 0.6.6 ผมเจอปัญหาอันหนึ่งคือ ถ้าต่อเน็ตด้วย ppp ผ่านโทรศัพท์มือถือที่มี EDGE ไม่ว่าจะหมุนเองด้วยคำสั่ง pppd หรือผ่าน network manager applet สถานะของ network จะยังแสดงเป็น offline อยู่ ซึ่งคุณสมบัติหนึ่งของ network manager คือมันใช้ dbus ในการสื่อสารกับโปรแกรมอื่น ๆ ได้ ปัญหาคือ Firefox 3.0 ดันฉลาดเกิน ขอเช็คสถานะเน็ตเวิร์คกับ network manager ผ่านทาง dbus ทุกครั้งที่เปิดโปรแกรม ถ้าเน็ตเวิร์คไม่พร้อม มันจะปรับไปโหมด offline ให้อัตโนมัติ ทีนี้พอใช้ ppp ต่อเน็ต ก็ต้องคอยยกเลิก offline ทุกครั้งไป
ปัญหานี้ Firefox ไม่รับว่าเป็นบั๊ก แต่โยนไปที่ network manager แทน ซึ่งการขยายขอบเขตการจัดการเน็ตเวิร์คไปถึง ppp นั้น จะอยู่ในแผนของรุ่น 0.7 ซึ่งก็ออกล่าช้าเช่นกัน คนพัฒนาอยู่ Red Hat ซึ่งจะออกมาให้ใช้ทัน Fedora 9 แต่กลับไม่ทันใช้ใน Hardy
ทางออก มีวิธีเลี่ยงปัญหา โดยยกเลิกการ roaming การใช้ Lan แบบสาย แล้วตั้งให้ใช้ Lan แบบ manual ด้วย dhcp จะทำให้ network manager ไม่มีสถานะ offline อีกต่อไป (ผมใช้วิธีนี้อยู่) ส่วน network manager 0.7 จะไม่ถูกอัพเดทใน Hardy แต่คนดูแลแพกเกจรับรองว่า เมื่อรุ่น 0.7 ออก จะเตรียมไว้ให้ใช้ใน backports
- F-Spot ถูกใช้เป็นโปรแกรมหลักสำหรับจัดการรูปภาพในเครื่อง f-spot มีคุณสมบัติเด่น ๆ เรื่องการอัพโหลดรูปภาพไปยังบริการเก็บภาพบนอินเทอร์เน็ตหลายตัวเช่น flickr, picasaweb, gallery และอื่น ๆ อีก จำไม่ได้ละ ในด้านการใช้งานนั้น ดูจงใจให้เหมือน iPhotos ของ Mac ซึ่งก็ทำได้ดีทีเดียว แต่ปัญหาคือยังขาดคุณสมบัติอื่น ๆ ที่เคยมีใน gthumb ที่เป็นตัวหลักใน Ubuntu รุ่นก่อน ๆ เช่นการบราวซ์ดูภาพในโฟลเดอร์ที่ยังดูอืด ๆ แถมมันไม่เรียงลำดับมาให้ และเลือกให้เรียงไม่ได้ด้วย ทำให้เกือบจะไร้ประโยชน์ไปเลยทีเดียว ไม่มีการ prefetch ภาพต่อไปไว้ล่วงหน้า ทำให้ตอนดูภาพต่อไปต้องรอมันประมวลผลสักแป๊บนึงก่อน
ทางออก ติดตั้งโปรแกรมตัวเก่งอย่าง gthumb หรือ gqview เถอะครับ สำหรับคนที่ชอบจัดภาพไว้ใน directory ด้วยตัวเองอย่างผม แล้วจะพบว่ามันสะดวกขึ้นเยอะเลย โดยส่วนตัวชอบ gqview มากกว่า เพราะเล็กและเร็วดี
