Simplest lexer for c in go I started learning compilers development and as pet project decided to implement c compiler.
The first step is implementing simplest lexer.
Also, I decided to try new programming language and chose go. This is my first go program and I will be grateful for any advice. Thanks.

package lexer

import (
    "errors"
    "fmt"
    "unicode"
)

type tokenType int

const (
    EOF tokenType = iota

    Identifier
    NumericConstant

    IntType

    ReturnKeyword

    OpenRoundBracket
    CloseRoundBracket
    OpenCurlyBracket
    CloseCurlyBracket
    Semicolon
)

type token struct {
    tokenType tokenType
    value string
}

type parser struct {
    code []rune
    currentIndex int
}

func (p *parser) nextToken() token {
    p.skipSpaces()

    if p.isEOF() {
        return token{tokenType: EOF}
    }

    var newToken token

    r := p.currentRune()
    if unicode.IsLetter(r) {
        newToken = p.parseLetterStartToken()
    } else if unicode.IsNumber(r) {
        newToken = p.parseNumberStartToken()
    } else if r == '(' {
        newToken = token{tokenType: OpenRoundBracket, value:string(r)}
    } else if r == ')' {
        newToken = token{tokenType: CloseRoundBracket, value:string(r)}
    } else if r == '{' {
        newToken = token{tokenType: OpenCurlyBracket, value:string(r)}
    } else if r == '}' {
        newToken = token{tokenType: CloseCurlyBracket, value:string(r)}
    } else if r == ';' {
        newToken = token{tokenType: Semicolon, value:string(r)}
    } else {
        errorText := fmt.Sprintf("Unexpected character: %c", r)
        panic(errors.New(errorText))
    }

    p.currentIndex += 1
    return newToken
}

func (p *parser) skipSpaces() {
    if p.isEOF() {
        return
    }

    for unicode.IsSpace(p.currentRune()) {
        p.currentIndex += 1

        if p.isEOF() {
            return
        }
    }
}

func (p *parser) parseLetterStartToken() token {
    startIndex := p.currentIndex

    for unicode.IsLetter(p.currentRune()) || unicode.IsNumber(p.currentRune()) {
        p.nextRune()
    }

    endIndex := p.currentIndex

    tokenValue := string(p.code[startIndex: endIndex])
    p.currentIndex -= 1

    return letterStartToken(tokenValue)
}

func letterStartToken(tokenValue string) token {
    var tokenType tokenType

    switch tokenValue {
    case "int":
        tokenType = IntType
    case "return":
        tokenType = ReturnKeyword
    default:
        tokenType = Identifier
    }

    return token{tokenType:tokenType, value:tokenValue}
}

func (p *parser) parseNumberStartToken() token {
    startIndex := p.currentIndex

    for unicode.IsNumber(p.currentRune()) {
        p.nextRune()
    }

    endIndex := p.currentIndex

    tokenValue := string(p.code[startIndex: endIndex])
    p.currentIndex -= 1

    return token{tokenType: NumericConstant, value:tokenValue}
}

func (p parser) isEOF() bool {
    return p.currentIndex >= len(p.code)
}

func (p parser) currentRune() rune {
    return p.code[p.currentIndex]
}

func (p *parser) nextRune() rune {
    p.currentIndex += 1
    return p.currentRune()
}

func Tokenize(code []rune) []token {
    parser := parser{code:code, currentIndex:0}
    tokens := []token{}

    for newToken := parser.nextToken(); newToken.tokenType != EOF; {
        tokens = append(tokens, newToken)
        newToken = parser.nextToken()
    }

    return tokens
}

Your code is a good start, but it is not finished yet. You still need to do:

character literals
string literals
floating-point literals
hexadecimal int literals
int literals containing underscores

I suggest you pick a copy of the current C standard and read through chapter 6, which contains the definitions for all these lexemes. Along with the reading, start to write unit tests for each of the lexeme rules, especially the edge cases.

Your current code is well-structured, and you will be able to write the full lexer keeping the structure the same. I've written a very similar lexer in my pkglint project, and the corresponding unit tests in lexer_test.go in the same directory. Reading this code will bring you up to speed with your own lexer. To see how I use the lexer, look for NewLexer in the code.

One aspect where my lexer differs from yours is that my lexer only remembers the remaining input string, whereas your lexer remembers the complete input string plus the current index. I chose my data structure since it uses the least amount of memory possible. Taking a subslice is an efficient operation in Go, therefore I haven't been bitten my the extra memory access that l.rest = l.rest[1:] needs (it updates both the start and the length of l.rest. Your code is more efficient in that it only increments the index.


Find sequence by adding 5 or multiplying by 3 I wrote this little JavaScript function that starts with the number 1 and continually either adds 5 or multiplies by 3. This function tries to find a sequence of additions and multiplications that find that number.

Keep in mind, this function does not necessarily find the shortest sequence of operations.

I am looking for a review of my code and possible ways to make it more optimized. I'm also open to suggestions about how I can go about having this function find the shortest sequence of operations.

My code:

function findSequence(goal) {
  function find(start, history) {
    if (start == goal)
      return history;
    else if (start > goal)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

Test:

print(findSequence(178));

Output:

((((((((((((((1 + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) + 5) * 3) + 5) + 5)

This question is a bit related to a previous question. I will give you the same advice I did to the asker of the previous question.
Work from the other direction.
Currently, you're branching out starting from 1 trying to reach 178. Instead, start from 178 and try to reach 1. I'll show you how that will make the problem a lot easier.

We're at 178. Can we divide by 3? 178 mod 3 != 0 so no. Instead we reduce by 5.
178 - 5 == 173. Can we divide by 3? 173 mod 3 != 0 so no, we reduce by 5 instead.
173 - 5 == 168. Can we divide by 3? 168 mod 3 == 0 so yes, we can. Let's do that.
168 / 3 == 56. Wait a minute... this number ends with a 6... Interesting. (56 - 1) mod 5 equals zero, so from here we can just reduce by 5 until we've reached our target of 1.

Instead of branching out in an exponential manner, we've reduced the problem to a linear approach. Simply by flipping things backwards.
Let's say that we don't want to do the end loop of reducing by 5 just because we can (we want the shortest path, right?), then I see no other solution than to branch out recursively. When checking for the division by 3, a lot of branches are removed so it will be possible to find the shortest path by branching.
I'll leave the fun part of implementing this up to you :)
Some comments about your current code
(Which, given the comments above you should remove and completely re-write using the "backwards" approach)
In Java at least, it's recommended to add braces for each if. Also, as you're using return inside each if there's no need for else.
function findSequence(goal) {
  function find(start, history) {
    if (start == goal) {
      return history;
    }
    if (start > goal) {
      return null;
    }
    return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

I would also add a parameter to allow switching the start value, it will make it more flexible very easily.
I think it's good that you're hiding the find method inside the other function.


Adding column to table in a for loop I'm running the following code on quite large data frames. I've rewritten it for the iris dataset to make it reproducable.
I'm quite unexperienced with the apply functions and I find them a pain in the bum to apply them.

Is there any ways to drastically improve the performance of this process?

lmfit <- lm(iris$Petal.Width ~ iris$Sepal.Length + iris$Sepal.Width)
out_index <- 1
TableWithResiduals <- data.frame(matrix(ncol = ncol(iris) +1, nrow = nrow(iris)))
for (row in 1:length(resid(lmfit))){
  TableWithResiduals[out_index,] <- cbind(iris[row,],resid(lmfit)[row])
  out_index <- out_index +1
}
colnames(TableWithResiduals) <- colnames(iris)
colnames(TableWithResiduals)[length(TableWithResiduals)] <- "Residual_value"

If you look at the doc for cbind, which you already use, you will see that it can take whole matrices, data.frames, and vectors as inputs. This means you can just do:

TableWithResiduals <- cbind(iris, Residual_value = resid(lmfit))

You could also have done:

TableWithResiduals <- iris
TableWithResiduals$Residual_value <- resid(lmfit)

If it were not for these solutions, there are a few things that could be improved in your code. First, you could have used row directly instead of the out_index variable you created. Second, the last two lines of your code could have been merged into one: names(TableWithResiduals) <- c(names(iris), "Residual_value"). Also, if you look at the doc for lm, you could have saved yourself some typing by doing lm(Petal.Width ~ Sepal.Length + Sepal.Width, iris)


Conway's Game of Life in Scala To learn Scala, coming from Java and Python, I'm attempting to program an implementation of Conway's Game of Life.

I've implemented two different approaches so far, with the first being so bad I'm not even going to ask for review.

The second is a bit cleaner, and produces the correct output, but since I'm new to Scala, I want to know a more Scala-centric way to write things.

I'm also curious about feasibility for my third approach to this game, such as a bit-map approach to neighborhoods, and value caching.

What I want to know is:

Does my implementation fit well with the Scala way of writing code?
Can my code by reduced and made more concise than it already may or may not be?
Would representing all outcomes as a 9-bit map, then pre-caching all 512 possible outcomes have a positive or negative effect on performance?

The code in question is here, and also on Github.

package com.himself12794.main

import scala.collection.mutable.HashMap

object GameLife2 {

  def mappify(str: String, pad: Char = ' ') = {
    val its = new HashMap[(Int,Int), Boolean]
    var x,y = 0
    var items = str.stripMargin split("\n") toBuffer
    val m = items.reduceLeft((a,b) => a max b ).length
    if (items.length < 100) 0 to 100 - items.length foreach { _ => items append ""  }
    items = items map { _ padTo(100, pad) }
    items foreach { z => z foreach { c => its put((x,y),c == 'X'); x += 1}; y += 1; x = 0 }
    its
  }

}

class GameLife2(m: String, val living: Char = 'X', val dead: Char = ' ') {

  private var cells = GameLife2.mappify(m, dead)
  private val hw = cells.keySet reduceLeft { (a,b) => (a._1 max b._1, a._2 max b._2) }
  val height = hw._2 + 1
  val width = hw._1 + 1

  def getCount(x1: Int, y1: Int) = {
    var am = 0
    for {
      x <- x1 - 1 to x1 + 1
      y <- y1 - 1 to y1 + 1
    } {
      if (x > -1 && y > -1 && x < width && y < height && (x,y) != (x1,y1) && this(x,y)) am += 1
    }
    am
  }

  def apply(x: Int, y: Int) = {
    cells.get((x,y)).get
  }

  def doCycle = {
    val cp = cells.clone
    cells foreach {
      cell => {
        val coords = cell._1
        val c = cell._2
        val am = getCount(coords._1, coords._2)

        if (c && (am < 2 || am > 3)) cp.put(coords, false)
        else if (am == 3) cp.put(coords, true)

      }
    }; cells = cp
  }

  def clearConsole = print("\n" * 9)

  def getCells = cells
}

You are storing the board state as a HashMap[(Int,Int), Boolean].  Why not store it as a Set[(Int,Int)] instead, containing only the live cells?  Alternatively, if you want to list every cell, whether dead or alive, a two-dimensional array seems like it would be more appropriate and efficient.

You're using a mutable HashMap.  An immutable HashMap would be a more natural fit for the Game of Life, and would also promote good functional programming practices.  You're already calling val cp = cells.clone followed by cells = cp in doCycle, which indicates that each generation involves building a new board state.

For comparison, I have written an implementation that uses immutable structures and functional programming.


Unit Test BST in Java I have written BST in Java for practice. How can I write better unit test cases. I am sure the way I have written them is not proper.

Code for BST

package com.r.basics.tree;
import org.junit.Before;
import org.junit.Test;

public class BinarySearchTreeTest{
private BinarySearchTree<Integer> binarySearchTreeSUT;

    @Before
    public void setUp() {
        binarySearchTreeSUT =  new BinarySearchTree<>();
    }

    @Test
    public void testShouldInsertItemToBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);
    }

    @Test
    public void testShouldGetMaxItemFromBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);

        assert(binarySearchTreeSUT.getMax()  == 8);
    }

    @Test
    public void testShouldGetMinItemFromBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);

        assert(binarySearchTreeSUT.getMin()  == 2);
    }
    @Test
    public void testShouldTraverseItemsFromBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);

        binarySearchTreeSUT.traversal();
    }

    @Test
    public void testShouldDeleteLeafNOdeItemsFromBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);

        binarySearchTreeSUT.traversal();

        binarySearchTreeSUT.delete(3);

        binarySearchTreeSUT.traversal();
    }

    @Test
    public void testShouldDeleteParentNodeWithBothChildrenItemsFromBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);

        binarySearchTreeSUT.traversal();

        binarySearchTreeSUT.delete(4);

        binarySearchTreeSUT.traversal();
    }

    @Test
    public void testShouldDeleteParentNodeWithBothChildrenItemsFromBSTWithSuccessor(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(7);

        binarySearchTreeSUT.traversal();

        binarySearchTreeSUT.delete(4);

        binarySearchTreeSUT.traversal();
    }

    @Test
    public void testShouldDeleteParentNodeWithOneChildrenItemsFromBST(){

        binarySearchTreeSUT.insert(4);
        binarySearchTreeSUT.insert(8);
        binarySearchTreeSUT.insert(2);
        binarySearchTreeSUT.insert(3);

        binarySearchTreeSUT.traversal();

        binarySearchTreeSUT.delete(2);

        binarySearchTreeSUT.traversal();
    }

}

Your tests seem to be of appropriate size and scope but there are a couple things I'd address.

Assertions
First and foremost I don't see your code asserting on anything.
You manipulate the binarySearch tree, which is the first step, but then you don't check the state of it afterward.  As a reviewer I'd ask "what are your tests actually testing?"

Magic numbers
It's clear you thought about what each test was supposed to accomplish but the intent of the test could be clearer to the reader.  You could try adding meaning to the numbers you are inserting to the tree, adding comments, or some other way of making the purpose of each test very clear to the reader.


jQuery plugin to cycle through text and "typewrite" it out I have written a jQuery plugin (my first for a long time) that simply cycles through strings of text in a data attribute and uses setInterval to type it out - it's a common effect you've probably seen hundreds of times.

I'm looking for a code review of the JavaScript/jQuery portion of the code mainly because a lot of the literature on building a jQuery plugin is quite old and I want to be sure I'm doing things the "modern" way.

CodePen

$(document).ready(function() {
  $().typeText();
});

(function($) {

  $.fn.typeText = function(options) {

    var settings = $.extend({
      loopSpeed: 5000,
      typeSpeed: 100,
      selector: '.words'
    }, options);

    var typeIntervals = [];

    load();

    function load() {

      $(settings.selector).each(function() {
        var wordsArray = $(this).data('words').split(',');
        var length = wordsArray.length - 1;
        var index = 0;
        var thisWordGroup = $(this);;
        if (typeof $(this).data('index') == 'undefined') {
          $(thisWordGroup).data('index', 0);
        }
        $(this).html(wordsArray[0]);
      });

      setIntervals();

    }

    function setIntervals() {

      setInterval(function() {
        clearTypeIntervals();
        $(settings.selector).each(function() {
          var thisWordGroup = $(this);
          var wordsArray = thisWordGroup.data('words').split(',');
          var length = wordsArray.length - 1;
          var index = thisWordGroup.data('index');
          index++;
          if (index > length) {
            index = 0;
          }
          thisWordGroup.data('index', index);
          type(thisWordGroup, wordsArray[index]);
        });
      }, settings.loopSpeed);

    }

    function type($selector, word) {
      $selector.html('');
      var index = 0;
      var splitWord = word.split('');
      var splitWordLength = splitWord.length - 1;
      var intervalName = 'typeWordInterval' + Math.ceil(Math.random() * 99999);
      typeIntervals[intervalName] = setInterval(function() {
        var currentText = $selector.html();
        $selector.html(currentText + splitWord[index]);
        if (index < splitWordLength) {
          index++
        } else {
          clearInterval(typeIntervals[intervalName])
        }
      }, settings.typeSpeed);
    }

    function clearTypeIntervals() {
      for (var element in typeIntervals) {
        clearInterval(typeIntervals[element]);
      }
    }

  }

}(jQuery));

The API design is rather weird.  You expect your plugin to be called like

$().typeText({ selector: '.words' })

But a design like this would be much more natural for jQuery:

$('.words').typeText()


Ruby Interrupted Bubble Sort Working through CodeEval's Interrupted Bubble Sort, I have a working algorithm, but there's a speed issue.  I'm trying to do this with Ruby and I keep getting an error that it's timing out after 10 seconds.  I'm not sure what else I could be doing here to speed things up.

def bubble(arr, interrupt)

    i = 0
    while i < interrupt
        for x in 1..arr.length-1
            if arr[x-1] > arr[x]
                arr[x-1], arr[x] = arr[x], arr[x-1]
            end
        end
        i += 1
    end

end

File.open(ARGV[0]).each_line do |line|

    line = line.chomp.split(" ");
    interrupt = line.pop.to_i
    line.pop

    line.map do |x| x = x.to_i end
    bubble(line, interrupt)
    puts line.join(" ")

end

There shouldn't be a speed issue (so far as I can tell), but there is an outright bug:

line.map do |x| x = x.to_i end

You're not storing the result of the map, you're just throwing it away. So line doesn't change, and you end up comparing the elements lexicographically, i.e. as strings. So "48" ends up being less "5" and such.

Other notes:

The Ruby convention is to use 2 spaces for indentation. Not 4 spaces, not tabs.
You don't need semicolons.
When writing a single line block, use {..} instead of do..end
When simply invoking the same single method on all elements in an array, you can use a shortcut: line.map(&:to_i)
You can exclude the last element in a range with 3 dots (...), so 1..arr.length-1 becomes just 1...arr.length

With that and a few other things you get:

def bubble(array, iterations)
  iterations.times do
    (1...array.length).each do |i|
      if array[i-1] > array[i]
        array[i-1], array[i] = array[i], array[i-1]
      end
    end
  end
end

File.open(ARGV[0]).each_line do |line|
  line = line.chomp.split(" ")
  iterations = line.last.to_i

  values = line[0...-2].map(&:to_i)
  bubble(values, iterations)

  puts values.join(" ")
end

Now, this is just a challenge, but for production code, I'd avoid the side-effects of bubble, and return a new array instead. But that's a different story.

Edit: Since it's still too slow, maybe it's because the input is crafted to trick you. For instance, a line that calls for billions of iterations on a relatively small set of values will, with the code above, cause waaay too many pointless iterations. I.e. the list may be sorted already, but the algorithm will keep loop through it the specified number of times.

A pretty simple solution would be something like:

def bubble(array, iterations)
  iterations.times do
    sorted = true
    (1...array.length).each do |i|
      if array[i-1] > array[i]
        sorted = false
        array[i-1], array[i] = array[i], array[i-1]
      end
    end
    break if sorted
  end
end

Additionally, you can skip stuff by checking the number of iterations before calling bubble. If it's zero, there's no need for the map:

File.open(ARGV[0]).each_line do |line|
  line = line.chomp.split(" ")
  iterations = line.last.to_i

  unless iterations.zero?
    values = line[0...-2].map(&:to_i)
    bubble(values, iterations)
  end

  puts values.join(" ")
end

Now of course it may just be that the input is just huge, and Ruby isn't the fastest thing. But one has to assume that the challenge can actually be solved.


Build process for compiling client JS modules into one script I am currently writing a rather large client-side JS application which is made of of multiple modules, each in different files (before compiling). I am using Node.js to build the final script based on all the individual modules.

For the script to work properly all modules must be added in the proper order, so they can access any modules they depend on. One way to solve this is by maintaining an array of all the modules in the correct order to be inserted. I find that limiting though, having to add each file manually and in the correct position.

I have come up with a different solution to this, and would love to get some feedback on it.

First I have one wrapper file, which is wraped around all the modules. Looks like this:

(function( ns ){

var module = window[ns] = {

    _modules: window[ns] && window[ns]._modules || {},

    exports: function( name, mod ){
        this._modules[name] = mod;
    },

    require: function( name ){
        var mod = this._modules[name];
        if(!mod) throw new Error(name + ' module not found');
        return mod;
    }
};

MODULES_INSERT

})( '_myCoolApp' );

Where it says "MODULES_INSERT" is where the modules get inserted.

Now inside the individual modules it looks something like this:

// export this module
module.exports('view', View);

function View(){ etc.. }

// import other module
var util = module.require('util');

And finally I have my build script (node.js) which adds all the modules/files, and orders them based on any module.requires they contain in their code, ensuring that all dependencies are loaded before they are required:

for(i in srcFiles){
    file = srcFiles[i];
    var content = fs.readFileSync(file.src);
    content = '(function(){\n' + content;
    content = content + '})();\n';

    // find any module dependencies
    var match, requires = [], regex = /module.require\(['"]([^'"]+)/g;
    while(match = regex.exec(content)){
        requires.push(match[1]);
    }

    file.requires = requires;
    file.content = content;
}

for(i in srcFiles){
    file = srcFiles[i];
    recurse(file);
}

function recurse(file){
    if(!file) return;

    if(file.requires.length > 0) {
        file.requires.forEach(function(req){
            recurse(srcFiles[req]);
        });
    }
    if(!file.added) results.push(file.content);
    file.added = true;
}

code = results.join('');
code = wrapper.replace('MODULES_INSERT', code);

Is this solution way overkill? One downside I see to this, is what happens when two files require each other, which gets loaded first? Is there a more effective solution for this?

Your approach is sound. The optimizer of RequireJS called r.js also scans the code for calls to methods with a special name (define and require) to detect dependencies.

You can see how this detection works in the file transform.js. As you can see, this optimizer uses a JavaScript parser, which is more reliable than using regular expressions: for example, your regular expression may match a call in a comment, which would be skipped using a parser.

There is another way to declare dependencies for RequireJS though, which is described in the Asynchronous Module Definition specification: wrap each module in a call to a function and list the dependencies explicitly in an array.

You may also be interested in the use of a simpler pattern for the declaration of modules, independently of the loader used.

With regards to circular dependencies ("when two files require each other"), there are two ways to handle them:

detect them and fail, forcing the developer to avoid them in their code
load one of the two modules with only parts of their dependencies, which requires extra care from developers: they can no longer be sure that all dependencies are available when the module runs, and must check before calling methods and accessing properties on required objects

Both approaches have drawbacks.


Function to count words in Python I am new to developing in Python and would like to see comments about my word count solution.

Please indicate my mistakes or best solutions.

def count_words(text):
  text = text.lower()

  symbols = "1234567890!#$%^&*\"()_+=-{}[].,:"
  for s in list(symbols):
    text = text.replace(s,"")
  text = text.split()
  lst = list(set(text))
  dictonary = {"words":lst, "nums":[0]*len(lst)}
  for word in text:
    dictonary['nums'][dictonary['words'].index(word)] += 1

  import pandas as pd
  df = pd.DataFrame(dictonary)
  return df.sort_values(by=['nums'], ascending=False)#.to_csv("./words.csv")

count_words("Hello world, World War, War and Peace")

How about using collections.Counter:

import string
from collections import Counter

def count_words(text):
    text = text.lower()
    for s in string.digits + string.punctuation:
        text = text.replace(s, "")
    text = text.split()
    return Counter(text)

print(count_words("Hello world, World War, War and Peace"))


PHP simple template loader This is not really a question but I'd like to obtain some opinions about this simple class. For an old project I had the necessity to load some php template files that includes some foreach() and for() loops and other variables loaded from a database. I was start thinking how to obtain this using a templating class and this is what I wrote to achieve the objective, I've reworked a templating class that works well with html and php files that doesn't need to load data from variables. I know that I can also use simply the include, require or include_once and require_once but writing a reusable class was the solution that seemed to me more reliable. Can this class to be considered useful? Is it possible to improve it by using magic methods like __set() and __get() to output the desired data to a loop? In the usage example I will not post the $data variable that is an array of data loaded from database, this choiche is because I don't want to write a long post.

<?php

class Template{

    private $tpl;
    private $fileName;
    private $templatePath;

    public function __construct($templatePath){
        $this->templatePath = $templatePath;
    }

    public function loadTemplate(string $tpl){
        $this->fileName = basename($tpl.'.php');
        if(file_exists($this->templatePath.'/'.$this->fileName)){
             return $this->templatePath.'/'.$this->fileName;
        } else {
            throw new Exception('Template not found.');
        }
    }

}

?>

Usage example:

<?php

require_once 'Template.class.php';
//$data = array(); this array comes from a db
//$results = array(); this is an handmade array
$template = new Template('path/to/template/file');

include($template->loadTemplate('demo'));
?>

Template file that is loaded

            <?php for($i = 0; $i < count($data); $i++): ?>
              <?php echo $data[$i]['h']; ?>
              &nbsp;-&nbsp;
              <?php echo $data[$i]['a']; ?>

<?php echo $results[mt_rand(1,12)]; ?>

            <?php endfor;?>

This is not a template class at all, but sort of a wrapper for file_exists() function. It does nothing of the templating business but just gets you a filename.

To make it a template class,

make it accept an array with all data used in the template
add a render() function that will extract data array into separate variables and then include the template file.
add some sort of auto-escaping feature (like going through the data array recursively and escaping all scalar values)
a possibility to return the rendered HTML instead of outputting it
add some facility to call a "master" template that will add the common site design to the certain page's template.

So a usage example would be

require_once 'Template.class.php';
$data = [
    'data' => $data,
    'results' => $results,
];
$template = new Template('path/to/template/file');
$template->render($data);

Quite off topic but consider a more tidy syntax for your template.

        <?php foreach($data as $row): ?>
          <?= $row['h'] ?>
          &nbsp;-&nbsp;
          <?= $row['a'] ?>

<?= $results[mt_rand(1,12)] ?>

        <?php endforeach ?>


Java code for Linked List I've been practicing implementing a linked list from scratch. Can someone help review my code?

class Node {
    Node next;
    int num;

    public Node(int val) {
        num = val;
        next = null;
    }
}

public class LinkedList {

    Node head;

    public LinkedList(int val) {
        head = new Node(val);
    }

    public void append(int val) {
        Node tmpNode = head;
        while (tmpNode.next != null) {
            tmpNode = tmpNode.next;
        }
        tmpNode.next = new Node(val);
    }

    public void insert(int val) {
        Node currentNode = head;
        Node nextNode = head.next;

        if (currentNode.num > val) {
            Node tmpNode = head;
            head = new Node(val);
            head.next = tmpNode;
            return;
        }

        if (nextNode != null && nextNode.num > val) {
            currentNode.next = new Node(val);
            currentNode.next.next = nextNode;
            return;
        }

        while (nextNode != null && nextNode.num < val) {
            currentNode = nextNode;
            nextNode = nextNode.next;
        }

        currentNode.next = new Node(val);
        currentNode.next.next = nextNode;
    }

    public void delete(int val) {
        Node prevNode = null;
        Node currNode = head;

        if (head.num == val) {
            head = head.next;
            return;
        }

        while (currNode != null && currNode.num != val) {
            prevNode = currNode;
            currNode = currNode.next;
        }

        if (currNode == null) {
            System.out.println("A node with that value does not exist.");
        }
        else {
            prevNode.next = currNode.next;
        }

    }

    public void print() {
        Node tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.num + " -> ");
            tmpNode = tmpNode.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        LinkedList myList = new LinkedList(5);
        myList.append(7);
        myList.append(16);
        myList.insert(9);
        myList.insert(4);
        myList.insert(6);
        myList.insert(17);
        myList.delete(16);
        myList.delete(5);
        myList.delete(4);
        myList.delete(17);
        myList.delete(34);
        myList.print();
    }
}

Your implementation does not allow for an empty list.

It's a bit odd to only have the constructor which takes a node value.

You should probably implement the List interface.
You should look into generics instead of hard-coding your list to only take ints.
It looks like from looking at insert() that you are trying to create an ordered linked list.  However, append() does not.  (If you really want to define an ordered linked list, you can still use generics, but you'll have to use types which are children of Comparable).
In insert() and delete() you have some if-conditions followed by a while-loop.  My guess is that they can be merged in a single while-loop.  I was lazy and haven't tried doing it, so it might not be true.


Phonebook using a trie I implemented a PhoneBook utilizing a Trie data structure.

Could I ask you to evaluate it?

Did I apply Trie correctly for such case or is it better to store data somehow else?

I'm looking not only for working solution but also for an optimal one in terms of run-time and storage.

From my calculations, it takes NlogT to add() and get() where N is a number of chars and T is a number of children.

Am I right?

Here is the logic

public final class PhoneBook {

    private final Node name;

    private final Node surname;

    private final Comparator<Record> comparator;

    public PhoneBook() {
        this.name = new Node();
        this.surname = new Node();
        comparator = (r1, r2) -> {
            int result = r1.getName().compareTo(r2.getName());
            if (result == 0) {
                result = r1.getSurname().compareTo(r2.getSurname());
                if (result == 0) {
                    result = r1.getNumber().compareTo(r2.getNumber());
                }
            }
            return result;
        };
    }

    public void add(final Record record) {
        add(record.getName().toLowerCase(), record, name);
        add(record.getSurname().toLowerCase(), record, surname);
    }

    public SortedSet<Record> get(final String prefix) {
        final String lc = prefix.toLowerCase();
        final List<Record> recordsRetrievedByName = get(lc, name);
        final List<Record> recordsRetrievedBySurname = get(lc, surname);
        final SortedSet<Record> result = new TreeSet<>(comparator);
        result.addAll(recordsRetrievedByName);
        result.addAll(recordsRetrievedBySurname);
        return result;
    }

    private List<Record> get(final String prefix, final Node ancestor) {
        Node node = ancestor;
        for (final char c: prefix.toCharArray()) {
            final Node child = node.children.get(c);
            if (child == null) {
                return Collections.emptyList();
            }
            node = child;
        }
        return node.records;
    }

    private void add(final String str, final Record record, final Node ancestor) {
        Node node = ancestor;
        for (final char c: str.toCharArray()) {
            final Node child;
            if (node.children.containsKey(c)) {
                child = node.children.get(c);
            } else {
                child = new Node();
                node.children.put(c, child);
            }
            child.records.add(record);
            node = child;
        }
    }

    private static final class Node {

        private final Map<Character, Node> children = new TreeMap<>();

        private final List<Record> records = new ArrayList<>();

    }

}

And the Record immutable object

public final class Record {

    private final String name;

    private final String surname;

    private final String number;

    //constructor, getters, toString
}

Naming:

name and surname are somewhat unclear in what they specifically mean. The "actual" purpose of these variables is to serve as "root" of the trie. Incidentally I'd rename ancestor to rootin all the usages in your code, simply because I'm more used to it. YMMV :)
I'd rename name and surname to nameRoot and surnameRoot.

Simplifications:

Initialize private fields that are not dependent on constructor arguments in the field declaration to save on space and complexity.
Use Comparator.comparing and thenComparing to simplify your comparator.

I personally also prefer to not leave too much space between fields.

private final Node name = new Node();
private final Node surname = new Node();
private static final Comparator<Record> comparator = Comparator.comparing(Record::getName)
    .thenComparing(Record::getSurname).thenComparing(Record::getNumber);

Note that I also changed the comparator to be static. It could also do with a better name, but I'm coming up empty right now...

Possible Trie Optimizations:

Currently your trie is using a lot of memory. It's not quite as bad as it could be, but considering that names are very much non-uniform, you will have a lot of "degenerated branches", where the branching factor is very low, if not 1 for "long" stretches of the data structure.

These long stretches of basically linked lists can be collapsed by sacrificing a WORD of memory to store how many characters you can skip before the next actual branching.

Currently Node does not support this in any way.

The traversal during add can be simplified a bit with computeIfAbsent like so:

for (final char c: str.toCharArray()) {
    final Node child = node.children.computeIfAbsent(c, Node::new);
    child.records.add(record);
    node = child;
}

This simplification pretty quickly vanishes when you implement the optimization mentioned above (or rather it becomes somewhat complicated).


Implementation of a templated Singly linked list class in c++ The code below is my implementation of singly linked list.I would prefer it, if you kindly review the code and give me pointers on how a professional programmer would have written the code. Basically, i want to know about some good code habits that I have missed in the code.

The class one_way_linked_list is the linked list class. It uses the node class to create the nodes of the list. It keeps record of every object's head node using the head pointer. The function list_create() creates the list. The function list_print() prints the code. The function list_delete() deletes the linked list by deallocating every node one by one.

Sorry for my english, as it is not my native language. Thank you in advance.

#include <iostream>

using namespace std;

template<typename t>
class node
{

public:
    t data;
    node *next;

    //constructors
    node()
    {
        next=NULL;
    }
    node(t d)
    {
        data=d;
        next=NULL;
    }
};

template<typename t>
class one_way_linked_list
{
    node<t> n;
public:
    node<t> *head=NULL;
    node<t> *prev=NULL;

    void list_create(t);
    void list_print();
    void list_delete()
};

template <typename t>
void one_way_linked_list<t>::list_create(t dat)
{
    node<t> *ptr=new node<t>(dat);
    if(head==NULL)
{
    head=ptr;
    prev=head;
}
else
{
    prev->next=ptr;
    prev=ptr;
}
}

template<typename t>
void one_way_linked_list<t>::list_print()
{
    node<t> *ptr=this->head;
    cout<<"Printing the list: "<<endl;
    while(ptr!=NULL)
    {
        cout<<ptr->data<<" ";
        ptr=ptr->next;
    }
    cout<<endl;
}

template<typename t>
void one_way_linked_list<t>::list_delete()
{
    node<t> *ptr=new node<t>();
    ptr->data=this->head->data;
    while(ptr!=NULL)
    {
        ptr=ptr->next;
        delete ptr;
    }
    delete this->head;
    head=NULL;
    cout<<"Deleted"<<endl;
}

int main()
{
    //driver program for int type list
    one_way_linked_list<int> list1;
    int temp;
    while(1)
    {
        cin>>temp;
        if(temp==-1) break;
        else
        {
            list1.list_create(temp);
        }
    }
    list1.list_print();
    list1.list_delete();
    list1.list_print();
}

Advice 1

You can move the definition of node into the declaration body of one_way_linked_list. This allows "inheritting" the type parameter t, and, thus, omitting it altogether in the node.

Advice 2

node(t d)
{
    data=d;
    next=NULL;
}

The more C++ way would be:

node(t d) : data{d}, next{nullptr} {}

Advice 3

Most C++ programmers write the type parameters starting from an uppercase letter. In your case, I suggest you rename t to T in the template declaration.

Advice 4

public:
    node<t> *head=NULL;
    node<t> *prev=NULL;

Here, you expose the implementation details. Move the two under a private:. Also, write nullptr instead of NULL.

Advice 5

prev: a better name is tail.

Advice 6

list_create: a better name is add or append.

Advice 7

template<typename t>
void one_way_linked_list<t>::list_delete()
{
    node<t> *ptr=new node<t>();
    ptr->data=this->head->data;
    while(ptr!=NULL)
    {
        ptr=ptr->next;
        delete ptr;
    }
    delete this->head;
    head=NULL;
    cout<<"Deleted"<<endl;
}

rewrite as:

node<t>* next;
node<t>* current = head;

while (current) {
    next = current->next;
    delete current;
    current = next;
}


Visualization of bubble sort in progress I've written a program showing the process of bubble sort arithmetic in C.  I need some suggestions on improving it.

#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
#define WIDE (SIZE * 2)

void RepaintScreen(int *pData, int count, int p1, int p2)
{
    system("cls");
    char b[(WIDE + 1) * (SIZE)];
    b[0] = '\0';
    for (int i = 0; i < count; i++)
    {
        if (i == p1 || i == p2)
        {
            strcat(b, "-->");
        } else {
            strcat(b, "   ");
        }
        for (int j = 0; j < pData[i]; j++)
        {
            strcat(b, "|");
        }
        strcat(b, "\n");
    }
    printf("%s", b);
}

void BubbleSort(int *pData, int count)
{
    int iTemp;
    for (int i = 0; i < count; i++)
    {
        for (int j = count - 1; j > i; j--)
        {
            if (pData[j] < pData[j - 1])
            {
                iTemp = pData[j];
                pData[j] = pData[j - 1];
                pData[j - 1] = iTemp;
                RepaintScreen(pData, count, i, j); //refresh the screen
                Sleep(10);
            }
        }
    }
}

int main( int argc, char **argv )
{
    int data[SIZE];
    srand(time(NULL));
    //initiate data
    for (int i = 0; i < SIZE; i++)
    {
        data[i] = rand() % WIDE;
    }
    BubbleSort(data, SIZE);
    return 1;
}

Your code works nicely.

In BubbleSort I would move the definition of iTemp to the point of first use.  The name iTemp is ugly and the 'i' makes me think you are using a type prefix (as does the 'p' in pData). I don't know anyone who thinks that is a good idea - just use temp and data.

In RepaintScreen I don't see the need to buffer the data yourself.  You can just use stdio to buffer it for you:

static void RepaintScreen(const int *data, int count, int p1, int p2)
{
    for (int i = 0; i < count; i++) {
        fputs((i == p1 || i == p2) ? "-->" : "   ", stdout);

        for (int j = 0; j < data[i]; j++) {
            putc('|', stdout);
        }
        putc('\n', stdout);
    }
}

If you do accumulate a string, using strcat is inefficient and prone to buffer overflow. It is inefficient because on each call it must traverse the whole string to find the end. It would be better to keep track of the end of the string yourself.  For example:

static void RepaintScreen(const int *data, int count, int p1, int p2)
{
    system("cls");
    char buf[(WIDE + 1) * (SIZE)];
    char *b = buf;

    for (int i = 0; i < count; i++) {
        if (i == p1 || i == p2) {
            *b++ = '>';
        } else {
            *b++ = ' ';
        }
        for (int j = 0; j < data[i]; j++) {
            *b++ = '|';
        }
        *b++ = '\n';
    }
    *b++ = '\0';
    fputs(buf, stdout);
}

Overflow occurs if you get the size of the buffer size wrong. Avoiding overflow is messy as you must check that there is enough space each time you insert into the buffer and exit sensibly if there is not. Using fputs/putc, as shown above, avoids overruns.


C-string manipulation I'd just like to get some pointers on my newbie-ish C here. The intention is to have an environment variable provide the "prefix" for any paths this app needs.

For example, APP_PREFIX could be /opt/app, a path the app wanted to get could be /etc/app.conf, and so app_path("/etc/app.conf") should return /opt/app/etc/app.conf.

I realise this is currently sensitive to leading/trailing slashes; I just wanted to make sure I'm on the right track with this basic stuff. Be as pedantic as you like – from outright bugs down to style and convention.

It compiles with no warnings on Mac OS X with gcc -Wall -pedantic ..., and does what I expect it to. On Linux, I had to compile with libbsd, and #include <bsd/string.h> for strlcpy() and strlcat().

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define APP_PREFIX_ENV_VAR "APP_PREFIX"

const char * app_path_prefix() {
    char * env_prefix = getenv(APP_PREFIX_ENV_VAR);
    if (env_prefix == NULL) {
        return "";
    } else {
        return env_prefix;
    }
}

char * app_path(char * in_path) {
    const char * prefix = app_path_prefix();
    size_t prefix_len = strlen(prefix);
    size_t out_size = prefix_len + strlen(in_path) + 1;
    char * out = malloc(out_size);

    strlcpy(out, prefix, prefix_len + 1);
    strlcat(out, in_path, out_size);
    return out;
}

int main(int argc, char ** argv) {
    char * path = app_path(argv[1]);
    printf("result: '%s'\n", path);
    free(path);
    return EXIT_SUCCESS;
}

All seems good.

As you mentioned it is sensitive to trailing slash being missing. I would just force that issue and always append one between the prefix and the path. An extra slash will not hurt but a missing one will.

Apart from not using C in the first place :-) all my other issues are simple stylistic ones that only 30% of people would agree (I always divide stylistic camps as 30% Side A, 30% side ~A, 40% don't care).

A tiny bit more white space to make it easier to read. But let me just say your code is not bad in that regards (just slightly less than I would use).

I don't want to recommend any particular style. But I can show you how I would have written it:

// Keep you includes sorted in alphabetical order
// Here it is not such a big deal but with big projects the list can get big
// and alphabetical order helps you find things in large lists.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define APP_PREFIX_ENV_VAR "APP_PREFIX"

const char * app_path_prefix()
{
    char * env_prefix = getenv(APP_PREFIX_ENV_VAR);
    return (env_prefix == NULL)
               ? ""
               : env_prefix;
}

char * app_path(char * in_path)
{
    /*
     * Some people really hate this.
     *
     * Others like myself really like lining up the '=' sign
     * Just do it locally with a set of calculations. I find it easier to see
     * both the lhs and the rhs of expression quickly.
     */
    char const* prefix     = app_path_prefix();
    size_t      prefix_len = strlen(prefix);
    size_t      out_size   = prefix_len + strlen(in_path) + 1;

    /*
     * Dynamically allocated. Released to outside world it is the
     * responsibility of the caller to free this memory
     */
    char *      out        = malloc(out_size);

    strlcpy(out, prefix, prefix_len + 1);
    strlcat(out, in_path, out_size);
    return out;
}

int main(int argc, char ** argv)
{
    /* test */
    char * path = app_path(argv[1]);
    printf("result: '%s'\n", path);
    free(path);

    return EXIT_SUCCESS;
}


Joining and resolving two paths while keeping them relative conditionally I would like to have a function Chain-Paths to accomplish the following: given a base directory (Base) and a location, possibly relative to that given Base (Chained), output the result of joining both paths. If however Chained is already an absolute path, just return that. If both paths are relative, keep the result relative as well.

The above, reformulated in test cases (works if run from a user directory, e.g. C:\Users\ojdo):

$testCases = @(
    @{
        Base = "..\..\Windows\Fonts"
        Chained = "..\system32\notepad.exe"
        Expected = "..\..\Windows\system32\notepad.exe"
    }
    @{
        Base = "C:\Windows\Fonts"
        Chained = "..\system32\notepad.exe"
        Expected = "C:\Windows\system32\notepad.exe"
    }
    @{

        Base = "AppData\Roaming"
        Chained = "C:\Windows\system32\notepad.exe"
        Expected = "C:\Windows\system32\notepad.exe"
    }
)

foreach ($case in $testCases) {
    $expectedResult = $case.Expected
    $actualResult = (Chain-Paths $case.Base $case.Chained)
    $testResult = if($actualResult -eq $expectedResult) {"PASS"} else {"FAIL"}

    Write-Host ("{0}: {1} == {2}" -f $testResult, $actualResult, $expectedResult)
}

This is the function I have come up with:

function Chain-Paths($Base, $Chained)
{
    if (Split-Path $Chained -IsAbsolute) {
        return $Chained
    } else {
        $joinedPath = Join-Path $Base $Chained
        if (Split-Path $Base -IsAbsolute) {
            return (Resolve-Path $joinedPath).Path
        } else {
            return Resolve-Path $joinedPath -Relative
        }
    }
}

My questions:

Am I overcomplicating things?
Is there a way to simplify things by using a .net function?
Is the (...).Path really required?
Any stylistic recommendations (apart from missing docstring)?

You can use the System.IO.Path.Combine Method.

  This method is intended to concatenate individual strings into a single string that represents a file path. However, if an argument other than the first contains a rooted path, any previous path components are ignored, and the returned string begins with that rooted path component.

$combined = [IO.Path]::Combine($Base, $Chained)

Also, it seems more natural to use System.IO.Path.IsPathRooted() method instead of Split-Path to see if the path is absolute.

$isRelative = ![IO.Path]::IsPathRooted($combined)

There is a way to pass parameter values by appending a colon after the parameter name in cmdlet. You can also pass values to the switch type parameter this way.

Verb-Noun -ParameterName:Value

Resolve-Path basically outputs a PathInfo object, but when the -Relative switch is set the output will be string.
Both types have a ToString () method, so you can get a path string without using an if statement. (The ToString() method of the PathInfo object outputs the value of the Path property)

function Chain-Path($Base, $Chained) {
    $combined = [IO.Path]::Combine($Base, $Chained)
    $isRelative = ![IO.Path]::IsPathRooted($combined)
    (Resolve-Path $combined -Relative:$isRelative).ToString()
}


Adding/remving dynamically text boxes I have this coding and I think it works. However, I would like to understand if there is a better way to do this. This would automatically create new textboxes or delete them based on the given selected number.

<select id=cornercases name=cornercases>
    <option value="1">1</option>
    <option value="2">2</option>
    <option value="3">3</option>
    <option value="4">4</option>
    <option value="5">5</option>
    <option value="6">6</option>
    <option value="7">7</option>
    <option value="8">8</option>
    <option value="9">9</option>
    <option value="10">10</option>
</select>

$(document.createElement('div')). ...

is the same as:

$('

'). ....

you can just build uppon your previus jQuery statements:

$('

')
    .attr('id','lol')
    .html('hey hey')
    .appendTo("#div_selection_section");

$("#cornercases").change(function () {
        CORNER_CASE_LOADING();
    });

is the same as:

$("#cornercases").change(CORNER_CASE_LOADING);

and you can bind 2 events in one with jQuery so:

$("#cornercases").bind("change ready",CORNER_CASE_LOADING)

you might want to
parsInt topvalue in the line with te var

var topvalue = parseInt($('#cornercases').val());

you will not need to repeat pareInt in each 'if' if you do that.

Also, I see that
OLD_CASE_NUMBER is an integer (and if you do what is mesioned above), you won't need to parse that either

as far as I see the second line of your function var counter = 0; is useless, because everywhere you use counter you first set it to something else


Morris inorder traversal Morris Inorder traversal - an algorithm for in-order traversal, of a tree, without recursion of extra memory. Looking for code review, optimizations and best practices.

public class MorrisInOrder<T> {

    TreeNode<T> root;

    /**
     * Takes in a BFS representation of a tree, and converts it into a tree.
     * here the left and right children of nodes are the (2*i + 1) and (2*i + 2)nd
     * positions respectively.
     *
     * @param items The items to be node values.
     */
    public MorrisInOrder(List<? extends T> items) {
        create(items);
    }

    private void create (List<? extends T> items) {
        root = new TreeNode<T>(null, items.get(0), null);

        final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode<T> current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode<T>(null, items.get(left), null);
                    queue.add(current.left);
                }
                if (right < items.size() && items.get(right) != null) {
                    current.right = new TreeNode<T>(null, items.get(right), null);
                    queue.add(current.right);
                }
            }
        }
    }

    private static class TreeNode<T> {
        TreeNode<T> left;
        T item;
        TreeNode<T> right;

        TreeNode(TreeNode<T> left, T item, TreeNode<T> right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    /**
     * Returns the inorder traversal of the tree.
     *
     * @return list containing inorder traversal of elements
     * @throws NoSuchAlgorithmException
     */
    public List<T> inOrder() throws NoSuchAlgorithmException {
        if (root == null) throw new NoSuchAlgorithmException("The root is null.");

        final List<T> list = new ArrayList<T>();
        TreeNode<T> current  = root;

        while (current != null) {
            if (current.left == null) {
                list.add(current.item);
                current = current.right;
            } else {
                TreeNode<T> predecessor = current.left;
                /*
                 * found the in-order predecessor.
                 */
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // hook it up.
                    predecessor.right = current;
                    current = current.left;
                } else {
                    list.add(current.item);
                    predecessor.right = null;
                    current  = current.right;
                }
            }
        }
        return list;
    }
}

public class MorrisInOrderTest {

    @Test
    public void testBalancedTree() throws NoSuchAlgorithmException {
        final MorrisInOrder<Integer> morrisInOrder1 = new MorrisInOrder<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        assertEquals(Arrays.asList(4, 2, 5, 1, 6, 3, 7), morrisInOrder1.inOrder());
    }

    @Test
    public void testUnBalancedTree() throws NoSuchAlgorithmException {
        final MorrisInOrder<Integer> morrisInOrder2 = new MorrisInOrder<Integer>(Arrays.asList(1, 2, 3, 4, 5, null, null));
        assertEquals(Arrays.asList(4, 2, 5, 1, 3), morrisInOrder2.inOrder());
    }
}

private void create (List<? extends T> items) {
    root = new TreeNode<T>(null, items.get(0), null);

This crashes if an empty list is passed in. And since you have this function...

public MorrisInOrder(List<? extends T> items) {
    create(items);
}

It's entirely possible for such a thing to happen.

final int left = 2 * i + 1;
final int right = 2 * i + 2;

right can be set to left + 1 instead.

current  = current.right;

and

TreeNode<T> current  = root;

There's an extra space in here.

            /*
             * found the in-order predecessor.
             */
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }

You're using a block-style comment for single line comment. Why?


Is this a safe way to parse out HTML tag attributes? I needed a super simple parser to get HTML attributes and their values. I didn’t want to load a big library or anything so I made this.

I realize I am making assumptions here, mainly:

Attribute values will be surrounded with either single or double
quotes.
The input string will end with > or />.

Besides those assumptions are there any other glaring issues here?

Dictionary<string, string> HTMLAttributes(string tag)
{
    Dictionary<string, string> attr = new Dictionary<string, string>();

    MatchCollection matches =
        Regex.Matches(tag, @"([^\t\n\f \/>""'=]+)(?:=)('.*?'|"".*?"")(?:\s|\/>|\>)");

    foreach (Match match in matches)
    {
        attr.Add(match.Groups[1].Value,
            match.Groups[2].Value.Substring(1, match.Groups[2].Value.Length - 2)
            );
    }

    return attr;
}

Running:

HTMLAttributes("<body class=\" something \" hello='world' />");

Returns:

{
    class: " something ",
    hello: "world"
}

Sample:

http://ideone.com/ZBaBhB

Whitespace around = is allowed, your regex won't handle that.
Characters in HTML can be encoded, some characters (like &) have to be encoded. For example name="AT&amp;T" should return that the value of name is AT&T.


For names sake - Project Euler 22 Project Euler - 22

Names scores

  Using names.txt (right click and 'Save Link/Target As...'), a 46K text
    file containing over five-thousand first names, begin by sorting it
    into alphabetical order. Then working out the alphabetical value for
    each name, multiply this value by its alphabetical position in the
    list to obtain a name score.

  For example, when the list is sorted into alphabetical order, COLIN,
    which is worth \$3 + 15 + 12 + 9 + 14 = 53\$, is the 938th name in the
    list. So, COLIN would obtain a score of \$938 × 53 = 49714\$.

  What is the total of all the name scores in the file?

While being fairly comfortable with the zen of Python, Julia is very new to me. Is the following code in line with Julia's vision?

In particular I feel my handling of the dictionary is sub-optimal and especially the way i hard-code remove the parenthesis in names.

Every hint on how to improve the code is welcome.

ALPHABET_INDEX = Dict( letter => index for (index, letter) in enumerate('A':'Z'))

function namescore(name)
    return sum(ALPHABET_INDEX[letter] for letter in name[2:end-1])
end

function sort_file(filename)
    file = open(filename)
    sort(split(readstring(filename),","))
end

function PE_022(filename="p022_names.txt")

    total = 0
    for (index, name) in enumerate(sort_file(filename))
        total += index*namescore(name)
    end
    total
end

println(PE_022())

the only change I would make is to remove your use of the Dict. Dicts are great when you need mutability, but here there is the much simpler solution Int(letter)-Int('A'). With this change, namescore becomes

function namescore(name)
    return sum(Int(char)-Int('A') for letter in name[2:end-1])
end

This, however is not ideal, as we can take out the subtraction, yielding

function namescore(name)
    return sum(Int(char) for letter in name[2:end-1]) - (lenth(name)-2) * Int('A')
end

I haven't done performance testing, but this should be a fair bit faster, as I would expect Int to be faster than a dictionary lookup.


Sequence-based enumeration of permutations in lexicographic order This is follow-up on
On Knuth's "Algorithm L" to generate permutations in lexicographic order,
where I presented the following method to enumerate all permutations of array elements
in lexicographic order:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] < self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] >= self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] < self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] >= self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This question is about using that method to create a Swift Sequence with all permutations, so that one can
simply enumerate these with for .. in loops and related techniques. My first approach is to use
the "type erasers" AnySequence and AnyIterator, which leads to this simple
implementation:

func permutations<T: Comparable>(of a: [T]) -> AnySequence<[T]> {
    var current = a.sorted()
    var done = false
    return AnySequence {
        return AnyIterator {
            if done { return nil }
            defer { done = !current.permute() }
            return current
        }
    }
}

Example usage:

for p in permutations(of: [3, 2, 1]) {
    print(p)
}

let allPerms = Array(permutations(of: ["B", "A", "C"]))
print(allPerms)

So this is easy to use, but what about performance? Here my benchmark code
(on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode):

let N = 10
var count = 0
let start = Date()
for _ in permutations(of: Array(1...N)) { count += 1 }
let end = Date()
print(count, end.timeIntervalSince(start))

This takes about 1.3 seconds, i.e. it is much slower than calling permute() on a mutable
array in a loop, which takes only 0.03 seconds (see On Knuth's "Algorithm L" to generate permutations in lexicographic order).

It gets a bit better if we implement our own sequence type instead of using the
type erasers:

struct PermutationSequence<T: Comparable>: Sequence, IteratorProtocol {
    private var current: [T]
    private var done: Bool

    init(elements: [T]) {
        self.current = elements.sorted()
        self.done = false
    }

    func makeIterator() -> PermutationSequence {
        return self
    }

    mutating func next() -> [T]? {
        if done { return nil }
        let retval = current
        done = !current.permute()
        return retval
    }
}

Benchmark:

let N = 10
var count = 0
let start = Date()
for _ in PermutationSequence(elements: Array(1...N)) { count += 1 }
let end = Date()
print(count, end.timeIntervalSince(start))

which takes about 0.8 seconds.

All feedback is welcome. In particular I am interested in making Sequence-based
enumeration of all permutations as fast as possible.

Performance

I'm not particularly surprised that the version of permutations(of:) which uses AnySequence and AnyIterator is so slow.

You're paying for the cost of both:

Heap allocation and reference counting for both the captured array and done flag.
Copy-on-write upon mutating the array in the defer block, as a copy of the array needs to be taken in order to return it to the caller prior to the mutation.

Therefore immediately you can speed things up by simply reducing the amount of closure capture – for example if you just removed the AnySequence wrapper and just returned an AnyIterator:

func permutations<T: Comparable>(of a: [T]) -> AnyIterator<[T]> {
    var current = a.sorted()
    var done = false
    return AnyIterator {
        if done { return nil }
        defer { done = !current.permute() }
        return current
    }
}

You can still use an AnyIterator in a for-in loop due to the fact that it conforms to Sequence itself, and just returns itself as its own iterator. Iterating through it will 'consume' the elements returned, but you get the same behaviour by wrapping it in an AnySequence due to the fact that it's ultimately capturing the same array.

From AnySequence to AnyIterator improves my benchmark time (using the same measurement setup as shown in your question) from ~1.1 seconds to ~0.95 seconds.

However, as you note, we can do better than that by removing the closures entirely by simply declaring our own custom iterator type – PermutationSequence.

struct PermutationSequence<T: Comparable>: Sequence, IteratorProtocol {
    private var current: [T]
    private var done: Bool

    init(elements: [T]) {
        self.current = elements.sorted()
        self.done = false
    }

    func makeIterator() -> PermutationSequence {
        return self
    }

    mutating func next() -> [T]? {
        if done { return nil }
        let retval = current
        done = !current.permute()
        return retval
    }
}

This reduces my benchmark time down to ~0.75 seconds.

However, the problem with this implementation, as @dfri points out, is that we're still paying the cost of copy-on-write at each iteration due to the fact that both retval and current have a view onto the underlying array buffer.

The solution to this is fairly simple, as you noted, we return the array after the mutation has taken place, and just maintain a flag so we don't do a mutation on the first iteration. This could look like:

struct PermutationSequence<Element : Comparable> : Sequence, IteratorProtocol {

    private var current: [Element]
    private var firstIteration = true

    init(startingFrom elements: [Element]) {
        self.current = elements
    }

    init<S : Sequence>(_ elements: S) where S.Iterator.Element == Element {
        self.current = elements.sorted()
    }

    mutating func next() -> [Element]? {

        // if it's the first iteration, we simply return the current array.
        if firstIteration {
            firstIteration = false
            return current
        }

        // do mutation – if the array has changed, then return it,
        // else we're at the end of the sequence.
        return current.permute() ? current : nil
    }
}

Note that I've also:

Removed the makeIterator() implementation as there's already a default implementation for this when the sequence is its own iterator.
Renamed the generic placeholder from T to Element, as it's a more descriptive name for it.
Added an init(startingFrom:) initialiser, as I suspect it will be quite useful to allow the sequence to resume from a given permutation, rather than always starting at the first.
Removed the argument label from init(elements:), as it was already clear what the initialiser does and made it take a generic Sequence input for increased flexibility.

Now we're no longer paying for the cost of an array copy at each iteration due to the fact that the iterator always has a single view onto the array's buffer (though the current property), reducing my benchmark time down to ~0.1 seconds (the target is ~0.02 seconds for directly applying permute() in repeat-while loop).

The key to achieving the target performance weirdly appears to be avoiding having multiple exits in the implementation of next().

If we refactor the iterator's next() method like this, so that there's only one return:

mutating func next() -> [Element]? {

    var continueIterating = true

    // if it's the first iteration, we avoid doing the permute() and reset the flag.
    if firstIteration {
        firstIteration = false
    } else {
        continueIterating = current.permute()
    }

    // if the array changed (and it isn't the first iteration), then return it,
    // else we're at the end of the sequence.
    return continueIterating ? current : nil
}

we are able to achieve the desired benchmark time of ~0.02 seconds. Exactly why this reduces the time so dramatically, I'm not too sure – it appears that having multiple points of exit in the method prevents the compiler from performing some important optimisation.

It also appears to be related to inlining, as when marking the next() method with the @inline(never) attribute, the use of an additional return has no significant impact on the performance. I'd certainly be interested if anyone else knows more about exactly what's going on here.

Regarding your comment about making shouldContinue (renamed to continueIterating here) a let constant – I could not observe a difference in performance in doing so, so I left it as a var.

Separating the sequence and iterator

Depending on your usage, it may be useful to separate your permutation sequence implementation from its iterator in order to allow for non-destructive iteration (this isn't required for a sequence, but can be useful in places).

This would just be as simple as having the sequence keep its own constant copy of the array prior to mutation, which gets passed to the iterator on its creation.

In Swift 3.1, this can be expressed rather nicely with a nested generic type:

struct PermutationSequence<Element : Comparable> : Sequence {

    // constant copy of the elements to pass to the iterator on its creation.
    let elements: [Element]

    init(startingFrom elements: [Element]) {
        self.elements = elements
    }

    init<S : Sequence>(_ elements: S) where S.Iterator.Element == Element {
        self.elements = elements.sorted()
    }

    struct Iterator : IteratorProtocol {

        private var current: [Element]
        private var firstIteration = true

        // you should create a PermutationSequence rather than invoking this
        // initialiser directly.
        fileprivate init(startingFrom elements: [Element]) {
            self.current = elements
        }

        mutating func next() -> [Element]? {

            var continueIterating = true

            // if it's the first iteration, we avoid doing the permute() and reset the flag
            if firstIteration {
                firstIteration = false
            } else {
                continueIterating = current.permute()
            }

            // if the array changed (and it isn't the first iteration), then return it,
            // else we're at the end of the sequence.
            return continueIterating ? current : nil
        }
    }

    func makeIterator() -> Iterator {
        return Iterator(startingFrom: elements)
    }
}

This shouldn't adversely affect the performance in any way (benchmarking doesn't reveal any significant difference) – an initial copy of the array may have to be taken upon the first mutation, but that's also true for the previous version of PermutationSequence due to the fact that the caller has a view onto the array buffer.


Cis 194: Homework 3 (Histogram) I am following CIS 194: Introduction to Haskell (Spring 2013) online to teach myself Haskell. Following is my response to third exercise of Homework 3, namely Histogram.

In which ways I could improve this, without getting too much into advanced topics of Haskell?

{-
For this task, write a function
histogram :: [Integer] -> String
which takes as input a list of Integers between 0 and 9 (inclusive),
and outputs a vertical histogram showing how many of each number
were in the input list. You may assume that the input list does not
contain any numbers less than zero or greater than 9 (that is, it does
not matter what your function does if the input does contain such
numbers). Your output must exactly match the output shown in the
examples below.

-}
histogram :: [Integer] -> String
histogram numbers =
    let initialcounts = take 10 (repeat 0)
        calculatedcounts = histogramcount numbers initialcounts
        maxheight = maximum calculatedcounts
        linefunctions = map drawline [maxheight,maxheight-1..1]
    in unlines ((map ($ calculatedcounts) linefunctions) ++ ["==========","0123456789"])

histogramcount :: [Integer] -> [Int] -> [Int]
histogramcount [] counts = counts
histogramcount (x:xs) counts =
    let
        xint = fromIntegral x
        newcount = (counts !! xint) + 1
    in histogramcount xs (take xint counts ++ [newcount] ++ drop (xint+1) counts)

drawline :: Int -> [Int] -> String
drawline level = map (\x -> if x >= level then '*' else ' ')

main = do
    putStr $ histogram [1,1,1,5]
    putStr $ histogram [1,4,5,4,6,6,3,4,2,4,9]

See below for comments on your overall approach, but taking the approach as a given, here are a few observations:

First, it seems unusual to pass initialcounts to histogramcount instead of making histogramcount self-contained.  Also, histogramcount is kind of a long name for such a simple function, and take 10 (repeat 0) is more succinctly written replicate 10 0.  Finally, the complex step of actually incrementing the count seems like it deserves its own function, so I might write:

-- |Return counts of integers from 0 to 9
count :: [Integer] -> [Int]
count = loop (replicate 10 0)
  where loop counts (x:xs) = loop (increment x counts) xs
        loop counts []     = counts

-- |Add one to a given count
increment :: Integer -> [Int] -> [Int]
increment x counts =
  let xint = fromIntegral x
      newcount = (counts !! xint) + 1
  in  take xint counts ++ [newcount] ++ drop (xint+1) counts

There's no particular reason to name linefunctions, and if you write:

map ($ calculatedcounts) (map drawline [maxheight,maxheight-1..1])

a pair of maps like this simplifies to a single map:

map (\height -> drawline height calculatedcounts) [maxheigh,maxheight-1..1]

which might be more clearly written as a list comprehension anyway:

[drawline h calculatedcounts | h <- [maxheight,maxheight-1..1]]

giving:

histogram :: [Integer] -> String
histogram numbers =
  unlines $ [drawline h counts | h <- [maxh,maxh-1..1]] ++ footer
  where counts = count numbers
        maxh = maximum counts
        footer = ["==========","0123456789"]

Note that Haskell code usually uses pretty short names for temporary variables.  It's also more common to use a where clause rather than a let clause when the variables being defined are just helpers, secondary to the main expression.  (Here, counts is arguable not secondary to the main expression, though that raises the question of whether or not we should separate out the function that graphs a set of 10 counts instead of combining it with the counting itself... hmm...)

The drawline function seems okay.  Again, maybe a list comprehension is clearer:

drawline :: Int -> [Int] -> String
drawline level counts = [if x >= level then '*' else ' ' | x <- counts]

or maybe you want to go the route of being excessively clever:

drawline :: Int -> [Int] -> String
drawline level = map (bool ' ' '*' . (>= level))

Before doing that, we should revisit increment.  It's pretty terrible.  The take/drop pair can be replaced with the more efficient splitAt standard function which can simultaneously fetch the current count and get everything prepared to update the count, like so:

-- |Add one to a given count
increment :: Integer -> [Int] -> [Int]
increment x counts =
  case splitAt (fromIntegral x) counts of
    (a,n:b) -> a ++ (n+1):b

That's better, and fairly idiomatic.  Note the use of a ++ (n+1):b in place of a ++ [n+1] ++ b, too.  That's pretty standard.

After you complete next week's lesson, you may discover that count is a fold and rewrite it as:

count :: [Integer] -> [Int]
count = foldr increment (replicate 10 0)

Further down the line, you may become concerned about whether a left fold would have been better for efficiency purposes, but there's not much point in worrying about that now.

Putting it all together, including breaking histogram up into the counting and the plotting and pulling the drawline helper function into the plot function, I might rewrite your program as:

-- |Plot histogram of counts
histogram :: [Integer] -> String
histogram = plot . count

-- |Return counts of integers from 0 to 9
count :: [Integer] -> [Int]
count = foldl (flip increment) (replicate 10 0)

-- |Add one to a given count
increment :: Integer -> [Int] -> [Int]
increment x counts =
  case splitAt (fromIntegral x) counts of
    (a,n:b) -> a ++ (n+1):b

-- |Plot a vertical bar chart of counts
plot :: [Int] -> String
plot counts =
  unlines $ [drawline h | h <- [maxh,maxh-1..1]] ++ footer
  where drawline level = [if x >= level then '*' else ' ' | x <- counts]
        maxh = maximum counts
        footer = ["==========","0123456789"]

main = do
  putStr $ histogram [1,1,1,5]
  putStr $ histogram [1,4,5,4,6,6,3,4,2,4,9]

Finally, I'd run hlint on it.  It gives "No hints", but if I'd run it earlier, it would have mentioned replicate 10 0 and recommended a foldl for the count version that used recursive loop calls.

Is this better than your original?  Well, I think so, of course, or I wouldn't be writing this.  I think the main improvements are:

removing long names for things that aren't very important, like linefunctions or initialcounts
giving top-level names to self-contained actions like count, increment, and plot that perform more well-defined operations than your original "histogramcount" and "drawline"

Now, let's get back to your overall approach.  The main criticism I have is that, like many new Haskell programmers, you're still trying to get over the tendency to use Haskell as an alternate syntax for writing Python (or any other imperative programming language of your choice).  You've started with an array of counts:

counts = [0] * 10    # Python syntax!

and you've looped over the input data, updating each count as you go:

for c in data:
    counts[c] += 1

Unfortunately, Haskell isn't Python, so you've had to represent your running counts as a list.  It has to be passed around as an extra argument, and it not only provides inefficient O(n) access to individual elements but also requires creating an updated immutable copy for every processed data point using the abominable expression:

take xint counts ++ [newcount] ++ drop (xint+1) counts

or its equally hideous cousin:

case splitAt (fromIntegral x) counts of (a,n:b) -> a ++ (n+1):b

Now, one "improvement" would be to switch from inefficient lists to an efficient Vector type to hold your counts.  Honestly, though, the resulting program would still be designed around your original imperative solution, and we aren't seriously concerned with efficiency here anyway.  If we need to process a few million data points, the fact that counting is slow isn't really the biggest issue as we try to generate hundreds of thousands of lines of vertical histogram output.

Instead, to really get a feeling for how Haskell programming is supposed to work, I'd suggest that you take a careful look at Data.List and try to imagine using the functions there as a pipeline of transformations on your data that gradual convert it from [Integer] to String.  See if you can do it without keeping track of any intermediate state, like counts or the current line "level" or anything like that.  As a hint, note that if you were to sort your data and then group it, you'd be close to having a set of required counts.

SPOILERS

Here's a super Haskelly solution to this problem.  Note how its just a pipeline of functional transformations composed together.  Read the pipeline from the bottom-up to understand how it works:

haskellHistogram :: [Integer] -> String
haskellHistogram =
    unlines      -- and print it as lines
  . reverse      -- flip it upside down
  . (['0'..'9']:) . (replicate 10 '-':)  -- add the header rows
  . takeWhile (any (=='*'))  -- take rows until we run out of stars
  . transpose    -- switch from horizontal rows of stars to vertical columns
  . map (  (++ repeat ' ')       -- extend with (infinite) spaces
         . flip replicate '*'    -- represent count as stars
         . (subtract 1)          -- drop the extra number we added
         . length                -- get the count
        )        -- for each group
  . group        -- group into 0s, 1s, 2s, etc.
  . sort         -- sort the input
  . ([0..9]++)   -- add one of each to ensure non-zero counts

I wrote that in one go, starting at the end of the pipeline and working my way backward, in about 5 minutes.  After it type checked and I tested it, I found I'd forgotten the unlines (because my type signature was wrong!) and the subtract 1, but it otherwise worked correctly.  That's what makes Haskell programming so much fun.


Calculating GCD for 2 integers I have implemented a method which takes 2 numbers and returns the Greatest Common Divisor, using the Euclidean algorithm.
The Euclidean algorithm goes like this:
If we take the numbers 585 and 442:

585 / 442 = 1 (remainder 143)
442 / 143 = 3 (remainder 13)
143 / 13 = 11 (remainder 0)

The process stops here and GCD = 13.
Is there any way I can make this implementation better, considering time, resources and refactoring?
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("Input first number: ");
        int x = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine("Input second number: ");
        int y = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine(GetGCD(x, y));

        Console.ReadKey();
    }

    static int GetGCD(int x, int y)
    {
        while (Math.Max(x, y) % Math.Min(x, y) != 0)
        {
            int tmp = Math.Max(x, y) % Math.Min(x, y);
            if (x < y) y = tmp;
            else x = tmp;
        }

        return Math.Min(x, y);
    }
}

Recursive Method

You can change your GetGCD() method to be much more intuitive and minimal using a ternary operator and recursion. I recommend also documenting what it's doing for readability purposes:

static int GetGCD(int x, int y)
{
    // If y is equal to 0, return x.
    // If y is not equal to 0, recursive call with x as y and y as the remainder.
    return y == 0 ? x : GetGCD(y, x % y);
}

Can also be written as:

static int GetGCD(int x, int y)
{
    // If y is equal to 0, return x.
    if (y == 0)
        return x;
    // If y is not equal to 0, recursive call with x as y and y as the remainder.
    return GetGCD(y, x % y);
}

Depending on your preference.

Iterative Method

As stated in other answers, you might use an iterative method:

static int GetGCD(int x, int y)
{
    while (y != 0)
    {
        int tmp = x % y;
        x = y;
        y = tmp;
    }
    return x;
}

Entry Point

Use TryParse() for retrieving integer input from the console. We don't want exceptions on user input.

Modular arithmetic should be positive. To ensure this, we use the absolute value of the input (Euclidean division). Here's how I would implement it:

static void Main()
{
    int x, y;

    // Get x. Ensure it's an integer.
    Console.WriteLine("Input first number: ");
    while(!Int32.TryParse(Console.ReadLine(), out x));

    // Get y. Ensure it's an integer.
    Console.WriteLine("Input second number: ");
    while(!Int32.TryParse(Console.ReadLine(), out y));

    // Ensure the values being used are positive.
    Console.WriteLine(GetGCD(Math.Abs(x), Math.Abs(y)));

    Console.ReadKey();
}

Output

As you can see, it will wait for an input that can be parsed to an integer and returns the expected value:

Input first number:
a
b
c
585
Input second number:
d
442
13

Benchmark

Just for fun, I thought I'd test the difference between the recursive and iterative methods.

Benchmarked method: Recursive
Test cases: 20
Bench in MS: 184
Iterations per case: 10000000

Benchmarked method: Iterative
Test cases: 20
Bench in MS: 121
Iterations per case: 10000000

The difference is negligible in real application (unless you plan to run this millions of times). These tests were run from entirely different processes.


(Java) Read .txt and organize activities for hours / minutes Doubts in logic to generate the output file according to the example
I need that even if he reaches the total_min <720 condition he continues to travel the lines. 720 is the total number of minutes before lunch, when reached, it should separate the activities that should be performed after lunch (lunch must be inserted manually).

I need to make a system that reads a TXT file (intput.txt).
This file has several lines.
Each line an activity with execution time (30min, 45min, 60min)
Activities should start at 9 am.
Half day (12:00) lunch break
Generate a TXT with organized activities (output.txt)

  intput.txt

Correr 60min
Estudar 30min
Ler 45min
Escrever 60min
Caminhar 45min
Jogar 30min

  Example how the output.txt file should look

09:00 Correr 60min
10:00 Estudar 30min
10:30 Ler 45min
11:15 Caminhar 45min
12:00 Almoço 60min
13:00 Jogar
(...)

  My code:

    public static void main(String[] args) throws IOException {
    // TODO code application logic here

    ArrayList<String> antes_almoco = new ArrayList<String>();
    ArrayList<String> depois_almoco = new ArrayList<String>();

    int total_min = 540;
    int horas = total_min / 60;
    int minutos = total_min % 60;
    String trinta = "30min";
    String quarentaCinco = "45min";
    String sessenta = "60min";
    boolean trinta_min = false;
    boolean quarentaCinco_min = false;
    boolean sessenta_min = false;
    String path = "C:\\input.txt";
    String outputDir = "C:\\output.txt";

    FileReader arq = new FileReader(path);
    BufferedReader lerArq = new BufferedReader(arq);
    String linha;

    //Output
    File file2 = new File(outputDir);
    FileWriter arq_output = new FileWriter(file2, true);
    PrintWriter gravarArq = new PrintWriter(arq_output);

    if (!file2.exists()) {
        file2.createNewFile();
    }

    while ((linha = lerArq.readLine()) != null) {

        trinta_min = linha.toLowerCase().contains(trinta.toLowerCase());
        quarentaCinco_min = linha.toLowerCase().contains(quarentaCinco.toLowerCase());
        sessenta_min = linha.toLowerCase().contains(sessenta.toLowerCase());

        if (sessenta_min == true) {
            total_min += 60;
            if (total_min < 720) {
                antes_almoco.add(linha);
            } else if (total_min > 720) {
                depois_almoco.add(linha);
            }
        }

        if (trinta_min == true && total_min < 720) {
            total_min += 30;
            if (total_min < 720) {
                antes_almoco.add(linha);
            } else if (total_min > 720) {
                depois_almoco.add(linha);
            }
        }

        if (quarentaCinco_min == true && total_min < 720) {
            total_min += 45;
            if (total_min < 720) {
                antes_almoco.add(linha);
            } else if (total_min > 720) {
                depois_almoco.add(linha);
            }
        }

        if (total_min == 720) {
            total_min += 60;
            antes_almoco.add("12:00 Almoço");
        }
    }

    for (String cont : antes_almoco) {
        System.out.println(cont);
        gravarArq.printf("%d:%02d %s \n", horas, minutos, cont);
    }
    for (String cont : depois_almoco) {
        //System.out.println(cont);
        gravarArq.printf("%d:%02d %s \n", horas, minutos, cont);
    }
    lerArq.close();
    gravarArq.close();
    arq.close();
}

I revised your code and ran some tests.

Here is the input to my last test.

Correr 60min
Estudar 30min
Ler 45min
Escrever 60min
Caminhar 45min
Cutting of steel sheets 60min
Jogar 30min

Here is the output from my last test.

09:00 Correr 60min
10:00 Estudar 30min
10:30 Ler 45min
11:15 Escrever 60min
12:15 Almoço 60min
01:15 Caminhar 45min
02:00 Cutting of steel sheets 60min
03:00 Jogar 30min

The first major change I made to your code was to write a method to convert elapsed minutes to time.

I only needed one List to hold the events.  Actually, I didn't need the List at all.  I could have written the string out as I created it, but I left the List in.

I also simplified the processing of each line.  All I need is the number of minutes that the event lasts.  This code can handle any number of minutes, not just 30, 45, or 60.

Edited to add: I revised the code to handle an input line with an event that has spaces in the event text.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Schedule {

    public static void main(String[] args) throws IOException {
        // TODO code application logic here

        List<String> events = new ArrayList<>();

        String path = "C:\\Eclipse\\Eclipse-2020-workspace\\"
                + "com.ggl.testing\\resources\\input.txt";
        String outputDir = "C:\\Eclipse\\Eclipse-2020-workspace\\"
                + "com.ggl.testing\\resources\\output.txt";

        FileReader arq = new FileReader(path);
        BufferedReader lerArq = new BufferedReader(arq);

        // Output
        File file2 = new File(outputDir);
        FileWriter arq_output = new FileWriter(file2, true);
        PrintWriter gravarArq = new PrintWriter(arq_output);

        if (!file2.exists()) {
            file2.createNewFile();
        }

        int totalMinutes = 0;
        int lunchMinutes = 180;
        boolean beforeLunch = true;

        String linha;
        while ((linha = lerArq.readLine()) != null) {
            String[] fields = linha.split(" ");
            int lastIndex = fields.length - 1;
            int endIndex = fields[lastIndex].lastIndexOf("min");
            int duration = Integer.valueOf(
                    fields[lastIndex].substring(0, endIndex));

            String output = "";
            for (int i = 0; i < fields.length; i++) {
                output += fields[i] + " ";
            }
            output = toTime(totalMinutes) + " " + output;
            events.add(output.trim());

            totalMinutes += duration;

            if (beforeLunch && totalMinutes >= lunchMinutes) {
                output = toTime(totalMinutes) + " Almoço 60min";
                events.add(output);
                totalMinutes += 60;
                beforeLunch = false;
            }
        }

        for (String cont : events) {
            System.out.println(cont);
            gravarArq.println(cont);
        }

        lerArq.close();
        gravarArq.close();
        arq.close();
    }

    private static String toTime(int minutes) {
        int hours = minutes / 60 + 9;
        hours = hours % 12;
        hours = (hours == 0) ? 12 : hours;
        minutes = minutes % 60;
        return String.format("%02d:%02d", hours, minutes);
    }

}


Python wrapper for official Hacker News API Since Hacker News launched their official API, I started working on Python wrapper for it. API v0 is fairly simple, you send a GET request with hacker news story's ID or user id, it returns data in JSON.

Here I do the same using requests library and return specific object like Item for news story or comment and User for a user on Hacker News.

All source can be found here.

#!/usr/bin/env python

__all__ = [
    'User',
    'Item',
    'HackerNews',
    'InvalidAPIVersion',
    'InvalidItemID',
    'InvalidUserID']

"""
haxor
Unofficial Python wrapper for official Hacker News API
"""

import datetime
import json

import requests

from settings import supported_api_versions
# supported_api_versions = {'v0': 'https://hacker-news.firebaseio.com/v0/'}

class InvalidItemID(Exception):
    pass

class InvalidUserID(Exception):
    pass

class InvalidAPIVersion(Exception):
    pass

class HackerNews(object):

    def __init__(self, version='v0'):
        try:
            self.base_url = supported_api_versions[version]
        except KeyError:
            raise InvalidAPIVersion

    def _get(self, url):
        response = requests.get(url)
        if response.status_code == requests.codes.ok:
            return response
        else:
            raise Exception('HTTP Error: {}'.format(response.status_code))

    def get_item(self, item_id):
        response = self._get('{0}item/{1}.json'.format(self.base_url, item_id))

        if not response.json():
            raise InvalidItemID

        return Item(response.json())

    def get_user(self, user_id):
        response = self._get('{0}user/{1}.json'.format(self.base_url, user_id))

        if not response.json():
            raise InvalidUserID

        return User(response.json())

    def top_stories(self, limit=None):
        response = self._get('{}topstories.json'.format(self.base_url))
        return response.json()[:limit]

    def get_max_item(self):
        response = self._get('{}maxitem.json'.format(self.base_url))
        return response.json()

class Item(object):

    """
    Represents stories, comments, jobs, Ask HNs and polls
    """

    def __init__(self, data):
        self.item_id = data.get('id')
        self.deleted = data.get('deleted')
        self.item_type = data.get('type')
        self.by = data.get('by')
        self.submission_time = datetime.datetime.fromtimestamp(
            data.get(
                'time',
                0))
        self.text = data.get('text')
        self.dead = data.get('dead')
        self.parent = data.get('parent')
        self.kids = data.get('kids')
        self.url = data.get('url')
        self.score = data.get('score')
        self.title = data.get('title')
        self.parts = data.get('parts')
        self.raw = json.dumps(data)

    def __repr__(self):
        return '{0}: {1}'.format(self.item_id, self.title)

class User(object):

    """
    Represents a hacker i.e. a user on Hacker News
    """

    def __init__(self, data):
        self.user_id = data.get('id')
        self.delay = data.get('delay')
        self.created = datetime.datetime.fromtimestamp(data.get('time', 0))
        self.karma = data.get('karma')
        self.about = data.get('about')
        self.submitted = data.get('submitted')
        self.raw = json.dumps(data)

    def __repr__(self):
        return '{0}: {1}'.format(self.user_id, self.karma)

response.json() appears repeatedly here and in other methods:

def get_item(self, item_id):
    response = self._get('{0}item/{1}.json'.format(self.base_url, item_id))

    if not response.json():
        raise InvalidItemID

    return Item(response.json())

You could simplify by getting .json() in the first place:

def get_item(self, item_id):
    data = self._get('{0}item/{1}.json'.format(self.base_url, item_id)).json()

    if not data:
        raise InvalidItemID

    return Item(data)

This could be more efficient, because you can't really know for sure if the .json() is implemented lazily (evaluating things only once), or every time you call it. In fact, the speed difference is noticeable after this change, when you iterate over a list of items.

self.base_url appears in many methods, for example:

def get_item(self, item_id):
    response = self._get('{0}item/{1}.json'.format(self.base_url, item_id))
    # ...

def get_user(self, user_id):
    response = self._get('{0}user/{1}.json'.format(self.base_url, user_id))
    # ...

def top_stories(self, limit=None):
    response = self._get('{}topstories.json'.format(self.base_url))
    return response.json()[:limit]

def get_max_item(self):
    response = self._get('{}maxitem.json'.format(self.base_url))
    return response.json()

To reduce the duplication, you could introduce some more helper methods like ._get, for example:

def _get_page(self, page):
    return self._get('{0}{1}.json'.format(self.base_url, page))

def _get_page_param(self, page, param):
    return self._get('{0}{1}/{2}.json'.format(self.base_url, page, param))

Using these new methods, you could simplify the above methods:

def get_item(self, item_id):
    response = self._get_page_param('item', item_id)
    # ...

def get_user(self, user_id):
    response = self._get_page_param('user', user_id)
    # ...

def top_stories(self, limit=None):
    return self._get_page('topstories').json()[:limit]

def get_max_item(self):
    return self._get_page('maxitem').json()