UWSCでエンジニアならば1時間以内に解けなければいけない問題を解く

こんぴーた UWSC

1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に | ソフトアンテナブログ
です。
「言語なんてどれも一緒」を公言しているので、面倒そうなUWSCで解いてみた。
（ダサい回答になっても、言い訳できるし！）
1時間はシビアだなぁ。
問4をとりあえず総当たりで解いて、最適化しようと思ったら昼休み終了。
問4、難しいよ。



解説

回答は最後にのせときます。
エラそうに解説書いてて、間違えてたら恥ずかしいですね、、、。

問1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

UWSCにリストはないので、配列想定で。
これは簡単。

問2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

これも簡単だね。
一応、配列の長さが違う場合も処理してみた。
SLICEとJOIN/SPLITを使って生成するのもよかったかもしれん。

問3

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

楽勝が続きます。
、、、と思ったら最初のつまづき。
UWSCはdoubleでした。
フィボナッチ、溢れてくれます。
桁あふれ処理が面倒でした。

問4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

これ最悪。
とりあえず問5見てやってから、考えるのが面倒だったので総当たりで処理しました。
これさ、[503,50,1,9]とかだと、「9505031」じゃない。（503と50に注目）
短い方が先とか思うけど、[506,50,1,9]だと、「9506501」になる。
じゃあ、ってんで、配列の全パターンの効率的な並べ替え考えてたけど、、、時間切れになった。
短い場合のパディングを自身の先頭の数字で行えばよかったかな？
（いや、ダメな気がする、、、）


スケジュール管理と解決能力判定のための問題かな。

  • 問4でひっかかって、問4と5ができない人はスケジュール管理に難あり
  • 問5を先にやって、問4ができなかった人は、スケジュール管理は良いけど、解決能力がもう少し
  • 問4を自信満々で間違えた人は、うっかり屋さん
  • 問4をダサいけど回答した人は、石橋を叩いて渡るタイプ（たまに叩き壊すかも）
  • 問4も含め全ての回答にセンスがある人は、、、一緒に仕事して！

といったところと言えそう。
何にしても、これで失格は厳しいテストだねぇ。
職場には失格者が相当いそう、、、。

問5

1,2,…,9の数をこの順序で、”+”、”-“、またはなにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 - 5 + 67 - 8 + 9 = 100となる。

問4に比べると簡単。
せっかく問2でマージする関数を作ったので、使ってみました。
EVAL禁止されたら、逆ポーランド記法で処理するかな。
あ、いや、+と-しかないから、頭から処理で良いか。

回答

OPTION EXPLICIT

DIM q[] = 50,2,1,9

MSGBOX("Q1For<#CR> " + Q1For(q))
MSGBOX("Q1While<#CR> " + Q1While(q))
MSGBOX("Q1Rec<#CR> " + Q1Rec(q))

DIM q2[] = "a","b","c","d","e"
MSGBOX("Q2<#CR> " + JOIN(Q2F(q, q2)))

PRINT "Q3<#CR>" + JOIN(Q3F(), "<#CR>")

MSGBOX("Q4<#CR> " + Q4F(q))

MSGBOX("Q5<#CR>" + JOIN(Q5F(), "<#CR>"))


// 配列は0始まりだとするよ！
// 数値検査はしないよ！
FUNCTION Q1For(q[])
	DIM i
	RESULT = 0
	FOR i = 0 TO LENGTH(q) - 1
		RESULT = RESULT + q[i]
	NEXT
FEND
FUNCTION Q1While(q[])
	DIM i = 0
	RESULT = 0
	WHILE i < LENGTH(q)
		RESULT = RESULT + q[i]
		i = i + 1
	WEND
FEND
FUNCTION Q1Rec(q[])
	IFB LENGTH(q) > 0 THEN
		// SLICEは不利だと思うけどより再帰らしいので
		RESULT = q[0] + Q1Rec(SLICE(q, 1))
	ELSE
		RESULT = 0
	ENDIF
FEND

FUNCTION Q2F(q1[], q2[])
	DIM m1 = LENGTH(q1), m2 = LENGTH(q2), i, m = m1
	RESULT = SAFEARRAY(0, m1 + m2 - 1)
	IF m > m2 THEN m = m2
	FOR i = 0 TO m - 1
		RESULT[i * 2] = q1[i]
		RESULT[i * 2 + 1] = q2[i]
	NEXT
	IF m1 > m2 THEN
		FOR i = m TO m1 - 1
			RESULT[m + i] = q1[i]
		NEXT
	ELSE
		FOR i = m TO m2 - 1
			RESULT[m + i] = q2[i]
		NEXT
	ENDIF
FEND

FUNCTION Q3F(n = 100)
	RESULT = SAFEARRAY(0, n - 1)
	DIM i, j, m1, m2, p1, p2
	FOR i = 0 TO n - 1
		IFB i > 1 THEN
			m2 = LENGTH(RESULT[i - 2])
			IFB m2 > 14 THEN
				m1 = LENGTH(RESULT[i - 1])
				RESULT[i] = ""
				WHILE m2 > 0 OR m1 > 0
					p2 = 14
					p1 = 14
					IF m2 < 14 THEN p2 = m2
					IF m1 < 14 THEN p1 = m1
					j = LENGTH(RESULT[i]) - 14
					IF j < 0 THEN j = 0
					RESULT[i] = (VAL(COPY(RESULT[i - 2], m2 - 13, p2), 0) + VAL(COPY(RESULT[i - 1], m1 - 13, p1), 0) + VAL(COPY(RESULT[i], 1, j), 0)) + COPY(RESULT[i], j + 1, 14)
					m2 = m2 - 14
					m1 = m1 - 14
				WEND
			ELSE
				RESULT[i] = RESULT[i - 2] + RESULT[i - 1]
			ENDIF
		ELSEIF i THEN
			RESULT[i] = 1
		ELSE
			RESULT[i] = 0
		ENDIF
	NEXT
FEND

// 15桁以内だとする
// 15桁超えるならQ3のようにその処理が必要なだけ
FUNCTION Q4F(q[])
	RESULT = VAL(JOIN(q, ""))
	DIM m = 1, l = LENGTH(q), i, j, b, n, c
	FOR i = 2 TO l
		m = m * i
	NEXT
	FOR i = 0 TO m - 1
		b = SPLIT(JOIN(q))
		FOR j = 0 TO l - 2
			n = i MOD (l - j)
			IFB n > 0 THEN
				c = b[n + j]
				b[n + j] = b[j]
				b[j] = c
			ENDIF
		NEXT
		b = VAL(JOIN(b, ""))
		IF RESULT < b THEN RESULT = b
	NEXT
FEND

FUNCTION Q5F()
	HASHTBL res

	DIM a[] = 1,2,3,4,5,6,7,8,9
	DIM b[7], c[] = "+","-",""
	DIM r, i, j, lb = LENGTH(b), lc = LENGTH(c)

	FOR i = 0 TO POWER(lc, lb) - 1
		FOR j = 0 TO lb - 1
			b[j] = c[i MOD lc]
			i = INT(i / lc)
		NEXT

		r = JOIN(Q2F(a, b), "")
		IF EVAL(r) = 100 THEN res[LENGTH(res)] = r
	NEXT

	RESULT = SAFEARRAY(0, LENGTH(res) - 1)
	FOR i = 0 TO LENGTH(res) - 1
		RESULT[i] = res[i, HASH_VAL]
	NEXT
FEND