Generate a random, nested map

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
1
down vote

favorite












To answer a question on Stack Overflow, I needed to generate a large, nested map that I could postwalk over to do some testing.



After a couple stabs, this is what I came up with. It works by taking a "template map", iterating over it, and randomly changing one of the children of the template via recursion.



While it works, and I'm fairly happy with it, I'd like any advice on how it could be improved. I'm mostly concerned about how prone gen-tree is to Stack Overflows, which necessitated the creation of gen-giant-tree to "brute-force" the problem and find the best of the results. Any advice here especially would be appreciated.



Example usage:



(gen-giant-tree 1000 0.1 :a 1, :b 2, :c 3, :d 4, :e 5, :f 6)

:a 1,
 :b 2,
 :c 3,
 :d :a :a 1,
 :b 2,
 :c 3,
 :d :a :a :a 1, :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a 1,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a :a 1,
 :b 2,
 :c 3,
 :d :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :e 5,
 :f 6,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :d 4,
 :e :a 1,
 :b 2,
 :c 3,
 :d :a :a 1, :b 2, :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :f 6,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :f 6,
 :e 5,
 :f 6


The code:



(ns fast-tree-transform.test-data)

(defn random-percent?
 "Returns true percent% of the time."
 [percent]
 (<= (rand) percent))

(defn gen-tree
 "Generates a deeply nested tree by branching from a child of the template chance-of-branch% of the time.
 Very prone to StackOverflows since there is no limitor."
 [chance-of-branch template-map]
 (into 
 (map (fn [[k :as pair]] (if (random-percent? chance-of-branch)
 [k (gen-tree chance-of-branch template-map)]
 pair))
 template-map)))

(defn gen-giant-tree
 "Tries to generate tries number of trees. Throws out any tries that result in a StackOverflow, then returns the 
 result with the longest length when stringified."
 [tries chance-of-branch template-map]
 (->> (repeatedly tries #(try
 (gen-tree chance-of-branch template-map)

 (catch StackOverflowError e
 nil)))
 (filter identity)
 (sort #(compare (count (str %)) (count (str %2))))
 (last)))



clojure




share|improve this question



















  • It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function.
    – Carcigenicate
    Apr 17 at 15:00
















up vote
1
down vote

favorite












To answer a question on Stack Overflow, I needed to generate a large, nested map that I could postwalk over to do some testing.



After a couple stabs, this is what I came up with. It works by taking a "template map", iterating over it, and randomly changing one of the children of the template via recursion.



While it works, and I'm fairly happy with it, I'd like any advice on how it could be improved. I'm mostly concerned about how prone gen-tree is to Stack Overflows, which necessitated the creation of gen-giant-tree to "brute-force" the problem and find the best of the results. Any advice here especially would be appreciated.



Example usage:



(gen-giant-tree 1000 0.1 :a 1, :b 2, :c 3, :d 4, :e 5, :f 6)

:a 1,
 :b 2,
 :c 3,
 :d :a :a 1,
 :b 2,
 :c 3,
 :d :a :a :a 1, :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a 1,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a :a 1,
 :b 2,
 :c 3,
 :d :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :e 5,
 :f 6,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :d 4,
 :e :a 1,
 :b 2,
 :c 3,
 :d :a :a 1, :b 2, :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :f 6,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :f 6,
 :e 5,
 :f 6


The code:



(ns fast-tree-transform.test-data)

(defn random-percent?
 "Returns true percent% of the time."
 [percent]
 (<= (rand) percent))

(defn gen-tree
 "Generates a deeply nested tree by branching from a child of the template chance-of-branch% of the time.
 Very prone to StackOverflows since there is no limitor."
 [chance-of-branch template-map]
 (into 
 (map (fn [[k :as pair]] (if (random-percent? chance-of-branch)
 [k (gen-tree chance-of-branch template-map)]
 pair))
 template-map)))

(defn gen-giant-tree
 "Tries to generate tries number of trees. Throws out any tries that result in a StackOverflow, then returns the 
 result with the longest length when stringified."
 [tries chance-of-branch template-map]
 (->> (repeatedly tries #(try
 (gen-tree chance-of-branch template-map)

 (catch StackOverflowError e
 nil)))
 (filter identity)
 (sort #(compare (count (str %)) (count (str %2))))
 (last)))



clojure




share|improve this question



















  • It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function.
    – Carcigenicate
    Apr 17 at 15:00












up vote
1
down vote

favorite









up vote
1
down vote

favorite











To answer a question on Stack Overflow, I needed to generate a large, nested map that I could postwalk over to do some testing.



After a couple stabs, this is what I came up with. It works by taking a "template map", iterating over it, and randomly changing one of the children of the template via recursion.



While it works, and I'm fairly happy with it, I'd like any advice on how it could be improved. I'm mostly concerned about how prone gen-tree is to Stack Overflows, which necessitated the creation of gen-giant-tree to "brute-force" the problem and find the best of the results. Any advice here especially would be appreciated.



Example usage:



(gen-giant-tree 1000 0.1 :a 1, :b 2, :c 3, :d 4, :e 5, :f 6)

:a 1,
 :b 2,
 :c 3,
 :d :a :a 1,
 :b 2,
 :c 3,
 :d :a :a :a 1, :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a 1,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a :a 1,
 :b 2,
 :c 3,
 :d :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :e 5,
 :f 6,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :d 4,
 :e :a 1,
 :b 2,
 :c 3,
 :d :a :a 1, :b 2, :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :f 6,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :f 6,
 :e 5,
 :f 6


The code:



(ns fast-tree-transform.test-data)

(defn random-percent?
 "Returns true percent% of the time."
 [percent]
 (<= (rand) percent))

(defn gen-tree
 "Generates a deeply nested tree by branching from a child of the template chance-of-branch% of the time.
 Very prone to StackOverflows since there is no limitor."
 [chance-of-branch template-map]
 (into 
 (map (fn [[k :as pair]] (if (random-percent? chance-of-branch)
 [k (gen-tree chance-of-branch template-map)]
 pair))
 template-map)))

(defn gen-giant-tree
 "Tries to generate tries number of trees. Throws out any tries that result in a StackOverflow, then returns the 
 result with the longest length when stringified."
 [tries chance-of-branch template-map]
 (->> (repeatedly tries #(try
 (gen-tree chance-of-branch template-map)

 (catch StackOverflowError e
 nil)))
 (filter identity)
 (sort #(compare (count (str %)) (count (str %2))))
 (last)))



clojure




share|improve this question











To answer a question on Stack Overflow, I needed to generate a large, nested map that I could postwalk over to do some testing.



After a couple stabs, this is what I came up with. It works by taking a "template map", iterating over it, and randomly changing one of the children of the template via recursion.



While it works, and I'm fairly happy with it, I'd like any advice on how it could be improved. I'm mostly concerned about how prone gen-tree is to Stack Overflows, which necessitated the creation of gen-giant-tree to "brute-force" the problem and find the best of the results. Any advice here especially would be appreciated.



Example usage:



(gen-giant-tree 1000 0.1 :a 1, :b 2, :c 3, :d 4, :e 5, :f 6)

:a 1,
 :b 2,
 :c 3,
 :d :a :a 1,
 :b 2,
 :c 3,
 :d :a :a :a 1, :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a 1,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a :a :a 1,
 :b 2,
 :c 3,
 :d :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :e 5,
 :f 6,
 :b :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a 1,
 :b 2,
 :c :a :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :d 4,
 :e 5,
 :f 6,
 :d 4,
 :e :a 1,
 :b 2,
 :c 3,
 :d :a :a 1, :b 2, :c :a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :f 6,
 :d 4,
 :e 5,
 :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e 5,
 :f 6,
 :e 5,
 :f 6,
 :b 2,
 :c 3,
 :d 4,
 :e :a 1, :b 2, :c 3, :d 4, :e 5, :f :a 1, :b 2, :c 3, :d 4, :e 5, :f 6,
 :f 6,
 :e 5,
 :f 6


The code:



(ns fast-tree-transform.test-data)

(defn random-percent?
 "Returns true percent% of the time."
 [percent]
 (<= (rand) percent))

(defn gen-tree
 "Generates a deeply nested tree by branching from a child of the template chance-of-branch% of the time.
 Very prone to StackOverflows since there is no limitor."
 [chance-of-branch template-map]
 (into 
 (map (fn [[k :as pair]] (if (random-percent? chance-of-branch)
 [k (gen-tree chance-of-branch template-map)]
 pair))
 template-map)))

(defn gen-giant-tree
 "Tries to generate tries number of trees. Throws out any tries that result in a StackOverflow, then returns the 
 result with the longest length when stringified."
 [tries chance-of-branch template-map]
 (->> (repeatedly tries #(try
 (gen-tree chance-of-branch template-map)

 (catch StackOverflowError e
 nil)))
 (filter identity)
 (sort #(compare (count (str %)) (count (str %2))))
 (last)))




clojure





share|improve this question










share|improve this question




share|improve this question









asked Apr 16 at 21:53









Carcigenicate

2,31911128




2,31911128











  • It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function.
    – Carcigenicate
    Apr 17 at 15:00
















  • It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function.
    – Carcigenicate
    Apr 17 at 15:00















It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function.
– Carcigenicate
Apr 17 at 15:00




It makes sense in retrospect, but I found, through fairly rigorous testing, that the optimal chance-of-branch is (/ 1 (count template-map)). I'm guessing this is because any more than this causes a StackOverflow since there will on average be more than 1 branch per branch, which will explode. Any less than that would lower the branches/branch beyond what is necessary to avoid SOs. I created a optimal-branch-chance function, and allowed chance-of-branch to default to a call to that function.
– Carcigenicate
Apr 17 at 15:00















active

oldest

votes











Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);








 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f192244%2fgenerate-a-random-nested-map%23new-answer', 'question_page');

);

Post as a guest






















active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes










 

draft saved


draft discarded


























 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f192244%2fgenerate-a-random-nested-map%23new-answer', 'question_page');

);

Post as a guest
































































-

Popular posts from this blog

Chat program with C++ and SFML

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 2 down vote favorite This is my client code: (My server is very similar at the moment but I will upload it below this one just in case somebody wants to run it) #include <SFML/Graphics.hpp> #include <SFML/Network.hpp> #include <thread> int main() sf::RenderWindow main_win(sf::VideoMode(800, 800), "Chatcy!"); main_win.setPosition(sf::Vector2i(sf::VideoMode::getDesktopMode().width/2 -400, sf::VideoMode::getDesktopMode().height/2 -400)); main_win.setVerticalSyncEnabled(true); //chatcy logo sf::Texture chatcy; chatcy.loadFromFile("image_chatcy.png"); sf::Sprite logo; logo.setTexture(chatcy); //200x800 //font sf::Font font; font.loadFromFile("FreeSerif.ttf"); //name sf::String name("Client"); name += ": "; //text input area and background sf::RectangleShape in_backg
Read more

Function to Return a JSON Like Objects Using VBA Collections and Arrays

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 1 down vote favorite My goal is to create a compact function that can create a JSON Like object from JSON string. I want a function with a small footprint that I or anyone who wants to use it, can simply paste into a module and use. At 61 lines of code, I am happy with its size and portability. Here is an image of JSON Object created from string data using a ScriptControl . Although the Locals Window displays the properties and values correctly, the object itself is extremely difficult to work with. This image shows an object created using getJSONCollection . Because it is made of VBA Collections and Arrays, it is very easy to work with. Option Explicit Private Function getJSONCollection(ByVal Value As Variant, Optional ScriptEngine As Object) As Variant Const DELIMITER As String = "||" Dim col As Collection, JSON As Object, KeyNam
Read more

Will my employers contract hold up in court?

Image
Clash Royale CLAN TAG #URR8PPP up vote 8 down vote favorite 2 When I started a new job back in July of 2017, I signed a contract that had the following bindings or restrictions if I was ever to leave the company: Cannot work for a competitor within 25 miles of current companies location for the next two years Cannot offer my services to any organization within 25 miles of current companies location for the next two years Now, when mentioned “my services” this can be related to my profession of website design. This contract seems incredibly binding, 2 years in length, and I’m looking to see if it would actually hold up in an Arizona court. contract employment non-compete arizona share | improve this question edited Aug 7 at 15:35 feetwet ♦ 13.8k 9 37 85 asked Aug 6 at 19:05 Alex S. 46 2 What does your company do and what services do they provide? What is your role (i.e. internal work or work for customers).
Read more