Skip to content

Instantly share code, notes, and snippets.

@rmoehn
Last active August 29, 2015 14:15
Show Gist options
  • Save rmoehn/2bf119af3e55664d42c7 to your computer and use it in GitHub Desktop.
Save rmoehn/2bf119af3e55664d42c7 to your computer and use it in GitHub Desktop.
Most likely chain of rooms a cleaning robot has visited given initial and final state
(ns user)
;;; See http://sparetimeteaching.dk/note_collections/2015%20Winter.pdf, A Functional Fever Fantasy
(def trans-probs {:living-room
{:living-room 0
:office 0.3
:kitchen 0.5
:desk 0
:bedroom 0.2}
:office
{:living-room 0.23
:office 0
:kitchen 0.662
:desk 0.1
:bedroom 0.008}
:kitchen
{:living-room 1/3
:office 1/3
:kitchen 0
:desk 0
:bedroom 1/3}
:desk
{:living-room 0
:office 1
:kitchen 0
:desk 0
:bedroom 0}
:bedroom
{:living-room 0.3
:office 0.6
:kitchen 0.1
:desk 0
:bedroom 0}})
(defn as-p [trans-probs]
(fn [event _ given]
(get-in trans-probs [given event])))
(defn foldn [e f n]
(if (zero? n)
e
(recur (f e) f (dec n))))
(defn max-prob-chain [trans-probs init-state fin-state in-betw-cnt]
(let [p (as-p trans-probs)
possible-states (keys trans-probs)]
((foldn (fn [next-state] [(p next-state :| init-state) []])
(fn [ml-states-before]
(fn [next-state]
(apply (partial max-key first)
(map (fn [s]
(let [[prob ml-states] (ml-states-before s)]
[(* (p next-state :| s) prob)
(conj ml-states s)]))
possible-states))))
in-betw-cnt)
fin-state)))
(second (max-prob-chain trans-probs :living-room :office 6))
;=> [:office :kitchen :bedroom :office :kitchen :bedroom]
;;; The MIT License (MIT)
;;;
;;; Copyright (c) 2015 Richard Möhn
;;;
;;; Permission is hereby granted, free of charge, to any person obtaining a copy
;;; of this software and associated documentation files (the "Software"), to deal
;;; in the Software without restriction, including without limitation the rights
;;; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
;;; copies of the Software, and to permit persons to whom the Software is
;;; furnished to do so, subject to the following conditions:
;;;
;;; The above copyright notice and this permission notice shall be included in
;;; all copies or substantial portions of the Software.
;;;
;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
;;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
;;; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
;;; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
;;; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
;;; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
;;; THE SOFTWARE.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment