回答編集履歴
4
バグ修正
answer
CHANGED
|
@@ -85,9 +85,9 @@
|
|
|
85
85
|
return 1 << (n - 1)
|
|
86
86
|
|
|
87
87
|
def numlist(lst): # 数列をビットパターンのリストに変換
|
|
88
|
-
return list(map(
|
|
88
|
+
return list(map(bitpattern,lst))
|
|
89
89
|
|
|
90
|
-
def bitmask(m): # すべての数の
|
|
90
|
+
def bitmask(m): # すべての数の論理和
|
|
91
91
|
return functools.reduce(lambda x, y: x | y, m)
|
|
92
92
|
|
|
93
93
|
def numofbits5(bits): # 1のビットの数を数える http://www.nminoru.jp/~nminoru/programming/bitcount.html
|
|
@@ -100,23 +100,20 @@
|
|
|
100
100
|
#print(source)
|
|
101
101
|
length = len(source) # リストの長さ
|
|
102
102
|
mlist = numlist(source) # ビットパターンのリスト
|
|
103
|
-
ncount = numofbits5(bitmask(mlist)) # 数の種類(n個)
|
|
103
|
+
ncount = numofbits5(bitmask(mlist)) # 数の種類(n 個)
|
|
104
|
-
(s,e) = (0,length
|
|
104
|
+
(s,e) = (0,length) # 直近の結果のインデックス（最短リスト）
|
|
105
105
|
i = 0
|
|
106
|
-
while i < length - ncount:
|
|
106
|
+
while ((e-s+1) != ncount) and (i < length - ncount + 1):
|
|
107
|
-
mm = 0
|
|
107
|
+
mm = 0
|
|
108
|
-
for j in range(i, min(length, i+e-s)): #
|
|
108
|
+
for j in range(i, min(length, i+e-s)): # 最短リスト - 1 の長さしか調べない
|
|
109
|
-
i = j if mm ^ mlist[j] == 0 else i #
|
|
109
|
+
i = j if mm ^ mlist[j] == 0 else i # 先行する数字を無視できるか？
|
|
110
110
|
mm |= mlist[j] # 累積ビットパターン
|
|
111
111
|
if numofbits5(mm) == ncount: # n 個揃った
|
|
112
|
-
#print("+:{0},{1} = {2}".format(i,j,j-i+1))
|
|
112
|
+
#print("+:{0},{1} = {2}".format(i,j,j-i+1))
|
|
113
|
-
# i = k # k は不要
|
|
114
113
|
s,e = (i,j) if (j-i) < (e-s) else (s,e)
|
|
115
114
|
break
|
|
116
115
|
#else:
|
|
117
116
|
#print("-:{0},{1}".format(i,j))
|
|
118
|
-
if (e-s+1) == ncount: # 最短なのは明らか
|
|
119
|
-
break
|
|
120
117
|
i += 1
|
|
121
118
|
return (s,e)
|
|
122
119
|
```
|
|
@@ -132,11 +129,11 @@
|
|
|
132
129
|
return max(0,i-1)
|
|
133
130
|
|
|
134
131
|
def trimright(ilist): # 右端の重複を排除
|
|
135
|
-
e = ilist[-1]
|
|
132
|
+
e, leng = ilist[-1], len(ilist)
|
|
136
|
-
for i in range(-1, (-1) -
|
|
133
|
+
for i in range(-1, (-1) - leng, -1):
|
|
137
134
|
if e != ilist[i]:
|
|
138
135
|
break
|
|
139
|
-
return min(
|
|
136
|
+
return min(leng+i+1,leng-1)
|
|
140
137
|
```
|
|
141
138
|
|
|
142
139
|
### 修正点 (2019-03-24)
|
|
@@ -157,4 +154,12 @@
|
|
|
157
154
|
print(findShortest("123455551115555555555"))
|
|
158
155
|
print(findShortest("33123456521223456"))
|
|
159
156
|
print(findShortest("123345561234456"))
|
|
160
|
-
```
|
|
157
|
+
```
|
|
158
|
+
### 修正点 (2019-03-25)
|
|
159
|
+
- numlist のラムダ式が冗長なので削除。
|
|
160
|
+
- 直近の結果のインデックス（最短リスト）の初期値を length-1 から length に変更。
|
|
161
|
+
- i の上限に +1
|
|
162
|
+
- while 条件を変更。一度もループしない場合があります。
|
|
163
|
+
- ソースコードをすべて最新に置き換え。
|
|
164
|
+
|
|
165
|
+
あれこれ考えた結果、バグが多なりました。申し訳ありません。なにかのお役に立てれば。
|
3
ソースコードを修正しました。
answer
CHANGED
|
@@ -104,13 +104,13 @@
|
|
|
104
104
|
(s,e) = (0,length-1) # 直近の結果のインデックス（最短リスト）
|
|
105
105
|
i = 0
|
|
106
106
|
while i < length - ncount:
|
|
107
|
-
mm, k = 0, i
|
|
107
|
+
mm = 0 # mm, k = 0, i
|
|
108
|
-
for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
|
|
108
|
+
for j in range(i, min(length, i+e-s)): # for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
|
|
109
|
-
k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
|
|
109
|
+
i = j if mm ^ mlist[j] == 0 else i # k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
|
|
110
110
|
mm |= mlist[j] # 累積ビットパターン
|
|
111
111
|
if numofbits5(mm) == ncount: # n 個揃った
|
|
112
|
-
#print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
|
|
112
|
+
#print("+:{0},{1} = {2}".format(i,j,j-i+1)) # print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
|
|
113
|
-
i = k
|
|
113
|
+
# i = k # k は不要
|
|
114
114
|
s,e = (i,j) if (j-i) < (e-s) else (s,e)
|
|
115
115
|
break
|
|
116
116
|
#else:
|
|
@@ -132,9 +132,29 @@
|
|
|
132
132
|
return max(0,i-1)
|
|
133
133
|
|
|
134
134
|
def trimright(ilist): # 右端の重複を排除
|
|
135
|
-
e,r = ilist[-1],[]
|
|
135
|
+
e = ilist[-1] # e,r = ilist[-1],[]
|
|
136
136
|
for i in range(-1, (-1) - len(ilist), -1):
|
|
137
137
|
if e != ilist[i]:
|
|
138
138
|
break
|
|
139
139
|
return min(len(ilist)+i+1,len(ilist)-1)
|
|
140
|
+
```
|
|
141
|
+
|
|
142
|
+
### 修正点 (2019-03-24)
|
|
143
|
+
- k を削除する。i を直接変更することで、探索失敗後の探索を効率化。
|
|
144
|
+
- 「最短リストの長さ」しか調べないを「最短リストの長さ - 1」に変更。
|
|
145
|
+
- 「右端の重複を排除」の変数を修正。
|
|
146
|
+
- 例を追加。
|
|
147
|
+
|
|
148
|
+
```python3
|
|
149
|
+
def findShortest(numstr):
|
|
150
|
+
return findMinList(list(map(int, numstr)))
|
|
151
|
+
|
|
152
|
+
print(findShortest("11222314113351413141121511"))
|
|
153
|
+
print(findShortest("12223141133514131411215111111111111"))
|
|
154
|
+
print(findShortest("11222314113351413141144444444444444421511"))
|
|
155
|
+
print(findShortest("2314113351413123141133511"))
|
|
156
|
+
print(findShortest("1233455654321234456"))
|
|
157
|
+
print(findShortest("123455551115555555555"))
|
|
158
|
+
print(findShortest("33123456521223456"))
|
|
159
|
+
print(findShortest("123345561234456"))
|
|
140
160
|
```
|
2
ビットを数える解を追記
answer
CHANGED
|
@@ -61,4 +61,80 @@
|
|
|
61
61
|
簡単な動作確認を行いましたが詳細まで詰めきれていません。問題点をご指摘ください。
|
|
62
62
|
|
|
63
63
|
### 結論 (2019-03-21)
|
|
64
|
-
数字が未知であり、もっとも右端、もっとも左端だけの探索なら早いのですが、**中央の部分リスト**の効率的な探索方法を見つけられませんでした。再帰呼出しの数は文字列の長さに比例して増えてしまいます。未熟なアイデアでした。
|
|
64
|
+
数字が未知であり、もっとも右端、もっとも左端だけの探索なら早いのですが、**中央の部分リスト**の効率的な探索方法を見つけられませんでした。再帰呼出しの数は文字列の長さに比例して増えてしまいます。未熟なアイデアでした。
|
|
65
|
+
|
|
66
|
+
### ビットを数える解 (2019-03-22)
|
|
67
|
+
|
|
68
|
+
敗北の証として、ビット 1 を数えることで数が揃っていることを判定するプログラムを書きました。概要は以下のとおり。
|
|
69
|
+
|
|
70
|
+
- 1-N の数字は未知である。数字は連続していなくてもよいが、1 -32 までしか許さない。
|
|
71
|
+
- 前処理で、数字 n を 32 ビットのパターンに置き換える。数字ごとにワードの n-1 番目のビットを 1 にする。
|
|
72
|
+
- 前処理で、使われるすべての数字のビットパターンの論理和と個数 K を調べる。
|
|
73
|
+
- 調査対象の数列のビットパターンの論理和をとり、ビットの個数が K なら数字が揃っていると判断する。
|
|
74
|
+
- 直近の最短リストのインデックスを持たせる。最短インデックスが更新される都度、探索の長さが短くなる。
|
|
75
|
+
- 先に同じ数字が出現した場合、排他的論理和を使って無視できるか判定する。(不完全ですが ... )
|
|
76
|
+
|
|
77
|
+
ビットの個数を数える方法は、以下の「バージョン5」を引用しました。
|
|
78
|
+
[ビットを数える・探すアルゴリズム](http://www.nminoru.jp/~nminoru/programming/bitcount.html)
|
|
79
|
+
|
|
80
|
+
```python3
|
|
81
|
+
import functools
|
|
82
|
+
def findMinList(source):
|
|
83
|
+
|
|
84
|
+
def bitpattern(n): # n-1番目のビットをon
|
|
85
|
+
return 1 << (n - 1)
|
|
86
|
+
|
|
87
|
+
def numlist(lst): # 数列をビットパターンのリストに変換
|
|
88
|
+
return list(map(lambda x: bitpattern(x),lst))
|
|
89
|
+
|
|
90
|
+
def bitmask(m): # すべての数のビットの論理和
|
|
91
|
+
return functools.reduce(lambda x, y: x | y, m)
|
|
92
|
+
|
|
93
|
+
def numofbits5(bits): # 1のビットの数を数える http://www.nminoru.jp/~nminoru/programming/bitcount.html
|
|
94
|
+
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
|
|
95
|
+
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
|
|
96
|
+
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
|
|
97
|
+
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
|
|
98
|
+
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
|
|
99
|
+
|
|
100
|
+
#print(source)
|
|
101
|
+
length = len(source) # リストの長さ
|
|
102
|
+
mlist = numlist(source) # ビットパターンのリスト
|
|
103
|
+
ncount = numofbits5(bitmask(mlist)) # 数の種類(n個)
|
|
104
|
+
(s,e) = (0,length-1) # 直近の結果のインデックス（最短リスト）
|
|
105
|
+
i = 0
|
|
106
|
+
while i < length - ncount:
|
|
107
|
+
mm, k = 0, i
|
|
108
|
+
for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
|
|
109
|
+
k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
|
|
110
|
+
mm |= mlist[j] # 累積ビットパターン
|
|
111
|
+
if numofbits5(mm) == ncount: # n 個揃った
|
|
112
|
+
#print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
|
|
113
|
+
i = k
|
|
114
|
+
s,e = (i,j) if (j-i) < (e-s) else (s,e)
|
|
115
|
+
break
|
|
116
|
+
#else:
|
|
117
|
+
#print("-:{0},{1}".format(i,j))
|
|
118
|
+
if (e-s+1) == ncount: # 最短なのは明らか
|
|
119
|
+
break
|
|
120
|
+
i += 1
|
|
121
|
+
return (s,e)
|
|
122
|
+
```
|
|
123
|
+
### 探索回数を減らす
|
|
124
|
+
改善案として、前処理で左端と右端の重複する数字の無視をあげておきます。
|
|
125
|
+
|
|
126
|
+
```python3
|
|
127
|
+
def trimleft(ilist): # 左端の重複を排除
|
|
128
|
+
s = ilist[0]
|
|
129
|
+
for i in range(len(ilist)):
|
|
130
|
+
if s != ilist[i]:
|
|
131
|
+
break
|
|
132
|
+
return max(0,i-1)
|
|
133
|
+
|
|
134
|
+
def trimright(ilist): # 右端の重複を排除
|
|
135
|
+
e,r = ilist[-1],[]
|
|
136
|
+
for i in range(-1, (-1) - len(ilist), -1):
|
|
137
|
+
if e != ilist[i]:
|
|
138
|
+
break
|
|
139
|
+
return min(len(ilist)+i+1,len(ilist)-1)
|
|
140
|
+
```
|
1
結論を追加
answer
CHANGED
|
@@ -55,7 +55,10 @@
|
|
|
55
55
|
|
|
56
56
|
### 自己評価
|
|
57
57
|
- できれば、インデックスの分布表を一度だけ作成し、それを複製、変形することで解を得たい。
|
|
58
|
-
- 数列が短ければ効率が悪いかもしれないが、長くなれば効率がよくなるのではなかろうか。
|
|
58
|
+
- ~~数列が短ければ効率が悪いかもしれないが、長くなれば効率がよくなるのではなかろうか。~~
|
|
59
59
|
- 再帰関数を参照透過にすれば、部分解を得るのに並行処理などが可能になるだろう。
|
|
60
60
|
|
|
61
|
-
簡単な動作確認を行いましたが詳細まで詰めきれていません。問題点をご指摘ください。
|
|
61
|
+
簡単な動作確認を行いましたが詳細まで詰めきれていません。問題点をご指摘ください。
|
|
62
|
+
|
|
63
|
+
### 結論 (2019-03-21)
|
|
64
|
+
数字が未知であり、もっとも右端、もっとも左端だけの探索なら早いのですが、**中央の部分リスト**の効率的な探索方法を見つけられませんでした。再帰呼出しの数は文字列の長さに比例して増えてしまいます。未熟なアイデアでした。
|