トイレ問題 未知の言語をPythonに翻訳（辞書と三項演算子）

トイレの問題の話

The Optimal Urinal Problem

 

赤はまた辞書について調べそうなので覚書

#dict = {'key1': 1, 'key2': 2, 'key3': 3} #辞書定義
#print(dict) #辞書表示
#dict['key4'] = 4 #辞書追加
#print('key1' in dict) #辞書キーの存在チェック

 

 

トイレ（小）が並んでいると普通男性は最大限離れて立つ。これは世界共通かもしれない。

この問題は隣には絶対に立たないという条件で基本最大限離れて立つとする。

あなたがトイレの最初の支配者だとして、左から何番目に立てばそのトイレ（小）を最大限立たせることができるかという問題。

 

テストケースにはToilet Universeというのがあり、トイレ（小）が1400000　並んでいるものもある。

ユニークな問題なので是非解きたいのだけれどシミュレーションだけではTimeout間違いなしの問題。

何か手がかりがネットのどこかにないかと調べると...プログラムがまんま置いてある。

 

そのままは…ということでPythonに移植。

Javaだろうとコピーしてそのまま移植しようしますが、こ、これはJavaではない別の何かだ！

あえて謎の言語のまま、内容を想像して移植していきました。

 

ハマった箇所

const memo = [];

const findTotal = (first, last) => {
    const dist = last-first;
    if (dist <= 3 ) return 0;
    const mid = Math.floor((first+last)/2);
    memo[dist] =
        memo[dist] ?
            memo[dist] : findTotal(first, mid) + findTotal(mid, last) + 1;
    return memo[dist];
};

const answer = n === 4 || n === 3 ? {max: 2, index: 1}: {max: 1, index: 1};
let i = 0;

 

[]といえば普通配列なんだけどただの配列ではなさげ

answerにいたってはクラスのよう。これでanswer.maxなんてクラスのような使いかもできる。（今見ると辞書でmaxがキー)

 

 

import math

n = int(input())

memo={}

def findTotal(first, last):
    dist = last-first
    if dist <= 3:
        return 0
    mid = math.floor( (first+last)/2 )
    if not(dist in memo):
        memo[dist] = findTotal(first, mid) + findTotal(mid, last) + 1
    return memo[dist]

aMax=2
aIndex=1

if 3>n:
    aMax=1
    aIndex=1

i = 0

while (n > 4 and math.floor(n/2) >= i):
    
    if not(i in memo):
        memo[i] = findTotal(0, i)
    if not((n-1-i) in memo):
        memo[n-1-i] = findTotal(i, n-1)
    c= 3 if i > 1 else 2
    
    total = memo[i] + memo[n-1-i] + c
    if total > aMax:
        aMax = total
        aIndex = i+1
    i+=1

print(aMax, aIndex)

 

新しい言語なのかなと期待して、調べてみるとJavaScriptでした。