title: Multiply without multiply

text:
# Question
Title: Multiply without multiply
Write the fastest (best big-O) and smallest multiplication algorithm for positive integers, without using multiplication operators. You are only allowed addition, subtraction, logical functions (AND, OR, XOR, NOT), bit shift, bit rotate, bit flip/set/clear and bit test. Your program should be capable of multiplying 16-bit numbers to produce a 32-bit result. Take input on stdin, separated by commas, spaces or new lines (your choice), but make it clear how to input the data.

**Example input/output:**

```
734 929
681886

```

# Answer
> 11 votes
# C, ~~84~~ ~~83~~ 78 Characters

```
m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

```

In a more readable form

```
m;main(a,b)
{
    scanf("%d%d",&a,&b);
    while (a)
    {
        if (a&1)
           m+=b;
        a>>=1;
        b+=b;
    }
    printf("%d\n",m);
}

```

The algorithm is better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.Here’s the algorithm :

1. Let the two numbers to be multiplied be a and b.
2. If a is zero then break and print the result.
3. If a is odd then add b to the result.
4. Half a, Double b. Goto Step 2.

# Answer
> 7 votes
## APL (5)

Takes input on standard input separated by newlines.

```
+/⎕⍴⎕

```

# Answer
> 5 votes
## Golfscript - 12 characteres

```
~0\{1$+}*\;

```

Please note that `*` here is *not* the multiplication operator, it's instead a repetition operator, see the second use here.

# Answer
> 4 votes
## Golfscript - 27 chars

Peasants multiplication. There first * in there *is* a multiply, but only by 0 or 1

```
~2base-1%{1&\..+\@*}%{+}*\;

```

Here's on at 31 chars that doesn't multiply at all

```
~2base-1%{1&\..+\[0\]@=}%{+}*\;

```

# Answer
> 4 votes
# Python, 64 chars

Probably not the most efficient though (or the most compliant, but I'm "adding", aren't I?):

```
a=int(raw_input())
print sum(a for i in range(int(raw_input())))

```

# Answer
> 3 votes
# Ruby, 30

```
->(a){Array.new(*a).inject:+}

```

Based on GigaWat answer.

# Answer
> 2 votes
## Golfscript - 43

```
~\:@;0 1{.3$&{\@+\}{}if@@+:@;.+.3$>!}do;\;

```

Implementation of the peasant multiplication. I think I may be able to golf it some more later on.

# Answer
> 2 votes
# Python, also 64 chars

```
m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())

```

# Answer
> 2 votes
# J, 18 17 characters

```
+/({.${:)".1!:1]3

```

Input needs to be space separated.

# Answer
> 1 votes
## A variation in Scala, optimized for size: 48 chars

```
def m(a:Int,b:Int):Int=if(b==1)a else a+m(a,b-1)

```

### optimized for speed a bit:

```
def mul (a:Int, b:Int) : Int = {
  print (".")
  if (a == 1) b
  else if (a > b) mul (b, a)
  else if (a % 2 == 0) mul (a >> 1, b << 1)
  else b + mul (a - 1, b)
}

```

I swap (a, b) if (a \> b), to reach the end more fast. The difference is 11 to 20 steps, when calling mul (1023,31), compared with omitting that line of code.

### golfed: 95 chars:

```
def m(a:Int,b:Int):Int=if(a==1)b
else if(a>b)m(b,a)
else if(a%2==0)m(a>>1,b<<1)
else b+m(a-1,b)

```

# Answer
> 1 votes
# Ruby, 35 bytes

```
def x(a)Array.new(*a).inject :+end

```

Usage: `x([123, 456]) #=> 56088`

Could probably be shortened if the numbers are read from ARGV, but it complains about them being the wrong format (strings, not ints). Any suggestions would be great.

# Answer
> 1 votes
## VBA, 70 chars

This is actually quite slow for large numbers, but it's small. I managed to improve the code size while improving speed. Calculation time varies, depending on argument position - not just size. (i.e. 1000, 5000 computes in about 4 seconds while 5000, 1000 calculates in about 19) Since the OP lists both fast and small, I figured I'd go with this one. Input is two numeric args, comma separated.

```
Sub i(j,k)
For m=1 To j:n=n & String(k," "):Next
MsgBox Len(n)
End Sub

```

This longer version (**103 chars**) will ensure it runs with the faster of the two possible arrangements:

```
Sub i(j,k)
If j<k Then a=j:b=k Else b=j:a=k
For m=1 To a:n=n & String(b," "):Next
MsgBox Len(n)
End Sub

```

# Answer
> 1 votes
## Perl: 52 chars

This is an old question, but Perl needs to be represented:

```
perl -pl '($m,$n,$_)=split;$_+=$m&1&&$n,$m>>=1,$n<<=1while$m'

```

(This is the binary algorithm; iterated addition is smaller but *way* too boring.)

This program includes an unintentional feature: if your input line contains a third number, the program will actually calculate A\*B+C.

# Answer
> 1 votes
# K, 18 16

```
{#,/(!y),\:/:!x}

```

.

```
k){#,/(!y),\:/:!x}[4;20]
80
k){#,/(!y),\:/:!x}[13;21]
273
k){#,/(!y),\:/:!x}[3;6]
18

```

# Answer
> 1 votes
### Ruby, 35 chars

`p $*.map!(&:to_i).pop*$*.inject(:+)`

It's *a program*, which takes input and outputs, not just a function.

```
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> wc -c golf.rb
35 golf.rb
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> ruby ./golf.rb 734 929
681886

```

# Answer
> 0 votes
# VB11, 101 Chars

```
   Dim m As Func(Of Integer, Integer, Integer, Integer) = Function(a, b, t) If(a = 0, t, m(a >> 1, b << 1, t + If(a Mod 2 = 1, b, 0)))

```

# Answer
> 0 votes
# Mathematica 12

The following sums `#2` instances of `#1`.

**Code**

```
#1~Sum~{#2}&

```

**Usage**

```
#1~Sum~{#2} &[734, 929]

(* out *)

```

> 681886

---

**9 chars?**

If program parameters, `a`, `b`, may be used for input, the same result can be achieved with **9 chars**.

```
a~Sum~{b}

```

---
Tags: code-golf, math, restricted-source
---


title: Create an acrostic

text:
# Question
Title: Create an acrostic
Pretty fun and simple challenge here

given any input, create an acrostic poem for that input. you may use any word list of your choosing, and include any code you want to help "smarten" up your acrostic.

```
EXAMPLE

Every
Xylophone
Always
Makes
Powerfully
Low
Emissions

```

the winner will be the code chosen by most up-votes, please up-vote for creativity, problem solving in making the acrostics make sense, and humor.

most important of all, have fun!

(please test your program using the following 3 words, and any other word or 2 you want to add - laughable ; codegolf ; loremipsum)

# Answer
# Python 2.7

```
import random
import string
import sys
import re

class Markov(object):
    def __init__(self,filename):
        with open(filename,'r') as f:
            self._words = f.read().split()
            self._wordCount = len(self._words)

    def getWordList(self,seedWord=None,pattern=r'^.*$'):
        if seedWord is not None:
            chainWords = [self._words[i+1] for i in range(self._wordCount-1)\
                if seedWord == self._words[i].lower()]
        else:
            chainWords = self._words
        p = re.compile(pattern,re.IGNORECASE)
        return filter(p.match,chainWords)

    def getRandWord(self,seedWord=None,pattern=r'^.*$'):
        wordList = self.getWordList(seedWord,pattern)
        if len(wordList) == 0:
            return None
        return random.choice(self.getWordList(seedWord,pattern))

def main():
    list = Markov('AStudyInScarlet.txt')
    for word in sys.argv[1:]:
        poem = []
        for letter in word:
            if len(poem) == 0:
                nextWord = list.getRandWord(pattern=r'^[{0}.*$]'.format(letter))
            else:
                nextWord = list.getRandWord(poem[-1],r'^{0}.*$'.format(letter))
                if nextWord is None:
                    nextWord = list.getRandWord(pattern=r'^{0}.*$'.format(letter))
            nextWord = ''.join(ch for ch in nextWord if ch not in string.punctuation)
            poem.append(nextWord)

        print word
        print '='*len(word)
        for line in poem:
            print line
        print ''

if __name__ == '__main__':
    main()

```

Loads a text file called 'AStudyInScarlet.txt'. Only words used in that document will be candidates for incorporation into the final poem. (currently there are no words starting with `x` in this document, I will add some soon)

This program tries to find words in the text file that follow the previous word in the poem. For example, if the acrostic word is 'pita' and so far the poem is "Private," a possible next word is "inquiry" as the two word phrase "private inquiry" is found in the text document. If no matching word pairs are found, any random word starting with the right letter is chosen.

A word is chosen from a list of words that meet the desired qualifications. If a word shows up multiple times in the list of acceptable words, it is more likely to be chosen than one that does not.

## Usage

Words to create poems from should be specified as command line arguments. One poem will be printed for each word specified on the command line.

### Example:

```
$ acrostic.py laughable codegolf loremipsum
laughable
=========
Looking
a
Union
grievous
his
agitation
be
likely
enough

codegolf
========
couple
of
discoloured
evident
goes
or
late
from

loremipsum
==========
learn
of
revenge
engine
me
it
proved
smartest
up
my

```
> 5 votes

# Answer
## PHP

```
<?php
$dict = array(
    'a' => 'and',
    'i' => 'if',
    'o' => 'or',
    'n' => 'not',
    'l' => 'list'
);
$funcs = get_defined_functions();
$word = rtrim(fgets(STDIN), "\n");
echo "\n";
foreach(str_split($word) as $char)
    foreach($dict + $funcs['internal'] as $func)
        if($func[0] == $char){
            echo $func . "\n";
            break;
        }

```

I admit it does not always make sense, but I am too lazy to look for a real word list, so I used PHP function names plus a couple of PHP reserved words.

Examples:

```
laughable

list
and
user_error
get_class
hash
and
bzopen
list
each

codegolf

class_exists
or
define
each
get_class
or
list
func_num_args

loremipsum

list
or
restore_error_handler
each
method_exists
if
property_exists
strlen
user_error
method_exists

neurotic

not
each
user_error
restore_error_handler
or
trigger_error
if
class_exists

diplomat

define
if
property_exists
list
or
method_exists
and
trigger_error

```
> 5 votes

---
Tags: popularity-contest
---


title: Help Alice in giving candies

text:
# Question
Title: Help Alice in giving candies
Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.

Input

```
The first line of the input is an integer N, the number of children in Alice's class.
Each of the following N lines contains an integer indicates the rating of each child.

```

Ouput

```
Output a single line containing the minimum number of candies Alice must give.

```

Sample Input

```
3
1
2
2

```

Sample Ouput

```
4

```

Explanation

```
The number of candies Alice must give are 1, 2 and 1.

```

Constraints:

```
N and the rating  of each child are no larger than 10^5.

```

**Language Restrictions:**

**C++/Java/C#**

# Answer
## Java

```
import java.io.*;
class Alice {
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(r.readLine());
    int[] ratings = new int[n];
    for (int i = 0; i < n; i++) ratings[i] = Integer.parseInt(r.readLine());
    System.out.println(minCandies(ratings));
  }
  private static int minCandies(int[] ratings) {
    int n = ratings.length;
    int[] reverseRatings = new int[n];
    for (int i = 0; i < n; i++) reverseRatings[n-1-i] = ratings[i];
    int[] forwardRun = findRunLengths(ratings);
    int[] reverseRun = findRunLengths(reverseRatings);
    int sum = 0;
    for (int i = 0; i < n; i++) sum += Math.max(forwardRun[i], reverseRun[n-1-i]);
    return sum;
  }
  private static int[] findRunLengths(int[] ratings) {
    int lastInRun = -1;
    int runLength = 0;
    int[] runs = new int[ratings.length];
    for (int i = 0; i < ratings.length; i++) {
      int r = ratings[i];
      if (r > lastInRun) {
        lastInRun = r;
        runLength++;
      } else {
        runLength = 1;
        lastInRun = r;
      }
      runs[i] = runLength;
    }
    return runs;
  }
}

```

Uses the fact that a kid will need C candies iff there is a strictly increasing run of C ratings in either direction that ends at that kid. Just walks the array in each direction looking for runs and keeps the length of the run found ending at each kid. O(n) time.
> 3 votes

# Answer
# Clojure - 2495

```
(ns alice)

(defn invert-derivative [d]
  (cond (= d <=) >=
        :else <= ))

(defn chunk-by-derivative [ivec]
  (loop [prev-seqs []
         prev-els  [(first ivec)]
         cur-derivative (if (<= (first ivec) (second ivec)) <= >=)
         remainder (rest ivec)]
    (let [cursor (first remainder)
          holds-trend (cur-derivative (last prev-els) (if (nil? cursor) 0 cursor))]
      (cond (empty? remainder)
                (conj prev-seqs prev-els)

            holds-trend
                (recur prev-seqs
                       (conj prev-els cursor)
                       cur-derivative
                       (rest remainder))
            :else
                (recur (conj prev-seqs prev-els)
                       [cursor]
                       (invert-derivative cur-derivative)
                       (rest remainder))))))

(defn candy-delta [ivec]
    (reduce (fn [pr c]
              (let [{:keys [value candies] :as previous
                     :or {:value 0 :candies 1}} (last pr)]
                (conj pr
                      (cond (empty? pr) {:candies 1 :value c}
                            (= value c)    previous
                            (> value c)    {:value c :candies (inc candies)}
                            (< value c)    {:value c :candies (dec candies)}))))
            [] ivec))

(defn simple-min-candy [ivec]
  (let [m (apply min (map #(:candies %1) ivec))]
    (if (> 1 m)
      (map #(assoc %1 :candies (+ (:candies %1) (- 1 m))) ivec)
      ivec)))

(defn subseq-concat [s1 s2]
  (let [s1-l-candies (:candies (last s1))
        s1-l-value   (:value   (last s1))

        s2-f-candies (:candies (first s2))
        s2-f-value   (:value   (first s2))]
    (cond (and (> s1-l-value   s2-f-value)
               (< s1-l-candies s2-f-candies))
              (recur (let [delta (- s2-f-candies s1-l-candies)]
                       (map #(assoc %1 :candies (+ delta (:candies %1))) s1))
                     s2)
          :else (concat s1 s2))))

(defn join-subseqs [subseqs]
  (if (<= 2 (count subseqs))
    (reduce subseq-concat
            (first subseqs)
            (rest subseqs))
    (first subseqs)))

(defn pipeline [v]
  (->> v
      (chunk-by-derivative)
      (map candy-delta)
      (map simple-min-candy)
      (join-subseqs)
      (map #(:candies %1))
      (apply +)
      (println)))

(defn -main [& args]
  (let
    [line-count (read)
     v (map (fn [x] (read)) (range line-count))]
    (pipeline v)))

(-main)

```

### Assumptions

* That the children numbered "2" rank **below** the child ranked "1"
* That two adjacent children of equal number should receive the same number of candies. Easy to change but until the OP clarifies the spec I'm keeping it that way.

### General Algorithm

This solution is based on problem decomposition and composition of functions via the -\>\> operator.

The approach is to "chunk" the ordering of students into sub-orders which are increasing or decreasing. Using the simple approach outlined below which is correct in these cases, a partial candy count can be generated for each of these subsequences which is absolutely minimum for that sequence as argued below. Subsequences can then be joined by comparing the last value of the sequence to concatenate to and the first value of the sequence to be added, and if necessary adding a constant C to all elements of the sequence to be added to in order to ensure that the rank-based order property between children is maintained.

This approach is correct for the multi-delta case as it will consider the ordering \[3 2 1 4 4\] to be the two sequences \[3 2 1\] which is strictly increasing and receive respectively \[1 2 3\] pieces of candy and the sequence \[4 4\] which will receive the candy \[1 1\]. The concatenation of \[1 2 3\] and \[1 1\] respects the order property that child 1 receive more candy than any child 4 so the order is correct.

### Algorithm for individual derivative constant sequences

This algorithm first generates a series of pairs \[d, v\] starting with \[1, (first input value)\] where the first element is the candy count of that child, being +1, +0, -1 from the last child. Note that these are ordered by the input (or seating) order, and thus correctly represent the minimum correct candy change between any pair of consecutive children \[c, c'\].

As the goal is to produce the number of total candies required, the first element of each pair is then taken to create a new sequence of numbers representing the candy count taken in comparison to the candy count of the child who happened to be seated first.

The last step then is to compute the final number of candies with regard to the child seated first. There are three cases here, all of which can be identified by the minimum number of candies given out to any one child.

1. The minimum is less than one. As all children must receive one or more candies all the children must gain K candies where K is `1 - (min chindren)`, thus guaranteeing that the bottom child receives exactly one candy.
2. The minimum is greater than one. An unreachable case, as the worst possible cases in terms of candy consumed are the increasing and decreasing sorts by rank. The decreasing sort would be handled by case 1, and the increasing sort would have a minimum value of 1 and require no further analysis.
3. The case where the minimum is one, so no further processing is required.

### Correctness for all strictly increasing cases

For any strictly increasing ordering of children `(c0 c1 c2 ... cn)` the ith \[counting from 0th\] child will receive `i + 1` pieces of candy. Consequently increasing the count of candy by one in the case of an increase in rank from \[c -\> c'\] is necessarily correct.

### Correctness for all strictly decreasing cases

By a similar argument, for any case where \[c -\> c'\] is always decrease the subtraction of one candy from each child to the next is the minimum possible delta. The first biasing case then kicks in to ensure that the result guarantees one candy per child.

### Correctness for all mixed cases

Any mixed sequence can be expressed as the composite of at least two sequences with different trends (being decreasing or increasing). By breaking such composite sequences into the trend-based subsequences, application of the known correct increasing/decreasing algorithm is trivially correct for all subsequences and a join of all subsequences which guarantees that the rank order property is preserved ensures that all resulting sequences are also minimal.

### Test Cases

```
3
1
2
2

```

=\> `4` being `[2 1 1]`

```
7
1
2
3
4
3
4
5

```

=\> `20` being `[5 4 3 2 3 2 1]`

```
8
1
2
1
2
1
2
1
2

```

=\> `12` being `[2 1 2 1 2 1 2 1]`

### Bugs

If there are any please smack me upside the head for being a cocky jerk. This composition of functions *should* be generally correct but I do not doubt my capacity for overlooking my own errors.
> 1 votes

---
Tags: code-challenge
---


title: Help johnny to solve this Puzzle

text:
# Question
Title: Help johnny to solve this Puzzle
**Scenario**

Little Johnny wants to play with his friends today. But his babysitter won't let him go! After a lot of begging, the heartless nanny gives him her brand new electronic puzzle and says: "If you solve the puzzle then you are free to go". Not being aware of Little Johnny's IT skills, the nanny leaves the kid alone. Rapidly, Little Johnny sends you an e-mail asking for your help. The puzzle consists of three hexagons as shown in the figure. Each vertex is painted black or white. Some of them belong to just one hexagon and some of them belong to more than one. Exactly four of them are painted black, and the other nine are white. The goal is to make the shared vertexes black by means of allowed moves: rotating a hexagon 60 degrees clockwise or counter-clockwise. Can you help Little Johnny?

**Input**

> Input starts with an integer T, the number of puzzles to solve (1\<=T\<=100). T lines follow, each one having 13 binary digits, corresponding to the top-down, left to right labeling of the vertexes in the puzzle. A '0' means the i-th vertex is painted white, while a '1' means it is painted black.

**output**

> For each test case output M on a single line, the minimum number of moves required to solve the puzzle. Then print M lines, each one describing a move in the following manner: two space separated integers H and C, the rotated hexagon (upper left is 0, upper right is 1, lower one is 2) and the direction (0 for counter-clockwise, 1 for clockwise). If there is more than one solution, any will suffice.

Example

**Input sample:**

1 0000000101011

**output sample:**

3

2 0

2 0

1 1

**source Limit**

```
50000 Bytes

```

**time limit**

```
1 sec

```

**Winning constrain**

shortest code with specified time limit wins!

I leave the question for five days to decide winner future answers after five days too welcome

# Answer
> 2 votes
## Python, 307 chars

```
S={'0001001011000':[]}
for i in[0]*7:
 for s in dict(S):
  for m in range(6):S.setdefault(''.join(s[int(x,16)]for x in['2150483769abc','3106428759abc','0326159487abc','0421753986abc','01234587a6c9b','012345976b8ca'][m]),[m]+S[s])
for j in[0]*input():
 L=S[raw_input()];print len(L)
 for m in L:print m/2,m%2

```

Computes `S` which is a mapping from a state (a string just like the input) to a list of move numbers which solve the state. Generates a complete `S` on startup (only 715 states), then looks up each input and prints the answer.

Moves are implemented using a string of hex digits indicating where each result vertex comes from.

Takes about 0.15 seconds regardless of how big the input is.

# Answer
> 0 votes
# Mathematica 831

This was a very demanding challenge that took me several days to work out and streamline, far more than a typical challenge.

This graphs all the nodes, where each node corresponds to one arrangement of 4 black hexagon vertices. Then we find the shortest distance from an input vertex to the solution vertex, `{4, 7, 9, 10}`.

```
c = Complement; h = {{7, 9, 6, 3, 1, 4}, {7, 4, 2, 5, 8, 10}, {7, 10, 12, 13, 11, 9}}; i = {4, 7, 9, 10};l = RotateLeft; n = Module; q = Sort; r = RotateRight; s = Flatten;

p[v_, x_, r_] := Block[{d}, n[{d = v \[Intersection] x},If[d != {}, {v, (r[x][[Position[x, #][[1, 1]]]] & /@ d) \[Union] c[v, d], {x /. {h[[1]] -> 0, h[[2]] -> 1, h[[3]] -> 2}, r /. {r -> 0, l -> 1}}}, {}]] /. {{a_, b_, c_} :>   {q@a \[DirectedEdge] q@b, q@a \[DirectedEdge] q@b -> c}}]

o[e_, t_] := Cases[s[Outer[p, {#}, h, {l, r}, 1]~s~2 & /@ e, 1], {a_ \[DirectedEdge] w_, b_} /; \[Not] MemberQ[t, w] :> {a \[DirectedEdge] w, b} ]

m[{g_, j_, _, b_}] :=n[{e, k, u, z},{e, k} = Transpose[o[c @@ g, g[[2]]]];z = Graph[u = Union@Join[e, j], EdgeLabels -> k];{Prepend[g, c[VertexList[z], s[g, 1]]], u, z, Union@Join[k, b]}]

t[j_] :=n[{r, v, y, i = {4, 7, 9, 10}},z = Nest[m, {{{i}, {}}, {}, 1, {}}, 7];v = FindShortestPath[z[[3]], i, Flatten@Position[Characters@j, "1"]];y = Cases[z[[4]], Rule[DirectedEdge[a_, b_], k_] /; MemberQ[v, a] && MemberQ[v, b]];r = Reverse[y[[Cases[Flatten[Position[y, #] & /@ v, 1], {a_, _, 1} :> a]]]] /. (_ \[DirectedEdge] _ -> k_) :>  k ;Grid@Join[{{Length[r]}}, r]]

```

**Usage**

```
t["0100000100011"]

```

>

---

**Timing**

The search space loads at the when the code is read for the first time. A solution takes approximately .32 seconds, regardless of the distance from the solution node.

Note: \[Intersection\], \[Union\], and \[DirectedEdge\] are single, dedicated characters in Mathematica.

---
Tags: code-golf, puzzle-solver
---


title: How can I make this program smaller?

text:
# Question
Title: How can I make this program smaller?
I am trying my hand at writing super small programs. I wrote a simple "tree" display program for showing a graphical representation of a folder hierarchy. I have made it small in all the ways I can think of. I was just wondering if you guys had more creative ways to "minify" it further. Here is the small version as well as a human-readable version.

```
import os,os.path as p
def w(c,d,s):
    a=os.listdir(c);s=s+'|';i=0
    for f in a:
        print s+'--'+f;j=p.join(c,f);
        if p.isdir(j):w(j,d+1,s[:-i==len(a)-1]+'  '*(d+1));i=i+1
def t(c):print c;w(c,0,'')
t(p.curdir)

```

That's a total of 236 bytes

```
import os

def treeWrap(curdir,depth,pipeStr):
    files = os.listdir(curdir)
    pipeStr = pipeStr + '|'
    for f in files:
        print pipeStr + '--' + f
        if os.path.isdir(os.path.join(curdir,f)):
            dir = os.path.join(curdir,f)
            if files.index(f) == (len(files)-1):
                treeWrap(dir,depth+1,pipeStr[:-1] + '  '*(depth+1))
            else:
                treeWrap(dir,depth+1,pipeStr + '  '*(depth+1))

def tree(curdir):
    print curdir
    treeWrap(curdir,0,'')

tree(os.path.curdir)

```

Oh, in addition, does anyone know how I can use the unicode ├,└,─ in this program? Whenever I use them they appear as garbage in the console and the idle interpreter.

# Answer
> 1 votes
There is a bug with your minified version: `s[:-0]` gives you the empty string, not the complete string as you anticipate with `s[:-i==len(a)-1]`. To rectify this, you will need to either ignore preceding bars or calculate the a little more thoroughly. The shorter version would be to ignore preceding bars and not worry about passing spacing to further recursions. Since it permits the removal of several variables, I worked your code to do this

Your `tree` function is only called once, I removed it.

`s=s+'|'` and `i=i+1` can be collapsed into `s+='|'` and `i+=1`

`os.path as p` can become `p=os.path` (Thanks James)

`p.join(c,f)` can become `c+'/'+f` (Thanks beary605)

New version:

```
import os,p=os.path
def w(c,d):
    for f in os.listdir(c):
        print '  '*(d+1)+'|--'+f;j=c+'/'+f
        if p.isdir(j): w(j,d+1)
z=p.curdir;print z;w(p.curdir,0)

```

If you really wanted to go crazy, you can make put this all on one line and get it down to 143 bytes (on linux)

```
import os,p=os.path
def w(c,d):
 for f in os.listdir(c):print'  '*(d+1)+'|--'+f;j=c+'/'+f;w(j,d+1)if p.isdir(j)else 0
z=p.curdir;print z;w(z,0)

```

---
Tags: tips, python, optimization, tree-traversal
---


title: Lightbox Generator

text:
# Question
Title: Lightbox Generator
Warning: this is a complex challenge.

## Overview

A lightbox, in the context of computing, is a visual effect used in image sites. A list of thumbnail images is displayed; each image can be selected and will be displayed on top of the contents of the page either at full size or to fill the screen.

The task is to generate a (fairly) self-contained web page which will display specified images in a lightbox.

## Input

The input will be from stdin and will specify (one item per line):

* The number of images (`n`)
* A pattern for transforming an image name into its thumbnail (substitution described in detail further down)
* A list of `n` images, each consisting of a URL for the full-sized image and a one-line description. You may assume that each URL ends with an extension (e.g. `.jpg`), although you cannot assume any extension in particular.

Sample input:

```
4
*_thumb.jpg
DSCF0001.jpg
My family
DSCF0002.jpg
Other animals
crop/DSCF0017.jpg
Aren't they cute?
http://www.example.com/fx.jpg
The bestest picture on the whole Internet!!!

```

Note: when the URLs are relative (the first three in this example), you may assume that they are relative to the current working directory. This is probably only relevant if you want to load them in your program to find their sizes.

Substitution into the thumbnail pattern works by removing the file extension from the base URL and replacing the `*` in the pattern. So for the four images in the example above, you would get

```
DSCF0001_thumb.jpg
DSCF0002_thumb.jpg
crop/DSCF0017_thumb.jpg
http://www.example.com/fx_thumb.jpg

```

If the pattern were `thumbs/*.jpg` you would get

```
thumbs/DSCF0001.jpg
thumbs/DSCF0002.jpg
thumbs/crop/DSCF0017.jpg
thumbs/http://www.example.com/fx.jpg

```

The fact that the last one there is clearly nonsense would be a bug in the input rather than in your program.

## Output

The output must include some HTML, and may additionally include some other files (e.g. separate JavaScript, CSS, or images). You may emit the main HTML to stdout or to a file named `index.html`. Please state which you choose to do.

The HTML must include a doctype and be valid for that doctype (I suggest using HTML5!). When it loads, it must display the thumbnails, which must have some separation (margin or padding) between them, and should not be one per line. Each thumbnail must either have a `title` attribute or be in an element with a `title` attribute which displays the corresponding image description. It must also have an `alt` attribute which is the same description.

Clicking on a thumbnail must open the lightbox. This consists of a translucent black overlay covering the entire screen, on top of which the following are displayed in a white rectangle with a padding of at least `8px`:

* The full image (scaled as required - see below)
* The image description
* Buttons or links to go forward and back, and to close the lightbox

It is up to you whether you overlay the description and buttons over the image or put them in the margin around it.

If everything fits within the browser's viewport with the image at full size, it should be displayed at full size. Otherwise it should be scaled down, preserving aspect ratio, so that everything fits.

The forward and back (or next and previous - your choice) buttons must load the corresponding images. It is your choice as to whether they loop or stop at the ends. There should be a simple but smooth transition between the images - if the (scaled) images are different sizes, then it shouldn't jump, and you should use some kind of fade or sweep.

The following features of many lightboxes are not required:

* Closing if the user clicks on the translucent black overlay
* Resizing everything correctly if the browser window is resized

## Permitted external resources

Use of external resources is restricted to using at most one of the following JavaScript libraries:

* jQuery
* Prototype
* mootools

You may assume that it is in the same directory as the output html, but if you do so you should document the name which you expect it to have and the version which you require.

## Compatibility

Compatibility with IE is nice, but this is a code golf, and apart from that it's not something which is easily tested without a Windows machine, so it is not a requirement. Please state which browser(s) you have tested with in your answer. I will test with Chromium, and I also have Firefox 3.6 and Konqueror available at home (plus various versions of IE, Win Safari and Opera in my lunchtimes at work, so if you want me to test on one of those, say so).

---

Note: this question has been sitting in the Sandbox for two weeks, so if you think there's a problem with the specification, please make it a habit to comment on questions over there.

# Answer
> 4 votes
## PHP, HTML, CSS and jQuery, 1551 1482 1511 characters

```
<?while($x=fgets(STDIN))$i[]=chop($x)?><!doctype html><title></title><style>.t{float:left;margin:10px;height:50px}#o,#p,p,b,i,q{position:fixed;top:0}#o{background:rgba(0,0,0,0.8);width:100%;height:100%;display:none;left:0}#p{display:none;z-index:1;border:10px solid #fff;top:50%;left:50%}p{padding:5px;background:rgba(50,50,50,0.7);color:#ccc;z-index:2;top:50%;left:50%}b,i,q{padding:10px;color:#f00;background:#ccc;z-index:2}b{right:0;font-weight:900}i{top:50%;left:0}q{top:50%;right:0}</style><script src=a></script><script>$(function(){$('img').click(function(){a=$(this);$('body').append('<b>X</b><i><</i><q>></q><div id=o>');z($(this).attr('data-l'),$(this).attr('alt'))});$('body').on('click','b',function(){$('b,i,q,p,#o,#p').fadeOut(function(){$(this).remove();})}).on('click','q,i',function(){f=$(this).is('q')?a.next('img'):a.prev();$('#p,p').fadeOut(function(){$(this).remove();a=f.size()==0?a:f;z(a.attr('data-l'),a.attr('alt'))})})});function z(l,m){if($('#p').size()<1){$('body').append('<img id=p src='+l+'><p>'+m);i=new Image();i.onload=function(){w=i.width;h=i.height;$('#p').css({maxWidth:$('body').innerWidth()-20,maxHeight:$('body').innerHeight()-20,marginLeft:0-w/2,marginTop:0-h/2});$('p').css({marginLeft:0-$('p').width()/2,marginTop:w/2-30});$('#o,#p').fadeIn()};i.src=l}}</script><?for(;$l<$i[0]*2;$l+=2){$a=str_replace('"','"',$i[2+$l]);$b=$i[3+$l];echo'<img class=t src='.str_replace("*",substr($a,0,strrpos($a,".")),$i[1]).' title="'.$b.'" alt="'.$b.'" data-l='.$a.'>';}?>

```

I've assumed that the jQuery library is available in the same directory as this file, and that it is named `a`. The HTML takes advantage of the fact that a lot of the tags are optional but at it's base it is only:

```
<!doctype html>
<title></title>
<img alt=title src=http://placehold.it/60 data-l=http://placehold.it/180>
...more images here...

```

which is considered valid by the w3c validator.

The CSS still contains some repeated styles which probably offers some room for further compression.

I've created a jsFiddle which demonstrates the lightbox functionality for those who wish to try it. One time when I ran it there was a glitch with the images when they were first loaded - please let me know if it's a regular thing so I can have a look into it.

I've only tested it in Chrome on Mac OSX (using the above jsFiddle), and on Chrome on Windows XP using the php to generate the page (`php -q lb.php > lb.html`) with the following input:

```
4
http://lorempixel.com/60/60
http://lorempixel.com/250/250
My family
http://lorempixel.com/300/300
Other animals
http://lorempixel.com/350/350
Aren't they cute?
http://lorempixel.com/400/400
The bestest picture on the whole internet!!!

```

which generates the following page source:

```
<!doctype html><title></title><style>.t{float:left;margin:10px;height:50px}#o,#p,p,b,i,q{position:fixed;top:0}#o{background:rgba(0,0,0,0.8);width:100%;height:100%;display:none;left:0}#p{display:none;z-index:1;border:10px solid #fff;top:50%;left:50%}p{padding:5px;background:rgba(50,50,50,0.7);color:#ccc;z-index:2;top:50%;left:50%}b,i,q{padding:10px;color:#f00;background:#ccc;z-index:2}b{right:0;font-weight:900}i{top:50%;left:0}q{top:50%;right:0}</style><script src=http://ajax.googleapis.com/ajax/libs/jquery/1.8.1/jquery.min.js></script><script>$(function(){$('img').click(function(){a=$(this);$('body').append('<b>X</b><i><</i><q>></q><div id=o>');z($(this).attr('data-l'),$(this).attr('alt'))});$('body').on('click','b',function(){$('b,i,q,p,#o,#p').fadeOut(function(){$(this).remove();})}).on('click','q,i',function(){f=$(this).is('q')?a.next('img'):a.prev();$('#p,p').fadeOut(function(){$(this).remove();a=f.size()==0?a:f;z(a.attr('data-l'),a.attr('alt'))})})});function z(l,m){if($('#p').size()<1){$('body').append('<img id=p src='+l+'><p>'+m);i=new Image();i.onload=function(){w=i.width;h=i.height;$('#p').css({maxWidth:$('body').innerWidth()-20,maxHeight:$('body').innerHeight()-20,marginLeft:0-w/2,marginTop:0-h/2});$('p').css({marginLeft:0-$('p').width()/2,marginTop:w/2-30});$('#o,#p').fadeIn()};i.src=l}}</script><img class=t src=http://lorempixel.com/60/60 title="My family" alt="My family" data-l=http://lorempixel.com/250/250><img class=t src=http://lorempixel.com/60/60 title="Other animals" alt="Other animals" data-l=http://lorempixel.com/300/300><img class=t src=http://lorempixel.com/60/60 title="Aren't they cute?" alt="Aren't they cute?" data-l=http://lorempixel.com/350/350><img class=t src=http://lorempixel.com/60/60 title="The bestest picture on the whole internet!!!" alt="The bestest picture on the whole internet!!!" data-l=http://lorempixel.com/400/400>

```

I've fixed a few issues that weren't apparent in the jsFiddle testing - the only real issue I'm aware of now is that in Chrome the `>` button gets quotes put around it because I'm using the `q` tag. Not sure if the default styles in Firefox, Opera and IE do the same.

I think I've met all the requirements - again let me know if I've missed anything.

**Edit:**

I've removed all the `ul` and `li` stuff because it wasn't necessary, saving about 70 characters.

Here's the code (of the previous version with `ul` and `li`s) with some line-breaks and indentation to aid readability, and a Google CDN jQuery link:

```
<?while($x=fgets(STDIN))$i[]=chop($x)?>
<!doctype html>
<title></title>
<style>
ul{list-style-type:none}
li{float:left;margin:10px;padding:0}
li img{height:50px}
#o,#p,p,b,i,q{position:fixed;top:0}
#o{background:rgba(0,0,0,0.8);width:100%;height:100%;display:none;left:0}
#p{display:none;z-index:1;border:10px solid #fff;top:50%;left:50%}
p{padding:5px;background:rgba(50,50,50,0.7);color:#ccc;z-index:2;top:50%;left:50%}
b,i,q{padding:10px;color:#f00;background:#ccc;z-index:2}
b{right:0;font-weight:900}
i{top:50%;left:0}
q{top:50%;right:0}
</style>
<script src=http://ajax.googleapis.com/ajax/libs/jquery/1.8.1/jquery.min.js></script>
<script>
$(function()
{
    $('img').click(function()
    {
        a=$(this).parent();
        $('body').append('<b>X</b><i><</i><q>></q><div id=o>');
        z($(this).attr('data-l'),$(this).attr('alt'))
    });
    $('body').on('click','b',function()
    {
        $('b,i,q,p,#o,#p').fadeOut(function(){$(this).remove();})
    }).on('click','q,i',function()
    {
        f=$(this).is('q')?a.next():a.prev();
        $('#p,p').fadeOut(function()
        {
            $(this).remove();
            a=f.size()==0?a:f;
            b=a.find('img');
            z(b.attr('data-l'),b.attr('alt'))
        })
    })
})
function z(l,m)
{
    if($('#p').size()<1)
    {
        $('body').append('<img id=p src='+l+'><p>'+m);
        i=new Image();
        i.onload=function()
        {
            w=i.width;
            h=i.height;
            $('#p').css({maxWidth:$('body').innerWidth()-20,maxHeight:$('body').innerHeight()-20,marginLeft:0-w/2,marginTop:0-h/2});
            $('p').css({marginLeft:0-$('p').width()/2,marginTop:w/2-30});
            $('#o,#p').fadeIn();
        }
        i.src=l;
    }
}
</script>
<ul>
<?for(;$l<$i[0]*2;$l+=2)
{
    $a=$i[2+$l];
    $b=$i[3+$l];
    echo"<li><img src=".str_replace("*",substr($a,0,strrpos($a,".")),$i[1])." title='".$b."' alt='".$b."' data-l=".$a.">";
}?>
</ul>

```

---
Tags: code-golf
---


# Question
Title: A doubly linked list that only stores 1 pointer per element
A favorite puzzle of mine. Not massively difficult but a tad interesting.

**The Objective**

Using a low level language (C/C++/similar level) - create a doubly linked list of elements that only stores a single pointer instead of storing both a previous and next element pointer as you normally would.

You must be able to find each element in your linked list, starting from either the first element you created, or the most recently created element.

You must use `malloc(sizeof(*node))` or similar to store each element (the addresses are likely to be non-sequential as a result)

**The Restrictions**

* The data type you use to store your value must be the length of a function pointer (No using long values to store 2 pointer addresses one after another)
* You may not use any external libraries (only the standard libc methods are permitted if you're using C/C++, apply the spirit of this rule to other languages)
* You may not store any additional metadata elsewhere (or in the list elements themselves) to solve this. The list element may only contain two fields - the 'data' value and the value you will use to find the previous and next elements. It may look something like:

`struct node
 {
 int myValue;
 struct node* prevAndNextNode;
 }`

**Golf or Challenge?**

You can either find the most elegant/interesting solution, or the shortest. Take your pick!

Have fun ;)

# Answer
This is an xor linked list:

```
struct node {
  int myValue;
  uintptr_t xor_prev_and_next;
  node *next(node *prev) {
    return (node*)((uintptr_t)prev ^ xor_prev_and_next);
  }
  node *prev(node *next) {
    return (node*)((uintptr_t)next ^ xor_prev_and_next);
  }
}

struct list {
  node *first;
  node *last;
  int sum_forwards() {
    int sum = 0;
    node *prev = NULL;
    node *curr = first;
    while (curr) {
      sum += curr->myValue;
      prev, curr = curr, curr->next(prev);
    }
    return sum;
  }
}

```
> 4 votes

# Answer
# EDIT

### Problem Definition

* For a given node, find the next node (null if tail)
* For a given node, find the previous node (null if head)
* Return a node at a specified offset from the start of the list (null if out of bounds)
* Return a node at a specified offset from the end of the list (null if out of bounds)

The constraints have been revised by the OP, and include restricting the nodes as well as external structures from storing any metadata. My initial implementation of a Circular Linked List did not meet this criteria since it required knowing the head node with a flag value.

I present now a clever workaround:

# A Circular Linked List with Forced Node Address Parity

Note that lately I am a C# programmer, but I will try to do this C-style as possible.

### The List Node Structure

Nothing fancy here:

```
struct ListNode
{
    ListNode *next;
    int value;
};

```

### Adding Nodes with Even Addresses Only

Since this implementation still requires that we be able to find the start of the list, we can use the LSB of the `next` pointer as a flag. If the last bit of the `next` pointer is 1, it means we are at the end of the list. A few helper functions:

```
bool isPtrOdd(void * addr)
{
    if((unsigned int) addr & 1)
        return 1;
    return 0;
}

ListNode * GetNodeAddr(ListNode * node)
{
    if(isPtrOdd(node))
        return node - 1;
    return node;
}

```

The only special considerations are that we must ensure that nodes are allocated only on even addresses. There are several ways of doing this, but I will show a basic one which allocates an extra byte for each node:

```
ListNode * NewNode()
{
    void * memBlock = malloc(4 + 4 + 1); // 32 bit address, 32 bit value, 1 padding byte

    if(isPtrOdd(memBlock)) // if the block started on an odd address
        memBlock++;                 // shift over to an even address

    ListNode * newNode = memBlock;

    newNode->value = 0;
    newNode->next = newNode + 1; // a new node circularly points to itself

    return newNode;
}

void AddNode(ListNode * list, ListNode * newNode)
{
    while(!isPtrOdd(list->next))
        list = list->next;         // Get to the end of the list

    newNode->next = list->next;    // Point the new node to the list head + 1
    list->next = newNode;
}

```

### Traversing the List

And using C-style external functions (no classes) we define each of the desired functions:

```
ListNode * NextNode(ListNode &Node)
{
    if(isPtrOdd(Node->next))
        return 0;
    return &(Node->next);
}

ListNode * PrevNode(ListNode &Node)
{
    ListNode curNode = Node;
    while(&(GetNodeAddr(curNode->next)) != &Node) // We compare addresses instead of values
        curNode = GetNodeAddr(curNode->next);     // since the == operator is not defined for structs

    if(isPtrOdd(curNode->next)) // if the 'previous node' is actually the end of list
        return 0;

    return &curNode;
}

ListNode * NodeFromStart(ListNode &Node, int offset)
{
    // This function returns offset from head node given
    // any node in the list

    ListNode Head = Node;
    while(!isPtrOdd(Head->next))       // Loop completes when tail is found
        Head = GetNodeAddr(Head->next);
    Head = GetNodeAddr(Head->next);    // Move once more and get to head

    for(int n=0; n<offset; n++)
    {
        if(isPtrOdd(Head->next))       // if we reach the end of the list
            return 0;
        Head = Head->next;
    }

    return &Head;
}

ListNode * NodeFromEnd(ListNode &Node, int offset)
{
    // This function returns offset from tail node given
    // any node in the list

    ListNode Head = Node;
    while(!isPtrOdd(Head->next))       // Loop completes when tail is found
        Head = GetNodeAddr(Head->next);
    Head = GetNodeAddr(Head->next);    // Move once more and get to head

    // Determine number of nodes in List
    int count = 1;
    while(!isPtrOdd(Head->next))
    {
        Head = GetNodeAddr(Head->next);
        count++;
    }

    if(count<=offset)
        return 0;

    return NodeFromStart(Head,count - offset);
}

```
> 3 votes

---
Tags: code-golf, code-challenge
---


# Question
Title: List ALL prime-factorized natural numbers in ANY order
*This is a variant of List prime-factorized natural numbers up to N in ascending order, but the solutions can be very different.*

Write a program that outputs prime factorizations of all natural numbers in any order. For example, the output could look like:

```
1:
4: 2^2
8: 2^3
2: 2^1
3: 3^1
5: 5^1
6: 2^1 3^1
21: 3^1 7^1
9: 3^2
...

```

**Requirements:**

1. *You cannot just iterate over the numbers and factor each of them.* This is too inefficient.
2. The output should be as in the example above: On each line the number and the list of its prime factors.
3. There is no given order in which the number appear in the list. However:
4. Each number must appear *exactly once* in the list (explain that your code satisfies this condition).

**Edit - remark:** Of course the program never finishes. But since (4) requires each number to appear in the list, for any `n` there is time `t` such that the list produced by the program within time `t` contains the factorization of `n`. (We don't care if `t` is comparable to the age of our universe or anything else.)

**Note:** This is *not* code-golf, it's code-challenge. This puzzle is about clever ideas, not code size. So please don't give the shortest solutions, give commented solutions that are easy to read and where the idea is easily understandable.

# Answer
> 2 votes
# Haskell

```
import Data.List

merge :: [[a]] -> [[a]] -> [[a]]
merge [] ys = ys
merge (x:xs) ys = x : merge ys xs

atmostonefromeach :: [[a]]-> [[a]]
atmostonefromeach = foldr weave undefined

weave :: [a] -> [[a]] -> [[a]]
weave pwrs odds = merge (map (:[]) pwrs) $
foldr (\odd -> merge (odd: (map (:odd) (pwrs)))) undefined odds

primes = nubBy (\x y->gcd x y > 1) [2..]

shw factors = show (product (map (\(p,k)->p^k) factors)) ++ ":" ++ concatMap(\(p,k) -> ' ': show p ++ '^': show k) factors

powers p = map (\x->(p,x)) [1..]

main = mapM_ (putStrLn . shw) $ ([]:) $ atmostonefromeach $ map powers primes

```

output:

```
1:
2: 2^1
3: 3^1
4: 2^2
5: 5^1
8: 2^3
6: 2^1 3^1

...

```

The program constructs, from the list Q=\[q0,q1,..\] of composite numbers with all prime factors \> p, the list of those with primes factors \>= p, as merge(P, merge((map(q0\*)P1), merge(map(q1\*)P1),... where P=\[p^1,p^2,...\] and P1=\[p^0,p^1,..\].

The name odds in function weave describes the case p==2, where Q is the set of all odd numbers \> 1.

# Answer
> 2 votes
Generates the list by iterating over N. Each iteration generates all numbers which are the product of up-to-Nth powers of the first N primes. Starts with N=1 and keeps growing N. To avoid duplicates, each iteration makes sure not to generate anything generated in previous iterations. Those are exactly the numbers that don't include the Nth prime and which don't have at least one exponent equal to N.

```
import itertools

print '1 ='

n = 0
primes = []
while 1:
  n += 1

  # generate next prime
  q = primes[-1] if primes else 1
  while 1:
    q += 1
    if all(q % p != 0 for p in primes):
      primes.append(q)
      break

  # generate all exponents of at most n of first n primes
  for e in itertools.product(*(xrange(n+1) for i in xrange(n))):
    if max(e) == n or e[-1] > 0:  # we didn't do this in iteration n-1
      print reduce(lambda x, y: x * y, (primes[i]**e[i] for i in xrange(n))), '=', ' '.join('%d^%d' % (primes[i], e[i]) for i in xrange(n))

```

---
Tags: code-challenge, fastest-code, primes, number-theory
---


title: Implement half away from 0 rounding

text:
# Question
Title: Implement half away from 0 rounding
## Overview:

Using you language of choice, implement a complete "half away from 0" rounding function in the shortest amount of code possible.

## Rules/Constraints:

* Direct, predefined `Round`-like functions are not allowed.
* `Floor`/`Ceiling`-type functions *are* allowed, if your language supports these.
* Function shall be able to handle 32-bit floating-point values.
* Function shall be able to correctly handle negative values (see examples).
* This is Golf, so shortest code wins.
* Correct rounding for this challenge is to round away from 0, such that a rounded value will have an equal or larger absolute value.

## Input/Output:

* Your function shall take two parameters:
    + The first is a float `x`, which is the value to round.
    + The second is an integer `n`, which is the number of decimal places to round to.
    + `x` can be a whole number or contain a decimal part, fitting within a 32-bit, single-precision float.
    + `n` can be greater than or equal to 0, and may be larger than the number of decimal places in `x`.
* Output will be the correctly rounded `x`.
* **In cases where the solution is not exactly representable in IEEE float format, the output should be the logical representation you would have figured if not using a computer. i.e. The output of `Round(0.125, 2)` should be `0.13`*.

## Example I/O:

```
Round(1.23456789, 7)
1.2345679

Round(1.234, 5)
1.234 OR 1.23400 (Your choice on trailing 0)

Round(-0.5, 0)
-1 NOT 0

Round(-0.123, 2)
-0.12 NOT -0.13

Round(3.1415926535897932384626433832, 20)
3.14159265358979323846

```

## Winning:

\***Some system limitations may be present which make your function less accurate/usable.* In these cases, supply the best possible calculation you can within those limitations.

For example, I have a solution in my preferred environment, VBA in Office 2003, which only allows me to round up to 307 digits, while the IDE will only let me use values up to 15 significant decimal places. (I will eventually post this example here.)

With your answer submission, please post the highest values of `n` and the largest number of significant decimal digits for `x` for which your function will run. If you cannot meet the minimum requirements, that solution is disqualified, no matter the code length. (i.e. my own solution described above is invalid)

While this is code golf, and the shortest code will generally win. If two answers exist with different maximum values for `x` and `n`, the solution which works with the highest input values (measured as `x * n`) will win. If these two solutions meet the same limitation while fulfilling the requirements of the challenge, then the shortest code of those two will win.

If no solutions meet the requirement, then the best limitation score (shortest code length in the event of a tie) will win.

Example submission given the rules above for my own code:

```
<CODE HERE>
Max n = 307
Max x digits = 15
Limitation Score (x * n) = 4605

```

# Answer
## Q (29 Characters)

```
{("i"$x*10 xexp y)%10 xexp y}

```

Sample usage

```
{("i"$x*10 xexp y)%10 xexp y}[1.23456;4]

```

Works by multiplying your x input by 10 to the power of your y input, casting to an int and then dividing again by 10 to the power of your y input.
> 2 votes

# Answer
Python (153 chars, max(x)=infinite, max(n)=13)

You can input a float, however it works much, much better (max(n)=infinite instead of 13) if you input a string.

```
def Round(x,n):
    x=map(str,str(x))
    if n==0:x.remove('.')
    n+=1+(n!=0)+(x[0]=='-')
    if n<len(x):x[n-1]=str(int(x[n-1])+(x[n]>='5'))
    return''.join(x[:n])

```

Explanation:

`x=map(str,str(x))`
Seperate each character of `x`. (e.x. when x=5.4, running this makes x equal to `['5', '.', '4']`.

`if n==0:x.remove('.')`
A hack to get around Test Case 3, `Round(-0.5, 0)`. Removes the decimal so we don't get the output `-1.`

`n+=1+(n!=0)+(x[0]=='-')`
`if n<len(x):x[n-1]=str(int(x[n-1])+(x[n]>='5'))`

`1` compensates for the decimal point. I think. `(n!=0)`: Compensates for the removal of the decimal point and allows the next line to run.
`(x[0]=='-')`: Makes it so that in the next line, the negative sign (an additional character) will not mess up the calculation.

`if n<len(x)`: Accounts for Test Case 2, `Round(1.234, 5)`, because Python errors when you try to access the `n`th item of a list if it's not there. (`x[5]` is called in the test case, and `x` does not have a 6th term.)
`x[n-1]=str(int(x[n-1])+(x[n]>='5'))`: Gets the `n-1`th item of `x` (which is a string, so it needs to be turned into a number), and adds 1 to it if the `n`th item of `x` is greater than or equal to 5. Then it gets turned back into a string.

`return''.join(x[:n])`: Returns the concatenation of everything up to the `n`th item in `x`.
> 1 votes

# Answer
## Python, 55 46 chars

```
R=lambda x,n:int(10**n*x+(.5,-.5)[x<0])/10.**n

```

Translates the decimal point, rounds half up using `int(x+.5)`, then translates the decimal point back. Negative numbers use `int(x-.5)`.

Should be as accurate as a 64-bit IEEE can get (15+ decimal digits). `n` can be up to about 300 or so (less if `x` is big).
> 1 votes

# Answer
# **C, 51 Characters**

```
float round(float x, int n)
{
    return(long)(x*pow(10,n)+(x>0?0.5:-0.5))/pow(10,n);
}

```

Not including the function headers, it's 51 characters.
> 1 votes

---
Tags: code-challenge, arithmetic
---


title: Write a CFG acceptor

text:
# Question
Title: Write a CFG acceptor
Write a program that, given a context free grammar and a string, returns whether the string is a word of the language defined by the grammar.

## Input

Your program should read a context free grammar and an input string in an implementation defined way during runtime. Hardcoding the input is acceptable as long as it is trivial to change the input.

The context free grammar is a set of rules as defined by the regex `[A-Z][a-zA-Z]*`, that is: One capital letter denoting the nonterminal to be replaced and an arbitrary number of terminals (minuscules) and nonterminals (capitals) to replace it. The grammar may contain up to 256 rules. The initial symbol is always `S`. You may not assume that the grammar is unambigous. The grammar must contain at least one production rule for `S`.

The input string must match the regex `[a-z]*`. It has a length of no more than 65536 characters.

## Output

Output is to be done in an implementation defined manner. Your program must output whether the input string is a word of the language defined by the grammar.

## Constraints

* Your program must terminate in reasonable time
* You may not use any libraries that provide parsers or parser generators
* You may not run any program that generates a parser
* You may not use compression utilities or libraries

## Scoring

This is code-golf. The submission with the smallest number of bytes wins

## Example

The rules

```
S
SaSb

```

represent a grammar which defines the language anbn for n≥0. So given string `aaabbb` it would indicate that it accepts it, but given string `aaabb` it would indicate that it does not accept it.

The ruleset

```
S
SaSbS
ScSdS

```

describes the Dyck language. It describes the language of all balanced pairs of ab's. and cd's. For instance, string *ababacabdb* matches but *cabdacb* doesn't.

# Answer
> 6 votes
## Python 2.7, 325 chars

```
R=['S','SaSb']
I='aaabbb'

L=len(I)
def P(x,y,n):
 if n<3:return[[x,y]][:n>1or x==y]
 return[[x]+w for z in range(x,y+1)for w in P(z,y,n-1)]
S={(i,i+1,c):1for i,c in enumerate(I)}
T=0
while S!=T:
 T=dict(S)
 for r in R:
  for a,x,y,b in P(0,L,4):
   if any(all(t in S for t in zip(p,p[1:],r[1:]))for p in P(x,y,len(r))):S[x,y,r[0]]=1
print(0,L,'S')in S

```

The rules are listed in `R` and the input is in `I`.

The code uses dynamic programming, similar to the Earley algorithm. `S` contains tuples `(i,j,N)` if the symbol `N` can generate the input from indexes `i` to `j`. We iterate through all rules and indexes looking for new entries we can put in `S`.

`P` is a helper function that calculates all possible partitions of the range `[x,y]` into `n-1` ranges (assigning one symbol in the rule to each). For instance, `P(0,7,4)` contains, among many others, `[0,3,6,7]`.

The run time is exponential in the longest rule, but shouldn't be too bad in the number of rules and length of the input.

---
Tags: code-golf, grammars
---


title: Unicode character classification

text:
# Question
Title: Unicode character classification
Real-world programs often use libraries like ICU to support Unicode.

The puzzle is to create the smallest possible function that can determine whether a given Unicode character is lowercase, uppercase, or neither (a commonly used Unicode character property).

You may indicate the property in any way (whatever is shortest for your language); just explain what the output means in your answer.

Of course, using a language feature or a function from the standard library that already provides this distinction is forbidden.

This could potentially have some practical use, since some embedded programs have to choose between including a bulky library and not supporting Unicode.

# Answer
# C & C++, 1922 1216 bytes/chars (BMP only 1451 1005 bytes/chars)

This is the "shortest" solution that came to mind that is both valid C and C++ and that supports all of Unicode version 6.1, not just the BMP:

```
int s[]={-74,-68,31054,-50,-49,-48,-47,-46,-44,-43,-39,-38,-37,-34,-33,-32,-30,-29,-28,-27,-26,-25,-24,-23,-22,-17,-16,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,19,20,27,28,29,53195,31,34,36,42,49,50,52,54,58,59,62,64,66,73,81,98,102,103,140,194,263,275,290,1066,1222,1230,2685,2732,2890,3379,6009,21254,22391,30996,53209};
char l[]="l5Hf`7HIAH2IH@IH7IJFIFHJIJKHLJKFHFJFIJIHIJKIJHJFHNFJ@IH?IHJIK1IBHFJHILDI!HI4HpIFKFHWZ-HIHKFH<IDHIFJHc&H9IQ4IJBIH(Ie+H{)Hh<HI.Hn I@H$I@HPCHRAHPAHPCHRAHPAHP;HJAHPAHPAHPDHIHNKFHIHPEHJHPAHRFHIHrKHKZFLJHPEHLdx'HJKHEILIHICHM$IHOILT,HIM~8IX=IoBIFH/IAHFIJDILIJIUDIk|BHTDHt5Hv*H\\5HYBHI9HY5HYEHFIBHI>HY5HY5HY5HY5HY5HY5HY5HY5HY3H[6HICHY6HICHY6HICHY6HICHY6HICHIG";
char u[]="i5Hm8HIBH^3IJAIJ7IHFIKHFIHIFHJEHIHIFHKHIHEIHIJIHIFHFIHKOEJAIJ@IFJIFH1IOHIHJIEHDIsIKVIFHFIHI:HI@H_JFHK=IMJIHJ#Ha:IQ3IHBIJ)IR,Hy,HIMz IQ%IQAHPCHRAHPAHPCHSEIPAHjEHTEHTEHTDHSEHqLKFHJFHJKDHNEIEHJEHRHMgw'HbIFHJEIEHIJPFH$IPIL\"8IX=IoBIK0IRFIHDILIJIUCI}5Hu*H\1775HY5HY5HYIHFJHJEHIAHY5HYHIEHJAHIBHZHIEHIDHIKBHZ5HY5HY5HY5HY5HY5H]6H^6H^6H^6H^6H^G";
int x(int a,char*p){int c=0,i=0,b=-1;while(c>0||s[*p-32]){if(!c)c=s[*p-32]<0?-s[*p++-32]:1,i=s[*p++-32];b+=i,--c;if(a==b)return 1;}return 0;}

```

Please note that "shortest" in this case does not mean that the solution is in any way efficient; it simply means that it is the shortest source code solution. It does not require any Unicode support in the standard library, and in fact does not use the standard library at all. (Which I now understand is what code golf means ... I'm a newbie around here, what can I say.)

To build the lower and upper case data tables I worked as follows:

1. Downloaded UnicodeData.txt.
2. Extracted a list of all lines that included the text ";Ll;" or ";Lu;" to indicate a lower case letter or upper case letter respectively.
3. Built two vectors of code points using the data from step 2.
4. Converted each absolute code point value to a relative value, the difference between the previous code point and this code point. Because it is convenient for the difference to always be a positive integer (not zero or negative), I use -1 as the value of the first previous code point. In this way zero will not appear anywhere in the sequence.
5. Used a form of run length encoding to compress runs of identical values into a pair of values. If the next value appears two or more times consecutively, replace the sequence with the negative of the length of the sequence and the value. Otherwise the value only appears once, so just use it as is.
6. Terminated the compressed vector with zero to mark the end of the sequence.
7. I noticed there were 96 unique values in the run length encoded vectors, so I built an array of the unique integers and used the index into that array for the lower and upper case vectors.

The above process compressed the vector of lower case code points from 1751 unique values to 350 mostly small non-unique values. In like fashion, the upper case code point vector went from 1441 values to 331 values.

Next I wrote the unique value vector out as a comma separated list of integers suitable for including in source code. I assumed int was 32 bits to avoid using long so that I could save an additional four characters / bytes of source code. Then I wrote out the lower and upper case vectors as strings, where each character in the string has a code 32 greater than its index into the unique integer array. This saves about half the characters necessary to encode the lower & upper case array through omission of comma characters. Three of the characters used have to be escaped (\\", \\, and \177). They are assigned to unique integers that only appear once in the data so as to minimize the size of the string literals.

What I wound up with was a global array of integers, two global arrays of characters, and a function. An array named s for the unique signed integers, an array named u for the character based upper case code point indexes, and another array named l for the character based lower case code point indexes. The function x takes code point a and pointer to an array of characters p and returns 1 if the code point is in the decompressed / normalized array of code points or 0 otherwise.

If you want to determine if code point cp is lower case, you call "x(cp, l)". If you want to determine if it is upper case, you call "x(cp, u)".

Since the point to this exercise is to make the smallest code to accomplish the task, I never save the decompressed / normalized data. I decompress it piecemeal as I need it every time I call it.

It would be possible to terminate the while loop early if the code point I'm checking has already been passed by during decompression. That would add extra code so I didn't bother, deciding I'd rather pay the speed penalty.

I admit the code is ugly. I did not write it this way originally. Here is the C++ version that I derived the compact C version from:

```
const int Ii[] = {-74,-68,31054,-50,-49,-48,-47,-46,-44,-43,-39,-38,-37,-34,-33,-32,-30,-29,-28,-27,-26,-25,-24,-23,-22,-17,-16,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,19,20,27,28,29,53195,31,34,36,42,49,50,52,54,58,59,62,64,66,73,81,98,102,103,140,194,263,275,290,1066,1222,1230,2685,2732,2890,3379,6009,21254,22391,30996,53209};
const char Ll[] = "l5Hf`7HIAH2IH@IH7IJFIFHJIJKHLJKFHFJFIJIHIJKIJHJFHNFJ@IH?IHJIK1IBHFJHILDI!HI4HpIFKFHWZ-HIHKFH<IDHIFJHc&H9IQ4IJBIH(Ie+H{)Hh<HI.Hn I@H$I@HPCHRAHPAHPCHRAHPAHP;HJAHPAHPAHPDHIHNKFHIHPEHJHPAHRFHIHrKHKZFLJHPEHLdx'HJKHEILIHICHM$IHOILT,HIM~8IX=IoBIFH/IAHFIJDILIJIUDIk|BHTDHt5Hv*H\\5HYBHI9HY5HYEHFIBHI>HY5HY5HY5HY5HY5HY5HY5HY5HY3H[6HICHY6HICHY6HICHY6HICHY6HICHIG";
const char Lu[] = "i5Hm8HIBH^3IJAIJ7IHFIKHFIHIFHJEHIHIFHKHIHEIHIJIHIFHFIHKOEJAIJ@IFJIFH1IOHIHJIEHDIsIKVIFHFIHI:HI@H_JFHK=IMJIHJ#Ha:IQ3IHBIJ)IR,Hy,HIMz IQ%IQAHPCHRAHPAHPCHSEIPAHjEHTEHTEHTDHSEHqLKFHJFHJKDHNEIEHJEHRHMgw'HbIFHJEIEHIJPFH$IPIL\"8IX=IoBIK0IRFIHDILIJIUCI}5Hu*H\1775HY5HY5HYIHFJHJEHIAHY5HYHIEHJAHIBHZHIEHIDHIKBHZ5HY5HY5HY5HY5HY5H]6H^6H^6H^6H^6H^G";

bool isXx(int cp, const char* Xx)
{
    int count = 0, step = 0, code = -1;

    while ((count > 0) || (Ii[*Xx-32] != 0))
    {
        if (count == 0)
        {
            count = (Ii[*Xx-32] < 0) ? -(Ii[*(Xx++)-32]) : 1;
            step = Ii[*(Xx++)-32];
        }

        code += step;
        --count;

        if (cp < code)
            break;

        if (cp == code)
            return true;
    }

    return false;
}

inline bool isLl(int cp)
{
    return isXx(cp, Ll);
}

inline bool isLu(int cp)
{
    return isXx(cp, Lu);
}

```

In the end, the compact version takes 1922 1216 bytes (including CR+LF end of line sequences). The original version only takes 2271 1578 bytes.

To put this in context of the other solutions that only support the BMP, the equivalent compact version only takes 1451 1005 bytes (or 1800 1367 bytes for the original version).
> 6 votes

# Answer
## PowerShell, 2101

```
filter x{if(97..122+170,181,186+223..246+248..255+311..312+(0..26|%{$_*2+257})+
328..329+(0..6|%{$_*2+314})+(0..22|%{$_*2+331})+382..384+378,380,387,389+
396..397+392,402+409..411+405,414,417,419,421,426,427,424,429,432,441,442+
445..447+436,438,454,457,476,477+(0..7|%{$_*2+460})+495,496+(0..7|%{$_*2+479})+
499,501+563..569+(0..28|%{$_*2+505})+575,576,572,578+591..659+661..687+
891..893+(0..3|%{$_*2+583})+940..974+976,977,912+981..983+1007..1011+
(0..10|%{$_*2+985})+1013,1016,1019,1020+1072..1119+(0..16|%{$_*2+1121})+
(0..26|%{$_*2+1163})+1230,1231+(0..5|%{$_*2+1218})+1377..1415+7424..7467+
7522..7578+(0..33|%{$_*2+1233})+7829..7835+(0..73|%{$_*2+7681})+7936..7943+
7952..7957+7968..7975+7984..7991+8000..8005+8016..8023+8032..8039+
8048..8061+8064..8071+8080..8087+8096..8103+8112..8116+8118,8119+
(0..44|%{$_*2+7841})+8130..8135+8144..8147+8150..8151+8160..8167+8178..8180+
8182,8183,8126,8305,8319+8462..8463+8458,8467,8495,8500,8508,8509+8518..8521+
8505,8526,8580+11312..11358+11365,11366,11361,11368,11370,11372,11382,11383,
11380+11491,11492+11520..11557+64256..64262+64275..64279+65345..65370+
(0..48|%{$_*2+11393})-ne7544-ne8133-eq$_){1}elseif(65..90+192..214+216..222+
(0..27|%{$_*2+256})+(0..7|%{$_*2+313})+376,377+(0..22|%{$_*2+330})+385..386+
379,381+390..395+398..408+412..416+388,422,423,418,420,425,428+430..435+439,
440,437,444,452,455,458,497,500+(0..7|%{$_*2+461})+(0..8|%{$_*2+478})+
502..504+570..574+(0..28|%{$_*2+506})+579..582+577,584,586,588,590,902,908+
904..906+910..939+978..980+(0..11|%{$_*2+984})+1012,1015,1017,1018+1021..1071+
(0..16|%{$_*2+1120})+1216,1217+(0..26|%{$_*2+1162})+(0..5|%{$_*2+1219})+
1329..1366+4256..4293+(0..33|%{$_*2+1232})+(0..74|%{$_*2+7680})+7944..7951+
7960..7965+7976..7983+7992..7999+8008..8013+(0..44|%{$_*2+7840})+8040..8047+
8120..8123+8136..8139+8152..8155+8168..8172+8184..8187+(0..3|%{$_*2+8025})+
8450,8455,8469+8459..8461+8464..8466+8473..8477+8490..8493+8496..8499+8510,
8511,8484,8486,8488,8517+11264..11310+8579,11360+11362..11364+11367,11369,
11371,11381+65313..65338+(0..49|%{$_*2+11392})-notmatch'^(392|40[25]|414|432|572|912|930)$'-eq$_){2}else{0}}

```

Notes:

* Returns 1 for lower-case, 2 for upper-case and 0 for neither.
* Works only for BMP code points (as the `char` type in .NET represents a single UTF-16 code unit).

This uses a few distinct ways of compressing the code points for the two sets:

* adjacent code points are conflated in a range (`97..122`)
* code points that are two apart are conflated in a small pipeline (`0..22|%{$_*2+331}`)
* Ranges with only one missing value are done via `7522..7578-ne7544`, effectively removing that single element. This may not be done with all such rages by now.

I did the first two steps automatically, the third one and minor optimizations (`0..1|%{2*$_+11370}` is useless) were done by hand.

Some tests:

```
PS> [char]'a'|x
1
PS> [char]'A'|x
2
PS> [char]'1'|x
0
PS> [char]'α'|x
1
PS> [char]'Д'|x
2

```
> 1 votes

# Answer
## Python 3, 1369 chars (not bytes)

```
a='abcdefghijklmnopqrstuvwxyzªµºßàáâãäåæçèéêëìíîïðñòóôõöøùúûüýþÿāăąćĉċčďđēĕėęěĝğġģĥħĩīĭįıĳĵķĸĺļľŀłńņňŉŋōŏőœŕŗřśŝşšţťŧũūŭůűųŵŷźżžſƀƃƅƈƌƍƒƕƙƚƛƞơƣƥƨƪƫƭưƴƶƹƺƽƾƿǆǉǌǎǐǒǔǖǘǚǜǝǟǡǣǥǧǩǫǭǯǰǳǵǹǻǽǿȁȃȅȇȉȋȍȏȑȓȕȗșțȝȟȡȣȥȧȩȫȭȯȱȳȴȵȶȷȸȹȼȿɀɂɇɉɋɍɏɐɑɒɓɔɕɖɗɘəɚɛɜɝɞɟɠɡɢɣɤɥɦɧɨɩɪɫɬɭɮɯɰɱɲɳɴɵɶɷɸɹɺɻɼɽɾɿʀʁʂʃʄʅʆʇʈʉʊʋʌʍʎʏʐʑʒʓʕʖʗʘʙʚʛʜʝʞʟʠʡʢʣʤʥʦʧʨʩʪʫʬʭʮʯͱͳͷͻͼͽΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋόύώϐϑϕϖϗϙϛϝϟϡϣϥϧϩϫϭϯϰϱϲϳϵϸϻϼабвгдежзийклмнопрстуфхцчшщъыьэюяѐёђѓєѕіїјљњћќѝўџѡѣѥѧѩѫѭѯѱѳѵѷѹѻѽѿҁҋҍҏґғҕҗҙқҝҟҡңҥҧҩҫҭүұҳҵҷҹһҽҿӂӄӆӈӊӌӎӏӑӓӕӗәӛӝӟӡӣӥӧөӫӭӯӱӳӵӷӹӻӽӿԁԃԅԇԉԋԍԏԑԓԕԗԙԛԝԟԡԣԥԧաբգդեզէըթժիլխծկհձղճմյնշոչպջռսվտրցւփքօֆևᴀᴁᴂᴃᴄᴅᴆᴇᴈᴉᴊᴋᴌᴍᴎᴏᴐᴑᴒᴓᴔᴕᴖᴗᴘᴙᴚᴛᴜᴝᴞᴟᴠᴡᴢᴣᴤᴥᴦᴧᴨᴩᴪᴫᵢᵣᵤᵥᵦᵧᵨᵩᵪᵫᵬᵭᵮᵯᵰᵱᵲᵳᵴᵵᵶᵷᵹᵺᵻᵼᵽᵾᵿᶀᶁᶂᶃᶄᶅᶆᶇᶈᶉᶊᶋᶌᶍᶎᶏᶐᶑᶒᶓᶔᶕᶖᶗᶘᶙᶚḁḃḅḇḉḋḍḏḑḓḕḗḙḛḝḟḡḣḥḧḩḫḭḯḱḳḵḷḹḻḽḿṁṃṅṇṉṋṍṏṑṓṕṗṙṛṝṟṡṣṥṧṩṫṭṯṱṳṵṷṹṻṽṿẁẃẅẇẉẋẍẏẑẓẕẖẗẘẙẚẛẜẝẟạảấầẩẫậắằẳẵặẹẻẽếềểễệỉịọỏốồổỗộớờởỡợụủứừửữựỳỵỷỹỻỽỿἀἁἂἃἄἅἆἇἐἑἒἓἔἕἠἡἢἣἤἥἦἧἰἱἲἳἴἵἶἷὀὁὂὃὄὅὐὑὒὓὔὕὖὗὠὡὢὣὤὥὦὧὰάὲέὴήὶίὸόὺύὼώᾀᾁᾂᾃᾄᾅᾆᾇᾐᾑᾒᾓᾔᾕᾖᾗᾠᾡᾢᾣᾤᾥᾦᾧᾰᾱᾲᾳᾴᾶᾷιῂῃῄῆῇῐῑῒΐῖῗῠῡῢΰῤῥῦῧῲῳῴῶῷℊℎℏℓℯℴℹℼℽⅆⅇⅈⅉⅎↄⰰⰱⰲⰳⰴⰵⰶⰷⰸⰹⰺⰻⰼⰽⰾⰿⱀⱁⱂⱃⱄⱅⱆⱇⱈⱉⱊⱋⱌⱍⱎⱏⱐⱑⱒⱓⱔⱕⱖⱗⱘⱙⱚⱛⱜⱝⱞⱡⱥⱦⱨⱪⱬⱱⱳⱴⱶⱷⱸⱹⱺⱻⱼⲁⲃⲅⲇⲉⲋⲍⲏⲑⲓⲕⲗⲙⲛⲝⲟⲡⲣⲥⲧⲩⲫⲭⲯⲱⲳⲵⲷⲹⲻⲽⲿⳁⳃⳅⳇⳉⳋⳍⳏⳑⳓⳕⳗⳙⳛⳝⳟⳡⳣⳤⳬⳮⴀⴁⴂⴃⴄⴅⴆⴇⴈⴉⴊⴋⴌⴍⴎⴏⴐⴑⴒⴓⴔⴕⴖⴗⴘⴙⴚⴛⴜⴝⴞⴟⴠⴡⴢⴣⴤⴥꙁꙃꙅꙇꙉꙋꙍꙏꙑꙓꙕꙗꙙꙛꙝꙟꙡꙣꙥꙧꙩꙫꙭꚁꚃꚅꚇꚉꚋꚍꚏꚑꚓꚕꚗꜣꜥꜧꜩꜫꜭꜯꜰꜱꜳꜵꜷꜹꜻꜽꜿꝁꝃꝅꝇꝉꝋꝍꝏꝑꝓꝕꝗꝙꝛꝝꝟꝡꝣꝥꝧꝩꝫꝭꝯꝱꝲꝳꝴꝵꝶꝷꝸꝺꝼꝿꞁꞃꞅꞇꞌꞎꞑꞡꞣꞥꞧꞩꟺﬀﬁﬂﬃﬄﬅﬆﬓﬔﬕﬖﬗａｂｃｄｅｆｇｈｉｊｋｌｍｎｏｐｑｒｓｔｕｖｗｘｙｚ'
def f(x):
 if x in a:
  return 'lowercase'
 if x in a.upper()+'ℂℇℋℍİℑℐℒℕℙℛℚℝℜẞℤΩℨÅKℭℬℱℰℳℿℾⅅℌϓϒϔϴ':
  return 'uppercase'
 return 'neither'

```

Almost as small as the other answer (uses the same approach but using literals instead of numbers) but no effort at all.

Your browser may not render the chars properly and it is UTF-8

Edit: Making uppercase characters and adding those which didn't correspond to any lowercase saved a ton of chars
> 1 votes

# Answer
## Python 2: 811 characters (after minification)

```
def D(s):
    k = 0
    for i in map(ord, s.decode('base64').decode('utf8')):
        for j in range(i // 2):
            yield k
            k ^= i % 2
        k ^= 1 - i % 2
U = list(D('woI0w4ouAw5CbwQfBF0ECQYEBwQDBgQIAwQDBgYEAwQLBAUEBQQDBgcEBgMOAwQDBAMEHwQjBAMEBQZ1DgQDBAQFCBHJggcGAx4FBgcEAyIDEkYDBAYGLwoDBAUEBGZgQxJtBBkEwqccTOGakkzhqbTEqxLDgxIQEAwUEBAQEAwWDxAQwpAIGAgYCBgKFgjIjAMIAwYGBAYEAwYKDA0IBAgUBAoDegPhk7heYgUGBA0GBAMEAxTDh++Kuj8GFyYvxJYbBnsUCQQRCAPqvKo0xoo='))
L = list(D('w4I0XgMUAwgDSDADEG8EHwRdBAkGBAcEAwYECAMEAwYGBAMECwQFBAUEAwYHBAQEBgwDBAMEIQQjBAQHBnUOBAMEBAUIEcKKAzbGggcGAwYGJAM2RgMEBgYvCgUEAwQEZmBFEmsEGQTCqXpO4ruwWGwsA0TDjMSpEsODEhAMFBAQEBAMFBAQEBAcBBAQEBAQEAoDBAwDBgYDBBAIBAQQEBQGAwTDsgMaA8SUAwYEBgM2AwgDCAMEBBAICANqA+GVll4EAwYEDQgFBAMOCMOFBDZM74i2PwYXJi/ElhkGfxAJBBMIA+qbpg4YCuChkjTFig=='))
f = lambda x: U[x] and 'upper' or L[x] and 'lower' or 'neither'

```

This supports the base multi-lingual plane only (as for the other answers). You could make it a bit shorter by omitting the encoding/decoding steps (and just putting Unicode strings into the program source), but then I think you really ought to count the length in bytes rather than characters.
> 1 votes

---
Tags: code-golf
---


title: calculate days of a month

text:
# Question
Title: calculate days of a month
I would like to see the shortest expression to calculate the days (or the last day) of a month in any language.

Considering y as the number of year and m as month.

Basic rules

* without date / time functions.
* considering leap years.
* there is not other rule.

# Answer
## C, 40 33 31 characters

Reduced length in three ways:
1. Replaced `m%2^m>7` with `m^m>7`. The first is 0/1 in 30/31 day months, the second is even/odd. But the high bits don't matter, because their all set in 30 anyway (months with 30/31 days look like a really good idea now).
2. Used mob's idea (`y%(y%100?4:400)` as a leap year test)
3. Used `<1` instead of `!` saves parenthesis.
4. `y%(y%100?4:400)` -\> `y%(y%25?4:16)` \- works the same.

```
m-2?30|m^m>7:28|y%(y%25?4:16)<1

```
> 5 votes

# Answer
## C, 47 45 characters

```
30+(m>7^m&1)-(m^2?0:2-!(y%100||(y/=100),y%4))

```

Taken from an answer to an earlier question where I borrowed a couple of tricks from another user. Returns the length of month `m` in year `y` for the Gregorian calendar. ugoren's answer to the same question is shorter and may give a shorter answer to this question.

With thanks to mob for his leap year calculation.
> 5 votes

# Answer
I've already answered it before in stackoverflow:

```
(62648012>>m*2&3)+28+(m==2&&y%4==0)

```

https://stackoverflow.com/questions/2675720/calculate-days-of-month/11675530#11675530

\[EDIT\] Matt advertised me about leap yars below and he's asked about language. About the language: the expression works on c/c++ and maybe others.

So, the simplest form will work until 2100... but to prevents the 2100 bug :) I've copied the Matt solution to leap year:

```
(62648012>>m*2&3)+28+(m==2&&(y%4==0&&(y%100!=0||y%400==0)))

```
> 3 votes

# Answer
# Python 64 61 59

```
(62648012>>m*2&3)+28+(m==2and y%4==0*(y%100>0 or y%400==0))

```

Based on olivecoder's solution, but accounting for multiples of 100.
> 3 votes

# Answer
## VBA, 84

```
28+Val(Mid("303232332323",M,1))-(M=2 And Y Mod 4=0 And (Y Mod 100>0 Or Y Mod 400=0))

```
> 2 votes

# Answer
# Python 50 ~~54~~ ~~57~~

```
29+{2:y%(y%25and 4or 16)and-1}.get(m,(1&m^m>>3)+1)

```

with inspiration from mob, and the interesting fact, that a dict saves 1 byte in contrast to m==2and(..)or(...)
> 2 votes

# Answer
# Mathematica 97 91 83 82 78 76

A bit long, but gets the job done.

> d = y ~ Divisible ~ \# & ; 30 \+ { 1 , Boole \[ d @ 400 ∨ ( d @ 4 ∧ ¬ d @ 100 ) \] \- 2 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 } \[ \[ m \] \]
> 1 votes

# Answer
### VB.net (89 81c)

shame about the date function restriction as **VB.net** at only **(21c)**

```
Date.DaysInMonth(y,m)

```

may have won one for a change. DAMN YOU!

So current best is **89c**

{0,31,28,31,30,31,30,31,31,30,31,30,31}(m)+(If( m=2 AndAlso (y Mod 4)=0 AndAlso (y Mod 400)\>0,1,0)

```
{0,31,28,31,30,31,30,31,31,30,31,30,31}(m)+(If( m=2 And (y Mod 4)=0 And (y Mod 400)>0,1,0)

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Visualise long multiplication with ASCII art
## The challenge

Write a program that takes two integers from standard input, separated by a comma, and then prints a visualisation of long multiplication of those two integers to standard output.

Eg:

**Input**

```
14, 11

```

**Program output**

```
     14
    x11
   _____
     14
    14
  ______
    154

```

**Input**

```
-7, 20

```

**Program output**

```
     -7
    x20
   _____
     00
    14
   _____
   -140

```

Assume always correct inputs and numbers in the range \[-999, 999\]

## Winning criteria

Shortest code wins!

# Answer
## Perl, 108 chars

Best of breed 108 char solution, incorporating some ideas from Orabig.

```
($x,$y)=<>=~/[-\d]+/g;printf"%7s
",$_ for$x,x.$y,"-"x7,(map{abs($x*$_).$"x$i++}reverse$y=~/\d/g),"-"x7,$x*$y

```

Earlier 139 char solution

```
sub P{sprintf"%*d",@_}
($x,$y)=<>=~/[^,]+/g;$,=$/;
print P(7,$x),"  x".P(4,$y),"-"x7,(map{P 7-$i++,abs$_*$x}reverse$y=~/\d/g),
"-"x7,P 7,$x*$y

```
> 3 votes

# Answer
# Mathematica 213 217 197 193 186 184 193 184 177

**Code**

```
a_~g~b_ :=
With[{e = IntegerDigits@b}, Column[Flatten@{a, UnderBar["x " <> IntegerString[b]],
Table[Row @@ {PadRight[{a Reverse[e][[i]]}, i, " "]}, {i, Length@e}], OverBar[a b]},
Alignment -> Right]]

```

**Usage**

```
g[845, 921]

```
> 5 votes

# Answer
Python, 174 170:

```
a,b=input();r,s=str(a),str(b);h=len(r+s)*'-';print'\n'.join(["%9s\n%9s\n%9s"%(r,'x'+s,h)]+["%%%ii"%(9-i)%(int(d)%10*a)for i,d in enumerate(s[::-1])]+["%9s\n%9i"%(h,a*b)])

```

Usage: exactly as requested, run and input the values in standard input.

To see running: http://ideone.com/S8xNb

Output:

```
     1234
    x5678
 --------
     9872
    8638
   7404
  6170
 --------
  7006652

```

Thanks to fabiocerqueira and beary605 and David Carraher
> 1 votes

# Answer
Python, 145, another answer with a little bit different output.

**Code**

```
a,b=input();h=6*'-';print'\n'.join(["%6i\nx%5i\n%s"%(a,b,h)]+["%%%ii"%(6-i)%(int(d)%10*a)for i,d in enumerate(str(b)[::-1])]+["%s\n%6i"%(h,a*b)])

```

**Usage**

just as requested

**Output**

```
   999
x  999
------
  8991
 8991
8991
------
998001

```

To see running: http://ideone.com/mdR18
> 1 votes

# Answer
**Perl**, 157 151 150 144 141 133 chars :

```
($x,$y)=<>=~/[-\d]+/g;map{$z=~s/z/ z/g;$z=(abs$x*$_)."z$z"}split//,abs$y;map{printf"%6s
",$_}$x,"x$y",$b="-"x6,(split/z/,$z),$b,$x*$y

```

**Usage :**

```
>echo "-123, 456" | perl mult.pl
   -123
   x456
-------
    738
   615
  492
-------
 -56088

```
> 1 votes

---
Tags: code-golf, ascii-art, arithmetic
---


# Question
Title: Generate a valid sequence of numbers with specific rules
## The challenge

The program must return a valid sequence of numbers into some rules

## Rules

* `x` is the size of the sequence;
* `x` cannot be less than `4` or greater than `9` (Thanks David Carraher);
* Digits of the sentence can't repeat, each one must appear once;
* All digits between `1` to `x` must be in the sequence;
* A valid sequence never begins nor ends with `1` or `x`;
* Into the sequence, numbers can never appear "together";

## Examples

If `x=4`:
`2413` valid
`3142` valid

`1423` not valid, because begins with `1` and `23` are "together".
`2134` not valid, because ends with `x` and `34` are "together".

Still don't get it? Other example:

If `x=8`:
`28375146` valid, because don't start with `1` nor `x`(8), don't end with `1` nor `x`, and no numbers are "together"(no numbers touches, no numbers are the next or previous)

Sorry, I really don't know how to explain the last rule. Hope the example make it understandable.

## Additional Information

* `x` does not need to be an input, you can show the outputs for `x=4` and `x=9` working;
* Since **any language will be accepted** and, I don't know how all of them work, I will ask you people to help me with this;
* The winner will be the one who got more up-votes in 1 week, so please, vote the answer you find the best; I will mark it as the Correct one;

Good, luck. =)

# Answer
> 3 votes
## GolfScript (17 16 chars)

Assuming input on stdin and output on stdout.

```
~:^),(;{-2\^%?}$

```

Almost alphanumeric-free...

# Answer
> 1 votes
May I try to answer my own challenge?

## Javascript (35 chars)

```
a="1";for(i=x;i>1;i--)a=i%2?a+i:i+a

```

Outputs

```
document.write(a);

4 => 2413
5 => 24153
6 => 246153
7 => 2461753
8 => 24681753
9 => 246819753

```

# Answer
> 1 votes
# Mathematica 38

This simply returns the digits less than or equal to `x`, in the order in which they appear below.

```
Row@Select[{2, 9, 6, 4, 7, 1, 8, 5, 3},#<x+1&]

```

The results from 4 through 9:

# Answer
> 0 votes
# Haskell 78

```
a 4=[3,1,4,2]
a x=let b=filter even [1..x]++filter odd[1..x]in tail b++[b!!0]

```

This defines a function `a` that takes one parameter, the desired length of the sequence. This function returns a list of numbers in that sequence. I believe this works for `x >= 4`

This can probably be golfed further (I don't have that much experience in haskell)

### Example (in ghci)

```
ghci> a 4
[3,1,4,2]
ghci> a 9
[4,6,8,1,3,5,7,9,2]

```

# Haskell 25

This version is from before a rule change that now requires that every digit from 1 to x be used exactly once in the sequence

This should work for any sequence of length \> 2 (even though the rules only required 4 \<= x \<= 9)

```
putStrLn$take x$cycle"02"

```

### Input

The number of digits in the sequence is stored in x.

### Output

x = 6 :: Int

```
020202

```

x = 4 :: Int

```
0202

```

# Answer
> 0 votes
# Perl 96 chars (obsolete solution since the new rules)

For what I can understand from the rules, we can assume that X is predefined. Then this solution should work :

```
for(2x$x..9x$x){if(!/^$x/+/$x$/+/1$/){$L=0;map{$d=$L-$_;abs$d>1||next;$L=$_}split//;print;exit}}

```

which is 96 characters long, although the algorithm is very naive.

It gives the following solutions :

```
2
30
240
2402
24020
240202
2402020
24020202
240202020

```

Thus, it seems obvious than there is room to a much simpler program which directly computes a solution of this form...

---

The following program outputs **all** valid sequences with any given length X (takes X in STDIN)

```
$x=<>;$b=10**$x;for($b/10..$b-1){if(!/^$x/+/$x$/+/1$/){$L=0;map{$d=$L-$_;abs$d>1||next;$L=$_}split//;print"$_
"}}

```

If you want to output ALL possible solutions (for any X), then the program becomes (102 chars) :

```
for(;;){$x=length$_++;if(!/^$x/+/$x$/+/1$/){$L=0;map{$d=$L-$_;abs$d>1||next;$L=$_}split//;print"$_
"}}

```

# Answer
> 0 votes
# PHP, 64

If I understand the rules correctly, this should work:

`for($i=1;$i<=$x;$i++)echo($x%2?2*$i%$x+1:2*$i-($x+1)*($i>$x/2));`

If x is odd, this simply cycles through multiples of 2 % x + 1 to produce sequences like 357924681. If x is even, this does the same, but halfway through subtracts 1+x because 2i%x+1 would otherwise never produce even values.

# Answer
> 0 votes
## GolfScript, ~~22~~ 20 chars

```
~.1|,.+2%(;(@.1&,~;\

```

Outputs the following sequences for the inputs `4` through `9`:

```
2413
41352
246135
4613572
24681357
468135792

```

For even inputs, just `~),.+2%(;` would suffice. I'm not too happy with the kluge for handling odd input values; there's got to be a more efficient way to do it.

**Edit:** Saved two chars by changing the output for odd inputs a bit and playing silly stack manipulation tricks. Still not too happy with the length.

# Answer
> 0 votes
Python, 37

```
range(3,x+1,2)+[1]+range(4,x+1,2)+[2])

```

http://ideone.com/xK40m

# Answer
> 0 votes
## Python,30:

```
' 3579'[:(1+x)/2]+'1468'[:x/2]+'2'

```

http://ideone.com/3csRh

---
Tags: popularity-contest, number, sequence
---


title: Generate N number of "Go First" dice

text:
# Question
Title: Generate N number of "Go First" dice
## Background

As described here http://www.ericharshbarger.org/dice/#gofirst\_4d12, "Go First" Dice is a set of four dice, each with unique numbering, so that:

* There will never be a tie. Each die has a unique set of numbers.
* Regardless of what subset of dice are rolled against one another, each player will always have an equal chance of rolling the high number.

Here is the specific numbering for the four dice mentioned, as an example:

```
DICE COUNT: 4
FACE COUNT: 12
D1: 1,8,11,14,19,22,27,30,35,38,41,48
D2: 2,7,10,15,18,23,26,31,34,39,42,47
D3: 3,6,12,13,17,24,25,32,36,37,43,46
D4: 4,5, 9,16,20,21,28,29,33,40,44,45

```

(via)

## Goal

Without requiring any *particular* result, I would like to be able to generate a set of `N` "Go First" dice... Such that, example output **might** look like so (formatted, python console):

```
    >>> generate_dice(players=4)
    [[1,8,11,14,19,22,27,30,35,38,41,48],
     [2,7,10,15,18,23,26,31,34,39,42,47],
     [3,6,12,13,17,24,25,32,36,37,43,46],
     [4,5,9,16,20,21,28,29,33,40,44,45]]

```

The number of sides here is chosen just for example purposes, because it matches the other example given. The number of sides of the dice can be determined by the algorithm used.

Ideally the solution would be in Python, but I can also read PHP, Javascript, some Ruby, quite well.

I'm honestly puzzling over this, and would love to understand what terminology/math I should have studied to figure this out. I've tried to explain it before, but seem to be having trouble not using words that imply too many things about what should be generated, and what odds should be, etc. I'm specifically interested in being able to generate "a set of N 'Go First' dice".

## Extra

Here's some ugly python, to "prove" the dice, and perhaps give an example.

```
def fair_chance(die1, die2):
    wins = 0
    losses = 0
    ties = 0
    for i in die1:
        for x in die2:
            if cmp(i, x) < 0:
                losses += 1
            if cmp(i, x) > 0:
                wins += 1
            if cmp(i, x) == 0:
                ties += 1
    if wins == losses and losses != 0 and ties == 0:
        return True
    return False

```

Give the above example dice:

```
D1 = [1,8,11,14,19,22,27,30,35,38,41,48]
D2 = [2,7,10,15,18,23,26,31,34,39,42,47]
D3 = [3,6,12,13,17,24,25,32,36,37,43,46]
D4 = [4,5, 9,16,20,21,28,29,33,40,44,45]

fair_chance(D1, D2)  # True
fair_chance(D1, D3)  # True
fair_chance(D1, D4)  # True
fair_chance(D2, D3)  # True
fair_chance(D2, D4)  # True
fair_chance(D3, D4)  # True

```

Thus, the function `generate_dice` should work, such that output in a Python shell would look like this:

```
>>> dice = generate_dice(players=4)
>>> D1 = dice[0]
>>> D2 = dice[1]
>>> D3 = dice[2]
>>> D4 = dice[3]
>>> fair_chance(D1, D2)
True
>>> fair_chance(D1, D3)
True
>>> fair_chance(D1, D4)
True
>>> fair_chance(D2, D3)
True
>>> fair_chance(D2, D4)
True
>>> fair_chance(D3, D4)
True

```

# Answer
My python is a little rusty because I haven't used it in a very long time, but how about something like this:

```
def generate_dice(count, sides = 12):
  dice = []
  for i in range(count):
    dice.append([])

  value = 0
  for sindex in range(sides):
    if sindex % 2:
      for dindex in range(count):
        value += 1
        dice[dindex].append(value)
    else:
      for dindex in reversed(range(count)):
        value += 1
        dice[dindex].append(value)
  return dice

```

The pattern here is simpler than the one you linked, but it appears to work as long as the number of sides on the dice is even. I originally did this in C# and then converted it to python.
> 1 votes

# Answer
Well, I believe that this deals with telescoping series. As it turns out, the number of dice and number of sides you use is very important. For example, try to make 4, 4 sided dice that fits the same requirement.

Using the numbers from 1 to 16, one of the dice has to get the number 16. Which ever dice has 16 already has a 25% chance of landing on the highest number when all 4 are rolled. However, the chance that any particular dice is first must = 25%. Thus, the remaining numbers must have 0% chance of being the highest number. This makes the first dice \[1,2,3,16\]. However this doesn't fit the requirement that when rolling 2 dice, you still have a equal probability of going first. Now you only have 25% instead of 50%. Thus when you have 4 dice, you must have more than 4 sides for these requirements to work.

I think the fact that they used 4 d12 is not just by chance. I would bet it's the minimum number of sides for 4 dice that works. I think if 4d8 or 4d6 worked, they would have just done that, because it's simpler to prove correct.

Thus, with 4 dice, you need a number of sides which is \>=12 to meet all the properties.

In the example, the die with the highest number (48) has only a 1/12 of getting that number. Since this die has a 1/12 of going first, it should also have a 1/12 of going last, so it gets a (1).

Notice that the relative order of the numbers of each dice forms a sort of palindrome of pairs. (1 4) (3 2) (3 2) (3 2) (3 2) (1 4) the first dice sequence This is obviously on purpose. I'd check to see if other palindromes have the same property.
> 1 votes

---
Tags: math, python, programming-puzzle
---