Home On The Range

คิดอะไรไม่ออก ลอกโจทย์ Code Golf มาเล่นกันดีกว่า

โจทย์ง่ายๆ คือให้ input เป็น string ของเลขจำนวนเต็มที่เรียงจากน้อยไปมาก ปัญหาคือถ้ามีเลขที่ติดกันเช่น 1 2 3 ต้องแปลงเป็นช่วง 1-3 อะไรอย่างนี้

ยกตัวอย่าง

"1 2 4 5 6 8 10" => "1-2 4-6 8 10"
"3 5 7 101 102 103" => "3 5 7 101-103"

เขียนด้วย ML ยาวมาก กว่าจะแปลงไปแปลงมาระหว่าง string กับ int

ฟังก์ชันที่น่าสนใจหน่อยคงเป็น toRangeList รับลิสต์ของ int แล้วก็มาจับเป็น range ตัวอย่างเช่น ถ้าสั่ง

- toRangeList([1,2,3,5,6,10,14,15,16]);
ได้ผลลัพธ์เป็น val it = [(1,3),(5,6),(10,10),(14,16)] : (int * int) list

ที่เหลือก็สำหรับแปลงไปแปลงมา

fun toRangeList([]) = []
  | toRangeList([x]) = [(x,x)]
  | toRangeList(x::xs) = let
	val y::ys = toRangeList(xs)
	val (f,t) = y
    in
	if x = (f-1) then
	    (x,t)::ys
	else
	    (x,x)::y::ys
    end;
 
fun toIntList(st) = let
    val stlist = String.tokens (fn c => (c = #" ")) st
    fun f([]) = []
      | f(x::xs) = let
	    val SOME x = Int.fromString(x)
	in 
	    x::f(xs) 
	end
in
    f(stlist)
end;
 
fun tupleToPrettyString(x,y) = 
    if x=y then 
	Int.toString(x)
    else 
	Int.toString(x) ^ "-" ^ Int.toString(y);
 
fun toPrettyString([]) = ""
  | toPrettyString([(x,y)]) = tupleToPrettyString(x,y)
  | toPrettyString((x,y)::xs) = let
	val st = toPrettyString(xs)
    in
	tupleToPrettyString(x,y) ^ " " ^ st
    end;
 
fun home(st) = let 
    val ilist = toIntList(st)
    val rlist = toRangeList(ilist)
in
    toPrettyString(rlist)
end;

[เข้าไปดูในเว็บ code golf มา.... พวกสั้น ๆ เขียนด้วย perl หมดเลยนี่นา]
^^^ ดูผิด มันมีให้ดูแยกภาษา แต่ว่า perl ก็สั้นสุดอยู่ดี

dynamic type ของ perl นี่มัน powerful (และ evil) มากครับ

sugree's picture

อยากลองเขียนบ้าง วิธีเหมือนกันเป๊ะ แต่เป็น Python รับรองว่าช้าแน่ๆ ก๊อปกันหลายรอบ

def range_list(l):
    x,xs = l[0],l[1:]
    if not x:
        return []
    elif not xs:
        return [(x,x)]
    else:
        l2 = range_list(xs)
        y,ys = l2[0],l2[1:]
        f,t = y
        if x == f-1:
            return [(x,t)]+ys
        else:
            return [(x,x),y]+ys
 
def home1(s):
    ilist = map(int,s.split(' '))
    rlist = range_list(ilist)
    def string_range(x):
        a,b = x
        if a == b:
            return '%d' % a
        return '%d-%d' % (a,b)
    slist = map(string_range,rlist)
    return ' '.join(slist)
 
p1 = "1 2 4 5 6 8 10"
p2 = "3 5 7 101 102 103"
 
print home1(p1)
print home1(p2)

เอาบ้าง (haskell)
ใช้ argument ที่ 2 เป็นตัวทด, ตัวที่ 3 เป็น accumulate

solve:: [Int] -> [(Int,Int)]
solve  (x:xs)        = solve' xs (x,x) []
 
solve':: [Int] -> (Int,Int) -> [(Int,Int)]
      -> [(Int,Int)]
 
solve' [] (x,y) z    = reverse  ((x,y) : z)
solve' (x:xs) (x',y') z
       | x == (y' + 1) = solve' xs (x', x) z
       | otherwise     = solve' xs (x , x) ((x', y'):z)
*Main> solve [1,2,3,4,7,9,11,12,14,15]
[(1,4),(7,7),(9,9),(11,12),(14,15)]

เนียนมากๆ

ผมชอบ toRangeList ของอาจารย์มะนาวมากกว่านะ สวยดี

ส่วน declare type มันรุงรังไปหน่อย
สามารถเขียนแบบนี้แทนได้
(พึ่งอ่านเจอ)

solve :: Num a => [a] -> [(a,a)]
 
solve':: Num a => [a] -> (a,a) -> [(a,a)]
      -> [(a,a)]

เท่าที่ทราบเหมือน Haskell มันทำ type inference ได้เอง (ตอนที่ผมลอง ๆ เขียนมันก็ทำให้)
ทีนี้ เท่าที่สังเกตโปรแกรมคุณ pphetra จะ declare type มาด้วย ก็เลยสงสัยว่า ถ้าไม่ declare เลยมันจะได้หรือเปล่าอ่ะครับ?

ไม่ใส่ก็ run ได้ครับ

แต่ที่ใส่ไว้ เพราะรู้สึกว่ามันเป็น visualize tool ชนิดหนึ่งครับ
ช่วยให้ทบทวน code ได้ดียิ่งขึ้น

veer's picture

ocaml หละ

type r = {s: int; e: int};;
 
let find_range seq = 
  let merge_range a n = match a with      
      x::xs when x.e + 1 == n -> {s = x.s; e = n}::xs
    | [] | _ -> {s = n; e = n}::a
  in
    List.rev (List.fold_left merge_range [] seq)
;;
 
let pretty seq = 
  let pretty_r r_ = 
    if r_.s == r_.e then
      string_of_int r_.s
    else
      (string_of_int r_.s) ^ "-" ^ (string_of_int r_.e)
  in
  let rec join seq = match seq with 
      x::xs -> 
	if List.length xs == 0 then 
	  x 
	else 
	  x ^ " " ^ (join xs)
    | _ -> ""
  in
    join (List.map pretty_r seq)
;;
 
let _ = print_endline (pretty (find_range [1;2;3;5;6;10;14;15;16]));;

โอ้ดู code ocaml นี่ต้องเอามือกุมหัว แล้วอ่านออกเสียง
(ด้วยยังไม่คุ้นกับ syntax)

veer's picture

ผมเขียนมั่วด้วยหละครับ ถ้าผมเขียนคล่อยๆแล้ว(คงมีซักวัน) ก็น่าจะอ่านง่ายขึ้นด้วย

มึนสุดยอดเหมือนกัน ผมเลยไปอ่านตารางเทียบระหว่าง SML กับ Ocaml มา (ดูที่นี่)

ตอนแรกดูแล้วจะงงตรง match ว่าคืออะไร ทำไปทำมา match มันเป็นเหมือน syntax ในการทำ pattern matching เลย แต่มันมีตรงที่เพิ่ม when เข้ามาด้วย

let find_range seq =
  let merge_range a n = match a with
      x::xs when x.e + 1 == n -> {s = x.s; e = n}::xs
    | [] | _ -> {s = n; e = n}::a
  in
    List.rev (List.fold_left merge_range [] seq)
;;

อย่างข้างบนทำ pattern matching a กับ x::xs, [] แล้วก็ _

sugree's picture

ไม่มีใครเขียน Perl ซะหน่อยเหรอครับ

php

$num=$_SERVER['QUERY_STRING'];//รับค่าแบบ file.php?ตัวเลข
$num=split(" ",$num);//แบ่งข้อมูลเป็น array คั่นด้วยวรรค
$i=0;
$temp=0;
while($i<=count($num)){
$temp=$i+1;
if($num[$i]+1==$num[$temp]){
$num[$i]=$num[$i]."-".$num[$temp];
unset($num[$temp]);
$i++;
}
print_r($num);

แบบนี้จะได้แค่ 2 ตัวเช่น
1 2 3 4 5 = Array[[0]=1-2[1]=3-4[2]=5]

ไพธอนแบบโบราณครับ

def range_list(s):
  slist=s.split(' ')
  n=len(slist)
  i=0
  newlist=[]
  while i<n:
    j=i+1
    k=i
    while j<n and int(slist[j])==int(slist[k])+1:
      k=j
      j=j+1
    if k==i:
      newlist.append(slist[i])
      i=i+1
    else:
      newlist.append(slist[i]+'-'+slist[k])
      i=k+1
  return ' '.join(newlist)

>>> print range_list("1 2 4 5 6 8 10")
1-2 4-6 8 10
>>> print range_list("3 5 7 101 102 103")
3 5 7 101-103

ของผมเขียนด้วยจาวาคงไม่เป็นไรใช้ไม่เป็นไรใช่ไหมครับ

>
class GroupRange {
	static int[] splitToInt(String str)
	{
		String [] strArray;
		strArray = str.split(" ");
		int [] intArray = new int[strArray.length];
		int i = 0;
		for(String s:strArray)
		{
			intArray[i] = Integer.parseInt(s);
			i++;
		}
		return intArray;
	}
	static String solve(String str)
	{
		StringBuffer output = new StringBuffer();
		int[] intArray = splitToInt(str);
		int start,end,a,b;
		start = 0;
		end   = 0;
		a = 0;
		b = 1;
		output.append(intArray[a]);
 
		while(b < intArray.length)
		{
			if ((intArray[b]-intArray[a]) > 1)
			{
				if ((end - start)>0)
				{
					output.append("-");
					output.append(intArray[end]);
				}
				output.append(" ");
				output.append(intArray[b]);
				a = b;
				b++;
				start = end = a;
			}else
			if ((intArray[b]-intArray[a]) == 1)
			{
				b++;
				a++;
				end++;
			}
			else b++;
		}
		if((end-start)>0)
		{
			output.append("-");
			output.append(intArray[end]);
		}
		return output.toString();
	}
	public static void main(String[] args)
	{
				System.out.println(solve("1 2 4 5 6 8 10"));
				System.out.println(solve("3 5 7 101 102 103"));
	}
 
}
</blockcode>

else if วาง layout ได้แปลกตาดีครับ

Groovy ครับ

def solve(str) {
  def a = str.split(/\s+/).collect { Integer.valueOf(it) }
 
  def result = []
  def idx = (0..<(a.size()-1)).grep{ a[it].next() != a[it+1] }
  [*idx, a.size()-1].inject(0) { from, to ->
    result << (a[from]..a[to])
    to.next()
  }
 
  result.collect{ (it.from - it.to)? "$it.from-$it.to" : it.from }.join(' ')
}
 
assert "1-2 4-6 8 10" == solve("1 2 4 5 6 8 10") 
assert "3 5 7 101-103" == solve("3 5 7 101 102 103")

>> def idx = (0..<(a.size()-1)).grep{ a[it].next() != a[it+1] }
>> [*idx, a.size()-1].inject(0) { from, to ->
สวยดี

อยากให้แต่ละคนที่ตอบ อธิบาย แนวคิด concept ที่ให้ในการแก้โจทย์ หน่อยหนะครับ
แบบคร่าวๆ ก็ยังดี เพราะว่า บางที เห็นแต่โค้ด แต่ว่า มันหลายภาษา ผมก็ไม่เป็นทุกภาษา
แต่อยากรู้แนวคิดที่ใช้แก้โจทย์ ที่มันสอดคล้องกับภาษาที่ทุกๆคนใช้แก้โจทย์หนะครับ

อืม น่าสนใจนะครับ นอกจากแนวคิดแล้ว ผมเห็นหลายๆ ฟอรั่มมีการทดสอบประสิทธิภาพการทำงานอย่างง่ายๆ ให้เห็นกันด้วย

เห็นด้วยนะครับ... (ต้องไปเขียนอันเก่า ๆ ด้วยหรือเปล่า?)

xce1's picture

PHP แบบถึกๆ ครับ

>
<?
$b = explode(" ", $input); // ระเบิด string เป็น array
$out=$b[0];
$flag=TRUE; //flag ตัวนี้เอาไว้บอกว่ามี serie ต่อหรือไม่ ผมสลับ TRUE กับ FALSE เพื่อความง่ายในการใช้ IF
for($i=0;$i<=count($b);$i++)
{
	if (($b[$i+1]-$b[$i])==1 && ($flag))
	{
		$out=$out."-";
		$flag=!$flag;
	}
	elseif ($b[$i+1]-$b[$i]>1)
	{
		if($flag)
			$out=$out." ".$b[$i+1];
		else
		{
			$flag=!$flag;
			$out=$out.$b[$i]." ".$b[$i+1];
		}
	}
}
if (!$flag)
	$out=$out.$b[count($b)-1];
echo $out;
?></blockcode>
โดย $out เป็น output ครับ กระทู้ตั้งกันต้นปี ตอบเอาปลายปี แหะๆ

กระทู้นานมากครับ แต่เพิ่งอ่านเจอ ขอเล่นด้วยคน

def home(input):
	output=''
	for i in map(int,input.split()):
		output=(output+'%d, '%i).replace('%d, '%(i-1),'%d-'%(i-1)).replace('-%d-'%(i-1),'-')
	return output[:-2]+'.'
print home("1 2 4 5 6 8 10")
print home("3 5 7 101 102 103")

wow เจ่งครับ

sugree's picture

โห คิดได้ไง

เจ๋งอะครับ คิดไปได้

นึกว่าง่าย… เขียนไปเขียนมา ก็ไม่ต่างจะข้างบน C# ครับ

    static string Test2(string input) {
        String output = "";
        int i=1,j;
        string[] a = input.Split(' ');
        while (i < a.Length) {
            output += a[i-1];
            for (j = i; j < a.Length && (int.Parse(a[j]) - int.Parse(a[j - 1]) == 1); j++) {
                //
            }
            if (i != j) {
                output += "-" + a[j - 1] + " ";
            } else {
                output += " ";
                if (j + 1 >= a.Length) {
                    output += a[j];
                }
            }
            i=++j;
        }
        return output;
    }
    static void Main(string[] args) {
        String a = "1 2 4 5 6 8 10";
        String b = "3 5 7 101 102 103";                        
        System.Console.WriteLine(Test2(a));
        System.Console.WriteLine(Test2(b));            
    }

โจทย์นี้หลายชาติแล้วเพิ่งจะเห็นอีกแล้ว คงจะยังไม่ช้าเกินไป :P
ลองเล่นๆดูเขียนด้วย Ruby ออกมายังงี้

str = "1 2 4 5 6 8 10"
def home str
     a = str.split
    (0...a.length).each do |n|
      previous_result = a[n].to_i - a[n-1].to_i == 1 ? true:false if n != 0
      result = a[n+1].to_i - a[n].to_i == 1 ? true:false
      next_result = a[n+2].to_i - a[n+1].to_i == 1 ? true:false if n+2 != a.length
      first_true = previous_result == false ? true:false if result and n != 0
      last_true = next_result == false ? true:false if result and n != a.length
      print "#{a[0]}-" if result and n == 0
      print "#{a[n]}-" if first_true
      if last_true then
         print "#{a[n+1]} "  
         @dup = a[n+1] 
      end
      print " #{a[n]} " if result == false and a[n] != @dup 
    end
end
home str

อนาถตัวเองจริงๆ
ป.ล. เดี๋ยวมาแก้ตัวอีกที
ป.ล. 2 พี่ป็อกชี้แนะด้วย

เริ่มด้วยลดความรุงรังของ to_i ก่อน

เปลี่ยนจาก
 a = str.split
เป็น
 a = str.split.map {|x| x.to_i}

แฮะๆ.. ลืม map,collect etc. พวกนี้ไปได้เรา
ขอบคุณครับพี่

เอ.. แล้วที่โพสต์ไปมันแก้ไม่ได้เหมือนใน blognone เหรอ

sugree's picture

ถ้ามีคน reply จะแก้ไม่ได้

krab

ไปเจอ module itertools (http://docs.python.org/lib/itertools-example.html)
เขามี function groupby ให้ใช้

ลองเขียนดูแล้ว มันมายาวตอนทำสวยนี่แหล่ะ

from itertools import *
 
prob = "1 2 4 5 6 8 10"
 
prob_int_ary = map(int,  prob.split(' '))
groups = groupby(enumerate(prob_int_ary), lambda (i,x): i-x)
 
def pretty_result(iter):
  for tmp in iter:
    if (tmp[0] == tmp[1]):
      yield str(tmp[0])
    else:
      yield "%s-%s" % (tmp[0], tmp[1])
 
print ' '.join(pretty_result(map(lambda l: (l[0][1], l[-1][1]), map(lambda(k,g): list(g), groups))))

? ใครช่วยทำให้ pretty_result มันสวยขึ้นกว่านี้หน่อย

roofimon's picture

พี่ป๊อกขอ scala ด้วยครับ

ย้าย Codenone

ประกาศย้าย Codenone ไปใช้ Forum ของ Blognone แทนครับ ตามไปตั้งกระทู้ต่อได้ที่ Codenone Forum (รายละเอียดอ่านจากกระทู้ ย้าย Codenone ไปรวมกับ Blognone)

กระทู้เก่าๆ จะย้ายตามไปในภายหลัง ตอนนี้ปิดการโพสต์กระทู้ไว้ เหลือไว้เฉพาะอ้างอิงเท่านั้น