MojoでProject Euler 84

https://projecteuler.net/problem=84

ちゃんと計算しようとすると大変です。カードをシャッフルして上から取って一番下に入れるというのが難しいです。シャッフルしてからでも状態の数が10240あります。シャッフルしてから収束させて、すべてのシャッフルに対して行うというのは無理です。
しかし、単に100万回をランダムに進めるだけで答えが出ます。

import sys
import random


#################### List ####################

fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]:
    var a = List[T](capacity=N)
    for n in range(N):
        a.append(init)
    return a

trait Printable(CollectionElement, Stringable):
    pass

fn print_list[T: Printable](a: List[T]):
    if a.size > 0:
        var s = "[" + str(a[0])
        for i in range(1, a.size):
            s += ", " + str(a[i])
        s += "]"
        print(s)
    else:
        print("[]")

fn copy_list[T: CollectionElement](a: List[T]) -> List[T]:
    return sublist(a, 0, len(a))

fn sublist[T: CollectionElement](a: List[T], first: Int, last: Int) -> List[T]:
    var b = List[T]()
    for i in range(first, last):
        b.append(a[i])
    return b


#################### process ####################

var squares = List[StringLiteral](
                "GO", "A1", "CC1", "A2", "T1", "R1", "B1", "CH1", "B2", "B3",
                "JAIL", "C1", "U1", "C2", "C3", "R2", "D1", "CC2", "D2", "D3",
                "FP", "E1", "CH2", "E2", "E3", "R3", "F1", "F2", "U2", "F3",
                "G2J", "G1", "G2", "CC3", "G3", "R4", "CH3", "H1", "T2", "H2")
var CC_cards = List[StringLiteral]("GO", "JAIL")
var CH_cards = List[StringLiteral]("GO", "JAIL", "C1", "E3", "H2",
                                        "R1", "R", "R", "U", "BACK")
var dic = Dict[StringLiteral, Int]()

fn find_next(j: Int, sq: StringLiteral) -> Int:
    if sq == "R":
        if j == 8:
            return 15
        elif j == 22:
            return 25
        else:
            return 5
    else:
        if j == 22:
            return 28
        else:
            return 12

fn step_simply(state: Int, N: Int) -> Int:
    var pos = state >> 8
    for _ in range(3):
        var dice1 = int(random.random_si64(1, N))
        var dice2 = int(random.random_si64(1, N))
        if dice1 != dice2:
            pos = (pos + dice1 + dice2) % 40
            return pos
    else:
        return 10   # JAIL

fn step(state: Int, N: Int) -> Int:
    var pos = state >> 8
    var cci = state & 15
    var chi = (state >> 4) & 15
    var new_pos = step_simply(state, N)
    var square = squares[new_pos]
    if square == "G2J":
        new_pos = 10
        return cci | (chi << 4) | (new_pos << 8)
    elif "CC" in squares[new_pos]:
        if cci < 2:
            new_pos = dic.get(CC_cards[cci], -1)
        return (cci+1) | (chi << 4) | (new_pos << 8)
    elif "CH" in square:
        if chi < 6:
            new_pos = dic.get(CH_cards[chi], -1)
        elif square == "R":
            new_pos = find_next(new_pos, "R")
        elif square == "U":
            new_pos = find_next(new_pos, "U")
        elif square == "BACK":
            new_pos = (new_pos - 3) % 40
        return cci | ((chi + 1) << 4) | (new_pos << 8)
    else:
        return cci | (chi << 4) | (new_pos << 8)

@value
struct Item(Comparable):
    var s: Float64
    var i: Int
    
    fn __lt__(self, other: Item) -> Bool:
        return self.s < other.s
    
    fn __le__(self, other: Item) -> Bool:
        return self.s <= other.s
    
    fn __gt__(self, other: Item) -> Bool:
        return self.s > other.s
    
    fn __ge__(self, other: Item) -> Bool:
        return self.s >= other.s
    
    fn __eq__(self, other: Item) -> Bool:
        return self.s == other.s
    
    fn __ne__(self, other: Item) -> Bool:
        return self.s != other.s

fn f(N: Int) -> String:
    for i in range(len(squares)):
        dic[squares[i]] = i
    random.seed(2)
    var L = 10**6
    var counter = initialize_list(40, 0)
    var state = 0
    for _ in range(L):
        state = step(state, N)
        var pos = state >> 8
        counter[pos] += 1
    var v = List[Item]()
    for i in range(40):
        v.append(Item(counter[i], i))
    sort(v)
    var n1 = v[39].i
    var n2 = v[38].i
    var n3 = v[37].i
    return (String(n1//10) + String(n1%10) +
            String(n2//10) + String(n2%10) +
            String(n3//10) + String(n3%10))

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))