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");
}
}
