同値関係を求めるパズルを Squeak Smalltalk で

問題

xxxx=yyyy という形式のデータをたくさん受け取り、等しいもの同士をグルーピングするプログラムを書いてください。

Rubyで同値関係を求めるパズル - rubyco（るびこ）の日記

Set を使って書いてみました。なお、入力は in.txt なるテキストファイルからとし、出力形式は端折ってしまっています。

| in pairs sets line |

in := FileStream fileNamed: 'in.txt'.
pairs := OrderedCollection new.
[(line := in nextLine) notNil] whileTrue: [pairs add: (line subStrings: '=')].
in close.

sets := OrderedCollection new.
pairs do: [:pair |
    | found |
    found := sets
        detect: [:set | pair anySatisfy: [:elem | set includes: elem]]
        ifNone: [sets add: Set new].
    found addAll: pair].

World findATranscript: nil.
sets do: [:each | Transcript cr; show: each asArray sort]

in.txt

b=d
A=B
b=a
B=C
c=b
D=A

出力

#('a' 'b' 'c' 'd')
#('A' 'B' 'C' 'D')

Ruby に直訳。

require "set"

pairs = Array.new
while line = ARGF.gets
  pairs << line.chomp!.split(/=/)
end

sets = Array.new
pairs.each{ |pair|
  found = sets.detect(proc{(sets << Set.new).last}){ |set|
    pair.any?{ |elem| set.include?(elem) } }
  pair.each{ |elem| found << elem }
}

sets.each{ |each| p each.to_a.sort }

出力

["a", "b", "c", "d"]
["A", "B", "C", "D"]

追記
コメント欄にて id:ykoubo さんに教えて頂いたことをうけて修正いたしました。

| in pairs sets line |

in := FileStream fileNamed: 'in.txt'.
pairs := OrderedCollection new.
[(line := in nextLine) notNil] whileTrue: [pairs add: (line subStrings: '=')].
in close.

sets := OrderedCollection new.
pairs do: [:pair |
    | founds marged |
    founds := sets select: [:set | pair anySatisfy: [:elem | set includes: elem]].
    sets removeAll: founds.
    sets add: pair asSet, founds concatenation].

World findATranscript: nil.
sets do: [:each | Transcript cr; show: each asArray sort]

in.txt

a=c
b=d
A=B
b=a
B=C
c=b
D=A

出力

#('a' 'b' 'c' 'd')
#('A' 'B' 'C' 'D')

Ruby 版もあわせて修正。

require "set"

pairs = Array.new
while line = ARGF.gets
  pairs << line.chomp!.split(/=/)
end

sets = Array.new
pairs.each{ |pair|
  founds = sets.select{ |set| pair.any?{ |elem| set.include?(elem) } }
  sets -= founds
  sets << founds.inject(Set[*pair]){ |r,s| r+s }
}

sets.each{ |each| p each.to_a.sort }