Skip to content

Instantly share code, notes, and snippets.

@ungood
Created June 29, 2012 15:01
Show Gist options
  • Save ungood/3018465 to your computer and use it in GitHub Desktop.
Save ungood/3018465 to your computer and use it in GitHub Desktop.
Silly Puzzle solved for multiple bases
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
namespace ConsoleApplication4
{
public static class BigIntegerExtensions
{
private static readonly char[] DigitLookup = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
public static string Format(this BigInteger i, int baseNumber)
{
var sb = new StringBuilder();
foreach (var digit in i.Digits(baseNumber).Reverse())
sb.Append(DigitLookup[digit]);
return sb.ToString();
}
public static IEnumerable<int> Digits(this BigInteger value, int baseNumber)
{
value = BigInteger.Abs(value);
while (value != BigInteger.Zero)
{
BigInteger digit;
value = BigInteger.DivRem(value, baseNumber, out digit);
yield return (int)digit;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Xml.Linq;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
var tests = Enumerable.Range(2, 32).AsParallel();
tests.ForAll(test =>
{
var puzzle = new Puzzle(test);
var answers = puzzle.FindAnswers(test - 1);
Console.WriteLine(test + ":" + answers.Count());
});
Console.WriteLine("Done");
Console.ReadLine();
}
}
public class Puzzle
{
public int NumberBase { get; private set; }
public Puzzle(int numberBase)
{
NumberBase = numberBase;
}
public IEnumerable<BigInteger> FindAnswers(int reps)
{
var seed = Range(1, NumberBase - 1).ToList();
for (int i = 2; i <= reps; i++)
{
seed = GetNextResults(seed, i).ToList();
if (seed.Count == 0)
return Enumerable.Empty<BigInteger>();
}
return seed;
}
public IEnumerable<BigInteger> Range(int start, int count)
{
return Enumerable.Range(start, count).Select(i => (BigInteger)i);
}
public IEnumerable<BigInteger> GetNextResults(IEnumerable<BigInteger> current, BigInteger index)
{
return current.SelectMany(ConcatUniqueDigits).Where(x => x % index == 0);
}
public IEnumerable<BigInteger> ConcatUniqueDigits(BigInteger i)
{
return Enumerable.Range(1, NumberBase - 1)
.Where(digit => !ContainsDigit(i, digit))
.Select(digit => (i * NumberBase) + digit);
}
public bool ContainsDigit(BigInteger value, int digitToFind)
{
return value.Digits(NumberBase).Contains(digitToFind);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment