仲間はずれの判定 in Haskell DouKaku?

仲間はずれの判定

リストxsが渡されたときに

全部の要素が同じ値である(例：[1, 1, 1, 1])、
一つだけ仲間はずれがある(例：[1, 2, 1, 1, 1])、
その他

を識別する関数を作ってください。また判定後に「全部の要素が同じ値」の場合にはその値、「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。

型にうるさい言語のために：リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。

追記：リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

もっとスリム化できそうですがとりあえず。

import java.util.*;
public class NakamaHazure {
    public static void main(String[] args) {
        check(Arrays.asList(1,1,1,1));    // => [1]
        check(Arrays.asList(1,2,1,1,1));    // => [2,1]
        check(Arrays.asList(1,2,2,1,1));    // => []
        check(Arrays.asList(1,2,2,1,3));    // => []
    }
    private static void check(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> minor = new HashSet<Integer>();;
        Integer major = null;
        for (Integer i : list) {
            if (!set.add(i)) {
                if (major != null && major != i) {
                    System.out.println("[]");
                    return;
                }
                minor.remove(i);
                major = i;
            } else {
                minor.add(i);
            }
        }
        if (set.size() == 1) {
            System.out.println("[" + set.iterator().next() + "]");
        } else if (set.size() == 2) {
            System.out.println("[" + minor.iterator().next() + "," + major + "]");
        } else {
            System.out.println("[]");
        }
    }
}

array_count_values便利ですね。あえて使わないで作ってみる事で便利さを際実感

$a[]= array(1,1,1,1);#1
$a[]= array(1,2,1,1,1);#2
$a[]= array(2,1,2,2);#その他
$a[]= array(1,2,2,2);#その他
$a[]= array(1,1,2,2);#その他
$a[]= array(1,1,2,3);#その他
function check($_array){
    $uniques = sizeof(array_unique($_array));
    switch($uniques){
        case(1):
            return array("仲間"=>array_pop($_array));
        case(2):
            sort($_array);
            #仲間はずれ
            if( $_array[0]!=$_array[1] ){
                return array( "仲間はずれ"=>array_shift($_array),"仲間"=>array_pop($_array) );
            }else if($_array[0]==$_array[1] && $_array[sizeof($_array)-1] != $_array[sizeof($_array)-2] ){
                return array( "仲間はずれ"=>array_pop($_array),"仲間"=>array_shift($_array) );
            }
        default:
            return "その他";
    }


}

foreach( $a as $b ){
    print_r( check($b) ).PHP_EOL;
}

post comment

Posted feedbacks - Haskell

そのまま実装

*Main> classify [1,1,1,1,1]                                                                                                                
("homo",[1])
it :: ([Char], [Integer])                                                                                                                  
*Main> classify [1,1,2,1,1]
("quasi-homo",[1,2])                                                                                                                       
it :: ([Char], [Integer])
*Main> classify [2,1,1,1,1]                                                                                                                
("quasi-homo",[1,2])
it :: ([Char], [Integer])                                                                                                                  
*Main> classify [2,2,1,2,2]
("quasi-homo",[2,1])                                                                                                                       
it :: ([Char], [Integer])
*Main> classify [2,3,2,1,5]                                                                                                                
("hetero",[])
it :: ([Char], [Integer])

otherList :: (Eq a) => [a] -> [a]
otherList (x:xs) = [ y |  y<-xs , y /= x ]

quasiHomo1 :: (Eq a) => [a] -> Bool
quasiHomo1     = (== 1) . length . otherList

quasiHomo2 :: (Eq a) => [a] -> Bool
quasiHomo2 xs  = (== 1) $ (length xs ) - (length $ otherList xs)

quasiHomoList :: (Eq a) => [a] -> [a]
quasiHomoList xs = map head $ [xs] ++ [otherList xs]

homo :: (Eq a) => [a] -> Bool
homo (xs) = xs == [ y | y <- xs , y == (head xs)]

classify :: (Eq a) => [a] ->  ([Char],[a])
classify xs | homo xs = ("homo" , [head xs])
            | quasiHomo1 xs = ("quasi-homo", quasiHomoList xs)
            | quasiHomo2 xs = ("quasi-homo", reverse $ quasiHomoList xs)
            | otherwise = ("hetero",[])

入力リストの長さが0,1,2のときの扱いを
いれたのでちょっとスマートじゃないけど
効率は悪くない(はず)
データ型のフィールドラベルについては
Haskell98の仕様に記述があるので参考にどうぞ。

see: フィールドラベルをもつデータ型

data Case a = Zero 
            | One {first :: a}
            | Two {first, second :: a}
            | Homo {homo :: a} 
            | QuasiHomo {homo, strange :: a}
            | Hetero
  deriving Show

classify :: Eq a => [a] -> Case a
classify []     = Zero
classify (x:xs) = judge (One x) xs

judge c [] = c
judge (One x) (y:ys) 
      | x == y    = judge (Homo x) ys
      | otherwise = judge (Two x y) ys
judge (Homo x) (y:ys)
      | x == y    = judge (Homo x) ys
      | otherwise = judge (QuasiHomo x y) ys
judge (Two x y) (z:zs)
      | x == z    = judge (QuasiHomo x y) zs
      | y == z    = judge (QuasiHomo y x) zs
judge (QuasiHomo x y) (z:zs)
      | x == z    = judge (QuasiHomo x y) zs
judge _ _         = Hetero

{-
*Main> classify [1,1,1,1,1]
Homo {homo = 1}
*Main> classify [1,2,1,1,1]
QuasiHomo {homo = 1, strange = 2}
*Main> classify [1,2,1,2,1]
Hetero
-}

*Main> classify [1,1,1,1,1,1]
("homo",[1])
*Main> classify [1,1,2,1,1,1]
("quasi-homo",[1,2])
*Main> classify [2,1,1,1,1,1]
("quasi-homo",[1,2])
*Main> classify [2,1,4,1,1,1]
("hetero",[])
*Main> classify [2,2,1,1,1,1]
("hetero",[])

import qualified Data.Map as M
import Data.List (sortBy)

classify xs = f M.empty xs
  where f dict xs | M.size dict > 2 = ("hetero",[])
                  | xs == [] = h (g (M.toAscList dict))
                  | otherwise = let x = head xs
                                    n = case M.lookup x dict of Just n  -> succ n; Nothing -> 1
                                in f (M.insert x n dict) (tail xs) 
        g = sortBy (\x y -> snd y `compare` snd x)
        h [(x,_)]         = ("homo",[x])
        h ((x,_):[(y,1)]) = ("quasi-homo",[x,y])
        h _               = ("hetero",[])

要素が大小比較できるという条件付き

import List

classify :: (Ord a) => [a] -> ([Char], [a])
classify xs = case (group . sort) xs of
  [(x:_)]     -> ("homo", [x])
  [[x],(y:_)] -> ("quasi-homo", [x,y])
  [(x:_),[y]] -> ("quasi-homo", [y,x])
  _           -> ("hetero", [])

無限リストでも hetero であることがわかれば止まるのがよいですね。
強引に mapAccumL 使ってみました。

judge c xs = fromJust $ msum $ ys ++ [Just s] where
  (s, ys) = mapAccumL f c xs
  f (One x) y
    | x == y    = (Homo x,        Nothing)
    | otherwise = (Two x y,       Nothing)
  f (Homo x) y
    | x == y    = (Homo x,        Nothing)
    | otherwise = (QuasiHomo x y, Nothing)
  f (Two x y) z
    | x == z    = (QuasiHomo x y, Nothing)
    | y == z    = (QuasiHomo y x, Nothing)
  f (QuasiHomo x y) z
    | x == z    = (QuasiHomo x y, Nothing)
  f _ _         = (Hetero,        Just Hetero)

DouKaku?

仲間はずれの判定

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq