Muzietto’s gists

Muzietto / LogicalKnapsack01

Last active January 4, 2017 17:04

A knapsack 0/1 algo that cycles first and foremost through the knapsack weights - clumsier but more logical

	function knapsack01(maxWeight, items, returnAllKnapsacks) {
	items = items.sort((a,b)=>a.weight-b.weight);

	var knapsacks = new Array(maxWeight + 1);
	for (var i = 0; i <= maxWeight; i++) {
	knapsacks[i] = new Array(items.length);
	for (var j = 0; j < items.length; j++) {
	knapsacks[i][j] = 0;
	};
	};

Muzietto / BetterMinimalNumberOfCoins.js

Created December 31, 2016 18:01

Dynamic programming self-tuition - minimal number of coins needed to reach a given total amount (BETTER SOLUTION)

	function betterMinNumOfCoins(coinages, amount) {
	// sort coinages
	coinages = coinages.sort((a,b)=>a-b);
	var minCoinage = Math.min.apply(null, coinages);
	var dp = new Array(amount + 1).fill(Infinity);
	dp[0] = 0;
	for (var i = 1; i <= amount; i++) {
	for (var j = 0; j < coinages.length; j++) {
	var coinage = coinages[j];
	if (coinage > i) break;

Muzietto / MinimalNumberOfCoins.js

Last active December 31, 2016 18:03

Dynamic programming self-tuition - minimal number of coins needed to reach a given total amount

	function minNumOfCoins(coinages, amount) {
	if (amount === 0) return 0;
	if (coinages.length === 0 && amount > 0) return Infinity;

	var maxCoinage = Math.max.apply(null, coinages);
	var otherCoinages = coinages.filter(coinage => coinage !== maxCoinage)
	if (amount < maxCoinage) return minNumOfCoins(otherCoinages, amount);

	var coinsWithMaxCoinage = minNumOfCoins(coinages, amount - maxCoinage) + 1;
	var coinsWithoutMaxCoinage = minNumOfCoins(otherCoinages, amount);

Muzietto / BoardsCoveringRooftopHoles.js

Created December 31, 2016 09:16

Human-readable solution for the problem at the end of https://codility.com/media/train/12-BinarySearch.pdf

	function boardsBinarySearch(A, numBoards) {
	var n = A.length;
	var minBoardSize = 1;
	var maxBoardSize = n;
	var result = -1;
	while (minBoardSize <= maxBoardSize) {
	var tentativeBoardSize = Math.floor((minBoardSize + maxBoardSize) / 2);
	if (neededBoards(A, tentativeBoardSize) <= numBoards) {
	result = tentativeBoardSize;
	maxBoardSize = tentativeBoardSize - 1;

Muzietto / NailingPlanks.js

Created December 31, 2016 08:58

Human-readable solution for the NailingPlanks puzzle at Codility (https://codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/)

	function solution(A,B,C) {
	return nailsBinarySearch(A,B,C);
	}

	function nailsBinarySearch(boardStarts, boardEnds, nailPositions) {
	var boards = boardStarts.map((cur, curIndex) => [cur, boardEnds[curIndex]],[]);
	var lowerBorderNailsNumber = 1;
	var upperBorderNailsNumber = nailPositions.length;
	var minimalNailsNumber = -1;

Muzietto / MinMaxDivision.js

Created December 31, 2016 08:37

Human-readable solution for the MinMaxDivision puzzle at Codility (https://codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/)

	function solution(K, M, A) {
	// M is a red herring
	return minimalLargeSumBinarySearch(K, A);
	}

	function minimalLargeSumBinarySearch(maxNumBlocks, arra) {
	var lowerBoundLargeSum = Math.max.apply(null, arra);
	var upperBoundLargeSum = arra.reduce((a,c)=>a+c,0);
	var result = -1;

Muzietto / StandaloneServer.java

Created December 15, 2016 13:38

Launching a standalone Jetty to run whatever...

	package com.wcg.product.ajax.ajaxserver.connectors;

	import java.net.URL;

	import org.apache.commons.lang.StringUtils;
	import org.eclipse.jetty.server.Server;
	import org.eclipse.jetty.xml.XmlConfiguration;

	public class StandaloneServer {

Muzietto / ClassNotFoundCrappyEclipse.bug

Created December 1, 2016 11:05

When tests do not start on Eclipse due to ClassNotFoundException

	- right-click project with issue
	- maven --> update project
	- de-select "clean projects" at the bottom
	- OK

Muzietto / pom.xml with annotations

Last active November 30, 2016 11:15

pom.xml with annotations

	<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>
	<parent>
	<groupId>com.xxx.yyy</groupId>
	<artifactId>XXXX</artifactId>
	<version>1.2.0-SNAPSHOT</version>
	</parent>
	<groupId>xxx.yyy.migration</groupId>
	<artifactId>YYY</artifactId>

Marco Faustinelli Muzietto