From: David Kerkeslager Date: Tue, 6 Jul 2010 04:56:42 +0000 (-0400) Subject: Adding in my random stuff. X-Git-Url: https://code.kerkeslager.com/?p=sandbox;a=commitdiff_plain;h=e68c1a3165d9cc2bf8ee17dbe849b610bd4fcad3 Adding in my random stuff. --- e68c1a3165d9cc2bf8ee17dbe849b610bd4fcad3 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..6f3ae28 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +*.out +*.pyc diff --git a/cycles.c b/cycles.c new file mode 100644 index 0000000..10f03e4 --- /dev/null +++ b/cycles.c @@ -0,0 +1,124 @@ +#include +#include +#include + +typedef struct List List; + +struct List { List* next; }; + +List* generateCycle() +{ + srand(time(NULL)); + + // It may be necessary to tinker with this value to keep rand() within + // reasonable bounds. + const int modifier = 16; + int a = rand() >> modifier,b = rand() >> modifier; + + // a must be less than or equal to b + if(a > b) + { + int t = a; + a = b; + b = t; + } + + List* cycle; + List* current = malloc(sizeof(List)); + + List* r = current; + + for(int i = 0; i < b; i++) + { + current->next = malloc(sizeof(List)); + current = current->next; + + if(i == a) cycle = current; + } + + current->next = cycle; + + return r; +} + +// TODO Implement a function that frees the cycled list. + +size_t tortoiseAndHare(List* list) +{ + size_t count = 0; + + List* tortoise = list; + List* hare = list; + + while(1) + { + count++; + + hare = hare->next; + if(hare == NULL) return 0; + else if(tortoise == hare) return count; + + hare = hare->next; + if(hare == NULL) return 0; + else if(tortoise == hare) return count; + + tortoise = tortoise->next; + } +} + +size_t teleportingTurtle(List* list) +{ + size_t count = 0; + + List* turtle = list; + List* rabbit = list; + int patience = 1; + + while(1) + { + for(int i = 0; i < patience; i++) + { + count++; + + rabbit = rabbit->next; + if(rabbit == NULL) return 0; + else if(turtle == rabbit) return count; + + rabbit = rabbit->next; + if(rabbit == NULL) return 0; + else if(turtle == rabbit) return count; + + turtle = turtle->next; + } + + patience = patience << 1; + turtle = rabbit; // TELEPORT! + } +} + +// TODO Instead of counting steps, take the time. +// TODO Research how to detect where the cycle starts (and if it is useful). + +int main() +{ + int limit = 256; + size_t th, thtotal = 0, tt, tttotal = 0; + + for(int i = 0; i < limit; i++) + { + printf("Generating racetrack.\n"); + List* cycle = generateCycle(); + + printf("Racing tortoise vs. hare.\n"); + th = tortoiseAndHare(cycle); + + printf("Racing teleporting turtle vs. rabbit.\n"); + tt = teleportingTurtle(cycle); + + thtotal += th; + tttotal += tt; + } + + printf("Tortoise and hare: %i\n",thtotal / limit); + printf("Teleporting turtle: %i\n",tttotal / limit); +} diff --git a/license.txt b/license.txt new file mode 100644 index 0000000..bd1512c --- /dev/null +++ b/license.txt @@ -0,0 +1,18 @@ +Copyright (c) 2010 David Kerkeslager + +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. diff --git a/memoization.py b/memoization.py new file mode 100644 index 0000000..b864148 --- /dev/null +++ b/memoization.py @@ -0,0 +1,51 @@ +class Memoize(object): + """ + Implements memoziation. Use as a decorator to cache the results of a + function. The function must have the following properties: + * No side effects. + * Referentially transparent. + * No keyword arguments. + + While the following are not required for proper behavior, memoization is + unlikely to produce a significant performance gain and may indeed produce + a performance loss unless the function has the following properties: + * Performance slower than a hash lookup on the arguments. + * The function is called many times with the same arguments. + These properties occur most often when a function has deep and/or wide + recursion. + + For more information see the following links: + * http://en.wikipedia.org/wiki/Memoization + * http://en.wikipedia.org/wiki/Referential_transparency_(computer_science) + """ + def __init__(self,f): + self.f = f + self.memo = {} + + def __call__(self,*args): + if args in self.memo: + return self.memo[args] + + result = self.f(*args) + self.memo[args] = result + return result + +class KWMemoize(object): + """ + This is equivalent to Memoize except that it allows keyword arguments. + However, there is a small performance cost for this so one should use + Memoize for functions that do not take keyword arguments. + """ + def __init__(self,f): + self.f = f + self.memo = {} + + def __call__(self,*args,**kwargs): + kws = tuple(kwargs.items()) + + if (args,kws) in self.memo: + return self.memo[(args,kws)] + + result = self.f(*args,**kwargs) + self.memo[(args,kws)] = result + return result diff --git a/project-euler/14.py b/project-euler/14.py new file mode 100644 index 0000000..75f3baf --- /dev/null +++ b/project-euler/14.py @@ -0,0 +1,52 @@ +"""This code is the result of my attempt to solve Project Euler problem 14. It +takes a positive integer from the command line and finds the positive integer +less than the given integer which starts the longest hailstone sequence. For +more information on hailstone sequences, see +http://en.wikipedia.org/wiki/Collatz_conjecture . + +While solving this problem I came across a novel usage of a few different +advanced Python features for a very generalizeable and reusable way to implement +memoization. For more information on memoization, see +http://en.wikipedia.org/wiki/Memoization .""" + +class Memoize: + def __init__(self,function): + self.function = function + self.memo = {} + + def __call__(self,*arguments): + if arguments in self.memo: + return self.memo[arguments] + + result = self.function(*arguments) + self.memo[arguments] = result + return result + +@Memoize +def hailstone(start): + if start == 1: + return 1 + + if start % 2 == 0: + return hailstone(start / 2) + 1 + + return hailstone(start * 3 + 1) + 1 + +if __name__ == '__main__': + import sys + + # Needed in order to calculate the hailstone number of large numbers. + sys.setrecursionlimit(1000000) + + limit = int(sys.argv[1]) + max = 1 + max_start = 1 + + for i in xrange(1,limit): + chain = hailstone(i) + + if chain > max: + max = chain + max_start = i + + print max_start diff --git a/project-euler/20.clj b/project-euler/20.clj new file mode 100644 index 0000000..5501ee5 --- /dev/null +++ b/project-euler/20.clj @@ -0,0 +1,12 @@ +(defn factorial [n] + (if (= n 1) + 1 + (* n (factorial (- n 1))))) + +(defn sum-digits [radix n] + (if (= n 0) + 0 + (+ (rem n radix) (sum-digits radix (quot n radix))))) + + +(println (sum-digits 10 (factorial 100))) diff --git a/project-euler/21.clj b/project-euler/21.clj new file mode 100644 index 0000000..aa337b8 --- /dev/null +++ b/project-euler/21.clj @@ -0,0 +1,16 @@ +(defn factors [n] + (filter #(zero? (mod n %)) + (take (- n 1) (iterate inc 1)))) + +(defn d [n] + (reduce + (factors n))) + +(defn amicable? [a b] + (and + (= a (d b)) + (= (d a) b))) + +(defn list-length [a] + (if (= (first a) nil) + 0 + (+ 1 (list-length (rest a))))) diff --git a/readme.txt b/readme.txt new file mode 100644 index 0000000..ff95800 --- /dev/null +++ b/readme.txt @@ -0,0 +1,21 @@ +This repository contains whatever code and writings I want to make publicly +available. As the name suggests, this is mostly my research into various +programming languages or code paradigms. Probably if it were production-quality +code, I would release it as its own project, so the fact that it is here means +that it needs serious work before it can be used for anything. Really, I mean +it. Don't use this code unless you've checked and fixed it thoroughly. + +Code is licensed under the MIT license (included in the file "license.txt") +unless otherwise licensed. Other (non-code) content is licensed under the +Creative Commons Attribution 3.0 United States License (explanation can be found +at http://creativecommons.org/licenses/by/3.0/us/, and the full license can be +found at http://creativecommons.org/licenses/by/3.0/us/legalcode ) unless +otherwise licensed. + +Code and text are best viewed in a monospace font with line width set to 80 +characters and with tab stops set to 4 spaces. + +I hope you find these materials useful and educational. + +Regards, +David Kerkeslager