2013年6月7日金曜日

シャフラーズ問題の回答 @sys1yagi編

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

 CodeIQで結城 浩さんが出題していた断片情報からデータを復元しよう!に挑戦したので解答をポストします。結果は満点でした。よかつた。今回はすごく簡単でした。30分程度で書き散らかしたのでソースは汚いです。
 

問題


 問題は以下の様なデータから、 aa = 10とかいった風にペアのデータを突き止めろ、というモノでした。てっきりデータ数が膨大だったりするのかと思ってたら1000件程度。サクーッといけました。
 10 22 24 = aa bb cc
 53 33 10 = dd ee aa
 24 33 53 = bb ee dd
 

解答ソース


 上記フォーマットのデータファイルを食わすと、ペアを解析してprintlnする感じのソースです。最初データを見たとき、「連立方程式っぽいな」と思ったんでそういう感じで解くようにしました。
 10 22 24 = aa bb cc
 53 33 10 = dd ee aa
 24 33 53 = bb ee dd
というデータがあった時、aaに着目すると、1行目ではaaの候補は10, 22, 24になります。
んで、2行目と比較すると53, 33, 10のうち10だけが1行目に存在してます。つー事でaa=10だ!という事。そんだけです。
 10 22 24 = aa
 53 33 10 = aa
 ↓重複する数字だけ取り出す
 10 = aa
 あとはデータを読み込んでkey,valueのリストを保持するShufflerクラスのリストを作って、名前の一覧を抽出し、名前に着目しながら1件ずつ特定していく感じ。特定された名前と数字はShufflerクラスにフィードバックして、Shuffler内でそれらの値をリストから削除する、という構造です。今見返すと実装大分汚いですが、大体そんな感じです。

package jp.dip.sys1.shufflers;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    static class Shuffler {
        private List<String> mIdList = new ArrayList<String>();
        private List<String> mNameList = new ArrayList<String>();

        public Shuffler(String[] ids, String[] names) {
            for (String id : ids) {
                this.mIdList.add(id);
            }
            for (String name : names) {
                this.mNameList.add(name);
            }
        }

        public List<String> getIdList() {
            return mIdList;
        }

        public List<String> getNameList() {
            return mNameList;
        }

        public void found(String id, String name) {
            mIdList.remove(id);
            mNameList.remove(name);
        }
        public User getUser(){
            if(mIdList.size() == 1 && mNameList.size() == 1){
                User user = new User(mIdList.get(0), mNameList.get(0));
                found(mIdList.get(0), mNameList.get(0));
                return user;
            }
            return null;
        } 
        @Override
        public String toString() {
            if(mIdList.isEmpty() && mNameList.isEmpty()){
                return null;
            }
            StringBuilder sb = new StringBuilder();
            for (String id : mIdList) {
                sb.append(id + " ");
            }
            sb.append("= ");
            for (String name : mNameList) {
                sb.append(name + " ");
            }
            return sb.toString();
        }
    }

    static class ShufflerFactory {
        public static Shuffler createShuffler(String line) {
            if (line == null) {
                return null;
            }
            String[] pair = line.split(" = ");
            String[] ids = pair[0].split(" ");
            String[] names = pair[1].split(" ");
            Shuffler shuffler = new Shuffler(ids, names);

            return shuffler;
        }
    }

    static class User {
        private String mId;
        private String mName;

        public User(String id, String name) {
            mId = id;
            mName = name;
        }

        public String getId() {
            return mId;
        }

        public String getName() {
            return mName;
        }

        @Override
        public String toString() {
            return mId + " = " + mName;
        }
        @Override
        public int hashCode() {
            return toString().hashCode();
        }
        @Override
        public boolean equals(Object obj) {
            return this.hashCode() == obj.hashCode();
        }
    }

    static class Matcher {
        private String mTargetName = null;
        private List<String> mCandidateIds = new ArrayList<String>();
        private User mUser = null;

        public Matcher(String targetName) {
            mTargetName = targetName;
        }
        public boolean identify(Shuffler shuffler) {
            for (String name : shuffler.getNameList()) {
                if (mTargetName.equals(name)) {
                    if (mCandidateIds.isEmpty()) {
                        for (String id : shuffler.getIdList()) {
                            mCandidateIds.add(id);
                        }
                    } else {
                        List<String> newCandidateIds = new ArrayList<String>();
                        for (String id : shuffler.getIdList()) {
                            if(mCandidateIds.contains(id)){
                                newCandidateIds.add(id);
                            }
                        }
                        mCandidateIds = newCandidateIds;
                    }
                }
            }
            if(mCandidateIds.size() == 1){
                mUser = new User(mCandidateIds.get(0), mTargetName);
                return true;
            }
            else{
                return false;
            }
        }

        public User getUser() {
            return mUser;
        }
    }

    List<Shuffler> loadShufflers(String path) {
        List<Shuffler> list = new ArrayList<Main.Shuffler>();
        FileInputStream fis = null;
        InputStreamReader isr = null;
        BufferedReader br = null;
        try {
            fis = new FileInputStream(path);
            isr = new InputStreamReader(fis);
            br = new BufferedReader(isr);
            String line = null;
            while ((line = br.readLine()) != null) {
                Shuffler shuffler = ShufflerFactory.createShuffler(line);
                if (shuffler != null) {
                    list.add(shuffler);
                } else {
                    System.out.println("error.");
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
                isr.close();
                fis.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return list;
    }

    List<String> treatName(List<Shuffler> list) {
        List<String> names = new ArrayList<String>();
        for (Shuffler shuffler : list) {
            for (String name : shuffler.getNameList()) {
                if (!names.contains(name)) {
                    names.add(name);
                }
            }
        }
        System.out.println(names.size());
        return names;
    }

    public void matching(String path) {
        List<Shuffler> list = loadShufflers(path);
        List<User> users = new ArrayList<Main.User>();
        List<String> names = treatName(list);
        for (String name : names) {
            Matcher matcher = new Matcher(name);
            for (Shuffler shuffler : list) {
                if (matcher.identify(shuffler)) {
                    break;
                }
            }
            User user = matcher.getUser();
            if (user != null) {
                if(!users.contains(user)){
                    users.add(user);
                }
                for (Shuffler shuffler : list) {
                    shuffler.found(user.getId(), user.getName());
                }
            }
        }
        for(Shuffler shuffler : list){
            User user = shuffler.getUser();
            if(user != null){
                if(!users.contains(user)){
                    users.add(user);
                }
                for(Shuffler shuffler2 : list){
                    shuffler2.found(user.getId(), user.getName());
                }
            }
        }
        Collections.sort(users, new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                return Integer.parseInt(o1.getId()) - Integer.parseInt(o2.getId());
            }
        });
        for (User user : users) {
            System.out.println(user);
        }
        List<String> remains = new ArrayList<String>();
        for(Shuffler shuffler : list){
           String remain = shuffler.toString();
           if(remain != null){
               if(!remains.contains(remain)){
                   remains.add(remain);
               }
           }
        }
        for(String remain : remains){
            System.out.println(remain);
        }
    }
    public static void main(String[] args) {
        Main main = new Main();
        //main.matching("shufflers/sample.txt");
        main.matching("shufflers/shufflers.txt");
    }
}

0 件のコメント:

コメントを投稿