A
мне нужно найти такой набор из a и b, чтобы World пришел из некоторого исходного состояния в некоторое конечное
Size: a a a
2021 January 17
A
при этом если просто сделать State World [a], то ветвлений слишком много
к
так, интересно
если a.b = 1 и b.a = 1, то возможны только комбинации a^n и b^n, все остальные сводятся в этим двум
если a.b = 1 и b.a = 1, то возможны только комбинации a^n и b^n, все остальные сводятся в этим двум
к
aaaaba
=
aaa(ab)a
=
aaaa
bababab
~
b(ab)(ab)(ab)
~
b
~
(ba)(ba)b(ab)
~
b
~
...
=
aaa(ab)a
=
aaaa
bababab
~
b(ab)(ab)(ab)
~
b
~
(ba)(ba)b(ab)
~
b
~
...
AP
Звучит как A* с эвристикой "a . b == b . a"
AP
А если будет "a . b . c == c . a"?
AP
Имхо, nub должна вызывающая сторона делать
A
ок, тогда еще более конкретно. Функция listActions :: World -> [World -> World]
A
но известно, что любые два действия коммутируют
AP
В BFS/DFS с отбрасыванием дублей путей как раз так и делают. Но никто не пишет DFS в инстансе монады
к
так, интересно
если a.b = 1 и b.a = 1, то возможны только комбинации a^n и b^n, все остальные сводятся в этим двум
если a.b = 1 и b.a = 1, то возможны только комбинации a^n и b^n, все остальные сводятся в этим двум
а, черт, нет, ошибся, нет правила что ab=1=ba
AP
но известно, что любые два действия коммутируют
Они все identity? Или их всего два? :)
к
ну тогда каждая комбинация это пара из двух чисел, где
type Action = (Int, Int)
runAction (n, m) = iter n a . iter m a
iter :: Int -> (a -> a) -> (a -> a)
type Action = (Int, Int)
runAction (n, m) = iter n a . iter m a
iter :: Int -> (a -> a) -> (a -> a)
A
они все не identity
к
значит нужно просто перебирать два числа, n и m
A
Гм. Ну World это некоторая структура с разными полями, а каждое из экшнов это "взять что-то из одних полей и положить в другие"
A
причем "взять" и "положить" это сложение и вычитание
A
допустим a w = w{field1=field1 w + 1}, а b w = w{field2=field2 w + 1}
A
они не идентити, но они коммутируют
к
без всякого стейта,
f result x = head do
n <- [0..]
m <- [0..n]
let guess = iter n a . iter m a $ x
guard $ guess == result
pure guess
iter 0 f = id
iter n f = f . iter (dec n) f
f result x = head do
n <- [0..]
m <- [0..n]
let guess = iter n a . iter m a $ x
guard $ guess == result
pure guess
iter 0 f = id
iter n f = f . iter (dec n) f